V4 IR: change block scheduling algorithm from recursive to iterative.

This makes time- and memory-complexity a lot better when compiling
big JavaScript functions.

Change-Id: I2a7cb9b5979844254747fa5cf7355cca0b113904
Reviewed-by: Fawzi Mohamed <fawzi.mohamed@digia.com>

1 files changed, 189 insertions, 102 deletions

diff --git a/src/qml/compiler/qv4ssa.cpp b/src/qml/compiler/qv4ssa.cpp
index 4fee3c04a0..b3eb6835df 100644
--- a/src/qml/compiler/qv4ssa.cpp
+++ b/src/qml/compiler/qv4ssa.cpp
@@ -213,6 +213,32 @@ void showMeTheCode(Function *function)
     }
 }
 
+class ProcessedBlocks
+{
+    QBitArray processed;
+
+public:
+    ProcessedBlocks(const QVector<BasicBlock *> allBlocks)
+    {
+        int maxBB = 0;
+        foreach (BasicBlock *bb, allBlocks)
+            maxBB = qMax(maxBB, bb->index);
+        processed = QBitArray(maxBB + 1, false);
+    }
+
+    bool alreadyProcessed(BasicBlock *bb) const
+    {
+        Q_ASSERT(bb);
+
+        return processed.at(bb->index);
+    }
+
+    void markAsProcessed(BasicBlock *bb)
+    {
+        processed.setBit(bb->index);
+    }
+};
+
 inline Temp *unescapableTemp(Expr *e, bool variablesCanEscape)
 {
     Temp *t = e->asTemp();
@@ -369,15 +395,6 @@ class DominatorTree {
 #endif // SHOW_SSA
     }
 
-    bool dominates(BasicBlock *dominator, BasicBlock *dominated) const {
-        for (BasicBlock *it = dominated; it; it = idom[it]) {
-            if (it == dominator)
-                return true;
-        }
-
-        return false;
-    }
-
     struct NodeProgress {
         QSet<BasicBlock *> children;
         QSet<BasicBlock *> todo;
@@ -490,6 +507,15 @@ public:
     BasicBlock *immediateDominator(BasicBlock *bb) const {
         return idom[bb];
     }
+
+    bool dominates(BasicBlock *dominator, BasicBlock *dominated) const {
+        for (BasicBlock *it = dominated; it; it = idom[it]) {
+            if (it == dominator)
+                return true;
+        }
+
+        return false;
+    }
 };
 
 class VariableCollector: public StmtVisitor, ExprVisitor {
@@ -720,19 +746,7 @@ class VariableRenamer: public StmtVisitor, public ExprVisitor
     enum { Absent = -1 };
     Mapping localMapping;
     Mapping vregMapping;
-    QBitArray processed;
-
-    bool alreadyProcessed(BasicBlock *bb) const
-    {
-        Q_ASSERT(bb);
-
-        return processed.at(bb->index);
-    }
-
-    void markAsProcessed(BasicBlock *bb)
-    {
-        processed.setBit(bb->index);
-    }
+    ProcessedBlocks processed;
 
     bool isRenamable(Temp *t) const
     {
@@ -796,11 +810,8 @@ public:
         : function(f)
         , variablesCanEscape(f->variablesCanEscape())
         , tempCount(0)
+        , processed(f->basicBlocks)
     {
-        int maxBB = 0;
-        foreach (BasicBlock *bb, f->basicBlocks)
-            maxBB = qMax(maxBB, bb->index);
-        processed = QBitArray(maxBB + 1, false);
     }
 
     void run() {
@@ -840,13 +851,13 @@ private:
 
     void rename(BasicBlock *bb)
     {
-        while (bb && !alreadyProcessed(bb)) {
+        while (bb && !processed.alreadyProcessed(bb)) {
             renameStatementsAndPhis(bb);
-            markAsProcessed(bb);
+            processed.markAsProcessed(bb);
 
             BasicBlock *next = 0;
             foreach (BasicBlock *out, bb->out) {
-                if (alreadyProcessed(out))
+                if (processed.alreadyProcessed(out))
                     continue;
                 if (!next)
                     next = out;
@@ -2251,13 +2262,16 @@ void splitCriticalEdges(Function *f)
             for (int inIdx = 0, eInIdx = bb->in.size(); inIdx != eInIdx; ++inIdx) {
                 BasicBlock *inBB = bb->in[inIdx];
                 if (inBB->out.size() > 1) { // this should have been split!
+                    int newIndex = f->basicBlocks.last()->index + 1;
 #if defined(SHOW_SSA)
-                    qDebug() << "Splitting edge from block" << inBB->index << "to block" << bb->index;
+                    qDebug() << "Splitting edge from block" << inBB->index << "to block" << bb->index << "by introducing block" << newIndex;
 #endif
 
+                    BasicBlock *containingGroup = inBB->isGroupStart() ? inBB : inBB->containingGroup();
+
                     // create the basic block:
-                    BasicBlock *newBB = new BasicBlock(f, bb->containingGroup(), bb->catchBlock);
-                    newBB->index = f->basicBlocks.last()->index + 1;
+                    BasicBlock *newBB = new BasicBlock(f, containingGroup, bb->catchBlock);
+                    newBB->index = newIndex;
                     f->basicBlocks.append(newBB);
                     Jump *s = f->New<Jump>();
                     s->init(bb);
@@ -2293,84 +2307,153 @@ void splitCriticalEdges(Function *f)
     }
 }
 
-QHash<BasicBlock *, BasicBlock *> scheduleBlocks(Function *function, const DominatorTree &df)
+// High-level algorithm:
+//  0. start with the first node (the start node) of a function
+//  1. emit the node
+//  2. add all outgoing edges that are not yet emitted to the postponed stack
+//  3. When the postponed stack is empty, pop a stack from the loop stack. If that is empty too,
+//     we're done.
+//  4. pop a node from the postponed stack, and check if it can be scheduled:
+//     a. if all incoming edges are scheduled, go to 4.
+//     b. if an incoming edge is unscheduled, but it's a back-edge (an edge in a loop that jumps
+//        back to the start of the loop), ignore it
+//     c. if there is any unscheduled edge that is not a back-edge, ignore this node, and go to 4.
+//  5. if this node is the start of a loop, push the postponed stack on the loop stack.
+//  6. go back to 1.
+//
+// The postponing action in step 2 will put the node into its containing group. The case where this
+// is important is when a (labeled) continue or a (labeled) break statement occur in a loop: the
+// outgoing edge points to a node that is not part of the current loop (and possibly not of the
+// parent loop).
+//
+// Linear scan register allocation benefits greatly from short life-time intervals with few holes
+// (see for example section 4 (Lifetime Analysis) of [Wimmer1]). This algorithm makes sure that the
+// blocks of a group are scheduled together, with no non-loop blocks in between. This applies
+// recursively for nested loops. It also schedules groups of if-then-else-endif blocks together for
+// the smae reason.
+class BlockScheduler
 {
-    struct I {
-        const DominatorTree &df;
-        QHash<BasicBlock *, BasicBlock *> &startEndLoops;
-        QSet<BasicBlock *> visited;
-        QVector<BasicBlock *> &sequence;
-        BasicBlock *currentGroup;
-        QSet<BasicBlock *> postponed;
-
-        I(const DominatorTree &df, QVector<BasicBlock *> &sequence,
-          QHash<BasicBlock *, BasicBlock *> &startEndLoops)
-            : df(df)
-            , startEndLoops(startEndLoops)
-            , sequence(sequence)
-            , currentGroup(0)
-        {}
+    Function *function;
+    const DominatorTree &dominatorTree;
 
-        void DFS(BasicBlock *bb) {
-            Q_ASSERT(bb);
-            if (visited.contains(bb))
-                return;
+    struct WorkForGroup
+    {
+        BasicBlock *group;
+        QStack<BasicBlock *> postponed;
 
-            if (bb->containingGroup() != currentGroup) {
-                postponed.insert(bb);
-                return;
-            }
-            if (bb->isGroupStart())
-                currentGroup = bb;
-            else if (bb->in.size() > 1)
-                foreach (BasicBlock *inBB, bb->in)
-                    if (!visited.contains(inBB))
-                        return;
-
-            Q_ASSERT(df.immediateDominator(bb) == 0 || sequence.contains(df.immediateDominator(bb)));
-            layout(bb);
-            if (Stmt *terminator = bb->terminator()) {
-                if (Jump *j = terminator->asJump()) {
-                    Q_ASSERT(bb->out.size() == 1);
-                    DFS(j->target);
-                } else if (CJump *cj = terminator->asCJump()) {
-                    Q_ASSERT(bb->out.size() == 2);
-                    DFS(cj->iftrue);
-                    DFS(cj->iffalse);
-                } else if (terminator->asRet()) {
-                    Q_ASSERT(bb->out.size() == 0);
-                    // nothing to do.
-                } else {
-                    Q_UNREACHABLE();
-                }
-            } else {
-                Q_UNREACHABLE();
+        WorkForGroup(BasicBlock *group = 0): group(group) {}
+    };
+    WorkForGroup currentGroup;
+    QStack<WorkForGroup> postponedGroups;
+    QVector<BasicBlock *> sequence;
+    ProcessedBlocks emitted;
+    QHash<BasicBlock *, BasicBlock *> loopsStartEnd;
+
+    bool checkCandidate(BasicBlock *candidate)
+    {
+        Q_ASSERT(candidate->containingGroup() == currentGroup.group);
+
+        foreach (BasicBlock *in, candidate->in) {
+            if (emitted.alreadyProcessed(in))
+                continue;
+
+            // this is a loop, where there in -> candidate edge is the jump back to the top of the loop.
+            if (dominatorTree.dominates(candidate, in))
+                continue;
+
+            return false; // an incoming edge that is not yet emitted, and is not a back-edge
+        }
+
+        // postpone everything, and schedule the loop first.
+        if (candidate->isGroupStart()) {
+            postponedGroups.push(currentGroup);
+            currentGroup = WorkForGroup(candidate);
+        }
+
+        return true;
+    }
+
+    BasicBlock *pickNext()
+    {
+        while (true) {
+            while (currentGroup.postponed.isEmpty()) {
+                if (postponedGroups.isEmpty())
+                    return 0;
+                if (currentGroup.group) // record the first and the last node of a group
+                    loopsStartEnd.insert(currentGroup.group, sequence.last());
+                currentGroup = postponedGroups.pop();
             }
 
-            if (bb->isGroupStart()) {
-                currentGroup = bb->containingGroup();
-                startEndLoops.insert(bb, sequence.last());
-                QSet<BasicBlock *> p = postponed;
-                foreach (BasicBlock *pBB, p)
-                    DFS(pBB);
+            BasicBlock *next = currentGroup.postponed.pop();
+            if (checkCandidate(next))
+                return next;
+        }
+
+        return 0;
+    }
+
+    void emitBlock(BasicBlock *bb)
+    {
+        if (emitted.alreadyProcessed(bb))
+            return;
+
+        sequence.append(bb);
+        emitted.markAsProcessed(bb);
+    }
+
+    void schedule(BasicBlock *functionEntryPoint)
+    {
+        BasicBlock *next = functionEntryPoint;
+
+        while (next) {
+            emitBlock(next);
+            for (int i = next->out.size(); i != 0; ) {
+                // postpone all outgoing edges, if they were not already processed
+                --i;
+                BasicBlock *out = next->out[i];
+                if (!emitted.alreadyProcessed(out))
+                    postpone(out);
             }
+            next = pickNext();
         }
+    }
 
-        void layout(BasicBlock *bb) {
-            sequence.append(bb);
-            visited.insert(bb);
-            postponed.remove(bb);
+    void postpone(BasicBlock *bb)
+    {
+        if (currentGroup.group == bb->containingGroup()) {
+            currentGroup.postponed.append(bb);
+            return;
         }
-    };
 
-    QVector<BasicBlock *> sequence;
-    sequence.reserve(function->basicBlocks.size());
-    QHash<BasicBlock *, BasicBlock *> startEndLoops;
-    I(df, sequence, startEndLoops).DFS(function->basicBlocks.first());
-    qSwap(function->basicBlocks, sequence);
+        for (int i = postponedGroups.size(); i != 0; ) {
+            --i;
+            WorkForGroup &g = postponedGroups[i];
+            if (g.group == bb->containingGroup()) {
+                g.postponed.append(bb);
+                return;
+            }
+        }
 
-    return startEndLoops;
-}
+        Q_UNREACHABLE();
+    }
+
+public:
+    BlockScheduler(Function *function, const DominatorTree &dominatorTree)
+        : function(function)
+        , dominatorTree(dominatorTree)
+        , emitted(function->basicBlocks)
+    {}
+
+    QHash<BasicBlock *, BasicBlock *> go()
+    {
+        showMeTheCode(function);
+        schedule(function->basicBlocks.first());
+
+        Q_ASSERT(function->basicBlocks.size() == sequence.size());
+        function->basicBlocks = sequence;
+        return loopsStartEnd;
+    }
+};
 
 #ifndef QT_NO_DEBUG
 void checkCriticalEdges(QVector<BasicBlock *> basicBlocks) {
@@ -3393,11 +3476,11 @@ void Optimizer::run(QQmlEnginePrivate *qmlEngine)
         // block scheduling, so remove those now.
 //        qout << "Cleaning up unreachable basic blocks..." << endl;
         cleanupBasicBlocks(function, false);
-//        showMeTheCode(function);
+        showMeTheCode(function);
 
 //        qout << "Doing block scheduling..." << endl;
-        startEndLoops = scheduleBlocks(function, df);
-//        showMeTheCode(function);
+        startEndLoops = BlockScheduler(function, df).go();
+        showMeTheCode(function);
 
 #ifndef QT_NO_DEBUG
         checkCriticalEdges(function->basicBlocks);
@@ -3663,3 +3746,7 @@ MoveMapping::Action MoveMapping::schedule(const Move &m, QList<Move> &todo, QLis
     output.append(m);
     return NormalMove;
 }
+
+// References:
+//  [Wimmer1] C. Wimmer and M. Franz. Linear Scan Register Allocation on SSA Form. In Proceedings of
+//            CGO’10, ACM Press, 2010