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

src/hydrogen-instructions.cc

Index: src/hydrogen-instructions.cc
diff --git a/src/hydrogen-instructions.cc b/src/hydrogen-instructions.cc
index 0e6ea00058f299ab0966d2e5055e1a70f6da9858..7a24e1cfbe44295d44eafa192294e7a4fcae17c4 100644
--- a/src/hydrogen-instructions.cc
+++ b/src/hydrogen-instructions.cc
@@ -633,6 +633,23 @@ void HInstruction::PrintMnemonicTo(StringStream* stream) {
 }
 
 
+bool HInstruction::IsDefinedAfterInSameBlock(HValue* other) const {
+  // Is the current instruction defined after other and in
+  // the same block?
+  if (block() != other->block()) {
+    return false;
+  }
+
+  HInstruction* cur = previous();
+  while (cur != NULL) {
+    if (cur == other) break;
+    cur = cur->previous();
+  }
+
+  return cur == other;
+}
+
+
 void HInstruction::Unlink() {
   ASSERT(IsLinked());
   ASSERT(!IsControlInstruction());  // Must never move control instructions.
@@ -708,13 +725,8 @@ void HInstruction::Verify() {
     HBasicBlock* other_block = other_operand->block();
     if (cur_block == other_block) {
       if (!other_operand->IsPhi()) {
-        HInstruction* cur = this->previous();
-        while (cur != NULL) {
-          if (cur == other_operand) break;
-          cur = cur->previous();
-        }
-        // Must reach other operand in the same block!
-        ASSERT(cur == other_operand);
+        // We must be defined after other operand in the same block!
+        ASSERT(IsDefinedAfterInSameBlock(other_operand));
       }
     } else {
       // If the following assert fires, you may have forgotten an
@@ -827,6 +839,14 @@ void HUnaryControlInstruction::PrintDataTo(StringStream* stream) {
 }
 
 
+void HFastLiteral::PrintDataTo(StringStream* stream) {
+  if (TransitionRequested()) {
+    stream->Add(" (Transition to %s requested)",
+                ElementsKindToString(TransitionTo()));
+  }
+}
+
+
 void HIsNilAndBranch::PrintDataTo(StringStream* stream) {
   value()->PrintNameTo(stream);
   stream->Add(kind() == kStrictEquality ? " === " : " == ");
@@ -1773,6 +1793,71 @@ Range* HShl::InferRange(Zone* zone) {
 }
 
 
+HLoadKeyed::HLoadKeyed(HValue* obj,
+                       HValue* key,
+                       HValue* dependency,
+                       ElementsKind elements_kind,
+                       Zone* zone)
+    : HArrayInstruction(obj, key, zone), bit_field_(0) {
+  bit_field_ = ElementsKindField::encode(elements_kind);
+  SetOperandAt(2, dependency);
+
+  if (is_external()) {
+    SetInitialized();
+
+    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);
+  } 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 HLoadKeyed::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);
+  }
+}
+
+
 Range* HLoadKeyed::InferRange(Zone* zone) {
   switch (elements_kind()) {
     case EXTERNAL_PIXEL_ELEMENTS:
@@ -2082,7 +2167,8 @@ HValue* HLoadKeyedGeneric::Canonicalize() {
             index_cache,
             key_load->key(),
             key_load->key(),
-            key_load->elements_kind());
+            key_load->elements_kind(),
+            block()->zone());
         map_check->InsertBefore(this);
         index->InsertBefore(this);
         HLoadFieldByIndex* load = new(block()->zone()) HLoadFieldByIndex(
@@ -2445,6 +2531,120 @@ HValue* HAdd::EnsureAndPropagateNotMinusZero(BitVector* visited) {
 }
 
 
+// Determines whether the given array or object literal boilerplate satisfies
+// all limits to be considered for fast deep-copying and computes the total
+// size of all objects that are part of the graph.
+bool HFastLiteral::IsFastLiteral(Handle<JSObject> boilerplate,
+                                 int max_depth,
+                                 int* max_properties,
+                                 int* total_size) {
+  ASSERT(max_depth >= 0 && *max_properties >= 0);
+  if (max_depth == 0) return false;
+
+  Handle<FixedArrayBase> elements(boilerplate->elements());
+  if (elements->length() > 0 &&
+      elements->map() != boilerplate->GetHeap()->fixed_cow_array_map()) {
+    if (boilerplate->HasFastDoubleElements()) {
+      *total_size += FixedDoubleArray::SizeFor(elements->length());
+    } else if (boilerplate->HasFastObjectElements()) {
+      Handle<FixedArray> fast_elements = Handle<FixedArray>::cast(elements);
+      int length = elements->length();
+      for (int i = 0; i < length; i++) {
+        if ((*max_properties)-- == 0) return false;
+        Handle<Object> value(fast_elements->get(i));
+        if (value->IsJSObject()) {
+          Handle<JSObject> value_object = Handle<JSObject>::cast(value);
+          if (!IsFastLiteral(value_object,
+                             max_depth - 1,
+                             max_properties,
+                             total_size)) {
+            return false;
+          }
+        }
+      }
+      *total_size += FixedArray::SizeFor(length);
+    } else {
+      return false;
+    }
+  }
+
+  Handle<FixedArray> properties(boilerplate->properties());
+  if (properties->length() > 0) {
+    return false;
+  } else {
+    int nof = boilerplate->map()->inobject_properties();
+    for (int i = 0; i < nof; i++) {
+      if ((*max_properties)-- == 0) return false;
+      Handle<Object> value(boilerplate->InObjectPropertyAt(i));
+      if (value->IsJSObject()) {
+        Handle<JSObject> value_object = Handle<JSObject>::cast(value);
+        if (!IsFastLiteral(value_object,
+                           max_depth - 1,
+                           max_properties,
+                           total_size)) {
+          return false;
+        }
+      }
+    }
+  }
+
+  *total_size += boilerplate->map()->instance_size();
+  return true;
+}
+
+
+HStoreKeyed::HStoreKeyed(HValue* obj, HValue* key, HValue* val,
+                         ElementsKind elements_kind,
+                         Zone* zone)
+    : HArrayInstruction(obj, key, zone),
+      elements_kind_(elements_kind),
+      index_offset_(0),
+      is_dehoisted_(false) {
+  SetOperandAt(2, val);
+
+  if (is_external()) {
+    SetInitialized();
+
+    SetGVNFlag(kChangesSpecializedArrayElements);
+    // 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);
+    SetGVNFlag(kChangesArrayElements);
+
+    if (!FLAG_use_place_elements_transitions) {
+      PerformDeferredInitialization();
+    }
+  }
+}
+
+
+void HStoreKeyed::PerformDeferredInitialization(
+    ElementsKind new_elements_kind) {
+  ASSERT(!is_external());
+  ASSERT(!Initialized());
+  SetInitialized();
+
+  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);
+  }
+}
+
+
 bool HStoreKeyed::NeedsCanonicalization() {
   // If value is an integer or comes from the result of a keyed load
   // then it will be a non-hole value: no need for canonicalization.
@@ -2739,6 +2939,143 @@ Representation HPhi::RepresentationFromUseRequirements() {
 }
 
 
+HTransitionElementsKind::HTransitionElementsKind(HValue* object,
+                                        Handle<Map> original_map,
+                                        Handle<Map> transitioned_map,
+                                        Isolate* isolate,
+                                        bool calculatePessimisticHoleyAndFamily)
+
+    : original_map_(original_map),
+      transitioned_map_(transitioned_map),
+      pessimistic_holey_(Handle<Map>::null()),
+      family_(Handle<Map>::null()),
+      special_case_(false) {
+  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());
+
+  if (calculatePessimisticHoleyAndFamily) {
+    Handle<Map> map_to = transitioned_map_;
+
+    // When transition records are created, we have the chance to create map
+    // transitions we might need later. Transitions are unified during
+    // optimization, and we may need to transition from a packed fastmap to a
+    // holey version of same. But we can't create those transitions during
+    // optimization. Do it now, recognizing that when the handle disappears
+    // these maps may be collected if they didn't make it into usage in the
+    // optimized graph.
+    if (pessimistic_holey_.is_null()) {
+      if (IsFastPackedElementsKind(map_to->elements_kind())) {
+        ElementsKind holey_kind = GetHoleyElementsKind(map_to->elements_kind());
+        // The transition might already exist
+        Handle<Map> holey_map_handle(FindClosestElementsTransition(*map_to,
+                                                                   holey_kind));
+        ASSERT(!holey_map_handle.is_null());
+        if (holey_map_handle->elements_kind() != holey_kind) {
+          MaybeObject* holey_map = map_to->AddMissingElementsTransitions(
+              holey_kind);
+          holey_map->ToHandle<Map>(&pessimistic_holey_, isolate);
+        } else {
+          pessimistic_holey_ = holey_map_handle;
+        }
+      } else {
+        pessimistic_holey_ = map_to;
+      }
+    }
+
+    if (family_.is_null()) {
+      // fill in map_family_
+      // Walk up to the base map from the map_to();
+      Handle<Map> end_map(FindClosestElementsTransition(*map_to,
+                                                  TERMINAL_FAST_ELEMENTS_KIND));
+      ASSERT(!end_map.is_null());
+      family_ = end_map;
+    }
+
+    ASSERT(!pessimistic_holey_.is_null());
+    ASSERT(!family_.is_null());
+  }
+}
+
+void HArrayInstruction::PrintElementPlacementTo(StringStream* stream) {
+  stream->Add("SITE: block%d %d: ", block()->block_id(),
+              id());
+  PrintTo(stream);
+  stream->Add("\n");
+
+  stream->Add("  HOISTABLE: %s\n", hoistable() ? "true" : "false");
+  stream->Add("  ELEMENTS_KIND: %s\n", ElementsKindToString(GetElementsKind()));
+
+  // Print score
+  // stream->Add("  SCORE: (+%d,%d,-%d)\n", score_[0], score_[1], score_[2]);
+
+  // Find the def point for the instruction
+  HValue *element = elements();
+  ASSERT(element != NULL);
+  // Now get the item from the elements
+  ASSERT(element->IsLoadElements());
+  HValue *elements_value = HLoadElements::cast(element)->value();
+  stream->Add("  OBJECT: ");
+  elements_value->PrintNameTo(stream);
+  stream->Add("  ");
+  elements_value->PrintTo(stream);
+  stream->Add(" %s\n", elements_value->IsPhi() ? "PHI" : "");
+  stream->Add("  TRANSITIONS:\n");
+  ElementsKind transitionElementsKind = FAST_SMI_ELEMENTS;
+  for (int i = 0; i < transitions(); i++) {
+    HTransitionElementsKind* b = transition(i);
+    stream->Add("    %s", ElementsKindToString(
+        b->original_map()->elements_kind()));
+    stream->Add("(0x%p)-> ", *(b->original_map()));
+    transitionElementsKind = b->transitioned_map()->elements_kind();
+    stream->Add("%s", ElementsKindToString(transitionElementsKind));
+    stream->Add("(0x%p)\n", *(b->transitioned_map()));
+  }
+}
+
+
+void HArrayInstruction::AddTransitions(const ZoneList<HTransitionElementsKind*>&
+                                      transition_list) {
+  ASSERT(transition_list.length() > 0);
+#ifdef DEBUG
+  Map* first_to_map = *(transition_list[0]->transitioned_map());
+#endif
+
+  // Doesn't check for duplicates.
+  // The "to" map values should be the same for the whole group
+  for (int i = 0; i < transition_list.length(); i++) {
+    transitions_->Add(transition_list[i], zone_);
+    ASSERT(first_to_map ==
+           *(transition_list[i]->transitioned_map()));
+  }
+}
+
+
+Handle<Map> HArrayInstruction::map_family() {
+  Handle<Map> family = Handle<Map>::null();
+  if (transitions()) {
+    family = transition(0)->family();
+  }
+
+#ifdef DEBUG
+  for (int i = 1; i < transitions(); i++) {
+    HTransitionElementsKind* tr = transition(i);
+    ASSERT(*(tr->family()) == *family);
+  }
+#endif
+  return family;
+}
+
+
 // Node-specific verification code is only included in debug mode.
 #ifdef DEBUG