Coverage Report

Created: 2018-10-23 09:19

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/include/polly/DependenceInfo.h
Line
Count
Source (jump to first uncovered line)
1
//===--- polly/DependenceInfo.h - Polyhedral dependency analysis *- C++ -*-===//
2
//
3
//                     The LLVM Compiler Infrastructure
4
//
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
7
//
8
//===----------------------------------------------------------------------===//
9
//
10
// Calculate the data dependency relations for a Scop using ISL.
11
//
12
// The integer set library (ISL) from Sven has an integrated dependency analysis
13
// to calculate data dependences. This pass takes advantage of this and
14
// calculates those dependences of 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
#ifndef POLLY_DEPENDENCE_INFO_H
24
#define POLLY_DEPENDENCE_INFO_H
25
26
#include "polly/ScopPass.h"
27
#include "isl/ctx.h"
28
#include "isl/isl-noexceptions.h"
29
30
struct isl_pw_aff;
31
struct isl_union_map;
32
struct isl_union_set;
33
struct isl_map;
34
struct isl_set;
35
struct clast_for;
36
37
using namespace llvm;
38
39
namespace polly {
40
41
class Scop;
42
class ScopStmt;
43
class MemoryAccess;
44
45
/// The accumulated dependence information for a SCoP.
46
///
47
/// The Dependences struct holds all dependence information we collect and
48
/// compute for one SCoP. It also offers an interface that allows users to
49
/// query only specific parts.
50
struct Dependences {
51
  // Granularities of the current dependence analysis
52
  enum AnalysisLevel {
53
    AL_Statement = 0,
54
    // Distinguish accessed memory references in the same statement
55
    AL_Reference,
56
    // Distinguish memory access instances in the same statement
57
    AL_Access,
58
59
    NumAnalysisLevels
60
  };
61
62
  /// Map type for reduction dependences.
63
  using ReductionDependencesMapTy = DenseMap<MemoryAccess *, isl_map *>;
64
65
  /// Map type to associate statements with schedules.
66
  using StatementToIslMapTy = DenseMap<ScopStmt *, isl::map>;
67
68
  /// The type of the dependences.
69
  ///
70
  /// Reduction dependences are separated from RAW/WAW/WAR dependences because
71
  /// we can ignore them during the scheduling. That's because the order
72
  /// in which the reduction statements are executed does not matter. However,
73
  /// if they are executed in parallel we need to take additional measures
74
  /// (e.g, privatization) to ensure a correct result. The (reverse) transitive
75
  /// closure of the reduction dependences are used to check for parallel
76
  /// executed reduction statements during code generation. These dependences
77
  /// connect all instances of a reduction with each other, they are therefore
78
  /// cyclic and possibly "reversed".
79
  enum Type {
80
    // Write after read
81
    TYPE_WAR = 1 << 0,
82
83
    // Read after write
84
    TYPE_RAW = 1 << 1,
85
86
    // Write after write
87
    TYPE_WAW = 1 << 2,
88
89
    // Reduction dependences
90
    TYPE_RED = 1 << 3,
91
92
    // Transitive closure of the reduction dependences (& the reverse)
93
    TYPE_TC_RED = 1 << 4,
94
  };
95
96
487
  const std::shared_ptr<isl_ctx> &getSharedIslCtx() const { return IslCtx; }
97
98
  /// Get the dependences of type @p Kinds.
99
  ///
100
  /// @param Kinds This integer defines the different kinds of dependences
101
  ///              that will be returned. To return more than one kind, the
102
  ///              different kinds are 'ored' together.
103
  isl::union_map getDependences(int Kinds) const;
104
105
  /// Report if valid dependences are available.
106
  bool hasValidDependences() const;
107
108
  /// Return the reduction dependences caused by @p MA.
109
  ///
110
  /// @return The reduction dependences caused by @p MA or nullptr if none.
111
  __isl_give isl_map *getReductionDependences(MemoryAccess *MA) const;
112
113
  /// Return all reduction dependences.
114
26
  const ReductionDependencesMapTy &getReductionDependences() const {
115
26
    return ReductionDependences;
116
26
  }
117
118
  /// Check if a partial schedule is parallel wrt to @p Deps.
119
  ///
120
  /// @param Schedule       The subset of the schedule space that we want to
121
  ///                       check.
122
  /// @param Deps           The dependences @p Schedule needs to respect.
123
  /// @param MinDistancePtr If not nullptr, the minimal dependence distance will
124
  ///                       be returned at the address of that pointer
125
  ///
126
  /// @return Returns true, if executing parallel the outermost dimension of
127
  ///         @p Schedule is valid according to the dependences @p Deps.
128
  bool isParallel(__isl_keep isl_union_map *Schedule,
129
                  __isl_take isl_union_map *Deps,
130
                  __isl_give isl_pw_aff **MinDistancePtr = nullptr) const;
131
132
  /// Check if a new schedule is valid.
133
  ///
134
  /// @param S             The current SCoP.
135
  /// @param NewSchedules  The new schedules
136
  ///
137
  /// @return True if the new schedule is valid, false if it reverses
138
  ///         dependences.
139
  bool isValidSchedule(Scop &S, const StatementToIslMapTy &NewSchedules) const;
140
141
  /// Print the stored dependence information.
142
  void print(llvm::raw_ostream &OS) const;
143
144
  /// Dump the dependence information stored to the dbgs stream.
145
  void dump() const;
146
147
  /// Return the granularity of this dependence analysis.
148
33
  AnalysisLevel getDependenceLevel() { return Level; }
149
150
  /// Allow the DependenceInfo access to private members and methods.
151
  ///
152
  /// To restrict access to the internal state, only the DependenceInfo class
153
  /// is able to call or modify a Dependences struct.
154
  friend struct DependenceAnalysis;
155
  friend struct DependenceInfoPrinterPass;
156
  friend class DependenceInfo;
157
  friend class DependenceInfoWrapperPass;
158
159
  /// Destructor that will free internal objects.
160
582
  ~Dependences() { releaseMemory(); }
161
162
private:
163
  /// Create an empty dependences struct.
164
  explicit Dependences(const std::shared_ptr<isl_ctx> &IslCtx,
165
                       AnalysisLevel Level)
166
      : RAW(nullptr), WAR(nullptr), WAW(nullptr), RED(nullptr), TC_RED(nullptr),
167
604
        IslCtx(IslCtx), Level(Level) {}
168
169
  /// Calculate and add at the privatization dependences.
170
  void addPrivatizationDependences();
171
172
  /// Calculate the dependences for a certain SCoP @p S.
173
  void calculateDependences(Scop &S);
174
175
  /// Set the reduction dependences for @p MA to @p Deps.
176
  void setReductionDependences(MemoryAccess *MA, __isl_take isl_map *Deps);
177
178
  /// Free the objects associated with this Dependences struct.
179
  ///
180
  /// The Dependences struct will again be "empty" afterwards.
181
  void releaseMemory();
182
183
  /// The different basic kinds of dependences we calculate.
184
  isl_union_map *RAW;
185
  isl_union_map *WAR;
186
  isl_union_map *WAW;
187
188
  /// The special reduction dependences.
189
  isl_union_map *RED;
190
191
  /// The (reverse) transitive closure of reduction dependences.
192
  isl_union_map *TC_RED;
193
194
  /// Mapping from memory accesses to their reduction dependences.
195
  ReductionDependencesMapTy ReductionDependences;
196
197
  /// Isl context from the SCoP.
198
  std::shared_ptr<isl_ctx> IslCtx;
199
200
  /// Granularity of this dependence analysis.
201
  const AnalysisLevel Level;
202
};
203
204
struct DependenceAnalysis : public AnalysisInfoMixin<DependenceAnalysis> {
205
  static AnalysisKey Key;
206
  struct Result {
207
    Scop &S;
208
    std::unique_ptr<Dependences> D[Dependences::NumAnalysisLevels];
209
210
    /// Return the dependence information for the current SCoP.
211
    ///
212
    /// @param Level The granularity of dependence analysis result.
213
    ///
214
    /// @return The dependence analysis result
215
    ///
216
    const Dependences &getDependences(Dependences::AnalysisLevel Level);
217
218
    /// Recompute dependences from schedule and memory accesses.
219
    const Dependences &recomputeDependences(Dependences::AnalysisLevel Level);
220
  };
221
  Result run(Scop &S, ScopAnalysisManager &SAM,
222
             ScopStandardAnalysisResults &SAR);
223
};
224
225
struct DependenceInfoPrinterPass
226
    : public PassInfoMixin<DependenceInfoPrinterPass> {
227
0
  DependenceInfoPrinterPass(raw_ostream &OS) : OS(OS) {}
228
229
  PreservedAnalyses run(Scop &S, ScopAnalysisManager &,
230
                        ScopStandardAnalysisResults &, SPMUpdater &);
231
232
  raw_ostream &OS;
233
};
234
235
class DependenceInfo : public ScopPass {
236
public:
237
  static char ID;
238
239
  /// Construct a new DependenceInfo pass.
240
587
  DependenceInfo() : ScopPass(ID) {}
241
242
  /// Return the dependence information for the current SCoP.
243
  ///
244
  /// @param Level The granularity of dependence analysis result.
245
  ///
246
  /// @return The dependence analysis result
247
  ///
248
  const Dependences &getDependences(Dependences::AnalysisLevel Level);
249
250
  /// Recompute dependences from schedule and memory accesses.
251
  const Dependences &recomputeDependences(Dependences::AnalysisLevel Level);
252
253
  /// Compute the dependence information for the SCoP @p S.
254
  bool runOnScop(Scop &S) override;
255
256
  /// Print the dependences for the given SCoP to @p OS.
257
  void printScop(raw_ostream &OS, Scop &) const override;
258
259
  /// Release the internal memory.
260
2.24k
  void releaseMemory() override {
261
2.24k
    for (auto &d : D)
262
6.74k
      d.reset();
263
2.24k
  }
264
265
  /// Register all analyses and transformation required.
266
  void getAnalysisUsage(AnalysisUsage &AU) const override;
267
268
private:
269
  Scop *S;
270
271
  /// Dependences struct for the current SCoP.
272
  std::unique_ptr<Dependences> D[Dependences::NumAnalysisLevels];
273
};
274
275
/// Construct a new DependenceInfoWrapper pass.
276
class DependenceInfoWrapperPass : public FunctionPass {
277
public:
278
  static char ID;
279
280
  /// Construct a new DependenceInfoWrapper pass.
281
26
  DependenceInfoWrapperPass() : FunctionPass(ID) {}
282
283
  /// Return the dependence information for the given SCoP.
284
  ///
285
  /// @param S     SCoP object.
286
  /// @param Level The granularity of dependence analysis result.
287
  ///
288
  /// @return The dependence analysis result
289
  ///
290
  const Dependences &getDependences(Scop *S, Dependences::AnalysisLevel Level);
291
292
  /// Recompute dependences from schedule and memory accesses.
293
  const Dependences &recomputeDependences(Scop *S,
294
                                          Dependences::AnalysisLevel Level);
295
296
  /// Compute the dependence information on-the-fly for the function.
297
  bool runOnFunction(Function &F) override;
298
299
  /// Print the dependences for the current function to @p OS.
300
  void print(raw_ostream &OS, const Module *M = nullptr) const override;
301
302
  /// Release the internal memory.
303
26
  void releaseMemory() override { ScopToDepsMap.clear(); }
304
305
  /// Register all analyses and transformation required.
306
  void getAnalysisUsage(AnalysisUsage &AU) const override;
307
308
private:
309
  using ScopToDepsMapTy = DenseMap<Scop *, std::unique_ptr<Dependences>>;
310
311
  /// Scop to Dependence map for the current function.
312
  ScopToDepsMapTy ScopToDepsMap;
313
};
314
} // namespace polly
315
316
namespace llvm {
317
class PassRegistry;
318
void initializeDependenceInfoPass(llvm::PassRegistry &);
319
void initializeDependenceInfoWrapperPassPass(llvm::PassRegistry &);
320
} // namespace llvm
321
322
#endif