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/DependenceInfo.h"
28 #include "polly/ForwardOpTree.h"
29 #include "polly/JSONExporter.h"
30 #include "polly/LinkAllPasses.h"
31 #include "polly/PolyhedralInfo.h"
32 #include "polly/ScopDetection.h"
33 #include "polly/ScopInfo.h"
34 #include "polly/Simplify.h"
35 #include "polly/Support/DumpModulePass.h"
36 #include "llvm/Analysis/CFGPrinter.h"
37 #include "llvm/IR/LegacyPassManager.h"
38 #include "llvm/IR/Verifier.h"
39 #include "llvm/Passes/PassBuilder.h"
40 #include "llvm/Passes/PassPlugin.h"
41 #include "llvm/Support/CommandLine.h"
42 #include "llvm/Support/TargetSelect.h"
43 #include "llvm/Transforms/IPO.h"
44 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
45
46 using namespace llvm;
47 using namespace polly;
48
49 cl::OptionCategory PollyCategory("Polly Options",
50 "Configure the polly loop optimizer");
51
52 static cl::opt<bool>
53 PollyEnabled("polly", cl::desc("Enable the polly optimizer (only at -O3)"),
54 cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
55
56 static cl::opt<bool> PollyDetectOnly(
57 "polly-only-scop-detection",
58 cl::desc("Only run scop detection, but no other optimizations"),
59 cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
60
61 enum PassPositionChoice {
62 POSITION_EARLY,
63 POSITION_AFTER_LOOPOPT,
64 POSITION_BEFORE_VECTORIZER
65 };
66
67 enum OptimizerChoice { OPTIMIZER_NONE, OPTIMIZER_ISL };
68
69 static cl::opt<PassPositionChoice> PassPosition(
70 "polly-position", cl::desc("Where to run polly in the pass pipeline"),
71 cl::values(
72 clEnumValN(POSITION_EARLY, "early", "Before everything"),
73 clEnumValN(POSITION_AFTER_LOOPOPT, "after-loopopt",
74 "After the loop optimizer (but within the inline cycle)"),
75 clEnumValN(POSITION_BEFORE_VECTORIZER, "before-vectorizer",
76 "Right before the vectorizer")),
77 cl::Hidden, cl::init(POSITION_BEFORE_VECTORIZER), cl::ZeroOrMore,
78 cl::cat(PollyCategory));
79
80 static cl::opt<OptimizerChoice>
81 Optimizer("polly-optimizer", cl::desc("Select the scheduling optimizer"),
82 cl::values(clEnumValN(OPTIMIZER_NONE, "none", "No optimizer"),
83 clEnumValN(OPTIMIZER_ISL, "isl",
84 "The isl scheduling optimizer")),
85 cl::Hidden, cl::init(OPTIMIZER_ISL), cl::ZeroOrMore,
86 cl::cat(PollyCategory));
87
88 enum CodeGenChoice { CODEGEN_FULL, CODEGEN_AST, CODEGEN_NONE };
89 static cl::opt<CodeGenChoice> CodeGeneration(
90 "polly-code-generation", cl::desc("How much code-generation to perform"),
91 cl::values(clEnumValN(CODEGEN_FULL, "full", "AST and IR generation"),
92 clEnumValN(CODEGEN_AST, "ast", "Only AST generation"),
93 clEnumValN(CODEGEN_NONE, "none", "No code generation")),
94 cl::Hidden, cl::init(CODEGEN_FULL), cl::ZeroOrMore, cl::cat(PollyCategory));
95
96 enum TargetChoice { TARGET_CPU, TARGET_GPU, TARGET_HYBRID };
97 static cl::opt<TargetChoice>
98 Target("polly-target", cl::desc("The hardware to target"),
99 cl::values(clEnumValN(TARGET_CPU, "cpu", "generate CPU code")
100 #ifdef GPU_CODEGEN
101 ,
102 clEnumValN(TARGET_GPU, "gpu", "generate GPU code"),
103 clEnumValN(TARGET_HYBRID, "hybrid",
104 "generate GPU code (preferably) or CPU code")
105 #endif
106 ),
107 cl::init(TARGET_CPU), cl::ZeroOrMore, cl::cat(PollyCategory));
108
109 #ifdef GPU_CODEGEN
110 static cl::opt<GPURuntime> GPURuntimeChoice(
111 "polly-gpu-runtime", cl::desc("The GPU Runtime API to target"),
112 cl::values(clEnumValN(GPURuntime::CUDA, "libcudart",
113 "use the CUDA Runtime API"),
114 clEnumValN(GPURuntime::OpenCL, "libopencl",
115 "use the OpenCL Runtime API")),
116 cl::init(GPURuntime::CUDA), cl::ZeroOrMore, cl::cat(PollyCategory));
117
118 static cl::opt<GPUArch>
119 GPUArchChoice("polly-gpu-arch", cl::desc("The GPU Architecture to target"),
120 cl::values(clEnumValN(GPUArch::NVPTX64, "nvptx64",
121 "target NVIDIA 64-bit architecture"),
122 clEnumValN(GPUArch::SPIR32, "spir32",
123 "target SPIR 32-bit architecture"),
124 clEnumValN(GPUArch::SPIR64, "spir64",
125 "target SPIR 64-bit architecture")),
126 cl::init(GPUArch::NVPTX64), cl::ZeroOrMore,
127 cl::cat(PollyCategory));
128 #endif
129
130 VectorizerChoice polly::PollyVectorizerChoice;
131 static cl::opt<polly::VectorizerChoice, true> Vectorizer(
132 "polly-vectorizer", cl::desc("Select the vectorization strategy"),
133 cl::values(
134 clEnumValN(polly::VECTORIZER_NONE, "none", "No Vectorization"),
135 clEnumValN(polly::VECTORIZER_POLLY, "polly",
136 "Polly internal vectorizer"),
137 clEnumValN(
138 polly::VECTORIZER_STRIPMINE, "stripmine",
139 "Strip-mine outer loops for the loop-vectorizer to trigger")),
140 cl::location(PollyVectorizerChoice), cl::init(polly::VECTORIZER_NONE),
141 cl::ZeroOrMore, cl::cat(PollyCategory));
142
143 static cl::opt<bool> ImportJScop(
144 "polly-import",
145 cl::desc("Import the polyhedral description of the detected Scops"),
146 cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
147
148 static cl::opt<bool> FullyIndexedStaticExpansion(
149 "polly-enable-mse",
150 cl::desc("Fully expand the memory accesses of the detected Scops"),
151 cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
152
153 static cl::opt<bool> ExportJScop(
154 "polly-export",
155 cl::desc("Export the polyhedral description of the detected Scops"),
156 cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
157
158 static cl::opt<bool> DeadCodeElim("polly-run-dce",
159 cl::desc("Run the dead code elimination"),
160 cl::Hidden, cl::init(false), cl::ZeroOrMore,
161 cl::cat(PollyCategory));
162
163 static cl::opt<bool> PollyViewer(
164 "polly-show",
165 cl::desc("Highlight the code regions that will be optimized in a "
166 "(CFG BBs and LLVM-IR instructions)"),
167 cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
168
169 static cl::opt<bool> PollyOnlyViewer(
170 "polly-show-only",
171 cl::desc("Highlight the code regions that will be optimized in "
172 "a (CFG only BBs)"),
173 cl::init(false), cl::cat(PollyCategory));
174
175 static cl::opt<bool>
176 PollyPrinter("polly-dot", cl::desc("Enable the Polly DOT printer in -O3"),
177 cl::Hidden, cl::value_desc("Run the Polly DOT printer at -O3"),
178 cl::init(false), cl::cat(PollyCategory));
179
180 static cl::opt<bool> PollyOnlyPrinter(
181 "polly-dot-only",
182 cl::desc("Enable the Polly DOT printer in -O3 (no BB content)"), cl::Hidden,
183 cl::value_desc("Run the Polly DOT printer at -O3 (no BB content"),
184 cl::init(false), cl::cat(PollyCategory));
185
186 static cl::opt<bool>
187 CFGPrinter("polly-view-cfg",
188 cl::desc("Show the Polly CFG right after code generation"),
189 cl::Hidden, cl::init(false), cl::cat(PollyCategory));
190
191 static cl::opt<bool>
192 EnablePolyhedralInfo("polly-enable-polyhedralinfo",
193 cl::desc("Enable polyhedral interface of Polly"),
194 cl::Hidden, cl::init(false), cl::cat(PollyCategory));
195
196 static cl::opt<bool>
197 EnableForwardOpTree("polly-enable-optree",
198 cl::desc("Enable operand tree forwarding"), cl::Hidden,
199 cl::init(true), cl::cat(PollyCategory));
200
201 static cl::opt<bool>
202 DumpBefore("polly-dump-before",
203 cl::desc("Dump module before Polly transformations into a file "
204 "suffixed with \"-before\""),
205 cl::init(false), cl::cat(PollyCategory));
206
207 static cl::list<std::string> DumpBeforeFile(
208 "polly-dump-before-file",
209 cl::desc("Dump module before Polly transformations to the given file"),
210 cl::cat(PollyCategory));
211
212 static cl::opt<bool>
213 DumpAfter("polly-dump-after",
214 cl::desc("Dump module after Polly transformations into a file "
215 "suffixed with \"-after\""),
216 cl::init(false), cl::cat(PollyCategory));
217
218 static cl::list<std::string> DumpAfterFile(
219 "polly-dump-after-file",
220 cl::desc("Dump module after Polly transformations to the given file"),
221 cl::ZeroOrMore, cl::cat(PollyCategory));
222
223 static cl::opt<bool>
224 EnableDeLICM("polly-enable-delicm",
225 cl::desc("Eliminate scalar loop carried dependences"),
226 cl::Hidden, cl::init(true), cl::cat(PollyCategory));
227
228 static cl::opt<bool>
229 EnableSimplify("polly-enable-simplify",
230 cl::desc("Simplify SCoP after optimizations"),
231 cl::init(true), cl::cat(PollyCategory));
232
233 static cl::opt<bool> EnablePruneUnprofitable(
234 "polly-enable-prune-unprofitable",
235 cl::desc("Bail out on unprofitable SCoPs before rescheduling"), cl::Hidden,
236 cl::init(true), cl::cat(PollyCategory));
237
238 namespace {
239
240 /// Initialize Polly passes when library is loaded.
241 ///
242 /// We use the constructor of a statically declared object to initialize the
243 /// different Polly passes right after the Polly library is loaded. This ensures
244 /// that the Polly passes are available e.g. in the 'opt' tool.
245 class StaticInitializer {
246 public:
StaticInitializer()247 StaticInitializer() {
248 llvm::PassRegistry &Registry = *llvm::PassRegistry::getPassRegistry();
249 polly::initializePollyPasses(Registry);
250 }
251 };
252 static StaticInitializer InitializeEverything;
253 } // end of anonymous namespace.
254
255 namespace polly {
initializePollyPasses(PassRegistry & Registry)256 void initializePollyPasses(PassRegistry &Registry) {
257 initializeCodeGenerationPass(Registry);
258
259 #ifdef GPU_CODEGEN
260 initializePPCGCodeGenerationPass(Registry);
261 initializeManagedMemoryRewritePassPass(Registry);
262 LLVMInitializeNVPTXTarget();
263 LLVMInitializeNVPTXTargetInfo();
264 LLVMInitializeNVPTXTargetMC();
265 LLVMInitializeNVPTXAsmPrinter();
266 #endif
267 initializeCodePreparationPass(Registry);
268 initializeDeadCodeElimPass(Registry);
269 initializeDependenceInfoPass(Registry);
270 initializeDependenceInfoWrapperPassPass(Registry);
271 initializeJSONExporterPass(Registry);
272 initializeJSONImporterPass(Registry);
273 initializeMaximalStaticExpanderPass(Registry);
274 initializeIslAstInfoWrapperPassPass(Registry);
275 initializeIslScheduleOptimizerPass(Registry);
276 initializePollyCanonicalizePass(Registry);
277 initializePolyhedralInfoPass(Registry);
278 initializeScopDetectionWrapperPassPass(Registry);
279 initializeScopInlinerPass(Registry);
280 initializeScopInfoRegionPassPass(Registry);
281 initializeScopInfoWrapperPassPass(Registry);
282 initializeRewriteByrefParamsPass(Registry);
283 initializeCodegenCleanupPass(Registry);
284 initializeFlattenSchedulePass(Registry);
285 initializeForwardOpTreePass(Registry);
286 initializeDeLICMPass(Registry);
287 initializeSimplifyLegacyPassPass(Registry);
288 initializeDumpModulePass(Registry);
289 initializePruneUnprofitablePass(Registry);
290 }
291
292 /// Register Polly passes such that they form a polyhedral optimizer.
293 ///
294 /// The individual Polly passes are registered in the pass manager such that
295 /// they form a full polyhedral optimizer. The flow of the optimizer starts with
296 /// a set of preparing transformations that canonicalize the LLVM-IR such that
297 /// the LLVM-IR is easier for us to understand and to optimizes. On the
298 /// canonicalized LLVM-IR we first run the ScopDetection pass, which detects
299 /// static control flow regions. Those regions are then translated by the
300 /// ScopInfo pass into a polyhedral representation. As a next step, a scheduling
301 /// optimizer is run on the polyhedral representation and finally the optimized
302 /// polyhedral representation is code generated back to LLVM-IR.
303 ///
304 /// Besides this core functionality, we optionally schedule passes that provide
305 /// a graphical view of the scops (Polly[Only]Viewer, Polly[Only]Printer), that
306 /// allow the export/import of the polyhedral representation
307 /// (JSCON[Exporter|Importer]) or that show the cfg after code generation.
308 ///
309 /// For certain parts of the Polly optimizer, several alternatives are provided:
310 ///
311 /// As scheduling optimizer we support the isl scheduling optimizer
312 /// (http://freecode.com/projects/isl).
313 /// It is also possible to run Polly with no optimizer. This mode is mainly
314 /// provided to analyze the run and compile time changes caused by the
315 /// scheduling optimizer.
316 ///
317 /// Polly supports the isl internal code generator.
registerPollyPasses(llvm::legacy::PassManagerBase & PM)318 void registerPollyPasses(llvm::legacy::PassManagerBase &PM) {
319 if (DumpBefore)
320 PM.add(polly::createDumpModulePass("-before", true));
321 for (auto &Filename : DumpBeforeFile)
322 PM.add(polly::createDumpModulePass(Filename, false));
323
324 PM.add(polly::createScopDetectionWrapperPassPass());
325
326 if (PollyDetectOnly)
327 return;
328
329 if (PollyViewer)
330 PM.add(polly::createDOTViewerPass());
331 if (PollyOnlyViewer)
332 PM.add(polly::createDOTOnlyViewerPass());
333 if (PollyPrinter)
334 PM.add(polly::createDOTPrinterPass());
335 if (PollyOnlyPrinter)
336 PM.add(polly::createDOTOnlyPrinterPass());
337
338 PM.add(polly::createScopInfoRegionPassPass());
339 if (EnablePolyhedralInfo)
340 PM.add(polly::createPolyhedralInfoPass());
341
342 if (EnableSimplify)
343 PM.add(polly::createSimplifyPass(0));
344 if (EnableForwardOpTree)
345 PM.add(polly::createForwardOpTreePass());
346 if (EnableDeLICM)
347 PM.add(polly::createDeLICMPass());
348 if (EnableSimplify)
349 PM.add(polly::createSimplifyPass(1));
350
351 if (ImportJScop)
352 PM.add(polly::createJSONImporterPass());
353
354 if (DeadCodeElim)
355 PM.add(polly::createDeadCodeElimPass());
356
357 if (FullyIndexedStaticExpansion)
358 PM.add(polly::createMaximalStaticExpansionPass());
359
360 if (EnablePruneUnprofitable)
361 PM.add(polly::createPruneUnprofitablePass());
362
363 #ifdef GPU_CODEGEN
364 if (Target == TARGET_HYBRID)
365 PM.add(
366 polly::createPPCGCodeGenerationPass(GPUArchChoice, GPURuntimeChoice));
367 #endif
368 if (Target == TARGET_CPU || Target == TARGET_HYBRID)
369 switch (Optimizer) {
370 case OPTIMIZER_NONE:
371 break; /* Do nothing */
372
373 case OPTIMIZER_ISL:
374 PM.add(polly::createIslScheduleOptimizerPass());
375 break;
376 }
377
378 if (ExportJScop)
379 PM.add(polly::createJSONExporterPass());
380
381 if (Target == TARGET_CPU || Target == TARGET_HYBRID)
382 switch (CodeGeneration) {
383 case CODEGEN_AST:
384 PM.add(polly::createIslAstInfoWrapperPassPass());
385 break;
386 case CODEGEN_FULL:
387 PM.add(polly::createCodeGenerationPass());
388 break;
389 case CODEGEN_NONE:
390 break;
391 }
392 #ifdef GPU_CODEGEN
393 else {
394 PM.add(
395 polly::createPPCGCodeGenerationPass(GPUArchChoice, GPURuntimeChoice));
396 PM.add(polly::createManagedMemoryRewritePassPass());
397 }
398 #endif
399
400 #ifdef GPU_CODEGEN
401 if (Target == TARGET_HYBRID)
402 PM.add(polly::createManagedMemoryRewritePassPass(GPUArchChoice,
403 GPURuntimeChoice));
404 #endif
405
406 // FIXME: This dummy ModulePass keeps some programs from miscompiling,
407 // probably some not correctly preserved analyses. It acts as a barrier to
408 // force all analysis results to be recomputed.
409 PM.add(createBarrierNoopPass());
410
411 if (DumpAfter)
412 PM.add(polly::createDumpModulePass("-after", true));
413 for (auto &Filename : DumpAfterFile)
414 PM.add(polly::createDumpModulePass(Filename, false));
415
416 if (CFGPrinter)
417 PM.add(llvm::createCFGPrinterLegacyPassPass());
418 }
419
shouldEnablePolly()420 static bool shouldEnablePolly() {
421 if (PollyOnlyPrinter || PollyPrinter || PollyOnlyViewer || PollyViewer)
422 PollyTrackFailures = true;
423
424 if (PollyOnlyPrinter || PollyPrinter || PollyOnlyViewer || PollyViewer ||
425 ExportJScop || ImportJScop)
426 PollyEnabled = true;
427
428 return PollyEnabled;
429 }
430
431 static void
registerPollyEarlyAsPossiblePasses(const llvm::PassManagerBuilder & Builder,llvm::legacy::PassManagerBase & PM)432 registerPollyEarlyAsPossiblePasses(const llvm::PassManagerBuilder &Builder,
433 llvm::legacy::PassManagerBase &PM) {
434 if (!polly::shouldEnablePolly())
435 return;
436
437 if (PassPosition != POSITION_EARLY)
438 return;
439
440 registerCanonicalicationPasses(PM);
441 polly::registerPollyPasses(PM);
442 }
443
444 static void
registerPollyLoopOptimizerEndPasses(const llvm::PassManagerBuilder & Builder,llvm::legacy::PassManagerBase & PM)445 registerPollyLoopOptimizerEndPasses(const llvm::PassManagerBuilder &Builder,
446 llvm::legacy::PassManagerBase &PM) {
447 if (!polly::shouldEnablePolly())
448 return;
449
450 if (PassPosition != POSITION_AFTER_LOOPOPT)
451 return;
452
453 PM.add(polly::createCodePreparationPass());
454 polly::registerPollyPasses(PM);
455 PM.add(createCodegenCleanupPass());
456 }
457
458 static void
registerPollyScalarOptimizerLatePasses(const llvm::PassManagerBuilder & Builder,llvm::legacy::PassManagerBase & PM)459 registerPollyScalarOptimizerLatePasses(const llvm::PassManagerBuilder &Builder,
460 llvm::legacy::PassManagerBase &PM) {
461 if (!polly::shouldEnablePolly())
462 return;
463
464 if (PassPosition != POSITION_BEFORE_VECTORIZER)
465 return;
466
467 PM.add(polly::createCodePreparationPass());
468 polly::registerPollyPasses(PM);
469 PM.add(createCodegenCleanupPass());
470 }
471
buildDefaultPollyPipeline(FunctionPassManager & PM,PassBuilder::OptimizationLevel Level)472 static void buildDefaultPollyPipeline(FunctionPassManager &PM,
473 PassBuilder::OptimizationLevel Level) {
474 if (!polly::shouldEnablePolly())
475 return;
476 PassBuilder PB;
477 ScopPassManager SPM;
478
479 // TODO add utility passes for the various command line options, once they're
480 // ported
481 assert(!DumpBefore && "This option is not implemented");
482 assert(DumpBeforeFile.empty() && "This option is not implemented");
483
484 if (PollyDetectOnly)
485 return;
486
487 assert(!PollyViewer && "This option is not implemented");
488 assert(!PollyOnlyViewer && "This option is not implemented");
489 assert(!PollyPrinter && "This option is not implemented");
490 assert(!PollyOnlyPrinter && "This option is not implemented");
491 assert(!EnablePolyhedralInfo && "This option is not implemented");
492 assert(!EnableDeLICM && "This option is not implemented");
493 assert(!EnableSimplify && "This option is not implemented");
494 if (ImportJScop)
495 SPM.addPass(JSONImportPass());
496 assert(!DeadCodeElim && "This option is not implemented");
497 assert(!EnablePruneUnprofitable && "This option is not implemented");
498 if (Target == TARGET_CPU || Target == TARGET_HYBRID)
499 switch (Optimizer) {
500 case OPTIMIZER_NONE:
501 break; /* Do nothing */
502 case OPTIMIZER_ISL:
503 llvm_unreachable("ISL optimizer is not implemented");
504 break;
505 }
506
507 assert(!ExportJScop && "This option is not implemented");
508
509 if (Target == TARGET_CPU || Target == TARGET_HYBRID) {
510 switch (CodeGeneration) {
511 case CODEGEN_FULL:
512 SPM.addPass(polly::CodeGenerationPass());
513 break;
514 case CODEGEN_AST:
515 default: // Does it actually make sense to distinguish IslAst codegen?
516 break;
517 }
518 }
519 #ifdef GPU_CODEGEN
520 else
521 llvm_unreachable("Hybrid Target with GPU support is not implemented");
522 #endif
523
524 PM.addPass(CodePreparationPass());
525 PM.addPass(createFunctionToScopPassAdaptor(std::move(SPM)));
526 PM.addPass(PB.buildFunctionSimplificationPipeline(
527 Level, PassBuilder::ThinLTOPhase::None)); // Cleanup
528
529 assert(!DumpAfter && "This option is not implemented");
530 assert(DumpAfterFile.empty() && "This option is not implemented");
531
532 if (CFGPrinter)
533 PM.addPass(llvm::CFGPrinterPass());
534 }
535
536 /// Register Polly to be available as an optimizer
537 ///
538 ///
539 /// We can currently run Polly at three different points int the pass manager.
540 /// a) very early, b) after the canonicalizing loop transformations and c) right
541 /// before the vectorizer.
542 ///
543 /// The default is currently a), to register Polly such that it runs as early as
544 /// possible. This has several implications:
545 ///
546 /// 1) We need to schedule more canonicalization passes
547 ///
548 /// As nothing is run before Polly, it is necessary to run a set of preparing
549 /// transformations before Polly to canonicalize the LLVM-IR and to allow
550 /// Polly to detect and understand the code.
551 ///
552 /// 2) LICM and LoopIdiom pass have not yet been run
553 ///
554 /// Loop invariant code motion as well as the loop idiom recognition pass make
555 /// it more difficult for Polly to transform code. LICM may introduce
556 /// additional data dependences that are hard to eliminate and the loop idiom
557 /// recognition pass may introduce calls to memset that we currently do not
558 /// understand. By running Polly early enough (meaning before these passes) we
559 /// avoid difficulties that may be introduced by these passes.
560 ///
561 /// 3) We get the full -O3 optimization sequence after Polly
562 ///
563 /// The LLVM-IR that is generated by Polly has been optimized on a high level,
564 /// but it may be rather inefficient on the lower/scalar level. By scheduling
565 /// Polly before all other passes, we have the full sequence of -O3
566 /// optimizations behind us, such that inefficiencies on the low level can
567 /// be optimized away.
568 ///
569 /// We are currently evaluating the benefit or running Polly at position b) or
570 /// c). b) is likely too early as it interacts with the inliner. c) is nice
571 /// as everything is fully inlined and canonicalized, but we need to be able
572 /// to handle LICMed code to make it useful.
573 static llvm::RegisterStandardPasses RegisterPollyOptimizerEarly(
574 llvm::PassManagerBuilder::EP_ModuleOptimizerEarly,
575 registerPollyEarlyAsPossiblePasses);
576
577 static llvm::RegisterStandardPasses
578 RegisterPollyOptimizerLoopEnd(llvm::PassManagerBuilder::EP_LoopOptimizerEnd,
579 registerPollyLoopOptimizerEndPasses);
580
581 static llvm::RegisterStandardPasses RegisterPollyOptimizerScalarLate(
582 llvm::PassManagerBuilder::EP_VectorizerStart,
583 registerPollyScalarOptimizerLatePasses);
584
585 static OwningScopAnalysisManagerFunctionProxy
createScopAnalyses(FunctionAnalysisManager & FAM)586 createScopAnalyses(FunctionAnalysisManager &FAM) {
587 OwningScopAnalysisManagerFunctionProxy Proxy;
588 #define SCOP_ANALYSIS(NAME, CREATE_PASS) \
589 Proxy.getManager().registerPass([] { return CREATE_PASS; });
590
591 #include "PollyPasses.def"
592
593 Proxy.getManager().registerPass(
594 [&FAM] { return FunctionAnalysisManagerScopProxy(FAM); });
595 return Proxy;
596 }
597
registerFunctionAnalyses(FunctionAnalysisManager & FAM)598 static void registerFunctionAnalyses(FunctionAnalysisManager &FAM) {
599 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS) \
600 FAM.registerPass([] { return CREATE_PASS; });
601
602 #include "PollyPasses.def"
603
604 FAM.registerPass([&FAM] { return createScopAnalyses(FAM); });
605 }
606
607 static bool
parseFunctionPipeline(StringRef Name,FunctionPassManager & FPM,ArrayRef<PassBuilder::PipelineElement> Pipeline)608 parseFunctionPipeline(StringRef Name, FunctionPassManager &FPM,
609 ArrayRef<PassBuilder::PipelineElement> Pipeline) {
610 if (parseAnalysisUtilityPasses<OwningScopAnalysisManagerFunctionProxy>(
611 "polly-scop-analyses", Name, FPM))
612 return true;
613
614 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS) \
615 if (parseAnalysisUtilityPasses< \
616 std::remove_reference<decltype(CREATE_PASS)>::type>(NAME, Name, \
617 FPM)) \
618 return true;
619
620 #define FUNCTION_PASS(NAME, CREATE_PASS) \
621 if (Name == NAME) { \
622 FPM.addPass(CREATE_PASS); \
623 return true; \
624 }
625
626 #include "PollyPasses.def"
627 return false;
628 }
629
parseScopPass(StringRef Name,ScopPassManager & SPM)630 static bool parseScopPass(StringRef Name, ScopPassManager &SPM) {
631 #define SCOP_ANALYSIS(NAME, CREATE_PASS) \
632 if (parseAnalysisUtilityPasses< \
633 std::remove_reference<decltype(CREATE_PASS)>::type>(NAME, Name, \
634 SPM)) \
635 return true;
636
637 #define SCOP_PASS(NAME, CREATE_PASS) \
638 if (Name == NAME) { \
639 SPM.addPass(CREATE_PASS); \
640 return true; \
641 }
642
643 #include "PollyPasses.def"
644
645 return false;
646 }
647
parseScopPipeline(StringRef Name,FunctionPassManager & FPM,ArrayRef<PassBuilder::PipelineElement> Pipeline)648 static bool parseScopPipeline(StringRef Name, FunctionPassManager &FPM,
649 ArrayRef<PassBuilder::PipelineElement> Pipeline) {
650 if (Name != "scop")
651 return false;
652 if (!Pipeline.empty()) {
653 ScopPassManager SPM;
654 for (const auto &E : Pipeline)
655 if (!parseScopPass(E.Name, SPM))
656 return false;
657 FPM.addPass(createFunctionToScopPassAdaptor(std::move(SPM)));
658 }
659 return true;
660 }
661
isScopPassName(StringRef Name)662 static bool isScopPassName(StringRef Name) {
663 #define SCOP_ANALYSIS(NAME, CREATE_PASS) \
664 if (Name == "require<" NAME ">") \
665 return true; \
666 if (Name == "invalidate<" NAME ">") \
667 return true;
668
669 #define SCOP_PASS(NAME, CREATE_PASS) \
670 if (Name == NAME) \
671 return true;
672
673 #include "PollyPasses.def"
674
675 return false;
676 }
677
678 static bool
parseTopLevelPipeline(ModulePassManager & MPM,ArrayRef<PassBuilder::PipelineElement> Pipeline,bool DebugLogging)679 parseTopLevelPipeline(ModulePassManager &MPM,
680 ArrayRef<PassBuilder::PipelineElement> Pipeline,
681 bool DebugLogging) {
682 std::vector<PassBuilder::PipelineElement> FullPipeline;
683 StringRef FirstName = Pipeline.front().Name;
684
685 if (!isScopPassName(FirstName))
686 return false;
687
688 FunctionPassManager FPM(DebugLogging);
689 ScopPassManager SPM(DebugLogging);
690
691 for (auto &Element : Pipeline) {
692 auto &Name = Element.Name;
693 auto &InnerPipeline = Element.InnerPipeline;
694 if (!InnerPipeline.empty()) // Scop passes don't have inner pipelines
695 return false;
696 if (!parseScopPass(Name, SPM))
697 return false;
698 }
699
700 FPM.addPass(createFunctionToScopPassAdaptor(std::move(SPM)));
701 MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
702
703 return true;
704 }
705
registerPollyPasses(PassBuilder & PB)706 void registerPollyPasses(PassBuilder &PB) {
707 PB.registerAnalysisRegistrationCallback(registerFunctionAnalyses);
708 PB.registerPipelineParsingCallback(parseFunctionPipeline);
709 PB.registerPipelineParsingCallback(parseScopPipeline);
710 PB.registerParseTopLevelPipelineCallback(parseTopLevelPipeline);
711
712 if (PassPosition == POSITION_BEFORE_VECTORIZER)
713 PB.registerVectorizerStartEPCallback(buildDefaultPollyPipeline);
714 // FIXME else Error?
715 }
716 } // namespace polly
717
getPollyPluginInfo()718 llvm::PassPluginLibraryInfo getPollyPluginInfo() {
719 return {LLVM_PLUGIN_API_VERSION, "Polly", LLVM_VERSION_STRING,
720 polly::registerPollyPasses};
721 }
722