From 2f3e7f904f9adf4125d5b7002293439da438fb15 Mon Sep 17 00:00:00 2001 From: Erik Verbruggen Date: Mon, 16 Dec 2013 16:45:59 +0100 Subject: V4 IR: change datastructures for dominator calculations. Replace hashes from basic-block to basic-block with vectors that associate basic-block index to basic-block index. Change-Id: I834ea3d825e4d2b02c075b1b0f080f5a65f41317 Reviewed-by: Fawzi Mohamed --- src/qml/compiler/qv4ssa.cpp | 284 +++++++++++++++++++++++++++----------------- 1 file changed, 172 insertions(+), 112 deletions(-) diff --git a/src/qml/compiler/qv4ssa.cpp b/src/qml/compiler/qv4ssa.cpp index eccdfff623..5e1122e18b 100644 --- a/src/qml/compiler/qv4ssa.cpp +++ b/src/qml/compiler/qv4ssa.cpp @@ -39,6 +39,10 @@ ** ****************************************************************************/ +#ifndef QT_NO_DEBUG +# define _LIBCPP_DEBUG2 0 +#endif // QT_NO_DEBUG + #include "qv4ssa_p.h" #include "qv4isel_util_p.h" #include "qv4util_p.h" @@ -256,71 +260,87 @@ inline Temp *unescapableTemp(Expr *e, bool variablesCanEscape) } class DominatorTree { + typedef int BasicBlockIndex; + enum { InvalidBasicBlockIndex = -1 }; + + const QVector nodes; int N; - QHash dfnum; - QVector vertex; - QHash parent; - QHash ancestor; - QHash best; - QHash semi; - QHash idom; - QHash samedom; - QHash > bucket; + std::vector dfnum; // BasicBlock index -> dfnum + std::vector vertex; + std::vector parent; // BasicBlock index -> parent BasicBlock index + std::vector ancestor; // BasicBlock index -> ancestor BasicBlock index + std::vector best; // BasicBlock index -> best BasicBlock index + std::vector semi; // BasicBlock index -> semi dominator BasicBlock index + std::vector idom; // BasicBlock index -> immediate dominator BasicBlock index + std::vector samedom; // BasicBlock index -> same dominator BasicBlock index struct DFSTodo { - BasicBlock *node, *parent; + BasicBlockIndex node, parent; + + DFSTodo() + : node(InvalidBasicBlockIndex) + , parent(InvalidBasicBlockIndex) + {} - DFSTodo():node(0),parent(0){} - DFSTodo(BasicBlock *node, BasicBlock *parent):node(node),parent(parent){} + DFSTodo(BasicBlockIndex node, BasicBlockIndex parent) + : node(node) + , parent(parent) + {} }; - void DFS(BasicBlock *node) { - QVector worklist; - worklist.reserve(vertex.capacity()); - DFSTodo todo(node, 0); + void DFS(BasicBlockIndex node) { + std::vector worklist; + worklist.reserve(vertex.capacity() / 2); + DFSTodo todo(node, InvalidBasicBlockIndex); while (true) { - BasicBlock *n = todo.node; + BasicBlockIndex 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)); + const QVector &out = nodes[n]->out; + for (int i = out.size() - 1; i > 0; --i) + worklist.push_back(DFSTodo(out[i]->index, n)); - if (n->out.size() > 0) { - todo.node = n->out.first(); + if (out.size() > 0) { + todo.node = out.first()->index; todo.parent = n; continue; } } - if (worklist.isEmpty()) + if (worklist.empty()) break; - todo = worklist.last(); - worklist.removeLast(); + todo = worklist.back(); + worklist.pop_back(); } + +#if defined(SHOW_SSA) + for (int i = 0; i < nodes.size(); ++i) + qDebug("\tL%d: dfnum = %d, parent = %d", i, dfnum[i], parent[i]); +#endif // SHOW_SSA } - BasicBlock *ancestorWithLowestSemi(BasicBlock *v) { - QVector worklist; - worklist.reserve(vertex.capacity()); - for (BasicBlock *it = v; it; it = ancestor[it]) - worklist.append(it); + BasicBlockIndex ancestorWithLowestSemi(BasicBlockIndex v) { + std::vector worklist; + worklist.reserve(vertex.capacity() / 2); + for (BasicBlockIndex it = v; it != InvalidBasicBlockIndex; it = ancestor[it]) + worklist.push_back(it); if (worklist.size() < 2) return best[v]; - BasicBlock *b = 0; - BasicBlock *last = worklist.last(); + BasicBlockIndex b = InvalidBasicBlockIndex; + BasicBlockIndex last = worklist.back(); for (int it = worklist.size() - 2; it >= 0; --it) { - BasicBlock *bbIt = worklist[it]; + BasicBlockIndex bbIt = worklist[it]; ancestor[bbIt] = last; - BasicBlock *&best_it = best[bbIt]; - if (b && dfnum[semi[b]] < dfnum[semi[best_it]]) + BasicBlockIndex &best_it = best[bbIt]; + if (b != InvalidBasicBlockIndex && dfnum[semi[b]] < dfnum[semi[best_it]]) best_it = b; else b = best_it; @@ -328,66 +348,82 @@ class DominatorTree { return b; } - void link(BasicBlock *p, BasicBlock *n) { + void link(BasicBlockIndex p, BasicBlockIndex n) { ancestor[n] = p; best[n] = n; } - void calculateIDoms(const QVector &nodes) { + void calculateIDoms() { Q_ASSERT(nodes.first()->in.isEmpty()); - vertex.resize(nodes.size()); - foreach (BasicBlock *n, nodes) { - dfnum[n] = 0; - semi[n] = 0; - ancestor[n] = 0; - idom[n] = 0; - samedom[n] = 0; - } - DFS(nodes.first()); + vertex = std::vector(nodes.size(), InvalidBasicBlockIndex); + parent = std::vector(nodes.size(), InvalidBasicBlockIndex); + dfnum = std::vector(nodes.size(), 0); + semi = std::vector(nodes.size(), InvalidBasicBlockIndex); + ancestor = std::vector(nodes.size(), InvalidBasicBlockIndex); + idom = std::vector(nodes.size(), InvalidBasicBlockIndex); + samedom = std::vector(nodes.size(), InvalidBasicBlockIndex); + best = std::vector(nodes.size(), InvalidBasicBlockIndex); + + QHash > bucket; + + DFS(nodes.first()->index); 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]; - BasicBlock *p = parent[n]; - BasicBlock *s = p; - - foreach (BasicBlock *v, n->in) { - BasicBlock *ss; - if (dfnum[v] <= dfnum[n]) - ss = v; + BasicBlockIndex n = vertex[i]; + BasicBlockIndex p = parent[n]; + BasicBlockIndex s = p; + + foreach (BasicBlock *v, nodes.at(n)->in) { + BasicBlockIndex ss = InvalidBasicBlockIndex; + if (dfnum[v->index] <= dfnum[n]) + ss = v->index; else - ss = semi[ancestorWithLowestSemi(v)]; + ss = semi[ancestorWithLowestSemi(v->index)]; if (dfnum[ss] < dfnum[s]) s = ss; } semi[n] = s; - bucket[s].insert(n); + bucket[s].push_back(n); link(p, n); - foreach (BasicBlock *v, bucket[p]) { - BasicBlock *y = ancestorWithLowestSemi(v); - BasicBlock *semi_v = semi[v]; - if (semi[y] == semi_v) - idom[v] = semi_v; - else - samedom[v] = y; + if (bucket.contains(p)) { + foreach (BasicBlockIndex v, bucket[p]) { + BasicBlockIndex y = ancestorWithLowestSemi(v); + BasicBlockIndex semi_v = semi[v]; + if (semi[y] == semi_v) + idom[v] = semi_v; + else + samedom[v] = y; + } + bucket.remove(p); } - bucket[p].clear(); } + +#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 < N; ++i) { - BasicBlock *n = vertex[i]; - Q_ASSERT(ancestor[n] && ((semi[n] && dfnum[ancestor[n]] <= dfnum[semi[n]]) || semi[n] == n)); - Q_ASSERT(bucket[n].isEmpty()); - if (BasicBlock *sdn = samedom[n]) + BasicBlockIndex n = vertex[i]; + Q_ASSERT(n != InvalidBasicBlockIndex); + Q_ASSERT(!bucket.contains(n)); + Q_ASSERT(ancestor[n] != InvalidBasicBlockIndex + && ((semi[n] != InvalidBasicBlockIndex + && dfnum[ancestor[n]] <= dfnum[semi[n]]) || semi[n] == n)); + BasicBlockIndex sdn = samedom[n]; + if (sdn != InvalidBasicBlockIndex) idom[n] = idom[sdn]; } -#ifdef SHOW_SSA +#if defined(SHOW_SSA) qout << "Immediate dominators:" << endl; foreach (BasicBlock *to, nodes) { qout << '\t'; - if (BasicBlock *from = idom.value(to)) - qout << from->index; + BasicBlockIndex from = idom.at(to->index); + if (from != InvalidBasicBlockIndex) + qout << from; else qout << "(none)"; qout << " -> " << to->index << endl; @@ -396,55 +432,59 @@ class DominatorTree { } struct NodeProgress { - QSet children; - QSet todo; + QSet children; + QSet todo; }; - void computeDF(const QVector &nodes) { - QHash nodeStatus; + void computeDF() { + QHash nodeStatus; nodeStatus.reserve(nodes.size()); - QVector worklist; + std::vector 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]; + BasicBlockIndex nodeIndex = nodes[i]->index; + worklist.push_back(nodeIndex); + NodeProgress &np = nodeStatus[nodeIndex]; + np.children = children[nodeIndex]; + np.todo = children[nodeIndex]; } - while (!worklist.isEmpty()) { - BasicBlock *node = worklist.last(); + std::vector DF_done(nodes.size(), false); - if (DF.contains(node)) { - worklist.removeLast(); + while (!worklist.empty()) { + BasicBlockIndex node = worklist.back(); + + if (DF_done[node]) { + worklist.pop_back(); continue; } NodeProgress &np = nodeStatus[node]; - QSet::iterator it = np.todo.begin(); + QSet::iterator it = np.todo.begin(); while (it != np.todo.end()) { - if (DF.contains(*it)) { + if (DF_done[*it]) { it = np.todo.erase(it); } else { - worklist.append(*it); + worklist.push_back(*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(); + foreach (BasicBlock *y, nodes[node]->out) + if (idom[y->index] != node) + S.insert(y); + foreach (BasicBlockIndex child, np.children) { + foreach (BasicBlock *w, DF[child]) { + const BasicBlockIndex wIndex = w->index; + if (node == wIndex || !dominates(node, w->index)) + S.insert(w); + } + } + DF[node] = S; + DF_done[node] = true; + worklist.pop_back(); } } @@ -452,7 +492,7 @@ class DominatorTree { qout << "Dominator Frontiers:" << endl; foreach (BasicBlock *n, nodes) { qout << "\tDF[" << n->index << "]: {"; - QList SList = DF[n].values(); + QList SList = DF[n->index].values(); for (int i = 0; i < SList.size(); ++i) { if (i > 0) qout << ", "; @@ -463,7 +503,7 @@ class DominatorTree { #endif // SHOW_SSA #if !defined(QT_NO_DEBUG) && defined(CAN_TAKE_LOSTS_OF_TIME) foreach (BasicBlock *n, nodes) { - foreach (BasicBlock *fBlock, DF[n]) { + foreach (BasicBlock *fBlock, DF[n->index]) { Q_ASSERT(!dominates(n, fBlock) || fBlock == n); bool hasDominatedSucc = false; foreach (BasicBlock *succ, fBlock->in) { @@ -473,7 +513,7 @@ class DominatorTree { } } if (!hasDominatedSucc) { - qout << fBlock->index << " in DF[" << n->index << "] has no dominated predecessors" << endl; + qout << fBlock << " in DF[" << n->index << "] has no dominated predecessors" << endl; } Q_ASSERT(hasDominatedSucc); } @@ -481,35 +521,50 @@ class DominatorTree { #endif // !QT_NO_DEBUG } - QHash > children; - QHash > DF; + std::vector > children; // BasicBlock index -> children + std::vector > DF; // BasicBlock index -> dominator frontier public: DominatorTree(const QVector &nodes) - : N(0) + : nodes(nodes) + , N(0) { - calculateIDoms(nodes); + DF.resize(nodes.size()); + children.resize(nodes.size()); + calculateIDoms(); // compute children of n foreach (BasicBlock *n, nodes) { - QSet &c = children[idom[n]]; - if (!c.contains(n)) - c.insert(n); + const BasicBlockIndex nodeIndex = n->index; + Q_ASSERT(nodes.at(nodeIndex) == n); + const BasicBlockIndex nodeDominator = idom[nodeIndex]; + if (nodeDominator == InvalidBasicBlockIndex) + continue; // there is no dominator to add this node to as a child (e.g. the start node) + QSet &c = children[nodeDominator]; + if (!c.contains(nodeIndex)) + c.insert(nodeIndex); } - computeDF(nodes); + computeDF(); } QSet operator[](BasicBlock *n) const { - return DF[n]; + return DF[n->index]; } BasicBlock *immediateDominator(BasicBlock *bb) const { - return idom[bb]; + return nodes[idom[bb->index]]; } bool dominates(BasicBlock *dominator, BasicBlock *dominated) const { - for (BasicBlock *it = dominated; it; it = idom[it]) { + // The index of the basic blocks might have changed, or the nodes array might have changed, + // or the block got deleted, so get the index from our copy of the array. + return dominates(nodes.indexOf(dominator), nodes.indexOf(dominated)); + } + +private: + bool dominates(BasicBlockIndex dominator, BasicBlockIndex dominated) const { + for (BasicBlockIndex it = dominated; it != InvalidBasicBlockIndex; it = idom[it]) { if (it == dominator) return true; } @@ -2687,6 +2742,11 @@ namespace { /// Important: this assumes that there are no critical edges in the control-flow graph! void purgeBB(BasicBlock *bb, Function *func, DefUsesCalculator &defUses, QVector &W) { + // TODO: change this to mark the block as deleted, but leave it alone so that other references + // won't be dangling pointers. + // TODO: after the change above: if we keep on detaching the block from predecessors or + // successors, update the DominatorTree too. + // don't purge blocks that are entry points for catch statements. They might not be directly // connected, but are required anyway if (bb->isExceptionHandler) -- cgit v1.2.3