Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/Transform/ZoneAlgo.cpp
Line
Count
Source (jump to first uncovered line)
1
//===------ ZoneAlgo.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
// Derive information about array elements between statements ("Zones").
11
//
12
// The algorithms here work on the scatter space - the image space of the
13
// schedule returned by Scop::getSchedule(). We call an element in that space a
14
// "timepoint". Timepoints are lexicographically ordered such that we can
15
// defined ranges in the scatter space. We use two flavors of such ranges:
16
// Timepoint sets and zones. A timepoint set is simply a subset of the scatter
17
// space and is directly stored as isl_set.
18
//
19
// Zones are used to describe the space between timepoints as open sets, i.e.
20
// they do not contain the extrema. Using isl rational sets to express these
21
// would be overkill. We also cannot store them as the integer timepoints they
22
// contain; the (nonempty) zone between 1 and 2 would be empty and
23
// indistinguishable from e.g. the zone between 3 and 4. Also, we cannot store
24
// the integer set including the extrema; the set ]1,2[ + ]3,4[ could be
25
// coalesced to ]1,3[, although we defined the range [2,3] to be not in the set.
26
// Instead, we store the "half-open" integer extrema, including the lower bound,
27
// but excluding the upper bound. Examples:
28
//
29
// * The set { [i] : 1 <= i <= 3 } represents the zone ]0,3[ (which contains the
30
//   integer points 1 and 2, but not 0 or 3)
31
//
32
// * { [1] } represents the zone ]0,1[
33
//
34
// * { [i] : i = 1 or i = 3 } represents the zone ]0,1[ + ]2,3[
35
//
36
// Therefore, an integer i in the set represents the zone ]i-1,i[, i.e. strictly
37
// speaking the integer points never belong to the zone. However, depending an
38
// the interpretation, one might want to include them. Part of the
39
// interpretation may not be known when the zone is constructed.
40
//
41
// Reads are assumed to always take place before writes, hence we can think of
42
// reads taking place at the beginning of a timepoint and writes at the end.
43
//
44
// Let's assume that the zone represents the lifetime of a variable. That is,
45
// the zone begins with a write that defines the value during its lifetime and
46
// ends with the last read of that value. In the following we consider whether a
47
// read/write at the beginning/ending of the lifetime zone should be within the
48
// zone or outside of it.
49
//
50
// * A read at the timepoint that starts the live-range loads the previous
51
//   value. Hence, exclude the timepoint starting the zone.
52
//
53
// * A write at the timepoint that starts the live-range is not defined whether
54
//   it occurs before or after the write that starts the lifetime. We do not
55
//   allow this situation to occur. Hence, we include the timepoint starting the
56
//   zone to determine whether they are conflicting.
57
//
58
// * A read at the timepoint that ends the live-range reads the same variable.
59
//   We include the timepoint at the end of the zone to include that read into
60
//   the live-range. Doing otherwise would mean that the two reads access
61
//   different values, which would mean that the value they read are both alive
62
//   at the same time but occupy the same variable.
63
//
64
// * A write at the timepoint that ends the live-range starts a new live-range.
65
//   It must not be included in the live-range of the previous definition.
66
//
67
// All combinations of reads and writes at the endpoints are possible, but most
68
// of the time only the write->read (for instance, a live-range from definition
69
// to last use) and read->write (for instance, an unused range from last use to
70
// overwrite) and combinations are interesting (half-open ranges). write->write
71
// zones might be useful as well in some context to represent
72
// output-dependencies.
73
//
74
// @see convertZoneToTimepoints
75
//
76
//
77
// The code makes use of maps and sets in many different spaces. To not loose
78
// track in which space a set or map is expected to be in, variables holding an
79
// isl reference are usually annotated in the comments. They roughly follow isl
80
// syntax for spaces, but only the tuples, not the dimensions. The tuples have a
81
// meaning as follows:
82
//
83
// * Space[] - An unspecified tuple. Used for function parameters such that the
84
//             function caller can use it for anything they like.
85
//
86
// * Domain[] - A statement instance as returned by ScopStmt::getDomain()
87
//     isl_id_get_name: Stmt_<NameOfBasicBlock>
88
//     isl_id_get_user: Pointer to ScopStmt
89
//
90
// * Element[] - An array element as in the range part of
91
//               MemoryAccess::getAccessRelation()
92
//     isl_id_get_name: MemRef_<NameOfArrayVariable>
93
//     isl_id_get_user: Pointer to ScopArrayInfo
94
//
95
// * Scatter[] - Scatter space or space of timepoints
96
//     Has no tuple id
97
//
98
// * Zone[] - Range between timepoints as described above
99
//     Has no tuple id
100
//
101
// * ValInst[] - An llvm::Value as defined at a specific timepoint.
102
//
103
//     A ValInst[] itself can be structured as one of:
104
//
105
//     * [] - An unknown value.
106
//         Always zero dimensions
107
//         Has no tuple id
108
//
109
//     * Value[] - An llvm::Value that is read-only in the SCoP, i.e. its
110
//                 runtime content does not depend on the timepoint.
111
//         Always zero dimensions
112
//         isl_id_get_name: Val_<NameOfValue>
113
//         isl_id_get_user: A pointer to an llvm::Value
114
//
115
//     * SCEV[...] - A synthesizable llvm::SCEV Expression.
116
//         In contrast to a Value[] is has at least one dimension per
117
//         SCEVAddRecExpr in the SCEV.
118
//
119
//     * [Domain[] -> Value[]] - An llvm::Value that may change during the
120
//                               Scop's execution.
121
//         The tuple itself has no id, but it wraps a map space holding a
122
//         statement instance which defines the llvm::Value as the map's domain
123
//         and llvm::Value itself as range.
124
//
125
// @see makeValInst()
126
//
127
// An annotation "{ Domain[] -> Scatter[] }" therefore means: A map from a
128
// statement instance to a timepoint, aka a schedule. There is only one scatter
129
// space, but most of the time multiple statements are processed in one set.
130
// This is why most of the time isl_union_map has to be used.
131
//
132
// The basic algorithm works as follows:
133
// At first we verify that the SCoP is compatible with this technique. For
134
// instance, two writes cannot write to the same location at the same statement
135
// instance because we cannot determine within the polyhedral model which one
136
// comes first. Once this was verified, we compute zones at which an array
137
// element is unused. This computation can fail if it takes too long. Then the
138
// main algorithm is executed. Because every store potentially trails an unused
139
// zone, we start at stores. We search for a scalar (MemoryKind::Value or
140
// MemoryKind::PHI) that we can map to the array element overwritten by the
141
// store, preferably one that is used by the store or at least the ScopStmt.
142
// When it does not conflict with the lifetime of the values in the array
143
// element, the map is applied and the unused zone updated as it is now used. We
144
// continue to try to map scalars to the array element until there are no more
145
// candidates to map. The algorithm is greedy in the sense that the first scalar
146
// not conflicting will be mapped. Other scalars processed later that could have
147
// fit the same unused zone will be rejected. As such the result depends on the
148
// processing order.
149
//
150
//===----------------------------------------------------------------------===//
151
152
#include "polly/ZoneAlgo.h"
153
#include "polly/ScopInfo.h"
154
#include "polly/Support/GICHelper.h"
155
#include "polly/Support/ISLTools.h"
156
#include "polly/Support/VirtualInstruction.h"
157
#include "llvm/ADT/Statistic.h"
158
159
#define DEBUG_TYPE "polly-zone"
160
161
STATISTIC(NumIncompatibleArrays, "Number of not zone-analyzable arrays");
162
STATISTIC(NumCompatibleArrays, "Number of zone-analyzable arrays");
163
164
using namespace polly;
165
using namespace llvm;
166
167
static isl::union_map computeReachingDefinition(isl::union_map Schedule,
168
                                                isl::union_map Writes,
169
134
                                                bool InclDef, bool InclRedef) {
170
134
  return computeReachingWrite(Schedule, Writes, false, InclDef, InclRedef);
171
134
}
172
173
/// Compute the reaching definition of a scalar.
174
///
175
/// Compared to computeReachingDefinition, there is just one element which is
176
/// accessed and therefore only a set if instances that accesses that element is
177
/// required.
178
///
179
/// @param Schedule  { DomainWrite[] -> Scatter[] }
180
/// @param Writes    { DomainWrite[] }
181
/// @param InclDef   Include the timepoint of the definition to the result.
182
/// @param InclRedef Include the timepoint of the overwrite into the result.
183
///
184
/// @return { Scatter[] -> DomainWrite[] }
185
static isl::union_map computeScalarReachingDefinition(isl::union_map Schedule,
186
                                                      isl::union_set Writes,
187
                                                      bool InclDef,
188
70
                                                      bool InclRedef) {
189
70
  // { DomainWrite[] -> Element[] }
190
70
  isl::union_map Defs = isl::union_map::from_domain(Writes);
191
70
192
70
  // { [Element[] -> Scatter[]] -> DomainWrite[] }
193
70
  auto ReachDefs =
194
70
      computeReachingDefinition(Schedule, Defs, InclDef, InclRedef);
195
70
196
70
  // { Scatter[] -> DomainWrite[] }
197
70
  return ReachDefs.curry().range().unwrap();
198
70
}
199
200
/// Compute the reaching definition of a scalar.
201
///
202
/// This overload accepts only a single writing statement as an isl_map,
203
/// consequently the result also is only a single isl_map.
204
///
205
/// @param Schedule  { DomainWrite[] -> Scatter[] }
206
/// @param Writes    { DomainWrite[] }
207
/// @param InclDef   Include the timepoint of the definition to the result.
208
/// @param InclRedef Include the timepoint of the overwrite into the result.
209
///
210
/// @return { Scatter[] -> DomainWrite[] }
211
static isl::map computeScalarReachingDefinition(isl::union_map Schedule,
212
                                                isl::set Writes, bool InclDef,
213
70
                                                bool InclRedef) {
214
70
  isl::space DomainSpace = Writes.get_space();
215
70
  isl::space ScatterSpace = getScatterSpace(Schedule);
216
70
217
70
  //  { Scatter[] -> DomainWrite[] }
218
70
  isl::union_map UMap = computeScalarReachingDefinition(
219
70
      Schedule, isl::union_set(Writes), InclDef, InclRedef);
220
70
221
70
  isl::space ResultSpace = ScatterSpace.map_from_domain_and_range(DomainSpace);
222
70
  return singleton(UMap, ResultSpace);
223
70
}
224
225
584
isl::union_map polly::makeUnknownForDomain(isl::union_set Domain) {
226
584
  return give(isl_union_map_from_domain(Domain.take()));
227
584
}
228
229
/// Create a domain-to-unknown value mapping.
230
///
231
/// @see makeUnknownForDomain(isl::union_set)
232
///
233
/// @param Domain { Domain[] }
234
///
235
/// @return { Domain[] -> ValInst[] }
236
16
static isl::map makeUnknownForDomain(isl::set Domain) {
237
16
  return give(isl_map_from_domain(Domain.take()));
238
16
}
239
240
/// Return whether @p Map maps to an unknown value.
241
///
242
/// @param { [] -> ValInst[] }
243
505
static bool isMapToUnknown(const isl::map &Map) {
244
505
  isl::space Space = Map.get_space().range();
245
505
  return Space.has_tuple_id(isl::dim::set).is_false() &&
246
505
         
Space.is_wrapping().is_false()340
&&
Space.dim(isl::dim::set) == 090
;
247
505
}
248
249
520
isl::union_map polly::filterKnownValInst(const isl::union_map &UMap) {
250
520
  isl::union_map Result = isl::union_map::empty(UMap.get_space());
251
505
  isl::stat Success = UMap.foreach_map([=, &Result](isl::map Map) -> isl::stat {
252
505
    if (!isMapToUnknown(Map))
253
415
      Result = Result.add_map(Map);
254
505
    return isl::stat::ok;
255
505
  });
256
520
  if (Success != isl::stat::ok)
257
1
    return {};
258
519
  return Result;
259
519
}
260
261
ZoneAlgorithm::ZoneAlgorithm(const char *PassName, Scop *S, LoopInfo *LI)
262
    : PassName(PassName), IslCtx(S->getSharedIslCtx()), S(S), LI(LI),
263
64
      Schedule(S->getSchedule()) {
264
64
  auto Domains = S->getDomains();
265
64
266
64
  Schedule =
267
64
      give(isl_union_map_intersect_domain(Schedule.take(), Domains.take()));
268
64
  ParamSpace = give(isl_union_map_get_space(Schedule.keep()));
269
64
  ScatterSpace = getScatterSpace(Schedule);
270
64
}
271
272
/// Check if all stores in @p Stmt store the very same value.
273
///
274
/// This covers a special situation occurring in Polybench's
275
/// covariance/correlation (which is typical for algorithms that cover symmetric
276
/// matrices):
277
///
278
/// for (int i = 0; i < n; i += 1)
279
///   for (int j = 0; j <= i; j += 1) {
280
///     double x = ...;
281
///     C[i][j] = x;
282
///     C[j][i] = x;
283
///   }
284
///
285
/// For i == j, the same value is written twice to the same element.Double
286
/// writes to the same element are not allowed in DeLICM because its algorithm
287
/// does not see which of the writes is effective.But if its the same value
288
/// anyway, it doesn't matter.
289
///
290
/// LLVM passes, however, cannot simplify this because the write is necessary
291
/// for i != j (unless it would add a condition for one of the writes to occur
292
/// only if i != j).
293
///
294
/// TODO: In the future we may want to extent this to make the checks
295
///       specific to different memory locations.
296
6
static bool onlySameValueWrites(ScopStmt *Stmt) {
297
6
  Value *V = nullptr;
298
6
299
19
  for (auto *MA : *Stmt) {
300
19
    if (
!MA->isLatestArrayKind() || 19
!MA->isMustWrite()13
||
301
10
        !MA->isOriginalArrayKind())
302
9
      continue;
303
10
304
10
    
if (10
!V10
) {
305
5
      V = MA->getAccessValue();
306
5
      continue;
307
5
    }
308
5
309
5
    
if (5
V != MA->getAccessValue()5
)
310
3
      return false;
311
3
  }
312
3
  return true;
313
3
}
314
315
void ZoneAlgorithm::collectIncompatibleElts(ScopStmt *Stmt,
316
                                            isl::union_set &IncompatibleElts,
317
230
                                            isl::union_set &AllElts) {
318
230
  auto Stores = makeEmptyUnionMap();
319
230
  auto Loads = makeEmptyUnionMap();
320
230
321
230
  // This assumes that the MemoryKind::Array MemoryAccesses are iterated in
322
230
  // order.
323
460
  for (auto *MA : *Stmt) {
324
460
    if (!MA->isLatestArrayKind())
325
344
      continue;
326
116
327
116
    isl::map AccRelMap = getAccessRelationFor(MA);
328
116
    isl::union_map AccRel = AccRelMap;
329
116
330
116
    // To avoid solving any ILP problems, always add entire arrays instead of
331
116
    // just the elements that are accessed.
332
116
    auto ArrayElts = isl::set::universe(AccRelMap.get_space().range());
333
116
    AllElts = AllElts.add_set(ArrayElts);
334
116
335
116
    if (
MA->isRead()116
) {
336
25
      // Reject load after store to same location.
337
25
      if (
!isl_union_map_is_disjoint(Stores.keep(), AccRel.keep())25
) {
338
1
        DEBUG(dbgs() << "Load after store of same element in same statement\n");
339
1
        OptimizationRemarkMissed R(PassName, "LoadAfterStore",
340
1
                                   MA->getAccessInstruction());
341
1
        R << "load after store of same element in same statement";
342
1
        R << " (previous stores: " << Stores;
343
1
        R << ", loading: " << AccRel << ")";
344
1
        S->getFunction().getContext().diagnose(R);
345
1
346
1
        IncompatibleElts = IncompatibleElts.add_set(ArrayElts);
347
1
      }
348
25
349
25
      Loads = give(isl_union_map_union(Loads.take(), AccRel.take()));
350
25
351
25
      continue;
352
25
    }
353
91
354
91
    // In region statements the order is less clear, eg. the load and store
355
91
    // might be in a boxed loop.
356
91
    
if (91
Stmt->isRegionStmt() &&
357
91
        
!isl_union_map_is_disjoint(Loads.keep(), AccRel.keep())9
) {
358
2
      DEBUG(dbgs() << "WRITE in non-affine subregion not supported\n");
359
2
      OptimizationRemarkMissed R(PassName, "StoreInSubregion",
360
2
                                 MA->getAccessInstruction());
361
2
      R << "store is in a non-affine subregion";
362
2
      S->getFunction().getContext().diagnose(R);
363
2
364
2
      IncompatibleElts = IncompatibleElts.add_set(ArrayElts);
365
2
    }
366
91
367
91
    // Do not allow more than one store to the same location.
368
91
    if (!isl_union_map_is_disjoint(Stores.keep(), AccRel.keep()) &&
369
91
        
!onlySameValueWrites(Stmt)6
) {
370
3
      DEBUG(dbgs() << "WRITE after WRITE to same element\n");
371
3
      OptimizationRemarkMissed R(PassName, "StoreAfterStore",
372
3
                                 MA->getAccessInstruction());
373
3
      R << "store after store of same element in same statement";
374
3
      R << " (previous stores: " << Stores;
375
3
      R << ", storing: " << AccRel << ")";
376
3
      S->getFunction().getContext().diagnose(R);
377
3
378
3
      IncompatibleElts = IncompatibleElts.add_set(ArrayElts);
379
3
    }
380
460
381
460
    Stores = give(isl_union_map_union(Stores.take(), AccRel.take()));
382
460
  }
383
230
}
384
385
25
void ZoneAlgorithm::addArrayReadAccess(MemoryAccess *MA) {
386
25
  assert(MA->isLatestArrayKind());
387
25
  assert(MA->isRead());
388
25
  ScopStmt *Stmt = MA->getStatement();
389
25
390
25
  // { DomainRead[] -> Element[] }
391
25
  auto AccRel = intersectRange(getAccessRelationFor(MA), CompatibleElts);
392
25
  AllReads = give(isl_union_map_add_map(AllReads.take(), AccRel.copy()));
393
25
394
25
  if (LoadInst *
Load25
= dyn_cast_or_null<LoadInst>(MA->getAccessInstruction())) {
395
25
    // { DomainRead[] -> ValInst[] }
396
25
    isl::map LoadValInst = makeValInst(
397
25
        Load, Stmt, LI->getLoopFor(Load->getParent()), Stmt->isBlockStmt());
398
25
399
25
    // { DomainRead[] -> [Element[] -> DomainRead[]] }
400
25
    isl::map IncludeElement =
401
25
        give(isl_map_curry(isl_map_domain_map(AccRel.take())));
402
25
403
25
    // { [Element[] -> DomainRead[]] -> ValInst[] }
404
25
    isl::map EltLoadValInst =
405
25
        give(isl_map_apply_domain(LoadValInst.take(), IncludeElement.take()));
406
25
407
25
    AllReadValInst = give(
408
25
        isl_union_map_add_map(AllReadValInst.take(), EltLoadValInst.take()));
409
25
  }
410
25
}
411
412
91
isl::map ZoneAlgorithm::getWrittenValue(MemoryAccess *MA, isl::map AccRel) {
413
91
  if (!MA->isMustWrite())
414
9
    return {};
415
82
416
82
  Value *AccVal = MA->getAccessValue();
417
82
  ScopStmt *Stmt = MA->getStatement();
418
82
  Instruction *AccInst = MA->getAccessInstruction();
419
82
420
82
  // Write a value to a single element.
421
82
  auto L = MA->isOriginalArrayKind() ? LI->getLoopFor(AccInst->getParent())
422
0
                                     : Stmt->getSurroundingLoop();
423
82
  if (AccVal &&
424
77
      AccVal->getType() == MA->getLatestScopArrayInfo()->getElementType() &&
425
74
      AccRel.is_single_valued().is_true())
426
73
    return makeValInst(AccVal, Stmt, L);
427
9
428
9
  // memset(_, '0', ) is equivalent to writing the null value to all touched
429
9
  // elements. isMustWrite() ensures that all of an element's bytes are
430
9
  // overwritten.
431
9
  
if (auto *9
Memset9
= dyn_cast<MemSetInst>(AccInst)) {
432
5
    auto *WrittenConstant = dyn_cast<Constant>(Memset->getValue());
433
5
    Type *Ty = MA->getLatestScopArrayInfo()->getElementType();
434
5
    if (
WrittenConstant && 5
WrittenConstant->isZeroValue()5
) {
435
5
      Constant *Zero = Constant::getNullValue(Ty);
436
5
      return makeValInst(Zero, Stmt, L);
437
5
    }
438
4
  }
439
4
440
4
  return {};
441
4
}
442
443
91
void ZoneAlgorithm::addArrayWriteAccess(MemoryAccess *MA) {
444
91
  assert(MA->isLatestArrayKind());
445
91
  assert(MA->isWrite());
446
91
  auto *Stmt = MA->getStatement();
447
91
448
91
  // { Domain[] -> Element[] }
449
91
  auto AccRel = intersectRange(getAccessRelationFor(MA), CompatibleElts);
450
91
451
91
  if (MA->isMustWrite())
452
82
    AllMustWrites =
453
82
        give(isl_union_map_add_map(AllMustWrites.take(), AccRel.copy()));
454
91
455
91
  if (MA->isMayWrite())
456
9
    AllMayWrites =
457
9
        give(isl_union_map_add_map(AllMayWrites.take(), AccRel.copy()));
458
91
459
91
  // { Domain[] -> ValInst[] }
460
91
  auto WriteValInstance = getWrittenValue(MA, AccRel);
461
91
  if (!WriteValInstance)
462
13
    WriteValInstance = makeUnknownForDomain(Stmt);
463
91
464
91
  // { Domain[] -> [Element[] -> Domain[]] }
465
91
  auto IncludeElement = give(isl_map_curry(isl_map_domain_map(AccRel.copy())));
466
91
467
91
  // { [Element[] -> DomainWrite[]] -> ValInst[] }
468
91
  auto EltWriteValInst = give(
469
91
      isl_map_apply_domain(WriteValInstance.take(), IncludeElement.take()));
470
91
471
91
  AllWriteValInst = give(
472
91
      isl_union_map_add_map(AllWriteValInst.take(), EltWriteValInst.take()));
473
91
}
474
475
165
isl::union_set ZoneAlgorithm::makeEmptyUnionSet() const {
476
165
  return give(isl_union_set_empty(ParamSpace.copy()));
477
165
}
478
479
891
isl::union_map ZoneAlgorithm::makeEmptyUnionMap() const {
480
891
  return give(isl_union_map_empty(ParamSpace.copy()));
481
891
}
482
483
64
void ZoneAlgorithm::collectCompatibleElts() {
484
64
  // First find all the incompatible elements, then take the complement.
485
64
  // We compile the list of compatible (rather than incompatible) elements so
486
64
  // users can intersect with the list, not requiring a subtract operation. It
487
64
  // also allows us to define a 'universe' of all elements and makes it more
488
64
  // explicit in which array elements can be used.
489
64
  isl::union_set AllElts = makeEmptyUnionSet();
490
64
  isl::union_set IncompatibleElts = makeEmptyUnionSet();
491
64
492
64
  for (auto &Stmt : *S)
493
230
    collectIncompatibleElts(&Stmt, IncompatibleElts, AllElts);
494
64
495
64
  NumIncompatibleArrays += isl_union_set_n_set(IncompatibleElts.keep());
496
64
  CompatibleElts = AllElts.subtract(IncompatibleElts);
497
64
  NumCompatibleArrays += isl_union_set_n_set(CompatibleElts.keep());
498
64
}
499
500
192
isl::map ZoneAlgorithm::getScatterFor(ScopStmt *Stmt) const {
501
192
  isl::space ResultSpace = give(isl_space_map_from_domain_and_range(
502
192
      Stmt->getDomainSpace().release(), ScatterSpace.copy()));
503
192
  return give(isl_union_map_extract_map(Schedule.keep(), ResultSpace.take()));
504
192
}
505
506
134
isl::map ZoneAlgorithm::getScatterFor(MemoryAccess *MA) const {
507
134
  return getScatterFor(MA->getStatement());
508
134
}
509
510
198
isl::union_map ZoneAlgorithm::getScatterFor(isl::union_set Domain) const {
511
198
  return give(isl_union_map_intersect_domain(Schedule.copy(), Domain.take()));
512
198
}
513
514
128
isl::map ZoneAlgorithm::getScatterFor(isl::set Domain) const {
515
128
  auto ResultSpace = give(isl_space_map_from_domain_and_range(
516
128
      isl_set_get_space(Domain.keep()), ScatterSpace.copy()));
517
128
  auto UDomain = give(isl_union_set_from_set(Domain.copy()));
518
128
  auto UResult = getScatterFor(std::move(UDomain));
519
128
  auto Result = singleton(std::move(UResult), std::move(ResultSpace));
520
128
  assert(!Result || isl_set_is_equal(give(isl_map_domain(Result.copy())).keep(),
521
128
                                     Domain.keep()) == isl_bool_true);
522
128
  return Result;
523
128
}
524
525
1.04k
isl::set ZoneAlgorithm::getDomainFor(ScopStmt *Stmt) const {
526
1.04k
  return Stmt->getDomain().remove_redundancies();
527
1.04k
}
528
529
593
isl::set ZoneAlgorithm::getDomainFor(MemoryAccess *MA) const {
530
593
  return getDomainFor(MA->getStatement());
531
593
}
532
533
305
isl::map ZoneAlgorithm::getAccessRelationFor(MemoryAccess *MA) const {
534
305
  auto Domain = getDomainFor(MA);
535
305
  auto AccRel = MA->getLatestAccessRelation();
536
305
  return give(isl_map_intersect_domain(AccRel.take(), Domain.take()));
537
305
}
538
539
186
isl::map ZoneAlgorithm::getScalarReachingDefinition(ScopStmt *Stmt) {
540
186
  auto &Result = ScalarReachDefZone[Stmt];
541
186
  if (Result)
542
116
    return Result;
543
70
544
70
  auto Domain = getDomainFor(Stmt);
545
70
  Result = computeScalarReachingDefinition(Schedule, Domain, false, true);
546
70
  simplify(Result);
547
70
548
70
  return Result;
549
70
}
550
551
91
isl::map ZoneAlgorithm::getScalarReachingDefinition(isl::set DomainDef) {
552
91
  auto DomId = give(isl_set_get_tuple_id(DomainDef.keep()));
553
91
  auto *Stmt = static_cast<ScopStmt *>(isl_id_get_user(DomId.keep()));
554
91
555
91
  auto StmtResult = getScalarReachingDefinition(Stmt);
556
91
557
91
  return give(isl_map_intersect_range(StmtResult.take(), DomainDef.take()));
558
91
}
559
560
15
isl::map ZoneAlgorithm::makeUnknownForDomain(ScopStmt *Stmt) const {
561
15
  return ::makeUnknownForDomain(getDomainFor(Stmt));
562
15
}
563
564
214
isl::id ZoneAlgorithm::makeValueId(Value *V) {
565
214
  if (!V)
566
0
    return nullptr;
567
214
568
214
  auto &Id = ValueIds[V];
569
214
  if (
Id.is_null()214
) {
570
121
    auto Name = getIslCompatibleName("Val_", V, ValueIds.size() - 1,
571
121
                                     std::string(), UseInstructionNames);
572
121
    Id = give(isl_id_alloc(IslCtx.get(), Name.c_str(), V));
573
121
  }
574
214
  return Id;
575
214
}
576
577
214
isl::space ZoneAlgorithm::makeValueSpace(Value *V) {
578
214
  auto Result = give(isl_space_set_from_params(ParamSpace.copy()));
579
214
  return give(isl_space_set_tuple_id(Result.take(), isl_dim_set,
580
214
                                     makeValueId(V).take()));
581
214
}
582
583
214
isl::set ZoneAlgorithm::makeValueSet(Value *V) {
584
214
  auto Space = makeValueSpace(V);
585
214
  return give(isl_set_universe(Space.take()));
586
214
}
587
588
isl::map ZoneAlgorithm::makeValInst(Value *Val, ScopStmt *UserStmt, Loop *Scope,
589
219
                                    bool IsCertain) {
590
219
  // If the definition/write is conditional, the value at the location could
591
219
  // be either the written value or the old value. Since we cannot know which
592
219
  // one, consider the value to be unknown.
593
219
  if (!IsCertain)
594
2
    return makeUnknownForDomain(UserStmt);
595
217
596
217
  auto DomainUse = getDomainFor(UserStmt);
597
217
  auto VUse = VirtualUse::create(S, UserStmt, Scope, Val, true);
598
217
  switch (VUse.getKind()) {
599
37
  case VirtualUse::Constant:
600
37
  case VirtualUse::Block:
601
37
  case VirtualUse::Hoisted:
602
37
  case VirtualUse::ReadOnly: {
603
37
    // The definition does not depend on the statement which uses it.
604
37
    auto ValSet = makeValueSet(Val);
605
37
    return give(isl_map_from_domain_and_range(DomainUse.take(), ValSet.take()));
606
37
  }
607
37
608
2
  case VirtualUse::Synthesizable: {
609
2
    auto *ScevExpr = VUse.getScevExpr();
610
2
    auto UseDomainSpace = give(isl_set_get_space(DomainUse.keep()));
611
2
612
2
    // Construct the SCEV space.
613
2
    // TODO: Add only the induction variables referenced in SCEVAddRecExpr
614
2
    // expressions, not just all of them.
615
2
    auto ScevId = give(isl_id_alloc(UseDomainSpace.get_ctx().get(), nullptr,
616
2
                                    const_cast<SCEV *>(ScevExpr)));
617
2
    auto ScevSpace =
618
2
        give(isl_space_drop_dims(UseDomainSpace.copy(), isl_dim_set, 0, 0));
619
2
    ScevSpace = give(
620
2
        isl_space_set_tuple_id(ScevSpace.take(), isl_dim_set, ScevId.copy()));
621
2
622
2
    // { DomainUse[] -> ScevExpr[] }
623
2
    auto ValInst = give(isl_map_identity(isl_space_map_from_domain_and_range(
624
2
        UseDomainSpace.copy(), ScevSpace.copy())));
625
2
    return ValInst;
626
37
  }
627
37
628
86
  case VirtualUse::Intra: {
629
86
    // Definition and use is in the same statement. We do not need to compute
630
86
    // a reaching definition.
631
86
632
86
    // { llvm::Value }
633
86
    auto ValSet = makeValueSet(Val);
634
86
635
86
    // {  UserDomain[] -> llvm::Value }
636
86
    auto ValInstSet =
637
86
        give(isl_map_from_domain_and_range(DomainUse.take(), ValSet.take()));
638
86
639
86
    // { UserDomain[] -> [UserDomain[] - >llvm::Value] }
640
86
    auto Result = give(isl_map_reverse(isl_map_domain_map(ValInstSet.take())));
641
86
    simplify(Result);
642
86
    return Result;
643
37
  }
644
37
645
92
  case VirtualUse::Inter: {
646
92
    // The value is defined in a different statement.
647
92
648
92
    auto *Inst = cast<Instruction>(Val);
649
92
    auto *ValStmt = S->getStmtFor(Inst);
650
92
651
92
    // If the llvm::Value is defined in a removed Stmt, we cannot derive its
652
92
    // domain. We could use an arbitrary statement, but this could result in
653
92
    // different ValInst[] for the same llvm::Value.
654
92
    if (!ValStmt)
655
1
      return ::makeUnknownForDomain(DomainUse);
656
91
657
91
    // { DomainDef[] }
658
91
    auto DomainDef = getDomainFor(ValStmt);
659
91
660
91
    // { Scatter[] -> DomainDef[] }
661
91
    auto ReachDef = getScalarReachingDefinition(DomainDef);
662
91
663
91
    // { DomainUse[] -> Scatter[] }
664
91
    auto UserSched = getScatterFor(DomainUse);
665
91
666
91
    // { DomainUse[] -> DomainDef[] }
667
91
    auto UsedInstance =
668
91
        give(isl_map_apply_range(UserSched.take(), ReachDef.take()));
669
91
670
91
    // { llvm::Value }
671
91
    auto ValSet = makeValueSet(Val);
672
91
673
91
    // { DomainUse[] -> llvm::Value[] }
674
91
    auto ValInstSet =
675
91
        give(isl_map_from_domain_and_range(DomainUse.take(), ValSet.take()));
676
91
677
91
    // { DomainUse[] -> [DomainDef[] -> llvm::Value]  }
678
91
    auto Result =
679
91
        give(isl_map_range_product(UsedInstance.take(), ValInstSet.take()));
680
91
681
91
    simplify(Result);
682
91
    return Result;
683
91
  }
684
0
  }
685
0
  
llvm_unreachable0
("Unhandled use type");
686
0
}
687
688
0
bool ZoneAlgorithm::isCompatibleAccess(MemoryAccess *MA) {
689
0
  if (!MA)
690
0
    return false;
691
0
  
if (0
!MA->isLatestArrayKind()0
)
692
0
    return false;
693
0
  Instruction *AccInst = MA->getAccessInstruction();
694
0
  return isa<StoreInst>(AccInst) || isa<LoadInst>(AccInst);
695
0
}
696
697
64
void ZoneAlgorithm::computeCommon() {
698
64
  AllReads = makeEmptyUnionMap();
699
64
  AllMayWrites = makeEmptyUnionMap();
700
64
  AllMustWrites = makeEmptyUnionMap();
701
64
  AllWriteValInst = makeEmptyUnionMap();
702
64
  AllReadValInst = makeEmptyUnionMap();
703
64
704
230
  for (auto &Stmt : *S) {
705
460
    for (auto *MA : Stmt) {
706
460
      if (!MA->isLatestArrayKind())
707
344
        continue;
708
116
709
116
      
if (116
MA->isRead()116
)
710
25
        addArrayReadAccess(MA);
711
116
712
116
      if (MA->isWrite())
713
91
        addArrayWriteAccess(MA);
714
460
    }
715
230
  }
716
64
717
64
  // { DomainWrite[] -> Element[] }
718
64
  AllWrites =
719
64
      give(isl_union_map_union(AllMustWrites.copy(), AllMayWrites.copy()));
720
64
721
64
  // { [Element[] -> Zone[]] -> DomainWrite[] }
722
64
  WriteReachDefZone =
723
64
      computeReachingDefinition(Schedule, AllWrites, false, true);
724
64
  simplify(WriteReachDefZone);
725
64
}
726
727
18
void ZoneAlgorithm::printAccesses(llvm::raw_ostream &OS, int Indent) const {
728
18
  OS.indent(Indent) << "After accesses {\n";
729
87
  for (auto &Stmt : *S) {
730
87
    OS.indent(Indent + 4) << Stmt.getBaseName() << "\n";
731
87
    for (auto *MA : Stmt)
732
175
      MA->print(OS);
733
87
  }
734
18
  OS.indent(Indent) << "}\n";
735
18
}
736
737
64
isl::union_map ZoneAlgorithm::computeKnownFromMustWrites() const {
738
64
  // { [Element[] -> Zone[]] -> [Element[] -> DomainWrite[]] }
739
64
  isl::union_map EltReachdDef = distributeDomain(WriteReachDefZone.curry());
740
64
741
64
  // { [Element[] -> DomainWrite[]] -> ValInst[] }
742
64
  isl::union_map AllKnownWriteValInst = filterKnownValInst(AllWriteValInst);
743
64
744
64
  // { [Element[] -> Zone[]] -> ValInst[] }
745
64
  return EltReachdDef.apply_range(AllKnownWriteValInst);
746
64
}
747
748
28
isl::union_map ZoneAlgorithm::computeKnownFromLoad() const {
749
28
  // { Element[] }
750
28
  isl::union_set AllAccessedElts = AllReads.range().unite(AllWrites.range());
751
28
752
28
  // { Element[] -> Scatter[] }
753
28
  isl::union_map EltZoneUniverse = isl::union_map::from_domain_and_range(
754
28
      AllAccessedElts, isl::set::universe(ScatterSpace));
755
28
756
28
  // This assumes there are no "holes" in
757
28
  // isl_union_map_domain(WriteReachDefZone); alternatively, compute the zone
758
28
  // before the first write or that are not written at all.
759
28
  // { Element[] -> Scatter[] }
760
28
  isl::union_set NonReachDef =
761
28
      EltZoneUniverse.wrap().subtract(WriteReachDefZone.domain());
762
28
763
28
  // { [Element[] -> Zone[]] -> ReachDefId[] }
764
28
  isl::union_map DefZone =
765
28
      WriteReachDefZone.unite(isl::union_map::from_domain(NonReachDef));
766
28
767
28
  // { [Element[] -> Scatter[]] -> Element[] }
768
28
  isl::union_map EltZoneElt = EltZoneUniverse.domain_map();
769
28
770
28
  // { [Element[] -> Zone[]] -> [Element[] -> ReachDefId[]] }
771
28
  isl::union_map DefZoneEltDefId = EltZoneElt.range_product(DefZone);
772
28
773
28
  // { Element[] -> [Zone[] -> ReachDefId[]] }
774
28
  isl::union_map EltDefZone = DefZone.curry();
775
28
776
28
  // { [Element[] -> Zone[] -> [Element[] -> ReachDefId[]] }
777
28
  isl::union_map EltZoneEltDefid = distributeDomain(EltDefZone);
778
28
779
28
  // { [Element[] -> Scatter[]] -> DomainRead[] }
780
28
  isl::union_map Reads = AllReads.range_product(Schedule).reverse();
781
28
782
28
  // { [Element[] -> Scatter[]] -> [Element[] -> DomainRead[]] }
783
28
  isl::union_map ReadsElt = EltZoneElt.range_product(Reads);
784
28
785
28
  // { [Element[] -> Scatter[]] -> ValInst[] }
786
28
  isl::union_map ScatterKnown = ReadsElt.apply_range(AllReadValInst);
787
28
788
28
  // { [Element[] -> ReachDefId[]] -> ValInst[] }
789
28
  isl::union_map DefidKnown =
790
28
      DefZoneEltDefId.apply_domain(ScatterKnown).reverse();
791
28
792
28
  // { [Element[] -> Zone[]] -> ValInst[] }
793
28
  return DefZoneEltDefId.apply_range(DefidKnown);
794
28
}
795
796
isl::union_map ZoneAlgorithm::computeKnown(bool FromWrite,
797
64
                                           bool FromRead) const {
798
64
  isl::union_map Result = makeEmptyUnionMap();
799
64
800
64
  if (FromWrite)
801
64
    Result = Result.unite(computeKnownFromMustWrites());
802
64
803
64
  if (FromRead)
804
28
    Result = Result.unite(computeKnownFromLoad());
805
64
806
64
  simplify(Result);
807
64
  return Result;
808
64
}