• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
9 namespace v8 {
10 namespace internal {
11 
12 class HInstructionMap FINAL : public ZoneObject {
13  public:
HInstructionMap(Zone * zone,SideEffectsTracker * side_effects_tracker)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 
Add(HInstruction * instr,Zone * zone)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 
Copy(Zone * zone) const35   HInstructionMap* Copy(Zone* zone) const {
36     return new(zone) HInstructionMap(zone, this);
37   }
38 
IsEmpty() const39   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);
Bound(uint32_t value) const57   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 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 
IsEmpty() const83   bool IsEmpty() const { return count_ == 0; }
84 
operator [](int i) const85   inline HInstruction* operator[](int i) const {
86     DCHECK(0 <= i);
87     DCHECK(i < kNumberOfTrackedSideEffects);
88     return data_[i];
89   }
at(int i) const90   inline HInstruction* at(int i) const { return operator[](i); }
91 
92  private:
93   int count_;
94   HInstruction* data_[kNumberOfTrackedSideEffects];
95 };
96 
97 
TraceGVN(const char * msg,...)98 void 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 
HInstructionMap(Zone * zone,const HInstructionMap * other)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   MemCopy(array_, other->array_,
144           array_size_ * sizeof(HInstructionMapListElement));
145   MemCopy(lists_, other->lists_,
146           lists_size_ * sizeof(HInstructionMapListElement));
147 }
148 
149 
Kill(SideEffects changes)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 
Lookup(HInstruction * instr) const199 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 
Resize(int new_size,Zone * zone)214 void 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 
ResizeLists(int new_size,Zone * zone)259 void 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 
Insert(HInstruction * instr,Zone * zone)282 void 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 
HSideEffectMap()307 HSideEffectMap::HSideEffectMap() : count_(0) {
308   memset(data_, 0, kNumberOfTrackedSideEffects * kPointerSize);
309 }
310 
311 
HSideEffectMap(HSideEffectMap * other)312 HSideEffectMap::HSideEffectMap(HSideEffectMap* other) : count_(other->count_) {
313   *this = *other;  // Calls operator=.
314 }
315 
316 
operator =(const HSideEffectMap & other)317 HSideEffectMap& HSideEffectMap::operator=(const HSideEffectMap& other) {
318   if (this != &other) {
319     MemCopy(data_, other.data_, kNumberOfTrackedSideEffects * kPointerSize);
320   }
321   return *this;
322 }
323 
324 
Kill(SideEffects side_effects)325 void 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 
Store(SideEffects side_effects,HInstruction * instr)335 void 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 
ComputeChanges(HInstruction * instr)345 SideEffects 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 
ComputeDependsOn(HInstruction * instr)374 SideEffects 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 
operator <<(OStream & os,const TrackedEffects & te)403 OStream& 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;
417 GVN_TRACKED_FLAG_LIST(DECLARE_FLAG)
418 GVN_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 
ComputeGlobalVar(Unique<Cell> cell,int * index)442 bool 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 
ComputeInobjectField(HObjectAccess access,int * index)463 bool 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 
HGlobalValueNumberingPhase(HGraph * graph)485 HGlobalValueNumberingPhase::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 
Run()499 void 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 
ComputeBlockSideEffects()527 void 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 
LoopInvariantCodeMotion()560 void 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 
ProcessLoopBlock(HBasicBlock * block,HBasicBlock * loop_header,SideEffects loop_kills)581 void 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 
AllowCodeMotion()632 bool HGlobalValueNumberingPhase::AllowCodeMotion() {
633   return info()->IsStub() || info()->opt_count() + 1 < FLAG_max_opt_count;
634 }
635 
636 
ShouldMove(HInstruction * instr,HBasicBlock * loop_header)637 bool 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 
646 SideEffects
CollectSideEffectsOnPathsToDominatedBlock(HBasicBlock * dominator,HBasicBlock * dominated)647 HGlobalValueNumberingPhase::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.
674 class GvnBasicBlockState: public ZoneObject {
675  public:
CreateEntry(Zone * zone,HBasicBlock * entry_block,HInstructionMap * entry_map)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 
block()683   HBasicBlock* block() { return block_; }
map()684   HInstructionMap* map() { return map_; }
dominators()685   HSideEffectMap* dominators() { return &dominators_; }
686 
next_in_dominator_tree_traversal(Zone * zone,HBasicBlock ** dominator)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:
Initialize(HBasicBlock * block,HInstructionMap * map,HSideEffectMap * dominators,bool copy_map,Zone * zone)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   }
is_done()723   bool is_done() { return dominated_index_ >= length_; }
724 
GvnBasicBlockState(GvnBasicBlockState * previous,HBasicBlock * block,HInstructionMap * map,HSideEffectMap * dominators,Zone * zone)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 
next_dominated(Zone * zone)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 
push(Zone * zone,HBasicBlock * block)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   }
pop()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.
AnalyzeGraph()785 void 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