Bug 844779 - IonMonkey: Make loops contiguous. r=h4writer
authorDan Gohman <sunfish@mozilla.com>
Fri, 06 Jun 2014 08:21:48 -0700
changeset 206452 5b4bd2f81719a1a2ef9623ebe0023e771aa7fe25
parent 206451 a2aa79041b93e86fb35322f56c1a6bf340255a8d
child 206453 5429275a038dba7577d1371a35fbd65ea637bb15
push id3741
push userasasaki@mozilla.com
push dateMon, 21 Jul 2014 20:25:18 +0000
treeherdermozilla-beta@4d6f46f5af68 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersh4writer
bugs844779
milestone32.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 844779 - IonMonkey: Make loops contiguous. r=h4writer
js/src/jit/Ion.cpp
js/src/jit/IonAnalysis.cpp
js/src/jit/IonAnalysis.h
js/src/jit/MIRGraph.h
js/src/vm/TraceLogging.h
--- a/js/src/jit/Ion.cpp
+++ b/js/src/jit/Ion.cpp
@@ -1503,16 +1503,31 @@ OptimizeMIR(MIRGenerator *mir)
             return false;
         IonSpewPass("DCE");
         AssertExtendedGraphCoherency(graph);
 
         if (mir->shouldCancel("DCE"))
             return false;
     }
 
+    // Make loops contiguious. We do this after GVN/UCE and range analysis,
+    // which can remove CFG edges, exposing more blocks that can be moved.
+    // We also disable this when profiling, since reordering blocks appears
+    // to make the profiler unhappy.
+    {
+        AutoTraceLog log(logger, TraceLogger::MakeLoopsContiguous);
+        if (!MakeLoopsContiguous(graph))
+            return false;
+        IonSpewPass("Make loops contiguous");
+        AssertExtendedGraphCoherency(graph);
+
+        if (mir->shouldCancel("Make loops contiguous"))
+            return false;
+    }
+
     // Passes after this point must not move instructions; these analyses
     // depend on knowing the final order in which instructions will execute.
 
     if (mir->optimizationInfo().edgeCaseAnalysisEnabled()) {
         AutoTraceLog log(logger, TraceLogger::EdgeCaseAnalysis);
         EdgeCaseAnalysis edgeCaseAnalysis(mir, graph);
         if (!edgeCaseAnalysis.analyzeLate())
             return false;
--- a/js/src/jit/IonAnalysis.cpp
+++ b/js/src/jit/IonAnalysis.cpp
@@ -2477,8 +2477,101 @@ jit::AnalyzeArgumentsUsage(JSContext *cx
     // 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;
 }
+
+// Reorder the blocks in the loop starting at the given header to be contiguous.
+static void
+MakeLoopContiguous(MIRGraph &graph, MBasicBlock *header, MBasicBlock *backedge, size_t numMarked)
+{
+    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 afterLoopId = 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(afterLoopId++);
+        }
+    }
+    MOZ_ASSERT(header->id() == headerId, "Loop header id changed");
+    MOZ_ASSERT(inLoopId == headerId + numMarked, "Wrong number of blocks kept in loop");
+    MOZ_ASSERT(afterLoopId == (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)
+{
+    MBasicBlock *osrBlock = graph.osrBlock();
+    Vector<MBasicBlock *, 1, IonAllocPolicy> inlooplist(graph.alloc());
+
+    // 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 the blocks in the loop by marking all blocks in a path
+        // between the backedge and the loop header.
+        MBasicBlock *backedge = header->backedge();
+        size_t numMarked = 1;
+        backedge->mark();
+        if (!inlooplist.append(backedge))
+            return false;
+        do {
+            MBasicBlock *block = inlooplist.popCopy();
+            MOZ_ASSERT(block->id() >= header->id() && block->id() <= backedge->id(),
+                       "Non-OSR predecessor of loop block not between header and backedge");
+            if (block == header)
+                continue;
+            for (size_t p = 0; p < block->numPredecessors(); p++) {
+                MBasicBlock *pred = block->getPredecessor(p);
+                if (pred->isMarked())
+                    continue;
+                // Ignore paths entering the loop in the middle from an OSR
+                // entry. They won't pass through the loop header and they
+                // aren't part of the loop.
+                if (osrBlock && osrBlock->dominates(pred) && !osrBlock->dominates(header))
+                    continue;
+                ++numMarked;
+                pred->mark();
+                if (!inlooplist.append(pred))
+                    return false;
+            }
+        } while (!inlooplist.empty());
+
+        // 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, backedge, numMarked);
+    }
+
+    return true;
+}
--- a/js/src/jit/IonAnalysis.h
+++ b/js/src/jit/IonAnalysis.h
@@ -27,16 +27,19 @@ enum Observability {
     ConservativeObservability,
     AggressiveObservability
 };
 
 bool
 EliminatePhis(MIRGenerator *mir, MIRGraph &graph, Observability observe);
 
 bool
+MakeLoopsContiguous(MIRGraph &graph);
+
+bool
 EliminateDeadResumePointOperands(MIRGenerator *mir, MIRGraph &graph);
 
 bool
 EliminateDeadCode(MIRGenerator *mir, MIRGraph &graph);
 
 bool
 ApplyTypeInformation(MIRGenerator *mir, MIRGraph &graph);
 
--- a/js/src/jit/MIRGraph.h
+++ b/js/src/jit/MIRGraph.h
@@ -617,16 +617,21 @@ class MIRGraph
     }
     void removeBlocksAfter(MBasicBlock *block);
     void removeBlock(MBasicBlock *block);
     void moveBlockToEnd(MBasicBlock *block) {
         JS_ASSERT(block->id());
         blocks_.remove(block);
         blocks_.pushBack(block);
     }
+    void moveBlockBefore(MBasicBlock *at, MBasicBlock *block) {
+        JS_ASSERT(block->id());
+        blocks_.remove(block);
+        blocks_.insertBefore(at, block);
+    }
     size_t numBlocks() const {
         return numBlocks_;
     }
     uint32_t numBlockIds() const {
         return blockIdGen_;
     }
     void allocDefinitionId(MDefinition *ins) {
         ins->setId(idGen_++);
--- a/js/src/vm/TraceLogging.h
+++ b/js/src/vm/TraceLogging.h
@@ -132,16 +132,17 @@ namespace jit {
     _(IrregexpExecute)                                \
     _(VM)                                             \
                                                       \
     /* Specific passes during ion compilation */      \
     _(SplitCriticalEdges)                             \
     _(RenumberBlocks)                                 \
     _(DominatorTree)                                  \
     _(PhiAnalysis)                                    \
+    _(MakeLoopsContiguous)                            \
     _(ApplyTypes)                                     \
     _(ParallelSafetyAnalysis)                         \
     _(AliasAnalysis)                                  \
     _(GVN)                                            \
     _(UCE)                                            \
     _(LICM)                                           \
     _(RangeAnalysis)                                  \
     _(EffectiveAddressAnalysis)                       \