Bug 820676: Remove unreachable basic blocks from the control flow graph in
authorNicholas D. Matsakis <nmatsakis@mozilla.com>
Thu, 13 Dec 2012 19:03:34 -0800
changeset 121598 0fb9ff76a1778ee3fbd57e9f3e6d8e0ce28d4587
parent 121597 4fb4bbc6b029987b32f0eb82d86c8b40ae7b7fa6
child 121599 f752f9d2563112b93940247dcec848035ae1fb78
push idunknown
push userunknown
push dateunknown
bugs820676
milestone20.0a1
Bug 820676: Remove unreachable basic blocks from the control flow graph in IonMonkey. r=jandem
js/src/Makefile.in
js/src/ion/Ion.cpp
js/src/ion/Ion.h
js/src/ion/IonAnalysis.cpp
js/src/ion/IonAnalysis.h
js/src/ion/MIR.cpp
js/src/ion/MIR.h
js/src/ion/MIRGraph.cpp
js/src/ion/MIRGraph.h
js/src/ion/UnreachableCodeElimination.cpp
js/src/ion/UnreachableCodeElimination.h
js/src/jit-test/tests/ion/eliminate-unreachable-1.js
js/src/jit-test/tests/ion/eliminate-unreachable-2.js
--- a/js/src/Makefile.in
+++ b/js/src/Makefile.in
@@ -305,16 +305,17 @@ CPPSRCS +=	MIR.cpp \
 		Safepoints.cpp \
 		StupidAllocator.cpp \
 		TypeOracle.cpp \
 		TypePolicy.cpp \
 		ValueNumbering.cpp \
 		RangeAnalysis.cpp \
 		VMFunctions.cpp \
 		AliasAnalysis.cpp \
+		UnreachableCodeElimination.cpp \
 		$(NULL)
 endif #ENABLE_ION
 ifeq (86, $(findstring 86,$(TARGET_CPU)))
 ifdef ENABLE_ION
 CPPSRCS +=	CodeGenerator-x86-shared.cpp
 CPPSRCS +=	IonFrames-x86-shared.cpp
 CPPSRCS +=	MoveEmitter-x86-shared.cpp
 CPPSRCS +=	Assembler-x86-shared.cpp
--- a/js/src/ion/Ion.cpp
+++ b/js/src/ion/Ion.cpp
@@ -17,16 +17,17 @@
 #include "EdgeCaseAnalysis.h"
 #include "RangeAnalysis.h"
 #include "LinearScan.h"
 #include "jscompartment.h"
 #include "jsworkers.h"
 #include "IonCompartment.h"
 #include "CodeGenerator.h"
 #include "StupidAllocator.h"
+#include "UnreachableCodeElimination.h"
 
 #if defined(JS_CPU_X86)
 # include "x86/Lowering-x86.h"
 #elif defined(JS_CPU_X64)
 # include "x64/Lowering-x64.h"
 #elif defined(JS_CPU_ARM)
 # include "arm/Lowering-arm.h"
 #endif
@@ -809,48 +810,49 @@ CompileBackEnd(MIRGenerator *mir)
     if (!BuildDominatorTree(graph))
         return NULL;
     // No spew: graph not changed.
 
     if (mir->shouldCancel("Dominator Tree"))
         return NULL;
 
     // This must occur before any code elimination.
-    if (!EliminatePhis(mir, graph))
+    if (!EliminatePhis(mir, graph, AggressiveObservability))
         return NULL;
     IonSpewPass("Eliminate phis");
     AssertGraphCoherency(graph);
 
     if (mir->shouldCancel("Eliminate phis"))
         return NULL;
 
     if (!BuildPhiReverseMapping(graph))
         return NULL;
+    AssertExtendedGraphCoherency(graph);
     // No spew: graph not changed.
 
     if (mir->shouldCancel("Phi reverse mapping"))
         return NULL;
 
     // This pass also removes copies.
     if (!ApplyTypeInformation(mir, graph))
         return NULL;
     IonSpewPass("Apply types");
-    AssertGraphCoherency(graph);
+    AssertExtendedGraphCoherency(graph);
 
     if (mir->shouldCancel("Apply types"))
         return NULL;
 
     // Alias analysis is required for LICM and GVN so that we don't move
     // loads across stores.
     if (js_IonOptions.licm || js_IonOptions.gvn) {
         AliasAnalysis analysis(mir, graph);
         if (!analysis.analyze())
             return NULL;
         IonSpewPass("Alias analysis");
-        AssertGraphCoherency(graph);
+        AssertExtendedGraphCoherency(graph);
 
         if (mir->shouldCancel("Alias analysis"))
             return NULL;
 
         // Eliminating dead resume point operands requires basic block
         // instructions to be numbered. Reuse the numbering computed during
         // alias analysis.
         if (!EliminateDeadResumePointOperands(mir, graph))
@@ -860,75 +862,86 @@ CompileBackEnd(MIRGenerator *mir)
             return NULL;
     }
 
     if (js_IonOptions.edgeCaseAnalysis) {
         EdgeCaseAnalysis edgeCaseAnalysis(mir, graph);
         if (!edgeCaseAnalysis.analyzeEarly())
             return NULL;
         IonSpewPass("Edge Case Analysis (Early)");
-        AssertGraphCoherency(graph);
+        AssertExtendedGraphCoherency(graph);
 
         if (mir->shouldCancel("Edge Case Analysis (Early)"))
             return NULL;
     }
 
     if (js_IonOptions.gvn) {
         ValueNumberer gvn(mir, graph, js_IonOptions.gvnIsOptimistic);
         if (!gvn.analyze())
             return NULL;
         IonSpewPass("GVN");
-        AssertGraphCoherency(graph);
+        AssertExtendedGraphCoherency(graph);
 
         if (mir->shouldCancel("GVN"))
             return NULL;
     }
 
+    if (js_IonOptions.uce) {
+        UnreachableCodeElimination uce(mir, graph);
+        if (!uce.analyze())
+            return NULL;
+        IonSpewPass("UCE");
+        AssertExtendedGraphCoherency(graph);
+    }
+
+    if (mir->shouldCancel("UCE"))
+        return NULL;
+
     if (js_IonOptions.licm) {
         LICM licm(mir, graph);
         if (!licm.analyze())
             return NULL;
         IonSpewPass("LICM");
-        AssertGraphCoherency(graph);
+        AssertExtendedGraphCoherency(graph);
 
         if (mir->shouldCancel("LICM"))
             return NULL;
     }
 
     if (js_IonOptions.rangeAnalysis) {
         RangeAnalysis r(graph);
         if (!r.addBetaNobes())
             return NULL;
         IonSpewPass("Beta");
-        AssertGraphCoherency(graph);
+        AssertExtendedGraphCoherency(graph);
 
         if (mir->shouldCancel("RA Beta"))
             return NULL;
 
         if (!r.analyze())
             return NULL;
         IonSpewPass("Range Analysis");
-        AssertGraphCoherency(graph);
+        AssertExtendedGraphCoherency(graph);
 
         if (mir->shouldCancel("Range Analysis"))
             return NULL;
 
         if (!r.removeBetaNobes())
             return NULL;
         IonSpewPass("De-Beta");
-        AssertGraphCoherency(graph);
+        AssertExtendedGraphCoherency(graph);
 
         if (mir->shouldCancel("RA De-Beta"))
             return NULL;
     }
 
     if (!EliminateDeadCode(mir, graph))
         return NULL;
     IonSpewPass("DCE");
-    AssertGraphCoherency(graph);
+    AssertExtendedGraphCoherency(graph);
 
     if (mir->shouldCancel("DCE"))
         return NULL;
 
     // Passes after this point must not move instructions; these analyses
     // depend on knowing the final order in which instructions will execute.
 
     if (js_IonOptions.edgeCaseAnalysis) {
--- a/js/src/ion/Ion.h
+++ b/js/src/ion/Ion.h
@@ -65,19 +65,24 @@ struct IonOptions
 
     // Toggles whether Edge Case Analysis is used.
     //
     // Default: true
     bool edgeCaseAnalysis;
 
     // Toggles whether Range Analysis is used.
     //
-    // Default: false
+    // Default: true
     bool rangeAnalysis;
 
+    // Toggles whether Unreachable Code Elimination is performed.
+    //
+    // Default: true
+    bool uce;
+
     // Toggles whether compilation occurs off the main thread.
     //
     // Default: true iff there are at least two CPUs available
     bool parallelCompilation;
 
     // How many invocations or loop iterations are needed before functions
     // are compiled.
     //
@@ -173,16 +178,17 @@ struct IonOptions
         gvnIsOptimistic(true),
         licm(true),
         osr(true),
         limitScriptSize(true),
         registerAllocator(RegisterAllocator_LSRA),
         inlining(true),
         edgeCaseAnalysis(true),
         rangeAnalysis(true),
+        uce(true),
         parallelCompilation(false),
         usesBeforeCompile(10240),
         usesBeforeCompileNoJaeger(40),
         usesBeforeInlining(usesBeforeCompile),
         maxStackArgs(4096),
         maxInlineDepth(3),
         smallFunctionMaxBytecodeLength(100),
         smallFunctionUsesBeforeInlining(usesBeforeInlining / 4),
--- a/js/src/ion/IonAnalysis.cpp
+++ b/js/src/ion/IonAnalysis.cpp
@@ -158,29 +158,46 @@ ion::EliminateDeadCode(MIRGenerator *mir
             }
         }
     }
 
     return true;
 }
 
 static inline bool
-IsPhiObservable(MPhi *phi)
+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->isFolded())
         return true;
 
-    // Check for any SSA uses. Note that this skips 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.
-    for (MUseDefIterator iter(phi); iter; iter++) {
-        if (!iter.def()->isPhi())
-            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.
+    switch (observe) {
+      case AggressiveObservability:
+        for (MUseDefIterator iter(phi); iter; iter++) {
+            if (!iter.def()->isPhi())
+                return true;
+        }
+        break;
+
+      case ConservativeObservability:
+        for (MUseIterator iter(phi->usesBegin()); iter != phi->usesEnd(); iter++) {
+            if (!iter->node()->isDefinition() ||
+                !iter->node()->toDefinition()->isPhi())
+                return true;
+        }
+        break;
     }
 
     // If the Phi is of the |this| value, it must always be observable.
     uint32_t slot = phi->slot();
     if (slot == 1)
         return true;
 
     // If the Phi is one of the formal argument, and we are using an argument
@@ -194,36 +211,57 @@ IsPhiObservable(MPhi *phi)
             return true;
     }
     return false;
 }
 
 // Handles cases like:
 //    x is phi(a, x) --> a
 //    x is phi(a, a) --> a
-static inline MDefinition *
+inline MDefinition *
 IsPhiRedundant(MPhi *phi)
 {
-    MDefinition *first = phi->getOperand(0);
-
-    for (size_t i = 1; i < phi->numOperands(); i++) {
-        if (phi->getOperand(i) != first && phi->getOperand(i) != phi)
-            return NULL;
-    }
+    MDefinition *first = phi->operandIfRedundant();
+    if (first == NULL)
+        return NULL;
 
     // Propagate the Folded flag if |phi| is replaced with another phi.
     if (phi->isFolded())
         first->setFoldedUnchecked();
 
     return first;
 }
 
 bool
-ion::EliminatePhis(MIRGenerator *mir, MIRGraph &graph)
+ion::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++) {
         if (mir->shouldCancel("Eliminate Phis (populate loop)"))
             return false;
 
@@ -236,17 +274,17 @@ ion::EliminatePhis(MIRGenerator *mir, MI
             // If the phi is redundant, remove it here.
             if (MDefinition *redundant = IsPhiRedundant(*iter)) {
                 iter->replaceAllUsesWith(redundant);
                 iter = block->discardPhiAt(iter);
                 continue;
             }
 
             // Enqueue observable Phis.
-            if (IsPhiObservable(*iter)) {
+            if (IsPhiObservable(*iter, observe)) {
                 iter->setInWorklist();
                 if (!worklist.append(*iter))
                     return false;
             }
             iter++;
         }
     }
 
@@ -871,33 +909,90 @@ AssertReversePostOrder(MIRGraph &graph)
 }
 #endif
 
 void
 ion::AssertGraphCoherency(MIRGraph &graph)
 {
 #ifdef DEBUG
     // Assert successor and predecessor list coherency.
+    uint32_t count = 0;
     for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) {
+        count++;
+
         for (size_t i = 0; i < block->numSuccessors(); i++)
             JS_ASSERT(CheckSuccessorImpliesPredecessor(*block, block->getSuccessor(i)));
 
         for (size_t i = 0; i < block->numPredecessors(); i++)
             JS_ASSERT(CheckPredecessorImpliesSuccessor(*block, block->getPredecessor(i)));
 
         for (MInstructionIterator ins = block->begin(); ins != block->end(); ins++) {
             for (uint32_t i = 0; i < ins->numOperands(); i++)
                 JS_ASSERT(CheckMarkedAsUse(*ins, ins->getOperand(i)));
         }
     }
 
+    JS_ASSERT(graph.numBlocks() == count);
+
     AssertReversePostOrder(graph);
 #endif
 }
 
+void
+ion::AssertExtendedGraphCoherency(MIRGraph &graph)
+{
+    // Checks the basic GraphCoherency but also other conditions that
+    // do not hold immediately (such as the fact that critical edges
+    // are split)
+
+#ifdef DEBUG
+    AssertGraphCoherency(graph);
+
+    uint32_t idx = 0;
+    for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) {
+        JS_ASSERT(block->id() == idx++);
+
+        // No critical edges:
+        if (block->numSuccessors() > 1)
+            for (size_t i = 0; i < block->numSuccessors(); i++)
+                JS_ASSERT(block->getSuccessor(i)->numPredecessors() == 1);
+
+        if (block->isLoopHeader()) {
+            JS_ASSERT(block->numPredecessors() == 2);
+            MBasicBlock *backedge = block->getPredecessor(1);
+            JS_ASSERT(backedge->id() >= block->id());
+            JS_ASSERT(backedge->numSuccessors() == 1);
+            JS_ASSERT(backedge->getSuccessor(0) == *block);
+        }
+
+        if (!block->phisEmpty()) {
+            for (size_t i = 0; i < block->numPredecessors(); i++) {
+                MBasicBlock *pred = block->getPredecessor(i);
+                JS_ASSERT(pred->successorWithPhis() == *block);
+                JS_ASSERT(pred->positionInPhiSuccessor() == i);
+            }
+        }
+
+        uint32_t successorWithPhis = 0;
+        for (size_t i = 0; i < block->numSuccessors(); i++)
+            if (!block->getSuccessor(i)->phisEmpty())
+                successorWithPhis++;
+
+        JS_ASSERT(successorWithPhis <= 1);
+        JS_ASSERT_IF(successorWithPhis, block->successorWithPhis() != NULL);
+
+        // I'd like to assert this, but it's not necc. true.  Sometimes we set this
+        // flag to non-NULL just because a successor has multiple preds, even if it
+        // does not actually have any phis.
+        //
+        // JS_ASSERT_IF(!successorWithPhis, block->successorWithPhis() == NULL);
+    }
+#endif
+}
+
 
 struct BoundsCheckInfo
 {
     MBoundsCheck *check;
     uint32_t validUntil;
 };
 
 typedef HashMap<uint32_t,
--- a/js/src/ion/IonAnalysis.h
+++ b/js/src/ion/IonAnalysis.h
@@ -17,18 +17,23 @@ namespace js {
 namespace ion {
 
 class MIRGenerator;
 class MIRGraph;
 
 bool
 SplitCriticalEdges(MIRGraph &graph);
 
+enum Observability {
+    ConservativeObservability,
+    AggressiveObservability
+};
+
 bool
-EliminatePhis(MIRGenerator *mir, MIRGraph &graph);
+EliminatePhis(MIRGenerator *mir, MIRGraph &graph, Observability observe);
 
 bool
 EliminateDeadResumePointOperands(MIRGenerator *mir, MIRGraph &graph);
 
 bool
 EliminateDeadCode(MIRGenerator *mir, MIRGraph &graph);
 
 bool
@@ -41,16 +46,19 @@ bool
 BuildDominatorTree(MIRGraph &graph);
 
 bool
 BuildPhiReverseMapping(MIRGraph &graph);
 
 void
 AssertGraphCoherency(MIRGraph &graph);
 
+void
+AssertExtendedGraphCoherency(MIRGraph &graph);
+
 bool
 EliminateRedundantBoundsChecks(MIRGraph &graph);
 
 class MDefinition;
 
 // Simple linear sum of the form 'n' or 'x + n'.
 struct SimpleLinearSum
 {
--- a/js/src/ion/MIR.cpp
+++ b/js/src/ion/MIR.cpp
@@ -429,16 +429,36 @@ MGoto::New(MBasicBlock *target)
 }
 
 MPhi *
 MPhi::New(uint32_t slot)
 {
     return new MPhi(slot);
 }
 
+void
+MPhi::removeOperand(size_t index)
+{
+    JS_ASSERT(index < inputs_.length());
+    JS_ASSERT(inputs_.length() > 1);
+
+    // If we have phi(..., a, b, c, d, ..., z) and we plan
+    // on removing a, then first shift downward so that we have
+    // phi(..., b, c, d, ..., z, z):
+    size_t length = inputs_.length();
+    for (size_t i = index + 1; i < length; i++)
+        replaceOperand(i - 1, getOperand(i));
+
+    // remove the final operand that now appears twice:
+    replaceOperand(length - 1, NULL);
+
+    // truncate the inputs_ list:
+    inputs_.shrinkBy(1);
+}
+
 MDefinition *
 MPhi::foldsTo(bool useValueNumbers)
 {
     JS_ASSERT(inputs_.length() != 0);
 
     MDefinition *first = getOperand(0);
 
     for (size_t i = 1; i < inputs_.length(); i++) {
--- a/js/src/ion/MIR.h
+++ b/js/src/ion/MIR.h
@@ -2783,16 +2783,18 @@ class MPhi : public MDefinition, public 
     void setOperand(size_t index, MDefinition *operand) {
         inputs_[index] = operand;
     }
 
   public:
     INSTRUCTION_HEADER(Phi)
     static MPhi *New(uint32_t slot);
 
+    void removeOperand(size_t index);
+
     MDefinition *getOperand(size_t index) const {
         return inputs_[index];
     }
     size_t numOperands() const {
         return inputs_.length();
     }
     uint32_t slot() const {
         return slot_;
@@ -2816,16 +2818,28 @@ class MPhi : public MDefinition, public 
     void setIterator() {
         isIterator_ = true;
     }
 
     AliasSet getAliasSet() const {
         return AliasSet::None();
     }
     void computeRange();
+
+    MDefinition *operandIfRedundant() {
+        // If this phi is redundant (e.g., phi(a,a) or b=phi(a,this)),
+        // returns the operand that it will always be equal to (a, in
+        // those two cases).
+        MDefinition *first = getOperand(0);
+        for (size_t i = 1; i < numOperands(); i++) {
+            if (getOperand(i) != first && getOperand(i) != this)
+                return NULL;
+        }
+        return first;
+    }
 };
 
 // The goal of a Beta node is to split a def at a conditionally taken
 // branch, so that uses dominated by it have a different name.
 class MBeta : public MUnaryInstruction
 {
   private:
     const Range *comparison_;
--- a/js/src/ion/MIRGraph.cpp
+++ b/js/src/ion/MIRGraph.cpp
@@ -45,29 +45,25 @@ MIRGenerator::abort(const char *message,
 }
 
 void
 MIRGraph::addBlock(MBasicBlock *block)
 {
     JS_ASSERT(block);
     block->setId(blockIdGen_++);
     blocks_.pushBack(block);
-#ifdef DEBUG
     numBlocks_++;
-#endif
 }
 
 void
 MIRGraph::insertBlockAfter(MBasicBlock *at, MBasicBlock *block)
 {
     block->setId(blockIdGen_++);
     blocks_.insertAfter(at, block);
-#ifdef DEBUG
     numBlocks_++;
-#endif
 }
 
 void
 MIRGraph::unmarkBlocks() {
     for (MBasicBlockIterator i(blocks_.begin()); i != blocks_.end(); i++)
         i->unmark();
 }
 
@@ -683,16 +679,23 @@ MBasicBlock::setBackedge(MBasicBlock *pr
     }
 
     // We are now a loop header proper
     kind_ = LOOP_HEADER;
 
     return predecessors_.append(pred);
 }
 
+void
+MBasicBlock::clearLoopHeader()
+{
+    JS_ASSERT(isLoopHeader());
+    kind_ = NORMAL;
+}
+
 size_t
 MBasicBlock::numSuccessors() const
 {
     JS_ASSERT(lastIns());
     return lastIns()->numSuccessors();
 }
 
 MBasicBlock *
@@ -723,16 +726,53 @@ MBasicBlock::replacePredecessor(MBasicBl
             // The same block should not appear twice in the predecessor list.
             for (size_t j = i; j < numPredecessors(); j++)
                 JS_ASSERT(predecessors_[j] != old);
 #endif
 
             return;
         }
     }
+
+    JS_NOT_REACHED("predecessor was not found");
+}
+
+void
+MBasicBlock::clearDominatorInfo()
+{
+    setImmediateDominator(NULL);
+    immediatelyDominated_.clear();
+    numDominated_ = 0;
+}
+
+void
+MBasicBlock::removePredecessor(MBasicBlock *pred)
+{
+    JS_ASSERT(numPredecessors() >= 2);
+
+    for (size_t i = 0; i < numPredecessors(); i++) {
+        if (getPredecessor(i) != pred)
+            continue;
+
+        // Adjust phis.  Note that this can leave redundant phis
+        // behind.
+        if (!phisEmpty()) {
+            JS_ASSERT(pred->successorWithPhis());
+            JS_ASSERT(pred->positionInPhiSuccessor() == i);
+            for (MPhiIterator iter = phisBegin(); iter != phisEnd(); iter++)
+                iter->removeOperand(i);
+            for (size_t j = i+1; j < numPredecessors(); j++)
+                getPredecessor(j)->setSuccessorWithPhis(this, j - 1);
+        }
+
+        // Remove from pred list.
+        MBasicBlock **ptr = predecessors_.begin() + i;
+        predecessors_.erase(ptr);
+        return;
+    }
     JS_NOT_REACHED("predecessor was not found");
 }
 
 void
 MBasicBlock::inheritPhis(MBasicBlock *header)
 {
     for (MPhiIterator iter = header->phisBegin(); iter != header->phisEnd(); iter++) {
         MPhi *phi = *iter;
--- a/js/src/ion/MIRGraph.h
+++ b/js/src/ion/MIRGraph.h
@@ -161,20 +161,34 @@ class MBasicBlock : public TempObject, p
     void inheritSlots(MBasicBlock *parent);
     bool initEntrySlots();
 
     // Replaces an edge for a given block with a new block. This is used for
     // critical edge splitting.
     void replacePredecessor(MBasicBlock *old, MBasicBlock *split);
     void replaceSuccessor(size_t pos, MBasicBlock *split);
 
+    // Removes `pred` from the predecessor list.  `pred` should not be
+    // the final predecessor. If this block defines phis, removes the
+    // entry for `pred` and updates the indices of later entries.
+    // This may introduce redundant phis if the new block has fewer
+    // than two predecessors.
+    void removePredecessor(MBasicBlock *pred);
+
+    // Resets all the dominator info so that it can be recomputed.
+    void clearDominatorInfo();
+
     // Sets a back edge. This places phi nodes and rewrites instructions within
     // the current loop as necessary.
     bool setBackedge(MBasicBlock *block);
 
+    // Resets a LOOP_HEADER block to a NORMAL block.  This is needed when
+    // optimizations remove the backedge.
+    void clearLoopHeader();
+
     // Propagates phis placed in a loop header down to this successor block.
     void inheritPhis(MBasicBlock *header);
 
     void insertBefore(MInstruction *at, MInstruction *ins);
     void insertAfter(MInstruction *at, MInstruction *ins);
 
     // Add an instruction to this block, from elsewhere in the graph.
     void addFromElsewhere(MInstruction *ins);
@@ -451,31 +465,27 @@ class MIRGraph
     uint32_t blockIdGen_;
     uint32_t idGen_;
     MBasicBlock *osrBlock_;
     MStart *osrStart_;
 
     // List of compiled/inlined scripts.
     Vector<JSScript *, 4, IonAllocPolicy> scripts_;
 
-#ifdef DEBUG
     size_t numBlocks_;
-#endif
 
   public:
     MIRGraph(TempAllocator *alloc)
       : alloc_(alloc),
         exitAccumulator_(NULL),
         blockIdGen_(0),
         idGen_(0),
         osrBlock_(NULL),
-        osrStart_(NULL)
-#ifdef DEBUG
-        , numBlocks_(0)
-#endif
+        osrStart_(NULL),
+        numBlocks_(0)
     { }
 
     template <typename T>
     T * allocate(size_t count = 1) {
         return reinterpret_cast<T *>(alloc_->allocate(sizeof(T) * count));
     }
 
     void addBlock(MBasicBlock *block);
@@ -499,19 +509,17 @@ class MIRGraph
 
     MBasicBlock *entryBlock() {
         return *blocks_.begin();
     }
 
     void clearBlockList() {
         blocks_.clear();
         blockIdGen_ = 0;
-#ifdef DEBUG
         numBlocks_ = 0;
-#endif
     }
     void resetInstructionNumber() {
         idGen_ = 0;
     }
     MBasicBlockIterator begin() {
         return blocks_.begin();
     }
     MBasicBlockIterator begin(MBasicBlock *at) {
@@ -529,30 +537,26 @@ class MIRGraph
     ReversePostorderIterator rpoBegin() {
         return blocks_.begin();
     }
     ReversePostorderIterator rpoEnd() {
         return blocks_.end();
     }
     void removeBlock(MBasicBlock *block) {
         blocks_.remove(block);
-#ifdef DEBUG
         numBlocks_--;
-#endif
     }
     void moveBlockToEnd(MBasicBlock *block) {
         JS_ASSERT(block->id());
         blocks_.remove(block);
         blocks_.pushBack(block);
     }
-#ifdef DEBUG
     size_t numBlocks() const {
         return numBlocks_;
     }
-#endif
     uint32_t numBlockIds() const {
         return blockIdGen_;
     }
     void allocDefinitionId(MDefinition *ins) {
         // This intentionally starts above 0. The id 0 is in places used to
         // indicate a failure to perform an operation on an instruction.
         idGen_ += 2;
         ins->setId(idGen_);
@@ -562,19 +566,17 @@ class MIRGraph
     }
     MResumePoint *entryResumePoint() {
         return blocks_.begin()->entryResumePoint();
     }
 
     void copyIds(const MIRGraph &other) {
         idGen_ = other.idGen_;
         blockIdGen_ = other.blockIdGen_;
-#ifdef DEBUG
         numBlocks_ = other.numBlocks_;
-#endif
     }
 
     void setOsrBlock(MBasicBlock *osrBlock) {
         JS_ASSERT(!osrBlock_);
         osrBlock_ = osrBlock;
     }
     MBasicBlock *osrBlock() {
         return osrBlock_;
new file mode 100644
--- /dev/null
+++ b/js/src/ion/UnreachableCodeElimination.cpp
@@ -0,0 +1,202 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=4 sw=4 et 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 "UnreachableCodeElimination.h"
+#include "IonAnalysis.h"
+
+using namespace js;
+using namespace ion;
+
+bool
+UnreachableCodeElimination::analyze()
+{
+    // The goal of this routine is to eliminate code that is
+    // unreachable, either because there is no path from the entry
+    // block to the code, or because the path traverses a conditional
+    // branch where the condition is a constant (e.g., "if (false) {
+    // ... }").  The latter can either appear in the source form or
+    // arise due to optimizations.
+    //
+    // The stategy is straightforward.  The pass begins with a
+    // depth-first search.  We set a bit on each basic block that
+    // is visited.  If a block terminates in a conditional branch
+    // predicated on a constant, we rewrite the block to an unconditional
+    // jump and do not visit the now irrelevant basic block.
+    //
+    // Once the initial DFS is complete, we do a second pass over the
+    // blocks to find those that were not reached.  Those blocks are
+    // simply removed wholesale.  We must also correct any phis that
+    // may be affected..
+
+    // Pass 1: Identify unreachable blocks (if any).
+    if (!prunePointlessBranchesAndMarkReachableBlocks())
+        return false;
+    if (marked_ == graph_.numBlocks()) {
+        // Everything is reachable.
+        graph_.unmarkBlocks();
+        return true;
+    }
+
+    // Pass 2: Remove unmarked blocks.
+    if (!removeUnmarkedBlocksAndClearDominators())
+        return false;
+    graph_.unmarkBlocks();
+
+    // Pass 3: Recompute dominators and tweak phis.
+    BuildDominatorTree(graph_);
+    if (redundantPhis_ && !EliminatePhis(mir_, graph_, ConservativeObservability))
+        return false;
+
+    return true;
+}
+
+bool
+UnreachableCodeElimination::prunePointlessBranchesAndMarkReachableBlocks()
+{
+    Vector<MBasicBlock *, 16, SystemAllocPolicy> worklist;
+
+    // Seed with the two entry points.
+    MBasicBlock *entries[] = { graph_.entryBlock(), graph_.osrBlock() };
+    for (size_t i = 0; i < sizeof(entries) / sizeof(entries[0]); i++) {
+        if (entries[i]) {
+            entries[i]->mark();
+            marked_++;
+            if (!worklist.append(entries[i]))
+                return false;
+        }
+    }
+
+    // Process everything reachable from there.
+    while (!worklist.empty()) {
+        if (mir_->shouldCancel("Eliminate Unreachable Code"))
+            return false;
+
+        MBasicBlock *block = worklist.popCopy();
+        MControlInstruction *ins = block->lastIns();
+
+        // Rewrite test false or test true to goto.
+        if (ins->isTest()) {
+            MTest *testIns = ins->toTest();
+            MDefinition *v = testIns->getOperand(0);
+            if (v->isConstant()) {
+                const Value &val = v->toConstant()->value();
+                if (val.isBoolean()) {
+                    BranchDirection bdir = (val.isTrue() ? TRUE_BRANCH : FALSE_BRANCH);
+                    MBasicBlock *succ = testIns->branchSuccessor(bdir);
+                    MGoto *gotoIns = MGoto::New(succ);
+                    block->discardLastIns();
+                    block->end(gotoIns);
+                    MBasicBlock *successorWithPhis = block->successorWithPhis();
+                    if (successorWithPhis && successorWithPhis != succ)
+                        block->setSuccessorWithPhis(NULL, 0);
+                }
+            }
+        }
+
+        for (size_t i = 0; i < block->numSuccessors(); i++) {
+            MBasicBlock *succ = block->getSuccessor(i);
+            if (!succ->isMarked()) {
+                succ->mark();
+                marked_++;
+                if (!worklist.append(succ))
+                    return false;
+            }
+        }
+    }
+    return true;
+}
+
+void
+UnreachableCodeElimination::removeUsesFromUnmarkedBlocks(MDefinition *instr)
+{
+    for (MUseIterator iter(instr->usesBegin()); iter != instr->usesEnd(); ) {
+        if (!iter->node()->block()->isMarked())
+            iter = instr->removeUse(iter);
+        else
+            iter++;
+    }
+}
+
+bool
+UnreachableCodeElimination::removeUnmarkedBlocksAndClearDominators()
+{
+    // Removes blocks that are not marked from the graph.  For blocks
+    // that *are* marked, clears the mark and adjusts the id to its
+    // new value.  Also adds blocks that are immediately reachable
+    // from an unmarked block to the frontier.
+
+    size_t id = marked_;
+    for (PostorderIterator iter(graph_.poBegin()); iter != graph_.poEnd();) {
+        if (mir_->shouldCancel("Eliminate Unreachable Code"))
+            return false;
+
+        MBasicBlock *block = *iter;
+        iter++;
+
+        // Unconditionally clear the dominators.  It's somewhat complex to
+        // adjust the values and relatively fast to just recompute.
+        block->clearDominatorInfo();
+
+        if (block->isMarked()) {
+            block->setId(--id);
+            for (MPhiIterator iter(block->phisBegin()); iter != block->phisEnd(); iter++)
+                removeUsesFromUnmarkedBlocks(*iter);
+            for (MInstructionIterator iter(block->begin()); iter != block->end(); iter++)
+                removeUsesFromUnmarkedBlocks(*iter);
+        } else {
+            if (block->numPredecessors() > 1) {
+                // If this block had phis, then any reachable
+                // predecessors need to have the successorWithPhis
+                // flag cleared.
+                for (size_t i = 0; i < block->numPredecessors(); i++)
+                    block->getPredecessor(i)->setSuccessorWithPhis(NULL, 0);
+            }
+
+            if (block->isLoopBackedge()) {
+                // NB. We have to update the loop header if we
+                // eliminate the backedge. At first I thought this
+                // check would be insufficient, because it would be
+                // possible to have code like this:
+                //
+                //    while (true) {
+                //       ...;
+                //       if (1 == 1) break;
+                //    }
+                //
+                // in which the backedge is removed as part of
+                // rewriting the condition, but no actual blocks are
+                // removed.  However, in all such cases, the backedge
+                // would be a critical edge and hence the critical
+                // edge block is being removed.
+                block->loopHeaderOfBackedge()->clearLoopHeader();
+            }
+
+            for (size_t i = 0, c = block->numSuccessors(); i < c; i++) {
+                MBasicBlock *succ = block->getSuccessor(i);
+                if (succ->isMarked()) {
+                    // succ is on the frontier of blocks to be removed:
+                    succ->removePredecessor(block);
+
+                    if (!redundantPhis_) {
+                        for (MPhiIterator iter(succ->phisBegin()); iter != succ->phisEnd(); iter++) {
+                            if (iter->operandIfRedundant()) {
+                                redundantPhis_ = true;
+                                break;
+                            }
+                        }
+                    }
+                }
+            }
+
+            graph_.removeBlock(block);
+        }
+    }
+
+    JS_ASSERT(id == 0);
+
+    return true;
+}
new file mode 100644
--- /dev/null
+++ b/js/src/ion/UnreachableCodeElimination.h
@@ -0,0 +1,44 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=4 sw=4 et 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/. */
+
+#ifndef jsion_unreachable_code_elimination_h__
+#define jsion_unreachable_code_elimination_h__
+
+#include "MIR.h"
+#include "MIRGraph.h"
+
+namespace js {
+namespace ion {
+
+class MIRGraph;
+
+class UnreachableCodeElimination
+{
+    MIRGenerator *mir_;
+    MIRGraph &graph_;
+    uint32_t marked_;
+    bool redundantPhis_;
+
+    bool prunePointlessBranchesAndMarkReachableBlocks();
+    void removeUsesFromUnmarkedBlocks(MDefinition *instr);
+    bool removeUnmarkedBlocksAndClearDominators();
+
+  public:
+    UnreachableCodeElimination(MIRGenerator *mir, MIRGraph &graph)
+      : mir_(mir),
+        graph_(graph),
+        marked_(0),
+        redundantPhis_(false)
+    {}
+
+    bool analyze();
+};
+
+} /* namespace ion */
+} /* namespace js */
+
+#endif
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/ion/eliminate-unreachable-1.js
@@ -0,0 +1,32 @@
+// Test for one annoying case of the EliminateUnreachableCode
+// optimization.  Here the dominators change and also phis are
+// eliminated.
+
+function test1(v) {
+  var i = 0;
+  if (v) {
+    if (v) {
+      i += 1;
+    } else {
+      i += 10;
+    }
+    i += 100;
+  } else {
+    if (v) {
+      i += 1000;
+    } else {
+      i += 10000;
+    }
+    i += 100000;
+  }
+  i += 1000000;
+  return i;
+}
+
+function test() {
+  assertEq(test1(true), 1000101);
+  assertEq(test1(false), 1110000);
+}
+
+for (var i = 0; i < 100; i++)
+  test();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/ion/eliminate-unreachable-2.js
@@ -0,0 +1,28 @@
+// Test for one annoying case of the EliminateUnreachableCode
+// optimization.  Here the dominator of print("Goodbye") changes to be
+// the print("Hello") after optimization.
+
+function test1(v) {
+  if (v) {
+    if (v) {
+      assertEq(v, v);
+    } else {
+      assertEq(0, 1);
+    }
+  } else {
+    if (v) {
+      assertEq(0, 1);
+    } else {
+      assertEq(v, v);
+    }
+  }
+  assertEq(v, v);
+}
+
+function test() {
+  test1(true);
+  test1(false);
+}
+
+for (var i = 0; i < 100; i++)
+  test();