-//===----------------------------------------------------------------------===//
-/// 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() {
- // 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::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)
- if (!contains(*PI)) {
- 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;
-}
-
-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";
-
-
- if (printStyle != 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) {
- for (const_element_iterator I = element_begin(), E = element_end(); I!=E; ++I)
- OS << **I << ", "; // TODO: remove the last ",
- }