xref: /llvm-project/polly/lib/Support/RegisterPasses.cpp (revision d86a206f06a51c12a9fcf2c20199f4e819751c0c)
1 //===------ RegisterPasses.cpp - Add the Polly Passes to default passes  --===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file composes the individual LLVM-IR passes provided by Polly to a
10 // functional polyhedral optimizer. The polyhedral optimizer is automatically
11 // made available to LLVM based compilers by loading the Polly shared library
12 // into such a compiler.
13 //
14 // The Polly optimizer is made available by executing a static constructor that
15 // registers the individual Polly passes in the LLVM pass manager builder. The
16 // passes are registered such that the default behaviour of the compiler is not
17 // changed, but that the flag '-polly' provided at optimization level '-O3'
18 // enables additional polyhedral optimizations.
19 //===----------------------------------------------------------------------===//
20 
21 #include "polly/RegisterPasses.h"
22 #include "polly/Canonicalization.h"
23 #include "polly/CodeGen/CodeGeneration.h"
24 #include "polly/CodeGen/CodegenCleanup.h"
25 #include "polly/CodeGen/IslAst.h"
26 #include "polly/CodePreparation.h"
27 #include "polly/DeLICM.h"
28 #include "polly/DeadCodeElimination.h"
29 #include "polly/DependenceInfo.h"
30 #include "polly/ForwardOpTree.h"
31 #include "polly/JSONExporter.h"
32 #include "polly/LinkAllPasses.h"
33 #include "polly/MaximalStaticExpansion.h"
34 #include "polly/PolyhedralInfo.h"
35 #include "polly/PruneUnprofitable.h"
36 #include "polly/ScheduleOptimizer.h"
37 #include "polly/ScopDetection.h"
38 #include "polly/ScopGraphPrinter.h"
39 #include "polly/ScopInfo.h"
40 #include "polly/Simplify.h"
41 #include "polly/Support/DumpFunctionPass.h"
42 #include "polly/Support/DumpModulePass.h"
43 #include "llvm/Analysis/CFGPrinter.h"
44 #include "llvm/IR/LegacyPassManager.h"
45 #include "llvm/IR/PassManager.h"
46 #include "llvm/IR/Verifier.h"
47 #include "llvm/Passes/PassBuilder.h"
48 #include "llvm/Passes/PassPlugin.h"
49 #include "llvm/Support/CommandLine.h"
50 #include "llvm/Support/TargetSelect.h"
51 #include "llvm/Transforms/IPO.h"
52 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
53 
54 namespace cl = llvm::cl;
55 
56 using llvm::FunctionPassManager;
57 using llvm::OptimizationLevel;
58 using llvm::PassBuilder;
59 using llvm::PassInstrumentationCallbacks;
60 
61 cl::OptionCategory PollyCategory("Polly Options",
62                                  "Configure the polly loop optimizer");
63 
64 namespace polly {
65 static cl::opt<bool>
66     PollyEnabled("polly",
67                  cl::desc("Enable the polly optimizer (with -O1, -O2 or -O3)"),
68                  cl::cat(PollyCategory));
69 
70 static cl::opt<bool> PollyDetectOnly(
71     "polly-only-scop-detection",
72     cl::desc("Only run scop detection, but no other optimizations"),
73     cl::cat(PollyCategory));
74 
75 enum PassPositionChoice {
76   POSITION_EARLY,
77   POSITION_AFTER_LOOPOPT,
78   POSITION_BEFORE_VECTORIZER
79 };
80 
81 enum OptimizerChoice { OPTIMIZER_NONE, OPTIMIZER_ISL };
82 
83 static cl::opt<PassPositionChoice> PassPosition(
84     "polly-position", cl::desc("Where to run polly in the pass pipeline"),
85     cl::values(
86         clEnumValN(POSITION_EARLY, "early", "Before everything"),
87         clEnumValN(POSITION_AFTER_LOOPOPT, "after-loopopt",
88                    "After the loop optimizer (but within the inline cycle)"),
89         clEnumValN(POSITION_BEFORE_VECTORIZER, "before-vectorizer",
90                    "Right before the vectorizer")),
91     cl::Hidden, cl::init(POSITION_BEFORE_VECTORIZER), cl::ZeroOrMore,
92     cl::cat(PollyCategory));
93 
94 static cl::opt<OptimizerChoice>
95     Optimizer("polly-optimizer", cl::desc("Select the scheduling optimizer"),
96               cl::values(clEnumValN(OPTIMIZER_NONE, "none", "No optimizer"),
97                          clEnumValN(OPTIMIZER_ISL, "isl",
98                                     "The isl scheduling optimizer")),
99               cl::Hidden, cl::init(OPTIMIZER_ISL), cl::cat(PollyCategory));
100 
101 enum CodeGenChoice { CODEGEN_FULL, CODEGEN_AST, CODEGEN_NONE };
102 static cl::opt<CodeGenChoice> CodeGeneration(
103     "polly-code-generation", cl::desc("How much code-generation to perform"),
104     cl::values(clEnumValN(CODEGEN_FULL, "full", "AST and IR generation"),
105                clEnumValN(CODEGEN_AST, "ast", "Only AST generation"),
106                clEnumValN(CODEGEN_NONE, "none", "No code generation")),
107     cl::Hidden, cl::init(CODEGEN_FULL), cl::ZeroOrMore, cl::cat(PollyCategory));
108 
109 enum TargetChoice { TARGET_CPU, TARGET_GPU, TARGET_HYBRID };
110 static cl::opt<TargetChoice>
111     Target("polly-target", cl::desc("The hardware to target"),
112            cl::values(clEnumValN(TARGET_CPU, "cpu", "generate CPU code")
113 #ifdef GPU_CODEGEN
114                           ,
115                       clEnumValN(TARGET_GPU, "gpu", "generate GPU code"),
116                       clEnumValN(TARGET_HYBRID, "hybrid",
117                                  "generate GPU code (preferably) or CPU code")
118 #endif
119                           ),
120            cl::init(TARGET_CPU), cl::ZeroOrMore, cl::cat(PollyCategory));
121 
122 VectorizerChoice PollyVectorizerChoice;
123 
124 static cl::opt<VectorizerChoice, true> Vectorizer(
125     "polly-vectorizer", cl::desc("Select the vectorization strategy"),
126     cl::values(
127         clEnumValN(VECTORIZER_NONE, "none", "No Vectorization"),
128         clEnumValN(VECTORIZER_POLLY, "polly", "Polly internal vectorizer"),
129         clEnumValN(
130             VECTORIZER_STRIPMINE, "stripmine",
131             "Strip-mine outer loops for the loop-vectorizer to trigger")),
132     cl::location(PollyVectorizerChoice), cl::init(VECTORIZER_NONE),
133     cl::ZeroOrMore, cl::cat(PollyCategory));
134 
135 static cl::opt<bool> ImportJScop(
136     "polly-import",
137     cl::desc("Import the polyhedral description of the detected Scops"),
138     cl::Hidden, cl::cat(PollyCategory));
139 
140 static cl::opt<bool> FullyIndexedStaticExpansion(
141     "polly-enable-mse",
142     cl::desc("Fully expand the memory accesses of the detected Scops"),
143     cl::Hidden, cl::cat(PollyCategory));
144 
145 static cl::opt<bool> ExportJScop(
146     "polly-export",
147     cl::desc("Export the polyhedral description of the detected Scops"),
148     cl::Hidden, cl::cat(PollyCategory));
149 
150 static cl::opt<bool> DeadCodeElim("polly-run-dce",
151                                   cl::desc("Run the dead code elimination"),
152                                   cl::Hidden, cl::cat(PollyCategory));
153 
154 static cl::opt<bool> PollyViewer(
155     "polly-show",
156     cl::desc("Highlight the code regions that will be optimized in a "
157              "(CFG BBs and LLVM-IR instructions)"),
158     cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
159 
160 static cl::opt<bool> PollyOnlyViewer(
161     "polly-show-only",
162     cl::desc("Highlight the code regions that will be optimized in "
163              "a (CFG only BBs)"),
164     cl::init(false), cl::cat(PollyCategory));
165 
166 static cl::opt<bool>
167     PollyPrinter("polly-dot", cl::desc("Enable the Polly DOT printer in -O3"),
168                  cl::Hidden, cl::value_desc("Run the Polly DOT printer at -O3"),
169                  cl::init(false), cl::cat(PollyCategory));
170 
171 static cl::opt<bool> PollyOnlyPrinter(
172     "polly-dot-only",
173     cl::desc("Enable the Polly DOT printer in -O3 (no BB content)"), cl::Hidden,
174     cl::value_desc("Run the Polly DOT printer at -O3 (no BB content"),
175     cl::init(false), cl::cat(PollyCategory));
176 
177 static cl::opt<bool>
178     CFGPrinter("polly-view-cfg",
179                cl::desc("Show the Polly CFG right after code generation"),
180                cl::Hidden, cl::init(false), cl::cat(PollyCategory));
181 
182 static cl::opt<bool>
183     EnablePolyhedralInfo("polly-enable-polyhedralinfo",
184                          cl::desc("Enable polyhedral interface of Polly"),
185                          cl::Hidden, cl::init(false), cl::cat(PollyCategory));
186 
187 static cl::opt<bool>
188     EnableForwardOpTree("polly-enable-optree",
189                         cl::desc("Enable operand tree forwarding"), cl::Hidden,
190                         cl::init(true), cl::cat(PollyCategory));
191 
192 static cl::opt<bool>
193     DumpBefore("polly-dump-before",
194                cl::desc("Dump module before Polly transformations into a file "
195                         "suffixed with \"-before\""),
196                cl::init(false), cl::cat(PollyCategory));
197 
198 static cl::list<std::string> DumpBeforeFile(
199     "polly-dump-before-file",
200     cl::desc("Dump module before Polly transformations to the given file"),
201     cl::cat(PollyCategory));
202 
203 static cl::opt<bool>
204     DumpAfter("polly-dump-after",
205               cl::desc("Dump module after Polly transformations into a file "
206                        "suffixed with \"-after\""),
207               cl::init(false), cl::cat(PollyCategory));
208 
209 static cl::list<std::string> DumpAfterFile(
210     "polly-dump-after-file",
211     cl::desc("Dump module after Polly transformations to the given file"),
212     cl::cat(PollyCategory));
213 
214 static cl::opt<bool>
215     EnableDeLICM("polly-enable-delicm",
216                  cl::desc("Eliminate scalar loop carried dependences"),
217                  cl::Hidden, cl::init(true), cl::cat(PollyCategory));
218 
219 static cl::opt<bool>
220     EnableSimplify("polly-enable-simplify",
221                    cl::desc("Simplify SCoP after optimizations"),
222                    cl::init(true), cl::cat(PollyCategory));
223 
224 static cl::opt<bool> EnablePruneUnprofitable(
225     "polly-enable-prune-unprofitable",
226     cl::desc("Bail out on unprofitable SCoPs before rescheduling"), cl::Hidden,
227     cl::init(true), cl::cat(PollyCategory));
228 
229 namespace {
230 
231 /// Initialize Polly passes when library is loaded.
232 ///
233 /// We use the constructor of a statically declared object to initialize the
234 /// different Polly passes right after the Polly library is loaded. This ensures
235 /// that the Polly passes are available e.g. in the 'opt' tool.
236 struct StaticInitializer {
237   StaticInitializer() {
238     llvm::PassRegistry &Registry = *llvm::PassRegistry::getPassRegistry();
239     polly::initializePollyPasses(Registry);
240   }
241 };
242 static StaticInitializer InitializeEverything;
243 } // end of anonymous namespace.
244 
245 void initializePollyPasses(llvm::PassRegistry &Registry) {
246   initializeCodeGenerationPass(Registry);
247 
248 #ifdef GPU_CODEGEN
249   initializePPCGCodeGenerationPass(Registry);
250   initializeManagedMemoryRewritePassPass(Registry);
251   LLVMInitializeNVPTXTarget();
252   LLVMInitializeNVPTXTargetInfo();
253   LLVMInitializeNVPTXTargetMC();
254   LLVMInitializeNVPTXAsmPrinter();
255 #endif
256   initializeCodePreparationPass(Registry);
257   initializeDeadCodeElimWrapperPassPass(Registry);
258   initializeDependenceInfoPass(Registry);
259   initializeDependenceInfoPrinterLegacyPassPass(Registry);
260   initializeDependenceInfoWrapperPassPass(Registry);
261   initializeDependenceInfoPrinterLegacyFunctionPassPass(Registry);
262   initializeJSONExporterPass(Registry);
263   initializeJSONImporterPass(Registry);
264   initializeJSONImporterPrinterLegacyPassPass(Registry);
265   initializeMaximalStaticExpanderWrapperPassPass(Registry);
266   initializeIslAstInfoWrapperPassPass(Registry);
267   initializeIslAstInfoPrinterLegacyPassPass(Registry);
268   initializeIslScheduleOptimizerWrapperPassPass(Registry);
269   initializeIslScheduleOptimizerPrinterLegacyPassPass(Registry);
270   initializePollyCanonicalizePass(Registry);
271   initializePolyhedralInfoPass(Registry);
272   initializePolyhedralInfoPrinterLegacyPassPass(Registry);
273   initializeScopDetectionWrapperPassPass(Registry);
274   initializeScopDetectionPrinterLegacyPassPass(Registry);
275   initializeScopInlinerPass(Registry);
276   initializeScopInfoRegionPassPass(Registry);
277   initializeScopInfoPrinterLegacyRegionPassPass(Registry);
278   initializeScopInfoWrapperPassPass(Registry);
279   initializeScopInfoPrinterLegacyFunctionPassPass(Registry);
280   initializeCodegenCleanupPass(Registry);
281   initializeFlattenSchedulePass(Registry);
282   initializeFlattenSchedulePrinterLegacyPassPass(Registry);
283   initializeForwardOpTreeWrapperPassPass(Registry);
284   initializeForwardOpTreePrinterLegacyPassPass(Registry);
285   initializeDeLICMWrapperPassPass(Registry);
286   initializeDeLICMPrinterLegacyPassPass(Registry);
287   initializeSimplifyWrapperPassPass(Registry);
288   initializeSimplifyPrinterLegacyPassPass(Registry);
289   initializeDumpModuleWrapperPassPass(Registry);
290   initializePruneUnprofitableWrapperPassPass(Registry);
291 }
292 
293 /// Register Polly passes such that they form a polyhedral optimizer.
294 ///
295 /// The individual Polly passes are registered in the pass manager such that
296 /// they form a full polyhedral optimizer. The flow of the optimizer starts with
297 /// a set of preparing transformations that canonicalize the LLVM-IR such that
298 /// the LLVM-IR is easier for us to understand and to optimizes. On the
299 /// canonicalized LLVM-IR we first run the ScopDetection pass, which detects
300 /// static control flow regions. Those regions are then translated by the
301 /// ScopInfo pass into a polyhedral representation. As a next step, a scheduling
302 /// optimizer is run on the polyhedral representation and finally the optimized
303 /// polyhedral representation is code generated back to LLVM-IR.
304 ///
305 /// Besides this core functionality, we optionally schedule passes that provide
306 /// a graphical view of the scops (Polly[Only]Viewer, Polly[Only]Printer), that
307 /// allow the export/import of the polyhedral representation
308 /// (JSCON[Exporter|Importer]) or that show the cfg after code generation.
309 ///
310 /// For certain parts of the Polly optimizer, several alternatives are provided:
311 ///
312 /// As scheduling optimizer we support the isl scheduling optimizer
313 /// (http://freecode.com/projects/isl).
314 /// It is also possible to run Polly with no optimizer. This mode is mainly
315 /// provided to analyze the run and compile time changes caused by the
316 /// scheduling optimizer.
317 ///
318 /// Polly supports the isl internal code generator.
319 static void registerPollyPasses(llvm::legacy::PassManagerBase &PM,
320                                 bool EnableForOpt) {
321   if (DumpBefore)
322     PM.add(polly::createDumpModuleWrapperPass("-before", true));
323   for (auto &Filename : DumpBeforeFile)
324     PM.add(polly::createDumpModuleWrapperPass(Filename, false));
325 
326   PM.add(polly::createCodePreparationPass());
327   PM.add(polly::createScopDetectionWrapperPassPass());
328 
329   if (PollyDetectOnly)
330     return;
331 
332   if (PollyViewer)
333     PM.add(polly::createDOTViewerWrapperPass());
334   if (PollyOnlyViewer)
335     PM.add(polly::createDOTOnlyViewerWrapperPass());
336   if (PollyPrinter)
337     PM.add(polly::createDOTPrinterWrapperPass());
338   if (PollyOnlyPrinter)
339     PM.add(polly::createDOTOnlyPrinterWrapperPass());
340   PM.add(polly::createScopInfoRegionPassPass());
341   if (EnablePolyhedralInfo)
342     PM.add(polly::createPolyhedralInfoPass());
343 
344   if (EnableSimplify)
345     PM.add(polly::createSimplifyWrapperPass(0));
346   if (EnableForwardOpTree)
347     PM.add(polly::createForwardOpTreeWrapperPass());
348   if (EnableDeLICM)
349     PM.add(polly::createDeLICMWrapperPass());
350   if (EnableSimplify)
351     PM.add(polly::createSimplifyWrapperPass(1));
352 
353   if (ImportJScop)
354     PM.add(polly::createJSONImporterPass());
355 
356   if (DeadCodeElim)
357     PM.add(polly::createDeadCodeElimWrapperPass());
358 
359   if (FullyIndexedStaticExpansion)
360     PM.add(polly::createMaximalStaticExpansionPass());
361 
362   if (EnablePruneUnprofitable)
363     PM.add(polly::createPruneUnprofitableWrapperPass());
364 
365 #ifdef GPU_CODEGEN
366   if (Target == TARGET_HYBRID)
367     PM.add(
368         polly::createPPCGCodeGenerationPass(GPUArchChoice, GPURuntimeChoice));
369 #endif
370   if (Target == TARGET_CPU || Target == TARGET_HYBRID)
371     switch (Optimizer) {
372     case OPTIMIZER_NONE:
373       break; /* Do nothing */
374 
375     case OPTIMIZER_ISL:
376       PM.add(polly::createIslScheduleOptimizerWrapperPass());
377       break;
378     }
379 
380   if (ExportJScop)
381     PM.add(polly::createJSONExporterPass());
382 
383   if (!EnableForOpt)
384     return;
385 
386   if (Target == TARGET_CPU || Target == TARGET_HYBRID)
387     switch (CodeGeneration) {
388     case CODEGEN_AST:
389       PM.add(polly::createIslAstInfoWrapperPassPass());
390       break;
391     case CODEGEN_FULL:
392       PM.add(polly::createCodeGenerationPass());
393       break;
394     case CODEGEN_NONE:
395       break;
396     }
397 #ifdef GPU_CODEGEN
398   else {
399     PM.add(
400         polly::createPPCGCodeGenerationPass(GPUArchChoice, GPURuntimeChoice));
401     PM.add(polly::createManagedMemoryRewritePassPass());
402   }
403 #endif
404 
405 #ifdef GPU_CODEGEN
406   if (Target == TARGET_HYBRID)
407     PM.add(polly::createManagedMemoryRewritePassPass(GPUArchChoice,
408                                                      GPURuntimeChoice));
409 #endif
410 
411   // FIXME: This dummy ModulePass keeps some programs from miscompiling,
412   // probably some not correctly preserved analyses. It acts as a barrier to
413   // force all analysis results to be recomputed.
414   PM.add(llvm::createBarrierNoopPass());
415 
416   if (DumpAfter)
417     PM.add(polly::createDumpModuleWrapperPass("-after", true));
418   for (auto &Filename : DumpAfterFile)
419     PM.add(polly::createDumpModuleWrapperPass(Filename, false));
420 
421   if (CFGPrinter)
422     PM.add(llvm::createCFGPrinterLegacyPassPass());
423 }
424 
425 static bool shouldEnablePollyForOptimization() { return PollyEnabled; }
426 
427 static bool shouldEnablePollyForDiagnostic() {
428   // FIXME: PollyTrackFailures is user-controlled, should not be set
429   // programmatically.
430   if (PollyOnlyPrinter || PollyPrinter || PollyOnlyViewer || PollyViewer)
431     PollyTrackFailures = true;
432 
433   return PollyOnlyPrinter || PollyPrinter || PollyOnlyViewer || PollyViewer ||
434          ExportJScop;
435 }
436 
437 static void
438 registerPollyEarlyAsPossiblePasses(const llvm::PassManagerBuilder &Builder,
439                                    llvm::legacy::PassManagerBase &PM) {
440   if (PassPosition != POSITION_EARLY)
441     return;
442 
443   bool EnableForOpt = shouldEnablePollyForOptimization() &&
444                       Builder.OptLevel >= 1 && Builder.SizeLevel == 0;
445   if (!shouldEnablePollyForDiagnostic() && !EnableForOpt)
446     return;
447 
448   registerCanonicalicationPasses(PM);
449   registerPollyPasses(PM, EnableForOpt);
450 }
451 
452 static void
453 registerPollyLoopOptimizerEndPasses(const llvm::PassManagerBuilder &Builder,
454                                     llvm::legacy::PassManagerBase &PM) {
455   if (PassPosition != POSITION_AFTER_LOOPOPT)
456     return;
457 
458   bool EnableForOpt = shouldEnablePollyForOptimization() &&
459                       Builder.OptLevel >= 1 && Builder.SizeLevel == 0;
460   if (!shouldEnablePollyForDiagnostic() && !EnableForOpt)
461     return;
462 
463   registerPollyPasses(PM, EnableForOpt);
464   if (EnableForOpt)
465     PM.add(createCodegenCleanupPass());
466 }
467 
468 static void
469 registerPollyScalarOptimizerLatePasses(const llvm::PassManagerBuilder &Builder,
470                                        llvm::legacy::PassManagerBase &PM) {
471   if (PassPosition != POSITION_BEFORE_VECTORIZER)
472     return;
473 
474   bool EnableForOpt = shouldEnablePollyForOptimization() &&
475                       Builder.OptLevel >= 1 && Builder.SizeLevel == 0;
476   if (!shouldEnablePollyForDiagnostic() && !EnableForOpt)
477     return;
478 
479   polly::registerPollyPasses(PM, EnableForOpt);
480   if (EnableForOpt)
481     PM.add(createCodegenCleanupPass());
482 }
483 
484 /// Add the pass sequence required for Polly to the New Pass Manager.
485 ///
486 /// @param PM           The pass manager itself.
487 /// @param Level        The optimization level. Used for the cleanup of Polly's
488 ///                     output.
489 /// @param EnableForOpt Whether to add Polly IR transformations. If False, only
490 ///                     the analysis passes are added, skipping Polly itself.
491 ///                     The IR may still be modified.
492 static void buildCommonPollyPipeline(FunctionPassManager &PM,
493                                      OptimizationLevel Level,
494                                      bool EnableForOpt) {
495   PassBuilder PB;
496   ScopPassManager SPM;
497 
498   PM.addPass(CodePreparationPass());
499 
500   // TODO add utility passes for the various command line options, once they're
501   // ported
502 
503   if (PollyDetectOnly) {
504     // Don't add more passes other than the ScopPassManager's detection passes.
505     PM.addPass(createFunctionToScopPassAdaptor(std::move(SPM)));
506     return;
507   }
508 
509   if (PollyViewer)
510     PM.addPass(ScopViewer());
511   if (PollyOnlyViewer)
512     PM.addPass(ScopOnlyViewer());
513   if (PollyPrinter)
514     PM.addPass(ScopPrinter());
515   if (PollyOnlyPrinter)
516     PM.addPass(ScopOnlyPrinter());
517   if (EnablePolyhedralInfo)
518     llvm::report_fatal_error(
519         "Option -polly-enable-polyhedralinfo not supported with NPM", false);
520 
521   if (EnableSimplify)
522     SPM.addPass(SimplifyPass(0));
523   if (EnableForwardOpTree)
524     SPM.addPass(ForwardOpTreePass());
525   if (EnableDeLICM)
526     SPM.addPass(DeLICMPass());
527   if (EnableSimplify)
528     SPM.addPass(SimplifyPass(1));
529 
530   if (ImportJScop)
531     SPM.addPass(JSONImportPass());
532 
533   if (DeadCodeElim)
534     SPM.addPass(DeadCodeElimPass());
535 
536   if (FullyIndexedStaticExpansion)
537     llvm::report_fatal_error("Option -polly-enable-mse not supported with NPM",
538                              false);
539 
540   if (EnablePruneUnprofitable)
541     SPM.addPass(PruneUnprofitablePass());
542 
543   if (Target == TARGET_CPU || Target == TARGET_HYBRID) {
544     switch (Optimizer) {
545     case OPTIMIZER_NONE:
546       break; /* Do nothing */
547     case OPTIMIZER_ISL:
548       SPM.addPass(IslScheduleOptimizerPass());
549       break;
550     }
551   }
552 
553   if (ExportJScop)
554     llvm::report_fatal_error("Option -polly-export not supported with NPM",
555                              false);
556 
557   if (!EnableForOpt)
558     return;
559 
560   if (Target == TARGET_CPU || Target == TARGET_HYBRID) {
561     switch (CodeGeneration) {
562     case CODEGEN_AST:
563       SPM.addPass(
564           llvm::RequireAnalysisPass<IslAstAnalysis, Scop, ScopAnalysisManager,
565                                     ScopStandardAnalysisResults &,
566                                     SPMUpdater &>());
567       break;
568     case CODEGEN_FULL:
569       SPM.addPass(CodeGenerationPass());
570       break;
571     case CODEGEN_NONE:
572       break;
573     }
574   }
575 #ifdef GPU_CODEGEN
576   else
577     llvm::report_fatal_error("Option -polly-target=gpu not supported for NPM",
578                              false);
579 #endif
580 
581 #ifdef GPU_CODEGEN
582   if (Target == TARGET_HYBRID)
583     llvm::report_fatal_error(
584         "Option -polly-target=hybrid not supported for NPM", false);
585 #endif
586 
587   PM.addPass(createFunctionToScopPassAdaptor(std::move(SPM)));
588   PM.addPass(PB.buildFunctionSimplificationPipeline(
589       Level, llvm::ThinOrFullLTOPhase::None)); // Cleanup
590 
591   if (CFGPrinter)
592     PM.addPass(llvm::CFGPrinterPass());
593 }
594 
595 static void buildEarlyPollyPipeline(llvm::ModulePassManager &MPM,
596                                     llvm::OptimizationLevel Level) {
597   bool EnableForOpt =
598       shouldEnablePollyForOptimization() && Level.isOptimizingForSpeed();
599   if (!shouldEnablePollyForDiagnostic() && !EnableForOpt)
600     return;
601 
602   FunctionPassManager FPM = buildCanonicalicationPassesForNPM(MPM, Level);
603 
604   if (DumpBefore || !DumpBeforeFile.empty()) {
605     MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
606 
607     if (DumpBefore)
608       MPM.addPass(DumpModulePass("-before", true));
609     for (auto &Filename : DumpBeforeFile)
610       MPM.addPass(DumpModulePass(Filename, false));
611 
612     FPM = FunctionPassManager();
613   }
614 
615   buildCommonPollyPipeline(FPM, Level, EnableForOpt);
616   MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
617 
618   if (DumpAfter)
619     MPM.addPass(DumpModulePass("-after", true));
620   for (auto &Filename : DumpAfterFile)
621     MPM.addPass(DumpModulePass(Filename, false));
622 }
623 
624 static void buildLatePollyPipeline(FunctionPassManager &PM,
625                                    llvm::OptimizationLevel Level) {
626   bool EnableForOpt =
627       shouldEnablePollyForOptimization() && Level.isOptimizingForSpeed();
628   if (!shouldEnablePollyForDiagnostic() && !EnableForOpt)
629     return;
630 
631   if (DumpBefore)
632     PM.addPass(DumpFunctionPass("-before"));
633   if (!DumpBeforeFile.empty())
634     llvm::report_fatal_error(
635         "Option -polly-dump-before-file at -polly-position=late "
636         "not supported with NPM",
637         false);
638 
639   buildCommonPollyPipeline(PM, Level, EnableForOpt);
640 
641   if (DumpAfter)
642     PM.addPass(DumpFunctionPass("-after"));
643   if (!DumpAfterFile.empty())
644     llvm::report_fatal_error(
645         "Option -polly-dump-after-file at -polly-position=late "
646         "not supported with NPM",
647         false);
648 }
649 
650 /// Register Polly to be available as an optimizer
651 ///
652 ///
653 /// We can currently run Polly at three different points int the pass manager.
654 /// a) very early, b) after the canonicalizing loop transformations and c) right
655 /// before the vectorizer.
656 ///
657 /// The default is currently a), to register Polly such that it runs as early as
658 /// possible. This has several implications:
659 ///
660 ///   1) We need to schedule more canonicalization passes
661 ///
662 ///   As nothing is run before Polly, it is necessary to run a set of preparing
663 ///   transformations before Polly to canonicalize the LLVM-IR and to allow
664 ///   Polly to detect and understand the code.
665 ///
666 ///   2) LICM and LoopIdiom pass have not yet been run
667 ///
668 ///   Loop invariant code motion as well as the loop idiom recognition pass make
669 ///   it more difficult for Polly to transform code. LICM may introduce
670 ///   additional data dependences that are hard to eliminate and the loop idiom
671 ///   recognition pass may introduce calls to memset that we currently do not
672 ///   understand. By running Polly early enough (meaning before these passes) we
673 ///   avoid difficulties that may be introduced by these passes.
674 ///
675 ///   3) We get the full -O3 optimization sequence after Polly
676 ///
677 ///   The LLVM-IR that is generated by Polly has been optimized on a high level,
678 ///   but it may be rather inefficient on the lower/scalar level. By scheduling
679 ///   Polly before all other passes, we have the full sequence of -O3
680 ///   optimizations behind us, such that inefficiencies on the low level can
681 ///   be optimized away.
682 ///
683 /// We are currently evaluating the benefit or running Polly at position b) or
684 /// c). b) is likely too early as it interacts with the inliner. c) is nice
685 /// as everything is fully inlined and canonicalized, but we need to be able
686 /// to handle LICMed code to make it useful.
687 static llvm::RegisterStandardPasses RegisterPollyOptimizerEarly(
688     llvm::PassManagerBuilder::EP_ModuleOptimizerEarly,
689     registerPollyEarlyAsPossiblePasses);
690 
691 static llvm::RegisterStandardPasses
692     RegisterPollyOptimizerLoopEnd(llvm::PassManagerBuilder::EP_LoopOptimizerEnd,
693                                   registerPollyLoopOptimizerEndPasses);
694 
695 static llvm::RegisterStandardPasses RegisterPollyOptimizerScalarLate(
696     llvm::PassManagerBuilder::EP_VectorizerStart,
697     registerPollyScalarOptimizerLatePasses);
698 
699 static OwningScopAnalysisManagerFunctionProxy
700 createScopAnalyses(FunctionAnalysisManager &FAM,
701                    PassInstrumentationCallbacks *PIC) {
702   OwningScopAnalysisManagerFunctionProxy Proxy;
703 #define SCOP_ANALYSIS(NAME, CREATE_PASS)                                       \
704   Proxy.getManager().registerPass([PIC] {                                      \
705     (void)PIC;                                                                 \
706     return CREATE_PASS;                                                        \
707   });
708 #include "PollyPasses.def"
709 
710   Proxy.getManager().registerPass(
711       [&FAM] { return FunctionAnalysisManagerScopProxy(FAM); });
712   return Proxy;
713 }
714 
715 static void registerFunctionAnalyses(FunctionAnalysisManager &FAM,
716                                      PassInstrumentationCallbacks *PIC) {
717 
718 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS)                                   \
719   FAM.registerPass([] { return CREATE_PASS; });
720 
721 #include "PollyPasses.def"
722 
723   FAM.registerPass([&FAM, PIC] { return createScopAnalyses(FAM, PIC); });
724 }
725 
726 static bool
727 parseFunctionPipeline(StringRef Name, FunctionPassManager &FPM,
728                       ArrayRef<PassBuilder::PipelineElement> Pipeline) {
729   if (llvm::parseAnalysisUtilityPasses<OwningScopAnalysisManagerFunctionProxy>(
730           "polly-scop-analyses", Name, FPM))
731     return true;
732 
733 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS)                                   \
734   if (llvm::parseAnalysisUtilityPasses<                                        \
735           std::remove_reference<decltype(CREATE_PASS)>::type>(NAME, Name,      \
736                                                               FPM))            \
737     return true;
738 
739 #define FUNCTION_PASS(NAME, CREATE_PASS)                                       \
740   if (Name == NAME) {                                                          \
741     FPM.addPass(CREATE_PASS);                                                  \
742     return true;                                                               \
743   }
744 
745 #include "PollyPasses.def"
746   return false;
747 }
748 
749 static bool parseScopPass(StringRef Name, ScopPassManager &SPM,
750                           PassInstrumentationCallbacks *PIC) {
751 #define SCOP_ANALYSIS(NAME, CREATE_PASS)                                       \
752   if (llvm::parseAnalysisUtilityPasses<                                        \
753           std::remove_reference<decltype(CREATE_PASS)>::type>(NAME, Name,      \
754                                                               SPM))            \
755     return true;
756 
757 #define SCOP_PASS(NAME, CREATE_PASS)                                           \
758   if (Name == NAME) {                                                          \
759     SPM.addPass(CREATE_PASS);                                                  \
760     return true;                                                               \
761   }
762 
763 #include "PollyPasses.def"
764 
765   return false;
766 }
767 
768 static bool parseScopPipeline(StringRef Name, FunctionPassManager &FPM,
769                               PassInstrumentationCallbacks *PIC,
770                               ArrayRef<PassBuilder::PipelineElement> Pipeline) {
771   if (Name != "scop")
772     return false;
773   if (!Pipeline.empty()) {
774     ScopPassManager SPM;
775     for (const auto &E : Pipeline)
776       if (!parseScopPass(E.Name, SPM, PIC))
777         return false;
778     FPM.addPass(createFunctionToScopPassAdaptor(std::move(SPM)));
779   }
780   return true;
781 }
782 
783 static bool isScopPassName(StringRef Name) {
784 #define SCOP_ANALYSIS(NAME, CREATE_PASS)                                       \
785   if (Name == "require<" NAME ">")                                             \
786     return true;                                                               \
787   if (Name == "invalidate<" NAME ">")                                          \
788     return true;
789 
790 #define SCOP_PASS(NAME, CREATE_PASS)                                           \
791   if (Name == NAME)                                                            \
792     return true;
793 
794 #include "PollyPasses.def"
795 
796   return false;
797 }
798 
799 static bool
800 parseTopLevelPipeline(llvm::ModulePassManager &MPM,
801                       PassInstrumentationCallbacks *PIC,
802                       ArrayRef<PassBuilder::PipelineElement> Pipeline) {
803   std::vector<PassBuilder::PipelineElement> FullPipeline;
804   StringRef FirstName = Pipeline.front().Name;
805 
806   if (!isScopPassName(FirstName))
807     return false;
808 
809   FunctionPassManager FPM;
810   ScopPassManager SPM;
811 
812   for (auto &Element : Pipeline) {
813     auto &Name = Element.Name;
814     auto &InnerPipeline = Element.InnerPipeline;
815     if (!InnerPipeline.empty()) // Scop passes don't have inner pipelines
816       return false;
817     if (!parseScopPass(Name, SPM, PIC))
818       return false;
819   }
820 
821   FPM.addPass(createFunctionToScopPassAdaptor(std::move(SPM)));
822   MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
823 
824   return true;
825 }
826 
827 void registerPollyPasses(PassBuilder &PB) {
828   PassInstrumentationCallbacks *PIC = PB.getPassInstrumentationCallbacks();
829   PB.registerAnalysisRegistrationCallback([PIC](FunctionAnalysisManager &FAM) {
830     registerFunctionAnalyses(FAM, PIC);
831   });
832   PB.registerPipelineParsingCallback(parseFunctionPipeline);
833   PB.registerPipelineParsingCallback(
834       [PIC](StringRef Name, FunctionPassManager &FPM,
835             ArrayRef<PassBuilder::PipelineElement> Pipeline) -> bool {
836         return parseScopPipeline(Name, FPM, PIC, Pipeline);
837       });
838   PB.registerParseTopLevelPipelineCallback(
839       [PIC](llvm::ModulePassManager &MPM,
840             ArrayRef<PassBuilder::PipelineElement> Pipeline) -> bool {
841         return parseTopLevelPipeline(MPM, PIC, Pipeline);
842       });
843 
844   switch (PassPosition) {
845   case POSITION_EARLY:
846     PB.registerPipelineStartEPCallback(buildEarlyPollyPipeline);
847     break;
848   case POSITION_AFTER_LOOPOPT:
849     llvm::report_fatal_error(
850         "Option -polly-position=after-loopopt not supported with NPM", false);
851     break;
852   case POSITION_BEFORE_VECTORIZER:
853     PB.registerVectorizerStartEPCallback(buildLatePollyPipeline);
854     break;
855   }
856 }
857 } // namespace polly
858 
859 llvm::PassPluginLibraryInfo getPollyPluginInfo() {
860   return {LLVM_PLUGIN_API_VERSION, "Polly", LLVM_VERSION_STRING,
861           polly::registerPollyPasses};
862 }
863