Chris Lattner | d695328 | 2002-01-21 07:37:31 +0000 | [diff] [blame] | 1 | //===- Pass.cpp - LLVM Pass Infrastructure Impementation ------------------===// |
| 2 | // |
| 3 | // This file implements the LLVM Pass infrastructure. It is primarily |
| 4 | // responsible with ensuring that passes are executed and batched together |
| 5 | // optimally. |
| 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 9 | #include "llvm/PassManager.h" |
Chris Lattner | d30efaf | 2002-04-28 20:46:05 +0000 | [diff] [blame] | 10 | #include "PassManagerT.h" // PassManagerT implementation |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 11 | #include "llvm/Module.h" |
Chris Lattner | 79df7c0 | 2002-03-26 18:01:55 +0000 | [diff] [blame] | 12 | #include "llvm/Function.h" |
Chris Lattner | 221d688 | 2002-02-12 21:07:25 +0000 | [diff] [blame] | 13 | #include "llvm/BasicBlock.h" |
Chris Lattner | d695328 | 2002-01-21 07:37:31 +0000 | [diff] [blame] | 14 | #include "Support/STLExtras.h" |
Chris Lattner | d30efaf | 2002-04-28 20:46:05 +0000 | [diff] [blame] | 15 | #include "Support/CommandLine.h" |
| 16 | #include <typeinfo> |
| 17 | #include <iostream> |
Chris Lattner | 691fa3c | 2002-04-29 04:04:29 +0000 | [diff] [blame] | 18 | #include <sys/time.h> |
| 19 | #include <stdio.h> |
Chris Lattner | e212062 | 2002-01-23 05:49:41 +0000 | [diff] [blame] | 20 | |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 21 | // Source of unique analysis ID #'s. |
| 22 | unsigned AnalysisID::NextID = 0; |
| 23 | |
| 24 | void AnalysisResolver::setAnalysisResolver(Pass *P, AnalysisResolver *AR) { |
| 25 | assert(P->Resolver == 0 && "Pass already in a PassManager!"); |
| 26 | P->Resolver = AR; |
| 27 | } |
| 28 | |
Chris Lattner | 3330e5b | 2002-04-28 21:25:41 +0000 | [diff] [blame] | 29 | |
| 30 | // preservesCFG - This function should be called to by the pass, iff they do |
| 31 | // not: |
| 32 | // |
| 33 | // 1. Add or remove basic blocks from the function |
| 34 | // 2. Modify terminator instructions in any way. |
| 35 | // |
| 36 | // This function annotates the AnalysisUsage info object to say that analyses |
| 37 | // that only depend on the CFG are preserved by this pass. |
| 38 | // |
| 39 | void AnalysisUsage::preservesCFG() { |
| 40 | // FIXME: implement preservesCFG |
| 41 | } |
| 42 | |
| 43 | |
Chris Lattner | d30efaf | 2002-04-28 20:46:05 +0000 | [diff] [blame] | 44 | //===----------------------------------------------------------------------===// |
| 45 | // PassManager implementation - The PassManager class is a simple Pimpl class |
| 46 | // that wraps the PassManagerT template. |
| 47 | // |
| 48 | PassManager::PassManager() : PM(new PassManagerT<Module>()) {} |
| 49 | PassManager::~PassManager() { delete PM; } |
| 50 | void PassManager::add(Pass *P) { PM->add(P); } |
| 51 | bool PassManager::run(Module *M) { return PM->run(M); } |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 52 | |
Chris Lattner | d30efaf | 2002-04-28 20:46:05 +0000 | [diff] [blame] | 53 | |
| 54 | //===----------------------------------------------------------------------===// |
Chris Lattner | 691fa3c | 2002-04-29 04:04:29 +0000 | [diff] [blame] | 55 | // TimingInfo Class - This class is used to calculate information about the |
| 56 | // amount of time each pass takes to execute. This only happens with |
| 57 | // -time-passes is enabled on the command line. |
| 58 | // |
| 59 | static cl::Flag EnableTiming("time-passes", "Time each pass, printing elapsed" |
| 60 | " time for each on exit"); |
| 61 | |
| 62 | static double getTime() { |
| 63 | struct timeval T; |
| 64 | gettimeofday(&T, 0); |
| 65 | return T.tv_sec + T.tv_usec/1000000.0; |
| 66 | } |
| 67 | |
| 68 | // Create method. If Timing is enabled, this creates and returns a new timing |
| 69 | // object, otherwise it returns null. |
| 70 | // |
| 71 | TimingInfo *TimingInfo::create() { |
| 72 | return EnableTiming ? new TimingInfo() : 0; |
| 73 | } |
| 74 | |
| 75 | void TimingInfo::passStarted(Pass *P) { TimingData[P] -= getTime(); } |
| 76 | void TimingInfo::passEnded(Pass *P) { TimingData[P] += getTime(); } |
| 77 | |
| 78 | // TimingDtor - Print out information about timing information |
| 79 | TimingInfo::~TimingInfo() { |
| 80 | // Iterate over all of the data, converting it into the dual of the data map, |
| 81 | // so that the data is sorted by amount of time taken, instead of pointer. |
| 82 | // |
| 83 | std::vector<pair<double, Pass*> > Data; |
| 84 | double TotalTime = 0; |
| 85 | for (std::map<Pass*, double>::iterator I = TimingData.begin(), |
| 86 | E = TimingData.end(); I != E; ++I) |
| 87 | // Throw out results for "grouping" pass managers... |
| 88 | if (!dynamic_cast<AnalysisResolver*>(I->first)) { |
| 89 | Data.push_back(std::make_pair(I->second, I->first)); |
| 90 | TotalTime += I->second; |
| 91 | } |
| 92 | |
| 93 | // Sort the data by time as the primary key, in reverse order... |
| 94 | std::sort(Data.begin(), Data.end(), greater<pair<double, Pass*> >()); |
| 95 | |
| 96 | // Print out timing header... |
| 97 | cerr << std::string(79, '=') << "\n" |
| 98 | << " ... Pass execution timing report ...\n" |
| 99 | << std::string(79, '=') << "\n Total Execution Time: " << TotalTime |
Chris Lattner | 96c466b | 2002-04-29 14:57:45 +0000 | [diff] [blame^] | 100 | << " seconds\n\n % Time: Seconds:\tPass Name:\n"; |
Chris Lattner | 691fa3c | 2002-04-29 04:04:29 +0000 | [diff] [blame] | 101 | |
| 102 | // Loop through all of the timing data, printing it out... |
| 103 | for (unsigned i = 0, e = Data.size(); i != e; ++i) { |
| 104 | fprintf(stderr, " %6.2f%% %fs\t%s\n", Data[i].first*100 / TotalTime, |
Chris Lattner | 96c466b | 2002-04-29 14:57:45 +0000 | [diff] [blame^] | 105 | Data[i].first, Data[i].second->getPassName()); |
Chris Lattner | 691fa3c | 2002-04-29 04:04:29 +0000 | [diff] [blame] | 106 | } |
| 107 | cerr << " 100.00% " << TotalTime << "s\tTOTAL\n" |
| 108 | << std::string(79, '=') << "\n"; |
| 109 | } |
| 110 | |
| 111 | |
| 112 | //===----------------------------------------------------------------------===// |
Chris Lattner | e212062 | 2002-01-23 05:49:41 +0000 | [diff] [blame] | 113 | // Pass debugging information. Often it is useful to find out what pass is |
| 114 | // running when a crash occurs in a utility. When this library is compiled with |
| 115 | // debugging on, a command line option (--debug-pass) is enabled that causes the |
| 116 | // pass name to be printed before it executes. |
| 117 | // |
Chris Lattner | e212062 | 2002-01-23 05:49:41 +0000 | [diff] [blame] | 118 | |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 119 | // Different debug levels that can be enabled... |
| 120 | enum PassDebugLevel { |
| 121 | None, PassStructure, PassExecutions, PassDetails |
| 122 | }; |
Chris Lattner | e212062 | 2002-01-23 05:49:41 +0000 | [diff] [blame] | 123 | |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 124 | static cl::Enum<enum PassDebugLevel> PassDebugging("debug-pass", cl::Hidden, |
| 125 | "Print PassManager debugging information", |
| 126 | clEnumVal(None , "disable debug output"), |
| 127 | clEnumVal(PassStructure , "print pass structure before run()"), |
| 128 | clEnumVal(PassExecutions, "print pass name before it is executed"), |
| 129 | clEnumVal(PassDetails , "print pass details when it is executed"), 0); |
| 130 | |
| 131 | void PMDebug::PrintPassStructure(Pass *P) { |
| 132 | if (PassDebugging >= PassStructure) |
| 133 | P->dumpPassStructure(); |
| 134 | } |
| 135 | |
| 136 | void PMDebug::PrintPassInformation(unsigned Depth, const char *Action, |
Chris Lattner | 2e9175a | 2002-04-28 05:14:06 +0000 | [diff] [blame] | 137 | Pass *P, Annotable *V) { |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 138 | if (PassDebugging >= PassExecutions) { |
Chris Lattner | ce885e9 | 2002-01-31 18:32:27 +0000 | [diff] [blame] | 139 | std::cerr << (void*)P << std::string(Depth*2+1, ' ') << Action << " '" |
Chris Lattner | 96c466b | 2002-04-29 14:57:45 +0000 | [diff] [blame^] | 140 | << P->getPassName(); |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 141 | if (V) { |
| 142 | std::cerr << "' on "; |
Chris Lattner | 2e9175a | 2002-04-28 05:14:06 +0000 | [diff] [blame] | 143 | |
| 144 | if (dynamic_cast<Module*>(V)) { |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 145 | std::cerr << "Module\n"; return; |
Chris Lattner | 2e9175a | 2002-04-28 05:14:06 +0000 | [diff] [blame] | 146 | } else if (Function *F = dynamic_cast<Function*>(V)) |
| 147 | std::cerr << "Function '" << F->getName(); |
| 148 | else if (BasicBlock *BB = dynamic_cast<BasicBlock*>(V)) |
| 149 | std::cerr << "BasicBlock '" << BB->getName(); |
| 150 | else if (Value *Val = dynamic_cast<Value*>(V)) |
| 151 | std::cerr << typeid(*Val).name() << " '" << Val->getName(); |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 152 | } |
| 153 | std::cerr << "'...\n"; |
| 154 | } |
| 155 | } |
| 156 | |
| 157 | void PMDebug::PrintAnalysisSetInfo(unsigned Depth, const char *Msg, |
Chris Lattner | f57b845 | 2002-04-27 06:56:12 +0000 | [diff] [blame] | 158 | Pass *P, const std::vector<AnalysisID> &Set){ |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 159 | if (PassDebugging >= PassDetails && !Set.empty()) { |
Chris Lattner | ce885e9 | 2002-01-31 18:32:27 +0000 | [diff] [blame] | 160 | std::cerr << (void*)P << std::string(Depth*2+3, ' ') << Msg << " Analyses:"; |
Chris Lattner | f57b845 | 2002-04-27 06:56:12 +0000 | [diff] [blame] | 161 | for (unsigned i = 0; i != Set.size(); ++i) { |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 162 | Pass *P = Set[i].createPass(); // Good thing this is just debug code... |
Chris Lattner | 96c466b | 2002-04-29 14:57:45 +0000 | [diff] [blame^] | 163 | std::cerr << " " << P->getPassName(); |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 164 | delete P; |
| 165 | } |
| 166 | std::cerr << "\n"; |
| 167 | } |
| 168 | } |
| 169 | |
| 170 | // dumpPassStructure - Implement the -debug-passes=PassStructure option |
| 171 | void Pass::dumpPassStructure(unsigned Offset = 0) { |
Chris Lattner | 96c466b | 2002-04-29 14:57:45 +0000 | [diff] [blame^] | 172 | std::cerr << std::string(Offset*2, ' ') << getPassName() << "\n"; |
Chris Lattner | e212062 | 2002-01-23 05:49:41 +0000 | [diff] [blame] | 173 | } |
Chris Lattner | e212062 | 2002-01-23 05:49:41 +0000 | [diff] [blame] | 174 | |
| 175 | |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 176 | //===----------------------------------------------------------------------===// |
| 177 | // Pass Implementation |
Chris Lattner | 35f07eb | 2002-01-22 00:17:48 +0000 | [diff] [blame] | 178 | // |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 179 | |
Chris Lattner | f57b845 | 2002-04-27 06:56:12 +0000 | [diff] [blame] | 180 | void Pass::addToPassManager(PassManagerT<Module> *PM, AnalysisUsage &AU) { |
| 181 | PM->addPass(this, AU); |
Chris Lattner | 35f07eb | 2002-01-22 00:17:48 +0000 | [diff] [blame] | 182 | } |
Chris Lattner | d695328 | 2002-01-21 07:37:31 +0000 | [diff] [blame] | 183 | |
Chris Lattner | 96c466b | 2002-04-29 14:57:45 +0000 | [diff] [blame^] | 184 | |
| 185 | // getPassName - Use C++ RTTI to get a SOMEWHAT intelligable name for the pass. |
| 186 | // |
| 187 | const char *Pass::getPassName() const { return typeid(*this).name(); } |
| 188 | |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 189 | //===----------------------------------------------------------------------===// |
Chris Lattner | f57b845 | 2002-04-27 06:56:12 +0000 | [diff] [blame] | 190 | // FunctionPass Implementation |
Chris Lattner | d695328 | 2002-01-21 07:37:31 +0000 | [diff] [blame] | 191 | // |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 192 | |
Chris Lattner | f57b845 | 2002-04-27 06:56:12 +0000 | [diff] [blame] | 193 | // run - On a module, we run this pass by initializing, runOnFunction'ing once |
| 194 | // for every function in the module, then by finalizing. |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 195 | // |
Chris Lattner | f57b845 | 2002-04-27 06:56:12 +0000 | [diff] [blame] | 196 | bool FunctionPass::run(Module *M) { |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 197 | bool Changed = doInitialization(M); |
| 198 | |
| 199 | for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) |
Chris Lattner | f57b845 | 2002-04-27 06:56:12 +0000 | [diff] [blame] | 200 | if (!(*I)->isExternal()) // Passes are not run on external functions! |
| 201 | Changed |= runOnFunction(*I); |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 202 | |
| 203 | return Changed | doFinalization(M); |
Chris Lattner | d695328 | 2002-01-21 07:37:31 +0000 | [diff] [blame] | 204 | } |
| 205 | |
Chris Lattner | f57b845 | 2002-04-27 06:56:12 +0000 | [diff] [blame] | 206 | // run - On a function, we simply initialize, run the function, then finalize. |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 207 | // |
Chris Lattner | f57b845 | 2002-04-27 06:56:12 +0000 | [diff] [blame] | 208 | bool FunctionPass::run(Function *F) { |
| 209 | if (F->isExternal()) return false;// Passes are not run on external functions! |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 210 | |
Chris Lattner | f57b845 | 2002-04-27 06:56:12 +0000 | [diff] [blame] | 211 | return doInitialization(F->getParent()) | runOnFunction(F) |
Chris Lattner | 79df7c0 | 2002-03-26 18:01:55 +0000 | [diff] [blame] | 212 | | doFinalization(F->getParent()); |
Chris Lattner | d695328 | 2002-01-21 07:37:31 +0000 | [diff] [blame] | 213 | } |
Chris Lattner | e212062 | 2002-01-23 05:49:41 +0000 | [diff] [blame] | 214 | |
Chris Lattner | f57b845 | 2002-04-27 06:56:12 +0000 | [diff] [blame] | 215 | void FunctionPass::addToPassManager(PassManagerT<Module> *PM, |
| 216 | AnalysisUsage &AU) { |
| 217 | PM->addPass(this, AU); |
Chris Lattner | e212062 | 2002-01-23 05:49:41 +0000 | [diff] [blame] | 218 | } |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 219 | |
Chris Lattner | f57b845 | 2002-04-27 06:56:12 +0000 | [diff] [blame] | 220 | void FunctionPass::addToPassManager(PassManagerT<Function> *PM, |
| 221 | AnalysisUsage &AU) { |
| 222 | PM->addPass(this, AU); |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 223 | } |
| 224 | |
| 225 | //===----------------------------------------------------------------------===// |
| 226 | // BasicBlockPass Implementation |
| 227 | // |
| 228 | |
Chris Lattner | f57b845 | 2002-04-27 06:56:12 +0000 | [diff] [blame] | 229 | // To run this pass on a function, we simply call runOnBasicBlock once for each |
| 230 | // function. |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 231 | // |
Chris Lattner | f57b845 | 2002-04-27 06:56:12 +0000 | [diff] [blame] | 232 | bool BasicBlockPass::runOnFunction(Function *F) { |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 233 | bool Changed = false; |
Chris Lattner | 79df7c0 | 2002-03-26 18:01:55 +0000 | [diff] [blame] | 234 | for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 235 | Changed |= runOnBasicBlock(*I); |
| 236 | return Changed; |
| 237 | } |
| 238 | |
| 239 | // To run directly on the basic block, we initialize, runOnBasicBlock, then |
| 240 | // finalize. |
| 241 | // |
| 242 | bool BasicBlockPass::run(BasicBlock *BB) { |
| 243 | Module *M = BB->getParent()->getParent(); |
| 244 | return doInitialization(M) | runOnBasicBlock(BB) | doFinalization(M); |
| 245 | } |
| 246 | |
Chris Lattner | 79df7c0 | 2002-03-26 18:01:55 +0000 | [diff] [blame] | 247 | void BasicBlockPass::addToPassManager(PassManagerT<Function> *PM, |
Chris Lattner | f57b845 | 2002-04-27 06:56:12 +0000 | [diff] [blame] | 248 | AnalysisUsage &AU) { |
| 249 | PM->addPass(this, AU); |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 250 | } |
| 251 | |
| 252 | void BasicBlockPass::addToPassManager(PassManagerT<BasicBlock> *PM, |
Chris Lattner | f57b845 | 2002-04-27 06:56:12 +0000 | [diff] [blame] | 253 | AnalysisUsage &AU) { |
| 254 | PM->addPass(this, AU); |
Chris Lattner | 4130086 | 2002-01-31 00:45:31 +0000 | [diff] [blame] | 255 | } |
| 256 | |