blob: 97555a01824be89e0809d8ebab9e07e1f91b9b42 [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//
10// This pass the isl to calculate a schedule that is optimized for parallelism
11// and tileablility. The algorithm used in isl is an optimized version of the
12// algorithm described in following paper:
13//
14// U. Bondhugula, A. Hartono, J. Ramanujam, and P. Sadayappan.
15// A Practical Automatic Polyhedral Parallelizer and Locality Optimizer.
16// In Proceedings of the 2008 ACM SIGPLAN Conference On Programming Language
17// Design and Implementation, PLDI ’08, pages 101–113. ACM, 2008.
18//===----------------------------------------------------------------------===//
19
Tobias Grosser967239c2011-10-23 20:59:44 +000020#include "polly/ScheduleOptimizer.h"
Tobias Grosser2493e922011-12-07 07:42:57 +000021#include "isl/aff.h"
Tobias Grosserde68cc92011-06-30 20:01:02 +000022#include "isl/band.h"
Tobias Grosser8ad6bc32012-01-31 13:26:29 +000023#include "isl/constraint.h"
24#include "isl/map.h"
Tobias Grosser42152ff2012-01-30 19:38:47 +000025#include "isl/options.h"
Tobias Grosser8ad6bc32012-01-31 13:26:29 +000026#include "isl/schedule.h"
27#include "isl/space.h"
Tobias Grosser83628182013-05-07 08:11:54 +000028#include "polly/CodeGen/CodeGeneration.h"
29#include "polly/Dependences.h"
30#include "polly/LinkAllPasses.h"
31#include "polly/Options.h"
32#include "polly/ScopInfo.h"
Tobias Grosser30aa24c2011-05-14 19:02:06 +000033
Tobias Grosser4dca4392011-11-22 19:40:19 +000034#define DEBUG_TYPE "polly-opt-isl"
Tobias Grosser30aa24c2011-05-14 19:02:06 +000035#include "llvm/Support/Debug.h"
36
37using namespace llvm;
38using namespace polly;
39
Tobias Grosser58032cb2013-06-23 01:29:29 +000040namespace polly {
41bool DisablePollyTiling;
42}
Tobias Grossere602a072013-05-07 07:30:56 +000043static cl::opt<bool, true>
44DisableTiling("polly-no-tiling", cl::desc("Disable tiling in the scheduler"),
Tobias Grosser637bd632013-05-07 07:31:10 +000045 cl::location(polly::DisablePollyTiling), cl::init(false),
Tobias Grosser64e8e372014-03-13 23:37:43 +000046 cl::ZeroOrMore, cl::cat(PollyCategory));
Tobias Grosser353a2682011-10-23 20:59:26 +000047
Tobias Grossera26db472012-01-30 19:38:43 +000048static cl::opt<std::string>
Tobias Grosser1deda292012-02-14 14:02:48 +000049OptimizeDeps("polly-opt-optimize-only",
50 cl::desc("Only a certain kind of dependences (all/raw)"),
Tobias Grosser64e8e372014-03-13 23:37:43 +000051 cl::Hidden, cl::init("all"), cl::ZeroOrMore,
52 cl::cat(PollyCategory));
Tobias Grosser1deda292012-02-14 14:02:48 +000053
54static cl::opt<std::string>
Tobias Grossera26db472012-01-30 19:38:43 +000055SimplifyDeps("polly-opt-simplify-deps",
Tobias Grosser4d96c8d2013-03-23 01:05:07 +000056 cl::desc("Dependences should be simplified (yes/no)"), cl::Hidden,
Tobias Grosser64e8e372014-03-13 23:37:43 +000057 cl::init("yes"), cl::ZeroOrMore, cl::cat(PollyCategory));
Tobias Grossera26db472012-01-30 19:38:43 +000058
Tobias Grosser992e60c2012-02-20 08:41:15 +000059static cl::opt<int>
60MaxConstantTerm("polly-opt-max-constant-term",
61 cl::desc("The maximal constant term allowed (-1 is unlimited)"),
Tobias Grosser64e8e372014-03-13 23:37:43 +000062 cl::Hidden, cl::init(20), cl::ZeroOrMore,
63 cl::cat(PollyCategory));
Tobias Grosser992e60c2012-02-20 08:41:15 +000064
Tobias Grosser92f54802012-02-20 08:41:47 +000065static cl::opt<int>
66MaxCoefficient("polly-opt-max-coefficient",
67 cl::desc("The maximal coefficient allowed (-1 is unlimited)"),
Tobias Grosser64e8e372014-03-13 23:37:43 +000068 cl::Hidden, cl::init(20), cl::ZeroOrMore,
69 cl::cat(PollyCategory));
Tobias Grosser92f54802012-02-20 08:41:47 +000070
Tobias Grossere602a072013-05-07 07:30:56 +000071static cl::opt<std::string>
72FusionStrategy("polly-opt-fusion",
73 cl::desc("The fusion strategy to choose (min/max)"), cl::Hidden,
Tobias Grosser64e8e372014-03-13 23:37:43 +000074 cl::init("min"), cl::ZeroOrMore, cl::cat(PollyCategory));
Tobias Grosserb3ad85b2012-01-30 19:38:50 +000075
Tobias Grossere602a072013-05-07 07:30:56 +000076static cl::opt<std::string>
77MaximizeBandDepth("polly-opt-maximize-bands",
78 cl::desc("Maximize the band depth (yes/no)"), cl::Hidden,
Tobias Grosser64e8e372014-03-13 23:37:43 +000079 cl::init("yes"), cl::ZeroOrMore, cl::cat(PollyCategory));
Tobias Grosser95e860c2012-01-30 19:38:54 +000080
Tobias Grosser30aa24c2011-05-14 19:02:06 +000081namespace {
82
Tobias Grosser4d96c8d2013-03-23 01:05:07 +000083class IslScheduleOptimizer : public ScopPass {
Tobias Grosser30aa24c2011-05-14 19:02:06 +000084
Tobias Grosser4d96c8d2013-03-23 01:05:07 +000085public:
86 static char ID;
87 explicit IslScheduleOptimizer() : ScopPass(ID) { LastSchedule = NULL; }
Tobias Grosser28781422012-10-16 07:29:19 +000088
Tobias Grosser4d96c8d2013-03-23 01:05:07 +000089 ~IslScheduleOptimizer() { isl_schedule_free(LastSchedule); }
Tobias Grosser30aa24c2011-05-14 19:02:06 +000090
Tobias Grosser4d96c8d2013-03-23 01:05:07 +000091 virtual bool runOnScop(Scop &S);
92 void printScop(llvm::raw_ostream &OS) const;
93 void getAnalysisUsage(AnalysisUsage &AU) const;
Tobias Grosser460e9a42012-04-25 13:22:43 +000094
Tobias Grosser4d96c8d2013-03-23 01:05:07 +000095private:
96 isl_schedule *LastSchedule;
Tobias Grosser28781422012-10-16 07:29:19 +000097
Tobias Grosser4d96c8d2013-03-23 01:05:07 +000098 static void extendScattering(Scop &S, unsigned NewDimensions);
Tobias Grosser460e9a42012-04-25 13:22:43 +000099
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000100 /// @brief Create a map that describes a n-dimensonal tiling.
101 ///
102 /// getTileMap creates a map from a n-dimensional scattering space into an
103 /// 2*n-dimensional scattering space. The map describes a rectangular
104 /// tiling.
105 ///
106 /// Example:
107 /// scheduleDimensions = 2, parameterDimensions = 1, tileSize = 32
108 ///
109 /// tileMap := [p0] -> {[s0, s1] -> [t0, t1, s0, s1]:
110 /// t0 % 32 = 0 and t0 <= s0 < t0 + 32 and
111 /// t1 % 32 = 0 and t1 <= s1 < t1 + 32}
112 ///
113 /// Before tiling:
114 ///
115 /// for (i = 0; i < N; i++)
116 /// for (j = 0; j < M; j++)
117 /// S(i,j)
118 ///
119 /// After tiling:
120 ///
121 /// for (t_i = 0; t_i < N; i+=32)
122 /// for (t_j = 0; t_j < M; j+=32)
123 /// for (i = t_i; i < min(t_i + 32, N); i++) | Unknown that N % 32 = 0
124 /// for (j = t_j; j < t_j + 32; j++) | Known that M % 32 = 0
125 /// S(i,j)
126 ///
127 static isl_basic_map *getTileMap(isl_ctx *ctx, int scheduleDimensions,
128 isl_space *SpaceModel, int tileSize = 32);
Tobias Grosser460e9a42012-04-25 13:22:43 +0000129
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000130 /// @brief Get the schedule for this band.
131 ///
132 /// Polly applies transformations like tiling on top of the isl calculated
133 /// value. This can influence the number of scheduling dimension. The
134 /// number of schedule dimensions is returned in the parameter 'Dimension'.
135 static isl_union_map *getScheduleForBand(isl_band *Band, int *Dimensions);
Tobias Grosser460e9a42012-04-25 13:22:43 +0000136
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000137 /// @brief Create a map that pre-vectorizes one scheduling dimension.
138 ///
139 /// getPrevectorMap creates a map that maps each input dimension to the same
140 /// output dimension, except for the dimension DimToVectorize.
141 /// DimToVectorize is strip mined by 'VectorWidth' and the newly created
142 /// point loop of DimToVectorize is moved to the innermost level.
143 ///
144 /// Example (DimToVectorize=0, ScheduleDimensions=2, VectorWidth=4):
145 ///
146 /// | Before transformation
147 /// |
148 /// | A[i,j] -> [i,j]
149 /// |
150 /// | for (i = 0; i < 128; i++)
151 /// | for (j = 0; j < 128; j++)
152 /// | A(i,j);
153 ///
154 /// Prevector map:
155 /// [i,j] -> [it,j,ip] : it % 4 = 0 and it <= ip <= it + 3 and i = ip
156 ///
157 /// | After transformation:
158 /// |
159 /// | A[i,j] -> [it,j,ip] : it % 4 = 0 and it <= ip <= it + 3 and i = ip
160 /// |
161 /// | for (it = 0; it < 128; it+=4)
162 /// | for (j = 0; j < 128; j++)
163 /// | for (ip = max(0,it); ip < min(128, it + 3); ip++)
164 /// | A(ip,j);
165 ///
166 /// The goal of this transformation is to create a trivially vectorizable
167 /// loop. This means a parallel loop at the innermost level that has a
168 /// constant number of iterations corresponding to the target vector width.
169 ///
170 /// This transformation creates a loop at the innermost level. The loop has
171 /// a constant number of iterations, if the number of loop iterations at
172 /// DimToVectorize can be divided by VectorWidth. The default VectorWidth is
173 /// currently constant and not yet target specific. This function does not
174 /// reason about parallelism.
175 static isl_map *getPrevectorMap(isl_ctx *ctx, int DimToVectorize,
176 int ScheduleDimensions, int VectorWidth = 4);
Tobias Grosser460e9a42012-04-25 13:22:43 +0000177
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000178 /// @brief Get the scheduling map for a list of bands.
179 ///
180 /// Walk recursively the forest of bands to combine the schedules of the
181 /// individual bands to the overall schedule. In case tiling is requested,
182 /// the individual bands are tiled.
183 static isl_union_map *getScheduleForBandList(isl_band_list *BandList);
Tobias Grosser460e9a42012-04-25 13:22:43 +0000184
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000185 static isl_union_map *getScheduleMap(isl_schedule *Schedule);
Tobias Grosser28781422012-10-16 07:29:19 +0000186
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000187 bool doFinalization() {
188 isl_schedule_free(LastSchedule);
189 LastSchedule = NULL;
190 return true;
191 }
192};
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000193}
194
Tobias Grosser73600b82011-10-08 00:30:40 +0000195char IslScheduleOptimizer::ID = 0;
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000196
Tobias Grosser460e9a42012-04-25 13:22:43 +0000197void IslScheduleOptimizer::extendScattering(Scop &S, unsigned NewDimensions) {
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000198 for (Scop::iterator SI = S.begin(), SE = S.end(); SI != SE; ++SI) {
Tobias Grossercf3942d2011-10-06 00:04:05 +0000199 ScopStmt *Stmt = *SI;
Tobias Grossercf3942d2011-10-06 00:04:05 +0000200 unsigned OldDimensions = Stmt->getNumScattering();
201 isl_space *Space;
Tobias Grosser29666112012-05-22 10:47:31 +0000202 isl_map *Map, *New;
Tobias Grossercf3942d2011-10-06 00:04:05 +0000203
204 Space = isl_space_alloc(Stmt->getIslCtx(), 0, OldDimensions, NewDimensions);
Tobias Grosser29666112012-05-22 10:47:31 +0000205 Map = isl_map_universe(Space);
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000206
Tobias Grosser29666112012-05-22 10:47:31 +0000207 for (unsigned i = 0; i < OldDimensions; i++)
208 Map = isl_map_equate(Map, isl_dim_in, i, isl_dim_out, i);
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000209
Tobias Grosser29666112012-05-22 10:47:31 +0000210 for (unsigned i = OldDimensions; i < NewDimensions; i++)
211 Map = isl_map_fix_si(Map, isl_dim_out, i, 0);
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000212
Tobias Grosser29666112012-05-22 10:47:31 +0000213 Map = isl_map_align_params(Map, S.getParamSpace());
214 New = isl_map_apply_range(Stmt->getScattering(), Map);
215 Stmt->setScattering(New);
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000216 }
217}
218
Tobias Grossere602a072013-05-07 07:30:56 +0000219isl_basic_map *IslScheduleOptimizer::getTileMap(isl_ctx *ctx,
220 int scheduleDimensions,
221 isl_space *SpaceModel,
222 int tileSize) {
Tobias Grosserde68cc92011-06-30 20:01:02 +0000223 // We construct
224 //
225 // tileMap := [p0] -> {[s0, s1] -> [t0, t1, p0, p1, a0, a1]:
226 // s0 = a0 * 32 and s0 = p0 and t0 <= p0 < t0 + 32 and
227 // s1 = a1 * 32 and s1 = p1 and t1 <= p1 < t1 + 32}
228 //
229 // and project out the auxilary dimensions a0 and a1.
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000230 isl_space *Space =
231 isl_space_alloc(ctx, 0, scheduleDimensions, scheduleDimensions * 3);
Tobias Grosserf5338802011-10-06 00:03:35 +0000232 isl_basic_map *tileMap = isl_basic_map_universe(isl_space_copy(Space));
233
234 isl_local_space *LocalSpace = isl_local_space_from_space(Space);
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000235
Tobias Grosserde68cc92011-06-30 20:01:02 +0000236 for (int x = 0; x < scheduleDimensions; x++) {
237 int sX = x;
238 int tX = x;
239 int pX = scheduleDimensions + x;
240 int aX = 2 * scheduleDimensions + x;
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000241
Tobias Grosserde68cc92011-06-30 20:01:02 +0000242 isl_constraint *c;
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000243
Tobias Grosserde68cc92011-06-30 20:01:02 +0000244 // sX = aX * tileSize;
Tobias Grosserf5338802011-10-06 00:03:35 +0000245 c = isl_equality_alloc(isl_local_space_copy(LocalSpace));
Tobias Grosserde68cc92011-06-30 20:01:02 +0000246 isl_constraint_set_coefficient_si(c, isl_dim_out, sX, 1);
247 isl_constraint_set_coefficient_si(c, isl_dim_out, aX, -tileSize);
248 tileMap = isl_basic_map_add_constraint(tileMap, c);
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000249
Tobias Grosserde68cc92011-06-30 20:01:02 +0000250 // pX = sX;
Tobias Grosserf5338802011-10-06 00:03:35 +0000251 c = isl_equality_alloc(isl_local_space_copy(LocalSpace));
Tobias Grosserde68cc92011-06-30 20:01:02 +0000252 isl_constraint_set_coefficient_si(c, isl_dim_out, pX, 1);
253 isl_constraint_set_coefficient_si(c, isl_dim_in, sX, -1);
254 tileMap = isl_basic_map_add_constraint(tileMap, c);
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000255
Tobias Grosserde68cc92011-06-30 20:01:02 +0000256 // tX <= pX
Tobias Grosserf5338802011-10-06 00:03:35 +0000257 c = isl_inequality_alloc(isl_local_space_copy(LocalSpace));
Tobias Grosserde68cc92011-06-30 20:01:02 +0000258 isl_constraint_set_coefficient_si(c, isl_dim_out, pX, 1);
259 isl_constraint_set_coefficient_si(c, isl_dim_out, tX, -1);
260 tileMap = isl_basic_map_add_constraint(tileMap, c);
261
262 // pX <= tX + (tileSize - 1)
Tobias Grosserf5338802011-10-06 00:03:35 +0000263 c = isl_inequality_alloc(isl_local_space_copy(LocalSpace));
Tobias Grosserde68cc92011-06-30 20:01:02 +0000264 isl_constraint_set_coefficient_si(c, isl_dim_out, tX, 1);
265 isl_constraint_set_coefficient_si(c, isl_dim_out, pX, -1);
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000266 isl_constraint_set_constant_si(c, tileSize - 1);
Tobias Grosserde68cc92011-06-30 20:01:02 +0000267 tileMap = isl_basic_map_add_constraint(tileMap, c);
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000268 }
269
Tobias Grosserde68cc92011-06-30 20:01:02 +0000270 // Project out auxilary dimensions.
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000271 //
Tobias Grosserde68cc92011-06-30 20:01:02 +0000272 // The auxilary dimensions are transformed into existentially quantified ones.
273 // This reduces the number of visible scattering dimensions and allows Cloog
274 // to produces better code.
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000275 tileMap = isl_basic_map_project_out(
276 tileMap, isl_dim_out, 2 * scheduleDimensions, scheduleDimensions);
Tobias Grosserf5338802011-10-06 00:03:35 +0000277 isl_local_space_free(LocalSpace);
Tobias Grosserde68cc92011-06-30 20:01:02 +0000278 return tileMap;
279}
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000280
Tobias Grossere602a072013-05-07 07:30:56 +0000281isl_union_map *IslScheduleOptimizer::getScheduleForBand(isl_band *Band,
282 int *Dimensions) {
Tobias Grosser1ae9a602011-11-17 12:56:03 +0000283 isl_union_map *PartialSchedule;
Tobias Grosserde68cc92011-06-30 20:01:02 +0000284 isl_ctx *ctx;
Tobias Grosserf5338802011-10-06 00:03:35 +0000285 isl_space *Space;
Tobias Grosser1ae9a602011-11-17 12:56:03 +0000286 isl_basic_map *TileMap;
287 isl_union_map *TileUMap;
Tobias Grosserde68cc92011-06-30 20:01:02 +0000288
Tobias Grosser1ae9a602011-11-17 12:56:03 +0000289 PartialSchedule = isl_band_get_partial_schedule(Band);
Tobias Grosserb6033392011-12-08 13:02:58 +0000290 *Dimensions = isl_band_n_member(Band);
Tobias Grosserde68cc92011-06-30 20:01:02 +0000291
Tobias Grosser79b30202011-11-17 12:56:00 +0000292 if (DisableTiling)
Tobias Grosser1ae9a602011-11-17 12:56:03 +0000293 return PartialSchedule;
Tobias Grosser353a2682011-10-23 20:59:26 +0000294
Tobias Grosserb6033392011-12-08 13:02:58 +0000295 // It does not make any sense to tile a band with just one dimension.
296 if (*Dimensions == 1)
297 return PartialSchedule;
298
Tobias Grosser1ae9a602011-11-17 12:56:03 +0000299 ctx = isl_union_map_get_ctx(PartialSchedule);
300 Space = isl_union_map_get_space(PartialSchedule);
Tobias Grosserde68cc92011-06-30 20:01:02 +0000301
Tobias Grosserb6033392011-12-08 13:02:58 +0000302 TileMap = getTileMap(ctx, *Dimensions, Space);
Tobias Grosser1ae9a602011-11-17 12:56:03 +0000303 TileUMap = isl_union_map_from_map(isl_map_from_basic_map(TileMap));
304 TileUMap = isl_union_map_align_params(TileUMap, Space);
Tobias Grosserb6033392011-12-08 13:02:58 +0000305 *Dimensions = 2 * *Dimensions;
306
Tobias Grosser1ae9a602011-11-17 12:56:03 +0000307 return isl_union_map_apply_range(PartialSchedule, TileUMap);
Tobias Grosserde68cc92011-06-30 20:01:02 +0000308}
309
Tobias Grossere602a072013-05-07 07:30:56 +0000310isl_map *IslScheduleOptimizer::getPrevectorMap(isl_ctx *ctx, int DimToVectorize,
311 int ScheduleDimensions,
312 int VectorWidth) {
Tobias Grosser2493e922011-12-07 07:42:57 +0000313 isl_space *Space;
314 isl_local_space *LocalSpace, *LocalSpaceRange;
315 isl_set *Modulo;
316 isl_map *TilingMap;
Tobias Grosserc6699b72011-06-30 20:29:13 +0000317 isl_constraint *c;
Tobias Grosser2493e922011-12-07 07:42:57 +0000318 isl_aff *Aff;
319 int PointDimension; /* ip */
320 int TileDimension; /* it */
Tobias Grosseredab1352013-06-21 06:41:31 +0000321 isl_val *VectorWidthMP;
Tobias Grosserc6699b72011-06-30 20:29:13 +0000322
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000323 assert(0 <= DimToVectorize && DimToVectorize < ScheduleDimensions);
Tobias Grosserf5338802011-10-06 00:03:35 +0000324
Tobias Grosser2493e922011-12-07 07:42:57 +0000325 Space = isl_space_alloc(ctx, 0, ScheduleDimensions, ScheduleDimensions + 1);
326 TilingMap = isl_map_universe(isl_space_copy(Space));
327 LocalSpace = isl_local_space_from_space(Space);
328 PointDimension = ScheduleDimensions;
329 TileDimension = DimToVectorize;
330
331 // Create an identity map for everything except DimToVectorize and map
332 // DimToVectorize to the point loop at the innermost dimension.
333 for (int i = 0; i < ScheduleDimensions; i++) {
Tobias Grosserf5338802011-10-06 00:03:35 +0000334 c = isl_equality_alloc(isl_local_space_copy(LocalSpace));
Tobias Grosserc6699b72011-06-30 20:29:13 +0000335 isl_constraint_set_coefficient_si(c, isl_dim_in, i, -1);
Tobias Grosser2493e922011-12-07 07:42:57 +0000336
337 if (i == DimToVectorize)
338 isl_constraint_set_coefficient_si(c, isl_dim_out, PointDimension, 1);
339 else
340 isl_constraint_set_coefficient_si(c, isl_dim_out, i, 1);
341
342 TilingMap = isl_map_add_constraint(TilingMap, c);
Tobias Grosserc6699b72011-06-30 20:29:13 +0000343 }
344
Tobias Grosser2493e922011-12-07 07:42:57 +0000345 // it % 'VectorWidth' = 0
346 LocalSpaceRange = isl_local_space_range(isl_local_space_copy(LocalSpace));
347 Aff = isl_aff_zero_on_domain(LocalSpaceRange);
348 Aff = isl_aff_set_constant_si(Aff, VectorWidth);
349 Aff = isl_aff_set_coefficient_si(Aff, isl_dim_in, TileDimension, 1);
Tobias Grosseredab1352013-06-21 06:41:31 +0000350 VectorWidthMP = isl_val_int_from_si(ctx, VectorWidth);
351 Aff = isl_aff_mod_val(Aff, VectorWidthMP);
Tobias Grosser2493e922011-12-07 07:42:57 +0000352 Modulo = isl_pw_aff_zero_set(isl_pw_aff_from_aff(Aff));
353 TilingMap = isl_map_intersect_range(TilingMap, Modulo);
Tobias Grosserc6699b72011-06-30 20:29:13 +0000354
Tobias Grosser2493e922011-12-07 07:42:57 +0000355 // it <= ip
Tobias Grosserf5338802011-10-06 00:03:35 +0000356 c = isl_inequality_alloc(isl_local_space_copy(LocalSpace));
Tobias Grosser2493e922011-12-07 07:42:57 +0000357 isl_constraint_set_coefficient_si(c, isl_dim_out, TileDimension, -1);
358 isl_constraint_set_coefficient_si(c, isl_dim_out, PointDimension, 1);
359 TilingMap = isl_map_add_constraint(TilingMap, c);
Tobias Grosserc6699b72011-06-30 20:29:13 +0000360
Tobias Grosser2493e922011-12-07 07:42:57 +0000361 // ip <= it + ('VectorWidth' - 1)
Tobias Grosserf5338802011-10-06 00:03:35 +0000362 c = isl_inequality_alloc(LocalSpace);
Tobias Grosser2493e922011-12-07 07:42:57 +0000363 isl_constraint_set_coefficient_si(c, isl_dim_out, TileDimension, 1);
364 isl_constraint_set_coefficient_si(c, isl_dim_out, PointDimension, -1);
365 isl_constraint_set_constant_si(c, VectorWidth - 1);
366 TilingMap = isl_map_add_constraint(TilingMap, c);
Tobias Grosserc6699b72011-06-30 20:29:13 +0000367
Tobias Grosser2493e922011-12-07 07:42:57 +0000368 return TilingMap;
Tobias Grosserc6699b72011-06-30 20:29:13 +0000369}
370
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000371isl_union_map *
372IslScheduleOptimizer::getScheduleForBandList(isl_band_list *BandList) {
Tobias Grosser1ae9a602011-11-17 12:56:03 +0000373 int NumBands;
374 isl_union_map *Schedule;
375 isl_ctx *ctx;
Tobias Grosserde68cc92011-06-30 20:01:02 +0000376
Tobias Grosser1ae9a602011-11-17 12:56:03 +0000377 ctx = isl_band_list_get_ctx(BandList);
378 NumBands = isl_band_list_n_band(BandList);
Tobias Grosser62872012011-11-17 12:56:04 +0000379 Schedule = isl_union_map_empty(isl_space_params_alloc(ctx, 0));
Tobias Grosserde68cc92011-06-30 20:01:02 +0000380
Tobias Grosser1ae9a602011-11-17 12:56:03 +0000381 for (int i = 0; i < NumBands; i++) {
382 isl_band *Band;
383 isl_union_map *PartialSchedule;
384 int ScheduleDimensions;
385 isl_space *Space;
Tobias Grosser44f19ac2011-07-05 22:15:53 +0000386
Tobias Grosser1ae9a602011-11-17 12:56:03 +0000387 Band = isl_band_list_get_band(BandList, i);
Tobias Grosserb6033392011-12-08 13:02:58 +0000388 PartialSchedule = getScheduleForBand(Band, &ScheduleDimensions);
Tobias Grosser1ae9a602011-11-17 12:56:03 +0000389 Space = isl_union_map_get_space(PartialSchedule);
Tobias Grosserde68cc92011-06-30 20:01:02 +0000390
Tobias Grosser1ae9a602011-11-17 12:56:03 +0000391 if (isl_band_has_children(Band)) {
392 isl_band_list *Children;
393 isl_union_map *SuffixSchedule;
394
395 Children = isl_band_get_children(Band);
396 SuffixSchedule = getScheduleForBandList(Children);
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000397 PartialSchedule =
398 isl_union_map_flat_range_product(PartialSchedule, SuffixSchedule);
Tobias Grosser1ae9a602011-11-17 12:56:03 +0000399 isl_band_list_free(Children);
Hongbin Zheng68794212012-05-06 10:22:19 +0000400 } else if (PollyVectorizerChoice != VECTORIZER_NONE) {
Tobias Grosser4ba60fe2014-03-11 06:27:36 +0000401 // In case we are at the innermost band, we try to prepare for
402 // vectorization. This means, we look for the innermost parallel loop
403 // and strip mine this loop to the innermost level using a strip-mine
404 // factor corresponding to the number of vector iterations.
405 int NumDims = isl_band_n_member(Band);
406 for (int j = NumDims - 1; j >= 0; j--) {
Tobias Grossera38c9242014-01-26 19:36:28 +0000407 if (isl_band_member_is_coincident(Band, j)) {
Tobias Grosser1ae9a602011-11-17 12:56:03 +0000408 isl_map *TileMap;
409 isl_union_map *TileUMap;
Tobias Grosserc6699b72011-06-30 20:29:13 +0000410
Tobias Grosser4ba60fe2014-03-11 06:27:36 +0000411 TileMap = getPrevectorMap(ctx, ScheduleDimensions - NumDims + j,
Tobias Grosser216ea582012-04-16 11:06:06 +0000412 ScheduleDimensions);
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000413 TileUMap = isl_union_map_from_map(TileMap);
414 TileUMap =
415 isl_union_map_align_params(TileUMap, isl_space_copy(Space));
416 PartialSchedule =
417 isl_union_map_apply_range(PartialSchedule, TileUMap);
418 break;
419 }
Tobias Grosser7c5ba832011-06-30 20:29:20 +0000420 }
Tobias Grosserde68cc92011-06-30 20:01:02 +0000421 }
422
Tobias Grosser62872012011-11-17 12:56:04 +0000423 Schedule = isl_union_map_union(Schedule, PartialSchedule);
Tobias Grosserde68cc92011-06-30 20:01:02 +0000424
Tobias Grosser1ae9a602011-11-17 12:56:03 +0000425 isl_band_free(Band);
Tobias Grosserf5338802011-10-06 00:03:35 +0000426 isl_space_free(Space);
Tobias Grosserde68cc92011-06-30 20:01:02 +0000427 }
428
Tobias Grosser1ae9a602011-11-17 12:56:03 +0000429 return Schedule;
Tobias Grosserde68cc92011-06-30 20:01:02 +0000430}
431
Tobias Grosser460e9a42012-04-25 13:22:43 +0000432isl_union_map *IslScheduleOptimizer::getScheduleMap(isl_schedule *Schedule) {
Tobias Grosser1ae9a602011-11-17 12:56:03 +0000433 isl_band_list *BandList = isl_schedule_get_band_forest(Schedule);
434 isl_union_map *ScheduleMap = getScheduleForBandList(BandList);
435 isl_band_list_free(BandList);
436 return ScheduleMap;
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000437}
438
Tobias Grosser73600b82011-10-08 00:30:40 +0000439bool IslScheduleOptimizer::runOnScop(Scop &S) {
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000440 Dependences *D = &getAnalysis<Dependences>();
441
Tobias Grosser38c36ea2014-02-23 15:15:44 +0000442 if (!D->hasValidDependences())
443 return false;
444
Tobias Grosser28781422012-10-16 07:29:19 +0000445 isl_schedule_free(LastSchedule);
446 LastSchedule = NULL;
447
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000448 // Build input data.
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000449 int ValidityKinds =
450 Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;
Tobias Grosser1deda292012-02-14 14:02:48 +0000451 int ProximityKinds;
452
453 if (OptimizeDeps == "all")
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000454 ProximityKinds =
455 Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;
Tobias Grosser1deda292012-02-14 14:02:48 +0000456 else if (OptimizeDeps == "raw")
Tobias Grosser1e03ad72012-02-15 09:58:42 +0000457 ProximityKinds = Dependences::TYPE_RAW;
Tobias Grosser1deda292012-02-14 14:02:48 +0000458 else {
459 errs() << "Do not know how to optimize for '" << OptimizeDeps << "'"
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000460 << " Falling back to optimizing all dependences.\n";
461 ProximityKinds =
462 Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;
Tobias Grosser1deda292012-02-14 14:02:48 +0000463 }
464
Tobias Grosser5f9a7622012-02-14 14:02:40 +0000465 isl_union_set *Domain = S.getDomains();
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000466
Tobias Grosser98610ee2012-02-13 23:31:39 +0000467 if (!Domain)
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000468 return false;
469
Tobias Grosser8a507022012-03-16 11:51:41 +0000470 isl_union_map *Validity = D->getDependences(ValidityKinds);
471 isl_union_map *Proximity = D->getDependences(ProximityKinds);
472
Tobias Grossera26db472012-01-30 19:38:43 +0000473 // Simplify the dependences by removing the constraints introduced by the
474 // domains. This can speed up the scheduling time significantly, as large
475 // constant coefficients will be removed from the dependences. The
476 // introduction of some additional dependences reduces the possible
477 // transformations, but in most cases, such transformation do not seem to be
478 // interesting anyway. In some cases this option may stop the scheduler to
479 // find any schedule.
480 if (SimplifyDeps == "yes") {
Tobias Grosser00383a72012-02-14 14:02:44 +0000481 Validity = isl_union_map_gist_domain(Validity, isl_union_set_copy(Domain));
482 Validity = isl_union_map_gist_range(Validity, isl_union_set_copy(Domain));
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000483 Proximity =
484 isl_union_map_gist_domain(Proximity, isl_union_set_copy(Domain));
Tobias Grosser00383a72012-02-14 14:02:44 +0000485 Proximity = isl_union_map_gist_range(Proximity, isl_union_set_copy(Domain));
Tobias Grossera26db472012-01-30 19:38:43 +0000486 } else if (SimplifyDeps != "no") {
487 errs() << "warning: Option -polly-opt-simplify-deps should either be 'yes' "
488 "or 'no'. Falling back to default: 'yes'\n";
489 }
490
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000491 DEBUG(dbgs() << "\n\nCompute schedule from: ");
Tobias Grosser98610ee2012-02-13 23:31:39 +0000492 DEBUG(dbgs() << "Domain := "; isl_union_set_dump(Domain); dbgs() << ";\n");
493 DEBUG(dbgs() << "Proximity := "; isl_union_map_dump(Proximity);
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000494 dbgs() << ";\n");
Tobias Grosser98610ee2012-02-13 23:31:39 +0000495 DEBUG(dbgs() << "Validity := "; isl_union_map_dump(Validity);
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000496 dbgs() << ";\n");
497
Tobias Grosserb3ad85b2012-01-30 19:38:50 +0000498 int IslFusionStrategy;
499
500 if (FusionStrategy == "max") {
501 IslFusionStrategy = ISL_SCHEDULE_FUSE_MAX;
502 } else if (FusionStrategy == "min") {
503 IslFusionStrategy = ISL_SCHEDULE_FUSE_MIN;
504 } else {
505 errs() << "warning: Unknown fusion strategy. Falling back to maximal "
506 "fusion.\n";
507 IslFusionStrategy = ISL_SCHEDULE_FUSE_MAX;
508 }
509
Tobias Grosser95e860c2012-01-30 19:38:54 +0000510 int IslMaximizeBands;
511
Tobias Grossera4ea90b2012-01-30 22:43:56 +0000512 if (MaximizeBandDepth == "yes") {
Tobias Grosser95e860c2012-01-30 19:38:54 +0000513 IslMaximizeBands = 1;
Tobias Grossera4ea90b2012-01-30 22:43:56 +0000514 } else if (MaximizeBandDepth == "no") {
Tobias Grosser95e860c2012-01-30 19:38:54 +0000515 IslMaximizeBands = 0;
516 } else {
517 errs() << "warning: Option -polly-opt-maximize-bands should either be 'yes'"
518 " or 'no'. Falling back to default: 'yes'\n";
519 IslMaximizeBands = 1;
520 }
521
Tobias Grosserb3ad85b2012-01-30 19:38:50 +0000522 isl_options_set_schedule_fuse(S.getIslCtx(), IslFusionStrategy);
Tobias Grosser95e860c2012-01-30 19:38:54 +0000523 isl_options_set_schedule_maximize_band_depth(S.getIslCtx(), IslMaximizeBands);
Tobias Grosser992e60c2012-02-20 08:41:15 +0000524 isl_options_set_schedule_max_constant_term(S.getIslCtx(), MaxConstantTerm);
Tobias Grosser92f54802012-02-20 08:41:47 +0000525 isl_options_set_schedule_max_coefficient(S.getIslCtx(), MaxCoefficient);
Tobias Grosser42152ff2012-01-30 19:38:47 +0000526
527 isl_options_set_on_error(S.getIslCtx(), ISL_ON_ERROR_CONTINUE);
Tobias Grossera38c9242014-01-26 19:36:28 +0000528
529 isl_schedule_constraints *ScheduleConstraints;
530 ScheduleConstraints = isl_schedule_constraints_on_domain(Domain);
531 ScheduleConstraints =
532 isl_schedule_constraints_set_proximity(ScheduleConstraints, Proximity);
533 ScheduleConstraints = isl_schedule_constraints_set_validity(
534 ScheduleConstraints, isl_union_map_copy(Validity));
535 ScheduleConstraints =
536 isl_schedule_constraints_set_coincidence(ScheduleConstraints, Validity);
Tobias Grosser00383a72012-02-14 14:02:44 +0000537 isl_schedule *Schedule;
Tobias Grossera38c9242014-01-26 19:36:28 +0000538 Schedule = isl_schedule_constraints_compute_schedule(ScheduleConstraints);
Tobias Grosser42152ff2012-01-30 19:38:47 +0000539 isl_options_set_on_error(S.getIslCtx(), ISL_ON_ERROR_ABORT);
540
541 // In cases the scheduler is not able to optimize the code, we just do not
542 // touch the schedule.
Tobias Grosser98610ee2012-02-13 23:31:39 +0000543 if (!Schedule)
Tobias Grosser42152ff2012-01-30 19:38:47 +0000544 return false;
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000545
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000546 DEBUG(dbgs() << "Schedule := "; isl_schedule_dump(Schedule); dbgs() << ";\n");
Tobias Grosser4d63b9d2012-02-20 08:41:21 +0000547
Tobias Grosser98610ee2012-02-13 23:31:39 +0000548 isl_union_map *ScheduleMap = getScheduleMap(Schedule);
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000549
Tobias Grosserde68cc92011-06-30 20:01:02 +0000550 for (Scop::iterator SI = S.begin(), SE = S.end(); SI != SE; ++SI) {
Tobias Grosser98610ee2012-02-13 23:31:39 +0000551 ScopStmt *Stmt = *SI;
Tobias Grosser249c4b12013-04-11 05:55:13 +0000552 isl_map *StmtSchedule;
Tobias Grosser98610ee2012-02-13 23:31:39 +0000553 isl_set *Domain = Stmt->getDomain();
554 isl_union_map *StmtBand;
555 StmtBand = isl_union_map_intersect_domain(isl_union_map_copy(ScheduleMap),
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000556 isl_union_set_from_set(Domain));
Tobias Grosser249c4b12013-04-11 05:55:13 +0000557 if (isl_union_map_is_empty(StmtBand)) {
Tobias Grosser34f06132014-02-21 20:51:36 +0000558 StmtSchedule = isl_map_from_domain(isl_set_empty(Stmt->getDomainSpace()));
Tobias Grosser249c4b12013-04-11 05:55:13 +0000559 isl_union_map_free(StmtBand);
560 } else {
561 assert(isl_union_map_n_map(StmtBand) == 1);
562 StmtSchedule = isl_map_from_union_map(StmtBand);
Tobias Grosserf242b802013-04-10 22:48:08 +0000563 }
564
Tobias Grosser98610ee2012-02-13 23:31:39 +0000565 Stmt->setScattering(StmtSchedule);
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000566 }
567
Tobias Grosser1ae9a602011-11-17 12:56:03 +0000568 isl_union_map_free(ScheduleMap);
Tobias Grosser28781422012-10-16 07:29:19 +0000569 LastSchedule = Schedule;
Tobias Grosserde68cc92011-06-30 20:01:02 +0000570
Tobias Grosser98610ee2012-02-13 23:31:39 +0000571 unsigned MaxScatDims = 0;
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000572
573 for (Scop::iterator SI = S.begin(), SE = S.end(); SI != SE; ++SI)
Tobias Grosser98610ee2012-02-13 23:31:39 +0000574 MaxScatDims = std::max((*SI)->getNumScattering(), MaxScatDims);
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000575
Tobias Grosser98610ee2012-02-13 23:31:39 +0000576 extendScattering(S, MaxScatDims);
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000577 return false;
578}
579
Tobias Grosser73600b82011-10-08 00:30:40 +0000580void IslScheduleOptimizer::printScop(raw_ostream &OS) const {
Tobias Grosser28781422012-10-16 07:29:19 +0000581 isl_printer *p;
582 char *ScheduleStr;
583
584 OS << "Calculated schedule:\n";
585
586 if (!LastSchedule) {
587 OS << "n/a\n";
588 return;
589 }
590
591 p = isl_printer_to_str(isl_schedule_get_ctx(LastSchedule));
592 p = isl_printer_print_schedule(p, LastSchedule);
593 ScheduleStr = isl_printer_get_str(p);
594 isl_printer_free(p);
595
596 OS << ScheduleStr << "\n";
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000597}
598
Tobias Grosser73600b82011-10-08 00:30:40 +0000599void IslScheduleOptimizer::getAnalysisUsage(AnalysisUsage &AU) const {
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000600 ScopPass::getAnalysisUsage(AU);
601 AU.addRequired<Dependences>();
602}
603
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000604Pass *polly::createIslScheduleOptimizerPass() {
Tobias Grosser73600b82011-10-08 00:30:40 +0000605 return new IslScheduleOptimizer();
Tobias Grosser30aa24c2011-05-14 19:02:06 +0000606}
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000607
608INITIALIZE_PASS_BEGIN(IslScheduleOptimizer, "polly-opt-isl",
609 "Polly - Optimize schedule of SCoP", false, false);
610INITIALIZE_PASS_DEPENDENCY(Dependences);
611INITIALIZE_PASS_DEPENDENCY(ScopInfo);
612INITIALIZE_PASS_END(IslScheduleOptimizer, "polly-opt-isl",
613 "Polly - Optimize schedule of SCoP", false, false)