Coverage Report

Created: 2017-04-27 19:33

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