ahat: Switch to a custom dominators implementation.

Rather than relying on perflib's dominators computation, use our own.
Benefits:
* Over 25% improvement in heap dump processing performance, improving
  ahat startup time by around 1 to 3 seconds on typical Android heap
  dumps.
* Provides more flexibility if we want to tweak the dominators
  computation in the future, for example by treating different
  soft/weak/finalizer differently or additional performance tuning.
* Opens the door to future performance optimizations based around
  eliminating the impedance mismatch between perflib and ahat's
  internal representations of the heap dump.
* Opens the door to possible future features that involve computing
  dominators of non-heap objects, such as dex code items.
* Avoids a bug in perflib's dominators computation when there are
  duplicate class or instance dumps.

Also included in this change:
* Include "class" in toString for class objects.
* Compute Site ObjectsInfos bottom-up in a separate pass.

Bug: 34884751
Bug: 33957507
Test: m ahat-test, with new tests for incoming references and dominators.
Test: Confirm dominator parity with perflib's dominators computation on
      a number of real heap dumps.
Test: Visually compare information reported for overview, rooted, sites,
      object, and objects pages on a real heap dump against ahat-1.2.

Change-Id: I4cf8fb177a0aaaee07ad6fddbc574682f91cc0f7

18 files changed, 1113 insertions, 188 deletions

diff --git a/tools/ahat/src/ObjectsHandler.java b/tools/ahat/src/ObjectsHandler.java
index 86d48f1702..fd226c24bf 100644
--- a/tools/ahat/src/ObjectsHandler.java
+++ b/tools/ahat/src/ObjectsHandler.java
@@ -43,13 +43,7 @@ class ObjectsHandler implements AhatHandler {
     Site site = mSnapshot.getSite(id, depth);
 
     List<AhatInstance> insts = new ArrayList<AhatInstance>();
-    for (AhatInstance inst : site.getObjects()) {
-      if ((heapName == null || inst.getHeap().getName().equals(heapName))
-          && (className == null || inst.getClassName().equals(className))) {
-        insts.add(inst);
-      }
-    }
-
+    site.getObjects(heapName, className, insts);
     Collections.sort(insts, Sort.defaultInstanceCompare(mSnapshot));
 
     doc.title("Objects");
diff --git a/tools/ahat/src/Summarizer.java b/tools/ahat/src/Summarizer.java
index 016eab44f2..3e9da31e96 100644
--- a/tools/ahat/src/Summarizer.java
+++ b/tools/ahat/src/Summarizer.java
@@ -60,14 +60,7 @@ class Summarizer {
       formatted.append("root ");
     }
 
-    // Annotate classes as classes.
-    DocString linkText = new DocString();
-    if (inst.isClassObj()) {
-      linkText.append("class ");
-    }
-
-    linkText.append(inst.toString());
-
+    DocString linkText = DocString.text(inst.toString());
     if (inst.isPlaceHolder()) {
       // Don't make links to placeholder objects.
       formatted.append(linkText);
diff --git a/tools/ahat/src/dominators/DominatorsComputation.java b/tools/ahat/src/dominators/DominatorsComputation.java
new file mode 100644
index 0000000000..9a2a272be0
--- /dev/null
+++ b/tools/ahat/src/dominators/DominatorsComputation.java
@@ -0,0 +1,260 @@
+/*
+ * 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 java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Deque;
+import java.util.List;
+import java.util.Queue;
+
+/**
+ * Generic DominatorsComputation.
+ *
+ * To use the dominators computation, have your graph nodes implement the
+ * DominatorsComputation.Node interface, then call
+ * DominatorsComputation.computeDominators on the single root node.
+ */
+public class DominatorsComputation {
+  /**
+   * Interface for a directed graph to perform the dominators computation on.
+   */
+  public interface Node {
+    /**
+     * Associate the given dominator state with this node.
+     */
+    void setDominatorsComputationState(Object state);
+
+    /**
+     * Get the most recent dominator state associated with this node using
+     * setDominatorsComputationState. If setDominatorsComputationState has not
+     * yet been called, this should return null.
+     */
+    Object getDominatorsComputationState();
+
+    /**
+     * Return a collection of nodes referenced from this node, for the
+     * purposes of computing dominators.
+     */
+    Iterable<? extends Node> getReferencesForDominators();
+
+    /**
+     * Update this node's dominator based on the results of the dominators
+     * computation.
+     */
+    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;
+
+    // Upper bound on the id of this node's dominator.
+    // The true immediate dominator of this node must have id <= domid.
+    // This upper bound is slowly tightened as part of the dominators
+    // computation.
+    public long domid;
+
+    // The current candidate dominator for this node.
+    // Invariant: (domid < domS.id) implies this node is on the queue of
+    // nodes to be revisited.
+    public NodeS domS;
+
+    // A node with a reference to this node that is one step closer to the
+    // root than this node.
+    // Invariant: srcS.id < this.id
+    public NodeS srcS;
+
+    // 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).
+    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 {
+    public NodeS srcS;
+    public Node dst;
+
+    public Link(NodeS srcS, Node dst) {
+      this.srcS = srcS;
+      this.dst = dst;
+    }
+  }
+
+  /**
+   * Compute the dominator tree rooted at the given node.
+   * There must not be any incoming references to the root node.
+   */
+  public static void computeDominators(Node root) {
+    long id = 0;
+
+    // List of all nodes seen. We keep track of this here to update all the
+    // dominators once we are done.
+    List<NodeS> nodes = new ArrayList<NodeS>();
+
+    // The set of nodes N such that N.domid < N.domS.id. These nodes need
+    // to be revisisted because their dominator is clearly wrong.
+    // Use a Queue instead of a Set because performance will be better. We
+    // avoid adding nodes already on the queue by checking whether it was
+    // already true that N.domid < N.domS.id, in which case the node is
+    // already on the queue.
+    Queue<NodeS> revisit = new ArrayDeque<NodeS>();
+
+    // Set up the root node specially.
+    NodeS rootS = new NodeS();
+    rootS.node = root;
+    rootS.id = id++;
+    root.setDominatorsComputationState(rootS);
+
+    // 1. Do a depth first search of the nodes, label them with ids and come
+    // up with intial candidate dominators for them.
+    Deque<Link> dfs = new ArrayDeque<Link>();
+    for (Node child : root.getReferencesForDominators()) {
+      dfs.push(new Link(rootS, child));
+    }
+
+    while (!dfs.isEmpty()) {
+      Link link = dfs.pop();
+      NodeS dstS = (NodeS)link.dst.getDominatorsComputationState();
+      if (dstS == null) {
+        // This is the first time we have seen the node. The candidate
+        // dominator is link src.
+        dstS = new NodeS();
+        dstS.node = link.dst;
+        dstS.id = id++;
+        dstS.domid = link.srcS.id;
+        dstS.domS = link.srcS;
+        dstS.srcS = link.srcS;
+        dstS.undomid = dstS.domid;
+        nodes.add(dstS);
+        link.dst.setDominatorsComputationState(dstS);
+
+        for (Node child : link.dst.getReferencesForDominators()) {
+          dfs.push(new Link(dstS, child));
+        }
+      } else {
+        // We have seen the node already. Update the state based on the new
+        // potential dominator.
+        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);
+          }
+          srcS = srcS.srcS;
+        }
+        dstS.undomid = link.srcS.id;
+
+        if (srcS.id < dstS.domid) {
+          // In this case, dstS.domid must be wrong, because we just found a
+          // path to dstS that does not go through dstS.domid:
+          // All nodes from root to srcS have id < domid, and all nodes from
+          // srcS to dstS had id > domid, so dstS.domid cannot be on this path
+          // from root to dstS.
+          dstS.domid = srcS.id;
+          if (!revisiting) {
+            revisit.add(dstS);
+          }
+        }
+      }
+    }
+
+    // 2. Continue revisiting nodes until they all satisfy the requirement
+    // that domS.id <= domid.
+    while (!revisit.isEmpty()) {
+      NodeS nodeS = revisit.poll();
+      NodeS domS = nodeS.domS;
+      assert nodeS.domid < domS.id;
+      while (domS.id > nodeS.domid) {
+        if (domS.domS.id < nodeS.domid) {
+          // In this case, nodeS.domid must be wrong, because there is a path
+          // from root to nodeS that does not go through nodeS.domid:
+          //  * We can go from root to domS without going through nodeS.domid,
+          //    because otherwise nodeS.domid would dominate domS, not
+          //    domS.domS.
+          //  * We can go from domS to nodeS without going through nodeS.domid
+          //    because we know nodeS is reachable from domS on a path of nodes
+          //    with increases ids, which cannot include nodeS.domid, which
+          //    has a smaller id than domS.
+          nodeS.domid = domS.domS.id;
+        }
+        domS.undom.add(nodeS);
+        domS = domS.srcS;
+      }
+      nodeS.domS = domS;
+      nodeS.domid = domS.id;
+
+      for (NodeS xS : nodeS.undom) {
+        if (domS.id < xS.domid) {
+          // In this case, xS.domid must be wrong, because there is a path
+          // from the root to xX that does not go through xS.domid:
+          //  * We can go from root to nodeS without going through xS.domid,
+          //    because otherwise xS.domid would dominate nodeS, not domS.
+          //  * We can go from nodeS to xS without going through xS.domid
+          //    because we know xS is reachable from nodeS on a path of nodes
+          //    with increasing ids, which cannot include xS.domid, which has
+          //    a smaller id than nodeS.
+          boolean revisiting = xS.domid < xS.domS.id;
+          xS.domid = domS.id;
+          if (!revisiting) {
+            revisit.add(xS);
+          }
+        }
+      }
+    }
+
+    // 3. Update the dominators of the nodes.
+    root.setDominatorsComputationState(null);
+    for (NodeS nodeS : nodes) {
+      nodeS.node.setDominator(nodeS.domS.node);
+      nodeS.node.setDominatorsComputationState(null);
+    }
+  }
+}
diff --git a/tools/ahat/src/heapdump/AhatArrayInstance.java b/tools/ahat/src/heapdump/AhatArrayInstance.java
index d88cf94075..6d4485d4b9 100644
--- a/tools/ahat/src/heapdump/AhatArrayInstance.java
+++ b/tools/ahat/src/heapdump/AhatArrayInstance.java
@@ -20,6 +20,7 @@ import com.android.tools.perflib.heap.ArrayInstance;
 import com.android.tools.perflib.heap.Instance;
 import java.nio.charset.StandardCharsets;
 import java.util.AbstractList;
+import java.util.Collections;
 import java.util.List;
 
 public class AhatArrayInstance extends AhatInstance {
@@ -37,8 +38,8 @@ public class AhatArrayInstance extends AhatInstance {
     super(id);
   }
 
-  @Override void initialize(AhatSnapshot snapshot, Instance inst) {
-    super.initialize(snapshot, inst);
+  @Override void initialize(AhatSnapshot snapshot, Instance inst, Site site) {
+    super.initialize(snapshot, inst, site);
 
     ArrayInstance array = (ArrayInstance)inst;
     switch (array.getArrayType()) {
@@ -49,10 +50,6 @@ public class AhatArrayInstance extends AhatInstance {
           if (objects[i] != null) {
             Instance ref = (Instance)objects[i];
             insts[i] = snapshot.findInstance(ref.getId());
-            if (ref.getNextInstanceToGcRoot() == inst) {
-              String field = "[" + Integer.toString(i) + "]";
-              insts[i].setNextInstanceToGcRoot(this, field);
-            }
           }
         }
         mValues = new AbstractList<Value>() {
@@ -132,6 +129,35 @@ public class AhatArrayInstance extends AhatInstance {
     return mValues.get(index);
   }
 
+  @Override
+  ReferenceIterator getReferences() {
+    // The list of references will be empty if this is a primitive array.
+    List<Reference> refs = Collections.emptyList();
+    if (!mValues.isEmpty()) {
+      Value first = mValues.get(0);
+      if (first == null || first.isAhatInstance()) {
+        refs = new AbstractList<Reference>() {
+          @Override
+          public int size() {
+            return mValues.size();
+          }
+
+          @Override
+          public Reference get(int index) {
+            Value value = mValues.get(index);
+            if (value != null) {
+              assert value.isAhatInstance();
+              String field = "[" + Integer.toString(index) + "]";
+              return new Reference(AhatArrayInstance.this, field, value.asAhatInstance(), true);
+            }
+            return null;
+          }
+        };
+      }
+    }
+    return new ReferenceIterator(refs);
+  }
+
   @Override public boolean isArrayInstance() {
     return true;
   }
diff --git a/tools/ahat/src/heapdump/AhatClassInstance.java b/tools/ahat/src/heapdump/AhatClassInstance.java
index 158de5240d..211592388c 100644
--- a/tools/ahat/src/heapdump/AhatClassInstance.java
+++ b/tools/ahat/src/heapdump/AhatClassInstance.java
@@ -19,6 +19,7 @@ package com.android.ahat.heapdump;
 import com.android.tools.perflib.heap.ClassInstance;
 import com.android.tools.perflib.heap.Instance;
 import java.awt.image.BufferedImage;
+import java.util.AbstractList;
 import java.util.Arrays;
 import java.util.List;
 
@@ -29,8 +30,8 @@ public class AhatClassInstance extends AhatInstance {
     super(id);
   }
 
-  @Override void initialize(AhatSnapshot snapshot, Instance inst) {
-    super.initialize(snapshot, inst);
+  @Override void initialize(AhatSnapshot snapshot, Instance inst, Site site) {
+    super.initialize(snapshot, inst, site);
 
     ClassInstance classInst = (ClassInstance)inst;
     List<ClassInstance.FieldValue> fieldValues = classInst.getValues();
@@ -40,15 +41,7 @@ public class AhatClassInstance extends AhatInstance {
       String name = field.getField().getName();
       String type = field.getField().getType().toString();
       Value value = snapshot.getValue(field.getValue());
-
       mFieldValues[i] = new FieldValue(name, type, value);
-
-      if (field.getValue() instanceof Instance) {
-        Instance ref = (Instance)field.getValue();
-        if (ref.getNextInstanceToGcRoot() == inst) {
-          value.asAhatInstance().setNextInstanceToGcRoot(this, "." + name);
-        }
-      }
     }
   }
 
@@ -101,6 +94,30 @@ public class AhatClassInstance extends AhatInstance {
     return Arrays.asList(mFieldValues);
   }
 
+  @Override
+  ReferenceIterator getReferences() {
+    List<Reference> refs = new AbstractList<Reference>() {
+      @Override
+      public int size() {
+        return mFieldValues.length;
+      }
+
+      @Override
+      public Reference get(int index) {
+        FieldValue field = mFieldValues[index];
+        Value value = field.value;
+        if (value != null && value.isAhatInstance()) {
+          boolean strong = !field.name.equals("referent")
+                        || !isInstanceOfClass("java.lang.ref.Reference");
+          AhatInstance ref = value.asAhatInstance();
+          return new Reference(AhatClassInstance.this, "." + field.name, ref, strong);
+        }
+        return null;
+      }
+    };
+    return new ReferenceIterator(refs);
+  }
+
   /**
    * Returns true if this is an instance of a class with the given name.
    */
diff --git a/tools/ahat/src/heapdump/AhatClassObj.java b/tools/ahat/src/heapdump/AhatClassObj.java
index c5ade1d405..052d7a8e88 100644
--- a/tools/ahat/src/heapdump/AhatClassObj.java
+++ b/tools/ahat/src/heapdump/AhatClassObj.java
@@ -19,6 +19,7 @@ package com.android.ahat.heapdump;
 import com.android.tools.perflib.heap.ClassObj;
 import com.android.tools.perflib.heap.Field;
 import com.android.tools.perflib.heap.Instance;
+import java.util.AbstractList;
 import java.util.Arrays;
 import java.util.Collection;
 import java.util.List;
@@ -34,8 +35,8 @@ public class AhatClassObj extends AhatInstance {
     super(id);
   }
 
-  @Override void initialize(AhatSnapshot snapshot, Instance inst) {
-    super.initialize(snapshot, inst);
+  @Override void initialize(AhatSnapshot snapshot, Instance inst, Site site) {
+    super.initialize(snapshot, inst, site);
 
     ClassObj classObj = (ClassObj)inst;
     mClassName = classObj.getClassName();
@@ -58,13 +59,6 @@ public class AhatClassObj extends AhatInstance {
       String type = field.getKey().getType().toString();
       Value value = snapshot.getValue(field.getValue());
       mStaticFieldValues[index++] = new FieldValue(name, type, value);
-
-      if (field.getValue() instanceof Instance) {
-        Instance ref = (Instance)field.getValue();
-        if (ref.getNextInstanceToGcRoot() == inst) {
-          value.asAhatInstance().setNextInstanceToGcRoot(this, "." + name);
-        }
-      }
     }
   }
 
@@ -96,6 +90,27 @@ public class AhatClassObj extends AhatInstance {
     return Arrays.asList(mStaticFieldValues);
   }
 
+  @Override
+  ReferenceIterator getReferences() {
+    List<Reference> refs = new AbstractList<Reference>() {
+      @Override
+      public int size() {
+        return mStaticFieldValues.length;
+      }
+
+      @Override
+      public Reference get(int index) {
+        FieldValue field = mStaticFieldValues[index];
+        Value value = field.value;
+        if (value != null && value.isAhatInstance()) {
+          return new Reference(AhatClassObj.this, "." + field.name, value.asAhatInstance(), true);
+        }
+        return null;
+      }
+    };
+    return new ReferenceIterator(refs);
+  }
+
   @Override public boolean isClassObj() {
     return true;
   }
@@ -105,11 +120,10 @@ public class AhatClassObj extends AhatInstance {
   }
 
   @Override public String toString() {
-    return mClassName;
+    return "class " + mClassName;
   }
 
   @Override AhatInstance newPlaceHolderInstance() {
     return new AhatPlaceHolderClassObj(this);
   }
 }
-
diff --git a/tools/ahat/src/heapdump/AhatInstance.java b/tools/ahat/src/heapdump/AhatInstance.java
index af369d95d8..8905b7638c 100644
--- a/tools/ahat/src/heapdump/AhatInstance.java
+++ b/tools/ahat/src/heapdump/AhatInstance.java
@@ -16,39 +16,48 @@
 
 package com.android.ahat.heapdump;
 
+import com.android.ahat.dominators.DominatorsComputation;
 import com.android.tools.perflib.heap.ClassObj;
 import com.android.tools.perflib.heap.Instance;
-import com.android.tools.perflib.heap.RootObj;
 import java.awt.image.BufferedImage;
 import java.util.ArrayDeque;
 import java.util.ArrayList;
-import java.util.Arrays;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.Deque;
 import java.util.List;
+import java.util.Queue;
 
-public abstract class AhatInstance implements Diffable<AhatInstance> {
-  private long mId;
+public abstract class AhatInstance implements Diffable<AhatInstance>,
+                                              DominatorsComputation.Node {
+  // The id of this instance from the heap dump.
+  private final long mId;
+
+  // Fields initialized in initialize().
   private Size mSize;
-  private Size[] mRetainedSizes;      // Retained size indexed by heap index
-  private boolean mIsReachable;
   private AhatHeap mHeap;
-  private AhatInstance mImmediateDominator;
-  private AhatInstance mNextInstanceToGcRoot;
-  private String mNextInstanceToGcRootField = "???";
   private AhatClassObj mClassObj;
-  private AhatInstance[] mHardReverseReferences;
-  private AhatInstance[] mSoftReverseReferences;
   private Site mSite;
 
   // If this instance is a root, mRootTypes contains a set of the root types.
   // If this instance is not a root, mRootTypes is null.
   private List<String> mRootTypes;
 
-  // List of instances this instance immediately dominates.
+  // Fields initialized in computeReverseReferences().
+  private AhatInstance mNextInstanceToGcRoot;
+  private String mNextInstanceToGcRootField;
+  private ArrayList<AhatInstance> mHardReverseReferences;
+  private ArrayList<AhatInstance> mSoftReverseReferences;
+
+  // Fields initialized in DominatorsComputation.computeDominators().
+  // mDominated - the list of instances immediately dominated by this instance.
+  // mRetainedSizes - retained size indexed by heap index.
+  private AhatInstance mImmediateDominator;
   private List<AhatInstance> mDominated = new ArrayList<AhatInstance>();
+  private Size[] mRetainedSizes;
+  private Object mDominatorsComputationState;
 
+  // The baseline instance for purposes of diff.
   private AhatInstance mBaseline;
 
   public AhatInstance(long id) {
@@ -62,58 +71,16 @@ public abstract class AhatInstance implements Diffable<AhatInstance> {
    * There is no guarantee that the AhatInstances returned by
    * snapshot.findInstance have been initialized yet.
    */
-  void initialize(AhatSnapshot snapshot, Instance inst) {
-    mId = inst.getId();
+  void initialize(AhatSnapshot snapshot, Instance inst, Site site) {
     mSize = new Size(inst.getSize(), 0);
-    mIsReachable = inst.isReachable();
-
-    List<AhatHeap> heaps = snapshot.getHeaps();
-
     mHeap = snapshot.getHeap(inst.getHeap().getName());
 
-    Instance dom = inst.getImmediateDominator();
-    if (dom == null || dom instanceof RootObj) {
-      mImmediateDominator = null;
-    } else {
-      mImmediateDominator = snapshot.findInstance(dom.getId());
-      mImmediateDominator.mDominated.add(this);
-    }
-
     ClassObj clsObj = inst.getClassObj();
     if (clsObj != null) {
       mClassObj = snapshot.findClassObj(clsObj.getId());
     }
 
-    // A couple notes about reverse references:
-    // * perflib sometimes returns unreachable reverse references. If
-    //   snapshot.findInstance returns null, it means the reverse reference is
-    //   not reachable, so we filter it out.
-    // * We store the references as AhatInstance[] instead of
-    //   ArrayList<AhatInstance> because it saves a lot of space and helps
-    //   with performance when there are a lot of AhatInstances.
-    ArrayList<AhatInstance> ahatRefs = new ArrayList<AhatInstance>();
-    ahatRefs = new ArrayList<AhatInstance>();
-    for (Instance ref : inst.getHardReverseReferences()) {
-      AhatInstance ahat = snapshot.findInstance(ref.getId());
-      if (ahat != null) {
-        ahatRefs.add(ahat);
-      }
-    }
-    mHardReverseReferences = new AhatInstance[ahatRefs.size()];
-    ahatRefs.toArray(mHardReverseReferences);
-
-    List<Instance> refs = inst.getSoftReverseReferences();
-    ahatRefs.clear();
-    if (refs != null) {
-      for (Instance ref : refs) {
-        AhatInstance ahat = snapshot.findInstance(ref.getId());
-        if (ahat != null) {
-          ahatRefs.add(ahat);
-        }
-      }
-    }
-    mSoftReverseReferences = new AhatInstance[ahatRefs.size()];
-    ahatRefs.toArray(mSoftReverseReferences);
+    mSite = site;
   }
 
   /**
@@ -166,7 +133,7 @@ public abstract class AhatInstance implements Diffable<AhatInstance> {
    * Returns whether this object is strongly-reachable.
    */
   public boolean isReachable() {
-    return mIsReachable;
+    return mImmediateDominator != null;
   }
 
   /**
@@ -177,6 +144,12 @@ public abstract class AhatInstance implements Diffable<AhatInstance> {
   }
 
   /**
+   * Returns an iterator over the references this AhatInstance has to other
+   * AhatInstances.
+   */
+  abstract ReferenceIterator getReferences();
+
+  /**
    * Returns true if this instance is marked as a root instance.
    */
   public boolean isRoot() {
@@ -227,13 +200,6 @@ public abstract class AhatInstance implements Diffable<AhatInstance> {
   }
 
   /**
-   * Sets the allocation site of this instance.
-   */
-  void setSite(Site site) {
-    mSite = site;
-  }
-
-  /**
    * Returns true if the given instance is a class object
    */
   public boolean isClassObj() {
@@ -311,14 +277,20 @@ public abstract class AhatInstance implements Diffable<AhatInstance> {
    * Returns a list of objects with hard references to this object.
    */
   public List<AhatInstance> getHardReverseReferences() {
-    return Arrays.asList(mHardReverseReferences);
+    if (mHardReverseReferences != null) {
+      return mHardReverseReferences;
+    }
+    return Collections.emptyList();
   }
 
   /**
    * Returns a list of objects with soft references to this object.
    */
   public List<AhatInstance> getSoftReverseReferences() {
-    return Arrays.asList(mSoftReverseReferences);
+    if (mSoftReverseReferences != null) {
+      return mSoftReverseReferences;
+    }
+    return Collections.emptyList();
   }
 
   /**
@@ -425,8 +397,10 @@ public abstract class AhatInstance implements Diffable<AhatInstance> {
   }
 
   void setNextInstanceToGcRoot(AhatInstance inst, String field) {
-    mNextInstanceToGcRoot = inst;
-    mNextInstanceToGcRootField = field;
+    if (mNextInstanceToGcRoot == null && !isRoot()) {
+      mNextInstanceToGcRoot = inst;
+      mNextInstanceToGcRootField = field;
+    }
   }
 
   /** Returns a human-readable identifier for this object.
@@ -466,6 +440,47 @@ public abstract class AhatInstance implements Diffable<AhatInstance> {
   }
 
   /**
+   * Initialize the reverse reference fields of this instance and all other
+   * instances reachable from it. Initializes the following fields:
+   *   mNextInstanceToGcRoot
+   *   mNextInstanceToGcRootField
+   *   mHardReverseReferences
+   *   mSoftReverseReferences
+   */
+  static void computeReverseReferences(AhatInstance root) {
+    // Do a breadth first search to visit the nodes.
+    Queue<Reference> bfs = new ArrayDeque<Reference>();
+    for (Reference ref : root.getReferences()) {
+      bfs.add(ref);
+    }
+    while (!bfs.isEmpty()) {
+      Reference ref = bfs.poll();
+
+      if (ref.ref.mHardReverseReferences == null) {
+        // This is the first time we are seeing ref.ref.
+        ref.ref.mNextInstanceToGcRoot = ref.src;
+        ref.ref.mNextInstanceToGcRootField = ref.field;
+        ref.ref.mHardReverseReferences = new ArrayList<AhatInstance>();
+        for (Reference childRef : ref.ref.getReferences()) {
+          bfs.add(childRef);
+        }
+      }
+
+      // Note: ref.src is null when the src is the SuperRoot.
+      if (ref.src != null) {
+        if (ref.strong) {
+          ref.ref.mHardReverseReferences.add(ref.src);
+        } else {
+          if (ref.ref.mSoftReverseReferences == null) {
+            ref.ref.mSoftReverseReferences = new ArrayList<AhatInstance>();
+          }
+          ref.ref.mSoftReverseReferences.add(ref.src);
+        }
+      }
+    }
+  }
+
+  /**
    * Recursively compute the retained size of the given instance and all
    * other instances it dominates.
    */
@@ -486,8 +501,10 @@ public abstract class AhatInstance implements Diffable<AhatInstance> {
         for (int i = 0; i < numHeaps; i++) {
           inst.mRetainedSizes[i] = Size.ZERO;
         }
-        inst.mRetainedSizes[inst.mHeap.getIndex()] = 
-          inst.mRetainedSizes[inst.mHeap.getIndex()].plus(inst.mSize);
+        if (!(inst instanceof SuperRoot)) {
+          inst.mRetainedSizes[inst.mHeap.getIndex()] =
+            inst.mRetainedSizes[inst.mHeap.getIndex()].plus(inst.mSize);
+        }
         deque.push(inst);
         for (AhatInstance dominated : inst.mDominated) {
           deque.push(dominated);
@@ -501,4 +518,25 @@ public abstract class AhatInstance implements Diffable<AhatInstance> {
       }
     }
   }
+
+  @Override
+  public void setDominatorsComputationState(Object state) {
+    mDominatorsComputationState = state;
+  }
+
+  @Override
+  public Object getDominatorsComputationState() {
+    return mDominatorsComputationState;
+  }
+
+  @Override
+  public Iterable<? extends DominatorsComputation.Node> getReferencesForDominators() {
+    return new DominatorReferenceIterator(getReferences());
+  }
+
+  @Override
+  public void setDominator(DominatorsComputation.Node dominator) {
+    mImmediateDominator = (AhatInstance)dominator;
+    mImmediateDominator.mDominated.add(this);
+  }
 }
diff --git a/tools/ahat/src/heapdump/AhatPlaceHolderInstance.java b/tools/ahat/src/heapdump/AhatPlaceHolderInstance.java
index 4aac80484d..d797b11030 100644
--- a/tools/ahat/src/heapdump/AhatPlaceHolderInstance.java
+++ b/tools/ahat/src/heapdump/AhatPlaceHolderInstance.java
@@ -16,6 +16,9 @@
 
 package com.android.ahat.heapdump;
 
+import java.util.Collections;
+import java.util.List;
+
 /**
  * Generic PlaceHolder instance to take the place of a real AhatInstance for
  * the purposes of displaying diffs.
@@ -60,4 +63,10 @@ public class AhatPlaceHolderInstance extends AhatInstance {
   @Override public boolean isPlaceHolder() {
     return true;
   }
+
+  @Override
+  ReferenceIterator getReferences() {
+    List<Reference> refs = Collections.emptyList();
+    return new ReferenceIterator(refs);
+  }
 }
diff --git a/tools/ahat/src/heapdump/AhatSnapshot.java b/tools/ahat/src/heapdump/AhatSnapshot.java
index 35d6c8a315..7df78c50b5 100644
--- a/tools/ahat/src/heapdump/AhatSnapshot.java
+++ b/tools/ahat/src/heapdump/AhatSnapshot.java
@@ -16,6 +16,7 @@
 
 package com.android.ahat.heapdump;
 
+import com.android.ahat.dominators.DominatorsComputation;
 import com.android.tools.perflib.captures.DataBuffer;
 import com.android.tools.perflib.captures.MemoryMappedFileBuffer;
 import com.android.tools.perflib.heap.ArrayInstance;
@@ -42,7 +43,7 @@ public class AhatSnapshot implements Diffable<AhatSnapshot> {
   private final Site mRootSite = new Site("ROOT");
 
   // Collection of objects whose immediate dominator is the SENTINEL_ROOT.
-  private final List<AhatInstance> mRooted = new ArrayList<AhatInstance>();
+  private final List<AhatInstance> mRooted;
 
   // List of all ahat instances stored in increasing order by id.
   private final List<AhatInstance> mInstances = new ArrayList<AhatInstance>();
@@ -80,7 +81,6 @@ public class AhatSnapshot implements Diffable<AhatSnapshot> {
    */
   private AhatSnapshot(DataBuffer buffer, ProguardMap map) throws IOException {
     Snapshot snapshot = Snapshot.createSnapshot(buffer, map);
-    snapshot.computeDominators();
 
     // Properly label the class of class objects in the perflib snapshot.
     final ClassObj javaLangClass = snapshot.findClass("java.lang.Class");
@@ -139,46 +139,45 @@ public class AhatSnapshot implements Diffable<AhatSnapshot> {
     // and instances.
     for (AhatInstance ahat : mInstances) {
       Instance inst = snapshot.findInstance(ahat.getId());
-      ahat.initialize(this, inst);
 
-      Long registeredNativeSize = registeredNative.get(inst);
-      if (registeredNativeSize != null) {
-        ahat.addRegisteredNativeSize(registeredNativeSize);
-      }
-
-      if (inst.getImmediateDominator() == Snapshot.SENTINEL_ROOT) {
-        mRooted.add(ahat);
-      }
-
-      if (inst.isReachable()) {
-        ahat.getHeap().addToSize(ahat.getSize());
-      }
-
-      // Update sites.
       StackFrame[] frames = null;
       StackTrace stack = inst.getStack();
       if (stack != null) {
         frames = stack.getFrames();
       }
       Site site = mRootSite.add(frames, frames == null ? 0 : frames.length, ahat);
-      ahat.setSite(site);
+      ahat.initialize(this, inst, site);
+
+      Long registeredNativeSize = registeredNative.get(inst);
+      if (registeredNativeSize != null) {
+        ahat.addRegisteredNativeSize(registeredNativeSize);
+      }
     }
 
     // Record the roots and their types.
+    SuperRoot superRoot = new SuperRoot();
     for (RootObj root : snapshot.getGCRoots()) {
       Instance inst = root.getReferredInstance();
       if (inst != null) {
-        findInstance(inst.getId()).addRootType(root.getRootType().toString());
+        AhatInstance ahat = findInstance(inst.getId());
+        if (!ahat.isRoot()) {
+          superRoot.addRoot(ahat);
+        }
+        ahat.addRootType(root.getRootType().toString());
       }
     }
     snapshot.dispose();
 
-    // Compute the retained sizes of objects. We do this explicitly now rather
-    // than relying on the retained sizes computed by perflib so that
-    // registered native sizes are included.
-    for (AhatInstance inst : mRooted) {
-      AhatInstance.computeRetainedSize(inst, mHeaps.size());
+    AhatInstance.computeReverseReferences(superRoot);
+    DominatorsComputation.computeDominators(superRoot);
+    AhatInstance.computeRetainedSize(superRoot, mHeaps.size());
+
+    mRooted = superRoot.getDominated();
+    for (AhatHeap heap : mHeaps) {
+      heap.addToSize(superRoot.getRetainedSize(heap));
     }
+
+    mRootSite.computeObjectsInfos(mHeaps.size());
   }
 
   /**
diff --git a/tools/ahat/src/heapdump/DominatorReferenceIterator.java b/tools/ahat/src/heapdump/DominatorReferenceIterator.java
new file mode 100644
index 0000000000..ce2e6efa6e
--- /dev/null
+++ b/tools/ahat/src/heapdump/DominatorReferenceIterator.java
@@ -0,0 +1,61 @@
+/*
+ * 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.heapdump;
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+/**
+ * Reference iterator used for the dominators computation.
+ * This visits only strong references.
+ */
+class DominatorReferenceIterator implements Iterator<AhatInstance>,
+                                            Iterable<AhatInstance> {
+  private ReferenceIterator mIter;
+  private AhatInstance mNext;
+
+  public DominatorReferenceIterator(ReferenceIterator iter) {
+    mIter = iter;
+    mNext = null;
+  }
+
+  @Override
+  public boolean hasNext() {
+    while (mNext == null && mIter.hasNext()) {
+      Reference ref = mIter.next();
+      if (ref.strong) {
+        mNext = ref.ref;
+      }
+    }
+    return mNext != null;
+  }
+
+  @Override
+  public AhatInstance next() {
+    if (hasNext()) {
+      AhatInstance next = mNext;
+      mNext = null;
+      return next;
+    }
+    throw new NoSuchElementException();
+  }
+
+  @Override
+  public Iterator<AhatInstance> iterator() {
+    return this;
+  }
+}
diff --git a/tools/ahat/src/heapdump/Reference.java b/tools/ahat/src/heapdump/Reference.java
new file mode 100644
index 0000000000..980f2780b6
--- /dev/null
+++ b/tools/ahat/src/heapdump/Reference.java
@@ -0,0 +1,38 @@
+/*
+ * 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.heapdump;
+
+/**
+ * Reference represents a reference from 'src' to 'ref' through 'field'.
+ * Field is a string description for human consumption. This is typically
+ * either "." followed by the field name or an array subscript such as "[4]".
+ * 'strong' is true if this is a strong reference, false if it is a
+ * weak/soft/other reference.
+ */
+public class Reference {
+  public final AhatInstance src;
+  public final String field;
+  public final AhatInstance ref;
+  public final boolean strong;
+
+  public Reference(AhatInstance src, String field, AhatInstance ref, boolean strong) {
+    this.src = src;
+    this.field = field;
+    this.ref = ref;
+    this.strong = strong;
+  }
+}
diff --git a/tools/ahat/src/heapdump/ReferenceIterator.java b/tools/ahat/src/heapdump/ReferenceIterator.java
new file mode 100644
index 0000000000..a707fb24ef
--- /dev/null
+++ b/tools/ahat/src/heapdump/ReferenceIterator.java
@@ -0,0 +1,65 @@
+/*
+ * 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.heapdump;
+
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+
+class ReferenceIterator implements Iterator<Reference>,
+                                   Iterable<Reference> {
+  private List<Reference> mRefs;
+  private int mLength;
+  private int mNextIndex;
+  private Reference mNext;
+
+  /**
+   * Construct a ReferenceIterator that iterators over the given list of
+   * references. Elements of the given list of references may be null, in
+   * which case the ReferenceIterator will skip over them.
+   */
+  public ReferenceIterator(List<Reference> refs) {
+    mRefs = refs;
+    mLength = refs.size();
+    mNextIndex = 0;
+    mNext = null;
+  }
+
+  @Override
+  public boolean hasNext() {
+    while (mNext == null && mNextIndex < mLength) {
+      mNext = mRefs.get(mNextIndex);
+      mNextIndex++;
+    }
+    return mNext != null;
+  }
+
+  @Override
+  public Reference next() {
+    if (!hasNext()) {
+      throw new NoSuchElementException();
+    }
+    Reference next = mNext;
+    mNext = null;
+    return next;
+  }
+
+  @Override
+  public Iterator<Reference> iterator() {
+    return this;
+  }
+}
diff --git a/tools/ahat/src/heapdump/Site.java b/tools/ahat/src/heapdump/Site.java
index fdd4eea7b3..f0fc5d2d6c 100644
--- a/tools/ahat/src/heapdump/Site.java
+++ b/tools/ahat/src/heapdump/Site.java
@@ -42,15 +42,15 @@ public class Site implements Diffable<Site> {
   private int mDepth;
 
   // The total size of objects allocated in this site (including child sites),
-  // organized by heap index. Heap indices outside the range of mSizesByHeap
-  // implicitly have size 0.
+  // organized by heap index. Computed as part of computeObjectsInfos.
   private Size[] mSizesByHeap;
 
   // List of child sites.
   private List<Site> mChildren;
 
-  // List of all objects allocated in this site (including child sites).
+  // List of objects allocated at this site (not including child sites).
   private List<AhatInstance> mObjects;
+
   private List<ObjectsInfo> mObjectsInfos;
   private Map<AhatHeap, Map<AhatClassObj, ObjectsInfo>> mObjectsInfoMap;
 
@@ -111,7 +111,6 @@ public class Site implements Diffable<Site> {
     mLineNumber = line;
     mId = id;
     mDepth = depth;
-    mSizesByHeap = new Size[0];
     mChildren = new ArrayList<Site>();
     mObjects = new ArrayList<AhatInstance>();
     mObjectsInfos = new ArrayList<ObjectsInfo>();
@@ -130,67 +129,102 @@ public class Site implements Diffable<Site> {
   }
 
   private static Site add(Site site, StackFrame[] frames, int depth, AhatInstance inst) {
-    while (true) {
-      site.mObjects.add(inst);
+    while (depth > 0) {
+      StackFrame next = frames[depth - 1];
+      Site child = null;
+      for (int i = 0; i < site.mChildren.size(); i++) {
+        Site curr = site.mChildren.get(i);
+        if (curr.mLineNumber == next.getLineNumber()
+            && curr.mMethodName.equals(next.getMethodName())
+            && curr.mSignature.equals(next.getSignature())
+            && curr.mFilename.equals(next.getFilename())) {
+          child = curr;
+          break;
+        }
+      }
+      if (child == null) {
+        child = new Site(site, next.getMethodName(), next.getSignature(),
+            next.getFilename(), next.getLineNumber(), inst.getId(), depth - 1);
+        site.mChildren.add(child);
+      }
+      depth = depth - 1;
+      site = child;
+    }
+    site.mObjects.add(inst);
+    return site;
+  }
+
+  /**
+   * Recompute the ObjectsInfos for this and all child sites.
+   * This should be done after the sites tree has been formed. It should also
+   * be done after dominators computation has been performed to ensure only
+   * reachable objects are included in the ObjectsInfos.
+   *
+   * @param numHeaps - The number of heaps in the heap dump.
+   */
+  void computeObjectsInfos(int numHeaps) {
+    // Count up the total sizes by heap.
+    mSizesByHeap = new Size[numHeaps];
+    for (int i = 0; i < numHeaps; ++i) {
+      mSizesByHeap[i] = Size.ZERO;
+    }
 
-      ObjectsInfo info = site.getObjectsInfo(inst.getHeap(), inst.getClassObj());
+    // Add all reachable objects allocated at this site.
+    for (AhatInstance inst : mObjects) {
       if (inst.isReachable()) {
         AhatHeap heap = inst.getHeap();
-        if (heap.getIndex() >= site.mSizesByHeap.length) {
-          Size[] newSizes = new Size[heap.getIndex() + 1];
-          for (int i = 0; i < site.mSizesByHeap.length; i++) {
-            newSizes[i] = site.mSizesByHeap[i];
-          }
-          for (int i = site.mSizesByHeap.length; i < heap.getIndex() + 1; i++) {
-            newSizes[i] = Size.ZERO;
-          }
-          site.mSizesByHeap = newSizes;
-        }
-        site.mSizesByHeap[heap.getIndex()]
-          = site.mSizesByHeap[heap.getIndex()].plus(inst.getSize());
-
+        Size size = inst.getSize();
+        ObjectsInfo info = getObjectsInfo(heap, inst.getClassObj());
         info.numInstances++;
-        info.numBytes = info.numBytes.plus(inst.getSize());
+        info.numBytes = info.numBytes.plus(size);
+        mSizesByHeap[heap.getIndex()] = mSizesByHeap[heap.getIndex()].plus(size);
       }
+    }
 
-      if (depth > 0) {
-        StackFrame next = frames[depth - 1];
-        Site child = null;
-        for (int i = 0; i < site.mChildren.size(); i++) {
-          Site curr = site.mChildren.get(i);
-          if (curr.mLineNumber == next.getLineNumber()
-              && curr.mMethodName.equals(next.getMethodName())
-              && curr.mSignature.equals(next.getSignature())
-              && curr.mFilename.equals(next.getFilename())) {
-            child = curr;
-            break;
-          }
-        }
-        if (child == null) {
-          child = new Site(site, next.getMethodName(), next.getSignature(),
-              next.getFilename(), next.getLineNumber(), inst.getId(), depth - 1);
-          site.mChildren.add(child);
-        }
-        depth = depth - 1;
-        site = child;
-      } else {
-        return site;
+    // Add objects allocated in child sites.
+    for (Site child : mChildren) {
+      child.computeObjectsInfos(numHeaps);
+      for (ObjectsInfo childInfo : child.mObjectsInfos) {
+        ObjectsInfo info = getObjectsInfo(childInfo.heap, childInfo.classObj);
+        info.numInstances += childInfo.numInstances;
+        info.numBytes = info.numBytes.plus(childInfo.numBytes);
+      }
+      for (int i = 0; i < numHeaps; ++i) {
+        mSizesByHeap[i] = mSizesByHeap[i].plus(child.mSizesByHeap[i]);
       }
     }
   }
 
   // Get the size of a site for a specific heap.
   public Size getSize(AhatHeap heap) {
-    int index = heap.getIndex();
-    return index >= 0 && index < mSizesByHeap.length ? mSizesByHeap[index] : Size.ZERO;
+    return mSizesByHeap[heap.getIndex()];
   }
 
   /**
-   * Get the list of objects allocated under this site. Includes objects
-   * allocated in children sites.
+   * Collect the objects allocated under this site, optionally filtered by
+   * heap name or class name. Includes objects allocated in children sites.
+   * @param heapName - The name of the heap the collected objects should
+   *                   belong to. This may be null to indicate objects of
+   *                   every heap should be collected.
+   * @param className - The name of the class the collected objects should
+   *                    belong to. This may be null to indicate objects of
+   *                    every class should be collected.
+   * @param objects - Out parameter. A collection of objects that all
+   *                  collected objects should be added to.
    */
-  public Collection<AhatInstance> getObjects() {
-    return mObjects;
+  public void getObjects(String heapName, String className, Collection<AhatInstance> objects) {
+    for (AhatInstance inst : mObjects) {
+      if ((heapName == null || inst.getHeap().getName().equals(heapName))
+          && (className == null || inst.getClassName().equals(className))) {
+        objects.add(inst);
+      }
+    }
+
+    // Recursively visit children. Recursion should be okay here because the
+    // stack depth is limited by a reasonable amount (128 frames or so).
+    for (Site child : mChildren) {
+      child.getObjects(heapName, className, objects);
+    }
   }
 
   /**
@@ -220,8 +254,8 @@ public class Site implements Diffable<Site> {
   // Get the combined size of the site for all heaps.
   public Size getTotalSize() {
     Size total = Size.ZERO;
-    for (int i = 0; i < mSizesByHeap.length; i++) {
-      total = total.plus(mSizesByHeap[i]);
+    for (Size size : mSizesByHeap) {
+      total = total.plus(size);
     }
     return total;
   }
diff --git a/tools/ahat/src/heapdump/SuperRoot.java b/tools/ahat/src/heapdump/SuperRoot.java
new file mode 100644
index 0000000000..54410cf1a6
--- /dev/null
+++ b/tools/ahat/src/heapdump/SuperRoot.java
@@ -0,0 +1,57 @@
+/*
+ * 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.heapdump;
+
+import com.android.ahat.dominators.DominatorsComputation;
+import java.util.AbstractList;
+import java.util.ArrayList;
+import java.util.List;
+
+public class SuperRoot extends AhatInstance implements DominatorsComputation.Node {
+  private List<AhatInstance> mRoots = new ArrayList<AhatInstance>();
+  private Object mDominatorsComputationState;
+
+  public SuperRoot() {
+    super(0);
+  }
+
+  public void addRoot(AhatInstance root) {
+    mRoots.add(root);
+  }
+
+  @Override
+  public String toString() {
+    return "SUPER_ROOT";
+  }
+
+  @Override
+  ReferenceIterator getReferences() {
+    List<Reference> refs = new AbstractList<Reference>() {
+      @Override
+      public int size() {
+        return mRoots.size();
+      }
+
+      @Override
+      public Reference get(int index) {
+        String field = ".roots[" + Integer.toString(index) + "]";
+        return new Reference(null, field, mRoots.get(index), true);
+      }
+    };
+    return new ReferenceIterator(refs);
+  }
+}
diff --git a/tools/ahat/test-dump/Main.java b/tools/ahat/test-dump/Main.java
index 3d3de78255..13fd102d7d 100644
--- a/tools/ahat/test-dump/Main.java
+++ b/tools/ahat/test-dump/Main.java
@@ -60,6 +60,14 @@ public class Main {
     public StackSmasher child;
   }
 
+  public static class Reference {
+    public Object referent;
+
+    public Reference(Object referent) {
+      this.referent = referent;
+    }
+  }
+
   // We will take a heap dump that includes a single instance of this
   // DumpedStuff class. Objects stored as fields in this class can be easily
   // found in the hprof dump by searching for the instance of the DumpedStuff
@@ -71,6 +79,7 @@ public class Main {
     public char[] charArray = "char thing".toCharArray();
     public String nullString = null;
     public Object anObject = new Object();
+    public Reference aReference = new Reference(anObject);
     public ReferenceQueue<Object> referenceQueue = new ReferenceQueue<Object>();
     public PhantomReference aPhantomReference = new PhantomReference(anObject, referenceQueue);
     public WeakReference aWeakReference = new WeakReference(anObject, referenceQueue);
diff --git a/tools/ahat/test/DominatorsTest.java b/tools/ahat/test/DominatorsTest.java
new file mode 100644
index 0000000000..0424e10dc8
--- /dev/null
+++ b/tools/ahat/test/DominatorsTest.java
@@ -0,0 +1,298 @@
+/*
+ * 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;
+
+import com.android.ahat.dominators.DominatorsComputation;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.List;
+import org.junit.Test;
+import static org.junit.Assert.assertEquals;
+
+public class DominatorsTest {
+  private static class Node implements DominatorsComputation.Node {
+    public String name;
+    public List<Node> depends = new ArrayList<Node>();
+    public Node dominator;
+    private Object dominatorsComputationState;
+
+    public Node(String name) {
+      this.name = name;
+    }
+
+    public void computeDominators() {
+      DominatorsComputation.computeDominators(this);
+    }
+
+    public String toString() {
+      return name;
+    }
+
+    @Override
+    public void setDominatorsComputationState(Object state) {
+      dominatorsComputationState = state;
+    }
+
+    @Override
+    public Object getDominatorsComputationState() {
+      return dominatorsComputationState;
+    }
+
+    @Override
+    public Collection<Node> getReferencesForDominators() {
+      return depends;
+    }
+
+    @Override
+    public void setDominator(DominatorsComputation.Node dominator) {
+      this.dominator = (Node)dominator;
+    }
+  }
+
+  @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);
+  }
+}
diff --git a/tools/ahat/test/InstanceTest.java b/tools/ahat/test/InstanceTest.java
index 71b081c9a4..f0e7f445ce 100644
--- a/tools/ahat/test/InstanceTest.java
+++ b/tools/ahat/test/InstanceTest.java
@@ -337,7 +337,7 @@ public class InstanceTest {
   public void classObjToString() throws IOException {
     TestDump dump = TestDump.getTestDump();
     AhatInstance obj = dump.getAhatSnapshot().findClass("Main");
-    assertEquals("Main", obj.toString());
+    assertEquals("class Main", obj.toString());
   }
 
   @Test
@@ -370,6 +370,18 @@ public class InstanceTest {
   }
 
   @Test
+  public void reverseReferences() throws IOException {
+    TestDump dump = TestDump.getTestDump();
+    AhatInstance obj = dump.getDumpedAhatInstance("anObject");
+    AhatInstance ref = dump.getDumpedAhatInstance("aReference");
+    AhatInstance weak = dump.getDumpedAhatInstance("aWeakReference");
+    assertTrue(obj.getHardReverseReferences().contains(ref));
+    assertFalse(obj.getHardReverseReferences().contains(weak));
+    assertFalse(obj.getSoftReverseReferences().contains(ref));
+    assertTrue(obj.getSoftReverseReferences().contains(weak));
+  }
+
+  @Test
   public void asStringEmbedded() throws IOException {
     // Set up a heap dump with an instance of java.lang.String of
     // "hello" with instance id 0x42 that is backed by a char array that is
diff --git a/tools/ahat/test/Tests.java b/tools/ahat/test/Tests.java
index a95788e3bd..a1e3246cd1 100644
--- a/tools/ahat/test/Tests.java
+++ b/tools/ahat/test/Tests.java
@@ -24,6 +24,7 @@ public class Tests {
       args = new String[]{
         "com.android.ahat.DiffFieldsTest",
         "com.android.ahat.DiffTest",
+        "com.android.ahat.DominatorsTest",
         "com.android.ahat.InstanceTest",
         "com.android.ahat.NativeAllocationTest",
         "com.android.ahat.ObjectHandlerTest",