1 //===- RegionInfoImpl.h - SESE region detection analysis --------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // Detects single entry single exit regions in the control flow graph. 10 //===----------------------------------------------------------------------===// 11 12 #ifndef LLVM_ANALYSIS_REGIONINFOIMPL_H 13 #define LLVM_ANALYSIS_REGIONINFOIMPL_H 14 15 #include "llvm/ADT/PostOrderIterator.h" 16 #include "llvm/Analysis/DominanceFrontier.h" 17 #include "llvm/Analysis/LoopInfo.h" 18 #include "llvm/Analysis/PostDominators.h" 19 #include "llvm/Analysis/RegionInfo.h" 20 #include "llvm/Analysis/RegionIterator.h" 21 #include "llvm/Support/CommandLine.h" 22 #include "llvm/Support/Debug.h" 23 #include "llvm/Support/ErrorHandling.h" 24 #include <algorithm> 25 #include <iterator> 26 #include <set> 27 28 namespace llvm { 29 30 #define DEBUG_TYPE "region" 31 32 //===----------------------------------------------------------------------===// 33 /// RegionBase Implementation 34 template <class Tr> 35 RegionBase<Tr>::RegionBase(BlockT *Entry, BlockT *Exit, 36 typename Tr::RegionInfoT *RInfo, DomTreeT *dt, 37 RegionT *Parent) 38 : RegionNodeBase<Tr>(Parent, Entry, 1), RI(RInfo), DT(dt), exit(Exit) {} 39 40 template <class Tr> 41 RegionBase<Tr>::~RegionBase() { 42 // Free the cached nodes. 43 for (typename BBNodeMapT::iterator it = BBNodeMap.begin(), 44 ie = BBNodeMap.end(); 45 it != ie; ++it) 46 delete it->second; 47 48 // Only clean the cache for this Region. Caches of child Regions will be 49 // cleaned when the child Regions are deleted. 50 BBNodeMap.clear(); 51 } 52 53 template <class Tr> 54 void RegionBase<Tr>::replaceEntry(BlockT *BB) { 55 this->entry.setPointer(BB); 56 } 57 58 template <class Tr> 59 void RegionBase<Tr>::replaceExit(BlockT *BB) { 60 assert(exit && "No exit to replace!"); 61 exit = BB; 62 } 63 64 template <class Tr> 65 void RegionBase<Tr>::replaceEntryRecursive(BlockT *NewEntry) { 66 std::vector<RegionT *> RegionQueue; 67 BlockT *OldEntry = getEntry(); 68 69 RegionQueue.push_back(static_cast<RegionT *>(this)); 70 while (!RegionQueue.empty()) { 71 RegionT *R = RegionQueue.back(); 72 RegionQueue.pop_back(); 73 74 R->replaceEntry(NewEntry); 75 for (typename RegionT::const_iterator RI = R->begin(), RE = R->end(); 76 RI != RE; ++RI) { 77 if ((*RI)->getEntry() == OldEntry) 78 RegionQueue.push_back(RI->get()); 79 } 80 } 81 } 82 83 template <class Tr> 84 void RegionBase<Tr>::replaceExitRecursive(BlockT *NewExit) { 85 std::vector<RegionT *> RegionQueue; 86 BlockT *OldExit = getExit(); 87 88 RegionQueue.push_back(static_cast<RegionT *>(this)); 89 while (!RegionQueue.empty()) { 90 RegionT *R = RegionQueue.back(); 91 RegionQueue.pop_back(); 92 93 R->replaceExit(NewExit); 94 for (typename RegionT::const_iterator RI = R->begin(), RE = R->end(); 95 RI != RE; ++RI) { 96 if ((*RI)->getExit() == OldExit) 97 RegionQueue.push_back(RI->get()); 98 } 99 } 100 } 101 102 template <class Tr> 103 bool RegionBase<Tr>::contains(const BlockT *B) const { 104 BlockT *BB = const_cast<BlockT *>(B); 105 106 if (!DT->getNode(BB)) 107 return false; 108 109 BlockT *entry = getEntry(), *exit = getExit(); 110 111 // Toplevel region. 112 if (!exit) 113 return true; 114 115 return (DT->dominates(entry, BB) && 116 !(DT->dominates(exit, BB) && DT->dominates(entry, exit))); 117 } 118 119 template <class Tr> 120 bool RegionBase<Tr>::contains(const LoopT *L) const { 121 // BBs that are not part of any loop are element of the Loop 122 // described by the NULL pointer. This loop is not part of any region, 123 // except if the region describes the whole function. 124 if (!L) 125 return getExit() == nullptr; 126 127 if (!contains(L->getHeader())) 128 return false; 129 130 SmallVector<BlockT *, 8> ExitingBlocks; 131 L->getExitingBlocks(ExitingBlocks); 132 133 for (BlockT *BB : ExitingBlocks) { 134 if (!contains(BB)) 135 return false; 136 } 137 138 return true; 139 } 140 141 template <class Tr> 142 typename Tr::LoopT *RegionBase<Tr>::outermostLoopInRegion(LoopT *L) const { 143 if (!contains(L)) 144 return nullptr; 145 146 while (L && contains(L->getParentLoop())) { 147 L = L->getParentLoop(); 148 } 149 150 return L; 151 } 152 153 template <class Tr> 154 typename Tr::LoopT *RegionBase<Tr>::outermostLoopInRegion(LoopInfoT *LI, 155 BlockT *BB) const { 156 assert(LI && BB && "LI and BB cannot be null!"); 157 LoopT *L = LI->getLoopFor(BB); 158 return outermostLoopInRegion(L); 159 } 160 161 template <class Tr> 162 typename RegionBase<Tr>::BlockT *RegionBase<Tr>::getEnteringBlock() const { 163 BlockT *entry = getEntry(); 164 BlockT *Pred; 165 BlockT *enteringBlock = nullptr; 166 167 for (PredIterTy PI = InvBlockTraits::child_begin(entry), 168 PE = InvBlockTraits::child_end(entry); 169 PI != PE; ++PI) { 170 Pred = *PI; 171 if (DT->getNode(Pred) && !contains(Pred)) { 172 if (enteringBlock) 173 return nullptr; 174 175 enteringBlock = Pred; 176 } 177 } 178 179 return enteringBlock; 180 } 181 182 template <class Tr> 183 typename RegionBase<Tr>::BlockT *RegionBase<Tr>::getExitingBlock() const { 184 BlockT *exit = getExit(); 185 BlockT *Pred; 186 BlockT *exitingBlock = nullptr; 187 188 if (!exit) 189 return nullptr; 190 191 for (PredIterTy PI = InvBlockTraits::child_begin(exit), 192 PE = InvBlockTraits::child_end(exit); 193 PI != PE; ++PI) { 194 Pred = *PI; 195 if (contains(Pred)) { 196 if (exitingBlock) 197 return nullptr; 198 199 exitingBlock = Pred; 200 } 201 } 202 203 return exitingBlock; 204 } 205 206 template <class Tr> 207 bool RegionBase<Tr>::isSimple() const { 208 return !isTopLevelRegion() && getEnteringBlock() && getExitingBlock(); 209 } 210 211 template <class Tr> 212 std::string RegionBase<Tr>::getNameStr() const { 213 std::string exitName; 214 std::string entryName; 215 216 if (getEntry()->getName().empty()) { 217 raw_string_ostream OS(entryName); 218 219 getEntry()->printAsOperand(OS, false); 220 } else 221 entryName = getEntry()->getName(); 222 223 if (getExit()) { 224 if (getExit()->getName().empty()) { 225 raw_string_ostream OS(exitName); 226 227 getExit()->printAsOperand(OS, false); 228 } else 229 exitName = getExit()->getName(); 230 } else 231 exitName = "<Function Return>"; 232 233 return entryName + " => " + exitName; 234 } 235 236 template <class Tr> 237 void RegionBase<Tr>::verifyBBInRegion(BlockT *BB) const { 238 if (!contains(BB)) 239 llvm_unreachable("Broken region found!"); 240 241 BlockT *entry = getEntry(), *exit = getExit(); 242 243 for (SuccIterTy SI = BlockTraits::child_begin(BB), 244 SE = BlockTraits::child_end(BB); 245 SI != SE; ++SI) { 246 if (!contains(*SI) && exit != *SI) 247 llvm_unreachable("Broken region found!"); 248 } 249 250 if (entry != BB) { 251 for (PredIterTy SI = InvBlockTraits::child_begin(BB), 252 SE = InvBlockTraits::child_end(BB); 253 SI != SE; ++SI) { 254 if (!contains(*SI)) 255 llvm_unreachable("Broken region found!"); 256 } 257 } 258 } 259 260 template <class Tr> 261 void RegionBase<Tr>::verifyWalk(BlockT *BB, std::set<BlockT *> *visited) const { 262 BlockT *exit = getExit(); 263 264 visited->insert(BB); 265 266 verifyBBInRegion(BB); 267 268 for (SuccIterTy SI = BlockTraits::child_begin(BB), 269 SE = BlockTraits::child_end(BB); 270 SI != SE; ++SI) { 271 if (*SI != exit && visited->find(*SI) == visited->end()) 272 verifyWalk(*SI, visited); 273 } 274 } 275 276 template <class Tr> 277 void RegionBase<Tr>::verifyRegion() const { 278 // Only do verification when user wants to, otherwise this expensive check 279 // will be invoked by PMDataManager::verifyPreservedAnalysis when 280 // a regionpass (marked PreservedAll) finish. 281 if (!RegionInfoBase<Tr>::VerifyRegionInfo) 282 return; 283 284 std::set<BlockT *> visited; 285 verifyWalk(getEntry(), &visited); 286 } 287 288 template <class Tr> 289 void RegionBase<Tr>::verifyRegionNest() const { 290 for (typename RegionT::const_iterator RI = begin(), RE = end(); RI != RE; 291 ++RI) 292 (*RI)->verifyRegionNest(); 293 294 verifyRegion(); 295 } 296 297 template <class Tr> 298 typename RegionBase<Tr>::element_iterator RegionBase<Tr>::element_begin() { 299 return GraphTraits<RegionT *>::nodes_begin(static_cast<RegionT *>(this)); 300 } 301 302 template <class Tr> 303 typename RegionBase<Tr>::element_iterator RegionBase<Tr>::element_end() { 304 return GraphTraits<RegionT *>::nodes_end(static_cast<RegionT *>(this)); 305 } 306 307 template <class Tr> 308 typename RegionBase<Tr>::const_element_iterator 309 RegionBase<Tr>::element_begin() const { 310 return GraphTraits<const RegionT *>::nodes_begin( 311 static_cast<const RegionT *>(this)); 312 } 313 314 template <class Tr> 315 typename RegionBase<Tr>::const_element_iterator 316 RegionBase<Tr>::element_end() const { 317 return GraphTraits<const RegionT *>::nodes_end( 318 static_cast<const RegionT *>(this)); 319 } 320 321 template <class Tr> 322 typename Tr::RegionT *RegionBase<Tr>::getSubRegionNode(BlockT *BB) const { 323 typedef typename Tr::RegionT RegionT; 324 RegionT *R = RI->getRegionFor(BB); 325 326 if (!R || R == this) 327 return nullptr; 328 329 // If we pass the BB out of this region, that means our code is broken. 330 assert(contains(R) && "BB not in current region!"); 331 332 while (contains(R->getParent()) && R->getParent() != this) 333 R = R->getParent(); 334 335 if (R->getEntry() != BB) 336 return nullptr; 337 338 return R; 339 } 340 341 template <class Tr> 342 typename Tr::RegionNodeT *RegionBase<Tr>::getBBNode(BlockT *BB) const { 343 assert(contains(BB) && "Can get BB node out of this region!"); 344 345 typename BBNodeMapT::const_iterator at = BBNodeMap.find(BB); 346 347 if (at != BBNodeMap.end()) 348 return at->second; 349 350 auto Deconst = const_cast<RegionBase<Tr> *>(this); 351 RegionNodeT *NewNode = new RegionNodeT(static_cast<RegionT *>(Deconst), BB); 352 BBNodeMap.insert(std::make_pair(BB, NewNode)); 353 return NewNode; 354 } 355 356 template <class Tr> 357 typename Tr::RegionNodeT *RegionBase<Tr>::getNode(BlockT *BB) const { 358 assert(contains(BB) && "Can get BB node out of this region!"); 359 if (RegionT *Child = getSubRegionNode(BB)) 360 return Child->getNode(); 361 362 return getBBNode(BB); 363 } 364 365 template <class Tr> 366 void RegionBase<Tr>::transferChildrenTo(RegionT *To) { 367 for (iterator I = begin(), E = end(); I != E; ++I) { 368 (*I)->parent = To; 369 To->children.push_back(std::move(*I)); 370 } 371 children.clear(); 372 } 373 374 template <class Tr> 375 void RegionBase<Tr>::addSubRegion(RegionT *SubRegion, bool moveChildren) { 376 assert(!SubRegion->parent && "SubRegion already has a parent!"); 377 assert(std::find_if(begin(), end(), [&](const std::unique_ptr<RegionT> &R) { 378 return R.get() == SubRegion; 379 }) == children.end() && 380 "Subregion already exists!"); 381 382 SubRegion->parent = static_cast<RegionT *>(this); 383 children.push_back(std::unique_ptr<RegionT>(SubRegion)); 384 385 if (!moveChildren) 386 return; 387 388 assert(SubRegion->children.empty() && 389 "SubRegions that contain children are not supported"); 390 391 for (element_iterator I = element_begin(), E = element_end(); I != E; ++I) { 392 if (!(*I)->isSubRegion()) { 393 BlockT *BB = (*I)->template getNodeAs<BlockT>(); 394 395 if (SubRegion->contains(BB)) 396 RI->setRegionFor(BB, SubRegion); 397 } 398 } 399 400 std::vector<std::unique_ptr<RegionT>> Keep; 401 for (iterator I = begin(), E = end(); I != E; ++I) { 402 if (SubRegion->contains(I->get()) && I->get() != SubRegion) { 403 (*I)->parent = SubRegion; 404 SubRegion->children.push_back(std::move(*I)); 405 } else 406 Keep.push_back(std::move(*I)); 407 } 408 409 children.clear(); 410 children.insert( 411 children.begin(), 412 std::move_iterator<typename RegionSet::iterator>(Keep.begin()), 413 std::move_iterator<typename RegionSet::iterator>(Keep.end())); 414 } 415 416 template <class Tr> 417 typename Tr::RegionT *RegionBase<Tr>::removeSubRegion(RegionT *Child) { 418 assert(Child->parent == this && "Child is not a child of this region!"); 419 Child->parent = nullptr; 420 typename RegionSet::iterator I = std::find_if( 421 children.begin(), children.end(), 422 [&](const std::unique_ptr<RegionT> &R) { return R.get() == Child; }); 423 assert(I != children.end() && "Region does not exit. Unable to remove."); 424 children.erase(children.begin() + (I - begin())); 425 return Child; 426 } 427 428 template <class Tr> 429 unsigned RegionBase<Tr>::getDepth() const { 430 unsigned Depth = 0; 431 432 for (RegionT *R = getParent(); R != nullptr; R = R->getParent()) 433 ++Depth; 434 435 return Depth; 436 } 437 438 template <class Tr> 439 typename Tr::RegionT *RegionBase<Tr>::getExpandedRegion() const { 440 unsigned NumSuccessors = Tr::getNumSuccessors(exit); 441 442 if (NumSuccessors == 0) 443 return nullptr; 444 445 for (PredIterTy PI = InvBlockTraits::child_begin(getExit()), 446 PE = InvBlockTraits::child_end(getExit()); 447 PI != PE; ++PI) { 448 if (!DT->dominates(getEntry(), *PI)) 449 return nullptr; 450 } 451 452 RegionT *R = RI->getRegionFor(exit); 453 454 if (R->getEntry() != exit) { 455 if (Tr::getNumSuccessors(exit) == 1) 456 return new RegionT(getEntry(), *BlockTraits::child_begin(exit), RI, DT); 457 return nullptr; 458 } 459 460 while (R->getParent() && R->getParent()->getEntry() == exit) 461 R = R->getParent(); 462 463 if (!DT->dominates(getEntry(), R->getExit())) { 464 for (PredIterTy PI = InvBlockTraits::child_begin(getExit()), 465 PE = InvBlockTraits::child_end(getExit()); 466 PI != PE; ++PI) { 467 if (!DT->dominates(R->getExit(), *PI)) 468 return nullptr; 469 } 470 } 471 472 return new RegionT(getEntry(), R->getExit(), RI, DT); 473 } 474 475 template <class Tr> 476 void RegionBase<Tr>::print(raw_ostream &OS, bool print_tree, unsigned level, 477 PrintStyle Style) const { 478 if (print_tree) 479 OS.indent(level * 2) << '[' << level << "] " << getNameStr(); 480 else 481 OS.indent(level * 2) << getNameStr(); 482 483 OS << '\n'; 484 485 if (Style != PrintNone) { 486 OS.indent(level * 2) << "{\n"; 487 OS.indent(level * 2 + 2); 488 489 if (Style == PrintBB) { 490 for (const auto *BB : blocks()) 491 OS << BB->getName() << ", "; // TODO: remove the last "," 492 } else if (Style == PrintRN) { 493 for (const_element_iterator I = element_begin(), E = element_end(); 494 I != E; ++I) { 495 OS << **I << ", "; // TODO: remove the last ", 496 } 497 } 498 499 OS << '\n'; 500 } 501 502 if (print_tree) { 503 for (const_iterator RI = begin(), RE = end(); RI != RE; ++RI) 504 (*RI)->print(OS, print_tree, level + 1, Style); 505 } 506 507 if (Style != PrintNone) 508 OS.indent(level * 2) << "} \n"; 509 } 510 511 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 512 template <class Tr> 513 void RegionBase<Tr>::dump() const { 514 print(dbgs(), true, getDepth(), RegionInfoBase<Tr>::printStyle); 515 } 516 #endif 517 518 template <class Tr> 519 void RegionBase<Tr>::clearNodeCache() { 520 // Free the cached nodes. 521 for (typename BBNodeMapT::iterator I = BBNodeMap.begin(), 522 IE = BBNodeMap.end(); 523 I != IE; ++I) 524 delete I->second; 525 526 BBNodeMap.clear(); 527 for (typename RegionT::iterator RI = begin(), RE = end(); RI != RE; ++RI) 528 (*RI)->clearNodeCache(); 529 } 530 531 //===----------------------------------------------------------------------===// 532 // RegionInfoBase implementation 533 // 534 535 template <class Tr> 536 RegionInfoBase<Tr>::RegionInfoBase() 537 : TopLevelRegion(nullptr) {} 538 539 template <class Tr> 540 RegionInfoBase<Tr>::~RegionInfoBase() { 541 releaseMemory(); 542 } 543 544 template <class Tr> 545 bool RegionInfoBase<Tr>::isCommonDomFrontier(BlockT *BB, BlockT *entry, 546 BlockT *exit) const { 547 for (PredIterTy PI = InvBlockTraits::child_begin(BB), 548 PE = InvBlockTraits::child_end(BB); 549 PI != PE; ++PI) { 550 BlockT *P = *PI; 551 if (DT->dominates(entry, P) && !DT->dominates(exit, P)) 552 return false; 553 } 554 555 return true; 556 } 557 558 template <class Tr> 559 bool RegionInfoBase<Tr>::isRegion(BlockT *entry, BlockT *exit) const { 560 assert(entry && exit && "entry and exit must not be null!"); 561 typedef typename DomFrontierT::DomSetType DST; 562 563 DST *entrySuccs = &DF->find(entry)->second; 564 565 // Exit is the header of a loop that contains the entry. In this case, 566 // the dominance frontier must only contain the exit. 567 if (!DT->dominates(entry, exit)) { 568 for (typename DST::iterator SI = entrySuccs->begin(), 569 SE = entrySuccs->end(); 570 SI != SE; ++SI) { 571 if (*SI != exit && *SI != entry) 572 return false; 573 } 574 575 return true; 576 } 577 578 DST *exitSuccs = &DF->find(exit)->second; 579 580 // Do not allow edges leaving the region. 581 for (typename DST::iterator SI = entrySuccs->begin(), SE = entrySuccs->end(); 582 SI != SE; ++SI) { 583 if (*SI == exit || *SI == entry) 584 continue; 585 if (exitSuccs->find(*SI) == exitSuccs->end()) 586 return false; 587 if (!isCommonDomFrontier(*SI, entry, exit)) 588 return false; 589 } 590 591 // Do not allow edges pointing into the region. 592 for (typename DST::iterator SI = exitSuccs->begin(), SE = exitSuccs->end(); 593 SI != SE; ++SI) { 594 if (DT->properlyDominates(entry, *SI) && *SI != exit) 595 return false; 596 } 597 598 return true; 599 } 600 601 template <class Tr> 602 void RegionInfoBase<Tr>::insertShortCut(BlockT *entry, BlockT *exit, 603 BBtoBBMap *ShortCut) const { 604 assert(entry && exit && "entry and exit must not be null!"); 605 606 typename BBtoBBMap::iterator e = ShortCut->find(exit); 607 608 if (e == ShortCut->end()) 609 // No further region at exit available. 610 (*ShortCut)[entry] = exit; 611 else { 612 // We found a region e that starts at exit. Therefore (entry, e->second) 613 // is also a region, that is larger than (entry, exit). Insert the 614 // larger one. 615 BlockT *BB = e->second; 616 (*ShortCut)[entry] = BB; 617 } 618 } 619 620 template <class Tr> 621 typename Tr::DomTreeNodeT * 622 RegionInfoBase<Tr>::getNextPostDom(DomTreeNodeT *N, BBtoBBMap *ShortCut) const { 623 typename BBtoBBMap::iterator e = ShortCut->find(N->getBlock()); 624 625 if (e == ShortCut->end()) 626 return N->getIDom(); 627 628 return PDT->getNode(e->second)->getIDom(); 629 } 630 631 template <class Tr> 632 bool RegionInfoBase<Tr>::isTrivialRegion(BlockT *entry, BlockT *exit) const { 633 assert(entry && exit && "entry and exit must not be null!"); 634 635 unsigned num_successors = 636 BlockTraits::child_end(entry) - BlockTraits::child_begin(entry); 637 638 if (num_successors <= 1 && exit == *(BlockTraits::child_begin(entry))) 639 return true; 640 641 return false; 642 } 643 644 template <class Tr> 645 typename Tr::RegionT *RegionInfoBase<Tr>::createRegion(BlockT *entry, 646 BlockT *exit) { 647 assert(entry && exit && "entry and exit must not be null!"); 648 649 if (isTrivialRegion(entry, exit)) 650 return nullptr; 651 652 RegionT *region = 653 new RegionT(entry, exit, static_cast<RegionInfoT *>(this), DT); 654 BBtoRegion.insert(std::make_pair(entry, region)); 655 656 #ifdef XDEBUG 657 region->verifyRegion(); 658 #else 659 DEBUG(region->verifyRegion()); 660 #endif 661 662 updateStatistics(region); 663 return region; 664 } 665 666 template <class Tr> 667 void RegionInfoBase<Tr>::findRegionsWithEntry(BlockT *entry, 668 BBtoBBMap *ShortCut) { 669 assert(entry); 670 671 DomTreeNodeT *N = PDT->getNode(entry); 672 if (!N) 673 return; 674 675 RegionT *lastRegion = nullptr; 676 BlockT *lastExit = entry; 677 678 // As only a BasicBlock that postdominates entry can finish a region, walk the 679 // post dominance tree upwards. 680 while ((N = getNextPostDom(N, ShortCut))) { 681 BlockT *exit = N->getBlock(); 682 683 if (!exit) 684 break; 685 686 if (isRegion(entry, exit)) { 687 RegionT *newRegion = createRegion(entry, exit); 688 689 if (lastRegion) 690 newRegion->addSubRegion(lastRegion); 691 692 lastRegion = newRegion; 693 lastExit = exit; 694 } 695 696 // This can never be a region, so stop the search. 697 if (!DT->dominates(entry, exit)) 698 break; 699 } 700 701 // Tried to create regions from entry to lastExit. Next time take a 702 // shortcut from entry to lastExit. 703 if (lastExit != entry) 704 insertShortCut(entry, lastExit, ShortCut); 705 } 706 707 template <class Tr> 708 void RegionInfoBase<Tr>::scanForRegions(FuncT &F, BBtoBBMap *ShortCut) { 709 typedef typename std::add_pointer<FuncT>::type FuncPtrT; 710 BlockT *entry = GraphTraits<FuncPtrT>::getEntryNode(&F); 711 DomTreeNodeT *N = DT->getNode(entry); 712 713 // Iterate over the dominance tree in post order to start with the small 714 // regions from the bottom of the dominance tree. If the small regions are 715 // detected first, detection of bigger regions is faster, as we can jump 716 // over the small regions. 717 for (auto DomNode : post_order(N)) 718 findRegionsWithEntry(DomNode->getBlock(), ShortCut); 719 } 720 721 template <class Tr> 722 typename Tr::RegionT *RegionInfoBase<Tr>::getTopMostParent(RegionT *region) { 723 while (region->getParent()) 724 region = region->getParent(); 725 726 return region; 727 } 728 729 template <class Tr> 730 void RegionInfoBase<Tr>::buildRegionsTree(DomTreeNodeT *N, RegionT *region) { 731 BlockT *BB = N->getBlock(); 732 733 // Passed region exit 734 while (BB == region->getExit()) 735 region = region->getParent(); 736 737 typename BBtoRegionMap::iterator it = BBtoRegion.find(BB); 738 739 // This basic block is a start block of a region. It is already in the 740 // BBtoRegion relation. Only the child basic blocks have to be updated. 741 if (it != BBtoRegion.end()) { 742 RegionT *newRegion = it->second; 743 region->addSubRegion(getTopMostParent(newRegion)); 744 region = newRegion; 745 } else { 746 BBtoRegion[BB] = region; 747 } 748 749 for (typename DomTreeNodeT::iterator CI = N->begin(), CE = N->end(); CI != CE; 750 ++CI) { 751 buildRegionsTree(*CI, region); 752 } 753 } 754 755 #ifdef XDEBUG 756 template <class Tr> 757 bool RegionInfoBase<Tr>::VerifyRegionInfo = true; 758 #else 759 template <class Tr> 760 bool RegionInfoBase<Tr>::VerifyRegionInfo = false; 761 #endif 762 763 template <class Tr> 764 typename Tr::RegionT::PrintStyle RegionInfoBase<Tr>::printStyle = 765 RegionBase<Tr>::PrintNone; 766 767 template <class Tr> 768 void RegionInfoBase<Tr>::print(raw_ostream &OS) const { 769 OS << "Region tree:\n"; 770 TopLevelRegion->print(OS, true, 0, printStyle); 771 OS << "End region tree\n"; 772 } 773 774 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 775 template <class Tr> 776 void RegionInfoBase<Tr>::dump() const { print(dbgs()); } 777 #endif 778 779 template <class Tr> 780 void RegionInfoBase<Tr>::releaseMemory() { 781 BBtoRegion.clear(); 782 if (TopLevelRegion) 783 delete TopLevelRegion; 784 TopLevelRegion = nullptr; 785 } 786 787 template <class Tr> 788 void RegionInfoBase<Tr>::verifyAnalysis() const { 789 TopLevelRegion->verifyRegionNest(); 790 } 791 792 // Region pass manager support. 793 template <class Tr> 794 typename Tr::RegionT *RegionInfoBase<Tr>::getRegionFor(BlockT *BB) const { 795 typename BBtoRegionMap::const_iterator I = BBtoRegion.find(BB); 796 return I != BBtoRegion.end() ? I->second : nullptr; 797 } 798 799 template <class Tr> 800 void RegionInfoBase<Tr>::setRegionFor(BlockT *BB, RegionT *R) { 801 BBtoRegion[BB] = R; 802 } 803 804 template <class Tr> 805 typename Tr::RegionT *RegionInfoBase<Tr>::operator[](BlockT *BB) const { 806 return getRegionFor(BB); 807 } 808 809 template <class Tr> 810 typename RegionInfoBase<Tr>::BlockT * 811 RegionInfoBase<Tr>::getMaxRegionExit(BlockT *BB) const { 812 BlockT *Exit = nullptr; 813 814 while (true) { 815 // Get largest region that starts at BB. 816 RegionT *R = getRegionFor(BB); 817 while (R && R->getParent() && R->getParent()->getEntry() == BB) 818 R = R->getParent(); 819 820 // Get the single exit of BB. 821 if (R && R->getEntry() == BB) 822 Exit = R->getExit(); 823 else if (++BlockTraits::child_begin(BB) == BlockTraits::child_end(BB)) 824 Exit = *BlockTraits::child_begin(BB); 825 else // No single exit exists. 826 return Exit; 827 828 // Get largest region that starts at Exit. 829 RegionT *ExitR = getRegionFor(Exit); 830 while (ExitR && ExitR->getParent() && 831 ExitR->getParent()->getEntry() == Exit) 832 ExitR = ExitR->getParent(); 833 834 for (PredIterTy PI = InvBlockTraits::child_begin(Exit), 835 PE = InvBlockTraits::child_end(Exit); 836 PI != PE; ++PI) { 837 if (!R->contains(*PI) && !ExitR->contains(*PI)) 838 break; 839 } 840 841 // This stops infinite cycles. 842 if (DT->dominates(Exit, BB)) 843 break; 844 845 BB = Exit; 846 } 847 848 return Exit; 849 } 850 851 template <class Tr> 852 typename Tr::RegionT *RegionInfoBase<Tr>::getCommonRegion(RegionT *A, 853 RegionT *B) const { 854 assert(A && B && "One of the Regions is NULL"); 855 856 if (A->contains(B)) 857 return A; 858 859 while (!B->contains(A)) 860 B = B->getParent(); 861 862 return B; 863 } 864 865 template <class Tr> 866 typename Tr::RegionT * 867 RegionInfoBase<Tr>::getCommonRegion(SmallVectorImpl<RegionT *> &Regions) const { 868 RegionT *ret = Regions.back(); 869 Regions.pop_back(); 870 871 for (RegionT *R : Regions) 872 ret = getCommonRegion(ret, R); 873 874 return ret; 875 } 876 877 template <class Tr> 878 typename Tr::RegionT * 879 RegionInfoBase<Tr>::getCommonRegion(SmallVectorImpl<BlockT *> &BBs) const { 880 RegionT *ret = getRegionFor(BBs.back()); 881 BBs.pop_back(); 882 883 for (BlockT *BB : BBs) 884 ret = getCommonRegion(ret, getRegionFor(BB)); 885 886 return ret; 887 } 888 889 template <class Tr> 890 void RegionInfoBase<Tr>::splitBlock(BlockT *NewBB, BlockT *OldBB) { 891 RegionT *R = getRegionFor(OldBB); 892 893 setRegionFor(NewBB, R); 894 895 while (R->getEntry() == OldBB && !R->isTopLevelRegion()) { 896 R->replaceEntry(NewBB); 897 R = R->getParent(); 898 } 899 900 setRegionFor(OldBB, R); 901 } 902 903 template <class Tr> 904 void RegionInfoBase<Tr>::calculate(FuncT &F) { 905 typedef typename std::add_pointer<FuncT>::type FuncPtrT; 906 907 // ShortCut a function where for every BB the exit of the largest region 908 // starting with BB is stored. These regions can be threated as single BBS. 909 // This improves performance on linear CFGs. 910 BBtoBBMap ShortCut; 911 912 scanForRegions(F, &ShortCut); 913 BlockT *BB = GraphTraits<FuncPtrT>::getEntryNode(&F); 914 buildRegionsTree(DT->getNode(BB), TopLevelRegion); 915 } 916 917 #undef DEBUG_TYPE 918 919 } // end namespace llvm 920 921 #endif 922