Home | History | Annotate | Download | only in crankshaft 
      1 // Copyright 2013 the V8 project authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #include "src/crankshaft/hydrogen-gvn.h"
      6 
      7 #include "src/crankshaft/hydrogen.h"
      8 #include "src/objects-inl.h"
      9 #include "src/v8.h"
     10 
     11 namespace v8 {
     12 namespace internal {
     13 
     14 class HInstructionMap final : public ZoneObject {
     15  public:
     16   HInstructionMap(Zone* zone, SideEffectsTracker* side_effects_tracker)
     17       : array_size_(0),
     18         lists_size_(0),
     19         count_(0),
     20         array_(NULL),
     21         lists_(NULL),
     22         free_list_head_(kNil),
     23         side_effects_tracker_(side_effects_tracker) {
     24     ResizeLists(kInitialSize, zone);
     25     Resize(kInitialSize, zone);
     26   }
     27 
     28   void Kill(SideEffects side_effects);
     29 
     30   void Add(HInstruction* instr, Zone* zone) {
     31     present_depends_on_.Add(side_effects_tracker_->ComputeDependsOn(instr));
     32     Insert(instr, zone);
     33   }
     34 
     35   HInstruction* Lookup(HInstruction* instr) const;
     36 
     37   HInstructionMap* Copy(Zone* zone) const {
     38     return new(zone) HInstructionMap(zone, this);
     39   }
     40 
     41   bool IsEmpty() const { return count_ == 0; }
     42 
     43  private:
     44   // A linked list of HInstruction* values.  Stored in arrays.
     45   struct HInstructionMapListElement {
     46     HInstruction* instr;
     47     int next;  // Index in the array of the next list element.
     48   };
     49   static const int kNil = -1;  // The end of a linked list
     50 
     51   // Must be a power of 2.
     52   static const int kInitialSize = 16;
     53 
     54   HInstructionMap(Zone* zone, const HInstructionMap* other);
     55 
     56   void Resize(int new_size, Zone* zone);
     57   void ResizeLists(int new_size, Zone* zone);
     58   void Insert(HInstruction* instr, Zone* zone);
     59   uint32_t Bound(uint32_t value) const { return value & (array_size_ - 1); }
     60 
     61   int array_size_;
     62   int lists_size_;
     63   int count_;  // The number of values stored in the HInstructionMap.
     64   SideEffects present_depends_on_;
     65   HInstructionMapListElement* array_;
     66   // Primary store - contains the first value
     67   // with a given hash.  Colliding elements are stored in linked lists.
     68   HInstructionMapListElement* lists_;
     69   // The linked lists containing hash collisions.
     70   int free_list_head_;  // Unused elements in lists_ are on the free list.
     71   SideEffectsTracker* side_effects_tracker_;
     72 };
     73 
     74 
     75 class HSideEffectMap final BASE_EMBEDDED {
     76  public:
     77   HSideEffectMap();
     78   explicit HSideEffectMap(HSideEffectMap* other);
     79   HSideEffectMap& operator= (const HSideEffectMap& other);
     80 
     81   void Kill(SideEffects side_effects);
     82 
     83   void Store(SideEffects side_effects, HInstruction* instr);
     84 
     85   bool IsEmpty() const { return count_ == 0; }
     86 
     87   inline HInstruction* operator[](int i) const {
     88     DCHECK(0 <= i);
     89     DCHECK(i < kNumberOfTrackedSideEffects);
     90     return data_[i];
     91   }
     92   inline HInstruction* at(int i) const { return operator[](i); }
     93 
     94  private:
     95   int count_;
     96   HInstruction* data_[kNumberOfTrackedSideEffects];
     97 };
     98 
     99 
    100 void TraceGVN(const char* msg, ...) {
    101   va_list arguments;
    102   va_start(arguments, msg);
    103   base::OS::VPrint(msg, arguments);
    104   va_end(arguments);
    105 }
    106 
    107 
    108 // Wrap TraceGVN in macros to avoid the expense of evaluating its arguments when
    109 // --trace-gvn is off.
    110 #define TRACE_GVN_1(msg, a1)                    \
    111   if (FLAG_trace_gvn) {                         \
    112     TraceGVN(msg, a1);                          \
    113   }
    114 
    115 #define TRACE_GVN_2(msg, a1, a2)                \
    116   if (FLAG_trace_gvn) {                         \
    117     TraceGVN(msg, a1, a2);                      \
    118   }
    119 
    120 #define TRACE_GVN_3(msg, a1, a2, a3)            \
    121   if (FLAG_trace_gvn) {                         \
    122     TraceGVN(msg, a1, a2, a3);                  \
    123   }
    124 
    125 #define TRACE_GVN_4(msg, a1, a2, a3, a4)        \
    126   if (FLAG_trace_gvn) {                         \
    127     TraceGVN(msg, a1, a2, a3, a4);              \
    128   }
    129 
    130 #define TRACE_GVN_5(msg, a1, a2, a3, a4, a5)    \
    131   if (FLAG_trace_gvn) {                         \
    132     TraceGVN(msg, a1, a2, a3, a4, a5);          \
    133   }
    134 
    135 
    136 HInstructionMap::HInstructionMap(Zone* zone, const HInstructionMap* other)
    137     : array_size_(other->array_size_),
    138       lists_size_(other->lists_size_),
    139       count_(other->count_),
    140       present_depends_on_(other->present_depends_on_),
    141       array_(zone->NewArray<HInstructionMapListElement>(other->array_size_)),
    142       lists_(zone->NewArray<HInstructionMapListElement>(other->lists_size_)),
    143       free_list_head_(other->free_list_head_),
    144       side_effects_tracker_(other->side_effects_tracker_) {
    145   MemCopy(array_, other->array_,
    146           array_size_ * sizeof(HInstructionMapListElement));
    147   MemCopy(lists_, other->lists_,
    148           lists_size_ * sizeof(HInstructionMapListElement));
    149 }
    150 
    151 
    152 void HInstructionMap::Kill(SideEffects changes) {
    153   if (!present_depends_on_.ContainsAnyOf(changes)) return;
    154   present_depends_on_.RemoveAll();
    155   for (int i = 0; i < array_size_; ++i) {
    156     HInstruction* instr = array_[i].instr;
    157     if (instr != NULL) {
    158       // Clear list of collisions first, so we know if it becomes empty.
    159       int kept = kNil;  // List of kept elements.
    160       int next;
    161       for (int current = array_[i].next; current != kNil; current = next) {
    162         next = lists_[current].next;
    163         HInstruction* instr = lists_[current].instr;
    164         SideEffects depends_on = side_effects_tracker_->ComputeDependsOn(instr);
    165         if (depends_on.ContainsAnyOf(changes)) {
    166           // Drop it.
    167           count_--;
    168           lists_[current].next = free_list_head_;
    169           free_list_head_ = current;
    170         } else {
    171           // Keep it.
    172           lists_[current].next = kept;
    173           kept = current;
    174           present_depends_on_.Add(depends_on);
    175         }
    176       }
    177       array_[i].next = kept;
    178 
    179       // Now possibly drop directly indexed element.
    180       instr = array_[i].instr;
    181       SideEffects depends_on = side_effects_tracker_->ComputeDependsOn(instr);
    182       if (depends_on.ContainsAnyOf(changes)) {  // Drop it.
    183         count_--;
    184         int head = array_[i].next;
    185         if (head == kNil) {
    186           array_[i].instr = NULL;
    187         } else {
    188           array_[i].instr = lists_[head].instr;
    189           array_[i].next = lists_[head].next;
    190           lists_[head].next = free_list_head_;
    191           free_list_head_ = head;
    192         }
    193       } else {
    194         present_depends_on_.Add(depends_on);  // Keep it.
    195       }
    196     }
    197   }
    198 }
    199 
    200 
    201 HInstruction* HInstructionMap::Lookup(HInstruction* instr) const {
    202   uint32_t hash = static_cast<uint32_t>(instr->Hashcode());
    203   uint32_t pos = Bound(hash);
    204   if (array_[pos].instr != NULL) {
    205     if (array_[pos].instr->Equals(instr)) return array_[pos].instr;
    206     int next = array_[pos].next;
    207     while (next != kNil) {
    208       if (lists_[next].instr->Equals(instr)) return lists_[next].instr;
    209       next = lists_[next].next;
    210     }
    211   }
    212   return NULL;
    213 }
    214 
    215 
    216 void HInstructionMap::Resize(int new_size, Zone* zone) {
    217   DCHECK(new_size > count_);
    218   // Hashing the values into the new array has no more collisions than in the
    219   // old hash map, so we can use the existing lists_ array, if we are careful.
    220 
    221   // Make sure we have at least one free element.
    222   if (free_list_head_ == kNil) {
    223     ResizeLists(lists_size_ << 1, zone);
    224   }
    225 
    226   HInstructionMapListElement* new_array =
    227       zone->NewArray<HInstructionMapListElement>(new_size);
    228   memset(new_array, 0, sizeof(HInstructionMapListElement) * new_size);
    229 
    230   HInstructionMapListElement* old_array = array_;
    231   int old_size = array_size_;
    232 
    233   int old_count = count_;
    234   count_ = 0;
    235   // Do not modify present_depends_on_.  It is currently correct.
    236   array_size_ = new_size;
    237   array_ = new_array;
    238 
    239   if (old_array != NULL) {
    240     // Iterate over all the elements in lists, rehashing them.
    241     for (int i = 0; i < old_size; ++i) {
    242       if (old_array[i].instr != NULL) {
    243         int current = old_array[i].next;
    244         while (current != kNil) {
    245           Insert(lists_[current].instr, zone);
    246           int next = lists_[current].next;
    247           lists_[current].next = free_list_head_;
    248           free_list_head_ = current;
    249           current = next;
    250         }
    251         // Rehash the directly stored instruction.
    252         Insert(old_array[i].instr, zone);
    253       }
    254     }
    255   }
    256   USE(old_count);
    257   DCHECK(count_ == old_count);
    258 }
    259 
    260 
    261 void HInstructionMap::ResizeLists(int new_size, Zone* zone) {
    262   DCHECK(new_size > lists_size_);
    263 
    264   HInstructionMapListElement* new_lists =
    265       zone->NewArray<HInstructionMapListElement>(new_size);
    266   memset(new_lists, 0, sizeof(HInstructionMapListElement) * new_size);
    267 
    268   HInstructionMapListElement* old_lists = lists_;
    269   int old_size = lists_size_;
    270 
    271   lists_size_ = new_size;
    272   lists_ = new_lists;
    273 
    274   if (old_lists != NULL) {
    275     MemCopy(lists_, old_lists, old_size * sizeof(HInstructionMapListElement));
    276   }
    277   for (int i = old_size; i < lists_size_; ++i) {
    278     lists_[i].next = free_list_head_;
    279     free_list_head_ = i;
    280   }
    281 }
    282 
    283 
    284 void HInstructionMap::Insert(HInstruction* instr, Zone* zone) {
    285   DCHECK(instr != NULL);
    286   // Resizing when half of the hashtable is filled up.
    287   if (count_ >= array_size_ >> 1) Resize(array_size_ << 1, zone);
    288   DCHECK(count_ < array_size_);
    289   count_++;
    290   uint32_t pos = Bound(static_cast<uint32_t>(instr->Hashcode()));
    291   if (array_[pos].instr == NULL) {
    292     array_[pos].instr = instr;
    293     array_[pos].next = kNil;
    294   } else {
    295     if (free_list_head_ == kNil) {
    296       ResizeLists(lists_size_ << 1, zone);
    297     }
    298     int new_element_pos = free_list_head_;
    299     DCHECK(new_element_pos != kNil);
    300     free_list_head_ = lists_[free_list_head_].next;
    301     lists_[new_element_pos].instr = instr;
    302     lists_[new_element_pos].next = array_[pos].next;
    303     DCHECK(array_[pos].next == kNil || lists_[array_[pos].next].instr != NULL);
    304     array_[pos].next = new_element_pos;
    305   }
    306 }
    307 
    308 
    309 HSideEffectMap::HSideEffectMap() : count_(0) {
    310   memset(data_, 0, kNumberOfTrackedSideEffects * kPointerSize);
    311 }
    312 
    313 
    314 HSideEffectMap::HSideEffectMap(HSideEffectMap* other) : count_(other->count_) {
    315   *this = *other;  // Calls operator=.
    316 }
    317 
    318 
    319 HSideEffectMap& HSideEffectMap::operator=(const HSideEffectMap& other) {
    320   if (this != &other) {
    321     MemCopy(data_, other.data_, kNumberOfTrackedSideEffects * kPointerSize);
    322   }
    323   return *this;
    324 }
    325 
    326 
    327 void HSideEffectMap::Kill(SideEffects side_effects) {
    328   for (int i = 0; i < kNumberOfTrackedSideEffects; i++) {
    329     if (side_effects.ContainsFlag(GVNFlagFromInt(i))) {
    330       if (data_[i] != NULL) count_--;
    331       data_[i] = NULL;
    332     }
    333   }
    334 }
    335 
    336 
    337 void HSideEffectMap::Store(SideEffects side_effects, HInstruction* instr) {
    338   for (int i = 0; i < kNumberOfTrackedSideEffects; i++) {
    339     if (side_effects.ContainsFlag(GVNFlagFromInt(i))) {
    340       if (data_[i] == NULL) count_++;
    341       data_[i] = instr;
    342     }
    343   }
    344 }
    345 
    346 
    347 SideEffects SideEffectsTracker::ComputeChanges(HInstruction* instr) {
    348   int index;
    349   SideEffects result(instr->ChangesFlags());
    350   if (result.ContainsFlag(kGlobalVars)) {
    351     if (instr->IsStoreNamedField()) {
    352       HStoreNamedField* store = HStoreNamedField::cast(instr);
    353       HConstant* target = HConstant::cast(store->object());
    354       if (ComputeGlobalVar(Unique<PropertyCell>::cast(target->GetUnique()),
    355                            &index)) {
    356         result.RemoveFlag(kGlobalVars);
    357         result.AddSpecial(GlobalVar(index));
    358         return result;
    359       }
    360     }
    361     for (index = 0; index < kNumberOfGlobalVars; ++index) {
    362       result.AddSpecial(GlobalVar(index));
    363     }
    364   } else if (result.ContainsFlag(kInobjectFields)) {
    365     if (instr->IsStoreNamedField() &&
    366         ComputeInobjectField(HStoreNamedField::cast(instr)->access(), &index)) {
    367       result.RemoveFlag(kInobjectFields);
    368       result.AddSpecial(InobjectField(index));
    369     } else {
    370       for (index = 0; index < kNumberOfInobjectFields; ++index) {
    371         result.AddSpecial(InobjectField(index));
    372       }
    373     }
    374   }
    375   return result;
    376 }
    377 
    378 
    379 SideEffects SideEffectsTracker::ComputeDependsOn(HInstruction* instr) {
    380   int index;
    381   SideEffects result(instr->DependsOnFlags());
    382   if (result.ContainsFlag(kGlobalVars)) {
    383     if (instr->IsLoadNamedField()) {
    384       HLoadNamedField* load = HLoadNamedField::cast(instr);
    385       HConstant* target = HConstant::cast(load->object());
    386       if (ComputeGlobalVar(Unique<PropertyCell>::cast(target->GetUnique()),
    387                            &index)) {
    388         result.RemoveFlag(kGlobalVars);
    389         result.AddSpecial(GlobalVar(index));
    390         return result;
    391       }
    392     }
    393     for (index = 0; index < kNumberOfGlobalVars; ++index) {
    394       result.AddSpecial(GlobalVar(index));
    395     }
    396   } else if (result.ContainsFlag(kInobjectFields)) {
    397     if (instr->IsLoadNamedField() &&
    398         ComputeInobjectField(HLoadNamedField::cast(instr)->access(), &index)) {
    399       result.RemoveFlag(kInobjectFields);
    400       result.AddSpecial(InobjectField(index));
    401     } else {
    402       for (index = 0; index < kNumberOfInobjectFields; ++index) {
    403         result.AddSpecial(InobjectField(index));
    404       }
    405     }
    406   }
    407   return result;
    408 }
    409 
    410 
    411 std::ostream& operator<<(std::ostream& os, const TrackedEffects& te) {
    412   SideEffectsTracker* t = te.tracker;
    413   const char* separator = "";
    414   os << "[";
    415   for (int bit = 0; bit < kNumberOfFlags; ++bit) {
    416     GVNFlag flag = GVNFlagFromInt(bit);
    417     if (te.effects.ContainsFlag(flag)) {
    418       os << separator;
    419       separator = ", ";
    420       switch (flag) {
    421 #define DECLARE_FLAG(Type) \
    422   case k##Type:            \
    423     os << #Type;           \
    424     break;
    425 GVN_TRACKED_FLAG_LIST(DECLARE_FLAG)
    426 GVN_UNTRACKED_FLAG_LIST(DECLARE_FLAG)
    427 #undef DECLARE_FLAG
    428         default:
    429             break;
    430       }
    431     }
    432   }
    433   for (int index = 0; index < t->num_global_vars_; ++index) {
    434     if (te.effects.ContainsSpecial(t->GlobalVar(index))) {
    435       os << separator << "[" << *t->global_vars_[index].handle() << "]";
    436       separator = ", ";
    437     }
    438   }
    439   for (int index = 0; index < t->num_inobject_fields_; ++index) {
    440     if (te.effects.ContainsSpecial(t->InobjectField(index))) {
    441       os << separator << t->inobject_fields_[index];
    442       separator = ", ";
    443     }
    444   }
    445   os << "]";
    446   return os;
    447 }
    448 
    449 
    450 bool SideEffectsTracker::ComputeGlobalVar(Unique<PropertyCell> cell,
    451                                           int* index) {
    452   for (int i = 0; i < num_global_vars_; ++i) {
    453     if (cell == global_vars_[i]) {
    454       *index = i;
    455       return true;
    456     }
    457   }
    458   if (num_global_vars_ < kNumberOfGlobalVars) {
    459     if (FLAG_trace_gvn) {
    460       OFStream os(stdout);
    461       os << "Tracking global var [" << *cell.handle() << "] "
    462          << "(mapped to index " << num_global_vars_ << ")" << std::endl;
    463     }
    464     *index = num_global_vars_;
    465     global_vars_[num_global_vars_++] = cell;
    466     return true;
    467   }
    468   return false;
    469 }
    470 
    471 
    472 bool SideEffectsTracker::ComputeInobjectField(HObjectAccess access,
    473                                               int* index) {
    474   for (int i = 0; i < num_inobject_fields_; ++i) {
    475     if (access.Equals(inobject_fields_[i])) {
    476       *index = i;
    477       return true;
    478     }
    479   }
    480   if (num_inobject_fields_ < kNumberOfInobjectFields) {
    481     if (FLAG_trace_gvn) {
    482       OFStream os(stdout);
    483       os << "Tracking inobject field access " << access << " (mapped to index "
    484          << num_inobject_fields_ << ")" << std::endl;
    485     }
    486     *index = num_inobject_fields_;
    487     inobject_fields_[num_inobject_fields_++] = access;
    488     return true;
    489   }
    490   return false;
    491 }
    492 
    493 
    494 HGlobalValueNumberingPhase::HGlobalValueNumberingPhase(HGraph* graph)
    495     : HPhase("H_Global value numbering", graph),
    496       removed_side_effects_(false),
    497       block_side_effects_(graph->blocks()->length(), zone()),
    498       loop_side_effects_(graph->blocks()->length(), zone()),
    499       visited_on_paths_(graph->blocks()->length(), zone()) {
    500   DCHECK(!AllowHandleAllocation::IsAllowed());
    501   block_side_effects_.AddBlock(
    502       SideEffects(), graph->blocks()->length(), zone());
    503   loop_side_effects_.AddBlock(
    504       SideEffects(), graph->blocks()->length(), zone());
    505 }
    506 
    507 
    508 void HGlobalValueNumberingPhase::Run() {
    509   DCHECK(!removed_side_effects_);
    510   for (int i = FLAG_gvn_iterations; i > 0; --i) {
    511     // Compute the side effects.
    512     ComputeBlockSideEffects();
    513 
    514     // Perform loop invariant code motion if requested.
    515     if (FLAG_loop_invariant_code_motion) LoopInvariantCodeMotion();
    516 
    517     // Perform the actual value numbering.
    518     AnalyzeGraph();
    519 
    520     // Continue GVN if we removed any side effects.
    521     if (!removed_side_effects_) break;
    522     removed_side_effects_ = false;
    523 
    524     // Clear all side effects.
    525     DCHECK_EQ(block_side_effects_.length(), graph()->blocks()->length());
    526     DCHECK_EQ(loop_side_effects_.length(), graph()->blocks()->length());
    527     for (int i = 0; i < graph()->blocks()->length(); ++i) {
    528       block_side_effects_[i].RemoveAll();
    529       loop_side_effects_[i].RemoveAll();
    530     }
    531     visited_on_paths_.Clear();
    532   }
    533 }
    534 
    535 
    536 void HGlobalValueNumberingPhase::ComputeBlockSideEffects() {
    537   for (int i = graph()->blocks()->length() - 1; i >= 0; --i) {
    538     // Compute side effects for the block.
    539     HBasicBlock* block = graph()->blocks()->at(i);
    540     SideEffects side_effects;
    541     if (block->IsReachable() && !block->IsDeoptimizing()) {
    542       int id = block->block_id();
    543       for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
    544         HInstruction* instr = it.Current();
    545         side_effects.Add(side_effects_tracker_.ComputeChanges(instr));
    546       }
    547       block_side_effects_[id].Add(side_effects);
    548 
    549       // Loop headers are part of their loop.
    550       if (block->IsLoopHeader()) {
    551         loop_side_effects_[id].Add(side_effects);
    552       }
    553 
    554       // Propagate loop side effects upwards.
    555       if (block->HasParentLoopHeader()) {
    556         HBasicBlock* with_parent = block;
    557         if (block->IsLoopHeader()) side_effects = loop_side_effects_[id];
    558         do {
    559           HBasicBlock* parent_block = with_parent->parent_loop_header();
    560           loop_side_effects_[parent_block->block_id()].Add(side_effects);
    561           with_parent = parent_block;
    562         } while (with_parent->HasParentLoopHeader());
    563       }
    564     }
    565   }
    566 }
    567 
    568 
    569 void HGlobalValueNumberingPhase::LoopInvariantCodeMotion() {
    570   TRACE_GVN_1("Using optimistic loop invariant code motion: %s\n",
    571               graph()->use_optimistic_licm() ? "yes" : "no");
    572   for (int i = graph()->blocks()->length() - 1; i >= 0; --i) {
    573     HBasicBlock* block = graph()->blocks()->at(i);
    574     if (block->IsLoopHeader()) {
    575       SideEffects side_effects = loop_side_effects_[block->block_id()];
    576       if (FLAG_trace_gvn) {
    577         OFStream os(stdout);
    578         os << "Try loop invariant motion for " << *block << " changes "
    579            << Print(side_effects) << std::endl;
    580       }
    581       HBasicBlock* last = block->loop_information()->GetLastBackEdge();
    582       for (int j = block->block_id(); j <= last->block_id(); ++j) {
    583         ProcessLoopBlock(graph()->blocks()->at(j), block, side_effects);
    584       }
    585     }
    586   }
    587 }
    588 
    589 
    590 void HGlobalValueNumberingPhase::ProcessLoopBlock(
    591     HBasicBlock* block,
    592     HBasicBlock* loop_header,
    593     SideEffects loop_kills) {
    594   HBasicBlock* pre_header = loop_header->predecessors()->at(0);
    595   if (FLAG_trace_gvn) {
    596     OFStream os(stdout);
    597     os << "Loop invariant code motion for " << *block << " depends on "
    598        << Print(loop_kills) << std::endl;
    599   }
    600   HInstruction* instr = block->first();
    601   while (instr != NULL) {
    602     HInstruction* next = instr->next();
    603     if (instr->CheckFlag(HValue::kUseGVN)) {
    604       SideEffects changes = side_effects_tracker_.ComputeChanges(instr);
    605       SideEffects depends_on = side_effects_tracker_.ComputeDependsOn(instr);
    606       if (FLAG_trace_gvn) {
    607         OFStream os(stdout);
    608         os << "Checking instruction i" << instr->id() << " ("
    609            << instr->Mnemonic() << ") changes " << Print(changes)
    610            << ", depends on " << Print(depends_on) << ". Loop changes "
    611            << Print(loop_kills) << std::endl;
    612       }
    613       bool can_hoist = !depends_on.ContainsAnyOf(loop_kills);
    614       if (can_hoist && !graph()->use_optimistic_licm()) {
    615         can_hoist = block->IsLoopSuccessorDominator();
    616       }
    617 
    618       if (can_hoist) {
    619         bool inputs_loop_invariant = true;
    620         for (int i = 0; i < instr->OperandCount(); ++i) {
    621           if (instr->OperandAt(i)->IsDefinedAfter(pre_header)) {
    622             inputs_loop_invariant = false;
    623           }
    624         }
    625 
    626         if (inputs_loop_invariant && ShouldMove(instr, loop_header)) {
    627           TRACE_GVN_2("Hoisting loop invariant instruction i%d to block B%d\n",
    628                       instr->id(), pre_header->block_id());
    629           // Move the instruction out of the loop.
    630           instr->Unlink();
    631           instr->InsertBefore(pre_header->end());
    632           if (instr->HasSideEffects()) removed_side_effects_ = true;
    633         }
    634       }
    635     }
    636     instr = next;
    637   }
    638 }
    639 
    640 
    641 bool HGlobalValueNumberingPhase::ShouldMove(HInstruction* instr,
    642                                             HBasicBlock* loop_header) {
    643   // If we've disabled code motion or we're in a block that unconditionally
    644   // deoptimizes, don't move any instructions.
    645   return graph()->allow_code_motion() && !instr->block()->IsDeoptimizing() &&
    646          instr->block()->IsReachable();
    647 }
    648 
    649 
    650 SideEffects
    651 HGlobalValueNumberingPhase::CollectSideEffectsOnPathsToDominatedBlock(
    652     HBasicBlock* dominator, HBasicBlock* dominated) {
    653   SideEffects side_effects;
    654   for (int i = 0; i < dominated->predecessors()->length(); ++i) {
    655     HBasicBlock* block = dominated->predecessors()->at(i);
    656     if (dominator->block_id() < block->block_id() &&
    657         block->block_id() < dominated->block_id() &&
    658         !visited_on_paths_.Contains(block->block_id())) {
    659       visited_on_paths_.Add(block->block_id());
    660       side_effects.Add(block_side_effects_[block->block_id()]);
    661       if (block->IsLoopHeader()) {
    662         side_effects.Add(loop_side_effects_[block->block_id()]);
    663       }
    664       side_effects.Add(CollectSideEffectsOnPathsToDominatedBlock(
    665           dominator, block));
    666     }
    667   }
    668   return side_effects;
    669 }
    670 
    671 
    672 // Each instance of this class is like a "stack frame" for the recursive
    673 // traversal of the dominator tree done during GVN (the stack is handled
    674 // as a double linked list).
    675 // We reuse frames when possible so the list length is limited by the depth
    676 // of the dominator tree but this forces us to initialize each frame calling
    677 // an explicit "Initialize" method instead of a using constructor.
    678 class GvnBasicBlockState: public ZoneObject {
    679  public:
    680   static GvnBasicBlockState* CreateEntry(Zone* zone,
    681                                          HBasicBlock* entry_block,
    682                                          HInstructionMap* entry_map) {
    683     return new(zone)
    684         GvnBasicBlockState(NULL, entry_block, entry_map, NULL, zone);
    685   }
    686 
    687   HBasicBlock* block() { return block_; }
    688   HInstructionMap* map() { return map_; }
    689   HSideEffectMap* dominators() { return &dominators_; }
    690 
    691   GvnBasicBlockState* next_in_dominator_tree_traversal(
    692       Zone* zone,
    693       HBasicBlock** dominator) {
    694     // This assignment needs to happen before calling next_dominated() because
    695     // that call can reuse "this" if we are at the last dominated block.
    696     *dominator = block();
    697     GvnBasicBlockState* result = next_dominated(zone);
    698     if (result == NULL) {
    699       GvnBasicBlockState* dominator_state = pop();
    700       if (dominator_state != NULL) {
    701         // This branch is guaranteed not to return NULL because pop() never
    702         // returns a state where "is_done() == true".
    703         *dominator = dominator_state->block();
    704         result = dominator_state->next_dominated(zone);
    705       } else {
    706         // Unnecessary (we are returning NULL) but done for cleanness.
    707         *dominator = NULL;
    708       }
    709     }
    710     return result;
    711   }
    712 
    713  private:
    714   void Initialize(HBasicBlock* block,
    715                   HInstructionMap* map,
    716                   HSideEffectMap* dominators,
    717                   bool copy_map,
    718                   Zone* zone) {
    719     block_ = block;
    720     map_ = copy_map ? map->Copy(zone) : map;
    721     dominated_index_ = -1;
    722     length_ = block->dominated_blocks()->length();
    723     if (dominators != NULL) {
    724       dominators_ = *dominators;
    725     }
    726   }
    727   bool is_done() { return dominated_index_ >= length_; }
    728 
    729   GvnBasicBlockState(GvnBasicBlockState* previous,
    730                      HBasicBlock* block,
    731                      HInstructionMap* map,
    732                      HSideEffectMap* dominators,
    733                      Zone* zone)
    734       : previous_(previous), next_(NULL) {
    735     Initialize(block, map, dominators, true, zone);
    736   }
    737 
    738   GvnBasicBlockState* next_dominated(Zone* zone) {
    739     dominated_index_++;
    740     if (dominated_index_ == length_ - 1) {
    741       // No need to copy the map for the last child in the dominator tree.
    742       Initialize(block_->dominated_blocks()->at(dominated_index_),
    743                  map(),
    744                  dominators(),
    745                  false,
    746                  zone);
    747       return this;
    748     } else if (dominated_index_ < length_) {
    749       return push(zone, block_->dominated_blocks()->at(dominated_index_));
    750     } else {
    751       return NULL;
    752     }
    753   }
    754 
    755   GvnBasicBlockState* push(Zone* zone, HBasicBlock* block) {
    756     if (next_ == NULL) {
    757       next_ =
    758           new(zone) GvnBasicBlockState(this, block, map(), dominators(), zone);
    759     } else {
    760       next_->Initialize(block, map(), dominators(), true, zone);
    761     }
    762     return next_;
    763   }
    764   GvnBasicBlockState* pop() {
    765     GvnBasicBlockState* result = previous_;
    766     while (result != NULL && result->is_done()) {
    767       TRACE_GVN_2("Backtracking from block B%d to block b%d\n",
    768                   block()->block_id(),
    769                   previous_->block()->block_id())
    770       result = result->previous_;
    771     }
    772     return result;
    773   }
    774 
    775   GvnBasicBlockState* previous_;
    776   GvnBasicBlockState* next_;
    777   HBasicBlock* block_;
    778   HInstructionMap* map_;
    779   HSideEffectMap dominators_;
    780   int dominated_index_;
    781   int length_;
    782 };
    783 
    784 
    785 // This is a recursive traversal of the dominator tree but it has been turned
    786 // into a loop to avoid stack overflows.
    787 // The logical "stack frames" of the recursion are kept in a list of
    788 // GvnBasicBlockState instances.
    789 void HGlobalValueNumberingPhase::AnalyzeGraph() {
    790   HBasicBlock* entry_block = graph()->entry_block();
    791   HInstructionMap* entry_map =
    792       new(zone()) HInstructionMap(zone(), &side_effects_tracker_);
    793   GvnBasicBlockState* current =
    794       GvnBasicBlockState::CreateEntry(zone(), entry_block, entry_map);
    795 
    796   while (current != NULL) {
    797     HBasicBlock* block = current->block();
    798     HInstructionMap* map = current->map();
    799     HSideEffectMap* dominators = current->dominators();
    800 
    801     TRACE_GVN_2("Analyzing block B%d%s\n",
    802                 block->block_id(),
    803                 block->IsLoopHeader() ? " (loop header)" : "");
    804 
    805     // If this is a loop header kill everything killed by the loop.
    806     if (block->IsLoopHeader()) {
    807       map->Kill(loop_side_effects_[block->block_id()]);
    808       dominators->Kill(loop_side_effects_[block->block_id()]);
    809     }
    810 
    811     // Go through all instructions of the current block.
    812     for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
    813       HInstruction* instr = it.Current();
    814       if (instr->CheckFlag(HValue::kTrackSideEffectDominators)) {
    815         for (int i = 0; i < kNumberOfTrackedSideEffects; i++) {
    816           HValue* other = dominators->at(i);
    817           GVNFlag flag = GVNFlagFromInt(i);
    818           if (instr->DependsOnFlags().Contains(flag) && other != NULL) {
    819             TRACE_GVN_5("Side-effect #%d in %d (%s) is dominated by %d (%s)\n",
    820                         i,
    821                         instr->id(),
    822                         instr->Mnemonic(),
    823                         other->id(),
    824                         other->Mnemonic());
    825             if (instr->HandleSideEffectDominator(flag, other)) {
    826               removed_side_effects_ = true;
    827             }
    828           }
    829         }
    830       }
    831       // Instruction was unlinked during graph traversal.
    832       if (!instr->IsLinked()) continue;
    833 
    834       SideEffects changes = side_effects_tracker_.ComputeChanges(instr);
    835       if (!changes.IsEmpty()) {
    836         // Clear all instructions in the map that are affected by side effects.
    837         // Store instruction as the dominating one for tracked side effects.
    838         map->Kill(changes);
    839         dominators->Store(changes, instr);
    840         if (FLAG_trace_gvn) {
    841           OFStream os(stdout);
    842           os << "Instruction i" << instr->id() << " changes " << Print(changes)
    843              << std::endl;
    844         }
    845       }
    846       if (instr->CheckFlag(HValue::kUseGVN) &&
    847           !instr->CheckFlag(HValue::kCantBeReplaced)) {
    848         DCHECK(!instr->HasObservableSideEffects());
    849         HInstruction* other = map->Lookup(instr);
    850         if (other != NULL) {
    851           DCHECK(instr->Equals(other) && other->Equals(instr));
    852           TRACE_GVN_4("Replacing instruction i%d (%s) with i%d (%s)\n",
    853                       instr->id(),
    854                       instr->Mnemonic(),
    855                       other->id(),
    856                       other->Mnemonic());
    857           if (instr->HasSideEffects()) removed_side_effects_ = true;
    858           instr->DeleteAndReplaceWith(other);
    859         } else {
    860           map->Add(instr, zone());
    861         }
    862       }
    863     }
    864 
    865     HBasicBlock* dominator_block;
    866     GvnBasicBlockState* next =
    867         current->next_in_dominator_tree_traversal(zone(),
    868                                                   &dominator_block);
    869 
    870     if (next != NULL) {
    871       HBasicBlock* dominated = next->block();
    872       HInstructionMap* successor_map = next->map();
    873       HSideEffectMap* successor_dominators = next->dominators();
    874 
    875       // Kill everything killed on any path between this block and the
    876       // dominated block.  We don't have to traverse these paths if the
    877       // value map and the dominators list is already empty.  If the range
    878       // of block ids (block_id, dominated_id) is empty there are no such
    879       // paths.
    880       if ((!successor_map->IsEmpty() || !successor_dominators->IsEmpty()) &&
    881           dominator_block->block_id() + 1 < dominated->block_id()) {
    882         visited_on_paths_.Clear();
    883         SideEffects side_effects_on_all_paths =
    884             CollectSideEffectsOnPathsToDominatedBlock(dominator_block,
    885                                                       dominated);
    886         successor_map->Kill(side_effects_on_all_paths);
    887         successor_dominators->Kill(side_effects_on_all_paths);
    888       }
    889     }
    890     current = next;
    891   }
    892 }
    893 
    894 }  // namespace internal
    895 }  // namespace v8
    896