Coverage Report

Created: 2017-11-21 16:49

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