Eliminate dominator and retained_size fields. They are calculating on front-end side.

src/profile-generator.cc

Index: src/profile-generator.cc
diff --git a/src/profile-generator.cc b/src/profile-generator.cc
index da2a969e7123ea132e550cee99a0df60b7a0f208..fb571cfdd45c139f1505a42258b59e44d2c4d7d6 100644
--- a/src/profile-generator.cc
+++ b/src/profile-generator.cc
@@ -964,16 +964,10 @@ HeapEntry::HeapEntry(HeapSnapshot* snapshot,
                      const char* name,
                      SnapshotObjectId id,
                      int self_size)
-    : painted_(false),
-      user_reachable_(false),
-      dominator_(kNoEntry),
-      type_(type),
-      retainers_count_(0),
-      retainers_index_(-1),
+    : type_(type),
       children_count_(0),
       children_index_(-1),
       self_size_(self_size),
-      retained_size_(0),
       id_(id),
       snapshot_(snapshot),
       name_(name) { }
@@ -985,7 +979,6 @@ void HeapEntry::SetNamedReference(HeapGraphEdge::Type type,
   HeapGraphEdge edge(type, name, this->index(), entry->index());
   snapshot_->edges().Add(edge);
   ++children_count_;
-  ++entry->retainers_count_;
 }
 
 
@@ -995,7 +988,6 @@ void HeapEntry::SetIndexedReference(HeapGraphEdge::Type type,
   HeapGraphEdge edge(type, index, this->index(), entry->index());
   snapshot_->edges().Add(edge);
   ++children_count_;
-  ++entry->retainers_count_;
 }
 
 
@@ -1007,9 +999,8 @@ Handle<HeapObject> HeapEntry::GetHeapObject() {
 void HeapEntry::Print(
     const char* prefix, const char* edge_name, int max_depth, int indent) {
   STATIC_CHECK(sizeof(unsigned) == sizeof(id()));
-  OS::Print("%6d %7d @%6u %*c %s%s: ",
-            self_size(), retained_size(), id(),
-            indent, ' ', prefix, edge_name);
+  OS::Print("%6d @%6u %*c %s%s: ",
+            self_size(),  id(), indent, ' ', prefix, edge_name);

[alexeif, 2012/05/22 16:47:03]

nit: extra space

   if (type() != kString) {
     OS::Print("%s %.40s\n", TypeAsString(), name_);
   } else {
@@ -1091,13 +1082,13 @@ template <size_t ptr_size> struct SnapshotSizeConstants;
 
 template <> struct SnapshotSizeConstants<4> {
   static const int kExpectedHeapGraphEdgeSize = 12;
-  static const int kExpectedHeapEntrySize = 40;
+  static const int kExpectedHeapEntrySize = 28;
   static const size_t kMaxSerializableSnapshotRawSize = 256 * MB;
 };
 
 template <> struct SnapshotSizeConstants<8> {
   static const int kExpectedHeapGraphEdgeSize = 24;
-  static const int kExpectedHeapEntrySize = 48;
+  static const int kExpectedHeapEntrySize = 40;
   static const uint64_t kMaxSerializableSnapshotRawSize =
       static_cast<uint64_t>(6000) * MB;
 };
@@ -1139,16 +1130,6 @@ void HeapSnapshot::RememberLastJSObjectId() {
 }
 
 
-static void HeapEntryClearPaint(HeapEntry* entry_ptr) {
-  entry_ptr->clear_paint();
-}
-
-
-void HeapSnapshot::ClearPaint() {
-  entries_.Iterate(HeapEntryClearPaint);
-}
-
-
 HeapEntry* HeapSnapshot::AddRootEntry() {
   ASSERT(root_index_ == HeapEntry::kNoEntry);
   ASSERT(entries_.is_empty());  // Root entry must be the first one.
@@ -1196,32 +1177,19 @@ HeapEntry* HeapSnapshot::AddEntry(HeapEntry::Type type,
 }
 
 
-void HeapSnapshot::FillChildrenAndRetainers() {
+void HeapSnapshot::FillChildren() {
   ASSERT(children().is_empty());
   children().Allocate(edges().length());
-  ASSERT(retainers().is_empty());
-  retainers().Allocate(edges().length());
   int children_index = 0;
-  int retainers_index = 0;
   for (int i = 0; i < entries().length(); ++i) {
     HeapEntry* entry = &entries()[i];
     children_index = entry->set_children_index(children_index);
-    retainers_index = entry->set_retainers_index(retainers_index);
   }
   ASSERT(edges().length() == children_index);
-  ASSERT(edges().length() == retainers_index);
   for (int i = 0; i < edges().length(); ++i) {
     HeapGraphEdge* edge = &edges()[i];
     edge->ReplaceToIndexWithEntry(this);
     edge->from()->add_child(edge);
-    edge->to()->add_retainer(edge);
-  }
-}
-
-
-void HeapSnapshot::SetDominatorsToSelf() {
-  for (int i = 0; i < entries_.length(); ++i) {
-    entries_[i].set_dominator(&entries_[i]);
   }
 }
 
@@ -1284,7 +1252,6 @@ size_t HeapSnapshot::RawSnapshotSize() const {
       GetMemoryUsedByList(entries_) +
       GetMemoryUsedByList(edges_) +
       GetMemoryUsedByList(children_) +
-      GetMemoryUsedByList(retainers_) +
       GetMemoryUsedByList(sorted_entries_);
 }
 
@@ -3091,12 +3058,9 @@ bool HeapSnapshotGenerator::GenerateSnapshot() {
 
   if (!FillReferences()) return false;
 
-  snapshot_->FillChildrenAndRetainers();
+  snapshot_->FillChildren();
   snapshot_->RememberLastJSObjectId();
 
-  if (!SetEntriesDominators()) return false;
-  if (!CalculateRetainedSizes()) return false;
-
   progress_counter_ = progress_total_;
   if (!ProgressReport(true)) return false;
   return true;
@@ -3138,187 +3102,6 @@ bool HeapSnapshotGenerator::FillReferences() {
 }
 
 
-bool HeapSnapshotGenerator::IsUserGlobalReference(const HeapGraphEdge* edge) {
-  ASSERT(edge->from() == snapshot_->root());
-  return edge->type() == HeapGraphEdge::kShortcut;
-}
-
-
-void HeapSnapshotGenerator::MarkUserReachableObjects() {
-  List<HeapEntry*> worklist;
-
-  Vector<HeapGraphEdge*> children = snapshot_->root()->children();
-  for (int i = 0; i < children.length(); ++i) {
-    if (IsUserGlobalReference(children[i])) {
-      worklist.Add(children[i]->to());
-    }
-  }
-
-  while (!worklist.is_empty()) {
-    HeapEntry* entry = worklist.RemoveLast();
-    if (entry->user_reachable()) continue;
-    entry->set_user_reachable();
-    Vector<HeapGraphEdge*> children = entry->children();
-    for (int i = 0; i < children.length(); ++i) {
-      HeapEntry* child = children[i]->to();
-      if (!child->user_reachable()) {
-        worklist.Add(child);
-      }
-    }
-  }
-}
-
-
-static bool IsRetainingEdge(HeapGraphEdge* edge) {
-  if (edge->type() == HeapGraphEdge::kShortcut) return false;
-  // The edge is not retaining if it goes from system domain
-  // (i.e. an object not reachable from window) to the user domain
-  // (i.e. a reachable object).
-  return edge->from()->user_reachable()
-      || !edge->to()->user_reachable();
-}
-
-
-void HeapSnapshotGenerator::FillPostorderIndexes(
-    Vector<HeapEntry*>* entries) {
-  snapshot_->ClearPaint();
-  int current_entry = 0;
-  List<HeapEntry*> nodes_to_visit;
-  HeapEntry* root = snapshot_->root();
-  nodes_to_visit.Add(root);
-  snapshot_->root()->paint();
-  while (!nodes_to_visit.is_empty()) {
-    HeapEntry* entry = nodes_to_visit.last();
-    Vector<HeapGraphEdge*> children = entry->children();
-    bool has_new_edges = false;
-    for (int i = 0; i < children.length(); ++i) {
-      if (entry != root && !IsRetainingEdge(children[i])) continue;
-      HeapEntry* child = children[i]->to();
-      if (!child->painted()) {
-        nodes_to_visit.Add(child);
-        child->paint();
-        has_new_edges = true;
-      }
-    }
-    if (!has_new_edges) {
-      entry->set_postorder_index(current_entry);
-      (*entries)[current_entry++] = entry;
-      nodes_to_visit.RemoveLast();
-    }
-  }
-  ASSERT_EQ(current_entry, entries->length());
-}
-
-
-static int Intersect(int i1, int i2, const Vector<int>& dominators) {
-  int finger1 = i1, finger2 = i2;
-  while (finger1 != finger2) {
-    while (finger1 < finger2) finger1 = dominators[finger1];
-    while (finger2 < finger1) finger2 = dominators[finger2];
-  }
-  return finger1;
-}
-
-
-// The algorithm is based on the article:
-// K. Cooper, T. Harvey and K. Kennedy "A Simple, Fast Dominance Algorithm"
-// Softw. Pract. Exper. 4 (2001), pp. 1-10.
-bool HeapSnapshotGenerator::BuildDominatorTree(
-    const Vector<HeapEntry*>& entries,
-    Vector<int>* dominators) {
-  if (entries.length() == 0) return true;
-  HeapEntry* root = snapshot_->root();
-  const int entries_length = entries.length(), root_index = entries_length - 1;
-  for (int i = 0; i < root_index; ++i) (*dominators)[i] = HeapEntry::kNoEntry;
-  (*dominators)[root_index] = root_index;
-
-  // The affected array is used to mark entries which dominators
-  // have to be racalculated because of changes in their retainers.
-  ScopedVector<bool> affected(entries_length);
-  for (int i = 0; i < affected.length(); ++i) affected[i] = false;
-  // Mark the root direct children as affected.
-  Vector<HeapGraphEdge*> children = entries[root_index]->children();
-  for (int i = 0; i < children.length(); ++i) {
-    affected[children[i]->to()->postorder_index()] = true;
-  }
-
-  bool changed = true;
-  while (changed) {
-    changed = false;
-    if (!ProgressReport(false)) return false;
-    for (int i = root_index - 1; i >= 0; --i) {
-      if (!affected[i]) continue;
-      affected[i] = false;
-      // If dominator of the entry has already been set to root,
-      // then it can't propagate any further.
-      if ((*dominators)[i] == root_index) continue;
-      int new_idom_index = HeapEntry::kNoEntry;
-      Vector<HeapGraphEdge*> rets = entries[i]->retainers();
-      for (int j = 0; j < rets.length(); ++j) {
-        if (rets[j]->from() != root && !IsRetainingEdge(rets[j])) continue;
-        int ret_index = rets[j]->from()->postorder_index();
-        if (dominators->at(ret_index) != HeapEntry::kNoEntry) {
-          new_idom_index = new_idom_index == HeapEntry::kNoEntry
-              ? ret_index
-              : Intersect(ret_index, new_idom_index, *dominators);
-          // If idom has already reached the root, it doesn't make sense
-          // to check other retainers.
-          if (new_idom_index == root_index) break;
-        }
-      }
-      if (new_idom_index != HeapEntry::kNoEntry
-          && dominators->at(i) != new_idom_index) {
-        (*dominators)[i] = new_idom_index;
-        changed = true;
-        Vector<HeapGraphEdge*> children = entries[i]->children();
-        for (int j = 0; j < children.length(); ++j) {
-          affected[children[j]->to()->postorder_index()] = true;
-        }
-      }
-    }
-  }
-  return true;
-}
-
-
-bool HeapSnapshotGenerator::SetEntriesDominators() {
-  MarkUserReachableObjects();
-  // This array is used for maintaining postorder of nodes.
-  ScopedVector<HeapEntry*> ordered_entries(snapshot_->entries().length());
-  FillPostorderIndexes(&ordered_entries);
-  ScopedVector<int> dominators(ordered_entries.length());
-  if (!BuildDominatorTree(ordered_entries, &dominators)) return false;
-  for (int i = 0; i < ordered_entries.length(); ++i) {
-    ASSERT(dominators[i] != HeapEntry::kNoEntry);
-    ordered_entries[i]->set_dominator(ordered_entries[dominators[i]]);
-  }
-  return true;
-}
-
-
-bool HeapSnapshotGenerator::CalculateRetainedSizes() {
-  // As for the dominators tree we only know parent nodes, not
-  // children, to sum up total sizes we "bubble" node's self size
-  // adding it to all of its parents.
-  List<HeapEntry>& entries = snapshot_->entries();
-  for (int i = 0; i < entries.length(); ++i) {
-    HeapEntry* entry = &entries[i];
-    entry->set_retained_size(entry->self_size());
-  }
-  for (int i = 0; i < entries.length(); ++i) {
-    int entry_size = entries[i].self_size();
-    HeapEntry* current = &entries[i];
-    for (HeapEntry* dominator = current->dominator();
-         dominator != current;
-         current = dominator, dominator = current->dominator()) {
-      ASSERT(current->dominator() != NULL);
-      dominator->add_retained_size(entry_size);
-    }
-  }
-  return true;
-}
-
-
 template<int bytes> struct MaxDecimalDigitsIn;
 template<> struct MaxDecimalDigitsIn<4> {
   static const int kSigned = 11;
@@ -3417,8 +3200,8 @@ class OutputStreamWriter {
 
 // type, name|index, to_node.
 const int HeapSnapshotJSONSerializer::kEdgeFieldsCount = 3;
-// type, name, id, self_size, retained_size, dominator, children_index.
-const int HeapSnapshotJSONSerializer::kNodeFieldsCount = 7;
+// type, name, id, self_size, children_index.
+const int HeapSnapshotJSONSerializer::kNodeFieldsCount = 5;
 
 void HeapSnapshotJSONSerializer::Serialize(v8::OutputStream* stream) {
   ASSERT(writer_ == NULL);
@@ -3458,8 +3241,7 @@ HeapSnapshot* HeapSnapshotJSONSerializer::CreateFakeSnapshot() {
       (snapshot_->RawSnapshotSize() + MB - 1) / MB);
   HeapEntry* message = result->AddEntry(HeapEntry::kString, text, 0, 4);
   result->root()->SetIndexedReference(HeapGraphEdge::kElement, 1, message);
-  result->FillChildrenAndRetainers();
-  result->SetDominatorsToSelf();
+  result->FillChildren();
   return result;
 }
 
@@ -3575,10 +3357,6 @@ void HeapSnapshotJSONSerializer::SerializeNode(HeapEntry* entry,
   buffer[buffer_pos++] = ',';
   buffer_pos = utoa(entry->self_size(), buffer, buffer_pos);
   buffer[buffer_pos++] = ',';
-  buffer_pos = utoa(entry->retained_size(), buffer, buffer_pos);
-  buffer[buffer_pos++] = ',';
-  buffer_pos = utoa(entry_index(entry->dominator()), buffer, buffer_pos);
-  buffer[buffer_pos++] = ',';
   buffer_pos = utoa(edges_index, buffer, buffer_pos);
   buffer[buffer_pos++] = '\n';
   buffer[buffer_pos++] = '\0';
@@ -3615,8 +3393,6 @@ void HeapSnapshotJSONSerializer::SerializeSnapshot() {
         JSON_S("name") ","
         JSON_S("id") ","
         JSON_S("self_size") ","
-        JSON_S("retained_size") ","
-        JSON_S("dominator") ","
         JSON_S("edges_index")) ","
     JSON_S("node_types") ":" JSON_A(
         JSON_A(