1//===- RegionPass.cpp - Region Pass and Region Pass Manager ---------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements RegionPass and RGPassManager. All region optimization 11// and transformation passes are derived from RegionPass. RGPassManager is 12// responsible for managing RegionPasses. 13// most of these codes are COPY from LoopPass.cpp 14// 15//===----------------------------------------------------------------------===// 16#include "llvm/Analysis/RegionPass.h" 17#include "llvm/Analysis/RegionIterator.h" 18#include "llvm/Support/Timer.h" 19 20#define DEBUG_TYPE "regionpassmgr" 21#include "llvm/Support/Debug.h" 22using namespace llvm; 23 24//===----------------------------------------------------------------------===// 25// RGPassManager 26// 27 28char RGPassManager::ID = 0; 29 30RGPassManager::RGPassManager() 31 : FunctionPass(ID), PMDataManager() { 32 skipThisRegion = false; 33 redoThisRegion = false; 34 RI = NULL; 35 CurrentRegion = NULL; 36} 37 38// Recurse through all subregions and all regions into RQ. 39static void addRegionIntoQueue(Region *R, std::deque<Region *> &RQ) { 40 RQ.push_back(R); 41 for (Region::iterator I = R->begin(), E = R->end(); I != E; ++I) 42 addRegionIntoQueue(*I, RQ); 43} 44 45/// Pass Manager itself does not invalidate any analysis info. 46void RGPassManager::getAnalysisUsage(AnalysisUsage &Info) const { 47 Info.addRequired<RegionInfo>(); 48 Info.setPreservesAll(); 49} 50 51/// run - Execute all of the passes scheduled for execution. Keep track of 52/// whether any of the passes modifies the function, and if so, return true. 53bool RGPassManager::runOnFunction(Function &F) { 54 RI = &getAnalysis<RegionInfo>(); 55 bool Changed = false; 56 57 // Collect inherited analysis from Module level pass manager. 58 populateInheritedAnalysis(TPM->activeStack); 59 60 addRegionIntoQueue(RI->getTopLevelRegion(), RQ); 61 62 if (RQ.empty()) // No regions, skip calling finalizers 63 return false; 64 65 // Initialization 66 for (std::deque<Region *>::const_iterator I = RQ.begin(), E = RQ.end(); 67 I != E; ++I) { 68 Region *R = *I; 69 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 70 RegionPass *RP = (RegionPass *)getContainedPass(Index); 71 Changed |= RP->doInitialization(R, *this); 72 } 73 } 74 75 // Walk Regions 76 while (!RQ.empty()) { 77 78 CurrentRegion = RQ.back(); 79 skipThisRegion = false; 80 redoThisRegion = false; 81 82 // Run all passes on the current Region. 83 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 84 RegionPass *P = (RegionPass*)getContainedPass(Index); 85 86 dumpPassInfo(P, EXECUTION_MSG, ON_REGION_MSG, 87 CurrentRegion->getNameStr()); 88 dumpRequiredSet(P); 89 90 initializeAnalysisImpl(P); 91 92 { 93 PassManagerPrettyStackEntry X(P, *CurrentRegion->getEntry()); 94 95 TimeRegion PassTimer(getPassTimer(P)); 96 Changed |= P->runOnRegion(CurrentRegion, *this); 97 } 98 99 if (Changed) 100 dumpPassInfo(P, MODIFICATION_MSG, ON_REGION_MSG, 101 skipThisRegion ? "<deleted>" : 102 CurrentRegion->getNameStr()); 103 dumpPreservedSet(P); 104 105 if (!skipThisRegion) { 106 // Manually check that this region is still healthy. This is done 107 // instead of relying on RegionInfo::verifyRegion since RegionInfo 108 // is a function pass and it's really expensive to verify every 109 // Region in the function every time. That level of checking can be 110 // enabled with the -verify-region-info option. 111 { 112 TimeRegion PassTimer(getPassTimer(P)); 113 CurrentRegion->verifyRegion(); 114 } 115 116 // Then call the regular verifyAnalysis functions. 117 verifyPreservedAnalysis(P); 118 } 119 120 removeNotPreservedAnalysis(P); 121 recordAvailableAnalysis(P); 122 removeDeadPasses(P, 123 skipThisRegion ? "<deleted>" : 124 CurrentRegion->getNameStr(), 125 ON_REGION_MSG); 126 127 if (skipThisRegion) 128 // Do not run other passes on this region. 129 break; 130 } 131 132 // If the region was deleted, release all the region passes. This frees up 133 // some memory, and avoids trouble with the pass manager trying to call 134 // verifyAnalysis on them. 135 if (skipThisRegion) 136 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 137 Pass *P = getContainedPass(Index); 138 freePass(P, "<deleted>", ON_REGION_MSG); 139 } 140 141 // Pop the region from queue after running all passes. 142 RQ.pop_back(); 143 144 if (redoThisRegion) 145 RQ.push_back(CurrentRegion); 146 147 // Free all region nodes created in region passes. 148 RI->clearNodeCache(); 149 } 150 151 // Finalization 152 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 153 RegionPass *P = (RegionPass*)getContainedPass(Index); 154 Changed |= P->doFinalization(); 155 } 156 157 // Print the region tree after all pass. 158 DEBUG( 159 dbgs() << "\nRegion tree of function " << F.getName() 160 << " after all region Pass:\n"; 161 RI->dump(); 162 dbgs() << "\n"; 163 ); 164 165 return Changed; 166} 167 168/// Print passes managed by this manager 169void RGPassManager::dumpPassStructure(unsigned Offset) { 170 errs().indent(Offset*2) << "Region Pass Manager\n"; 171 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 172 Pass *P = getContainedPass(Index); 173 P->dumpPassStructure(Offset + 1); 174 dumpLastUses(P, Offset+1); 175 } 176} 177 178namespace { 179//===----------------------------------------------------------------------===// 180// PrintRegionPass 181class PrintRegionPass : public RegionPass { 182private: 183 std::string Banner; 184 raw_ostream &Out; // raw_ostream to print on. 185 186public: 187 static char ID; 188 PrintRegionPass() : RegionPass(ID), Out(dbgs()) {} 189 PrintRegionPass(const std::string &B, raw_ostream &o) 190 : RegionPass(ID), Banner(B), Out(o) {} 191 192 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 193 AU.setPreservesAll(); 194 } 195 196 virtual bool runOnRegion(Region *R, RGPassManager &RGM) { 197 Out << Banner; 198 for (Region::block_iterator I = R->block_begin(), E = R->block_end(); 199 I != E; ++I) 200 (*I)->print(Out); 201 202 return false; 203 } 204}; 205 206char PrintRegionPass::ID = 0; 207} //end anonymous namespace 208 209//===----------------------------------------------------------------------===// 210// RegionPass 211 212// Check if this pass is suitable for the current RGPassManager, if 213// available. This pass P is not suitable for a RGPassManager if P 214// is not preserving higher level analysis info used by other 215// RGPassManager passes. In such case, pop RGPassManager from the 216// stack. This will force assignPassManager() to create new 217// LPPassManger as expected. 218void RegionPass::preparePassManager(PMStack &PMS) { 219 220 // Find RGPassManager 221 while (!PMS.empty() && 222 PMS.top()->getPassManagerType() > PMT_RegionPassManager) 223 PMS.pop(); 224 225 226 // If this pass is destroying high level information that is used 227 // by other passes that are managed by LPM then do not insert 228 // this pass in current LPM. Use new RGPassManager. 229 if (PMS.top()->getPassManagerType() == PMT_RegionPassManager && 230 !PMS.top()->preserveHigherLevelAnalysis(this)) 231 PMS.pop(); 232} 233 234/// Assign pass manager to manage this pass. 235void RegionPass::assignPassManager(PMStack &PMS, 236 PassManagerType PreferredType) { 237 // Find RGPassManager 238 while (!PMS.empty() && 239 PMS.top()->getPassManagerType() > PMT_RegionPassManager) 240 PMS.pop(); 241 242 RGPassManager *RGPM; 243 244 // Create new Region Pass Manager if it does not exist. 245 if (PMS.top()->getPassManagerType() == PMT_RegionPassManager) 246 RGPM = (RGPassManager*)PMS.top(); 247 else { 248 249 assert (!PMS.empty() && "Unable to create Region Pass Manager"); 250 PMDataManager *PMD = PMS.top(); 251 252 // [1] Create new Region Pass Manager 253 RGPM = new RGPassManager(); 254 RGPM->populateInheritedAnalysis(PMS); 255 256 // [2] Set up new manager's top level manager 257 PMTopLevelManager *TPM = PMD->getTopLevelManager(); 258 TPM->addIndirectPassManager(RGPM); 259 260 // [3] Assign manager to manage this new manager. This may create 261 // and push new managers into PMS 262 TPM->schedulePass(RGPM); 263 264 // [4] Push new manager into PMS 265 PMS.push(RGPM); 266 } 267 268 RGPM->add(this); 269} 270 271/// Get the printer pass 272Pass *RegionPass::createPrinterPass(raw_ostream &O, 273 const std::string &Banner) const { 274 return new PrintRegionPass(Banner, O); 275} 276