1 //===- Schedule.cpp - Calculate an optimized schedule ---------------------===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // This pass generates an entirely new schedule tree from the data dependences
10 // and iteration domains. The new schedule tree is computed in two steps:
12 // 1) The isl scheduling optimizer is run
14 // The isl scheduling optimizer creates a new schedule tree that maximizes
15 // parallelism and tileability and minimizes data-dependence distances. The
16 // algorithm used is a modified version of the ``Pluto'' algorithm:
18 // U. Bondhugula, A. Hartono, J. Ramanujam, and P. Sadayappan.
19 // A Practical Automatic Polyhedral Parallelizer and Locality Optimizer.
20 // In Proceedings of the 2008 ACM SIGPLAN Conference On Programming Language
21 // Design and Implementation, PLDI ’08, pages 101–113. ACM, 2008.
23 // 2) A set of post-scheduling transformations is applied on the schedule tree.
25 // These optimizations include:
27 // - Tiling of the innermost tilable bands
28 // - Prevectorization - The choice of a possible outer loop that is strip-mined
29 // to the innermost level to enable inner-loop
31 // - Some optimizations for spatial locality are also planned.
33 // For a detailed description of the schedule tree itself please see section 6
36 // Polyhedral AST generation is more than scanning polyhedra
37 // Tobias Grosser, Sven Verdoolaege, Albert Cohen
38 // ACM Transactions on Programming Languages and Systems (TOPLAS),
40 // http://www.grosser.es/#pub-polyhedral-AST-generation
42 // This publication also contains a detailed discussion of the different options
43 // for polyhedral loop unrolling, full/partial tile separation and other uses
44 // of the schedule tree.
46 //===----------------------------------------------------------------------===//
48 #include "polly/ScheduleOptimizer.h"
49 #include "polly/CodeGen/CodeGeneration.h"
50 #include "polly/DependenceInfo.h"
51 #include "polly/LinkAllPasses.h"
52 #include "polly/Options.h"
53 #include "polly/ScheduleTreeTransform.h"
54 #include "polly/ScopInfo.h"
55 #include "polly/ScopPass.h"
56 #include "polly/Simplify.h"
57 #include "polly/Support/ISLOStream.h"
58 #include "llvm/ADT/Statistic.h"
59 #include "llvm/Analysis/TargetTransformInfo.h"
60 #include "llvm/IR/Function.h"
61 #include "llvm/Support/CommandLine.h"
62 #include "llvm/Support/Debug.h"
63 #include "llvm/Support/raw_ostream.h"
65 #include "isl/options.h"
66 #include "isl/printer.h"
67 #include "isl/schedule.h"
68 #include "isl/schedule_node.h"
69 #include "isl/union_map.h"
70 #include "isl/union_set.h"
80 using namespace polly
;
82 #define DEBUG_TYPE "polly-opt-isl"
84 static cl::opt
<std::string
>
85 OptimizeDeps("polly-opt-optimize-only",
86 cl::desc("Only a certain kind of dependences (all/raw)"),
87 cl::Hidden
, cl::init("all"), cl::ZeroOrMore
,
88 cl::cat(PollyCategory
));
90 static cl::opt
<std::string
>
91 SimplifyDeps("polly-opt-simplify-deps",
92 cl::desc("Dependences should be simplified (yes/no)"),
93 cl::Hidden
, cl::init("yes"), cl::ZeroOrMore
,
94 cl::cat(PollyCategory
));
96 static cl::opt
<int> MaxConstantTerm(
97 "polly-opt-max-constant-term",
98 cl::desc("The maximal constant term allowed (-1 is unlimited)"), cl::Hidden
,
99 cl::init(20), cl::ZeroOrMore
, cl::cat(PollyCategory
));
101 static cl::opt
<int> MaxCoefficient(
102 "polly-opt-max-coefficient",
103 cl::desc("The maximal coefficient allowed (-1 is unlimited)"), cl::Hidden
,
104 cl::init(20), cl::ZeroOrMore
, cl::cat(PollyCategory
));
106 static cl::opt
<std::string
> FusionStrategy(
107 "polly-opt-fusion", cl::desc("The fusion strategy to choose (min/max)"),
108 cl::Hidden
, cl::init("min"), cl::ZeroOrMore
, cl::cat(PollyCategory
));
110 static cl::opt
<std::string
>
111 MaximizeBandDepth("polly-opt-maximize-bands",
112 cl::desc("Maximize the band depth (yes/no)"), cl::Hidden
,
113 cl::init("yes"), cl::ZeroOrMore
, cl::cat(PollyCategory
));
115 static cl::opt
<std::string
> OuterCoincidence(
116 "polly-opt-outer-coincidence",
117 cl::desc("Try to construct schedules where the outer member of each band "
118 "satisfies the coincidence constraints (yes/no)"),
119 cl::Hidden
, cl::init("no"), cl::ZeroOrMore
, cl::cat(PollyCategory
));
121 static cl::opt
<int> PrevectorWidth(
122 "polly-prevect-width",
124 "The number of loop iterations to strip-mine for pre-vectorization"),
125 cl::Hidden
, cl::init(4), cl::ZeroOrMore
, cl::cat(PollyCategory
));
127 static cl::opt
<bool> FirstLevelTiling("polly-tiling",
128 cl::desc("Enable loop tiling"),
129 cl::init(true), cl::ZeroOrMore
,
130 cl::cat(PollyCategory
));
132 static cl::opt
<int> LatencyVectorFma(
133 "polly-target-latency-vector-fma",
134 cl::desc("The minimal number of cycles between issuing two "
135 "dependent consecutive vector fused multiply-add "
137 cl::Hidden
, cl::init(8), cl::ZeroOrMore
, cl::cat(PollyCategory
));
139 static cl::opt
<int> ThroughputVectorFma(
140 "polly-target-throughput-vector-fma",
141 cl::desc("A throughput of the processor floating-point arithmetic units "
142 "expressed in the number of vector fused multiply-add "
143 "instructions per clock cycle."),
144 cl::Hidden
, cl::init(1), cl::ZeroOrMore
, cl::cat(PollyCategory
));
146 // This option, along with --polly-target-2nd-cache-level-associativity,
147 // --polly-target-1st-cache-level-size, and --polly-target-2st-cache-level-size
148 // represent the parameters of the target cache, which do not have typical
149 // values that can be used by default. However, to apply the pattern matching
150 // optimizations, we use the values of the parameters of Intel Core i7-3820
151 // SandyBridge in case the parameters are not specified or not provided by the
152 // TargetTransformInfo.
153 static cl::opt
<int> FirstCacheLevelAssociativity(
154 "polly-target-1st-cache-level-associativity",
155 cl::desc("The associativity of the first cache level."), cl::Hidden
,
156 cl::init(-1), cl::ZeroOrMore
, cl::cat(PollyCategory
));
158 static cl::opt
<int> FirstCacheLevelDefaultAssociativity(
159 "polly-target-1st-cache-level-default-associativity",
160 cl::desc("The default associativity of the first cache level"
161 " (if not enough were provided by the TargetTransformInfo)."),
162 cl::Hidden
, cl::init(8), cl::ZeroOrMore
, cl::cat(PollyCategory
));
164 static cl::opt
<int> SecondCacheLevelAssociativity(
165 "polly-target-2nd-cache-level-associativity",
166 cl::desc("The associativity of the second cache level."), cl::Hidden
,
167 cl::init(-1), cl::ZeroOrMore
, cl::cat(PollyCategory
));
169 static cl::opt
<int> SecondCacheLevelDefaultAssociativity(
170 "polly-target-2nd-cache-level-default-associativity",
171 cl::desc("The default associativity of the second cache level"
172 " (if not enough were provided by the TargetTransformInfo)."),
173 cl::Hidden
, cl::init(8), cl::ZeroOrMore
, cl::cat(PollyCategory
));
175 static cl::opt
<int> FirstCacheLevelSize(
176 "polly-target-1st-cache-level-size",
177 cl::desc("The size of the first cache level specified in bytes."),
178 cl::Hidden
, cl::init(-1), cl::ZeroOrMore
, cl::cat(PollyCategory
));
180 static cl::opt
<int> FirstCacheLevelDefaultSize(
181 "polly-target-1st-cache-level-default-size",
182 cl::desc("The default size of the first cache level specified in bytes"
183 " (if not enough were provided by the TargetTransformInfo)."),
184 cl::Hidden
, cl::init(32768), cl::ZeroOrMore
, cl::cat(PollyCategory
));
186 static cl::opt
<int> SecondCacheLevelSize(
187 "polly-target-2nd-cache-level-size",
188 cl::desc("The size of the second level specified in bytes."), cl::Hidden
,
189 cl::init(-1), cl::ZeroOrMore
, cl::cat(PollyCategory
));
191 static cl::opt
<int> SecondCacheLevelDefaultSize(
192 "polly-target-2nd-cache-level-default-size",
193 cl::desc("The default size of the second cache level specified in bytes"
194 " (if not enough were provided by the TargetTransformInfo)."),
195 cl::Hidden
, cl::init(262144), cl::ZeroOrMore
, cl::cat(PollyCategory
));
197 static cl::opt
<int> VectorRegisterBitwidth(
198 "polly-target-vector-register-bitwidth",
199 cl::desc("The size in bits of a vector register (if not set, this "
200 "information is taken from LLVM's target information."),
201 cl::Hidden
, cl::init(-1), cl::ZeroOrMore
, cl::cat(PollyCategory
));
203 static cl::opt
<int> FirstLevelDefaultTileSize(
204 "polly-default-tile-size",
205 cl::desc("The default tile size (if not enough were provided by"
206 " --polly-tile-sizes)"),
207 cl::Hidden
, cl::init(32), cl::ZeroOrMore
, cl::cat(PollyCategory
));
210 FirstLevelTileSizes("polly-tile-sizes",
211 cl::desc("A tile size for each loop dimension, filled "
212 "with --polly-default-tile-size"),
213 cl::Hidden
, cl::ZeroOrMore
, cl::CommaSeparated
,
214 cl::cat(PollyCategory
));
217 SecondLevelTiling("polly-2nd-level-tiling",
218 cl::desc("Enable a 2nd level loop of loop tiling"),
219 cl::init(false), cl::ZeroOrMore
, cl::cat(PollyCategory
));
221 static cl::opt
<int> SecondLevelDefaultTileSize(
222 "polly-2nd-level-default-tile-size",
223 cl::desc("The default 2nd-level tile size (if not enough were provided by"
224 " --polly-2nd-level-tile-sizes)"),
225 cl::Hidden
, cl::init(16), cl::ZeroOrMore
, cl::cat(PollyCategory
));
228 SecondLevelTileSizes("polly-2nd-level-tile-sizes",
229 cl::desc("A tile size for each loop dimension, filled "
230 "with --polly-default-tile-size"),
231 cl::Hidden
, cl::ZeroOrMore
, cl::CommaSeparated
,
232 cl::cat(PollyCategory
));
234 static cl::opt
<bool> RegisterTiling("polly-register-tiling",
235 cl::desc("Enable register tiling"),
236 cl::init(false), cl::ZeroOrMore
,
237 cl::cat(PollyCategory
));
239 static cl::opt
<int> RegisterDefaultTileSize(
240 "polly-register-tiling-default-tile-size",
241 cl::desc("The default register tile size (if not enough were provided by"
242 " --polly-register-tile-sizes)"),
243 cl::Hidden
, cl::init(2), cl::ZeroOrMore
, cl::cat(PollyCategory
));
245 static cl::opt
<int> PollyPatternMatchingNcQuotient(
246 "polly-pattern-matching-nc-quotient",
247 cl::desc("Quotient that is obtained by dividing Nc, the parameter of the"
248 "macro-kernel, by Nr, the parameter of the micro-kernel"),
249 cl::Hidden
, cl::init(256), cl::ZeroOrMore
, cl::cat(PollyCategory
));
252 RegisterTileSizes("polly-register-tile-sizes",
253 cl::desc("A tile size for each loop dimension, filled "
254 "with --polly-register-tile-size"),
255 cl::Hidden
, cl::ZeroOrMore
, cl::CommaSeparated
,
256 cl::cat(PollyCategory
));
259 PMBasedOpts("polly-pattern-matching-based-opts",
260 cl::desc("Perform optimizations based on pattern matching"),
261 cl::init(true), cl::ZeroOrMore
, cl::cat(PollyCategory
));
263 static cl::opt
<bool> OptimizedScops(
264 "polly-optimized-scops",
265 cl::desc("Polly - Dump polyhedral description of Scops optimized with "
266 "the isl scheduling optimizer and the set of post-scheduling "
267 "transformations is applied on the schedule tree"),
268 cl::init(false), cl::ZeroOrMore
, cl::cat(PollyCategory
));
270 STATISTIC(ScopsProcessed
, "Number of scops processed");
271 STATISTIC(ScopsRescheduled
, "Number of scops rescheduled");
272 STATISTIC(ScopsOptimized
, "Number of scops optimized");
274 STATISTIC(NumAffineLoopsOptimized
, "Number of affine loops optimized");
275 STATISTIC(NumBoxedLoopsOptimized
, "Number of boxed loops optimized");
277 #define THREE_STATISTICS(VARNAME, DESC) \
278 static Statistic VARNAME[3] = { \
279 {DEBUG_TYPE, #VARNAME "0", DESC " (original)"}, \
280 {DEBUG_TYPE, #VARNAME "1", DESC " (after scheduler)"}, \
281 {DEBUG_TYPE, #VARNAME "2", DESC " (after optimizer)"}}
283 THREE_STATISTICS(NumBands
, "Number of bands");
284 THREE_STATISTICS(NumBandMembers
, "Number of band members");
285 THREE_STATISTICS(NumCoincident
, "Number of coincident band members");
286 THREE_STATISTICS(NumPermutable
, "Number of permutable bands");
287 THREE_STATISTICS(NumFilters
, "Number of filter nodes");
288 THREE_STATISTICS(NumExtension
, "Number of extension nodes");
290 STATISTIC(FirstLevelTileOpts
, "Number of first level tiling applied");
291 STATISTIC(SecondLevelTileOpts
, "Number of second level tiling applied");
292 STATISTIC(RegisterTileOpts
, "Number of register tiling applied");
293 STATISTIC(PrevectOpts
, "Number of strip-mining for prevectorization applied");
294 STATISTIC(MatMulOpts
,
295 "Number of matrix multiplication patterns detected and optimized");
297 /// Create an isl::union_set, which describes the isolate option based on
300 /// @param IsolateDomain An isl::set whose @p OutDimsNum last dimensions should
301 /// belong to the current band node.
302 /// @param OutDimsNum A number of dimensions that should belong to
303 /// the current band node.
304 static isl::union_set
getIsolateOptions(isl::set IsolateDomain
,
305 unsigned OutDimsNum
) {
306 unsigned Dims
= IsolateDomain
.dim(isl::dim::set
);
307 assert(OutDimsNum
<= Dims
&&
308 "The isl::set IsolateDomain is used to describe the range of schedule "
309 "dimensions values, which should be isolated. Consequently, the "
310 "number of its dimensions should be greater than or equal to the "
311 "number of the schedule dimensions.");
312 isl::map IsolateRelation
= isl::map::from_domain(IsolateDomain
);
313 IsolateRelation
= IsolateRelation
.move_dims(isl::dim::out
, 0, isl::dim::in
,
314 Dims
- OutDimsNum
, OutDimsNum
);
315 isl::set IsolateOption
= IsolateRelation
.wrap();
316 isl::id Id
= isl::id::alloc(IsolateOption
.get_ctx(), "isolate", nullptr);
317 IsolateOption
= IsolateOption
.set_tuple_id(Id
);
318 return isl::union_set(IsolateOption
);
322 /// Create an isl::union_set, which describes the specified option for the
323 /// dimension of the current node.
325 /// @param Ctx An isl::ctx, which is used to create the isl::union_set.
326 /// @param Option The name of the option.
327 isl::union_set
getDimOptions(isl::ctx Ctx
, const char *Option
) {
328 isl::space
Space(Ctx
, 0, 1);
329 auto DimOption
= isl::set::universe(Space
);
330 auto Id
= isl::id::alloc(Ctx
, Option
, nullptr);
331 DimOption
= DimOption
.set_tuple_id(Id
);
332 return isl::union_set(DimOption
);
336 /// Create an isl::union_set, which describes the option of the form
337 /// [isolate[] -> unroll[x]].
339 /// @param Ctx An isl::ctx, which is used to create the isl::union_set.
340 static isl::union_set
getUnrollIsolatedSetOptions(isl::ctx Ctx
) {
341 isl::space Space
= isl::space(Ctx
, 0, 0, 1);
342 isl::map UnrollIsolatedSetOption
= isl::map::universe(Space
);
343 isl::id DimInId
= isl::id::alloc(Ctx
, "isolate", nullptr);
344 isl::id DimOutId
= isl::id::alloc(Ctx
, "unroll", nullptr);
345 UnrollIsolatedSetOption
=
346 UnrollIsolatedSetOption
.set_tuple_id(isl::dim::in
, DimInId
);
347 UnrollIsolatedSetOption
=
348 UnrollIsolatedSetOption
.set_tuple_id(isl::dim::out
, DimOutId
);
349 return UnrollIsolatedSetOption
.wrap();
352 /// Make the last dimension of Set to take values from 0 to VectorWidth - 1.
354 /// @param Set A set, which should be modified.
355 /// @param VectorWidth A parameter, which determines the constraint.
356 static isl::set
addExtentConstraints(isl::set Set
, int VectorWidth
) {
357 unsigned Dims
= Set
.dim(isl::dim::set
);
358 isl::space Space
= Set
.get_space();
359 isl::local_space LocalSpace
= isl::local_space(Space
);
360 isl::constraint ExtConstr
= isl::constraint::alloc_inequality(LocalSpace
);
361 ExtConstr
= ExtConstr
.set_constant_si(0);
362 ExtConstr
= ExtConstr
.set_coefficient_si(isl::dim::set
, Dims
- 1, 1);
363 Set
= Set
.add_constraint(ExtConstr
);
364 ExtConstr
= isl::constraint::alloc_inequality(LocalSpace
);
365 ExtConstr
= ExtConstr
.set_constant_si(VectorWidth
- 1);
366 ExtConstr
= ExtConstr
.set_coefficient_si(isl::dim::set
, Dims
- 1, -1);
367 return Set
.add_constraint(ExtConstr
);
370 isl::set
getPartialTilePrefixes(isl::set ScheduleRange
, int VectorWidth
) {
371 unsigned Dims
= ScheduleRange
.dim(isl::dim::set
);
372 isl::set LoopPrefixes
=
373 ScheduleRange
.drop_constraints_involving_dims(isl::dim::set
, Dims
- 1, 1);
374 auto ExtentPrefixes
= addExtentConstraints(LoopPrefixes
, VectorWidth
);
375 isl::set BadPrefixes
= ExtentPrefixes
.subtract(ScheduleRange
);
376 BadPrefixes
= BadPrefixes
.project_out(isl::dim::set
, Dims
- 1, 1);
377 LoopPrefixes
= LoopPrefixes
.project_out(isl::dim::set
, Dims
- 1, 1);
378 return LoopPrefixes
.subtract(BadPrefixes
);
382 ScheduleTreeOptimizer::isolateFullPartialTiles(isl::schedule_node Node
,
384 assert(isl_schedule_node_get_type(Node
.get()) == isl_schedule_node_band
);
385 Node
= Node
.child(0).child(0);
386 isl::union_map SchedRelUMap
= Node
.get_prefix_schedule_relation();
387 isl::map ScheduleRelation
= isl::map::from_union_map(SchedRelUMap
);
388 isl::set ScheduleRange
= ScheduleRelation
.range();
389 isl::set IsolateDomain
= getPartialTilePrefixes(ScheduleRange
, VectorWidth
);
390 auto AtomicOption
= getDimOptions(IsolateDomain
.get_ctx(), "atomic");
391 isl::union_set IsolateOption
= getIsolateOptions(IsolateDomain
, 1);
392 Node
= Node
.parent().parent();
393 isl::union_set Options
= IsolateOption
.unite(AtomicOption
);
394 Node
= Node
.band_set_ast_build_options(Options
);
398 isl::schedule_node
ScheduleTreeOptimizer::prevectSchedBand(
399 isl::schedule_node Node
, unsigned DimToVectorize
, int VectorWidth
) {
400 assert(isl_schedule_node_get_type(Node
.get()) == isl_schedule_node_band
);
402 auto Space
= isl::manage(isl_schedule_node_band_get_space(Node
.get()));
403 auto ScheduleDimensions
= Space
.dim(isl::dim::set
);
404 assert(DimToVectorize
< ScheduleDimensions
);
406 if (DimToVectorize
> 0) {
408 isl_schedule_node_band_split(Node
.release(), DimToVectorize
));
409 Node
= Node
.child(0);
411 if (DimToVectorize
< ScheduleDimensions
- 1)
412 Node
= isl::manage(isl_schedule_node_band_split(Node
.release(), 1));
413 Space
= isl::manage(isl_schedule_node_band_get_space(Node
.get()));
414 auto Sizes
= isl::multi_val::zero(Space
);
415 Sizes
= Sizes
.set_val(0, isl::val(Node
.get_ctx(), VectorWidth
));
417 isl::manage(isl_schedule_node_band_tile(Node
.release(), Sizes
.release()));
418 Node
= isolateFullPartialTiles(Node
, VectorWidth
);
419 Node
= Node
.child(0);
420 // Make sure the "trivially vectorizable loop" is not unrolled. Otherwise,
421 // we will have troubles to match it in the backend.
422 Node
= Node
.band_set_ast_build_options(
423 isl::union_set(Node
.get_ctx(), "{ unroll[x]: 1 = 0 }"));
424 Node
= isl::manage(isl_schedule_node_band_sink(Node
.release()));
425 Node
= Node
.child(0);
426 if (isl_schedule_node_get_type(Node
.get()) == isl_schedule_node_leaf
)
427 Node
= Node
.parent();
428 auto LoopMarker
= isl::id::alloc(Node
.get_ctx(), "SIMD", nullptr);
430 return Node
.insert_mark(LoopMarker
);
433 isl::schedule_node
ScheduleTreeOptimizer::tileNode(isl::schedule_node Node
,
434 const char *Identifier
,
435 ArrayRef
<int> TileSizes
,
436 int DefaultTileSize
) {
437 auto Space
= isl::manage(isl_schedule_node_band_get_space(Node
.get()));
438 auto Dims
= Space
.dim(isl::dim::set
);
439 auto Sizes
= isl::multi_val::zero(Space
);
440 std::string
IdentifierString(Identifier
);
441 for (unsigned i
= 0; i
< Dims
; i
++) {
442 auto tileSize
= i
< TileSizes
.size() ? TileSizes
[i
] : DefaultTileSize
;
443 Sizes
= Sizes
.set_val(i
, isl::val(Node
.get_ctx(), tileSize
));
445 auto TileLoopMarkerStr
= IdentifierString
+ " - Tiles";
446 auto TileLoopMarker
=
447 isl::id::alloc(Node
.get_ctx(), TileLoopMarkerStr
, nullptr);
448 Node
= Node
.insert_mark(TileLoopMarker
);
449 Node
= Node
.child(0);
451 isl::manage(isl_schedule_node_band_tile(Node
.release(), Sizes
.release()));
452 Node
= Node
.child(0);
453 auto PointLoopMarkerStr
= IdentifierString
+ " - Points";
454 auto PointLoopMarker
=
455 isl::id::alloc(Node
.get_ctx(), PointLoopMarkerStr
, nullptr);
456 Node
= Node
.insert_mark(PointLoopMarker
);
457 return Node
.child(0);
460 isl::schedule_node
ScheduleTreeOptimizer::applyRegisterTiling(
461 isl::schedule_node Node
, ArrayRef
<int> TileSizes
, int DefaultTileSize
) {
462 Node
= tileNode(Node
, "Register tiling", TileSizes
, DefaultTileSize
);
463 auto Ctx
= Node
.get_ctx();
464 return Node
.band_set_ast_build_options(isl::union_set(Ctx
, "{unroll[x]}"));
467 static bool isSimpleInnermostBand(const isl::schedule_node
&Node
) {
468 assert(isl_schedule_node_get_type(Node
.get()) == isl_schedule_node_band
);
469 assert(isl_schedule_node_n_children(Node
.get()) == 1);
471 auto ChildType
= isl_schedule_node_get_type(Node
.child(0).get());
473 if (ChildType
== isl_schedule_node_leaf
)
476 if (ChildType
!= isl_schedule_node_sequence
)
479 auto Sequence
= Node
.child(0);
481 for (int c
= 0, nc
= isl_schedule_node_n_children(Sequence
.get()); c
< nc
;
483 auto Child
= Sequence
.child(c
);
484 if (isl_schedule_node_get_type(Child
.get()) != isl_schedule_node_filter
)
486 if (isl_schedule_node_get_type(Child
.child(0).get()) !=
487 isl_schedule_node_leaf
)
493 bool ScheduleTreeOptimizer::isTileableBandNode(isl::schedule_node Node
) {
494 if (isl_schedule_node_get_type(Node
.get()) != isl_schedule_node_band
)
497 if (isl_schedule_node_n_children(Node
.get()) != 1)
500 if (!isl_schedule_node_band_get_permutable(Node
.get()))
503 auto Space
= isl::manage(isl_schedule_node_band_get_space(Node
.get()));
504 auto Dims
= Space
.dim(isl::dim::set
);
509 return isSimpleInnermostBand(Node
);
512 __isl_give
isl::schedule_node
513 ScheduleTreeOptimizer::standardBandOpts(isl::schedule_node Node
, void *User
) {
514 if (FirstLevelTiling
) {
515 Node
= tileNode(Node
, "1st level tiling", FirstLevelTileSizes
,
516 FirstLevelDefaultTileSize
);
517 FirstLevelTileOpts
++;
520 if (SecondLevelTiling
) {
521 Node
= tileNode(Node
, "2nd level tiling", SecondLevelTileSizes
,
522 SecondLevelDefaultTileSize
);
523 SecondLevelTileOpts
++;
526 if (RegisterTiling
) {
528 applyRegisterTiling(Node
, RegisterTileSizes
, RegisterDefaultTileSize
);
532 if (PollyVectorizerChoice
== VECTORIZER_NONE
)
535 auto Space
= isl::manage(isl_schedule_node_band_get_space(Node
.get()));
536 auto Dims
= Space
.dim(isl::dim::set
);
538 for (int i
= Dims
- 1; i
>= 0; i
--)
539 if (Node
.band_member_get_coincident(i
)) {
540 Node
= prevectSchedBand(Node
, i
, PrevectorWidth
);
547 /// Permute the two dimensions of the isl map.
549 /// Permute @p DstPos and @p SrcPos dimensions of the isl map @p Map that
550 /// have type @p DimType.
552 /// @param Map The isl map to be modified.
553 /// @param DimType The type of the dimensions.
554 /// @param DstPos The first dimension.
555 /// @param SrcPos The second dimension.
556 /// @return The modified map.
557 isl::map
permuteDimensions(isl::map Map
, isl::dim DimType
, unsigned DstPos
,
559 assert(DstPos
< Map
.dim(DimType
) && SrcPos
< Map
.dim(DimType
));
560 if (DstPos
== SrcPos
)
563 if (Map
.has_tuple_id(DimType
))
564 DimId
= Map
.get_tuple_id(DimType
);
565 auto FreeDim
= DimType
== isl::dim::in
? isl::dim::out
: isl::dim::in
;
567 if (Map
.has_tuple_id(FreeDim
))
568 FreeDimId
= Map
.get_tuple_id(FreeDim
);
569 auto MaxDim
= std::max(DstPos
, SrcPos
);
570 auto MinDim
= std::min(DstPos
, SrcPos
);
571 Map
= Map
.move_dims(FreeDim
, 0, DimType
, MaxDim
, 1);
572 Map
= Map
.move_dims(FreeDim
, 0, DimType
, MinDim
, 1);
573 Map
= Map
.move_dims(DimType
, MinDim
, FreeDim
, 1, 1);
574 Map
= Map
.move_dims(DimType
, MaxDim
, FreeDim
, 0, 1);
576 Map
= Map
.set_tuple_id(DimType
, DimId
);
578 Map
= Map
.set_tuple_id(FreeDim
, FreeDimId
);
582 /// Check the form of the access relation.
584 /// Check that the access relation @p AccMap has the form M[i][j], where i
585 /// is a @p FirstPos and j is a @p SecondPos.
587 /// @param AccMap The access relation to be checked.
588 /// @param FirstPos The index of the input dimension that is mapped to
589 /// the first output dimension.
590 /// @param SecondPos The index of the input dimension that is mapped to the
591 /// second output dimension.
592 /// @return True in case @p AccMap has the expected form and false,
594 static bool isMatMulOperandAcc(isl::set Domain
, isl::map AccMap
, int &FirstPos
,
596 isl::space Space
= AccMap
.get_space();
597 isl::map Universe
= isl::map::universe(Space
);
599 if (Space
.dim(isl::dim::out
) != 2)
602 // MatMul has the form:
603 // for (i = 0; i < N; i++)
604 // for (j = 0; j < M; j++)
605 // for (k = 0; k < P; k++)
606 // C[i, j] += A[i, k] * B[k, j]
608 // Permutation of three outer loops: 3! = 6 possibilities.
609 int FirstDims
[] = {0, 0, 1, 1, 2, 2};
610 int SecondDims
[] = {1, 2, 2, 0, 0, 1};
611 for (int i
= 0; i
< 6; i
+= 1) {
612 auto PossibleMatMul
=
613 Universe
.equate(isl::dim::in
, FirstDims
[i
], isl::dim::out
, 0)
614 .equate(isl::dim::in
, SecondDims
[i
], isl::dim::out
, 1);
616 AccMap
= AccMap
.intersect_domain(Domain
);
617 PossibleMatMul
= PossibleMatMul
.intersect_domain(Domain
);
619 // If AccMap spans entire domain (Non-partial write),
620 // compute FirstPos and SecondPos.
621 // If AccMap != PossibleMatMul here (the two maps have been gisted at
622 // this point), it means that the writes are not complete, or in other
623 // words, it is a Partial write and Partial writes must be rejected.
624 if (AccMap
.is_equal(PossibleMatMul
)) {
625 if (FirstPos
!= -1 && FirstPos
!= FirstDims
[i
])
627 FirstPos
= FirstDims
[i
];
628 if (SecondPos
!= -1 && SecondPos
!= SecondDims
[i
])
630 SecondPos
= SecondDims
[i
];
638 /// Does the memory access represent a non-scalar operand of the matrix
641 /// Check that the memory access @p MemAccess is the read access to a non-scalar
642 /// operand of the matrix multiplication or its result.
644 /// @param MemAccess The memory access to be checked.
645 /// @param MMI Parameters of the matrix multiplication operands.
646 /// @return True in case the memory access represents the read access
647 /// to a non-scalar operand of the matrix multiplication and
648 /// false, otherwise.
649 static bool isMatMulNonScalarReadAccess(MemoryAccess
*MemAccess
,
651 if (!MemAccess
->isLatestArrayKind() || !MemAccess
->isRead())
653 auto AccMap
= MemAccess
->getLatestAccessRelation();
654 isl::set StmtDomain
= MemAccess
->getStatement()->getDomain();
655 if (isMatMulOperandAcc(StmtDomain
, AccMap
, MMI
.i
, MMI
.j
) && !MMI
.ReadFromC
) {
656 MMI
.ReadFromC
= MemAccess
;
659 if (isMatMulOperandAcc(StmtDomain
, AccMap
, MMI
.i
, MMI
.k
) && !MMI
.A
) {
663 if (isMatMulOperandAcc(StmtDomain
, AccMap
, MMI
.k
, MMI
.j
) && !MMI
.B
) {
670 /// Check accesses to operands of the matrix multiplication.
672 /// Check that accesses of the SCoP statement, which corresponds to
673 /// the partial schedule @p PartialSchedule, are scalar in terms of loops
674 /// containing the matrix multiplication, in case they do not represent
675 /// accesses to the non-scalar operands of the matrix multiplication or
678 /// @param PartialSchedule The partial schedule of the SCoP statement.
679 /// @param MMI Parameters of the matrix multiplication operands.
680 /// @return True in case the corresponding SCoP statement
681 /// represents matrix multiplication and false,
683 static bool containsOnlyMatrMultAcc(isl::map PartialSchedule
,
685 auto InputDimId
= PartialSchedule
.get_tuple_id(isl::dim::in
);
686 auto *Stmt
= static_cast<ScopStmt
*>(InputDimId
.get_user());
687 unsigned OutDimNum
= PartialSchedule
.dim(isl::dim::out
);
688 assert(OutDimNum
> 2 && "In case of the matrix multiplication the loop nest "
689 "and, consequently, the corresponding scheduling "
690 "functions have at least three dimensions.");
692 permuteDimensions(PartialSchedule
, isl::dim::out
, MMI
.i
, OutDimNum
- 1);
694 permuteDimensions(PartialSchedule
, isl::dim::out
, MMI
.j
, OutDimNum
- 1);
696 permuteDimensions(PartialSchedule
, isl::dim::out
, MMI
.k
, OutDimNum
- 1);
698 auto Accesses
= getAccessesInOrder(*Stmt
);
699 for (auto *MemA
= Accesses
.begin(); MemA
!= Accesses
.end() - 1; MemA
++) {
700 auto *MemAccessPtr
= *MemA
;
701 if (MemAccessPtr
->isLatestArrayKind() && MemAccessPtr
!= MMI
.WriteToC
&&
702 !isMatMulNonScalarReadAccess(MemAccessPtr
, MMI
) &&
703 !(MemAccessPtr
->isStrideZero(MapI
)) &&
704 MemAccessPtr
->isStrideZero(MapJ
) && MemAccessPtr
->isStrideZero(MapK
))
710 /// Check for dependencies corresponding to the matrix multiplication.
712 /// Check that there is only true dependence of the form
713 /// S(..., k, ...) -> S(..., k + 1, …), where S is the SCoP statement
714 /// represented by @p Schedule and k is @p Pos. Such a dependence corresponds
715 /// to the dependency produced by the matrix multiplication.
717 /// @param Schedule The schedule of the SCoP statement.
718 /// @param D The SCoP dependencies.
719 /// @param Pos The parameter to describe an acceptable true dependence.
720 /// In case it has a negative value, try to determine its
721 /// acceptable value.
722 /// @return True in case dependencies correspond to the matrix multiplication
723 /// and false, otherwise.
724 static bool containsOnlyMatMulDep(isl::map Schedule
, const Dependences
*D
,
726 isl::union_map Dep
= D
->getDependences(Dependences::TYPE_RAW
);
727 isl::union_map Red
= D
->getDependences(Dependences::TYPE_RED
);
729 Dep
= Dep
.unite(Red
);
730 auto DomainSpace
= Schedule
.get_space().domain();
731 auto Space
= DomainSpace
.map_from_domain_and_range(DomainSpace
);
732 auto Deltas
= Dep
.extract_map(Space
).deltas();
733 int DeltasDimNum
= Deltas
.dim(isl::dim::set
);
734 for (int i
= 0; i
< DeltasDimNum
; i
++) {
735 auto Val
= Deltas
.plain_get_val_if_fixed(isl::dim::set
, i
);
736 Pos
= Pos
< 0 && Val
.is_one() ? i
: Pos
;
737 if (Val
.is_nan() || !(Val
.is_zero() || (i
== Pos
&& Val
.is_one())))
740 if (DeltasDimNum
== 0 || Pos
< 0)
745 /// Check if the SCoP statement could probably be optimized with analytical
748 /// containsMatrMult tries to determine whether the following conditions
750 /// 1. The last memory access modeling an array, MA1, represents writing to
751 /// memory and has the form S(..., i1, ..., i2, ...) -> M(i1, i2) or
752 /// S(..., i2, ..., i1, ...) -> M(i1, i2), where S is the SCoP statement
753 /// under consideration.
754 /// 2. There is only one loop-carried true dependency, and it has the
755 /// form S(..., i3, ...) -> S(..., i3 + 1, ...), and there are no
756 /// loop-carried or anti dependencies.
757 /// 3. SCoP contains three access relations, MA2, MA3, and MA4 that represent
758 /// reading from memory and have the form S(..., i3, ...) -> M(i1, i3),
759 /// S(..., i3, ...) -> M(i3, i2), S(...) -> M(i1, i2), respectively,
760 /// and all memory accesses of the SCoP that are different from MA1, MA2,
761 /// MA3, and MA4 have stride 0, if the innermost loop is exchanged with any
762 /// of loops i1, i2 and i3.
764 /// @param PartialSchedule The PartialSchedule that contains a SCoP statement
766 /// @D The SCoP dependencies.
767 /// @MMI Parameters of the matrix multiplication operands.
768 static bool containsMatrMult(isl::map PartialSchedule
, const Dependences
*D
,
770 auto InputDimsId
= PartialSchedule
.get_tuple_id(isl::dim::in
);
771 auto *Stmt
= static_cast<ScopStmt
*>(InputDimsId
.get_user());
772 if (Stmt
->size() <= 1)
775 auto Accesses
= getAccessesInOrder(*Stmt
);
776 for (auto *MemA
= Accesses
.end() - 1; MemA
!= Accesses
.begin(); MemA
--) {
777 auto *MemAccessPtr
= *MemA
;
778 if (!MemAccessPtr
->isLatestArrayKind())
780 if (!MemAccessPtr
->isWrite())
782 auto AccMap
= MemAccessPtr
->getLatestAccessRelation();
783 if (!isMatMulOperandAcc(Stmt
->getDomain(), AccMap
, MMI
.i
, MMI
.j
))
785 MMI
.WriteToC
= MemAccessPtr
;
789 if (!containsOnlyMatMulDep(PartialSchedule
, D
, MMI
.k
))
792 if (!MMI
.WriteToC
|| !containsOnlyMatrMultAcc(PartialSchedule
, MMI
))
795 if (!MMI
.A
|| !MMI
.B
|| !MMI
.ReadFromC
)
800 /// Permute two dimensions of the band node.
802 /// Permute FirstDim and SecondDim dimensions of the Node.
804 /// @param Node The band node to be modified.
805 /// @param FirstDim The first dimension to be permuted.
806 /// @param SecondDim The second dimension to be permuted.
807 static isl::schedule_node
permuteBandNodeDimensions(isl::schedule_node Node
,
809 unsigned SecondDim
) {
810 assert(isl_schedule_node_get_type(Node
.get()) == isl_schedule_node_band
&&
811 isl_schedule_node_band_n_member(Node
.get()) >
812 std::max(FirstDim
, SecondDim
));
813 auto PartialSchedule
=
814 isl::manage(isl_schedule_node_band_get_partial_schedule(Node
.get()));
815 auto PartialScheduleFirstDim
= PartialSchedule
.get_union_pw_aff(FirstDim
);
816 auto PartialScheduleSecondDim
= PartialSchedule
.get_union_pw_aff(SecondDim
);
818 PartialSchedule
.set_union_pw_aff(SecondDim
, PartialScheduleFirstDim
);
820 PartialSchedule
.set_union_pw_aff(FirstDim
, PartialScheduleSecondDim
);
821 Node
= isl::manage(isl_schedule_node_delete(Node
.release()));
822 return Node
.insert_partial_schedule(PartialSchedule
);
825 isl::schedule_node
ScheduleTreeOptimizer::createMicroKernel(
826 isl::schedule_node Node
, MicroKernelParamsTy MicroKernelParams
) {
827 Node
= applyRegisterTiling(Node
, {MicroKernelParams
.Mr
, MicroKernelParams
.Nr
},
829 Node
= Node
.parent().parent();
830 return permuteBandNodeDimensions(Node
, 0, 1).child(0).child(0);
833 isl::schedule_node
ScheduleTreeOptimizer::createMacroKernel(
834 isl::schedule_node Node
, MacroKernelParamsTy MacroKernelParams
) {
835 assert(isl_schedule_node_get_type(Node
.get()) == isl_schedule_node_band
);
836 if (MacroKernelParams
.Mc
== 1 && MacroKernelParams
.Nc
== 1 &&
837 MacroKernelParams
.Kc
== 1)
839 int DimOutNum
= isl_schedule_node_band_n_member(Node
.get());
840 std::vector
<int> TileSizes(DimOutNum
, 1);
841 TileSizes
[DimOutNum
- 3] = MacroKernelParams
.Mc
;
842 TileSizes
[DimOutNum
- 2] = MacroKernelParams
.Nc
;
843 TileSizes
[DimOutNum
- 1] = MacroKernelParams
.Kc
;
844 Node
= tileNode(Node
, "1st level tiling", TileSizes
, 1);
845 Node
= Node
.parent().parent();
846 Node
= permuteBandNodeDimensions(Node
, DimOutNum
- 2, DimOutNum
- 1);
847 Node
= permuteBandNodeDimensions(Node
, DimOutNum
- 3, DimOutNum
- 1);
849 // Mark the outermost loop as parallelizable.
850 Node
= Node
.band_member_set_coincident(0, true);
852 return Node
.child(0).child(0);
855 /// Get the size of the widest type of the matrix multiplication operands
856 /// in bytes, including alignment padding.
858 /// @param MMI Parameters of the matrix multiplication operands.
859 /// @return The size of the widest type of the matrix multiplication operands
860 /// in bytes, including alignment padding.
861 static uint64_t getMatMulAlignTypeSize(MatMulInfoTy MMI
) {
862 auto *S
= MMI
.A
->getStatement()->getParent();
863 auto &DL
= S
->getFunction().getParent()->getDataLayout();
864 auto ElementSizeA
= DL
.getTypeAllocSize(MMI
.A
->getElementType());
865 auto ElementSizeB
= DL
.getTypeAllocSize(MMI
.B
->getElementType());
866 auto ElementSizeC
= DL
.getTypeAllocSize(MMI
.WriteToC
->getElementType());
867 return std::max({ElementSizeA
, ElementSizeB
, ElementSizeC
});
870 /// Get the size of the widest type of the matrix multiplication operands
873 /// @param MMI Parameters of the matrix multiplication operands.
874 /// @return The size of the widest type of the matrix multiplication operands
876 static uint64_t getMatMulTypeSize(MatMulInfoTy MMI
) {
877 auto *S
= MMI
.A
->getStatement()->getParent();
878 auto &DL
= S
->getFunction().getParent()->getDataLayout();
879 auto ElementSizeA
= DL
.getTypeSizeInBits(MMI
.A
->getElementType());
880 auto ElementSizeB
= DL
.getTypeSizeInBits(MMI
.B
->getElementType());
881 auto ElementSizeC
= DL
.getTypeSizeInBits(MMI
.WriteToC
->getElementType());
882 return std::max({ElementSizeA
, ElementSizeB
, ElementSizeC
});
885 /// Get parameters of the BLIS micro kernel.
887 /// We choose the Mr and Nr parameters of the micro kernel to be large enough
888 /// such that no stalls caused by the combination of latencies and dependencies
889 /// are introduced during the updates of the resulting matrix of the matrix
890 /// multiplication. However, they should also be as small as possible to
891 /// release more registers for entries of multiplied matrices.
893 /// @param TTI Target Transform Info.
894 /// @param MMI Parameters of the matrix multiplication operands.
895 /// @return The structure of type MicroKernelParamsTy.
896 /// @see MicroKernelParamsTy
897 static struct MicroKernelParamsTy
898 getMicroKernelParams(const TargetTransformInfo
*TTI
, MatMulInfoTy MMI
) {
899 assert(TTI
&& "The target transform info should be provided.");
901 // Nvec - Number of double-precision floating-point numbers that can be hold
902 // by a vector register. Use 2 by default.
903 long RegisterBitwidth
= VectorRegisterBitwidth
;
905 if (RegisterBitwidth
== -1)
906 RegisterBitwidth
= TTI
->getRegisterBitWidth(true);
907 auto ElementSize
= getMatMulTypeSize(MMI
);
908 assert(ElementSize
> 0 && "The element size of the matrix multiplication "
909 "operands should be greater than zero.");
910 auto Nvec
= RegisterBitwidth
/ ElementSize
;
913 int Nr
= ceil(sqrt((double)(Nvec
* LatencyVectorFma
* ThroughputVectorFma
)) /
916 int Mr
= ceil((double)(Nvec
* LatencyVectorFma
* ThroughputVectorFma
/ Nr
));
921 /// Determine parameters of the target cache.
923 /// @param TTI Target Transform Info.
924 void getTargetCacheParameters(const llvm::TargetTransformInfo
*TTI
) {
925 auto L1DCache
= llvm::TargetTransformInfo::CacheLevel::L1D
;
926 auto L2DCache
= llvm::TargetTransformInfo::CacheLevel::L2D
;
927 if (FirstCacheLevelSize
== -1) {
928 if (TTI
->getCacheSize(L1DCache
).hasValue())
929 FirstCacheLevelSize
= TTI
->getCacheSize(L1DCache
).getValue();
931 FirstCacheLevelSize
= static_cast<int>(FirstCacheLevelDefaultSize
);
933 if (SecondCacheLevelSize
== -1) {
934 if (TTI
->getCacheSize(L2DCache
).hasValue())
935 SecondCacheLevelSize
= TTI
->getCacheSize(L2DCache
).getValue();
937 SecondCacheLevelSize
= static_cast<int>(SecondCacheLevelDefaultSize
);
939 if (FirstCacheLevelAssociativity
== -1) {
940 if (TTI
->getCacheAssociativity(L1DCache
).hasValue())
941 FirstCacheLevelAssociativity
=
942 TTI
->getCacheAssociativity(L1DCache
).getValue();
944 FirstCacheLevelAssociativity
=
945 static_cast<int>(FirstCacheLevelDefaultAssociativity
);
947 if (SecondCacheLevelAssociativity
== -1) {
948 if (TTI
->getCacheAssociativity(L2DCache
).hasValue())
949 SecondCacheLevelAssociativity
=
950 TTI
->getCacheAssociativity(L2DCache
).getValue();
952 SecondCacheLevelAssociativity
=
953 static_cast<int>(SecondCacheLevelDefaultAssociativity
);
958 /// Get parameters of the BLIS macro kernel.
960 /// During the computation of matrix multiplication, blocks of partitioned
961 /// matrices are mapped to different layers of the memory hierarchy.
962 /// To optimize data reuse, blocks should be ideally kept in cache between
963 /// iterations. Since parameters of the macro kernel determine sizes of these
964 /// blocks, there are upper and lower bounds on these parameters.
966 /// @param TTI Target Transform Info.
967 /// @param MicroKernelParams Parameters of the micro-kernel
968 /// to be taken into account.
969 /// @param MMI Parameters of the matrix multiplication operands.
970 /// @return The structure of type MacroKernelParamsTy.
971 /// @see MacroKernelParamsTy
972 /// @see MicroKernelParamsTy
973 static struct MacroKernelParamsTy
974 getMacroKernelParams(const llvm::TargetTransformInfo
*TTI
,
975 const MicroKernelParamsTy
&MicroKernelParams
,
977 getTargetCacheParameters(TTI
);
978 // According to www.cs.utexas.edu/users/flame/pubs/TOMS-BLIS-Analytical.pdf,
979 // it requires information about the first two levels of a cache to determine
980 // all the parameters of a macro-kernel. It also checks that an associativity
981 // degree of a cache level is greater than two. Otherwise, another algorithm
982 // for determination of the parameters should be used.
983 if (!(MicroKernelParams
.Mr
> 0 && MicroKernelParams
.Nr
> 0 &&
984 FirstCacheLevelSize
> 0 && SecondCacheLevelSize
> 0 &&
985 FirstCacheLevelAssociativity
> 2 && SecondCacheLevelAssociativity
> 2))
987 // The quotient should be greater than zero.
988 if (PollyPatternMatchingNcQuotient
<= 0)
991 (FirstCacheLevelAssociativity
- 1) /
992 (1 + static_cast<double>(MicroKernelParams
.Nr
) / MicroKernelParams
.Mr
));
994 // Car can be computed to be zero since it is floor to int.
995 // On Mac OS, division by 0 does not raise a signal. This causes negative
996 // tile sizes to be computed. Prevent division by Cac==0 by early returning
1001 auto ElementSize
= getMatMulAlignTypeSize(MMI
);
1002 assert(ElementSize
> 0 && "The element size of the matrix multiplication "
1003 "operands should be greater than zero.");
1004 int Kc
= (Car
* FirstCacheLevelSize
) /
1005 (MicroKernelParams
.Mr
* FirstCacheLevelAssociativity
* ElementSize
);
1007 static_cast<double>(Kc
* ElementSize
* SecondCacheLevelAssociativity
) /
1008 SecondCacheLevelSize
;
1009 int Mc
= floor((SecondCacheLevelAssociativity
- 2) / Cac
);
1010 int Nc
= PollyPatternMatchingNcQuotient
* MicroKernelParams
.Nr
;
1012 assert(Mc
> 0 && Nc
> 0 && Kc
> 0 &&
1013 "Matrix block sizes should be greater than zero");
1014 return {Mc
, Nc
, Kc
};
1017 /// Create an access relation that is specific to
1018 /// the matrix multiplication pattern.
1020 /// Create an access relation of the following form:
1021 /// [O0, O1, O2, O3, O4, O5, O6, O7, O8] -> [OI, O5, OJ]
1022 /// where I is @p FirstDim, J is @p SecondDim.
1024 /// It can be used, for example, to create relations that helps to consequently
1025 /// access elements of operands of a matrix multiplication after creation of
1026 /// the BLIS micro and macro kernels.
1028 /// @see ScheduleTreeOptimizer::createMicroKernel
1029 /// @see ScheduleTreeOptimizer::createMacroKernel
1031 /// Subsequently, the described access relation is applied to the range of
1032 /// @p MapOldIndVar, that is used to map original induction variables to
1033 /// the ones, which are produced by schedule transformations. It helps to
1034 /// define relations using a new space and, at the same time, keep them
1035 /// in the original one.
1037 /// @param MapOldIndVar The relation, which maps original induction variables
1038 /// to the ones, which are produced by schedule
1039 /// transformations.
1040 /// @param FirstDim, SecondDim The input dimensions that are used to define
1041 /// the specified access relation.
1042 /// @return The specified access relation.
1043 isl::map
getMatMulAccRel(isl::map MapOldIndVar
, unsigned FirstDim
,
1044 unsigned SecondDim
) {
1045 auto AccessRelSpace
= isl::space(MapOldIndVar
.get_ctx(), 0, 9, 3);
1046 auto AccessRel
= isl::map::universe(AccessRelSpace
);
1047 AccessRel
= AccessRel
.equate(isl::dim::in
, FirstDim
, isl::dim::out
, 0);
1048 AccessRel
= AccessRel
.equate(isl::dim::in
, 5, isl::dim::out
, 1);
1049 AccessRel
= AccessRel
.equate(isl::dim::in
, SecondDim
, isl::dim::out
, 2);
1050 return MapOldIndVar
.apply_range(AccessRel
);
1053 isl::schedule_node
createExtensionNode(isl::schedule_node Node
,
1054 isl::map ExtensionMap
) {
1055 auto Extension
= isl::union_map(ExtensionMap
);
1056 auto NewNode
= isl::schedule_node::from_extension(Extension
);
1057 return Node
.graft_before(NewNode
);
1060 /// Apply the packing transformation.
1062 /// The packing transformation can be described as a data-layout
1063 /// transformation that requires to introduce a new array, copy data
1064 /// to the array, and change memory access locations to reference the array.
1065 /// It can be used to ensure that elements of the new array are read in-stride
1066 /// access, aligned to cache lines boundaries, and preloaded into certain cache
1069 /// As an example let us consider the packing of the array A that would help
1070 /// to read its elements with in-stride access. An access to the array A
1071 /// is represented by an access relation that has the form
1072 /// S[i, j, k] -> A[i, k]. The scheduling function of the SCoP statement S has
1073 /// the form S[i,j, k] -> [floor((j mod Nc) / Nr), floor((i mod Mc) / Mr),
1074 /// k mod Kc, j mod Nr, i mod Mr].
1076 /// To ensure that elements of the array A are read in-stride access, we add
1077 /// a new array Packed_A[Mc/Mr][Kc][Mr] to the SCoP, using
1078 /// Scop::createScopArrayInfo, change the access relation
1079 /// S[i, j, k] -> A[i, k] to
1080 /// S[i, j, k] -> Packed_A[floor((i mod Mc) / Mr), k mod Kc, i mod Mr], using
1081 /// MemoryAccess::setNewAccessRelation, and copy the data to the array, using
1082 /// the copy statement created by Scop::addScopStmt.
1084 /// @param Node The schedule node to be optimized.
1085 /// @param MapOldIndVar The relation, which maps original induction variables
1086 /// to the ones, which are produced by schedule
1087 /// transformations.
1088 /// @param MicroParams, MacroParams Parameters of the BLIS kernel
1089 /// to be taken into account.
1090 /// @param MMI Parameters of the matrix multiplication operands.
1091 /// @return The optimized schedule node.
1092 static isl::schedule_node
1093 optimizeDataLayoutMatrMulPattern(isl::schedule_node Node
, isl::map MapOldIndVar
,
1094 MicroKernelParamsTy MicroParams
,
1095 MacroKernelParamsTy MacroParams
,
1096 MatMulInfoTy
&MMI
) {
1097 auto InputDimsId
= MapOldIndVar
.get_tuple_id(isl::dim::in
);
1098 auto *Stmt
= static_cast<ScopStmt
*>(InputDimsId
.get_user());
1100 // Create a copy statement that corresponds to the memory access to the
1101 // matrix B, the second operand of the matrix multiplication.
1102 Node
= Node
.parent().parent().parent().parent().parent().parent();
1103 Node
= isl::manage(isl_schedule_node_band_split(Node
.release(), 2)).child(0);
1104 auto AccRel
= getMatMulAccRel(MapOldIndVar
, 3, 7);
1105 unsigned FirstDimSize
= MacroParams
.Nc
/ MicroParams
.Nr
;
1106 unsigned SecondDimSize
= MacroParams
.Kc
;
1107 unsigned ThirdDimSize
= MicroParams
.Nr
;
1108 auto *SAI
= Stmt
->getParent()->createScopArrayInfo(
1109 MMI
.B
->getElementType(), "Packed_B",
1110 {FirstDimSize
, SecondDimSize
, ThirdDimSize
});
1111 AccRel
= AccRel
.set_tuple_id(isl::dim::out
, SAI
->getBasePtrId());
1112 auto OldAcc
= MMI
.B
->getLatestAccessRelation();
1113 MMI
.B
->setNewAccessRelation(AccRel
);
1114 auto ExtMap
= MapOldIndVar
.project_out(isl::dim::out
, 2,
1115 MapOldIndVar
.dim(isl::dim::out
) - 2);
1116 ExtMap
= ExtMap
.reverse();
1117 ExtMap
= ExtMap
.fix_si(isl::dim::out
, MMI
.i
, 0);
1118 auto Domain
= Stmt
->getDomain();
1120 // Restrict the domains of the copy statements to only execute when also its
1121 // originating statement is executed.
1122 auto DomainId
= Domain
.get_tuple_id();
1123 auto *NewStmt
= Stmt
->getParent()->addScopStmt(
1124 OldAcc
, MMI
.B
->getLatestAccessRelation(), Domain
);
1125 ExtMap
= ExtMap
.set_tuple_id(isl::dim::out
, DomainId
);
1126 ExtMap
= ExtMap
.intersect_range(Domain
);
1127 ExtMap
= ExtMap
.set_tuple_id(isl::dim::out
, NewStmt
->getDomainId());
1128 Node
= createExtensionNode(Node
, ExtMap
);
1130 // Create a copy statement that corresponds to the memory access
1131 // to the matrix A, the first operand of the matrix multiplication.
1132 Node
= Node
.child(0);
1133 AccRel
= getMatMulAccRel(MapOldIndVar
, 4, 6);
1134 FirstDimSize
= MacroParams
.Mc
/ MicroParams
.Mr
;
1135 ThirdDimSize
= MicroParams
.Mr
;
1136 SAI
= Stmt
->getParent()->createScopArrayInfo(
1137 MMI
.A
->getElementType(), "Packed_A",
1138 {FirstDimSize
, SecondDimSize
, ThirdDimSize
});
1139 AccRel
= AccRel
.set_tuple_id(isl::dim::out
, SAI
->getBasePtrId());
1140 OldAcc
= MMI
.A
->getLatestAccessRelation();
1141 MMI
.A
->setNewAccessRelation(AccRel
);
1142 ExtMap
= MapOldIndVar
.project_out(isl::dim::out
, 3,
1143 MapOldIndVar
.dim(isl::dim::out
) - 3);
1144 ExtMap
= ExtMap
.reverse();
1145 ExtMap
= ExtMap
.fix_si(isl::dim::out
, MMI
.j
, 0);
1146 NewStmt
= Stmt
->getParent()->addScopStmt(
1147 OldAcc
, MMI
.A
->getLatestAccessRelation(), Domain
);
1149 // Restrict the domains of the copy statements to only execute when also its
1150 // originating statement is executed.
1151 ExtMap
= ExtMap
.set_tuple_id(isl::dim::out
, DomainId
);
1152 ExtMap
= ExtMap
.intersect_range(Domain
);
1153 ExtMap
= ExtMap
.set_tuple_id(isl::dim::out
, NewStmt
->getDomainId());
1154 Node
= createExtensionNode(Node
, ExtMap
);
1155 return Node
.child(0).child(0).child(0).child(0).child(0);
1158 /// Get a relation mapping induction variables produced by schedule
1159 /// transformations to the original ones.
1161 /// @param Node The schedule node produced as the result of creation
1162 /// of the BLIS kernels.
1163 /// @param MicroKernelParams, MacroKernelParams Parameters of the BLIS kernel
1164 /// to be taken into account.
1165 /// @return The relation mapping original induction variables to the ones
1166 /// produced by schedule transformation.
1167 /// @see ScheduleTreeOptimizer::createMicroKernel
1168 /// @see ScheduleTreeOptimizer::createMacroKernel
1169 /// @see getMacroKernelParams
1171 getInductionVariablesSubstitution(isl::schedule_node Node
,
1172 MicroKernelParamsTy MicroKernelParams
,
1173 MacroKernelParamsTy MacroKernelParams
) {
1174 auto Child
= Node
.child(0);
1175 auto UnMapOldIndVar
= Child
.get_prefix_schedule_union_map();
1176 auto MapOldIndVar
= isl::map::from_union_map(UnMapOldIndVar
);
1177 if (MapOldIndVar
.dim(isl::dim::out
) > 9)
1178 return MapOldIndVar
.project_out(isl::dim::out
, 0,
1179 MapOldIndVar
.dim(isl::dim::out
) - 9);
1180 return MapOldIndVar
;
1183 /// Isolate a set of partial tile prefixes and unroll the isolated part.
1185 /// The set should ensure that it contains only partial tile prefixes that have
1186 /// exactly Mr x Nr iterations of the two innermost loops produced by
1187 /// the optimization of the matrix multiplication. Mr and Nr are parameters of
1188 /// the micro-kernel.
1190 /// In case of parametric bounds, this helps to auto-vectorize the unrolled
1191 /// innermost loops, using the SLP vectorizer.
1193 /// @param Node The schedule node to be modified.
1194 /// @param MicroKernelParams Parameters of the micro-kernel
1195 /// to be taken into account.
1196 /// @return The modified isl_schedule_node.
1197 static isl::schedule_node
1198 isolateAndUnrollMatMulInnerLoops(isl::schedule_node Node
,
1199 struct MicroKernelParamsTy MicroKernelParams
) {
1200 isl::schedule_node Child
= Node
.get_child(0);
1201 isl::union_map UnMapOldIndVar
= Child
.get_prefix_schedule_relation();
1202 isl::set Prefix
= isl::map::from_union_map(UnMapOldIndVar
).range();
1203 unsigned Dims
= Prefix
.dim(isl::dim::set
);
1204 Prefix
= Prefix
.project_out(isl::dim::set
, Dims
- 1, 1);
1205 Prefix
= getPartialTilePrefixes(Prefix
, MicroKernelParams
.Nr
);
1206 Prefix
= getPartialTilePrefixes(Prefix
, MicroKernelParams
.Mr
);
1208 isl::union_set IsolateOption
=
1209 getIsolateOptions(Prefix
.add_dims(isl::dim::set
, 3), 3);
1210 isl::ctx Ctx
= Node
.get_ctx();
1211 auto Options
= IsolateOption
.unite(getDimOptions(Ctx
, "unroll"));
1212 Options
= Options
.unite(getUnrollIsolatedSetOptions(Ctx
));
1213 Node
= Node
.band_set_ast_build_options(Options
);
1214 Node
= Node
.parent().parent().parent();
1215 IsolateOption
= getIsolateOptions(Prefix
, 3);
1216 Options
= IsolateOption
.unite(getDimOptions(Ctx
, "separate"));
1217 Node
= Node
.band_set_ast_build_options(Options
);
1218 Node
= Node
.child(0).child(0).child(0);
1222 /// Mark @p BasePtr with "Inter iteration alias-free" mark node.
1224 /// @param Node The child of the mark node to be inserted.
1225 /// @param BasePtr The pointer to be marked.
1226 /// @return The modified isl_schedule_node.
1227 static isl::schedule_node
markInterIterationAliasFree(isl::schedule_node Node
,
1233 isl::id::alloc(Node
.get_ctx(), "Inter iteration alias-free", BasePtr
);
1234 return Node
.insert_mark(Id
).child(0);
1237 /// Insert "Loop Vectorizer Disabled" mark node.
1239 /// @param Node The child of the mark node to be inserted.
1240 /// @return The modified isl_schedule_node.
1241 static isl::schedule_node
markLoopVectorizerDisabled(isl::schedule_node Node
) {
1242 auto Id
= isl::id::alloc(Node
.get_ctx(), "Loop Vectorizer Disabled", nullptr);
1243 return Node
.insert_mark(Id
).child(0);
1246 /// Restore the initial ordering of dimensions of the band node
1248 /// In case the band node represents all the dimensions of the iteration
1249 /// domain, recreate the band node to restore the initial ordering of the
1252 /// @param Node The band node to be modified.
1253 /// @return The modified schedule node.
1254 static isl::schedule_node
1255 getBandNodeWithOriginDimOrder(isl::schedule_node Node
) {
1256 assert(isl_schedule_node_get_type(Node
.get()) == isl_schedule_node_band
);
1257 if (isl_schedule_node_get_type(Node
.child(0).get()) != isl_schedule_node_leaf
)
1259 auto Domain
= Node
.get_universe_domain();
1260 assert(isl_union_set_n_set(Domain
.get()) == 1);
1261 if (Node
.get_schedule_depth() != 0 ||
1262 (isl::set(Domain
).dim(isl::dim::set
) !=
1263 isl_schedule_node_band_n_member(Node
.get())))
1265 Node
= isl::manage(isl_schedule_node_delete(Node
.copy()));
1266 auto PartialSchedulePwAff
= Domain
.identity_union_pw_multi_aff();
1267 auto PartialScheduleMultiPwAff
=
1268 isl::multi_union_pw_aff(PartialSchedulePwAff
);
1269 PartialScheduleMultiPwAff
=
1270 PartialScheduleMultiPwAff
.reset_tuple_id(isl::dim::set
);
1271 return Node
.insert_partial_schedule(PartialScheduleMultiPwAff
);
1275 ScheduleTreeOptimizer::optimizeMatMulPattern(isl::schedule_node Node
,
1276 const TargetTransformInfo
*TTI
,
1277 MatMulInfoTy
&MMI
) {
1278 assert(TTI
&& "The target transform info should be provided.");
1279 Node
= markInterIterationAliasFree(
1280 Node
, MMI
.WriteToC
->getLatestScopArrayInfo()->getBasePtr());
1281 int DimOutNum
= isl_schedule_node_band_n_member(Node
.get());
1282 assert(DimOutNum
> 2 && "In case of the matrix multiplication the loop nest "
1283 "and, consequently, the corresponding scheduling "
1284 "functions have at least three dimensions.");
1285 Node
= getBandNodeWithOriginDimOrder(Node
);
1286 Node
= permuteBandNodeDimensions(Node
, MMI
.i
, DimOutNum
- 3);
1287 int NewJ
= MMI
.j
== DimOutNum
- 3 ? MMI
.i
: MMI
.j
;
1288 int NewK
= MMI
.k
== DimOutNum
- 3 ? MMI
.i
: MMI
.k
;
1289 Node
= permuteBandNodeDimensions(Node
, NewJ
, DimOutNum
- 2);
1290 NewK
= NewK
== DimOutNum
- 2 ? NewJ
: NewK
;
1291 Node
= permuteBandNodeDimensions(Node
, NewK
, DimOutNum
- 1);
1292 auto MicroKernelParams
= getMicroKernelParams(TTI
, MMI
);
1293 auto MacroKernelParams
= getMacroKernelParams(TTI
, MicroKernelParams
, MMI
);
1294 Node
= createMacroKernel(Node
, MacroKernelParams
);
1295 Node
= createMicroKernel(Node
, MicroKernelParams
);
1296 if (MacroKernelParams
.Mc
== 1 || MacroKernelParams
.Nc
== 1 ||
1297 MacroKernelParams
.Kc
== 1)
1299 auto MapOldIndVar
= getInductionVariablesSubstitution(Node
, MicroKernelParams
,
1303 Node
= markLoopVectorizerDisabled(Node
.parent()).child(0);
1304 Node
= isolateAndUnrollMatMulInnerLoops(Node
, MicroKernelParams
);
1305 return optimizeDataLayoutMatrMulPattern(Node
, MapOldIndVar
, MicroKernelParams
,
1306 MacroKernelParams
, MMI
);
1309 bool ScheduleTreeOptimizer::isMatrMultPattern(isl::schedule_node Node
,
1310 const Dependences
*D
,
1311 MatMulInfoTy
&MMI
) {
1312 auto PartialSchedule
= isl::manage(
1313 isl_schedule_node_band_get_partial_schedule_union_map(Node
.get()));
1314 Node
= Node
.child(0);
1315 auto LeafType
= isl_schedule_node_get_type(Node
.get());
1316 Node
= Node
.parent();
1317 if (LeafType
!= isl_schedule_node_leaf
||
1318 isl_schedule_node_band_n_member(Node
.get()) < 3 ||
1319 Node
.get_schedule_depth() != 0 ||
1320 isl_union_map_n_map(PartialSchedule
.get()) != 1)
1322 auto NewPartialSchedule
= isl::map::from_union_map(PartialSchedule
);
1323 if (containsMatrMult(NewPartialSchedule
, D
, MMI
))
1328 __isl_give isl_schedule_node
*
1329 ScheduleTreeOptimizer::optimizeBand(__isl_take isl_schedule_node
*Node
,
1331 if (!isTileableBandNode(isl::manage_copy(Node
)))
1334 const OptimizerAdditionalInfoTy
*OAI
=
1335 static_cast<const OptimizerAdditionalInfoTy
*>(User
);
1338 if (PMBasedOpts
&& User
&&
1339 isMatrMultPattern(isl::manage_copy(Node
), OAI
->D
, MMI
)) {
1340 LLVM_DEBUG(dbgs() << "The matrix multiplication pattern was detected\n");
1342 return optimizeMatMulPattern(isl::manage(Node
), OAI
->TTI
, MMI
).release();
1345 return standardBandOpts(isl::manage(Node
), User
).release();
1349 ScheduleTreeOptimizer::optimizeSchedule(isl::schedule Schedule
,
1350 const OptimizerAdditionalInfoTy
*OAI
) {
1351 auto Root
= Schedule
.get_root();
1352 Root
= optimizeScheduleNode(Root
, OAI
);
1353 return Root
.get_schedule();
1356 isl::schedule_node
ScheduleTreeOptimizer::optimizeScheduleNode(
1357 isl::schedule_node Node
, const OptimizerAdditionalInfoTy
*OAI
) {
1358 Node
= isl::manage(isl_schedule_node_map_descendant_bottom_up(
1359 Node
.release(), optimizeBand
,
1360 const_cast<void *>(static_cast<const void *>(OAI
))));
1364 bool ScheduleTreeOptimizer::isProfitableSchedule(Scop
&S
,
1365 isl::schedule NewSchedule
) {
1366 // To understand if the schedule has been optimized we check if the schedule
1367 // has changed at all.
1368 // TODO: We can improve this by tracking if any necessarily beneficial
1369 // transformations have been performed. This can e.g. be tiling, loop
1370 // interchange, or ...) We can track this either at the place where the
1371 // transformation has been performed or, in case of automatic ILP based
1372 // optimizations, by comparing (yet to be defined) performance metrics
1373 // before/after the scheduling optimizer
1374 // (e.g., #stride-one accesses)
1375 auto NewScheduleMap
= NewSchedule
.get_map();
1376 auto OldSchedule
= S
.getSchedule();
1377 assert(OldSchedule
&& "Only IslScheduleOptimizer can insert extension nodes "
1378 "that make Scop::getSchedule() return nullptr.");
1379 bool changed
= !OldSchedule
.is_equal(NewScheduleMap
);
1385 class IslScheduleOptimizer
: public ScopPass
{
1389 explicit IslScheduleOptimizer() : ScopPass(ID
) {}
1391 ~IslScheduleOptimizer() override
{ isl_schedule_free(LastSchedule
); }
1393 /// Optimize the schedule of the SCoP @p S.
1394 bool runOnScop(Scop
&S
) override
;
1396 /// Print the new schedule for the SCoP @p S.
1397 void printScop(raw_ostream
&OS
, Scop
&S
) const override
;
1399 /// Register all analyses and transformation required.
1400 void getAnalysisUsage(AnalysisUsage
&AU
) const override
;
1402 /// Release the internal memory.
1403 void releaseMemory() override
{
1404 isl_schedule_free(LastSchedule
);
1405 LastSchedule
= nullptr;
1409 isl_schedule
*LastSchedule
= nullptr;
1413 char IslScheduleOptimizer::ID
= 0;
1415 /// Collect statistics for the schedule tree.
1417 /// @param Schedule The schedule tree to analyze. If not a schedule tree it is
1419 /// @param Version The version of the schedule tree that is analyzed.
1420 /// 0 for the original schedule tree before any transformation.
1421 /// 1 for the schedule tree after isl's rescheduling.
1422 /// 2 for the schedule tree after optimizations are applied
1423 /// (tiling, pattern matching)
1424 static void walkScheduleTreeForStatistics(isl::schedule Schedule
, int Version
) {
1425 auto Root
= Schedule
.get_root();
1429 isl_schedule_node_foreach_descendant_top_down(
1431 [](__isl_keep isl_schedule_node
*nodeptr
, void *user
) -> isl_bool
{
1432 isl::schedule_node Node
= isl::manage_copy(nodeptr
);
1433 int Version
= *static_cast<int *>(user
);
1435 switch (isl_schedule_node_get_type(Node
.get())) {
1436 case isl_schedule_node_band
: {
1437 NumBands
[Version
]++;
1438 if (isl_schedule_node_band_get_permutable(Node
.get()) ==
1440 NumPermutable
[Version
]++;
1442 int CountMembers
= isl_schedule_node_band_n_member(Node
.get());
1443 NumBandMembers
[Version
] += CountMembers
;
1444 for (int i
= 0; i
< CountMembers
; i
+= 1) {
1445 if (Node
.band_member_get_coincident(i
))
1446 NumCoincident
[Version
]++;
1451 case isl_schedule_node_filter
:
1452 NumFilters
[Version
]++;
1455 case isl_schedule_node_extension
:
1456 NumExtension
[Version
]++;
1463 return isl_bool_true
;
1468 bool IslScheduleOptimizer::runOnScop(Scop
&S
) {
1469 // Skip SCoPs in case they're already optimised by PPCGCodeGeneration
1470 if (S
.isToBeSkipped())
1473 // Skip empty SCoPs but still allow code generation as it will delete the
1474 // loops present but not needed.
1475 if (S
.getSize() == 0) {
1476 S
.markAsOptimized();
1480 const Dependences
&D
=
1481 getAnalysis
<DependenceInfo
>().getDependences(Dependences::AL_Statement
);
1483 if (D
.getSharedIslCtx() != S
.getSharedIslCtx()) {
1484 LLVM_DEBUG(dbgs() << "DependenceInfo for another SCoP/isl_ctx\n");
1488 if (!D
.hasValidDependences())
1491 isl_schedule_free(LastSchedule
);
1492 LastSchedule
= nullptr;
1494 // Build input data.
1496 Dependences::TYPE_RAW
| Dependences::TYPE_WAR
| Dependences::TYPE_WAW
;
1499 if (OptimizeDeps
== "all")
1501 Dependences::TYPE_RAW
| Dependences::TYPE_WAR
| Dependences::TYPE_WAW
;
1502 else if (OptimizeDeps
== "raw")
1503 ProximityKinds
= Dependences::TYPE_RAW
;
1505 errs() << "Do not know how to optimize for '" << OptimizeDeps
<< "'"
1506 << " Falling back to optimizing all dependences.\n";
1508 Dependences::TYPE_RAW
| Dependences::TYPE_WAR
| Dependences::TYPE_WAW
;
1511 isl::union_set Domain
= S
.getDomains();
1517 walkScheduleTreeForStatistics(S
.getScheduleTree(), 0);
1519 isl::union_map Validity
= D
.getDependences(ValidityKinds
);
1520 isl::union_map Proximity
= D
.getDependences(ProximityKinds
);
1522 // Simplify the dependences by removing the constraints introduced by the
1523 // domains. This can speed up the scheduling time significantly, as large
1524 // constant coefficients will be removed from the dependences. The
1525 // introduction of some additional dependences reduces the possible
1526 // transformations, but in most cases, such transformation do not seem to be
1527 // interesting anyway. In some cases this option may stop the scheduler to
1528 // find any schedule.
1529 if (SimplifyDeps
== "yes") {
1530 Validity
= Validity
.gist_domain(Domain
);
1531 Validity
= Validity
.gist_range(Domain
);
1532 Proximity
= Proximity
.gist_domain(Domain
);
1533 Proximity
= Proximity
.gist_range(Domain
);
1534 } else if (SimplifyDeps
!= "no") {
1535 errs() << "warning: Option -polly-opt-simplify-deps should either be 'yes' "
1536 "or 'no'. Falling back to default: 'yes'\n";
1539 LLVM_DEBUG(dbgs() << "\n\nCompute schedule from: ");
1540 LLVM_DEBUG(dbgs() << "Domain := " << Domain
<< ";\n");
1541 LLVM_DEBUG(dbgs() << "Proximity := " << Proximity
<< ";\n");
1542 LLVM_DEBUG(dbgs() << "Validity := " << Validity
<< ";\n");
1544 unsigned IslSerializeSCCs
;
1546 if (FusionStrategy
== "max") {
1547 IslSerializeSCCs
= 0;
1548 } else if (FusionStrategy
== "min") {
1549 IslSerializeSCCs
= 1;
1551 errs() << "warning: Unknown fusion strategy. Falling back to maximal "
1553 IslSerializeSCCs
= 0;
1556 int IslMaximizeBands
;
1558 if (MaximizeBandDepth
== "yes") {
1559 IslMaximizeBands
= 1;
1560 } else if (MaximizeBandDepth
== "no") {
1561 IslMaximizeBands
= 0;
1563 errs() << "warning: Option -polly-opt-maximize-bands should either be 'yes'"
1564 " or 'no'. Falling back to default: 'yes'\n";
1565 IslMaximizeBands
= 1;
1568 int IslOuterCoincidence
;
1570 if (OuterCoincidence
== "yes") {
1571 IslOuterCoincidence
= 1;
1572 } else if (OuterCoincidence
== "no") {
1573 IslOuterCoincidence
= 0;
1575 errs() << "warning: Option -polly-opt-outer-coincidence should either be "
1576 "'yes' or 'no'. Falling back to default: 'no'\n";
1577 IslOuterCoincidence
= 0;
1580 isl_ctx
*Ctx
= S
.getIslCtx().get();
1582 isl_options_set_schedule_outer_coincidence(Ctx
, IslOuterCoincidence
);
1583 isl_options_set_schedule_serialize_sccs(Ctx
, IslSerializeSCCs
);
1584 isl_options_set_schedule_maximize_band_depth(Ctx
, IslMaximizeBands
);
1585 isl_options_set_schedule_max_constant_term(Ctx
, MaxConstantTerm
);
1586 isl_options_set_schedule_max_coefficient(Ctx
, MaxCoefficient
);
1587 isl_options_set_tile_scale_tile_loops(Ctx
, 0);
1589 auto OnErrorStatus
= isl_options_get_on_error(Ctx
);
1590 isl_options_set_on_error(Ctx
, ISL_ON_ERROR_CONTINUE
);
1592 auto SC
= isl::schedule_constraints::on_domain(Domain
);
1593 SC
= SC
.set_proximity(Proximity
);
1594 SC
= SC
.set_validity(Validity
);
1595 SC
= SC
.set_coincidence(Validity
);
1596 auto Schedule
= SC
.compute_schedule();
1597 isl_options_set_on_error(Ctx
, OnErrorStatus
);
1599 walkScheduleTreeForStatistics(Schedule
, 1);
1601 // In cases the scheduler is not able to optimize the code, we just do not
1602 // touch the schedule.
1609 auto *P
= isl_printer_to_str(Ctx
);
1610 P
= isl_printer_set_yaml_style(P
, ISL_YAML_STYLE_BLOCK
);
1611 P
= isl_printer_print_schedule(P
, Schedule
.get());
1612 auto *str
= isl_printer_get_str(P
);
1613 dbgs() << "NewScheduleTree: \n" << str
<< "\n";
1615 isl_printer_free(P
);
1618 Function
&F
= S
.getFunction();
1619 auto *TTI
= &getAnalysis
<TargetTransformInfoWrapperPass
>().getTTI(F
);
1620 const OptimizerAdditionalInfoTy OAI
= {TTI
, const_cast<Dependences
*>(&D
)};
1621 auto NewSchedule
= ScheduleTreeOptimizer::optimizeSchedule(Schedule
, &OAI
);
1622 NewSchedule
= hoistExtensionNodes(NewSchedule
);
1623 walkScheduleTreeForStatistics(NewSchedule
, 2);
1625 if (!ScheduleTreeOptimizer::isProfitableSchedule(S
, NewSchedule
))
1628 auto ScopStats
= S
.getStatistics();
1630 NumAffineLoopsOptimized
+= ScopStats
.NumAffineLoops
;
1631 NumBoxedLoopsOptimized
+= ScopStats
.NumBoxedLoops
;
1633 S
.setScheduleTree(NewSchedule
);
1634 S
.markAsOptimized();
1642 void IslScheduleOptimizer::printScop(raw_ostream
&OS
, Scop
&) const {
1646 OS
<< "Calculated schedule:\n";
1648 if (!LastSchedule
) {
1653 p
= isl_printer_to_str(isl_schedule_get_ctx(LastSchedule
));
1654 p
= isl_printer_print_schedule(p
, LastSchedule
);
1655 ScheduleStr
= isl_printer_get_str(p
);
1656 isl_printer_free(p
);
1658 OS
<< ScheduleStr
<< "\n";
1661 void IslScheduleOptimizer::getAnalysisUsage(AnalysisUsage
&AU
) const {
1662 ScopPass::getAnalysisUsage(AU
);
1663 AU
.addRequired
<DependenceInfo
>();
1664 AU
.addRequired
<TargetTransformInfoWrapperPass
>();
1666 AU
.addPreserved
<DependenceInfo
>();
1669 Pass
*polly::createIslScheduleOptimizerPass() {
1670 return new IslScheduleOptimizer();
1673 INITIALIZE_PASS_BEGIN(IslScheduleOptimizer
, "polly-opt-isl",
1674 "Polly - Optimize schedule of SCoP", false, false);
1675 INITIALIZE_PASS_DEPENDENCY(DependenceInfo
);
1676 INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass
);
1677 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass
);
1678 INITIALIZE_PASS_END(IslScheduleOptimizer
, "polly-opt-isl",
1679 "Polly - Optimize schedule of SCoP", false, false)