PassBuilder.cpp revision 283625 
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
36using namespace llvm;
37
38namespace {
39
40/// \brief No-op module pass which does nothing.
41struct NoOpModulePass {
42  PreservedAnalyses run(Module &M) { return PreservedAnalyses::all(); }
43  static StringRef name() { return "NoOpModulePass"; }
44};
45
46/// \brief No-op module analysis.
47struct NoOpModuleAnalysis {
48  struct Result {};
49  Result run(Module &) { return Result(); }
50  static StringRef name() { return "NoOpModuleAnalysis"; }
51  static void *ID() { return (void *)&PassID; }
52private:
53  static char PassID;
54};
55
56char NoOpModuleAnalysis::PassID;
57
58/// \brief No-op CGSCC pass which does nothing.
59struct NoOpCGSCCPass {
60  PreservedAnalyses run(LazyCallGraph::SCC &C) {
61    return PreservedAnalyses::all();
62  }
63  static StringRef name() { return "NoOpCGSCCPass"; }
64};
65
66/// \brief No-op CGSCC analysis.
67struct NoOpCGSCCAnalysis {
68  struct Result {};
69  Result run(LazyCallGraph::SCC &) { return Result(); }
70  static StringRef name() { return "NoOpCGSCCAnalysis"; }
71  static void *ID() { return (void *)&PassID; }
72private:
73  static char PassID;
74};
75
76char NoOpCGSCCAnalysis::PassID;
77
78/// \brief No-op function pass which does nothing.
79struct NoOpFunctionPass {
80  PreservedAnalyses run(Function &F) { return PreservedAnalyses::all(); }
81  static StringRef name() { return "NoOpFunctionPass"; }
82};
83
84/// \brief No-op function analysis.
85struct NoOpFunctionAnalysis {
86  struct Result {};
87  Result run(Function &) { return Result(); }
88  static StringRef name() { return "NoOpFunctionAnalysis"; }
89  static void *ID() { return (void *)&PassID; }
90private:
91  static char PassID;
92};
93
94char NoOpFunctionAnalysis::PassID;
95
96} // End anonymous namespace.
97
98void PassBuilder::registerModuleAnalyses(ModuleAnalysisManager &MAM) {
99#define MODULE_ANALYSIS(NAME, CREATE_PASS) \
100  MAM.registerPass(CREATE_PASS);
101#include "PassRegistry.def"
102}
103
104void PassBuilder::registerCGSCCAnalyses(CGSCCAnalysisManager &CGAM) {
105#define CGSCC_ANALYSIS(NAME, CREATE_PASS) \
106  CGAM.registerPass(CREATE_PASS);
107#include "PassRegistry.def"
108}
109
110void 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
117static 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
128static 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
138static 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
148bool 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
168bool 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
188bool 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
209bool 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
248bool 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
300bool 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?
371bool 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