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/DependenceInfo.h"
26 #include "polly/LinkAllPasses.h"
27 #include "polly/Options.h"
28 #include "polly/ScopDetection.h"
29 #include "polly/ScopInfo.h"
30 #include "polly/TempScopInfo.h"
31 #include "llvm/Analysis/CFGPrinter.h"
32 #include "llvm/IR/LegacyPassManager.h"
33 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
34 #include "llvm/Transforms/Scalar.h"
35 #include "llvm/Transforms/Vectorize.h"
36 
37 using namespace llvm;
38 using namespace polly;
39 
40 cl::OptionCategory PollyCategory("Polly Options",
41                                  "Configure the polly loop optimizer");
42 
43 static cl::opt<bool>
44     PollyEnabled("polly", cl::desc("Enable the polly optimizer (only at -O3)"),
45                  cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
46 
47 static cl::opt<bool> PollyDetectOnly(
48     "polly-only-scop-detection",
49     cl::desc("Only run scop detection, but no other optimizations"),
50     cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
51 
52 enum OptimizerChoice { OPTIMIZER_NONE, OPTIMIZER_ISL };
53 
54 static cl::opt<OptimizerChoice> Optimizer(
55     "polly-optimizer", cl::desc("Select the scheduling optimizer"),
56     cl::values(clEnumValN(OPTIMIZER_NONE, "none", "No optimizer"),
57                clEnumValN(OPTIMIZER_ISL, "isl", "The isl scheduling optimizer"),
58                clEnumValEnd),
59     cl::Hidden, cl::init(OPTIMIZER_ISL), cl::ZeroOrMore,
60     cl::cat(PollyCategory));
61 
62 enum CodeGenChoice { CODEGEN_ISL, CODEGEN_NONE };
63 static cl::opt<CodeGenChoice> CodeGenerator(
64     "polly-code-generator", cl::desc("Select the code generator"),
65     cl::values(clEnumValN(CODEGEN_ISL, "isl", "isl code generator"),
66                clEnumValN(CODEGEN_NONE, "none", "no code generation"),
67                clEnumValEnd),
68     cl::Hidden, cl::init(CODEGEN_ISL), cl::ZeroOrMore, cl::cat(PollyCategory));
69 
70 VectorizerChoice polly::PollyVectorizerChoice;
71 static cl::opt<polly::VectorizerChoice, true> Vectorizer(
72     "polly-vectorizer", cl::desc("Select the vectorization strategy"),
73     cl::values(
74         clEnumValN(polly::VECTORIZER_NONE, "none", "No Vectorization"),
75         clEnumValN(polly::VECTORIZER_POLLY, "polly",
76                    "Polly internal vectorizer"),
77         clEnumValN(polly::VECTORIZER_STRIPMINE, "stripmine",
78                    "Strip-mine outer loops for the loop-vectorizer to trigger"),
79         clEnumValEnd),
80     cl::location(PollyVectorizerChoice), cl::init(polly::VECTORIZER_NONE),
81     cl::ZeroOrMore, cl::cat(PollyCategory));
82 
83 static cl::opt<bool> ImportJScop(
84     "polly-import",
85     cl::desc("Export the polyhedral description of the detected Scops"),
86     cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
87 
88 static cl::opt<bool> ExportJScop(
89     "polly-export",
90     cl::desc("Export the polyhedral description of the detected Scops"),
91     cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
92 
93 static cl::opt<bool> DeadCodeElim("polly-run-dce",
94                                   cl::desc("Run the dead code elimination"),
95                                   cl::Hidden, cl::init(false), cl::ZeroOrMore,
96                                   cl::cat(PollyCategory));
97 
98 static cl::opt<bool> PollyViewer(
99     "polly-show",
100     cl::desc("Highlight the code regions that will be optimized in a "
101              "(CFG BBs and LLVM-IR instructions)"),
102     cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
103 
104 static cl::opt<bool> PollyOnlyViewer(
105     "polly-show-only",
106     cl::desc("Highlight the code regions that will be optimized in "
107              "a (CFG only BBs)"),
108     cl::init(false), cl::cat(PollyCategory));
109 
110 static cl::opt<bool>
111     PollyPrinter("polly-dot", cl::desc("Enable the Polly DOT printer in -O3"),
112                  cl::Hidden, cl::value_desc("Run the Polly DOT printer at -O3"),
113                  cl::init(false), cl::cat(PollyCategory));
114 
115 static cl::opt<bool> PollyOnlyPrinter(
116     "polly-dot-only",
117     cl::desc("Enable the Polly DOT printer in -O3 (no BB content)"), cl::Hidden,
118     cl::value_desc("Run the Polly DOT printer at -O3 (no BB content"),
119     cl::init(false), cl::cat(PollyCategory));
120 
121 static cl::opt<bool>
122     CFGPrinter("polly-view-cfg",
123                cl::desc("Show the Polly CFG right after code generation"),
124                cl::Hidden, cl::init(false), cl::cat(PollyCategory));
125 
126 namespace polly {
127 void initializePollyPasses(PassRegistry &Registry) {
128   initializeIslCodeGenerationPass(Registry);
129   initializeCodePreparationPass(Registry);
130   initializeDeadCodeElimPass(Registry);
131   initializeDependenceInfoPass(Registry);
132   initializeIndependentBlocksPass(Registry);
133   initializeJSONExporterPass(Registry);
134   initializeJSONImporterPass(Registry);
135   initializeIslAstInfoPass(Registry);
136   initializeIslScheduleOptimizerPass(Registry);
137   initializePollyCanonicalizePass(Registry);
138   initializeScopDetectionPass(Registry);
139   initializeScopInfoPass(Registry);
140   initializeTempScopInfoPass(Registry);
141 }
142 
143 /// @brief Register Polly passes such that they form a polyhedral optimizer.
144 ///
145 /// The individual Polly passes are registered in the pass manager such that
146 /// they form a full polyhedral optimizer. The flow of the optimizer starts with
147 /// a set of preparing transformations that canonicalize the LLVM-IR such that
148 /// the LLVM-IR is easier for us to understand and to optimizes. On the
149 /// canonicalized LLVM-IR we first run the ScopDetection pass, which detects
150 /// static control flow regions. Those regions are then translated by the
151 /// ScopInfo pass into a polyhedral representation. As a next step, a scheduling
152 /// optimizer is run on the polyhedral representation and finally the optimized
153 /// polyhedral representation is code generated back to LLVM-IR.
154 ///
155 /// Besides this core functionality, we optionally schedule passes that provide
156 /// a graphical view of the scops (Polly[Only]Viewer, Polly[Only]Printer), that
157 /// allow the export/import of the polyhedral representation
158 /// (JSCON[Exporter|Importer]) or that show the cfg after code generation.
159 ///
160 /// For certain parts of the Polly optimizer, several alternatives are provided:
161 ///
162 /// As scheduling optimizer we support the isl scheduling optimizer
163 /// (http://freecode.com/projects/isl).
164 /// It is also possible to run Polly with no optimizer. This mode is mainly
165 /// provided to analyze the run and compile time changes caused by the
166 /// scheduling optimizer.
167 ///
168 /// Polly supports the isl internal code generator.
169 void registerPollyPasses(llvm::legacy::PassManagerBase &PM) {
170   registerCanonicalicationPasses(PM);
171 
172   PM.add(polly::createScopDetectionPass());
173 
174   if (PollyDetectOnly)
175     return;
176 
177   PM.add(polly::createScopInfoPass());
178 
179   if (PollyViewer)
180     PM.add(polly::createDOTViewerPass());
181   if (PollyOnlyViewer)
182     PM.add(polly::createDOTOnlyViewerPass());
183   if (PollyPrinter)
184     PM.add(polly::createDOTPrinterPass());
185   if (PollyOnlyPrinter)
186     PM.add(polly::createDOTOnlyPrinterPass());
187 
188   if (ImportJScop)
189     PM.add(polly::createJSONImporterPass());
190 
191   if (DeadCodeElim)
192     PM.add(polly::createDeadCodeElimPass());
193 
194   switch (Optimizer) {
195   case OPTIMIZER_NONE:
196     break; /* Do nothing */
197 
198   case OPTIMIZER_ISL:
199     PM.add(polly::createIslScheduleOptimizerPass());
200     break;
201   }
202 
203   if (ExportJScop)
204     PM.add(polly::createJSONExporterPass());
205 
206   switch (CodeGenerator) {
207   case CODEGEN_ISL:
208     PM.add(polly::createIslCodeGenerationPass());
209     break;
210   case CODEGEN_NONE:
211     break;
212   }
213 
214   if (CFGPrinter)
215     PM.add(llvm::createCFGPrinterPass());
216 }
217 
218 static bool shouldEnablePolly() {
219   if (PollyOnlyPrinter || PollyPrinter || PollyOnlyViewer || PollyViewer)
220     PollyTrackFailures = true;
221 
222   if (PollyOnlyPrinter || PollyPrinter || PollyOnlyViewer || PollyViewer ||
223       ExportJScop || ImportJScop)
224     PollyEnabled = true;
225 
226   return PollyEnabled;
227 }
228 
229 static void
230 registerPollyEarlyAsPossiblePasses(const llvm::PassManagerBuilder &Builder,
231                                    llvm::legacy::PassManagerBase &PM) {
232   if (!polly::shouldEnablePolly())
233     return;
234 
235   polly::registerPollyPasses(PM);
236 }
237 
238 /// @brief Register Polly to be available as an optimizer
239 ///
240 /// We currently register Polly such that it runs as early as possible. This has
241 /// several implications:
242 ///
243 ///   1) We need to schedule more canonicalization passes
244 ///
245 ///   As nothing is run before Polly, it is necessary to run a set of preparing
246 ///   transformations before Polly to canonicalize the LLVM-IR and to allow
247 ///   Polly to detect and understand the code.
248 ///
249 ///   2) LICM and LoopIdiom pass have not yet been run
250 ///
251 ///   Loop invariant code motion as well as the loop idiom recognition pass make
252 ///   it more difficult for Polly to transform code. LICM may introduce
253 ///   additional data dependences that are hard to eliminate and the loop idiom
254 ///   recognition pass may introduce calls to memset that we currently do not
255 ///   understand. By running Polly early enough (meaning before these passes) we
256 ///   avoid difficulties that may be introduced by these passes.
257 ///
258 ///   3) We get the full -O3 optimization sequence after Polly
259 ///
260 ///   The LLVM-IR that is generated by Polly has been optimized on a high level,
261 ///   but it may be rather inefficient on the lower/scalar level. By scheduling
262 ///   Polly before all other passes, we have the full sequence of -O3
263 ///   optimizations behind us, such that inefficiencies on the low level can
264 ///   be optimized away.
265 static llvm::RegisterStandardPasses
266     RegisterPollyOptimizer(llvm::PassManagerBuilder::EP_EarlyAsPossible,
267                            registerPollyEarlyAsPossiblePasses);
268 }
269