Bug 1238592 - IonMonkey: Optimize away any OSR fixup blocks that are ultimately unreachable. r=nbp a=lizzard CLOSED TREE
authorDan Gohman <sunfish@mozilla.com>
Mon, 08 Feb 2016 16:11:37 -0800
changeset 317800 56772498e022e454c1489337e3477769b9513c46
parent 317799 eb98893ffbd4f38cec8172098d6da05e956b92b9
child 317803 871de95c7a87a05f97367405d8eb6fc344f32c34
push id5904
push userkwierso@gmail.com
push dateMon, 18 Apr 2016 18:41:36 +0000
treeherdermozilla-beta@56772498e022 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersnbp, lizzard
bugs1238592
milestone46.0
Bug 1238592 - IonMonkey: Optimize away any OSR fixup blocks that are ultimately unreachable. r=nbp a=lizzard CLOSED TREE MozReview-Commit-ID: APJfOl2lkRM
js/src/jit/IonAnalysis.cpp
js/src/jit/ValueNumbering.cpp
js/src/jit/ValueNumbering.h
--- a/js/src/jit/IonAnalysis.cpp
+++ b/js/src/jit/IonAnalysis.cpp
@@ -195,24 +195,24 @@ FlagAllOperandsAsHavingRemovedUses(MBasi
                     continue;
                 rp->getOperand(i)->setUseRemovedUnchecked();
             }
         }
     }
 
     // Flag observable operands of the entry resume point as having removed uses.
     MResumePoint* rp = block->entryResumePoint();
-    do {
+    while (rp) {
         for (size_t i = 0, e = rp->numOperands(); i < e; i++) {
             if (!rp->isObservableOperand(i))
                 continue;
             rp->getOperand(i)->setUseRemovedUnchecked();
         }
         rp = rp->caller();
-    } while (rp);
+    }
 
     // Flag Phi inputs of the successors has having removed uses.
     MPhiVector worklist;
     for (size_t i = 0, e = block->numSuccessors(); i < e; i++) {
         if (!FlagPhiInputsAsHavingRemovedUses(block, block->getSuccessor(i), worklist))
             return false;
     }
 
@@ -1916,16 +1916,27 @@ 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(block);
+        }
+
         // Find unmarked blocks and remove them.
         for (ReversePostorderIterator iter(graph.rpoBegin()); iter != graph.rpoEnd();) {
             MBasicBlock* block = *iter++;
 
             if (block->isMarked()) {
                 block->unmark();
                 continue;
             }
--- a/js/src/jit/ValueNumbering.cpp
+++ b/js/src/jit/ValueNumbering.cpp
@@ -457,16 +457,17 @@ ValueNumberer::fixupOSROnlyLoop(MBasicBl
     if (!block->addPredecessorWithoutPhis(fake))
         return false;
 
     // Restore |backedge| as |block|'s loop backedge.
     block->clearLoopHeader();
     block->setLoopHeader(backedge);
 
     JitSpew(JitSpew_GVN, "        Created fake block%u", fake->id());
+    hasOSRFixups_ = true;
     return true;
 }
 
 // Remove the CFG edge between |pred| and |block|, after releasing the phi
 // operands on that edge and discarding any definitions consequently made dead.
 bool
 ValueNumberer::removePredecessorAndDoDCE(MBasicBlock* block, MBasicBlock* pred, size_t predIndex)
 {
@@ -1071,27 +1072,74 @@ ValueNumberer::visitGraph()
             // This block a dominator tree root. Proceed to the next one.
             ++iter;
         }
     }
     totalNumVisited_ = 0;
     return true;
 }
 
+// OSR fixups serve the purpose of representing the non-OSR entry into a loop
+// when the only real entry is an OSR entry into the middle. However, if the
+// entry into the middle is subsequently folded away, the loop may actually
+// have become unreachable. Mark-and-sweep all blocks to remove all such code.
+bool ValueNumberer::cleanupOSRFixups()
+{
+    // Mark.
+    Vector<MBasicBlock*, 0, JitAllocPolicy> worklist(graph_.alloc());
+    unsigned numMarked = 2;
+    graph_.entryBlock()->mark();
+    graph_.osrBlock()->mark();
+    if (!worklist.append(graph_.entryBlock()) || !worklist.append(graph_.osrBlock()))
+        return false;
+    while (!worklist.empty()) {
+        MBasicBlock* block = worklist.popCopy();
+        for (size_t i = 0, e = block->numSuccessors(); i != e; ++i) {
+            MBasicBlock* succ = block->getSuccessor(i);
+            if (!succ->isMarked()) {
+                ++numMarked;
+                succ->mark();
+                if (!worklist.append(succ))
+                    return false;
+            }
+        }
+        // The one special thing we do during this mark pass is to mark
+        // loop predecessors of reachable blocks as reachable. These blocks are
+        // the OSR fixups blocks which need to remain if the loop remains,
+        // though they can be removed if the loop is removed.
+        if (block->isLoopHeader()) {
+            MBasicBlock* pred = block->loopPredecessor();
+            if (!pred->isMarked() && pred->numPredecessors() == 0) {
+                MOZ_ASSERT(pred->numSuccessors() == 1,
+                           "OSR fixup block should have exactly one successor");
+                MOZ_ASSERT(pred != graph_.entryBlock(),
+                           "OSR fixup block shouldn't be the entry block");
+                MOZ_ASSERT(pred != graph_.osrBlock(),
+                           "OSR fixup block shouldn't be the OSR entry block");
+                pred->mark();
+            }
+        }
+    }
+
+    // And sweep.
+    return RemoveUnmarkedBlocks(mir_, graph_, numMarked);
+}
+
 ValueNumberer::ValueNumberer(MIRGenerator* mir, MIRGraph& graph)
   : mir_(mir), graph_(graph),
     values_(graph.alloc()),
     deadDefs_(graph.alloc()),
     remainingBlocks_(graph.alloc()),
     nextDef_(nullptr),
     totalNumVisited_(0),
     rerun_(false),
     blocksRemoved_(false),
     updateAliasAnalysis_(false),
-    dependenciesBroken_(false)
+    dependenciesBroken_(false),
+    hasOSRFixups_(false)
 {}
 
 bool
 ValueNumberer::init()
 {
     // Initialize the value set. It's tempting to pass in a size here of some
     // function of graph_.getNumInstructionIds(), however if we start out with a
     // large capacity, it will be far larger than the actual element count for
@@ -1158,10 +1206,15 @@ ValueNumberer::run(UpdateAliasAnalysisFl
             JitSpew(JitSpew_GVN, "Re-run cutoff of %d reached. Terminating GVN!", runs);
             break;
         }
 
         JitSpew(JitSpew_GVN, "Re-running GVN on graph (run %d, now with %llu blocks)",
                 runs, uint64_t(graph_.numBlocks()));
     }
 
+    if (MOZ_UNLIKELY(hasOSRFixups_)) {
+        cleanupOSRFixups();
+        hasOSRFixups_ = false;
+    }
+
     return true;
 }
--- a/js/src/jit/ValueNumbering.h
+++ b/js/src/jit/ValueNumbering.h
@@ -66,16 +66,17 @@ class ValueNumberer
     DefWorklist deadDefs_;            // Worklist for deleting values
     BlockWorklist remainingBlocks_;   // Blocks remaining with fewer preds
     MDefinition* nextDef_;            // The next definition; don't discard
     size_t totalNumVisited_;          // The number of blocks visited
     bool rerun_;                      // Should we run another GVN iteration?
     bool blocksRemoved_;              // Have any blocks been removed?
     bool updateAliasAnalysis_;        // Do we care about AliasAnalysis?
     bool dependenciesBroken_;         // Have we broken AliasAnalysis?
+    bool hasOSRFixups_;               // Have we created any OSR fixup blocks?
 
     enum UseRemovedOption {
         DontSetUseRemoved,
         SetUseRemoved
     };
 
     bool handleUseReleased(MDefinition* def, UseRemovedOption useRemovedOption);
     bool discardDefsRecursively(MDefinition* def);
@@ -95,16 +96,17 @@ class ValueNumberer
     bool loopHasOptimizablePhi(MBasicBlock* header) const;
 
     bool visitDefinition(MDefinition* def);
     bool visitControlInstruction(MBasicBlock* block, const MBasicBlock* root);
     bool visitUnreachableBlock(MBasicBlock* block);
     bool visitBlock(MBasicBlock* block, const MBasicBlock* root);
     bool visitDominatorTree(MBasicBlock* root);
     bool visitGraph();
+    bool cleanupOSRFixups();
 
   public:
     ValueNumberer(MIRGenerator* mir, MIRGraph& graph);
     bool init();
 
     enum UpdateAliasAnalysisFlag {
         DontUpdateAliasAnalysis,
         UpdateAliasAnalysis