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

src/hydrogen.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 2431 matching lines @@
       ZoneList<HValue*> worklist(block->phis()->length(), zone());
       for (int j = 0; j < block->phis()->length(); ++j) {
         worklist.Add(block->phis()->at(j), zone());
       }
       InferTypes(&worklist);
     }
   }
 }
 
 
+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) {
     if (visited->Contains(current->id())) return;
 
     // For phis, we must propagate the check to all of its inputs.
     if (current->IsPhi()) {
       visited->Add(current->id());
       HPhi* phi = HPhi::cast(current);
       for (int i = 0; i < phi->OperandCount(); ++i) {
@@ skipping 805 matching lines @@
   }
   EliminateRedundantPhis();
   if (!CheckArgumentsPhiUses()) {
     *bailout_reason = SmartArrayPointer<char>(StrDup(
         "Unsupported phi use of arguments"));
     return false;
   }
   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++) {
       HPhi* phi = phis->at(j);
       osr_values()->at(phi->merged_index())->set_incoming_value(phi);
     }
   }
 
   HInferRepresentation rep(this);
   rep.Analyze();
@@ skipping 376 matching lines @@
 }
 
 
 void HGraph::EliminateRedundantBoundsChecks() {
   HPhase phase("H_Eliminate bounds checks", this);
   BoundsCheckTable checks_table(zone());
   EliminateRedundantBoundsChecks(entry_block(), &checks_table);
 }
 
 
-static void DehoistArrayIndex(ArrayInstructionInterface* array_operation) {
+static void DehoistArrayIndex(ArrayInstruction* array_operation) {
   HValue* index = array_operation->GetKey();
   if (!index->representation().IsInteger32()) return;
 
   HConstant* constant;
   HValue* subexpression;
   int32_t sign;
   if (index->IsAdd()) {
     sign = 1;
     HAdd* add = HAdd::cast(index);
     if (add->left()->IsConstant()) {
@@ skipping 35 matching lines @@
 
 
 void HGraph::DehoistSimpleArrayIndexComputations() {
   if (!FLAG_array_index_dehoisting) return;
 
   HPhase phase("H_Dehoist index computations", this);
   for (int i = 0; i < blocks()->length(); ++i) {
     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;
       }
       DehoistArrayIndex(array_instruction);
     }
   }
 }
 
 
 void HGraph::DeadCodeElimination() {
@@ skipping 824 matching lines @@
   set_current_block(loop_successor);
   Drop(5);
 
   set_current_block(loop_body);
 
   HValue* key = AddInstruction(
       new(zone()) HLoadKeyed(
           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.
   AddInstruction(new(zone()) HCheckMapValue(
       environment()->ExpressionStackAt(4),
       environment()->ExpressionStackAt(3)));
 
   Bind(each_var, key);
 
   BreakAndContinueInfo break_info(stmt, 5);
@@ skipping 592 matching lines @@
         AddInstruction(new(zone()) HCheckSmi(value));
         // Fall through.
       case FAST_ELEMENTS:
       case FAST_HOLEY_ELEMENTS:
       case FAST_DOUBLE_ELEMENTS:
       case FAST_HOLEY_DOUBLE_ELEMENTS:
         AddInstruction(new(zone()) HStoreKeyed(
             elements,
             key,
             value,
-            boilerplate_elements_kind));
+            boilerplate_elements_kind,
+            zone()));
         break;
       default:
         UNREACHABLE();
         break;
     }
 
     AddSimulate(expr->GetIdForElement(i));
   }
   return ast_context()->ReturnValue(Pop());
 }
@@ skipping 805 matching lines @@
 }
 
 
 HInstruction* HGraphBuilder::BuildLoadKeyedGeneric(HValue* object,
                                                    HValue* key) {
   HValue* context = environment()->LookupContext();
   return new(zone()) HLoadKeyedGeneric(context, object, key);
 }
 
 
-HInstruction* HGraphBuilder::BuildExternalArrayElementAccess(
+ArrayInstruction* HGraphBuilder::BuildExternalArrayElementAccess(
     HValue* external_elements,
     HValue* checked_key,
     HValue* val,
     HValue* dependency,
     ElementsKind elements_kind,
     bool is_store) {
   if (is_store) {
     ASSERT(val != NULL);
     switch (elements_kind) {
       case EXTERNAL_PIXEL_ELEMENTS: {
@@ skipping 18 matching lines @@
       case FAST_HOLEY_ELEMENTS:
       case FAST_HOLEY_DOUBLE_ELEMENTS:
       case DICTIONARY_ELEMENTS:
       case NON_STRICT_ARGUMENTS_ELEMENTS:
         UNREACHABLE();
         break;
     }
     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);
     }
     return load;
   }
 }
 
 
-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) {
       case FAST_SMI_ELEMENTS:
       case FAST_HOLEY_SMI_ELEMENTS:
         // Smi-only arrays need a smi check.
         AddInstruction(new(zone()) HCheckSmi(val));
         // Fall through.
       case FAST_ELEMENTS:
       case FAST_HOLEY_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;
     }
   }
   // It's an element load (!is_store).
   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,
     HCheckMaps* mapcheck,
     Handle<Map> map,
     bool is_store) {
   // 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
   // ElementsKind transitions. Finally, the dependency can be removed for stores
@@ skipping 35 matching lines @@
   } else {
     length = AddInstruction(new(zone()) HFixedArrayBaseLength(elements));
   }
   checked_key = AddInstruction(new(zone()) HBoundsCheck(key, length,
                                                         ALLOW_SMI_KEY));
   return BuildFastElementAccess(elements, checked_key, val, mapcheck,
                                 map->elements_kind(), is_store);
 }
 
 
-HInstruction* HGraphBuilder::TryBuildConsolidatedElementLoad(
+ArrayInstruction* HGraphBuilder::TryBuildConsolidatedElementLoad(
     HValue* object,
     HValue* key,
     HValue* val,
     SmallMapList* maps) {
   // For polymorphic loads of similar elements kinds (i.e. all tagged or all
   // double), always use the "worst case" code without a transition.  This is
   // much faster than transitioning the elements to the worst case, trading a
   // HTransitionElements for a HCheckMaps, and avoiding mutation of the array.
   bool has_double_maps = false;
   bool has_smi_or_object_maps = false;
@@ skipping 26 matching lines @@
     if ((i == 0) || IsMoreGeneralElementsKindTransition(
             most_general_consolidated_map->elements_kind(),
             map->elements_kind())) {
       most_general_consolidated_map = map;
     }
   }
   if (!has_double_maps && !has_smi_or_object_maps) return NULL;
 
   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;
 }
 
 
 HValue* HGraphBuilder::HandlePolymorphicElementAccess(HValue* object,
                                                       HValue* key,
                                                       HValue* val,
                                                       Expression* prop,
                                                       BailoutId ast_id,
                                                       int position,
                                                       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;
 
   if (!is_store) {
     HInstruction* consolidated_load =
         TryBuildConsolidatedElementLoad(object, key, val, maps);
     if (consolidated_load != NULL) {
       AddInstruction(consolidated_load);
       *has_side_effects |= consolidated_load->HasObservableSideEffects();
       if (position != RelocInfo::kNoPosition) {
@@ skipping 25 matching lines @@
   for (int i = 0; i < maps->length(); ++i) {
     Handle<Map> map = maps->at(i);
     Handle<Map> transitioned_map =
         map->FindTransitionedMap(&possible_transitioned_maps);
     transition_target.Add(transitioned_map);
   }
 
   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());
     if (!transition_target.at(i).is_null()) {
       ASSERT(Map::IsValidElementsTransition(
           map->elements_kind(),
           transition_target.at(i)->elements_kind()));
       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())) {
         todo_external_array = true;
       }
       num_untransitionable_maps++;
       untransitionable_map = map;
     }
   }
 
   // If only one map is left after transitioning, handle this case
   // monomorphically.
   if (num_untransitionable_maps == 1) {
     HInstruction* instr = NULL;
     if (untransitionable_map->has_slow_elements_kind()) {
       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);
     return is_store ? NULL : instr;
   }
 
   HInstruction* checkspec =
       AddInstruction(HCheckInstanceType::NewIsSpecObject(object, zone()));
   HBasicBlock* join = graph()->CreateBasicBlock();
 
@@ skipping 31 matching lines @@
       HBasicBlock* if_false = graph()->CreateBasicBlock();
       HCompareConstantEqAndBranch* elements_kind_branch =
           new(zone()) HCompareConstantEqAndBranch(
               elements_kind_instr, elements_kind, Token::EQ_STRICT);
       elements_kind_branch->SetSuccessorAt(0, if_true);
       elements_kind_branch->SetSuccessorAt(1, if_false);
       current_block()->Finish(elements_kind_branch);
 
       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:
         // (1) Introduce ElementsKinds for JSArrays that are distinct from
         //     those for fast objects.
         // (2) Put the common instructions into a third "join" block. This
         //     requires additional AST IDs that we can deopt to from inside
         //     that join block. They must be added to the Property class (when
         //     it's a keyed property) and registered in the full codegen.
         HBasicBlock* if_jsarray = graph()->CreateBasicBlock();
         HBasicBlock* if_fastobject = graph()->CreateBasicBlock();
         HHasInstanceTypeAndBranch* typecheck =
             new(zone()) HHasInstanceTypeAndBranch(object, JS_ARRAY_TYPE);
         typecheck->SetSuccessorAt(0, if_jsarray);
         typecheck->SetSuccessorAt(1, if_fastobject);
         current_block()->Finish(typecheck);
 
         set_current_block(if_jsarray);
         HInstruction* length;
         length = AddInstruction(new(zone()) HJSArrayLength(object, typecheck,
                                                            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);
         }
 
         *has_side_effects |= access->HasObservableSideEffects();
         if (position != -1) {
           access->set_position(position);
         }
         if_jsarray->Goto(join);
 
         set_current_block(if_fastobject);
         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));
         } else {
           access = AddInstruction(BuildLoadKeyedGeneric(object, key));
         }
       } else {  // External array elements.
         access = AddInstruction(BuildExternalArrayElementAccess(
             external_elements, checked_key, val, elements_kind_branch,
             elements_kind, is_store));
       }
       *has_side_effects |= access->HasObservableSideEffects();
       if (position != RelocInfo::kNoPosition) access->set_position(position);
       if (!is_store) {
         Push(access);
       }
+
       current_block()->Goto(join);
       set_current_block(if_false);
     }
   }
 
   // Deopt if none of the cases matched.
   current_block()->FinishExitWithDeoptimization(HDeoptimize::kNoUses);
   join->SetJoinId(ast_id);
   set_current_block(join);
   return is_store ? NULL : Pop();
@@ skipping 1097 matching lines @@
     ast_context()->ReturnInstruction(call, expr->id());
     return true;
   }
 }
 
 
 // Checks if all maps in |types| are from the same family, i.e., are elements
 // 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.
   Map* kinds[kFastElementsKindCount];
   Map* first_map = *types->first();
   ElementsKind first_kind = first_map->elements_kind();
   if (!IsFastElementsKind(first_kind)) return NULL;
   int first_index = GetSequenceIndexFromFastElementsKind(first_kind);
   int last_index = first_index;
 
@@ skipping 2209 matching lines @@
 
 
 void HEnvironment::PrintToStd() {
   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();
   PrintStringProperty("name", *name->ToCString());
   PrintStringProperty("method", *name->ToCString());
   PrintLongProperty("date", static_cast<int64_t>(OS::TimeCurrentMillis()));
 }
 
 
 void HTracer::TraceLithium(const char* name, LChunk* chunk) {
@@ skipping 313 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify(false);  // No full verify.
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal