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

src/profile-generator.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 946 matching lines @@
 }
 
 
 const int HeapEntry::kNoEntry = -1;
 
 HeapEntry::HeapEntry(HeapSnapshot* snapshot,
                      Type type,
                      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) { }
 
 
 void HeapEntry::SetNamedReference(HeapGraphEdge::Type type,
                                   const char* name,
                                   HeapEntry* entry) {
   HeapGraphEdge edge(type, name, this->index(), entry->index());
   snapshot_->edges().Add(edge);
   ++children_count_;
-  ++entry->retainers_count_;
 }
 
 
 void HeapEntry::SetIndexedReference(HeapGraphEdge::Type type,
                                     int index,
                                     HeapEntry* entry) {
   HeapGraphEdge edge(type, index, this->index(), entry->index());
   snapshot_->edges().Add(edge);
   ++children_count_;
-  ++entry->retainers_count_;
 }
 
 
 Handle<HeapObject> HeapEntry::GetHeapObject() {
   return snapshot_->collection()->FindHeapObjectById(id());
 }
 
 
 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);
   if (type() != kString) {
     OS::Print("%s %.40s\n", TypeAsString(), name_);
   } else {
     OS::Print("\"");
     const char* c = name_;
     while (*c && (c - name_) <= 40) {
       if (*c != '\n')
         OS::Print("%c", *c);
       else
         OS::Print("\\n");
@@ skipping 61 matching lines @@
 
 
 // It is very important to keep objects that form a heap snapshot
 // as small as possible.
 namespace {  // Avoid littering the global namespace.
 
 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 = 24;
   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 = 32;
   static const uint64_t kMaxSerializableSnapshotRawSize =
       static_cast<uint64_t>(6000) * MB;
 };
 
 }  // namespace
 
 HeapSnapshot::HeapSnapshot(HeapSnapshotsCollection* collection,
                            HeapSnapshot::Type type,
                            const char* title,
                            unsigned uid)
@@ skipping 21 matching lines @@
   collection_->RemoveSnapshot(this);
   delete this;
 }
 
 
 void HeapSnapshot::RememberLastJSObjectId() {
   max_snapshot_js_object_id_ = collection_->last_assigned_id();
 }
 
 
-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.
   HeapEntry* entry = AddEntry(HeapEntry::kObject,
                               "",
                               HeapObjectsMap::kInternalRootObjectId,
                               0);
   root_index_ = entry->index();
   ASSERT(root_index_ == 0);
   return entry;
@@ skipping 27 matching lines @@
 HeapEntry* HeapSnapshot::AddEntry(HeapEntry::Type type,
                                   const char* name,
                                   SnapshotObjectId id,
                                   int size) {
   HeapEntry entry(this, type, name, id, size);
   entries_.Add(entry);
   return &entries_.last();
 }
 
 
-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]);
-  }
-}
-
 
 class FindEntryById {
  public:
   explicit FindEntryById(SnapshotObjectId id) : id_(id) { }
   int operator()(HeapEntry* const* entry) {
     if ((*entry)->id() == id_) return 0;
     return (*entry)->id() < id_ ? -1 : 1;
   }
  private:
   SnapshotObjectId id_;
@@ skipping 39 matching lines @@
 static size_t GetMemoryUsedByList(const List<T, P>& list) {
   return list.capacity() * sizeof(T);
 }
 
 
 size_t HeapSnapshot::RawSnapshotSize() const {
   return
       GetMemoryUsedByList(entries_) +
       GetMemoryUsedByList(edges_) +
       GetMemoryUsedByList(children_) +
-      GetMemoryUsedByList(retainers_) +
       GetMemoryUsedByList(sorted_entries_);
 }
 
 
 // We split IDs on evens for embedder objects (see
 // HeapObjectsMap::GenerateId) and odds for native objects.
 const SnapshotObjectId HeapObjectsMap::kInternalRootObjectId = 1;
 const SnapshotObjectId HeapObjectsMap::kGcRootsObjectId =
     HeapObjectsMap::kInternalRootObjectId + HeapObjectsMap::kObjectIdStep;
 const SnapshotObjectId HeapObjectsMap::kGcRootsFirstSubrootId =
@@ skipping 1786 matching lines @@
 #endif
 
   SetProgressTotal(1);  // 1 pass.
 
 #ifdef DEBUG
   debug_heap->Verify();
 #endif
 
   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;
 }
 
 
 void HeapSnapshotGenerator::ProgressStep() {
   ++progress_counter_;
 }
 
@@ skipping 21 matching lines @@
 
 
 bool HeapSnapshotGenerator::FillReferences() {
   SnapshotFiller filler(snapshot_, &entries_);
   v8_heap_explorer_.AddRootEntries(&filler);
   return v8_heap_explorer_.IterateAndExtractReferences(&filler)
       && dom_explorer_.IterateAndExtractReferences(&filler);
 }
 
 
-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;
   static const int kUnsigned = 10;
 };
 template<> struct MaxDecimalDigitsIn<8> {
   static const int kSigned = 20;
   static const int kUnsigned = 20;
 };
 
@@ skipping 78 matching lines @@
   v8::OutputStream* stream_;
   int chunk_size_;
   ScopedVector<char> chunk_;
   int chunk_pos_;
   bool aborted_;
 };
 
 
 // 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);
   writer_ = new OutputStreamWriter(stream);
 
   HeapSnapshot* original_snapshot = NULL;
   if (snapshot_->RawSnapshotSize() >=
       SnapshotSizeConstants<kPointerSize>::kMaxSerializableSnapshotRawSize) {
     // The snapshot is too big. Serialize a fake snapshot.
     original_snapshot = snapshot_;
@@ skipping 19 matching lines @@
                                           snapshot_->uid());
   result->AddRootEntry();
   const char* text = snapshot_->collection()->names()->GetFormatted(
       "The snapshot is too big. "
       "Maximum snapshot size is %"  V8_PTR_PREFIX "u MB. "
       "Actual snapshot size is %"  V8_PTR_PREFIX "u MB.",
       SnapshotSizeConstants<kPointerSize>::kMaxSerializableSnapshotRawSize / MB,
       (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;
 }
 
 
 void HeapSnapshotJSONSerializer::SerializeImpl() {
   List<HeapEntry>& nodes = snapshot_->entries();
   ASSERT(0 == snapshot_->root()->index());
   writer_->AddCharacter('{');
   writer_->AddString("\"snapshot\":{");
   SerializeSnapshot();
@@ skipping 77 matching lines @@
       SerializeEdge(children[j], first_edge);
       first_edge = false;
       if (writer_->aborted()) return;
     }
   }
 }
 
 
 void HeapSnapshotJSONSerializer::SerializeNode(HeapEntry* entry,
                                                int edges_index) {
-  // The buffer needs space for 6 ints, 1 uint32_t, 7 commas, \n and \0
+  // The buffer needs space for 5 uint32_t, 5 commas, \n and \0
   static const int kBufferSize =
-      6 * MaxDecimalDigitsIn<sizeof(int)>::kSigned  // NOLINT
-      + MaxDecimalDigitsIn<sizeof(uint32_t)>::kUnsigned  // NOLINT
-      + 7 + 1 + 1;
+      5 * MaxDecimalDigitsIn<sizeof(uint32_t)>::kUnsigned  // NOLINT
+      + 5 + 1 + 1;
   EmbeddedVector<char, kBufferSize> buffer;
   int buffer_pos = 0;
   if (entry_index(entry) != 0) {
     buffer[buffer_pos++] = ',';
   }
   buffer_pos = utoa(entry->type(), buffer, buffer_pos);
   buffer[buffer_pos++] = ',';
   buffer_pos = utoa(GetStringId(entry->name()), buffer, buffer_pos);
   buffer[buffer_pos++] = ',';
   buffer_pos = utoa(entry->id(), buffer, buffer_pos);
   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';
   writer_->AddString(buffer.start());
 }
 
 
 void HeapSnapshotJSONSerializer::SerializeNodes(const List<HeapEntry>& nodes) {
   int edges_index = 0;
   for (int i = 0; i < nodes.length(); ++i) {
@@ skipping 16 matching lines @@
   // We use a set of macros to improve readability.
 #define JSON_A(s) "[" s "]"
 #define JSON_O(s) "{" s "}"
 #define JSON_S(s) "\"" s "\""
   writer_->AddString(JSON_O(
     JSON_S("node_fields") ":" JSON_A(
         JSON_S("type") ","
         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(
             JSON_S("hidden") ","
             JSON_S("array") ","
             JSON_S("string") ","
             JSON_S("object") ","
             JSON_S("code") ","
             JSON_S("closure") ","
             JSON_S("regexp") ","
@@ skipping 118 matching lines @@
 
 
 void HeapSnapshotJSONSerializer::SortHashMap(
     HashMap* map, List<HashMap::Entry*>* sorted_entries) {
   for (HashMap::Entry* p = map->Start(); p != NULL; p = map->Next(p))
     sorted_entries->Add(p);
   sorted_entries->Sort(SortUsingEntryValue);
 }
 
 } }  // namespace v8::internal