PassManager.cpp revision 844731a7f1909f55935e3514c9e713a62d67662e
1ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao//===- PassManager.cpp - LLVM Pass Infrastructure Implementation ----------===// 2ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao// 3ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao// The LLVM Compiler Infrastructure 4ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao// 5ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao// This file is distributed under the University of Illinois Open Source 6ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao// License. See LICENSE.TXT for details. 7ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao// 8ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao//===----------------------------------------------------------------------===// 9ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao// 10ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao// This file implements the LLVM Pass Manager infrastructure. 11ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao// 12ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao//===----------------------------------------------------------------------===// 13ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 14ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 15ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao#include "llvm/PassManagers.h" 16ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao#include "llvm/Support/CommandLine.h" 17ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao#include "llvm/Support/Timer.h" 18ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao#include "llvm/Module.h" 19ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao#include "llvm/ModuleProvider.h" 20ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao#include "llvm/Support/Streams.h" 21ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao#include "llvm/Support/ManagedStatic.h" 22ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao#include "llvm-c/Core.h" 23ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao#include <algorithm> 24ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao#include <vector> 25ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao#include <map> 26ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaousing namespace llvm; 27ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 28ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao// See PassManagers.h for Pass Manager infrastructure overview. 29ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 30ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaonamespace llvm { 31ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 32ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao//===----------------------------------------------------------------------===// 33ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao// Pass debugging information. Often it is useful to find out what pass is 34ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao// running when a crash occurs in a utility. When this library is compiled with 35ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao// debugging on, a command line option (--debug-pass) is enabled that causes the 36ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao// pass name to be printed before it executes. 37ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao// 38ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 39ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao// Different debug levels that can be enabled... 40ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaoenum PassDebugLevel { 41ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao None, Arguments, Structure, Executions, Details 42ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao}; 43ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 44ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaostatic cl::opt<enum PassDebugLevel> 45ea285162342df160e7860e26528bc7110bc6c0cdShih-wei LiaoPassDebugging("debug-pass", cl::Hidden, 46ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao cl::desc("Print PassManager debugging information"), 47ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao cl::values( 48ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao clEnumVal(None , "disable debug output"), 49ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao clEnumVal(Arguments , "print pass arguments to pass to 'opt'"), 50ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao clEnumVal(Structure , "print pass structure before run()"), 51ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao clEnumVal(Executions, "print pass name before it is executed"), 52ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao clEnumVal(Details , "print pass details when it is executed"), 53ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao clEnumValEnd)); 54ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao} // End of llvm namespace 55ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 56ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaonamespace { 57ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 58ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao//===----------------------------------------------------------------------===// 59ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao// BBPassManager 60ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao// 61ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao/// BBPassManager manages BasicBlockPass. It batches all the 62ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao/// pass together and sequence them to process one basic block before 63ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao/// processing next basic block. 64ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaoclass VISIBILITY_HIDDEN BBPassManager : public PMDataManager, 65ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao public FunctionPass { 66ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 67ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaopublic: 68ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao static char ID; 69ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao explicit BBPassManager(int Depth) 70ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao : PMDataManager(Depth), FunctionPass((intptr_t)&ID) {} 71ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 72ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao /// Execute all of the passes scheduled for execution. Keep track of 73ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao /// whether any of the passes modifies the function, and if so, return true. 74ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao bool runOnFunction(Function &F); 75ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 76ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao /// Pass Manager itself does not invalidate any analysis info. 77ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao void getAnalysisUsage(AnalysisUsage &Info) const { 78ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao Info.setPreservesAll(); 79ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao } 80ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 81ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao bool doInitialization(Module &M); 82ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao bool doInitialization(Function &F); 83ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao bool doFinalization(Module &M); 84ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao bool doFinalization(Function &F); 85ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 86ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao virtual const char *getPassName() const { 87ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return "BasicBlock Pass Manager"; 88ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao } 89ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 90ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao // Print passes managed by this manager 91ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao void dumpPassStructure(unsigned Offset) { 92ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao llvm::cerr << std::string(Offset*2, ' ') << "BasicBlockPass Manager\n"; 93ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 94ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao BasicBlockPass *BP = getContainedPass(Index); 95ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao BP->dumpPassStructure(Offset + 1); 96ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao dumpLastUses(BP, Offset+1); 97ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao } 98ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao } 99ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 100ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao BasicBlockPass *getContainedPass(unsigned N) { 101ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao assert ( N < PassVector.size() && "Pass number out of range!"); 102ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao BasicBlockPass *BP = static_cast<BasicBlockPass *>(PassVector[N]); 103ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return BP; 104ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao } 105ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 106ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao virtual PassManagerType getPassManagerType() const { 107ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao return PMT_BasicBlockPassManager; 108ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao } 109ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao}; 110ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 111ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaochar BBPassManager::ID = 0; 112ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao} 113ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 114ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaonamespace llvm { 115ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 116ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao//===----------------------------------------------------------------------===// 117ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao// FunctionPassManagerImpl 118ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao// 119ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao/// FunctionPassManagerImpl manages FPPassManagers 120ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaoclass FunctionPassManagerImpl : public Pass, 121ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao public PMDataManager, 122ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao public PMTopLevelManager { 123ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liaopublic: 124ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao static char ID; 125ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao explicit FunctionPassManagerImpl(int Depth) : 126ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao Pass((intptr_t)&ID), PMDataManager(Depth), 127ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao PMTopLevelManager(TLM_Function) { } 128ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 129ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao /// add - Add a pass to the queue of passes to run. This passes ownership of 130ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao /// the Pass to the PassManager. When the PassManager is destroyed, the pass 131ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao /// will be destroyed as well, so there is no need to delete the pass. This 132ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao /// implies that all passes MUST be allocated with 'new'. 133ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao void add(Pass *P) { 134ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao schedulePass(P); 135ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao } 136ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 137ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao /// run - Execute all of the passes scheduled for execution. Keep track of 138ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao /// whether any of the passes modifies the module, and if so, return true. 139ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao bool run(Function &F); 140ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao 141ea285162342df160e7860e26528bc7110bc6c0cdShih-wei Liao /// doInitialization - Run all of the initializers for the function passes. 142 /// 143 bool doInitialization(Module &M); 144 145 /// doFinalization - Run all of the finalizers for the function passes. 146 /// 147 bool doFinalization(Module &M); 148 149 /// Pass Manager itself does not invalidate any analysis info. 150 void getAnalysisUsage(AnalysisUsage &Info) const { 151 Info.setPreservesAll(); 152 } 153 154 inline void addTopLevelPass(Pass *P) { 155 156 if (ImmutablePass *IP = dynamic_cast<ImmutablePass *> (P)) { 157 158 // P is a immutable pass and it will be managed by this 159 // top level manager. Set up analysis resolver to connect them. 160 AnalysisResolver *AR = new AnalysisResolver(*this); 161 P->setResolver(AR); 162 initializeAnalysisImpl(P); 163 addImmutablePass(IP); 164 recordAvailableAnalysis(IP); 165 } else { 166 P->assignPassManager(activeStack); 167 } 168 169 } 170 171 FPPassManager *getContainedManager(unsigned N) { 172 assert ( N < PassManagers.size() && "Pass number out of range!"); 173 FPPassManager *FP = static_cast<FPPassManager *>(PassManagers[N]); 174 return FP; 175 } 176}; 177 178char FunctionPassManagerImpl::ID = 0; 179//===----------------------------------------------------------------------===// 180// MPPassManager 181// 182/// MPPassManager manages ModulePasses and function pass managers. 183/// It batches all Module passes and function pass managers together and 184/// sequences them to process one module. 185class MPPassManager : public Pass, public PMDataManager { 186 187public: 188 static char ID; 189 explicit MPPassManager(int Depth) : 190 Pass((intptr_t)&ID), PMDataManager(Depth) { } 191 192 // Delete on the fly managers. 193 virtual ~MPPassManager() { 194 for (std::map<Pass *, FunctionPassManagerImpl *>::iterator 195 I = OnTheFlyManagers.begin(), E = OnTheFlyManagers.end(); 196 I != E; ++I) { 197 FunctionPassManagerImpl *FPP = I->second; 198 delete FPP; 199 } 200 } 201 202 /// run - Execute all of the passes scheduled for execution. Keep track of 203 /// whether any of the passes modifies the module, and if so, return true. 204 bool runOnModule(Module &M); 205 206 /// Pass Manager itself does not invalidate any analysis info. 207 void getAnalysisUsage(AnalysisUsage &Info) const { 208 Info.setPreservesAll(); 209 } 210 211 /// Add RequiredPass into list of lower level passes required by pass P. 212 /// RequiredPass is run on the fly by Pass Manager when P requests it 213 /// through getAnalysis interface. 214 virtual void addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass); 215 216 /// Return function pass corresponding to PassInfo PI, that is 217 /// required by module pass MP. Instantiate analysis pass, by using 218 /// its runOnFunction() for function F. 219 virtual Pass* getOnTheFlyPass(Pass *MP, const PassInfo *PI, Function &F); 220 221 virtual const char *getPassName() const { 222 return "Module Pass Manager"; 223 } 224 225 // Print passes managed by this manager 226 void dumpPassStructure(unsigned Offset) { 227 llvm::cerr << std::string(Offset*2, ' ') << "ModulePass Manager\n"; 228 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 229 ModulePass *MP = getContainedPass(Index); 230 MP->dumpPassStructure(Offset + 1); 231 if (FunctionPassManagerImpl *FPP = OnTheFlyManagers[MP]) 232 FPP->dumpPassStructure(Offset + 2); 233 dumpLastUses(MP, Offset+1); 234 } 235 } 236 237 ModulePass *getContainedPass(unsigned N) { 238 assert ( N < PassVector.size() && "Pass number out of range!"); 239 ModulePass *MP = static_cast<ModulePass *>(PassVector[N]); 240 return MP; 241 } 242 243 virtual PassManagerType getPassManagerType() const { 244 return PMT_ModulePassManager; 245 } 246 247 private: 248 /// Collection of on the fly FPPassManagers. These managers manage 249 /// function passes that are required by module passes. 250 std::map<Pass *, FunctionPassManagerImpl *> OnTheFlyManagers; 251}; 252 253char MPPassManager::ID = 0; 254//===----------------------------------------------------------------------===// 255// PassManagerImpl 256// 257 258/// PassManagerImpl manages MPPassManagers 259class PassManagerImpl : public Pass, 260 public PMDataManager, 261 public PMTopLevelManager { 262 263public: 264 static char ID; 265 explicit PassManagerImpl(int Depth) : 266 Pass((intptr_t)&ID), PMDataManager(Depth), 267 PMTopLevelManager(TLM_Pass) { } 268 269 /// add - Add a pass to the queue of passes to run. This passes ownership of 270 /// the Pass to the PassManager. When the PassManager is destroyed, the pass 271 /// will be destroyed as well, so there is no need to delete the pass. This 272 /// implies that all passes MUST be allocated with 'new'. 273 void add(Pass *P) { 274 schedulePass(P); 275 } 276 277 /// run - Execute all of the passes scheduled for execution. Keep track of 278 /// whether any of the passes modifies the module, and if so, return true. 279 bool run(Module &M); 280 281 /// Pass Manager itself does not invalidate any analysis info. 282 void getAnalysisUsage(AnalysisUsage &Info) const { 283 Info.setPreservesAll(); 284 } 285 286 inline void addTopLevelPass(Pass *P) { 287 288 if (ImmutablePass *IP = dynamic_cast<ImmutablePass *> (P)) { 289 290 // P is a immutable pass and it will be managed by this 291 // top level manager. Set up analysis resolver to connect them. 292 AnalysisResolver *AR = new AnalysisResolver(*this); 293 P->setResolver(AR); 294 initializeAnalysisImpl(P); 295 addImmutablePass(IP); 296 recordAvailableAnalysis(IP); 297 } else { 298 P->assignPassManager(activeStack); 299 } 300 301 } 302 303 MPPassManager *getContainedManager(unsigned N) { 304 assert ( N < PassManagers.size() && "Pass number out of range!"); 305 MPPassManager *MP = static_cast<MPPassManager *>(PassManagers[N]); 306 return MP; 307 } 308 309}; 310 311char PassManagerImpl::ID = 0; 312} // End of llvm namespace 313 314namespace { 315 316//===----------------------------------------------------------------------===// 317// TimingInfo Class - This class is used to calculate information about the 318// amount of time each pass takes to execute. This only happens when 319// -time-passes is enabled on the command line. 320// 321 322class VISIBILITY_HIDDEN TimingInfo { 323 std::map<Pass*, Timer> TimingData; 324 TimerGroup TG; 325 326public: 327 // Use 'create' member to get this. 328 TimingInfo() : TG("... Pass execution timing report ...") {} 329 330 // TimingDtor - Print out information about timing information 331 ~TimingInfo() { 332 // Delete all of the timers... 333 TimingData.clear(); 334 // TimerGroup is deleted next, printing the report. 335 } 336 337 // createTheTimeInfo - This method either initializes the TheTimeInfo pointer 338 // to a non null value (if the -time-passes option is enabled) or it leaves it 339 // null. It may be called multiple times. 340 static void createTheTimeInfo(); 341 342 void passStarted(Pass *P) { 343 344 if (dynamic_cast<PMDataManager *>(P)) 345 return; 346 347 std::map<Pass*, Timer>::iterator I = TimingData.find(P); 348 if (I == TimingData.end()) 349 I=TimingData.insert(std::make_pair(P, Timer(P->getPassName(), TG))).first; 350 I->second.startTimer(); 351 } 352 void passEnded(Pass *P) { 353 354 if (dynamic_cast<PMDataManager *>(P)) 355 return; 356 357 std::map<Pass*, Timer>::iterator I = TimingData.find(P); 358 assert (I != TimingData.end() && "passStarted/passEnded not nested right!"); 359 I->second.stopTimer(); 360 } 361}; 362 363} // End of anon namespace 364 365static TimingInfo *TheTimeInfo; 366 367//===----------------------------------------------------------------------===// 368// PMTopLevelManager implementation 369 370/// Initialize top level manager. Create first pass manager. 371PMTopLevelManager::PMTopLevelManager (enum TopLevelManagerType t) { 372 373 if (t == TLM_Pass) { 374 MPPassManager *MPP = new MPPassManager(1); 375 MPP->setTopLevelManager(this); 376 addPassManager(MPP); 377 activeStack.push(MPP); 378 } 379 else if (t == TLM_Function) { 380 FPPassManager *FPP = new FPPassManager(1); 381 FPP->setTopLevelManager(this); 382 addPassManager(FPP); 383 activeStack.push(FPP); 384 } 385} 386 387/// Set pass P as the last user of the given analysis passes. 388void PMTopLevelManager::setLastUser(SmallVector<Pass *, 12> &AnalysisPasses, 389 Pass *P) { 390 391 for (SmallVector<Pass *, 12>::iterator I = AnalysisPasses.begin(), 392 E = AnalysisPasses.end(); I != E; ++I) { 393 Pass *AP = *I; 394 LastUser[AP] = P; 395 396 if (P == AP) 397 continue; 398 399 // If AP is the last user of other passes then make P last user of 400 // such passes. 401 for (std::map<Pass *, Pass *>::iterator LUI = LastUser.begin(), 402 LUE = LastUser.end(); LUI != LUE; ++LUI) { 403 if (LUI->second == AP) 404 LastUser[LUI->first] = P; 405 } 406 } 407} 408 409/// Collect passes whose last user is P 410void PMTopLevelManager::collectLastUses(SmallVector<Pass *, 12> &LastUses, 411 Pass *P) { 412 for (std::map<Pass *, Pass *>::iterator LUI = LastUser.begin(), 413 LUE = LastUser.end(); LUI != LUE; ++LUI) 414 if (LUI->second == P) 415 LastUses.push_back(LUI->first); 416} 417 418/// Schedule pass P for execution. Make sure that passes required by 419/// P are run before P is run. Update analysis info maintained by 420/// the manager. Remove dead passes. This is a recursive function. 421void PMTopLevelManager::schedulePass(Pass *P) { 422 423 // TODO : Allocate function manager for this pass, other wise required set 424 // may be inserted into previous function manager 425 426 // Give pass a chance to prepare the stage. 427 P->preparePassManager(activeStack); 428 429 // If P is an analysis pass and it is available then do not 430 // generate the analysis again. Stale analysis info should not be 431 // available at this point. 432 if (P->getPassInfo() && 433 P->getPassInfo()->isAnalysis() && findAnalysisPass(P->getPassInfo())) 434 return; 435 436 AnalysisUsage AnUsage; 437 P->getAnalysisUsage(AnUsage); 438 const std::vector<AnalysisID> &RequiredSet = AnUsage.getRequiredSet(); 439 for (std::vector<AnalysisID>::const_iterator I = RequiredSet.begin(), 440 E = RequiredSet.end(); I != E; ++I) { 441 442 Pass *AnalysisPass = findAnalysisPass(*I); 443 if (!AnalysisPass) { 444 AnalysisPass = (*I)->createPass(); 445 // Schedule this analysis run first only if it is not a lower level 446 // analysis pass. Lower level analsyis passes are run on the fly. 447 if (P->getPotentialPassManagerType () >= 448 AnalysisPass->getPotentialPassManagerType()) 449 schedulePass(AnalysisPass); 450 else 451 delete AnalysisPass; 452 } 453 } 454 455 // Now all required passes are available. 456 addTopLevelPass(P); 457} 458 459/// Find the pass that implements Analysis AID. Search immutable 460/// passes and all pass managers. If desired pass is not found 461/// then return NULL. 462Pass *PMTopLevelManager::findAnalysisPass(AnalysisID AID) { 463 464 Pass *P = NULL; 465 // Check pass managers 466 for (std::vector<PMDataManager *>::iterator I = PassManagers.begin(), 467 E = PassManagers.end(); P == NULL && I != E; ++I) { 468 PMDataManager *PMD = *I; 469 P = PMD->findAnalysisPass(AID, false); 470 } 471 472 // Check other pass managers 473 for (std::vector<PMDataManager *>::iterator I = IndirectPassManagers.begin(), 474 E = IndirectPassManagers.end(); P == NULL && I != E; ++I) 475 P = (*I)->findAnalysisPass(AID, false); 476 477 for (std::vector<ImmutablePass *>::iterator I = ImmutablePasses.begin(), 478 E = ImmutablePasses.end(); P == NULL && I != E; ++I) { 479 const PassInfo *PI = (*I)->getPassInfo(); 480 if (PI == AID) 481 P = *I; 482 483 // If Pass not found then check the interfaces implemented by Immutable Pass 484 if (!P) { 485 const std::vector<const PassInfo*> &ImmPI = 486 PI->getInterfacesImplemented(); 487 if (std::find(ImmPI.begin(), ImmPI.end(), AID) != ImmPI.end()) 488 P = *I; 489 } 490 } 491 492 return P; 493} 494 495// Print passes managed by this top level manager. 496void PMTopLevelManager::dumpPasses() const { 497 498 if (PassDebugging < Structure) 499 return; 500 501 // Print out the immutable passes 502 for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i) { 503 ImmutablePasses[i]->dumpPassStructure(0); 504 } 505 506 // Every class that derives from PMDataManager also derives from Pass 507 // (sometimes indirectly), but there's no inheritance relationship 508 // between PMDataManager and Pass, so we have to dynamic_cast to get 509 // from a PMDataManager* to a Pass*. 510 for (std::vector<PMDataManager *>::const_iterator I = PassManagers.begin(), 511 E = PassManagers.end(); I != E; ++I) 512 dynamic_cast<Pass *>(*I)->dumpPassStructure(1); 513} 514 515void PMTopLevelManager::dumpArguments() const { 516 517 if (PassDebugging < Arguments) 518 return; 519 520 cerr << "Pass Arguments: "; 521 for (std::vector<PMDataManager *>::const_iterator I = PassManagers.begin(), 522 E = PassManagers.end(); I != E; ++I) { 523 PMDataManager *PMD = *I; 524 PMD->dumpPassArguments(); 525 } 526 cerr << "\n"; 527} 528 529void PMTopLevelManager::initializeAllAnalysisInfo() { 530 531 for (std::vector<PMDataManager *>::iterator I = PassManagers.begin(), 532 E = PassManagers.end(); I != E; ++I) { 533 PMDataManager *PMD = *I; 534 PMD->initializeAnalysisInfo(); 535 } 536 537 // Initailize other pass managers 538 for (std::vector<PMDataManager *>::iterator I = IndirectPassManagers.begin(), 539 E = IndirectPassManagers.end(); I != E; ++I) 540 (*I)->initializeAnalysisInfo(); 541} 542 543/// Destructor 544PMTopLevelManager::~PMTopLevelManager() { 545 for (std::vector<PMDataManager *>::iterator I = PassManagers.begin(), 546 E = PassManagers.end(); I != E; ++I) 547 delete *I; 548 549 for (std::vector<ImmutablePass *>::iterator 550 I = ImmutablePasses.begin(), E = ImmutablePasses.end(); I != E; ++I) 551 delete *I; 552} 553 554//===----------------------------------------------------------------------===// 555// PMDataManager implementation 556 557/// Augement AvailableAnalysis by adding analysis made available by pass P. 558void PMDataManager::recordAvailableAnalysis(Pass *P) { 559 560 if (const PassInfo *PI = P->getPassInfo()) { 561 AvailableAnalysis[PI] = P; 562 563 //This pass is the current implementation of all of the interfaces it 564 //implements as well. 565 const std::vector<const PassInfo*> &II = PI->getInterfacesImplemented(); 566 for (unsigned i = 0, e = II.size(); i != e; ++i) 567 AvailableAnalysis[II[i]] = P; 568 } 569} 570 571// Return true if P preserves high level analysis used by other 572// passes managed by this manager 573bool PMDataManager::preserveHigherLevelAnalysis(Pass *P) { 574 575 AnalysisUsage AnUsage; 576 P->getAnalysisUsage(AnUsage); 577 578 if (AnUsage.getPreservesAll()) 579 return true; 580 581 const std::vector<AnalysisID> &PreservedSet = AnUsage.getPreservedSet(); 582 for (std::vector<Pass *>::iterator I = HigherLevelAnalysis.begin(), 583 E = HigherLevelAnalysis.end(); I != E; ++I) { 584 Pass *P1 = *I; 585 if (!dynamic_cast<ImmutablePass*>(P1) && 586 std::find(PreservedSet.begin(), PreservedSet.end(), 587 P1->getPassInfo()) == 588 PreservedSet.end()) 589 return false; 590 } 591 592 return true; 593} 594 595/// verifyPreservedAnalysis -- Verify analysis presreved by pass P. 596void PMDataManager::verifyPreservedAnalysis(Pass *P) { 597 AnalysisUsage AnUsage; 598 P->getAnalysisUsage(AnUsage); 599 const std::vector<AnalysisID> &PreservedSet = AnUsage.getPreservedSet(); 600 601 // Verify preserved analysis 602 for (std::vector<AnalysisID>::const_iterator I = PreservedSet.begin(), 603 E = PreservedSet.end(); I != E; ++I) { 604 AnalysisID AID = *I; 605 Pass *AP = findAnalysisPass(AID, true); 606 if (AP) 607 AP->verifyAnalysis(); 608 } 609} 610 611/// Remove Analyss not preserved by Pass P 612void PMDataManager::removeNotPreservedAnalysis(Pass *P) { 613 AnalysisUsage AnUsage; 614 P->getAnalysisUsage(AnUsage); 615 if (AnUsage.getPreservesAll()) 616 return; 617 618 const std::vector<AnalysisID> &PreservedSet = AnUsage.getPreservedSet(); 619 for (std::map<AnalysisID, Pass*>::iterator I = AvailableAnalysis.begin(), 620 E = AvailableAnalysis.end(); I != E; ) { 621 std::map<AnalysisID, Pass*>::iterator Info = I++; 622 if (!dynamic_cast<ImmutablePass*>(Info->second) 623 && std::find(PreservedSet.begin(), PreservedSet.end(), Info->first) == 624 PreservedSet.end()) 625 // Remove this analysis 626 AvailableAnalysis.erase(Info); 627 } 628 629 // Check inherited analysis also. If P is not preserving analysis 630 // provided by parent manager then remove it here. 631 for (unsigned Index = 0; Index < PMT_Last; ++Index) { 632 633 if (!InheritedAnalysis[Index]) 634 continue; 635 636 for (std::map<AnalysisID, Pass*>::iterator 637 I = InheritedAnalysis[Index]->begin(), 638 E = InheritedAnalysis[Index]->end(); I != E; ) { 639 std::map<AnalysisID, Pass *>::iterator Info = I++; 640 if (!dynamic_cast<ImmutablePass*>(Info->second) && 641 std::find(PreservedSet.begin(), PreservedSet.end(), Info->first) == 642 PreservedSet.end()) 643 // Remove this analysis 644 InheritedAnalysis[Index]->erase(Info); 645 } 646 } 647 648} 649 650/// Remove analysis passes that are not used any longer 651void PMDataManager::removeDeadPasses(Pass *P, const char *Msg, 652 enum PassDebuggingString DBG_STR) { 653 654 SmallVector<Pass *, 12> DeadPasses; 655 656 // If this is a on the fly manager then it does not have TPM. 657 if (!TPM) 658 return; 659 660 TPM->collectLastUses(DeadPasses, P); 661 662 for (SmallVector<Pass *, 12>::iterator I = DeadPasses.begin(), 663 E = DeadPasses.end(); I != E; ++I) { 664 665 dumpPassInfo(*I, FREEING_MSG, DBG_STR, Msg); 666 667 if (TheTimeInfo) TheTimeInfo->passStarted(*I); 668 (*I)->releaseMemory(); 669 if (TheTimeInfo) TheTimeInfo->passEnded(*I); 670 671 std::map<AnalysisID, Pass*>::iterator Pos = 672 AvailableAnalysis.find((*I)->getPassInfo()); 673 674 // It is possible that pass is already removed from the AvailableAnalysis 675 if (Pos != AvailableAnalysis.end()) 676 AvailableAnalysis.erase(Pos); 677 } 678} 679 680/// Add pass P into the PassVector. Update 681/// AvailableAnalysis appropriately if ProcessAnalysis is true. 682void PMDataManager::add(Pass *P, 683 bool ProcessAnalysis) { 684 685 // This manager is going to manage pass P. Set up analysis resolver 686 // to connect them. 687 AnalysisResolver *AR = new AnalysisResolver(*this); 688 P->setResolver(AR); 689 690 // If a FunctionPass F is the last user of ModulePass info M 691 // then the F's manager, not F, records itself as a last user of M. 692 SmallVector<Pass *, 12> TransferLastUses; 693 694 if (ProcessAnalysis) { 695 696 // At the moment, this pass is the last user of all required passes. 697 SmallVector<Pass *, 12> LastUses; 698 SmallVector<Pass *, 8> RequiredPasses; 699 SmallVector<AnalysisID, 8> ReqAnalysisNotAvailable; 700 701 unsigned PDepth = this->getDepth(); 702 703 collectRequiredAnalysis(RequiredPasses, 704 ReqAnalysisNotAvailable, P); 705 for (SmallVector<Pass *, 8>::iterator I = RequiredPasses.begin(), 706 E = RequiredPasses.end(); I != E; ++I) { 707 Pass *PRequired = *I; 708 unsigned RDepth = 0; 709 710 PMDataManager &DM = PRequired->getResolver()->getPMDataManager(); 711 RDepth = DM.getDepth(); 712 713 if (PDepth == RDepth) 714 LastUses.push_back(PRequired); 715 else if (PDepth > RDepth) { 716 // Let the parent claim responsibility of last use 717 TransferLastUses.push_back(PRequired); 718 // Keep track of higher level analysis used by this manager. 719 HigherLevelAnalysis.push_back(PRequired); 720 } else 721 assert (0 && "Unable to accomodate Required Pass"); 722 } 723 724 // Set P as P's last user until someone starts using P. 725 // However, if P is a Pass Manager then it does not need 726 // to record its last user. 727 if (!dynamic_cast<PMDataManager *>(P)) 728 LastUses.push_back(P); 729 TPM->setLastUser(LastUses, P); 730 731 if (!TransferLastUses.empty()) { 732 Pass *My_PM = dynamic_cast<Pass *>(this); 733 TPM->setLastUser(TransferLastUses, My_PM); 734 TransferLastUses.clear(); 735 } 736 737 // Now, take care of required analysises that are not available. 738 for (SmallVector<AnalysisID, 8>::iterator 739 I = ReqAnalysisNotAvailable.begin(), 740 E = ReqAnalysisNotAvailable.end() ;I != E; ++I) { 741 Pass *AnalysisPass = (*I)->createPass(); 742 this->addLowerLevelRequiredPass(P, AnalysisPass); 743 } 744 745 // Take a note of analysis required and made available by this pass. 746 // Remove the analysis not preserved by this pass 747 removeNotPreservedAnalysis(P); 748 recordAvailableAnalysis(P); 749 } 750 751 // Add pass 752 PassVector.push_back(P); 753} 754 755 756/// Populate RP with analysis pass that are required by 757/// pass P and are available. Populate RP_NotAvail with analysis 758/// pass that are required by pass P but are not available. 759void PMDataManager::collectRequiredAnalysis(SmallVector<Pass *, 8>&RP, 760 SmallVector<AnalysisID, 8> &RP_NotAvail, 761 Pass *P) { 762 AnalysisUsage AnUsage; 763 P->getAnalysisUsage(AnUsage); 764 const std::vector<AnalysisID> &RequiredSet = AnUsage.getRequiredSet(); 765 for (std::vector<AnalysisID>::const_iterator 766 I = RequiredSet.begin(), E = RequiredSet.end(); 767 I != E; ++I) { 768 AnalysisID AID = *I; 769 if (Pass *AnalysisPass = findAnalysisPass(*I, true)) 770 RP.push_back(AnalysisPass); 771 else 772 RP_NotAvail.push_back(AID); 773 } 774 775 const std::vector<AnalysisID> &IDs = AnUsage.getRequiredTransitiveSet(); 776 for (std::vector<AnalysisID>::const_iterator I = IDs.begin(), 777 E = IDs.end(); I != E; ++I) { 778 AnalysisID AID = *I; 779 if (Pass *AnalysisPass = findAnalysisPass(*I, true)) 780 RP.push_back(AnalysisPass); 781 else 782 RP_NotAvail.push_back(AID); 783 } 784} 785 786// All Required analyses should be available to the pass as it runs! Here 787// we fill in the AnalysisImpls member of the pass so that it can 788// successfully use the getAnalysis() method to retrieve the 789// implementations it needs. 790// 791void PMDataManager::initializeAnalysisImpl(Pass *P) { 792 AnalysisUsage AnUsage; 793 P->getAnalysisUsage(AnUsage); 794 795 for (std::vector<const PassInfo *>::const_iterator 796 I = AnUsage.getRequiredSet().begin(), 797 E = AnUsage.getRequiredSet().end(); I != E; ++I) { 798 Pass *Impl = findAnalysisPass(*I, true); 799 if (Impl == 0) 800 // This may be analysis pass that is initialized on the fly. 801 // If that is not the case then it will raise an assert when it is used. 802 continue; 803 AnalysisResolver *AR = P->getResolver(); 804 AR->addAnalysisImplsPair(*I, Impl); 805 } 806} 807 808/// Find the pass that implements Analysis AID. If desired pass is not found 809/// then return NULL. 810Pass *PMDataManager::findAnalysisPass(AnalysisID AID, bool SearchParent) { 811 812 // Check if AvailableAnalysis map has one entry. 813 std::map<AnalysisID, Pass*>::const_iterator I = AvailableAnalysis.find(AID); 814 815 if (I != AvailableAnalysis.end()) 816 return I->second; 817 818 // Search Parents through TopLevelManager 819 if (SearchParent) 820 return TPM->findAnalysisPass(AID); 821 822 return NULL; 823} 824 825// Print list of passes that are last used by P. 826void PMDataManager::dumpLastUses(Pass *P, unsigned Offset) const{ 827 828 SmallVector<Pass *, 12> LUses; 829 830 // If this is a on the fly manager then it does not have TPM. 831 if (!TPM) 832 return; 833 834 TPM->collectLastUses(LUses, P); 835 836 for (SmallVector<Pass *, 12>::iterator I = LUses.begin(), 837 E = LUses.end(); I != E; ++I) { 838 llvm::cerr << "--" << std::string(Offset*2, ' '); 839 (*I)->dumpPassStructure(0); 840 } 841} 842 843void PMDataManager::dumpPassArguments() const { 844 for(std::vector<Pass *>::const_iterator I = PassVector.begin(), 845 E = PassVector.end(); I != E; ++I) { 846 if (PMDataManager *PMD = dynamic_cast<PMDataManager *>(*I)) 847 PMD->dumpPassArguments(); 848 else 849 if (const PassInfo *PI = (*I)->getPassInfo()) 850 if (!PI->isAnalysisGroup()) 851 cerr << " -" << PI->getPassArgument(); 852 } 853} 854 855void PMDataManager::dumpPassInfo(Pass *P, enum PassDebuggingString S1, 856 enum PassDebuggingString S2, 857 const char *Msg) { 858 if (PassDebugging < Executions) 859 return; 860 cerr << (void*)this << std::string(getDepth()*2+1, ' '); 861 switch (S1) { 862 case EXECUTION_MSG: 863 cerr << "Executing Pass '" << P->getPassName(); 864 break; 865 case MODIFICATION_MSG: 866 cerr << "Made Modification '" << P->getPassName(); 867 break; 868 case FREEING_MSG: 869 cerr << " Freeing Pass '" << P->getPassName(); 870 break; 871 default: 872 break; 873 } 874 switch (S2) { 875 case ON_BASICBLOCK_MSG: 876 cerr << "' on BasicBlock '" << Msg << "'...\n"; 877 break; 878 case ON_FUNCTION_MSG: 879 cerr << "' on Function '" << Msg << "'...\n"; 880 break; 881 case ON_MODULE_MSG: 882 cerr << "' on Module '" << Msg << "'...\n"; 883 break; 884 case ON_LOOP_MSG: 885 cerr << "' on Loop " << Msg << "'...\n"; 886 break; 887 case ON_CG_MSG: 888 cerr << "' on Call Graph " << Msg << "'...\n"; 889 break; 890 default: 891 break; 892 } 893} 894 895void PMDataManager::dumpAnalysisSetInfo(const char *Msg, Pass *P, 896 const std::vector<AnalysisID> &Set) 897 const { 898 if (PassDebugging >= Details && !Set.empty()) { 899 cerr << (void*)P << std::string(getDepth()*2+3, ' ') << Msg << " Analyses:"; 900 for (unsigned i = 0; i != Set.size(); ++i) { 901 if (i) cerr << ","; 902 cerr << " " << Set[i]->getPassName(); 903 } 904 cerr << "\n"; 905 } 906} 907 908/// Add RequiredPass into list of lower level passes required by pass P. 909/// RequiredPass is run on the fly by Pass Manager when P requests it 910/// through getAnalysis interface. 911/// This should be handled by specific pass manager. 912void PMDataManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) { 913 if (TPM) { 914 TPM->dumpArguments(); 915 TPM->dumpPasses(); 916 } 917 918 // Module Level pass may required Function Level analysis info 919 // (e.g. dominator info). Pass manager uses on the fly function pass manager 920 // to provide this on demand. In that case, in Pass manager terminology, 921 // module level pass is requiring lower level analysis info managed by 922 // lower level pass manager. 923 924 // When Pass manager is not able to order required analysis info, Pass manager 925 // checks whether any lower level manager will be able to provide this 926 // analysis info on demand or not. 927 assert (0 && "Unable to handle Pass that requires lower level Analysis pass"); 928} 929 930// Destructor 931PMDataManager::~PMDataManager() { 932 933 for (std::vector<Pass *>::iterator I = PassVector.begin(), 934 E = PassVector.end(); I != E; ++I) 935 delete *I; 936 937} 938 939//===----------------------------------------------------------------------===// 940// NOTE: Is this the right place to define this method ? 941// getAnalysisToUpdate - Return an analysis result or null if it doesn't exist 942Pass *AnalysisResolver::getAnalysisToUpdate(AnalysisID ID, bool dir) const { 943 return PM.findAnalysisPass(ID, dir); 944} 945 946Pass *AnalysisResolver::findImplPass(Pass *P, const PassInfo *AnalysisPI, 947 Function &F) { 948 return PM.getOnTheFlyPass(P, AnalysisPI, F); 949} 950 951//===----------------------------------------------------------------------===// 952// BBPassManager implementation 953 954/// Execute all of the passes scheduled for execution by invoking 955/// runOnBasicBlock method. Keep track of whether any of the passes modifies 956/// the function, and if so, return true. 957bool 958BBPassManager::runOnFunction(Function &F) { 959 960 if (F.isDeclaration()) 961 return false; 962 963 bool Changed = doInitialization(F); 964 965 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 966 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 967 BasicBlockPass *BP = getContainedPass(Index); 968 AnalysisUsage AnUsage; 969 BP->getAnalysisUsage(AnUsage); 970 971 dumpPassInfo(BP, EXECUTION_MSG, ON_BASICBLOCK_MSG, I->getNameStart()); 972 dumpAnalysisSetInfo("Required", BP, AnUsage.getRequiredSet()); 973 974 initializeAnalysisImpl(BP); 975 976 if (TheTimeInfo) TheTimeInfo->passStarted(BP); 977 Changed |= BP->runOnBasicBlock(*I); 978 if (TheTimeInfo) TheTimeInfo->passEnded(BP); 979 980 if (Changed) 981 dumpPassInfo(BP, MODIFICATION_MSG, ON_BASICBLOCK_MSG, 982 I->getNameStart()); 983 dumpAnalysisSetInfo("Preserved", BP, AnUsage.getPreservedSet()); 984 985 verifyPreservedAnalysis(BP); 986 removeNotPreservedAnalysis(BP); 987 recordAvailableAnalysis(BP); 988 removeDeadPasses(BP, I->getNameStart(), ON_BASICBLOCK_MSG); 989 } 990 991 return Changed |= doFinalization(F); 992} 993 994// Implement doInitialization and doFinalization 995inline bool BBPassManager::doInitialization(Module &M) { 996 bool Changed = false; 997 998 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 999 BasicBlockPass *BP = getContainedPass(Index); 1000 Changed |= BP->doInitialization(M); 1001 } 1002 1003 return Changed; 1004} 1005 1006inline bool BBPassManager::doFinalization(Module &M) { 1007 bool Changed = false; 1008 1009 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 1010 BasicBlockPass *BP = getContainedPass(Index); 1011 Changed |= BP->doFinalization(M); 1012 } 1013 1014 return Changed; 1015} 1016 1017inline bool BBPassManager::doInitialization(Function &F) { 1018 bool Changed = false; 1019 1020 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 1021 BasicBlockPass *BP = getContainedPass(Index); 1022 Changed |= BP->doInitialization(F); 1023 } 1024 1025 return Changed; 1026} 1027 1028inline bool BBPassManager::doFinalization(Function &F) { 1029 bool Changed = false; 1030 1031 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 1032 BasicBlockPass *BP = getContainedPass(Index); 1033 Changed |= BP->doFinalization(F); 1034 } 1035 1036 return Changed; 1037} 1038 1039 1040//===----------------------------------------------------------------------===// 1041// FunctionPassManager implementation 1042 1043/// Create new Function pass manager 1044FunctionPassManager::FunctionPassManager(ModuleProvider *P) { 1045 FPM = new FunctionPassManagerImpl(0); 1046 // FPM is the top level manager. 1047 FPM->setTopLevelManager(FPM); 1048 1049 AnalysisResolver *AR = new AnalysisResolver(*FPM); 1050 FPM->setResolver(AR); 1051 1052 MP = P; 1053} 1054 1055FunctionPassManager::~FunctionPassManager() { 1056 delete FPM; 1057} 1058 1059/// add - Add a pass to the queue of passes to run. This passes 1060/// ownership of the Pass to the PassManager. When the 1061/// PassManager_X is destroyed, the pass will be destroyed as well, so 1062/// there is no need to delete the pass. (TODO delete passes.) 1063/// This implies that all passes MUST be allocated with 'new'. 1064void FunctionPassManager::add(Pass *P) { 1065 FPM->add(P); 1066} 1067 1068/// run - Execute all of the passes scheduled for execution. Keep 1069/// track of whether any of the passes modifies the function, and if 1070/// so, return true. 1071/// 1072bool FunctionPassManager::run(Function &F) { 1073 std::string errstr; 1074 if (MP->materializeFunction(&F, &errstr)) { 1075 cerr << "Error reading bitcode file: " << errstr << "\n"; 1076 abort(); 1077 } 1078 return FPM->run(F); 1079} 1080 1081 1082/// doInitialization - Run all of the initializers for the function passes. 1083/// 1084bool FunctionPassManager::doInitialization() { 1085 return FPM->doInitialization(*MP->getModule()); 1086} 1087 1088/// doFinalization - Run all of the finalizers for the function passes. 1089/// 1090bool FunctionPassManager::doFinalization() { 1091 return FPM->doFinalization(*MP->getModule()); 1092} 1093 1094//===----------------------------------------------------------------------===// 1095// FunctionPassManagerImpl implementation 1096// 1097inline bool FunctionPassManagerImpl::doInitialization(Module &M) { 1098 bool Changed = false; 1099 1100 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) { 1101 FPPassManager *FP = getContainedManager(Index); 1102 Changed |= FP->doInitialization(M); 1103 } 1104 1105 return Changed; 1106} 1107 1108inline bool FunctionPassManagerImpl::doFinalization(Module &M) { 1109 bool Changed = false; 1110 1111 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) { 1112 FPPassManager *FP = getContainedManager(Index); 1113 Changed |= FP->doFinalization(M); 1114 } 1115 1116 return Changed; 1117} 1118 1119// Execute all the passes managed by this top level manager. 1120// Return true if any function is modified by a pass. 1121bool FunctionPassManagerImpl::run(Function &F) { 1122 1123 bool Changed = false; 1124 1125 TimingInfo::createTheTimeInfo(); 1126 1127 dumpArguments(); 1128 dumpPasses(); 1129 1130 initializeAllAnalysisInfo(); 1131 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) { 1132 FPPassManager *FP = getContainedManager(Index); 1133 Changed |= FP->runOnFunction(F); 1134 } 1135 return Changed; 1136} 1137 1138//===----------------------------------------------------------------------===// 1139// FPPassManager implementation 1140 1141char FPPassManager::ID = 0; 1142/// Print passes managed by this manager 1143void FPPassManager::dumpPassStructure(unsigned Offset) { 1144 llvm::cerr << std::string(Offset*2, ' ') << "FunctionPass Manager\n"; 1145 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 1146 FunctionPass *FP = getContainedPass(Index); 1147 FP->dumpPassStructure(Offset + 1); 1148 dumpLastUses(FP, Offset+1); 1149 } 1150} 1151 1152 1153/// Execute all of the passes scheduled for execution by invoking 1154/// runOnFunction method. Keep track of whether any of the passes modifies 1155/// the function, and if so, return true. 1156bool FPPassManager::runOnFunction(Function &F) { 1157 1158 bool Changed = false; 1159 1160 if (F.isDeclaration()) 1161 return false; 1162 1163 // Collect inherited analysis from Module level pass manager. 1164 populateInheritedAnalysis(TPM->activeStack); 1165 1166 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 1167 FunctionPass *FP = getContainedPass(Index); 1168 1169 AnalysisUsage AnUsage; 1170 FP->getAnalysisUsage(AnUsage); 1171 1172 dumpPassInfo(FP, EXECUTION_MSG, ON_FUNCTION_MSG, F.getNameStart()); 1173 dumpAnalysisSetInfo("Required", FP, AnUsage.getRequiredSet()); 1174 1175 initializeAnalysisImpl(FP); 1176 1177 if (TheTimeInfo) TheTimeInfo->passStarted(FP); 1178 Changed |= FP->runOnFunction(F); 1179 if (TheTimeInfo) TheTimeInfo->passEnded(FP); 1180 1181 if (Changed) 1182 dumpPassInfo(FP, MODIFICATION_MSG, ON_FUNCTION_MSG, F.getNameStart()); 1183 dumpAnalysisSetInfo("Preserved", FP, AnUsage.getPreservedSet()); 1184 1185 verifyPreservedAnalysis(FP); 1186 removeNotPreservedAnalysis(FP); 1187 recordAvailableAnalysis(FP); 1188 removeDeadPasses(FP, F.getNameStart(), ON_FUNCTION_MSG); 1189 } 1190 return Changed; 1191} 1192 1193bool FPPassManager::runOnModule(Module &M) { 1194 1195 bool Changed = doInitialization(M); 1196 1197 for(Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 1198 this->runOnFunction(*I); 1199 1200 return Changed |= doFinalization(M); 1201} 1202 1203inline bool FPPassManager::doInitialization(Module &M) { 1204 bool Changed = false; 1205 1206 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 1207 FunctionPass *FP = getContainedPass(Index); 1208 Changed |= FP->doInitialization(M); 1209 } 1210 1211 return Changed; 1212} 1213 1214inline bool FPPassManager::doFinalization(Module &M) { 1215 bool Changed = false; 1216 1217 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 1218 FunctionPass *FP = getContainedPass(Index); 1219 Changed |= FP->doFinalization(M); 1220 } 1221 1222 return Changed; 1223} 1224 1225//===----------------------------------------------------------------------===// 1226// MPPassManager implementation 1227 1228/// Execute all of the passes scheduled for execution by invoking 1229/// runOnModule method. Keep track of whether any of the passes modifies 1230/// the module, and if so, return true. 1231bool 1232MPPassManager::runOnModule(Module &M) { 1233 bool Changed = false; 1234 1235 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 1236 ModulePass *MP = getContainedPass(Index); 1237 1238 AnalysisUsage AnUsage; 1239 MP->getAnalysisUsage(AnUsage); 1240 1241 dumpPassInfo(MP, EXECUTION_MSG, ON_MODULE_MSG, 1242 M.getModuleIdentifier().c_str()); 1243 dumpAnalysisSetInfo("Required", MP, AnUsage.getRequiredSet()); 1244 1245 initializeAnalysisImpl(MP); 1246 1247 if (TheTimeInfo) TheTimeInfo->passStarted(MP); 1248 Changed |= MP->runOnModule(M); 1249 if (TheTimeInfo) TheTimeInfo->passEnded(MP); 1250 1251 if (Changed) 1252 dumpPassInfo(MP, MODIFICATION_MSG, ON_MODULE_MSG, 1253 M.getModuleIdentifier().c_str()); 1254 dumpAnalysisSetInfo("Preserved", MP, AnUsage.getPreservedSet()); 1255 1256 verifyPreservedAnalysis(MP); 1257 removeNotPreservedAnalysis(MP); 1258 recordAvailableAnalysis(MP); 1259 removeDeadPasses(MP, M.getModuleIdentifier().c_str(), ON_MODULE_MSG); 1260 } 1261 return Changed; 1262} 1263 1264/// Add RequiredPass into list of lower level passes required by pass P. 1265/// RequiredPass is run on the fly by Pass Manager when P requests it 1266/// through getAnalysis interface. 1267void MPPassManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) { 1268 1269 assert (P->getPotentialPassManagerType() == PMT_ModulePassManager 1270 && "Unable to handle Pass that requires lower level Analysis pass"); 1271 assert ((P->getPotentialPassManagerType() < 1272 RequiredPass->getPotentialPassManagerType()) 1273 && "Unable to handle Pass that requires lower level Analysis pass"); 1274 1275 FunctionPassManagerImpl *FPP = OnTheFlyManagers[P]; 1276 if (!FPP) { 1277 FPP = new FunctionPassManagerImpl(0); 1278 // FPP is the top level manager. 1279 FPP->setTopLevelManager(FPP); 1280 1281 OnTheFlyManagers[P] = FPP; 1282 } 1283 FPP->add(RequiredPass); 1284 1285 // Register P as the last user of RequiredPass. 1286 SmallVector<Pass *, 12> LU; 1287 LU.push_back(RequiredPass); 1288 FPP->setLastUser(LU, P); 1289} 1290 1291/// Return function pass corresponding to PassInfo PI, that is 1292/// required by module pass MP. Instantiate analysis pass, by using 1293/// its runOnFunction() for function F. 1294Pass* MPPassManager::getOnTheFlyPass(Pass *MP, const PassInfo *PI, 1295 Function &F) { 1296 AnalysisID AID = PI; 1297 FunctionPassManagerImpl *FPP = OnTheFlyManagers[MP]; 1298 assert (FPP && "Unable to find on the fly pass"); 1299 1300 FPP->run(F); 1301 return (dynamic_cast<PMTopLevelManager *>(FPP))->findAnalysisPass(AID); 1302} 1303 1304 1305//===----------------------------------------------------------------------===// 1306// PassManagerImpl implementation 1307// 1308/// run - Execute all of the passes scheduled for execution. Keep track of 1309/// whether any of the passes modifies the module, and if so, return true. 1310bool PassManagerImpl::run(Module &M) { 1311 1312 bool Changed = false; 1313 1314 TimingInfo::createTheTimeInfo(); 1315 1316 dumpArguments(); 1317 dumpPasses(); 1318 1319 initializeAllAnalysisInfo(); 1320 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) { 1321 MPPassManager *MP = getContainedManager(Index); 1322 Changed |= MP->runOnModule(M); 1323 } 1324 return Changed; 1325} 1326 1327//===----------------------------------------------------------------------===// 1328// PassManager implementation 1329 1330/// Create new pass manager 1331PassManager::PassManager() { 1332 PM = new PassManagerImpl(0); 1333 // PM is the top level manager 1334 PM->setTopLevelManager(PM); 1335} 1336 1337PassManager::~PassManager() { 1338 delete PM; 1339} 1340 1341/// add - Add a pass to the queue of passes to run. This passes ownership of 1342/// the Pass to the PassManager. When the PassManager is destroyed, the pass 1343/// will be destroyed as well, so there is no need to delete the pass. This 1344/// implies that all passes MUST be allocated with 'new'. 1345void 1346PassManager::add(Pass *P) { 1347 PM->add(P); 1348} 1349 1350/// run - Execute all of the passes scheduled for execution. Keep track of 1351/// whether any of the passes modifies the module, and if so, return true. 1352bool 1353PassManager::run(Module &M) { 1354 return PM->run(M); 1355} 1356 1357//===----------------------------------------------------------------------===// 1358// TimingInfo Class - This class is used to calculate information about the 1359// amount of time each pass takes to execute. This only happens with 1360// -time-passes is enabled on the command line. 1361// 1362bool llvm::TimePassesIsEnabled = false; 1363static cl::opt<bool,true> 1364EnableTiming("time-passes", cl::location(TimePassesIsEnabled), 1365 cl::desc("Time each pass, printing elapsed time for each on exit")); 1366 1367// createTheTimeInfo - This method either initializes the TheTimeInfo pointer to 1368// a non null value (if the -time-passes option is enabled) or it leaves it 1369// null. It may be called multiple times. 1370void TimingInfo::createTheTimeInfo() { 1371 if (!TimePassesIsEnabled || TheTimeInfo) return; 1372 1373 // Constructed the first time this is called, iff -time-passes is enabled. 1374 // This guarantees that the object will be constructed before static globals, 1375 // thus it will be destroyed before them. 1376 static ManagedStatic<TimingInfo> TTI; 1377 TheTimeInfo = &*TTI; 1378} 1379 1380/// If TimingInfo is enabled then start pass timer. 1381void StartPassTimer(Pass *P) { 1382 if (TheTimeInfo) 1383 TheTimeInfo->passStarted(P); 1384} 1385 1386/// If TimingInfo is enabled then stop pass timer. 1387void StopPassTimer(Pass *P) { 1388 if (TheTimeInfo) 1389 TheTimeInfo->passEnded(P); 1390} 1391 1392//===----------------------------------------------------------------------===// 1393// PMStack implementation 1394// 1395 1396// Pop Pass Manager from the stack and clear its analysis info. 1397void PMStack::pop() { 1398 1399 PMDataManager *Top = this->top(); 1400 Top->initializeAnalysisInfo(); 1401 1402 S.pop_back(); 1403} 1404 1405// Push PM on the stack and set its top level manager. 1406void PMStack::push(PMDataManager *PM) { 1407 1408 PMDataManager *Top = NULL; 1409 assert (PM && "Unable to push. Pass Manager expected"); 1410 1411 if (this->empty()) { 1412 Top = PM; 1413 } 1414 else { 1415 Top = this->top(); 1416 PMTopLevelManager *TPM = Top->getTopLevelManager(); 1417 1418 assert (TPM && "Unable to find top level manager"); 1419 TPM->addIndirectPassManager(PM); 1420 PM->setTopLevelManager(TPM); 1421 } 1422 1423 S.push_back(PM); 1424} 1425 1426// Dump content of the pass manager stack. 1427void PMStack::dump() { 1428 for(std::deque<PMDataManager *>::iterator I = S.begin(), 1429 E = S.end(); I != E; ++I) { 1430 Pass *P = dynamic_cast<Pass *>(*I); 1431 printf("%s ", P->getPassName()); 1432 } 1433 if (!S.empty()) 1434 printf("\n"); 1435} 1436 1437/// Find appropriate Module Pass Manager in the PM Stack and 1438/// add self into that manager. 1439void ModulePass::assignPassManager(PMStack &PMS, 1440 PassManagerType PreferredType) { 1441 1442 // Find Module Pass Manager 1443 while(!PMS.empty()) { 1444 PassManagerType TopPMType = PMS.top()->getPassManagerType(); 1445 if (TopPMType == PreferredType) 1446 break; // We found desired pass manager 1447 else if (TopPMType > PMT_ModulePassManager) 1448 PMS.pop(); // Pop children pass managers 1449 else 1450 break; 1451 } 1452 1453 PMS.top()->add(this); 1454} 1455 1456/// Find appropriate Function Pass Manager or Call Graph Pass Manager 1457/// in the PM Stack and add self into that manager. 1458void FunctionPass::assignPassManager(PMStack &PMS, 1459 PassManagerType PreferredType) { 1460 1461 // Find Module Pass Manager (TODO : Or Call Graph Pass Manager) 1462 while(!PMS.empty()) { 1463 if (PMS.top()->getPassManagerType() > PMT_FunctionPassManager) 1464 PMS.pop(); 1465 else 1466 break; 1467 } 1468 FPPassManager *FPP = dynamic_cast<FPPassManager *>(PMS.top()); 1469 1470 // Create new Function Pass Manager 1471 if (!FPP) { 1472 assert(!PMS.empty() && "Unable to create Function Pass Manager"); 1473 PMDataManager *PMD = PMS.top(); 1474 1475 // [1] Create new Function Pass Manager 1476 FPP = new FPPassManager(PMD->getDepth() + 1); 1477 FPP->populateInheritedAnalysis(PMS); 1478 1479 // [2] Set up new manager's top level manager 1480 PMTopLevelManager *TPM = PMD->getTopLevelManager(); 1481 TPM->addIndirectPassManager(FPP); 1482 1483 // [3] Assign manager to manage this new manager. This may create 1484 // and push new managers into PMS 1485 1486 // If Call Graph Pass Manager is active then use it to manage 1487 // this new Function Pass manager. 1488 if (PMD->getPassManagerType() == PMT_CallGraphPassManager) 1489 FPP->assignPassManager(PMS, PMT_CallGraphPassManager); 1490 else 1491 FPP->assignPassManager(PMS); 1492 1493 // [4] Push new manager into PMS 1494 PMS.push(FPP); 1495 } 1496 1497 // Assign FPP as the manager of this pass. 1498 FPP->add(this); 1499} 1500 1501/// Find appropriate Basic Pass Manager or Call Graph Pass Manager 1502/// in the PM Stack and add self into that manager. 1503void BasicBlockPass::assignPassManager(PMStack &PMS, 1504 PassManagerType PreferredType) { 1505 1506 BBPassManager *BBP = NULL; 1507 1508 // Basic Pass Manager is a leaf pass manager. It does not handle 1509 // any other pass manager. 1510 if (!PMS.empty()) 1511 BBP = dynamic_cast<BBPassManager *>(PMS.top()); 1512 1513 // If leaf manager is not Basic Block Pass manager then create new 1514 // basic Block Pass manager. 1515 1516 if (!BBP) { 1517 assert(!PMS.empty() && "Unable to create BasicBlock Pass Manager"); 1518 PMDataManager *PMD = PMS.top(); 1519 1520 // [1] Create new Basic Block Manager 1521 BBP = new BBPassManager(PMD->getDepth() + 1); 1522 1523 // [2] Set up new manager's top level manager 1524 // Basic Block Pass Manager does not live by itself 1525 PMTopLevelManager *TPM = PMD->getTopLevelManager(); 1526 TPM->addIndirectPassManager(BBP); 1527 1528 // [3] Assign manager to manage this new manager. This may create 1529 // and push new managers into PMS 1530 BBP->assignPassManager(PMS); 1531 1532 // [4] Push new manager into PMS 1533 PMS.push(BBP); 1534 } 1535 1536 // Assign BBP as the manager of this pass. 1537 BBP->add(this); 1538} 1539 1540PassManagerBase::~PassManagerBase() {} 1541 1542/*===-- C Bindings --------------------------------------------------------===*/ 1543 1544LLVMPassManagerRef LLVMCreatePassManager() { 1545 return wrap(new PassManager()); 1546} 1547 1548LLVMPassManagerRef LLVMCreateFunctionPassManager(LLVMModuleProviderRef P) { 1549 return wrap(new FunctionPassManager(unwrap(P))); 1550} 1551 1552int LLVMRunPassManager(LLVMPassManagerRef PM, LLVMModuleRef M) { 1553 return unwrap<PassManager>(PM)->run(*unwrap(M)); 1554} 1555 1556int LLVMInitializeFunctionPassManager(LLVMPassManagerRef FPM) { 1557 return unwrap<FunctionPassManager>(FPM)->doInitialization(); 1558} 1559 1560int LLVMRunFunctionPassManager(LLVMPassManagerRef FPM, LLVMValueRef F) { 1561 return unwrap<FunctionPassManager>(FPM)->run(*unwrap<Function>(F)); 1562} 1563 1564int LLVMFinalizeFunctionPassManager(LLVMPassManagerRef FPM) { 1565 return unwrap<FunctionPassManager>(FPM)->doFinalization(); 1566} 1567 1568void LLVMDisposePassManager(LLVMPassManagerRef PM) { 1569 delete unwrap(PM); 1570} 1571