/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- * vim: set ts=8 sts=4 et sw=4 tw=99: * This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ #include "jit/IonControlFlow.h" #include "mozilla/DebugOnly.h" using namespace js; using namespace js::jit; using mozilla::DebugOnly; ControlFlowGenerator::ControlFlowGenerator(TempAllocator& temp, JSScript* script) : script(script), current(nullptr), alloc_(temp), blocks_(temp), cfgStack_(temp), loops_(temp), switches_(temp), labels_(temp), aborted_(false), checkedTryFinally_(false) { } static inline int32_t GetJumpOffset(jsbytecode* pc) { MOZ_ASSERT(CodeSpec[JSOp(*pc)].type() == JOF_JUMP); return GET_JUMP_OFFSET(pc); } void ControlFlowGraph::dump(GenericPrinter& print, JSScript* script) { if (blocks_.length() == 0) { print.printf("Didn't run yet.\n"); return; } fprintf(stderr, "Dumping cfg:\n\n"); for (size_t i = 0; i < blocks_.length(); i++) { print.printf(" Block %zu, %zu:%zu\n", blocks_[i].id(), script->pcToOffset(blocks_[i].startPc()), script->pcToOffset(blocks_[i].stopPc())); jsbytecode* pc = blocks_[i].startPc(); for ( ; pc < blocks_[i].stopPc(); pc += CodeSpec[JSOp(*pc)].length) { MOZ_ASSERT(pc < script->codeEnd()); print.printf(" %zu: %s\n", script->pcToOffset(pc), CodeName[JSOp(*pc)]); } if (blocks_[i].stopIns()->isGoto()) { print.printf(" %s (popping:%zu) [", blocks_[i].stopIns()->Name(), blocks_[i].stopIns()->toGoto()->popAmount()); } else { print.printf(" %s [", blocks_[i].stopIns()->Name()); } for (size_t j=0; jnumSuccessors(); j++) { if (j!=0) print.printf(", "); print.printf("%zu", blocks_[i].stopIns()->getSuccessor(j)->id()); } print.printf("]\n\n"); } } bool ControlFlowGraph::init(TempAllocator& alloc, const CFGBlockVector& blocks) { if (!blocks_.reserve(blocks.length())) return false; for (size_t i = 0; i < blocks.length(); i++) { MOZ_ASSERT(blocks[i]->id() == i); CFGBlock block(blocks[i]->startPc()); block.setStopPc(blocks[i]->stopPc()); block.setId(i); blocks_.infallibleAppend(mozilla::Move(block)); } for (size_t i = 0; i < blocks.length(); i++) { if (!alloc.ensureBallast()) return false; CFGControlInstruction* copy = nullptr; CFGControlInstruction* ins = blocks[i]->stopIns(); switch (ins->type()) { case CFGControlInstruction::Type_Goto: { CFGBlock* successor = &blocks_[ins->getSuccessor(0)->id()]; copy = CFGGoto::CopyWithNewTargets(alloc, ins->toGoto(), successor); break; } case CFGControlInstruction::Type_BackEdge: { CFGBlock* successor = &blocks_[ins->getSuccessor(0)->id()]; copy = CFGBackEdge::CopyWithNewTargets(alloc, ins->toBackEdge(), successor); break; } case CFGControlInstruction::Type_LoopEntry: { CFGLoopEntry* old = ins->toLoopEntry(); CFGBlock* successor = &blocks_[ins->getSuccessor(0)->id()]; copy = CFGLoopEntry::CopyWithNewTargets(alloc, old, successor); break; } case CFGControlInstruction::Type_Throw: { copy = CFGThrow::New(alloc); break; } case CFGControlInstruction::Type_Test: { CFGTest* old = ins->toTest(); CFGBlock* trueBranch = &blocks_[old->trueBranch()->id()]; CFGBlock* falseBranch = &blocks_[old->falseBranch()->id()]; copy = CFGTest::CopyWithNewTargets(alloc, old, trueBranch, falseBranch); break; } case CFGControlInstruction::Type_Compare: { CFGCompare* old = ins->toCompare(); CFGBlock* trueBranch = &blocks_[old->trueBranch()->id()]; CFGBlock* falseBranch = &blocks_[old->falseBranch()->id()]; copy = CFGCompare::CopyWithNewTargets(alloc, old, trueBranch, falseBranch); break; } case CFGControlInstruction::Type_Return: { copy = CFGReturn::New(alloc); break; } case CFGControlInstruction::Type_RetRVal: { copy = CFGRetRVal::New(alloc); break; } case CFGControlInstruction::Type_Try: { CFGTry* old = ins->toTry(); CFGBlock* tryBlock = &blocks_[old->tryBlock()->id()]; CFGBlock* merge = nullptr; if (old->numSuccessors() == 2) merge = &blocks_[old->afterTryCatchBlock()->id()]; copy = CFGTry::CopyWithNewTargets(alloc, old, tryBlock, merge); break; } case CFGControlInstruction::Type_TableSwitch: { CFGTableSwitch* old = ins->toTableSwitch(); CFGTableSwitch* tableSwitch = CFGTableSwitch::New(alloc, old->low(), old->high()); if (!tableSwitch->addDefault(&blocks_[old->defaultCase()->id()])) return false; for (size_t i = 0; i < ins->numSuccessors() - 1; i++) { if (!tableSwitch->addCase(&blocks_[old->getCase(i)->id()])) return false; } copy = tableSwitch; break; } } MOZ_ASSERT(copy); blocks_[i].setStopIns(copy); } return true; } bool ControlFlowGenerator::addBlock(CFGBlock* block) { block->setId(blocks_.length()); return blocks_.append(block); } // We try to build a control-flow graph in the order that it would be built as // if traversing the AST. This leads to a nice ordering and lets us build SSA // in one pass, since the bytecode is structured. // // Things get interesting when we encounter a control structure. This can be // either an IFEQ, downward GOTO, or a decompiler hint stashed away in source // notes. Once we encounter such an opcode, we recover the structure of the // control flow (its branches and bounds), and push it on a stack. // // As we continue traversing the bytecode, we look for points that would // terminate the topmost control flow path pushed on the stack. These are: // (1) The bounds of the current structure (end of a loop or join/edge of a // branch). // (2) A "return", "break", or "continue" statement. // // For (1), we expect that there is a current block in the progress of being // built, and we complete the necessary edges in the CFG. For (2), we expect // that there is no active block. bool ControlFlowGenerator::traverseBytecode() { blocks_.clear(); current = CFGBlock::New(alloc(), script->code()); pc = current->startPc(); if (!addBlock(current)) return false; for (;;) { MOZ_ASSERT(pc < script->codeEnd()); for (;;) { if (!alloc().ensureBallast()) return false; // Check if we've hit an expected join point or edge in the bytecode. // Leaving one control structure could place us at the edge of another, // thus |while| instead of |if| so we don't skip any opcodes. MOZ_ASSERT_IF(!cfgStack_.empty(), cfgStack_.back().stopAt >= pc); if (!cfgStack_.empty() && cfgStack_.back().stopAt == pc) { ControlStatus status = processCfgStack(); if (status == ControlStatus::Error) return false; if (status == ControlStatus::Abort) { aborted_ = true; return false; } if (!current) return true; continue; } // Some opcodes need to be handled early because they affect control // flow, terminating the current basic block and/or instructing the // traversal algorithm to continue from a new pc. // // (1) If the opcode does not affect control flow, then the opcode // is inspected and transformed to IR. This is the process_opcode // label. // (2) A loop could be detected via a forward GOTO. In this case, // we don't want to process the GOTO, but the following // instruction. // (3) A RETURN, STOP, BREAK, or CONTINUE may require processing the // CFG stack to terminate open branches. // // Similar to above, snooping control flow could land us at another // control flow point, so we iterate until it's time to inspect a real // opcode. ControlStatus status; if ((status = snoopControlFlow(JSOp(*pc))) == ControlStatus::None) break; if (status == ControlStatus::Error) return false; if (status == ControlStatus::Abort) { aborted_ = true; return false; } if (!current) return true; } JSOp op = JSOp(*pc); pc += CodeSpec[op].length; } } ControlFlowGenerator::ControlStatus ControlFlowGenerator::snoopControlFlow(JSOp op) { switch (op) { case JSOP_POP: case JSOP_NOP: { jssrcnote* sn = GetSrcNote(gsn, script, pc); return maybeLoop(op, sn); } case JSOP_RETURN: case JSOP_RETRVAL: return processReturn(op); case JSOP_THROW: return processThrow(); case JSOP_GOTO: { jssrcnote* sn = GetSrcNote(gsn, script, pc); switch (sn ? SN_TYPE(sn) : SRC_NULL) { case SRC_BREAK: case SRC_BREAK2LABEL: return processBreak(op, sn); case SRC_CONTINUE: return processContinue(op); case SRC_SWITCHBREAK: return processSwitchBreak(op); case SRC_WHILE: case SRC_FOR_IN: case SRC_FOR_OF: // while (cond) { } return processWhileOrForInLoop(sn); default: // Hard assert for now - make an error later. MOZ_CRASH("unknown goto case"); } break; } case JSOP_TABLESWITCH: { jssrcnote* sn = GetSrcNote(gsn, script, pc); return processTableSwitch(op, sn); } case JSOP_CONDSWITCH: return processCondSwitch(); case JSOP_IFNE: // We should never reach an IFNE, it's a stopAt point, which will // trigger closing the loop. MOZ_CRASH("we should never reach an ifne!"); case JSOP_IFEQ: return processIfStart(JSOP_IFEQ); case JSOP_AND: case JSOP_OR: return processAndOr(op); case JSOP_LABEL: return processLabel(); case JSOP_TRY: return processTry(); case JSOP_THROWMSG: // Not implemented yet. return ControlStatus::Abort; default: break; } return ControlStatus::None; } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processReturn(JSOp op) { MOZ_ASSERT(op == JSOP_RETURN || op == JSOP_RETRVAL); CFGControlInstruction* ins; if (op == JSOP_RETURN) ins = CFGReturn::New(alloc()); else ins = CFGRetRVal::New(alloc()); endCurrentBlock(ins); return processControlEnd(); } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processThrow() { CFGThrow* ins = CFGThrow::New(alloc()); endCurrentBlock(ins); return processControlEnd(); } void ControlFlowGenerator::endCurrentBlock(CFGControlInstruction* ins) { current->setStopPc(pc); current->setStopIns(ins); // Make sure no one tries to use this block now. current = nullptr; } // Processes the top of the CFG stack. This is used from two places: // (1) processControlEnd(), whereby a break, continue, or return may interrupt // an in-progress CFG structure before reaching its actual termination // point in the bytecode. // (2) traverseBytecode(), whereby we reach the last instruction in a CFG // structure. ControlFlowGenerator::ControlStatus ControlFlowGenerator::processCfgStack() { ControlStatus status = processCfgEntry(cfgStack_.back()); // If this terminated a CFG structure, act like processControlEnd() and // keep propagating upward. while (status == ControlStatus::Ended) { popCfgStack(); if (cfgStack_.empty()) return status; status = processCfgEntry(cfgStack_.back()); } // If some join took place, the current structure is finished. if (status == ControlStatus::Joined) popCfgStack(); return status; } // Given that the current control flow structure has ended forcefully, // via a return, break, or continue (rather than joining), propagate the // termination up. For example, a return nested 5 loops deep may terminate // every outer loop at once, if there are no intervening conditionals: // // for (...) { // for (...) { // return x; // } // } // // If |current| is nullptr when this function returns, then there is no more // control flow to be processed. ControlFlowGenerator::ControlStatus ControlFlowGenerator::processControlEnd() { MOZ_ASSERT(!current); if (cfgStack_.empty()) { // If there is no more control flow to process, then this is the // last return in the function. return ControlStatus::Ended; } return processCfgStack(); } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processCfgEntry(CFGState& state) { switch (state.state) { case CFGState::IF_TRUE: case CFGState::IF_TRUE_EMPTY_ELSE: return processIfEnd(state); case CFGState::IF_ELSE_TRUE: return processIfElseTrueEnd(state); case CFGState::IF_ELSE_FALSE: return processIfElseFalseEnd(state); case CFGState::DO_WHILE_LOOP_BODY: return processDoWhileBodyEnd(state); case CFGState::DO_WHILE_LOOP_COND: return processDoWhileCondEnd(state); case CFGState::WHILE_LOOP_COND: return processWhileCondEnd(state); case CFGState::WHILE_LOOP_BODY: return processWhileBodyEnd(state); case CFGState::FOR_LOOP_COND: return processForCondEnd(state); case CFGState::FOR_LOOP_BODY: return processForBodyEnd(state); case CFGState::FOR_LOOP_UPDATE: return processForUpdateEnd(state); case CFGState::TABLE_SWITCH: return processNextTableSwitchCase(state); case CFGState::COND_SWITCH_CASE: return processCondSwitchCase(state); case CFGState::COND_SWITCH_BODY: return processCondSwitchBody(state); case CFGState::AND_OR: return processAndOrEnd(state); case CFGState::LABEL: return processLabelEnd(state); case CFGState::TRY: return processTryEnd(state); default: MOZ_CRASH("unknown cfgstate"); } } void ControlFlowGenerator::popCfgStack() { if (cfgStack_.back().isLoop()) loops_.popBack(); if (cfgStack_.back().state == CFGState::LABEL) labels_.popBack(); cfgStack_.popBack(); } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processLabelEnd(CFGState& state) { MOZ_ASSERT(state.state == CFGState::LABEL); // If there are no breaks and no current, controlflow is terminated. if (!state.label.breaks && !current) return ControlStatus::Ended; // If there are no breaks to this label, there's nothing to do. if (!state.label.breaks) return ControlStatus::Joined; CFGBlock* successor = createBreakCatchBlock(state.label.breaks, state.stopAt); if (!successor) return ControlStatus::Error; if (current) { current->setStopIns(CFGGoto::New(alloc(), successor)); current->setStopPc(pc); } current = successor; pc = successor->startPc(); if (!addBlock(successor)) return ControlStatus::Error; return ControlStatus::Joined; } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processTry() { MOZ_ASSERT(JSOp(*pc) == JSOP_TRY); // Try-finally is not yet supported. if (!checkedTryFinally_) { JSTryNote* tn = script->trynotes()->vector; JSTryNote* tnlimit = tn + script->trynotes()->length; for (; tn < tnlimit; tn++) { if (tn->kind == JSTRY_FINALLY) return ControlStatus::Abort; } checkedTryFinally_ = true; } jssrcnote* sn = GetSrcNote(gsn, script, pc); MOZ_ASSERT(SN_TYPE(sn) == SRC_TRY); // Get the pc of the last instruction in the try block. It's a JSOP_GOTO to // jump over the catch block. jsbytecode* endpc = pc + GetSrcNoteOffset(sn, 0); MOZ_ASSERT(JSOp(*endpc) == JSOP_GOTO); MOZ_ASSERT(GetJumpOffset(endpc) > 0); jsbytecode* afterTry = endpc + GetJumpOffset(endpc); // If controlflow in the try body is terminated (by a return or throw // statement), the code after the try-statement may still be reachable // via the catch block (which we don't compile) and OSR can enter it. // For example: // // try { // throw 3; // } catch(e) { } // // for (var i=0; i<1000; i++) {} // // To handle this, we create two blocks: one for the try block and one // for the code following the try-catch statement. CFGBlock* tryBlock = CFGBlock::New(alloc(), GetNextPc(pc)); CFGBlock* successor = CFGBlock::New(alloc(), afterTry); current->setStopIns(CFGTry::New(alloc(), tryBlock, endpc, successor)); current->setStopPc(pc); if (!cfgStack_.append(CFGState::Try(endpc, successor))) return ControlStatus::Error; current = tryBlock; pc = current->startPc(); if (!addBlock(current)) return ControlStatus::Error; return ControlStatus::Jumped; } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processTryEnd(CFGState& state) { MOZ_ASSERT(state.state == CFGState::TRY); MOZ_ASSERT(state.try_.successor); if (current) { current->setStopIns(CFGGoto::New(alloc(), state.try_.successor)); current->setStopPc(pc); } // Start parsing the code after this try-catch statement. current = state.try_.successor; pc = current->startPc(); if (!addBlock(current)) return ControlStatus::Error; return ControlStatus::Joined; } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processIfEnd(CFGState& state) { if (current) { // Here, the false block is the join point. Create an edge from the // current block to the false block. Note that a RETURN opcode // could have already ended the block. current->setStopIns(CFGGoto::New(alloc(), state.branch.ifFalse)); current->setStopPc(pc); } current = state.branch.ifFalse; pc = current->startPc(); if (!addBlock(current)) return ControlStatus::Error; return ControlStatus::Joined; } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processIfElseTrueEnd(CFGState& state) { // We've reached the end of the true branch of an if-else. Don't // create an edge yet, just transition to parsing the false branch. state.state = CFGState::IF_ELSE_FALSE; state.branch.ifTrue = current; state.stopAt = state.branch.falseEnd; if (current) current->setStopPc(pc); current = state.branch.ifFalse; pc = current->startPc(); if (!addBlock(current)) return ControlStatus::Error; return ControlStatus::Jumped; } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processIfElseFalseEnd(CFGState& state) { // Update the state to have the latest block from the false path. state.branch.ifFalse = current; if (current) current->setStopPc(pc); // To create the join node, we need an incoming edge that has not been // terminated yet. CFGBlock* pred = state.branch.ifTrue ? state.branch.ifTrue : state.branch.ifFalse; CFGBlock* other = (pred == state.branch.ifTrue) ? state.branch.ifFalse : state.branch.ifTrue; if (!pred) return ControlStatus::Ended; // Create a new block to represent the join. CFGBlock* join = CFGBlock::New(alloc(), state.branch.falseEnd); // Create edges from the true and false blocks as needed. pred->setStopIns(CFGGoto::New(alloc(), join)); if (other) other->setStopIns(CFGGoto::New(alloc(), join)); // Ignore unreachable remainder of false block if existent. current = join; pc = current->startPc(); if (!addBlock(current)) return ControlStatus::Error; return ControlStatus::Joined; } CFGBlock* ControlFlowGenerator::createBreakCatchBlock(DeferredEdge* edge, jsbytecode* pc) { // Create block, using the first break statement as predecessor CFGBlock* successor = CFGBlock::New(alloc(), pc); // Finish up remaining breaks. while (edge) { if (!alloc().ensureBallast()) return nullptr; CFGGoto* brk = CFGGoto::New(alloc(), successor); edge->block->setStopIns(brk); edge = edge->next; } return successor; } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processDoWhileBodyEnd(CFGState& state) { if (!processDeferredContinues(state)) return ControlStatus::Error; // No current means control flow cannot reach the condition, so this will // never loop. if (!current) return processBrokenLoop(state); CFGBlock* header = CFGBlock::New(alloc(), state.loop.updatepc); current->setStopIns(CFGGoto::New(alloc(), header)); current->setStopPc(pc); state.state = CFGState::DO_WHILE_LOOP_COND; state.stopAt = state.loop.updateEnd; current = header; pc = header->startPc(); if (!addBlock(current)) return ControlStatus::Error; return ControlStatus::Jumped; } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processDoWhileCondEnd(CFGState& state) { MOZ_ASSERT(JSOp(*pc) == JSOP_IFNE); // We're guaranteed a |current|, it's impossible to break or return from // inside the conditional expression. MOZ_ASSERT(current); // Create the successor block. CFGBlock* successor = CFGBlock::New(alloc(), GetNextPc(pc)); CFGLoopEntry* entry = state.loop.entry->stopIns()->toLoopEntry(); entry->setLoopStopPc(pc); // Create backedge with pc at start of loop to make sure we capture the // right stack. CFGBlock* backEdge = CFGBlock::New(alloc(), entry->successor()->startPc()); backEdge->setStopIns(CFGBackEdge::New(alloc(), entry->successor())); backEdge->setStopPc(entry->successor()->startPc()); if (!addBlock(backEdge)) return ControlStatus::Error; // Create the test instruction and end the current block. CFGTest* test = CFGTest::New(alloc(), backEdge, successor); current->setStopIns(test); current->setStopPc(pc); return finishLoop(state, successor); } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processWhileCondEnd(CFGState& state) { MOZ_ASSERT(JSOp(*pc) == JSOP_IFNE || JSOp(*pc) == JSOP_IFEQ); // Create the body and successor blocks. CFGBlock* body = CFGBlock::New(alloc(), state.loop.bodyStart); state.loop.successor = CFGBlock::New(alloc(), state.loop.exitpc); if (!body || !state.loop.successor) return ControlStatus::Error; CFGTest* test; if (JSOp(*pc) == JSOP_IFNE) test = CFGTest::New(alloc(), body, state.loop.successor); else test = CFGTest::New(alloc(), state.loop.successor, body); current->setStopIns(test); current->setStopPc(pc); state.state = CFGState::WHILE_LOOP_BODY; state.stopAt = state.loop.bodyEnd; current = body; pc = body->startPc(); if (!addBlock(current)) return ControlStatus::Error; return ControlStatus::Jumped; } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processWhileBodyEnd(CFGState& state) { if (!processDeferredContinues(state)) return ControlStatus::Error; if (!current) return processBrokenLoop(state); CFGLoopEntry* entry = state.loop.entry->stopIns()->toLoopEntry(); entry->setLoopStopPc(pc); current->setStopIns(CFGBackEdge::New(alloc(), entry->successor())); if (pc != current->startPc()) { current->setStopPc(pc); } else { // If the block is empty update the pc to the start of loop to make // sure we capture the right stack. current->setStartPc(entry->successor()->startPc()); current->setStopPc(entry->successor()->startPc()); } return finishLoop(state, state.loop.successor); } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processForCondEnd(CFGState& state) { MOZ_ASSERT(JSOp(*pc) == JSOP_IFNE); // Create the body and successor blocks. CFGBlock* body = CFGBlock::New(alloc(), state.loop.bodyStart); state.loop.successor = CFGBlock::New(alloc(), state.loop.exitpc); CFGTest* test = CFGTest::New(alloc(), body, state.loop.successor); current->setStopIns(test); current->setStopPc(pc); state.state = CFGState::FOR_LOOP_BODY; state.stopAt = state.loop.bodyEnd; current = body; pc = body->startPc(); if (!addBlock(current)) return ControlStatus::Error; return ControlStatus::Jumped; } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processForBodyEnd(CFGState& state) { if (!processDeferredContinues(state)) return ControlStatus::Error; // If there is no updatepc, just go right to processing what would be the // end of the update clause. Otherwise, |current| might be nullptr; if this is // the case, the update is unreachable anyway. if (!state.loop.updatepc || !current) return processForUpdateEnd(state); //MOZ_ASSERT(pc == state.loop.updatepc); if (state.loop.updatepc != pc) { CFGBlock* next = CFGBlock::New(alloc(), state.loop.updatepc); current->setStopIns(CFGGoto::New(alloc(), next)); current->setStopPc(pc); current = next; if (!addBlock(current)) return ControlStatus::Error; } pc = state.loop.updatepc; state.state = CFGState::FOR_LOOP_UPDATE; state.stopAt = state.loop.updateEnd; return ControlStatus::Jumped; } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processForUpdateEnd(CFGState& state) { // If there is no current, we couldn't reach the loop edge and there was no // update clause. if (!current) return processBrokenLoop(state); CFGLoopEntry* entry = state.loop.entry->stopIns()->toLoopEntry(); entry->setLoopStopPc(pc); current->setStopIns(CFGBackEdge::New(alloc(), entry->successor())); if (pc != current->startPc()) { current->setStopPc(pc); } else { // If the block is empty update the pc to the start of loop to make // sure we capture the right stack. current->setStartPc(entry->successor()->startPc()); current->setStopPc(entry->successor()->startPc()); } return finishLoop(state, state.loop.successor); } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processWhileOrForInLoop(jssrcnote* sn) { // while (cond) { } loops have the following structure: // GOTO cond ; SRC_WHILE (offset to IFNE) // LOOPHEAD // ... // cond: // LOOPENTRY // ... // IFNE ; goes to LOOPHEAD // for (x in y) { } loops are similar; the cond will be a MOREITER. MOZ_ASSERT(SN_TYPE(sn) == SRC_FOR_OF || SN_TYPE(sn) == SRC_FOR_IN || SN_TYPE(sn) == SRC_WHILE); int ifneOffset = GetSrcNoteOffset(sn, 0); jsbytecode* ifne = pc + ifneOffset; MOZ_ASSERT(ifne > pc); // Verify that the IFNE goes back to a loophead op. MOZ_ASSERT(JSOp(*GetNextPc(pc)) == JSOP_LOOPHEAD); MOZ_ASSERT(GetNextPc(pc) == ifne + GetJumpOffset(ifne)); jsbytecode* loopEntry = pc + GetJumpOffset(pc); size_t stackPhiCount; if (SN_TYPE(sn) == SRC_FOR_OF) stackPhiCount = 2; else if (SN_TYPE(sn) == SRC_FOR_IN) stackPhiCount = 1; else stackPhiCount = 0; // Skip past the JSOP_LOOPHEAD for the body start. jsbytecode* loopHead = GetNextPc(pc); jsbytecode* bodyStart = GetNextPc(loopHead); jsbytecode* bodyEnd = pc + GetJumpOffset(pc); jsbytecode* exitpc = GetNextPc(ifne); jsbytecode* continuepc = pc; CFGBlock* header = CFGBlock::New(alloc(), GetNextPc(loopEntry)); CFGLoopEntry* ins = CFGLoopEntry::New(alloc(), header, stackPhiCount); if (LoopEntryCanIonOsr(loopEntry)) ins->setCanOsr(); if (SN_TYPE(sn) == SRC_FOR_IN) ins->setIsForIn(); current->setStopIns(ins); current->setStopPc(pc); if (!pushLoop(CFGState::WHILE_LOOP_COND, ifne, current, loopHead, bodyEnd, bodyStart, bodyEnd, exitpc, continuepc)) { return ControlStatus::Error; } // Parse the condition first. current = header; pc = header->startPc(); if (!addBlock(current)) return ControlStatus::Error; return ControlStatus::Jumped; } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processBrokenLoop(CFGState& state) { MOZ_ASSERT(!current); { state.loop.entry->setStopIns( CFGGoto::New(alloc(), state.loop.entry->stopIns()->toLoopEntry()->successor())); } // If the loop started with a condition (while/for) then even if the // structure never actually loops, the condition itself can still fail and // thus we must resume at the successor, if one exists. current = state.loop.successor; if (current) { if (!addBlock(current)) return ControlStatus::Error; } // Join the breaks together and continue parsing. if (state.loop.breaks) { CFGBlock* block = createBreakCatchBlock(state.loop.breaks, state.loop.exitpc); if (!block) return ControlStatus::Error; if (current) { current->setStopIns(CFGGoto::New(alloc(), block)); current->setStopPc(current->startPc()); } current = block; if (!addBlock(current)) return ControlStatus::Error; } // If the loop is not gated on a condition, and has only returns, we'll // reach this case. For example: // do { ... return; } while (); if (!current) return ControlStatus::Ended; // Otherwise, the loop is gated on a condition and/or has breaks so keep // parsing at the successor. pc = current->startPc(); return ControlStatus::Joined; } ControlFlowGenerator::ControlStatus ControlFlowGenerator::finishLoop(CFGState& state, CFGBlock* successor) { MOZ_ASSERT(current); if (state.loop.breaks) { if (successor) { if (!addBlock(successor)) return ControlStatus::Error; } // Create a catch block to join all break exits. CFGBlock* block = createBreakCatchBlock(state.loop.breaks, state.loop.exitpc); if (!block) return ControlStatus::Error; if (successor) { // Finally, create an unconditional edge from the successor to the // catch block. successor->setStopIns(CFGGoto::New(alloc(), block)); successor->setStopPc(successor->startPc()); } successor = block; } // An infinite loop (for (;;) { }) will not have a successor. if (!successor) { current = nullptr; return ControlStatus::Ended; } current = successor; pc = current->startPc(); if (!addBlock(current)) return ControlStatus::Error; return ControlStatus::Joined; } bool ControlFlowGenerator::processDeferredContinues(CFGState& state) { // If there are any continues for this loop, and there is an update block, // then we need to create a new basic block to house the update. if (state.loop.continues) { DeferredEdge* edge = state.loop.continues; CFGBlock* update = CFGBlock::New(alloc(), pc); if (current) { current->setStopIns(CFGGoto::New(alloc(), update)); current->setStopPc(pc); } // Remaining edges while (edge) { if (!alloc().ensureBallast()) return false; edge->block->setStopIns(CFGGoto::New(alloc(), update)); edge = edge->next; } state.loop.continues = nullptr; current = update; if (!addBlock(current)) return false; } return true; } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processCondSwitch() { // CondSwitch op looks as follows: // condswitch [length +exit_pc; first case offset +next-case ] // { // { // ... any code ... // case (+jump) [pcdelta offset +next-case] // }+ // default (+jump) // ... jump targets ... // } // // The default case is always emitted even if there is no default case in // the source. The last case statement pcdelta source note might have a 0 // offset on the last case (not all the time). // // A conditional evaluate the condition of each case and compare it to the // switch value with a strict equality. Cases conditions are iterated // linearly until one is matching. If one case succeeds, the flow jumps into // the corresponding body block. The body block might alias others and // might continue in the next body block if the body is not terminated with // a break. // // Algorithm: // 1/ Loop over the case chain to reach the default target // & Estimate the number of uniq bodies. // 2/ Generate code for all cases (see processCondSwitchCase). // 3/ Generate code for all bodies (see processCondSwitchBody). MOZ_ASSERT(JSOp(*pc) == JSOP_CONDSWITCH); jssrcnote* sn = GetSrcNote(gsn, script, pc); MOZ_ASSERT(SN_TYPE(sn) == SRC_CONDSWITCH); // Get the exit pc jsbytecode* exitpc = pc + GetSrcNoteOffset(sn, 0); jsbytecode* firstCase = pc + GetSrcNoteOffset(sn, 1); // Iterate all cases in the conditional switch. // - Stop at the default case. (always emitted after the last case) // - Estimate the number of uniq bodies. This estimation might be off by 1 // if the default body alias a case body. jsbytecode* curCase = firstCase; jsbytecode* lastTarget = GetJumpOffset(curCase) + curCase; size_t nbBodies = 1; // default target and the first body. MOZ_ASSERT(pc < curCase && curCase <= exitpc); while (JSOp(*curCase) == JSOP_CASE) { // Fetch the next case. jssrcnote* caseSn = GetSrcNote(gsn, script, curCase); MOZ_ASSERT(caseSn && SN_TYPE(caseSn) == SRC_NEXTCASE); ptrdiff_t off = GetSrcNoteOffset(caseSn, 0); MOZ_ASSERT_IF(off == 0, JSOp(*GetNextPc(curCase)) == JSOP_JUMPTARGET); curCase = off ? curCase + off : GetNextPc(GetNextPc(curCase)); MOZ_ASSERT(pc < curCase && curCase <= exitpc); // Count non-aliased cases. jsbytecode* curTarget = GetJumpOffset(curCase) + curCase; if (lastTarget < curTarget) nbBodies++; lastTarget = curTarget; } // The current case now be the default case which jump to the body of the // default case, which might be behind the last target. MOZ_ASSERT(JSOp(*curCase) == JSOP_DEFAULT); jsbytecode* defaultTarget = GetJumpOffset(curCase) + curCase; MOZ_ASSERT(curCase < defaultTarget && defaultTarget <= exitpc); // Iterate over all cases again to find the position of the default block. curCase = firstCase; lastTarget = nullptr; size_t defaultIdx = 0; while (JSOp(*curCase) == JSOP_CASE) { jsbytecode* curTarget = GetJumpOffset(curCase) + curCase; if (lastTarget < defaultTarget && defaultTarget <= curTarget) { if (defaultTarget < curTarget) nbBodies++; break; } if (lastTarget < curTarget) defaultIdx++; jssrcnote* caseSn = GetSrcNote(gsn, script, curCase); ptrdiff_t off = GetSrcNoteOffset(caseSn, 0); curCase = off ? curCase + off : GetNextPc(GetNextPc(curCase)); lastTarget = curTarget; } // Allocate the current graph state. CFGState state = CFGState::CondSwitch(alloc(), exitpc, defaultTarget); if (!state.switch_.bodies || !state.switch_.bodies->init(alloc(), nbBodies)) return ControlStatus::Error; state.switch_.defaultIdx = defaultIdx; // Create the default case already. FixedList& bodies = *state.switch_.bodies; bodies[state.switch_.defaultIdx] = CFGBlock::New(alloc(), defaultTarget); // Skip default case. if (state.switch_.defaultIdx == 0) state.switch_.currentIdx++; // We loop on case conditions with processCondSwitchCase. MOZ_ASSERT(JSOp(*firstCase) == JSOP_CASE); state.stopAt = firstCase; state.state = CFGState::COND_SWITCH_CASE; if (!cfgStack_.append(state)) return ControlStatus::Error; jsbytecode* nextPc = GetNextPc(pc); CFGBlock* next = CFGBlock::New(alloc(), nextPc); current->setStopIns(CFGGoto::New(alloc(), next)); current->setStopPc(pc); current = next; pc = current->startPc(); if (!addBlock(current)) return ControlStatus::Error; return ControlStatus::Jumped; } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processCondSwitchCase(CFGState& state) { MOZ_ASSERT(state.state == CFGState::COND_SWITCH_CASE); MOZ_ASSERT(!state.switch_.breaks); MOZ_ASSERT(current); MOZ_ASSERT(JSOp(*pc) == JSOP_CASE); FixedList& bodies = *state.switch_.bodies; uint32_t& currentIdx = state.switch_.currentIdx; jsbytecode* lastTarget = currentIdx ? bodies[currentIdx - 1]->startPc() : nullptr; // Fetch the following case in which we will continue. jssrcnote* sn = GetSrcNote(gsn, script, pc); ptrdiff_t off = GetSrcNoteOffset(sn, 0); MOZ_ASSERT_IF(off == 0, JSOp(*GetNextPc(pc)) == JSOP_JUMPTARGET); jsbytecode* casePc = off ? pc + off : GetNextPc(GetNextPc(pc)); bool nextIsDefault = JSOp(*casePc) == JSOP_DEFAULT; MOZ_ASSERT(JSOp(*casePc) == JSOP_CASE || nextIsDefault); // Allocate the block of the matching case. jsbytecode* bodyTarget = pc + GetJumpOffset(pc); CFGBlock* bodyBlock = nullptr; if (lastTarget < bodyTarget) { // Skip default case. if (currentIdx == state.switch_.defaultIdx) { currentIdx++; lastTarget = bodies[currentIdx - 1]->startPc(); if (lastTarget < bodyTarget) { bodyBlock = CFGBlock::New(alloc(), bodyTarget); bodies[currentIdx++] = bodyBlock; } else { // This body alias the previous one. MOZ_ASSERT(lastTarget == bodyTarget); MOZ_ASSERT(currentIdx > 0); bodyBlock = bodies[currentIdx - 1]; } } else { bodyBlock = CFGBlock::New(alloc(), bodyTarget); bodies[currentIdx++] = bodyBlock; } } else { // This body alias the previous one. MOZ_ASSERT(lastTarget == bodyTarget); MOZ_ASSERT(currentIdx > 0); bodyBlock = bodies[currentIdx - 1]; } CFGBlock* emptyBlock = CFGBlock::New(alloc(), bodyBlock->startPc()); emptyBlock->setStopIns(CFGGoto::New(alloc(), bodyBlock)); emptyBlock->setStopPc(bodyBlock->startPc()); if (!addBlock(emptyBlock)) return ControlStatus::Error; if (nextIsDefault) { CFGBlock* defaultBlock = bodies[state.switch_.defaultIdx]; CFGBlock* emptyBlock2 = CFGBlock::New(alloc(), defaultBlock->startPc()); emptyBlock2->setStopIns(CFGGoto::New(alloc(), defaultBlock)); emptyBlock2->setStopPc(defaultBlock->startPc()); if (!addBlock(emptyBlock2)) return ControlStatus::Error; current->setStopIns(CFGCompare::NewFalseBranchIsDefault(alloc(), emptyBlock, emptyBlock2)); current->setStopPc(pc); return processCondSwitchDefault(state); } CFGBlock* nextBlock = CFGBlock::New(alloc(), GetNextPc(pc)); current->setStopIns(CFGCompare::NewFalseBranchIsNextCompare(alloc(), emptyBlock, nextBlock)); current->setStopPc(pc); // Continue until the case condition. current = nextBlock; pc = current->startPc(); state.stopAt = casePc; if (!addBlock(current)) return ControlStatus::Error; return ControlStatus::Jumped; } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processCondSwitchDefault(CFGState& state) { uint32_t& currentIdx = state.switch_.currentIdx; // The last case condition is finished. Loop in processCondSwitchBody, // with potential stops in processSwitchBreak. #ifdef DEBUG // Test that we calculated the number of bodies correctly. FixedList& bodies = *state.switch_.bodies; MOZ_ASSERT(state.switch_.currentIdx == bodies.length() || state.switch_.defaultIdx + 1 == bodies.length()); #endif // Handle break statements in processSwitchBreak while processing // bodies. ControlFlowInfo breakInfo(cfgStack_.length() - 1, state.switch_.exitpc); if (!switches_.append(breakInfo)) return ControlStatus::Error; // Jump into the first body. currentIdx = 0; current = nullptr; state.state = CFGState::COND_SWITCH_BODY; return processCondSwitchBody(state); } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processCondSwitchBody(CFGState& state) { MOZ_ASSERT(state.state == CFGState::COND_SWITCH_BODY); MOZ_ASSERT(pc <= state.switch_.exitpc); FixedList& bodies = *state.switch_.bodies; uint32_t& currentIdx = state.switch_.currentIdx; MOZ_ASSERT(currentIdx <= bodies.length()); if (currentIdx == bodies.length()) { MOZ_ASSERT_IF(current, pc == state.switch_.exitpc); return processSwitchEnd(state.switch_.breaks, state.switch_.exitpc); } // Get the next body CFGBlock* nextBody = bodies[currentIdx++]; MOZ_ASSERT_IF(current, pc == nextBody->startPc()); // The last body continue into the new one. if (current) { current->setStopIns(CFGGoto::New(alloc(), nextBody)); current->setStopPc(pc); } // Continue in the next body. current = nextBody; pc = current->startPc(); if (!addBlock(current)) return ControlStatus::Error; if (currentIdx < bodies.length()) state.stopAt = bodies[currentIdx]->startPc(); else state.stopAt = state.switch_.exitpc; return ControlStatus::Jumped; } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processAndOrEnd(CFGState& state) { MOZ_ASSERT(current); CFGBlock* lhs = state.branch.ifFalse; // Create a new block to represent the join. CFGBlock* join = CFGBlock::New(alloc(), state.stopAt); // End the rhs. current->setStopIns(CFGGoto::New(alloc(), join)); current->setStopPc(pc); // End the lhs. lhs->setStopIns(CFGGoto::New(alloc(), join)); lhs->setStopPc(pc); // Set the join path as current path. current = join; pc = current->startPc(); if (!addBlock(current)) return ControlStatus::Error; return ControlStatus::Joined; } ControlFlowGenerator::ControlStatus ControlFlowGenerator::maybeLoop(JSOp op, jssrcnote* sn) { // This function looks at the opcode and source note and tries to // determine the structure of the loop. For some opcodes, like // POP/NOP which are not explicitly control flow, this source note is // optional. For opcodes with control flow, like GOTO, an unrecognized // or not-present source note is a compilation failure. switch (op) { case JSOP_POP: // for (init; ; update?) ... if (sn && SN_TYPE(sn) == SRC_FOR) { MOZ_CRASH("Not supported anymore?"); return processForLoop(op, sn); } break; case JSOP_NOP: if (sn) { // do { } while (cond) if (SN_TYPE(sn) == SRC_WHILE) return processDoWhileLoop(op, sn); // Build a mapping such that given a basic block, whose successor // has a phi // for (; ; update?) if (SN_TYPE(sn) == SRC_FOR) return processForLoop(op, sn); } break; default: MOZ_CRASH("unexpected opcode"); } return ControlStatus::None; } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processForLoop(JSOp op, jssrcnote* sn) { // Skip the NOP. MOZ_ASSERT(op == JSOP_NOP); pc = GetNextPc(pc); jsbytecode* condpc = pc + GetSrcNoteOffset(sn, 0); jsbytecode* updatepc = pc + GetSrcNoteOffset(sn, 1); jsbytecode* ifne = pc + GetSrcNoteOffset(sn, 2); jsbytecode* exitpc = GetNextPc(ifne); // for loops have the following structures: // // NOP or POP // [GOTO cond | NOP] // LOOPHEAD // body: // ; [body] // [increment:] // [FRESHENBLOCKSCOPE, if needed by a cloned block] // ; [increment] // [cond:] // LOOPENTRY // GOTO body // // If there is a condition (condpc != ifne), this acts similar to a while // loop otherwise, it acts like a do-while loop. // // Note that currently Ion does not compile pushblockscope/popblockscope as // necessary prerequisites to freshenblockscope. So the code below doesn't // and needn't consider the implications of freshenblockscope. jsbytecode* bodyStart = pc; jsbytecode* bodyEnd = updatepc; jsbytecode* loopEntry = condpc; if (condpc != ifne) { MOZ_ASSERT(JSOp(*bodyStart) == JSOP_GOTO); MOZ_ASSERT(bodyStart + GetJumpOffset(bodyStart) == condpc); bodyStart = GetNextPc(bodyStart); } else { // No loop condition, such as for(j = 0; ; j++) if (op != JSOP_NOP) { // If the loop starts with POP, we have to skip a NOP. MOZ_ASSERT(JSOp(*bodyStart) == JSOP_NOP); bodyStart = GetNextPc(bodyStart); } loopEntry = GetNextPc(bodyStart); } jsbytecode* loopHead = bodyStart; MOZ_ASSERT(JSOp(*bodyStart) == JSOP_LOOPHEAD); MOZ_ASSERT(ifne + GetJumpOffset(ifne) == bodyStart); bodyStart = GetNextPc(bodyStart); MOZ_ASSERT(JSOp(*loopEntry) == JSOP_LOOPENTRY); CFGBlock* header = CFGBlock::New(alloc(), GetNextPc(loopEntry)); CFGLoopEntry* ins = CFGLoopEntry::New(alloc(), header, 0); if (LoopEntryCanIonOsr(loopEntry)) ins->setCanOsr(); current->setStopIns(ins); current->setStopPc(pc); // If there is no condition, we immediately parse the body. Otherwise, we // parse the condition. jsbytecode* stopAt; CFGState::State initial; if (condpc != ifne) { pc = condpc; stopAt = ifne; initial = CFGState::FOR_LOOP_COND; } else { pc = bodyStart; stopAt = bodyEnd; initial = CFGState::FOR_LOOP_BODY; } if (!pushLoop(initial, stopAt, current, loopHead, pc, bodyStart, bodyEnd, exitpc, updatepc)) { return ControlStatus::Error; } CFGState& state = cfgStack_.back(); state.loop.condpc = (condpc != ifne) ? condpc : nullptr; state.loop.updatepc = (updatepc != condpc) ? updatepc : nullptr; if (state.loop.updatepc) state.loop.updateEnd = condpc; current = header; if (!addBlock(current)) return ControlStatus::Error; return ControlStatus::Jumped; } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processDoWhileLoop(JSOp op, jssrcnote* sn) { // do { } while() loops have the following structure: // NOP ; SRC_WHILE (offset to COND) // LOOPHEAD ; SRC_WHILE (offset to IFNE) // LOOPENTRY // ... ; body // ... // COND ; start of condition // ... // IFNE -> ; goes to LOOPHEAD int condition_offset = GetSrcNoteOffset(sn, 0); jsbytecode* conditionpc = pc + condition_offset; jssrcnote* sn2 = GetSrcNote(gsn, script, pc + 1); int offset = GetSrcNoteOffset(sn2, 0); jsbytecode* ifne = pc + offset + 1; MOZ_ASSERT(ifne > pc); // Verify that the IFNE goes back to a loophead op. jsbytecode* loopHead = GetNextPc(pc); MOZ_ASSERT(JSOp(*loopHead) == JSOP_LOOPHEAD); MOZ_ASSERT(loopHead == ifne + GetJumpOffset(ifne)); jsbytecode* loopEntry = GetNextPc(loopHead); CFGBlock* header = CFGBlock::New(alloc(), GetNextPc(loopEntry)); CFGLoopEntry* ins = CFGLoopEntry::New(alloc(), header, 0); if (LoopEntryCanIonOsr(loopEntry)) ins->setCanOsr(); current->setStopIns(ins); current->setStopPc(pc); jsbytecode* bodyEnd = conditionpc; jsbytecode* exitpc = GetNextPc(ifne); if (!pushLoop(CFGState::DO_WHILE_LOOP_BODY, conditionpc, current, loopHead, loopEntry, loopEntry, bodyEnd, exitpc, conditionpc)) { return ControlStatus::Error; } CFGState& state = cfgStack_.back(); state.loop.updatepc = conditionpc; state.loop.updateEnd = ifne; current = header; pc = loopEntry; if (!addBlock(current)) return ControlStatus::Error; return ControlStatus::Jumped; } bool ControlFlowGenerator::pushLoop(CFGState::State initial, jsbytecode* stopAt, CFGBlock* entry, jsbytecode* loopHead, jsbytecode* initialPc, jsbytecode* bodyStart, jsbytecode* bodyEnd, jsbytecode* exitpc, jsbytecode* continuepc) { ControlFlowInfo loop(cfgStack_.length(), continuepc); if (!loops_.append(loop)) return false; CFGState state; state.state = initial; state.stopAt = stopAt; state.loop.bodyStart = bodyStart; state.loop.bodyEnd = bodyEnd; state.loop.exitpc = exitpc; state.loop.entry = entry; state.loop.successor = nullptr; state.loop.breaks = nullptr; state.loop.continues = nullptr; state.loop.initialState = initial; state.loop.initialPc = initialPc; state.loop.initialStopAt = stopAt; state.loop.loopHead = loopHead; return cfgStack_.append(state); } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processBreak(JSOp op, jssrcnote* sn) { MOZ_ASSERT(op == JSOP_GOTO); MOZ_ASSERT(SN_TYPE(sn) == SRC_BREAK || SN_TYPE(sn) == SRC_BREAK2LABEL); // Find the break target. jsbytecode* target = pc + GetJumpOffset(pc); DebugOnly found = false; if (SN_TYPE(sn) == SRC_BREAK2LABEL) { for (size_t i = labels_.length() - 1; ; i--) { CFGState& cfg = cfgStack_[labels_[i].cfgEntry]; MOZ_ASSERT(cfg.state == CFGState::LABEL); if (cfg.stopAt == target) { cfg.label.breaks = new(alloc()) DeferredEdge(current, cfg.label.breaks); found = true; break; } if (i == 0) break; } } else { for (size_t i = loops_.length() - 1; ; i--) { CFGState& cfg = cfgStack_[loops_[i].cfgEntry]; MOZ_ASSERT(cfg.isLoop()); if (cfg.loop.exitpc == target) { cfg.loop.breaks = new(alloc()) DeferredEdge(current, cfg.loop.breaks); found = true; break; } if (i == 0) break; } } current->setStopPc(pc); MOZ_ASSERT(found); current = nullptr; pc += CodeSpec[op].length; return processControlEnd(); } static inline jsbytecode* EffectiveContinue(jsbytecode* pc) { if (JSOp(*pc) == JSOP_GOTO) return pc + GetJumpOffset(pc); return pc; } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processContinue(JSOp op) { MOZ_ASSERT(op == JSOP_GOTO); // Find the target loop. CFGState* found = nullptr; jsbytecode* target = pc + GetJumpOffset(pc); for (size_t i = loops_.length() - 1; ; i--) { // +1 to skip JSOP_JUMPTARGET. if (loops_[i].continuepc == target + 1 || EffectiveContinue(loops_[i].continuepc) == target) { found = &cfgStack_[loops_[i].cfgEntry]; break; } if (i == 0) break; } // There must always be a valid target loop structure. If not, there's // probably an off-by-something error in which pc we track. MOZ_ASSERT(found); CFGState& state = *found; state.loop.continues = new(alloc()) DeferredEdge(current, state.loop.continues); if (!state.loop.continues) return ControlStatus::Error; current->setStopPc(pc); current = nullptr; pc += CodeSpec[op].length; return processControlEnd(); } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processSwitchBreak(JSOp op) { MOZ_ASSERT(op == JSOP_GOTO); // Find the target switch. CFGState* found = nullptr; jsbytecode* target = pc + GetJumpOffset(pc); for (size_t i = switches_.length() - 1; ; i--) { if (switches_[i].continuepc == target) { found = &cfgStack_[switches_[i].cfgEntry]; break; } if (i == 0) break; } // There must always be a valid target loop structure. If not, there's // probably an off-by-something error in which pc we track. MOZ_ASSERT(found); CFGState& state = *found; DeferredEdge** breaks = nullptr; switch (state.state) { case CFGState::TABLE_SWITCH: breaks = &state.switch_.breaks; break; case CFGState::COND_SWITCH_BODY: breaks = &state.switch_.breaks; break; default: MOZ_CRASH("Unexpected switch state."); } *breaks = new(alloc()) DeferredEdge(current, *breaks); current->setStopPc(pc); current = nullptr; pc += CodeSpec[op].length; return processControlEnd(); } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processIfStart(JSOp op) { // IFEQ always has a forward offset. jsbytecode* trueStart = pc + CodeSpec[op].length; jsbytecode* falseStart = pc + GetJumpOffset(pc); MOZ_ASSERT(falseStart > pc); // We only handle cases that emit source notes. jssrcnote* sn = GetSrcNote(gsn, script, pc); if (!sn) return ControlStatus::Error; // Create true and false branches. CFGBlock* ifTrue = CFGBlock::New(alloc(), trueStart); CFGBlock* ifFalse = CFGBlock::New(alloc(), falseStart); CFGTest* test = CFGTest::New(alloc(), ifTrue, ifFalse); current->setStopIns(test); current->setStopPc(pc); // The bytecode for if/ternary gets emitted either like this: // // IFEQ X ; src note (IF_ELSE, COND) points to the GOTO // ... // GOTO Z // X: ... ; else/else if // ... // Z: ; join // // Or like this: // // IFEQ X ; src note (IF) has no offset // ... // Z: ... ; join // // We want to parse the bytecode as if we were parsing the AST, so for the // IF_ELSE/COND cases, we use the source note and follow the GOTO. For the // IF case, the IFEQ offset is the join point. switch (SN_TYPE(sn)) { case SRC_IF: if (!cfgStack_.append(CFGState::If(falseStart, test))) return ControlStatus::Error; break; case SRC_IF_ELSE: case SRC_COND: { // Infer the join point from the JSOP_GOTO[X] sitting here, then // assert as we much we can that this is the right GOTO. jsbytecode* trueEnd = pc + GetSrcNoteOffset(sn, 0); MOZ_ASSERT(trueEnd > pc); MOZ_ASSERT(trueEnd < falseStart); MOZ_ASSERT(JSOp(*trueEnd) == JSOP_GOTO); MOZ_ASSERT(!GetSrcNote(gsn, script, trueEnd)); jsbytecode* falseEnd = trueEnd + GetJumpOffset(trueEnd); MOZ_ASSERT(falseEnd > trueEnd); MOZ_ASSERT(falseEnd >= falseStart); if (!cfgStack_.append(CFGState::IfElse(trueEnd, falseEnd, test))) return ControlStatus::Error; break; } default: MOZ_CRASH("unexpected source note type"); } // Switch to parsing the true branch. Note that no PC update is needed, // it's the next instruction. current = ifTrue; pc = ifTrue->startPc(); if (!addBlock(current)) return ControlStatus::Error; return ControlStatus::Jumped; } int ControlFlowGenerator::CmpSuccessors(const void* a, const void* b) { const CFGBlock* a0 = * (CFGBlock * const*)a; const CFGBlock* b0 = * (CFGBlock * const*)b; if (a0->startPc() == b0->startPc()) return 0; return (a0->startPc() > b0->startPc()) ? 1 : -1; } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processTableSwitch(JSOp op, jssrcnote* sn) { // TableSwitch op contains the following data // (length between data is JUMP_OFFSET_LEN) // // 0: Offset of default case // 1: Lowest number in tableswitch // 2: Highest number in tableswitch // 3: Offset of case low // 4: Offset of case low+1 // .: ... // .: Offset of case high MOZ_ASSERT(op == JSOP_TABLESWITCH); MOZ_ASSERT(SN_TYPE(sn) == SRC_TABLESWITCH); // Get the default and exit pc jsbytecode* exitpc = pc + GetSrcNoteOffset(sn, 0); jsbytecode* defaultpc = pc + GET_JUMP_OFFSET(pc); MOZ_ASSERT(defaultpc > pc && defaultpc <= exitpc); // Get the low and high from the tableswitch jsbytecode* pc2 = pc; pc2 += JUMP_OFFSET_LEN; int low = GET_JUMP_OFFSET(pc2); pc2 += JUMP_OFFSET_LEN; int high = GET_JUMP_OFFSET(pc2); pc2 += JUMP_OFFSET_LEN; // Create MIR instruction CFGTableSwitch* tableswitch = CFGTableSwitch::New(alloc(), low, high); // Create default case CFGBlock* defaultcase = CFGBlock::New(alloc(), defaultpc); if (!tableswitch->addDefault(defaultcase)) return ControlStatus::Error; // Create cases jsbytecode* casepc = nullptr; for (int i = 0; i < high-low+1; i++) { if (!alloc().ensureBallast()) return ControlStatus::Error; casepc = pc + GET_JUMP_OFFSET(pc2); MOZ_ASSERT(casepc >= pc && casepc <= exitpc); CFGBlock* caseBlock; if (casepc == pc) { // If the casepc equals the current pc, it is not a written case, // but a filled gap. That way we can use a tableswitch instead of // condswitch, even if not all numbers are consecutive. // In that case this block goes to the default case caseBlock = CFGBlock::New(alloc(), defaultpc); caseBlock->setStopIns(CFGGoto::New(alloc(), defaultcase)); } else { // If this is an actual case (not filled gap), // add this block to the list that still needs to get processed. caseBlock = CFGBlock::New(alloc(), casepc); } if (!tableswitch->addCase(caseBlock)) return ControlStatus::Error; pc2 += JUMP_OFFSET_LEN; } // Create info ControlFlowInfo switchinfo(cfgStack_.length(), exitpc); if (!switches_.append(switchinfo)) return ControlStatus::Error; // Use a state to retrieve some information CFGState state = CFGState::TableSwitch(alloc(), exitpc); if (!state.switch_.bodies || !state.switch_.bodies->init(alloc(), tableswitch->numSuccessors())) { return ControlStatus::Error; } FixedList& bodies = *state.switch_.bodies; for (size_t i = 0; i < tableswitch->numSuccessors(); i++) bodies[i] = tableswitch->getSuccessor(i); qsort(bodies.begin(), state.switch_.bodies->length(), sizeof(CFGBlock*), CmpSuccessors); // Save the MIR instruction as last instruction of this block. current->setStopIns(tableswitch); current->setStopPc(pc); // If there is only one successor the block should stop at the end of the switch // Else it should stop at the start of the next successor if (bodies.length() > 1) state.stopAt = bodies[1]->startPc(); else state.stopAt = exitpc; if (!cfgStack_.append(state)) return ControlStatus::Error; current = bodies[0]; pc = current->startPc(); if (!addBlock(current)) return ControlStatus::Error; return ControlStatus::Jumped; } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processNextTableSwitchCase(CFGState& state) { MOZ_ASSERT(state.state == CFGState::TABLE_SWITCH); FixedList& bodies = *state.switch_.bodies; state.switch_.currentIdx++; // Test if there are still unprocessed successors (cases/default) if (state.switch_.currentIdx >= bodies.length()) return processSwitchEnd(state.switch_.breaks, state.switch_.exitpc); // Get the next successor CFGBlock* successor = bodies[state.switch_.currentIdx]; // Add current block as predecessor if available. // This means the previous case didn't have a break statement. // So flow will continue in this block. if (current) { current->setStopIns(CFGGoto::New(alloc(), successor)); current->setStopPc(pc); } // If this is the last successor the block should stop at the end of the tableswitch // Else it should stop at the start of the next successor if (state.switch_.currentIdx + 1 < bodies.length()) state.stopAt = bodies[state.switch_.currentIdx + 1]->startPc(); else state.stopAt = state.switch_.exitpc; current = bodies[state.switch_.currentIdx]; pc = current->startPc(); if (!addBlock(current)) return ControlStatus::Error; return ControlStatus::Jumped; } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processSwitchEnd(DeferredEdge* breaks, jsbytecode* exitpc) { // No break statements, no current. // This means that control flow is cut-off from this point // (e.g. all cases have return statements). if (!breaks && !current) return ControlStatus::Ended; // Create successor block. // If there are breaks, create block with breaks as predecessor // Else create a block with current as predecessor CFGBlock* successor = nullptr; if (breaks) { successor = createBreakCatchBlock(breaks, exitpc); if (!successor) return ControlStatus::Error; } else { successor = CFGBlock::New(alloc(), exitpc); } // If there is current, the current block flows into this one. // So current is also a predecessor to this block if (current) { current->setStopIns(CFGGoto::New(alloc(), successor)); current->setStopPc(pc); } current = successor; pc = successor->startPc(); if (!addBlock(successor)) return ControlStatus::Error; return ControlStatus::Joined; } ControlFlowGenerator::CFGState ControlFlowGenerator::CFGState::If(jsbytecode* join, CFGTest* test) { CFGState state; state.state = IF_TRUE; state.stopAt = join; state.branch.ifFalse = test->getSuccessor(1); state.branch.test = test; return state; } ControlFlowGenerator::CFGState ControlFlowGenerator::CFGState::IfElse(jsbytecode* trueEnd, jsbytecode* falseEnd, CFGTest* test) { CFGBlock* ifFalse = test->getSuccessor(1); CFGState state; // If the end of the false path is the same as the start of the // false path, then the "else" block is empty and we can devolve // this to the IF_TRUE case. We handle this here because there is // still an extra GOTO on the true path and we want stopAt to point // there, whereas the IF_TRUE case does not have the GOTO. state.state = (falseEnd == ifFalse->startPc()) ? IF_TRUE_EMPTY_ELSE : IF_ELSE_TRUE; state.stopAt = trueEnd; state.branch.falseEnd = falseEnd; state.branch.ifFalse = ifFalse; state.branch.test = test; return state; } ControlFlowGenerator::CFGState ControlFlowGenerator::CFGState::AndOr(jsbytecode* join, CFGBlock* lhs) { CFGState state; state.state = AND_OR; state.stopAt = join; state.branch.ifFalse = lhs; state.branch.test = nullptr; return state; } ControlFlowGenerator::CFGState ControlFlowGenerator::CFGState::TableSwitch(TempAllocator& alloc, jsbytecode* exitpc) { CFGState state; state.state = TABLE_SWITCH; state.stopAt = exitpc; state.switch_.bodies = (FixedList*)alloc.allocate(sizeof(FixedList)); state.switch_.currentIdx = 0; state.switch_.exitpc = exitpc; state.switch_.breaks = nullptr; return state; } ControlFlowGenerator::CFGState ControlFlowGenerator::CFGState::CondSwitch(TempAllocator& alloc, jsbytecode* exitpc, jsbytecode* defaultTarget) { CFGState state; state.state = COND_SWITCH_CASE; state.stopAt = nullptr; state.switch_.bodies = (FixedList*)alloc.allocate(sizeof(FixedList)); state.switch_.currentIdx = 0; state.switch_.defaultTarget = defaultTarget; state.switch_.defaultIdx = uint32_t(-1); state.switch_.exitpc = exitpc; state.switch_.breaks = nullptr; return state; } ControlFlowGenerator::CFGState ControlFlowGenerator::CFGState::Label(jsbytecode* exitpc) { CFGState state; state.state = LABEL; state.stopAt = exitpc; state.label.breaks = nullptr; return state; } ControlFlowGenerator::CFGState ControlFlowGenerator::CFGState::Try(jsbytecode* exitpc, CFGBlock* successor) { CFGState state; state.state = TRY; state.stopAt = exitpc; state.try_.successor = successor; return state; } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processAndOr(JSOp op) { MOZ_ASSERT(op == JSOP_AND || op == JSOP_OR); jsbytecode* rhsStart = pc + CodeSpec[op].length; jsbytecode* joinStart = pc + GetJumpOffset(pc); MOZ_ASSERT(joinStart > pc); CFGBlock* evalLhs = CFGBlock::New(alloc(), joinStart); CFGBlock* evalRhs = CFGBlock::New(alloc(), rhsStart); CFGTest* test = (op == JSOP_AND) ? CFGTest::New(alloc(), evalRhs, evalLhs) : CFGTest::New(alloc(), evalLhs, evalRhs); test->keepCondition(); current->setStopIns(test); current->setStopPc(pc); // Create the rhs block. if (!cfgStack_.append(CFGState::AndOr(joinStart, evalLhs))) return ControlStatus::Error; if (!addBlock(evalLhs)) return ControlStatus::Error; current = evalRhs; pc = current->startPc(); if (!addBlock(current)) return ControlStatus::Error; return ControlStatus::Jumped; } ControlFlowGenerator::ControlStatus ControlFlowGenerator::processLabel() { MOZ_ASSERT(JSOp(*pc) == JSOP_LABEL); jsbytecode* endpc = pc + GET_JUMP_OFFSET(pc); MOZ_ASSERT(endpc > pc); ControlFlowInfo label(cfgStack_.length(), endpc); if (!labels_.append(label)) return ControlStatus::Error; if (!cfgStack_.append(CFGState::Label(endpc))) return ControlStatus::Error; return ControlStatus::None; }