Coverage Report

Created: 2019-04-25 15:07

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