//===----------------------------------------------------------------------===//
#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 <set>
+#include "llvm/Support/ErrorHandling.h"
#include <algorithm>
+#include <iterator>
+#include <set>
using namespace llvm;
+#define DEBUG_TYPE "region"
+
// Always verify if expensive checking is enabled.
#ifdef XDEBUG
static bool VerifyRegionInfo = true;
STATISTIC(numRegions, "The # of regions");
STATISTIC(numSimpleRegions, "The # of simple regions");
-//===----------------------------------------------------------------------===//
-/// PrintStyle - Print region in difference ways.
-enum PrintStyle { PrintNone, PrintBB, PrintRN };
-
-cl::opt<enum PrintStyle> printStyle("print-region-style", cl::Hidden,
+static cl::opt<enum Region::PrintStyle> 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
// 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) {
+ entry.setPointer(BB);
+}
+
+void Region::replaceExit(BasicBlock *BB) {
+ assert(exit && "No exit to replace!");
+ exit = BB;
+}
+
+void Region::replaceEntryRecursive(BasicBlock *NewEntry) {
+ std::vector<Region *> 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<Region *> 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<BasicBlock*>(B);
- assert(DT->getNode(BB) && "BB not part of the dominance tree");
+ if (!DT->getNode(BB))
+ return false;
BasicBlock *entry = getEntry(), *exit = getExit();
// 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;
Loop *Region::outermostLoopInRegion(Loop *L) const {
if (!contains(L))
- return 0;
+ return nullptr;
while (L && contains(L->getParentLoop())) {
L = L->getParentLoop();
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 exitingBlock;
+}
- return isSimple;
+bool Region::isSimple() const {
+ return !isTopLevelRegion() && getEnteringBlock() && getExitingBlock();
}
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 = "<Function Return>";
verifyRegion();
}
-Region::block_iterator Region::block_begin() {
- return GraphTraits<FlatIt<Region*> >::nodes_begin(this);
-}
-
-Region::block_iterator Region::block_end() {
- return GraphTraits<FlatIt<Region*> >::nodes_end(this);
-}
-
-Region::const_block_iterator Region::block_begin() const {
- return GraphTraits<FlatIt<const Region*> >::nodes_begin(this);
-}
-
-Region::const_block_iterator Region::block_end() const {
- return GraphTraits<FlatIt<const Region*> >::nodes_end(this);
-}
-
Region::element_iterator Region::element_begin() {
return GraphTraits<Region*>::nodes_begin(this);
}
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!");
R = R->getParent();
if (R->getEntry() != BB)
- return 0;
+ return nullptr;
return R;
}
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) {
- assert(SubRegion->parent == 0 && "SubRegion already has a parent!");
+void Region::addSubRegion(Region *SubRegion, bool moveChildren) {
+ assert(!SubRegion->parent && "SubRegion already has a parent!");
+ assert(std::find_if(begin(), end(), [&](const std::unique_ptr<Region> &R) {
+ return R.get() == 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);
+ children.push_back(std::unique_ptr<Region>(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<BasicBlock>();
+
+ if (SubRegion->contains(BB))
+ RI->setRegionFor(BB, SubRegion);
+ }
+
+ std::vector<std::unique_ptr<Region>> Keep;
+ for (iterator I = begin(), E = end(); I != E; ++I)
+ if (SubRegion->contains(I->get()) && I->get() != SubRegion) {
+ (*I)->parent = SubRegion;
+ SubRegion->children.push_back(std::move(*I));
+ } else
+ Keep.push_back(std::move(*I));
+
+ children.clear();
+ children.insert(children.begin(),
+ std::move_iterator<RegionSet::iterator>(Keep.begin()),
+ std::move_iterator<RegionSet::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<Region> &R) { return R.get() == Child; });
assert(I != children.end() && "Region does not exit. Unable to remove.");
children.erase(children.begin()+(I-begin()));
return 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
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 ",
}
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();
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));
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
// 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 {
BBtoRegion.clear();
if (TopLevelRegion)
delete TopLevelRegion;
- TopLevelRegion = 0;
+ TopLevelRegion = nullptr;
}
RegionInfo::RegionInfo() : FunctionPass(ID) {
- TopLevelRegion = 0;
+ initializeRegionInfoPass(*PassRegistry::getPassRegistry());
+ TopLevelRegion = nullptr;
}
RegionInfo::~RegionInfo() {
bool RegionInfo::runOnFunction(Function &F) {
releaseMemory();
- DT = &getAnalysis<DominatorTree>();
+ DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
PDT = &getAnalysis<PostDominatorTree>();
DF = &getAnalysis<DominanceFrontier>();
- TopLevelRegion = new Region(&F.getEntryBlock(), 0, this, DT, 0);
+ TopLevelRegion = new Region(&F.getEntryBlock(), nullptr, this, DT, nullptr);
updateStatistics(TopLevelRegion);
Calculate(F);
void RegionInfo::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
- AU.addRequiredTransitive<DominatorTree>();
+ AU.addRequiredTransitive<DominatorTreeWrapperPass>();
AU.addRequired<PostDominatorTree>();
AU.addRequired<DominanceFrontier>();
}
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";
}
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) {
+ BBtoRegion[BB] = R;
}
Region *RegionInfo::operator[](BasicBlock *BB) const {
return getRegionFor(BB);
}
-
BasicBlock *RegionInfo::getMaxRegionExit(BasicBlock *BB) const {
- BasicBlock *Exit = NULL;
+ BasicBlock *Exit = nullptr;
while (true) {
// Get largest region that starts at BB.
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",
projects / oota-llvm.git / blobdiff