Avoid recursion in some of our SSA optimizations, and cache computed block.dominates(other) operati…

sdk/lib/_internal/compiler/implementation/ssa/nodes.dart

Index: sdk/lib/_internal/compiler/implementation/ssa/nodes.dart
===================================================================
--- sdk/lib/_internal/compiler/implementation/ssa/nodes.dart	(revision 27430)
+++ sdk/lib/_internal/compiler/implementation/ssa/nodes.dart	(working copy)
@@ -737,14 +737,20 @@
     return validator.isValid;
   }
 
-  // TODO(ngeoffray): Cache the information if this method ends up
-  // being hot.
+  Map<HBasicBlock, bool> cacheDominates;

[kasperl, 2013/09/13 08:01:27]

I'd prefer dominatesCache. Do you feel like the lazy initialization of it is
important? Do we have many blocks that are never asked if they dominate
something?

[ngeoffray, 2013/09/13 10:11:24]

Yeah, we only ask it for a certain number of instructions in our optimizations
that some blocks never see.

+
   bool dominates(HBasicBlock other) {
+    if (cacheDominates == null) {
+      cacheDominates = new Map<HBasicBlock, bool>();
+    } else {
+      bool res = cacheDominates[other];
+      if (res != null) return res;
+    }
     do {
-      if (identical(this, other)) return true;
+      if (identical(this, other)) return cacheDominates[other] = true;
       other = other.dominator;
     } while (other != null && other.id >= id);
-    return false;
+    return cacheDominates[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);
     }
   }