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