Coverage Report

Created: 2017-10-03 07:32

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