Coverage Report

Created: 2017-11-21 03:47

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/Analysis/DependenceInfo.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- DependenceInfo.cpp - Calculate dependency information for a Scop. --===//
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
// Calculate the data dependency relations for a Scop using ISL.
11
//
12
// The integer set library (ISL) from Sven, has a integrated dependency analysis
13
// to calculate data dependences. This pass takes advantage of this and
14
// calculate those dependences a Scop.
15
//
16
// The dependences in this pass are exact in terms that for a specific read
17
// statement instance only the last write statement instance is returned. In
18
// case of may writes a set of possible write instances is returned. This
19
// analysis will never produce redundant dependences.
20
//
21
//===----------------------------------------------------------------------===//
22
//
23
#include "polly/DependenceInfo.h"
24
#include "polly/LinkAllPasses.h"
25
#include "polly/Options.h"
26
#include "polly/ScopInfo.h"
27
#include "polly/Support/GICHelper.h"
28
#include "llvm/Support/Debug.h"
29
#include <isl/aff.h>
30
#include <isl/ctx.h>
31
#include <isl/flow.h>
32
#include <isl/map.h>
33
#include <isl/options.h>
34
#include <isl/schedule.h>
35
#include <isl/set.h>
36
#include <isl/union_map.h>
37
#include <isl/union_set.h>
38
39
using namespace polly;
40
using namespace llvm;
41
42
#define DEBUG_TYPE "polly-dependence"
43
44
static cl::opt<int> OptComputeOut(
45
    "polly-dependences-computeout",
46
    cl::desc("Bound the dependence analysis by a maximal amount of "
47
             "computational steps (0 means no bound)"),
48
    cl::Hidden, cl::init(500000), cl::ZeroOrMore, cl::cat(PollyCategory));
49
50
static cl::opt<bool> LegalityCheckDisabled(
51
    "disable-polly-legality", cl::desc("Disable polly legality check"),
52
    cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
53
54
static cl::opt<bool>
55
    UseReductions("polly-dependences-use-reductions",
56
                  cl::desc("Exploit reductions in dependence analysis"),
57
                  cl::Hidden, cl::init(true), cl::ZeroOrMore,
58
                  cl::cat(PollyCategory));
59
60
enum AnalysisType { VALUE_BASED_ANALYSIS, MEMORY_BASED_ANALYSIS };
61
62
static cl::opt<enum AnalysisType> OptAnalysisType(
63
    "polly-dependences-analysis-type",
64
    cl::desc("The kind of dependence analysis to use"),
65
    cl::values(clEnumValN(VALUE_BASED_ANALYSIS, "value-based",
66
                          "Exact dependences without transitive dependences"),
67
               clEnumValN(MEMORY_BASED_ANALYSIS, "memory-based",
68
                          "Overapproximation of dependences")),
69
    cl::Hidden, cl::init(VALUE_BASED_ANALYSIS), cl::ZeroOrMore,
70
    cl::cat(PollyCategory));
71
72
static cl::opt<Dependences::AnalysisLevel> OptAnalysisLevel(
73
    "polly-dependences-analysis-level",
74
    cl::desc("The level of dependence analysis"),
75
    cl::values(clEnumValN(Dependences::AL_Statement, "statement-wise",
76
                          "Statement-level analysis"),
77
               clEnumValN(Dependences::AL_Reference, "reference-wise",
78
                          "Memory reference level analysis that distinguish"
79
                          " accessed references in the same statement"),
80
               clEnumValN(Dependences::AL_Access, "access-wise",
81
                          "Memory reference level analysis that distinguish"
82
                          " access instructions in the same statement")),
83
    cl::Hidden, cl::init(Dependences::AL_Statement), cl::ZeroOrMore,
84
    cl::cat(PollyCategory));
85
86
//===----------------------------------------------------------------------===//
87
88
/// Tag the @p Relation domain with @p TagId
89
static __isl_give isl_map *tag(__isl_take isl_map *Relation,
90
368
                               __isl_take isl_id *TagId) {
91
368
  isl_space *Space = isl_map_get_space(Relation);
92
368
  Space = isl_space_drop_dims(Space, isl_dim_out, 0,
93
368
                              isl_map_dim(Relation, isl_dim_out));
94
368
  Space = isl_space_set_tuple_id(Space, isl_dim_out, TagId);
95
368
  isl_multi_aff *Tag = isl_multi_aff_domain_map(Space);
96
368
  Relation = isl_map_preimage_domain_multi_aff(Relation, Tag);
97
368
  return Relation;
98
368
}
99
100
/// Tag the @p Relation domain with either MA->getArrayId() or
101
///        MA->getId() based on @p TagLevel
102
static __isl_give isl_map *tag(__isl_take isl_map *Relation, MemoryAccess *MA,
103
1.66k
                               Dependences::AnalysisLevel TagLevel) {
104
1.66k
  if (TagLevel == Dependences::AL_Reference)
105
252
    return tag(Relation, MA->getArrayId().release());
106
1.41k
107
1.41k
  if (TagLevel == Dependences::AL_Access)
108
116
    return tag(Relation, MA->getId().release());
109
1.30k
110
1.30k
  // No need to tag at the statement level.
111
1.30k
  return Relation;
112
1.30k
}
113
114
/// Collect information about the SCoP @p S.
115
static void collectInfo(Scop &S, isl_union_map *&Read,
116
                        isl_union_map *&MustWrite, isl_union_map *&MayWrite,
117
                        isl_union_map *&ReductionTagMap,
118
                        isl_union_set *&TaggedStmtDomain,
119
599
                        Dependences::AnalysisLevel Level) {
120
599
  isl_space *Space = S.getParamSpace().release();
121
599
  Read = isl_union_map_empty(isl_space_copy(Space));
122
599
  MustWrite = isl_union_map_empty(isl_space_copy(Space));
123
599
  MayWrite = isl_union_map_empty(isl_space_copy(Space));
124
599
  ReductionTagMap = isl_union_map_empty(isl_space_copy(Space));
125
599
  isl_union_map *StmtSchedule = isl_union_map_empty(Space);
126
599
127
599
  SmallPtrSet<const ScopArrayInfo *, 8> ReductionArrays;
128
599
  if (UseReductions)
129
599
    for (ScopStmt &Stmt : S)
130
955
      for (MemoryAccess *MA : Stmt)
131
1.86k
        if (MA->isReductionLike())
132
330
          ReductionArrays.insert(MA->getScopArrayInfo());
133
599
134
955
  for (ScopStmt &Stmt : S) {
135
1.86k
    for (MemoryAccess *MA : Stmt) {
136
1.86k
      isl_set *domcp = Stmt.getDomain().release();
137
1.86k
      isl_map *accdom = MA->getAccessRelation().release();
138
1.86k
139
1.86k
      accdom = isl_map_intersect_domain(accdom, domcp);
140
1.86k
141
1.86k
      if (ReductionArrays.count(MA->getScopArrayInfo())) {
142
378
        // Wrap the access domain and adjust the schedule accordingly.
143
378
        //
144
378
        // An access domain like
145
378
        //   Stmt[i0, i1] -> MemAcc_A[i0 + i1]
146
378
        // will be transformed into
147
378
        //   [Stmt[i0, i1] -> MemAcc_A[i0 + i1]] -> MemAcc_A[i0 + i1]
148
378
        //
149
378
        // We collect all the access domains in the ReductionTagMap.
150
378
        // This is used in Dependences::calculateDependences to create
151
378
        // a tagged Schedule tree.
152
378
153
378
        ReductionTagMap =
154
378
            isl_union_map_add_map(ReductionTagMap, isl_map_copy(accdom));
155
378
        accdom = isl_map_range_map(accdom);
156
1.48k
      } else {
157
1.48k
        accdom = tag(accdom, MA, Level);
158
1.48k
        if (Level > Dependences::AL_Statement) {
159
184
          isl_map *StmtScheduleMap = Stmt.getSchedule().release();
160
184
          assert(StmtScheduleMap &&
161
184
                 "Schedules that contain extension nodes require special "
162
184
                 "handling.");
163
184
          isl_map *Schedule = tag(StmtScheduleMap, MA, Level);
164
184
          StmtSchedule = isl_union_map_add_map(StmtSchedule, Schedule);
165
184
        }
166
1.48k
      }
167
1.86k
168
1.86k
      if (MA->isRead())
169
756
        Read = isl_union_map_add_map(Read, accdom);
170
1.10k
      else if (MA->isMayWrite())
171
34
        MayWrite = isl_union_map_add_map(MayWrite, accdom);
172
1.07k
      else
173
1.07k
        MustWrite = isl_union_map_add_map(MustWrite, accdom);
174
1.86k
    }
175
955
176
955
    if (!ReductionArrays.empty() && 
Level == Dependences::AL_Statement198
)
177
182
      StmtSchedule =
178
182
          isl_union_map_add_map(StmtSchedule, Stmt.getSchedule().release());
179
955
  }
180
599
181
599
  StmtSchedule = isl_union_map_intersect_params(
182
599
      StmtSchedule, S.getAssumedContext().release());
183
599
  TaggedStmtDomain = isl_union_map_domain(StmtSchedule);
184
599
185
599
  ReductionTagMap = isl_union_map_coalesce(ReductionTagMap);
186
599
  Read = isl_union_map_coalesce(Read);
187
599
  MustWrite = isl_union_map_coalesce(MustWrite);
188
599
  MayWrite = isl_union_map_coalesce(MayWrite);
189
599
}
190
191
/// Fix all dimension of @p Zero to 0 and add it to @p user
192
92
static isl_stat fixSetToZero(__isl_take isl_set *Zero, void *user) {
193
92
  isl_union_set **User = (isl_union_set **)user;
194
347
  for (unsigned i = 0; i < isl_set_dim(Zero, isl_dim_set); 
i++255
)
195
255
    Zero = isl_set_fix_si(Zero, isl_dim_set, i, 0);
196
92
  *User = isl_union_set_add_set(*User, Zero);
197
92
  return isl_stat_ok;
198
92
}
199
200
/// Compute the privatization dependences for a given dependency @p Map
201
///
202
/// Privatization dependences are widened original dependences which originate
203
/// or end in a reduction access. To compute them we apply the transitive close
204
/// of the reduction dependences (which maps each iteration of a reduction
205
/// statement to all following ones) on the RAW/WAR/WAW dependences. The
206
/// dependences which start or end at a reduction statement will be extended to
207
/// depend on all following reduction statement iterations as well.
208
/// Note: "Following" here means according to the reduction dependences.
209
///
210
/// For the input:
211
///
212
///  S0:   *sum = 0;
213
///        for (int i = 0; i < 1024; i++)
214
///  S1:     *sum += i;
215
///  S2:   *sum = *sum * 3;
216
///
217
/// we have the following dependences before we add privatization dependences:
218
///
219
///   RAW:
220
///     { S0[] -> S1[0]; S1[1023] -> S2[] }
221
///   WAR:
222
///     {  }
223
///   WAW:
224
///     { S0[] -> S1[0]; S1[1024] -> S2[] }
225
///   RED:
226
///     { S1[i0] -> S1[1 + i0] : i0 >= 0 and i0 <= 1022 }
227
///
228
/// and afterwards:
229
///
230
///   RAW:
231
///     { S0[] -> S1[i0] : i0 >= 0 and i0 <= 1023;
232
///       S1[i0] -> S2[] : i0 >= 0 and i0 <= 1023}
233
///   WAR:
234
///     {  }
235
///   WAW:
236
///     { S0[] -> S1[i0] : i0 >= 0 and i0 <= 1023;
237
///       S1[i0] -> S2[] : i0 >= 0 and i0 <= 1023}
238
///   RED:
239
///     { S1[i0] -> S1[1 + i0] : i0 >= 0 and i0 <= 1022 }
240
///
241
/// Note: This function also computes the (reverse) transitive closure of the
242
///       reduction dependences.
243
72
void Dependences::addPrivatizationDependences() {
244
72
  isl_union_map *PrivRAW, *PrivWAW, *PrivWAR;
245
72
246
72
  // The transitive closure might be over approximated, thus could lead to
247
72
  // dependency cycles in the privatization dependences. To make sure this
248
72
  // will not happen we remove all negative dependences after we computed
249
72
  // the transitive closure.
250
72
  TC_RED = isl_union_map_transitive_closure(isl_union_map_copy(RED), nullptr);
251
72
252
72
  // FIXME: Apply the current schedule instead of assuming the identity schedule
253
72
  //        here. The current approach is only valid as long as we compute the
254
72
  //        dependences only with the initial (identity schedule). Any other
255
72
  //        schedule could change "the direction of the backward dependences" we
256
72
  //        want to eliminate here.
257
72
  isl_union_set *UDeltas = isl_union_map_deltas(isl_union_map_copy(TC_RED));
258
72
  isl_union_set *Universe = isl_union_set_universe(isl_union_set_copy(UDeltas));
259
72
  isl_union_set *Zero = isl_union_set_empty(isl_union_set_get_space(Universe));
260
72
  isl_union_set_foreach_set(Universe, fixSetToZero, &Zero);
261
72
  isl_union_map *NonPositive = isl_union_set_lex_le_union_set(UDeltas, Zero);
262
72
263
72
  TC_RED = isl_union_map_subtract(TC_RED, NonPositive);
264
72
265
72
  TC_RED = isl_union_map_union(
266
72
      TC_RED, isl_union_map_reverse(isl_union_map_copy(TC_RED)));
267
72
  TC_RED = isl_union_map_coalesce(TC_RED);
268
72
269
72
  isl_union_map **Maps[] = {&RAW, &WAW, &WAR};
270
72
  isl_union_map **PrivMaps[] = {&PrivRAW, &PrivWAW, &PrivWAR};
271
288
  for (unsigned u = 0; u < 3; 
u++216
) {
272
216
    isl_union_map **Map = Maps[u], **PrivMap = PrivMaps[u];
273
216
274
216
    *PrivMap = isl_union_map_apply_range(isl_union_map_copy(*Map),
275
216
                                         isl_union_map_copy(TC_RED));
276
216
    *PrivMap = isl_union_map_union(
277
216
        *PrivMap, isl_union_map_apply_range(isl_union_map_copy(TC_RED),
278
216
                                            isl_union_map_copy(*Map)));
279
216
280
216
    *Map = isl_union_map_union(*Map, *PrivMap);
281
216
  }
282
72
283
72
  isl_union_set_free(Universe);
284
72
}
285
286
static __isl_give isl_union_flow *buildFlow(__isl_keep isl_union_map *Snk,
287
                                            __isl_keep isl_union_map *Src,
288
                                            __isl_keep isl_union_map *MaySrc,
289
2.39k
                                            __isl_keep isl_schedule *Schedule) {
290
2.39k
  isl_union_access_info *AI;
291
2.39k
292
2.39k
  AI = isl_union_access_info_from_sink(isl_union_map_copy(Snk));
293
2.39k
  if (MaySrc)
294
2.39k
    AI = isl_union_access_info_set_may_source(AI, isl_union_map_copy(MaySrc));
295
2.39k
  if (Src)
296
2.37k
    AI = isl_union_access_info_set_must_source(AI, isl_union_map_copy(Src));
297
2.39k
  AI = isl_union_access_info_set_schedule(AI, isl_schedule_copy(Schedule));
298
2.39k
  auto Flow = isl_union_access_info_compute_flow(AI);
299
2.39k
  DEBUG(if (!Flow) dbgs() << "last error: "
300
2.39k
                          << isl_ctx_last_error(isl_schedule_get_ctx(Schedule))
301
2.39k
                          << '\n';);
302
2.39k
  return Flow;
303
2.39k
}
304
305
/// Compute exact WAR dependences
306
/// We need exact WAR dependences. That is, if there are
307
/// dependences of the form:
308
/// must-W2 (sink) <- must-W1 (sink) <- R (source)
309
/// We wish to generate *ONLY*:
310
/// { R -> W1 },
311
/// NOT:
312
/// { R -> W2, R -> W1 }
313
///
314
/// However, in the case of may-writes, we do *not* wish to allow
315
/// may-writes to block must-writes. This makes sense, since perhaps the
316
/// may-write will not happen. In that case, the exact dependence will
317
/// be the (read -> must-write).
318
/// Example:
319
/// must-W2 (sink) <- may-W1 (sink) <- R (source)
320
/// We wish to generate:
321
/// { R-> W1, R -> W2 }
322
///
323
/// We use the fact that may dependences are not allowed to flow
324
/// through a must source. That way, reads will be stopped by intermediate
325
/// must-writes.
326
/// However, may-sources may not interfere with one another. Hence, reads
327
/// will not block each other from generating dependences.
328
///
329
/// Write (Sink) <- MustWrite (Must-Source) <- Read (MaySource) is
330
/// present, then the dependence
331
///    { Write <- Read }
332
/// is not tracked.
333
///
334
/// We would like to specify the Must-Write as kills, source as Read
335
/// and sink as Write.
336
/// ISL does not have the functionality currently to support "kills".
337
/// Use the Must-Source as a way to specify "kills".
338
/// The drawback is that we will have both
339
///   { Write <- MustWrite, Write <- Read }
340
///
341
/// We need to filter this to track only { Write <- Read }.
342
///
343
/// Filtering { Write <- Read } from WAROverestimated:
344
/// --------------------------------------------------
345
/// isl_union_flow_get_full_may_dependence gives us dependences of the form
346
///   WAROverestimated = { Read+MustWrite -> [Write -> MemoryAccess]}
347
///
348
///  We need to intersect the domain with Read to get only
349
///  Read dependences.
350
///    Read = { Read -> MemoryAccess }
351
///
352
///
353
/// 1. Construct:
354
///   WARMemAccesses = { Read+Write -> [Read+Write -> MemoryAccess] }
355
/// This takes a Read+Write from WAROverestimated and maps it to the
356
/// corresponding wrapped memory access from WAROverestimated.
357
///
358
/// 2. Apply WARMemAcesses to the domain of WAR Overestimated to give:
359
///   WAR = { [Read+Write -> MemoryAccess] -> [Write -> MemoryAccess] }
360
///
361
/// WAR is in a state where we can intersect with Read, since they
362
/// have the same structure.
363
///
364
/// 3. Intersect this with a wrapped Read. Read is wrapped
365
/// to ensure the domains look the same.
366
///   WAR = WAR \intersect (wrapped Read)
367
///   WAR = { [Read -> MemoryAccesss] -> [Write -> MemoryAccess] }
368
///
369
///  4. Project out the memory access in the domain to get
370
///  WAR = { Read -> Write }
371
static isl_union_map *buildWAR(isl_union_map *Write, isl_union_map *MustWrite,
372
593
                               isl_union_map *Read, isl_schedule *Schedule) {
373
593
  isl_union_flow *Flow = buildFlow(Write, MustWrite, Read, Schedule);
374
593
  auto *WAROverestimated = isl_union_flow_get_full_may_dependence(Flow);
375
593
376
593
  // 1. Constructing WARMemAccesses
377
593
  // WarMemAccesses = { Read+Write -> [Write -> MemAccess] }
378
593
  // Range factor of range product
379
593
  //     { Read+Write -> MemAcesss }
380
593
  // Domain projection
381
593
  //     { [Read+Write -> MemAccess] -> Read+Write }
382
593
  // Reverse
383
593
  //     { Read+Write -> [Read+Write -> MemAccess] }
384
593
  auto WARMemAccesses = isl_union_map_copy(WAROverestimated);
385
593
  WARMemAccesses = isl_union_map_range_factor_range(WAROverestimated);
386
593
  WARMemAccesses = isl_union_map_domain_map(WARMemAccesses);
387
593
  WARMemAccesses = isl_union_map_reverse(WARMemAccesses);
388
593
389
593
  // 2. Apply to get domain tagged with memory accesses
390
593
  isl_union_map *WAR =
391
593
      isl_union_map_apply_domain(WAROverestimated, WARMemAccesses);
392
593
393
593
  // 3. Intersect with Read to extract only reads
394
593
  auto ReadWrapped = isl_union_map_wrap(isl_union_map_copy(Read));
395
593
  WAR = isl_union_map_intersect_domain(WAR, ReadWrapped);
396
593
397
593
  // 4. Project out memory accesses to get usual style dependences
398
593
  WAR = isl_union_map_range_factor_domain(WAR);
399
593
  WAR = isl_union_map_domain_factor_domain(WAR);
400
593
401
593
  isl_union_flow_free(Flow);
402
593
  return WAR;
403
593
}
404
405
599
void Dependences::calculateDependences(Scop &S) {
406
599
  isl_union_map *Read, *MustWrite, *MayWrite, *ReductionTagMap;
407
599
  isl_schedule *Schedule;
408
599
  isl_union_set *TaggedStmtDomain;
409
599
410
599
  DEBUG(dbgs() << "Scop: \n" << S << "\n");
411
599
412
599
  collectInfo(S, Read, MustWrite, MayWrite, ReductionTagMap, TaggedStmtDomain,
413
599
              Level);
414
599
415
599
  bool HasReductions = !isl_union_map_is_empty(ReductionTagMap);
416
599
417
599
  DEBUG(dbgs() << "Read: " << Read << '\n';
418
599
        dbgs() << "MustWrite: " << MustWrite << '\n';
419
599
        dbgs() << "MayWrite: " << MayWrite << '\n';
420
599
        dbgs() << "ReductionTagMap: " << ReductionTagMap << '\n';
421
599
        dbgs() << "TaggedStmtDomain: " << TaggedStmtDomain << '\n';);
422
599
423
599
  Schedule = S.getScheduleTree().release();
424
599
425
599
  if (!HasReductions) {
426
493
    isl_union_map_free(ReductionTagMap);
427
493
    // Tag the schedule tree if we want fine-grain dependence info
428
493
    if (Level > AL_Statement) {
429
40
      auto TaggedMap =
430
40
          isl_union_set_unwrap(isl_union_set_copy(TaggedStmtDomain));
431
40
      auto Tags = isl_union_map_domain_map_union_pw_multi_aff(TaggedMap);
432
40
      Schedule = isl_schedule_pullback_union_pw_multi_aff(Schedule, Tags);
433
40
    }
434
493
  } else {
435
106
    isl_union_map *IdentityMap;
436
106
    isl_union_pw_multi_aff *ReductionTags, *IdentityTags, *Tags;
437
106
438
106
    // Extract Reduction tags from the combined access domains in the given
439
106
    // SCoP. The result is a map that maps each tagged element in the domain to
440
106
    // the memory location it accesses. ReductionTags = {[Stmt[i] ->
441
106
    // Array[f(i)]] -> Stmt[i] }
442
106
    ReductionTags =
443
106
        isl_union_map_domain_map_union_pw_multi_aff(ReductionTagMap);
444
106
445
106
    // Compute an identity map from each statement in domain to itself.
446
106
    // IdentityTags = { [Stmt[i] -> Stmt[i] }
447
106
    IdentityMap = isl_union_set_identity(isl_union_set_copy(TaggedStmtDomain));
448
106
    IdentityTags = isl_union_pw_multi_aff_from_union_map(IdentityMap);
449
106
450
106
    Tags = isl_union_pw_multi_aff_union_add(ReductionTags, IdentityTags);
451
106
452
106
    // By pulling back Tags from Schedule, we have a schedule tree that can
453
106
    // be used to compute normal dependences, as well as 'tagged' reduction
454
106
    // dependences.
455
106
    Schedule = isl_schedule_pullback_union_pw_multi_aff(Schedule, Tags);
456
106
  }
457
599
458
599
  DEBUG(dbgs() << "Read: " << Read << "\n";
459
599
        dbgs() << "MustWrite: " << MustWrite << "\n";
460
599
        dbgs() << "MayWrite: " << MayWrite << "\n";
461
599
        dbgs() << "Schedule: " << Schedule << "\n");
462
599
463
599
  isl_union_map *StrictWAW = nullptr;
464
599
  {
465
599
    IslMaxOperationsGuard MaxOpGuard(IslCtx.get(), OptComputeOut);
466
599
467
599
    RAW = WAW = WAR = RED = nullptr;
468
599
    isl_union_map *Write = isl_union_map_union(isl_union_map_copy(MustWrite),
469
599
                                               isl_union_map_copy(MayWrite));
470
599
471
599
    // We are interested in detecting reductions that do not have intermediate
472
599
    // computations that are captured by other statements.
473
599
    //
474
599
    // Example:
475
599
    // void f(int *A, int *B) {
476
599
    //     for(int i = 0; i <= 100; i++) {
477
599
    //
478
599
    //            *-WAR (S0[i] -> S0[i + 1] 0 <= i <= 100)------------*
479
599
    //            |                                                   |
480
599
    //            *-WAW (S0[i] -> S0[i + 1] 0 <= i <= 100)------------*
481
599
    //            |                                                   |
482
599
    //            v                                                   |
483
599
    //     S0:    *A += i; >------------------*-----------------------*
484
599
    //                                        |
485
599
    //         if (i >= 98) {          WAR (S0[i] -> S1[i]) 98 <= i <= 100
486
599
    //                                        |
487
599
    //     S1:        *B = *A; <--------------*
488
599
    //         }
489
599
    //     }
490
599
    // }
491
599
    //
492
599
    // S0[0 <= i <= 100] has a reduction. However, the values in
493
599
    // S0[98 <= i <= 100] is captured in S1[98 <= i <= 100].
494
599
    // Since we allow free reordering on our reduction dependences, we need to
495
599
    // remove all instances of a reduction statement that have data dependences
496
599
    // originating from them.
497
599
    // In the case of the example, we need to remove S0[98 <= i <= 100] from
498
599
    // our reduction dependences.
499
599
    //
500
599
    // When we build up the WAW dependences that are used to detect reductions,
501
599
    // we consider only **Writes that have no intermediate Reads**.
502
599
    //
503
599
    // `isl_union_flow_get_must_dependence` gives us dependences of the form:
504
599
    // (sink <- must_source).
505
599
    //
506
599
    // It *will not give* dependences of the form:
507
599
    // 1. (sink <- ... <- may_source <- ... <- must_source)
508
599
    // 2. (sink <- ... <- must_source <- ... <- must_source)
509
599
    //
510
599
    // For a detailed reference on ISL's flow analysis, see:
511
599
    // "Presburger Formulas and Polyhedral Compilation" - Approximate Dataflow
512
599
    //  Analysis.
513
599
    //
514
599
    // Since we set "Write" as a must-source, "Read" as a may-source, and ask
515
599
    // for must dependences, we get all Writes to Writes that **do not flow
516
599
    // through a Read**.
517
599
    //
518
599
    // ScopInfo::checkForReductions makes sure that if something captures
519
599
    // the reduction variable in the same basic block, then it is rejected
520
599
    // before it is even handed here. This makes sure that there is exactly
521
599
    // one read and one write to a reduction variable in a Statement.
522
599
    // Example:
523
599
    //     void f(int *sum, int A[N], int B[N]) {
524
599
    //       for (int i = 0; i < N; i++) {
525
599
    //         *sum += A[i]; < the store and the load is not tagged as a
526
599
    //         B[i] = *sum;  < reduction-like access due to the overlap.
527
599
    //       }
528
599
    //     }
529
599
530
599
    isl_union_flow *Flow = buildFlow(Write, Write, Read, Schedule);
531
599
    StrictWAW = isl_union_flow_get_must_dependence(Flow);
532
599
    isl_union_flow_free(Flow);
533
599
534
599
    if (OptAnalysisType == VALUE_BASED_ANALYSIS) {
535
593
      Flow = buildFlow(Read, MustWrite, MayWrite, Schedule);
536
593
      RAW = isl_union_flow_get_may_dependence(Flow);
537
593
      isl_union_flow_free(Flow);
538
593
539
593
      Flow = buildFlow(Write, MustWrite, MayWrite, Schedule);
540
593
      WAW = isl_union_flow_get_may_dependence(Flow);
541
593
      isl_union_flow_free(Flow);
542
593
543
593
      WAR = buildWAR(Write, MustWrite, Read, Schedule);
544
593
      isl_union_map_free(Write);
545
593
      isl_schedule_free(Schedule);
546
593
    } else {
547
6
      isl_union_flow *Flow;
548
6
549
6
      Flow = buildFlow(Read, nullptr, Write, Schedule);
550
6
      RAW = isl_union_flow_get_may_dependence(Flow);
551
6
      isl_union_flow_free(Flow);
552
6
553
6
      Flow = buildFlow(Write, nullptr, Read, Schedule);
554
6
      WAR = isl_union_flow_get_may_dependence(Flow);
555
6
      isl_union_flow_free(Flow);
556
6
557
6
      Flow = buildFlow(Write, nullptr, Write, Schedule);
558
6
      WAW = isl_union_flow_get_may_dependence(Flow);
559
6
      isl_union_flow_free(Flow);
560
6
561
6
      isl_union_map_free(Write);
562
6
      isl_schedule_free(Schedule);
563
6
    }
564
599
565
599
    isl_union_map_free(MustWrite);
566
599
    isl_union_map_free(MayWrite);
567
599
    isl_union_map_free(Read);
568
599
569
599
    RAW = isl_union_map_coalesce(RAW);
570
599
    WAW = isl_union_map_coalesce(WAW);
571
599
    WAR = isl_union_map_coalesce(WAR);
572
599
573
599
    // End of max_operations scope.
574
599
  }
575
599
576
599
  if (isl_ctx_last_error(IslCtx.get()) == isl_error_quota) {
577
6
    isl_union_map_free(RAW);
578
6
    isl_union_map_free(WAW);
579
6
    isl_union_map_free(WAR);
580
6
    isl_union_map_free(StrictWAW);
581
6
    RAW = WAW = WAR = StrictWAW = nullptr;
582
6
    isl_ctx_reset_error(IslCtx.get());
583
6
  }
584
599
585
599
  // Drop out early, as the remaining computations are only needed for
586
599
  // reduction dependences or dependences that are finer than statement
587
599
  // level dependences.
588
599
  if (!HasReductions && 
Level == AL_Statement493
) {
589
453
    RED = isl_union_map_empty(isl_union_map_get_space(RAW));
590
453
    TC_RED = isl_union_map_empty(isl_union_set_get_space(TaggedStmtDomain));
591
453
    isl_union_set_free(TaggedStmtDomain);
592
453
    isl_union_map_free(StrictWAW);
593
453
    return;
594
453
  }
595
146
596
146
  isl_union_map *STMT_RAW, *STMT_WAW, *STMT_WAR;
597
146
  STMT_RAW = isl_union_map_intersect_domain(
598
146
      isl_union_map_copy(RAW), isl_union_set_copy(TaggedStmtDomain));
599
146
  STMT_WAW = isl_union_map_intersect_domain(
600
146
      isl_union_map_copy(WAW), isl_union_set_copy(TaggedStmtDomain));
601
146
  STMT_WAR =
602
146
      isl_union_map_intersect_domain(isl_union_map_copy(WAR), TaggedStmtDomain);
603
146
  DEBUG({
604
146
    dbgs() << "Wrapped Dependences:\n";
605
146
    dump();
606
146
    dbgs() << "\n";
607
146
  });
608
146
609
146
  // To handle reduction dependences we proceed as follows:
610
146
  // 1) Aggregate all possible reduction dependences, namely all self
611
146
  //    dependences on reduction like statements.
612
146
  // 2) Intersect them with the actual RAW & WAW dependences to the get the
613
146
  //    actual reduction dependences. This will ensure the load/store memory
614
146
  //    addresses were __identical__ in the two iterations of the statement.
615
146
  // 3) Relax the original RAW, WAW and WAR dependences by subtracting the
616
146
  //    actual reduction dependences. Binary reductions (sum += A[i]) cause
617
146
  //    the same, RAW, WAW and WAR dependences.
618
146
  // 4) Add the privatization dependences which are widened versions of
619
146
  //    already present dependences. They model the effect of manual
620
146
  //    privatization at the outermost possible place (namely after the last
621
146
  //    write and before the first access to a reduction location).
622
146
623
146
  // Step 1)
624
146
  RED = isl_union_map_empty(isl_union_map_get_space(RAW));
625
285
  for (ScopStmt &Stmt : S) {
626
605
    for (MemoryAccess *MA : Stmt) {
627
605
      if (!MA->isReductionLike())
628
275
        continue;
629
330
      isl_set *AccDomW = isl_map_wrap(MA->getAccessRelation().release());
630
330
      isl_map *Identity =
631
330
          isl_map_from_domain_and_range(isl_set_copy(AccDomW), AccDomW);
632
330
      RED = isl_union_map_add_map(RED, Identity);
633
330
    }
634
285
  }
635
146
636
146
  // Step 2)
637
146
  RED = isl_union_map_intersect(RED, isl_union_map_copy(RAW));
638
146
  RED = isl_union_map_intersect(RED, StrictWAW);
639
146
640
146
  if (!isl_union_map_is_empty(RED)) {
641
72
642
72
    // Step 3)
643
72
    RAW = isl_union_map_subtract(RAW, isl_union_map_copy(RED));
644
72
    WAW = isl_union_map_subtract(WAW, isl_union_map_copy(RED));
645
72
    WAR = isl_union_map_subtract(WAR, isl_union_map_copy(RED));
646
72
647
72
    // Step 4)
648
72
    addPrivatizationDependences();
649
72
  }
650
146
651
146
  DEBUG({
652
146
    dbgs() << "Final Wrapped Dependences:\n";
653
146
    dump();
654
146
    dbgs() << "\n";
655
146
  });
656
146
657
146
  // RED_SIN is used to collect all reduction dependences again after we
658
146
  // split them according to the causing memory accesses. The current assumption
659
146
  // is that our method of splitting will not have any leftovers. In the end
660
146
  // we validate this assumption until we have more confidence in this method.
661
146
  isl_union_map *RED_SIN = isl_union_map_empty(isl_union_map_get_space(RAW));
662
146
663
146
  // For each reduction like memory access, check if there are reduction
664
146
  // dependences with the access relation of the memory access as a domain
665
146
  // (wrapped space!). If so these dependences are caused by this memory access.
666
146
  // We then move this portion of reduction dependences back to the statement ->
667
146
  // statement space and add a mapping from the memory access to these
668
146
  // dependences.
669
285
  for (ScopStmt &Stmt : S) {
670
605
    for (MemoryAccess *MA : Stmt) {
671
605
      if (!MA->isReductionLike())
672
275
        continue;
673
330
674
330
      isl_set *AccDomW = isl_map_wrap(MA->getAccessRelation().release());
675
330
      isl_union_map *AccRedDepU = isl_union_map_intersect_domain(
676
330
          isl_union_map_copy(TC_RED), isl_union_set_from_set(AccDomW));
677
330
      if (isl_union_map_is_empty(AccRedDepU)) {
678
146
        isl_union_map_free(AccRedDepU);
679
146
        continue;
680
146
      }
681
184
682
184
      isl_map *AccRedDep = isl_map_from_union_map(AccRedDepU);
683
184
      RED_SIN = isl_union_map_add_map(RED_SIN, isl_map_copy(AccRedDep));
684
184
      AccRedDep = isl_map_zip(AccRedDep);
685
184
      AccRedDep = isl_set_unwrap(isl_map_domain(AccRedDep));
686
184
      setReductionDependences(MA, AccRedDep);
687
184
    }
688
285
  }
689
146
690
146
  assert(isl_union_map_is_equal(RED_SIN, TC_RED) &&
691
146
         "Intersecting the reduction dependence domain with the wrapped access "
692
146
         "relation is not enough, we need to loosen the access relation also");
693
146
  isl_union_map_free(RED_SIN);
694
146
695
146
  RAW = isl_union_map_zip(RAW);
696
146
  WAW = isl_union_map_zip(WAW);
697
146
  WAR = isl_union_map_zip(WAR);
698
146
  RED = isl_union_map_zip(RED);
699
146
  TC_RED = isl_union_map_zip(TC_RED);
700
146
701
146
  DEBUG({
702
146
    dbgs() << "Zipped Dependences:\n";
703
146
    dump();
704
146
    dbgs() << "\n";
705
146
  });
706
146
707
146
  RAW = isl_union_set_unwrap(isl_union_map_domain(RAW));
708
146
  WAW = isl_union_set_unwrap(isl_union_map_domain(WAW));
709
146
  WAR = isl_union_set_unwrap(isl_union_map_domain(WAR));
710
146
  RED = isl_union_set_unwrap(isl_union_map_domain(RED));
711
146
  TC_RED = isl_union_set_unwrap(isl_union_map_domain(TC_RED));
712
146
713
146
  DEBUG({
714
146
    dbgs() << "Unwrapped Dependences:\n";
715
146
    dump();
716
146
    dbgs() << "\n";
717
146
  });
718
146
719
146
  RAW = isl_union_map_union(RAW, STMT_RAW);
720
146
  WAW = isl_union_map_union(WAW, STMT_WAW);
721
146
  WAR = isl_union_map_union(WAR, STMT_WAR);
722
146
723
146
  RAW = isl_union_map_coalesce(RAW);
724
146
  WAW = isl_union_map_coalesce(WAW);
725
146
  WAR = isl_union_map_coalesce(WAR);
726
146
  RED = isl_union_map_coalesce(RED);
727
146
  TC_RED = isl_union_map_coalesce(TC_RED);
728
146
729
146
  DEBUG(dump());
730
599
}
731
732
bool Dependences::isValidSchedule(Scop &S,
733
86
                                  StatementToIslMapTy *NewSchedule) const {
734
86
  if (LegalityCheckDisabled)
735
0
    return true;
736
86
737
86
  isl_union_map *Dependences = getDependences(TYPE_RAW | TYPE_WAW | TYPE_WAR);
738
86
  isl_space *Space = S.getParamSpace().release();
739
86
  isl_union_map *Schedule = isl_union_map_empty(Space);
740
86
741
86
  isl_space *ScheduleSpace = nullptr;
742
86
743
131
  for (ScopStmt &Stmt : S) {
744
131
    isl_map *StmtScat;
745
131
746
131
    if (NewSchedule->find(&Stmt) == NewSchedule->end())
747
0
      StmtScat = Stmt.getSchedule().release();
748
131
    else
749
131
      StmtScat = isl_map_copy((*NewSchedule)[&Stmt]);
750
131
    assert(StmtScat &&
751
131
           "Schedules that contain extension nodes require special handling.");
752
131
753
131
    if (!ScheduleSpace)
754
86
      ScheduleSpace = isl_space_range(isl_map_get_space(StmtScat));
755
131
756
131
    Schedule = isl_union_map_add_map(Schedule, StmtScat);
757
131
  }
758
86
759
86
  Dependences =
760
86
      isl_union_map_apply_domain(Dependences, isl_union_map_copy(Schedule));
761
86
  Dependences = isl_union_map_apply_range(Dependences, Schedule);
762
86
763
86
  isl_set *Zero = isl_set_universe(isl_space_copy(ScheduleSpace));
764
304
  for (unsigned i = 0; i < isl_set_dim(Zero, isl_dim_set); 
i++218
)
765
218
    Zero = isl_set_fix_si(Zero, isl_dim_set, i, 0);
766
86
767
86
  isl_union_set *UDeltas = isl_union_map_deltas(Dependences);
768
86
  isl_set *Deltas = isl_union_set_extract_set(UDeltas, ScheduleSpace);
769
86
  isl_union_set_free(UDeltas);
770
86
771
86
  isl_map *NonPositive = isl_set_lex_le_set(Deltas, Zero);
772
86
  bool IsValid = isl_map_is_empty(NonPositive);
773
86
  isl_map_free(NonPositive);
774
86
775
86
  return IsValid;
776
86
}
777
778
// Check if the current scheduling dimension is parallel.
779
//
780
// We check for parallelism by verifying that the loop does not carry any
781
// dependences.
782
//
783
// Parallelism test: if the distance is zero in all outer dimensions, then it
784
// has to be zero in the current dimension as well.
785
//
786
// Implementation: first, translate dependences into time space, then force
787
// outer dimensions to be equal. If the distance is zero in the current
788
// dimension, then the loop is parallel. The distance is zero in the current
789
// dimension if it is a subset of a map with equal values for the current
790
// dimension.
791
bool Dependences::isParallel(isl_union_map *Schedule, isl_union_map *Deps,
792
388
                             isl_pw_aff **MinDistancePtr) const {
793
388
  isl_set *Deltas, *Distance;
794
388
  isl_map *ScheduleDeps;
795
388
  unsigned Dimension;
796
388
  bool IsParallel;
797
388
798
388
  Deps = isl_union_map_apply_range(Deps, isl_union_map_copy(Schedule));
799
388
  Deps = isl_union_map_apply_domain(Deps, isl_union_map_copy(Schedule));
800
388
801
388
  if (isl_union_map_is_empty(Deps)) {
802
228
    isl_union_map_free(Deps);
803
228
    return true;
804
228
  }
805
160
806
160
  ScheduleDeps = isl_map_from_union_map(Deps);
807
160
  Dimension = isl_map_dim(ScheduleDeps, isl_dim_out) - 1;
808
160
809
257
  for (unsigned i = 0; i < Dimension; 
i++97
)
810
160
    
ScheduleDeps = isl_map_equate(ScheduleDeps, isl_dim_out, i, isl_dim_in, i)97
;
811
160
812
160
  Deltas = isl_map_deltas(ScheduleDeps);
813
160
  Distance = isl_set_universe(isl_set_get_space(Deltas));
814
160
815
160
  // [0, ..., 0, +] - All zeros and last dimension larger than zero
816
257
  for (unsigned i = 0; i < Dimension; 
i++97
)
817
160
    
Distance = isl_set_fix_si(Distance, isl_dim_set, i, 0)97
;
818
160
819
160
  Distance = isl_set_lower_bound_si(Distance, isl_dim_set, Dimension, 1);
820
160
  Distance = isl_set_intersect(Distance, Deltas);
821
160
822
160
  IsParallel = isl_set_is_empty(Distance);
823
160
  if (IsParallel || 
!MinDistancePtr123
) {
824
129
    isl_set_free(Distance);
825
129
    return IsParallel;
826
129
  }
827
31
828
31
  Distance = isl_set_project_out(Distance, isl_dim_set, 0, Dimension);
829
31
  Distance = isl_set_coalesce(Distance);
830
31
831
31
  // This last step will compute a expression for the minimal value in the
832
31
  // distance polyhedron Distance with regards to the first (outer most)
833
31
  // dimension.
834
31
  *MinDistancePtr = isl_pw_aff_coalesce(isl_set_dim_min(Distance, 0));
835
31
836
31
  return false;
837
31
}
838
839
265
static void printDependencyMap(raw_ostream &OS, __isl_keep isl_union_map *DM) {
840
265
  if (DM)
841
244
    OS << DM << "\n";
842
21
  else
843
21
    OS << "n/a\n";
844
265
}
845
846
53
void Dependences::print(raw_ostream &OS) const {
847
53
  OS << "\tRAW dependences:\n\t\t";
848
53
  printDependencyMap(OS, RAW);
849
53
  OS << "\tWAR dependences:\n\t\t";
850
53
  printDependencyMap(OS, WAR);
851
53
  OS << "\tWAW dependences:\n\t\t";
852
53
  printDependencyMap(OS, WAW);
853
53
  OS << "\tReduction dependences:\n\t\t";
854
53
  printDependencyMap(OS, RED);
855
53
  OS << "\tTransitive closure of reduction dependences:\n\t\t";
856
53
  printDependencyMap(OS, TC_RED);
857
53
}
858
859
0
void Dependences::dump() const { print(dbgs()); }
860
861
577
void Dependences::releaseMemory() {
862
577
  isl_union_map_free(RAW);
863
577
  isl_union_map_free(WAR);
864
577
  isl_union_map_free(WAW);
865
577
  isl_union_map_free(RED);
866
577
  isl_union_map_free(TC_RED);
867
577
868
577
  RED = RAW = WAR = WAW = TC_RED = nullptr;
869
577
870
577
  for (auto &ReductionDeps : ReductionDependences)
871
577
    
isl_map_free(ReductionDeps.second)152
;
872
577
  ReductionDependences.clear();
873
577
}
874
875
550
__isl_give isl_union_map *Dependences::getDependences(int Kinds) const {
876
550
  assert(hasValidDependences() && "No valid dependences available");
877
550
  isl_space *Space = isl_union_map_get_space(RAW);
878
550
  isl_union_map *Deps = isl_union_map_empty(Space);
879
550
880
550
  if (Kinds & TYPE_RAW)
881
400
    Deps = isl_union_map_union(Deps, isl_union_map_copy(RAW));
882
550
883
550
  if (Kinds & TYPE_WAR)
884
362
    Deps = isl_union_map_union(Deps, isl_union_map_copy(WAR));
885
550
886
550
  if (Kinds & TYPE_WAW)
887
362
    Deps = isl_union_map_union(Deps, isl_union_map_copy(WAW));
888
550
889
550
  if (Kinds & TYPE_RED)
890
54
    Deps = isl_union_map_union(Deps, isl_union_map_copy(RED));
891
550
892
550
  if (Kinds & TYPE_TC_RED)
893
136
    Deps = isl_union_map_union(Deps, isl_union_map_copy(TC_RED));
894
550
895
550
  Deps = isl_union_map_coalesce(Deps);
896
550
  Deps = isl_union_map_detect_equalities(Deps);
897
550
  return Deps;
898
550
}
899
900
248
bool Dependences::hasValidDependences() const {
901
248
  return (RAW != nullptr) && 
(WAR != nullptr)245
&&
(WAW != nullptr)245
;
902
248
}
903
904
__isl_give isl_map *
905
0
Dependences::getReductionDependences(MemoryAccess *MA) const {
906
0
  return isl_map_copy(ReductionDependences.lookup(MA));
907
0
}
908
909
184
void Dependences::setReductionDependences(MemoryAccess *MA, isl_map *D) {
910
184
  assert(ReductionDependences.count(MA) == 0 &&
911
184
         "Reduction dependences set twice!");
912
184
  ReductionDependences[MA] = D;
913
184
}
914
915
const Dependences &
916
0
DependenceAnalysis::Result::getDependences(Dependences::AnalysisLevel Level) {
917
0
  if (Dependences *d = D[Level].get())
918
0
    return *d;
919
0
920
0
  return recomputeDependences(Level);
921
0
}
922
923
const Dependences &DependenceAnalysis::Result::recomputeDependences(
924
0
    Dependences::AnalysisLevel Level) {
925
0
  D[Level].reset(new Dependences(S.getSharedIslCtx(), Level));
926
0
  D[Level]->calculateDependences(S);
927
0
  return *D[Level];
928
0
}
929
930
DependenceAnalysis::Result
931
DependenceAnalysis::run(Scop &S, ScopAnalysisManager &SAM,
932
0
                        ScopStandardAnalysisResults &SAR) {
933
0
  return {S, {}};
934
0
}
935
936
AnalysisKey DependenceAnalysis::Key;
937
938
PreservedAnalyses
939
DependenceInfoPrinterPass::run(Scop &S, ScopAnalysisManager &SAM,
940
                               ScopStandardAnalysisResults &SAR,
941
0
                               SPMUpdater &U) {
942
0
  auto &DI = SAM.getResult<DependenceAnalysis>(S, SAR);
943
0
944
0
  if (auto d = DI.D[OptAnalysisLevel].get()) {
945
0
    d->print(OS);
946
0
    return PreservedAnalyses::all();
947
0
  }
948
0
949
0
  // Otherwise create the dependences on-the-fly and print them
950
0
  Dependences D(S.getSharedIslCtx(), OptAnalysisLevel);
951
0
  D.calculateDependences(S);
952
0
  D.print(OS);
953
0
954
0
  return PreservedAnalyses::all();
955
0
}
956
957
const Dependences &
958
602
DependenceInfo::getDependences(Dependences::AnalysisLevel Level) {
959
602
  if (Dependences *d = D[Level].get())
960
80
    return *d;
961
522
962
522
  return recomputeDependences(Level);
963
522
}
964
965
const Dependences &
966
527
DependenceInfo::recomputeDependences(Dependences::AnalysisLevel Level) {
967
527
  D[Level].reset(new Dependences(S->getSharedIslCtx(), Level));
968
527
  D[Level]->calculateDependences(*S);
969
527
  return *D[Level];
970
527
}
971
972
569
bool DependenceInfo::runOnScop(Scop &ScopVar) {
973
569
  S = &ScopVar;
974
569
  return false;
975
569
}
976
977
/// Print the dependences for the given SCoP to @p OS.
978
979
47
void polly::DependenceInfo::printScop(raw_ostream &OS, Scop &S) const {
980
47
  if (auto d = D[OptAnalysisLevel].get()) {
981
0
    d->print(OS);
982
0
    return;
983
0
  }
984
47
985
47
  // Otherwise create the dependences on-the-fly and print it
986
47
  Dependences D(S.getSharedIslCtx(), OptAnalysisLevel);
987
47
  D.calculateDependences(S);
988
47
  D.print(OS);
989
47
}
990
991
582
void DependenceInfo::getAnalysisUsage(AnalysisUsage &AU) const {
992
582
  AU.addRequiredTransitive<ScopInfoRegionPass>();
993
582
  AU.setPreservesAll();
994
582
}
995
996
char DependenceInfo::ID = 0;
997
998
0
Pass *polly::createDependenceInfoPass() { return new DependenceInfo(); }
999
1000
37.2k
INITIALIZE_PASS_BEGIN(DependenceInfo, "polly-dependences",
1001
37.2k
                      "Polly - Calculate dependences", false, false);
1002
37.2k
INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass);
1003
37.2k
INITIALIZE_PASS_END(DependenceInfo, "polly-dependences",
1004
                    "Polly - Calculate dependences", false, false)
1005
1006
//===----------------------------------------------------------------------===//
1007
const Dependences &
1008
DependenceInfoWrapperPass::getDependences(Scop *S,
1009
33
                                          Dependences::AnalysisLevel Level) {
1010
33
  auto It = ScopToDepsMap.find(S);
1011
33
  if (It != ScopToDepsMap.end())
1012
33
    if (It->second) {
1013
33
      if (It->second->getDependenceLevel() == Level)
1014
33
        return *It->second.get();
1015
0
    }
1016
0
  return recomputeDependences(S, Level);
1017
0
}
1018
1019
const Dependences &DependenceInfoWrapperPass::recomputeDependences(
1020
25
    Scop *S, Dependences::AnalysisLevel Level) {
1021
25
  std::unique_ptr<Dependences> D(new Dependences(S->getSharedIslCtx(), Level));
1022
25
  D->calculateDependences(*S);
1023
25
  auto Inserted = ScopToDepsMap.insert(std::make_pair(S, std::move(D)));
1024
25
  return *Inserted.first->second;
1025
25
}
1026
1027
26
bool DependenceInfoWrapperPass::runOnFunction(Function &F) {
1028
26
  auto &SI = *getAnalysis<ScopInfoWrapperPass>().getSI();
1029
26
  for (auto &It : SI) {
1030
25
    assert(It.second && "Invalid SCoP object!");
1031
25
    recomputeDependences(It.second.get(), Dependences::AL_Access);
1032
25
  }
1033
26
  return false;
1034
26
}
1035
1036
7
void DependenceInfoWrapperPass::print(raw_ostream &OS, const Module *M) const {
1037
7
  for (auto &It : ScopToDepsMap) {
1038
6
    assert((It.first && It.second) && "Invalid Scop or Dependence object!\n");
1039
6
    It.second->print(OS);
1040
6
  }
1041
7
}
1042
1043
26
void DependenceInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1044
26
  AU.addRequiredTransitive<ScopInfoWrapperPass>();
1045
26
  AU.setPreservesAll();
1046
26
}
1047
1048
char DependenceInfoWrapperPass::ID = 0;
1049
1050
0
Pass *polly::createDependenceInfoWrapperPassPass() {
1051
0
  return new DependenceInfoWrapperPass();
1052
0
}
1053
1054
37.2k
INITIALIZE_PASS_BEGIN(
1055
37.2k
    DependenceInfoWrapperPass, "polly-function-dependences",
1056
37.2k
    "Polly - Calculate dependences for all the SCoPs of a function", false,
1057
37.2k
    false)
1058
37.2k
INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass);
1059
37.2k
INITIALIZE_PASS_END(
1060
    DependenceInfoWrapperPass, "polly-function-dependences",
1061
    "Polly - Calculate dependences for all the SCoPs of a function", false,
1062
    false)