Upgrade V8 to 2.5.8

1 files changed, 111 insertions, 74 deletions

diff --git a/deps/v8/src/profile-generator.h b/deps/v8/src/profile-generator.h
index b691a056e..30d70a2c7 100644
--- a/deps/v8/src/profile-generator.h
+++ b/deps/v8/src/profile-generator.h
@@ -439,22 +439,26 @@ class HeapGraphEdge BASE_EMBEDDED {
     kContextVariable = v8::HeapGraphEdge::kContextVariable,
     kElement = v8::HeapGraphEdge::kElement,
     kProperty = v8::HeapGraphEdge::kProperty,
-    kInternal = v8::HeapGraphEdge::kInternal
+    kInternal = v8::HeapGraphEdge::kInternal,
+    kHidden = v8::HeapGraphEdge::kHidden,
+    kShortcut = v8::HeapGraphEdge::kShortcut
   };
 
   HeapGraphEdge() { }
   void Init(int child_index, Type type, const char* name, HeapEntry* to);
+  void Init(int child_index, Type type, int index, HeapEntry* to);
   void Init(int child_index, int index, HeapEntry* to);
 
   Type type() { return static_cast<Type>(type_); }
   int index() {
-    ASSERT(type_ == kElement);
+    ASSERT(type_ == kElement || type_ == kHidden);
     return index_;
   }
   const char* name() {
     ASSERT(type_ == kContextVariable
            || type_ == kProperty
-           || type_ == kInternal);
+           || type_ == kInternal
+           || type_ == kShortcut);
     return name_;
   }
   HeapEntry* to() { return to_; }
@@ -462,8 +466,8 @@ class HeapGraphEdge BASE_EMBEDDED {
   HeapEntry* From();
 
  private:
-  int child_index_ : 30;
-  unsigned type_ : 2;
+  int child_index_ : 29;
+  unsigned type_ : 3;
   union {
     int index_;
     const char* name_;
@@ -500,7 +504,7 @@ class HeapSnapshot;
 class HeapEntry BASE_EMBEDDED {
  public:
   enum Type {
-    kInternal = v8::HeapGraphNode::kInternal,
+    kHidden = v8::HeapGraphNode::kHidden,
     kArray = v8::HeapGraphNode::kArray,
     kString = v8::HeapGraphNode::kString,
     kObject = v8::HeapGraphNode::kObject,
@@ -522,14 +526,21 @@ class HeapEntry BASE_EMBEDDED {
   HeapSnapshot* snapshot() { return snapshot_; }
   Type type() { return static_cast<Type>(type_); }
   const char* name() { return name_; }
-  uint64_t id() { return id_; }
+  uint64_t id();
   int self_size() { return self_size_; }
+  int retained_size() { return retained_size_; }
+  void add_retained_size(int size) { retained_size_ += size; }
+  void set_retained_size(int value) { retained_size_ = value; }
+  int ordered_index() { return ordered_index_; }
+  void set_ordered_index(int value) { ordered_index_ = value; }
 
   Vector<HeapGraphEdge> children() {
     return Vector<HeapGraphEdge>(children_arr(), children_count_); }
   Vector<HeapGraphEdge*> retainers() {
     return Vector<HeapGraphEdge*>(retainers_arr(), retainers_count_); }
   List<HeapGraphPath*>* GetRetainingPaths();
+  HeapEntry* dominator() { return dominator_; }
+  void set_dominator(HeapEntry* entry) { dominator_ = entry; }
 
   void clear_paint() { painted_ = kUnpainted; }
   bool painted_reachable() { return painted_ == kPainted; }
@@ -547,8 +558,18 @@ class HeapEntry BASE_EMBEDDED {
   void ApplyAndPaintAllReachable(Visitor* visitor);
   void PaintAllReachable();
 
-  void SetElementReference(
-      int child_index, int index, HeapEntry* entry, int retainer_index);
+  bool is_leaf() { return painted_ == kLeaf; }
+  void set_leaf() { painted_ = kLeaf; }
+  bool is_non_leaf() { return painted_ == kNonLeaf; }
+  void set_non_leaf() { painted_ = kNonLeaf; }
+  bool is_processed() { return painted_ == kProcessed; }
+  void set_processed() { painted_ = kProcessed; }
+
+  void SetIndexedReference(HeapGraphEdge::Type type,
+                           int child_index,
+                           int index,
+                           HeapEntry* entry,
+                           int retainer_index);
   void SetNamedReference(HeapGraphEdge::Type type,
                          int child_index,
                          const char* name,
@@ -557,14 +578,19 @@ class HeapEntry BASE_EMBEDDED {
   void SetUnidirElementReference(int child_index, int index, HeapEntry* entry);
 
   int EntrySize() { return EntriesSize(1, children_count_, retainers_count_); }
-  int ReachableSize();
-  int RetainedSize();
+  int RetainedSize(bool exact);
+  List<HeapGraphPath*>* CalculateRetainingPaths();
 
   void Print(int max_depth, int indent);
 
   static int EntriesSize(int entries_count,
                          int children_count,
                          int retainers_count);
+  static uint32_t Hash(HeapEntry* entry) {
+    return ComputeIntegerHash(
+        static_cast<uint32_t>(reinterpret_cast<uintptr_t>(entry)));
+  }
+  static bool Match(void* entry1, void* entry2) { return entry1 == entry2; }
 
  private:
   HeapGraphEdge* children_arr() {
@@ -573,53 +599,40 @@ class HeapEntry BASE_EMBEDDED {
   HeapGraphEdge** retainers_arr() {
     return reinterpret_cast<HeapGraphEdge**>(children_arr() + children_count_);
   }
+  void CalculateExactRetainedSize();
+  void FindRetainingPaths(CachedHeapGraphPath* prev_path,
+                          List<HeapGraphPath*>* retaining_paths);
   const char* TypeAsString();
 
   unsigned painted_: 2;
   unsigned type_: 3;
-  // The calculated data is stored in HeapSnapshot in HeapEntryCalculatedData
-  // entries. See AddCalculatedData and GetCalculatedData.
-  int calculated_data_index_: 27;
-  int self_size_;
-  int children_count_;
+  int children_count_: 27;
   int retainers_count_;
+  int self_size_;
+  union {
+    int ordered_index_;  // Used during dominator tree building.
+    int retained_size_;  // At that moment, there is no retained size yet.
+  };
+  HeapEntry* dominator_;
   HeapSnapshot* snapshot_;
+  struct Id {
+    uint32_t id1_;
+    uint32_t id2_;
+  } id_;  // This is to avoid extra padding of 64-bit value.
   const char* name_;
-  uint64_t id_;
 
+  // Paints used for exact retained sizes calculation.
   static const unsigned kUnpainted = 0;
   static const unsigned kPainted = 1;
   static const unsigned kPaintedReachableFromOthers = 2;
-  static const int kNoCalculatedData = -1;
-
-  DISALLOW_COPY_AND_ASSIGN(HeapEntry);
-};
-
-
-class HeapEntryCalculatedData {
- public:
-  HeapEntryCalculatedData()
-      : retaining_paths_(NULL),
-        reachable_size_(kUnknownSize),
-        retained_size_(kUnknownSize) {
-  }
-  void Dispose();
-
-  List<HeapGraphPath*>* GetRetainingPaths(HeapEntry* entry);
-  int ReachableSize(HeapEntry* entry);
-  int RetainedSize(HeapEntry* entry);
-
- private:
-  void CalculateSizes(HeapEntry* entry);
-  void FindRetainingPaths(HeapEntry* entry, CachedHeapGraphPath* prev_path);
-
-  List<HeapGraphPath*>* retaining_paths_;
-  int reachable_size_;
-  int retained_size_;
+  // Paints used for approximate retained sizes calculation.
+  static const unsigned kLeaf = 0;
+  static const unsigned kNonLeaf = 1;
+  static const unsigned kProcessed = 2;
 
-  static const int kUnknownSize = -1;
+  static const int kExactRetainedSizeTag = 1;
 
-  // Allow generated copy constructor and assignment operator.
+  DISALLOW_COPY_AND_ASSIGN(HeapEntry);
 };
 
 
@@ -668,24 +681,22 @@ class HeapSnapshot {
   const char* title() { return title_; }
   unsigned uid() { return uid_; }
   HeapEntry* root() { return root_entry_; }
+  HeapEntry* gc_roots() { return gc_roots_entry_; }
 
   void AllocateEntries(
       int entries_count, int children_count, int retainers_count);
   HeapEntry* AddEntry(
       HeapObject* object, int children_count, int retainers_count);
-  bool WillAddEntry(HeapObject* object);
   HeapEntry* AddEntry(HeapEntry::Type type,
                       const char* name,
                       uint64_t id,
                       int size,
                       int children_count,
                       int retainers_count);
-  int AddCalculatedData();
-  HeapEntryCalculatedData& GetCalculatedData(int index) {
-    return calculated_data_[index];
-  }
+  void ApproximateRetainedSizes();
   void ClearPaint();
   HeapSnapshotsDiff* CompareWith(HeapSnapshot* snapshot);
+  List<HeapGraphPath*>* GetRetainingPaths(HeapEntry* entry);
   List<HeapEntry*>* GetSortedEntriesList();
   template<class Visitor>
   void IterateEntries(Visitor* visitor) { entries_.Iterate(visitor); }
@@ -693,7 +704,8 @@ class HeapSnapshot {
   void Print(int max_depth);
   void PrintEntriesSize();
 
-  static HeapObject *const kInternalRootObject;
+  static HeapObject* const kInternalRootObject;
+  static HeapObject* const kGcRootsObject;
 
  private:
   HeapEntry* AddEntry(HeapObject* object,
@@ -702,18 +714,21 @@ class HeapSnapshot {
                       int children_count,
                       int retainers_count);
   HeapEntry* GetNextEntryToInit();
-  static int GetObjectSize(HeapObject* obj);
-  static int CalculateNetworkSize(JSObject* obj);
+  void BuildDominatorTree(const Vector<HeapEntry*>& entries,
+                          Vector<HeapEntry*>* dominators);
+  void FillReversePostorderIndexes(Vector<HeapEntry*>* entries);
+  void SetEntriesDominators();
 
   HeapSnapshotsCollection* collection_;
   Type type_;
   const char* title_;
   unsigned uid_;
   HeapEntry* root_entry_;
+  HeapEntry* gc_roots_entry_;
   char* raw_entries_;
   List<HeapEntry*> entries_;
   bool entries_sorted_;
-  List<HeapEntryCalculatedData> calculated_data_;
+  HashMap retaining_paths_;
 #ifdef DEBUG
   int raw_entries_size_;
 #endif
@@ -733,6 +748,10 @@ class HeapObjectsMap {
   uint64_t FindObject(Address addr);
   void MoveObject(Address from, Address to);
 
+  static const uint64_t kInternalRootObjectId;
+  static const uint64_t kGcRootsObjectId;
+  static const uint64_t kFirstAvailableObjectId;
+
  private:
   struct EntryInfo {
     explicit EntryInfo(uint64_t id) : id(id), accessed(true) { }
@@ -868,9 +887,6 @@ class HeapEntriesMap {
   HeapEntriesMap();
   ~HeapEntriesMap();
 
-  // Aliasing is used for skipping intermediate proxy objects, like
-  // JSGlobalPropertyCell.
-  void Alias(HeapObject* from, HeapObject* to);
   HeapEntry* Map(HeapObject* object);
   void Pair(HeapObject* object, HeapEntry* entry);
   void CountReference(HeapObject* from, HeapObject* to,
@@ -894,41 +910,45 @@ class HeapEntriesMap {
     int retainers_count;
   };
 
-  uint32_t Hash(HeapObject* object) {
+  static uint32_t Hash(HeapObject* object) {
     return ComputeIntegerHash(
         static_cast<uint32_t>(reinterpret_cast<uintptr_t>(object)));
   }
   static bool HeapObjectsMatch(void* key1, void* key2) { return key1 == key2; }
 
-  bool IsAlias(void* ptr) {
-    return reinterpret_cast<intptr_t>(ptr) & kAliasTag;
-  }
-  void* MakeAlias(void* ptr) {
-    return reinterpret_cast<void*>(reinterpret_cast<intptr_t>(ptr) | kAliasTag);
-  }
-  void* Unalias(void* ptr) {
-    return reinterpret_cast<void*>(
-        reinterpret_cast<intptr_t>(ptr) & (~kAliasTag));
-  }
-
   HashMap entries_;
   int entries_count_;
   int total_children_count_;
   int total_retainers_count_;
 
-  static const intptr_t kAliasTag = 1;
+  friend class HeapObjectsSet;
 
   DISALLOW_COPY_AND_ASSIGN(HeapEntriesMap);
 };
 
 
+class HeapObjectsSet {
+ public:
+  HeapObjectsSet();
+  void Clear();
+  bool Contains(Object* object);
+  void Insert(Object* obj);
+
+ private:
+  HashMap entries_;
+
+  DISALLOW_COPY_AND_ASSIGN(HeapObjectsSet);
+};
+
+
 class HeapSnapshotGenerator {
  public:
   class SnapshotFillerInterface {
    public:
     virtual ~SnapshotFillerInterface() { }
     virtual HeapEntry* AddEntry(HeapObject* obj) = 0;
-    virtual void SetElementReference(HeapObject* parent_obj,
+    virtual void SetIndexedReference(HeapGraphEdge::Type type,
+                                     HeapObject* parent_obj,
                                      HeapEntry* parent_entry,
                                      int index,
                                      Object* child_obj,
@@ -939,8 +959,11 @@ class HeapSnapshotGenerator {
                                    const char* reference_name,
                                    Object* child_obj,
                                    HeapEntry* child_entry) = 0;
-    virtual void SetRootReference(Object* child_obj,
-                                  HeapEntry* child_entry) = 0;
+    virtual void SetRootGcRootsReference() = 0;
+    virtual void SetRootShortcutReference(Object* child_obj,
+                                          HeapEntry* child_entry) = 0;
+    virtual void SetStrongRootReference(Object* child_obj,
+                                        HeapEntry* child_entry) = 0;
   };
 
   explicit HeapSnapshotGenerator(HeapSnapshot* snapshot);
@@ -969,19 +992,33 @@ class HeapSnapshotGenerator {
                             HeapEntry* parent,
                             int index,
                             Object* child);
+  void SetHiddenReference(HeapObject* parent_obj,
+                          HeapEntry* parent,
+                          int index,
+                          Object* child);
   void SetPropertyReference(HeapObject* parent_obj,
                             HeapEntry* parent,
                             String* reference_name,
                             Object* child);
-  void SetRootReference(Object* child);
+  void SetPropertyShortcutReference(HeapObject* parent_obj,
+                                    HeapEntry* parent,
+                                    String* reference_name,
+                                    Object* child);
+  void SetRootShortcutReference(Object* child);
+  void SetRootGcRootsReference();
+  void SetGcRootsReference(Object* child);
 
   HeapSnapshot* snapshot_;
   HeapSnapshotsCollection* collection_;
   // Mapping from HeapObject* pointers to HeapEntry* pointers.
   HeapEntriesMap entries_;
   SnapshotFillerInterface* filler_;
+  // Used during references extraction to mark heap objects that
+  // are references via non-hidden properties.
+  HeapObjectsSet known_references_;
 
   friend class IndexedReferencesExtractor;
+  friend class RootsReferencesExtractor;
 
   DISALLOW_COPY_AND_ASSIGN(HeapSnapshotGenerator);
 };