Coverage Report

Created: 2018-06-24 14:39

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