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