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