Coverage Report

Created: 2017-04-29 12:21

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/Transform/ScheduleOptimizer.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- 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 generates an entirely new schedule tree from the data dependences
11
// and iteration domains. The new schedule tree is computed in two steps:
12
//
13
// 1) The isl scheduling optimizer is run
14
//
15
// The isl scheduling optimizer creates a new schedule tree that maximizes
16
// parallelism and tileability and minimizes data-dependence distances. The
17
// algorithm used is a modified version of the ``Pluto'' algorithm:
18
//
19
//   U. Bondhugula, A. Hartono, J. Ramanujam, and P. Sadayappan.
20
//   A Practical Automatic Polyhedral Parallelizer and Locality Optimizer.
21
//   In Proceedings of the 2008 ACM SIGPLAN Conference On Programming Language
22
//   Design and Implementation, PLDI ’08, pages 101–113. ACM, 2008.
23
//
24
// 2) A set of post-scheduling transformations is applied on the schedule tree.
25
//
26
// These optimizations include:
27
//
28
//  - Tiling of the innermost tilable bands
29
//  - Prevectorization - The choice of a possible outer loop that is strip-mined
30
//                       to the innermost level to enable inner-loop
31
//                       vectorization.
32
//  - Some optimizations for spatial locality are also planned.
33
//
34
// For a detailed description of the schedule tree itself please see section 6
35
// of:
36
//
37
// Polyhedral AST generation is more than scanning polyhedra
38
// Tobias Grosser, Sven Verdoolaege, Albert Cohen
39
// ACM Transactions on Programming Languages and Systems (TOPLAS),
40
// 37(4), July 2015
41
// http://www.grosser.es/#pub-polyhedral-AST-generation
42
//
43
// This publication also contains a detailed discussion of the different options
44
// for polyhedral loop unrolling, full/partial tile separation and other uses
45
// of the schedule tree.
46
//
47
//===----------------------------------------------------------------------===//
48
49
#include "polly/ScheduleOptimizer.h"
50
#include "polly/CodeGen/CodeGeneration.h"
51
#include "polly/DependenceInfo.h"
52
#include "polly/LinkAllPasses.h"
53
#include "polly/Options.h"
54
#include "polly/ScopInfo.h"
55
#include "polly/Support/GICHelper.h"
56
#include "llvm/Analysis/TargetTransformInfo.h"
57
#include "llvm/Support/Debug.h"
58
#include "isl/aff.h"
59
#include "isl/band.h"
60
#include "isl/constraint.h"
61
#include "isl/map.h"
62
#include "isl/options.h"
63
#include "isl/printer.h"
64
#include "isl/schedule.h"
65
#include "isl/schedule_node.h"
66
#include "isl/space.h"
67
#include "isl/union_map.h"
68
#include "isl/union_set.h"
69
70
using namespace llvm;
71
using namespace polly;
72
73
#define DEBUG_TYPE "polly-opt-isl"
74
75
static cl::opt<std::string>
76
    OptimizeDeps("polly-opt-optimize-only",
77
                 cl::desc("Only a certain kind of dependences (all/raw)"),
78
                 cl::Hidden, cl::init("all"), cl::ZeroOrMore,
79
                 cl::cat(PollyCategory));
80
81
static cl::opt<std::string>
82
    SimplifyDeps("polly-opt-simplify-deps",
83
                 cl::desc("Dependences should be simplified (yes/no)"),
84
                 cl::Hidden, cl::init("yes"), cl::ZeroOrMore,
85
                 cl::cat(PollyCategory));
86
87
static cl::opt<int> MaxConstantTerm(
88
    "polly-opt-max-constant-term",
89
    cl::desc("The maximal constant term allowed (-1 is unlimited)"), cl::Hidden,
90
    cl::init(20), cl::ZeroOrMore, cl::cat(PollyCategory));
91
92
static cl::opt<int> MaxCoefficient(
93
    "polly-opt-max-coefficient",
94
    cl::desc("The maximal coefficient allowed (-1 is unlimited)"), cl::Hidden,
95
    cl::init(20), cl::ZeroOrMore, cl::cat(PollyCategory));
96
97
static cl::opt<std::string> FusionStrategy(
98
    "polly-opt-fusion", cl::desc("The fusion strategy to choose (min/max)"),
99
    cl::Hidden, cl::init("min"), cl::ZeroOrMore, cl::cat(PollyCategory));
100
101
static cl::opt<std::string>
102
    MaximizeBandDepth("polly-opt-maximize-bands",
103
                      cl::desc("Maximize the band depth (yes/no)"), cl::Hidden,
104
                      cl::init("yes"), cl::ZeroOrMore, cl::cat(PollyCategory));
105
106
static cl::opt<std::string> OuterCoincidence(
107
    "polly-opt-outer-coincidence",
108
    cl::desc("Try to construct schedules where the outer member of each band "
109
             "satisfies the coincidence constraints (yes/no)"),
110
    cl::Hidden, cl::init("no"), cl::ZeroOrMore, cl::cat(PollyCategory));
111
112
static cl::opt<int> PrevectorWidth(
113
    "polly-prevect-width",
114
    cl::desc(
115
        "The number of loop iterations to strip-mine for pre-vectorization"),
116
    cl::Hidden, cl::init(4), cl::ZeroOrMore, cl::cat(PollyCategory));
117
118
static cl::opt<bool> FirstLevelTiling("polly-tiling",
119
                                      cl::desc("Enable loop tiling"),
120
                                      cl::init(true), cl::ZeroOrMore,
121
                                      cl::cat(PollyCategory));
122
123
static cl::opt<int> LatencyVectorFma(
124
    "polly-target-latency-vector-fma",
125
    cl::desc("The minimal number of cycles between issuing two "
126
             "dependent consecutive vector fused multiply-add "
127
             "instructions."),
128
    cl::Hidden, cl::init(8), cl::ZeroOrMore, cl::cat(PollyCategory));
129
130
static cl::opt<int> ThroughputVectorFma(
131
    "polly-target-throughput-vector-fma",
132
    cl::desc("A throughput of the processor floating-point arithmetic units "
133
             "expressed in the number of vector fused multiply-add "
134
             "instructions per clock cycle."),
135
    cl::Hidden, cl::init(1), cl::ZeroOrMore, cl::cat(PollyCategory));
136
137
// This option, along with --polly-target-2nd-cache-level-associativity,
138
// --polly-target-1st-cache-level-size, and --polly-target-2st-cache-level-size
139
// represent the parameters of the target cache, which do not have typical
140
// values that can be used by default. However, to apply the pattern matching
141
// optimizations, we use the values of the parameters of Intel Core i7-3820
142
// SandyBridge in case the parameters are not specified. Such an approach helps
143
// also to attain the high-performance on IBM POWER System S822 and IBM Power
144
// 730 Express server.
145
static cl::opt<int> FirstCacheLevelAssociativity(
146
    "polly-target-1st-cache-level-associativity",
147
    cl::desc("The associativity of the first cache level."), cl::Hidden,
148
    cl::init(8), cl::ZeroOrMore, cl::cat(PollyCategory));
149
150
static cl::opt<int> SecondCacheLevelAssociativity(
151
    "polly-target-2nd-cache-level-associativity",
152
    cl::desc("The associativity of the second cache level."), cl::Hidden,
153
    cl::init(8), cl::ZeroOrMore, cl::cat(PollyCategory));
154
155
static cl::opt<int> FirstCacheLevelSize(
156
    "polly-target-1st-cache-level-size",
157
    cl::desc("The size of the first cache level specified in bytes."),
158
    cl::Hidden, cl::init(32768), cl::ZeroOrMore, cl::cat(PollyCategory));
159
160
static cl::opt<int> SecondCacheLevelSize(
161
    "polly-target-2nd-cache-level-size",
162
    cl::desc("The size of the second level specified in bytes."), cl::Hidden,
163
    cl::init(262144), cl::ZeroOrMore, cl::cat(PollyCategory));
164
165
static cl::opt<int> VectorRegisterBitwidth(
166
    "polly-target-vector-register-bitwidth",
167
    cl::desc("The size in bits of a vector register (if not set, this "
168
             "information is taken from LLVM's target information."),
169
    cl::Hidden, cl::init(-1), cl::ZeroOrMore, cl::cat(PollyCategory));
170
171
static cl::opt<int> FirstLevelDefaultTileSize(
172
    "polly-default-tile-size",
173
    cl::desc("The default tile size (if not enough were provided by"
174
             " --polly-tile-sizes)"),
175
    cl::Hidden, cl::init(32), cl::ZeroOrMore, cl::cat(PollyCategory));
176
177
static cl::list<int>
178
    FirstLevelTileSizes("polly-tile-sizes",
179
                        cl::desc("A tile size for each loop dimension, filled "
180
                                 "with --polly-default-tile-size"),
181
                        cl::Hidden, cl::ZeroOrMore, cl::CommaSeparated,
182
                        cl::cat(PollyCategory));
183
184
static cl::opt<bool>
185
    SecondLevelTiling("polly-2nd-level-tiling",
186
                      cl::desc("Enable a 2nd level loop of loop tiling"),
187
                      cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
188
189
static cl::opt<int> SecondLevelDefaultTileSize(
190
    "polly-2nd-level-default-tile-size",
191
    cl::desc("The default 2nd-level tile size (if not enough were provided by"
192
             " --polly-2nd-level-tile-sizes)"),
193
    cl::Hidden, cl::init(16), cl::ZeroOrMore, cl::cat(PollyCategory));
194
195
static cl::list<int>
196
    SecondLevelTileSizes("polly-2nd-level-tile-sizes",
197
                         cl::desc("A tile size for each loop dimension, filled "
198
                                  "with --polly-default-tile-size"),
199
                         cl::Hidden, cl::ZeroOrMore, cl::CommaSeparated,
200
                         cl::cat(PollyCategory));
201
202
static cl::opt<bool> RegisterTiling("polly-register-tiling",
203
                                    cl::desc("Enable register tiling"),
204
                                    cl::init(false), cl::ZeroOrMore,
205
                                    cl::cat(PollyCategory));
206
207
static cl::opt<int> RegisterDefaultTileSize(
208
    "polly-register-tiling-default-tile-size",
209
    cl::desc("The default register tile size (if not enough were provided by"
210
             " --polly-register-tile-sizes)"),
211
    cl::Hidden, cl::init(2), cl::ZeroOrMore, cl::cat(PollyCategory));
212
213
static cl::opt<int> PollyPatternMatchingNcQuotient(
214
    "polly-pattern-matching-nc-quotient",
215
    cl::desc("Quotient that is obtained by dividing Nc, the parameter of the"
216
             "macro-kernel, by Nr, the parameter of the micro-kernel"),
217
    cl::Hidden, cl::init(256), cl::ZeroOrMore, cl::cat(PollyCategory));
218
219
static cl::list<int>
220
    RegisterTileSizes("polly-register-tile-sizes",
221
                      cl::desc("A tile size for each loop dimension, filled "
222
                               "with --polly-register-tile-size"),
223
                      cl::Hidden, cl::ZeroOrMore, cl::CommaSeparated,
224
                      cl::cat(PollyCategory));
225
226
static cl::opt<bool>
227
    PMBasedOpts("polly-pattern-matching-based-opts",
228
                cl::desc("Perform optimizations based on pattern matching"),
229
                cl::init(true), cl::ZeroOrMore, cl::cat(PollyCategory));
230
231
static cl::opt<bool> OptimizedScops(
232
    "polly-optimized-scops",
233
    cl::desc("Polly - Dump polyhedral description of Scops optimized with "
234
             "the isl scheduling optimizer and the set of post-scheduling "
235
             "transformations is applied on the schedule tree"),
236
    cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
237
238
/// Create an isl_union_set, which describes the isolate option based on
239
/// IsoalteDomain.
240
///
241
/// @param IsolateDomain An isl_set whose @p OutDimsNum last dimensions should
242
///                      belong to the current band node.
243
/// @param OutDimsNum    A number of dimensions that should belong to
244
///                      the current band node.
245
static __isl_give isl_union_set *
246
33
getIsolateOptions(__isl_take isl_set *IsolateDomain, unsigned OutDimsNum) {
247
33
  auto Dims = isl_set_dim(IsolateDomain, isl_dim_set);
248
33
  assert(OutDimsNum <= Dims &&
249
33
         "The isl_set IsolateDomain is used to describe the range of schedule "
250
33
         "dimensions values, which should be isolated. Consequently, the "
251
33
         "number of its dimensions should be greater than or equal to the "
252
33
         "number of the schedule dimensions.");
253
33
  auto *IsolateRelation = isl_map_from_domain(IsolateDomain);
254
33
  IsolateRelation =
255
33
      isl_map_move_dims(IsolateRelation, isl_dim_out, 0, isl_dim_in,
256
33
                        Dims - OutDimsNum, OutDimsNum);
257
33
  auto *IsolateOption = isl_map_wrap(IsolateRelation);
258
33
  auto *Id = isl_id_alloc(isl_set_get_ctx(IsolateOption), "isolate", nullptr);
259
33
  return isl_union_set_from_set(isl_set_set_tuple_id(IsolateOption, Id));
260
33
}
261
262
/// Create an isl_union_set, which describes the atomic option for the dimension
263
/// of the current node.
264
///
265
/// It may help to reduce the size of generated code.
266
///
267
/// @param Ctx An isl_ctx, which is used to create the isl_union_set.
268
24
static __isl_give isl_union_set *getAtomicOptions(isl_ctx *Ctx) {
269
24
  auto *Space = isl_space_set_alloc(Ctx, 0, 1);
270
24
  auto *AtomicOption = isl_set_universe(Space);
271
24
  auto *Id = isl_id_alloc(Ctx, "atomic", nullptr);
272
24
  return isl_union_set_from_set(isl_set_set_tuple_id(AtomicOption, Id));
273
24
}
274
275
/// Create an isl_union_set, which describes the option of the form
276
/// [isolate[] -> unroll[x]].
277
///
278
/// @param Ctx An isl_ctx, which is used to create the isl_union_set.
279
9
static __isl_give isl_union_set *getUnrollIsolatedSetOptions(isl_ctx *Ctx) {
280
9
  auto *Space = isl_space_alloc(Ctx, 0, 0, 1);
281
9
  auto *UnrollIsolatedSetOption = isl_map_universe(Space);
282
9
  auto *DimInId = isl_id_alloc(Ctx, "isolate", nullptr);
283
9
  auto *DimOutId = isl_id_alloc(Ctx, "unroll", nullptr);
284
9
  UnrollIsolatedSetOption =
285
9
      isl_map_set_tuple_id(UnrollIsolatedSetOption, isl_dim_in, DimInId);
286
9
  UnrollIsolatedSetOption =
287
9
      isl_map_set_tuple_id(UnrollIsolatedSetOption, isl_dim_out, DimOutId);
288
9
  return isl_union_set_from_set(isl_map_wrap(UnrollIsolatedSetOption));
289
9
}
290
291
/// Make the last dimension of Set to take values from 0 to VectorWidth - 1.
292
///
293
/// @param Set         A set, which should be modified.
294
/// @param VectorWidth A parameter, which determines the constraint.
295
static __isl_give isl_set *addExtentConstraints(__isl_take isl_set *Set,
296
33
                                                int VectorWidth) {
297
33
  auto Dims = isl_set_dim(Set, isl_dim_set);
298
33
  auto Space = isl_set_get_space(Set);
299
33
  auto *LocalSpace = isl_local_space_from_space(Space);
300
33
  auto *ExtConstr =
301
33
      isl_constraint_alloc_inequality(isl_local_space_copy(LocalSpace));
302
33
  ExtConstr = isl_constraint_set_constant_si(ExtConstr, 0);
303
33
  ExtConstr =
304
33
      isl_constraint_set_coefficient_si(ExtConstr, isl_dim_set, Dims - 1, 1);
305
33
  Set = isl_set_add_constraint(Set, ExtConstr);
306
33
  ExtConstr = isl_constraint_alloc_inequality(LocalSpace);
307
33
  ExtConstr = isl_constraint_set_constant_si(ExtConstr, VectorWidth - 1);
308
33
  ExtConstr =
309
33
      isl_constraint_set_coefficient_si(ExtConstr, isl_dim_set, Dims - 1, -1);
310
33
  return isl_set_add_constraint(Set, ExtConstr);
311
33
}
312
313
/// Build the desired set of partial tile prefixes.
314
///
315
/// We build a set of partial tile prefixes, which are prefixes of the vector
316
/// loop that have exactly VectorWidth iterations.
317
///
318
/// 1. Get all prefixes of the vector loop.
319
/// 2. Extend it to a set, which has exactly VectorWidth iterations for
320
///    any prefix from the set that was built on the previous step.
321
/// 3. Subtract loop domain from it, project out the vector loop dimension and
322
///    get a set of prefixes, which don't have exactly VectorWidth iterations.
323
/// 4. Subtract it from all prefixes of the vector loop and get the desired
324
///    set.
325
///
326
/// @param ScheduleRange A range of a map, which describes a prefix schedule
327
///                      relation.
328
static __isl_give isl_set *
329
33
getPartialTilePrefixes(__isl_take isl_set *ScheduleRange, int VectorWidth) {
330
33
  auto Dims = isl_set_dim(ScheduleRange, isl_dim_set);
331
33
  auto *LoopPrefixes = isl_set_project_out(isl_set_copy(ScheduleRange),
332
33
                                           isl_dim_set, Dims - 1, 1);
333
33
  auto *ExtentPrefixes =
334
33
      isl_set_add_dims(isl_set_copy(LoopPrefixes), isl_dim_set, 1);
335
33
  ExtentPrefixes = addExtentConstraints(ExtentPrefixes, VectorWidth);
336
33
  auto *BadPrefixes = isl_set_subtract(ExtentPrefixes, ScheduleRange);
337
33
  BadPrefixes = isl_set_project_out(BadPrefixes, isl_dim_set, Dims - 1, 1);
338
33
  return isl_set_subtract(LoopPrefixes, BadPrefixes);
339
33
}
340
341
__isl_give isl_schedule_node *ScheduleTreeOptimizer::isolateFullPartialTiles(
342
15
    __isl_take isl_schedule_node *Node, int VectorWidth) {
343
15
  assert(isl_schedule_node_get_type(Node) == isl_schedule_node_band);
344
15
  Node = isl_schedule_node_child(Node, 0);
345
15
  Node = isl_schedule_node_child(Node, 0);
346
15
  auto *SchedRelUMap = isl_schedule_node_get_prefix_schedule_relation(Node);
347
15
  auto *ScheduleRelation = isl_map_from_union_map(SchedRelUMap);
348
15
  auto *ScheduleRange = isl_map_range(ScheduleRelation);
349
15
  auto *IsolateDomain = getPartialTilePrefixes(ScheduleRange, VectorWidth);
350
15
  auto *AtomicOption = getAtomicOptions(isl_set_get_ctx(IsolateDomain));
351
15
  auto *IsolateOption = getIsolateOptions(IsolateDomain, 1);
352
15
  Node = isl_schedule_node_parent(Node);
353
15
  Node = isl_schedule_node_parent(Node);
354
15
  auto *Options = isl_union_set_union(IsolateOption, AtomicOption);
355
15
  Node = isl_schedule_node_band_set_ast_build_options(Node, Options);
356
15
  return Node;
357
15
}
358
359
__isl_give isl_schedule_node *
360
ScheduleTreeOptimizer::prevectSchedBand(__isl_take isl_schedule_node *Node,
361
                                        unsigned DimToVectorize,
362
15
                                        int VectorWidth) {
363
15
  assert(isl_schedule_node_get_type(Node) == isl_schedule_node_band);
364
15
365
15
  auto Space = isl_schedule_node_band_get_space(Node);
366
15
  auto ScheduleDimensions = isl_space_dim(Space, isl_dim_set);
367
15
  isl_space_free(Space);
368
15
  assert(DimToVectorize < ScheduleDimensions);
369
15
370
15
  if (
DimToVectorize > 015
)
{14
371
14
    Node = isl_schedule_node_band_split(Node, DimToVectorize);
372
14
    Node = isl_schedule_node_child(Node, 0);
373
14
  }
374
15
  if (DimToVectorize < ScheduleDimensions - 1)
375
7
    Node = isl_schedule_node_band_split(Node, 1);
376
15
  Space = isl_schedule_node_band_get_space(Node);
377
15
  auto Sizes = isl_multi_val_zero(Space);
378
15
  auto Ctx = isl_schedule_node_get_ctx(Node);
379
15
  Sizes =
380
15
      isl_multi_val_set_val(Sizes, 0, isl_val_int_from_si(Ctx, VectorWidth));
381
15
  Node = isl_schedule_node_band_tile(Node, Sizes);
382
15
  Node = isolateFullPartialTiles(Node, VectorWidth);
383
15
  Node = isl_schedule_node_child(Node, 0);
384
15
  // Make sure the "trivially vectorizable loop" is not unrolled. Otherwise,
385
15
  // we will have troubles to match it in the backend.
386
15
  Node = isl_schedule_node_band_set_ast_build_options(
387
15
      Node, isl_union_set_read_from_str(Ctx, "{ unroll[x]: 1 = 0 }"));
388
15
  Node = isl_schedule_node_band_sink(Node);
389
15
  Node = isl_schedule_node_child(Node, 0);
390
15
  if (isl_schedule_node_get_type(Node) == isl_schedule_node_leaf)
391
8
    Node = isl_schedule_node_parent(Node);
392
15
  isl_id *LoopMarker = isl_id_alloc(Ctx, "SIMD", nullptr);
393
15
  Node = isl_schedule_node_insert_mark(Node, LoopMarker);
394
15
  return Node;
395
15
}
396
397
__isl_give isl_schedule_node *
398
ScheduleTreeOptimizer::tileNode(__isl_take isl_schedule_node *Node,
399
                                const char *Identifier, ArrayRef<int> TileSizes,
400
51
                                int DefaultTileSize) {
401
51
  auto Ctx = isl_schedule_node_get_ctx(Node);
402
51
  auto Space = isl_schedule_node_band_get_space(Node);
403
51
  auto Dims = isl_space_dim(Space, isl_dim_set);
404
51
  auto Sizes = isl_multi_val_zero(Space);
405
51
  std::string IdentifierString(Identifier);
406
179
  for (unsigned i = 0; 
i < Dims179
;
i++128
)
{128
407
69
    auto tileSize = i < TileSizes.size() ? 
TileSizes[i]69
:
DefaultTileSize59
;
408
128
    Sizes = isl_multi_val_set_val(Sizes, i, isl_val_int_from_si(Ctx, tileSize));
409
128
  }
410
51
  auto TileLoopMarkerStr = IdentifierString + " - Tiles";
411
51
  isl_id *TileLoopMarker =
412
51
      isl_id_alloc(Ctx, TileLoopMarkerStr.c_str(), nullptr);
413
51
  Node = isl_schedule_node_insert_mark(Node, TileLoopMarker);
414
51
  Node = isl_schedule_node_child(Node, 0);
415
51
  Node = isl_schedule_node_band_tile(Node, Sizes);
416
51
  Node = isl_schedule_node_child(Node, 0);
417
51
  auto PointLoopMarkerStr = IdentifierString + " - Points";
418
51
  isl_id *PointLoopMarker =
419
51
      isl_id_alloc(Ctx, PointLoopMarkerStr.c_str(), nullptr);
420
51
  Node = isl_schedule_node_insert_mark(Node, PointLoopMarker);
421
51
  Node = isl_schedule_node_child(Node, 0);
422
51
  return Node;
423
51
}
424
425
__isl_give isl_schedule_node *
426
ScheduleTreeOptimizer::applyRegisterTiling(__isl_take isl_schedule_node *Node,
427
                                           llvm::ArrayRef<int> TileSizes,
428
13
                                           int DefaultTileSize) {
429
13
  auto *Ctx = isl_schedule_node_get_ctx(Node);
430
13
  Node = tileNode(Node, "Register tiling", TileSizes, DefaultTileSize);
431
13
  Node = isl_schedule_node_band_set_ast_build_options(
432
13
      Node, isl_union_set_read_from_str(Ctx, "{unroll[x]}"));
433
13
  return Node;
434
13
}
435
436
namespace {
437
72
bool isSimpleInnermostBand(const isl::schedule_node &Node) {
438
72
  assert(isl_schedule_node_get_type(Node.keep()) == isl_schedule_node_band);
439
72
  assert(isl_schedule_node_n_children(Node.keep()) == 1);
440
72
441
72
  auto ChildType = isl_schedule_node_get_type(Node.child(0).keep());
442
72
443
72
  if (ChildType == isl_schedule_node_leaf)
444
40
    return true;
445
72
446
32
  
if (32
ChildType != isl_schedule_node_sequence32
)
447
31
    return false;
448
32
449
1
  auto Sequence = Node.child(0);
450
1
451
3
  for (int c = 0, nc = isl_schedule_node_n_children(Sequence.keep()); c < nc;
452
2
       
++c2
)
{2
453
2
    auto Child = Sequence.child(c);
454
2
    if (isl_schedule_node_get_type(Child.keep()) != isl_schedule_node_filter)
455
0
      return false;
456
2
    
if (2
isl_schedule_node_get_type(Child.child(0).keep()) !=2
457
2
        isl_schedule_node_leaf)
458
0
      return false;
459
2
  }
460
1
  return true;
461
1
}
462
} // namespace
463
464
bool ScheduleTreeOptimizer::isTileableBandNode(
465
434
    __isl_keep isl_schedule_node *Node) {
466
434
  if (isl_schedule_node_get_type(Node) != isl_schedule_node_band)
467
291
    return false;
468
434
469
143
  
if (143
isl_schedule_node_n_children(Node) != 1143
)
470
0
    return false;
471
143
472
143
  
if (143
!isl_schedule_node_band_get_permutable(Node)143
)
473
30
    return false;
474
143
475
113
  auto Space = isl_schedule_node_band_get_space(Node);
476
113
  auto Dims = isl_space_dim(Space, isl_dim_set);
477
113
  isl_space_free(Space);
478
113
479
113
  if (Dims <= 1)
480
41
    return false;
481
113
482
72
  auto ManagedNode = isl::manage(isl_schedule_node_copy(Node));
483
72
  return isSimpleInnermostBand(ManagedNode);
484
113
}
485
486
__isl_give isl_schedule_node *
487
ScheduleTreeOptimizer::standardBandOpts(__isl_take isl_schedule_node *Node,
488
30
                                        void *User) {
489
30
  if (FirstLevelTiling)
490
26
    Node = tileNode(Node, "1st level tiling", FirstLevelTileSizes,
491
26
                    FirstLevelDefaultTileSize);
492
30
493
30
  if (SecondLevelTiling)
494
3
    Node = tileNode(Node, "2nd level tiling", SecondLevelTileSizes,
495
3
                    SecondLevelDefaultTileSize);
496
30
497
30
  if (RegisterTiling)
498
2
    Node =
499
2
        applyRegisterTiling(Node, RegisterTileSizes, RegisterDefaultTileSize);
500
30
501
30
  if (PollyVectorizerChoice == VECTORIZER_NONE)
502
15
    return Node;
503
30
504
15
  auto Space = isl_schedule_node_band_get_space(Node);
505
15
  auto Dims = isl_space_dim(Space, isl_dim_set);
506
15
  isl_space_free(Space);
507
15
508
22
  for (int i = Dims - 1; 
i >= 022
;
i--7
)
509
22
    
if (22
isl_schedule_node_band_member_get_coincident(Node, i)22
)
{15
510
15
      Node = prevectSchedBand(Node, i, PrevectorWidth);
511
15
      break;
512
15
    }
513
15
514
15
  return Node;
515
30
}
516
517
/// Get the position of a dimension with a non-zero coefficient.
518
///
519
/// Check that isl constraint @p Constraint has only one non-zero
520
/// coefficient for dimensions that have type @p DimType. If this is true,
521
/// return the position of the dimension corresponding to the non-zero
522
/// coefficient and negative value, otherwise.
523
///
524
/// @param Constraint The isl constraint to be checked.
525
/// @param DimType    The type of the dimensions.
526
/// @return           The position of the dimension in case the isl
527
///                   constraint satisfies the requirements, a negative
528
///                   value, otherwise.
529
static int getMatMulConstraintDim(__isl_keep isl_constraint *Constraint,
530
264
                                  enum isl_dim_type DimType) {
531
264
  int DimPos = -1;
532
264
  auto *LocalSpace = isl_constraint_get_local_space(Constraint);
533
264
  int LocalSpaceDimNum = isl_local_space_dim(LocalSpace, DimType);
534
924
  for (int i = 0; 
i < LocalSpaceDimNum924
;
i++660
)
{660
535
660
    auto *Val = isl_constraint_get_coefficient_val(Constraint, DimType, i);
536
660
    if (
isl_val_is_zero(Val)660
)
{396
537
396
      isl_val_free(Val);
538
396
      continue;
539
396
    }
540
264
    
if (264
DimPos >= 0 || 264
(DimType == isl_dim_out && 264
!isl_val_is_one(Val)132
) ||
541
264
        
(DimType == isl_dim_in && 264
!isl_val_is_negone(Val)132
))
{0
542
0
      isl_val_free(Val);
543
0
      isl_local_space_free(LocalSpace);
544
0
      return -1;
545
0
    }
546
264
    DimPos = i;
547
264
    isl_val_free(Val);
548
264
  }
549
264
  isl_local_space_free(LocalSpace);
550
264
  return DimPos;
551
264
}
552
553
/// Check the form of the isl constraint.
554
///
555
/// Check that the @p DimInPos input dimension of the isl constraint
556
/// @p Constraint has a coefficient that is equal to negative one, the @p
557
/// DimOutPos has a coefficient that is equal to one and others
558
/// have coefficients equal to zero.
559
///
560
/// @param Constraint The isl constraint to be checked.
561
/// @param DimInPos   The input dimension of the isl constraint.
562
/// @param DimOutPos  The output dimension of the isl constraint.
563
/// @return           isl_stat_ok in case the isl constraint satisfies
564
///                   the requirements, isl_stat_error otherwise.
565
static isl_stat isMatMulOperandConstraint(__isl_keep isl_constraint *Constraint,
566
132
                                          int &DimInPos, int &DimOutPos) {
567
132
  auto *Val = isl_constraint_get_constant_val(Constraint);
568
132
  if (
!isl_constraint_is_equality(Constraint) || 132
!isl_val_is_zero(Val)132
)
{0
569
0
    isl_val_free(Val);
570
0
    return isl_stat_error;
571
0
  }
572
132
  isl_val_free(Val);
573
132
  DimInPos = getMatMulConstraintDim(Constraint, isl_dim_in);
574
132
  if (DimInPos < 0)
575
0
    return isl_stat_error;
576
132
  DimOutPos = getMatMulConstraintDim(Constraint, isl_dim_out);
577
132
  if (DimOutPos < 0)
578
0
    return isl_stat_error;
579
132
  return isl_stat_ok;
580
132
}
581
582
/// Check that the access relation corresponds to a non-constant operand
583
/// of the matrix multiplication.
584
///
585
/// Access relations that correspond to non-constant operands of the matrix
586
/// multiplication depend only on two input dimensions and have two output
587
/// dimensions. The function checks that the isl basic map @p bmap satisfies
588
/// the requirements. The two input dimensions can be specified via @p user
589
/// array.
590
///
591
/// @param bmap The isl basic map to be checked.
592
/// @param user The input dimensions of @p bmap.
593
/// @return     isl_stat_ok in case isl basic map satisfies the requirements,
594
///             isl_stat_error otherwise.
595
static isl_stat isMatMulOperandBasicMap(__isl_take isl_basic_map *bmap,
596
78
                                        void *user) {
597
78
  auto *Constraints = isl_basic_map_get_constraint_list(bmap);
598
78
  isl_basic_map_free(bmap);
599
78
  if (
isl_constraint_list_n_constraint(Constraints) != 278
)
{1
600
1
    isl_constraint_list_free(Constraints);
601
1
    return isl_stat_error;
602
1
  }
603
77
  int InPosPair[] = {-1, -1};
604
77
  auto DimInPos = user ? 
static_cast<int *>(user)77
:
InPosPair0
;
605
176
  for (int i = 0; 
i < 2176
;
i++99
)
{132
606
132
    auto *Constraint = isl_constraint_list_get_constraint(Constraints, i);
607
132
    int InPos, OutPos;
608
132
    if (isMatMulOperandConstraint(Constraint, InPos, OutPos) ==
609
132
            isl_stat_error ||
610
132
        
OutPos > 1132
||
(DimInPos[OutPos] >= 0 && 132
DimInPos[OutPos] != InPos110
))
{33
611
33
      isl_constraint_free(Constraint);
612
33
      isl_constraint_list_free(Constraints);
613
33
      return isl_stat_error;
614
33
    }
615
99
    DimInPos[OutPos] = InPos;
616
99
    isl_constraint_free(Constraint);
617
99
  }
618
44
  isl_constraint_list_free(Constraints);
619
44
  return isl_stat_ok;
620
77
}
621
622
/// Permute the two dimensions of the isl map.
623
///
624
/// Permute @p DstPos and @p SrcPos dimensions of the isl map @p Map that
625
/// have type @p DimType.
626
///
627
/// @param Map     The isl map to be modified.
628
/// @param DimType The type of the dimensions.
629
/// @param DstPos  The first dimension.
630
/// @param SrcPos  The second dimension.
631
/// @return        The modified map.
632
__isl_give isl_map *permuteDimensions(__isl_take isl_map *Map,
633
                                      enum isl_dim_type DimType,
634
33
                                      unsigned DstPos, unsigned SrcPos) {
635
33
  assert(DstPos < isl_map_dim(Map, DimType) &&
636
33
         SrcPos < isl_map_dim(Map, DimType));
637
33
  if (DstPos == SrcPos)
638
11
    return Map;
639
22
  isl_id *DimId = nullptr;
640
22
  if (isl_map_has_tuple_id(Map, DimType))
641
0
    DimId = isl_map_get_tuple_id(Map, DimType);
642
22
  auto FreeDim = DimType == isl_dim_in ? 
isl_dim_out0
:
isl_dim_in22
;
643
22
  isl_id *FreeDimId = nullptr;
644
22
  if (isl_map_has_tuple_id(Map, FreeDim))
645
22
    FreeDimId = isl_map_get_tuple_id(Map, FreeDim);
646
22
  auto MaxDim = std::max(DstPos, SrcPos);
647
22
  auto MinDim = std::min(DstPos, SrcPos);
648
22
  Map = isl_map_move_dims(Map, FreeDim, 0, DimType, MaxDim, 1);
649
22
  Map = isl_map_move_dims(Map, FreeDim, 0, DimType, MinDim, 1);
650
22
  Map = isl_map_move_dims(Map, DimType, MinDim, FreeDim, 1, 1);
651
22
  Map = isl_map_move_dims(Map, DimType, MaxDim, FreeDim, 0, 1);
652
22
  if (DimId)
653
0
    Map = isl_map_set_tuple_id(Map, DimType, DimId);
654
22
  if (FreeDimId)
655
22
    Map = isl_map_set_tuple_id(Map, FreeDim, FreeDimId);
656
22
  return Map;
657
33
}
658
659
/// Check the form of the access relation.
660
///
661
/// Check that the access relation @p AccMap has the form M[i][j], where i
662
/// is a @p FirstPos and j is a @p SecondPos.
663
///
664
/// @param AccMap    The access relation to be checked.
665
/// @param FirstPos  The index of the input dimension that is mapped to
666
///                  the first output dimension.
667
/// @param SecondPos The index of the input dimension that is mapped to the
668
///                  second output dimension.
669
/// @return          True in case @p AccMap has the expected form and false,
670
///                  otherwise.
671
static bool isMatMulOperandAcc(__isl_keep isl_map *AccMap, int &FirstPos,
672
78
                               int &SecondPos) {
673
78
  int DimInPos[] = {FirstPos, SecondPos};
674
78
  if (isl_map_foreach_basic_map(AccMap, isMatMulOperandBasicMap,
675
78
                                static_cast<void *>(DimInPos)) != isl_stat_ok ||
676
44
      
DimInPos[0] < 044
||
DimInPos[1] < 044
)
677
34
    return false;
678
44
  FirstPos = DimInPos[0];
679
44
  SecondPos = DimInPos[1];
680
44
  return true;
681
78
}
682
683
/// Does the memory access represent a non-scalar operand of the matrix
684
/// multiplication.
685
///
686
/// Check that the memory access @p MemAccess is the read access to a non-scalar
687
/// operand of the matrix multiplication or its result.
688
///
689
/// @param MemAccess The memory access to be checked.
690
/// @param MMI       Parameters of the matrix multiplication operands.
691
/// @return          True in case the memory access represents the read access
692
///                  to a non-scalar operand of the matrix multiplication and
693
///                  false, otherwise.
694
static bool isMatMulNonScalarReadAccess(MemoryAccess *MemAccess,
695
33
                                        MatMulInfoTy &MMI) {
696
33
  if (
!MemAccess->isArrayKind() || 33
!MemAccess->isRead()33
)
697
0
    return false;
698
33
  isl_map *AccMap = MemAccess->getAccessRelation();
699
33
  if (
isMatMulOperandAcc(AccMap, MMI.i, MMI.j) && 33
!MMI.ReadFromC11
&&
700
11
      
isl_map_n_basic_map(AccMap) == 111
)
{11
701
11
    MMI.ReadFromC = MemAccess;
702
11
    isl_map_free(AccMap);
703
11
    return true;
704
11
  }
705
22
  
if (22
isMatMulOperandAcc(AccMap, MMI.i, MMI.k) && 22
!MMI.A11
&&
706
11
      
isl_map_n_basic_map(AccMap) == 111
)
{11
707
11
    MMI.A = MemAccess;
708
11
    isl_map_free(AccMap);
709
11
    return true;
710
11
  }
711
11
  
if (11
isMatMulOperandAcc(AccMap, MMI.k, MMI.j) && 11
!MMI.B11
&&
712
11
      
isl_map_n_basic_map(AccMap) == 111
)
{11
713
11
    MMI.B = MemAccess;
714
11
    isl_map_free(AccMap);
715
11
    return true;
716
11
  }
717
0
  isl_map_free(AccMap);
718
0
  return false;
719
11
}
720
721
/// Check accesses to operands of the matrix multiplication.
722
///
723
/// Check that accesses of the SCoP statement, which corresponds to
724
/// the partial schedule @p PartialSchedule, are scalar in terms of loops
725
/// containing the matrix multiplication, in case they do not represent
726
/// accesses to the non-scalar operands of the matrix multiplication or
727
/// its result.
728
///
729
/// @param  PartialSchedule The partial schedule of the SCoP statement.
730
/// @param  MMI             Parameters of the matrix multiplication operands.
731
/// @return                 True in case the corresponding SCoP statement
732
///                         represents matrix multiplication and false,
733
///                         otherwise.
734
static bool containsOnlyMatrMultAcc(__isl_keep isl_map *PartialSchedule,
735
11
                                    MatMulInfoTy &MMI) {
736
11
  auto *InputDimId = isl_map_get_tuple_id(PartialSchedule, isl_dim_in);
737
11
  auto *Stmt = static_cast<ScopStmt *>(isl_id_get_user(InputDimId));
738
11
  isl_id_free(InputDimId);
739
11
  unsigned OutDimNum = isl_map_dim(PartialSchedule, isl_dim_out);
740
11
  assert(OutDimNum > 2 && "In case of the matrix multiplication the loop nest "
741
11
                          "and, consequently, the corresponding scheduling "
742
11
                          "functions have at least three dimensions.");
743
11
  auto *MapI = permuteDimensions(isl_map_copy(PartialSchedule), isl_dim_out,
744
11
                                 MMI.i, OutDimNum - 1);
745
11
  auto *MapJ = permuteDimensions(isl_map_copy(PartialSchedule), isl_dim_out,
746
11
                                 MMI.j, OutDimNum - 1);
747
11
  auto *MapK = permuteDimensions(isl_map_copy(PartialSchedule), isl_dim_out,
748
11
                                 MMI.k, OutDimNum - 1);
749
49
  for (auto *MemA = Stmt->begin(); 
MemA != Stmt->end() - 149
;
MemA++38
)
{38
750
38
    auto *MemAccessPtr = *MemA;
751
38
    if (
MemAccessPtr->isArrayKind() && 38
MemAccessPtr != MMI.WriteToC33
&&
752
33
        !isMatMulNonScalarReadAccess(MemAccessPtr, MMI) &&
753
0
        !(MemAccessPtr->isStrideZero(isl_map_copy(MapI)) &&
754
0
          MemAccessPtr->isStrideZero(isl_map_copy(MapJ)) &&
755
0
          
MemAccessPtr->isStrideZero(isl_map_copy(MapK))0
))
{0
756
0
      isl_map_free(MapI);
757
0
      isl_map_free(MapJ);
758
0
      isl_map_free(MapK);
759
0
      return false;
760
0
    }
761
38
  }
762
11
  isl_map_free(MapI);
763
11
  isl_map_free(MapJ);
764
11
  isl_map_free(MapK);
765
11
  return true;
766
11
}
767
768
/// Check for dependencies corresponding to the matrix multiplication.
769
///
770
/// Check that there is only true dependence of the form
771
/// S(..., k, ...) -> S(..., k + 1, …), where S is the SCoP statement
772
/// represented by @p Schedule and k is @p Pos. Such a dependence corresponds
773
/// to the dependency produced by the matrix multiplication.
774
///
775
/// @param  Schedule The schedule of the SCoP statement.
776
/// @param  D The SCoP dependencies.
777
/// @param  Pos The parameter to desribe an acceptable true dependence.
778
///             In case it has a negative value, try to determine its
779
///             acceptable value.
780
/// @return True in case dependencies correspond to the matrix multiplication
781
///         and false, otherwise.
782
static bool containsOnlyMatMulDep(__isl_keep isl_map *Schedule,
783
11
                                  const Dependences *D, int &Pos) {
784
11
  auto *Dep = D->getDependences(Dependences::TYPE_RAW);
785
11
  auto *Red = D->getDependences(Dependences::TYPE_RED);
786
11
  if (Red)
787
11
    Dep = isl_union_map_union(Dep, Red);
788
11
  auto *DomainSpace = isl_space_domain(isl_map_get_space(Schedule));
789
11
  auto *Space = isl_space_map_from_domain_and_range(isl_space_copy(DomainSpace),
790
11
                                                    DomainSpace);
791
11
  auto *Deltas = isl_map_deltas(isl_union_map_extract_map(Dep, Space));
792
11
  isl_union_map_free(Dep);
793
11
  int DeltasDimNum = isl_set_dim(Deltas, isl_dim_set);
794
44
  for (int i = 0; 
i < DeltasDimNum44
;
i++33
)
{33
795
33
    auto *Val = isl_set_plain_get_val_if_fixed(Deltas, isl_dim_set, i);
796
33
    Pos = Pos < 0 && 
isl_val_is_one(Val)33
?
i11
:
Pos22
;
797
33
    if (isl_val_is_nan(Val) ||
798
33
        
!(isl_val_is_zero(Val) || 33
(i == Pos && 11
isl_val_is_one(Val)11
)))
{0
799
0
      isl_val_free(Val);
800
0
      isl_set_free(Deltas);
801
0
      return false;
802
0
    }
803
33
    isl_val_free(Val);
804
33
  }
805
11
  isl_set_free(Deltas);
806
11
  if (
DeltasDimNum == 0 || 11
Pos < 011
)
807
0
    return false;
808
11
  return true;
809
11
}
810
811
/// Check if the SCoP statement could probably be optimized with analytical
812
/// modeling.
813
///
814
/// containsMatrMult tries to determine whether the following conditions
815
/// are true:
816
/// 1. The last memory access modeling an array, MA1, represents writing to
817
///    memory and has the form S(..., i1, ..., i2, ...) -> M(i1, i2) or
818
///    S(..., i2, ..., i1, ...) -> M(i1, i2), where S is the SCoP statement
819
///    under consideration.
820
/// 2. There is only one loop-carried true dependency, and it has the
821
///    form S(..., i3, ...) -> S(..., i3 + 1, ...), and there are no
822
///    loop-carried or anti dependencies.
823
/// 3. SCoP contains three access relations, MA2, MA3, and MA4 that represent
824
///    reading from memory and have the form S(..., i3, ...) -> M(i1, i3),
825
///    S(..., i3, ...) -> M(i3, i2), S(...) -> M(i1, i2), respectively,
826
///    and all memory accesses of the SCoP that are different from MA1, MA2,
827
///    MA3, and MA4 have stride 0, if the innermost loop is exchanged with any
828
///    of loops i1, i2 and i3.
829
///
830
/// @param PartialSchedule The PartialSchedule that contains a SCoP statement
831
///        to check.
832
/// @D     The SCoP dependencies.
833
/// @MMI   Parameters of the matrix multiplication operands.
834
static bool containsMatrMult(__isl_keep isl_map *PartialSchedule,
835
12
                             const Dependences *D, MatMulInfoTy &MMI) {
836
12
  auto *InputDimsId = isl_map_get_tuple_id(PartialSchedule, isl_dim_in);
837
12
  auto *Stmt = static_cast<ScopStmt *>(isl_id_get_user(InputDimsId));
838
12
  isl_id_free(InputDimsId);
839
12
  if (Stmt->size() <= 1)
840
0
    return false;
841
12
  
for (auto *MemA = Stmt->end() - 1; 12
MemA != Stmt->begin()12
;
MemA--0
)
{12
842
12
    auto *MemAccessPtr = *MemA;
843
12
    if (!MemAccessPtr->isArrayKind())
844
0
      continue;
845
12
    
if (12
!MemAccessPtr->isWrite()12
)
846
0
      return false;
847
12
    auto *AccMap = MemAccessPtr->getAccessRelation();
848
12
    if (isl_map_n_basic_map(AccMap) != 1 ||
849
12
        
!isMatMulOperandAcc(AccMap, MMI.i, MMI.j)12
)
{1
850
1
      isl_map_free(AccMap);
851
1
      return false;
852
1
    }
853
11
    isl_map_free(AccMap);
854
11
    MMI.WriteToC = MemAccessPtr;
855
11
    break;
856
12
  }
857
12
858
11
  
if (11
!containsOnlyMatMulDep(PartialSchedule, D, MMI.k)11
)
859
0
    return false;
860
11
861
11
  
if (11
!MMI.WriteToC || 11
!containsOnlyMatrMultAcc(PartialSchedule, MMI)11
)
862
0
    return false;
863
11
864
11
  
if (11
!MMI.A || 11
!MMI.B11
||
!MMI.ReadFromC11
)
865
0
    return false;
866
11
  return true;
867
11
}
868
869
/// Permute two dimensions of the band node.
870
///
871
/// Permute FirstDim and SecondDim dimensions of the Node.
872
///
873
/// @param Node The band node to be modified.
874
/// @param FirstDim The first dimension to be permuted.
875
/// @param SecondDim The second dimension to be permuted.
876
static __isl_give isl_schedule_node *
877
permuteBandNodeDimensions(__isl_take isl_schedule_node *Node, unsigned FirstDim,
878
62
                          unsigned SecondDim) {
879
62
  assert(isl_schedule_node_get_type(Node) == isl_schedule_node_band &&
880
62
         isl_schedule_node_band_n_member(Node) > std::max(FirstDim, SecondDim));
881
62
  auto PartialSchedule = isl_schedule_node_band_get_partial_schedule(Node);
882
62
  auto PartialScheduleFirstDim =
883
62
      isl_multi_union_pw_aff_get_union_pw_aff(PartialSchedule, FirstDim);
884
62
  auto PartialScheduleSecondDim =
885
62
      isl_multi_union_pw_aff_get_union_pw_aff(PartialSchedule, SecondDim);
886
62
  PartialSchedule = isl_multi_union_pw_aff_set_union_pw_aff(
887
62
      PartialSchedule, SecondDim, PartialScheduleFirstDim);
888
62
  PartialSchedule = isl_multi_union_pw_aff_set_union_pw_aff(
889
62
      PartialSchedule, FirstDim, PartialScheduleSecondDim);
890
62
  Node = isl_schedule_node_delete(Node);
891
62
  Node = isl_schedule_node_insert_partial_schedule(Node, PartialSchedule);
892
62
  return Node;
893
62
}
894
895
__isl_give isl_schedule_node *ScheduleTreeOptimizer::createMicroKernel(
896
11
    __isl_take isl_schedule_node *Node, MicroKernelParamsTy MicroKernelParams) {
897
11
  applyRegisterTiling(Node, {MicroKernelParams.Mr, MicroKernelParams.Nr}, 1);
898
11
  Node = isl_schedule_node_parent(isl_schedule_node_parent(Node));
899
11
  Node = permuteBandNodeDimensions(Node, 0, 1);
900
11
  return isl_schedule_node_child(isl_schedule_node_child(Node, 0), 0);
901
11
}
902
903
__isl_give isl_schedule_node *ScheduleTreeOptimizer::createMacroKernel(
904
11
    __isl_take isl_schedule_node *Node, MacroKernelParamsTy MacroKernelParams) {
905
11
  assert(isl_schedule_node_get_type(Node) == isl_schedule_node_band);
906
11
  if (
MacroKernelParams.Mc == 1 && 11
MacroKernelParams.Nc == 12
&&
907
2
      MacroKernelParams.Kc == 1)
908
2
    return Node;
909
9
  int DimOutNum = isl_schedule_node_band_n_member(Node);
910
9
  std::vector<int> TileSizes(DimOutNum, 1);
911
9
  TileSizes[DimOutNum - 3] = MacroKernelParams.Mc;
912
9
  TileSizes[DimOutNum - 2] = MacroKernelParams.Nc;
913
9
  TileSizes[DimOutNum - 1] = MacroKernelParams.Kc;
914
9
  Node = tileNode(Node, "1st level tiling", TileSizes, 1);
915
9
  Node = isl_schedule_node_parent(isl_schedule_node_parent(Node));
916
9
  Node = permuteBandNodeDimensions(Node, DimOutNum - 2, DimOutNum - 1);
917
9
  Node = permuteBandNodeDimensions(Node, DimOutNum - 3, DimOutNum - 1);
918
9
  return isl_schedule_node_child(isl_schedule_node_child(Node, 0), 0);
919
11
}
920
921
/// Get the size of the widest type of the matrix multiplication operands
922
/// in bytes, including alignment padding.
923
///
924
/// @param MMI Parameters of the matrix multiplication operands.
925
/// @return The size of the widest type of the matrix multiplication operands
926
///         in bytes, including alignment padding.
927
9
static uint64_t getMatMulAlignTypeSize(MatMulInfoTy MMI) {
928
9
  auto *S = MMI.A->getStatement()->getParent();
929
9
  auto &DL = S->getFunction().getParent()->getDataLayout();
930
9
  auto ElementSizeA = DL.getTypeAllocSize(MMI.A->getElementType());
931
9
  auto ElementSizeB = DL.getTypeAllocSize(MMI.B->getElementType());
932
9
  auto ElementSizeC = DL.getTypeAllocSize(MMI.WriteToC->getElementType());
933
9
  return std::max({ElementSizeA, ElementSizeB, ElementSizeC});
934
9
}
935
936
/// Get the size of the widest type of the matrix multiplication operands
937
/// in bits.
938
///
939
/// @param MMI Parameters of the matrix multiplication operands.
940
/// @return The size of the widest type of the matrix multiplication operands
941
///         in bits.
942
11
static uint64_t getMatMulTypeSize(MatMulInfoTy MMI) {
943
11
  auto *S = MMI.A->getStatement()->getParent();
944
11
  auto &DL = S->getFunction().getParent()->getDataLayout();
945
11
  auto ElementSizeA = DL.getTypeSizeInBits(MMI.A->getElementType());
946
11
  auto ElementSizeB = DL.getTypeSizeInBits(MMI.B->getElementType());
947
11
  auto ElementSizeC = DL.getTypeSizeInBits(MMI.WriteToC->getElementType());
948
11
  return std::max({ElementSizeA, ElementSizeB, ElementSizeC});
949
11
}
950
951
/// Get parameters of the BLIS micro kernel.
952
///
953
/// We choose the Mr and Nr parameters of the micro kernel to be large enough
954
/// such that no stalls caused by the combination of latencies and dependencies
955
/// are introduced during the updates of the resulting matrix of the matrix
956
/// multiplication. However, they should also be as small as possible to
957
/// release more registers for entries of multiplied matrices.
958
///
959
/// @param TTI Target Transform Info.
960
/// @param MMI Parameters of the matrix multiplication operands.
961
/// @return The structure of type MicroKernelParamsTy.
962
/// @see MicroKernelParamsTy
963
static struct MicroKernelParamsTy
964
11
getMicroKernelParams(const llvm::TargetTransformInfo *TTI, MatMulInfoTy MMI) {
965
11
  assert(TTI && "The target transform info should be provided.");
966
11
967
11
  // Nvec - Number of double-precision floating-point numbers that can be hold
968
11
  // by a vector register. Use 2 by default.
969
11
  long RegisterBitwidth = VectorRegisterBitwidth;
970
11
971
11
  if (RegisterBitwidth == -1)
972
0
    RegisterBitwidth = TTI->getRegisterBitWidth(true);
973
11
  auto ElementSize = getMatMulTypeSize(MMI);
974
11
  assert(ElementSize > 0 && "The element size of the matrix multiplication "
975
11
                            "operands should be greater than zero.");
976
11
  auto Nvec = RegisterBitwidth / ElementSize;
977
11
  if (Nvec == 0)
978
0
    Nvec = 2;
979
11
  int Nr =
980
11
      ceil(sqrt(Nvec * LatencyVectorFma * ThroughputVectorFma) / Nvec) * Nvec;
981
11
  int Mr = ceil(Nvec * LatencyVectorFma * ThroughputVectorFma / Nr);
982
11
  return {Mr, Nr};
983
11
}
984
985
/// Get parameters of the BLIS macro kernel.
986
///
987
/// During the computation of matrix multiplication, blocks of partitioned
988
/// matrices are mapped to different layers of the memory hierarchy.
989
/// To optimize data reuse, blocks should be ideally kept in cache between
990
/// iterations. Since parameters of the macro kernel determine sizes of these
991
/// blocks, there are upper and lower bounds on these parameters.
992
///
993
/// @param MicroKernelParams Parameters of the micro-kernel
994
///                          to be taken into account.
995
/// @param MMI Parameters of the matrix multiplication operands.
996
/// @return The structure of type MacroKernelParamsTy.
997
/// @see MacroKernelParamsTy
998
/// @see MicroKernelParamsTy
999
static struct MacroKernelParamsTy
1000
getMacroKernelParams(const MicroKernelParamsTy &MicroKernelParams,
1001
11
                     MatMulInfoTy MMI) {
1002
11
  // According to www.cs.utexas.edu/users/flame/pubs/TOMS-BLIS-Analytical.pdf,
1003
11
  // it requires information about the first two levels of a cache to determine
1004
11
  // all the parameters of a macro-kernel. It also checks that an associativity
1005
11
  // degree of a cache level is greater than two. Otherwise, another algorithm
1006
11
  // for determination of the parameters should be used.
1007
11
  if (
!(MicroKernelParams.Mr > 0 && 11
MicroKernelParams.Nr > 011
&&
1008
11
        
FirstCacheLevelSize > 011
&&
SecondCacheLevelSize > 010
&&
1009
10
        
FirstCacheLevelAssociativity > 210
&&
SecondCacheLevelAssociativity > 210
))
1010
1
    return {1, 1, 1};
1011
11
  // The quotient should be greater than zero.
1012
10
  
if (10
PollyPatternMatchingNcQuotient <= 010
)
1013
0
    return {1, 1, 1};
1014
10
  int Car = floor(
1015
10
      (FirstCacheLevelAssociativity - 1) /
1016
10
      (1 + static_cast<double>(MicroKernelParams.Nr) / MicroKernelParams.Mr));
1017
10
1018
10
  // Car can be computed to be zero since it is floor to int.
1019
10
  // On Mac OS, division by 0 does not raise a signal. This causes negative
1020
10
  // tile sizes to be computed. Prevent division by 0 Cac by early returning
1021
10
  // if this happens.
1022
10
  if (Car == 0)
1023
1
    return {1, 1, 1};
1024
10
1025
9
  auto ElementSize = getMatMulAlignTypeSize(MMI);
1026
9
  assert(ElementSize > 0 && "The element size of the matrix multiplication "
1027
9
                            "operands should be greater than zero.");
1028
9
  int Kc = (Car * FirstCacheLevelSize) /
1029
9
           (MicroKernelParams.Mr * FirstCacheLevelAssociativity * ElementSize);
1030
9
  double Cac =
1031
9
      static_cast<double>(Kc * ElementSize * SecondCacheLevelAssociativity) /
1032
9
      SecondCacheLevelSize;
1033
9
  int Mc = floor((SecondCacheLevelAssociativity - 2) / Cac);
1034
9
  int Nc = PollyPatternMatchingNcQuotient * MicroKernelParams.Nr;
1035
9
1036
9
  assert(Mc > 0 && Nc > 0 && Kc > 0 &&
1037
9
         "Matrix block sizes should be  greater than zero");
1038
9
  return {Mc, Nc, Kc};
1039
10
}
1040
1041
/// Create an access relation that is specific to
1042
///        the matrix multiplication pattern.
1043
///
1044
/// Create an access relation of the following form:
1045
/// [O0, O1, O2, O3, O4, O5, O6, O7, O8] -> [OI, O5, OJ]
1046
/// where I is @p FirstDim, J is @p SecondDim.
1047
///
1048
/// It can be used, for example, to create relations that helps to consequently
1049
/// access elements of operands of a matrix multiplication after creation of
1050
/// the BLIS micro and macro kernels.
1051
///
1052
/// @see ScheduleTreeOptimizer::createMicroKernel
1053
/// @see ScheduleTreeOptimizer::createMacroKernel
1054
///
1055
/// Subsequently, the described access relation is applied to the range of
1056
/// @p MapOldIndVar, that is used to map original induction variables to
1057
/// the ones, which are produced by schedule transformations. It helps to
1058
/// define relations using a new space and, at the same time, keep them
1059
/// in the original one.
1060
///
1061
/// @param MapOldIndVar The relation, which maps original induction variables
1062
///                     to the ones, which are produced by schedule
1063
///                     transformations.
1064
/// @param FirstDim, SecondDim The input dimensions that are used to define
1065
///        the specified access relation.
1066
/// @return The specified access relation.
1067
__isl_give isl_map *getMatMulAccRel(__isl_take isl_map *MapOldIndVar,
1068
18
                                    unsigned FirstDim, unsigned SecondDim) {
1069
18
  auto *Ctx = isl_map_get_ctx(MapOldIndVar);
1070
18
  auto *AccessRelSpace = isl_space_alloc(Ctx, 0, 9, 3);
1071
18
  auto *AccessRel = isl_map_universe(AccessRelSpace);
1072
18
  AccessRel = isl_map_equate(AccessRel, isl_dim_in, FirstDim, isl_dim_out, 0);
1073
18
  AccessRel = isl_map_equate(AccessRel, isl_dim_in, 5, isl_dim_out, 1);
1074
18
  AccessRel = isl_map_equate(AccessRel, isl_dim_in, SecondDim, isl_dim_out, 2);
1075
18
  return isl_map_apply_range(MapOldIndVar, AccessRel);
1076
18
}
1077
1078
__isl_give isl_schedule_node *
1079
createExtensionNode(__isl_take isl_schedule_node *Node,
1080
18
                    __isl_take isl_map *ExtensionMap) {
1081
18
  auto *Extension = isl_union_map_from_map(ExtensionMap);
1082
18
  auto *NewNode = isl_schedule_node_from_extension(Extension);
1083
18
  return isl_schedule_node_graft_before(Node, NewNode);
1084
18
}
1085
1086
/// Apply the packing transformation.
1087
///
1088
/// The packing transformation can be described as a data-layout
1089
/// transformation that requires to introduce a new array, copy data
1090
/// to the array, and change memory access locations to reference the array.
1091
/// It can be used to ensure that elements of the new array are read in-stride
1092
/// access, aligned to cache lines boundaries, and preloaded into certain cache
1093
/// levels.
1094
///
1095
/// As an example let us consider the packing of the array A that would help
1096
/// to read its elements with in-stride access. An access to the array A
1097
/// is represented by an access relation that has the form
1098
/// S[i, j, k] -> A[i, k]. The scheduling function of the SCoP statement S has
1099
/// the form S[i,j, k] -> [floor((j mod Nc) / Nr), floor((i mod Mc) / Mr),
1100
/// k mod Kc, j mod Nr, i mod Mr].
1101
///
1102
/// To ensure that elements of the array A are read in-stride access, we add
1103
/// a new array Packed_A[Mc/Mr][Kc][Mr] to the SCoP, using
1104
/// Scop::createScopArrayInfo, change the access relation
1105
/// S[i, j, k] -> A[i, k] to
1106
/// S[i, j, k] -> Packed_A[floor((i mod Mc) / Mr), k mod Kc, i mod Mr], using
1107
/// MemoryAccess::setNewAccessRelation, and copy the data to the array, using
1108
/// the copy statement created by Scop::addScopStmt.
1109
///
1110
/// @param Node The schedule node to be optimized.
1111
/// @param MapOldIndVar The relation, which maps original induction variables
1112
///                     to the ones, which are produced by schedule
1113
///                     transformations.
1114
/// @param MicroParams, MacroParams Parameters of the BLIS kernel
1115
///                                 to be taken into account.
1116
/// @param MMI Parameters of the matrix multiplication operands.
1117
/// @return The optimized schedule node.
1118
static __isl_give isl_schedule_node *optimizeDataLayoutMatrMulPattern(
1119
    __isl_take isl_schedule_node *Node, __isl_take isl_map *MapOldIndVar,
1120
    MicroKernelParamsTy MicroParams, MacroKernelParamsTy MacroParams,
1121
9
    MatMulInfoTy &MMI) {
1122
9
  auto InputDimsId = isl_map_get_tuple_id(MapOldIndVar, isl_dim_in);
1123
9
  auto *Stmt = static_cast<ScopStmt *>(isl_id_get_user(InputDimsId));
1124
9
  isl_id_free(InputDimsId);
1125
9
1126
9
  // Create a copy statement that corresponds to the memory access to the
1127
9
  // matrix B, the second operand of the matrix multiplication.
1128
9
  Node = isl_schedule_node_parent(isl_schedule_node_parent(Node));
1129
9
  Node = isl_schedule_node_parent(isl_schedule_node_parent(Node));
1130
9
  Node = isl_schedule_node_parent(Node);
1131
9
  Node = isl_schedule_node_child(isl_schedule_node_band_split(Node, 2), 0);
1132
9
  auto *AccRel = getMatMulAccRel(isl_map_copy(MapOldIndVar), 3, 7);
1133
9
  unsigned FirstDimSize = MacroParams.Nc / MicroParams.Nr;
1134
9
  unsigned SecondDimSize = MacroParams.Kc;
1135
9
  unsigned ThirdDimSize = MicroParams.Nr;
1136
9
  auto *SAI = Stmt->getParent()->createScopArrayInfo(
1137
9
      MMI.B->getElementType(), "Packed_B",
1138
9
      {FirstDimSize, SecondDimSize, ThirdDimSize});
1139
9
  AccRel = isl_map_set_tuple_id(AccRel, isl_dim_out, SAI->getBasePtrId());
1140
9
  auto *OldAcc = MMI.B->getAccessRelation();
1141
9
  MMI.B->setNewAccessRelation(AccRel);
1142
9
  auto *ExtMap =
1143
9
      isl_map_project_out(isl_map_copy(MapOldIndVar), isl_dim_out, 2,
1144
9
                          isl_map_dim(MapOldIndVar, isl_dim_out) - 2);
1145
9
  ExtMap = isl_map_reverse(ExtMap);
1146
9
  ExtMap = isl_map_fix_si(ExtMap, isl_dim_out, MMI.i, 0);
1147
9
  auto *Domain = Stmt->getDomain();
1148
9
1149
9
  // Restrict the domains of the copy statements to only execute when also its
1150
9
  // originating statement is executed.
1151
9
  auto *DomainId = isl_set_get_tuple_id(Domain);
1152
9
  auto *NewStmt = Stmt->getParent()->addScopStmt(
1153
9
      OldAcc, MMI.B->getAccessRelation(), isl_set_copy(Domain));
1154
9
  ExtMap = isl_map_set_tuple_id(ExtMap, isl_dim_out, isl_id_copy(DomainId));
1155
9
  ExtMap = isl_map_intersect_range(ExtMap, isl_set_copy(Domain));
1156
9
  ExtMap = isl_map_set_tuple_id(ExtMap, isl_dim_out, NewStmt->getDomainId());
1157
9
  Node = createExtensionNode(Node, ExtMap);
1158
9
1159
9
  // Create a copy statement that corresponds to the memory access
1160
9
  // to the matrix A, the first operand of the matrix multiplication.
1161
9
  Node = isl_schedule_node_child(Node, 0);
1162
9
  AccRel = getMatMulAccRel(isl_map_copy(MapOldIndVar), 4, 6);
1163
9
  FirstDimSize = MacroParams.Mc / MicroParams.Mr;
1164
9
  ThirdDimSize = MicroParams.Mr;
1165
9
  SAI = Stmt->getParent()->createScopArrayInfo(
1166
9
      MMI.A->getElementType(), "Packed_A",
1167
9
      {FirstDimSize, SecondDimSize, ThirdDimSize});
1168
9
  AccRel = isl_map_set_tuple_id(AccRel, isl_dim_out, SAI->getBasePtrId());
1169
9
  OldAcc = MMI.A->getAccessRelation();
1170
9
  MMI.A->setNewAccessRelation(AccRel);
1171
9
  ExtMap = isl_map_project_out(MapOldIndVar, isl_dim_out, 3,
1172
9
                               isl_map_dim(MapOldIndVar, isl_dim_out) - 3);
1173
9
  ExtMap = isl_map_reverse(ExtMap);
1174
9
  ExtMap = isl_map_fix_si(ExtMap, isl_dim_out, MMI.j, 0);
1175
9
  NewStmt = Stmt->getParent()->addScopStmt(OldAcc, MMI.A->getAccessRelation(),
1176
9
                                           isl_set_copy(Domain));
1177
9
1178
9
  // Restrict the domains of the copy statements to only execute when also its
1179
9
  // originating statement is executed.
1180
9
  ExtMap = isl_map_set_tuple_id(ExtMap, isl_dim_out, DomainId);
1181
9
  ExtMap = isl_map_intersect_range(ExtMap, Domain);
1182
9
  ExtMap = isl_map_set_tuple_id(ExtMap, isl_dim_out, NewStmt->getDomainId());
1183
9
  Node = createExtensionNode(Node, ExtMap);
1184
9
  Node = isl_schedule_node_child(isl_schedule_node_child(Node, 0), 0);
1185
9
  return isl_schedule_node_child(isl_schedule_node_child(Node, 0), 0);
1186
9
}
1187
1188
/// Get a relation mapping induction variables produced by schedule
1189
/// transformations to the original ones.
1190
///
1191
/// @param Node The schedule node produced as the result of creation
1192
///        of the BLIS kernels.
1193
/// @param MicroKernelParams, MacroKernelParams Parameters of the BLIS kernel
1194
///                                             to be taken into account.
1195
/// @return  The relation mapping original induction variables to the ones
1196
///          produced by schedule transformation.
1197
/// @see ScheduleTreeOptimizer::createMicroKernel
1198
/// @see ScheduleTreeOptimizer::createMacroKernel
1199
/// @see getMacroKernelParams
1200
__isl_give isl_map *
1201
getInductionVariablesSubstitution(__isl_take isl_schedule_node *Node,
1202
                                  MicroKernelParamsTy MicroKernelParams,
1203
9
                                  MacroKernelParamsTy MacroKernelParams) {
1204
9
  auto *Child = isl_schedule_node_get_child(Node, 0);
1205
9
  auto *UnMapOldIndVar = isl_schedule_node_get_prefix_schedule_union_map(Child);
1206
9
  isl_schedule_node_free(Child);
1207
9
  auto *MapOldIndVar = isl_map_from_union_map(UnMapOldIndVar);
1208
9
  if (isl_map_dim(MapOldIndVar, isl_dim_out) > 9)
1209
0
    MapOldIndVar =
1210
0
        isl_map_project_out(MapOldIndVar, isl_dim_out, 0,
1211
0
                            isl_map_dim(MapOldIndVar, isl_dim_out) - 9);
1212
9
  return MapOldIndVar;
1213
9
}
1214
1215
/// Isolate a set of partial tile prefixes and unroll the isolated part.
1216
///
1217
/// The set should ensure that it contains only partial tile prefixes that have
1218
/// exactly Mr x Nr iterations of the two innermost loops produced by
1219
/// the optimization of the matrix multiplication. Mr and Nr are parameters of
1220
/// the micro-kernel.
1221
///
1222
/// In case of parametric bounds, this helps to auto-vectorize the unrolled
1223
/// innermost loops, using the SLP vectorizer.
1224
///
1225
/// @param Node              The schedule node to be modified.
1226
/// @param MicroKernelParams Parameters of the micro-kernel
1227
///                          to be taken into account.
1228
/// @return The modified isl_schedule_node.
1229
static __isl_give isl_schedule_node *
1230
isolateAndUnrollMatMulInnerLoops(__isl_take isl_schedule_node *Node,
1231
9
                                 struct MicroKernelParamsTy MicroKernelParams) {
1232
9
  auto *Child = isl_schedule_node_get_child(Node, 0);
1233
9
  auto *UnMapOldIndVar = isl_schedule_node_get_prefix_schedule_relation(Child);
1234
9
  isl_schedule_node_free(Child);
1235
9
  auto *Prefix = isl_map_range(isl_map_from_union_map(UnMapOldIndVar));
1236
9
  auto Dims = isl_set_dim(Prefix, isl_dim_set);
1237
9
  Prefix = isl_set_project_out(Prefix, isl_dim_set, Dims - 1, 1);
1238
9
  Prefix = getPartialTilePrefixes(Prefix, MicroKernelParams.Nr);
1239
9
  Prefix = getPartialTilePrefixes(Prefix, MicroKernelParams.Mr);
1240
9
  auto *IsolateOption = getIsolateOptions(
1241
9
      isl_set_add_dims(isl_set_copy(Prefix), isl_dim_set, 3), 3);
1242
9
  auto *Ctx = isl_schedule_node_get_ctx(Node);
1243
9
  auto *AtomicOption = getAtomicOptions(Ctx);
1244
9
  auto *Options =
1245
9
      isl_union_set_union(IsolateOption, isl_union_set_copy(AtomicOption));
1246
9
  Options = isl_union_set_union(Options, getUnrollIsolatedSetOptions(Ctx));
1247
9
  Node = isl_schedule_node_band_set_ast_build_options(Node, Options);
1248
9
  Node = isl_schedule_node_parent(isl_schedule_node_parent(Node));
1249
9
  IsolateOption = getIsolateOptions(Prefix, 3);
1250
9
  Options = isl_union_set_union(IsolateOption, AtomicOption);
1251
9
  Node = isl_schedule_node_band_set_ast_build_options(Node, Options);
1252
9
  Node = isl_schedule_node_child(isl_schedule_node_child(Node, 0), 0);
1253
9
  return Node;
1254
9
}
1255
1256
/// Mark @p BasePtr with "Inter iteration alias-free" mark node.
1257
///
1258
/// @param Node The child of the mark node to be inserted.
1259
/// @param BasePtr The pointer to be marked.
1260
/// @return The modified isl_schedule_node.
1261
static isl_schedule_node *markInterIterationAliasFree(isl_schedule_node *Node,
1262
11
                                                      llvm::Value *BasePtr) {
1263
11
  if (!BasePtr)
1264
0
    return Node;
1265
11
1266
11
  auto *Ctx = isl_schedule_node_get_ctx(Node);
1267
11
  auto *Id = isl_id_alloc(Ctx, "Inter iteration alias-free", BasePtr);
1268
11
  return isl_schedule_node_child(isl_schedule_node_insert_mark(Node, Id), 0);
1269
11
}
1270
1271
/// Restore the initial ordering of dimensions of the band node
1272
///
1273
/// In case the band node represents all the dimensions of the iteration
1274
/// domain, recreate the band node to restore the initial ordering of the
1275
/// dimensions.
1276
///
1277
/// @param Node The band node to be modified.
1278
/// @return The modified schedule node.
1279
namespace {
1280
11
isl::schedule_node getBandNodeWithOriginDimOrder(isl::schedule_node Node) {
1281
11
  assert(isl_schedule_node_get_type(Node.keep()) == isl_schedule_node_band);
1282
11
  if (isl_schedule_node_get_type(Node.child(0).keep()) !=
1283
11
      isl_schedule_node_leaf)
1284
0
    return Node;
1285
11
  auto Domain = isl::manage(isl_schedule_node_get_universe_domain(Node.keep()));
1286
11
  assert(isl_union_set_n_set(Domain.keep()) == 1);
1287
11
  if (isl_schedule_node_get_schedule_depth(Node.keep()) != 0 ||
1288
11
      (isl::set(isl::manage(Domain.copy())).dim(isl::dim::set) !=
1289
11
       isl_schedule_node_band_n_member(Node.keep())))
1290
0
    return Node;
1291
11
  Node = isl::manage(isl_schedule_node_delete(Node.take()));
1292
11
  auto PartialSchedulePwAff =
1293
11
      isl::manage(isl_union_set_identity_union_pw_multi_aff(Domain.take()));
1294
11
  auto PartialScheduleMultiPwAff =
1295
11
      isl::multi_union_pw_aff(PartialSchedulePwAff);
1296
11
  PartialScheduleMultiPwAff = isl::manage(isl_multi_union_pw_aff_reset_tuple_id(
1297
11
      PartialScheduleMultiPwAff.take(), isl_dim_set));
1298
11
  return isl::manage(isl_schedule_node_insert_partial_schedule(
1299
11
      Node.take(), PartialScheduleMultiPwAff.take()));
1300
11
}
1301
} // namespace
1302
1303
__isl_give isl_schedule_node *ScheduleTreeOptimizer::optimizeMatMulPattern(
1304
    __isl_take isl_schedule_node *Node, const llvm::TargetTransformInfo *TTI,
1305
11
    MatMulInfoTy &MMI) {
1306
11
  assert(TTI && "The target transform info should be provided.");
1307
11
  Node = markInterIterationAliasFree(Node, MMI.WriteToC->getLatestBaseAddr());
1308
11
  int DimOutNum = isl_schedule_node_band_n_member(Node);
1309
11
  assert(DimOutNum > 2 && "In case of the matrix multiplication the loop nest "
1310
11
                          "and, consequently, the corresponding scheduling "
1311
11
                          "functions have at least three dimensions.");
1312
11
  Node = getBandNodeWithOriginDimOrder(isl::manage(Node)).take();
1313
11
  Node = permuteBandNodeDimensions(Node, MMI.i, DimOutNum - 3);
1314
11
  int NewJ = MMI.j == DimOutNum - 3 ? 
MMI.i0
:
MMI.j11
;
1315
11
  int NewK = MMI.k == DimOutNum - 3 ? 
MMI.i0
:
MMI.k11
;
1316
11
  Node = permuteBandNodeDimensions(Node, NewJ, DimOutNum - 2);
1317
11
  NewK = NewK == DimOutNum - 2 ? 
NewJ0
:
NewK11
;
1318
11
  Node = permuteBandNodeDimensions(Node, NewK, DimOutNum - 1);
1319
11
  auto MicroKernelParams = getMicroKernelParams(TTI, MMI);
1320
11
  auto MacroKernelParams = getMacroKernelParams(MicroKernelParams, MMI);
1321
11
  Node = createMacroKernel(Node, MacroKernelParams);
1322
11
  Node = createMicroKernel(Node, MicroKernelParams);
1323
11
  if (
MacroKernelParams.Mc == 1 || 11
MacroKernelParams.Nc == 19
||
1324
9
      MacroKernelParams.Kc == 1)
1325
2
    return Node;
1326
9
  auto *MapOldIndVar = getInductionVariablesSubstitution(
1327
9
      Node, MicroKernelParams, MacroKernelParams);
1328
9
  if (!MapOldIndVar)
1329
0
    return Node;
1330
9
  Node = isolateAndUnrollMatMulInnerLoops(Node, MicroKernelParams);
1331
9
  return optimizeDataLayoutMatrMulPattern(Node, MapOldIndVar, MicroKernelParams,
1332
9
                                          MacroKernelParams, MMI);
1333
9
}
1334
1335
bool ScheduleTreeOptimizer::isMatrMultPattern(
1336
    __isl_keep isl_schedule_node *Node, const Dependences *D,
1337
32
    MatMulInfoTy &MMI) {
1338
32
  auto *PartialSchedule =
1339
32
      isl_schedule_node_band_get_partial_schedule_union_map(Node);
1340
32
  Node = isl_schedule_node_child(Node, 0);
1341
32
  auto LeafType = isl_schedule_node_get_type(Node);
1342
32
  Node = isl_schedule_node_parent(Node);
1343
32
  if (LeafType != isl_schedule_node_leaf ||
1344
31
      isl_schedule_node_band_n_member(Node) < 3 ||
1345
12
      isl_schedule_node_get_schedule_depth(Node) != 0 ||
1346
20
      
isl_union_map_n_map(PartialSchedule) != 112
)
{20
1347
20
    isl_union_map_free(PartialSchedule);
1348
20
    return false;
1349
20
  }
1350
12
  auto *NewPartialSchedule = isl_map_from_union_map(PartialSchedule);
1351
12
  if (
containsMatrMult(NewPartialSchedule, D, MMI)12
)
{11
1352
11
    isl_map_free(NewPartialSchedule);
1353
11
    return true;
1354
11
  }
1355
1
  isl_map_free(NewPartialSchedule);
1356
1
  return false;
1357
12
}
1358
1359
__isl_give isl_schedule_node *
1360
ScheduleTreeOptimizer::optimizeBand(__isl_take isl_schedule_node *Node,
1361
434
                                    void *User) {
1362
434
  if (!isTileableBandNode(Node))
1363
393
    return Node;
1364
434
1365
41
  const OptimizerAdditionalInfoTy *OAI =
1366
41
      static_cast<const OptimizerAdditionalInfoTy *>(User);
1367
41
1368
41
  MatMulInfoTy MMI;
1369
41
  if (
PMBasedOpts && 41
User32
&&
isMatrMultPattern(Node, OAI->D, MMI)32
)
{11
1370
11
    DEBUG(dbgs() << "The matrix multiplication pattern was detected\n");
1371
11
    return optimizeMatMulPattern(Node, OAI->TTI, MMI);
1372
11
  }
1373
41
1374
30
  return standardBandOpts(Node, User);
1375
41
}
1376
1377
__isl_give isl_schedule *
1378
ScheduleTreeOptimizer::optimizeSchedule(__isl_take isl_schedule *Schedule,
1379
33
                                        const OptimizerAdditionalInfoTy *OAI) {
1380
33
  isl_schedule_node *Root = isl_schedule_get_root(Schedule);
1381
33
  Root = optimizeScheduleNode(Root, OAI);
1382
33
  isl_schedule_free(Schedule);
1383
33
  auto S = isl_schedule_node_get_schedule(Root);
1384
33
  isl_schedule_node_free(Root);
1385
33
  return S;
1386
33
}
1387
1388
__isl_give isl_schedule_node *ScheduleTreeOptimizer::optimizeScheduleNode(
1389
33
    __isl_take isl_schedule_node *Node, const OptimizerAdditionalInfoTy *OAI) {
1390
33
  Node = isl_schedule_node_map_descendant_bottom_up(
1391
33
      Node, optimizeBand, const_cast<void *>(static_cast<const void *>(OAI)));
1392
33
  return Node;
1393
33
}
1394
1395
bool ScheduleTreeOptimizer::isProfitableSchedule(
1396
33
    Scop &S, __isl_keep isl_schedule *NewSchedule) {
1397
33
  // To understand if the schedule has been optimized we check if the schedule
1398
33
  // has changed at all.
1399
33
  // TODO: We can improve this by tracking if any necessarily beneficial
1400
33
  // transformations have been performed. This can e.g. be tiling, loop
1401
33
  // interchange, or ...) We can track this either at the place where the
1402
33
  // transformation has been performed or, in case of automatic ILP based
1403
33
  // optimizations, by comparing (yet to be defined) performance metrics
1404
33
  // before/after the scheduling optimizer
1405
33
  // (e.g., #stride-one accesses)
1406
33
  if (S.containsExtensionNode(NewSchedule))
1407
9
    return true;
1408
24
  auto *NewScheduleMap = isl_schedule_get_map(NewSchedule);
1409
24
  isl_union_map *OldSchedule = S.getSchedule();
1410
24
  assert(OldSchedule && "Only IslScheduleOptimizer can insert extension nodes "
1411
24
                        "that make Scop::getSchedule() return nullptr.");
1412
24
  bool changed = !isl_union_map_is_equal(OldSchedule, NewScheduleMap);
1413
24
  isl_union_map_free(OldSchedule);
1414
24
  isl_union_map_free(NewScheduleMap);
1415
24
  return changed;
1416
33
}
1417
1418
namespace {
1419
class IslScheduleOptimizer : public ScopPass {
1420
public:
1421
  static char ID;
1422
35
  explicit IslScheduleOptimizer() : ScopPass(ID) { LastSchedule = nullptr; }
1423
1424
35
  ~IslScheduleOptimizer() { isl_schedule_free(LastSchedule); }
1425
1426
  /// Optimize the schedule of the SCoP @p S.
1427
  bool runOnScop(Scop &S) override;
1428
1429
  /// Print the new schedule for the SCoP @p S.
1430
  void printScop(raw_ostream &OS, Scop &S) const override;
1431
1432
  /// Register all analyses and transformation required.
1433
  void getAnalysisUsage(AnalysisUsage &AU) const override;
1434
1435
  /// Release the internal memory.
1436
155
  void releaseMemory() override {
1437
155
    isl_schedule_free(LastSchedule);
1438
155
    LastSchedule = nullptr;
1439
155
  }
1440
1441
private:
1442
  isl_schedule *LastSchedule;
1443
};
1444
} // namespace
1445
1446
char IslScheduleOptimizer::ID = 0;
1447
1448
34
bool IslScheduleOptimizer::runOnScop(Scop &S) {
1449
34
1450
34
  // Skip empty SCoPs but still allow code generation as it will delete the
1451
34
  // loops present but not needed.
1452
34
  if (
S.getSize() == 034
)
{0
1453
0
    S.markAsOptimized();
1454
0
    return false;
1455
0
  }
1456
34
1457
34
  const Dependences &D =
1458
34
      getAnalysis<DependenceInfo>().getDependences(Dependences::AL_Statement);
1459
34
1460
34
  if (!D.hasValidDependences())
1461
1
    return false;
1462
34
1463
33
  isl_schedule_free(LastSchedule);
1464
33
  LastSchedule = nullptr;
1465
33
1466
33
  // Build input data.
1467
33
  int ValidityKinds =
1468
33
      Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;
1469
33
  int ProximityKinds;
1470
33
1471
33
  if (OptimizeDeps == "all")
1472
33
    ProximityKinds =
1473
33
        Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;
1474
0
  else 
if (0
OptimizeDeps == "raw"0
)
1475
0
    ProximityKinds = Dependences::TYPE_RAW;
1476
0
  else {
1477
0
    errs() << "Do not know how to optimize for '" << OptimizeDeps << "'"
1478
0
           << " Falling back to optimizing all dependences.\n";
1479
0
    ProximityKinds =
1480
0
        Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;
1481
0
  }
1482
33
1483
33
  isl_union_set *Domain = S.getDomains();
1484
33
1485
33
  if (!Domain)
1486
0
    return false;
1487
33
1488
33
  isl_union_map *Validity = D.getDependences(ValidityKinds);
1489
33
  isl_union_map *Proximity = D.getDependences(ProximityKinds);
1490
33
1491
33
  // Simplify the dependences by removing the constraints introduced by the
1492
33
  // domains. This can speed up the scheduling time significantly, as large
1493
33
  // constant coefficients will be removed from the dependences. The
1494
33
  // introduction of some additional dependences reduces the possible
1495
33
  // transformations, but in most cases, such transformation do not seem to be
1496
33
  // interesting anyway. In some cases this option may stop the scheduler to
1497
33
  // find any schedule.
1498
33
  if (
SimplifyDeps == "yes"33
)
{33
1499
33
    Validity = isl_union_map_gist_domain(Validity, isl_union_set_copy(Domain));
1500
33
    Validity = isl_union_map_gist_range(Validity, isl_union_set_copy(Domain));
1501
33
    Proximity =
1502
33
        isl_union_map_gist_domain(Proximity, isl_union_set_copy(Domain));
1503
33
    Proximity = isl_union_map_gist_range(Proximity, isl_union_set_copy(Domain));
1504
0
  } else 
if (0
SimplifyDeps != "no"0
)
{0
1505
0
    errs() << "warning: Option -polly-opt-simplify-deps should either be 'yes' "
1506
0
              "or 'no'. Falling back to default: 'yes'\n";
1507
0
  }
1508
33
1509
33
  DEBUG(dbgs() << "\n\nCompute schedule from: ");
1510
33
  DEBUG(dbgs() << "Domain := " << stringFromIslObj(Domain) << ";\n");
1511
33
  DEBUG(dbgs() << "Proximity := " << stringFromIslObj(Proximity) << ";\n");
1512
33
  DEBUG(dbgs() << "Validity := " << stringFromIslObj(Validity) << ";\n");
1513
33
1514
33
  unsigned IslSerializeSCCs;
1515
33
1516
33
  if (
FusionStrategy == "max"33
)
{2
1517
2
    IslSerializeSCCs = 0;
1518
31
  } else 
if (31
FusionStrategy == "min"31
)
{31
1519
31
    IslSerializeSCCs = 1;
1520
0
  } else {
1521
0
    errs() << "warning: Unknown fusion strategy. Falling back to maximal "
1522
0
              "fusion.\n";
1523
0
    IslSerializeSCCs = 0;
1524
0
  }
1525
33
1526
33
  int IslMaximizeBands;
1527
33
1528
33
  if (
MaximizeBandDepth == "yes"33
)
{33
1529
33
    IslMaximizeBands = 1;
1530
0
  } else 
if (0
MaximizeBandDepth == "no"0
)
{0
1531
0
    IslMaximizeBands = 0;
1532
0
  } else {
1533
0
    errs() << "warning: Option -polly-opt-maximize-bands should either be 'yes'"
1534
0
              " or 'no'. Falling back to default: 'yes'\n";
1535
0
    IslMaximizeBands = 1;
1536
0
  }
1537
33
1538
33
  int IslOuterCoincidence;
1539
33
1540
33
  if (
OuterCoincidence == "yes"33
)
{1
1541
1
    IslOuterCoincidence = 1;
1542
32
  } else 
if (32
OuterCoincidence == "no"32
)
{32
1543
32
    IslOuterCoincidence = 0;
1544
0
  } else {
1545
0
    errs() << "warning: Option -polly-opt-outer-coincidence should either be "
1546
0
              "'yes' or 'no'. Falling back to default: 'no'\n";
1547
0
    IslOuterCoincidence = 0;
1548
0
  }
1549
33
1550
33
  isl_ctx *Ctx = S.getIslCtx();
1551
33
1552
33
  isl_options_set_schedule_outer_coincidence(Ctx, IslOuterCoincidence);
1553
33
  isl_options_set_schedule_serialize_sccs(Ctx, IslSerializeSCCs);
1554
33
  isl_options_set_schedule_maximize_band_depth(Ctx, IslMaximizeBands);
1555
33
  isl_options_set_schedule_max_constant_term(Ctx, MaxConstantTerm);
1556
33
  isl_options_set_schedule_max_coefficient(Ctx, MaxCoefficient);
1557
33
  isl_options_set_tile_scale_tile_loops(Ctx, 0);
1558
33
1559
33
  auto OnErrorStatus = isl_options_get_on_error(Ctx);
1560
33
  isl_options_set_on_error(Ctx, ISL_ON_ERROR_CONTINUE);
1561
33
1562
33
  isl_schedule_constraints *ScheduleConstraints;
1563
33
  ScheduleConstraints = isl_schedule_constraints_on_domain(Domain);
1564
33
  ScheduleConstraints =
1565
33
      isl_schedule_constraints_set_proximity(ScheduleConstraints, Proximity);
1566
33
  ScheduleConstraints = isl_schedule_constraints_set_validity(
1567
33
      ScheduleConstraints, isl_union_map_copy(Validity));
1568
33
  ScheduleConstraints =
1569
33
      isl_schedule_constraints_set_coincidence(ScheduleConstraints, Validity);
1570
33
  isl_schedule *Schedule;
1571
33
  Schedule = isl_schedule_constraints_compute_schedule(ScheduleConstraints);
1572
33
  isl_options_set_on_error(Ctx, OnErrorStatus);
1573
33
1574
33
  // In cases the scheduler is not able to optimize the code, we just do not
1575
33
  // touch the schedule.
1576
33
  if (!Schedule)
1577
0
    return false;
1578
33
1579
33
  
DEBUG33
({33
1580
33
    auto *P = isl_printer_to_str(Ctx);
1581
33
    P = isl_printer_set_yaml_style(P, ISL_YAML_STYLE_BLOCK);
1582
33
    P = isl_printer_print_schedule(P, Schedule);
1583
33
    auto *str = isl_printer_get_str(P);
1584
33
    dbgs() << "NewScheduleTree: \n" << str << "\n";
1585
33
    free(str);
1586
33
    isl_printer_free(P);
1587
33
  });
1588
33
1589
33
  Function &F = S.getFunction();
1590
33
  auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1591
33
  const OptimizerAdditionalInfoTy OAI = {TTI, const_cast<Dependences *>(&D)};
1592
33
  isl_schedule *NewSchedule =
1593
33
      ScheduleTreeOptimizer::optimizeSchedule(Schedule, &OAI);
1594
33
1595
33
  if (
!ScheduleTreeOptimizer::isProfitableSchedule(S, NewSchedule)33
)
{3
1596
3
    isl_schedule_free(NewSchedule);
1597
3
    return false;
1598
3
  }
1599
33
1600
30
  S.setScheduleTree(NewSchedule);
1601
30
  S.markAsOptimized();
1602
30
1603
30
  if (OptimizedScops)
1604
1
    S.dump();
1605
30
1606
30
  return false;
1607
33
}
1608
1609
27
void IslScheduleOptimizer::printScop(raw_ostream &OS, Scop &) const {
1610
27
  isl_printer *p;
1611
27
  char *ScheduleStr;
1612
27
1613
27
  OS << "Calculated schedule:\n";
1614
27
1615
27
  if (
!LastSchedule27
)
{27
1616
27
    OS << "n/a\n";
1617
27
    return;
1618
27
  }
1619
27
1620
0
  p = isl_printer_to_str(isl_schedule_get_ctx(LastSchedule));
1621
0
  p = isl_printer_print_schedule(p, LastSchedule);
1622
0
  ScheduleStr = isl_printer_get_str(p);
1623
0
  isl_printer_free(p);
1624
0
1625
0
  OS << ScheduleStr << "\n";
1626
0
}
1627
1628
35
void IslScheduleOptimizer::getAnalysisUsage(AnalysisUsage &AU) const {
1629
35
  ScopPass::getAnalysisUsage(AU);
1630
35
  AU.addRequired<DependenceInfo>();
1631
35
  AU.addRequired<TargetTransformInfoWrapperPass>();
1632
35
}
1633
1634
0
Pass *polly::createIslScheduleOptimizerPass() {
1635
0
  return new IslScheduleOptimizer();
1636
0
}
1637
1638
39.7k
INITIALIZE_PASS_BEGIN39.7k
(IslScheduleOptimizer, "polly-opt-isl",39.7k
1639
39.7k
                      "Polly - Optimize schedule of SCoP", false, false);
1640
39.7k
INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
1641
39.7k
INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass);
1642
39.7k
INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass);
1643
39.7k
INITIALIZE_PASS_END(IslScheduleOptimizer, "polly-opt-isl",
1644
                    "Polly - Optimize schedule of SCoP", false, false)