A change in the way we place TransitionElementKinds in the tree.

src/hydrogen-instructions.h

Index: src/hydrogen-instructions.h
diff --git a/src/hydrogen-instructions.h b/src/hydrogen-instructions.h
index 79e4a5dea0b5e0a28d83fa9c2ad5d1471c66a7c6..15f0106a12c4384f88ee1d00b9f3694c35855c0d 100644
--- a/src/hydrogen-instructions.h
+++ b/src/hydrogen-instructions.h
@@ -2258,6 +2258,8 @@ class HCheckMaps: public HTemplateInstruction<2> {
   virtual HType CalculateInferredType();
 
   HValue* value() { return OperandAt(0); }
+  bool HasTypeCheck() const { return OperandAt(0) != OperandAt(1); }
+  void RemoveTypeCheck() { SetOperandAt(1, OperandAt(0)); }
   SmallMapList* map_set() { return &map_set_; }
   CompareMapMode mode() { return mode_; }
 
@@ -4330,50 +4332,126 @@ class HLoadFunctionPrototype: public HUnaryOperation {
   virtual bool DataEquals(HValue* other) { return true; }
 };
 
-class ArrayInstructionInterface {
+
+class HTransitionElementsKind;
+class TransitionElementsBookmark BASE_EMBEDDED {
+ public:
+  TransitionElementsBookmark(HTransitionElementsKind* transition,
+                             Handle<Map> map_from,
+                             Handle<Map> map_to,
+                             Isolate* isolate);
+  ElementsKind elementskind_from() const { return from_->elements_kind(); }
+  ElementsKind elementskind_to() const { return to_->elements_kind(); }
+  Handle<Map> from() const { return from_; }
+  Handle<Map>* from_pointer() { return &from_; }

[danno, 2012/11/28 14:42:10]

I don't think you need this version. Creating a Handle from another handle
doesn't allocate a new location_. So you should always be able to just pass
Handle<Map> around, even when you need to create another Handle<Map> based on
it.

+  Handle<Map> to() const { return to_; }
+  Handle<Map>* to_pointer() { return &to_; }
+  Handle<Map> family() const { return family_; }
+  Handle<Map>* family_pointer() { return &family_; }
+  Handle<Map> pessimistic_holey() const { return pessimistic_holey_; }
+  Handle<Map>* pessimistic_holey_pointer() { return &pessimistic_holey_; }
+  HTransitionElementsKind* transition_instruction() const {
+    return transition_; }
+
+  bool Equals(const TransitionElementsBookmark& other) const {
+    return *from() == *(other.from()) &&
+        *to() == *(other.to()) &&
+        *family() == *(other.family());

[danno, 2012/11/28 14:42:10]

family must be equal if from and to are equal. You could probably make that part
some sort of assert instead.

+  }
+
+ private:
+  HTransitionElementsKind* transition_;

[danno, 2012/11/28 14:42:10]

Here's a radical idea. Since you need to allocate one of these for every
HTransitionElementsKind, why not just add all this functionality to
HTransitionElementsKind itself? You could remove the from_ and to_, since they
are already recorded in the TransitionElementsKind instruction. 

[mvstanton, 2012/12/04 11:39:59]

Done.

+  Handle<Map> from_;
+  Handle<Map> to_;
+  Handle<Map> family_;
+  Handle<Map> pessimistic_holey_;
+};
+
+
+class ArrayInstruction: public HTemplateInstruction<3> {

[danno, 2012/11/28 14:42:10]

Maybe HArrayInstruction, it's more consistent.

[mvstanton, 2012/12/04 11:39:59]

Done.

  public:
-  virtual HValue* GetKey() = 0;
-  virtual void SetKey(HValue* key) = 0;
+  ArrayInstruction(HValue* obj, HValue* key, Zone* zone) :
+        zone_(zone),
+        bookmarks_(new(zone) ZoneList<TransitionElementsBookmark>(10, zone)),

[danno, 2012/11/28 14:42:10]

Maybe TransitionElementsBookmark*, and allocate the bookmarks from the zone when
they're added. Also, 10 seems like a lot, might cause a lot of extra space to be
allocated that is never used.

[mvstanton, 2012/12/04 11:39:59]

Got rid of the Bookmarks entirely.

+        hoistable_(true),
+        initialized_(false) {
+    SetOperandAt(0, obj);
+    SetOperandAt(1, key);
+  }
+  
+  HValue* elements() { return OperandAt(0); }
+  HValue* key() { return OperandAt(1); }
+  
+  HValue* GetKey() { return key(); }
+  void SetKey(HValue* key) { SetOperandAt(1, key); }  
+
+
+  virtual ElementsKind GetElementsKind() = 0;
   virtual void SetIndexOffset(uint32_t index_offset) = 0;
   virtual bool IsDehoisted() = 0;
   virtual void SetDehoisted(bool is_dehoisted) = 0;
-  virtual ~ArrayInstructionInterface() { };
+  virtual void PerformDeferredInitialization(
+      ElementsKind new_elements_kind) = 0;
+  virtual void PerformDeferredInitialization() = 0;
+  virtual ~ArrayInstruction() { };
+  
+  void AddBookmarks(const ZoneList<TransitionElementsBookmark>& records);
+  bool hoistable() const { return hoistable_; }
+  void set_hoistable(bool value) { hoistable_ = value; }
+
+  int bookmarks() const { return bookmarks_->length(); }
+  TransitionElementsBookmark* bookmark(int index) {
+    return &(bookmarks_->at(index));
+  }
+
+  Map* map_family();
+
+  void Finalize(ElementsKind kind) {
+    // ElementsKind elements_kind = most_general_map()->elements_kind();

[danno, 2012/11/28 14:42:10]

Is this comment stale?

[mvstanton, 2012/12/04 11:39:59]

Done.

+    if (!Initialized()) {
+      PerformDeferredInitialization(kind);
+    }
+
+    // This will detect re-initialization
+    ASSERT(Initialized() && kind == GetElementsKind());
+  }
+
+  void Finalize() {
+    // ElementsKind elements_kind = most_general_map()->elements_kind();
+    if (!Initialized()) {
+      PerformDeferredInitialization();
+    }
+  }
+  
+  void PrintElementPlacementTo(StringStream* stream);
+  bool Initialized() const { return initialized_; }
+ protected:
+  void SetInitialized() { initialized_ = true; }
+
+ private:
+  Zone* zone_;
+  ZoneList<TransitionElementsBookmark>* bookmarks_;
+  bool hoistable_;
+  bool initialized_;
 };
 
 
 class HLoadKeyed
-    : public HTemplateInstruction<3>, public ArrayInstructionInterface {
+    : public ArrayInstruction {
  public:
   HLoadKeyed(HValue* obj,
              HValue* key,
              HValue* dependency,
-             ElementsKind elements_kind)
-      : bit_field_(0) {
+             ElementsKind elements_kind,
+             Zone* zone)
+      : ArrayInstruction(obj, key, zone), bit_field_(0) {
     bit_field_ = ElementsKindField::encode(elements_kind);
-
-    SetOperandAt(0, obj);
-    SetOperandAt(1, key);
+    
     SetOperandAt(2, dependency);
 
-    if (!is_external()) {
-      // I can detect the case between storing double (holey and fast) and
-      // smi/object by looking at elements_kind_.
-      ASSERT(IsFastSmiOrObjectElementsKind(elements_kind) ||
-             IsFastDoubleElementsKind(elements_kind));
-
-      if (IsFastSmiOrObjectElementsKind(elements_kind)) {
-        if (IsFastSmiElementsKind(elements_kind) &&
-            IsFastPackedElementsKind(elements_kind)) {
-          set_type(HType::Smi());
-        }
-
-        set_representation(Representation::Tagged());
-        SetGVNFlag(kDependsOnArrayElements);
-      } else {
-        set_representation(Representation::Double());
-        SetGVNFlag(kDependsOnDoubleArrayElements);
-      }
-    } else {
+    if (is_external()) {
+      SetInitialized();
+      
       if (elements_kind == EXTERNAL_FLOAT_ELEMENTS ||
           elements_kind == EXTERNAL_DOUBLE_ELEMENTS) {
         set_representation(Representation::Double());
@@ -4384,23 +4462,61 @@ class HLoadKeyed
       SetGVNFlag(kDependsOnSpecializedArrayElements);
       // Native code could change the specialized array.
       SetGVNFlag(kDependsOnCalls);
-    }
+    } else {
+      ASSERT(IsFastSmiOrObjectElementsKind(elements_kind) ||
+             IsFastDoubleElementsKind(elements_kind));
 
+      // We don't yet know what it depends on yet, so set both flags
+      SetGVNFlag(kDependsOnArrayElements);
+      SetGVNFlag(kDependsOnDoubleArrayElements);
+      if (!FLAG_use_place_elements_transitions) {
+        PerformDeferredInitialization();
+      }
+    }
+    
     SetFlag(kUseGVN);
   }
 
+  void PerformDeferredInitialization(ElementsKind new_elements_kind) {
+    ASSERT(!is_external());    
+    ASSERT(!Initialized());
+    SetInitialized();
+    
+    if (new_elements_kind != elements_kind()) {
+      bit_field_ = ElementsKindField::encode(new_elements_kind);
+    }
+
+    ClearGVNFlag(kDependsOnArrayElements);
+    ClearGVNFlag(kDependsOnDoubleArrayElements);
+
+    if (IsFastSmiOrObjectElementsKind(elements_kind())) {
+      if (IsFastSmiElementsKind(elements_kind()) &&
+          IsFastPackedElementsKind(elements_kind())) {
+        set_type(HType::Smi());
+      }
+
+      set_representation(Representation::Tagged());
+      SetGVNFlag(kDependsOnArrayElements);
+    } else {
+      set_representation(Representation::Double());
+      SetGVNFlag(kDependsOnDoubleArrayElements);
+    }
+  }
+
+  void PerformDeferredInitialization() {
+    PerformDeferredInitialization(elements_kind());
+  }
+  
   bool is_external() const {
     return IsExternalArrayElementsKind(elements_kind());
   }
-  HValue* elements() { return OperandAt(0); }
-  HValue* key() { return OperandAt(1); }
   HValue* dependency() { return OperandAt(2); }
+  ElementsKind GetElementsKind() { return elements_kind(); }
+
   uint32_t index_offset() { return IndexOffsetField::decode(bit_field_); }
   void SetIndexOffset(uint32_t index_offset) {
     bit_field_ = IndexOffsetField::update(bit_field_, index_offset);
   }
-  HValue* GetKey() { return key(); }
-  void SetKey(HValue* key) { SetOperandAt(1, key); }
   bool IsDehoisted() { return IsDehoistedField::decode(bit_field_); }
   void SetDehoisted(bool is_dehoisted) {
     bit_field_ = IsDehoistedField::update(bit_field_, is_dehoisted);
@@ -4410,6 +4526,8 @@ class HLoadKeyed
   }
 
   virtual Representation RequiredInputRepresentation(int index) {
+    ASSERT(Initialized());
+
     // kind_fast:       tagged[int32] (none)
     // kind_double:     tagged[int32] (none)
     // kind_external: external[int32] (none)
@@ -4599,32 +4717,63 @@ class HStoreNamedGeneric: public HTemplateInstruction<3> {
 
 
 class HStoreKeyed
-    : public HTemplateInstruction<3>, public ArrayInstructionInterface {
+    : public ArrayInstruction {
  public:
   HStoreKeyed(HValue* obj, HValue* key, HValue* val,
-              ElementsKind elements_kind)
-      : elements_kind_(elements_kind), index_offset_(0), is_dehoisted_(false) {
-    SetOperandAt(0, obj);
-    SetOperandAt(1, key);
+              ElementsKind elements_kind,
+              Zone* zone)
+      : ArrayInstruction(obj, key, zone),
+      elements_kind_(elements_kind),
+      index_offset_(0),
+      is_dehoisted_(false) {
     SetOperandAt(2, val);
 
     if (is_external()) {
+      SetInitialized();
+      
       SetGVNFlag(kChangesSpecializedArrayElements);
-    } else if (IsFastDoubleElementsKind(elements_kind)) {
+      // EXTERNAL_{UNSIGNED_,}{BYTE,SHORT,INT}_ELEMENTS are truncating.
+      if (elements_kind >= EXTERNAL_BYTE_ELEMENTS &&
+          elements_kind <= EXTERNAL_UNSIGNED_INT_ELEMENTS) {
+        SetFlag(kTruncatingToInt32);
+      }
+    } else {
+      // We don't know what we'll have later.
+      // Initialize for the worst case
       SetGVNFlag(kChangesDoubleArrayElements);
       SetFlag(kDeoptimizeOnUndefined);
-    } else {
       SetGVNFlag(kChangesArrayElements);
+
+      if (!FLAG_use_place_elements_transitions) {
+        PerformDeferredInitialization();
+      }
+    }
+  }
+
+  void PerformDeferredInitialization(ElementsKind new_elements_kind) {
+    ASSERT(!is_external());
+    ASSERT(!Initialized());
+    SetInitialized();
+
+    if (new_elements_kind != elements_kind_) {
+      elements_kind_ = new_elements_kind;
     }
 
-    // EXTERNAL_{UNSIGNED_,}{BYTE,SHORT,INT}_ELEMENTS are truncating.
-    if (elements_kind >= EXTERNAL_BYTE_ELEMENTS &&
-        elements_kind <= EXTERNAL_UNSIGNED_INT_ELEMENTS) {
-      SetFlag(kTruncatingToInt32);
+    // Adjust flags appropriately
+    if (IsFastDoubleElementsKind(elements_kind())) {
+      ClearGVNFlag(kChangesArrayElements);
+    } else {
+      ClearGVNFlag(kChangesDoubleArrayElements);
+      ClearFlag(kDeoptimizeOnUndefined);
     }
   }
 
+  void PerformDeferredInitialization() {
+    PerformDeferredInitialization(elements_kind());
+  }
+
   virtual Representation RequiredInputRepresentation(int index) {
+    ASSERT(Initialized());
     // kind_fast:       tagged[int32] = tagged
     // kind_double:     tagged[int32] = double
     // kind_external: external[int32] = (double | int32)
@@ -4660,17 +4809,14 @@ class HStoreKeyed
     return Representation::None();
   }
 
-  HValue* elements() { return OperandAt(0); }
-  HValue* key() { return OperandAt(1); }
   HValue* value() { return OperandAt(2); }
   bool value_is_smi() const {
     return IsFastSmiElementsKind(elements_kind_);
   }
   ElementsKind elements_kind() const { return elements_kind_; }
+  ElementsKind GetElementsKind() { return elements_kind(); }
   uint32_t index_offset() { return index_offset_; }
   void SetIndexOffset(uint32_t index_offset) { index_offset_ = index_offset; }
-  HValue* GetKey() { return key(); }
-  void SetKey(HValue* key) { SetOperandAt(1, key); }
   bool IsDehoisted() { return is_dehoisted_; }
   void SetDehoisted(bool is_dehoisted) { is_dehoisted_ = is_dehoisted; }
 
@@ -4683,7 +4829,6 @@ class HStoreKeyed
   }
 
   bool NeedsCanonicalization();
-
   virtual void PrintDataTo(StringStream* stream);
 
   DECLARE_CONCRETE_INSTRUCTION(StoreKeyed)