dart2js: make dominator tree traversals nonrecursive

pkg/compiler/lib/src/ssa/nodes.dart

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 import '../closure.dart';
 import '../common.dart';
 import '../common/backend_api.dart' show BackendClasses;
 import '../compiler.dart' show Compiler;
 import '../constants/constant_system.dart';
 import '../constants/values.dart';
@@ skipping 87 matching lines @@
   R visitTypeKnown(HTypeKnown node);
   R visitYield(HYield node);
 
   R visitTypeInfoReadRaw(HTypeInfoReadRaw node);
   R visitTypeInfoReadVariable(HTypeInfoReadVariable node);
   R visitTypeInfoExpression(HTypeInfoExpression node);
 }
 
 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) {

[Emily Fortuna, 2017/04/05 19:56:37]

thank you for writing out this comment. it helps. :-D

+    //       visitBasicBlock(block);
+    //       List dominated = block.dominatedBlocks;
+    //       for (int i = 0; i < dominated.length; i++) {
+    //         visitBasicBlockAndSuccessors(dominated[i]);
+    //         visitBasicBlockAndSuccessors(graph.entry);
+    //       }
+    //     }
+    //     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;
 
   visitInstruction(HInstruction node);
 
   visitBasicBlock(HBasicBlock node) {
     void visitInstructionList(HInstructionList list) {
       HInstruction instruction = list.first;
       while (instruction != null) {
         visitInstruction(instruction);
@@ skipping 3250 matching lines @@
   // ignore: MISSING_RETURN
   String get kindAsString {
     switch (kind) {
       case TypeInfoExpressionKind.COMPLETE:
         return 'COMPLETE';
       case TypeInfoExpressionKind.INSTANCE:
         return 'INSTANCE';
     }
   }
 }