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..1554db15b8b4c8a1669f1d49413a140484ee5875 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,122 @@ 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_; }
+  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());
+  }
+
+ private:
+  HTransitionElementsKind* transition_;
+  Handle<Map> from_;
+  Handle<Map> to_;
+  Handle<Map> family_;
+  Handle<Map> pessimistic_holey_;
+};
+
+
+class ArrayInstruction: public HTemplateInstruction<3> {
  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)),
+        hoistable_(true) {
+    SetOperandAt(0, obj);
+    SetOperandAt(1, key);
+
+#ifdef DEBUG
+    initialized_ = false;
+#endif
+  }
+  
+  HValue* elements() { return OperandAt(0); }
+  HValue* key() { return OperandAt(1); }
+  
+  HValue* GetKey() { return key(); }
+  void SetKey(HValue* key) { SetOperandAt(1, key); }  
+
+#ifdef DEBUG
+  bool Initialized() const { return initialized_; }
+  void SetInitialized() { initialized_ = true; }
+#endif
+  
   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();
+    PerformDeferredInitialization(kind);
+  }
+
+  void Finalize() {
+    // ElementsKind elements_kind = most_general_map()->elements_kind();
+    PerformDeferredInitialization();
+  }
+  
+  void PrintElementPlacementTo(StringStream* stream);
+
+ private:
+  Zone* zone_;
+  ZoneList<TransitionElementsBookmark>* bookmarks_;
+  bool hoistable_;
+#ifdef DEBUG
+  bool initialized_;
+#endif
 };
 
 
 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()) {
       if (elements_kind == EXTERNAL_FLOAT_ELEMENTS ||
           elements_kind == EXTERNAL_DOUBLE_ELEMENTS) {
         set_representation(Representation::Double());
@@ -4384,23 +4458,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);
+    }
+    
     SetFlag(kUseGVN);
+
+    if (!FLAG_use_place_elements_transitions) {
+      PerformDeferredInitialization();
+    }
   }
 
+
+  void PerformDeferredInitialization(ElementsKind new_elements_kind) {
+#ifdef DEBUG
+    ASSERT(!Initialized());
+    SetInitialized();
+#endif
+    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); }
   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 +4522,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 +4713,61 @@ 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()) {
       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);
     }
 
-    // EXTERNAL_{UNSIGNED_,}{BYTE,SHORT,INT}_ELEMENTS are truncating.
-    if (elements_kind >= EXTERNAL_BYTE_ELEMENTS &&
-        elements_kind <= EXTERNAL_UNSIGNED_INT_ELEMENTS) {
-      SetFlag(kTruncatingToInt32);
+    if (!FLAG_use_place_elements_transitions) {
+      PerformDeferredInitialization();
+    }
+  }
+
+  void PerformDeferredInitialization(ElementsKind new_elements_kind) {
+#ifdef DEBUG
+    ASSERT(!Initialized());
+    SetInitialized();
+#endif
+    if (new_elements_kind != elements_kind_) {
+      elements_kind_ = new_elements_kind;
+    }
+
+    // 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,8 +4803,6 @@ 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_);
@@ -4669,8 +4810,6 @@ class HStoreKeyed
   ElementsKind elements_kind() const { 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 +4822,6 @@ class HStoreKeyed
   }
 
   bool NeedsCanonicalization();
-
   virtual void PrintDataTo(StringStream* stream);
 
   DECLARE_CONCRETE_INSTRUCTION(StoreKeyed)