X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FRegionInfo.cpp;h=abc057a773a9fba3263ee44cd844c26dc853f79c;hb=1c8820d8d858aafcccbfa6b8820cadd915a6049b;hp=589cc471defca0dabdabbdf1a36f702f6f5b5006;hpb=f96b0063674e6bf72da5429bd49097e33c2325c7;p=oota-llvm.git

diff --git a/lib/Analysis/RegionInfo.cpp b/lib/Analysis/RegionInfo.cpp
index 589cc471def..abc057a773a 100644
--- a/lib/Analysis/RegionInfo.cpp
+++ b/lib/Analysis/RegionInfo.cpp
@@ -17,6 +17,7 @@
 #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"
@@ -28,9 +29,9 @@ using namespace llvm;
 
 // 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>
@@ -58,6 +59,11 @@ Region::Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo* RInfo,
                : 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();
@@ -81,6 +87,44 @@ bool Region::contains(const BasicBlock *B) const {
     && !(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;
@@ -92,14 +136,16 @@ bool Region::isSimple() const {
     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;
 
@@ -116,6 +162,32 @@ bool Region::isSimple() const {
   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!");
@@ -315,10 +387,11 @@ void Region::clearNodeCache() {
 
 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;
 }
 
@@ -326,7 +399,7 @@ bool RegionInfo::isRegion(BasicBlock *entry, BasicBlock *exit) const {
   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.
@@ -339,7 +412,7 @@ bool RegionInfo::isRegion(BasicBlock *entry, BasicBlock *exit) const {
     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();
@@ -355,7 +428,7 @@ bool RegionInfo::isRegion(BasicBlock *entry, BasicBlock *exit) const {
   // 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;
 
 
@@ -477,7 +550,7 @@ void RegionInfo::scanForRegions(Function &F, BBtoBBMap *ShortCut) {
   // 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);
   }
 }
 
@@ -518,7 +591,7 @@ void RegionInfo::releaseMemory() {
   TopLevelRegion = 0;
 }
 
-RegionInfo::RegionInfo() : FunctionPass(&ID) {
+RegionInfo::RegionInfo() : FunctionPass(ID) {
   TopLevelRegion = 0;
 }
 
@@ -585,6 +658,45 @@ Region *RegionInfo::operator[](BasicBlock *BB) const {
   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");