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