Observatory: Add view of dominator tree with siblings merged by class.

runtime/observatory/lib/object_graph.dart

 // Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 library object_graph;
 
 import 'dart:async';
 import 'dart:collection';
 import 'dart:typed_data';
 
@@ skipping 196 matching lines @@
 
   void skipUnsigned() {
     while (_getUint8(position++) <= maxUnsignedDataPerByte);
   }
 
   static const int dataBitsPerByte = 7;
   static const int byteMask = (1 << dataBitsPerByte) - 1;
   static const int maxUnsignedDataPerByte = byteMask;
 }
 
+// Node indices for the root and sentinel nodes. Note that using 0 as the
+// sentinel means a newly allocated typed array comes initialized with all
+// elements as the sentinel.
+const ROOT = 1;
+const SENTINEL = 0;
+
 class ObjectVertex {
-  // 0 represents invalid/uninitialized, 1 is the root.
   final int _id;
   final ObjectGraph _graph;
 
   ObjectVertex._(this._id, this._graph);
 
-  bool get isRoot => _id == 1;
+  bool get isRoot => ROOT == _id;
 
   bool operator ==(other) => _id == other._id && _graph == other._graph;
   int get hashCode => _id;
 
   int get retainedSize => _graph._retainedSizes[_id];
   ObjectVertex get dominator => new ObjectVertex._(_graph._doms[_id], _graph);
 
   int get shallowSize => _graph._shallowSizes[_id];
   int get vmCid => _graph._cids[_id];
 
@@ skipping 30 matching lines @@
     return strAddr;
   }
 
   List<ObjectVertex> dominatorTreeChildren() {
     var N = _graph._N;
     var doms = _graph._doms;
 
     var parentId = _id;
     var domChildren = [];
 
-    for (var childId = 1; childId <= N; childId++) {
+    for (var childId = ROOT; childId <= N; childId++) {
       if (doms[childId] == parentId) {
         domChildren.add(new ObjectVertex._(childId, _graph));
       }
     }
 
     return domChildren;
   }
 }
 
+// A node in the dominator tree where siblings with the same class are merged.
+// That is, a set of objects with the same cid whose parent chains in the
+// dominator tree have the same cids at each level. [id_] is the representative
+// object of this set. The other members of the set are found by walking the
+// mergedDomNext links until finding the sentinel node or a node with a
+// different class.
+class MergedObjectVertex {
+  final int _id;
+  final ObjectGraph _graph;
+
+  MergedObjectVertex._(this._id, this._graph);
+
+  bool get isRoot => ROOT == _id;
+
+  bool operator ==(other) => _id == other._id && _graph == other._graph;
+  int get hashCode => _id;
+
+  int get vmCid => _graph._cids[_id];
+
+  int get shallowSize {
+    var cids = _graph._cids;
+    var size = 0;
+    var sibling = _id;
+    while (sibling != SENTINEL &&
+           cids[sibling] == cids[_id]) {
+      size += _graph._shallowSizes[sibling];
+      sibling = _graph._mergedDomNext[sibling];
+    }
+    return size;
+  }
+  int get retainedSize {
+    var cids = _graph._cids;
+    var size = 0;
+    var sibling = _id;
+    while (sibling != SENTINEL &&
+           cids[sibling] == cids[_id]) {
+      size += _graph._retainedSizes[sibling];
+      sibling = _graph._mergedDomNext[sibling];
+    }
+    return size;
+  }
+  int get instanceCount {
+    var cids = _graph._cids;
+    var count = 0;
+    var sibling = _id;
+    while (sibling != SENTINEL &&
+           cids[sibling] == cids[_id]) {
+      count++;
+      sibling = _graph._mergedDomNext[sibling];
+    }
+    return count;
+  }
+
+  List<MergedObjectVertex> dominatorTreeChildren() {
+    var next = _graph._mergedDomNext;
+    var cids = _graph._cids;
+
+    var domChildren = [];
+    var prev = SENTINEL;
+    var child = _graph._mergedDomHead[_id];
+    // Walk the list of children and look for the representative objects, i.e.
+    // the first sibling of each cid.
+    while (child != SENTINEL) {
+      if (prev == SENTINEL ||
+          cids[prev] != cids[child]) {
+        domChildren.add(new MergedObjectVertex._(child, _graph));
+      }
+      prev = child;
+      child = next[child];
+    }
+
+    return domChildren;
+  }
+}
+
 class _SuccessorsIterable extends IterableBase<ObjectVertex> {
   final ObjectGraph _graph;
   final int _id;
 
   _SuccessorsIterable(this._graph, this._id);
 
   Iterator<ObjectVertex> get iterator => new _SuccessorsIterator(_graph, _id);
 }
 
 class _SuccessorsIterator implements Iterator<ObjectVertex> {
@@ skipping 43 matching lines @@
 
 class ObjectGraph {
   ObjectGraph(List<ByteData> chunks, int nodeCount)
       : this._chunks = chunks,
         this._N = nodeCount;
 
   int get size => _size;
   int get vertexCount => _N;
   int get edgeCount => _E;
 
-  ObjectVertex get root => new ObjectVertex._(1, this);
+  ObjectVertex get root => new ObjectVertex._(ROOT, this);
+  MergedObjectVertex get mergedRoot => new MergedObjectVertex._(ROOT, this);
   Iterable<ObjectVertex> get vertices => new _VerticesIterable(this);
 
   Iterable<ObjectVertex> getMostRetained({int classId, int limit}) {
     List<ObjectVertex> _mostRetained =
         new List<ObjectVertex>.from(vertices.where((u) => !u.isRoot));
     _mostRetained.sort((u, v) => v.retainedSize - u.retainedSize);
 
     var result = _mostRetained;
     if (classId != null) {
       result = result.where((u) => u.vmCid == classId);
@@ skipping 15 matching lines @@
 
       controller.add(["Remapping $_E references...", 15.0]);
       await new Future(() => _remapEdges());
 
       _addrToId = null;
       _chunks = null;
 
       controller.add(["Finding depth-first order...", 30.0]);
       await new Future(() => _dfs());
 
-      controller.add(["Finding predecessors...", 45.0]);
+      controller.add(["Finding predecessors...", 40.0]);
       await new Future(() => _buildPredecessors());
 
-      controller.add(["Finding dominators...", 60.0]);
+      controller.add(["Finding dominators...", 50.0]);
       await new Future(() => _buildDominators());
 
       _firstPreds = null;
       _preds = null;
 
       _semi = null;
       _parent = null;
 
-      controller.add(["Finding retained sizes...", 75.0]);
+      controller.add(["Finding retained sizes...", 60.0]);
       await new Future(() => _calculateRetainedSizes());
 
       _vertex = null;
 
-      controller.add(["Loaded", 100.0]);
+      controller.add(["Linking dominator tree children...", 70.0]);
+      await new Future(() => _linkDominatorChildren());
+
+      controller.add(["Sorting dominator tree children...", 80.0]);
+      await new Future(() => _sortDominatorChildren());
+
+      controller.add(["Merging dominator tree siblings...", 90.0]);
+      await new Future(() => _mergeDominatorSiblings());
+
+      controller.add(["Processed", 100.0]);
       controller.close();
     }());
     return controller.stream;
   }
 
   List<ByteData> _chunks;
 
   int _kObjectAlignment;
   int _N;
   int _E;
@@ skipping 12 matching lines @@
   AddressMapper _addrToId;
   Uint32List _vertex;
   Uint32List _parent;
   Uint32List _semi;
   Uint32List _firstPreds; // Offset into preds.
   Uint32List _preds;
 
   // Outputs.
   Uint32List _doms;
   Uint32List _retainedSizes;
+  Uint32List _mergedDomHead;
+  Uint32List _mergedDomNext;
 
   void _remapNodes() {
     var N = _N;
     var E = 0;
     var addrToId = new AddressMapper(N);
 
     var addressesHigh = new Uint32List(N + 1);
     var addressesLow = new Uint32List(N + 1);
     var shallowSizes = new Uint32List(N + 1);
     var cids = new Uint16List(N + 1);
 
     var stream = new ReadStream(_chunks);
     stream.readUnsigned();
     _kObjectAlignment = stream.clampedUint32;
 
-    var id = 1;
+    var id = ROOT;
     while (stream.pendingBytes > 0) {
       stream.readUnsigned(); // addr
       addrToId.put(stream.high, stream.mid, stream.low, id);
       addressesHigh[id] = stream.highUint32;
       addressesLow[id] = stream.lowUint32;
       stream.readUnsigned(); // shallowSize
       shallowSizes[id] = stream.clampedUint32;
       stream.readUnsigned(); // cid
       cids[id] = stream.clampedUint32;
 
       stream.readUnsigned();
       while (!stream.isZero) {
         E++;
         stream.readUnsigned();
       }
       id++;
     }
     assert(id == (N + 1));
 
-    var root = addrToId.get(0, 0, 0);
-    assert(root == 1);
+    assert(ROOT == addrToId.get(0, 0, 0));
 
     _E = E;
     _addrToId = addrToId;
     _addressesLow = addressesLow;
     _addressesHigh = addressesHigh;
     _shallowSizes = shallowSizes;
     _cids = cids;
   }
 
   void _remapEdges() {
@@ skipping 46 matching lines @@
 
     var stackNodes = new Uint32List(N);
     var stackCurrentEdgePos = new Uint32List(N);
 
     var vertex = new Uint32List(N + 1);
     var semi = new Uint32List(N + 1);
     var parent = new Uint32List(N + 1);
     var dfsNumber = 0;
 
     var stackTop = 0;
-    var root = 1;
 
     // Push root.
-    stackNodes[0] = root;
-    stackCurrentEdgePos[0] = firstSuccs[root];
+    stackNodes[0] = ROOT;
+    stackCurrentEdgePos[0] = firstSuccs[ROOT];
 
     while (stackTop >= 0) {
       var v = stackNodes[stackTop];
       var edgePos = stackCurrentEdgePos[stackTop];
 
       if (semi[v] == 0) {
         // First visit.
         dfsNumber++;
         semi[v] = dfsNumber;
         vertex[dfsNumber] = v;
@@ skipping 12 matching lines @@
           stackNodes[stackTop] = childId;
           stackCurrentEdgePos[stackTop] = firstSuccs[childId];
         }
       } else {
         // Done with all children.
         stackTop--;
       }
     }
 
     assert(dfsNumber == N);
-    for (var i = 1; i <= N; i++) {
-      assert(semi[i] != 0);
+    for (var i = ROOT; i <= N; i++) {
+      assert(semi[i] != SENTINEL);
     }
-    assert(parent[1] == 0);
-    for (var i = 2; i <= N; i++) {
-      assert(parent[i] != 0);
+    assert(parent[ROOT] == SENTINEL);
+    for (var i = ROOT + 1; i <= N; i++) {
+      assert(parent[i] != SENTINEL);
     }
 
     _vertex = vertex;
     _semi = semi;
     _parent = parent;
   }
 
   void _buildPredecessors() {
     var N = _N;
     var E = _E;
@@ skipping 39 matching lines @@
         preds[predIndex] = i;
       }
     }
 
     _firstPreds = firstPreds;
     _preds = preds;
   }
 
   static int _eval(int v, Uint32List ancestor, Uint32List semi,
       Uint32List label, Uint32List stackNode, Uint8List stackState) {
-    if (ancestor[v] == 0) {
+    if (ancestor[v] == SENTINEL) {
       return label[v];
     } else {
       {
         // Inlined 'compress' with an explicit stack to prevent JS stack
         // overflow.
         var top = 0;
         stackNode[top] = v;
         stackState[top] = 0;
         while (top >= 0) {
           var v = stackNode[top];
@@ skipping 62 matching lines @@
   // in a Flowgraph."
   void _buildDominators() {
     var N = _N;
 
     var vertex = _vertex;
     var semi = _semi;
     var parent = _parent;
     var firstPreds = _firstPreds;
     var preds = _preds;
 
-    var root = 1;
     var dom = new Uint32List(N + 1);
 
     var ancestor = new Uint32List(N + 1);
     var label = new Uint32List(N + 1);
     for (var i = 1; i <= N; i++) {
       label[i] = i;
     }
     var buckets = new List(N + 1);
     var child = new Uint32List(N + 1);
     var size = new Uint32List(N + 1);
     for (var i = 1; i <= N; i++) {
       size[i] = 1;
     }
     var stackNode = new Uint32List(N + 1);
     var stackState = new Uint8List(N + 1);
 
     for (var i = N; i > 1; i--) {
       var w = vertex[i];
-      assert(w != root);
+      assert(w != ROOT);
 
       // Lengauer & Tarjan Step 2.
       var startPred = firstPreds[w];
       var limitPred = firstPreds[w + 1];
       for (var predIndex = startPred; predIndex < limitPred; predIndex++) {
         var v = preds[predIndex];
         var u = _eval(v, ancestor, semi, label, stackNode, stackState);
         if (semi[u] < semi[w]) {
           semi[w] = semi[u];
         }
@@ skipping 12 matching lines @@
       tmp = parent[w];
       var bucket = buckets[tmp];
       buckets[tmp] = null;
       if (bucket != null) {
         for (var v in bucket) {
           var u = _eval(v, ancestor, semi, label, stackNode, stackState);
           dom[v] = semi[u] < semi[v] ? u : parent[w];
         }
       }
     }
-    for (var i = 1; i <= N; i++) {
+    for (var i = ROOT; i <= N; i++) {
       assert(buckets[i] == null);
     }
     // Lengauer & Tarjan Step 4.
     for (var i = 2; i <= N; i++) {
       var w = vertex[i];
       if (dom[w] != vertex[semi[w]]) {
         dom[w] = dom[dom[w]];
       }
     }
 
     _doms = dom;
   }
 
   void _calculateRetainedSizes() {
     var N = _N;
 
     var size = 0;
     var shallowSizes = _shallowSizes;
     var vertex = _vertex;
     var doms = _doms;
 
     // Sum shallow sizes.
-    for (var i = 1; i < N; i++) {
+    for (var i = ROOT; i < N; i++) {
       size += shallowSizes[i];
     }
 
     // Start with retained size as shallow size.
     var retainedSizes = new Uint32List.fromList(shallowSizes);
 
     // In post order (bottom up), add retained size to dominator's retained
     // size, skipping root.
     for (var i = N; i > 1; i--) {
       var v = vertex[i];
-      assert(v != 1);
+      assert(v != ROOT);
       retainedSizes[doms[i]] += retainedSizes[i];
     }
 
     _retainedSizes = retainedSizes;
     _size = size;
   }
+
+  // Build linked lists of the children for each node in the dominator tree.
+  void _linkDominatorChildren() {
+    var N = _N;
+    var doms = _doms;
+    var head = new Uint32List(N + 1);
+    var next = new Uint32List(N + 1);
+
+    for (var child = ROOT; child <= N; child++) {
+      var parent = doms[child];
+      next[child] = head[parent];
+      head[parent] = child;
+    }
+
+    _mergedDomHead = head;
+    _mergedDomNext = next;
+  }
+
+  // Merge the given lists according to the given key in ascending order.
+  // Returns the head of the merged list.
+  static int _mergeSorted(int head1, int head2,
+                          Uint32List next, Uint16List key) {
+    var head = head1;
+    var beforeInsert = SENTINEL;
+    var afterInsert = head1;
+    var startInsert = head2;
+
+    while (startInsert != SENTINEL) {
+      while ((afterInsert != SENTINEL) &&
+             (key[afterInsert] <= key[startInsert])) {
+        beforeInsert = afterInsert;
+        afterInsert = next[beforeInsert];
+      }
+
+      var endInsert = startInsert;
+      var peek = next[endInsert];
+
+      while ((peek != SENTINEL) && (key[peek] < key[afterInsert])) {
+        endInsert = peek;
+        peek = next[endInsert];
+      }
+      assert(endInsert != SENTINEL);
+
+      if (beforeInsert == SENTINEL) {
+        head = startInsert;
+      } else {
+        next[beforeInsert] = startInsert;
+      }
+      next[endInsert] = afterInsert;
+
+      startInsert = peek;
+      beforeInsert = endInsert;
+    }
+
+    return head;
+  }
+
+  void _sortDominatorChildren() {
+    var N = _N;
+    var cids = _cids;
+    var head = _mergedDomHead;
+    var next = _mergedDomNext;
+
+    // Returns the new head of the sorted list.
+    int sort(int head) {
+      if (head == SENTINEL) return SENTINEL;
+      if (next[head] == SENTINEL) return head;
+
+      // Find the middle of the list.
+      int head1 = head;
+      int slow = head;
+      int fast = head;
+      while (next[fast] != SENTINEL &&
+             next[next[fast]] != SENTINEL) {
+        slow = next[slow];
+        fast = next[next[fast]];
+      }
+
+      // Split the list in half.
+      int head2 = next[slow];
+      next[slow] = SENTINEL;
+
+      // Recursively sort the sublists and merge.
+      assert(head1 != head2);
+      int newHead1 = sort(head1);
+      int newHead2 = sort(head2);
+      return _mergeSorted(newHead1, newHead2, next, cids);
+    }
+
+    // Sort all list of dominator tree children by cid.
+    for (var parent = ROOT; parent <= N; parent++) {
+      head[parent] = sort(head[parent]);
+    }
+  }
+
+  void _mergeDominatorSiblings() {
+    var N = _N;
+    var cids = _cids;
+    var head = _mergedDomHead;
+    var next = _mergedDomNext;
+    var workStack = new Uint32List(N);
+    var workStackTop = 0;
+
+    mergeChildrenAndSort(var parent1, var end) {
+      assert(parent1 != SENTINEL);
+      if (next[parent1] == end) return;
+
+      // Find the middle of the list.
+      int cid = cids[parent1];
+      int slow = parent1;
+      int fast = parent1;
+      while (next[fast] != end &&
+             next[next[fast]] != end) {
+        slow = next[slow];
+        fast = next[next[fast]];
+      }
+
+      int parent2 = next[slow];
+
+      assert(parent2 != SENTINEL);
+      assert(parent1 != parent2);
+      assert(cids[parent1] == cids[parent2]);
+
+      // Recursively sort the sublists.
+      mergeChildrenAndSort(parent1, parent2);
+      mergeChildrenAndSort(parent2, end);
+
+      // Merge sorted sublists.
+      head[parent1] = _mergeSorted(head[parent1], head[parent2], next, cids);
+
+      // Children moved to parent1.
+      head[parent2] = SENTINEL;
+    }
+
+    // Push root.
+    workStack[workStackTop++] = ROOT;
+
+    while (workStackTop > 0) {
+      var parent = workStack[--workStackTop];
+
+      var prev = SENTINEL;
+      var child = head[parent];
+      while (child != SENTINEL) {
+        // Push child.
+        workStack[workStackTop++] = child;
+
+        // Find next sibling with a different cid.
+        var after = child;
+        while (after != SENTINEL &&
+               cids[after] == cids[child]) {
+          after = next[after];
+        }
+
+        // From all the siblings between child and after, take their children,
+        // merge them and given to child.
+        mergeChildrenAndSort(child, after);
+
+        child = after;
+      }
+    }
+  }
 }