src/v8/src/hydrogen-gvn.cc

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