1//===- llvm/PassManagers.h - Pass Infrastructure classes -------*- 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_PASSMANAGERS_H 15#define LLVM_PASSMANAGERS_H 16 17#include "llvm/Pass.h" 18#include "llvm/ADT/ArrayRef.h" 19#include "llvm/ADT/SmallVector.h" 20#include "llvm/ADT/SmallPtrSet.h" 21#include "llvm/ADT/DenseMap.h" 22#include <vector> 23#include <map> 24 25//===----------------------------------------------------------------------===// 26// Overview: 27// The Pass Manager Infrastructure manages passes. It's responsibilities are: 28// 29// o Manage optimization pass execution order 30// o Make required Analysis information available before pass P is run 31// o Release memory occupied by dead passes 32// o If Analysis information is dirtied by a pass then regenerate Analysis 33// information before it is consumed by another pass. 34// 35// Pass Manager Infrastructure uses multiple pass managers. They are 36// PassManager, FunctionPassManager, MPPassManager, FPPassManager, BBPassManager. 37// This class hierarchy uses multiple inheritance but pass managers do not 38// derive from another pass manager. 39// 40// PassManager and FunctionPassManager are two top-level pass manager that 41// represents the external interface of this entire pass manager infrastucture. 42// 43// Important classes : 44// 45// [o] class PMTopLevelManager; 46// 47// Two top level managers, PassManager and FunctionPassManager, derive from 48// PMTopLevelManager. PMTopLevelManager manages information used by top level 49// managers such as last user info. 50// 51// [o] class PMDataManager; 52// 53// PMDataManager manages information, e.g. list of available analysis info, 54// used by a pass manager to manage execution order of passes. It also provides 55// a place to implement common pass manager APIs. All pass managers derive from 56// PMDataManager. 57// 58// [o] class BBPassManager : public FunctionPass, public PMDataManager; 59// 60// BBPassManager manages BasicBlockPasses. 61// 62// [o] class FunctionPassManager; 63// 64// This is a external interface used by JIT to manage FunctionPasses. This 65// interface relies on FunctionPassManagerImpl to do all the tasks. 66// 67// [o] class FunctionPassManagerImpl : public ModulePass, PMDataManager, 68// public PMTopLevelManager; 69// 70// FunctionPassManagerImpl is a top level manager. It manages FPPassManagers 71// 72// [o] class FPPassManager : public ModulePass, public PMDataManager; 73// 74// FPPassManager manages FunctionPasses and BBPassManagers 75// 76// [o] class MPPassManager : public Pass, public PMDataManager; 77// 78// MPPassManager manages ModulePasses and FPPassManagers 79// 80// [o] class PassManager; 81// 82// This is a external interface used by various tools to manages passes. It 83// relies on PassManagerImpl to do all the tasks. 84// 85// [o] class PassManagerImpl : public Pass, public PMDataManager, 86// public PMTopLevelManager 87// 88// PassManagerImpl is a top level pass manager responsible for managing 89// MPPassManagers. 90//===----------------------------------------------------------------------===// 91 92#include "llvm/Support/PrettyStackTrace.h" 93 94namespace llvm { 95 class Module; 96 class Pass; 97 class StringRef; 98 class Value; 99 class Timer; 100 class PMDataManager; 101 102// enums for debugging strings 103enum PassDebuggingString { 104 EXECUTION_MSG, // "Executing Pass '" 105 MODIFICATION_MSG, // "' Made Modification '" 106 FREEING_MSG, // " Freeing Pass '" 107 ON_BASICBLOCK_MSG, // "' on BasicBlock '" + PassName + "'...\n" 108 ON_FUNCTION_MSG, // "' on Function '" + FunctionName + "'...\n" 109 ON_MODULE_MSG, // "' on Module '" + ModuleName + "'...\n" 110 ON_REGION_MSG, // " 'on Region ...\n'" 111 ON_LOOP_MSG, // " 'on Loop ...\n'" 112 ON_CG_MSG // "' on Call Graph ...\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; 121public: 122 explicit PassManagerPrettyStackEntry(Pass *p) 123 : P(p), V(0), M(0) {} // When P is releaseMemory'd. 124 PassManagerPrettyStackEntry(Pass *p, Value &v) 125 : P(p), V(&v), M(0) {} // When P is run on V 126 PassManagerPrettyStackEntry(Pass *p, Module &m) 127 : P(p), V(0), M(&m) {} // When P is run on M 128 129 /// print - Emit information about this stack frame to OS. 130 virtual void print(raw_ostream &OS) const; 131}; 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//===----------------------------------------------------------------------===// 163// PMTopLevelManager 164// 165/// PMTopLevelManager manages LastUser info and collects common APIs used by 166/// top level pass managers. 167class PMTopLevelManager { 168protected: 169 explicit PMTopLevelManager(PMDataManager *PMDM); 170 171 virtual unsigned getNumContainedManagers() const { 172 return (unsigned)PassManagers.size(); 173 } 174 175 void initializeAllAnalysisInfo(); 176 177private: 178 virtual PMDataManager *getAsPMDataManager() = 0; 179 virtual PassManagerType getTopLevelPassManagerType() = 0; 180 181public: 182 /// Schedule pass P for execution. Make sure that passes required by 183 /// P are run before P is run. Update analysis info maintained by 184 /// the manager. Remove dead passes. This is a recursive function. 185 void schedulePass(Pass *P); 186 187 /// Set pass P as the last user of the given analysis passes. 188 void setLastUser(ArrayRef<Pass*> AnalysisPasses, Pass *P); 189 190 /// Collect passes whose last user is P 191 void collectLastUses(SmallVectorImpl<Pass *> &LastUses, Pass *P); 192 193 /// Find the pass that implements Analysis AID. Search immutable 194 /// passes and all pass managers. If desired pass is not found 195 /// then return NULL. 196 Pass *findAnalysisPass(AnalysisID AID); 197 198 /// Find analysis usage information for the pass P. 199 AnalysisUsage *findAnalysisUsage(Pass *P); 200 201 virtual ~PMTopLevelManager(); 202 203 /// Add immutable pass and initialize it. 204 inline void addImmutablePass(ImmutablePass *P) { 205 P->initializePass(); 206 ImmutablePasses.push_back(P); 207 } 208 209 inline SmallVectorImpl<ImmutablePass *>& getImmutablePasses() { 210 return ImmutablePasses; 211 } 212 213 void addPassManager(PMDataManager *Manager) { 214 PassManagers.push_back(Manager); 215 } 216 217 // Add Manager into the list of managers that are not directly 218 // maintained by this top level pass manager 219 inline void addIndirectPassManager(PMDataManager *Manager) { 220 IndirectPassManagers.push_back(Manager); 221 } 222 223 // Print passes managed by this top level manager. 224 void dumpPasses() const; 225 void dumpArguments() const; 226 227 // Active Pass Managers 228 PMStack activeStack; 229 230protected: 231 232 /// Collection of pass managers 233 SmallVector<PMDataManager *, 8> PassManagers; 234 235private: 236 237 /// Collection of pass managers that are not directly maintained 238 /// by this pass manager 239 SmallVector<PMDataManager *, 8> IndirectPassManagers; 240 241 // Map to keep track of last user of the analysis pass. 242 // LastUser->second is the last user of Lastuser->first. 243 DenseMap<Pass *, Pass *> LastUser; 244 245 // Map to keep track of passes that are last used by a pass. 246 // This inverse map is initialized at PM->run() based on 247 // LastUser map. 248 DenseMap<Pass *, SmallPtrSet<Pass *, 8> > InversedLastUser; 249 250 /// Immutable passes are managed by top level manager. 251 SmallVector<ImmutablePass *, 8> ImmutablePasses; 252 253 DenseMap<Pass *, AnalysisUsage *> AnUsageMap; 254}; 255 256 257 258//===----------------------------------------------------------------------===// 259// PMDataManager 260 261/// PMDataManager provides the common place to manage the analysis data 262/// used by pass managers. 263class PMDataManager { 264public: 265 266 explicit PMDataManager() : TPM(NULL), Depth(0) { 267 initializeAnalysisInfo(); 268 } 269 270 virtual ~PMDataManager(); 271 272 virtual Pass *getAsPass() = 0; 273 274 /// Augment AvailableAnalysis by adding analysis made available by pass P. 275 void recordAvailableAnalysis(Pass *P); 276 277 /// verifyPreservedAnalysis -- Verify analysis presreved by pass P. 278 void verifyPreservedAnalysis(Pass *P); 279 280 /// Remove Analysis that is not preserved by the pass 281 void removeNotPreservedAnalysis(Pass *P); 282 283 /// Remove dead passes used by P. 284 void removeDeadPasses(Pass *P, StringRef Msg, 285 enum PassDebuggingString); 286 287 /// Remove P. 288 void freePass(Pass *P, StringRef Msg, 289 enum PassDebuggingString); 290 291 /// Add pass P into the PassVector. Update 292 /// AvailableAnalysis appropriately if ProcessAnalysis is true. 293 void add(Pass *P, bool ProcessAnalysis = true); 294 295 /// Add RequiredPass into list of lower level passes required by pass P. 296 /// RequiredPass is run on the fly by Pass Manager when P requests it 297 /// through getAnalysis interface. 298 virtual void addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass); 299 300 virtual Pass *getOnTheFlyPass(Pass *P, AnalysisID PI, Function &F); 301 302 /// Initialize available analysis information. 303 void initializeAnalysisInfo() { 304 AvailableAnalysis.clear(); 305 for (unsigned i = 0; i < PMT_Last; ++i) 306 InheritedAnalysis[i] = NULL; 307 } 308 309 // Return true if P preserves high level analysis used by other 310 // passes that are managed by this manager. 311 bool preserveHigherLevelAnalysis(Pass *P); 312 313 314 /// Populate RequiredPasses with analysis pass that are required by 315 /// pass P and are available. Populate ReqPassNotAvailable with analysis 316 /// pass that are required by pass P but are not available. 317 void collectRequiredAnalysis(SmallVectorImpl<Pass *> &RequiredPasses, 318 SmallVectorImpl<AnalysisID> &ReqPassNotAvailable, 319 Pass *P); 320 321 /// All Required analyses should be available to the pass as it runs! Here 322 /// we fill in the AnalysisImpls member of the pass so that it can 323 /// successfully use the getAnalysis() method to retrieve the 324 /// implementations it needs. 325 void initializeAnalysisImpl(Pass *P); 326 327 /// Find the pass that implements Analysis AID. If desired pass is not found 328 /// then return NULL. 329 Pass *findAnalysisPass(AnalysisID AID, bool Direction); 330 331 // Access toplevel manager 332 PMTopLevelManager *getTopLevelManager() { return TPM; } 333 void setTopLevelManager(PMTopLevelManager *T) { TPM = T; } 334 335 unsigned getDepth() const { return Depth; } 336 void setDepth(unsigned newDepth) { Depth = newDepth; } 337 338 // Print routines used by debug-pass 339 void dumpLastUses(Pass *P, unsigned Offset) const; 340 void dumpPassArguments() const; 341 void dumpPassInfo(Pass *P, enum PassDebuggingString S1, 342 enum PassDebuggingString S2, StringRef Msg); 343 void dumpRequiredSet(const Pass *P) const; 344 void dumpPreservedSet(const Pass *P) const; 345 346 virtual unsigned getNumContainedPasses() const { 347 return (unsigned)PassVector.size(); 348 } 349 350 virtual PassManagerType getPassManagerType() const { 351 assert ( 0 && "Invalid use of getPassManagerType"); 352 return PMT_Unknown; 353 } 354 355 std::map<AnalysisID, Pass*> *getAvailableAnalysis() { 356 return &AvailableAnalysis; 357 } 358 359 // Collect AvailableAnalysis from all the active Pass Managers. 360 void populateInheritedAnalysis(PMStack &PMS) { 361 unsigned Index = 0; 362 for (PMStack::iterator I = PMS.begin(), E = PMS.end(); 363 I != E; ++I) 364 InheritedAnalysis[Index++] = (*I)->getAvailableAnalysis(); 365 } 366 367protected: 368 369 // Top level manager. 370 PMTopLevelManager *TPM; 371 372 // Collection of pass that are managed by this manager 373 SmallVector<Pass *, 16> PassVector; 374 375 // Collection of Analysis provided by Parent pass manager and 376 // used by current pass manager. At at time there can not be more 377 // then PMT_Last active pass mangers. 378 std::map<AnalysisID, Pass *> *InheritedAnalysis[PMT_Last]; 379 380 381 /// isPassDebuggingExecutionsOrMore - Return true if -debug-pass=Executions 382 /// or higher is specified. 383 bool isPassDebuggingExecutionsOrMore() const; 384 385private: 386 void dumpAnalysisUsage(StringRef Msg, const Pass *P, 387 const AnalysisUsage::VectorType &Set) const; 388 389 // Set of available Analysis. This information is used while scheduling 390 // pass. If a pass requires an analysis which is not available then 391 // the required analysis pass is scheduled to run before the pass itself is 392 // scheduled to run. 393 std::map<AnalysisID, Pass*> AvailableAnalysis; 394 395 // Collection of higher level analysis used by the pass managed by 396 // this manager. 397 SmallVector<Pass *, 8> HigherLevelAnalysis; 398 399 unsigned Depth; 400}; 401 402//===----------------------------------------------------------------------===// 403// FPPassManager 404// 405/// FPPassManager manages BBPassManagers and FunctionPasses. 406/// It batches all function passes and basic block pass managers together and 407/// sequence them to process one function at a time before processing next 408/// function. 409class FPPassManager : public ModulePass, public PMDataManager { 410public: 411 static char ID; 412 explicit FPPassManager() 413 : ModulePass(ID), PMDataManager() { } 414 415 /// run - Execute all of the passes scheduled for execution. Keep track of 416 /// whether any of the passes modifies the module, and if so, return true. 417 bool runOnFunction(Function &F); 418 bool runOnModule(Module &M); 419 420 /// cleanup - After running all passes, clean up pass manager cache. 421 void cleanup(); 422 423 /// doInitialization - Run all of the initializers for the function passes. 424 /// 425 bool doInitialization(Module &M); 426 427 /// doFinalization - Run all of the finalizers for the function passes. 428 /// 429 bool doFinalization(Module &M); 430 431 virtual PMDataManager *getAsPMDataManager() { return this; } 432 virtual Pass *getAsPass() { return this; } 433 434 /// Pass Manager itself does not invalidate any analysis info. 435 void getAnalysisUsage(AnalysisUsage &Info) const { 436 Info.setPreservesAll(); 437 } 438 439 // Print passes managed by this manager 440 void dumpPassStructure(unsigned Offset); 441 442 virtual const char *getPassName() const { 443 return "Function Pass Manager"; 444 } 445 446 FunctionPass *getContainedPass(unsigned N) { 447 assert ( N < PassVector.size() && "Pass number out of range!"); 448 FunctionPass *FP = static_cast<FunctionPass *>(PassVector[N]); 449 return FP; 450 } 451 452 virtual PassManagerType getPassManagerType() const { 453 return PMT_FunctionPassManager; 454 } 455}; 456 457Timer *getPassTimer(Pass *); 458 459} 460 461#endif 462