Coverage Report

Created: 2017-03-27 23:01

/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
49
                                int DefaultTileSize) {
401
49
  auto Ctx = isl_schedule_node_get_ctx(Node);
402
49
  auto Space = isl_schedule_node_band_get_space(Node);
403
49
  auto Dims = isl_space_dim(Space, isl_dim_set);
404
49
  auto Sizes = isl_multi_val_zero(Space);
405
49
  std::string IdentifierString(Identifier);
406
172
  for (unsigned i = 0; 
i < Dims172
;
i++123
)
{123
407
67
    auto tileSize = i < TileSizes.size() ? 
TileSizes[i]67
:
DefaultTileSize56
;
408
123
    Sizes = isl_multi_val_set_val(Sizes, i, isl_val_int_from_si(Ctx, tileSize));
409
123
  }
410
49
  auto TileLoopMarkerStr = IdentifierString + " - Tiles";
411
49
  isl_id *TileLoopMarker =
412
49
      isl_id_alloc(Ctx, TileLoopMarkerStr.c_str(), nullptr);
413
49
  Node = isl_schedule_node_insert_mark(Node, TileLoopMarker);
414
49
  Node = isl_schedule_node_child(Node, 0);
415
49
  Node = isl_schedule_node_band_tile(Node, Sizes);
416
49
  Node = isl_schedule_node_child(Node, 0);
417
49
  auto PointLoopMarkerStr = IdentifierString + " - Points";
418
49
  isl_id *PointLoopMarker =
419
49
      isl_id_alloc(Ctx, PointLoopMarkerStr.c_str(), nullptr);
420
49
  Node = isl_schedule_node_insert_mark(Node, PointLoopMarker);
421
49
  Node = isl_schedule_node_child(Node, 0);
422
49
  return Node;
423
49
}
424
425
__isl_give isl_schedule_node *
426
ScheduleTreeOptimizer::applyRegisterTiling(__isl_take isl_schedule_node *Node,
427
                                           llvm::ArrayRef<int> TileSizes,
428
12
                                           int DefaultTileSize) {
429
12
  auto *Ctx = isl_schedule_node_get_ctx(Node);
430
12
  Node = tileNode(Node, "Register tiling", TileSizes, DefaultTileSize);
431
12
  Node = isl_schedule_node_band_set_ast_build_options(
432
12
      Node, isl_union_set_read_from_str(Ctx, "{unroll[x]}"));
433
12
  return Node;
434
12
}
435
436
namespace {
437
69
bool isSimpleInnermostBand(const isl::schedule_node &Node) {
438
69
  assert(isl_schedule_node_get_type(Node.keep()) == isl_schedule_node_band);
439
69
  assert(isl_schedule_node_n_children(Node.keep()) == 1);
440
69
441
69
  auto ChildType = isl_schedule_node_get_type(Node.child(0).keep());
442
69
443
69
  if (ChildType == isl_schedule_node_leaf)
444
38
    return true;
445
69
446
31
  
if (31
ChildType != isl_schedule_node_sequence31
)
447
30
    return false;
448
31
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
419
    __isl_keep isl_schedule_node *Node) {
466
419
  if (isl_schedule_node_get_type(Node) != isl_schedule_node_band)
467
280
    return false;
468
419
469
139
  
if (139
isl_schedule_node_n_children(Node) != 1139
)
470
0
    return false;
471
139
472
139
  
if (139
!isl_schedule_node_band_get_permutable(Node)139
)
473
29
    return false;
474
139
475
110
  auto Space = isl_schedule_node_band_get_space(Node);
476
110
  auto Dims = isl_space_dim(Space, isl_dim_set);
477
110
  isl_space_free(Space);
478
110
479
110
  if (Dims <= 1)
480
41
    return false;
481
110
482
69
  auto ManagedNode = isl::manage(isl_schedule_node_copy(Node));
483
69
  return isSimpleInnermostBand(ManagedNode);
484
110
}
485
486
__isl_give isl_schedule_node *
487
ScheduleTreeOptimizer::standardBandOpts(__isl_take isl_schedule_node *Node,
488
29
                                        void *User) {
489
29
  if (FirstLevelTiling)
490
25
    Node = tileNode(Node, "1st level tiling", FirstLevelTileSizes,
491
25
                    FirstLevelDefaultTileSize);
492
29
493
29
  if (SecondLevelTiling)
494
3
    Node = tileNode(Node, "2nd level tiling", SecondLevelTileSizes,
495
3
                    SecondLevelDefaultTileSize);
496
29
497
29
  if (RegisterTiling)
498
2
    Node =
499
2
        applyRegisterTiling(Node, RegisterTileSizes, RegisterDefaultTileSize);
500
29
501
29
  if (PollyVectorizerChoice == VECTORIZER_NONE)
502
14
    return Node;
503
29
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
29
}
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
240
                                  enum isl_dim_type DimType) {
531
240
  int DimPos = -1;
532
240
  auto *LocalSpace = isl_constraint_get_local_space(Constraint);
533
240
  int LocalSpaceDimNum = isl_local_space_dim(LocalSpace, DimType);
534
840
  for (int i = 0; 
i < LocalSpaceDimNum840
;
i++600
)
{600
535
600
    auto *Val = isl_constraint_get_coefficient_val(Constraint, DimType, i);
536
600
    if (
isl_val_is_zero(Val)600
)
{360
537
360
      isl_val_free(Val);
538
360
      continue;
539
360
    }
540
240
    
if (240
DimPos >= 0 || 240
(DimType == isl_dim_out && 240
!isl_val_is_one(Val)120
) ||
541
240
        
(DimType == isl_dim_in && 240
!isl_val_is_negone(Val)120
))
{0
542
0
      isl_val_free(Val);
543
0
      isl_local_space_free(LocalSpace);
544
0
      return -1;
545
0
    }
546
240
    DimPos = i;
547
240
    isl_val_free(Val);
548
240
  }
549
240
  isl_local_space_free(LocalSpace);
550
240
  return DimPos;
551
240
}
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
120
                                          int &DimInPos, int &DimOutPos) {
567
120
  auto *Val = isl_constraint_get_constant_val(Constraint);
568
120
  if (
!isl_constraint_is_equality(Constraint) || 120
!isl_val_is_zero(Val)120
)
{0
569
0
    isl_val_free(Val);
570
0
    return isl_stat_error;
571
0
  }
572
120
  isl_val_free(Val);
573
120
  DimInPos = getMatMulConstraintDim(Constraint, isl_dim_in);
574
120
  if (DimInPos < 0)
575
0
    return isl_stat_error;
576
120
  DimOutPos = getMatMulConstraintDim(Constraint, isl_dim_out);
577
120
  if (DimOutPos < 0)
578
0
    return isl_stat_error;
579
120
  return isl_stat_ok;
580
120
}
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
71
                                        void *user) {
597
71
  auto *Constraints = isl_basic_map_get_constraint_list(bmap);
598
71
  isl_basic_map_free(bmap);
599
71
  if (
isl_constraint_list_n_constraint(Constraints) != 271
)
{1
600
1
    isl_constraint_list_free(Constraints);
601
1
    return isl_stat_error;
602
1
  }
603
70
  int InPosPair[] = {-1, -1};
604
70
  auto DimInPos = user ? 
static_cast<int *>(user)70
:
InPosPair0
;
605
160
  for (int i = 0; 
i < 2160
;
i++90
)
{120
606
120
    auto *Constraint = isl_constraint_list_get_constraint(Constraints, i);
607
120
    int InPos, OutPos;
608
120
    if (isMatMulOperandConstraint(Constraint, InPos, OutPos) ==
609
120
            isl_stat_error ||
610
120
        
OutPos > 1120
||
(DimInPos[OutPos] >= 0 && 120
DimInPos[OutPos] != InPos100
))
{30
611
30
      isl_constraint_free(Constraint);
612
30
      isl_constraint_list_free(Constraints);
613
30
      return isl_stat_error;
614
30
    }
615
90
    DimInPos[OutPos] = InPos;
616
90
    isl_constraint_free(Constraint);
617
90
  }
618
40
  isl_constraint_list_free(Constraints);
619
40
  return isl_stat_ok;
620
70
}
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
30
                                      unsigned DstPos, unsigned SrcPos) {
635
30
  assert(DstPos < isl_map_dim(Map, DimType) &&
636
30
         SrcPos < isl_map_dim(Map, DimType));
637
30
  if (DstPos == SrcPos)
638
10
    return Map;
639
20
  isl_id *DimId = nullptr;
640
20
  if (isl_map_has_tuple_id(Map, DimType))
641
0
    DimId = isl_map_get_tuple_id(Map, DimType);
642
20
  auto FreeDim = DimType == isl_dim_in ? 
isl_dim_out0
:
isl_dim_in20
;
643
20
  isl_id *FreeDimId = nullptr;
644
20
  if (isl_map_has_tuple_id(Map, FreeDim))
645
20
    FreeDimId = isl_map_get_tuple_id(Map, FreeDim);
646
20
  auto MaxDim = std::max(DstPos, SrcPos);
647
20
  auto MinDim = std::min(DstPos, SrcPos);
648
20
  Map = isl_map_move_dims(Map, FreeDim, 0, DimType, MaxDim, 1);
649
20
  Map = isl_map_move_dims(Map, FreeDim, 0, DimType, MinDim, 1);
650
20
  Map = isl_map_move_dims(Map, DimType, MinDim, FreeDim, 1, 1);
651
20
  Map = isl_map_move_dims(Map, DimType, MaxDim, FreeDim, 0, 1);
652
20
  if (DimId)
653
0
    Map = isl_map_set_tuple_id(Map, DimType, DimId);
654
20
  if (FreeDimId)
655
20
    Map = isl_map_set_tuple_id(Map, FreeDim, FreeDimId);
656
20
  return Map;
657
30
}
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
71
                               int &SecondPos) {
673
71
  int DimInPos[] = {FirstPos, SecondPos};
674
71
  if (isl_map_foreach_basic_map(AccMap, isMatMulOperandBasicMap,
675
71
                                static_cast<void *>(DimInPos)) != isl_stat_ok ||
676
40
      
DimInPos[0] < 040
||
DimInPos[1] < 040
)
677
31
    return false;
678
40
  FirstPos = DimInPos[0];
679
40
  SecondPos = DimInPos[1];
680
40
  return true;
681
71
}
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
30
                                        MatMulInfoTy &MMI) {
696
30
  if (
!MemAccess->isArrayKind() || 30
!MemAccess->isRead()30
)
697
0
    return false;
698
30
  isl_map *AccMap = MemAccess->getAccessRelation();
699
30
  if (
isMatMulOperandAcc(AccMap, MMI.i, MMI.j) && 30
!MMI.ReadFromC10
&&
700
10
      
isl_map_n_basic_map(AccMap) == 110
)
{10
701
10
    MMI.ReadFromC = MemAccess;
702
10
    isl_map_free(AccMap);
703
10
    return true;
704
10
  }
705
20
  
if (20
isMatMulOperandAcc(AccMap, MMI.i, MMI.k) && 20
!MMI.A10
&&
706
10
      
isl_map_n_basic_map(AccMap) == 110
)
{10
707
10
    MMI.A = MemAccess;
708
10
    isl_map_free(AccMap);
709
10
    return true;
710
10
  }
711
10
  
if (10
isMatMulOperandAcc(AccMap, MMI.k, MMI.j) && 10
!MMI.B10
&&
712
10
      
isl_map_n_basic_map(AccMap) == 110
)
{10
713
10
    MMI.B = MemAccess;
714
10
    isl_map_free(AccMap);
715
10
    return true;
716
10
  }
717
0
  isl_map_free(AccMap);
718
0
  return false;
719
10
}
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
10
                                    MatMulInfoTy &MMI) {
736
10
  auto *InputDimId = isl_map_get_tuple_id(PartialSchedule, isl_dim_in);
737
10
  auto *Stmt = static_cast<ScopStmt *>(isl_id_get_user(InputDimId));
738
10
  isl_id_free(InputDimId);
739
10
  unsigned OutDimNum = isl_map_dim(PartialSchedule, isl_dim_out);
740
10
  assert(OutDimNum > 2 && "In case of the matrix multiplication the loop nest "
741
10
                          "and, consequently, the corresponding scheduling "
742
10
                          "functions have at least three dimensions.");
743
10
  auto *MapI = permuteDimensions(isl_map_copy(PartialSchedule), isl_dim_out,
744
10
                                 MMI.i, OutDimNum - 1);
745
10
  auto *MapJ = permuteDimensions(isl_map_copy(PartialSchedule), isl_dim_out,
746
10
                                 MMI.j, OutDimNum - 1);
747
10
  auto *MapK = permuteDimensions(isl_map_copy(PartialSchedule), isl_dim_out,
748
10
                                 MMI.k, OutDimNum - 1);
749
45
  for (auto *MemA = Stmt->begin(); 
MemA != Stmt->end() - 145
;
MemA++35
)
{35
750
35
    auto *MemAccessPtr = *MemA;
751
35
    if (
MemAccessPtr->isArrayKind() && 35
MemAccessPtr != MMI.WriteToC30
&&
752
30
        !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
35
  }
762
10
  isl_map_free(MapI);
763
10
  isl_map_free(MapJ);
764
10
  isl_map_free(MapK);
765
10
  return true;
766
10
}
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
10
                                  const Dependences *D, int &Pos) {
784
10
  auto *WAR = D->getDependences(Dependences::TYPE_WAR);
785
10
  if (
!isl_union_map_is_empty(WAR)10
)
{0
786
0
    isl_union_map_free(WAR);
787
0
    return false;
788
0
  }
789
10
  isl_union_map_free(WAR);
790
10
  auto *Dep = D->getDependences(Dependences::TYPE_RAW);
791
10
  auto *Red = D->getDependences(Dependences::TYPE_RED);
792
10
  if (Red)
793
10
    Dep = isl_union_map_union(Dep, Red);
794
10
  auto *DomainSpace = isl_space_domain(isl_map_get_space(Schedule));
795
10
  auto *Space = isl_space_map_from_domain_and_range(isl_space_copy(DomainSpace),
796
10
                                                    DomainSpace);
797
10
  auto *Deltas = isl_map_deltas(isl_union_map_extract_map(Dep, Space));
798
10
  isl_union_map_free(Dep);
799
10
  int DeltasDimNum = isl_set_dim(Deltas, isl_dim_set);
800
40
  for (int i = 0; 
i < DeltasDimNum40
;
i++30
)
{30
801
30
    auto *Val = isl_set_plain_get_val_if_fixed(Deltas, isl_dim_set, i);
802
30
    Pos = Pos < 0 && 
isl_val_is_one(Val)30
?
i10
:
Pos20
;
803
30
    if (isl_val_is_nan(Val) ||
804
30
        
!(isl_val_is_zero(Val) || 30
(i == Pos && 10
isl_val_is_one(Val)10
)))
{0
805
0
      isl_val_free(Val);
806
0
      isl_set_free(Deltas);
807
0
      return false;
808
0
    }
809
30
    isl_val_free(Val);
810
30
  }
811
10
  isl_set_free(Deltas);
812
10
  if (
DeltasDimNum == 0 || 10
Pos < 010
)
813
0
    return false;
814
10
  return true;
815
10
}
816
817
/// Check if the SCoP statement could probably be optimized with analytical
818
/// modeling.
819
///
820
/// containsMatrMult tries to determine whether the following conditions
821
/// are true:
822
/// 1. The last memory access modeling an array, MA1, represents writing to
823
///    memory and has the form S(..., i1, ..., i2, ...) -> M(i1, i2) or
824
///    S(..., i2, ..., i1, ...) -> M(i1, i2), where S is the SCoP statement
825
///    under consideration.
826
/// 2. There is only one loop-carried true dependency, and it has the
827
///    form S(..., i3, ...) -> S(..., i3 + 1, ...), and there are no
828
///    loop-carried or anti dependencies.
829
/// 3. SCoP contains three access relations, MA2, MA3, and MA4 that represent
830
///    reading from memory and have the form S(..., i3, ...) -> M(i1, i3),
831
///    S(..., i3, ...) -> M(i3, i2), S(...) -> M(i1, i2), respectively,
832
///    and all memory accesses of the SCoP that are different from MA1, MA2,
833
///    MA3, and MA4 have stride 0, if the innermost loop is exchanged with any
834
///    of loops i1, i2 and i3.
835
///
836
/// @param PartialSchedule The PartialSchedule that contains a SCoP statement
837
///        to check.
838
/// @D     The SCoP dependencies.
839
/// @MMI   Parameters of the matrix multiplication operands.
840
static bool containsMatrMult(__isl_keep isl_map *PartialSchedule,
841
11
                             const Dependences *D, MatMulInfoTy &MMI) {
842
11
  auto *InputDimsId = isl_map_get_tuple_id(PartialSchedule, isl_dim_in);
843
11
  auto *Stmt = static_cast<ScopStmt *>(isl_id_get_user(InputDimsId));
844
11
  isl_id_free(InputDimsId);
845
11
  if (Stmt->size() <= 1)
846
0
    return false;
847
11
  
for (auto *MemA = Stmt->end() - 1; 11
MemA != Stmt->begin()11
;
MemA--0
)
{11
848
11
    auto *MemAccessPtr = *MemA;
849
11
    if (!MemAccessPtr->isArrayKind())
850
0
      continue;
851
11
    
if (11
!MemAccessPtr->isWrite()11
)
852
0
      return false;
853
11
    auto *AccMap = MemAccessPtr->getAccessRelation();
854
11
    if (isl_map_n_basic_map(AccMap) != 1 ||
855
11
        
!isMatMulOperandAcc(AccMap, MMI.i, MMI.j)11
)
{1
856
1
      isl_map_free(AccMap);
857
1
      return false;
858
1
    }
859
10
    isl_map_free(AccMap);
860
10
    MMI.WriteToC = MemAccessPtr;
861
10
    break;
862
11
  }
863
11
864
10
  
if (10
!containsOnlyMatMulDep(PartialSchedule, D, MMI.k)10
)
865
0
    return false;
866
10
867
10
  
if (10
!MMI.WriteToC || 10
!containsOnlyMatrMultAcc(PartialSchedule, MMI)10
)
868
0
    return false;
869
10
870
10
  
if (10
!MMI.A || 10
!MMI.B10
||
!MMI.ReadFromC10
)
871
0
    return false;
872
10
  return true;
873
10
}
874
875
/// Permute two dimensions of the band node.
876
///
877
/// Permute FirstDim and SecondDim dimensions of the Node.
878
///
879
/// @param Node The band node to be modified.
880
/// @param FirstDim The first dimension to be permuted.
881
/// @param SecondDim The second dimension to be permuted.
882
static __isl_give isl_schedule_node *
883
permuteBandNodeDimensions(__isl_take isl_schedule_node *Node, unsigned FirstDim,
884
58
                          unsigned SecondDim) {
885
58
  assert(isl_schedule_node_get_type(Node) == isl_schedule_node_band &&
886
58
         isl_schedule_node_band_n_member(Node) > std::max(FirstDim, SecondDim));
887
58
  auto PartialSchedule = isl_schedule_node_band_get_partial_schedule(Node);
888
58
  auto PartialScheduleFirstDim =
889
58
      isl_multi_union_pw_aff_get_union_pw_aff(PartialSchedule, FirstDim);
890
58
  auto PartialScheduleSecondDim =
891
58
      isl_multi_union_pw_aff_get_union_pw_aff(PartialSchedule, SecondDim);
892
58
  PartialSchedule = isl_multi_union_pw_aff_set_union_pw_aff(
893
58
      PartialSchedule, SecondDim, PartialScheduleFirstDim);
894
58
  PartialSchedule = isl_multi_union_pw_aff_set_union_pw_aff(
895
58
      PartialSchedule, FirstDim, PartialScheduleSecondDim);
896
58
  Node = isl_schedule_node_delete(Node);
897
58
  Node = isl_schedule_node_insert_partial_schedule(Node, PartialSchedule);
898
58
  return Node;
899
58
}
900
901
__isl_give isl_schedule_node *ScheduleTreeOptimizer::createMicroKernel(
902
10
    __isl_take isl_schedule_node *Node, MicroKernelParamsTy MicroKernelParams) {
903
10
  applyRegisterTiling(Node, {MicroKernelParams.Mr, MicroKernelParams.Nr}, 1);
904
10
  Node = isl_schedule_node_parent(isl_schedule_node_parent(Node));
905
10
  Node = permuteBandNodeDimensions(Node, 0, 1);
906
10
  return isl_schedule_node_child(isl_schedule_node_child(Node, 0), 0);
907
10
}
908
909
__isl_give isl_schedule_node *ScheduleTreeOptimizer::createMacroKernel(
910
10
    __isl_take isl_schedule_node *Node, MacroKernelParamsTy MacroKernelParams) {
911
10
  assert(isl_schedule_node_get_type(Node) == isl_schedule_node_band);
912
10
  if (
MacroKernelParams.Mc == 1 && 10
MacroKernelParams.Nc == 11
&&
913
1
      MacroKernelParams.Kc == 1)
914
1
    return Node;
915
9
  int DimOutNum = isl_schedule_node_band_n_member(Node);
916
9
  std::vector<int> TileSizes(DimOutNum, 1);
917
9
  TileSizes[DimOutNum - 3] = MacroKernelParams.Mc;
918
9
  TileSizes[DimOutNum - 2] = MacroKernelParams.Nc;
919
9
  TileSizes[DimOutNum - 1] = MacroKernelParams.Kc;
920
9
  Node = tileNode(Node, "1st level tiling", TileSizes, 1);
921
9
  Node = isl_schedule_node_parent(isl_schedule_node_parent(Node));
922
9
  Node = permuteBandNodeDimensions(Node, DimOutNum - 2, DimOutNum - 1);
923
9
  Node = permuteBandNodeDimensions(Node, DimOutNum - 3, DimOutNum - 1);
924
9
  return isl_schedule_node_child(isl_schedule_node_child(Node, 0), 0);
925
10
}
926
927
/// Get the size of the widest type of the matrix multiplication operands
928
/// in bytes, including alignment padding.
929
///
930
/// @param MMI Parameters of the matrix multiplication operands.
931
/// @return The size of the widest type of the matrix multiplication operands
932
///         in bytes, including alignment padding.
933
9
static uint64_t getMatMulAlignTypeSize(MatMulInfoTy MMI) {
934
9
  auto *S = MMI.A->getStatement()->getParent();
935
9
  auto &DL = S->getFunction().getParent()->getDataLayout();
936
9
  auto ElementSizeA = DL.getTypeAllocSize(MMI.A->getElementType());
937
9
  auto ElementSizeB = DL.getTypeAllocSize(MMI.B->getElementType());
938
9
  auto ElementSizeC = DL.getTypeAllocSize(MMI.WriteToC->getElementType());
939
9
  return std::max({ElementSizeA, ElementSizeB, ElementSizeC});
940
9
}
941
942
/// Get the size of the widest type of the matrix multiplication operands
943
/// in bits.
944
///
945
/// @param MMI Parameters of the matrix multiplication operands.
946
/// @return The size of the widest type of the matrix multiplication operands
947
///         in bits.
948
10
static uint64_t getMatMulTypeSize(MatMulInfoTy MMI) {
949
10
  auto *S = MMI.A->getStatement()->getParent();
950
10
  auto &DL = S->getFunction().getParent()->getDataLayout();
951
10
  auto ElementSizeA = DL.getTypeSizeInBits(MMI.A->getElementType());
952
10
  auto ElementSizeB = DL.getTypeSizeInBits(MMI.B->getElementType());
953
10
  auto ElementSizeC = DL.getTypeSizeInBits(MMI.WriteToC->getElementType());
954
10
  return std::max({ElementSizeA, ElementSizeB, ElementSizeC});
955
10
}
956
957
/// Get parameters of the BLIS micro kernel.
958
///
959
/// We choose the Mr and Nr parameters of the micro kernel to be large enough
960
/// such that no stalls caused by the combination of latencies and dependencies
961
/// are introduced during the updates of the resulting matrix of the matrix
962
/// multiplication. However, they should also be as small as possible to
963
/// release more registers for entries of multiplied matrices.
964
///
965
/// @param TTI Target Transform Info.
966
/// @param MMI Parameters of the matrix multiplication operands.
967
/// @return The structure of type MicroKernelParamsTy.
968
/// @see MicroKernelParamsTy
969
static struct MicroKernelParamsTy
970
10
getMicroKernelParams(const llvm::TargetTransformInfo *TTI, MatMulInfoTy MMI) {
971
10
  assert(TTI && "The target transform info should be provided.");
972
10
973
10
  // Nvec - Number of double-precision floating-point numbers that can be hold
974
10
  // by a vector register. Use 2 by default.
975
10
  long RegisterBitwidth = VectorRegisterBitwidth;
976
10
977
10
  if (RegisterBitwidth == -1)
978
0
    RegisterBitwidth = TTI->getRegisterBitWidth(true);
979
10
  auto ElementSize = getMatMulTypeSize(MMI);
980
10
  assert(ElementSize > 0 && "The element size of the matrix multiplication "
981
10
                            "operands should be greater than zero.");
982
10
  auto Nvec = RegisterBitwidth / ElementSize;
983
10
  if (Nvec == 0)
984
0
    Nvec = 2;
985
10
  int Nr =
986
10
      ceil(sqrt(Nvec * LatencyVectorFma * ThroughputVectorFma) / Nvec) * Nvec;
987
10
  int Mr = ceil(Nvec * LatencyVectorFma * ThroughputVectorFma / Nr);
988
10
  return {Mr, Nr};
989
10
}
990
991
/// Get parameters of the BLIS macro kernel.
992
///
993
/// During the computation of matrix multiplication, blocks of partitioned
994
/// matrices are mapped to different layers of the memory hierarchy.
995
/// To optimize data reuse, blocks should be ideally kept in cache between
996
/// iterations. Since parameters of the macro kernel determine sizes of these
997
/// blocks, there are upper and lower bounds on these parameters.
998
///
999
/// @param MicroKernelParams Parameters of the micro-kernel
1000
///                          to be taken into account.
1001
/// @param MMI Parameters of the matrix multiplication operands.
1002
/// @return The structure of type MacroKernelParamsTy.
1003
/// @see MacroKernelParamsTy
1004
/// @see MicroKernelParamsTy
1005
static struct MacroKernelParamsTy
1006
getMacroKernelParams(const MicroKernelParamsTy &MicroKernelParams,
1007
10
                     MatMulInfoTy MMI) {
1008
10
  // According to www.cs.utexas.edu/users/flame/pubs/TOMS-BLIS-Analytical.pdf,
1009
10
  // it requires information about the first two levels of a cache to determine
1010
10
  // all the parameters of a macro-kernel. It also checks that an associativity
1011
10
  // degree of a cache level is greater than two. Otherwise, another algorithm
1012
10
  // for determination of the parameters should be used.
1013
10
  if (
!(MicroKernelParams.Mr > 0 && 10
MicroKernelParams.Nr > 010
&&
1014
10
        
FirstCacheLevelSize > 010
&&
SecondCacheLevelSize > 09
&&
1015
9
        
FirstCacheLevelAssociativity > 29
&&
SecondCacheLevelAssociativity > 29
))
1016
1
    return {1, 1, 1};
1017
10
  // The quotient should be greater than zero.
1018
9
  
if (9
PollyPatternMatchingNcQuotient <= 09
)
1019
0
    return {1, 1, 1};
1020
9
  int Car = floor(
1021
9
      (FirstCacheLevelAssociativity - 1) /
1022
9
      (1 + static_cast<double>(MicroKernelParams.Nr) / MicroKernelParams.Mr));
1023
9
  auto ElementSize = getMatMulAlignTypeSize(MMI);
1024
9
  assert(ElementSize > 0 && "The element size of the matrix multiplication "
1025
9
                            "operands should be greater than zero.");
1026
9
  int Kc = (Car * FirstCacheLevelSize) /
1027
9
           (MicroKernelParams.Mr * FirstCacheLevelAssociativity * ElementSize);
1028
9
  double Cac =
1029
9
      static_cast<double>(Kc * ElementSize * SecondCacheLevelAssociativity) /
1030
9
      SecondCacheLevelSize;
1031
9
  int Mc = floor((SecondCacheLevelAssociativity - 2) / Cac);
1032
9
  int Nc = PollyPatternMatchingNcQuotient * MicroKernelParams.Nr;
1033
9
  return {Mc, Nc, Kc};
1034
9
}
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_give isl_schedule_node *
1225
isolateAndUnrollMatMulInnerLoops(__isl_take isl_schedule_node *Node,
1226
9
                                 struct MicroKernelParamsTy MicroKernelParams) {
1227
9
  auto *Child = isl_schedule_node_get_child(Node, 0);
1228
9
  auto *UnMapOldIndVar = isl_schedule_node_get_prefix_schedule_relation(Child);
1229
9
  isl_schedule_node_free(Child);
1230
9
  auto *Prefix = isl_map_range(isl_map_from_union_map(UnMapOldIndVar));
1231
9
  auto Dims = isl_set_dim(Prefix, isl_dim_set);
1232
9
  Prefix = isl_set_project_out(Prefix, isl_dim_set, Dims - 1, 1);
1233
9
  Prefix = getPartialTilePrefixes(Prefix, MicroKernelParams.Nr);
1234
9
  Prefix = getPartialTilePrefixes(Prefix, MicroKernelParams.Mr);
1235
9
  auto *IsolateOption = getIsolateOptions(
1236
9
      isl_set_add_dims(isl_set_copy(Prefix), isl_dim_set, 3), 3);
1237
9
  auto *Ctx = isl_schedule_node_get_ctx(Node);
1238
9
  auto *AtomicOption = getAtomicOptions(Ctx);
1239
9
  auto *Options =
1240
9
      isl_union_set_union(IsolateOption, isl_union_set_copy(AtomicOption));
1241
9
  Options = isl_union_set_union(Options, getUnrollIsolatedSetOptions(Ctx));
1242
9
  Node = isl_schedule_node_band_set_ast_build_options(Node, Options);
1243
9
  Node = isl_schedule_node_parent(isl_schedule_node_parent(Node));
1244
9
  IsolateOption = getIsolateOptions(Prefix, 3);
1245
9
  Options = isl_union_set_union(IsolateOption, AtomicOption);
1246
9
  Node = isl_schedule_node_band_set_ast_build_options(Node, Options);
1247
9
  Node = isl_schedule_node_child(isl_schedule_node_child(Node, 0), 0);
1248
9
  return Node;
1249
9
}
1250
1251
/// Mark @p BasePtr with "Inter iteration alias-free" mark node.
1252
///
1253
/// @param Node The child of the mark node to be inserted.
1254
/// @param BasePtr The pointer to be marked.
1255
/// @return The modified isl_schedule_node.
1256
static isl_schedule_node *markInterIterationAliasFree(isl_schedule_node *Node,
1257
10
                                                      llvm::Value *BasePtr) {
1258
10
  if (!BasePtr)
1259
0
    return Node;
1260
10
1261
10
  auto *Ctx = isl_schedule_node_get_ctx(Node);
1262
10
  auto *Id = isl_id_alloc(Ctx, "Inter iteration alias-free", BasePtr);
1263
10
  return isl_schedule_node_child(isl_schedule_node_insert_mark(Node, Id), 0);
1264
10
}
1265
1266
__isl_give isl_schedule_node *ScheduleTreeOptimizer::optimizeMatMulPattern(
1267
    __isl_take isl_schedule_node *Node, const llvm::TargetTransformInfo *TTI,
1268
10
    MatMulInfoTy &MMI) {
1269
10
  assert(TTI && "The target transform info should be provided.");
1270
10
  Node = markInterIterationAliasFree(Node, MMI.WriteToC->getLatestBaseAddr());
1271
10
  int DimOutNum = isl_schedule_node_band_n_member(Node);
1272
10
  assert(DimOutNum > 2 && "In case of the matrix multiplication the loop nest "
1273
10
                          "and, consequently, the corresponding scheduling "
1274
10
                          "functions have at least three dimensions.");
1275
10
  Node = permuteBandNodeDimensions(Node, MMI.i, DimOutNum - 3);
1276
10
  int NewJ = MMI.j == DimOutNum - 3 ? 
MMI.i0
:
MMI.j10
;
1277
10
  int NewK = MMI.k == DimOutNum - 3 ? 
MMI.i0
:
MMI.k10
;
1278
10
  Node = permuteBandNodeDimensions(Node, NewJ, DimOutNum - 2);
1279
10
  NewK = MMI.k == DimOutNum - 2 ? 
MMI.j0
:
MMI.k10
;
1280
10
  Node = permuteBandNodeDimensions(Node, NewK, DimOutNum - 1);
1281
10
  auto MicroKernelParams = getMicroKernelParams(TTI, MMI);
1282
10
  auto MacroKernelParams = getMacroKernelParams(MicroKernelParams, MMI);
1283
10
  Node = createMacroKernel(Node, MacroKernelParams);
1284
10
  Node = createMicroKernel(Node, MicroKernelParams);
1285
10
  if (
MacroKernelParams.Mc == 1 || 10
MacroKernelParams.Nc == 19
||
1286
9
      MacroKernelParams.Kc == 1)
1287
1
    return Node;
1288
9
  auto *MapOldIndVar = getInductionVariablesSubstitution(
1289
9
      Node, MicroKernelParams, MacroKernelParams);
1290
9
  if (!MapOldIndVar)
1291
0
    return Node;
1292
9
  Node = isolateAndUnrollMatMulInnerLoops(Node, MicroKernelParams);
1293
9
  return optimizeDataLayoutMatrMulPattern(Node, MapOldIndVar, MicroKernelParams,
1294
9
                                          MacroKernelParams, MMI);
1295
9
}
1296
1297
bool ScheduleTreeOptimizer::isMatrMultPattern(
1298
    __isl_keep isl_schedule_node *Node, const Dependences *D,
1299
30
    MatMulInfoTy &MMI) {
1300
30
  auto *PartialSchedule =
1301
30
      isl_schedule_node_band_get_partial_schedule_union_map(Node);
1302
30
  if (isl_schedule_node_band_n_member(Node) < 3 ||
1303
19
      
isl_union_map_n_map(PartialSchedule) != 112
)
{19
1304
19
    isl_union_map_free(PartialSchedule);
1305
19
    return false;
1306
19
  }
1307
11
  auto *NewPartialSchedule = isl_map_from_union_map(PartialSchedule);
1308
11
  if (
containsMatrMult(NewPartialSchedule, D, MMI)11
)
{10
1309
10
    isl_map_free(NewPartialSchedule);
1310
10
    return true;
1311
10
  }
1312
1
  isl_map_free(NewPartialSchedule);
1313
1
  return false;
1314
11
}
1315
1316
__isl_give isl_schedule_node *
1317
ScheduleTreeOptimizer::optimizeBand(__isl_take isl_schedule_node *Node,
1318
419
                                    void *User) {
1319
419
  if (!isTileableBandNode(Node))
1320
380
    return Node;
1321
419
1322
39
  const OptimizerAdditionalInfoTy *OAI =
1323
39
      static_cast<const OptimizerAdditionalInfoTy *>(User);
1324
39
1325
39
  MatMulInfoTy MMI;
1326
39
  if (
PMBasedOpts && 39
User30
&&
isMatrMultPattern(Node, OAI->D, MMI)30
)
{10
1327
10
    DEBUG(dbgs() << "The matrix multiplication pattern was detected\n");
1328
10
    return optimizeMatMulPattern(Node, OAI->TTI, MMI);
1329
10
  }
1330
39
1331
29
  return standardBandOpts(Node, User);
1332
39
}
1333
1334
__isl_give isl_schedule *
1335
ScheduleTreeOptimizer::optimizeSchedule(__isl_take isl_schedule *Schedule,
1336
32
                                        const OptimizerAdditionalInfoTy *OAI) {
1337
32
  isl_schedule_node *Root = isl_schedule_get_root(Schedule);
1338
32
  Root = optimizeScheduleNode(Root, OAI);
1339
32
  isl_schedule_free(Schedule);
1340
32
  auto S = isl_schedule_node_get_schedule(Root);
1341
32
  isl_schedule_node_free(Root);
1342
32
  return S;
1343
32
}
1344
1345
__isl_give isl_schedule_node *ScheduleTreeOptimizer::optimizeScheduleNode(
1346
32
    __isl_take isl_schedule_node *Node, const OptimizerAdditionalInfoTy *OAI) {
1347
32
  Node = isl_schedule_node_map_descendant_bottom_up(
1348
32
      Node, optimizeBand, const_cast<void *>(static_cast<const void *>(OAI)));
1349
32
  return Node;
1350
32
}
1351
1352
bool ScheduleTreeOptimizer::isProfitableSchedule(
1353
32
    Scop &S, __isl_keep isl_schedule *NewSchedule) {
1354
32
  // To understand if the schedule has been optimized we check if the schedule
1355
32
  // has changed at all.
1356
32
  // TODO: We can improve this by tracking if any necessarily beneficial
1357
32
  // transformations have been performed. This can e.g. be tiling, loop
1358
32
  // interchange, or ...) We can track this either at the place where the
1359
32
  // transformation has been performed or, in case of automatic ILP based
1360
32
  // optimizations, by comparing (yet to be defined) performance metrics
1361
32
  // before/after the scheduling optimizer
1362
32
  // (e.g., #stride-one accesses)
1363
32
  if (S.containsExtensionNode(NewSchedule))
1364
9
    return true;
1365
23
  auto *NewScheduleMap = isl_schedule_get_map(NewSchedule);
1366
23
  isl_union_map *OldSchedule = S.getSchedule();
1367
23
  assert(OldSchedule && "Only IslScheduleOptimizer can insert extension nodes "
1368
23
                        "that make Scop::getSchedule() return nullptr.");
1369
23
  bool changed = !isl_union_map_is_equal(OldSchedule, NewScheduleMap);
1370
23
  isl_union_map_free(OldSchedule);
1371
23
  isl_union_map_free(NewScheduleMap);
1372
23
  return changed;
1373
32
}
1374
1375
namespace {
1376
class IslScheduleOptimizer : public ScopPass {
1377
public:
1378
  static char ID;
1379
34
  explicit IslScheduleOptimizer() : ScopPass(ID) { LastSchedule = nullptr; }
1380
1381
34
  ~IslScheduleOptimizer() { isl_schedule_free(LastSchedule); }
1382
1383
  /// Optimize the schedule of the SCoP @p S.
1384
  bool runOnScop(Scop &S) override;
1385
1386
  /// Print the new schedule for the SCoP @p S.
1387
  void printScop(raw_ostream &OS, Scop &S) const override;
1388
1389
  /// Register all analyses and transformation required.
1390
  void getAnalysisUsage(AnalysisUsage &AU) const override;
1391
1392
  /// Release the internal memory.
1393
151
  void releaseMemory() override {
1394
151
    isl_schedule_free(LastSchedule);
1395
151
    LastSchedule = nullptr;
1396
151
  }
1397
1398
private:
1399
  isl_schedule *LastSchedule;
1400
};
1401
} // namespace
1402
1403
char IslScheduleOptimizer::ID = 0;
1404
1405
33
bool IslScheduleOptimizer::runOnScop(Scop &S) {
1406
33
1407
33
  // Skip empty SCoPs but still allow code generation as it will delete the
1408
33
  // loops present but not needed.
1409
33
  if (
S.getSize() == 033
)
{0
1410
0
    S.markAsOptimized();
1411
0
    return false;
1412
0
  }
1413
33
1414
33
  const Dependences &D =
1415
33
      getAnalysis<DependenceInfo>().getDependences(Dependences::AL_Statement);
1416
33
1417
33
  if (!D.hasValidDependences())
1418
1
    return false;
1419
33
1420
32
  isl_schedule_free(LastSchedule);
1421
32
  LastSchedule = nullptr;
1422
32
1423
32
  // Build input data.
1424
32
  int ValidityKinds =
1425
32
      Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;
1426
32
  int ProximityKinds;
1427
32
1428
32
  if (OptimizeDeps == "all")
1429
32
    ProximityKinds =
1430
32
        Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;
1431
0
  else 
if (0
OptimizeDeps == "raw"0
)
1432
0
    ProximityKinds = Dependences::TYPE_RAW;
1433
0
  else {
1434
0
    errs() << "Do not know how to optimize for '" << OptimizeDeps << "'"
1435
0
           << " Falling back to optimizing all dependences.\n";
1436
0
    ProximityKinds =
1437
0
        Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;
1438
0
  }
1439
32
1440
32
  isl_union_set *Domain = S.getDomains();
1441
32
1442
32
  if (!Domain)
1443
0
    return false;
1444
32
1445
32
  isl_union_map *Validity = D.getDependences(ValidityKinds);
1446
32
  isl_union_map *Proximity = D.getDependences(ProximityKinds);
1447
32
1448
32
  // Simplify the dependences by removing the constraints introduced by the
1449
32
  // domains. This can speed up the scheduling time significantly, as large
1450
32
  // constant coefficients will be removed from the dependences. The
1451
32
  // introduction of some additional dependences reduces the possible
1452
32
  // transformations, but in most cases, such transformation do not seem to be
1453
32
  // interesting anyway. In some cases this option may stop the scheduler to
1454
32
  // find any schedule.
1455
32
  if (
SimplifyDeps == "yes"32
)
{32
1456
32
    Validity = isl_union_map_gist_domain(Validity, isl_union_set_copy(Domain));
1457
32
    Validity = isl_union_map_gist_range(Validity, isl_union_set_copy(Domain));
1458
32
    Proximity =
1459
32
        isl_union_map_gist_domain(Proximity, isl_union_set_copy(Domain));
1460
32
    Proximity = isl_union_map_gist_range(Proximity, isl_union_set_copy(Domain));
1461
0
  } else 
if (0
SimplifyDeps != "no"0
)
{0
1462
0
    errs() << "warning: Option -polly-opt-simplify-deps should either be 'yes' "
1463
0
              "or 'no'. Falling back to default: 'yes'\n";
1464
0
  }
1465
32
1466
32
  DEBUG(dbgs() << "\n\nCompute schedule from: ");
1467
32
  DEBUG(dbgs() << "Domain := " << stringFromIslObj(Domain) << ";\n");
1468
32
  DEBUG(dbgs() << "Proximity := " << stringFromIslObj(Proximity) << ";\n");
1469
32
  DEBUG(dbgs() << "Validity := " << stringFromIslObj(Validity) << ";\n");
1470
32
1471
32
  unsigned IslSerializeSCCs;
1472
32
1473
32
  if (
FusionStrategy == "max"32
)
{2
1474
2
    IslSerializeSCCs = 0;
1475
30
  } else 
if (30
FusionStrategy == "min"30
)
{30
1476
30
    IslSerializeSCCs = 1;
1477
0
  } else {
1478
0
    errs() << "warning: Unknown fusion strategy. Falling back to maximal "
1479
0
              "fusion.\n";
1480
0
    IslSerializeSCCs = 0;
1481
0
  }
1482
32
1483
32
  int IslMaximizeBands;
1484
32
1485
32
  if (
MaximizeBandDepth == "yes"32
)
{32
1486
32
    IslMaximizeBands = 1;
1487
0
  } else 
if (0
MaximizeBandDepth == "no"0
)
{0
1488
0
    IslMaximizeBands = 0;
1489
0
  } else {
1490
0
    errs() << "warning: Option -polly-opt-maximize-bands should either be 'yes'"
1491
0
              " or 'no'. Falling back to default: 'yes'\n";
1492
0
    IslMaximizeBands = 1;
1493
0
  }
1494
32
1495
32
  int IslOuterCoincidence;
1496
32
1497
32
  if (
OuterCoincidence == "yes"32
)
{1
1498
1
    IslOuterCoincidence = 1;
1499
31
  } else 
if (31
OuterCoincidence == "no"31
)
{31
1500
31
    IslOuterCoincidence = 0;
1501
0
  } else {
1502
0
    errs() << "warning: Option -polly-opt-outer-coincidence should either be "
1503
0
              "'yes' or 'no'. Falling back to default: 'no'\n";
1504
0
    IslOuterCoincidence = 0;
1505
0
  }
1506
32
1507
32
  isl_ctx *Ctx = S.getIslCtx();
1508
32
1509
32
  isl_options_set_schedule_outer_coincidence(Ctx, IslOuterCoincidence);
1510
32
  isl_options_set_schedule_serialize_sccs(Ctx, IslSerializeSCCs);
1511
32
  isl_options_set_schedule_maximize_band_depth(Ctx, IslMaximizeBands);
1512
32
  isl_options_set_schedule_max_constant_term(Ctx, MaxConstantTerm);
1513
32
  isl_options_set_schedule_max_coefficient(Ctx, MaxCoefficient);
1514
32
  isl_options_set_tile_scale_tile_loops(Ctx, 0);
1515
32
1516
32
  auto OnErrorStatus = isl_options_get_on_error(Ctx);
1517
32
  isl_options_set_on_error(Ctx, ISL_ON_ERROR_CONTINUE);
1518
32
1519
32
  isl_schedule_constraints *ScheduleConstraints;
1520
32
  ScheduleConstraints = isl_schedule_constraints_on_domain(Domain);
1521
32
  ScheduleConstraints =
1522
32
      isl_schedule_constraints_set_proximity(ScheduleConstraints, Proximity);
1523
32
  ScheduleConstraints = isl_schedule_constraints_set_validity(
1524
32
      ScheduleConstraints, isl_union_map_copy(Validity));
1525
32
  ScheduleConstraints =
1526
32
      isl_schedule_constraints_set_coincidence(ScheduleConstraints, Validity);
1527
32
  isl_schedule *Schedule;
1528
32
  Schedule = isl_schedule_constraints_compute_schedule(ScheduleConstraints);
1529
32
  isl_options_set_on_error(Ctx, OnErrorStatus);
1530
32
1531
32
  // In cases the scheduler is not able to optimize the code, we just do not
1532
32
  // touch the schedule.
1533
32
  if (!Schedule)
1534
0
    return false;
1535
32
1536
32
  
DEBUG32
({32
1537
32
    auto *P = isl_printer_to_str(Ctx);
1538
32
    P = isl_printer_set_yaml_style(P, ISL_YAML_STYLE_BLOCK);
1539
32
    P = isl_printer_print_schedule(P, Schedule);
1540
32
    auto *str = isl_printer_get_str(P);
1541
32
    dbgs() << "NewScheduleTree: \n" << str << "\n";
1542
32
    free(str);
1543
32
    isl_printer_free(P);
1544
32
  });
1545
32
1546
32
  Function &F = S.getFunction();
1547
32
  auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1548
32
  const OptimizerAdditionalInfoTy OAI = {TTI, const_cast<Dependences *>(&D)};
1549
32
  isl_schedule *NewSchedule =
1550
32
      ScheduleTreeOptimizer::optimizeSchedule(Schedule, &OAI);
1551
32
1552
32
  if (
!ScheduleTreeOptimizer::isProfitableSchedule(S, NewSchedule)32
)
{3
1553
3
    isl_schedule_free(NewSchedule);
1554
3
    return false;
1555
3
  }
1556
32
1557
29
  S.setScheduleTree(NewSchedule);
1558
29
  S.markAsOptimized();
1559
29
1560
29
  if (OptimizedScops)
1561
1
    S.dump();
1562
29
1563
29
  return false;
1564
32
}
1565
1566
26
void IslScheduleOptimizer::printScop(raw_ostream &OS, Scop &) const {
1567
26
  isl_printer *p;
1568
26
  char *ScheduleStr;
1569
26
1570
26
  OS << "Calculated schedule:\n";
1571
26
1572
26
  if (
!LastSchedule26
)
{26
1573
26
    OS << "n/a\n";
1574
26
    return;
1575
26
  }
1576
26
1577
0
  p = isl_printer_to_str(isl_schedule_get_ctx(LastSchedule));
1578
0
  p = isl_printer_print_schedule(p, LastSchedule);
1579
0
  ScheduleStr = isl_printer_get_str(p);
1580
0
  isl_printer_free(p);
1581
0
1582
0
  OS << ScheduleStr << "\n";
1583
0
}
1584
1585
34
void IslScheduleOptimizer::getAnalysisUsage(AnalysisUsage &AU) const {
1586
34
  ScopPass::getAnalysisUsage(AU);
1587
34
  AU.addRequired<DependenceInfo>();
1588
34
  AU.addRequired<TargetTransformInfoWrapperPass>();
1589
34
}
1590
1591
0
Pass *polly::createIslScheduleOptimizerPass() {
1592
0
  return new IslScheduleOptimizer();
1593
0
}
1594
1595
39.2k
INITIALIZE_PASS_BEGIN39.2k
(IslScheduleOptimizer, "polly-opt-isl",39.2k
1596
39.2k
                      "Polly - Optimize schedule of SCoP", false, false);
1597
39.2k
INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
1598
39.2k
INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass);
1599
39.2k
INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass);
1600
39.2k
INITIALIZE_PASS_END(IslScheduleOptimizer, "polly-opt-isl",
1601
                    "Polly - Optimize schedule of SCoP", false, false)