Bug 844779: IonMonkey: Improve the order of blocks, r=jandem
authorHannes Verschore <hv1989@gmail.com>
Fri, 05 Apr 2013 17:23:52 +0200
changeset 127837 d93ad2c96f01806909ccb442c090e0f95540dd99
parent 127836 2633093f531e511c2409f4e3cf54938d1177643b
child 127838 5820d44601c173d627eb30ee6ab6f18de6a807c5
push id24512
push userryanvm@gmail.com
push dateFri, 05 Apr 2013 20:13:49 +0000
treeherderautoland@139b6ba547fa [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjandem
bugs844779
milestone23.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: Improve the order of blocks, r=jandem
js/src/ion/AsmJS.cpp
js/src/ion/Ion.cpp
js/src/ion/IonAnalysis.cpp
js/src/ion/IonAnalysis.h
js/src/ion/IonBuilder.cpp
js/src/ion/MIRGraph.h
--- a/js/src/ion/AsmJS.cpp
+++ b/js/src/ion/AsmJS.cpp
@@ -1910,26 +1910,24 @@ class FunctionCompiler
     {
         if (!joinBlock)
             return;
         if (curBlock_) {
             curBlock_->end(MGoto::New(joinBlock));
             joinBlock->addPredecessor(curBlock_);
         }
         curBlock_ = joinBlock;
-        mirGraph().moveBlockToEnd(curBlock_);
     }
 
     MBasicBlock *switchToElse(MBasicBlock *elseBlock)
     {
         if (!elseBlock)
             return NULL;
         MBasicBlock *thenEnd = curBlock_;
         curBlock_ = elseBlock;
-        mirGraph().moveBlockToEnd(curBlock_);
         return thenEnd;
     }
 
     bool joinIfElse(MBasicBlock *thenEnd)
     {
         if (!curBlock_ && !thenEnd)
             return true;
         MBasicBlock *pred = curBlock_ ? curBlock_ : thenEnd;
@@ -2026,18 +2024,16 @@ class FunctionCompiler
         JS_ASSERT(loopEntry->loopDepth() == loopStack_.length() + 1);
         JS_ASSERT_IF(afterLoop, afterLoop->loopDepth() == loopStack_.length());
         if (curBlock_) {
             JS_ASSERT(curBlock_->loopDepth() == loopStack_.length() + 1);
             curBlock_->end(MGoto::New(loopEntry));
             loopEntry->setBackedge(curBlock_);
         }
         curBlock_ = afterLoop;
-        if (curBlock_)
-            mirGraph().moveBlockToEnd(curBlock_);
         return bindUnlabeledBreaks(pn);
     }
 
     bool branchAndCloseDoWhileLoop(MDefinition *cond, MBasicBlock *loopEntry)
     {
         ParseNode *pn = popLoop();
         if (!loopEntry) {
             JS_ASSERT(!curBlock_);
@@ -2140,17 +2136,16 @@ class FunctionCompiler
                 MBasicBlock *bb;
                 if (!newBlock(switchBlock, &bb))
                     return false;
                 bb->end(MGoto::New(*defaultBlock));
                 (*defaultBlock)->addPredecessor(bb);
                 (*cases)[i] = bb;
             }
         }
-        mirGraph().moveBlockToEnd(*defaultBlock);
         return true;
     }
 
     bool joinSwitch(MBasicBlock *switchBlock, const CaseVector &cases, MBasicBlock *defaultBlock)
     {
         ParseNode *pn = breakableStack_.popCopy();
         if (!switchBlock)
             return true;
--- a/js/src/ion/Ion.cpp
+++ b/js/src/ion/Ion.cpp
@@ -888,32 +888,45 @@ ion::ToggleBarriers(JS::Zone *zone, bool
 
 namespace js {
 namespace ion {
 
 bool
 OptimizeMIR(MIRGenerator *mir)
 {
     IonSpewPass("BuildSSA");
-    // Note: don't call AssertGraphCoherency before SplitCriticalEdges,
+    // Note: don't call AssertGraphCoherency before ReorderBlocks,
     // the graph is not in RPO at this point.
 
     MIRGraph &graph = mir->graph();
 
     if (mir->shouldCancel("Start"))
         return false;
 
     if (!SplitCriticalEdges(graph))
         return false;
     IonSpewPass("Split Critical Edges");
-    AssertGraphCoherency(graph);
 
     if (mir->shouldCancel("Split Critical Edges"))
         return false;
 
+    if (!RecalculateLoopDepth(graph))
+        return false;
+    // No spew: graph not changed.
+
+    if (mir->shouldCancel("Recalculate Loop Depth"))
+        return false;
+
+    if (!ReorderBlocks(graph))
+        return false;
+    // No spew: wait for right block numbers
+
+    if (mir->shouldCancel("ReorderBlocks"))
+        return false;
+
     if (!RenumberBlocks(graph))
         return false;
     IonSpewPass("Renumber Blocks");
     AssertGraphCoherency(graph);
 
     if (mir->shouldCancel("Renumber Blocks"))
         return false;
 
--- a/js/src/ion/IonAnalysis.cpp
+++ b/js/src/ion/IonAnalysis.cpp
@@ -618,16 +618,220 @@ ion::ApplyTypeInformation(MIRGenerator *
     TypeAnalyzer analyzer(mir, graph);
 
     if (!analyzer.analyze())
         return false;
 
     return true;
 }
 
+static bool
+SetLoopDepth(MBasicBlock *header)
+{
+    size_t depth = header->loopDepth() + 1;
+
+    Vector<MBasicBlock *, 1, IonAllocPolicy> worklist;
+    worklist.append(header->backedge());
+
+    // Iterate over all blocks that are in a path from backedge to the loopheader.
+    while (!worklist.empty()) {
+        MBasicBlock *block = worklist.popCopy();
+        block->setLoopDepth(depth);
+        if (block == header)
+            continue;
+
+        for (size_t i = 0; i < block->numPredecessors(); i++) {
+            MBasicBlock *pred = block->getPredecessor(i);
+            if (pred->loopDepth() == depth)
+                continue;
+
+            if (!worklist.append(pred))
+                return false;
+        }
+    }
+
+    return true;
+}
+
+bool
+ion::RecalculateLoopDepth(MIRGraph &graph)
+{
+    // Recalculate the loop depth information.
+    //
+    // The definition of a loop (important to correctly reorder blocks and for LICM) is:
+    // all blocks reached when creating a path from the loop backedge to the loopheader.
+    // This information differs from the loopdepth information gathered in IonBuilder.
+    // In IonBuilder blocks that are placed inside the loop are considered to be part of the loop.
+    // E.g.:
+    // for (...) {
+    //
+    //   if (...) {
+    //      return;
+    //   }
+    // }
+    // IonBuilder will consider the content of the conditional to be part of the loop.
+    // As of this pass/call this block won't be part of the loop anymore.
+
+
+    // Reset all loopdepth information
+    for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++)
+        (*block)->setLoopDepth(0);
+
+    // Iterate through graph for loopheaders
+    // The graph isn't in RPO order yet. Therefore we need to iterate differently.
+    // In order to iterate correctly we only need to make sure we see the loopheader
+    // of outer loops, before the loopheader of an innerloop.
+    // This is guarenteed if we walk just by following the successors,
+    // since we can't enter a loopbody before seeing the loopheader.
+    // Here we do DFS.
+    Vector<MBasicBlock *, 1, IonAllocPolicy> worklist;
+    if (!worklist.append(graph.entryBlock()))
+        return false;
+
+    JS_ASSERT(!graph.entryBlock()->isLoopHeader());
+    while (!worklist.empty()) {
+        MBasicBlock *block = worklist.back();
+
+        // Add not yet visited successors to the worklist.
+        for (size_t i = 0; i < block->numSuccessors(); i++) {
+            MBasicBlock *succ = block->getSuccessor(i);
+            if (!succ->isMarked()) {
+                if (!worklist.append(succ))
+                    return false;
+                succ->mark();
+
+                // Set the loopdepth correctly.
+                if (succ->isLoopHeader()) {
+                    if (!SetLoopDepth(succ))
+                        return false;
+                }
+            }
+        }
+
+        // If any blocks were added, process them first.
+        if (block != worklist.back())
+            continue;
+
+        // All successors of this block are visited.
+        worklist.popBack();
+    }
+
+    graph.unmarkBlocks();
+
+    return true;
+}
+
+static void
+SortByLoopDepth(InlineList<MBasicBlock> &pending, MBasicBlockIterator from)
+{
+    // Sort the blocks between "from" and the end of the pending list.
+    // In almost all cases this list will contain at max 2 items (except for tableswitch).
+    // Therefore no need for a fancy algorithm.
+
+    MBasicBlockIterator end = pending.end();
+    while (from != end) {
+        MBasicBlockIterator current(from);
+        MBasicBlock *max = *current;
+        while (current != end) {
+            if (current->loopDepth() > max->loopDepth())
+                max = *current;
+            current++;
+        }
+        if (max != *from) {
+            pending.remove(max);
+            pending.insertBefore(*from, max);
+        }
+        from++;
+    }
+}
+
+bool
+ion::ReorderBlocks(MIRGraph &graph)
+{
+    // The blocks get reordered to be in RPO (they are already).
+    // The order will be improved by adding an extra constrain:
+    // when deciding which successor to visit, always start with the one with lowest loopdepth.
+    // Consequences:
+    // => blocks with the same loopdepth are closer (=> tighter loops)
+    // => loop backedges and loop headers aren't interleaved when visiting
+    //    the graph in RPO (important for Alias Analysis)
+
+    // The RPO algorithm works as following.
+    // It has a stack (pending) and we put the successors on there.
+    // The last item on the stack is the one we are looking too.
+    // If it still has unmarked successsors those get added and there is a new last item.
+    // If there are no unmarked successors anymore, all successors are processed
+    // and this block can get popped from the stack and added to the graph.
+
+    mozilla::DebugOnly<size_t> numBlocks = graph.numBlocks();
+
+    InlineList<MBasicBlock> pending;
+    MBasicBlock *entry = graph.entryBlock();
+    MBasicBlock *osr = graph.osrBlock();
+    graph.clearBlockList();
+
+    // Start with entry block
+    pending.pushBack(entry);
+    entry->mark();
+
+    // Iterate all blocks to put the blocks in PostOrder to the graph,
+    // reversing happens by using moveBlockToBegin.
+    while (!pending.empty()) {
+        MBasicBlock *block = pending.peekBack();
+        bool sortSuccessors = false;
+
+        // Add not yet visited successors to the pending list.
+        for (size_t i = 0; i < block->numSuccessors(); i++) {
+            MBasicBlock *succ = block->getSuccessor(i);
+            if (!succ->isMarked()) {
+                pending.pushBack(succ);
+                succ->mark();
+
+                // Only request sorting, when there are different loopDepths.
+                if (succ->loopDepth() != block->loopDepth())
+                    sortSuccessors = true;
+            }
+        }
+
+        // Test if there was a new block added
+        if (block != pending.peekBack()) {
+            // Sort the blocks if needed
+            if (sortSuccessors) {
+                MBasicBlockIterator start = pending.begin(block);
+                start++;
+                SortByLoopDepth(pending, start);
+            }
+            continue;
+        }
+
+        // Here we are sure all successors of this block have been added to the graph.
+        // Now this block can get added to the graph.
+        pending.popBack();
+        graph.addBlock(block);
+        graph.moveBlockToBegin(block);
+    }
+
+    // Put the osr block in the second place
+    if (osr) {
+        graph.addBlock(osr);
+        graph.moveBlockToBegin(osr);
+        graph.moveBlockToBegin(entry);
+    }
+
+    graph.unmarkBlocks();
+
+    JS_ASSERT(graph.numBlocks() == numBlocks);
+
+#ifdef DEBUG
+    graph.setInRPO();
+#endif
+
+    return true;
+}
+
 bool
 ion::RenumberBlocks(MIRGraph &graph)
 {
     size_t id = 0;
     for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); block++)
         block->setId(id++);
 
     return true;
--- a/js/src/ion/IonAnalysis.h
+++ b/js/src/ion/IonAnalysis.h
@@ -35,16 +35,22 @@ EliminateDeadResumePointOperands(MIRGene
 
 bool
 EliminateDeadCode(MIRGenerator *mir, MIRGraph &graph);
 
 bool
 ApplyTypeInformation(MIRGenerator *mir, MIRGraph &graph);
 
 bool
+RecalculateLoopDepth(MIRGraph &graph);
+
+bool
+ReorderBlocks(MIRGraph &graph);
+
+bool
 RenumberBlocks(MIRGraph &graph);
 
 bool
 BuildDominatorTree(MIRGraph &graph);
 
 bool
 BuildPhiReverseMapping(MIRGraph &graph);
 
--- a/js/src/ion/IonBuilder.cpp
+++ b/js/src/ion/IonBuilder.cpp
@@ -1260,32 +1260,30 @@ IonBuilder::processIfEnd(CFGState &state
         // could have already ended the block.
         current->end(MGoto::New(state.branch.ifFalse));
 
         if (!state.branch.ifFalse->addPredecessor(current))
             return ControlStatus_Error;
     }
 
     current = state.branch.ifFalse;
-    graph().moveBlockToEnd(current);
     pc = current->pc();
     return ControlStatus_Joined;
 }
 
 IonBuilder::ControlStatus
 IonBuilder::processIfElseTrueEnd(CFGState &state)
 {
     // We've reached the end of the true branch of an if-else. Don't
     // create an edge yet, just transition to parsing the false branch.
     state.state = CFGState::IF_ELSE_FALSE;
     state.branch.ifTrue = current;
     state.stopAt = state.branch.falseEnd;
     pc = state.branch.ifFalse->pc();
     current = state.branch.ifFalse;
-    graph().moveBlockToEnd(current);
     return ControlStatus_Jumped;
 }
 
 IonBuilder::ControlStatus
 IonBuilder::processIfElseFalseEnd(CFGState &state)
 {
     // Update the state to have the latest block from the false path.
     state.branch.ifFalse = current;
@@ -1334,20 +1332,17 @@ IonBuilder::processBrokenLoop(CFGState &
         if (i->loopDepth() > loopDepth_)
             i->setLoopDepth(i->loopDepth() - 1);
     }
 
     // If the loop started with a condition (while/for) then even if the
     // structure never actually loops, the condition itself can still fail and
     // thus we must resume at the successor, if one exists.
     current = state.loop.successor;
-    if (current) {
-        JS_ASSERT(current->loopDepth() == loopDepth_);
-        graph().moveBlockToEnd(current);
-    }
+    JS_ASSERT_IF(current, current->loopDepth() == loopDepth_);
 
     // Join the breaks together and continue parsing.
     if (state.loop.breaks) {
         MBasicBlock *block = createBreakCatchBlock(state.loop.breaks, state.loop.exitpc);
         if (!block)
             return ControlStatus_Error;
 
         if (current) {
@@ -1379,20 +1374,18 @@ IonBuilder::finishLoop(CFGState &state, 
     JS_ASSERT(loopDepth_);
     loopDepth_--;
     JS_ASSERT_IF(successor, successor->loopDepth() == loopDepth_);
 
     // Compute phis in the loop header and propagate them throughout the loop,
     // including the successor.
     if (!state.loop.entry->setBackedge(current))
         return ControlStatus_Error;
-    if (successor) {
-        graph().moveBlockToEnd(successor);
+    if (successor)
         successor->inheritPhis(state.loop.entry);
-    }
 
     if (state.loop.breaks) {
         // Propagate phis placed in the header to individual break exit points.
         DeferredEdge *edge = state.loop.breaks;
         while (edge) {
             edge->block->inheritPhis(state.loop.entry);
             edge = edge->next;
         }
@@ -1637,19 +1630,16 @@ IonBuilder::processNextTableSwitchCase(C
     // Add current block as predecessor if available.
     // This means the previous case didn't have a break statement.
     // So flow will continue in this block.
     if (current) {
         current->end(MGoto::New(successor));
         successor->addPredecessor(current);
     }
 
-    // Insert successor after the current block, to maintain RPO.
-    graph().moveBlockToEnd(successor);
-
     // If this is the last successor the block should stop at the end of the tableswitch
     // Else it should stop at the start of the next successor
     if (state.tableswitch.currentBlock+1 < state.tableswitch.ins->numBlocks())
         state.stopAt = state.tableswitch.ins->getBlock(state.tableswitch.currentBlock+1)->pc();
     else
         state.stopAt = state.tableswitch.exitpc;
 
     current = successor;
@@ -1663,17 +1653,16 @@ IonBuilder::processAndOrEnd(CFGState &st
     // We just processed the RHS of an && or || expression.
     // Now jump to the join point (the false block).
     current->end(MGoto::New(state.branch.ifFalse));
 
     if (!state.branch.ifFalse->addPredecessor(current))
         return ControlStatus_Error;
 
     current = state.branch.ifFalse;
-    graph().moveBlockToEnd(current);
     pc = current->pc();
     return ControlStatus_Joined;
 }
 
 IonBuilder::ControlStatus
 IonBuilder::processLabelEnd(CFGState &state)
 {
     JS_ASSERT(state.state == CFGState::LABEL);
@@ -2210,19 +2199,16 @@ IonBuilder::tableSwitch(JSOp op, jssrcno
         // If this is an actual case (not filled gap),
         // add this block to the list that still needs to get processed
         if (casepc != pc)
             tableswitch->addBlock(caseblock);
 
         pc2 += JUMP_OFFSET_LEN;
     }
 
-    // Move defaultcase to the end, to maintain RPO.
-    graph().moveBlockToEnd(defaultcase);
-
     JS_ASSERT(tableswitch->numCases() == (uint32_t)(high - low + 1));
     JS_ASSERT(tableswitch->numSuccessors() > 0);
 
     // Sort the list of blocks that still needs to get processed by pc
     qsort(tableswitch->blocks(), tableswitch->numBlocks(),
           sizeof(MBasicBlock*), CmpSuccessors);
 
     // Create info
@@ -2538,19 +2524,16 @@ IonBuilder::processCondSwitchBody(CFGSta
         JS_ASSERT_IF(current, pc == state.condswitch.exitpc);
         return processSwitchEnd(state.condswitch.breaks, state.condswitch.exitpc);
     }
 
     // Get the next body
     MBasicBlock *nextBody = bodies[currentIdx++];
     JS_ASSERT_IF(current, pc == nextBody->pc());
 
-    // Fix the reverse post-order iteration.
-    graph().moveBlockToEnd(nextBody);
-
     // The last body continue into the new one.
     if (current) {
         current->end(MGoto::New(nextBody));
         nextBody->addPredecessor(current);
     }
 
     // Continue in the next body.
     current = nextBody;
@@ -3864,17 +3847,16 @@ IonBuilder::inlineCalls(CallInfo &callIn
 
     // Finally add the dispatch instruction.
     // This must be done at the end so that add() may be called above.
     dispatchBlock->end(dispatch);
 
     // Check the depth change: +1 for retval
     JS_ASSERT(returnBlock->stackDepth() == dispatchBlock->stackDepth() - callInfo.numFormals() + 1);
 
-    graph().moveBlockToEnd(returnBlock);
     current = returnBlock;
     return true;
 }
 
 MInstruction *
 IonBuilder::createDeclEnvObject(MDefinition *callee, MDefinition *scope)
 {
     // Create a template CallObject that we'll use to generate inline object
--- a/js/src/ion/MIRGraph.h
+++ b/js/src/ion/MIRGraph.h
@@ -477,25 +477,33 @@ class MIRGraph
     MBasicBlock *osrBlock_;
     MStart *osrStart_;
 
     // List of compiled/inlined scripts.
     Vector<RawScript, 4, IonAllocPolicy> scripts_;
 
     size_t numBlocks_;
 
+#ifdef DEBUG
+    // Is the graph in Reverse Post Order
+    bool inRPO_;
+#endif
+
   public:
     MIRGraph(TempAllocator *alloc)
       : alloc_(alloc),
         exitAccumulator_(NULL),
         blockIdGen_(0),
         idGen_(0),
         osrBlock_(NULL),
         osrStart_(NULL),
         numBlocks_(0)
+#ifdef DEBUG
+        , inRPO_(false)
+#endif
     { }
 
     template <typename T>
     T * allocate(size_t count = 1) {
         return reinterpret_cast<T *>(alloc_->allocate(sizeof(T) * count));
     }
 
     void addBlock(MBasicBlock *block);
@@ -534,35 +542,38 @@ class MIRGraph
     }
     MBasicBlockIterator begin(MBasicBlock *at) {
         return blocks_.begin(at);
     }
     MBasicBlockIterator end() {
         return blocks_.end();
     }
     PostorderIterator poBegin() {
+        JS_ASSERT(inRPO_);
         return blocks_.rbegin();
     }
     PostorderIterator poEnd() {
+        JS_ASSERT(inRPO_);
         return blocks_.rend();
     }
     ReversePostorderIterator rpoBegin() {
+        JS_ASSERT(inRPO_);
         return blocks_.begin();
     }
     ReversePostorderIterator rpoEnd() {
+        JS_ASSERT(inRPO_);
         return blocks_.end();
     }
     void removeBlock(MBasicBlock *block) {
         blocks_.remove(block);
         numBlocks_--;
     }
-    void moveBlockToEnd(MBasicBlock *block) {
-        JS_ASSERT(block->id());
+    void moveBlockToBegin(MBasicBlock *block) {
         blocks_.remove(block);
-        blocks_.pushBack(block);
+        blocks_.pushFront(block);
     }
     size_t numBlocks() const {
         return numBlocks_;
     }
     uint32_t numBlockIds() const {
         return blockIdGen_;
     }
     void allocDefinitionId(MDefinition *ins) {
@@ -607,16 +618,22 @@ class MIRGraph
     }
     size_t numScripts() const {
         return scripts_.length();
     }
     JSScript **scripts() {
         return scripts_.begin();
     }
 
+#ifdef DEBUG
+    void setInRPO() {
+        inRPO_ = true;
+    }
+#endif
+
     // The ParSlice is an instance of ForkJoinSlice*, it carries
     // "per-helper-thread" information.  So as not to modify the
     // calling convention for parallel code, we obtain the current
     // slice from thread-local storage.  This helper method will
     // lazilly insert an MParSlice instruction in the entry block and
     // return the definition.
     MDefinition *parSlice();
 };