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 675 matching lines @@
 
 
 HGraph::HGraph(CompilationInfo* info)
     : isolate_(info->isolate()),
       next_block_id_(0),
       entry_block_(NULL),
       blocks_(8, info->zone()),
       values_(16, info->zone()),
       phi_list_(NULL),
       uint32_instructions_(NULL),
+      deferred_transitions_(10, info->zone()),      
       info_(info),
       zone_(info->zone()),
       is_recursive_(false),
       use_optimistic_licm_(false),
       type_change_checksum_(0) {
   start_environment_ =
       new(zone_) HEnvironment(NULL, info->scope(), info->closure(), zone_);
   start_environment_->set_ast_id(BailoutId::FunctionEntry());
   entry_block_ = CreateBasicBlock();
   entry_block_->SetInitialEnvironment(start_environment_);
@@ skipping 1789 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);
     }
   }
 }
 
 
+static bool TerminalMatch(void* key1, void* key2) {
+  return key1 == key2;
+}
+
+typedef ZoneList<DeferredTransitions*> DeferredTransitionsList;
+
+class HighestMapAndFamily {

[danno, 2012/11/14 15:28:18]

When you say "highest", do you mean most general? That's a term that we use
elsewhere for elements kind, and you might want to be consistent.

[mvstanton, 2012/11/16 15:15:06]

I needed to update many locations to be consistent about this. Good advice, thx.

+ public:
+  HighestMapAndFamily() : highest_map_(NULL), family_(NULL) { }
+  HighestMapAndFamily(HighestMapAndFamily& h)
+      : highest_map_(h.highest_map()),
+        family_(h.family()) {
+  }  
+
+  Map* highest_map() const { return highest_map_; }
+  Map* family() const { return family_; }
+
+  void change(Map* new_highest_map, Map* new_family) {

[danno, 2012/11/14 15:28:18]

Maybe "Update" instead?

[mvstanton, 2012/11/16 15:15:06]

Done.

+    if (is_valid()) {
+      ASSERT(new_family == family_); // family shouldn't be changed
+      highest_map_ = new_highest_map;
+    } else {
+      highest_map_ = new_highest_map;
+      family_ = new_family;
+    }
+  }
+
+  void invalidate() {
+    highest_map_ = NULL;
+    family_ = NULL;
+  }
+  
+  bool is_valid() const { return highest_map_ != NULL && family_ != NULL; }
+  bool operator==(const HighestMapAndFamily& h) const {

[danno, 2012/11/14 15:28:18]

We tend to avoid operator== (see
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Operator_Overl...).
"Equals" is more consistent with other sites?

[mvstanton, 2012/11/16 15:15:06]

Done.

+    if (!is_valid() || !h.is_valid()) {
+      return is_valid() == h.is_valid();
+    }
+    return highest_map_ == h.highest_map() && family_ == h.family();
+  }
+
+  bool operator!=(const HighestMapAndFamily& h) const {

[danno, 2012/11/14 15:28:18]

operator overloading

[mvstanton, 2012/11/16 15:15:06]

Done.

+    return !(*this == h);
+  }
+
+  HighestMapAndFamily& operator=(const HighestMapAndFamily& h) {

[danno, 2012/11/14 15:28:18]

operator overloading

[mvstanton, 2012/11/16 15:15:06]

this one I need to keep in order to copy these things. If it's all too much I
could just revert to thinking about the maps as two separate pointers and
abandon this little type.

+    if(this != &h) {
+      highest_map_ = h.highest_map();
+      family_ = h.family();
+    }
+    return *this;
+  }
+  
+ private:
+  Map *highest_map_;

[danno, 2012/11/14 15:28:18]

Map* highest_map_

[mvstanton, 2012/11/16 15:15:06]

Done.

+  Map *family_;
+};
+
+typedef EnumSet<ElementsKind> ElementsKindSet;
+
+class TerminalMapValue: public ZoneObject {

[danno, 2012/11/14 15:28:18]

TransitionElementsInputValueData?

[mvstanton, 2012/11/16 15:15:06]

Done.

+ public:
+  TerminalMapValue(HInstruction* terminal_node,Zone* zone) :
+      terminal_node_(terminal_node),
+      transitions_(new (zone) DeferredTransitionsList(10,zone)),
+      zone_(zone),
+      last_in_chain_(NULL) {
+
+  }
+
+  void add_transition(DeferredTransitions* todo) {

[danno, 2012/11/14 15:28:18]

AddTransition

[mvstanton, 2012/11/16 15:15:06]

Done.

+    if (todo->terminal_nodes() == 1) {
+      // put at the front of the list. Processing single element
+      // transitions first makes score calculation easier.
+      transitions_->InsertAt(0, todo, zone_);
+    } else {
+      transitions_->Add(todo, zone_);
+    }
+  }
+  
+  ElementsKind highest_elementskind() const {

[danno, 2012/11/14 15:28:18]

GetMostGenerateElementsKind()?

[mvstanton, 2012/11/16 15:15:06]

removed method, no callers

+    ASSERT(highest_.highest_map() != NULL);
+    return highest_.highest_map()->elements_kind();
+  }
+
+  HighestMapAndFamily& highest() { return highest_; }
+  void set_highest(HighestMapAndFamily& h) { highest_ = h; }
+  
+  int todo_count() const { return transitions_->length(); }
+  DeferredTransitions* todo(int i) { return (*transitions_)[i]; }
+  Zone* zone() { return zone_; }
+
+  // For instruction emission
+
+  bool RequiresTransitionElementsKind(ElementsKind from) const {
+    return !from_elements_.Contains(from);
+  }
+
+  void InsertTransitionElementsKind(HTransitionElementsKind* new_instr) {
+    ElementsKind from_elements_kind = new_instr->original_map()->elements_kind();
+    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(terminal_node_);
+      addafter->InsertAfter(terminal_node_);
+    }
+
+    new_instr->InsertAfter(addafter);
+    last_in_chain_ = new_instr;
+    from_elements_.Add(from_elements_kind);
+  }
+
+  HTransitionElementsKind* last_transitionelementskind() const {
+    // Will be NULL if none inserted yet.
+    return last_in_chain_;
+  }
+  
+ private:
+  HInstruction* terminal_node_;

[danno, 2012/11/14 15:28:18]

HValue*

[mvstanton, 2012/11/16 15:15:06]

Done.

+  DeferredTransitionsList* transitions_;  
+  Zone* zone_;
+  HighestMapAndFamily highest_;
+  ElementsKindSet from_elements_;
+  HTransitionElementsKind* last_in_chain_;
+};
+
+
+// This method walks through the TODOs that mapped to a particular terminal node
+// value. It returns the "TO" map that these nodes unify too. If they return
+// a NULL handle, then that means that the nodes couldn't be unified, and have
+// already been marked as invalid.
+// If they return a non-null value, then all the TODOs have also been updated to
+// recognize the returned map as their "TO" map as well.
+void ComputeHighest(TerminalMapValue* value, HighestMapAndFamily* highest, DeferredTransitions** cannotTransition) {
+  *highest = value->highest();
+  
+  // At the end of this function all todos in the list need to agree on the highest map.
+  // so one time through the loop isn't enough.
+  for (int count=0; count<2; count++) {
+    for (int i=0; i<value->todo_count(); i++) {
+      DeferredTransitions* todo = value->todo(i);
+      Map* todo_highest = todo->highest();
+
+      if (!highest->is_valid()) {
+        // First todo, first time through the loop
+        highest->change(todo_highest, todo->map_family());
+      } else if (highest->highest_map() != todo_highest) {
+        
+        // Are they in the same family?
+        if (highest->family() != todo->map_family()) {
+          // Yikes. this won't work.
+          *cannotTransition = todo;
+          highest->invalidate();
+          return;
+        }
+        
+        // which one is higher? Figure that out and then the other one needs to
+        // be able to find a path to it.
+        ElementsKind unified_highest_elements_kind = GetUnifiedFastElementsKind(
+            highest->highest_map()->elements_kind(), todo_highest->elements_kind());
+
+        // make sure both maps have a path to success
+        Map* unified_highest_map = highest->highest_map()->LookupElementsTransitionMap(unified_highest_elements_kind);
+        Map* unified_todo_highest_map = todo_highest->LookupElementsTransitionMap(unified_highest_elements_kind);
+        if (unified_highest_map == NULL || unified_todo_highest_map == NULL ||
+            (unified_highest_map != unified_todo_highest_map)) {
+          *cannotTransition = todo;
+          highest->invalidate();          
+          return;
+        }
+      
+        highest->change(unified_highest_map, todo->map_family());
+        todo->set_highest(highest->highest_map());
+      }
+    }
+  }
+}
+
+
+void ScorchTerminalMap(ZoneAllocationPolicy allocationPolicy, Zone* zone,
+                       DeferredTransitions* cannotTransition, ZoneHashMap* terminalMap) {
+  ZoneList<DeferredTransitions*> worklist(10, zone);
+  cannotTransition->set_invalid();
+  worklist.Add(cannotTransition, zone);
+
+  while (!worklist.is_empty()) {
+    DeferredTransitions* todo = worklist.RemoveLast();
+    ASSERT(todo->invalid());
+    for (int t=0; t<todo->terminal_nodes(); t++) {
+      HInstruction* terminal_node = todo->terminal_node(t);
+      ZoneHashMap::Entry* entry = terminalMap->Lookup(terminal_node,
+                                                      terminal_node->id(),
+                                                      false,
+                                                      allocationPolicy);
+      if (entry != NULL) {      
+        TerminalMapValue* value = reinterpret_cast<TerminalMapValue*>(entry->value);
+        for (int i=0; i<value->todo_count(); i++) {
+          DeferredTransitions* todo = value->todo(i);
+          if (!todo->invalid()) {
+            todo->set_invalid();
+            worklist.Add(todo, zone);
+          }
+        }
+
+        terminalMap->Remove(terminal_node, terminal_node->id());
+      }
+    }
+  }
+}
+
+
+Handle<Map>& StashedMapHandle(ZoneList<DeferredTransitions>* transitions,
+                                   Map* map) {
+
+  // The guarantee is that a handle does exist for the given map, since
+  // we saved/created it earlier.
+  // TODO(mvstanton): this could be way more efficient. It is brute force.
+  for (int i=0; i<transitions->length(); i++) {
+    DeferredTransitions& todo = transitions->at(i);
+    for (int r=0; r<todo.transitions(); r++) {
+      TransitionRecord& record = todo.transition_ref(r);
+      if (*(record.map_to().location()) == map) {
+        return record.map_to_ref();
+      } else if(*(record.optimistic_holey().location()) == map) {
+        return record.optimistic_holey_ref();
+      }
+    }
+  }
+
+  // This code is marked as unreachable because at runtime we can't actually create
+  // a handle during compiler optimization.
+  UNREACHABLE();
+  return transitions->at(0).transition_ref(0).map_to_ref();
+}
+
+
+void FinalizeTransitionToDos(ZoneList<DeferredTransitions>& transitions, int maximumGraphID) {

[danno, 2012/11/14 15:28:18]

How about FinalizeDeferredTransitionElements?

[mvstanton, 2012/11/16 15:15:06]

Done.

+  for (int i=0; i<transitions.length(); i++) {
+    DeferredTransitions& todo = transitions[i];
+    todo.ComputeTerminalNodes(maximumGraphID);
+    // Also fill in the current highest, which may later be changed externally.

[danno, 2012/11/14 15:28:18]

most general?

[mvstanton, 2012/11/16 15:15:06]

Done.

+    todo.compute_highest();
+  }
+}
+
+void HGraph::InitializeTerminalMap(ZoneHashMap& terminalMap) {
+  ZoneAllocationPolicy allocator(zone());
+  Counters* counters = isolate()->counters();
+ 
+  for (int i=0; i<deferred_transitions_.length(); i++) {
+    DeferredTransitions& todo = deferred_transitions_[i];
+    ASSERT(todo.transitions() > 0);
+    int site_nesting_depth = todo.instr()->block()->LoopNestingDepth();      
+
+    for (int t=0; t<todo.terminal_nodes(); t++) {
+      HInstruction* terminal_node = todo.terminal_node(t);
+
+      // Score computation
+      int terminal_site_nesting_depth = terminal_node->block()->LoopNestingDepth();
+      int loop_delta = site_nesting_depth - terminal_site_nesting_depth;
+      int proposedAdds = todo.transitions();
+      DeferredTransitions::ScoreType scoreType = todo.scoretype_from_loopdelta(loop_delta);
+      int score = (loop_delta==0 ? 1 : loop_delta)*proposedAdds;
+      if (score < 0) score *= -1;
+      todo.increment_score(scoreType,score);
+
+      ZoneHashMap::Entry* entry = terminalMap.Lookup(terminal_node,
+                                                     terminal_node->id(),
+                                                     true,
+                                                     allocator);
+      TerminalMapValue* value = NULL;
+      if (entry->value == NULL) {
+        // It's new, add a value
+        value = new (zone()) TerminalMapValue(terminal_node,zone());
+        entry->value = reinterpret_cast<void*>(value);
+      } else {
+        value = reinterpret_cast<TerminalMapValue*>(entry->value);
+      }
+
+      value->add_transition(&todo);
+    }
+
+    // Export the site score in aggregate for reporting
+    counters->transition_site_positive_score()->Increment(todo.score(DeferredTransitions::SCORE_POSITIVE));
+    counters->transition_site_negative_score()->Increment(todo.score(DeferredTransitions::SCORE_NEGATIVE));
+    counters->transition_site_neutral_score()->Increment(todo.score(DeferredTransitions::SCORE_NEUTRAL));
+  }
+}
+
+void HGraph::InsertElementsTransitions()
+{
+  ZoneAllocationPolicy allocator(zone());
+  HPhase phase("H_Place elements transitions", this);
+  
+  // ===========================================================================  
+  // Compute the equivalence classes of the LoadKeyed/StoreKeyed sites that need
+  // transitions.
+  FinalizeTransitionToDos(deferred_transitions_, GetMaximumValueID());
+
+  //
+  // IF in a forest of terminal nodes shared among some load/store keyed
+  // instructions, there are map transitions TO maps that are not in the same
+  // "floor" of the map tree, then all transitions involving those terminal

[danno, 2012/11/14 15:28:18]

to abuse the metaphor even more, maybe "trunk" instead of "floor"

[danno, 2012/11/14 15:28:18]

pre-transitioned input value?

+  // nodes must be left down at the load/store site, rather than factored up.
+  //
+  ZoneHashMap terminalMap(TerminalMatch,32,allocator);

[danno, 2012/11/14 15:28:18]

spaces after ,s

[mvstanton, 2012/11/16 15:15:06]

Done.

+  InitializeTerminalMap(terminalMap);
+ 
+  // Now that the map is created, run the unification algorithm
+  bool done = false;
+  while (!done) {
+    bool changed = false;
+    for (ZoneHashMap::Entry* p = terminalMap.Start(); p != NULL;
+         p = terminalMap.Next(p)) {
+      TerminalMapValue* value = reinterpret_cast<TerminalMapValue*>(p->value);
+      DeferredTransitions* cannotTransitionTodo = NULL;
+      HighestMapAndFamily newHighest;
+      ComputeHighest(value, &newHighest, &cannotTransitionTodo);
+      if (!newHighest.is_valid()) {
+        ASSERT(cannotTransitionTodo != NULL);
+        ScorchTerminalMap(allocator, zone(), cannotTransitionTodo, &terminalMap);
+        changed = true;
+        break;
+      }
+
+      if (value->highest() != newHighest) {
+        value->set_highest(newHighest);
+        changed = true;
+      }
+    }
+
+    done = !changed;
+  }
+
+  // Now we have the "to" value for each location, and todos have been divided into
+  // sets, including a set that couldn't be transitioned and is no longer represented
+  // in the terminalMap
+  // Handle each todo again.
+  if (FLAG_trace_transition_placement) {  
+    for (int i=0; i<deferred_transitions_.length(); i++) {
+      DeferredTransitions& todo = deferred_transitions_[i];
+      HeapStringAllocator string_allocator;
+      StringStream stream(&string_allocator);
+      todo.PrintTo(&stream);
+      PrintF("%s", *stream.ToCString());        
+    }
+  }
+
+  // Do the work
+  for (int i=0; i<deferred_transitions_.length(); i++) {
+    DeferredTransitions& todo = deferred_transitions_[i];
+
+    // All todos need to be finalized, even if we don't take action on them.
+    todo.Finalize();
+    
+    if (todo.invalid()) {
+      // We aren't moving this todo, leave it alone and visit the next
+      continue;
+    }
+
+    // 1) Remove the nonsmicheck.
+    todo.checknonsmi_instr()->DeleteAndReplaceWith(NULL);
+
+    // 2) alter the elementkind of the loadkeyed/storekeyed instruction if required.
+    // (note that steps a,b,c won't happen if the transition was marked as invalid because
+    //  it operates on a different map family)
+    // 2a) unlink transitions associated with this site from their current location
+    // 2b) Create appropriate transition instructions up at the terminal site.
+    // 2c) Fix the checkmaps instruction if required.
+
+    Handle<Map>& handle = StashedMapHandle(&deferred_transitions_, todo.highest());
+
+    for (int t=0; t<todo.terminal_nodes(); t++) {
+      HInstruction* terminal_node = todo.terminal_node(t);
+      ZoneHashMap::Entry* entry = terminalMap.Lookup(terminal_node,
+                                                     terminal_node->id(),
+                                                     false,
+                                                     allocator);
+      CHECK(entry->value != NULL);
+      TerminalMapValue* value = reinterpret_cast<TerminalMapValue*>(entry->value);
+      for (int r=0; r<todo.transitions(); r++) {
+        TransitionRecord& record = todo.transition_ref(r);
+        if (value->RequiresTransitionElementsKind(record.from())) {
+            
+          // We need to emit a transition.
+          ASSERT(terminal_node->IsInstruction());
+          HTransitionElementsKind* transition = new(zone())
+              HTransitionElementsKind(terminal_node, record.map_from(), handle);
+          value->InsertTransitionElementsKind(transition);
+
+          // Remove the transition from it's original location
+          if (record.transition_instruction()->block() != NULL) {
+            if (record.transition_instruction()->HasNoUses()) {
+              record.transition_instruction()->DeleteAndReplaceWith(NULL);
+            } else {
+              record.transition_instruction()->DeleteAndReplaceWith(transition);
+            }
+          }
+        }
+      }
+          
+      HCheckMaps* checkmaps = todo.checkmaps_instr();
+      if (checkmaps != NULL) {
+        // The checkmaps depends on the transition instruction we just unlinked.
+        // Conveniently, we can make it depend on the last instruction we just emitted.
+            
+        // We may need to update the map
+        // TODO(mvstanton) update the map instruction
+        // todo.mapcheck_instr()->
+        // one case:
+        // HCheckMaps* mapcheck = new(zone()) HCheckMaps(object, map,
+        //                                    zone(), dependency);
+        // other case:
+        // emitted_checkmaps = new(zone()) HCheckMaps(
+        //  elements, isolate()->factory()->fixed_array_map(),
+        // zone(), elements_kind_branch);
+
+        // I'm not sure what to do right now if this is > 1, so
+        // TODO(mvstanton): this assert is temporary
+        ASSERT(checkmaps->map_set()->length() == 1);
+        // Surgically replace the map in there
+        checkmaps->map_set()->Clear();
+        checkmaps->map_set()->Add(handle, zone());
+
+        // Remove the dependency, only keeping it if our new transition is in the same basic
+        // block as the checkmaps.
+        HTransitionElementsKind* lasttransition = value->last_transitionelementskind();        
+        if (checkmaps->has_typecheck()) {
+          if (lasttransition->block() == checkmaps->block()) {
+            checkmaps->SetOperandAt(1, lasttransition);
+          } else {
+            checkmaps->SetOperandAt(1, checkmaps->OperandAt(0));
+          }
+        }
+      }
+    }
+  }
+}
+
+
+template<class T>
+void FinishFastKeyedInitialization(T* instruction, ElementsKind elements_kind) {
+  instruction->PerformDeferredInitialization(elements_kind);
+}
+
+     
+
 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 788 matching lines @@
   }
   EliminateRedundantPhis();
   if (!CheckArgumentsPhiUses()) {
     *bailout_reason = SmartArrayPointer<char>(StrDup(
         "Unsupported phi use of arguments"));
     return false;
   }
   if (FLAG_eliminate_dead_phis) EliminateUnreachablePhis();
   CollectPhis();
 
+  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 2767 matching lines @@
     return load;
   }
 }
 
 
 HInstruction* HGraphBuilder::BuildFastElementAccess(HValue* elements,
                                                     HValue* checked_key,
                                                     HValue* val,
                                                     HValue* load_dependency,
                                                     ElementsKind elements_kind,
-                                                    bool is_store) {
+                                                    bool is_store,
+                                                    bool defer_initialization) {
   if (is_store) {
     ASSERT(val != NULL);
     switch (elements_kind) {
       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, defer_initialization);
       default:
         UNREACHABLE();
         return NULL;
     }
   }
   // It's an element load (!is_store).
   return new(zone()) HLoadKeyed(elements,
                                 checked_key,
                                 load_dependency,
-                                elements_kind);
+                                elements_kind, defer_initialization);
 }
 
 
 HInstruction* HGraphBuilder::BuildMonomorphicElementAccess(HValue* object,
                                                            HValue* key,
                                                            HValue* val,
                                                            HValue* dependency,
                                                            Handle<Map> map,
-                                                           bool is_store) {
+                                                           bool is_store,
+                                                           HCheckMaps** checkmap_instr) {
   HCheckMaps* mapcheck = new(zone()) HCheckMaps(object, map,
                                                 zone(), dependency);
   AddInstruction(mapcheck);
   if (dependency) {
     mapcheck->ClearGVNFlag(kDependsOnElementsKind);
   }
+
+  if (checkmap_instr != NULL) {
+    *checkmap_instr = mapcheck;
+  }
+  
   return BuildUncheckedMonomorphicElementAccess(object, key, val,
-                                                mapcheck, map, is_store);
+                                                mapcheck, map, is_store, dependency != NULL);
 }
 
 
 HInstruction* HGraphBuilder::BuildUncheckedMonomorphicElementAccess(
     HValue* object,
     HValue* key,
     HValue* val,
     HCheckMaps* mapcheck,
     Handle<Map> map,
-    bool is_store) {
+    bool is_store,
+    bool defer_initialization) {
   // No GVNFlag is necessary for ElementsKind if there is an explicit dependency
   // on a HElementsTransition instruction. The flag can also be removed if the
   // map to check has FAST_HOLEY_ELEMENTS, since there can be no further
   // ElementsKind transitions. Finally, the dependency can be removed for stores
   // for FAST_ELEMENTS, since a transition to HOLEY elements won't change the
   // generated store code.
   if ((map->elements_kind() == FAST_HOLEY_ELEMENTS) ||
       (map->elements_kind() == FAST_ELEMENTS && is_store)) {
     mapcheck->ClearGVNFlag(kDependsOnElementsKind);
   }
@@ skipping 25 matching lines @@
          map->has_fast_double_elements());
   if (map->instance_type() == JS_ARRAY_TYPE) {
     length = AddInstruction(new(zone()) HJSArrayLength(object, mapcheck,
                                                        HType::Smi()));
   } 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);
+                                map->elements_kind(), is_store, defer_initialization);
 }
 
 
 HInstruction* 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
@@ skipping 31 matching lines @@
             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(
-      object, key, val, check_maps, most_general_consolidated_map, false);
+      object, key, val, check_maps, most_general_consolidated_map, false, 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));
+  HCheckNonSmi* checknonsmi = new(zone()) HCheckNonSmi(object);
+  AddInstruction(checknonsmi);
   SmallMapList* maps = prop->GetReceiverTypes();
   bool todo_external_array = false;
 
   if (!is_store) {
+    // TODO(mvstanton): Should I reference this as a TODO for worst case transition?
     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) {
         consolidated_load->set_position(position);
       }
       return consolidated_load;
     }
@@ skipping 21 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<TransitionRecord> records(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);
+      
+      TransitionRecord tr(transition, map, transition_target.at(i));
+      records.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 {
+      // TODO(mvstanton): when we remove the transition what do we do about the
+      // parameter in the call to BuildMonomorphicElementAccess?
+      HCheckMaps *checkmaps = NULL;
       instr = AddInstruction(BuildMonomorphicElementAccess(
-          object, key, val, transition, untransitionable_map, is_store));
+          object, key, val, transition, untransitionable_map, is_store,
+          &checkmaps));
+
+      if (records.length() > 0) {
+        DeferredTransitions todo(instr,checknonsmi,checkmaps,zone());
+        todo.add_transitions(records);
+        graph()->AddDeferredTransitions(todo);
+      }
     }
     *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(
             elements, checked_key, val, elements_kind_branch,
-            elements_kind, is_store));
+            elements_kind, is_store, true));
         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(
             elements, checked_key, val, elements_kind_branch,
-            elements_kind, is_store));
+            elements_kind, is_store, true));
       } 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);
       }
+      
+      if (records.length() > 0) {
+        // Only move transitions for fast element types
+        if (IsFastElementsKind(elements_kind)) {
+          ASSERT(access->IsLoadKeyed() || access->IsStoreKeyed());
+          DeferredTransitions todo(access,checknonsmi,checkmaps,zone());
+          todo.add_transitions(records);
+          graph()->AddDeferredTransitions(todo);
+        }
+      }
+      
       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 3227 matching lines @@
 
 
 void HEnvironment::PrintToStd() {
   HeapStringAllocator string_allocator;
   StringStream trace(&string_allocator);
   PrintTo(&trace);
   PrintF("%s", *trace.ToCString());
 }
 
 
+TransitionRecord::TransitionRecord(HTransitionElementsKind* transition_instr,
+                                   Handle<Map> map_from, Handle<Map> map_to)
+    : transition_instr_(transition_instr),
+      map_from_(map_from),
+      map_to_(map_to),
+      optimistic_holey_() {
+
+  // When transition records are created, we have the chance to create map transitions we
+  // might need later. Transitions are unified during optimization, and we may need
+  // to transition from a packed fastmap to a holey version of same. But we can't create
+  // those transitions during optimization. Do it now, recognizing that when the handle
+  // disappears these maps may be collected if they didn't make it into usage in the
+  // optimized graph.
+
+  // TODO(mvstanton): generalize this service into "MakeWorstCaseMapForElementsKindTransition"
+  // (ie, not "holey")
+  if (IsFastPackedElementsKind(map_to->elements_kind())) {
+    ElementsKind holey_kind = GetHoleyElementsKind(map_to->elements_kind());
+    // The transition might already exist
+    Handle<Map> holey_map_handle(FindClosestElementsTransition(*map_to, holey_kind));
+    ASSERT(!holey_map_handle.is_null());
+    if (holey_map_handle->elements_kind() != holey_kind) {
+      MaybeObject* holey_map = AddMissingElementsTransitions(*map_to, holey_kind);
+      holey_map->ToHandle<Map>(&optimistic_holey_);
+    } else {
+      optimistic_holey_ = holey_map_handle;
+    }
+  } else {
+    optimistic_holey_ = map_to;
+  }
+  
+  ASSERT(!optimistic_holey_.is_null());
+  
+  // fill in map_family_
+  // Walk up to the base map from the map_to();
+  Handle<Map> end_map(FindClosestElementsTransition(*map_to, TERMINAL_FAST_ELEMENTS_KIND));
+  ASSERT(!end_map.is_null());
+  map_family_ = end_map;  
+}
+
+
+void DeferredTransitions::compute_highest() {
+  // Walk the transition records and find the "highest to" value, setting it.
+  Map* newHighest = *(transition(0).map_to().location());
+  set_highest(newHighest);
+}
+    
+
+void DeferredTransitions::ComputeTerminalNodes(int maximumGraphValueID) {
+  HValue* elements = NULL;
+  
+  if(instr()->IsStoreKeyed()) {
+    elements = HStoreKeyed::cast(instr())->elements();
+  } else {
+    CHECK(instr()->IsLoadKeyed());
+    elements = HLoadKeyed::cast(instr())->elements();
+  }
+
+  ASSERT(elements != NULL);
+  // Now get the item from the elements
+  ASSERT(elements->IsLoadElements());
+  HLoadElements *start = HLoadElements::cast(elements);
+  
+  ASSERT(terminal_nodes_->length() == 0);
+  BitVector visited(maximumGraphValueID, zone());
+  
+  ZoneList<HValue*> worklist(10, zone());
+  worklist.Add(start->value(), zone());
+
+  while (!worklist.is_empty()) {
+    HValue* value = worklist.RemoveLast();
+    // Have we visited this node?
+    if (!visited.Contains(value->id())) {
+      visited.Add(value->id());
+      if (value->IsPhi()) {
+        HPhi *phi = HPhi::cast(value);
+        for (int i=0; i<phi->OperandCount(); i++) {
+          worklist.Add(phi->OperandAt(i), zone());
+        }
+      } else {
+        // It must be a terminal node.
+        ASSERT(value->IsInstruction());
+        terminal_nodes_->Add(HInstruction::cast(value), zone());
+      }
+    }
+  }
+
+  // We must have found something.
+  ASSERT(terminal_nodes_->length() > 0);
+}
+
+
+void DeferredTransitions::PrintTo(StringStream* stream) const {
+  stream->Add("SITE: block%d %d: ", instr()->block()->block_id(), instr()->id());
+  instr()->PrintTo(stream);
+  stream->Add("\n");
+  
+  // Print validness
+  stream->Add("  VALIDITY: %s\n", invalid() ? "invalid" : "valid");
+  
+  // Print score
+  stream->Add("  SCORE: (+%d,%d,-%d)\n", score_[0], score_[1], score_[2]);
+  
+  // Find the def point for the instruction
+  HValue *elementsptr = NULL;
+  if(instr()->IsStoreKeyed()) {
+    elementsptr = HStoreKeyed::cast(instr())->elements();
+  } else {
+    ASSERT(instr()->IsLoadKeyed());
+    elementsptr = HLoadKeyed::cast(instr())->elements();
+  }
+
+  ASSERT(elementsptr != NULL);
+  // Now get the item from the elements
+  ASSERT(elementsptr->IsLoadElements());
+  HLoadElements *elements = HLoadElements::cast(elementsptr);
+  HValue *elementValue = elements->value();
+  stream->Add("  OBJECT: ");
+  elementValue->PrintNameTo(stream);
+  stream->Add("  ");
+  elementValue->PrintTo(stream);
+  stream->Add(" %s\n",elementValue->IsPhi() ? "PHI" : "");
+  stream->Add("  TRANSITIONS:\n");
+  ElementsKind transitionElementsKind = FAST_SMI_ELEMENTS;
+  for (int i = 0; i < transitions(); i++) {
+    stream->Add("    %s", ElementsKindToString(transition(i).from()));
+    stream->Add("(0x%p)-> ", *(transition(i).map_from()));
+    stream->Add("%s", ElementsKindToString(transition(i).to()));
+    stream->Add("(0x%p)\n", *(transition(i).map_to()));
+    transitionElementsKind = transition(i).to();
+  }
+
+  // Print possibly externally computed map
+  const char *signifier = (transitionElementsKind != highest()->elements_kind())
+      ? "*" : "";
+  stream->Add("  COMPUTED HIGHEST: %s%s(0x%p)\n", signifier,
+              ElementsKindToString(highest()->elements_kind()),
+              highest());
+
+  // Print terminal nodes if available
+  stream->Add("  TERMINAL NODES:\n");
+  for (int j=0; j < terminal_nodes(); j++) {
+    HValue* node = terminal_node(j);
+    stream->Add("    block%d %d: ", node->block()->block_id(), node->id());
+    node->PrintNameTo(stream);
+    stream->Add("  ");
+    node->PrintTo(stream);
+    stream->Add("\n");
+  }
+
+}
+
+
+void DeferredTransitions::PrintToStd() const {
+  HeapStringAllocator string_allocator;
+  StringStream trace(&string_allocator);
+  PrintTo(&trace);
+  PrintF("%s", *trace.ToCString());
+}
+
+
 void HTracer::TraceCompilation(FunctionLiteral* function) {
   Tag tag(this, "compilation");
   Handle<String> name = function->debug_name();
   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 300 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify(false);  // No full verify.
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal