Coverage Report

Created: 2017-03-28 09:59

/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.15k
                               Dependences::AnalysisLevel TagLevel) {
104
1.15k
  if (TagLevel == Dependences::AL_Reference)
105
10
    return tag(Relation, MA->getArrayId());
106
1.15k
107
1.14k
  
if (1.14k
TagLevel == Dependences::AL_Access1.14k
)
108
116
    return tag(Relation, MA->getId());
109
1.14k
110
1.14k
  // No need to tag at the statement level.
111
1.02k
  return Relation;
112
1.14k
}
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
492
                        Dependences::AnalysisLevel Level) {
120
492
  isl_space *Space = S.getParamSpace();
121
492
  Read = isl_union_map_empty(isl_space_copy(Space));
122
492
  MustWrite = isl_union_map_empty(isl_space_copy(Space));
123
492
  MayWrite = isl_union_map_empty(isl_space_copy(Space));
124
492
  ReductionTagMap = isl_union_map_empty(isl_space_copy(Space));
125
492
  isl_union_map *StmtSchedule = isl_union_map_empty(Space);
126
492
127
492
  SmallPtrSet<const ScopArrayInfo *, 8> ReductionArrays;
128
492
  if (UseReductions)
129
492
    for (ScopStmt &Stmt : S)
130
746
      for (MemoryAccess *MA : Stmt)
131
1.40k
        
if (1.40k
MA->isReductionLike()1.40k
)
132
285
          ReductionArrays.insert(MA->getScopArrayInfo());
133
492
134
746
  for (ScopStmt &Stmt : S) {
135
1.40k
    for (MemoryAccess *MA : Stmt) {
136
1.40k
      isl_set *domcp = Stmt.getDomain();
137
1.40k
      isl_map *accdom = MA->getAccessRelation();
138
1.40k
139
1.40k
      accdom = isl_map_intersect_domain(accdom, domcp);
140
1.40k
141
1.40k
      if (
ReductionArrays.count(MA->getScopArrayInfo())1.40k
)
{312
142
312
        // Wrap the access domain and adjust the schedule accordingly.
143
312
        //
144
312
        // An access domain like
145
312
        //   Stmt[i0, i1] -> MemAcc_A[i0 + i1]
146
312
        // will be transformed into
147
312
        //   [Stmt[i0, i1] -> MemAcc_A[i0 + i1]] -> MemAcc_A[i0 + i1]
148
312
        //
149
312
        // We collect all the access domains in the ReductionTagMap.
150
312
        // This is used in Dependences::calculateDependences to create
151
312
        // a tagged Schedule tree.
152
312
153
312
        ReductionTagMap =
154
312
            isl_union_map_add_map(ReductionTagMap, isl_map_copy(accdom));
155
312
        accdom = isl_map_range_map(accdom);
156
1.09k
      } else {
157
1.09k
        accdom = tag(accdom, MA, Level);
158
1.09k
        if (
Level > Dependences::AL_Statement1.09k
)
{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.09k
      }
167
1.40k
168
1.40k
      if (MA->isRead())
169
581
        Read = isl_union_map_add_map(Read, accdom);
170
822
      else 
if (822
MA->isMayWrite()822
)
171
23
        MayWrite = isl_union_map_add_map(MayWrite, accdom);
172
822
      else
173
799
        MustWrite = isl_union_map_add_map(MustWrite, accdom);
174
1.40k
    }
175
746
176
746
    if (
!ReductionArrays.empty() && 746
Level == Dependences::AL_Statement154
)
177
138
      StmtSchedule = isl_union_map_add_map(StmtSchedule, Stmt.getSchedule());
178
746
  }
179
492
180
492
  StmtSchedule =
181
492
      isl_union_map_intersect_params(StmtSchedule, S.getAssumedContext());
182
492
  TaggedStmtDomain = isl_union_map_domain(StmtSchedule);
183
492
184
492
  ReductionTagMap = isl_union_map_coalesce(ReductionTagMap);
185
492
  Read = isl_union_map_coalesce(Read);
186
492
  MustWrite = isl_union_map_coalesce(MustWrite);
187
492
  MayWrite = isl_union_map_coalesce(MayWrite);
188
492
}
189
190
/// Fix all dimension of @p Zero to 0 and add it to @p user
191
73
static isl_stat fixSetToZero(__isl_take isl_set *Zero, void *user) {
192
73
  isl_union_set **User = (isl_union_set **)user;
193
284
  for (unsigned i = 0; 
i < isl_set_dim(Zero, isl_dim_set)284
;
i++211
)
194
211
    Zero = isl_set_fix_si(Zero, isl_dim_set, i, 0);
195
73
  *User = isl_union_set_add_set(*User, Zero);
196
73
  return isl_stat_ok;
197
73
}
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
53
void Dependences::addPrivatizationDependences() {
243
53
  isl_union_map *PrivRAW, *PrivWAW, *PrivWAR;
244
53
245
53
  // The transitive closure might be over approximated, thus could lead to
246
53
  // dependency cycles in the privatization dependences. To make sure this
247
53
  // will not happen we remove all negative dependences after we computed
248
53
  // the transitive closure.
249
53
  TC_RED = isl_union_map_transitive_closure(isl_union_map_copy(RED), nullptr);
250
53
251
53
  // FIXME: Apply the current schedule instead of assuming the identity schedule
252
53
  //        here. The current approach is only valid as long as we compute the
253
53
  //        dependences only with the initial (identity schedule). Any other
254
53
  //        schedule could change "the direction of the backward dependences" we
255
53
  //        want to eliminate here.
256
53
  isl_union_set *UDeltas = isl_union_map_deltas(isl_union_map_copy(TC_RED));
257
53
  isl_union_set *Universe = isl_union_set_universe(isl_union_set_copy(UDeltas));
258
53
  isl_union_set *Zero = isl_union_set_empty(isl_union_set_get_space(Universe));
259
53
  isl_union_set_foreach_set(Universe, fixSetToZero, &Zero);
260
53
  isl_union_map *NonPositive = isl_union_set_lex_le_union_set(UDeltas, Zero);
261
53
262
53
  TC_RED = isl_union_map_subtract(TC_RED, NonPositive);
263
53
264
53
  TC_RED = isl_union_map_union(
265
53
      TC_RED, isl_union_map_reverse(isl_union_map_copy(TC_RED)));
266
53
  TC_RED = isl_union_map_coalesce(TC_RED);
267
53
268
53
  isl_union_map **Maps[] = {&RAW, &WAW, &WAR};
269
53
  isl_union_map **PrivMaps[] = {&PrivRAW, &PrivWAW, &PrivWAR};
270
212
  for (unsigned u = 0; 
u < 3212
;
u++159
)
{159
271
159
    isl_union_map **Map = Maps[u], **PrivMap = PrivMaps[u];
272
159
273
159
    *PrivMap = isl_union_map_apply_range(isl_union_map_copy(*Map),
274
159
                                         isl_union_map_copy(TC_RED));
275
159
    *PrivMap = isl_union_map_union(
276
159
        *PrivMap, isl_union_map_apply_range(isl_union_map_copy(TC_RED),
277
159
                                            isl_union_map_copy(*Map)));
278
159
279
159
    *Map = isl_union_map_union(*Map, *PrivMap);
280
159
  }
281
53
282
53
  isl_union_set_free(Universe);
283
53
}
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
990
                                            __isl_keep isl_schedule *Schedule) {
289
990
  isl_union_access_info *AI;
290
990
291
990
  AI = isl_union_access_info_from_sink(isl_union_map_copy(Snk));
292
990
  AI = isl_union_access_info_set_may_source(AI, isl_union_map_copy(MaySrc));
293
990
  if (Src)
294
972
    AI = isl_union_access_info_set_must_source(AI, isl_union_map_copy(Src));
295
990
  AI = isl_union_access_info_set_schedule(AI, isl_schedule_copy(Schedule));
296
990
  auto Flow = isl_union_access_info_compute_flow(AI);
297
990
  DEBUG(if (!Flow) dbgs() << "last error: "
298
990
                          << isl_ctx_last_error(isl_schedule_get_ctx(Schedule))
299
990
                          << '\n';);
300
990
  return Flow;
301
990
}
302
303
492
void Dependences::calculateDependences(Scop &S) {
304
492
  isl_union_map *Read, *MustWrite, *MayWrite, *ReductionTagMap;
305
492
  isl_schedule *Schedule;
306
492
  isl_union_set *TaggedStmtDomain;
307
492
308
492
  DEBUG(dbgs() << "Scop: \n" << S << "\n");
309
492
310
492
  collectInfo(S, Read, MustWrite, MayWrite, ReductionTagMap, TaggedStmtDomain,
311
492
              Level);
312
492
313
492
  bool HasReductions = !isl_union_map_is_empty(ReductionTagMap);
314
492
315
492
  DEBUG(dbgs() << "Read: " << Read << '\n';
316
492
        dbgs() << "MustWrite: " << MustWrite << '\n';
317
492
        dbgs() << "MayWrite: " << MayWrite << '\n';
318
492
        dbgs() << "ReductionTagMap: " << ReductionTagMap << '\n';
319
492
        dbgs() << "TaggedStmtDomain: " << TaggedStmtDomain << '\n';);
320
492
321
492
  Schedule = S.getScheduleTree();
322
492
323
492
  if (
!HasReductions492
)
{407
324
407
    isl_union_map_free(ReductionTagMap);
325
407
    // Tag the schedule tree if we want fine-grain dependence info
326
407
    if (
Level > AL_Statement407
)
{23
327
23
      auto TaggedMap =
328
23
          isl_union_set_unwrap(isl_union_set_copy(TaggedStmtDomain));
329
23
      auto Tags = isl_union_map_domain_map_union_pw_multi_aff(TaggedMap);
330
23
      Schedule = isl_schedule_pullback_union_pw_multi_aff(Schedule, Tags);
331
23
    }
332
85
  } else {
333
85
    isl_union_map *IdentityMap;
334
85
    isl_union_pw_multi_aff *ReductionTags, *IdentityTags, *Tags;
335
85
336
85
    // Extract Reduction tags from the combined access domains in the given
337
85
    // SCoP. The result is a map that maps each tagged element in the domain to
338
85
    // the memory location it accesses. ReductionTags = {[Stmt[i] ->
339
85
    // Array[f(i)]] -> Stmt[i] }
340
85
    ReductionTags =
341
85
        isl_union_map_domain_map_union_pw_multi_aff(ReductionTagMap);
342
85
343
85
    // Compute an identity map from each statement in domain to itself.
344
85
    // IdentityTags = { [Stmt[i] -> Stmt[i] }
345
85
    IdentityMap = isl_union_set_identity(isl_union_set_copy(TaggedStmtDomain));
346
85
    IdentityTags = isl_union_pw_multi_aff_from_union_map(IdentityMap);
347
85
348
85
    Tags = isl_union_pw_multi_aff_union_add(ReductionTags, IdentityTags);
349
85
350
85
    // By pulling back Tags from Schedule, we have a schedule tree that can
351
85
    // be used to compute normal dependences, as well as 'tagged' reduction
352
85
    // dependences.
353
85
    Schedule = isl_schedule_pullback_union_pw_multi_aff(Schedule, Tags);
354
85
  }
355
492
356
492
  DEBUG(dbgs() << "Read: " << Read << "\n";
357
492
        dbgs() << "MustWrite: " << MustWrite << "\n";
358
492
        dbgs() << "MayWrite: " << MayWrite << "\n";
359
492
        dbgs() << "Schedule: " << Schedule << "\n");
360
492
361
492
  {
362
492
    IslMaxOperationsGuard MaxOpGuard(IslCtx.get(), OptComputeOut);
363
492
364
492
    RAW = WAW = WAR = RED = nullptr;
365
492
366
492
    if (
OptAnalysisType == VALUE_BASED_ANALYSIS492
)
{486
367
486
      isl_union_flow *Flow;
368
486
369
486
      Flow = buildFlow(Read, MustWrite, MayWrite, Schedule);
370
486
371
486
      RAW = isl_union_flow_get_may_dependence(Flow);
372
486
      isl_union_flow_free(Flow);
373
486
374
486
      Flow = buildFlow(MustWrite, MustWrite, Read, Schedule);
375
486
376
486
      WAW = isl_union_flow_get_must_dependence(Flow);
377
486
      WAR = isl_union_flow_get_may_dependence(Flow);
378
486
379
486
      // This subtraction is needed to obtain the same results as were given by
380
486
      // isl_union_map_compute_flow. For large sets this may add some
381
486
      // compile-time cost. As there does not seem to be a need to distinguish
382
486
      // between WAW and WAR, refactoring Polly to only track general non-flow
383
486
      // dependences may improve performance.
384
486
      WAR = isl_union_map_subtract(WAR, isl_union_map_copy(WAW));
385
486
386
486
      isl_union_flow_free(Flow);
387
486
      isl_schedule_free(Schedule);
388
6
    } else {
389
6
      isl_union_flow *Flow;
390
6
391
6
      isl_union_map *Write = isl_union_map_union(isl_union_map_copy(MustWrite),
392
6
                                                 isl_union_map_copy(MayWrite));
393
6
394
6
      Flow = buildFlow(Read, nullptr, Write, Schedule);
395
6
396
6
      RAW = isl_union_flow_get_may_dependence(Flow);
397
6
      isl_union_flow_free(Flow);
398
6
399
6
      Flow = buildFlow(Write, nullptr, Read, Schedule);
400
6
401
6
      WAR = isl_union_flow_get_may_dependence(Flow);
402
6
      isl_union_flow_free(Flow);
403
6
404
6
      Flow = buildFlow(Write, nullptr, Write, Schedule);
405
6
406
6
      WAW = isl_union_flow_get_may_dependence(Flow);
407
6
      isl_union_flow_free(Flow);
408
6
      isl_schedule_free(Schedule);
409
6
      isl_union_map_free(Write);
410
6
    }
411
492
412
492
    isl_union_map_free(MustWrite);
413
492
    isl_union_map_free(MayWrite);
414
492
    isl_union_map_free(Read);
415
492
416
492
    RAW = isl_union_map_coalesce(RAW);
417
492
    WAW = isl_union_map_coalesce(WAW);
418
492
    WAR = isl_union_map_coalesce(WAR);
419
492
420
492
    // End of max_operations scope.
421
492
  }
422
492
423
492
  if (
isl_ctx_last_error(IslCtx.get()) == isl_error_quota492
)
{5
424
5
    isl_union_map_free(RAW);
425
5
    isl_union_map_free(WAW);
426
5
    isl_union_map_free(WAR);
427
5
    RAW = WAW = WAR = nullptr;
428
5
    isl_ctx_reset_error(IslCtx.get());
429
5
  }
430
492
431
492
  // Drop out early, as the remaining computations are only needed for
432
492
  // reduction dependences or dependences that are finer than statement
433
492
  // level dependences.
434
492
  if (
!HasReductions && 492
Level == AL_Statement407
)
{384
435
384
    RED = isl_union_map_empty(isl_union_map_get_space(RAW));
436
384
    TC_RED = isl_union_map_empty(isl_union_set_get_space(TaggedStmtDomain));
437
384
    isl_union_set_free(TaggedStmtDomain);
438
384
    return;
439
384
  }
440
492
441
108
  isl_union_map *STMT_RAW, *STMT_WAW, *STMT_WAR;
442
108
  STMT_RAW = isl_union_map_intersect_domain(
443
108
      isl_union_map_copy(RAW), isl_union_set_copy(TaggedStmtDomain));
444
108
  STMT_WAW = isl_union_map_intersect_domain(
445
108
      isl_union_map_copy(WAW), isl_union_set_copy(TaggedStmtDomain));
446
108
  STMT_WAR =
447
108
      isl_union_map_intersect_domain(isl_union_map_copy(WAR), TaggedStmtDomain);
448
108
  DEBUG({
449
108
    dbgs() << "Wrapped Dependences:\n";
450
108
    dump();
451
108
    dbgs() << "\n";
452
108
  });
453
108
454
108
  // To handle reduction dependences we proceed as follows:
455
108
  // 1) Aggregate all possible reduction dependences, namely all self
456
108
  //    dependences on reduction like statements.
457
108
  // 2) Intersect them with the actual RAW & WAW dependences to the get the
458
108
  //    actual reduction dependences. This will ensure the load/store memory
459
108
  //    addresses were __identical__ in the two iterations of the statement.
460
108
  // 3) Relax the original RAW and WAW dependences by subtracting the actual
461
108
  //    reduction dependences. Binary reductions (sum += A[i]) cause both, and
462
108
  //    the same, RAW and WAW dependences.
463
108
  // 4) Add the privatization dependences which are widened versions of
464
108
  //    already present dependences. They model the effect of manual
465
108
  //    privatization at the outermost possible place (namely after the last
466
108
  //    write and before the first access to a reduction location).
467
108
468
108
  // Step 1)
469
108
  RED = isl_union_map_empty(isl_union_map_get_space(RAW));
470
191
  for (ScopStmt &Stmt : S) {
471
412
    for (MemoryAccess *MA : Stmt) {
472
412
      if (!MA->isReductionLike())
473
127
        continue;
474
285
      isl_set *AccDomW = isl_map_wrap(MA->getAccessRelation());
475
285
      isl_map *Identity =
476
285
          isl_map_from_domain_and_range(isl_set_copy(AccDomW), AccDomW);
477
285
      RED = isl_union_map_add_map(RED, Identity);
478
285
    }
479
191
  }
480
108
481
108
  // Step 2)
482
108
  RED = isl_union_map_intersect(RED, isl_union_map_copy(RAW));
483
108
  RED = isl_union_map_intersect(RED, isl_union_map_copy(WAW));
484
108
485
108
  if (
!isl_union_map_is_empty(RED)108
)
{53
486
53
487
53
    // Step 3)
488
53
    RAW = isl_union_map_subtract(RAW, isl_union_map_copy(RED));
489
53
    WAW = isl_union_map_subtract(WAW, isl_union_map_copy(RED));
490
53
491
53
    // Step 4)
492
53
    addPrivatizationDependences();
493
53
  }
494
108
495
108
  DEBUG({
496
108
    dbgs() << "Final Wrapped Dependences:\n";
497
108
    dump();
498
108
    dbgs() << "\n";
499
108
  });
500
108
501
108
  // RED_SIN is used to collect all reduction dependences again after we
502
108
  // split them according to the causing memory accesses. The current assumption
503
108
  // is that our method of splitting will not have any leftovers. In the end
504
108
  // we validate this assumption until we have more confidence in this method.
505
108
  isl_union_map *RED_SIN = isl_union_map_empty(isl_union_map_get_space(RAW));
506
108
507
108
  // For each reduction like memory access, check if there are reduction
508
108
  // dependences with the access relation of the memory access as a domain
509
108
  // (wrapped space!). If so these dependences are caused by this memory access.
510
108
  // We then move this portion of reduction dependences back to the statement ->
511
108
  // statement space and add a mapping from the memory access to these
512
108
  // dependences.
513
191
  for (ScopStmt &Stmt : S) {
514
412
    for (MemoryAccess *MA : Stmt) {
515
412
      if (!MA->isReductionLike())
516
127
        continue;
517
412
518
285
      isl_set *AccDomW = isl_map_wrap(MA->getAccessRelation());
519
285
      isl_union_map *AccRedDepU = isl_union_map_intersect_domain(
520
285
          isl_union_map_copy(TC_RED), isl_union_set_from_set(AccDomW));
521
285
      if (
isl_union_map_is_empty(AccRedDepU)285
)
{139
522
139
        isl_union_map_free(AccRedDepU);
523
139
        continue;
524
139
      }
525
285
526
146
      isl_map *AccRedDep = isl_map_from_union_map(AccRedDepU);
527
146
      RED_SIN = isl_union_map_add_map(RED_SIN, isl_map_copy(AccRedDep));
528
146
      AccRedDep = isl_map_zip(AccRedDep);
529
146
      AccRedDep = isl_set_unwrap(isl_map_domain(AccRedDep));
530
146
      setReductionDependences(MA, AccRedDep);
531
146
    }
532
191
  }
533
108
534
108
  assert(isl_union_map_is_equal(RED_SIN, TC_RED) &&
535
108
         "Intersecting the reduction dependence domain with the wrapped access "
536
108
         "relation is not enough, we need to loosen the access relation also");
537
108
  isl_union_map_free(RED_SIN);
538
108
539
108
  RAW = isl_union_map_zip(RAW);
540
108
  WAW = isl_union_map_zip(WAW);
541
108
  WAR = isl_union_map_zip(WAR);
542
108
  RED = isl_union_map_zip(RED);
543
108
  TC_RED = isl_union_map_zip(TC_RED);
544
108
545
108
  DEBUG({
546
108
    dbgs() << "Zipped Dependences:\n";
547
108
    dump();
548
108
    dbgs() << "\n";
549
108
  });
550
108
551
108
  RAW = isl_union_set_unwrap(isl_union_map_domain(RAW));
552
108
  WAW = isl_union_set_unwrap(isl_union_map_domain(WAW));
553
108
  WAR = isl_union_set_unwrap(isl_union_map_domain(WAR));
554
108
  RED = isl_union_set_unwrap(isl_union_map_domain(RED));
555
108
  TC_RED = isl_union_set_unwrap(isl_union_map_domain(TC_RED));
556
108
557
108
  DEBUG({
558
108
    dbgs() << "Unwrapped Dependences:\n";
559
108
    dump();
560
108
    dbgs() << "\n";
561
108
  });
562
108
563
108
  RAW = isl_union_map_union(RAW, STMT_RAW);
564
108
  WAW = isl_union_map_union(WAW, STMT_WAW);
565
108
  WAR = isl_union_map_union(WAR, STMT_WAR);
566
108
567
108
  RAW = isl_union_map_coalesce(RAW);
568
108
  WAW = isl_union_map_coalesce(WAW);
569
108
  WAR = isl_union_map_coalesce(WAR);
570
108
  RED = isl_union_map_coalesce(RED);
571
108
  TC_RED = isl_union_map_coalesce(TC_RED);
572
108
573
108
  DEBUG(dump());
574
108
}
575
576
bool Dependences::isValidSchedule(Scop &S,
577
41
                                  StatementToIslMapTy *NewSchedule) const {
578
41
  if (LegalityCheckDisabled)
579
0
    return true;
580
41
581
41
  isl_union_map *Dependences = getDependences(TYPE_RAW | TYPE_WAW | TYPE_WAR);
582
41
  isl_space *Space = S.getParamSpace();
583
41
  isl_union_map *Schedule = isl_union_map_empty(Space);
584
41
585
41
  isl_space *ScheduleSpace = nullptr;
586
41
587
57
  for (ScopStmt &Stmt : S) {
588
57
    isl_map *StmtScat;
589
57
590
57
    if (NewSchedule->find(&Stmt) == NewSchedule->end())
591
0
      StmtScat = Stmt.getSchedule();
592
57
    else
593
57
      StmtScat = isl_map_copy((*NewSchedule)[&Stmt]);
594
57
    assert(StmtScat &&
595
57
           "Schedules that contain extension nodes require special handling.");
596
57
597
57
    if (!ScheduleSpace)
598
41
      ScheduleSpace = isl_space_range(isl_map_get_space(StmtScat));
599
57
600
57
    Schedule = isl_union_map_add_map(Schedule, StmtScat);
601
57
  }
602
41
603
41
  Dependences =
604
41
      isl_union_map_apply_domain(Dependences, isl_union_map_copy(Schedule));
605
41
  Dependences = isl_union_map_apply_range(Dependences, Schedule);
606
41
607
41
  isl_set *Zero = isl_set_universe(isl_space_copy(ScheduleSpace));
608
166
  for (unsigned i = 0; 
i < isl_set_dim(Zero, isl_dim_set)166
;
i++125
)
609
125
    Zero = isl_set_fix_si(Zero, isl_dim_set, i, 0);
610
41
611
41
  isl_union_set *UDeltas = isl_union_map_deltas(Dependences);
612
41
  isl_set *Deltas = isl_union_set_extract_set(UDeltas, ScheduleSpace);
613
41
  isl_union_set_free(UDeltas);
614
41
615
41
  isl_map *NonPositive = isl_set_lex_le_set(Deltas, Zero);
616
41
  bool IsValid = isl_map_is_empty(NonPositive);
617
41
  isl_map_free(NonPositive);
618
41
619
41
  return IsValid;
620
41
}
621
622
// Check if the current scheduling dimension is parallel.
623
//
624
// We check for parallelism by verifying that the loop does not carry any
625
// dependences.
626
//
627
// Parallelism test: if the distance is zero in all outer dimensions, then it
628
// has to be zero in the current dimension as well.
629
//
630
// Implementation: first, translate dependences into time space, then force
631
// outer dimensions to be equal. If the distance is zero in the current
632
// dimension, then the loop is parallel. The distance is zero in the current
633
// dimension if it is a subset of a map with equal values for the current
634
// dimension.
635
bool Dependences::isParallel(isl_union_map *Schedule, isl_union_map *Deps,
636
381
                             isl_pw_aff **MinDistancePtr) const {
637
381
  isl_set *Deltas, *Distance;
638
381
  isl_map *ScheduleDeps;
639
381
  unsigned Dimension;
640
381
  bool IsParallel;
641
381
642
381
  Deps = isl_union_map_apply_range(Deps, isl_union_map_copy(Schedule));
643
381
  Deps = isl_union_map_apply_domain(Deps, isl_union_map_copy(Schedule));
644
381
645
381
  if (
isl_union_map_is_empty(Deps)381
)
{226
646
226
    isl_union_map_free(Deps);
647
226
    return true;
648
226
  }
649
381
650
155
  ScheduleDeps = isl_map_from_union_map(Deps);
651
155
  Dimension = isl_map_dim(ScheduleDeps, isl_dim_out) - 1;
652
155
653
250
  for (unsigned i = 0; 
i < Dimension250
;
i++95
)
654
95
    ScheduleDeps = isl_map_equate(ScheduleDeps, isl_dim_out, i, isl_dim_in, i);
655
155
656
155
  Deltas = isl_map_deltas(ScheduleDeps);
657
155
  Distance = isl_set_universe(isl_set_get_space(Deltas));
658
155
659
155
  // [0, ..., 0, +] - All zeros and last dimension larger than zero
660
250
  for (unsigned i = 0; 
i < Dimension250
;
i++95
)
661
95
    Distance = isl_set_fix_si(Distance, isl_dim_set, i, 0);
662
155
663
155
  Distance = isl_set_lower_bound_si(Distance, isl_dim_set, Dimension, 1);
664
155
  Distance = isl_set_intersect(Distance, Deltas);
665
155
666
155
  IsParallel = isl_set_is_empty(Distance);
667
155
  if (
IsParallel || 155
!MinDistancePtr120
)
{127
668
127
    isl_set_free(Distance);
669
127
    return IsParallel;
670
127
  }
671
155
672
28
  Distance = isl_set_project_out(Distance, isl_dim_set, 0, Dimension);
673
28
  Distance = isl_set_coalesce(Distance);
674
28
675
28
  // This last step will compute a expression for the minimal value in the
676
28
  // distance polyhedron Distance with regards to the first (outer most)
677
28
  // dimension.
678
28
  *MinDistancePtr = isl_pw_aff_coalesce(isl_set_dim_min(Distance, 0));
679
28
680
28
  return false;
681
155
}
682
683
260
static void printDependencyMap(raw_ostream &OS, __isl_keep isl_union_map *DM) {
684
260
  if (DM)
685
239
    OS << DM << "\n";
686
260
  else
687
21
    OS << "n/a\n";
688
260
}
689
690
52
void Dependences::print(raw_ostream &OS) const {
691
52
  OS << "\tRAW dependences:\n\t\t";
692
52
  printDependencyMap(OS, RAW);
693
52
  OS << "\tWAR dependences:\n\t\t";
694
52
  printDependencyMap(OS, WAR);
695
52
  OS << "\tWAW dependences:\n\t\t";
696
52
  printDependencyMap(OS, WAW);
697
52
  OS << "\tReduction dependences:\n\t\t";
698
52
  printDependencyMap(OS, RED);
699
52
  OS << "\tTransitive closure of reduction dependences:\n\t\t";
700
52
  printDependencyMap(OS, TC_RED);
701
52
}
702
703
0
void Dependences::dump() const { print(dbgs()); }
704
705
492
void Dependences::releaseMemory() {
706
492
  isl_union_map_free(RAW);
707
492
  isl_union_map_free(WAR);
708
492
  isl_union_map_free(WAW);
709
492
  isl_union_map_free(RED);
710
492
  isl_union_map_free(TC_RED);
711
492
712
492
  RED = RAW = WAR = WAW = TC_RED = nullptr;
713
492
714
492
  for (auto &ReductionDeps : ReductionDependences)
715
146
    isl_map_free(ReductionDeps.second);
716
492
  ReductionDependences.clear();
717
492
}
718
719
471
__isl_give isl_union_map *Dependences::getDependences(int Kinds) const {
720
471
  assert(hasValidDependences() && "No valid dependences available");
721
471
  isl_space *Space = isl_union_map_get_space(RAW);
722
471
  isl_union_map *Deps = isl_union_map_empty(Space);
723
471
724
471
  if (Kinds & TYPE_RAW)
725
317
    Deps = isl_union_map_union(Deps, isl_union_map_copy(RAW));
726
471
727
471
  if (Kinds & TYPE_WAR)
728
310
    Deps = isl_union_map_union(Deps, isl_union_map_copy(WAR));
729
471
730
471
  if (Kinds & TYPE_WAW)
731
300
    Deps = isl_union_map_union(Deps, isl_union_map_copy(WAW));
732
471
733
471
  if (Kinds & TYPE_RED)
734
50
    Deps = isl_union_map_union(Deps, isl_union_map_copy(RED));
735
471
736
471
  if (Kinds & TYPE_TC_RED)
737
134
    Deps = isl_union_map_union(Deps, isl_union_map_copy(TC_RED));
738
471
739
471
  Deps = isl_union_map_coalesce(Deps);
740
471
  Deps = isl_union_map_detect_equalities(Deps);
741
471
  return Deps;
742
471
}
743
744
237
bool Dependences::hasValidDependences() const {
745
234
  return (RAW != nullptr) && 
(WAR != nullptr)234
&&
(WAW != nullptr)234
;
746
237
}
747
748
__isl_give isl_map *
749
0
Dependences::getReductionDependences(MemoryAccess *MA) const {
750
0
  return isl_map_copy(ReductionDependences.lookup(MA));
751
0
}
752
753
146
void Dependences::setReductionDependences(MemoryAccess *MA, isl_map *D) {
754
146
  assert(ReductionDependences.count(MA) == 0 &&
755
146
         "Reduction dependences set twice!");
756
146
  ReductionDependences[MA] = D;
757
146
}
758
759
const Dependences &
760
488
DependenceInfo::getDependences(Dependences::AnalysisLevel Level) {
761
488
  if (Dependences *d = D[Level].get())
762
72
    return *d;
763
488
764
416
  return recomputeDependences(Level);
765
488
}
766
767
const Dependences &
768
421
DependenceInfo::recomputeDependences(Dependences::AnalysisLevel Level) {
769
421
  D[Level].reset(new Dependences(S->getSharedIslCtx(), Level));
770
421
  D[Level]->calculateDependences(*S);
771
421
  return *D[Level];
772
421
}
773
774
462
bool DependenceInfo::runOnScop(Scop &ScopVar) {
775
462
  S = &ScopVar;
776
462
  return false;
777
462
}
778
779
/// Print the dependences for the given SCoP to @p OS.
780
781
46
void polly::DependenceInfo::printScop(raw_ostream &OS, Scop &S) const {
782
46
  if (auto 
d46
= D[OptAnalysisLevel].get())
{0
783
0
    d->print(OS);
784
0
    return;
785
0
  }
786
46
787
46
  // Otherwise create the dependences on-the-fly and print it
788
46
  Dependences D(S.getSharedIslCtx(), OptAnalysisLevel);
789
46
  D.calculateDependences(S);
790
46
  D.print(OS);
791
46
}
792
793
478
void DependenceInfo::getAnalysisUsage(AnalysisUsage &AU) const {
794
478
  AU.addRequiredTransitive<ScopInfoRegionPass>();
795
478
  AU.setPreservesAll();
796
478
}
797
798
char DependenceInfo::ID = 0;
799
800
0
Pass *polly::createDependenceInfoPass() { return new DependenceInfo(); }
801
802
39.2k
INITIALIZE_PASS_BEGIN39.2k
(DependenceInfo, "polly-dependences",39.2k
803
39.2k
                      "Polly - Calculate dependences", false, false);
804
39.2k
INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass);
805
39.2k
INITIALIZE_PASS_END(DependenceInfo, "polly-dependences",
806
                    "Polly - Calculate dependences", false, false)
807
808
//===----------------------------------------------------------------------===//
809
const Dependences &
810
DependenceInfoWrapperPass::getDependences(Scop *S,
811
33
                                          Dependences::AnalysisLevel Level) {
812
33
  auto It = ScopToDepsMap.find(S);
813
33
  if (It != ScopToDepsMap.end())
814
33
    
if (33
It->second33
)
{33
815
33
      if (It->second->getDependenceLevel() == Level)
816
33
        return *It->second.get();
817
33
    }
818
0
  return recomputeDependences(S, Level);
819
33
}
820
821
const Dependences &DependenceInfoWrapperPass::recomputeDependences(
822
25
    Scop *S, Dependences::AnalysisLevel Level) {
823
25
  std::unique_ptr<Dependences> D(new Dependences(S->getSharedIslCtx(), Level));
824
25
  D->calculateDependences(*S);
825
25
  auto Inserted = ScopToDepsMap.insert(std::make_pair(S, std::move(D)));
826
25
  return *Inserted.first->second;
827
25
}
828
829
26
bool DependenceInfoWrapperPass::runOnFunction(Function &F) {
830
26
  auto &SI = getAnalysis<ScopInfoWrapperPass>();
831
25
  for (auto &It : SI) {
832
25
    assert(It.second && "Invalid SCoP object!");
833
25
    recomputeDependences(It.second.get(), Dependences::AL_Access);
834
25
  }
835
26
  return false;
836
26
}
837
838
7
void DependenceInfoWrapperPass::print(raw_ostream &OS, const Module *M) const {
839
6
  for (auto &It : ScopToDepsMap) {
840
6
    assert((It.first && It.second) && "Invalid Scop or Dependence object!\n");
841
6
    It.second->print(OS);
842
6
  }
843
7
}
844
845
26
void DependenceInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
846
26
  AU.addRequiredTransitive<ScopInfoWrapperPass>();
847
26
  AU.setPreservesAll();
848
26
}
849
850
char DependenceInfoWrapperPass::ID = 0;
851
852
0
Pass *polly::createDependenceInfoWrapperPassPass() {
853
0
  return new DependenceInfoWrapperPass();
854
0
}
855
856
39.2k
INITIALIZE_PASS_BEGIN39.2k
(39.2k
857
39.2k
    DependenceInfoWrapperPass, "polly-function-dependences",
858
39.2k
    "Polly - Calculate dependences for all the SCoPs of a function", false,
859
39.2k
    false)
860
39.2k
INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass);
861
39.2k
INITIALIZE_PASS_END(
862
    DependenceInfoWrapperPass, "polly-function-dependences",
863
    "Polly - Calculate dependences for all the SCoPs of a function", false,
864
    false)