X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FRegionInfo.cpp;h=857702570f2f8bd8ee55f1189e35c3a6397dab1e;hb=318b7cc7f10d41370929ff93274de29c11f87b81;hp=0bf6aad48a8d4f3c416eb6b8f0e2f5eef770a4cc;hpb=4bcc0228dcc90385e90f22cef38b2614d3aa3cd1;p=oota-llvm.git diff --git a/lib/Analysis/RegionInfo.cpp b/lib/Analysis/RegionInfo.cpp index 0bf6aad48a8..857702570f2 100644 --- a/lib/Analysis/RegionInfo.cpp +++ b/lib/Analysis/RegionInfo.cpp @@ -10,14 +10,13 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/RegionInfo.h" -#include "llvm/Analysis/RegionIterator.h" - #include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/RegionIterator.h" +#include "llvm/Assembly/Writer.h" #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" @@ -41,16 +40,15 @@ VerifyRegionInfoX("verify-region-info", cl::location(VerifyRegionInfo), STATISTIC(numRegions, "The # of regions"); STATISTIC(numSimpleRegions, "The # of simple regions"); -//===----------------------------------------------------------------------===// -/// PrintStyle - Print region in difference ways. -enum PrintStyle { PrintNone, PrintBB, PrintRN }; - -cl::opt printStyle("print-region-style", cl::Hidden, +static cl::opt printStyle("print-region-style", + cl::Hidden, cl::desc("style of printing regions"), cl::values( - clEnumValN(PrintNone, "none", "print no details"), - clEnumValN(PrintBB, "bb", "print regions in detail with block_iterator"), - clEnumValN(PrintRN, "rn", "print regions in detail with element_iterator"), + clEnumValN(Region::PrintNone, "none", "print no details"), + clEnumValN(Region::PrintBB, "bb", + "print regions in detail with block_iterator"), + clEnumValN(Region::PrintRN, "rn", + "print regions in detail with element_iterator"), clEnumValEnd)); //===----------------------------------------------------------------------===// /// Region Implementation @@ -81,10 +79,43 @@ void Region::replaceExit(BasicBlock *BB) { exit = BB; } +void Region::replaceEntryRecursive(BasicBlock *NewEntry) { + std::vector RegionQueue; + BasicBlock *OldEntry = getEntry(); + + RegionQueue.push_back(this); + while (!RegionQueue.empty()) { + Region *R = RegionQueue.back(); + RegionQueue.pop_back(); + + R->replaceEntry(NewEntry); + for (Region::const_iterator RI = R->begin(), RE = R->end(); RI != RE; ++RI) + if ((*RI)->getEntry() == OldEntry) + RegionQueue.push_back(*RI); + } +} + +void Region::replaceExitRecursive(BasicBlock *NewExit) { + std::vector RegionQueue; + BasicBlock *OldExit = getExit(); + + RegionQueue.push_back(this); + while (!RegionQueue.empty()) { + Region *R = RegionQueue.back(); + RegionQueue.pop_back(); + + R->replaceExit(NewExit); + for (Region::const_iterator RI = R->begin(), RE = R->end(); RI != RE; ++RI) + if ((*RI)->getExit() == OldExit) + RegionQueue.push_back(*RI); + } +} + bool Region::contains(const BasicBlock *B) const { BasicBlock *BB = const_cast(B); - assert(DT->getNode(BB) && "BB not part of the dominance tree"); + if (!DT->getNode(BB)) + return false; BasicBlock *entry = getEntry(), *exit = getExit(); @@ -134,41 +165,49 @@ Loop *Region::outermostLoopInRegion(LoopInfo *LI, BasicBlock* BB) const { return outermostLoopInRegion(L); } -bool Region::isSimple() const { - bool isSimple = true; - bool found = false; - - BasicBlock *entry = getEntry(), *exit = getExit(); - - // TopLevelRegion - if (!exit) - return false; +BasicBlock *Region::getEnteringBlock() const { + BasicBlock *entry = getEntry(); + BasicBlock *Pred; + BasicBlock *enteringBlock = 0; for (pred_iterator PI = pred_begin(entry), PE = pred_end(entry); PI != PE; ++PI) { - BasicBlock *Pred = *PI; + Pred = *PI; if (DT->getNode(Pred) && !contains(Pred)) { - if (found) { - isSimple = false; - break; - } - found = true; + if (enteringBlock) + return 0; + + enteringBlock = Pred; } } - found = false; + return enteringBlock; +} + +BasicBlock *Region::getExitingBlock() const { + BasicBlock *exit = getExit(); + BasicBlock *Pred; + BasicBlock *exitingBlock = 0; + + if (!exit) + return 0; for (pred_iterator PI = pred_begin(exit), PE = pred_end(exit); PI != PE; - ++PI) - if (contains(*PI)) { - if (found) { - isSimple = false; - break; - } - found = true; + ++PI) { + Pred = *PI; + if (contains(Pred)) { + if (exitingBlock) + return 0; + + exitingBlock = Pred; } + } - return isSimple; + return exitingBlock; +} + +bool Region::isSimple() const { + return !isTopLevelRegion() && getEnteringBlock() && getExitingBlock(); } std::string Region::getNameStr() const { @@ -179,18 +218,16 @@ std::string Region::getNameStr() const { raw_string_ostream OS(entryName); WriteAsOperand(OS, getEntry(), false); - entryName = OS.str(); } else - entryName = getEntry()->getNameStr(); + entryName = getEntry()->getName(); if (getExit()) { if (getExit()->getName().empty()) { raw_string_ostream OS(exitName); WriteAsOperand(OS, getExit(), false); - exitName = OS.str(); } else - exitName = getExit()->getNameStr(); + exitName = getExit()->getName(); } else exitName = ""; @@ -241,22 +278,6 @@ void Region::verifyRegionNest() const { verifyRegion(); } -Region::block_iterator Region::block_begin() { - return GraphTraits >::nodes_begin(this); -} - -Region::block_iterator Region::block_end() { - return GraphTraits >::nodes_end(this); -} - -Region::const_block_iterator Region::block_begin() const { - return GraphTraits >::nodes_begin(this); -} - -Region::const_block_iterator Region::block_end() const { - return GraphTraits >::nodes_end(this); -} - Region::element_iterator Region::element_begin() { return GraphTraits::nodes_begin(this); } @@ -373,7 +394,40 @@ unsigned Region::getDepth() const { return Depth; } -void Region::print(raw_ostream &OS, bool print_tree, unsigned level) const { +Region *Region::getExpandedRegion() const { + unsigned NumSuccessors = exit->getTerminator()->getNumSuccessors(); + + if (NumSuccessors == 0) + return NULL; + + for (pred_iterator PI = pred_begin(getExit()), PE = pred_end(getExit()); + PI != PE; ++PI) + if (!DT->dominates(getEntry(), *PI)) + return NULL; + + Region *R = RI->getRegionFor(exit); + + if (R->getEntry() != exit) { + if (exit->getTerminator()->getNumSuccessors() == 1) + return new Region(getEntry(), *succ_begin(exit), RI, DT); + else + return NULL; + } + + while (R->getParent() && R->getParent()->getEntry() == exit) + R = R->getParent(); + + if (!DT->dominates(getEntry(), R->getExit())) + for (pred_iterator PI = pred_begin(getExit()), PE = pred_end(getExit()); + PI != PE; ++PI) + if (!DT->dominates(R->getExit(), *PI)) + return NULL; + + return new Region(getEntry(), R->getExit(), RI, DT); +} + +void Region::print(raw_ostream &OS, bool print_tree, unsigned level, + enum PrintStyle Style) const { if (print_tree) OS.indent(level*2) << "[" << level << "] " << getNameStr(); else @@ -382,14 +436,14 @@ void Region::print(raw_ostream &OS, bool print_tree, unsigned level) const { OS << "\n"; - if (printStyle != PrintNone) { + if (Style != PrintNone) { OS.indent(level*2) << "{\n"; OS.indent(level*2 + 2); - if (printStyle == PrintBB) { - for (const_block_iterator I = block_begin(), E = block_end(); I!=E; ++I) - OS << **I << ", "; // TODO: remove the last "," - } else if (printStyle == PrintRN) { + if (Style == PrintBB) { + for (const_block_iterator I = block_begin(), E = block_end(); I != E; ++I) + OS << (*I)->getName() << ", "; // TODO: remove the last "," + } else if (Style == PrintRN) { for (const_element_iterator I = element_begin(), E = element_end(); I!=E; ++I) OS << **I << ", "; // TODO: remove the last ", } @@ -399,20 +453,22 @@ void Region::print(raw_ostream &OS, bool print_tree, unsigned level) const { if (print_tree) for (const_iterator RI = begin(), RE = end(); RI != RE; ++RI) - (*RI)->print(OS, print_tree, level+1); + (*RI)->print(OS, print_tree, level+1, Style); - if (printStyle != PrintNone) + if (Style != PrintNone) OS.indent(level*2) << "} \n"; } +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) void Region::dump() const { - print(dbgs(), true, getDepth()); + print(dbgs(), true, getDepth(), printStyle.getValue()); } +#endif void Region::clearNodeCache() { // Free the cached nodes. for (BBNodeMapT::iterator I = BBNodeMap.begin(), - IE = BBNodeMap.end(); I != IE; ++IE) + IE = BBNodeMap.end(); I != IE; ++I) delete I->second; BBNodeMap.clear(); @@ -612,7 +668,7 @@ void RegionInfo::buildRegionsTree(DomTreeNode *N, Region *region) { // This basic block is a start block of a region. It is already in the // BBtoRegion relation. Only the child basic blocks have to be updated. if (it != BBtoRegion.end()) { - Region *newRegion = it->second;; + Region *newRegion = it->second; region->addSubRegion(getTopMostParent(newRegion)); region = newRegion; } else { @@ -631,6 +687,7 @@ void RegionInfo::releaseMemory() { } RegionInfo::RegionInfo() : FunctionPass(ID) { + initializeRegionInfoPass(*PassRegistry::getPassRegistry()); TopLevelRegion = 0; } @@ -673,7 +730,7 @@ void RegionInfo::getAnalysisUsage(AnalysisUsage &AU) const { void RegionInfo::print(raw_ostream &OS, const Module *) const { OS << "Region tree:\n"; - TopLevelRegion->print(OS, true, 0); + TopLevelRegion->print(OS, true, 0, printStyle.getValue()); OS << "End region tree\n"; } @@ -775,6 +832,20 @@ RegionInfo::getCommonRegion(SmallVectorImpl &BBs) const { return ret; } +void RegionInfo::splitBlock(BasicBlock* NewBB, BasicBlock *OldBB) +{ + Region *R = getRegionFor(OldBB); + + setRegionFor(NewBB, R); + + while (R->getEntry() == OldBB && !R->isTopLevelRegion()) { + R->replaceEntry(NewBB); + R = R->getParent(); + } + + setRegionFor(OldBB, R); +} + char RegionInfo::ID = 0; INITIALIZE_PASS_BEGIN(RegionInfo, "regions", "Detect single entry single exit regions", true, true)