Coverage Report

Created: 2017-11-21 16:49

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/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
#include "llvm/Support/raw_ostream.h"
159
160
#define DEBUG_TYPE "polly-zone"
161
162
STATISTIC(NumIncompatibleArrays, "Number of not zone-analyzable arrays");
163
STATISTIC(NumCompatibleArrays, "Number of zone-analyzable arrays");
164
STATISTIC(NumRecursivePHIs, "Number of recursive PHIs");
165
STATISTIC(NumNormalizablePHIs, "Number of normalizable PHIs");
166
STATISTIC(NumPHINormialization, "Number of PHI executed normalizations");
167
168
using namespace polly;
169
using namespace llvm;
170
171
static isl::union_map computeReachingDefinition(isl::union_map Schedule,
172
                                                isl::union_map Writes,
173
59
                                                bool InclDef, bool InclRedef) {
174
59
  return computeReachingWrite(Schedule, Writes, false, InclDef, InclRedef);
175
59
}
176
177
/// Compute the reaching definition of a scalar.
178
///
179
/// Compared to computeReachingDefinition, there is just one element which is
180
/// accessed and therefore only a set if instances that accesses that element is
181
/// required.
182
///
183
/// @param Schedule  { DomainWrite[] -> Scatter[] }
184
/// @param Writes    { DomainWrite[] }
185
/// @param InclDef   Include the timepoint of the definition to the result.
186
/// @param InclRedef Include the timepoint of the overwrite into the result.
187
///
188
/// @return { Scatter[] -> DomainWrite[] }
189
static isl::union_map computeScalarReachingDefinition(isl::union_map Schedule,
190
                                                      isl::union_set Writes,
191
                                                      bool InclDef,
192
34
                                                      bool InclRedef) {
193
34
  // { DomainWrite[] -> Element[] }
194
34
  isl::union_map Defs = isl::union_map::from_domain(Writes);
195
34
196
34
  // { [Element[] -> Scatter[]] -> DomainWrite[] }
197
34
  auto ReachDefs =
198
34
      computeReachingDefinition(Schedule, Defs, InclDef, InclRedef);
199
34
200
34
  // { Scatter[] -> DomainWrite[] }
201
34
  return ReachDefs.curry().range().unwrap();
202
34
}
203
204
/// Compute the reaching definition of a scalar.
205
///
206
/// This overload accepts only a single writing statement as an isl_map,
207
/// consequently the result also is only a single isl_map.
208
///
209
/// @param Schedule  { DomainWrite[] -> Scatter[] }
210
/// @param Writes    { DomainWrite[] }
211
/// @param InclDef   Include the timepoint of the definition to the result.
212
/// @param InclRedef Include the timepoint of the overwrite into the result.
213
///
214
/// @return { Scatter[] -> DomainWrite[] }
215
static isl::map computeScalarReachingDefinition(isl::union_map Schedule,
216
                                                isl::set Writes, bool InclDef,
217
34
                                                bool InclRedef) {
218
34
  isl::space DomainSpace = Writes.get_space();
219
34
  isl::space ScatterSpace = getScatterSpace(Schedule);
220
34
221
34
  //  { Scatter[] -> DomainWrite[] }
222
34
  isl::union_map UMap = computeScalarReachingDefinition(
223
34
      Schedule, isl::union_set(Writes), InclDef, InclRedef);
224
34
225
34
  isl::space ResultSpace = ScatterSpace.map_from_domain_and_range(DomainSpace);
226
34
  return singleton(UMap, ResultSpace);
227
34
}
228
229
546
isl::union_map polly::makeUnknownForDomain(isl::union_set Domain) {
230
546
  return give(isl_union_map_from_domain(Domain.take()));
231
546
}
232
233
/// Create a domain-to-unknown value mapping.
234
///
235
/// @see makeUnknownForDomain(isl::union_set)
236
///
237
/// @param Domain { Domain[] }
238
///
239
/// @return { Domain[] -> ValInst[] }
240
3
static isl::map makeUnknownForDomain(isl::set Domain) {
241
3
  return give(isl_map_from_domain(Domain.take()));
242
3
}
243
244
/// Return whether @p Map maps to an unknown value.
245
///
246
/// @param { [] -> ValInst[] }
247
390
static bool isMapToUnknown(const isl::map &Map) {
248
390
  isl::space Space = Map.get_space().range();
249
390
  return Space.has_tuple_id(isl::dim::set).is_false() &&
250
390
         
Space.is_wrapping().is_false()259
&&
Space.dim(isl::dim::set) == 081
;
251
390
}
252
253
432
isl::union_map polly::filterKnownValInst(const isl::union_map &UMap) {
254
432
  isl::union_map Result = isl::union_map::empty(UMap.get_space());
255
432
  isl::stat Success = UMap.foreach_map([=, &Result](isl::map Map) -> isl::stat {
256
390
    if (!isMapToUnknown(Map))
257
309
      Result = Result.add_map(Map);
258
390
    return isl::stat::ok;
259
390
  });
260
432
  if (Success != isl::stat::ok)
261
0
    return {};
262
432
  return Result;
263
432
}
264
265
ZoneAlgorithm::ZoneAlgorithm(const char *PassName, Scop *S, LoopInfo *LI)
266
    : PassName(PassName), IslCtx(S->getSharedIslCtx()), S(S), LI(LI),
267
25
      Schedule(S->getSchedule()) {
268
25
  auto Domains = S->getDomains();
269
25
270
25
  Schedule =
271
25
      give(isl_union_map_intersect_domain(Schedule.take(), Domains.take()));
272
25
  ParamSpace = give(isl_union_map_get_space(Schedule.keep()));
273
25
  ScatterSpace = getScatterSpace(Schedule);
274
25
}
275
276
/// Check if all stores in @p Stmt store the very same value.
277
///
278
/// This covers a special situation occurring in Polybench's
279
/// covariance/correlation (which is typical for algorithms that cover symmetric
280
/// matrices):
281
///
282
/// for (int i = 0; i < n; i += 1)
283
///   for (int j = 0; j <= i; j += 1) {
284
///     double x = ...;
285
///     C[i][j] = x;
286
///     C[j][i] = x;
287
///   }
288
///
289
/// For i == j, the same value is written twice to the same element.Double
290
/// writes to the same element are not allowed in DeLICM because its algorithm
291
/// does not see which of the writes is effective.But if its the same value
292
/// anyway, it doesn't matter.
293
///
294
/// LLVM passes, however, cannot simplify this because the write is necessary
295
/// for i != j (unless it would add a condition for one of the writes to occur
296
/// only if i != j).
297
///
298
/// TODO: In the future we may want to extent this to make the checks
299
///       specific to different memory locations.
300
0
static bool onlySameValueWrites(ScopStmt *Stmt) {
301
0
  Value *V = nullptr;
302
0
303
0
  for (auto *MA : *Stmt) {
304
0
    if (!MA->isLatestArrayKind() || !MA->isMustWrite() ||
305
0
        !MA->isOriginalArrayKind())
306
0
      continue;
307
0
308
0
    if (!V) {
309
0
      V = MA->getAccessValue();
310
0
      continue;
311
0
    }
312
0
313
0
    if (V != MA->getAccessValue())
314
0
      return false;
315
0
  }
316
0
  return true;
317
0
}
318
319
void ZoneAlgorithm::collectIncompatibleElts(ScopStmt *Stmt,
320
                                            isl::union_set &IncompatibleElts,
321
102
                                            isl::union_set &AllElts) {
322
102
  auto Stores = makeEmptyUnionMap();
323
102
  auto Loads = makeEmptyUnionMap();
324
102
325
102
  // This assumes that the MemoryKind::Array MemoryAccesses are iterated in
326
102
  // order.
327
199
  for (auto *MA : *Stmt) {
328
199
    if (!MA->isOriginalArrayKind())
329
160
      continue;
330
39
331
39
    isl::map AccRelMap = getAccessRelationFor(MA);
332
39
    isl::union_map AccRel = AccRelMap;
333
39
334
39
    // To avoid solving any ILP problems, always add entire arrays instead of
335
39
    // just the elements that are accessed.
336
39
    auto ArrayElts = isl::set::universe(AccRelMap.get_space().range());
337
39
    AllElts = AllElts.add_set(ArrayElts);
338
39
339
39
    if (MA->isRead()) {
340
9
      // Reject load after store to same location.
341
9
      if (!isl_union_map_is_disjoint(Stores.keep(), AccRel.keep())) {
342
0
        DEBUG(dbgs() << "Load after store of same element in same statement\n");
343
0
        OptimizationRemarkMissed R(PassName, "LoadAfterStore",
344
0
                                   MA->getAccessInstruction());
345
0
        R << "load after store of same element in same statement";
346
0
        R << " (previous stores: " << Stores;
347
0
        R << ", loading: " << AccRel << ")";
348
0
        S->getFunction().getContext().diagnose(R);
349
0
350
0
        IncompatibleElts = IncompatibleElts.add_set(ArrayElts);
351
0
      }
352
9
353
9
      Loads = give(isl_union_map_union(Loads.take(), AccRel.take()));
354
9
355
9
      continue;
356
9
    }
357
30
358
30
    // In region statements the order is less clear, eg. the load and store
359
30
    // might be in a boxed loop.
360
30
    if (Stmt->isRegionStmt() &&
361
30
        
!isl_union_map_is_disjoint(Loads.keep(), AccRel.keep())1
) {
362
1
      DEBUG(dbgs() << "WRITE in non-affine subregion not supported\n");
363
1
      OptimizationRemarkMissed R(PassName, "StoreInSubregion",
364
1
                                 MA->getAccessInstruction());
365
1
      R << "store is in a non-affine subregion";
366
1
      S->getFunction().getContext().diagnose(R);
367
1
368
1
      IncompatibleElts = IncompatibleElts.add_set(ArrayElts);
369
1
    }
370
30
371
30
    // Do not allow more than one store to the same location.
372
30
    if (!isl_union_map_is_disjoint(Stores.keep(), AccRel.keep()) &&
373
30
        
!onlySameValueWrites(Stmt)0
) {
374
0
      DEBUG(dbgs() << "WRITE after WRITE to same element\n");
375
0
      OptimizationRemarkMissed R(PassName, "StoreAfterStore",
376
0
                                 MA->getAccessInstruction());
377
0
      R << "store after store of same element in same statement";
378
0
      R << " (previous stores: " << Stores;
379
0
      R << ", storing: " << AccRel << ")";
380
0
      S->getFunction().getContext().diagnose(R);
381
0
382
0
      IncompatibleElts = IncompatibleElts.add_set(ArrayElts);
383
0
    }
384
199
385
199
    Stores = give(isl_union_map_union(Stores.take(), AccRel.take()));
386
199
  }
387
102
}
388
389
10
void ZoneAlgorithm::addArrayReadAccess(MemoryAccess *MA) {
390
10
  assert(MA->isLatestArrayKind());
391
10
  assert(MA->isRead());
392
10
  ScopStmt *Stmt = MA->getStatement();
393
10
394
10
  // { DomainRead[] -> Element[] }
395
10
  auto AccRel = intersectRange(getAccessRelationFor(MA), CompatibleElts);
396
10
  AllReads = give(isl_union_map_add_map(AllReads.take(), AccRel.copy()));
397
10
398
10
  if (LoadInst *Load = dyn_cast_or_null<LoadInst>(MA->getAccessInstruction())) {
399
9
    // { DomainRead[] -> ValInst[] }
400
9
    isl::map LoadValInst = makeValInst(
401
9
        Load, Stmt, LI->getLoopFor(Load->getParent()), Stmt->isBlockStmt());
402
9
403
9
    // { DomainRead[] -> [Element[] -> DomainRead[]] }
404
9
    isl::map IncludeElement =
405
9
        give(isl_map_curry(isl_map_domain_map(AccRel.take())));
406
9
407
9
    // { [Element[] -> DomainRead[]] -> ValInst[] }
408
9
    isl::map EltLoadValInst =
409
9
        give(isl_map_apply_domain(LoadValInst.take(), IncludeElement.take()));
410
9
411
9
    AllReadValInst = give(
412
9
        isl_union_map_add_map(AllReadValInst.take(), EltLoadValInst.take()));
413
9
  }
414
10
}
415
416
isl::union_map ZoneAlgorithm::getWrittenValue(MemoryAccess *MA,
417
30
                                              isl::map AccRel) {
418
30
  if (!MA->isMustWrite())
419
1
    return {};
420
29
421
29
  Value *AccVal = MA->getAccessValue();
422
29
  ScopStmt *Stmt = MA->getStatement();
423
29
  Instruction *AccInst = MA->getAccessInstruction();
424
29
425
29
  // Write a value to a single element.
426
29
  auto L = MA->isOriginalArrayKind() ? LI->getLoopFor(AccInst->getParent())
427
29
                                     : 
Stmt->getSurroundingLoop()0
;
428
29
  if (AccVal &&
429
29
      AccVal->getType() == MA->getLatestScopArrayInfo()->getElementType() &&
430
29
      AccRel.is_single_valued().is_true())
431
29
    return makeNormalizedValInst(AccVal, Stmt, L);
432
0
433
0
  // memset(_, '0', ) is equivalent to writing the null value to all touched
434
0
  // elements. isMustWrite() ensures that all of an element's bytes are
435
0
  // overwritten.
436
0
  if (auto *Memset = dyn_cast<MemSetInst>(AccInst)) {
437
0
    auto *WrittenConstant = dyn_cast<Constant>(Memset->getValue());
438
0
    Type *Ty = MA->getLatestScopArrayInfo()->getElementType();
439
0
    if (WrittenConstant && WrittenConstant->isZeroValue()) {
440
0
      Constant *Zero = Constant::getNullValue(Ty);
441
0
      return makeNormalizedValInst(Zero, Stmt, L);
442
0
    }
443
0
  }
444
0
445
0
  return {};
446
0
}
447
448
30
void ZoneAlgorithm::addArrayWriteAccess(MemoryAccess *MA) {
449
30
  assert(MA->isLatestArrayKind());
450
30
  assert(MA->isWrite());
451
30
  auto *Stmt = MA->getStatement();
452
30
453
30
  // { Domain[] -> Element[] }
454
30
  isl::map AccRel = intersectRange(getAccessRelationFor(MA), CompatibleElts);
455
30
456
30
  if (MA->isMustWrite())
457
29
    AllMustWrites = AllMustWrites.add_map(AccRel);
458
30
459
30
  if (MA->isMayWrite())
460
1
    AllMayWrites = AllMayWrites.add_map(AccRel);
461
30
462
30
  // { Domain[] -> ValInst[] }
463
30
  isl::union_map WriteValInstance = getWrittenValue(MA, AccRel);
464
30
  if (!WriteValInstance)
465
1
    WriteValInstance = makeUnknownForDomain(Stmt);
466
30
467
30
  // { Domain[] -> [Element[] -> Domain[]] }
468
30
  isl::map IncludeElement = AccRel.domain_map().curry();
469
30
470
30
  // { [Element[] -> DomainWrite[]] -> ValInst[] }
471
30
  isl::union_map EltWriteValInst =
472
30
      WriteValInstance.apply_domain(IncludeElement);
473
30
474
30
  AllWriteValInst = AllWriteValInst.unite(EltWriteValInst);
475
30
}
476
477
/// Return whether @p PHI refers (also transitively through other PHIs) to
478
/// itself.
479
///
480
/// loop:
481
///   %phi1 = phi [0, %preheader], [%phi1, %loop]
482
///   br i1 %c, label %loop, label %exit
483
///
484
/// exit:
485
///   %phi2 = phi [%phi1, %bb]
486
///
487
/// In this example, %phi1 is recursive, but %phi2 is not.
488
0
static bool isRecursivePHI(const PHINode *PHI) {
489
0
  SmallVector<const PHINode *, 8> Worklist;
490
0
  SmallPtrSet<const PHINode *, 8> Visited;
491
0
  Worklist.push_back(PHI);
492
0
493
0
  while (!Worklist.empty()) {
494
0
    const PHINode *Cur = Worklist.pop_back_val();
495
0
496
0
    if (Visited.count(Cur))
497
0
      continue;
498
0
    Visited.insert(Cur);
499
0
500
0
    for (const Use &Incoming : Cur->incoming_values()) {
501
0
      Value *IncomingVal = Incoming.get();
502
0
      auto *IncomingPHI = dyn_cast<PHINode>(IncomingVal);
503
0
      if (!IncomingPHI)
504
0
        continue;
505
0
506
0
      if (IncomingPHI == PHI)
507
0
        return true;
508
0
      Worklist.push_back(IncomingPHI);
509
0
    }
510
0
  }
511
0
  return false;
512
0
}
513
514
16
isl::union_map ZoneAlgorithm::computePerPHI(const ScopArrayInfo *SAI) {
515
16
  // TODO: If the PHI has an incoming block from before the SCoP, it is not
516
16
  // represented in any ScopStmt.
517
16
518
16
  auto *PHI = cast<PHINode>(SAI->getBasePtr());
519
16
  auto It = PerPHIMaps.find(PHI);
520
16
  if (It != PerPHIMaps.end())
521
0
    return It->second;
522
16
523
16
  assert(SAI->isPHIKind());
524
16
525
16
  // { DomainPHIWrite[] -> Scatter[] }
526
16
  isl::union_map PHIWriteScatter = makeEmptyUnionMap();
527
16
528
16
  // Collect all incoming block timepoints.
529
32
  for (MemoryAccess *MA : S->getPHIIncomings(SAI)) {
530
32
    isl::map Scatter = getScatterFor(MA);
531
32
    PHIWriteScatter = PHIWriteScatter.add_map(Scatter);
532
32
  }
533
16
534
16
  // { DomainPHIRead[] -> Scatter[] }
535
16
  isl::map PHIReadScatter = getScatterFor(S->getPHIRead(SAI));
536
16
537
16
  // { DomainPHIRead[] -> Scatter[] }
538
16
  isl::map BeforeRead = beforeScatter(PHIReadScatter, true);
539
16
540
16
  // { Scatter[] }
541
16
  isl::set WriteTimes = singleton(PHIWriteScatter.range(), ScatterSpace);
542
16
543
16
  // { DomainPHIRead[] -> Scatter[] }
544
16
  isl::map PHIWriteTimes = BeforeRead.intersect_range(WriteTimes);
545
16
  isl::map LastPerPHIWrites = PHIWriteTimes.lexmax();
546
16
547
16
  // { DomainPHIRead[] -> DomainPHIWrite[] }
548
16
  isl::union_map Result =
549
16
      isl::union_map(LastPerPHIWrites).apply_range(PHIWriteScatter.reverse());
550
16
  assert(!Result.is_single_valued().is_false());
551
16
  assert(!Result.is_injective().is_false());
552
16
553
16
  PerPHIMaps.insert({PHI, Result});
554
16
  return Result;
555
16
}
556
557
75
isl::union_set ZoneAlgorithm::makeEmptyUnionSet() const {
558
75
  return give(isl_union_set_empty(ParamSpace.copy()));
559
75
}
560
561
411
isl::union_map ZoneAlgorithm::makeEmptyUnionMap() const {
562
411
  return give(isl_union_map_empty(ParamSpace.copy()));
563
411
}
564
565
25
void ZoneAlgorithm::collectCompatibleElts() {
566
25
  // First find all the incompatible elements, then take the complement.
567
25
  // We compile the list of compatible (rather than incompatible) elements so
568
25
  // users can intersect with the list, not requiring a subtract operation. It
569
25
  // also allows us to define a 'universe' of all elements and makes it more
570
25
  // explicit in which array elements can be used.
571
25
  isl::union_set AllElts = makeEmptyUnionSet();
572
25
  isl::union_set IncompatibleElts = makeEmptyUnionSet();
573
25
574
25
  for (auto &Stmt : *S)
575
102
    collectIncompatibleElts(&Stmt, IncompatibleElts, AllElts);
576
25
577
25
  NumIncompatibleArrays += isl_union_set_n_set(IncompatibleElts.keep());
578
25
  CompatibleElts = AllElts.subtract(IncompatibleElts);
579
25
  NumCompatibleArrays += isl_union_set_n_set(CompatibleElts.keep());
580
25
}
581
582
102
isl::map ZoneAlgorithm::getScatterFor(ScopStmt *Stmt) const {
583
102
  isl::space ResultSpace = give(isl_space_map_from_domain_and_range(
584
102
      Stmt->getDomainSpace().release(), ScatterSpace.copy()));
585
102
  return give(isl_union_map_extract_map(Schedule.keep(), ResultSpace.take()));
586
102
}
587
588
90
isl::map ZoneAlgorithm::getScatterFor(MemoryAccess *MA) const {
589
90
  return getScatterFor(MA->getStatement());
590
90
}
591
592
101
isl::union_map ZoneAlgorithm::getScatterFor(isl::union_set Domain) const {
593
101
  return give(isl_union_map_intersect_domain(Schedule.copy(), Domain.take()));
594
101
}
595
596
66
isl::map ZoneAlgorithm::getScatterFor(isl::set Domain) const {
597
66
  auto ResultSpace = give(isl_space_map_from_domain_and_range(
598
66
      isl_set_get_space(Domain.keep()), ScatterSpace.copy()));
599
66
  auto UDomain = give(isl_union_set_from_set(Domain.copy()));
600
66
  auto UResult = getScatterFor(std::move(UDomain));
601
66
  auto Result = singleton(std::move(UResult), std::move(ResultSpace));
602
66
  assert(!Result || isl_set_is_equal(give(isl_map_domain(Result.copy())).keep(),
603
66
                                     Domain.keep()) == isl_bool_true);
604
66
  return Result;
605
66
}
606
607
516
isl::set ZoneAlgorithm::getDomainFor(ScopStmt *Stmt) const {
608
516
  return Stmt->getDomain().remove_redundancies();
609
516
}
610
611
309
isl::set ZoneAlgorithm::getDomainFor(MemoryAccess *MA) const {
612
309
  return getDomainFor(MA->getStatement());
613
309
}
614
615
115
isl::map ZoneAlgorithm::getAccessRelationFor(MemoryAccess *MA) const {
616
115
  auto Domain = getDomainFor(MA);
617
115
  auto AccRel = MA->getLatestAccessRelation();
618
115
  return give(isl_map_intersect_domain(AccRel.take(), Domain.take()));
619
115
}
620
621
78
isl::map ZoneAlgorithm::getScalarReachingDefinition(ScopStmt *Stmt) {
622
78
  auto &Result = ScalarReachDefZone[Stmt];
623
78
  if (Result)
624
44
    return Result;
625
34
626
34
  auto Domain = getDomainFor(Stmt);
627
34
  Result = computeScalarReachingDefinition(Schedule, Domain, false, true);
628
34
  simplify(Result);
629
34
630
34
  return Result;
631
34
}
632
633
41
isl::map ZoneAlgorithm::getScalarReachingDefinition(isl::set DomainDef) {
634
41
  auto DomId = give(isl_set_get_tuple_id(DomainDef.keep()));
635
41
  auto *Stmt = static_cast<ScopStmt *>(isl_id_get_user(DomId.keep()));
636
41
637
41
  auto StmtResult = getScalarReachingDefinition(Stmt);
638
41
639
41
  return give(isl_map_intersect_range(StmtResult.take(), DomainDef.take()));
640
41
}
641
642
2
isl::map ZoneAlgorithm::makeUnknownForDomain(ScopStmt *Stmt) const {
643
2
  return ::makeUnknownForDomain(getDomainFor(Stmt));
644
2
}
645
646
102
isl::id ZoneAlgorithm::makeValueId(Value *V) {
647
102
  if (!V)
648
0
    return nullptr;
649
102
650
102
  auto &Id = ValueIds[V];
651
102
  if (Id.is_null()) {
652
56
    auto Name = getIslCompatibleName("Val_", V, ValueIds.size() - 1,
653
56
                                     std::string(), UseInstructionNames);
654
56
    Id = give(isl_id_alloc(IslCtx.get(), Name.c_str(), V));
655
56
  }
656
102
  return Id;
657
102
}
658
659
102
isl::space ZoneAlgorithm::makeValueSpace(Value *V) {
660
102
  auto Result = give(isl_space_set_from_params(ParamSpace.copy()));
661
102
  return give(isl_space_set_tuple_id(Result.take(), isl_dim_set,
662
102
                                     makeValueId(V).take()));
663
102
}
664
665
102
isl::set ZoneAlgorithm::makeValueSet(Value *V) {
666
102
  auto Space = makeValueSpace(V);
667
102
  return give(isl_set_universe(Space.take()));
668
102
}
669
670
isl::map ZoneAlgorithm::makeValInst(Value *Val, ScopStmt *UserStmt, Loop *Scope,
671
105
                                    bool IsCertain) {
672
105
  // If the definition/write is conditional, the value at the location could
673
105
  // be either the written value or the old value. Since we cannot know which
674
105
  // one, consider the value to be unknown.
675
105
  if (!IsCertain)
676
1
    return makeUnknownForDomain(UserStmt);
677
104
678
104
  auto DomainUse = getDomainFor(UserStmt);
679
104
  auto VUse = VirtualUse::create(S, UserStmt, Scope, Val, true);
680
104
  switch (VUse.getKind()) {
681
104
  case VirtualUse::Constant:
682
13
  case VirtualUse::Block:
683
13
  case VirtualUse::Hoisted:
684
13
  case VirtualUse::ReadOnly: {
685
13
    // The definition does not depend on the statement which uses it.
686
13
    auto ValSet = makeValueSet(Val);
687
13
    return give(isl_map_from_domain_and_range(DomainUse.take(), ValSet.take()));
688
13
  }
689
13
690
13
  case VirtualUse::Synthesizable: {
691
1
    auto *ScevExpr = VUse.getScevExpr();
692
1
    auto UseDomainSpace = give(isl_set_get_space(DomainUse.keep()));
693
1
694
1
    // Construct the SCEV space.
695
1
    // TODO: Add only the induction variables referenced in SCEVAddRecExpr
696
1
    // expressions, not just all of them.
697
1
    auto ScevId = give(isl_id_alloc(UseDomainSpace.get_ctx().get(), nullptr,
698
1
                                    const_cast<SCEV *>(ScevExpr)));
699
1
    auto ScevSpace =
700
1
        give(isl_space_drop_dims(UseDomainSpace.copy(), isl_dim_set, 0, 0));
701
1
    ScevSpace = give(
702
1
        isl_space_set_tuple_id(ScevSpace.take(), isl_dim_set, ScevId.copy()));
703
1
704
1
    // { DomainUse[] -> ScevExpr[] }
705
1
    auto ValInst = give(isl_map_identity(isl_space_map_from_domain_and_range(
706
1
        UseDomainSpace.copy(), ScevSpace.copy())));
707
1
    return ValInst;
708
13
  }
709
13
710
48
  case VirtualUse::Intra: {
711
48
    // Definition and use is in the same statement. We do not need to compute
712
48
    // a reaching definition.
713
48
714
48
    // { llvm::Value }
715
48
    auto ValSet = makeValueSet(Val);
716
48
717
48
    // {  UserDomain[] -> llvm::Value }
718
48
    auto ValInstSet =
719
48
        give(isl_map_from_domain_and_range(DomainUse.take(), ValSet.take()));
720
48
721
48
    // { UserDomain[] -> [UserDomain[] - >llvm::Value] }
722
48
    auto Result = give(isl_map_reverse(isl_map_domain_map(ValInstSet.take())));
723
48
    simplify(Result);
724
48
    return Result;
725
13
  }
726
13
727
42
  case VirtualUse::Inter: {
728
42
    // The value is defined in a different statement.
729
42
730
42
    auto *Inst = cast<Instruction>(Val);
731
42
    auto *ValStmt = S->getStmtFor(Inst);
732
42
733
42
    // If the llvm::Value is defined in a removed Stmt, we cannot derive its
734
42
    // domain. We could use an arbitrary statement, but this could result in
735
42
    // different ValInst[] for the same llvm::Value.
736
42
    if (!ValStmt)
737
1
      return ::makeUnknownForDomain(DomainUse);
738
41
739
41
    // { DomainDef[] }
740
41
    auto DomainDef = getDomainFor(ValStmt);
741
41
742
41
    // { Scatter[] -> DomainDef[] }
743
41
    auto ReachDef = getScalarReachingDefinition(DomainDef);
744
41
745
41
    // { DomainUse[] -> Scatter[] }
746
41
    auto UserSched = getScatterFor(DomainUse);
747
41
748
41
    // { DomainUse[] -> DomainDef[] }
749
41
    auto UsedInstance =
750
41
        give(isl_map_apply_range(UserSched.take(), ReachDef.take()));
751
41
752
41
    // { llvm::Value }
753
41
    auto ValSet = makeValueSet(Val);
754
41
755
41
    // { DomainUse[] -> llvm::Value[] }
756
41
    auto ValInstSet =
757
41
        give(isl_map_from_domain_and_range(DomainUse.take(), ValSet.take()));
758
41
759
41
    // { DomainUse[] -> [DomainDef[] -> llvm::Value]  }
760
41
    auto Result =
761
41
        give(isl_map_range_product(UsedInstance.take(), ValInstSet.take()));
762
41
763
41
    simplify(Result);
764
41
    return Result;
765
41
  }
766
0
  }
767
0
  llvm_unreachable("Unhandled use type");
768
0
}
769
770
/// Remove all computed PHIs out of @p Input and replace by their incoming
771
/// value.
772
///
773
/// @param Input        { [] -> ValInst[] }
774
/// @param ComputedPHIs Set of PHIs that are replaced. Its ValInst must appear
775
///                     on the LHS of @p NormalizeMap.
776
/// @param NormalizeMap { ValInst[] -> ValInst[] }
777
static isl::union_map normalizeValInst(isl::union_map Input,
778
                                       const DenseSet<PHINode *> &ComputedPHIs,
779
32
                                       isl::union_map NormalizeMap) {
780
32
  isl::union_map Result = isl::union_map::empty(Input.get_space());
781
32
  Input.foreach_map(
782
32
      [&Result, &ComputedPHIs, &NormalizeMap](isl::map Map) -> isl::stat {
783
32
        isl::space Space = Map.get_space();
784
32
        isl::space RangeSpace = Space.range();
785
32
786
32
        // Instructions within the SCoP are always wrapped. Non-wrapped tuples
787
32
        // are therefore invariant in the SCoP and don't need normalization.
788
32
        if (!RangeSpace.is_wrapping()) {
789
4
          Result = Result.add_map(Map);
790
4
          return isl::stat::ok;
791
4
        }
792
28
793
28
        auto *PHI = dyn_cast<PHINode>(static_cast<Value *>(
794
28
            RangeSpace.unwrap().get_tuple_id(isl::dim::out).get_user()));
795
28
796
28
        // If no normalization is necessary, then the ValInst stands for itself.
797
28
        if (!ComputedPHIs.count(PHI)) {
798
28
          Result = Result.add_map(Map);
799
28
          return isl::stat::ok;
800
28
        }
801
0
802
0
        // Otherwise, apply the normalization.
803
0
        isl::union_map Mapped = isl::union_map(Map).apply_range(NormalizeMap);
804
0
        Result = Result.unite(Mapped);
805
0
        NumPHINormialization++;
806
0
        return isl::stat::ok;
807
0
      });
808
32
  return Result;
809
32
}
810
811
isl::union_map ZoneAlgorithm::makeNormalizedValInst(llvm::Value *Val,
812
                                                    ScopStmt *UserStmt,
813
                                                    llvm::Loop *Scope,
814
32
                                                    bool IsCertain) {
815
32
  isl::map ValInst = makeValInst(Val, UserStmt, Scope, IsCertain);
816
32
  isl::union_map Normalized =
817
32
      normalizeValInst(ValInst, ComputedPHIs, NormalizeMap);
818
32
  return Normalized;
819
32
}
820
821
0
bool ZoneAlgorithm::isCompatibleAccess(MemoryAccess *MA) {
822
0
  if (!MA)
823
0
    return false;
824
0
  if (!MA->isLatestArrayKind())
825
0
    return false;
826
0
  Instruction *AccInst = MA->getAccessInstruction();
827
0
  return isa<StoreInst>(AccInst) || isa<LoadInst>(AccInst);
828
0
}
829
830
0
bool ZoneAlgorithm::isNormalizable(MemoryAccess *MA) {
831
0
  assert(MA->isRead());
832
0
833
0
  // Exclude ExitPHIs, we are assuming that a normalizable PHI has a READ
834
0
  // MemoryAccess.
835
0
  if (!MA->isOriginalPHIKind())
836
0
    return false;
837
0
838
0
  // Exclude recursive PHIs, normalizing them would require a transitive
839
0
  // closure.
840
0
  auto *PHI = cast<PHINode>(MA->getAccessInstruction());
841
0
  if (RecursivePHIs.count(PHI))
842
0
    return false;
843
0
844
0
  // Ensure that each incoming value can be represented by a ValInst[].
845
0
  // We do represent values from statements associated to multiple incoming
846
0
  // value by the PHI itself, but we do not handle this case yet (especially
847
0
  // isNormalized()) when normalizing.
848
0
  const ScopArrayInfo *SAI = MA->getOriginalScopArrayInfo();
849
0
  auto Incomings = S->getPHIIncomings(SAI);
850
0
  for (MemoryAccess *Incoming : Incomings) {
851
0
    if (Incoming->getIncoming().size() != 1)
852
0
      return false;
853
0
  }
854
0
855
0
  return true;
856
0
}
857
858
0
bool ZoneAlgorithm::isNormalized(isl::map Map) {
859
0
  isl::space Space = Map.get_space();
860
0
  isl::space RangeSpace = Space.range();
861
0
862
0
  if (!RangeSpace.is_wrapping())
863
0
    return true;
864
0
865
0
  auto *PHI = dyn_cast<PHINode>(static_cast<Value *>(
866
0
      RangeSpace.unwrap().get_tuple_id(isl::dim::out).get_user()));
867
0
  if (!PHI)
868
0
    return true;
869
0
870
0
  auto *IncomingStmt = static_cast<ScopStmt *>(
871
0
      RangeSpace.unwrap().get_tuple_id(isl::dim::in).get_user());
872
0
  MemoryAccess *PHIRead = IncomingStmt->lookupPHIReadOf(PHI);
873
0
  if (!isNormalizable(PHIRead))
874
0
    return true;
875
0
876
0
  return false;
877
0
}
878
879
0
bool ZoneAlgorithm::isNormalized(isl::union_map UMap) {
880
0
  auto Result = UMap.foreach_map([this](isl::map Map) -> isl::stat {
881
0
    if (isNormalized(Map))
882
0
      return isl::stat::ok;
883
0
    return isl::stat::error;
884
0
  });
885
0
  return Result == isl::stat::ok;
886
0
}
887
888
25
void ZoneAlgorithm::computeCommon() {
889
25
  AllReads = makeEmptyUnionMap();
890
25
  AllMayWrites = makeEmptyUnionMap();
891
25
  AllMustWrites = makeEmptyUnionMap();
892
25
  AllWriteValInst = makeEmptyUnionMap();
893
25
  AllReadValInst = makeEmptyUnionMap();
894
25
895
25
  // Default to empty, i.e. no normalization/replacement is taking place. Call
896
25
  // computeNormalizedPHIs() to initialize.
897
25
  NormalizeMap = makeEmptyUnionMap();
898
25
  ComputedPHIs.clear();
899
25
900
102
  for (auto &Stmt : *S) {
901
199
    for (auto *MA : Stmt) {
902
199
      if (!MA->isLatestArrayKind())
903
159
        continue;
904
40
905
40
      if (MA->isRead())
906
10
        addArrayReadAccess(MA);
907
40
908
40
      if (MA->isWrite())
909
30
        addArrayWriteAccess(MA);
910
199
    }
911
102
  }
912
25
913
25
  // { DomainWrite[] -> Element[] }
914
25
  AllWrites =
915
25
      give(isl_union_map_union(AllMustWrites.copy(), AllMayWrites.copy()));
916
25
917
25
  // { [Element[] -> Zone[]] -> DomainWrite[] }
918
25
  WriteReachDefZone =
919
25
      computeReachingDefinition(Schedule, AllWrites, false, true);
920
25
  simplify(WriteReachDefZone);
921
25
}
922
923
0
void ZoneAlgorithm::computeNormalizedPHIs() {
924
0
  // Determine which PHIs can reference themselves. They are excluded from
925
0
  // normalization to avoid problems with transitive closures.
926
0
  for (ScopStmt &Stmt : *S) {
927
0
    for (MemoryAccess *MA : Stmt) {
928
0
      if (!MA->isPHIKind())
929
0
        continue;
930
0
      if (!MA->isRead())
931
0
        continue;
932
0
933
0
      // TODO: Can be more efficient since isRecursivePHI can theoretically
934
0
      // determine recursiveness for multiple values and/or cache results.
935
0
      auto *PHI = cast<PHINode>(MA->getAccessInstruction());
936
0
      if (isRecursivePHI(PHI)) {
937
0
        NumRecursivePHIs++;
938
0
        RecursivePHIs.insert(PHI);
939
0
      }
940
0
    }
941
0
  }
942
0
943
0
  // { PHIValInst[] -> IncomingValInst[] }
944
0
  isl::union_map AllPHIMaps = makeEmptyUnionMap();
945
0
946
0
  // Discover new PHIs and try to normalize them.
947
0
  DenseSet<PHINode *> AllPHIs;
948
0
  for (ScopStmt &Stmt : *S) {
949
0
    for (MemoryAccess *MA : Stmt) {
950
0
      if (!MA->isOriginalPHIKind())
951
0
        continue;
952
0
      if (!MA->isRead())
953
0
        continue;
954
0
      if (!isNormalizable(MA))
955
0
        continue;
956
0
957
0
      auto *PHI = cast<PHINode>(MA->getAccessInstruction());
958
0
      const ScopArrayInfo *SAI = MA->getOriginalScopArrayInfo();
959
0
960
0
      // { PHIDomain[] -> PHIValInst[] }
961
0
      isl::map PHIValInst = makeValInst(PHI, &Stmt, Stmt.getSurroundingLoop());
962
0
963
0
      // { IncomingDomain[] -> IncomingValInst[] }
964
0
      isl::union_map IncomingValInsts = makeEmptyUnionMap();
965
0
966
0
      // Get all incoming values.
967
0
      for (MemoryAccess *MA : S->getPHIIncomings(SAI)) {
968
0
        ScopStmt *IncomingStmt = MA->getStatement();
969
0
970
0
        auto Incoming = MA->getIncoming();
971
0
        assert(Incoming.size() == 1 && "The incoming value must be "
972
0
                                       "representable by something else than "
973
0
                                       "the PHI itself");
974
0
        Value *IncomingVal = Incoming[0].second;
975
0
976
0
        // { IncomingDomain[] -> IncomingValInst[] }
977
0
        isl::map IncomingValInst = makeValInst(
978
0
            IncomingVal, IncomingStmt, IncomingStmt->getSurroundingLoop());
979
0
980
0
        IncomingValInsts = IncomingValInsts.add_map(IncomingValInst);
981
0
      }
982
0
983
0
      // Determine which instance of the PHI statement corresponds to which
984
0
      // incoming value.
985
0
      // { PHIDomain[] -> IncomingDomain[] }
986
0
      isl::union_map PerPHI = computePerPHI(SAI);
987
0
988
0
      // { PHIValInst[] -> IncomingValInst[] }
989
0
      isl::union_map PHIMap =
990
0
          PerPHI.apply_domain(PHIValInst).apply_range(IncomingValInsts);
991
0
      assert(!PHIMap.is_single_valued().is_false());
992
0
993
0
      // Resolve transitiveness: The incoming value of the newly discovered PHI
994
0
      // may reference a previously normalized PHI. At the same time, already
995
0
      // normalized PHIs might be normalized to the new PHI. At the end, none of
996
0
      // the PHIs may appear on the right-hand-side of the normalization map.
997
0
      PHIMap = normalizeValInst(PHIMap, AllPHIs, AllPHIMaps);
998
0
      AllPHIs.insert(PHI);
999
0
      AllPHIMaps = normalizeValInst(AllPHIMaps, AllPHIs, PHIMap);
1000
0
1001
0
      AllPHIMaps = AllPHIMaps.unite(PHIMap);
1002
0
      NumNormalizablePHIs++;
1003
0
    }
1004
0
  }
1005
0
  simplify(AllPHIMaps);
1006
0
1007
0
  // Apply the normalization.
1008
0
  ComputedPHIs = AllPHIs;
1009
0
  NormalizeMap = AllPHIMaps;
1010
0
1011
0
  assert(!NormalizeMap || isNormalized(NormalizeMap));
1012
0
}
1013
1014
13
void ZoneAlgorithm::printAccesses(llvm::raw_ostream &OS, int Indent) const {
1015
13
  OS.indent(Indent) << "After accesses {\n";
1016
65
  for (auto &Stmt : *S) {
1017
65
    OS.indent(Indent + 4) << Stmt.getBaseName() << "\n";
1018
65
    for (auto *MA : Stmt)
1019
127
      MA->print(OS);
1020
65
  }
1021
13
  OS.indent(Indent) << "}\n";
1022
13
}
1023
1024
25
isl::union_map ZoneAlgorithm::computeKnownFromMustWrites() const {
1025
25
  // { [Element[] -> Zone[]] -> [Element[] -> DomainWrite[]] }
1026
25
  isl::union_map EltReachdDef = distributeDomain(WriteReachDefZone.curry());
1027
25
1028
25
  // { [Element[] -> DomainWrite[]] -> ValInst[] }
1029
25
  isl::union_map AllKnownWriteValInst = filterKnownValInst(AllWriteValInst);
1030
25
1031
25
  // { [Element[] -> Zone[]] -> ValInst[] }
1032
25
  return EltReachdDef.apply_range(AllKnownWriteValInst);
1033
25
}
1034
1035
7
isl::union_map ZoneAlgorithm::computeKnownFromLoad() const {
1036
7
  // { Element[] }
1037
7
  isl::union_set AllAccessedElts = AllReads.range().unite(AllWrites.range());
1038
7
1039
7
  // { Element[] -> Scatter[] }
1040
7
  isl::union_map EltZoneUniverse = isl::union_map::from_domain_and_range(
1041
7
      AllAccessedElts, isl::set::universe(ScatterSpace));
1042
7
1043
7
  // This assumes there are no "holes" in
1044
7
  // isl_union_map_domain(WriteReachDefZone); alternatively, compute the zone
1045
7
  // before the first write or that are not written at all.
1046
7
  // { Element[] -> Scatter[] }
1047
7
  isl::union_set NonReachDef =
1048
7
      EltZoneUniverse.wrap().subtract(WriteReachDefZone.domain());
1049
7
1050
7
  // { [Element[] -> Zone[]] -> ReachDefId[] }
1051
7
  isl::union_map DefZone =
1052
7
      WriteReachDefZone.unite(isl::union_map::from_domain(NonReachDef));
1053
7
1054
7
  // { [Element[] -> Scatter[]] -> Element[] }
1055
7
  isl::union_map EltZoneElt = EltZoneUniverse.domain_map();
1056
7
1057
7
  // { [Element[] -> Zone[]] -> [Element[] -> ReachDefId[]] }
1058
7
  isl::union_map DefZoneEltDefId = EltZoneElt.range_product(DefZone);
1059
7
1060
7
  // { Element[] -> [Zone[] -> ReachDefId[]] }
1061
7
  isl::union_map EltDefZone = DefZone.curry();
1062
7
1063
7
  // { [Element[] -> Zone[] -> [Element[] -> ReachDefId[]] }
1064
7
  isl::union_map EltZoneEltDefid = distributeDomain(EltDefZone);
1065
7
1066
7
  // { [Element[] -> Scatter[]] -> DomainRead[] }
1067
7
  isl::union_map Reads = AllReads.range_product(Schedule).reverse();
1068
7
1069
7
  // { [Element[] -> Scatter[]] -> [Element[] -> DomainRead[]] }
1070
7
  isl::union_map ReadsElt = EltZoneElt.range_product(Reads);
1071
7
1072
7
  // { [Element[] -> Scatter[]] -> ValInst[] }
1073
7
  isl::union_map ScatterKnown = ReadsElt.apply_range(AllReadValInst);
1074
7
1075
7
  // { [Element[] -> ReachDefId[]] -> ValInst[] }
1076
7
  isl::union_map DefidKnown =
1077
7
      DefZoneEltDefId.apply_domain(ScatterKnown).reverse();
1078
7
1079
7
  // { [Element[] -> Zone[]] -> ValInst[] }
1080
7
  return DefZoneEltDefId.apply_range(DefidKnown);
1081
7
}
1082
1083
isl::union_map ZoneAlgorithm::computeKnown(bool FromWrite,
1084
25
                                           bool FromRead) const {
1085
25
  isl::union_map Result = makeEmptyUnionMap();
1086
25
1087
25
  if (FromWrite)
1088
25
    Result = Result.unite(computeKnownFromMustWrites());
1089
25
1090
25
  if (FromRead)
1091
7
    Result = Result.unite(computeKnownFromLoad());
1092
25
1093
25
  simplify(Result);
1094
25
  return Result;
1095
25
}