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