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 "BatchedTransitionOptimizer.h"
  34 #include "JSFunction.h"
  35 #include "Machine.h"
  36 #include "ustring.h"
  37
  38 using namespace std;
  39
  40 namespace JSC {
  41
  42 /*
  43     The layout of a register frame looks like this:
  44
  45     For
  46
  47     function f(x, y) {
  48         var v1;
  49         function g() { }
  50         var v2;
  51         return (x) * (y);
  52     }
  53
  54     assuming (x) and (y) generated temporaries t1 and t2, you would have
  55
  56     ------------------------------------
  57     |  x |  y |  g | v2 | v1 | t1 | t2 | <-- value held
  58     ------------------------------------
  59     | -5 | -4 | -3 | -2 | -1 | +0 | +1 | <-- register index
  60     ------------------------------------
  61     | params->|<-locals      | temps->
  62
  63     Because temporary registers are allocated in a stack-like fashion, we
  64     can reclaim them with a simple popping algorithm. The same goes for labels.
  65     (We never reclaim parameter or local registers, because parameters and
  66     locals are DontDelete.)
  67
  68     The register layout before a function call looks like this:
  69
  70     For
  71
  72     function f(x, y)
  73     {
  74     }
  75
  76     f(1);
  77
  78     >                        <------------------------------
  79     <                        >  reserved: call frame  |  1 | <-- value held
  80     >         >snip<         <------------------------------
  81     <                        > +0 | +1 | +2 | +3 | +4 | +5 | <-- register index
  82     >                        <------------------------------
  83     | params->|<-locals      | temps->
  84
  85     The call instruction fills in the "call frame" registers. It also pads
  86     missing arguments at the end of the call:
  87
  88     >                        <-----------------------------------
  89     <                        >  reserved: call frame  |  1 |  ? | <-- value held ("?" stands for "undefined")
  90     >         >snip<         <-----------------------------------
  91     <                        > +0 | +1 | +2 | +3 | +4 | +5 | +6 | <-- register index
  92     >                        <-----------------------------------
  93     | params->|<-locals      | temps->
  94
  95     After filling in missing arguments, the call instruction sets up the new
  96     stack frame to overlap the end of the old stack frame:
  97
  98                              |---------------------------------->                        <
  99                              |  reserved: call frame  |  1 |  ? <                        > <-- value held ("?" stands for "undefined")
 100                              |---------------------------------->         >snip<         <
 101                              | -7 | -6 | -5 | -4 | -3 | -2 | -1 <                        > <-- register index
 102                              |---------------------------------->                        <
 103                              |                        | params->|<-locals       | temps->
 104
 105     That way, arguments are "copied" into the callee's stack frame for free.
 106
 107     If the caller supplies too many arguments, this trick doesn't work. The
 108     extra arguments protrude into space reserved for locals and temporaries.
 109     In that case, the call instruction makes a real copy of the call frame header,
 110     along with just the arguments expected by the callee, leaving the original
 111     call frame header and arguments behind. (The call instruction can't just discard
 112     extra arguments, because the "arguments" object may access them later.)
 113     This copying strategy ensures that all named values will be at the indices
 114     expected by the callee.
 115 */
 116
 117 #ifndef NDEBUG
 118 bool CodeGenerator::s_dumpsGeneratedCode = false;
 119 #endif
 120
 121 void CodeGenerator::setDumpsGeneratedCode(bool dumpsGeneratedCode)
 122 {
 123 #ifndef NDEBUG
 124     s_dumpsGeneratedCode = dumpsGeneratedCode;
 125 #else
 126     UNUSED_PARAM(dumpsGeneratedCode);
 127 #endif
 128 }
 129
 130 void CodeGenerator::generate()
 131 {
 132     m_codeBlock->numLocals = m_codeBlock->numVars + m_codeBlock->numParameters;
 133     m_codeBlock->thisRegister = m_thisRegister.index();
 134     if (m_shouldEmitDebugHooks)
 135         m_codeBlock->needsFullScopeChain = true;
 136
 137     m_scopeNode->emitCode(*this);
 138
 139 #ifndef NDEBUG
 140     if (s_dumpsGeneratedCode) {
 141         JSGlobalObject* globalObject = m_scopeChain->globalObject();
 142         m_codeBlock->dump(globalObject->globalExec());
 143     }
 144 #endif
 145
 146     m_scopeNode->children().shrinkCapacity(0);
 147     if (m_codeType != EvalCode) { // eval code needs to hang on to its declaration stacks to keep declaration info alive until Machine::execute time.
 148         m_scopeNode->varStack().shrinkCapacity(0);
 149         m_scopeNode->functionStack().shrinkCapacity(0);
 150     }
 151 }
 152
 153 bool CodeGenerator::addVar(const Identifier& ident, bool isConstant, RegisterID*& r0)
 154 {
 155     int index = m_nextVar;
 156     SymbolTableEntry newEntry(index, isConstant ? ReadOnly : 0);
 157     pair<SymbolTable::iterator, bool> result = symbolTable().add(ident.ustring().rep(), newEntry);
 158
 159     if (!result.second)
 160         index = result.first->second.getIndex();
 161     else {
 162         --m_nextVar;
 163         ++m_codeBlock->numVars;
 164
 165         m_locals.append(index);
 166     }
 167
 168     r0 = &m_locals[localsIndex(index)];
 169     return result.second;
 170 }
 171
 172 bool CodeGenerator::addGlobalVar(const Identifier& ident, bool isConstant, RegisterID*& r0)
 173 {
 174     int index = m_nextVar;
 175     SymbolTableEntry newEntry(index, isConstant ? ReadOnly : 0);
 176     pair<SymbolTable::iterator, bool> result = symbolTable().add(ident.ustring().rep(), newEntry);
 177
 178     if (!result.second)
 179         index = result.first->second.getIndex();
 180     else {
 181         --m_nextVar;
 182         m_locals.append(index + m_globalVarStorageOffset);
 183     }
 184
 185     r0 = &m_locals[localsIndex(index)];
 186     return result.second;
 187 }
 188
 189 CodeGenerator::CodeGenerator(ProgramNode* programNode, const Debugger* debugger, const ScopeChain& scopeChain, SymbolTable* symbolTable, CodeBlock* codeBlock, VarStack& varStack, FunctionStack& functionStack)
 190     : m_shouldEmitDebugHooks(!!debugger)
 191     , m_scopeChain(&scopeChain)
 192     , m_symbolTable(symbolTable)
 193     , m_scopeNode(programNode)
 194     , m_codeBlock(codeBlock)
 195     , m_thisRegister(RegisterFile::ProgramCodeThisRegister)
 196     , m_finallyDepth(0)
 197     , m_dynamicScopeDepth(0)
 198     , m_codeType(GlobalCode)
 199     , m_continueDepth(0)
 200     , m_nextVar(-1)
 201     , m_globalData(&scopeChain.globalObject()->globalExec()->globalData())
 202     , m_lastOpcodeID(op_end)
 203 {
 204     codeBlock->globalData = m_globalData;
 205
 206     // FIXME: Move code that modifies the global object to Machine::execute.
 207
 208     m_codeBlock->numConstants = programNode->neededConstants();
 209     m_codeBlock->numVars = 1; // Allocate space for "this"
 210
 211     JSGlobalObject* globalObject = scopeChain.globalObject();
 212     ExecState* exec = globalObject->globalExec();
 213     RegisterFile* registerFile = &exec->globalData().machine->registerFile();
 214
 215     // Shift register indexes in generated code to elide registers allocated by intermediate stack frames.
 216     m_globalVarStorageOffset = -1 - RegisterFile::CallFrameHeaderSize - registerFile->size();
 217
 218     // Add previously defined symbols to bookkeeping.
 219     m_locals.resize(symbolTable->size());
 220     SymbolTable::iterator end = symbolTable->end();
 221     for (SymbolTable::iterator it = symbolTable->begin(); it != end; ++it)
 222         m_locals[localsIndex(it->second.getIndex())].setIndex(it->second.getIndex() + m_globalVarStorageOffset);
 223
 224     BatchedTransitionOptimizer optimizer(globalObject);
 225
 226     bool canOptimizeNewGlobals = symbolTable->size() + functionStack.size() + varStack.size() < registerFile->maxGlobals();
 227     if (canOptimizeNewGlobals) {
 228         // Shift new symbols so they get stored prior to existing symbols.
 229         m_nextVar -= symbolTable->size();
 230
 231         for (size_t i = 0; i < functionStack.size(); ++i) {
 232             FuncDeclNode* funcDecl = functionStack[i].get();
 233             globalObject->removeDirect(funcDecl->m_ident); // Make sure our new function is not shadowed by an old property.
 234             emitNewFunction(addGlobalVar(funcDecl->m_ident, false), funcDecl);
 235         }
 236
 237         for (size_t i = 0; i < varStack.size(); ++i) {
 238             if (!globalObject->hasProperty(exec, varStack[i].first))
 239                 emitLoad(addGlobalVar(varStack[i].first, varStack[i].second & DeclarationStacks::IsConstant), jsUndefined());
 240         }
 241     } else {
 242         for (size_t i = 0; i < functionStack.size(); ++i) {
 243             FuncDeclNode* funcDecl = functionStack[i].get();
 244             globalObject->putWithAttributes(exec, funcDecl->m_ident, funcDecl->makeFunction(exec, scopeChain.node()), DontDelete);
 245         }
 246         for (size_t i = 0; i < varStack.size(); ++i) {
 247             if (globalObject->hasProperty(exec, varStack[i].first))
 248                 continue;
 249             int attributes = DontDelete;
 250             if (varStack[i].second & DeclarationStacks::IsConstant)
 251                 attributes |= ReadOnly;
 252             globalObject->putWithAttributes(exec, varStack[i].first, jsUndefined(), attributes);
 253         }
 254     }
 255 }
 256
 257 CodeGenerator::CodeGenerator(FunctionBodyNode* functionBody, const Debugger* debugger, const ScopeChain& scopeChain, SymbolTable* symbolTable, CodeBlock* codeBlock)
 258     : m_shouldEmitDebugHooks(!!debugger)
 259     , m_scopeChain(&scopeChain)
 260     , m_symbolTable(symbolTable)
 261     , m_scopeNode(functionBody)
 262     , m_codeBlock(codeBlock)
 263     , m_finallyDepth(0)
 264     , m_dynamicScopeDepth(0)
 265     , m_codeType(FunctionCode)
 266     , m_continueDepth(0)
 267     , m_nextVar(-1)
 268     , m_globalData(&scopeChain.globalObject()->globalExec()->globalData())
 269     , m_lastOpcodeID(op_end)
 270 {
 271     codeBlock->globalData = m_globalData;
 272
 273     m_codeBlock->numConstants = functionBody->neededConstants();
 274
 275     const Node::FunctionStack& functionStack = functionBody->functionStack();
 276     for (size_t i = 0; i < functionStack.size(); ++i) {
 277         FuncDeclNode* funcDecl = functionStack[i].get();
 278         const Identifier& ident = funcDecl->m_ident;
 279
 280         m_functions.add(ident.ustring().rep());
 281         emitNewFunction(addVar(ident, false), funcDecl);
 282     }
 283
 284     const Node::VarStack& varStack = functionBody->varStack();
 285     for (size_t i = 0; i < varStack.size(); ++i) {
 286         const Identifier& ident = varStack[i].first;
 287         if (ident == propertyNames().arguments)
 288             continue;
 289         addVar(ident, varStack[i].second & DeclarationStacks::IsConstant);
 290     }
 291
 292     Vector<Identifier>& parameters = functionBody->parameters();
 293     m_nextParameter = m_nextVar - parameters.size(); // parameters are allocated prior to vars
 294     m_locals.resize(localsIndex(m_nextParameter) + 1); // localsIndex of 0 => m_locals size of 1
 295
 296     // Add "this" as a parameter
 297     m_thisRegister.setIndex(m_nextParameter);
 298     ++m_nextParameter;
 299     ++m_codeBlock->numParameters;
 300
 301     for (size_t i = 0; i < parameters.size(); ++i)
 302         addParameter(parameters[i]);
 303 }
 304
 305 CodeGenerator::CodeGenerator(EvalNode* evalNode, const Debugger* debugger, const ScopeChain& scopeChain, SymbolTable* symbolTable, EvalCodeBlock* codeBlock)
 306     : m_shouldEmitDebugHooks(!!debugger)
 307     , m_scopeChain(&scopeChain)
 308     , m_symbolTable(symbolTable)
 309     , m_scopeNode(evalNode)
 310     , m_codeBlock(codeBlock)
 311     , m_thisRegister(RegisterFile::ProgramCodeThisRegister)
 312     , m_finallyDepth(0)
 313     , m_dynamicScopeDepth(0)
 314     , m_codeType(EvalCode)
 315     , m_continueDepth(0)
 316     , m_globalData(&scopeChain.globalObject()->globalExec()->globalData())
 317     , m_lastOpcodeID(op_end)
 318 {
 319     codeBlock->globalData = m_globalData;
 320
 321     m_codeBlock->numConstants = evalNode->neededConstants();
 322     m_codeBlock->numVars = 1; // Allocate space for "this"
 323 }
 324
 325 CodeGenerator::~CodeGenerator()
 326 {
 327 }
 328
 329 RegisterID* CodeGenerator::addParameter(const Identifier& ident)
 330 {
 331     // Parameters overwrite var declarations, but not function declarations,
 332     // in the symbol table.
 333     RegisterID* result = 0;
 334     UString::Rep* rep = ident.ustring().rep();
 335     if (!m_functions.contains(rep)) {
 336         symbolTable().set(rep, m_nextParameter);
 337         m_locals[localsIndex(m_nextParameter)].setIndex(m_nextParameter);
 338         result = &(m_locals[localsIndex(m_nextParameter)]);
 339     }
 340
 341     // To maintain the calling convention, we have to allocate unique space for
 342     // each parameter, even if the parameter doesn't make it into the symbol table.
 343     ++m_nextParameter;
 344     ++m_codeBlock->numParameters;
 345     return result;
 346 }
 347
 348 RegisterID* CodeGenerator::registerForLocal(const Identifier& ident)
 349 {
 350     if (m_codeType == FunctionCode && ident == propertyNames().arguments)
 351         m_codeBlock->needsFullScopeChain = true;
 352
 353     if (ident == propertyNames().thisIdentifier)
 354         return &m_thisRegister;
 355
 356     if (!shouldOptimizeLocals())
 357         return 0;
 358
 359     SymbolTableEntry entry = symbolTable().get(ident.ustring().rep());
 360     if (entry.isNull())
 361         return 0;
 362
 363     return &m_locals[localsIndex(entry.getIndex())];
 364 }
 365
 366 RegisterID* CodeGenerator::registerForLocalConstInit(const Identifier& ident)
 367 {
 368     if (m_codeType == EvalCode)
 369         return 0;
 370
 371     SymbolTableEntry entry = symbolTable().get(ident.ustring().rep());
 372     ASSERT(!entry.isNull());
 373
 374     return &m_locals[localsIndex(entry.getIndex())];
 375 }
 376
 377 bool CodeGenerator::isLocal(const Identifier& ident)
 378 {
 379     if (ident == propertyNames().thisIdentifier)
 380         return true;
 381
 382     return shouldOptimizeLocals() && symbolTable().contains(ident.ustring().rep());
 383 }
 384
 385 bool CodeGenerator::isLocalConstant(const Identifier& ident)
 386 {
 387     return symbolTable().get(ident.ustring().rep()).isReadOnly();
 388 }
 389
 390 RegisterID* CodeGenerator::newTemporary()
 391 {
 392     // Reclaim free register IDs.
 393     while (m_temporaries.size() && !m_temporaries.last().refCount())
 394         m_temporaries.removeLast();
 395
 396     // Allocate new register ID.
 397     m_temporaries.append(m_temporaries.size() + m_codeBlock->numConstants);
 398     m_codeBlock->numTemporaries = max<int>(m_codeBlock->numTemporaries, m_temporaries.size());
 399     return &m_temporaries.last();
 400 }
 401
 402 RegisterID* CodeGenerator::highestUsedRegister()
 403 {
 404     while (m_temporaries.size() < static_cast<unsigned>(m_codeBlock->numTemporaries))
 405         m_temporaries.append(m_temporaries.size());
 406     return &m_temporaries.last();
 407 }
 408
 409 PassRefPtr<LabelID> CodeGenerator::newLabel()
 410 {
 411     // Reclaim free label IDs.
 412     while (m_labels.size() && !m_labels.last().refCount())
 413         m_labels.removeLast();
 414
 415     // Allocate new label ID.
 416     m_labels.append(m_codeBlock);
 417     return &m_labels.last();
 418 }
 419
 420 PassRefPtr<LabelID> CodeGenerator::emitLabel(LabelID* l0)
 421 {
 422     l0->setLocation(instructions().size());
 423
 424     // This disables peephole optimizations when an instruction is a jump target
 425     m_lastOpcodeID = op_end;
 426
 427     return l0;
 428 }
 429
 430 void CodeGenerator::emitOpcode(OpcodeID opcodeID)
 431 {
 432     instructions().append(globalData()->machine->getOpcode(opcodeID));
 433     m_lastOpcodeID = opcodeID;
 434 }
 435
 436 void CodeGenerator::retrieveLastBinaryOp(int& dstIndex, int& src1Index, int& src2Index)
 437 {
 438     ASSERT(instructions().size() >= 4);
 439     size_t size = instructions().size();
 440     dstIndex = instructions().at(size - 3).u.operand;
 441     src1Index = instructions().at(size - 2).u.operand;
 442     src2Index = instructions().at(size - 1).u.operand;
 443 }
 444
 445 void CodeGenerator::retrieveLastUnaryOp(int& dstIndex, int& srcIndex)
 446 {
 447     ASSERT(instructions().size() >= 3);
 448     size_t size = instructions().size();
 449     dstIndex = instructions().at(size - 2).u.operand;
 450     srcIndex = instructions().at(size - 1).u.operand;
 451 }
 452
 453 void ALWAYS_INLINE CodeGenerator::rewindBinaryOp()
 454 {
 455     ASSERT(instructions().size() >= 4);
 456     instructions().shrink(instructions().size() - 4);
 457 }
 458
 459 void ALWAYS_INLINE CodeGenerator::rewindUnaryOp()
 460 {
 461     ASSERT(instructions().size() >= 3);
 462     instructions().shrink(instructions().size() - 3);
 463 }
 464
 465 PassRefPtr<LabelID> CodeGenerator::emitJump(LabelID* target)
 466 {
 467     emitOpcode(target->isForwardLabel() ? op_jmp : op_loop);
 468     instructions().append(target->offsetFrom(instructions().size()));
 469     return target;
 470 }
 471
 472 PassRefPtr<LabelID> CodeGenerator::emitJumpIfTrue(RegisterID* cond, LabelID* target)
 473 {
 474     if (m_lastOpcodeID == op_less && !target->isForwardLabel()) {
 475         int dstIndex;
 476         int src1Index;
 477         int src2Index;
 478
 479         retrieveLastBinaryOp(dstIndex, src1Index, src2Index);
 480
 481         if (cond->index() == dstIndex && cond->isTemporary() && !cond->refCount()) {
 482             rewindBinaryOp();
 483             emitOpcode(op_loop_if_less);
 484             instructions().append(src1Index);
 485             instructions().append(src2Index);
 486             instructions().append(target->offsetFrom(instructions().size()));
 487             return target;
 488         }
 489     } else if (m_lastOpcodeID == op_lesseq && !target->isForwardLabel()) {
 490         int dstIndex;
 491         int src1Index;
 492         int src2Index;
 493
 494         retrieveLastBinaryOp(dstIndex, src1Index, src2Index);
 495
 496         if (cond->index() == dstIndex && cond->isTemporary() && !cond->refCount()) {
 497             rewindBinaryOp();
 498             emitOpcode(op_loop_if_lesseq);
 499             instructions().append(src1Index);
 500             instructions().append(src2Index);
 501             instructions().append(target->offsetFrom(instructions().size()));
 502             return target;
 503         }
 504     }
 505
 506     emitOpcode(target->isForwardLabel() ? op_jtrue : op_loop_if_true);
 507     instructions().append(cond->index());
 508     instructions().append(target->offsetFrom(instructions().size()));
 509     return target;
 510 }
 511
 512 PassRefPtr<LabelID> CodeGenerator::emitJumpIfFalse(RegisterID* cond, LabelID* target)
 513 {
 514     ASSERT(target->isForwardLabel());
 515
 516     if (m_lastOpcodeID == op_less) {
 517         int dstIndex;
 518         int src1Index;
 519         int src2Index;
 520
 521         retrieveLastBinaryOp(dstIndex, src1Index, src2Index);
 522
 523         if (cond->index() == dstIndex && cond->isTemporary() && !cond->refCount()) {
 524             rewindBinaryOp();
 525             emitOpcode(op_jnless);
 526             instructions().append(src1Index);
 527             instructions().append(src2Index);
 528             instructions().append(target->offsetFrom(instructions().size()));
 529             return target;
 530         }
 531     } else if (m_lastOpcodeID == op_not) {
 532         int dstIndex;
 533         int srcIndex;
 534
 535         retrieveLastUnaryOp(dstIndex, srcIndex);
 536
 537         if (cond->index() == dstIndex && cond->isTemporary() && !cond->refCount()) {
 538             rewindUnaryOp();
 539             emitOpcode(target->isForwardLabel() ? op_jtrue : op_loop_if_true);
 540             instructions().append(srcIndex);
 541             instructions().append(target->offsetFrom(instructions().size()));
 542             return target;
 543         }
 544     }
 545
 546     emitOpcode(op_jfalse);
 547     instructions().append(cond->index());
 548     instructions().append(target->offsetFrom(instructions().size()));
 549     return target;
 550 }
 551
 552 unsigned CodeGenerator::addConstant(FuncDeclNode* n)
 553 {
 554     // No need to explicitly unique function body nodes -- they're unique already.
 555     int index = m_codeBlock->functions.size();
 556     m_codeBlock->functions.append(n);
 557     return index;
 558 }
 559
 560 unsigned CodeGenerator::addConstant(FuncExprNode* n)
 561 {
 562     // No need to explicitly unique function expression nodes -- they're unique already.
 563     int index = m_codeBlock->functionExpressions.size();
 564     m_codeBlock->functionExpressions.append(n);
 565     return index;
 566 }
 567
 568 unsigned CodeGenerator::addConstant(const Identifier& ident)
 569 {
 570     UString::Rep* rep = ident.ustring().rep();
 571     pair<IdentifierMap::iterator, bool> result = m_identifierMap.add(rep, m_codeBlock->identifiers.size());
 572     if (result.second) // new entry
 573         m_codeBlock->identifiers.append(Identifier(m_globalData, rep));
 574
 575     return result.first->second;
 576 }
 577
 578 RegisterID* CodeGenerator::addConstant(JSValue* v)
 579 {
 580     pair<JSValueMap::iterator, bool> result = m_jsValueMap.add(v, m_codeBlock->constantRegisters.size());
 581     if (result.second) {
 582         m_constants.append(m_codeBlock->constantRegisters.size());
 583         m_constants.last().makeConstant();
 584         m_codeBlock->constantRegisters.append(v);
 585         ASSERT(m_codeBlock->constantRegisters.size() <= (unsigned) m_codeBlock->numConstants);
 586         return &m_constants.last();
 587     }
 588
 589     return &m_constants[result.first->second];
 590 }
 591
 592 unsigned CodeGenerator::addUnexpectedConstant(JSValue* v)
 593 {
 594     int index = m_codeBlock->unexpectedConstants.size();
 595     m_codeBlock->unexpectedConstants.append(v);
 596     return index;
 597 }
 598
 599 unsigned CodeGenerator::addRegExp(RegExp* r)
 600 {
 601     int index = m_codeBlock->regexps.size();
 602     m_codeBlock->regexps.append(r);
 603     return index;
 604 }
 605
 606 RegisterID* CodeGenerator::emitMove(RegisterID* dst, RegisterID* src)
 607 {
 608     emitOpcode(op_mov);
 609     instructions().append(dst->index());
 610     instructions().append(src->index());
 611     return dst;
 612 }
 613
 614 RegisterID* CodeGenerator::emitUnaryOp(OpcodeID opcode, RegisterID* dst, RegisterID* src)
 615 {
 616     emitOpcode(opcode);
 617     instructions().append(dst->index());
 618     instructions().append(src->index());
 619     return dst;
 620 }
 621
 622 RegisterID* CodeGenerator::emitPreInc(RegisterID* srcDst)
 623 {
 624     emitOpcode(op_pre_inc);
 625     instructions().append(srcDst->index());
 626     return srcDst;
 627 }
 628
 629 RegisterID* CodeGenerator::emitPreDec(RegisterID* srcDst)
 630 {
 631     emitOpcode(op_pre_dec);
 632     instructions().append(srcDst->index());
 633     return srcDst;
 634 }
 635
 636 RegisterID* CodeGenerator::emitPostInc(RegisterID* dst, RegisterID* srcDst)
 637 {
 638     emitOpcode(op_post_inc);
 639     instructions().append(dst->index());
 640     instructions().append(srcDst->index());
 641     return dst;
 642 }
 643
 644 RegisterID* CodeGenerator::emitPostDec(RegisterID* dst, RegisterID* srcDst)
 645 {
 646     emitOpcode(op_post_dec);
 647     instructions().append(dst->index());
 648     instructions().append(srcDst->index());
 649     return dst;
 650 }
 651
 652 RegisterID* CodeGenerator::emitBinaryOp(OpcodeID opcode, RegisterID* dst, RegisterID* src1, RegisterID* src2)
 653 {
 654     emitOpcode(opcode);
 655     instructions().append(dst->index());
 656     instructions().append(src1->index());
 657     instructions().append(src2->index());
 658     return dst;
 659 }
 660
 661 RegisterID* CodeGenerator::emitEqualityOp(OpcodeID opcode, RegisterID* dst, RegisterID* src1, RegisterID* src2)
 662 {
 663     if (m_lastOpcodeID == op_typeof) {
 664         int dstIndex;
 665         int srcIndex;
 666
 667         retrieveLastUnaryOp(dstIndex, srcIndex);
 668
 669         if (src1->index() == dstIndex
 670             && src1->isTemporary()
 671             && static_cast<unsigned>(src2->index()) < m_codeBlock->constantRegisters.size()
 672             && m_codeBlock->constantRegisters[src2->index()].jsValue(globalExec())->isString()) {
 673             const UString& value = static_cast<JSString*>(m_codeBlock->constantRegisters[src2->index()].jsValue(globalExec()))->value();
 674             if (value == "undefined") {
 675                 rewindUnaryOp();
 676                 emitOpcode(op_is_undefined);
 677                 instructions().append(dst->index());
 678                 instructions().append(srcIndex);
 679                 return dst;
 680             }
 681             if (value == "boolean") {
 682                 rewindUnaryOp();
 683                 emitOpcode(op_is_boolean);
 684                 instructions().append(dst->index());
 685                 instructions().append(srcIndex);
 686                 return dst;
 687             }
 688             if (value == "number") {
 689                 rewindUnaryOp();
 690                 emitOpcode(op_is_number);
 691                 instructions().append(dst->index());
 692                 instructions().append(srcIndex);
 693                 return dst;
 694             }
 695             if (value == "string") {
 696                 rewindUnaryOp();
 697                 emitOpcode(op_is_string);
 698                 instructions().append(dst->index());
 699                 instructions().append(srcIndex);
 700                 return dst;
 701             }
 702             if (value == "object") {
 703                 rewindUnaryOp();
 704                 emitOpcode(op_is_object);
 705                 instructions().append(dst->index());
 706                 instructions().append(srcIndex);
 707                 return dst;
 708             }
 709             if (value == "function") {
 710                 rewindUnaryOp();
 711                 emitOpcode(op_is_function);
 712                 instructions().append(dst->index());
 713                 instructions().append(srcIndex);
 714                 return dst;
 715             }
 716         }
 717     }
 718
 719     emitOpcode(opcode);
 720     instructions().append(dst->index());
 721     instructions().append(src1->index());
 722     instructions().append(src2->index());
 723     return dst;
 724 }
 725
 726 RegisterID* CodeGenerator::emitLoad(RegisterID* dst, bool b)
 727 {
 728     return emitLoad(dst, jsBoolean(b));
 729 }
 730
 731 RegisterID* CodeGenerator::emitLoad(RegisterID* dst, double d)
 732 {
 733     return emitLoad(dst, jsNumber(globalExec(), d));
 734 }
 735
 736 RegisterID* CodeGenerator::emitLoad(RegisterID* dst, JSValue* v)
 737 {
 738     RegisterID* constantID = addConstant(v);
 739     if (dst)
 740         return emitMove(dst, constantID);
 741     return constantID;
 742 }
 743
 744 RegisterID* CodeGenerator::emitUnexpectedLoad(RegisterID* dst, bool b)
 745 {
 746     emitOpcode(op_unexpected_load);
 747     instructions().append(dst->index());
 748     instructions().append(addUnexpectedConstant(jsBoolean(b)));
 749     return dst;
 750 }
 751
 752 RegisterID* CodeGenerator::emitUnexpectedLoad(RegisterID* dst, double d)
 753 {
 754     emitOpcode(op_unexpected_load);
 755     instructions().append(dst->index());
 756     instructions().append(addUnexpectedConstant(jsNumber(globalExec(), d)));
 757     return dst;
 758 }
 759
 760 bool CodeGenerator::findScopedProperty(const Identifier& property, int& index, size_t& stackDepth, bool forWriting, JSValue*& globalObject)
 761 {
 762     // Cases where we cannot statically optimise the lookup
 763     if (property == propertyNames().arguments || !canOptimizeNonLocals()) {
 764         stackDepth = 0;
 765         index = missingSymbolMarker();
 766
 767         if (shouldOptimizeLocals() && m_codeType == GlobalCode) {
 768             ScopeChainIterator iter = m_scopeChain->begin();
 769             globalObject = *iter;
 770             ASSERT((++iter) == m_scopeChain->end());
 771         }
 772         return false;
 773     }
 774
 775     size_t depth = 0;
 776
 777     ScopeChainIterator iter = m_scopeChain->begin();
 778     ScopeChainIterator end = m_scopeChain->end();
 779     for (; iter != end; ++iter, ++depth) {
 780         JSObject* currentScope = *iter;
 781         if (!currentScope->isVariableObject())
 782             break;
 783         JSVariableObject* currentVariableObject = static_cast<JSVariableObject*>(currentScope);
 784         SymbolTableEntry entry = currentVariableObject->symbolTable().get(property.ustring().rep());
 785
 786         // Found the property
 787         if (!entry.isNull()) {
 788             if (entry.isReadOnly() && forWriting) {
 789                 stackDepth = 0;
 790                 index = missingSymbolMarker();
 791                 if (++iter == end)
 792                     globalObject = currentVariableObject;
 793                 return false;
 794             }
 795             stackDepth = depth;
 796             index = entry.getIndex();
 797             if (++iter == end)
 798                 globalObject = currentVariableObject;
 799             return true;
 800         }
 801         if (currentVariableObject->isDynamicScope())
 802             break;
 803     }
 804
 805     // Can't locate the property but we're able to avoid a few lookups
 806     stackDepth = depth;
 807     index = missingSymbolMarker();
 808     JSObject* scope = *iter;
 809     if (++iter == end)
 810         globalObject = scope;
 811     return true;
 812 }
 813
 814 RegisterID* CodeGenerator::emitInstanceOf(RegisterID* dst, RegisterID* value, RegisterID* base, RegisterID* basePrototype)
 815 {
 816     emitOpcode(op_instanceof);
 817     instructions().append(dst->index());
 818     instructions().append(value->index());
 819     instructions().append(base->index());
 820     instructions().append(basePrototype->index());
 821     return dst;
 822 }
 823
 824 RegisterID* CodeGenerator::emitResolve(RegisterID* dst, const Identifier& property)
 825 {
 826     size_t depth = 0;
 827     int index = 0;
 828     JSValue* globalObject = 0;
 829     if (!findScopedProperty(property, index, depth, false, globalObject) && !globalObject) {
 830         // We can't optimise at all :-(
 831         emitOpcode(op_resolve);
 832         instructions().append(dst->index());
 833         instructions().append(addConstant(property));
 834         return dst;
 835     }
 836
 837     if (index != missingSymbolMarker()) {
 838         // Directly index the property lookup across multiple scopes.  Yay!
 839         return emitGetScopedVar(dst, depth, index, globalObject);
 840     }
 841
 842     if (globalObject) {
 843         m_codeBlock->structureIDInstructions.append(instructions().size());
 844         emitOpcode(op_resolve_global);
 845         instructions().append(dst->index());
 846         instructions().append(static_cast<JSCell*>(globalObject));
 847         instructions().append(addConstant(property));
 848         instructions().append(0);
 849         instructions().append(0);
 850         return dst;
 851     }
 852
 853     // In this case we are at least able to drop a few scope chains from the
 854     // lookup chain, although we still need to hash from then on.
 855     emitOpcode(op_resolve_skip);
 856     instructions().append(dst->index());
 857     instructions().append(addConstant(property));
 858     instructions().append(depth);
 859     return dst;
 860 }
 861
 862 RegisterID* CodeGenerator::emitGetScopedVar(RegisterID* dst, size_t depth, int index, JSValue* globalObject)
 863 {
 864     if (globalObject) {
 865         emitOpcode(op_get_global_var);
 866         instructions().append(dst->index());
 867         instructions().append(static_cast<JSCell*>(globalObject));
 868         instructions().append(index);
 869         return dst;
 870     }
 871
 872     emitOpcode(op_get_scoped_var);
 873     instructions().append(dst->index());
 874     instructions().append(index);
 875     instructions().append(depth);
 876     return dst;
 877 }
 878
 879 RegisterID* CodeGenerator::emitPutScopedVar(size_t depth, int index, RegisterID* value, JSValue* globalObject)
 880 {
 881     if (globalObject) {
 882         emitOpcode(op_put_global_var);
 883         instructions().append(static_cast<JSCell*>(globalObject));
 884         instructions().append(index);
 885         instructions().append(value->index());
 886         return value;
 887     }
 888     emitOpcode(op_put_scoped_var);
 889     instructions().append(index);
 890     instructions().append(depth);
 891     instructions().append(value->index());
 892     return value;
 893 }
 894
 895 RegisterID* CodeGenerator::emitResolveBase(RegisterID* dst, const Identifier& property)
 896 {
 897     emitOpcode(op_resolve_base);
 898     instructions().append(dst->index());
 899     instructions().append(addConstant(property));
 900     return dst;
 901 }
 902
 903 RegisterID* CodeGenerator::emitResolveWithBase(RegisterID* baseDst, RegisterID* propDst, const Identifier& property)
 904 {
 905     emitOpcode(op_resolve_with_base);
 906     instructions().append(baseDst->index());
 907     instructions().append(propDst->index());
 908     instructions().append(addConstant(property));
 909     return baseDst;
 910 }
 911
 912 RegisterID* CodeGenerator::emitResolveFunction(RegisterID* baseDst, RegisterID* funcDst, const Identifier& property)
 913 {
 914     emitOpcode(op_resolve_func);
 915     instructions().append(baseDst->index());
 916     instructions().append(funcDst->index());
 917     instructions().append(addConstant(property));
 918     return baseDst;
 919 }
 920
 921 RegisterID* CodeGenerator::emitGetById(RegisterID* dst, RegisterID* base, const Identifier& property)
 922 {
 923     m_codeBlock->structureIDInstructions.append(instructions().size());
 924
 925     emitOpcode(op_get_by_id);
 926     instructions().append(dst->index());
 927     instructions().append(base->index());
 928     instructions().append(addConstant(property));
 929     instructions().append(0);
 930     instructions().append(0);
 931     instructions().append(0);
 932     instructions().append(0);
 933     return dst;
 934 }
 935
 936 RegisterID* CodeGenerator::emitPutById(RegisterID* base, const Identifier& property, RegisterID* value)
 937 {
 938     m_codeBlock->structureIDInstructions.append(instructions().size());
 939
 940     emitOpcode(op_put_by_id);
 941     instructions().append(base->index());
 942     instructions().append(addConstant(property));
 943     instructions().append(value->index());
 944     instructions().append(0);
 945     instructions().append(0);
 946     instructions().append(0);
 947     instructions().append(0);
 948     return value;
 949 }
 950
 951 RegisterID* CodeGenerator::emitPutGetter(RegisterID* base, const Identifier& property, RegisterID* value)
 952 {
 953     emitOpcode(op_put_getter);
 954     instructions().append(base->index());
 955     instructions().append(addConstant(property));
 956     instructions().append(value->index());
 957     return value;
 958 }
 959
 960 RegisterID* CodeGenerator::emitPutSetter(RegisterID* base, const Identifier& property, RegisterID* value)
 961 {
 962     emitOpcode(op_put_setter);
 963     instructions().append(base->index());
 964     instructions().append(addConstant(property));
 965     instructions().append(value->index());
 966     return value;
 967 }
 968
 969 RegisterID* CodeGenerator::emitDeleteById(RegisterID* dst, RegisterID* base, const Identifier& property)
 970 {
 971     emitOpcode(op_del_by_id);
 972     instructions().append(dst->index());
 973     instructions().append(base->index());
 974     instructions().append(addConstant(property));
 975     return dst;
 976 }
 977
 978 RegisterID* CodeGenerator::emitGetByVal(RegisterID* dst, RegisterID* base, RegisterID* property)
 979 {
 980     emitOpcode(op_get_by_val);
 981     instructions().append(dst->index());
 982     instructions().append(base->index());
 983     instructions().append(property->index());
 984     return dst;
 985 }
 986
 987 RegisterID* CodeGenerator::emitPutByVal(RegisterID* base, RegisterID* property, RegisterID* value)
 988 {
 989     emitOpcode(op_put_by_val);
 990     instructions().append(base->index());
 991     instructions().append(property->index());
 992     instructions().append(value->index());
 993     return value;
 994 }
 995
 996 RegisterID* CodeGenerator::emitDeleteByVal(RegisterID* dst, RegisterID* base, RegisterID* property)
 997 {
 998     emitOpcode(op_del_by_val);
 999     instructions().append(dst->index());
1000     instructions().append(base->index());
1001     instructions().append(property->index());
1002     return dst;
1003 }
1004
1005 RegisterID* CodeGenerator::emitPutByIndex(RegisterID* base, unsigned index, RegisterID* value)
1006 {
1007     emitOpcode(op_put_by_index);
1008     instructions().append(base->index());
1009     instructions().append(index);
1010     instructions().append(value->index());
1011     return value;
1012 }
1013
1014 RegisterID* CodeGenerator::emitNewObject(RegisterID* dst)
1015 {
1016     emitOpcode(op_new_object);
1017     instructions().append(dst->index());
1018     return dst;
1019 }
1020
1021 RegisterID* CodeGenerator::emitNewArray(RegisterID* dst, ElementNode* elements)
1022 {
1023     Vector<RefPtr<RegisterID>, 16> argv;
1024     for (ElementNode* n = elements; n; n = n->next()) {
1025         if (n->elision())
1026             break;
1027         argv.append(newTemporary());
1028         emitNode(argv.last().get(), n->value());
1029     }
1030     emitOpcode(op_new_array);
1031     instructions().append(dst->index());
1032     instructions().append(argv.size() ? argv[0]->index() : 0); // argv
1033     instructions().append(argv.size()); // argc
1034     return dst;
1035 }
1036
1037 RegisterID* CodeGenerator::emitNewFunction(RegisterID* dst, FuncDeclNode* n)
1038 {
1039     emitOpcode(op_new_func);
1040     instructions().append(dst->index());
1041     instructions().append(addConstant(n));
1042     return dst;
1043 }
1044
1045 RegisterID* CodeGenerator::emitNewRegExp(RegisterID* dst, RegExp* regExp)
1046 {
1047     emitOpcode(op_new_regexp);
1048     instructions().append(dst->index());
1049     instructions().append(addRegExp(regExp));
1050     return dst;
1051 }
1052
1053
1054 RegisterID* CodeGenerator::emitNewFunctionExpression(RegisterID* r0, FuncExprNode* n)
1055 {
1056     emitOpcode(op_new_func_exp);
1057     instructions().append(r0->index());
1058     instructions().append(addConstant(n));
1059     return r0;
1060 }
1061
1062 RegisterID* CodeGenerator::emitCall(RegisterID* dst, RegisterID* func, RegisterID* base, ArgumentsNode* argumentsNode, unsigned divot, unsigned startOffset, unsigned endOffset)
1063 {
1064     return emitCall(op_call, dst, func, base, argumentsNode, divot, startOffset, endOffset);
1065 }
1066
1067 RegisterID* CodeGenerator::emitCallEval(RegisterID* dst, RegisterID* func, RegisterID* base, ArgumentsNode* argumentsNode, unsigned divot, unsigned startOffset, unsigned endOffset)
1068 {
1069     return emitCall(op_call_eval, dst, func, base, argumentsNode, divot, startOffset, endOffset);
1070 }
1071
1072 RegisterID* CodeGenerator::emitCall(OpcodeID opcodeID, RegisterID* dst, RegisterID* func, RegisterID* base, ArgumentsNode* argumentsNode, unsigned divot, unsigned startOffset, unsigned endOffset)
1073 {
1074     ASSERT(opcodeID == op_call || opcodeID == op_call_eval);
1075
1076     // Ordinarily, we might ref "func" and "base", to avoid allocating new
1077     // temporaries in the same registers. In this case, though, we actually
1078     // want the call frame we allocate to overlap "func" and "base", if they're
1079     // not otherwise referenced. op_call will read "func" and "base" before
1080     // writing out the call frame, so this is safe.
1081
1082     // Reserve space for call frame.
1083     Vector<RefPtr<RegisterID>, RegisterFile::CallFrameHeaderSize> callFrame;
1084     for (int i = 0; i < RegisterFile::CallFrameHeaderSize; ++i)
1085         callFrame.append(newTemporary());
1086
1087     // Generate code for arguments.
1088     Vector<RefPtr<RegisterID>, 16> argv;
1089     argv.append(newTemporary()); // reserve space for "this"
1090     for (ArgumentListNode* n = argumentsNode->m_listNode.get(); n; n = n->m_next.get()) {
1091         argv.append(newTemporary());
1092         emitNode(argv.last().get(), n);
1093     }
1094
1095     emitExpressionInfo(divot, startOffset, endOffset);
1096     emitOpcode(opcodeID);
1097     instructions().append(dst->index());
1098     instructions().append(func->index());
1099     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.
1100     instructions().append(argv[0]->index()); // argv
1101     instructions().append(argv.size()); // argc
1102     return dst;
1103 }
1104
1105 RegisterID* CodeGenerator::emitUnaryNoDstOp(OpcodeID opcode, RegisterID* src)
1106 {
1107     emitOpcode(opcode);
1108     instructions().append(src->index());
1109     return src;
1110 }
1111
1112 RegisterID* CodeGenerator::emitConstruct(RegisterID* dst, RegisterID* func, ArgumentsNode* argumentsNode)
1113 {
1114     // Ordinarily, we might ref "func", to avoid allocating a new temporary in
1115     // the same register. In this case, though, we actually want the call
1116     // frame we allocate to overlap "func", if it's not otherwise referenced.
1117     // op_construct will read "func" before writing out the call frame, so this
1118     // is safe.
1119
1120     RefPtr<RegisterID> protectFunc = func;
1121
1122     // Reserve space for prototype
1123     RefPtr<RegisterID> funcProto = newTemporary();
1124
1125     // Reserve space for call frame.
1126     Vector<RefPtr<RegisterID>, RegisterFile::CallFrameHeaderSize> callFrame;
1127     for (int i = 0; i < RegisterFile::CallFrameHeaderSize; ++i)
1128         callFrame.append(newTemporary());
1129
1130     // Generate code for arguments.
1131     Vector<RefPtr<RegisterID>, 16> argv;
1132     argv.append(newTemporary()); // reserve space for "this"
1133     for (ArgumentListNode* n = argumentsNode ? argumentsNode->m_listNode.get() : 0; n; n = n->m_next.get()) {
1134         argv.append(newTemporary());
1135         emitNode(argv.last().get(), n);
1136     }
1137
1138     emitGetById(funcProto.get(), func, globalExec()->propertyNames().prototype);
1139
1140     emitOpcode(op_construct);
1141     instructions().append(dst->index());
1142     instructions().append(func->index());
1143     instructions().append(funcProto->index());
1144     instructions().append(argv[0]->index()); // argv
1145     instructions().append(argv.size()); // argc
1146
1147     emitOpcode(op_construct_verify);
1148     instructions().append(dst->index());
1149     instructions().append(argv[0]->index());
1150
1151     return dst;
1152 }
1153
1154 RegisterID* CodeGenerator::emitPushScope(RegisterID* scope)
1155 {
1156     m_codeBlock->needsFullScopeChain = true;
1157     ControlFlowContext context;
1158     context.isFinallyBlock = false;
1159     m_scopeContextStack.append(context);
1160     m_dynamicScopeDepth++;
1161
1162     return emitUnaryNoDstOp(op_push_scope, scope);
1163 }
1164
1165 void CodeGenerator::emitPopScope()
1166 {
1167     ASSERT(m_scopeContextStack.size());
1168     ASSERT(!m_scopeContextStack.last().isFinallyBlock);
1169
1170     emitOpcode(op_pop_scope);
1171
1172     m_scopeContextStack.removeLast();
1173     m_dynamicScopeDepth--;
1174 }
1175
1176 void CodeGenerator::emitDebugHook(DebugHookID debugHookID, int firstLine, int lastLine)
1177 {
1178     if (!m_shouldEmitDebugHooks)
1179         return;
1180     emitOpcode(op_debug);
1181     instructions().append(debugHookID);
1182     instructions().append(firstLine);
1183     instructions().append(lastLine);
1184 }
1185
1186 void CodeGenerator::pushFinallyContext(LabelID* target, RegisterID* retAddrDst)
1187 {
1188     ControlFlowContext scope;
1189     scope.isFinallyBlock = true;
1190     FinallyContext context = { target, retAddrDst };
1191     scope.finallyContext = context;
1192     m_scopeContextStack.append(scope);
1193     m_finallyDepth++;
1194 }
1195
1196 void CodeGenerator::popFinallyContext()
1197 {
1198     ASSERT(m_scopeContextStack.size());
1199     ASSERT(m_scopeContextStack.last().isFinallyBlock);
1200     ASSERT(m_finallyDepth > 0);
1201     m_scopeContextStack.removeLast();
1202     m_finallyDepth--;
1203 }
1204
1205 void CodeGenerator::pushJumpContext(LabelStack* labels, LabelID* continueTarget, LabelID* breakTarget, bool isValidUnlabeledBreakTarget)
1206 {
1207     JumpContext context = { labels, continueTarget, breakTarget, scopeDepth(), isValidUnlabeledBreakTarget };
1208     m_jumpContextStack.append(context);
1209     if (continueTarget)
1210         m_continueDepth++;
1211 }
1212
1213 void CodeGenerator::popJumpContext()
1214 {
1215     ASSERT(m_jumpContextStack.size());
1216     if (m_jumpContextStack.last().continueTarget)
1217         m_continueDepth--;
1218     m_jumpContextStack.removeLast();
1219 }
1220
1221 JumpContext* CodeGenerator::jumpContextForContinue(const Identifier& label)
1222 {
1223     if(!m_jumpContextStack.size())
1224         return 0;
1225
1226     if (label.isEmpty()) {
1227         for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
1228             JumpContext* scope = &m_jumpContextStack[i];
1229             if (scope->continueTarget)
1230                 return scope;
1231         }
1232         return 0;
1233     }
1234
1235     for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
1236         JumpContext* scope = &m_jumpContextStack[i];
1237         if (scope->labels->contains(label))
1238             return scope;
1239     }
1240     return 0;
1241 }
1242
1243 JumpContext* CodeGenerator::jumpContextForBreak(const Identifier& label)
1244 {
1245     if(!m_jumpContextStack.size())
1246         return 0;
1247
1248     if (label.isEmpty()) {
1249         for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
1250             JumpContext* scope = &m_jumpContextStack[i];
1251             if (scope->isValidUnlabeledBreakTarget)
1252                 return scope;
1253         }
1254         return 0;
1255     }
1256
1257     for (int i = m_jumpContextStack.size() - 1; i >= 0; i--) {
1258         JumpContext* scope = &m_jumpContextStack[i];
1259         if (scope->labels->contains(label))
1260             return scope;
1261     }
1262     return 0;
1263 }
1264
1265 PassRefPtr<LabelID> CodeGenerator::emitComplexJumpScopes(LabelID* target, ControlFlowContext* topScope, ControlFlowContext* bottomScope)
1266 {
1267     while (topScope > bottomScope) {
1268         // First we count the number of dynamic scopes we need to remove to get
1269         // to a finally block.
1270         int nNormalScopes = 0;
1271         while (topScope > bottomScope) {
1272             if (topScope->isFinallyBlock)
1273                 break;
1274             ++nNormalScopes;
1275             --topScope;
1276         }
1277
1278         if (nNormalScopes) {
1279             // We need to remove a number of dynamic scopes to get to the next
1280             // finally block
1281             emitOpcode(op_jmp_scopes);
1282             instructions().append(nNormalScopes);
1283
1284             // If topScope == bottomScope then there isn't actually a finally block
1285             // left to emit, so make the jmp_scopes jump directly to the target label
1286             if (topScope == bottomScope) {
1287                 instructions().append(target->offsetFrom(instructions().size()));
1288                 return target;
1289             }
1290
1291             // Otherwise we just use jmp_scopes to pop a group of scopes and go
1292             // to the next instruction
1293             RefPtr<LabelID> nextInsn = newLabel();
1294             instructions().append(nextInsn->offsetFrom(instructions().size()));
1295             emitLabel(nextInsn.get());
1296         }
1297
1298         // To get here there must be at least one finally block present
1299         do {
1300             ASSERT(topScope->isFinallyBlock);
1301             emitJumpSubroutine(topScope->finallyContext.retAddrDst, topScope->finallyContext.finallyAddr);
1302             --topScope;
1303             if (!topScope->isFinallyBlock)
1304                 break;
1305         } while (topScope > bottomScope);
1306     }
1307     return emitJump(target);
1308 }
1309
1310 PassRefPtr<LabelID> CodeGenerator::emitJumpScopes(LabelID* target, int targetScopeDepth)
1311 {
1312     ASSERT(scopeDepth() - targetScopeDepth >= 0);
1313     ASSERT(target->isForwardLabel());
1314
1315     size_t scopeDelta = scopeDepth() - targetScopeDepth;
1316     ASSERT(scopeDelta <= m_scopeContextStack.size());
1317     if (!scopeDelta)
1318         return emitJump(target);
1319
1320     if (m_finallyDepth)
1321         return emitComplexJumpScopes(target, &m_scopeContextStack.last(), &m_scopeContextStack.last() - scopeDelta);
1322
1323     emitOpcode(op_jmp_scopes);
1324     instructions().append(scopeDelta);
1325     instructions().append(target->offsetFrom(instructions().size()));
1326     return target;
1327 }
1328
1329 RegisterID* CodeGenerator::emitNextPropertyName(RegisterID* dst, RegisterID* iter, LabelID* target)
1330 {
1331     emitOpcode(op_next_pname);
1332     instructions().append(dst->index());
1333     instructions().append(iter->index());
1334     instructions().append(target->offsetFrom(instructions().size()));
1335     return dst;
1336 }
1337
1338 RegisterID* CodeGenerator::emitCatch(RegisterID* targetRegister, LabelID* start, LabelID* end)
1339 {
1340     HandlerInfo info = { start->offsetFrom(0), end->offsetFrom(0), instructions().size(), m_dynamicScopeDepth, 0 };
1341     exceptionHandlers().append(info);
1342     emitOpcode(op_catch);
1343     instructions().append(targetRegister->index());
1344     return targetRegister;
1345 }
1346
1347 RegisterID* CodeGenerator::emitNewError(RegisterID* dst, ErrorType type, JSValue* message)
1348 {
1349     emitOpcode(op_new_error);
1350     instructions().append(dst->index());
1351     instructions().append(static_cast<int>(type));
1352     instructions().append(addUnexpectedConstant(message));
1353     return dst;
1354 }
1355
1356 PassRefPtr<LabelID> CodeGenerator::emitJumpSubroutine(RegisterID* retAddrDst, LabelID* finally)
1357 {
1358     emitOpcode(op_jsr);
1359     instructions().append(retAddrDst->index());
1360     instructions().append(finally->offsetFrom(instructions().size()));
1361     return finally;
1362 }
1363
1364 void CodeGenerator::emitSubroutineReturn(RegisterID* retAddrSrc)
1365 {
1366     emitOpcode(op_sret);
1367     instructions().append(retAddrSrc->index());
1368 }
1369
1370 void CodeGenerator::emitPushNewScope(RegisterID* dst, Identifier& property, RegisterID* value)
1371 {
1372     m_codeBlock->needsFullScopeChain = true;
1373     ControlFlowContext context;
1374     context.isFinallyBlock = false;
1375     m_scopeContextStack.append(context);
1376     m_dynamicScopeDepth++;
1377
1378     emitOpcode(op_push_new_scope);
1379     instructions().append(dst->index());
1380     instructions().append(addConstant(property));
1381     instructions().append(value->index());
1382 }
1383
1384 void CodeGenerator::beginSwitch(RegisterID* scrutineeRegister, SwitchInfo::SwitchType type)
1385 {
1386     SwitchInfo info = { instructions().size(), type };
1387     switch (type) {
1388         case SwitchInfo::SwitchImmediate:
1389             emitOpcode(op_switch_imm);
1390             break;
1391         case SwitchInfo::SwitchCharacter:
1392             emitOpcode(op_switch_char);
1393             break;
1394         case SwitchInfo::SwitchString:
1395             emitOpcode(op_switch_string);
1396             break;
1397         default:
1398             ASSERT_NOT_REACHED();
1399     }
1400
1401     instructions().append(0); // place holder for table index
1402     instructions().append(0); // place holder for default target
1403     instructions().append(scrutineeRegister->index());
1404     m_switchContextStack.append(info);
1405 }
1406
1407 static int32_t keyForImmediateSwitch(ExpressionNode* node, int32_t min, int32_t max)
1408 {
1409     UNUSED_PARAM(max);
1410     ASSERT(node->isNumber());
1411     double value = static_cast<NumberNode*>(node)->value();
1412     ASSERT(JSImmediate::from(value));
1413     int32_t key = static_cast<int32_t>(value);
1414     ASSERT(key == value);
1415     ASSERT(key >= min);
1416     ASSERT(key <= max);
1417     return key - min;
1418 }
1419
1420 static void prepareJumpTableForImmediateSwitch(SimpleJumpTable& jumpTable, int32_t switchAddress, uint32_t clauseCount, RefPtr<LabelID>* labels, ExpressionNode** nodes, int32_t min, int32_t max)
1421 {
1422     jumpTable.min = min;
1423     jumpTable.branchOffsets.resize(max - min + 1);
1424     jumpTable.branchOffsets.fill(0);
1425     for (uint32_t i = 0; i < clauseCount; ++i) {
1426         // We're emitting this after the clause labels should have been fixed, so
1427         // the labels should not be "forward" references
1428         ASSERT(!labels[i]->isForwardLabel());
1429         jumpTable.add(keyForImmediateSwitch(nodes[i], min, max), labels[i]->offsetFrom(switchAddress));
1430     }
1431 }
1432
1433 static int32_t keyForCharacterSwitch(ExpressionNode* node, int32_t min, int32_t max)
1434 {
1435     UNUSED_PARAM(max);
1436     ASSERT(node->isString());
1437     UString::Rep* clause = static_cast<StringNode*>(node)->value().rep();
1438     ASSERT(clause->size() == 1);
1439
1440     int32_t key = clause->data()[0];
1441     ASSERT(key >= min);
1442     ASSERT(key <= max);
1443     return key - min;
1444 }
1445
1446 static void prepareJumpTableForCharacterSwitch(SimpleJumpTable& jumpTable, int32_t switchAddress, uint32_t clauseCount, RefPtr<LabelID>* labels, ExpressionNode** nodes, int32_t min, int32_t max)
1447 {
1448     jumpTable.min = min;
1449     jumpTable.branchOffsets.resize(max - min + 1);
1450     jumpTable.branchOffsets.fill(0);
1451     for (uint32_t i = 0; i < clauseCount; ++i) {
1452         // We're emitting this after the clause labels should have been fixed, so
1453         // the labels should not be "forward" references
1454         ASSERT(!labels[i]->isForwardLabel());
1455         jumpTable.add(keyForCharacterSwitch(nodes[i], min, max), labels[i]->offsetFrom(switchAddress));
1456     }
1457 }
1458
1459 static void prepareJumpTableForStringSwitch(StringJumpTable& jumpTable, int32_t switchAddress, uint32_t clauseCount, RefPtr<LabelID>* labels, ExpressionNode** nodes)
1460 {
1461     for (uint32_t i = 0; i < clauseCount; ++i) {
1462         // We're emitting this after the clause labels should have been fixed, so
1463         // the labels should not be "forward" references
1464         ASSERT(!labels[i]->isForwardLabel());
1465
1466         ASSERT(nodes[i]->isString());
1467         UString::Rep* clause = static_cast<StringNode*>(nodes[i])->value().rep();
1468         OffsetLocation location;
1469         location.branchOffset = labels[i]->offsetFrom(switchAddress);
1470 #if ENABLE(CTI)
1471         location.ctiOffset = 0;
1472 #endif
1473         jumpTable.offsetTable.add(clause, location);
1474     }
1475 }
1476
1477 void CodeGenerator::endSwitch(uint32_t clauseCount, RefPtr<LabelID>* labels, ExpressionNode** nodes, LabelID* defaultLabel, int32_t min, int32_t max)
1478 {
1479     SwitchInfo switchInfo = m_switchContextStack.last();
1480     m_switchContextStack.removeLast();
1481     if (switchInfo.switchType == SwitchInfo::SwitchImmediate) {
1482         instructions()[switchInfo.opcodeOffset + 1] = m_codeBlock->immediateSwitchJumpTables.size();
1483         instructions()[switchInfo.opcodeOffset + 2] = defaultLabel->offsetFrom(switchInfo.opcodeOffset + 3);
1484
1485         m_codeBlock->immediateSwitchJumpTables.append(SimpleJumpTable());
1486         SimpleJumpTable& jumpTable = m_codeBlock->immediateSwitchJumpTables.last();
1487
1488         prepareJumpTableForImmediateSwitch(jumpTable, switchInfo.opcodeOffset + 3, clauseCount, labels, nodes, min, max);
1489     } else if (switchInfo.switchType == SwitchInfo::SwitchCharacter) {
1490         instructions()[switchInfo.opcodeOffset + 1] = m_codeBlock->characterSwitchJumpTables.size();
1491         instructions()[switchInfo.opcodeOffset + 2] = defaultLabel->offsetFrom(switchInfo.opcodeOffset + 3);
1492
1493         m_codeBlock->characterSwitchJumpTables.append(SimpleJumpTable());
1494         SimpleJumpTable& jumpTable = m_codeBlock->characterSwitchJumpTables.last();
1495
1496         prepareJumpTableForCharacterSwitch(jumpTable, switchInfo.opcodeOffset + 3, clauseCount, labels, nodes, min, max);
1497     } else {
1498         ASSERT(switchInfo.switchType == SwitchInfo::SwitchString);
1499         instructions()[switchInfo.opcodeOffset + 1] = m_codeBlock->stringSwitchJumpTables.size();
1500         instructions()[switchInfo.opcodeOffset + 2] = defaultLabel->offsetFrom(switchInfo.opcodeOffset + 3);
1501
1502         m_codeBlock->stringSwitchJumpTables.append(StringJumpTable());
1503         StringJumpTable& jumpTable = m_codeBlock->stringSwitchJumpTables.last();
1504
1505         prepareJumpTableForStringSwitch(jumpTable, switchInfo.opcodeOffset + 3, clauseCount, labels, nodes);
1506     }
1507 }
1508
1509 } // namespace JSC