Fix move ordering while resolving edges in register allocation

When register allocation on an IR in SSA form is done, the last step is
to turn the Phi nodes into moves and swaps and put those instructions in
the predecessors. As the Phi nodes are conceptually "executed in
parallel", this can result in cycles:
  r1 <- r0
  r0 <- r1
These have to be turned into a swap instruction. Also, the moves have to
be ordered in order to make sure that no values are overwritten:
  r1 <- r0
  r2 <- r1
Here the two moves need to be switched. The comments in the code
document the algorithm.

Change-Id: I4151988681f7554b00a3eb70d224e6e2f29ebf04
Reviewed-by: Simon Hausmann <simon.hausmann@qt.io>

4 files changed, 104 insertions, 67 deletions

diff --git a/src/qml/compiler/qv4jsir_p.h b/src/qml/compiler/qv4jsir_p.h
index 73aa6c4975..a614d3fe1c 100644
--- a/src/qml/compiler/qv4jsir_p.h
+++ b/src/qml/compiler/qv4jsir_p.h
@@ -507,6 +507,16 @@ struct Q_AUTOTEST_EXPORT Temp: Expr {
         , memberResolver(0)
     {}
 
+    Temp(Type type, Kind kind, unsigned index)
+        : Expr(TempExpr)
+        , index(index)
+        , isReadOnly(0)
+        , kind(kind)
+        , memberResolver(0)
+    {
+        this->type = type;
+    }
+
     void init(unsigned kind, unsigned index)
     {
         this->index = index;
diff --git a/src/qml/compiler/qv4ssa.cpp b/src/qml/compiler/qv4ssa.cpp
index 220bdc10b4..45ca56584f 100644
--- a/src/qml/compiler/qv4ssa.cpp
+++ b/src/qml/compiler/qv4ssa.cpp
@@ -5646,25 +5646,97 @@ void MoveMapping::add(Expr *from, Temp *to) {
     _moves.append(m);
 }
 
+// Order the moves that are generated when resolving edges during register allocation (see [Wimmer1]
+// section 6 for details). Now these moves form one or more graphs, so we have to output them in
+// such an order that values don't get overwritten:
+//   r1 <- r0
+//   r2 <- r1
+// That input has to be ordered as follows in order to prevent the value in r1 from being lost:
+//   r2 <- r1
+//   r1 <- r0
+//
+// So, the algorithm is to output the leaves first, and take them out of the input. This will result
+// in some moves to become leaves (in the above example: when leaf r2 <- r1 is generated and taken
+// away, the r1 <- r0 is now a leaf), so we can output those and take those out, and repeat until
+// there are no more leafs.
+//
+// The tricky part is that there might be cycles:
+//   r4 <- r5
+//   r5 <- r4
+// These have to be turned into a "register swap":
+//   r4 <=> r5
+//
+// So after running the above algorithm where we progressively remove the leaves, we are left with
+// zero or more cycles. To resolve those, we break one of the edges of the cycle, and for all other
+// edges we generate swaps. Note that the swaps will always occur as the last couple of moves,
+// because otherwise they might clobber sources for moves:
+//   r4 <=> r5
+//   r6 <- r5
+// Here, the value of r5 is already overwritten with the one in r4, so the correct order is:
+//   r6 <- r5
+//   r4 <=> r5
 void MoveMapping::order()
 {
-    QList<Move> todo = _moves;
-    QList<Move> output, swaps;
+    QList<Move> output;
     output.reserve(_moves.size());
-    QList<Move> delayed;
-    delayed.reserve(_moves.size());
 
-    while (!todo.isEmpty()) {
-        const Move m = todo.first();
-        todo.removeFirst();
-        schedule(m, todo, delayed, output, swaps);
-    }
+    while (!_moves.isEmpty()) {
+        // Take out all leaf edges, because we can output them without any problems.
+        int nextLeaf = findLeaf();
+        if (nextLeaf == -1)
+            break; // No more leafs left, we're done here.
+        output.append(_moves.takeAt(nextLeaf));
+        // Now there might be new leaf edges: any move that had the input of the previously found
+        // leaf as an output, so loop around.
+    }
+
+    while (!_moves.isEmpty()) {
+        // We're now left with one or more cycles.
+        // Step one: break the/a cycle.
+        _moves.removeFirst();
+        // Step two: find the other edges of the cycle, starting with the one of that is now a leaf.
+        while (!_moves.isEmpty()) {
+            int nextLeaf = findLeaf();
+            if (nextLeaf == -1)
+                break; // We're done with this cycle.
+            Move m = _moves.takeAt(nextLeaf);
+            // Step three: get the edges from the cycle and turn it into a swap
+            m.needsSwap = true;
+            output.append(m);
+            // Because we took out a leaf, find the next one.
+        }
+        // We're done with the cycle, let's see if there are more.
+    }
+
+    _moves = output;
+}
 
-    output += swaps;
+int MoveMapping::findLeaf() const
+{
+    for (int i = 0, e = _moves.size(); i != e; ++i) {
+        // Take an edge from the list...
+        const Temp *target = _moves.at(i).to;
+        // ... and see if its target is used as a source...
+        bool targetUsedAsSource = false;
+        for (int j = 0; j != e; ++j) {
+            if (i == j)
+                continue;
 
-    Q_ASSERT(todo.isEmpty());
-    Q_ASSERT(delayed.isEmpty());
-    qSwap(_moves, output);
+            Expr *source = _moves.at(j).from;
+            if (const Temp *sourceTemp = source->asTemp()) {
+                if (overlappingStorage(*target, *sourceTemp)) {
+                    targetUsedAsSource = true;
+                    break;
+                }
+            }
+        }
+        // ... if not, we have a leaf edge ...
+        if (!targetUsedAsSource)
+            return i;
+        // .. otherwise we try the next one.
+    }
+
+    return -1; // No leaf found
 }
 
 QList<IR::Move *> MoveMapping::insertMoves(BasicBlock *bb, IR::Function *function, bool atEnd) const
@@ -5706,54 +5778,6 @@ void MoveMapping::dump() const
     }
 }
 
-MoveMapping::Action MoveMapping::schedule(const Move &m, QList<Move> &todo, QList<Move> &delayed,
-                                          QList<Move> &output, QList<Move> &swaps) const
-{
-    Moves usages = sourceUsages(m.to, todo) + sourceUsages(m.to, delayed);
-    foreach (const Move &dependency, usages) {
-        if (!output.contains(dependency)) {
-            if (delayed.contains(dependency)) {
-                // We have a cycle! Break it by swapping instead of assigning.
-                if (DebugMoveMapping) {
-                    delayed += m;
-                    QBuffer buf;
-                    buf.open(QIODevice::WriteOnly);
-                    QTextStream out(&buf);
-                    IRPrinter printer(&out);
-                    out<<"we have a cycle! temps:" << endl;
-                    foreach (const Move &m, delayed) {
-                        out<<"\t";
-                        printer.print(m.to);
-                        out<<" <- ";
-                        printer.print(m.from);
-                        out<<endl;
-                    }
-                    qDebug("%s", buf.data().constData());
-                    delayed.removeOne(m);
-                }
-
-                return NeedsSwap;
-            } else {
-                delayed.append(m);
-                todo.removeOne(dependency);
-                Action action = schedule(dependency, todo, delayed, output, swaps);
-                delayed.removeOne(m);
-                Move mm(m);
-                if (action == NeedsSwap) {
-                    mm.needsSwap = true;
-                    swaps.append(mm);
-                } else {
-                    output.append(mm);
-                }
-                return action;
-            }
-        }
-    }
-
-    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
diff --git a/src/qml/compiler/qv4ssa_p.h b/src/qml/compiler/qv4ssa_p.h
index 3a787f0347..977739e5d2 100644
--- a/src/qml/compiler/qv4ssa_p.h
+++ b/src/qml/compiler/qv4ssa_p.h
@@ -256,15 +256,18 @@ private:
     QHash<BasicBlock *, BasicBlock *> startEndLoops;
 };
 
-class MoveMapping
+class Q_AUTOTEST_EXPORT MoveMapping
 {
+#ifdef V4_AUTOTEST
+public:
+#endif
     struct Move {
         Expr *from;
         Temp *to;
         bool needsSwap;
 
-        Move(Expr *from, Temp *to)
-            : from(from), to(to), needsSwap(false)
+        Move(Expr *from, Temp *to, bool needsSwap = false)
+            : from(from), to(to), needsSwap(needsSwap)
         {}
 
         bool operator==(const Move &other) const
@@ -284,9 +287,7 @@ public:
     void dump() const;
 
 private:
-    enum Action { NormalMove, NeedsSwap };
-    Action schedule(const Move &m, QList<Move> &todo, QList<Move> &delayed, QList<Move> &output,
-                    QList<Move> &swaps) const;
+    int findLeaf() const;
 };
 
 /*
diff --git a/src/qml/jit/qv4regalloc.cpp b/src/qml/jit/qv4regalloc.cpp
index 124717680c..d49fae3096 100644
--- a/src/qml/jit/qv4regalloc.cpp
+++ b/src/qml/jit/qv4regalloc.cpp
@@ -1134,6 +1134,8 @@ private:
             mapping.add(moveFrom, moveTo);
         }
 
+        if (DebugRegAlloc)
+            mapping.dump();
         mapping.order();
         if (DebugRegAlloc)
             mapping.dump();