Coverage Report

Created: 2019-04-21 19:17

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