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