1 | //===- polly/ScopInfo.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 | // Store the polyhedral model representation of a static control flow region, |
10 | // also called SCoP (Static Control Part). |
11 | // |
12 | // This representation is shared among several tools in the polyhedral |
13 | // community, which are e.g. CLooG, Pluto, Loopo, Graphite. |
14 | // |
15 | //===----------------------------------------------------------------------===// |
16 | |
17 | #ifndef POLLY_SCOPINFO_H |
18 | #define POLLY_SCOPINFO_H |
19 | |
20 | #include "polly/ScopDetection.h" |
21 | #include "polly/Support/SCEVAffinator.h" |
22 | #include "polly/Support/ScopHelper.h" |
23 | #include "llvm/ADT/ArrayRef.h" |
24 | #include "llvm/ADT/MapVector.h" |
25 | #include "llvm/ADT/SetVector.h" |
26 | #include "llvm/Analysis/RegionPass.h" |
27 | #include "llvm/IR/DebugLoc.h" |
28 | #include "llvm/IR/Instruction.h" |
29 | #include "llvm/IR/Instructions.h" |
30 | #include "llvm/IR/PassManager.h" |
31 | #include "llvm/IR/ValueHandle.h" |
32 | #include "llvm/Pass.h" |
33 | #include "isl/isl-noexceptions.h" |
34 | #include <cassert> |
35 | #include <cstddef> |
36 | #include <forward_list> |
37 | #include <optional> |
38 | |
39 | namespace polly { |
40 | using llvm::AnalysisInfoMixin; |
41 | using llvm::ArrayRef; |
42 | using llvm::AssertingVH; |
43 | using llvm::AssumptionCache; |
44 | using llvm::cast; |
45 | using llvm::DataLayout; |
46 | using llvm::DenseMap; |
47 | using llvm::DenseSet; |
48 | using llvm::function_ref; |
49 | using llvm::isa; |
50 | using llvm::iterator_range; |
51 | using llvm::LoadInst; |
52 | using llvm::make_range; |
53 | using llvm::MapVector; |
54 | using llvm::MemIntrinsic; |
55 | using llvm::PassInfoMixin; |
56 | using llvm::PHINode; |
57 | using llvm::RegionNode; |
58 | using llvm::RegionPass; |
59 | using llvm::RGPassManager; |
60 | using llvm::SetVector; |
61 | using llvm::SmallPtrSetImpl; |
62 | using llvm::SmallVector; |
63 | using llvm::SmallVectorImpl; |
64 | using llvm::StringMap; |
65 | using llvm::Type; |
66 | using llvm::Use; |
67 | using llvm::Value; |
68 | using llvm::ValueToValueMap; |
69 | |
70 | class MemoryAccess; |
71 | |
72 | //===---------------------------------------------------------------------===// |
73 | |
74 | extern bool UseInstructionNames; |
75 | |
76 | // The maximal number of basic sets we allow during domain construction to |
77 | // be created. More complex scops will result in very high compile time and |
78 | // are also unlikely to result in good code. |
79 | extern unsigned const MaxDisjunctsInDomain; |
80 | |
81 | /// The different memory kinds used in Polly. |
82 | /// |
83 | /// We distinguish between arrays and various scalar memory objects. We use |
84 | /// the term ``array'' to describe memory objects that consist of a set of |
85 | /// individual data elements arranged in a multi-dimensional grid. A scalar |
86 | /// memory object describes an individual data element and is used to model |
87 | /// the definition and uses of llvm::Values. |
88 | /// |
89 | /// The polyhedral model does traditionally not reason about SSA values. To |
90 | /// reason about llvm::Values we model them "as if" they were zero-dimensional |
91 | /// memory objects, even though they were not actually allocated in (main) |
92 | /// memory. Memory for such objects is only alloca[ed] at CodeGeneration |
93 | /// time. To relate the memory slots used during code generation with the |
94 | /// llvm::Values they belong to the new names for these corresponding stack |
95 | /// slots are derived by appending suffixes (currently ".s2a" and ".phiops") |
96 | /// to the name of the original llvm::Value. To describe how def/uses are |
97 | /// modeled exactly we use these suffixes here as well. |
98 | /// |
99 | /// There are currently four different kinds of memory objects: |
100 | enum class MemoryKind { |
101 | /// MemoryKind::Array: Models a one or multi-dimensional array |
102 | /// |
103 | /// A memory object that can be described by a multi-dimensional array. |
104 | /// Memory objects of this type are used to model actual multi-dimensional |
105 | /// arrays as they exist in LLVM-IR, but they are also used to describe |
106 | /// other objects: |
107 | /// - A single data element allocated on the stack using 'alloca' is |
108 | /// modeled as a one-dimensional, single-element array. |
109 | /// - A single data element allocated as a global variable is modeled as |
110 | /// one-dimensional, single-element array. |
111 | /// - Certain multi-dimensional arrays with variable size, which in |
112 | /// LLVM-IR are commonly expressed as a single-dimensional access with a |
113 | /// complicated access function, are modeled as multi-dimensional |
114 | /// memory objects (grep for "delinearization"). |
115 | Array, |
116 | |
117 | /// MemoryKind::Value: Models an llvm::Value |
118 | /// |
119 | /// Memory objects of type MemoryKind::Value are used to model the data flow |
120 | /// induced by llvm::Values. For each llvm::Value that is used across |
121 | /// BasicBlocks, one ScopArrayInfo object is created. A single memory WRITE |
122 | /// stores the llvm::Value at its definition into the memory object and at |
123 | /// each use of the llvm::Value (ignoring trivial intra-block uses) a |
124 | /// corresponding READ is added. For instance, the use/def chain of a |
125 | /// llvm::Value %V depicted below |
126 | /// ______________________ |
127 | /// |DefBB: | |
128 | /// | %V = float op ... | |
129 | /// ---------------------- |
130 | /// | | |
131 | /// _________________ _________________ |
132 | /// |UseBB1: | |UseBB2: | |
133 | /// | use float %V | | use float %V | |
134 | /// ----------------- ----------------- |
135 | /// |
136 | /// is modeled as if the following memory accesses occurred: |
137 | /// |
138 | /// __________________________ |
139 | /// |entry: | |
140 | /// | %V.s2a = alloca float | |
141 | /// -------------------------- |
142 | /// | |
143 | /// ___________________________________ |
144 | /// |DefBB: | |
145 | /// | store %float %V, float* %V.s2a | |
146 | /// ----------------------------------- |
147 | /// | | |
148 | /// ____________________________________ ___________________________________ |
149 | /// |UseBB1: | |UseBB2: | |
150 | /// | %V.reload1 = load float* %V.s2a | | %V.reload2 = load float* %V.s2a| |
151 | /// | use float %V.reload1 | | use float %V.reload2 | |
152 | /// ------------------------------------ ----------------------------------- |
153 | /// |
154 | Value, |
155 | |
156 | /// MemoryKind::PHI: Models PHI nodes within the SCoP |
157 | /// |
158 | /// Besides the MemoryKind::Value memory object used to model the normal |
159 | /// llvm::Value dependences described above, PHI nodes require an additional |
160 | /// memory object of type MemoryKind::PHI to describe the forwarding of values |
161 | /// to |
162 | /// the PHI node. |
163 | /// |
164 | /// As an example, a PHIInst instructions |
165 | /// |
166 | /// %PHI = phi float [ %Val1, %IncomingBlock1 ], [ %Val2, %IncomingBlock2 ] |
167 | /// |
168 | /// is modeled as if the accesses occurred this way: |
169 | /// |
170 | /// _______________________________ |
171 | /// |entry: | |
172 | /// | %PHI.phiops = alloca float | |
173 | /// ------------------------------- |
174 | /// | | |
175 | /// __________________________________ __________________________________ |
176 | /// |IncomingBlock1: | |IncomingBlock2: | |
177 | /// | ... | | ... | |
178 | /// | store float %Val1 %PHI.phiops | | store float %Val2 %PHI.phiops | |
179 | /// | br label % JoinBlock | | br label %JoinBlock | |
180 | /// ---------------------------------- ---------------------------------- |
181 | /// \ / |
182 | /// \ / |
183 | /// _________________________________________ |
184 | /// |JoinBlock: | |
185 | /// | %PHI = load float, float* PHI.phiops | |
186 | /// ----------------------------------------- |
187 | /// |
188 | /// Note that there can also be a scalar write access for %PHI if used in a |
189 | /// different BasicBlock, i.e. there can be a memory object %PHI.phiops as |
190 | /// well as a memory object %PHI.s2a. |
191 | PHI, |
192 | |
193 | /// MemoryKind::ExitPHI: Models PHI nodes in the SCoP's exit block |
194 | /// |
195 | /// For PHI nodes in the Scop's exit block a special memory object kind is |
196 | /// used. The modeling used is identical to MemoryKind::PHI, with the |
197 | /// exception |
198 | /// that there are no READs from these memory objects. The PHINode's |
199 | /// llvm::Value is treated as a value escaping the SCoP. WRITE accesses |
200 | /// write directly to the escaping value's ".s2a" alloca. |
201 | ExitPHI |
202 | }; |
203 | |
204 | /// Maps from a loop to the affine function expressing its backedge taken count. |
205 | /// The backedge taken count already enough to express iteration domain as we |
206 | /// only allow loops with canonical induction variable. |
207 | /// A canonical induction variable is: |
208 | /// an integer recurrence that starts at 0 and increments by one each time |
209 | /// through the loop. |
210 | using LoopBoundMapType = std::map<const Loop *, const SCEV *>; |
211 | |
212 | using AccFuncVector = std::vector<std::unique_ptr<MemoryAccess>>; |
213 | |
214 | /// A class to store information about arrays in the SCoP. |
215 | /// |
216 | /// Objects are accessible via the ScoP, MemoryAccess or the id associated with |
217 | /// the MemoryAccess access function. |
218 | /// |
219 | class ScopArrayInfo final { |
220 | public: |
221 | /// Construct a ScopArrayInfo object. |
222 | /// |
223 | /// @param BasePtr The array base pointer. |
224 | /// @param ElementType The type of the elements stored in the array. |
225 | /// @param IslCtx The isl context used to create the base pointer id. |
226 | /// @param DimensionSizes A vector containing the size of each dimension. |
227 | /// @param Kind The kind of the array object. |
228 | /// @param DL The data layout of the module. |
229 | /// @param S The scop this array object belongs to. |
230 | /// @param BaseName The optional name of this memory reference. |
231 | ScopArrayInfo(Value *BasePtr, Type *ElementType, isl::ctx IslCtx, |
232 | ArrayRef<const SCEV *> DimensionSizes, MemoryKind Kind, |
233 | const DataLayout &DL, Scop *S, const char *BaseName = nullptr); |
234 | |
235 | /// Destructor to free the isl id of the base pointer. |
236 | ~ScopArrayInfo(); |
237 | |
238 | /// Update the element type of the ScopArrayInfo object. |
239 | /// |
240 | /// Memory accesses referencing this ScopArrayInfo object may use |
241 | /// different element sizes. This function ensures the canonical element type |
242 | /// stored is small enough to model accesses to the current element type as |
243 | /// well as to @p NewElementType. |
244 | /// |
245 | /// @param NewElementType An element type that is used to access this array. |
246 | void updateElementType(Type *NewElementType); |
247 | |
248 | /// Update the sizes of the ScopArrayInfo object. |
249 | /// |
250 | /// A ScopArrayInfo object may be created without all outer dimensions being |
251 | /// available. This function is called when new memory accesses are added for |
252 | /// this ScopArrayInfo object. It verifies that sizes are compatible and adds |
253 | /// additional outer array dimensions, if needed. |
254 | /// |
255 | /// @param Sizes A vector of array sizes where the rightmost array |
256 | /// sizes need to match the innermost array sizes already |
257 | /// defined in SAI. |
258 | /// @param CheckConsistency Update sizes, even if new sizes are inconsistent |
259 | /// with old sizes |
260 | bool updateSizes(ArrayRef<const SCEV *> Sizes, bool CheckConsistency = true); |
261 | |
262 | /// Set the base pointer to @p BP. |
263 | void setBasePtr(Value *BP) { BasePtr = BP; } |
264 | |
265 | /// Return the base pointer. |
266 | Value *getBasePtr() const { return BasePtr; } |
267 | |
268 | // Set IsOnHeap to the value in parameter. |
269 | void setIsOnHeap(bool value) { IsOnHeap = value; } |
270 | |
271 | /// For indirect accesses return the origin SAI of the BP, else null. |
272 | const ScopArrayInfo *getBasePtrOriginSAI() const { return BasePtrOriginSAI; } |
273 | |
274 | /// The set of derived indirect SAIs for this origin SAI. |
275 | const SmallSetVector<ScopArrayInfo *, 2> &getDerivedSAIs() const { |
276 | return DerivedSAIs; |
277 | } |
278 | |
279 | /// Return the number of dimensions. |
280 | unsigned getNumberOfDimensions() const { |
281 | if (Kind == MemoryKind::PHI || Kind == MemoryKind::ExitPHI || |
282 | Kind == MemoryKind::Value) |
283 | return 0; |
284 | return DimensionSizes.size(); |
285 | } |
286 | |
287 | /// Return the size of dimension @p dim as SCEV*. |
288 | // |
289 | // Scalars do not have array dimensions and the first dimension of |
290 | // a (possibly multi-dimensional) array also does not carry any size |
291 | // information, in case the array is not newly created. |
292 | const SCEV *getDimensionSize(unsigned Dim) const { |
293 | assert(Dim < getNumberOfDimensions() && "Invalid dimension" ); |
294 | return DimensionSizes[Dim]; |
295 | } |
296 | |
297 | /// Return the size of dimension @p dim as isl::pw_aff. |
298 | // |
299 | // Scalars do not have array dimensions and the first dimension of |
300 | // a (possibly multi-dimensional) array also does not carry any size |
301 | // information, in case the array is not newly created. |
302 | isl::pw_aff getDimensionSizePw(unsigned Dim) const { |
303 | assert(Dim < getNumberOfDimensions() && "Invalid dimension" ); |
304 | return DimensionSizesPw[Dim]; |
305 | } |
306 | |
307 | /// Get the canonical element type of this array. |
308 | /// |
309 | /// @returns The canonical element type of this array. |
310 | Type *getElementType() const { return ElementType; } |
311 | |
312 | /// Get element size in bytes. |
313 | int getElemSizeInBytes() const; |
314 | |
315 | /// Get the name of this memory reference. |
316 | std::string getName() const; |
317 | |
318 | /// Return the isl id for the base pointer. |
319 | isl::id getBasePtrId() const; |
320 | |
321 | /// Return what kind of memory this represents. |
322 | MemoryKind getKind() const { return Kind; } |
323 | |
324 | /// Is this array info modeling an llvm::Value? |
325 | bool isValueKind() const { return Kind == MemoryKind::Value; } |
326 | |
327 | /// Is this array info modeling special PHI node memory? |
328 | /// |
329 | /// During code generation of PHI nodes, there is a need for two kinds of |
330 | /// virtual storage. The normal one as it is used for all scalar dependences, |
331 | /// where the result of the PHI node is stored and later loaded from as well |
332 | /// as a second one where the incoming values of the PHI nodes are stored |
333 | /// into and reloaded when the PHI is executed. As both memories use the |
334 | /// original PHI node as virtual base pointer, we have this additional |
335 | /// attribute to distinguish the PHI node specific array modeling from the |
336 | /// normal scalar array modeling. |
337 | bool isPHIKind() const { return Kind == MemoryKind::PHI; } |
338 | |
339 | /// Is this array info modeling an MemoryKind::ExitPHI? |
340 | bool isExitPHIKind() const { return Kind == MemoryKind::ExitPHI; } |
341 | |
342 | /// Is this array info modeling an array? |
343 | bool isArrayKind() const { return Kind == MemoryKind::Array; } |
344 | |
345 | /// Is this array allocated on heap |
346 | /// |
347 | /// This property is only relevant if the array is allocated by Polly instead |
348 | /// of pre-existing. If false, it is allocated using alloca instead malloca. |
349 | bool isOnHeap() const { return IsOnHeap; } |
350 | |
351 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
352 | /// Dump a readable representation to stderr. |
353 | void dump() const; |
354 | #endif |
355 | |
356 | /// Print a readable representation to @p OS. |
357 | /// |
358 | /// @param SizeAsPwAff Print the size as isl::pw_aff |
359 | void print(raw_ostream &OS, bool SizeAsPwAff = false) const; |
360 | |
361 | /// Access the ScopArrayInfo associated with an access function. |
362 | static const ScopArrayInfo *getFromAccessFunction(isl::pw_multi_aff PMA); |
363 | |
364 | /// Access the ScopArrayInfo associated with an isl Id. |
365 | static const ScopArrayInfo *getFromId(isl::id Id); |
366 | |
367 | /// Get the space of this array access. |
368 | isl::space getSpace() const; |
369 | |
370 | /// If the array is read only |
371 | bool isReadOnly(); |
372 | |
373 | /// Verify that @p Array is compatible to this ScopArrayInfo. |
374 | /// |
375 | /// Two arrays are compatible if their dimensionality, the sizes of their |
376 | /// dimensions, and their element sizes match. |
377 | /// |
378 | /// @param Array The array to compare against. |
379 | /// |
380 | /// @returns True, if the arrays are compatible, False otherwise. |
381 | bool isCompatibleWith(const ScopArrayInfo *Array) const; |
382 | |
383 | private: |
384 | void addDerivedSAI(ScopArrayInfo *DerivedSAI) { |
385 | DerivedSAIs.insert(X: DerivedSAI); |
386 | } |
387 | |
388 | /// For indirect accesses this is the SAI of the BP origin. |
389 | const ScopArrayInfo *BasePtrOriginSAI; |
390 | |
391 | /// For origin SAIs the set of derived indirect SAIs. |
392 | SmallSetVector<ScopArrayInfo *, 2> DerivedSAIs; |
393 | |
394 | /// The base pointer. |
395 | AssertingVH<Value> BasePtr; |
396 | |
397 | /// The canonical element type of this array. |
398 | /// |
399 | /// The canonical element type describes the minimal accessible element in |
400 | /// this array. Not all elements accessed, need to be of the very same type, |
401 | /// but the allocation size of the type of the elements loaded/stored from/to |
402 | /// this array needs to be a multiple of the allocation size of the canonical |
403 | /// type. |
404 | Type *ElementType; |
405 | |
406 | /// The isl id for the base pointer. |
407 | isl::id Id; |
408 | |
409 | /// True if the newly allocated array is on heap. |
410 | bool IsOnHeap = false; |
411 | |
412 | /// The sizes of each dimension as SCEV*. |
413 | SmallVector<const SCEV *, 4> DimensionSizes; |
414 | |
415 | /// The sizes of each dimension as isl::pw_aff. |
416 | SmallVector<isl::pw_aff, 4> DimensionSizesPw; |
417 | |
418 | /// The type of this scop array info object. |
419 | /// |
420 | /// We distinguish between SCALAR, PHI and ARRAY objects. |
421 | MemoryKind Kind; |
422 | |
423 | /// The data layout of the module. |
424 | const DataLayout &DL; |
425 | |
426 | /// The scop this SAI object belongs to. |
427 | Scop &S; |
428 | }; |
429 | |
430 | /// Represent memory accesses in statements. |
431 | class MemoryAccess final { |
432 | friend class Scop; |
433 | friend class ScopStmt; |
434 | friend class ScopBuilder; |
435 | |
436 | public: |
437 | /// The access type of a memory access |
438 | /// |
439 | /// There are three kind of access types: |
440 | /// |
441 | /// * A read access |
442 | /// |
443 | /// A certain set of memory locations are read and may be used for internal |
444 | /// calculations. |
445 | /// |
446 | /// * A must-write access |
447 | /// |
448 | /// A certain set of memory locations is definitely written. The old value is |
449 | /// replaced by a newly calculated value. The old value is not read or used at |
450 | /// all. |
451 | /// |
452 | /// * A may-write access |
453 | /// |
454 | /// A certain set of memory locations may be written. The memory location may |
455 | /// contain a new value if there is actually a write or the old value may |
456 | /// remain, if no write happens. |
457 | enum AccessType { |
458 | READ = 0x1, |
459 | MUST_WRITE = 0x2, |
460 | MAY_WRITE = 0x3, |
461 | }; |
462 | |
463 | /// Reduction access type |
464 | /// |
465 | /// Commutative and associative binary operations suitable for reductions |
466 | enum ReductionType { |
467 | RT_NONE, ///< Indicate no reduction at all |
468 | RT_ADD, ///< Addition |
469 | RT_MUL, ///< Multiplication |
470 | RT_BOR, ///< Bitwise Or |
471 | RT_BXOR, ///< Bitwise XOr |
472 | RT_BAND, ///< Bitwise And |
473 | }; |
474 | |
475 | using SubscriptsTy = SmallVector<const SCEV *, 4>; |
476 | |
477 | private: |
478 | /// A unique identifier for this memory access. |
479 | /// |
480 | /// The identifier is unique between all memory accesses belonging to the same |
481 | /// scop statement. |
482 | isl::id Id; |
483 | |
484 | /// What is modeled by this MemoryAccess. |
485 | /// @see MemoryKind |
486 | MemoryKind Kind; |
487 | |
488 | /// Whether it a reading or writing access, and if writing, whether it |
489 | /// is conditional (MAY_WRITE). |
490 | enum AccessType AccType; |
491 | |
492 | /// Reduction type for reduction like accesses, RT_NONE otherwise |
493 | /// |
494 | /// An access is reduction like if it is part of a load-store chain in which |
495 | /// both access the same memory location (use the same LLVM-IR value |
496 | /// as pointer reference). Furthermore, between the load and the store there |
497 | /// is exactly one binary operator which is known to be associative and |
498 | /// commutative. |
499 | /// |
500 | /// TODO: |
501 | /// |
502 | /// We can later lift the constraint that the same LLVM-IR value defines the |
503 | /// memory location to handle scops such as the following: |
504 | /// |
505 | /// for i |
506 | /// for j |
507 | /// sum[i+j] = sum[i] + 3; |
508 | /// |
509 | /// Here not all iterations access the same memory location, but iterations |
510 | /// for which j = 0 holds do. After lifting the equality check in ScopBuilder, |
511 | /// subsequent transformations do not only need check if a statement is |
512 | /// reduction like, but they also need to verify that the reduction |
513 | /// property is only exploited for statement instances that load from and |
514 | /// store to the same data location. Doing so at dependence analysis time |
515 | /// could allow us to handle the above example. |
516 | ReductionType RedType = RT_NONE; |
517 | |
518 | /// Parent ScopStmt of this access. |
519 | ScopStmt *Statement; |
520 | |
521 | /// The domain under which this access is not modeled precisely. |
522 | /// |
523 | /// The invalid domain for an access describes all parameter combinations |
524 | /// under which the statement looks to be executed but is in fact not because |
525 | /// some assumption/restriction makes the access invalid. |
526 | isl::set InvalidDomain; |
527 | |
528 | // Properties describing the accessed array. |
529 | // TODO: It might be possible to move them to ScopArrayInfo. |
530 | // @{ |
531 | |
532 | /// The base address (e.g., A for A[i+j]). |
533 | /// |
534 | /// The #BaseAddr of a memory access of kind MemoryKind::Array is the base |
535 | /// pointer of the memory access. |
536 | /// The #BaseAddr of a memory access of kind MemoryKind::PHI or |
537 | /// MemoryKind::ExitPHI is the PHI node itself. |
538 | /// The #BaseAddr of a memory access of kind MemoryKind::Value is the |
539 | /// instruction defining the value. |
540 | AssertingVH<Value> BaseAddr; |
541 | |
542 | /// Type a single array element wrt. this access. |
543 | Type *ElementType; |
544 | |
545 | /// Size of each dimension of the accessed array. |
546 | SmallVector<const SCEV *, 4> Sizes; |
547 | // @} |
548 | |
549 | // Properties describing the accessed element. |
550 | // @{ |
551 | |
552 | /// The access instruction of this memory access. |
553 | /// |
554 | /// For memory accesses of kind MemoryKind::Array the access instruction is |
555 | /// the Load or Store instruction performing the access. |
556 | /// |
557 | /// For memory accesses of kind MemoryKind::PHI or MemoryKind::ExitPHI the |
558 | /// access instruction of a load access is the PHI instruction. The access |
559 | /// instruction of a PHI-store is the incoming's block's terminator |
560 | /// instruction. |
561 | /// |
562 | /// For memory accesses of kind MemoryKind::Value the access instruction of a |
563 | /// load access is nullptr because generally there can be multiple |
564 | /// instructions in the statement using the same llvm::Value. The access |
565 | /// instruction of a write access is the instruction that defines the |
566 | /// llvm::Value. |
567 | Instruction *AccessInstruction = nullptr; |
568 | |
569 | /// Incoming block and value of a PHINode. |
570 | SmallVector<std::pair<BasicBlock *, Value *>, 4> Incoming; |
571 | |
572 | /// The value associated with this memory access. |
573 | /// |
574 | /// - For array memory accesses (MemoryKind::Array) it is the loaded result |
575 | /// or the stored value. If the access instruction is a memory intrinsic it |
576 | /// the access value is also the memory intrinsic. |
577 | /// - For accesses of kind MemoryKind::Value it is the access instruction |
578 | /// itself. |
579 | /// - For accesses of kind MemoryKind::PHI or MemoryKind::ExitPHI it is the |
580 | /// PHI node itself (for both, READ and WRITE accesses). |
581 | /// |
582 | AssertingVH<Value> AccessValue; |
583 | |
584 | /// Are all the subscripts affine expression? |
585 | bool IsAffine = true; |
586 | |
587 | /// Subscript expression for each dimension. |
588 | SubscriptsTy Subscripts; |
589 | |
590 | /// Relation from statement instances to the accessed array elements. |
591 | /// |
592 | /// In the common case this relation is a function that maps a set of loop |
593 | /// indices to the memory address from which a value is loaded/stored: |
594 | /// |
595 | /// for i |
596 | /// for j |
597 | /// S: A[i + 3 j] = ... |
598 | /// |
599 | /// => { S[i,j] -> A[i + 3j] } |
600 | /// |
601 | /// In case the exact access function is not known, the access relation may |
602 | /// also be a one to all mapping { S[i,j] -> A[o] } describing that any |
603 | /// element accessible through A might be accessed. |
604 | /// |
605 | /// In case of an access to a larger element belonging to an array that also |
606 | /// contains smaller elements, the access relation models the larger access |
607 | /// with multiple smaller accesses of the size of the minimal array element |
608 | /// type: |
609 | /// |
610 | /// short *A; |
611 | /// |
612 | /// for i |
613 | /// S: A[i] = *((double*)&A[4 * i]); |
614 | /// |
615 | /// => { S[i] -> A[i]; S[i] -> A[o] : 4i <= o <= 4i + 3 } |
616 | isl::map AccessRelation; |
617 | |
618 | /// Updated access relation read from JSCOP file. |
619 | isl::map NewAccessRelation; |
620 | // @} |
621 | |
622 | isl::basic_map createBasicAccessMap(ScopStmt *Statement); |
623 | |
624 | isl::set assumeNoOutOfBound(); |
625 | |
626 | /// Compute bounds on an over approximated access relation. |
627 | /// |
628 | /// @param ElementSize The size of one element accessed. |
629 | void computeBoundsOnAccessRelation(unsigned ElementSize); |
630 | |
631 | /// Get the original access function as read from IR. |
632 | isl::map getOriginalAccessRelation() const; |
633 | |
634 | /// Return the space in which the access relation lives in. |
635 | isl::space getOriginalAccessRelationSpace() const; |
636 | |
637 | /// Get the new access function imported or set by a pass |
638 | isl::map getNewAccessRelation() const; |
639 | |
640 | /// Fold the memory access to consider parametric offsets |
641 | /// |
642 | /// To recover memory accesses with array size parameters in the subscript |
643 | /// expression we post-process the delinearization results. |
644 | /// |
645 | /// We would normally recover from an access A[exp0(i) * N + exp1(i)] into an |
646 | /// array A[][N] the 2D access A[exp0(i)][exp1(i)]. However, another valid |
647 | /// delinearization is A[exp0(i) - 1][exp1(i) + N] which - depending on the |
648 | /// range of exp1(i) - may be preferable. Specifically, for cases where we |
649 | /// know exp1(i) is negative, we want to choose the latter expression. |
650 | /// |
651 | /// As we commonly do not have any information about the range of exp1(i), |
652 | /// we do not choose one of the two options, but instead create a piecewise |
653 | /// access function that adds the (-1, N) offsets as soon as exp1(i) becomes |
654 | /// negative. For a 2D array such an access function is created by applying |
655 | /// the piecewise map: |
656 | /// |
657 | /// [i,j] -> [i, j] : j >= 0 |
658 | /// [i,j] -> [i-1, j+N] : j < 0 |
659 | /// |
660 | /// We can generalize this mapping to arbitrary dimensions by applying this |
661 | /// piecewise mapping pairwise from the rightmost to the leftmost access |
662 | /// dimension. It would also be possible to cover a wider range by introducing |
663 | /// more cases and adding multiple of Ns to these cases. However, this has |
664 | /// not yet been necessary. |
665 | /// The introduction of different cases necessarily complicates the memory |
666 | /// access function, but cases that can be statically proven to not happen |
667 | /// will be eliminated later on. |
668 | void foldAccessRelation(); |
669 | |
670 | /// Create the access relation for the underlying memory intrinsic. |
671 | void buildMemIntrinsicAccessRelation(); |
672 | |
673 | /// Assemble the access relation from all available information. |
674 | /// |
675 | /// In particular, used the information passes in the constructor and the |
676 | /// parent ScopStmt set by setStatment(). |
677 | /// |
678 | /// @param SAI Info object for the accessed array. |
679 | void buildAccessRelation(const ScopArrayInfo *SAI); |
680 | |
681 | /// Carry index overflows of dimensions with constant size to the next higher |
682 | /// dimension. |
683 | /// |
684 | /// For dimensions that have constant size, modulo the index by the size and |
685 | /// add up the carry (floored division) to the next higher dimension. This is |
686 | /// how overflow is defined in row-major order. |
687 | /// It happens e.g. when ScalarEvolution computes the offset to the base |
688 | /// pointer and would algebraically sum up all lower dimensions' indices of |
689 | /// constant size. |
690 | /// |
691 | /// Example: |
692 | /// float (*A)[4]; |
693 | /// A[1][6] -> A[2][2] |
694 | void wrapConstantDimensions(); |
695 | |
696 | public: |
697 | /// Create a new MemoryAccess. |
698 | /// |
699 | /// @param Stmt The parent statement. |
700 | /// @param AccessInst The instruction doing the access. |
701 | /// @param BaseAddr The accessed array's address. |
702 | /// @param ElemType The type of the accessed array elements. |
703 | /// @param AccType Whether read or write access. |
704 | /// @param IsAffine Whether the subscripts are affine expressions. |
705 | /// @param Kind The kind of memory accessed. |
706 | /// @param Subscripts Subscript expressions |
707 | /// @param Sizes Dimension lengths of the accessed array. |
708 | MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst, AccessType AccType, |
709 | Value *BaseAddress, Type *ElemType, bool Affine, |
710 | ArrayRef<const SCEV *> Subscripts, ArrayRef<const SCEV *> Sizes, |
711 | Value *AccessValue, MemoryKind Kind); |
712 | |
713 | /// Create a new MemoryAccess that corresponds to @p AccRel. |
714 | /// |
715 | /// Along with @p Stmt and @p AccType it uses information about dimension |
716 | /// lengths of the accessed array, the type of the accessed array elements, |
717 | /// the name of the accessed array that is derived from the object accessible |
718 | /// via @p AccRel. |
719 | /// |
720 | /// @param Stmt The parent statement. |
721 | /// @param AccType Whether read or write access. |
722 | /// @param AccRel The access relation that describes the memory access. |
723 | MemoryAccess(ScopStmt *Stmt, AccessType AccType, isl::map AccRel); |
724 | |
725 | MemoryAccess(const MemoryAccess &) = delete; |
726 | MemoryAccess &operator=(const MemoryAccess &) = delete; |
727 | ~MemoryAccess(); |
728 | |
729 | /// Add a new incoming block/value pairs for this PHI/ExitPHI access. |
730 | /// |
731 | /// @param IncomingBlock The PHI's incoming block. |
732 | /// @param IncomingValue The value when reaching the PHI from the @p |
733 | /// IncomingBlock. |
734 | void addIncoming(BasicBlock *IncomingBlock, Value *IncomingValue) { |
735 | assert(!isRead()); |
736 | assert(isAnyPHIKind()); |
737 | Incoming.emplace_back(Args: std::make_pair(x&: IncomingBlock, y&: IncomingValue)); |
738 | } |
739 | |
740 | /// Return the list of possible PHI/ExitPHI values. |
741 | /// |
742 | /// After code generation moves some PHIs around during region simplification, |
743 | /// we cannot reliably locate the original PHI node and its incoming values |
744 | /// anymore. For this reason we remember these explicitly for all PHI-kind |
745 | /// accesses. |
746 | ArrayRef<std::pair<BasicBlock *, Value *>> getIncoming() const { |
747 | assert(isAnyPHIKind()); |
748 | return Incoming; |
749 | } |
750 | |
751 | /// Get the type of a memory access. |
752 | enum AccessType getType() { return AccType; } |
753 | |
754 | /// Is this a reduction like access? |
755 | bool isReductionLike() const { return RedType != RT_NONE; } |
756 | |
757 | /// Is this a read memory access? |
758 | bool isRead() const { return AccType == MemoryAccess::READ; } |
759 | |
760 | /// Is this a must-write memory access? |
761 | bool isMustWrite() const { return AccType == MemoryAccess::MUST_WRITE; } |
762 | |
763 | /// Is this a may-write memory access? |
764 | bool isMayWrite() const { return AccType == MemoryAccess::MAY_WRITE; } |
765 | |
766 | /// Is this a write memory access? |
767 | bool isWrite() const { return isMustWrite() || isMayWrite(); } |
768 | |
769 | /// Is this a memory intrinsic access (memcpy, memset, memmove)? |
770 | bool isMemoryIntrinsic() const { |
771 | return isa<MemIntrinsic>(Val: getAccessInstruction()); |
772 | } |
773 | |
774 | /// Check if a new access relation was imported or set by a pass. |
775 | bool hasNewAccessRelation() const { return !NewAccessRelation.is_null(); } |
776 | |
777 | /// Return the newest access relation of this access. |
778 | /// |
779 | /// There are two possibilities: |
780 | /// 1) The original access relation read from the LLVM-IR. |
781 | /// 2) A new access relation imported from a json file or set by another |
782 | /// pass (e.g., for privatization). |
783 | /// |
784 | /// As 2) is by construction "newer" than 1) we return the new access |
785 | /// relation if present. |
786 | /// |
787 | isl::map getLatestAccessRelation() const { |
788 | return hasNewAccessRelation() ? getNewAccessRelation() |
789 | : getOriginalAccessRelation(); |
790 | } |
791 | |
792 | /// Old name of getLatestAccessRelation(). |
793 | isl::map getAccessRelation() const { return getLatestAccessRelation(); } |
794 | |
795 | /// Get an isl map describing the memory address accessed. |
796 | /// |
797 | /// In most cases the memory address accessed is well described by the access |
798 | /// relation obtained with getAccessRelation. However, in case of arrays |
799 | /// accessed with types of different size the access relation maps one access |
800 | /// to multiple smaller address locations. This method returns an isl map that |
801 | /// relates each dynamic statement instance to the unique memory location |
802 | /// that is loaded from / stored to. |
803 | /// |
804 | /// For an access relation { S[i] -> A[o] : 4i <= o <= 4i + 3 } this method |
805 | /// will return the address function { S[i] -> A[4i] }. |
806 | /// |
807 | /// @returns The address function for this memory access. |
808 | isl::map getAddressFunction() const; |
809 | |
810 | /// Return the access relation after the schedule was applied. |
811 | isl::pw_multi_aff |
812 | applyScheduleToAccessRelation(isl::union_map Schedule) const; |
813 | |
814 | /// Get an isl string representing the access function read from IR. |
815 | std::string getOriginalAccessRelationStr() const; |
816 | |
817 | /// Get an isl string representing a new access function, if available. |
818 | std::string getNewAccessRelationStr() const; |
819 | |
820 | /// Get an isl string representing the latest access relation. |
821 | std::string getAccessRelationStr() const; |
822 | |
823 | /// Get the original base address of this access (e.g. A for A[i+j]) when |
824 | /// detected. |
825 | /// |
826 | /// This address may differ from the base address referenced by the original |
827 | /// ScopArrayInfo to which this array belongs, as this memory access may |
828 | /// have been canonicalized to a ScopArrayInfo which has a different but |
829 | /// identically-valued base pointer in case invariant load hoisting is |
830 | /// enabled. |
831 | Value *getOriginalBaseAddr() const { return BaseAddr; } |
832 | |
833 | /// Get the detection-time base array isl::id for this access. |
834 | isl::id getOriginalArrayId() const; |
835 | |
836 | /// Get the base array isl::id for this access, modifiable through |
837 | /// setNewAccessRelation(). |
838 | isl::id getLatestArrayId() const; |
839 | |
840 | /// Old name of getOriginalArrayId(). |
841 | isl::id getArrayId() const { return getOriginalArrayId(); } |
842 | |
843 | /// Get the detection-time ScopArrayInfo object for the base address. |
844 | const ScopArrayInfo *getOriginalScopArrayInfo() const; |
845 | |
846 | /// Get the ScopArrayInfo object for the base address, or the one set |
847 | /// by setNewAccessRelation(). |
848 | const ScopArrayInfo *getLatestScopArrayInfo() const; |
849 | |
850 | /// Legacy name of getOriginalScopArrayInfo(). |
851 | const ScopArrayInfo *getScopArrayInfo() const { |
852 | return getOriginalScopArrayInfo(); |
853 | } |
854 | |
855 | /// Return a string representation of the access's reduction type. |
856 | const std::string getReductionOperatorStr() const; |
857 | |
858 | /// Return a string representation of the reduction type @p RT. |
859 | static const std::string getReductionOperatorStr(ReductionType RT); |
860 | |
861 | /// Return the element type of the accessed array wrt. this access. |
862 | Type *getElementType() const { return ElementType; } |
863 | |
864 | /// Return the access value of this memory access. |
865 | Value *getAccessValue() const { return AccessValue; } |
866 | |
867 | /// Return llvm::Value that is stored by this access, if available. |
868 | /// |
869 | /// PHI nodes may not have a unique value available that is stored, as in |
870 | /// case of region statements one out of possibly several llvm::Values |
871 | /// might be stored. In this case nullptr is returned. |
872 | Value *tryGetValueStored() { |
873 | assert(isWrite() && "Only write statement store values" ); |
874 | if (isAnyPHIKind()) { |
875 | if (Incoming.size() == 1) |
876 | return Incoming[0].second; |
877 | return nullptr; |
878 | } |
879 | return AccessValue; |
880 | } |
881 | |
882 | /// Return the access instruction of this memory access. |
883 | Instruction *getAccessInstruction() const { return AccessInstruction; } |
884 | |
885 | /// Return an iterator range containing the subscripts. |
886 | iterator_range<SubscriptsTy::const_iterator> subscripts() const { |
887 | return make_range(x: Subscripts.begin(), y: Subscripts.end()); |
888 | } |
889 | |
890 | /// Return the number of access function subscript. |
891 | unsigned getNumSubscripts() const { return Subscripts.size(); } |
892 | |
893 | /// Return the access function subscript in the dimension @p Dim. |
894 | const SCEV *getSubscript(unsigned Dim) const { return Subscripts[Dim]; } |
895 | |
896 | /// Compute the isl representation for the SCEV @p E wrt. this access. |
897 | /// |
898 | /// Note that this function will also adjust the invalid context accordingly. |
899 | isl::pw_aff getPwAff(const SCEV *E); |
900 | |
901 | /// Get the invalid domain for this access. |
902 | isl::set getInvalidDomain() const { return InvalidDomain; } |
903 | |
904 | /// Get the invalid context for this access. |
905 | isl::set getInvalidContext() const { return getInvalidDomain().params(); } |
906 | |
907 | /// Get the stride of this memory access in the specified Schedule. Schedule |
908 | /// is a map from the statement to a schedule where the innermost dimension is |
909 | /// the dimension of the innermost loop containing the statement. |
910 | isl::set getStride(isl::map Schedule) const; |
911 | |
912 | /// Is the stride of the access equal to a certain width? Schedule is a map |
913 | /// from the statement to a schedule where the innermost dimension is the |
914 | /// dimension of the innermost loop containing the statement. |
915 | bool isStrideX(isl::map Schedule, int StrideWidth) const; |
916 | |
917 | /// Is consecutive memory accessed for a given statement instance set? |
918 | /// Schedule is a map from the statement to a schedule where the innermost |
919 | /// dimension is the dimension of the innermost loop containing the |
920 | /// statement. |
921 | bool isStrideOne(isl::map Schedule) const; |
922 | |
923 | /// Is always the same memory accessed for a given statement instance set? |
924 | /// Schedule is a map from the statement to a schedule where the innermost |
925 | /// dimension is the dimension of the innermost loop containing the |
926 | /// statement. |
927 | bool isStrideZero(isl::map Schedule) const; |
928 | |
929 | /// Return the kind when this access was first detected. |
930 | MemoryKind getOriginalKind() const { |
931 | assert(!getOriginalScopArrayInfo() /* not yet initialized */ || |
932 | getOriginalScopArrayInfo()->getKind() == Kind); |
933 | return Kind; |
934 | } |
935 | |
936 | /// Return the kind considering a potential setNewAccessRelation. |
937 | MemoryKind getLatestKind() const { |
938 | return getLatestScopArrayInfo()->getKind(); |
939 | } |
940 | |
941 | /// Whether this is an access of an explicit load or store in the IR. |
942 | bool isOriginalArrayKind() const { |
943 | return getOriginalKind() == MemoryKind::Array; |
944 | } |
945 | |
946 | /// Whether storage memory is either an custom .s2a/.phiops alloca |
947 | /// (false) or an existing pointer into an array (true). |
948 | bool isLatestArrayKind() const { |
949 | return getLatestKind() == MemoryKind::Array; |
950 | } |
951 | |
952 | /// Old name of isOriginalArrayKind. |
953 | bool isArrayKind() const { return isOriginalArrayKind(); } |
954 | |
955 | /// Whether this access is an array to a scalar memory object, without |
956 | /// considering changes by setNewAccessRelation. |
957 | /// |
958 | /// Scalar accesses are accesses to MemoryKind::Value, MemoryKind::PHI or |
959 | /// MemoryKind::ExitPHI. |
960 | bool isOriginalScalarKind() const { |
961 | return getOriginalKind() != MemoryKind::Array; |
962 | } |
963 | |
964 | /// Whether this access is an array to a scalar memory object, also |
965 | /// considering changes by setNewAccessRelation. |
966 | bool isLatestScalarKind() const { |
967 | return getLatestKind() != MemoryKind::Array; |
968 | } |
969 | |
970 | /// Old name of isOriginalScalarKind. |
971 | bool isScalarKind() const { return isOriginalScalarKind(); } |
972 | |
973 | /// Was this MemoryAccess detected as a scalar dependences? |
974 | bool isOriginalValueKind() const { |
975 | return getOriginalKind() == MemoryKind::Value; |
976 | } |
977 | |
978 | /// Is this MemoryAccess currently modeling scalar dependences? |
979 | bool isLatestValueKind() const { |
980 | return getLatestKind() == MemoryKind::Value; |
981 | } |
982 | |
983 | /// Old name of isOriginalValueKind(). |
984 | bool isValueKind() const { return isOriginalValueKind(); } |
985 | |
986 | /// Was this MemoryAccess detected as a special PHI node access? |
987 | bool isOriginalPHIKind() const { |
988 | return getOriginalKind() == MemoryKind::PHI; |
989 | } |
990 | |
991 | /// Is this MemoryAccess modeling special PHI node accesses, also |
992 | /// considering a potential change by setNewAccessRelation? |
993 | bool isLatestPHIKind() const { return getLatestKind() == MemoryKind::PHI; } |
994 | |
995 | /// Old name of isOriginalPHIKind. |
996 | bool isPHIKind() const { return isOriginalPHIKind(); } |
997 | |
998 | /// Was this MemoryAccess detected as the accesses of a PHI node in the |
999 | /// SCoP's exit block? |
1000 | bool isOriginalExitPHIKind() const { |
1001 | return getOriginalKind() == MemoryKind::ExitPHI; |
1002 | } |
1003 | |
1004 | /// Is this MemoryAccess modeling the accesses of a PHI node in the |
1005 | /// SCoP's exit block? Can be changed to an array access using |
1006 | /// setNewAccessRelation(). |
1007 | bool isLatestExitPHIKind() const { |
1008 | return getLatestKind() == MemoryKind::ExitPHI; |
1009 | } |
1010 | |
1011 | /// Old name of isOriginalExitPHIKind(). |
1012 | bool isExitPHIKind() const { return isOriginalExitPHIKind(); } |
1013 | |
1014 | /// Was this access detected as one of the two PHI types? |
1015 | bool isOriginalAnyPHIKind() const { |
1016 | return isOriginalPHIKind() || isOriginalExitPHIKind(); |
1017 | } |
1018 | |
1019 | /// Does this access originate from one of the two PHI types? Can be |
1020 | /// changed to an array access using setNewAccessRelation(). |
1021 | bool isLatestAnyPHIKind() const { |
1022 | return isLatestPHIKind() || isLatestExitPHIKind(); |
1023 | } |
1024 | |
1025 | /// Old name of isOriginalAnyPHIKind(). |
1026 | bool isAnyPHIKind() const { return isOriginalAnyPHIKind(); } |
1027 | |
1028 | /// Get the statement that contains this memory access. |
1029 | ScopStmt *getStatement() const { return Statement; } |
1030 | |
1031 | /// Get the reduction type of this access |
1032 | ReductionType getReductionType() const { return RedType; } |
1033 | |
1034 | /// Update the original access relation. |
1035 | /// |
1036 | /// We need to update the original access relation during scop construction, |
1037 | /// when unifying the memory accesses that access the same scop array info |
1038 | /// object. After the scop has been constructed, the original access relation |
1039 | /// should not be changed any more. Instead setNewAccessRelation should |
1040 | /// be called. |
1041 | void setAccessRelation(isl::map AccessRelation); |
1042 | |
1043 | /// Set the updated access relation read from JSCOP file. |
1044 | void setNewAccessRelation(isl::map NewAccessRelation); |
1045 | |
1046 | /// Return whether the MemoryyAccess is a partial access. That is, the access |
1047 | /// is not executed in some instances of the parent statement's domain. |
1048 | bool isLatestPartialAccess() const; |
1049 | |
1050 | /// Mark this a reduction like access |
1051 | void markAsReductionLike(ReductionType RT) { RedType = RT; } |
1052 | |
1053 | /// Align the parameters in the access relation to the scop context |
1054 | void realignParams(); |
1055 | |
1056 | /// Update the dimensionality of the memory access. |
1057 | /// |
1058 | /// During scop construction some memory accesses may not be constructed with |
1059 | /// their full dimensionality, but outer dimensions may have been omitted if |
1060 | /// they took the value 'zero'. By updating the dimensionality of the |
1061 | /// statement we add additional zero-valued dimensions to match the |
1062 | /// dimensionality of the ScopArrayInfo object that belongs to this memory |
1063 | /// access. |
1064 | void updateDimensionality(); |
1065 | |
1066 | /// Get identifier for the memory access. |
1067 | /// |
1068 | /// This identifier is unique for all accesses that belong to the same scop |
1069 | /// statement. |
1070 | isl::id getId() const; |
1071 | |
1072 | /// Print the MemoryAccess. |
1073 | /// |
1074 | /// @param OS The output stream the MemoryAccess is printed to. |
1075 | void print(raw_ostream &OS) const; |
1076 | |
1077 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
1078 | /// Print the MemoryAccess to stderr. |
1079 | void dump() const; |
1080 | #endif |
1081 | |
1082 | /// Is the memory access affine? |
1083 | bool isAffine() const { return IsAffine; } |
1084 | }; |
1085 | |
1086 | raw_ostream &operator<<(raw_ostream &OS, MemoryAccess::ReductionType RT); |
1087 | |
1088 | /// Ordered list type to hold accesses. |
1089 | using MemoryAccessList = std::forward_list<MemoryAccess *>; |
1090 | |
1091 | /// Helper structure for invariant memory accesses. |
1092 | struct InvariantAccess { |
1093 | /// The memory access that is (partially) invariant. |
1094 | MemoryAccess *MA; |
1095 | |
1096 | /// The context under which the access is not invariant. |
1097 | isl::set NonHoistableCtx; |
1098 | }; |
1099 | |
1100 | /// Ordered container type to hold invariant accesses. |
1101 | using InvariantAccessesTy = SmallVector<InvariantAccess, 8>; |
1102 | |
1103 | /// Type for equivalent invariant accesses and their domain context. |
1104 | struct InvariantEquivClassTy { |
1105 | /// The pointer that identifies this equivalence class |
1106 | const SCEV *IdentifyingPointer; |
1107 | |
1108 | /// Memory accesses now treated invariant |
1109 | /// |
1110 | /// These memory accesses access the pointer location that identifies |
1111 | /// this equivalence class. They are treated as invariant and hoisted during |
1112 | /// code generation. |
1113 | MemoryAccessList InvariantAccesses; |
1114 | |
1115 | /// The execution context under which the memory location is accessed |
1116 | /// |
1117 | /// It is the union of the execution domains of the memory accesses in the |
1118 | /// InvariantAccesses list. |
1119 | isl::set ExecutionContext; |
1120 | |
1121 | /// The type of the invariant access |
1122 | /// |
1123 | /// It is used to differentiate between differently typed invariant loads from |
1124 | /// the same location. |
1125 | Type *AccessType; |
1126 | }; |
1127 | |
1128 | /// Type for invariant accesses equivalence classes. |
1129 | using InvariantEquivClassesTy = SmallVector<InvariantEquivClassTy, 8>; |
1130 | |
1131 | /// Statement of the Scop |
1132 | /// |
1133 | /// A Scop statement represents an instruction in the Scop. |
1134 | /// |
1135 | /// It is further described by its iteration domain, its schedule and its data |
1136 | /// accesses. |
1137 | /// At the moment every statement represents a single basic block of LLVM-IR. |
1138 | class ScopStmt final { |
1139 | friend class ScopBuilder; |
1140 | |
1141 | public: |
1142 | /// Create the ScopStmt from a BasicBlock. |
1143 | ScopStmt(Scop &parent, BasicBlock &bb, StringRef Name, Loop *SurroundingLoop, |
1144 | std::vector<Instruction *> Instructions); |
1145 | |
1146 | /// Create an overapproximating ScopStmt for the region @p R. |
1147 | /// |
1148 | /// @param EntryBlockInstructions The list of instructions that belong to the |
1149 | /// entry block of the region statement. |
1150 | /// Instructions are only tracked for entry |
1151 | /// blocks for now. We currently do not allow |
1152 | /// to modify the instructions of blocks later |
1153 | /// in the region statement. |
1154 | ScopStmt(Scop &parent, Region &R, StringRef Name, Loop *SurroundingLoop, |
1155 | std::vector<Instruction *> EntryBlockInstructions); |
1156 | |
1157 | /// Create a copy statement. |
1158 | /// |
1159 | /// @param Stmt The parent statement. |
1160 | /// @param SourceRel The source location. |
1161 | /// @param TargetRel The target location. |
1162 | /// @param Domain The original domain under which the copy statement would |
1163 | /// be executed. |
1164 | ScopStmt(Scop &parent, isl::map SourceRel, isl::map TargetRel, |
1165 | isl::set Domain); |
1166 | |
1167 | ScopStmt(const ScopStmt &) = delete; |
1168 | const ScopStmt &operator=(const ScopStmt &) = delete; |
1169 | ~ScopStmt(); |
1170 | |
1171 | private: |
1172 | /// Polyhedral description |
1173 | //@{ |
1174 | |
1175 | /// The Scop containing this ScopStmt. |
1176 | Scop &Parent; |
1177 | |
1178 | /// The domain under which this statement is not modeled precisely. |
1179 | /// |
1180 | /// The invalid domain for a statement describes all parameter combinations |
1181 | /// under which the statement looks to be executed but is in fact not because |
1182 | /// some assumption/restriction makes the statement/scop invalid. |
1183 | isl::set InvalidDomain; |
1184 | |
1185 | /// The iteration domain describes the set of iterations for which this |
1186 | /// statement is executed. |
1187 | /// |
1188 | /// Example: |
1189 | /// for (i = 0; i < 100 + b; ++i) |
1190 | /// for (j = 0; j < i; ++j) |
1191 | /// S(i,j); |
1192 | /// |
1193 | /// 'S' is executed for different values of i and j. A vector of all |
1194 | /// induction variables around S (i, j) is called iteration vector. |
1195 | /// The domain describes the set of possible iteration vectors. |
1196 | /// |
1197 | /// In this case it is: |
1198 | /// |
1199 | /// Domain: 0 <= i <= 100 + b |
1200 | /// 0 <= j <= i |
1201 | /// |
1202 | /// A pair of statement and iteration vector (S, (5,3)) is called statement |
1203 | /// instance. |
1204 | isl::set Domain; |
1205 | |
1206 | /// The memory accesses of this statement. |
1207 | /// |
1208 | /// The only side effects of a statement are its memory accesses. |
1209 | using MemoryAccessVec = llvm::SmallVector<MemoryAccess *, 8>; |
1210 | MemoryAccessVec MemAccs; |
1211 | |
1212 | /// Mapping from instructions to (scalar) memory accesses. |
1213 | DenseMap<const Instruction *, MemoryAccessList> InstructionToAccess; |
1214 | |
1215 | /// The set of values defined elsewhere required in this ScopStmt and |
1216 | /// their MemoryKind::Value READ MemoryAccesses. |
1217 | DenseMap<Value *, MemoryAccess *> ValueReads; |
1218 | |
1219 | /// The set of values defined in this ScopStmt that are required |
1220 | /// elsewhere, mapped to their MemoryKind::Value WRITE MemoryAccesses. |
1221 | DenseMap<Instruction *, MemoryAccess *> ValueWrites; |
1222 | |
1223 | /// Map from PHI nodes to its incoming value when coming from this |
1224 | /// statement. |
1225 | /// |
1226 | /// Non-affine subregions can have multiple exiting blocks that are incoming |
1227 | /// blocks of the PHI nodes. This map ensures that there is only one write |
1228 | /// operation for the complete subregion. A PHI selecting the relevant value |
1229 | /// will be inserted. |
1230 | DenseMap<PHINode *, MemoryAccess *> PHIWrites; |
1231 | |
1232 | /// Map from PHI nodes to its read access in this statement. |
1233 | DenseMap<PHINode *, MemoryAccess *> PHIReads; |
1234 | |
1235 | //@} |
1236 | |
1237 | /// A SCoP statement represents either a basic block (affine/precise case) or |
1238 | /// a whole region (non-affine case). |
1239 | /// |
1240 | /// Only one of the following two members will therefore be set and indicate |
1241 | /// which kind of statement this is. |
1242 | /// |
1243 | ///{ |
1244 | |
1245 | /// The BasicBlock represented by this statement (in the affine case). |
1246 | BasicBlock *BB = nullptr; |
1247 | |
1248 | /// The region represented by this statement (in the non-affine case). |
1249 | Region *R = nullptr; |
1250 | |
1251 | ///} |
1252 | |
1253 | /// The isl AST build for the new generated AST. |
1254 | isl::ast_build Build; |
1255 | |
1256 | SmallVector<Loop *, 4> NestLoops; |
1257 | |
1258 | std::string BaseName; |
1259 | |
1260 | /// The closest loop that contains this statement. |
1261 | Loop *SurroundingLoop; |
1262 | |
1263 | /// Vector for Instructions in this statement. |
1264 | std::vector<Instruction *> Instructions; |
1265 | |
1266 | /// Remove @p MA from dictionaries pointing to them. |
1267 | void removeAccessData(MemoryAccess *MA); |
1268 | |
1269 | public: |
1270 | /// Get an isl_ctx pointer. |
1271 | isl::ctx getIslCtx() const; |
1272 | |
1273 | /// Get the iteration domain of this ScopStmt. |
1274 | /// |
1275 | /// @return The iteration domain of this ScopStmt. |
1276 | isl::set getDomain() const; |
1277 | |
1278 | /// Get the space of the iteration domain |
1279 | /// |
1280 | /// @return The space of the iteration domain |
1281 | isl::space getDomainSpace() const; |
1282 | |
1283 | /// Get the id of the iteration domain space |
1284 | /// |
1285 | /// @return The id of the iteration domain space |
1286 | isl::id getDomainId() const; |
1287 | |
1288 | /// Get an isl string representing this domain. |
1289 | std::string getDomainStr() const; |
1290 | |
1291 | /// Get the schedule function of this ScopStmt. |
1292 | /// |
1293 | /// @return The schedule function of this ScopStmt, if it does not contain |
1294 | /// extension nodes, and nullptr, otherwise. |
1295 | isl::map getSchedule() const; |
1296 | |
1297 | /// Get an isl string representing this schedule. |
1298 | /// |
1299 | /// @return An isl string representing this schedule, if it does not contain |
1300 | /// extension nodes, and an empty string, otherwise. |
1301 | std::string getScheduleStr() const; |
1302 | |
1303 | /// Get the invalid domain for this statement. |
1304 | isl::set getInvalidDomain() const { return InvalidDomain; } |
1305 | |
1306 | /// Get the invalid context for this statement. |
1307 | isl::set getInvalidContext() const { return getInvalidDomain().params(); } |
1308 | |
1309 | /// Set the invalid context for this statement to @p ID. |
1310 | void setInvalidDomain(isl::set ID); |
1311 | |
1312 | /// Get the BasicBlock represented by this ScopStmt (if any). |
1313 | /// |
1314 | /// @return The BasicBlock represented by this ScopStmt, or null if the |
1315 | /// statement represents a region. |
1316 | BasicBlock *getBasicBlock() const { return BB; } |
1317 | |
1318 | /// Return true if this statement represents a single basic block. |
1319 | bool isBlockStmt() const { return BB != nullptr; } |
1320 | |
1321 | /// Return true if this is a copy statement. |
1322 | bool isCopyStmt() const { return BB == nullptr && R == nullptr; } |
1323 | |
1324 | /// Get the region represented by this ScopStmt (if any). |
1325 | /// |
1326 | /// @return The region represented by this ScopStmt, or null if the statement |
1327 | /// represents a basic block. |
1328 | Region *getRegion() const { return R; } |
1329 | |
1330 | /// Return true if this statement represents a whole region. |
1331 | bool isRegionStmt() const { return R != nullptr; } |
1332 | |
1333 | /// Return a BasicBlock from this statement. |
1334 | /// |
1335 | /// For block statements, it returns the BasicBlock itself. For subregion |
1336 | /// statements, return its entry block. |
1337 | BasicBlock *getEntryBlock() const; |
1338 | |
1339 | /// Return whether @p L is boxed within this statement. |
1340 | bool contains(const Loop *L) const { |
1341 | // Block statements never contain loops. |
1342 | if (isBlockStmt()) |
1343 | return false; |
1344 | |
1345 | return getRegion()->contains(L); |
1346 | } |
1347 | |
1348 | /// Return whether this statement represents @p BB. |
1349 | bool represents(BasicBlock *BB) const { |
1350 | if (isCopyStmt()) |
1351 | return false; |
1352 | if (isBlockStmt()) |
1353 | return BB == getBasicBlock(); |
1354 | return getRegion()->contains(BB); |
1355 | } |
1356 | |
1357 | /// Return whether this statement contains @p Inst. |
1358 | bool contains(Instruction *Inst) const { |
1359 | if (!Inst) |
1360 | return false; |
1361 | if (isBlockStmt()) |
1362 | return llvm::is_contained(Range: Instructions, Element: Inst); |
1363 | return represents(BB: Inst->getParent()); |
1364 | } |
1365 | |
1366 | /// Return the closest innermost loop that contains this statement, but is not |
1367 | /// contained in it. |
1368 | /// |
1369 | /// For block statement, this is just the loop that contains the block. Region |
1370 | /// statements can contain boxed loops, so getting the loop of one of the |
1371 | /// region's BBs might return such an inner loop. For instance, the region's |
1372 | /// entry could be a header of a loop, but the region might extend to BBs |
1373 | /// after the loop exit. Similarly, the region might only contain parts of the |
1374 | /// loop body and still include the loop header. |
1375 | /// |
1376 | /// Most of the time the surrounding loop is the top element of #NestLoops, |
1377 | /// except when it is empty. In that case it return the loop that the whole |
1378 | /// SCoP is contained in. That can be nullptr if there is no such loop. |
1379 | Loop *getSurroundingLoop() const { |
1380 | assert(!isCopyStmt() && |
1381 | "No surrounding loop for artificially created statements" ); |
1382 | return SurroundingLoop; |
1383 | } |
1384 | |
1385 | /// Return true if this statement does not contain any accesses. |
1386 | bool isEmpty() const { return MemAccs.empty(); } |
1387 | |
1388 | /// Find all array accesses for @p Inst. |
1389 | /// |
1390 | /// @param Inst The instruction accessing an array. |
1391 | /// |
1392 | /// @return A list of array accesses (MemoryKind::Array) accessed by @p Inst. |
1393 | /// If there is no such access, it returns nullptr. |
1394 | const MemoryAccessList * |
1395 | lookupArrayAccessesFor(const Instruction *Inst) const { |
1396 | auto It = InstructionToAccess.find(Val: Inst); |
1397 | if (It == InstructionToAccess.end()) |
1398 | return nullptr; |
1399 | if (It->second.empty()) |
1400 | return nullptr; |
1401 | return &It->second; |
1402 | } |
1403 | |
1404 | /// Return the only array access for @p Inst, if existing. |
1405 | /// |
1406 | /// @param Inst The instruction for which to look up the access. |
1407 | /// @returns The unique array memory access related to Inst or nullptr if |
1408 | /// no array access exists |
1409 | MemoryAccess *getArrayAccessOrNULLFor(const Instruction *Inst) const { |
1410 | auto It = InstructionToAccess.find(Val: Inst); |
1411 | if (It == InstructionToAccess.end()) |
1412 | return nullptr; |
1413 | |
1414 | MemoryAccess *ArrayAccess = nullptr; |
1415 | |
1416 | for (auto Access : It->getSecond()) { |
1417 | if (!Access->isArrayKind()) |
1418 | continue; |
1419 | |
1420 | assert(!ArrayAccess && "More then one array access for instruction" ); |
1421 | |
1422 | ArrayAccess = Access; |
1423 | } |
1424 | |
1425 | return ArrayAccess; |
1426 | } |
1427 | |
1428 | /// Return the only array access for @p Inst. |
1429 | /// |
1430 | /// @param Inst The instruction for which to look up the access. |
1431 | /// @returns The unique array memory access related to Inst. |
1432 | MemoryAccess &getArrayAccessFor(const Instruction *Inst) const { |
1433 | MemoryAccess *ArrayAccess = getArrayAccessOrNULLFor(Inst); |
1434 | |
1435 | assert(ArrayAccess && "No array access found for instruction!" ); |
1436 | return *ArrayAccess; |
1437 | } |
1438 | |
1439 | /// Return the MemoryAccess that writes the value of an instruction |
1440 | /// defined in this statement, or nullptr if not existing, respectively |
1441 | /// not yet added. |
1442 | MemoryAccess *lookupValueWriteOf(Instruction *Inst) const { |
1443 | assert((isRegionStmt() && R->contains(Inst)) || |
1444 | (!isRegionStmt() && Inst->getParent() == BB)); |
1445 | return ValueWrites.lookup(Val: Inst); |
1446 | } |
1447 | |
1448 | /// Return the MemoryAccess that reloads a value, or nullptr if not |
1449 | /// existing, respectively not yet added. |
1450 | MemoryAccess *lookupValueReadOf(Value *Inst) const { |
1451 | return ValueReads.lookup(Val: Inst); |
1452 | } |
1453 | |
1454 | /// Return the MemoryAccess that loads a PHINode value, or nullptr if not |
1455 | /// existing, respectively not yet added. |
1456 | MemoryAccess *lookupPHIReadOf(PHINode *PHI) const { |
1457 | return PHIReads.lookup(Val: PHI); |
1458 | } |
1459 | |
1460 | /// Return the PHI write MemoryAccess for the incoming values from any |
1461 | /// basic block in this ScopStmt, or nullptr if not existing, |
1462 | /// respectively not yet added. |
1463 | MemoryAccess *lookupPHIWriteOf(PHINode *PHI) const { |
1464 | assert(isBlockStmt() || R->getExit() == PHI->getParent()); |
1465 | return PHIWrites.lookup(Val: PHI); |
1466 | } |
1467 | |
1468 | /// Return the input access of the value, or null if no such MemoryAccess |
1469 | /// exists. |
1470 | /// |
1471 | /// The input access is the MemoryAccess that makes an inter-statement value |
1472 | /// available in this statement by reading it at the start of this statement. |
1473 | /// This can be a MemoryKind::Value if defined in another statement or a |
1474 | /// MemoryKind::PHI if the value is a PHINode in this statement. |
1475 | MemoryAccess *lookupInputAccessOf(Value *Val) const { |
1476 | if (isa<PHINode>(Val)) |
1477 | if (auto InputMA = lookupPHIReadOf(PHI: cast<PHINode>(Val))) { |
1478 | assert(!lookupValueReadOf(Val) && "input accesses must be unique; a " |
1479 | "statement cannot read a .s2a and " |
1480 | ".phiops simultaneously" ); |
1481 | return InputMA; |
1482 | } |
1483 | |
1484 | if (auto *InputMA = lookupValueReadOf(Inst: Val)) |
1485 | return InputMA; |
1486 | |
1487 | return nullptr; |
1488 | } |
1489 | |
1490 | /// Add @p Access to this statement's list of accesses. |
1491 | /// |
1492 | /// @param Access The access to add. |
1493 | /// @param Prepend If true, will add @p Access before all other instructions |
1494 | /// (instead of appending it). |
1495 | void addAccess(MemoryAccess *Access, bool Preprend = false); |
1496 | |
1497 | /// Remove a MemoryAccess from this statement. |
1498 | /// |
1499 | /// Note that scalar accesses that are caused by MA will |
1500 | /// be eliminated too. |
1501 | void removeMemoryAccess(MemoryAccess *MA); |
1502 | |
1503 | /// Remove @p MA from this statement. |
1504 | /// |
1505 | /// In contrast to removeMemoryAccess(), no other access will be eliminated. |
1506 | /// |
1507 | /// @param MA The MemoryAccess to be removed. |
1508 | /// @param AfterHoisting If true, also remove from data access lists. |
1509 | /// These lists are filled during |
1510 | /// ScopBuilder::buildAccessRelations. Therefore, if this |
1511 | /// method is called before buildAccessRelations, false |
1512 | /// must be passed. |
1513 | void removeSingleMemoryAccess(MemoryAccess *MA, bool AfterHoisting = true); |
1514 | |
1515 | using iterator = MemoryAccessVec::iterator; |
1516 | using const_iterator = MemoryAccessVec::const_iterator; |
1517 | |
1518 | iterator begin() { return MemAccs.begin(); } |
1519 | iterator end() { return MemAccs.end(); } |
1520 | const_iterator begin() const { return MemAccs.begin(); } |
1521 | const_iterator end() const { return MemAccs.end(); } |
1522 | size_t size() const { return MemAccs.size(); } |
1523 | |
1524 | unsigned getNumIterators() const; |
1525 | |
1526 | Scop *getParent() { return &Parent; } |
1527 | const Scop *getParent() const { return &Parent; } |
1528 | |
1529 | const std::vector<Instruction *> &getInstructions() const { |
1530 | return Instructions; |
1531 | } |
1532 | |
1533 | /// Set the list of instructions for this statement. It replaces the current |
1534 | /// list. |
1535 | void setInstructions(ArrayRef<Instruction *> Range) { |
1536 | Instructions.assign(first: Range.begin(), last: Range.end()); |
1537 | } |
1538 | |
1539 | std::vector<Instruction *>::const_iterator insts_begin() const { |
1540 | return Instructions.begin(); |
1541 | } |
1542 | |
1543 | std::vector<Instruction *>::const_iterator insts_end() const { |
1544 | return Instructions.end(); |
1545 | } |
1546 | |
1547 | /// The range of instructions in this statement. |
1548 | iterator_range<std::vector<Instruction *>::const_iterator> insts() const { |
1549 | return {insts_begin(), insts_end()}; |
1550 | } |
1551 | |
1552 | /// Insert an instruction before all other instructions in this statement. |
1553 | void prependInstruction(Instruction *Inst) { |
1554 | Instructions.insert(position: Instructions.begin(), x: Inst); |
1555 | } |
1556 | |
1557 | const char *getBaseName() const; |
1558 | |
1559 | /// Set the isl AST build. |
1560 | void setAstBuild(isl::ast_build B) { Build = B; } |
1561 | |
1562 | /// Get the isl AST build. |
1563 | isl::ast_build getAstBuild() const { return Build; } |
1564 | |
1565 | /// Restrict the domain of the statement. |
1566 | /// |
1567 | /// @param NewDomain The new statement domain. |
1568 | void restrictDomain(isl::set NewDomain); |
1569 | |
1570 | /// Get the loop for a dimension. |
1571 | /// |
1572 | /// @param Dimension The dimension of the induction variable |
1573 | /// @return The loop at a certain dimension. |
1574 | Loop *getLoopForDimension(unsigned Dimension) const; |
1575 | |
1576 | /// Align the parameters in the statement to the scop context |
1577 | void realignParams(); |
1578 | |
1579 | /// Print the ScopStmt. |
1580 | /// |
1581 | /// @param OS The output stream the ScopStmt is printed to. |
1582 | /// @param PrintInstructions Whether to print the statement's instructions as |
1583 | /// well. |
1584 | void print(raw_ostream &OS, bool PrintInstructions) const; |
1585 | |
1586 | /// Print the instructions in ScopStmt. |
1587 | /// |
1588 | void printInstructions(raw_ostream &OS) const; |
1589 | |
1590 | /// Check whether there is a value read access for @p V in this statement, and |
1591 | /// if not, create one. |
1592 | /// |
1593 | /// This allows to add MemoryAccesses after the initial creation of the Scop |
1594 | /// by ScopBuilder. |
1595 | /// |
1596 | /// @return The already existing or newly created MemoryKind::Value READ |
1597 | /// MemoryAccess. |
1598 | /// |
1599 | /// @see ScopBuilder::ensureValueRead(Value*,ScopStmt*) |
1600 | MemoryAccess *ensureValueRead(Value *V); |
1601 | |
1602 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
1603 | /// Print the ScopStmt to stderr. |
1604 | void dump() const; |
1605 | #endif |
1606 | }; |
1607 | |
1608 | /// Print ScopStmt S to raw_ostream OS. |
1609 | raw_ostream &operator<<(raw_ostream &OS, const ScopStmt &S); |
1610 | |
1611 | /// Static Control Part |
1612 | /// |
1613 | /// A Scop is the polyhedral representation of a control flow region detected |
1614 | /// by the Scop detection. It is generated by translating the LLVM-IR and |
1615 | /// abstracting its effects. |
1616 | /// |
1617 | /// A Scop consists of a set of: |
1618 | /// |
1619 | /// * A set of statements executed in the Scop. |
1620 | /// |
1621 | /// * A set of global parameters |
1622 | /// Those parameters are scalar integer values, which are constant during |
1623 | /// execution. |
1624 | /// |
1625 | /// * A context |
1626 | /// This context contains information about the values the parameters |
1627 | /// can take and relations between different parameters. |
1628 | class Scop final { |
1629 | public: |
1630 | /// Type to represent a pair of minimal/maximal access to an array. |
1631 | using MinMaxAccessTy = std::pair<isl::pw_multi_aff, isl::pw_multi_aff>; |
1632 | |
1633 | /// Vector of minimal/maximal accesses to different arrays. |
1634 | using MinMaxVectorTy = SmallVector<MinMaxAccessTy, 4>; |
1635 | |
1636 | /// Pair of minimal/maximal access vectors representing |
1637 | /// read write and read only accesses |
1638 | using MinMaxVectorPairTy = std::pair<MinMaxVectorTy, MinMaxVectorTy>; |
1639 | |
1640 | /// Vector of pair of minimal/maximal access vectors representing |
1641 | /// non read only and read only accesses for each alias group. |
1642 | using MinMaxVectorPairVectorTy = SmallVector<MinMaxVectorPairTy, 4>; |
1643 | |
1644 | private: |
1645 | friend class ScopBuilder; |
1646 | |
1647 | /// Isl context. |
1648 | /// |
1649 | /// We need a shared_ptr with reference counter to delete the context when all |
1650 | /// isl objects are deleted. We will distribute the shared_ptr to all objects |
1651 | /// that use the context to create isl objects, and increase the reference |
1652 | /// counter. By doing this, we guarantee that the context is deleted when we |
1653 | /// delete the last object that creates isl objects with the context. This |
1654 | /// declaration needs to be the first in class to gracefully destroy all isl |
1655 | /// objects before the context. |
1656 | std::shared_ptr<isl_ctx> IslCtx; |
1657 | |
1658 | ScalarEvolution *SE; |
1659 | DominatorTree *DT; |
1660 | |
1661 | /// The underlying Region. |
1662 | Region &R; |
1663 | |
1664 | /// The name of the SCoP (identical to the regions name) |
1665 | std::optional<std::string> name; |
1666 | |
1667 | // Access functions of the SCoP. |
1668 | // |
1669 | // This owns all the MemoryAccess objects of the Scop created in this pass. |
1670 | AccFuncVector AccessFunctions; |
1671 | |
1672 | /// Flag to indicate that the scheduler actually optimized the SCoP. |
1673 | bool IsOptimized = false; |
1674 | |
1675 | /// True if the underlying region has a single exiting block. |
1676 | bool HasSingleExitEdge; |
1677 | |
1678 | /// Flag to remember if the SCoP contained an error block or not. |
1679 | bool HasErrorBlock = false; |
1680 | |
1681 | /// Max loop depth. |
1682 | unsigned MaxLoopDepth = 0; |
1683 | |
1684 | /// Number of copy statements. |
1685 | unsigned CopyStmtsNum = 0; |
1686 | |
1687 | using StmtSet = std::list<ScopStmt>; |
1688 | |
1689 | /// The statements in this Scop. |
1690 | StmtSet Stmts; |
1691 | |
1692 | /// Parameters of this Scop |
1693 | ParameterSetTy Parameters; |
1694 | |
1695 | /// Mapping from parameters to their ids. |
1696 | DenseMap<const SCEV *, isl::id> ParameterIds; |
1697 | |
1698 | /// The context of the SCoP created during SCoP detection. |
1699 | ScopDetection::DetectionContext &DC; |
1700 | |
1701 | /// OptimizationRemarkEmitter object for displaying diagnostic remarks |
1702 | OptimizationRemarkEmitter &ORE; |
1703 | |
1704 | /// A map from basic blocks to vector of SCoP statements. Currently this |
1705 | /// vector comprises only of a single statement. |
1706 | DenseMap<BasicBlock *, std::vector<ScopStmt *>> StmtMap; |
1707 | |
1708 | /// A map from instructions to SCoP statements. |
1709 | DenseMap<Instruction *, ScopStmt *> InstStmtMap; |
1710 | |
1711 | /// A map from basic blocks to their domains. |
1712 | DenseMap<BasicBlock *, isl::set> DomainMap; |
1713 | |
1714 | /// Constraints on parameters. |
1715 | isl::set Context; |
1716 | |
1717 | /// The affinator used to translate SCEVs to isl expressions. |
1718 | SCEVAffinator Affinator; |
1719 | |
1720 | using ArrayInfoMapTy = |
1721 | std::map<std::pair<AssertingVH<const Value>, MemoryKind>, |
1722 | std::unique_ptr<ScopArrayInfo>>; |
1723 | |
1724 | using ArrayNameMapTy = StringMap<std::unique_ptr<ScopArrayInfo>>; |
1725 | |
1726 | using ArrayInfoSetTy = SetVector<ScopArrayInfo *>; |
1727 | |
1728 | /// A map to remember ScopArrayInfo objects for all base pointers. |
1729 | /// |
1730 | /// As PHI nodes may have two array info objects associated, we add a flag |
1731 | /// that distinguishes between the PHI node specific ArrayInfo object |
1732 | /// and the normal one. |
1733 | ArrayInfoMapTy ScopArrayInfoMap; |
1734 | |
1735 | /// A map to remember ScopArrayInfo objects for all names of memory |
1736 | /// references. |
1737 | ArrayNameMapTy ScopArrayNameMap; |
1738 | |
1739 | /// A set to remember ScopArrayInfo objects. |
1740 | /// @see Scop::ScopArrayInfoMap |
1741 | ArrayInfoSetTy ScopArrayInfoSet; |
1742 | |
1743 | /// The assumptions under which this scop was built. |
1744 | /// |
1745 | /// When constructing a scop sometimes the exact representation of a statement |
1746 | /// or condition would be very complex, but there is a common case which is a |
1747 | /// lot simpler, but which is only valid under certain assumptions. The |
1748 | /// assumed context records the assumptions taken during the construction of |
1749 | /// this scop and that need to be code generated as a run-time test. |
1750 | isl::set AssumedContext; |
1751 | |
1752 | /// The restrictions under which this SCoP was built. |
1753 | /// |
1754 | /// The invalid context is similar to the assumed context as it contains |
1755 | /// constraints over the parameters. However, while we need the constraints |
1756 | /// in the assumed context to be "true" the constraints in the invalid context |
1757 | /// need to be "false". Otherwise they behave the same. |
1758 | isl::set InvalidContext; |
1759 | |
1760 | /// The context under which the SCoP must have defined behavior. Optimizer and |
1761 | /// code generator can assume that the SCoP will only be executed with |
1762 | /// parameter values within this context. This might be either because we can |
1763 | /// prove that other values are impossible or explicitly have undefined |
1764 | /// behavior, such as due to no-wrap flags. If this becomes too complex, can |
1765 | /// also be nullptr. |
1766 | /// |
1767 | /// In contrast to Scop::AssumedContext and Scop::InvalidContext, these do not |
1768 | /// need to be checked at runtime. |
1769 | /// |
1770 | /// Scop::Context on the other side is an overapproximation and does not |
1771 | /// include all requirements, but is always defined. However, there is still |
1772 | /// no guarantee that there is no undefined behavior in |
1773 | /// DefinedBehaviorContext. |
1774 | isl::set DefinedBehaviorContext; |
1775 | |
1776 | /// The schedule of the SCoP |
1777 | /// |
1778 | /// The schedule of the SCoP describes the execution order of the statements |
1779 | /// in the scop by assigning each statement instance a possibly |
1780 | /// multi-dimensional execution time. The schedule is stored as a tree of |
1781 | /// schedule nodes. |
1782 | /// |
1783 | /// The most common nodes in a schedule tree are so-called band nodes. Band |
1784 | /// nodes map statement instances into a multi dimensional schedule space. |
1785 | /// This space can be seen as a multi-dimensional clock. |
1786 | /// |
1787 | /// Example: |
1788 | /// |
1789 | /// <S,(5,4)> may be mapped to (5,4) by this schedule: |
1790 | /// |
1791 | /// s0 = i (Year of execution) |
1792 | /// s1 = j (Day of execution) |
1793 | /// |
1794 | /// or to (9, 20) by this schedule: |
1795 | /// |
1796 | /// s0 = i + j (Year of execution) |
1797 | /// s1 = 20 (Day of execution) |
1798 | /// |
1799 | /// The order statement instances are executed is defined by the |
1800 | /// schedule vectors they are mapped to. A statement instance |
1801 | /// <A, (i, j, ..)> is executed before a statement instance <B, (i', ..)>, if |
1802 | /// the schedule vector of A is lexicographic smaller than the schedule |
1803 | /// vector of B. |
1804 | /// |
1805 | /// Besides band nodes, schedule trees contain additional nodes that specify |
1806 | /// a textual ordering between two subtrees or filter nodes that filter the |
1807 | /// set of statement instances that will be scheduled in a subtree. There |
1808 | /// are also several other nodes. A full description of the different nodes |
1809 | /// in a schedule tree is given in the isl manual. |
1810 | isl::schedule Schedule; |
1811 | |
1812 | /// Is this Scop marked as not to be transformed by an optimization heuristic? |
1813 | bool HasDisableHeuristicsHint = false; |
1814 | |
1815 | /// Whether the schedule has been modified after derived from the CFG by |
1816 | /// ScopBuilder. |
1817 | bool ScheduleModified = false; |
1818 | |
1819 | /// The set of minimal/maximal accesses for each alias group. |
1820 | /// |
1821 | /// When building runtime alias checks we look at all memory instructions and |
1822 | /// build so called alias groups. Each group contains a set of accesses to |
1823 | /// different base arrays which might alias with each other. However, between |
1824 | /// alias groups there is no aliasing possible. |
1825 | /// |
1826 | /// In a program with int and float pointers annotated with tbaa information |
1827 | /// we would probably generate two alias groups, one for the int pointers and |
1828 | /// one for the float pointers. |
1829 | /// |
1830 | /// During code generation we will create a runtime alias check for each alias |
1831 | /// group to ensure the SCoP is executed in an alias free environment. |
1832 | MinMaxVectorPairVectorTy MinMaxAliasGroups; |
1833 | |
1834 | /// Mapping from invariant loads to the representing invariant load of |
1835 | /// their equivalence class. |
1836 | ValueToValueMap InvEquivClassVMap; |
1837 | |
1838 | /// List of invariant accesses. |
1839 | InvariantEquivClassesTy InvariantEquivClasses; |
1840 | |
1841 | /// The smallest array index not yet assigned. |
1842 | long ArrayIdx = 0; |
1843 | |
1844 | /// The smallest statement index not yet assigned. |
1845 | long StmtIdx = 0; |
1846 | |
1847 | /// A number that uniquely represents a Scop within its function |
1848 | const int ID; |
1849 | |
1850 | /// Map of values to the MemoryAccess that writes its definition. |
1851 | /// |
1852 | /// There must be at most one definition per llvm::Instruction in a SCoP. |
1853 | DenseMap<Value *, MemoryAccess *> ValueDefAccs; |
1854 | |
1855 | /// Map of values to the MemoryAccess that reads a PHI. |
1856 | DenseMap<PHINode *, MemoryAccess *> PHIReadAccs; |
1857 | |
1858 | /// List of all uses (i.e. read MemoryAccesses) for a MemoryKind::Value |
1859 | /// scalar. |
1860 | DenseMap<const ScopArrayInfo *, SmallVector<MemoryAccess *, 4>> ValueUseAccs; |
1861 | |
1862 | /// List of all incoming values (write MemoryAccess) of a MemoryKind::PHI or |
1863 | /// MemoryKind::ExitPHI scalar. |
1864 | DenseMap<const ScopArrayInfo *, SmallVector<MemoryAccess *, 4>> |
1865 | PHIIncomingAccs; |
1866 | |
1867 | /// Scop constructor; invoked from ScopBuilder::buildScop. |
1868 | (Region &R, ScalarEvolution &SE, LoopInfo &LI, DominatorTree &DT, |
1869 | ScopDetection::DetectionContext &DC, OptimizationRemarkEmitter &ORE, |
1870 | int ID); |
1871 | |
1872 | //@} |
1873 | |
1874 | /// Return the access for the base ptr of @p MA if any. |
1875 | MemoryAccess *lookupBasePtrAccess(MemoryAccess *MA); |
1876 | |
1877 | /// Create an id for @p Param and store it in the ParameterIds map. |
1878 | void createParameterId(const SCEV *Param); |
1879 | |
1880 | /// Build the Context of the Scop. |
1881 | void buildContext(); |
1882 | |
1883 | /// Add the bounds of the parameters to the context. |
1884 | void addParameterBounds(); |
1885 | |
1886 | /// Simplify the assumed and invalid context. |
1887 | void simplifyContexts(); |
1888 | |
1889 | /// Create a new SCoP statement for @p BB. |
1890 | /// |
1891 | /// A new statement for @p BB will be created and added to the statement |
1892 | /// vector |
1893 | /// and map. |
1894 | /// |
1895 | /// @param BB The basic block we build the statement for. |
1896 | /// @param Name The name of the new statement. |
1897 | /// @param SurroundingLoop The loop the created statement is contained in. |
1898 | /// @param Instructions The instructions in the statement. |
1899 | void addScopStmt(BasicBlock *BB, StringRef Name, Loop *SurroundingLoop, |
1900 | std::vector<Instruction *> Instructions); |
1901 | |
1902 | /// Create a new SCoP statement for @p R. |
1903 | /// |
1904 | /// A new statement for @p R will be created and added to the statement vector |
1905 | /// and map. |
1906 | /// |
1907 | /// @param R The region we build the statement for. |
1908 | /// @param Name The name of the new statement. |
1909 | /// @param SurroundingLoop The loop the created statement is contained |
1910 | /// in. |
1911 | /// @param EntryBlockInstructions The (interesting) instructions in the |
1912 | /// entry block of the region statement. |
1913 | void addScopStmt(Region *R, StringRef Name, Loop *SurroundingLoop, |
1914 | std::vector<Instruction *> EntryBlockInstructions); |
1915 | |
1916 | /// Removes @p Stmt from the StmtMap. |
1917 | void removeFromStmtMap(ScopStmt &Stmt); |
1918 | |
1919 | /// Removes all statements where the entry block of the statement does not |
1920 | /// have a corresponding domain in the domain map (or it is empty). |
1921 | void removeStmtNotInDomainMap(); |
1922 | |
1923 | /// Collect all memory access relations of a given type. |
1924 | /// |
1925 | /// @param Predicate A predicate function that returns true if an access is |
1926 | /// of a given type. |
1927 | /// |
1928 | /// @returns The set of memory accesses in the scop that match the predicate. |
1929 | isl::union_map |
1930 | getAccessesOfType(std::function<bool(MemoryAccess &)> Predicate); |
1931 | |
1932 | /// @name Helper functions for printing the Scop. |
1933 | /// |
1934 | //@{ |
1935 | void printContext(raw_ostream &OS) const; |
1936 | void printArrayInfo(raw_ostream &OS) const; |
1937 | void printStatements(raw_ostream &OS, bool PrintInstructions) const; |
1938 | void printAliasAssumptions(raw_ostream &OS) const; |
1939 | //@} |
1940 | |
1941 | public: |
1942 | Scop(const Scop &) = delete; |
1943 | Scop &operator=(const Scop &) = delete; |
1944 | ~Scop(); |
1945 | |
1946 | /// Increment actual number of aliasing assumptions taken |
1947 | /// |
1948 | /// @param Step Number of new aliasing assumptions which should be added to |
1949 | /// the number of already taken assumptions. |
1950 | static void incrementNumberOfAliasingAssumptions(unsigned Step); |
1951 | |
1952 | /// Get the count of copy statements added to this Scop. |
1953 | /// |
1954 | /// @return The count of copy statements added to this Scop. |
1955 | unsigned getCopyStmtsNum() { return CopyStmtsNum; } |
1956 | |
1957 | /// Create a new copy statement. |
1958 | /// |
1959 | /// A new statement will be created and added to the statement vector. |
1960 | /// |
1961 | /// @param SourceRel The source location. |
1962 | /// @param TargetRel The target location. |
1963 | /// @param Domain The original domain under which the copy statement would |
1964 | /// be executed. |
1965 | ScopStmt *addScopStmt(isl::map SourceRel, isl::map TargetRel, |
1966 | isl::set Domain); |
1967 | |
1968 | /// Add the access function to all MemoryAccess objects of the Scop |
1969 | /// created in this pass. |
1970 | void addAccessFunction(MemoryAccess *Access) { |
1971 | AccessFunctions.emplace_back(args&: Access); |
1972 | |
1973 | // Register value definitions. |
1974 | if (Access->isWrite() && Access->isOriginalValueKind()) { |
1975 | assert(!ValueDefAccs.count(Access->getAccessValue()) && |
1976 | "there can be just one definition per value" ); |
1977 | ValueDefAccs[Access->getAccessValue()] = Access; |
1978 | } else if (Access->isRead() && Access->isOriginalPHIKind()) { |
1979 | PHINode *PHI = cast<PHINode>(Val: Access->getAccessInstruction()); |
1980 | assert(!PHIReadAccs.count(PHI) && |
1981 | "there can be just one PHI read per PHINode" ); |
1982 | PHIReadAccs[PHI] = Access; |
1983 | } |
1984 | } |
1985 | |
1986 | /// Add metadata for @p Access. |
1987 | void addAccessData(MemoryAccess *Access); |
1988 | |
1989 | /// Add new invariant access equivalence class |
1990 | void |
1991 | addInvariantEquivClass(const InvariantEquivClassTy &InvariantEquivClass) { |
1992 | InvariantEquivClasses.emplace_back(Args: InvariantEquivClass); |
1993 | } |
1994 | |
1995 | /// Add mapping from invariant loads to the representing invariant load of |
1996 | /// their equivalence class. |
1997 | void addInvariantLoadMapping(const Value *LoadInst, Value *ClassRep) { |
1998 | InvEquivClassVMap[LoadInst] = ClassRep; |
1999 | } |
2000 | |
2001 | /// Remove the metadata stored for @p Access. |
2002 | void removeAccessData(MemoryAccess *Access); |
2003 | |
2004 | /// Return the scalar evolution. |
2005 | ScalarEvolution *getSE() const; |
2006 | |
2007 | /// Return the dominator tree. |
2008 | DominatorTree *getDT() const { return DT; } |
2009 | |
2010 | /// Return the LoopInfo used for this Scop. |
2011 | LoopInfo *getLI() const { return Affinator.getLI(); } |
2012 | |
2013 | /// Get the count of parameters used in this Scop. |
2014 | /// |
2015 | /// @return The count of parameters used in this Scop. |
2016 | size_t getNumParams() const { return Parameters.size(); } |
2017 | |
2018 | /// Return whether given SCEV is used as the parameter in this Scop. |
2019 | bool isParam(const SCEV *Param) const { return Parameters.count(key: Param); } |
2020 | |
2021 | /// Take a list of parameters and add the new ones to the scop. |
2022 | void addParams(const ParameterSetTy &NewParameters); |
2023 | |
2024 | /// Return an iterator range containing the scop parameters. |
2025 | iterator_range<ParameterSetTy::iterator> parameters() const { |
2026 | return make_range(x: Parameters.begin(), y: Parameters.end()); |
2027 | } |
2028 | |
2029 | /// Return an iterator range containing invariant accesses. |
2030 | iterator_range<InvariantEquivClassesTy::iterator> invariantEquivClasses() { |
2031 | return make_range(x: InvariantEquivClasses.begin(), |
2032 | y: InvariantEquivClasses.end()); |
2033 | } |
2034 | |
2035 | /// Return an iterator range containing all the MemoryAccess objects of the |
2036 | /// Scop. |
2037 | iterator_range<AccFuncVector::iterator> access_functions() { |
2038 | return make_range(x: AccessFunctions.begin(), y: AccessFunctions.end()); |
2039 | } |
2040 | |
2041 | /// Return whether this scop is empty, i.e. contains no statements that |
2042 | /// could be executed. |
2043 | bool isEmpty() const { return Stmts.empty(); } |
2044 | |
2045 | StringRef getName() { |
2046 | if (!name) |
2047 | name = R.getNameStr(); |
2048 | return *name; |
2049 | } |
2050 | |
2051 | using array_iterator = ArrayInfoSetTy::iterator; |
2052 | using const_array_iterator = ArrayInfoSetTy::const_iterator; |
2053 | using array_range = iterator_range<ArrayInfoSetTy::iterator>; |
2054 | using const_array_range = iterator_range<ArrayInfoSetTy::const_iterator>; |
2055 | |
2056 | inline array_iterator array_begin() { return ScopArrayInfoSet.begin(); } |
2057 | |
2058 | inline array_iterator array_end() { return ScopArrayInfoSet.end(); } |
2059 | |
2060 | inline const_array_iterator array_begin() const { |
2061 | return ScopArrayInfoSet.begin(); |
2062 | } |
2063 | |
2064 | inline const_array_iterator array_end() const { |
2065 | return ScopArrayInfoSet.end(); |
2066 | } |
2067 | |
2068 | inline array_range arrays() { |
2069 | return array_range(array_begin(), array_end()); |
2070 | } |
2071 | |
2072 | inline const_array_range arrays() const { |
2073 | return const_array_range(array_begin(), array_end()); |
2074 | } |
2075 | |
2076 | /// Return the isl_id that represents a certain parameter. |
2077 | /// |
2078 | /// @param Parameter A SCEV that was recognized as a Parameter. |
2079 | /// |
2080 | /// @return The corresponding isl_id or NULL otherwise. |
2081 | isl::id getIdForParam(const SCEV *Parameter) const; |
2082 | |
2083 | /// Get the maximum region of this static control part. |
2084 | /// |
2085 | /// @return The maximum region of this static control part. |
2086 | inline const Region &getRegion() const { return R; } |
2087 | inline Region &getRegion() { return R; } |
2088 | |
2089 | /// Return the function this SCoP is in. |
2090 | Function &getFunction() const { return *R.getEntry()->getParent(); } |
2091 | |
2092 | /// Check if @p L is contained in the SCoP. |
2093 | bool contains(const Loop *L) const { return R.contains(L); } |
2094 | |
2095 | /// Check if @p BB is contained in the SCoP. |
2096 | bool contains(const BasicBlock *BB) const { return R.contains(BB); } |
2097 | |
2098 | /// Check if @p I is contained in the SCoP. |
2099 | bool contains(const Instruction *I) const { return R.contains(Inst: I); } |
2100 | |
2101 | /// Return the unique exit block of the SCoP. |
2102 | BasicBlock *getExit() const { return R.getExit(); } |
2103 | |
2104 | /// Return the unique exiting block of the SCoP if any. |
2105 | BasicBlock *getExitingBlock() const { return R.getExitingBlock(); } |
2106 | |
2107 | /// Return the unique entry block of the SCoP. |
2108 | BasicBlock *getEntry() const { return R.getEntry(); } |
2109 | |
2110 | /// Return the unique entering block of the SCoP if any. |
2111 | BasicBlock *getEnteringBlock() const { return R.getEnteringBlock(); } |
2112 | |
2113 | /// Return true if @p BB is the exit block of the SCoP. |
2114 | bool isExit(BasicBlock *BB) const { return getExit() == BB; } |
2115 | |
2116 | /// Return a range of all basic blocks in the SCoP. |
2117 | Region::block_range blocks() const { return R.blocks(); } |
2118 | |
2119 | /// Return true if and only if @p BB dominates the SCoP. |
2120 | bool isDominatedBy(const DominatorTree &DT, BasicBlock *BB) const; |
2121 | |
2122 | /// Get the maximum depth of the loop. |
2123 | /// |
2124 | /// @return The maximum depth of the loop. |
2125 | inline unsigned getMaxLoopDepth() const { return MaxLoopDepth; } |
2126 | |
2127 | /// Return the invariant equivalence class for @p Val if any. |
2128 | InvariantEquivClassTy *lookupInvariantEquivClass(Value *Val); |
2129 | |
2130 | /// Return the set of invariant accesses. |
2131 | InvariantEquivClassesTy &getInvariantAccesses() { |
2132 | return InvariantEquivClasses; |
2133 | } |
2134 | |
2135 | /// Check if the scop has any invariant access. |
2136 | bool hasInvariantAccesses() { return !InvariantEquivClasses.empty(); } |
2137 | |
2138 | /// Mark the SCoP as optimized by the scheduler. |
2139 | void markAsOptimized() { IsOptimized = true; } |
2140 | |
2141 | /// Check if the SCoP has been optimized by the scheduler. |
2142 | bool isOptimized() const { return IsOptimized; } |
2143 | |
2144 | /// Return the ID of the Scop |
2145 | int getID() const { return ID; } |
2146 | |
2147 | /// Get the name of the entry and exit blocks of this Scop. |
2148 | /// |
2149 | /// These along with the function name can uniquely identify a Scop. |
2150 | /// |
2151 | /// @return std::pair whose first element is the entry name & second element |
2152 | /// is the exit name. |
2153 | std::pair<std::string, std::string> getEntryExitStr() const; |
2154 | |
2155 | /// Get the name of this Scop. |
2156 | std::string getNameStr() const; |
2157 | |
2158 | /// Get the constraint on parameter of this Scop. |
2159 | /// |
2160 | /// @return The constraint on parameter of this Scop. |
2161 | isl::set getContext() const; |
2162 | |
2163 | /// Return the context where execution behavior is defined. Might return |
2164 | /// nullptr. |
2165 | isl::set getDefinedBehaviorContext() const { return DefinedBehaviorContext; } |
2166 | |
2167 | /// Return the define behavior context, or if not available, its approximation |
2168 | /// from all other contexts. |
2169 | isl::set getBestKnownDefinedBehaviorContext() const { |
2170 | if (!DefinedBehaviorContext.is_null()) |
2171 | return DefinedBehaviorContext; |
2172 | |
2173 | return Context.intersect_params(params: AssumedContext).subtract(set2: InvalidContext); |
2174 | } |
2175 | |
2176 | /// Return space of isl context parameters. |
2177 | /// |
2178 | /// Returns the set of context parameters that are currently constrained. In |
2179 | /// case the full set of parameters is needed, see @getFullParamSpace. |
2180 | isl::space getParamSpace() const; |
2181 | |
2182 | /// Return the full space of parameters. |
2183 | /// |
2184 | /// getParamSpace will only return the parameters of the context that are |
2185 | /// actually constrained, whereas getFullParamSpace will return all |
2186 | // parameters. This is useful in cases, where we need to ensure all |
2187 | // parameters are available, as certain isl functions will abort if this is |
2188 | // not the case. |
2189 | isl::space getFullParamSpace() const; |
2190 | |
2191 | /// Get the assumed context for this Scop. |
2192 | /// |
2193 | /// @return The assumed context of this Scop. |
2194 | isl::set getAssumedContext() const; |
2195 | |
2196 | /// Return true if the optimized SCoP can be executed. |
2197 | /// |
2198 | /// In addition to the runtime check context this will also utilize the domain |
2199 | /// constraints to decide it the optimized version can actually be executed. |
2200 | /// |
2201 | /// @returns True if the optimized SCoP can be executed. |
2202 | bool hasFeasibleRuntimeContext() const; |
2203 | |
2204 | /// Check if the assumption in @p Set is trivial or not. |
2205 | /// |
2206 | /// @param Set The relations between parameters that are assumed to hold. |
2207 | /// @param Sign Enum to indicate if the assumptions in @p Set are positive |
2208 | /// (needed/assumptions) or negative (invalid/restrictions). |
2209 | /// |
2210 | /// @returns True if the assumption @p Set is not trivial. |
2211 | bool isEffectiveAssumption(isl::set Set, AssumptionSign Sign); |
2212 | |
2213 | /// Track and report an assumption. |
2214 | /// |
2215 | /// Use 'clang -Rpass-analysis=polly-scops' or 'opt |
2216 | /// -pass-remarks-analysis=polly-scops' to output the assumptions. |
2217 | /// |
2218 | /// @param Kind The assumption kind describing the underlying cause. |
2219 | /// @param Set The relations between parameters that are assumed to hold. |
2220 | /// @param Loc The location in the source that caused this assumption. |
2221 | /// @param Sign Enum to indicate if the assumptions in @p Set are positive |
2222 | /// (needed/assumptions) or negative (invalid/restrictions). |
2223 | /// @param BB The block in which this assumption was taken. Used to |
2224 | /// calculate hotness when emitting remark. |
2225 | /// |
2226 | /// @returns True if the assumption is not trivial. |
2227 | bool trackAssumption(AssumptionKind Kind, isl::set Set, DebugLoc Loc, |
2228 | AssumptionSign Sign, BasicBlock *BB); |
2229 | |
2230 | /// Add the conditions from @p Set (or subtract them if @p Sign is |
2231 | /// AS_RESTRICTION) to the defined behaviour context. |
2232 | void intersectDefinedBehavior(isl::set Set, AssumptionSign Sign); |
2233 | |
2234 | /// Add assumptions to assumed context. |
2235 | /// |
2236 | /// The assumptions added will be assumed to hold during the execution of the |
2237 | /// scop. However, as they are generally not statically provable, at code |
2238 | /// generation time run-time checks will be generated that ensure the |
2239 | /// assumptions hold. |
2240 | /// |
2241 | /// WARNING: We currently exploit in simplifyAssumedContext the knowledge |
2242 | /// that assumptions do not change the set of statement instances |
2243 | /// executed. |
2244 | /// |
2245 | /// @param Kind The assumption kind describing the underlying cause. |
2246 | /// @param Set The relations between parameters that are assumed to hold. |
2247 | /// @param Loc The location in the source that caused this assumption. |
2248 | /// @param Sign Enum to indicate if the assumptions in @p Set are positive |
2249 | /// (needed/assumptions) or negative (invalid/restrictions). |
2250 | /// @param BB The block in which this assumption was taken. Used to |
2251 | /// calculate hotness when emitting remark. |
2252 | /// @param RTC Does the assumption require a runtime check? |
2253 | void addAssumption(AssumptionKind Kind, isl::set Set, DebugLoc Loc, |
2254 | AssumptionSign Sign, BasicBlock *BB, bool RTC = true); |
2255 | |
2256 | /// Mark the scop as invalid. |
2257 | /// |
2258 | /// This method adds an assumption to the scop that is always invalid. As a |
2259 | /// result, the scop will not be optimized later on. This function is commonly |
2260 | /// called when a condition makes it impossible (or too compile time |
2261 | /// expensive) to process this scop any further. |
2262 | /// |
2263 | /// @param Kind The assumption kind describing the underlying cause. |
2264 | /// @param Loc The location in the source that triggered . |
2265 | /// @param BB The BasicBlock where it was triggered. |
2266 | void invalidate(AssumptionKind Kind, DebugLoc Loc, BasicBlock *BB = nullptr); |
2267 | |
2268 | /// Get the invalid context for this Scop. |
2269 | /// |
2270 | /// @return The invalid context of this Scop. |
2271 | isl::set getInvalidContext() const; |
2272 | |
2273 | /// Return true if and only if the InvalidContext is trivial (=empty). |
2274 | bool hasTrivialInvalidContext() const { return InvalidContext.is_empty(); } |
2275 | |
2276 | /// Return all alias groups for this SCoP. |
2277 | const MinMaxVectorPairVectorTy &getAliasGroups() const { |
2278 | return MinMaxAliasGroups; |
2279 | } |
2280 | |
2281 | void addAliasGroup(MinMaxVectorTy &MinMaxAccessesReadWrite, |
2282 | MinMaxVectorTy &MinMaxAccessesReadOnly) { |
2283 | MinMaxAliasGroups.emplace_back(); |
2284 | MinMaxAliasGroups.back().first = MinMaxAccessesReadWrite; |
2285 | MinMaxAliasGroups.back().second = MinMaxAccessesReadOnly; |
2286 | } |
2287 | |
2288 | /// Remove statements from the list of scop statements. |
2289 | /// |
2290 | /// @param ShouldDelete A function that returns true if the statement passed |
2291 | /// to it should be deleted. |
2292 | /// @param AfterHoisting If true, also remove from data access lists. |
2293 | /// These lists are filled during |
2294 | /// ScopBuilder::buildAccessRelations. Therefore, if this |
2295 | /// method is called before buildAccessRelations, false |
2296 | /// must be passed. |
2297 | void removeStmts(function_ref<bool(ScopStmt &)> ShouldDelete, |
2298 | bool AfterHoisting = true); |
2299 | |
2300 | /// Get an isl string representing the context. |
2301 | std::string getContextStr() const; |
2302 | |
2303 | /// Get an isl string representing the assumed context. |
2304 | std::string getAssumedContextStr() const; |
2305 | |
2306 | /// Get an isl string representing the invalid context. |
2307 | std::string getInvalidContextStr() const; |
2308 | |
2309 | /// Return the list of ScopStmts that represent the given @p BB. |
2310 | ArrayRef<ScopStmt *> getStmtListFor(BasicBlock *BB) const; |
2311 | |
2312 | /// Get the statement to put a PHI WRITE into. |
2313 | /// |
2314 | /// @param U The operand of a PHINode. |
2315 | ScopStmt *getIncomingStmtFor(const Use &U) const; |
2316 | |
2317 | /// Return the last statement representing @p BB. |
2318 | /// |
2319 | /// Of the sequence of statements that represent a @p BB, this is the last one |
2320 | /// to be executed. It is typically used to determine which instruction to add |
2321 | /// a MemoryKind::PHI WRITE to. For this purpose, it is not strictly required |
2322 | /// to be executed last, only that the incoming value is available in it. |
2323 | ScopStmt *getLastStmtFor(BasicBlock *BB) const; |
2324 | |
2325 | /// Return the ScopStmts that represents the Region @p R, or nullptr if |
2326 | /// it is not represented by any statement in this Scop. |
2327 | ArrayRef<ScopStmt *> getStmtListFor(Region *R) const; |
2328 | |
2329 | /// Return the ScopStmts that represents @p RN; can return nullptr if |
2330 | /// the RegionNode is not within the SCoP or has been removed due to |
2331 | /// simplifications. |
2332 | ArrayRef<ScopStmt *> getStmtListFor(RegionNode *RN) const; |
2333 | |
2334 | /// Return the ScopStmt an instruction belongs to, or nullptr if it |
2335 | /// does not belong to any statement in this Scop. |
2336 | ScopStmt *getStmtFor(Instruction *Inst) const { |
2337 | return InstStmtMap.lookup(Val: Inst); |
2338 | } |
2339 | |
2340 | /// Return the number of statements in the SCoP. |
2341 | size_t getSize() const { return Stmts.size(); } |
2342 | |
2343 | /// @name Statements Iterators |
2344 | /// |
2345 | /// These iterators iterate over all statements of this Scop. |
2346 | //@{ |
2347 | using iterator = StmtSet::iterator; |
2348 | using const_iterator = StmtSet::const_iterator; |
2349 | |
2350 | iterator begin() { return Stmts.begin(); } |
2351 | iterator end() { return Stmts.end(); } |
2352 | const_iterator begin() const { return Stmts.begin(); } |
2353 | const_iterator end() const { return Stmts.end(); } |
2354 | |
2355 | using reverse_iterator = StmtSet::reverse_iterator; |
2356 | using const_reverse_iterator = StmtSet::const_reverse_iterator; |
2357 | |
2358 | reverse_iterator rbegin() { return Stmts.rbegin(); } |
2359 | reverse_iterator rend() { return Stmts.rend(); } |
2360 | const_reverse_iterator rbegin() const { return Stmts.rbegin(); } |
2361 | const_reverse_iterator rend() const { return Stmts.rend(); } |
2362 | //@} |
2363 | |
2364 | /// Return the set of required invariant loads. |
2365 | const InvariantLoadsSetTy &getRequiredInvariantLoads() const { |
2366 | return DC.RequiredILS; |
2367 | } |
2368 | |
2369 | /// Add @p LI to the set of required invariant loads. |
2370 | void addRequiredInvariantLoad(LoadInst *LI) { DC.RequiredILS.insert(X: LI); } |
2371 | |
2372 | /// Return the set of boxed (thus overapproximated) loops. |
2373 | const BoxedLoopsSetTy &getBoxedLoops() const { return DC.BoxedLoopsSet; } |
2374 | |
2375 | /// Return true if and only if @p R is a non-affine subregion. |
2376 | bool isNonAffineSubRegion(const Region *R) { |
2377 | return DC.NonAffineSubRegionSet.count(key: R); |
2378 | } |
2379 | |
2380 | const MapInsnToMemAcc &getInsnToMemAccMap() const { return DC.InsnToMemAcc; } |
2381 | |
2382 | /// Return the (possibly new) ScopArrayInfo object for @p Access. |
2383 | /// |
2384 | /// @param ElementType The type of the elements stored in this array. |
2385 | /// @param Kind The kind of the array info object. |
2386 | /// @param BaseName The optional name of this memory reference. |
2387 | ScopArrayInfo *getOrCreateScopArrayInfo(Value *BasePtr, Type *ElementType, |
2388 | ArrayRef<const SCEV *> Sizes, |
2389 | MemoryKind Kind, |
2390 | const char *BaseName = nullptr); |
2391 | |
2392 | /// Create an array and return the corresponding ScopArrayInfo object. |
2393 | /// |
2394 | /// @param ElementType The type of the elements stored in this array. |
2395 | /// @param BaseName The name of this memory reference. |
2396 | /// @param Sizes The sizes of dimensions. |
2397 | ScopArrayInfo *createScopArrayInfo(Type *ElementType, |
2398 | const std::string &BaseName, |
2399 | const std::vector<unsigned> &Sizes); |
2400 | |
2401 | /// Return the cached ScopArrayInfo object for @p BasePtr. |
2402 | /// |
2403 | /// @param BasePtr The base pointer the object has been stored for. |
2404 | /// @param Kind The kind of array info object. |
2405 | /// |
2406 | /// @returns The ScopArrayInfo pointer or NULL if no such pointer is |
2407 | /// available. |
2408 | ScopArrayInfo *getScopArrayInfoOrNull(Value *BasePtr, MemoryKind Kind); |
2409 | |
2410 | /// Return the cached ScopArrayInfo object for @p BasePtr. |
2411 | /// |
2412 | /// @param BasePtr The base pointer the object has been stored for. |
2413 | /// @param Kind The kind of array info object. |
2414 | /// |
2415 | /// @returns The ScopArrayInfo pointer (may assert if no such pointer is |
2416 | /// available). |
2417 | ScopArrayInfo *getScopArrayInfo(Value *BasePtr, MemoryKind Kind); |
2418 | |
2419 | /// Invalidate ScopArrayInfo object for base address. |
2420 | /// |
2421 | /// @param BasePtr The base pointer of the ScopArrayInfo object to invalidate. |
2422 | /// @param Kind The Kind of the ScopArrayInfo object. |
2423 | void invalidateScopArrayInfo(Value *BasePtr, MemoryKind Kind) { |
2424 | auto It = ScopArrayInfoMap.find(x: std::make_pair(x&: BasePtr, y&: Kind)); |
2425 | if (It == ScopArrayInfoMap.end()) |
2426 | return; |
2427 | ScopArrayInfoSet.remove(X: It->second.get()); |
2428 | ScopArrayInfoMap.erase(position: It); |
2429 | } |
2430 | |
2431 | /// Set new isl context. |
2432 | void setContext(isl::set NewContext); |
2433 | |
2434 | /// Update maximal loop depth. If @p Depth is smaller than current value, |
2435 | /// then maximal loop depth is not updated. |
2436 | void updateMaxLoopDepth(unsigned Depth) { |
2437 | MaxLoopDepth = std::max(a: MaxLoopDepth, b: Depth); |
2438 | } |
2439 | |
2440 | /// Align the parameters in the statement to the scop context |
2441 | void realignParams(); |
2442 | |
2443 | /// Return true if this SCoP can be profitably optimized. |
2444 | /// |
2445 | /// @param ScalarsAreUnprofitable Never consider statements with scalar writes |
2446 | /// as profitably optimizable. |
2447 | /// |
2448 | /// @return Whether this SCoP can be profitably optimized. |
2449 | bool isProfitable(bool ScalarsAreUnprofitable) const; |
2450 | |
2451 | /// Return true if the SCoP contained at least one error block. |
2452 | bool hasErrorBlock() const { return HasErrorBlock; } |
2453 | |
2454 | /// Notify SCoP that it contains an error block |
2455 | void notifyErrorBlock() { HasErrorBlock = true; } |
2456 | |
2457 | /// Return true if the underlying region has a single exiting block. |
2458 | bool hasSingleExitEdge() const { return HasSingleExitEdge; } |
2459 | |
2460 | /// Print the static control part. |
2461 | /// |
2462 | /// @param OS The output stream the static control part is printed to. |
2463 | /// @param PrintInstructions Whether to print the statement's instructions as |
2464 | /// well. |
2465 | void print(raw_ostream &OS, bool PrintInstructions) const; |
2466 | |
2467 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
2468 | /// Print the ScopStmt to stderr. |
2469 | void dump() const; |
2470 | #endif |
2471 | |
2472 | /// Get the isl context of this static control part. |
2473 | /// |
2474 | /// @return The isl context of this static control part. |
2475 | isl::ctx getIslCtx() const; |
2476 | |
2477 | /// Directly return the shared_ptr of the context. |
2478 | const std::shared_ptr<isl_ctx> &getSharedIslCtx() const { return IslCtx; } |
2479 | |
2480 | /// Compute the isl representation for the SCEV @p E |
2481 | /// |
2482 | /// @param E The SCEV that should be translated. |
2483 | /// @param BB An (optional) basic block in which the isl_pw_aff is computed. |
2484 | /// SCEVs known to not reference any loops in the SCoP can be |
2485 | /// passed without a @p BB. |
2486 | /// @param NonNegative Flag to indicate the @p E has to be non-negative. |
2487 | /// |
2488 | /// Note that this function will always return a valid isl_pw_aff. However, if |
2489 | /// the translation of @p E was deemed to complex the SCoP is invalidated and |
2490 | /// a dummy value of appropriate dimension is returned. This allows to bail |
2491 | /// for complex cases without "error handling code" needed on the users side. |
2492 | PWACtx getPwAff(const SCEV *E, BasicBlock *BB = nullptr, |
2493 | bool NonNegative = false, |
2494 | RecordedAssumptionsTy *RecordedAssumptions = nullptr); |
2495 | |
2496 | /// Compute the isl representation for the SCEV @p E |
2497 | /// |
2498 | /// This function is like @see Scop::getPwAff() but strips away the invalid |
2499 | /// domain part associated with the piecewise affine function. |
2500 | isl::pw_aff |
2501 | getPwAffOnly(const SCEV *E, BasicBlock *BB = nullptr, |
2502 | RecordedAssumptionsTy *RecordedAssumptions = nullptr); |
2503 | |
2504 | /// Check if an <nsw> AddRec for the loop L is cached. |
2505 | bool hasNSWAddRecForLoop(Loop *L) { return Affinator.hasNSWAddRecForLoop(L); } |
2506 | |
2507 | /// Return the domain of @p Stmt. |
2508 | /// |
2509 | /// @param Stmt The statement for which the conditions should be returned. |
2510 | isl::set getDomainConditions(const ScopStmt *Stmt) const; |
2511 | |
2512 | /// Return the domain of @p BB. |
2513 | /// |
2514 | /// @param BB The block for which the conditions should be returned. |
2515 | isl::set getDomainConditions(BasicBlock *BB) const; |
2516 | |
2517 | /// Return the domain of @p BB. If it does not exist, create an empty one. |
2518 | isl::set &getOrInitEmptyDomain(BasicBlock *BB) { return DomainMap[BB]; } |
2519 | |
2520 | /// Check if domain is determined for @p BB. |
2521 | bool isDomainDefined(BasicBlock *BB) const { return DomainMap.count(Val: BB) > 0; } |
2522 | |
2523 | /// Set domain for @p BB. |
2524 | void setDomain(BasicBlock *BB, isl::set &Domain) { DomainMap[BB] = Domain; } |
2525 | |
2526 | /// Get a union set containing the iteration domains of all statements. |
2527 | isl::union_set getDomains() const; |
2528 | |
2529 | /// Get a union map of all may-writes performed in the SCoP. |
2530 | isl::union_map getMayWrites(); |
2531 | |
2532 | /// Get a union map of all must-writes performed in the SCoP. |
2533 | isl::union_map getMustWrites(); |
2534 | |
2535 | /// Get a union map of all writes performed in the SCoP. |
2536 | isl::union_map getWrites(); |
2537 | |
2538 | /// Get a union map of all reads performed in the SCoP. |
2539 | isl::union_map getReads(); |
2540 | |
2541 | /// Get a union map of all memory accesses performed in the SCoP. |
2542 | isl::union_map getAccesses(); |
2543 | |
2544 | /// Get a union map of all memory accesses performed in the SCoP. |
2545 | /// |
2546 | /// @param Array The array to which the accesses should belong. |
2547 | isl::union_map getAccesses(ScopArrayInfo *Array); |
2548 | |
2549 | /// Get the schedule of all the statements in the SCoP. |
2550 | /// |
2551 | /// @return The schedule of all the statements in the SCoP, if the schedule of |
2552 | /// the Scop does not contain extension nodes, and nullptr, otherwise. |
2553 | isl::union_map getSchedule() const; |
2554 | |
2555 | /// Get a schedule tree describing the schedule of all statements. |
2556 | isl::schedule getScheduleTree() const; |
2557 | |
2558 | /// Update the current schedule |
2559 | /// |
2560 | /// NewSchedule The new schedule (given as a flat union-map). |
2561 | void setSchedule(isl::union_map NewSchedule); |
2562 | |
2563 | /// Update the current schedule |
2564 | /// |
2565 | /// NewSchedule The new schedule (given as schedule tree). |
2566 | void setScheduleTree(isl::schedule NewSchedule); |
2567 | |
2568 | /// Whether the schedule is the original schedule as derived from the CFG by |
2569 | /// ScopBuilder. |
2570 | bool isOriginalSchedule() const { return !ScheduleModified; } |
2571 | |
2572 | /// Intersects the domains of all statements in the SCoP. |
2573 | /// |
2574 | /// @return true if a change was made |
2575 | bool restrictDomains(isl::union_set Domain); |
2576 | |
2577 | /// Get the depth of a loop relative to the outermost loop in the Scop. |
2578 | /// |
2579 | /// This will return |
2580 | /// 0 if @p L is an outermost loop in the SCoP |
2581 | /// >0 for other loops in the SCoP |
2582 | /// -1 if @p L is nullptr or there is no outermost loop in the SCoP |
2583 | int getRelativeLoopDepth(const Loop *L) const; |
2584 | |
2585 | /// Find the ScopArrayInfo associated with an isl Id |
2586 | /// that has name @p Name. |
2587 | ScopArrayInfo *getArrayInfoByName(const std::string BaseName); |
2588 | |
2589 | /// Simplify the SCoP representation. |
2590 | /// |
2591 | /// @param AfterHoisting Whether it is called after invariant load hoisting. |
2592 | /// When true, also removes statements without |
2593 | /// side-effects. |
2594 | void simplifySCoP(bool AfterHoisting); |
2595 | |
2596 | /// Get the next free array index. |
2597 | /// |
2598 | /// This function returns a unique index which can be used to identify an |
2599 | /// array. |
2600 | long getNextArrayIdx() { return ArrayIdx++; } |
2601 | |
2602 | /// Get the next free statement index. |
2603 | /// |
2604 | /// This function returns a unique index which can be used to identify a |
2605 | /// statement. |
2606 | long getNextStmtIdx() { return StmtIdx++; } |
2607 | |
2608 | /// Get the representing SCEV for @p S if applicable, otherwise @p S. |
2609 | /// |
2610 | /// Invariant loads of the same location are put in an equivalence class and |
2611 | /// only one of them is chosen as a representing element that will be |
2612 | /// modeled as a parameter. The others have to be normalized, i.e., |
2613 | /// replaced by the representing element of their equivalence class, in order |
2614 | /// to get the correct parameter value, e.g., in the SCEVAffinator. |
2615 | /// |
2616 | /// @param S The SCEV to normalize. |
2617 | /// |
2618 | /// @return The representing SCEV for invariant loads or @p S if none. |
2619 | const SCEV *getRepresentingInvariantLoadSCEV(const SCEV *S) const; |
2620 | |
2621 | /// Return the MemoryAccess that writes an llvm::Value, represented by a |
2622 | /// ScopArrayInfo. |
2623 | /// |
2624 | /// There can be at most one such MemoryAccess per llvm::Value in the SCoP. |
2625 | /// Zero is possible for read-only values. |
2626 | MemoryAccess *getValueDef(const ScopArrayInfo *SAI) const; |
2627 | |
2628 | /// Return all MemoryAccesses that us an llvm::Value, represented by a |
2629 | /// ScopArrayInfo. |
2630 | ArrayRef<MemoryAccess *> getValueUses(const ScopArrayInfo *SAI) const; |
2631 | |
2632 | /// Return the MemoryAccess that represents an llvm::PHINode. |
2633 | /// |
2634 | /// ExitPHIs's PHINode is not within the SCoPs. This function returns nullptr |
2635 | /// for them. |
2636 | MemoryAccess *getPHIRead(const ScopArrayInfo *SAI) const; |
2637 | |
2638 | /// Return all MemoryAccesses for all incoming statements of a PHINode, |
2639 | /// represented by a ScopArrayInfo. |
2640 | ArrayRef<MemoryAccess *> getPHIIncomings(const ScopArrayInfo *SAI) const; |
2641 | |
2642 | /// Return whether @p Inst has a use outside of this SCoP. |
2643 | bool isEscaping(Instruction *Inst); |
2644 | |
2645 | struct ScopStatistics { |
2646 | int NumAffineLoops = 0; |
2647 | int NumBoxedLoops = 0; |
2648 | |
2649 | int NumValueWrites = 0; |
2650 | int NumValueWritesInLoops = 0; |
2651 | int NumPHIWrites = 0; |
2652 | int NumPHIWritesInLoops = 0; |
2653 | int NumSingletonWrites = 0; |
2654 | int NumSingletonWritesInLoops = 0; |
2655 | }; |
2656 | |
2657 | /// Collect statistic about this SCoP. |
2658 | /// |
2659 | /// These are most commonly used for LLVM's static counters (Statistic.h) in |
2660 | /// various places. If statistics are disabled, only zeros are returned to |
2661 | /// avoid the overhead. |
2662 | ScopStatistics getStatistics() const; |
2663 | |
2664 | /// Is this Scop marked as not to be transformed by an optimization heuristic? |
2665 | /// In this case, only user-directed transformations are allowed. |
2666 | bool hasDisableHeuristicsHint() const { return HasDisableHeuristicsHint; } |
2667 | |
2668 | /// Mark this Scop to not apply an optimization heuristic. |
2669 | void markDisableHeuristics() { HasDisableHeuristicsHint = true; } |
2670 | }; |
2671 | |
2672 | /// Print Scop scop to raw_ostream OS. |
2673 | raw_ostream &operator<<(raw_ostream &OS, const Scop &scop); |
2674 | |
2675 | /// The legacy pass manager's analysis pass to compute scop information |
2676 | /// for a region. |
2677 | class ScopInfoRegionPass final : public RegionPass { |
2678 | /// The Scop pointer which is used to construct a Scop. |
2679 | std::unique_ptr<Scop> S; |
2680 | |
2681 | public: |
2682 | static char ID; // Pass identification, replacement for typeid |
2683 | |
2684 | ScopInfoRegionPass() : RegionPass(ID) {} |
2685 | ~ScopInfoRegionPass() override = default; |
2686 | |
2687 | /// Build Scop object, the Polly IR of static control |
2688 | /// part for the current SESE-Region. |
2689 | /// |
2690 | /// @return If the current region is a valid for a static control part, |
2691 | /// return the Polly IR representing this static control part, |
2692 | /// return null otherwise. |
2693 | Scop *getScop() { return S.get(); } |
2694 | const Scop *getScop() const { return S.get(); } |
2695 | |
2696 | /// Calculate the polyhedral scop information for a given Region. |
2697 | bool runOnRegion(Region *R, RGPassManager &RGM) override; |
2698 | |
2699 | void releaseMemory() override { S.reset(); } |
2700 | |
2701 | void print(raw_ostream &O, const Module *M = nullptr) const override; |
2702 | |
2703 | void getAnalysisUsage(AnalysisUsage &AU) const override; |
2704 | }; |
2705 | |
2706 | llvm::Pass *createScopInfoPrinterLegacyRegionPass(raw_ostream &OS); |
2707 | |
2708 | class ScopInfo { |
2709 | public: |
2710 | using RegionToScopMapTy = MapVector<Region *, std::unique_ptr<Scop>>; |
2711 | using reverse_iterator = RegionToScopMapTy::reverse_iterator; |
2712 | using const_reverse_iterator = RegionToScopMapTy::const_reverse_iterator; |
2713 | using iterator = RegionToScopMapTy::iterator; |
2714 | using const_iterator = RegionToScopMapTy::const_iterator; |
2715 | |
2716 | private: |
2717 | /// A map of Region to its Scop object containing |
2718 | /// Polly IR of static control part. |
2719 | RegionToScopMapTy RegionToScopMap; |
2720 | const DataLayout &DL; |
2721 | ScopDetection &SD; |
2722 | ScalarEvolution &SE; |
2723 | LoopInfo &LI; |
2724 | AAResults &AA; |
2725 | DominatorTree &DT; |
2726 | AssumptionCache &AC; |
2727 | OptimizationRemarkEmitter &ORE; |
2728 | |
2729 | public: |
2730 | ScopInfo(const DataLayout &DL, ScopDetection &SD, ScalarEvolution &SE, |
2731 | LoopInfo &LI, AAResults &AA, DominatorTree &DT, AssumptionCache &AC, |
2732 | OptimizationRemarkEmitter &ORE); |
2733 | |
2734 | /// Get the Scop object for the given Region. |
2735 | /// |
2736 | /// @return If the given region is the maximal region within a scop, return |
2737 | /// the scop object. If the given region is a subregion, return a |
2738 | /// nullptr. Top level region containing the entry block of a function |
2739 | /// is not considered in the scop creation. |
2740 | Scop *getScop(Region *R) const { |
2741 | auto MapIt = RegionToScopMap.find(Key: R); |
2742 | if (MapIt != RegionToScopMap.end()) |
2743 | return MapIt->second.get(); |
2744 | return nullptr; |
2745 | } |
2746 | |
2747 | /// Recompute the Scop-Information for a function. |
2748 | /// |
2749 | /// This invalidates any iterators. |
2750 | void recompute(); |
2751 | |
2752 | /// Handle invalidation explicitly |
2753 | bool invalidate(Function &F, const PreservedAnalyses &PA, |
2754 | FunctionAnalysisManager::Invalidator &Inv); |
2755 | |
2756 | iterator begin() { return RegionToScopMap.begin(); } |
2757 | iterator end() { return RegionToScopMap.end(); } |
2758 | const_iterator begin() const { return RegionToScopMap.begin(); } |
2759 | const_iterator end() const { return RegionToScopMap.end(); } |
2760 | reverse_iterator rbegin() { return RegionToScopMap.rbegin(); } |
2761 | reverse_iterator rend() { return RegionToScopMap.rend(); } |
2762 | const_reverse_iterator rbegin() const { return RegionToScopMap.rbegin(); } |
2763 | const_reverse_iterator rend() const { return RegionToScopMap.rend(); } |
2764 | bool empty() const { return RegionToScopMap.empty(); } |
2765 | }; |
2766 | |
2767 | struct ScopInfoAnalysis : AnalysisInfoMixin<ScopInfoAnalysis> { |
2768 | static AnalysisKey Key; |
2769 | |
2770 | using Result = ScopInfo; |
2771 | |
2772 | Result run(Function &, FunctionAnalysisManager &); |
2773 | }; |
2774 | |
2775 | struct ScopInfoPrinterPass final : PassInfoMixin<ScopInfoPrinterPass> { |
2776 | ScopInfoPrinterPass(raw_ostream &OS) : Stream(OS) {} |
2777 | |
2778 | PreservedAnalyses run(Function &, FunctionAnalysisManager &); |
2779 | |
2780 | raw_ostream &Stream; |
2781 | }; |
2782 | |
2783 | //===----------------------------------------------------------------------===// |
2784 | /// The legacy pass manager's analysis pass to compute scop information |
2785 | /// for the whole function. |
2786 | /// |
2787 | /// This pass will maintain a map of the maximal region within a scop to its |
2788 | /// scop object for all the feasible scops present in a function. |
2789 | /// This pass is an alternative to the ScopInfoRegionPass in order to avoid a |
2790 | /// region pass manager. |
2791 | class ScopInfoWrapperPass final : public FunctionPass { |
2792 | std::unique_ptr<ScopInfo> Result; |
2793 | |
2794 | public: |
2795 | ScopInfoWrapperPass() : FunctionPass(ID) {} |
2796 | ~ScopInfoWrapperPass() override = default; |
2797 | |
2798 | static char ID; // Pass identification, replacement for typeid |
2799 | |
2800 | ScopInfo *getSI() { return Result.get(); } |
2801 | const ScopInfo *getSI() const { return Result.get(); } |
2802 | |
2803 | /// Calculate all the polyhedral scops for a given function. |
2804 | bool runOnFunction(Function &F) override; |
2805 | |
2806 | void releaseMemory() override { Result.reset(); } |
2807 | |
2808 | void print(raw_ostream &O, const Module *M = nullptr) const override; |
2809 | |
2810 | void getAnalysisUsage(AnalysisUsage &AU) const override; |
2811 | }; |
2812 | |
2813 | llvm::Pass *createScopInfoPrinterLegacyFunctionPass(llvm::raw_ostream &OS); |
2814 | } // end namespace polly |
2815 | |
2816 | namespace llvm { |
2817 | void initializeScopInfoRegionPassPass(PassRegistry &); |
2818 | void initializeScopInfoPrinterLegacyRegionPassPass(PassRegistry &); |
2819 | void initializeScopInfoWrapperPassPass(PassRegistry &); |
2820 | void initializeScopInfoPrinterLegacyFunctionPassPass(PassRegistry &); |
2821 | } // end namespace llvm |
2822 | |
2823 | #endif // POLLY_SCOPINFO_H |
2824 | |