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