V4 IR: (natural) loop detection.

We perform loop detection to be able to assign to each block its loop,
an chain them up from inner loop to outer loop. The new algorithm works
on each basic block just once, and looks at a basic block just the
number of connections it has. As it relies on the dominator tree it is
more robust on actually finding al looping constructs and only those
rather than relying on the statements used. It assumes that a basic
block is analyzed before the one that dominate it (to guarantee finding
outer loop headers before inner loop headers), so blocks are ordered to
work on them in a way that guarantees that, using dominator tree depth,
that is trivially available.

Loop detection allows us to then schedule the loop body before the part
after the loop (the header dominates both so just domination cannot
choose between both), and can be used to optimize loops (either
unrolling the first iteration or hoisting constant parts out of it).

It also helps with generated JavaScript code: in order to simulate gotos
or other unconditional branches, nested labeled do-while(false) loops
are often used in combination with break/continue to "jump" between
"loops".

Change-Id: Idfcc74589e057b191f74880ffd309d0a9c301811
Reviewed-by: Fawzi Mohamed <fawzi.mohamed@digia.com>

1 files changed, 3 insertions, 11 deletions

diff --git a/src/qml/compiler/qv4codegen_p.h b/src/qml/compiler/qv4codegen_p.h
index 0d52fb83fa..cbe8301c09 100644
--- a/src/qml/compiler/qv4codegen_p.h
+++ b/src/qml/compiler/qv4codegen_p.h
@@ -256,28 +256,20 @@ protected:
     struct Loop {
         AST::LabelledStatement *labelledStatement;
         AST::Statement *node;
-        QV4::IR::BasicBlock *groupStartBlock;
         QV4::IR::BasicBlock *breakBlock;
         QV4::IR::BasicBlock *continueBlock;
         Loop *parent;
         ScopeAndFinally *scopeAndFinally;
 
-        Loop(AST::Statement *node, QV4::IR::BasicBlock *groupStartBlock, QV4::IR::BasicBlock *breakBlock, QV4::IR::BasicBlock *continueBlock, Loop *parent)
-            : labelledStatement(0), node(node), groupStartBlock(groupStartBlock), breakBlock(breakBlock), continueBlock(continueBlock), parent(parent) {}
+        Loop(AST::Statement *node, QV4::IR::BasicBlock *breakBlock, QV4::IR::BasicBlock *continueBlock, Loop *parent)
+            : labelledStatement(0), node(node), breakBlock(breakBlock), continueBlock(continueBlock), parent(parent) {}
     };
 
     void enterEnvironment(AST::Node *node);
     void leaveEnvironment();
 
-    void enterLoop(AST::Statement *node, QV4::IR::BasicBlock *startBlock, QV4::IR::BasicBlock *breakBlock, QV4::IR::BasicBlock *continueBlock);
+    void enterLoop(AST::Statement *node, QV4::IR::BasicBlock *breakBlock, QV4::IR::BasicBlock *continueBlock);
     void leaveLoop();
-    QV4::IR::BasicBlock *groupStartBlock() const
-    {
-        for (Loop *it = _loop; it; it = it->parent)
-            if (it->groupStartBlock)
-                return it->groupStartBlock;
-        return 0;
-    }
     QV4::IR::BasicBlock *exceptionHandler() const
     {
         if (_exceptionHandlers.isEmpty())