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