Coverage Report

Created: 2017-06-28 17:40

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