1 //===------ RegisterPasses.cpp - Add the Polly Passes to default passes  --===//
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 //
10 // This file composes the individual LLVM-IR passes provided by Polly to a
11 // functional polyhedral optimizer. The polyhedral optimizer is automatically
12 // made available to LLVM based compilers by loading the Polly shared library
13 // into such a compiler.
14 //
15 // The Polly optimizer is made available by executing a static constructor that
16 // registers the individual Polly passes in the LLVM pass manager builder. The
17 // passes are registered such that the default behaviour of the compiler is not
18 // changed, but that the flag '-polly' provided at optimization level '-O3'
19 // enables additional polyhedral optimizations.
20 //===----------------------------------------------------------------------===//
21 
22 #include "polly/RegisterPasses.h"
23 #include "polly/Canonicalization.h"
24 #include "polly/CodeGen/CodeGeneration.h"
25 #include "polly/CodeGen/CodegenCleanup.h"
26 #include "polly/CodeGen/PPCGCodeGeneration.h"
27 #include "polly/DeLICM.h"
28 #include "polly/DependenceInfo.h"
29 #include "polly/FlattenSchedule.h"
30 #include "polly/ForwardOpTree.h"
31 #include "polly/LinkAllPasses.h"
32 #include "polly/Options.h"
33 #include "polly/PolyhedralInfo.h"
34 #include "polly/ScopDetection.h"
35 #include "polly/ScopInfo.h"
36 #include "polly/Simplify.h"
37 #include "polly/Support/DumpModulePass.h"
38 #include "llvm/Analysis/CFGPrinter.h"
39 #include "llvm/IR/LegacyPassManager.h"
40 #include "llvm/Support/TargetSelect.h"
41 #include "llvm/Transforms/IPO.h"
42 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
43 #include "llvm/Transforms/Scalar.h"
44 #include "llvm/Transforms/Vectorize.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_EARLY), 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> ExportJScop(
149     "polly-export",
150     cl::desc("Export the polyhedral description of the detected Scops"),
151     cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
152 
153 static cl::opt<bool> DeadCodeElim("polly-run-dce",
154                                   cl::desc("Run the dead code elimination"),
155                                   cl::Hidden, cl::init(false), cl::ZeroOrMore,
156                                   cl::cat(PollyCategory));
157 
158 static cl::opt<bool> PollyViewer(
159     "polly-show",
160     cl::desc("Highlight the code regions that will be optimized in a "
161              "(CFG BBs and LLVM-IR instructions)"),
162     cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
163 
164 static cl::opt<bool> PollyOnlyViewer(
165     "polly-show-only",
166     cl::desc("Highlight the code regions that will be optimized in "
167              "a (CFG only BBs)"),
168     cl::init(false), cl::cat(PollyCategory));
169 
170 static cl::opt<bool>
171     PollyPrinter("polly-dot", cl::desc("Enable the Polly DOT printer in -O3"),
172                  cl::Hidden, cl::value_desc("Run the Polly DOT printer at -O3"),
173                  cl::init(false), cl::cat(PollyCategory));
174 
175 static cl::opt<bool> PollyOnlyPrinter(
176     "polly-dot-only",
177     cl::desc("Enable the Polly DOT printer in -O3 (no BB content)"), cl::Hidden,
178     cl::value_desc("Run the Polly DOT printer at -O3 (no BB content"),
179     cl::init(false), cl::cat(PollyCategory));
180 
181 static cl::opt<bool>
182     CFGPrinter("polly-view-cfg",
183                cl::desc("Show the Polly CFG right after code generation"),
184                cl::Hidden, cl::init(false), cl::cat(PollyCategory));
185 
186 static cl::opt<bool>
187     EnablePolyhedralInfo("polly-enable-polyhedralinfo",
188                          cl::desc("Enable polyhedral interface of Polly"),
189                          cl::Hidden, cl::init(false), cl::cat(PollyCategory));
190 
191 static cl::opt<bool>
192     EnableForwardOpTree("polly-enable-optree",
193                         cl::desc("Enable operand tree forwarding"), cl::Hidden,
194                         cl::init(false), cl::cat(PollyCategory));
195 
196 static cl::opt<bool>
197     DumpBefore("polly-dump-before",
198                cl::desc("Dump module before Polly transformations into a file "
199                         "suffixed with \"-before\""),
200                cl::init(false), cl::cat(PollyCategory));
201 
202 static cl::list<std::string> DumpBeforeFile(
203     "polly-dump-before-file",
204     cl::desc("Dump module before Polly transformations to the given file"),
205     cl::cat(PollyCategory));
206 
207 static cl::opt<bool>
208     DumpAfter("polly-dump-after",
209               cl::desc("Dump module after Polly transformations into a file "
210                        "suffixed with \"-after\""),
211               cl::init(false), cl::cat(PollyCategory));
212 
213 static cl::list<std::string> DumpAfterFile(
214     "polly-dump-after-file",
215     cl::desc("Dump module after Polly transformations to the given file"),
216     cl::ZeroOrMore, cl::cat(PollyCategory));
217 
218 static cl::opt<bool>
219     EnableDeLICM("polly-enable-delicm",
220                  cl::desc("Eliminate scalar loop carried dependences"),
221                  cl::Hidden, cl::init(false), cl::cat(PollyCategory));
222 
223 static cl::opt<bool>
224     EnableSimplify("polly-enable-simplify",
225                    cl::desc("Simplify SCoP after optimizations"),
226                    cl::init(false), cl::cat(PollyCategory));
227 
228 static cl::opt<bool> EnablePruneUnprofitable(
229     "polly-enable-prune-unprofitable",
230     cl::desc("Bail out on unprofitable SCoPs before rescheduling"), cl::Hidden,
231     cl::init(true), cl::cat(PollyCategory));
232 
233 namespace polly {
234 void initializePollyPasses(PassRegistry &Registry) {
235   initializeCodeGenerationPass(Registry);
236 
237 #ifdef GPU_CODEGEN
238   initializePPCGCodeGenerationPass(Registry);
239   LLVMInitializeNVPTXTarget();
240   LLVMInitializeNVPTXTargetInfo();
241   LLVMInitializeNVPTXTargetMC();
242   LLVMInitializeNVPTXAsmPrinter();
243 #endif
244   initializeCodePreparationPass(Registry);
245   initializeDeadCodeElimPass(Registry);
246   initializeDependenceInfoPass(Registry);
247   initializeDependenceInfoWrapperPassPass(Registry);
248   initializeJSONExporterPass(Registry);
249   initializeJSONImporterPass(Registry);
250   initializeIslAstInfoWrapperPassPass(Registry);
251   initializeIslScheduleOptimizerPass(Registry);
252   initializePollyCanonicalizePass(Registry);
253   initializePolyhedralInfoPass(Registry);
254   initializeScopDetectionWrapperPassPass(Registry);
255   initializeScopInfoRegionPassPass(Registry);
256   initializeScopInfoWrapperPassPass(Registry);
257   initializeCodegenCleanupPass(Registry);
258   initializeFlattenSchedulePass(Registry);
259   initializeForwardOpTreePass(Registry);
260   initializeDeLICMPass(Registry);
261   initializeSimplifyPass(Registry);
262   initializeDumpModulePass(Registry);
263   initializePruneUnprofitablePass(Registry);
264 }
265 
266 /// Register Polly passes such that they form a polyhedral optimizer.
267 ///
268 /// The individual Polly passes are registered in the pass manager such that
269 /// they form a full polyhedral optimizer. The flow of the optimizer starts with
270 /// a set of preparing transformations that canonicalize the LLVM-IR such that
271 /// the LLVM-IR is easier for us to understand and to optimizes. On the
272 /// canonicalized LLVM-IR we first run the ScopDetection pass, which detects
273 /// static control flow regions. Those regions are then translated by the
274 /// ScopInfo pass into a polyhedral representation. As a next step, a scheduling
275 /// optimizer is run on the polyhedral representation and finally the optimized
276 /// polyhedral representation is code generated back to LLVM-IR.
277 ///
278 /// Besides this core functionality, we optionally schedule passes that provide
279 /// a graphical view of the scops (Polly[Only]Viewer, Polly[Only]Printer), that
280 /// allow the export/import of the polyhedral representation
281 /// (JSCON[Exporter|Importer]) or that show the cfg after code generation.
282 ///
283 /// For certain parts of the Polly optimizer, several alternatives are provided:
284 ///
285 /// As scheduling optimizer we support the isl scheduling optimizer
286 /// (http://freecode.com/projects/isl).
287 /// It is also possible to run Polly with no optimizer. This mode is mainly
288 /// provided to analyze the run and compile time changes caused by the
289 /// scheduling optimizer.
290 ///
291 /// Polly supports the isl internal code generator.
292 void registerPollyPasses(llvm::legacy::PassManagerBase &PM) {
293   if (DumpBefore)
294     PM.add(polly::createDumpModulePass("-before", true));
295   for (auto &Filename : DumpBeforeFile)
296     PM.add(polly::createDumpModulePass(Filename, false));
297 
298   PM.add(polly::createScopDetectionWrapperPassPass());
299 
300   if (PollyDetectOnly)
301     return;
302 
303   if (PollyViewer)
304     PM.add(polly::createDOTViewerPass());
305   if (PollyOnlyViewer)
306     PM.add(polly::createDOTOnlyViewerPass());
307   if (PollyPrinter)
308     PM.add(polly::createDOTPrinterPass());
309   if (PollyOnlyPrinter)
310     PM.add(polly::createDOTOnlyPrinterPass());
311 
312   PM.add(polly::createScopInfoRegionPassPass());
313   if (EnablePolyhedralInfo)
314     PM.add(polly::createPolyhedralInfoPass());
315 
316   if (EnableForwardOpTree)
317     PM.add(polly::createForwardOpTreePass());
318   if (EnableDeLICM)
319     PM.add(polly::createDeLICMPass());
320   if (EnableSimplify)
321     PM.add(polly::createSimplifyPass());
322 
323   if (ImportJScop)
324     PM.add(polly::createJSONImporterPass());
325 
326   if (DeadCodeElim)
327     PM.add(polly::createDeadCodeElimPass());
328 
329   if (EnablePruneUnprofitable)
330     PM.add(polly::createPruneUnprofitablePass());
331 
332 #ifdef GPU_CODEGEN
333   if (Target == TARGET_HYBRID)
334     PM.add(
335         polly::createPPCGCodeGenerationPass(GPUArchChoice, GPURuntimeChoice));
336 #endif
337   if (Target == TARGET_CPU || Target == TARGET_HYBRID)
338     switch (Optimizer) {
339     case OPTIMIZER_NONE:
340       break; /* Do nothing */
341 
342     case OPTIMIZER_ISL:
343       PM.add(polly::createIslScheduleOptimizerPass());
344       break;
345     }
346 
347   if (ExportJScop)
348     PM.add(polly::createJSONExporterPass());
349 
350   if (Target == TARGET_CPU || Target == TARGET_HYBRID)
351     switch (CodeGeneration) {
352     case CODEGEN_AST:
353       PM.add(polly::createIslAstInfoWrapperPassPass());
354       break;
355     case CODEGEN_FULL:
356       PM.add(polly::createCodeGenerationPass());
357       break;
358     case CODEGEN_NONE:
359       break;
360     }
361 #ifdef GPU_CODEGEN
362   else
363     PM.add(
364         polly::createPPCGCodeGenerationPass(GPUArchChoice, GPURuntimeChoice));
365 #endif
366 
367   // FIXME: This dummy ModulePass keeps some programs from miscompiling,
368   // probably some not correctly preserved analyses. It acts as a barrier to
369   // force all analysis results to be recomputed.
370   PM.add(createBarrierNoopPass());
371 
372   if (DumpAfter)
373     PM.add(polly::createDumpModulePass("-after", true));
374   for (auto &Filename : DumpAfterFile)
375     PM.add(polly::createDumpModulePass(Filename, false));
376 
377   if (CFGPrinter)
378     PM.add(llvm::createCFGPrinterLegacyPassPass());
379 }
380 
381 static bool shouldEnablePolly() {
382   if (PollyOnlyPrinter || PollyPrinter || PollyOnlyViewer || PollyViewer)
383     PollyTrackFailures = true;
384 
385   if (PollyOnlyPrinter || PollyPrinter || PollyOnlyViewer || PollyViewer ||
386       ExportJScop || ImportJScop)
387     PollyEnabled = true;
388 
389   return PollyEnabled;
390 }
391 
392 static void
393 registerPollyEarlyAsPossiblePasses(const llvm::PassManagerBuilder &Builder,
394                                    llvm::legacy::PassManagerBase &PM) {
395   if (!polly::shouldEnablePolly())
396     return;
397 
398   if (PassPosition != POSITION_EARLY)
399     return;
400 
401   registerCanonicalicationPasses(PM);
402   polly::registerPollyPasses(PM);
403 }
404 
405 static void
406 registerPollyLoopOptimizerEndPasses(const llvm::PassManagerBuilder &Builder,
407                                     llvm::legacy::PassManagerBase &PM) {
408   if (!polly::shouldEnablePolly())
409     return;
410 
411   if (PassPosition != POSITION_AFTER_LOOPOPT)
412     return;
413 
414   PM.add(polly::createCodePreparationPass());
415   polly::registerPollyPasses(PM);
416   PM.add(createCodegenCleanupPass());
417 }
418 
419 static void
420 registerPollyScalarOptimizerLatePasses(const llvm::PassManagerBuilder &Builder,
421                                        llvm::legacy::PassManagerBase &PM) {
422   if (!polly::shouldEnablePolly())
423     return;
424 
425   if (PassPosition != POSITION_BEFORE_VECTORIZER)
426     return;
427 
428   PM.add(polly::createCodePreparationPass());
429   polly::registerPollyPasses(PM);
430   PM.add(createCodegenCleanupPass());
431 }
432 
433 /// Register Polly to be available as an optimizer
434 ///
435 ///
436 /// We can currently run Polly at three different points int the pass manager.
437 /// a) very early, b) after the canonicalizing loop transformations and c) right
438 /// before the vectorizer.
439 ///
440 /// The default is currently a), to register Polly such that it runs as early as
441 /// possible. This has several implications:
442 ///
443 ///   1) We need to schedule more canonicalization passes
444 ///
445 ///   As nothing is run before Polly, it is necessary to run a set of preparing
446 ///   transformations before Polly to canonicalize the LLVM-IR and to allow
447 ///   Polly to detect and understand the code.
448 ///
449 ///   2) LICM and LoopIdiom pass have not yet been run
450 ///
451 ///   Loop invariant code motion as well as the loop idiom recognition pass make
452 ///   it more difficult for Polly to transform code. LICM may introduce
453 ///   additional data dependences that are hard to eliminate and the loop idiom
454 ///   recognition pass may introduce calls to memset that we currently do not
455 ///   understand. By running Polly early enough (meaning before these passes) we
456 ///   avoid difficulties that may be introduced by these passes.
457 ///
458 ///   3) We get the full -O3 optimization sequence after Polly
459 ///
460 ///   The LLVM-IR that is generated by Polly has been optimized on a high level,
461 ///   but it may be rather inefficient on the lower/scalar level. By scheduling
462 ///   Polly before all other passes, we have the full sequence of -O3
463 ///   optimizations behind us, such that inefficiencies on the low level can
464 ///   be optimized away.
465 ///
466 /// We are currently evaluating the benefit or running Polly at position b) or
467 /// c). b) is likely too early as it interacts with the inliner. c) is nice
468 /// as everything is fully inlined and canonicalized, but we need to be able
469 /// to handle LICMed code to make it useful.
470 static llvm::RegisterStandardPasses RegisterPollyOptimizerEarly(
471     llvm::PassManagerBuilder::EP_ModuleOptimizerEarly,
472     registerPollyEarlyAsPossiblePasses);
473 
474 static llvm::RegisterStandardPasses
475     RegisterPollyOptimizerLoopEnd(llvm::PassManagerBuilder::EP_LoopOptimizerEnd,
476                                   registerPollyLoopOptimizerEndPasses);
477 
478 static llvm::RegisterStandardPasses RegisterPollyOptimizerScalarLate(
479     llvm::PassManagerBuilder::EP_VectorizerStart,
480     registerPollyScalarOptimizerLatePasses);
481 } // namespace polly
482