Coverage Report

Created: 2017-08-18 19:41

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