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

src/hydrogen.h

Index: src/hydrogen.h
diff --git a/src/hydrogen.h b/src/hydrogen.h
index 3748970585155bb876219b0a70a777aa9b49e32f..0b26b202da833f7f57d54f0d3d9087598e450198 100644
--- a/src/hydrogen.h
+++ b/src/hydrogen.h
@@ -239,6 +239,149 @@ class HLoopInformation: public ZoneObject {
   HStackCheck* stack_check_;
 };
 
+
+class TransitionRecord BASE_EMBEDDED {

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

I hate being overly fussy about names, but they are important. How about these
bad suggestions:
TransitionElementsMemento?
TransitionElementsBookmark?
PontentialTransitionElements?
I guess what's missing in the name is what kind of name (therefore + "Elements")
and what it actually does: remembers that a transition needs to be accounted for
later (e.g. "Memento"). You can probably do better than I, tho.

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

Bad suggestion TransitionElementsBookmark sounds perfect.

+ public:
+  TransitionRecord(HTransitionElementsKind* transition_instr, Handle<Map> map_from,

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

80 col

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

Done.

+                   Handle<Map> map_to);
+  ElementsKind from() const { return map_from_->elements_kind(); }
+  ElementsKind to() const { return map_to_->elements_kind(); }
+  Handle<Map> map_from() const { return map_from_; }
+  Handle<Map> map_to() const { return map_to_; }
+  Handle<Map>& map_to_ref() { return map_to_; }    

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

We really avoid & (refs) everywhere else in the code. Does this allow you to
change the map? If so, add a set_map_to method.

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

Done.

+  Handle<Map> map_family() const { return map_family_; }
+  Handle<Map> optimistic_holey() const { return optimistic_holey_; }
+  Handle<Map>& optimistic_holey_ref() { return optimistic_holey_; }

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

Again, please void the ref.

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

Done.

+  HTransitionElementsKind* transition_instruction() const { return transition_instr_; }
+  
+  bool equal(const TransitionRecord& other) const {

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

Equals

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

Done.

+    return *map_from() == *(other.map_from()) && *map_to() == *(other.map_to()) &&
+        *map_family() == *(other.map_family());
+  }
+    
+ private:
+  HTransitionElementsKind* transition_instr_;

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

Just transition_?

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

Done.

+  Handle<Map> map_from_;

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

how about just "from_", "to_", "family_" 

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

Done.

+  Handle<Map> map_to_;
+  Handle<Map> map_family_;
+  Handle<Map> optimistic_holey_;

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

Isn't this the "pesimistic_holey_" map? i.e. the one you will have to use in the
worst case?

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

Done.

+};
+
+
+typedef ZoneList<HInstruction*> TerminalNodeList;

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

Are these HInstructions or HValues? If it's just HValues, then move this typedef
into hydrogen-instructions, and call it simply HValueList.

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

I do treat them as HInstructions a few times...

+
+class DeferredTransitions BASE_EMBEDDED {

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

PontentialTransitionElementsGroup?

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

I went with MarkedTransitionElementsGroup. "marking" and "bookmarks" maybe that
is a good metaphor. We mark them, and might later use them to optimize, or maybe
not.

+ public:
+  DeferredTransitions(HInstruction* keyedInstr, HCheckNonSmi* checknonsmi,

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

keyed_instruction and other style guide stuff on other parameters.

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

Done.

+                  HCheckMaps* checkmaps, Zone* zone)
+      : zone_(zone), keyed_instr_(keyedInstr), checknonsmi_instr_(checknonsmi),

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

In general, for variables and members, separate every word with a "_" and no
abbreviations if possible, so "check_non_smi_instruction_" and check_non_smi

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

Done.

+      checkmaps_instr_(checkmaps),
+      invalid_(false),
+      records_(new (zone) ZoneList<TransitionRecord>(10, zone)),
+      terminal_nodes_(new (zone) TerminalNodeList(10, zone)) {
+    ASSERT((keyedInstr->IsLoadKeyed() &&
+            !HLoadKeyed::cast(keyedInstr)->Initialized()) ||
+           (keyedInstr->IsStoreKeyed() &&
+            !HStoreKeyed::cast(keyedInstr)->Initialized()));
+    score_[0] = score_[1] = score_[2] = 0;
+  }
+
+  HInstruction* instr() const { return keyed_instr_; }
+  HCheckMaps* checkmaps_instr() { return checkmaps_instr_; }
+  HCheckNonSmi* checknonsmi_instr() { return checknonsmi_instr_; }
+  
+  void add_transitions(const ZoneList<TransitionRecord>& records) {

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

"AddTransitions". Only trivial variable accessors (get/set) should be lower case
and use "_", all other method names should be CamelCase

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

Done.

+    // Doesn't check for duplications
+    for (int i=0; i<records.length(); i++) {
+      records_->Add(records[i], zone_);
+    }
+  }
+
+  void add_transition(const TransitionRecord& record) {
+    records_->Add(record, zone_);
+  }
+
+  int transitions() const { return records_->length(); }
+  const TransitionRecord& transition(int index) const {
+    return (*records_)[index];
+  }
+
+  TransitionRecord& transition_ref(int index) {
+    return records_->at(index);
+  }
+
+  void PrintTo(StringStream* stream) const;
+  void PrintToStd() const;
+
+  // Populate terminal_nodes, initially empty
+  void ComputeTerminalNodes(int maximumGraphValueID);
+
+  int terminal_nodes() const { return terminal_nodes_->length(); }
+  HInstruction* terminal_node(int index) const { return (*terminal_nodes_)[index]; }
+
+  enum ScoreType {
+    SCORE_POSITIVE,
+    SCORE_NEGATIVE,
+    SCORE_NEUTRAL

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

, SCORE_TYPE_COUNT  // Must be last

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

Done.

+  };
+
+  ScoreType scoretype_from_loopdelta(int loopDelta) const {
+    if (loopDelta > 0) return SCORE_POSITIVE;
+    else if(loopDelta < 0) return SCORE_NEGATIVE;
+    return SCORE_NEUTRAL;
+  }
+  
+  int score(ScoreType type) const { return score_[type]; }
+  void increment_score(ScoreType type, int score) { score_[type] += score; }
+
+  bool invalid() const { return invalid_; }
+  void set_invalid() { invalid_ = true; }
+
+  void set_highest(Map* new_highest) { computed_highest_ = new_highest; }
+  Map* highest() const { return computed_highest_; }
+
+  void Finalize() {
+    ASSERT(highest() != NULL);
+    ElementsKind elements_kind = highest()->elements_kind();
+    if (instr()->IsLoadKeyed()) {
+      HLoadKeyed::cast(instr())->PerformDeferredInitialization(elements_kind);

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

Is it possible to move PerformDeferredInitialization into
ArrayInstructionInterface?

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

Done.

+    } else {
+      ASSERT(instr()->IsStoreKeyed());
+      HStoreKeyed::cast(instr())->PerformDeferredInitialization(elements_kind);
+    }
+  }
+    
+  // Fill in highest from local values
+  void compute_highest();
+  Zone* zone() const { return zone_; }
+
+  Map* map_family() const {
+    Map* family = NULL;
+    if (transitions()) {
+      family = *(transition(0).map_family().location());
+    }
+    
+#ifdef DEBUG
+    for (int i=1; i<transitions(); i++) {
+      const TransitionRecord& tr = transition(i);
+      ASSERT(*(tr.map_family().location()) == family);
+    }
+#endif
+    return family;
+  }
+  
+ private:
+  Zone* zone_;
+  HInstruction *keyed_instr_;

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

load_or_store_?

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

Done.

+  HCheckNonSmi* checknonsmi_instr_;

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

how about just smi_check_?

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

Done.

+  HCheckMaps* checkmaps_instr_;

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

map_check_?

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

Done.

+  Map* computed_highest_;
+  int score_[3];

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

score_[SCORE_TYPE_COUNT]

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

Done.

+  bool invalid_;
+  ZoneList<TransitionRecord> *records_;
+  TerminalNodeList *terminal_nodes_;

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

I think "Terminal" might not be the right to use. I think something like
"pre_transitioned_values_" might be better.

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

Done.

+};
+
 class BoundsCheckTable;
 class HGraph: public ZoneObject {
  public:
@@ -366,6 +509,10 @@ class HGraph: public ZoneObject {
     uint32_instructions_->Add(instr, zone());
   }
 
+  void AddDeferredTransitions(const DeferredTransitions& todo) {
+    deferred_transitions_.Add(todo, zone());
+  }
+  
  private:
   HConstant* GetConstant(SetOncePointer<HConstant>* pointer,
                          Handle<Object> value);
@@ -373,6 +520,8 @@ class HGraph: public ZoneObject {
                               int32_t integer_value);
 
   void MarkAsDeoptimizingRecursively(HBasicBlock* block);
+  void InsertElementsTransitions();
+  void InitializeTerminalMap(ZoneHashMap& terminalMap);
   void InsertTypeConversions(HInstruction* instr);
   void PropagateMinusZeroChecks(HValue* value, BitVector* visited);
   void RecursivelyMarkPhiDeoptimizeOnUndefined(HPhi* phi);
@@ -394,6 +543,7 @@ class HGraph: public ZoneObject {
   ZoneList<HValue*> values_;
   ZoneList<HPhi*>* phi_list_;
   ZoneList<HInstruction*>* uint32_instructions_;
+  ZoneList<DeferredTransitions> deferred_transitions_;
   SetOncePointer<HConstant> undefined_constant_;
   SetOncePointer<HConstant> constant_1_;
   SetOncePointer<HConstant> constant_minus1_;
@@ -861,6 +1011,7 @@ class HGraphBuilder: public AstVisitor {
     BreakAndContinueScope* next_;
   };
 
+    

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

nit: extra whitespace :-)

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

Done.

   HGraphBuilder(CompilationInfo* info, TypeFeedbackOracle* oracle);
 
   HGraph* CreateGraph();
@@ -1124,7 +1275,8 @@ class HGraphBuilder: public AstVisitor {
                                        HValue* val,
                                        HValue* dependency,
                                        ElementsKind elements_kind,
-                                       bool is_store);
+                                       bool is_store,
+                                       bool defer_initialization);
 
   HInstruction* TryBuildConsolidatedElementLoad(HValue* object,
                                                 HValue* key,
@@ -1136,14 +1288,16 @@ class HGraphBuilder: public AstVisitor {
                                                        HValue* val,
                                                        HCheckMaps* mapcheck,
                                                        Handle<Map> map,
-                                                       bool is_store);
+                                                       bool is_store,
+                                                       bool defer_initialization);
 
   HInstruction* BuildMonomorphicElementAccess(HValue* object,
                                               HValue* key,
                                               HValue* val,
                                               HValue* dependency,
                                               Handle<Map> map,
-                                              bool is_store);
+                                              bool is_store,
+                                              HCheckMaps** checkmap_instr=NULL);

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

extra <sp> around =

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

Done.

 
   HValue* HandlePolymorphicElementAccess(HValue* object,
                                          HValue* key,