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