diff options
| -rw-r--r-- | src/qml/compiler/qv4codegen.cpp | 122 | ||||
| -rw-r--r-- | src/qml/compiler/qv4codegen_p.h | 14 | ||||
| -rw-r--r-- | src/qml/compiler/qv4jsir.cpp | 4 | ||||
| -rw-r--r-- | src/qml/compiler/qv4jsir_p.h | 6 | ||||
| -rw-r--r-- | src/qml/compiler/qv4ssa.cpp | 226 |
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(); |