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 {
+ 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) {
+    for (int r = 0; r < instruction->bookmarks(); r++) {
+      Add(instruction->bookmark(r));
+    }
+  }
+
+ private:
+  struct IndexKey: public ZoneObject  {
+    IndexKey(Map* family_in, ElementsKind kind_in) :
+        family(family_in),
+        kind(kind_in) {
+    }
+    
+    int Hash() {
+      return family->Hash() + (31*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->Hash() == k2->Hash();
+  }
+  
+  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) {
+    Map* map = *(handle->location());
+    Map* family_map = *(family->location());
+    
+    MapHandleTable::Iterator i = map_.find(map, true,
+                                           ZoneAllocationPolicy(zone_));
+    ASSERT(i != map_.end());
+    i->second = handle;
+
+    IndexKey *key = new(zone()) IndexKey(family_map, map->elements_kind());
+    IndexKeyTable::Iterator iki = indexer_.find(
+        key, true,
+        ZoneAllocationPolicy(zone_));
+    ASSERT(iki != indexer_.end());
+    iki->second = map;
+  }
+
+  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) {
+      // 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()) {
+      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());
+      }
+    }
+  }
+
+  void Initialize(HPhi* phi, int maximum_graph_id, Zone* zone) {
+    visited_set_ = new(zone) BitVector(maximum_graph_id, zone);
+  }
+  
+  bool Merge(ResolutionTableValue* from_value) {
+
+    // a) Poison must always be imbibed
+    if (from_value->poisoned() && !poisoned()) {
+      poisoned_ = true;
+      return true;
+    }
+
+    // b) from_value has no information. No change.
+    if (from_value->to() == NULL) {
+      return false;
+    }
+
+    // c) We are uninitialized. Copy from_value.
+    ASSERT(from_value->family() != NULL);
+    if (to() == NULL) {
+      to_ = from_value->to();
+      from_elements_.Add(from_value->from_set());
+      family_ = from_value->family();
+      return true;
+    }
+
+    // d) We are both initialized. Negotiate
+    if (from_value->family() != family()) {
+      // We cannot change families!
+      poisoned_ = true;
+      return true;
+    }
+
+    bool changed = false;
+    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);
+      Map* unified_from_value_map = from_value->to()->LookupElementsTransitionMap(unified_elements_kind);      
+      if (unified_map == NULL || unified_from_value_map == NULL ||
+          (unified_map != unified_from_value_map)) {
+        // impossible
+        poisoned_ = true;
+        return true;
+      }
+
+      // TODO(mvstanton): on merges "down" the tree from roots back to load/store sites,
+      // we know we already did the unification step above, and that the current ResolutionTableValue
+      // should just accept the from.to_ map. Is it worth adding something like "mergemode"
+      // to save the trouble of the calls above?
+      to_ = unified_map;
+      changed = true;
+    }
+
+    if (!(from_set() == from_value->from_set())) {
+      from_elements_.Add(from_value->from_set());
+      changed = true;
+    }
+    
+    return changed;
+  }
+
+  bool VisitedBy(HValue* value) {
+    return visited_set_->Contains(value->id());
+  }
+  
+  void MarkVisitedBy(HValue* value) {
+    visited_set_->Add(value->id());
+  }
+
+  InstructionPlacer* placer() { return placer_; }
+  void set_placer(InstructionPlacer* placer) { placer_ = placer; }
+ private:
+  Map* to_;
+  Map* family_;  
+  bool poisoned_;
+  ElementsKindSet from_elements_;
+  InstructionPlacer* placer_; // Field only used for root nodes
+  BitVector* visited_set_; // only used by phi 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,
+                                      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;
+  }
+  
+  // 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) {
+        // The transition instruction should only be referred to by a map check instruction.
+        for (HUseIterator it(bookmark->transition_instruction()->uses()); !it.Done(); it.Advance()) {
+          HValue* value = it.value();
+          ASSERT(value->IsCheckMaps());
+          HCheckMaps::cast(value)->RemoveTypeCheck();
+        }
+        
+        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();
+  ASSERT(to != NULL && family != NULL);
+  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
+          check_maps->map_set()->RemoveAt(i);
+        }
+      }      
+    }
+  }
+
+  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.
+  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;
+      }
+
+      HValue* elements = array_instruction->elements();
+      if (elements->IsLoadElements()) {
+        // 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,
+        HLoadElements* start = HLoadElements::cast(elements);
+        WorkItem item(array_instruction, start->value(), array_instruction);
+        worklist.Add(item, zone());
+
+        if (FLAG_trace_transition_placement) {
+          HeapStringAllocator string_allocator;
+          StringStream stream(&string_allocator);
+          array_instruction->PrintElementPlacementTo(&stream);
+          PrintF("%s", *stream.ToCString());
+        }
+      } else {
+        // No need to consider external arrays in our case.
+        ASSERT(IsExternalArrayElementsKind(array_instruction->GetElementsKind()));
+        array_instruction->Finalize();
+      }
+    }
+  }
+
+  // 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);
+      if (item.to->IsPhi()) {
+        to_value->Initialize(HPhi::cast(item.to),GetMaximumValueID(), zone());
+      }
+      changed = true;
+    }
+    
+    changed |= to_value->Merge(table.Lookup(item.from));
+    if (item.to->IsPhi()) {
+      if (changed) {
+        HPhi* phi = HPhi::cast(item.to);
+        for (int i = 0; i < phi->OperandCount(); i++) {
+          worklist.Add(WorkItem(phi, phi->OperandAt(i), item.context), zone());
+        }
+      }
+    } else {
+      // Item.to is a root node. The context is useful to print
+      if (FLAG_trace_transition_placement) {
+        HeapStringAllocator string_allocator;
+        StringStream stream(&string_allocator);
+        ArrayInstruction* instr = reinterpret_cast<ArrayInstruction*>(item.context);
+        stream.Add("ARRAY INSTRUCTION: block%d %d: ", instr->block()->block_id(),
+              instr->id());
+        instr->PrintTo(&stream);
+        stream.Add("\n");
+        stream.Add("  maps to\n");
+        HInstruction* root = HInstruction::cast(item.to);
+        stream.Add("    block%d %d: ", root->block()->block_id(), root->id());
+        root->PrintNameTo(&stream);
+        stream.Add("  ");
+        root->PrintTo(&stream);
+        stream.Add("\n");
+        if (to_value->to() != NULL) {
+          stream.Add("  To: %s(0x%p)\n", 
+                     ElementsKindToString(to_value->to()->elements_kind()),
+                     to_value->to());
+        } else {
+          stream.Add("  To: n/a\n");
+        }
+
+        PrintF("%s", *stream.ToCString());
+      }      
+    }      
+  }
+
+  // Now propagate information back down to input sites, starting from root
+  // 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() &&
+        !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());
+        }
+      }
+    }
+
+    current = table.Next(current);
+  }
+  
+  while (!worklist.is_empty()) {
+    WorkItem item = worklist.RemoveLast();
+    /*
+    PrintF("Downpropagation: (%d,%d,%d)\n",
+           item.from->id(),
+           item.to->id(),
+           item.context->id());
+    */
+    bool changed = false;
+
+    ResolutionTableValue* from_value = table.Lookup(item.from);
+    ASSERT(from_value != NULL);
+    ResolutionTableValue* to_value = table.Lookup(item.to);
+    
+    if (to_value == NULL && item.to->IsPhi()) {
+      // We walk through phis on the way down, even if we didn't see
+      // them on the way up. There may be interesting nodes in these
+      // new locations (checkmaps, store/loads).
+      to_value = new(zone()) ResolutionTableValue();
+      to_value->Initialize(HPhi::cast(item.to), GetMaximumValueID(), zone());
+      table.Insert(item.to, to_value);
+    }
+
+    if (to_value != NULL) {
+      changed = to_value->Merge(from_value);
+    }
+
+    if (item.to->IsPhi() && (changed || !to_value->VisitedBy(item.context))) {
+      to_value->MarkVisitedBy(item.context);
+      
+      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 (value->IsCheckMaps()) {
+          worklist.Add(WorkItem(item.to, value, item.context), zone());
+        }
+      }
+    } else if (item.to->IsLoadKeyed() || item.to->IsStoreKeyed()) {
+      // Either it's the first time we are coming here OR the change is effectively no change
+      // This is because we begin the graph traversal at ROOT nodes, which have comprehensive
+      // information. Any edge in the worklist which leads to the array instruction will have
+      // that full information already, so there aren't really any changes at this point. 
+          
+      ASSERT(to_value != NULL);
+      ArrayInstruction* array_instruction = reinterpret_cast<ArrayInstruction*>(item.to);
+      // It can now be finalized
+      ResolutionTableValue* context_value = table.Lookup(item.context);
+      ASSERT(context_value != NULL);
+      if (to_value->to() != NULL) {
+        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.
+          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);
+      if (from_value->to() != 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
+}
+
+
 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