Merge squirrelfish branch into trunk.
[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* r0, RegisterID* r1, RegisterID* r2, ArgumentsNode* argumentsNode)
947 {
948     return emitCall(op_call, r0, r1, r2, argumentsNode);
949 }
950
951 RegisterID* CodeGenerator::emitCallEval(RegisterID* r0, RegisterID* r1, RegisterID* r2, ArgumentsNode* argumentsNode)
952 {
953     return emitCall(op_call_eval, r0, r1, r2, argumentsNode);
954 }
955
956 RegisterID* CodeGenerator::emitCall(OpcodeID opcodeID, RegisterID* r0, RegisterID* r1, RegisterID* r2, ArgumentsNode* argumentsNode)
957 {
958     ASSERT(opcodeID == op_call || opcodeID == op_call_eval);
959
960     RefPtr<RegisterID> ref1 = r1;
961     RefPtr<RegisterID> ref2 = r2;
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(r0->index());
978     instructions().append(r1->index());
979     instructions().append(r2 ? r2->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
983     return r0;
984 }
985
986 RegisterID* CodeGenerator::emitReturn(RegisterID* r0)
987 {
988     instructions().append(machine().getOpcode(op_ret));
989     instructions().append(r0->index());
990     return r0;
991 }
992
993 RegisterID* CodeGenerator::emitEnd(RegisterID* r0)
994 {
995     instructions().append(machine().getOpcode(op_end));
996     instructions().append(r0->index());
997     return r0;
998 }
999
1000 RegisterID* CodeGenerator::emitConstruct(RegisterID* r0, RegisterID* r1, ArgumentsNode* argumentsNode)
1001 {
1002     // Reserve space for call frame.
1003     Vector<RefPtr<RegisterID>, Machine::CallFrameHeaderSize> callFrame;
1004     for (int i = 0; i < Machine::CallFrameHeaderSize; ++i)
1005         callFrame.append(newTemporary());
1006
1007     // Generate code for arguments.
1008     Vector<RefPtr<RegisterID>, 16> argv;
1009     argv.append(newTemporary()); // reserve space for "this"
1010     for (ArgumentListNode* n = argumentsNode ? argumentsNode->m_listNode.get() : 0; n; n = n->m_next.get()) {
1011         argv.append(newTemporary());
1012         emitNode(argv.last().get(), n);
1013     }
1014
1015     instructions().append(machine().getOpcode(op_construct));
1016     instructions().append(r0->index());
1017     instructions().append(r1->index());
1018     instructions().append(argv.size() ? argv[0]->index() : m_temporaries.size()); // argv
1019     instructions().append(argv.size()); // argc
1020     return r0;
1021 }
1022
1023 RegisterID* CodeGenerator::emitPushScope(RegisterID* scope)
1024 {
1025     m_codeBlock->needsFullScopeChain = true;
1026     instructions().append(machine().getOpcode(op_push_scope));
1027     instructions().append(scope->index());
1028
1029     ControlFlowContext context;
1030     context.isFinallyBlock = false;
1031     m_scopeContextStack.append(context);
1032     m_dynamicScopeDepth++;
1033     return scope;
1034 }
1035
1036 void CodeGenerator::emitPopScope()
1037 {
1038     ASSERT(m_scopeContextStack.size());
1039     ASSERT(!m_scopeContextStack.last().isFinallyBlock);
1040
1041     instructions().append(machine().getOpcode(op_pop_scope));
1042
1043     m_scopeContextStack.removeLast();
1044     m_dynamicScopeDepth--;
1045 }
1046
1047 void CodeGenerator::emitDebugHook(DebugHookID debugHookID, int firstLine, int lastLine)
1048 {
1049     if (!m_shouldEmitDebugHooks)
1050         return;
1051     instructions().append(machine().getOpcode(op_debug));
1052     instructions().append(debugHookID);
1053     instructions().append(firstLine);
1054     instructions().append(lastLine);
1055 }
1056
1057 void CodeGenerator::pushFinallyContext(LabelID* target, RegisterID* retAddrDst)
1058 {
1059     ControlFlowContext scope;
1060     scope.isFinallyBlock = true;
1061     FinallyContext context = { target, retAddrDst };
1062     scope.finallyContext = context;
1063     m_scopeContextStack.append(scope);
1064     m_finallyDepth++;
1065 }
1066
1067 void CodeGenerator::popFinallyContext()
1068 {
1069     ASSERT(m_scopeContextStack.size());
1070     ASSERT(m_scopeContextStack.last().isFinallyBlock);
1071     ASSERT(m_finallyDepth > 0);
1072     m_scopeContextStack.removeLast();
1073     m_finallyDepth--;
1074 }
1075
1076 void CodeGenerator::pushJumpContext(LabelStack* labels, LabelID* continueTarget, LabelID* breakTarget, bool isValidUnlabeledBreakTarget)
1077 {
1078     JumpContext context = { labels, continueTarget, breakTarget, scopeDepth(), isValidUnlabeledBreakTarget };
1079     m_jumpContextStack.append(context);
1080     if (continueTarget)
1081         m_continueDepth++;
1082 }
1083
1084 void CodeGenerator::popJumpContext()
1085 {
1086     ASSERT(m_jumpContextStack.size());
1087     if (m_jumpContextStack.last().continueTarget)
1088         m_continueDepth--;
1089     m_jumpContextStack.removeLast();
1090 }
1091
1092 JumpContext* CodeGenerator::jumpContextForContinue(const Identifier& label)
1093 {
1094     if(!m_jumpContextStack.size())
1095         return 0;
1096
1097     if (label.isEmpty()) {
1098         for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
1099             JumpContext* scope = &m_jumpContextStack[i];
1100             if (scope->continueTarget)
1101                 return scope;
1102         }
1103         return 0;
1104     }
1105     
1106     for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
1107         JumpContext* scope = &m_jumpContextStack[i];
1108         if (scope->labels->contains(label))
1109             return scope;
1110     }
1111     return 0;
1112 }
1113
1114 JumpContext* CodeGenerator::jumpContextForBreak(const Identifier& label)
1115 {
1116     if(!m_jumpContextStack.size())
1117         return 0;
1118
1119     if (label.isEmpty()) {
1120         for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
1121             JumpContext* scope = &m_jumpContextStack[i];
1122             if (scope->isValidUnlabeledBreakTarget)
1123                 return scope;
1124         }
1125         return 0;
1126     }
1127     
1128     for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
1129         JumpContext* scope = &m_jumpContextStack[i];
1130         if (scope->labels->contains(label))
1131             return scope;
1132     }
1133     return 0;
1134 }
1135
1136 PassRefPtr<LabelID> CodeGenerator::emitComplexJumpScopes(LabelID* target, ControlFlowContext* topScope, ControlFlowContext* bottomScope)
1137 {
1138     while (topScope > bottomScope) {
1139         // First we count the number of dynamic scopes we need to remove to get
1140         // to a finally block.
1141         int nNormalScopes = 0;
1142         while (topScope > bottomScope) {
1143             if (topScope->isFinallyBlock)
1144                 break;
1145             ++nNormalScopes;
1146             --topScope;
1147         }
1148
1149         if (nNormalScopes) {
1150             // We need to remove a number of dynamic scopes to get to the next 
1151             // finally block
1152             instructions().append(machine().getOpcode(op_jmp_scopes));
1153             instructions().append(nNormalScopes);
1154             
1155             // If topScope == bottomScope then there isn't actually a finally block
1156             // left to emit, so make the jmp_scopes jump directly to the target label
1157             if (topScope == bottomScope) {
1158                 instructions().append(target->offsetFrom(instructions().size()));
1159                 return target;
1160             }
1161
1162             // Otherwise we just use jmp_scopes to pop a group of scopes and go 
1163             // to the next instruction
1164             RefPtr<LabelID> nextInsn = newLabel();
1165             instructions().append(nextInsn->offsetFrom(instructions().size()));
1166             emitLabel(nextInsn.get());
1167         }
1168
1169         // To get here there must be at least one finally block present
1170         do {
1171             ASSERT(topScope->isFinallyBlock);
1172             emitJumpSubroutine(topScope->finallyContext.retAddrDst, topScope->finallyContext.finallyAddr);
1173             --topScope;
1174             if (!topScope->isFinallyBlock)
1175                 break;
1176         } while (topScope > bottomScope);
1177     }
1178     return emitJump(target);
1179 }
1180
1181 PassRefPtr<LabelID> CodeGenerator::emitJumpScopes(LabelID* target, int targetScopeDepth)
1182 {
1183     ASSERT(scopeDepth() - targetScopeDepth >= 0);
1184
1185     size_t scopeDelta = scopeDepth() - targetScopeDepth;
1186     ASSERT(scopeDelta <= m_scopeContextStack.size());
1187     if (!scopeDelta)
1188         return emitJump(target);
1189
1190     if (m_finallyDepth)
1191         return emitComplexJumpScopes(target, &m_scopeContextStack.last(), &m_scopeContextStack.last() - scopeDelta);
1192
1193     instructions().append(machine().getOpcode(op_jmp_scopes));
1194     instructions().append(scopeDelta);
1195     instructions().append(target->offsetFrom(instructions().size()));
1196     return target;
1197 }
1198
1199 RegisterID* CodeGenerator::emitNextPropertyName(RegisterID* dst, RegisterID* iter, LabelID* target)
1200 {
1201     instructions().append(machine().getOpcode(op_next_pname));
1202     instructions().append(dst->index());
1203     instructions().append(iter->index());
1204     instructions().append(target->offsetFrom(instructions().size()));
1205     return dst;
1206 }
1207
1208 RegisterID* CodeGenerator::emitGetPropertyNames(RegisterID* dst, RegisterID* base)
1209 {
1210     instructions().append(machine().getOpcode(op_get_pnames));
1211     instructions().append(dst->index());
1212     instructions().append(base->index());
1213     return dst;
1214 }
1215
1216 RegisterID* CodeGenerator::emitCatch(RegisterID* targetRegister, LabelID* start, LabelID* end)
1217 {
1218     HandlerInfo info = { start->offsetFrom(0), end->offsetFrom(0), instructions().size(), m_dynamicScopeDepth };
1219     exceptionHandlers().append(info);
1220     instructions().append(machine().getOpcode(op_catch));
1221     instructions().append(targetRegister->index());
1222     return targetRegister;
1223 }
1224     
1225 void CodeGenerator::emitThrow(RegisterID* exception)
1226 {
1227     instructions().append(machine().getOpcode(op_throw));
1228     instructions().append(exception->index());
1229 }
1230
1231 RegisterID* CodeGenerator::emitNewError(RegisterID* dst, ErrorType type, JSValue* message)
1232 {
1233     instructions().append(machine().getOpcode(op_new_error));
1234     instructions().append(dst->index());
1235     instructions().append(static_cast<int>(type));
1236     instructions().append(addConstant(message));
1237     return dst;
1238 }
1239
1240 PassRefPtr<LabelID> CodeGenerator::emitJumpSubroutine(RegisterID* retAddrDst, LabelID* finally)
1241 {
1242     instructions().append(machine().getOpcode(op_jsr));
1243     instructions().append(retAddrDst->index());
1244     instructions().append(finally->offsetFrom(instructions().size()));
1245     return finally;
1246 }
1247
1248 void CodeGenerator::emitSubroutineReturn(RegisterID* retAddrSrc)
1249 {
1250     instructions().append(machine().getOpcode(op_sret));
1251     instructions().append(retAddrSrc->index());
1252 }
1253
1254 } // namespace KJS