/* -*- 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/IonAnalysis.h" #include "mozilla/SizePrintfMacros.h" #include "jit/AliasAnalysis.h" #include "jit/BaselineInspector.h" #include "jit/BaselineJIT.h" #include "jit/FlowAliasAnalysis.h" #include "jit/Ion.h" #include "jit/IonBuilder.h" #include "jit/IonOptimizationLevels.h" #include "jit/LIR.h" #include "jit/Lowering.h" #include "jit/MIRGraph.h" #include "vm/RegExpObject.h" #include "vm/SelfHosting.h" #include "jsobjinlines.h" #include "jsopcodeinlines.h" #include "jsscriptinlines.h" #include "jit/shared/Lowering-shared-inl.h" using namespace js; using namespace js::jit; using mozilla::DebugOnly; typedef Vector<MPhi*, 16, SystemAllocPolicy> MPhiVector; static bool FlagPhiInputsAsHavingRemovedUses(MIRGenerator* mir, MBasicBlock* block, MBasicBlock* succ, MPhiVector& worklist) { // When removing an edge between 2 blocks, we might remove the ability of // later phases to figure out that the uses of a Phi should be considered as // a use of all its inputs. Thus we need to mark the Phi inputs as having // removed uses iff the phi has any uses. // // // +--------------------+ +---------------------+ // |12 MFoo 6 | |32 MBar 5 | // | | | | // | ... | | ... | // | | | | // |25 MGoto Block 4 | |43 MGoto Block 4 | // +--------------------+ +---------------------+ // | | // | | | // | | | // | +-----X------------------------+ // | Edge | // | Removed | // | | // | +------------v-----------+ // | |50 MPhi 12 32 | // | | | // | | ... | // | | | // | |70 MReturn 50 | // | +------------------------+ // | // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - // | // v // // ^ +--------------------+ +---------------------+ // /!\ |12 MConst opt-out | |32 MBar 5 | // '---' | | | | // | ... | | ... | // |78 MBail | | | // |80 MUnreachable | |43 MGoto Block 4 | // +--------------------+ +---------------------+ // | // | // | // +---------------+ // | // | // | // +------------v-----------+ // |50 MPhi 32 | // | | // | ... | // | | // |70 MReturn 50 | // +------------------------+ // // // If the inputs of the Phi are not flagged as having removed uses, then // later compilation phase might optimize them out. The problem is that a // bailout will use this value and give it back to baseline, which will then // use the OptimizedOut magic value in a computation. // Conservative upper limit for the number of Phi instructions which are // visited while looking for uses. const size_t conservativeUsesLimit = 128; MOZ_ASSERT(worklist.empty()); size_t predIndex = succ->getPredecessorIndex(block); MPhiIterator end = succ->phisEnd(); MPhiIterator it = succ->phisBegin(); for (; it != end; it++) { MPhi* phi = *it; if (mir->shouldCancel("FlagPhiInputsAsHavingRemovedUses outer loop")) return false; // We are looking to mark the Phi inputs which are used across the edge // between the |block| and its successor |succ|. MDefinition* def = phi->getOperand(predIndex); if (def->isUseRemoved()) continue; phi->setInWorklist(); if (!worklist.append(phi)) return false; // Fill the work list with all the Phi nodes uses until we reach either: // - A resume point which uses the Phi as an observable operand. // - An explicit use of the Phi instruction. // - An implicit use of the Phi instruction. bool isUsed = false; for (size_t idx = 0; !isUsed && idx < worklist.length(); idx++) { phi = worklist[idx]; if (mir->shouldCancel("FlagPhiInputsAsHavingRemovedUses inner loop 1")) return false; if (phi->isUseRemoved() || phi->isImplicitlyUsed()) { // The phi is implicitly used. isUsed = true; break; } MUseIterator usesEnd(phi->usesEnd()); for (MUseIterator use(phi->usesBegin()); use != usesEnd; use++) { MNode* consumer = (*use)->consumer(); if (mir->shouldCancel("FlagPhiInputsAsHavingRemovedUses inner loop 2")) return false; if (consumer->isResumePoint()) { MResumePoint* rp = consumer->toResumePoint(); if (rp->isObservableOperand(*use)) { // The phi is observable via a resume point operand. isUsed = true; break; } continue; } MDefinition* cdef = consumer->toDefinition(); if (!cdef->isPhi()) { // The phi is explicitly used. isUsed = true; break; } phi = cdef->toPhi(); if (phi->isInWorklist()) continue; phi->setInWorklist(); if (!worklist.append(phi)) return false; } // Use a conservative upper bound to avoid iterating too many times // on very large graphs. if (idx >= conservativeUsesLimit) { isUsed = true; break; } } if (isUsed) def->setUseRemoved(); // Remove all the InWorklist flags. while (!worklist.empty()) { phi = worklist.popCopy(); phi->setNotInWorklist(); } } return true; } static bool FlagAllOperandsAsHavingRemovedUses(MIRGenerator* mir, MBasicBlock* block) { // Flag all instructions operands as having removed uses. MInstructionIterator end = block->end(); for (MInstructionIterator it = block->begin(); it != end; it++) { if (mir->shouldCancel("FlagAllOperandsAsHavingRemovedUses loop 1")) return false; MInstruction* ins = *it; for (size_t i = 0, e = ins->numOperands(); i < e; i++) ins->getOperand(i)->setUseRemovedUnchecked(); // Flag observable resume point operands as having removed uses. if (MResumePoint* rp = ins->resumePoint()) { // Note: no need to iterate over the caller's of the resume point as // this is the same as the entry resume point. for (size_t i = 0, e = rp->numOperands(); i < e; i++) { if (mir->shouldCancel("FlagAllOperandsAsHavingRemovedUses inner loop")) return false; if (!rp->isObservableOperand(i)) continue; rp->getOperand(i)->setUseRemovedUnchecked(); } } } // Flag observable operands of the entry resume point as having removed uses. MResumePoint* rp = block->entryResumePoint(); while (rp) { if (mir->shouldCancel("FlagAllOperandsAsHavingRemovedUses loop 2")) return false; for (size_t i = 0, e = rp->numOperands(); i < e; i++) { if (!rp->isObservableOperand(i)) continue; rp->getOperand(i)->setUseRemovedUnchecked(); } rp = rp->caller(); } // Flag Phi inputs of the successors has having removed uses. MPhiVector worklist; for (size_t i = 0, e = block->numSuccessors(); i < e; i++) { if (mir->shouldCancel("FlagAllOperandsAsHavingRemovedUses loop 3")) return false; if (!FlagPhiInputsAsHavingRemovedUses(mir, block, block->getSuccessor(i), worklist)) return false; } return true; } static void RemoveFromSuccessors(MBasicBlock* block) { // Remove this block from its successors. size_t numSucc = block->numSuccessors(); while (numSucc--) { MBasicBlock* succ = block->getSuccessor(numSucc); if (succ->isDead()) continue; JitSpew(JitSpew_Prune, "Remove block edge %d -> %d.", block->id(), succ->id()); succ->removePredecessor(block); } } static void ConvertToBailingBlock(TempAllocator& alloc, MBasicBlock* block) { // Add a bailout instruction. MBail* bail = MBail::New(alloc, Bailout_FirstExecution); MInstruction* bailPoint = block->safeInsertTop(); block->insertBefore(block->safeInsertTop(), bail); // Discard all remaining instructions. MInstructionIterator clearStart = block->begin(bailPoint); block->discardAllInstructionsStartingAt(clearStart); if (block->outerResumePoint()) block->clearOuterResumePoint(); // And replace the last instruction by the unreachable control instruction. block->end(MUnreachable::New(alloc)); } bool jit::PruneUnusedBranches(MIRGenerator* mir, MIRGraph& graph) { MOZ_ASSERT(!mir->compilingWasm(), "wasm compilation has no code coverage support."); // We do a reverse-post-order traversal, marking basic blocks when the block // have to be converted into bailing blocks, and flagging block as // unreachable if all predecessors are flagged as bailing or unreachable. bool someUnreachable = false; for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); block++) { if (mir->shouldCancel("Prune unused branches (main loop)")) return false; JitSpew(JitSpew_Prune, "Investigate Block %d:", block->id()); JitSpewIndent indent(JitSpew_Prune); // Do not touch entry basic blocks. if (*block == graph.osrBlock() || *block == graph.entryBlock()) { JitSpew(JitSpew_Prune, "Block %d is an entry point.", block->id()); continue; } // Compute if all the predecessors of this block are either bailling out // or are already flagged as unreachable. bool isUnreachable = true; bool isLoopHeader = block->isLoopHeader(); size_t numPred = block->numPredecessors(); size_t i = 0; for (; i < numPred; i++) { if (mir->shouldCancel("Prune unused branches (inner loop 1)")) return false; MBasicBlock* pred = block->getPredecessor(i); // The backedge is visited after the loop header, but if the loop // header is unreachable, then we can assume that the backedge would // be unreachable too. if (isLoopHeader && pred == block->backedge()) continue; // Break if any of the predecessor can continue in this block. if (!pred->isMarked() && !pred->unreachable()) { isUnreachable = false; break; } } // Compute if the block should bailout, based on the trivial heuristic // which is that if the block never got visited before, then it is // likely to not be visited after. bool shouldBailout = block->getHitState() == MBasicBlock::HitState::Count && block->getHitCount() == 0; // Check if the predecessors got accessed a large number of times in // comparisons of the current block, in order to know if our attempt at // removing this block is not premature. if (!isUnreachable && shouldBailout) { size_t p = numPred; size_t predCount = 0; size_t numSuccessorsOfPreds = 1; bool isLoopExit = false; while (p--) { if (mir->shouldCancel("Prune unused branches (inner loop 2)")) return false; MBasicBlock* pred = block->getPredecessor(p); if (pred->getHitState() == MBasicBlock::HitState::Count) predCount += pred->getHitCount(); isLoopExit |= pred->isLoopHeader() && pred->backedge() != *block; numSuccessorsOfPreds += pred->numSuccessors() - 1; } // Iterate over the approximated set of dominated blocks and count // the number of instructions which are dominated. Note that this // approximation has issues with OSR blocks, but this should not be // a big deal. size_t numDominatedInst = 0; size_t numEffectfulInst = 0; int numInOutEdges = block->numPredecessors(); size_t branchSpan = 0; ReversePostorderIterator it(block); do { if (mir->shouldCancel("Prune unused branches (inner loop 3)")) return false; // Iterate over dominated blocks, and visit exit blocks as well. numInOutEdges -= it->numPredecessors(); if (numInOutEdges < 0) break; numInOutEdges += it->numSuccessors(); // Collect information about the instructions within the block. for (MDefinitionIterator def(*it); def; def++) { numDominatedInst++; if (def->isEffectful()) numEffectfulInst++; } it++; branchSpan++; } while(numInOutEdges > 0 && it != graph.rpoEnd()); // The goal of branch pruning is to remove branches which are // preventing other optimization, while keeping branches which would // be costly if we were to bailout. The following heuristics are // made to prevent bailouts in branches when we estimate that the // confidence is not enough to compensate for the cost of a bailout. // // 1. Confidence for removal varies with the number of hit counts // of the predecessor. The reason being that the likelyhood of // taking this branch is decreasing with the number of hit // counts of the predecessor. // // 2. Confidence for removal varies with the number of dominated // instructions. The reason being that the complexity of the // branch increases with the number of instructions, thus // working against other optimizations. // // 3. Confidence for removal varies with the span of the // branch. The reason being that a branch that spans over a // large set of blocks is likely to remove optimization // opportunity as it prevents instructions from the other // branches to dominate the blocks which are after. // // 4. Confidence for removal varies with the number of effectful // instructions. The reason being that an effectful instruction // can remove optimization opportunities based on Scalar // Replacement, and based on Alias Analysis. // // The following converts various units in some form of arbitrary // score, such that we can compare it to a threshold. size_t score = 0; MOZ_ASSERT(numSuccessorsOfPreds >= 1); score += predCount * JitOptions.branchPruningHitCountFactor / numSuccessorsOfPreds; score += numDominatedInst * JitOptions.branchPruningInstFactor; score += branchSpan * JitOptions.branchPruningBlockSpanFactor; score += numEffectfulInst * JitOptions.branchPruningEffectfulInstFactor; if (score < JitOptions.branchPruningThreshold) shouldBailout = false; // If the predecessors do not have enough hit counts, keep the // branch, until we recompile this function later, with more // information. if (predCount / numSuccessorsOfPreds < 50) shouldBailout = false; // There is only a single successors to the predecessors, thus the // decision should be taken as part of the previous block // investigation, and this block should be unreachable. if (numSuccessorsOfPreds == 1) shouldBailout = false; // If this is the exit block of a loop, then keep this basic // block. This heuristic is useful as a bailout is often much more // costly than a simple exit sequence. if (isLoopExit) shouldBailout = false; // Interpreters are often implemented as a table switch within a for // loop. What might happen is that the interpreter heats up in a // subset of instructions, but might need other instructions for the // rest of the evaluation. if (numSuccessorsOfPreds > 8) shouldBailout = false; JitSpew(JitSpew_Prune, "info: block %d," " predCount: %" PRIuSIZE ", domInst: %" PRIuSIZE ", span: %" PRIuSIZE ", effectful: %" PRIuSIZE ", " " isLoopExit: %s, numSuccessorsOfPred: %" PRIuSIZE "." " (score: %" PRIuSIZE ", shouldBailout: %s)", block->id(), predCount, numDominatedInst, branchSpan, numEffectfulInst, isLoopExit ? "true" : "false", numSuccessorsOfPreds, score, shouldBailout ? "true" : "false"); } // Continue to the next basic block if the current basic block can // remain unchanged. if (!isUnreachable && !shouldBailout) continue; someUnreachable = true; if (isUnreachable) { JitSpew(JitSpew_Prune, "Mark block %d as unreachable.", block->id()); block->setUnreachable(); // If the block is unreachable, then there is no need to convert it // to a bailing block. } else if (shouldBailout) { JitSpew(JitSpew_Prune, "Mark block %d as bailing block.", block->id()); block->markUnchecked(); } // When removing a loop header, we should ensure that its backedge is // removed first, otherwise this triggers an assertion in // removePredecessorsWithoutPhiOperands. if (block->isLoopHeader()) { JitSpew(JitSpew_Prune, "Mark block %d as bailing block. (loop backedge)", block->backedge()->id()); block->backedge()->markUnchecked(); } } // Returns early if nothing changed. if (!someUnreachable) return true; JitSpew(JitSpew_Prune, "Convert basic block to bailing blocks, and remove unreachable blocks:"); JitSpewIndent indent(JitSpew_Prune); // As we are going to remove edges and basic block, we have to mark // instructions which would be needed by baseline if we were to bailout. for (PostorderIterator it(graph.poBegin()); it != graph.poEnd();) { if (mir->shouldCancel("Prune unused branches (marking loop)")) return false; MBasicBlock* block = *it++; if (!block->isMarked() && !block->unreachable()) continue; FlagAllOperandsAsHavingRemovedUses(mir, block); } // Remove the blocks in post-order such that consumers are visited before // the predecessors, the only exception being the Phi nodes of loop headers. for (PostorderIterator it(graph.poBegin()); it != graph.poEnd();) { if (mir->shouldCancel("Prune unused branches (removal loop)")) return false; MBasicBlock* block = *it++; if (!block->isMarked() && !block->unreachable()) continue; JitSpew(JitSpew_Prune, "Remove / Replace block %d.", block->id()); JitSpewIndent indent(JitSpew_Prune); // As we are going to replace/remove the last instruction, we first have // to remove this block from the predecessor list of its successors. RemoveFromSuccessors(block); // Convert the current basic block to a bailing block which ends with an // Unreachable control instruction. if (block->isMarked()) { JitSpew(JitSpew_Prune, "Convert Block %d to a bailing block.", block->id()); if (!graph.alloc().ensureBallast()) return false; ConvertToBailingBlock(graph.alloc(), block); block->unmark(); } // Remove all instructions. if (block->unreachable()) { JitSpew(JitSpew_Prune, "Remove Block %d.", block->id()); JitSpewIndent indent(JitSpew_Prune); graph.removeBlock(block); } } return true; } static bool SplitCriticalEdgesForBlock(MIRGraph& graph, MBasicBlock* block) { if (block->numSuccessors() < 2) return true; for (size_t i = 0; i < block->numSuccessors(); i++) { MBasicBlock* target = block->getSuccessor(i); if (target->numPredecessors() < 2) continue; // Create a simple new block which contains a goto and which split the // edge between block and target. MBasicBlock* split = MBasicBlock::NewSplitEdge(graph, block, i, target); if (!split) return false; } return true; } // A critical edge is an edge which is neither its successor's only predecessor // nor its predecessor's only successor. Critical edges must be split to // prevent copy-insertion and code motion from affecting other edges. bool jit::SplitCriticalEdges(MIRGraph& graph) { for (MBasicBlockIterator iter(graph.begin()); iter != graph.end(); iter++) { MBasicBlock* block = *iter; if (!SplitCriticalEdgesForBlock(graph, block)) return false; } return true; } bool jit::IsUint32Type(const MDefinition* def) { if (def->isBeta()) def = def->getOperand(0); if (def->type() != MIRType::Int32) return false; return def->isUrsh() && def->getOperand(1)->isConstant() && def->getOperand(1)->toConstant()->type() == MIRType::Int32 && def->getOperand(1)->toConstant()->toInt32() == 0; } // Return whether a block simply computes the specified constant value. static bool BlockComputesConstant(MBasicBlock* block, MDefinition* value, bool* constBool) { // Look for values with no uses. This is used to eliminate constant // computing blocks in condition statements, and the phi which used to // consume the constant has already been removed. if (value->hasUses()) return false; if (!value->isConstant() || value->block() != block) return false; if (!block->phisEmpty()) return false; for (MInstructionIterator iter = block->begin(); iter != block->end(); ++iter) { if (*iter != value || !iter->isGoto()) return false; } return value->toConstant()->valueToBoolean(constBool); } // Find phis that are redudant: // // 1) phi(a, a) // can get replaced by a // // 2) phi(filtertypeset(a, type1), filtertypeset(a, type1)) // equals filtertypeset(a, type1) // // 3) phi(a, filtertypeset(a, type1)) // equals filtertypeset(a, type1 union type(a)) // equals filtertypeset(a, type(a)) // equals a // // 4) phi(filtertypeset(a, type1), filtertypeset(a, type2)) // equals filtertypeset(a, type1 union type2) // // This is the special case. We can only replace this with 'a' iif // type(a) == type1 union type2. Since optimizations could have // happened based on a more specific phi type. static bool IsPhiRedudantFilter(MPhi* phi) { // Handle (1) and (2) if (phi->operandIfRedundant()) return true; // Handle (3) bool onlyFilters = false; MDefinition* a = phi->getOperand(0); if (a->isFilterTypeSet()) { a = a->toFilterTypeSet()->input(); onlyFilters = true; } for (size_t i = 1; i < phi->numOperands(); i++) { MDefinition* operand = phi->getOperand(i); if (operand == a) { onlyFilters = false; continue; } if (operand->isFilterTypeSet() && operand->toFilterTypeSet()->input() == a) continue; return false; } if (!onlyFilters) return true; // Handle (4) MOZ_ASSERT(onlyFilters); return EqualTypes(a->type(), a->resultTypeSet(), phi->type(), phi->resultTypeSet()); } // Determine whether phiBlock/testBlock simply compute a phi and perform a // test on it. static bool BlockIsSingleTest(MBasicBlock* phiBlock, MBasicBlock* testBlock, MPhi** pphi, MTest** ptest) { *pphi = nullptr; *ptest = nullptr; if (phiBlock != testBlock) { MOZ_ASSERT(phiBlock->numSuccessors() == 1 && phiBlock->getSuccessor(0) == testBlock); if (!phiBlock->begin()->isGoto()) return false; } MInstruction* ins = *testBlock->begin(); if (!ins->isTest()) return false; MTest* test = ins->toTest(); if (!test->input()->isPhi()) return false; MPhi* phi = test->input()->toPhi(); if (phi->block() != phiBlock) return false; for (MUseIterator iter = phi->usesBegin(); iter != phi->usesEnd(); ++iter) { MUse* use = *iter; if (use->consumer() == test) continue; if (use->consumer()->isResumePoint()) { MBasicBlock* useBlock = use->consumer()->block(); if (useBlock == phiBlock || useBlock == testBlock) continue; } return false; } for (MPhiIterator iter = phiBlock->phisBegin(); iter != phiBlock->phisEnd(); ++iter) { if (*iter == phi) continue; if (IsPhiRedudantFilter(*iter)) continue; return false; } if (phiBlock != testBlock && !testBlock->phisEmpty()) return false; *pphi = phi; *ptest = test; return true; } // Change block so that it ends in a goto to the specific target block. // existingPred is an existing predecessor of the block. static void UpdateGotoSuccessor(TempAllocator& alloc, MBasicBlock* block, MBasicBlock* target, MBasicBlock* existingPred) { MInstruction* ins = block->lastIns(); MOZ_ASSERT(ins->isGoto()); ins->toGoto()->target()->removePredecessor(block); block->discardLastIns(); MGoto* newGoto = MGoto::New(alloc, target); block->end(newGoto); target->addPredecessorSameInputsAs(block, existingPred); } // Change block so that it ends in a test of the specified value, going to // either ifTrue or ifFalse. existingPred is an existing predecessor of ifTrue // or ifFalse with the same values incoming to ifTrue/ifFalse as block. // existingPred is not required to be a predecessor of ifTrue/ifFalse if block // already ends in a test going to that block on a true/false result. static void UpdateTestSuccessors(TempAllocator& alloc, MBasicBlock* block, MDefinition* value, MBasicBlock* ifTrue, MBasicBlock* ifFalse, MBasicBlock* existingPred) { MInstruction* ins = block->lastIns(); if (ins->isTest()) { MTest* test = ins->toTest(); MOZ_ASSERT(test->input() == value); if (ifTrue != test->ifTrue()) { test->ifTrue()->removePredecessor(block); ifTrue->addPredecessorSameInputsAs(block, existingPred); MOZ_ASSERT(test->ifTrue() == test->getSuccessor(0)); test->replaceSuccessor(0, ifTrue); } if (ifFalse != test->ifFalse()) { test->ifFalse()->removePredecessor(block); ifFalse->addPredecessorSameInputsAs(block, existingPred); MOZ_ASSERT(test->ifFalse() == test->getSuccessor(1)); test->replaceSuccessor(1, ifFalse); } return; } MOZ_ASSERT(ins->isGoto()); ins->toGoto()->target()->removePredecessor(block); block->discardLastIns(); MTest* test = MTest::New(alloc, value, ifTrue, ifFalse); block->end(test); ifTrue->addPredecessorSameInputsAs(block, existingPred); ifFalse->addPredecessorSameInputsAs(block, existingPred); } static bool MaybeFoldConditionBlock(MIRGraph& graph, MBasicBlock* initialBlock) { // Optimize the MIR graph to improve the code generated for conditional // operations. A test like 'if (a ? b : c)' normally requires four blocks, // with a phi for the intermediate value. This can be improved to use three // blocks with no phi value, and if either b or c is constant, // e.g. 'if (a ? b : 0)', then the block associated with that constant // can be eliminated. /* * Look for a diamond pattern: * * initialBlock * / \ * trueBranch falseBranch * \ / * phiBlock * | * testBlock * * Where phiBlock contains a single phi combining values pushed onto the * stack by trueBranch and falseBranch, and testBlock contains a test on * that phi. phiBlock and testBlock may be the same block; generated code * will use different blocks if the (?:) op is in an inlined function. */ MInstruction* ins = initialBlock->lastIns(); if (!ins->isTest()) return true; MTest* initialTest = ins->toTest(); MBasicBlock* trueBranch = initialTest->ifTrue(); if (trueBranch->numPredecessors() != 1 || trueBranch->numSuccessors() != 1) return true; MBasicBlock* falseBranch = initialTest->ifFalse(); if (falseBranch->numPredecessors() != 1 || falseBranch->numSuccessors() != 1) return true; MBasicBlock* phiBlock = trueBranch->getSuccessor(0); if (phiBlock != falseBranch->getSuccessor(0)) return true; if (phiBlock->numPredecessors() != 2) return true; if (initialBlock->isLoopBackedge() || trueBranch->isLoopBackedge() || falseBranch->isLoopBackedge()) return true; MBasicBlock* testBlock = phiBlock; if (testBlock->numSuccessors() == 1) { if (testBlock->isLoopBackedge()) return true; testBlock = testBlock->getSuccessor(0); if (testBlock->numPredecessors() != 1) return true; } // Make sure the test block does not have any outgoing loop backedges. if (!SplitCriticalEdgesForBlock(graph, testBlock)) return false; MPhi* phi; MTest* finalTest; if (!BlockIsSingleTest(phiBlock, testBlock, &phi, &finalTest)) return true; MDefinition* trueResult = phi->getOperand(phiBlock->indexForPredecessor(trueBranch)); MDefinition* falseResult = phi->getOperand(phiBlock->indexForPredecessor(falseBranch)); // OK, we found the desired pattern, now transform the graph. // Patch up phis that filter their input. for (MPhiIterator iter = phiBlock->phisBegin(); iter != phiBlock->phisEnd(); ++iter) { if (*iter == phi) continue; MOZ_ASSERT(IsPhiRedudantFilter(*iter)); MDefinition* redundant = (*iter)->operandIfRedundant(); if (!redundant) { redundant = (*iter)->getOperand(0); if (redundant->isFilterTypeSet()) redundant = redundant->toFilterTypeSet()->input(); } (*iter)->replaceAllUsesWith(redundant); } // Remove the phi from phiBlock. phiBlock->discardPhi(*phiBlock->phisBegin()); // If either trueBranch or falseBranch just computes a constant for the // test, determine the block that branch will end up jumping to and eliminate // the branch. Otherwise, change the end of the block to a test that jumps // directly to successors of testBlock, rather than to testBlock itself. MBasicBlock* trueTarget = trueBranch; bool constBool; if (BlockComputesConstant(trueBranch, trueResult, &constBool)) { trueTarget = constBool ? finalTest->ifTrue() : finalTest->ifFalse(); phiBlock->removePredecessor(trueBranch); graph.removeBlock(trueBranch); } else if (initialTest->input() == trueResult) { UpdateGotoSuccessor(graph.alloc(), trueBranch, finalTest->ifTrue(), testBlock); } else { UpdateTestSuccessors(graph.alloc(), trueBranch, trueResult, finalTest->ifTrue(), finalTest->ifFalse(), testBlock); } MBasicBlock* falseTarget = falseBranch; if (BlockComputesConstant(falseBranch, falseResult, &constBool)) { falseTarget = constBool ? finalTest->ifTrue() : finalTest->ifFalse(); phiBlock->removePredecessor(falseBranch); graph.removeBlock(falseBranch); } else if (initialTest->input() == falseResult) { UpdateGotoSuccessor(graph.alloc(), falseBranch, finalTest->ifFalse(), testBlock); } else { UpdateTestSuccessors(graph.alloc(), falseBranch, falseResult, finalTest->ifTrue(), finalTest->ifFalse(), testBlock); } // Short circuit the initial test to skip any constant branch eliminated above. UpdateTestSuccessors(graph.alloc(), initialBlock, initialTest->input(), trueTarget, falseTarget, testBlock); // Remove phiBlock, if different from testBlock. if (phiBlock != testBlock) { testBlock->removePredecessor(phiBlock); graph.removeBlock(phiBlock); } // Remove testBlock itself. finalTest->ifTrue()->removePredecessor(testBlock); finalTest->ifFalse()->removePredecessor(testBlock); graph.removeBlock(testBlock); return true; } bool jit::FoldTests(MIRGraph& graph) { for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) { if (!MaybeFoldConditionBlock(graph, *block)) return false; } return true; } static void EliminateTriviallyDeadResumePointOperands(MIRGraph& graph, MResumePoint* rp) { // If we will pop the top of the stack immediately after resuming, // then don't preserve the top value in the resume point. if (rp->mode() != MResumePoint::ResumeAt || *rp->pc() != JSOP_POP) return; size_t top = rp->stackDepth() - 1; MOZ_ASSERT(!rp->isObservableOperand(top)); MDefinition* def = rp->getOperand(top); if (def->isConstant()) return; MConstant* constant = rp->block()->optimizedOutConstant(graph.alloc()); rp->replaceOperand(top, constant); } // Operands to a resume point which are dead at the point of the resume can be // replaced with a magic value. This analysis supports limited detection of // dead operands, pruning those which are defined in the resume point's basic // block and have no uses outside the block or at points later than the resume // point. // // This is intended to ensure that extra resume points within a basic block // will not artificially extend the lifetimes of any SSA values. This could // otherwise occur if the new resume point captured a value which is created // between the old and new resume point and is dead at the new resume point. bool jit::EliminateDeadResumePointOperands(MIRGenerator* mir, MIRGraph& graph) { // If we are compiling try blocks, locals and arguments may be observable // from catch or finally blocks (which Ion does not compile). For now just // disable the pass in this case. if (graph.hasTryBlock()) return true; for (PostorderIterator block = graph.poBegin(); block != graph.poEnd(); block++) { if (mir->shouldCancel("Eliminate Dead Resume Point Operands (main loop)")) return false; if (MResumePoint* rp = block->entryResumePoint()) EliminateTriviallyDeadResumePointOperands(graph, rp); // The logic below can get confused on infinite loops. if (block->isLoopHeader() && block->backedge() == *block) continue; for (MInstructionIterator ins = block->begin(); ins != block->end(); ins++) { if (MResumePoint* rp = ins->resumePoint()) EliminateTriviallyDeadResumePointOperands(graph, rp); // No benefit to replacing constant operands with other constants. if (ins->isConstant()) continue; // Scanning uses does not give us sufficient information to tell // where instructions that are involved in box/unbox operations or // parameter passing might be live. Rewriting uses of these terms // in resume points may affect the interpreter's behavior. Rather // than doing a more sophisticated analysis, just ignore these. if (ins->isUnbox() || ins->isParameter() || ins->isTypeBarrier() || ins->isComputeThis() || ins->isFilterTypeSet()) { continue; } // Early intermediate values captured by resume points, such as // TypedObject, ArrayState and its allocation, may be legitimately // dead in Ion code, but are still needed if we bail out. They can // recover on bailout. if (ins->isNewDerivedTypedObject() || ins->isRecoveredOnBailout()) { MOZ_ASSERT(ins->canRecoverOnBailout()); continue; } // If the instruction's behavior has been constant folded into a // separate instruction, we can't determine precisely where the // instruction becomes dead and can't eliminate its uses. if (ins->isImplicitlyUsed() || ins->isUseRemoved()) continue; // Check if this instruction's result is only used within the // current block, and keep track of its last use in a definition // (not resume point). This requires the instructions in the block // to be numbered, ensured by running this immediately after alias // analysis. uint32_t maxDefinition = 0; for (MUseIterator uses(ins->usesBegin()); uses != ins->usesEnd(); uses++) { MNode* consumer = uses->consumer(); if (consumer->isResumePoint()) { // If the instruction's is captured by one of the resume point, then // it might be observed indirectly while the frame is live on the // stack, so it has to be computed. MResumePoint* resume = consumer->toResumePoint(); if (resume->isObservableOperand(*uses)) { maxDefinition = UINT32_MAX; break; } continue; } MDefinition* def = consumer->toDefinition(); if (def->block() != *block || def->isBox() || def->isPhi()) { maxDefinition = UINT32_MAX; break; } maxDefinition = Max(maxDefinition, def->id()); } if (maxDefinition == UINT32_MAX) continue; // Walk the uses a second time, removing any in resume points after // the last use in a definition. for (MUseIterator uses(ins->usesBegin()); uses != ins->usesEnd(); ) { MUse* use = *uses++; if (use->consumer()->isDefinition()) continue; MResumePoint* mrp = use->consumer()->toResumePoint(); if (mrp->block() != *block || !mrp->instruction() || mrp->instruction() == *ins || mrp->instruction()->id() <= maxDefinition) { continue; } if (!graph.alloc().ensureBallast()) return false; // Store an optimized out magic value in place of all dead // resume point operands. Making any such substitution can in // general alter the interpreter's behavior, even though the // code is dead, as the interpreter will still execute opcodes // whose effects cannot be observed. If the magic value value // were to flow to, say, a dead property access the // interpreter could throw an exception; we avoid this problem // by removing dead operands before removing dead code. MConstant* constant = MConstant::New(graph.alloc(), MagicValue(JS_OPTIMIZED_OUT)); block->insertBefore(*(block->begin()), constant); use->replaceProducer(constant); } } } return true; } // Test whether |def| would be needed if it had no uses. bool js::jit::DeadIfUnused(const MDefinition* def) { return !def->isEffectful() && (!def->isGuard() || def->block() == def->block()->graph().osrBlock()) && !def->isGuardRangeBailouts() && !def->isControlInstruction() && (!def->isInstruction() || !def->toInstruction()->resumePoint()); } // Test whether |def| may be safely discarded, due to being dead or due to being // located in a basic block which has itself been marked for discarding. bool js::jit::IsDiscardable(const MDefinition* def) { return !def->hasUses() && (DeadIfUnused(def) || def->block()->isMarked()); } // Instructions are useless if they are unused and have no side effects. // This pass eliminates useless instructions. // The graph itself is unchanged. bool jit::EliminateDeadCode(MIRGenerator* mir, MIRGraph& graph) { // Traverse in postorder so that we hit uses before definitions. // Traverse instruction list backwards for the same reason. for (PostorderIterator block = graph.poBegin(); block != graph.poEnd(); block++) { if (mir->shouldCancel("Eliminate Dead Code (main loop)")) return false; // Remove unused instructions. for (MInstructionReverseIterator iter = block->rbegin(); iter != block->rend(); ) { MInstruction* inst = *iter++; if (js::jit::IsDiscardable(inst)) { block->discard(inst); } } } return true; } static inline bool IsPhiObservable(MPhi* phi, Observability observe) { // If the phi has uses which are not reflected in SSA, then behavior in the // interpreter may be affected by removing the phi. if (phi->isImplicitlyUsed() || phi->isUseRemoved()) return true; // Check for uses of this phi node outside of other phi nodes. // Note that, initially, we skip reading resume points, which we // don't count as actual uses. If the only uses are resume points, // then the SSA name is never consumed by the program. However, // after optimizations have been performed, it's possible that the // actual uses in the program have been (incorrectly) optimized // away, so we must be more conservative and consider resume // points as well. for (MUseIterator iter(phi->usesBegin()); iter != phi->usesEnd(); iter++) { MNode* consumer = iter->consumer(); if (consumer->isResumePoint()) { MResumePoint* resume = consumer->toResumePoint(); if (observe == ConservativeObservability) return true; if (resume->isObservableOperand(*iter)) return true; } else { MDefinition* def = consumer->toDefinition(); if (!def->isPhi()) return true; } } return false; } // Handles cases like: // x is phi(a, x) --> a // x is phi(a, a) --> a static inline MDefinition* IsPhiRedundant(MPhi* phi) { MDefinition* first = phi->operandIfRedundant(); if (first == nullptr) return nullptr; // Propagate the ImplicitlyUsed flag if |phi| is replaced with another phi. if (phi->isImplicitlyUsed()) first->setImplicitlyUsedUnchecked(); return first; } bool jit::EliminatePhis(MIRGenerator* mir, MIRGraph& graph, Observability observe) { // Eliminates redundant or unobservable phis from the graph. A // redundant phi is something like b = phi(a, a) or b = phi(a, b), // both of which can be replaced with a. An unobservable phi is // one that whose value is never used in the program. // // Note that we must be careful not to eliminate phis representing // values that the interpreter will require later. When the graph // is first constructed, we can be more aggressive, because there // is a greater correspondence between the CFG and the bytecode. // After optimizations such as GVN have been performed, however, // the bytecode and CFG may not correspond as closely to one // another. In that case, we must be more conservative. The flag // |conservativeObservability| is used to indicate that eliminate // phis is being run after some optimizations have been performed, // and thus we should use more conservative rules about // observability. The particular danger is that we can optimize // away uses of a phi because we think they are not executable, // but the foundation for that assumption is false TI information // that will eventually be invalidated. Therefore, if // |conservativeObservability| is set, we will consider any use // from a resume point to be observable. Otherwise, we demand a // use from an actual instruction. Vector<MPhi*, 16, SystemAllocPolicy> worklist; // Add all observable phis to a worklist. We use the "in worklist" bit to // mean "this phi is live". for (PostorderIterator block = graph.poBegin(); block != graph.poEnd(); block++) { MPhiIterator iter = block->phisBegin(); while (iter != block->phisEnd()) { MPhi* phi = *iter++; if (mir->shouldCancel("Eliminate Phis (populate loop)")) return false; // Flag all as unused, only observable phis would be marked as used // when processed by the work list. phi->setUnused(); // If the phi is redundant, remove it here. if (MDefinition* redundant = IsPhiRedundant(phi)) { phi->justReplaceAllUsesWith(redundant); block->discardPhi(phi); continue; } // Enqueue observable Phis. if (IsPhiObservable(phi, observe)) { phi->setInWorklist(); if (!worklist.append(phi)) return false; } } } // Iteratively mark all phis reachable from live phis. while (!worklist.empty()) { if (mir->shouldCancel("Eliminate Phis (worklist)")) return false; MPhi* phi = worklist.popCopy(); MOZ_ASSERT(phi->isUnused()); phi->setNotInWorklist(); // The removal of Phis can produce newly redundant phis. if (MDefinition* redundant = IsPhiRedundant(phi)) { // Add to the worklist the used phis which are impacted. for (MUseDefIterator it(phi); it; it++) { if (it.def()->isPhi()) { MPhi* use = it.def()->toPhi(); if (!use->isUnused()) { use->setUnusedUnchecked(); use->setInWorklist(); if (!worklist.append(use)) return false; } } } phi->justReplaceAllUsesWith(redundant); } else { // Otherwise flag them as used. phi->setNotUnused(); } // The current phi is/was used, so all its operands are used. for (size_t i = 0, e = phi->numOperands(); i < e; i++) { MDefinition* in = phi->getOperand(i); if (!in->isPhi() || !in->isUnused() || in->isInWorklist()) continue; in->setInWorklist(); if (!worklist.append(in->toPhi())) return false; } } // Sweep dead phis. for (PostorderIterator block = graph.poBegin(); block != graph.poEnd(); block++) { MPhiIterator iter = block->phisBegin(); while (iter != block->phisEnd()) { MPhi* phi = *iter++; if (phi->isUnused()) { if (!phi->optimizeOutAllUses(graph.alloc())) return false; block->discardPhi(phi); } } } return true; } namespace { // The type analysis algorithm inserts conversions and box/unbox instructions // to make the IR graph well-typed for future passes. // // Phi adjustment: If a phi's inputs are all the same type, the phi is // specialized to return that type. // // Input adjustment: Each input is asked to apply conversion operations to its // inputs. This may include Box, Unbox, or other instruction-specific type // conversion operations. // class TypeAnalyzer { MIRGenerator* mir; MIRGraph& graph; Vector<MPhi*, 0, SystemAllocPolicy> phiWorklist_; TempAllocator& alloc() const { return graph.alloc(); } bool addPhiToWorklist(MPhi* phi) { if (phi->isInWorklist()) return true; if (!phiWorklist_.append(phi)) return false; phi->setInWorklist(); return true; } MPhi* popPhi() { MPhi* phi = phiWorklist_.popCopy(); phi->setNotInWorklist(); return phi; } bool respecialize(MPhi* phi, MIRType type); bool propagateSpecialization(MPhi* phi); bool specializePhis(); void replaceRedundantPhi(MPhi* phi); bool adjustPhiInputs(MPhi* phi); bool adjustInputs(MDefinition* def); bool insertConversions(); bool checkFloatCoherency(); bool graphContainsFloat32(); bool markPhiConsumers(); bool markPhiProducers(); bool specializeValidFloatOps(); bool tryEmitFloatOperations(); public: TypeAnalyzer(MIRGenerator* mir, MIRGraph& graph) : mir(mir), graph(graph) { } bool analyze(); }; } /* anonymous namespace */ // Try to specialize this phi based on its non-cyclic inputs. static MIRType GuessPhiType(MPhi* phi, bool* hasInputsWithEmptyTypes) { #ifdef DEBUG // Check that different magic constants aren't flowing together. Ignore // JS_OPTIMIZED_OUT, since an operand could be legitimately optimized // away. MIRType magicType = MIRType::None; for (size_t i = 0; i < phi->numOperands(); i++) { MDefinition* in = phi->getOperand(i); if (in->type() == MIRType::MagicOptimizedArguments || in->type() == MIRType::MagicHole || in->type() == MIRType::MagicIsConstructing) { if (magicType == MIRType::None) magicType = in->type(); MOZ_ASSERT(magicType == in->type()); } } #endif *hasInputsWithEmptyTypes = false; MIRType type = MIRType::None; bool convertibleToFloat32 = false; bool hasPhiInputs = false; for (size_t i = 0, e = phi->numOperands(); i < e; i++) { MDefinition* in = phi->getOperand(i); if (in->isPhi()) { hasPhiInputs = true; if (!in->toPhi()->triedToSpecialize()) continue; if (in->type() == MIRType::None) { // The operand is a phi we tried to specialize, but we were // unable to guess its type. propagateSpecialization will // propagate the type to this phi when it becomes known. continue; } } // Ignore operands which we've never observed. if (in->resultTypeSet() && in->resultTypeSet()->empty()) { *hasInputsWithEmptyTypes = true; continue; } if (type == MIRType::None) { type = in->type(); if (in->canProduceFloat32()) convertibleToFloat32 = true; continue; } if (type != in->type()) { if (convertibleToFloat32 && in->type() == MIRType::Float32) { // If we only saw definitions that can be converted into Float32 before and // encounter a Float32 value, promote previous values to Float32 type = MIRType::Float32; } else if (IsTypeRepresentableAsDouble(type) && IsTypeRepresentableAsDouble(in->type())) { // Specialize phis with int32 and double operands as double. type = MIRType::Double; convertibleToFloat32 &= in->canProduceFloat32(); } else { return MIRType::Value; } } } if (type == MIRType::None && !hasPhiInputs) { // All inputs are non-phis with empty typesets. Use MIRType::Value // in this case, as it's impossible to get better type information. MOZ_ASSERT(*hasInputsWithEmptyTypes); type = MIRType::Value; } return type; } bool TypeAnalyzer::respecialize(MPhi* phi, MIRType type) { if (phi->type() == type) return true; phi->specialize(type); return addPhiToWorklist(phi); } bool TypeAnalyzer::propagateSpecialization(MPhi* phi) { MOZ_ASSERT(phi->type() != MIRType::None); // Verify that this specialization matches any phis depending on it. for (MUseDefIterator iter(phi); iter; iter++) { if (!iter.def()->isPhi()) continue; MPhi* use = iter.def()->toPhi(); if (!use->triedToSpecialize()) continue; if (use->type() == MIRType::None) { // We tried to specialize this phi, but were unable to guess its // type. Now that we know the type of one of its operands, we can // specialize it. if (!respecialize(use, phi->type())) return false; continue; } if (use->type() != phi->type()) { // Specialize phis with int32 that can be converted to float and float operands as floats. if ((use->type() == MIRType::Int32 && use->canProduceFloat32() && phi->type() == MIRType::Float32) || (phi->type() == MIRType::Int32 && phi->canProduceFloat32() && use->type() == MIRType::Float32)) { if (!respecialize(use, MIRType::Float32)) return false; continue; } // Specialize phis with int32 and double operands as double. if (IsTypeRepresentableAsDouble(use->type()) && IsTypeRepresentableAsDouble(phi->type())) { if (!respecialize(use, MIRType::Double)) return false; continue; } // This phi in our use chain can now no longer be specialized. if (!respecialize(use, MIRType::Value)) return false; } } return true; } bool TypeAnalyzer::specializePhis() { Vector<MPhi*, 0, SystemAllocPolicy> phisWithEmptyInputTypes; for (PostorderIterator block(graph.poBegin()); block != graph.poEnd(); block++) { if (mir->shouldCancel("Specialize Phis (main loop)")) return false; for (MPhiIterator phi(block->phisBegin()); phi != block->phisEnd(); phi++) { if (mir->shouldCancel("Specialize Phis (inner loop)")) return false; bool hasInputsWithEmptyTypes; MIRType type = GuessPhiType(*phi, &hasInputsWithEmptyTypes); phi->specialize(type); if (type == MIRType::None) { // We tried to guess the type but failed because all operands are // phis we still have to visit. Set the triedToSpecialize flag but // don't propagate the type to other phis, propagateSpecialization // will do that once we know the type of one of the operands. // Edge case: when this phi has a non-phi input with an empty // typeset, it's possible for two phis to have a cyclic // dependency and they will both have MIRType::None. Specialize // such phis to MIRType::Value later on. if (hasInputsWithEmptyTypes && !phisWithEmptyInputTypes.append(*phi)) return false; continue; } if (!propagateSpecialization(*phi)) return false; } } do { while (!phiWorklist_.empty()) { if (mir->shouldCancel("Specialize Phis (worklist)")) return false; MPhi* phi = popPhi(); if (!propagateSpecialization(phi)) return false; } // When two phis have a cyclic dependency and inputs that have an empty // typeset (which are ignored by GuessPhiType), we may still have to // specialize these to MIRType::Value. while (!phisWithEmptyInputTypes.empty()) { if (mir->shouldCancel("Specialize Phis (phisWithEmptyInputTypes)")) return false; MPhi* phi = phisWithEmptyInputTypes.popCopy(); if (phi->type() == MIRType::None) { phi->specialize(MIRType::Value); if (!propagateSpecialization(phi)) return false; } } } while (!phiWorklist_.empty()); return true; } bool TypeAnalyzer::adjustPhiInputs(MPhi* phi) { MIRType phiType = phi->type(); MOZ_ASSERT(phiType != MIRType::None); // If we specialized a type that's not Value, there are 3 cases: // 1. Every input is of that type. // 2. Every observed input is of that type (i.e., some inputs haven't been executed yet). // 3. Inputs were doubles and int32s, and was specialized to double. if (phiType != MIRType::Value) { for (size_t i = 0, e = phi->numOperands(); i < e; i++) { MDefinition* in = phi->getOperand(i); if (in->type() == phiType) continue; if (!alloc().ensureBallast()) return false; if (in->isBox() && in->toBox()->input()->type() == phiType) { phi->replaceOperand(i, in->toBox()->input()); } else { MInstruction* replacement; if (phiType == MIRType::Double && IsFloatType(in->type())) { // Convert int32 operands to double. replacement = MToDouble::New(alloc(), in); } else if (phiType == MIRType::Float32) { if (in->type() == MIRType::Int32 || in->type() == MIRType::Double) { replacement = MToFloat32::New(alloc(), in); } else { // See comment below if (in->type() != MIRType::Value) { MBox* box = MBox::New(alloc(), in); in->block()->insertBefore(in->block()->lastIns(), box); in = box; } MUnbox* unbox = MUnbox::New(alloc(), in, MIRType::Double, MUnbox::Fallible); in->block()->insertBefore(in->block()->lastIns(), unbox); replacement = MToFloat32::New(alloc(), in); } } else { // If we know this branch will fail to convert to phiType, // insert a box that'll immediately fail in the fallible unbox // below. if (in->type() != MIRType::Value) { MBox* box = MBox::New(alloc(), in); in->block()->insertBefore(in->block()->lastIns(), box); in = box; } // Be optimistic and insert unboxes when the operand is a // value. replacement = MUnbox::New(alloc(), in, phiType, MUnbox::Fallible); } in->block()->insertBefore(in->block()->lastIns(), replacement); phi->replaceOperand(i, replacement); } } return true; } // Box every typed input. for (size_t i = 0, e = phi->numOperands(); i < e; i++) { MDefinition* in = phi->getOperand(i); if (in->type() == MIRType::Value) continue; // The input is being explicitly unboxed, so sneak past and grab // the original box. if (in->isUnbox() && phi->typeIncludes(in->toUnbox()->input())) in = in->toUnbox()->input(); if (in->type() != MIRType::Value) { if (!alloc().ensureBallast()) return false; MBasicBlock* pred = phi->block()->getPredecessor(i); in = AlwaysBoxAt(alloc(), pred->lastIns(), in); } phi->replaceOperand(i, in); } return true; } bool TypeAnalyzer::adjustInputs(MDefinition* def) { // Definitions such as MPhi have no type policy. if (!def->isInstruction()) return true; MInstruction* ins = def->toInstruction(); TypePolicy* policy = ins->typePolicy(); if (policy && !policy->adjustInputs(alloc(), ins)) return false; return true; } void TypeAnalyzer::replaceRedundantPhi(MPhi* phi) { MBasicBlock* block = phi->block(); js::Value v; switch (phi->type()) { case MIRType::Undefined: v = UndefinedValue(); break; case MIRType::Null: v = NullValue(); break; case MIRType::MagicOptimizedArguments: v = MagicValue(JS_OPTIMIZED_ARGUMENTS); break; case MIRType::MagicOptimizedOut: v = MagicValue(JS_OPTIMIZED_OUT); break; case MIRType::MagicUninitializedLexical: v = MagicValue(JS_UNINITIALIZED_LEXICAL); break; default: MOZ_CRASH("unexpected type"); } MConstant* c = MConstant::New(alloc(), v); // The instruction pass will insert the box block->insertBefore(*(block->begin()), c); phi->justReplaceAllUsesWith(c); } bool TypeAnalyzer::insertConversions() { // Instructions are processed in reverse postorder: all uses are defs are // seen before uses. This ensures that output adjustment (which may rewrite // inputs of uses) does not conflict with input adjustment. for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); block++) { if (mir->shouldCancel("Insert Conversions")) return false; for (MPhiIterator iter(block->phisBegin()), end(block->phisEnd()); iter != end; ) { MPhi* phi = *iter++; if (phi->type() == MIRType::Undefined || phi->type() == MIRType::Null || phi->type() == MIRType::MagicOptimizedArguments || phi->type() == MIRType::MagicOptimizedOut || phi->type() == MIRType::MagicUninitializedLexical) { replaceRedundantPhi(phi); block->discardPhi(phi); } else { if (!adjustPhiInputs(phi)) return false; } } // AdjustInputs can add/remove/mutate instructions before and after the // current instruction. Only increment the iterator after it is finished. for (MInstructionIterator iter(block->begin()); iter != block->end(); iter++) { if (!alloc().ensureBallast()) return false; if (!adjustInputs(*iter)) return false; } } return true; } // This function tries to emit Float32 specialized operations whenever it's possible. // MIR nodes are flagged as: // - Producers, when they can create Float32 that might need to be coerced into a Double. // Loads in Float32 arrays and conversions to Float32 are producers. // - Consumers, when they can have Float32 as inputs and validate a legal use of a Float32. // Stores in Float32 arrays and conversions to Float32 are consumers. // - Float32 commutative, when using the Float32 instruction instead of the Double instruction // does not result in a compound loss of precision. This is the case for +, -, /, * with 2 // operands, for instance. However, an addition with 3 operands is not commutative anymore, // so an intermediate coercion is needed. // Except for phis, all these flags are known after Ion building, so they cannot change during // the process. // // The idea behind the algorithm is easy: whenever we can prove that a commutative operation // has only producers as inputs and consumers as uses, we can specialize the operation as a // float32 operation. Otherwise, we have to convert all float32 inputs to doubles. Even // if a lot of conversions are produced, GVN will take care of eliminating the redundant ones. // // Phis have a special status. Phis need to be flagged as producers or consumers as they can // be inputs or outputs of commutative instructions. Fortunately, producers and consumers // properties are such that we can deduce the property using all non phis inputs first (which form // an initial phi graph) and then propagate all properties from one phi to another using a // fixed point algorithm. The algorithm is ensured to terminate as each iteration has less or as // many flagged phis as the previous iteration (so the worst steady state case is all phis being // flagged as false). // // In a nutshell, the algorithm applies three passes: // 1 - Determine which phis are consumers. Each phi gets an initial value by making a global AND on // all its non-phi inputs. Then each phi propagates its value to other phis. If after propagation, // the flag value changed, we have to reapply the algorithm on all phi operands, as a phi is a // consumer if all of its uses are consumers. // 2 - Determine which phis are producers. It's the same algorithm, except that we have to reapply // the algorithm on all phi uses, as a phi is a producer if all of its operands are producers. // 3 - Go through all commutative operations and ensure their inputs are all producers and their // uses are all consumers. bool TypeAnalyzer::markPhiConsumers() { MOZ_ASSERT(phiWorklist_.empty()); // Iterate in postorder so worklist is initialized to RPO. for (PostorderIterator block(graph.poBegin()); block != graph.poEnd(); ++block) { if (mir->shouldCancel("Ensure Float32 commutativity - Consumer Phis - Initial state")) return false; for (MPhiIterator phi(block->phisBegin()); phi != block->phisEnd(); ++phi) { MOZ_ASSERT(!phi->isInWorklist()); bool canConsumeFloat32 = true; for (MUseDefIterator use(*phi); canConsumeFloat32 && use; use++) { MDefinition* usedef = use.def(); canConsumeFloat32 &= usedef->isPhi() || usedef->canConsumeFloat32(use.use()); } phi->setCanConsumeFloat32(canConsumeFloat32); if (canConsumeFloat32 && !addPhiToWorklist(*phi)) return false; } } while (!phiWorklist_.empty()) { if (mir->shouldCancel("Ensure Float32 commutativity - Consumer Phis - Fixed point")) return false; MPhi* phi = popPhi(); MOZ_ASSERT(phi->canConsumeFloat32(nullptr /* unused */)); bool validConsumer = true; for (MUseDefIterator use(phi); use; use++) { MDefinition* def = use.def(); if (def->isPhi() && !def->canConsumeFloat32(use.use())) { validConsumer = false; break; } } if (validConsumer) continue; // Propagate invalidated phis phi->setCanConsumeFloat32(false); for (size_t i = 0, e = phi->numOperands(); i < e; ++i) { MDefinition* input = phi->getOperand(i); if (input->isPhi() && !input->isInWorklist() && input->canConsumeFloat32(nullptr /* unused */)) { if (!addPhiToWorklist(input->toPhi())) return false; } } } return true; } bool TypeAnalyzer::markPhiProducers() { MOZ_ASSERT(phiWorklist_.empty()); // Iterate in reverse postorder so worklist is initialized to PO. for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); ++block) { if (mir->shouldCancel("Ensure Float32 commutativity - Producer Phis - initial state")) return false; for (MPhiIterator phi(block->phisBegin()); phi != block->phisEnd(); ++phi) { MOZ_ASSERT(!phi->isInWorklist()); bool canProduceFloat32 = true; for (size_t i = 0, e = phi->numOperands(); canProduceFloat32 && i < e; ++i) { MDefinition* input = phi->getOperand(i); canProduceFloat32 &= input->isPhi() || input->canProduceFloat32(); } phi->setCanProduceFloat32(canProduceFloat32); if (canProduceFloat32 && !addPhiToWorklist(*phi)) return false; } } while (!phiWorklist_.empty()) { if (mir->shouldCancel("Ensure Float32 commutativity - Producer Phis - Fixed point")) return false; MPhi* phi = popPhi(); MOZ_ASSERT(phi->canProduceFloat32()); bool validProducer = true; for (size_t i = 0, e = phi->numOperands(); i < e; ++i) { MDefinition* input = phi->getOperand(i); if (input->isPhi() && !input->canProduceFloat32()) { validProducer = false; break; } } if (validProducer) continue; // Propagate invalidated phis phi->setCanProduceFloat32(false); for (MUseDefIterator use(phi); use; use++) { MDefinition* def = use.def(); if (def->isPhi() && !def->isInWorklist() && def->canProduceFloat32()) { if (!addPhiToWorklist(def->toPhi())) return false; } } } return true; } bool TypeAnalyzer::specializeValidFloatOps() { for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); ++block) { if (mir->shouldCancel("Ensure Float32 commutativity - Instructions")) return false; for (MInstructionIterator ins(block->begin()); ins != block->end(); ++ins) { if (!ins->isFloat32Commutative()) continue; if (ins->type() == MIRType::Float32) continue; if (!alloc().ensureBallast()) return false; // This call will try to specialize the instruction iff all uses are consumers and // all inputs are producers. ins->trySpecializeFloat32(alloc()); } } return true; } bool TypeAnalyzer::graphContainsFloat32() { for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); ++block) { for (MDefinitionIterator def(*block); def; def++) { if (mir->shouldCancel("Ensure Float32 commutativity - Graph contains Float32")) return false; if (def->type() == MIRType::Float32) return true; } } return false; } bool TypeAnalyzer::tryEmitFloatOperations() { // Asm.js uses the ahead of time type checks to specialize operations, no need to check // them again at this point. if (mir->compilingWasm()) return true; // Check ahead of time that there is at least one definition typed as Float32, otherwise we // don't need this pass. if (!graphContainsFloat32()) return true; if (!markPhiConsumers()) return false; if (!markPhiProducers()) return false; if (!specializeValidFloatOps()) return false; return true; } bool TypeAnalyzer::checkFloatCoherency() { #ifdef DEBUG // Asserts that all Float32 instructions are flowing into Float32 consumers or specialized // operations for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); ++block) { if (mir->shouldCancel("Check Float32 coherency")) return false; for (MDefinitionIterator def(*block); def; def++) { if (def->type() != MIRType::Float32) continue; for (MUseDefIterator use(*def); use; use++) { MDefinition* consumer = use.def(); MOZ_ASSERT(consumer->isConsistentFloat32Use(use.use())); } } } #endif return true; } bool TypeAnalyzer::analyze() { if (!tryEmitFloatOperations()) return false; if (!specializePhis()) return false; if (!insertConversions()) return false; if (!checkFloatCoherency()) return false; return true; } bool jit::ApplyTypeInformation(MIRGenerator* mir, MIRGraph& graph) { TypeAnalyzer analyzer(mir, graph); if (!analyzer.analyze()) return false; return true; } // Check if `def` is only the N-th operand of `useDef`. static inline size_t IsExclusiveNthOperand(MDefinition* useDef, size_t n, MDefinition* def) { uint32_t num = useDef->numOperands(); if (n >= num || useDef->getOperand(n) != def) return false; for (uint32_t i = 0; i < num; i++) { if (i == n) continue; if (useDef->getOperand(i) == def) return false; } return true; } static size_t IsExclusiveThisArg(MCall* call, MDefinition* def) { return IsExclusiveNthOperand(call, MCall::IndexOfThis(), def); } static size_t IsExclusiveFirstArg(MCall* call, MDefinition* def) { return IsExclusiveNthOperand(call, MCall::IndexOfArgument(0), def); } static bool IsRegExpHoistableCall(MCall* call, MDefinition* def) { if (call->isConstructing()) return false; JSAtom* name; if (WrappedFunction* fun = call->getSingleTarget()) { if (!fun->isSelfHostedBuiltin()) return false; name = GetSelfHostedFunctionName(fun->rawJSFunction()); } else { MDefinition* funDef = call->getFunction(); if (funDef->isDebugCheckSelfHosted()) funDef = funDef->toDebugCheckSelfHosted()->input(); if (funDef->isTypeBarrier()) funDef = funDef->toTypeBarrier()->input(); if (!funDef->isCallGetIntrinsicValue()) return false; name = funDef->toCallGetIntrinsicValue()->name(); } // Hoistable only if the RegExp is the first argument of RegExpBuiltinExec. CompileRuntime* runtime = GetJitContext()->runtime; if (name == runtime->names().RegExpBuiltinExec || name == runtime->names().UnwrapAndCallRegExpBuiltinExec || name == runtime->names().RegExpMatcher || name == runtime->names().RegExpTester || name == runtime->names().RegExpSearcher) { return IsExclusiveFirstArg(call, def); } if (name == runtime->names().RegExp_prototype_Exec) return IsExclusiveThisArg(call, def); return false; } static bool CanCompareRegExp(MCompare* compare, MDefinition* def) { MDefinition* value; if (compare->lhs() == def) { value = compare->rhs(); } else { MOZ_ASSERT(compare->rhs() == def); value = compare->lhs(); } // Comparing two regexp that weren't cloned will give different result // than if they were cloned. if (value->mightBeType(MIRType::Object)) return false; // Make sure @@toPrimitive is not called which could notice // the difference between a not cloned/cloned regexp. JSOp op = compare->jsop(); // Strict equality comparison won't invoke @@toPrimitive. if (op == JSOP_STRICTEQ || op == JSOP_STRICTNE) return true; if (op != JSOP_EQ && op != JSOP_NE) { // Relational comparison always invoke @@toPrimitive. MOZ_ASSERT(op == JSOP_GT || op == JSOP_GE || op == JSOP_LT || op == JSOP_LE); return false; } // Loose equality comparison can invoke @@toPrimitive. if (value->mightBeType(MIRType::Boolean) || value->mightBeType(MIRType::String) || value->mightBeType(MIRType::Int32) || value->mightBeType(MIRType::Double) || value->mightBeType(MIRType::Float32) || value->mightBeType(MIRType::Symbol)) { return false; } return true; } static inline void SetNotInWorklist(MDefinitionVector& worklist) { for (size_t i = 0; i < worklist.length(); i++) worklist[i]->setNotInWorklist(); } static bool IsRegExpHoistable(MIRGenerator* mir, MDefinition* regexp, MDefinitionVector& worklist, bool* hoistable) { MOZ_ASSERT(worklist.length() == 0); if (!worklist.append(regexp)) return false; regexp->setInWorklist(); for (size_t i = 0; i < worklist.length(); i++) { MDefinition* def = worklist[i]; if (mir->shouldCancel("IsRegExpHoistable outer loop")) return false; for (MUseIterator use = def->usesBegin(); use != def->usesEnd(); use++) { if (mir->shouldCancel("IsRegExpHoistable inner loop")) return false; // Ignore resume points. At this point all uses are listed. // No DCE or GVN or something has happened. if (use->consumer()->isResumePoint()) continue; MDefinition* useDef = use->consumer()->toDefinition(); // Step through a few white-listed ops. if (useDef->isPhi() || useDef->isFilterTypeSet() || useDef->isGuardShape()) { if (useDef->isInWorklist()) continue; if (!worklist.append(useDef)) return false; useDef->setInWorklist(); continue; } // Instructions that doesn't invoke unknown code that may modify // RegExp instance or pass it to elsewhere. if (useDef->isRegExpMatcher() || useDef->isRegExpTester() || useDef->isRegExpSearcher()) { if (IsExclusiveNthOperand(useDef, 0, def)) continue; } else if (useDef->isLoadFixedSlot() || useDef->isTypeOf()) { continue; } else if (useDef->isCompare()) { if (CanCompareRegExp(useDef->toCompare(), def)) continue; } // Instructions that modifies `lastIndex` property. else if (useDef->isStoreFixedSlot()) { if (IsExclusiveNthOperand(useDef, 0, def)) { MStoreFixedSlot* store = useDef->toStoreFixedSlot(); if (store->slot() == RegExpObject::lastIndexSlot()) continue; } } else if (useDef->isSetPropertyCache()) { if (IsExclusiveNthOperand(useDef, 0, def)) { MSetPropertyCache* setProp = useDef->toSetPropertyCache(); if (setProp->idval()->isConstant()) { Value propIdVal = setProp->idval()->toConstant()->toJSValue(); if (propIdVal.isString()) { CompileRuntime* runtime = GetJitContext()->runtime; if (propIdVal.toString() == runtime->names().lastIndex) continue; } } } } // MCall is safe only for some known safe functions. else if (useDef->isCall()) { if (IsRegExpHoistableCall(useDef->toCall(), def)) continue; } // Everything else is unsafe. SetNotInWorklist(worklist); worklist.clear(); *hoistable = false; return true; } } SetNotInWorklist(worklist); worklist.clear(); *hoistable = true; return true; } bool jit::MakeMRegExpHoistable(MIRGenerator* mir, MIRGraph& graph) { MDefinitionVector worklist(graph.alloc()); for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); block++) { if (mir->shouldCancel("MakeMRegExpHoistable outer loop")) return false; for (MDefinitionIterator iter(*block); iter; iter++) { if (!*iter) MOZ_CRASH("confirm bug 1263794."); if (mir->shouldCancel("MakeMRegExpHoistable inner loop")) return false; if (!iter->isRegExp()) continue; MRegExp* regexp = iter->toRegExp(); bool hoistable = false; if (!IsRegExpHoistable(mir, regexp, worklist, &hoistable)) return false; if (!hoistable) continue; // Make MRegExp hoistable regexp->setMovable(); regexp->setDoNotClone(); // That would be incorrect for global/sticky, because lastIndex // could be wrong. Therefore setting the lastIndex to 0. That is // faster than a not movable regexp. RegExpObject* source = regexp->source(); if (source->sticky() || source->global()) { if (!graph.alloc().ensureBallast()) return false; MConstant* zero = MConstant::New(graph.alloc(), Int32Value(0)); regexp->block()->insertAfter(regexp, zero); MStoreFixedSlot* lastIndex = MStoreFixedSlot::New(graph.alloc(), regexp, RegExpObject::lastIndexSlot(), zero); regexp->block()->insertAfter(zero, lastIndex); } } } return true; } void jit::RenumberBlocks(MIRGraph& graph) { size_t id = 0; for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); block++) block->setId(id++); } // A utility for code which deletes blocks. Renumber the remaining blocks, // recompute dominators, and optionally recompute AliasAnalysis dependencies. bool jit::AccountForCFGChanges(MIRGenerator* mir, MIRGraph& graph, bool updateAliasAnalysis, bool underValueNumberer) { // Renumber the blocks and clear out the old dominator info. size_t id = 0; for (ReversePostorderIterator i(graph.rpoBegin()), e(graph.rpoEnd()); i != e; ++i) { i->clearDominatorInfo(); i->setId(id++); } // Recompute dominator info. if (!BuildDominatorTree(graph)) return false; // If needed, update alias analysis dependencies. if (updateAliasAnalysis) { TraceLoggerThread* logger; if (GetJitContext()->onMainThread()) logger = TraceLoggerForMainThread(GetJitContext()->runtime); else logger = TraceLoggerForCurrentThread(); AutoTraceLog log(logger, TraceLogger_AliasAnalysis); if (JitOptions.disableFlowAA) { if (!AliasAnalysis(mir, graph).analyze()) return false; } else { if (!FlowAliasAnalysis(mir, graph).analyze()) return false; } } AssertExtendedGraphCoherency(graph, underValueNumberer); return true; } // Remove all blocks not marked with isMarked(). Unmark all remaining blocks. // Alias analysis dependencies may be invalid after calling this function. bool jit::RemoveUnmarkedBlocks(MIRGenerator* mir, MIRGraph& graph, uint32_t numMarkedBlocks) { if (numMarkedBlocks == graph.numBlocks()) { // If all blocks are marked, no blocks need removal. Just clear the // marks. We'll still need to update the dominator tree below though, // since we may have removed edges even if we didn't remove any blocks. graph.unmarkBlocks(); } else { // As we are going to remove edges and basic blocks, we have to mark // instructions which would be needed by baseline if we were to // bailout. for (PostorderIterator it(graph.poBegin()); it != graph.poEnd();) { MBasicBlock* block = *it++; if (!block->isMarked()) continue; FlagAllOperandsAsHavingRemovedUses(mir, block); } // Find unmarked blocks and remove them. for (ReversePostorderIterator iter(graph.rpoBegin()); iter != graph.rpoEnd();) { MBasicBlock* block = *iter++; if (block->isMarked()) { block->unmark(); continue; } // The block is unreachable. Clear out the loop header flag, as // we're doing the sweep of a mark-and-sweep here, so we no longer // need to worry about whether an unmarked block is a loop or not. if (block->isLoopHeader()) block->clearLoopHeader(); for (size_t i = 0, e = block->numSuccessors(); i != e; ++i) block->getSuccessor(i)->removePredecessor(block); graph.removeBlockIncludingPhis(block); } } // Renumber the blocks and update the dominator tree. return AccountForCFGChanges(mir, graph, /*updateAliasAnalysis=*/false); } // A Simple, Fast Dominance Algorithm by Cooper et al. // Modified to support empty intersections for OSR, and in RPO. static MBasicBlock* IntersectDominators(MBasicBlock* block1, MBasicBlock* block2) { MBasicBlock* finger1 = block1; MBasicBlock* finger2 = block2; MOZ_ASSERT(finger1); MOZ_ASSERT(finger2); // In the original paper, the block ID comparisons are on the postorder index. // This implementation iterates in RPO, so the comparisons are reversed. // For this function to be called, the block must have multiple predecessors. // If a finger is then found to be self-dominating, it must therefore be // reachable from multiple roots through non-intersecting control flow. // nullptr is returned in this case, to denote an empty intersection. while (finger1->id() != finger2->id()) { while (finger1->id() > finger2->id()) { MBasicBlock* idom = finger1->immediateDominator(); if (idom == finger1) return nullptr; // Empty intersection. finger1 = idom; } while (finger2->id() > finger1->id()) { MBasicBlock* idom = finger2->immediateDominator(); if (idom == finger2) return nullptr; // Empty intersection. finger2 = idom; } } return finger1; } void jit::ClearDominatorTree(MIRGraph& graph) { for (MBasicBlockIterator iter = graph.begin(); iter != graph.end(); iter++) iter->clearDominatorInfo(); } static void ComputeImmediateDominators(MIRGraph& graph) { // The default start block is a root and therefore only self-dominates. MBasicBlock* startBlock = graph.entryBlock(); startBlock->setImmediateDominator(startBlock); // Any OSR block is a root and therefore only self-dominates. MBasicBlock* osrBlock = graph.osrBlock(); if (osrBlock) osrBlock->setImmediateDominator(osrBlock); bool changed = true; while (changed) { changed = false; ReversePostorderIterator block = graph.rpoBegin(); // For each block in RPO, intersect all dominators. for (; block != graph.rpoEnd(); block++) { // If a node has once been found to have no exclusive dominator, // it will never have an exclusive dominator, so it may be skipped. if (block->immediateDominator() == *block) continue; // A block with no predecessors is not reachable from any entry, so // it self-dominates. if (MOZ_UNLIKELY(block->numPredecessors() == 0)) { block->setImmediateDominator(*block); continue; } MBasicBlock* newIdom = block->getPredecessor(0); // Find the first common dominator. for (size_t i = 1; i < block->numPredecessors(); i++) { MBasicBlock* pred = block->getPredecessor(i); if (pred->immediateDominator() == nullptr) continue; newIdom = IntersectDominators(pred, newIdom); // If there is no common dominator, the block self-dominates. if (newIdom == nullptr) { block->setImmediateDominator(*block); changed = true; break; } } if (newIdom && block->immediateDominator() != newIdom) { block->setImmediateDominator(newIdom); changed = true; } } } #ifdef DEBUG // Assert that all blocks have dominator information. for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) { MOZ_ASSERT(block->immediateDominator() != nullptr); } #endif } bool jit::BuildDominatorTree(MIRGraph& graph) { ComputeImmediateDominators(graph); Vector<MBasicBlock*, 4, JitAllocPolicy> worklist(graph.alloc()); // Traversing through the graph in post-order means that every non-phi use // of a definition is visited before the def itself. Since a def // dominates its uses, by the time we reach a particular // block, we have processed all of its dominated children, so // block->numDominated() is accurate. for (PostorderIterator i(graph.poBegin()); i != graph.poEnd(); i++) { MBasicBlock* child = *i; MBasicBlock* parent = child->immediateDominator(); // Dominance is defined such that blocks always dominate themselves. child->addNumDominated(1); // If the block only self-dominates, it has no definite parent. // Add it to the worklist as a root for pre-order traversal. // This includes all roots. Order does not matter. if (child == parent) { if (!worklist.append(child)) return false; continue; } if (!parent->addImmediatelyDominatedBlock(child)) return false; parent->addNumDominated(child->numDominated()); } #ifdef DEBUG // If compiling with OSR, many blocks will self-dominate. // Without OSR, there is only one root block which dominates all. if (!graph.osrBlock()) MOZ_ASSERT(graph.entryBlock()->numDominated() == graph.numBlocks()); #endif // Now, iterate through the dominator tree in pre-order and annotate every // block with its index in the traversal. size_t index = 0; while (!worklist.empty()) { MBasicBlock* block = worklist.popCopy(); block->setDomIndex(index); if (!worklist.append(block->immediatelyDominatedBlocksBegin(), block->immediatelyDominatedBlocksEnd())) { return false; } index++; } return true; } bool jit::BuildPhiReverseMapping(MIRGraph& graph) { // Build a mapping such that given a basic block, whose successor has one or // more phis, we can find our specific input to that phi. To make this fast // mapping work we rely on a specific property of our structured control // flow graph: For a block with phis, its predecessors each have only one // successor with phis. Consider each case: // * Blocks with less than two predecessors cannot have phis. // * Breaks. A break always has exactly one successor, and the break // catch block has exactly one predecessor for each break, as // well as a final predecessor for the actual loop exit. // * Continues. A continue always has exactly one successor, and the // continue catch block has exactly one predecessor for each // continue, as well as a final predecessor for the actual // loop continuation. The continue itself has exactly one // successor. // * An if. Each branch as exactly one predecessor. // * A switch. Each branch has exactly one predecessor. // * Loop tail. A new block is always created for the exit, and if a // break statement is present, the exit block will forward // directly to the break block. for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) { if (block->phisEmpty()) continue; // Assert on the above. for (size_t j = 0; j < block->numPredecessors(); j++) { MBasicBlock* pred = block->getPredecessor(j); #ifdef DEBUG size_t numSuccessorsWithPhis = 0; for (size_t k = 0; k < pred->numSuccessors(); k++) { MBasicBlock* successor = pred->getSuccessor(k); if (!successor->phisEmpty()) numSuccessorsWithPhis++; } MOZ_ASSERT(numSuccessorsWithPhis <= 1); #endif pred->setSuccessorWithPhis(*block, j); } } return true; } #ifdef DEBUG static bool CheckSuccessorImpliesPredecessor(MBasicBlock* A, MBasicBlock* B) { // Assuming B = succ(A), verify A = pred(B). for (size_t i = 0; i < B->numPredecessors(); i++) { if (A == B->getPredecessor(i)) return true; } return false; } static bool CheckPredecessorImpliesSuccessor(MBasicBlock* A, MBasicBlock* B) { // Assuming B = pred(A), verify A = succ(B). for (size_t i = 0; i < B->numSuccessors(); i++) { if (A == B->getSuccessor(i)) return true; } return false; } // If you have issues with the usesBalance assertions, then define the macro // _DEBUG_CHECK_OPERANDS_USES_BALANCE to spew information on the error output. // This output can then be processed with the following awk script to filter and // highlight which checks are missing or if there is an unexpected operand / // use. // // define _DEBUG_CHECK_OPERANDS_USES_BALANCE 1 /* $ ./js 2>stderr.log $ gawk ' /^==Check/ { context = ""; state = $2; } /^[a-z]/ { context = context "\n\t" $0; } /^==End/ { if (state == "Operand") { list[context] = list[context] - 1; } else if (state == "Use") { list[context] = list[context] + 1; } } END { for (ctx in list) { if (list[ctx] > 0) { print "Missing operand check", ctx, "\n" } if (list[ctx] < 0) { print "Missing use check", ctx, "\n" } }; }' < stderr.log */ static void CheckOperand(const MNode* consumer, const MUse* use, int32_t* usesBalance) { MOZ_ASSERT(use->hasProducer()); MDefinition* producer = use->producer(); MOZ_ASSERT(!producer->isDiscarded()); MOZ_ASSERT(producer->block() != nullptr); MOZ_ASSERT(use->consumer() == consumer); #ifdef _DEBUG_CHECK_OPERANDS_USES_BALANCE fprintf(stderr, "==Check Operand\n"); use->producer()->dump(stderr); fprintf(stderr, " index: %" PRIuSIZE "\n", use->consumer()->indexOf(use)); use->consumer()->dump(stderr); fprintf(stderr, "==End\n"); #endif --*usesBalance; } static void CheckUse(const MDefinition* producer, const MUse* use, int32_t* usesBalance) { MOZ_ASSERT(!use->consumer()->block()->isDead()); MOZ_ASSERT_IF(use->consumer()->isDefinition(), !use->consumer()->toDefinition()->isDiscarded()); MOZ_ASSERT(use->consumer()->block() != nullptr); MOZ_ASSERT(use->consumer()->getOperand(use->index()) == producer); #ifdef _DEBUG_CHECK_OPERANDS_USES_BALANCE fprintf(stderr, "==Check Use\n"); use->producer()->dump(stderr); fprintf(stderr, " index: %" PRIuSIZE "\n", use->consumer()->indexOf(use)); use->consumer()->dump(stderr); fprintf(stderr, "==End\n"); #endif ++*usesBalance; } // To properly encode entry resume points, we have to ensure that all the // operands of the entry resume point are located before the safeInsertTop // location. static void AssertOperandsBeforeSafeInsertTop(MResumePoint* resume) { MBasicBlock* block = resume->block(); if (block == block->graph().osrBlock()) return; MInstruction* stop = block->safeInsertTop(); for (size_t i = 0, e = resume->numOperands(); i < e; ++i) { MDefinition* def = resume->getOperand(i); if (def->block() != block) continue; if (def->isPhi()) continue; for (MInstructionIterator ins = block->begin(); true; ins++) { if (*ins == def) break; MOZ_ASSERT(*ins != stop, "Resume point operand located after the safeInsertTop location"); } } } #endif // DEBUG void jit::AssertBasicGraphCoherency(MIRGraph& graph) { #ifdef DEBUG MOZ_ASSERT(graph.entryBlock()->numPredecessors() == 0); MOZ_ASSERT(graph.entryBlock()->phisEmpty()); MOZ_ASSERT(!graph.entryBlock()->unreachable()); if (MBasicBlock* osrBlock = graph.osrBlock()) { MOZ_ASSERT(osrBlock->numPredecessors() == 0); MOZ_ASSERT(osrBlock->phisEmpty()); MOZ_ASSERT(osrBlock != graph.entryBlock()); MOZ_ASSERT(!osrBlock->unreachable()); } if (MResumePoint* resumePoint = graph.entryResumePoint()) MOZ_ASSERT(resumePoint->block() == graph.entryBlock()); // Assert successor and predecessor list coherency. uint32_t count = 0; int32_t usesBalance = 0; for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) { count++; MOZ_ASSERT(&block->graph() == &graph); MOZ_ASSERT(!block->isDead()); MOZ_ASSERT_IF(block->outerResumePoint() != nullptr, block->entryResumePoint() != nullptr); for (size_t i = 0; i < block->numSuccessors(); i++) MOZ_ASSERT(CheckSuccessorImpliesPredecessor(*block, block->getSuccessor(i))); for (size_t i = 0; i < block->numPredecessors(); i++) MOZ_ASSERT(CheckPredecessorImpliesSuccessor(*block, block->getPredecessor(i))); if (MResumePoint* resume = block->entryResumePoint()) { MOZ_ASSERT(!resume->instruction()); MOZ_ASSERT(resume->block() == *block); AssertOperandsBeforeSafeInsertTop(resume); } if (MResumePoint* resume = block->outerResumePoint()) { MOZ_ASSERT(!resume->instruction()); MOZ_ASSERT(resume->block() == *block); } for (MResumePointIterator iter(block->resumePointsBegin()); iter != block->resumePointsEnd(); iter++) { // We cannot yet assert that is there is no instruction then this is // the entry resume point because we are still storing resume points // in the InlinePropertyTable. MOZ_ASSERT_IF(iter->instruction(), iter->instruction()->block() == *block); for (uint32_t i = 0, e = iter->numOperands(); i < e; i++) CheckOperand(*iter, iter->getUseFor(i), &usesBalance); } for (MPhiIterator phi(block->phisBegin()); phi != block->phisEnd(); phi++) { MOZ_ASSERT(phi->numOperands() == block->numPredecessors()); MOZ_ASSERT(!phi->isRecoveredOnBailout()); MOZ_ASSERT(phi->type() != MIRType::None); MOZ_ASSERT(phi->dependency() == nullptr); } for (MDefinitionIterator iter(*block); iter; iter++) { MOZ_ASSERT(iter->block() == *block); MOZ_ASSERT_IF(iter->hasUses(), iter->type() != MIRType::None); MOZ_ASSERT(!iter->isDiscarded()); MOZ_ASSERT_IF(iter->isStart(), *block == graph.entryBlock() || *block == graph.osrBlock()); MOZ_ASSERT_IF(iter->isParameter(), *block == graph.entryBlock() || *block == graph.osrBlock()); MOZ_ASSERT_IF(iter->isOsrEntry(), *block == graph.osrBlock()); MOZ_ASSERT_IF(iter->isOsrValue(), *block == graph.osrBlock()); // Assert that use chains are valid for this instruction. for (uint32_t i = 0, end = iter->numOperands(); i < end; i++) CheckOperand(*iter, iter->getUseFor(i), &usesBalance); for (MUseIterator use(iter->usesBegin()); use != iter->usesEnd(); use++) CheckUse(*iter, *use, &usesBalance); if (iter->isInstruction()) { if (MResumePoint* resume = iter->toInstruction()->resumePoint()) { MOZ_ASSERT(resume->instruction() == *iter); MOZ_ASSERT(resume->block() == *block); MOZ_ASSERT(resume->block()->entryResumePoint() != nullptr); } } if (iter->isRecoveredOnBailout()) MOZ_ASSERT(!iter->hasLiveDefUses()); } // The control instruction is not visited by the MDefinitionIterator. MControlInstruction* control = block->lastIns(); MOZ_ASSERT(control->block() == *block); MOZ_ASSERT(!control->hasUses()); MOZ_ASSERT(control->type() == MIRType::None); MOZ_ASSERT(!control->isDiscarded()); MOZ_ASSERT(!control->isRecoveredOnBailout()); MOZ_ASSERT(control->resumePoint() == nullptr); for (uint32_t i = 0, end = control->numOperands(); i < end; i++) CheckOperand(control, control->getUseFor(i), &usesBalance); for (size_t i = 0; i < control->numSuccessors(); i++) MOZ_ASSERT(control->getSuccessor(i)); } // In case issues, see the _DEBUG_CHECK_OPERANDS_USES_BALANCE macro above. MOZ_ASSERT(usesBalance <= 0, "More use checks than operand checks"); MOZ_ASSERT(usesBalance >= 0, "More operand checks than use checks"); MOZ_ASSERT(graph.numBlocks() == count); #endif } #ifdef DEBUG static void AssertReversePostorder(MIRGraph& graph) { // Check that every block is visited after all its predecessors (except backedges). for (ReversePostorderIterator iter(graph.rpoBegin()); iter != graph.rpoEnd(); ++iter) { MBasicBlock* block = *iter; MOZ_ASSERT(!block->isMarked()); for (size_t i = 0; i < block->numPredecessors(); i++) { MBasicBlock* pred = block->getPredecessor(i); if (!pred->isMarked()) { MOZ_ASSERT(pred->isLoopBackedge()); MOZ_ASSERT(block->backedge() == pred); } } block->mark(); } graph.unmarkBlocks(); } #endif #ifdef DEBUG static void AssertDominatorTree(MIRGraph& graph) { // Check dominators. MOZ_ASSERT(graph.entryBlock()->immediateDominator() == graph.entryBlock()); if (MBasicBlock* osrBlock = graph.osrBlock()) MOZ_ASSERT(osrBlock->immediateDominator() == osrBlock); else MOZ_ASSERT(graph.entryBlock()->numDominated() == graph.numBlocks()); size_t i = graph.numBlocks(); size_t totalNumDominated = 0; for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) { MOZ_ASSERT(block->dominates(*block)); MBasicBlock* idom = block->immediateDominator(); MOZ_ASSERT(idom->dominates(*block)); MOZ_ASSERT(idom == *block || idom->id() < block->id()); if (idom == *block) { totalNumDominated += block->numDominated(); } else { bool foundInParent = false; for (size_t j = 0; j < idom->numImmediatelyDominatedBlocks(); j++) { if (idom->getImmediatelyDominatedBlock(j) == *block) { foundInParent = true; break; } } MOZ_ASSERT(foundInParent); } size_t numDominated = 1; for (size_t j = 0; j < block->numImmediatelyDominatedBlocks(); j++) { MBasicBlock* dom = block->getImmediatelyDominatedBlock(j); MOZ_ASSERT(block->dominates(dom)); MOZ_ASSERT(dom->id() > block->id()); MOZ_ASSERT(dom->immediateDominator() == *block); numDominated += dom->numDominated(); } MOZ_ASSERT(block->numDominated() == numDominated); MOZ_ASSERT(block->numDominated() <= i); MOZ_ASSERT(block->numSuccessors() != 0 || block->numDominated() == 1); i--; } MOZ_ASSERT(i == 0); MOZ_ASSERT(totalNumDominated == graph.numBlocks()); } #endif void jit::AssertGraphCoherency(MIRGraph& graph) { #ifdef DEBUG if (!JitOptions.checkGraphConsistency) return; AssertBasicGraphCoherency(graph); AssertReversePostorder(graph); #endif } #ifdef DEBUG static bool IsResumableMIRType(MIRType type) { // see CodeGeneratorShared::encodeAllocation switch (type) { case MIRType::Undefined: case MIRType::Null: case MIRType::Boolean: case MIRType::Int32: case MIRType::Double: case MIRType::Float32: case MIRType::String: case MIRType::Symbol: case MIRType::Object: case MIRType::MagicOptimizedArguments: case MIRType::MagicOptimizedOut: case MIRType::MagicUninitializedLexical: case MIRType::MagicIsConstructing: case MIRType::Value: case MIRType::Int32x4: case MIRType::Int16x8: case MIRType::Int8x16: case MIRType::Float32x4: case MIRType::Bool32x4: case MIRType::Bool16x8: case MIRType::Bool8x16: return true; case MIRType::MagicHole: case MIRType::ObjectOrNull: case MIRType::None: case MIRType::Slots: case MIRType::Elements: case MIRType::Pointer: case MIRType::Shape: case MIRType::ObjectGroup: case MIRType::Doublex2: // NYI, see also RSimdBox::recover case MIRType::SinCosDouble: case MIRType::Int64: return false; } MOZ_CRASH("Unknown MIRType."); } static void AssertResumableOperands(MNode* node) { for (size_t i = 0, e = node->numOperands(); i < e; ++i) { MDefinition* op = node->getOperand(i); if (op->isRecoveredOnBailout()) continue; MOZ_ASSERT(IsResumableMIRType(op->type()), "Resume point cannot encode its operands"); } } static void AssertIfResumableInstruction(MDefinition* def) { if (!def->isRecoveredOnBailout()) return; AssertResumableOperands(def); } static void AssertResumePointDominatedByOperands(MResumePoint* resume) { for (size_t i = 0, e = resume->numOperands(); i < e; ++i) { MDefinition* op = resume->getOperand(i); if (op->type() == MIRType::MagicOptimizedArguments) continue; MOZ_ASSERT(op->block()->dominates(resume->block()), "Resume point is not dominated by its operands"); } } #endif // DEBUG void jit::AssertExtendedGraphCoherency(MIRGraph& graph, bool underValueNumberer) { // Checks the basic GraphCoherency but also other conditions that // do not hold immediately (such as the fact that critical edges // are split) #ifdef DEBUG if (!JitOptions.checkGraphConsistency) return; AssertGraphCoherency(graph); AssertDominatorTree(graph); DebugOnly<uint32_t> idx = 0; for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) { MOZ_ASSERT(block->id() == idx); ++idx; // No critical edges: if (block->numSuccessors() > 1) for (size_t i = 0; i < block->numSuccessors(); i++) MOZ_ASSERT(block->getSuccessor(i)->numPredecessors() == 1); if (block->isLoopHeader()) { if (underValueNumberer && block->numPredecessors() == 3) { // Fixup block. MOZ_ASSERT(block->getPredecessor(1)->numPredecessors() == 0); MOZ_ASSERT(graph.osrBlock(), "Fixup blocks should only exists if we have an osr block."); } else { MOZ_ASSERT(block->numPredecessors() == 2); } MBasicBlock* backedge = block->backedge(); MOZ_ASSERT(backedge->id() >= block->id()); MOZ_ASSERT(backedge->numSuccessors() == 1); MOZ_ASSERT(backedge->getSuccessor(0) == *block); } if (!block->phisEmpty()) { for (size_t i = 0; i < block->numPredecessors(); i++) { MBasicBlock* pred = block->getPredecessor(i); MOZ_ASSERT(pred->successorWithPhis() == *block); MOZ_ASSERT(pred->positionInPhiSuccessor() == i); } } uint32_t successorWithPhis = 0; for (size_t i = 0; i < block->numSuccessors(); i++) if (!block->getSuccessor(i)->phisEmpty()) successorWithPhis++; MOZ_ASSERT(successorWithPhis <= 1); MOZ_ASSERT((successorWithPhis != 0) == (block->successorWithPhis() != nullptr)); // Verify that phi operands dominate the corresponding CFG predecessor // edges. for (MPhiIterator iter(block->phisBegin()), end(block->phisEnd()); iter != end; ++iter) { MPhi* phi = *iter; for (size_t i = 0, e = phi->numOperands(); i < e; ++i) { // We sometimes see a phi with a magic-optimized-arguments // operand defined in the normal entry block, while the phi is // also reachable from the OSR entry (auto-regress/bug779818.js) if (phi->getOperand(i)->type() == MIRType::MagicOptimizedArguments) continue; MOZ_ASSERT(phi->getOperand(i)->block()->dominates(block->getPredecessor(i)), "Phi input is not dominated by its operand"); } } // Verify that instructions are dominated by their operands. for (MInstructionIterator iter(block->begin()), end(block->end()); iter != end; ++iter) { MInstruction* ins = *iter; for (size_t i = 0, e = ins->numOperands(); i < e; ++i) { MDefinition* op = ins->getOperand(i); MBasicBlock* opBlock = op->block(); MOZ_ASSERT(opBlock->dominates(*block), "Instruction is not dominated by its operands"); // If the operand is an instruction in the same block, check // that it comes first. if (opBlock == *block && !op->isPhi()) { MInstructionIterator opIter = block->begin(op->toInstruction()); do { ++opIter; MOZ_ASSERT(opIter != block->end(), "Operand in same block as instruction does not precede"); } while (*opIter != ins); } } AssertIfResumableInstruction(ins); if (MResumePoint* resume = ins->resumePoint()) { AssertResumePointDominatedByOperands(resume); AssertResumableOperands(resume); } } // Verify that the block resume points are dominated by their operands. if (MResumePoint* resume = block->entryResumePoint()) { AssertResumePointDominatedByOperands(resume); AssertResumableOperands(resume); } if (MResumePoint* resume = block->outerResumePoint()) { AssertResumePointDominatedByOperands(resume); AssertResumableOperands(resume); } } #endif } struct BoundsCheckInfo { MBoundsCheck* check; uint32_t validEnd; }; typedef HashMap<uint32_t, BoundsCheckInfo, DefaultHasher<uint32_t>, JitAllocPolicy> BoundsCheckMap; // Compute a hash for bounds checks which ignores constant offsets in the index. static HashNumber BoundsCheckHashIgnoreOffset(MBoundsCheck* check) { SimpleLinearSum indexSum = ExtractLinearSum(check->index()); uintptr_t index = indexSum.term ? uintptr_t(indexSum.term) : 0; uintptr_t length = uintptr_t(check->length()); return index ^ length; } static MBoundsCheck* FindDominatingBoundsCheck(BoundsCheckMap& checks, MBoundsCheck* check, size_t index) { // Since we are traversing the dominator tree in pre-order, when we // are looking at the |index|-th block, the next numDominated() blocks // we traverse are precisely the set of blocks that are dominated. // // So, this value is visible in all blocks if: // index <= index + ins->block->numDominated() // and becomes invalid after that. HashNumber hash = BoundsCheckHashIgnoreOffset(check); BoundsCheckMap::Ptr p = checks.lookup(hash); if (!p || index >= p->value().validEnd) { // We didn't find a dominating bounds check. BoundsCheckInfo info; info.check = check; info.validEnd = index + check->block()->numDominated(); if(!checks.put(hash, info)) return nullptr; return check; } return p->value().check; } static MathSpace ExtractMathSpace(MDefinition* ins) { MOZ_ASSERT(ins->isAdd() || ins->isSub()); MBinaryArithInstruction* arith = nullptr; if (ins->isAdd()) arith = ins->toAdd(); else arith = ins->toSub(); switch (arith->truncateKind()) { case MDefinition::NoTruncate: case MDefinition::TruncateAfterBailouts: // TruncateAfterBailouts is considered as infinite space because the // LinearSum will effectively remove the bailout check. return MathSpace::Infinite; case MDefinition::IndirectTruncate: case MDefinition::Truncate: return MathSpace::Modulo; } MOZ_MAKE_COMPILER_ASSUME_IS_UNREACHABLE("Unknown TruncateKind"); } // Extract a linear sum from ins, if possible (otherwise giving the sum 'ins + 0'). SimpleLinearSum jit::ExtractLinearSum(MDefinition* ins, MathSpace space) { if (ins->isBeta()) ins = ins->getOperand(0); if (ins->type() != MIRType::Int32) return SimpleLinearSum(ins, 0); if (ins->isConstant()) return SimpleLinearSum(nullptr, ins->toConstant()->toInt32()); if (!ins->isAdd() && !ins->isSub()) return SimpleLinearSum(ins, 0); // Only allow math which are in the same space. MathSpace insSpace = ExtractMathSpace(ins); if (space == MathSpace::Unknown) space = insSpace; else if (space != insSpace) return SimpleLinearSum(ins, 0); MOZ_ASSERT(space == MathSpace::Modulo || space == MathSpace::Infinite); MDefinition* lhs = ins->getOperand(0); MDefinition* rhs = ins->getOperand(1); if (lhs->type() != MIRType::Int32 || rhs->type() != MIRType::Int32) return SimpleLinearSum(ins, 0); // Extract linear sums of each operand. SimpleLinearSum lsum = ExtractLinearSum(lhs, space); SimpleLinearSum rsum = ExtractLinearSum(rhs, space); // LinearSum only considers a single term operand, if both sides have // terms, then ignore extracted linear sums. if (lsum.term && rsum.term) return SimpleLinearSum(ins, 0); // Check if this is of the form <SUM> + n or n + <SUM>. if (ins->isAdd()) { int32_t constant; if (space == MathSpace::Modulo) constant = lsum.constant + rsum.constant; else if (!SafeAdd(lsum.constant, rsum.constant, &constant)) return SimpleLinearSum(ins, 0); return SimpleLinearSum(lsum.term ? lsum.term : rsum.term, constant); } MOZ_ASSERT(ins->isSub()); // Check if this is of the form <SUM> - n. if (lsum.term) { int32_t constant; if (space == MathSpace::Modulo) constant = lsum.constant - rsum.constant; else if (!SafeSub(lsum.constant, rsum.constant, &constant)) return SimpleLinearSum(ins, 0); return SimpleLinearSum(lsum.term, constant); } // Ignore any of the form n - <SUM>. return SimpleLinearSum(ins, 0); } // Extract a linear inequality holding when a boolean test goes in the // specified direction, of the form 'lhs + lhsN <= rhs' (or >=). bool jit::ExtractLinearInequality(MTest* test, BranchDirection direction, SimpleLinearSum* plhs, MDefinition** prhs, bool* plessEqual) { if (!test->getOperand(0)->isCompare()) return false; MCompare* compare = test->getOperand(0)->toCompare(); MDefinition* lhs = compare->getOperand(0); MDefinition* rhs = compare->getOperand(1); // TODO: optimize Compare_UInt32 if (!compare->isInt32Comparison()) return false; MOZ_ASSERT(lhs->type() == MIRType::Int32); MOZ_ASSERT(rhs->type() == MIRType::Int32); JSOp jsop = compare->jsop(); if (direction == FALSE_BRANCH) jsop = NegateCompareOp(jsop); SimpleLinearSum lsum = ExtractLinearSum(lhs); SimpleLinearSum rsum = ExtractLinearSum(rhs); if (!SafeSub(lsum.constant, rsum.constant, &lsum.constant)) return false; // Normalize operations to use <= or >=. switch (jsop) { case JSOP_LE: *plessEqual = true; break; case JSOP_LT: /* x < y ==> x + 1 <= y */ if (!SafeAdd(lsum.constant, 1, &lsum.constant)) return false; *plessEqual = true; break; case JSOP_GE: *plessEqual = false; break; case JSOP_GT: /* x > y ==> x - 1 >= y */ if (!SafeSub(lsum.constant, 1, &lsum.constant)) return false; *plessEqual = false; break; default: return false; } *plhs = lsum; *prhs = rsum.term; return true; } static bool TryEliminateBoundsCheck(BoundsCheckMap& checks, size_t blockIndex, MBoundsCheck* dominated, bool* eliminated) { MOZ_ASSERT(!*eliminated); // Replace all uses of the bounds check with the actual index. // This is (a) necessary, because we can coalesce two different // bounds checks and would otherwise use the wrong index and // (b) helps register allocation. Note that this is safe since // no other pass after bounds check elimination moves instructions. dominated->replaceAllUsesWith(dominated->index()); if (!dominated->isMovable()) return true; if (!dominated->fallible()) return true; MBoundsCheck* dominating = FindDominatingBoundsCheck(checks, dominated, blockIndex); if (!dominating) return false; if (dominating == dominated) { // We didn't find a dominating bounds check. return true; } // We found two bounds checks with the same hash number, but we still have // to make sure the lengths and index terms are equal. if (dominating->length() != dominated->length()) return true; SimpleLinearSum sumA = ExtractLinearSum(dominating->index()); SimpleLinearSum sumB = ExtractLinearSum(dominated->index()); // Both terms should be nullptr or the same definition. if (sumA.term != sumB.term) return true; // This bounds check is redundant. *eliminated = true; // Normalize the ranges according to the constant offsets in the two indexes. int32_t minimumA, maximumA, minimumB, maximumB; if (!SafeAdd(sumA.constant, dominating->minimum(), &minimumA) || !SafeAdd(sumA.constant, dominating->maximum(), &maximumA) || !SafeAdd(sumB.constant, dominated->minimum(), &minimumB) || !SafeAdd(sumB.constant, dominated->maximum(), &maximumB)) { return false; } // Update the dominating check to cover both ranges, denormalizing the // result per the constant offset in the index. int32_t newMinimum, newMaximum; if (!SafeSub(Min(minimumA, minimumB), sumA.constant, &newMinimum) || !SafeSub(Max(maximumA, maximumB), sumA.constant, &newMaximum)) { return false; } dominating->setMinimum(newMinimum); dominating->setMaximum(newMaximum); return true; } static void TryEliminateTypeBarrierFromTest(MTypeBarrier* barrier, bool filtersNull, bool filtersUndefined, MTest* test, BranchDirection direction, bool* eliminated) { MOZ_ASSERT(filtersNull || filtersUndefined); // Watch for code patterns similar to 'if (x.f) { ... = x.f }'. If x.f // is either an object or null/undefined, there will be a type barrier on // the latter read as the null/undefined value is never realized there. // The type barrier can be eliminated, however, by looking at tests // performed on the result of the first operation that filter out all // types that have been seen in the first access but not the second. // A test 'if (x.f)' filters both null and undefined. // Disregard the possible unbox added before the Typebarrier for checking. MDefinition* input = barrier->input(); MUnbox* inputUnbox = nullptr; if (input->isUnbox() && input->toUnbox()->mode() != MUnbox::Fallible) { inputUnbox = input->toUnbox(); input = inputUnbox->input(); } MDefinition* subject = nullptr; bool removeUndefined; bool removeNull; test->filtersUndefinedOrNull(direction == TRUE_BRANCH, &subject, &removeUndefined, &removeNull); // The Test doesn't filter undefined nor null. if (!subject) return; // Make sure the subject equals the input to the TypeBarrier. if (subject != input) return; // When the TypeBarrier filters undefined, the test must at least also do, // this, before the TypeBarrier can get removed. if (!removeUndefined && filtersUndefined) return; // When the TypeBarrier filters null, the test must at least also do, // this, before the TypeBarrier can get removed. if (!removeNull && filtersNull) return; // Eliminate the TypeBarrier. The possible TypeBarrier unboxing is kept, // but made infallible. *eliminated = true; if (inputUnbox) inputUnbox->makeInfallible(); barrier->replaceAllUsesWith(barrier->input()); } static bool TryEliminateTypeBarrier(MTypeBarrier* barrier, bool* eliminated) { MOZ_ASSERT(!*eliminated); const TemporaryTypeSet* barrierTypes = barrier->resultTypeSet(); const TemporaryTypeSet* inputTypes = barrier->input()->resultTypeSet(); // Disregard the possible unbox added before the Typebarrier. if (barrier->input()->isUnbox() && barrier->input()->toUnbox()->mode() != MUnbox::Fallible) inputTypes = barrier->input()->toUnbox()->input()->resultTypeSet(); if (!barrierTypes || !inputTypes) return true; bool filtersNull = barrierTypes->filtersType(inputTypes, TypeSet::NullType()); bool filtersUndefined = barrierTypes->filtersType(inputTypes, TypeSet::UndefinedType()); if (!filtersNull && !filtersUndefined) return true; MBasicBlock* block = barrier->block(); while (true) { BranchDirection direction; MTest* test = block->immediateDominatorBranch(&direction); if (test) { TryEliminateTypeBarrierFromTest(barrier, filtersNull, filtersUndefined, test, direction, eliminated); } MBasicBlock* previous = block->immediateDominator(); if (previous == block) break; block = previous; } return true; } static bool TryOptimizeLoadObjectOrNull(MDefinition* def, MDefinitionVector* peliminateList) { if (def->type() != MIRType::Value) return true; // Check if this definition can only produce object or null values. TemporaryTypeSet* types = def->resultTypeSet(); if (!types) return true; if (types->baseFlags() & ~(TYPE_FLAG_NULL | TYPE_FLAG_ANYOBJECT)) return true; MDefinitionVector eliminateList(def->block()->graph().alloc()); for (MUseDefIterator iter(def); iter; ++iter) { MDefinition* ndef = iter.def(); switch (ndef->op()) { case MDefinition::Op_Compare: if (ndef->toCompare()->compareType() != MCompare::Compare_Null) return true; break; case MDefinition::Op_Test: break; case MDefinition::Op_PostWriteBarrier: break; case MDefinition::Op_StoreFixedSlot: break; case MDefinition::Op_StoreSlot: break; case MDefinition::Op_ToObjectOrNull: if (!eliminateList.append(ndef->toToObjectOrNull())) return false; break; case MDefinition::Op_Unbox: if (ndef->type() != MIRType::Object) return true; break; case MDefinition::Op_TypeBarrier: // For now, only handle type barriers which are not consumed // anywhere and only test that the value is null. if (ndef->hasUses() || ndef->resultTypeSet()->getKnownMIRType() != MIRType::Null) return true; break; default: return true; } } // On punboxing systems we are better off leaving the value boxed if it // is only stored back to the heap. #ifdef JS_PUNBOX64 bool foundUse = false; for (MUseDefIterator iter(def); iter; ++iter) { MDefinition* ndef = iter.def(); if (!ndef->isStoreFixedSlot() && !ndef->isStoreSlot()) { foundUse = true; break; } } if (!foundUse) return true; #endif // JS_PUNBOX64 def->setResultType(MIRType::ObjectOrNull); // Fixup the result type of MTypeBarrier uses. for (MUseDefIterator iter(def); iter; ++iter) { MDefinition* ndef = iter.def(); if (ndef->isTypeBarrier()) ndef->setResultType(MIRType::ObjectOrNull); } // Eliminate MToObjectOrNull instruction uses. for (size_t i = 0; i < eliminateList.length(); i++) { MDefinition* ndef = eliminateList[i]; ndef->replaceAllUsesWith(def); if (!peliminateList->append(ndef)) return false; } return true; } static inline MDefinition* PassthroughOperand(MDefinition* def) { if (def->isConvertElementsToDoubles()) return def->toConvertElementsToDoubles()->elements(); if (def->isMaybeCopyElementsForWrite()) return def->toMaybeCopyElementsForWrite()->object(); if (def->isConvertUnboxedObjectToNative()) return def->toConvertUnboxedObjectToNative()->object(); return nullptr; } // Eliminate checks which are redundant given each other or other instructions. // // A type barrier is considered redundant if all missing types have been tested // for by earlier control instructions. // // A bounds check is considered redundant if it's dominated by another bounds // check with the same length and the indexes differ by only a constant amount. // In this case we eliminate the redundant bounds check and update the other one // to cover the ranges of both checks. // // Bounds checks are added to a hash map and since the hash function ignores // differences in constant offset, this offers a fast way to find redundant // checks. bool jit::EliminateRedundantChecks(MIRGraph& graph) { BoundsCheckMap checks(graph.alloc()); if (!checks.init()) return false; // Stack for pre-order CFG traversal. Vector<MBasicBlock*, 1, JitAllocPolicy> worklist(graph.alloc()); // The index of the current block in the CFG traversal. size_t index = 0; // Add all self-dominating blocks to the worklist. // This includes all roots. Order does not matter. for (MBasicBlockIterator i(graph.begin()); i != graph.end(); i++) { MBasicBlock* block = *i; if (block->immediateDominator() == block) { if (!worklist.append(block)) return false; } } MDefinitionVector eliminateList(graph.alloc()); // Starting from each self-dominating block, traverse the CFG in pre-order. while (!worklist.empty()) { MBasicBlock* block = worklist.popCopy(); // Add all immediate dominators to the front of the worklist. if (!worklist.append(block->immediatelyDominatedBlocksBegin(), block->immediatelyDominatedBlocksEnd())) { return false; } for (MDefinitionIterator iter(block); iter; ) { MDefinition* def = *iter++; bool eliminated = false; switch (def->op()) { case MDefinition::Op_BoundsCheck: if (!TryEliminateBoundsCheck(checks, index, def->toBoundsCheck(), &eliminated)) return false; break; case MDefinition::Op_TypeBarrier: if (!TryEliminateTypeBarrier(def->toTypeBarrier(), &eliminated)) return false; break; case MDefinition::Op_LoadFixedSlot: case MDefinition::Op_LoadSlot: case MDefinition::Op_LoadUnboxedObjectOrNull: if (!TryOptimizeLoadObjectOrNull(def, &eliminateList)) return false; break; default: // Now that code motion passes have finished, replace // instructions which pass through one of their operands // (and perform additional checks) with that operand. if (MDefinition* passthrough = PassthroughOperand(def)) def->replaceAllUsesWith(passthrough); break; } if (eliminated) block->discardDef(def); } index++; } MOZ_ASSERT(index == graph.numBlocks()); for (size_t i = 0; i < eliminateList.length(); i++) { MDefinition* def = eliminateList[i]; def->block()->discardDef(def); } return true; } static bool NeedsKeepAlive(MInstruction* slotsOrElements, MInstruction* use) { MOZ_ASSERT(slotsOrElements->type() == MIRType::Elements || slotsOrElements->type() == MIRType::Slots); if (slotsOrElements->block() != use->block()) return true; MBasicBlock* block = use->block(); MInstructionIterator iter(block->begin(slotsOrElements)); MOZ_ASSERT(*iter == slotsOrElements); ++iter; while (true) { if (*iter == use) return false; switch (iter->op()) { case MDefinition::Op_Nop: case MDefinition::Op_Constant: case MDefinition::Op_KeepAliveObject: case MDefinition::Op_Unbox: case MDefinition::Op_LoadSlot: case MDefinition::Op_StoreSlot: case MDefinition::Op_LoadFixedSlot: case MDefinition::Op_StoreFixedSlot: case MDefinition::Op_LoadElement: case MDefinition::Op_StoreElement: case MDefinition::Op_InitializedLength: case MDefinition::Op_ArrayLength: case MDefinition::Op_BoundsCheck: iter++; break; default: return true; } } MOZ_CRASH("Unreachable"); } bool jit::AddKeepAliveInstructions(MIRGraph& graph) { for (MBasicBlockIterator i(graph.begin()); i != graph.end(); i++) { MBasicBlock* block = *i; for (MInstructionIterator insIter(block->begin()); insIter != block->end(); insIter++) { MInstruction* ins = *insIter; if (ins->type() != MIRType::Elements && ins->type() != MIRType::Slots) continue; MDefinition* ownerObject; switch (ins->op()) { case MDefinition::Op_ConstantElements: continue; case MDefinition::Op_ConvertElementsToDoubles: // EliminateRedundantChecks should have replaced all uses. MOZ_ASSERT(!ins->hasUses()); continue; case MDefinition::Op_Elements: case MDefinition::Op_TypedArrayElements: case MDefinition::Op_TypedObjectElements: MOZ_ASSERT(ins->numOperands() == 1); ownerObject = ins->getOperand(0); break; case MDefinition::Op_Slots: ownerObject = ins->toSlots()->object(); break; default: MOZ_CRASH("Unexpected op"); } MOZ_ASSERT(ownerObject->type() == MIRType::Object); if (ownerObject->isConstant()) { // Constants are kept alive by other pointers, for instance // ImmGCPtr in JIT code. continue; } for (MUseDefIterator uses(ins); uses; uses++) { MInstruction* use = uses.def()->toInstruction(); if (use->isStoreElementHole()) { // StoreElementHole has an explicit object operand. If GVN // is disabled, we can get different unbox instructions with // the same object as input, so we check for that case. MOZ_ASSERT_IF(!use->toStoreElementHole()->object()->isUnbox() && !ownerObject->isUnbox(), use->toStoreElementHole()->object() == ownerObject); continue; } if (use->isFallibleStoreElement()) { // See StoreElementHole case above. MOZ_ASSERT_IF(!use->toFallibleStoreElement()->object()->isUnbox() && !ownerObject->isUnbox(), use->toFallibleStoreElement()->object() == ownerObject); continue; } if (use->isInArray()) { // See StoreElementHole case above. MOZ_ASSERT_IF(!use->toInArray()->object()->isUnbox() && !ownerObject->isUnbox(), use->toInArray()->object() == ownerObject); continue; } if (!NeedsKeepAlive(ins, use)) continue; if (!graph.alloc().ensureBallast()) return false; MKeepAliveObject* keepAlive = MKeepAliveObject::New(graph.alloc(), ownerObject); use->block()->insertAfter(use, keepAlive); } } } return true; } bool LinearSum::multiply(int32_t scale) { for (size_t i = 0; i < terms_.length(); i++) { if (!SafeMul(scale, terms_[i].scale, &terms_[i].scale)) return false; } return SafeMul(scale, constant_, &constant_); } bool LinearSum::divide(uint32_t scale) { MOZ_ASSERT(scale > 0); for (size_t i = 0; i < terms_.length(); i++) { if (terms_[i].scale % scale != 0) return false; } if (constant_ % scale != 0) return false; for (size_t i = 0; i < terms_.length(); i++) terms_[i].scale /= scale; constant_ /= scale; return true; } bool LinearSum::add(const LinearSum& other, int32_t scale /* = 1 */) { for (size_t i = 0; i < other.terms_.length(); i++) { int32_t newScale = scale; if (!SafeMul(scale, other.terms_[i].scale, &newScale)) return false; if (!add(other.terms_[i].term, newScale)) return false; } int32_t newConstant = scale; if (!SafeMul(scale, other.constant_, &newConstant)) return false; return add(newConstant); } bool LinearSum::add(SimpleLinearSum other, int32_t scale) { if (other.term && !add(other.term, scale)) return false; int32_t constant; if (!SafeMul(other.constant, scale, &constant)) return false; return add(constant); } bool LinearSum::add(MDefinition* term, int32_t scale) { MOZ_ASSERT(term); if (scale == 0) return true; if (MConstant* termConst = term->maybeConstantValue()) { int32_t constant = termConst->toInt32(); if (!SafeMul(constant, scale, &constant)) return false; return add(constant); } for (size_t i = 0; i < terms_.length(); i++) { if (term == terms_[i].term) { if (!SafeAdd(scale, terms_[i].scale, &terms_[i].scale)) return false; if (terms_[i].scale == 0) { terms_[i] = terms_.back(); terms_.popBack(); } return true; } } AutoEnterOOMUnsafeRegion oomUnsafe; if (!terms_.append(LinearTerm(term, scale))) oomUnsafe.crash("LinearSum::add"); return true; } bool LinearSum::add(int32_t constant) { return SafeAdd(constant, constant_, &constant_); } void LinearSum::dump(GenericPrinter& out) const { for (size_t i = 0; i < terms_.length(); i++) { int32_t scale = terms_[i].scale; int32_t id = terms_[i].term->id(); MOZ_ASSERT(scale); if (scale > 0) { if (i) out.printf("+"); if (scale == 1) out.printf("#%d", id); else out.printf("%d*#%d", scale, id); } else if (scale == -1) { out.printf("-#%d", id); } else { out.printf("%d*#%d", scale, id); } } if (constant_ > 0) out.printf("+%d", constant_); else if (constant_ < 0) out.printf("%d", constant_); } void LinearSum::dump() const { Fprinter out(stderr); dump(out); out.finish(); } MDefinition* jit::ConvertLinearSum(TempAllocator& alloc, MBasicBlock* block, const LinearSum& sum, bool convertConstant) { MDefinition* def = nullptr; for (size_t i = 0; i < sum.numTerms(); i++) { LinearTerm term = sum.term(i); MOZ_ASSERT(!term.term->isConstant()); if (term.scale == 1) { if (def) { def = MAdd::New(alloc, def, term.term); def->toAdd()->setInt32Specialization(); block->insertAtEnd(def->toInstruction()); def->computeRange(alloc); } else { def = term.term; } } else if (term.scale == -1) { if (!def) { def = MConstant::New(alloc, Int32Value(0)); block->insertAtEnd(def->toInstruction()); def->computeRange(alloc); } def = MSub::New(alloc, def, term.term); def->toSub()->setInt32Specialization(); block->insertAtEnd(def->toInstruction()); def->computeRange(alloc); } else { MOZ_ASSERT(term.scale != 0); MConstant* factor = MConstant::New(alloc, Int32Value(term.scale)); block->insertAtEnd(factor); MMul* mul = MMul::New(alloc, term.term, factor); mul->setInt32Specialization(); block->insertAtEnd(mul); mul->computeRange(alloc); if (def) { def = MAdd::New(alloc, def, mul); def->toAdd()->setInt32Specialization(); block->insertAtEnd(def->toInstruction()); def->computeRange(alloc); } else { def = mul; } } } if (convertConstant && sum.constant()) { MConstant* constant = MConstant::New(alloc, Int32Value(sum.constant())); block->insertAtEnd(constant); constant->computeRange(alloc); if (def) { def = MAdd::New(alloc, def, constant); def->toAdd()->setInt32Specialization(); block->insertAtEnd(def->toInstruction()); def->computeRange(alloc); } else { def = constant; } } if (!def) { def = MConstant::New(alloc, Int32Value(0)); block->insertAtEnd(def->toInstruction()); def->computeRange(alloc); } return def; } MCompare* jit::ConvertLinearInequality(TempAllocator& alloc, MBasicBlock* block, const LinearSum& sum) { LinearSum lhs(sum); // Look for a term with a -1 scale which we can use for the rhs. MDefinition* rhsDef = nullptr; for (size_t i = 0; i < lhs.numTerms(); i++) { if (lhs.term(i).scale == -1) { AutoEnterOOMUnsafeRegion oomUnsafe; rhsDef = lhs.term(i).term; if (!lhs.add(rhsDef, 1)) oomUnsafe.crash("ConvertLinearInequality"); break; } } MDefinition* lhsDef = nullptr; JSOp op = JSOP_GE; do { if (!lhs.numTerms()) { lhsDef = MConstant::New(alloc, Int32Value(lhs.constant())); block->insertAtEnd(lhsDef->toInstruction()); lhsDef->computeRange(alloc); break; } lhsDef = ConvertLinearSum(alloc, block, lhs); if (lhs.constant() == 0) break; if (lhs.constant() == -1) { op = JSOP_GT; break; } if (!rhsDef) { int32_t constant = lhs.constant(); if (SafeMul(constant, -1, &constant)) { rhsDef = MConstant::New(alloc, Int32Value(constant)); block->insertAtEnd(rhsDef->toInstruction()); rhsDef->computeRange(alloc); break; } } MDefinition* constant = MConstant::New(alloc, Int32Value(lhs.constant())); block->insertAtEnd(constant->toInstruction()); constant->computeRange(alloc); lhsDef = MAdd::New(alloc, lhsDef, constant); lhsDef->toAdd()->setInt32Specialization(); block->insertAtEnd(lhsDef->toInstruction()); lhsDef->computeRange(alloc); } while (false); if (!rhsDef) { rhsDef = MConstant::New(alloc, Int32Value(0)); block->insertAtEnd(rhsDef->toInstruction()); rhsDef->computeRange(alloc); } MCompare* compare = MCompare::New(alloc, lhsDef, rhsDef, op); block->insertAtEnd(compare); compare->setCompareType(MCompare::Compare_Int32); return compare; } static bool AnalyzePoppedThis(JSContext* cx, ObjectGroup* group, MDefinition* thisValue, MInstruction* ins, bool definitelyExecuted, HandlePlainObject baseobj, Vector<TypeNewScript::Initializer>* initializerList, Vector<PropertyName*>* accessedProperties, bool* phandled) { // Determine the effect that a use of the |this| value when calling |new| // on a script has on the properties definitely held by the new object. if (ins->isCallSetProperty()) { MCallSetProperty* setprop = ins->toCallSetProperty(); if (setprop->object() != thisValue) return true; if (setprop->name() == cx->names().prototype || setprop->name() == cx->names().proto || setprop->name() == cx->names().constructor) { return true; } // Ignore assignments to properties that were already written to. if (baseobj->lookup(cx, NameToId(setprop->name()))) { *phandled = true; return true; } // Don't add definite properties for properties that were already // read in the constructor. for (size_t i = 0; i < accessedProperties->length(); i++) { if ((*accessedProperties)[i] == setprop->name()) return true; } // Assignments to new properties must always execute. if (!definitelyExecuted) return true; RootedId id(cx, NameToId(setprop->name())); if (!AddClearDefiniteGetterSetterForPrototypeChain(cx, group, id)) { // The prototype chain already contains a getter/setter for this // property, or type information is too imprecise. return true; } // Add the property to the object, being careful not to update type information. DebugOnly<unsigned> slotSpan = baseobj->slotSpan(); MOZ_ASSERT(!baseobj->containsPure(id)); if (!baseobj->addDataProperty(cx, id, baseobj->slotSpan(), JSPROP_ENUMERATE)) return false; MOZ_ASSERT(baseobj->slotSpan() != slotSpan); MOZ_ASSERT(!baseobj->inDictionaryMode()); Vector<MResumePoint*> callerResumePoints(cx); for (MResumePoint* rp = ins->block()->callerResumePoint(); rp; rp = rp->block()->callerResumePoint()) { if (!callerResumePoints.append(rp)) return false; } for (int i = callerResumePoints.length() - 1; i >= 0; i--) { MResumePoint* rp = callerResumePoints[i]; JSScript* script = rp->block()->info().script(); TypeNewScript::Initializer entry(TypeNewScript::Initializer::SETPROP_FRAME, script->pcToOffset(rp->pc())); if (!initializerList->append(entry)) return false; } JSScript* script = ins->block()->info().script(); TypeNewScript::Initializer entry(TypeNewScript::Initializer::SETPROP, script->pcToOffset(setprop->resumePoint()->pc())); if (!initializerList->append(entry)) return false; *phandled = true; return true; } if (ins->isCallGetProperty()) { MCallGetProperty* get = ins->toCallGetProperty(); /* * Properties can be read from the 'this' object if the following hold: * * - The read is not on a getter along the prototype chain, which * could cause 'this' to escape. * * - The accessed property is either already a definite property or * is not later added as one. Since the definite properties are * added to the object at the point of its creation, reading a * definite property before it is assigned could incorrectly hit. */ RootedId id(cx, NameToId(get->name())); if (!baseobj->lookup(cx, id) && !accessedProperties->append(get->name())) return false; if (!AddClearDefiniteGetterSetterForPrototypeChain(cx, group, id)) { // The |this| value can escape if any property reads it does go // through a getter. return true; } *phandled = true; return true; } if (ins->isPostWriteBarrier()) { *phandled = true; return true; } return true; } static int CmpInstructions(const void* a, const void* b) { return (*static_cast<MInstruction * const*>(a))->id() - (*static_cast<MInstruction * const*>(b))->id(); } bool jit::AnalyzeNewScriptDefiniteProperties(JSContext* cx, JSFunction* fun, ObjectGroup* group, HandlePlainObject baseobj, Vector<TypeNewScript::Initializer>* initializerList) { MOZ_ASSERT(cx->zone()->types.activeAnalysis); // When invoking 'new' on the specified script, try to find some properties // which will definitely be added to the created object before it has a // chance to escape and be accessed elsewhere. RootedScript script(cx, fun->getOrCreateScript(cx)); if (!script) return false; if (!jit::IsIonEnabled(cx) || !jit::IsBaselineEnabled(cx) || !script->canBaselineCompile()) return true; static const uint32_t MAX_SCRIPT_SIZE = 2000; if (script->length() > MAX_SCRIPT_SIZE) return true; TraceLoggerThread* logger = TraceLoggerForMainThread(cx->runtime()); TraceLoggerEvent event(logger, TraceLogger_AnnotateScripts, script); AutoTraceLog logScript(logger, event); AutoTraceLog logCompile(logger, TraceLogger_IonAnalysis); Vector<PropertyName*> accessedProperties(cx); LifoAlloc alloc(TempAllocator::PreferredLifoChunkSize); TempAllocator temp(&alloc); JitContext jctx(cx, &temp); if (!jit::CanLikelyAllocateMoreExecutableMemory()) return true; if (!cx->compartment()->ensureJitCompartmentExists(cx)) return false; if (!script->hasBaselineScript()) { MethodStatus status = BaselineCompile(cx, script); if (status == Method_Error) return false; if (status != Method_Compiled) return true; } TypeScript::SetThis(cx, script, TypeSet::ObjectType(group)); MIRGraph graph(&temp); InlineScriptTree* inlineScriptTree = InlineScriptTree::New(&temp, nullptr, nullptr, script); if (!inlineScriptTree) return false; CompileInfo info(script, fun, /* osrPc = */ nullptr, Analysis_DefiniteProperties, script->needsArgsObj(), inlineScriptTree); const OptimizationInfo* optimizationInfo = IonOptimizations.get(OptimizationLevel::Normal); CompilerConstraintList* constraints = NewCompilerConstraintList(temp); if (!constraints) { ReportOutOfMemory(cx); return false; } BaselineInspector inspector(script); const JitCompileOptions options(cx); IonBuilder builder(cx, CompileCompartment::get(cx->compartment()), options, &temp, &graph, constraints, &inspector, &info, optimizationInfo, /* baselineFrame = */ nullptr); if (!builder.build()) { if (cx->isThrowingOverRecursed() || cx->isThrowingOutOfMemory() || builder.abortReason() == AbortReason_Alloc) { return false; } MOZ_ASSERT(!cx->isExceptionPending()); return true; } FinishDefinitePropertiesAnalysis(cx, constraints); if (!SplitCriticalEdges(graph)) { ReportOutOfMemory(cx); return false; } RenumberBlocks(graph); if (!BuildDominatorTree(graph)) { ReportOutOfMemory(cx); return false; } if (!EliminatePhis(&builder, graph, AggressiveObservability)) { ReportOutOfMemory(cx); return false; } MDefinition* thisValue = graph.entryBlock()->getSlot(info.thisSlot()); // Get a list of instructions using the |this| value in the order they // appear in the graph. Vector<MInstruction*> instructions(cx); for (MUseDefIterator uses(thisValue); uses; uses++) { MDefinition* use = uses.def(); // Don't track |this| through assignments to phis. if (!use->isInstruction()) return true; if (!instructions.append(use->toInstruction())) return false; } // Sort the instructions to visit in increasing order. qsort(instructions.begin(), instructions.length(), sizeof(MInstruction*), CmpInstructions); // Find all exit blocks in the graph. Vector<MBasicBlock*> exitBlocks(cx); for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) { if (!block->numSuccessors() && !exitBlocks.append(*block)) return false; } // id of the last block which added a new property. size_t lastAddedBlock = 0; for (size_t i = 0; i < instructions.length(); i++) { MInstruction* ins = instructions[i]; // Track whether the use of |this| is in unconditional code, i.e. // the block dominates all graph exits. bool definitelyExecuted = true; for (size_t i = 0; i < exitBlocks.length(); i++) { for (MBasicBlock* exit = exitBlocks[i]; exit != ins->block(); exit = exit->immediateDominator()) { if (exit == exit->immediateDominator()) { definitelyExecuted = false; break; } } } // Also check to see if the instruction is inside a loop body. Even if // an access will always execute in the script, if it executes multiple // times then we can get confused when rolling back objects while // clearing the new script information. if (ins->block()->loopDepth() != 0) definitelyExecuted = false; bool handled = false; size_t slotSpan = baseobj->slotSpan(); if (!AnalyzePoppedThis(cx, group, thisValue, ins, definitelyExecuted, baseobj, initializerList, &accessedProperties, &handled)) { return false; } if (!handled) break; if (slotSpan != baseobj->slotSpan()) { MOZ_ASSERT(ins->block()->id() >= lastAddedBlock); lastAddedBlock = ins->block()->id(); } } if (baseobj->slotSpan() != 0) { // We found some definite properties, but their correctness is still // contingent on the correct frames being inlined. Add constraints to // invalidate the definite properties if additional functions could be // called at the inline frame sites. Vector<MBasicBlock*> exitBlocks(cx); for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) { // Inlining decisions made after the last new property was added to // the object don't need to be frozen. if (block->id() > lastAddedBlock) break; if (MResumePoint* rp = block->callerResumePoint()) { if (block->numPredecessors() == 1 && block->getPredecessor(0) == rp->block()) { JSScript* script = rp->block()->info().script(); if (!AddClearDefiniteFunctionUsesInScript(cx, group, script, block->info().script())) return false; } } } } return true; } static bool ArgumentsUseCanBeLazy(JSContext* cx, JSScript* script, MInstruction* ins, size_t index, bool* argumentsContentsObserved) { // We can read the frame's arguments directly for f.apply(x, arguments). if (ins->isCall()) { if (*ins->toCall()->resumePoint()->pc() == JSOP_FUNAPPLY && ins->toCall()->numActualArgs() == 2 && index == MCall::IndexOfArgument(1)) { *argumentsContentsObserved = true; return true; } } // arguments[i] can read fp->canonicalActualArg(i) directly. if (ins->isCallGetElement() && index == 0) { *argumentsContentsObserved = true; return true; } // MGetArgumentsObjectArg needs to be considered as a use that allows laziness. if (ins->isGetArgumentsObjectArg() && index == 0) return true; // arguments.length length can read fp->numActualArgs() directly. // arguments.callee can read fp->callee() directly if the arguments object // is mapped. if (ins->isCallGetProperty() && index == 0 && (ins->toCallGetProperty()->name() == cx->names().length || (script->hasMappedArgsObj() && ins->toCallGetProperty()->name() == cx->names().callee))) { return true; } return false; } bool jit::AnalyzeArgumentsUsage(JSContext* cx, JSScript* scriptArg) { RootedScript script(cx, scriptArg); AutoEnterAnalysis enter(cx); MOZ_ASSERT(!script->analyzedArgsUsage()); // Treat the script as needing an arguments object until we determine it // does not need one. This both allows us to easily see where the arguments // object can escape through assignments to the function's named arguments, // and also simplifies handling of early returns. script->setNeedsArgsObj(true); // Always construct arguments objects when in debug mode, for generator // scripts (generators can be suspended when speculation fails) or when // direct eval is present. // // FIXME: Don't build arguments for ES6 generator expressions. if (scriptArg->isDebuggee() || script->isGenerator() || script->bindingsAccessedDynamically()) return true; if (!jit::IsIonEnabled(cx)) return true; static const uint32_t MAX_SCRIPT_SIZE = 10000; if (script->length() > MAX_SCRIPT_SIZE) return true; if (!script->ensureHasTypes(cx)) return false; TraceLoggerThread* logger = TraceLoggerForMainThread(cx->runtime()); TraceLoggerEvent event(logger, TraceLogger_AnnotateScripts, script); AutoTraceLog logScript(logger, event); AutoTraceLog logCompile(logger, TraceLogger_IonAnalysis); LifoAlloc alloc(TempAllocator::PreferredLifoChunkSize); TempAllocator temp(&alloc); JitContext jctx(cx, &temp); if (!jit::CanLikelyAllocateMoreExecutableMemory()) return true; if (!cx->compartment()->ensureJitCompartmentExists(cx)) return false; MIRGraph graph(&temp); InlineScriptTree* inlineScriptTree = InlineScriptTree::New(&temp, nullptr, nullptr, script); if (!inlineScriptTree) { ReportOutOfMemory(cx); return false; } CompileInfo info(script, script->functionNonDelazifying(), /* osrPc = */ nullptr, Analysis_ArgumentsUsage, /* needsArgsObj = */ true, inlineScriptTree); const OptimizationInfo* optimizationInfo = IonOptimizations.get(OptimizationLevel::Normal); CompilerConstraintList* constraints = NewCompilerConstraintList(temp); if (!constraints) { ReportOutOfMemory(cx); return false; } BaselineInspector inspector(script); const JitCompileOptions options(cx); IonBuilder builder(nullptr, CompileCompartment::get(cx->compartment()), options, &temp, &graph, constraints, &inspector, &info, optimizationInfo, /* baselineFrame = */ nullptr); if (!builder.build()) { if (cx->isThrowingOverRecursed() || builder.abortReason() == AbortReason_Alloc) return false; MOZ_ASSERT(!cx->isExceptionPending()); return true; } if (!SplitCriticalEdges(graph)) { ReportOutOfMemory(cx); return false; } RenumberBlocks(graph); if (!BuildDominatorTree(graph)) { ReportOutOfMemory(cx); return false; } if (!EliminatePhis(&builder, graph, AggressiveObservability)) { ReportOutOfMemory(cx); return false; } MDefinition* argumentsValue = graph.entryBlock()->getSlot(info.argsObjSlot()); bool argumentsContentsObserved = false; for (MUseDefIterator uses(argumentsValue); uses; uses++) { MDefinition* use = uses.def(); // Don't track |arguments| through assignments to phis. if (!use->isInstruction()) return true; if (!ArgumentsUseCanBeLazy(cx, script, use->toInstruction(), use->indexOf(uses.use()), &argumentsContentsObserved)) { return true; } } // If a script explicitly accesses the contents of 'arguments', and has // formals which may be stored as part of a call object, don't use lazy // arguments. The compiler can then assume that accesses through // arguments[i] will be on unaliased variables. if (script->funHasAnyAliasedFormal() && argumentsContentsObserved) return true; script->setNeedsArgsObj(false); return true; } // Mark all the blocks that are in the loop with the given header. // Returns the number of blocks marked. Set *canOsr to true if the loop is // reachable from both the normal entry and the OSR entry. size_t jit::MarkLoopBlocks(MIRGraph& graph, MBasicBlock* header, bool* canOsr) { #ifdef DEBUG for (ReversePostorderIterator i = graph.rpoBegin(), e = graph.rpoEnd(); i != e; ++i) MOZ_ASSERT(!i->isMarked(), "Some blocks already marked"); #endif MBasicBlock* osrBlock = graph.osrBlock(); *canOsr = false; // The blocks are in RPO; start at the loop backedge, which marks the bottom // of the loop, and walk up until we get to the header. Loops may be // discontiguous, so we trace predecessors to determine which blocks are // actually part of the loop. The backedge is always part of the loop, and // so are its predecessors, transitively, up to the loop header or an OSR // entry. MBasicBlock* backedge = header->backedge(); backedge->mark(); size_t numMarked = 1; for (PostorderIterator i = graph.poBegin(backedge); ; ++i) { MOZ_ASSERT(i != graph.poEnd(), "Reached the end of the graph while searching for the loop header"); MBasicBlock* block = *i; // If we've reached the loop header, we're done. if (block == header) break; // A block not marked by the time we reach it is not in the loop. if (!block->isMarked()) continue; // This block is in the loop; trace to its predecessors. for (size_t p = 0, e = block->numPredecessors(); p != e; ++p) { MBasicBlock* pred = block->getPredecessor(p); if (pred->isMarked()) continue; // Blocks dominated by the OSR entry are not part of the loop // (unless they aren't reachable from the normal entry). if (osrBlock && pred != header && osrBlock->dominates(pred) && !osrBlock->dominates(header)) { *canOsr = true; continue; } MOZ_ASSERT(pred->id() >= header->id() && pred->id() <= backedge->id(), "Loop block not between loop header and loop backedge"); pred->mark(); ++numMarked; // A nested loop may not exit back to the enclosing loop at its // bottom. If we just marked its header, then the whole nested loop // is part of the enclosing loop. if (pred->isLoopHeader()) { MBasicBlock* innerBackedge = pred->backedge(); if (!innerBackedge->isMarked()) { // Mark its backedge so that we add all of its blocks to the // outer loop as we walk upwards. innerBackedge->mark(); ++numMarked; // If the nested loop is not contiguous, we may have already // passed its backedge. If this happens, back up. if (backedge->id() > block->id()) { i = graph.poBegin(innerBackedge); --i; } } } } } // If there's no path connecting the header to the backedge, then this isn't // actually a loop. This can happen when the code starts with a loop but GVN // folds some branches away. if (!header->isMarked()) { jit::UnmarkLoopBlocks(graph, header); return 0; } return numMarked; } // Unmark all the blocks that are in the loop with the given header. void jit::UnmarkLoopBlocks(MIRGraph& graph, MBasicBlock* header) { MBasicBlock* backedge = header->backedge(); for (ReversePostorderIterator i = graph.rpoBegin(header); ; ++i) { MOZ_ASSERT(i != graph.rpoEnd(), "Reached the end of the graph while searching for the backedge"); MBasicBlock* block = *i; if (block->isMarked()) { block->unmark(); if (block == backedge) break; } } #ifdef DEBUG for (ReversePostorderIterator i = graph.rpoBegin(), e = graph.rpoEnd(); i != e; ++i) MOZ_ASSERT(!i->isMarked(), "Not all blocks got unmarked"); #endif } // Reorder the blocks in the loop starting at the given header to be contiguous. static void MakeLoopContiguous(MIRGraph& graph, MBasicBlock* header, size_t numMarked) { MBasicBlock* backedge = header->backedge(); MOZ_ASSERT(header->isMarked(), "Loop header is not part of loop"); MOZ_ASSERT(backedge->isMarked(), "Loop backedge is not part of loop"); // If there are any blocks between the loop header and the loop backedge // that are not part of the loop, prepare to move them to the end. We keep // them in order, which preserves RPO. ReversePostorderIterator insertIter = graph.rpoBegin(backedge); insertIter++; MBasicBlock* insertPt = *insertIter; // Visit all the blocks from the loop header to the loop backedge. size_t headerId = header->id(); size_t inLoopId = headerId; size_t notInLoopId = inLoopId + numMarked; ReversePostorderIterator i = graph.rpoBegin(header); for (;;) { MBasicBlock* block = *i++; MOZ_ASSERT(block->id() >= header->id() && block->id() <= backedge->id(), "Loop backedge should be last block in loop"); if (block->isMarked()) { // This block is in the loop. block->unmark(); block->setId(inLoopId++); // If we've reached the loop backedge, we're done! if (block == backedge) break; } else { // This block is not in the loop. Move it to the end. graph.moveBlockBefore(insertPt, block); block->setId(notInLoopId++); } } MOZ_ASSERT(header->id() == headerId, "Loop header id changed"); MOZ_ASSERT(inLoopId == headerId + numMarked, "Wrong number of blocks kept in loop"); MOZ_ASSERT(notInLoopId == (insertIter != graph.rpoEnd() ? insertPt->id() : graph.numBlocks()), "Wrong number of blocks moved out of loop"); } // Reorder the blocks in the graph so that loops are contiguous. bool jit::MakeLoopsContiguous(MIRGraph& graph) { // Visit all loop headers (in any order). for (MBasicBlockIterator i(graph.begin()); i != graph.end(); i++) { MBasicBlock* header = *i; if (!header->isLoopHeader()) continue; // Mark all blocks that are actually part of the loop. bool canOsr; size_t numMarked = MarkLoopBlocks(graph, header, &canOsr); // If the loop isn't a loop, don't try to optimize it. if (numMarked == 0) continue; // If there's an OSR block entering the loop in the middle, it's tricky, // so don't try to handle it, for now. if (canOsr) { UnmarkLoopBlocks(graph, header); continue; } // Move all blocks between header and backedge that aren't marked to // the end of the loop, making the loop itself contiguous. MakeLoopContiguous(graph, header, numMarked); } return true; } MRootList::MRootList(TempAllocator& alloc) { #define INIT_VECTOR(name, _0, _1) \ roots_[JS::RootKind::name].emplace(alloc); JS_FOR_EACH_TRACEKIND(INIT_VECTOR) #undef INIT_VECTOR } template <typename T> static void TraceVector(JSTracer* trc, const MRootList::RootVector& vector, const char* name) { for (auto ptr : vector) { T ptrT = static_cast<T>(ptr); TraceManuallyBarrieredEdge(trc, &ptrT, name); MOZ_ASSERT(ptr == ptrT, "Shouldn't move without updating MIR pointers"); } } void MRootList::trace(JSTracer* trc) { #define TRACE_ROOTS(name, type, _) \ TraceVector<type*>(trc, *roots_[JS::RootKind::name], "mir-root-" #name); JS_FOR_EACH_TRACEKIND(TRACE_ROOTS) #undef TRACE_ROOTS } MOZ_MUST_USE bool jit::CreateMIRRootList(IonBuilder& builder) { MOZ_ASSERT(!builder.info().isAnalysis()); TempAllocator& alloc = builder.alloc(); MIRGraph& graph = builder.graph(); MRootList* roots = new(alloc.fallible()) MRootList(alloc); if (!roots) return false; JSScript* prevScript = nullptr; for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); block++) { JSScript* script = block->info().script(); if (script != prevScript) { if (!roots->append(script)) return false; prevScript = script; } for (MInstructionIterator iter(block->begin()), end(block->end()); iter != end; iter++) { if (!iter->appendRoots(*roots)) return false; } } builder.setRootList(*roots); return true; } static void DumpDefinition(GenericPrinter& out, MDefinition* def, size_t depth) { MDefinition::PrintOpcodeName(out, def->op()); if (depth == 0) return; for (size_t i = 0; i < def->numOperands(); i++) { out.printf(" ("); DumpDefinition(out, def->getOperand(i), depth - 1); out.printf(")"); } } void jit::DumpMIRExpressions(MIRGraph& graph) { if (!JitSpewEnabled(JitSpew_MIRExpressions)) return; size_t depth = 2; Fprinter& out = JitSpewPrinter(); for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); block++) { for (MInstructionIterator iter(block->begin()), end(block->end()); iter != end; iter++) { DumpDefinition(out, *iter, depth); out.printf("\n"); } } }