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

sdk/lib/_internal/compiler/implementation/ssa/optimize.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 OptimizationPhase {
   String get name;
   void visitGraph(HGraph graph);
 }
@@ skipping 1135 matching lines @@
       // to the worklist.
       for (final user in phi.usedBy) {
         if (user is HPhi) worklist.add(user);
       }
       phi.block.rewrite(phi, candidate);
       phi.block.removePhi(phi);
     }
   }
 }
 
+class GvnWorkItem {
+  final HBasicBlock block;
+  final ValueSet valueSet;
+  GvnWorkItem(this.block, this.valueSet);
+}
+
 class SsaGlobalValueNumberer implements OptimizationPhase {
   final String name = "SsaGlobalValueNumberer";
   final Compiler compiler;
   final Set<int> visited;
 
   List<int> blockChangesFlags;
   List<int> loopChangesFlags;
 
   SsaGlobalValueNumberer(this.compiler) : visited = new Set<int>();
 
   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) {
     for (int i = graph.blocks.length - 1; i >= 0; i--) {
       HBasicBlock block = graph.blocks[i];
       if (block.isLoopHeader()) {
         int changesFlags = loopChangesFlags[block.id];
         HLoopInformation info = block.loopInformation;
         // Iterate over all blocks of this loop. Note that blocks in
         // inner loops are not visited here, but we know they
@@ skipping 56 matching lines @@
       }
       instruction = next;
     }
   }
 
   bool isInputDefinedAfterDominator(HInstruction input,
                                     HBasicBlock dominator) {
     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];
       values.kill(flags);
     }
     while (instruction != null) {
       HInstruction next = instruction.next;
       int flags = instruction.sideEffects.getChangesFlags();
       assert(flags == 0 || !instruction.useGvn());
       values.kill(flags);
@@ skipping 16 matching lines @@
       // No need to copy the value set for the last child.
       ValueSet successorValues = (i == length - 1) ? values : values.copy();
       // If we have no values in our set, we do not have to kill
       // anything. Also, if the range of block ids from the current
       // block to the dominated block is empty, there is no blocks on
       // any path from the current block to the dominated block so we
       // don't have to do anything either.
       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));
     }
   }
 
   void computeChangesFlags(HGraph graph) {
     // Create the changes flags lists. Make sure to initialize the
     // loop changes flags list to zero so we can use bitwise or when
     // propagating loop changes upwards.
     final int length = graph.blocks.length;
     blockChangesFlags = new List<int>(length);
     loopChangesFlags = new List<int>(length);
@@ skipping 25 matching lines @@
       HBasicBlock parentLoopHeader = block.parentLoopHeader;
       if (parentLoopHeader != null) {
         loopChangesFlags[parentLoopHeader.id] |= (block.isLoopHeader())
             ? loopChangesFlags[id]
             : changesFlags;
       }
     }
   }
 
   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++) {
       HBasicBlock block = predecessors[i];
       int id = block.id;
       // If the current predecessor block is on the path from the
       // dominator to the dominated, it must have an id that is in the
       // range from the dominator to the dominated.
       if (dominator.id < id && id < dominated.id && !visited.contains(id)) {
         visited.add(id);
         changesFlags |= blockChangesFlags[id];
         // 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;
   }
 }
 
 // This phase merges equivalent instructions on different paths into
 // one instruction in a dominator block. It runs through the graph
 // post dominator order and computes a ValueSet for each block of
 // instructions that can be moved to a dominator block. These
@@ skipping 146 matching lines @@
       // that knows it is not of a specific Type.
     }
 
     for (HIf ifUser in notIfUsers) {
       changeUsesDominatedBy(ifUser.elseBlock, input, convertedType);
       // TODO(ngeoffray): Also change uses for the then block on a HType
       // that knows it is not of a specific Type.
     }
   }
 }