1212793Sdim//===- RegionInfo.cpp - SESE region detection analysis --------------------===// 2212793Sdim// 3212793Sdim// The LLVM Compiler Infrastructure 4212793Sdim// 5212793Sdim// This file is distributed under the University of Illinois Open Source 6212793Sdim// License. See LICENSE.TXT for details. 7212793Sdim// 8212793Sdim//===----------------------------------------------------------------------===// 9212793Sdim// Detects single entry single exit regions in the control flow graph. 10212793Sdim//===----------------------------------------------------------------------===// 11212793Sdim 12263509Sdim#define DEBUG_TYPE "region" 13212793Sdim#include "llvm/Analysis/RegionInfo.h" 14212793Sdim#include "llvm/ADT/PostOrderIterator.h" 15212793Sdim#include "llvm/ADT/Statistic.h" 16252723Sdim#include "llvm/Analysis/LoopInfo.h" 17252723Sdim#include "llvm/Analysis/RegionIterator.h" 18252723Sdim#include "llvm/Assembly/Writer.h" 19212793Sdim#include "llvm/Support/CommandLine.h" 20212793Sdim#include "llvm/Support/ErrorHandling.h" 21212793Sdim#include "llvm/Support/Debug.h" 22263509Sdim#include <algorithm> 23212793Sdim#include <set> 24212793Sdim 25212793Sdimusing namespace llvm; 26212793Sdim 27212793Sdim// Always verify if expensive checking is enabled. 28212793Sdim#ifdef XDEBUG 29212793Sdimstatic bool VerifyRegionInfo = true; 30212793Sdim#else 31212793Sdimstatic bool VerifyRegionInfo = false; 32212793Sdim#endif 33212793Sdim 34212793Sdimstatic cl::opt<bool,true> 35212793SdimVerifyRegionInfoX("verify-region-info", cl::location(VerifyRegionInfo), 36212793Sdim cl::desc("Verify region info (time consuming)")); 37212793Sdim 38212793SdimSTATISTIC(numRegions, "The # of regions"); 39212793SdimSTATISTIC(numSimpleRegions, "The # of simple regions"); 40212793Sdim 41221345Sdimstatic cl::opt<enum Region::PrintStyle> printStyle("print-region-style", 42221345Sdim cl::Hidden, 43212793Sdim cl::desc("style of printing regions"), 44212793Sdim cl::values( 45221345Sdim clEnumValN(Region::PrintNone, "none", "print no details"), 46221345Sdim clEnumValN(Region::PrintBB, "bb", 47221345Sdim "print regions in detail with block_iterator"), 48221345Sdim clEnumValN(Region::PrintRN, "rn", 49221345Sdim "print regions in detail with element_iterator"), 50212793Sdim clEnumValEnd)); 51212793Sdim//===----------------------------------------------------------------------===// 52212793Sdim/// Region Implementation 53212793SdimRegion::Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo* RInfo, 54212793Sdim DominatorTree *dt, Region *Parent) 55212793Sdim : RegionNode(Parent, Entry, 1), RI(RInfo), DT(dt), exit(Exit) {} 56212793Sdim 57212793SdimRegion::~Region() { 58212793Sdim // Free the cached nodes. 59212793Sdim for (BBNodeMapT::iterator it = BBNodeMap.begin(), 60212793Sdim ie = BBNodeMap.end(); it != ie; ++it) 61212793Sdim delete it->second; 62212793Sdim 63212793Sdim // Only clean the cache for this Region. Caches of child Regions will be 64212793Sdim // cleaned when the child Regions are deleted. 65212793Sdim BBNodeMap.clear(); 66212793Sdim 67212793Sdim for (iterator I = begin(), E = end(); I != E; ++I) 68212793Sdim delete *I; 69212793Sdim} 70212793Sdim 71218893Sdimvoid Region::replaceEntry(BasicBlock *BB) { 72218893Sdim entry.setPointer(BB); 73218893Sdim} 74218893Sdim 75218893Sdimvoid Region::replaceExit(BasicBlock *BB) { 76218893Sdim assert(exit && "No exit to replace!"); 77218893Sdim exit = BB; 78218893Sdim} 79218893Sdim 80252723Sdimvoid Region::replaceEntryRecursive(BasicBlock *NewEntry) { 81252723Sdim std::vector<Region *> RegionQueue; 82252723Sdim BasicBlock *OldEntry = getEntry(); 83252723Sdim 84252723Sdim RegionQueue.push_back(this); 85252723Sdim while (!RegionQueue.empty()) { 86252723Sdim Region *R = RegionQueue.back(); 87252723Sdim RegionQueue.pop_back(); 88252723Sdim 89252723Sdim R->replaceEntry(NewEntry); 90252723Sdim for (Region::const_iterator RI = R->begin(), RE = R->end(); RI != RE; ++RI) 91252723Sdim if ((*RI)->getEntry() == OldEntry) 92252723Sdim RegionQueue.push_back(*RI); 93252723Sdim } 94252723Sdim} 95252723Sdim 96252723Sdimvoid Region::replaceExitRecursive(BasicBlock *NewExit) { 97252723Sdim std::vector<Region *> RegionQueue; 98252723Sdim BasicBlock *OldExit = getExit(); 99252723Sdim 100252723Sdim RegionQueue.push_back(this); 101252723Sdim while (!RegionQueue.empty()) { 102252723Sdim Region *R = RegionQueue.back(); 103252723Sdim RegionQueue.pop_back(); 104252723Sdim 105252723Sdim R->replaceExit(NewExit); 106252723Sdim for (Region::const_iterator RI = R->begin(), RE = R->end(); RI != RE; ++RI) 107252723Sdim if ((*RI)->getExit() == OldExit) 108252723Sdim RegionQueue.push_back(*RI); 109252723Sdim } 110252723Sdim} 111252723Sdim 112212793Sdimbool Region::contains(const BasicBlock *B) const { 113212793Sdim BasicBlock *BB = const_cast<BasicBlock*>(B); 114212793Sdim 115252723Sdim if (!DT->getNode(BB)) 116252723Sdim return false; 117212793Sdim 118212793Sdim BasicBlock *entry = getEntry(), *exit = getExit(); 119212793Sdim 120212793Sdim // Toplevel region. 121212793Sdim if (!exit) 122212793Sdim return true; 123212793Sdim 124212793Sdim return (DT->dominates(entry, BB) 125212793Sdim && !(DT->dominates(exit, BB) && DT->dominates(entry, exit))); 126212793Sdim} 127212793Sdim 128212793Sdimbool Region::contains(const Loop *L) const { 129212793Sdim // BBs that are not part of any loop are element of the Loop 130212793Sdim // described by the NULL pointer. This loop is not part of any region, 131212793Sdim // except if the region describes the whole function. 132212793Sdim if (L == 0) 133212793Sdim return getExit() == 0; 134212793Sdim 135212793Sdim if (!contains(L->getHeader())) 136212793Sdim return false; 137212793Sdim 138212793Sdim SmallVector<BasicBlock *, 8> ExitingBlocks; 139212793Sdim L->getExitingBlocks(ExitingBlocks); 140212793Sdim 141212793Sdim for (SmallVectorImpl<BasicBlock*>::iterator BI = ExitingBlocks.begin(), 142212793Sdim BE = ExitingBlocks.end(); BI != BE; ++BI) 143212793Sdim if (!contains(*BI)) 144212793Sdim return false; 145212793Sdim 146212793Sdim return true; 147212793Sdim} 148212793Sdim 149212793SdimLoop *Region::outermostLoopInRegion(Loop *L) const { 150212793Sdim if (!contains(L)) 151212793Sdim return 0; 152212793Sdim 153212793Sdim while (L && contains(L->getParentLoop())) { 154212793Sdim L = L->getParentLoop(); 155212793Sdim } 156212793Sdim 157212793Sdim return L; 158212793Sdim} 159212793Sdim 160212793SdimLoop *Region::outermostLoopInRegion(LoopInfo *LI, BasicBlock* BB) const { 161212793Sdim assert(LI && BB && "LI and BB cannot be null!"); 162212793Sdim Loop *L = LI->getLoopFor(BB); 163212793Sdim return outermostLoopInRegion(L); 164212793Sdim} 165212793Sdim 166218893SdimBasicBlock *Region::getEnteringBlock() const { 167218893Sdim BasicBlock *entry = getEntry(); 168218893Sdim BasicBlock *Pred; 169218893Sdim BasicBlock *enteringBlock = 0; 170212793Sdim 171212793Sdim for (pred_iterator PI = pred_begin(entry), PE = pred_end(entry); PI != PE; 172212793Sdim ++PI) { 173218893Sdim Pred = *PI; 174212793Sdim if (DT->getNode(Pred) && !contains(Pred)) { 175218893Sdim if (enteringBlock) 176218893Sdim return 0; 177218893Sdim 178218893Sdim enteringBlock = Pred; 179212793Sdim } 180212793Sdim } 181212793Sdim 182218893Sdim return enteringBlock; 183218893Sdim} 184212793Sdim 185218893SdimBasicBlock *Region::getExitingBlock() const { 186218893Sdim BasicBlock *exit = getExit(); 187218893Sdim BasicBlock *Pred; 188218893Sdim BasicBlock *exitingBlock = 0; 189218893Sdim 190218893Sdim if (!exit) 191218893Sdim return 0; 192218893Sdim 193212793Sdim for (pred_iterator PI = pred_begin(exit), PE = pred_end(exit); PI != PE; 194218893Sdim ++PI) { 195218893Sdim Pred = *PI; 196218893Sdim if (contains(Pred)) { 197218893Sdim if (exitingBlock) 198218893Sdim return 0; 199218893Sdim 200218893Sdim exitingBlock = Pred; 201212793Sdim } 202218893Sdim } 203212793Sdim 204218893Sdim return exitingBlock; 205212793Sdim} 206212793Sdim 207218893Sdimbool Region::isSimple() const { 208218893Sdim return !isTopLevelRegion() && getEnteringBlock() && getExitingBlock(); 209218893Sdim} 210218893Sdim 211212793Sdimstd::string Region::getNameStr() const { 212212793Sdim std::string exitName; 213212793Sdim std::string entryName; 214212793Sdim 215212793Sdim if (getEntry()->getName().empty()) { 216212793Sdim raw_string_ostream OS(entryName); 217212793Sdim 218212793Sdim WriteAsOperand(OS, getEntry(), false); 219212793Sdim } else 220235633Sdim entryName = getEntry()->getName(); 221212793Sdim 222212793Sdim if (getExit()) { 223212793Sdim if (getExit()->getName().empty()) { 224212793Sdim raw_string_ostream OS(exitName); 225212793Sdim 226212793Sdim WriteAsOperand(OS, getExit(), false); 227212793Sdim } else 228235633Sdim exitName = getExit()->getName(); 229212793Sdim } else 230212793Sdim exitName = "<Function Return>"; 231212793Sdim 232212793Sdim return entryName + " => " + exitName; 233212793Sdim} 234212793Sdim 235212793Sdimvoid Region::verifyBBInRegion(BasicBlock *BB) const { 236212793Sdim if (!contains(BB)) 237212793Sdim llvm_unreachable("Broken region found!"); 238212793Sdim 239212793Sdim BasicBlock *entry = getEntry(), *exit = getExit(); 240212793Sdim 241212793Sdim for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 242212793Sdim if (!contains(*SI) && exit != *SI) 243212793Sdim llvm_unreachable("Broken region found!"); 244212793Sdim 245212793Sdim if (entry != BB) 246212793Sdim for (pred_iterator SI = pred_begin(BB), SE = pred_end(BB); SI != SE; ++SI) 247212793Sdim if (!contains(*SI)) 248212793Sdim llvm_unreachable("Broken region found!"); 249212793Sdim} 250212793Sdim 251212793Sdimvoid Region::verifyWalk(BasicBlock *BB, std::set<BasicBlock*> *visited) const { 252212793Sdim BasicBlock *exit = getExit(); 253212793Sdim 254212793Sdim visited->insert(BB); 255212793Sdim 256212793Sdim verifyBBInRegion(BB); 257212793Sdim 258212793Sdim for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 259212793Sdim if (*SI != exit && visited->find(*SI) == visited->end()) 260212793Sdim verifyWalk(*SI, visited); 261212793Sdim} 262212793Sdim 263212793Sdimvoid Region::verifyRegion() const { 264212793Sdim // Only do verification when user wants to, otherwise this expensive 265212793Sdim // check will be invoked by PassManager. 266212793Sdim if (!VerifyRegionInfo) return; 267212793Sdim 268212793Sdim std::set<BasicBlock*> visited; 269212793Sdim verifyWalk(getEntry(), &visited); 270212793Sdim} 271212793Sdim 272212793Sdimvoid Region::verifyRegionNest() const { 273212793Sdim for (Region::const_iterator RI = begin(), RE = end(); RI != RE; ++RI) 274212793Sdim (*RI)->verifyRegionNest(); 275212793Sdim 276212793Sdim verifyRegion(); 277212793Sdim} 278212793Sdim 279212793SdimRegion::element_iterator Region::element_begin() { 280212793Sdim return GraphTraits<Region*>::nodes_begin(this); 281212793Sdim} 282212793Sdim 283212793SdimRegion::element_iterator Region::element_end() { 284212793Sdim return GraphTraits<Region*>::nodes_end(this); 285212793Sdim} 286212793Sdim 287212793SdimRegion::const_element_iterator Region::element_begin() const { 288212793Sdim return GraphTraits<const Region*>::nodes_begin(this); 289212793Sdim} 290212793Sdim 291212793SdimRegion::const_element_iterator Region::element_end() const { 292212793Sdim return GraphTraits<const Region*>::nodes_end(this); 293212793Sdim} 294212793Sdim 295212793SdimRegion* Region::getSubRegionNode(BasicBlock *BB) const { 296212793Sdim Region *R = RI->getRegionFor(BB); 297212793Sdim 298212793Sdim if (!R || R == this) 299212793Sdim return 0; 300212793Sdim 301212793Sdim // If we pass the BB out of this region, that means our code is broken. 302212793Sdim assert(contains(R) && "BB not in current region!"); 303212793Sdim 304212793Sdim while (contains(R->getParent()) && R->getParent() != this) 305212793Sdim R = R->getParent(); 306212793Sdim 307212793Sdim if (R->getEntry() != BB) 308212793Sdim return 0; 309212793Sdim 310212793Sdim return R; 311212793Sdim} 312212793Sdim 313212793SdimRegionNode* Region::getBBNode(BasicBlock *BB) const { 314212793Sdim assert(contains(BB) && "Can get BB node out of this region!"); 315212793Sdim 316212793Sdim BBNodeMapT::const_iterator at = BBNodeMap.find(BB); 317212793Sdim 318212793Sdim if (at != BBNodeMap.end()) 319212793Sdim return at->second; 320212793Sdim 321212793Sdim RegionNode *NewNode = new RegionNode(const_cast<Region*>(this), BB); 322212793Sdim BBNodeMap.insert(std::make_pair(BB, NewNode)); 323212793Sdim return NewNode; 324212793Sdim} 325212793Sdim 326212793SdimRegionNode* Region::getNode(BasicBlock *BB) const { 327212793Sdim assert(contains(BB) && "Can get BB node out of this region!"); 328212793Sdim if (Region* Child = getSubRegionNode(BB)) 329212793Sdim return Child->getNode(); 330212793Sdim 331212793Sdim return getBBNode(BB); 332212793Sdim} 333212793Sdim 334212793Sdimvoid Region::transferChildrenTo(Region *To) { 335212793Sdim for (iterator I = begin(), E = end(); I != E; ++I) { 336212793Sdim (*I)->parent = To; 337212793Sdim To->children.push_back(*I); 338212793Sdim } 339212793Sdim children.clear(); 340212793Sdim} 341212793Sdim 342218893Sdimvoid Region::addSubRegion(Region *SubRegion, bool moveChildren) { 343212793Sdim assert(SubRegion->parent == 0 && "SubRegion already has a parent!"); 344218893Sdim assert(std::find(begin(), end(), SubRegion) == children.end() 345218893Sdim && "Subregion already exists!"); 346218893Sdim 347212793Sdim SubRegion->parent = this; 348212793Sdim children.push_back(SubRegion); 349218893Sdim 350218893Sdim if (!moveChildren) 351218893Sdim return; 352218893Sdim 353218893Sdim assert(SubRegion->children.size() == 0 354218893Sdim && "SubRegions that contain children are not supported"); 355218893Sdim 356218893Sdim for (element_iterator I = element_begin(), E = element_end(); I != E; ++I) 357218893Sdim if (!(*I)->isSubRegion()) { 358218893Sdim BasicBlock *BB = (*I)->getNodeAs<BasicBlock>(); 359218893Sdim 360218893Sdim if (SubRegion->contains(BB)) 361218893Sdim RI->setRegionFor(BB, SubRegion); 362218893Sdim } 363218893Sdim 364218893Sdim std::vector<Region*> Keep; 365218893Sdim for (iterator I = begin(), E = end(); I != E; ++I) 366218893Sdim if (SubRegion->contains(*I) && *I != SubRegion) { 367218893Sdim SubRegion->children.push_back(*I); 368218893Sdim (*I)->parent = SubRegion; 369218893Sdim } else 370218893Sdim Keep.push_back(*I); 371218893Sdim 372218893Sdim children.clear(); 373218893Sdim children.insert(children.begin(), Keep.begin(), Keep.end()); 374212793Sdim} 375212793Sdim 376212793Sdim 377212793SdimRegion *Region::removeSubRegion(Region *Child) { 378212793Sdim assert(Child->parent == this && "Child is not a child of this region!"); 379212793Sdim Child->parent = 0; 380212793Sdim RegionSet::iterator I = std::find(children.begin(), children.end(), Child); 381212793Sdim assert(I != children.end() && "Region does not exit. Unable to remove."); 382212793Sdim children.erase(children.begin()+(I-begin())); 383212793Sdim return Child; 384212793Sdim} 385212793Sdim 386212793Sdimunsigned Region::getDepth() const { 387212793Sdim unsigned Depth = 0; 388212793Sdim 389212793Sdim for (Region *R = parent; R != 0; R = R->parent) 390212793Sdim ++Depth; 391212793Sdim 392212793Sdim return Depth; 393212793Sdim} 394212793Sdim 395218893SdimRegion *Region::getExpandedRegion() const { 396218893Sdim unsigned NumSuccessors = exit->getTerminator()->getNumSuccessors(); 397218893Sdim 398218893Sdim if (NumSuccessors == 0) 399218893Sdim return NULL; 400218893Sdim 401218893Sdim for (pred_iterator PI = pred_begin(getExit()), PE = pred_end(getExit()); 402218893Sdim PI != PE; ++PI) 403218893Sdim if (!DT->dominates(getEntry(), *PI)) 404218893Sdim return NULL; 405218893Sdim 406218893Sdim Region *R = RI->getRegionFor(exit); 407218893Sdim 408218893Sdim if (R->getEntry() != exit) { 409218893Sdim if (exit->getTerminator()->getNumSuccessors() == 1) 410218893Sdim return new Region(getEntry(), *succ_begin(exit), RI, DT); 411218893Sdim else 412218893Sdim return NULL; 413218893Sdim } 414218893Sdim 415218893Sdim while (R->getParent() && R->getParent()->getEntry() == exit) 416218893Sdim R = R->getParent(); 417218893Sdim 418218893Sdim if (!DT->dominates(getEntry(), R->getExit())) 419218893Sdim for (pred_iterator PI = pred_begin(getExit()), PE = pred_end(getExit()); 420218893Sdim PI != PE; ++PI) 421218893Sdim if (!DT->dominates(R->getExit(), *PI)) 422218893Sdim return NULL; 423218893Sdim 424218893Sdim return new Region(getEntry(), R->getExit(), RI, DT); 425218893Sdim} 426218893Sdim 427221345Sdimvoid Region::print(raw_ostream &OS, bool print_tree, unsigned level, 428221345Sdim enum PrintStyle Style) const { 429212793Sdim if (print_tree) 430212793Sdim OS.indent(level*2) << "[" << level << "] " << getNameStr(); 431212793Sdim else 432212793Sdim OS.indent(level*2) << getNameStr(); 433212793Sdim 434212793Sdim OS << "\n"; 435212793Sdim 436212793Sdim 437221345Sdim if (Style != PrintNone) { 438212793Sdim OS.indent(level*2) << "{\n"; 439212793Sdim OS.indent(level*2 + 2); 440212793Sdim 441221345Sdim if (Style == PrintBB) { 442245431Sdim for (const_block_iterator I = block_begin(), E = block_end(); I != E; ++I) 443245431Sdim OS << (*I)->getName() << ", "; // TODO: remove the last "," 444221345Sdim } else if (Style == PrintRN) { 445212793Sdim for (const_element_iterator I = element_begin(), E = element_end(); I!=E; ++I) 446212793Sdim OS << **I << ", "; // TODO: remove the last ", 447212793Sdim } 448212793Sdim 449212793Sdim OS << "\n"; 450212793Sdim } 451212793Sdim 452212793Sdim if (print_tree) 453212793Sdim for (const_iterator RI = begin(), RE = end(); RI != RE; ++RI) 454221345Sdim (*RI)->print(OS, print_tree, level+1, Style); 455212793Sdim 456221345Sdim if (Style != PrintNone) 457212793Sdim OS.indent(level*2) << "} \n"; 458212793Sdim} 459212793Sdim 460245431Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 461212793Sdimvoid Region::dump() const { 462221345Sdim print(dbgs(), true, getDepth(), printStyle.getValue()); 463212793Sdim} 464245431Sdim#endif 465212793Sdim 466212793Sdimvoid Region::clearNodeCache() { 467218893Sdim // Free the cached nodes. 468218893Sdim for (BBNodeMapT::iterator I = BBNodeMap.begin(), 469218893Sdim IE = BBNodeMap.end(); I != IE; ++I) 470218893Sdim delete I->second; 471218893Sdim 472212793Sdim BBNodeMap.clear(); 473212793Sdim for (Region::iterator RI = begin(), RE = end(); RI != RE; ++RI) 474212793Sdim (*RI)->clearNodeCache(); 475212793Sdim} 476212793Sdim 477212793Sdim//===----------------------------------------------------------------------===// 478212793Sdim// RegionInfo implementation 479212793Sdim// 480212793Sdim 481212793Sdimbool RegionInfo::isCommonDomFrontier(BasicBlock *BB, BasicBlock *entry, 482212793Sdim BasicBlock *exit) const { 483212793Sdim for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) { 484212793Sdim BasicBlock *P = *PI; 485212793Sdim if (DT->dominates(entry, P) && !DT->dominates(exit, P)) 486212793Sdim return false; 487212793Sdim } 488212793Sdim return true; 489212793Sdim} 490212793Sdim 491212793Sdimbool RegionInfo::isRegion(BasicBlock *entry, BasicBlock *exit) const { 492212793Sdim assert(entry && exit && "entry and exit must not be null!"); 493212793Sdim typedef DominanceFrontier::DomSetType DST; 494212793Sdim 495212793Sdim DST *entrySuccs = &DF->find(entry)->second; 496212793Sdim 497212793Sdim // Exit is the header of a loop that contains the entry. In this case, 498212793Sdim // the dominance frontier must only contain the exit. 499212793Sdim if (!DT->dominates(entry, exit)) { 500212793Sdim for (DST::iterator SI = entrySuccs->begin(), SE = entrySuccs->end(); 501212793Sdim SI != SE; ++SI) 502212793Sdim if (*SI != exit && *SI != entry) 503212793Sdim return false; 504212793Sdim 505212793Sdim return true; 506212793Sdim } 507212793Sdim 508212793Sdim DST *exitSuccs = &DF->find(exit)->second; 509212793Sdim 510212793Sdim // Do not allow edges leaving the region. 511212793Sdim for (DST::iterator SI = entrySuccs->begin(), SE = entrySuccs->end(); 512212793Sdim SI != SE; ++SI) { 513212793Sdim if (*SI == exit || *SI == entry) 514212793Sdim continue; 515212793Sdim if (exitSuccs->find(*SI) == exitSuccs->end()) 516212793Sdim return false; 517212793Sdim if (!isCommonDomFrontier(*SI, entry, exit)) 518212793Sdim return false; 519212793Sdim } 520212793Sdim 521212793Sdim // Do not allow edges pointing into the region. 522212793Sdim for (DST::iterator SI = exitSuccs->begin(), SE = exitSuccs->end(); 523212793Sdim SI != SE; ++SI) 524212793Sdim if (DT->properlyDominates(entry, *SI) && *SI != exit) 525212793Sdim return false; 526212793Sdim 527212793Sdim 528212793Sdim return true; 529212793Sdim} 530212793Sdim 531212793Sdimvoid RegionInfo::insertShortCut(BasicBlock *entry, BasicBlock *exit, 532212793Sdim BBtoBBMap *ShortCut) const { 533212793Sdim assert(entry && exit && "entry and exit must not be null!"); 534212793Sdim 535212793Sdim BBtoBBMap::iterator e = ShortCut->find(exit); 536212793Sdim 537212793Sdim if (e == ShortCut->end()) 538212793Sdim // No further region at exit available. 539212793Sdim (*ShortCut)[entry] = exit; 540212793Sdim else { 541212793Sdim // We found a region e that starts at exit. Therefore (entry, e->second) 542212793Sdim // is also a region, that is larger than (entry, exit). Insert the 543212793Sdim // larger one. 544212793Sdim BasicBlock *BB = e->second; 545212793Sdim (*ShortCut)[entry] = BB; 546212793Sdim } 547212793Sdim} 548212793Sdim 549212793SdimDomTreeNode* RegionInfo::getNextPostDom(DomTreeNode* N, 550212793Sdim BBtoBBMap *ShortCut) const { 551212793Sdim BBtoBBMap::iterator e = ShortCut->find(N->getBlock()); 552212793Sdim 553212793Sdim if (e == ShortCut->end()) 554212793Sdim return N->getIDom(); 555212793Sdim 556212793Sdim return PDT->getNode(e->second)->getIDom(); 557212793Sdim} 558212793Sdim 559212793Sdimbool RegionInfo::isTrivialRegion(BasicBlock *entry, BasicBlock *exit) const { 560212793Sdim assert(entry && exit && "entry and exit must not be null!"); 561212793Sdim 562212793Sdim unsigned num_successors = succ_end(entry) - succ_begin(entry); 563212793Sdim 564212793Sdim if (num_successors <= 1 && exit == *(succ_begin(entry))) 565212793Sdim return true; 566212793Sdim 567212793Sdim return false; 568212793Sdim} 569212793Sdim 570212793Sdimvoid RegionInfo::updateStatistics(Region *R) { 571212793Sdim ++numRegions; 572212793Sdim 573212793Sdim // TODO: Slow. Should only be enabled if -stats is used. 574212793Sdim if (R->isSimple()) ++numSimpleRegions; 575212793Sdim} 576212793Sdim 577212793SdimRegion *RegionInfo::createRegion(BasicBlock *entry, BasicBlock *exit) { 578212793Sdim assert(entry && exit && "entry and exit must not be null!"); 579212793Sdim 580212793Sdim if (isTrivialRegion(entry, exit)) 581212793Sdim return 0; 582212793Sdim 583212793Sdim Region *region = new Region(entry, exit, this, DT); 584212793Sdim BBtoRegion.insert(std::make_pair(entry, region)); 585212793Sdim 586212793Sdim #ifdef XDEBUG 587212793Sdim region->verifyRegion(); 588212793Sdim #else 589212793Sdim DEBUG(region->verifyRegion()); 590212793Sdim #endif 591212793Sdim 592212793Sdim updateStatistics(region); 593212793Sdim return region; 594212793Sdim} 595212793Sdim 596212793Sdimvoid RegionInfo::findRegionsWithEntry(BasicBlock *entry, BBtoBBMap *ShortCut) { 597212793Sdim assert(entry); 598212793Sdim 599212793Sdim DomTreeNode *N = PDT->getNode(entry); 600212793Sdim 601212793Sdim if (!N) 602212793Sdim return; 603212793Sdim 604212793Sdim Region *lastRegion= 0; 605212793Sdim BasicBlock *lastExit = entry; 606212793Sdim 607212793Sdim // As only a BasicBlock that postdominates entry can finish a region, walk the 608212793Sdim // post dominance tree upwards. 609212793Sdim while ((N = getNextPostDom(N, ShortCut))) { 610212793Sdim BasicBlock *exit = N->getBlock(); 611212793Sdim 612212793Sdim if (!exit) 613212793Sdim break; 614212793Sdim 615212793Sdim if (isRegion(entry, exit)) { 616212793Sdim Region *newRegion = createRegion(entry, exit); 617212793Sdim 618212793Sdim if (lastRegion) 619212793Sdim newRegion->addSubRegion(lastRegion); 620212793Sdim 621212793Sdim lastRegion = newRegion; 622212793Sdim lastExit = exit; 623212793Sdim } 624212793Sdim 625212793Sdim // This can never be a region, so stop the search. 626212793Sdim if (!DT->dominates(entry, exit)) 627212793Sdim break; 628212793Sdim } 629212793Sdim 630212793Sdim // Tried to create regions from entry to lastExit. Next time take a 631212793Sdim // shortcut from entry to lastExit. 632212793Sdim if (lastExit != entry) 633212793Sdim insertShortCut(entry, lastExit, ShortCut); 634212793Sdim} 635212793Sdim 636212793Sdimvoid RegionInfo::scanForRegions(Function &F, BBtoBBMap *ShortCut) { 637212793Sdim BasicBlock *entry = &(F.getEntryBlock()); 638212793Sdim DomTreeNode *N = DT->getNode(entry); 639212793Sdim 640212793Sdim // Iterate over the dominance tree in post order to start with the small 641212793Sdim // regions from the bottom of the dominance tree. If the small regions are 642212793Sdim // detected first, detection of bigger regions is faster, as we can jump 643212793Sdim // over the small regions. 644212793Sdim for (po_iterator<DomTreeNode*> FI = po_begin(N), FE = po_end(N); FI != FE; 645212793Sdim ++FI) { 646212793Sdim findRegionsWithEntry(FI->getBlock(), ShortCut); 647212793Sdim } 648212793Sdim} 649212793Sdim 650212793SdimRegion *RegionInfo::getTopMostParent(Region *region) { 651212793Sdim while (region->parent) 652212793Sdim region = region->getParent(); 653212793Sdim 654212793Sdim return region; 655212793Sdim} 656212793Sdim 657212793Sdimvoid RegionInfo::buildRegionsTree(DomTreeNode *N, Region *region) { 658212793Sdim BasicBlock *BB = N->getBlock(); 659212793Sdim 660212793Sdim // Passed region exit 661212793Sdim while (BB == region->getExit()) 662212793Sdim region = region->getParent(); 663212793Sdim 664212793Sdim BBtoRegionMap::iterator it = BBtoRegion.find(BB); 665212793Sdim 666212793Sdim // This basic block is a start block of a region. It is already in the 667212793Sdim // BBtoRegion relation. Only the child basic blocks have to be updated. 668212793Sdim if (it != BBtoRegion.end()) { 669235633Sdim Region *newRegion = it->second; 670212793Sdim region->addSubRegion(getTopMostParent(newRegion)); 671212793Sdim region = newRegion; 672212793Sdim } else { 673212793Sdim BBtoRegion[BB] = region; 674212793Sdim } 675212793Sdim 676212793Sdim for (DomTreeNode::iterator CI = N->begin(), CE = N->end(); CI != CE; ++CI) 677212793Sdim buildRegionsTree(*CI, region); 678212793Sdim} 679212793Sdim 680212793Sdimvoid RegionInfo::releaseMemory() { 681212793Sdim BBtoRegion.clear(); 682212793Sdim if (TopLevelRegion) 683212793Sdim delete TopLevelRegion; 684212793Sdim TopLevelRegion = 0; 685212793Sdim} 686212793Sdim 687212793SdimRegionInfo::RegionInfo() : FunctionPass(ID) { 688218893Sdim initializeRegionInfoPass(*PassRegistry::getPassRegistry()); 689212793Sdim TopLevelRegion = 0; 690212793Sdim} 691212793Sdim 692212793SdimRegionInfo::~RegionInfo() { 693212793Sdim releaseMemory(); 694212793Sdim} 695212793Sdim 696212793Sdimvoid RegionInfo::Calculate(Function &F) { 697212793Sdim // ShortCut a function where for every BB the exit of the largest region 698212793Sdim // starting with BB is stored. These regions can be threated as single BBS. 699212793Sdim // This improves performance on linear CFGs. 700212793Sdim BBtoBBMap ShortCut; 701212793Sdim 702212793Sdim scanForRegions(F, &ShortCut); 703212793Sdim BasicBlock *BB = &F.getEntryBlock(); 704212793Sdim buildRegionsTree(DT->getNode(BB), TopLevelRegion); 705212793Sdim} 706212793Sdim 707212793Sdimbool RegionInfo::runOnFunction(Function &F) { 708212793Sdim releaseMemory(); 709212793Sdim 710212793Sdim DT = &getAnalysis<DominatorTree>(); 711212793Sdim PDT = &getAnalysis<PostDominatorTree>(); 712212793Sdim DF = &getAnalysis<DominanceFrontier>(); 713212793Sdim 714212793Sdim TopLevelRegion = new Region(&F.getEntryBlock(), 0, this, DT, 0); 715212793Sdim updateStatistics(TopLevelRegion); 716212793Sdim 717212793Sdim Calculate(F); 718212793Sdim 719212793Sdim return false; 720212793Sdim} 721212793Sdim 722212793Sdimvoid RegionInfo::getAnalysisUsage(AnalysisUsage &AU) const { 723212793Sdim AU.setPreservesAll(); 724212793Sdim AU.addRequiredTransitive<DominatorTree>(); 725212793Sdim AU.addRequired<PostDominatorTree>(); 726212793Sdim AU.addRequired<DominanceFrontier>(); 727212793Sdim} 728212793Sdim 729212793Sdimvoid RegionInfo::print(raw_ostream &OS, const Module *) const { 730212793Sdim OS << "Region tree:\n"; 731221345Sdim TopLevelRegion->print(OS, true, 0, printStyle.getValue()); 732212793Sdim OS << "End region tree\n"; 733212793Sdim} 734212793Sdim 735212793Sdimvoid RegionInfo::verifyAnalysis() const { 736212793Sdim // Only do verification when user wants to, otherwise this expensive check 737212793Sdim // will be invoked by PMDataManager::verifyPreservedAnalysis when 738212793Sdim // a regionpass (marked PreservedAll) finish. 739212793Sdim if (!VerifyRegionInfo) return; 740212793Sdim 741212793Sdim TopLevelRegion->verifyRegionNest(); 742212793Sdim} 743212793Sdim 744212793Sdim// Region pass manager support. 745212793SdimRegion *RegionInfo::getRegionFor(BasicBlock *BB) const { 746212793Sdim BBtoRegionMap::const_iterator I= 747212793Sdim BBtoRegion.find(BB); 748212793Sdim return I != BBtoRegion.end() ? I->second : 0; 749212793Sdim} 750212793Sdim 751218893Sdimvoid RegionInfo::setRegionFor(BasicBlock *BB, Region *R) { 752218893Sdim BBtoRegion[BB] = R; 753218893Sdim} 754218893Sdim 755212793SdimRegion *RegionInfo::operator[](BasicBlock *BB) const { 756212793Sdim return getRegionFor(BB); 757212793Sdim} 758212793Sdim 759212793SdimBasicBlock *RegionInfo::getMaxRegionExit(BasicBlock *BB) const { 760212793Sdim BasicBlock *Exit = NULL; 761212793Sdim 762212793Sdim while (true) { 763212793Sdim // Get largest region that starts at BB. 764212793Sdim Region *R = getRegionFor(BB); 765212793Sdim while (R && R->getParent() && R->getParent()->getEntry() == BB) 766212793Sdim R = R->getParent(); 767212793Sdim 768212793Sdim // Get the single exit of BB. 769212793Sdim if (R && R->getEntry() == BB) 770212793Sdim Exit = R->getExit(); 771212793Sdim else if (++succ_begin(BB) == succ_end(BB)) 772212793Sdim Exit = *succ_begin(BB); 773212793Sdim else // No single exit exists. 774212793Sdim return Exit; 775212793Sdim 776212793Sdim // Get largest region that starts at Exit. 777212793Sdim Region *ExitR = getRegionFor(Exit); 778212793Sdim while (ExitR && ExitR->getParent() 779212793Sdim && ExitR->getParent()->getEntry() == Exit) 780212793Sdim ExitR = ExitR->getParent(); 781212793Sdim 782212793Sdim for (pred_iterator PI = pred_begin(Exit), PE = pred_end(Exit); PI != PE; 783212793Sdim ++PI) 784212793Sdim if (!R->contains(*PI) && !ExitR->contains(*PI)) 785212793Sdim break; 786212793Sdim 787212793Sdim // This stops infinite cycles. 788212793Sdim if (DT->dominates(Exit, BB)) 789212793Sdim break; 790212793Sdim 791212793Sdim BB = Exit; 792212793Sdim } 793212793Sdim 794212793Sdim return Exit; 795212793Sdim} 796212793Sdim 797212793SdimRegion* 798212793SdimRegionInfo::getCommonRegion(Region *A, Region *B) const { 799212793Sdim assert (A && B && "One of the Regions is NULL"); 800212793Sdim 801212793Sdim if (A->contains(B)) return A; 802212793Sdim 803212793Sdim while (!B->contains(A)) 804212793Sdim B = B->getParent(); 805212793Sdim 806212793Sdim return B; 807212793Sdim} 808212793Sdim 809212793SdimRegion* 810212793SdimRegionInfo::getCommonRegion(SmallVectorImpl<Region*> &Regions) const { 811212793Sdim Region* ret = Regions.back(); 812212793Sdim Regions.pop_back(); 813212793Sdim 814212793Sdim for (SmallVectorImpl<Region*>::const_iterator I = Regions.begin(), 815212793Sdim E = Regions.end(); I != E; ++I) 816212793Sdim ret = getCommonRegion(ret, *I); 817212793Sdim 818212793Sdim return ret; 819212793Sdim} 820212793Sdim 821212793SdimRegion* 822212793SdimRegionInfo::getCommonRegion(SmallVectorImpl<BasicBlock*> &BBs) const { 823212793Sdim Region* ret = getRegionFor(BBs.back()); 824212793Sdim BBs.pop_back(); 825212793Sdim 826212793Sdim for (SmallVectorImpl<BasicBlock*>::const_iterator I = BBs.begin(), 827212793Sdim E = BBs.end(); I != E; ++I) 828212793Sdim ret = getCommonRegion(ret, getRegionFor(*I)); 829212793Sdim 830212793Sdim return ret; 831212793Sdim} 832212793Sdim 833218893Sdimvoid RegionInfo::splitBlock(BasicBlock* NewBB, BasicBlock *OldBB) 834218893Sdim{ 835218893Sdim Region *R = getRegionFor(OldBB); 836218893Sdim 837218893Sdim setRegionFor(NewBB, R); 838218893Sdim 839218893Sdim while (R->getEntry() == OldBB && !R->isTopLevelRegion()) { 840218893Sdim R->replaceEntry(NewBB); 841218893Sdim R = R->getParent(); 842218893Sdim } 843218893Sdim 844218893Sdim setRegionFor(OldBB, R); 845218893Sdim} 846218893Sdim 847212793Sdimchar RegionInfo::ID = 0; 848218893SdimINITIALIZE_PASS_BEGIN(RegionInfo, "regions", 849218893Sdim "Detect single entry single exit regions", true, true) 850218893SdimINITIALIZE_PASS_DEPENDENCY(DominatorTree) 851218893SdimINITIALIZE_PASS_DEPENDENCY(PostDominatorTree) 852218893SdimINITIALIZE_PASS_DEPENDENCY(DominanceFrontier) 853218893SdimINITIALIZE_PASS_END(RegionInfo, "regions", 854218893Sdim "Detect single entry single exit regions", true, true) 855212793Sdim 856212793Sdim// Create methods available outside of this file, to use them 857212793Sdim// "include/llvm/LinkAllPasses.h". Otherwise the pass would be deleted by 858212793Sdim// the link time optimization. 859212793Sdim 860212793Sdimnamespace llvm { 861212793Sdim FunctionPass *createRegionInfoPass() { 862212793Sdim return new RegionInfo(); 863212793Sdim } 864212793Sdim} 865212793Sdim 866