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

src/hydrogen-instructions.h

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 40 matching lines @@
 class HValue;
 class LInstruction;
 class LChunkBuilder;
 
 
 #define HYDROGEN_ABSTRACT_INSTRUCTION_LIST(V)  \
   V(BinaryOperation)                           \
   V(BitwiseBinaryOperation)                    \
   V(ControlInstruction)                        \
   V(Instruction)                               \
+  V(ArrayInstruction)                          \
 
 
 #define HYDROGEN_CONCRETE_INSTRUCTION_LIST(V)  \
   V(AbnormalExit)                              \
   V(AccessArgumentsAt)                         \
   V(Add)                                       \
   V(AllocateObject)                            \
   V(ApplyArguments)                            \
   V(ArgumentsElements)                         \
   V(ArgumentsLength)                           \
@@ skipping 556 matching lines @@
              flags_(0) {}
   virtual ~HValue() {}
 
   HBasicBlock* block() const { return block_; }
   void SetBlock(HBasicBlock* block);
   int LoopWeight() const;
 
   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; }
   Representation representation() const { return representation_; }
   void ChangeRepresentation(Representation r) {
     ASSERT(CheckFlag(kFlexibleRepresentation));
     RepresentationChanged(r);
     representation_ = r;
     if (r.IsTagged()) {
       // Tagged is the bottom of the lattice, don't go any further.
@@ skipping 244 matching lines @@
   HInstruction* next() const { return next_; }
   HInstruction* previous() const { return previous_; }
 
   virtual void PrintTo(StringStream* stream);
   virtual void PrintDataTo(StringStream* stream) { }
 
   bool IsLinked() const { return block() != NULL; }
   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_; }
   bool has_position() const { return position_ != RelocInfo::kNoPosition; }
   void set_position(int position) {
     ASSERT(!has_position());
     ASSERT(position != RelocInfo::kNoPosition);
     position_ = position;
   }
 
@@ skipping 1343 matching lines @@
   }
 
   virtual Representation RequiredInputRepresentation(int index) {
     return Representation::Tagged();
   }
 
   virtual void PrintDataTo(StringStream* stream);
   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)
 
  protected:
   virtual bool DataEquals(HValue* other) {
     HCheckMaps* b = HCheckMaps::cast(other);
     // Relies on the fact that map_set has been sorted before.
     if (map_set()->length() != b->map_set()->length()) return false;
     for (int i = 0; i < map_set()->length(); i++) {
@@ skipping 2062 matching lines @@
   virtual Representation RequiredInputRepresentation(int index) {
     return Representation::Tagged();
   }
 
   DECLARE_CONCRETE_INSTRUCTION(LoadFunctionPrototype)
 
  protected:
   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; }
+
+  int transitions() const { return transitions_->length(); }
+  HTransitionElementsKind* transition(int index) {
+    return transitions_->at(index);
+  }
+
+  Handle<Map> map_family();
+
+  void Finalize(ElementsKind kind) {
+    if (!Initialized()) {
+      PerformDeferredInitialization(kind);
+    }
+
+    // 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 HTemplateInstruction<3>, public ArrayInstructionInterface {
+class HLoadKeyed: public HArrayInstruction {
  public:
   HLoadKeyed(HValue* obj,
              HValue* key,
              HValue* dependency,
-             ElementsKind elements_kind)
-      : bit_field_(0) {
-    bit_field_ = ElementsKindField::encode(elements_kind);
+             ElementsKind elements_kind,
+             Zone* zone);
 
-    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 (elements_kind == EXTERNAL_FLOAT_ELEMENTS ||
-          elements_kind == EXTERNAL_DOUBLE_ELEMENTS) {
-        set_representation(Representation::Double());
-      } else {
-        set_representation(Representation::Integer32());
-      }
-
-      SetGVNFlag(kDependsOnSpecializedArrayElements);
-      // Native code could change the specialized array.
-      SetGVNFlag(kDependsOnCalls);
-    }
-
-    SetFlag(kUseGVN);
+  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);
   }
   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)
     if (index == 0) {
       return is_external() ? Representation::External()
           : Representation::Tagged();
     }
     if (index == 1) return Representation::Integer32();
     return Representation::None();
   }
@@ skipping 168 matching lines @@
   }
 
   DECLARE_CONCRETE_INSTRUCTION(StoreNamedGeneric)
 
  private:
   Handle<String> name_;
   StrictModeFlag strict_mode_flag_;
 };
 
 
-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);
+              ElementsKind elements_kind, Zone* zone);
 
-    if (is_external()) {
-      SetGVNFlag(kChangesSpecializedArrayElements);
-    } else if (IsFastDoubleElementsKind(elements_kind)) {
-      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);
-    }
+  void PerformDeferredInitialization(ElementsKind new_elements_kind);
+  void PerformDeferredInitialization() {
+    PerformDeferredInitialization(elements_kind());
   }
 
   virtual Representation RequiredInputRepresentation(int index) {
     // kind_fast:       tagged[int32] = tagged
     // kind_double:     tagged[int32] = double
     // kind_external: external[int32] = (double | int32)
     if (index == 0) {
       return is_external() ? Representation::External()
                            : Representation::Tagged();
     } else if (index == 1) {
@@ skipping 18 matching lines @@
     if (IsDoubleOrFloatElementsKind(elements_kind())) {
       return Representation::Double();
     }
     if (is_external()) {
       return Representation::Integer32();
     }
     // For fast object elements kinds, don't assume anything.
     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; }
 
   bool NeedsWriteBarrier() {
     if (value_is_smi()) {
       return false;
     } else {
       return StoringValueNeedsWriteBarrier(value());
     }
   }
 
   bool NeedsCanonicalization();
-
   virtual void PrintDataTo(StringStream* stream);
 
   DECLARE_CONCRETE_INSTRUCTION(StoreKeyed)
 
  private:
   ElementsKind elements_kind_;
   uint32_t index_offset_;
   bool is_dehoisted_;
 };
 
@@ skipping 30 matching lines @@
 
  private:
   StrictModeFlag strict_mode_flag_;
 };
 
 
 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);
 
   DECLARE_CONCRETE_INSTRUCTION(TransitionElementsKind)
 
  protected:
   virtual bool DataEquals(HValue* other) {
     HTransitionElementsKind* instr = HTransitionElementsKind::cast(other);
     return original_map_.is_identical_to(instr->original_map()) &&
         transitioned_map_.is_identical_to(instr->transitioned_map());
   }
 
  private:
   Handle<Map> original_map_;
   Handle<Map> transitioned_map_;
+  Handle<Map> pessimistic_holey_;
+  Handle<Map> family_;
+  bool special_case_;
 };
 
 
 class HStringAdd: public HBinaryOperation {
  public:
   HStringAdd(HValue* context, HValue* left, HValue* right)
       : HBinaryOperation(context, left, right) {
     set_representation(Representation::Tagged());
     SetFlag(kUseGVN);
     SetGVNFlag(kDependsOnMaps);
@@ skipping 164 matching lines @@
 
   int literal_index_;
   int depth_;
 };
 
 
 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);
   }
 
   // Maximum depth and total number of elements and properties for literal
   // graphs to be considered for fast deep-copying.
   static const int kMaxLiteralDepth = 3;
   static const int kMaxLiteralProperties = 8;
 
   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_;
 };
 
 
 class HArrayLiteral: public HMaterializedLiteral<1> {
  public:
   HArrayLiteral(HValue* context,
                 Handle<HeapObject> boilerplate_object,
                 int length,
                 int literal_index,
                 int depth)
@@ skipping 418 matching lines @@
   virtual bool IsDeletable() const { return true; }
 };
 
 
 #undef DECLARE_INSTRUCTION
 #undef DECLARE_CONCRETE_INSTRUCTION
 
 } }  // namespace v8::internal
 
 #endif  // V8_HYDROGEN_INSTRUCTIONS_H_