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