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