[PM] Actually add the new pass manager support for the assumption cache.
[oota-llvm.git] / tools / opt / Passes.cpp
1 //===- Passes.cpp - Parsing, selection, and running of passes -------------===//
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 /// \file
10 ///
11 /// This file provides the infrastructure to parse and build a custom pass
12 /// manager based on a commandline flag. It also provides helpers to aid in
13 /// analyzing, debugging, and testing pass structures.
14 ///
15 //===----------------------------------------------------------------------===//
16
17 #include "Passes.h"
18 #include "llvm/Analysis/AssumptionCache.h"
19 #include "llvm/Analysis/CGSCCPassManager.h"
20 #include "llvm/Analysis/LazyCallGraph.h"
21 #include "llvm/Analysis/LoopInfo.h"
22 #include "llvm/Analysis/TargetLibraryInfo.h"
23 #include "llvm/IR/Dominators.h"
24 #include "llvm/IR/IRPrintingPasses.h"
25 #include "llvm/IR/PassManager.h"
26 #include "llvm/IR/Verifier.h"
27 #include "llvm/Support/Debug.h"
28
29 using namespace llvm;
30
31 namespace {
32
33 /// \brief No-op module pass which does nothing.
34 struct NoOpModulePass {
35   PreservedAnalyses run(Module &M) { return PreservedAnalyses::all(); }
36   static StringRef name() { return "NoOpModulePass"; }
37 };
38
39 /// \brief No-op module analysis.
40 struct NoOpModuleAnalysis {
41   struct Result {};
42   Result run(Module &) { return Result(); }
43   static StringRef name() { return "NoOpModuleAnalysis"; }
44   static void *ID() { return (void *)&PassID; }
45 private:
46   static char PassID;
47 };
48
49 char NoOpModuleAnalysis::PassID;
50
51 /// \brief No-op CGSCC pass which does nothing.
52 struct NoOpCGSCCPass {
53   PreservedAnalyses run(LazyCallGraph::SCC &C) {
54     return PreservedAnalyses::all();
55   }
56   static StringRef name() { return "NoOpCGSCCPass"; }
57 };
58
59 /// \brief No-op CGSCC analysis.
60 struct NoOpCGSCCAnalysis {
61   struct Result {};
62   Result run(LazyCallGraph::SCC &) { return Result(); }
63   static StringRef name() { return "NoOpCGSCCAnalysis"; }
64   static void *ID() { return (void *)&PassID; }
65 private:
66   static char PassID;
67 };
68
69 char NoOpCGSCCAnalysis::PassID;
70
71 /// \brief No-op function pass which does nothing.
72 struct NoOpFunctionPass {
73   PreservedAnalyses run(Function &F) { return PreservedAnalyses::all(); }
74   static StringRef name() { return "NoOpFunctionPass"; }
75 };
76
77 /// \brief No-op function analysis.
78 struct NoOpFunctionAnalysis {
79   struct Result {};
80   Result run(Function &) { return Result(); }
81   static StringRef name() { return "NoOpFunctionAnalysis"; }
82   static void *ID() { return (void *)&PassID; }
83 private:
84   static char PassID;
85 };
86
87 char NoOpFunctionAnalysis::PassID;
88
89 } // End anonymous namespace.
90
91 void llvm::registerModuleAnalyses(ModuleAnalysisManager &MAM) {
92 #define MODULE_ANALYSIS(NAME, CREATE_PASS) \
93   MAM.registerPass(CREATE_PASS);
94 #include "PassRegistry.def"
95 }
96
97 void llvm::registerCGSCCAnalyses(CGSCCAnalysisManager &CGAM) {
98 #define CGSCC_ANALYSIS(NAME, CREATE_PASS) \
99   CGAM.registerPass(CREATE_PASS);
100 #include "PassRegistry.def"
101 }
102
103 void llvm::registerFunctionAnalyses(FunctionAnalysisManager &FAM) {
104 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS) \
105   FAM.registerPass(CREATE_PASS);
106 #include "PassRegistry.def"
107 }
108
109 #ifndef NDEBUG
110 static bool isModulePassName(StringRef Name) {
111 #define MODULE_PASS(NAME, CREATE_PASS) if (Name == NAME) return true;
112 #define MODULE_ANALYSIS(NAME, CREATE_PASS)                                     \
113   if (Name == "require<" NAME ">" || Name == "invalidate<" NAME ">")           \
114     return true;
115 #include "PassRegistry.def"
116
117   return false;
118 }
119 #endif
120
121 static bool isCGSCCPassName(StringRef Name) {
122 #define CGSCC_PASS(NAME, CREATE_PASS) if (Name == NAME) return true;
123 #define CGSCC_ANALYSIS(NAME, CREATE_PASS)                                      \
124   if (Name == "require<" NAME ">" || Name == "invalidate<" NAME ">")           \
125     return true;
126 #include "PassRegistry.def"
127
128   return false;
129 }
130
131 static bool isFunctionPassName(StringRef Name) {
132 #define FUNCTION_PASS(NAME, CREATE_PASS) if (Name == NAME) return true;
133 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS)                                   \
134   if (Name == "require<" NAME ">" || Name == "invalidate<" NAME ">")           \
135     return true;
136 #include "PassRegistry.def"
137
138   return false;
139 }
140
141 static bool parseModulePassName(ModulePassManager &MPM, StringRef Name) {
142 #define MODULE_PASS(NAME, CREATE_PASS)                                         \
143   if (Name == NAME) {                                                          \
144     MPM.addPass(CREATE_PASS);                                                  \
145     return true;                                                               \
146   }
147 #define MODULE_ANALYSIS(NAME, CREATE_PASS)                                     \
148   if (Name == "require<" NAME ">") {                                           \
149     MPM.addPass(RequireAnalysisPass<decltype(CREATE_PASS)>());                 \
150     return true;                                                               \
151   }                                                                            \
152   if (Name == "invalidate<" NAME ">") {                                        \
153     MPM.addPass(InvalidateAnalysisPass<decltype(CREATE_PASS)>());              \
154     return true;                                                               \
155   }
156 #include "PassRegistry.def"
157
158   return false;
159 }
160
161 static bool parseCGSCCPassName(CGSCCPassManager &CGPM, StringRef Name) {
162 #define CGSCC_PASS(NAME, CREATE_PASS)                                          \
163   if (Name == NAME) {                                                          \
164     CGPM.addPass(CREATE_PASS);                                                 \
165     return true;                                                               \
166   }
167 #define CGSCC_ANALYSIS(NAME, CREATE_PASS)                                      \
168   if (Name == "require<" NAME ">") {                                           \
169     CGPM.addPass(RequireAnalysisPass<decltype(CREATE_PASS)>());                \
170     return true;                                                               \
171   }                                                                            \
172   if (Name == "invalidate<" NAME ">") {                                        \
173     CGPM.addPass(InvalidateAnalysisPass<decltype(CREATE_PASS)>());             \
174     return true;                                                               \
175   }
176 #include "PassRegistry.def"
177
178   return false;
179 }
180
181 static bool parseFunctionPassName(FunctionPassManager &FPM, StringRef Name) {
182 #define FUNCTION_PASS(NAME, CREATE_PASS)                                       \
183   if (Name == NAME) {                                                          \
184     FPM.addPass(CREATE_PASS);                                                  \
185     return true;                                                               \
186   }
187 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS)                                   \
188   if (Name == "require<" NAME ">") {                                           \
189     FPM.addPass(RequireAnalysisPass<decltype(CREATE_PASS)>());                 \
190     return true;                                                               \
191   }                                                                            \
192   if (Name == "invalidate<" NAME ">") {                                        \
193     FPM.addPass(InvalidateAnalysisPass<decltype(CREATE_PASS)>());              \
194     return true;                                                               \
195   }
196 #include "PassRegistry.def"
197
198   return false;
199 }
200
201 static bool parseFunctionPassPipeline(FunctionPassManager &FPM,
202                                       StringRef &PipelineText,
203                                       bool VerifyEachPass, bool DebugLogging) {
204   for (;;) {
205     // Parse nested pass managers by recursing.
206     if (PipelineText.startswith("function(")) {
207       FunctionPassManager NestedFPM(DebugLogging);
208
209       // Parse the inner pipeline inte the nested manager.
210       PipelineText = PipelineText.substr(strlen("function("));
211       if (!parseFunctionPassPipeline(NestedFPM, PipelineText, VerifyEachPass,
212                                      DebugLogging) ||
213           PipelineText.empty())
214         return false;
215       assert(PipelineText[0] == ')');
216       PipelineText = PipelineText.substr(1);
217
218       // Add the nested pass manager with the appropriate adaptor.
219       FPM.addPass(std::move(NestedFPM));
220     } else {
221       // Otherwise try to parse a pass name.
222       size_t End = PipelineText.find_first_of(",)");
223       if (!parseFunctionPassName(FPM, PipelineText.substr(0, End)))
224         return false;
225       if (VerifyEachPass)
226         FPM.addPass(VerifierPass());
227
228       PipelineText = PipelineText.substr(End);
229     }
230
231     if (PipelineText.empty() || PipelineText[0] == ')')
232       return true;
233
234     assert(PipelineText[0] == ',');
235     PipelineText = PipelineText.substr(1);
236   }
237 }
238
239 static bool parseCGSCCPassPipeline(CGSCCPassManager &CGPM,
240                                    StringRef &PipelineText, bool VerifyEachPass,
241                                    bool DebugLogging) {
242   for (;;) {
243     // Parse nested pass managers by recursing.
244     if (PipelineText.startswith("cgscc(")) {
245       CGSCCPassManager NestedCGPM(DebugLogging);
246
247       // Parse the inner pipeline into the nested manager.
248       PipelineText = PipelineText.substr(strlen("cgscc("));
249       if (!parseCGSCCPassPipeline(NestedCGPM, PipelineText, VerifyEachPass,
250                                   DebugLogging) ||
251           PipelineText.empty())
252         return false;
253       assert(PipelineText[0] == ')');
254       PipelineText = PipelineText.substr(1);
255
256       // Add the nested pass manager with the appropriate adaptor.
257       CGPM.addPass(std::move(NestedCGPM));
258     } else if (PipelineText.startswith("function(")) {
259       FunctionPassManager NestedFPM(DebugLogging);
260
261       // Parse the inner pipeline inte the nested manager.
262       PipelineText = PipelineText.substr(strlen("function("));
263       if (!parseFunctionPassPipeline(NestedFPM, PipelineText, VerifyEachPass,
264                                      DebugLogging) ||
265           PipelineText.empty())
266         return false;
267       assert(PipelineText[0] == ')');
268       PipelineText = PipelineText.substr(1);
269
270       // Add the nested pass manager with the appropriate adaptor.
271       CGPM.addPass(createCGSCCToFunctionPassAdaptor(std::move(NestedFPM)));
272     } else {
273       // Otherwise try to parse a pass name.
274       size_t End = PipelineText.find_first_of(",)");
275       if (!parseCGSCCPassName(CGPM, PipelineText.substr(0, End)))
276         return false;
277       // FIXME: No verifier support for CGSCC passes!
278
279       PipelineText = PipelineText.substr(End);
280     }
281
282     if (PipelineText.empty() || PipelineText[0] == ')')
283       return true;
284
285     assert(PipelineText[0] == ',');
286     PipelineText = PipelineText.substr(1);
287   }
288 }
289
290 static bool parseModulePassPipeline(ModulePassManager &MPM,
291                                     StringRef &PipelineText,
292                                     bool VerifyEachPass, bool DebugLogging) {
293   for (;;) {
294     // Parse nested pass managers by recursing.
295     if (PipelineText.startswith("module(")) {
296       ModulePassManager NestedMPM(DebugLogging);
297
298       // Parse the inner pipeline into the nested manager.
299       PipelineText = PipelineText.substr(strlen("module("));
300       if (!parseModulePassPipeline(NestedMPM, PipelineText, VerifyEachPass,
301                                    DebugLogging) ||
302           PipelineText.empty())
303         return false;
304       assert(PipelineText[0] == ')');
305       PipelineText = PipelineText.substr(1);
306
307       // Now add the nested manager as a module pass.
308       MPM.addPass(std::move(NestedMPM));
309     } else if (PipelineText.startswith("cgscc(")) {
310       CGSCCPassManager NestedCGPM(DebugLogging);
311
312       // Parse the inner pipeline inte the nested manager.
313       PipelineText = PipelineText.substr(strlen("cgscc("));
314       if (!parseCGSCCPassPipeline(NestedCGPM, PipelineText, VerifyEachPass,
315                                   DebugLogging) ||
316           PipelineText.empty())
317         return false;
318       assert(PipelineText[0] == ')');
319       PipelineText = PipelineText.substr(1);
320
321       // Add the nested pass manager with the appropriate adaptor.
322       MPM.addPass(
323           createModuleToPostOrderCGSCCPassAdaptor(std::move(NestedCGPM)));
324     } else if (PipelineText.startswith("function(")) {
325       FunctionPassManager NestedFPM(DebugLogging);
326
327       // Parse the inner pipeline inte the nested manager.
328       PipelineText = PipelineText.substr(strlen("function("));
329       if (!parseFunctionPassPipeline(NestedFPM, PipelineText, VerifyEachPass,
330                                      DebugLogging) ||
331           PipelineText.empty())
332         return false;
333       assert(PipelineText[0] == ')');
334       PipelineText = PipelineText.substr(1);
335
336       // Add the nested pass manager with the appropriate adaptor.
337       MPM.addPass(createModuleToFunctionPassAdaptor(std::move(NestedFPM)));
338     } else {
339       // Otherwise try to parse a pass name.
340       size_t End = PipelineText.find_first_of(",)");
341       if (!parseModulePassName(MPM, PipelineText.substr(0, End)))
342         return false;
343       if (VerifyEachPass)
344         MPM.addPass(VerifierPass());
345
346       PipelineText = PipelineText.substr(End);
347     }
348
349     if (PipelineText.empty() || PipelineText[0] == ')')
350       return true;
351
352     assert(PipelineText[0] == ',');
353     PipelineText = PipelineText.substr(1);
354   }
355 }
356
357 // Primary pass pipeline description parsing routine.
358 // FIXME: Should this routine accept a TargetMachine or require the caller to
359 // pre-populate the analysis managers with target-specific stuff?
360 bool llvm::parsePassPipeline(ModulePassManager &MPM, StringRef PipelineText,
361                              bool VerifyEachPass, bool DebugLogging) {
362   // By default, try to parse the pipeline as-if it were within an implicit
363   // 'module(...)' pass pipeline. If this will parse at all, it needs to
364   // consume the entire string.
365   if (parseModulePassPipeline(MPM, PipelineText, VerifyEachPass, DebugLogging))
366     return PipelineText.empty();
367
368   // This isn't parsable as a module pipeline, look for the end of a pass name
369   // and directly drop down to that layer.
370   StringRef FirstName =
371       PipelineText.substr(0, PipelineText.find_first_of(",)"));
372   assert(!isModulePassName(FirstName) &&
373          "Already handled all module pipeline options.");
374
375   // If this looks like a CGSCC pass, parse the whole thing as a CGSCC
376   // pipeline.
377   if (isCGSCCPassName(FirstName)) {
378     CGSCCPassManager CGPM(DebugLogging);
379     if (!parseCGSCCPassPipeline(CGPM, PipelineText, VerifyEachPass,
380                                 DebugLogging) ||
381         !PipelineText.empty())
382       return false;
383     MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
384     return true;
385   }
386
387   // Similarly, if this looks like a Function pass, parse the whole thing as
388   // a Function pipelien.
389   if (isFunctionPassName(FirstName)) {
390     FunctionPassManager FPM(DebugLogging);
391     if (!parseFunctionPassPipeline(FPM, PipelineText, VerifyEachPass,
392                                    DebugLogging) ||
393         !PipelineText.empty())
394       return false;
395     MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
396     return true;
397   }
398
399   return false;
400 }