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