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/hydrogen.h"
6#include "src/hydrogen-gvn.h"
7#include "src/v8.h"
8
9namespace v8 {
10namespace internal {
11
12class HInstructionMap 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
73class HSideEffectMap 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    DCHECK(0 <= i);
87    DCHECK(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
98void TraceGVN(const char* msg, ...) {
99  va_list arguments;
100  va_start(arguments, msg);
101  base::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
134HInstructionMap::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  MemCopy(array_, other->array_,
144          array_size_ * sizeof(HInstructionMapListElement));
145  MemCopy(lists_, other->lists_,
146          lists_size_ * sizeof(HInstructionMapListElement));
147}
148
149
150void 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
199HInstruction* 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
214void HInstructionMap::Resize(int new_size, Zone* zone) {
215  DCHECK(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  DCHECK(count_ == old_count);
256}
257
258
259void HInstructionMap::ResizeLists(int new_size, Zone* zone) {
260  DCHECK(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    MemCopy(lists_, old_lists, old_size * sizeof(HInstructionMapListElement));
274  }
275  for (int i = old_size; i < lists_size_; ++i) {
276    lists_[i].next = free_list_head_;
277    free_list_head_ = i;
278  }
279}
280
281
282void HInstructionMap::Insert(HInstruction* instr, Zone* zone) {
283  DCHECK(instr != NULL);
284  // Resizing when half of the hashtable is filled up.
285  if (count_ >= array_size_ >> 1) Resize(array_size_ << 1, zone);
286  DCHECK(count_ < array_size_);
287  count_++;
288  uint32_t pos = Bound(static_cast<uint32_t>(instr->Hashcode()));
289  if (array_[pos].instr == NULL) {
290    array_[pos].instr = instr;
291    array_[pos].next = kNil;
292  } else {
293    if (free_list_head_ == kNil) {
294      ResizeLists(lists_size_ << 1, zone);
295    }
296    int new_element_pos = free_list_head_;
297    DCHECK(new_element_pos != kNil);
298    free_list_head_ = lists_[free_list_head_].next;
299    lists_[new_element_pos].instr = instr;
300    lists_[new_element_pos].next = array_[pos].next;
301    DCHECK(array_[pos].next == kNil || lists_[array_[pos].next].instr != NULL);
302    array_[pos].next = new_element_pos;
303  }
304}
305
306
307HSideEffectMap::HSideEffectMap() : count_(0) {
308  memset(data_, 0, kNumberOfTrackedSideEffects * kPointerSize);
309}
310
311
312HSideEffectMap::HSideEffectMap(HSideEffectMap* other) : count_(other->count_) {
313  *this = *other;  // Calls operator=.
314}
315
316
317HSideEffectMap& HSideEffectMap::operator=(const HSideEffectMap& other) {
318  if (this != &other) {
319    MemCopy(data_, other.data_, kNumberOfTrackedSideEffects * kPointerSize);
320  }
321  return *this;
322}
323
324
325void HSideEffectMap::Kill(SideEffects side_effects) {
326  for (int i = 0; i < kNumberOfTrackedSideEffects; i++) {
327    if (side_effects.ContainsFlag(GVNFlagFromInt(i))) {
328      if (data_[i] != NULL) count_--;
329      data_[i] = NULL;
330    }
331  }
332}
333
334
335void HSideEffectMap::Store(SideEffects side_effects, HInstruction* instr) {
336  for (int i = 0; i < kNumberOfTrackedSideEffects; i++) {
337    if (side_effects.ContainsFlag(GVNFlagFromInt(i))) {
338      if (data_[i] == NULL) count_++;
339      data_[i] = instr;
340    }
341  }
342}
343
344
345SideEffects SideEffectsTracker::ComputeChanges(HInstruction* instr) {
346  int index;
347  SideEffects result(instr->ChangesFlags());
348  if (result.ContainsFlag(kGlobalVars)) {
349    if (instr->IsStoreGlobalCell() &&
350        ComputeGlobalVar(HStoreGlobalCell::cast(instr)->cell(), &index)) {
351      result.RemoveFlag(kGlobalVars);
352      result.AddSpecial(GlobalVar(index));
353    } else {
354      for (index = 0; index < kNumberOfGlobalVars; ++index) {
355        result.AddSpecial(GlobalVar(index));
356      }
357    }
358  }
359  if (result.ContainsFlag(kInobjectFields)) {
360    if (instr->IsStoreNamedField() &&
361        ComputeInobjectField(HStoreNamedField::cast(instr)->access(), &index)) {
362      result.RemoveFlag(kInobjectFields);
363      result.AddSpecial(InobjectField(index));
364    } else {
365      for (index = 0; index < kNumberOfInobjectFields; ++index) {
366        result.AddSpecial(InobjectField(index));
367      }
368    }
369  }
370  return result;
371}
372
373
374SideEffects SideEffectsTracker::ComputeDependsOn(HInstruction* instr) {
375  int index;
376  SideEffects result(instr->DependsOnFlags());
377  if (result.ContainsFlag(kGlobalVars)) {
378    if (instr->IsLoadGlobalCell() &&
379        ComputeGlobalVar(HLoadGlobalCell::cast(instr)->cell(), &index)) {
380      result.RemoveFlag(kGlobalVars);
381      result.AddSpecial(GlobalVar(index));
382    } else {
383      for (index = 0; index < kNumberOfGlobalVars; ++index) {
384        result.AddSpecial(GlobalVar(index));
385      }
386    }
387  }
388  if (result.ContainsFlag(kInobjectFields)) {
389    if (instr->IsLoadNamedField() &&
390        ComputeInobjectField(HLoadNamedField::cast(instr)->access(), &index)) {
391      result.RemoveFlag(kInobjectFields);
392      result.AddSpecial(InobjectField(index));
393    } else {
394      for (index = 0; index < kNumberOfInobjectFields; ++index) {
395        result.AddSpecial(InobjectField(index));
396      }
397    }
398  }
399  return result;
400}
401
402
403OStream& operator<<(OStream& os, const TrackedEffects& te) {
404  SideEffectsTracker* t = te.tracker;
405  const char* separator = "";
406  os << "[";
407  for (int bit = 0; bit < kNumberOfFlags; ++bit) {
408    GVNFlag flag = GVNFlagFromInt(bit);
409    if (te.effects.ContainsFlag(flag)) {
410      os << separator;
411      separator = ", ";
412      switch (flag) {
413#define DECLARE_FLAG(Type) \
414  case k##Type:            \
415    os << #Type;           \
416    break;
417GVN_TRACKED_FLAG_LIST(DECLARE_FLAG)
418GVN_UNTRACKED_FLAG_LIST(DECLARE_FLAG)
419#undef DECLARE_FLAG
420        default:
421            break;
422      }
423    }
424  }
425  for (int index = 0; index < t->num_global_vars_; ++index) {
426    if (te.effects.ContainsSpecial(t->GlobalVar(index))) {
427      os << separator << "[" << *t->global_vars_[index].handle() << "]";
428      separator = ", ";
429    }
430  }
431  for (int index = 0; index < t->num_inobject_fields_; ++index) {
432    if (te.effects.ContainsSpecial(t->InobjectField(index))) {
433      os << separator << t->inobject_fields_[index];
434      separator = ", ";
435    }
436  }
437  os << "]";
438  return os;
439}
440
441
442bool SideEffectsTracker::ComputeGlobalVar(Unique<Cell> cell, int* index) {
443  for (int i = 0; i < num_global_vars_; ++i) {
444    if (cell == global_vars_[i]) {
445      *index = i;
446      return true;
447    }
448  }
449  if (num_global_vars_ < kNumberOfGlobalVars) {
450    if (FLAG_trace_gvn) {
451      OFStream os(stdout);
452      os << "Tracking global var [" << *cell.handle() << "] "
453         << "(mapped to index " << num_global_vars_ << ")" << endl;
454    }
455    *index = num_global_vars_;
456    global_vars_[num_global_vars_++] = cell;
457    return true;
458  }
459  return false;
460}
461
462
463bool SideEffectsTracker::ComputeInobjectField(HObjectAccess access,
464                                              int* index) {
465  for (int i = 0; i < num_inobject_fields_; ++i) {
466    if (access.Equals(inobject_fields_[i])) {
467      *index = i;
468      return true;
469    }
470  }
471  if (num_inobject_fields_ < kNumberOfInobjectFields) {
472    if (FLAG_trace_gvn) {
473      OFStream os(stdout);
474      os << "Tracking inobject field access " << access << " (mapped to index "
475         << num_inobject_fields_ << ")" << endl;
476    }
477    *index = num_inobject_fields_;
478    inobject_fields_[num_inobject_fields_++] = access;
479    return true;
480  }
481  return false;
482}
483
484
485HGlobalValueNumberingPhase::HGlobalValueNumberingPhase(HGraph* graph)
486    : HPhase("H_Global value numbering", graph),
487      removed_side_effects_(false),
488      block_side_effects_(graph->blocks()->length(), zone()),
489      loop_side_effects_(graph->blocks()->length(), zone()),
490      visited_on_paths_(graph->blocks()->length(), zone()) {
491  DCHECK(!AllowHandleAllocation::IsAllowed());
492  block_side_effects_.AddBlock(
493      SideEffects(), graph->blocks()->length(), zone());
494  loop_side_effects_.AddBlock(
495      SideEffects(), graph->blocks()->length(), zone());
496}
497
498
499void HGlobalValueNumberingPhase::Run() {
500  DCHECK(!removed_side_effects_);
501  for (int i = FLAG_gvn_iterations; i > 0; --i) {
502    // Compute the side effects.
503    ComputeBlockSideEffects();
504
505    // Perform loop invariant code motion if requested.
506    if (FLAG_loop_invariant_code_motion) LoopInvariantCodeMotion();
507
508    // Perform the actual value numbering.
509    AnalyzeGraph();
510
511    // Continue GVN if we removed any side effects.
512    if (!removed_side_effects_) break;
513    removed_side_effects_ = false;
514
515    // Clear all side effects.
516    DCHECK_EQ(block_side_effects_.length(), graph()->blocks()->length());
517    DCHECK_EQ(loop_side_effects_.length(), graph()->blocks()->length());
518    for (int i = 0; i < graph()->blocks()->length(); ++i) {
519      block_side_effects_[i].RemoveAll();
520      loop_side_effects_[i].RemoveAll();
521    }
522    visited_on_paths_.Clear();
523  }
524}
525
526
527void HGlobalValueNumberingPhase::ComputeBlockSideEffects() {
528  for (int i = graph()->blocks()->length() - 1; i >= 0; --i) {
529    // Compute side effects for the block.
530    HBasicBlock* block = graph()->blocks()->at(i);
531    SideEffects side_effects;
532    if (block->IsReachable() && !block->IsDeoptimizing()) {
533      int id = block->block_id();
534      for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
535        HInstruction* instr = it.Current();
536        side_effects.Add(side_effects_tracker_.ComputeChanges(instr));
537      }
538      block_side_effects_[id].Add(side_effects);
539
540      // Loop headers are part of their loop.
541      if (block->IsLoopHeader()) {
542        loop_side_effects_[id].Add(side_effects);
543      }
544
545      // Propagate loop side effects upwards.
546      if (block->HasParentLoopHeader()) {
547        HBasicBlock* with_parent = block;
548        if (block->IsLoopHeader()) side_effects = loop_side_effects_[id];
549        do {
550          HBasicBlock* parent_block = with_parent->parent_loop_header();
551          loop_side_effects_[parent_block->block_id()].Add(side_effects);
552          with_parent = parent_block;
553        } while (with_parent->HasParentLoopHeader());
554      }
555    }
556  }
557}
558
559
560void HGlobalValueNumberingPhase::LoopInvariantCodeMotion() {
561  TRACE_GVN_1("Using optimistic loop invariant code motion: %s\n",
562              graph()->use_optimistic_licm() ? "yes" : "no");
563  for (int i = graph()->blocks()->length() - 1; i >= 0; --i) {
564    HBasicBlock* block = graph()->blocks()->at(i);
565    if (block->IsLoopHeader()) {
566      SideEffects side_effects = loop_side_effects_[block->block_id()];
567      if (FLAG_trace_gvn) {
568        OFStream os(stdout);
569        os << "Try loop invariant motion for " << *block << " changes "
570           << Print(side_effects) << endl;
571      }
572      HBasicBlock* last = block->loop_information()->GetLastBackEdge();
573      for (int j = block->block_id(); j <= last->block_id(); ++j) {
574        ProcessLoopBlock(graph()->blocks()->at(j), block, side_effects);
575      }
576    }
577  }
578}
579
580
581void HGlobalValueNumberingPhase::ProcessLoopBlock(
582    HBasicBlock* block,
583    HBasicBlock* loop_header,
584    SideEffects loop_kills) {
585  HBasicBlock* pre_header = loop_header->predecessors()->at(0);
586  if (FLAG_trace_gvn) {
587    OFStream os(stdout);
588    os << "Loop invariant code motion for " << *block << " depends on "
589       << Print(loop_kills) << endl;
590  }
591  HInstruction* instr = block->first();
592  while (instr != NULL) {
593    HInstruction* next = instr->next();
594    if (instr->CheckFlag(HValue::kUseGVN)) {
595      SideEffects changes = side_effects_tracker_.ComputeChanges(instr);
596      SideEffects depends_on = side_effects_tracker_.ComputeDependsOn(instr);
597      if (FLAG_trace_gvn) {
598        OFStream os(stdout);
599        os << "Checking instruction i" << instr->id() << " ("
600           << instr->Mnemonic() << ") changes " << Print(changes)
601           << ", depends on " << Print(depends_on) << ". Loop changes "
602           << Print(loop_kills) << endl;
603      }
604      bool can_hoist = !depends_on.ContainsAnyOf(loop_kills);
605      if (can_hoist && !graph()->use_optimistic_licm()) {
606        can_hoist = block->IsLoopSuccessorDominator();
607      }
608
609      if (can_hoist) {
610        bool inputs_loop_invariant = true;
611        for (int i = 0; i < instr->OperandCount(); ++i) {
612          if (instr->OperandAt(i)->IsDefinedAfter(pre_header)) {
613            inputs_loop_invariant = false;
614          }
615        }
616
617        if (inputs_loop_invariant && ShouldMove(instr, loop_header)) {
618          TRACE_GVN_2("Hoisting loop invariant instruction i%d to block B%d\n",
619                      instr->id(), pre_header->block_id());
620          // Move the instruction out of the loop.
621          instr->Unlink();
622          instr->InsertBefore(pre_header->end());
623          if (instr->HasSideEffects()) removed_side_effects_ = true;
624        }
625      }
626    }
627    instr = next;
628  }
629}
630
631
632bool HGlobalValueNumberingPhase::AllowCodeMotion() {
633  return info()->IsStub() || info()->opt_count() + 1 < FLAG_max_opt_count;
634}
635
636
637bool HGlobalValueNumberingPhase::ShouldMove(HInstruction* instr,
638                                            HBasicBlock* loop_header) {
639  // If we've disabled code motion or we're in a block that unconditionally
640  // deoptimizes, don't move any instructions.
641  return AllowCodeMotion() && !instr->block()->IsDeoptimizing() &&
642      instr->block()->IsReachable();
643}
644
645
646SideEffects
647HGlobalValueNumberingPhase::CollectSideEffectsOnPathsToDominatedBlock(
648    HBasicBlock* dominator, HBasicBlock* dominated) {
649  SideEffects side_effects;
650  for (int i = 0; i < dominated->predecessors()->length(); ++i) {
651    HBasicBlock* block = dominated->predecessors()->at(i);
652    if (dominator->block_id() < block->block_id() &&
653        block->block_id() < dominated->block_id() &&
654        !visited_on_paths_.Contains(block->block_id())) {
655      visited_on_paths_.Add(block->block_id());
656      side_effects.Add(block_side_effects_[block->block_id()]);
657      if (block->IsLoopHeader()) {
658        side_effects.Add(loop_side_effects_[block->block_id()]);
659      }
660      side_effects.Add(CollectSideEffectsOnPathsToDominatedBlock(
661          dominator, block));
662    }
663  }
664  return side_effects;
665}
666
667
668// Each instance of this class is like a "stack frame" for the recursive
669// traversal of the dominator tree done during GVN (the stack is handled
670// as a double linked list).
671// We reuse frames when possible so the list length is limited by the depth
672// of the dominator tree but this forces us to initialize each frame calling
673// an explicit "Initialize" method instead of a using constructor.
674class GvnBasicBlockState: public ZoneObject {
675 public:
676  static GvnBasicBlockState* CreateEntry(Zone* zone,
677                                         HBasicBlock* entry_block,
678                                         HInstructionMap* entry_map) {
679    return new(zone)
680        GvnBasicBlockState(NULL, entry_block, entry_map, NULL, zone);
681  }
682
683  HBasicBlock* block() { return block_; }
684  HInstructionMap* map() { return map_; }
685  HSideEffectMap* dominators() { return &dominators_; }
686
687  GvnBasicBlockState* next_in_dominator_tree_traversal(
688      Zone* zone,
689      HBasicBlock** dominator) {
690    // This assignment needs to happen before calling next_dominated() because
691    // that call can reuse "this" if we are at the last dominated block.
692    *dominator = block();
693    GvnBasicBlockState* result = next_dominated(zone);
694    if (result == NULL) {
695      GvnBasicBlockState* dominator_state = pop();
696      if (dominator_state != NULL) {
697        // This branch is guaranteed not to return NULL because pop() never
698        // returns a state where "is_done() == true".
699        *dominator = dominator_state->block();
700        result = dominator_state->next_dominated(zone);
701      } else {
702        // Unnecessary (we are returning NULL) but done for cleanness.
703        *dominator = NULL;
704      }
705    }
706    return result;
707  }
708
709 private:
710  void Initialize(HBasicBlock* block,
711                  HInstructionMap* map,
712                  HSideEffectMap* dominators,
713                  bool copy_map,
714                  Zone* zone) {
715    block_ = block;
716    map_ = copy_map ? map->Copy(zone) : map;
717    dominated_index_ = -1;
718    length_ = block->dominated_blocks()->length();
719    if (dominators != NULL) {
720      dominators_ = *dominators;
721    }
722  }
723  bool is_done() { return dominated_index_ >= length_; }
724
725  GvnBasicBlockState(GvnBasicBlockState* previous,
726                     HBasicBlock* block,
727                     HInstructionMap* map,
728                     HSideEffectMap* dominators,
729                     Zone* zone)
730      : previous_(previous), next_(NULL) {
731    Initialize(block, map, dominators, true, zone);
732  }
733
734  GvnBasicBlockState* next_dominated(Zone* zone) {
735    dominated_index_++;
736    if (dominated_index_ == length_ - 1) {
737      // No need to copy the map for the last child in the dominator tree.
738      Initialize(block_->dominated_blocks()->at(dominated_index_),
739                 map(),
740                 dominators(),
741                 false,
742                 zone);
743      return this;
744    } else if (dominated_index_ < length_) {
745      return push(zone, block_->dominated_blocks()->at(dominated_index_));
746    } else {
747      return NULL;
748    }
749  }
750
751  GvnBasicBlockState* push(Zone* zone, HBasicBlock* block) {
752    if (next_ == NULL) {
753      next_ =
754          new(zone) GvnBasicBlockState(this, block, map(), dominators(), zone);
755    } else {
756      next_->Initialize(block, map(), dominators(), true, zone);
757    }
758    return next_;
759  }
760  GvnBasicBlockState* pop() {
761    GvnBasicBlockState* result = previous_;
762    while (result != NULL && result->is_done()) {
763      TRACE_GVN_2("Backtracking from block B%d to block b%d\n",
764                  block()->block_id(),
765                  previous_->block()->block_id())
766      result = result->previous_;
767    }
768    return result;
769  }
770
771  GvnBasicBlockState* previous_;
772  GvnBasicBlockState* next_;
773  HBasicBlock* block_;
774  HInstructionMap* map_;
775  HSideEffectMap dominators_;
776  int dominated_index_;
777  int length_;
778};
779
780
781// This is a recursive traversal of the dominator tree but it has been turned
782// into a loop to avoid stack overflows.
783// The logical "stack frames" of the recursion are kept in a list of
784// GvnBasicBlockState instances.
785void HGlobalValueNumberingPhase::AnalyzeGraph() {
786  HBasicBlock* entry_block = graph()->entry_block();
787  HInstructionMap* entry_map =
788      new(zone()) HInstructionMap(zone(), &side_effects_tracker_);
789  GvnBasicBlockState* current =
790      GvnBasicBlockState::CreateEntry(zone(), entry_block, entry_map);
791
792  while (current != NULL) {
793    HBasicBlock* block = current->block();
794    HInstructionMap* map = current->map();
795    HSideEffectMap* dominators = current->dominators();
796
797    TRACE_GVN_2("Analyzing block B%d%s\n",
798                block->block_id(),
799                block->IsLoopHeader() ? " (loop header)" : "");
800
801    // If this is a loop header kill everything killed by the loop.
802    if (block->IsLoopHeader()) {
803      map->Kill(loop_side_effects_[block->block_id()]);
804      dominators->Kill(loop_side_effects_[block->block_id()]);
805    }
806
807    // Go through all instructions of the current block.
808    for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
809      HInstruction* instr = it.Current();
810      if (instr->CheckFlag(HValue::kTrackSideEffectDominators)) {
811        for (int i = 0; i < kNumberOfTrackedSideEffects; i++) {
812          HValue* other = dominators->at(i);
813          GVNFlag flag = GVNFlagFromInt(i);
814          if (instr->DependsOnFlags().Contains(flag) && other != NULL) {
815            TRACE_GVN_5("Side-effect #%d in %d (%s) is dominated by %d (%s)\n",
816                        i,
817                        instr->id(),
818                        instr->Mnemonic(),
819                        other->id(),
820                        other->Mnemonic());
821            if (instr->HandleSideEffectDominator(flag, other)) {
822              removed_side_effects_ = true;
823            }
824          }
825        }
826      }
827      // Instruction was unlinked during graph traversal.
828      if (!instr->IsLinked()) continue;
829
830      SideEffects changes = side_effects_tracker_.ComputeChanges(instr);
831      if (!changes.IsEmpty()) {
832        // Clear all instructions in the map that are affected by side effects.
833        // Store instruction as the dominating one for tracked side effects.
834        map->Kill(changes);
835        dominators->Store(changes, instr);
836        if (FLAG_trace_gvn) {
837          OFStream os(stdout);
838          os << "Instruction i" << instr->id() << " changes " << Print(changes)
839             << endl;
840        }
841      }
842      if (instr->CheckFlag(HValue::kUseGVN) &&
843          !instr->CheckFlag(HValue::kCantBeReplaced)) {
844        DCHECK(!instr->HasObservableSideEffects());
845        HInstruction* other = map->Lookup(instr);
846        if (other != NULL) {
847          DCHECK(instr->Equals(other) && other->Equals(instr));
848          TRACE_GVN_4("Replacing instruction i%d (%s) with i%d (%s)\n",
849                      instr->id(),
850                      instr->Mnemonic(),
851                      other->id(),
852                      other->Mnemonic());
853          if (instr->HasSideEffects()) removed_side_effects_ = true;
854          instr->DeleteAndReplaceWith(other);
855        } else {
856          map->Add(instr, zone());
857        }
858      }
859    }
860
861    HBasicBlock* dominator_block;
862    GvnBasicBlockState* next =
863        current->next_in_dominator_tree_traversal(zone(),
864                                                  &dominator_block);
865
866    if (next != NULL) {
867      HBasicBlock* dominated = next->block();
868      HInstructionMap* successor_map = next->map();
869      HSideEffectMap* successor_dominators = next->dominators();
870
871      // Kill everything killed on any path between this block and the
872      // dominated block.  We don't have to traverse these paths if the
873      // value map and the dominators list is already empty.  If the range
874      // of block ids (block_id, dominated_id) is empty there are no such
875      // paths.
876      if ((!successor_map->IsEmpty() || !successor_dominators->IsEmpty()) &&
877          dominator_block->block_id() + 1 < dominated->block_id()) {
878        visited_on_paths_.Clear();
879        SideEffects side_effects_on_all_paths =
880            CollectSideEffectsOnPathsToDominatedBlock(dominator_block,
881                                                      dominated);
882        successor_map->Kill(side_effects_on_all_paths);
883        successor_dominators->Kill(side_effects_on_all_paths);
884      }
885    }
886    current = next;
887  }
888}
889
890} }  // namespace v8::internal
891