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