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 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 side_effects_tracker_(side_effects_tracker) { 24 ResizeLists(kInitialSize, zone); 25 Resize(kInitialSize, zone); 26 } 27 28 void Kill(SideEffects side_effects); 29 30 void Add(HInstruction* instr, Zone* zone) { 31 present_depends_on_.Add(side_effects_tracker_->ComputeDependsOn(instr)); 32 Insert(instr, zone); 33 } 34 35 HInstruction* Lookup(HInstruction* instr) const; 36 37 HInstructionMap* Copy(Zone* zone) const { 38 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 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 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 void TraceGVN(const char* msg, ...) { 101 va_list arguments; 102 va_start(arguments, msg); 103 base::OS::VPrint(msg, arguments); 104 va_end(arguments); 105 } 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 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 array_(zone->NewArray<HInstructionMapListElement>(other->array_size_)), 142 lists_(zone->NewArray<HInstructionMapListElement>(other->lists_size_)), 143 free_list_head_(other->free_list_head_), 144 side_effects_tracker_(other->side_effects_tracker_) { 145 MemCopy(array_, other->array_, 146 array_size_ * sizeof(HInstructionMapListElement)); 147 MemCopy(lists_, other->lists_, 148 lists_size_ * sizeof(HInstructionMapListElement)); 149 } 150 151 152 void HInstructionMap::Kill(SideEffects changes) { 153 if (!present_depends_on_.ContainsAnyOf(changes)) return; 154 present_depends_on_.RemoveAll(); 155 for (int i = 0; i < array_size_; ++i) { 156 HInstruction* instr = array_[i].instr; 157 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 for (int current = array_[i].next; current != kNil; current = next) { 162 next = lists_[current].next; 163 HInstruction* instr = lists_[current].instr; 164 SideEffects depends_on = side_effects_tracker_->ComputeDependsOn(instr); 165 if (depends_on.ContainsAnyOf(changes)) { 166 // Drop it. 167 count_--; 168 lists_[current].next = free_list_head_; 169 free_list_head_ = current; 170 } else { 171 // Keep it. 172 lists_[current].next = kept; 173 kept = current; 174 present_depends_on_.Add(depends_on); 175 } 176 } 177 array_[i].next = kept; 178 179 // Now possibly drop directly indexed element. 180 instr = array_[i].instr; 181 SideEffects depends_on = side_effects_tracker_->ComputeDependsOn(instr); 182 if (depends_on.ContainsAnyOf(changes)) { // Drop it. 183 count_--; 184 int head = array_[i].next; 185 if (head == kNil) { 186 array_[i].instr = NULL; 187 } else { 188 array_[i].instr = lists_[head].instr; 189 array_[i].next = lists_[head].next; 190 lists_[head].next = free_list_head_; 191 free_list_head_ = head; 192 } 193 } else { 194 present_depends_on_.Add(depends_on); // Keep it. 195 } 196 } 197 } 198 } 199 200 201 HInstruction* HInstructionMap::Lookup(HInstruction* instr) const { 202 uint32_t hash = static_cast<uint32_t>(instr->Hashcode()); 203 uint32_t pos = Bound(hash); 204 if (array_[pos].instr != NULL) { 205 if (array_[pos].instr->Equals(instr)) return array_[pos].instr; 206 int next = array_[pos].next; 207 while (next != kNil) { 208 if (lists_[next].instr->Equals(instr)) return lists_[next].instr; 209 next = lists_[next].next; 210 } 211 } 212 return NULL; 213 } 214 215 216 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 if (free_list_head_ == kNil) { 223 ResizeLists(lists_size_ << 1, zone); 224 } 225 226 HInstructionMapListElement* new_array = 227 zone->NewArray<HInstructionMapListElement>(new_size); 228 memset(new_array, 0, sizeof(HInstructionMapListElement) * new_size); 229 230 HInstructionMapListElement* old_array = array_; 231 int old_size = array_size_; 232 233 int old_count = count_; 234 count_ = 0; 235 // Do not modify present_depends_on_. It is currently correct. 236 array_size_ = new_size; 237 array_ = new_array; 238 239 if (old_array != NULL) { 240 // Iterate over all the elements in lists, rehashing them. 241 for (int i = 0; i < old_size; ++i) { 242 if (old_array[i].instr != NULL) { 243 int current = old_array[i].next; 244 while (current != kNil) { 245 Insert(lists_[current].instr, zone); 246 int next = lists_[current].next; 247 lists_[current].next = free_list_head_; 248 free_list_head_ = current; 249 current = next; 250 } 251 // Rehash the directly stored instruction. 252 Insert(old_array[i].instr, zone); 253 } 254 } 255 } 256 USE(old_count); 257 DCHECK(count_ == old_count); 258 } 259 260 261 void HInstructionMap::ResizeLists(int new_size, Zone* zone) { 262 DCHECK(new_size > lists_size_); 263 264 HInstructionMapListElement* new_lists = 265 zone->NewArray<HInstructionMapListElement>(new_size); 266 memset(new_lists, 0, sizeof(HInstructionMapListElement) * new_size); 267 268 HInstructionMapListElement* old_lists = lists_; 269 int old_size = lists_size_; 270 271 lists_size_ = new_size; 272 lists_ = new_lists; 273 274 if (old_lists != NULL) { 275 MemCopy(lists_, old_lists, old_size * sizeof(HInstructionMapListElement)); 276 } 277 for (int i = old_size; i < lists_size_; ++i) { 278 lists_[i].next = free_list_head_; 279 free_list_head_ = i; 280 } 281 } 282 283 284 void HInstructionMap::Insert(HInstruction* instr, Zone* zone) { 285 DCHECK(instr != NULL); 286 // Resizing when half of the hashtable is filled up. 287 if (count_ >= array_size_ >> 1) Resize(array_size_ << 1, zone); 288 DCHECK(count_ < array_size_); 289 count_++; 290 uint32_t pos = Bound(static_cast<uint32_t>(instr->Hashcode())); 291 if (array_[pos].instr == NULL) { 292 array_[pos].instr = instr; 293 array_[pos].next = kNil; 294 } else { 295 if (free_list_head_ == kNil) { 296 ResizeLists(lists_size_ << 1, zone); 297 } 298 int new_element_pos = free_list_head_; 299 DCHECK(new_element_pos != kNil); 300 free_list_head_ = lists_[free_list_head_].next; 301 lists_[new_element_pos].instr = instr; 302 lists_[new_element_pos].next = array_[pos].next; 303 DCHECK(array_[pos].next == kNil || lists_[array_[pos].next].instr != NULL); 304 array_[pos].next = new_element_pos; 305 } 306 } 307 308 309 HSideEffectMap::HSideEffectMap() : count_(0) { 310 memset(data_, 0, kNumberOfTrackedSideEffects * kPointerSize); 311 } 312 313 314 HSideEffectMap::HSideEffectMap(HSideEffectMap* other) : count_(other->count_) { 315 *this = *other; // Calls operator=. 316 } 317 318 319 HSideEffectMap& HSideEffectMap::operator=(const HSideEffectMap& other) { 320 if (this != &other) { 321 MemCopy(data_, other.data_, kNumberOfTrackedSideEffects * kPointerSize); 322 } 323 return *this; 324 } 325 326 327 void HSideEffectMap::Kill(SideEffects side_effects) { 328 for (int i = 0; i < kNumberOfTrackedSideEffects; i++) { 329 if (side_effects.ContainsFlag(GVNFlagFromInt(i))) { 330 if (data_[i] != NULL) count_--; 331 data_[i] = NULL; 332 } 333 } 334 } 335 336 337 void HSideEffectMap::Store(SideEffects side_effects, HInstruction* instr) { 338 for (int i = 0; i < kNumberOfTrackedSideEffects; i++) { 339 if (side_effects.ContainsFlag(GVNFlagFromInt(i))) { 340 if (data_[i] == NULL) count_++; 341 data_[i] = instr; 342 } 343 } 344 } 345 346 347 SideEffects SideEffectsTracker::ComputeChanges(HInstruction* instr) { 348 int index; 349 SideEffects result(instr->ChangesFlags()); 350 if (result.ContainsFlag(kGlobalVars)) { 351 if (instr->IsStoreNamedField()) { 352 HStoreNamedField* store = HStoreNamedField::cast(instr); 353 HConstant* target = HConstant::cast(store->object()); 354 if (ComputeGlobalVar(Unique<PropertyCell>::cast(target->GetUnique()), 355 &index)) { 356 result.RemoveFlag(kGlobalVars); 357 result.AddSpecial(GlobalVar(index)); 358 return result; 359 } 360 } 361 for (index = 0; index < kNumberOfGlobalVars; ++index) { 362 result.AddSpecial(GlobalVar(index)); 363 } 364 } else if (result.ContainsFlag(kInobjectFields)) { 365 if (instr->IsStoreNamedField() && 366 ComputeInobjectField(HStoreNamedField::cast(instr)->access(), &index)) { 367 result.RemoveFlag(kInobjectFields); 368 result.AddSpecial(InobjectField(index)); 369 } else { 370 for (index = 0; index < kNumberOfInobjectFields; ++index) { 371 result.AddSpecial(InobjectField(index)); 372 } 373 } 374 } 375 return result; 376 } 377 378 379 SideEffects SideEffectsTracker::ComputeDependsOn(HInstruction* instr) { 380 int index; 381 SideEffects result(instr->DependsOnFlags()); 382 if (result.ContainsFlag(kGlobalVars)) { 383 if (instr->IsLoadNamedField()) { 384 HLoadNamedField* load = HLoadNamedField::cast(instr); 385 HConstant* target = HConstant::cast(load->object()); 386 if (ComputeGlobalVar(Unique<PropertyCell>::cast(target->GetUnique()), 387 &index)) { 388 result.RemoveFlag(kGlobalVars); 389 result.AddSpecial(GlobalVar(index)); 390 return result; 391 } 392 } 393 for (index = 0; index < kNumberOfGlobalVars; ++index) { 394 result.AddSpecial(GlobalVar(index)); 395 } 396 } else if (result.ContainsFlag(kInobjectFields)) { 397 if (instr->IsLoadNamedField() && 398 ComputeInobjectField(HLoadNamedField::cast(instr)->access(), &index)) { 399 result.RemoveFlag(kInobjectFields); 400 result.AddSpecial(InobjectField(index)); 401 } else { 402 for (index = 0; index < kNumberOfInobjectFields; ++index) { 403 result.AddSpecial(InobjectField(index)); 404 } 405 } 406 } 407 return result; 408 } 409 410 411 std::ostream& operator<<(std::ostream& os, const TrackedEffects& te) { 412 SideEffectsTracker* t = te.tracker; 413 const char* separator = ""; 414 os << "["; 415 for (int bit = 0; bit < kNumberOfFlags; ++bit) { 416 GVNFlag flag = GVNFlagFromInt(bit); 417 if (te.effects.ContainsFlag(flag)) { 418 os << separator; 419 separator = ", "; 420 switch (flag) { 421 #define DECLARE_FLAG(Type) \ 422 case k##Type: \ 423 os << #Type; \ 424 break; 425 GVN_TRACKED_FLAG_LIST(DECLARE_FLAG) 426 GVN_UNTRACKED_FLAG_LIST(DECLARE_FLAG) 427 #undef DECLARE_FLAG 428 default: 429 break; 430 } 431 } 432 } 433 for (int index = 0; index < t->num_global_vars_; ++index) { 434 if (te.effects.ContainsSpecial(t->GlobalVar(index))) { 435 os << separator << "[" << *t->global_vars_[index].handle() << "]"; 436 separator = ", "; 437 } 438 } 439 for (int index = 0; index < t->num_inobject_fields_; ++index) { 440 if (te.effects.ContainsSpecial(t->InobjectField(index))) { 441 os << separator << t->inobject_fields_[index]; 442 separator = ", "; 443 } 444 } 445 os << "]"; 446 return os; 447 } 448 449 450 bool SideEffectsTracker::ComputeGlobalVar(Unique<PropertyCell> cell, 451 int* index) { 452 for (int i = 0; i < num_global_vars_; ++i) { 453 if (cell == global_vars_[i]) { 454 *index = i; 455 return true; 456 } 457 } 458 if (num_global_vars_ < kNumberOfGlobalVars) { 459 if (FLAG_trace_gvn) { 460 OFStream os(stdout); 461 os << "Tracking global var [" << *cell.handle() << "] " 462 << "(mapped to index " << num_global_vars_ << ")" << std::endl; 463 } 464 *index = num_global_vars_; 465 global_vars_[num_global_vars_++] = cell; 466 return true; 467 } 468 return false; 469 } 470 471 472 bool SideEffectsTracker::ComputeInobjectField(HObjectAccess access, 473 int* index) { 474 for (int i = 0; i < num_inobject_fields_; ++i) { 475 if (access.Equals(inobject_fields_[i])) { 476 *index = i; 477 return true; 478 } 479 } 480 if (num_inobject_fields_ < kNumberOfInobjectFields) { 481 if (FLAG_trace_gvn) { 482 OFStream os(stdout); 483 os << "Tracking inobject field access " << access << " (mapped to index " 484 << num_inobject_fields_ << ")" << std::endl; 485 } 486 *index = num_inobject_fields_; 487 inobject_fields_[num_inobject_fields_++] = access; 488 return true; 489 } 490 return false; 491 } 492 493 494 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 visited_on_paths_(graph->blocks()->length(), zone()) { 500 DCHECK(!AllowHandleAllocation::IsAllowed()); 501 block_side_effects_.AddBlock( 502 SideEffects(), graph->blocks()->length(), zone()); 503 loop_side_effects_.AddBlock( 504 SideEffects(), graph->blocks()->length(), zone()); 505 } 506 507 508 void HGlobalValueNumberingPhase::Run() { 509 DCHECK(!removed_side_effects_); 510 for (int i = FLAG_gvn_iterations; i > 0; --i) { 511 // Compute the side effects. 512 ComputeBlockSideEffects(); 513 514 // Perform loop invariant code motion if requested. 515 if (FLAG_loop_invariant_code_motion) LoopInvariantCodeMotion(); 516 517 // Perform the actual value numbering. 518 AnalyzeGraph(); 519 520 // Continue GVN if we removed any side effects. 521 if (!removed_side_effects_) break; 522 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 for (int i = 0; i < graph()->blocks()->length(); ++i) { 528 block_side_effects_[i].RemoveAll(); 529 loop_side_effects_[i].RemoveAll(); 530 } 531 visited_on_paths_.Clear(); 532 } 533 } 534 535 536 void HGlobalValueNumberingPhase::ComputeBlockSideEffects() { 537 for (int i = graph()->blocks()->length() - 1; i >= 0; --i) { 538 // Compute side effects for the block. 539 HBasicBlock* block = graph()->blocks()->at(i); 540 SideEffects side_effects; 541 if (block->IsReachable() && !block->IsDeoptimizing()) { 542 int id = block->block_id(); 543 for (HInstructionIterator it(block); !it.Done(); it.Advance()) { 544 HInstruction* instr = it.Current(); 545 side_effects.Add(side_effects_tracker_.ComputeChanges(instr)); 546 } 547 block_side_effects_[id].Add(side_effects); 548 549 // Loop headers are part of their loop. 550 if (block->IsLoopHeader()) { 551 loop_side_effects_[id].Add(side_effects); 552 } 553 554 // Propagate loop side effects upwards. 555 if (block->HasParentLoopHeader()) { 556 HBasicBlock* with_parent = block; 557 if (block->IsLoopHeader()) side_effects = loop_side_effects_[id]; 558 do { 559 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 } 567 568 569 void HGlobalValueNumberingPhase::LoopInvariantCodeMotion() { 570 TRACE_GVN_1("Using optimistic loop invariant code motion: %s\n", 571 graph()->use_optimistic_licm() ? "yes" : "no"); 572 for (int i = graph()->blocks()->length() - 1; i >= 0; --i) { 573 HBasicBlock* block = graph()->blocks()->at(i); 574 if (block->IsLoopHeader()) { 575 SideEffects side_effects = loop_side_effects_[block->block_id()]; 576 if (FLAG_trace_gvn) { 577 OFStream os(stdout); 578 os << "Try loop invariant motion for " << *block << " changes " 579 << Print(side_effects) << std::endl; 580 } 581 HBasicBlock* last = block->loop_information()->GetLastBackEdge(); 582 for (int j = block->block_id(); j <= last->block_id(); ++j) { 583 ProcessLoopBlock(graph()->blocks()->at(j), block, side_effects); 584 } 585 } 586 } 587 } 588 589 590 void HGlobalValueNumberingPhase::ProcessLoopBlock( 591 HBasicBlock* block, 592 HBasicBlock* loop_header, 593 SideEffects loop_kills) { 594 HBasicBlock* pre_header = loop_header->predecessors()->at(0); 595 if (FLAG_trace_gvn) { 596 OFStream os(stdout); 597 os << "Loop invariant code motion for " << *block << " depends on " 598 << Print(loop_kills) << std::endl; 599 } 600 HInstruction* instr = block->first(); 601 while (instr != NULL) { 602 HInstruction* next = instr->next(); 603 if (instr->CheckFlag(HValue::kUseGVN)) { 604 SideEffects changes = side_effects_tracker_.ComputeChanges(instr); 605 SideEffects depends_on = side_effects_tracker_.ComputeDependsOn(instr); 606 if (FLAG_trace_gvn) { 607 OFStream os(stdout); 608 os << "Checking instruction i" << instr->id() << " (" 609 << instr->Mnemonic() << ") changes " << Print(changes) 610 << ", depends on " << Print(depends_on) << ". Loop changes " 611 << Print(loop_kills) << std::endl; 612 } 613 bool can_hoist = !depends_on.ContainsAnyOf(loop_kills); 614 if (can_hoist && !graph()->use_optimistic_licm()) { 615 can_hoist = block->IsLoopSuccessorDominator(); 616 } 617 618 if (can_hoist) { 619 bool inputs_loop_invariant = true; 620 for (int i = 0; i < instr->OperandCount(); ++i) { 621 if (instr->OperandAt(i)->IsDefinedAfter(pre_header)) { 622 inputs_loop_invariant = false; 623 } 624 } 625 626 if (inputs_loop_invariant && ShouldMove(instr, loop_header)) { 627 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 instr->Unlink(); 631 instr->InsertBefore(pre_header->end()); 632 if (instr->HasSideEffects()) removed_side_effects_ = true; 633 } 634 } 635 } 636 instr = next; 637 } 638 } 639 640 641 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 return graph()->allow_code_motion() && !instr->block()->IsDeoptimizing() && 646 instr->block()->IsReachable(); 647 } 648 649 650 SideEffects 651 HGlobalValueNumberingPhase::CollectSideEffectsOnPathsToDominatedBlock( 652 HBasicBlock* dominator, HBasicBlock* dominated) { 653 SideEffects side_effects; 654 for (int i = 0; i < dominated->predecessors()->length(); ++i) { 655 HBasicBlock* block = dominated->predecessors()->at(i); 656 if (dominator->block_id() < block->block_id() && 657 block->block_id() < dominated->block_id() && 658 !visited_on_paths_.Contains(block->block_id())) { 659 visited_on_paths_.Add(block->block_id()); 660 side_effects.Add(block_side_effects_[block->block_id()]); 661 if (block->IsLoopHeader()) { 662 side_effects.Add(loop_side_effects_[block->block_id()]); 663 } 664 side_effects.Add(CollectSideEffectsOnPathsToDominatedBlock( 665 dominator, block)); 666 } 667 } 668 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 static GvnBasicBlockState* CreateEntry(Zone* zone, 681 HBasicBlock* entry_block, 682 HInstructionMap* entry_map) { 683 return new(zone) 684 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 GvnBasicBlockState* next_in_dominator_tree_traversal( 692 Zone* zone, 693 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 *dominator = block(); 697 GvnBasicBlockState* result = next_dominated(zone); 698 if (result == NULL) { 699 GvnBasicBlockState* dominator_state = pop(); 700 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 *dominator = dominator_state->block(); 704 result = dominator_state->next_dominated(zone); 705 } else { 706 // Unnecessary (we are returning NULL) but done for cleanness. 707 *dominator = NULL; 708 } 709 } 710 return result; 711 } 712 713 private: 714 void Initialize(HBasicBlock* block, 715 HInstructionMap* map, 716 HSideEffectMap* dominators, 717 bool copy_map, 718 Zone* zone) { 719 block_ = block; 720 map_ = copy_map ? map->Copy(zone) : map; 721 dominated_index_ = -1; 722 length_ = block->dominated_blocks()->length(); 723 if (dominators != NULL) { 724 dominators_ = *dominators; 725 } 726 } 727 bool is_done() { return dominated_index_ >= length_; } 728 729 GvnBasicBlockState(GvnBasicBlockState* previous, 730 HBasicBlock* block, 731 HInstructionMap* map, 732 HSideEffectMap* dominators, 733 Zone* zone) 734 : previous_(previous), next_(NULL) { 735 Initialize(block, map, dominators, true, zone); 736 } 737 738 GvnBasicBlockState* next_dominated(Zone* zone) { 739 dominated_index_++; 740 if (dominated_index_ == length_ - 1) { 741 // No need to copy the map for the last child in the dominator tree. 742 Initialize(block_->dominated_blocks()->at(dominated_index_), 743 map(), 744 dominators(), 745 false, 746 zone); 747 return this; 748 } else if (dominated_index_ < length_) { 749 return push(zone, block_->dominated_blocks()->at(dominated_index_)); 750 } else { 751 return NULL; 752 } 753 } 754 755 GvnBasicBlockState* push(Zone* zone, HBasicBlock* block) { 756 if (next_ == NULL) { 757 next_ = 758 new(zone) GvnBasicBlockState(this, block, map(), dominators(), zone); 759 } else { 760 next_->Initialize(block, map(), dominators(), true, zone); 761 } 762 return next_; 763 } 764 GvnBasicBlockState* pop() { 765 GvnBasicBlockState* result = previous_; 766 while (result != NULL && result->is_done()) { 767 TRACE_GVN_2("Backtracking from block B%d to block b%d\n", 768 block()->block_id(), 769 previous_->block()->block_id()) 770 result = result->previous_; 771 } 772 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 void HGlobalValueNumberingPhase::AnalyzeGraph() { 790 HBasicBlock* entry_block = graph()->entry_block(); 791 HInstructionMap* entry_map = 792 new(zone()) HInstructionMap(zone(), &side_effects_tracker_); 793 GvnBasicBlockState* current = 794 GvnBasicBlockState::CreateEntry(zone(), entry_block, entry_map); 795 796 while (current != NULL) { 797 HBasicBlock* block = current->block(); 798 HInstructionMap* map = current->map(); 799 HSideEffectMap* dominators = current->dominators(); 800 801 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 if (block->IsLoopHeader()) { 807 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 for (HInstructionIterator it(block); !it.Done(); it.Advance()) { 813 HInstruction* instr = it.Current(); 814 if (instr->CheckFlag(HValue::kTrackSideEffectDominators)) { 815 for (int i = 0; i < kNumberOfTrackedSideEffects; i++) { 816 HValue* other = dominators->at(i); 817 GVNFlag flag = GVNFlagFromInt(i); 818 if (instr->DependsOnFlags().Contains(flag) && other != NULL) { 819 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 if (instr->HandleSideEffectDominator(flag, other)) { 826 removed_side_effects_ = true; 827 } 828 } 829 } 830 } 831 // Instruction was unlinked during graph traversal. 832 if (!instr->IsLinked()) continue; 833 834 SideEffects changes = side_effects_tracker_.ComputeChanges(instr); 835 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 map->Kill(changes); 839 dominators->Store(changes, instr); 840 if (FLAG_trace_gvn) { 841 OFStream os(stdout); 842 os << "Instruction i" << instr->id() << " changes " << Print(changes) 843 << std::endl; 844 } 845 } 846 if (instr->CheckFlag(HValue::kUseGVN) && 847 !instr->CheckFlag(HValue::kCantBeReplaced)) { 848 DCHECK(!instr->HasObservableSideEffects()); 849 HInstruction* other = map->Lookup(instr); 850 if (other != NULL) { 851 DCHECK(instr->Equals(other) && other->Equals(instr)); 852 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 if (instr->HasSideEffects()) removed_side_effects_ = true; 858 instr->DeleteAndReplaceWith(other); 859 } else { 860 map->Add(instr, zone()); 861 } 862 } 863 } 864 865 HBasicBlock* dominator_block; 866 GvnBasicBlockState* next = 867 current->next_in_dominator_tree_traversal(zone(), 868 &dominator_block); 869 870 if (next != NULL) { 871 HBasicBlock* dominated = next->block(); 872 HInstructionMap* successor_map = next->map(); 873 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 if ((!successor_map->IsEmpty() || !successor_dominators->IsEmpty()) && 881 dominator_block->block_id() + 1 < dominated->block_id()) { 882 visited_on_paths_.Clear(); 883 SideEffects side_effects_on_all_paths = 884 CollectSideEffectsOnPathsToDominatedBlock(dominator_block, 885 dominated); 886 successor_map->Kill(side_effects_on_all_paths); 887 successor_dominators->Kill(side_effects_on_all_paths); 888 } 889 } 890 current = next; 891 } 892 } 893 894 } // namespace internal 895 } // namespace v8 896