Version 2.5.8...

src/profile-generator.cc

Index: src/profile-generator.cc
===================================================================
--- src/profile-generator.cc	(revision 5873)
+++ src/profile-generator.cc	(working copy)
@@ -829,7 +829,10 @@
 
 void HeapGraphEdge::Init(
     int child_index, Type type, const char* name, HeapEntry* to) {
-  ASSERT(type == kContextVariable || type == kProperty || type == kInternal);
+  ASSERT(type == kContextVariable
+         || type == kProperty
+         || type == kInternal
+         || type == kShortcut);
   child_index_ = child_index;
   type_ = type;
   name_ = name;
@@ -837,14 +840,20 @@
 }
 
 
-void HeapGraphEdge::Init(int child_index, int index, HeapEntry* to) {
+void HeapGraphEdge::Init(int child_index, Type type, int index, HeapEntry* to) {
+  ASSERT(type == kElement || type == kHidden);
   child_index_ = child_index;
-  type_ = kElement;
+  type_ = type;
   index_ = index;
   to_ = to;
 }
 
 
+void HeapGraphEdge::Init(int child_index, int index, HeapEntry* to) {
+  Init(child_index, kElement, index, to);
+}
+
+
 HeapEntry* HeapGraphEdge::From() {
   return reinterpret_cast<HeapEntry*>(this - child_index_) - 1;
 }
@@ -860,12 +869,18 @@
   snapshot_ = snapshot;
   type_ = type;
   painted_ = kUnpainted;
-  calculated_data_index_ = kNoCalculatedData;
   name_ = name;
-  id_ = id;
   self_size_ = self_size;
+  retained_size_ = 0;
   children_count_ = children_count;
   retainers_count_ = retainers_count;
+  dominator_ = NULL;
+
+  union {
+    uint64_t set_id;
+    Id stored_id;
+  } id_adaptor = {id};
+  id_ = id_adaptor.stored_id;
 }
 
 
@@ -879,9 +894,12 @@
 }
 
 
-void HeapEntry::SetElementReference(
-    int child_index, int index, HeapEntry* entry, int retainer_index) {
-  children_arr()[child_index].Init(child_index, index, entry);
+void HeapEntry::SetIndexedReference(HeapGraphEdge::Type type,
+                                    int child_index,
+                                    int index,
+                                    HeapEntry* entry,
+                                    int retainer_index) {
+  children_arr()[child_index].Init(child_index, type, index, entry);
   entry->retainers_arr()[retainer_index] = children_arr() + child_index;
 }
 
@@ -892,30 +910,16 @@
 }
 
 
-int HeapEntry::ReachableSize() {
-  if (calculated_data_index_ == kNoCalculatedData) {
-    calculated_data_index_ = snapshot_->AddCalculatedData();
+int HeapEntry::RetainedSize(bool exact) {
+  if (exact && (retained_size_ & kExactRetainedSizeTag) == 0) {
+    CalculateExactRetainedSize();
   }
-  return snapshot_->GetCalculatedData(
-      calculated_data_index_).ReachableSize(this);
+  return retained_size_ & (~kExactRetainedSizeTag);
 }
 
 
-int HeapEntry::RetainedSize() {
-  if (calculated_data_index_ == kNoCalculatedData) {
-    calculated_data_index_ = snapshot_->AddCalculatedData();
-  }
-  return snapshot_->GetCalculatedData(
-      calculated_data_index_).RetainedSize(this);
-}
-
-
 List<HeapGraphPath*>* HeapEntry::GetRetainingPaths() {
-  if (calculated_data_index_ == kNoCalculatedData) {
-    calculated_data_index_ = snapshot_->AddCalculatedData();
-  }
-  return snapshot_->GetCalculatedData(
-      calculated_data_index_).GetRetainingPaths(this);
+  return snapshot_->GetRetainingPaths(this);
 }
 
 
@@ -929,6 +933,7 @@
     HeapEntry* entry = list.RemoveLast();
     Vector<HeapGraphEdge> children = entry->children();
     for (int i = 0; i < children.length(); ++i) {
+      if (children[i].type() == HeapGraphEdge::kShortcut) continue;
       HeapEntry* child = children[i].to();
       if (!child->painted_reachable()) {
         list.Add(child);
@@ -952,8 +957,7 @@
 
 
 void HeapEntry::Print(int max_depth, int indent) {
-  OS::Print("%6d %6d %6d [%llu] ",
-            self_size(), ReachableSize(), RetainedSize(), id_);
+  OS::Print("%6d %6d [%llu] ", self_size(), RetainedSize(false), id());
   if (type() != kString) {
     OS::Print("%s %.40s\n", TypeAsString(), name_);
   } else {
@@ -985,6 +989,12 @@
       case HeapGraphEdge::kProperty:
         OS::Print("  %*c %s: ", indent, ' ', edge.name());
         break;
+      case HeapGraphEdge::kHidden:
+        OS::Print("  %*c $%d: ", indent, ' ', edge.index());
+        break;
+      case HeapGraphEdge::kShortcut:
+        OS::Print("  %*c ^%s: ", indent, ' ', edge.name());
+        break;
       default:
         OS::Print("!!! unknown edge type: %d ", edge.type());
     }
@@ -995,7 +1005,7 @@
 
 const char* HeapEntry::TypeAsString() {
   switch (type()) {
-    case kInternal: return "/internal/";
+    case kHidden: return "/hidden/";
     case kObject: return "/object/";
     case kClosure: return "/closure/";
     case kString: return "/string/";
@@ -1017,44 +1027,6 @@
 }
 
 
-static void DeleteHeapGraphPath(HeapGraphPath** path_ptr) {
-  delete *path_ptr;
-}
-
-void HeapEntryCalculatedData::Dispose() {
-  if (retaining_paths_ != NULL) retaining_paths_->Iterate(DeleteHeapGraphPath);
-  delete retaining_paths_;
-}
-
-
-int HeapEntryCalculatedData::ReachableSize(HeapEntry* entry) {
-  if (reachable_size_ == kUnknownSize) CalculateSizes(entry);
-  return reachable_size_;
-}
-
-
-int HeapEntryCalculatedData::RetainedSize(HeapEntry* entry) {
-  if (retained_size_ == kUnknownSize) CalculateSizes(entry);
-  return retained_size_;
-}
-
-
-class ReachableSizeCalculator {
- public:
-  ReachableSizeCalculator()
-      : reachable_size_(0) {
-  }
-
-  int reachable_size() const { return reachable_size_; }
-
-  void Apply(HeapEntry* entry) {
-    reachable_size_ += entry->self_size();
-  }
-
- private:
-  int reachable_size_;
-};
-
 class RetainedSizeCalculator {
  public:
   RetainedSizeCalculator()
@@ -1073,20 +1045,17 @@
   int retained_size_;
 };
 
-void HeapEntryCalculatedData::CalculateSizes(HeapEntry* entry) {
+void HeapEntry::CalculateExactRetainedSize() {
   // To calculate retained size, first we paint all reachable nodes in
-  // one color (and calculate reachable size as a byproduct), then we
-  // paint (or re-paint) all nodes reachable from other nodes with a
-  // different color. Then we consider only nodes painted with the
-  // first color for calculating the retained size.
-  entry->snapshot()->ClearPaint();
-  ReachableSizeCalculator rch_size_calc;
-  entry->ApplyAndPaintAllReachable(&rch_size_calc);
-  reachable_size_ = rch_size_calc.reachable_size();
+  // one color, then we paint (or re-paint) all nodes reachable from
+  // other nodes with a different color. Then we sum up self sizes of
+  // nodes painted with the first color.
+  snapshot()->ClearPaint();
+  PaintAllReachable();
 
   List<HeapEntry*> list(10);
-  HeapEntry* root = entry->snapshot()->root();
-  if (entry != root) {
+  HeapEntry* root = snapshot()->root();
+  if (this != root) {
     list.Add(root);
     root->paint_reachable_from_others();
   }
@@ -1094,8 +1063,9 @@
     HeapEntry* curr = list.RemoveLast();
     Vector<HeapGraphEdge> children = curr->children();
     for (int i = 0; i < children.length(); ++i) {
+      if (children[i].type() == HeapGraphEdge::kShortcut) continue;
       HeapEntry* child = children[i].to();
-      if (child != entry && child->not_painted_reachable_from_others()) {
+      if (child != this && child->not_painted_reachable_from_others()) {
         list.Add(child);
         child->paint_reachable_from_others();
       }
@@ -1103,8 +1073,10 @@
   }
 
   RetainedSizeCalculator ret_size_calc;
-  entry->snapshot()->IterateEntries(&ret_size_calc);
+  snapshot()->IterateEntries(&ret_size_calc);
   retained_size_ = ret_size_calc.reained_size();
+  ASSERT((retained_size_ & kExactRetainedSizeTag) == 0);
+  retained_size_ |= kExactRetainedSizeTag;
 }
 
 
@@ -1142,32 +1114,28 @@
 };
 
 
-List<HeapGraphPath*>* HeapEntryCalculatedData::GetRetainingPaths(
-    HeapEntry* entry) {
-  if (retaining_paths_ == NULL) retaining_paths_ = new List<HeapGraphPath*>(4);
-  if (retaining_paths_->length() == 0 && entry->retainers().length() != 0) {
-    CachedHeapGraphPath path;
-    FindRetainingPaths(entry, &path);
-  }
-  return retaining_paths_;
+List<HeapGraphPath*>* HeapEntry::CalculateRetainingPaths() {
+  List<HeapGraphPath*>* retaining_paths = new List<HeapGraphPath*>(4);
+  CachedHeapGraphPath path;
+  FindRetainingPaths(&path, retaining_paths);
+  return retaining_paths;
 }
 
 
-void HeapEntryCalculatedData::FindRetainingPaths(
-    HeapEntry* entry,
-    CachedHeapGraphPath* prev_path) {
-  Vector<HeapGraphEdge*> retainers = entry->retainers();
-  for (int i = 0; i < retainers.length(); ++i) {
-    HeapGraphEdge* ret_edge = retainers[i];
+void HeapEntry::FindRetainingPaths(CachedHeapGraphPath* prev_path,
+                                   List<HeapGraphPath*>* retaining_paths) {
+  Vector<HeapGraphEdge*> rets = retainers();
+  for (int i = 0; i < rets.length(); ++i) {
+    HeapGraphEdge* ret_edge = rets[i];
     if (prev_path->ContainsNode(ret_edge->From())) continue;
-    if (ret_edge->From() != entry->snapshot()->root()) {
+    if (ret_edge->From() != snapshot()->root()) {
       CachedHeapGraphPath path(*prev_path);
       path.Add(ret_edge);
-      FindRetainingPaths(ret_edge->From(), &path);
+      ret_edge->From()->FindRetainingPaths(&path, retaining_paths);
     } else {
       HeapGraphPath* ret_path = new HeapGraphPath(*prev_path->path());
       ret_path->Set(0, ret_edge);
-      retaining_paths_->Add(ret_path);
+      retaining_paths->Add(ret_path);
     }
   }
 }
@@ -1192,6 +1160,7 @@
         OS::Print("[#%s] ", edge->name());
         break;
       case HeapGraphEdge::kElement:
+      case HeapGraphEdge::kHidden:
         OS::Print("[%d] ", edge->index());
         break;
       case HeapGraphEdge::kInternal:
@@ -1200,6 +1169,9 @@
       case HeapGraphEdge::kProperty:
         OS::Print("[%s] ", edge->name());
         break;
+      case HeapGraphEdge::kShortcut:
+        OS::Print("[^%s] ", edge->name());
+        break;
       default:
         OS::Print("!!! unknown edge type: %d ", edge->type());
     }
@@ -1211,6 +1183,8 @@
 
 HeapObject *const HeapSnapshot::kInternalRootObject =
     reinterpret_cast<HeapObject*>(1);
+HeapObject *const HeapSnapshot::kGcRootsObject =
+    reinterpret_cast<HeapObject*>(2);
 
 
 // It is very important to keep objects that form a heap snapshot
@@ -1221,12 +1195,12 @@
 
 template <> struct SnapshotSizeConstants<4> {
   static const int kExpectedHeapGraphEdgeSize = 12;
-  static const int kExpectedHeapEntrySize = 32;
+  static const int kExpectedHeapEntrySize = 36;
 };
 
 template <> struct SnapshotSizeConstants<8> {
   static const int kExpectedHeapGraphEdgeSize = 24;
-  static const int kExpectedHeapEntrySize = 40;
+  static const int kExpectedHeapEntrySize = 48;
 };
 
 }  // namespace
@@ -1240,8 +1214,10 @@
       title_(title),
       uid_(uid),
       root_entry_(NULL),
+      gc_roots_entry_(NULL),
       raw_entries_(NULL),
-      entries_sorted_(false) {
+      entries_sorted_(false),
+      retaining_paths_(HeapEntry::Match) {
   STATIC_ASSERT(
       sizeof(HeapGraphEdge) ==
       SnapshotSizeConstants<sizeof(void*)>::kExpectedHeapGraphEdgeSize);  // NOLINT
@@ -1251,13 +1227,20 @@
 }
 
 
-static void DisposeCalculatedData(HeapEntryCalculatedData* cdata) {
-  cdata->Dispose();
+static void DeleteHeapGraphPath(HeapGraphPath** path_ptr) {
+  delete *path_ptr;
 }
 
 HeapSnapshot::~HeapSnapshot() {
   DeleteArray(raw_entries_);
-  calculated_data_.Iterate(DisposeCalculatedData);
+  for (HashMap::Entry* p = retaining_paths_.Start();
+       p != NULL;
+       p = retaining_paths_.Next(p)) {
+    List<HeapGraphPath*>* list =
+        reinterpret_cast<List<HeapGraphPath*>*>(p->value);
+    list->Iterate(DeleteHeapGraphPath);
+    delete list;
+  }
 }
 
 
@@ -1280,9 +1263,20 @@
   if (object == kInternalRootObject) {
     ASSERT(root_entry_ == NULL);
     ASSERT(retainers_count == 0);
-    root_entry_ = AddEntry(
-        HeapEntry::kInternal, "", 0, 0, children_count, retainers_count);
-    return root_entry_;
+    return (root_entry_ = AddEntry(HeapEntry::kObject,
+                                   "",
+                                   HeapObjectsMap::kInternalRootObjectId,
+                                   0,
+                                   children_count,
+                                   retainers_count));
+  } else if (object == kGcRootsObject) {
+    ASSERT(gc_roots_entry_ == NULL);
+    return (gc_roots_entry_ = AddEntry(HeapEntry::kObject,
+                                       "(GC roots)",
+                                       HeapObjectsMap::kGcRootsObjectId,
+                                       0,
+                                       children_count,
+                                       retainers_count));
   } else if (object->IsJSFunction()) {
     JSFunction* func = JSFunction::cast(object);
     SharedFunctionInfo* shared = func->shared();
@@ -1345,25 +1339,14 @@
                     children_count,
                     retainers_count);
   }
-  // No interest in this object.
-  return NULL;
+  return AddEntry(object,
+                  HeapEntry::kHidden,
+                  "system",
+                  children_count,
+                  retainers_count);
 }
 
 
-bool HeapSnapshot::WillAddEntry(HeapObject* object) {
-  return object == kInternalRootObject
-      || object->IsJSFunction()
-      || object->IsJSRegExp()
-      || object->IsJSObject()
-      || object->IsString()
-      || object->IsCode()
-      || object->IsSharedFunctionInfo()
-      || object->IsScript()
-      || object->IsFixedArray()
-      || object->IsHeapNumber();
-}
-
-
 static void HeapEntryClearPaint(HeapEntry** entry_ptr) {
   (*entry_ptr)->clear_paint();
 }
@@ -1373,12 +1356,6 @@
 }
 
 
-int HeapSnapshot::AddCalculatedData() {
-  calculated_data_.Add(HeapEntryCalculatedData());
-  return calculated_data_.length() - 1;
-}
-
-
 HeapEntry* HeapSnapshot::AddEntry(HeapObject* object,
                                   HeapEntry::Type type,
                                   const char* name,
@@ -1387,7 +1364,7 @@
   return AddEntry(type,
                   name,
                   collection_->GetObjectId(object->address()),
-                  GetObjectSize(object),
+                  object->Size(),
                   children_count,
                   retainers_count);
 }
@@ -1405,6 +1382,144 @@
 }
 
 
+void HeapSnapshot::FillReversePostorderIndexes(Vector<HeapEntry*>* entries) {
+  ClearPaint();
+  int current_entry = 0;
+  List<HeapEntry*> nodes_to_visit;
+  nodes_to_visit.Add(root());
+  root()->paint_reachable();
+  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 (children[i].type() == HeapGraphEdge::kShortcut) continue;
+      HeapEntry* child = children[i].to();
+      if (!child->painted_reachable()) {
+        nodes_to_visit.Add(child);
+        child->paint_reachable();
+        has_new_edges = true;
+      }
+    }
+    if (!has_new_edges) {
+      entry->set_ordered_index(current_entry);
+      entries->at(current_entry++) = entry;
+      nodes_to_visit.RemoveLast();
+    }
+  }
+  entries->Truncate(current_entry);
+}
+
+
+static int Intersect(int i1, int i2, const Vector<HeapEntry*>& dominators) {
+  int finger1 = i1, finger2 = i2;
+  while (finger1 != finger2) {
+    while (finger1 < finger2) finger1 = dominators[finger1]->ordered_index();
+    while (finger2 < finger1) finger2 = dominators[finger2]->ordered_index();
+  }
+  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.
+void HeapSnapshot::BuildDominatorTree(const Vector<HeapEntry*>& entries,
+                                      Vector<HeapEntry*>* dominators) {
+  if (entries.length() == 0) return;
+  const int root_index = entries.length() - 1;
+  for (int i = 0; i < root_index; ++i) dominators->at(i) = NULL;
+  dominators->at(root_index) = entries[root_index];
+  bool changed = true;
+  while (changed) {
+    changed = false;
+    for (int i = root_index - 1; i >= 0; --i) {
+      HeapEntry* new_idom = NULL;
+      Vector<HeapGraphEdge*> rets = entries[i]->retainers();
+      int j = 0;
+      for (; j < rets.length(); ++j) {
+        if (rets[j]->type() == HeapGraphEdge::kShortcut) continue;
+        HeapEntry* ret = rets[j]->From();
+        if (dominators->at(ret->ordered_index()) != NULL) {
+          new_idom = ret;
+          break;
+        }
+      }
+      for (++j; j < rets.length(); ++j) {
+        if (rets[j]->type() == HeapGraphEdge::kShortcut) continue;
+        HeapEntry* ret = rets[j]->From();
+        if (dominators->at(ret->ordered_index()) != NULL) {
+          new_idom = entries[Intersect(ret->ordered_index(),
+                                       new_idom->ordered_index(),
+                                       *dominators)];
+        }
+      }
+      if (new_idom != NULL && dominators->at(i) != new_idom) {
+        dominators->at(i) = new_idom;
+        changed = true;
+      }
+    }
+  }
+}
+
+
+void HeapSnapshot::SetEntriesDominators() {
+  // This array is used for maintaining reverse postorder of nodes.
+  ScopedVector<HeapEntry*> ordered_entries(entries_.length());
+  FillReversePostorderIndexes(&ordered_entries);
+  ScopedVector<HeapEntry*> dominators(ordered_entries.length());
+  BuildDominatorTree(ordered_entries, &dominators);
+  for (int i = 0; i < ordered_entries.length(); ++i) {
+    ASSERT(dominators[i] != NULL);
+    ordered_entries[i]->set_dominator(dominators[i]);
+  }
+  // For nodes unreachable from root, set dominator to itself.
+  for (int i = 0; i < entries_.length(); ++i) {
+    HeapEntry* entry = entries_[i];
+    if (entry->dominator() == NULL) entry->set_dominator(entry);
+  }
+}
+
+
+void HeapSnapshot::ApproximateRetainedSizes() {
+  SetEntriesDominators();
+  // As for the dominators tree we only know parent nodes, not
+  // children, to sum up total sizes we traverse the tree level by
+  // level upwards, starting from leaves.
+  for (int i = 0; i < entries_.length(); ++i) {
+    HeapEntry* entry = entries_[i];
+    entry->set_retained_size(entry->self_size());
+    entry->set_leaf();
+  }
+  while (true) {
+    bool onlyLeaves = true;
+    for (int i = 0; i < entries_.length(); ++i) {
+      HeapEntry *entry = entries_[i], *dominator = entry->dominator();
+      if (!entry->is_processed() && dominator != entry) {
+        dominator->set_non_leaf();
+        onlyLeaves = false;
+      }
+    }
+    if (onlyLeaves) break;
+
+    for (int i = 0; i < entries_.length(); ++i) {
+      HeapEntry *entry = entries_[i], *dominator = entry->dominator();
+      if (entry->is_leaf() && dominator != entry) {
+        dominator->add_retained_size(entry->retained_size());
+      }
+    }
+
+    // Mark all current leaves as processed, reset non-leaves back to leaves.
+    for (int i = 0; i < entries_.length(); ++i) {
+      HeapEntry* entry = entries_[i];
+      if (entry->is_leaf())
+        entry->set_processed();
+      else if (entry->is_non_leaf())
+        entry->set_leaf();
+    }
+  }
+}
+
+
 HeapEntry* HeapSnapshot::GetNextEntryToInit() {
   if (entries_.length() > 0) {
     HeapEntry* last_entry = entries_.last();
@@ -1419,41 +1534,21 @@
 }
 
 
-int HeapSnapshot::GetObjectSize(HeapObject* obj) {
-  return obj->IsJSObject() ?
-      CalculateNetworkSize(JSObject::cast(obj)) : obj->Size();
+HeapSnapshotsDiff* HeapSnapshot::CompareWith(HeapSnapshot* snapshot) {
+  return collection_->CompareSnapshots(this, snapshot);
 }
 
 
-int HeapSnapshot::CalculateNetworkSize(JSObject* obj) {
-  int size = obj->Size();
-  // If 'properties' and 'elements' are non-empty (thus, non-shared),
-  // take their size into account.
-  if (obj->properties() != Heap::empty_fixed_array()) {
-    size += obj->properties()->Size();
+List<HeapGraphPath*>* HeapSnapshot::GetRetainingPaths(HeapEntry* entry) {
+  HashMap::Entry* p =
+      retaining_paths_.Lookup(entry, HeapEntry::Hash(entry), true);
+  if (p->value == NULL) {
+    p->value = entry->CalculateRetainingPaths();
   }
-  if (obj->elements() != Heap::empty_fixed_array()) {
-    size += obj->elements()->Size();
-  }
-  // For functions, also account non-empty context and literals sizes.
-  if (obj->IsJSFunction()) {
-    JSFunction* f = JSFunction::cast(obj);
-    if (f->unchecked_context()->IsContext()) {
-      size += f->context()->Size();
-    }
-    if (f->literals()->length() != 0) {
-      size += f->literals()->Size();
-    }
-  }
-  return size;
+  return reinterpret_cast<List<HeapGraphPath*>*>(p->value);
 }
 
 
-HeapSnapshotsDiff* HeapSnapshot::CompareWith(HeapSnapshot* snapshot) {
-  return collection_->CompareSnapshots(this, snapshot);
-}
-
-
 template<class T>
 static int SortByIds(const T* entry1_ptr,
                      const T* entry2_ptr) {
@@ -1475,9 +1570,14 @@
 }
 
 
+const uint64_t HeapObjectsMap::kInternalRootObjectId = 0;
+const uint64_t HeapObjectsMap::kGcRootsObjectId = 1;
+// Increase kFirstAvailableObjectId if new 'special' objects appear.
+const uint64_t HeapObjectsMap::kFirstAvailableObjectId = 2;
+
 HeapObjectsMap::HeapObjectsMap()
     : initial_fill_mode_(true),
-      next_id_(1),
+      next_id_(kFirstAvailableObjectId),
       entries_map_(AddressesMatch),
       entries_(new List<EntryInfo>()) { }
 
@@ -1628,26 +1728,15 @@
 
 HeapEntriesMap::~HeapEntriesMap() {
   for (HashMap::Entry* p = entries_.Start(); p != NULL; p = entries_.Next(p)) {
-    if (!IsAlias(p->value)) delete reinterpret_cast<EntryInfo*>(p->value);
+    delete reinterpret_cast<EntryInfo*>(p->value);
   }
 }
 
 
-void HeapEntriesMap::Alias(HeapObject* from, HeapObject* to) {
-  HashMap::Entry* from_cache_entry = entries_.Lookup(from, Hash(from), true);
-  HashMap::Entry* to_cache_entry = entries_.Lookup(to, Hash(to), false);
-  if (from_cache_entry->value == NULL) {
-    ASSERT(to_cache_entry != NULL);
-    from_cache_entry->value = MakeAlias(to_cache_entry->value);
-  }
-}
-
-
 HeapEntry* HeapEntriesMap::Map(HeapObject* object) {
   HashMap::Entry* cache_entry = entries_.Lookup(object, Hash(object), false);
   if (cache_entry != NULL) {
-    EntryInfo* entry_info =
-        reinterpret_cast<EntryInfo*>(Unalias(cache_entry->value));
+    EntryInfo* entry_info = reinterpret_cast<EntryInfo*>(cache_entry->value);
     return entry_info->entry;
   } else {
     return NULL;
@@ -1671,9 +1760,9 @@
   ASSERT(from_cache_entry != NULL);
   ASSERT(to_cache_entry != NULL);
   EntryInfo* from_entry_info =
-      reinterpret_cast<EntryInfo*>(Unalias(from_cache_entry->value));
+      reinterpret_cast<EntryInfo*>(from_cache_entry->value);
   EntryInfo* to_entry_info =
-      reinterpret_cast<EntryInfo*>(Unalias(to_cache_entry->value));
+      reinterpret_cast<EntryInfo*>(to_cache_entry->value);
   if (prev_children_count)
     *prev_children_count = from_entry_info->children_count;
   if (prev_retainers_count)
@@ -1685,6 +1774,36 @@
 }
 
 
+HeapObjectsSet::HeapObjectsSet()
+    : entries_(HeapEntriesMap::HeapObjectsMatch) {
+}
+
+
+void HeapObjectsSet::Clear() {
+  entries_.Clear();
+}
+
+
+bool HeapObjectsSet::Contains(Object* obj) {
+  if (!obj->IsHeapObject()) return false;
+  HeapObject* object = HeapObject::cast(obj);
+  HashMap::Entry* cache_entry =
+      entries_.Lookup(object, HeapEntriesMap::Hash(object), false);
+  return cache_entry != NULL;
+}
+
+
+void HeapObjectsSet::Insert(Object* obj) {
+  if (!obj->IsHeapObject()) return;
+  HeapObject* object = HeapObject::cast(obj);
+  HashMap::Entry* cache_entry =
+      entries_.Lookup(object, HeapEntriesMap::Hash(object), true);
+  if (cache_entry->value == NULL) {
+    cache_entry->value = HeapEntriesMap::kHeapEntryPlaceholder;
+  }
+}
+
+
 HeapSnapshotGenerator::HeapSnapshotGenerator(HeapSnapshot* snapshot)
     : snapshot_(snapshot),
       collection_(snapshot->collection()),
@@ -1699,7 +1818,8 @@
     entries_->Pair(obj, HeapEntriesMap::kHeapEntryPlaceholder);
     return HeapEntriesMap::kHeapEntryPlaceholder;
   }
-  void SetElementReference(HeapObject* parent_obj,
+  void SetIndexedReference(HeapGraphEdge::Type,
+                           HeapObject* parent_obj,
                            HeapEntry*,
                            int,
                            Object* child_obj,
@@ -1714,10 +1834,18 @@
                          HeapEntry*) {
     entries_->CountReference(parent_obj, HeapObject::cast(child_obj));
   }
-  void SetRootReference(Object* child_obj, HeapEntry*) {
+  void SetRootShortcutReference(Object* child_obj, HeapEntry*) {
     entries_->CountReference(
         HeapSnapshot::kInternalRootObject, HeapObject::cast(child_obj));
   }
+  void SetRootGcRootsReference() {
+    entries_->CountReference(
+        HeapSnapshot::kInternalRootObject, HeapSnapshot::kGcRootsObject);
+  }
+  void SetStrongRootReference(Object* child_obj, HeapEntry*) {
+    entries_->CountReference(
+        HeapSnapshot::kGcRootsObject, HeapObject::cast(child_obj));
+  }
  private:
   HeapEntriesMap* entries_;
 };
@@ -1733,16 +1861,19 @@
     UNREACHABLE();
     return NULL;
   }
-  void SetElementReference(HeapObject* parent_obj,
+  void SetIndexedReference(HeapGraphEdge::Type type,
+                           HeapObject* parent_obj,
                            HeapEntry* parent_entry,
                            int index,
                            Object* child_obj,
                            HeapEntry* child_entry) {
     int child_index, retainer_index;
-    entries_->CountReference(parent_obj, HeapObject::cast(child_obj),
-                             &child_index, &retainer_index);
-    parent_entry->SetElementReference(
-        child_index, index, child_entry, retainer_index);
+    entries_->CountReference(parent_obj,
+                             HeapObject::cast(child_obj),
+                             &child_index,
+                             &retainer_index);
+    parent_entry->SetIndexedReference(
+        type, child_index, index, child_entry, retainer_index);
   }
   void SetNamedReference(HeapGraphEdge::Type type,
                          HeapObject* parent_obj,
@@ -1759,14 +1890,44 @@
                               child_entry,
                               retainer_index);
   }
-  void SetRootReference(Object* child_obj, HeapEntry* child_entry) {
+  void SetRootGcRootsReference() {
     int child_index, retainer_index;
-    entries_->CountReference(
-        HeapSnapshot::kInternalRootObject, HeapObject::cast(child_obj),
-        &child_index, &retainer_index);
-    snapshot_->root()->SetElementReference(
-        child_index, child_index + 1, child_entry, retainer_index);
+    entries_->CountReference(HeapSnapshot::kInternalRootObject,
+                             HeapSnapshot::kGcRootsObject,
+                             &child_index,
+                             &retainer_index);
+    snapshot_->root()->SetIndexedReference(HeapGraphEdge::kElement,
+                                           child_index,
+                                           child_index + 1,
+                                           snapshot_->gc_roots(),
+                                           retainer_index);
   }
+  void SetRootShortcutReference(Object* child_obj,
+                                HeapEntry* child_entry) {
+    int child_index, retainer_index;
+    entries_->CountReference(HeapSnapshot::kInternalRootObject,
+                             HeapObject::cast(child_obj),
+                             &child_index,
+                             &retainer_index);
+    snapshot_->root()->SetNamedReference(HeapGraphEdge::kShortcut,
+                                         child_index,
+                                         collection_->GetName(child_index + 1),
+                                         child_entry,
+                                         retainer_index);
+  }
+  void SetStrongRootReference(Object* child_obj,
+                              HeapEntry* child_entry) {
+    int child_index, retainer_index;
+    entries_->CountReference(HeapSnapshot::kGcRootsObject,
+                             HeapObject::cast(child_obj),
+                             &child_index,
+                             &retainer_index);
+    snapshot_->gc_roots()->SetIndexedReference(HeapGraphEdge::kElement,
+                                               child_index,
+                                               child_index + 1,
+                                               child_entry,
+                                               retainer_index);
+  }
  private:
   HeapSnapshot* snapshot_;
   HeapSnapshotsCollection* collection_;
@@ -1788,6 +1949,19 @@
   HeapSnapshot* snapshot_;
 };
 
+class RootsReferencesExtractor : public ObjectVisitor {
+ public:
+  explicit RootsReferencesExtractor(HeapSnapshotGenerator* generator)
+      : generator_(generator) {
+  }
+  void VisitPointers(Object** start, Object** end) {
+    for (Object** p = start; p < end; p++) generator_->SetGcRootsReference(*p);
+  }
+ private:
+  HeapSnapshotGenerator* generator_;
+};
+
+
 void HeapSnapshotGenerator::GenerateSnapshot() {
   AssertNoAllocation no_alloc;
 
@@ -1795,12 +1969,14 @@
   SnapshotCounter counter(&entries_);
   filler_ = &counter;
   filler_->AddEntry(HeapSnapshot::kInternalRootObject);
-  HeapIterator iterator1;
-  for (HeapObject* obj = iterator1.next();
-       obj != NULL;
-       obj = iterator1.next()) {
+  filler_->AddEntry(HeapSnapshot::kGcRootsObject);
+  HeapIterator iterator(HeapIterator::kPreciseFiltering);
+  for (HeapObject* obj = iterator.next(); obj != NULL; obj = iterator.next()) {
     ExtractReferences(obj);
   }
+  SetRootGcRootsReference();
+  RootsReferencesExtractor extractor(this);
+  Heap::IterateRoots(&extractor, VISIT_ONLY_STRONG);
 
   // Allocate and fill entries in the snapshot, allocate references.
   snapshot_->AllocateEntries(entries_.entries_count(),
@@ -1812,12 +1988,14 @@
   // Pass 2. Fill references.
   SnapshotFiller filler(snapshot_, &entries_);
   filler_ = &filler;
-  HeapIterator iterator2;
-  for (HeapObject* obj = iterator2.next();
-       obj != NULL;
-       obj = iterator2.next()) {
+  iterator.reset();
+  for (HeapObject* obj = iterator.next(); obj != NULL; obj = iterator.next()) {
     ExtractReferences(obj);
   }
+  SetRootGcRootsReference();
+  Heap::IterateRoots(&extractor, VISIT_ONLY_STRONG);
+
+  snapshot_->ApproximateRetainedSizes();
 }
 
 
@@ -1825,25 +2003,8 @@
   if (!obj->IsHeapObject()) return NULL;
   HeapObject* object = HeapObject::cast(obj);
   HeapEntry* entry = entries_.Map(object);
-
   // A new entry.
-  if (entry == NULL) {
-    if (obj->IsJSGlobalPropertyCell()) {
-      Object* cell_target = JSGlobalPropertyCell::cast(obj)->value();
-      entry = GetEntry(cell_target);
-      // If GPC references an object that we have interest in (see
-      // HeapSnapshot::AddEntry, WillAddEntry), add the object.  We
-      // don't store HeapEntries for GPCs. Instead, we make our hash
-      // map to point to object's HeapEntry by GPCs address.
-      if (entry != NULL) {
-        entries_.Alias(object, HeapObject::cast(cell_target));
-      }
-      return entry;
-    }
-
-    if (snapshot_->WillAddEntry(object)) entry = filler_->AddEntry(object);
-  }
-
+  if (entry == NULL) entry = filler_->AddEntry(object);
   return entry;
 }
 
@@ -1852,43 +2013,44 @@
  public:
   IndexedReferencesExtractor(HeapSnapshotGenerator* generator,
                              HeapObject* parent_obj,
-                             HeapEntry* parent_entry)
+                             HeapEntry* parent_entry,
+                             HeapObjectsSet* known_references = NULL)
       : generator_(generator),
         parent_obj_(parent_obj),
         parent_(parent_entry),
+        known_references_(known_references),
         next_index_(1) {
   }
-
-  void VisitPointer(Object** o) {
-    generator_->SetElementReference(parent_obj_, parent_, next_index_++, *o);
-  }
-
   void VisitPointers(Object** start, Object** end) {
-    for (Object** p = start; p < end; p++) VisitPointer(p);
+    for (Object** p = start; p < end; p++) {
+      if (!known_references_ || !known_references_->Contains(*p)) {
+        generator_->SetHiddenReference(parent_obj_, parent_, next_index_++, *p);
+      }
+    }
   }
-
  private:
   HeapSnapshotGenerator* generator_;
   HeapObject* parent_obj_;
   HeapEntry* parent_;
+  HeapObjectsSet* known_references_;
   int next_index_;
 };
 
 
 void HeapSnapshotGenerator::ExtractReferences(HeapObject* obj) {
-  // We need to reference JS global objects from snapshot's root.
-  // We use JSGlobalProxy because this is what embedder (e.g. browser)
-  // uses for the global object.
-  if (obj->IsJSGlobalProxy()) {
-    JSGlobalProxy* proxy = JSGlobalProxy::cast(obj);
-    SetRootReference(proxy->map()->prototype());
-    return;
-  }
-
   HeapEntry* entry = GetEntry(obj);
   if (entry == NULL) return;  // No interest in this object.
 
-  if (obj->IsJSObject()) {
+  known_references_.Clear();
+  if (obj->IsJSGlobalProxy()) {
+    // We need to reference JS global objects from snapshot's root.
+    // We use JSGlobalProxy because this is what embedder (e.g. browser)
+    // uses for the global object.
+    JSGlobalProxy* proxy = JSGlobalProxy::cast(obj);
+    SetRootShortcutReference(proxy->map()->prototype());
+    IndexedReferencesExtractor refs_extractor(this, obj, entry);
+    obj->Iterate(&refs_extractor);
+  } else if (obj->IsJSObject()) {
     JSObject* js_obj = JSObject::cast(obj);
     ExtractClosureReferences(js_obj, entry);
     ExtractPropertyReferences(js_obj, entry);
@@ -1903,18 +2065,18 @@
             obj, entry, Heap::prototype_symbol(), js_fun->prototype());
       }
     }
+    IndexedReferencesExtractor refs_extractor(
+        this, obj, entry, &known_references_);
+    obj->Iterate(&refs_extractor);
   } else if (obj->IsString()) {
     if (obj->IsConsString()) {
       ConsString* cs = ConsString::cast(obj);
-      SetInternalReference(obj, entry, "1", cs->first());
-      SetInternalReference(obj, entry, "2", cs->second());
+      SetInternalReference(obj, entry, 1, cs->first());
+      SetInternalReference(obj, entry, 2, cs->second());
     }
-  } else if (obj->IsCode() || obj->IsSharedFunctionInfo() || obj->IsScript()) {
+  } else {
     IndexedReferencesExtractor refs_extractor(this, obj, entry);
     obj->Iterate(&refs_extractor);
-  } else if (obj->IsFixedArray()) {
-    IndexedReferencesExtractor refs_extractor(this, obj, entry);
-    obj->Iterate(&refs_extractor);
   }
 }
 
@@ -1967,8 +2129,17 @@
     for (int i = 0; i < length; ++i) {
       Object* k = dictionary->KeyAt(i);
       if (dictionary->IsKey(k)) {
+        Object* target = dictionary->ValueAt(i);
         SetPropertyReference(
-            js_obj, entry, String::cast(k), dictionary->ValueAt(i));
+            js_obj, entry, String::cast(k), target);
+        // We assume that global objects can only have slow properties.
+        if (target->IsJSGlobalPropertyCell()) {
+          SetPropertyShortcutReference(js_obj,
+                                       entry,
+                                       String::cast(k),
+                                       JSGlobalPropertyCell::cast(
+                                           target)->value());
+        }
       }
     }
   }
@@ -2024,6 +2195,7 @@
                                collection_->GetName(reference_name),
                                child_obj,
                                child_entry);
+    known_references_.Insert(child_obj);
   }
 }
 
@@ -2034,8 +2206,13 @@
                                                 Object* child_obj) {
   HeapEntry* child_entry = GetEntry(child_obj);
   if (child_entry != NULL) {
-    filler_->SetElementReference(
-        parent_obj, parent_entry, index, child_obj, child_entry);
+    filler_->SetIndexedReference(HeapGraphEdge::kElement,
+                                 parent_obj,
+                                 parent_entry,
+                                 index,
+                                 child_obj,
+                                 child_entry);
+    known_references_.Insert(child_obj);
   }
 }
 
@@ -2052,6 +2229,7 @@
                                reference_name,
                                child_obj,
                                child_entry);
+    known_references_.Insert(child_obj);
   }
 }
 
@@ -2068,10 +2246,27 @@
                                collection_->GetName(index),
                                child_obj,
                                child_entry);
+    known_references_.Insert(child_obj);
   }
 }
 
 
+void HeapSnapshotGenerator::SetHiddenReference(HeapObject* parent_obj,
+                                               HeapEntry* parent_entry,
+                                               int index,
+                                               Object* child_obj) {
+  HeapEntry* child_entry = GetEntry(child_obj);
+  if (child_entry != NULL) {
+    filler_->SetIndexedReference(HeapGraphEdge::kHidden,
+                                 parent_obj,
+                                 parent_entry,
+                                 index,
+                                 child_obj,
+                                 child_entry);
+  }
+}
+
+
 void HeapSnapshotGenerator::SetPropertyReference(HeapObject* parent_obj,
                                                  HeapEntry* parent_entry,
                                                  String* reference_name,
@@ -2086,26 +2281,57 @@
                                collection_->GetName(reference_name),
                                child_obj,
                                child_entry);
+    known_references_.Insert(child_obj);
   }
 }
 
 
-void HeapSnapshotGenerator::SetRootReference(Object* child_obj) {
+void HeapSnapshotGenerator::SetPropertyShortcutReference(
+    HeapObject* parent_obj,
+    HeapEntry* parent_entry,
+    String* reference_name,
+    Object* child_obj) {
   HeapEntry* child_entry = GetEntry(child_obj);
+  if (child_entry != NULL) {
+    filler_->SetNamedReference(HeapGraphEdge::kShortcut,
+                               parent_obj,
+                               parent_entry,
+                               collection_->GetName(reference_name),
+                               child_obj,
+                               child_entry);
+  }
+}
+
+
+void HeapSnapshotGenerator::SetRootGcRootsReference() {
+  filler_->SetRootGcRootsReference();
+}
+
+
+void HeapSnapshotGenerator::SetRootShortcutReference(Object* child_obj) {
+  HeapEntry* child_entry = GetEntry(child_obj);
   ASSERT(child_entry != NULL);
-  filler_->SetRootReference(child_obj, child_entry);
+  filler_->SetRootShortcutReference(child_obj, child_entry);
 }
 
 
+void HeapSnapshotGenerator::SetGcRootsReference(Object* child_obj) {
+  HeapEntry* child_entry = GetEntry(child_obj);
+  if (child_entry != NULL) {
+    filler_->SetStrongRootReference(child_obj, child_entry);
+  }
+}
+
+
 void HeapSnapshotsDiff::CreateRoots(int additions_count, int deletions_count) {
   raw_additions_root_ =
       NewArray<char>(HeapEntry::EntriesSize(1, additions_count, 0));
   additions_root()->Init(
-      snapshot2_, HeapEntry::kInternal, "", 0, 0, additions_count, 0);
+      snapshot2_, HeapEntry::kHidden, "", 0, 0, additions_count, 0);
   raw_deletions_root_ =
       NewArray<char>(HeapEntry::EntriesSize(1, deletions_count, 0));
   deletions_root()->Init(
-      snapshot1_, HeapEntry::kInternal, "", 0, 0, deletions_count, 0);
+      snapshot1_, HeapEntry::kHidden, "", 0, 0, deletions_count, 0);
 }
 
 
@@ -2324,7 +2550,8 @@
   writer_->AddCharacter(',');
   writer_->AddNumber(edge->type());
   writer_->AddCharacter(',');
-  if (edge->type() == HeapGraphEdge::kElement) {
+  if (edge->type() == HeapGraphEdge::kElement
+      || edge->type() == HeapGraphEdge::kHidden) {
     writer_->AddNumber(edge->index());
   } else {
     writer_->AddNumber(GetStringId(edge->name()));
@@ -2344,6 +2571,10 @@
   writer_->AddNumber(entry->id());
   writer_->AddCharacter(',');
   writer_->AddNumber(entry->self_size());
+  writer_->AddCharacter(',');
+  writer_->AddNumber(entry->RetainedSize(false));
+  writer_->AddCharacter(',');
+  writer_->AddNumber(GetNodeId(entry->dominator()));
   Vector<HeapGraphEdge> children = entry->children();
   writer_->AddCharacter(',');
   writer_->AddNumber(children.length());
@@ -2355,23 +2586,25 @@
 
 
 void HeapSnapshotJSONSerializer::SerializeNodes() {
-  // The first (zero) item of nodes array is a JSON-ified object
-  // describing node serialization layout.
-  // We use a set of macros to improve readability.
+  // The first (zero) item of nodes array is an object describing node
+  // serialization layout.  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(
+#define JSON_S(s) "\""s"\""
+  writer_->AddString(JSON_O(
     JSON_S("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("children_count")
         "," JSON_S("children"))
     "," JSON_S("types") ":" JSON_A(
         JSON_A(
-            JSON_S("internal")
+            JSON_S("hidden")
             "," JSON_S("array")
             "," JSON_S("string")
             "," JSON_S("object")
@@ -2383,6 +2616,8 @@
         "," JSON_S("number")
         "," JSON_S("number")
         "," JSON_S("number")
+        "," JSON_S("number")
+        "," JSON_S("number")
         "," JSON_O(
             JSON_S("fields") ":" JSON_A(
                 JSON_S("type")
@@ -2393,14 +2628,17 @@
                     JSON_S("context")
                     "," JSON_S("element")
                     "," JSON_S("property")
-                    "," JSON_S("internal"))
+                    "," JSON_S("internal")
+                    "," JSON_S("hidden")
+                    "," JSON_S("shortcut"))
                 "," JSON_S("string_or_number")
-                "," JSON_S("node"))))) "\"");
+                "," JSON_S("node"))))));
 #undef JSON_S
 #undef JSON_O
 #undef JSON_A
 
-  const int node_fields_count = 5;  // type,name,id,self_size,children_count.
+  const int node_fields_count = 7;
+  // type,name,id,self_size,retained_size,dominator,children_count.
   const int edge_fields_count = 3;  // type,name|index,to_node.
   List<HashMap::Entry*> sorted_nodes;
   SortHashMap(&nodes_, &sorted_nodes);