Coverage Report

Created: 2017-06-23 12:40

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