Coverage Report

Created: 2017-04-27 19:33

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/include/polly/DependenceInfo.h
Line
Count
Source
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
  /// Get the dependences of type @p Kinds.
96
  ///
97
  /// @param Kinds This integer defines the different kinds of dependences
98
  ///              that will be returned. To return more than one kind, the
99
  ///              different kinds are 'ored' together.
100
  __isl_give isl_union_map *getDependences(int Kinds) const;
101
102
  /// Report if valid dependences are available.
103
  bool hasValidDependences() const;
104
105
  /// Return the reduction dependences caused by @p MA.
106
  ///
107
  /// @return The reduction dependences caused by @p MA or nullptr if none.
108
  __isl_give isl_map *getReductionDependences(MemoryAccess *MA) const;
109
110
  /// Return all reduction dependences.
111
22
  const ReductionDependencesMapTy &getReductionDependences() const {
112
22
    return ReductionDependences;
113
22
  }
114
115
  /// Check if a partial schedule is parallel wrt to @p Deps.
116
  ///
117
  /// @param Schedule       The subset of the schedule space that we want to
118
  ///                       check.
119
  /// @param Deps           The dependences @p Schedule needs to respect.
120
  /// @param MinDistancePtr If not nullptr, the minimal dependence distance will
121
  ///                       be returned at the address of that pointer
122
  ///
123
  /// @return Returns true, if executing parallel the outermost dimension of
124
  ///         @p Schedule is valid according to the dependences @p Deps.
125
  bool isParallel(__isl_keep isl_union_map *Schedule,
126
                  __isl_take isl_union_map *Deps,
127
                  __isl_give isl_pw_aff **MinDistancePtr = nullptr) const;
128
129
  /// Check if a new schedule is valid.
130
  ///
131
  /// @param S             The current SCoP.
132
  /// @param NewSchedules  The new schedules
133
  ///
134
  /// @return True if the new schedule is valid, false it it reverses
135
  ///         dependences.
136
  bool isValidSchedule(Scop &S, StatementToIslMapTy *NewSchedules) const;
137
138
  /// Print the stored dependence information.
139
  void print(llvm::raw_ostream &OS) const;
140
141
  /// Dump the dependence information stored to the dbgs stream.
142
  void dump() const;
143
144
  /// Return the granularity of this dependence analysis.
145
33
  AnalysisLevel getDependenceLevel() { return Level; }
146
147
  /// Allow the DependenceInfo access to private members and methods.
148
  ///
149
  /// To restrict access to the internal state, only the DependenceInfo class
150
  /// is able to call or modify a Dependences struct.
151
  friend class DependenceInfo;
152
  friend class DependenceInfoWrapperPass;
153
154
  /// Destructor that will free internal objects.
155
498
  ~Dependences() { releaseMemory(); }
156
157
private:
158
  /// Create an empty dependences struct.
159
  explicit Dependences(const std::shared_ptr<isl_ctx> &IslCtx,
160
                       AnalysisLevel Level)
161
      : RAW(nullptr), WAR(nullptr), WAW(nullptr), RED(nullptr), TC_RED(nullptr),
162
498
        IslCtx(IslCtx), Level(Level) {}
163
164
  /// Calculate and add at the privatization dependences.
165
  void addPrivatizationDependences();
166
167
  /// Calculate the dependences for a certain SCoP @p S.
168
  void calculateDependences(Scop &S);
169
170
  /// Set the reduction dependences for @p MA to @p Deps.
171
  void setReductionDependences(MemoryAccess *MA, __isl_take isl_map *Deps);
172
173
  /// Free the objects associated with this Dependences struct.
174
  ///
175
  /// The Dependences struct will again be "empty" afterwards.
176
  void releaseMemory();
177
178
  /// The different basic kinds of dependences we calculate.
179
  isl_union_map *RAW;
180
  isl_union_map *WAR;
181
  isl_union_map *WAW;
182
183
  /// The special reduction dependences.
184
  isl_union_map *RED;
185
186
  /// The (reverse) transitive closure of reduction dependences.
187
  isl_union_map *TC_RED;
188
189
  /// Mapping from memory accesses to their reduction dependences.
190
  ReductionDependencesMapTy ReductionDependences;
191
192
  /// Isl context from the SCoP.
193
  std::shared_ptr<isl_ctx> IslCtx;
194
195
  /// Granularity of this dependence analysis.
196
  const AnalysisLevel Level;
197
};
198
199
class DependenceInfo : public ScopPass {
200
public:
201
  static char ID;
202
203
  /// Construct a new DependenceInfo pass.
204
483
  DependenceInfo() : ScopPass(ID) {}
205
206
  /// Return the dependence information for the current SCoP.
207
  ///
208
  /// @param Level The granularity of dependence analysis result.
209
  ///
210
  /// @return The dependence analysis result
211
  ///
212
  const Dependences &getDependences(Dependences::AnalysisLevel Level);
213
214
  /// Recompute dependences from schedule and memory accesses.
215
  const Dependences &recomputeDependences(Dependences::AnalysisLevel Level);
216
217
  /// Compute the dependence information for the SCoP @p S.
218
  bool runOnScop(Scop &S) override;
219
220
  /// Print the dependences for the given SCoP to @p OS.
221
  void printScop(raw_ostream &OS, Scop &) const override;
222
223
  /// Release the internal memory.
224
1.82k
  void releaseMemory() override {
225
1.82k
    for (auto &d : D)
226
5.48k
      d.reset();
227
1.82k
  }
228
229
  /// Register all analyses and transformation required.
230
  void getAnalysisUsage(AnalysisUsage &AU) const override;
231
232
private:
233
  Scop *S;
234
235
  /// Dependences struct for the current SCoP.
236
  std::unique_ptr<Dependences> D[Dependences::NumAnalysisLevels];
237
};
238
239
/// Construct a new DependenceInfoWrapper pass.
240
class DependenceInfoWrapperPass : public FunctionPass {
241
public:
242
  static char ID;
243
244
  /// Construct a new DependenceInfoWrapper pass.
245
26
  DependenceInfoWrapperPass() : FunctionPass(ID) {}
246
247
  /// Return the dependence information for the given SCoP.
248
  ///
249
  /// @param S     SCoP object.
250
  /// @param Level The granularity of dependence analysis result.
251
  ///
252
  /// @return The dependence analysis result
253
  ///
254
  const Dependences &getDependences(Scop *S, Dependences::AnalysisLevel Level);
255
256
  /// Recompute dependences from schedule and memory accesses.
257
  const Dependences &recomputeDependences(Scop *S,
258
                                          Dependences::AnalysisLevel Level);
259
260
  /// Compute the dependence information on-the-fly for the function.
261
  bool runOnFunction(Function &F) override;
262
263
  /// Print the dependences for the current function to @p OS.
264
  void print(raw_ostream &OS, const Module *M = nullptr) const override;
265
266
  /// Release the internal memory.
267
26
  void releaseMemory() override { ScopToDepsMap.clear(); }
268
269
  /// Register all analyses and transformation required.
270
  void getAnalysisUsage(AnalysisUsage &AU) const override;
271
272
private:
273
  using ScopToDepsMapTy = DenseMap<Scop *, std::unique_ptr<Dependences>>;
274
275
  /// Scop to Dependence map for the current function.
276
  ScopToDepsMapTy ScopToDepsMap;
277
};
278
279
} // namespace polly
280
281
namespace llvm {
282
class PassRegistry;
283
void initializeDependenceInfoPass(llvm::PassRegistry &);
284
void initializeDependenceInfoWrapperPassPass(llvm::PassRegistry &);
285
} // namespace llvm
286
287
#endif