V4: Fix issues with very small loops5.8

Loops consisting of just a single basic block (e.g. a do-while loop with
no nested loops or if statements) have a back-edge to themselves. There
were 2 problems:
- loop detection would create LoopInfo for any loop header referred to
  by blocks inside the loop (and a 1 block loop doesn't have body
  blocks), nor would it mark the loop header as such
- when splitting critical edges, the newly inserted block would not be
  marked as part of the loop

This is a problem specifically for 1 block loops: the block ends with
a CJUMP, so the back-edge is a critical edge. So the new block inserted
by edge splitting wouldn't be marked as belonging to the loop.

The end result was that the life-time intervals for temporaries that
are defined before the loop, but that are used inside the loop, and not
after the loop, would have their life-time ended before the loop ends
(instead of spanning the whole loop, *including* the back-edge). This
in turns could lead to the stack/register allocator re-using the storage
for that temporary, resulting in strange things happening.

Task-number: QTBUG-59012
Change-Id: Ic946c73913711272efea2151cb85350412ca2fde
Reviewed-by: Simon Hausmann <simon.hausmann@qt.io>

5 files changed, 208 insertions, 157 deletions

diff --git a/src/qml/compiler/qv4jsir.cpp b/src/qml/compiler/qv4jsir.cpp
index 5687834b00..1dff7c9ac3 100644
--- a/src/qml/compiler/qv4jsir.cpp
+++ b/src/qml/compiler/qv4jsir.cpp
@@ -448,10 +448,6 @@ void Function::setScheduledBlocks(const QVector<BasicBlock *> &scheduled)
     Q_ASSERT(!_allBasicBlocks);
     _allBasicBlocks = new QVector<BasicBlock *>(basicBlocks());
     _basicBlocks = scheduled;
-}
-
-void Function::renumberBasicBlocks()
-{
     for (int i = 0, ei = basicBlockCount(); i != ei; ++i)
         basicBlock(i)->changeIndex(i);
 }
diff --git a/src/qml/compiler/qv4jsir_p.h b/src/qml/compiler/qv4jsir_p.h
index a614d3fe1c..d55726cd0f 100644
--- a/src/qml/compiler/qv4jsir_p.h
+++ b/src/qml/compiler/qv4jsir_p.h
@@ -1347,7 +1347,6 @@ struct Function {
     { return hasDirectEval || !nestedFunctions.isEmpty() || module->debugMode; }
 
     void setScheduledBlocks(const QVector<BasicBlock *> &scheduled);
-    void renumberBasicBlocks();
 
     int getNewStatementId() { return _statementCount++; }
     int statementCount() const { return _statementCount; }
diff --git a/src/qml/compiler/qv4ssa.cpp b/src/qml/compiler/qv4ssa.cpp
index 45ca56584f..fa4bd93eb0 100644
--- a/src/qml/compiler/qv4ssa.cpp
+++ b/src/qml/compiler/qv4ssa.cpp
@@ -3023,14 +3023,19 @@ void splitCriticalEdges(IR::Function *f, DominatorTree &df, StatementWorklist &w
 
             // add newBB to the correct loop group
             if (toBB->isGroupStart()) {
-                BasicBlock *container;
-                for (container = fromBB->containingGroup(); container; container = container->containingGroup())
-                     if (container == toBB)
-                         break;
-                if (container == toBB) // if we were already inside the toBB loop
+                if (fromBB == toBB) {
+                    // special case: the loop header points back to itself (so it's a small loop).
                     newBB->setContainingGroup(toBB);
-                else
-                    newBB->setContainingGroup(toBB->containingGroup());
+                } else {
+                    BasicBlock *container;
+                    for (container = fromBB->containingGroup(); container; container = container->containingGroup())
+                        if (container == toBB)
+                            break;
+                    if (container == toBB) // if we were already inside the toBB loop
+                        newBB->setContainingGroup(toBB);
+                    else
+                        newBB->setContainingGroup(toBB->containingGroup());
+                }
             } else {
                 newBB->setContainingGroup(toBB->containingGroup());
             }
@@ -3061,7 +3066,7 @@ void splitCriticalEdges(IR::Function *f, DominatorTree &df, StatementWorklist &w
 
             bool toNeedsNewIdom = true;
             for (BasicBlock *bb : toBB->in) {
-                if (bb != newBB && !df.dominates(toBB, bb)) {
+                if (bb != newBB && bb != toBB && !df.dominates(toBB, bb)) {
                     toNeedsNewIdom = false;
                     break;
                 }
@@ -3171,7 +3176,7 @@ public:
             backedges.clear();
 
             for (BasicBlock *in : bb->in)
-                if (dt.dominates(bb, in))
+                if (bb == in || dt.dominates(bb, in))
                     backedges.push_back(in);
 
             if (!backedges.empty()) {
@@ -3188,6 +3193,7 @@ public:
         if (!DebugLoopDetection)
             return;
 
+        qDebug() << "Found" << loopInfos.size() << "loops";
         foreach (LoopInfo *info, loopInfos) {
             qDebug() << "Loop header:" << info->loopHeader->index()
                      << "for loop" << quint64(info);
@@ -3221,6 +3227,9 @@ private:
     void subLoop(BasicBlock *loopHead, const std::vector<BasicBlock *> &backedges)
     {
         loopHead->markAsGroupStart();
+        LoopInfo *info = new LoopInfo;
+        info->loopHeader = loopHead;
+        loopInfos.append(info);
 
         std::vector<BasicBlock *> worklist;
         worklist.reserve(backedges.size() + 8);
@@ -3290,10 +3299,8 @@ private:
                 return info;
         }
 
-        LoopInfo *info = new LoopInfo;
-        info->loopHeader = loopHeader;
-        loopInfos.append(info);
-        return info;
+        Q_UNREACHABLE();
+        return nullptr;
     }
 };
 
@@ -3323,6 +3330,8 @@ private:
 // the same reason.
 class BlockScheduler
 {
+    enum { DebugBlockScheduler = 0 };
+
     IR::Function *function;
     const DominatorTree &dominatorTree;
 
@@ -3438,6 +3447,14 @@ class BlockScheduler
         Q_UNREACHABLE();
     }
 
+    void dumpLoopStartsEnds() const
+    {
+        qDebug() << "Found" << loopsStartEnd.size() << "loops:";
+        for (auto key : loopsStartEnd.keys())
+            qDebug("Loop starting at L%d ends at L%d.", key->index(),
+                   loopsStartEnd.value(key)->index());
+    }
+
 public:
     BlockScheduler(IR::Function *function, const DominatorTree &dominatorTree)
         : function(function)
@@ -3449,11 +3466,15 @@ public:
     QHash<BasicBlock *, BasicBlock *> go()
     {
         showMeTheCode(function, "Before block scheduling");
+        if (DebugBlockScheduler)
+            dominatorTree.dumpImmediateDominators();
+
         schedule(function->basicBlock(0));
 
         Q_ASSERT(function->liveBasicBlocksCount() == sequence.size());
         function->setScheduledBlocks(sequence);
-        function->renumberBasicBlocks();
+        if (DebugBlockScheduler)
+            dumpLoopStartsEnds();
         return loopsStartEnd;
     }
 };
@@ -4588,7 +4609,6 @@ void removeUnreachleBlocks(IR::Function *function)
         if (!bb->isRemoved())
             newSchedule.append(bb);
     function->setScheduledBlocks(newSchedule);
-    function->renumberBasicBlocks();
 }
 
 class ConvertArgLocals
@@ -4762,6 +4782,137 @@ private:
     IR::Stmt *clonedStmt;
 };
 
+static void verifyCFG(IR::Function *function)
+{
+    if (!DoVerification)
+        return;
+
+    for (BasicBlock *bb : function->basicBlocks()) {
+        if (bb->isRemoved()) {
+            Q_ASSERT(bb->in.isEmpty());
+            Q_ASSERT(bb->out.isEmpty());
+            continue;
+        }
+
+        Q_ASSERT(function->basicBlock(bb->index()) == bb);
+
+        // Check the terminators:
+        Stmt *terminator = bb->terminator();
+        if (terminator == nullptr) {
+            Stmt *last = bb->statements().last();
+            Call *call = last->asExp()->expr->asCall();
+            Name *baseName = call->base->asName();
+            Q_ASSERT(baseName->builtin == Name::builtin_rethrow);
+            Q_UNUSED(baseName);
+        } else if (Jump *jump = terminator->asJump()) {
+            Q_UNUSED(jump);
+            Q_ASSERT(jump->target);
+            Q_ASSERT(!jump->target->isRemoved());
+            Q_ASSERT(bb->out.size() == 1);
+            Q_ASSERT(bb->out.first() == jump->target);
+        } else if (CJump *cjump = terminator->asCJump()) {
+            Q_UNUSED(cjump);
+            Q_ASSERT(bb->out.size() == 2);
+            Q_ASSERT(cjump->iftrue);
+            Q_ASSERT(!cjump->iftrue->isRemoved());
+            Q_ASSERT(cjump->iftrue == bb->out[0]);
+            Q_ASSERT(cjump->iffalse);
+            Q_ASSERT(!cjump->iffalse->isRemoved());
+            Q_ASSERT(cjump->iffalse == bb->out[1]);
+        } else if (terminator->asRet()) {
+            Q_ASSERT(bb->out.size() == 0);
+        } else {
+            Q_UNREACHABLE();
+        }
+
+        // Check the outgoing edges:
+        for (BasicBlock *out : bb->out) {
+            Q_UNUSED(out);
+            Q_ASSERT(!out->isRemoved());
+            Q_ASSERT(out->in.contains(bb));
+        }
+
+        // Check the incoming edges:
+        for (BasicBlock *in : bb->in) {
+            Q_UNUSED(in);
+            Q_ASSERT(!in->isRemoved());
+            Q_ASSERT(in->out.contains(bb));
+        }
+    }
+}
+
+static void verifyImmediateDominators(const DominatorTree &dt, IR::Function *function)
+{
+    if (!DoVerification)
+        return;
+
+    cfg2dot(function);
+    dt.dumpImmediateDominators();
+    DominatorTree referenceTree(function);
+
+    for (BasicBlock *bb : function->basicBlocks()) {
+        if (bb->isRemoved())
+            continue;
+
+        BasicBlock *idom = dt.immediateDominator(bb);
+        BasicBlock *referenceIdom = referenceTree.immediateDominator(bb);
+        Q_UNUSED(idom);
+        Q_UNUSED(referenceIdom);
+        Q_ASSERT(idom == referenceIdom);
+    }
+}
+
+static void verifyNoPointerSharing(IR::Function *function)
+{
+    if (!DoVerification)
+        return;
+
+    class {
+    public:
+        void operator()(IR::Function *f)
+        {
+            for (BasicBlock *bb : f->basicBlocks()) {
+                if (bb->isRemoved())
+                    continue;
+
+                for (Stmt *s : bb->statements()) {
+                    visit(s);
+                }
+            }
+        }
+
+    private:
+        void visit(Stmt *s)
+        {
+            check(s);
+            STMT_VISIT_ALL_KINDS(s);
+        }
+
+        void visit(Expr *e)
+        {
+            check(e);
+            EXPR_VISIT_ALL_KINDS(e);
+        }
+
+    private:
+        void check(Stmt *s)
+        {
+            Q_ASSERT(!stmts.contains(s));
+            stmts.insert(s);
+        }
+
+        void check(Expr *e)
+        {
+            Q_ASSERT(!exprs.contains(e));
+            exprs.insert(e);
+        }
+
+        QSet<Stmt *> stmts;
+        QSet<Expr *> exprs;
+    } V;
+    V(function);
+}
+
 // Loop-peeling is done by unfolding the loop once. The "original" loop basic blocks stay where they
 // are, and a copy of the loop is placed after it. Special care is taken while copying the loop body:
 // by having the copies of the basic-blocks point to the same nodes as the "original" basic blocks,
@@ -4822,12 +4973,14 @@ private:
 
     void peelLoop(LoopDetection::LoopInfo *loop)
     {
+        IR::Function *f = loop->loopHeader->function;
         CloneBasicBlock clone;
 
         LoopDetection::LoopInfo unpeeled(*loop);
         unpeeled.loopHeader = clone(unpeeled.loopHeader);
         unpeeled.loopHeader->setContainingGroup(loop->loopHeader->containingGroup());
         unpeeled.loopHeader->markAsGroupStart(true);
+        f->addBasicBlock(unpeeled.loopHeader);
         for (int i = 0, ei = unpeeled.loopBody.size(); i != ei; ++i) {
             BasicBlock *&bodyBlock = unpeeled.loopBody[i];
             bodyBlock = clone(bodyBlock);
@@ -4841,8 +4994,8 @@ private:
 
         BasicBlock::IncomingEdges inCopy = loop->loopHeader->in;
         for (BasicBlock *in : inCopy) {
-            if (unpeeled.loopHeader != in // this can happen for really tight loops (where there are no body blocks). This is a back-edge in that case.
-                    && !unpeeled.loopBody.contains(in) // if the edge is not coming from within the copied set, leave it alone
+            if (loop->loopHeader != in // this can happen for really tight loops (where there are no body blocks). This is a back-edge in that case.
+                    && unpeeled.loopHeader != in && !unpeeled.loopBody.contains(in) // if the edge is not coming from within the copied set, leave it alone
                     && !dt.dominates(loop->loopHeader, in)) // an edge coming from within the loop (so a back-edge): this is handled when rewiring all outgoing edges
                 continue;
 
@@ -4872,9 +5025,7 @@ private:
         loopExits.reserve(8);
         loopExits.append(unpeeled.loopHeader);
 
-        IR::Function *f = unpeeled.loopHeader->function;
         rewire(unpeeled.loopHeader, loop->loopBody, unpeeled.loopBody, loopExits);
-        f->addBasicBlock(unpeeled.loopHeader);
         for (int i = 0, ei = unpeeled.loopBody.size(); i != ei; ++i) {
             BasicBlock *bodyBlock = unpeeled.loopBody.at(i);
             rewire(bodyBlock, loop->loopBody, unpeeled.loopBody, loopExits);
@@ -4887,6 +5038,9 @@ private:
         foreach (BasicBlock *bb, loop->loopBody)
             bb->setContainingGroup(loop->loopHeader->containingGroup());
 
+        // Set the immediate dominator of the new loop header to the old one. The real immediate
+        // dominator will be calculated later.
+        dt.setImmediateDominator(unpeeled.loopHeader, loop->loopHeader);
         // calculate the idoms in a separate loop, because addBasicBlock in the previous loop will
         // set the block index, which in turn is used by the dominator tree.
         for (int i = 0, ei = unpeeled.loopBody.size(); i != ei; ++i) {
@@ -4905,141 +5059,13 @@ private:
         foreach (BasicBlock *bb, loopExits)
             dt.collectSiblings(bb, siblings);
 
+        siblings.insert(unpeeled.loopHeader);
         dt.recalculateIDoms(siblings, loop->loopHeader);
+        dt.dumpImmediateDominators();
+        verifyImmediateDominators(dt, f);
     }
 };
 
-static void verifyCFG(IR::Function *function)
-{
-    if (!DoVerification)
-        return;
-
-    for (BasicBlock *bb : function->basicBlocks()) {
-        if (bb->isRemoved()) {
-            Q_ASSERT(bb->in.isEmpty());
-            Q_ASSERT(bb->out.isEmpty());
-            continue;
-        }
-
-        Q_ASSERT(function->basicBlock(bb->index()) == bb);
-
-        // Check the terminators:
-        Stmt *terminator = bb->terminator();
-        if (terminator == nullptr) {
-            Stmt *last = bb->statements().last();
-            Call *call = last->asExp()->expr->asCall();
-            Name *baseName = call->base->asName();
-            Q_ASSERT(baseName->builtin == Name::builtin_rethrow);
-            Q_UNUSED(baseName);
-        } else if (Jump *jump = terminator->asJump()) {
-            Q_UNUSED(jump);
-            Q_ASSERT(jump->target);
-            Q_ASSERT(!jump->target->isRemoved());
-            Q_ASSERT(bb->out.size() == 1);
-            Q_ASSERT(bb->out.first() == jump->target);
-        } else if (CJump *cjump = terminator->asCJump()) {
-            Q_UNUSED(cjump);
-            Q_ASSERT(bb->out.size() == 2);
-            Q_ASSERT(cjump->iftrue);
-            Q_ASSERT(!cjump->iftrue->isRemoved());
-            Q_ASSERT(cjump->iftrue == bb->out[0]);
-            Q_ASSERT(cjump->iffalse);
-            Q_ASSERT(!cjump->iffalse->isRemoved());
-            Q_ASSERT(cjump->iffalse == bb->out[1]);
-        } else if (terminator->asRet()) {
-            Q_ASSERT(bb->out.size() == 0);
-        } else {
-            Q_UNREACHABLE();
-        }
-
-        // Check the outgoing edges:
-        for (BasicBlock *out : bb->out) {
-            Q_UNUSED(out);
-            Q_ASSERT(!out->isRemoved());
-            Q_ASSERT(out->in.contains(bb));
-        }
-
-        // Check the incoming edges:
-        for (BasicBlock *in : bb->in) {
-            Q_UNUSED(in);
-            Q_ASSERT(!in->isRemoved());
-            Q_ASSERT(in->out.contains(bb));
-        }
-    }
-}
-
-static void verifyImmediateDominators(const DominatorTree &dt, IR::Function *function)
-{
-    if (!DoVerification)
-        return;
-
-    cfg2dot(function);
-    dt.dumpImmediateDominators();
-    DominatorTree referenceTree(function);
-
-    for (BasicBlock *bb : function->basicBlocks()) {
-        if (bb->isRemoved())
-            continue;
-
-        BasicBlock *idom = dt.immediateDominator(bb);
-        BasicBlock *referenceIdom = referenceTree.immediateDominator(bb);
-        Q_UNUSED(idom);
-        Q_UNUSED(referenceIdom);
-        Q_ASSERT(idom == referenceIdom);
-    }
-}
-
-static void verifyNoPointerSharing(IR::Function *function)
-{
-    if (!DoVerification)
-        return;
-
-    class {
-    public:
-        void operator()(IR::Function *f)
-        {
-            for (BasicBlock *bb : f->basicBlocks()) {
-                if (bb->isRemoved())
-                    continue;
-
-                for (Stmt *s : bb->statements()) {
-                    visit(s);
-                }
-            }
-        }
-
-    private:
-        void visit(Stmt *s)
-        {
-            check(s);
-            STMT_VISIT_ALL_KINDS(s);
-        }
-
-        void visit(Expr *e)
-        {
-            check(e);
-            EXPR_VISIT_ALL_KINDS(e);
-        }
-
-    private:
-        void check(Stmt *s)
-        {
-            Q_ASSERT(!stmts.contains(s));
-            stmts.insert(s);
-        }
-
-        void check(Expr *e)
-        {
-            Q_ASSERT(!exprs.contains(e));
-            exprs.insert(e);
-        }
-
-        QSet<Stmt *> stmts;
-        QSet<Expr *> exprs;
-    } V;
-    V(function);
-}
-
 class RemoveLineNumbers: private SideEffectsChecker
 {
 public:
@@ -5448,6 +5474,9 @@ void Optimizer::run(QQmlEnginePrivate *qmlEngine, bool doTypeInference, bool pee
         verifyNoPointerSharing(function);
         mergeBasicBlocks(function, &defUses, &df);
 
+        verifyImmediateDominators(df, function);
+        verifyCFG(function);
+
         // Basic-block cycles that are unreachable (i.e. for loops in a then-part where the
         // condition is calculated to be always false) are not yet removed. This will choke the
         // block scheduling, so remove those now.
@@ -5455,10 +5484,13 @@ void Optimizer::run(QQmlEnginePrivate *qmlEngine, bool doTypeInference, bool pee
         cleanupBasicBlocks(function);
 //        showMeTheCode(function);
 
+        verifyImmediateDominators(df, function);
+        verifyCFG(function);
+
         // Transform the CFG into edge-split SSA.
-//        qout << "Starting edge splitting..." << endl;
+        showMeTheCode(function, "Before edge splitting");
         splitCriticalEdges(function, df, worklist, defUses);
-//        showMeTheCode(function);
+        showMeTheCode(function, "After edge splitting");
 
         verifyImmediateDominators(df, function);
         verifyCFG(function);
diff --git a/tests/auto/qml/qqmlecmascript/data/qtbug_59012.qml b/tests/auto/qml/qqmlecmascript/data/qtbug_59012.qml
new file mode 100644
index 0000000000..5283614435
--- /dev/null
+++ b/tests/auto/qml/qqmlecmascript/data/qtbug_59012.qml
@@ -0,0 +1,14 @@
+import QtQuick 2.0
+
+QtObject {
+    Component.onCompleted: {
+        var pieces = [[4,21],[6,22],[8,23],[12,24],[10,25],[8,26],[6,27],[4,28],[2,31],[2,32],[2,33],[2,35],[2,36],[2,37],[2,38],[2,54]]
+        var i = pieces.length;
+        var king = 10
+        var val
+        do {
+            var p = pieces[--i];
+            val = p[0]
+        } while (val !== king);
+    }
+}
diff --git a/tests/auto/qml/qqmlecmascript/tst_qqmlecmascript.cpp b/tests/auto/qml/qqmlecmascript/tst_qqmlecmascript.cpp
index 20f7940e9d..068881affb 100644
--- a/tests/auto/qml/qqmlecmascript/tst_qqmlecmascript.cpp
+++ b/tests/auto/qml/qqmlecmascript/tst_qqmlecmascript.cpp
@@ -331,6 +331,7 @@ private slots:
     void qtbug_54589();
     void qtbug_54687();
     void stringify_qtbug_50592();
+    void singleBlockLoops();
 
 private:
 //    static void propertyVarWeakRefCallback(v8::Persistent<v8::Value> object, void* parameter);
@@ -8119,6 +8120,15 @@ void tst_qqmlecmascript::stringify_qtbug_50592()
     QCOMPARE(obj->property("source").toString(), QString::fromLatin1("http://example.org/some_nonexistant_image.png"));
 }
 
+void tst_qqmlecmascript::singleBlockLoops()
+{
+    QQmlComponent component(&engine, testFileUrl("qtbug_59012.qml"));
+
+    QScopedPointer<QObject> obj(component.create());
+    QVERIFY(obj != 0);
+    QVERIFY(!component.isError());
+}
+
 QTEST_MAIN(tst_qqmlecmascript)
 
 #include "tst_qqmlecmascript.moc"