PassManager.cpp revision fcb2d940a0f0c471069a65c57c48b847d1b6762e
1//===- PassManager.cpp - LLVM Pass Infrastructure Implementation ----------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by Devang Patel and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the LLVM Pass Manager infrastructure. 11// 12//===----------------------------------------------------------------------===// 13 14 15#include "llvm/PassManager.h" 16#include "llvm/Module.h" 17#include <vector> 18#include <set> 19 20using namespace llvm; 21 22namespace llvm { 23 24/// CommonPassManagerImpl helps pass manager analysis required by 25/// the managed passes. It provides methods to add/remove analysis 26/// available and query if certain analysis is available or not. 27class CommonPassManagerImpl : public Pass { 28 29public: 30 31 /// Return true IFF pass P's required analysis set does not required new 32 /// manager. 33 bool manageablePass(Pass *P); 34 35 /// Return true IFF AnalysisID AID is currently available. 36 bool analysisCurrentlyAvailable(AnalysisID AID); 37 38 /// Augment RequiredAnalysis by adding analysis required by pass P. 39 void noteDownRequiredAnalysis(Pass *P); 40 41 /// Augment AvailableAnalysis by adding analysis made available by pass P. 42 void noteDownAvailableAnalysis(Pass *P); 43 44 /// Remove Analysis that is not preserved by the pass 45 void removeNotPreservedAnalysis(Pass *P); 46 47 /// Remove dead passes 48 void removeDeadPasses() { /* TODO : Implement */ } 49 50 /// Add pass P into the PassVector. Update RequiredAnalysis and 51 /// AvailableAnalysis appropriately if ProcessAnalysis is true. 52 void addPassToManager (Pass *P, bool ProcessAnalysis = true); 53 54 inline std::vector<Pass *>::iterator passVectorBegin() { 55 return PassVector.begin(); 56 } 57 58 inline std::vector<Pass *>::iterator passVectorEnd() { 59 return PassVector.end(); 60 } 61 62private: 63 // Analysis required by the passes managed by this manager 64 std::vector<AnalysisID> RequiredAnalysis; 65 66 // set of available Analysis 67 std::set<AnalysisID> AvailableAnalysis; 68 69 // Collection of pass that are managed by this manager 70 std::vector<Pass *> PassVector; 71}; 72 73/// BasicBlockPassManager_New manages BasicBlockPass. It batches all the 74/// pass together and sequence them to process one basic block before 75/// processing next basic block. 76class BasicBlockPassManager_New : public CommonPassManagerImpl { 77 78public: 79 BasicBlockPassManager_New() { } 80 81 /// Add a pass into a passmanager queue. 82 bool addPass(Pass *p); 83 84 /// Execute all of the passes scheduled for execution. Keep track of 85 /// whether any of the passes modifies the function, and if so, return true. 86 bool runOnFunction(Function &F); 87 88private: 89}; 90 91/// FunctionPassManagerImpl_New manages FunctionPasses and BasicBlockPassManagers. 92/// It batches all function passes and basic block pass managers together and 93/// sequence them to process one function at a time before processing next 94/// function. 95class FunctionPassManagerImpl_New : public CommonPassManagerImpl { 96public: 97 FunctionPassManagerImpl_New(ModuleProvider *P) { /* TODO */ } 98 FunctionPassManagerImpl_New() { 99 activeBBPassManager = NULL; 100 } 101 ~FunctionPassManagerImpl_New() { /* TODO */ }; 102 103 /// add - Add a pass to the queue of passes to run. This passes 104 /// ownership of the Pass to the PassManager. When the 105 /// PassManager_X is destroyed, the pass will be destroyed as well, so 106 /// there is no need to delete the pass. (TODO delete passes.) 107 /// This implies that all passes MUST be allocated with 'new'. 108 void add(Pass *P) { /* TODO*/ } 109 110 /// Add pass into the pass manager queue. 111 bool addPass(Pass *P); 112 113 /// Execute all of the passes scheduled for execution. Keep 114 /// track of whether any of the passes modifies the function, and if 115 /// so, return true. 116 bool runOnModule(Module &M); 117 118private: 119 // Active Pass Managers 120 BasicBlockPassManager_New *activeBBPassManager; 121}; 122 123/// ModulePassManager_New manages ModulePasses and function pass managers. 124/// It batches all Module passes passes and function pass managers together and 125/// sequence them to process one module. 126class ModulePassManager_New : public CommonPassManagerImpl { 127 128public: 129 ModulePassManager_New() { activeFunctionPassManager = NULL; } 130 131 /// Add a pass into a passmanager queue. 132 bool addPass(Pass *p); 133 134 /// run - Execute all of the passes scheduled for execution. Keep track of 135 /// whether any of the passes modifies the module, and if so, return true. 136 bool runOnModule(Module &M); 137 138private: 139 // Active Pass Manager 140 FunctionPassManagerImpl_New *activeFunctionPassManager; 141}; 142 143/// PassManager_New manages ModulePassManagers 144class PassManagerImpl_New : public CommonPassManagerImpl { 145 146public: 147 148 /// add - Add a pass to the queue of passes to run. This passes ownership of 149 /// the Pass to the PassManager. When the PassManager is destroyed, the pass 150 /// will be destroyed as well, so there is no need to delete the pass. This 151 /// implies that all passes MUST be allocated with 'new'. 152 void add(Pass *P); 153 154 /// run - Execute all of the passes scheduled for execution. Keep track of 155 /// whether any of the passes modifies the module, and if so, return true. 156 bool run(Module &M); 157 158private: 159 160 /// Add a pass into a passmanager queue. This is used by schedulePasses 161 bool addPass(Pass *p); 162 163 /// Schedule all passes collected in pass queue using add(). Add all the 164 /// schedule passes into various manager's queue using addPass(). 165 void schedulePasses(); 166 167 // Collection of pass managers 168 std::vector<ModulePassManager_New *> PassManagers; 169 170 // Active Pass Manager 171 ModulePassManager_New *activeManager; 172}; 173 174} // End of llvm namespace 175 176// CommonPassManagerImpl implementation 177 178/// Return true IFF pass P's required analysis set does not required new 179/// manager. 180bool CommonPassManagerImpl::manageablePass(Pass *P) { 181 182 AnalysisUsage AnUsage; 183 P->getAnalysisUsage(AnUsage); 184 185 // If this pass is not preserving information that is required by the other 186 // passes managed by this manager then use new manager 187 if (!AnUsage.getPreservesAll()) { 188 const std::vector<AnalysisID> &PreservedSet = AnUsage.getPreservedSet(); 189 for (std::vector<AnalysisID>::iterator I = RequiredAnalysis.begin(), 190 E = RequiredAnalysis.end(); I != E; ++I) { 191 if (std::find(PreservedSet.begin(), PreservedSet.end(), *I) == 192 PreservedSet.end()) 193 // This analysis is not preserved. Need new manager. 194 return false; 195 } 196 } 197 return true; 198} 199 200/// Return true IFF AnalysisID AID is currently available. 201bool CommonPassManagerImpl::analysisCurrentlyAvailable(AnalysisID AID) { 202 203 // TODO 204 return false; 205} 206 207/// Augment RequiredAnalysis by adding analysis required by pass P. 208void CommonPassManagerImpl::noteDownRequiredAnalysis(Pass *P) { 209 AnalysisUsage AnUsage; 210 P->getAnalysisUsage(AnUsage); 211 const std::vector<AnalysisID> &RequiredSet = AnUsage.getRequiredSet(); 212 213 // FIXME: What about duplicates ? 214 RequiredAnalysis.insert(RequiredAnalysis.end(), RequiredSet.begin(), 215 RequiredSet.end()); 216} 217 218/// Augement AvailableAnalysis by adding analysis made available by pass P. 219void CommonPassManagerImpl::noteDownAvailableAnalysis(Pass *P) { 220 221 if (const PassInfo *PI = P->getPassInfo()) { 222 AvailableAnalysis.insert(PI); 223 224 //TODO This pass is the current implementation of all of the interfaces it 225 //TODO implements as well. 226 //TODO 227 //TODO const std::vector<const PassInfo*> &II = PI->getInterfacesImplemented(); 228 //TODO for (unsigned i = 0, e = II.size(); i != e; ++i) 229 //TODO CurrentAnalyses[II[i]] = P; 230 } 231} 232 233/// Remove Analyss not preserved by Pass P 234void CommonPassManagerImpl::removeNotPreservedAnalysis(Pass *P) { 235 AnalysisUsage AnUsage; 236 P->getAnalysisUsage(AnUsage); 237 const std::vector<AnalysisID> &PreservedSet = AnUsage.getPreservedSet(); 238 239 for (std::set<AnalysisID>::iterator I = AvailableAnalysis.begin(), 240 E = AvailableAnalysis.end(); I != E; ++I ) { 241 if (std::find(PreservedSet.begin(), PreservedSet.end(), *I) == 242 PreservedSet.end()) { 243 // Remove this analysis 244 std::set<AnalysisID>::iterator J = I++; 245 AvailableAnalysis.erase(J); 246 } 247 } 248} 249 250/// Add pass P into the PassVector. Update RequiredAnalysis and 251/// AvailableAnalysis appropriately if ProcessAnalysis is true. 252void CommonPassManagerImpl::addPassToManager (Pass *P, 253 bool ProcessAnalysis) { 254 255 if (ProcessAnalysis) { 256 // Take a note of analysis required and made available by this pass 257 noteDownRequiredAnalysis(P); 258 noteDownAvailableAnalysis(P); 259 260 // Remove the analysis not preserved by this pass 261 removeNotPreservedAnalysis(P); 262 } 263 264 // Add pass 265 PassVector.push_back(P); 266} 267 268/// BasicBlockPassManager implementation 269 270/// Add pass P into PassVector and return true. If this pass is not 271/// manageable by this manager then return false. 272bool 273BasicBlockPassManager_New::addPass(Pass *P) { 274 275 BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P); 276 if (!BP) 277 return false; 278 279 // If this pass does not preserve anlysis that is used by other passes 280 // managed by this manager than it is not a suiable pass for this manager. 281 if (!manageablePass(P)) 282 return false; 283 284 addPassToManager (BP); 285 286 return true; 287} 288 289/// Execute all of the passes scheduled for execution by invoking 290/// runOnBasicBlock method. Keep track of whether any of the passes modifies 291/// the function, and if so, return true. 292bool 293BasicBlockPassManager_New::runOnFunction(Function &F) { 294 295 bool Changed = false; 296 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 297 for (std::vector<Pass *>::iterator itr = passVectorBegin(), 298 e = passVectorEnd(); itr != e; ++itr) { 299 Pass *P = *itr; 300 BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P); 301 Changed |= BP->runOnBasicBlock(*I); 302 } 303 return Changed; 304} 305 306// FunctionPassManager_New implementation 307/// Create new Function pass manager 308FunctionPassManager_New::FunctionPassManager_New() { 309 FPM = new FunctionPassManagerImpl_New(); 310} 311 312/// add - Add a pass to the queue of passes to run. This passes 313/// ownership of the Pass to the PassManager. When the 314/// PassManager_X is destroyed, the pass will be destroyed as well, so 315/// there is no need to delete the pass. (TODO delete passes.) 316/// This implies that all passes MUST be allocated with 'new'. 317void 318FunctionPassManager_New::add(Pass *P) { 319 FPM->add(P); 320} 321 322/// Execute all of the passes scheduled for execution. Keep 323/// track of whether any of the passes modifies the function, and if 324/// so, return true. 325bool 326FunctionPassManager_New::runOnModule(Module &M) { 327 return FPM->runOnModule(M); 328} 329 330// FunctionPassManagerImpl_New implementation 331 332// FunctionPassManager 333 334/// Add pass P into the pass manager queue. If P is a BasicBlockPass then 335/// either use it into active basic block pass manager or create new basic 336/// block pass manager to handle pass P. 337bool 338FunctionPassManagerImpl_New::addPass(Pass *P) { 339 340 // If P is a BasicBlockPass then use BasicBlockPassManager_New. 341 if (BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P)) { 342 343 if (!activeBBPassManager 344 || !activeBBPassManager->addPass(BP)) { 345 346 activeBBPassManager = new BasicBlockPassManager_New(); 347 addPassToManager(activeBBPassManager, false); 348 if (!activeBBPassManager->addPass(BP)) 349 assert(0 && "Unable to add Pass"); 350 } 351 return true; 352 } 353 354 FunctionPass *FP = dynamic_cast<FunctionPass *>(P); 355 if (!FP) 356 return false; 357 358 // If this pass does not preserve anlysis that is used by other passes 359 // managed by this manager than it is not a suiable pass for this manager. 360 if (!manageablePass(P)) 361 return false; 362 363 addPassToManager (FP); 364 activeBBPassManager = NULL; 365 return true; 366} 367 368/// Execute all of the passes scheduled for execution by invoking 369/// runOnFunction method. Keep track of whether any of the passes modifies 370/// the function, and if so, return true. 371bool 372FunctionPassManagerImpl_New::runOnModule(Module &M) { 373 374 bool Changed = false; 375 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 376 for (std::vector<Pass *>::iterator itr = passVectorBegin(), 377 e = passVectorEnd(); itr != e; ++itr) { 378 Pass *P = *itr; 379 FunctionPass *FP = dynamic_cast<FunctionPass*>(P); 380 Changed |= FP->runOnFunction(*I); 381 } 382 return Changed; 383} 384 385 386// ModulePassManager implementation 387 388/// Add P into pass vector if it is manageble. If P is a FunctionPass 389/// then use FunctionPassManagerImpl_New to manage it. Return false if P 390/// is not manageable by this manager. 391bool 392ModulePassManager_New::addPass(Pass *P) { 393 394 // If P is FunctionPass then use function pass maanager. 395 if (FunctionPass *FP = dynamic_cast<FunctionPass*>(P)) { 396 397 activeFunctionPassManager = NULL; 398 399 if (!activeFunctionPassManager 400 || !activeFunctionPassManager->addPass(P)) { 401 402 activeFunctionPassManager = new FunctionPassManagerImpl_New(); 403 addPassToManager(activeFunctionPassManager, false); 404 if (!activeFunctionPassManager->addPass(FP)) 405 assert(0 && "Unable to add pass"); 406 } 407 return true; 408 } 409 410 ModulePass *MP = dynamic_cast<ModulePass *>(P); 411 if (!MP) 412 return false; 413 414 // If this pass does not preserve anlysis that is used by other passes 415 // managed by this manager than it is not a suiable pass for this manager. 416 if (!manageablePass(P)) 417 return false; 418 419 addPassToManager(MP); 420 activeFunctionPassManager = NULL; 421 return true; 422} 423 424 425/// Execute all of the passes scheduled for execution by invoking 426/// runOnModule method. Keep track of whether any of the passes modifies 427/// the module, and if so, return true. 428bool 429ModulePassManager_New::runOnModule(Module &M) { 430 bool Changed = false; 431 for (std::vector<Pass *>::iterator itr = passVectorBegin(), 432 e = passVectorEnd(); itr != e; ++itr) { 433 Pass *P = *itr; 434 ModulePass *MP = dynamic_cast<ModulePass*>(P); 435 Changed |= MP->runOnModule(M); 436 } 437 return Changed; 438} 439 440/// Schedule all passes from the queue by adding them in their 441/// respective manager's queue. 442void 443PassManagerImpl_New::schedulePasses() { 444 /* TODO */ 445} 446 447/// Add pass P to the queue of passes to run. 448void 449PassManagerImpl_New::add(Pass *P) { 450 addPassToManager(P, false); 451} 452 453// PassManager_New implementation 454/// Add P into active pass manager or use new module pass manager to 455/// manage it. 456bool 457PassManagerImpl_New::addPass(Pass *P) { 458 459 if (!activeManager || !activeManager->addPass(P)) { 460 activeManager = new ModulePassManager_New(); 461 PassManagers.push_back(activeManager); 462 } 463 464 return activeManager->addPass(P); 465} 466 467/// run - Execute all of the passes scheduled for execution. Keep track of 468/// whether any of the passes modifies the module, and if so, return true. 469bool 470PassManagerImpl_New::run(Module &M) { 471 472 schedulePasses(); 473 bool Changed = false; 474 for (std::vector<ModulePassManager_New *>::iterator itr = PassManagers.begin(), 475 e = PassManagers.end(); itr != e; ++itr) { 476 ModulePassManager_New *pm = *itr; 477 Changed |= pm->runOnModule(M); 478 } 479 return Changed; 480} 481 482/// Create new pass manager 483PassManager_New::PassManager_New() { 484 PM = new PassManagerImpl_New(); 485} 486 487/// add - Add a pass to the queue of passes to run. This passes ownership of 488/// the Pass to the PassManager. When the PassManager is destroyed, the pass 489/// will be destroyed as well, so there is no need to delete the pass. This 490/// implies that all passes MUST be allocated with 'new'. 491void 492PassManager_New::add(Pass *P) { 493 PM->add(P); 494} 495 496/// run - Execute all of the passes scheduled for execution. Keep track of 497/// whether any of the passes modifies the module, and if so, return true. 498bool 499PassManager_New::run(Module &M) { 500 return PM->run(M); 501} 502 503