blob: 8c773d817a173a18849775b32404df0b4a3be3be [file] [log] [blame]
Tobias Grosser30aa24c2011-05-14 19:02:06 +00001//===- Schedule.cpp - Calculate an optimized schedule ---------------------===//
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//
Tobias Grosser234a4822015-08-15 09:34:33 +000010// This pass generates an entirey new schedule tree from the data dependences
11// and iteration domains. The new schedule tree is computed in two steps:
Tobias Grosser30aa24c2011-05-14 19:02:06 +000012//
Tobias Grosser234a4822015-08-15 09:34:33 +000013// 1) The isl scheduling optimizer is run
14//
15// The isl scheduling optimizer creates a new schedule tree that maximizes
16// parallelism and tileability and minimizes data-dependence distances. The
17// algorithm used is a modified version of the ``Pluto'' algorithm:
18//
19// U. Bondhugula, A. Hartono, J. Ramanujam, and P. Sadayappan.
20// A Practical Automatic Polyhedral Parallelizer and Locality Optimizer.
21// In Proceedings of the 2008 ACM SIGPLAN Conference On Programming Language
22// Design and Implementation, PLDI ’08, pages 101–113. ACM, 2008.
23//
24// 2) A set of post-scheduling transformations is applied on the schedule tree.
25//
26// These optimizations include:
27//
28// - Tiling of the innermost tilable bands
29// - Prevectorization - The coice of a possible outer loop that is strip-mined
30// to the innermost level to enable inner-loop
31// vectorization.
32// - Some optimizations for spatial locality are also planned.
33//
34// For a detailed description of the schedule tree itself please see section 6
35// of:
36//
37// Polyhedral AST generation is more than scanning polyhedra
38// Tobias Grosser, Sven Verdoolaege, Albert Cohen
39// ACM Transations on Programming Languages and Systems (TOPLAS),
40// 37(4), July 2015
41// http://www.grosser.es/#pub-polyhedral-AST-generation
42//
43// This publication also contains a detailed discussion of the different options
44// for polyhedral loop unrolling, full/partial tile separation and other uses
45// of the schedule tree.
46//
Tobias Grosser30aa24c2011-05-14 19:02:06 +000047//===----------------------------------------------------------------------===//
48
Tobias Grosser967239c2011-10-23 20:59:44 +000049#include "polly/ScheduleOptimizer.h"
Tobias Grosserba0d0922015-05-09 09:13:42 +000050#include "polly/CodeGen/CodeGeneration.h"
51#include "polly/DependenceInfo.h"
52#include "polly/LinkAllPasses.h"
53#include "polly/Options.h"
54#include "polly/ScopInfo.h"
55#include "polly/Support/GICHelper.h"
56#include "llvm/Support/Debug.h"
Tobias Grosser2493e922011-12-07 07:42:57 +000057#include "isl/aff.h"
Tobias Grosserde68cc92011-06-30 20:01:02 +000058#include "isl/band.h"
Tobias Grosser8ad6bc32012-01-31 13:26:29 +000059#include "isl/constraint.h"
60#include "isl/map.h"
Tobias Grosser42152ff2012-01-30 19:38:47 +000061#include "isl/options.h"
Tobias Grosser97d87452015-05-30 06:46:59 +000062#include "isl/printer.h"
Tobias Grosser8ad6bc32012-01-31 13:26:29 +000063#include "isl/schedule.h"
Tobias Grosserbbb4cec2015-03-22 12:06:39 +000064#include "isl/schedule_node.h"
Tobias Grosser8ad6bc32012-01-31 13:26:29 +000065#include "isl/space.h"
Tobias Grossercd524dc2015-05-09 09:36:38 +000066#include "isl/union_map.h"
67#include "isl/union_set.h"
Tobias Grosser30aa24c2011-05-14 19:02:06 +000068
69using namespace llvm;
70using namespace polly;
71
Chandler Carruth95fef942014-04-22 03:30:19 +000072#define DEBUG_TYPE "polly-opt-isl"
73
Tobias Grossera26db472012-01-30 19:38:43 +000074static cl::opt<std::string>
Tobias Grosser483a90d2014-07-09 10:50:10 +000075 OptimizeDeps("polly-opt-optimize-only",
76 cl::desc("Only a certain kind of dependences (all/raw)"),
77 cl::Hidden, cl::init("all"), cl::ZeroOrMore,
78 cl::cat(PollyCategory));
Tobias Grosser1deda292012-02-14 14:02:48 +000079
80static cl::opt<std::string>
Tobias Grosser483a90d2014-07-09 10:50:10 +000081 SimplifyDeps("polly-opt-simplify-deps",
82 cl::desc("Dependences should be simplified (yes/no)"),
83 cl::Hidden, cl::init("yes"), cl::ZeroOrMore,
84 cl::cat(PollyCategory));
Tobias Grossera26db472012-01-30 19:38:43 +000085
Tobias Grosser483a90d2014-07-09 10:50:10 +000086static cl::opt<int> MaxConstantTerm(
87 "polly-opt-max-constant-term",
88 cl::desc("The maximal constant term allowed (-1 is unlimited)"), cl::Hidden,
89 cl::init(20), cl::ZeroOrMore, cl::cat(PollyCategory));
Tobias Grosser992e60c2012-02-20 08:41:15 +000090
Tobias Grosser483a90d2014-07-09 10:50:10 +000091static cl::opt<int> MaxCoefficient(
92 "polly-opt-max-coefficient",
93 cl::desc("The maximal coefficient allowed (-1 is unlimited)"), cl::Hidden,
94 cl::init(20), cl::ZeroOrMore, cl::cat(PollyCategory));
95
96static cl::opt<std::string> FusionStrategy(
97 "polly-opt-fusion", cl::desc("The fusion strategy to choose (min/max)"),
98 cl::Hidden, cl::init("min"), cl::ZeroOrMore, cl::cat(PollyCategory));
Tobias Grosser92f54802012-02-20 08:41:47 +000099
Tobias Grossere602a072013-05-07 07:30:56 +0000100static cl::opt<std::string>
Tobias Grosser483a90d2014-07-09 10:50:10 +0000101 MaximizeBandDepth("polly-opt-maximize-bands",
102 cl::desc("Maximize the band depth (yes/no)"), cl::Hidden,
103 cl::init("yes"), cl::ZeroOrMore, cl::cat(PollyCategory));
Tobias Grosserb3ad85b2012-01-30 19:38:50 +0000104
Tobias Grosser07c1c2f2015-08-19 08:46:11 +0000105static cl::opt<int> PrevectorWidth(
106 "polly-prevect-width",
107 cl::desc(
108 "The number of loop iterations to strip-mine for pre-vectorization"),
109 cl::Hidden, cl::init(4), cl::ZeroOrMore, cl::cat(PollyCategory));
110
Tobias Grosser04832712015-08-20 13:45:02 +0000111static cl::opt<bool> FirstLevelTiling("polly-tiling",
112 cl::desc("Enable loop tiling"),
113 cl::init(true), cl::ZeroOrMore,
114 cl::cat(PollyCategory));
115
116static cl::opt<int> FirstLevelDefaultTileSize(
Tobias Grosser483a90d2014-07-09 10:50:10 +0000117 "polly-default-tile-size",
118 cl::desc("The default tile size (if not enough were provided by"
119 " --polly-tile-sizes)"),
120 cl::Hidden, cl::init(32), cl::ZeroOrMore, cl::cat(PollyCategory));
Johannes Doerfertc3958b22014-05-28 17:21:02 +0000121
Tobias Grosser04832712015-08-20 13:45:02 +0000122static cl::list<int> FirstLevelTileSizes(
123 "polly-tile-sizes", cl::desc("A tile size for each loop dimension, filled "
124 "with --polly-default-tile-size"),
125 cl::Hidden, cl::ZeroOrMore, cl::CommaSeparated, cl::cat(PollyCategory));
126
127static cl::opt<bool>
128 SecondLevelTiling("polly-2nd-level-tiling",
129 cl::desc("Enable a 2nd level loop of loop tiling"),
130 cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
131
132static cl::opt<int> SecondLevelDefaultTileSize(
133 "polly-2nd-level-default-tile-size",
134 cl::desc("The default 2nd-level tile size (if not enough were provided by"
135 " --polly-2nd-level-tile-sizes)"),
136 cl::Hidden, cl::init(16), cl::ZeroOrMore, cl::cat(PollyCategory));
137
138static cl::list<int>
139 SecondLevelTileSizes("polly-2nd-level-tile-sizes",
140 cl::desc("A tile size for each loop dimension, filled "
141 "with --polly-default-tile-size"),
142 cl::Hidden, cl::ZeroOrMore, cl::CommaSeparated,
143 cl::cat(PollyCategory));
144
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000145namespace {
146
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000147class IslScheduleOptimizer : public ScopPass {
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000148public:
149 static char ID;
Tobias Grosser5a56cbf2014-04-16 07:33:47 +0000150 explicit IslScheduleOptimizer() : ScopPass(ID) { LastSchedule = nullptr; }
Tobias Grosser28781422012-10-16 07:29:19 +0000151
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000152 ~IslScheduleOptimizer() { isl_schedule_free(LastSchedule); }
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000153
Johannes Doerfert909a3bf2015-03-01 18:42:08 +0000154 bool runOnScop(Scop &S) override;
155 void printScop(raw_ostream &OS, Scop &S) const override;
156 void getAnalysisUsage(AnalysisUsage &AU) const override;
Tobias Grosser460e9a42012-04-25 13:22:43 +0000157
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000158private:
159 isl_schedule *LastSchedule;
Tobias Grosser28781422012-10-16 07:29:19 +0000160
Johannes Doerfert7ceb0402015-02-11 17:25:09 +0000161 /// @brief Decide if the @p NewSchedule is profitable for @p S.
162 ///
163 /// @param S The SCoP we optimize.
164 /// @param NewSchedule The new schedule we computed.
165 ///
166 /// @return True, if we believe @p NewSchedule is an improvement for @p S.
167 bool isProfitableSchedule(Scop &S, __isl_keep isl_union_map *NewSchedule);
168
Tobias Grosser9bdea572015-08-20 12:22:37 +0000169 /// @brief Tile a schedule node.
170 ///
171 /// @param Node The node to tile.
172 /// @param TileSizes A vector of tile sizes that should be used for
173 /// tiling.
174 /// @param DefaultTileSize A default tile size that is used for dimensions
175 /// that are not covered by the TileSizes vector.
176 static __isl_give isl_schedule_node *
177 tileNode(__isl_take isl_schedule_node *Node, ArrayRef<int> TileSizes,
178 int DefaultTileSize);
179
Tobias Grosser862b9b52015-08-20 12:32:45 +0000180 /// @brief Check if this node is a band node we want to tile.
181 ///
182 /// We look for innermost band nodes where individual dimensions are marked as
183 /// permutable.
184 ///
185 /// @param Node The node to check.
186 static bool isTileableBandNode(__isl_keep isl_schedule_node *Node);
187
Tobias Grosserb241d922015-07-28 18:03:36 +0000188 /// @brief Pre-vectorizes one scheduling dimension of a schedule band.
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000189 ///
Tobias Grosserb241d922015-07-28 18:03:36 +0000190 /// prevectSchedBand splits out the dimension DimToVectorize, tiles it and
191 /// sinks the resulting point loop.
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000192 ///
Tobias Grosserb241d922015-07-28 18:03:36 +0000193 /// Example (DimToVectorize=0, VectorWidth=4):
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000194 ///
Tobias Grosserb241d922015-07-28 18:03:36 +0000195 /// | Before transformation:
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000196 /// |
197 /// | A[i,j] -> [i,j]
198 /// |
199 /// | for (i = 0; i < 128; i++)
200 /// | for (j = 0; j < 128; j++)
201 /// | A(i,j);
202 ///
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000203 /// | After transformation:
204 /// |
Tobias Grosserb241d922015-07-28 18:03:36 +0000205 /// | for (it = 0; it < 32; it+=1)
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000206 /// | for (j = 0; j < 128; j++)
Tobias Grosserb241d922015-07-28 18:03:36 +0000207 /// | for (ip = 0; ip <= 3; ip++)
208 /// | A(4 * it + ip,j);
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000209 ///
210 /// The goal of this transformation is to create a trivially vectorizable
211 /// loop. This means a parallel loop at the innermost level that has a
212 /// constant number of iterations corresponding to the target vector width.
213 ///
214 /// This transformation creates a loop at the innermost level. The loop has
215 /// a constant number of iterations, if the number of loop iterations at
216 /// DimToVectorize can be divided by VectorWidth. The default VectorWidth is
217 /// currently constant and not yet target specific. This function does not
218 /// reason about parallelism.
Tobias Grosserb241d922015-07-28 18:03:36 +0000219 static __isl_give isl_schedule_node *
220 prevectSchedBand(__isl_take isl_schedule_node *Node, unsigned DimToVectorize,
Tobias Grosser07c1c2f2015-08-19 08:46:11 +0000221 int VectorWidth);
Tobias Grosser460e9a42012-04-25 13:22:43 +0000222
Tobias Grosserbbb4cec2015-03-22 12:06:39 +0000223 /// @brief Apply additional optimizations on the bands in the schedule tree.
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000224 ///
Tobias Grosserbbb4cec2015-03-22 12:06:39 +0000225 /// We are looking for an innermost band node and apply the following
226 /// transformations:
227 ///
228 /// - Tile the band
229 /// - if the band is tileable
230 /// - if the band has more than one loop dimension
231 ///
Tobias Grosser3b10c942015-07-25 12:28:56 +0000232 /// - Prevectorize the schedule of the band (or the point loop in case of
Tobias Grosserb241d922015-07-28 18:03:36 +0000233 /// tiling).
Tobias Grosserbbb4cec2015-03-22 12:06:39 +0000234 /// - if vectorization is enabled
235 ///
236 /// @param Node The schedule node to (possibly) optimize.
237 /// @param User A pointer to forward some use information (currently unused).
238 static isl_schedule_node *optimizeBand(isl_schedule_node *Node, void *User);
Tobias Grosser460e9a42012-04-25 13:22:43 +0000239
Tobias Grosser808cd692015-07-14 09:33:13 +0000240 /// @brief Apply post-scheduling transformations.
241 ///
242 /// This function applies a set of additional local transformations on the
243 /// schedule tree as it computed by the isl scheduler. Local transformations
244 /// applied include:
245 ///
246 /// - Tiling
247 /// - Prevectorization
248 ///
249 /// @param Schedule The schedule object post-transformations will be applied
250 /// on.
251 /// @returns The transformed schedule.
252 static __isl_give isl_schedule *
253 addPostTransforms(__isl_take isl_schedule *Schedule);
Tobias Grosser28781422012-10-16 07:29:19 +0000254
Tobias Grosser20532b82014-04-11 17:56:49 +0000255 using llvm::Pass::doFinalization;
256
Johannes Doerfert909a3bf2015-03-01 18:42:08 +0000257 virtual bool doFinalization() override {
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000258 isl_schedule_free(LastSchedule);
Tobias Grosser5a56cbf2014-04-16 07:33:47 +0000259 LastSchedule = nullptr;
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000260 return true;
261 }
262};
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000263}
264
Tobias Grosser73600b82011-10-08 00:30:40 +0000265char IslScheduleOptimizer::ID = 0;
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000266
Tobias Grosserb241d922015-07-28 18:03:36 +0000267__isl_give isl_schedule_node *
268IslScheduleOptimizer::prevectSchedBand(__isl_take isl_schedule_node *Node,
269 unsigned DimToVectorize,
270 int VectorWidth) {
271 assert(isl_schedule_node_get_type(Node) == isl_schedule_node_band);
Tobias Grosserc6699b72011-06-30 20:29:13 +0000272
Tobias Grosserb241d922015-07-28 18:03:36 +0000273 auto Space = isl_schedule_node_band_get_space(Node);
274 auto ScheduleDimensions = isl_space_dim(Space, isl_dim_set);
275 isl_space_free(Space);
276 assert(DimToVectorize < ScheduleDimensions);
Tobias Grosserf5338802011-10-06 00:03:35 +0000277
Tobias Grosserb241d922015-07-28 18:03:36 +0000278 if (DimToVectorize > 0) {
279 Node = isl_schedule_node_band_split(Node, DimToVectorize);
280 Node = isl_schedule_node_child(Node, 0);
281 }
282 if (DimToVectorize < ScheduleDimensions - 1)
283 Node = isl_schedule_node_band_split(Node, 1);
284 Space = isl_schedule_node_band_get_space(Node);
285 auto Sizes = isl_multi_val_zero(Space);
286 auto Ctx = isl_schedule_node_get_ctx(Node);
287 Sizes =
288 isl_multi_val_set_val(Sizes, 0, isl_val_int_from_si(Ctx, VectorWidth));
289 Node = isl_schedule_node_band_tile(Node, Sizes);
290 Node = isl_schedule_node_child(Node, 0);
291 Node = isl_schedule_node_band_sink(Node);
292 Node = isl_schedule_node_child(Node, 0);
293 return Node;
Tobias Grosserc6699b72011-06-30 20:29:13 +0000294}
295
Tobias Grosserd891b542015-08-20 12:16:23 +0000296__isl_give isl_schedule_node *
Tobias Grosser9bdea572015-08-20 12:22:37 +0000297IslScheduleOptimizer::tileNode(__isl_take isl_schedule_node *Node,
298 ArrayRef<int> TileSizes, int DefaultTileSize) {
299 auto Ctx = isl_schedule_node_get_ctx(Node);
300 auto Space = isl_schedule_node_band_get_space(Node);
301 auto Dims = isl_space_dim(Space, isl_dim_set);
302 auto Sizes = isl_multi_val_zero(Space);
303 for (unsigned i = 0; i < Dims; i++) {
304 auto tileSize = i < TileSizes.size() ? TileSizes[i] : DefaultTileSize;
305 Sizes = isl_multi_val_set_val(Sizes, i, isl_val_int_from_si(Ctx, tileSize));
306 }
307 Node = isl_schedule_node_band_tile(Node, Sizes);
308 return isl_schedule_node_child(Node, 0);
309}
310
Tobias Grosser862b9b52015-08-20 12:32:45 +0000311bool IslScheduleOptimizer::isTileableBandNode(
312 __isl_keep isl_schedule_node *Node) {
Tobias Grosserbbb4cec2015-03-22 12:06:39 +0000313 if (isl_schedule_node_get_type(Node) != isl_schedule_node_band)
Tobias Grosser862b9b52015-08-20 12:32:45 +0000314 return false;
Tobias Grosserde68cc92011-06-30 20:01:02 +0000315
Tobias Grosserbbb4cec2015-03-22 12:06:39 +0000316 if (isl_schedule_node_n_children(Node) != 1)
Tobias Grosser862b9b52015-08-20 12:32:45 +0000317 return false;
Tobias Grosserde68cc92011-06-30 20:01:02 +0000318
Tobias Grosserbbb4cec2015-03-22 12:06:39 +0000319 if (!isl_schedule_node_band_get_permutable(Node))
Tobias Grosser862b9b52015-08-20 12:32:45 +0000320 return false;
Tobias Grosser44f19ac2011-07-05 22:15:53 +0000321
Tobias Grosserbbb4cec2015-03-22 12:06:39 +0000322 auto Space = isl_schedule_node_band_get_space(Node);
323 auto Dims = isl_space_dim(Space, isl_dim_set);
Tobias Grosser9bdea572015-08-20 12:22:37 +0000324 isl_space_free(Space);
Tobias Grosserde68cc92011-06-30 20:01:02 +0000325
Tobias Grosser9bdea572015-08-20 12:22:37 +0000326 if (Dims <= 1)
Tobias Grosser862b9b52015-08-20 12:32:45 +0000327 return false;
Tobias Grosserde68cc92011-06-30 20:01:02 +0000328
Tobias Grosserbbb4cec2015-03-22 12:06:39 +0000329 auto Child = isl_schedule_node_get_child(Node, 0);
330 auto Type = isl_schedule_node_get_type(Child);
331 isl_schedule_node_free(Child);
332
Tobias Grosser9bdea572015-08-20 12:22:37 +0000333 if (Type != isl_schedule_node_leaf)
Tobias Grosser862b9b52015-08-20 12:32:45 +0000334 return false;
335
336 return true;
337}
338
339__isl_give isl_schedule_node *
340IslScheduleOptimizer::optimizeBand(__isl_take isl_schedule_node *Node,
341 void *User) {
342 if (!isTileableBandNode(Node))
Tobias Grosserbbb4cec2015-03-22 12:06:39 +0000343 return Node;
Tobias Grosserbbb4cec2015-03-22 12:06:39 +0000344
Tobias Grosser04832712015-08-20 13:45:02 +0000345 if (FirstLevelTiling)
346 Node = tileNode(Node, FirstLevelTileSizes, FirstLevelDefaultTileSize);
347
348 if (SecondLevelTiling)
349 Node = tileNode(Node, SecondLevelTileSizes, SecondLevelDefaultTileSize);
Tobias Grosserbbb4cec2015-03-22 12:06:39 +0000350
351 if (PollyVectorizerChoice == VECTORIZER_NONE)
Tobias Grosserf10f4632015-08-19 08:03:37 +0000352 return Node;
Tobias Grosserbbb4cec2015-03-22 12:06:39 +0000353
Tobias Grosser862b9b52015-08-20 12:32:45 +0000354 auto Space = isl_schedule_node_band_get_space(Node);
355 auto Dims = isl_space_dim(Space, isl_dim_set);
356 isl_space_free(Space);
357
Tobias Grosserb241d922015-07-28 18:03:36 +0000358 for (int i = Dims - 1; i >= 0; i--)
Tobias Grosserf10f4632015-08-19 08:03:37 +0000359 if (isl_schedule_node_band_member_get_coincident(Node, i)) {
Tobias Grosser07c1c2f2015-08-19 08:46:11 +0000360 Node = IslScheduleOptimizer::prevectSchedBand(Node, i, PrevectorWidth);
Tobias Grosserbbb4cec2015-03-22 12:06:39 +0000361 break;
362 }
Tobias Grosserbbb4cec2015-03-22 12:06:39 +0000363
Tobias Grosserf10f4632015-08-19 08:03:37 +0000364 return Node;
Tobias Grosserde68cc92011-06-30 20:01:02 +0000365}
366
Tobias Grosser808cd692015-07-14 09:33:13 +0000367__isl_give isl_schedule *
368IslScheduleOptimizer::addPostTransforms(__isl_take isl_schedule *Schedule) {
Tobias Grosserbbb4cec2015-03-22 12:06:39 +0000369 isl_schedule_node *Root = isl_schedule_get_root(Schedule);
Tobias Grosser808cd692015-07-14 09:33:13 +0000370 isl_schedule_free(Schedule);
Tobias Grosserb2f39922015-05-28 13:32:11 +0000371 Root = isl_schedule_node_map_descendant_bottom_up(
Tobias Grosserbbb4cec2015-03-22 12:06:39 +0000372 Root, IslScheduleOptimizer::optimizeBand, NULL);
Tobias Grosser808cd692015-07-14 09:33:13 +0000373 auto S = isl_schedule_node_get_schedule(Root);
Tobias Grosserbbb4cec2015-03-22 12:06:39 +0000374 isl_schedule_node_free(Root);
Tobias Grosser808cd692015-07-14 09:33:13 +0000375 return S;
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000376}
377
Johannes Doerfert7ceb0402015-02-11 17:25:09 +0000378bool IslScheduleOptimizer::isProfitableSchedule(
379 Scop &S, __isl_keep isl_union_map *NewSchedule) {
380 // To understand if the schedule has been optimized we check if the schedule
381 // has changed at all.
382 // TODO: We can improve this by tracking if any necessarily beneficial
383 // transformations have been performed. This can e.g. be tiling, loop
384 // interchange, or ...) We can track this either at the place where the
385 // transformation has been performed or, in case of automatic ILP based
386 // optimizations, by comparing (yet to be defined) performance metrics
387 // before/after the scheduling optimizer
388 // (e.g., #stride-one accesses)
389 isl_union_map *OldSchedule = S.getSchedule();
390 bool changed = !isl_union_map_is_equal(OldSchedule, NewSchedule);
391 isl_union_map_free(OldSchedule);
392 return changed;
393}
394
Tobias Grosser73600b82011-10-08 00:30:40 +0000395bool IslScheduleOptimizer::runOnScop(Scop &S) {
Johannes Doerfert6f7921f2015-02-14 12:02:24 +0000396
397 // Skip empty SCoPs but still allow code generation as it will delete the
398 // loops present but not needed.
399 if (S.getSize() == 0) {
400 S.markAsOptimized();
401 return false;
402 }
403
Johannes Doerfert7e6424b2015-03-05 00:43:48 +0000404 const Dependences &D = getAnalysis<DependenceInfo>().getDependences();
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000405
Johannes Doerfert7e6424b2015-03-05 00:43:48 +0000406 if (!D.hasValidDependences())
Tobias Grosser38c36ea2014-02-23 15:15:44 +0000407 return false;
408
Tobias Grosser28781422012-10-16 07:29:19 +0000409 isl_schedule_free(LastSchedule);
Tobias Grosser5a56cbf2014-04-16 07:33:47 +0000410 LastSchedule = nullptr;
Tobias Grosser28781422012-10-16 07:29:19 +0000411
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000412 // Build input data.
Johannes Doerfert7e6424b2015-03-05 00:43:48 +0000413 int ValidityKinds =
414 Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;
Tobias Grosser1deda292012-02-14 14:02:48 +0000415 int ProximityKinds;
416
417 if (OptimizeDeps == "all")
Johannes Doerfert7e6424b2015-03-05 00:43:48 +0000418 ProximityKinds =
419 Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;
Tobias Grosser1deda292012-02-14 14:02:48 +0000420 else if (OptimizeDeps == "raw")
Johannes Doerfert7e6424b2015-03-05 00:43:48 +0000421 ProximityKinds = Dependences::TYPE_RAW;
Tobias Grosser1deda292012-02-14 14:02:48 +0000422 else {
423 errs() << "Do not know how to optimize for '" << OptimizeDeps << "'"
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000424 << " Falling back to optimizing all dependences.\n";
Johannes Doerfert7e6424b2015-03-05 00:43:48 +0000425 ProximityKinds =
426 Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;
Tobias Grosser1deda292012-02-14 14:02:48 +0000427 }
428
Tobias Grosser5f9a7622012-02-14 14:02:40 +0000429 isl_union_set *Domain = S.getDomains();
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000430
Tobias Grosser98610ee2012-02-13 23:31:39 +0000431 if (!Domain)
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000432 return false;
433
Johannes Doerfert7e6424b2015-03-05 00:43:48 +0000434 isl_union_map *Validity = D.getDependences(ValidityKinds);
435 isl_union_map *Proximity = D.getDependences(ProximityKinds);
Tobias Grosser8a507022012-03-16 11:51:41 +0000436
Tobias Grossera26db472012-01-30 19:38:43 +0000437 // Simplify the dependences by removing the constraints introduced by the
438 // domains. This can speed up the scheduling time significantly, as large
439 // constant coefficients will be removed from the dependences. The
440 // introduction of some additional dependences reduces the possible
441 // transformations, but in most cases, such transformation do not seem to be
442 // interesting anyway. In some cases this option may stop the scheduler to
443 // find any schedule.
444 if (SimplifyDeps == "yes") {
Tobias Grosser00383a72012-02-14 14:02:44 +0000445 Validity = isl_union_map_gist_domain(Validity, isl_union_set_copy(Domain));
446 Validity = isl_union_map_gist_range(Validity, isl_union_set_copy(Domain));
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000447 Proximity =
448 isl_union_map_gist_domain(Proximity, isl_union_set_copy(Domain));
Tobias Grosser00383a72012-02-14 14:02:44 +0000449 Proximity = isl_union_map_gist_range(Proximity, isl_union_set_copy(Domain));
Tobias Grossera26db472012-01-30 19:38:43 +0000450 } else if (SimplifyDeps != "no") {
451 errs() << "warning: Option -polly-opt-simplify-deps should either be 'yes' "
452 "or 'no'. Falling back to default: 'yes'\n";
453 }
454
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000455 DEBUG(dbgs() << "\n\nCompute schedule from: ");
Tobias Grosser01aea582014-10-22 23:16:28 +0000456 DEBUG(dbgs() << "Domain := " << stringFromIslObj(Domain) << ";\n");
457 DEBUG(dbgs() << "Proximity := " << stringFromIslObj(Proximity) << ";\n");
458 DEBUG(dbgs() << "Validity := " << stringFromIslObj(Validity) << ";\n");
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000459
Michael Krusec59f22c2015-06-18 16:45:40 +0000460 unsigned IslSerializeSCCs;
Tobias Grosserb3ad85b2012-01-30 19:38:50 +0000461
462 if (FusionStrategy == "max") {
Michael Krusec59f22c2015-06-18 16:45:40 +0000463 IslSerializeSCCs = 0;
Tobias Grosserb3ad85b2012-01-30 19:38:50 +0000464 } else if (FusionStrategy == "min") {
Michael Krusec59f22c2015-06-18 16:45:40 +0000465 IslSerializeSCCs = 1;
Tobias Grosserb3ad85b2012-01-30 19:38:50 +0000466 } else {
467 errs() << "warning: Unknown fusion strategy. Falling back to maximal "
468 "fusion.\n";
Michael Krusec59f22c2015-06-18 16:45:40 +0000469 IslSerializeSCCs = 0;
Tobias Grosserb3ad85b2012-01-30 19:38:50 +0000470 }
471
Tobias Grosser95e860c2012-01-30 19:38:54 +0000472 int IslMaximizeBands;
473
Tobias Grossera4ea90b2012-01-30 22:43:56 +0000474 if (MaximizeBandDepth == "yes") {
Tobias Grosser95e860c2012-01-30 19:38:54 +0000475 IslMaximizeBands = 1;
Tobias Grossera4ea90b2012-01-30 22:43:56 +0000476 } else if (MaximizeBandDepth == "no") {
Tobias Grosser95e860c2012-01-30 19:38:54 +0000477 IslMaximizeBands = 0;
478 } else {
479 errs() << "warning: Option -polly-opt-maximize-bands should either be 'yes'"
480 " or 'no'. Falling back to default: 'yes'\n";
481 IslMaximizeBands = 1;
482 }
483
Michael Krusec59f22c2015-06-18 16:45:40 +0000484 isl_options_set_schedule_serialize_sccs(S.getIslCtx(), IslSerializeSCCs);
Tobias Grosser95e860c2012-01-30 19:38:54 +0000485 isl_options_set_schedule_maximize_band_depth(S.getIslCtx(), IslMaximizeBands);
Tobias Grosser992e60c2012-02-20 08:41:15 +0000486 isl_options_set_schedule_max_constant_term(S.getIslCtx(), MaxConstantTerm);
Tobias Grosser92f54802012-02-20 08:41:47 +0000487 isl_options_set_schedule_max_coefficient(S.getIslCtx(), MaxCoefficient);
Tobias Grosser4f6bcef2015-03-31 07:52:36 +0000488 isl_options_set_tile_scale_tile_loops(S.getIslCtx(), 0);
Tobias Grosser42152ff2012-01-30 19:38:47 +0000489
490 isl_options_set_on_error(S.getIslCtx(), ISL_ON_ERROR_CONTINUE);
Tobias Grossera38c9242014-01-26 19:36:28 +0000491
492 isl_schedule_constraints *ScheduleConstraints;
493 ScheduleConstraints = isl_schedule_constraints_on_domain(Domain);
494 ScheduleConstraints =
495 isl_schedule_constraints_set_proximity(ScheduleConstraints, Proximity);
496 ScheduleConstraints = isl_schedule_constraints_set_validity(
497 ScheduleConstraints, isl_union_map_copy(Validity));
498 ScheduleConstraints =
499 isl_schedule_constraints_set_coincidence(ScheduleConstraints, Validity);
Tobias Grosser00383a72012-02-14 14:02:44 +0000500 isl_schedule *Schedule;
Tobias Grossera38c9242014-01-26 19:36:28 +0000501 Schedule = isl_schedule_constraints_compute_schedule(ScheduleConstraints);
Tobias Grosser42152ff2012-01-30 19:38:47 +0000502 isl_options_set_on_error(S.getIslCtx(), ISL_ON_ERROR_ABORT);
503
504 // In cases the scheduler is not able to optimize the code, we just do not
505 // touch the schedule.
Tobias Grosser98610ee2012-02-13 23:31:39 +0000506 if (!Schedule)
Tobias Grosser42152ff2012-01-30 19:38:47 +0000507 return false;
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000508
Tobias Grosser97d87452015-05-30 06:46:59 +0000509 DEBUG({
510 auto *P = isl_printer_to_str(S.getIslCtx());
511 P = isl_printer_set_yaml_style(P, ISL_YAML_STYLE_BLOCK);
512 P = isl_printer_print_schedule(P, Schedule);
513 dbgs() << "NewScheduleTree: \n" << isl_printer_get_str(P) << "\n";
514 isl_printer_free(P);
515 });
Tobias Grosser4d63b9d2012-02-20 08:41:21 +0000516
Tobias Grosser808cd692015-07-14 09:33:13 +0000517 isl_schedule *NewSchedule = addPostTransforms(Schedule);
518 isl_union_map *NewScheduleMap = isl_schedule_get_map(NewSchedule);
Johannes Doerfert7ceb0402015-02-11 17:25:09 +0000519
Tobias Grosser808cd692015-07-14 09:33:13 +0000520 if (!isProfitableSchedule(S, NewScheduleMap)) {
521 isl_union_map_free(NewScheduleMap);
522 isl_schedule_free(NewSchedule);
Johannes Doerfert7ceb0402015-02-11 17:25:09 +0000523 return false;
524 }
525
Tobias Grosser808cd692015-07-14 09:33:13 +0000526 S.setScheduleTree(NewSchedule);
Johannes Doerfert7ceb0402015-02-11 17:25:09 +0000527 S.markAsOptimized();
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000528
Tobias Grosser808cd692015-07-14 09:33:13 +0000529 isl_union_map_free(NewScheduleMap);
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000530 return false;
531}
532
Johannes Doerfert3fe584d2015-03-01 18:40:25 +0000533void IslScheduleOptimizer::printScop(raw_ostream &OS, Scop &) const {
Tobias Grosser28781422012-10-16 07:29:19 +0000534 isl_printer *p;
535 char *ScheduleStr;
536
537 OS << "Calculated schedule:\n";
538
539 if (!LastSchedule) {
540 OS << "n/a\n";
541 return;
542 }
543
544 p = isl_printer_to_str(isl_schedule_get_ctx(LastSchedule));
545 p = isl_printer_print_schedule(p, LastSchedule);
546 ScheduleStr = isl_printer_get_str(p);
547 isl_printer_free(p);
548
549 OS << ScheduleStr << "\n";
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000550}
551
Tobias Grosser73600b82011-10-08 00:30:40 +0000552void IslScheduleOptimizer::getAnalysisUsage(AnalysisUsage &AU) const {
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000553 ScopPass::getAnalysisUsage(AU);
Johannes Doerfertf6557f92015-03-04 22:43:40 +0000554 AU.addRequired<DependenceInfo>();
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000555}
556
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000557Pass *polly::createIslScheduleOptimizerPass() {
Tobias Grosser73600b82011-10-08 00:30:40 +0000558 return new IslScheduleOptimizer();
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000559}
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000560
561INITIALIZE_PASS_BEGIN(IslScheduleOptimizer, "polly-opt-isl",
562 "Polly - Optimize schedule of SCoP", false, false);
Johannes Doerfertf6557f92015-03-04 22:43:40 +0000563INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000564INITIALIZE_PASS_DEPENDENCY(ScopInfo);
565INITIALIZE_PASS_END(IslScheduleOptimizer, "polly-opt-isl",
566 "Polly - Optimize schedule of SCoP", false, false)