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