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