Coverage Report

Created: 2019-04-21 11:35

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