Coverage Report

Created: 2019-04-25 15:07

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