Add m-esr52 at 52.6.0

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");
+        }
+    }
+}