From 7471ce401ddc09dc03dc612f8f8fa6473230c98a Mon Sep 17 00:00:00 2001 From: Erik Verbruggen Date: Thu, 10 Jul 2014 11:40:26 +0200 Subject: V4 IR: change dominator tree to hold on to less memory. Move all data needed to calculate the immediate dominators into a struct that is freed immediately after finishing this calculation. Change-Id: Id0cefa4088643539d59c4c593cba1848422c1726 Reviewed-by: Simon Hausmann --- src/qml/compiler/qv4ssa.cpp | 131 ++++++++++++++++++++++++-------------------- 1 file changed, 72 insertions(+), 59 deletions(-) (limited to 'src/qml/compiler') diff --git a/src/qml/compiler/qv4ssa.cpp b/src/qml/compiler/qv4ssa.cpp index 335cbcc7cf..9a2f6a86ba 100644 --- a/src/qml/compiler/qv4ssa.cpp +++ b/src/qml/compiler/qv4ssa.cpp @@ -264,16 +264,23 @@ class DominatorTree typedef int BasicBlockIndex; enum { InvalidBasicBlockIndex = -1 }; + struct Data + { + int N; + 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 samedom; // BasicBlock index -> same dominator BasicBlock index + + Data(): N(0) {} + }; + IR::Function *function; - int N; - 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 + QScopedPointer d; std::vector idom; // BasicBlock index -> immediate dominator BasicBlock index - std::vector samedom; // BasicBlock index -> same dominator BasicBlock index std::vector DF; // BasicBlock index -> dominator frontier struct DFSTodo { @@ -292,17 +299,17 @@ class DominatorTree void DFS(BasicBlockIndex node) { std::vector worklist; - worklist.reserve(vertex.capacity() / 2); + worklist.reserve(d->vertex.capacity() / 2); DFSTodo todo(node, InvalidBasicBlockIndex); while (true) { BasicBlockIndex n = todo.node; - if (dfnum[n] == 0) { - dfnum[n] = N; - vertex[N] = n; - parent[n] = todo.parent; - ++N; + if (d->dfnum[n] == 0) { + d->dfnum[n] = d->N; + d->vertex[d->N] = n; + d->parent[n] = todo.parent; + ++d->N; const QVector &out = function->basicBlock(n)->out; for (int i = out.size() - 1; i > 0; --i) worklist.push_back(DFSTodo(out[i]->index(), n)); @@ -329,20 +336,20 @@ class DominatorTree BasicBlockIndex ancestorWithLowestSemi(BasicBlockIndex v, std::vector &worklist) { worklist.clear(); - for (BasicBlockIndex it = v; it != InvalidBasicBlockIndex; it = ancestor[it]) + for (BasicBlockIndex it = v; it != InvalidBasicBlockIndex; it = d->ancestor[it]) worklist.push_back(it); if (worklist.size() < 2) - return best[v]; + return d->best[v]; BasicBlockIndex b = InvalidBasicBlockIndex; BasicBlockIndex last = worklist.back(); Q_ASSERT(worklist.size() <= INT_MAX); for (int it = static_cast(worklist.size()) - 2; it >= 0; --it) { BasicBlockIndex bbIt = worklist[it]; - ancestor[bbIt] = last; - BasicBlockIndex &best_it = best[bbIt]; - if (b != InvalidBasicBlockIndex && dfnum[semi[b]] < dfnum[semi[best_it]]) + d->ancestor[bbIt] = last; + BasicBlockIndex &best_it = d->best[bbIt]; + if (b != InvalidBasicBlockIndex && d->dfnum[d->semi[b]] < d->dfnum[d->semi[best_it]]) best_it = b; else b = best_it; @@ -351,57 +358,57 @@ class DominatorTree } void link(BasicBlockIndex p, BasicBlockIndex n) { - ancestor[n] = p; - best[n] = n; + d->ancestor[n] = p; + d->best[n] = n; } void calculateIDoms() { Q_ASSERT(function->basicBlock(0)->in.isEmpty()); const int bbCount = function->basicBlockCount(); - vertex = std::vector(bbCount, InvalidBasicBlockIndex); - parent = std::vector(bbCount, InvalidBasicBlockIndex); - dfnum = std::vector(bbCount, 0); - semi = std::vector(bbCount, InvalidBasicBlockIndex); - ancestor = std::vector(bbCount, InvalidBasicBlockIndex); + d->vertex = std::vector(bbCount, InvalidBasicBlockIndex); + d->parent = std::vector(bbCount, InvalidBasicBlockIndex); + d->dfnum = std::vector(bbCount, 0); + d->semi = std::vector(bbCount, InvalidBasicBlockIndex); + d->ancestor = std::vector(bbCount, InvalidBasicBlockIndex); idom = std::vector(bbCount, InvalidBasicBlockIndex); - samedom = std::vector(bbCount, InvalidBasicBlockIndex); - best = std::vector(bbCount, InvalidBasicBlockIndex); + d->samedom = std::vector(bbCount, InvalidBasicBlockIndex); + d->best = std::vector(bbCount, InvalidBasicBlockIndex); QHash > bucket; bucket.reserve(bbCount); DFS(function->basicBlock(0)->index()); - Q_ASSERT(N == function->liveBasicBlocksCount()); + Q_ASSERT(d->N == function->liveBasicBlocksCount()); std::vector worklist; - worklist.reserve(vertex.capacity() / 2); + worklist.reserve(d->vertex.capacity() / 2); - for (int i = N - 1; i > 0; --i) { - BasicBlockIndex n = vertex[i]; - BasicBlockIndex p = parent[n]; + for (int i = d->N - 1; i > 0; --i) { + BasicBlockIndex n = d->vertex[i]; + BasicBlockIndex p = d->parent[n]; BasicBlockIndex s = p; foreach (BasicBlock *v, function->basicBlock(n)->in) { BasicBlockIndex ss = InvalidBasicBlockIndex; - if (dfnum[v->index()] <= dfnum[n]) + if (d->dfnum[v->index()] <= d->dfnum[n]) ss = v->index(); else - ss = semi[ancestorWithLowestSemi(v->index(), worklist)]; - if (dfnum[ss] < dfnum[s]) + ss = d->semi[ancestorWithLowestSemi(v->index(), worklist)]; + if (d->dfnum[ss] < d->dfnum[s]) s = ss; } - semi[n] = s; + d->semi[n] = s; bucket[s].push_back(n); link(p, n); if (bucket.contains(p)) { foreach (BasicBlockIndex v, bucket[p]) { BasicBlockIndex y = ancestorWithLowestSemi(v, worklist); - BasicBlockIndex semi_v = semi[v]; - if (semi[y] == semi_v) + BasicBlockIndex semi_v = d->semi[v]; + if (d->semi[y] == semi_v) idom[v] = semi_v; else - samedom[v] = y; + d->samedom[v] = y; } bucket.remove(p); } @@ -412,14 +419,14 @@ class DominatorTree 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) { - BasicBlockIndex n = vertex[i]; + for (int i = 1; i < d->N; ++i) { + BasicBlockIndex n = d->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]; + Q_ASSERT(d->ancestor[n] != InvalidBasicBlockIndex + && ((d->semi[n] != InvalidBasicBlockIndex + && d->dfnum[d->ancestor[n]] <= d->dfnum[d->semi[n]]) || d->semi[n] == n)); + BasicBlockIndex sdn = d->samedom[n]; if (sdn != InvalidBasicBlockIndex) idom[n] = idom[sdn]; } @@ -432,7 +439,18 @@ class DominatorTree std::vector todo; }; +public: + DominatorTree(IR::Function *function) + : function(function) + , d(new Data) + { + calculateIDoms(); + d.reset(); + } + void computeDF() { + DF.resize(function->basicBlockCount()); + // compute children of each node in the dominator tree std::vector > children; // BasicBlock index -> children children.resize(function->basicBlockCount()); @@ -451,7 +469,7 @@ class DominatorTree std::vector nodeStatus; nodeStatus.resize(function->basicBlockCount()); std::vector worklist; - worklist.reserve(function->basicBlockCount() * 2); + worklist.reserve(function->basicBlockCount()); foreach (BasicBlock *bb, function->basicBlocks()) { if (bb->isRemoved()) continue; @@ -542,22 +560,15 @@ class DominatorTree #endif // !QT_NO_DEBUG } -public: - DominatorTree(IR::Function *function) - : function(function) - , N(0) - { - DF.resize(function->basicBlockCount()); - calculateIDoms(); - computeDF(); - } - const BasicBlockSet &dominatorFrontier(BasicBlock *n) const { return DF[n->index()]; } BasicBlock *immediateDominator(BasicBlock *bb) const { - return function->basicBlock(idom[bb->index()]); + const BasicBlockIndex idx = idom[bb->index()]; + if (idx == -1) + return 0; + return function->basicBlock(idx); } void dumpImmediateDominators() const @@ -582,6 +593,7 @@ public: void updateImmediateDominator(BasicBlock *bb, BasicBlock *newDominator) { Q_ASSERT(bb->index() >= 0); + Q_ASSERT(!newDominator || newDominator->index() >= 0); if (static_cast::size_type>(bb->index()) >= idom.size()) { // This is a new block, probably introduced by edge splitting. So, we'll have to grow @@ -589,7 +601,7 @@ public: idom.resize(function->basicBlockCount(), InvalidBasicBlockIndex); } - idom[bb->index()] = newDominator->index(); + idom[bb->index()] = newDominator ? newDominator->index() : 0; } bool dominates(BasicBlock *dominator, BasicBlock *dominated) const { @@ -4490,6 +4502,7 @@ void Optimizer::run(QQmlEnginePrivate *qmlEngine) // Calculate the dominator tree: DominatorTree df(function); + df.computeDF(); verifyCFG(function); verifyImmediateDominators(df, function); -- cgit v1.2.3