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             globalObject->removeDirect(funcDecl->m_ident); // Make sure our new function is not shadowed by an old property.
210             emitNewFunction(addVar(funcDecl->m_ident, false), funcDecl);
211         }
212         
213         for (size_t i = 0; i < varStack.size(); ++i) {
214             if (!globalObject->hasProperty(exec, varStack[i].first))
215                 emitLoad(addVar(varStack[i].first, varStack[i].second & DeclarationStacks::IsConstant), jsUndefined());
216         }
217     } else {
218         for (size_t i = 0; i < functionStack.size(); ++i) {
219             FuncDeclNode* funcDecl = functionStack[i];
220             globalObject->putWithAttributes(exec, funcDecl->m_ident, funcDecl->makeFunction(exec, scopeChain.node()), DontDelete);
221         }
222         for (size_t i = 0; i < varStack.size(); ++i) {
223             if (globalObject->hasProperty(exec, varStack[i].first))
224                 continue;
225             int attributes = DontDelete;
226             if (varStack[i].second & DeclarationStacks::IsConstant)
227                 attributes |= ReadOnly;
228             globalObject->putWithAttributes(exec, varStack[i].first, jsUndefined(), attributes);
229         }
230     }
231 }
232
233 CodeGenerator::CodeGenerator(FunctionBodyNode* functionBody, const Debugger* debugger, const ScopeChain& scopeChain, SymbolTable* symbolTable, CodeBlock* codeBlock, VarStack& varStack, FunctionStack& functionStack, Vector<Identifier>& parameters)
234     : m_shouldEmitDebugHooks(!!debugger)
235     , m_scopeChain(&scopeChain)
236     , m_symbolTable(symbolTable)
237     , m_scopeNode(functionBody)
238     , m_codeBlock(codeBlock)
239     , m_thisRegister(0)
240     , m_finallyDepth(0)
241     , m_dynamicScopeDepth(0)
242     , m_codeType(FunctionCode)
243     , m_continueDepth(0)
244     , m_nextVar(-1)
245     , m_propertyNames(CommonIdentifiers::shared())
246 {
247     for (size_t i = 0; i < functionStack.size(); ++i) {
248         FuncDeclNode* funcDecl = functionStack[i];
249         const Identifier& ident = funcDecl->m_ident;
250         
251         m_functions.add(ident.ustring().rep());
252         emitNewFunction(addVar(ident, false), funcDecl);
253     }
254
255     for (size_t i = 0; i < varStack.size(); ++i) {
256         const Identifier& ident = varStack[i].first;
257         if (ident == m_propertyNames->arguments)
258             continue;
259         
260         RegisterID* r0;
261         if (addVar(ident, r0, varStack[i].second & DeclarationStacks::IsConstant))
262             emitLoad(r0, jsUndefined());
263     }
264
265     m_nextParameter = m_nextVar - parameters.size();
266     m_locals.resize(localsIndex(m_nextParameter) + 1);
267
268     m_thisRegister = addParameter(m_propertyNames->thisIdentifier);
269     for (size_t i = 0; i < parameters.size(); ++i) {
270         addParameter(parameters[i]);
271     }
272 }
273
274 CodeGenerator::CodeGenerator(EvalNode* evalNode, const Debugger* debugger, const ScopeChain& scopeChain, SymbolTable* symbolTable, EvalCodeBlock* codeBlock, VarStack& varStack, FunctionStack& functionStack)
275     : m_shouldEmitDebugHooks(!!debugger)
276     , m_scopeChain(&scopeChain)
277     , m_symbolTable(symbolTable)
278     , m_scopeNode(evalNode)
279     , m_codeBlock(codeBlock)
280     , m_thisRegister(0)
281     , m_finallyDepth(0)
282     , m_dynamicScopeDepth(0)
283     , m_codeType(EvalCode)
284     , m_continueDepth(0)
285     , m_nextVar(-1)
286     , m_propertyNames(CommonIdentifiers::shared())
287 {
288     addVar(m_propertyNames->thisIdentifier, m_thisRegister, false);
289     
290     for (size_t i = 0; i < varStack.size(); ++i)
291         codeBlock->declaredVariableNames.append(varStack[i].first);
292     
293     for (size_t i = 0; i < functionStack.size(); ++i) {
294         FuncDeclNode* funcDecl = functionStack[i];
295         codeBlock->declaredFunctionNames.append(funcDecl->m_ident);
296         addConstant(funcDecl);
297     }
298 }
299
300 CodeGenerator::~CodeGenerator()
301 {
302 }
303
304 RegisterID* CodeGenerator::addParameter(const Identifier& ident)
305 {
306     // Parameters overwrite var declarations, but not function declarations,
307     // in the symbol table.
308     RegisterID* result = 0;
309     UString::Rep* rep = ident.ustring().rep();
310     if (!m_functions.contains(rep)) {
311         symbolTable().set(rep, m_nextParameter);
312         m_locals[localsIndex(m_nextParameter)].setIndex(m_nextParameter);
313         result = &(m_locals[localsIndex(m_nextParameter)]);
314     }
315     
316     // To maintain the calling convention, we have to allocate unique space for
317     // each parameter, even if the parameter doesn't make it into the symbol table.
318     ++m_nextParameter;
319     ++m_codeBlock->numParameters;
320     return result;
321 }
322
323 RegisterID* CodeGenerator::registerForLocal(const Identifier& ident)
324 {
325     if (m_codeType == FunctionCode && ident == m_propertyNames->arguments)
326         m_codeBlock->needsFullScopeChain = true;
327
328     if (!shouldOptimizeLocals() && ident != m_propertyNames->thisIdentifier)
329         return 0;
330
331     SymbolTableEntry entry = symbolTable().get(ident.ustring().rep());
332     if (entry.isEmpty())
333         return 0;
334
335     return &m_locals[localsIndex(entry.getIndex())];
336 }
337
338 RegisterID* CodeGenerator::registerForLocalConstInit(const Identifier& ident)
339 {
340     if (m_codeType == EvalCode)
341         return 0;
342     
343     SymbolTableEntry entry = symbolTable().get(ident.ustring().rep());
344     ASSERT(!entry.isEmpty());
345     
346     return &m_locals[localsIndex(entry.getIndex())];
347 }
348
349 bool CodeGenerator::isLocalConstant(const Identifier& ident)
350 {
351     return symbolTable().get(ident.ustring().rep()).isReadOnly();
352 }
353
354 RegisterID* CodeGenerator::newTemporary()
355 {
356     // Reclaim free register IDs.
357     while (m_temporaries.size() && !m_temporaries.last().refCount())
358         m_temporaries.removeLast();
359
360     // Allocate new register ID.
361     m_temporaries.append(m_temporaries.size());
362     m_codeBlock->numTemporaries = max<int>(m_codeBlock->numTemporaries, m_temporaries.size());
363     return &m_temporaries.last();
364 }
365
366 PassRefPtr<LabelID> CodeGenerator::newLabel()
367 {
368     // Reclaim free label IDs.
369     while (m_labels.size() && !m_labels.last().refCount())
370         m_labels.removeLast();
371
372     // Allocate new label ID.
373     m_labels.append(m_codeBlock);
374     return &m_labels.last();
375 }
376
377 PassRefPtr<LabelID> CodeGenerator::emitLabel(LabelID* l0)
378 {
379     l0->setLocation(instructions().size());
380     return l0;
381 }
382
383 PassRefPtr<LabelID> CodeGenerator::emitJump(LabelID* target)
384 {
385     instructions().append(machine().getOpcode(op_jmp));
386     instructions().append(target->offsetFrom(instructions().size()));
387     return target;
388 }
389
390 PassRefPtr<LabelID> CodeGenerator::emitJumpIfTrue(RegisterID* cond, LabelID* target)
391 {
392     instructions().append(machine().getOpcode(op_jtrue));
393     instructions().append(cond->index());
394     instructions().append(target->offsetFrom(instructions().size()));
395     return target;
396 }
397
398 PassRefPtr<LabelID> CodeGenerator::emitJumpIfFalse(RegisterID* cond, LabelID* target)
399 {
400     instructions().append(machine().getOpcode(op_jfalse));
401     instructions().append(cond->index());
402     instructions().append(target->offsetFrom(instructions().size()));
403     return target;
404 }
405
406 unsigned CodeGenerator::addConstant(FuncDeclNode* n)
407 {
408     // No need to explicitly unique function body nodes -- they're unique already.
409     int index = m_codeBlock->functions.size();
410     m_codeBlock->functions.append(n);
411     return index;
412 }
413
414 unsigned CodeGenerator::addConstant(FuncExprNode* n)
415 {
416     // No need to explicitly unique function expression nodes -- they're unique already.
417     int index = m_codeBlock->functionExpressions.size();
418     m_codeBlock->functionExpressions.append(n);
419     return index;
420 }
421
422 unsigned CodeGenerator::addConstant(const Identifier& ident)
423 {
424     UString::Rep* rep = ident.ustring().rep();
425     pair<IdentifierMap::iterator, bool> result = m_identifierMap.add(rep, m_codeBlock->identifiers.size());
426     if (result.second) // new entry
427         m_codeBlock->identifiers.append(rep);
428     
429     return result.first->second;
430 }
431
432 unsigned CodeGenerator::addConstant(JSValue* v)
433 {
434     pair<JSValueMap::iterator, bool> result = m_jsValueMap.add(v, m_codeBlock->jsValues.size());
435     if (result.second) // new entry
436         m_codeBlock->jsValues.append(v);
437     
438     return result.first->second;
439 }
440
441 unsigned CodeGenerator::addRegExp(RegExp* r)
442 {
443     int index = m_codeBlock->regexps.size();
444     m_codeBlock->regexps.append(r);
445     return index;
446 }
447
448 RegisterID* CodeGenerator::emitMove(RegisterID* dst, RegisterID* src)
449 {
450     instructions().append(machine().getOpcode(op_mov));
451     instructions().append(dst->index());
452     instructions().append(src->index());
453     return dst;
454 }
455
456 RegisterID* CodeGenerator::emitNot(RegisterID* dst, RegisterID* src)
457 {
458     instructions().append(machine().getOpcode(op_not));
459     instructions().append(dst->index());
460     instructions().append(src->index());
461     return dst;
462 }
463
464 RegisterID* CodeGenerator::emitEqual(RegisterID* dst, RegisterID* src1, RegisterID* src2)
465 {
466     instructions().append(machine().getOpcode(op_eq));
467     instructions().append(dst->index());
468     instructions().append(src1->index());
469     instructions().append(src2->index());
470     return dst;
471 }
472
473 RegisterID* CodeGenerator::emitNotEqual(RegisterID* dst, RegisterID* src1, RegisterID* src2)
474 {
475     instructions().append(machine().getOpcode(op_neq));
476     instructions().append(dst->index());
477     instructions().append(src1->index());
478     instructions().append(src2->index());
479     return dst;
480 }
481
482 RegisterID* CodeGenerator::emitStrictEqual(RegisterID* dst, RegisterID* src1, RegisterID* src2)
483 {
484     instructions().append(machine().getOpcode(op_stricteq));
485     instructions().append(dst->index());
486     instructions().append(src1->index());
487     instructions().append(src2->index());
488     return dst;
489 }
490
491 RegisterID* CodeGenerator::emitNotStrictEqual(RegisterID* dst, RegisterID* src1, RegisterID* src2)
492 {
493     instructions().append(machine().getOpcode(op_nstricteq));
494     instructions().append(dst->index());
495     instructions().append(src1->index());
496     instructions().append(src2->index());
497     return dst;
498 }
499
500 RegisterID* CodeGenerator::emitLess(RegisterID* dst, RegisterID* src1, RegisterID* src2)
501 {
502     instructions().append(machine().getOpcode(op_less));
503     instructions().append(dst->index());
504     instructions().append(src1->index());
505     instructions().append(src2->index());
506     return dst;
507 }
508
509 RegisterID* CodeGenerator::emitLessEq(RegisterID* dst, RegisterID* src1, RegisterID* src2)
510 {
511     instructions().append(machine().getOpcode(op_lesseq));
512     instructions().append(dst->index());
513     instructions().append(src1->index());
514     instructions().append(src2->index());
515     return dst;
516 }
517
518 RegisterID* CodeGenerator::emitPreInc(RegisterID* srcDst)
519 {
520     instructions().append(machine().getOpcode(op_pre_inc));
521     instructions().append(srcDst->index());
522     return srcDst;
523 }
524
525 RegisterID* CodeGenerator::emitPreDec(RegisterID* srcDst)
526 {
527     instructions().append(machine().getOpcode(op_pre_dec));
528     instructions().append(srcDst->index());
529     return srcDst;
530 }
531
532 RegisterID* CodeGenerator::emitPostInc(RegisterID* dst, RegisterID* srcDst)
533 {
534     instructions().append(machine().getOpcode(op_post_inc));
535     instructions().append(dst->index());
536     instructions().append(srcDst->index());
537     return dst;
538 }
539
540 RegisterID* CodeGenerator::emitPostDec(RegisterID* dst, RegisterID* srcDst)
541 {
542     instructions().append(machine().getOpcode(op_post_dec));
543     instructions().append(dst->index());
544     instructions().append(srcDst->index());
545     return dst;
546 }
547
548 RegisterID* CodeGenerator::emitToJSNumber(RegisterID* dst, RegisterID* src)
549 {
550     instructions().append(machine().getOpcode(op_to_jsnumber));
551     instructions().append(dst->index());
552     instructions().append(src->index());
553     return dst;
554 }
555
556 RegisterID* CodeGenerator::emitNegate(RegisterID* dst, RegisterID* src)
557 {
558     instructions().append(machine().getOpcode(op_negate));
559     instructions().append(dst->index());
560     instructions().append(src->index());
561     return dst;
562 }
563
564 RegisterID* CodeGenerator::emitAdd(RegisterID* dst, RegisterID* src1, RegisterID* src2)
565 {
566     instructions().append(machine().getOpcode(op_add));
567     instructions().append(dst->index());
568     instructions().append(src1->index());
569     instructions().append(src2->index());
570     return dst;
571 }
572
573 RegisterID* CodeGenerator::emitMul(RegisterID* dst, RegisterID* src1, RegisterID* src2)
574 {
575     instructions().append(machine().getOpcode(op_mul));
576     instructions().append(dst->index());
577     instructions().append(src1->index());
578     instructions().append(src2->index());
579     return dst;
580 }
581
582 RegisterID* CodeGenerator::emitDiv(RegisterID* dst, RegisterID* dividend, RegisterID* divisor)
583 {
584     instructions().append(machine().getOpcode(op_div));
585     instructions().append(dst->index());
586     instructions().append(dividend->index());
587     instructions().append(divisor->index());
588     return dst;
589 }
590
591 RegisterID* CodeGenerator::emitMod(RegisterID* dst, RegisterID* dividend, RegisterID* divisor)
592 {
593     instructions().append(machine().getOpcode(op_mod));
594     instructions().append(dst->index());
595     instructions().append(dividend->index());
596     instructions().append(divisor->index());
597     return dst;
598 }
599
600 RegisterID* CodeGenerator::emitSub(RegisterID* dst, RegisterID* src1, RegisterID* src2)
601 {
602     instructions().append(machine().getOpcode(op_sub));
603     instructions().append(dst->index());
604     instructions().append(src1->index());
605     instructions().append(src2->index());
606     return dst;
607 }
608
609 RegisterID* CodeGenerator::emitLeftShift(RegisterID* dst, RegisterID* val, RegisterID* shift)
610 {
611     instructions().append(machine().getOpcode(op_lshift));
612     instructions().append(dst->index());
613     instructions().append(val->index());
614     instructions().append(shift->index());
615     return dst;
616 }
617
618 RegisterID* CodeGenerator::emitRightShift(RegisterID* dst, RegisterID* val, RegisterID* shift)
619 {
620     instructions().append(machine().getOpcode(op_rshift));
621     instructions().append(dst->index());
622     instructions().append(val->index());
623     instructions().append(shift->index());
624     return dst;
625 }
626
627 RegisterID* CodeGenerator::emitUnsignedRightShift(RegisterID* dst, RegisterID* val, RegisterID* shift)
628 {
629     instructions().append(machine().getOpcode(op_urshift));
630     instructions().append(dst->index());
631     instructions().append(val->index());
632     instructions().append(shift->index());
633     return dst;
634 }
635
636 RegisterID* CodeGenerator::emitBitAnd(RegisterID* dst, RegisterID* src1, RegisterID* src2)
637 {
638     instructions().append(machine().getOpcode(op_bitand));
639     instructions().append(dst->index());
640     instructions().append(src1->index());
641     instructions().append(src2->index());
642     return dst;
643 }
644
645 RegisterID* CodeGenerator::emitBitXOr(RegisterID* dst, RegisterID* src1, RegisterID* src2)
646 {
647     instructions().append(machine().getOpcode(op_bitxor));
648     instructions().append(dst->index());
649     instructions().append(src1->index());
650     instructions().append(src2->index());
651     return dst;
652 }
653
654 RegisterID* CodeGenerator::emitBitOr(RegisterID* dst, RegisterID* src1, RegisterID* src2)
655 {
656     instructions().append(machine().getOpcode(op_bitor));
657     instructions().append(dst->index());
658     instructions().append(src1->index());
659     instructions().append(src2->index());
660     return dst;
661 }
662
663 RegisterID* CodeGenerator::emitBitNot(RegisterID* dst, RegisterID* src)
664 {
665     instructions().append(machine().getOpcode(op_bitnot));
666     instructions().append(dst->index());
667     instructions().append(src->index());
668     return dst;
669 }
670
671 RegisterID* CodeGenerator::emitInstanceOf(RegisterID* dst, RegisterID* value, RegisterID* base)
672 {
673     instructions().append(machine().getOpcode(op_instanceof));
674     instructions().append(dst->index());
675     instructions().append(value->index());
676     instructions().append(base->index());
677     return dst;
678 }
679
680 RegisterID* CodeGenerator::emitTypeOf(RegisterID* dst, RegisterID* src)
681 {
682     instructions().append(machine().getOpcode(op_typeof));
683     instructions().append(dst->index());
684     instructions().append(src->index());
685     return dst;
686 }
687
688 RegisterID* CodeGenerator::emitIn(RegisterID* dst, RegisterID* property, RegisterID* base)
689 {
690     instructions().append(machine().getOpcode(op_in));
691     instructions().append(dst->index());
692     instructions().append(property->index());
693     instructions().append(base->index());
694     return dst;
695 }
696
697 RegisterID* CodeGenerator::emitLoad(RegisterID* dst, bool b)
698 {
699     instructions().append(machine().getOpcode(op_load));
700     instructions().append(dst->index());
701     instructions().append(addConstant(jsBoolean(b)));
702     return dst;
703 }
704
705 RegisterID* CodeGenerator::emitLoad(RegisterID* dst, double d)
706 {
707     instructions().append(machine().getOpcode(op_load));
708     instructions().append(dst->index());
709     instructions().append(addConstant(jsNumber(d)));
710     return dst;
711 }
712
713 RegisterID* CodeGenerator::emitLoad(RegisterID* dst, JSValue* v)
714 {
715     instructions().append(machine().getOpcode(op_load));
716     instructions().append(dst->index());
717     instructions().append(addConstant(v));
718     return dst;
719 }
720
721 RegisterID* CodeGenerator::emitNewObject(RegisterID* dst)
722 {
723     instructions().append(machine().getOpcode(op_new_object));
724     instructions().append(dst->index());
725     return dst;
726 }
727
728 RegisterID* CodeGenerator::emitNewArray(RegisterID* dst)
729 {
730     instructions().append(machine().getOpcode(op_new_array));
731     instructions().append(dst->index());
732     return dst;
733 }
734
735 bool CodeGenerator::findScopedProperty(const Identifier& property, int& index, size_t& stackDepth)
736 {
737     // Cases where we cannot optimise the lookup
738     if (property == m_propertyNames->arguments || !canOptimizeNonLocals()) {
739         stackDepth = 0;
740         index = missingSymbolMarker();
741         return false;
742     }
743
744     ScopeChainIterator iter = m_scopeChain->begin();
745     ScopeChainIterator end = m_scopeChain->end();
746     size_t depth = 0;
747
748     for (; iter != end; ++iter, ++depth) {
749         JSObject* currentScope = *iter;
750         if (!currentScope->isVariableObject()) 
751             break;
752         JSVariableObject* currentVariableObject = static_cast<JSVariableObject*>(currentScope);
753         SymbolTableEntry entry = currentVariableObject->symbolTable().get(property.ustring().rep());
754
755         // Found the property
756         if (!entry.isEmpty()) {
757             stackDepth = depth;
758             index = entry.getIndex();
759             return true;
760         }
761         if (currentVariableObject->isDynamicScope())
762             break;
763     }
764
765     // Can't locate the property but we're able to avoid a few lookups
766     stackDepth = depth;
767     index = missingSymbolMarker();
768     return true;
769 }
770
771 RegisterID* CodeGenerator::emitResolve(RegisterID* dst, const Identifier& property)
772 {
773     size_t depth = 0;
774     int index = 0;
775     if (!findScopedProperty(property, index, depth)) {
776         // We can't optimise at all :-(
777         instructions().append(machine().getOpcode(op_resolve));
778         instructions().append(dst->index());
779         instructions().append(addConstant(property));
780         return dst;
781     }
782
783     if (index == missingSymbolMarker()) {
784         // In this case we are at least able to drop a few scope chains from the
785         // lookup chain, although we still need to hash from then on.
786         instructions().append(machine().getOpcode(op_resolve_skip));
787         instructions().append(dst->index());
788         instructions().append(addConstant(property));
789         instructions().append(depth);
790         return dst;
791     }
792
793     // Directly index the property lookup across multiple scopes.  Yay!
794     return emitGetScopedVar(dst, depth, index);
795 }
796     
797 RegisterID* CodeGenerator::emitGetScopedVar(RegisterID* dst, size_t depth, int index)
798 {
799     instructions().append(machine().getOpcode(op_get_scoped_var));
800     instructions().append(dst->index());
801     instructions().append(index);
802     instructions().append(depth);
803     return dst;
804 }
805     
806 RegisterID* CodeGenerator::emitPutScopedVar(size_t depth, int index, RegisterID* value)
807 {
808     instructions().append(machine().getOpcode(op_put_scoped_var));
809     instructions().append(index);
810     instructions().append(depth);
811     instructions().append(value->index());
812     return value;
813 }
814
815 RegisterID* CodeGenerator::emitResolveBase(RegisterID* dst, const Identifier& property)
816 {
817     instructions().append(machine().getOpcode(op_resolve_base));
818     instructions().append(dst->index());
819     instructions().append(addConstant(property));
820     return dst;
821 }
822     
823 RegisterID* CodeGenerator::emitResolveWithBase(RegisterID* baseDst, RegisterID* propDst, const Identifier& property)
824 {
825     instructions().append(machine().getOpcode(op_resolve_with_base));
826     instructions().append(baseDst->index());
827     instructions().append(propDst->index());
828     instructions().append(addConstant(property));
829     return baseDst;
830 }
831
832 RegisterID* CodeGenerator::emitResolveFunction(RegisterID* baseDst, RegisterID* funcDst, const Identifier& property)
833 {
834     instructions().append(machine().getOpcode(op_resolve_func));
835     instructions().append(baseDst->index());
836     instructions().append(funcDst->index());
837     instructions().append(addConstant(property));
838     return baseDst;
839 }
840
841 RegisterID* CodeGenerator::emitGetById(RegisterID* dst, RegisterID* base, const Identifier& property)
842 {
843     instructions().append(machine().getOpcode(op_get_by_id));
844     instructions().append(dst->index());
845     instructions().append(base->index());
846     instructions().append(addConstant(property));
847     return dst;
848 }
849
850 RegisterID* CodeGenerator::emitPutById(RegisterID* base, const Identifier& property, RegisterID* value)
851 {
852     instructions().append(machine().getOpcode(op_put_by_id));
853     instructions().append(base->index());
854     instructions().append(addConstant(property));
855     instructions().append(value->index());
856     return value;
857 }
858
859 RegisterID* CodeGenerator::emitPutGetter(RegisterID* base, const Identifier& property, RegisterID* value)
860 {
861     instructions().append(machine().getOpcode(op_put_getter));
862     instructions().append(base->index());
863     instructions().append(addConstant(property));
864     instructions().append(value->index());
865     return value;
866 }
867
868 RegisterID* CodeGenerator::emitPutSetter(RegisterID* base, const Identifier& property, RegisterID* value)
869 {
870     instructions().append(machine().getOpcode(op_put_setter));
871     instructions().append(base->index());
872     instructions().append(addConstant(property));
873     instructions().append(value->index());
874     return value;
875 }
876
877 RegisterID* CodeGenerator::emitDeleteById(RegisterID* dst, RegisterID* base, const Identifier& property)
878 {
879     instructions().append(machine().getOpcode(op_del_by_id));
880     instructions().append(dst->index());
881     instructions().append(base->index());
882     instructions().append(addConstant(property));
883     return dst;
884 }
885
886 RegisterID* CodeGenerator::emitGetByVal(RegisterID* dst, RegisterID* base, RegisterID* property)
887 {
888     instructions().append(machine().getOpcode(op_get_by_val));
889     instructions().append(dst->index());
890     instructions().append(base->index());
891     instructions().append(property->index());
892     return dst;
893 }
894
895 RegisterID* CodeGenerator::emitPutByVal(RegisterID* base, RegisterID* property, RegisterID* value)
896 {
897     instructions().append(machine().getOpcode(op_put_by_val));
898     instructions().append(base->index());
899     instructions().append(property->index());
900     instructions().append(value->index());
901     return value;
902 }
903
904 RegisterID* CodeGenerator::emitDeleteByVal(RegisterID* dst, RegisterID* base, RegisterID* property)
905 {
906     instructions().append(machine().getOpcode(op_del_by_val));
907     instructions().append(dst->index());
908     instructions().append(base->index());
909     instructions().append(property->index());
910     return dst;
911 }
912
913 RegisterID* CodeGenerator::emitPutByIndex(RegisterID* base, unsigned index, RegisterID* value)
914 {
915     instructions().append(machine().getOpcode(op_put_by_index));
916     instructions().append(base->index());
917     instructions().append(index);
918     instructions().append(value->index());
919     return value;
920 }
921
922 RegisterID* CodeGenerator::emitNewFunction(RegisterID* r0, FuncDeclNode* n)
923 {
924     instructions().append(machine().getOpcode(op_new_func));
925     instructions().append(r0->index());
926     instructions().append(addConstant(n));
927     return r0;
928 }
929
930 RegisterID* CodeGenerator::emitNewRegExp(RegisterID* dst, RegExp* regExp)
931 {
932     instructions().append(machine().getOpcode(op_new_regexp));
933     instructions().append(dst->index());
934     instructions().append(addRegExp(regExp));
935     return dst;
936 }
937
938
939 RegisterID* CodeGenerator::emitNewFunctionExpression(RegisterID* r0, FuncExprNode* n)
940 {
941     instructions().append(machine().getOpcode(op_new_func_exp));
942     instructions().append(r0->index());
943     instructions().append(addConstant(n));
944     return r0;
945 }
946
947 RegisterID* CodeGenerator::emitCall(RegisterID* dst, RegisterID* func, RegisterID* base, ArgumentsNode* argumentsNode)
948 {
949     return emitCall(op_call, dst, func, base, argumentsNode);
950 }
951
952 RegisterID* CodeGenerator::emitCallEval(RegisterID* dst, RegisterID* func, RegisterID* base, ArgumentsNode* argumentsNode)
953 {
954     return emitCall(op_call_eval, dst, func, base, argumentsNode);
955 }
956
957 RegisterID* CodeGenerator::emitCall(OpcodeID opcodeID, RegisterID* dst, RegisterID* func, RegisterID* base, ArgumentsNode* argumentsNode)
958 {
959     ASSERT(opcodeID == op_call || opcodeID == op_call_eval);
960
961     RefPtr<RegisterID> refFunc = func;
962     RefPtr<RegisterID> refBase = base;
963     
964     // Reserve space for call frame.
965     Vector<RefPtr<RegisterID>, Machine::CallFrameHeaderSize> callFrame;
966     for (int i = 0; i < Machine::CallFrameHeaderSize; ++i)
967         callFrame.append(newTemporary());
968
969     // Generate code for arguments.
970     Vector<RefPtr<RegisterID>, 16> argv;
971     argv.append(newTemporary()); // reserve space for "this"
972     for (ArgumentListNode* n = argumentsNode->m_listNode.get(); n; n = n->m_next.get()) {
973         argv.append(newTemporary());
974         emitNode(argv.last().get(), n);
975     }
976
977     instructions().append(machine().getOpcode(opcodeID));
978     instructions().append(dst->index());
979     instructions().append(func->index());
980     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.
981     instructions().append(argv.size() ? argv[0]->index() : m_temporaries.size()); // argv
982     instructions().append(argv.size()); // argc
983     return dst;
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* dst)
994 {
995     instructions().append(machine().getOpcode(op_end));
996     instructions().append(dst->index());
997     return dst;
998 }
999
1000 RegisterID* CodeGenerator::emitConstruct(RegisterID* dst, RegisterID* func, 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(dst->index());
1017     instructions().append(func->index());
1018     instructions().append(argv.size() ? argv[0]->index() : m_temporaries.size()); // argv
1019     instructions().append(argv.size()); // argc
1020     return dst;
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