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