V4: remove unnecessary spills and order them correctly.

When doing edge resolving, too many spills were generated, and the
dependency tracking of moves was not complete. Now we only insert spills
that are caused by phi-nodes (because any other spill would be generated
at the point a variable was defined). However, there can still be
multiple dependencies between the moves generated by the edge resolving.
Instead of only checking the first dependency, all of them are tracked.

The bug report was a case where an unneccesary spill was generated, that
got tracked, but "suppressed" the other (valid!) dependent move. The
randomness was caused by the hash seeding of QHash.

Task-number: QTBUG-35840

Change-Id: Ifbc3c8fc13de53c46a8b5859721b2497189921a3
Reviewed-by: Fawzi Mohamed <fawzi.mohamed@digia.com>
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

3 files changed, 31 insertions, 21 deletions

diff --git a/src/qml/compiler/qv4regalloc.cpp b/src/qml/compiler/qv4regalloc.cpp
index 93ecdb2602..5597759ee1 100644
--- a/src/qml/compiler/qv4regalloc.cpp
+++ b/src/qml/compiler/qv4regalloc.cpp
@@ -817,19 +817,15 @@ private:
     void resolve()
     {
         foreach (BasicBlock *bb, _function->basicBlocks) {
-            foreach (BasicBlock *bbOut, bb->out) {
-#ifdef DEBUG_REGALLOC
-                Optimizer::showMeTheCode(_function);
-#endif // DEBUG_REGALLOC
-
+            foreach (BasicBlock *bbOut, bb->out)
                 resolveEdge(bb, bbOut);
-            }
         }
     }
 
     void resolveEdge(BasicBlock *predecessor, BasicBlock *successor)
     {
 #ifdef DEBUG_REGALLOC
+        Optimizer::showMeTheCode(_function);
         qDebug() << "Resolving edge" << predecessor->index << "->" << successor->index;
 #endif // DEBUG_REGALLOC
 
@@ -849,16 +845,20 @@ private:
         Q_ASSERT(successorStart > 0);
 
         foreach (const LifeTimeInterval &it, _liveAtStart[successor]) {
-            bool lifeTimeHole = false;
             if (it.end() < successorStart)
                 continue;
+
+            bool lifeTimeHole = false;
+            bool isPhiTarget = false;
             Expr *moveFrom = 0;
+
             if (it.start() == successorStart) {
                 foreach (Stmt *s, successor->statements) {
                     if (!s || s->id < 1)
                         continue;
                     if (Phi *phi = s->asPhi()) {
                         if (*phi->targetTemp == it.temp()) {
+                            isPhiTarget = true;
                             Expr *opd = phi->d->incoming[successor->in.indexOf(predecessor)];
                             if (opd->asConst()) {
                                 moveFrom = opd;
@@ -939,12 +939,17 @@ private:
 
             Temp *moveTo;
             if (it.reg() == LifeTimeInterval::Invalid || !it.covers(successorStart)) {
-                int spillSlot = _assignedSpillSlots.value(it.temp(), -1);
+                if (!isPhiTarget) // if it.temp() is a phi target, skip it.
+                    continue;
+                const int spillSlot = _assignedSpillSlots.value(it.temp(), -1);
                 if (spillSlot == -1)
                     continue; // it has a life-time hole here.
                 moveTo = createTemp(Temp::StackSlot, spillSlot, it.temp().type);
             } else {
                 moveTo = createTemp(Temp::PhysicalRegister, platformRegister(it), it.temp().type);
+                const int spillSlot = _assignedSpillSlots.value(it.temp(), -1);
+                if (isPhiTarget && spillSlot != -1)
+                    mapping.add(moveFrom, createTemp(Temp::StackSlot, spillSlot, it.temp().type));
             }
 
             // add move to mapping
@@ -1078,7 +1083,7 @@ void RegisterAllocator::run(Function *function, const Optimizer &opt)
     {
         QTextStream qout(stdout, QIODevice::WriteOnly);
         qout << "Ranges:" << endl;
-        QList<LifeTimeInterval> intervals = _unhandled;
+        QVector<LifeTimeInterval> intervals = _unhandled;
         std::sort(intervals.begin(), intervals.end(), LifeTimeInterval::lessThanForTemp);
         foreach (const LifeTimeInterval &r, intervals) {
             r.dump(qout);
@@ -1585,7 +1590,7 @@ void RegisterAllocator::dump() const
 
     {
         qout << "Ranges:" << endl;
-        QList<LifeTimeInterval> handled = _handled;
+        QVector<LifeTimeInterval> handled = _handled;
         std::sort(handled.begin(), handled.end(), LifeTimeInterval::lessThanForTemp);
         foreach (const LifeTimeInterval &r, handled) {
             r.dump(qout);
diff --git a/src/qml/compiler/qv4ssa.cpp b/src/qml/compiler/qv4ssa.cpp
index 31a1e4cdc4..a668375da0 100644
--- a/src/qml/compiler/qv4ssa.cpp
+++ b/src/qml/compiler/qv4ssa.cpp
@@ -3837,15 +3837,20 @@ static inline bool overlappingStorage(const Temp &t1, const Temp &t2)
             || (t1.type != DoubleType && t2.type != DoubleType);
 }
 
-int MoveMapping::isUsedAsSource(Expr *e) const
+MoveMapping::Moves MoveMapping::sourceUsages(Expr *e, const Moves &moves)
 {
-    if (Temp *t = e->asTemp())
-        for (int i = 0, ei = _moves.size(); i != ei; ++i)
-            if (Temp *from = _moves[i].from->asTemp())
+    Moves usages;
+
+    if (Temp *t = e->asTemp()) {
+        for (int i = 0, ei = moves.size(); i != ei; ++i) {
+            const Move &move = moves[i];
+            if (Temp *from = move.from->asTemp())
                 if (overlappingStorage(*from, *t))
-                    return i;
+                    usages.append(move);
+        }
+    }
 
-    return -1;
+    return usages;
 }
 
 void MoveMapping::add(Expr *from, Temp *to, int id) {
@@ -3924,9 +3929,8 @@ void MoveMapping::dump() const
 MoveMapping::Action MoveMapping::schedule(const Move &m, QList<Move> &todo, QList<Move> &delayed,
                                           QList<Move> &output, QList<Move> &swaps) const
 {
-    int useIdx = isUsedAsSource(m.to);
-    if (useIdx != -1) {
-        const Move &dependency = _moves[useIdx];
+    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.
diff --git a/src/qml/compiler/qv4ssa_p.h b/src/qml/compiler/qv4ssa_p.h
index dcbc83ae65..2c61a2fe1a 100644
--- a/src/qml/compiler/qv4ssa_p.h
+++ b/src/qml/compiler/qv4ssa_p.h
@@ -165,10 +165,11 @@ class MoveMapping
         bool operator==(const Move &other) const
         { return from == other.from && to == other.to; }
     };
+    typedef QList<Move> Moves;
 
-    QList<Move> _moves;
+    Moves _moves;
 
-    int isUsedAsSource(Expr *e) const;
+    static Moves sourceUsages(Expr *e, const Moves &moves);
 
 public:
     void add(Expr *from, Temp *to, int id = 0);