Avoid recursion in some of our SSA optimizations, and cache computed block.dominates(other) operations.
R=kasperl@google.com
Review URL: https://codereview.chromium.org//23721009
git-svn-id: https://dart.googlecode.com/svn/branches/bleeding_edge/dart@27471 260f80e4-7a28-3924-810f-c04153c831b5
diff --git a/sdk/lib/_internal/compiler/implementation/ssa/nodes.dart b/sdk/lib/_internal/compiler/implementation/ssa/nodes.dart
index ff83098..c7770c8 100644
--- a/sdk/lib/_internal/compiler/implementation/ssa/nodes.dart
+++ b/sdk/lib/_internal/compiler/implementation/ssa/nodes.dart
@@ -737,14 +737,20 @@
return validator.isValid;
}
- // TODO(ngeoffray): Cache the information if this method ends up
- // being hot.
+ Map<HBasicBlock, bool> dominatesCache;
+
bool dominates(HBasicBlock other) {
+ if (dominatesCache == null) {
+ dominatesCache = new Map<HBasicBlock, bool>();
+ } else {
+ bool res = dominatesCache[other];
+ if (res != null) return res;
+ }
do {
- if (identical(this, other)) return true;
+ if (identical(this, other)) return dominatesCache[other] = true;
other = other.dominator;
} while (other != null && other.id >= id);
- return false;
+ return dominatesCache[other] = false;
}
}
@@ -2416,24 +2422,26 @@
void addBackEdge(HBasicBlock predecessor) {
backEdges.add(predecessor);
- addBlock(predecessor);
+ List<HBasicBlock> workQueue = <HBasicBlock>[predecessor];
+ do {
+ HBasicBlock current = workQueue.removeLast();
+ addBlock(current, workQueue);
+ } while (!workQueue.isEmpty);
}
// Adds a block and transitively all its predecessors in the loop as
// loop blocks.
- void addBlock(HBasicBlock block) {
+ void addBlock(HBasicBlock block, List<HBasicBlock> workQueue) {
if (identical(block, header)) return;
HBasicBlock parentHeader = block.parentLoopHeader;
if (identical(parentHeader, header)) {
// Nothing to do in this case.
} else if (parentHeader != null) {
- addBlock(parentHeader);
+ workQueue.add(parentHeader);
} else {
block.parentLoopHeader = header;
blocks.add(block);
- for (int i = 0, length = block.predecessors.length; i < length; i++) {
- addBlock(block.predecessors[i]);
- }
+ workQueue.addAll(block.predecessors);
}
}
diff --git a/sdk/lib/_internal/compiler/implementation/ssa/optimize.dart b/sdk/lib/_internal/compiler/implementation/ssa/optimize.dart
index e433676..463e198 100644
--- a/sdk/lib/_internal/compiler/implementation/ssa/optimize.dart
+++ b/sdk/lib/_internal/compiler/implementation/ssa/optimize.dart
@@ -1153,6 +1153,12 @@
}
}
+class GvnWorkItem {
+ final HBasicBlock block;
+ final ValueSet valueSet;
+ GvnWorkItem(this.block, this.valueSet);
+}
+
class SsaGlobalValueNumberer implements OptimizationPhase {
final String name = "SsaGlobalValueNumberer";
final Compiler compiler;
@@ -1166,7 +1172,12 @@
void visitGraph(HGraph graph) {
computeChangesFlags(graph);
moveLoopInvariantCode(graph);
- visitBasicBlock(graph.entry, new ValueSet());
+ List<GvnWorkItem> workQueue =
+ <GvnWorkItem>[new GvnWorkItem(graph.entry, new ValueSet())];
+ do {
+ GvnWorkItem item = workQueue.removeLast();
+ visitBasicBlock(item.block, item.valueSet, workQueue);
+ } while (!workQueue.isEmpty);
}
void moveLoopInvariantCode(HGraph graph) {
@@ -1243,7 +1254,8 @@
return input.block.id > dominator.id;
}
- void visitBasicBlock(HBasicBlock block, ValueSet values) {
+ void visitBasicBlock(
+ HBasicBlock block, ValueSet values, List<GvnWorkItem> workQueue) {
HInstruction instruction = block.first;
if (block.isLoopHeader()) {
int flags = loopChangesFlags[block.id];
@@ -1280,10 +1292,16 @@
assert(block.id < dominated.id);
if (!successorValues.isEmpty && block.id + 1 < dominated.id) {
visited.clear();
- int changesFlags = getChangesFlagsForDominatedBlock(block, dominated);
+ List<HBasicBlock> workQueue = <HBasicBlock>[dominated];
+ int changesFlags = 0;
+ do {
+ HBasicBlock current = workQueue.removeLast();
+ changesFlags |=
+ getChangesFlagsForDominatedBlock(block, current, workQueue);
+ } while (!workQueue.isEmpty);
successorValues.kill(changesFlags);
}
- visitBasicBlock(dominated, successorValues);
+ workQueue.add(new GvnWorkItem(dominated, successorValues));
}
}
@@ -1329,7 +1347,8 @@
}
int getChangesFlagsForDominatedBlock(HBasicBlock dominator,
- HBasicBlock dominated) {
+ HBasicBlock dominated,
+ List<HBasicBlock> workQueue) {
int changesFlags = 0;
List<HBasicBlock> predecessors = dominated.predecessors;
for (int i = 0, length = predecessors.length; i < length; i++) {
@@ -1344,7 +1363,7 @@
// Loop bodies might not be on the path from dominator to dominated,
// but they can invalidate values.
changesFlags |= loopChangesFlags[id];
- changesFlags |= getChangesFlagsForDominatedBlock(dominator, block);
+ workQueue.add(block);
}
}
return changesFlags;
