2008-06-15 Maciej Stachowiak <mjs@apple.com>
[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::emitUnaryOp(OpcodeID opcode, RegisterID* dst, RegisterID* src)
513 {
514     emitOpcode(opcode);
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::emitBinaryOp(OpcodeID opcode, RegisterID* dst, RegisterID* src1, RegisterID* src2)
551 {
552     emitOpcode(opcode);
553     instructions().append(dst->index());
554     instructions().append(src1->index());
555     instructions().append(src2->index());
556     return dst;
557 }
558
559 RegisterID* CodeGenerator::emitLoad(RegisterID* dst, bool b)
560 {
561     emitOpcode(op_load);
562     instructions().append(dst->index());
563     instructions().append(addConstant(jsBoolean(b)));
564     return dst;
565 }
566
567 RegisterID* CodeGenerator::emitLoad(RegisterID* dst, double d)
568 {
569     emitOpcode(op_load);
570     instructions().append(dst->index());
571     instructions().append(addConstant(jsNumber(d)));
572     return dst;
573 }
574
575 RegisterID* CodeGenerator::emitLoad(RegisterID* dst, JSValue* v)
576 {
577     emitOpcode(op_load);
578     instructions().append(dst->index());
579     instructions().append(addConstant(v));
580     return dst;
581 }
582
583 RegisterID* CodeGenerator::emitNullaryOp(OpcodeID opcode, RegisterID* dst)
584 {
585     emitOpcode(opcode);
586     instructions().append(dst->index());
587     return dst;
588 }
589
590 bool CodeGenerator::findScopedProperty(const Identifier& property, int& index, size_t& stackDepth)
591 {
592     // Cases where we cannot optimise the lookup
593     if (property == m_propertyNames->arguments || !canOptimizeNonLocals()) {
594         stackDepth = 0;
595         index = missingSymbolMarker();
596         return false;
597     }
598
599     ScopeChainIterator iter = m_scopeChain->begin();
600     ScopeChainIterator end = m_scopeChain->end();
601     size_t depth = 0;
602
603     for (; iter != end; ++iter, ++depth) {
604         JSObject* currentScope = *iter;
605         if (!currentScope->isVariableObject())
606             break;
607         JSVariableObject* currentVariableObject = static_cast<JSVariableObject*>(currentScope);
608         SymbolTableEntry entry = currentVariableObject->symbolTable().get(property.ustring().rep());
609
610         // Found the property
611         if (!entry.isEmpty()) {
612             stackDepth = depth;
613             index = entry.getIndex();
614             return true;
615         }
616         if (currentVariableObject->isDynamicScope())
617             break;
618     }
619
620     // Can't locate the property but we're able to avoid a few lookups
621     stackDepth = depth;
622     index = missingSymbolMarker();
623     return true;
624 }
625
626 RegisterID* CodeGenerator::emitResolve(RegisterID* dst, const Identifier& property)
627 {
628     size_t depth = 0;
629     int index = 0;
630     if (!findScopedProperty(property, index, depth)) {
631         // We can't optimise at all :-(
632         emitOpcode(op_resolve);
633         instructions().append(dst->index());
634         instructions().append(addConstant(property));
635         return dst;
636     }
637
638     if (index == missingSymbolMarker()) {
639         // In this case we are at least able to drop a few scope chains from the
640         // lookup chain, although we still need to hash from then on.
641         emitOpcode(op_resolve_skip);
642         instructions().append(dst->index());
643         instructions().append(addConstant(property));
644         instructions().append(depth);
645         return dst;
646     }
647
648     // Directly index the property lookup across multiple scopes.  Yay!
649     return emitGetScopedVar(dst, depth, index);
650 }
651
652 RegisterID* CodeGenerator::emitGetScopedVar(RegisterID* dst, size_t depth, int index)
653 {
654     emitOpcode(op_get_scoped_var);
655     instructions().append(dst->index());
656     instructions().append(index);
657     instructions().append(depth);
658     return dst;
659 }
660
661 RegisterID* CodeGenerator::emitPutScopedVar(size_t depth, int index, RegisterID* value)
662 {
663     emitOpcode(op_put_scoped_var);
664     instructions().append(index);
665     instructions().append(depth);
666     instructions().append(value->index());
667     return value;
668 }
669
670 RegisterID* CodeGenerator::emitResolveBase(RegisterID* dst, const Identifier& property)
671 {
672     emitOpcode(op_resolve_base);
673     instructions().append(dst->index());
674     instructions().append(addConstant(property));
675     return dst;
676 }
677
678 RegisterID* CodeGenerator::emitResolveWithBase(RegisterID* baseDst, RegisterID* propDst, const Identifier& property)
679 {
680     emitOpcode(op_resolve_with_base);
681     instructions().append(baseDst->index());
682     instructions().append(propDst->index());
683     instructions().append(addConstant(property));
684     return baseDst;
685 }
686
687 RegisterID* CodeGenerator::emitResolveFunction(RegisterID* baseDst, RegisterID* funcDst, const Identifier& property)
688 {
689     emitOpcode(op_resolve_func);
690     instructions().append(baseDst->index());
691     instructions().append(funcDst->index());
692     instructions().append(addConstant(property));
693     return baseDst;
694 }
695
696 RegisterID* CodeGenerator::emitGetById(RegisterID* dst, RegisterID* base, const Identifier& property)
697 {
698     emitOpcode(op_get_by_id);
699     instructions().append(dst->index());
700     instructions().append(base->index());
701     instructions().append(addConstant(property));
702     return dst;
703 }
704
705 RegisterID* CodeGenerator::emitPutById(RegisterID* base, const Identifier& property, RegisterID* value)
706 {
707     emitOpcode(op_put_by_id);
708     instructions().append(base->index());
709     instructions().append(addConstant(property));
710     instructions().append(value->index());
711     return value;
712 }
713
714 RegisterID* CodeGenerator::emitPutGetter(RegisterID* base, const Identifier& property, RegisterID* value)
715 {
716     emitOpcode(op_put_getter);
717     instructions().append(base->index());
718     instructions().append(addConstant(property));
719     instructions().append(value->index());
720     return value;
721 }
722
723 RegisterID* CodeGenerator::emitPutSetter(RegisterID* base, const Identifier& property, RegisterID* value)
724 {
725     emitOpcode(op_put_setter);
726     instructions().append(base->index());
727     instructions().append(addConstant(property));
728     instructions().append(value->index());
729     return value;
730 }
731
732 RegisterID* CodeGenerator::emitDeleteById(RegisterID* dst, RegisterID* base, const Identifier& property)
733 {
734     emitOpcode(op_del_by_id);
735     instructions().append(dst->index());
736     instructions().append(base->index());
737     instructions().append(addConstant(property));
738     return dst;
739 }
740
741 RegisterID* CodeGenerator::emitGetByVal(RegisterID* dst, RegisterID* base, RegisterID* property)
742 {
743     emitOpcode(op_get_by_val);
744     instructions().append(dst->index());
745     instructions().append(base->index());
746     instructions().append(property->index());
747     return dst;
748 }
749
750 RegisterID* CodeGenerator::emitPutByVal(RegisterID* base, RegisterID* property, RegisterID* value)
751 {
752     emitOpcode(op_put_by_val);
753     instructions().append(base->index());
754     instructions().append(property->index());
755     instructions().append(value->index());
756     return value;
757 }
758
759 RegisterID* CodeGenerator::emitDeleteByVal(RegisterID* dst, RegisterID* base, RegisterID* property)
760 {
761     emitOpcode(op_del_by_val);
762     instructions().append(dst->index());
763     instructions().append(base->index());
764     instructions().append(property->index());
765     return dst;
766 }
767
768 RegisterID* CodeGenerator::emitPutByIndex(RegisterID* base, unsigned index, RegisterID* value)
769 {
770     emitOpcode(op_put_by_index);
771     instructions().append(base->index());
772     instructions().append(index);
773     instructions().append(value->index());
774     return value;
775 }
776
777 RegisterID* CodeGenerator::emitNewFunction(RegisterID* r0, FuncDeclNode* n)
778 {
779     emitOpcode(op_new_func);
780     instructions().append(r0->index());
781     instructions().append(addConstant(n));
782     return r0;
783 }
784
785 RegisterID* CodeGenerator::emitNewRegExp(RegisterID* dst, RegExp* regExp)
786 {
787     emitOpcode(op_new_regexp);
788     instructions().append(dst->index());
789     instructions().append(addRegExp(regExp));
790     return dst;
791 }
792
793
794 RegisterID* CodeGenerator::emitNewFunctionExpression(RegisterID* r0, FuncExprNode* n)
795 {
796     emitOpcode(op_new_func_exp);
797     instructions().append(r0->index());
798     instructions().append(addConstant(n));
799     return r0;
800 }
801
802 RegisterID* CodeGenerator::emitCall(RegisterID* dst, RegisterID* func, RegisterID* base, ArgumentsNode* argumentsNode)
803 {
804     return emitCall(op_call, dst, func, base, argumentsNode);
805 }
806
807 RegisterID* CodeGenerator::emitCallEval(RegisterID* dst, RegisterID* func, RegisterID* base, ArgumentsNode* argumentsNode)
808 {
809     return emitCall(op_call_eval, dst, func, base, argumentsNode);
810 }
811
812 RegisterID* CodeGenerator::emitCall(OpcodeID opcodeID, RegisterID* dst, RegisterID* func, RegisterID* base, ArgumentsNode* argumentsNode)
813 {
814     ASSERT(opcodeID == op_call || opcodeID == op_call_eval);
815
816     RefPtr<RegisterID> refFunc = func;
817     RefPtr<RegisterID> refBase = base;
818
819     // Reserve space for call frame.
820     Vector<RefPtr<RegisterID>, Machine::CallFrameHeaderSize> callFrame;
821     for (int i = 0; i < Machine::CallFrameHeaderSize; ++i)
822         callFrame.append(newTemporary());
823
824     // Generate code for arguments.
825     Vector<RefPtr<RegisterID>, 16> argv;
826     argv.append(newTemporary()); // reserve space for "this"
827     for (ArgumentListNode* n = argumentsNode->m_listNode.get(); n; n = n->m_next.get()) {
828         argv.append(newTemporary());
829         emitNode(argv.last().get(), n);
830     }
831
832     emitOpcode(opcodeID);
833     instructions().append(dst->index());
834     instructions().append(func->index());
835     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.
836     instructions().append(argv.size() ? argv[0]->index() : m_temporaries.size()); // argv
837     instructions().append(argv.size()); // argc
838     return dst;
839 }
840
841 RegisterID* CodeGenerator::emitUnaryNoDstOp(OpcodeID opcode, RegisterID* src)
842 {
843     emitOpcode(opcode);
844     instructions().append(src->index());
845     return src;
846 }
847
848 RegisterID* CodeGenerator::emitConstruct(RegisterID* dst, RegisterID* func, ArgumentsNode* argumentsNode)
849 {
850     // Reserve space for call frame.
851     Vector<RefPtr<RegisterID>, Machine::CallFrameHeaderSize> callFrame;
852     for (int i = 0; i < Machine::CallFrameHeaderSize; ++i)
853         callFrame.append(newTemporary());
854
855     // Generate code for arguments.
856     Vector<RefPtr<RegisterID>, 16> argv;
857     argv.append(newTemporary()); // reserve space for "this"
858     for (ArgumentListNode* n = argumentsNode ? argumentsNode->m_listNode.get() : 0; n; n = n->m_next.get()) {
859         argv.append(newTemporary());
860         emitNode(argv.last().get(), n);
861     }
862
863     emitOpcode(op_construct);
864     instructions().append(dst->index());
865     instructions().append(func->index());
866     instructions().append(argv.size() ? argv[0]->index() : m_temporaries.size()); // argv
867     instructions().append(argv.size()); // argc
868     return dst;
869 }
870
871 RegisterID* CodeGenerator::emitPushScope(RegisterID* scope)
872 {
873     m_codeBlock->needsFullScopeChain = true;
874     ControlFlowContext context;
875     context.isFinallyBlock = false;
876     m_scopeContextStack.append(context);
877     m_dynamicScopeDepth++;
878
879     return emitUnaryNoDstOp(op_push_scope, scope);
880 }
881
882 void CodeGenerator::emitPopScope()
883 {
884     ASSERT(m_scopeContextStack.size());
885     ASSERT(!m_scopeContextStack.last().isFinallyBlock);
886
887     emitOpcode(op_pop_scope);
888
889     m_scopeContextStack.removeLast();
890     m_dynamicScopeDepth--;
891 }
892
893 void CodeGenerator::emitDebugHook(DebugHookID debugHookID, int firstLine, int lastLine)
894 {
895     if (!m_shouldEmitDebugHooks)
896         return;
897     emitOpcode(op_debug);
898     instructions().append(debugHookID);
899     instructions().append(firstLine);
900     instructions().append(lastLine);
901 }
902
903 void CodeGenerator::pushFinallyContext(LabelID* target, RegisterID* retAddrDst)
904 {
905     ControlFlowContext scope;
906     scope.isFinallyBlock = true;
907     FinallyContext context = { target, retAddrDst };
908     scope.finallyContext = context;
909     m_scopeContextStack.append(scope);
910     m_finallyDepth++;
911 }
912
913 void CodeGenerator::popFinallyContext()
914 {
915     ASSERT(m_scopeContextStack.size());
916     ASSERT(m_scopeContextStack.last().isFinallyBlock);
917     ASSERT(m_finallyDepth > 0);
918     m_scopeContextStack.removeLast();
919     m_finallyDepth--;
920 }
921
922 void CodeGenerator::pushJumpContext(LabelStack* labels, LabelID* continueTarget, LabelID* breakTarget, bool isValidUnlabeledBreakTarget)
923 {
924     JumpContext context = { labels, continueTarget, breakTarget, scopeDepth(), isValidUnlabeledBreakTarget };
925     m_jumpContextStack.append(context);
926     if (continueTarget)
927         m_continueDepth++;
928 }
929
930 void CodeGenerator::popJumpContext()
931 {
932     ASSERT(m_jumpContextStack.size());
933     if (m_jumpContextStack.last().continueTarget)
934         m_continueDepth--;
935     m_jumpContextStack.removeLast();
936 }
937
938 JumpContext* CodeGenerator::jumpContextForContinue(const Identifier& label)
939 {
940     if(!m_jumpContextStack.size())
941         return 0;
942
943     if (label.isEmpty()) {
944         for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
945             JumpContext* scope = &m_jumpContextStack[i];
946             if (scope->continueTarget)
947                 return scope;
948         }
949         return 0;
950     }
951
952     for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
953         JumpContext* scope = &m_jumpContextStack[i];
954         if (scope->labels->contains(label))
955             return scope;
956     }
957     return 0;
958 }
959
960 JumpContext* CodeGenerator::jumpContextForBreak(const Identifier& label)
961 {
962     if(!m_jumpContextStack.size())
963         return 0;
964
965     if (label.isEmpty()) {
966         for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
967             JumpContext* scope = &m_jumpContextStack[i];
968             if (scope->isValidUnlabeledBreakTarget)
969                 return scope;
970         }
971         return 0;
972     }
973
974     for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
975         JumpContext* scope = &m_jumpContextStack[i];
976         if (scope->labels->contains(label))
977             return scope;
978     }
979     return 0;
980 }
981
982 PassRefPtr<LabelID> CodeGenerator::emitComplexJumpScopes(LabelID* target, ControlFlowContext* topScope, ControlFlowContext* bottomScope)
983 {
984     while (topScope > bottomScope) {
985         // First we count the number of dynamic scopes we need to remove to get
986         // to a finally block.
987         int nNormalScopes = 0;
988         while (topScope > bottomScope) {
989             if (topScope->isFinallyBlock)
990                 break;
991             ++nNormalScopes;
992             --topScope;
993         }
994
995         if (nNormalScopes) {
996             // We need to remove a number of dynamic scopes to get to the next
997             // finally block
998             emitOpcode(op_jmp_scopes);
999             instructions().append(nNormalScopes);
1000
1001             // If topScope == bottomScope then there isn't actually a finally block
1002             // left to emit, so make the jmp_scopes jump directly to the target label
1003             if (topScope == bottomScope) {
1004                 instructions().append(target->offsetFrom(instructions().size()));
1005                 return target;
1006             }
1007
1008             // Otherwise we just use jmp_scopes to pop a group of scopes and go
1009             // to the next instruction
1010             RefPtr<LabelID> nextInsn = newLabel();
1011             instructions().append(nextInsn->offsetFrom(instructions().size()));
1012             emitLabel(nextInsn.get());
1013         }
1014
1015         // To get here there must be at least one finally block present
1016         do {
1017             ASSERT(topScope->isFinallyBlock);
1018             emitJumpSubroutine(topScope->finallyContext.retAddrDst, topScope->finallyContext.finallyAddr);
1019             --topScope;
1020             if (!topScope->isFinallyBlock)
1021                 break;
1022         } while (topScope > bottomScope);
1023     }
1024     return emitJump(target);
1025 }
1026
1027 PassRefPtr<LabelID> CodeGenerator::emitJumpScopes(LabelID* target, int targetScopeDepth)
1028 {
1029     ASSERT(scopeDepth() - targetScopeDepth >= 0);
1030
1031     size_t scopeDelta = scopeDepth() - targetScopeDepth;
1032     ASSERT(scopeDelta <= m_scopeContextStack.size());
1033     if (!scopeDelta)
1034         return emitJump(target);
1035
1036     if (m_finallyDepth)
1037         return emitComplexJumpScopes(target, &m_scopeContextStack.last(), &m_scopeContextStack.last() - scopeDelta);
1038
1039     emitOpcode(op_jmp_scopes);
1040     instructions().append(scopeDelta);
1041     instructions().append(target->offsetFrom(instructions().size()));
1042     return target;
1043 }
1044
1045 RegisterID* CodeGenerator::emitNextPropertyName(RegisterID* dst, RegisterID* iter, LabelID* target)
1046 {
1047     emitOpcode(op_next_pname);
1048     instructions().append(dst->index());
1049     instructions().append(iter->index());
1050     instructions().append(target->offsetFrom(instructions().size()));
1051     return dst;
1052 }
1053
1054 RegisterID* CodeGenerator::emitCatch(RegisterID* targetRegister, LabelID* start, LabelID* end)
1055 {
1056     HandlerInfo info = { start->offsetFrom(0), end->offsetFrom(0), instructions().size(), m_dynamicScopeDepth };
1057     exceptionHandlers().append(info);
1058     emitOpcode(op_catch);
1059     instructions().append(targetRegister->index());
1060     return targetRegister;
1061 }
1062
1063 RegisterID* CodeGenerator::emitNewError(RegisterID* dst, ErrorType type, JSValue* message)
1064 {
1065     emitOpcode(op_new_error);
1066     instructions().append(dst->index());
1067     instructions().append(static_cast<int>(type));
1068     instructions().append(addConstant(message));
1069     return dst;
1070 }
1071
1072 PassRefPtr<LabelID> CodeGenerator::emitJumpSubroutine(RegisterID* retAddrDst, LabelID* finally)
1073 {
1074     emitOpcode(op_jsr);
1075     instructions().append(retAddrDst->index());
1076     instructions().append(finally->offsetFrom(instructions().size()));
1077     return finally;
1078 }
1079
1080 void CodeGenerator::emitSubroutineReturn(RegisterID* retAddrSrc)
1081 {
1082     emitOpcode(op_sret);
1083     instructions().append(retAddrSrc->index());
1084 }
1085
1086 } // namespace KJS