Add a more flexible Dominators API.

Adds a new API for accessing the DominatorsComputation that makes it
easier to pass global state through the computation.

Bug: 79131879
Test: m ahat-test, with tests for new API added.

Change-Id: Id81a192abd1087773837714ccf2a7b3577a32992
diff --git a/tools/ahat/etc/ahat_api.txt b/tools/ahat/etc/ahat_api.txt
index f60c1a8..8c7ff64 100644
--- a/tools/ahat/etc/ahat_api.txt
+++ b/tools/ahat/etc/ahat_api.txt
@@ -8,7 +8,20 @@
 
 package com.android.ahat.dominators {
 
-  public class DominatorsComputation {
+  public class Dominators<Node> {
+    ctor public Dominators(com.android.ahat.dominators.Dominators.Graph);
+    method public void computeDominators(Node);
+    method public com.android.ahat.dominators.Dominators progress(com.android.ahat.progress.Progress, long);
+  }
+
+  public static abstract interface Dominators.Graph<Node> {
+    method public abstract java.lang.Object getDominatorsComputationState(Node);
+    method public abstract java.lang.Iterable<? extends Node> getReferencesForDominators(Node);
+    method public abstract void setDominator(Node, Node);
+    method public abstract void setDominatorsComputationState(Node, java.lang.Object);
+  }
+
+  public deprecated class DominatorsComputation {
     method public static void computeDominators(com.android.ahat.dominators.DominatorsComputation.Node);
     method public static void computeDominators(com.android.ahat.dominators.DominatorsComputation.Node, com.android.ahat.progress.Progress, long);
   }
diff --git a/tools/ahat/src/main/com/android/ahat/dominators/Dominators.java b/tools/ahat/src/main/com/android/ahat/dominators/Dominators.java
new file mode 100644
index 0000000..dda0e83
--- /dev/null
+++ b/tools/ahat/src/main/com/android/ahat/dominators/Dominators.java
@@ -0,0 +1,476 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.ahat.dominators;
+
+import com.android.ahat.progress.NullProgress;
+import com.android.ahat.progress.Progress;
+import java.util.ArrayDeque;
+import java.util.Arrays;
+import java.util.Deque;
+import java.util.Queue;
+
+/**
+ * Computes the immediate dominators of a directed graph. It can be used with
+ * any directed graph data structure that implements the
+ * {@link Dominators.Graph} interface and has some root node with no incoming
+ * edges.
+ */
+public class Dominators<Node> {
+  private final Graph<Node> graph;
+
+  private Progress progress = new NullProgress();
+  private long numNodes = 0;
+
+  /**
+   * Interface for a directed graph to perform immediate dominators
+   * computation on.
+   * The dominators computation can be used with directed graph data
+   * structures that implement this <code>Graph</code> interface. To use the
+   * dominators computation on your graph, you must make the following
+   * functionality available to the dominators computation:
+   * <ul>
+   * <li>Efficiently mapping from node to associated internal dominators
+   *     computation state using the
+   *     {@link #setDominatorsComputationState setDominatorsComputationState} and
+   *     {@link #getDominatorsComputationState getDominatorsComputationState} methods.
+   * <li>Iterating over all outgoing edges of an node using the
+   *     {@link #getReferencesForDominators getReferencesForDominators} method.
+   * <li>Setting the computed dominator for a node using the
+   *     {@link #setDominator setDominator} method.
+   * </ul>
+   */
+  public interface Graph<Node> {
+    /**
+     * Associates the given dominator state with the given node. Subsequent
+     * calls to
+     * {@link #getDominatorsComputationState getDominatorsComputationState} on
+     * this node should return the state given here. At the conclusion of the
+     * dominators computation, this method will be called for
+     * each node with <code>state</code> set to null.
+     *
+     * @param node the node to associate dominator state
+     * @param state the dominator state to associate with the node
+     */
+    void setDominatorsComputationState(Node node, Object state);
+
+    /**
+     * Returns the dominator state most recently associated with the given node
+     * by a call to {@link #setDominatorsComputationState setDominatorsComputationState}.
+     * If <code>setDominatorsComputationState</code> has not yet been called
+     * on this node for this dominators computation, this method should return
+     * null.
+     *
+     * @param node the node to get the dominator state for
+     * @return the associated dominator state
+     */
+    Object getDominatorsComputationState(Node node);
+
+    /**
+     * Returns a collection of nodes referenced from the given node, for the
+     * purposes of computing dominators. This method will be called at most
+     * once for each node reachable from the root node of the dominators
+     * computation.
+     *
+     * @param node the node to get the references for
+     * @return an iterable collection of the nodes with an incoming edge from
+     *         the node.
+     */
+    Iterable<? extends Node> getReferencesForDominators(Node node);
+
+    /**
+     * Sets the dominator for the given node based on the results of the
+     * dominators computation.
+     *
+     * @param node the node to set the dominator for
+     * @param dominator the computed immediate dominator of the node
+     */
+    void setDominator(Node node, Node dominator);
+  }
+
+  /**
+   * Construct an object to do dominators computation on the given graph.
+   *
+   * @param graph the graph to compute the dominators of
+   */
+  public Dominators(Graph graph) {
+    this.graph = graph;
+  }
+
+  /**
+   * Sets up a progress tracker for the dominators computation.
+   *
+   * @param progress the progress tracker to use
+   * @param numNodes an upper bound on the number of nodes in the graph
+   * @return this Dominators object
+   */
+  public Dominators progress(Progress progress, long numNodes) {
+    this.progress = progress;
+    this.numNodes = numNodes;
+    return this;
+  }
+
+  // NodeS is information associated with a particular node for the
+  // purposes of computing dominators.
+  // By convention we use the suffix 'S' to name instances of NodeS.
+  private static class NodeS {
+    // The node that this NodeS is associated with.
+    public Object node;
+
+    // Unique identifier for this node, in increasing order based on the order
+    // this node was visited in a depth first search from the root. In
+    // particular, given nodes A and B, if A.id > B.id, then A cannot be a
+    // dominator of B.
+    public long id;
+
+    // The largest id of all nodes reachable from this node.
+    // If foo.id > this.maxReachableId, then foo is not reachable from this
+    // node.
+    public long maxReachableId;
+
+    // The set of ids of nodes that have references to this node.
+    public IdSet inRefIds = new IdSet();
+
+    // The current candidate dominator for this node.
+    // The true immediate dominator of this node must have id <= domS.id.
+    public NodeS domS;
+
+    // The previous candidate dominator for this node.
+    // Invariant:
+    // * There are no nodes xS reachable from this node on a path of nodes
+    //   with increasing ids (not counting xS.id) for which
+    //   this.id > xS.domS.id > this.oldDomS.id.
+    // This ensures that when all nodes xS satisfy xS.domS == xS.oldDomS, we
+    // have found the true immediate dominator of each node.
+    //
+    // Note: We only use this field to tell if this node is scheduled to be
+    // revisited. We could replace it with a boolean to save space, but it
+    // probably doesn't save that much space and it's easier to explain the
+    // algorithm if we can refer to this field.
+    public NodeS oldDomS;
+
+    // The set of nodes that this node is the candidate immediate dominator
+    // of. More precisely, the set of nodes xS such that xS.domS == this.
+    public NodeSet dominated = new NodeSet();
+
+    // The set of nodes that this node is the old candidate immediate
+    // dominator of that need to be revisited. Specifically, the set of nodes
+    // xS such that:
+    //   xS.oldDomS == this && xS.oldDomS != xS.domS.
+    //
+    // The empty set is represented as null instead of an empty NodeSet to
+    // save memory.
+    // Invariant:
+    //   If revisit != null, this node is on the global list of nodes to be
+    //   revisited.
+    public NodeSet revisit = null;
+
+    // Distance from the root to this node. Used for purposes of tracking
+    // progress only.
+    public long depth;
+  }
+
+  // A collection of node ids.
+  private static class IdSet {
+    private int size = 0;
+    private long[] ids = new long[4];
+
+    // Adds an id to the set.
+    public void add(long id) {
+      if (size == ids.length) {
+        ids = Arrays.copyOf(ids, size * 2);
+      }
+      ids[size++] = id;
+    }
+
+    // Returns the most recent id added to the set. Behavior is undefined if
+    // the set is empty.
+    public long last() {
+      assert size != 0;
+      return ids[size - 1];
+    }
+
+    // Returns true if the set contains an id in the range [low, high]
+    // inclusive, false otherwise.
+    public boolean hasIdInRange(long low, long high) {
+      for (int i = 0; i < size; ++i) {
+        if (low <= ids[i] && ids[i] <= high) {
+          return true;
+        }
+      }
+      return false;
+    }
+  }
+
+  // An unordered set of nodes data structure supporting efficient iteration
+  // over elements. The bulk of the time spent in the dominators algorithm is
+  // iterating over these sets. Using an array to store the set provides
+  // noticable performance improvements over ArrayList or a linked list.
+  private static class NodeSet {
+    public int size = 0;
+    public NodeS[] nodes = new NodeS[4];
+
+    public void add(NodeS nodeS) {
+      if (size == nodes.length) {
+        nodes = Arrays.copyOf(nodes, size * 2);
+      }
+      nodes[size++] = nodeS;
+    }
+
+    public void remove(NodeS nodeS) {
+      for (int i = 0; i < size; ++i) {
+        if (nodes[i] == nodeS) {
+          remove(i);
+          break;
+        }
+      }
+    }
+
+    public void remove(int index) {
+      nodes[index] = nodes[--size];
+      nodes[size] = null;
+    }
+  }
+
+  // A reference from a source node to a destination node to be processed
+  // during the initial depth-first traversal of nodes.
+  //
+  // Also used as a marker to indicate when the depth-first traversal has been
+  // completed for a node. In that case, srcS is the node depth-first
+  // traversal has been completed for, and dst will be set to null.
+  private static class Link<Node> {
+    public final NodeS srcS;
+    public final Node dst;
+
+    // Constructor for a reference from srcS to dst.
+    public Link(NodeS srcS, Node dst) {
+      this.srcS = srcS;
+      this.dst = dst;
+    }
+
+    // Constructor for a marker indicating depth-first traversal has been
+    // completed for srcS.
+    public Link(NodeS srcS) {
+      this.srcS = srcS;
+      this.dst = null;
+    }
+  }
+
+  /**
+   * Computes the immediate dominators of all nodes reachable from the <code>root</code> node.
+   * There must not be any incoming references to the <code>root</code> node.
+   * <p>
+   * The result of this function is to call the {@link Graph#setDominator}
+   * function on every node reachable from the root node.
+   *
+   * @param root the root node of the dominators computation
+   */
+  public void computeDominators(Node root) {
+    long id = 0;
+
+    // The set of nodes xS such that xS.revisit != null.
+    // Use a Queue instead of a Set because performance will be better. We
+    // avoid adding nodes already on the queue by checking
+    // xS == null before adding the node to the queue.
+    Queue<NodeS> revisit = new ArrayDeque<NodeS>();
+
+    // Set up the root node specially.
+    NodeS rootS = new NodeS();
+    rootS.node = root;
+    rootS.id = id++;
+    rootS.depth = 0;
+    graph.setDominatorsComputationState(root, rootS);
+
+    Deque<Link<Node>> dfs = new ArrayDeque<Link<Node>>();
+    dfs.push(new Link(rootS));
+    for (Node child : graph.getReferencesForDominators(root)) {
+      dfs.push(new Link(rootS, child));
+    }
+
+    // workBound is an upper bound on the amount of work required in the
+    // second phase of dominators computation, used solely for the purposes of
+    // tracking progress.
+    long workBound = 0;
+
+    // 1. Do a depth first search of the nodes, label them with ids and come
+    // up with initial candidate dominators for them.
+    progress.start("Initializing dominators", numNodes);
+    while (!dfs.isEmpty()) {
+      Link<Node> link = dfs.pop();
+
+      if (link.dst == null) {
+        // This is the marker link indicating we have now visited all
+        // nodes reachable from link.srcS.
+        link.srcS.maxReachableId = id - 1;
+        progress.advance();
+      } else {
+        NodeS dstS = (NodeS)graph.getDominatorsComputationState(link.dst);
+        if (dstS == null) {
+          // We are seeing the destination node for the first time.
+          // The candidate dominator is the source node.
+          dstS = new NodeS();
+          graph.setDominatorsComputationState(link.dst, dstS);
+
+          dstS.node = link.dst;
+          dstS.id = id++;
+          dstS.inRefIds.add(link.srcS.id);
+          dstS.domS = link.srcS;
+          dstS.domS.dominated.add(dstS);
+          dstS.oldDomS = link.srcS;
+          dstS.depth = link.srcS.depth + 1;
+
+          dfs.push(new Link<>(dstS));
+          for (Node child : graph.getReferencesForDominators(link.dst)) {
+            dfs.push(new Link<>(dstS, child));
+          }
+        } else {
+          // We have seen the destination node before. Update the state based
+          // on the new potential dominator.
+          if (dstS.inRefIds.size == 1) {
+            workBound += dstS.oldDomS.depth;
+          }
+
+          long seenid = dstS.inRefIds.last();
+          dstS.inRefIds.add(link.srcS.id);
+
+          // Go up the dominator chain until we reach a node we haven't already
+          // seen with a path to dstS.
+          NodeS xS = link.srcS;
+          while (xS.id > seenid) {
+            xS = xS.domS;
+          }
+
+          // The new dominator for dstS must have an id less than the node we
+          // just reached. Pull the dominator for dstS up its dominator
+          // chain until we find a suitable new dominator for dstS.
+          long domid = xS.id;
+          if (dstS.domS.id > domid) {
+            // Mark the node as needing to be revisited.
+            if (dstS.domS == dstS.oldDomS) {
+              if (dstS.oldDomS.revisit == null) {
+                dstS.oldDomS.revisit = new NodeSet();
+                revisit.add(dstS.oldDomS);
+              }
+              dstS.oldDomS.revisit.add(dstS);
+            }
+
+            // Update the node's candidate dominator.
+            dstS.domS.dominated.remove(dstS);
+            do {
+              dstS.domS = dstS.domS.domS;
+            } while (dstS.domS.id > domid);
+            dstS.domS.dominated.add(dstS);
+          }
+        }
+      }
+    }
+    progress.done();
+
+    // 2. Continue revisiting nodes until every node satisfies the requirement
+    // that domS.id == oldDomS.id.
+    progress.start("Resolving dominators", workBound);
+    while (!revisit.isEmpty()) {
+      NodeS oldDomS = revisit.poll();
+      assert oldDomS.revisit != null;
+
+      NodeSet nodes = oldDomS.revisit;
+      oldDomS.revisit = null;
+
+      // Search for pairs of nodes nodeS, xS for which
+      //    nodeS.id > xS.domS.id > nodeS.oldDomS.id
+      // and there is a path of nodes with increasing ids from nodeS to xS.
+      // In that case, xS.domS must be wrong, because there is a path to xS
+      // from the root that does not go through xS.domS:
+      // * There is a path from the root to nodeS.oldDomS that doesn't go
+      //   through xS.domS. Otherwise xS.domS would be a dominator of
+      //   nodeS.oldDomS, but it can't be because xS.domS.id > nodeS.oldDomS.id.
+      // * There is a path from nodeS.oldDomS to nodeS that doesn't go through
+      //   xS.domS, because xS.domS is not a dominator of nodeS.
+      // * There is a path from nodeS to xS that doesn't go through xS.domS,
+      //   because we have a path of increasing ids from nodeS to xS, none of
+      //   which can have an id smaller than nodeS as xS.domS does.
+      for (int i = 0; i < oldDomS.dominated.size; ++i) {
+        NodeS xS = oldDomS.dominated.nodes[i];
+        for (int j = 0; j < nodes.size; ++j) {
+          NodeS nodeS = nodes.nodes[j];
+          assert nodeS.oldDomS == oldDomS;
+          if (isReachableAscending(nodeS, xS)) {
+            // Update the dominator for xS.
+            if (xS.domS == xS.oldDomS) {
+              if (xS.oldDomS.revisit == null) {
+                xS.oldDomS.revisit = new NodeSet();
+                revisit.add(xS.oldDomS);
+              }
+              xS.oldDomS.revisit.add(xS);
+            }
+            oldDomS.dominated.remove(i--);
+            xS.domS = nodeS.domS;
+            xS.domS.dominated.add(xS);
+            break;
+          }
+        }
+      }
+
+      // We can now safely update oldDomS for each of the nodes nodeS while
+      // preserving the oldDomS invariant.
+      for (int i = 0; i < nodes.size; ++i) {
+        NodeS nodeS = nodes.nodes[i];
+        nodeS.oldDomS = oldDomS.oldDomS;
+        if (nodeS.oldDomS != nodeS.domS) {
+          if (nodeS.oldDomS.revisit == null) {
+            nodeS.oldDomS.revisit = new NodeSet();
+            revisit.add(nodeS.oldDomS);
+          }
+          nodeS.oldDomS.revisit.add(nodeS);
+        }
+      }
+      progress.advance((oldDomS.depth - oldDomS.oldDomS.depth) * nodes.size);
+    }
+    progress.done();
+
+
+    // 3. We have figured out the correct dominator for each node. Notify the
+    // user of the results by doing one last traversal of the nodes.
+    assert revisit.isEmpty();
+    revisit.add(rootS);
+    while (!revisit.isEmpty()) {
+      NodeS nodeS = revisit.poll();
+      assert nodeS.domS == nodeS.oldDomS;
+      assert nodeS.revisit == null;
+      graph.setDominatorsComputationState((Node)nodeS.node, null);
+      for (int i = 0; i < nodeS.dominated.size; ++i) {
+        NodeS xS = nodeS.dominated.nodes[i];
+        graph.setDominator((Node)xS.node, (Node)nodeS.node);
+        revisit.add(xS);
+      }
+    }
+  }
+
+  // Returns true if there is a path from srcS to dstS of nodes with ascending
+  // ids (not including dstS.id).
+  private static boolean isReachableAscending(NodeS srcS, NodeS dstS) {
+    if (dstS.id < srcS.id) {
+      // The first time we saw dstS was before we saw srcS. See if srcS is on
+      // the source chain for any nodes with direct references to dstS.
+      return dstS.inRefIds.hasIdInRange(srcS.id, srcS.maxReachableId);
+    }
+
+    // Otherwise dstS is only reachable from srcS on a node with ascending ids
+    // if it was visited for the first time while performing the depth-first
+    // traversal of srcS.
+    return dstS.id <= srcS.maxReachableId;
+  }
+}
diff --git a/tools/ahat/src/main/com/android/ahat/dominators/DominatorsComputation.java b/tools/ahat/src/main/com/android/ahat/dominators/DominatorsComputation.java
index 903211e..7ab52cb 100644
--- a/tools/ahat/src/main/com/android/ahat/dominators/DominatorsComputation.java
+++ b/tools/ahat/src/main/com/android/ahat/dominators/DominatorsComputation.java
@@ -18,18 +18,16 @@
 
 import com.android.ahat.progress.NullProgress;
 import com.android.ahat.progress.Progress;
-import java.util.ArrayDeque;
-import java.util.Arrays;
-import java.util.Deque;
-import java.util.Queue;
 
 /**
  * Provides a static method for computing the immediate dominators of a
  * directed graph. It can be used with any directed graph data structure
  * that implements the {@link DominatorsComputation.Node} interface and has
  * some root node with no incoming edges.
+ *
+ * @deprecated Use {@link Dominators} class instead, which has a nicer interface.
  */
-public class DominatorsComputation {
+@Deprecated public class DominatorsComputation {
   private DominatorsComputation() {
   }
 
@@ -94,152 +92,6 @@
     void setDominator(Node dominator);
   }
 
-  // NodeS is information associated with a particular node for the
-  // purposes of computing dominators.
-  // By convention we use the suffix 'S' to name instances of NodeS.
-  private static class NodeS {
-    // The node that this NodeS is associated with.
-    public Node node;
-
-    // Unique identifier for this node, in increasing order based on the order
-    // this node was visited in a depth first search from the root. In
-    // particular, given nodes A and B, if A.id > B.id, then A cannot be a
-    // dominator of B.
-    public long id;
-
-    // The largest id of all nodes reachable from this node.
-    // If foo.id > this.maxReachableId, then foo is not reachable from this
-    // node.
-    public long maxReachableId;
-
-    // The set of ids of nodes that have references to this node.
-    public IdSet inRefIds = new IdSet();
-
-    // The current candidate dominator for this node.
-    // The true immediate dominator of this node must have id <= domS.id.
-    public NodeS domS;
-
-    // The previous candidate dominator for this node.
-    // Invariant:
-    // * There are no nodes xS reachable from this node on a path of nodes
-    //   with increasing ids (not counting xS.id) for which
-    //   this.id > xS.domS.id > this.oldDomS.id.
-    // This ensures that when all nodes xS satisfy xS.domS == xS.oldDomS, we
-    // have found the true immediate dominator of each node.
-    //
-    // Note: We only use this field to tell if this node is scheduled to be
-    // revisited. We could replace it with a boolean to save space, but it
-    // probably doesn't save that much space and it's easier to explain the
-    // algorithm if we can refer to this field.
-    public NodeS oldDomS;
-
-    // The set of nodes that this node is the candidate immediate dominator
-    // of. More precisely, the set of nodes xS such that xS.domS == this.
-    public NodeSet dominated = new NodeSet();
-
-    // The set of nodes that this node is the old candidate immediate
-    // dominator of that need to be revisited. Specifically, the set of nodes
-    // xS such that:
-    //   xS.oldDomS == this && xS.oldDomS != xS.domS.
-    //
-    // The empty set is represented as null instead of an empty NodeSet to
-    // save memory.
-    // Invariant:
-    //   If revisit != null, this node is on the global list of nodes to be
-    //   revisited.
-    public NodeSet revisit = null;
-
-    // Distance from the root to this node. Used for purposes of tracking
-    // progress only.
-    public long depth;
-  }
-
-  // A collection of node ids.
-  private static class IdSet {
-    private int size = 0;
-    private long[] ids = new long[4];
-
-    // Adds an id to the set.
-    public void add(long id) {
-      if (size == ids.length) {
-        ids = Arrays.copyOf(ids, size * 2);
-      }
-      ids[size++] = id;
-    }
-
-    // Returns the most recent id added to the set. Behavior is undefined if
-    // the set is empty.
-    public long last() {
-      assert size != 0;
-      return ids[size - 1];
-    }
-
-    // Returns true if the set contains an id in the range [low, high]
-    // inclusive, false otherwise.
-    public boolean hasIdInRange(long low, long high) {
-      for (int i = 0; i < size; ++i) {
-        if (low <= ids[i] && ids[i] <= high) {
-          return true;
-        }
-      }
-      return false;
-    }
-  }
-
-  // An unordered set of nodes data structure supporting efficient iteration
-  // over elements. The bulk of the time spent in the dominators algorithm is
-  // iterating over these sets. Using an array to store the set provides
-  // noticable performance improvements over ArrayList or a linked list.
-  private static class NodeSet {
-    public int size = 0;
-    public NodeS[] nodes = new NodeS[4];
-
-    public void add(NodeS nodeS) {
-      if (size == nodes.length) {
-        nodes = Arrays.copyOf(nodes, size * 2);
-      }
-      nodes[size++] = nodeS;
-    }
-
-    public void remove(NodeS nodeS) {
-      for (int i = 0; i < size; ++i) {
-        if (nodes[i] == nodeS) {
-          remove(i);
-          break;
-        }
-      }
-    }
-
-    public void remove(int index) {
-      nodes[index] = nodes[--size];
-      nodes[size] = null;
-    }
-  }
-
-  // A reference from a source node to a destination node to be processed
-  // during the initial depth-first traversal of nodes.
-  //
-  // Also used as a marker to indicate when the depth-first traversal has been
-  // completed for a node. In that case, srcS is the node depth-first
-  // traversal has been completed for, and dst will be set to null.
-  private static class Link {
-    public final NodeS srcS;
-    public final Node dst;
-
-    // Constructor for a reference from srcS to dst.
-    public Link(NodeS srcS, Node dst) {
-      this.srcS = srcS;
-      this.dst = dst;
-    }
-
-    // Constructor for a marker indicating depth-first traversal has been
-    // completed for srcS.
-    public Link(NodeS srcS) {
-      this.srcS = srcS;
-      this.dst = null;
-    }
-  }
-
   /**
    * Computes the immediate dominators of all nodes reachable from the <code>root</code> node.
    * There must not be any incoming references to the <code>root</code> node.
@@ -268,198 +120,28 @@
    * @see Node
    */
   public static void computeDominators(Node root, Progress progress, long numNodes) {
-    long id = 0;
-
-    // The set of nodes xS such that xS.revisit != null.
-    // Use a Queue instead of a Set because performance will be better. We
-    // avoid adding nodes already on the queue by checking
-    // xS == null before adding the node to the queue.
-    Queue<NodeS> revisit = new ArrayDeque<NodeS>();
-
-    // Set up the root node specially.
-    NodeS rootS = new NodeS();
-    rootS.node = root;
-    rootS.id = id++;
-    rootS.depth = 0;
-    root.setDominatorsComputationState(rootS);
-
-    Deque<Link> dfs = new ArrayDeque<Link>();
-    dfs.push(new Link(rootS));
-    for (Node child : root.getReferencesForDominators()) {
-      dfs.push(new Link(rootS, child));
-    }
-
-    // workBound is an upper bound on the amount of work required in the
-    // second phase of dominators computation, used solely for the purposes of
-    // tracking progress.
-    long workBound = 0;
-
-    // 1. Do a depth first search of the nodes, label them with ids and come
-    // up with initial candidate dominators for them.
-    progress.start("Initializing dominators", numNodes);
-    while (!dfs.isEmpty()) {
-      Link link = dfs.pop();
-
-      if (link.dst == null) {
-        // This is the marker link indicating we have now visited all
-        // nodes reachable from link.srcS.
-        link.srcS.maxReachableId = id - 1;
-        progress.advance();
-      } else {
-        NodeS dstS = (NodeS)link.dst.getDominatorsComputationState();
-        if (dstS == null) {
-          // We are seeing the destination node for the first time.
-          // The candidate dominator is the source node.
-          dstS = new NodeS();
-          link.dst.setDominatorsComputationState(dstS);
-
-          dstS.node = link.dst;
-          dstS.id = id++;
-          dstS.inRefIds.add(link.srcS.id);
-          dstS.domS = link.srcS;
-          dstS.domS.dominated.add(dstS);
-          dstS.oldDomS = link.srcS;
-          dstS.depth = link.srcS.depth + 1;
-
-          dfs.push(new Link(dstS));
-          for (Node child : link.dst.getReferencesForDominators()) {
-            dfs.push(new Link(dstS, child));
-          }
-        } else {
-          // We have seen the destination node before. Update the state based
-          // on the new potential dominator.
-          if (dstS.inRefIds.size == 1) {
-            workBound += dstS.oldDomS.depth;
-          }
-
-          long seenid = dstS.inRefIds.last();
-          dstS.inRefIds.add(link.srcS.id);
-
-          // Go up the dominator chain until we reach a node we haven't already
-          // seen with a path to dstS.
-          NodeS xS = link.srcS;
-          while (xS.id > seenid) {
-            xS = xS.domS;
-          }
-
-          // The new dominator for dstS must have an id less than the node we
-          // just reached. Pull the dominator for dstS up its dominator
-          // chain until we find a suitable new dominator for dstS.
-          long domid = xS.id;
-          if (dstS.domS.id > domid) {
-            // Mark the node as needing to be revisited.
-            if (dstS.domS == dstS.oldDomS) {
-              if (dstS.oldDomS.revisit == null) {
-                dstS.oldDomS.revisit = new NodeSet();
-                revisit.add(dstS.oldDomS);
-              }
-              dstS.oldDomS.revisit.add(dstS);
-            }
-
-            // Update the node's candidate dominator.
-            dstS.domS.dominated.remove(dstS);
-            do {
-              dstS.domS = dstS.domS.domS;
-            } while (dstS.domS.id > domid);
-            dstS.domS.dominated.add(dstS);
-          }
-        }
-      }
-    }
-    progress.done();
-
-    // 2. Continue revisiting nodes until every node satisfies the requirement
-    // that domS.id == oldDomS.id.
-    progress.start("Resolving dominators", workBound);
-    while (!revisit.isEmpty()) {
-      NodeS oldDomS = revisit.poll();
-      assert oldDomS.revisit != null;
-
-      NodeSet nodes = oldDomS.revisit;
-      oldDomS.revisit = null;
-
-      // Search for pairs of nodes nodeS, xS for which
-      //    nodeS.id > xS.domS.id > nodeS.oldDomS.id
-      // and there is a path of nodes with increasing ids from nodeS to xS.
-      // In that case, xS.domS must be wrong, because there is a path to xS
-      // from the root that does not go through xS.domS:
-      // * There is a path from the root to nodeS.oldDomS that doesn't go
-      //   through xS.domS. Otherwise xS.domS would be a dominator of
-      //   nodeS.oldDomS, but it can't be because xS.domS.id > nodeS.oldDomS.id.
-      // * There is a path from nodeS.oldDomS to nodeS that doesn't go through
-      //   xS.domS, because xS.domS is not a dominator of nodeS.
-      // * There is a path from nodeS to xS that doesn't go through xS.domS,
-      //   because we have a path of increasing ids from nodeS to xS, none of
-      //   which can have an id smaller than nodeS as xS.domS does.
-      for (int i = 0; i < oldDomS.dominated.size; ++i) {
-        NodeS xS = oldDomS.dominated.nodes[i];
-        for (int j = 0; j < nodes.size; ++j) {
-          NodeS nodeS = nodes.nodes[j];
-          assert nodeS.oldDomS == oldDomS;
-          if (isReachableAscending(nodeS, xS)) {
-            // Update the dominator for xS.
-            if (xS.domS == xS.oldDomS) {
-              if (xS.oldDomS.revisit == null) {
-                xS.oldDomS.revisit = new NodeSet();
-                revisit.add(xS.oldDomS);
-              }
-              xS.oldDomS.revisit.add(xS);
-            }
-            oldDomS.dominated.remove(i--);
-            xS.domS = nodeS.domS;
-            xS.domS.dominated.add(xS);
-            break;
-          }
-        }
+    Dominators.Graph<Node> graph = new Dominators.Graph<Node>() {
+      @Override
+      public void setDominatorsComputationState(Node node, Object state) {
+        node.setDominatorsComputationState(state);
       }
 
-      // We can now safely update oldDomS for each of the nodes nodeS while
-      // preserving the oldDomS invariant.
-      for (int i = 0; i < nodes.size; ++i) {
-        NodeS nodeS = nodes.nodes[i];
-        nodeS.oldDomS = oldDomS.oldDomS;
-        if (nodeS.oldDomS != nodeS.domS) {
-          if (nodeS.oldDomS.revisit == null) {
-            nodeS.oldDomS.revisit = new NodeSet();
-            revisit.add(nodeS.oldDomS);
-          }
-          nodeS.oldDomS.revisit.add(nodeS);
-        }
+      @Override
+      public Object getDominatorsComputationState(Node node) {
+        return node.getDominatorsComputationState();
       }
-      progress.advance((oldDomS.depth - oldDomS.oldDomS.depth) * nodes.size);
-    }
-    progress.done();
 
-
-    // 3. We have figured out the correct dominator for each node. Notify the
-    // user of the results by doing one last traversal of the nodes.
-    assert revisit.isEmpty();
-    revisit.add(rootS);
-    while (!revisit.isEmpty()) {
-      NodeS nodeS = revisit.poll();
-      assert nodeS.domS == nodeS.oldDomS;
-      assert nodeS.revisit == null;
-      nodeS.node.setDominatorsComputationState(null);
-      for (int i = 0; i < nodeS.dominated.size; ++i) {
-        NodeS xS = nodeS.dominated.nodes[i];
-        xS.node.setDominator(nodeS.node);
-        revisit.add(xS);
+      @Override
+      public Iterable<? extends Node> getReferencesForDominators(Node node) {
+        return node.getReferencesForDominators();
       }
-    }
-  }
 
-  // Returns true if there is a path from srcS to dstS of nodes with ascending
-  // ids (not including dstS.id).
-  private static boolean isReachableAscending(NodeS srcS, NodeS dstS) {
-    if (dstS.id < srcS.id) {
-      // The first time we saw dstS was before we saw srcS. See if srcS is on
-      // the source chain for any nodes with direct references to dstS.
-      return dstS.inRefIds.hasIdInRange(srcS.id, srcS.maxReachableId);
-    }
+      @Override
+      public void setDominator(Node node, Node dominator) {
+        node.setDominator(dominator);
+      }
+    };
 
-    // Otherwise dstS is only reachable from srcS on a node with ascending ids
-    // if it was visited for the first time while performing the depth-first
-    // traversal of srcS.
-    return dstS.id <= srcS.maxReachableId;
+    new Dominators(graph).progress(progress, numNodes).computeDominators(root);
   }
 }
diff --git a/tools/ahat/src/test/com/android/ahat/DominatorsTest.java b/tools/ahat/src/test/com/android/ahat/DominatorsTest.java
index d9af363..955b59f 100644
--- a/tools/ahat/src/test/com/android/ahat/DominatorsTest.java
+++ b/tools/ahat/src/test/com/android/ahat/DominatorsTest.java
@@ -16,15 +16,298 @@
 
 package com.android.ahat;
 
+import com.android.ahat.dominators.Dominators;
 import com.android.ahat.dominators.DominatorsComputation;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collection;
+import java.util.HashMap;
 import java.util.List;
+import java.util.Map;
 import org.junit.Test;
 import static org.junit.Assert.assertEquals;
 
 public class DominatorsTest {
+
+  private static class Graph implements Dominators.Graph<String> {
+    private Map<String, Object> states = new HashMap<>();
+    private Map<String, Collection<String>> depends = new HashMap<>();
+    private Map<String, String> dominators = new HashMap<>();
+
+    @Override
+    public void setDominatorsComputationState(String node, Object state) {
+      states.put(node, state);
+    }
+
+    @Override public Object getDominatorsComputationState(String node) {
+      return states.get(node);
+    }
+
+    @Override
+    public Collection<String> getReferencesForDominators(String node) {
+      return depends.get(node);
+    }
+
+    @Override
+    public void setDominator(String node, String dominator) {
+      dominators.put(node, dominator);
+    }
+
+    /**
+     * Define a node in the graph, including all its outgoing edges.
+     */
+    public void node(String src, String... dsts) {
+      depends.put(src, Arrays.asList(dsts));
+    }
+
+    /**
+     * Get the computed dominator for a given node.
+     */
+    public String dom(String node) {
+      return dominators.get(node);
+    }
+  }
+
+  @Test
+  public void singleNode() {
+    // --> n
+    // Trivial case.
+    Graph graph = new Graph();
+    graph.node("n");
+    new Dominators(graph).computeDominators("n");
+  }
+
+  @Test
+  public void parentWithChild() {
+    // --> parent --> child
+    // The child node is dominated by the parent.
+    Graph graph = new Graph();
+    graph.node("parent", "child");
+    graph.node("child");
+    new Dominators(graph).computeDominators("parent");
+
+    assertEquals("parent", graph.dom("child"));
+  }
+
+  @Test
+  public void reachableTwoWays() {
+    //            /-> right -->\
+    // --> parent               child
+    //            \-> left --->/
+    // The child node can be reached either by right or by left.
+    Graph graph = new Graph();
+    graph.node("parent", "left", "right");
+    graph.node("right", "child");
+    graph.node("left", "child");
+    graph.node("child");
+    new Dominators(graph).computeDominators("parent");
+
+    assertEquals("parent", graph.dom("left"));
+    assertEquals("parent", graph.dom("right"));
+    assertEquals("parent", graph.dom("child"));
+  }
+
+  @Test
+  public void reachableDirectAndIndirect() {
+    //            /-> right -->\
+    // --> parent  -----------> child
+    // The child node can be reached either by right or parent.
+    Graph graph = new Graph();
+    graph.node("parent", "right", "child");
+    graph.node("right", "child");
+    graph.node("child");
+    new Dominators(graph).computeDominators("parent");
+
+    assertEquals("parent", graph.dom("child"));
+    assertEquals("parent", graph.dom("right"));
+  }
+
+  @Test
+  public void subDominator() {
+    // --> parent --> middle --> child
+    // The child is dominated by an internal node.
+    Graph graph = new Graph();
+    graph.node("parent", "middle");
+    graph.node("middle", "child");
+    graph.node("child");
+    new Dominators(graph).computeDominators("parent");
+
+    assertEquals("parent", graph.dom("middle"));
+    assertEquals("middle", graph.dom("child"));
+  }
+
+  @Test
+  public void childSelfLoop() {
+    // --> parent --> child -\
+    //                  \<---/
+    // The child points back to itself.
+    Graph graph = new Graph();
+    graph.node("parent", "child");
+    graph.node("child", "child");
+    new Dominators(graph).computeDominators("parent");
+
+    assertEquals("parent", graph.dom("child"));
+  }
+
+  @Test
+  public void singleEntryLoop() {
+    // --> parent --> a --> b --> c -\
+    //                 \<------------/
+    // There is a loop in the graph, with only one way into the loop.
+    Graph graph = new Graph();
+    graph.node("parent", "a");
+    graph.node("a", "b");
+    graph.node("b", "c");
+    graph.node("c", "a");
+    new Dominators(graph).computeDominators("parent");
+
+    assertEquals("parent", graph.dom("a"));
+    assertEquals("a", graph.dom("b"));
+    assertEquals("b", graph.dom("c"));
+  }
+
+  @Test
+  public void multiEntryLoop() {
+    // --> parent --> right --> a --> b ----\
+    //        \                  \<-- c <---/
+    //         \--> left --->--------/
+    // There is a loop in the graph, with two different ways to enter the
+    // loop.
+    Graph graph = new Graph();
+    graph.node("parent", "left", "right");
+    graph.node("left", "c");
+    graph.node("right", "a");
+    graph.node("a", "b");
+    graph.node("b", "c");
+    graph.node("c", "a");
+    new Dominators(graph).computeDominators("parent");
+
+    assertEquals("parent", graph.dom("right"));
+    assertEquals("parent", graph.dom("left"));
+    assertEquals("parent", graph.dom("a"));
+    assertEquals("parent", graph.dom("c"));
+    assertEquals("a", graph.dom("b"));
+  }
+
+  @Test
+  public void dominatorOverwrite() {
+    //            /---------> right <--\
+    // --> parent  --> child <--/      /
+    //            \---> left ---------/
+    // Test a strange case where we have had trouble in the past with a
+    // dominator getting improperly overwritten. The relevant features of this
+    // case are: 'child' is visited after 'right', 'child' is dominated by
+    // 'parent', and 'parent' revisits 'right' after visiting 'child'.
+    Graph graph = new Graph();
+    graph.node("parent", "left", "child", "right");
+    graph.node("right", "child");
+    graph.node("left", "right");
+    graph.node("child");
+    new Dominators(graph).computeDominators("parent");
+
+    assertEquals("parent", graph.dom("left"));
+    assertEquals("parent", graph.dom("child"));
+    assertEquals("parent", graph.dom("right"));
+  }
+
+  @Test
+  public void stackOverflow() {
+    // --> a --> b --> ... --> N
+    // Verify we don't smash the stack for deep chains.
+    Graph graph = new Graph();
+    String root = "end";
+    graph.node(root);
+
+    for (int i = 0; i < 10000; ++i) {
+      String child = root;
+      root = "n" + i;
+      graph.node(root, child);
+    }
+
+    new Dominators(graph).computeDominators(root);
+  }
+
+  @Test
+  public void hiddenRevisit() {
+    //           /-> left ---->---------\
+    // --> parent      \---> a --> b --> c
+    //           \-> right -/
+    // Test a case we have had trouble in the past.
+    // When a's dominator is updated from left to parent, that should trigger
+    // all reachable children's dominators to be updated too. In particular,
+    // c's dominator should be updated, even though b's dominator is
+    // unchanged.
+    Graph graph = new Graph();
+    graph.node("parent", "right", "left");
+    graph.node("right", "a");
+    graph.node("left", "a", "c");
+    graph.node("a", "b");
+    graph.node("b", "c");
+    graph.node("c");
+    new Dominators(graph).computeDominators("parent");
+
+    assertEquals("parent", graph.dom("left"));
+    assertEquals("parent", graph.dom("right"));
+    assertEquals("parent", graph.dom("a"));
+    assertEquals("parent", graph.dom("c"));
+    assertEquals("a", graph.dom("b"));
+  }
+
+  @Test
+  public void preUndominatedUpdate() {
+    //       /--------->--------\
+    //      /          /---->----\
+    // --> p -> a --> b --> c --> d --> e
+    //           \---------->----------/
+    // Test a case we have had trouble in the past.
+    // The candidate dominator for e is revised from d to a, then d is shown
+    // to be reachable from p. Make sure that causes e's dominator to be
+    // refined again from a to p. The extra nodes are there to ensure the
+    // necessary scheduling to expose the bug we had.
+    Graph graph = new Graph();
+    graph.node("p", "d", "a");
+    graph.node("a", "e", "b");
+    graph.node("b", "d", "c");
+    graph.node("c", "d");
+    graph.node("d", "e");
+    graph.node("e");
+    new Dominators(graph).computeDominators("p");
+
+    assertEquals("p", graph.dom("a"));
+    assertEquals("a", graph.dom("b"));
+    assertEquals("b", graph.dom("c"));
+    assertEquals("p", graph.dom("d"));
+    assertEquals("p", graph.dom("e"));
+  }
+
+  @Test
+  public void twiceRevisit() {
+    //       /---->---\
+    //      /     /--> f -->-\
+    // --> a --> b -->--x---> c --> d
+    //            \----------->----/
+    // A regression test for a bug where we failed to ever revisit a node more
+    // than once. The node c is revisited a first time to bring its dominator
+    // up to b. c needs to be revisited again after the dominator for f is
+    // pulled up to a, and that revisit of c is necessary to ensure the
+    // dominator for d is pulled up to a.
+    Graph graph = new Graph();
+    graph.node("a", "f", "b");
+    graph.node("b", "f", "d", "x");
+    graph.node("x", "c");
+    graph.node("c", "d");
+    graph.node("d");
+    graph.node("f", "c");
+    new Dominators(graph).computeDominators("a");
+
+    assertEquals("a", graph.dom("b"));
+    assertEquals("b", graph.dom("x"));
+    assertEquals("a", graph.dom("c"));
+    assertEquals("a", graph.dom("d"));
+    assertEquals("a", graph.dom("f"));
+  }
+
+  // Test the old dominators API.
   private static class Node implements DominatorsComputation.Node {
     public String name;
     public List<Node> depends = new ArrayList<Node>();
@@ -65,248 +348,13 @@
   }
 
   @Test
-  public void singleNode() {
-    // --> n
-    // Trivial case.
-    Node n = new Node("n");
-    n.computeDominators();
-  }
-
-  @Test
-  public void parentWithChild() {
-    // --> parent --> child
-    // The child node is dominated by the parent.
-    Node parent = new Node("parent");
-    Node child = new Node("child");
-    parent.depends = Arrays.asList(child);
-
-    parent.computeDominators();
-    assertEquals(parent, child.dominator);
-  }
-
-  @Test
-  public void reachableTwoWays() {
-    //            /-> right -->\
-    // --> parent               child
-    //            \-> left --->/
-    // The child node can be reached either by right or by left.
-    Node parent = new Node("parent");
-    Node right = new Node("right");
-    Node left = new Node("left");
-    Node child = new Node("child");
-    parent.depends = Arrays.asList(left, right);
-    right.depends = Arrays.asList(child);
-    left.depends = Arrays.asList(child);
-
-    parent.computeDominators();
-    assertEquals(parent, left.dominator);
-    assertEquals(parent, right.dominator);
-    assertEquals(parent, child.dominator);
-  }
-
-  @Test
-  public void reachableDirectAndIndirect() {
-    //            /-> right -->\
-    // --> parent  -----------> child
-    // The child node can be reached either by right or parent.
-    Node parent = new Node("parent");
-    Node right = new Node("right");
-    Node child = new Node("child");
-    parent.depends = Arrays.asList(right, child);
-    right.depends = Arrays.asList(child);
-
-    parent.computeDominators();
-    assertEquals(parent, child.dominator);
-    assertEquals(parent, right.dominator);
-  }
-
-  @Test
-  public void subDominator() {
-    // --> parent --> middle --> child
-    // The child is dominated by an internal node.
-    Node parent = new Node("parent");
-    Node middle = new Node("middle");
-    Node child = new Node("child");
-    parent.depends = Arrays.asList(middle);
-    middle.depends = Arrays.asList(child);
-
-    parent.computeDominators();
-    assertEquals(parent, middle.dominator);
-    assertEquals(middle, child.dominator);
-  }
-
-  @Test
-  public void childSelfLoop() {
-    // --> parent --> child -\
-    //                  \<---/
-    // The child points back to itself.
-    Node parent = new Node("parent");
-    Node child = new Node("child");
-    parent.depends = Arrays.asList(child);
-    child.depends = Arrays.asList(child);
-
-    parent.computeDominators();
-    assertEquals(parent, child.dominator);
-  }
-
-  @Test
-  public void singleEntryLoop() {
-    // --> parent --> a --> b --> c -\
-    //                 \<------------/
-    // There is a loop in the graph, with only one way into the loop.
-    Node parent = new Node("parent");
-    Node a = new Node("a");
-    Node b = new Node("b");
-    Node c = new Node("c");
-    parent.depends = Arrays.asList(a);
-    a.depends = Arrays.asList(b);
-    b.depends = Arrays.asList(c);
-    c.depends = Arrays.asList(a);
-
-    parent.computeDominators();
-    assertEquals(parent, a.dominator);
-    assertEquals(a, b.dominator);
-    assertEquals(b, c.dominator);
-  }
-
-  @Test
-  public void multiEntryLoop() {
-    // --> parent --> right --> a --> b ----\
-    //        \                  \<-- c <---/
-    //         \--> left --->--------/
-    // There is a loop in the graph, with two different ways to enter the
-    // loop.
-    Node parent = new Node("parent");
-    Node left = new Node("left");
-    Node right = new Node("right");
-    Node a = new Node("a");
-    Node b = new Node("b");
-    Node c = new Node("c");
-    parent.depends = Arrays.asList(left, right);
-    right.depends = Arrays.asList(a);
-    left.depends = Arrays.asList(c);
-    a.depends = Arrays.asList(b);
-    b.depends = Arrays.asList(c);
-    c.depends = Arrays.asList(a);
-
-    parent.computeDominators();
-    assertEquals(parent, right.dominator);
-    assertEquals(parent, left.dominator);
-    assertEquals(parent, a.dominator);
-    assertEquals(parent, c.dominator);
-    assertEquals(a, b.dominator);
-  }
-
-  @Test
-  public void dominatorOverwrite() {
-    //            /---------> right <--\
-    // --> parent  --> child <--/      /
-    //            \---> left ---------/
-    // Test a strange case where we have had trouble in the past with a
-    // dominator getting improperly overwritten. The relevant features of this
-    // case are: 'child' is visited after 'right', 'child' is dominated by
-    // 'parent', and 'parent' revisits 'right' after visiting 'child'.
-    Node parent = new Node("parent");
-    Node right = new Node("right");
-    Node left = new Node("left");
-    Node child = new Node("child");
-    parent.depends = Arrays.asList(left, child, right);
-    left.depends = Arrays.asList(right);
-    right.depends = Arrays.asList(child);
-
-    parent.computeDominators();
-    assertEquals(parent, left.dominator);
-    assertEquals(parent, child.dominator);
-    assertEquals(parent, right.dominator);
-  }
-
-  @Test
-  public void stackOverflow() {
-    // --> a --> b --> ... --> N
-    // Verify we don't smash the stack for deep chains.
-    Node root = new Node("root");
-    Node curr = root;
-    for (int i = 0; i < 10000; ++i) {
-      Node node = new Node("n" + i);
-      curr.depends.add(node);
-      curr = node;
-    }
-
-    root.computeDominators();
-  }
-
-  @Test
-  public void hiddenRevisit() {
-    //           /-> left ---->---------\
-    // --> parent      \---> a --> b --> c
-    //           \-> right -/
-    // Test a case we have had trouble in the past.
-    // When a's dominator is updated from left to parent, that should trigger
-    // all reachable children's dominators to be updated too. In particular,
-    // c's dominator should be updated, even though b's dominator is
-    // unchanged.
-    Node parent = new Node("parent");
-    Node right = new Node("right");
-    Node left = new Node("left");
-    Node a = new Node("a");
-    Node b = new Node("b");
-    Node c = new Node("c");
-    parent.depends = Arrays.asList(right, left);
-    left.depends = Arrays.asList(a, c);
-    right.depends = Arrays.asList(a);
-    a.depends = Arrays.asList(b);
-    b.depends = Arrays.asList(c);
-
-    parent.computeDominators();
-    assertEquals(parent, left.dominator);
-    assertEquals(parent, right.dominator);
-    assertEquals(parent, a.dominator);
-    assertEquals(parent, c.dominator);
-    assertEquals(a, b.dominator);
-  }
-
-  @Test
-  public void preUndominatedUpdate() {
-    //       /--------->--------\
-    //      /          /---->----\
-    // --> p -> a --> b --> c --> d --> e
-    //           \---------->----------/
-    // Test a case we have had trouble in the past.
-    // The candidate dominator for e is revised from d to a, then d is shown
-    // to be reachable from p. Make sure that causes e's dominator to be
-    // refined again from a to p. The extra nodes are there to ensure the
-    // necessary scheduling to expose the bug we had.
-    Node p = new Node("p");
-    Node a = new Node("a");
-    Node b = new Node("b");
-    Node c = new Node("c");
-    Node d = new Node("d");
-    Node e = new Node("e");
-    p.depends = Arrays.asList(d, a);
-    a.depends = Arrays.asList(e, b);
-    b.depends = Arrays.asList(d, c);
-    c.depends = Arrays.asList(d);
-    d.depends = Arrays.asList(e);
-
-    p.computeDominators();
-    assertEquals(p, a.dominator);
-    assertEquals(a, b.dominator);
-    assertEquals(b, c.dominator);
-    assertEquals(p, d.dominator);
-    assertEquals(p, e.dominator);
-  }
-
-  @Test
-  public void twiceRevisit() {
+  public void twiceRevisitOldApi() {
     //       /---->---\
     //      /     /--> f -->-\
     // --> a --> b -->--x---> c --> d
     //            \----------->----/
-    // A regression test for a bug where we failed to ever revisit a node more
-    // than once. The node c is revisited a first time to bring its dominator
-    // up to b. c needs to be revisited again after the dominator for f is
-    // pulled up to a, and that revisit of c is necessary to ensure the
-    // dominator for d is pulled up to a.
+    // Run the twiceRevisit test using the user api version of computing
+    // dominators.
     Node a = new Node("a");
     Node b = new Node("b");
     Node x = new Node("x");