diff --git a/sdk/lib/_internal/compiler/implementation/ssa/nodes.dart b/sdk/lib/_internal/compiler/implementation/ssa/nodes.dart
index ff83098..c7770c8 100644
--- a/sdk/lib/_internal/compiler/implementation/ssa/nodes.dart
+++ b/sdk/lib/_internal/compiler/implementation/ssa/nodes.dart
@@ -737,14 +737,20 @@
     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;
   }
 }
 
@@ -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);
     }
   }
 
diff --git a/sdk/lib/_internal/compiler/implementation/ssa/optimize.dart b/sdk/lib/_internal/compiler/implementation/ssa/optimize.dart
index e433676..463e198 100644
--- a/sdk/lib/_internal/compiler/implementation/ssa/optimize.dart
+++ b/sdk/lib/_internal/compiler/implementation/ssa/optimize.dart
@@ -1153,6 +1153,12 @@
   }
 }
 
+class GvnWorkItem {
+  final HBasicBlock block;
+  final ValueSet valueSet;
+  GvnWorkItem(this.block, this.valueSet);
+}
+
 class SsaGlobalValueNumberer implements OptimizationPhase {
   final String name = "SsaGlobalValueNumberer";
   final Compiler compiler;
@@ -1166,7 +1172,12 @@
   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) {
@@ -1243,7 +1254,8 @@
     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];
@@ -1280,10 +1292,16 @@
       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));
     }
   }
 
@@ -1329,7 +1347,8 @@
   }
 
   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++) {
@@ -1344,7 +1363,7 @@
         // 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;