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>

5 files changed, 291 insertions, 81 deletions

diff --git a/src/qml/compiler/qv4codegen.cpp b/src/qml/compiler/qv4codegen.cpp
index 421dcf6775..2d45543305 100644
--- a/src/qml/compiler/qv4codegen.cpp
+++ b/src/qml/compiler/qv4codegen.cpp
@@ -487,11 +487,9 @@ void Codegen::leaveEnvironment()
     _env = _env->parent;
 }
 
-void Codegen::enterLoop(Statement *node, IR::BasicBlock *startBlock, IR::BasicBlock *breakBlock, IR::BasicBlock *continueBlock)
+void Codegen::enterLoop(Statement *node, IR::BasicBlock *breakBlock, IR::BasicBlock *continueBlock)
 {
-    if (startBlock)
-        startBlock->markAsGroupStart();
-    _loop = new Loop(node, startBlock, breakBlock, continueBlock, _loop);
+    _loop = new Loop(node, breakBlock, continueBlock, _loop);
     _loop->labelledStatement = _labelledStatement; // consume the enclosing labelled statement
     _loop->scopeAndFinally = _scopeAndFinally;
     _labelledStatement = 0;
@@ -1127,13 +1125,13 @@ bool Codegen::visit(BinaryExpression *ast)
 
     if (ast->op == QSOperator::And) {
         if (_expr.accept(cx)) {
-            IR::BasicBlock *iftrue = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
+            IR::BasicBlock *iftrue = _function->newBasicBlock(exceptionHandler());
             condition(ast->left, iftrue, _expr.iffalse);
             _block = iftrue;
             condition(ast->right, _expr.iftrue, _expr.iffalse);
         } else {
-            IR::BasicBlock *iftrue = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
-            IR::BasicBlock *endif = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
+            IR::BasicBlock *iftrue = _function->newBasicBlock(exceptionHandler());
+            IR::BasicBlock *endif = _function->newBasicBlock(exceptionHandler());
 
             const unsigned r = _block->newTemp();
 
@@ -1149,13 +1147,13 @@ bool Codegen::visit(BinaryExpression *ast)
         return false;
     } else if (ast->op == QSOperator::Or) {
         if (_expr.accept(cx)) {
-            IR::BasicBlock *iffalse = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
+            IR::BasicBlock *iffalse = _function->newBasicBlock(exceptionHandler());
             condition(ast->left, _expr.iftrue, iffalse);
             _block = iffalse;
             condition(ast->right, _expr.iftrue, _expr.iffalse);
         } else {
-            IR::BasicBlock *iffalse = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
-            IR::BasicBlock *endif = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
+            IR::BasicBlock *iffalse = _function->newBasicBlock(exceptionHandler());
+            IR::BasicBlock *endif = _function->newBasicBlock(exceptionHandler());
 
             const unsigned r = _block->newTemp();
             move(_block->TEMP(r), *expression(ast->left));
@@ -1318,9 +1316,9 @@ bool Codegen::visit(ConditionalExpression *ast)
     if (hasError)
         return true;
 
-    IR::BasicBlock *iftrue = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
-    IR::BasicBlock *iffalse = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
-    IR::BasicBlock *endif = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
+    IR::BasicBlock *iftrue = _function->newBasicBlock(exceptionHandler());
+    IR::BasicBlock *iffalse = _function->newBasicBlock(exceptionHandler());
+    IR::BasicBlock *endif = _function->newBasicBlock(exceptionHandler());
 
     const unsigned t = _block->newTemp();
 
@@ -1950,8 +1948,8 @@ int Codegen::defineFunction(const QString &name, AST::Node *ast,
     IR::Function *function = _module->newFunction(name, _function);
     int functionIndex = _module->functions.count() - 1;
 
-    IR::BasicBlock *entryBlock = function->newBasicBlock(groupStartBlock(), 0);
-    IR::BasicBlock *exitBlock = function->newBasicBlock(groupStartBlock(), 0, IR::Function::DontInsertBlock);
+    IR::BasicBlock *entryBlock = function->newBasicBlock(0);
+    IR::BasicBlock *exitBlock = function->newBasicBlock(0, IR::Function::DontInsertBlock);
     function->hasDirectEval = _env->hasDirectEval || _env->compilationMode == EvalCode;
     function->usesArgumentsObject = _env->parent && (_env->usesArgumentsObject == Environment::ArgumentsObjectUsed);
     function->usesThis = _env->usesThis;
@@ -2165,11 +2163,11 @@ bool Codegen::visit(DoWhileStatement *ast)
     if (hasError)
         return true;
 
-    IR::BasicBlock *loopbody = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
-    IR::BasicBlock *loopcond = _function->newBasicBlock(loopbody, exceptionHandler());
-    IR::BasicBlock *loopend = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
+    IR::BasicBlock *loopbody = _function->newBasicBlock(exceptionHandler());
+    IR::BasicBlock *loopcond = _function->newBasicBlock(exceptionHandler());
+    IR::BasicBlock *loopend = _function->newBasicBlock(exceptionHandler());
 
-    enterLoop(ast, loopbody, loopend, loopcond);
+    enterLoop(ast, loopend, loopcond);
 
     _block->JUMP(loopbody);
 
@@ -2215,9 +2213,9 @@ bool Codegen::visit(ForEachStatement *ast)
     if (hasError)
         return true;
 
-    IR::BasicBlock *foreachin = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
-    IR::BasicBlock *foreachbody = _function->newBasicBlock(foreachin, exceptionHandler());
-    IR::BasicBlock *foreachend = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
+    IR::BasicBlock *foreachin = _function->newBasicBlock(exceptionHandler());
+    IR::BasicBlock *foreachbody = _function->newBasicBlock(exceptionHandler());
+    IR::BasicBlock *foreachend = _function->newBasicBlock(exceptionHandler());
 
     int objectToIterateOn = _block->newTemp();
     move(_block->TEMP(objectToIterateOn), *expression(ast->expression));
@@ -2227,7 +2225,7 @@ bool Codegen::visit(ForEachStatement *ast)
     int iterator = _block->newTemp();
     move(_block->TEMP(iterator), _block->CALL(_block->NAME(IR::Name::builtin_foreach_iterator_object, 0, 0), args));
 
-    enterLoop(ast, foreachin, foreachend, foreachin);
+    enterLoop(ast, foreachend, foreachin);
     _block->JUMP(foreachin);
 
     _block = foreachbody;
@@ -2255,15 +2253,15 @@ bool Codegen::visit(ForStatement *ast)
     if (hasError)
         return true;
 
-    IR::BasicBlock *forcond = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
-    IR::BasicBlock *forbody = _function->newBasicBlock(forcond, exceptionHandler());
-    IR::BasicBlock *forstep = _function->newBasicBlock(forcond, exceptionHandler());
-    IR::BasicBlock *forend = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
+    IR::BasicBlock *forcond = _function->newBasicBlock(exceptionHandler());
+    IR::BasicBlock *forbody = _function->newBasicBlock(exceptionHandler());
+    IR::BasicBlock *forstep = _function->newBasicBlock(exceptionHandler());
+    IR::BasicBlock *forend = _function->newBasicBlock(exceptionHandler());
 
     statement(ast->initialiser);
     _block->JUMP(forcond);
 
-    enterLoop(ast, forcond, forend, forstep);
+    enterLoop(ast, forend, forstep);
 
     _block = forcond;
     if (ast->condition)
@@ -2291,9 +2289,9 @@ bool Codegen::visit(IfStatement *ast)
     if (hasError)
         return true;
 
-    IR::BasicBlock *iftrue = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
-    IR::BasicBlock *iffalse = ast->ko ? _function->newBasicBlock(groupStartBlock(), exceptionHandler()) : 0;
-    IR::BasicBlock *endif = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
+    IR::BasicBlock *iftrue = _function->newBasicBlock(exceptionHandler());
+    IR::BasicBlock *iffalse = ast->ko ? _function->newBasicBlock(exceptionHandler()) : 0;
+    IR::BasicBlock *endif = _function->newBasicBlock(exceptionHandler());
 
     condition(ast->expression, iftrue, ast->ko ? iffalse : endif);
 
@@ -2338,8 +2336,8 @@ bool Codegen::visit(LabelledStatement *ast)
             AST::cast<AST::LocalForEachStatement *>(ast->statement)) {
         statement(ast->statement); // labelledStatement will be associated with the ast->statement's loop.
     } else {
-        IR::BasicBlock *breakBlock = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
-        enterLoop(ast->statement, 0, breakBlock, /*continueBlock*/ 0);
+        IR::BasicBlock *breakBlock = _function->newBasicBlock(exceptionHandler());
+        enterLoop(ast->statement, breakBlock, /*continueBlock*/ 0);
         statement(ast->statement);
         _block->JUMP(breakBlock);
         _block = breakBlock;
@@ -2354,9 +2352,9 @@ bool Codegen::visit(LocalForEachStatement *ast)
     if (hasError)
         return true;
 
-    IR::BasicBlock *foreachin = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
-    IR::BasicBlock *foreachbody = _function->newBasicBlock(foreachin, exceptionHandler());
-    IR::BasicBlock *foreachend = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
+    IR::BasicBlock *foreachin = _function->newBasicBlock(exceptionHandler());
+    IR::BasicBlock *foreachbody = _function->newBasicBlock(exceptionHandler());
+    IR::BasicBlock *foreachend = _function->newBasicBlock(exceptionHandler());
 
     variableDeclaration(ast->declaration);
 
@@ -2367,7 +2365,7 @@ bool Codegen::visit(LocalForEachStatement *ast)
     move(_block->TEMP(iterator), _block->CALL(_block->NAME(IR::Name::builtin_foreach_iterator_object, 0, 0), args));
 
     _block->JUMP(foreachin);
-    enterLoop(ast, foreachin, foreachend, foreachin);
+    enterLoop(ast, foreachend, foreachin);
 
     _block = foreachbody;
     int temp = _block->newTemp();
@@ -2394,15 +2392,15 @@ bool Codegen::visit(LocalForStatement *ast)
     if (hasError)
         return true;
 
-    IR::BasicBlock *forcond = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
-    IR::BasicBlock *forbody = _function->newBasicBlock(forcond, exceptionHandler());
-    IR::BasicBlock *forstep = _function->newBasicBlock(forcond, exceptionHandler());
-    IR::BasicBlock *forend = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
+    IR::BasicBlock *forcond = _function->newBasicBlock(exceptionHandler());
+    IR::BasicBlock *forbody = _function->newBasicBlock(exceptionHandler());
+    IR::BasicBlock *forstep = _function->newBasicBlock(exceptionHandler());
+    IR::BasicBlock *forend = _function->newBasicBlock(exceptionHandler());
 
     variableDeclarationList(ast->declarations);
     _block->JUMP(forcond);
 
-    enterLoop(ast, forcond, forend, forstep);
+    enterLoop(ast, forend, forstep);
 
     _block = forcond;
     if (ast->condition)
@@ -2449,22 +2447,22 @@ bool Codegen::visit(SwitchStatement *ast)
     if (hasError)
         return true;
 
-    IR::BasicBlock *switchend = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
+    IR::BasicBlock *switchend = _function->newBasicBlock(exceptionHandler());
 
     if (ast->block) {
         Result lhs = expression(ast->expression);
-        IR::BasicBlock *switchcond = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
+        IR::BasicBlock *switchcond = _function->newBasicBlock(exceptionHandler());
         _block->JUMP(switchcond);
         IR::BasicBlock *previousBlock = 0;
 
         QHash<Node *, IR::BasicBlock *> blockMap;
 
-        enterLoop(ast, 0, switchend, 0);
+        enterLoop(ast, switchend, 0);
 
         for (CaseClauses *it = ast->block->clauses; it; it = it->next) {
             CaseClause *clause = it->clause;
 
-            _block = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
+            _block = _function->newBasicBlock(exceptionHandler());
             blockMap[clause] = _block;
 
             if (previousBlock && !previousBlock->isTerminated())
@@ -2477,7 +2475,7 @@ bool Codegen::visit(SwitchStatement *ast)
         }
 
         if (ast->block->defaultClause) {
-            _block = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
+            _block = _function->newBasicBlock(exceptionHandler());
             blockMap[ast->block->defaultClause] = _block;
 
             if (previousBlock && !previousBlock->isTerminated())
@@ -2492,7 +2490,7 @@ bool Codegen::visit(SwitchStatement *ast)
         for (CaseClauses *it = ast->block->moreClauses; it; it = it->next) {
             CaseClause *clause = it->clause;
 
-            _block = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
+            _block = _function->newBasicBlock(exceptionHandler());
             blockMap[clause] = _block;
 
             if (previousBlock && !previousBlock->isTerminated())
@@ -2513,7 +2511,7 @@ bool Codegen::visit(SwitchStatement *ast)
             CaseClause *clause = it->clause;
             Result rhs = expression(clause->expression);
             IR::BasicBlock *iftrue = blockMap[clause];
-            IR::BasicBlock *iffalse = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
+            IR::BasicBlock *iffalse = _function->newBasicBlock(exceptionHandler());
             cjump(binop(IR::OpStrictEqual, *lhs, *rhs), iftrue, iffalse);
             _block = iffalse;
         }
@@ -2522,7 +2520,7 @@ bool Codegen::visit(SwitchStatement *ast)
             CaseClause *clause = it->clause;
             Result rhs = expression(clause->expression);
             IR::BasicBlock *iftrue = blockMap[clause];
-            IR::BasicBlock *iffalse = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
+            IR::BasicBlock *iffalse = _function->newBasicBlock(exceptionHandler());
             cjump(binop(IR::OpStrictEqual, *lhs, *rhs), iftrue, iffalse);
             _block = iffalse;
         }
@@ -2571,16 +2569,16 @@ bool Codegen::visit(TryStatement *ast)
     IR::BasicBlock *finallyBody = 0;
     IR::BasicBlock *catchBody = 0;
     IR::BasicBlock *catchExceptionHandler = 0;
-    IR::BasicBlock *end = _function->newBasicBlock(groupStartBlock(), surroundingExceptionHandler, IR::Function::DontInsertBlock);
+    IR::BasicBlock *end = _function->newBasicBlock(surroundingExceptionHandler, IR::Function::DontInsertBlock);
 
     if (ast->finallyExpression)
-        finallyBody = _function->newBasicBlock(groupStartBlock(), surroundingExceptionHandler, IR::Function::DontInsertBlock);
+        finallyBody = _function->newBasicBlock(surroundingExceptionHandler, IR::Function::DontInsertBlock);
 
     if (ast->catchExpression) {
         // exception handler for the catch body
-        catchExceptionHandler = _function->newBasicBlock(groupStartBlock(), 0, IR::Function::DontInsertBlock);
+        catchExceptionHandler = _function->newBasicBlock(0, IR::Function::DontInsertBlock);
         pushExceptionHandler(catchExceptionHandler);
-        catchBody =  _function->newBasicBlock(groupStartBlock(), catchExceptionHandler, IR::Function::DontInsertBlock);
+        catchBody =  _function->newBasicBlock(catchExceptionHandler, IR::Function::DontInsertBlock);
         popExceptionHandler();
         pushExceptionHandler(catchBody);
     } else {
@@ -2588,7 +2586,7 @@ bool Codegen::visit(TryStatement *ast)
         pushExceptionHandler(finallyBody);
     }
 
-    IR::BasicBlock *tryBody = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
+    IR::BasicBlock *tryBody = _function->newBasicBlock(exceptionHandler());
     _block->JUMP(tryBody);
 
     ScopeAndFinally tcf(_scopeAndFinally, ast->finallyExpression);
@@ -2693,11 +2691,11 @@ bool Codegen::visit(WhileStatement *ast)
     if (hasError)
         return true;
 
-    IR::BasicBlock *whilecond = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
-    IR::BasicBlock *whilebody = _function->newBasicBlock(whilecond, exceptionHandler());
-    IR::BasicBlock *whileend = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
+    IR::BasicBlock *whilecond = _function->newBasicBlock(exceptionHandler());
+    IR::BasicBlock *whilebody = _function->newBasicBlock(exceptionHandler());
+    IR::BasicBlock *whileend = _function->newBasicBlock(exceptionHandler());
 
-    enterLoop(ast, whilecond, whileend, whilecond);
+    enterLoop(ast, whileend, whilecond);
 
     _block->JUMP(whilecond);
     _block = whilecond;
@@ -2721,7 +2719,7 @@ bool Codegen::visit(WithStatement *ast)
     _function->hasWith = true;
 
     // need an exception handler for with to cleanup the with scope
-    IR::BasicBlock *withExceptionHandler = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
+    IR::BasicBlock *withExceptionHandler = _function->newBasicBlock(exceptionHandler());
     withExceptionHandler->EXP(withExceptionHandler->CALL(withExceptionHandler->NAME(IR::Name::builtin_pop_scope, 0, 0), 0));
     if (!exceptionHandler())
         withExceptionHandler->EXP(withExceptionHandler->CALL(withExceptionHandler->NAME(IR::Name::builtin_rethrow, 0, 0), 0));
@@ -2730,7 +2728,7 @@ bool Codegen::visit(WithStatement *ast)
 
     pushExceptionHandler(withExceptionHandler);
 
-    IR::BasicBlock *withBlock = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
+    IR::BasicBlock *withBlock = _function->newBasicBlock(exceptionHandler());
 
     _block->JUMP(withBlock);
     _block = withBlock;
@@ -2751,7 +2749,7 @@ bool Codegen::visit(WithStatement *ast)
     _block->EXP(_block->CALL(_block->NAME(IR::Name::builtin_pop_scope, 0, 0), 0));
     popExceptionHandler();
 
-    IR::BasicBlock *next = _function->newBasicBlock(groupStartBlock(), exceptionHandler());
+    IR::BasicBlock *next = _function->newBasicBlock(exceptionHandler());
     _block->JUMP(next);
     _block = next;
 
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())
diff --git a/src/qml/compiler/qv4jsir.cpp b/src/qml/compiler/qv4jsir.cpp
index aa3769be46..5bebfb3caf 100644
--- a/src/qml/compiler/qv4jsir.cpp
+++ b/src/qml/compiler/qv4jsir.cpp
@@ -436,9 +436,9 @@ const QString *Function::newString(const QString &text)
     return &*strings.insert(text);
 }
 
-BasicBlock *Function::newBasicBlock(BasicBlock *containingLoop, BasicBlock *catchBlock, BasicBlockInsertMode mode)
+BasicBlock *Function::newBasicBlock(BasicBlock *catchBlock, BasicBlockInsertMode mode)
 {
-    BasicBlock *block = new BasicBlock(this, containingLoop, catchBlock);
+    BasicBlock *block = new BasicBlock(this, catchBlock);
     return mode == InsertBlock ? addBasicBlock(block) : block;
 }
 
diff --git a/src/qml/compiler/qv4jsir_p.h b/src/qml/compiler/qv4jsir_p.h
index 9dd113efc4..4bff15ddce 100644
--- a/src/qml/compiler/qv4jsir_p.h
+++ b/src/qml/compiler/qv4jsir_p.h
@@ -783,10 +783,10 @@ public:
     QVector<BasicBlock *> out;
     QQmlJS::AST::SourceLocation nextLocation;
 
-    BasicBlock(Function *function, BasicBlock *containingLoop, BasicBlock *catcher)
+    BasicBlock(Function *function, BasicBlock *catcher)
         : function(function)
         , catchBlock(catcher)
-        , _containingGroup(containingLoop)
+        , _containingGroup(0)
         , _index(-1)
         , _isExceptionHandler(false)
         , _groupStart(false)
@@ -1013,7 +1013,7 @@ struct Function {
         DontInsertBlock
     };
 
-    BasicBlock *newBasicBlock(BasicBlock *containingLoop, BasicBlock *catchBlock, BasicBlockInsertMode mode = InsertBlock);
+    BasicBlock *newBasicBlock(BasicBlock *catchBlock, BasicBlockInsertMode mode = InsertBlock);
     const QString *newString(const QString &text);
 
     void RECEIVE(const QString &name) { formals.append(newString(name)); }
diff --git a/src/qml/compiler/qv4ssa.cpp b/src/qml/compiler/qv4ssa.cpp
index b3240b987f..eb9e818bac 100644
--- a/src/qml/compiler/qv4ssa.cpp
+++ b/src/qml/compiler/qv4ssa.cpp
@@ -583,6 +583,53 @@ public:
         return dominates(dominator->index(), dominated->index());
     }
 
+    // Calculate a depth-first iteration order on the nodes of the dominator tree.
+    //
+    // The order of the nodes in the vector is not the same as one where a recursive depth-first
+    // iteration is done on a tree. Rather, the nodes are (reverse) sorted on tree depth.
+    // So for the:
+    //    1 dominates 2
+    //    2 dominates 3
+    //    3 dominates 4
+    //    2 dominates 5
+    // the order will be:
+    //    4, 3, 5, 2, 1
+    // or:
+    //    4, 5, 3, 2, 1
+    // So the order of nodes on the same depth is undefined, but it will be after the nodes
+    // they dominate, and before the nodes that dominate them.
+    //
+    // The reason for this order is that a proper DFS pre-/post-order would require inverting
+    // the idom vector by either building a real tree datastructure or by searching the idoms
+    // for siblings and children. Both have a higher time complexity than sorting by depth.
+    QVector<BasicBlock *> calculateDFNodeIterOrder() const
+    {
+        std::vector<int> depths = calculateNodeDepths();
+        struct Cmp {
+            std::vector<int> *nodeDepths;
+            Cmp(std::vector<int> *nodeDepths)
+                : nodeDepths(nodeDepths)
+            { Q_ASSERT(nodeDepths); }
+            bool operator()(BasicBlock *one, BasicBlock *two) const
+            {
+                if (one->isRemoved())
+                    return false;
+                if (two->isRemoved())
+                    return true;
+                return nodeDepths->at(one->index()) > nodeDepths->at(two->index());
+            }
+        };
+        QVector<BasicBlock *> order = function->basicBlocks();
+        std::sort(order.begin(), order.end(), Cmp(&depths));
+        for (int i = 0; i < order.size(); ) {
+            if (order[i]->isRemoved())
+                order.remove(i);
+            else
+                ++i;
+        }
+        return order;
+    }
+
 private:
     bool dominates(BasicBlockIndex dominator, BasicBlockIndex dominated) const {
         // dominator can be Invalid when the dominated block has no dominator (i.e. the start node)
@@ -598,6 +645,57 @@ private:
 
         return false;
     }
+
+    // Algorithm:
+    //  - for each node:
+    //    - get the depth of a node. If it's unknown (-1):
+    //      - get the depth of the immediate dominator.
+    //      - if that's unknown too, calculate it by calling calculateNodeDepth
+    //      - set the current node's depth to that of immediate dominator + 1
+    std::vector<int> calculateNodeDepths() const
+    {
+        std::vector<int> nodeDepths(function->basicBlockCount(), -1);
+        nodeDepths[0] = 0;
+        foreach (BasicBlock *bb, function->basicBlocks()) {
+            if (bb->isRemoved())
+                continue;
+
+            int &bbDepth = nodeDepths[bb->index()];
+            if (bbDepth == -1) {
+                const int immDom = idom[bb->index()];
+                int immDomDepth = nodeDepths[immDom];
+                if (immDomDepth == -1)
+                    immDomDepth = calculateNodeDepth(immDom, nodeDepths);
+                bbDepth = immDomDepth + 1;
+            }
+        }
+        return nodeDepths;
+    }
+
+    // Algorithm:
+    //   - search for the first dominator of a node that has a known depth. As all nodes are
+    //     reachable from the start node, and that node's depth is 0, this is finite.
+    //   - while doing that search, put all unknown nodes in the worklist
+    //   - pop all nodes from the worklist, and set their depth to the previous' (== dominating)
+    //     node's depth + 1
+    // This way every node's depth is calculated once, and the complexity is O(n).
+    int calculateNodeDepth(int nodeIdx, std::vector<int> &nodeDepths) const
+    {
+        std::vector<int> worklist;
+        worklist.reserve(8);
+        int depth = -1;
+
+        do {
+            worklist.push_back(nodeIdx);
+            nodeIdx = idom[nodeIdx];
+            depth = nodeDepths[nodeIdx];
+        } while (depth == -1);
+
+        for (std::vector<int>::const_reverse_iterator it = worklist.rbegin(), eit = worklist.rend(); it != eit; ++it)
+            nodeDepths[*it] = ++depth;
+
+        return depth;
+    }
 };
 
 class VariableCollector: public StmtVisitor, ExprVisitor {
@@ -2643,10 +2741,8 @@ void splitCriticalEdges(IR::Function *f, DominatorTree &df, StatementWorklist &w
                 continue;
 
             // We found a critical edge.
-            BasicBlock *containingGroup = inBB->isGroupStart() ? inBB : inBB->containingGroup();
-
             // create the basic block:
-            BasicBlock *newBB = f->newBasicBlock(containingGroup, bb->catchBlock);
+            BasicBlock *newBB = f->newBasicBlock(bb->catchBlock);
             Jump *s = f->NewStmt<Jump>();
             worklist.registerNewStatement(s);
             defUses.registerNewStatement(s);
@@ -2686,6 +2782,127 @@ void splitCriticalEdges(IR::Function *f, DominatorTree &df, StatementWorklist &w
     }
 }
 
+// Detect all (sub-)loops in a function.
+//
+// Doing loop detection on the CFG is better than relying on the statement information in
+// order to mark loops. Although JavaScript only has natural loops, it can still be the case
+// that something is not a loop even though a loop-like-statement is in the source. For
+// example:
+//    while (true) {
+//      if (i > 0)
+//        break;
+//      else
+//        break;
+//    }
+//
+// Algorithm:
+//  - do a DFS on the dominator tree, where for each node:
+//    - collect all back-edges
+//    - if there are back-edges, the node is a loop-header for a new loop, so:
+//      - walk the CFG is reverse-direction, and for every node:
+//        - if the node already belongs to a loop, we've found a nested loop:
+//          - get the loop-header for the (outermost) nested loop
+//          - add that loop-header to the current loop
+//          - continue by walking all incoming edges that do not yet belong to the current loop
+//        - if the node does not belong to a loop yet, add it to the current loop, and
+//          go on with all incoming edges
+//
+// Loop-header detection by checking for back-edges is very straight forward: a back-edge is
+// an incoming edge where the other node is dominated by the current node. Meaning: all
+// execution paths that reach that other node have to go through the current node, that other
+// node ends with a (conditional) jump back to the loop header.
+//
+// The exact order of the DFS on the dominator tree is not important. The only property has to
+// be that a node is only visited when all the nodes it dominates have been visited before.
+// The reason for the DFS is that for nested loops, the inner loop's loop-header is dominated
+// by the outer loop's header. So, by visiting depth-first, sub-loops are identified before
+// their containing loops, which makes nested-loop identification free. An added benefit is
+// that the nodes for those sub-loops are only processed once.
+//
+// Note: independent loops that share the same header are merged together. For example, in
+// the code snippet below, there are 2 back-edges into the loop-header, but only one single
+// loop will be detected.
+//    while (a) {
+//      if (b)
+//        continue;
+//      else
+//        continue;
+//    }
+class LoopDetection
+{
+    const DominatorTree &dt;
+
+    Q_DISABLE_COPY(LoopDetection)
+
+public:
+    LoopDetection(const DominatorTree &dt)
+        : dt(dt)
+    {}
+
+    void run()
+    {
+        foreach (BasicBlock *bb, dt.calculateDFNodeIterOrder()) {
+            Q_ASSERT(!bb->isRemoved());
+
+            std::vector<BasicBlock *> backedges;
+            backedges.reserve(4);
+
+            foreach (BasicBlock *in, bb->in)
+                if (dt.dominates(bb, in))
+                    backedges.push_back(in);
+
+            if (!backedges.empty()) {
+                subLoop(bb, backedges);
+            }
+        }
+    }
+
+private:
+    void subLoop(BasicBlock *loopHead, const std::vector<BasicBlock *> &backedges)
+    {
+        loopHead->markAsGroupStart();
+
+        std::vector<BasicBlock *> worklist(backedges.begin(), backedges.end());
+        while (!worklist.empty()) {
+            BasicBlock *predIt = worklist.back();
+            worklist.pop_back();
+
+            BasicBlock *subloop = predIt->containingGroup();
+            if (subloop) {
+                // This is a discovered block. Find its outermost discovered loop.
+                while (BasicBlock *parentLoop = subloop->containingGroup())
+                  subloop = parentLoop;
+
+                // If it is already discovered to be a subloop of this loop, continue.
+                if (subloop == loopHead)
+                    continue;
+
+                // Yay, it's a subloop of this loop.
+                subloop->setContainingGroup(loopHead);
+                predIt = subloop;
+
+                // Add all predecessors of the subloop header to the worklist, as long as
+                // those predecessors are not in the current subloop. It might be the case
+                // that they are in other loops, which we will then add as a subloop to the
+                // current loop.
+                foreach (BasicBlock *predIn, predIt->in)
+                    if (predIn->containingGroup() != subloop)
+                        worklist.push_back(predIn);
+            } else {
+                if (predIt == loopHead)
+                    continue;
+
+                // This is an undiscovered block. Map it to the current loop.
+                predIt->setContainingGroup(loopHead);
+
+                // Add all incoming edges to the worklist.
+                foreach (BasicBlock *bb, predIt->in)
+                    worklist.push_back(bb);
+            }
+        }
+    }
+};
+
 // High-level algorithm:
 //  0. start with the first node (the start node) of a function
 //  1. emit the node
@@ -4088,6 +4305,9 @@ void Optimizer::run(QQmlEnginePrivate *qmlEngine)
         cleanupBasicBlocks(function);
 //        showMeTheCode(function);
 
+        LoopDetection(df).run();
+        showMeTheCode(function);
+
 //        qout << "Doing block scheduling..." << endl;
 //        df.dumpImmediateDominators();
         startEndLoops = BlockScheduler(function, df).go();