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: enumerated BB not in region!"); 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: edges leaving the region must go " 248 "to the exit node!"); 249 } 250 251 if (entry != BB) { 252 for (PredIterTy SI = InvBlockTraits::child_begin(BB), 253 SE = InvBlockTraits::child_end(BB); 254 SI != SE; ++SI) { 255 if (!contains(*SI)) 256 llvm_unreachable("Broken region found: edges entering the region must " 257 "go to the entry node!"); 258 } 259 } 260 } 261 262 template <class Tr> 263 void RegionBase<Tr>::verifyWalk(BlockT *BB, std::set<BlockT *> *visited) const { 264 BlockT *exit = getExit(); 265 266 visited->insert(BB); 267 268 verifyBBInRegion(BB); 269 270 for (SuccIterTy SI = BlockTraits::child_begin(BB), 271 SE = BlockTraits::child_end(BB); 272 SI != SE; ++SI) { 273 if (*SI != exit && visited->find(*SI) == visited->end()) 274 verifyWalk(*SI, visited); 275 } 276 } 277 278 template <class Tr> 279 void RegionBase<Tr>::verifyRegion() const { 280 // Only do verification when user wants to, otherwise this expensive check 281 // will be invoked by PMDataManager::verifyPreservedAnalysis when 282 // a regionpass (marked PreservedAll) finish. 283 if (!RegionInfoBase<Tr>::VerifyRegionInfo) 284 return; 285 286 std::set<BlockT *> visited; 287 verifyWalk(getEntry(), &visited); 288 } 289 290 template <class Tr> 291 void RegionBase<Tr>::verifyRegionNest() const { 292 for (typename RegionT::const_iterator RI = begin(), RE = end(); RI != RE; 293 ++RI) 294 (*RI)->verifyRegionNest(); 295 296 verifyRegion(); 297 } 298 299 template <class Tr> 300 typename RegionBase<Tr>::element_iterator RegionBase<Tr>::element_begin() { 301 return GraphTraits<RegionT *>::nodes_begin(static_cast<RegionT *>(this)); 302 } 303 304 template <class Tr> 305 typename RegionBase<Tr>::element_iterator RegionBase<Tr>::element_end() { 306 return GraphTraits<RegionT *>::nodes_end(static_cast<RegionT *>(this)); 307 } 308 309 template <class Tr> 310 typename RegionBase<Tr>::const_element_iterator 311 RegionBase<Tr>::element_begin() const { 312 return GraphTraits<const RegionT *>::nodes_begin( 313 static_cast<const RegionT *>(this)); 314 } 315 316 template <class Tr> 317 typename RegionBase<Tr>::const_element_iterator 318 RegionBase<Tr>::element_end() const { 319 return GraphTraits<const RegionT *>::nodes_end( 320 static_cast<const RegionT *>(this)); 321 } 322 323 template <class Tr> 324 typename Tr::RegionT *RegionBase<Tr>::getSubRegionNode(BlockT *BB) const { 325 typedef typename Tr::RegionT RegionT; 326 RegionT *R = RI->getRegionFor(BB); 327 328 if (!R || R == this) 329 return nullptr; 330 331 // If we pass the BB out of this region, that means our code is broken. 332 assert(contains(R) && "BB not in current region!"); 333 334 while (contains(R->getParent()) && R->getParent() != this) 335 R = R->getParent(); 336 337 if (R->getEntry() != BB) 338 return nullptr; 339 340 return R; 341 } 342 343 template <class Tr> 344 typename Tr::RegionNodeT *RegionBase<Tr>::getBBNode(BlockT *BB) const { 345 assert(contains(BB) && "Can get BB node out of this region!"); 346 347 typename BBNodeMapT::const_iterator at = BBNodeMap.find(BB); 348 349 if (at != BBNodeMap.end()) 350 return at->second; 351 352 auto Deconst = const_cast<RegionBase<Tr> *>(this); 353 RegionNodeT *NewNode = new RegionNodeT(static_cast<RegionT *>(Deconst), BB); 354 BBNodeMap.insert(std::make_pair(BB, NewNode)); 355 return NewNode; 356 } 357 358 template <class Tr> 359 typename Tr::RegionNodeT *RegionBase<Tr>::getNode(BlockT *BB) const { 360 assert(contains(BB) && "Can get BB node out of this region!"); 361 if (RegionT *Child = getSubRegionNode(BB)) 362 return Child->getNode(); 363 364 return getBBNode(BB); 365 } 366 367 template <class Tr> 368 void RegionBase<Tr>::transferChildrenTo(RegionT *To) { 369 for (iterator I = begin(), E = end(); I != E; ++I) { 370 (*I)->parent = To; 371 To->children.push_back(std::move(*I)); 372 } 373 children.clear(); 374 } 375 376 template <class Tr> 377 void RegionBase<Tr>::addSubRegion(RegionT *SubRegion, bool moveChildren) { 378 assert(!SubRegion->parent && "SubRegion already has a parent!"); 379 assert(std::find_if(begin(), end(), [&](const std::unique_ptr<RegionT> &R) { 380 return R.get() == SubRegion; 381 }) == children.end() && 382 "Subregion already exists!"); 383 384 SubRegion->parent = static_cast<RegionT *>(this); 385 children.push_back(std::unique_ptr<RegionT>(SubRegion)); 386 387 if (!moveChildren) 388 return; 389 390 assert(SubRegion->children.empty() && 391 "SubRegions that contain children are not supported"); 392 393 for (element_iterator I = element_begin(), E = element_end(); I != E; ++I) { 394 if (!(*I)->isSubRegion()) { 395 BlockT *BB = (*I)->template getNodeAs<BlockT>(); 396 397 if (SubRegion->contains(BB)) 398 RI->setRegionFor(BB, SubRegion); 399 } 400 } 401 402 std::vector<std::unique_ptr<RegionT>> Keep; 403 for (iterator I = begin(), E = end(); I != E; ++I) { 404 if (SubRegion->contains(I->get()) && I->get() != SubRegion) { 405 (*I)->parent = SubRegion; 406 SubRegion->children.push_back(std::move(*I)); 407 } else 408 Keep.push_back(std::move(*I)); 409 } 410 411 children.clear(); 412 children.insert( 413 children.begin(), 414 std::move_iterator<typename RegionSet::iterator>(Keep.begin()), 415 std::move_iterator<typename RegionSet::iterator>(Keep.end())); 416 } 417 418 template <class Tr> 419 typename Tr::RegionT *RegionBase<Tr>::removeSubRegion(RegionT *Child) { 420 assert(Child->parent == this && "Child is not a child of this region!"); 421 Child->parent = nullptr; 422 typename RegionSet::iterator I = std::find_if( 423 children.begin(), children.end(), 424 [&](const std::unique_ptr<RegionT> &R) { return R.get() == Child; }); 425 assert(I != children.end() && "Region does not exit. Unable to remove."); 426 children.erase(children.begin() + (I - begin())); 427 return Child; 428 } 429 430 template <class Tr> 431 unsigned RegionBase<Tr>::getDepth() const { 432 unsigned Depth = 0; 433 434 for (RegionT *R = getParent(); R != nullptr; R = R->getParent()) 435 ++Depth; 436 437 return Depth; 438 } 439 440 template <class Tr> 441 typename Tr::RegionT *RegionBase<Tr>::getExpandedRegion() const { 442 unsigned NumSuccessors = Tr::getNumSuccessors(exit); 443 444 if (NumSuccessors == 0) 445 return nullptr; 446 447 RegionT *R = RI->getRegionFor(exit); 448 449 if (R->getEntry() != exit) { 450 for (PredIterTy PI = InvBlockTraits::child_begin(getExit()), 451 PE = InvBlockTraits::child_end(getExit()); 452 PI != PE; ++PI) 453 if (!contains(*PI)) 454 return nullptr; 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 for (PredIterTy PI = InvBlockTraits::child_begin(getExit()), 464 PE = InvBlockTraits::child_end(getExit()); 465 PI != PE; ++PI) { 466 if (!(contains(*PI) || R->contains(*PI))) 467 return nullptr; 468 } 469 470 return new RegionT(getEntry(), R->getExit(), RI, DT); 471 } 472 473 template <class Tr> 474 void RegionBase<Tr>::print(raw_ostream &OS, bool print_tree, unsigned level, 475 PrintStyle Style) const { 476 if (print_tree) 477 OS.indent(level * 2) << '[' << level << "] " << getNameStr(); 478 else 479 OS.indent(level * 2) << getNameStr(); 480 481 OS << '\n'; 482 483 if (Style != PrintNone) { 484 OS.indent(level * 2) << "{\n"; 485 OS.indent(level * 2 + 2); 486 487 if (Style == PrintBB) { 488 for (const auto *BB : blocks()) 489 OS << BB->getName() << ", "; // TODO: remove the last "," 490 } else if (Style == PrintRN) { 491 for (const_element_iterator I = element_begin(), E = element_end(); 492 I != E; ++I) { 493 OS << **I << ", "; // TODO: remove the last ", 494 } 495 } 496 497 OS << '\n'; 498 } 499 500 if (print_tree) { 501 for (const_iterator RI = begin(), RE = end(); RI != RE; ++RI) 502 (*RI)->print(OS, print_tree, level + 1, Style); 503 } 504 505 if (Style != PrintNone) 506 OS.indent(level * 2) << "} \n"; 507 } 508 509 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 510 template <class Tr> 511 void RegionBase<Tr>::dump() const { 512 print(dbgs(), true, getDepth(), RegionInfoBase<Tr>::printStyle); 513 } 514 #endif 515 516 template <class Tr> 517 void RegionBase<Tr>::clearNodeCache() { 518 // Free the cached nodes. 519 for (typename BBNodeMapT::iterator I = BBNodeMap.begin(), 520 IE = BBNodeMap.end(); 521 I != IE; ++I) 522 delete I->second; 523 524 BBNodeMap.clear(); 525 for (typename RegionT::iterator RI = begin(), RE = end(); RI != RE; ++RI) 526 (*RI)->clearNodeCache(); 527 } 528 529 //===----------------------------------------------------------------------===// 530 // RegionInfoBase implementation 531 // 532 533 template <class Tr> 534 RegionInfoBase<Tr>::RegionInfoBase() 535 : TopLevelRegion(nullptr) {} 536 537 template <class Tr> 538 RegionInfoBase<Tr>::~RegionInfoBase() { 539 releaseMemory(); 540 } 541 542 template <class Tr> 543 void RegionInfoBase<Tr>::verifyBBMap(const RegionT *R) const { 544 assert(R && "Re must be non-null"); 545 for (auto I = R->element_begin(), E = R->element_end(); I != E; ++I) { 546 if (I->isSubRegion()) { 547 const RegionT *SR = I->template getNodeAs<RegionT>(); 548 verifyBBMap(SR); 549 } else { 550 BlockT *BB = I->template getNodeAs<BlockT>(); 551 if (getRegionFor(BB) != R) 552 llvm_unreachable("BB map does not match region nesting"); 553 } 554 } 555 } 556 557 template <class Tr> 558 bool RegionInfoBase<Tr>::isCommonDomFrontier(BlockT *BB, BlockT *entry, 559 BlockT *exit) const { 560 for (PredIterTy PI = InvBlockTraits::child_begin(BB), 561 PE = InvBlockTraits::child_end(BB); 562 PI != PE; ++PI) { 563 BlockT *P = *PI; 564 if (DT->dominates(entry, P) && !DT->dominates(exit, P)) 565 return false; 566 } 567 568 return true; 569 } 570 571 template <class Tr> 572 bool RegionInfoBase<Tr>::isRegion(BlockT *entry, BlockT *exit) const { 573 assert(entry && exit && "entry and exit must not be null!"); 574 typedef typename DomFrontierT::DomSetType DST; 575 576 DST *entrySuccs = &DF->find(entry)->second; 577 578 // Exit is the header of a loop that contains the entry. In this case, 579 // the dominance frontier must only contain the exit. 580 if (!DT->dominates(entry, exit)) { 581 for (typename DST::iterator SI = entrySuccs->begin(), 582 SE = entrySuccs->end(); 583 SI != SE; ++SI) { 584 if (*SI != exit && *SI != entry) 585 return false; 586 } 587 588 return true; 589 } 590 591 DST *exitSuccs = &DF->find(exit)->second; 592 593 // Do not allow edges leaving the region. 594 for (typename DST::iterator SI = entrySuccs->begin(), SE = entrySuccs->end(); 595 SI != SE; ++SI) { 596 if (*SI == exit || *SI == entry) 597 continue; 598 if (exitSuccs->find(*SI) == exitSuccs->end()) 599 return false; 600 if (!isCommonDomFrontier(*SI, entry, exit)) 601 return false; 602 } 603 604 // Do not allow edges pointing into the region. 605 for (typename DST::iterator SI = exitSuccs->begin(), SE = exitSuccs->end(); 606 SI != SE; ++SI) { 607 if (DT->properlyDominates(entry, *SI) && *SI != exit) 608 return false; 609 } 610 611 return true; 612 } 613 614 template <class Tr> 615 void RegionInfoBase<Tr>::insertShortCut(BlockT *entry, BlockT *exit, 616 BBtoBBMap *ShortCut) const { 617 assert(entry && exit && "entry and exit must not be null!"); 618 619 typename BBtoBBMap::iterator e = ShortCut->find(exit); 620 621 if (e == ShortCut->end()) 622 // No further region at exit available. 623 (*ShortCut)[entry] = exit; 624 else { 625 // We found a region e that starts at exit. Therefore (entry, e->second) 626 // is also a region, that is larger than (entry, exit). Insert the 627 // larger one. 628 BlockT *BB = e->second; 629 (*ShortCut)[entry] = BB; 630 } 631 } 632 633 template <class Tr> 634 typename Tr::DomTreeNodeT * 635 RegionInfoBase<Tr>::getNextPostDom(DomTreeNodeT *N, BBtoBBMap *ShortCut) const { 636 typename BBtoBBMap::iterator e = ShortCut->find(N->getBlock()); 637 638 if (e == ShortCut->end()) 639 return N->getIDom(); 640 641 return PDT->getNode(e->second)->getIDom(); 642 } 643 644 template <class Tr> 645 bool RegionInfoBase<Tr>::isTrivialRegion(BlockT *entry, BlockT *exit) const { 646 assert(entry && exit && "entry and exit must not be null!"); 647 648 unsigned num_successors = 649 BlockTraits::child_end(entry) - BlockTraits::child_begin(entry); 650 651 if (num_successors <= 1 && exit == *(BlockTraits::child_begin(entry))) 652 return true; 653 654 return false; 655 } 656 657 template <class Tr> 658 typename Tr::RegionT *RegionInfoBase<Tr>::createRegion(BlockT *entry, 659 BlockT *exit) { 660 assert(entry && exit && "entry and exit must not be null!"); 661 662 if (isTrivialRegion(entry, exit)) 663 return nullptr; 664 665 RegionT *region = 666 new RegionT(entry, exit, static_cast<RegionInfoT *>(this), DT); 667 BBtoRegion.insert(std::make_pair(entry, region)); 668 669 #ifdef XDEBUG 670 region->verifyRegion(); 671 #else 672 DEBUG(region->verifyRegion()); 673 #endif 674 675 updateStatistics(region); 676 return region; 677 } 678 679 template <class Tr> 680 void RegionInfoBase<Tr>::findRegionsWithEntry(BlockT *entry, 681 BBtoBBMap *ShortCut) { 682 assert(entry); 683 684 DomTreeNodeT *N = PDT->getNode(entry); 685 if (!N) 686 return; 687 688 RegionT *lastRegion = nullptr; 689 BlockT *lastExit = entry; 690 691 // As only a BasicBlock that postdominates entry can finish a region, walk the 692 // post dominance tree upwards. 693 while ((N = getNextPostDom(N, ShortCut))) { 694 BlockT *exit = N->getBlock(); 695 696 if (!exit) 697 break; 698 699 if (isRegion(entry, exit)) { 700 RegionT *newRegion = createRegion(entry, exit); 701 702 if (lastRegion) 703 newRegion->addSubRegion(lastRegion); 704 705 lastRegion = newRegion; 706 lastExit = exit; 707 } 708 709 // This can never be a region, so stop the search. 710 if (!DT->dominates(entry, exit)) 711 break; 712 } 713 714 // Tried to create regions from entry to lastExit. Next time take a 715 // shortcut from entry to lastExit. 716 if (lastExit != entry) 717 insertShortCut(entry, lastExit, ShortCut); 718 } 719 720 template <class Tr> 721 void RegionInfoBase<Tr>::scanForRegions(FuncT &F, BBtoBBMap *ShortCut) { 722 typedef typename std::add_pointer<FuncT>::type FuncPtrT; 723 BlockT *entry = GraphTraits<FuncPtrT>::getEntryNode(&F); 724 DomTreeNodeT *N = DT->getNode(entry); 725 726 // Iterate over the dominance tree in post order to start with the small 727 // regions from the bottom of the dominance tree. If the small regions are 728 // detected first, detection of bigger regions is faster, as we can jump 729 // over the small regions. 730 for (auto DomNode : post_order(N)) 731 findRegionsWithEntry(DomNode->getBlock(), ShortCut); 732 } 733 734 template <class Tr> 735 typename Tr::RegionT *RegionInfoBase<Tr>::getTopMostParent(RegionT *region) { 736 while (region->getParent()) 737 region = region->getParent(); 738 739 return region; 740 } 741 742 template <class Tr> 743 void RegionInfoBase<Tr>::buildRegionsTree(DomTreeNodeT *N, RegionT *region) { 744 BlockT *BB = N->getBlock(); 745 746 // Passed region exit 747 while (BB == region->getExit()) 748 region = region->getParent(); 749 750 typename BBtoRegionMap::iterator it = BBtoRegion.find(BB); 751 752 // This basic block is a start block of a region. It is already in the 753 // BBtoRegion relation. Only the child basic blocks have to be updated. 754 if (it != BBtoRegion.end()) { 755 RegionT *newRegion = it->second; 756 region->addSubRegion(getTopMostParent(newRegion)); 757 region = newRegion; 758 } else { 759 BBtoRegion[BB] = region; 760 } 761 762 for (typename DomTreeNodeT::iterator CI = N->begin(), CE = N->end(); CI != CE; 763 ++CI) { 764 buildRegionsTree(*CI, region); 765 } 766 } 767 768 #ifdef XDEBUG 769 template <class Tr> 770 bool RegionInfoBase<Tr>::VerifyRegionInfo = true; 771 #else 772 template <class Tr> 773 bool RegionInfoBase<Tr>::VerifyRegionInfo = false; 774 #endif 775 776 template <class Tr> 777 typename Tr::RegionT::PrintStyle RegionInfoBase<Tr>::printStyle = 778 RegionBase<Tr>::PrintNone; 779 780 template <class Tr> 781 void RegionInfoBase<Tr>::print(raw_ostream &OS) const { 782 OS << "Region tree:\n"; 783 TopLevelRegion->print(OS, true, 0, printStyle); 784 OS << "End region tree\n"; 785 } 786 787 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 788 template <class Tr> 789 void RegionInfoBase<Tr>::dump() const { print(dbgs()); } 790 #endif 791 792 template <class Tr> 793 void RegionInfoBase<Tr>::releaseMemory() { 794 BBtoRegion.clear(); 795 if (TopLevelRegion) 796 delete TopLevelRegion; 797 TopLevelRegion = nullptr; 798 } 799 800 template <class Tr> 801 void RegionInfoBase<Tr>::verifyAnalysis() const { 802 // Do only verify regions if explicitely activated using XDEBUG or 803 // -verify-region-info 804 if (!RegionInfoBase<Tr>::VerifyRegionInfo) 805 return; 806 807 TopLevelRegion->verifyRegionNest(); 808 809 verifyBBMap(TopLevelRegion); 810 } 811 812 // Region pass manager support. 813 template <class Tr> 814 typename Tr::RegionT *RegionInfoBase<Tr>::getRegionFor(BlockT *BB) const { 815 typename BBtoRegionMap::const_iterator I = BBtoRegion.find(BB); 816 return I != BBtoRegion.end() ? I->second : nullptr; 817 } 818 819 template <class Tr> 820 void RegionInfoBase<Tr>::setRegionFor(BlockT *BB, RegionT *R) { 821 BBtoRegion[BB] = R; 822 } 823 824 template <class Tr> 825 typename Tr::RegionT *RegionInfoBase<Tr>::operator[](BlockT *BB) const { 826 return getRegionFor(BB); 827 } 828 829 template <class Tr> 830 typename RegionInfoBase<Tr>::BlockT * 831 RegionInfoBase<Tr>::getMaxRegionExit(BlockT *BB) const { 832 BlockT *Exit = nullptr; 833 834 while (true) { 835 // Get largest region that starts at BB. 836 RegionT *R = getRegionFor(BB); 837 while (R && R->getParent() && R->getParent()->getEntry() == BB) 838 R = R->getParent(); 839 840 // Get the single exit of BB. 841 if (R && R->getEntry() == BB) 842 Exit = R->getExit(); 843 else if (++BlockTraits::child_begin(BB) == BlockTraits::child_end(BB)) 844 Exit = *BlockTraits::child_begin(BB); 845 else // No single exit exists. 846 return Exit; 847 848 // Get largest region that starts at Exit. 849 RegionT *ExitR = getRegionFor(Exit); 850 while (ExitR && ExitR->getParent() && 851 ExitR->getParent()->getEntry() == Exit) 852 ExitR = ExitR->getParent(); 853 854 for (PredIterTy PI = InvBlockTraits::child_begin(Exit), 855 PE = InvBlockTraits::child_end(Exit); 856 PI != PE; ++PI) { 857 if (!R->contains(*PI) && !ExitR->contains(*PI)) 858 break; 859 } 860 861 // This stops infinite cycles. 862 if (DT->dominates(Exit, BB)) 863 break; 864 865 BB = Exit; 866 } 867 868 return Exit; 869 } 870 871 template <class Tr> 872 typename Tr::RegionT *RegionInfoBase<Tr>::getCommonRegion(RegionT *A, 873 RegionT *B) const { 874 assert(A && B && "One of the Regions is NULL"); 875 876 if (A->contains(B)) 877 return A; 878 879 while (!B->contains(A)) 880 B = B->getParent(); 881 882 return B; 883 } 884 885 template <class Tr> 886 typename Tr::RegionT * 887 RegionInfoBase<Tr>::getCommonRegion(SmallVectorImpl<RegionT *> &Regions) const { 888 RegionT *ret = Regions.back(); 889 Regions.pop_back(); 890 891 for (RegionT *R : Regions) 892 ret = getCommonRegion(ret, R); 893 894 return ret; 895 } 896 897 template <class Tr> 898 typename Tr::RegionT * 899 RegionInfoBase<Tr>::getCommonRegion(SmallVectorImpl<BlockT *> &BBs) const { 900 RegionT *ret = getRegionFor(BBs.back()); 901 BBs.pop_back(); 902 903 for (BlockT *BB : BBs) 904 ret = getCommonRegion(ret, getRegionFor(BB)); 905 906 return ret; 907 } 908 909 template <class Tr> 910 void RegionInfoBase<Tr>::calculate(FuncT &F) { 911 typedef typename std::add_pointer<FuncT>::type FuncPtrT; 912 913 // ShortCut a function where for every BB the exit of the largest region 914 // starting with BB is stored. These regions can be threated as single BBS. 915 // This improves performance on linear CFGs. 916 BBtoBBMap ShortCut; 917 918 scanForRegions(F, &ShortCut); 919 BlockT *BB = GraphTraits<FuncPtrT>::getEntryNode(&F); 920 buildRegionsTree(DT->getNode(BB), TopLevelRegion); 921 } 922 923 #undef DEBUG_TYPE 924 925 } // end namespace llvm 926 927 #endif 928