Coverage Report

Created: 2017-10-03 07:32

/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
//===----------------------------------------------------------------------===//
17
18
#include "polly/DeLICM.h"
19
#include "polly/Options.h"
20
#include "polly/ScopInfo.h"
21
#include "polly/ScopPass.h"
22
#include "polly/Support/ISLOStream.h"
23
#include "polly/Support/ISLTools.h"
24
#include "polly/ZoneAlgo.h"
25
#include "llvm/ADT/Statistic.h"
26
19
#define DEBUG_TYPE "polly-delicm"
27
28
using namespace polly;
29
using namespace llvm;
30
31
namespace {
32
33
cl::opt<int>
34
    DelicmMaxOps("polly-delicm-max-ops",
35
                 cl::desc("Maximum number of isl operations to invest for "
36
                          "lifetime analysis; 0=no limit"),
37
                 cl::init(1000000), cl::cat(PollyCategory));
38
39
cl::opt<bool> DelicmOverapproximateWrites(
40
    "polly-delicm-overapproximate-writes",
41
    cl::desc(
42
        "Do more PHI writes than necessary in order to avoid partial accesses"),
43
    cl::init(false), cl::Hidden, cl::cat(PollyCategory));
44
45
cl::opt<bool> DelicmPartialWrites("polly-delicm-partial-writes",
46
                                  cl::desc("Allow partial writes"),
47
                                  cl::init(true), cl::Hidden,
48
                                  cl::cat(PollyCategory));
49
50
cl::opt<bool>
51
    DelicmComputeKnown("polly-delicm-compute-known",
52
                       cl::desc("Compute known content of array elements"),
53
                       cl::init(true), cl::Hidden, cl::cat(PollyCategory));
54
55
STATISTIC(DeLICMAnalyzed, "Number of successfully analyzed SCoPs");
56
STATISTIC(DeLICMOutOfQuota,
57
          "Analyses aborted because max_operations was reached");
58
STATISTIC(MappedValueScalars, "Number of mapped Value scalars");
59
STATISTIC(MappedPHIScalars, "Number of mapped PHI scalars");
60
STATISTIC(TargetsMapped, "Number of stores used for at least one mapping");
61
STATISTIC(DeLICMScopsModified, "Number of SCoPs optimized");
62
63
STATISTIC(NumValueWrites, "Number of scalar value writes after DeLICM");
64
STATISTIC(NumValueWritesInLoops,
65
          "Number of scalar value writes nested in affine loops after DeLICM");
66
STATISTIC(NumPHIWrites, "Number of scalar phi writes after DeLICM");
67
STATISTIC(NumPHIWritesInLoops,
68
          "Number of scalar phi writes nested in affine loops after DeLICM");
69
STATISTIC(NumSingletonWrites, "Number of singleton writes after DeLICM");
70
STATISTIC(NumSingletonWritesInLoops,
71
          "Number of singleton writes nested in affine loops after DeLICM");
72
73
isl::union_map computeReachingOverwrite(isl::union_map Schedule,
74
                                        isl::union_map Writes,
75
                                        bool InclPrevWrite,
76
30
                                        bool InclOverwrite) {
77
30
  return computeReachingWrite(Schedule, Writes, true, InclPrevWrite,
78
30
                              InclOverwrite);
79
30
}
80
81
/// Compute the next overwrite for a scalar.
82
///
83
/// @param Schedule      { DomainWrite[] -> Scatter[] }
84
///                      Schedule of (at least) all writes. Instances not in @p
85
///                      Writes are ignored.
86
/// @param Writes        { DomainWrite[] }
87
///                      The element instances that write to the scalar.
88
/// @param InclPrevWrite Whether to extend the timepoints to include
89
///                      the timepoint where the previous write happens.
90
/// @param InclOverwrite Whether the reaching overwrite includes the timepoint
91
///                      of the overwrite itself.
92
///
93
/// @return { Scatter[] -> DomainDef[] }
94
isl::union_map computeScalarReachingOverwrite(isl::union_map Schedule,
95
                                              isl::union_set Writes,
96
                                              bool InclPrevWrite,
97
30
                                              bool InclOverwrite) {
98
30
99
30
  // { DomainWrite[] }
100
30
  auto WritesMap = give(isl_union_map_from_domain(Writes.take()));
101
30
102
30
  // { [Element[] -> Scatter[]] -> DomainWrite[] }
103
30
  auto Result = computeReachingOverwrite(
104
30
      std::move(Schedule), std::move(WritesMap), InclPrevWrite, InclOverwrite);
105
30
106
30
  return give(isl_union_map_domain_factor_range(Result.take()));
107
30
}
108
109
/// Overload of computeScalarReachingOverwrite, with only one writing statement.
110
/// Consequently, the result consists of only one map space.
111
///
112
/// @param Schedule      { DomainWrite[] -> Scatter[] }
113
/// @param Writes        { DomainWrite[] }
114
/// @param InclPrevWrite Include the previous write to result.
115
/// @param InclOverwrite Include the overwrite to the result.
116
///
117
/// @return { Scatter[] -> DomainWrite[] }
118
isl::map computeScalarReachingOverwrite(isl::union_map Schedule,
119
                                        isl::set Writes, bool InclPrevWrite,
120
30
                                        bool InclOverwrite) {
121
30
  isl::space ScatterSpace = getScatterSpace(Schedule);
122
30
  isl::space DomSpace = Writes.get_space();
123
30
124
30
  isl::union_map ReachOverwrite = computeScalarReachingOverwrite(
125
30
      Schedule, isl::union_set(Writes), InclPrevWrite, InclOverwrite);
126
30
127
30
  isl::space ResultSpace = ScatterSpace.map_from_domain_and_range(DomSpace);
128
30
  return singleton(std::move(ReachOverwrite), ResultSpace);
129
30
}
130
131
/// Try to find a 'natural' extension of a mapped to elements outside its
132
/// domain.
133
///
134
/// @param Relevant The map with mapping that may not be modified.
135
/// @param Universe The domain to which @p Relevant needs to be extended.
136
///
137
/// @return A map with that associates the domain elements of @p Relevant to the
138
///         same elements and in addition the elements of @p Universe to some
139
///         undefined elements. The function prefers to return simple maps.
140
11
isl::union_map expandMapping(isl::union_map Relevant, isl::union_set Universe) {
141
11
  Relevant = Relevant.coalesce();
142
11
  isl::union_set RelevantDomain = Relevant.domain();
143
11
  isl::union_map Simplified = Relevant.gist_domain(RelevantDomain);
144
11
  Simplified = Simplified.coalesce();
145
11
  return Simplified.intersect_domain(Universe);
146
11
}
147
148
/// Represent the knowledge of the contents of any array elements in any zone or
149
/// the knowledge we would add when mapping a scalar to an array element.
150
///
151
/// Every array element at every zone unit has one of two states:
152
///
153
/// - Unused: Not occupied by any value so a transformation can change it to
154
///   other values.
155
///
156
/// - Occupied: The element contains a value that is still needed.
157
///
158
/// The union of Unused and Unknown zones forms the universe, the set of all
159
/// elements at every timepoint. The universe can easily be derived from the
160
/// array elements that are accessed someway. Arrays that are never accessed
161
/// also never play a role in any computation and can hence be ignored. With a
162
/// given universe, only one of the sets needs to stored implicitly. Computing
163
/// the complement is also an expensive operation, hence this class has been
164
/// designed that only one of sets is needed while the other is assumed to be
165
/// implicit. It can still be given, but is mostly ignored.
166
///
167
/// There are two use cases for the Knowledge class:
168
///
169
/// 1) To represent the knowledge of the current state of ScopInfo. The unused
170
///    state means that an element is currently unused: there is no read of it
171
///    before the next overwrite. Also called 'Existing'.
172
///
173
/// 2) To represent the requirements for mapping a scalar to array elements. The
174
///    unused state means that there is no change/requirement. Also called
175
///    'Proposed'.
176
///
177
/// In addition to these states at unit zones, Knowledge needs to know when
178
/// values are written. This is because written values may have no lifetime (one
179
/// reason is that the value is never read). Such writes would therefore never
180
/// conflict, but overwrite values that might still be required. Another source
181
/// of problems are multiple writes to the same element at the same timepoint,
182
/// because their order is undefined.
183
class Knowledge {
184
private:
185
  /// { [Element[] -> Zone[]] }
186
  /// Set of array elements and when they are alive.
187
  /// Can contain a nullptr; in this case the set is implicitly defined as the
188
  /// complement of #Unused.
189
  ///
190
  /// The set of alive array elements is represented as zone, as the set of live
191
  /// values can differ depending on how the elements are interpreted.
192
  /// Assuming a value X is written at timestep [0] and read at timestep [1]
193
  /// without being used at any later point, then the value is alive in the
194
  /// interval ]0,1[. This interval cannot be represented by an integer set, as
195
  /// it does not contain any integer point. Zones allow us to represent this
196
  /// interval and can be converted to sets of timepoints when needed (e.g., in
197
  /// isConflicting when comparing to the write sets).
198
  /// @see convertZoneToTimepoints and this file's comment for more details.
199
  isl::union_set Occupied;
200
201
  /// { [Element[] -> Zone[]] }
202
  /// Set of array elements when they are not alive, i.e. their memory can be
203
  /// used for other purposed. Can contain a nullptr; in this case the set is
204
  /// implicitly defined as the complement of #Occupied.
205
  isl::union_set Unused;
206
207
  /// { [Element[] -> Zone[]] -> ValInst[] }
208
  /// Maps to the known content for each array element at any interval.
209
  ///
210
  /// Any element/interval can map to multiple known elements. This is due to
211
  /// multiple llvm::Value referring to the same content. Examples are
212
  ///
213
  /// - A value stored and loaded again. The LoadInst represents the same value
214
  /// as the StoreInst's value operand.
215
  ///
216
  /// - A PHINode is equal to any one of the incoming values. In case of
217
  /// LCSSA-form, it is always equal to its single incoming value.
218
  ///
219
  /// Two Knowledges are considered not conflicting if at least one of the known
220
  /// values match. Not known values are not stored as an unnamed tuple (as
221
  /// #Written does), but maps to nothing.
222
  ///
223
  ///  Known values are usually just defined for #Occupied elements. Knowing
224
  ///  #Unused contents has no advantage as it can be overwritten.
225
  isl::union_map Known;
226
227
  /// { [Element[] -> Scatter[]] -> ValInst[] }
228
  /// The write actions currently in the scop or that would be added when
229
  /// mapping a scalar. Maps to the value that is written.
230
  ///
231
  /// Written values that cannot be identified are represented by an unknown
232
  /// ValInst[] (an unnamed tuple of 0 dimension). It conflicts with itself.
233
  isl::union_map Written;
234
235
  /// Check whether this Knowledge object is well-formed.
236
613
  void checkConsistency() const {
237
#ifndef NDEBUG
238
    // Default-initialized object
239
    if (!Occupied && !Unused && !Known && !Written)
240
      return;
241
242
    assert(Occupied || Unused);
243
    assert(Known);
244
    assert(Written);
245
246
    // If not all fields are defined, we cannot derived the universe.
247
    if (!Occupied || !Unused)
248
      return;
249
250
    assert(isl_union_set_is_disjoint(Occupied.keep(), Unused.keep()) ==
251
           isl_bool_true);
252
    auto Universe = give(isl_union_set_union(Occupied.copy(), Unused.copy()));
253
254
    assert(!Known.domain().is_subset(Universe).is_false());
255
    assert(!Written.domain().is_subset(Universe).is_false());
256
#endif
257
  }
258
259
public:
260
  /// Initialize a nullptr-Knowledge. This is only provided for convenience; do
261
  /// not use such an object.
262
72
  Knowledge() {}
263
264
  /// Create a new object with the given members.
265
  Knowledge(isl::union_set Occupied, isl::union_set Unused,
266
            isl::union_map Known, isl::union_map Written)
267
      : Occupied(std::move(Occupied)), Unused(std::move(Unused)),
268
559
        Known(std::move(Known)), Written(std::move(Written)) {
269
559
    checkConsistency();
270
559
  }
271
272
  /// Return whether this object was not default-constructed.
273
35
  bool isUsable() const 
{ return (Occupied || 35
Unused35
) &&
Known34
&&
Written34
; }
274
275
  /// Print the content of this object to @p OS.
276
0
  void print(llvm::raw_ostream &OS, unsigned Indent = 0) const {
277
0
    if (isUsable()) {
278
0
      if (Occupied)
279
0
        OS.indent(Indent) << "Occupied: " << Occupied << "\n";
280
0
      else
281
0
        OS.indent(Indent) << "Occupied: <Everything else not in Unused>\n";
282
0
      if (Unused)
283
0
        OS.indent(Indent) << "Unused:   " << Unused << "\n";
284
0
      else
285
0
        OS.indent(Indent) << "Unused:   <Everything else not in Occupied>\n";
286
0
      OS.indent(Indent) << "Known:    " << Known << "\n";
287
0
      OS.indent(Indent) << "Written : " << Written << '\n';
288
0
    } else {
289
0
      OS.indent(Indent) << "Invalid knowledge\n";
290
0
    }
291
0
  }
292
293
  /// Combine two knowledges, this and @p That.
294
54
  void learnFrom(Knowledge That) {
295
54
    assert(!isConflicting(*this, That));
296
54
    assert(Unused && That.Occupied);
297
54
    assert(
298
54
        !That.Unused &&
299
54
        "This function is only prepared to learn occupied elements from That");
300
54
    assert(!Occupied && "This function does not implement "
301
54
                        "`this->Occupied = "
302
54
                        "give(isl_union_set_union(this->Occupied.take(), "
303
54
                        "That.Occupied.copy()));`");
304
54
305
54
    Unused = give(isl_union_set_subtract(Unused.take(), That.Occupied.copy()));
306
54
    Known = give(isl_union_map_union(Known.take(), That.Known.copy()));
307
54
    Written = give(isl_union_map_union(Written.take(), That.Written.take()));
308
54
309
54
    checkConsistency();
310
54
  }
311
312
  /// Determine whether two Knowledges conflict with each other.
313
  ///
314
  /// In theory @p Existing and @p Proposed are symmetric, but the
315
  /// implementation is constrained by the implicit interpretation. That is, @p
316
  /// Existing must have #Unused defined (use case 1) and @p Proposed must have
317
  /// #Occupied defined (use case 1).
318
  ///
319
  /// A conflict is defined as non-preserved semantics when they are merged. For
320
  /// instance, when for the same array and zone they assume different
321
  /// llvm::Values.
322
  ///
323
  /// @param Existing One of the knowledges with #Unused defined.
324
  /// @param Proposed One of the knowledges with #Occupied defined.
325
  /// @param OS       Dump the conflict reason to this output stream; use
326
  ///                 nullptr to not output anything.
327
  /// @param Indent   Indention for the conflict reason.
328
  ///
329
  /// @return True, iff the two knowledges are conflicting.
330
  static bool isConflicting(const Knowledge &Existing,
331
                            const Knowledge &Proposed,
332
                            llvm::raw_ostream *OS = nullptr,
333
292
                            unsigned Indent = 0) {
334
292
    assert(Existing.Unused);
335
292
    assert(Proposed.Occupied);
336
292
337
#ifndef NDEBUG
338
    if (Existing.Occupied && Proposed.Unused) {
339
      auto ExistingUniverse = give(isl_union_set_union(Existing.Occupied.copy(),
340
                                                       Existing.Unused.copy()));
341
      auto ProposedUniverse = give(isl_union_set_union(Proposed.Occupied.copy(),
342
                                                       Proposed.Unused.copy()));
343
      assert(isl_union_set_is_equal(ExistingUniverse.keep(),
344
                                    ProposedUniverse.keep()) == isl_bool_true &&
345
             "Both inputs' Knowledges must be over the same universe");
346
    }
347
#endif
348
349
292
    // Do the Existing and Proposed lifetimes conflict?
350
292
    //
351
292
    // Lifetimes are described as the cross-product of array elements and zone
352
292
    // intervals in which they are alive (the space { [Element[] -> Zone[]] }).
353
292
    // In the following we call this "element/lifetime interval".
354
292
    //
355
292
    // In order to not conflict, one of the following conditions must apply for
356
292
    // each element/lifetime interval:
357
292
    //
358
292
    // 1. If occupied in one of the knowledges, it is unused in the other.
359
292
    //
360
292
    //   - or -
361
292
    //
362
292
    // 2. Both contain the same value.
363
292
    //
364
292
    // Instead of partitioning the element/lifetime intervals into a part that
365
292
    // both Knowledges occupy (which requires an expensive subtraction) and for
366
292
    // these to check whether they are known to be the same value, we check only
367
292
    // the second condition and ensure that it also applies when then first
368
292
    // condition is true. This is done by adding a wildcard value to
369
292
    // Proposed.Known and Existing.Unused such that they match as a common known
370
292
    // value. We use the "unknown ValInst" for this purpose. Every
371
292
    // Existing.Unused may match with an unknown Proposed.Occupied because these
372
292
    // never are in conflict with each other.
373
292
    auto ProposedOccupiedAnyVal = makeUnknownForDomain(Proposed.Occupied);
374
292
    auto ProposedValues = Proposed.Known.unite(ProposedOccupiedAnyVal);
375
292
376
292
    auto ExistingUnusedAnyVal = makeUnknownForDomain(Existing.Unused);
377
292
    auto ExistingValues = Existing.Known.unite(ExistingUnusedAnyVal);
378
292
379
292
    auto MatchingVals = ExistingValues.intersect(ProposedValues);
380
292
    auto Matches = MatchingVals.domain();
381
292
382
292
    // Any Proposed.Occupied must either have a match between the known values
383
292
    // of Existing and Occupied, or be in Existing.Unused. In the latter case,
384
292
    // the previously added "AnyVal" will match each other.
385
292
    if (
!Proposed.Occupied.is_subset(Matches)292
) {
386
44
      if (
OS44
) {
387
0
        auto Conflicting = Proposed.Occupied.subtract(Matches);
388
0
        auto ExistingConflictingKnown =
389
0
            Existing.Known.intersect_domain(Conflicting);
390
0
        auto ProposedConflictingKnown =
391
0
            Proposed.Known.intersect_domain(Conflicting);
392
0
393
0
        OS->indent(Indent) << "Proposed lifetime conflicting with Existing's\n";
394
0
        OS->indent(Indent) << "Conflicting occupied: " << Conflicting << "\n";
395
0
        if (!ExistingConflictingKnown.is_empty())
396
0
          OS->indent(Indent)
397
0
              << "Existing Known:       " << ExistingConflictingKnown << "\n";
398
0
        if (!ProposedConflictingKnown.is_empty())
399
0
          OS->indent(Indent)
400
0
              << "Proposed Known:       " << ProposedConflictingKnown << "\n";
401
0
      }
402
44
      return true;
403
44
    }
404
248
405
248
    // Do the writes in Existing conflict with occupied values in Proposed?
406
248
    //
407
248
    // In order to not conflict, it must either write to unused lifetime or
408
248
    // write the same value. To check, we remove the writes that write into
409
248
    // Proposed.Unused (they never conflict) and then see whether the written
410
248
    // value is already in Proposed.Known. If there are multiple known values
411
248
    // and a written value is known under different names, it is enough when one
412
248
    // of the written values (assuming that they are the same value under
413
248
    // different names, e.g. a PHINode and one of the incoming values) matches
414
248
    // one of the known names.
415
248
    //
416
248
    // We convert here the set of lifetimes to actual timepoints. A lifetime is
417
248
    // in conflict with a set of write timepoints, if either a live timepoint is
418
248
    // clearly within the lifetime or if a write happens at the beginning of the
419
248
    // lifetime (where it would conflict with the value that actually writes the
420
248
    // value alive). There is no conflict at the end of a lifetime, as the alive
421
248
    // value will always be read, before it is overwritten again. The last
422
248
    // property holds in Polly for all scalar values and we expect all users of
423
248
    // Knowledge to check this property also for accesses to MemoryKind::Array.
424
248
    auto ProposedFixedDefs =
425
248
        convertZoneToTimepoints(Proposed.Occupied, true, false);
426
248
    auto ProposedFixedKnown =
427
248
        convertZoneToTimepoints(Proposed.Known, isl::dim::in, true, false);
428
248
429
248
    auto ExistingConflictingWrites =
430
248
        Existing.Written.intersect_domain(ProposedFixedDefs);
431
248
    auto ExistingConflictingWritesDomain = ExistingConflictingWrites.domain();
432
248
433
248
    auto CommonWrittenVal =
434
248
        ProposedFixedKnown.intersect(ExistingConflictingWrites);
435
248
    auto CommonWrittenValDomain = CommonWrittenVal.domain();
436
248
437
248
    if (
!ExistingConflictingWritesDomain.is_subset(CommonWrittenValDomain)248
) {
438
26
      if (
OS26
) {
439
0
        auto ExistingConflictingWritten =
440
0
            ExistingConflictingWrites.subtract_domain(CommonWrittenValDomain);
441
0
        auto ProposedConflictingKnown = ProposedFixedKnown.subtract_domain(
442
0
            ExistingConflictingWritten.domain());
443
0
444
0
        OS->indent(Indent)
445
0
            << "Proposed a lifetime where there is an Existing write into it\n";
446
0
        OS->indent(Indent) << "Existing conflicting writes: "
447
0
                           << ExistingConflictingWritten << "\n";
448
0
        if (!ProposedConflictingKnown.is_empty())
449
0
          OS->indent(Indent)
450
0
              << "Proposed conflicting known:  " << ProposedConflictingKnown
451
0
              << "\n";
452
0
      }
453
26
      return true;
454
26
    }
455
222
456
222
    // Do the writes in Proposed conflict with occupied values in Existing?
457
222
    auto ExistingAvailableDefs =
458
222
        convertZoneToTimepoints(Existing.Unused, true, false);
459
222
    auto ExistingKnownDefs =
460
222
        convertZoneToTimepoints(Existing.Known, isl::dim::in, true, false);
461
222
462
222
    auto ProposedWrittenDomain = Proposed.Written.domain();
463
222
    auto KnownIdentical = ExistingKnownDefs.intersect(Proposed.Written);
464
222
    auto IdenticalOrUnused =
465
222
        ExistingAvailableDefs.unite(KnownIdentical.domain());
466
222
    if (
!ProposedWrittenDomain.is_subset(IdenticalOrUnused)222
) {
467
24
      if (
OS24
) {
468
0
        auto Conflicting = ProposedWrittenDomain.subtract(IdenticalOrUnused);
469
0
        auto ExistingConflictingKnown =
470
0
            ExistingKnownDefs.intersect_domain(Conflicting);
471
0
        auto ProposedConflictingWritten =
472
0
            Proposed.Written.intersect_domain(Conflicting);
473
0
474
0
        OS->indent(Indent) << "Proposed writes into range used by Existing\n";
475
0
        OS->indent(Indent) << "Proposed conflicting writes: "
476
0
                           << ProposedConflictingWritten << "\n";
477
0
        if (!ExistingConflictingKnown.is_empty())
478
0
          OS->indent(Indent)
479
0
              << "Existing conflicting known: " << ExistingConflictingKnown
480
0
              << "\n";
481
0
      }
482
24
      return true;
483
24
    }
484
198
485
198
    // Does Proposed write at the same time as Existing already does (order of
486
198
    // writes is undefined)? Writing the same value is permitted.
487
198
    auto ExistingWrittenDomain =
488
198
        isl::manage(isl_union_map_domain(Existing.Written.copy()));
489
198
    auto BothWritten =
490
198
        Existing.Written.domain().intersect(Proposed.Written.domain());
491
198
    auto ExistingKnownWritten = filterKnownValInst(Existing.Written);
492
198
    auto ProposedKnownWritten = filterKnownValInst(Proposed.Written);
493
198
    auto CommonWritten =
494
198
        ExistingKnownWritten.intersect(ProposedKnownWritten).domain();
495
198
496
198
    if (
!BothWritten.is_subset(CommonWritten)198
) {
497
24
      if (
OS24
) {
498
0
        auto Conflicting = BothWritten.subtract(CommonWritten);
499
0
        auto ExistingConflictingWritten =
500
0
            Existing.Written.intersect_domain(Conflicting);
501
0
        auto ProposedConflictingWritten =
502
0
            Proposed.Written.intersect_domain(Conflicting);
503
0
504
0
        OS->indent(Indent) << "Proposed writes at the same time as an already "
505
0
                              "Existing write\n";
506
0
        OS->indent(Indent) << "Conflicting writes: " << Conflicting << "\n";
507
0
        if (!ExistingConflictingWritten.is_empty())
508
0
          OS->indent(Indent)
509
0
              << "Exiting write:      " << ExistingConflictingWritten << "\n";
510
0
        if (!ProposedConflictingWritten.is_empty())
511
0
          OS->indent(Indent)
512
0
              << "Proposed write:     " << ProposedConflictingWritten << "\n";
513
0
      }
514
24
      return true;
515
24
    }
516
174
517
174
    return false;
518
174
  }
519
};
520
521
/// Implementation of the DeLICM/DePRE transformation.
522
class DeLICMImpl : public ZoneAlgorithm {
523
private:
524
  /// Knowledge before any transformation took place.
525
  Knowledge OriginalZone;
526
527
  /// Current knowledge of the SCoP including all already applied
528
  /// transformations.
529
  Knowledge Zone;
530
531
  /// Number of StoreInsts something can be mapped to.
532
  int NumberOfCompatibleTargets = 0;
533
534
  /// The number of StoreInsts to which at least one value or PHI has been
535
  /// mapped to.
536
  int NumberOfTargetsMapped = 0;
537
538
  /// The number of llvm::Value mapped to some array element.
539
  int NumberOfMappedValueScalars = 0;
540
541
  /// The number of PHIs mapped to some array element.
542
  int NumberOfMappedPHIScalars = 0;
543
544
  /// Determine whether two knowledges are conflicting with each other.
545
  ///
546
  /// @see Knowledge::isConflicting
547
60
  bool isConflicting(const Knowledge &Proposed) {
548
60
    raw_ostream *OS = nullptr;
549
60
    DEBUG(OS = &llvm::dbgs());
550
60
    return Knowledge::isConflicting(Zone, Proposed, OS, 4);
551
60
  }
552
553
  /// Determine whether @p SAI is a scalar that can be mapped to an array
554
  /// element.
555
67
  bool isMappable(const ScopArrayInfo *SAI) {
556
67
    assert(SAI);
557
67
558
67
    if (
SAI->isValueKind()67
) {
559
43
      auto *MA = S->getValueDef(SAI);
560
43
      if (
!MA43
) {
561
2
        DEBUG(dbgs()
562
2
              << "    Reject because value is read-only within the scop\n");
563
2
        return false;
564
2
      }
565
41
566
41
      // Mapping if value is used after scop is not supported. The code
567
41
      // generator would need to reload the scalar after the scop, but it
568
41
      // does not have the information to where it is mapped to. Only the
569
41
      // MemoryAccesses have that information, not the ScopArrayInfo.
570
41
      auto Inst = MA->getAccessInstruction();
571
69
      for (auto User : Inst->users()) {
572
69
        if (!isa<Instruction>(User))
573
0
          return false;
574
69
        auto UserInst = cast<Instruction>(User);
575
69
576
69
        if (
!S->contains(UserInst)69
) {
577
1
          DEBUG(dbgs() << "    Reject because value is escaping\n");
578
1
          return false;
579
1
        }
580
40
      }
581
40
582
40
      return true;
583
40
    }
584
24
585
24
    
if (24
SAI->isPHIKind()24
) {
586
24
      auto *MA = S->getPHIRead(SAI);
587
24
      assert(MA);
588
24
589
24
      // Mapping of an incoming block from before the SCoP is not supported by
590
24
      // the code generator.
591
24
      auto PHI = cast<PHINode>(MA->getAccessInstruction());
592
48
      for (auto Incoming : PHI->blocks()) {
593
48
        if (
!S->contains(Incoming)48
) {
594
0
          DEBUG(dbgs() << "    Reject because at least one incoming block is "
595
0
                          "not in the scop region\n");
596
0
          return false;
597
0
        }
598
24
      }
599
24
600
24
      return true;
601
24
    }
602
0
603
0
    
DEBUG0
(dbgs() << " Reject ExitPHI or other non-value\n");
604
0
    return false;
605
0
  }
606
607
  /// Compute the uses of a MemoryKind::Value and its lifetime (from its
608
  /// definition to the last use).
609
  ///
610
  /// @param SAI The ScopArrayInfo representing the value's storage.
611
  ///
612
  /// @return { DomainDef[] -> DomainUse[] }, { DomainDef[] -> Zone[] }
613
  ///         First element is the set of uses for each definition.
614
  ///         The second is the lifetime of each definition.
615
  std::tuple<isl::union_map, isl::map>
616
37
  computeValueUses(const ScopArrayInfo *SAI) {
617
37
    assert(SAI->isValueKind());
618
37
619
37
    // { DomainRead[] }
620
37
    auto Reads = makeEmptyUnionSet();
621
37
622
37
    // Find all uses.
623
37
    for (auto *MA : S->getValueUses(SAI))
624
54
      Reads =
625
54
          give(isl_union_set_add_set(Reads.take(), getDomainFor(MA).take()));
626
37
627
37
    // { DomainRead[] -> Scatter[] }
628
37
    auto ReadSchedule = getScatterFor(Reads);
629
37
630
37
    auto *DefMA = S->getValueDef(SAI);
631
37
    assert(DefMA);
632
37
633
37
    // { DomainDef[] }
634
37
    auto Writes = getDomainFor(DefMA);
635
37
636
37
    // { DomainDef[] -> Scatter[] }
637
37
    auto WriteScatter = getScatterFor(Writes);
638
37
639
37
    // { Scatter[] -> DomainDef[] }
640
37
    auto ReachDef = getScalarReachingDefinition(DefMA->getStatement());
641
37
642
37
    // { [DomainDef[] -> Scatter[]] -> DomainUse[] }
643
37
    auto Uses = give(
644
37
        isl_union_map_apply_range(isl_union_map_from_map(isl_map_range_map(
645
37
                                      isl_map_reverse(ReachDef.take()))),
646
37
                                  isl_union_map_reverse(ReadSchedule.take())));
647
37
648
37
    // { DomainDef[] -> Scatter[] }
649
37
    auto UseScatter =
650
37
        singleton(give(isl_union_set_unwrap(isl_union_map_domain(Uses.copy()))),
651
37
                  give(isl_space_map_from_domain_and_range(
652
37
                      isl_set_get_space(Writes.keep()), ScatterSpace.copy())));
653
37
654
37
    // { DomainDef[] -> Zone[] }
655
37
    auto Lifetime = betweenScatter(WriteScatter, UseScatter, false, true);
656
37
657
37
    // { DomainDef[] -> DomainRead[] }
658
37
    auto DefUses = give(isl_union_map_domain_factor_domain(Uses.take()));
659
37
660
37
    return std::make_pair(DefUses, Lifetime);
661
37
  }
662
663
  /// For each 'execution' of a PHINode, get the incoming block that was
664
  /// executed before.
665
  ///
666
  /// For each PHI instance we can directly determine which was the incoming
667
  /// block, and hence derive which value the PHI has.
668
  ///
669
  /// The returned relation generally is injective, meaning that every PHI write
670
  /// has at most one (or zero, if the incoming block's branch does not jump to
671
  /// the PHI's block) PHI Read that reads it. However, due to the SCoP's
672
  /// parameter context it is possible a statement instance that would overwrite
673
  /// the PHI scalar is not in the statement's domain and thus a PHI write
674
  /// appear to be used twice.  This is a static property, at runtime the
675
  /// runtime condition should avoid that a configuration is executed. Although
676
  /// incorrect, it should not have any effect in DeLICM.  If it passes the
677
  /// conflict check, there are multiple locations, one for each PHI Read it
678
  /// matches, it had to write to.  MemoryAccess::getAddressFunction() will
679
  /// select only one of them.  That is, statically, not all necessary value are
680
  /// written, but the runtime check guards it from ever being executed.
681
  ///
682
  /// @param SAI The ScopArrayInfo representing the PHI's storage.
683
  ///
684
  /// @return { DomainPHIRead[] -> DomainPHIWrite[] }
685
24
  isl::union_map computePerPHI(const ScopArrayInfo *SAI) {
686
24
    assert(SAI->isPHIKind());
687
24
688
24
    // { DomainPHIWrite[] -> Scatter[] }
689
24
    auto PHIWriteScatter = makeEmptyUnionMap();
690
24
691
24
    // Collect all incoming block timepoint.
692
48
    for (auto *MA : S->getPHIIncomings(SAI)) {
693
48
      auto Scatter = getScatterFor(MA);
694
48
      PHIWriteScatter =
695
48
          give(isl_union_map_add_map(PHIWriteScatter.take(), Scatter.take()));
696
48
    }
697
24
698
24
    // { DomainPHIRead[] -> Scatter[] }
699
24
    auto PHIReadScatter = getScatterFor(S->getPHIRead(SAI));
700
24
701
24
    // { DomainPHIRead[] -> Scatter[] }
702
24
    auto BeforeRead = beforeScatter(PHIReadScatter, true);
703
24
704
24
    // { Scatter[] }
705
24
    auto WriteTimes = singleton(
706
24
        give(isl_union_map_range(PHIWriteScatter.copy())), ScatterSpace);
707
24
708
24
    // { DomainPHIRead[] -> Scatter[] }
709
24
    auto PHIWriteTimes =
710
24
        give(isl_map_intersect_range(BeforeRead.take(), WriteTimes.take()));
711
24
    auto LastPerPHIWrites = give(isl_map_lexmax(PHIWriteTimes.take()));
712
24
713
24
    // { DomainPHIRead[] -> DomainPHIWrite[] }
714
24
    auto Result = give(isl_union_map_apply_range(
715
24
        isl_union_map_from_map(LastPerPHIWrites.take()),
716
24
        isl_union_map_reverse(PHIWriteScatter.take())));
717
24
    assert(isl_union_map_is_single_valued(Result.keep()) == isl_bool_true);
718
24
    return Result;
719
24
  }
720
721
  /// Try to map a MemoryKind::Value to a given array element.
722
  ///
723
  /// @param SAI       Representation of the scalar's memory to map.
724
  /// @param TargetElt { Scatter[] -> Element[] }
725
  ///                  Suggestion where to map a scalar to when at a timepoint.
726
  ///
727
  /// @return true if the scalar was successfully mapped.
728
39
  bool tryMapValue(const ScopArrayInfo *SAI, isl::map TargetElt) {
729
39
    assert(SAI->isValueKind());
730
39
731
39
    auto *DefMA = S->getValueDef(SAI);
732
39
    assert(DefMA->isValueKind());
733
39
    assert(DefMA->isMustWrite());
734
39
    auto *V = DefMA->getAccessValue();
735
39
    auto *DefInst = DefMA->getAccessInstruction();
736
39
737
39
    // Stop if the scalar has already been mapped.
738
39
    if (!DefMA->getLatestScopArrayInfo()->isValueKind())
739
1
      return false;
740
38
741
38
    // { DomainDef[] -> Scatter[] }
742
38
    auto DefSched = getScatterFor(DefMA);
743
38
744
38
    // Where each write is mapped to, according to the suggestion.
745
38
    // { DomainDef[] -> Element[] }
746
38
    auto DefTarget = give(isl_map_apply_domain(
747
38
        TargetElt.copy(), isl_map_reverse(DefSched.copy())));
748
38
    simplify(DefTarget);
749
38
    DEBUG(dbgs() << "    Def Mapping: " << DefTarget << '\n');
750
38
751
38
    auto OrigDomain = getDomainFor(DefMA);
752
38
    auto MappedDomain = give(isl_map_domain(DefTarget.copy()));
753
38
    if (
!isl_set_is_subset(OrigDomain.keep(), MappedDomain.keep())38
) {
754
1
      DEBUG(dbgs()
755
1
            << "    Reject because mapping does not encompass all instances\n");
756
1
      return false;
757
1
    }
758
37
759
37
    // { DomainDef[] -> Zone[] }
760
37
    isl::map Lifetime;
761
37
762
37
    // { DomainDef[] -> DomainUse[] }
763
37
    isl::union_map DefUses;
764
37
765
37
    std::tie(DefUses, Lifetime) = computeValueUses(SAI);
766
37
    DEBUG(dbgs() << "    Lifetime: " << Lifetime << '\n');
767
37
768
37
    /// { [Element[] -> Zone[]] }
769
37
    auto EltZone = give(
770
37
        isl_map_wrap(isl_map_apply_domain(Lifetime.copy(), DefTarget.copy())));
771
37
    simplify(EltZone);
772
37
773
37
    // When known knowledge is disabled, just return the unknown value. It will
774
37
    // either get filtered out or conflict with itself.
775
37
    // { DomainDef[] -> ValInst[] }
776
37
    isl::map ValInst;
777
37
    if (DelicmComputeKnown)
778
37
      ValInst = makeValInst(V, DefMA->getStatement(),
779
37
                            LI->getLoopFor(DefInst->getParent()));
780
37
    else
781
0
      ValInst = makeUnknownForDomain(DefMA->getStatement());
782
37
783
37
    // { DomainDef[] -> [Element[] -> Zone[]] }
784
37
    auto EltKnownTranslator =
785
37
        give(isl_map_range_product(DefTarget.copy(), Lifetime.copy()));
786
37
787
37
    // { [Element[] -> Zone[]] -> ValInst[] }
788
37
    auto EltKnown =
789
37
        give(isl_map_apply_domain(ValInst.copy(), EltKnownTranslator.take()));
790
37
    simplify(EltKnown);
791
37
792
37
    // { DomainDef[] -> [Element[] -> Scatter[]] }
793
37
    auto WrittenTranslator =
794
37
        give(isl_map_range_product(DefTarget.copy(), DefSched.take()));
795
37
796
37
    // { [Element[] -> Scatter[]] -> ValInst[] }
797
37
    auto DefEltSched =
798
37
        give(isl_map_apply_domain(ValInst.copy(), WrittenTranslator.take()));
799
37
    simplify(DefEltSched);
800
37
801
37
    Knowledge Proposed(EltZone, nullptr, filterKnownValInst(EltKnown),
802
37
                       DefEltSched);
803
37
    if (isConflicting(Proposed))
804
4
      return false;
805
33
806
33
    // { DomainUse[] -> Element[] }
807
33
    auto UseTarget = give(
808
33
        isl_union_map_apply_range(isl_union_map_reverse(DefUses.take()),
809
33
                                  isl_union_map_from_map(DefTarget.copy())));
810
33
811
33
    mapValue(SAI, std::move(DefTarget), std::move(UseTarget),
812
33
             std::move(Lifetime), std::move(Proposed));
813
33
    return true;
814
33
  }
815
816
  /// After a scalar has been mapped, update the global knowledge.
817
54
  void applyLifetime(Knowledge Proposed) {
818
54
    Zone.learnFrom(std::move(Proposed));
819
54
  }
820
821
  /// Map a MemoryKind::Value scalar to an array element.
822
  ///
823
  /// Callers must have ensured that the mapping is valid and not conflicting.
824
  ///
825
  /// @param SAI       The ScopArrayInfo representing the scalar's memory to
826
  ///                  map.
827
  /// @param DefTarget { DomainDef[] -> Element[] }
828
  ///                  The array element to map the scalar to.
829
  /// @param UseTarget { DomainUse[] -> Element[] }
830
  ///                  The array elements the uses are mapped to.
831
  /// @param Lifetime  { DomainDef[] -> Zone[] }
832
  ///                  The lifetime of each llvm::Value definition for
833
  ///                  reporting.
834
  /// @param Proposed  Mapping constraints for reporting.
835
  void mapValue(const ScopArrayInfo *SAI, isl::map DefTarget,
836
                isl::union_map UseTarget, isl::map Lifetime,
837
33
                Knowledge Proposed) {
838
33
    // Redirect the read accesses.
839
45
    for (auto *MA : S->getValueUses(SAI)) {
840
45
      // { DomainUse[] }
841
45
      auto Domain = getDomainFor(MA);
842
45
843
45
      // { DomainUse[] -> Element[] }
844
45
      auto NewAccRel = give(isl_union_map_intersect_domain(
845
45
          UseTarget.copy(), isl_union_set_from_set(Domain.take())));
846
45
      simplify(NewAccRel);
847
45
848
45
      assert(isl_union_map_n_map(NewAccRel.keep()) == 1);
849
45
      MA->setNewAccessRelation(isl::map::from_union_map(NewAccRel));
850
45
    }
851
33
852
33
    auto *WA = S->getValueDef(SAI);
853
33
    WA->setNewAccessRelation(DefTarget);
854
33
    applyLifetime(Proposed);
855
33
856
33
    MappedValueScalars++;
857
33
    NumberOfMappedValueScalars += 1;
858
33
  }
859
860
  isl::map makeValInst(Value *Val, ScopStmt *UserStmt, Loop *Scope,
861
83
                       bool IsCertain = true) {
862
83
    // When known knowledge is disabled, just return the unknown value. It will
863
83
    // either get filtered out or conflict with itself.
864
83
    if (!DelicmComputeKnown)
865
0
      return makeUnknownForDomain(UserStmt);
866
83
    return ZoneAlgorithm::makeValInst(Val, UserStmt, Scope, IsCertain);
867
83
  }
868
869
  /// Express the incoming values of a PHI for each incoming statement in an
870
  /// isl::union_map.
871
  ///
872
  /// @param SAI The PHI scalar represented by a ScopArrayInfo.
873
  ///
874
  /// @return { PHIWriteDomain[] -> ValInst[] }
875
23
  isl::union_map determinePHIWrittenValues(const ScopArrayInfo *SAI) {
876
23
    auto Result = makeEmptyUnionMap();
877
23
878
23
    // Collect the incoming values.
879
46
    for (auto *MA : S->getPHIIncomings(SAI)) {
880
46
      // { DomainWrite[] -> ValInst[] }
881
46
      isl::union_map ValInst;
882
46
      auto *WriteStmt = MA->getStatement();
883
46
884
46
      auto Incoming = MA->getIncoming();
885
46
      assert(!Incoming.empty());
886
46
      if (
Incoming.size() == 146
) {
887
46
        ValInst = makeValInst(Incoming[0].second, WriteStmt,
888
46
                              LI->getLoopFor(Incoming[0].first));
889
46
      } else {
890
0
        // If the PHI is in a subregion's exit node it can have multiple
891
0
        // incoming values (+ maybe another incoming edge from an unrelated
892
0
        // block). We cannot directly represent it as a single llvm::Value.
893
0
        // We currently model it as unknown value, but modeling as the PHIInst
894
0
        // itself could be OK, too.
895
0
        ValInst = makeUnknownForDomain(WriteStmt);
896
0
      }
897
46
898
46
      Result = give(isl_union_map_union(Result.take(), ValInst.take()));
899
46
    }
900
23
901
23
    assert(isl_union_map_is_single_valued(Result.keep()) == isl_bool_true &&
902
23
           "Cannot have multiple incoming values for same incoming statement");
903
23
    return Result;
904
23
  }
905
906
  /// Try to map a MemoryKind::PHI scalar to a given array element.
907
  ///
908
  /// @param SAI       Representation of the scalar's memory to map.
909
  /// @param TargetElt { Scatter[] -> Element[] }
910
  ///                  Suggestion where to map the scalar to when at a
911
  ///                  timepoint.
912
  ///
913
  /// @return true if the PHI scalar has been mapped.
914
24
  bool tryMapPHI(const ScopArrayInfo *SAI, isl::map TargetElt) {
915
24
    auto *PHIRead = S->getPHIRead(SAI);
916
24
    assert(PHIRead->isPHIKind());
917
24
    assert(PHIRead->isRead());
918
24
919
24
    // Skip if already been mapped.
920
24
    if (!PHIRead->getLatestScopArrayInfo()->isPHIKind())
921
0
      return false;
922
24
923
24
    // { DomainRead[] -> Scatter[] }
924
24
    auto PHISched = getScatterFor(PHIRead);
925
24
926
24
    // { DomainRead[] -> Element[] }
927
24
    auto PHITarget =
928
24
        give(isl_map_apply_range(PHISched.copy(), TargetElt.copy()));
929
24
    simplify(PHITarget);
930
24
    DEBUG(dbgs() << "    Mapping: " << PHITarget << '\n');
931
24
932
24
    auto OrigDomain = getDomainFor(PHIRead);
933
24
    auto MappedDomain = give(isl_map_domain(PHITarget.copy()));
934
24
    if (
!isl_set_is_subset(OrigDomain.keep(), MappedDomain.keep())24
) {
935
0
      DEBUG(dbgs()
936
0
            << "    Reject because mapping does not encompass all instances\n");
937
0
      return false;
938
0
    }
939
24
940
24
    // { DomainRead[] -> DomainWrite[] }
941
24
    auto PerPHIWrites = computePerPHI(SAI);
942
24
943
24
    // { DomainWrite[] -> Element[] }
944
24
    auto WritesTarget = give(isl_union_map_reverse(isl_union_map_apply_domain(
945
24
        PerPHIWrites.copy(), isl_union_map_from_map(PHITarget.copy()))));
946
24
    simplify(WritesTarget);
947
24
948
24
    // { DomainWrite[] }
949
24
    auto UniverseWritesDom = give(isl_union_set_empty(ParamSpace.copy()));
950
24
951
24
    for (auto *MA : S->getPHIIncomings(SAI))
952
48
      UniverseWritesDom = give(isl_union_set_add_set(UniverseWritesDom.take(),
953
48
                                                     getDomainFor(MA).take()));
954
24
955
24
    auto RelevantWritesTarget = WritesTarget;
956
24
    if (DelicmOverapproximateWrites)
957
11
      WritesTarget = expandMapping(WritesTarget, UniverseWritesDom);
958
24
959
24
    auto ExpandedWritesDom = give(isl_union_map_domain(WritesTarget.copy()));
960
24
    if (!DelicmPartialWrites &&
961
3
        !isl_union_set_is_subset(UniverseWritesDom.keep(),
962
24
                                 ExpandedWritesDom.keep())) {
963
1
      DEBUG(dbgs() << "    Reject because did not find PHI write mapping for "
964
1
                      "all instances\n");
965
1
      if (DelicmOverapproximateWrites)
966
1
        DEBUG(dbgs() << "      Relevant Mapping:    " << RelevantWritesTarget
967
1
                     << '\n');
968
1
      DEBUG(dbgs() << "      Deduced Mapping:     " << WritesTarget << '\n');
969
1
      DEBUG(dbgs() << "      Missing instances:    "
970
1
                   << give(isl_union_set_subtract(UniverseWritesDom.copy(),
971
1
                                                  ExpandedWritesDom.copy()))
972
1
                   << '\n');
973
1
      return false;
974
1
    }
975
23
976
23
    //  { DomainRead[] -> Scatter[] }
977
23
    auto PerPHIWriteScatter = give(isl_map_from_union_map(
978
23
        isl_union_map_apply_range(PerPHIWrites.copy(), Schedule.copy())));
979
23
980
23
    // { DomainRead[] -> Zone[] }
981
23
    auto Lifetime = betweenScatter(PerPHIWriteScatter, PHISched, false, true);
982
23
    simplify(Lifetime);
983
23
    DEBUG(dbgs() << "    Lifetime: " << Lifetime << "\n");
984
23
985
23
    // { DomainWrite[] -> Zone[] }
986
23
    auto WriteLifetime = give(isl_union_map_apply_domain(
987
23
        isl_union_map_from_map(Lifetime.copy()), PerPHIWrites.copy()));
988
23
989
23
    // { DomainWrite[] -> ValInst[] }
990
23
    auto WrittenValue = determinePHIWrittenValues(SAI);
991
23
992
23
    // { DomainWrite[] -> [Element[] -> Scatter[]] }
993
23
    auto WrittenTranslator =
994
23
        give(isl_union_map_range_product(WritesTarget.copy(), Schedule.copy()));
995
23
996
23
    // { [Element[] -> Scatter[]] -> ValInst[] }
997
23
    auto Written = give(isl_union_map_apply_domain(WrittenValue.copy(),
998
23
                                                   WrittenTranslator.copy()));
999
23
    simplify(Written);
1000
23
1001
23
    // { DomainWrite[] -> [Element[] -> Zone[]] }
1002
23
    auto LifetimeTranslator = give(
1003
23
        isl_union_map_range_product(WritesTarget.copy(), WriteLifetime.copy()));
1004
23
1005
23
    // { DomainWrite[] -> ValInst[] }
1006
23
    auto WrittenKnownValue = filterKnownValInst(WrittenValue);
1007
23
1008
23
    // { [Element[] -> Zone[]] -> ValInst[] }
1009
23
    auto EltLifetimeInst = give(isl_union_map_apply_domain(
1010
23
        WrittenKnownValue.copy(), LifetimeTranslator.copy()));
1011
23
    simplify(EltLifetimeInst);
1012
23
1013
23
    // { [Element[] -> Zone[] }
1014
23
    auto Occupied = give(isl_union_map_range(LifetimeTranslator.copy()));
1015
23
    simplify(Occupied);
1016
23
1017
23
    Knowledge Proposed(Occupied, nullptr, EltLifetimeInst, Written);
1018
23
    if (isConflicting(Proposed))
1019
2
      return false;
1020
21
1021
21
    mapPHI(SAI, std::move(PHITarget), std::move(WritesTarget),
1022
21
           std::move(Lifetime), std::move(Proposed));
1023
21
    return true;
1024
21
  }
1025
1026
  /// Map a MemoryKind::PHI scalar to an array element.
1027
  ///
1028
  /// Callers must have ensured that the mapping is valid and not conflicting
1029
  /// with the common knowledge.
1030
  ///
1031
  /// @param SAI         The ScopArrayInfo representing the scalar's memory to
1032
  ///                    map.
1033
  /// @param ReadTarget  { DomainRead[] -> Element[] }
1034
  ///                    The array element to map the scalar to.
1035
  /// @param WriteTarget { DomainWrite[] -> Element[] }
1036
  ///                    New access target for each PHI incoming write.
1037
  /// @param Lifetime    { DomainRead[] -> Zone[] }
1038
  ///                    The lifetime of each PHI for reporting.
1039
  /// @param Proposed    Mapping constraints for reporting.
1040
  void mapPHI(const ScopArrayInfo *SAI, isl::map ReadTarget,
1041
              isl::union_map WriteTarget, isl::map Lifetime,
1042
21
              Knowledge Proposed) {
1043
21
    // { Element[] }
1044
21
    isl::space ElementSpace = ReadTarget.get_space().range();
1045
21
1046
21
    // Redirect the PHI incoming writes.
1047
42
    for (auto *MA : S->getPHIIncomings(SAI)) {
1048
42
      // { DomainWrite[] }
1049
42
      auto Domain = getDomainFor(MA);
1050
42
1051
42
      // { DomainWrite[] -> Element[] }
1052
42
      auto NewAccRel = give(isl_union_map_intersect_domain(
1053
42
          WriteTarget.copy(), isl_union_set_from_set(Domain.copy())));
1054
42
      simplify(NewAccRel);
1055
42
1056
42
      isl::space NewAccRelSpace =
1057
42
          Domain.get_space().map_from_domain_and_range(ElementSpace);
1058
42
      isl::map NewAccRelMap = singleton(NewAccRel, NewAccRelSpace);
1059
42
      MA->setNewAccessRelation(NewAccRelMap);
1060
42
    }
1061
21
1062
21
    // Redirect the PHI read.
1063
21
    auto *PHIRead = S->getPHIRead(SAI);
1064
21
    PHIRead->setNewAccessRelation(ReadTarget);
1065
21
    applyLifetime(Proposed);
1066
21
1067
21
    MappedPHIScalars++;
1068
21
    NumberOfMappedPHIScalars++;
1069
21
  }
1070
1071
  /// Search and map scalars to memory overwritten by @p TargetStoreMA.
1072
  ///
1073
  /// Start trying to map scalars that are used in the same statement as the
1074
  /// store. For every successful mapping, try to also map scalars of the
1075
  /// statements where those are written. Repeat, until no more mapping
1076
  /// opportunity is found.
1077
  ///
1078
  /// There is currently no preference in which order scalars are tried.
1079
  /// Ideally, we would direct it towards a load instruction of the same array
1080
  /// element.
1081
30
  bool collapseScalarsToStore(MemoryAccess *TargetStoreMA) {
1082
30
    assert(TargetStoreMA->isLatestArrayKind());
1083
30
    assert(TargetStoreMA->isMustWrite());
1084
30
1085
30
    auto TargetStmt = TargetStoreMA->getStatement();
1086
30
1087
30
    // { DomTarget[] }
1088
30
    auto TargetDom = getDomainFor(TargetStmt);
1089
30
1090
30
    // { DomTarget[] -> Element[] }
1091
30
    auto TargetAccRel = getAccessRelationFor(TargetStoreMA);
1092
30
1093
30
    // { Zone[] -> DomTarget[] }
1094
30
    // For each point in time, find the next target store instance.
1095
30
    auto Target =
1096
30
        computeScalarReachingOverwrite(Schedule, TargetDom, false, true);
1097
30
1098
30
    // { Zone[] -> Element[] }
1099
30
    // Use the target store's write location as a suggestion to map scalars to.
1100
30
    auto EltTarget =
1101
30
        give(isl_map_apply_range(Target.take(), TargetAccRel.take()));
1102
30
    simplify(EltTarget);
1103
30
    DEBUG(dbgs() << "    Target mapping is " << EltTarget << '\n');
1104
30
1105
30
    // Stack of elements not yet processed.
1106
30
    SmallVector<MemoryAccess *, 16> Worklist;
1107
30
1108
30
    // Set of scalars already tested.
1109
30
    SmallPtrSet<const ScopArrayInfo *, 16> Closed;
1110
30
1111
30
    // Lambda to add all scalar reads to the work list.
1112
64
    auto ProcessAllIncoming = [&](ScopStmt *Stmt) {
1113
134
      for (auto *MA : *Stmt) {
1114
134
        if (!MA->isLatestScalarKind())
1115
87
          continue;
1116
47
        
if (47
!MA->isRead()47
)
1117
11
          continue;
1118
36
1119
36
        Worklist.push_back(MA);
1120
36
      }
1121
64
    };
1122
30
1123
30
    auto *WrittenVal = TargetStoreMA->getAccessInstruction()->getOperand(0);
1124
30
    if (auto *WrittenValInputMA = TargetStmt->lookupInputAccessOf(WrittenVal))
1125
22
      Worklist.push_back(WrittenValInputMA);
1126
30
    else
1127
8
      ProcessAllIncoming(TargetStmt);
1128
30
1129
30
    auto AnyMapped = false;
1130
30
    auto &DL = S->getRegion().getEntry()->getModule()->getDataLayout();
1131
30
    auto StoreSize =
1132
30
        DL.getTypeAllocSize(TargetStoreMA->getAccessValue()->getType());
1133
30
1134
107
    while (
!Worklist.empty()107
) {
1135
77
      auto *MA = Worklist.pop_back_val();
1136
77
1137
77
      auto *SAI = MA->getScopArrayInfo();
1138
77
      if (Closed.count(SAI))
1139
10
        continue;
1140
67
      Closed.insert(SAI);
1141
67
      DEBUG(dbgs() << "\n    Trying to map " << MA << " (SAI: " << SAI
1142
67
                   << ")\n");
1143
67
1144
67
      // Skip non-mappable scalars.
1145
67
      if (!isMappable(SAI))
1146
3
        continue;
1147
64
1148
64
      auto MASize = DL.getTypeAllocSize(MA->getAccessValue()->getType());
1149
64
      if (
MASize > StoreSize64
) {
1150
1
        DEBUG(dbgs() << "    Reject because storage size is insufficient\n");
1151
1
        continue;
1152
1
      }
1153
63
1154
63
      // Try to map MemoryKind::Value scalars.
1155
63
      
if (63
SAI->isValueKind()63
) {
1156
39
        if (!tryMapValue(SAI, EltTarget))
1157
6
          continue;
1158
33
1159
33
        auto *DefAcc = S->getValueDef(SAI);
1160
33
        ProcessAllIncoming(DefAcc->getStatement());
1161
33
1162
33
        AnyMapped = true;
1163
33
        continue;
1164
33
      }
1165
24
1166
24
      // Try to map MemoryKind::PHI scalars.
1167
24
      
if (24
SAI->isPHIKind()24
) {
1168
24
        if (!tryMapPHI(SAI, EltTarget))
1169
3
          continue;
1170
21
        // Add inputs of all incoming statements to the worklist. Prefer the
1171
21
        // input accesses of the incoming blocks.
1172
21
        
for (auto *PHIWrite : S->getPHIIncomings(SAI)) 21
{
1173
42
          auto *PHIWriteStmt = PHIWrite->getStatement();
1174
42
          bool FoundAny = false;
1175
42
          for (auto Incoming : PHIWrite->getIncoming()) {
1176
42
            auto *IncomingInputMA =
1177
42
                PHIWriteStmt->lookupInputAccessOf(Incoming.second);
1178
42
            if (!IncomingInputMA)
1179
23
              continue;
1180
19
1181
19
            Worklist.push_back(IncomingInputMA);
1182
19
            FoundAny = true;
1183
19
          }
1184
42
1185
42
          if (!FoundAny)
1186
23
            ProcessAllIncoming(PHIWrite->getStatement());
1187
42
        }
1188
24
1189
24
        AnyMapped = true;
1190
24
        continue;
1191
24
      }
1192
77
    }
1193
30
1194
30
    if (
AnyMapped30
) {
1195
19
      TargetsMapped++;
1196
19
      NumberOfTargetsMapped++;
1197
19
    }
1198
30
    return AnyMapped;
1199
30
  }
1200
1201
  /// Compute when an array element is unused.
1202
  ///
1203
  /// @return { [Element[] -> Zone[]] }
1204
36
  isl::union_set computeLifetime() const {
1205
36
    // { Element[] -> Zone[] }
1206
36
    auto ArrayUnused = computeArrayUnused(Schedule, AllMustWrites, AllReads,
1207
36
                                          false, false, true);
1208
36
1209
36
    auto Result = give(isl_union_map_wrap(ArrayUnused.copy()));
1210
36
1211
36
    simplify(Result);
1212
36
    return Result;
1213
36
  }
1214
1215
  /// Determine when an array element is written to, and which value instance is
1216
  /// written.
1217
  ///
1218
  /// @return { [Element[] -> Scatter[]] -> ValInst[] }
1219
36
  isl::union_map computeWritten() const {
1220
36
    // { [Element[] -> Scatter[]] -> ValInst[] }
1221
36
    auto EltWritten = applyDomainRange(AllWriteValInst, Schedule);
1222
36
1223
36
    simplify(EltWritten);
1224
36
    return EltWritten;
1225
36
  }
1226
1227
  /// Determine whether an access touches at most one element.
1228
  ///
1229
  /// The accessed element could be a scalar or accessing an array with constant
1230
  /// subscript, such that all instances access only that element.
1231
  ///
1232
  /// @param MA The access to test.
1233
  ///
1234
  /// @return True, if zero or one elements are accessed; False if at least two
1235
  ///         different elements are accessed.
1236
43
  bool isScalarAccess(MemoryAccess *MA) {
1237
43
    auto Map = getAccessRelationFor(MA);
1238
43
    auto Set = give(isl_map_range(Map.take()));
1239
43
    return isl_set_is_singleton(Set.keep()) == isl_bool_true;
1240
43
  }
1241
1242
  /// Print mapping statistics to @p OS.
1243
34
  void printStatistics(llvm::raw_ostream &OS, int Indent = 0) const {
1244
34
    OS.indent(Indent) << "Statistics {\n";
1245
34
    OS.indent(Indent + 4) << "Compatible overwrites: "
1246
34
                          << NumberOfCompatibleTargets << "\n";
1247
34
    OS.indent(Indent + 4) << "Overwrites mapped to:  " << NumberOfTargetsMapped
1248
34
                          << '\n';
1249
34
    OS.indent(Indent + 4) << "Value scalars mapped:  "
1250
34
                          << NumberOfMappedValueScalars << '\n';
1251
34
    OS.indent(Indent + 4) << "PHI scalars mapped:    "
1252
34
                          << NumberOfMappedPHIScalars << '\n';
1253
34
    OS.indent(Indent) << "}\n";
1254
34
  }
1255
1256
  /// Return whether at least one transformation been applied.
1257
34
  bool isModified() const { return NumberOfTargetsMapped > 0; }
1258
1259
public:
1260
36
  DeLICMImpl(Scop *S, LoopInfo *LI) : ZoneAlgorithm("polly-delicm", S, LI) {}
1261
1262
  /// Calculate the lifetime (definition to last use) of every array element.
1263
  ///
1264
  /// @return True if the computed lifetimes (#Zone) is usable.
1265
36
  bool computeZone() {
1266
36
    // Check that nothing strange occurs.
1267
36
    collectCompatibleElts();
1268
36
1269
36
    isl::union_set EltUnused;
1270
36
    isl::union_map EltKnown, EltWritten;
1271
36
1272
36
    {
1273
36
      IslMaxOperationsGuard MaxOpGuard(IslCtx.get(), DelicmMaxOps);
1274
36
1275
36
      computeCommon();
1276
36
1277
36
      EltUnused = computeLifetime();
1278
36
      EltKnown = computeKnown(true, false);
1279
36
      EltWritten = computeWritten();
1280
36
    }
1281
36
    DeLICMAnalyzed++;
1282
36
1283
36
    if (
!EltUnused || 36
!EltKnown35
||
!EltWritten35
) {
1284
1
      assert(isl_ctx_last_error(IslCtx.get()) == isl_error_quota &&
1285
1
             "The only reason that these things have not been computed should "
1286
1
             "be if the max-operations limit hit");
1287
1
      DeLICMOutOfQuota++;
1288
1
      DEBUG(dbgs() << "DeLICM analysis exceeded max_operations\n");
1289
1
      DebugLoc Begin, End;
1290
1
      getDebugLocations(getBBPairForRegion(&S->getRegion()), Begin, End);
1291
1
      OptimizationRemarkAnalysis R(DEBUG_TYPE, "OutOfQuota", Begin,
1292
1
                                   S->getEntry());
1293
1
      R << "maximal number of operations exceeded during zone analysis";
1294
1
      S->getFunction().getContext().diagnose(R);
1295
1
      return false;
1296
1
    }
1297
35
1298
35
    Zone = OriginalZone = Knowledge(nullptr, EltUnused, EltKnown, EltWritten);
1299
35
    DEBUG(dbgs() << "Computed Zone:\n"; OriginalZone.print(dbgs(), 4));
1300
36
1301
36
    assert(Zone.isUsable() && OriginalZone.isUsable());
1302
36
    return true;
1303
36
  }
1304
1305
  /// Try to map as many scalars to unused array elements as possible.
1306
  ///
1307
  /// Multiple scalars might be mappable to intersecting unused array element
1308
  /// zones, but we can only chose one. This is a greedy algorithm, therefore
1309
  /// the first processed element claims it.
1310
35
  void greedyCollapse() {
1311
35
    bool Modified = false;
1312
35
1313
162
    for (auto &Stmt : *S) {
1314
325
      for (auto *MA : Stmt) {
1315
325
        if (!MA->isLatestArrayKind())
1316
252
          continue;
1317
73
        
if (73
!MA->isWrite()73
)
1318
25
          continue;
1319
48
1320
48
        
if (48
MA->isMayWrite()48
) {
1321
4
          DEBUG(dbgs() << "Access " << MA
1322
4
                       << " pruned because it is a MAY_WRITE\n");
1323
4
          OptimizationRemarkMissed R(DEBUG_TYPE, "TargetMayWrite",
1324
4
                                     MA->getAccessInstruction());
1325
4
          R << "Skipped possible mapping target because it is not an "
1326
4
               "unconditional overwrite";
1327
4
          S->getFunction().getContext().diagnose(R);
1328
4
          continue;
1329
4
        }
1330
44
1331
44
        
if (44
Stmt.getNumIterators() == 044
) {
1332
1
          DEBUG(dbgs() << "Access " << MA
1333
1
                       << " pruned because it is not in a loop\n");
1334
1
          OptimizationRemarkMissed R(DEBUG_TYPE, "WriteNotInLoop",
1335
1
                                     MA->getAccessInstruction());
1336
1
          R << "skipped possible mapping target because it is not in a loop";
1337
1
          S->getFunction().getContext().diagnose(R);
1338
1
          continue;
1339
1
        }
1340
43
1341
43
        
if (43
isScalarAccess(MA)43
) {
1342
6
          DEBUG(dbgs() << "Access " << MA
1343
6
                       << " pruned because it writes only a single element\n");
1344
6
          OptimizationRemarkMissed R(DEBUG_TYPE, "ScalarWrite",
1345
6
                                     MA->getAccessInstruction());
1346
6
          R << "skipped possible mapping target because the memory location "
1347
6
               "written to does not depend on its outer loop";
1348
6
          S->getFunction().getContext().diagnose(R);
1349
6
          continue;
1350
6
        }
1351
37
1352
37
        
if (37
!isa<StoreInst>(MA->getAccessInstruction())37
) {
1353
3
          DEBUG(dbgs() << "Access " << MA
1354
3
                       << " pruned because it is not a StoreInst\n");
1355
3
          OptimizationRemarkMissed R(DEBUG_TYPE, "NotAStore",
1356
3
                                     MA->getAccessInstruction());
1357
3
          R << "skipped possible mapping target because non-store instructions "
1358
3
               "are not supported";
1359
3
          S->getFunction().getContext().diagnose(R);
1360
3
          continue;
1361
3
        }
1362
34
1363
34
        isl::union_set TouchedElts = MA->getLatestAccessRelation().range();
1364
34
        if (
!TouchedElts.is_subset(CompatibleElts)34
) {
1365
4
          DEBUG(
1366
4
              dbgs()
1367
4
              << "Access " << MA
1368
4
              << " is incompatible because it touches incompatible elements\n");
1369
4
          OptimizationRemarkMissed R(DEBUG_TYPE, "IncompatibleElts",
1370
4
                                     MA->getAccessInstruction());
1371
4
          R << "skipped possible mapping target because a target location "
1372
4
               "cannot be reliably analyzed";
1373
4
          S->getFunction().getContext().diagnose(R);
1374
4
          continue;
1375
4
        }
1376
30
1377
34
        assert(isCompatibleAccess(MA));
1378
30
        NumberOfCompatibleTargets++;
1379
30
        DEBUG(dbgs() << "Analyzing target access " << MA << "\n");
1380
30
        if (collapseScalarsToStore(MA))
1381
19
          Modified = true;
1382
325
      }
1383
162
    }
1384
35
1385
35
    if (Modified)
1386
19
      DeLICMScopsModified++;
1387
35
  }
1388
1389
  /// Dump the internal information about a performed DeLICM to @p OS.
1390
35
  void print(llvm::raw_ostream &OS, int Indent = 0) {
1391
35
    if (
!Zone.isUsable()35
) {
1392
1
      OS.indent(Indent) << "Zone not computed\n";
1393
1
      return;
1394
1
    }
1395
34
1396
34
    printStatistics(OS, Indent);
1397
34
    if (
!isModified()34
) {
1398
16
      OS.indent(Indent) << "No modification has been made\n";
1399
16
      return;
1400
16
    }
1401
18
    printAccesses(OS, Indent);
1402
18
  }
1403
};
1404
1405
class DeLICM : public ScopPass {
1406
private:
1407
  DeLICM(const DeLICM &) = delete;
1408
  const DeLICM &operator=(const DeLICM &) = delete;
1409
1410
  /// The pass implementation, also holding per-scop data.
1411
  std::unique_ptr<DeLICMImpl> Impl;
1412
1413
36
  void collapseToUnused(Scop &S) {
1414
36
    auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1415
36
    Impl = make_unique<DeLICMImpl>(&S, &LI);
1416
36
1417
36
    if (
!Impl->computeZone()36
) {
1418
1
      DEBUG(dbgs() << "Abort because cannot reliably compute lifetimes\n");
1419
1
      return;
1420
1
    }
1421
35
1422
35
    
DEBUG35
(dbgs() << "Collapsing scalars to unused array elements...\n");
1423
35
    Impl->greedyCollapse();
1424
35
1425
35
    DEBUG(dbgs() << "\nFinal Scop:\n");
1426
35
    DEBUG(dbgs() << S);
1427
36
  }
1428
1429
public:
1430
  static char ID;
1431
36
  explicit DeLICM() : ScopPass(ID) {}
1432
1433
36
  virtual void getAnalysisUsage(AnalysisUsage &AU) const override {
1434
36
    AU.addRequiredTransitive<ScopInfoRegionPass>();
1435
36
    AU.addRequired<LoopInfoWrapperPass>();
1436
36
    AU.setPreservesAll();
1437
36
  }
1438
1439
36
  virtual bool runOnScop(Scop &S) override {
1440
36
    // Free resources for previous scop's computation, if not yet done.
1441
36
    releaseMemory();
1442
36
1443
36
    collapseToUnused(S);
1444
36
1445
36
    auto ScopStats = S.getStatistics();
1446
36
    NumValueWrites += ScopStats.NumValueWrites;
1447
36
    NumValueWritesInLoops += ScopStats.NumValueWritesInLoops;
1448
36
    NumPHIWrites += ScopStats.NumPHIWrites;
1449
36
    NumPHIWritesInLoops += ScopStats.NumPHIWritesInLoops;
1450
36
    NumSingletonWrites += ScopStats.NumSingletonWrites;
1451
36
    NumSingletonWritesInLoops += ScopStats.NumSingletonWritesInLoops;
1452
36
1453
36
    return false;
1454
36
  }
1455
1456
35
  virtual void printScop(raw_ostream &OS, Scop &S) const override {
1457
35
    if (!Impl)
1458
0
      return;
1459
35
    assert(Impl->getScop() == &S);
1460
35
1461
35
    OS << "DeLICM result:\n";
1462
35
    Impl->print(OS);
1463
35
  }
1464
1465
191
  virtual void releaseMemory() override { Impl.reset(); }
1466
};
1467
1468
char DeLICM::ID;
1469
} // anonymous namespace
1470
1471
0
Pass *polly::createDeLICMPass() { return new DeLICM(); }
1472
1473
41.7k
INITIALIZE_PASS_BEGIN41.7k
(DeLICM, "polly-delicm", "Polly - DeLICM/DePRE", false,
1474
41.7k
                      false)
1475
41.7k
INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass)
1476
41.7k
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
1477
41.7k
INITIALIZE_PASS_END(DeLICM, "polly-delicm", "Polly - DeLICM/DePRE", false,
1478
                    false)
1479
1480
bool polly::isConflicting(
1481
    isl::union_set ExistingOccupied, isl::union_set ExistingUnused,
1482
    isl::union_map ExistingKnown, isl::union_map ExistingWrites,
1483
    isl::union_set ProposedOccupied, isl::union_set ProposedUnused,
1484
    isl::union_map ProposedKnown, isl::union_map ProposedWrites,
1485
232
    llvm::raw_ostream *OS, unsigned Indent) {
1486
232
  Knowledge Existing(std::move(ExistingOccupied), std::move(ExistingUnused),
1487
232
                     std::move(ExistingKnown), std::move(ExistingWrites));
1488
232
  Knowledge Proposed(std::move(ProposedOccupied), std::move(ProposedUnused),
1489
232
                     std::move(ProposedKnown), std::move(ProposedWrites));
1490
232
1491
232
  return Knowledge::isConflicting(Existing, Proposed, OS, Indent);
1492
232
}