12cce6e5a8c8ba0fa39f515d98bdb3aacfe49a2a
[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 "BatchedTransitionOptimizer.h"
34 #include "JSFunction.h"
35 #include "Machine.h"
36 #include "ustring.h"
37
38 using namespace std;
39
40 namespace JSC {
41
42 /*
43     The layout of a register frame looks like this:
44
45     For
46
47     function f(x, y) {
48         var v1;
49         function g() { }
50         var v2;
51         return (x) * (y);
52     }
53
54     assuming (x) and (y) generated temporaries t1 and t2, you would have
55
56     ------------------------------------
57     |  x |  y |  g | v2 | v1 | t1 | t2 | <-- value held
58     ------------------------------------
59     | -5 | -4 | -3 | -2 | -1 | +0 | +1 | <-- register index
60     ------------------------------------
61     | params->|<-locals      | temps->
62
63     Because temporary registers are allocated in a stack-like fashion, we
64     can reclaim them with a simple popping algorithm. The same goes for labels.
65     (We never reclaim parameter or local registers, because parameters and
66     locals are DontDelete.)
67
68     The register layout before a function call looks like this:
69
70     For
71
72     function f(x, y)
73     {
74     }
75
76     f(1);
77
78     >                        <------------------------------
79     <                        >  reserved: call frame  |  1 | <-- value held
80     >         >snip<         <------------------------------
81     <                        > +0 | +1 | +2 | +3 | +4 | +5 | <-- register index
82     >                        <------------------------------
83     | params->|<-locals      | temps->
84
85     The call instruction fills in the "call frame" registers. It also pads
86     missing arguments at the end of the call:
87
88     >                        <-----------------------------------
89     <                        >  reserved: call frame  |  1 |  ? | <-- value held ("?" stands for "undefined")
90     >         >snip<         <-----------------------------------
91     <                        > +0 | +1 | +2 | +3 | +4 | +5 | +6 | <-- register index
92     >                        <-----------------------------------
93     | params->|<-locals      | temps->
94
95     After filling in missing arguments, the call instruction sets up the new
96     stack frame to overlap the end of the old stack frame:
97
98                              |---------------------------------->                        <
99                              |  reserved: call frame  |  1 |  ? <                        > <-- value held ("?" stands for "undefined")
100                              |---------------------------------->         >snip<         <
101                              | -7 | -6 | -5 | -4 | -3 | -2 | -1 <                        > <-- register index
102                              |---------------------------------->                        <
103                              |                        | params->|<-locals       | temps->
104
105     That way, arguments are "copied" into the callee's stack frame for free.
106
107     If the caller supplies too many arguments, this trick doesn't work. The
108     extra arguments protrude into space reserved for locals and temporaries.
109     In that case, the call instruction makes a real copy of the call frame header,
110     along with just the arguments expected by the callee, leaving the original
111     call frame header and arguments behind. (The call instruction can't just discard
112     extra arguments, because the "arguments" object may access them later.)
113     This copying strategy ensures that all named values will be at the indices
114     expected by the callee.
115 */
116
117 #ifndef NDEBUG
118 bool CodeGenerator::s_dumpsGeneratedCode = false;
119 #endif
120
121 void CodeGenerator::setDumpsGeneratedCode(bool dumpsGeneratedCode)
122 {
123 #ifndef NDEBUG
124     s_dumpsGeneratedCode = dumpsGeneratedCode;
125 #else
126     UNUSED_PARAM(dumpsGeneratedCode);
127 #endif
128 }
129
130 void CodeGenerator::generate()
131 {
132     m_codeBlock->numLocals = m_codeBlock->numVars + m_codeBlock->numParameters;
133     m_codeBlock->thisRegister = m_thisRegister.index();
134     if (m_shouldEmitDebugHooks)
135         m_codeBlock->needsFullScopeChain = true;
136
137     m_scopeNode->emitCode(*this);
138
139 #ifndef NDEBUG
140     if (s_dumpsGeneratedCode) {
141         JSGlobalObject* globalObject = m_scopeChain->globalObject();
142         m_codeBlock->dump(globalObject->globalExec());
143     }
144 #endif
145
146     m_scopeNode->children().shrinkCapacity(0);
147     if (m_codeType != EvalCode) { // eval code needs to hang on to its declaration stacks to keep declaration info alive until Machine::execute time.
148         m_scopeNode->varStack().shrinkCapacity(0);
149         m_scopeNode->functionStack().shrinkCapacity(0);
150     }
151 }
152
153 bool CodeGenerator::addVar(const Identifier& ident, bool isConstant, RegisterID*& r0)
154 {
155     int index = m_nextVar;
156     SymbolTableEntry newEntry(index, isConstant ? ReadOnly : 0);
157     pair<SymbolTable::iterator, bool> result = symbolTable().add(ident.ustring().rep(), newEntry);
158
159     if (!result.second)
160         index = result.first->second.getIndex();
161     else {
162         --m_nextVar;
163         ++m_codeBlock->numVars;
164
165         m_locals.append(index);
166     }
167
168     r0 = &m_locals[localsIndex(index)];
169     return result.second;
170 }
171
172 bool CodeGenerator::addGlobalVar(const Identifier& ident, bool isConstant, RegisterID*& r0)
173 {
174     int index = m_nextVar;
175     SymbolTableEntry newEntry(index, isConstant ? ReadOnly : 0);
176     pair<SymbolTable::iterator, bool> result = symbolTable().add(ident.ustring().rep(), newEntry);
177
178     if (!result.second)
179         index = result.first->second.getIndex();
180     else {
181         --m_nextVar;
182         m_locals.append(index + m_globalVarStorageOffset);
183     }
184
185     r0 = &m_locals[localsIndex(index)];
186     return result.second;
187 }
188
189 CodeGenerator::CodeGenerator(ProgramNode* programNode, const Debugger* debugger, const ScopeChain& scopeChain, SymbolTable* symbolTable, CodeBlock* codeBlock, VarStack& varStack, FunctionStack& functionStack)
190     : m_shouldEmitDebugHooks(!!debugger)
191     , m_scopeChain(&scopeChain)
192     , m_symbolTable(symbolTable)
193     , m_scopeNode(programNode)
194     , m_codeBlock(codeBlock)
195     , m_thisRegister(RegisterFile::ProgramCodeThisRegister)
196     , m_finallyDepth(0)
197     , m_dynamicScopeDepth(0)
198     , m_codeType(GlobalCode)
199     , m_continueDepth(0)
200     , m_nextVar(-1)
201     , m_globalData(&scopeChain.globalObject()->globalExec()->globalData())
202     , m_lastOpcodeID(op_end)
203 {
204     codeBlock->globalData = m_globalData;
205
206     // FIXME: Move code that modifies the global object to Machine::execute.
207     
208     m_codeBlock->numConstants = programNode->neededConstants();
209     m_codeBlock->numVars = 1; // Allocate space for "this"
210
211     JSGlobalObject* globalObject = scopeChain.globalObject();
212     ExecState* exec = globalObject->globalExec();
213     RegisterFile* registerFile = &exec->globalData().machine->registerFile();
214     
215     // Shift register indexes in generated code to elide registers allocated by intermediate stack frames.
216     m_globalVarStorageOffset = -1 - RegisterFile::CallFrameHeaderSize - registerFile->size();
217
218     // Add previously defined symbols to bookkeeping.
219     m_locals.resize(symbolTable->size());
220     SymbolTable::iterator end = symbolTable->end();
221     for (SymbolTable::iterator it = symbolTable->begin(); it != end; ++it)
222         m_locals[localsIndex(it->second.getIndex())].setIndex(it->second.getIndex() + m_globalVarStorageOffset);
223         
224     BatchedTransitionOptimizer optimizer(globalObject);
225
226     bool canOptimizeNewGlobals = symbolTable->size() + functionStack.size() + varStack.size() < registerFile->maxGlobals();
227     if (canOptimizeNewGlobals) {
228         // Shift new symbols so they get stored prior to existing symbols.
229         m_nextVar -= symbolTable->size();
230
231         for (size_t i = 0; i < functionStack.size(); ++i) {
232             FuncDeclNode* funcDecl = functionStack[i].get();
233             globalObject->removeDirect(funcDecl->m_ident); // Make sure our new function is not shadowed by an old property.
234             emitNewFunction(addGlobalVar(funcDecl->m_ident, false), funcDecl);
235         }
236
237         for (size_t i = 0; i < varStack.size(); ++i) {
238             if (!globalObject->hasProperty(exec, varStack[i].first))
239                 emitLoad(addGlobalVar(varStack[i].first, varStack[i].second & DeclarationStacks::IsConstant), jsUndefined());
240         }
241     } else {
242         for (size_t i = 0; i < functionStack.size(); ++i) {
243             FuncDeclNode* funcDecl = functionStack[i].get();
244             globalObject->putWithAttributes(exec, funcDecl->m_ident, funcDecl->makeFunction(exec, scopeChain.node()), DontDelete);
245         }
246         for (size_t i = 0; i < varStack.size(); ++i) {
247             if (globalObject->hasProperty(exec, varStack[i].first))
248                 continue;
249             int attributes = DontDelete;
250             if (varStack[i].second & DeclarationStacks::IsConstant)
251                 attributes |= ReadOnly;
252             globalObject->putWithAttributes(exec, varStack[i].first, jsUndefined(), attributes);
253         }
254     }
255 }
256
257 CodeGenerator::CodeGenerator(FunctionBodyNode* functionBody, const Debugger* debugger, const ScopeChain& scopeChain, SymbolTable* symbolTable, CodeBlock* codeBlock)
258     : m_shouldEmitDebugHooks(!!debugger)
259     , m_scopeChain(&scopeChain)
260     , m_symbolTable(symbolTable)
261     , m_scopeNode(functionBody)
262     , m_codeBlock(codeBlock)
263     , m_finallyDepth(0)
264     , m_dynamicScopeDepth(0)
265     , m_codeType(FunctionCode)
266     , m_continueDepth(0)
267     , m_nextVar(-1)
268     , m_globalData(&scopeChain.globalObject()->globalExec()->globalData())
269     , m_lastOpcodeID(op_end)
270 {
271     emitOpcode(op_initialise_locals);
272     codeBlock->globalData = m_globalData;
273
274     m_codeBlock->numConstants = functionBody->neededConstants();
275
276     const Node::FunctionStack& functionStack = functionBody->functionStack();
277     for (size_t i = 0; i < functionStack.size(); ++i) {
278         FuncDeclNode* funcDecl = functionStack[i].get();
279         const Identifier& ident = funcDecl->m_ident;
280
281         m_functions.add(ident.ustring().rep());
282         emitNewFunction(addVar(ident, false), funcDecl);
283     }
284
285     const Node::VarStack& varStack = functionBody->varStack();
286     for (size_t i = 0; i < varStack.size(); ++i) {
287         const Identifier& ident = varStack[i].first;
288         if (ident == propertyNames().arguments)
289             continue;
290         addVar(ident, varStack[i].second & DeclarationStacks::IsConstant);
291     }
292
293     Vector<Identifier>& parameters = functionBody->parameters();
294     m_nextParameter = m_nextVar - parameters.size(); // parameters are allocated prior to vars
295     m_locals.resize(localsIndex(m_nextParameter) + 1); // localsIndex of 0 => m_locals size of 1
296
297     // Add "this" as a parameter
298     m_thisRegister.setIndex(m_nextParameter);
299     ++m_nextParameter;
300     ++m_codeBlock->numParameters;
301     
302     for (size_t i = 0; i < parameters.size(); ++i)
303         addParameter(parameters[i]);
304 }
305
306 CodeGenerator::CodeGenerator(EvalNode* evalNode, const Debugger* debugger, const ScopeChain& scopeChain, SymbolTable* symbolTable, EvalCodeBlock* codeBlock)
307     : m_shouldEmitDebugHooks(!!debugger)
308     , m_scopeChain(&scopeChain)
309     , m_symbolTable(symbolTable)
310     , m_scopeNode(evalNode)
311     , m_codeBlock(codeBlock)
312     , m_thisRegister(RegisterFile::ProgramCodeThisRegister)
313     , m_finallyDepth(0)
314     , m_dynamicScopeDepth(0)
315     , m_codeType(EvalCode)
316     , m_continueDepth(0)
317     , m_globalData(&scopeChain.globalObject()->globalExec()->globalData())
318     , m_lastOpcodeID(op_end)
319 {
320     emitOpcode(op_initialise_locals);
321     codeBlock->globalData = m_globalData;
322
323     m_codeBlock->numConstants = evalNode->neededConstants();
324     m_codeBlock->numVars = 1; // Allocate space for "this"
325 }
326
327 CodeGenerator::~CodeGenerator()
328 {
329 }
330
331 RegisterID* CodeGenerator::addParameter(const Identifier& ident)
332 {
333     // Parameters overwrite var declarations, but not function declarations,
334     // in the symbol table.
335     RegisterID* result = 0;
336     UString::Rep* rep = ident.ustring().rep();
337     if (!m_functions.contains(rep)) {
338         symbolTable().set(rep, m_nextParameter);
339         m_locals[localsIndex(m_nextParameter)].setIndex(m_nextParameter);
340         result = &(m_locals[localsIndex(m_nextParameter)]);
341     }
342
343     // To maintain the calling convention, we have to allocate unique space for
344     // each parameter, even if the parameter doesn't make it into the symbol table.
345     ++m_nextParameter;
346     ++m_codeBlock->numParameters;
347     return result;
348 }
349
350 RegisterID* CodeGenerator::registerForLocal(const Identifier& ident)
351 {
352     if (m_codeType == FunctionCode && ident == propertyNames().arguments)
353         m_codeBlock->needsFullScopeChain = true;
354
355     if (ident == propertyNames().thisIdentifier)
356         return &m_thisRegister;
357
358     if (!shouldOptimizeLocals())
359         return 0;
360
361     SymbolTableEntry entry = symbolTable().get(ident.ustring().rep());
362     if (entry.isNull())
363         return 0;
364
365     return &m_locals[localsIndex(entry.getIndex())];
366 }
367
368 RegisterID* CodeGenerator::registerForLocalConstInit(const Identifier& ident)
369 {
370     if (m_codeType == EvalCode)
371         return 0;
372
373     SymbolTableEntry entry = symbolTable().get(ident.ustring().rep());
374     ASSERT(!entry.isNull());
375
376     return &m_locals[localsIndex(entry.getIndex())];
377 }
378
379 bool CodeGenerator::isLocal(const Identifier& ident)
380 {
381     if (ident == propertyNames().thisIdentifier)
382         return true;
383     
384     return shouldOptimizeLocals() && symbolTable().contains(ident.ustring().rep());
385 }
386
387 bool CodeGenerator::isLocalConstant(const Identifier& ident)
388 {
389     return symbolTable().get(ident.ustring().rep()).isReadOnly();
390 }
391
392 RegisterID* CodeGenerator::newTemporary()
393 {
394     // Reclaim free register IDs.
395     while (m_temporaries.size() && !m_temporaries.last().refCount())
396         m_temporaries.removeLast();
397
398     // Allocate new register ID.
399     m_temporaries.append(m_temporaries.size() + m_codeBlock->numConstants);
400     m_codeBlock->numTemporaries = max<int>(m_codeBlock->numTemporaries, m_temporaries.size());
401     return &m_temporaries.last();
402 }
403
404 RegisterID* CodeGenerator::highestUsedRegister()
405 {
406     while (m_temporaries.size() < static_cast<unsigned>(m_codeBlock->numTemporaries))
407         m_temporaries.append(m_temporaries.size());
408     return &m_temporaries.last();
409 }
410
411 PassRefPtr<LabelID> CodeGenerator::newLabel()
412 {
413     // Reclaim free label IDs.
414     while (m_labels.size() && !m_labels.last().refCount())
415         m_labels.removeLast();
416
417     // Allocate new label ID.
418     m_labels.append(m_codeBlock);
419     return &m_labels.last();
420 }
421
422 PassRefPtr<LabelID> CodeGenerator::emitLabel(LabelID* l0)
423 {
424     l0->setLocation(instructions().size());
425     
426     // This disables peephole optimizations when an instruction is a jump target
427     m_lastOpcodeID = op_end;
428     
429     return l0;
430 }
431
432 void CodeGenerator::emitOpcode(OpcodeID opcodeID)
433 {
434     instructions().append(globalData()->machine->getOpcode(opcodeID));
435     m_lastOpcodeID = opcodeID;
436 }
437
438 void CodeGenerator::retrieveLastBinaryOp(int& dstIndex, int& src1Index, int& src2Index)
439 {
440     ASSERT(instructions().size() >= 4);
441     size_t size = instructions().size();
442     dstIndex = instructions().at(size - 3).u.operand;
443     src1Index = instructions().at(size - 2).u.operand;
444     src2Index = instructions().at(size - 1).u.operand;
445 }
446
447 void CodeGenerator::retrieveLastUnaryOp(int& dstIndex, int& srcIndex)
448 {
449     ASSERT(instructions().size() >= 3);
450     size_t size = instructions().size();
451     dstIndex = instructions().at(size - 2).u.operand;
452     srcIndex = instructions().at(size - 1).u.operand;
453 }
454
455 void ALWAYS_INLINE CodeGenerator::rewindBinaryOp()
456 {
457     ASSERT(instructions().size() >= 4);
458     instructions().shrink(instructions().size() - 4);
459 }
460
461 void ALWAYS_INLINE CodeGenerator::rewindUnaryOp()
462 {
463     ASSERT(instructions().size() >= 3);
464     instructions().shrink(instructions().size() - 3);
465 }
466
467 PassRefPtr<LabelID> CodeGenerator::emitJump(LabelID* target)
468 {
469     emitOpcode(target->isForwardLabel() ? op_jmp : op_loop);
470     instructions().append(target->offsetFrom(instructions().size()));
471     return target;
472 }
473
474 PassRefPtr<LabelID> CodeGenerator::emitJumpIfTrue(RegisterID* cond, LabelID* target)
475 {
476     if (m_lastOpcodeID == op_less && !target->isForwardLabel()) {
477         int dstIndex;
478         int src1Index;
479         int src2Index;
480
481         retrieveLastBinaryOp(dstIndex, src1Index, src2Index);
482
483         if (cond->index() == dstIndex && cond->isTemporary() && !cond->refCount()) {
484             rewindBinaryOp();
485             emitOpcode(op_loop_if_less);
486             instructions().append(src1Index);
487             instructions().append(src2Index);
488             instructions().append(target->offsetFrom(instructions().size()));
489             return target;
490         }
491     } else if (m_lastOpcodeID == op_lesseq && !target->isForwardLabel()) {
492         int dstIndex;
493         int src1Index;
494         int src2Index;
495
496         retrieveLastBinaryOp(dstIndex, src1Index, src2Index);
497
498         if (cond->index() == dstIndex && cond->isTemporary() && !cond->refCount()) {
499             rewindBinaryOp();
500             emitOpcode(op_loop_if_lesseq);
501             instructions().append(src1Index);
502             instructions().append(src2Index);
503             instructions().append(target->offsetFrom(instructions().size()));
504             return target;
505         }
506     }
507
508     emitOpcode(target->isForwardLabel() ? op_jtrue : op_loop_if_true);
509     instructions().append(cond->index());
510     instructions().append(target->offsetFrom(instructions().size()));
511     return target;
512 }
513
514 PassRefPtr<LabelID> CodeGenerator::emitJumpIfFalse(RegisterID* cond, LabelID* target)
515 {
516     ASSERT(target->isForwardLabel());
517
518     if (m_lastOpcodeID == op_less) {
519         int dstIndex;
520         int src1Index;
521         int src2Index;
522
523         retrieveLastBinaryOp(dstIndex, src1Index, src2Index);
524
525         if (cond->index() == dstIndex && cond->isTemporary() && !cond->refCount()) {
526             rewindBinaryOp();
527             emitOpcode(op_jnless);
528             instructions().append(src1Index);
529             instructions().append(src2Index);
530             instructions().append(target->offsetFrom(instructions().size()));
531             return target;
532         }
533     } else if (m_lastOpcodeID == op_not) {
534         int dstIndex;
535         int srcIndex;
536
537         retrieveLastUnaryOp(dstIndex, srcIndex);
538
539         if (cond->index() == dstIndex && cond->isTemporary() && !cond->refCount()) {
540             rewindUnaryOp();
541             emitOpcode(target->isForwardLabel() ? op_jtrue : op_loop_if_true);
542             instructions().append(srcIndex);
543             instructions().append(target->offsetFrom(instructions().size()));
544             return target;
545         }        
546     }
547
548     emitOpcode(op_jfalse);
549     instructions().append(cond->index());
550     instructions().append(target->offsetFrom(instructions().size()));
551     return target;
552 }
553
554 unsigned CodeGenerator::addConstant(FuncDeclNode* n)
555 {
556     // No need to explicitly unique function body nodes -- they're unique already.
557     int index = m_codeBlock->functions.size();
558     m_codeBlock->functions.append(n);
559     return index;
560 }
561
562 unsigned CodeGenerator::addConstant(FuncExprNode* n)
563 {
564     // No need to explicitly unique function expression nodes -- they're unique already.
565     int index = m_codeBlock->functionExpressions.size();
566     m_codeBlock->functionExpressions.append(n);
567     return index;
568 }
569
570 unsigned CodeGenerator::addConstant(const Identifier& ident)
571 {
572     UString::Rep* rep = ident.ustring().rep();
573     pair<IdentifierMap::iterator, bool> result = m_identifierMap.add(rep, m_codeBlock->identifiers.size());
574     if (result.second) // new entry
575         m_codeBlock->identifiers.append(Identifier(m_globalData, rep));
576
577     return result.first->second;
578 }
579
580 RegisterID* CodeGenerator::addConstant(JSValue* v)
581 {
582     pair<JSValueMap::iterator, bool> result = m_jsValueMap.add(v, m_codeBlock->constantRegisters.size());
583     if (result.second) {
584         m_constants.append(m_codeBlock->constantRegisters.size());
585         m_constants.last().makeConstant();
586         m_codeBlock->constantRegisters.append(v);
587         ASSERT(m_codeBlock->constantRegisters.size() <= (unsigned) m_codeBlock->numConstants);
588         return &m_constants.last();
589     }
590
591     return &m_constants[result.first->second];
592 }
593
594 unsigned CodeGenerator::addUnexpectedConstant(JSValue* v)
595 {
596     int index = m_codeBlock->unexpectedConstants.size();
597     m_codeBlock->unexpectedConstants.append(v);
598     return index;
599 }
600
601 unsigned CodeGenerator::addRegExp(RegExp* r)
602 {
603     int index = m_codeBlock->regexps.size();
604     m_codeBlock->regexps.append(r);
605     return index;
606 }
607
608 RegisterID* CodeGenerator::emitMove(RegisterID* dst, RegisterID* src)
609 {
610     emitOpcode(op_mov);
611     instructions().append(dst->index());
612     instructions().append(src->index());
613     return dst;
614 }
615
616 RegisterID* CodeGenerator::emitUnaryOp(OpcodeID opcode, RegisterID* dst, RegisterID* src)
617 {
618     emitOpcode(opcode);
619     instructions().append(dst->index());
620     instructions().append(src->index());
621     return dst;
622 }
623
624 RegisterID* CodeGenerator::emitPreInc(RegisterID* srcDst)
625 {
626     emitOpcode(op_pre_inc);
627     instructions().append(srcDst->index());
628     return srcDst;
629 }
630
631 RegisterID* CodeGenerator::emitPreDec(RegisterID* srcDst)
632 {
633     emitOpcode(op_pre_dec);
634     instructions().append(srcDst->index());
635     return srcDst;
636 }
637
638 RegisterID* CodeGenerator::emitPostInc(RegisterID* dst, RegisterID* srcDst)
639 {
640     emitOpcode(op_post_inc);
641     instructions().append(dst->index());
642     instructions().append(srcDst->index());
643     return dst;
644 }
645
646 RegisterID* CodeGenerator::emitPostDec(RegisterID* dst, RegisterID* srcDst)
647 {
648     emitOpcode(op_post_dec);
649     instructions().append(dst->index());
650     instructions().append(srcDst->index());
651     return dst;
652 }
653
654 RegisterID* CodeGenerator::emitBinaryOp(OpcodeID opcode, RegisterID* dst, RegisterID* src1, RegisterID* src2)
655 {
656     emitOpcode(opcode);
657     instructions().append(dst->index());
658     instructions().append(src1->index());
659     instructions().append(src2->index());
660     return dst;
661 }
662
663 RegisterID* CodeGenerator::emitEqualityOp(OpcodeID opcode, RegisterID* dst, RegisterID* src1, RegisterID* src2)
664 {
665     if (m_lastOpcodeID == op_typeof) {
666         int dstIndex;
667         int srcIndex;
668
669         retrieveLastUnaryOp(dstIndex, srcIndex);
670
671         if (src1->index() == dstIndex
672             && src1->isTemporary()
673             && static_cast<unsigned>(src2->index()) < m_codeBlock->constantRegisters.size()
674             && m_codeBlock->constantRegisters[src2->index()].jsValue(globalExec())->isString()) {
675             const UString& value = static_cast<JSString*>(m_codeBlock->constantRegisters[src2->index()].jsValue(globalExec()))->value();
676             if (value == "undefined") {
677                 rewindUnaryOp();
678                 emitOpcode(op_is_undefined);
679                 instructions().append(dst->index());
680                 instructions().append(srcIndex);
681                 return dst;
682             }
683             if (value == "boolean") {
684                 rewindUnaryOp();
685                 emitOpcode(op_is_boolean);
686                 instructions().append(dst->index());
687                 instructions().append(srcIndex);
688                 return dst;
689             }
690             if (value == "number") {
691                 rewindUnaryOp();
692                 emitOpcode(op_is_number);
693                 instructions().append(dst->index());
694                 instructions().append(srcIndex);
695                 return dst;
696             }
697             if (value == "string") {
698                 rewindUnaryOp();
699                 emitOpcode(op_is_string);
700                 instructions().append(dst->index());
701                 instructions().append(srcIndex);
702                 return dst;
703             }
704             if (value == "object") {
705                 rewindUnaryOp();
706                 emitOpcode(op_is_object);
707                 instructions().append(dst->index());
708                 instructions().append(srcIndex);
709                 return dst;
710             }
711             if (value == "function") {
712                 rewindUnaryOp();
713                 emitOpcode(op_is_function);
714                 instructions().append(dst->index());
715                 instructions().append(srcIndex);
716                 return dst;
717             }
718         }
719     }
720
721     emitOpcode(opcode);
722     instructions().append(dst->index());
723     instructions().append(src1->index());
724     instructions().append(src2->index());
725     return dst;
726 }
727
728 RegisterID* CodeGenerator::emitLoad(RegisterID* dst, bool b)
729 {
730     return emitLoad(dst, jsBoolean(b));
731 }
732
733 RegisterID* CodeGenerator::emitLoad(RegisterID* dst, double number)
734 {
735     // FIXME: Our hash tables won't hold infinity, so we make a new JSNumberCell each time.
736     // Later we can do the extra work to handle that like the other cases.
737     if (number == HashTraits<double>::emptyValue() || HashTraits<double>::isDeletedValue(number))
738         return emitLoad(dst, jsNumber(globalExec(), number));
739     JSValue*& valueInMap = m_numberMap.add(number, 0).first->second;
740     if (!valueInMap)
741         valueInMap = jsNumber(globalExec(), number);
742     return emitLoad(dst, valueInMap);
743 }
744
745 RegisterID* CodeGenerator::emitLoad(RegisterID* dst, const Identifier& identifier)
746 {
747     JSString*& valueInMap = m_stringMap.add(identifier.ustring().rep(), 0).first->second;
748     if (!valueInMap)
749         valueInMap = jsOwnedString(globalExec(), identifier.ustring());
750     return emitLoad(dst, valueInMap);
751 }
752
753 RegisterID* CodeGenerator::emitLoad(RegisterID* dst, JSValue* v)
754 {
755     RegisterID* constantID = addConstant(v);
756     if (dst)
757         return emitMove(dst, constantID);
758     return constantID;
759 }
760
761 RegisterID* CodeGenerator::emitUnexpectedLoad(RegisterID* dst, bool b)
762 {
763     emitOpcode(op_unexpected_load);
764     instructions().append(dst->index());
765     instructions().append(addUnexpectedConstant(jsBoolean(b)));
766     return dst;
767 }
768
769 RegisterID* CodeGenerator::emitUnexpectedLoad(RegisterID* dst, double d)
770 {
771     emitOpcode(op_unexpected_load);
772     instructions().append(dst->index());
773     instructions().append(addUnexpectedConstant(jsNumber(globalExec(), d)));
774     return dst;
775 }
776
777 bool CodeGenerator::findScopedProperty(const Identifier& property, int& index, size_t& stackDepth, bool forWriting, JSValue*& globalObject)
778 {
779     // Cases where we cannot statically optimise the lookup
780     if (property == propertyNames().arguments || !canOptimizeNonLocals()) {
781         stackDepth = 0;
782         index = missingSymbolMarker();
783
784         if (shouldOptimizeLocals() && m_codeType == GlobalCode) {
785             ScopeChainIterator iter = m_scopeChain->begin();
786             globalObject = *iter;
787             ASSERT((++iter) == m_scopeChain->end());
788         }
789         return false;
790     }
791
792     size_t depth = 0;
793     
794     ScopeChainIterator iter = m_scopeChain->begin();
795     ScopeChainIterator end = m_scopeChain->end();
796     for (; iter != end; ++iter, ++depth) {
797         JSObject* currentScope = *iter;
798         if (!currentScope->isVariableObject())
799             break;
800         JSVariableObject* currentVariableObject = static_cast<JSVariableObject*>(currentScope);
801         SymbolTableEntry entry = currentVariableObject->symbolTable().get(property.ustring().rep());
802
803         // Found the property
804         if (!entry.isNull()) {
805             if (entry.isReadOnly() && forWriting) {
806                 stackDepth = 0;
807                 index = missingSymbolMarker();
808                 if (++iter == end)
809                     globalObject = currentVariableObject;
810                 return false;
811             }
812             stackDepth = depth;
813             index = entry.getIndex();
814             if (++iter == end)
815                 globalObject = currentVariableObject;
816             return true;
817         }
818         if (currentVariableObject->isDynamicScope())
819             break;
820     }
821
822     // Can't locate the property but we're able to avoid a few lookups
823     stackDepth = depth;
824     index = missingSymbolMarker();
825     JSObject* scope = *iter;
826     if (++iter == end)
827         globalObject = scope;
828     return true;
829 }
830
831 RegisterID* CodeGenerator::emitInstanceOf(RegisterID* dst, RegisterID* value, RegisterID* base, RegisterID* basePrototype)
832
833     emitOpcode(op_instanceof);
834     instructions().append(dst->index());
835     instructions().append(value->index());
836     instructions().append(base->index());
837     instructions().append(basePrototype->index());
838     return dst;
839 }
840
841 RegisterID* CodeGenerator::emitResolve(RegisterID* dst, const Identifier& property)
842 {
843     size_t depth = 0;
844     int index = 0;
845     JSValue* globalObject = 0;
846     if (!findScopedProperty(property, index, depth, false, globalObject) && !globalObject) {
847         // We can't optimise at all :-(
848         emitOpcode(op_resolve);
849         instructions().append(dst->index());
850         instructions().append(addConstant(property));
851         return dst;
852     }
853
854     if (index != missingSymbolMarker()) {
855         // Directly index the property lookup across multiple scopes.  Yay!
856         return emitGetScopedVar(dst, depth, index, globalObject);
857     }
858
859     if (globalObject) {
860         m_codeBlock->structureIDInstructions.append(instructions().size());
861         emitOpcode(op_resolve_global);
862         instructions().append(dst->index());
863         instructions().append(static_cast<JSCell*>(globalObject));
864         instructions().append(addConstant(property));
865         instructions().append(0);
866         instructions().append(0);
867         return dst;
868     }
869
870     // In this case we are at least able to drop a few scope chains from the
871     // lookup chain, although we still need to hash from then on.
872     emitOpcode(op_resolve_skip);
873     instructions().append(dst->index());
874     instructions().append(addConstant(property));
875     instructions().append(depth);
876     return dst;
877 }
878
879 RegisterID* CodeGenerator::emitGetScopedVar(RegisterID* dst, size_t depth, int index, JSValue* globalObject)
880 {
881     if (globalObject) {
882         emitOpcode(op_get_global_var);
883         instructions().append(dst->index());
884         instructions().append(static_cast<JSCell*>(globalObject));
885         instructions().append(index);
886         return dst;
887     }
888
889     emitOpcode(op_get_scoped_var);
890     instructions().append(dst->index());
891     instructions().append(index);
892     instructions().append(depth);
893     return dst;
894 }
895
896 RegisterID* CodeGenerator::emitPutScopedVar(size_t depth, int index, RegisterID* value, JSValue* globalObject)
897 {
898     if (globalObject) {
899         emitOpcode(op_put_global_var);
900         instructions().append(static_cast<JSCell*>(globalObject));
901         instructions().append(index);
902         instructions().append(value->index());
903         return value;
904     }
905     emitOpcode(op_put_scoped_var);
906     instructions().append(index);
907     instructions().append(depth);
908     instructions().append(value->index());
909     return value;
910 }
911
912 RegisterID* CodeGenerator::emitResolveBase(RegisterID* dst, const Identifier& property)
913 {
914     emitOpcode(op_resolve_base);
915     instructions().append(dst->index());
916     instructions().append(addConstant(property));
917     return dst;
918 }
919
920 RegisterID* CodeGenerator::emitResolveWithBase(RegisterID* baseDst, RegisterID* propDst, const Identifier& property)
921 {
922     emitOpcode(op_resolve_with_base);
923     instructions().append(baseDst->index());
924     instructions().append(propDst->index());
925     instructions().append(addConstant(property));
926     return baseDst;
927 }
928
929 RegisterID* CodeGenerator::emitResolveFunction(RegisterID* baseDst, RegisterID* funcDst, const Identifier& property)
930 {
931     emitOpcode(op_resolve_func);
932     instructions().append(baseDst->index());
933     instructions().append(funcDst->index());
934     instructions().append(addConstant(property));
935     return baseDst;
936 }
937
938 RegisterID* CodeGenerator::emitGetById(RegisterID* dst, RegisterID* base, const Identifier& property)
939 {
940     m_codeBlock->structureIDInstructions.append(instructions().size());
941
942     emitOpcode(op_get_by_id);
943     instructions().append(dst->index());
944     instructions().append(base->index());
945     instructions().append(addConstant(property));
946     instructions().append(0);
947     instructions().append(0);
948     instructions().append(0);
949     instructions().append(0);
950     return dst;
951 }
952
953 RegisterID* CodeGenerator::emitPutById(RegisterID* base, const Identifier& property, RegisterID* value)
954 {
955     m_codeBlock->structureIDInstructions.append(instructions().size());
956
957     emitOpcode(op_put_by_id);
958     instructions().append(base->index());
959     instructions().append(addConstant(property));
960     instructions().append(value->index());
961     instructions().append(0);
962     instructions().append(0);
963     instructions().append(0);
964     instructions().append(0);
965     return value;
966 }
967
968 RegisterID* CodeGenerator::emitPutGetter(RegisterID* base, const Identifier& property, RegisterID* value)
969 {
970     emitOpcode(op_put_getter);
971     instructions().append(base->index());
972     instructions().append(addConstant(property));
973     instructions().append(value->index());
974     return value;
975 }
976
977 RegisterID* CodeGenerator::emitPutSetter(RegisterID* base, const Identifier& property, RegisterID* value)
978 {
979     emitOpcode(op_put_setter);
980     instructions().append(base->index());
981     instructions().append(addConstant(property));
982     instructions().append(value->index());
983     return value;
984 }
985
986 RegisterID* CodeGenerator::emitDeleteById(RegisterID* dst, RegisterID* base, const Identifier& property)
987 {
988     emitOpcode(op_del_by_id);
989     instructions().append(dst->index());
990     instructions().append(base->index());
991     instructions().append(addConstant(property));
992     return dst;
993 }
994
995 RegisterID* CodeGenerator::emitGetByVal(RegisterID* dst, RegisterID* base, RegisterID* property)
996 {
997     emitOpcode(op_get_by_val);
998     instructions().append(dst->index());
999     instructions().append(base->index());
1000     instructions().append(property->index());
1001     return dst;
1002 }
1003
1004 RegisterID* CodeGenerator::emitPutByVal(RegisterID* base, RegisterID* property, RegisterID* value)
1005 {
1006     emitOpcode(op_put_by_val);
1007     instructions().append(base->index());
1008     instructions().append(property->index());
1009     instructions().append(value->index());
1010     return value;
1011 }
1012
1013 RegisterID* CodeGenerator::emitDeleteByVal(RegisterID* dst, RegisterID* base, RegisterID* property)
1014 {
1015     emitOpcode(op_del_by_val);
1016     instructions().append(dst->index());
1017     instructions().append(base->index());
1018     instructions().append(property->index());
1019     return dst;
1020 }
1021
1022 RegisterID* CodeGenerator::emitPutByIndex(RegisterID* base, unsigned index, RegisterID* value)
1023 {
1024     emitOpcode(op_put_by_index);
1025     instructions().append(base->index());
1026     instructions().append(index);
1027     instructions().append(value->index());
1028     return value;
1029 }
1030
1031 RegisterID* CodeGenerator::emitNewObject(RegisterID* dst)
1032 {
1033     emitOpcode(op_new_object);
1034     instructions().append(dst->index());
1035     return dst;
1036 }
1037
1038 RegisterID* CodeGenerator::emitNewArray(RegisterID* dst, ElementNode* elements)
1039 {
1040     Vector<RefPtr<RegisterID>, 16> argv;
1041     for (ElementNode* n = elements; n; n = n->next()) {
1042         if (n->elision())
1043             break;
1044         argv.append(newTemporary());
1045         emitNode(argv.last().get(), n->value());
1046     }
1047     emitOpcode(op_new_array);
1048     instructions().append(dst->index());
1049     instructions().append(argv.size() ? argv[0]->index() : 0); // argv
1050     instructions().append(argv.size()); // argc
1051     return dst;
1052 }
1053
1054 RegisterID* CodeGenerator::emitNewFunction(RegisterID* dst, FuncDeclNode* n)
1055 {
1056     emitOpcode(op_new_func);
1057     instructions().append(dst->index());
1058     instructions().append(addConstant(n));
1059     return dst;
1060 }
1061
1062 RegisterID* CodeGenerator::emitNewRegExp(RegisterID* dst, RegExp* regExp)
1063 {
1064     emitOpcode(op_new_regexp);
1065     instructions().append(dst->index());
1066     instructions().append(addRegExp(regExp));
1067     return dst;
1068 }
1069
1070
1071 RegisterID* CodeGenerator::emitNewFunctionExpression(RegisterID* r0, FuncExprNode* n)
1072 {
1073     emitOpcode(op_new_func_exp);
1074     instructions().append(r0->index());
1075     instructions().append(addConstant(n));
1076     return r0;
1077 }
1078
1079 RegisterID* CodeGenerator::emitCall(RegisterID* dst, RegisterID* func, RegisterID* base, ArgumentsNode* argumentsNode, unsigned divot, unsigned startOffset, unsigned endOffset)
1080 {
1081     return emitCall(op_call, dst, func, base, argumentsNode, divot, startOffset, endOffset);
1082 }
1083
1084 RegisterID* CodeGenerator::emitCallEval(RegisterID* dst, RegisterID* func, RegisterID* base, ArgumentsNode* argumentsNode, unsigned divot, unsigned startOffset, unsigned endOffset)
1085 {
1086     return emitCall(op_call_eval, dst, func, base, argumentsNode, divot, startOffset, endOffset);
1087 }
1088
1089 RegisterID* CodeGenerator::emitCall(OpcodeID opcodeID, RegisterID* dst, RegisterID* func, RegisterID* base, ArgumentsNode* argumentsNode, unsigned divot, unsigned startOffset, unsigned endOffset)
1090 {
1091     ASSERT(opcodeID == op_call || opcodeID == op_call_eval);
1092     
1093     // Ordinarily, we might ref "func" and "base", to avoid allocating new
1094     // temporaries in the same registers. In this case, though, we actually
1095     // want the call frame we allocate to overlap "func" and "base", if they're
1096     // not otherwise referenced. op_call will read "func" and "base" before
1097     // writing out the call frame, so this is safe.
1098
1099     // Reserve space for call frame.
1100     Vector<RefPtr<RegisterID>, RegisterFile::CallFrameHeaderSize> callFrame;
1101     for (int i = 0; i < RegisterFile::CallFrameHeaderSize; ++i)
1102         callFrame.append(newTemporary());
1103
1104     // Generate code for arguments.
1105     Vector<RefPtr<RegisterID>, 16> argv;
1106     argv.append(newTemporary()); // reserve space for "this"
1107     for (ArgumentListNode* n = argumentsNode->m_listNode.get(); n; n = n->m_next.get()) {
1108         argv.append(newTemporary());
1109         emitNode(argv.last().get(), n);
1110     }
1111
1112     emitExpressionInfo(divot, startOffset, endOffset);
1113     emitOpcode(opcodeID);
1114     instructions().append(dst->index());
1115     instructions().append(func->index());
1116     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.
1117     instructions().append(argv[0]->index()); // argv
1118     instructions().append(argv.size()); // argc
1119     return dst;
1120 }
1121
1122 RegisterID* CodeGenerator::emitUnaryNoDstOp(OpcodeID opcode, RegisterID* src)
1123 {
1124     emitOpcode(opcode);
1125     instructions().append(src->index());
1126     return src;
1127 }
1128
1129 RegisterID* CodeGenerator::emitConstruct(RegisterID* dst, RegisterID* func, ArgumentsNode* argumentsNode, unsigned divot, unsigned startOffset, unsigned endOffset)
1130 {
1131     ASSERT(func->refCount());
1132
1133     // Reserve space for prototype
1134     RefPtr<RegisterID> funcProto = newTemporary();
1135
1136     // Reserve space for call frame.
1137     Vector<RefPtr<RegisterID>, RegisterFile::CallFrameHeaderSize> callFrame;
1138     for (int i = 0; i < RegisterFile::CallFrameHeaderSize; ++i)
1139         callFrame.append(newTemporary());
1140
1141     // Generate code for arguments.
1142     Vector<RefPtr<RegisterID>, 16> argv;
1143     argv.append(newTemporary()); // reserve space for "this"
1144     for (ArgumentListNode* n = argumentsNode ? argumentsNode->m_listNode.get() : 0; n; n = n->m_next.get()) {
1145         argv.append(newTemporary());
1146         emitNode(argv.last().get(), n);
1147     }
1148
1149     emitExpressionInfo(divot, startOffset, endOffset);
1150     emitGetById(funcProto.get(), func, globalExec()->propertyNames().prototype);
1151
1152     emitExpressionInfo(divot, startOffset, endOffset);
1153     emitOpcode(op_construct);
1154     instructions().append(dst->index());
1155     instructions().append(func->index());
1156     instructions().append(funcProto->index());
1157     instructions().append(argv[0]->index()); // argv
1158     instructions().append(argv.size()); // argc
1159     
1160     emitOpcode(op_construct_verify);
1161     instructions().append(dst->index());
1162     instructions().append(argv[0]->index());
1163
1164     return dst;
1165 }
1166
1167 RegisterID* CodeGenerator::emitPushScope(RegisterID* scope)
1168 {
1169     m_codeBlock->needsFullScopeChain = true;
1170     ControlFlowContext context;
1171     context.isFinallyBlock = false;
1172     m_scopeContextStack.append(context);
1173     m_dynamicScopeDepth++;
1174
1175     return emitUnaryNoDstOp(op_push_scope, scope);
1176 }
1177
1178 void CodeGenerator::emitPopScope()
1179 {
1180     ASSERT(m_scopeContextStack.size());
1181     ASSERT(!m_scopeContextStack.last().isFinallyBlock);
1182
1183     emitOpcode(op_pop_scope);
1184
1185     m_scopeContextStack.removeLast();
1186     m_dynamicScopeDepth--;
1187 }
1188
1189 void CodeGenerator::emitDebugHook(DebugHookID debugHookID, int firstLine, int lastLine)
1190 {
1191     if (!m_shouldEmitDebugHooks)
1192         return;
1193     emitOpcode(op_debug);
1194     instructions().append(debugHookID);
1195     instructions().append(firstLine);
1196     instructions().append(lastLine);
1197 }
1198
1199 void CodeGenerator::pushFinallyContext(LabelID* target, RegisterID* retAddrDst)
1200 {
1201     ControlFlowContext scope;
1202     scope.isFinallyBlock = true;
1203     FinallyContext context = { target, retAddrDst };
1204     scope.finallyContext = context;
1205     m_scopeContextStack.append(scope);
1206     m_finallyDepth++;
1207 }
1208
1209 void CodeGenerator::popFinallyContext()
1210 {
1211     ASSERT(m_scopeContextStack.size());
1212     ASSERT(m_scopeContextStack.last().isFinallyBlock);
1213     ASSERT(m_finallyDepth > 0);
1214     m_scopeContextStack.removeLast();
1215     m_finallyDepth--;
1216 }
1217
1218 void CodeGenerator::pushJumpContext(LabelStack* labels, LabelID* continueTarget, LabelID* breakTarget, bool isValidUnlabeledBreakTarget)
1219 {
1220     JumpContext context = { labels, continueTarget, breakTarget, scopeDepth(), isValidUnlabeledBreakTarget };
1221     m_jumpContextStack.append(context);
1222     if (continueTarget)
1223         m_continueDepth++;
1224 }
1225
1226 void CodeGenerator::popJumpContext()
1227 {
1228     ASSERT(m_jumpContextStack.size());
1229     if (m_jumpContextStack.last().continueTarget)
1230         m_continueDepth--;
1231     m_jumpContextStack.removeLast();
1232 }
1233
1234 JumpContext* CodeGenerator::jumpContextForContinue(const Identifier& label)
1235 {
1236     if(!m_jumpContextStack.size())
1237         return 0;
1238
1239     if (label.isEmpty()) {
1240         for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
1241             JumpContext* scope = &m_jumpContextStack[i];
1242             if (scope->continueTarget)
1243                 return scope;
1244         }
1245         return 0;
1246     }
1247
1248     for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
1249         JumpContext* scope = &m_jumpContextStack[i];
1250         if (scope->labels->contains(label))
1251             return scope;
1252     }
1253     return 0;
1254 }
1255
1256 JumpContext* CodeGenerator::jumpContextForBreak(const Identifier& label)
1257 {
1258     if(!m_jumpContextStack.size())
1259         return 0;
1260
1261     if (label.isEmpty()) {
1262         for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
1263             JumpContext* scope = &m_jumpContextStack[i];
1264             if (scope->isValidUnlabeledBreakTarget)
1265                 return scope;
1266         }
1267         return 0;
1268     }
1269
1270     for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
1271         JumpContext* scope = &m_jumpContextStack[i];
1272         if (scope->labels->contains(label))
1273             return scope;
1274     }
1275     return 0;
1276 }
1277
1278 PassRefPtr<LabelID> CodeGenerator::emitComplexJumpScopes(LabelID* target, ControlFlowContext* topScope, ControlFlowContext* bottomScope)
1279 {
1280     while (topScope > bottomScope) {
1281         // First we count the number of dynamic scopes we need to remove to get
1282         // to a finally block.
1283         int nNormalScopes = 0;
1284         while (topScope > bottomScope) {
1285             if (topScope->isFinallyBlock)
1286                 break;
1287             ++nNormalScopes;
1288             --topScope;
1289         }
1290
1291         if (nNormalScopes) {
1292             // We need to remove a number of dynamic scopes to get to the next
1293             // finally block
1294             emitOpcode(op_jmp_scopes);
1295             instructions().append(nNormalScopes);
1296
1297             // If topScope == bottomScope then there isn't actually a finally block
1298             // left to emit, so make the jmp_scopes jump directly to the target label
1299             if (topScope == bottomScope) {
1300                 instructions().append(target->offsetFrom(instructions().size()));
1301                 return target;
1302             }
1303
1304             // Otherwise we just use jmp_scopes to pop a group of scopes and go
1305             // to the next instruction
1306             RefPtr<LabelID> nextInsn = newLabel();
1307             instructions().append(nextInsn->offsetFrom(instructions().size()));
1308             emitLabel(nextInsn.get());
1309         }
1310
1311         // To get here there must be at least one finally block present
1312         do {
1313             ASSERT(topScope->isFinallyBlock);
1314             emitJumpSubroutine(topScope->finallyContext.retAddrDst, topScope->finallyContext.finallyAddr);
1315             --topScope;
1316             if (!topScope->isFinallyBlock)
1317                 break;
1318         } while (topScope > bottomScope);
1319     }
1320     return emitJump(target);
1321 }
1322
1323 PassRefPtr<LabelID> CodeGenerator::emitJumpScopes(LabelID* target, int targetScopeDepth)
1324 {
1325     ASSERT(scopeDepth() - targetScopeDepth >= 0);
1326     ASSERT(target->isForwardLabel());
1327
1328     size_t scopeDelta = scopeDepth() - targetScopeDepth;
1329     ASSERT(scopeDelta <= m_scopeContextStack.size());
1330     if (!scopeDelta)
1331         return emitJump(target);
1332
1333     if (m_finallyDepth)
1334         return emitComplexJumpScopes(target, &m_scopeContextStack.last(), &m_scopeContextStack.last() - scopeDelta);
1335
1336     emitOpcode(op_jmp_scopes);
1337     instructions().append(scopeDelta);
1338     instructions().append(target->offsetFrom(instructions().size()));
1339     return target;
1340 }
1341
1342 RegisterID* CodeGenerator::emitNextPropertyName(RegisterID* dst, RegisterID* iter, LabelID* target)
1343 {
1344     emitOpcode(op_next_pname);
1345     instructions().append(dst->index());
1346     instructions().append(iter->index());
1347     instructions().append(target->offsetFrom(instructions().size()));
1348     return dst;
1349 }
1350
1351 RegisterID* CodeGenerator::emitCatch(RegisterID* targetRegister, LabelID* start, LabelID* end)
1352 {
1353     HandlerInfo info = { start->offsetFrom(0), end->offsetFrom(0), instructions().size(), m_dynamicScopeDepth, 0 };
1354     exceptionHandlers().append(info);
1355     emitOpcode(op_catch);
1356     instructions().append(targetRegister->index());
1357     return targetRegister;
1358 }
1359
1360 RegisterID* CodeGenerator::emitNewError(RegisterID* dst, ErrorType type, JSValue* message)
1361 {
1362     emitOpcode(op_new_error);
1363     instructions().append(dst->index());
1364     instructions().append(static_cast<int>(type));
1365     instructions().append(addUnexpectedConstant(message));
1366     return dst;
1367 }
1368
1369 PassRefPtr<LabelID> CodeGenerator::emitJumpSubroutine(RegisterID* retAddrDst, LabelID* finally)
1370 {
1371     emitOpcode(op_jsr);
1372     instructions().append(retAddrDst->index());
1373     instructions().append(finally->offsetFrom(instructions().size()));
1374     return finally;
1375 }
1376
1377 void CodeGenerator::emitSubroutineReturn(RegisterID* retAddrSrc)
1378 {
1379     emitOpcode(op_sret);
1380     instructions().append(retAddrSrc->index());
1381 }
1382
1383 void CodeGenerator::emitPushNewScope(RegisterID* dst, Identifier& property, RegisterID* value)
1384 {
1385     m_codeBlock->needsFullScopeChain = true;
1386     ControlFlowContext context;
1387     context.isFinallyBlock = false;
1388     m_scopeContextStack.append(context);
1389     m_dynamicScopeDepth++;
1390     
1391     emitOpcode(op_push_new_scope);
1392     instructions().append(dst->index());
1393     instructions().append(addConstant(property));
1394     instructions().append(value->index());
1395 }
1396
1397 void CodeGenerator::beginSwitch(RegisterID* scrutineeRegister, SwitchInfo::SwitchType type)
1398 {
1399     SwitchInfo info = { instructions().size(), type };
1400     switch (type) {
1401         case SwitchInfo::SwitchImmediate:
1402             emitOpcode(op_switch_imm);
1403             break;
1404         case SwitchInfo::SwitchCharacter:
1405             emitOpcode(op_switch_char);
1406             break;
1407         case SwitchInfo::SwitchString:
1408             emitOpcode(op_switch_string);
1409             break;
1410         default:
1411             ASSERT_NOT_REACHED();
1412     }
1413
1414     instructions().append(0); // place holder for table index
1415     instructions().append(0); // place holder for default target    
1416     instructions().append(scrutineeRegister->index());
1417     m_switchContextStack.append(info);
1418 }
1419
1420 static int32_t keyForImmediateSwitch(ExpressionNode* node, int32_t min, int32_t max)
1421 {
1422     UNUSED_PARAM(max);
1423     ASSERT(node->isNumber());
1424     double value = static_cast<NumberNode*>(node)->value();
1425     ASSERT(JSImmediate::from(value));
1426     int32_t key = static_cast<int32_t>(value);
1427     ASSERT(key == value);
1428     ASSERT(key >= min);
1429     ASSERT(key <= max);
1430     return key - min;
1431 }
1432
1433 static void prepareJumpTableForImmediateSwitch(SimpleJumpTable& jumpTable, int32_t switchAddress, uint32_t clauseCount, RefPtr<LabelID>* labels, ExpressionNode** nodes, int32_t min, int32_t max)
1434 {
1435     jumpTable.min = min;
1436     jumpTable.branchOffsets.resize(max - min + 1);
1437     jumpTable.branchOffsets.fill(0);
1438     for (uint32_t i = 0; i < clauseCount; ++i) {
1439         // We're emitting this after the clause labels should have been fixed, so 
1440         // the labels should not be "forward" references
1441         ASSERT(!labels[i]->isForwardLabel());
1442         jumpTable.add(keyForImmediateSwitch(nodes[i], min, max), labels[i]->offsetFrom(switchAddress)); 
1443     }
1444 }
1445
1446 static int32_t keyForCharacterSwitch(ExpressionNode* node, int32_t min, int32_t max)
1447 {
1448     UNUSED_PARAM(max);
1449     ASSERT(node->isString());
1450     UString::Rep* clause = static_cast<StringNode*>(node)->value().ustring().rep();
1451     ASSERT(clause->size() == 1);
1452     
1453     int32_t key = clause->data()[0];
1454     ASSERT(key >= min);
1455     ASSERT(key <= max);
1456     return key - min;
1457 }
1458
1459 static void prepareJumpTableForCharacterSwitch(SimpleJumpTable& jumpTable, int32_t switchAddress, uint32_t clauseCount, RefPtr<LabelID>* labels, ExpressionNode** nodes, int32_t min, int32_t max)
1460 {
1461     jumpTable.min = min;
1462     jumpTable.branchOffsets.resize(max - min + 1);
1463     jumpTable.branchOffsets.fill(0);
1464     for (uint32_t i = 0; i < clauseCount; ++i) {
1465         // We're emitting this after the clause labels should have been fixed, so 
1466         // the labels should not be "forward" references
1467         ASSERT(!labels[i]->isForwardLabel());
1468         jumpTable.add(keyForCharacterSwitch(nodes[i], min, max), labels[i]->offsetFrom(switchAddress)); 
1469     }
1470 }
1471
1472 static void prepareJumpTableForStringSwitch(StringJumpTable& jumpTable, int32_t switchAddress, uint32_t clauseCount, RefPtr<LabelID>* labels, ExpressionNode** nodes)
1473 {
1474     for (uint32_t i = 0; i < clauseCount; ++i) {
1475         // We're emitting this after the clause labels should have been fixed, so 
1476         // the labels should not be "forward" references
1477         ASSERT(!labels[i]->isForwardLabel());
1478         
1479         ASSERT(nodes[i]->isString());
1480         UString::Rep* clause = static_cast<StringNode*>(nodes[i])->value().ustring().rep();
1481         OffsetLocation location;
1482         location.branchOffset = labels[i]->offsetFrom(switchAddress);
1483 #if ENABLE(CTI)
1484         location.ctiOffset = 0;
1485 #endif
1486         jumpTable.offsetTable.add(clause, location);
1487     }
1488 }
1489
1490 void CodeGenerator::endSwitch(uint32_t clauseCount, RefPtr<LabelID>* labels, ExpressionNode** nodes, LabelID* defaultLabel, int32_t min, int32_t max)
1491 {
1492     SwitchInfo switchInfo = m_switchContextStack.last();
1493     m_switchContextStack.removeLast();
1494     if (switchInfo.switchType == SwitchInfo::SwitchImmediate) {
1495         instructions()[switchInfo.opcodeOffset + 1] = m_codeBlock->immediateSwitchJumpTables.size();
1496         instructions()[switchInfo.opcodeOffset + 2] = defaultLabel->offsetFrom(switchInfo.opcodeOffset + 3);
1497
1498         m_codeBlock->immediateSwitchJumpTables.append(SimpleJumpTable());
1499         SimpleJumpTable& jumpTable = m_codeBlock->immediateSwitchJumpTables.last();
1500
1501         prepareJumpTableForImmediateSwitch(jumpTable, switchInfo.opcodeOffset + 3, clauseCount, labels, nodes, min, max);
1502     } else if (switchInfo.switchType == SwitchInfo::SwitchCharacter) {
1503         instructions()[switchInfo.opcodeOffset + 1] = m_codeBlock->characterSwitchJumpTables.size();
1504         instructions()[switchInfo.opcodeOffset + 2] = defaultLabel->offsetFrom(switchInfo.opcodeOffset + 3);
1505         
1506         m_codeBlock->characterSwitchJumpTables.append(SimpleJumpTable());
1507         SimpleJumpTable& jumpTable = m_codeBlock->characterSwitchJumpTables.last();
1508
1509         prepareJumpTableForCharacterSwitch(jumpTable, switchInfo.opcodeOffset + 3, clauseCount, labels, nodes, min, max);
1510     } else {
1511         ASSERT(switchInfo.switchType == SwitchInfo::SwitchString);
1512         instructions()[switchInfo.opcodeOffset + 1] = m_codeBlock->stringSwitchJumpTables.size();
1513         instructions()[switchInfo.opcodeOffset + 2] = defaultLabel->offsetFrom(switchInfo.opcodeOffset + 3);
1514
1515         m_codeBlock->stringSwitchJumpTables.append(StringJumpTable());
1516         StringJumpTable& jumpTable = m_codeBlock->stringSwitchJumpTables.last();
1517
1518         prepareJumpTableForStringSwitch(jumpTable, switchInfo.opcodeOffset + 3, clauseCount, labels, nodes);
1519     }
1520 }
1521
1522 } // namespace JSC