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