1f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser//===- RegionInfo.cpp - SESE region detection analysis --------------------===// 2f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// 3f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// The LLVM Compiler Infrastructure 4f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// 5f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// This file is distributed under the University of Illinois Open Source 6f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// License. See LICENSE.TXT for details. 7f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// 8f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser//===----------------------------------------------------------------------===// 9f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// Detects single entry single exit regions in the control flow graph. 10f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser//===----------------------------------------------------------------------===// 11f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 12f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser#include "llvm/Analysis/RegionInfo.h" 13f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser#include "llvm/Analysis/RegionIterator.h" 14f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 15f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser#include "llvm/ADT/PostOrderIterator.h" 16f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser#include "llvm/ADT/Statistic.h" 17f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser#include "llvm/Support/CommandLine.h" 18f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser#include "llvm/Support/ErrorHandling.h" 19082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser#include "llvm/Analysis/LoopInfo.h" 209fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner#include "llvm/Assembly/Writer.h" 21f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 22f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser#define DEBUG_TYPE "region" 23f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser#include "llvm/Support/Debug.h" 24f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 25f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser#include <set> 26f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser#include <algorithm> 27f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 28f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosserusing namespace llvm; 29f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 30f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// Always verify if expensive checking is enabled. 31f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser#ifdef XDEBUG 32811edc1f1a0672d28cd7c938e478a92543e68a51Dan Gohmanstatic bool VerifyRegionInfo = true; 33f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser#else 34811edc1f1a0672d28cd7c938e478a92543e68a51Dan Gohmanstatic bool VerifyRegionInfo = false; 35f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser#endif 36f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 37f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosserstatic cl::opt<bool,true> 38f96b0063674e6bf72da5429bd49097e33c2325c7Tobias GrosserVerifyRegionInfoX("verify-region-info", cl::location(VerifyRegionInfo), 39f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser cl::desc("Verify region info (time consuming)")); 40f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 41f96b0063674e6bf72da5429bd49097e33c2325c7Tobias GrosserSTATISTIC(numRegions, "The # of regions"); 42f96b0063674e6bf72da5429bd49097e33c2325c7Tobias GrosserSTATISTIC(numSimpleRegions, "The # of simple regions"); 43f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 44cc5d992bc167ded99b039ed8fdde190a586a1562Tobias Grosserstatic cl::opt<enum Region::PrintStyle> printStyle("print-region-style", 45cc5d992bc167ded99b039ed8fdde190a586a1562Tobias Grosser cl::Hidden, 46f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser cl::desc("style of printing regions"), 47f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser cl::values( 48cc5d992bc167ded99b039ed8fdde190a586a1562Tobias Grosser clEnumValN(Region::PrintNone, "none", "print no details"), 49cc5d992bc167ded99b039ed8fdde190a586a1562Tobias Grosser clEnumValN(Region::PrintBB, "bb", 5023a22a29441b8b7d948e6ff7c2afb39e6528cfbdHongbin Zheng "print regions in detail with block_iterator"), 51cc5d992bc167ded99b039ed8fdde190a586a1562Tobias Grosser clEnumValN(Region::PrintRN, "rn", 52cc5d992bc167ded99b039ed8fdde190a586a1562Tobias Grosser "print regions in detail with element_iterator"), 53f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser clEnumValEnd)); 54f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser//===----------------------------------------------------------------------===// 55f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser/// Region Implementation 56f96b0063674e6bf72da5429bd49097e33c2325c7Tobias GrosserRegion::Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo* RInfo, 57f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser DominatorTree *dt, Region *Parent) 58f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser : RegionNode(Parent, Entry, 1), RI(RInfo), DT(dt), exit(Exit) {} 59f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 60f96b0063674e6bf72da5429bd49097e33c2325c7Tobias GrosserRegion::~Region() { 61329878f4ddd72c6f2d2d6acfa48d7e1447ed88c0Daniel Dunbar // Free the cached nodes. 62329878f4ddd72c6f2d2d6acfa48d7e1447ed88c0Daniel Dunbar for (BBNodeMapT::iterator it = BBNodeMap.begin(), 63329878f4ddd72c6f2d2d6acfa48d7e1447ed88c0Daniel Dunbar ie = BBNodeMap.end(); it != ie; ++it) 64329878f4ddd72c6f2d2d6acfa48d7e1447ed88c0Daniel Dunbar delete it->second; 65329878f4ddd72c6f2d2d6acfa48d7e1447ed88c0Daniel Dunbar 66f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // Only clean the cache for this Region. Caches of child Regions will be 67f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // cleaned when the child Regions are deleted. 68f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BBNodeMap.clear(); 69f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 70f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser for (iterator I = begin(), E = end(); I != E; ++I) 71f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser delete *I; 72f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 73f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 744bcc0228dcc90385e90f22cef38b2614d3aa3cd1Tobias Grosservoid Region::replaceEntry(BasicBlock *BB) { 754bcc0228dcc90385e90f22cef38b2614d3aa3cd1Tobias Grosser entry.setPointer(BB); 764bcc0228dcc90385e90f22cef38b2614d3aa3cd1Tobias Grosser} 774bcc0228dcc90385e90f22cef38b2614d3aa3cd1Tobias Grosser 784bcc0228dcc90385e90f22cef38b2614d3aa3cd1Tobias Grosservoid Region::replaceExit(BasicBlock *BB) { 794bcc0228dcc90385e90f22cef38b2614d3aa3cd1Tobias Grosser assert(exit && "No exit to replace!"); 804bcc0228dcc90385e90f22cef38b2614d3aa3cd1Tobias Grosser exit = BB; 814bcc0228dcc90385e90f22cef38b2614d3aa3cd1Tobias Grosser} 824bcc0228dcc90385e90f22cef38b2614d3aa3cd1Tobias Grosser 83f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosserbool Region::contains(const BasicBlock *B) const { 84f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BasicBlock *BB = const_cast<BasicBlock*>(B); 85f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 86f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser assert(DT->getNode(BB) && "BB not part of the dominance tree"); 87f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 88f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BasicBlock *entry = getEntry(), *exit = getExit(); 89f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 90f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // Toplevel region. 91f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (!exit) 92f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return true; 93f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 94f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return (DT->dominates(entry, BB) 95f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser && !(DT->dominates(exit, BB) && DT->dominates(entry, exit))); 96f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 97f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 98082d587d35a41ee06985d7867b72fb2632962281Tobias Grosserbool Region::contains(const Loop *L) const { 99082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser // BBs that are not part of any loop are element of the Loop 100082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser // described by the NULL pointer. This loop is not part of any region, 101082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser // except if the region describes the whole function. 102082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser if (L == 0) 103082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser return getExit() == 0; 104082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser 105082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser if (!contains(L->getHeader())) 106082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser return false; 107082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser 108082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser SmallVector<BasicBlock *, 8> ExitingBlocks; 109082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser L->getExitingBlocks(ExitingBlocks); 110082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser 111082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser for (SmallVectorImpl<BasicBlock*>::iterator BI = ExitingBlocks.begin(), 112082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser BE = ExitingBlocks.end(); BI != BE; ++BI) 113082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser if (!contains(*BI)) 114082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser return false; 115082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser 116082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser return true; 117082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser} 118082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser 119082d587d35a41ee06985d7867b72fb2632962281Tobias GrosserLoop *Region::outermostLoopInRegion(Loop *L) const { 120082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser if (!contains(L)) 121082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser return 0; 122082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser 123082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser while (L && contains(L->getParentLoop())) { 124082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser L = L->getParentLoop(); 125082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser } 126082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser 127082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser return L; 128082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser} 129082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser 130082d587d35a41ee06985d7867b72fb2632962281Tobias GrosserLoop *Region::outermostLoopInRegion(LoopInfo *LI, BasicBlock* BB) const { 131082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser assert(LI && BB && "LI and BB cannot be null!"); 132082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser Loop *L = LI->getLoopFor(BB); 133082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser return outermostLoopInRegion(L); 134082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser} 135082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser 13621d842c35326281798f685661b88dedcd09c13aaTobias GrosserBasicBlock *Region::getEnteringBlock() const { 13721d842c35326281798f685661b88dedcd09c13aaTobias Grosser BasicBlock *entry = getEntry(); 13821d842c35326281798f685661b88dedcd09c13aaTobias Grosser BasicBlock *Pred; 13921d842c35326281798f685661b88dedcd09c13aaTobias Grosser BasicBlock *enteringBlock = 0; 140f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 141f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser for (pred_iterator PI = pred_begin(entry), PE = pred_end(entry); PI != PE; 14273362c820bad20e545d37b8a2414c35c0d3d583cTobias Grosser ++PI) { 14321d842c35326281798f685661b88dedcd09c13aaTobias Grosser Pred = *PI; 14473362c820bad20e545d37b8a2414c35c0d3d583cTobias Grosser if (DT->getNode(Pred) && !contains(Pred)) { 14521d842c35326281798f685661b88dedcd09c13aaTobias Grosser if (enteringBlock) 14621d842c35326281798f685661b88dedcd09c13aaTobias Grosser return 0; 14721d842c35326281798f685661b88dedcd09c13aaTobias Grosser 14821d842c35326281798f685661b88dedcd09c13aaTobias Grosser enteringBlock = Pred; 149f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser } 15073362c820bad20e545d37b8a2414c35c0d3d583cTobias Grosser } 151f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 15221d842c35326281798f685661b88dedcd09c13aaTobias Grosser return enteringBlock; 15321d842c35326281798f685661b88dedcd09c13aaTobias Grosser} 15421d842c35326281798f685661b88dedcd09c13aaTobias Grosser 15521d842c35326281798f685661b88dedcd09c13aaTobias GrosserBasicBlock *Region::getExitingBlock() const { 15621d842c35326281798f685661b88dedcd09c13aaTobias Grosser BasicBlock *exit = getExit(); 15721d842c35326281798f685661b88dedcd09c13aaTobias Grosser BasicBlock *Pred; 15821d842c35326281798f685661b88dedcd09c13aaTobias Grosser BasicBlock *exitingBlock = 0; 15921d842c35326281798f685661b88dedcd09c13aaTobias Grosser 16021d842c35326281798f685661b88dedcd09c13aaTobias Grosser if (!exit) 16121d842c35326281798f685661b88dedcd09c13aaTobias Grosser return 0; 162f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 163f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser for (pred_iterator PI = pred_begin(exit), PE = pred_end(exit); PI != PE; 16421d842c35326281798f685661b88dedcd09c13aaTobias Grosser ++PI) { 16521d842c35326281798f685661b88dedcd09c13aaTobias Grosser Pred = *PI; 16621d842c35326281798f685661b88dedcd09c13aaTobias Grosser if (contains(Pred)) { 16721d842c35326281798f685661b88dedcd09c13aaTobias Grosser if (exitingBlock) 16821d842c35326281798f685661b88dedcd09c13aaTobias Grosser return 0; 16921d842c35326281798f685661b88dedcd09c13aaTobias Grosser 17021d842c35326281798f685661b88dedcd09c13aaTobias Grosser exitingBlock = Pred; 171f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser } 17221d842c35326281798f685661b88dedcd09c13aaTobias Grosser } 17321d842c35326281798f685661b88dedcd09c13aaTobias Grosser 17421d842c35326281798f685661b88dedcd09c13aaTobias Grosser return exitingBlock; 17521d842c35326281798f685661b88dedcd09c13aaTobias Grosser} 176f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 17721d842c35326281798f685661b88dedcd09c13aaTobias Grosserbool Region::isSimple() const { 17821d842c35326281798f685661b88dedcd09c13aaTobias Grosser return !isTopLevelRegion() && getEnteringBlock() && getExitingBlock(); 179f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 180f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 181082d587d35a41ee06985d7867b72fb2632962281Tobias Grosserstd::string Region::getNameStr() const { 182082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser std::string exitName; 183082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser std::string entryName; 184082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser 185082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser if (getEntry()->getName().empty()) { 186082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser raw_string_ostream OS(entryName); 187082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser 188082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser WriteAsOperand(OS, getEntry(), false); 189082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser } else 1902774dc085d36c2097e080e2e0ea46a7e49be37afBenjamin Kramer entryName = getEntry()->getName(); 191082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser 192082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser if (getExit()) { 193082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser if (getExit()->getName().empty()) { 194082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser raw_string_ostream OS(exitName); 195082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser 196082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser WriteAsOperand(OS, getExit(), false); 197082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser } else 1982774dc085d36c2097e080e2e0ea46a7e49be37afBenjamin Kramer exitName = getExit()->getName(); 199082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser } else 200082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser exitName = "<Function Return>"; 201082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser 202082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser return entryName + " => " + exitName; 203082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser} 204082d587d35a41ee06985d7867b72fb2632962281Tobias Grosser 205f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosservoid Region::verifyBBInRegion(BasicBlock *BB) const { 206f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (!contains(BB)) 207f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser llvm_unreachable("Broken region found!"); 208f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 209f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BasicBlock *entry = getEntry(), *exit = getExit(); 210f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 211f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 212f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (!contains(*SI) && exit != *SI) 213f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser llvm_unreachable("Broken region found!"); 214f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 215f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (entry != BB) 216f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser for (pred_iterator SI = pred_begin(BB), SE = pred_end(BB); SI != SE; ++SI) 217f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (!contains(*SI)) 218f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser llvm_unreachable("Broken region found!"); 219f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 220f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 221f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosservoid Region::verifyWalk(BasicBlock *BB, std::set<BasicBlock*> *visited) const { 222f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BasicBlock *exit = getExit(); 223f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 224f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser visited->insert(BB); 225f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 226f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser verifyBBInRegion(BB); 227f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 228f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 229f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (*SI != exit && visited->find(*SI) == visited->end()) 230f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser verifyWalk(*SI, visited); 231f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 232f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 233f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosservoid Region::verifyRegion() const { 234f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // Only do verification when user wants to, otherwise this expensive 235f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // check will be invoked by PassManager. 236f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (!VerifyRegionInfo) return; 237f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 238f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser std::set<BasicBlock*> visited; 239f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser verifyWalk(getEntry(), &visited); 240f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 241f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 242f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosservoid Region::verifyRegionNest() const { 243f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser for (Region::const_iterator RI = begin(), RE = end(); RI != RE; ++RI) 244f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser (*RI)->verifyRegionNest(); 245f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 246f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser verifyRegion(); 247f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 248f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 249f96b0063674e6bf72da5429bd49097e33c2325c7Tobias GrosserRegion::element_iterator Region::element_begin() { 250f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return GraphTraits<Region*>::nodes_begin(this); 251f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 252f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 253f96b0063674e6bf72da5429bd49097e33c2325c7Tobias GrosserRegion::element_iterator Region::element_end() { 254f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return GraphTraits<Region*>::nodes_end(this); 255f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 256f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 257f96b0063674e6bf72da5429bd49097e33c2325c7Tobias GrosserRegion::const_element_iterator Region::element_begin() const { 258f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return GraphTraits<const Region*>::nodes_begin(this); 259f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 260f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 261f96b0063674e6bf72da5429bd49097e33c2325c7Tobias GrosserRegion::const_element_iterator Region::element_end() const { 262f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return GraphTraits<const Region*>::nodes_end(this); 263f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 264f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 265f96b0063674e6bf72da5429bd49097e33c2325c7Tobias GrosserRegion* Region::getSubRegionNode(BasicBlock *BB) const { 266f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser Region *R = RI->getRegionFor(BB); 267f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 268f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (!R || R == this) 269f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return 0; 270f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 271f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // If we pass the BB out of this region, that means our code is broken. 272f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser assert(contains(R) && "BB not in current region!"); 273f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 274f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser while (contains(R->getParent()) && R->getParent() != this) 275f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser R = R->getParent(); 276f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 277f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (R->getEntry() != BB) 278f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return 0; 279f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 280f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return R; 281f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 282f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 283f96b0063674e6bf72da5429bd49097e33c2325c7Tobias GrosserRegionNode* Region::getBBNode(BasicBlock *BB) const { 284f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser assert(contains(BB) && "Can get BB node out of this region!"); 285f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 286f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BBNodeMapT::const_iterator at = BBNodeMap.find(BB); 287f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 288f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (at != BBNodeMap.end()) 289f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return at->second; 290f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 291f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser RegionNode *NewNode = new RegionNode(const_cast<Region*>(this), BB); 292f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BBNodeMap.insert(std::make_pair(BB, NewNode)); 293f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return NewNode; 294f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 295f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 296f96b0063674e6bf72da5429bd49097e33c2325c7Tobias GrosserRegionNode* Region::getNode(BasicBlock *BB) const { 297f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser assert(contains(BB) && "Can get BB node out of this region!"); 298f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (Region* Child = getSubRegionNode(BB)) 299f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return Child->getNode(); 300f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 301f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return getBBNode(BB); 302f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 303f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 304f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosservoid Region::transferChildrenTo(Region *To) { 305f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser for (iterator I = begin(), E = end(); I != E; ++I) { 306f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser (*I)->parent = To; 307f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser To->children.push_back(*I); 308f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser } 309f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser children.clear(); 310f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 311f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 3129649390e1fcb6d42e228364230f16409ad150fefTobias Grosservoid Region::addSubRegion(Region *SubRegion, bool moveChildren) { 313f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser assert(SubRegion->parent == 0 && "SubRegion already has a parent!"); 3149649390e1fcb6d42e228364230f16409ad150fefTobias Grosser assert(std::find(begin(), end(), SubRegion) == children.end() 3159649390e1fcb6d42e228364230f16409ad150fefTobias Grosser && "Subregion already exists!"); 3169649390e1fcb6d42e228364230f16409ad150fefTobias Grosser 317f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser SubRegion->parent = this; 318f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser children.push_back(SubRegion); 3199649390e1fcb6d42e228364230f16409ad150fefTobias Grosser 3209649390e1fcb6d42e228364230f16409ad150fefTobias Grosser if (!moveChildren) 3219649390e1fcb6d42e228364230f16409ad150fefTobias Grosser return; 3229649390e1fcb6d42e228364230f16409ad150fefTobias Grosser 3239649390e1fcb6d42e228364230f16409ad150fefTobias Grosser assert(SubRegion->children.size() == 0 3249649390e1fcb6d42e228364230f16409ad150fefTobias Grosser && "SubRegions that contain children are not supported"); 3259649390e1fcb6d42e228364230f16409ad150fefTobias Grosser 3269649390e1fcb6d42e228364230f16409ad150fefTobias Grosser for (element_iterator I = element_begin(), E = element_end(); I != E; ++I) 3279649390e1fcb6d42e228364230f16409ad150fefTobias Grosser if (!(*I)->isSubRegion()) { 3289649390e1fcb6d42e228364230f16409ad150fefTobias Grosser BasicBlock *BB = (*I)->getNodeAs<BasicBlock>(); 3299649390e1fcb6d42e228364230f16409ad150fefTobias Grosser 3309649390e1fcb6d42e228364230f16409ad150fefTobias Grosser if (SubRegion->contains(BB)) 3319649390e1fcb6d42e228364230f16409ad150fefTobias Grosser RI->setRegionFor(BB, SubRegion); 3329649390e1fcb6d42e228364230f16409ad150fefTobias Grosser } 3339649390e1fcb6d42e228364230f16409ad150fefTobias Grosser 3349649390e1fcb6d42e228364230f16409ad150fefTobias Grosser std::vector<Region*> Keep; 3359649390e1fcb6d42e228364230f16409ad150fefTobias Grosser for (iterator I = begin(), E = end(); I != E; ++I) 3369649390e1fcb6d42e228364230f16409ad150fefTobias Grosser if (SubRegion->contains(*I) && *I != SubRegion) { 3379649390e1fcb6d42e228364230f16409ad150fefTobias Grosser SubRegion->children.push_back(*I); 3389649390e1fcb6d42e228364230f16409ad150fefTobias Grosser (*I)->parent = SubRegion; 3399649390e1fcb6d42e228364230f16409ad150fefTobias Grosser } else 3409649390e1fcb6d42e228364230f16409ad150fefTobias Grosser Keep.push_back(*I); 3419649390e1fcb6d42e228364230f16409ad150fefTobias Grosser 3429649390e1fcb6d42e228364230f16409ad150fefTobias Grosser children.clear(); 3439649390e1fcb6d42e228364230f16409ad150fefTobias Grosser children.insert(children.begin(), Keep.begin(), Keep.end()); 344f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 345f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 346f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 347f96b0063674e6bf72da5429bd49097e33c2325c7Tobias GrosserRegion *Region::removeSubRegion(Region *Child) { 348f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser assert(Child->parent == this && "Child is not a child of this region!"); 349f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser Child->parent = 0; 350f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser RegionSet::iterator I = std::find(children.begin(), children.end(), Child); 351f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser assert(I != children.end() && "Region does not exit. Unable to remove."); 352f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser children.erase(children.begin()+(I-begin())); 353f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return Child; 354f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 355f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 356f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosserunsigned Region::getDepth() const { 357f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser unsigned Depth = 0; 358f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 359f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser for (Region *R = parent; R != 0; R = R->parent) 360f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser ++Depth; 361f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 362f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return Depth; 363f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 364f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 365c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias GrosserRegion *Region::getExpandedRegion() const { 366c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser unsigned NumSuccessors = exit->getTerminator()->getNumSuccessors(); 367c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser 368c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser if (NumSuccessors == 0) 369c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser return NULL; 370c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser 371c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser for (pred_iterator PI = pred_begin(getExit()), PE = pred_end(getExit()); 372c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser PI != PE; ++PI) 373c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser if (!DT->dominates(getEntry(), *PI)) 374c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser return NULL; 375c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser 376c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser Region *R = RI->getRegionFor(exit); 377c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser 378c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser if (R->getEntry() != exit) { 379c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser if (exit->getTerminator()->getNumSuccessors() == 1) 380c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser return new Region(getEntry(), *succ_begin(exit), RI, DT); 381c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser else 382c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser return NULL; 383c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser } 384c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser 385c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser while (R->getParent() && R->getParent()->getEntry() == exit) 386c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser R = R->getParent(); 387c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser 388c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser if (!DT->dominates(getEntry(), R->getExit())) 389c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser for (pred_iterator PI = pred_begin(getExit()), PE = pred_end(getExit()); 390c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser PI != PE; ++PI) 391c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser if (!DT->dominates(R->getExit(), *PI)) 392c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser return NULL; 393c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser 394c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser return new Region(getEntry(), R->getExit(), RI, DT); 395c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser} 396c69bd733c02a4e0ca25f7a2d6b9b05168720d373Tobias Grosser 397cc5d992bc167ded99b039ed8fdde190a586a1562Tobias Grosservoid Region::print(raw_ostream &OS, bool print_tree, unsigned level, 398cc5d992bc167ded99b039ed8fdde190a586a1562Tobias Grosser enum PrintStyle Style) const { 399f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (print_tree) 400f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser OS.indent(level*2) << "[" << level << "] " << getNameStr(); 401f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser else 402f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser OS.indent(level*2) << getNameStr(); 403f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 404f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser OS << "\n"; 405f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 406f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 407cc5d992bc167ded99b039ed8fdde190a586a1562Tobias Grosser if (Style != PrintNone) { 408f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser OS.indent(level*2) << "{\n"; 409f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser OS.indent(level*2 + 2); 410f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 411cc5d992bc167ded99b039ed8fdde190a586a1562Tobias Grosser if (Style == PrintBB) { 41223a22a29441b8b7d948e6ff7c2afb39e6528cfbdHongbin Zheng for (const_block_iterator I = block_begin(), E = block_end(); I != E; ++I) 41323a22a29441b8b7d948e6ff7c2afb39e6528cfbdHongbin Zheng OS << (*I)->getName() << ", "; // TODO: remove the last "," 414cc5d992bc167ded99b039ed8fdde190a586a1562Tobias Grosser } else if (Style == PrintRN) { 415f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser for (const_element_iterator I = element_begin(), E = element_end(); I!=E; ++I) 416f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser OS << **I << ", "; // TODO: remove the last ", 417f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser } 418f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 419f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser OS << "\n"; 420f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser } 421f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 422f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (print_tree) 423f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser for (const_iterator RI = begin(), RE = end(); RI != RE; ++RI) 424cc5d992bc167ded99b039ed8fdde190a586a1562Tobias Grosser (*RI)->print(OS, print_tree, level+1, Style); 425f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 426cc5d992bc167ded99b039ed8fdde190a586a1562Tobias Grosser if (Style != PrintNone) 427f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser OS.indent(level*2) << "} \n"; 428f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 429f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 430cc77eece74c8db09acc2af425e7e6c88a5bb30d1Manman Ren#ifndef NDEBUG 431f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosservoid Region::dump() const { 432cc5d992bc167ded99b039ed8fdde190a586a1562Tobias Grosser print(dbgs(), true, getDepth(), printStyle.getValue()); 433f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 434cc77eece74c8db09acc2af425e7e6c88a5bb30d1Manman Ren#endif 435f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 436f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosservoid Region::clearNodeCache() { 43767be08a2f186d8262781f0d1ef67cab3cd2a0d2bTobias Grosser // Free the cached nodes. 43867be08a2f186d8262781f0d1ef67cab3cd2a0d2bTobias Grosser for (BBNodeMapT::iterator I = BBNodeMap.begin(), 439c502101000b53eca25ef45068f57669d12d617bfTobias Grosser IE = BBNodeMap.end(); I != IE; ++I) 44067be08a2f186d8262781f0d1ef67cab3cd2a0d2bTobias Grosser delete I->second; 44167be08a2f186d8262781f0d1ef67cab3cd2a0d2bTobias Grosser 442f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BBNodeMap.clear(); 443f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser for (Region::iterator RI = begin(), RE = end(); RI != RE; ++RI) 444f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser (*RI)->clearNodeCache(); 445f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 446f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 447f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser//===----------------------------------------------------------------------===// 448f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// RegionInfo implementation 449f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// 450f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 451f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosserbool RegionInfo::isCommonDomFrontier(BasicBlock *BB, BasicBlock *entry, 452f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BasicBlock *exit) const { 4533d8586eb6384f22984e8c519ea9742eac68c9724Gabor Greif for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) { 4543d8586eb6384f22984e8c519ea9742eac68c9724Gabor Greif BasicBlock *P = *PI; 4553d8586eb6384f22984e8c519ea9742eac68c9724Gabor Greif if (DT->dominates(entry, P) && !DT->dominates(exit, P)) 456f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return false; 4573d8586eb6384f22984e8c519ea9742eac68c9724Gabor Greif } 458f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return true; 459f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 460f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 461f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosserbool RegionInfo::isRegion(BasicBlock *entry, BasicBlock *exit) const { 462f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser assert(entry && exit && "entry and exit must not be null!"); 463f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser typedef DominanceFrontier::DomSetType DST; 464f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 46511aa60d05ac3a26a547022f574fa09dfeec2e0ccGabor Greif DST *entrySuccs = &DF->find(entry)->second; 466f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 467f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // Exit is the header of a loop that contains the entry. In this case, 468f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // the dominance frontier must only contain the exit. 469f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (!DT->dominates(entry, exit)) { 470f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser for (DST::iterator SI = entrySuccs->begin(), SE = entrySuccs->end(); 471f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser SI != SE; ++SI) 472f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (*SI != exit && *SI != entry) 473f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return false; 474f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 475f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return true; 476f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser } 477f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 47811aa60d05ac3a26a547022f574fa09dfeec2e0ccGabor Greif DST *exitSuccs = &DF->find(exit)->second; 479f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 480f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // Do not allow edges leaving the region. 481f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser for (DST::iterator SI = entrySuccs->begin(), SE = entrySuccs->end(); 482f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser SI != SE; ++SI) { 483f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (*SI == exit || *SI == entry) 484f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser continue; 485f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (exitSuccs->find(*SI) == exitSuccs->end()) 486f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return false; 487f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (!isCommonDomFrontier(*SI, entry, exit)) 488f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return false; 489f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser } 490f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 491f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // Do not allow edges pointing into the region. 492f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser for (DST::iterator SI = exitSuccs->begin(), SE = exitSuccs->end(); 493f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser SI != SE; ++SI) 494a29dbd2dcc04c8d07dd9e1e49b4e54debbc23996Dan Gohman if (DT->properlyDominates(entry, *SI) && *SI != exit) 495f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return false; 496f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 497f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 498f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return true; 499f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 500f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 501f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosservoid RegionInfo::insertShortCut(BasicBlock *entry, BasicBlock *exit, 502f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BBtoBBMap *ShortCut) const { 503f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser assert(entry && exit && "entry and exit must not be null!"); 504f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 505f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BBtoBBMap::iterator e = ShortCut->find(exit); 506f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 507f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (e == ShortCut->end()) 508f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // No further region at exit available. 509f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser (*ShortCut)[entry] = exit; 510f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser else { 511f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // We found a region e that starts at exit. Therefore (entry, e->second) 512f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // is also a region, that is larger than (entry, exit). Insert the 513f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // larger one. 514f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BasicBlock *BB = e->second; 515f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser (*ShortCut)[entry] = BB; 516f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser } 517f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 518f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 519f96b0063674e6bf72da5429bd49097e33c2325c7Tobias GrosserDomTreeNode* RegionInfo::getNextPostDom(DomTreeNode* N, 520f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BBtoBBMap *ShortCut) const { 521f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BBtoBBMap::iterator e = ShortCut->find(N->getBlock()); 522f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 523f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (e == ShortCut->end()) 524f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return N->getIDom(); 525f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 526f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return PDT->getNode(e->second)->getIDom(); 527f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 528f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 529f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosserbool RegionInfo::isTrivialRegion(BasicBlock *entry, BasicBlock *exit) const { 530f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser assert(entry && exit && "entry and exit must not be null!"); 531f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 532f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser unsigned num_successors = succ_end(entry) - succ_begin(entry); 533f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 534f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (num_successors <= 1 && exit == *(succ_begin(entry))) 535f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return true; 536f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 537f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return false; 538f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 539f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 540f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosservoid RegionInfo::updateStatistics(Region *R) { 541f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser ++numRegions; 542f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 543f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // TODO: Slow. Should only be enabled if -stats is used. 544f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (R->isSimple()) ++numSimpleRegions; 545f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 546f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 547f96b0063674e6bf72da5429bd49097e33c2325c7Tobias GrosserRegion *RegionInfo::createRegion(BasicBlock *entry, BasicBlock *exit) { 548f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser assert(entry && exit && "entry and exit must not be null!"); 549f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 550f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (isTrivialRegion(entry, exit)) 551f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return 0; 552f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 553f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser Region *region = new Region(entry, exit, this, DT); 554f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BBtoRegion.insert(std::make_pair(entry, region)); 555f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 556f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser #ifdef XDEBUG 557f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser region->verifyRegion(); 558f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser #else 559f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser DEBUG(region->verifyRegion()); 560f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser #endif 561f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 562f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser updateStatistics(region); 563f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return region; 564f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 565f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 566f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosservoid RegionInfo::findRegionsWithEntry(BasicBlock *entry, BBtoBBMap *ShortCut) { 567f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser assert(entry); 568f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 569f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser DomTreeNode *N = PDT->getNode(entry); 570f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 571f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (!N) 572f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return; 573f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 574f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser Region *lastRegion= 0; 575f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BasicBlock *lastExit = entry; 576f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 577f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // As only a BasicBlock that postdominates entry can finish a region, walk the 578f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // post dominance tree upwards. 579f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser while ((N = getNextPostDom(N, ShortCut))) { 580f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BasicBlock *exit = N->getBlock(); 581f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 582f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (!exit) 583f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser break; 584f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 585f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (isRegion(entry, exit)) { 586f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser Region *newRegion = createRegion(entry, exit); 587f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 588f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (lastRegion) 589f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser newRegion->addSubRegion(lastRegion); 590f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 591f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser lastRegion = newRegion; 592f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser lastExit = exit; 593f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser } 594f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 595f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // This can never be a region, so stop the search. 596f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (!DT->dominates(entry, exit)) 597f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser break; 598f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser } 599f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 600f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // Tried to create regions from entry to lastExit. Next time take a 601f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // shortcut from entry to lastExit. 602f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (lastExit != entry) 603f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser insertShortCut(entry, lastExit, ShortCut); 604f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 605f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 606f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosservoid RegionInfo::scanForRegions(Function &F, BBtoBBMap *ShortCut) { 607f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BasicBlock *entry = &(F.getEntryBlock()); 608f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser DomTreeNode *N = DT->getNode(entry); 609f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 610f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // Iterate over the dominance tree in post order to start with the small 611f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // regions from the bottom of the dominance tree. If the small regions are 612f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // detected first, detection of bigger regions is faster, as we can jump 613f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // over the small regions. 614f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser for (po_iterator<DomTreeNode*> FI = po_begin(N), FE = po_end(N); FI != FE; 615f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser ++FI) { 616f95eef695d35cac832dfd1ff2b2e3081f7d0e24aGabor Greif findRegionsWithEntry(FI->getBlock(), ShortCut); 617f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser } 618f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 619f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 620f96b0063674e6bf72da5429bd49097e33c2325c7Tobias GrosserRegion *RegionInfo::getTopMostParent(Region *region) { 621f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser while (region->parent) 622f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser region = region->getParent(); 623f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 624f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return region; 625f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 626f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 627f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosservoid RegionInfo::buildRegionsTree(DomTreeNode *N, Region *region) { 628f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BasicBlock *BB = N->getBlock(); 629f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 630f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // Passed region exit 631f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser while (BB == region->getExit()) 632f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser region = region->getParent(); 633f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 634f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BBtoRegionMap::iterator it = BBtoRegion.find(BB); 635f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 636f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // This basic block is a start block of a region. It is already in the 637f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // BBtoRegion relation. Only the child basic blocks have to be updated. 638f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (it != BBtoRegion.end()) { 63990f20044ade3712c8b0c3f4ebe47d57ad15ae6ceChad Rosier Region *newRegion = it->second; 640f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser region->addSubRegion(getTopMostParent(newRegion)); 641f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser region = newRegion; 642f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser } else { 643f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BBtoRegion[BB] = region; 644f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser } 645f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 646f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser for (DomTreeNode::iterator CI = N->begin(), CE = N->end(); CI != CE; ++CI) 647f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser buildRegionsTree(*CI, region); 648f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 649f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 650f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosservoid RegionInfo::releaseMemory() { 651f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BBtoRegion.clear(); 652f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (TopLevelRegion) 653f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser delete TopLevelRegion; 654f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser TopLevelRegion = 0; 655f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 656f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 65790c579de5a383cee278acc3f7e7b9d0a656e6a35Owen AndersonRegionInfo::RegionInfo() : FunctionPass(ID) { 658081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeRegionInfoPass(*PassRegistry::getPassRegistry()); 659f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser TopLevelRegion = 0; 660f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 661f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 662f96b0063674e6bf72da5429bd49097e33c2325c7Tobias GrosserRegionInfo::~RegionInfo() { 663f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser releaseMemory(); 664f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 665f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 666f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosservoid RegionInfo::Calculate(Function &F) { 667f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // ShortCut a function where for every BB the exit of the largest region 668f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // starting with BB is stored. These regions can be threated as single BBS. 669f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // This improves performance on linear CFGs. 670f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BBtoBBMap ShortCut; 671f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 672f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser scanForRegions(F, &ShortCut); 673f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BasicBlock *BB = &F.getEntryBlock(); 674f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser buildRegionsTree(DT->getNode(BB), TopLevelRegion); 675f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 676f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 677f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosserbool RegionInfo::runOnFunction(Function &F) { 678f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser releaseMemory(); 679f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 680f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser DT = &getAnalysis<DominatorTree>(); 681f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser PDT = &getAnalysis<PostDominatorTree>(); 682f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser DF = &getAnalysis<DominanceFrontier>(); 683f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 684f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser TopLevelRegion = new Region(&F.getEntryBlock(), 0, this, DT, 0); 685f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser updateStatistics(TopLevelRegion); 686f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 687f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser Calculate(F); 688f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 689f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return false; 690f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 691f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 692f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosservoid RegionInfo::getAnalysisUsage(AnalysisUsage &AU) const { 693f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser AU.setPreservesAll(); 694f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser AU.addRequiredTransitive<DominatorTree>(); 695f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser AU.addRequired<PostDominatorTree>(); 696f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser AU.addRequired<DominanceFrontier>(); 697f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 698f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 699f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosservoid RegionInfo::print(raw_ostream &OS, const Module *) const { 700f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser OS << "Region tree:\n"; 701cc5d992bc167ded99b039ed8fdde190a586a1562Tobias Grosser TopLevelRegion->print(OS, true, 0, printStyle.getValue()); 702f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser OS << "End region tree\n"; 703f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 704f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 705f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosservoid RegionInfo::verifyAnalysis() const { 706f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // Only do verification when user wants to, otherwise this expensive check 707f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // will be invoked by PMDataManager::verifyPreservedAnalysis when 708f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser // a regionpass (marked PreservedAll) finish. 709f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (!VerifyRegionInfo) return; 710f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 711f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser TopLevelRegion->verifyRegionNest(); 712f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 713f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 714f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// Region pass manager support. 715f96b0063674e6bf72da5429bd49097e33c2325c7Tobias GrosserRegion *RegionInfo::getRegionFor(BasicBlock *BB) const { 716f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BBtoRegionMap::const_iterator I= 717f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BBtoRegion.find(BB); 718f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return I != BBtoRegion.end() ? I->second : 0; 719f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 720f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 7219ee5c5077690a4de31e22bb9e135deb6da3f68fbTobias Grosservoid RegionInfo::setRegionFor(BasicBlock *BB, Region *R) { 7229ee5c5077690a4de31e22bb9e135deb6da3f68fbTobias Grosser BBtoRegion[BB] = R; 7239ee5c5077690a4de31e22bb9e135deb6da3f68fbTobias Grosser} 7249ee5c5077690a4de31e22bb9e135deb6da3f68fbTobias Grosser 725f96b0063674e6bf72da5429bd49097e33c2325c7Tobias GrosserRegion *RegionInfo::operator[](BasicBlock *BB) const { 726f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return getRegionFor(BB); 727f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 728f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 7290e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias GrosserBasicBlock *RegionInfo::getMaxRegionExit(BasicBlock *BB) const { 7300e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser BasicBlock *Exit = NULL; 7310e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser 7320e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser while (true) { 7330e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser // Get largest region that starts at BB. 7340e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser Region *R = getRegionFor(BB); 7350e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser while (R && R->getParent() && R->getParent()->getEntry() == BB) 7360e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser R = R->getParent(); 7370e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser 7380e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser // Get the single exit of BB. 7390e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser if (R && R->getEntry() == BB) 7400e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser Exit = R->getExit(); 7410e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser else if (++succ_begin(BB) == succ_end(BB)) 7420e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser Exit = *succ_begin(BB); 7430e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser else // No single exit exists. 7440e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser return Exit; 7450e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser 7460e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser // Get largest region that starts at Exit. 7470e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser Region *ExitR = getRegionFor(Exit); 7480e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser while (ExitR && ExitR->getParent() 7490e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser && ExitR->getParent()->getEntry() == Exit) 7500e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser ExitR = ExitR->getParent(); 7510e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser 7520e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser for (pred_iterator PI = pred_begin(Exit), PE = pred_end(Exit); PI != PE; 7530e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser ++PI) 7540e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser if (!R->contains(*PI) && !ExitR->contains(*PI)) 7550e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser break; 7560e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser 7570e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser // This stops infinite cycles. 7580e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser if (DT->dominates(Exit, BB)) 7590e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser break; 7600e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser 7610e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser BB = Exit; 7620e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser } 7630e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser 7640e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser return Exit; 7650e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser} 7660e6fcf4be360f5d73685c213e3b4af1bb9ce2b5dTobias Grosser 767f96b0063674e6bf72da5429bd49097e33c2325c7Tobias GrosserRegion* 768f96b0063674e6bf72da5429bd49097e33c2325c7Tobias GrosserRegionInfo::getCommonRegion(Region *A, Region *B) const { 769f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser assert (A && B && "One of the Regions is NULL"); 770f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 771f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser if (A->contains(B)) return A; 772f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 773f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser while (!B->contains(A)) 774f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser B = B->getParent(); 775f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 776f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return B; 777f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 778f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 779f96b0063674e6bf72da5429bd49097e33c2325c7Tobias GrosserRegion* 780f96b0063674e6bf72da5429bd49097e33c2325c7Tobias GrosserRegionInfo::getCommonRegion(SmallVectorImpl<Region*> &Regions) const { 781f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser Region* ret = Regions.back(); 782f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser Regions.pop_back(); 783f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 784f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser for (SmallVectorImpl<Region*>::const_iterator I = Regions.begin(), 785f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser E = Regions.end(); I != E; ++I) 786f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser ret = getCommonRegion(ret, *I); 787f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 788f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return ret; 789f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 790f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 791f96b0063674e6bf72da5429bd49097e33c2325c7Tobias GrosserRegion* 792f96b0063674e6bf72da5429bd49097e33c2325c7Tobias GrosserRegionInfo::getCommonRegion(SmallVectorImpl<BasicBlock*> &BBs) const { 793f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser Region* ret = getRegionFor(BBs.back()); 794f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser BBs.pop_back(); 795f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 796f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser for (SmallVectorImpl<BasicBlock*>::const_iterator I = BBs.begin(), 797f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser E = BBs.end(); I != E; ++I) 798f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser ret = getCommonRegion(ret, getRegionFor(*I)); 799f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 800f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return ret; 801f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 802f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 803592316c4198023431799f8e597860b31ea7116c9Tobias Grosservoid RegionInfo::splitBlock(BasicBlock* NewBB, BasicBlock *OldBB) 804592316c4198023431799f8e597860b31ea7116c9Tobias Grosser{ 805592316c4198023431799f8e597860b31ea7116c9Tobias Grosser Region *R = getRegionFor(OldBB); 806b227930cd6850e4c47358e671dbe2cdacb430defTobias Grosser 807592316c4198023431799f8e597860b31ea7116c9Tobias Grosser setRegionFor(NewBB, R); 808592316c4198023431799f8e597860b31ea7116c9Tobias Grosser 809b227930cd6850e4c47358e671dbe2cdacb430defTobias Grosser while (R->getEntry() == OldBB && !R->isTopLevelRegion()) { 810592316c4198023431799f8e597860b31ea7116c9Tobias Grosser R->replaceEntry(NewBB); 811592316c4198023431799f8e597860b31ea7116c9Tobias Grosser R = R->getParent(); 812592316c4198023431799f8e597860b31ea7116c9Tobias Grosser } 813592316c4198023431799f8e597860b31ea7116c9Tobias Grosser 814592316c4198023431799f8e597860b31ea7116c9Tobias Grosser setRegionFor(OldBB, R); 815592316c4198023431799f8e597860b31ea7116c9Tobias Grosser} 816592316c4198023431799f8e597860b31ea7116c9Tobias Grosser 817f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosserchar RegionInfo::ID = 0; 8182ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(RegionInfo, "regions", 8192ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Detect single entry single exit regions", true, true) 8202ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(DominatorTree) 8212ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(PostDominatorTree) 8222ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(DominanceFrontier) 8232ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(RegionInfo, "regions", 824ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Detect single entry single exit regions", true, true) 825f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 826f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// Create methods available outside of this file, to use them 827f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// "include/llvm/LinkAllPasses.h". Otherwise the pass would be deleted by 828f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser// the link time optimization. 829f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 830f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grossernamespace llvm { 831f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser FunctionPass *createRegionInfoPass() { 832f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser return new RegionInfo(); 833f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser } 834f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser} 835f96b0063674e6bf72da5429bd49097e33c2325c7Tobias Grosser 836