Coverage Report

Created: 2018-04-23 18:20

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/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
40
                                        unsigned OutDimsNum) {
311
40
  unsigned Dims = IsolateDomain.dim(isl::dim::set);
312
40
  assert(OutDimsNum <= Dims &&
313
40
         "The isl::set IsolateDomain is used to describe the range of schedule "
314
40
         "dimensions values, which should be isolated. Consequently, the "
315
40
         "number of its dimensions should be greater than or equal to the "
316
40
         "number of the schedule dimensions.");
317
40
  isl::map IsolateRelation = isl::map::from_domain(IsolateDomain);
318
40
  IsolateRelation = IsolateRelation.move_dims(isl::dim::out, 0, isl::dim::in,
319
40
                                              Dims - OutDimsNum, OutDimsNum);
320
40
  isl::set IsolateOption = IsolateRelation.wrap();
321
40
  isl::id Id = isl::id::alloc(IsolateOption.get_ctx(), "isolate", nullptr);
322
40
  IsolateOption = IsolateOption.set_tuple_id(Id);
323
40
  return isl::union_set(IsolateOption);
324
40
}
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
40
isl::union_set getDimOptions(isl::ctx Ctx, const char *Option) {
333
40
  isl::space Space(Ctx, 0, 1);
334
40
  auto DimOption = isl::set::universe(Space);
335
40
  auto Id = isl::id::alloc(Ctx, Option, nullptr);
336
40
  DimOption = DimOption.set_tuple_id(Id);
337
40
  return isl::union_set(DimOption);
338
40
}
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
43
static isl::set addExtentConstraints(isl::set Set, int VectorWidth) {
362
43
  unsigned Dims = Set.dim(isl::dim::set);
363
43
  isl::space Space = Set.get_space();
364
43
  isl::local_space LocalSpace = isl::local_space(Space);
365
43
  isl::constraint ExtConstr = isl::constraint::alloc_inequality(LocalSpace);
366
43
  ExtConstr = ExtConstr.set_constant_si(0);
367
43
  ExtConstr = ExtConstr.set_coefficient_si(isl::dim::set, Dims - 1, 1);
368
43
  Set = Set.add_constraint(ExtConstr);
369
43
  ExtConstr = isl::constraint::alloc_inequality(LocalSpace);
370
43
  ExtConstr = ExtConstr.set_constant_si(VectorWidth - 1);
371
43
  ExtConstr = ExtConstr.set_coefficient_si(isl::dim::set, Dims - 1, -1);
372
43
  return Set.add_constraint(ExtConstr);
373
43
}
374
375
43
isl::set getPartialTilePrefixes(isl::set ScheduleRange, int VectorWidth) {
376
43
  unsigned Dims = ScheduleRange.dim(isl::dim::set);
377
43
  isl::set LoopPrefixes =
378
43
      ScheduleRange.drop_constraints_involving_dims(isl::dim::set, Dims - 1, 1);
379
43
  auto ExtentPrefixes = addExtentConstraints(LoopPrefixes, VectorWidth);
380
43
  isl::set BadPrefixes = ExtentPrefixes.subtract(ScheduleRange);
381
43
  BadPrefixes = BadPrefixes.project_out(isl::dim::set, Dims - 1, 1);
382
43
  LoopPrefixes = LoopPrefixes.project_out(isl::dim::set, Dims - 1, 1);
383
43
  return LoopPrefixes.subtract(BadPrefixes);
384
43
}
385
386
isl::schedule_node
387
ScheduleTreeOptimizer::isolateFullPartialTiles(isl::schedule_node Node,
388
16
                                               int VectorWidth) {
389
16
  assert(isl_schedule_node_get_type(Node.get()) == isl_schedule_node_band);
390
16
  Node = Node.child(0).child(0);
391
16
  isl::union_map SchedRelUMap = Node.get_prefix_schedule_relation();
392
16
  isl::map ScheduleRelation = isl::map::from_union_map(SchedRelUMap);
393
16
  isl::set ScheduleRange = ScheduleRelation.range();
394
16
  isl::set IsolateDomain = getPartialTilePrefixes(ScheduleRange, VectorWidth);
395
16
  auto AtomicOption = getDimOptions(IsolateDomain.get_ctx(), "atomic");
396
16
  isl::union_set IsolateOption = getIsolateOptions(IsolateDomain, 1);
397
16
  Node = Node.parent().parent();
398
16
  isl::union_set Options = IsolateOption.unite(AtomicOption);
399
16
  Node = Node.band_set_ast_build_options(Options);
400
16
  return Node;
401
16
}
402
403
isl::schedule_node ScheduleTreeOptimizer::prevectSchedBand(
404
16
    isl::schedule_node Node, unsigned DimToVectorize, int VectorWidth) {
405
16
  assert(isl_schedule_node_get_type(Node.get()) == isl_schedule_node_band);
406
16
407
16
  auto Space = isl::manage(isl_schedule_node_band_get_space(Node.get()));
408
16
  auto ScheduleDimensions = Space.dim(isl::dim::set);
409
16
  assert(DimToVectorize < ScheduleDimensions);
410
16
411
16
  if (DimToVectorize > 0) {
412
15
    Node = isl::manage(
413
15
        isl_schedule_node_band_split(Node.release(), DimToVectorize));
414
15
    Node = Node.child(0);
415
15
  }
416
16
  if (DimToVectorize < ScheduleDimensions - 1)
417
7
    Node = isl::manage(isl_schedule_node_band_split(Node.release(), 1));
418
16
  Space = isl::manage(isl_schedule_node_band_get_space(Node.get()));
419
16
  auto Sizes = isl::multi_val::zero(Space);
420
16
  Sizes = Sizes.set_val(0, isl::val(Node.get_ctx(), VectorWidth));
421
16
  Node =
422
16
      isl::manage(isl_schedule_node_band_tile(Node.release(), Sizes.release()));
423
16
  Node = isolateFullPartialTiles(Node, VectorWidth);
424
16
  Node = Node.child(0);
425
16
  // Make sure the "trivially vectorizable loop" is not unrolled. Otherwise,
426
16
  // we will have troubles to match it in the backend.
427
16
  Node = Node.band_set_ast_build_options(
428
16
      isl::union_set(Node.get_ctx(), "{ unroll[x]: 1 = 0 }"));
429
16
  Node = isl::manage(isl_schedule_node_band_sink(Node.release()));
430
16
  Node = Node.child(0);
431
16
  if (isl_schedule_node_get_type(Node.get()) == isl_schedule_node_leaf)
432
9
    Node = Node.parent();
433
16
  auto LoopMarker = isl::id::alloc(Node.get_ctx(), "SIMD", nullptr);
434
16
  PrevectOpts++;
435
16
  return Node.insert_mark(LoopMarker);
436
16
}
437
438
isl::schedule_node ScheduleTreeOptimizer::tileNode(isl::schedule_node Node,
439
                                                   const char *Identifier,
440
                                                   ArrayRef<int> TileSizes,
441
58
                                                   int DefaultTileSize) {
442
58
  auto Space = isl::manage(isl_schedule_node_band_get_space(Node.get()));
443
58
  auto Dims = Space.dim(isl::dim::set);
444
58
  auto Sizes = isl::multi_val::zero(Space);
445
58
  std::string IdentifierString(Identifier);
446
206
  for (unsigned i = 0; i < Dims; 
i++148
) {
447
148
    auto tileSize = i < TileSizes.size() ? 
TileSizes[i]84
:
DefaultTileSize64
;
448
148
    Sizes = Sizes.set_val(i, isl::val(Node.get_ctx(), tileSize));
449
148
  }
450
58
  auto TileLoopMarkerStr = IdentifierString + " - Tiles";
451
58
  auto TileLoopMarker =
452
58
      isl::id::alloc(Node.get_ctx(), TileLoopMarkerStr, nullptr);
453
58
  Node = Node.insert_mark(TileLoopMarker);
454
58
  Node = Node.child(0);
455
58
  Node =
456
58
      isl::manage(isl_schedule_node_band_tile(Node.release(), Sizes.release()));
457
58
  Node = Node.child(0);
458
58
  auto PointLoopMarkerStr = IdentifierString + " - Points";
459
58
  auto PointLoopMarker =
460
58
      isl::id::alloc(Node.get_ctx(), PointLoopMarkerStr, nullptr);
461
58
  Node = Node.insert_mark(PointLoopMarker);
462
58
  return Node.child(0);
463
58
}
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
77
static bool isSimpleInnermostBand(const isl::schedule_node &Node) {
473
77
  assert(isl_schedule_node_get_type(Node.keep()) == isl_schedule_node_band);
474
77
  assert(isl_schedule_node_n_children(Node.keep()) == 1);
475
77
476
77
  auto ChildType = isl_schedule_node_get_type(Node.child(0).keep());
477
77
478
77
  if (ChildType == isl_schedule_node_leaf)
479
44
    return true;
480
33
481
33
  if (ChildType != isl_schedule_node_sequence)
482
32
    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
       ++c) {
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 (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
1
}
497
498
538
bool ScheduleTreeOptimizer::isTileableBandNode(isl::schedule_node Node) {
499
538
  if (isl_schedule_node_get_type(Node.get()) != isl_schedule_node_band)
500
374
    return false;
501
164
502
164
  if (isl_schedule_node_n_children(Node.get()) != 1)
503
0
    return false;
504
164
505
164
  if (!isl_schedule_node_band_get_permutable(Node.get()))
506
40
    return false;
507
124
508
124
  auto Space = isl::manage(isl_schedule_node_band_get_space(Node.get()));
509
124
  auto Dims = Space.dim(isl::dim::set);
510
124
511
124
  if (Dims <= 1)
512
47
    return false;
513
77
514
77
  return isSimpleInnermostBand(Node);
515
77
}
516
517
__isl_give isl::schedule_node
518
31
ScheduleTreeOptimizer::standardBandOpts(isl::schedule_node Node, void *User) {
519
31
  if (FirstLevelTiling) {
520
27
    Node = tileNode(Node, "1st level tiling", FirstLevelTileSizes,
521
27
                    FirstLevelDefaultTileSize);
522
27
    FirstLevelTileOpts++;
523
27
  }
524
31
525
31
  if (SecondLevelTiling) {
526
3
    Node = tileNode(Node, "2nd level tiling", SecondLevelTileSizes,
527
3
                    SecondLevelDefaultTileSize);
528
3
    SecondLevelTileOpts++;
529
3
  }
530
31
531
31
  if (RegisterTiling) {
532
2
    Node =
533
2
        applyRegisterTiling(Node, RegisterTileSizes, RegisterDefaultTileSize);
534
2
    RegisterTileOpts++;
535
2
  }
536
31
537
31
  if (PollyVectorizerChoice == VECTORIZER_NONE)
538
15
    return Node;
539
16
540
16
  auto Space = isl::manage(isl_schedule_node_band_get_space(Node.get()));
541
16
  auto Dims = Space.dim(isl::dim::set);
542
16
543
23
  for (int i = Dims - 1; i >= 0; 
i--7
)
544
23
    if (Node.band_member_get_coincident(i)) {
545
16
      Node = prevectSchedBand(Node, i, PrevectorWidth);
546
16
      break;
547
16
    }
548
16
549
16
  return Node;
550
16
}
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::in;
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
28
  return Map;
585
28
}
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 < 6; 
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)) {
630
98
      if (FirstPos != -1 && 
FirstPos != FirstDims[i]84
)
631
28
        continue;
632
70
      FirstPos = FirstDims[i];
633
70
      if (SecondPos != -1 && 
SecondPos != SecondDims[i]56
)
634
14
        continue;
635
56
      SecondPos = SecondDims[i];
636
56
      return true;
637
56
    }
638
392
  }
639
98
640
98
  
return false42
;
641
98
}
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() || !MemAccess->isRead())
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) && 
!MMI.ReadFromC14
) {
661
14
    MMI.ReadFromC = MemAccess;
662
14
    return true;
663
14
  }
664
29
  if (isMatMulOperandAcc(StmtDomain, AccMap, MMI.i, MMI.k) && 
!MMI.A14
) {
665
14
    MMI.A = MemAccess;
666
14
    return true;
667
14
  }
668
15
  if (isMatMulOperandAcc(StmtDomain, AccMap, MMI.k, MMI.j) && 
!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() - 1; 
MemA++48
) {
705
48
    auto *MemAccessPtr = *MemA;
706
48
    if (MemAccessPtr->isLatestArrayKind() && 
MemAccessPtr != MMI.WriteToC43
&&
707
48
        
!isMatMulNonScalarReadAccess(MemAccessPtr, MMI)43
&&
708
48
        
!(MemAccessPtr->isStrideZero(MapI))1
&&
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 < DeltasDimNum; 
i++42
) {
740
42
    auto Val = Deltas.plain_get_val_if_fixed(isl::dim::set, i);
741
42
    Pos = Pos < 0 && Val.is_one() ? 
i14
:
Pos28
;
742
42
    if (Val.is_nan() || !(Val.is_zero() || 
(14
i == Pos14
&&
Val.is_one()14
)))
743
0
      return false;
744
42
  }
745
14
  if (DeltasDimNum == 0 || Pos < 0)
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(); 
MemA--0
) {
782
15
    auto *MemAccessPtr = *MemA;
783
15
    if (!MemAccessPtr->isLatestArrayKind())
784
0
      continue;
785
15
    if (!MemAccessPtr->isWrite())
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
15
  
if (14
!containsOnlyMatMulDep(PartialSchedule, D, MMI.k)14
)
795
0
    return false;
796
14
797
14
  if (!MMI.WriteToC || !containsOnlyMatrMultAcc(PartialSchedule, MMI))
798
0
    return false;
799
14
800
14
  if (!MMI.A || !MMI.B || !MMI.ReadFromC)
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 && 
MacroKernelParams.Nc == 12
&&
842
14
      
MacroKernelParams.Kc == 12
)
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 == -1) {
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 == -1) {
934
2
    if (TTI->getCacheSize(L2DCache).hasValue())
935
1
      SecondCacheLevelSize = TTI->getCacheSize(L2DCache).getValue();
936
1
    else
937
1
      SecondCacheLevelSize = static_cast<int>(SecondCacheLevelDefaultSize);
938
2
  }
939
14
  if (FirstCacheLevelAssociativity == -1) {
940
1
    if (TTI->getCacheAssociativity(L1DCache).hasValue())
941
1
      FirstCacheLevelAssociativity =
942
1
          TTI->getCacheAssociativity(L1DCache).getValue();
943
0
    else
944
0
      FirstCacheLevelAssociativity =
945
0
          static_cast<int>(FirstCacheLevelDefaultAssociativity);
946
1
  }
947
14
  if (SecondCacheLevelAssociativity == -1) {
948
2
    if (TTI->getCacheAssociativity(L2DCache).hasValue())
949
1
      SecondCacheLevelAssociativity =
950
1
          TTI->getCacheAssociativity(L2DCache).getValue();
951
1
    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 && MicroKernelParams.Nr > 0 &&
984
14
        FirstCacheLevelSize > 0 && 
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 (PollyPatternMatchingNcQuotient <= 0)
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(MapOldIndVar, 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, DomainId);
1126
12
  ExtMap = ExtMap.intersect_range(Domain);
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(MapOldIndVar, 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(Domain).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.j;
1289
14
  int NewK = MMI.k == DimOutNum - 3 ? 
MMI.i0
: MMI.k;
1290
14
  Node = permuteBandNodeDimensions(Node, NewJ, DimOutNum - 2);
1291
14
  NewK = NewK == DimOutNum - 2 ? 
NewJ0
: NewK;
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 || 
MacroKernelParams.Nc == 112
||
1298
14
      
MacroKernelParams.Kc == 112
)
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
36
                                              MatMulInfoTy &MMI) {
1313
36
  auto PartialSchedule = isl::manage(
1314
36
      isl_schedule_node_band_get_partial_schedule_union_map(Node.get()));
1315
36
  Node = Node.child(0);
1316
36
  auto LeafType = isl_schedule_node_get_type(Node.get());
1317
36
  Node = Node.parent();
1318
36
  if (LeafType != isl_schedule_node_leaf ||
1319
36
      
isl_schedule_node_band_n_member(Node.get()) < 335
||
1320
36
      
Node.get_schedule_depth() != 015
||
1321
36
      
isl_union_map_n_map(PartialSchedule.get()) != 115
)
1322
21
    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
538
                                    void *User) {
1332
538
  if (!isTileableBandNode(isl::manage_copy(Node)))
1333
493
    return Node;
1334
45
1335
45
  const OptimizerAdditionalInfoTy *OAI =
1336
45
      static_cast<const OptimizerAdditionalInfoTy *>(User);
1337
45
1338
45
  MatMulInfoTy MMI;
1339
45
  if (PMBasedOpts && 
User36
&&
1340
45
      
isMatrMultPattern(isl::manage_copy(Node), OAI->D, MMI)36
) {
1341
14
    DEBUG(dbgs() << "The matrix multiplication pattern was detected\n");
1342
14
    MatMulOpts++;
1343
14
    return optimizeMatMulPattern(isl::manage(Node), OAI->TTI, MMI).release();
1344
14
  }
1345
31
1346
31
  return standardBandOpts(isl::manage(Node), User).release();
1347
31
}
1348
1349
isl::schedule
1350
ScheduleTreeOptimizer::optimizeSchedule(isl::schedule Schedule,
1351
39
                                        const OptimizerAdditionalInfoTy *OAI) {
1352
39
  auto Root = Schedule.get_root();
1353
39
  Root = optimizeScheduleNode(Root, OAI);
1354
39
  return Root.get_schedule();
1355
39
}
1356
1357
isl::schedule_node ScheduleTreeOptimizer::optimizeScheduleNode(
1358
39
    isl::schedule_node Node, const OptimizerAdditionalInfoTy *OAI) {
1359
39
  Node = isl::manage(isl_schedule_node_map_descendant_bottom_up(
1360
39
      Node.release(), optimizeBand,
1361
39
      const_cast<void *>(static_cast<const void *>(OAI))));
1362
39
  return Node;
1363
39
}
1364
1365
bool ScheduleTreeOptimizer::isProfitableSchedule(Scop &S,
1366
39
                                                 isl::schedule NewSchedule) {
1367
39
  // To understand if the schedule has been optimized we check if the schedule
1368
39
  // has changed at all.
1369
39
  // TODO: We can improve this by tracking if any necessarily beneficial
1370
39
  // transformations have been performed. This can e.g. be tiling, loop
1371
39
  // interchange, or ...) We can track this either at the place where the
1372
39
  // transformation has been performed or, in case of automatic ILP based
1373
39
  // optimizations, by comparing (yet to be defined) performance metrics
1374
39
  // before/after the scheduling optimizer
1375
39
  // (e.g., #stride-one accesses)
1376
39
  if (S.containsExtensionNode(NewSchedule))
1377
12
    return true;
1378
27
  auto NewScheduleMap = NewSchedule.get_map();
1379
27
  auto OldSchedule = S.getSchedule();
1380
27
  assert(OldSchedule && "Only IslScheduleOptimizer can insert extension nodes "
1381
27
                        "that make Scop::getSchedule() return nullptr.");
1382
27
  bool changed = !OldSchedule.is_equal(NewScheduleMap);
1383
27
  return changed;
1384
27
}
1385
1386
namespace {
1387
1388
class IslScheduleOptimizer : public ScopPass {
1389
public:
1390
  static char ID;
1391
1392
41
  explicit IslScheduleOptimizer() : ScopPass(ID) {}
1393
1394
41
  ~IslScheduleOptimizer() override { isl_schedule_free(LastSchedule); }
1395
1396
  /// Optimize the schedule of the SCoP @p S.
1397
  bool runOnScop(Scop &S) override;
1398
1399
  /// Print the new schedule for the SCoP @p S.
1400
  void printScop(raw_ostream &OS, Scop &S) const override;
1401
1402
  /// Register all analyses and transformation required.
1403
  void getAnalysisUsage(AnalysisUsage &AU) const override;
1404
1405
  /// Release the internal memory.
1406
177
  void releaseMemory() override {
1407
177
    isl_schedule_free(LastSchedule);
1408
177
    LastSchedule = nullptr;
1409
177
  }
1410
1411
private:
1412
  isl_schedule *LastSchedule = nullptr;
1413
};
1414
} // namespace
1415
1416
char IslScheduleOptimizer::ID = 0;
1417
1418
/// Collect statistics for the schedule tree.
1419
///
1420
/// @param Schedule The schedule tree to analyze. If not a schedule tree it is
1421
/// ignored.
1422
/// @param Version  The version of the schedule tree that is analyzed.
1423
///                 0 for the original schedule tree before any transformation.
1424
///                 1 for the schedule tree after isl's rescheduling.
1425
///                 2 for the schedule tree after optimizations are applied
1426
///                 (tiling, pattern matching)
1427
117
static void walkScheduleTreeForStatistics(isl::schedule Schedule, int Version) {
1428
117
  auto Root = Schedule.get_root();
1429
117
  if (!Root)
1430
0
    return;
1431
117
1432
117
  isl_schedule_node_foreach_descendant_top_down(
1433
117
      Root.get(),
1434
1.07k
      [](__isl_keep isl_schedule_node *nodeptr, void *user) -> isl_bool {
1435
1.07k
        isl::schedule_node Node = isl::manage_copy(nodeptr);
1436
1.07k
        int Version = *static_cast<int *>(user);
1437
1.07k
1438
1.07k
        switch (isl_schedule_node_get_type(Node.get())) {
1439
1.07k
        case isl_schedule_node_band: {
1440
320
          NumBands[Version]++;
1441
320
          if (isl_schedule_node_band_get_permutable(Node.get()) ==
1442
320
              isl_bool_true)
1443
164
            NumPermutable[Version]++;
1444
320
1445
320
          int CountMembers = isl_schedule_node_band_n_member(Node.get());
1446
320
          NumBandMembers[Version] += CountMembers;
1447
831
          for (int i = 0; i < CountMembers; 
i += 1511
) {
1448
511
            if (Node.band_member_get_coincident(i))
1449
239
              NumCoincident[Version]++;
1450
511
          }
1451
320
          break;
1452
1.07k
        }
1453
1.07k
1454
1.07k
        case isl_schedule_node_filter:
1455
169
          NumFilters[Version]++;
1456
169
          break;
1457
1.07k
1458
1.07k
        case isl_schedule_node_extension:
1459
24
          NumExtension[Version]++;
1460
24
          break;
1461
1.07k
1462
1.07k
        default:
1463
561
          break;
1464
1.07k
        }
1465
1.07k
1466
1.07k
        return isl_bool_true;
1467
1.07k
      },
1468
117
      &Version);
1469
117
}
1470
1471
40
bool IslScheduleOptimizer::runOnScop(Scop &S) {
1472
40
  // Skip SCoPs in case they're already optimised by PPCGCodeGeneration
1473
40
  if (S.isToBeSkipped())
1474
0
    return false;
1475
40
1476
40
  // Skip empty SCoPs but still allow code generation as it will delete the
1477
40
  // loops present but not needed.
1478
40
  if (S.getSize() == 0) {
1479
0
    S.markAsOptimized();
1480
0
    return false;
1481
0
  }
1482
40
1483
40
  const Dependences &D =
1484
40
      getAnalysis<DependenceInfo>().getDependences(Dependences::AL_Statement);
1485
40
1486
40
  if (D.getSharedIslCtx() != S.getSharedIslCtx()) {
1487
0
    DEBUG(dbgs() << "DependenceInfo for another SCoP/isl_ctx\n");
1488
0
    return false;
1489
0
  }
1490
40
1491
40
  if (!D.hasValidDependences())
1492
1
    return false;
1493
39
1494
39
  isl_schedule_free(LastSchedule);
1495
39
  LastSchedule = nullptr;
1496
39
1497
39
  // Build input data.
1498
39
  int ValidityKinds =
1499
39
      Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;
1500
39
  int ProximityKinds;
1501
39
1502
39
  if (OptimizeDeps == "all")
1503
39
    ProximityKinds =
1504
39
        Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;
1505
0
  else if (OptimizeDeps == "raw")
1506
0
    ProximityKinds = Dependences::TYPE_RAW;
1507
0
  else {
1508
0
    errs() << "Do not know how to optimize for '" << OptimizeDeps << "'"
1509
0
           << " Falling back to optimizing all dependences.\n";
1510
0
    ProximityKinds =
1511
0
        Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;
1512
0
  }
1513
39
1514
39
  isl::union_set Domain = S.getDomains();
1515
39
1516
39
  if (!Domain)
1517
0
    return false;
1518
39
1519
39
  ScopsProcessed++;
1520
39
  walkScheduleTreeForStatistics(S.getScheduleTree(), 0);
1521
39
1522
39
  isl::union_map Validity = give(D.getDependences(ValidityKinds));
1523
39
  isl::union_map Proximity = give(D.getDependences(ProximityKinds));
1524
39
1525
39
  // Simplify the dependences by removing the constraints introduced by the
1526
39
  // domains. This can speed up the scheduling time significantly, as large
1527
39
  // constant coefficients will be removed from the dependences. The
1528
39
  // introduction of some additional dependences reduces the possible
1529
39
  // transformations, but in most cases, such transformation do not seem to be
1530
39
  // interesting anyway. In some cases this option may stop the scheduler to
1531
39
  // find any schedule.
1532
39
  if (SimplifyDeps == "yes") {
1533
39
    Validity = Validity.gist_domain(Domain);
1534
39
    Validity = Validity.gist_range(Domain);
1535
39
    Proximity = Proximity.gist_domain(Domain);
1536
39
    Proximity = Proximity.gist_range(Domain);
1537
39
  } else 
if (0
SimplifyDeps != "no"0
) {
1538
0
    errs() << "warning: Option -polly-opt-simplify-deps should either be 'yes' "
1539
0
              "or 'no'. Falling back to default: 'yes'\n";
1540
0
  }
1541
39
1542
39
  DEBUG(dbgs() << "\n\nCompute schedule from: ");
1543
39
  DEBUG(dbgs() << "Domain := " << Domain << ";\n");
1544
39
  DEBUG(dbgs() << "Proximity := " << Proximity << ";\n");
1545
39
  DEBUG(dbgs() << "Validity := " << Validity << ";\n");
1546
39
1547
39
  unsigned IslSerializeSCCs;
1548
39
1549
39
  if (FusionStrategy == "max") {
1550
2
    IslSerializeSCCs = 0;
1551
37
  } else if (FusionStrategy == "min") {
1552
37
    IslSerializeSCCs = 1;
1553
37
  } else {
1554
0
    errs() << "warning: Unknown fusion strategy. Falling back to maximal "
1555
0
              "fusion.\n";
1556
0
    IslSerializeSCCs = 0;
1557
0
  }
1558
39
1559
39
  int IslMaximizeBands;
1560
39
1561
39
  if (MaximizeBandDepth == "yes") {
1562
39
    IslMaximizeBands = 1;
1563
39
  } else 
if (0
MaximizeBandDepth == "no"0
) {
1564
0
    IslMaximizeBands = 0;
1565
0
  } else {
1566
0
    errs() << "warning: Option -polly-opt-maximize-bands should either be 'yes'"
1567
0
              " or 'no'. Falling back to default: 'yes'\n";
1568
0
    IslMaximizeBands = 1;
1569
0
  }
1570
39
1571
39
  int IslOuterCoincidence;
1572
39
1573
39
  if (OuterCoincidence == "yes") {
1574
1
    IslOuterCoincidence = 1;
1575
38
  } else if (OuterCoincidence == "no") {
1576
38
    IslOuterCoincidence = 0;
1577
38
  } else {
1578
0
    errs() << "warning: Option -polly-opt-outer-coincidence should either be "
1579
0
              "'yes' or 'no'. Falling back to default: 'no'\n";
1580
0
    IslOuterCoincidence = 0;
1581
0
  }
1582
39
1583
39
  isl_ctx *Ctx = S.getIslCtx().get();
1584
39
1585
39
  isl_options_set_schedule_outer_coincidence(Ctx, IslOuterCoincidence);
1586
39
  isl_options_set_schedule_serialize_sccs(Ctx, IslSerializeSCCs);
1587
39
  isl_options_set_schedule_maximize_band_depth(Ctx, IslMaximizeBands);
1588
39
  isl_options_set_schedule_max_constant_term(Ctx, MaxConstantTerm);
1589
39
  isl_options_set_schedule_max_coefficient(Ctx, MaxCoefficient);
1590
39
  isl_options_set_tile_scale_tile_loops(Ctx, 0);
1591
39
1592
39
  auto OnErrorStatus = isl_options_get_on_error(Ctx);
1593
39
  isl_options_set_on_error(Ctx, ISL_ON_ERROR_CONTINUE);
1594
39
1595
39
  auto SC = isl::schedule_constraints::on_domain(Domain);
1596
39
  SC = SC.set_proximity(Proximity);
1597
39
  SC = SC.set_validity(Validity);
1598
39
  SC = SC.set_coincidence(Validity);
1599
39
  auto Schedule = SC.compute_schedule();
1600
39
  isl_options_set_on_error(Ctx, OnErrorStatus);
1601
39
1602
39
  walkScheduleTreeForStatistics(Schedule, 1);
1603
39
1604
39
  // In cases the scheduler is not able to optimize the code, we just do not
1605
39
  // touch the schedule.
1606
39
  if (!Schedule)
1607
0
    return false;
1608
39
1609
39
  ScopsRescheduled++;
1610
39
1611
39
  DEBUG({
1612
39
    auto *P = isl_printer_to_str(Ctx);
1613
39
    P = isl_printer_set_yaml_style(P, ISL_YAML_STYLE_BLOCK);
1614
39
    P = isl_printer_print_schedule(P, Schedule.get());
1615
39
    auto *str = isl_printer_get_str(P);
1616
39
    dbgs() << "NewScheduleTree: \n" << str << "\n";
1617
39
    free(str);
1618
39
    isl_printer_free(P);
1619
39
  });
1620
39
1621
39
  Function &F = S.getFunction();
1622
39
  auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1623
39
  const OptimizerAdditionalInfoTy OAI = {TTI, const_cast<Dependences *>(&D)};
1624
39
  auto NewSchedule = ScheduleTreeOptimizer::optimizeSchedule(Schedule, &OAI);
1625
39
  walkScheduleTreeForStatistics(NewSchedule, 2);
1626
39
1627
39
  if (!ScheduleTreeOptimizer::isProfitableSchedule(S, NewSchedule))
1628
4
    return false;
1629
35
1630
35
  auto ScopStats = S.getStatistics();
1631
35
  ScopsOptimized++;
1632
35
  NumAffineLoopsOptimized += ScopStats.NumAffineLoops;
1633
35
  NumBoxedLoopsOptimized += ScopStats.NumBoxedLoops;
1634
35
1635
35
  S.setScheduleTree(NewSchedule);
1636
35
  S.markAsOptimized();
1637
35
1638
35
  if (OptimizedScops)
1639
1
    errs() << S;
1640
35
1641
35
  return false;
1642
35
}
1643
1644
29
void IslScheduleOptimizer::printScop(raw_ostream &OS, Scop &) const {
1645
29
  isl_printer *p;
1646
29
  char *ScheduleStr;
1647
29
1648
29
  OS << "Calculated schedule:\n";
1649
29
1650
29
  if (!LastSchedule) {
1651
29
    OS << "n/a\n";
1652
29
    return;
1653
29
  }
1654
0
1655
0
  p = isl_printer_to_str(isl_schedule_get_ctx(LastSchedule));
1656
0
  p = isl_printer_print_schedule(p, LastSchedule);
1657
0
  ScheduleStr = isl_printer_get_str(p);
1658
0
  isl_printer_free(p);
1659
0
1660
0
  OS << ScheduleStr << "\n";
1661
0
}
1662
1663
41
void IslScheduleOptimizer::getAnalysisUsage(AnalysisUsage &AU) const {
1664
41
  ScopPass::getAnalysisUsage(AU);
1665
41
  AU.addRequired<DependenceInfo>();
1666
41
  AU.addRequired<TargetTransformInfoWrapperPass>();
1667
41
1668
41
  AU.addPreserved<DependenceInfo>();
1669
41
}
1670
1671
0
Pass *polly::createIslScheduleOptimizerPass() {
1672
0
  return new IslScheduleOptimizer();
1673
0
}
1674
1675
43.0k
INITIALIZE_PASS_BEGIN(IslScheduleOptimizer, "polly-opt-isl",
1676
43.0k
                      "Polly - Optimize schedule of SCoP", false, false);
1677
43.0k
INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
1678
43.0k
INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass);
1679
43.0k
INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass);
1680
43.0k
INITIALIZE_PASS_END(IslScheduleOptimizer, "polly-opt-isl",
1681
                    "Polly - Optimize schedule of SCoP", false, false)