Coverage Report

Created: 2017-11-23 03:11

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/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 "llvm/ADT/DenseSet.h"
19
#include "llvm/ADT/SmallPtrSet.h"
20
#include "isl/isl-noexceptions.h"
21
#include <memory>
22
23
namespace llvm {
24
class Value;
25
class LoopInfo;
26
class Loop;
27
class PHINode;
28
class raw_ostream;
29
} // namespace llvm
30
31
namespace polly {
32
class Scop;
33
class ScopStmt;
34
class MemoryAccess;
35
class ScopArrayInfo;
36
37
/// Return only the mappings that map to known values.
38
///
39
/// @param UMap { [] -> ValInst[] }
40
///
41
/// @return { [] -> ValInst[] }
42
isl::union_map filterKnownValInst(const isl::union_map &UMap);
43
44
/// Base class for algorithms based on zones, like DeLICM.
45
class ZoneAlgorithm {
46
protected:
47
  /// The name of the pass this is used from. Used for optimization remarks.
48
  const char *PassName;
49
50
  /// Hold a reference to the isl_ctx to avoid it being freed before we released
51
  /// all of the isl objects.
52
  ///
53
  /// This must be declared before any other member that holds an isl object.
54
  /// This guarantees that the shared_ptr and its isl_ctx is destructed last,
55
  /// after all other members free'd the isl objects they were holding.
56
  std::shared_ptr<isl_ctx> IslCtx;
57
58
  /// Cached reaching definitions for each ScopStmt.
59
  ///
60
  /// Use getScalarReachingDefinition() to get its contents.
61
  llvm::DenseMap<ScopStmt *, isl::map> ScalarReachDefZone;
62
63
  /// The analyzed Scop.
64
  Scop *S;
65
66
  /// LoopInfo analysis used to determine whether values are synthesizable.
67
  llvm::LoopInfo *LI;
68
69
  /// Parameter space that does not need realignment.
70
  isl::space ParamSpace;
71
72
  /// Space the schedule maps to.
73
  isl::space ScatterSpace;
74
75
  /// Cached version of the schedule and domains.
76
  isl::union_map Schedule;
77
78
  /// Combined access relations of all MemoryKind::Array READ accesses.
79
  /// { DomainRead[] -> Element[] }
80
  isl::union_map AllReads;
81
82
  /// The loaded values (llvm::LoadInst) of all reads.
83
  /// { [Element[] -> DomainRead[]] -> ValInst[] }
84
  isl::union_map AllReadValInst;
85
86
  /// Combined access relations of all MemoryKind::Array, MAY_WRITE accesses.
87
  /// { DomainMayWrite[] -> Element[] }
88
  isl::union_map AllMayWrites;
89
90
  /// Combined access relations of all MemoryKind::Array, MUST_WRITE accesses.
91
  /// { DomainMustWrite[] -> Element[] }
92
  isl::union_map AllMustWrites;
93
94
  /// Combined access relations of all MK_Array write accesses (union of
95
  /// AllMayWrites and AllMustWrites).
96
  /// { DomainWrite[] -> Element[] }
97
  isl::union_map AllWrites;
98
99
  /// The value instances written to array elements of all write accesses.
100
  /// { [Element[] -> DomainWrite[]] -> ValInst[] }
101
  isl::union_map AllWriteValInst;
102
103
  /// All reaching definitions for  MemoryKind::Array writes.
104
  /// { [Element[] -> Zone[]] -> DomainWrite[] }
105
  isl::union_map WriteReachDefZone;
106
107
  /// Map llvm::Values to an isl identifier.
108
  /// Used with -polly-use-llvm-names=false as an alternative method to get
109
  /// unique ids that do not depend on pointer values.
110
  llvm::DenseMap<llvm::Value *, isl::id> ValueIds;
111
112
  /// Set of array elements that can be reliably used for zone analysis.
113
  /// { Element[] }
114
  isl::union_set CompatibleElts;
115
116
  /// List of PHIs that may transitively refer to themselves.
117
  ///
118
  /// Computing them would require a polyhedral transitive closure operation,
119
  /// for which isl may only return an approximation. For correctness, we always
120
  /// require an exact result. Hence, we exclude such PHIs.
121
  llvm::SmallPtrSet<llvm::PHINode *, 4> RecursivePHIs;
122
123
  /// PHIs that have been computed.
124
  ///
125
  /// Computed PHIs are replaced by their incoming values using #NormalizeMap.
126
  llvm::DenseSet<llvm::PHINode *> ComputedPHIs;
127
128
  /// For computed PHIs, contains the ValInst they stand for.
129
  ///
130
  /// To show an example, assume the following PHINode:
131
  ///
132
  ///   Stmt:
133
  ///     %phi = phi double [%val1, %bb1], [%val2, %bb2]
134
  ///
135
  /// It's ValInst is:
136
  ///
137
  ///   { [Stmt[i] -> phi[]] }
138
  ///
139
  /// The value %phi will be either %val1 or %val2, depending on whether in
140
  /// iteration i %bb1 or %bb2 has been executed before. In SCoPs, this can be
141
  /// determined at compile-time, and the result stored in #NormalizeMap. For
142
  /// the previous example, it could be:
143
  ///
144
  ///   { [Stmt[i] -> phi[]] -> [Stmt[0] -> val1[]];
145
  ///     [Stmt[i] -> phi[]] -> [Stmt[i] -> val2[]] : i > 0 }
146
  ///
147
  /// Only ValInsts in #ComputedPHIs are present in this map. Other values are
148
  /// assumed to represent themselves. This is to avoid adding lots of identity
149
  /// entries to this map.
150
  ///
151
  /// { PHIValInst[] -> IncomingValInst[] }
152
  isl::union_map NormalizeMap;
153
154
  /// Cache for computePerPHI(const ScopArrayInfo *)
155
  llvm::SmallDenseMap<llvm::PHINode *, isl::union_map> PerPHIMaps;
156
157
  /// Prepare the object before computing the zones of @p S.
158
  ///
159
  /// @param PassName Name of the pass using this analysis.
160
  /// @param S        The SCoP to process.
161
  /// @param LI       LoopInfo analysis used to determine synthesizable values.
162
  ZoneAlgorithm(const char *PassName, Scop *S, llvm::LoopInfo *LI);
163
164
private:
165
  /// Find the array elements that violate the zone analysis assumptions.
166
  ///
167
  /// What violates our assumptions:
168
  /// - A load after a write of the same location; we assume that all reads
169
  ///   occur before the writes.
170
  /// - Two writes to the same location; we cannot model the order in which
171
  ///   these occur.
172
  ///
173
  /// Scalar reads implicitly always occur before other accesses therefore never
174
  /// violate the first condition. There is also at most one write to a scalar,
175
  /// satisfying the second condition.
176
  ///
177
  /// @param Stmt                  The statement to be analyzed.
178
  /// @param[out] IncompatibleElts Receives the elements that are not
179
  ///                              zone-analysis compatible.
180
  /// @param[out]                  AllElts receives all encountered elements.
181
  void collectIncompatibleElts(ScopStmt *Stmt, isl::union_set &IncompatibleElts,
182
                               isl::union_set &AllElts);
183
184
  void addArrayReadAccess(MemoryAccess *MA);
185
186
  /// Return the ValInst write by a (must-)write access. Returns the 'unknown'
187
  /// ValInst if there is no single ValInst[] the array element written to will
188
  /// have.
189
  ///
190
  /// @return { ValInst[] }
191
  isl::union_map getWrittenValue(MemoryAccess *MA, isl::map AccRel);
192
193
  void addArrayWriteAccess(MemoryAccess *MA);
194
195
protected:
196
  isl::union_set makeEmptyUnionSet() const;
197
198
  isl::union_map makeEmptyUnionMap() const;
199
200
  /// For each 'execution' of a PHINode, get the incoming block that was
201
  /// executed before.
202
  ///
203
  /// For each PHI instance we can directly determine which was the incoming
204
  /// block, and hence derive which value the PHI has.
205
  ///
206
  /// @param SAI The ScopArrayInfo representing the PHI's storage.
207
  ///
208
  /// @return { DomainPHIRead[] -> DomainPHIWrite[] }
209
  isl::union_map computePerPHI(const polly::ScopArrayInfo *SAI);
210
211
  /// Find the array elements that can be used for zone analysis.
212
  void collectCompatibleElts();
213
214
  /// Get the schedule for @p Stmt.
215
  ///
216
  /// The domain of the result is as narrow as possible.
217
  isl::map getScatterFor(ScopStmt *Stmt) const;
218
219
  /// Get the schedule of @p MA's parent statement.
220
  isl::map getScatterFor(MemoryAccess *MA) const;
221
222
  /// Get the schedule for the statement instances of @p Domain.
223
  isl::union_map getScatterFor(isl::union_set Domain) const;
224
225
  /// Get the schedule for the statement instances of @p Domain.
226
  isl::map getScatterFor(isl::set Domain) const;
227
228
  /// Get the domain of @p Stmt.
229
  isl::set getDomainFor(ScopStmt *Stmt) const;
230
231
  /// Get the domain @p MA's parent statement.
232
  isl::set getDomainFor(MemoryAccess *MA) const;
233
234
  /// Get the access relation of @p MA.
235
  ///
236
  /// The domain of the result is as narrow as possible.
237
  isl::map getAccessRelationFor(MemoryAccess *MA) const;
238
239
  /// Get the reaching definition of a scalar defined in @p Stmt.
240
  ///
241
  /// Note that this does not depend on the llvm::Instruction, only on the
242
  /// statement it is defined in. Therefore the same computation can be reused.
243
  ///
244
  /// @param Stmt The statement in which a scalar is defined.
245
  ///
246
  /// @return { Scatter[] -> DomainDef[] }
247
  isl::map getScalarReachingDefinition(ScopStmt *Stmt);
248
249
  /// Get the reaching definition of a scalar defined in @p DefDomain.
250
  ///
251
  /// @param DomainDef { DomainDef[] }
252
  ///              The write statements to get the reaching definition for.
253
  ///
254
  /// @return { Scatter[] -> DomainDef[] }
255
  isl::map getScalarReachingDefinition(isl::set DomainDef);
256
257
  /// Create a statement-to-unknown value mapping.
258
  ///
259
  /// @param Stmt The statement whose instances are mapped to unknown.
260
  ///
261
  /// @return { Domain[] -> ValInst[] }
262
  isl::map makeUnknownForDomain(ScopStmt *Stmt) const;
263
264
  /// Create an isl_id that represents @p V.
265
  isl::id makeValueId(llvm::Value *V);
266
267
  /// Create the space for an llvm::Value that is available everywhere.
268
  isl::space makeValueSpace(llvm::Value *V);
269
270
  /// Create a set with the llvm::Value @p V which is available everywhere.
271
  isl::set makeValueSet(llvm::Value *V);
272
273
  /// Create a mapping from a statement instance to the instance of an
274
  /// llvm::Value that can be used in there.
275
  ///
276
  /// Although LLVM IR uses single static assignment, llvm::Values can have
277
  /// different contents in loops, when they get redefined in the last
278
  /// iteration. This function tries to get the statement instance of the
279
  /// previous definition, relative to a user.
280
  ///
281
  /// Example:
282
  /// for (int i = 0; i < N; i += 1) {
283
  /// DEF:
284
  ///    int v = A[i];
285
  /// USE:
286
  ///    use(v);
287
  ///  }
288
  ///
289
  /// The value instance used by statement instance USE[i] is DEF[i]. Hence,
290
  /// makeValInst returns:
291
  ///
292
  /// { USE[i] -> [DEF[i] -> v[]] : 0 <= i < N }
293
  ///
294
  /// @param Val       The value to get the instance of.
295
  /// @param UserStmt  The statement that uses @p Val. Can be nullptr.
296
  /// @param Scope     Loop the using instruction resides in.
297
  /// @param IsCertain Pass true if the definition of @p Val is a
298
  ///                  MUST_WRITE or false if the write is conditional.
299
  ///
300
  /// @return { DomainUse[] -> ValInst[] }
301
  isl::map makeValInst(llvm::Value *Val, ScopStmt *UserStmt, llvm::Loop *Scope,
302
                       bool IsCertain = true);
303
304
  /// Create and normalize a ValInst.
305
  ///
306
  /// @see makeValInst
307
  /// @see normalizeValInst
308
  /// @see #NormalizedPHI
309
  isl::union_map makeNormalizedValInst(llvm::Value *Val, ScopStmt *UserStmt,
310
                                       llvm::Loop *Scope,
311
                                       bool IsCertain = true);
312
313
  /// Return whether @p MA can be used for transformations (e.g. OpTree load
314
  /// forwarding, DeLICM mapping).
315
  bool isCompatibleAccess(MemoryAccess *MA);
316
317
  /// Compute the different zones.
318
  void computeCommon();
319
320
  ///  Compute the normalization map that replaces PHIs by their incoming
321
  ///  values.
322
  ///
323
  /// @see #NormalizeMap
324
  void computeNormalizedPHIs();
325
326
  /// Print the current state of all MemoryAccesses to @p.
327
  void printAccesses(llvm::raw_ostream &OS, int Indent = 0) const;
328
329
  /// Is @p MA a PHI READ access that can be normalized?
330
  ///
331
  /// @see #NormalizeMap
332
  bool isNormalizable(MemoryAccess *MA);
333
334
  /// @{
335
  /// Determine whether the argument does not map to any computed PHI. Those
336
  /// should have been replaced by their incoming values.
337
  ///
338
  /// @see #NormalizedPHI
339
  bool isNormalized(isl::map Map);
340
  bool isNormalized(isl::union_map Map);
341
  /// @}
342
343
public:
344
  /// Return the SCoP this object is analyzing.
345
0
  Scop *getScop() const { return S; }
346
347
  /// A reaching definition zone is known to have the definition's written value
348
  /// if the definition is a MUST_WRITE.
349
  ///
350
  /// @return { [Element[] -> Zone[]] -> ValInst[] }
351
  isl::union_map computeKnownFromMustWrites() const;
352
353
  /// A reaching definition zone is known to be the same value as any load that
354
  /// reads from that array element in that period.
355
  ///
356
  /// @return { [Element[] -> Zone[]] -> ValInst[] }
357
  isl::union_map computeKnownFromLoad() const;
358
359
  /// Compute which value an array element stores at every instant.
360
  ///
361
  /// @param FromWrite Use stores as source of information.
362
  /// @param FromRead  Use loads as source of information.
363
  ///
364
  /// @return { [Element[] -> Zone[]] -> ValInst[] }
365
  isl::union_map computeKnown(bool FromWrite, bool FromRead) const;
366
};
367
368
/// Create a domain-to-unknown value mapping.
369
///
370
/// Value instances that do not represent a specific value are represented by an
371
/// unnamed tuple of 0 dimensions. Its meaning depends on the context. It can
372
/// either mean a specific but unknown value which cannot be represented by
373
/// other means. It conflicts with itself because those two unknown ValInsts may
374
/// have different concrete values at runtime.
375
///
376
/// The other meaning is an arbitrary or wildcard value that can be chosen
377
/// freely, like LLVM's undef. If matched with an unknown ValInst, there is no
378
/// conflict.
379
///
380
/// @param Domain { Domain[] }
381
///
382
/// @return { Domain[] -> ValInst[] }
383
isl::union_map makeUnknownForDomain(isl::union_set Domain);
384
} // namespace polly
385
386
#endif /* POLLY_ZONEALGO_H */