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 ddf86c5e4706c7e2168d6ace7096bb3edb337db9..fd1dc23c5bc8dc3af9e8e4e7744c9392c93e9ca5 100644
--- a/src/hydrogen.cc
+++ b/src/hydrogen.cc
@@ -2449,6 +2449,673 @@ void HGraph::InitializeInferredTypes(int from_inclusive, int to_inclusive) {
 }
 
 
+typedef ZoneList<HInstruction*> TransitionInputList;
+typedef ZoneList<ArrayInstruction*> ArrayInstructionList;
+typedef EnumSet<ElementsKind> ElementsKindSet;
+
+
+class MapHandleMap BASE_EMBEDDED {

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

How about this idea. Just have a single table that maps {Map*, ElementsKind} ->
Handle<Map>. 

If you want the handle for the map itself, you add
{map, elements()->kind()} -> the map's handle
to the table.
If you want the "transitioned from family", you add 
{family_map, transitioned_kind} -> the transitioned_kind's handle
to the table. 

Probably reduces the code by about half. Then better name might be
TransitionedMapHandlesMap. 

[mvstanton, 2012/12/04 11:39:58]

Done.

+ public:
+  explicit MapHandleMap(Zone* zone) :
+      map_(MapPointerMatch, ZoneAllocationPolicy(zone)),
+      indexer_(IndexMatch, 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_;
+  }
+
+  Map* Lookup(Map* family, ElementsKind kind) {
+    IndexKey lookupKey(family, kind);
+    IndexKeyTable::Iterator i = indexer_.find(
+        &lookupKey, false, ZoneAllocationPolicy(zone_));
+    if (i != indexer_.end()) {
+      return i->second;
+    }
+
+    return NULL;
+  }
+  
+  void Populate(ArrayInstruction* instruction) {

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

I kind of think that the methods to handle ArrayInstructions (this one and Add)
should logically live outside this class, since it would be great if the
MapHandleMap class only needs to know about the implementation of types it
directly contains.

[mvstanton, 2012/12/04 11:39:58]

Done.

+    for (int r = 0; r < instruction->bookmarks(); r++) {
+      Add(instruction->bookmark(r));
+    }
+  }
+
+ private:
+  struct IndexKey {
+    IndexKey(Map* family_in, ElementsKind kind_in) :
+        family(family_in),
+        kind(kind_in) {
+    }
+    
+    bool operator==(const IndexKey& pair) const {
+      return pair.family == family && pair.kind == kind;
+    }
+
+    int Hash() {
+      return family->Hash() ^ (17*static_cast<int>(kind));
+    }
+
+    Map* family;
+    ElementsKind kind;
+  };
+  
+  static bool MapPointerMatch(void* key1, void* key2) {
+    return key1 == key2;
+  }
+
+  static bool IndexMatch(void* key1, void* key2) {
+    IndexKey* k1 = reinterpret_cast<IndexKey*>(key1);
+    IndexKey* k2 = reinterpret_cast<IndexKey*>(key2);
+    return *k1 == *k2;
+  }
+  
+  void Add(TransitionElementsBookmark* record) {
+    Handle<Map>* family = record->family_pointer();
+    InsertIfMissing(record->from_pointer(), family);
+    InsertIfMissing(record->to_pointer(), family);
+    InsertIfMissing(record->pessimistic_holey_pointer(), family);
+  }
+
+  void Insert(Handle<Map>* handle, Handle<Map>* family) {
+    MapHandleTable::Iterator i = map_.find(*(handle->location()), true,

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

here and below: doesn't *handle return a Map°, you don't have to do
*(handle->location().

[mvstanton, 2012/12/04 11:39:58]

Done.

+                                           ZoneAllocationPolicy(zone_));
+    ASSERT(i != map_.end());
+    i->second = handle;
+
+    IndexKeyTable::Iterator iki = indexer_.find(
+        new(zone()) IndexKey(*(family->location()),(*handle)->elements_kind()), true,
+        ZoneAllocationPolicy(zone_));
+    ASSERT(iki != indexer_.end());
+    iki->second = *(family->location());
+  }
+
+  void InsertIfMissing(Handle<Map>* handle, Handle<Map>* family) {
+    if (Lookup(*(handle->location())).is_null()) {
+      Insert(handle, family);
+    }
+  }
+
+  Zone* zone() { return zone_; }
+  
+  typedef TemplateHashMap<Map, Handle<Map>, ZoneAllocationPolicy>
+      MapHandleTable;
+  MapHandleTable map_;
+  typedef TemplateHashMap<IndexKey, Map, ZoneAllocationPolicy>
+      IndexKeyTable;
+  IndexKeyTable indexer_;
+  Zone* zone_;
+  Handle<Map> null_handle_;
+};
+
+
+class InstructionPlacer: public ZoneObject {
+ public:
+  InstructionPlacer(HInstruction* transition_input, Zone* zone) :
+      zone_(zone),
+      transition_input_(transition_input),
+      last_in_chain_(NULL) {
+
+  }
+
+  // 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) {

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

add_after

[mvstanton, 2012/12/04 11:39:58]

Done.

+      // 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)) {

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

Wow. How can this happen? Don't you just visit each use once, and since the
transition is brand new, when would they ever be equal?

[mvstanton, 2012/12/04 11:39:58]

Note that the iterator starts at last_in_chain_->uses(), not
transition_input_->uses(), so indeed, our newly added HTransitionElementsKind is
going to be a usage. Ugh!

+          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]

You mentioned that you copied this magic from somewhere else. Any chance that
you could pack that in a shared method that gets called from both sites?

[mvstanton, 2012/12/04 11:39:58]

Done.

+      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);
+        }
+      }
+    }
+  }
+
+  Zone* zone() { return zone_; }
+  Zone* zone_;
+  HInstruction* transition_input_;
+  ElementsKindSet from_elements_;
+  HTransitionElementsKind* last_in_chain_;
+};
+
+
+class ResolutionTableValue: public ZoneObject {
+ public:
+  ResolutionTableValue() :
+      to_(NULL),
+      family_(NULL),
+      poisoned_(false),
+      placer_(NULL) {
+
+  }
+
+  Map* to() { return to_; }
+  Map* family() { return family_; }
+  bool poisoned() { return poisoned_; }
+  ElementsKindSet from_set() { return from_elements_; }
+
+  void Initialize(ArrayInstruction* instr) {
+    if (!instr->hoistable()) {
+      poisoned_ = true;
+      return;
+    }
+
+    family_ = instr->map_family(); // may be null
+    if (family_ != NULL) {
+      // We should have bookmarks to initialize with
+      ASSERT(instr->bookmarks() > 0);
+      for (int i=0;i<instr->bookmarks();i++) {
+        TransitionElementsBookmark* tr = instr->bookmark(i);
+        from_elements_.Add(tr->elementskind_from());
+        to_ = *(tr->to_pointer()->location());
+      }
+    }
+  }
+  
+  bool Merge(ResolutionTableValue* from_value) {
+    if (from_value->poisoned() && !poisoned()) {
+      poisoned_ = true;
+      return true;
+    }
+
+    if (family() != NULL && from_value->family() != family()) {
+      poisoned_ = true;
+      return true;
+    }
+
+    bool changed = false;
+    family_ = from_value->family();
+    if (to() == NULL) {
+      to_ = from_value->to();
+      changed = true;
+    } else if (to() != from_value->to()) {
+      // figure out unified map
+      ElementsKind unified_elements_kind = GetUnifiedFastElementsKind(
+          to()->elements_kind(),
+          from_value->to()->elements_kind());
+      // make sure both maps have a path to success
+      Map* unified_map = to()->LookupElementsTransitionMap(unified_elements_kind);

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

This won't be GC-safe if we're running concurrent compilation. you'll have to
use the MapHandleMap in some way.

[mvstanton, 2012/12/04 11:39:58]

Done.

+      Map* unified_from_value_map = from_value->to()->LookupElementsTransitionMap(unified_elements_kind);      

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

Same here.

[mvstanton, 2012/12/04 11:39:58]

Done.

+      if (unified_map == NULL || unified_from_value_map == NULL ||
+	  (unified_map != unified_from_value_map)) {
+        // impossible
+        poisoned_ = true;
+        return false;
+      }
+      
+      changed = true;
+    }
+
+    if (!(from_set() == from_value->from_set())) {
+      from_elements_.Add(from_value->from_set());
+      changed = true;
+    }
+    
+    return changed;
+  }
+
+  InstructionPlacer* placer() { return placer_; }
+  void set_placer(InstructionPlacer* placer) { placer_ = placer; }
+ private:
+  Map* to_;

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

Can these be Handles?

+  Map* family_;  
+  bool poisoned_;
+  ElementsKindSet from_elements_;
+  InstructionPlacer* placer_; // Field only used for root nodes
+};
+
+
+class ResolutionTable BASE_EMBEDDED {
+ public:
+  explicit ResolutionTable(Isolate* isolate, Zone* zone) :
+      dictionary_(NodeMatch, 32, ZoneAllocationPolicy(zone)),
+      zone_(zone) {
+  }
+
+  void Insert(HValue* node, ResolutionTableValue* value) {
+    ZoneHashMap::Entry* entry = dictionary_.Lookup(node,
+                                    node->id(),
+                                    true,
+                                    ZoneAllocationPolicy(zone_));
+    ASSERT(entry->value == NULL);
+    entry->value = value;
+  }
+  
+  ResolutionTableValue* Lookup(HValue* node) {
+    ZoneHashMap::Entry* entry = dictionary_.Lookup(node,
+                                               node->id(),
+                                               false,
+                                               ZoneAllocationPolicy(zone_));
+
+    if (entry == NULL) {
+      return NULL;
+    }
+
+    ResolutionTableValue* value =
+        reinterpret_cast<ResolutionTableValue*>(entry->value);
+    return value;
+  }
+
+  ZoneHashMap::Entry* Start() {
+    return dictionary_.Start();
+  }
+
+  inline HValue* KeyFromEntry(ZoneHashMap::Entry* entry) {
+    return reinterpret_cast<HValue*>(entry->key);
+  }
+
+  inline ResolutionTableValue* ValueFromEntry(ZoneHashMap::Entry* entry) {
+    return reinterpret_cast<ResolutionTableValue*>(entry->value);
+  }
+
+  ZoneHashMap::Entry* Next(ZoneHashMap::Entry* previous_entry) {
+    return dictionary_.Next(previous_entry);
+  }
+  
+ private:
+  Zone* zone() { return zone_; }
+  static bool NodeMatch(void* key1, void* key2) {
+    return key1 == key2;
+  }
+
+  ZoneHashMap dictionary_;
+  Zone* zone_;
+};
+
+
+struct WorkItem {
+  WorkItem(HValue* from_in, HValue* to_in, HValue* context_in)
+      : from(from_in), to(to_in), context(context_in) {
+  }
+  bool operator==(const WorkItem& pair) const {
+    return pair.from == from && pair.to == to && pair.context == context;
+  }
+  HValue* from;
+  HValue* to;
+  HValue* context;
+};
+
+
+void HoistTransitionsFromArrayInstructionSites(ArrayInstruction* load_or_store,

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

If you make all of these methods inside of a HInsertElementsTransitions
optimization phase, then you probably can avoid passing MapHandleMap* and Zone*

[mvstanton, 2012/12/04 11:39:58]

I solved it a little differently, moving the method as a member of new class
HTransitionHoister.

+                                      ResolutionTableValue* load_or_store_value,
+                                      HValue* root,
+                                      ResolutionTableValue* root_value,
+                                      MapHandleMap* map_handles,
+                                      Zone* zone) {
+
+  // Are we poisonous? We can't participate in this wonderful scheme...
+  if (load_or_store_value->poisoned()) {
+    // Poison should have flowed up and down the graph from sites to roots
+    ASSERT(root_value->poisoned());
+    return;
+  }

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

if (load_or_store->bookmarks() == 0) return;

avoid the loop if there are no bookmarks.

[mvstanton, 2012/12/04 11:39:58]

Done.

+  
+  // In here we'll
+  // 1) remove any transition statements from the load_or_store site
+  // 2) place correct statements at the root site, avoiding duplicates
+  if (load_or_store->bookmarks() > 0 && root_value->placer() == NULL) {
+    ASSERT(root->IsInstruction());
+    root_value->set_placer(new(zone) InstructionPlacer(HInstruction::cast(root),
+                                                       zone));
+  }
+
+  ASSERT(root_value->to() == load_or_store_value->to());
+  Handle<Map>& handle = map_handles->Lookup(root_value->to());
+  InstructionPlacer* placer = root_value->placer();
+  for (int i = 0; i < load_or_store->bookmarks(); i++) {
+    TransitionElementsBookmark* bookmark = load_or_store->bookmark(i);
+
+    // TODO(mvstanton): lots of asserts in this method that the information
+    // at the instruction site and the root site are the same or subsets.
+    // Unnecessary redundancy?
+    ASSERT(root_value->from_set().Contains(bookmark->elementskind_from()));
+    ASSERT(load_or_store_value->from_set().Contains(
+        bookmark->elementskind_from()));
+
+    if (placer->RequiresTransitionElementsKind(bookmark->elementskind_from())) {
+      placer->InsertTransitionElementsKind(bookmark->from(), handle);
+
+      if (bookmark->transition_instruction()->block() != NULL) {
+        ASSERT(bookmark->transition_instruction()->HasNoUses());
+        bookmark->transition_instruction()->DeleteAndReplaceWith(NULL);
+      }
+    }
+  }
+}
+
+
+void UpdateMapCheck(HCheckMaps* check_maps,
+                    ResolutionTableValue* nearest_value,
+                    MapHandleMap* map_handles,
+                    Zone* zone) {
+  // Only manipulate this mapcheck if at least one of the {from,to} maps from
+  // nearest_value is in the check.
+  Map* family = nearest_value->family();
+  Map* to = nearest_value->to();
+  bool contains_to = false;
+  bool contains_from = false;
+  for (int i = 0; i < check_maps->map_set()->length(); i++) {
+    Map* current = *(check_maps->map_set()->at(i).location());
+    if (current != to) {
+      Map* in_family = map_handles->Lookup(family,
+                                           current->elements_kind());
+      if (current == in_family) {
+        contains_from = true;
+      }
+    } else {
+      contains_to = true;
+    }
+  }
+
+  if (!contains_from && !contains_to) {
+    // This map check deals with a different family. Leave it alone
+    return;
+  }
+
+  if (!contains_to) {
+    // We definitely need the to map in the checkmaps instruction
+    Handle<Map>& handle = map_handles->Lookup(to);
+    ASSERT(!handle.is_null());
+    check_maps->map_set()->Add(handle, zone); 
+  }
+
+  if (contains_from) {
+    // The whole from set should be removed from the map check, since we have
+    // the to map in there.
+    for (int i = check_maps->map_set()->length() - 1; i >= 0; i--) {
+      Map* current = *(check_maps->map_set()->at(i).location());
+      if (current != to) {
+        Map* in_family = map_handles->Lookup(family,
+                                             current->elements_kind());
+        if (current == in_family) {
+          // Delete this map
+          Handle<Map>& handle = map_handles->Lookup(current);
+          ASSERT(!handle.is_null());
+          check_maps->map_set()->Remove(handle);
+        }
+      }      
+    }
+  }
+
+  if (!contains_to) {
+    // We should sort the map since we added one, removing others
+    check_maps->map_set()->Sort();
+  }
+}
+
+
+void HGraph::InsertElementsTransitions() {
+  ZoneAllocationPolicy allocator(zone());
+  HPhase phase("H_Place elements transitions", this);
+
+  MapHandleMap mapHandleMap(zone());
+  ResolutionTable table(isolate(),zone());
+
+  ZoneList<WorkItem> worklist(10, zone());
+  
+  // Walk the graph looking for store and load keyed instructions.

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

I think it would be better if you build the list of ArrayInstructions explicitly
from HKeyedLoad/HKeyedStore's constructors, avoiding iterating over all
instructions.

[mvstanton, 2012/12/04 11:39:58]

Done.

+  for (int i = 0; i < blocks()->length(); ++i) {
+    for (HInstruction* instr = blocks()->at(i)->first();
+        instr != NULL;
+        instr = instr->next()) {
+      ArrayInstruction* array_instruction = NULL;
+      if (instr->IsLoadKeyed()) {
+        HLoadKeyed* op = HLoadKeyed::cast(instr);
+        array_instruction = static_cast<ArrayInstruction*>(op);
+      } else if (instr->IsStoreKeyed()) {
+        HStoreKeyed* op = HStoreKeyed::cast(instr);
+        array_instruction = static_cast<ArrayInstruction*>(op);
+      } else {
+        continue;
+      }
+
+      // Add to our table
+      ResolutionTableValue* value = new(zone()) ResolutionTableValue();
+      value->Initialize(array_instruction);
+      table.Insert(array_instruction, value);
+      
+      // Add to our handle map
+      mapHandleMap.Populate(array_instruction);
+
+      // Add to our worklist. Here I am skipping over elements,
+      HValue* elements = array_instruction->elements();
+      ASSERT(elements->IsLoadElements());
+      HLoadElements* start = HLoadElements::cast(elements);
+      WorkItem item(array_instruction, start->value(), NULL);
+      worklist.Add(item, zone());
+    }
+  }
+
+  // Propagate information up the graph.
+  while (!worklist.is_empty()) {
+    WorkItem item = worklist.RemoveLast();
+    ASSERT(table.Lookup(item.from) != NULL);
+    bool changed = false;
+    ResolutionTableValue* to_value = table.Lookup(item.to);
+    if (to_value == NULL) {
+      to_value = new(zone()) ResolutionTableValue();
+      table.Insert(item.to, to_value);
+      changed = true;
+    }
+    
+    changed |= to_value->Merge(table.Lookup(item.from));
+    if (item.to->IsPhi() && changed) {
+      HPhi* phi = HPhi::cast(item.to);
+      for (int i = 0; i < phi->OperandCount(); i++) {
+        worklist.Add(WorkItem(phi, phi->OperandAt(i), NULL), zone());
+      }
+    }
+  }
+
+  // Now propagate information back down to input sites, starting from root

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

root... do you mean transition input candidates?

+  // nodes in the table
+  // Table contains phi nodes, arrayinstructions, and roots.
+  ZoneHashMap::Entry* current = table.Start();
+  while (current != NULL) {
+    HValue* current_value = table.KeyFromEntry(current);
+    if (!current_value->IsPhi() && !current_value->IsLoadKeyed() &&

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

Would things get easier if you had a up_worklist and a down_worklist? That way
you could initialize the down_worklist when you found roots during the
up_worklist iteration, avoiding having to go hunting for them in the table in a
separate step.

[mvstanton, 2012/12/04 11:39:58]

Done.

+        !current_value->IsStoreKeyed()) {
+      HInstruction* current_instr = HInstruction::cast(current_value);
+
+      for (HUseIterator it(current_instr->uses()); !it.Done(); it.Advance()) {
+        HValue* value = it.value();
+        if (value->IsPhi()) {
+          worklist.Add(WorkItem(current_value, value, current_value), zone());
+        } else if (value->IsLoadElements()) {
+          // Walk through to the StoreKeyed(s)
+          for (HUseIterator it_load(value->uses()); !it_load.Done(); it_load.Advance()) {
+            HValue* value_load = it_load.value();
+            if (value_load->IsStoreKeyed() || value_load->IsLoadKeyed()) {
+              worklist.Add(WorkItem(current_value, value_load, current_value), zone());
+            }
+          }
+        } else if (value->IsCheckMaps()) {
+          // CheckMaps don't have rows in the table, as they are periphery instructions
+          // we might need to update.
+          worklist.Add(WorkItem(current_value, value, current_value), zone());

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

Is it wrong to call UpdateMapCheck here directly?

[mvstanton, 2012/12/04 11:39:58]

We could get away with that. I was thinking though, that the logic around
calling UpdateMapCheck is a bit careful and I'd rather do all the "actual
operations" in one place.

+        }
+      }
+    }
+
+    current = table.Next(current);
+  }
+
+  BitVector visited(GetMaximumValueID(), zone());
+  while (!worklist.is_empty()) {
+    WorkItem item = worklist.RemoveLast();
+    ASSERT(table.Lookup(item.from) != NULL);
+    bool changed = false;
+    ResolutionTableValue* from_value = table.Lookup(item.from);    
+    ResolutionTableValue* to_value = table.Lookup(item.to);
+    if (to_value != NULL) {
+      changed = to_value->Merge(from_value);
+    }
+
+    if (item.to->IsPhi() &&
+        (changed || !visited.Contains(item.to->id()))) {
+      visited.Add(item.to->id());
+
+      ASSERT(to_value != NULL);
+      for (HUseIterator it(item.to->uses()); !it.Done(); it.Advance()) {
+        HValue* value = it.value();
+        if (value->IsPhi()) {
+          worklist.Add(WorkItem(item.to, value, item.context), zone());
+        } else if (value->IsLoadElements()) {
+          // Walk through to the StoreKeyed(s)
+          for (HUseIterator it_load(value->uses()); !it_load.Done(); it_load.Advance()) {
+            HValue* value_load = it_load.value();
+            if (value_load->IsStoreKeyed() || value_load->IsLoadKeyed()) {
+              worklist.Add(WorkItem(item.to, value_load, item.context), zone());
+            }
+          }
+        }
+      }
+    } else if (item.to->IsLoadKeyed() || item.to->IsStoreKeyed()) {
+      ASSERT(to_value != NULL);
+      // It can now be finalized
+      ArrayInstruction* array_instruction = reinterpret_cast<ArrayInstruction*>(item.to);
+      if (to_value->to() != NULL) {

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

Can you move this and the Finalize in the NULL case into
HoistTransitionsFromArrayInstructionSites, which maybe could be be just just
called PlaceArrayInstructionTransitions

[mvstanton, 2012/12/04 11:39:58]

Done.

+        array_instruction->Finalize(to_value->to()->elements_kind());
+        if (array_instruction->bookmarks() > 0) {
+          // We have work to do here with the context variable.
+          // It is the root node where we'll move transitions to.
+          ResolutionTableValue* context_value = table.Lookup(item.context);
+          ASSERT(context_value != NULL);
+          HoistTransitionsFromArrayInstructionSites(array_instruction,
+                                                    to_value,
+                                                    item.context,
+                                                    context_value,
+                                                    &mapHandleMap,
+                                                    zone());
+        }
+      } else {
+        // It's possible there is no exchange of typing information for a site.
+        array_instruction->Finalize();
+      }
+    } else if (item.to->IsCheckMaps()) {
+      // There is no to_value for this case. We just need to try and update the
+      // checkmaps
+      ASSERT(to_value == NULL);
+      UpdateMapCheck(HCheckMaps::cast(item.to), from_value, &mapHandleMap, zone());
+    }
+  }                                                                      
+
+#ifdef DEBUG
+  // Verify that we didn't miss initialization of any array instructions.
+  current = table.Start();
+  while (current != NULL) {
+    HValue* current_value = table.KeyFromEntry(current);
+    if (current_value->IsLoadKeyed() || current_value->IsStoreKeyed()) {
+      ArrayInstruction* array_instr = reinterpret_cast<ArrayInstruction*>(current_value);
+      ASSERT(array_instr->Initialized());
+    }
+
+    current = table.Next(current);
+  }
+#endif // DEBUG
+  
+  // Now the table actually has enough information to make decisions.
+  if (FLAG_trace_transition_placement) {
+    HeapStringAllocator string_allocator;
+    StringStream stream(&string_allocator);
+
+    // print the table
+    ZoneHashMap::Entry* current = table.Start();
+    while (current != NULL) {
+      HValue* current_value = table.KeyFromEntry(current);
+      ResolutionTableValue* value = table.ValueFromEntry(current);
+
+      if (current_value->IsLoadKeyed() || current_value->IsStoreKeyed()) {
+        ArrayInstruction* array_instruction = reinterpret_cast<ArrayInstruction*>(current_value);
+        array_instruction->PrintElementPlacementTo(&stream);
+        stream.Add("  Here is what we need to do\n");
+        if (value->to() != NULL) {
+          stream.Add("  To: %s\n", ElementsKindToString(value->to()->elements_kind()));
+        } else {
+          stream.Add("  No instructions\n");
+        }
+      }
+      current = table.Next(current);
+    }
+
+    PrintF("%s", *stream.ToCString());
+  }
+}
+
+
 void HGraph::PropagateMinusZeroChecks(HValue* value, BitVector* visited) {
   HValue* current = value;
   while (current != NULL) {
@@ -3274,6 +3941,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++) {
@@ -3670,7 +4339,7 @@ void HGraph::EliminateRedundantBoundsChecks() {
 }
 
 
-static void DehoistArrayIndex(ArrayInstructionInterface* array_operation) {
+static void DehoistArrayIndex(ArrayInstruction* array_operation) {
   HValue* index = array_operation->GetKey();
   if (!index->representation().IsInteger32()) return;
 
@@ -3726,13 +4395,13 @@ void HGraph::DehoistSimpleArrayIndexComputations() {
     for (HInstruction* instr = blocks()->at(i)->first();
         instr != NULL;
         instr = instr->next()) {
-      ArrayInstructionInterface* array_instruction = NULL;
+      ArrayInstruction* array_instruction = NULL;
       if (instr->IsLoadKeyed()) {
         HLoadKeyed* op = HLoadKeyed::cast(instr);
-        array_instruction = static_cast<ArrayInstructionInterface*>(op);
+        array_instruction = static_cast<ArrayInstruction*>(op);
       } else if (instr->IsStoreKeyed()) {
         HStoreKeyed* op = HStoreKeyed::cast(instr);
-        array_instruction = static_cast<ArrayInstructionInterface*>(op);
+        array_instruction = static_cast<ArrayInstruction*>(op);
       } else {
         continue;
       }
@@ -4577,7 +5246,8 @@ void HGraphBuilder::VisitForInStatement(ForInStatement* stmt) {
           environment()->ExpressionStackAt(2),  // Enum cache.
           environment()->ExpressionStackAt(0),  // Iteration index.
           environment()->ExpressionStackAt(0),
-          FAST_ELEMENTS));
+          FAST_ELEMENTS,
+          zone()));
 
   // Check if the expected map still matches that of the enumerable.
   // If not just deoptimize.
@@ -5190,7 +5860,8 @@ void HGraphBuilder::VisitArrayLiteral(ArrayLiteral* expr) {
             elements,
             key,
             value,
-            boilerplate_elements_kind));
+            boilerplate_elements_kind,
+            zone()));
         break;
       default:
         UNREACHABLE();
@@ -6016,7 +6687,7 @@ HInstruction* HGraphBuilder::BuildLoadKeyedGeneric(HValue* object,
 }
 
 
-HInstruction* HGraphBuilder::BuildExternalArrayElementAccess(
+ArrayInstruction* HGraphBuilder::BuildExternalArrayElementAccess(
     HValue* external_elements,
     HValue* checked_key,
     HValue* val,
@@ -6055,12 +6726,13 @@ HInstruction* HGraphBuilder::BuildExternalArrayElementAccess(
     return new(zone()) HStoreKeyed(external_elements,
                                    checked_key,
                                    val,
-                                   elements_kind);
+                                   elements_kind,
+                                   zone());
   } else {
     ASSERT(val == NULL);
     HLoadKeyed* load =
        new(zone()) HLoadKeyed(
-           external_elements, checked_key, dependency, elements_kind);
+           external_elements, checked_key, dependency, elements_kind, zone());
     if (FLAG_opt_safe_uint32_operations &&
         elements_kind == EXTERNAL_UNSIGNED_INT_ELEMENTS) {
       graph()->RecordUint32Instruction(load);
@@ -6070,12 +6742,12 @@ HInstruction* HGraphBuilder::BuildExternalArrayElementAccess(
 }
 
 
-HInstruction* HGraphBuilder::BuildFastElementAccess(HValue* elements,
-                                                    HValue* checked_key,
-                                                    HValue* val,
-                                                    HValue* load_dependency,
-                                                    ElementsKind elements_kind,
-                                                    bool is_store) {
+ArrayInstruction* HGraphBuilder::BuildFastElementAccess(HValue* elements,
+                                                        HValue* checked_key,
+                                                        HValue* val,
+                                                        HValue* load_dependency,
+                                                        ElementsKind elements_kind,
+                                                        bool is_store) {
   if (is_store) {
     ASSERT(val != NULL);
     switch (elements_kind) {
@@ -6089,7 +6761,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, zone());
       default:
         UNREACHABLE();
         return NULL;
@@ -6099,28 +6771,32 @@ HInstruction* HGraphBuilder::BuildFastElementAccess(HValue* elements,
   return new(zone()) HLoadKeyed(elements,
                                 checked_key,
                                 load_dependency,
-                                elements_kind);
+                                elements_kind,
+                                zone());
 }
 
 
-HInstruction* HGraphBuilder::BuildMonomorphicElementAccess(HValue* object,
-                                                           HValue* key,
-                                                           HValue* val,
-                                                           HValue* dependency,
-                                                           Handle<Map> map,
-                                                           bool is_store) {
+ArrayInstruction* HGraphBuilder::BuildMonomorphicElementAccess(
+    HValue* object,
+    HValue* key,
+    HValue* val,
+    HValue* dependency,
+    Handle<Map> map,
+    bool is_store) {
   HCheckMaps* mapcheck = new(zone()) HCheckMaps(object, map,
                                                 zone(), dependency);
   AddInstruction(mapcheck);
   if (dependency) {
     mapcheck->ClearGVNFlag(kDependsOnElementsKind);
   }
-  return BuildUncheckedMonomorphicElementAccess(object, key, val,
-                                                mapcheck, map, is_store);
+
+  ArrayInstruction* instr =  BuildUncheckedMonomorphicElementAccess(
+      object, key, val, mapcheck, map, is_store);
+  return instr;
 }
 
 
-HInstruction* HGraphBuilder::BuildUncheckedMonomorphicElementAccess(
+ArrayInstruction* HGraphBuilder::BuildUncheckedMonomorphicElementAccess(
     HValue* object,
     HValue* key,
     HValue* val,
@@ -6176,7 +6852,7 @@ HInstruction* HGraphBuilder::BuildUncheckedMonomorphicElementAccess(
 }
 
 
-HInstruction* HGraphBuilder::TryBuildConsolidatedElementLoad(
+ArrayInstruction* HGraphBuilder::TryBuildConsolidatedElementLoad(
     HValue* object,
     HValue* key,
     HValue* val,
@@ -6223,9 +6899,8 @@ HInstruction* HGraphBuilder::TryBuildConsolidatedElementLoad(
 
   HCheckMaps* check_maps = new(zone()) HCheckMaps(object, maps, zone());
   AddInstruction(check_maps);
-  HInstruction* instr = BuildUncheckedMonomorphicElementAccess(
+  return BuildUncheckedMonomorphicElementAccess(
       object, key, val, check_maps, most_general_consolidated_map, false);
-  return instr;
 }
 
 
@@ -6238,7 +6913,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 +6961,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 +6972,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 +6998,12 @@ HValue* HGraphBuilder::HandlePolymorphicElementAccess(HValue* object,
       instr = AddInstruction(is_store ? BuildStoreKeyedGeneric(object, key, val)
                                       : BuildLoadKeyedGeneric(object, key));
     } else {
-      instr = AddInstruction(BuildMonomorphicElementAccess(
-          object, key, val, transition, untransitionable_map, is_store));
+      ArrayInstruction* array_instr = BuildMonomorphicElementAccess(
+          object, key, val, transition, untransitionable_map, is_store);
+      instr = AddInstruction(array_instr);
+      if (use_groups && bookmarks.length() > 0) {
+        array_instr->AddBookmarks(bookmarks);
+      }
     }
     *has_side_effects |= instr->HasObservableSideEffects();
     if (position != RelocInfo::kNoPosition) instr->set_position(position);
@@ -6365,11 +7055,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:
@@ -6393,9 +7085,12 @@ HValue* HGraphBuilder::HandlePolymorphicElementAccess(HValue* object,
                                                            HType::Smi()));
         checked_key = AddInstruction(new(zone()) HBoundsCheck(key, length,
                                                               ALLOW_SMI_KEY));
-        access = AddInstruction(BuildFastElementAccess(
+        ArrayInstruction* array_instruction = BuildFastElementAccess(
             elements, checked_key, val, elements_kind_branch,
-            elements_kind, is_store));
+            elements_kind, is_store);
+        array_instruction->set_hoistable(false);
+        
+        access = AddInstruction(array_instruction);
         if (!is_store) {
           Push(access);
         }
@@ -6410,9 +7105,11 @@ HValue* HGraphBuilder::HandlePolymorphicElementAccess(HValue* object,
         length = AddInstruction(new(zone()) HFixedArrayBaseLength(elements));
         checked_key = AddInstruction(new(zone()) HBoundsCheck(key, length,
                                                               ALLOW_SMI_KEY));
-        access = AddInstruction(BuildFastElementAccess(
+        array_instruction = BuildFastElementAccess(
             elements, checked_key, val, elements_kind_branch,
-            elements_kind, is_store));
+            elements_kind, is_store);
+        array_instruction->set_hoistable(false);
+        access = AddInstruction(array_instruction);
       } else if (elements_kind == DICTIONARY_ELEMENTS) {
         if (is_store) {
           access = AddInstruction(BuildStoreKeyedGeneric(object, key, val));
@@ -6429,6 +7126,7 @@ HValue* HGraphBuilder::HandlePolymorphicElementAccess(HValue* object,
       if (!is_store) {
         Push(access);
       }
+
       current_block()->Goto(join);
       set_current_block(if_false);
     }
@@ -7546,6 +8244,10 @@ bool HGraphBuilder::TryCallApply(Call* expr) {
 // transitions of each other. Returns either NULL if they are not from the same
 // family, or a Map* indicating the map with the first elements kind of the
 // family that is in the list.
+
+//
+// TODO(mvstanton) - can I use this function?
+//
 static Map* CheckSameElementsFamily(SmallMapList* types) {
   if (types->length() <= 1) return NULL;
   // Check if all maps belong to the same transition family.
@@ -9775,6 +10477,10 @@ void HEnvironment::PrintToStd() {
 }
 
 
+
+
+
+
 void HTracer::TraceCompilation(FunctionLiteral* function) {
   Tag tag(this, "compilation");
   Handle<String> name = function->debug_name();