Coverage Report

Created: 2017-06-28 17:40

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/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
  /// 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
38
  const ReductionDependencesMapTy &getReductionDependences() const {
112
38
    return ReductionDependences;
113
38
  }
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 if 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 struct DependenceAnalysis;
152
  friend struct DependenceInfoPrinterPass;
153
  friend class DependenceInfo;
154
  friend class DependenceInfoWrapperPass;
155
156
  /// Destructor that will free internal objects.
157
540
  ~Dependences() { releaseMemory(); }
158
159
private:
160
  /// Create an empty dependences struct.
161
  explicit Dependences(const std::shared_ptr<isl_ctx> &IslCtx,
162
                       AnalysisLevel Level)
163
      : RAW(nullptr), WAR(nullptr), WAW(nullptr), RED(nullptr), TC_RED(nullptr),
164
540
        IslCtx(IslCtx), Level(Level) {}
165
166
  /// Calculate and add at the privatization dependences.
167
  void addPrivatizationDependences();
168
169
  /// Calculate the dependences for a certain SCoP @p S.
170
  void calculateDependences(Scop &S);
171
172
  /// Set the reduction dependences for @p MA to @p Deps.
173
  void setReductionDependences(MemoryAccess *MA, __isl_take isl_map *Deps);
174
175
  /// Free the objects associated with this Dependences struct.
176
  ///
177
  /// The Dependences struct will again be "empty" afterwards.
178
  void releaseMemory();
179
180
  /// The different basic kinds of dependences we calculate.
181
  isl_union_map *RAW;
182
  isl_union_map *WAR;
183
  isl_union_map *WAW;
184
185
  /// The special reduction dependences.
186
  isl_union_map *RED;
187
188
  /// The (reverse) transitive closure of reduction dependences.
189
  isl_union_map *TC_RED;
190
191
  /// Mapping from memory accesses to their reduction dependences.
192
  ReductionDependencesMapTy ReductionDependences;
193
194
  /// Isl context from the SCoP.
195
  std::shared_ptr<isl_ctx> IslCtx;
196
197
  /// Granularity of this dependence analysis.
198
  const AnalysisLevel Level;
199
};
200
201
struct DependenceAnalysis : public AnalysisInfoMixin<DependenceAnalysis> {
202
  static AnalysisKey Key;
203
  struct Result {
204
    Scop &S;
205
    std::unique_ptr<Dependences> D[Dependences::NumAnalysisLevels];
206
207
    /// Return the dependence information for the current SCoP.
208
    ///
209
    /// @param Level The granularity of dependence analysis result.
210
    ///
211
    /// @return The dependence analysis result
212
    ///
213
    const Dependences &getDependences(Dependences::AnalysisLevel Level);
214
215
    /// Recompute dependences from schedule and memory accesses.
216
    const Dependences &recomputeDependences(Dependences::AnalysisLevel Level);
217
  };
218
  Result run(Scop &S, ScopAnalysisManager &SAM,
219
             ScopStandardAnalysisResults &SAR);
220
};
221
222
struct DependenceInfoPrinterPass
223
    : public PassInfoMixin<DependenceInfoPrinterPass> {
224
0
  DependenceInfoPrinterPass(raw_ostream &OS) : OS(OS) {}
225
226
  PreservedAnalyses run(Scop &S, ScopAnalysisManager &,
227
                        ScopStandardAnalysisResults &, SPMUpdater &);
228
229
  raw_ostream &OS;
230
};
231
232
class DependenceInfo : public ScopPass {
233
public:
234
  static char ID;
235
236
  /// Construct a new DependenceInfo pass.
237
523
  DependenceInfo() : ScopPass(ID) {}
238
239
  /// Return the dependence information for the current SCoP.
240
  ///
241
  /// @param Level The granularity of dependence analysis result.
242
  ///
243
  /// @return The dependence analysis result
244
  ///
245
  const Dependences &getDependences(Dependences::AnalysisLevel Level);
246
247
  /// Recompute dependences from schedule and memory accesses.
248
  const Dependences &recomputeDependences(Dependences::AnalysisLevel Level);
249
250
  /// Compute the dependence information for the SCoP @p S.
251
  bool runOnScop(Scop &S) override;
252
253
  /// Print the dependences for the given SCoP to @p OS.
254
  void printScop(raw_ostream &OS, Scop &) const override;
255
256
  /// Release the internal memory.
257
1.98k
  void releaseMemory() override {
258
1.98k
    for (auto &d : D)
259
5.94k
      d.reset();
260
1.98k
  }
261
262
  /// Register all analyses and transformation required.
263
  void getAnalysisUsage(AnalysisUsage &AU) const override;
264
265
private:
266
  Scop *S;
267
268
  /// Dependences struct for the current SCoP.
269
  std::unique_ptr<Dependences> D[Dependences::NumAnalysisLevels];
270
};
271
272
/// Construct a new DependenceInfoWrapper pass.
273
class DependenceInfoWrapperPass : public FunctionPass {
274
public:
275
  static char ID;
276
277
  /// Construct a new DependenceInfoWrapper pass.
278
26
  DependenceInfoWrapperPass() : FunctionPass(ID) {}
279
280
  /// Return the dependence information for the given SCoP.
281
  ///
282
  /// @param S     SCoP object.
283
  /// @param Level The granularity of dependence analysis result.
284
  ///
285
  /// @return The dependence analysis result
286
  ///
287
  const Dependences &getDependences(Scop *S, Dependences::AnalysisLevel Level);
288
289
  /// Recompute dependences from schedule and memory accesses.
290
  const Dependences &recomputeDependences(Scop *S,
291
                                          Dependences::AnalysisLevel Level);
292
293
  /// Compute the dependence information on-the-fly for the function.
294
  bool runOnFunction(Function &F) override;
295
296
  /// Print the dependences for the current function to @p OS.
297
  void print(raw_ostream &OS, const Module *M = nullptr) const override;
298
299
  /// Release the internal memory.
300
26
  void releaseMemory() override { ScopToDepsMap.clear(); }
301
302
  /// Register all analyses and transformation required.
303
  void getAnalysisUsage(AnalysisUsage &AU) const override;
304
305
private:
306
  using ScopToDepsMapTy = DenseMap<Scop *, std::unique_ptr<Dependences>>;
307
308
  /// Scop to Dependence map for the current function.
309
  ScopToDepsMapTy ScopToDepsMap;
310
};
311
312
} // namespace polly
313
314
namespace llvm {
315
class PassRegistry;
316
void initializeDependenceInfoPass(llvm::PassRegistry &);
317
void initializeDependenceInfoWrapperPassPass(llvm::PassRegistry &);
318
} // namespace llvm
319
320
#endif