Remove unnecessary work in dominators computation.

Also rename 'undomid' to better indicate how it is being used.

This fixes a performance problem with the dominators computation for
some pathological cases, in one case reducing the time to compute
dominators from 10 minutes down to a few seconds.

Bug: 33957507
Test: m ahat-test
Test: manually verify overview and rooted numbers are unchanged for a
      reasonably complex heap dump.

Change-Id: I2a13f6b62f0bf56e6051da637d9872ea8f8b3d2d
diff --git a/tools/ahat/src/dominators/DominatorsComputation.java b/tools/ahat/src/dominators/DominatorsComputation.java
index 9a2a272..58b7b59 100644
--- a/tools/ahat/src/dominators/DominatorsComputation.java
+++ b/tools/ahat/src/dominators/DominatorsComputation.java
@@ -88,33 +88,17 @@
     // Invariant: srcS.id < this.id
     public NodeS srcS;
 
+    // The largest id of the nodes we have seen so far on a path from the root
+    // to this node. Used to keep track of which nodes we have already seen
+    // and avoid processing them again.
+    public long seenid;
+
     // The set of nodes X reachable by 'this' on a path of nodes from the
     // root with increasing ids (possibly excluding X) that this node does not
     // dominate (this.id > X.domid).
-    // We can use a List instead of a Set for this because we guarentee that
-    // we don't add the same node more than once to the list (see below).
+    // We can use a List instead of a Set for this because we guarentee based
+    // on seenid that we don't add the same node more than once to the list.
     public List<NodeS> undom = new ArrayList<NodeS>();
-
-    // The largest id of the node X for which we did X.undom.add(this).
-    // This is an optimization to avoid adding duplicate node entries to the
-    // undom set.
-    //
-    // The first time we see this node, we reach it through a path of nodes
-    // with IDs 0,...,a,this. These form our src chain to the root.
-    //
-    // The next time we see this node, we reach it through a path of nodes
-    // with IDS 0,...,b,c,...,d,this. Where all 0,...,b < a and all c,...,d > a.
-    //
-    // The next time we see this node, we reach it through a path of nodes
-    // with IDS 0,...,e,f,...,g,this. With all 0,...,e < d and all f,...,g > d.
-    // And so on.
-    //
-    // The first time we see this node, we set undomid to a.id. Nodes 0,...,a
-    // will be added as undom in the 'revisit' phase of the node.
-    //
-    // The next times we see this node, we mark a+,...,d as undom and
-    // change undomid to d. And so on.
-    public long undomid;
   }
 
   private static class Link {
@@ -171,7 +155,7 @@
         dstS.domid = link.srcS.id;
         dstS.domS = link.srcS;
         dstS.srcS = link.srcS;
-        dstS.undomid = dstS.domid;
+        dstS.seenid = dstS.domid;
         nodes.add(dstS);
         link.dst.setDominatorsComputationState(dstS);
 
@@ -184,13 +168,11 @@
         NodeS srcS = link.srcS;
         boolean revisiting = dstS.domid < dstS.domS.id;
 
-        while (srcS.id > dstS.domid) {
-          if (srcS.id > dstS.undomid) {
-            srcS.undom.add(dstS);
-          }
+        while (srcS.id > dstS.seenid) {
+          srcS.undom.add(dstS);
           srcS = srcS.srcS;
         }
-        dstS.undomid = link.srcS.id;
+        dstS.seenid = link.srcS.id;
 
         if (srcS.id < dstS.domid) {
           // In this case, dstS.domid must be wrong, because we just found a