Coverage Report

Created: 2017-08-21 19:50

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