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

src/hydrogen.cc

Index: src/hydrogen.cc
diff --git a/src/hydrogen.cc b/src/hydrogen.cc
index da69d79260759d7c5c5bffab557fa4c04b937173..1c242ae3ac0d49753e202f0c20c008b9841f7958 100644
--- a/src/hydrogen.cc
+++ b/src/hydrogen.cc
@@ -698,6 +698,7 @@ HGraph::HGraph(CompilationInfo* info)
       values_(16, info->zone()),
       phi_list_(NULL),
       uint32_instructions_(NULL),
+      marked_transitions_(10, info->zone()),
       info_(info),
       zone_(info->zone()),
       is_recursive_(false),
@@ -2449,6 +2450,711 @@ void HGraph::InitializeInferredTypes(int from_inclusive, int to_inclusive) {
 }
 
 
+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_;
+};
+
+
+typedef ZoneList<HInstruction*> TransitionInputList;
+
+class MarkedTransitionElementsGroup: public ZoneObject {
+ public:
+  MarkedTransitionElementsGroup(HInstruction* load_or_store,
+                      HCheckNonSmi* check_non_smi,
+                      HCheckMaps* check_maps, Zone* zone)
+      : zone_(zone),
+      load_or_store_(load_or_store),
+      smi_check_(check_non_smi),
+      map_check_(check_maps),
+      hoistable_(true),
+      bookmarks_(new(zone) ZoneList<TransitionElementsBookmark>(10, zone)),
+      transition_inputs_(new(zone) TransitionInputList(10, zone)) {
+    ASSERT((load_or_store->IsLoadKeyed() &&
+            !HLoadKeyed::cast(load_or_store)->Initialized()) ||
+           (load_or_store->IsStoreKeyed() &&
+            !HStoreKeyed::cast(load_or_store)->Initialized()));
+    score_[0] = score_[1] = score_[2] = 0;
+  }
+
+  HInstruction* load_or_store() const { return load_or_store_; }
+  HCheckMaps* map_check() { return map_check_; }
+  HCheckNonSmi* smi_check() { return smi_check_; }
+
+  void AddBookmarks(const ZoneList<TransitionElementsBookmark>& records);
+
+  int bookmarks() const { return bookmarks_->length(); }
+  const TransitionElementsBookmark& bookmark(int index) const {
+    return (*bookmarks_)[index];
+  }
+
+  TransitionElementsBookmark* bookmark_pointer(int index) {
+    return &(bookmarks_->at(index));
+  }
+
+  void PrintTo(StringStream* stream) const;
+  void PrintToStd() const;
+
+  // This must be called before querying transition input values
+  void ComputeTransitionInputValues(int maximumGraphValueID);
+
+  int transition_inputs() const { return transition_inputs_->length(); }
+  HInstruction* transition_input(int index) const {
+    return (*transition_inputs_)[index]; }
+
+  enum ScoreType {
+    SCORE_POSITIVE,
+    SCORE_NEGATIVE,
+    SCORE_NEUTRAL,
+    SCORE_TYPE_COUNT
+  };
+
+  ScoreType scoretype_from_loopdelta(int loopDelta) const {
+    if (loopDelta > 0) return SCORE_POSITIVE;
+    else if (loopDelta < 0) return SCORE_NEGATIVE;
+    return SCORE_NEUTRAL;
+  }
+
+  int score(ScoreType type) const { return score_[type]; }
+  void increment_score(ScoreType type, int score) { score_[type] += score; }
+
+  bool hoistable() const { return hoistable_; }
+  void set_hoistable(bool value) { hoistable_ = value; }
+
+  void set_most_general_map(Map* new_most_general_map) {
+    computed_most_general_map_ = new_most_general_map; }
+  Map* most_general_map() const { return computed_most_general_map_; }
+
+  void Finalize() {
+    ASSERT(most_general_map() != NULL);
+    ElementsKind elements_kind = most_general_map()->elements_kind();
+    // We have to cast to array instruction very carefully here.
+    // A simple reinterpret cast will produce errors at runtime.
+    ArrayInstructionInterface* array_instruction = NULL;
+    if (load_or_store()->IsLoadKeyed()) {
+      array_instruction = static_cast<ArrayInstructionInterface*>(
+          HLoadKeyed::cast(load_or_store()));
+    } else if (load_or_store()->IsStoreKeyed()) {
+      array_instruction = static_cast<ArrayInstructionInterface*>(
+          HStoreKeyed::cast(load_or_store()));
+    }
+    ASSERT(array_instruction != NULL);
+    array_instruction->PerformDeferredInitialization(elements_kind);
+  }
+
+  Zone* zone() const { return zone_; }
+
+  Map* map_family() const {
+    Map* family = NULL;
+    if (bookmarks()) {
+      family = *(bookmark(0).family().location());
+    }
+
+#ifdef DEBUG
+    for (int i = 1; i < bookmarks(); i++) {
+      const TransitionElementsBookmark& tr = bookmark(i);
+      ASSERT(*(tr.family().location()) == family);
+    }
+#endif
+    return family;
+  }
+
+ private:
+  Zone* zone_;
+  HInstruction* load_or_store_;
+  HCheckNonSmi* smi_check_;
+  HCheckMaps* map_check_;
+  Map* computed_most_general_map_;
+  int score_[SCORE_TYPE_COUNT];
+  bool hoistable_;
+  ZoneList<TransitionElementsBookmark>* bookmarks_;
+  TransitionInputList* transition_inputs_;
+};
+
+
+typedef ZoneList<MarkedTransitionElementsGroup*>
+MarkedTransitionElementsGroupList;
+typedef EnumSet<ElementsKind> ElementsKindSet;
+
+
+class MostGeneralMapAndFamily {
+ public:
+  MostGeneralMapAndFamily() : most_general_map_(NULL), family_(NULL) { }
+  MostGeneralMapAndFamily(const MostGeneralMapAndFamily& h)
+      : most_general_map_(h.most_general_map()),
+        family_(h.family()) {
+  }
+
+  Map* most_general_map() const { return most_general_map_; }
+  Map* family() const { return family_; }
+
+  void Update(Map* new_most_general_map, Map* new_family) {
+    if (is_valid()) {
+      // family shouldn't be changed
+      ASSERT(new_family == family_);
+      most_general_map_ = new_most_general_map;
+    } else {
+      most_general_map_ = new_most_general_map;
+      family_ = new_family;
+    }
+  }
+
+  void invalidate() {
+    most_general_map_ = NULL;
+    family_ = NULL;
+  }
+
+  bool is_valid() const {
+    return most_general_map_ != NULL && family_ != NULL; }
+  bool Equals(const MostGeneralMapAndFamily& h) const {
+    if (!is_valid() || !h.is_valid()) {
+      return is_valid() == h.is_valid();
+    }
+    return most_general_map_ == h.most_general_map() && family_ == h.family();
+  }
+
+  MostGeneralMapAndFamily& operator=(const MostGeneralMapAndFamily& h) {
+    if (this != &h) {
+      most_general_map_ = h.most_general_map();
+      family_ = h.family();
+    }
+    return *this;
+  }
+
+ private:
+  Map* most_general_map_;
+  Map* family_;
+};
+
+
+class TransitionInputDictionaryValue: public ZoneObject {
+ public:
+  TransitionInputDictionaryValue(HInstruction* transition_input, Zone* zone) :
+      transition_input_(transition_input),
+      groups_(new(zone) MarkedTransitionElementsGroupList(10, zone)),
+      zone_(zone),
+      last_in_chain_(NULL) {
+  }
+
+  void AddGroup(MarkedTransitionElementsGroup* group) {
+    if (group->transition_inputs() == 1) {
+      // put at the front of the list. Processing single element
+      // transitions first makes score calculation easier.
+      groups_->InsertAt(0, group, zone_);
+    } else {
+      groups_->Add(group, zone_);
+    }
+  }
+
+  const MostGeneralMapAndFamily& most_general() { return most_general_; }
+  void set_most_general(const MostGeneralMapAndFamily& m) { most_general_ = m; }
+
+  int groups() const { return groups_->length(); }
+  MarkedTransitionElementsGroup* group(int i) { return (*groups_)[i]; }
+  Zone* zone() { return zone_; }
+
+  void ComputeMostGeneralMapAndFamily(MostGeneralMapAndFamily* most_general,
+                            MarkedTransitionElementsGroup** other_family_group);
+
+  // For instruction emission
+  bool RequiresTransitionElementsKind(ElementsKind from) const {
+    return !from_elements_.Contains(from);
+  }
+
+  void InsertTransitionElementsKind(Handle<Map> from, Handle<Map> to) {
+    ASSERT(RequiresTransitionElementsKind(from->elements_kind()));
+    // At the site, we maintain a most recent instruction we added, and
+    // new instructions should appear at the end of the chain.
+    HInstruction* addafter = last_in_chain_;
+    if (addafter == NULL) {
+      // This is the first instruction to add.
+      // We must emit a checknonsmi
+      addafter = new(zone()) HCheckNonSmi(transition_input_);
+      addafter->InsertAfter(transition_input_);
+    }
+
+    HTransitionElementsKind* transition = NULL;
+    if (last_in_chain_ == NULL) {
+      transition = new(zone()) HTransitionElementsKind(transition_input_, from,
+                                                       to);
+      transition->InsertAfter(addafter);
+
+      // Careful tree surgery
+      for (HUseIterator it(transition_input_->uses()); !it.Done();
+           it.Advance()) {
+        HValue* use = it.value();
+        if (use != HValue::cast(addafter) &&
+            use != HValue::cast(transition)) {
+          CarefullyReplaceOperand(&it, transition);
+        }
+      }
+    } else {
+      transition = new(zone()) HTransitionElementsKind(last_in_chain_, from,
+                                                       to);
+      transition->InsertAfter(last_in_chain_);
+
+      // Careful tree surgery
+      for (HUseIterator it(last_in_chain_->uses()); !it.Done();
+           it.Advance()) {
+        HValue* use = it.value();
+        if (use != HValue::cast(transition)) {
+          CarefullyReplaceOperand(&it, transition);
+        }
+      }
+    }
+
+    last_in_chain_ = transition;
+    from_elements_.Add(from->elements_kind());
+  }
+
+  HInstruction* transition_input() const { return transition_input_; }
+
+ private:
+  void CarefullyReplaceOperand(HUseIterator* it, HInstruction* with) {
+    HValue* use = it->value();
+    if (!use->block()->IsStartBlock()) {

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

More comments?

+      if (!use->IsSimulate() || use->block() != with->block()) {
+        use->SetOperandAt(it->index(), with);
+      } else {
+        // Because of the way our new transition elements can be placed at the
+        // start of a block, but ONLY AFTER any simulate instruction, we can
+        // only replace usages of the with instruction if we are sure our new
+        // instruction is defined in the block somewhere before the simulate.
+        HInstruction* cur = HInstruction::cast(use)->previous();
+        while (cur != NULL) {
+          if (cur == with) break;
+          cur = cur->previous();
+        }
+        if (cur == with) {
+          // We can safely do the replacement
+          use->SetOperandAt(it->index(), with);
+        }
+      }
+    }
+  }
+
+  HInstruction* transition_input_;
+  MarkedTransitionElementsGroupList* groups_;
+  Zone* zone_;
+  MostGeneralMapAndFamily most_general_;
+  ElementsKindSet from_elements_;
+  HTransitionElementsKind* last_in_chain_;
+};
+
+
+
+class MapHandleMap BASE_EMBEDDED {
+ public:
+  explicit MapHandleMap(Zone* zone) :
+      map_(MapPointerMatch, ZoneAllocationPolicy(zone)),
+      zone_(zone),
+      null_handle_(Handle<Map>::null()) {
+  }
+
+  Handle<Map>& Lookup(Map* map) {
+    MapHandleTable::Iterator i = map_.find(map, false,
+                                           ZoneAllocationPolicy(zone_));
+    if (i != map_.end()) {
+      return *(i->second);
+    }
+
+    return null_handle_;
+  }
+
+  void Populate(ZoneList<MarkedTransitionElementsGroup*>* groups) {
+    for (int i = 0; i < groups->length(); i++) {
+      MarkedTransitionElementsGroup* group = groups->at(i);
+      for (int r = 0; r < group->bookmarks(); r++) {
+        Add(group->bookmark_pointer(r));
+      }
+    }
+  }
+
+ private:
+  static bool MapPointerMatch(void* key1, void* key2) {
+    return key1 == key2;
+  }
+
+  void Add(TransitionElementsBookmark* record) {
+    InsertIfMissing(record->from_pointer());
+    InsertIfMissing(record->to_pointer());
+    InsertIfMissing(record->family_pointer());
+    InsertIfMissing(record->pessimistic_holey_pointer());
+  }
+
+  void Insert(Handle<Map>* handle) {
+    MapHandleTable::Iterator i = map_.find(*(handle->location()), true,
+                                           ZoneAllocationPolicy(zone_));
+    ASSERT(i != map_.end());
+    i->second = handle;
+  }
+
+  void InsertIfMissing(Handle<Map>* handle) {
+    if (Lookup(*(handle->location())).is_null()) {
+      Insert(handle);
+    }
+  }
+
+  typedef TemplateHashMap<Map, Handle<Map>, ZoneAllocationPolicy>
+      MapHandleTable;
+  MapHandleTable map_;
+  Zone* zone_;
+  Handle<Map> null_handle_;
+};
+
+
+class TransitionInputDictionary BASE_EMBEDDED {
+ public:
+  explicit TransitionInputDictionary(Zone* zone) :
+      dictionary_(TransitionInputMatch, 32, ZoneAllocationPolicy(zone)),
+      zone_(zone),
+      iterator_(NULL) {
+  }
+
+  void Initialize(Isolate* isolate,
+                  ZoneList<MarkedTransitionElementsGroup*>* groups);
+
+  TransitionInputDictionaryValue* Lookup(HInstruction* transition_input) {
+    ZoneHashMap::Entry* entry = dictionary_.Lookup(transition_input,
+                                               transition_input->id(),
+                                               false,
+                                               ZoneAllocationPolicy(zone_));
+
+    if (entry == NULL) {
+      return NULL;
+    }
+
+    TransitionInputDictionaryValue* value =
+        reinterpret_cast<TransitionInputDictionaryValue*>(entry->value);
+    return value;
+  }
+
+  void Scorch(MarkedTransitionElementsGroup* other_family_group);
+
+  TransitionInputDictionaryValue* Start() {
+    iterator_ =  dictionary_.Start();
+    if (iterator_ != NULL) {
+      return reinterpret_cast<TransitionInputDictionaryValue*>(
+          iterator_->value);
+    }
+
+    return NULL;
+  }
+
+  TransitionInputDictionaryValue* Next() {
+    iterator_ = dictionary_.Next(iterator_);
+    if (iterator_ != NULL) {
+      return reinterpret_cast<TransitionInputDictionaryValue*>(
+          iterator_->value);
+    }
+
+    return NULL;
+  }
+
+ private:
+  Zone* zone() { return zone_; }
+  static bool TransitionInputMatch(void* key1, void* key2) {
+    return key1 == key2;
+  }
+
+  void Insert(TransitionInputDictionaryValue* value) {
+    ZoneHashMap::Entry* entry = dictionary_.Lookup(value->transition_input(),
+                                    value->transition_input()->id(),
+                                    true,
+                                    ZoneAllocationPolicy(zone_));
+    ASSERT(entry->value == NULL);
+    entry->value = value;
+    iterator_ = NULL;
+  }
+
+  void Remove(HInstruction* transition_input) {
+    dictionary_.Remove(transition_input, transition_input->id());
+    iterator_ = NULL;
+  }
+
+  ZoneHashMap dictionary_;
+  Zone* zone_;
+  ZoneHashMap::Entry* iterator_;
+};
+
+
+void TransitionInputDictionaryValue::ComputeMostGeneralMapAndFamily(
+                    MostGeneralMapAndFamily* most_general_map_and_family,
+                    MarkedTransitionElementsGroup** other_family_group) {
+  *most_general_map_and_family = most_general();
+
+  // At the end of this function all groups in the list need to agree on the
+  // highest map.  so one time through the loop isn't enough.
+  for (int count = 0; count < 2; count++) {
+    for (int i = 0; i < groups(); i++) {
+      Map* todo_most_general_map = group(i)->most_general_map();
+
+      if (!most_general_map_and_family->is_valid()) {
+        // First todo, first time through the loop
+        most_general_map_and_family->Update(todo_most_general_map,
+                                            group(i)->map_family());
+      } else if (most_general_map_and_family->most_general_map() !=
+                 todo_most_general_map) {
+        // Are they in the same family?
+        if (most_general_map_and_family->family() != group(i)->map_family()) {
+          // Yikes. this won't work.
+          *other_family_group = group(i);
+          most_general_map_and_family->invalidate();
+          return;
+        }
+
+        // which one is higher? Figure that out and then the other one needs to
+        // be able to find a path to it.
+        ElementsKind unified_elements_kind = GetUnifiedFastElementsKind(
+            most_general_map_and_family->most_general_map()->elements_kind(),
+            todo_most_general_map->elements_kind());
+
+        // make sure both maps have a path to success
+        Map* unified_map = most_general_map_and_family->most_general_map()->
+            LookupElementsTransitionMap(unified_elements_kind);
+        Map* unified_todo_map = todo_most_general_map->
+            LookupElementsTransitionMap(unified_elements_kind);
+        if (unified_map == NULL || unified_todo_map == NULL ||
+            (unified_map != unified_todo_map)) {
+          *other_family_group = group(i);
+          most_general_map_and_family->invalidate();
+          return;
+        }
+
+        most_general_map_and_family->Update(unified_map,
+                                            group(i)->map_family());
+        group(i)->set_most_general_map(
+            most_general_map_and_family->most_general_map());
+      }
+    }
+  }
+}
+
+
+void TransitionInputDictionary::Scorch(MarkedTransitionElementsGroup*
+                                         other_family_group) {
+  MarkedTransitionElementsGroupList worklist(10, zone());
+  other_family_group->set_hoistable(false);
+  worklist.Add(other_family_group, zone());
+
+  while (!worklist.is_empty()) {
+    MarkedTransitionElementsGroup* group = worklist.RemoveLast();
+    ASSERT(!group->hoistable());
+    for (int t = 0; t < group->transition_inputs(); t++) {
+      HInstruction* transition_input = group->transition_input(t);
+      TransitionInputDictionaryValue* value = Lookup(transition_input);
+      if (value != NULL) {
+        for (int i = 0; i < value->groups(); i++) {
+          MarkedTransitionElementsGroup* other_group = value->group(i);
+          if (other_group->hoistable()) {
+            other_group->set_hoistable(false);
+            worklist.Add(other_group, zone());
+          }
+        }
+
+        Remove(transition_input);
+      }
+    }
+  }
+}
+
+
+void TransitionInputDictionary::Initialize(Isolate* isolate,
+                             ZoneList<MarkedTransitionElementsGroup*>* groups) {
+  ZoneAllocationPolicy allocator(zone());
+  Counters* counters = isolate->counters();
+
+  for (int i = 0; i < groups->length(); i++) {
+    MarkedTransitionElementsGroup* group = groups->at(i);
+    int site_nesting_depth = group->load_or_store()->block()->
+        LoopNestingDepth();
+
+    for (int t = 0; t < group->transition_inputs(); t++) {
+      HInstruction* transition_input = group->transition_input(t);
+
+      // Score computation
+      int input_site_nesting_depth = transition_input->block()->
+          LoopNestingDepth();
+      int loop_delta = site_nesting_depth - input_site_nesting_depth;
+      int proposedAdds = group->bookmarks();
+      MarkedTransitionElementsGroup::ScoreType scoreType =
+          group->scoretype_from_loopdelta(loop_delta);
+      int score = (loop_delta == 0 ? 1 : loop_delta)*proposedAdds;
+      if (score < 0) score *= -1;
+      group->increment_score(scoreType, score);
+      TransitionInputDictionaryValue* value = Lookup(transition_input);
+      if (value == NULL) {
+        // It's new, add a value
+        value = new(zone())
+            TransitionInputDictionaryValue(transition_input, zone());
+        Insert(value);
+      }
+
+      value->AddGroup(group);
+    }
+
+    // Export the site score in aggregate for reporting
+    counters->transition_site_positive_score()->
+        Increment(group->score(MarkedTransitionElementsGroup::SCORE_POSITIVE));
+    counters->transition_site_negative_score()->
+        Increment(group->score(MarkedTransitionElementsGroup::SCORE_NEGATIVE));
+    counters->transition_site_neutral_score()->
+        Increment(group->score(MarkedTransitionElementsGroup::SCORE_NEUTRAL));
+  }
+}
+
+
+void HGraph::InsertElementsTransitions() {
+  ZoneAllocationPolicy allocator(zone());
+  HPhase phase("H_Place elements transitions", this);
+
+  // Initialize the groups, the map handle map, the transition input dictionary
+  for (int i = 0; i < marked_transitions_.length(); i++) {
+    MarkedTransitionElementsGroup* group = marked_transitions_[i];
+    ASSERT(group->bookmarks() > 0);
+    group->ComputeTransitionInputValues(GetMaximumValueID());

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

As discussed, this algorithm costs O(n x m), where n is number of loads/stores
and m is number of involved phi nodes + input values. Is there a way to
transform this to just visit phi nodes + input values once? and then propagate
to the load/stores, for a total expense of O(n + m)

+  }
+
+  MapHandleMap mapHandleMap(zone());
+  mapHandleMap.Populate(&marked_transitions_);
+
+  TransitionInputDictionary transitionInputDictionary(zone());
+  transitionInputDictionary.Initialize(isolate(), &marked_transitions_);
+
+  // Now that the map is created, run the unification algorithm
+  bool done = false;
+  while (!done) {
+    bool changed = false;
+    for (TransitionInputDictionaryValue* value =
+             transitionInputDictionary.Start();
+         value != NULL;
+         value = transitionInputDictionary.Next()) {
+      MarkedTransitionElementsGroup* wrong_family_group = NULL;
+      MostGeneralMapAndFamily new_most_general;
+      value->ComputeMostGeneralMapAndFamily(&new_most_general,
+                                            &wrong_family_group);
+      if (!new_most_general.is_valid()) {
+        ASSERT(wrong_family_group != NULL);
+        transitionInputDictionary.Scorch(wrong_family_group);
+        changed = true;
+        break;
+      }
+
+      if (!value->most_general().Equals(new_most_general)) {
+        value->set_most_general(new_most_general);
+        changed = true;
+      }
+    }
+
+    done = !changed;
+  }
+
+  // Now we have the "to" value for each location, and groups have been divided
+  // into sets, including a set that couldn't be transitioned and is no longer
+  // represented in the transitionInputDictionary Handle each todo again.
+  if (FLAG_trace_transition_placement) {
+    for (int i = 0; i < marked_transitions_.length(); i++) {
+      MarkedTransitionElementsGroup* group = marked_transitions_.at(i);
+      HeapStringAllocator string_allocator;
+      StringStream stream(&string_allocator);
+      group->PrintTo(&stream);
+      PrintF("%s", *stream.ToCString());
+    }
+  }
+
+  // Do the work
+  for (int i = 0; i < marked_transitions_.length(); i++) {
+    MarkedTransitionElementsGroup* group = marked_transitions_.at(i);

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

Is this just an ArrayInterface?

+
+    // All groups need to be finalized, even if we don't take action on them.
+    group->Finalize();
+
+    if (!group->hoistable()) {
+      // We aren't moving this todo, leave it alone and visit the next
+      continue;
+    }
+
+    // 1) Remove the nonsmicheck.
+    if (group->smi_check()->IsLinked()) {
+      group->smi_check()->DeleteAndReplaceWith(NULL);
+    }
+
+    // 2) alter the elementkind of the loadkeyed/storekeyed instruction if
+    // required.  (note that steps a,b,c won't happen if the transition was
+    // marked as invalid because it operates on a different map family) 2a)
+    // unlink transitions associated with this site from their current location
+    // 2b) Create appropriate transition instructions up at the transition input
+    // site.  2c) Fix the checkmaps instruction if required.
+
+    Handle<Map>& handle = mapHandleMap.Lookup(group->most_general_map());
+    ASSERT(!handle.is_null());
+
+    HCheckMaps* map_check = group->map_check();
+    if (map_check != NULL) {
+      ASSERT(map_check->map_set()->length() == 1);
+      // Surgically replace the map in there if necessary
+      if (*(map_check->map_set()->at(0).location()) != *handle.location()) {
+        map_check->map_set()->Clear();
+        map_check->map_set()->Add(handle, zone());
+      }
+
+      // The map check had a dependency on the transition elements statement
+      // that was in place before. This is unnecessary now, just remove it.
+      // After the operations above, the tree expresses dependency through
+      // ordinary output values
+      map_check->RemoveTypeCheck();
+    }
+
+    for (int t = 0; t < group->transition_inputs(); t++) {
+      TransitionInputDictionaryValue* value =
+          transitionInputDictionary.Lookup(group->transition_input(t));
+      for (int r = 0; r < group->bookmarks(); r++) {
+        TransitionElementsBookmark* record = group->bookmark_pointer(r);
+        if (value->RequiresTransitionElementsKind(
+                record->elementskind_from())) {
+          // We need to emit a transition.
+          value->InsertTransitionElementsKind(record->from(), handle);
+
+          // Remove the transition from it's original location
+          if (record->transition_instruction()->block() != NULL) {
+            ASSERT(record->transition_instruction()->HasNoUses());
+            record->transition_instruction()->DeleteAndReplaceWith(NULL);
+          }
+        }
+      }
+    }
+  }
+}
+
+
 void HGraph::PropagateMinusZeroChecks(HValue* value, BitVector* visited) {
   HValue* current = value;
   while (current != NULL) {
@@ -3274,6 +3980,8 @@ bool HGraph::Optimize(SmartArrayPointer<char>* bailout_reason) {
   if (FLAG_eliminate_dead_phis) EliminateUnreachablePhis();
   CollectPhis();
 
+  if (FLAG_use_place_elements_transitions) InsertElementsTransitions();
+
   if (has_osr_loop_entry()) {
     const ZoneList<HPhi*>* phis = osr_loop_entry()->phis();
     for (int j = 0; j < phis->length(); j++) {
@@ -6075,7 +6783,8 @@ HInstruction* HGraphBuilder::BuildFastElementAccess(HValue* elements,
                                                     HValue* val,
                                                     HValue* load_dependency,
                                                     ElementsKind elements_kind,
-                                                    bool is_store) {
+                                                    bool is_store,
+                                                    bool defer_initialization) {
   if (is_store) {
     ASSERT(val != NULL);
     switch (elements_kind) {
@@ -6089,7 +6798,7 @@ HInstruction* HGraphBuilder::BuildFastElementAccess(HValue* elements,
       case FAST_DOUBLE_ELEMENTS:
       case FAST_HOLEY_DOUBLE_ELEMENTS:
         return new(zone()) HStoreKeyed(
-            elements, checked_key, val, elements_kind);
+            elements, checked_key, val, elements_kind, defer_initialization);
       default:
         UNREACHABLE();
         return NULL;
@@ -6099,24 +6808,35 @@ HInstruction* HGraphBuilder::BuildFastElementAccess(HValue* elements,
   return new(zone()) HLoadKeyed(elements,
                                 checked_key,
                                 load_dependency,
-                                elements_kind);
+                                elements_kind, defer_initialization);
 }
 
 
 HInstruction* HGraphBuilder::BuildMonomorphicElementAccess(HValue* object,
-                                                           HValue* key,
-                                                           HValue* val,
-                                                           HValue* dependency,
-                                                           Handle<Map> map,
-                                                           bool is_store) {
+                                                  HValue* key,
+                                                  HValue* val,
+                                                  HValue* dependency,
+                                                  Handle<Map> map,
+                                                  bool is_store,
+                                                  HCheckMaps** checkmap_instr) {
   HCheckMaps* mapcheck = new(zone()) HCheckMaps(object, map,
                                                 zone(), dependency);
   AddInstruction(mapcheck);
   if (dependency) {
     mapcheck->ClearGVNFlag(kDependsOnElementsKind);
   }
+
+  if (checkmap_instr != NULL) {
+    *checkmap_instr = mapcheck;
+  }
+
+  // TODO(mvstanton): this is a bit opaque, maybe just pass in a
+  // defer_initialization param
+  bool defer_initialization = FLAG_use_place_elements_transitions &&
+      (dependency != NULL);
   return BuildUncheckedMonomorphicElementAccess(object, key, val,
-                                                mapcheck, map, is_store);
+                                                mapcheck, map, is_store,
+                                                defer_initialization);
 }
 
 
@@ -6126,7 +6846,8 @@ HInstruction* HGraphBuilder::BuildUncheckedMonomorphicElementAccess(
     HValue* val,
     HCheckMaps* mapcheck,
     Handle<Map> map,
-    bool is_store) {
+    bool is_store,
+    bool defer_initialization) {
   // No GVNFlag is necessary for ElementsKind if there is an explicit dependency
   // on a HElementsTransition instruction. The flag can also be removed if the
   // map to check has FAST_HOLEY_ELEMENTS, since there can be no further
@@ -6172,7 +6893,8 @@ HInstruction* HGraphBuilder::BuildUncheckedMonomorphicElementAccess(
   checked_key = AddInstruction(new(zone()) HBoundsCheck(key, length,
                                                         ALLOW_SMI_KEY));
   return BuildFastElementAccess(elements, checked_key, val, mapcheck,
-                                map->elements_kind(), is_store);
+                                map->elements_kind(), is_store,
+                                defer_initialization);
 }
 
 
@@ -6224,7 +6946,8 @@ HInstruction* HGraphBuilder::TryBuildConsolidatedElementLoad(
   HCheckMaps* check_maps = new(zone()) HCheckMaps(object, maps, zone());
   AddInstruction(check_maps);
   HInstruction* instr = BuildUncheckedMonomorphicElementAccess(
-      object, key, val, check_maps, most_general_consolidated_map, false);
+      object, key, val, check_maps, most_general_consolidated_map, false,
+      false);
   return instr;
 }
 
@@ -6238,7 +6961,9 @@ HValue* HGraphBuilder::HandlePolymorphicElementAccess(HValue* object,
                                                       bool is_store,
                                                       bool* has_side_effects) {
   *has_side_effects = false;
-  AddInstruction(new(zone()) HCheckNonSmi(object));
+  bool use_groups = FLAG_use_place_elements_transitions;
+  HCheckNonSmi* checknonsmi = new(zone()) HCheckNonSmi(object);
+  AddInstruction(checknonsmi);
   SmallMapList* maps = prop->GetReceiverTypes();
   bool todo_external_array = false;
 
@@ -6284,6 +7009,7 @@ HValue* HGraphBuilder::HandlePolymorphicElementAccess(HValue* object,
   int num_untransitionable_maps = 0;
   Handle<Map> untransitionable_map;
   HTransitionElementsKind* transition = NULL;
+  ZoneList<TransitionElementsBookmark> bookmarks(10, zone());
   for (int i = 0; i < maps->length(); ++i) {
     Handle<Map> map = maps->at(i);
     ASSERT(map->IsMap());
@@ -6294,6 +7020,14 @@ HValue* HGraphBuilder::HandlePolymorphicElementAccess(HValue* object,
       transition = new(zone()) HTransitionElementsKind(
           object, map, transition_target.at(i));
       AddInstruction(transition);
+
+      if (use_groups) {
+        TransitionElementsBookmark tr(transition,
+                                      map,
+                                      transition_target.at(i),
+                                      isolate());
+        bookmarks.Add(tr, zone());
+      }
     } else {
       type_todo[map->elements_kind()] = true;
       if (IsExternalArrayElementsKind(map->elements_kind())) {
@@ -6312,8 +7046,18 @@ HValue* HGraphBuilder::HandlePolymorphicElementAccess(HValue* object,
       instr = AddInstruction(is_store ? BuildStoreKeyedGeneric(object, key, val)
                                       : BuildLoadKeyedGeneric(object, key));
     } else {
+      HCheckMaps *checkmaps = NULL;
       instr = AddInstruction(BuildMonomorphicElementAccess(
-          object, key, val, transition, untransitionable_map, is_store));
+          object, key, val, transition, untransitionable_map, is_store,
+          &checkmaps));
+
+      if (use_groups && bookmarks.length() > 0) {
+        MarkedTransitionElementsGroup* group = new(zone())
+            MarkedTransitionElementsGroup(instr, checknonsmi,
+                                          checkmaps, zone());
+        group->AddBookmarks(bookmarks);
+        graph()->AddMarkedTransitionElementsGroup(group);
+      }
     }
     *has_side_effects |= instr->HasObservableSideEffects();
     if (position != RelocInfo::kNoPosition) instr->set_position(position);
@@ -6365,11 +7109,13 @@ HValue* HGraphBuilder::HandlePolymorphicElementAccess(HValue* object,
 
       set_current_block(if_true);
       HInstruction* access;
+      HCheckMaps* checkmaps = NULL;
       if (IsFastElementsKind(elements_kind)) {
         if (is_store && !IsFastDoubleElementsKind(elements_kind)) {
-          AddInstruction(new(zone()) HCheckMaps(
+          checkmaps = new(zone()) HCheckMaps(
               elements, isolate()->factory()->fixed_array_map(),
-              zone(), elements_kind_branch));
+              zone(), elements_kind_branch);
+          AddInstruction(checkmaps);
         }
         // TODO(jkummerow): The need for these two blocks could be avoided
         // in one of two ways:
@@ -6395,11 +7141,20 @@ HValue* HGraphBuilder::HandlePolymorphicElementAccess(HValue* object,
                                                               ALLOW_SMI_KEY));
         access = AddInstruction(BuildFastElementAccess(
             elements, checked_key, val, elements_kind_branch,
-            elements_kind, is_store));
+            elements_kind, is_store, use_groups && bookmarks.length() > 0));
         if (!is_store) {
           Push(access);
         }
 
+        if (use_groups && bookmarks.length() > 0) {
+          ASSERT(access->IsLoadKeyed() || access->IsStoreKeyed());
+          MarkedTransitionElementsGroup* group = new(zone())
+              MarkedTransitionElementsGroup(access, checknonsmi,
+                                            checkmaps, zone());
+          group->AddBookmarks(bookmarks);
+          graph()->AddMarkedTransitionElementsGroup(group);
+        }
+
         *has_side_effects |= access->HasObservableSideEffects();
         if (position != -1) {
           access->set_position(position);
@@ -6412,7 +7167,16 @@ HValue* HGraphBuilder::HandlePolymorphicElementAccess(HValue* object,
                                                               ALLOW_SMI_KEY));
         access = AddInstruction(BuildFastElementAccess(
             elements, checked_key, val, elements_kind_branch,
-            elements_kind, is_store));
+            elements_kind, is_store, use_groups && bookmarks.length() > 0));
+
+        if (use_groups && bookmarks.length() > 0) {
+          ASSERT(access->IsLoadKeyed() || access->IsStoreKeyed());
+          MarkedTransitionElementsGroup* group = new(zone())
+              MarkedTransitionElementsGroup(access, checknonsmi,
+                                            checkmaps, zone());
+          group->AddBookmarks(bookmarks);
+          graph()->AddMarkedTransitionElementsGroup(group);
+        }
       } else if (elements_kind == DICTIONARY_ELEMENTS) {
         if (is_store) {
           access = AddInstruction(BuildStoreKeyedGeneric(object, key, val));
@@ -6429,6 +7193,7 @@ HValue* HGraphBuilder::HandlePolymorphicElementAccess(HValue* object,
       if (!is_store) {
         Push(access);
       }
+
       current_block()->Goto(join);
       set_current_block(if_false);
     }
@@ -9722,6 +10487,185 @@ void HEnvironment::PrintToStd() {
 }
 
 
+TransitionElementsBookmark::TransitionElementsBookmark(
+    HTransitionElementsKind* transition,
+    Handle<Map> map_from, Handle<Map> map_to, Isolate* isolate)
+    : transition_(transition),
+      from_(map_from),
+      to_(map_to),
+      pessimistic_holey_() {
+
+  // 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.
+
+  // TODO(mvstanton): generalize this service into
+  // "MakeWorstCaseMapForElementsKindTransition" (ie, not "holey")
+  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;
+  }
+
+  ASSERT(!pessimistic_holey_.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;
+}
+
+
+void MarkedTransitionElementsGroup::AddBookmarks(
+    const ZoneList<TransitionElementsBookmark>& records) {
+  ASSERT(records.length() > 0);
+  Map* first_to_map = *(records[0].to().location());
+
+  // Doesn't check for duplicates.
+  // The "to" map values should be the same for the whole group
+  for (int i = 0; i < records.length(); i++) {
+    bookmarks_->Add(records[i], zone_);
+    ASSERT(first_to_map == *(records[i].to().location()));
+  }
+
+  set_most_general_map(first_to_map);
+}
+
+
+void MarkedTransitionElementsGroup::ComputeTransitionInputValues(
+    int maximumGraphValueID) {
+  HValue* elements = NULL;
+
+  HInstruction* instruction = load_or_store();
+  if (instruction->IsStoreKeyed()) {
+    elements = HStoreKeyed::cast(instruction)->elements();

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

Can you add elements to ArrayInterface?

+  } else {
+    CHECK(instruction->IsLoadKeyed());
+    elements = HLoadKeyed::cast(instruction)->elements();
+  }
+
+  ASSERT(elements != NULL);
+  // Now get the item from the elements
+  ASSERT(elements->IsLoadElements());
+  HLoadElements *start = HLoadElements::cast(elements);
+
+  ASSERT(transition_inputs_->length() == 0);
+  BitVector visited(maximumGraphValueID, zone());

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

maximum_graph_value_id

+
+  ZoneList<HValue*> worklist(10, zone());
+  worklist.Add(start->value(), zone());
+
+  while (!worklist.is_empty()) {
+    HValue* value = worklist.RemoveLast();
+    // Have we visited this node?
+    if (!visited.Contains(value->id())) {
+      visited.Add(value->id());
+      if (value->IsPhi()) {
+        HPhi *phi = HPhi::cast(value);
+        for (int i = 0; i < phi->OperandCount(); i++) {
+          worklist.Add(phi->OperandAt(i), zone());
+        }
+      } else {
+        // It must be a transition input value.
+        ASSERT(value->IsInstruction());
+        transition_inputs_->Add(HInstruction::cast(value), zone());
+      }
+    }
+  }
+
+  // We must have found something.
+  ASSERT(transition_inputs_->length() > 0);
+}
+
+
+void MarkedTransitionElementsGroup::PrintTo(StringStream* stream) const {
+  HInstruction* instruction = load_or_store();
+  stream->Add("SITE: block%d %d: ", instruction->block()->block_id(),
+              instruction->id());
+  instruction->PrintTo(stream);
+  stream->Add("\n");
+
+  // Print validness
+  stream->Add("  HOISTABLE: %s\n", hoistable() ? "true" : "false");
+
+  // Print score
+  stream->Add("  SCORE: (+%d,%d,-%d)\n", score_[0], score_[1], score_[2]);
+
+  // Find the def point for the instruction
+  HValue *elements = NULL;
+  if (instruction->IsStoreKeyed()) {
+    elements = HStoreKeyed::cast(instruction)->elements();
+  } else {
+    ASSERT(instruction->IsLoadKeyed());
+    elements = HLoadKeyed::cast(instruction)->elements();
+  }
+
+  ASSERT(elements != NULL);
+  // Now get the item from the elements
+  ASSERT(elements->IsLoadElements());
+  HValue *elements_value = HLoadElements::cast(elements)->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 < bookmarks(); i++) {
+    const TransitionElementsBookmark& b = bookmark(i);
+    stream->Add("    %s", ElementsKindToString(b.elementskind_from()));
+    stream->Add("(0x%p)-> ", *(b.from()));
+    transitionElementsKind = b.elementskind_to();
+    stream->Add("%s", ElementsKindToString(transitionElementsKind));
+    stream->Add("(0x%p)\n", *(b.to()));
+  }
+
+  // Print possibly externally computed map
+  const char *signifier = (transitionElementsKind !=
+                           most_general_map()->elements_kind())
+      ? "*" : "";
+  stream->Add("  COMPUTED MOST GENERAL MAP: %s%s(0x%p)\n", signifier,
+              ElementsKindToString(most_general_map()->elements_kind()),
+              most_general_map());
+
+  // Print terminal nodes if available
+  stream->Add("  TRANSITION INPUT VALUES:\n");
+  for (int j = 0; j < transition_inputs(); j++) {
+    HValue* node = transition_input(j);
+    stream->Add("    block%d %d: ", node->block()->block_id(), node->id());
+    node->PrintNameTo(stream);
+    stream->Add("  ");
+    node->PrintTo(stream);
+    stream->Add("\n");
+  }
+}
+
+
+void MarkedTransitionElementsGroup::PrintToStd() const {
+  HeapStringAllocator string_allocator;
+  StringStream trace(&string_allocator);
+  PrintTo(&trace);
+  PrintF("%s", *trace.ToCString());
+}
+
+
 void HTracer::TraceCompilation(FunctionLiteral* function) {
   Tag tag(this, "compilation");
   Handle<String> name = function->debug_name();