From da31479ee237a40ed03bcaf1352f00d33d1f325c Mon Sep 17 00:00:00 2001 From: Erik Verbruggen Date: Tue, 15 Oct 2013 16:13:01 +0200 Subject: [PATCH] V4 SSA: speed up dominator calculations. Changed three recursive routines to worklist-based iterative ones. This not only speeds up the dominator frontier calculation, but also prevents the algorithm to run out of stack space. This is a partial fix for QTBUG-34047. Change-Id: Ife8dc35724d50408ad356e1621884bdb82db9626 Reviewed-by: Lars Knoll --- src/qml/compiler/qv4ssa.cpp | 200 ++++++++++++++++++++++++++++++-------------- 1 file changed, 137 insertions(+), 63 deletions(-) diff --git a/src/qml/compiler/qv4ssa.cpp b/src/qml/compiler/qv4ssa.cpp index aaf86f1..62f65c0 100644 --- a/src/qml/compiler/qv4ssa.cpp +++ b/src/qml/compiler/qv4ssa.cpp @@ -224,26 +224,65 @@ class DominatorTree { QHash samedom; QHash > bucket; - void DFS(BasicBlock *p, BasicBlock *n) { - if (dfnum[n] == 0) { - dfnum[n] = N; - vertex[N] = n; - parent[n] = p; - ++N; - foreach (BasicBlock *w, n->out) - DFS(n, w); + struct DFSTodo { + BasicBlock *node, *parent; + + DFSTodo():node(0),parent(0){} + DFSTodo(BasicBlock *node, BasicBlock *parent):node(node),parent(parent){} + }; + + void DFS(BasicBlock *node) { + QVector worklist; + worklist.reserve(vertex.capacity()); + DFSTodo todo(node, 0); + + while (true) { + BasicBlock *n = todo.node; + + if (dfnum[n] == 0) { + dfnum[n] = N; + vertex[N] = n; + parent[n] = todo.parent; + ++N; + for (int i = n->out.size() - 1; i > 0; --i) + worklist.append(DFSTodo(n->out[i], n)); + + if (n->out.size() > 0) { + todo.node = n->out.first(); + todo.parent = n; + continue; + } + } + + if (worklist.isEmpty()) + break; + + todo = worklist.last(); + worklist.removeLast(); } } BasicBlock *ancestorWithLowestSemi(BasicBlock *v) { - BasicBlock *a = ancestor[v]; - if (ancestor[a]) { - BasicBlock *b = ancestorWithLowestSemi(a); - ancestor[v] = ancestor[a]; - if (dfnum[semi[b]] < dfnum[semi[best[v]]]) - best[v] = b; + QVector worklist; + worklist.reserve(vertex.capacity()); + for (BasicBlock *it = v; it; it = ancestor[it]) + worklist.append(it); + + if (worklist.size() < 2) + return best[v]; + + BasicBlock *b = 0; + BasicBlock *last = worklist.last(); + for (int it = worklist.size() - 2; it >= 0; --it) { + BasicBlock *bbIt = worklist[it]; + ancestor[bbIt] = last; + BasicBlock *&best_it = best[bbIt]; + if (b && dfnum[semi[b]] < dfnum[semi[best_it]]) + best_it = b; + else + b = best_it; } - return best[v]; + return b; } void link(BasicBlock *p, BasicBlock *n) { @@ -262,8 +301,8 @@ class DominatorTree { samedom[n] = 0; } - DFS(0, nodes.first()); - Q_ASSERT(N == nodes.size()); // fails with unreachable nodes... + DFS(nodes.first()); + Q_ASSERT(N == nodes.size()); // fails with unreachable nodes, but those should have been removed before. for (int i = N - 1; i > 0; --i) { BasicBlock *n = vertex[i]; @@ -322,52 +361,88 @@ class DominatorTree { return false; } - void computeDF(BasicBlock *n) { - if (DF.contains(n)) - return; // TODO: verify this! + struct NodeProgress { + QSet children; + QSet todo; + }; + + void computeDF(const QVector &nodes) { + QHash nodeStatus; + nodeStatus.reserve(nodes.size()); + QVector worklist; + worklist.reserve(nodes.size() * 2); + for (int i = 0, ei = nodes.size(); i != ei; ++i) { + BasicBlock *node = nodes[i]; + worklist.append(node); + NodeProgress &np = nodeStatus[node]; + np.children = children[node]; + np.todo = children[node]; + } - QSet S; - foreach (BasicBlock *y, n->out) - if (idom[y] != n) - S.insert(y); + while (!worklist.isEmpty()) { + BasicBlock *node = worklist.last(); + + if (DF.contains(node)) { + worklist.removeLast(); + continue; + } - /* - * foreach child c of n in the dominator tree - * computeDF[c] - * foreach element w of DF[c] - * if n does not dominate w or if n = w - * S.insert(w) - * DF[n] = S; - */ - foreach (BasicBlock *c, children[n]) { - computeDF(c); - foreach (BasicBlock *w, DF[c]) - if (!dominates(n, w) || n == w) - S.insert(w); + NodeProgress &np = nodeStatus[node]; + QSet::iterator it = np.todo.begin(); + while (it != np.todo.end()) { + if (DF.contains(*it)) { + it = np.todo.erase(it); + } else { + worklist.append(*it); + break; + } + } + + if (np.todo.isEmpty()) { + QSet S; + foreach (BasicBlock *y, node->out) + if (idom[y] != node) + if (!S.contains(y)) + S.insert(y); + foreach (BasicBlock *child, np.children) + foreach (BasicBlock *w, DF[child]) + if (!dominates(node, w) || node == w) + if (!S.contains(w)) + S.insert(w); + DF.insert(node, S); + worklist.removeLast(); + } } - DF[n] = S; -#ifdef SHOW_SSA - qout << "\tDF[" << n->index << "]: {"; - QList SList = S.values(); - for (int i = 0; i < SList.size(); ++i) { - if (i > 0) - qout << ", "; - qout << SList[i]->index; +#if defined(SHOW_SSA) + qout << "Dominator Frontiers:" << endl; + foreach (BasicBlock *n, nodes) { + qout << "\tDF[" << n->index << "]: {"; + QList SList = DF[n].values(); + for (int i = 0; i < SList.size(); ++i) { + if (i > 0) + qout << ", "; + qout << SList[i]->index; + } + qout << "}" << endl; } - qout << "}" << endl; #endif // SHOW_SSA -#ifndef QT_NO_DEBUG - foreach (BasicBlock *fBlock, S) { - Q_ASSERT(!dominates(n, fBlock) || fBlock == n); - bool hasDominatedSucc = false; - foreach (BasicBlock *succ, fBlock->in) - if (dominates(n, succ)) - hasDominatedSucc = true; - if (!hasDominatedSucc) { - qout << fBlock->index << " in DF[" << n->index << "] has no dominated predecessors" << endl; +#if !defined(QT_NO_DEBUG) && defined(CAN_TAKE_LOSTS_OF_TIME) + foreach (BasicBlock *n, nodes) { + foreach (BasicBlock *fBlock, DF[n]) { + 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->index << " in DF[" << n->index << "] has no dominated predecessors" << endl; + } + Q_ASSERT(hasDominatedSucc); } - Q_ASSERT(hasDominatedSucc); } #endif // !QT_NO_DEBUG } @@ -382,14 +457,13 @@ public: calculateIDoms(nodes); // compute children of n - foreach (BasicBlock *n, nodes) - children[idom[n]].insert(n); + foreach (BasicBlock *n, nodes) { + QSet &c = children[idom[n]]; + if (!c.contains(n)) + c.insert(n); + } -#ifdef SHOW_SSA - qout << "Dominator Frontiers:" << endl; -#endif // SHOW_SSA - foreach (BasicBlock *n, nodes) - computeDF(n); + computeDF(nodes); } QSet operator[](BasicBlock *n) const { -- 2.7.4