Bug 1229813 - Improve Branch Pruning heuristics. r=jandem
☠☠ backed out by 5e43e3f84e81 ☠ ☠
authorNicolas B. Pierron <nicolas.b.pierron@mozilla.com>
Thu, 09 Jun 2016 13:54:29 +0000
changeset 301360 0ace95ea7f4cb6366e19a3a4e9e8626637f74028
parent 301359 a5dffe261ee1c41cfff95ba1859cbed8240c07da
child 301361 1e0258f175c13227aeda0968f20d643b5cc4130b
push id30333
push usercbook@mozilla.com
push dateFri, 10 Jun 2016 13:39:58 +0000
treeherdermozilla-central@52679ce4756c [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjandem
bugs1229813
milestone50.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1229813 - Improve Branch Pruning heuristics. r=jandem
js/src/jit/IonAnalysis.cpp
--- a/js/src/jit/IonAnalysis.cpp
+++ b/js/src/jit/IonAnalysis.cpp
@@ -260,20 +260,23 @@ jit::PruneUnusedBranches(MIRGenerator* m
     MOZ_ASSERT(!mir->compilingAsmJS(), "AsmJS compilation have 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++) {
         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())
+        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++) {
@@ -297,56 +300,103 @@ jit::PruneUnusedBranches(MIRGenerator* m
         // 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 (shouldBailout) {
+        if (!isUnreachable && shouldBailout) {
             size_t p = numPred;
             size_t predCount = 0;
             bool isLoopExit = false;
+            bool isCaseStatement = false;
             while (p--) {
                 MBasicBlock* pred = block->getPredecessor(p);
                 if (pred->getHitState() == MBasicBlock::HitState::Count)
                     predCount += pred->getHitCount();
                 isLoopExit |= pred->isLoopHeader() && pred->backedge() != *block;
+                isCaseStatement |= pred->numSuccessors() > 2;
             }
 
-            // This assumes that instructions are numbered in sequence, which is
-            // the case after IonBuilder creation of basic blocks.
-            size_t numInst = block->rbegin()->id() - block->begin()->id();
-
-            // This sum is not homogeneous but gives good results on benchmarks
-            // like Kraken and Octane. The current block has not been executed
-            // yet, and ...
+            // 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, as this is a heuristic.
+            size_t numDominatedInst = 0;
+            int numInOutEdges = block->numPredecessors();
+            ReversePostorderIterator it(block);
+            do {
+                for (MDefinitionIterator def(*it); def; def++)
+                    numDominatedInst++;
+
+                numInOutEdges += int(it->numSuccessors()) - int(it->numPredecessors());
+                it++;
+            } while (numInOutEdges > 0 && it != graph.rpoEnd());
+
+            // This relation is a heuristic which attempt at avoiding converting
+            // this block to a bailing block when we do not have enough
+            // information to make a wise decision.
             //
             //   1. If the number of times the predecessor got executed is
             //      larger, then we are less likely to hit this block.
             //
             //   2. If the block is large, then this is likely a corner case,
             //      and thus we are less likely to hit this block.
-            if (predCount + numInst < 75)
+            //
+            // predCount
+            //  ^
+            //  |x
+            //  |x
+            //  |xx
+            //  |xx
+            //  |xxxx
+            //  |xxxxxxx
+            //  |xxxxxxxxxxxxxx
+            //  |xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
+            //  +---------------------------------> numInst
+            //
+            if (predCount * numDominatedInst * numDominatedInst < 250000)
                 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 heat up in a
+            // subset of instructions, but might need other instructions for the
+            // rest of the evaluation.
+            if (isCaseStatement)
+                shouldBailout = false;
+
+            // If this basic block is a simple basic block which contains an
+            // early return statement, we should compile it as such as the cost
+            // of a return is less than the cost of a bailout.
+            bool isExitBlock = block->numSuccessors() == 0;
+            if (isExitBlock && numDominatedInst < 10)
+                shouldBailout = false;
+
+            JitSpew(JitSpew_Prune, "info: block %d, predCount: %lu, numDomInst: %lu, "
+                    "isLoopExit: %s, isExitBlock: %s, isCaseStatement: %s. (shouldBailout: %s)",
+                    block->id(), predCount, numDominatedInst,
+                    isLoopExit ? "true" : "false",
+                    isExitBlock ? "true" : "false",
+                    isCaseStatement ? "true" : "false",
+                    shouldBailout ? "true" : "false");
         }
 
         // Continue to the next basic block if the current basic block can
         // remain unchanged.
         if (!isUnreachable && !shouldBailout)
             continue;
 
-        JitSpewIndent indent(JitSpew_Prune);
         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());