summaryrefslogtreecommitdiffstats
path: root/js/src/jit/IonAnalysis.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'js/src/jit/IonAnalysis.cpp')
-rw-r--r--js/src/jit/IonAnalysis.cpp4760
1 files changed, 4760 insertions, 0 deletions
diff --git a/js/src/jit/IonAnalysis.cpp b/js/src/jit/IonAnalysis.cpp
new file mode 100644
index 000000000..90303255d
--- /dev/null
+++ b/js/src/jit/IonAnalysis.cpp
@@ -0,0 +1,4760 @@
+/* -*- 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");
+ }
+ }
+}