X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FRegionInfo.cpp;h=7f88ae125019a410fdba6741b12d103ba8e508ec;hb=6f1f9f4c7f8a5de44c2bcd610fa909f17860fbd1;hp=0bf6aad48a8d4f3c416eb6b8f0e2f5eef770a4cc;hpb=4bcc0228dcc90385e90f22cef38b2614d3aa3cd1;p=oota-llvm.git diff --git a/lib/Analysis/RegionInfo.cpp b/lib/Analysis/RegionInfo.cpp index 0bf6aad48a8..7f88ae12501 100644 --- a/lib/Analysis/RegionInfo.cpp +++ b/lib/Analysis/RegionInfo.cpp @@ -10,23 +10,21 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/RegionInfo.h" -#include "llvm/Analysis/RegionIterator.h" - #include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/Statistic.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/Analysis/RegionIterator.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" - -#include +#include "llvm/Support/ErrorHandling.h" #include +#include +#include using namespace llvm; +#define DEBUG_TYPE "region" + // Always verify if expensive checking is enabled. #ifdef XDEBUG static bool VerifyRegionInfo = true; @@ -41,16 +39,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 @@ -67,9 +64,6 @@ Region::~Region() { // Only clean the cache for this Region. Caches of child Regions will be // cleaned when the child Regions are deleted. BBNodeMap.clear(); - - for (iterator I = begin(), E = end(); I != E; ++I) - delete *I; } void Region::replaceEntry(BasicBlock *BB) { @@ -81,10 +75,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->get()); + } +} + +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->get()); + } +} + 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(); @@ -100,8 +127,8 @@ 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 (!L) + return getExit() == nullptr; if (!contains(L->getHeader())) return false; @@ -119,7 +146,7 @@ bool Region::contains(const Loop *L) const { Loop *Region::outermostLoopInRegion(Loop *L) const { if (!contains(L)) - return 0; + return nullptr; while (L && contains(L->getParentLoop())) { L = L->getParentLoop(); @@ -134,41 +161,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 = nullptr; 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 nullptr; + + enteringBlock = Pred; } } - found = false; + return enteringBlock; +} + +BasicBlock *Region::getExitingBlock() const { + BasicBlock *exit = getExit(); + BasicBlock *Pred; + BasicBlock *exitingBlock = nullptr; + + if (!exit) + return nullptr; 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 nullptr; + + exitingBlock = Pred; } + } - return isSimple; + return exitingBlock; +} + +bool Region::isSimple() const { + return !isTopLevelRegion() && getEnteringBlock() && getExitingBlock(); } std::string Region::getNameStr() const { @@ -178,19 +213,17 @@ std::string Region::getNameStr() const { if (getEntry()->getName().empty()) { raw_string_ostream OS(entryName); - WriteAsOperand(OS, getEntry(), false); - entryName = OS.str(); + getEntry()->printAsOperand(OS, false); } 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(); + getExit()->printAsOperand(OS, false); } else - exitName = getExit()->getNameStr(); + exitName = getExit()->getName(); } else exitName = ""; @@ -241,22 +274,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); } @@ -277,7 +294,7 @@ Region* Region::getSubRegionNode(BasicBlock *BB) const { Region *R = RI->getRegionFor(BB); if (!R || R == this) - return 0; + return nullptr; // If we pass the BB out of this region, that means our code is broken. assert(contains(R) && "BB not in current region!"); @@ -286,7 +303,7 @@ Region* Region::getSubRegionNode(BasicBlock *BB) const { R = R->getParent(); if (R->getEntry() != BB) - return 0; + return nullptr; return R; } @@ -315,18 +332,20 @@ RegionNode* Region::getNode(BasicBlock *BB) const { void Region::transferChildrenTo(Region *To) { for (iterator I = begin(), E = end(); I != E; ++I) { (*I)->parent = To; - To->children.push_back(*I); + To->children.push_back(std::move(*I)); } children.clear(); } void Region::addSubRegion(Region *SubRegion, bool moveChildren) { - assert(SubRegion->parent == 0 && "SubRegion already has a parent!"); - assert(std::find(begin(), end(), SubRegion) == children.end() - && "Subregion already exists!"); + assert(!SubRegion->parent && "SubRegion already has a parent!"); + assert(std::find_if(begin(), end(), [&](const std::unique_ptr &R) { + return R.get() == SubRegion; + }) == children.end() && + "Subregion already exists!"); SubRegion->parent = this; - children.push_back(SubRegion); + children.push_back(std::unique_ptr(SubRegion)); if (!moveChildren) return; @@ -342,23 +361,27 @@ void Region::addSubRegion(Region *SubRegion, bool moveChildren) { RI->setRegionFor(BB, SubRegion); } - std::vector Keep; + std::vector> Keep; for (iterator I = begin(), E = end(); I != E; ++I) - if (SubRegion->contains(*I) && *I != SubRegion) { - SubRegion->children.push_back(*I); + if (SubRegion->contains(I->get()) && I->get() != SubRegion) { (*I)->parent = SubRegion; + SubRegion->children.push_back(std::move(*I)); } else - Keep.push_back(*I); + Keep.push_back(std::move(*I)); children.clear(); - children.insert(children.begin(), Keep.begin(), Keep.end()); + children.insert(children.begin(), + std::move_iterator(Keep.begin()), + std::move_iterator(Keep.end())); } Region *Region::removeSubRegion(Region *Child) { assert(Child->parent == this && "Child is not a child of this region!"); - Child->parent = 0; - RegionSet::iterator I = std::find(children.begin(), children.end(), Child); + Child->parent = nullptr; + RegionSet::iterator I = std::find_if( + children.begin(), children.end(), + [&](const std::unique_ptr &R) { return R.get() == Child; }); assert(I != children.end() && "Region does not exit. Unable to remove."); children.erase(children.begin()+(I-begin())); return Child; @@ -367,13 +390,46 @@ Region *Region::removeSubRegion(Region *Child) { unsigned Region::getDepth() const { unsigned Depth = 0; - for (Region *R = parent; R != 0; R = R->parent) + for (Region *R = parent; R != nullptr; R = R->parent) ++Depth; 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 nullptr; + + for (pred_iterator PI = pred_begin(getExit()), PE = pred_end(getExit()); + PI != PE; ++PI) + if (!DT->dominates(getEntry(), *PI)) + return nullptr; + + 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 nullptr; + } + + 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 nullptr; + + 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 +438,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 auto &BB : blocks()) + OS << BB->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 +455,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(); @@ -524,7 +582,7 @@ Region *RegionInfo::createRegion(BasicBlock *entry, BasicBlock *exit) { assert(entry && exit && "entry and exit must not be null!"); if (isTrivialRegion(entry, exit)) - return 0; + return nullptr; Region *region = new Region(entry, exit, this, DT); BBtoRegion.insert(std::make_pair(entry, region)); @@ -547,7 +605,7 @@ void RegionInfo::findRegionsWithEntry(BasicBlock *entry, BBtoBBMap *ShortCut) { if (!N) return; - Region *lastRegion= 0; + Region *lastRegion= nullptr; BasicBlock *lastExit = entry; // As only a BasicBlock that postdominates entry can finish a region, walk the @@ -612,7 +670,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 { @@ -627,11 +685,12 @@ void RegionInfo::releaseMemory() { BBtoRegion.clear(); if (TopLevelRegion) delete TopLevelRegion; - TopLevelRegion = 0; + TopLevelRegion = nullptr; } RegionInfo::RegionInfo() : FunctionPass(ID) { - TopLevelRegion = 0; + initializeRegionInfoPass(*PassRegistry::getPassRegistry()); + TopLevelRegion = nullptr; } RegionInfo::~RegionInfo() { @@ -652,11 +711,11 @@ void RegionInfo::Calculate(Function &F) { bool RegionInfo::runOnFunction(Function &F) { releaseMemory(); - DT = &getAnalysis(); + DT = &getAnalysis().getDomTree(); PDT = &getAnalysis(); DF = &getAnalysis(); - TopLevelRegion = new Region(&F.getEntryBlock(), 0, this, DT, 0); + TopLevelRegion = new Region(&F.getEntryBlock(), nullptr, this, DT, nullptr); updateStatistics(TopLevelRegion); Calculate(F); @@ -666,14 +725,14 @@ bool RegionInfo::runOnFunction(Function &F) { void RegionInfo::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); - AU.addRequiredTransitive(); + AU.addRequiredTransitive(); AU.addRequired(); AU.addRequired(); } 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"; } @@ -690,7 +749,7 @@ void RegionInfo::verifyAnalysis() const { Region *RegionInfo::getRegionFor(BasicBlock *BB) const { BBtoRegionMap::const_iterator I= BBtoRegion.find(BB); - return I != BBtoRegion.end() ? I->second : 0; + return I != BBtoRegion.end() ? I->second : nullptr; } void RegionInfo::setRegionFor(BasicBlock *BB, Region *R) { @@ -702,7 +761,7 @@ Region *RegionInfo::operator[](BasicBlock *BB) const { } BasicBlock *RegionInfo::getMaxRegionExit(BasicBlock *BB) const { - BasicBlock *Exit = NULL; + BasicBlock *Exit = nullptr; while (true) { // Get largest region that starts at BB. @@ -775,10 +834,24 @@ 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) -INITIALIZE_PASS_DEPENDENCY(DominatorTree) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(PostDominatorTree) INITIALIZE_PASS_DEPENDENCY(DominanceFrontier) INITIALIZE_PASS_END(RegionInfo, "regions",