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 161e6542d9a59e32934a18e2b5a739363557f630..3fd3cda73b8f868c9ea47c2908fbc0012985757e 100644
--- a/src/hydrogen-instructions.h
+++ b/src/hydrogen-instructions.h
@@ -58,6 +58,7 @@ class LChunkBuilder;
   V(BitwiseBinaryOperation)                    \
   V(ControlInstruction)                        \
   V(Instruction)                               \
+  V(ArrayInstruction)                          \
 
 
 #define HYDROGEN_CONCRETE_INSTRUCTION_LIST(V)  \
@@ -634,6 +635,12 @@ class HValue: public ZoneObject {
   int id() const { return id_; }
   void set_id(int id) { id_ = id; }
 
+  // For participation in hashmaps
+  uint32_t Hash() {
+    ASSERT(id() != kNoNumber);
+    return id();
+  }
+
   HUseIterator uses() const { return HUseIterator(use_list_); }
 
   virtual bool EmitAtUses() { return false; }
@@ -898,6 +905,7 @@ class HInstruction: public HValue {
   void Unlink();
   void InsertBefore(HInstruction* next);
   void InsertAfter(HInstruction* previous);
+  bool IsDefinedAfterInSameBlock(HValue* other) const;
 
   // The position is a write-once variable.
   int position() const { return position_; }
@@ -2261,6 +2269,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_; }
 
   DECLARE_CONCRETE_INSTRUCTION(CheckMaps)
@@ -4343,77 +4353,98 @@ class HLoadFunctionPrototype: public HUnaryOperation {
   virtual bool DataEquals(HValue* other) { return true; }
 };
 
-class ArrayInstructionInterface {
+
+class HTransitionElementsKind;
+class HArrayInstruction: public HTemplateInstruction<3> {
  public:
-  virtual HValue* GetKey() = 0;
-  virtual void SetKey(HValue* key) = 0;
+  HArrayInstruction(HValue* obj, HValue* key, Zone* zone) :
+        zone_(zone),
+        transitions_(new(zone) ZoneList<HTransitionElementsKind*>(5, zone)),
+        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 ~HArrayInstruction() { };
 
+  void AddTransitions(const ZoneList<HTransitionElementsKind*>&
+                      transition_list);
+  bool hoistable() const { return hoistable_; }
+  void set_hoistable(bool value) { hoistable_ = value; }
 
-class HLoadKeyed
-    : public HTemplateInstruction<3>, public ArrayInstructionInterface {
- public:
-  HLoadKeyed(HValue* obj,
-             HValue* key,
-             HValue* dependency,
-             ElementsKind elements_kind)
-      : 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());
-        }
+  int transitions() const { return transitions_->length(); }
+  HTransitionElementsKind* transition(int index) {
+    return transitions_->at(index);
+  }
 
-        set_representation(Representation::Tagged());
-        SetGVNFlag(kDependsOnArrayElements);
-      } else {
-        set_representation(Representation::Double());
-        SetGVNFlag(kDependsOnDoubleArrayElements);
-      }
-    } else {
-      if (elements_kind == EXTERNAL_FLOAT_ELEMENTS ||
-          elements_kind == EXTERNAL_DOUBLE_ELEMENTS) {
-        set_representation(Representation::Double());
-      } else {
-        set_representation(Representation::Integer32());
-      }
+  Handle<Map> map_family();
 
-      SetGVNFlag(kDependsOnSpecializedArrayElements);
-      // Native code could change the specialized array.
-      SetGVNFlag(kDependsOnCalls);
+  void Finalize(ElementsKind kind) {
+    if (!Initialized()) {
+      PerformDeferredInitialization(kind);
     }
 
-    SetFlag(kUseGVN);
+    // This will detect re-initialization
+    ASSERT(Initialized() && kind == GetElementsKind());
   }
 
+  void Finalize() {
+    if (!Initialized()) {
+      PerformDeferredInitialization();
+    }
+  }
+
+  void PrintElementPlacementTo(StringStream* stream);
+  bool Initialized() const { return initialized_; }
+
+  DECLARE_ABSTRACT_INSTRUCTION(ArrayInstruction)
+
+ protected:
+  void SetInitialized() { initialized_ = true; }
+
+ private:
+  Zone* zone_;
+  ZoneList<HTransitionElementsKind*>* transitions_;
+  bool hoistable_;
+  bool initialized_;
+ };
+
+
+class HLoadKeyed: public HArrayInstruction {
+ public:
+  HLoadKeyed(HValue* obj,
+             HValue* key,
+             HValue* dependency,
+             ElementsKind elements_kind,
+             Zone* zone);
+
+  void PerformDeferredInitialization(ElementsKind new_elements_kind);
+  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);
@@ -4421,8 +4452,13 @@ class HLoadKeyed
   ElementsKind elements_kind() const {
     return ElementsKindField::decode(bit_field_);
   }
+  ElementsKind GetElementsKind() {
+    return elements_kind();
+  }
 
   virtual Representation RequiredInputRepresentation(int index) {
+    ASSERT(Initialized());
+
     // kind_fast:       tagged[int32] (none)
     // kind_double:     tagged[int32] (none)
     // kind_external: external[int32] (none)
@@ -4611,30 +4647,14 @@ class HStoreNamedGeneric: public HTemplateInstruction<3> {
 };
 
 
-class HStoreKeyed
-    : public HTemplateInstruction<3>, public ArrayInstructionInterface {
+class HStoreKeyed: public HArrayInstruction {
  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);
-    SetOperandAt(2, val);
-
-    if (is_external()) {
-      SetGVNFlag(kChangesSpecializedArrayElements);
-    } else if (IsFastDoubleElementsKind(elements_kind)) {
-      SetGVNFlag(kChangesDoubleArrayElements);
-      SetFlag(kDeoptimizeOnUndefined);
-    } else {
-      SetGVNFlag(kChangesArrayElements);
-    }
+              ElementsKind elements_kind, Zone* zone);
 
-    // EXTERNAL_{UNSIGNED_,}{BYTE,SHORT,INT}_ELEMENTS are truncating.
-    if (elements_kind >= EXTERNAL_BYTE_ELEMENTS &&
-        elements_kind <= EXTERNAL_UNSIGNED_INT_ELEMENTS) {
-      SetFlag(kTruncatingToInt32);
-    }
+  void PerformDeferredInitialization(ElementsKind new_elements_kind);
+  void PerformDeferredInitialization() {
+    PerformDeferredInitialization(elements_kind());
   }
 
   virtual Representation RequiredInputRepresentation(int index) {
@@ -4673,17 +4693,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; }
 
@@ -4696,7 +4713,6 @@ class HStoreKeyed
   }
 
   bool NeedsCanonicalization();
-
   virtual void PrintDataTo(StringStream* stream);
 
   DECLARE_CONCRETE_INSTRUCTION(StoreKeyed)
@@ -4747,30 +4763,23 @@ class HTransitionElementsKind: public HTemplateInstruction<1> {
  public:
   HTransitionElementsKind(HValue* object,
                           Handle<Map> original_map,
-                          Handle<Map> transitioned_map)
-      : original_map_(original_map),
-        transitioned_map_(transitioned_map) {
-    SetOperandAt(0, object);
-    SetFlag(kUseGVN);
-    SetGVNFlag(kChangesElementsKind);
-    if (original_map->has_fast_double_elements()) {
-      SetGVNFlag(kChangesElementsPointer);
-      SetGVNFlag(kChangesNewSpacePromotion);
-    }
-    if (transitioned_map->has_fast_double_elements()) {
-      SetGVNFlag(kChangesElementsPointer);
-      SetGVNFlag(kChangesNewSpacePromotion);
-    }
-    set_representation(Representation::Tagged());
-  }
+                          Handle<Map> transitioned_map,
+                          Isolate* isolate,
+                          bool calculatePessimisticHoleyAndFamily = true);
 
   virtual Representation RequiredInputRepresentation(int index) {
     return Representation::Tagged();
   }
 
   HValue* object() { return OperandAt(0); }
-  Handle<Map> original_map() { return original_map_; }
-  Handle<Map> transitioned_map() { return transitioned_map_; }
+
+  Handle<Map> original_map() const { return original_map_; }
+  Handle<Map> transitioned_map() const { return transitioned_map_; }
+  Handle<Map> family() const { return family_; }
+  Handle<Map> pessimistic_holey() const { return pessimistic_holey_; }
+
+  bool is_special_case() const { return special_case_; }
+  void set_special_case() { special_case_ = true; }
 
   virtual void PrintDataTo(StringStream* stream);
 
@@ -4786,6 +4795,9 @@ class HTransitionElementsKind: public HTemplateInstruction<1> {
  private:
   Handle<Map> original_map_;
   Handle<Map> transitioned_map_;
+  Handle<Map> pessimistic_holey_;
+  Handle<Map> family_;
+  bool special_case_;
 };
 
 
@@ -4970,12 +4982,11 @@ class HFastLiteral: public HMaterializedLiteral<1> {
  public:
   HFastLiteral(HValue* context,
                Handle<JSObject> boilerplate,
-               int total_size,
                int literal_index,
                int depth)
       : HMaterializedLiteral<1>(literal_index, depth),
-        boilerplate_(boilerplate),
-        total_size_(total_size) {
+        boilerplate_(boilerplate) {
+    transition_to_ = boilerplate->GetElementsKind();
     SetOperandAt(0, context);
     SetGVNFlag(kChangesNewSpacePromotion);
   }
@@ -4987,18 +4998,32 @@ class HFastLiteral: public HMaterializedLiteral<1> {
 
   HValue* context() { return OperandAt(0); }
   Handle<JSObject> boilerplate() const { return boilerplate_; }
-  int total_size() const { return total_size_; }
 
   virtual Representation RequiredInputRepresentation(int index) {
     return Representation::Tagged();
   }
   virtual HType CalculateInferredType();
 
+  void SetTransitionTo(ElementsKind elements_kind) {
+    transition_to_ = elements_kind;
+  }
+  ElementsKind TransitionTo() { return transition_to_; }
+  bool TransitionRequested() {
+    return transition_to_ != boilerplate()->GetElementsKind();
+  }
+
   DECLARE_CONCRETE_INSTRUCTION(FastLiteral)
 
+  static bool IsFastLiteral(Handle<JSObject> boilerplate,
+                            int max_depth,
+                            int* max_properties,
+                            int* total_size);
+
+  virtual void PrintDataTo(StringStream* stream);
+
  private:
   Handle<JSObject> boilerplate_;
-  int total_size_;
+  ElementsKind transition_to_;
 };