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