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