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 93namespace llvm { 94template <typename T> class ArrayRef; 95class Module; 96class Pass; 97class StringRef; 98class Value; 99class Timer; 100class PMDataManager; 101 102// enums for debugging strings 103enum 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. 117class PassManagerPrettyStackEntry : public PrettyStackTraceEntry { 118 Pass *P; 119 Value *V; 120 Module *M; 121 122public: 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. 144class PMStack { 145public: 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 157private: 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. 166class PMTopLevelManager { 167protected: 168 explicit PMTopLevelManager(PMDataManager *PMDM); 169 170 unsigned getNumContainedManagers() const { 171 return (unsigned)PassManagers.size(); 172 } 173 174 void initializeAllAnalysisInfo(); 175 176private: 177 virtual PMDataManager *getAsPMDataManager() = 0; 178 virtual PassManagerType getTopLevelPassManagerType() = 0; 179 180public: 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 229protected: 230 /// Collection of pass managers 231 SmallVector<PMDataManager *, 8> PassManagers; 232 233private: 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. 303class PMDataManager { 304public: 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 406protected: 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 422private: 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. 446class FPPassManager : public ModulePass, public PMDataManager { 447public: 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 502Timer *getPassTimer(Pass *); 503} 504 505#endif 506