2008-06-24 Cameron Zwarich <cwzwarich@uwaterloo.ca>
[WebKit-https.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 "JSFunction.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_globalData(&scopeChain.globalObject()->globalExec()->globalData())
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_globalData(&scopeChain.globalObject()->globalExec()->globalData())
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 == 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_globalData(&scopeChain.globalObject()->globalExec()->globalData())
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 == propertyNames().arguments)
320         m_codeBlock->needsFullScopeChain = true;
321
322     if (ident == 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.isNull())
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.isNull());
342
343     return &m_locals[localsIndex(entry.getIndex())];
344 }
345
346 bool CodeGenerator::isLocal(const Identifier& ident)
347 {
348     if (ident == 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     
394     // This disables peephole optimizations when an instruction is a jump target
395     m_lastOpcodeID = op_end;
396     
397     return l0;
398 }
399
400 void CodeGenerator::emitOpcode(OpcodeID opcodeID)
401 {
402     instructions().append(globalData()->machine->getOpcode(opcodeID));
403     m_lastOpcodeID = opcodeID;
404 }
405
406 void CodeGenerator::retrieveLastBinaryOp(int& dstIndex, int& src1Index, int& src2Index)
407 {
408     ASSERT(instructions().size() >= 4);
409     size_t size = instructions().size();
410     dstIndex = instructions().at(size - 3).u.operand;
411     src1Index = instructions().at(size - 2).u.operand;
412     src2Index = instructions().at(size - 1).u.operand;
413 }
414
415 void CodeGenerator::rewindBinaryOp()
416 {
417     ASSERT(instructions().size() >= 4);
418     instructions().shrink(instructions().size() - 4);
419 }
420
421 PassRefPtr<LabelID> CodeGenerator::emitJump(LabelID* target)
422 {
423     emitOpcode(op_jmp);
424     instructions().append(target->offsetFrom(instructions().size()));
425     return target;
426 }
427
428 PassRefPtr<LabelID> CodeGenerator::emitJumpIfTrue(RegisterID* cond, LabelID* target)
429 {
430     if (m_lastOpcodeID == op_less) {
431         int dstIndex;
432         int src1Index;
433         int src2Index;
434         
435         retrieveLastBinaryOp(dstIndex, src1Index, src2Index);
436         
437         if (cond->index() == dstIndex && !cond->refCount()) {
438             rewindBinaryOp();
439             emitOpcode(op_jless);
440             instructions().append(src1Index);
441             instructions().append(src2Index);
442             instructions().append(target->offsetFrom(instructions().size()));
443             return target;
444         }
445     }
446     
447     emitOpcode(op_jtrue);
448     instructions().append(cond->index());
449     instructions().append(target->offsetFrom(instructions().size()));
450     return target;
451 }
452
453 PassRefPtr<LabelID> CodeGenerator::emitJumpIfFalse(RegisterID* cond, LabelID* target)
454 {
455     emitOpcode(op_jfalse);
456     instructions().append(cond->index());
457     instructions().append(target->offsetFrom(instructions().size()));
458     return target;
459 }
460
461 unsigned CodeGenerator::addConstant(FuncDeclNode* n)
462 {
463     // No need to explicitly unique function body nodes -- they're unique already.
464     int index = m_codeBlock->functions.size();
465     m_codeBlock->functions.append(n);
466     return index;
467 }
468
469 unsigned CodeGenerator::addConstant(FuncExprNode* n)
470 {
471     // No need to explicitly unique function expression nodes -- they're unique already.
472     int index = m_codeBlock->functionExpressions.size();
473     m_codeBlock->functionExpressions.append(n);
474     return index;
475 }
476
477 unsigned CodeGenerator::addConstant(const Identifier& ident)
478 {
479     UString::Rep* rep = ident.ustring().rep();
480     pair<IdentifierMap::iterator, bool> result = m_identifierMap.add(rep, m_codeBlock->identifiers.size());
481     if (result.second) // new entry
482         m_codeBlock->identifiers.append(Identifier(m_globalData, rep));
483
484     return result.first->second;
485 }
486
487 unsigned CodeGenerator::addConstant(JSValue* v)
488 {
489     pair<JSValueMap::iterator, bool> result = m_jsValueMap.add(v, m_codeBlock->jsValues.size());
490     if (result.second) // new entry
491         m_codeBlock->jsValues.append(v);
492
493     return result.first->second;
494 }
495
496 unsigned CodeGenerator::addRegExp(RegExp* r)
497 {
498     int index = m_codeBlock->regexps.size();
499     m_codeBlock->regexps.append(r);
500     return index;
501 }
502
503 RegisterID* CodeGenerator::emitMove(RegisterID* dst, RegisterID* src)
504 {
505     emitOpcode(op_mov);
506     instructions().append(dst->index());
507     instructions().append(src->index());
508     return dst;
509 }
510
511 RegisterID* CodeGenerator::emitUnaryOp(OpcodeID opcode, RegisterID* dst, RegisterID* src)
512 {
513     emitOpcode(opcode);
514     instructions().append(dst->index());
515     instructions().append(src->index());
516     return dst;
517 }
518
519 RegisterID* CodeGenerator::emitPreInc(RegisterID* srcDst)
520 {
521     emitOpcode(op_pre_inc);
522     instructions().append(srcDst->index());
523     return srcDst;
524 }
525
526 RegisterID* CodeGenerator::emitPreDec(RegisterID* srcDst)
527 {
528     emitOpcode(op_pre_dec);
529     instructions().append(srcDst->index());
530     return srcDst;
531 }
532
533 RegisterID* CodeGenerator::emitPostInc(RegisterID* dst, RegisterID* srcDst)
534 {
535     emitOpcode(op_post_inc);
536     instructions().append(dst->index());
537     instructions().append(srcDst->index());
538     return dst;
539 }
540
541 RegisterID* CodeGenerator::emitPostDec(RegisterID* dst, RegisterID* srcDst)
542 {
543     emitOpcode(op_post_dec);
544     instructions().append(dst->index());
545     instructions().append(srcDst->index());
546     return dst;
547 }
548
549 RegisterID* CodeGenerator::emitBinaryOp(OpcodeID opcode, RegisterID* dst, RegisterID* src1, RegisterID* src2)
550 {
551     emitOpcode(opcode);
552     instructions().append(dst->index());
553     instructions().append(src1->index());
554     instructions().append(src2->index());
555     return dst;
556 }
557
558 RegisterID* CodeGenerator::emitLoad(RegisterID* dst, bool b)
559 {
560     emitOpcode(op_load);
561     instructions().append(dst->index());
562     instructions().append(addConstant(jsBoolean(b)));
563     return dst;
564 }
565
566 RegisterID* CodeGenerator::emitLoad(RegisterID* dst, double d)
567 {
568     emitOpcode(op_load);
569     instructions().append(dst->index());
570     instructions().append(addConstant(jsNumber(globalExec(), d)));
571     return dst;
572 }
573
574 RegisterID* CodeGenerator::emitLoad(RegisterID* dst, JSValue* v)
575 {
576     emitOpcode(op_load);
577     instructions().append(dst->index());
578     instructions().append(addConstant(v));
579     return dst;
580 }
581
582 RegisterID* CodeGenerator::emitNullaryOp(OpcodeID opcode, RegisterID* dst)
583 {
584     emitOpcode(opcode);
585     instructions().append(dst->index());
586     return dst;
587 }
588
589 bool CodeGenerator::findScopedProperty(const Identifier& property, int& index, size_t& stackDepth)
590 {
591     // Cases where we cannot optimise the lookup
592     if (property == propertyNames().arguments || !canOptimizeNonLocals()) {
593         stackDepth = 0;
594         index = missingSymbolMarker();
595         return false;
596     }
597
598     ScopeChainIterator iter = m_scopeChain->begin();
599     ScopeChainIterator end = m_scopeChain->end();
600     size_t depth = 0;
601
602     for (; iter != end; ++iter, ++depth) {
603         JSObject* currentScope = *iter;
604         if (!currentScope->isVariableObject())
605             break;
606         JSVariableObject* currentVariableObject = static_cast<JSVariableObject*>(currentScope);
607         SymbolTableEntry entry = currentVariableObject->symbolTable().get(property.ustring().rep());
608
609         // Found the property
610         if (!entry.isNull()) {
611             stackDepth = depth;
612             index = entry.getIndex();
613             return true;
614         }
615         if (currentVariableObject->isDynamicScope())
616             break;
617     }
618
619     // Can't locate the property but we're able to avoid a few lookups
620     stackDepth = depth;
621     index = missingSymbolMarker();
622     return true;
623 }
624
625 RegisterID* CodeGenerator::emitResolve(RegisterID* dst, const Identifier& property)
626 {
627     size_t depth = 0;
628     int index = 0;
629     if (!findScopedProperty(property, index, depth)) {
630         // We can't optimise at all :-(
631         emitOpcode(op_resolve);
632         instructions().append(dst->index());
633         instructions().append(addConstant(property));
634         return dst;
635     }
636
637     if (index == missingSymbolMarker()) {
638         // In this case we are at least able to drop a few scope chains from the
639         // lookup chain, although we still need to hash from then on.
640         emitOpcode(op_resolve_skip);
641         instructions().append(dst->index());
642         instructions().append(addConstant(property));
643         instructions().append(depth);
644         return dst;
645     }
646
647     // Directly index the property lookup across multiple scopes.  Yay!
648     return emitGetScopedVar(dst, depth, index);
649 }
650
651 RegisterID* CodeGenerator::emitGetScopedVar(RegisterID* dst, size_t depth, int index)
652 {
653     emitOpcode(op_get_scoped_var);
654     instructions().append(dst->index());
655     instructions().append(index);
656     instructions().append(depth);
657     return dst;
658 }
659
660 RegisterID* CodeGenerator::emitPutScopedVar(size_t depth, int index, RegisterID* value)
661 {
662     emitOpcode(op_put_scoped_var);
663     instructions().append(index);
664     instructions().append(depth);
665     instructions().append(value->index());
666     return value;
667 }
668
669 RegisterID* CodeGenerator::emitResolveBase(RegisterID* dst, const Identifier& property)
670 {
671     emitOpcode(op_resolve_base);
672     instructions().append(dst->index());
673     instructions().append(addConstant(property));
674     return dst;
675 }
676
677 RegisterID* CodeGenerator::emitResolveWithBase(RegisterID* baseDst, RegisterID* propDst, const Identifier& property)
678 {
679     emitOpcode(op_resolve_with_base);
680     instructions().append(baseDst->index());
681     instructions().append(propDst->index());
682     instructions().append(addConstant(property));
683     return baseDst;
684 }
685
686 RegisterID* CodeGenerator::emitResolveFunction(RegisterID* baseDst, RegisterID* funcDst, const Identifier& property)
687 {
688     emitOpcode(op_resolve_func);
689     instructions().append(baseDst->index());
690     instructions().append(funcDst->index());
691     instructions().append(addConstant(property));
692     return baseDst;
693 }
694
695 RegisterID* CodeGenerator::emitGetById(RegisterID* dst, RegisterID* base, const Identifier& property)
696 {
697     emitOpcode(op_get_by_id);
698     instructions().append(dst->index());
699     instructions().append(base->index());
700     instructions().append(addConstant(property));
701     return dst;
702 }
703
704 RegisterID* CodeGenerator::emitPutById(RegisterID* base, const Identifier& property, RegisterID* value)
705 {
706     emitOpcode(op_put_by_id);
707     instructions().append(base->index());
708     instructions().append(addConstant(property));
709     instructions().append(value->index());
710     return value;
711 }
712
713 RegisterID* CodeGenerator::emitPutGetter(RegisterID* base, const Identifier& property, RegisterID* value)
714 {
715     emitOpcode(op_put_getter);
716     instructions().append(base->index());
717     instructions().append(addConstant(property));
718     instructions().append(value->index());
719     return value;
720 }
721
722 RegisterID* CodeGenerator::emitPutSetter(RegisterID* base, const Identifier& property, RegisterID* value)
723 {
724     emitOpcode(op_put_setter);
725     instructions().append(base->index());
726     instructions().append(addConstant(property));
727     instructions().append(value->index());
728     return value;
729 }
730
731 RegisterID* CodeGenerator::emitDeleteById(RegisterID* dst, RegisterID* base, const Identifier& property)
732 {
733     emitOpcode(op_del_by_id);
734     instructions().append(dst->index());
735     instructions().append(base->index());
736     instructions().append(addConstant(property));
737     return dst;
738 }
739
740 RegisterID* CodeGenerator::emitGetByVal(RegisterID* dst, RegisterID* base, RegisterID* property)
741 {
742     emitOpcode(op_get_by_val);
743     instructions().append(dst->index());
744     instructions().append(base->index());
745     instructions().append(property->index());
746     return dst;
747 }
748
749 RegisterID* CodeGenerator::emitPutByVal(RegisterID* base, RegisterID* property, RegisterID* value)
750 {
751     emitOpcode(op_put_by_val);
752     instructions().append(base->index());
753     instructions().append(property->index());
754     instructions().append(value->index());
755     return value;
756 }
757
758 RegisterID* CodeGenerator::emitDeleteByVal(RegisterID* dst, RegisterID* base, RegisterID* property)
759 {
760     emitOpcode(op_del_by_val);
761     instructions().append(dst->index());
762     instructions().append(base->index());
763     instructions().append(property->index());
764     return dst;
765 }
766
767 RegisterID* CodeGenerator::emitPutByIndex(RegisterID* base, unsigned index, RegisterID* value)
768 {
769     emitOpcode(op_put_by_index);
770     instructions().append(base->index());
771     instructions().append(index);
772     instructions().append(value->index());
773     return value;
774 }
775
776 RegisterID* CodeGenerator::emitNewFunction(RegisterID* r0, FuncDeclNode* n)
777 {
778     emitOpcode(op_new_func);
779     instructions().append(r0->index());
780     instructions().append(addConstant(n));
781     return r0;
782 }
783
784 RegisterID* CodeGenerator::emitNewRegExp(RegisterID* dst, RegExp* regExp)
785 {
786     emitOpcode(op_new_regexp);
787     instructions().append(dst->index());
788     instructions().append(addRegExp(regExp));
789     return dst;
790 }
791
792
793 RegisterID* CodeGenerator::emitNewFunctionExpression(RegisterID* r0, FuncExprNode* n)
794 {
795     emitOpcode(op_new_func_exp);
796     instructions().append(r0->index());
797     instructions().append(addConstant(n));
798     return r0;
799 }
800
801 RegisterID* CodeGenerator::emitCall(RegisterID* dst, RegisterID* func, RegisterID* base, ArgumentsNode* argumentsNode)
802 {
803     return emitCall(op_call, dst, func, base, argumentsNode);
804 }
805
806 RegisterID* CodeGenerator::emitCallEval(RegisterID* dst, RegisterID* func, RegisterID* base, ArgumentsNode* argumentsNode)
807 {
808     return emitCall(op_call_eval, dst, func, base, argumentsNode);
809 }
810
811 RegisterID* CodeGenerator::emitCall(OpcodeID opcodeID, RegisterID* dst, RegisterID* func, RegisterID* base, ArgumentsNode* argumentsNode)
812 {
813     ASSERT(opcodeID == op_call || opcodeID == op_call_eval);
814
815     RefPtr<RegisterID> refFunc = func;
816     RefPtr<RegisterID> refBase = base;
817
818     // Reserve space for call frame.
819     Vector<RefPtr<RegisterID>, Machine::CallFrameHeaderSize> callFrame;
820     for (int i = 0; i < Machine::CallFrameHeaderSize; ++i)
821         callFrame.append(newTemporary());
822
823     // Generate code for arguments.
824     Vector<RefPtr<RegisterID>, 16> argv;
825     argv.append(newTemporary()); // reserve space for "this"
826     for (ArgumentListNode* n = argumentsNode->m_listNode.get(); n; n = n->m_next.get()) {
827         argv.append(newTemporary());
828         emitNode(argv.last().get(), n);
829     }
830
831     emitOpcode(opcodeID);
832     instructions().append(dst->index());
833     instructions().append(func->index());
834     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.
835     instructions().append(argv.size() ? argv[0]->index() : m_temporaries.size()); // argv
836     instructions().append(argv.size()); // argc
837     return dst;
838 }
839
840 RegisterID* CodeGenerator::emitUnaryNoDstOp(OpcodeID opcode, RegisterID* src)
841 {
842     emitOpcode(opcode);
843     instructions().append(src->index());
844     return src;
845 }
846
847 RegisterID* CodeGenerator::emitConstruct(RegisterID* dst, RegisterID* func, ArgumentsNode* argumentsNode)
848 {
849     // Reserve space for call frame.
850     Vector<RefPtr<RegisterID>, Machine::CallFrameHeaderSize> callFrame;
851     for (int i = 0; i < Machine::CallFrameHeaderSize; ++i)
852         callFrame.append(newTemporary());
853
854     // Generate code for arguments.
855     Vector<RefPtr<RegisterID>, 16> argv;
856     argv.append(newTemporary()); // reserve space for "this"
857     for (ArgumentListNode* n = argumentsNode ? argumentsNode->m_listNode.get() : 0; n; n = n->m_next.get()) {
858         argv.append(newTemporary());
859         emitNode(argv.last().get(), n);
860     }
861
862     emitOpcode(op_construct);
863     instructions().append(dst->index());
864     instructions().append(func->index());
865     instructions().append(argv.size() ? argv[0]->index() : m_temporaries.size()); // argv
866     instructions().append(argv.size()); // argc
867     return dst;
868 }
869
870 RegisterID* CodeGenerator::emitPushScope(RegisterID* scope)
871 {
872     m_codeBlock->needsFullScopeChain = true;
873     ControlFlowContext context;
874     context.isFinallyBlock = false;
875     m_scopeContextStack.append(context);
876     m_dynamicScopeDepth++;
877
878     return emitUnaryNoDstOp(op_push_scope, scope);
879 }
880
881 void CodeGenerator::emitPopScope()
882 {
883     ASSERT(m_scopeContextStack.size());
884     ASSERT(!m_scopeContextStack.last().isFinallyBlock);
885
886     emitOpcode(op_pop_scope);
887
888     m_scopeContextStack.removeLast();
889     m_dynamicScopeDepth--;
890 }
891
892 void CodeGenerator::emitDebugHook(DebugHookID debugHookID, int firstLine, int lastLine)
893 {
894     if (!m_shouldEmitDebugHooks)
895         return;
896     emitOpcode(op_debug);
897     instructions().append(debugHookID);
898     instructions().append(firstLine);
899     instructions().append(lastLine);
900 }
901
902 void CodeGenerator::pushFinallyContext(LabelID* target, RegisterID* retAddrDst)
903 {
904     ControlFlowContext scope;
905     scope.isFinallyBlock = true;
906     FinallyContext context = { target, retAddrDst };
907     scope.finallyContext = context;
908     m_scopeContextStack.append(scope);
909     m_finallyDepth++;
910 }
911
912 void CodeGenerator::popFinallyContext()
913 {
914     ASSERT(m_scopeContextStack.size());
915     ASSERT(m_scopeContextStack.last().isFinallyBlock);
916     ASSERT(m_finallyDepth > 0);
917     m_scopeContextStack.removeLast();
918     m_finallyDepth--;
919 }
920
921 void CodeGenerator::pushJumpContext(LabelStack* labels, LabelID* continueTarget, LabelID* breakTarget, bool isValidUnlabeledBreakTarget)
922 {
923     JumpContext context = { labels, continueTarget, breakTarget, scopeDepth(), isValidUnlabeledBreakTarget };
924     m_jumpContextStack.append(context);
925     if (continueTarget)
926         m_continueDepth++;
927 }
928
929 void CodeGenerator::popJumpContext()
930 {
931     ASSERT(m_jumpContextStack.size());
932     if (m_jumpContextStack.last().continueTarget)
933         m_continueDepth--;
934     m_jumpContextStack.removeLast();
935 }
936
937 JumpContext* CodeGenerator::jumpContextForContinue(const Identifier& label)
938 {
939     if(!m_jumpContextStack.size())
940         return 0;
941
942     if (label.isEmpty()) {
943         for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
944             JumpContext* scope = &m_jumpContextStack[i];
945             if (scope->continueTarget)
946                 return scope;
947         }
948         return 0;
949     }
950
951     for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
952         JumpContext* scope = &m_jumpContextStack[i];
953         if (scope->labels->contains(label))
954             return scope;
955     }
956     return 0;
957 }
958
959 JumpContext* CodeGenerator::jumpContextForBreak(const Identifier& label)
960 {
961     if(!m_jumpContextStack.size())
962         return 0;
963
964     if (label.isEmpty()) {
965         for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
966             JumpContext* scope = &m_jumpContextStack[i];
967             if (scope->isValidUnlabeledBreakTarget)
968                 return scope;
969         }
970         return 0;
971     }
972
973     for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
974         JumpContext* scope = &m_jumpContextStack[i];
975         if (scope->labels->contains(label))
976             return scope;
977     }
978     return 0;
979 }
980
981 PassRefPtr<LabelID> CodeGenerator::emitComplexJumpScopes(LabelID* target, ControlFlowContext* topScope, ControlFlowContext* bottomScope)
982 {
983     while (topScope > bottomScope) {
984         // First we count the number of dynamic scopes we need to remove to get
985         // to a finally block.
986         int nNormalScopes = 0;
987         while (topScope > bottomScope) {
988             if (topScope->isFinallyBlock)
989                 break;
990             ++nNormalScopes;
991             --topScope;
992         }
993
994         if (nNormalScopes) {
995             // We need to remove a number of dynamic scopes to get to the next
996             // finally block
997             emitOpcode(op_jmp_scopes);
998             instructions().append(nNormalScopes);
999
1000             // If topScope == bottomScope then there isn't actually a finally block
1001             // left to emit, so make the jmp_scopes jump directly to the target label
1002             if (topScope == bottomScope) {
1003                 instructions().append(target->offsetFrom(instructions().size()));
1004                 return target;
1005             }
1006
1007             // Otherwise we just use jmp_scopes to pop a group of scopes and go
1008             // to the next instruction
1009             RefPtr<LabelID> nextInsn = newLabel();
1010             instructions().append(nextInsn->offsetFrom(instructions().size()));
1011             emitLabel(nextInsn.get());
1012         }
1013
1014         // To get here there must be at least one finally block present
1015         do {
1016             ASSERT(topScope->isFinallyBlock);
1017             emitJumpSubroutine(topScope->finallyContext.retAddrDst, topScope->finallyContext.finallyAddr);
1018             --topScope;
1019             if (!topScope->isFinallyBlock)
1020                 break;
1021         } while (topScope > bottomScope);
1022     }
1023     return emitJump(target);
1024 }
1025
1026 PassRefPtr<LabelID> CodeGenerator::emitJumpScopes(LabelID* target, int targetScopeDepth)
1027 {
1028     ASSERT(scopeDepth() - targetScopeDepth >= 0);
1029
1030     size_t scopeDelta = scopeDepth() - targetScopeDepth;
1031     ASSERT(scopeDelta <= m_scopeContextStack.size());
1032     if (!scopeDelta)
1033         return emitJump(target);
1034
1035     if (m_finallyDepth)
1036         return emitComplexJumpScopes(target, &m_scopeContextStack.last(), &m_scopeContextStack.last() - scopeDelta);
1037
1038     emitOpcode(op_jmp_scopes);
1039     instructions().append(scopeDelta);
1040     instructions().append(target->offsetFrom(instructions().size()));
1041     return target;
1042 }
1043
1044 RegisterID* CodeGenerator::emitNextPropertyName(RegisterID* dst, RegisterID* iter, LabelID* target)
1045 {
1046     emitOpcode(op_next_pname);
1047     instructions().append(dst->index());
1048     instructions().append(iter->index());
1049     instructions().append(target->offsetFrom(instructions().size()));
1050     return dst;
1051 }
1052
1053 RegisterID* CodeGenerator::emitCatch(RegisterID* targetRegister, LabelID* start, LabelID* end)
1054 {
1055     HandlerInfo info = { start->offsetFrom(0), end->offsetFrom(0), instructions().size(), m_dynamicScopeDepth };
1056     exceptionHandlers().append(info);
1057     emitOpcode(op_catch);
1058     instructions().append(targetRegister->index());
1059     return targetRegister;
1060 }
1061
1062 RegisterID* CodeGenerator::emitNewError(RegisterID* dst, ErrorType type, JSValue* message)
1063 {
1064     emitOpcode(op_new_error);
1065     instructions().append(dst->index());
1066     instructions().append(static_cast<int>(type));
1067     instructions().append(addConstant(message));
1068     return dst;
1069 }
1070
1071 PassRefPtr<LabelID> CodeGenerator::emitJumpSubroutine(RegisterID* retAddrDst, LabelID* finally)
1072 {
1073     emitOpcode(op_jsr);
1074     instructions().append(retAddrDst->index());
1075     instructions().append(finally->offsetFrom(instructions().size()));
1076     return finally;
1077 }
1078
1079 void CodeGenerator::emitSubroutineReturn(RegisterID* retAddrSrc)
1080 {
1081     emitOpcode(op_sret);
1082     instructions().append(retAddrSrc->index());
1083 }
1084
1085 } // namespace KJS