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