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