#include "llvm/Support/CommandLine.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
+#include "llvm/Analysis/LoopInfo.h"
#define DEBUG_TYPE "region"
#include "llvm/Support/Debug.h"
// Always verify if expensive checking is enabled.
#ifdef XDEBUG
-bool VerifyRegionInfo = true;
+static bool VerifyRegionInfo = true;
#else
-bool VerifyRegionInfo = false;
+static bool VerifyRegionInfo = false;
#endif
static cl::opt<bool,true>
: RegionNode(Parent, Entry, 1), RI(RInfo), DT(dt), exit(Exit) {}
Region::~Region() {
+ // Free the cached nodes.
+ for (BBNodeMapT::iterator it = BBNodeMap.begin(),
+ ie = BBNodeMap.end(); it != ie; ++it)
+ delete it->second;
+
// Only clean the cache for this Region. Caches of child Regions will be
// cleaned when the child Regions are deleted.
BBNodeMap.clear();
&& !(DT->dominates(exit, BB) && DT->dominates(entry, exit)));
}
+bool Region::contains(const Loop *L) const {
+ // BBs that are not part of any loop are element of the Loop
+ // described by the NULL pointer. This loop is not part of any region,
+ // except if the region describes the whole function.
+ if (L == 0)
+ return getExit() == 0;
+
+ if (!contains(L->getHeader()))
+ return false;
+
+ SmallVector<BasicBlock *, 8> ExitingBlocks;
+ L->getExitingBlocks(ExitingBlocks);
+
+ for (SmallVectorImpl<BasicBlock*>::iterator BI = ExitingBlocks.begin(),
+ BE = ExitingBlocks.end(); BI != BE; ++BI)
+ if (!contains(*BI))
+ return false;
+
+ return true;
+}
+
+Loop *Region::outermostLoopInRegion(Loop *L) const {
+ if (!contains(L))
+ return 0;
+
+ while (L && contains(L->getParentLoop())) {
+ L = L->getParentLoop();
+ }
+
+ return L;
+}
+
+Loop *Region::outermostLoopInRegion(LoopInfo *LI, BasicBlock* BB) const {
+ assert(LI && BB && "LI and BB cannot be null!");
+ Loop *L = LI->getLoopFor(BB);
+ return outermostLoopInRegion(L);
+}
+
bool Region::isSimple() const {
bool isSimple = true;
bool found = false;
return false;
for (pred_iterator PI = pred_begin(entry), PE = pred_end(entry); PI != PE;
- ++PI)
- if (!contains(*PI)) {
+ ++PI) {
+ BasicBlock *Pred = *PI;
+ if (DT->getNode(Pred) && !contains(Pred)) {
if (found) {
isSimple = false;
break;
}
found = true;
}
+ }
found = false;
return isSimple;
}
+std::string Region::getNameStr() const {
+ std::string exitName;
+ std::string entryName;
+
+ if (getEntry()->getName().empty()) {
+ raw_string_ostream OS(entryName);
+
+ WriteAsOperand(OS, getEntry(), false);
+ entryName = OS.str();
+ } else
+ entryName = getEntry()->getNameStr();
+
+ if (getExit()) {
+ if (getExit()->getName().empty()) {
+ raw_string_ostream OS(exitName);
+
+ WriteAsOperand(OS, getExit(), false);
+ exitName = OS.str();
+ } else
+ exitName = getExit()->getNameStr();
+ } else
+ exitName = "<Function Return>";
+
+ return entryName + " => " + exitName;
+}
+
void Region::verifyBBInRegion(BasicBlock *BB) const {
if (!contains(BB))
llvm_unreachable("Broken region found!");
bool RegionInfo::isCommonDomFrontier(BasicBlock *BB, BasicBlock *entry,
BasicBlock *exit) const {
- for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI)
- if (DT->dominates(entry, *PI) && !DT->dominates(exit, *PI))
+ for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
+ BasicBlock *P = *PI;
+ if (DT->dominates(entry, P) && !DT->dominates(exit, P))
return false;
-
+ }
return true;
}
assert(entry && exit && "entry and exit must not be null!");
typedef DominanceFrontier::DomSetType DST;
- DST *entrySuccs = &(*DF->find(entry)).second;
+ DST *entrySuccs = &DF->find(entry)->second;
// Exit is the header of a loop that contains the entry. In this case,
// the dominance frontier must only contain the exit.
return true;
}
- DST *exitSuccs = &(*DF->find(exit)).second;
+ DST *exitSuccs = &DF->find(exit)->second;
// Do not allow edges leaving the region.
for (DST::iterator SI = entrySuccs->begin(), SE = entrySuccs->end();
// Do not allow edges pointing into the region.
for (DST::iterator SI = exitSuccs->begin(), SE = exitSuccs->end();
SI != SE; ++SI)
- if (DT->dominates(entry, *SI) && *SI != entry && *SI != exit)
+ if (DT->properlyDominates(entry, *SI) && *SI != exit)
return false;
// over the small regions.
for (po_iterator<DomTreeNode*> FI = po_begin(N), FE = po_end(N); FI != FE;
++FI) {
- findRegionsWithEntry((*FI)->getBlock(), ShortCut);
+ findRegionsWithEntry(FI->getBlock(), ShortCut);
}
}
TopLevelRegion = 0;
}
-RegionInfo::RegionInfo() : FunctionPass(&ID) {
+RegionInfo::RegionInfo() : FunctionPass(ID) {
TopLevelRegion = 0;
}
return getRegionFor(BB);
}
+
+BasicBlock *RegionInfo::getMaxRegionExit(BasicBlock *BB) const {
+ BasicBlock *Exit = NULL;
+
+ while (true) {
+ // Get largest region that starts at BB.
+ Region *R = getRegionFor(BB);
+ while (R && R->getParent() && R->getParent()->getEntry() == BB)
+ R = R->getParent();
+
+ // Get the single exit of BB.
+ if (R && R->getEntry() == BB)
+ Exit = R->getExit();
+ else if (++succ_begin(BB) == succ_end(BB))
+ Exit = *succ_begin(BB);
+ else // No single exit exists.
+ return Exit;
+
+ // Get largest region that starts at Exit.
+ Region *ExitR = getRegionFor(Exit);
+ while (ExitR && ExitR->getParent()
+ && ExitR->getParent()->getEntry() == Exit)
+ ExitR = ExitR->getParent();
+
+ for (pred_iterator PI = pred_begin(Exit), PE = pred_end(Exit); PI != PE;
+ ++PI)
+ if (!R->contains(*PI) && !ExitR->contains(*PI))
+ break;
+
+ // This stops infinite cycles.
+ if (DT->dominates(Exit, BB))
+ break;
+
+ BB = Exit;
+ }
+
+ return Exit;
+}
+
Region*
RegionInfo::getCommonRegion(Region *A, Region *B) const {
assert (A && B && "One of the Regions is NULL");
projects / oota-llvm.git / blobdiff