V4 IR: update immediate dominators when purging unreachable basic-blocks

The basic block scheduling uses this information to place loops. When
the immediate dominator information is invalid, the scheduling can be
sub-optimal, or will sometimes forget to schedule some blocks.

Change-Id: Iaeb45f2b757b676310be25a658ceadc07d5722ec
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

1 files changed, 19 insertions, 13 deletions

diff --git a/src/qml/compiler/qv4ssa.cpp b/src/qml/compiler/qv4ssa.cpp
index a668375da0..c2889a2b9a 100644
--- a/src/qml/compiler/qv4ssa.cpp
+++ b/src/qml/compiler/qv4ssa.cpp
@@ -695,10 +695,6 @@ public:
         computeDF();
     }
 
-//    QSet<BasicBlock *> operator[](BasicBlock *n) const {
-//        return DF[n->index];
-//    }
-
     const BasicBlockSet &dominatorFrontier(BasicBlock *n) const {
         return DF[n->index];
     }
@@ -707,6 +703,11 @@ public:
         return nodes[idom[bb->index]];
     }
 
+    void updateImmediateDominator(BasicBlock *bb, BasicBlock *newDominator)
+    {
+        idom[bb->index] = newDominator->index;
+    }
+
     bool dominates(BasicBlock *dominator, BasicBlock *dominated) const {
         // The index of the basic blocks might have changed, or the nodes array might have changed,
         // or the block got deleted, so get the index from our copy of the array.
@@ -2895,7 +2896,8 @@ namespace {
 /// and removes unreachable staements from the worklist, so that optimiseSSA won't consider them
 /// anymore.
 /// Important: this assumes that there are no critical edges in the control-flow graph!
-void purgeBB(BasicBlock *bb, Function *func, DefUsesCalculator &defUses, QVector<Stmt *> &W)
+void purgeBB(BasicBlock *bb, Function *func, DefUsesCalculator &defUses, QVector<Stmt *> &W,
+             DominatorTree &df)
 {
     // TODO: change this to mark the block as deleted, but leave it alone so that other references
     //       won't be dangling pointers.
@@ -2945,11 +2947,15 @@ void purgeBB(BasicBlock *bb, Function *func, DefUsesCalculator &defUses, QVector
                 }
             }
 
-            // if a successor has no incoming edges after unlinking the current basic block, then
-            // it is unreachable, and can be purged too
-            if (out->in.isEmpty())
+            if (out->in.isEmpty()) {
+                // if a successor has no incoming edges after unlinking the current basic block, then
+                // it is unreachable, and can be purged too
                 toPurge.append(out);
-
+            } else if (out->in.size() == 1) {
+                // if the successor now has only one incoming edge, we that edge is the new
+                // immediate dominator
+                df.updateImmediateDominator(out, out->in.first());
+            }
         }
 
         // unlink all defs/uses from the statements in the basic block
@@ -3032,7 +3038,7 @@ bool tryOptimizingComparison(Expr *&expr)
 }
 } // anonymous namespace
 
-void optimizeSSA(Function *function, DefUsesCalculator &defUses)
+void optimizeSSA(Function *function, DefUsesCalculator &defUses, DominatorTree &df)
 {
     const bool variablesCanEscape = function->variablesCanEscape();
 
@@ -3298,10 +3304,10 @@ void optimizeSSA(Function *function, DefUsesCalculator &defUses)
                 Jump *jump = function->New<Jump>();
                 if (convertToValue(constantCondition).toBoolean()) {
                     jump->target = cjump->iftrue;
-                    purgeBB(cjump->iffalse, function, defUses, W);
+                    purgeBB(cjump->iffalse, function, defUses, W, df);
                 } else {
                     jump->target = cjump->iffalse;
-                    purgeBB(cjump->iftrue, function, defUses, W);
+                    purgeBB(cjump->iftrue, function, defUses, W, df);
                 }
                 *ref[s] = jump;
 
@@ -3681,7 +3687,7 @@ void Optimizer::run(QQmlEnginePrivate *qmlEngine)
         static bool doOpt = qgetenv("QV4_NO_OPT").isEmpty();
         if (doOpt) {
 //            qout << "Running SSA optimization..." << endl;
-            optimizeSSA(function, defUses);
+            optimizeSSA(function, defUses, df);
 //            showMeTheCode(function);
         }