2008-06-30 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 "JSFunction.h"
34 #include "Machine.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, bool isConstant, RegisterID*& r0)
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 bool CodeGenerator::addGlobalVar(const Identifier& ident, bool isConstant, RegisterID*& r0)
171 {
172     int index = m_nextVar;
173     SymbolTableEntry newEntry(index, isConstant ? ReadOnly : 0);
174     pair<SymbolTable::iterator, bool> result = symbolTable().add(ident.ustring().rep(), newEntry);
175
176     if (!result.second)
177         index = result.first->second.getIndex();
178     else {
179         --m_nextVar;
180         m_locals.append(index + m_globalVarStorageOffset);
181     }
182
183     r0 = &m_locals[localsIndex(index)];
184     return result.second;
185 }
186
187 CodeGenerator::CodeGenerator(ProgramNode* programNode, const Debugger* debugger, const ScopeChain& scopeChain, SymbolTable* symbolTable, CodeBlock* codeBlock, VarStack& varStack, FunctionStack& functionStack)
188     : m_shouldEmitDebugHooks(!!debugger)
189     , m_scopeChain(&scopeChain)
190     , m_symbolTable(symbolTable)
191     , m_scopeNode(programNode)
192     , m_codeBlock(codeBlock)
193     , m_thisRegister(RegisterFile::ProgramCodeThisRegister)
194     , m_finallyDepth(0)
195     , m_dynamicScopeDepth(0)
196     , m_codeType(GlobalCode)
197     , m_continueDepth(0)
198     , m_nextVar(-1)
199     , m_globalData(&scopeChain.globalObject()->globalExec()->globalData())
200     , m_lastOpcodeID(op_end)
201 {
202     // FIXME: Move code that modifies the global object to Machine::execute.
203     
204     m_codeBlock->numVars = 1; // Allocate space for "this"
205
206     JSGlobalObject* globalObject = scopeChain.globalObject();
207     ExecState* exec = globalObject->globalExec();
208     RegisterFile* registerFile = &exec->globalData().machine->registerFile();
209     
210     // Shift register indexes in generated code to elide registers allocated by intermediate stack frames.
211     m_globalVarStorageOffset =  -1 - RegisterFile::CallFrameHeaderSize - registerFile->size();
212
213     // Add previously defined symbols to bookkeeping.
214     m_locals.resize(symbolTable->size());
215     SymbolTable::iterator end = symbolTable->end();
216     for (SymbolTable::iterator it = symbolTable->begin(); it != end; ++it)
217         m_locals[localsIndex(it->second.getIndex())].setIndex(it->second.getIndex() + m_globalVarStorageOffset);
218
219     bool canOptimizeNewGlobals = symbolTable->size() + functionStack.size() + varStack.size() < registerFile->maxGlobals();
220     if (canOptimizeNewGlobals) {
221         // Shift new symbols so they get stored prior to existing symbols.
222         m_nextVar -= symbolTable->size();
223
224         for (size_t i = 0; i < functionStack.size(); ++i) {
225             FuncDeclNode* funcDecl = functionStack[i].get();
226             globalObject->removeDirect(funcDecl->m_ident); // Make sure our new function is not shadowed by an old property.
227             emitNewFunction(addGlobalVar(funcDecl->m_ident, false), funcDecl);
228         }
229
230         for (size_t i = 0; i < varStack.size(); ++i) {
231             if (!globalObject->hasProperty(exec, varStack[i].first))
232                 emitLoad(addGlobalVar(varStack[i].first, varStack[i].second & DeclarationStacks::IsConstant), jsUndefined());
233         }
234     } else {
235         for (size_t i = 0; i < functionStack.size(); ++i) {
236             FuncDeclNode* funcDecl = functionStack[i].get();
237             globalObject->putWithAttributes(exec, funcDecl->m_ident, funcDecl->makeFunction(exec, scopeChain.node()), DontDelete);
238         }
239         for (size_t i = 0; i < varStack.size(); ++i) {
240             if (globalObject->hasProperty(exec, varStack[i].first))
241                 continue;
242             int attributes = DontDelete;
243             if (varStack[i].second & DeclarationStacks::IsConstant)
244                 attributes |= ReadOnly;
245             globalObject->putWithAttributes(exec, varStack[i].first, jsUndefined(), attributes);
246         }
247     }
248 }
249
250 CodeGenerator::CodeGenerator(FunctionBodyNode* functionBody, const Debugger* debugger, const ScopeChain& scopeChain, SymbolTable* symbolTable, CodeBlock* codeBlock)
251     : m_shouldEmitDebugHooks(!!debugger)
252     , m_scopeChain(&scopeChain)
253     , m_symbolTable(symbolTable)
254     , m_scopeNode(functionBody)
255     , m_codeBlock(codeBlock)
256     , m_finallyDepth(0)
257     , m_dynamicScopeDepth(0)
258     , m_codeType(FunctionCode)
259     , m_continueDepth(0)
260     , m_nextVar(-1)
261     , m_globalData(&scopeChain.globalObject()->globalExec()->globalData())
262     , m_lastOpcodeID(op_end)
263 {
264     const Node::FunctionStack& functionStack = functionBody->functionStack();
265     for (size_t i = 0; i < functionStack.size(); ++i) {
266         FuncDeclNode* funcDecl = functionStack[i].get();
267         const Identifier& ident = funcDecl->m_ident;
268
269         m_functions.add(ident.ustring().rep());
270         emitNewFunction(addVar(ident, false), funcDecl);
271     }
272
273     const Node::VarStack& varStack = functionBody->varStack();
274     for (size_t i = 0; i < varStack.size(); ++i) {
275         const Identifier& ident = varStack[i].first;
276         if (ident == propertyNames().arguments)
277             continue;
278         addVar(ident, varStack[i].second & DeclarationStacks::IsConstant);
279     }
280
281     Vector<Identifier>& parameters = functionBody->parameters();
282     m_nextParameter = m_nextVar - parameters.size(); // parameters are allocated prior to vars
283     m_locals.resize(localsIndex(m_nextParameter) + 1); // localsIndex of 0 => m_locals size of 1
284
285     // Add "this" as a parameter
286     m_thisRegister.setIndex(m_nextParameter);
287     ++m_nextParameter;
288     ++m_codeBlock->numParameters;
289     
290     for (size_t i = 0; i < parameters.size(); ++i)
291         addParameter(parameters[i]);
292 }
293
294 CodeGenerator::CodeGenerator(EvalNode* evalNode, const Debugger* debugger, const ScopeChain& scopeChain, SymbolTable* symbolTable, EvalCodeBlock* codeBlock)
295     : m_shouldEmitDebugHooks(!!debugger)
296     , m_scopeChain(&scopeChain)
297     , m_symbolTable(symbolTable)
298     , m_scopeNode(evalNode)
299     , m_codeBlock(codeBlock)
300     , m_thisRegister(RegisterFile::ProgramCodeThisRegister)
301     , m_finallyDepth(0)
302     , m_dynamicScopeDepth(0)
303     , m_codeType(EvalCode)
304     , m_continueDepth(0)
305     , m_globalData(&scopeChain.globalObject()->globalExec()->globalData())
306     , m_lastOpcodeID(op_end)
307 {
308     m_codeBlock->numVars = 1; // Allocate space for "this"
309 }
310
311 CodeGenerator::~CodeGenerator()
312 {
313 }
314
315 RegisterID* CodeGenerator::addParameter(const Identifier& ident)
316 {
317     // Parameters overwrite var declarations, but not function declarations,
318     // in the symbol table.
319     RegisterID* result = 0;
320     UString::Rep* rep = ident.ustring().rep();
321     if (!m_functions.contains(rep)) {
322         symbolTable().set(rep, m_nextParameter);
323         m_locals[localsIndex(m_nextParameter)].setIndex(m_nextParameter);
324         result = &(m_locals[localsIndex(m_nextParameter)]);
325     }
326
327     // To maintain the calling convention, we have to allocate unique space for
328     // each parameter, even if the parameter doesn't make it into the symbol table.
329     ++m_nextParameter;
330     ++m_codeBlock->numParameters;
331     return result;
332 }
333
334 RegisterID* CodeGenerator::registerForLocal(const Identifier& ident)
335 {
336     if (m_codeType == FunctionCode && ident == propertyNames().arguments)
337         m_codeBlock->needsFullScopeChain = true;
338
339     if (ident == propertyNames().thisIdentifier)
340         return &m_thisRegister;
341
342     if (!shouldOptimizeLocals())
343         return 0;
344
345     SymbolTableEntry entry = symbolTable().get(ident.ustring().rep());
346     if (entry.isNull())
347         return 0;
348
349     return &m_locals[localsIndex(entry.getIndex())];
350 }
351
352 RegisterID* CodeGenerator::registerForLocalConstInit(const Identifier& ident)
353 {
354     if (m_codeType == EvalCode)
355         return 0;
356
357     SymbolTableEntry entry = symbolTable().get(ident.ustring().rep());
358     ASSERT(!entry.isNull());
359
360     return &m_locals[localsIndex(entry.getIndex())];
361 }
362
363 bool CodeGenerator::isLocal(const Identifier& ident)
364 {
365     if (ident == propertyNames().thisIdentifier)
366         return true;
367     
368     return shouldOptimizeLocals() && symbolTable().contains(ident.ustring().rep());
369 }
370
371 bool CodeGenerator::isLocalConstant(const Identifier& ident)
372 {
373     return symbolTable().get(ident.ustring().rep()).isReadOnly();
374 }
375
376 RegisterID* CodeGenerator::newTemporary()
377 {
378     // Reclaim free register IDs.
379     while (m_temporaries.size() && !m_temporaries.last().refCount())
380         m_temporaries.removeLast();
381
382     // Allocate new register ID.
383     m_temporaries.append(m_temporaries.size());
384     m_codeBlock->numTemporaries = max<int>(m_codeBlock->numTemporaries, m_temporaries.size());
385     return &m_temporaries.last();
386 }
387
388
389 RegisterID* CodeGenerator::highestUsedRegister()
390 {
391     while (m_temporaries.size() < static_cast<unsigned>(m_codeBlock->numTemporaries))
392         m_temporaries.append(m_temporaries.size());
393     return &m_temporaries.last();
394 }
395
396 PassRefPtr<LabelID> CodeGenerator::newLabel()
397 {
398     // Reclaim free label IDs.
399     while (m_labels.size() && !m_labels.last().refCount())
400         m_labels.removeLast();
401
402     // Allocate new label ID.
403     m_labels.append(m_codeBlock);
404     return &m_labels.last();
405 }
406
407 PassRefPtr<LabelID> CodeGenerator::emitLabel(LabelID* l0)
408 {
409     l0->setLocation(instructions().size());
410     
411     // This disables peephole optimizations when an instruction is a jump target
412     m_lastOpcodeID = op_end;
413     
414     return l0;
415 }
416
417 void CodeGenerator::emitOpcode(OpcodeID opcodeID)
418 {
419     instructions().append(globalData()->machine->getOpcode(opcodeID));
420     m_lastOpcodeID = opcodeID;
421 }
422
423 void CodeGenerator::retrieveLastBinaryOp(int& dstIndex, int& src1Index, int& src2Index)
424 {
425     ASSERT(instructions().size() >= 4);
426     size_t size = instructions().size();
427     dstIndex = instructions().at(size - 3).u.operand;
428     src1Index = instructions().at(size - 2).u.operand;
429     src2Index = instructions().at(size - 1).u.operand;
430 }
431
432 void ALWAYS_INLINE CodeGenerator::rewindBinaryOp()
433 {
434     ASSERT(instructions().size() >= 4);
435     instructions().shrink(instructions().size() - 4);
436 }
437
438 PassRefPtr<LabelID> CodeGenerator::emitJump(LabelID* target)
439 {
440     emitOpcode(target->isForwardLabel() ? op_jmp : op_loop);
441     instructions().append(target->offsetFrom(instructions().size()));
442     return target;
443 }
444
445 PassRefPtr<LabelID> CodeGenerator::emitJumpIfTrue(RegisterID* cond, LabelID* target)
446 {
447     if (m_lastOpcodeID == op_less) {
448         int dstIndex;
449         int src1Index;
450         int src2Index;
451         
452         retrieveLastBinaryOp(dstIndex, src1Index, src2Index);
453         
454         if (cond->index() == dstIndex && cond->isTemporary() && !cond->refCount()) {
455             rewindBinaryOp();
456             emitOpcode(target->isForwardLabel() ? op_jless : op_loop_if_less);
457             instructions().append(src1Index);
458             instructions().append(src2Index);
459             instructions().append(target->offsetFrom(instructions().size()));
460             return target;
461         }
462     }
463     
464     emitOpcode(target->isForwardLabel() ? op_jtrue : op_loop_if_true);
465     instructions().append(cond->index());
466     instructions().append(target->offsetFrom(instructions().size()));
467     return target;
468 }
469
470 PassRefPtr<LabelID> CodeGenerator::emitJumpIfFalse(RegisterID* cond, LabelID* target)
471 {
472     ASSERT(target->isForwardLabel());
473     
474     if (m_lastOpcodeID == op_less) {
475         int dstIndex;
476         int src1Index;
477         int src2Index;
478         
479         retrieveLastBinaryOp(dstIndex, src1Index, src2Index);
480         
481         if (cond->index() == dstIndex && cond->isTemporary() && !cond->refCount()) {
482             rewindBinaryOp();
483             emitOpcode(op_jnless);
484             instructions().append(src1Index);
485             instructions().append(src2Index);
486             instructions().append(target->offsetFrom(instructions().size()));
487             return target;
488         }
489     }
490     
491     emitOpcode(op_jfalse);
492     instructions().append(cond->index());
493     instructions().append(target->offsetFrom(instructions().size()));
494     return target;
495 }
496
497 unsigned CodeGenerator::addConstant(FuncDeclNode* n)
498 {
499     // No need to explicitly unique function body nodes -- they're unique already.
500     int index = m_codeBlock->functions.size();
501     m_codeBlock->functions.append(n);
502     return index;
503 }
504
505 unsigned CodeGenerator::addConstant(FuncExprNode* n)
506 {
507     // No need to explicitly unique function expression nodes -- they're unique already.
508     int index = m_codeBlock->functionExpressions.size();
509     m_codeBlock->functionExpressions.append(n);
510     return index;
511 }
512
513 unsigned CodeGenerator::addConstant(const Identifier& ident)
514 {
515     UString::Rep* rep = ident.ustring().rep();
516     pair<IdentifierMap::iterator, bool> result = m_identifierMap.add(rep, m_codeBlock->identifiers.size());
517     if (result.second) // new entry
518         m_codeBlock->identifiers.append(Identifier(m_globalData, rep));
519
520     return result.first->second;
521 }
522
523 unsigned CodeGenerator::addConstant(JSValue* v)
524 {
525     pair<JSValueMap::iterator, bool> result = m_jsValueMap.add(v, m_codeBlock->jsValues.size());
526     if (result.second) // new entry
527         m_codeBlock->jsValues.append(v);
528
529     return result.first->second;
530 }
531
532 unsigned CodeGenerator::addRegExp(RegExp* r)
533 {
534     int index = m_codeBlock->regexps.size();
535     m_codeBlock->regexps.append(r);
536     return index;
537 }
538
539 RegisterID* CodeGenerator::emitMove(RegisterID* dst, RegisterID* src)
540 {
541     emitOpcode(op_mov);
542     instructions().append(dst->index());
543     instructions().append(src->index());
544     return dst;
545 }
546
547 RegisterID* CodeGenerator::emitUnaryOp(OpcodeID opcode, RegisterID* dst, RegisterID* src)
548 {
549     emitOpcode(opcode);
550     instructions().append(dst->index());
551     instructions().append(src->index());
552     return dst;
553 }
554
555 RegisterID* CodeGenerator::emitPreInc(RegisterID* srcDst)
556 {
557     emitOpcode(op_pre_inc);
558     instructions().append(srcDst->index());
559     return srcDst;
560 }
561
562 RegisterID* CodeGenerator::emitPreDec(RegisterID* srcDst)
563 {
564     emitOpcode(op_pre_dec);
565     instructions().append(srcDst->index());
566     return srcDst;
567 }
568
569 RegisterID* CodeGenerator::emitPostInc(RegisterID* dst, RegisterID* srcDst)
570 {
571     emitOpcode(op_post_inc);
572     instructions().append(dst->index());
573     instructions().append(srcDst->index());
574     return dst;
575 }
576
577 RegisterID* CodeGenerator::emitPostDec(RegisterID* dst, RegisterID* srcDst)
578 {
579     emitOpcode(op_post_dec);
580     instructions().append(dst->index());
581     instructions().append(srcDst->index());
582     return dst;
583 }
584
585 RegisterID* CodeGenerator::emitBinaryOp(OpcodeID opcode, RegisterID* dst, RegisterID* src1, RegisterID* src2)
586 {
587     emitOpcode(opcode);
588     instructions().append(dst->index());
589     instructions().append(src1->index());
590     instructions().append(src2->index());
591     return dst;
592 }
593
594 RegisterID* CodeGenerator::emitLoad(RegisterID* dst, bool b)
595 {
596     emitOpcode(op_load);
597     instructions().append(dst->index());
598     instructions().append(addConstant(jsBoolean(b)));
599     return dst;
600 }
601
602 RegisterID* CodeGenerator::emitLoad(RegisterID* dst, double d)
603 {
604     emitOpcode(op_load);
605     instructions().append(dst->index());
606     instructions().append(addConstant(jsNumber(globalExec(), d)));
607     return dst;
608 }
609
610 RegisterID* CodeGenerator::emitLoad(RegisterID* dst, JSValue* v)
611 {
612     emitOpcode(op_load);
613     instructions().append(dst->index());
614     instructions().append(addConstant(v));
615     return dst;
616 }
617
618 RegisterID* CodeGenerator::emitNullaryOp(OpcodeID opcode, RegisterID* dst)
619 {
620     emitOpcode(opcode);
621     instructions().append(dst->index());
622     return dst;
623 }
624
625 bool CodeGenerator::findScopedProperty(const Identifier& property, int& index, size_t& stackDepth)
626 {
627     // Cases where we cannot optimise the lookup
628     if (property == propertyNames().arguments || !canOptimizeNonLocals()) {
629         stackDepth = 0;
630         index = missingSymbolMarker();
631         return false;
632     }
633
634     ScopeChainIterator iter = m_scopeChain->begin();
635     ScopeChainIterator end = m_scopeChain->end();
636     size_t depth = 0;
637
638     for (; iter != end; ++iter, ++depth) {
639         JSObject* currentScope = *iter;
640         if (!currentScope->isVariableObject())
641             break;
642         JSVariableObject* currentVariableObject = static_cast<JSVariableObject*>(currentScope);
643         SymbolTableEntry entry = currentVariableObject->symbolTable().get(property.ustring().rep());
644
645         // Found the property
646         if (!entry.isNull()) {
647             stackDepth = depth;
648             index = entry.getIndex();
649             return true;
650         }
651         if (currentVariableObject->isDynamicScope())
652             break;
653     }
654
655     // Can't locate the property but we're able to avoid a few lookups
656     stackDepth = depth;
657     index = missingSymbolMarker();
658     return true;
659 }
660
661 RegisterID* CodeGenerator::emitResolve(RegisterID* dst, const Identifier& property)
662 {
663     size_t depth = 0;
664     int index = 0;
665     if (!findScopedProperty(property, index, depth)) {
666         // We can't optimise at all :-(
667         emitOpcode(op_resolve);
668         instructions().append(dst->index());
669         instructions().append(addConstant(property));
670         return dst;
671     }
672
673     if (index == missingSymbolMarker()) {
674         // In this case we are at least able to drop a few scope chains from the
675         // lookup chain, although we still need to hash from then on.
676         emitOpcode(op_resolve_skip);
677         instructions().append(dst->index());
678         instructions().append(addConstant(property));
679         instructions().append(depth);
680         return dst;
681     }
682
683     // Directly index the property lookup across multiple scopes.  Yay!
684     return emitGetScopedVar(dst, depth, index);
685 }
686
687 RegisterID* CodeGenerator::emitGetScopedVar(RegisterID* dst, size_t depth, int index)
688 {
689     emitOpcode(op_get_scoped_var);
690     instructions().append(dst->index());
691     instructions().append(index);
692     instructions().append(depth);
693     return dst;
694 }
695
696 RegisterID* CodeGenerator::emitPutScopedVar(size_t depth, int index, RegisterID* value)
697 {
698     emitOpcode(op_put_scoped_var);
699     instructions().append(index);
700     instructions().append(depth);
701     instructions().append(value->index());
702     return value;
703 }
704
705 RegisterID* CodeGenerator::emitResolveBase(RegisterID* dst, const Identifier& property)
706 {
707     emitOpcode(op_resolve_base);
708     instructions().append(dst->index());
709     instructions().append(addConstant(property));
710     return dst;
711 }
712
713 RegisterID* CodeGenerator::emitResolveWithBase(RegisterID* baseDst, RegisterID* propDst, const Identifier& property)
714 {
715     emitOpcode(op_resolve_with_base);
716     instructions().append(baseDst->index());
717     instructions().append(propDst->index());
718     instructions().append(addConstant(property));
719     return baseDst;
720 }
721
722 RegisterID* CodeGenerator::emitResolveFunction(RegisterID* baseDst, RegisterID* funcDst, const Identifier& property)
723 {
724     emitOpcode(op_resolve_func);
725     instructions().append(baseDst->index());
726     instructions().append(funcDst->index());
727     instructions().append(addConstant(property));
728     return baseDst;
729 }
730
731 RegisterID* CodeGenerator::emitGetById(RegisterID* dst, RegisterID* base, const Identifier& property)
732 {
733     emitOpcode(op_get_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::emitPutById(RegisterID* base, const Identifier& property, RegisterID* value)
741 {
742     emitOpcode(op_put_by_id);
743     instructions().append(base->index());
744     instructions().append(addConstant(property));
745     instructions().append(value->index());
746     return value;
747 }
748
749 RegisterID* CodeGenerator::emitPutGetter(RegisterID* base, const Identifier& property, RegisterID* value)
750 {
751     emitOpcode(op_put_getter);
752     instructions().append(base->index());
753     instructions().append(addConstant(property));
754     instructions().append(value->index());
755     return value;
756 }
757
758 RegisterID* CodeGenerator::emitPutSetter(RegisterID* base, const Identifier& property, RegisterID* value)
759 {
760     emitOpcode(op_put_setter);
761     instructions().append(base->index());
762     instructions().append(addConstant(property));
763     instructions().append(value->index());
764     return value;
765 }
766
767 RegisterID* CodeGenerator::emitDeleteById(RegisterID* dst, RegisterID* base, const Identifier& property)
768 {
769     emitOpcode(op_del_by_id);
770     instructions().append(dst->index());
771     instructions().append(base->index());
772     instructions().append(addConstant(property));
773     return dst;
774 }
775
776 RegisterID* CodeGenerator::emitGetByVal(RegisterID* dst, RegisterID* base, RegisterID* property)
777 {
778     emitOpcode(op_get_by_val);
779     instructions().append(dst->index());
780     instructions().append(base->index());
781     instructions().append(property->index());
782     return dst;
783 }
784
785 RegisterID* CodeGenerator::emitPutByVal(RegisterID* base, RegisterID* property, RegisterID* value)
786 {
787     emitOpcode(op_put_by_val);
788     instructions().append(base->index());
789     instructions().append(property->index());
790     instructions().append(value->index());
791     return value;
792 }
793
794 RegisterID* CodeGenerator::emitDeleteByVal(RegisterID* dst, RegisterID* base, RegisterID* property)
795 {
796     emitOpcode(op_del_by_val);
797     instructions().append(dst->index());
798     instructions().append(base->index());
799     instructions().append(property->index());
800     return dst;
801 }
802
803 RegisterID* CodeGenerator::emitPutByIndex(RegisterID* base, unsigned index, RegisterID* value)
804 {
805     emitOpcode(op_put_by_index);
806     instructions().append(base->index());
807     instructions().append(index);
808     instructions().append(value->index());
809     return value;
810 }
811
812 RegisterID* CodeGenerator::emitNewArray(RegisterID* dst, ElementNode* elements)
813 {
814     Vector<RefPtr<RegisterID>, 16> argv;
815     for (ElementNode* n = elements; n; n = n->next()) {
816         if (n->elision())
817             break;
818         argv.append(newTemporary());
819         emitNode(argv.last().get(), n->value());
820     }
821     emitOpcode(op_new_array);
822     instructions().append(dst->index());
823     instructions().append(argv.size() ? argv[0]->index() : 0); // argv
824     instructions().append(argv.size()); // argc
825     return dst;
826 }
827
828 RegisterID* CodeGenerator::emitNewFunction(RegisterID* dst, FuncDeclNode* n)
829 {
830     emitOpcode(op_new_func);
831     instructions().append(dst->index());
832     instructions().append(addConstant(n));
833     return dst;
834 }
835
836 RegisterID* CodeGenerator::emitNewRegExp(RegisterID* dst, RegExp* regExp)
837 {
838     emitOpcode(op_new_regexp);
839     instructions().append(dst->index());
840     instructions().append(addRegExp(regExp));
841     return dst;
842 }
843
844
845 RegisterID* CodeGenerator::emitNewFunctionExpression(RegisterID* r0, FuncExprNode* n)
846 {
847     emitOpcode(op_new_func_exp);
848     instructions().append(r0->index());
849     instructions().append(addConstant(n));
850     return r0;
851 }
852
853 RegisterID* CodeGenerator::emitCall(RegisterID* dst, RegisterID* func, RegisterID* base, ArgumentsNode* argumentsNode)
854 {
855     return emitCall(op_call, dst, func, base, argumentsNode);
856 }
857
858 RegisterID* CodeGenerator::emitCallEval(RegisterID* dst, RegisterID* func, RegisterID* base, ArgumentsNode* argumentsNode)
859 {
860     return emitCall(op_call_eval, dst, func, base, argumentsNode);
861 }
862
863 RegisterID* CodeGenerator::emitCall(OpcodeID opcodeID, RegisterID* dst, RegisterID* func, RegisterID* base, ArgumentsNode* argumentsNode)
864 {
865     ASSERT(opcodeID == op_call || opcodeID == op_call_eval);
866
867     RefPtr<RegisterID> refFunc = func;
868     RefPtr<RegisterID> refBase = base;
869
870     // Reserve space for call frame.
871     Vector<RefPtr<RegisterID>, RegisterFile::CallFrameHeaderSize> callFrame;
872     for (int i = 0; i < RegisterFile::CallFrameHeaderSize; ++i)
873         callFrame.append(newTemporary());
874
875     // Generate code for arguments.
876     Vector<RefPtr<RegisterID>, 16> argv;
877     argv.append(newTemporary()); // reserve space for "this"
878     for (ArgumentListNode* n = argumentsNode->m_listNode.get(); n; n = n->m_next.get()) {
879         argv.append(newTemporary());
880         emitNode(argv.last().get(), n);
881     }
882
883     emitOpcode(opcodeID);
884     instructions().append(dst->index());
885     instructions().append(func->index());
886     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.
887     instructions().append(argv.size() ? argv[0]->index() : m_temporaries.size()); // argv
888     instructions().append(argv.size()); // argc
889     return dst;
890 }
891
892 RegisterID* CodeGenerator::emitUnaryNoDstOp(OpcodeID opcode, RegisterID* src)
893 {
894     emitOpcode(opcode);
895     instructions().append(src->index());
896     return src;
897 }
898
899 RegisterID* CodeGenerator::emitConstruct(RegisterID* dst, RegisterID* func, ArgumentsNode* argumentsNode)
900 {
901     // Reserve space for call frame.
902     Vector<RefPtr<RegisterID>, RegisterFile::CallFrameHeaderSize> callFrame;
903     for (int i = 0; i < RegisterFile::CallFrameHeaderSize; ++i)
904         callFrame.append(newTemporary());
905
906     // Generate code for arguments.
907     Vector<RefPtr<RegisterID>, 16> argv;
908     argv.append(newTemporary()); // reserve space for "this"
909     for (ArgumentListNode* n = argumentsNode ? argumentsNode->m_listNode.get() : 0; n; n = n->m_next.get()) {
910         argv.append(newTemporary());
911         emitNode(argv.last().get(), n);
912     }
913
914     emitOpcode(op_construct);
915     instructions().append(dst->index());
916     instructions().append(func->index());
917     instructions().append(argv.size() ? argv[0]->index() : m_temporaries.size()); // argv
918     instructions().append(argv.size()); // argc
919     return dst;
920 }
921
922 RegisterID* CodeGenerator::emitPushScope(RegisterID* scope)
923 {
924     m_codeBlock->needsFullScopeChain = true;
925     ControlFlowContext context;
926     context.isFinallyBlock = false;
927     m_scopeContextStack.append(context);
928     m_dynamicScopeDepth++;
929
930     return emitUnaryNoDstOp(op_push_scope, scope);
931 }
932
933 void CodeGenerator::emitPopScope()
934 {
935     ASSERT(m_scopeContextStack.size());
936     ASSERT(!m_scopeContextStack.last().isFinallyBlock);
937
938     emitOpcode(op_pop_scope);
939
940     m_scopeContextStack.removeLast();
941     m_dynamicScopeDepth--;
942 }
943
944 void CodeGenerator::emitDebugHook(DebugHookID debugHookID, int firstLine, int lastLine)
945 {
946     if (!m_shouldEmitDebugHooks)
947         return;
948     emitOpcode(op_debug);
949     instructions().append(debugHookID);
950     instructions().append(firstLine);
951     instructions().append(lastLine);
952 }
953
954 void CodeGenerator::pushFinallyContext(LabelID* target, RegisterID* retAddrDst)
955 {
956     ControlFlowContext scope;
957     scope.isFinallyBlock = true;
958     FinallyContext context = { target, retAddrDst };
959     scope.finallyContext = context;
960     m_scopeContextStack.append(scope);
961     m_finallyDepth++;
962 }
963
964 void CodeGenerator::popFinallyContext()
965 {
966     ASSERT(m_scopeContextStack.size());
967     ASSERT(m_scopeContextStack.last().isFinallyBlock);
968     ASSERT(m_finallyDepth > 0);
969     m_scopeContextStack.removeLast();
970     m_finallyDepth--;
971 }
972
973 void CodeGenerator::pushJumpContext(LabelStack* labels, LabelID* continueTarget, LabelID* breakTarget, bool isValidUnlabeledBreakTarget)
974 {
975     JumpContext context = { labels, continueTarget, breakTarget, scopeDepth(), isValidUnlabeledBreakTarget };
976     m_jumpContextStack.append(context);
977     if (continueTarget)
978         m_continueDepth++;
979 }
980
981 void CodeGenerator::popJumpContext()
982 {
983     ASSERT(m_jumpContextStack.size());
984     if (m_jumpContextStack.last().continueTarget)
985         m_continueDepth--;
986     m_jumpContextStack.removeLast();
987 }
988
989 JumpContext* CodeGenerator::jumpContextForContinue(const Identifier& label)
990 {
991     if(!m_jumpContextStack.size())
992         return 0;
993
994     if (label.isEmpty()) {
995         for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
996             JumpContext* scope = &m_jumpContextStack[i];
997             if (scope->continueTarget)
998                 return scope;
999         }
1000         return 0;
1001     }
1002
1003     for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
1004         JumpContext* scope = &m_jumpContextStack[i];
1005         if (scope->labels->contains(label))
1006             return scope;
1007     }
1008     return 0;
1009 }
1010
1011 JumpContext* CodeGenerator::jumpContextForBreak(const Identifier& label)
1012 {
1013     if(!m_jumpContextStack.size())
1014         return 0;
1015
1016     if (label.isEmpty()) {
1017         for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
1018             JumpContext* scope = &m_jumpContextStack[i];
1019             if (scope->isValidUnlabeledBreakTarget)
1020                 return scope;
1021         }
1022         return 0;
1023     }
1024
1025     for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
1026         JumpContext* scope = &m_jumpContextStack[i];
1027         if (scope->labels->contains(label))
1028             return scope;
1029     }
1030     return 0;
1031 }
1032
1033 PassRefPtr<LabelID> CodeGenerator::emitComplexJumpScopes(LabelID* target, ControlFlowContext* topScope, ControlFlowContext* bottomScope)
1034 {
1035     while (topScope > bottomScope) {
1036         // First we count the number of dynamic scopes we need to remove to get
1037         // to a finally block.
1038         int nNormalScopes = 0;
1039         while (topScope > bottomScope) {
1040             if (topScope->isFinallyBlock)
1041                 break;
1042             ++nNormalScopes;
1043             --topScope;
1044         }
1045
1046         if (nNormalScopes) {
1047             // We need to remove a number of dynamic scopes to get to the next
1048             // finally block
1049             emitOpcode(op_jmp_scopes);
1050             instructions().append(nNormalScopes);
1051
1052             // If topScope == bottomScope then there isn't actually a finally block
1053             // left to emit, so make the jmp_scopes jump directly to the target label
1054             if (topScope == bottomScope) {
1055                 instructions().append(target->offsetFrom(instructions().size()));
1056                 return target;
1057             }
1058
1059             // Otherwise we just use jmp_scopes to pop a group of scopes and go
1060             // to the next instruction
1061             RefPtr<LabelID> nextInsn = newLabel();
1062             instructions().append(nextInsn->offsetFrom(instructions().size()));
1063             emitLabel(nextInsn.get());
1064         }
1065
1066         // To get here there must be at least one finally block present
1067         do {
1068             ASSERT(topScope->isFinallyBlock);
1069             emitJumpSubroutine(topScope->finallyContext.retAddrDst, topScope->finallyContext.finallyAddr);
1070             --topScope;
1071             if (!topScope->isFinallyBlock)
1072                 break;
1073         } while (topScope > bottomScope);
1074     }
1075     return emitJump(target);
1076 }
1077
1078 PassRefPtr<LabelID> CodeGenerator::emitJumpScopes(LabelID* target, int targetScopeDepth)
1079 {
1080     ASSERT(scopeDepth() - targetScopeDepth >= 0);
1081     ASSERT(target->isForwardLabel());
1082
1083     size_t scopeDelta = scopeDepth() - targetScopeDepth;
1084     ASSERT(scopeDelta <= m_scopeContextStack.size());
1085     if (!scopeDelta)
1086         return emitJump(target);
1087
1088     if (m_finallyDepth)
1089         return emitComplexJumpScopes(target, &m_scopeContextStack.last(), &m_scopeContextStack.last() - scopeDelta);
1090
1091     emitOpcode(op_jmp_scopes);
1092     instructions().append(scopeDelta);
1093     instructions().append(target->offsetFrom(instructions().size()));
1094     return target;
1095 }
1096
1097 RegisterID* CodeGenerator::emitNextPropertyName(RegisterID* dst, RegisterID* iter, LabelID* target)
1098 {
1099     emitOpcode(op_next_pname);
1100     instructions().append(dst->index());
1101     instructions().append(iter->index());
1102     instructions().append(target->offsetFrom(instructions().size()));
1103     return dst;
1104 }
1105
1106 RegisterID* CodeGenerator::emitCatch(RegisterID* targetRegister, LabelID* start, LabelID* end)
1107 {
1108     HandlerInfo info = { start->offsetFrom(0), end->offsetFrom(0), instructions().size(), m_dynamicScopeDepth };
1109     exceptionHandlers().append(info);
1110     emitOpcode(op_catch);
1111     instructions().append(targetRegister->index());
1112     return targetRegister;
1113 }
1114
1115 RegisterID* CodeGenerator::emitNewError(RegisterID* dst, ErrorType type, JSValue* message)
1116 {
1117     emitOpcode(op_new_error);
1118     instructions().append(dst->index());
1119     instructions().append(static_cast<int>(type));
1120     instructions().append(addConstant(message));
1121     return dst;
1122 }
1123
1124 PassRefPtr<LabelID> CodeGenerator::emitJumpSubroutine(RegisterID* retAddrDst, LabelID* finally)
1125 {
1126     emitOpcode(op_jsr);
1127     instructions().append(retAddrDst->index());
1128     instructions().append(finally->offsetFrom(instructions().size()));
1129     return finally;
1130 }
1131
1132 void CodeGenerator::emitSubroutineReturn(RegisterID* retAddrSrc)
1133 {
1134     emitOpcode(op_sret);
1135     instructions().append(retAddrSrc->index());
1136 }
1137
1138 } // namespace KJS