From 7e5a589b905969a5712b801cec01be257fbc237c Mon Sep 17 00:00:00 2001 From: Erik Verbruggen Date: Wed, 23 Jul 2014 12:17:28 +0200 Subject: V4 IR: add immediate dominator re-calculation. When removing edges, the control-flow graph changes, so some immediate dominators might need to be updated. This change collects all candidates and processes them in a single batch. Change-Id: I928f42232427a84bcb9658e314dadd0bd021b12f Reviewed-by: Fawzi Mohamed --- src/qml/compiler/qv4ssa.cpp | 368 ++++++++++++++++++++++++++++++++------------ 1 file changed, 272 insertions(+), 96 deletions(-) (limited to 'src/qml/compiler/qv4ssa.cpp') diff --git a/src/qml/compiler/qv4ssa.cpp b/src/qml/compiler/qv4ssa.cpp index 9a597952eb..4d1735cffd 100644 --- a/src/qml/compiler/qv4ssa.cpp +++ b/src/qml/compiler/qv4ssa.cpp @@ -339,7 +339,9 @@ class DominatorTree { enum { DebugDominatorFrontiers = 0, - DebugImmediateDominators = 0 + DebugImmediateDominators = 0, + + DebugCodeCanUseLotsOfCpu = 0 }; typedef int BasicBlockIndex; @@ -495,11 +497,6 @@ class DominatorTree } } -#if defined(SHOW_SSA) - for (int i = 0; i < nodes.size(); ++i) - qDebug("\tL%d: ancestor = %d, semi = %d, samedom = %d", i, ancestor[i], semi[i], samedom[i]); -#endif // SHOW_SSA - for (int i = 1; i < d->N; ++i) { BasicBlockIndex n = d->vertex[i]; Q_ASSERT(n != InvalidBasicBlockIndex); @@ -619,26 +616,28 @@ public: } } -#if !defined(QT_NO_DEBUG) && defined(CAN_TAKE_LOSTS_OF_TIME) - foreach (BasicBlock *n, nodes) { - const BasicBlockSet &fBlocks = DF[n->index]; - for (BasicBlockSet::const_iterator it = fBlocks.begin(), eit = fBlocks.end(); it != eit; ++it) { - BasicBlock *fBlock = *it; - Q_ASSERT(!dominates(n, fBlock) || fBlock == n); - bool hasDominatedSucc = false; - foreach (BasicBlock *succ, fBlock->in) { - if (dominates(n, succ)) { - hasDominatedSucc = true; - break; + if (DebugDominatorFrontiers && DebugCodeCanUseLotsOfCpu) { + foreach (BasicBlock *n, function->basicBlocks()) { + if (n->isRemoved()) + continue; + const BasicBlockSet &fBlocks = DF[n->index()]; + for (BasicBlockSet::const_iterator it = fBlocks.begin(), eit = fBlocks.end(); it != eit; ++it) { + BasicBlock *fBlock = *it; + Q_ASSERT(!dominates(n, fBlock) || fBlock == n); + bool hasDominatedSucc = false; + foreach (BasicBlock *succ, fBlock->in) { + if (dominates(n, succ)) { + hasDominatedSucc = true; + break; + } } + if (!hasDominatedSucc) { + qout << fBlock << " in DF[" << n->index() << "] has no dominated predecessors" << endl; + } + Q_ASSERT(hasDominatedSucc); } - if (!hasDominatedSucc) { - qout << fBlock << " in DF[" << n->index << "] has no dominated predecessors" << endl; - } - Q_ASSERT(hasDominatedSucc); } } -#endif // !QT_NO_DEBUG } const BasicBlockSet &dominatorFrontier(BasicBlock *n) const { @@ -671,7 +670,7 @@ public: } } - void updateImmediateDominator(BasicBlock *bb, BasicBlock *newDominator) + void setImmediateDominator(BasicBlock *bb, BasicBlock *newDominator) { Q_ASSERT(bb->index() >= 0); Q_ASSERT(!newDominator || newDominator->index() >= 0); @@ -682,7 +681,33 @@ public: idom.resize(function->basicBlockCount(), InvalidBasicBlockIndex); } - idom[bb->index()] = newDominator ? newDominator->index() : 0; + const BasicBlockIndex newIdx = newDominator ? newDominator->index() : InvalidBasicBlockIndex; + if (DebugImmediateDominators) + qDebug() << "Setting idom of" << bb->index() << "from" << idom[bb->index()] << "to" << newIdx; + idom[bb->index()] = newIdx; + } + + void collectSiblings(BasicBlock *node, BasicBlockSet &siblings) + { + siblings.insert(node); + const BasicBlockIndex dominator = idom[node->index()]; + if (dominator == InvalidBasicBlockIndex) + return; + for (size_t i = 0, ei = idom.size(); i != ei; ++i) { + if (idom[i] == dominator) { + BasicBlock *bb = function->basicBlock(i); + if (!bb->isRemoved()) + siblings.insert(bb); + } + } + } + + void recalculateIDoms(const BasicBlockSet &nodes, BasicBlock *limit = 0) + { + const BasicBlockIndex limitIndex = limit ? limit->index() : InvalidBasicBlockIndex; + BasicBlockSet todo(nodes), postponed(function); + while (!todo.empty()) + recalculateIDom(*todo.begin(), todo, postponed, limitIndex); } bool dominates(BasicBlock *dominator, BasicBlock *dominated) const { @@ -803,6 +828,97 @@ private: return depth; } + + // The immediate-dominator recalculation is used when edges are removed from the CFG. See + // [Ramalingam] for a description. Note that instead of calculating the priority, a recursive + // algorithm is used: when recalculating the immediate dominator of a node by looking for the + // least-common ancestor, and a node is hit that also needs recalculation, a recursive call + // is done to calculate that nodes immediate dominator first. + // + // Note that this simplified algorithm cannot cope with back-edges. It only works for + // non-looping edges (which is our use-case). + void recalculateIDom(BasicBlock *node, BasicBlockSet &todo, BasicBlockSet &postponed, BasicBlockIndex limit) { + Q_ASSERT(!postponed.contains(node)); + Q_ASSERT(todo.contains(node)); + todo.remove(node); + + if (node->in.size() == 1) { + // Special case: if the node has only one incoming edge, then that is the immediate + // dominator. + setImmediateDominator(node, node->in.first()); + return; + } + + std::vector prefix; + prefix.reserve(32); + + for (int i = 0, ei = node->in.size(); i != ei; ++i) { + BasicBlock *in = node->in.at(i); + if (node == in) // back-edge to self + continue; + if (dominates(node->index(), in->index())) // a known back-edge + continue; + + if (prefix.empty()) { + calculatePrefix(node, in, prefix, todo, postponed, limit); + + if (!prefix.empty()) { + std::reverse(prefix.begin(), prefix.end()); + Q_ASSERT(!prefix.empty()); + Q_ASSERT(prefix.front() == limit || limit == InvalidBasicBlockIndex); + } + } else { + std::vector anotherPrefix; + anotherPrefix.reserve(prefix.size()); + calculatePrefix(node, in, anotherPrefix, todo, postponed, limit); + + if (!anotherPrefix.empty()) + commonPrefix(prefix, anotherPrefix); + } + } + + Q_ASSERT(!prefix.empty()); + idom[node->index()] = prefix.back(); + } + + void calculatePrefix(BasicBlock *node, BasicBlock *in, std::vector &prefix, BasicBlockSet &todo, BasicBlockSet &postponed, BasicBlockIndex limit) + { + for (BasicBlockIndex it = in->index(); it != InvalidBasicBlockIndex; it = idom[it]) { + prefix.push_back(it); + if (it == limit) + return; + BasicBlock *n = function->basicBlock(it); + if (postponed.contains(n)) { // possible back-edge, bail out. + prefix.clear(); + return; + } + if (todo.contains(n)) { + postponed.insert(node); + recalculateIDom(n, todo, postponed, limit); + postponed.remove(node); + } + } + } + + // Calculate the LCA (Least Common Ancestor) by finding the longest common prefix between two + // dominator chains. Note that "anotherPrefix" has the node's immediate dominator first, while + // "bestPrefix" has it last (meaning: is in reverse order). The reason for this is that removing + // nodes from "bestPrefix" is cheaper because it's done at the end of the vector, while + // reversing all "anotherPrefix" nodes would take unnecessary time. + static void commonPrefix(std::vector &bestPrefix, const std::vector &anotherPrefix) + { + const size_t anotherSize = anotherPrefix.size(); + size_t minLen = qMin(bestPrefix.size(), anotherPrefix.size()); + while (minLen != 0) { + --minLen; + if (bestPrefix[minLen] == anotherPrefix[anotherSize - minLen - 1]) { + ++minLen; + break; + } + } + if (minLen != bestPrefix.size()) + bestPrefix.erase(bestPrefix.begin() + minLen, bestPrefix.end()); + } }; class VariableCollector: public StmtVisitor, ExprVisitor { @@ -2847,37 +2963,47 @@ protected: void splitCriticalEdges(IR::Function *f, DominatorTree &df, StatementWorklist &worklist, DefUses &defUses) { - foreach (BasicBlock *bb, f->basicBlocks()) { - if (bb->isRemoved()) + foreach (BasicBlock *toBB, f->basicBlocks()) { + if (toBB->isRemoved()) continue; - if (bb->in.size() < 2) + if (toBB->in.size() < 2) continue; - for (int inIdx = 0, eInIdx = bb->in.size(); inIdx != eInIdx; ++inIdx) { - BasicBlock *inBB = bb->in[inIdx]; - if (inBB->out.size() < 2) + for (int inIdx = 0, eInIdx = toBB->in.size(); inIdx != eInIdx; ++inIdx) { + BasicBlock *fromBB = toBB->in[inIdx]; + if (fromBB->out.size() < 2) continue; // We found a critical edge. // create the basic block: - BasicBlock *newBB = f->newBasicBlock(bb->catchBlock); + BasicBlock *newBB = f->newBasicBlock(toBB->catchBlock); Jump *s = f->NewStmt(); worklist.registerNewStatement(s); defUses.registerNewStatement(s); - s->init(bb); + s->init(toBB); newBB->appendStatement(s); // rewire the old outgoing edge - int outIdx = inBB->out.indexOf(bb); - inBB->out[outIdx] = newBB; - newBB->in.append(inBB); + int outIdx = fromBB->out.indexOf(toBB); + fromBB->out[outIdx] = newBB; + newBB->in.append(fromBB); // rewire the old incoming edge - bb->in[inIdx] = newBB; - newBB->out.append(bb); + toBB->in[inIdx] = newBB; + newBB->out.append(toBB); + + BasicBlock *container = 0; + for (container = fromBB->containingGroup(); container; container = container->containingGroup()) { + if (container == toBB || container == toBB->containingGroup()) + break; + } + if (container == 0) + container = fromBB->containingGroup(); + + newBB->setContainingGroup(container); // patch the terminator - Stmt *terminator = inBB->terminator(); + Stmt *terminator = fromBB->terminator(); if (Jump *j = terminator->asJump()) { Q_ASSERT(outIdx == 0); j->target = newBB; @@ -2894,8 +3020,21 @@ void splitCriticalEdges(IR::Function *f, DominatorTree &df, StatementWorklist &w Q_ASSERT(!"Unknown terminator!"); } +// qDebug() << "splitting edge" << fromBB->index() << "->" << toBB->index() +// << "by inserting block" << newBB->index(); + // Set the immediate dominator of the new block to inBB - df.updateImmediateDominator(newBB, inBB); + df.setImmediateDominator(newBB, fromBB); + + bool toNeedsNewIdom = true; + foreach (BasicBlock *bb, toBB->in) { + if (bb != newBB && !df.dominates(toBB, bb)) { + toNeedsNewIdom = false; + break; + } + } + if (toNeedsNewIdom) + df.setImmediateDominator(toBB, newBB); } } } @@ -3509,78 +3648,113 @@ namespace { /// This function removes the basic-block from the function's list, unlinks any uses and/or defs, /// and removes unreachable staements from the worklist, so that optimiseSSA won't consider them /// anymore. -/// Important: this assumes that there are no critical edges in the control-flow graph! -void purgeBB(BasicBlock *bb, IR::Function *func, DefUses &defUses, StatementWorklist &W, - DominatorTree &df) +void unlink(BasicBlock *from, BasicBlock *to, IR::Function *func, DefUses &defUses, + StatementWorklist &W, DominatorTree &dt) { - // TODO: after the change above: if we keep on detaching the block from predecessors or - // successors, update the DominatorTree too. + struct Util { + static void removeIncomingEdge(BasicBlock *from, BasicBlock *to, DefUses &defUses, StatementWorklist &W) + { + int idx = to->in.indexOf(from); + if (idx == -1) + return; + + to->in.remove(idx); + foreach (Stmt *outStmt, to->statements()) { + if (!outStmt) + continue; + if (Phi *phi = outStmt->asPhi()) { + if (Temp *t = phi->d->incoming[idx]->asTemp()) { + defUses.removeUse(phi, *t); + W += defUses.defStmt(*t); + } + phi->d->incoming.remove(idx); + W += phi; + } else { + break; + } + } + } + + static bool isReachable(BasicBlock *bb, const DominatorTree &dt) + { + foreach (BasicBlock *in, bb->in) { + if (in->isRemoved()) + continue; + if (dt.dominates(bb, in)) // a back-edge, not interesting + continue; + return true; + } + + return false; + } + }; // don't purge blocks that are entry points for catch statements. They might not be directly // connected, but are required anyway - if (bb->isExceptionHandler()) + if (to->isExceptionHandler()) return; - QVector toPurge; - toPurge.reserve(8); - toPurge.append(bb); + // First, unlink the edge + from->out.removeOne(to); + Util::removeIncomingEdge(from, to, defUses, W); - while (!toPurge.isEmpty()) { - bb = toPurge.first(); - toPurge.removeFirst(); + BasicBlockSet siblings; + siblings.init(func); - if (bb->isRemoved()) - continue; + // Check if the target is still reachable... + if (Util::isReachable(to, dt)) { // yes, recalculate the immediate dominator, and we're done. + dt.collectSiblings(to, siblings); + } else { + // The target is unreachable, so purge it: + QVector toPurge; + toPurge.reserve(8); + toPurge.append(to); + while (!toPurge.isEmpty()) { + BasicBlock *bb = toPurge.first(); + toPurge.removeFirst(); - // unlink all incoming edges - foreach (BasicBlock *in, bb->in) { - int idx = in->out.indexOf(bb); - if (idx != -1) - in->out.remove(idx); - } + if (bb->isRemoved()) + continue; - // unlink all outgoing edges, including "arguments" to phi statements - foreach (BasicBlock *out, bb->out) { - int idx = out->in.indexOf(bb); - if (idx != -1) { - out->in.remove(idx); - foreach (Stmt *outStmt, out->statements()) { - if (!outStmt) - continue; - if (Phi *phi = outStmt->asPhi()) { - if (Temp *t = phi->d->incoming[idx]->asTemp()) { - defUses.removeUse(phi, *t); - W += defUses.defStmt(*t); - } - phi->d->incoming.remove(idx); - W += phi; - } else - break; - } + // unlink all incoming edges + foreach (BasicBlock *in, bb->in) { + int idx = in->out.indexOf(bb); + if (idx != -1) + in->out.remove(idx); } - if (out->in.isEmpty()) { - // if a successor has no incoming edges after unlinking the current basic block, then - // it is unreachable, and can be purged too - toPurge.append(out); - } else if (out->in.size() == 1) { - // if the successor now has only one incoming edge, we that edge is the new - // immediate dominator - df.updateImmediateDominator(out, out->in.first()); + // unlink all outgoing edges, including "arguments" to phi statements + foreach (BasicBlock *out, bb->out) { + if (out->isRemoved()) + continue; + + Util::removeIncomingEdge(bb, out, defUses, W); + + if (Util::isReachable(out, dt)) { + dt.collectSiblings(out, siblings); + } else { + // if a successor has no incoming edges after unlinking the current basic block, + // then it is unreachable, and can be purged too + toPurge.append(out); + } } - } - // unlink all defs/uses from the statements in the basic block - foreach (Stmt *s, bb->statements()) { - if (!s) - continue; + // unlink all defs/uses from the statements in the basic block + foreach (Stmt *s, bb->statements()) { + if (!s) + continue; - W += defUses.removeDefUses(s); - W -= s; - } + W += defUses.removeDefUses(s); + W -= s; + } - func->removeBasicBlock(bb); + siblings.remove(bb); + dt.setImmediateDominator(bb, 0); + func->removeBasicBlock(bb); + } } + + dt.recalculateIDoms(siblings); } bool tryOptimizingComparison(Expr *&expr) @@ -3973,10 +4147,10 @@ void optimizeSSA(StatementWorklist &W, DefUses &defUses, DominatorTree &df) W.registerNewStatement(jump); if (convertToValue(constantCondition).toBoolean()) { jump->target = cjump->iftrue; - purgeBB(cjump->iffalse, function, defUses, W, df); + unlink(cjump->parent, cjump->iffalse, function, defUses, W, df); } else { jump->target = cjump->iffalse; - purgeBB(cjump->iftrue, function, defUses, W, df); + unlink(cjump->parent, cjump->iftrue, function, defUses, W, df); } W.replace(s, jump); @@ -5065,3 +5239,5 @@ MoveMapping::Action MoveMapping::schedule(const Move &m, QList &todo, QLis // Construction and Destruction of Static Single Assignment Form. // [Appel] A.W. Appel. Modern Compiler Implementation in Java. Second edition, Cambridge // University Press. +// [Ramalingam] G. Ramalingam and T. Reps. An Incremental Algorithm for Maintaining the Dominator +// Tree of a Reducible Flowgraph. -- cgit v1.2.3