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

sdk/lib/_internal/compiler/implementation/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.
 
 part of ssa;
 
 abstract class HVisitor<R> {
   R visitAdd(HAdd node);
   R visitBailoutTarget(HBailoutTarget node);
   R visitBitAnd(HBitAnd node);
@@ skipping 719 matching lines @@
     }
   }
 
   bool isValid() {
     assert(isClosed());
     HValidator validator = new HValidator();
     validator.visitBasicBlock(this);
     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;
   }
 }
 
 
 abstract class HInstruction implements Spannable {
   Element sourceElement;
   SourceFileLocation sourcePosition;
 
   final int id;
   static int idCounter;
@@ skipping 1651 matching lines @@
 
   /** Corresponding block information for the loop. */
   HLoopBlockInformation loopBlockInformation;
 
   HLoopInformation(this.header, this.target, this.labels)
       : blocks = new List<HBasicBlock>(),
         backEdges = new List<HBasicBlock>();
 
   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);
     }
   }
 
   HBasicBlock getLastBackEdge() {
     int maxId = -1;
     HBasicBlock result = null;
     for (int i = 0, length = backEdges.length; i < length; i++) {
       HBasicBlock current = backEdges[i];
       if (current.id > maxId) {
         maxId = current.id;
@@ skipping 281 matching lines @@
   HBasicBlock get start => expression.start;
   HBasicBlock get end {
     // We don't create a switch block if there are no cases.
     assert(!statements.isEmpty);
     return statements.last.end;
   }
 
   bool accept(HStatementInformationVisitor visitor) =>
       visitor.visitSwitchInfo(this);
 }