Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/include/polly/ZoneAlgo.h
Line
Count
Source (jump to first uncovered line)
1
//===------ ZoneAlgo.h ------------------------------------------*- 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
// Derive information about array elements between statements ("Zones").
11
//
12
//===----------------------------------------------------------------------===//
13
14
#ifndef POLLY_ZONEALGO_H
15
#define POLLY_ZONEALGO_H
16
17
#include "llvm/ADT/DenseMap.h"
18
#include "isl/isl-noexceptions.h"
19
#include <memory>
20
21
namespace llvm {
22
class Value;
23
class LoopInfo;
24
class Loop;
25
} // namespace llvm
26
27
namespace polly {
28
class Scop;
29
class ScopStmt;
30
class MemoryAccess;
31
32
/// Return only the mappings that map to known values.
33
///
34
/// @param UMap { [] -> ValInst[] }
35
///
36
/// @return { [] -> ValInst[] }
37
isl::union_map filterKnownValInst(const isl::union_map &UMap);
38
39
/// Base class for algorithms based on zones, like DeLICM.
40
class ZoneAlgorithm {
41
protected:
42
  /// The name of the pass this is used from. Used for optimization remarks.
43
  const char *PassName;
44
45
  /// Hold a reference to the isl_ctx to avoid it being freed before we released
46
  /// all of the isl objects.
47
  ///
48
  /// This must be declared before any other member that holds an isl object.
49
  /// This guarantees that the shared_ptr and its isl_ctx is destructed last,
50
  /// after all other members free'd the isl objects they were holding.
51
  std::shared_ptr<isl_ctx> IslCtx;
52
53
  /// Cached reaching definitions for each ScopStmt.
54
  ///
55
  /// Use getScalarReachingDefinition() to get its contents.
56
  llvm::DenseMap<ScopStmt *, isl::map> ScalarReachDefZone;
57
58
  /// The analyzed Scop.
59
  Scop *S;
60
61
  /// LoopInfo analysis used to determine whether values are synthesizable.
62
  llvm::LoopInfo *LI;
63
64
  /// Parameter space that does not need realignment.
65
  isl::space ParamSpace;
66
67
  /// Space the schedule maps to.
68
  isl::space ScatterSpace;
69
70
  /// Cached version of the schedule and domains.
71
  isl::union_map Schedule;
72
73
  /// Combined access relations of all MemoryKind::Array READ accesses.
74
  /// { DomainRead[] -> Element[] }
75
  isl::union_map AllReads;
76
77
  /// The loaded values (llvm::LoadInst) of all reads.
78
  /// { [Element[] -> DomainRead[]] -> ValInst[] }
79
  isl::union_map AllReadValInst;
80
81
  /// Combined access relations of all MemoryKind::Array, MAY_WRITE accesses.
82
  /// { DomainMayWrite[] -> Element[] }
83
  isl::union_map AllMayWrites;
84
85
  /// Combined access relations of all MemoryKind::Array, MUST_WRITE accesses.
86
  /// { DomainMustWrite[] -> Element[] }
87
  isl::union_map AllMustWrites;
88
89
  /// Combined access relations of all MK_Array write accesses (union of
90
  /// AllMayWrites and AllMustWrites).
91
  /// { DomainWrite[] -> Element[] }
92
  isl::union_map AllWrites;
93
94
  /// The value instances written to array elements of all write accesses.
95
  /// { [Element[] -> DomainWrite[]] -> ValInst[] }
96
  isl::union_map AllWriteValInst;
97
98
  /// All reaching definitions for  MemoryKind::Array writes.
99
  /// { [Element[] -> Zone[]] -> DomainWrite[] }
100
  isl::union_map WriteReachDefZone;
101
102
  /// Map llvm::Values to an isl identifier.
103
  /// Used with -polly-use-llvm-names=false as an alternative method to get
104
  /// unique ids that do not depend on pointer values.
105
  llvm::DenseMap<llvm::Value *, isl::id> ValueIds;
106
107
  /// Set of array elements that can be reliably used for zone analysis.
108
  /// { Element[] }
109
  isl::union_set CompatibleElts;
110
111
  /// Prepare the object before computing the zones of @p S.
112
  ///
113
  /// @param PassName Name of the pass using this analysis.
114
  /// @param S        The SCoP to process.
115
  /// @param LI       LoopInfo analysis used to determine synthesizable values.
116
  ZoneAlgorithm(const char *PassName, Scop *S, llvm::LoopInfo *LI);
117
118
private:
119
  /// Find the array elements that violate the zone analysis assumptions.
120
  ///
121
  /// What violates our assumptions:
122
  /// - A load after a write of the same location; we assume that all reads
123
  ///   occur before the writes.
124
  /// - Two writes to the same location; we cannot model the order in which
125
  ///   these occur.
126
  ///
127
  /// Scalar reads implicitly always occur before other accesses therefore never
128
  /// violate the first condition. There is also at most one write to a scalar,
129
  /// satisfying the second condition.
130
  ///
131
  /// @param Stmt                  The statement to be analyzed.
132
  /// @param[out] IncompatibleElts Receives the elements that are not
133
  ///                              zone-analysis compatible.
134
  /// @param[out]                  AllElts receives all encountered elements.
135
  void collectIncompatibleElts(ScopStmt *Stmt, isl::union_set &IncompatibleElts,
136
                               isl::union_set &AllElts);
137
138
  void addArrayReadAccess(MemoryAccess *MA);
139
140
  /// Return the ValInst write by a (must-)write access. Returns the 'unknown'
141
  /// ValInst if there is no single ValInst[] the array element written to will
142
  /// have.
143
  ///
144
  /// @return { ValInst[] }
145
  isl::map getWrittenValue(MemoryAccess *MA, isl::map AccRel);
146
147
  void addArrayWriteAccess(MemoryAccess *MA);
148
149
protected:
150
  isl::union_set makeEmptyUnionSet() const;
151
152
  isl::union_map makeEmptyUnionMap() const;
153
154
  /// Find the array elements that can be used for zone analysis.
155
  void collectCompatibleElts();
156
157
  /// Get the schedule for @p Stmt.
158
  ///
159
  /// The domain of the result is as narrow as possible.
160
  isl::map getScatterFor(ScopStmt *Stmt) const;
161
162
  /// Get the schedule of @p MA's parent statement.
163
  isl::map getScatterFor(MemoryAccess *MA) const;
164
165
  /// Get the schedule for the statement instances of @p Domain.
166
  isl::union_map getScatterFor(isl::union_set Domain) const;
167
168
  /// Get the schedule for the statement instances of @p Domain.
169
  isl::map getScatterFor(isl::set Domain) const;
170
171
  /// Get the domain of @p Stmt.
172
  isl::set getDomainFor(ScopStmt *Stmt) const;
173
174
  /// Get the domain @p MA's parent statement.
175
  isl::set getDomainFor(MemoryAccess *MA) const;
176
177
  /// Get the access relation of @p MA.
178
  ///
179
  /// The domain of the result is as narrow as possible.
180
  isl::map getAccessRelationFor(MemoryAccess *MA) const;
181
182
  /// Get the reaching definition of a scalar defined in @p Stmt.
183
  ///
184
  /// Note that this does not depend on the llvm::Instruction, only on the
185
  /// statement it is defined in. Therefore the same computation can be reused.
186
  ///
187
  /// @param Stmt The statement in which a scalar is defined.
188
  ///
189
  /// @return { Scatter[] -> DomainDef[] }
190
  isl::map getScalarReachingDefinition(ScopStmt *Stmt);
191
192
  /// Get the reaching definition of a scalar defined in @p DefDomain.
193
  ///
194
  /// @param DomainDef { DomainDef[] }
195
  ///              The write statements to get the reaching definition for.
196
  ///
197
  /// @return { Scatter[] -> DomainDef[] }
198
  isl::map getScalarReachingDefinition(isl::set DomainDef);
199
200
  /// Create a statement-to-unknown value mapping.
201
  ///
202
  /// @param Stmt The statement whose instances are mapped to unknown.
203
  ///
204
  /// @return { Domain[] -> ValInst[] }
205
  isl::map makeUnknownForDomain(ScopStmt *Stmt) const;
206
207
  /// Create an isl_id that represents @p V.
208
  isl::id makeValueId(llvm::Value *V);
209
210
  /// Create the space for an llvm::Value that is available everywhere.
211
  isl::space makeValueSpace(llvm::Value *V);
212
213
  /// Create a set with the llvm::Value @p V which is available everywhere.
214
  isl::set makeValueSet(llvm::Value *V);
215
216
  /// Create a mapping from a statement instance to the instance of an
217
  /// llvm::Value that can be used in there.
218
  ///
219
  /// Although LLVM IR uses single static assignment, llvm::Values can have
220
  /// different contents in loops, when they get redefined in the last
221
  /// iteration. This function tries to get the statement instance of the
222
  /// previous definition, relative to a user.
223
  ///
224
  /// Example:
225
  /// for (int i = 0; i < N; i += 1) {
226
  /// DEF:
227
  ///    int v = A[i];
228
  /// USE:
229
  ///    use(v);
230
  ///  }
231
  ///
232
  /// The value instance used by statement instance USE[i] is DEF[i]. Hence,
233
  /// makeValInst returns:
234
  ///
235
  /// { USE[i] -> [DEF[i] -> v[]] : 0 <= i < N }
236
  ///
237
  /// @param Val       The value to get the instance of.
238
  /// @param UserStmt  The statement that uses @p Val. Can be nullptr.
239
  /// @param Scope     Loop the using instruction resides in.
240
  /// @param IsCertain Pass true if the definition of @p Val is a
241
  ///                  MUST_WRITE or false if the write is conditional.
242
  ///
243
  /// @return { DomainUse[] -> ValInst[] }
244
  isl::map makeValInst(llvm::Value *Val, ScopStmt *UserStmt, llvm::Loop *Scope,
245
                       bool IsCertain = true);
246
247
  /// Return whether @p MA can be used for transformations (e.g. OpTree load
248
  /// forwarding, DeLICM mapping).
249
  bool isCompatibleAccess(MemoryAccess *MA);
250
251
  /// Compute the different zones.
252
  void computeCommon();
253
254
  /// Print the current state of all MemoryAccesses to @p.
255
  void printAccesses(llvm::raw_ostream &OS, int Indent = 0) const;
256
257
public:
258
  /// Return the SCoP this object is analyzing.
259
0
  Scop *getScop() const { return S; }
260
261
  /// A reaching definition zone is known to have the definition's written value
262
  /// if the definition is a MUST_WRITE.
263
  ///
264
  /// @return { [Element[] -> Zone[]] -> ValInst[] }
265
  isl::union_map computeKnownFromMustWrites() const;
266
267
  /// A reaching definition zone is known to be the same value as any load that
268
  /// reads from that array element in that period.
269
  ///
270
  /// @return { [Element[] -> Zone[]] -> ValInst[] }
271
  isl::union_map computeKnownFromLoad() const;
272
273
  /// Compute which value an array element stores at every instant.
274
  ///
275
  /// @param FromWrite Use stores as source of information.
276
  /// @param FromRead  Use loads as source of information.
277
  ///
278
  /// @return { [Element[] -> Zone[]] -> ValInst[] }
279
  isl::union_map computeKnown(bool FromWrite, bool FromRead) const;
280
};
281
282
/// Create a domain-to-unknown value mapping.
283
///
284
/// Value instances that do not represent a specific value are represented by an
285
/// unnamed tuple of 0 dimensions. Its meaning depends on the context. It can
286
/// either mean a specific but unknown value which cannot be represented by
287
/// other means. It conflicts with itself because those two unknown ValInsts may
288
/// have different concrete values at runtime.
289
///
290
/// The other meaning is an arbitrary or wildcard value that can be chosen
291
/// freely, like LLVM's undef. If matched with an unknown ValInst, there is no
292
/// conflict.
293
///
294
/// @param Domain { Domain[] }
295
///
296
/// @return { Domain[] -> ValInst[] }
297
isl::union_map makeUnknownForDomain(isl::union_set Domain);
298
} // namespace polly
299
300
#endif /* POLLY_ZONEALGO_H */