2563d9ec6f34cf4f5f075c641a7d811ee1d13820
[WebKit.git] / JavaScriptCore / VM / CodeGenerator.cpp
1 /*
2  * Copyright (C) 2008 Apple Inc. All rights reserved.
3  * Copyright (C) 2008 Cameron Zwarich <cwzwarich@uwaterloo.ca>
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  *
9  * 1.  Redistributions of source code must retain the above copyright
10  *     notice, this list of conditions and the following disclaimer.
11  * 2.  Redistributions in binary form must reproduce the above copyright
12  *     notice, this list of conditions and the following disclaimer in the
13  *     documentation and/or other materials provided with the distribution.
14  * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
15  *     its contributors may be used to endorse or promote products derived
16  *     from this software without specific prior written permission.
17  *
18  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
19  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
20  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
22  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
24  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
25  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28  */
29
30 #include "config.h"
31 #include "CodeGenerator.h"
32
33 #include "Machine.h"
34 #include "function.h"
35
36 using namespace std;
37
38 namespace KJS {
39
40 /*
41     The layout of a register frame looks like this:
42
43     For
44
45     function f(x, y) {
46         var v1;
47         function g() { }
48         var v2;
49         return (x) * (y);
50     }
51
52     assuming (x) and (y) generated temporaries t1 and t2, you would have
53
54     ------------------------------------
55     |  x |  y |  g | v2 | v1 | t1 | t2 | <-- value held
56     ------------------------------------
57     | -5 | -4 | -3 | -2 | -1 | +0 | +1 | <-- register index
58     ------------------------------------
59     | params->|<-locals      | temps->
60
61     Because temporary registers are allocated in a stack-like fashion, we
62     can reclaim them with a simple popping algorithm. The same goes for labels.
63     (We never reclaim parameter or local registers, because parameters and
64     locals are DontDelete.)
65
66     The register layout before a function call looks like this:
67
68     For
69
70     function f(x, y)
71     {
72     }
73
74     f(1);
75
76     >                        <------------------------------
77     <                        >  reserved: call frame  |  1 | <-- value held
78     >         >snip<         <------------------------------
79     <                        > +0 | +1 | +2 | +3 | +4 | +5 | <-- register index
80     >                        <------------------------------
81     | params->|<-locals      | temps->
82
83     The call instruction fills in the "call frame" registers. It also pads
84     missing arguments at the end of the call:
85
86     >                        <-----------------------------------
87     <                        >  reserved: call frame  |  1 |  ? | <-- value held ("?" stands for "undefined")
88     >         >snip<         <-----------------------------------
89     <                        > +0 | +1 | +2 | +3 | +4 | +5 | +6 | <-- register index
90     >                        <-----------------------------------
91     | params->|<-locals      | temps->
92
93     After filling in missing arguments, the call instruction sets up the new
94     stack frame to overlap the end of the old stack frame:
95
96                              |---------------------------------->                        <
97                              |  reserved: call frame  |  1 |  ? <                        > <-- value held ("?" stands for "undefined")
98                              |---------------------------------->         >snip<         <
99                              | -7 | -6 | -5 | -4 | -3 | -2 | -1 <                        > <-- register index
100                              |---------------------------------->                        <
101                              |                        | params->|<-locals       | temps->
102
103     That way, arguments are "copied" into the callee's stack frame for free.
104
105     If the caller supplies too many arguments, this trick doesn't work. The
106     extra arguments protrude into space reserved for locals and temporaries.
107     In that case, the call instruction makes a real copy of the call frame header,
108     along with just the arguments expected by the callee, leaving the original
109     call frame header and arguments behind. (The call instruction can't just discard
110     extra arguments, because the "arguments" object may access them later.)
111     This copying strategy ensures that all named values will be at the indices
112     expected by the callee.
113 */
114
115 #ifndef NDEBUG
116 bool CodeGenerator::s_dumpsGeneratedCode = false;
117 #endif
118
119 void CodeGenerator::setDumpsGeneratedCode(bool dumpsGeneratedCode)
120 {
121 #ifndef NDEBUG
122     s_dumpsGeneratedCode = dumpsGeneratedCode;
123 #else
124     UNUSED_PARAM(dumpsGeneratedCode);
125 #endif
126 }
127
128 void CodeGenerator::generate()
129 {
130     m_codeBlock->numLocals = m_codeBlock->numVars + m_codeBlock->numParameters;
131     m_codeBlock->thisRegister = m_thisRegister.index();
132     if (m_shouldEmitDebugHooks)
133         m_codeBlock->needsFullScopeChain = true;
134
135     m_scopeNode->emitCode(*this);
136
137 #ifndef NDEBUG
138     if (s_dumpsGeneratedCode) {
139         JSGlobalObject* globalObject = m_scopeChain->globalObject();
140         m_codeBlock->dump(globalObject->globalExec());
141     }
142 #endif
143
144     m_scopeNode->children().shrinkCapacity(0);
145     if (m_codeType != EvalCode) { // eval code needs to hang on to its declaration stacks to keep declaration info alive until Machine::execute time.
146         m_scopeNode->varStack().shrinkCapacity(0);
147         m_scopeNode->functionStack().shrinkCapacity(0);
148     }
149 }
150
151 bool CodeGenerator::addVar(const Identifier& ident, RegisterID*& r0, bool isConstant)
152 {
153     int index = m_nextVar;
154     SymbolTableEntry newEntry(index, isConstant ? ReadOnly : 0);
155     pair<SymbolTable::iterator, bool> result = symbolTable().add(ident.ustring().rep(), newEntry);
156
157     if (!result.second)
158         index = result.first->second.getIndex();
159     else {
160         --m_nextVar;
161         ++m_codeBlock->numVars;
162
163         m_locals.append(index);
164     }
165
166     r0 = &m_locals[localsIndex(index)];
167     return result.second;
168 }
169
170 CodeGenerator::CodeGenerator(ProgramNode* programNode, const Debugger* debugger, const ScopeChain& scopeChain, SymbolTable* symbolTable, CodeBlock* codeBlock, VarStack& varStack, FunctionStack& functionStack, bool canCreateVariables)
171     : m_shouldEmitDebugHooks(!!debugger)
172     , m_scopeChain(&scopeChain)
173     , m_symbolTable(symbolTable)
174     , m_scopeNode(programNode)
175     , m_codeBlock(codeBlock)
176     , m_thisRegister(Machine::ProgramCodeThisRegister)
177     , m_finallyDepth(0)
178     , m_dynamicScopeDepth(0)
179     , m_codeType(GlobalCode)
180     , m_continueDepth(0)
181     , m_nextVar(-1)
182     , m_propertyNames(&scopeChain.globalObject()->globalExec()->propertyNames())
183     , m_lastOpcodeID(op_end)
184 {
185     // Global code can inherit previously defined symbols.
186     int size = symbolTable->size() + 1; // + 1 slot for  "this"
187
188     // Add previously defined symbols to bookkeeping.
189     m_locals.resize(size);
190     SymbolTable::iterator end = symbolTable->end();
191     for (SymbolTable::iterator it = symbolTable->begin(); it != end; ++it)
192         m_locals[localsIndex(it->second.getIndex())].setIndex(it->second.getIndex());
193
194     // Shift new symbols so they get stored prior to previously defined symbols.
195     m_nextVar -= size;
196
197     JSGlobalObject* globalObject = scopeChain.globalObject();
198
199     ExecState* exec = globalObject->globalExec();
200     
201     // FIXME: Move the execution-related parts of this code to Machine::execute.
202
203     if (canCreateVariables) {
204         for (size_t i = 0; i < functionStack.size(); ++i) {
205             FuncDeclNode* funcDecl = functionStack[i].get();
206             globalObject->removeDirect(funcDecl->m_ident); // Make sure our new function is not shadowed by an old property.
207             emitNewFunction(addVar(funcDecl->m_ident, false), funcDecl);
208         }
209
210         for (size_t i = 0; i < varStack.size(); ++i) {
211             if (!globalObject->hasProperty(exec, varStack[i].first))
212                 emitLoad(addVar(varStack[i].first, varStack[i].second & DeclarationStacks::IsConstant), jsUndefined());
213         }
214     } else {
215         for (size_t i = 0; i < functionStack.size(); ++i) {
216             FuncDeclNode* funcDecl = functionStack[i].get();
217             globalObject->putWithAttributes(exec, funcDecl->m_ident, funcDecl->makeFunction(exec, scopeChain.node()), DontDelete);
218         }
219         for (size_t i = 0; i < varStack.size(); ++i) {
220             if (globalObject->hasProperty(exec, varStack[i].first))
221                 continue;
222             int attributes = DontDelete;
223             if (varStack[i].second & DeclarationStacks::IsConstant)
224                 attributes |= ReadOnly;
225             globalObject->putWithAttributes(exec, varStack[i].first, jsUndefined(), attributes);
226         }
227     }
228 }
229
230 CodeGenerator::CodeGenerator(FunctionBodyNode* functionBody, const Debugger* debugger, const ScopeChain& scopeChain, SymbolTable* symbolTable, CodeBlock* codeBlock)
231     : m_shouldEmitDebugHooks(!!debugger)
232     , m_scopeChain(&scopeChain)
233     , m_symbolTable(symbolTable)
234     , m_scopeNode(functionBody)
235     , m_codeBlock(codeBlock)
236     , m_finallyDepth(0)
237     , m_dynamicScopeDepth(0)
238     , m_codeType(FunctionCode)
239     , m_continueDepth(0)
240     , m_nextVar(-1)
241     , m_propertyNames(&scopeChain.globalObject()->globalExec()->propertyNames())
242     , m_lastOpcodeID(op_end)
243 {
244     const Node::FunctionStack& functionStack = functionBody->functionStack();
245     for (size_t i = 0; i < functionStack.size(); ++i) {
246         FuncDeclNode* funcDecl = functionStack[i].get();
247         const Identifier& ident = funcDecl->m_ident;
248
249         m_functions.add(ident.ustring().rep());
250         emitNewFunction(addVar(ident, false), funcDecl);
251     }
252
253     const Node::VarStack& varStack = functionBody->varStack();
254     for (size_t i = 0; i < varStack.size(); ++i) {
255         const Identifier& ident = varStack[i].first;
256         if (ident == m_propertyNames->arguments)
257             continue;
258
259         RegisterID* r0;
260         addVar(ident, r0, varStack[i].second & DeclarationStacks::IsConstant);
261     }
262
263     Vector<Identifier>& parameters = functionBody->parameters();
264     m_nextParameter = m_nextVar - parameters.size(); // parameters are allocated prior to vars
265     m_locals.resize(localsIndex(m_nextParameter) + 1); // localsIndex of 0 => m_locals size of 1
266
267     // Add "this" as a parameter
268     m_thisRegister.setIndex(m_nextParameter);
269     ++m_nextParameter;
270     ++m_codeBlock->numParameters;
271     
272     for (size_t i = 0; i < parameters.size(); ++i)
273         addParameter(parameters[i]);
274 }
275
276 CodeGenerator::CodeGenerator(EvalNode* evalNode, const Debugger* debugger, const ScopeChain& scopeChain, SymbolTable* symbolTable, EvalCodeBlock* codeBlock)
277     : m_shouldEmitDebugHooks(!!debugger)
278     , m_scopeChain(&scopeChain)
279     , m_symbolTable(symbolTable)
280     , m_scopeNode(evalNode)
281     , m_codeBlock(codeBlock)
282     , m_thisRegister(Machine::ProgramCodeThisRegister)
283     , m_finallyDepth(0)
284     , m_dynamicScopeDepth(0)
285     , m_codeType(EvalCode)
286     , m_continueDepth(0)
287     , m_nextVar(-1)
288     , m_propertyNames(&scopeChain.globalObject()->globalExec()->propertyNames())
289     , m_lastOpcodeID(op_end)
290 {
291     m_codeBlock->numVars = 1; // Allocate space for "this"
292 }
293
294 CodeGenerator::~CodeGenerator()
295 {
296 }
297
298 RegisterID* CodeGenerator::addParameter(const Identifier& ident)
299 {
300     // Parameters overwrite var declarations, but not function declarations,
301     // in the symbol table.
302     RegisterID* result = 0;
303     UString::Rep* rep = ident.ustring().rep();
304     if (!m_functions.contains(rep)) {
305         symbolTable().set(rep, m_nextParameter);
306         m_locals[localsIndex(m_nextParameter)].setIndex(m_nextParameter);
307         result = &(m_locals[localsIndex(m_nextParameter)]);
308     }
309
310     // To maintain the calling convention, we have to allocate unique space for
311     // each parameter, even if the parameter doesn't make it into the symbol table.
312     ++m_nextParameter;
313     ++m_codeBlock->numParameters;
314     return result;
315 }
316
317 RegisterID* CodeGenerator::registerForLocal(const Identifier& ident)
318 {
319     if (m_codeType == FunctionCode && ident == m_propertyNames->arguments)
320         m_codeBlock->needsFullScopeChain = true;
321
322     if (ident == m_propertyNames->thisIdentifier)
323         return &m_thisRegister;
324
325     if (!shouldOptimizeLocals())
326         return 0;
327
328     SymbolTableEntry entry = symbolTable().get(ident.ustring().rep());
329     if (entry.isEmpty())
330         return 0;
331
332     return &m_locals[localsIndex(entry.getIndex())];
333 }
334
335 RegisterID* CodeGenerator::registerForLocalConstInit(const Identifier& ident)
336 {
337     if (m_codeType == EvalCode)
338         return 0;
339
340     SymbolTableEntry entry = symbolTable().get(ident.ustring().rep());
341     ASSERT(!entry.isEmpty());
342
343     return &m_locals[localsIndex(entry.getIndex())];
344 }
345
346 bool CodeGenerator::isLocal(const Identifier& ident)
347 {
348     if (ident == m_propertyNames->thisIdentifier)
349         return true;
350     
351     return shouldOptimizeLocals() && symbolTable().contains(ident.ustring().rep());
352 }
353
354 bool CodeGenerator::isLocalConstant(const Identifier& ident)
355 {
356     return symbolTable().get(ident.ustring().rep()).isReadOnly();
357 }
358
359 RegisterID* CodeGenerator::newTemporary()
360 {
361     // Reclaim free register IDs.
362     while (m_temporaries.size() && !m_temporaries.last().refCount())
363         m_temporaries.removeLast();
364
365     // Allocate new register ID.
366     m_temporaries.append(m_temporaries.size());
367     m_codeBlock->numTemporaries = max<int>(m_codeBlock->numTemporaries, m_temporaries.size());
368     return &m_temporaries.last();
369 }
370
371
372 RegisterID* CodeGenerator::highestUsedRegister()
373 {
374     while (m_temporaries.size() < static_cast<unsigned>(m_codeBlock->numTemporaries))
375         m_temporaries.append(m_temporaries.size());
376     return &m_temporaries.last();
377 }
378
379 PassRefPtr<LabelID> CodeGenerator::newLabel()
380 {
381     // Reclaim free label IDs.
382     while (m_labels.size() && !m_labels.last().refCount())
383         m_labels.removeLast();
384
385     // Allocate new label ID.
386     m_labels.append(m_codeBlock);
387     return &m_labels.last();
388 }
389
390 PassRefPtr<LabelID> CodeGenerator::emitLabel(LabelID* l0)
391 {
392     l0->setLocation(instructions().size());
393     return l0;
394 }
395
396 void CodeGenerator::emitOpcode(OpcodeID opcodeID)
397 {
398     instructions().append(machine().getOpcode(opcodeID));
399     m_lastOpcodeID = opcodeID;
400 }
401
402 void CodeGenerator::retrieveLastBinaryOp(int& dstIndex, int& src1Index, int& src2Index)
403 {
404     ASSERT(instructions().size() >= 4);
405     size_t size = instructions().size();
406     dstIndex = instructions().at(size - 3).u.operand;
407     src1Index = instructions().at(size - 2).u.operand;
408     src2Index = instructions().at(size - 1).u.operand;
409 }
410
411 void CodeGenerator::rewindBinaryOp()
412 {
413     ASSERT(instructions().size() >= 4);
414     instructions().shrink(instructions().size() - 4);
415 }
416
417 PassRefPtr<LabelID> CodeGenerator::emitJump(LabelID* target)
418 {
419     emitOpcode(op_jmp);
420     instructions().append(target->offsetFrom(instructions().size()));
421     return target;
422 }
423
424 PassRefPtr<LabelID> CodeGenerator::emitJumpIfTrueMayCombine(RegisterID* cond, LabelID* target)
425 {
426     if (m_lastOpcodeID == op_less) {
427         int dstIndex;
428         int src1Index;
429         int src2Index;
430         
431         retrieveLastBinaryOp(dstIndex, src1Index, src2Index);
432         
433         if (cond->index() == dstIndex) {
434             rewindBinaryOp();
435             emitOpcode(op_jless);
436             instructions().append(src1Index);
437             instructions().append(src2Index);
438             instructions().append(target->offsetFrom(instructions().size()));
439             return target;
440         }
441     }
442     
443     return emitJumpIfTrue(cond, target);
444 }
445
446 PassRefPtr<LabelID> CodeGenerator::emitJumpIfTrue(RegisterID* cond, LabelID* target)
447 {
448     emitOpcode(op_jtrue);
449     instructions().append(cond->index());
450     instructions().append(target->offsetFrom(instructions().size()));
451     return target;
452 }
453
454 PassRefPtr<LabelID> CodeGenerator::emitJumpIfFalse(RegisterID* cond, LabelID* target)
455 {
456     emitOpcode(op_jfalse);
457     instructions().append(cond->index());
458     instructions().append(target->offsetFrom(instructions().size()));
459     return target;
460 }
461
462 unsigned CodeGenerator::addConstant(FuncDeclNode* n)
463 {
464     // No need to explicitly unique function body nodes -- they're unique already.
465     int index = m_codeBlock->functions.size();
466     m_codeBlock->functions.append(n);
467     return index;
468 }
469
470 unsigned CodeGenerator::addConstant(FuncExprNode* n)
471 {
472     // No need to explicitly unique function expression nodes -- they're unique already.
473     int index = m_codeBlock->functionExpressions.size();
474     m_codeBlock->functionExpressions.append(n);
475     return index;
476 }
477
478 unsigned CodeGenerator::addConstant(const Identifier& ident)
479 {
480     UString::Rep* rep = ident.ustring().rep();
481     pair<IdentifierMap::iterator, bool> result = m_identifierMap.add(rep, m_codeBlock->identifiers.size());
482     if (result.second) // new entry
483         m_codeBlock->identifiers.append(rep);
484
485     return result.first->second;
486 }
487
488 unsigned CodeGenerator::addConstant(JSValue* v)
489 {
490     pair<JSValueMap::iterator, bool> result = m_jsValueMap.add(v, m_codeBlock->jsValues.size());
491     if (result.second) // new entry
492         m_codeBlock->jsValues.append(v);
493
494     return result.first->second;
495 }
496
497 unsigned CodeGenerator::addRegExp(RegExp* r)
498 {
499     int index = m_codeBlock->regexps.size();
500     m_codeBlock->regexps.append(r);
501     return index;
502 }
503
504 RegisterID* CodeGenerator::emitMove(RegisterID* dst, RegisterID* src)
505 {
506     emitOpcode(op_mov);
507     instructions().append(dst->index());
508     instructions().append(src->index());
509     return dst;
510 }
511
512 RegisterID* CodeGenerator::emitNot(RegisterID* dst, RegisterID* src)
513 {
514     emitOpcode(op_not);
515     instructions().append(dst->index());
516     instructions().append(src->index());
517     return dst;
518 }
519
520 RegisterID* CodeGenerator::emitPreInc(RegisterID* srcDst)
521 {
522     emitOpcode(op_pre_inc);
523     instructions().append(srcDst->index());
524     return srcDst;
525 }
526
527 RegisterID* CodeGenerator::emitPreDec(RegisterID* srcDst)
528 {
529     emitOpcode(op_pre_dec);
530     instructions().append(srcDst->index());
531     return srcDst;
532 }
533
534 RegisterID* CodeGenerator::emitPostInc(RegisterID* dst, RegisterID* srcDst)
535 {
536     emitOpcode(op_post_inc);
537     instructions().append(dst->index());
538     instructions().append(srcDst->index());
539     return dst;
540 }
541
542 RegisterID* CodeGenerator::emitPostDec(RegisterID* dst, RegisterID* srcDst)
543 {
544     emitOpcode(op_post_dec);
545     instructions().append(dst->index());
546     instructions().append(srcDst->index());
547     return dst;
548 }
549
550 RegisterID* CodeGenerator::emitToJSNumber(RegisterID* dst, RegisterID* src)
551 {
552     emitOpcode(op_to_jsnumber);
553     instructions().append(dst->index());
554     instructions().append(src->index());
555     return dst;
556 }
557
558 RegisterID* CodeGenerator::emitNegate(RegisterID* dst, RegisterID* src)
559 {
560     emitOpcode(op_negate);
561     instructions().append(dst->index());
562     instructions().append(src->index());
563     return dst;
564 }
565
566 RegisterID* CodeGenerator::emitBitNot(RegisterID* dst, RegisterID* src)
567 {
568     emitOpcode(op_bitnot);
569     instructions().append(dst->index());
570     instructions().append(src->index());
571     return dst;
572 }
573
574 RegisterID* CodeGenerator::emitBinaryOp(OpcodeID opcode, RegisterID* dst, RegisterID* src1, RegisterID* src2)
575 {
576     emitOpcode(opcode);
577     instructions().append(dst->index());
578     instructions().append(src1->index());
579     instructions().append(src2->index());
580     return dst;
581 }
582
583 RegisterID* CodeGenerator::emitInstanceOf(RegisterID* dst, RegisterID* value, RegisterID* base)
584 {
585     emitOpcode(op_instanceof);
586     instructions().append(dst->index());
587     instructions().append(value->index());
588     instructions().append(base->index());
589     return dst;
590 }
591
592 RegisterID* CodeGenerator::emitTypeOf(RegisterID* dst, RegisterID* src)
593 {
594     emitOpcode(op_typeof);
595     instructions().append(dst->index());
596     instructions().append(src->index());
597     return dst;
598 }
599
600 RegisterID* CodeGenerator::emitIn(RegisterID* dst, RegisterID* property, RegisterID* base)
601 {
602     emitOpcode(op_in);
603     instructions().append(dst->index());
604     instructions().append(property->index());
605     instructions().append(base->index());
606     return dst;
607 }
608
609 RegisterID* CodeGenerator::emitLoad(RegisterID* dst, bool b)
610 {
611     emitOpcode(op_load);
612     instructions().append(dst->index());
613     instructions().append(addConstant(jsBoolean(b)));
614     return dst;
615 }
616
617 RegisterID* CodeGenerator::emitLoad(RegisterID* dst, double d)
618 {
619     emitOpcode(op_load);
620     instructions().append(dst->index());
621     instructions().append(addConstant(jsNumber(d)));
622     return dst;
623 }
624
625 RegisterID* CodeGenerator::emitLoad(RegisterID* dst, JSValue* v)
626 {
627     emitOpcode(op_load);
628     instructions().append(dst->index());
629     instructions().append(addConstant(v));
630     return dst;
631 }
632
633 RegisterID* CodeGenerator::emitNewObject(RegisterID* dst)
634 {
635     emitOpcode(op_new_object);
636     instructions().append(dst->index());
637     return dst;
638 }
639
640 RegisterID* CodeGenerator::emitNewArray(RegisterID* dst)
641 {
642     emitOpcode(op_new_array);
643     instructions().append(dst->index());
644     return dst;
645 }
646
647 bool CodeGenerator::findScopedProperty(const Identifier& property, int& index, size_t& stackDepth)
648 {
649     // Cases where we cannot optimise the lookup
650     if (property == m_propertyNames->arguments || !canOptimizeNonLocals()) {
651         stackDepth = 0;
652         index = missingSymbolMarker();
653         return false;
654     }
655
656     ScopeChainIterator iter = m_scopeChain->begin();
657     ScopeChainIterator end = m_scopeChain->end();
658     size_t depth = 0;
659
660     for (; iter != end; ++iter, ++depth) {
661         JSObject* currentScope = *iter;
662         if (!currentScope->isVariableObject())
663             break;
664         JSVariableObject* currentVariableObject = static_cast<JSVariableObject*>(currentScope);
665         SymbolTableEntry entry = currentVariableObject->symbolTable().get(property.ustring().rep());
666
667         // Found the property
668         if (!entry.isEmpty()) {
669             stackDepth = depth;
670             index = entry.getIndex();
671             return true;
672         }
673         if (currentVariableObject->isDynamicScope())
674             break;
675     }
676
677     // Can't locate the property but we're able to avoid a few lookups
678     stackDepth = depth;
679     index = missingSymbolMarker();
680     return true;
681 }
682
683 RegisterID* CodeGenerator::emitResolve(RegisterID* dst, const Identifier& property)
684 {
685     size_t depth = 0;
686     int index = 0;
687     if (!findScopedProperty(property, index, depth)) {
688         // We can't optimise at all :-(
689         emitOpcode(op_resolve);
690         instructions().append(dst->index());
691         instructions().append(addConstant(property));
692         return dst;
693     }
694
695     if (index == missingSymbolMarker()) {
696         // In this case we are at least able to drop a few scope chains from the
697         // lookup chain, although we still need to hash from then on.
698         emitOpcode(op_resolve_skip);
699         instructions().append(dst->index());
700         instructions().append(addConstant(property));
701         instructions().append(depth);
702         return dst;
703     }
704
705     // Directly index the property lookup across multiple scopes.  Yay!
706     return emitGetScopedVar(dst, depth, index);
707 }
708
709 RegisterID* CodeGenerator::emitGetScopedVar(RegisterID* dst, size_t depth, int index)
710 {
711     emitOpcode(op_get_scoped_var);
712     instructions().append(dst->index());
713     instructions().append(index);
714     instructions().append(depth);
715     return dst;
716 }
717
718 RegisterID* CodeGenerator::emitPutScopedVar(size_t depth, int index, RegisterID* value)
719 {
720     emitOpcode(op_put_scoped_var);
721     instructions().append(index);
722     instructions().append(depth);
723     instructions().append(value->index());
724     return value;
725 }
726
727 RegisterID* CodeGenerator::emitResolveBase(RegisterID* dst, const Identifier& property)
728 {
729     emitOpcode(op_resolve_base);
730     instructions().append(dst->index());
731     instructions().append(addConstant(property));
732     return dst;
733 }
734
735 RegisterID* CodeGenerator::emitResolveWithBase(RegisterID* baseDst, RegisterID* propDst, const Identifier& property)
736 {
737     emitOpcode(op_resolve_with_base);
738     instructions().append(baseDst->index());
739     instructions().append(propDst->index());
740     instructions().append(addConstant(property));
741     return baseDst;
742 }
743
744 RegisterID* CodeGenerator::emitResolveFunction(RegisterID* baseDst, RegisterID* funcDst, const Identifier& property)
745 {
746     emitOpcode(op_resolve_func);
747     instructions().append(baseDst->index());
748     instructions().append(funcDst->index());
749     instructions().append(addConstant(property));
750     return baseDst;
751 }
752
753 RegisterID* CodeGenerator::emitGetById(RegisterID* dst, RegisterID* base, const Identifier& property)
754 {
755     emitOpcode(op_get_by_id);
756     instructions().append(dst->index());
757     instructions().append(base->index());
758     instructions().append(addConstant(property));
759     return dst;
760 }
761
762 RegisterID* CodeGenerator::emitPutById(RegisterID* base, const Identifier& property, RegisterID* value)
763 {
764     emitOpcode(op_put_by_id);
765     instructions().append(base->index());
766     instructions().append(addConstant(property));
767     instructions().append(value->index());
768     return value;
769 }
770
771 RegisterID* CodeGenerator::emitPutGetter(RegisterID* base, const Identifier& property, RegisterID* value)
772 {
773     emitOpcode(op_put_getter);
774     instructions().append(base->index());
775     instructions().append(addConstant(property));
776     instructions().append(value->index());
777     return value;
778 }
779
780 RegisterID* CodeGenerator::emitPutSetter(RegisterID* base, const Identifier& property, RegisterID* value)
781 {
782     emitOpcode(op_put_setter);
783     instructions().append(base->index());
784     instructions().append(addConstant(property));
785     instructions().append(value->index());
786     return value;
787 }
788
789 RegisterID* CodeGenerator::emitDeleteById(RegisterID* dst, RegisterID* base, const Identifier& property)
790 {
791     emitOpcode(op_del_by_id);
792     instructions().append(dst->index());
793     instructions().append(base->index());
794     instructions().append(addConstant(property));
795     return dst;
796 }
797
798 RegisterID* CodeGenerator::emitGetByVal(RegisterID* dst, RegisterID* base, RegisterID* property)
799 {
800     emitOpcode(op_get_by_val);
801     instructions().append(dst->index());
802     instructions().append(base->index());
803     instructions().append(property->index());
804     return dst;
805 }
806
807 RegisterID* CodeGenerator::emitPutByVal(RegisterID* base, RegisterID* property, RegisterID* value)
808 {
809     emitOpcode(op_put_by_val);
810     instructions().append(base->index());
811     instructions().append(property->index());
812     instructions().append(value->index());
813     return value;
814 }
815
816 RegisterID* CodeGenerator::emitDeleteByVal(RegisterID* dst, RegisterID* base, RegisterID* property)
817 {
818     emitOpcode(op_del_by_val);
819     instructions().append(dst->index());
820     instructions().append(base->index());
821     instructions().append(property->index());
822     return dst;
823 }
824
825 RegisterID* CodeGenerator::emitPutByIndex(RegisterID* base, unsigned index, RegisterID* value)
826 {
827     emitOpcode(op_put_by_index);
828     instructions().append(base->index());
829     instructions().append(index);
830     instructions().append(value->index());
831     return value;
832 }
833
834 RegisterID* CodeGenerator::emitNewFunction(RegisterID* r0, FuncDeclNode* n)
835 {
836     emitOpcode(op_new_func);
837     instructions().append(r0->index());
838     instructions().append(addConstant(n));
839     return r0;
840 }
841
842 RegisterID* CodeGenerator::emitNewRegExp(RegisterID* dst, RegExp* regExp)
843 {
844     emitOpcode(op_new_regexp);
845     instructions().append(dst->index());
846     instructions().append(addRegExp(regExp));
847     return dst;
848 }
849
850
851 RegisterID* CodeGenerator::emitNewFunctionExpression(RegisterID* r0, FuncExprNode* n)
852 {
853     emitOpcode(op_new_func_exp);
854     instructions().append(r0->index());
855     instructions().append(addConstant(n));
856     return r0;
857 }
858
859 RegisterID* CodeGenerator::emitCall(RegisterID* dst, RegisterID* func, RegisterID* base, ArgumentsNode* argumentsNode)
860 {
861     return emitCall(op_call, dst, func, base, argumentsNode);
862 }
863
864 RegisterID* CodeGenerator::emitCallEval(RegisterID* dst, RegisterID* func, RegisterID* base, ArgumentsNode* argumentsNode)
865 {
866     return emitCall(op_call_eval, dst, func, base, argumentsNode);
867 }
868
869 RegisterID* CodeGenerator::emitCall(OpcodeID opcodeID, RegisterID* dst, RegisterID* func, RegisterID* base, ArgumentsNode* argumentsNode)
870 {
871     ASSERT(opcodeID == op_call || opcodeID == op_call_eval);
872
873     RefPtr<RegisterID> refFunc = func;
874     RefPtr<RegisterID> refBase = base;
875
876     // Reserve space for call frame.
877     Vector<RefPtr<RegisterID>, Machine::CallFrameHeaderSize> callFrame;
878     for (int i = 0; i < Machine::CallFrameHeaderSize; ++i)
879         callFrame.append(newTemporary());
880
881     // Generate code for arguments.
882     Vector<RefPtr<RegisterID>, 16> argv;
883     argv.append(newTemporary()); // reserve space for "this"
884     for (ArgumentListNode* n = argumentsNode->m_listNode.get(); n; n = n->m_next.get()) {
885         argv.append(newTemporary());
886         emitNode(argv.last().get(), n);
887     }
888
889     emitOpcode(opcodeID);
890     instructions().append(dst->index());
891     instructions().append(func->index());
892     instructions().append(base ? base->index() : missingThisObjectMarker()); // We encode the "this" value in the instruction stream, to avoid an explicit instruction for copying or loading it.
893     instructions().append(argv.size() ? argv[0]->index() : m_temporaries.size()); // argv
894     instructions().append(argv.size()); // argc
895     return dst;
896 }
897
898 RegisterID* CodeGenerator::emitReturn(RegisterID* r0)
899 {
900     emitOpcode(op_ret);
901     instructions().append(r0->index());
902     return r0;
903 }
904
905 RegisterID* CodeGenerator::emitEnd(RegisterID* dst)
906 {
907     emitOpcode(op_end);
908     instructions().append(dst->index());
909     return dst;
910 }
911
912 RegisterID* CodeGenerator::emitConstruct(RegisterID* dst, RegisterID* func, ArgumentsNode* argumentsNode)
913 {
914     // Reserve space for call frame.
915     Vector<RefPtr<RegisterID>, Machine::CallFrameHeaderSize> callFrame;
916     for (int i = 0; i < Machine::CallFrameHeaderSize; ++i)
917         callFrame.append(newTemporary());
918
919     // Generate code for arguments.
920     Vector<RefPtr<RegisterID>, 16> argv;
921     argv.append(newTemporary()); // reserve space for "this"
922     for (ArgumentListNode* n = argumentsNode ? argumentsNode->m_listNode.get() : 0; n; n = n->m_next.get()) {
923         argv.append(newTemporary());
924         emitNode(argv.last().get(), n);
925     }
926
927     emitOpcode(op_construct);
928     instructions().append(dst->index());
929     instructions().append(func->index());
930     instructions().append(argv.size() ? argv[0]->index() : m_temporaries.size()); // argv
931     instructions().append(argv.size()); // argc
932     return dst;
933 }
934
935 RegisterID* CodeGenerator::emitPushScope(RegisterID* scope)
936 {
937     m_codeBlock->needsFullScopeChain = true;
938     emitOpcode(op_push_scope);
939     instructions().append(scope->index());
940
941     ControlFlowContext context;
942     context.isFinallyBlock = false;
943     m_scopeContextStack.append(context);
944     m_dynamicScopeDepth++;
945     return scope;
946 }
947
948 void CodeGenerator::emitPopScope()
949 {
950     ASSERT(m_scopeContextStack.size());
951     ASSERT(!m_scopeContextStack.last().isFinallyBlock);
952
953     emitOpcode(op_pop_scope);
954
955     m_scopeContextStack.removeLast();
956     m_dynamicScopeDepth--;
957 }
958
959 void CodeGenerator::emitDebugHook(DebugHookID debugHookID, int firstLine, int lastLine)
960 {
961     if (!m_shouldEmitDebugHooks)
962         return;
963     emitOpcode(op_debug);
964     instructions().append(debugHookID);
965     instructions().append(firstLine);
966     instructions().append(lastLine);
967 }
968
969 void CodeGenerator::pushFinallyContext(LabelID* target, RegisterID* retAddrDst)
970 {
971     ControlFlowContext scope;
972     scope.isFinallyBlock = true;
973     FinallyContext context = { target, retAddrDst };
974     scope.finallyContext = context;
975     m_scopeContextStack.append(scope);
976     m_finallyDepth++;
977 }
978
979 void CodeGenerator::popFinallyContext()
980 {
981     ASSERT(m_scopeContextStack.size());
982     ASSERT(m_scopeContextStack.last().isFinallyBlock);
983     ASSERT(m_finallyDepth > 0);
984     m_scopeContextStack.removeLast();
985     m_finallyDepth--;
986 }
987
988 void CodeGenerator::pushJumpContext(LabelStack* labels, LabelID* continueTarget, LabelID* breakTarget, bool isValidUnlabeledBreakTarget)
989 {
990     JumpContext context = { labels, continueTarget, breakTarget, scopeDepth(), isValidUnlabeledBreakTarget };
991     m_jumpContextStack.append(context);
992     if (continueTarget)
993         m_continueDepth++;
994 }
995
996 void CodeGenerator::popJumpContext()
997 {
998     ASSERT(m_jumpContextStack.size());
999     if (m_jumpContextStack.last().continueTarget)
1000         m_continueDepth--;
1001     m_jumpContextStack.removeLast();
1002 }
1003
1004 JumpContext* CodeGenerator::jumpContextForContinue(const Identifier& label)
1005 {
1006     if(!m_jumpContextStack.size())
1007         return 0;
1008
1009     if (label.isEmpty()) {
1010         for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
1011             JumpContext* scope = &m_jumpContextStack[i];
1012             if (scope->continueTarget)
1013                 return scope;
1014         }
1015         return 0;
1016     }
1017
1018     for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
1019         JumpContext* scope = &m_jumpContextStack[i];
1020         if (scope->labels->contains(label))
1021             return scope;
1022     }
1023     return 0;
1024 }
1025
1026 JumpContext* CodeGenerator::jumpContextForBreak(const Identifier& label)
1027 {
1028     if(!m_jumpContextStack.size())
1029         return 0;
1030
1031     if (label.isEmpty()) {
1032         for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
1033             JumpContext* scope = &m_jumpContextStack[i];
1034             if (scope->isValidUnlabeledBreakTarget)
1035                 return scope;
1036         }
1037         return 0;
1038     }
1039
1040     for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
1041         JumpContext* scope = &m_jumpContextStack[i];
1042         if (scope->labels->contains(label))
1043             return scope;
1044     }
1045     return 0;
1046 }
1047
1048 PassRefPtr<LabelID> CodeGenerator::emitComplexJumpScopes(LabelID* target, ControlFlowContext* topScope, ControlFlowContext* bottomScope)
1049 {
1050     while (topScope > bottomScope) {
1051         // First we count the number of dynamic scopes we need to remove to get
1052         // to a finally block.
1053         int nNormalScopes = 0;
1054         while (topScope > bottomScope) {
1055             if (topScope->isFinallyBlock)
1056                 break;
1057             ++nNormalScopes;
1058             --topScope;
1059         }
1060
1061         if (nNormalScopes) {
1062             // We need to remove a number of dynamic scopes to get to the next
1063             // finally block
1064             emitOpcode(op_jmp_scopes);
1065             instructions().append(nNormalScopes);
1066
1067             // If topScope == bottomScope then there isn't actually a finally block
1068             // left to emit, so make the jmp_scopes jump directly to the target label
1069             if (topScope == bottomScope) {
1070                 instructions().append(target->offsetFrom(instructions().size()));
1071                 return target;
1072             }
1073
1074             // Otherwise we just use jmp_scopes to pop a group of scopes and go
1075             // to the next instruction
1076             RefPtr<LabelID> nextInsn = newLabel();
1077             instructions().append(nextInsn->offsetFrom(instructions().size()));
1078             emitLabel(nextInsn.get());
1079         }
1080
1081         // To get here there must be at least one finally block present
1082         do {
1083             ASSERT(topScope->isFinallyBlock);
1084             emitJumpSubroutine(topScope->finallyContext.retAddrDst, topScope->finallyContext.finallyAddr);
1085             --topScope;
1086             if (!topScope->isFinallyBlock)
1087                 break;
1088         } while (topScope > bottomScope);
1089     }
1090     return emitJump(target);
1091 }
1092
1093 PassRefPtr<LabelID> CodeGenerator::emitJumpScopes(LabelID* target, int targetScopeDepth)
1094 {
1095     ASSERT(scopeDepth() - targetScopeDepth >= 0);
1096
1097     size_t scopeDelta = scopeDepth() - targetScopeDepth;
1098     ASSERT(scopeDelta <= m_scopeContextStack.size());
1099     if (!scopeDelta)
1100         return emitJump(target);
1101
1102     if (m_finallyDepth)
1103         return emitComplexJumpScopes(target, &m_scopeContextStack.last(), &m_scopeContextStack.last() - scopeDelta);
1104
1105     emitOpcode(op_jmp_scopes);
1106     instructions().append(scopeDelta);
1107     instructions().append(target->offsetFrom(instructions().size()));
1108     return target;
1109 }
1110
1111 RegisterID* CodeGenerator::emitNextPropertyName(RegisterID* dst, RegisterID* iter, LabelID* target)
1112 {
1113     emitOpcode(op_next_pname);
1114     instructions().append(dst->index());
1115     instructions().append(iter->index());
1116     instructions().append(target->offsetFrom(instructions().size()));
1117     return dst;
1118 }
1119
1120 RegisterID* CodeGenerator::emitGetPropertyNames(RegisterID* dst, RegisterID* base)
1121 {
1122     emitOpcode(op_get_pnames);
1123     instructions().append(dst->index());
1124     instructions().append(base->index());
1125     return dst;
1126 }
1127
1128 RegisterID* CodeGenerator::emitCatch(RegisterID* targetRegister, LabelID* start, LabelID* end)
1129 {
1130     HandlerInfo info = { start->offsetFrom(0), end->offsetFrom(0), instructions().size(), m_dynamicScopeDepth };
1131     exceptionHandlers().append(info);
1132     emitOpcode(op_catch);
1133     instructions().append(targetRegister->index());
1134     return targetRegister;
1135 }
1136
1137 void CodeGenerator::emitThrow(RegisterID* exception)
1138 {
1139     emitOpcode(op_throw);
1140     instructions().append(exception->index());
1141 }
1142
1143 RegisterID* CodeGenerator::emitNewError(RegisterID* dst, ErrorType type, JSValue* message)
1144 {
1145     emitOpcode(op_new_error);
1146     instructions().append(dst->index());
1147     instructions().append(static_cast<int>(type));
1148     instructions().append(addConstant(message));
1149     return dst;
1150 }
1151
1152 PassRefPtr<LabelID> CodeGenerator::emitJumpSubroutine(RegisterID* retAddrDst, LabelID* finally)
1153 {
1154     emitOpcode(op_jsr);
1155     instructions().append(retAddrDst->index());
1156     instructions().append(finally->offsetFrom(instructions().size()));
1157     return finally;
1158 }
1159
1160 void CodeGenerator::emitSubroutineReturn(RegisterID* retAddrSrc)
1161 {
1162     emitOpcode(op_sret);
1163     instructions().append(retAddrSrc->index());
1164 }
1165
1166 } // namespace KJS