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 "JSFunction.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_globalData(&scopeChain.globalObject()->globalExec()->globalData())
 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_globalData(&scopeChain.globalObject()->globalExec()->globalData())
 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 == 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_globalData(&scopeChain.globalObject()->globalExec()->globalData())
 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 == propertyNames().arguments)
 320         m_codeBlock->needsFullScopeChain = true;
 321
 322     if (ident == 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.isNull())
 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.isNull());
 342
 343     return &m_locals[localsIndex(entry.getIndex())];
 344 }
 345
 346 bool CodeGenerator::isLocal(const Identifier& ident)
 347 {
 348     if (ident == 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
 394     // This disables peephole optimizations when an instruction is a jump target
 395     m_lastOpcodeID = op_end;
 396
 397     return l0;
 398 }
 399
 400 void CodeGenerator::emitOpcode(OpcodeID opcodeID)
 401 {
 402     instructions().append(globalData()->machine->getOpcode(opcodeID));
 403     m_lastOpcodeID = opcodeID;
 404 }
 405
 406 void CodeGenerator::retrieveLastBinaryOp(int& dstIndex, int& src1Index, int& src2Index)
 407 {
 408     ASSERT(instructions().size() >= 4);
 409     size_t size = instructions().size();
 410     dstIndex = instructions().at(size - 3).u.operand;
 411     src1Index = instructions().at(size - 2).u.operand;
 412     src2Index = instructions().at(size - 1).u.operand;
 413 }
 414
 415 void CodeGenerator::rewindBinaryOp()
 416 {
 417     ASSERT(instructions().size() >= 4);
 418     instructions().shrink(instructions().size() - 4);
 419 }
 420
 421 PassRefPtr<LabelID> CodeGenerator::emitJump(LabelID* target)
 422 {
 423     ASSERT(target->isForwardLabel());
 424     emitOpcode(op_jmp);
 425     instructions().append(target->offsetFrom(instructions().size()));
 426     return target;
 427 }
 428
 429 PassRefPtr<LabelID> CodeGenerator::emitJumpIfTrueMayCombine(RegisterID* cond, LabelID* target)
 430 {
 431     if (m_lastOpcodeID == op_less) {
 432         int dstIndex;
 433         int src1Index;
 434         int src2Index;
 435
 436         retrieveLastBinaryOp(dstIndex, src1Index, src2Index);
 437
 438         if (cond->index() == dstIndex) {
 439             rewindBinaryOp();
 440             emitOpcode(target->isForwardLabel() ? op_jless : op_loop_if_less);
 441             instructions().append(src1Index);
 442             instructions().append(src2Index);
 443             instructions().append(target->offsetFrom(instructions().size()));
 444             return target;
 445         }
 446     }
 447
 448     return emitJumpIfTrue(cond, target);
 449 }
 450
 451 PassRefPtr<LabelID> CodeGenerator::emitJumpIfTrue(RegisterID* cond, LabelID* target)
 452 {
 453     emitOpcode(target->isForwardLabel() ? op_jtrue : op_loop_if_true);
 454     instructions().append(cond->index());
 455     instructions().append(target->offsetFrom(instructions().size()));
 456     return target;
 457 }
 458
 459 PassRefPtr<LabelID> CodeGenerator::emitJumpIfFalse(RegisterID* cond, LabelID* target)
 460 {
 461     ASSERT(target->isForwardLabel());
 462     emitOpcode(op_jfalse);
 463     instructions().append(cond->index());
 464     instructions().append(target->offsetFrom(instructions().size()));
 465     return target;
 466 }
 467
 468 unsigned CodeGenerator::addConstant(FuncDeclNode* n)
 469 {
 470     // No need to explicitly unique function body nodes -- they're unique already.
 471     int index = m_codeBlock->functions.size();
 472     m_codeBlock->functions.append(n);
 473     return index;
 474 }
 475
 476 unsigned CodeGenerator::addConstant(FuncExprNode* n)
 477 {
 478     // No need to explicitly unique function expression nodes -- they're unique already.
 479     int index = m_codeBlock->functionExpressions.size();
 480     m_codeBlock->functionExpressions.append(n);
 481     return index;
 482 }
 483
 484 unsigned CodeGenerator::addConstant(const Identifier& ident)
 485 {
 486     UString::Rep* rep = ident.ustring().rep();
 487     pair<IdentifierMap::iterator, bool> result = m_identifierMap.add(rep, m_codeBlock->identifiers.size());
 488     if (result.second) // new entry
 489         m_codeBlock->identifiers.append(Identifier(m_globalData, rep));
 490
 491     return result.first->second;
 492 }
 493
 494 unsigned CodeGenerator::addConstant(JSValue* v)
 495 {
 496     pair<JSValueMap::iterator, bool> result = m_jsValueMap.add(v, m_codeBlock->jsValues.size());
 497     if (result.second) // new entry
 498         m_codeBlock->jsValues.append(v);
 499
 500     return result.first->second;
 501 }
 502
 503 unsigned CodeGenerator::addRegExp(RegExp* r)
 504 {
 505     int index = m_codeBlock->regexps.size();
 506     m_codeBlock->regexps.append(r);
 507     return index;
 508 }
 509
 510 RegisterID* CodeGenerator::emitMove(RegisterID* dst, RegisterID* src)
 511 {
 512     emitOpcode(op_mov);
 513     instructions().append(dst->index());
 514     instructions().append(src->index());
 515     return dst;
 516 }
 517
 518 RegisterID* CodeGenerator::emitUnaryOp(OpcodeID opcode, RegisterID* dst, RegisterID* src)
 519 {
 520     emitOpcode(opcode);
 521     instructions().append(dst->index());
 522     instructions().append(src->index());
 523     return dst;
 524 }
 525
 526 RegisterID* CodeGenerator::emitPreInc(RegisterID* srcDst)
 527 {
 528     emitOpcode(op_pre_inc);
 529     instructions().append(srcDst->index());
 530     return srcDst;
 531 }
 532
 533 RegisterID* CodeGenerator::emitPreDec(RegisterID* srcDst)
 534 {
 535     emitOpcode(op_pre_dec);
 536     instructions().append(srcDst->index());
 537     return srcDst;
 538 }
 539
 540 RegisterID* CodeGenerator::emitPostInc(RegisterID* dst, RegisterID* srcDst)
 541 {
 542     emitOpcode(op_post_inc);
 543     instructions().append(dst->index());
 544     instructions().append(srcDst->index());
 545     return dst;
 546 }
 547
 548 RegisterID* CodeGenerator::emitPostDec(RegisterID* dst, RegisterID* srcDst)
 549 {
 550     emitOpcode(op_post_dec);
 551     instructions().append(dst->index());
 552     instructions().append(srcDst->index());
 553     return dst;
 554 }
 555
 556 RegisterID* CodeGenerator::emitBinaryOp(OpcodeID opcode, RegisterID* dst, RegisterID* src1, RegisterID* src2)
 557 {
 558     emitOpcode(opcode);
 559     instructions().append(dst->index());
 560     instructions().append(src1->index());
 561     instructions().append(src2->index());
 562     return dst;
 563 }
 564
 565 RegisterID* CodeGenerator::emitLoad(RegisterID* dst, bool b)
 566 {
 567     emitOpcode(op_load);
 568     instructions().append(dst->index());
 569     instructions().append(addConstant(jsBoolean(b)));
 570     return dst;
 571 }
 572
 573 RegisterID* CodeGenerator::emitLoad(RegisterID* dst, double d)
 574 {
 575     emitOpcode(op_load);
 576     instructions().append(dst->index());
 577     instructions().append(addConstant(jsNumber(globalExec(), d)));
 578     return dst;
 579 }
 580
 581 RegisterID* CodeGenerator::emitLoad(RegisterID* dst, JSValue* v)
 582 {
 583     emitOpcode(op_load);
 584     instructions().append(dst->index());
 585     instructions().append(addConstant(v));
 586     return dst;
 587 }
 588
 589 RegisterID* CodeGenerator::emitNullaryOp(OpcodeID opcode, RegisterID* dst)
 590 {
 591     emitOpcode(opcode);
 592     instructions().append(dst->index());
 593     return dst;
 594 }
 595
 596 bool CodeGenerator::findScopedProperty(const Identifier& property, int& index, size_t& stackDepth)
 597 {
 598     // Cases where we cannot optimise the lookup
 599     if (property == propertyNames().arguments || !canOptimizeNonLocals()) {
 600         stackDepth = 0;
 601         index = missingSymbolMarker();
 602         return false;
 603     }
 604
 605     ScopeChainIterator iter = m_scopeChain->begin();
 606     ScopeChainIterator end = m_scopeChain->end();
 607     size_t depth = 0;
 608
 609     for (; iter != end; ++iter, ++depth) {
 610         JSObject* currentScope = *iter;
 611         if (!currentScope->isVariableObject())
 612             break;
 613         JSVariableObject* currentVariableObject = static_cast<JSVariableObject*>(currentScope);
 614         SymbolTableEntry entry = currentVariableObject->symbolTable().get(property.ustring().rep());
 615
 616         // Found the property
 617         if (!entry.isNull()) {
 618             stackDepth = depth;
 619             index = entry.getIndex();
 620             return true;
 621         }
 622         if (currentVariableObject->isDynamicScope())
 623             break;
 624     }
 625
 626     // Can't locate the property but we're able to avoid a few lookups
 627     stackDepth = depth;
 628     index = missingSymbolMarker();
 629     return true;
 630 }
 631
 632 RegisterID* CodeGenerator::emitResolve(RegisterID* dst, const Identifier& property)
 633 {
 634     size_t depth = 0;
 635     int index = 0;
 636     if (!findScopedProperty(property, index, depth)) {
 637         // We can't optimise at all :-(
 638         emitOpcode(op_resolve);
 639         instructions().append(dst->index());
 640         instructions().append(addConstant(property));
 641         return dst;
 642     }
 643
 644     if (index == missingSymbolMarker()) {
 645         // In this case we are at least able to drop a few scope chains from the
 646         // lookup chain, although we still need to hash from then on.
 647         emitOpcode(op_resolve_skip);
 648         instructions().append(dst->index());
 649         instructions().append(addConstant(property));
 650         instructions().append(depth);
 651         return dst;
 652     }
 653
 654     // Directly index the property lookup across multiple scopes.  Yay!
 655     return emitGetScopedVar(dst, depth, index);
 656 }
 657
 658 RegisterID* CodeGenerator::emitGetScopedVar(RegisterID* dst, size_t depth, int index)
 659 {
 660     emitOpcode(op_get_scoped_var);
 661     instructions().append(dst->index());
 662     instructions().append(index);
 663     instructions().append(depth);
 664     return dst;
 665 }
 666
 667 RegisterID* CodeGenerator::emitPutScopedVar(size_t depth, int index, RegisterID* value)
 668 {
 669     emitOpcode(op_put_scoped_var);
 670     instructions().append(index);
 671     instructions().append(depth);
 672     instructions().append(value->index());
 673     return value;
 674 }
 675
 676 RegisterID* CodeGenerator::emitResolveBase(RegisterID* dst, const Identifier& property)
 677 {
 678     emitOpcode(op_resolve_base);
 679     instructions().append(dst->index());
 680     instructions().append(addConstant(property));
 681     return dst;
 682 }
 683
 684 RegisterID* CodeGenerator::emitResolveWithBase(RegisterID* baseDst, RegisterID* propDst, const Identifier& property)
 685 {
 686     emitOpcode(op_resolve_with_base);
 687     instructions().append(baseDst->index());
 688     instructions().append(propDst->index());
 689     instructions().append(addConstant(property));
 690     return baseDst;
 691 }
 692
 693 RegisterID* CodeGenerator::emitResolveFunction(RegisterID* baseDst, RegisterID* funcDst, const Identifier& property)
 694 {
 695     emitOpcode(op_resolve_func);
 696     instructions().append(baseDst->index());
 697     instructions().append(funcDst->index());
 698     instructions().append(addConstant(property));
 699     return baseDst;
 700 }
 701
 702 RegisterID* CodeGenerator::emitGetById(RegisterID* dst, RegisterID* base, const Identifier& property)
 703 {
 704     emitOpcode(op_get_by_id);
 705     instructions().append(dst->index());
 706     instructions().append(base->index());
 707     instructions().append(addConstant(property));
 708     return dst;
 709 }
 710
 711 RegisterID* CodeGenerator::emitPutById(RegisterID* base, const Identifier& property, RegisterID* value)
 712 {
 713     emitOpcode(op_put_by_id);
 714     instructions().append(base->index());
 715     instructions().append(addConstant(property));
 716     instructions().append(value->index());
 717     return value;
 718 }
 719
 720 RegisterID* CodeGenerator::emitPutGetter(RegisterID* base, const Identifier& property, RegisterID* value)
 721 {
 722     emitOpcode(op_put_getter);
 723     instructions().append(base->index());
 724     instructions().append(addConstant(property));
 725     instructions().append(value->index());
 726     return value;
 727 }
 728
 729 RegisterID* CodeGenerator::emitPutSetter(RegisterID* base, const Identifier& property, RegisterID* value)
 730 {
 731     emitOpcode(op_put_setter);
 732     instructions().append(base->index());
 733     instructions().append(addConstant(property));
 734     instructions().append(value->index());
 735     return value;
 736 }
 737
 738 RegisterID* CodeGenerator::emitDeleteById(RegisterID* dst, RegisterID* base, const Identifier& property)
 739 {
 740     emitOpcode(op_del_by_id);
 741     instructions().append(dst->index());
 742     instructions().append(base->index());
 743     instructions().append(addConstant(property));
 744     return dst;
 745 }
 746
 747 RegisterID* CodeGenerator::emitGetByVal(RegisterID* dst, RegisterID* base, RegisterID* property)
 748 {
 749     emitOpcode(op_get_by_val);
 750     instructions().append(dst->index());
 751     instructions().append(base->index());
 752     instructions().append(property->index());
 753     return dst;
 754 }
 755
 756 RegisterID* CodeGenerator::emitPutByVal(RegisterID* base, RegisterID* property, RegisterID* value)
 757 {
 758     emitOpcode(op_put_by_val);
 759     instructions().append(base->index());
 760     instructions().append(property->index());
 761     instructions().append(value->index());
 762     return value;
 763 }
 764
 765 RegisterID* CodeGenerator::emitDeleteByVal(RegisterID* dst, RegisterID* base, RegisterID* property)
 766 {
 767     emitOpcode(op_del_by_val);
 768     instructions().append(dst->index());
 769     instructions().append(base->index());
 770     instructions().append(property->index());
 771     return dst;
 772 }
 773
 774 RegisterID* CodeGenerator::emitPutByIndex(RegisterID* base, unsigned index, RegisterID* value)
 775 {
 776     emitOpcode(op_put_by_index);
 777     instructions().append(base->index());
 778     instructions().append(index);
 779     instructions().append(value->index());
 780     return value;
 781 }
 782
 783 RegisterID* CodeGenerator::emitNewFunction(RegisterID* r0, FuncDeclNode* n)
 784 {
 785     emitOpcode(op_new_func);
 786     instructions().append(r0->index());
 787     instructions().append(addConstant(n));
 788     return r0;
 789 }
 790
 791 RegisterID* CodeGenerator::emitNewRegExp(RegisterID* dst, RegExp* regExp)
 792 {
 793     emitOpcode(op_new_regexp);
 794     instructions().append(dst->index());
 795     instructions().append(addRegExp(regExp));
 796     return dst;
 797 }
 798
 799
 800 RegisterID* CodeGenerator::emitNewFunctionExpression(RegisterID* r0, FuncExprNode* n)
 801 {
 802     emitOpcode(op_new_func_exp);
 803     instructions().append(r0->index());
 804     instructions().append(addConstant(n));
 805     return r0;
 806 }
 807
 808 RegisterID* CodeGenerator::emitCall(RegisterID* dst, RegisterID* func, RegisterID* base, ArgumentsNode* argumentsNode)
 809 {
 810     return emitCall(op_call, dst, func, base, argumentsNode);
 811 }
 812
 813 RegisterID* CodeGenerator::emitCallEval(RegisterID* dst, RegisterID* func, RegisterID* base, ArgumentsNode* argumentsNode)
 814 {
 815     return emitCall(op_call_eval, dst, func, base, argumentsNode);
 816 }
 817
 818 RegisterID* CodeGenerator::emitCall(OpcodeID opcodeID, RegisterID* dst, RegisterID* func, RegisterID* base, ArgumentsNode* argumentsNode)
 819 {
 820     ASSERT(opcodeID == op_call || opcodeID == op_call_eval);
 821
 822     RefPtr<RegisterID> refFunc = func;
 823     RefPtr<RegisterID> refBase = base;
 824
 825     // Reserve space for call frame.
 826     Vector<RefPtr<RegisterID>, Machine::CallFrameHeaderSize> callFrame;
 827     for (int i = 0; i < Machine::CallFrameHeaderSize; ++i)
 828         callFrame.append(newTemporary());
 829
 830     // Generate code for arguments.
 831     Vector<RefPtr<RegisterID>, 16> argv;
 832     argv.append(newTemporary()); // reserve space for "this"
 833     for (ArgumentListNode* n = argumentsNode->m_listNode.get(); n; n = n->m_next.get()) {
 834         argv.append(newTemporary());
 835         emitNode(argv.last().get(), n);
 836     }
 837
 838     emitOpcode(opcodeID);
 839     instructions().append(dst->index());
 840     instructions().append(func->index());
 841     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.
 842     instructions().append(argv.size() ? argv[0]->index() : m_temporaries.size()); // argv
 843     instructions().append(argv.size()); // argc
 844     return dst;
 845 }
 846
 847 RegisterID* CodeGenerator::emitUnaryNoDstOp(OpcodeID opcode, RegisterID* src)
 848 {
 849     emitOpcode(opcode);
 850     instructions().append(src->index());
 851     return src;
 852 }
 853
 854 RegisterID* CodeGenerator::emitConstruct(RegisterID* dst, RegisterID* func, ArgumentsNode* argumentsNode)
 855 {
 856     // Reserve space for call frame.
 857     Vector<RefPtr<RegisterID>, Machine::CallFrameHeaderSize> callFrame;
 858     for (int i = 0; i < Machine::CallFrameHeaderSize; ++i)
 859         callFrame.append(newTemporary());
 860
 861     // Generate code for arguments.
 862     Vector<RefPtr<RegisterID>, 16> argv;
 863     argv.append(newTemporary()); // reserve space for "this"
 864     for (ArgumentListNode* n = argumentsNode ? argumentsNode->m_listNode.get() : 0; n; n = n->m_next.get()) {
 865         argv.append(newTemporary());
 866         emitNode(argv.last().get(), n);
 867     }
 868
 869     emitOpcode(op_construct);
 870     instructions().append(dst->index());
 871     instructions().append(func->index());
 872     instructions().append(argv.size() ? argv[0]->index() : m_temporaries.size()); // argv
 873     instructions().append(argv.size()); // argc
 874     return dst;
 875 }
 876
 877 RegisterID* CodeGenerator::emitPushScope(RegisterID* scope)
 878 {
 879     m_codeBlock->needsFullScopeChain = true;
 880     ControlFlowContext context;
 881     context.isFinallyBlock = false;
 882     m_scopeContextStack.append(context);
 883     m_dynamicScopeDepth++;
 884
 885     return emitUnaryNoDstOp(op_push_scope, scope);
 886 }
 887
 888 void CodeGenerator::emitPopScope()
 889 {
 890     ASSERT(m_scopeContextStack.size());
 891     ASSERT(!m_scopeContextStack.last().isFinallyBlock);
 892
 893     emitOpcode(op_pop_scope);
 894
 895     m_scopeContextStack.removeLast();
 896     m_dynamicScopeDepth--;
 897 }
 898
 899 void CodeGenerator::emitDebugHook(DebugHookID debugHookID, int firstLine, int lastLine)
 900 {
 901     if (!m_shouldEmitDebugHooks)
 902         return;
 903     emitOpcode(op_debug);
 904     instructions().append(debugHookID);
 905     instructions().append(firstLine);
 906     instructions().append(lastLine);
 907 }
 908
 909 void CodeGenerator::pushFinallyContext(LabelID* target, RegisterID* retAddrDst)
 910 {
 911     ControlFlowContext scope;
 912     scope.isFinallyBlock = true;
 913     FinallyContext context = { target, retAddrDst };
 914     scope.finallyContext = context;
 915     m_scopeContextStack.append(scope);
 916     m_finallyDepth++;
 917 }
 918
 919 void CodeGenerator::popFinallyContext()
 920 {
 921     ASSERT(m_scopeContextStack.size());
 922     ASSERT(m_scopeContextStack.last().isFinallyBlock);
 923     ASSERT(m_finallyDepth > 0);
 924     m_scopeContextStack.removeLast();
 925     m_finallyDepth--;
 926 }
 927
 928 void CodeGenerator::pushJumpContext(LabelStack* labels, LabelID* continueTarget, LabelID* breakTarget, bool isValidUnlabeledBreakTarget)
 929 {
 930     JumpContext context = { labels, continueTarget, breakTarget, scopeDepth(), isValidUnlabeledBreakTarget };
 931     m_jumpContextStack.append(context);
 932     if (continueTarget)
 933         m_continueDepth++;
 934 }
 935
 936 void CodeGenerator::popJumpContext()
 937 {
 938     ASSERT(m_jumpContextStack.size());
 939     if (m_jumpContextStack.last().continueTarget)
 940         m_continueDepth--;
 941     m_jumpContextStack.removeLast();
 942 }
 943
 944 JumpContext* CodeGenerator::jumpContextForContinue(const Identifier& label)
 945 {
 946     if(!m_jumpContextStack.size())
 947         return 0;
 948
 949     if (label.isEmpty()) {
 950         for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
 951             JumpContext* scope = &m_jumpContextStack[i];
 952             if (scope->continueTarget)
 953                 return scope;
 954         }
 955         return 0;
 956     }
 957
 958     for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
 959         JumpContext* scope = &m_jumpContextStack[i];
 960         if (scope->labels->contains(label))
 961             return scope;
 962     }
 963     return 0;
 964 }
 965
 966 JumpContext* CodeGenerator::jumpContextForBreak(const Identifier& label)
 967 {
 968     if(!m_jumpContextStack.size())
 969         return 0;
 970
 971     if (label.isEmpty()) {
 972         for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
 973             JumpContext* scope = &m_jumpContextStack[i];
 974             if (scope->isValidUnlabeledBreakTarget)
 975                 return scope;
 976         }
 977         return 0;
 978     }
 979
 980     for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
 981         JumpContext* scope = &m_jumpContextStack[i];
 982         if (scope->labels->contains(label))
 983             return scope;
 984     }
 985     return 0;
 986 }
 987
 988 PassRefPtr<LabelID> CodeGenerator::emitComplexJumpScopes(LabelID* target, ControlFlowContext* topScope, ControlFlowContext* bottomScope)
 989 {
 990     while (topScope > bottomScope) {
 991         // First we count the number of dynamic scopes we need to remove to get
 992         // to a finally block.
 993         int nNormalScopes = 0;
 994         while (topScope > bottomScope) {
 995             if (topScope->isFinallyBlock)
 996                 break;
 997             ++nNormalScopes;
 998             --topScope;
 999         }
1000
1001         if (nNormalScopes) {
1002             // We need to remove a number of dynamic scopes to get to the next
1003             // finally block
1004             emitOpcode(op_jmp_scopes);
1005             instructions().append(nNormalScopes);
1006
1007             // If topScope == bottomScope then there isn't actually a finally block
1008             // left to emit, so make the jmp_scopes jump directly to the target label
1009             if (topScope == bottomScope) {
1010                 instructions().append(target->offsetFrom(instructions().size()));
1011                 return target;
1012             }
1013
1014             // Otherwise we just use jmp_scopes to pop a group of scopes and go
1015             // to the next instruction
1016             RefPtr<LabelID> nextInsn = newLabel();
1017             instructions().append(nextInsn->offsetFrom(instructions().size()));
1018             emitLabel(nextInsn.get());
1019         }
1020
1021         // To get here there must be at least one finally block present
1022         do {
1023             ASSERT(topScope->isFinallyBlock);
1024             emitJumpSubroutine(topScope->finallyContext.retAddrDst, topScope->finallyContext.finallyAddr);
1025             --topScope;
1026             if (!topScope->isFinallyBlock)
1027                 break;
1028         } while (topScope > bottomScope);
1029     }
1030     return emitJump(target);
1031 }
1032
1033 PassRefPtr<LabelID> CodeGenerator::emitJumpScopes(LabelID* target, int targetScopeDepth)
1034 {
1035     ASSERT(scopeDepth() - targetScopeDepth >= 0);
1036     ASSERT(target->isForwardLabel());
1037
1038     size_t scopeDelta = scopeDepth() - targetScopeDepth;
1039     ASSERT(scopeDelta <= m_scopeContextStack.size());
1040     if (!scopeDelta)
1041         return emitJump(target);
1042
1043     if (m_finallyDepth)
1044         return emitComplexJumpScopes(target, &m_scopeContextStack.last(), &m_scopeContextStack.last() - scopeDelta);
1045
1046     emitOpcode(op_jmp_scopes);
1047     instructions().append(scopeDelta);
1048     instructions().append(target->offsetFrom(instructions().size()));
1049     return target;
1050 }
1051
1052 RegisterID* CodeGenerator::emitNextPropertyName(RegisterID* dst, RegisterID* iter, LabelID* target)
1053 {
1054     emitOpcode(op_next_pname);
1055     instructions().append(dst->index());
1056     instructions().append(iter->index());
1057     instructions().append(target->offsetFrom(instructions().size()));
1058     return dst;
1059 }
1060
1061 RegisterID* CodeGenerator::emitCatch(RegisterID* targetRegister, LabelID* start, LabelID* end)
1062 {
1063     HandlerInfo info = { start->offsetFrom(0), end->offsetFrom(0), instructions().size(), m_dynamicScopeDepth };
1064     exceptionHandlers().append(info);
1065     emitOpcode(op_catch);
1066     instructions().append(targetRegister->index());
1067     return targetRegister;
1068 }
1069
1070 RegisterID* CodeGenerator::emitNewError(RegisterID* dst, ErrorType type, JSValue* message)
1071 {
1072     emitOpcode(op_new_error);
1073     instructions().append(dst->index());
1074     instructions().append(static_cast<int>(type));
1075     instructions().append(addConstant(message));
1076     return dst;
1077 }
1078
1079 PassRefPtr<LabelID> CodeGenerator::emitJumpSubroutine(RegisterID* retAddrDst, LabelID* finally)
1080 {
1081     emitOpcode(op_jsr);
1082     instructions().append(retAddrDst->index());
1083     instructions().append(finally->offsetFrom(instructions().size()));
1084     return finally;
1085 }
1086
1087 void CodeGenerator::emitSubroutineReturn(RegisterID* retAddrSrc)
1088 {
1089     emitOpcode(op_sret);
1090     instructions().append(retAddrSrc->index());
1091 }
1092
1093 } // namespace KJS