-//===----------------------------------------------------------------------===//
-/// Region Implementation
-Region::Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo* RInfo,
- DominatorTree *dt, Region *Parent)
- : 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();
-
- for (iterator I = begin(), E = end(); I != E; ++I)
- delete *I;
-}
-
-bool Region::contains(const BasicBlock *B) const {
- BasicBlock *BB = const_cast<BasicBlock*>(B);
-
- assert(DT->getNode(BB) && "BB not part of the dominance tree");
-
- BasicBlock *entry = getEntry(), *exit = getExit();
-
- // Toplevel region.
- if (!exit)
- return true;
-
- return (DT->dominates(entry, BB)
- && !(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;
-
- BasicBlock *entry = getEntry(), *exit = getExit();
-
- // TopLevelRegion
- if (!exit)
- return false;
-
- for (pred_iterator PI = pred_begin(entry), PE = pred_end(entry); PI != PE;
- ++PI) {
- BasicBlock *Pred = *PI;
- if (DT->getNode(Pred) && !contains(Pred)) {
- if (found) {
- isSimple = false;
- break;
- }
- found = true;
- }
- }
-
- found = false;
-
- for (pred_iterator PI = pred_begin(exit), PE = pred_end(exit); PI != PE;
- ++PI)
- if (contains(*PI)) {
- if (found) {
- isSimple = false;
- break;
- }
- found = true;
- }
-
- 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!");
-
- BasicBlock *entry = getEntry(), *exit = getExit();
-
- for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
- if (!contains(*SI) && exit != *SI)
- llvm_unreachable("Broken region found!");
-
- if (entry != BB)
- for (pred_iterator SI = pred_begin(BB), SE = pred_end(BB); SI != SE; ++SI)
- if (!contains(*SI))
- llvm_unreachable("Broken region found!");
-}
-
-void Region::verifyWalk(BasicBlock *BB, std::set<BasicBlock*> *visited) const {
- BasicBlock *exit = getExit();
-
- visited->insert(BB);
-
- verifyBBInRegion(BB);
-
- for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
- if (*SI != exit && visited->find(*SI) == visited->end())
- verifyWalk(*SI, visited);
-}
-
-void Region::verifyRegion() const {
- // Only do verification when user wants to, otherwise this expensive
- // check will be invoked by PassManager.
- if (!VerifyRegionInfo) return;
-
- std::set<BasicBlock*> visited;
- verifyWalk(getEntry(), &visited);
-}
-
-void Region::verifyRegionNest() const {
- for (Region::const_iterator RI = begin(), RE = end(); RI != RE; ++RI)
- (*RI)->verifyRegionNest();
-
- 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::element_iterator Region::element_end() {
- return GraphTraits<Region*>::nodes_end(this);
-}
-
-Region::const_element_iterator Region::element_begin() const {
- return GraphTraits<const Region*>::nodes_begin(this);
-}
-
-Region::const_element_iterator Region::element_end() const {
- return GraphTraits<const Region*>::nodes_end(this);
-}
-
-Region* Region::getSubRegionNode(BasicBlock *BB) const {
- Region *R = RI->getRegionFor(BB);
-
- if (!R || R == this)
- return 0;
-
- // If we pass the BB out of this region, that means our code is broken.
- assert(contains(R) && "BB not in current region!");
-
- while (contains(R->getParent()) && R->getParent() != this)
- R = R->getParent();
-
- if (R->getEntry() != BB)
- return 0;
-
- return R;
-}
-
-RegionNode* Region::getBBNode(BasicBlock *BB) const {
- assert(contains(BB) && "Can get BB node out of this region!");
-
- BBNodeMapT::const_iterator at = BBNodeMap.find(BB);
-
- if (at != BBNodeMap.end())
- return at->second;
-
- RegionNode *NewNode = new RegionNode(const_cast<Region*>(this), BB);
- BBNodeMap.insert(std::make_pair(BB, NewNode));
- return NewNode;
-}
-
-RegionNode* Region::getNode(BasicBlock *BB) const {
- assert(contains(BB) && "Can get BB node out of this region!");
- if (Region* Child = getSubRegionNode(BB))
- return Child->getNode();
-
- return getBBNode(BB);
-}
-
-void Region::transferChildrenTo(Region *To) {
- for (iterator I = begin(), E = end(); I != E; ++I) {
- (*I)->parent = To;
- To->children.push_back(*I);
- }
- children.clear();
-}
-
-void Region::addSubRegion(Region *SubRegion) {
- assert(SubRegion->parent == 0 && "SubRegion already has a parent!");
- 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);
-}
-
-
-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);
- 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)
- ++Depth;
-
- return Depth;
-}
-
-void Region::print(raw_ostream &OS, bool print_tree, unsigned level) const {
- if (print_tree)
- OS.indent(level*2) << "[" << level << "] " << getNameStr();
- else
- OS.indent(level*2) << getNameStr();
-
- OS << "\n";
-