X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FRegionInfo.cpp;h=fad5074086ce6c4e324e03e181fe77f6a8f036eb;hb=d1b8ef97c47d347f2a2261a0d6de4872f248321f;hp=27cee76e081cf47ec975eaded15a2d472f9426ea;hpb=9ccaf53ada99c63737547c0235baeb8454b04e80;p=oota-llvm.git diff --git a/lib/Analysis/RegionInfo.cpp b/lib/Analysis/RegionInfo.cpp index 27cee76e081..fad5074086c 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 @@ -72,6 +70,15 @@ Region::~Region() { delete *I; } +void Region::replaceEntry(BasicBlock *BB) { + entry.setPointer(BB); +} + +void Region::replaceExit(BasicBlock *BB) { + assert(exit && "No exit to replace!"); + exit = BB; +} + bool Region::contains(const BasicBlock *B) const { BasicBlock *BB = const_cast(B); @@ -125,39 +132,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) - if (!contains(*PI)) { - if (found) { - isSimple = false; - break; - } - found = true; + ++PI) { + Pred = *PI; + if (DT->getNode(Pred) && !contains(Pred)) { + if (enteringBlock) + return 0; + + enteringBlock = Pred; } + } + + return enteringBlock; +} + +BasicBlock *Region::getExitingBlock() const { + BasicBlock *exit = getExit(); + BasicBlock *Pred; + BasicBlock *exitingBlock = 0; - found = false; + 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 { @@ -168,18 +185,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 = ""; @@ -230,22 +245,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); } @@ -309,13 +308,38 @@ void Region::transferChildrenTo(Region *To) { children.clear(); } -void Region::addSubRegion(Region *SubRegion) { +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!"); + SubRegion->parent = this; - // Set up the region node. - assert(std::find(children.begin(), children.end(), SubRegion) == children.end() - && "Node already exist!"); children.push_back(SubRegion); + + if (!moveChildren) + return; + + assert(SubRegion->children.size() == 0 + && "SubRegions that contain children are not supported"); + + for (element_iterator I = element_begin(), E = element_end(); I != E; ++I) + if (!(*I)->isSubRegion()) { + BasicBlock *BB = (*I)->getNodeAs(); + + if (SubRegion->contains(BB)) + RI->setRegionFor(BB, SubRegion); + } + + std::vector Keep; + for (iterator I = begin(), E = end(); I != E; ++I) + if (SubRegion->contains(*I) && *I != SubRegion) { + SubRegion->children.push_back(*I); + (*I)->parent = SubRegion; + } else + Keep.push_back(*I); + + children.clear(); + children.insert(children.begin(), Keep.begin(), Keep.end()); } @@ -337,7 +361,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 @@ -346,14 +403,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 ", } @@ -363,17 +420,24 @@ 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; ++I) + delete I->second; + BBNodeMap.clear(); for (Region::iterator RI = begin(), RE = end(); RI != RE; ++RI) (*RI)->clearNodeCache(); @@ -571,7 +635,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 { @@ -590,6 +654,7 @@ void RegionInfo::releaseMemory() { } RegionInfo::RegionInfo() : FunctionPass(ID) { + initializeRegionInfoPass(*PassRegistry::getPassRegistry()); TopLevelRegion = 0; } @@ -632,7 +697,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"; } @@ -652,11 +717,14 @@ Region *RegionInfo::getRegionFor(BasicBlock *BB) const { return I != BBtoRegion.end() ? I->second : 0; } +void RegionInfo::setRegionFor(BasicBlock *BB, Region *R) { + BBtoRegion[BB] = R; +} + Region *RegionInfo::operator[](BasicBlock *BB) const { return getRegionFor(BB); } - BasicBlock *RegionInfo::getMaxRegionExit(BasicBlock *BB) const { BasicBlock *Exit = NULL; @@ -731,9 +799,28 @@ 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(RegionInfo, "regions", - "Detect single entry single exit regions", true, true); +INITIALIZE_PASS_BEGIN(RegionInfo, "regions", + "Detect single entry single exit regions", true, true) +INITIALIZE_PASS_DEPENDENCY(DominatorTree) +INITIALIZE_PASS_DEPENDENCY(PostDominatorTree) +INITIALIZE_PASS_DEPENDENCY(DominanceFrontier) +INITIALIZE_PASS_END(RegionInfo, "regions", + "Detect single entry single exit regions", true, true) // Create methods available outside of this file, to use them // "include/llvm/LinkAllPasses.h". Otherwise the pass would be deleted by