137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines//===- RegionInfoImpl.h - SESE region detection analysis --------*- C++ -*-===// 237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// 337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// The LLVM Compiler Infrastructure 437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// 537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// This file is distributed under the University of Illinois Open Source 637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// License. See LICENSE.TXT for details. 737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// 837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines//===----------------------------------------------------------------------===// 937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// Detects single entry single exit regions in the control flow graph. 1037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines//===----------------------------------------------------------------------===// 1137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 1237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#ifndef LLVM_ANALYSIS_REGIONINFOIMPL_H 1337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#define LLVM_ANALYSIS_REGIONINFOIMPL_H 1437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 1537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include "llvm/ADT/PostOrderIterator.h" 1637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include "llvm/Analysis/DominanceFrontier.h" 1737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include "llvm/Analysis/LoopInfo.h" 1837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include "llvm/Analysis/PostDominators.h" 19ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/Analysis/RegionInfo.h" 2037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include "llvm/Analysis/RegionIterator.h" 2137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include "llvm/Support/Debug.h" 2237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include "llvm/Support/ErrorHandling.h" 2337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include <algorithm> 2437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include <iterator> 2537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include <set> 2637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 2737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesnamespace llvm { 2837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 2937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#define DEBUG_TYPE "region" 3037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 3137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines//===----------------------------------------------------------------------===// 3237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// RegionBase Implementation 3337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 3437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen HinesRegionBase<Tr>::RegionBase(BlockT *Entry, BlockT *Exit, 3537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typename Tr::RegionInfoT *RInfo, DomTreeT *dt, 3637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *Parent) 3737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines : RegionNodeBase<Tr>(Parent, Entry, 1), RI(RInfo), DT(dt), exit(Exit) {} 3837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 3937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 4037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen HinesRegionBase<Tr>::~RegionBase() { 4137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Free the cached nodes. 4237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (typename BBNodeMapT::iterator it = BBNodeMap.begin(), 4337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines ie = BBNodeMap.end(); 4437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines it != ie; ++it) 4537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines delete it->second; 4637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 4737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Only clean the cache for this Region. Caches of child Regions will be 4837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // cleaned when the child Regions are deleted. 4937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BBNodeMap.clear(); 5037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 5137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 5237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 5337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesvoid RegionBase<Tr>::replaceEntry(BlockT *BB) { 5437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines this->entry.setPointer(BB); 5537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 5637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 5737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 5837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesvoid RegionBase<Tr>::replaceExit(BlockT *BB) { 5937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(exit && "No exit to replace!"); 6037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines exit = BB; 6137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 6237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 6337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 6437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesvoid RegionBase<Tr>::replaceEntryRecursive(BlockT *NewEntry) { 6537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines std::vector<RegionT *> RegionQueue; 6637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *OldEntry = getEntry(); 6737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 6837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionQueue.push_back(static_cast<RegionT *>(this)); 6937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines while (!RegionQueue.empty()) { 7037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *R = RegionQueue.back(); 7137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionQueue.pop_back(); 7237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 7337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines R->replaceEntry(NewEntry); 7437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (typename RegionT::const_iterator RI = R->begin(), RE = R->end(); 7537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RI != RE; ++RI) { 7637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if ((*RI)->getEntry() == OldEntry) 7737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionQueue.push_back(RI->get()); 7837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 7937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 8037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 8137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 8237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 8337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesvoid RegionBase<Tr>::replaceExitRecursive(BlockT *NewExit) { 8437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines std::vector<RegionT *> RegionQueue; 8537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *OldExit = getExit(); 8637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 8737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionQueue.push_back(static_cast<RegionT *>(this)); 8837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines while (!RegionQueue.empty()) { 8937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *R = RegionQueue.back(); 9037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionQueue.pop_back(); 9137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 9237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines R->replaceExit(NewExit); 9337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (typename RegionT::const_iterator RI = R->begin(), RE = R->end(); 9437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RI != RE; ++RI) { 9537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if ((*RI)->getExit() == OldExit) 9637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionQueue.push_back(RI->get()); 9737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 9837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 9937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 10037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 10137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 10237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesbool RegionBase<Tr>::contains(const BlockT *B) const { 10337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *BB = const_cast<BlockT *>(B); 10437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 10537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!DT->getNode(BB)) 10637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return false; 10737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 10837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *entry = getEntry(), *exit = getExit(); 10937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 11037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Toplevel region. 11137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!exit) 11237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return true; 11337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 11437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return (DT->dominates(entry, BB) && 11537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines !(DT->dominates(exit, BB) && DT->dominates(entry, exit))); 11637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 11737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 11837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 11937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesbool RegionBase<Tr>::contains(const LoopT *L) const { 12037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // BBs that are not part of any loop are element of the Loop 12137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // described by the NULL pointer. This loop is not part of any region, 12237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // except if the region describes the whole function. 12337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!L) 12437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return getExit() == nullptr; 12537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 12637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!contains(L->getHeader())) 12737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return false; 12837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 12937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines SmallVector<BlockT *, 8> ExitingBlocks; 13037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines L->getExitingBlocks(ExitingBlocks); 13137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 13237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (BlockT *BB : ExitingBlocks) { 13337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!contains(BB)) 13437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return false; 13537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 13637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 13737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return true; 13837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 13937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 14037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 14137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestypename Tr::LoopT *RegionBase<Tr>::outermostLoopInRegion(LoopT *L) const { 14237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!contains(L)) 14337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return nullptr; 14437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 14537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines while (L && contains(L->getParentLoop())) { 14637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines L = L->getParentLoop(); 14737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 14837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 14937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return L; 15037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 15137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 15237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 15337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestypename Tr::LoopT *RegionBase<Tr>::outermostLoopInRegion(LoopInfoT *LI, 15437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *BB) const { 15537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(LI && BB && "LI and BB cannot be null!"); 15637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines LoopT *L = LI->getLoopFor(BB); 15737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return outermostLoopInRegion(L); 15837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 15937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 16037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 16137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestypename RegionBase<Tr>::BlockT *RegionBase<Tr>::getEnteringBlock() const { 16237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *entry = getEntry(); 16337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *Pred; 16437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *enteringBlock = nullptr; 16537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 16637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (PredIterTy PI = InvBlockTraits::child_begin(entry), 16737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines PE = InvBlockTraits::child_end(entry); 16837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines PI != PE; ++PI) { 16937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Pred = *PI; 17037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (DT->getNode(Pred) && !contains(Pred)) { 17137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (enteringBlock) 17237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return nullptr; 17337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 17437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines enteringBlock = Pred; 17537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 17637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 17737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 17837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return enteringBlock; 17937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 18037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 18137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 18237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestypename RegionBase<Tr>::BlockT *RegionBase<Tr>::getExitingBlock() const { 18337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *exit = getExit(); 18437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *Pred; 18537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *exitingBlock = nullptr; 18637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 18737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!exit) 18837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return nullptr; 18937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 19037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (PredIterTy PI = InvBlockTraits::child_begin(exit), 19137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines PE = InvBlockTraits::child_end(exit); 19237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines PI != PE; ++PI) { 19337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Pred = *PI; 19437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (contains(Pred)) { 19537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (exitingBlock) 19637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return nullptr; 19737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 19837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines exitingBlock = Pred; 19937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 20037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 20137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 20237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return exitingBlock; 20337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 20437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 20537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 20637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesbool RegionBase<Tr>::isSimple() const { 20737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return !isTopLevelRegion() && getEnteringBlock() && getExitingBlock(); 20837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 20937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 21037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 21137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesstd::string RegionBase<Tr>::getNameStr() const { 21237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines std::string exitName; 21337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines std::string entryName; 21437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 21537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (getEntry()->getName().empty()) { 21637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines raw_string_ostream OS(entryName); 21737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 21837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines getEntry()->printAsOperand(OS, false); 21937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } else 22037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines entryName = getEntry()->getName(); 22137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 22237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (getExit()) { 22337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (getExit()->getName().empty()) { 22437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines raw_string_ostream OS(exitName); 22537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 22637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines getExit()->printAsOperand(OS, false); 22737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } else 22837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines exitName = getExit()->getName(); 22937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } else 23037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines exitName = "<Function Return>"; 23137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 23237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return entryName + " => " + exitName; 23337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 23437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 23537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 23637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesvoid RegionBase<Tr>::verifyBBInRegion(BlockT *BB) const { 23737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!contains(BB)) 238f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar llvm_unreachable("Broken region found: enumerated BB not in region!"); 23937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 24037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *entry = getEntry(), *exit = getExit(); 24137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 24237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (SuccIterTy SI = BlockTraits::child_begin(BB), 24337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines SE = BlockTraits::child_end(BB); 24437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines SI != SE; ++SI) { 24537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!contains(*SI) && exit != *SI) 246f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar llvm_unreachable("Broken region found: edges leaving the region must go " 247f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar "to the exit node!"); 24837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 24937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 25037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (entry != BB) { 25137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (PredIterTy SI = InvBlockTraits::child_begin(BB), 25237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines SE = InvBlockTraits::child_end(BB); 25337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines SI != SE; ++SI) { 25437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!contains(*SI)) 255f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar llvm_unreachable("Broken region found: edges entering the region must " 256f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar "go to the entry node!"); 25737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 25837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 25937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 26037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 26137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 26237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesvoid RegionBase<Tr>::verifyWalk(BlockT *BB, std::set<BlockT *> *visited) const { 26337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *exit = getExit(); 26437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 26537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines visited->insert(BB); 26637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 26737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines verifyBBInRegion(BB); 26837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 26937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (SuccIterTy SI = BlockTraits::child_begin(BB), 27037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines SE = BlockTraits::child_end(BB); 27137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines SI != SE; ++SI) { 27237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (*SI != exit && visited->find(*SI) == visited->end()) 27337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines verifyWalk(*SI, visited); 27437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 27537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 27637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 27737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 27837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesvoid RegionBase<Tr>::verifyRegion() const { 27937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Only do verification when user wants to, otherwise this expensive check 28037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // will be invoked by PMDataManager::verifyPreservedAnalysis when 28137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // a regionpass (marked PreservedAll) finish. 28237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!RegionInfoBase<Tr>::VerifyRegionInfo) 28337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return; 28437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 28537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines std::set<BlockT *> visited; 28637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines verifyWalk(getEntry(), &visited); 28737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 28837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 28937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 29037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesvoid RegionBase<Tr>::verifyRegionNest() const { 29137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (typename RegionT::const_iterator RI = begin(), RE = end(); RI != RE; 29237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines ++RI) 29337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines (*RI)->verifyRegionNest(); 29437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 29537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines verifyRegion(); 29637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 29737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 29837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 29937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestypename RegionBase<Tr>::element_iterator RegionBase<Tr>::element_begin() { 30037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return GraphTraits<RegionT *>::nodes_begin(static_cast<RegionT *>(this)); 30137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 30237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 30337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 30437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestypename RegionBase<Tr>::element_iterator RegionBase<Tr>::element_end() { 30537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return GraphTraits<RegionT *>::nodes_end(static_cast<RegionT *>(this)); 30637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 30737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 30837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 30937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestypename RegionBase<Tr>::const_element_iterator 31037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen HinesRegionBase<Tr>::element_begin() const { 31137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return GraphTraits<const RegionT *>::nodes_begin( 31237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines static_cast<const RegionT *>(this)); 31337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 31437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 31537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 31637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestypename RegionBase<Tr>::const_element_iterator 31737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen HinesRegionBase<Tr>::element_end() const { 31837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return GraphTraits<const RegionT *>::nodes_end( 31937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines static_cast<const RegionT *>(this)); 32037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 32137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 32237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 32337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestypename Tr::RegionT *RegionBase<Tr>::getSubRegionNode(BlockT *BB) const { 32437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename Tr::RegionT RegionT; 32537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *R = RI->getRegionFor(BB); 32637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 32737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!R || R == this) 32837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return nullptr; 32937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 33037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // If we pass the BB out of this region, that means our code is broken. 33137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(contains(R) && "BB not in current region!"); 33237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 33337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines while (contains(R->getParent()) && R->getParent() != this) 33437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines R = R->getParent(); 33537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 33637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (R->getEntry() != BB) 33737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return nullptr; 33837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 33937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return R; 34037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 34137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 34237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 34337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestypename Tr::RegionNodeT *RegionBase<Tr>::getBBNode(BlockT *BB) const { 34437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(contains(BB) && "Can get BB node out of this region!"); 34537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 34637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typename BBNodeMapT::const_iterator at = BBNodeMap.find(BB); 34737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 34837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (at != BBNodeMap.end()) 34937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return at->second; 35037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 35137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto Deconst = const_cast<RegionBase<Tr> *>(this); 35237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionNodeT *NewNode = new RegionNodeT(static_cast<RegionT *>(Deconst), BB); 35337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BBNodeMap.insert(std::make_pair(BB, NewNode)); 35437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return NewNode; 35537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 35637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 35737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 35837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestypename Tr::RegionNodeT *RegionBase<Tr>::getNode(BlockT *BB) const { 35937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(contains(BB) && "Can get BB node out of this region!"); 36037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (RegionT *Child = getSubRegionNode(BB)) 36137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Child->getNode(); 36237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 36337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return getBBNode(BB); 36437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 36537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 36637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 36737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesvoid RegionBase<Tr>::transferChildrenTo(RegionT *To) { 36837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (iterator I = begin(), E = end(); I != E; ++I) { 36937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines (*I)->parent = To; 37037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines To->children.push_back(std::move(*I)); 37137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 37237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines children.clear(); 37337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 37437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 37537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 37637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesvoid RegionBase<Tr>::addSubRegion(RegionT *SubRegion, bool moveChildren) { 37737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(!SubRegion->parent && "SubRegion already has a parent!"); 37837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(std::find_if(begin(), end(), [&](const std::unique_ptr<RegionT> &R) { 37937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return R.get() == SubRegion; 38037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines }) == children.end() && 38137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines "Subregion already exists!"); 38237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 38337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines SubRegion->parent = static_cast<RegionT *>(this); 38437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines children.push_back(std::unique_ptr<RegionT>(SubRegion)); 38537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 38637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!moveChildren) 38737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return; 38837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 38937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(SubRegion->children.empty() && 39037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines "SubRegions that contain children are not supported"); 39137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 39237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (element_iterator I = element_begin(), E = element_end(); I != E; ++I) { 39337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!(*I)->isSubRegion()) { 39437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *BB = (*I)->template getNodeAs<BlockT>(); 39537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 39637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (SubRegion->contains(BB)) 39737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RI->setRegionFor(BB, SubRegion); 39837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 39937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 40037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 40137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines std::vector<std::unique_ptr<RegionT>> Keep; 40237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (iterator I = begin(), E = end(); I != E; ++I) { 40337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (SubRegion->contains(I->get()) && I->get() != SubRegion) { 40437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines (*I)->parent = SubRegion; 40537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines SubRegion->children.push_back(std::move(*I)); 40637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } else 40737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Keep.push_back(std::move(*I)); 40837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 40937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 41037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines children.clear(); 41137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines children.insert( 41237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines children.begin(), 41337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines std::move_iterator<typename RegionSet::iterator>(Keep.begin()), 41437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines std::move_iterator<typename RegionSet::iterator>(Keep.end())); 41537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 41637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 41737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 41837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestypename Tr::RegionT *RegionBase<Tr>::removeSubRegion(RegionT *Child) { 41937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(Child->parent == this && "Child is not a child of this region!"); 42037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Child->parent = nullptr; 42137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typename RegionSet::iterator I = std::find_if( 42237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines children.begin(), children.end(), 42337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines [&](const std::unique_ptr<RegionT> &R) { return R.get() == Child; }); 42437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(I != children.end() && "Region does not exit. Unable to remove."); 42537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines children.erase(children.begin() + (I - begin())); 42637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Child; 42737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 42837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 42937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 43037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesunsigned RegionBase<Tr>::getDepth() const { 43137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines unsigned Depth = 0; 43237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 43337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (RegionT *R = getParent(); R != nullptr; R = R->getParent()) 43437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines ++Depth; 43537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 43637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Depth; 43737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 43837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 43937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 44037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestypename Tr::RegionT *RegionBase<Tr>::getExpandedRegion() const { 44137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines unsigned NumSuccessors = Tr::getNumSuccessors(exit); 44237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 44337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (NumSuccessors == 0) 44437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return nullptr; 44537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 44637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *R = RI->getRegionFor(exit); 44737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 44837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (R->getEntry() != exit) { 449f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (PredIterTy PI = InvBlockTraits::child_begin(getExit()), 450f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar PE = InvBlockTraits::child_end(getExit()); 451f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar PI != PE; ++PI) 452f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (!contains(*PI)) 453f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return nullptr; 45437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (Tr::getNumSuccessors(exit) == 1) 45537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return new RegionT(getEntry(), *BlockTraits::child_begin(exit), RI, DT); 45637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return nullptr; 45737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 45837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 45937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines while (R->getParent() && R->getParent()->getEntry() == exit) 46037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines R = R->getParent(); 46137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 462f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (PredIterTy PI = InvBlockTraits::child_begin(getExit()), 463f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar PE = InvBlockTraits::child_end(getExit()); 464f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar PI != PE; ++PI) { 465f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (!(contains(*PI) || R->contains(*PI))) 466f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return nullptr; 46737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 46837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 46937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return new RegionT(getEntry(), R->getExit(), RI, DT); 47037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 47137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 47237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 47337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesvoid RegionBase<Tr>::print(raw_ostream &OS, bool print_tree, unsigned level, 47437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines PrintStyle Style) const { 47537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (print_tree) 47637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines OS.indent(level * 2) << '[' << level << "] " << getNameStr(); 47737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines else 47837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines OS.indent(level * 2) << getNameStr(); 47937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 48037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines OS << '\n'; 48137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 48237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (Style != PrintNone) { 48337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines OS.indent(level * 2) << "{\n"; 48437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines OS.indent(level * 2 + 2); 48537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 48637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (Style == PrintBB) { 4870c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar for (const auto *BB : blocks()) 48837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines OS << BB->getName() << ", "; // TODO: remove the last "," 48937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } else if (Style == PrintRN) { 49037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (const_element_iterator I = element_begin(), E = element_end(); 49137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines I != E; ++I) { 49237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines OS << **I << ", "; // TODO: remove the last ", 49337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 49437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 49537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 49637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines OS << '\n'; 49737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 49837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 49937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (print_tree) { 50037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (const_iterator RI = begin(), RE = end(); RI != RE; ++RI) 50137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines (*RI)->print(OS, print_tree, level + 1, Style); 50237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 50337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 50437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (Style != PrintNone) 50537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines OS.indent(level * 2) << "} \n"; 50637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 50737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 50837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 50937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 51037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesvoid RegionBase<Tr>::dump() const { 51137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines print(dbgs(), true, getDepth(), RegionInfoBase<Tr>::printStyle); 51237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 51337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#endif 51437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 51537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 51637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesvoid RegionBase<Tr>::clearNodeCache() { 51737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Free the cached nodes. 51837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (typename BBNodeMapT::iterator I = BBNodeMap.begin(), 51937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines IE = BBNodeMap.end(); 52037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines I != IE; ++I) 52137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines delete I->second; 52237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 52337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BBNodeMap.clear(); 52437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (typename RegionT::iterator RI = begin(), RE = end(); RI != RE; ++RI) 52537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines (*RI)->clearNodeCache(); 52637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 52737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 52837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines//===----------------------------------------------------------------------===// 52937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// RegionInfoBase implementation 53037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// 53137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 53237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 53337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen HinesRegionInfoBase<Tr>::RegionInfoBase() 53437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines : TopLevelRegion(nullptr) {} 53537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 53637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 53737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen HinesRegionInfoBase<Tr>::~RegionInfoBase() { 53837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines releaseMemory(); 53937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 54037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 54137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 542f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarvoid RegionInfoBase<Tr>::verifyBBMap(const RegionT *R) const { 543f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar assert(R && "Re must be non-null"); 544f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (auto I = R->element_begin(), E = R->element_end(); I != E; ++I) { 545f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (I->isSubRegion()) { 546f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const RegionT *SR = I->template getNodeAs<RegionT>(); 547f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar verifyBBMap(SR); 548f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } else { 549f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar BlockT *BB = I->template getNodeAs<BlockT>(); 550f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (getRegionFor(BB) != R) 551f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar llvm_unreachable("BB map does not match region nesting"); 552f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 553f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 554f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 555f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 556f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainartemplate <class Tr> 55737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesbool RegionInfoBase<Tr>::isCommonDomFrontier(BlockT *BB, BlockT *entry, 55837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *exit) const { 55937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (PredIterTy PI = InvBlockTraits::child_begin(BB), 56037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines PE = InvBlockTraits::child_end(BB); 56137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines PI != PE; ++PI) { 56237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *P = *PI; 56337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (DT->dominates(entry, P) && !DT->dominates(exit, P)) 56437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return false; 56537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 56637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 56737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return true; 56837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 56937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 57037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 57137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesbool RegionInfoBase<Tr>::isRegion(BlockT *entry, BlockT *exit) const { 57237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(entry && exit && "entry and exit must not be null!"); 57337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename DomFrontierT::DomSetType DST; 57437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 57537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines DST *entrySuccs = &DF->find(entry)->second; 57637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 57737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Exit is the header of a loop that contains the entry. In this case, 57837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // the dominance frontier must only contain the exit. 57937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!DT->dominates(entry, exit)) { 58037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (typename DST::iterator SI = entrySuccs->begin(), 58137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines SE = entrySuccs->end(); 58237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines SI != SE; ++SI) { 58337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (*SI != exit && *SI != entry) 58437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return false; 58537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 58637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 58737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return true; 58837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 58937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 59037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines DST *exitSuccs = &DF->find(exit)->second; 59137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 59237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Do not allow edges leaving the region. 59337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (typename DST::iterator SI = entrySuccs->begin(), SE = entrySuccs->end(); 59437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines SI != SE; ++SI) { 59537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (*SI == exit || *SI == entry) 59637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines continue; 59737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (exitSuccs->find(*SI) == exitSuccs->end()) 59837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return false; 59937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!isCommonDomFrontier(*SI, entry, exit)) 60037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return false; 60137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 60237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 60337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Do not allow edges pointing into the region. 60437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (typename DST::iterator SI = exitSuccs->begin(), SE = exitSuccs->end(); 60537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines SI != SE; ++SI) { 60637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (DT->properlyDominates(entry, *SI) && *SI != exit) 60737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return false; 60837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 60937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 61037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return true; 61137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 61237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 61337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 61437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesvoid RegionInfoBase<Tr>::insertShortCut(BlockT *entry, BlockT *exit, 61537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BBtoBBMap *ShortCut) const { 61637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(entry && exit && "entry and exit must not be null!"); 61737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 61837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typename BBtoBBMap::iterator e = ShortCut->find(exit); 61937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 62037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (e == ShortCut->end()) 62137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // No further region at exit available. 62237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines (*ShortCut)[entry] = exit; 62337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines else { 62437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // We found a region e that starts at exit. Therefore (entry, e->second) 62537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // is also a region, that is larger than (entry, exit). Insert the 62637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // larger one. 62737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *BB = e->second; 62837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines (*ShortCut)[entry] = BB; 62937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 63037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 63137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 63237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 63337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestypename Tr::DomTreeNodeT * 63437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen HinesRegionInfoBase<Tr>::getNextPostDom(DomTreeNodeT *N, BBtoBBMap *ShortCut) const { 63537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typename BBtoBBMap::iterator e = ShortCut->find(N->getBlock()); 63637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 63737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (e == ShortCut->end()) 63837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return N->getIDom(); 63937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 64037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return PDT->getNode(e->second)->getIDom(); 64137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 64237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 64337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 64437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesbool RegionInfoBase<Tr>::isTrivialRegion(BlockT *entry, BlockT *exit) const { 64537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(entry && exit && "entry and exit must not be null!"); 64637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 64737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines unsigned num_successors = 64837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockTraits::child_end(entry) - BlockTraits::child_begin(entry); 64937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 65037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (num_successors <= 1 && exit == *(BlockTraits::child_begin(entry))) 65137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return true; 65237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 65337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return false; 65437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 65537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 65637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 65737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestypename Tr::RegionT *RegionInfoBase<Tr>::createRegion(BlockT *entry, 65837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *exit) { 65937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(entry && exit && "entry and exit must not be null!"); 66037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 66137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (isTrivialRegion(entry, exit)) 66237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return nullptr; 66337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 66437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *region = 66537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines new RegionT(entry, exit, static_cast<RegionInfoT *>(this), DT); 66637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BBtoRegion.insert(std::make_pair(entry, region)); 66737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 668de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#ifdef EXPENSIVE_CHECKS 66937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines region->verifyRegion(); 67037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#else 67137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines DEBUG(region->verifyRegion()); 67237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#endif 67337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 67437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines updateStatistics(region); 67537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return region; 67637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 67737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 67837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 67937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesvoid RegionInfoBase<Tr>::findRegionsWithEntry(BlockT *entry, 68037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BBtoBBMap *ShortCut) { 68137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(entry); 68237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 68337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines DomTreeNodeT *N = PDT->getNode(entry); 68437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!N) 68537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return; 68637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 68737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *lastRegion = nullptr; 68837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *lastExit = entry; 68937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 69037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // As only a BasicBlock that postdominates entry can finish a region, walk the 69137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // post dominance tree upwards. 69237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines while ((N = getNextPostDom(N, ShortCut))) { 69337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *exit = N->getBlock(); 69437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 69537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!exit) 69637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines break; 69737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 69837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (isRegion(entry, exit)) { 69937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *newRegion = createRegion(entry, exit); 70037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 70137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (lastRegion) 70237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines newRegion->addSubRegion(lastRegion); 70337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 70437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines lastRegion = newRegion; 70537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines lastExit = exit; 70637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 70737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 70837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // This can never be a region, so stop the search. 70937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!DT->dominates(entry, exit)) 71037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines break; 71137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 71237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 71337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Tried to create regions from entry to lastExit. Next time take a 71437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // shortcut from entry to lastExit. 71537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (lastExit != entry) 71637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines insertShortCut(entry, lastExit, ShortCut); 71737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 71837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 71937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 72037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesvoid RegionInfoBase<Tr>::scanForRegions(FuncT &F, BBtoBBMap *ShortCut) { 72137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename std::add_pointer<FuncT>::type FuncPtrT; 72237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *entry = GraphTraits<FuncPtrT>::getEntryNode(&F); 72337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines DomTreeNodeT *N = DT->getNode(entry); 72437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 72537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Iterate over the dominance tree in post order to start with the small 72637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // regions from the bottom of the dominance tree. If the small regions are 72737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // detected first, detection of bigger regions is faster, as we can jump 72837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // over the small regions. 7290c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar for (auto DomNode : post_order(N)) 7300c7f116bb6950ef819323d855415b2f2b0aad987Pirama Arumuga Nainar findRegionsWithEntry(DomNode->getBlock(), ShortCut); 73137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 73237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 73337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 73437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestypename Tr::RegionT *RegionInfoBase<Tr>::getTopMostParent(RegionT *region) { 73537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines while (region->getParent()) 73637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines region = region->getParent(); 73737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 73837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return region; 73937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 74037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 74137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 74237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesvoid RegionInfoBase<Tr>::buildRegionsTree(DomTreeNodeT *N, RegionT *region) { 74337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *BB = N->getBlock(); 74437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 74537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Passed region exit 74637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines while (BB == region->getExit()) 74737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines region = region->getParent(); 74837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 74937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typename BBtoRegionMap::iterator it = BBtoRegion.find(BB); 75037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 75137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // This basic block is a start block of a region. It is already in the 75237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // BBtoRegion relation. Only the child basic blocks have to be updated. 75337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (it != BBtoRegion.end()) { 75437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *newRegion = it->second; 75537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines region->addSubRegion(getTopMostParent(newRegion)); 75637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines region = newRegion; 75737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } else { 75837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BBtoRegion[BB] = region; 75937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 76037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 76137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (typename DomTreeNodeT::iterator CI = N->begin(), CE = N->end(); CI != CE; 76237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines ++CI) { 76337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines buildRegionsTree(*CI, region); 76437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 76537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 76637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 767de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#ifdef EXPENSIVE_CHECKS 76837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 76937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesbool RegionInfoBase<Tr>::VerifyRegionInfo = true; 77037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#else 77137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 77237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesbool RegionInfoBase<Tr>::VerifyRegionInfo = false; 77337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#endif 77437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 77537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 77637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestypename Tr::RegionT::PrintStyle RegionInfoBase<Tr>::printStyle = 77737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionBase<Tr>::PrintNone; 77837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 77937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 78037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesvoid RegionInfoBase<Tr>::print(raw_ostream &OS) const { 78137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines OS << "Region tree:\n"; 78237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines TopLevelRegion->print(OS, true, 0, printStyle); 78337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines OS << "End region tree\n"; 78437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 78537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 78637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 78737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 78837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesvoid RegionInfoBase<Tr>::dump() const { print(dbgs()); } 78937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#endif 79037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 79137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 79237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesvoid RegionInfoBase<Tr>::releaseMemory() { 79337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BBtoRegion.clear(); 79437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (TopLevelRegion) 79537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines delete TopLevelRegion; 79637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines TopLevelRegion = nullptr; 79737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 79837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 79937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 80037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesvoid RegionInfoBase<Tr>::verifyAnalysis() const { 801de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Do only verify regions if explicitely activated using EXPENSIVE_CHECKS or 802f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // -verify-region-info 803f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (!RegionInfoBase<Tr>::VerifyRegionInfo) 804f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return; 805f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 80637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines TopLevelRegion->verifyRegionNest(); 807f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 808f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar verifyBBMap(TopLevelRegion); 80937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 81037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 81137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// Region pass manager support. 81237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 81337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestypename Tr::RegionT *RegionInfoBase<Tr>::getRegionFor(BlockT *BB) const { 81437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typename BBtoRegionMap::const_iterator I = BBtoRegion.find(BB); 81537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return I != BBtoRegion.end() ? I->second : nullptr; 81637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 81737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 81837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 81937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesvoid RegionInfoBase<Tr>::setRegionFor(BlockT *BB, RegionT *R) { 82037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BBtoRegion[BB] = R; 82137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 82237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 82337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 82437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestypename Tr::RegionT *RegionInfoBase<Tr>::operator[](BlockT *BB) const { 82537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return getRegionFor(BB); 82637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 82737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 82837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 82937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestypename RegionInfoBase<Tr>::BlockT * 83037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen HinesRegionInfoBase<Tr>::getMaxRegionExit(BlockT *BB) const { 83137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *Exit = nullptr; 83237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 83337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines while (true) { 83437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Get largest region that starts at BB. 83537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *R = getRegionFor(BB); 83637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines while (R && R->getParent() && R->getParent()->getEntry() == BB) 83737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines R = R->getParent(); 83837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 83937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Get the single exit of BB. 84037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (R && R->getEntry() == BB) 84137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Exit = R->getExit(); 84237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines else if (++BlockTraits::child_begin(BB) == BlockTraits::child_end(BB)) 84337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Exit = *BlockTraits::child_begin(BB); 84437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines else // No single exit exists. 84537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Exit; 84637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 84737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Get largest region that starts at Exit. 84837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *ExitR = getRegionFor(Exit); 84937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines while (ExitR && ExitR->getParent() && 85037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines ExitR->getParent()->getEntry() == Exit) 85137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines ExitR = ExitR->getParent(); 85237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 85337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (PredIterTy PI = InvBlockTraits::child_begin(Exit), 85437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines PE = InvBlockTraits::child_end(Exit); 85537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines PI != PE; ++PI) { 85637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!R->contains(*PI) && !ExitR->contains(*PI)) 85737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines break; 85837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 85937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 86037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // This stops infinite cycles. 86137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (DT->dominates(Exit, BB)) 86237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines break; 86337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 86437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BB = Exit; 86537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 86637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 86737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Exit; 86837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 86937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 87037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 87137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestypename Tr::RegionT *RegionInfoBase<Tr>::getCommonRegion(RegionT *A, 87237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *B) const { 87337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(A && B && "One of the Regions is NULL"); 87437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 87537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (A->contains(B)) 87637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return A; 87737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 87837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines while (!B->contains(A)) 87937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines B = B->getParent(); 88037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 88137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return B; 88237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 88337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 88437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 88537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestypename Tr::RegionT * 88637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen HinesRegionInfoBase<Tr>::getCommonRegion(SmallVectorImpl<RegionT *> &Regions) const { 88737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *ret = Regions.back(); 88837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Regions.pop_back(); 88937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 89037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (RegionT *R : Regions) 89137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines ret = getCommonRegion(ret, R); 89237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 89337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return ret; 89437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 89537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 89637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 89737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestypename Tr::RegionT * 89837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen HinesRegionInfoBase<Tr>::getCommonRegion(SmallVectorImpl<BlockT *> &BBs) const { 89937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines RegionT *ret = getRegionFor(BBs.back()); 90037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BBs.pop_back(); 90137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 90237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (BlockT *BB : BBs) 90337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines ret = getCommonRegion(ret, getRegionFor(BB)); 90437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 90537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return ret; 90637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 90737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 90837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinestemplate <class Tr> 90937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesvoid RegionInfoBase<Tr>::calculate(FuncT &F) { 91037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typedef typename std::add_pointer<FuncT>::type FuncPtrT; 91137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 91237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // ShortCut a function where for every BB the exit of the largest region 91337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // starting with BB is stored. These regions can be threated as single BBS. 91437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // This improves performance on linear CFGs. 91537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BBtoBBMap ShortCut; 91637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 91737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines scanForRegions(F, &ShortCut); 91837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BlockT *BB = GraphTraits<FuncPtrT>::getEntryNode(&F); 91937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines buildRegionsTree(DT->getNode(BB), TopLevelRegion); 92037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 92137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 92237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#undef DEBUG_TYPE 92337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 92437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} // end namespace llvm 92537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 92637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#endif 927