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>

1 files changed, 92 insertions, 0 deletions

diff --git a/tests/auto/qml/v4misc/tst_v4misc.cpp b/tests/auto/qml/v4misc/tst_v4misc.cpp
index 057714e175..88b6ae92a8 100644
--- a/tests/auto/qml/v4misc/tst_v4misc.cpp
+++ b/tests/auto/qml/v4misc/tst_v4misc.cpp
@@ -28,6 +28,7 @@
 
 #include <qtest.h>
 
+#define V4_AUTOTEST
 #include <private/qv4ssa_p.h>
 
 class tst_v4misc: public QObject
@@ -40,6 +41,9 @@ private slots:
     void rangeSplitting_1();
     void rangeSplitting_2();
     void rangeSplitting_3();
+
+    void moveMapping_1();
+    void moveMapping_2();
 };
 
 QT_BEGIN_NAMESPACE
@@ -139,6 +143,94 @@ void tst_v4misc::rangeSplitting_3()
     QCOMPARE(interval.end(), 71);
 }
 
+void tst_v4misc::moveMapping_1()
+{
+    Temp fp2(DoubleType, Temp::PhysicalRegister, 2);
+    Temp fp3(DoubleType, Temp::PhysicalRegister, 3);
+    Temp fp4(DoubleType, Temp::PhysicalRegister, 4);
+    Temp fp5(DoubleType, Temp::PhysicalRegister, 5);
+
+    MoveMapping mapping;
+    mapping.add(&fp2, &fp3);
+    mapping.add(&fp2, &fp4);
+    mapping.add(&fp2, &fp5);
+    mapping.add(&fp3, &fp2);
+
+    mapping.order();
+//    mapping.dump();
+
+    QCOMPARE(mapping._moves.size(), 3);
+    QVERIFY(mapping._moves.contains(MoveMapping::Move(&fp2, &fp4, false)));
+    QVERIFY(mapping._moves.contains(MoveMapping::Move(&fp2, &fp5, false)));
+    QVERIFY(mapping._moves.last() == MoveMapping::Move(&fp2, &fp3, true) ||
+            mapping._moves.last() == MoveMapping::Move(&fp3, &fp2, true));
+}
+
+void tst_v4misc::moveMapping_2()
+{
+    Temp fp1(DoubleType, Temp::PhysicalRegister, 1);
+    Temp fp2(DoubleType, Temp::PhysicalRegister, 2);
+    Temp fp3(DoubleType, Temp::PhysicalRegister, 3);
+    Temp fp4(DoubleType, Temp::PhysicalRegister, 4);
+    Temp fp5(DoubleType, Temp::PhysicalRegister, 5);
+    Temp fp6(DoubleType, Temp::PhysicalRegister, 6);
+    Temp fp7(DoubleType, Temp::PhysicalRegister, 7);
+    Temp fp8(DoubleType, Temp::PhysicalRegister, 8);
+    Temp fp9(DoubleType, Temp::PhysicalRegister, 9);
+    Temp fp10(DoubleType, Temp::PhysicalRegister, 10);
+    Temp fp11(DoubleType, Temp::PhysicalRegister, 11);
+    Temp fp12(DoubleType, Temp::PhysicalRegister, 12);
+    Temp fp13(DoubleType, Temp::PhysicalRegister, 13);
+
+    MoveMapping mapping;
+    mapping.add(&fp2, &fp1);
+    mapping.add(&fp2, &fp3);
+    mapping.add(&fp3, &fp2);
+    mapping.add(&fp3, &fp4);
+
+    mapping.add(&fp9, &fp8);
+    mapping.add(&fp8, &fp7);
+    mapping.add(&fp7, &fp6);
+    mapping.add(&fp7, &fp5);
+
+    mapping.add(&fp10, &fp11);
+    mapping.add(&fp11, &fp12);
+    mapping.add(&fp12, &fp13);
+    mapping.add(&fp13, &fp10);
+
+    mapping.order();
+//    mapping.dump();
+
+    QCOMPARE(mapping._moves.size(), 10);
+
+    QVERIFY(mapping._moves.contains(MoveMapping::Move(&fp2, &fp1, false)));
+    QVERIFY(mapping._moves.contains(MoveMapping::Move(&fp3, &fp4, false)));
+    QVERIFY(mapping._moves.contains(MoveMapping::Move(&fp7, &fp6, false)));
+    QVERIFY(mapping._moves.contains(MoveMapping::Move(&fp7, &fp5, false)));
+    QVERIFY(mapping._moves.contains(MoveMapping::Move(&fp8, &fp7, false)));
+    QVERIFY(mapping._moves.contains(MoveMapping::Move(&fp9, &fp8, false)));
+
+    QVERIFY(mapping._moves.contains(MoveMapping::Move(&fp2, &fp3, true)) ||
+            mapping._moves.contains(MoveMapping::Move(&fp3, &fp2, true)));
+    QVERIFY(mapping._moves.contains(MoveMapping::Move(&fp10, &fp13, true)) ||
+            mapping._moves.contains(MoveMapping::Move(&fp13, &fp10, true)));
+    QVERIFY(mapping._moves.contains(MoveMapping::Move(&fp12, &fp13, true)) ||
+            mapping._moves.contains(MoveMapping::Move(&fp13, &fp12, true)));
+    QVERIFY(mapping._moves.contains(MoveMapping::Move(&fp12, &fp11, true)) ||
+            mapping._moves.contains(MoveMapping::Move(&fp11, &fp12, true)));
+
+    QVERIFY(!mapping._moves.at(0).needsSwap);
+    QVERIFY(!mapping._moves.at(1).needsSwap);
+    QVERIFY(!mapping._moves.at(2).needsSwap);
+    QVERIFY(!mapping._moves.at(3).needsSwap);
+    QVERIFY(!mapping._moves.at(4).needsSwap);
+    QVERIFY(!mapping._moves.at(5).needsSwap);
+    QVERIFY(mapping._moves.at(6).needsSwap);
+    QVERIFY(mapping._moves.at(7).needsSwap);
+    QVERIFY(mapping._moves.at(8).needsSwap);
+    QVERIFY(mapping._moves.at(9).needsSwap);
+}
+
 QTEST_MAIN(tst_v4misc)
 
 #include "tst_v4misc.moc"