1 //===- LegacyPassManagers.h - Legacy Pass Infrastructure --------*- C++ -*-===// 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 declares the LLVM Pass Manager infrastructure. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_IR_LEGACYPASSMANAGERS_H 15 #define LLVM_IR_LEGACYPASSMANAGERS_H 16 17 #include "llvm/ADT/DenseMap.h" 18 #include "llvm/ADT/FoldingSet.h" 19 #include "llvm/ADT/SmallPtrSet.h" 20 #include "llvm/ADT/SmallVector.h" 21 #include "llvm/Pass.h" 22 #include <vector> 23 24 //===----------------------------------------------------------------------===// 25 // Overview: 26 // The Pass Manager Infrastructure manages passes. It's responsibilities are: 27 // 28 // o Manage optimization pass execution order 29 // o Make required Analysis information available before pass P is run 30 // o Release memory occupied by dead passes 31 // o If Analysis information is dirtied by a pass then regenerate Analysis 32 // information before it is consumed by another pass. 33 // 34 // Pass Manager Infrastructure uses multiple pass managers. They are 35 // PassManager, FunctionPassManager, MPPassManager, FPPassManager, BBPassManager. 36 // This class hierarchy uses multiple inheritance but pass managers do not 37 // derive from another pass manager. 38 // 39 // PassManager and FunctionPassManager are two top-level pass manager that 40 // represents the external interface of this entire pass manager infrastucture. 41 // 42 // Important classes : 43 // 44 // [o] class PMTopLevelManager; 45 // 46 // Two top level managers, PassManager and FunctionPassManager, derive from 47 // PMTopLevelManager. PMTopLevelManager manages information used by top level 48 // managers such as last user info. 49 // 50 // [o] class PMDataManager; 51 // 52 // PMDataManager manages information, e.g. list of available analysis info, 53 // used by a pass manager to manage execution order of passes. It also provides 54 // a place to implement common pass manager APIs. All pass managers derive from 55 // PMDataManager. 56 // 57 // [o] class BBPassManager : public FunctionPass, public PMDataManager; 58 // 59 // BBPassManager manages BasicBlockPasses. 60 // 61 // [o] class FunctionPassManager; 62 // 63 // This is a external interface used to manage FunctionPasses. This 64 // interface relies on FunctionPassManagerImpl to do all the tasks. 65 // 66 // [o] class FunctionPassManagerImpl : public ModulePass, PMDataManager, 67 // public PMTopLevelManager; 68 // 69 // FunctionPassManagerImpl is a top level manager. It manages FPPassManagers 70 // 71 // [o] class FPPassManager : public ModulePass, public PMDataManager; 72 // 73 // FPPassManager manages FunctionPasses and BBPassManagers 74 // 75 // [o] class MPPassManager : public Pass, public PMDataManager; 76 // 77 // MPPassManager manages ModulePasses and FPPassManagers 78 // 79 // [o] class PassManager; 80 // 81 // This is a external interface used by various tools to manages passes. It 82 // relies on PassManagerImpl to do all the tasks. 83 // 84 // [o] class PassManagerImpl : public Pass, public PMDataManager, 85 // public PMTopLevelManager 86 // 87 // PassManagerImpl is a top level pass manager responsible for managing 88 // MPPassManagers. 89 //===----------------------------------------------------------------------===// 90 91 #include "llvm/Support/PrettyStackTrace.h" 92 93 namespace llvm { 94 template <typename T> class ArrayRef; 95 class Module; 96 class Pass; 97 class StringRef; 98 class Value; 99 class Timer; 100 class PMDataManager; 101 102 // enums for debugging strings 103 enum PassDebuggingString { 104 EXECUTION_MSG, // "Executing Pass '" + PassName 105 MODIFICATION_MSG, // "Made Modification '" + PassName 106 FREEING_MSG, // " Freeing Pass '" + PassName 107 ON_BASICBLOCK_MSG, // "' on BasicBlock '" + InstructionName + "'...\n" 108 ON_FUNCTION_MSG, // "' on Function '" + FunctionName + "'...\n" 109 ON_MODULE_MSG, // "' on Module '" + ModuleName + "'...\n" 110 ON_REGION_MSG, // "' on Region '" + Msg + "'...\n'" 111 ON_LOOP_MSG, // "' on Loop '" + Msg + "'...\n'" 112 ON_CG_MSG // "' on Call Graph Nodes '" + Msg + "'...\n'" 113 }; 114 115 /// PassManagerPrettyStackEntry - This is used to print informative information 116 /// about what pass is running when/if a stack trace is generated. 117 class PassManagerPrettyStackEntry : public PrettyStackTraceEntry { 118 Pass *P; 119 Value *V; 120 Module *M; 121 122 public: 123 explicit PassManagerPrettyStackEntry(Pass *p) 124 : P(p), V(nullptr), M(nullptr) {} // When P is releaseMemory'd. 125 PassManagerPrettyStackEntry(Pass *p, Value &v) 126 : P(p), V(&v), M(nullptr) {} // When P is run on V 127 PassManagerPrettyStackEntry(Pass *p, Module &m) 128 : P(p), V(nullptr), M(&m) {} // When P is run on M 129 130 /// print - Emit information about this stack frame to OS. 131 void print(raw_ostream &OS) const override; 132 }; 133 134 //===----------------------------------------------------------------------===// 135 // PMStack 136 // 137 /// PMStack - This class implements a stack data structure of PMDataManager 138 /// pointers. 139 /// 140 /// Top level pass managers (see PassManager.cpp) maintain active Pass Managers 141 /// using PMStack. Each Pass implements assignPassManager() to connect itself 142 /// with appropriate manager. assignPassManager() walks PMStack to find 143 /// suitable manager. 144 class PMStack { 145 public: 146 typedef std::vector<PMDataManager *>::const_reverse_iterator iterator; 147 iterator begin() const { return S.rbegin(); } 148 iterator end() const { return S.rend(); } 149 150 void pop(); 151 PMDataManager *top() const { return S.back(); } 152 void push(PMDataManager *PM); 153 bool empty() const { return S.empty(); } 154 155 void dump() const; 156 157 private: 158 std::vector<PMDataManager *> S; 159 }; 160 161 //===----------------------------------------------------------------------===// 162 // PMTopLevelManager 163 // 164 /// PMTopLevelManager manages LastUser info and collects common APIs used by 165 /// top level pass managers. 166 class PMTopLevelManager { 167 protected: 168 explicit PMTopLevelManager(PMDataManager *PMDM); 169 170 unsigned getNumContainedManagers() const { 171 return (unsigned)PassManagers.size(); 172 } 173 174 void initializeAllAnalysisInfo(); 175 176 private: 177 virtual PMDataManager *getAsPMDataManager() = 0; 178 virtual PassManagerType getTopLevelPassManagerType() = 0; 179 180 public: 181 /// Schedule pass P for execution. Make sure that passes required by 182 /// P are run before P is run. Update analysis info maintained by 183 /// the manager. Remove dead passes. This is a recursive function. 184 void schedulePass(Pass *P); 185 186 /// Set pass P as the last user of the given analysis passes. 187 void setLastUser(ArrayRef<Pass*> AnalysisPasses, Pass *P); 188 189 /// Collect passes whose last user is P 190 void collectLastUses(SmallVectorImpl<Pass *> &LastUses, Pass *P); 191 192 /// Find the pass that implements Analysis AID. Search immutable 193 /// passes and all pass managers. If desired pass is not found 194 /// then return NULL. 195 Pass *findAnalysisPass(AnalysisID AID); 196 197 /// Retrieve the PassInfo for an analysis. 198 const PassInfo *findAnalysisPassInfo(AnalysisID AID) const; 199 200 /// Find analysis usage information for the pass P. 201 AnalysisUsage *findAnalysisUsage(Pass *P); 202 203 virtual ~PMTopLevelManager(); 204 205 /// Add immutable pass and initialize it. 206 void addImmutablePass(ImmutablePass *P); 207 208 inline SmallVectorImpl<ImmutablePass *>& getImmutablePasses() { 209 return ImmutablePasses; 210 } 211 212 void addPassManager(PMDataManager *Manager) { 213 PassManagers.push_back(Manager); 214 } 215 216 // Add Manager into the list of managers that are not directly 217 // maintained by this top level pass manager 218 inline void addIndirectPassManager(PMDataManager *Manager) { 219 IndirectPassManagers.push_back(Manager); 220 } 221 222 // Print passes managed by this top level manager. 223 void dumpPasses() const; 224 void dumpArguments() const; 225 226 // Active Pass Managers 227 PMStack activeStack; 228 229 protected: 230 /// Collection of pass managers 231 SmallVector<PMDataManager *, 8> PassManagers; 232 233 private: 234 /// Collection of pass managers that are not directly maintained 235 /// by this pass manager 236 SmallVector<PMDataManager *, 8> IndirectPassManagers; 237 238 // Map to keep track of last user of the analysis pass. 239 // LastUser->second is the last user of Lastuser->first. 240 DenseMap<Pass *, Pass *> LastUser; 241 242 // Map to keep track of passes that are last used by a pass. 243 // This inverse map is initialized at PM->run() based on 244 // LastUser map. 245 DenseMap<Pass *, SmallPtrSet<Pass *, 8> > InversedLastUser; 246 247 /// Immutable passes are managed by top level manager. 248 SmallVector<ImmutablePass *, 16> ImmutablePasses; 249 250 /// Map from ID to immutable passes. 251 SmallDenseMap<AnalysisID, ImmutablePass *, 8> ImmutablePassMap; 252 253 254 /// A wrapper around AnalysisUsage for the purpose of uniqueing. The wrapper 255 /// is used to avoid needing to make AnalysisUsage itself a folding set node. 256 struct AUFoldingSetNode : public FoldingSetNode { 257 AnalysisUsage AU; 258 AUFoldingSetNode(const AnalysisUsage &AU) : AU(AU) {} 259 void Profile(FoldingSetNodeID &ID) const { 260 Profile(ID, AU); 261 } 262 static void Profile(FoldingSetNodeID &ID, const AnalysisUsage &AU) { 263 // TODO: We could consider sorting the dependency arrays within the 264 // AnalysisUsage (since they are conceptually unordered). 265 ID.AddBoolean(AU.getPreservesAll()); 266 auto ProfileVec = [&](const SmallVectorImpl<AnalysisID>& Vec) { 267 ID.AddInteger(Vec.size()); 268 for(AnalysisID AID : Vec) 269 ID.AddPointer(AID); 270 }; 271 ProfileVec(AU.getRequiredSet()); 272 ProfileVec(AU.getRequiredTransitiveSet()); 273 ProfileVec(AU.getPreservedSet()); 274 ProfileVec(AU.getUsedSet()); 275 } 276 }; 277 278 // Contains all of the unique combinations of AnalysisUsage. This is helpful 279 // when we have multiple instances of the same pass since they'll usually 280 // have the same analysis usage and can share storage. 281 FoldingSet<AUFoldingSetNode> UniqueAnalysisUsages; 282 283 // Allocator used for allocating UAFoldingSetNodes. This handles deletion of 284 // all allocated nodes in one fell swoop. 285 SpecificBumpPtrAllocator<AUFoldingSetNode> AUFoldingSetNodeAllocator; 286 287 // Maps from a pass to it's associated entry in UniqueAnalysisUsages. Does 288 // not own the storage associated with either key or value.. 289 DenseMap<Pass *, AnalysisUsage*> AnUsageMap; 290 291 /// Collection of PassInfo objects found via analysis IDs and in this top 292 /// level manager. This is used to memoize queries to the pass registry. 293 /// FIXME: This is an egregious hack because querying the pass registry is 294 /// either slow or racy. 295 mutable DenseMap<AnalysisID, const PassInfo *> AnalysisPassInfos; 296 }; 297 298 //===----------------------------------------------------------------------===// 299 // PMDataManager 300 301 /// PMDataManager provides the common place to manage the analysis data 302 /// used by pass managers. 303 class PMDataManager { 304 public: 305 explicit PMDataManager() : TPM(nullptr), Depth(0) { 306 initializeAnalysisInfo(); 307 } 308 309 virtual ~PMDataManager(); 310 311 virtual Pass *getAsPass() = 0; 312 313 /// Augment AvailableAnalysis by adding analysis made available by pass P. 314 void recordAvailableAnalysis(Pass *P); 315 316 /// verifyPreservedAnalysis -- Verify analysis presreved by pass P. 317 void verifyPreservedAnalysis(Pass *P); 318 319 /// Remove Analysis that is not preserved by the pass 320 void removeNotPreservedAnalysis(Pass *P); 321 322 /// Remove dead passes used by P. 323 void removeDeadPasses(Pass *P, StringRef Msg, 324 enum PassDebuggingString); 325 326 /// Remove P. 327 void freePass(Pass *P, StringRef Msg, 328 enum PassDebuggingString); 329 330 /// Add pass P into the PassVector. Update 331 /// AvailableAnalysis appropriately if ProcessAnalysis is true. 332 void add(Pass *P, bool ProcessAnalysis = true); 333 334 /// Add RequiredPass into list of lower level passes required by pass P. 335 /// RequiredPass is run on the fly by Pass Manager when P requests it 336 /// through getAnalysis interface. 337 virtual void addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass); 338 339 virtual Pass *getOnTheFlyPass(Pass *P, AnalysisID PI, Function &F); 340 341 /// Initialize available analysis information. 342 void initializeAnalysisInfo() { 343 AvailableAnalysis.clear(); 344 for (unsigned i = 0; i < PMT_Last; ++i) 345 InheritedAnalysis[i] = nullptr; 346 } 347 348 // Return true if P preserves high level analysis used by other 349 // passes that are managed by this manager. 350 bool preserveHigherLevelAnalysis(Pass *P); 351 352 /// Populate UsedPasses with analysis pass that are used or required by pass 353 /// P and are available. Populate ReqPassNotAvailable with analysis pass that 354 /// are required by pass P but are not available. 355 void collectRequiredAndUsedAnalyses( 356 SmallVectorImpl<Pass *> &UsedPasses, 357 SmallVectorImpl<AnalysisID> &ReqPassNotAvailable, Pass *P); 358 359 /// All Required analyses should be available to the pass as it runs! Here 360 /// we fill in the AnalysisImpls member of the pass so that it can 361 /// successfully use the getAnalysis() method to retrieve the 362 /// implementations it needs. 363 void initializeAnalysisImpl(Pass *P); 364 365 /// Find the pass that implements Analysis AID. If desired pass is not found 366 /// then return NULL. 367 Pass *findAnalysisPass(AnalysisID AID, bool Direction); 368 369 // Access toplevel manager 370 PMTopLevelManager *getTopLevelManager() { return TPM; } 371 void setTopLevelManager(PMTopLevelManager *T) { TPM = T; } 372 373 unsigned getDepth() const { return Depth; } 374 void setDepth(unsigned newDepth) { Depth = newDepth; } 375 376 // Print routines used by debug-pass 377 void dumpLastUses(Pass *P, unsigned Offset) const; 378 void dumpPassArguments() const; 379 void dumpPassInfo(Pass *P, enum PassDebuggingString S1, 380 enum PassDebuggingString S2, StringRef Msg); 381 void dumpRequiredSet(const Pass *P) const; 382 void dumpPreservedSet(const Pass *P) const; 383 void dumpUsedSet(const Pass *P) const; 384 385 unsigned getNumContainedPasses() const { 386 return (unsigned)PassVector.size(); 387 } 388 389 virtual PassManagerType getPassManagerType() const { 390 assert ( 0 && "Invalid use of getPassManagerType"); 391 return PMT_Unknown; 392 } 393 394 DenseMap<AnalysisID, Pass*> *getAvailableAnalysis() { 395 return &AvailableAnalysis; 396 } 397 398 // Collect AvailableAnalysis from all the active Pass Managers. 399 void populateInheritedAnalysis(PMStack &PMS) { 400 unsigned Index = 0; 401 for (PMStack::iterator I = PMS.begin(), E = PMS.end(); 402 I != E; ++I) 403 InheritedAnalysis[Index++] = (*I)->getAvailableAnalysis(); 404 } 405 406 protected: 407 // Top level manager. 408 PMTopLevelManager *TPM; 409 410 // Collection of pass that are managed by this manager 411 SmallVector<Pass *, 16> PassVector; 412 413 // Collection of Analysis provided by Parent pass manager and 414 // used by current pass manager. At at time there can not be more 415 // then PMT_Last active pass mangers. 416 DenseMap<AnalysisID, Pass *> *InheritedAnalysis[PMT_Last]; 417 418 /// isPassDebuggingExecutionsOrMore - Return true if -debug-pass=Executions 419 /// or higher is specified. 420 bool isPassDebuggingExecutionsOrMore() const; 421 422 private: 423 void dumpAnalysisUsage(StringRef Msg, const Pass *P, 424 const AnalysisUsage::VectorType &Set) const; 425 426 // Set of available Analysis. This information is used while scheduling 427 // pass. If a pass requires an analysis which is not available then 428 // the required analysis pass is scheduled to run before the pass itself is 429 // scheduled to run. 430 DenseMap<AnalysisID, Pass*> AvailableAnalysis; 431 432 // Collection of higher level analysis used by the pass managed by 433 // this manager. 434 SmallVector<Pass *, 16> HigherLevelAnalysis; 435 436 unsigned Depth; 437 }; 438 439 //===----------------------------------------------------------------------===// 440 // FPPassManager 441 // 442 /// FPPassManager manages BBPassManagers and FunctionPasses. 443 /// It batches all function passes and basic block pass managers together and 444 /// sequence them to process one function at a time before processing next 445 /// function. 446 class FPPassManager : public ModulePass, public PMDataManager { 447 public: 448 static char ID; 449 explicit FPPassManager() 450 : ModulePass(ID), PMDataManager() { } 451 452 /// run - Execute all of the passes scheduled for execution. Keep track of 453 /// whether any of the passes modifies the module, and if so, return true. 454 bool runOnFunction(Function &F); 455 bool runOnModule(Module &M) override; 456 457 /// cleanup - After running all passes, clean up pass manager cache. 458 void cleanup(); 459 460 /// doInitialization - Overrides ModulePass doInitialization for global 461 /// initialization tasks 462 /// 463 using ModulePass::doInitialization; 464 465 /// doInitialization - Run all of the initializers for the function passes. 466 /// 467 bool doInitialization(Module &M) override; 468 469 /// doFinalization - Overrides ModulePass doFinalization for global 470 /// finalization tasks 471 /// 472 using ModulePass::doFinalization; 473 474 /// doFinalization - Run all of the finalizers for the function passes. 475 /// 476 bool doFinalization(Module &M) override; 477 478 PMDataManager *getAsPMDataManager() override { return this; } 479 Pass *getAsPass() override { return this; } 480 481 /// Pass Manager itself does not invalidate any analysis info. 482 void getAnalysisUsage(AnalysisUsage &Info) const override { 483 Info.setPreservesAll(); 484 } 485 486 // Print passes managed by this manager 487 void dumpPassStructure(unsigned Offset) override; 488 489 StringRef getPassName() const override { return "Function Pass Manager"; } 490 491 FunctionPass *getContainedPass(unsigned N) { 492 assert ( N < PassVector.size() && "Pass number out of range!"); 493 FunctionPass *FP = static_cast<FunctionPass *>(PassVector[N]); 494 return FP; 495 } 496 497 PassManagerType getPassManagerType() const override { 498 return PMT_FunctionPassManager; 499 } 500 }; 501 502 Timer *getPassTimer(Pass *); 503 } 504 505 #endif 506