Index: pkg/compiler/lib/src/ssa/nodes.dart |
diff --git a/pkg/compiler/lib/src/ssa/nodes.dart b/pkg/compiler/lib/src/ssa/nodes.dart |
index ac1961c96b51fa323f04f9e5ae223aaf29d264f8..12d82d9a966f2b318da8dc2c7aabcb4a2f287b77 100644 |
--- a/pkg/compiler/lib/src/ssa/nodes.dart |
+++ b/pkg/compiler/lib/src/ssa/nodes.dart |
@@ -105,32 +105,80 @@ abstract class HVisitor<R> { |
abstract class HGraphVisitor { |
visitDominatorTree(HGraph graph) { |
- void visitBasicBlockAndSuccessors(HBasicBlock block) { |
- visitBasicBlock(block); |
- List dominated = block.dominatedBlocks; |
- for (int i = 0; i < dominated.length; i++) { |
- visitBasicBlockAndSuccessors(dominated[i]); |
+ // Recursion free version of: |
+ // |
+ // void visitBasicBlockAndSuccessors(HBasicBlock block) { |
+ // visitBasicBlock(block); |
+ // List dominated = block.dominatedBlocks; |
+ // for (int i = 0; i < dominated.length; i++) { |
+ // visitBasicBlockAndSuccessors(dominated[i]); |
+ // } |
+ // } |
+ // visitBasicBlockAndSuccessors(graph.entry); |
+ |
+ _Frame frame = new _Frame(null); |
+ frame.block = graph.entry; |
+ frame.index = 0; |
+ |
+ visitBasicBlock(frame.block); |
+ |
+ while (frame != null) { |
+ HBasicBlock block = frame.block; |
+ int index = frame.index; |
+ if (index < block.dominatedBlocks.length) { |
+ frame.index = index + 1; |
+ frame = frame.next ??= new _Frame(frame); |
+ frame.block = block.dominatedBlocks[index]; |
+ frame.index = 0; |
+ visitBasicBlock(frame.block); |
+ continue; |
} |
+ frame = frame.previous; |
} |
- |
- visitBasicBlockAndSuccessors(graph.entry); |
} |
visitPostDominatorTree(HGraph graph) { |
- void visitBasicBlockAndSuccessors(HBasicBlock block) { |
- List dominated = block.dominatedBlocks; |
- for (int i = dominated.length - 1; i >= 0; i--) { |
- visitBasicBlockAndSuccessors(dominated[i]); |
+ // Recusion free version of: |
+ // |
+ // void visitBasicBlockAndSuccessors(HBasicBlock block) { |
+ // List dominated = block.dominatedBlocks; |
+ // for (int i = dominated.length - 1; i >= 0; i--) { |
+ // visitBasicBlockAndSuccessors(dominated[i]); |
+ // } |
+ // visitBasicBlock(block); |
+ // } |
+ // visitBasicBlockAndSuccessors(graph.entry); |
+ |
+ _Frame frame = new _Frame(null); |
+ frame.block = graph.entry; |
+ frame.index = frame.block.dominatedBlocks.length; |
+ |
+ while (frame != null) { |
+ HBasicBlock block = frame.block; |
+ int index = frame.index; |
+ if (index > 0) { |
+ frame.index = index - 1; |
+ frame = frame.next ??= new _Frame(frame); |
+ frame.block = block.dominatedBlocks[index - 1]; |
+ frame.index = frame.block.dominatedBlocks.length; |
+ continue; |
} |
visitBasicBlock(block); |
+ frame = frame.previous; |
} |
- |
- visitBasicBlockAndSuccessors(graph.entry); |
} |
visitBasicBlock(HBasicBlock block); |
} |
+class _Frame { |
+ final _Frame previous; |
+ _Frame next; |
+ HBasicBlock block; |
+ int index; |
+ _Frame(this.previous); |
+} |
+ |
abstract class HInstructionVisitor extends HGraphVisitor { |
HBasicBlock currentBlock; |