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 | 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 */ |
420 | |