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