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