Coverage Report

Created: 2019-02-15 18:59

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