Coverage Report

Created: 2017-04-27 19:33

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/Transform/DeLICM.cpp
Line
Count
Source (jump to first uncovered line)
1
//===------ DeLICM.cpp -----------------------------------------*- C++ -*-===//
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
// Undo the effect of Loop Invariant Code Motion (LICM) and
11
// GVN Partial Redundancy Elimination (PRE) on SCoP-level.
12
//
13
// Namely, remove register/scalar dependencies by mapping them back to array
14
// elements.
15
//
16
// The algorithms here work on the scatter space - the image space of the
17
// schedule returned by Scop::getSchedule(). We call an element in that space a
18
// "timepoint". Timepoints are lexicographically ordered such that we can
19
// defined ranges in the scatter space. We use two flavors of such ranges:
20
// Timepoint sets and zones. A timepoint set is simply a subset of the scatter
21
// space and is directly stored as isl_set.
22
//
23
// Zones are used to describe the space between timepoints as open sets, i.e.
24
// they do not contain the extrema. Using isl rational sets to express these
25
// would be overkill. We also cannot store them as the integer timepoints they
26
// contain; the (nonempty) zone between 1 and 2 would be empty and
27
// indistinguishable from e.g. the zone between 3 and 4. Also, we cannot store
28
// the integer set including the extrema; the set ]1,2[ + ]3,4[ could be
29
// coalesced to ]1,3[, although we defined the range [2,3] to be not in the set.
30
// Instead, we store the "half-open" integer extrema, including the lower bound,
31
// but excluding the upper bound. Examples:
32
//
33
// * The set { [i] : 1 <= i <= 3 } represents the zone ]0,3[ (which contains the
34
//   integer points 1 and 2, but not 0 or 3)
35
//
36
// * { [1] } represents the zone ]0,1[
37
//
38
// * { [i] : i = 1 or i = 3 } represents the zone ]0,1[ + ]2,3[
39
//
40
// Therefore, an integer i in the set represents the zone ]i-1,i[, i.e. strictly
41
// speaking the integer points never belong to the zone. However, depending an
42
// the interpretation, one might want to include them. Part of the
43
// interpretation may not be known when the zone is constructed.
44
//
45
// Reads are assumed to always take place before writes, hence we can think of
46
// reads taking place at the beginning of a timepoint and writes at the end.
47
//
48
// Let's assume that the zone represents the lifetime of a variable. That is,
49
// the zone begins with a write that defines the value during its lifetime and
50
// ends with the last read of that value. In the following we consider whether a
51
// read/write at the beginning/ending of the lifetime zone should be within the
52
// zone or outside of it.
53
//
54
// * A read at the timepoint that starts the live-range loads the previous
55
//   value. Hence, exclude the timepoint starting the zone.
56
//
57
// * A write at the timepoint that starts the live-range is not defined whether
58
//   it occurs before or after the write that starts the lifetime. We do not
59
//   allow this situation to occur. Hence, we include the timepoint starting the
60
//   zone to determine whether they are conflicting.
61
//
62
// * A read at the timepoint that ends the live-range reads the same variable.
63
//   We include the timepoint at the end of the zone to include that read into
64
//   the live-range. Doing otherwise would mean that the two reads access
65
//   different values, which would mean that the value they read are both alive
66
//   at the same time but occupy the same variable.
67
//
68
// * A write at the timepoint that ends the live-range starts a new live-range.
69
//   It must not be included in the live-range of the previous definition.
70
//
71
// All combinations of reads and writes at the endpoints are possible, but most
72
// of the time only the write->read (for instance, a live-range from definition
73
// to last use) and read->write (for instance, an unused range from last use to
74
// overwrite) and combinations are interesting (half-open ranges). write->write
75
// zones might be useful as well in some context to represent
76
// output-dependencies.
77
//
78
// @see convertZoneToTimepoints
79
//
80
//
81
// The code makes use of maps and sets in many different spaces. To not loose
82
// track in which space a set or map is expected to be in, variables holding an
83
// isl reference are usually annotated in the comments. They roughly follow isl
84
// syntax for spaces, but only the tuples, not the dimensions. The tuples have a
85
// meaning as follows:
86
//
87
// * Space[] - An unspecified tuple. Used for function parameters such that the
88
//             function caller can use it for anything they like.
89
//
90
// * Domain[] - A statement instance as returned by ScopStmt::getDomain()
91
//     isl_id_get_name: Stmt_<NameOfBasicBlock>
92
//     isl_id_get_user: Pointer to ScopStmt
93
//
94
// * Element[] - An array element as in the range part of
95
//               MemoryAccess::getAccessRelation()
96
//     isl_id_get_name: MemRef_<NameOfArrayVariable>
97
//     isl_id_get_user: Pointer to ScopArrayInfo
98
//
99
// * Scatter[] - Scatter space or space of timepoints
100
//     Has no tuple id
101
//
102
// * Zone[] - Range between timepoints as described above
103
//     Has no tuple id
104
//
105
// An annotation "{ Domain[] -> Scatter[] }" therefore means: A map from a
106
// statement instance to a timepoint, aka a schedule. There is only one scatter
107
// space, but most of the time multiple statements are processed in one set.
108
// This is why most of the time isl_union_map has to be used.
109
//
110
// The basic algorithm works as follows:
111
// At first we verify that the SCoP is compatible with this technique. For
112
// instance, two writes cannot write to the same location at the same statement
113
// instance because we cannot determine within the polyhedral model which one
114
// comes first. Once this was verified, we compute zones at which an array
115
// element is unused. This computation can fail if it takes too long. Then the
116
// main algorithm is executed. Because every store potentially trails an unused
117
// zone, we start at stores. We search for a scalar (MemoryKind::Value or
118
// MemoryKind::PHI) that we can map to the array element overwritten by the
119
// store, preferably one that is used by the store or at least the ScopStmt.
120
// When it does not conflict with the lifetime of the values in the array
121
// element, the map is applied and the unused zone updated as it is now used. We
122
// continue to try to map scalars to the array element until there are no more
123
// candidates to map. The algorithm is greedy in the sense that the first scalar
124
// not conflicting will be mapped. Other scalars processed later that could have
125
// fit the same unused zone will be rejected. As such the result depends on the
126
// processing order.
127
//
128
//===----------------------------------------------------------------------===//
129
130
#include "polly/DeLICM.h"
131
#include "polly/Options.h"
132
#include "polly/ScopInfo.h"
133
#include "polly/ScopPass.h"
134
#include "polly/Support/ISLTools.h"
135
#include "llvm/ADT/Statistic.h"
136
11
#define DEBUG_TYPE "polly-delicm"
137
138
using namespace polly;
139
using namespace llvm;
140
141
namespace {
142
143
cl::opt<int>
144
    DelicmMaxOps("polly-delicm-max-ops",
145
                 cl::desc("Maximum number of isl operations to invest for "
146
                          "lifetime analysis; 0=no limit"),
147
                 cl::init(1000000), cl::cat(PollyCategory));
148
149
cl::opt<bool> DelicmOverapproximateWrites(
150
    "polly-delicm-overapproximate-writes",
151
    cl::desc(
152
        "Do more PHI writes than necessary in order to avoid partial accesses"),
153
    cl::init(false), cl::Hidden, cl::cat(PollyCategory));
154
155
STATISTIC(DeLICMAnalyzed, "Number of successfully analyzed SCoPs");
156
STATISTIC(DeLICMOutOfQuota,
157
          "Analyses aborted because max_operations was reached");
158
STATISTIC(DeLICMIncompatible, "Number of SCoPs incompatible for analysis");
159
STATISTIC(MappedValueScalars, "Number of mapped Value scalars");
160
STATISTIC(MappedPHIScalars, "Number of mapped PHI scalars");
161
STATISTIC(TargetsMapped, "Number of stores used for at least one mapping");
162
STATISTIC(DeLICMScopsModified, "Number of SCoPs optimized");
163
164
/// Class for keeping track of scalar def-use chains in the polyhedral
165
/// representation.
166
///
167
/// MemoryKind::Value:
168
/// There is one definition per llvm::Value or zero (read-only values defined
169
/// before the SCoP) and an arbitrary number of reads.
170
///
171
/// MemoryKind::PHI, MemoryKind::ExitPHI:
172
/// There is at least one write (the incoming blocks/stmts) and one
173
/// (MemoryKind::PHI) or zero (MemoryKind::ExitPHI) reads per llvm::PHINode.
174
class ScalarDefUseChains {
175
private:
176
  /// The definitions (i.e. write MemoryAccess) of a MemoryKind::Value scalar.
177
  DenseMap<const ScopArrayInfo *, MemoryAccess *> ValueDefAccs;
178
179
  /// List of all uses (i.e. read MemoryAccesses) for a MemoryKind::Value
180
  /// scalar.
181
  DenseMap<const ScopArrayInfo *, SmallVector<MemoryAccess *, 4>> ValueUseAccs;
182
183
  /// The receiving part (i.e. read MemoryAccess) of a MemoryKind::PHI scalar.
184
  DenseMap<const ScopArrayInfo *, MemoryAccess *> PHIReadAccs;
185
186
  /// List of all incoming values (write MemoryAccess) of a MemoryKind::PHI or
187
  /// MemoryKind::ExitPHI scalar.
188
  DenseMap<const ScopArrayInfo *, SmallVector<MemoryAccess *, 4>>
189
      PHIIncomingAccs;
190
191
public:
192
  /// Find the MemoryAccesses that access the ScopArrayInfo-represented memory.
193
  ///
194
  /// @param S The SCoP to analyze.
195
15
  void compute(Scop *S) {
196
15
    // Purge any previous result.
197
15
    reset();
198
15
199
74
    for (auto &Stmt : *S) {
200
143
      for (auto *MA : Stmt) {
201
143
        if (
MA->isOriginalValueKind() && 143
MA->isWrite()75
)
{31
202
31
          auto *SAI = MA->getScopArrayInfo();
203
31
          assert(!ValueDefAccs.count(SAI) &&
204
31
                 "There can be at most one "
205
31
                 "definition per MemoryKind::Value scalar");
206
31
          ValueDefAccs[SAI] = MA;
207
31
        }
208
143
209
143
        if (
MA->isOriginalValueKind() && 143
MA->isRead()75
)
210
44
          ValueUseAccs[MA->getScopArrayInfo()].push_back(MA);
211
143
212
143
        if (
MA->isOriginalAnyPHIKind() && 143
MA->isRead()50
)
{17
213
17
          auto *SAI = MA->getScopArrayInfo();
214
17
          assert(!PHIReadAccs.count(SAI) &&
215
17
                 "There must be exactly one read "
216
17
                 "per PHI (that's where the PHINode is)");
217
17
          PHIReadAccs[SAI] = MA;
218
17
        }
219
143
220
143
        if (
MA->isOriginalAnyPHIKind() && 143
MA->isWrite()50
)
221
33
          PHIIncomingAccs[MA->getScopArrayInfo()].push_back(MA);
222
143
      }
223
74
    }
224
15
  }
225
226
  /// Free all memory used by the analysis.
227
15
  void reset() {
228
15
    ValueDefAccs.clear();
229
15
    ValueUseAccs.clear();
230
15
    PHIReadAccs.clear();
231
15
    PHIIncomingAccs.clear();
232
15
  }
233
234
48
  MemoryAccess *getValueDef(const ScopArrayInfo *SAI) const {
235
48
    return ValueDefAccs.lookup(SAI);
236
48
  }
237
238
17
  ArrayRef<MemoryAccess *> getValueUses(const ScopArrayInfo *SAI) const {
239
17
    auto It = ValueUseAccs.find(SAI);
240
17
    if (It == ValueUseAccs.end())
241
0
      return {};
242
17
    return It->second;
243
17
  }
244
245
21
  MemoryAccess *getPHIRead(const ScopArrayInfo *SAI) const {
246
21
    return PHIReadAccs.lookup(SAI);
247
21
  }
248
249
18
  ArrayRef<MemoryAccess *> getPHIIncomings(const ScopArrayInfo *SAI) const {
250
18
    auto It = PHIIncomingAccs.find(SAI);
251
18
    if (It == PHIIncomingAccs.end())
252
0
      return {};
253
18
    return It->second;
254
18
  }
255
};
256
257
isl::union_map computeReachingDefinition(isl::union_map Schedule,
258
                                         isl::union_map Writes, bool InclDef,
259
9
                                         bool InclRedef) {
260
9
  return computeReachingWrite(Schedule, Writes, false, InclDef, InclRedef);
261
9
}
262
263
isl::union_map computeReachingOverwrite(isl::union_map Schedule,
264
                                        isl::union_map Writes,
265
                                        bool InclPrevWrite,
266
10
                                        bool InclOverwrite) {
267
10
  return computeReachingWrite(Schedule, Writes, true, InclPrevWrite,
268
10
                              InclOverwrite);
269
10
}
270
271
/// Compute the next overwrite for a scalar.
272
///
273
/// @param Schedule      { DomainWrite[] -> Scatter[] }
274
///                      Schedule of (at least) all writes. Instances not in @p
275
///                      Writes are ignored.
276
/// @param Writes        { DomainWrite[] }
277
///                      The element instances that write to the scalar.
278
/// @param InclPrevWrite Whether to extend the timepoints to include
279
///                      the timepoint where the previous write happens.
280
/// @param InclOverwrite Whether the reaching overwrite includes the timepoint
281
///                      of the overwrite itself.
282
///
283
/// @return { Scatter[] -> DomainDef[] }
284
isl::union_map computeScalarReachingOverwrite(isl::union_map Schedule,
285
                                              isl::union_set Writes,
286
                                              bool InclPrevWrite,
287
10
                                              bool InclOverwrite) {
288
10
289
10
  // { DomainWrite[] }
290
10
  auto WritesMap = give(isl_union_map_from_domain(Writes.take()));
291
10
292
10
  // { [Element[] -> Scatter[]] -> DomainWrite[] }
293
10
  auto Result = computeReachingOverwrite(
294
10
      std::move(Schedule), std::move(WritesMap), InclPrevWrite, InclOverwrite);
295
10
296
10
  return give(isl_union_map_domain_factor_range(Result.take()));
297
10
}
298
299
/// Overload of computeScalarReachingOverwrite, with only one writing statement.
300
/// Consequently, the result consists of only one map space.
301
///
302
/// @param Schedule      { DomainWrite[] -> Scatter[] }
303
/// @param Writes        { DomainWrite[] }
304
/// @param InclPrevWrite Include the previous write to result.
305
/// @param InclOverwrite Include the overwrite to the result.
306
///
307
/// @return { Scatter[] -> DomainWrite[] }
308
isl::map computeScalarReachingOverwrite(isl::union_map Schedule,
309
                                        isl::set Writes, bool InclPrevWrite,
310
10
                                        bool InclOverwrite) {
311
10
  auto ScatterSpace = getScatterSpace(Schedule);
312
10
  auto DomSpace = give(isl_set_get_space(Writes.keep()));
313
10
314
10
  auto ReachOverwrite = computeScalarReachingOverwrite(
315
10
      Schedule, give(isl_union_set_from_set(Writes.take())), InclPrevWrite,
316
10
      InclOverwrite);
317
10
318
10
  auto ResultSpace = give(isl_space_map_from_domain_and_range(
319
10
      ScatterSpace.take(), DomSpace.take()));
320
10
  return singleton(std::move(ReachOverwrite), ResultSpace);
321
10
}
322
323
/// Compute the reaching definition of a scalar.
324
///
325
/// Compared to computeReachingDefinition, there is just one element which is
326
/// accessed and therefore only a set if instances that accesses that element is
327
/// required.
328
///
329
/// @param Schedule  { DomainWrite[] -> Scatter[] }
330
/// @param Writes    { DomainWrite[] }
331
/// @param InclDef   Include the timepoint of the definition to the result.
332
/// @param InclRedef Include the timepoint of the overwrite into the result.
333
///
334
/// @return { Scatter[] -> DomainWrite[] }
335
isl::union_map computeScalarReachingDefinition(isl::union_map Schedule,
336
                                               isl::union_set Writes,
337
9
                                               bool InclDef, bool InclRedef) {
338
9
339
9
  // { DomainWrite[] -> Element[] }
340
9
  auto Defs = give(isl_union_map_from_domain(Writes.take()));
341
9
342
9
  // { [Element[] -> Scatter[]] -> DomainWrite[] }
343
9
  auto ReachDefs =
344
9
      computeReachingDefinition(Schedule, Defs, InclDef, InclRedef);
345
9
346
9
  // { Scatter[] -> DomainWrite[] }
347
9
  return give(isl_union_set_unwrap(
348
9
      isl_union_map_range(isl_union_map_curry(ReachDefs.take()))));
349
9
}
350
351
/// Compute the reaching definition of a scalar.
352
///
353
/// This overload accepts only a single writing statement as an isl_map,
354
/// consequently the result also is only a single isl_map.
355
///
356
/// @param Schedule  { DomainWrite[] -> Scatter[] }
357
/// @param Writes    { DomainWrite[] }
358
/// @param InclDef   Include the timepoint of the definition to the result.
359
/// @param InclRedef Include the timepoint of the overwrite into the result.
360
///
361
/// @return { Scatter[] -> DomainWrite[] }
362
isl::map computeScalarReachingDefinition( // { Domain[] -> Zone[] }
363
9
    isl::union_map Schedule, isl::set Writes, bool InclDef, bool InclRedef) {
364
9
  auto DomainSpace = give(isl_set_get_space(Writes.keep()));
365
9
  auto ScatterSpace = getScatterSpace(Schedule);
366
9
367
9
  //  { Scatter[] -> DomainWrite[] }
368
9
  auto UMap = computeScalarReachingDefinition(
369
9
      Schedule, give(isl_union_set_from_set(Writes.take())), InclDef,
370
9
      InclRedef);
371
9
372
9
  auto ResultSpace = give(isl_space_map_from_domain_and_range(
373
9
      ScatterSpace.take(), DomainSpace.take()));
374
9
  return singleton(UMap, ResultSpace);
375
9
}
376
377
/// Create a domain-to-unknown value mapping.
378
///
379
/// Value instances that do not represent a specific value are represented by an
380
/// unnamed tuple of 0 dimensions. Its meaning depends on the context. It can
381
/// either mean a specific but unknown value which cannot be represented by
382
/// other means. It conflicts with itself because those two unknown ValInsts may
383
/// have different concrete values at runtime.
384
///
385
/// The other meaning is an arbitrary or wildcard value that can be chosen
386
/// freely, like LLVM's undef. If matched with an unknown ValInst, there is no
387
/// conflict.
388
///
389
/// @param Domain { Domain[] }
390
///
391
/// @return { Domain[] -> ValInst[] }
392
496
isl::union_map makeUnknownForDomain(isl::union_set Domain) {
393
496
  return give(isl_union_map_from_domain(Domain.take()));
394
496
}
395
396
/// If InputVal is not defined in the stmt itself, return the MemoryAccess that
397
/// reads the scalar. Return nullptr otherwise (if the value is defined in the
398
/// scop, or is synthesizable).
399
10
MemoryAccess *getInputAccessOf(Value *InputVal, ScopStmt *Stmt) {
400
20
  for (auto *MA : *Stmt) {
401
20
    if (!MA->isRead())
402
8
      continue;
403
12
    
if (12
!MA->isLatestScalarKind()12
)
404
1
      continue;
405
12
406
11
    assert(MA->getAccessValue() == MA->getBaseAddr());
407
11
    if (MA->getAccessValue() == InputVal)
408
8
      return MA;
409
11
  }
410
2
  return nullptr;
411
10
}
412
413
/// Return whether @p Map maps to an unknown value.
414
///
415
/// @param { [] -> ValInst[] }
416
194
bool isMapToUnknown(const isl::map &Map) {
417
194
  auto Space = give(isl_space_range(isl_map_get_space(Map.keep())));
418
194
  return !isl_map_has_tuple_id(Map.keep(), isl_dim_set) &&
419
98
         !isl_space_is_wrapping(Space.keep()) &&
420
98
         isl_map_dim(Map.keep(), isl_dim_out) == 0;
421
194
}
422
423
/// Return only the mappings that map to known values.
424
///
425
/// @param UMap { [] -> ValInst[] }
426
///
427
/// @return { [] -> ValInst[] }
428
306
isl::union_map filterKnownValInst(const isl::union_map &UMap) {
429
306
  auto Result = give(isl_union_map_empty(isl_union_map_get_space(UMap.keep())));
430
194
  UMap.foreach_map([=, &Result](isl::map Map) -> isl::stat {
431
194
    if (!isMapToUnknown(Map))
432
96
      Result = give(isl_union_map_add_map(Result.take(), Map.take()));
433
194
    return isl::stat::ok;
434
194
  });
435
306
  return Result;
436
306
}
437
438
/// Try to find a 'natural' extension of a mapped to elements outside its
439
/// domain.
440
///
441
/// @param Relevant The map with mapping that may not be modified.
442
/// @param Universe The domain to which @p Relevant needs to be extended.
443
///
444
/// @return A map with that associates the domain elements of @p Relevant to the
445
///         same elements and in addition the elements of @p Universe to some
446
///         undefined elements. The function prefers to return simple maps.
447
2
isl::union_map expandMapping(isl::union_map Relevant, isl::union_set Universe) {
448
2
  Relevant = give(isl_union_map_coalesce(Relevant.take()));
449
2
  auto RelevantDomain = give(isl_union_map_domain(Relevant.copy()));
450
2
  auto Simplified =
451
2
      give(isl_union_map_gist_domain(Relevant.take(), RelevantDomain.take()));
452
2
  Simplified = give(isl_union_map_coalesce(Simplified.take()));
453
2
  return give(
454
2
      isl_union_map_intersect_domain(Simplified.take(), Universe.take()));
455
2
}
456
457
/// Represent the knowledge of the contents of any array elements in any zone or
458
/// the knowledge we would add when mapping a scalar to an array element.
459
///
460
/// Every array element at every zone unit has one of two states:
461
///
462
/// - Unused: Not occupied by any value so a transformation can change it to
463
///   other values.
464
///
465
/// - Occupied: The element contains a value that is still needed.
466
///
467
/// The union of Unused and Unknown zones forms the universe, the set of all
468
/// elements at every timepoint. The universe can easily be derived from the
469
/// array elements that are accessed someway. Arrays that are never accessed
470
/// also never play a role in any computation and can hence be ignored. With a
471
/// given universe, only one of the sets needs to stored implicitly. Computing
472
/// the complement is also an expensive operation, hence this class has been
473
/// designed that only one of sets is needed while the other is assumed to be
474
/// implicit. It can still be given, but is mostly ignored.
475
///
476
/// There are two use cases for the Knowledge class:
477
///
478
/// 1) To represent the knowledge of the current state of ScopInfo. The unused
479
///    state means that an element is currently unused: there is no read of it
480
///    before the next overwrite. Also called 'Existing'.
481
///
482
/// 2) To represent the requirements for mapping a scalar to array elements. The
483
///    unused state means that there is no change/requirement. Also called
484
///    'Proposed'.
485
///
486
/// In addition to these states at unit zones, Knowledge needs to know when
487
/// values are written. This is because written values may have no lifetime (one
488
/// reason is that the value is never read). Such writes would therefore never
489
/// conflict, but overwrite values that might still be required. Another source
490
/// of problems are multiple writes to the same element at the same timepoint,
491
/// because their order is undefined.
492
class Knowledge {
493
private:
494
  /// { [Element[] -> Zone[]] }
495
  /// Set of array elements and when they are alive.
496
  /// Can contain a nullptr; in this case the set is implicitly defined as the
497
  /// complement of #Unused.
498
  ///
499
  /// The set of alive array elements is represented as zone, as the set of live
500
  /// values can differ depending on how the elements are interpreted.
501
  /// Assuming a value X is written at timestep [0] and read at timestep [1]
502
  /// without being used at any later point, then the value is alive in the
503
  /// interval ]0,1[. This interval cannot be represented by an integer set, as
504
  /// it does not contain any integer point. Zones allow us to represent this
505
  /// interval and can be converted to sets of timepoints when needed (e.g., in
506
  /// isConflicting when comparing to the write sets).
507
  /// @see convertZoneToTimepoints and this file's comment for more details.
508
  isl::union_set Occupied;
509
510
  /// { [Element[] -> Zone[]] }
511
  /// Set of array elements when they are not alive, i.e. their memory can be
512
  /// used for other purposed. Can contain a nullptr; in this case the set is
513
  /// implicitly defined as the complement of #Occupied.
514
  isl::union_set Unused;
515
516
  /// { [Element[] -> Zone[]] -> ValInst[] }
517
  /// Maps to the known content for each array element at any interval.
518
  ///
519
  /// Any element/interval can map to multiple known elements. This is due to
520
  /// multiple llvm::Value referring to the same content. Examples are
521
  ///
522
  /// - A value stored and loaded again. The LoadInst represents the same value
523
  /// as the StoreInst's value operand.
524
  ///
525
  /// - A PHINode is equal to any one of the incoming values. In case of
526
  /// LCSSA-form, it is always equal to its single incoming value.
527
  ///
528
  /// Two Knowledges are considered not conflicting if at least one of the known
529
  /// values match. Not known values are not stored as an unnamed tuple (as
530
  /// #Written does), but maps to nothing.
531
  ///
532
  ///  Known values are usually just defined for #Occupied elements. Knowing
533
  ///  #Unused contents has no advantage as it can be overwritten.
534
  isl::union_map Known;
535
536
  /// { [Element[] -> Scatter[]] -> ValInst[] }
537
  /// The write actions currently in the scop or that would be added when
538
  /// mapping a scalar. Maps to the value that is written.
539
  ///
540
  /// Written values that cannot be identified are represented by an unknown
541
  /// ValInst[] (an unnamed tuple of 0 dimension). It conflicts with itself.
542
  isl::union_map Written;
543
544
  /// Check whether this Knowledge object is well-formed.
545
503
  void checkConsistency() const {
546
503
#ifndef NDEBUG
547
    // Default-initialized object
548
    if (!Occupied && !Unused && !Known && !Written)
549
      return;
550
551
    assert(Occupied || Unused);
552
    assert(Known);
553
    assert(Written);
554
555
    // If not all fields are defined, we cannot derived the universe.
556
    if (!Occupied || !Unused)
557
      return;
558
559
    assert(isl_union_set_is_disjoint(Occupied.keep(), Unused.keep()) ==
560
           isl_bool_true);
561
    auto Universe = give(isl_union_set_union(Occupied.copy(), Unused.copy()));
562
563
    assert(!Known.domain().is_subset(Universe).is_false());
564
    assert(!Written.domain().is_subset(Universe).is_false());
565
#endif
566
503
  }
567
568
public:
569
  /// Initialize a nullptr-Knowledge. This is only provided for convenience; do
570
  /// not use such an object.
571
38
  Knowledge() {}
572
573
  /// Create a new object with the given members.
574
  Knowledge(isl::union_set Occupied, isl::union_set Unused,
575
            isl::union_set Written)
576
      : Occupied(std::move(Occupied)), Unused(std::move(Unused)),
577
        Known(isl::manage(
578
            isl_union_map_empty(isl_union_set_get_space(Written.keep())))),
579
30
        Written(isl::manage(isl_union_map_from_domain(Written.take()))) {
580
30
    checkConsistency();
581
30
  }
582
583
  /// Create a new object with the given members.
584
  Knowledge(isl::union_set Occupied, isl::union_set Unused,
585
            isl::union_map Known, isl::union_map Written)
586
      : Occupied(std::move(Occupied)), Unused(std::move(Unused)),
587
464
        Known(std::move(Known)), Written(std::move(Written)) {
588
464
    checkConsistency();
589
464
  }
590
591
  /// Return whether this object was not default-constructed.
592
19
  bool isUsable() const 
{ return (Occupied || 19
Unused19
) &&
Known14
&&
Written14
; }
593
594
  /// Print the content of this object to @p OS.
595
0
  void print(llvm::raw_ostream &OS, unsigned Indent = 0) const {
596
0
    if (isUsable()) {
597
0
      if (Occupied)
598
0
        OS.indent(Indent) << "Occupied: " << Occupied << "\n";
599
0
      else
600
0
        OS.indent(Indent) << "Occupied: <Everything else not in Unused>\n";
601
0
      if (Unused)
602
0
        OS.indent(Indent) << "Unused:   " << Unused << "\n";
603
0
      else
604
0
        OS.indent(Indent) << "Unused:   <Everything else not in Occupied>\n";
605
0
      OS.indent(Indent) << "Known:    " << Known << "\n";
606
0
      OS.indent(Indent) << "Written : " << Written << '\n';
607
0
    } else {
608
0
      OS.indent(Indent) << "Invalid knowledge\n";
609
0
    }
610
0
  }
611
612
  /// Combine two knowledges, this and @p That.
613
9
  void learnFrom(Knowledge That) {
614
9
    assert(!isConflicting(*this, That));
615
9
    assert(Unused && That.Occupied);
616
9
    assert(
617
9
        !That.Unused &&
618
9
        "This function is only prepared to learn occupied elements from That");
619
9
    assert(!Occupied && "This function does not implement "
620
9
                        "`this->Occupied = "
621
9
                        "give(isl_union_set_union(this->Occupied.take(), "
622
9
                        "That.Occupied.copy()));`");
623
9
624
9
    Unused = give(isl_union_set_subtract(Unused.take(), That.Occupied.copy()));
625
9
    Known = give(isl_union_map_union(Known.take(), That.Known.copy()));
626
9
    Written = give(isl_union_map_union(Written.take(), That.Written.take()));
627
9
628
9
    checkConsistency();
629
9
  }
630
631
  /// Determine whether two Knowledges conflict with each other.
632
  ///
633
  /// In theory @p Existing and @p Proposed are symmetric, but the
634
  /// implementation is constrained by the implicit interpretation. That is, @p
635
  /// Existing must have #Unused defined (use case 1) and @p Proposed must have
636
  /// #Occupied defined (use case 1).
637
  ///
638
  /// A conflict is defined as non-preserved semantics when they are merged. For
639
  /// instance, when for the same array and zone they assume different
640
  /// llvm::Values.
641
  ///
642
  /// @param Existing One of the knowledges with #Unused defined.
643
  /// @param Proposed One of the knowledges with #Occupied defined.
644
  /// @param OS       Dump the conflict reason to this output stream; use
645
  ///                 nullptr to not output anything.
646
  /// @param Indent   Indention for the conflict reason.
647
  ///
648
  /// @return True, iff the two knowledges are conflicting.
649
  static bool isConflicting(const Knowledge &Existing,
650
                            const Knowledge &Proposed,
651
                            llvm::raw_ostream *OS = nullptr,
652
248
                            unsigned Indent = 0) {
653
248
    assert(Existing.Unused);
654
248
    assert(Proposed.Occupied);
655
248
656
248
#ifndef NDEBUG
657
    if (Existing.Occupied && Proposed.Unused) {
658
      auto ExistingUniverse = give(isl_union_set_union(Existing.Occupied.copy(),
659
                                                       Existing.Unused.copy()));
660
      auto ProposedUniverse = give(isl_union_set_union(Proposed.Occupied.copy(),
661
                                                       Proposed.Unused.copy()));
662
      assert(isl_union_set_is_equal(ExistingUniverse.keep(),
663
                                    ProposedUniverse.keep()) == isl_bool_true &&
664
             "Both inputs' Knowledges must be over the same universe");
665
    }
666
#endif
667
248
668
248
    // Do the Existing and Proposed lifetimes conflict?
669
248
    //
670
248
    // Lifetimes are described as the cross-product of array elements and zone
671
248
    // intervals in which they are alive (the space { [Element[] -> Zone[]] }).
672
248
    // In the following we call this "element/lifetime interval".
673
248
    //
674
248
    // In order to not conflict, one of the following conditions must apply for
675
248
    // each element/lifetime interval:
676
248
    //
677
248
    // 1. If occupied in one of the knowledges, it is unused in the other.
678
248
    //
679
248
    //   - or -
680
248
    //
681
248
    // 2. Both contain the same value.
682
248
    //
683
248
    // Instead of partitioning the element/lifetime intervals into a part that
684
248
    // both Knowledges occupy (which requires an expensive subtraction) and for
685
248
    // these to check whether they are known to be the same value, we check only
686
248
    // the second condition and ensure that it also applies when then first
687
248
    // condition is true. This is done by adding a wildcard value to
688
248
    // Proposed.Known and Existing.Unused such that they match as a common known
689
248
    // value. We use the "unknown ValInst" for this purpose. Every
690
248
    // Existing.Unused may match with an unknown Proposed.Occupied because these
691
248
    // never are in conflict with each other.
692
248
    auto ProposedOccupiedAnyVal = makeUnknownForDomain(Proposed.Occupied);
693
248
    auto ProposedValues = Proposed.Known.unite(ProposedOccupiedAnyVal);
694
248
695
248
    auto ExistingUnusedAnyVal = makeUnknownForDomain(Existing.Unused);
696
248
    auto ExistingValues = Existing.Known.unite(ExistingUnusedAnyVal);
697
248
698
248
    auto MatchingVals = ExistingValues.intersect(ProposedValues);
699
248
    auto Matches = MatchingVals.domain();
700
248
701
248
    // Any Proposed.Occupied must either have a match between the known values
702
248
    // of Existing and Occupied, or be in Existing.Unused. In the latter case,
703
248
    // the previously added "AnyVal" will match each other.
704
248
    if (
!Proposed.Occupied.is_subset(Matches)248
)
{44
705
44
      if (
OS44
)
{0
706
0
        auto Conflicting = Proposed.Occupied.subtract(Matches);
707
0
        auto ExistingConflictingKnown =
708
0
            Existing.Known.intersect_domain(Conflicting);
709
0
        auto ProposedConflictingKnown =
710
0
            Proposed.Known.intersect_domain(Conflicting);
711
0
712
0
        OS->indent(Indent) << "Proposed lifetime conflicting with Existing's\n";
713
0
        OS->indent(Indent) << "Conflicting occupied: " << Conflicting << "\n";
714
0
        if (!ExistingConflictingKnown.is_empty())
715
0
          OS->indent(Indent)
716
0
              << "Existing Known:       " << ExistingConflictingKnown << "\n";
717
0
        if (!ProposedConflictingKnown.is_empty())
718
0
          OS->indent(Indent)
719
0
              << "Proposed Known:       " << ProposedConflictingKnown << "\n";
720
0
      }
721
44
      return true;
722
44
    }
723
248
724
248
    // Do the writes in Existing conflict with occupied values in Proposed?
725
248
    //
726
248
    // In order to not conflict, it must either write to unused lifetime or
727
248
    // write the same value. To check, we remove the writes that write into
728
248
    // Proposed.Unused (they never conflict) and then see whether the written
729
248
    // value is already in Proposed.Known. If there are multiple known values
730
248
    // and a written value is known under different names, it is enough when one
731
248
    // of the written values (assuming that they are the same value under
732
248
    // different names, e.g. a PHINode and one of the incoming values) matches
733
248
    // one of the known names.
734
248
    //
735
248
    // We convert here the set of lifetimes to actual timepoints. A lifetime is
736
248
    // in conflict with a set of write timepoints, if either a live timepoint is
737
248
    // clearly within the lifetime or if a write happens at the beginning of the
738
248
    // lifetime (where it would conflict with the value that actually writes the
739
248
    // value alive). There is no conflict at the end of a lifetime, as the alive
740
248
    // value will always be read, before it is overwritten again. The last
741
248
    // property holds in Polly for all scalar values and we expect all users of
742
248
    // Knowledge to check this property also for accesses to MemoryKind::Array.
743
204
    auto ProposedFixedDefs =
744
204
        convertZoneToTimepoints(Proposed.Occupied, true, false);
745
204
    auto ProposedFixedKnown =
746
204
        convertZoneToTimepoints(Proposed.Known, isl::dim::in, true, false);
747
204
748
204
    auto ExistingConflictingWrites =
749
204
        Existing.Written.intersect_domain(ProposedFixedDefs);
750
204
    auto ExistingConflictingWritesDomain = ExistingConflictingWrites.domain();
751
204
752
204
    auto CommonWrittenVal =
753
204
        ProposedFixedKnown.intersect(ExistingConflictingWrites);
754
204
    auto CommonWrittenValDomain = CommonWrittenVal.domain();
755
204
756
204
    if (
!ExistingConflictingWritesDomain.is_subset(CommonWrittenValDomain)204
)
{27
757
27
      if (
OS27
)
{0
758
0
        auto ExistingConflictingWritten =
759
0
            ExistingConflictingWrites.subtract_domain(CommonWrittenValDomain);
760
0
        auto ProposedConflictingKnown = ProposedFixedKnown.subtract_domain(
761
0
            ExistingConflictingWritten.domain());
762
0
763
0
        OS->indent(Indent)
764
0
            << "Proposed a lifetime where there is an Existing write into it\n";
765
0
        OS->indent(Indent) << "Existing conflicting writes: "
766
0
                           << ExistingConflictingWritten << "\n";
767
0
        if (!ProposedConflictingKnown.is_empty())
768
0
          OS->indent(Indent)
769
0
              << "Proposed conflicting known:  " << ProposedConflictingKnown
770
0
              << "\n";
771
0
      }
772
27
      return true;
773
27
    }
774
204
775
204
    // Do the writes in Proposed conflict with occupied values in Existing?
776
177
    auto ExistingAvailableDefs =
777
177
        convertZoneToTimepoints(Existing.Unused, true, false);
778
177
    auto ExistingKnownDefs =
779
177
        convertZoneToTimepoints(Existing.Known, isl::dim::in, true, false);
780
177
781
177
    auto ProposedWrittenDomain = Proposed.Written.domain();
782
177
    auto KnownIdentical = ExistingKnownDefs.intersect(Proposed.Written);
783
177
    auto IdenticalOrUnused =
784
177
        ExistingAvailableDefs.unite(KnownIdentical.domain());
785
177
    if (
!ProposedWrittenDomain.is_subset(IdenticalOrUnused)177
)
{24
786
24
      if (
OS24
)
{0
787
0
        auto Conflicting = ProposedWrittenDomain.subtract(IdenticalOrUnused);
788
0
        auto ExistingConflictingKnown =
789
0
            ExistingKnownDefs.intersect_domain(Conflicting);
790
0
        auto ProposedConflictingWritten =
791
0
            Proposed.Written.intersect_domain(Conflicting);
792
0
793
0
        OS->indent(Indent) << "Proposed writes into range used by Existing\n";
794
0
        OS->indent(Indent) << "Proposed conflicting writes: "
795
0
                           << ProposedConflictingWritten << "\n";
796
0
        if (!ExistingConflictingKnown.is_empty())
797
0
          OS->indent(Indent)
798
0
              << "Existing conflicting known: " << ExistingConflictingKnown
799
0
              << "\n";
800
0
      }
801
24
      return true;
802
24
    }
803
177
804
177
    // Does Proposed write at the same time as Existing already does (order of
805
177
    // writes is undefined)? Writing the same value is permitted.
806
153
    auto ExistingWrittenDomain =
807
153
        isl::manage(isl_union_map_domain(Existing.Written.copy()));
808
153
    auto BothWritten =
809
153
        Existing.Written.domain().intersect(Proposed.Written.domain());
810
153
    auto ExistingKnownWritten = filterKnownValInst(Existing.Written);
811
153
    auto ProposedKnownWritten = filterKnownValInst(Proposed.Written);
812
153
    auto CommonWritten =
813
153
        ExistingKnownWritten.intersect(ProposedKnownWritten).domain();
814
153
815
153
    if (
!BothWritten.is_subset(CommonWritten)153
)
{24
816
24
      if (
OS24
)
{0
817
0
        auto Conflicting = BothWritten.subtract(CommonWritten);
818
0
        auto ExistingConflictingWritten =
819
0
            Existing.Written.intersect_domain(Conflicting);
820
0
        auto ProposedConflictingWritten =
821
0
            Proposed.Written.intersect_domain(Conflicting);
822
0
823
0
        OS->indent(Indent) << "Proposed writes at the same time as an already "
824
0
                              "Existing write\n";
825
0
        OS->indent(Indent) << "Conflicting writes: " << Conflicting << "\n";
826
0
        if (!ExistingConflictingWritten.is_empty())
827
0
          OS->indent(Indent)
828
0
              << "Exiting write:      " << ExistingConflictingWritten << "\n";
829
0
        if (!ProposedConflictingWritten.is_empty())
830
0
          OS->indent(Indent)
831
0
              << "Proposed write:     " << ProposedConflictingWritten << "\n";
832
0
      }
833
24
      return true;
834
24
    }
835
153
836
129
    return false;
837
153
  }
838
};
839
840
1
std::string printIntruction(Instruction *Instr, bool IsForDebug = false) {
841
1
  std::string Result;
842
1
  raw_string_ostream OS(Result);
843
1
  Instr->print(OS, IsForDebug);
844
1
  OS.flush();
845
1
  size_t i = 0;
846
3
  while (
i < Result.size() && 3
Result[i] == ' '3
)
847
2
    i += 1;
848
1
  return Result.substr(i);
849
1
}
850
851
/// Base class for algorithms based on zones, like DeLICM.
852
class ZoneAlgorithm {
853
protected:
854
  /// Hold a reference to the isl_ctx to avoid it being freed before we released
855
  /// all of the isl objects.
856
  ///
857
  /// This must be declared before any other member that holds an isl object.
858
  /// This guarantees that the shared_ptr and its isl_ctx is destructed last,
859
  /// after all other members free'd the isl objects they were holding.
860
  std::shared_ptr<isl_ctx> IslCtx;
861
862
  /// Cached reaching definitions for each ScopStmt.
863
  ///
864
  /// Use getScalarReachingDefinition() to get its contents.
865
  DenseMap<ScopStmt *, isl::map> ScalarReachDefZone;
866
867
  /// The analyzed Scop.
868
  Scop *S;
869
870
  /// Parameter space that does not need realignment.
871
  isl::space ParamSpace;
872
873
  /// Space the schedule maps to.
874
  isl::space ScatterSpace;
875
876
  /// Cached version of the schedule and domains.
877
  isl::union_map Schedule;
878
879
  /// Combined access relations of all MemoryKind::Array READ accesses.
880
  /// { DomainRead[] -> Element[] }
881
  isl::union_map AllReads;
882
883
  /// Combined access relations of all MemoryKind::Array, MAY_WRITE accesses.
884
  /// { DomainMayWrite[] -> Element[] }
885
  isl::union_map AllMayWrites;
886
887
  /// Combined access relations of all MemoryKind::Array, MUST_WRITE accesses.
888
  /// { DomainMustWrite[] -> Element[] }
889
  isl::union_map AllMustWrites;
890
891
  /// Prepare the object before computing the zones of @p S.
892
  ZoneAlgorithm(Scop *S)
893
19
      : IslCtx(S->getSharedIslCtx()), S(S), Schedule(give(S->getSchedule())) {
894
19
895
19
    auto Domains = give(S->getDomains());
896
19
897
19
    Schedule =
898
19
        give(isl_union_map_intersect_domain(Schedule.take(), Domains.take()));
899
19
    ParamSpace = give(isl_union_map_get_space(Schedule.keep()));
900
19
    ScatterSpace = getScatterSpace(Schedule);
901
19
  }
902
903
private:
904
  /// Check whether @p Stmt can be accurately analyzed by zones.
905
  ///
906
  /// What violates our assumptions:
907
  /// - A load after a write of the same location; we assume that all reads
908
  ///   occur before the writes.
909
  /// - Two writes to the same location; we cannot model the order in which
910
  ///   these occur.
911
  ///
912
  /// Scalar reads implicitly always occur before other accesses therefore never
913
  /// violate the first condition. There is also at most one write to a scalar,
914
  /// satisfying the second condition.
915
88
  bool isCompatibleStmt(ScopStmt *Stmt) {
916
88
    auto Stores = makeEmptyUnionMap();
917
88
    auto Loads = makeEmptyUnionMap();
918
88
919
88
    // This assumes that the MemoryKind::Array MemoryAccesses are iterated in
920
88
    // order.
921
170
    for (auto *MA : *Stmt) {
922
170
      if (!MA->isLatestArrayKind())
923
145
        continue;
924
170
925
25
      auto AccRel =
926
25
          give(isl_union_map_from_map(getAccessRelationFor(MA).take()));
927
25
928
25
      if (
MA->isRead()25
)
{3
929
3
        // Reject load after store to same location.
930
3
        if (
!isl_union_map_is_disjoint(Stores.keep(), AccRel.keep())3
)
{1
931
1
          OptimizationRemarkMissed R(DEBUG_TYPE, "LoadAfterStore",
932
1
                                     MA->getAccessInstruction());
933
1
          R << "load after store of same element in same statement";
934
1
          R << " (previous stores: " << Stores;
935
1
          R << ", loading: " << AccRel << ")";
936
1
          S->getFunction().getContext().diagnose(R);
937
1
          return false;
938
1
        }
939
3
940
2
        Loads = give(isl_union_map_union(Loads.take(), AccRel.take()));
941
2
942
2
        continue;
943
3
      }
944
25
945
22
      
if (22
!isa<StoreInst>(MA->getAccessInstruction())22
)
{1
946
1
        DEBUG(dbgs() << "WRITE that is not a StoreInst not supported\n");
947
1
        OptimizationRemarkMissed R(DEBUG_TYPE, "UnusualStore",
948
1
                                   MA->getAccessInstruction());
949
1
        R << "encountered write that is not a StoreInst: "
950
1
          << printIntruction(MA->getAccessInstruction());
951
1
        S->getFunction().getContext().diagnose(R);
952
1
        return false;
953
1
      }
954
22
955
22
      // In region statements the order is less clear, eg. the load and store
956
22
      // might be in a boxed loop.
957
21
      
if (21
Stmt->isRegionStmt() &&21
958
4
          
!isl_union_map_is_disjoint(Loads.keep(), AccRel.keep())4
)
{1
959
1
        OptimizationRemarkMissed R(DEBUG_TYPE, "StoreInSubregion",
960
1
                                   MA->getAccessInstruction());
961
1
        R << "store is in a non-affine subregion";
962
1
        S->getFunction().getContext().diagnose(R);
963
1
        return false;
964
1
      }
965
21
966
21
      // Do not allow more than one store to the same location.
967
20
      
if (20
!isl_union_map_is_disjoint(Stores.keep(), AccRel.keep())20
)
{1
968
1
        OptimizationRemarkMissed R(DEBUG_TYPE, "StoreAfterStore",
969
1
                                   MA->getAccessInstruction());
970
1
        R << "store after store of same element in same statement";
971
1
        R << " (previous stores: " << Stores;
972
1
        R << ", storing: " << AccRel << ")";
973
1
        S->getFunction().getContext().diagnose(R);
974
1
        return false;
975
1
      }
976
20
977
19
      Stores = give(isl_union_map_union(Stores.take(), AccRel.take()));
978
19
    }
979
88
980
84
    return true;
981
88
  }
982
983
1
  void addArrayReadAccess(MemoryAccess *MA) {
984
1
    assert(MA->isLatestArrayKind());
985
1
    assert(MA->isRead());
986
1
987
1
    // { DomainRead[] -> Element[] }
988
1
    auto AccRel = getAccessRelationFor(MA);
989
1
    AllReads = give(isl_union_map_add_map(AllReads.take(), AccRel.copy()));
990
1
  }
991
992
17
  void addArrayWriteAccess(MemoryAccess *MA) {
993
17
    assert(MA->isLatestArrayKind());
994
17
    assert(MA->isWrite());
995
17
996
17
    // { Domain[] -> Element[] }
997
17
    auto AccRel = getAccessRelationFor(MA);
998
17
999
17
    if (MA->isMustWrite())
1000
14
      AllMustWrites =
1001
14
          give(isl_union_map_add_map(AllMustWrites.take(), AccRel.copy()));
1002
17
1003
17
    if (MA->isMayWrite())
1004
3
      AllMayWrites =
1005
3
          give(isl_union_map_add_map(AllMayWrites.take(), AccRel.copy()));
1006
17
  }
1007
1008
protected:
1009
11
  isl::union_set makeEmptyUnionSet() const {
1010
11
    return give(isl_union_set_empty(ParamSpace.copy()));
1011
11
  }
1012
1013
227
  isl::union_map makeEmptyUnionMap() const {
1014
227
    return give(isl_union_map_empty(ParamSpace.copy()));
1015
227
  }
1016
1017
  /// Check whether @p S can be accurately analyzed by zones.
1018
19
  bool isCompatibleScop() {
1019
88
    for (auto &Stmt : *S) {
1020
88
      if (!isCompatibleStmt(&Stmt))
1021
4
        return false;
1022
88
    }
1023
15
    return true;
1024
19
  }
1025
1026
  /// Get the schedule for @p Stmt.
1027
  ///
1028
  /// The domain of the result is as narrow as possible.
1029
35
  isl::map getScatterFor(ScopStmt *Stmt) const {
1030
35
    auto ResultSpace = give(isl_space_map_from_domain_and_range(
1031
35
        Stmt->getDomainSpace(), ScatterSpace.copy()));
1032
35
    return give(isl_union_map_extract_map(Schedule.keep(), ResultSpace.take()));
1033
35
  }
1034
1035
  /// Get the schedule of @p MA's parent statement.
1036
35
  isl::map getScatterFor(MemoryAccess *MA) const {
1037
35
    return getScatterFor(MA->getStatement());
1038
35
  }
1039
1040
  /// Get the schedule for the statement instances of @p Domain.
1041
22
  isl::union_map getScatterFor(isl::union_set Domain) const {
1042
22
    return give(isl_union_map_intersect_domain(Schedule.copy(), Domain.take()));
1043
22
  }
1044
1045
  /// Get the schedule for the statement instances of @p Domain.
1046
11
  isl::map getScatterFor(isl::set Domain) const {
1047
11
    auto ResultSpace = give(isl_space_map_from_domain_and_range(
1048
11
        isl_set_get_space(Domain.keep()), ScatterSpace.copy()));
1049
11
    auto UDomain = give(isl_union_set_from_set(Domain.copy()));
1050
11
    auto UResult = getScatterFor(std::move(UDomain));
1051
11
    auto Result = singleton(std::move(UResult), std::move(ResultSpace));
1052
11
    assert(isl_set_is_equal(give(isl_map_domain(Result.copy())).keep(),
1053
11
                            Domain.keep()) == isl_bool_true);
1054
11
    return Result;
1055
11
  }
1056
1057
  /// Get the domain of @p Stmt.
1058
156
  isl::set getDomainFor(ScopStmt *Stmt) const {
1059
156
    return give(Stmt->getDomain());
1060
156
  }
1061
1062
  /// Get the domain @p MA's parent statement.
1063
137
  isl::set getDomainFor(MemoryAccess *MA) const {
1064
137
    return getDomainFor(MA->getStatement());
1065
137
  }
1066
1067
  /// Get the access relation of @p MA.
1068
  ///
1069
  /// The domain of the result is as narrow as possible.
1070
65
  isl::map getAccessRelationFor(MemoryAccess *MA) const {
1071
65
    auto Domain = getDomainFor(MA);
1072
65
    auto AccRel = give(MA->getLatestAccessRelation());
1073
65
    return give(isl_map_intersect_domain(AccRel.take(), Domain.take()));
1074
65
  }
1075
1076
  /// Get the reaching definition of a scalar defined in @p Stmt.
1077
  ///
1078
  /// Note that this does not depend on the llvm::Instruction, only on the
1079
  /// statement it is defined in. Therefore the same computation can be reused.
1080
  ///
1081
  /// @param Stmt The statement in which a scalar is defined.
1082
  ///
1083
  /// @return { Scatter[] -> DomainDef[] }
1084
11
  isl::map getScalarReachingDefinition(ScopStmt *Stmt) {
1085
11
    auto &Result = ScalarReachDefZone[Stmt];
1086
11
    if (Result)
1087
2
      return Result;
1088
11
1089
9
    auto Domain = getDomainFor(Stmt);
1090
9
    Result = computeScalarReachingDefinition(Schedule, Domain, false, true);
1091
9
    simplify(Result);
1092
9
1093
9
    assert(Result);
1094
9
    return Result;
1095
11
  }
1096
1097
  /// Compute the different zones.
1098
15
  void computeCommon() {
1099
15
    AllReads = makeEmptyUnionMap();
1100
15
    AllMayWrites = makeEmptyUnionMap();
1101
15
    AllMustWrites = makeEmptyUnionMap();
1102
15
1103
74
    for (auto &Stmt : *S) {
1104
143
      for (auto *MA : Stmt) {
1105
143
        if (!MA->isLatestArrayKind())
1106
125
          continue;
1107
143
1108
18
        
if (18
MA->isRead()18
)
1109
1
          addArrayReadAccess(MA);
1110
18
1111
18
        if (MA->isWrite())
1112
17
          addArrayWriteAccess(MA);
1113
18
      }
1114
74
    }
1115
15
1116
15
    // { DomainWrite[] -> Element[] }
1117
15
    auto AllWrites =
1118
15
        give(isl_union_map_union(AllMustWrites.copy(), AllMayWrites.copy()));
1119
15
  }
1120
1121
  /// Print the current state of all MemoryAccesses to @p.
1122
3
  void printAccesses(llvm::raw_ostream &OS, int Indent = 0) const {
1123
3
    OS.indent(Indent) << "After accesses {\n";
1124
16
    for (auto &Stmt : *S) {
1125
16
      OS.indent(Indent + 4) << Stmt.getBaseName() << "\n";
1126
16
      for (auto *MA : Stmt)
1127
37
        MA->print(OS);
1128
16
    }
1129
3
    OS.indent(Indent) << "}\n";
1130
3
  }
1131
1132
public:
1133
  /// Return the SCoP this object is analyzing.
1134
0
  Scop *getScop() const { return S; }
1135
};
1136
1137
/// Implementation of the DeLICM/DePRE transformation.
1138
class DeLICMImpl : public ZoneAlgorithm {
1139
private:
1140
  /// Knowledge before any transformation took place.
1141
  Knowledge OriginalZone;
1142
1143
  /// Current knowledge of the SCoP including all already applied
1144
  /// transformations.
1145
  Knowledge Zone;
1146
1147
  /// For getting the MemoryAccesses that write or read a given scalar.
1148
  ScalarDefUseChains DefUse;
1149
1150
  /// Number of StoreInsts something can be mapped to.
1151
  int NumberOfCompatibleTargets = 0;
1152
1153
  /// The number of StoreInsts to which at least one value or PHI has been
1154
  /// mapped to.
1155
  int NumberOfTargetsMapped = 0;
1156
1157
  /// The number of llvm::Value mapped to some array element.
1158
  int NumberOfMappedValueScalars = 0;
1159
1160
  /// The number of PHIs mapped to some array element.
1161
  int NumberOfMappedPHIScalars = 0;
1162
1163
  /// Determine whether two knowledges are conflicting with each other.
1164
  ///
1165
  /// @see Knowledge::isConflicting
1166
16
  bool isConflicting(const Knowledge &Proposed) {
1167
16
    raw_ostream *OS = nullptr;
1168
16
    DEBUG(OS = &llvm::dbgs());
1169
16
    return Knowledge::isConflicting(Zone, Proposed, OS, 4);
1170
16
  }
1171
1172
  /// Determine whether @p SAI is a scalar that can be mapped to an array
1173
  /// element.
1174
20
  bool isMappable(const ScopArrayInfo *SAI) {
1175
20
    assert(SAI);
1176
20
1177
20
    if (
SAI->isValueKind()20
)
{14
1178
14
      auto *MA = DefUse.getValueDef(SAI);
1179
14
      if (
!MA14
)
{1
1180
1
        DEBUG(dbgs()
1181
1
              << "    Reject because value is read-only within the scop\n");
1182
1
        return false;
1183
1
      }
1184
14
1185
14
      // Mapping if value is used after scop is not supported. The code
1186
14
      // generator would need to reload the scalar after the scop, but it
1187
14
      // does not have the information to where it is mapped to. Only the
1188
14
      // MemoryAccesses have that information, not the ScopArrayInfo.
1189
13
      auto Inst = MA->getAccessInstruction();
1190
23
      for (auto User : Inst->users()) {
1191
23
        if (!isa<Instruction>(User))
1192
0
          return false;
1193
23
        auto UserInst = cast<Instruction>(User);
1194
23
1195
23
        if (
!S->contains(UserInst)23
)
{1
1196
1
          DEBUG(dbgs() << "    Reject because value is escaping\n");
1197
1
          return false;
1198
1
        }
1199
23
      }
1200
13
1201
12
      return true;
1202
13
    }
1203
20
1204
6
    
if (6
SAI->isPHIKind()6
)
{6
1205
6
      auto *MA = DefUse.getPHIRead(SAI);
1206
6
      assert(MA);
1207
6
1208
6
      // Mapping of an incoming block from before the SCoP is not supported by
1209
6
      // the code generator.
1210
6
      auto PHI = cast<PHINode>(MA->getAccessInstruction());
1211
12
      for (auto Incoming : PHI->blocks()) {
1212
12
        if (
!S->contains(Incoming)12
)
{0
1213
0
          DEBUG(dbgs() << "    Reject because at least one incoming block is "
1214
0
                          "not in the scop region\n");
1215
0
          return false;
1216
0
        }
1217
12
      }
1218
6
1219
6
      return true;
1220
6
    }
1221
6
1222
0
    
DEBUG0
(dbgs() << " Reject ExitPHI or other non-value\n");0
1223
0
    return false;
1224
6
  }
1225
1226
  /// Compute the uses of a MemoryKind::Value and its lifetime (from its
1227
  /// definition to the last use).
1228
  ///
1229
  /// @param SAI The ScopArrayInfo representing the value's storage.
1230
  ///
1231
  /// @return { DomainDef[] -> DomainUse[] }, { DomainDef[] -> Zone[] }
1232
  ///         First element is the set of uses for each definition.
1233
  ///         The second is the lifetime of each definition.
1234
  std::tuple<isl::union_map, isl::map>
1235
11
  computeValueUses(const ScopArrayInfo *SAI) {
1236
11
    assert(SAI->isValueKind());
1237
11
1238
11
    // { DomainRead[] }
1239
11
    auto Reads = makeEmptyUnionSet();
1240
11
1241
11
    // Find all uses.
1242
11
    for (auto *MA : DefUse.getValueUses(SAI))
1243
18
      Reads =
1244
18
          give(isl_union_set_add_set(Reads.take(), getDomainFor(MA).take()));
1245
11
1246
11
    // { DomainRead[] -> Scatter[] }
1247
11
    auto ReadSchedule = getScatterFor(Reads);
1248
11
1249
11
    auto *DefMA = DefUse.getValueDef(SAI);
1250
11
    assert(DefMA);
1251
11
1252
11
    // { DomainDef[] }
1253
11
    auto Writes = getDomainFor(DefMA);
1254
11
1255
11
    // { DomainDef[] -> Scatter[] }
1256
11
    auto WriteScatter = getScatterFor(Writes);
1257
11
1258
11
    // { Scatter[] -> DomainDef[] }
1259
11
    auto ReachDef = getScalarReachingDefinition(DefMA->getStatement());
1260
11
1261
11
    // { [DomainDef[] -> Scatter[]] -> DomainUse[] }
1262
11
    auto Uses = give(
1263
11
        isl_union_map_apply_range(isl_union_map_from_map(isl_map_range_map(
1264
11
                                      isl_map_reverse(ReachDef.take()))),
1265
11
                                  isl_union_map_reverse(ReadSchedule.take())));
1266
11
1267
11
    // { DomainDef[] -> Scatter[] }
1268
11
    auto UseScatter =
1269
11
        singleton(give(isl_union_set_unwrap(isl_union_map_domain(Uses.copy()))),
1270
11
                  give(isl_space_map_from_domain_and_range(
1271
11
                      isl_set_get_space(Writes.keep()), ScatterSpace.copy())));
1272
11
1273
11
    // { DomainDef[] -> Zone[] }
1274
11
    auto Lifetime = betweenScatter(WriteScatter, UseScatter, false, true);
1275
11
1276
11
    // { DomainDef[] -> DomainRead[] }
1277
11
    auto DefUses = give(isl_union_map_domain_factor_domain(Uses.take()));
1278
11
1279
11
    return std::make_pair(DefUses, Lifetime);
1280
11
  }
1281
1282
  /// For each 'execution' of a PHINode, get the incoming block that was
1283
  /// executed before.
1284
  ///
1285
  /// For each PHI instance we can directly determine which was the incoming
1286
  /// block, and hence derive which value the PHI has.
1287
  ///
1288
  /// @param SAI The ScopArrayInfo representing the PHI's storage.
1289
  ///
1290
  /// @return { DomainPHIRead[] -> DomainPHIWrite[] }
1291
6
  isl::union_map computePerPHI(const ScopArrayInfo *SAI) {
1292
6
    assert(SAI->isPHIKind());
1293
6
1294
6
    // { DomainPHIWrite[] -> Scatter[] }
1295
6
    auto PHIWriteScatter = makeEmptyUnionMap();
1296
6
1297
6
    // Collect all incoming block timepoint.
1298
12
    for (auto *MA : DefUse.getPHIIncomings(SAI)) {
1299
12
      auto Scatter = getScatterFor(MA);
1300
12
      PHIWriteScatter =
1301
12
          give(isl_union_map_add_map(PHIWriteScatter.take(), Scatter.take()));
1302
12
    }
1303
6
1304
6
    // { DomainPHIRead[] -> Scatter[] }
1305
6
    auto PHIReadScatter = getScatterFor(DefUse.getPHIRead(SAI));
1306
6
1307
6
    // { DomainPHIRead[] -> Scatter[] }
1308
6
    auto BeforeRead = beforeScatter(PHIReadScatter, true);
1309
6
1310
6
    // { Scatter[] }
1311
6
    auto WriteTimes = singleton(
1312
6
        give(isl_union_map_range(PHIWriteScatter.copy())), ScatterSpace);
1313
6
1314
6
    // { DomainPHIRead[] -> Scatter[] }
1315
6
    auto PHIWriteTimes =
1316
6
        give(isl_map_intersect_range(BeforeRead.take(), WriteTimes.take()));
1317
6
    auto LastPerPHIWrites = give(isl_map_lexmax(PHIWriteTimes.take()));
1318
6
1319
6
    // { DomainPHIRead[] -> DomainPHIWrite[] }
1320
6
    auto Result = give(isl_union_map_apply_range(
1321
6
        isl_union_map_from_map(LastPerPHIWrites.take()),
1322
6
        isl_union_map_reverse(PHIWriteScatter.take())));
1323
6
    assert(isl_union_map_is_single_valued(Result.keep()) == isl_bool_true);
1324
6
    assert(isl_union_map_is_injective(Result.keep()) == isl_bool_true);
1325
6
    return Result;
1326
6
  }
1327
1328
  /// Try to map a MemoryKind::Value to a given array element.
1329
  ///
1330
  /// @param SAI       Representation of the scalar's memory to map.
1331
  /// @param TargetElt { Scatter[] -> Element[] }
1332
  ///                  Suggestion where to map a scalar to when at a timepoint.
1333
  ///
1334
  /// @return true if the scalar was successfully mapped.
1335
11
  bool tryMapValue(const ScopArrayInfo *SAI, isl::map TargetElt) {
1336
11
    assert(SAI->isValueKind());
1337
11
1338
11
    auto *DefMA = DefUse.getValueDef(SAI);
1339
11
    assert(DefMA->isValueKind());
1340
11
    assert(DefMA->isMustWrite());
1341
11
1342
11
    // Stop if the scalar has already been mapped.
1343
11
    if (!DefMA->getLatestScopArrayInfo()->isValueKind())
1344
0
      return false;
1345
11
1346
11
    // { DomainDef[] -> Scatter[] }
1347
11
    auto DefSched = getScatterFor(DefMA);
1348
11
1349
11
    // Where each write is mapped to, according to the suggestion.
1350
11
    // { DomainDef[] -> Element[] }
1351
11
    auto DefTarget = give(isl_map_apply_domain(
1352
11
        TargetElt.copy(), isl_map_reverse(DefSched.copy())));
1353
11
    simplify(DefTarget);
1354
11
    DEBUG(dbgs() << "    Def Mapping: " << DefTarget << '\n');
1355
11
1356
11
    auto OrigDomain = getDomainFor(DefMA);
1357
11
    auto MappedDomain = give(isl_map_domain(DefTarget.copy()));
1358
11
    if (
!isl_set_is_subset(OrigDomain.keep(), MappedDomain.keep())11
)
{0
1359
0
      DEBUG(dbgs()
1360
0
            << "    Reject because mapping does not encompass all instances\n");
1361
0
      return false;
1362
0
    }
1363
11
1364
11
    // { DomainDef[] -> Zone[] }
1365
11
    isl::map Lifetime;
1366
11
1367
11
    // { DomainDef[] -> DomainUse[] }
1368
11
    isl::union_map DefUses;
1369
11
1370
11
    std::tie(DefUses, Lifetime) = computeValueUses(SAI);
1371
11
    DEBUG(dbgs() << "    Lifetime: " << Lifetime << '\n');
1372
11
1373
11
    /// { [Element[] -> Zone[]] }
1374
11
    auto EltZone = give(
1375
11
        isl_map_wrap(isl_map_apply_domain(Lifetime.copy(), DefTarget.copy())));
1376
11
    simplify(EltZone);
1377
11
1378
11
    // { [Element[] -> Scatter[]] }
1379
11
    auto DefEltSched = give(isl_map_wrap(isl_map_reverse(
1380
11
        isl_map_apply_domain(DefTarget.copy(), DefSched.copy()))));
1381
11
    simplify(DefEltSched);
1382
11
1383
11
    Knowledge Proposed(EltZone, nullptr, DefEltSched);
1384
11
    if (isConflicting(Proposed))
1385
5
      return false;
1386
11
1387
11
    // { DomainUse[] -> Element[] }
1388
6
    auto UseTarget = give(
1389
6
        isl_union_map_apply_range(isl_union_map_reverse(DefUses.take()),
1390
6
                                  isl_union_map_from_map(DefTarget.copy())));
1391
6
1392
6
    mapValue(SAI, std::move(DefTarget), std::move(UseTarget),
1393
6
             std::move(Lifetime), std::move(Proposed));
1394
6
    return true;
1395
11
  }
1396
1397
  /// After a scalar has been mapped, update the global knowledge.
1398
9
  void applyLifetime(Knowledge Proposed) {
1399
9
    Zone.learnFrom(std::move(Proposed));
1400
9
  }
1401
1402
  /// Map a MemoryKind::Value scalar to an array element.
1403
  ///
1404
  /// Callers must have ensured that the mapping is valid and not conflicting.
1405
  ///
1406
  /// @param SAI       The ScopArrayInfo representing the scalar's memory to
1407
  ///                  map.
1408
  /// @param DefTarget { DomainDef[] -> Element[] }
1409
  ///                  The array element to map the scalar to.
1410
  /// @param UseTarget { DomainUse[] -> Element[] }
1411
  ///                  The array elements the uses are mapped to.
1412
  /// @param Lifetime  { DomainDef[] -> Zone[] }
1413
  ///                  The lifetime of each llvm::Value definition for
1414
  ///                  reporting.
1415
  /// @param Proposed  Mapping constraints for reporting.
1416
  void mapValue(const ScopArrayInfo *SAI, isl::map DefTarget,
1417
                isl::union_map UseTarget, isl::map Lifetime,
1418
6
                Knowledge Proposed) {
1419
6
    // Redirect the read accesses.
1420
8
    for (auto *MA : DefUse.getValueUses(SAI)) {
1421
8
      // { DomainUse[] }
1422
8
      auto Domain = getDomainFor(MA);
1423
8
1424
8
      // { DomainUse[] -> Element[] }
1425
8
      auto NewAccRel = give(isl_union_map_intersect_domain(
1426
8
          UseTarget.copy(), isl_union_set_from_set(Domain.take())));
1427
8
      simplify(NewAccRel);
1428
8
1429
8
      assert(isl_union_map_n_map(NewAccRel.keep()) == 1);
1430
8
      MA->setNewAccessRelation(isl_map_from_union_map(NewAccRel.take()));
1431
8
    }
1432
6
1433
6
    auto *WA = DefUse.getValueDef(SAI);
1434
6
    WA->setNewAccessRelation(DefTarget.copy());
1435
6
    applyLifetime(Proposed);
1436
6
1437
6
    MappedValueScalars++;
1438
6
    NumberOfMappedValueScalars += 1;
1439
6
  }
1440
1441
  /// Try to map a MemoryKind::PHI scalar to a given array element.
1442
  ///
1443
  /// @param SAI       Representation of the scalar's memory to map.
1444
  /// @param TargetElt { Scatter[] -> Element[] }
1445
  ///                  Suggestion where to map the scalar to when at a
1446
  ///                  timepoint.
1447
  ///
1448
  /// @return true if the PHI scalar has been mapped.
1449
6
  bool tryMapPHI(const ScopArrayInfo *SAI, isl::map TargetElt) {
1450
6
    auto *PHIRead = DefUse.getPHIRead(SAI);
1451
6
    assert(PHIRead->isPHIKind());
1452
6
    assert(PHIRead->isRead());
1453
6
1454
6
    // Skip if already been mapped.
1455
6
    if (!PHIRead->getLatestScopArrayInfo()->isPHIKind())
1456
0
      return false;
1457
6
1458
6
    // { DomainRead[] -> Scatter[] }
1459
6
    auto PHISched = getScatterFor(PHIRead);
1460
6
1461
6
    // { DomainRead[] -> Element[] }
1462
6
    auto PHITarget =
1463
6
        give(isl_map_apply_range(PHISched.copy(), TargetElt.copy()));
1464
6
    simplify(PHITarget);
1465
6
    DEBUG(dbgs() << "    Mapping: " << PHITarget << '\n');
1466
6
1467
6
    auto OrigDomain = getDomainFor(PHIRead);
1468
6
    auto MappedDomain = give(isl_map_domain(PHITarget.copy()));
1469
6
    if (
!isl_set_is_subset(OrigDomain.keep(), MappedDomain.keep())6
)
{0
1470
0
      DEBUG(dbgs()
1471
0
            << "    Reject because mapping does not encompass all instances\n");
1472
0
      return false;
1473
0
    }
1474
6
1475
6
    // { DomainRead[] -> DomainWrite[] }
1476
6
    auto PerPHIWrites = computePerPHI(SAI);
1477
6
1478
6
    // { DomainWrite[] -> Element[] }
1479
6
    auto WritesTarget = give(isl_union_map_reverse(isl_union_map_apply_domain(
1480
6
        PerPHIWrites.copy(), isl_union_map_from_map(PHITarget.copy()))));
1481
6
    simplify(WritesTarget);
1482
6
1483
6
    // { DomainWrite[] }
1484
6
    auto UniverseWritesDom = give(isl_union_set_empty(ParamSpace.copy()));
1485
6
1486
6
    for (auto *MA : DefUse.getPHIIncomings(SAI))
1487
12
      UniverseWritesDom = give(isl_union_set_add_set(UniverseWritesDom.take(),
1488
12
                                                     getDomainFor(MA).take()));
1489
6
1490
6
    auto RelevantWritesTarget = WritesTarget;
1491
6
    if (DelicmOverapproximateWrites)
1492
2
      WritesTarget = expandMapping(WritesTarget, UniverseWritesDom);
1493
6
1494
6
    auto ExpandedWritesDom = give(isl_union_map_domain(WritesTarget.copy()));
1495
6
    if (!isl_union_set_is_subset(UniverseWritesDom.keep(),
1496
1
                                 ExpandedWritesDom.keep())) {
1497
1
      DEBUG(dbgs() << "    Reject because did not find PHI write mapping for "
1498
1
                      "all instances\n");
1499
1
      if (DelicmOverapproximateWrites)
1500
1
        DEBUG(dbgs() << "      Relevant Mapping:    " << RelevantWritesTarget
1501
1
                     << '\n');
1502
1
      DEBUG(dbgs() << "      Deduced Mapping:     " << WritesTarget << '\n');
1503
1
      DEBUG(dbgs() << "      Missing instances:    "
1504
1
                   << give(isl_union_set_subtract(UniverseWritesDom.copy(),
1505
1
                                                  ExpandedWritesDom.copy()))
1506
1
                   << '\n');
1507
1
      return false;
1508
1
    }
1509
6
1510
6
    //  { DomainRead[] -> Scatter[] }
1511
5
    auto PerPHIWriteScatter = give(isl_map_from_union_map(
1512
5
        isl_union_map_apply_range(PerPHIWrites.copy(), Schedule.copy())));
1513
5
1514
5
    // { DomainRead[] -> Zone[] }
1515
5
    auto Lifetime = betweenScatter(PerPHIWriteScatter, PHISched, false, true);
1516
5
    simplify(Lifetime);
1517
5
    DEBUG(dbgs() << "    Lifetime: " << Lifetime << "\n");
1518
5
1519
5
    // { DomainWrite[] -> Zone[] }
1520
5
    auto WriteLifetime = give(isl_union_map_apply_domain(
1521
5
        isl_union_map_from_map(Lifetime.copy()), PerPHIWrites.copy()));
1522
5
1523
5
    // { DomainWrite[] -> [Element[] -> Scatter[]] }
1524
5
    auto WrittenTranslator =
1525
5
        give(isl_union_map_range_product(WritesTarget.copy(), Schedule.copy()));
1526
5
1527
5
    // { [Element[] -> Scatter[]] }
1528
5
    auto Written = give(isl_union_map_range(WrittenTranslator.copy()));
1529
5
    simplify(Written);
1530
5
1531
5
    // { DomainWrite[] -> [Element[] -> Zone[]] }
1532
5
    auto LifetimeTranslator = give(
1533
5
        isl_union_map_range_product(WritesTarget.copy(), WriteLifetime.take()));
1534
5
1535
5
    // { [Element[] -> Zone[] }
1536
5
    auto Occupied = give(isl_union_map_range(LifetimeTranslator.copy()));
1537
5
    simplify(Occupied);
1538
5
1539
5
    Knowledge Proposed(Occupied, nullptr, Written);
1540
5
    if (isConflicting(Proposed))
1541
2
      return false;
1542
5
1543
3
    mapPHI(SAI, std::move(PHITarget), std::move(WritesTarget),
1544
3
           std::move(Lifetime), std::move(Proposed));
1545
3
    return true;
1546
5
  }
1547
1548
  /// Map a MemoryKind::PHI scalar to an array element.
1549
  ///
1550
  /// Callers must have ensured that the mapping is valid and not conflicting
1551
  /// with the common knowledge.
1552
  ///
1553
  /// @param SAI         The ScopArrayInfo representing the scalar's memory to
1554
  ///                    map.
1555
  /// @param ReadTarget  { DomainRead[] -> Element[] }
1556
  ///                    The array element to map the scalar to.
1557
  /// @param WriteTarget { DomainWrite[] -> Element[] }
1558
  ///                    New access target for each PHI incoming write.
1559
  /// @param Lifetime    { DomainRead[] -> Zone[] }
1560
  ///                    The lifetime of each PHI for reporting.
1561
  /// @param Proposed    Mapping constraints for reporting.
1562
  void mapPHI(const ScopArrayInfo *SAI, isl::map ReadTarget,
1563
              isl::union_map WriteTarget, isl::map Lifetime,
1564
3
              Knowledge Proposed) {
1565
3
    // Redirect the PHI incoming writes.
1566
6
    for (auto *MA : DefUse.getPHIIncomings(SAI)) {
1567
6
      // { DomainWrite[] }
1568
6
      auto Domain = getDomainFor(MA);
1569
6
1570
6
      // { DomainWrite[] -> Element[] }
1571
6
      auto NewAccRel = give(isl_union_map_intersect_domain(
1572
6
          WriteTarget.copy(), isl_union_set_from_set(Domain.take())));
1573
6
      simplify(NewAccRel);
1574
6
1575
6
      assert(isl_union_map_n_map(NewAccRel.keep()) == 1);
1576
6
      MA->setNewAccessRelation(isl_map_from_union_map(NewAccRel.take()));
1577
6
    }
1578
3
1579
3
    // Redirect the PHI read.
1580
3
    auto *PHIRead = DefUse.getPHIRead(SAI);
1581
3
    PHIRead->setNewAccessRelation(ReadTarget.copy());
1582
3
    applyLifetime(Proposed);
1583
3
1584
3
    MappedPHIScalars++;
1585
3
    NumberOfMappedPHIScalars++;
1586
3
  }
1587
1588
  /// Search and map scalars to memory overwritten by @p TargetStoreMA.
1589
  ///
1590
  /// Start trying to map scalars that are used in the same statement as the
1591
  /// store. For every successful mapping, try to also map scalars of the
1592
  /// statements where those are written. Repeat, until no more mapping
1593
  /// opportunity is found.
1594
  ///
1595
  /// There is currently no preference in which order scalars are tried.
1596
  /// Ideally, we would direct it towards a load instruction of the same array
1597
  /// element.
1598
10
  bool collapseScalarsToStore(MemoryAccess *TargetStoreMA) {
1599
10
    assert(TargetStoreMA->isLatestArrayKind());
1600
10
    assert(TargetStoreMA->isMustWrite());
1601
10
1602
10
    auto TargetStmt = TargetStoreMA->getStatement();
1603
10
1604
10
    // { DomTarget[] }
1605
10
    auto TargetDom = getDomainFor(TargetStmt);
1606
10
1607
10
    // { DomTarget[] -> Element[] }
1608
10
    auto TargetAccRel = getAccessRelationFor(TargetStoreMA);
1609
10
1610
10
    // { Zone[] -> DomTarget[] }
1611
10
    // For each point in time, find the next target store instance.
1612
10
    auto Target =
1613
10
        computeScalarReachingOverwrite(Schedule, TargetDom, false, true);
1614
10
1615
10
    // { Zone[] -> Element[] }
1616
10
    // Use the target store's write location as a suggestion to map scalars to.
1617
10
    auto EltTarget =
1618
10
        give(isl_map_apply_range(Target.take(), TargetAccRel.take()));
1619
10
    simplify(EltTarget);
1620
10
    DEBUG(dbgs() << "    Target mapping is " << EltTarget << '\n');
1621
10
1622
10
    // Stack of elements not yet processed.
1623
10
    SmallVector<MemoryAccess *, 16> Worklist;
1624
10
1625
10
    // Set of scalars already tested.
1626
10
    SmallPtrSet<const ScopArrayInfo *, 16> Closed;
1627
10
1628
10
    // Lambda to add all scalar reads to the work list.
1629
14
    auto ProcessAllIncoming = [&](ScopStmt *Stmt) {
1630
34
      for (auto *MA : *Stmt) {
1631
34
        if (!MA->isLatestScalarKind())
1632
16
          continue;
1633
18
        
if (18
!MA->isRead()18
)
1634
5
          continue;
1635
18
1636
13
        Worklist.push_back(MA);
1637
13
      }
1638
14
    };
1639
10
1640
10
    // Add initial scalar. Either the value written by the store, or all inputs
1641
10
    // of its statement.
1642
10
    auto WrittenVal = TargetStoreMA->getAccessValue();
1643
10
    if (auto InputAcc = getInputAccessOf(WrittenVal, TargetStmt))
1644
8
      Worklist.push_back(InputAcc);
1645
10
    else
1646
2
      ProcessAllIncoming(TargetStmt);
1647
10
1648
10
    auto AnyMapped = false;
1649
10
    auto &DL = S->getRegion().getEntry()->getModule()->getDataLayout();
1650
10
    auto StoreSize =
1651
10
        DL.getTypeAllocSize(TargetStoreMA->getAccessValue()->getType());
1652
10
1653
31
    while (
!Worklist.empty()31
)
{21
1654
21
      auto *MA = Worklist.pop_back_val();
1655
21
1656
21
      auto *SAI = MA->getScopArrayInfo();
1657
21
      if (Closed.count(SAI))
1658
1
        continue;
1659
20
      Closed.insert(SAI);
1660
20
      DEBUG(dbgs() << "\n    Trying to map " << MA << " (SAI: " << SAI
1661
20
                   << ")\n");
1662
20
1663
20
      // Skip non-mappable scalars.
1664
20
      if (!isMappable(SAI))
1665
2
        continue;
1666
20
1667
18
      auto MASize = DL.getTypeAllocSize(MA->getAccessValue()->getType());
1668
18
      if (
MASize > StoreSize18
)
{1
1669
1
        DEBUG(dbgs() << "    Reject because storage size is insufficient\n");
1670
1
        continue;
1671
1
      }
1672
18
1673
18
      // Try to map MemoryKind::Value scalars.
1674
17
      
if (17
SAI->isValueKind()17
)
{11
1675
11
        if (!tryMapValue(SAI, EltTarget))
1676
5
          continue;
1677
11
1678
6
        auto *DefAcc = DefUse.getValueDef(SAI);
1679
6
        ProcessAllIncoming(DefAcc->getStatement());
1680
6
1681
6
        AnyMapped = true;
1682
6
        continue;
1683
11
      }
1684
17
1685
17
      // Try to map MemoryKind::PHI scalars.
1686
6
      
if (6
SAI->isPHIKind()6
)
{6
1687
6
        if (!tryMapPHI(SAI, EltTarget))
1688
3
          continue;
1689
6
        // Add inputs of all incoming statements to the worklist.
1690
3
        for (auto *PHIWrite : DefUse.getPHIIncomings(SAI))
1691
6
          ProcessAllIncoming(PHIWrite->getStatement());
1692
3
1693
3
        AnyMapped = true;
1694
3
        continue;
1695
6
      }
1696
6
    }
1697
10
1698
10
    if (
AnyMapped10
)
{3
1699
3
      TargetsMapped++;
1700
3
      NumberOfTargetsMapped++;
1701
3
    }
1702
10
    return AnyMapped;
1703
10
  }
1704
1705
  /// Compute when an array element is unused.
1706
  ///
1707
  /// @return { [Element[] -> Zone[]] }
1708
15
  isl::union_set computeLifetime() const {
1709
15
    // { Element[] -> Zone[] }
1710
15
    auto ArrayUnused = computeArrayUnused(Schedule, AllMustWrites, AllReads,
1711
15
                                          false, false, true);
1712
15
1713
15
    auto Result = give(isl_union_map_wrap(ArrayUnused.copy()));
1714
15
1715
15
    simplify(Result);
1716
15
    return Result;
1717
15
  }
1718
1719
  /// Determine when an array element is written to.
1720
  ///
1721
  /// @return { [Element[] -> Scatter[]] }
1722
15
  isl::union_set computeWritten() const {
1723
15
    // { WriteDomain[] -> Element[] }
1724
15
    auto AllWrites =
1725
15
        give(isl_union_map_union(AllMustWrites.copy(), AllMayWrites.copy()));
1726
15
1727
15
    // { Scatter[] -> Element[] }
1728
15
    auto WriteTimepoints =
1729
15
        give(isl_union_map_apply_domain(AllWrites.copy(), Schedule.copy()));
1730
15
1731
15
    auto Result =
1732
15
        give(isl_union_map_wrap(isl_union_map_reverse(WriteTimepoints.copy())));
1733
15
1734
15
    simplify(Result);
1735
15
    return Result;
1736
15
  }
1737
1738
  /// Determine whether an access touches at most one element.
1739
  ///
1740
  /// The accessed element could be a scalar or accessing an array with constant
1741
  /// subscript, such that all instances access only that element.
1742
  ///
1743
  /// @param MA The access to test.
1744
  ///
1745
  /// @return True, if zero or one elements are accessed; False if at least two
1746
  ///         different elements are accessed.
1747
12
  bool isScalarAccess(MemoryAccess *MA) {
1748
12
    auto Map = getAccessRelationFor(MA);
1749
12
    auto Set = give(isl_map_range(Map.take()));
1750
12
    return isl_set_is_singleton(Set.keep()) == isl_bool_true;
1751
12
  }
1752
1753
  /// Print mapping statistics to @p OS.
1754
14
  void printStatistics(llvm::raw_ostream &OS, int Indent = 0) const {
1755
14
    OS.indent(Indent) << "Statistics {\n";
1756
14
    OS.indent(Indent + 4) << "Compatible overwrites: "
1757
14
                          << NumberOfCompatibleTargets << "\n";
1758
14
    OS.indent(Indent + 4) << "Overwrites mapped to:  " << NumberOfTargetsMapped
1759
14
                          << '\n';
1760
14
    OS.indent(Indent + 4) << "Value scalars mapped:  "
1761
14
                          << NumberOfMappedValueScalars << '\n';
1762
14
    OS.indent(Indent + 4) << "PHI scalars mapped:    "
1763
14
                          << NumberOfMappedPHIScalars << '\n';
1764
14
    OS.indent(Indent) << "}\n";
1765
14
  }
1766
1767
  /// Return whether at least one transformation been applied.
1768
14
  bool isModified() const { return NumberOfTargetsMapped > 0; }
1769
1770
public:
1771
19
  DeLICMImpl(Scop *S) : ZoneAlgorithm(S) {}
1772
1773
  /// Calculate the lifetime (definition to last use) of every array element.
1774
  ///
1775
  /// @return True if the computed lifetimes (#Zone) is usable.
1776
19
  bool computeZone() {
1777
19
    // Check that nothing strange occurs.
1778
19
    if (
!isCompatibleScop()19
)
{4
1779
4
      DeLICMIncompatible++;
1780
4
      return false;
1781
4
    }
1782
19
1783
15
    DefUse.compute(S);
1784
15
    isl::union_set EltUnused, EltWritten;
1785
15
1786
15
    {
1787
15
      IslMaxOperationsGuard MaxOpGuard(IslCtx.get(), DelicmMaxOps);
1788
15
1789
15
      computeCommon();
1790
15
1791
15
      EltUnused = computeLifetime();
1792
15
      EltWritten = computeWritten();
1793
15
    }
1794
15
    DeLICMAnalyzed++;
1795
15
1796
15
    if (
!EltUnused || 15
!EltWritten14
)
{1
1797
1
      assert(isl_ctx_last_error(IslCtx.get()) == isl_error_quota &&
1798
1
             "The only reason that these things have not been computed should "
1799
1
             "be if the max-operations limit hit");
1800
1
      DeLICMOutOfQuota++;
1801
1
      DEBUG(dbgs() << "DeLICM analysis exceeded max_operations\n");
1802
1
      DebugLoc Begin, End;
1803
1
      getDebugLocations(getBBPairForRegion(&S->getRegion()), Begin, End);
1804
1
      OptimizationRemarkAnalysis R(DEBUG_TYPE, "OutOfQuota", Begin,
1805
1
                                   S->getEntry());
1806
1
      R << "maximal number of operations exceeded during zone analysis";
1807
1
      S->getFunction().getContext().diagnose(R);
1808
1
      return false;
1809
1
    }
1810
15
1811
14
    Zone = OriginalZone = Knowledge(nullptr, EltUnused, EltWritten);
1812
14
    DEBUG(dbgs() << "Computed Zone:\n"; OriginalZone.print(dbgs(), 4));
1813
14
1814
14
    assert(Zone.isUsable() && OriginalZone.isUsable());
1815
14
    return true;
1816
15
  }
1817
1818
  /// Try to map as many scalars to unused array elements as possible.
1819
  ///
1820
  /// Multiple scalars might be mappable to intersecting unused array element
1821
  /// zones, but we can only chose one. This is a greedy algorithm, therefore
1822
  /// the first processed element claims it.
1823
14
  void greedyCollapse() {
1824
14
    bool Modified = false;
1825
14
1826
69
    for (auto &Stmt : *S) {
1827
134
      for (auto *MA : Stmt) {
1828
134
        if (!MA->isLatestArrayKind())
1829
116
          continue;
1830
18
        
if (18
!MA->isWrite()18
)
1831
2
          continue;
1832
18
1833
16
        
if (16
MA->isMayWrite()16
)
{3
1834
3
          DEBUG(dbgs() << "Access " << MA
1835
3
                       << " pruned because it is a MAY_WRITE\n");
1836
3
          OptimizationRemarkMissed R(DEBUG_TYPE, "TargetMayWrite",
1837
3
                                     MA->getAccessInstruction());
1838
3
          R << "Skipped possible mapping target because it is not an "
1839
3
               "unconditional overwrite";
1840
3
          S->getFunction().getContext().diagnose(R);
1841
3
          continue;
1842
3
        }
1843
16
1844
13
        
if (13
Stmt.getNumIterators() == 013
)
{1
1845
1
          DEBUG(dbgs() << "Access " << MA
1846
1
                       << " pruned because it is not in a loop\n");
1847
1
          OptimizationRemarkMissed R(DEBUG_TYPE, "WriteNotInLoop",
1848
1
                                     MA->getAccessInstruction());
1849
1
          R << "skipped possible mapping target because it is not in a loop";
1850
1
          S->getFunction().getContext().diagnose(R);
1851
1
          continue;
1852
1
        }
1853
13
1854
12
        
if (12
isScalarAccess(MA)12
)
{2
1855
2
          DEBUG(dbgs() << "Access " << MA
1856
2
                       << " pruned because it writes only a single element\n");
1857
2
          OptimizationRemarkMissed R(DEBUG_TYPE, "ScalarWrite",
1858
2
                                     MA->getAccessInstruction());
1859
2
          R << "skipped possible mapping target because the memory location "
1860
2
               "written to does not depend on its outer loop";
1861
2
          S->getFunction().getContext().diagnose(R);
1862
2
          continue;
1863
2
        }
1864
12
1865
10
        NumberOfCompatibleTargets++;
1866
10
        DEBUG(dbgs() << "Analyzing target access " << MA << "\n");
1867
10
        if (collapseScalarsToStore(MA))
1868
3
          Modified = true;
1869
10
      }
1870
69
    }
1871
14
1872
14
    if (Modified)
1873
3
      DeLICMScopsModified++;
1874
14
  }
1875
1876
  /// Dump the internal information about a performed DeLICM to @p OS.
1877
19
  void print(llvm::raw_ostream &OS, int Indent = 0) {
1878
19
    if (
!Zone.isUsable()19
)
{5
1879
5
      OS.indent(Indent) << "Zone not computed\n";
1880
5
      return;
1881
5
    }
1882
19
1883
14
    printStatistics(OS, Indent);
1884
14
    if (
!isModified()14
)
{11
1885
11
      OS.indent(Indent) << "No modification has been made\n";
1886
11
      return;
1887
11
    }
1888
3
    printAccesses(OS, Indent);
1889
3
  }
1890
};
1891
1892
class DeLICM : public ScopPass {
1893
private:
1894
  DeLICM(const DeLICM &) = delete;
1895
  const DeLICM &operator=(const DeLICM &) = delete;
1896
1897
  /// The pass implementation, also holding per-scop data.
1898
  std::unique_ptr<DeLICMImpl> Impl;
1899
1900
19
  void collapseToUnused(Scop &S) {
1901
19
    Impl = make_unique<DeLICMImpl>(&S);
1902
19
1903
19
    if (
!Impl->computeZone()19
)
{5
1904
5
      DEBUG(dbgs() << "Abort because cannot reliably compute lifetimes\n");
1905
5
      return;
1906
5
    }
1907
19
1908
14
    
DEBUG14
(dbgs() << "Collapsing scalars to unused array elements...\n");14
1909
14
    Impl->greedyCollapse();
1910
14
1911
14
    DEBUG(dbgs() << "\nFinal Scop:\n");
1912
14
    DEBUG(S.print(dbgs()));
1913
14
  }
1914
1915
public:
1916
  static char ID;
1917
19
  explicit DeLICM() : ScopPass(ID) {}
1918
1919
19
  virtual void getAnalysisUsage(AnalysisUsage &AU) const override {
1920
19
    AU.addRequiredTransitive<ScopInfoRegionPass>();
1921
19
    AU.setPreservesAll();
1922
19
  }
1923
1924
19
  virtual bool runOnScop(Scop &S) override {
1925
19
    // Free resources for previous scop's computation, if not yet done.
1926
19
    releaseMemory();
1927
19
1928
19
    collapseToUnused(S);
1929
19
1930
19
    return false;
1931
19
  }
1932
1933
19
  virtual void printScop(raw_ostream &OS, Scop &S) const override {
1934
19
    if (!Impl)
1935
0
      return;
1936
19
    assert(Impl->getScop() == &S);
1937
19
1938
19
    OS << "DeLICM result:\n";
1939
19
    Impl->print(OS);
1940
19
  }
1941
1942
99
  virtual void releaseMemory() override { Impl.reset(); }
1943
};
1944
1945
char DeLICM::ID;
1946
} // anonymous namespace
1947
1948
0
Pass *polly::createDeLICMPass() { return new DeLICM(); }
1949
1950
39.7k
INITIALIZE_PASS_BEGIN39.7k
(DeLICM, "polly-delicm", "Polly - DeLICM/DePRE", false,39.7k
1951
39.7k
                      false)
1952
39.7k
INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass)
1953
39.7k
INITIALIZE_PASS_END(DeLICM, "polly-delicm", "Polly - DeLICM/DePRE", false,
1954
                    false)
1955
1956
bool polly::isConflicting(
1957
    isl::union_set ExistingOccupied, isl::union_set ExistingUnused,
1958
    isl::union_map ExistingKnown, isl::union_map ExistingWrites,
1959
    isl::union_set ProposedOccupied, isl::union_set ProposedUnused,
1960
    isl::union_map ProposedKnown, isl::union_map ProposedWrites,
1961
232
    llvm::raw_ostream *OS, unsigned Indent) {
1962
232
  Knowledge Existing(std::move(ExistingOccupied), std::move(ExistingUnused),
1963
232
                     std::move(ExistingKnown), std::move(ExistingWrites));
1964
232
  Knowledge Proposed(std::move(ProposedOccupied), std::move(ProposedUnused),
1965
232
                     std::move(ProposedKnown), std::move(ProposedWrites));
1966
232
1967
232
  return Knowledge::isConflicting(Existing, Proposed, OS, Indent);
1968
232
}