V4 IR: loop detection: also record loop information separately.

Now loop-specific algorithms can easily query which blocks are loop
headers, which blocks make up a loop body, and whether loops are nested.

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

1 files changed, 133 insertions, 7 deletions

diff --git a/src/qml/compiler/qv4ssa.cpp b/src/qml/compiler/qv4ssa.cpp
index 9a2f6a86ba..673d4e5db0 100644
--- a/src/qml/compiler/qv4ssa.cpp
+++ b/src/qml/compiler/qv4ssa.cpp
@@ -2866,22 +2866,55 @@ void splitCriticalEdges(IR::Function *f, DominatorTree &df, StatementWorklist &w
 //    }
 class LoopDetection
 {
-    const DominatorTree &dt;
+    enum { DebugLoopDetection = 0 };
 
     Q_DISABLE_COPY(LoopDetection)
 
 public:
+    struct LoopInfo
+    {
+        BasicBlock *loopHeader;
+        QVector<BasicBlock *> loopBody;
+        QVector<LoopInfo *> nestedLoops;
+        LoopInfo *parentLoop;
+
+        LoopInfo(BasicBlock *loopHeader = 0)
+            : loopHeader(loopHeader)
+            , parentLoop(0)
+        {}
+
+        bool isValid() const
+        { return loopHeader != 0; }
+
+        void addNestedLoop(LoopInfo *nested)
+        {
+            Q_ASSERT(nested);
+            Q_ASSERT(!nestedLoops.contains(nested));
+            Q_ASSERT(nested->parentLoop == 0);
+            nested->parentLoop = this;
+            nestedLoops.append(nested);
+        }
+    };
+
+public:
     LoopDetection(const DominatorTree &dt)
         : dt(dt)
     {}
 
-    void run()
+    ~LoopDetection()
     {
+        qDeleteAll(loopInfos);
+    }
+
+    void run(IR::Function *function)
+    {
+        std::vector<BasicBlock *> backedges;
+        backedges.reserve(4);
+
         foreach (BasicBlock *bb, dt.calculateDFNodeIterOrder()) {
             Q_ASSERT(!bb->isRemoved());
 
-            std::vector<BasicBlock *> backedges;
-            backedges.reserve(4);
+            backedges.clear();
 
             foreach (BasicBlock *in, bb->in)
                 if (dt.dominates(bb, in))
@@ -2891,6 +2924,43 @@ public:
                 subLoop(bb, backedges);
             }
         }
+
+        createLoopInfos(function);
+        dumpLoopInfo();
+    }
+
+    void dumpLoopInfo() const
+    {
+        if (!DebugLoopDetection)
+            return;
+
+        foreach (LoopInfo *info, loopInfos) {
+            qDebug() << "Loop header:" << info->loopHeader->index()
+                     << "for loop" << quint64(info);
+            foreach (BasicBlock *bb, info->loopBody)
+                qDebug() << "    " << bb->index();
+            foreach (LoopInfo *nested, info->nestedLoops)
+                qDebug() << "    sub loop:" << quint64(nested);
+            qDebug() << "     parent loop:" << quint64(info->parentLoop);
+        }
+    }
+
+    QVector<LoopInfo *> allLoops() const
+    { return loopInfos; }
+
+    // returns all loop headers for loops that have no nested loops.
+    QVector<LoopInfo *> innermostLoops() const
+    {
+        QVector<LoopInfo *> inner(loopInfos);
+
+        for (int i = 0; i < inner.size(); ) {
+            if (inner.at(i)->nestedLoops.isEmpty())
+                ++i;
+            else
+                inner.remove(i);
+        }
+
+        return inner;
     }
 
 private:
@@ -2898,7 +2968,9 @@ private:
     {
         loopHead->markAsGroupStart();
 
-        std::vector<BasicBlock *> worklist(backedges.begin(), backedges.end());
+        std::vector<BasicBlock *> worklist;
+        worklist.reserve(backedges.size() + 8);
+        worklist.insert(worklist.end(), backedges.begin(), backedges.end());
         while (!worklist.empty()) {
             BasicBlock *predIt = worklist.back();
             worklist.pop_back();
@@ -2937,6 +3009,38 @@ private:
             }
         }
     }
+
+private:
+    const DominatorTree &dt;
+    QVector<LoopInfo *> loopInfos;
+
+    void createLoopInfos(IR::Function *function)
+    {
+        foreach (BasicBlock *bb, function->basicBlocks()) {
+            if (bb->isRemoved())
+                continue;
+            if (BasicBlock *loopHeader = bb->containingGroup())
+                findLoop(loopHeader)->loopBody.append(bb);
+        }
+
+        foreach (LoopInfo *info, loopInfos) {
+            if (BasicBlock *containingLoopHeader = info->loopHeader->containingGroup())
+                findLoop(containingLoopHeader)->addNestedLoop(info);
+        }
+    }
+
+    LoopInfo *findLoop(BasicBlock *loopHeader)
+    {
+        foreach (LoopInfo *info, loopInfos) {
+            if (info->loopHeader == loopHeader)
+                return info;
+        }
+
+        LoopInfo *info = new LoopInfo;
+        info->loopHeader = loopHeader;
+        loopInfos.append(info);
+        return info;
+    }
 };
 
 // High-level algorithm:
@@ -3460,13 +3564,35 @@ bool tryOptimizingComparison(Expr *&expr)
     return false;
 }
 
-void cfg2dot(IR::Function *f)
+void cfg2dot(IR::Function *f, const QVector<LoopDetection::LoopInfo *> &loops = QVector<LoopDetection::LoopInfo *>())
 {
+    static bool showCode = !qgetenv("QV4_SHOW_IR").isNull();
+    if (!showCode)
+        return;
+
+    struct Util {
+        static void genLoop(LoopDetection::LoopInfo *loop)
+        {
+            qout << "  subgraph \"cluster" << quint64(loop) << "\" {\n";
+            qout << "    L" << loop->loopHeader->index() << ";\n";
+            foreach (BasicBlock *bb, loop->loopBody)
+                qout << "    L" << bb->index() << ";\n";
+            foreach (LoopDetection::LoopInfo *nested, loop->nestedLoops)
+                genLoop(nested);
+            qout << "  }\n";
+        }
+    };
+
     QString name;
     if (f->name) name = *f->name;
     else name = QString::fromLatin1("%1").arg((unsigned long long)f);
     qout << "digraph \"" << name << "\" { ordering=out;\n";
 
+    foreach (LoopDetection::LoopInfo *l, loops) {
+        if (l->parentLoop == 0)
+            Util::genLoop(l);
+    }
+
     foreach (BasicBlock *bb, f->basicBlocks()) {
         if (bb->isRemoved())
             continue;
@@ -4557,7 +4683,7 @@ void Optimizer::run(QQmlEnginePrivate *qmlEngine)
         cleanupBasicBlocks(function);
 //        showMeTheCode(function);
 
-        LoopDetection(df).run();
+        LoopDetection(df).run(function);
         showMeTheCode(function);
 
 //        qout << "Doing block scheduling..." << endl;