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

src/hydrogen.h

 // 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 221 matching lines @@
 
  private:
   void AddBlock(HBasicBlock* block);
 
   ZoneList<HBasicBlock*> back_edges_;
   HBasicBlock* loop_header_;
   ZoneList<HBasicBlock*> blocks_;
   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:
   explicit HGraph(CompilationInfo* info);
 
   Isolate* isolate() { return isolate_; }
   Zone* zone() const { return zone_; }
   CompilationInfo* info() const { return info_; }
 
   const ZoneList<HBasicBlock*>* blocks() const { return &blocks_; }
@@ skipping 107 matching lines @@
     return is_recursive_;
   }
 
   void RecordUint32Instruction(HInstruction* instr) {
     if (uint32_instructions_ == NULL) {
       uint32_instructions_ = new(zone()) ZoneList<HInstruction*>(4, zone());
     }
     uint32_instructions_->Add(instr, zone());
   }
 
+  void AddDeferredTransitions(const DeferredTransitions& todo) {
+    deferred_transitions_.Add(todo, zone());
+  }
+  
  private:
   HConstant* GetConstant(SetOncePointer<HConstant>* pointer,
                          Handle<Object> value);
   HConstant* GetConstantInt32(SetOncePointer<HConstant>* pointer,
                               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);
   void InsertRepresentationChangeForUse(HValue* value,
                                         HValue* use_value,
                                         int use_index,
                                         Representation to);
   void InsertRepresentationChangesForValue(HValue* value);
   void InferTypes(ZoneList<HValue*>* worklist);
   void InitializeInferredTypes(int from_inclusive, int to_inclusive);
   void CheckForBackEdge(HBasicBlock* block, HBasicBlock* successor);
   void EliminateRedundantBoundsChecks(HBasicBlock* bb, BoundsCheckTable* table);
 
   Isolate* isolate_;
   int next_block_id_;
   HBasicBlock* entry_block_;
   HEnvironment* start_environment_;
   ZoneList<HBasicBlock*> blocks_;
   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_;
   SetOncePointer<HConstant> constant_true_;
   SetOncePointer<HConstant> constant_false_;
   SetOncePointer<HConstant> constant_hole_;
   SetOncePointer<HArgumentsObject> arguments_object_;
 
   SetOncePointer<HBasicBlock> osr_loop_entry_;
   SetOncePointer<ZoneList<HUnknownOSRValue*> > osr_values_;
@@ skipping 447 matching lines @@
 
     // Search the break stack for a break or continue target.
     HBasicBlock* Get(BreakableStatement* stmt, BreakType type, int* drop_extra);
 
    private:
     BreakAndContinueInfo* info_;
     HGraphBuilder* owner_;
     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();
 
   // Simple accessors.
   HGraph* graph() const { return graph_; }
   BreakAndContinueScope* break_scope() const { return break_scope_; }
   void set_break_scope(BreakAndContinueScope* head) { break_scope_ = head; }
 
   HBasicBlock* current_block() const { return current_block_; }
@@ skipping 243 matching lines @@
   HInstruction* BuildBinaryOperation(BinaryOperation* expr,
                                      HValue* left,
                                      HValue* right);
   HInstruction* BuildIncrement(bool returns_original_input,
                                CountOperation* expr);
   HInstruction* BuildFastElementAccess(HValue* elements,
                                        HValue* checked_key,
                                        HValue* val,
                                        HValue* dependency,
                                        ElementsKind elements_kind,
-                                       bool is_store);
+                                       bool is_store,
+                                       bool defer_initialization);
 
   HInstruction* TryBuildConsolidatedElementLoad(HValue* object,
                                                 HValue* key,
                                                 HValue* val,
                                                 SmallMapList* maps);
 
   HInstruction* BuildUncheckedMonomorphicElementAccess(HValue* object,
                                                        HValue* key,
                                                        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,
                                          HValue* val,
                                          Expression* prop,
                                          BailoutId ast_id,
                                          int position,
                                          bool is_store,
                                          bool* has_side_effects);
 
@@ skipping 339 matching lines @@
   const char* filename_;
   HeapStringAllocator string_allocator_;
   StringStream trace_;
   int indent_;
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_HYDROGEN_H_