1 //===- polly/ScopInfo.h -----------------------------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // Store the polyhedral model representation of a static control flow region,
10 // also called SCoP (Static Control Part).
12 // This representation is shared among several tools in the polyhedral
13 // community, which are e.g. CLooG, Pluto, Loopo, Graphite.
15 //===----------------------------------------------------------------------===//
17 #ifndef POLLY_SCOPINFO_H
18 #define POLLY_SCOPINFO_H
20 #include "polly/ScopDetection.h"
21 #include "polly/Support/SCEVAffinator.h"
22 #include "llvm/ADT/ArrayRef.h"
23 #include "llvm/ADT/MapVector.h"
24 #include "llvm/ADT/SetVector.h"
25 #include "llvm/Analysis/RegionPass.h"
26 #include "llvm/IR/DebugLoc.h"
27 #include "llvm/IR/Instruction.h"
28 #include "llvm/IR/Instructions.h"
29 #include "llvm/IR/PassManager.h"
30 #include "llvm/IR/ValueHandle.h"
31 #include "llvm/Pass.h"
32 #include "isl/isl-noexceptions.h"
35 #include <forward_list>
40 void initializeScopInfoRegionPassPass(PassRegistry
&);
41 void initializeScopInfoWrapperPassPass(PassRegistry
&);
42 } // end namespace llvm
48 //===---------------------------------------------------------------------===//
50 extern bool UseInstructionNames
;
52 // The maximal number of basic sets we allow during domain construction to
53 // be created. More complex scops will result in very high compile time and
54 // are also unlikely to result in good code.
55 extern int const MaxDisjunctsInDomain
;
57 /// Enumeration of assumptions Polly can take.
71 /// Enum to distinguish between assumptions and restrictions.
72 enum AssumptionSign
{ AS_ASSUMPTION
, AS_RESTRICTION
};
74 /// The different memory kinds used in Polly.
76 /// We distinguish between arrays and various scalar memory objects. We use
77 /// the term ``array'' to describe memory objects that consist of a set of
78 /// individual data elements arranged in a multi-dimensional grid. A scalar
79 /// memory object describes an individual data element and is used to model
80 /// the definition and uses of llvm::Values.
82 /// The polyhedral model does traditionally not reason about SSA values. To
83 /// reason about llvm::Values we model them "as if" they were zero-dimensional
84 /// memory objects, even though they were not actually allocated in (main)
85 /// memory. Memory for such objects is only alloca[ed] at CodeGeneration
86 /// time. To relate the memory slots used during code generation with the
87 /// llvm::Values they belong to the new names for these corresponding stack
88 /// slots are derived by appending suffixes (currently ".s2a" and ".phiops")
89 /// to the name of the original llvm::Value. To describe how def/uses are
90 /// modeled exactly we use these suffixes here as well.
92 /// There are currently four different kinds of memory objects:
93 enum class MemoryKind
{
94 /// MemoryKind::Array: Models a one or multi-dimensional array
96 /// A memory object that can be described by a multi-dimensional array.
97 /// Memory objects of this type are used to model actual multi-dimensional
98 /// arrays as they exist in LLVM-IR, but they are also used to describe
100 /// - A single data element allocated on the stack using 'alloca' is
101 /// modeled as a one-dimensional, single-element array.
102 /// - A single data element allocated as a global variable is modeled as
103 /// one-dimensional, single-element array.
104 /// - Certain multi-dimensional arrays with variable size, which in
105 /// LLVM-IR are commonly expressed as a single-dimensional access with a
106 /// complicated access function, are modeled as multi-dimensional
107 /// memory objects (grep for "delinearization").
110 /// MemoryKind::Value: Models an llvm::Value
112 /// Memory objects of type MemoryKind::Value are used to model the data flow
113 /// induced by llvm::Values. For each llvm::Value that is used across
114 /// BasicBlocks, one ScopArrayInfo object is created. A single memory WRITE
115 /// stores the llvm::Value at its definition into the memory object and at
116 /// each use of the llvm::Value (ignoring trivial intra-block uses) a
117 /// corresponding READ is added. For instance, the use/def chain of a
118 /// llvm::Value %V depicted below
119 /// ______________________
121 /// | %V = float op ... |
122 /// ----------------------
124 /// _________________ _________________
125 /// |UseBB1: | |UseBB2: |
126 /// | use float %V | | use float %V |
127 /// ----------------- -----------------
129 /// is modeled as if the following memory accesses occurred:
131 /// __________________________
133 /// | %V.s2a = alloca float |
134 /// --------------------------
136 /// ___________________________________
138 /// | store %float %V, float* %V.s2a |
139 /// -----------------------------------
141 /// ____________________________________ ___________________________________
142 /// |UseBB1: | |UseBB2: |
143 /// | %V.reload1 = load float* %V.s2a | | %V.reload2 = load float* %V.s2a|
144 /// | use float %V.reload1 | | use float %V.reload2 |
145 /// ------------------------------------ -----------------------------------
149 /// MemoryKind::PHI: Models PHI nodes within the SCoP
151 /// Besides the MemoryKind::Value memory object used to model the normal
152 /// llvm::Value dependences described above, PHI nodes require an additional
153 /// memory object of type MemoryKind::PHI to describe the forwarding of values
157 /// As an example, a PHIInst instructions
159 /// %PHI = phi float [ %Val1, %IncomingBlock1 ], [ %Val2, %IncomingBlock2 ]
161 /// is modeled as if the accesses occurred this way:
163 /// _______________________________
165 /// | %PHI.phiops = alloca float |
166 /// -------------------------------
168 /// __________________________________ __________________________________
169 /// |IncomingBlock1: | |IncomingBlock2: |
171 /// | store float %Val1 %PHI.phiops | | store float %Val2 %PHI.phiops |
172 /// | br label % JoinBlock | | br label %JoinBlock |
173 /// ---------------------------------- ----------------------------------
176 /// _________________________________________
178 /// | %PHI = load float, float* PHI.phiops |
179 /// -----------------------------------------
181 /// Note that there can also be a scalar write access for %PHI if used in a
182 /// different BasicBlock, i.e. there can be a memory object %PHI.phiops as
183 /// well as a memory object %PHI.s2a.
186 /// MemoryKind::ExitPHI: Models PHI nodes in the SCoP's exit block
188 /// For PHI nodes in the Scop's exit block a special memory object kind is
189 /// used. The modeling used is identical to MemoryKind::PHI, with the
191 /// that there are no READs from these memory objects. The PHINode's
192 /// llvm::Value is treated as a value escaping the SCoP. WRITE accesses
193 /// write directly to the escaping value's ".s2a" alloca.
197 /// Maps from a loop to the affine function expressing its backedge taken count.
198 /// The backedge taken count already enough to express iteration domain as we
199 /// only allow loops with canonical induction variable.
200 /// A canonical induction variable is:
201 /// an integer recurrence that starts at 0 and increments by one each time
202 /// through the loop.
203 using LoopBoundMapType
= std::map
<const Loop
*, const SCEV
*>;
205 using AccFuncVector
= std::vector
<std::unique_ptr
<MemoryAccess
>>;
207 /// A class to store information about arrays in the SCoP.
209 /// Objects are accessible via the ScoP, MemoryAccess or the id associated with
210 /// the MemoryAccess access function.
212 class ScopArrayInfo
{
214 /// Construct a ScopArrayInfo object.
216 /// @param BasePtr The array base pointer.
217 /// @param ElementType The type of the elements stored in the array.
218 /// @param IslCtx The isl context used to create the base pointer id.
219 /// @param DimensionSizes A vector containing the size of each dimension.
220 /// @param Kind The kind of the array object.
221 /// @param DL The data layout of the module.
222 /// @param S The scop this array object belongs to.
223 /// @param BaseName The optional name of this memory reference.
224 ScopArrayInfo(Value
*BasePtr
, Type
*ElementType
, isl::ctx IslCtx
,
225 ArrayRef
<const SCEV
*> DimensionSizes
, MemoryKind Kind
,
226 const DataLayout
&DL
, Scop
*S
, const char *BaseName
= nullptr);
228 /// Destructor to free the isl id of the base pointer.
231 /// Update the element type of the ScopArrayInfo object.
233 /// Memory accesses referencing this ScopArrayInfo object may use
234 /// different element sizes. This function ensures the canonical element type
235 /// stored is small enough to model accesses to the current element type as
236 /// well as to @p NewElementType.
238 /// @param NewElementType An element type that is used to access this array.
239 void updateElementType(Type
*NewElementType
);
241 /// Update the sizes of the ScopArrayInfo object.
243 /// A ScopArrayInfo object may be created without all outer dimensions being
244 /// available. This function is called when new memory accesses are added for
245 /// this ScopArrayInfo object. It verifies that sizes are compatible and adds
246 /// additional outer array dimensions, if needed.
248 /// @param Sizes A vector of array sizes where the rightmost array
249 /// sizes need to match the innermost array sizes already
251 /// @param CheckConsistency Update sizes, even if new sizes are inconsistent
253 bool updateSizes(ArrayRef
<const SCEV
*> Sizes
, bool CheckConsistency
= true);
255 /// Make the ScopArrayInfo model a Fortran array.
256 /// It receives the Fortran array descriptor and stores this.
257 /// It also adds a piecewise expression for the outermost dimension
258 /// since this information is available for Fortran arrays at runtime.
259 void applyAndSetFAD(Value
*FAD
);
261 /// Get the FortranArrayDescriptor corresponding to this array if it exists,
262 /// nullptr otherwise.
263 Value
*getFortranArrayDescriptor() const { return this->FAD
; }
265 /// Set the base pointer to @p BP.
266 void setBasePtr(Value
*BP
) { BasePtr
= BP
; }
268 /// Return the base pointer.
269 Value
*getBasePtr() const { return BasePtr
; }
271 // Set IsOnHeap to the value in parameter.
272 void setIsOnHeap(bool value
) { IsOnHeap
= value
; }
274 /// For indirect accesses return the origin SAI of the BP, else null.
275 const ScopArrayInfo
*getBasePtrOriginSAI() const { return BasePtrOriginSAI
; }
277 /// The set of derived indirect SAIs for this origin SAI.
278 const SmallSetVector
<ScopArrayInfo
*, 2> &getDerivedSAIs() const {
282 /// Return the number of dimensions.
283 unsigned getNumberOfDimensions() const {
284 if (Kind
== MemoryKind::PHI
|| Kind
== MemoryKind::ExitPHI
||
285 Kind
== MemoryKind::Value
)
287 return DimensionSizes
.size();
290 /// Return the size of dimension @p dim as SCEV*.
292 // Scalars do not have array dimensions and the first dimension of
293 // a (possibly multi-dimensional) array also does not carry any size
294 // information, in case the array is not newly created.
295 const SCEV
*getDimensionSize(unsigned Dim
) const {
296 assert(Dim
< getNumberOfDimensions() && "Invalid dimension");
297 return DimensionSizes
[Dim
];
300 /// Return the size of dimension @p dim as isl::pw_aff.
302 // Scalars do not have array dimensions and the first dimension of
303 // a (possibly multi-dimensional) array also does not carry any size
304 // information, in case the array is not newly created.
305 isl::pw_aff
getDimensionSizePw(unsigned Dim
) const {
306 assert(Dim
< getNumberOfDimensions() && "Invalid dimension");
307 return DimensionSizesPw
[Dim
];
310 /// Get the canonical element type of this array.
312 /// @returns The canonical element type of this array.
313 Type
*getElementType() const { return ElementType
; }
315 /// Get element size in bytes.
316 int getElemSizeInBytes() const;
318 /// Get the name of this memory reference.
319 std::string
getName() const;
321 /// Return the isl id for the base pointer.
322 isl::id
getBasePtrId() const;
324 /// Return what kind of memory this represents.
325 MemoryKind
getKind() const { return Kind
; }
327 /// Is this array info modeling an llvm::Value?
328 bool isValueKind() const { return Kind
== MemoryKind::Value
; }
330 /// Is this array info modeling special PHI node memory?
332 /// During code generation of PHI nodes, there is a need for two kinds of
333 /// virtual storage. The normal one as it is used for all scalar dependences,
334 /// where the result of the PHI node is stored and later loaded from as well
335 /// as a second one where the incoming values of the PHI nodes are stored
336 /// into and reloaded when the PHI is executed. As both memories use the
337 /// original PHI node as virtual base pointer, we have this additional
338 /// attribute to distinguish the PHI node specific array modeling from the
339 /// normal scalar array modeling.
340 bool isPHIKind() const { return Kind
== MemoryKind::PHI
; }
342 /// Is this array info modeling an MemoryKind::ExitPHI?
343 bool isExitPHIKind() const { return Kind
== MemoryKind::ExitPHI
; }
345 /// Is this array info modeling an array?
346 bool isArrayKind() const { return Kind
== MemoryKind::Array
; }
348 /// Is this array allocated on heap
350 /// This property is only relevant if the array is allocated by Polly instead
351 /// of pre-existing. If false, it is allocated using alloca instead malloca.
352 bool isOnHeap() const { return IsOnHeap
; }
354 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
355 /// Dump a readable representation to stderr.
359 /// Print a readable representation to @p OS.
361 /// @param SizeAsPwAff Print the size as isl::pw_aff
362 void print(raw_ostream
&OS
, bool SizeAsPwAff
= false) const;
364 /// Access the ScopArrayInfo associated with an access function.
365 static const ScopArrayInfo
*getFromAccessFunction(isl::pw_multi_aff PMA
);
367 /// Access the ScopArrayInfo associated with an isl Id.
368 static const ScopArrayInfo
*getFromId(isl::id Id
);
370 /// Get the space of this array access.
371 isl::space
getSpace() const;
373 /// If the array is read only
376 /// Verify that @p Array is compatible to this ScopArrayInfo.
378 /// Two arrays are compatible if their dimensionality, the sizes of their
379 /// dimensions, and their element sizes match.
381 /// @param Array The array to compare against.
383 /// @returns True, if the arrays are compatible, False otherwise.
384 bool isCompatibleWith(const ScopArrayInfo
*Array
) const;
387 void addDerivedSAI(ScopArrayInfo
*DerivedSAI
) {
388 DerivedSAIs
.insert(DerivedSAI
);
391 /// For indirect accesses this is the SAI of the BP origin.
392 const ScopArrayInfo
*BasePtrOriginSAI
;
394 /// For origin SAIs the set of derived indirect SAIs.
395 SmallSetVector
<ScopArrayInfo
*, 2> DerivedSAIs
;
397 /// The base pointer.
398 AssertingVH
<Value
> BasePtr
;
400 /// The canonical element type of this array.
402 /// The canonical element type describes the minimal accessible element in
403 /// this array. Not all elements accessed, need to be of the very same type,
404 /// but the allocation size of the type of the elements loaded/stored from/to
405 /// this array needs to be a multiple of the allocation size of the canonical
409 /// The isl id for the base pointer.
412 /// True if the newly allocated array is on heap.
413 bool IsOnHeap
= false;
415 /// The sizes of each dimension as SCEV*.
416 SmallVector
<const SCEV
*, 4> DimensionSizes
;
418 /// The sizes of each dimension as isl::pw_aff.
419 SmallVector
<isl::pw_aff
, 4> DimensionSizesPw
;
421 /// The type of this scop array info object.
423 /// We distinguish between SCALAR, PHI and ARRAY objects.
426 /// The data layout of the module.
427 const DataLayout
&DL
;
429 /// The scop this SAI object belongs to.
432 /// If this array models a Fortran array, then this points
433 /// to the Fortran array descriptor.
434 Value
*FAD
= nullptr;
437 /// Represent memory accesses in statements.
440 friend class ScopStmt
;
441 friend class ScopBuilder
;
444 /// The access type of a memory access
446 /// There are three kind of access types:
450 /// A certain set of memory locations are read and may be used for internal
453 /// * A must-write access
455 /// A certain set of memory locations is definitely written. The old value is
456 /// replaced by a newly calculated value. The old value is not read or used at
459 /// * A may-write access
461 /// A certain set of memory locations may be written. The memory location may
462 /// contain a new value if there is actually a write or the old value may
463 /// remain, if no write happens.
470 /// Reduction access type
472 /// Commutative and associative binary operations suitable for reductions
474 RT_NONE
, ///< Indicate no reduction at all
475 RT_ADD
, ///< Addition
476 RT_MUL
, ///< Multiplication
477 RT_BOR
, ///< Bitwise Or
478 RT_BXOR
, ///< Bitwise XOr
479 RT_BAND
, ///< Bitwise And
483 /// A unique identifier for this memory access.
485 /// The identifier is unique between all memory accesses belonging to the same
489 /// What is modeled by this MemoryAccess.
493 /// Whether it a reading or writing access, and if writing, whether it
494 /// is conditional (MAY_WRITE).
495 enum AccessType AccType
;
497 /// Reduction type for reduction like accesses, RT_NONE otherwise
499 /// An access is reduction like if it is part of a load-store chain in which
500 /// both access the same memory location (use the same LLVM-IR value
501 /// as pointer reference). Furthermore, between the load and the store there
502 /// is exactly one binary operator which is known to be associative and
507 /// We can later lift the constraint that the same LLVM-IR value defines the
508 /// memory location to handle scops such as the following:
512 /// sum[i+j] = sum[i] + 3;
514 /// Here not all iterations access the same memory location, but iterations
515 /// for which j = 0 holds do. After lifting the equality check in ScopBuilder,
516 /// subsequent transformations do not only need check if a statement is
517 /// reduction like, but they also need to verify that that the reduction
518 /// property is only exploited for statement instances that load from and
519 /// store to the same data location. Doing so at dependence analysis time
520 /// could allow us to handle the above example.
521 ReductionType RedType
= RT_NONE
;
523 /// Parent ScopStmt of this access.
526 /// The domain under which this access is not modeled precisely.
528 /// The invalid domain for an access describes all parameter combinations
529 /// under which the statement looks to be executed but is in fact not because
530 /// some assumption/restriction makes the access invalid.
531 isl::set InvalidDomain
;
533 // Properties describing the accessed array.
534 // TODO: It might be possible to move them to ScopArrayInfo.
537 /// The base address (e.g., A for A[i+j]).
539 /// The #BaseAddr of a memory access of kind MemoryKind::Array is the base
540 /// pointer of the memory access.
541 /// The #BaseAddr of a memory access of kind MemoryKind::PHI or
542 /// MemoryKind::ExitPHI is the PHI node itself.
543 /// The #BaseAddr of a memory access of kind MemoryKind::Value is the
544 /// instruction defining the value.
545 AssertingVH
<Value
> BaseAddr
;
547 /// Type a single array element wrt. this access.
550 /// Size of each dimension of the accessed array.
551 SmallVector
<const SCEV
*, 4> Sizes
;
554 // Properties describing the accessed element.
557 /// The access instruction of this memory access.
559 /// For memory accesses of kind MemoryKind::Array the access instruction is
560 /// the Load or Store instruction performing the access.
562 /// For memory accesses of kind MemoryKind::PHI or MemoryKind::ExitPHI the
563 /// access instruction of a load access is the PHI instruction. The access
564 /// instruction of a PHI-store is the incoming's block's terminator
567 /// For memory accesses of kind MemoryKind::Value the access instruction of a
568 /// load access is nullptr because generally there can be multiple
569 /// instructions in the statement using the same llvm::Value. The access
570 /// instruction of a write access is the instruction that defines the
572 Instruction
*AccessInstruction
= nullptr;
574 /// Incoming block and value of a PHINode.
575 SmallVector
<std::pair
<BasicBlock
*, Value
*>, 4> Incoming
;
577 /// The value associated with this memory access.
579 /// - For array memory accesses (MemoryKind::Array) it is the loaded result
580 /// or the stored value. If the access instruction is a memory intrinsic it
581 /// the access value is also the memory intrinsic.
582 /// - For accesses of kind MemoryKind::Value it is the access instruction
584 /// - For accesses of kind MemoryKind::PHI or MemoryKind::ExitPHI it is the
585 /// PHI node itself (for both, READ and WRITE accesses).
587 AssertingVH
<Value
> AccessValue
;
589 /// Are all the subscripts affine expression?
590 bool IsAffine
= true;
592 /// Subscript expression for each dimension.
593 SmallVector
<const SCEV
*, 4> Subscripts
;
595 /// Relation from statement instances to the accessed array elements.
597 /// In the common case this relation is a function that maps a set of loop
598 /// indices to the memory address from which a value is loaded/stored:
602 /// S: A[i + 3 j] = ...
604 /// => { S[i,j] -> A[i + 3j] }
606 /// In case the exact access function is not known, the access relation may
607 /// also be a one to all mapping { S[i,j] -> A[o] } describing that any
608 /// element accessible through A might be accessed.
610 /// In case of an access to a larger element belonging to an array that also
611 /// contains smaller elements, the access relation models the larger access
612 /// with multiple smaller accesses of the size of the minimal array element
618 /// S: A[i] = *((double*)&A[4 * i]);
620 /// => { S[i] -> A[i]; S[i] -> A[o] : 4i <= o <= 4i + 3 }
621 isl::map AccessRelation
;
623 /// Updated access relation read from JSCOP file.
624 isl::map NewAccessRelation
;
626 /// Fortran arrays whose sizes are not statically known are stored in terms
627 /// of a descriptor struct. This maintains a raw pointer to the memory,
628 /// along with auxiliary fields with information such as dimensions.
629 /// We hold a reference to the descriptor corresponding to a MemoryAccess
630 /// into a Fortran array. FAD for "Fortran Array Descriptor"
631 AssertingVH
<Value
> FAD
;
634 isl::basic_map
createBasicAccessMap(ScopStmt
*Statement
);
636 void assumeNoOutOfBound();
638 /// Compute bounds on an over approximated access relation.
640 /// @param ElementSize The size of one element accessed.
641 void computeBoundsOnAccessRelation(unsigned ElementSize
);
643 /// Get the original access function as read from IR.
644 isl::map
getOriginalAccessRelation() const;
646 /// Return the space in which the access relation lives in.
647 isl::space
getOriginalAccessRelationSpace() const;
649 /// Get the new access function imported or set by a pass
650 isl::map
getNewAccessRelation() const;
652 /// Fold the memory access to consider parametric offsets
654 /// To recover memory accesses with array size parameters in the subscript
655 /// expression we post-process the delinearization results.
657 /// We would normally recover from an access A[exp0(i) * N + exp1(i)] into an
658 /// array A[][N] the 2D access A[exp0(i)][exp1(i)]. However, another valid
659 /// delinearization is A[exp0(i) - 1][exp1(i) + N] which - depending on the
660 /// range of exp1(i) - may be preferable. Specifically, for cases where we
661 /// know exp1(i) is negative, we want to choose the latter expression.
663 /// As we commonly do not have any information about the range of exp1(i),
664 /// we do not choose one of the two options, but instead create a piecewise
665 /// access function that adds the (-1, N) offsets as soon as exp1(i) becomes
666 /// negative. For a 2D array such an access function is created by applying
667 /// the piecewise map:
669 /// [i,j] -> [i, j] : j >= 0
670 /// [i,j] -> [i-1, j+N] : j < 0
672 /// We can generalize this mapping to arbitrary dimensions by applying this
673 /// piecewise mapping pairwise from the rightmost to the leftmost access
674 /// dimension. It would also be possible to cover a wider range by introducing
675 /// more cases and adding multiple of Ns to these cases. However, this has
676 /// not yet been necessary.
677 /// The introduction of different cases necessarily complicates the memory
678 /// access function, but cases that can be statically proven to not happen
679 /// will be eliminated later on.
680 void foldAccessRelation();
682 /// Create the access relation for the underlying memory intrinsic.
683 void buildMemIntrinsicAccessRelation();
685 /// Assemble the access relation from all available information.
687 /// In particular, used the information passes in the constructor and the
688 /// parent ScopStmt set by setStatment().
690 /// @param SAI Info object for the accessed array.
691 void buildAccessRelation(const ScopArrayInfo
*SAI
);
693 /// Carry index overflows of dimensions with constant size to the next higher
696 /// For dimensions that have constant size, modulo the index by the size and
697 /// add up the carry (floored division) to the next higher dimension. This is
698 /// how overflow is defined in row-major order.
699 /// It happens e.g. when ScalarEvolution computes the offset to the base
700 /// pointer and would algebraically sum up all lower dimensions' indices of
705 /// A[1][6] -> A[2][2]
706 void wrapConstantDimensions();
709 /// Create a new MemoryAccess.
711 /// @param Stmt The parent statement.
712 /// @param AccessInst The instruction doing the access.
713 /// @param BaseAddr The accessed array's address.
714 /// @param ElemType The type of the accessed array elements.
715 /// @param AccType Whether read or write access.
716 /// @param IsAffine Whether the subscripts are affine expressions.
717 /// @param Kind The kind of memory accessed.
718 /// @param Subscripts Subscript expressions
719 /// @param Sizes Dimension lengths of the accessed array.
720 MemoryAccess(ScopStmt
*Stmt
, Instruction
*AccessInst
, AccessType AccType
,
721 Value
*BaseAddress
, Type
*ElemType
, bool Affine
,
722 ArrayRef
<const SCEV
*> Subscripts
, ArrayRef
<const SCEV
*> Sizes
,
723 Value
*AccessValue
, MemoryKind Kind
);
725 /// Create a new MemoryAccess that corresponds to @p AccRel.
727 /// Along with @p Stmt and @p AccType it uses information about dimension
728 /// lengths of the accessed array, the type of the accessed array elements,
729 /// the name of the accessed array that is derived from the object accessible
732 /// @param Stmt The parent statement.
733 /// @param AccType Whether read or write access.
734 /// @param AccRel The access relation that describes the memory access.
735 MemoryAccess(ScopStmt
*Stmt
, AccessType AccType
, isl::map AccRel
);
737 MemoryAccess(const MemoryAccess
&) = delete;
738 MemoryAccess
&operator=(const MemoryAccess
&) = delete;
741 /// Add a new incoming block/value pairs for this PHI/ExitPHI access.
743 /// @param IncomingBlock The PHI's incoming block.
744 /// @param IncomingValue The value when reaching the PHI from the @p
746 void addIncoming(BasicBlock
*IncomingBlock
, Value
*IncomingValue
) {
748 assert(isAnyPHIKind());
749 Incoming
.emplace_back(std::make_pair(IncomingBlock
, IncomingValue
));
752 /// Return the list of possible PHI/ExitPHI values.
754 /// After code generation moves some PHIs around during region simplification,
755 /// we cannot reliably locate the original PHI node and its incoming values
756 /// anymore. For this reason we remember these explicitly for all PHI-kind
758 ArrayRef
<std::pair
<BasicBlock
*, Value
*>> getIncoming() const {
759 assert(isAnyPHIKind());
763 /// Get the type of a memory access.
764 enum AccessType
getType() { return AccType
; }
766 /// Is this a reduction like access?
767 bool isReductionLike() const { return RedType
!= RT_NONE
; }
769 /// Is this a read memory access?
770 bool isRead() const { return AccType
== MemoryAccess::READ
; }
772 /// Is this a must-write memory access?
773 bool isMustWrite() const { return AccType
== MemoryAccess::MUST_WRITE
; }
775 /// Is this a may-write memory access?
776 bool isMayWrite() const { return AccType
== MemoryAccess::MAY_WRITE
; }
778 /// Is this a write memory access?
779 bool isWrite() const { return isMustWrite() || isMayWrite(); }
781 /// Is this a memory intrinsic access (memcpy, memset, memmove)?
782 bool isMemoryIntrinsic() const {
783 return isa
<MemIntrinsic
>(getAccessInstruction());
786 /// Check if a new access relation was imported or set by a pass.
787 bool hasNewAccessRelation() const { return !NewAccessRelation
.is_null(); }
789 /// Return the newest access relation of this access.
791 /// There are two possibilities:
792 /// 1) The original access relation read from the LLVM-IR.
793 /// 2) A new access relation imported from a json file or set by another
794 /// pass (e.g., for privatization).
796 /// As 2) is by construction "newer" than 1) we return the new access
797 /// relation if present.
799 isl::map
getLatestAccessRelation() const {
800 return hasNewAccessRelation() ? getNewAccessRelation()
801 : getOriginalAccessRelation();
804 /// Old name of getLatestAccessRelation().
805 isl::map
getAccessRelation() const { return getLatestAccessRelation(); }
807 /// Get an isl map describing the memory address accessed.
809 /// In most cases the memory address accessed is well described by the access
810 /// relation obtained with getAccessRelation. However, in case of arrays
811 /// accessed with types of different size the access relation maps one access
812 /// to multiple smaller address locations. This method returns an isl map that
813 /// relates each dynamic statement instance to the unique memory location
814 /// that is loaded from / stored to.
816 /// For an access relation { S[i] -> A[o] : 4i <= o <= 4i + 3 } this method
817 /// will return the address function { S[i] -> A[4i] }.
819 /// @returns The address function for this memory access.
820 isl::map
getAddressFunction() const;
822 /// Return the access relation after the schedule was applied.
824 applyScheduleToAccessRelation(isl::union_map Schedule
) const;
826 /// Get an isl string representing the access function read from IR.
827 std::string
getOriginalAccessRelationStr() const;
829 /// Get an isl string representing a new access function, if available.
830 std::string
getNewAccessRelationStr() const;
832 /// Get an isl string representing the latest access relation.
833 std::string
getAccessRelationStr() const;
835 /// Get the original base address of this access (e.g. A for A[i+j]) when
838 /// This address may differ from the base address referenced by the original
839 /// ScopArrayInfo to which this array belongs, as this memory access may
840 /// have been canonicalized to a ScopArrayInfo which has a different but
841 /// identically-valued base pointer in case invariant load hoisting is
843 Value
*getOriginalBaseAddr() const { return BaseAddr
; }
845 /// Get the detection-time base array isl::id for this access.
846 isl::id
getOriginalArrayId() const;
848 /// Get the base array isl::id for this access, modifiable through
849 /// setNewAccessRelation().
850 isl::id
getLatestArrayId() const;
852 /// Old name of getOriginalArrayId().
853 isl::id
getArrayId() const { return getOriginalArrayId(); }
855 /// Get the detection-time ScopArrayInfo object for the base address.
856 const ScopArrayInfo
*getOriginalScopArrayInfo() const;
858 /// Get the ScopArrayInfo object for the base address, or the one set
859 /// by setNewAccessRelation().
860 const ScopArrayInfo
*getLatestScopArrayInfo() const;
862 /// Legacy name of getOriginalScopArrayInfo().
863 const ScopArrayInfo
*getScopArrayInfo() const {
864 return getOriginalScopArrayInfo();
867 /// Return a string representation of the access's reduction type.
868 const std::string
getReductionOperatorStr() const;
870 /// Return a string representation of the reduction type @p RT.
871 static const std::string
getReductionOperatorStr(ReductionType RT
);
873 /// Return the element type of the accessed array wrt. this access.
874 Type
*getElementType() const { return ElementType
; }
876 /// Return the access value of this memory access.
877 Value
*getAccessValue() const { return AccessValue
; }
879 /// Return llvm::Value that is stored by this access, if available.
881 /// PHI nodes may not have a unique value available that is stored, as in
882 /// case of region statements one out of possibly several llvm::Values
883 /// might be stored. In this case nullptr is returned.
884 Value
*tryGetValueStored() {
885 assert(isWrite() && "Only write statement store values");
886 if (isAnyPHIKind()) {
887 if (Incoming
.size() == 1)
888 return Incoming
[0].second
;
894 /// Return the access instruction of this memory access.
895 Instruction
*getAccessInstruction() const { return AccessInstruction
; }
897 /// Return the number of access function subscript.
898 unsigned getNumSubscripts() const { return Subscripts
.size(); }
900 /// Return the access function subscript in the dimension @p Dim.
901 const SCEV
*getSubscript(unsigned Dim
) const { return Subscripts
[Dim
]; }
903 /// Compute the isl representation for the SCEV @p E wrt. this access.
905 /// Note that this function will also adjust the invalid context accordingly.
906 isl::pw_aff
getPwAff(const SCEV
*E
);
908 /// Get the invalid domain for this access.
909 isl::set
getInvalidDomain() const { return InvalidDomain
; }
911 /// Get the invalid context for this access.
912 isl::set
getInvalidContext() const { return getInvalidDomain().params(); }
914 /// Get the stride of this memory access in the specified Schedule. Schedule
915 /// is a map from the statement to a schedule where the innermost dimension is
916 /// the dimension of the innermost loop containing the statement.
917 isl::set
getStride(isl::map Schedule
) const;
919 /// Get the FortranArrayDescriptor corresponding to this memory access if
920 /// it exists, and nullptr otherwise.
921 Value
*getFortranArrayDescriptor() const { return this->FAD
; }
923 /// Is the stride of the access equal to a certain width? Schedule is a map
924 /// from the statement to a schedule where the innermost dimension is the
925 /// dimension of the innermost loop containing the statement.
926 bool isStrideX(isl::map Schedule
, int StrideWidth
) const;
928 /// Is consecutive memory accessed for a given statement instance set?
929 /// Schedule is a map from the statement to a schedule where the innermost
930 /// dimension is the dimension of the innermost loop containing the
932 bool isStrideOne(isl::map Schedule
) const;
934 /// Is always the same memory accessed for a given statement instance set?
935 /// Schedule is a map from the statement to a schedule where the innermost
936 /// dimension is the dimension of the innermost loop containing the
938 bool isStrideZero(isl::map Schedule
) const;
940 /// Return the kind when this access was first detected.
941 MemoryKind
getOriginalKind() const {
942 assert(!getOriginalScopArrayInfo() /* not yet initialized */ ||
943 getOriginalScopArrayInfo()->getKind() == Kind
);
947 /// Return the kind considering a potential setNewAccessRelation.
948 MemoryKind
getLatestKind() const {
949 return getLatestScopArrayInfo()->getKind();
952 /// Whether this is an access of an explicit load or store in the IR.
953 bool isOriginalArrayKind() const {
954 return getOriginalKind() == MemoryKind::Array
;
957 /// Whether storage memory is either an custom .s2a/.phiops alloca
958 /// (false) or an existing pointer into an array (true).
959 bool isLatestArrayKind() const {
960 return getLatestKind() == MemoryKind::Array
;
963 /// Old name of isOriginalArrayKind.
964 bool isArrayKind() const { return isOriginalArrayKind(); }
966 /// Whether this access is an array to a scalar memory object, without
967 /// considering changes by setNewAccessRelation.
969 /// Scalar accesses are accesses to MemoryKind::Value, MemoryKind::PHI or
970 /// MemoryKind::ExitPHI.
971 bool isOriginalScalarKind() const {
972 return getOriginalKind() != MemoryKind::Array
;
975 /// Whether this access is an array to a scalar memory object, also
976 /// considering changes by setNewAccessRelation.
977 bool isLatestScalarKind() const {
978 return getLatestKind() != MemoryKind::Array
;
981 /// Old name of isOriginalScalarKind.
982 bool isScalarKind() const { return isOriginalScalarKind(); }
984 /// Was this MemoryAccess detected as a scalar dependences?
985 bool isOriginalValueKind() const {
986 return getOriginalKind() == MemoryKind::Value
;
989 /// Is this MemoryAccess currently modeling scalar dependences?
990 bool isLatestValueKind() const {
991 return getLatestKind() == MemoryKind::Value
;
994 /// Old name of isOriginalValueKind().
995 bool isValueKind() const { return isOriginalValueKind(); }
997 /// Was this MemoryAccess detected as a special PHI node access?
998 bool isOriginalPHIKind() const {
999 return getOriginalKind() == MemoryKind::PHI
;
1002 /// Is this MemoryAccess modeling special PHI node accesses, also
1003 /// considering a potential change by setNewAccessRelation?
1004 bool isLatestPHIKind() const { return getLatestKind() == MemoryKind::PHI
; }
1006 /// Old name of isOriginalPHIKind.
1007 bool isPHIKind() const { return isOriginalPHIKind(); }
1009 /// Was this MemoryAccess detected as the accesses of a PHI node in the
1010 /// SCoP's exit block?
1011 bool isOriginalExitPHIKind() const {
1012 return getOriginalKind() == MemoryKind::ExitPHI
;
1015 /// Is this MemoryAccess modeling the accesses of a PHI node in the
1016 /// SCoP's exit block? Can be changed to an array access using
1017 /// setNewAccessRelation().
1018 bool isLatestExitPHIKind() const {
1019 return getLatestKind() == MemoryKind::ExitPHI
;
1022 /// Old name of isOriginalExitPHIKind().
1023 bool isExitPHIKind() const { return isOriginalExitPHIKind(); }
1025 /// Was this access detected as one of the two PHI types?
1026 bool isOriginalAnyPHIKind() const {
1027 return isOriginalPHIKind() || isOriginalExitPHIKind();
1030 /// Does this access originate from one of the two PHI types? Can be
1031 /// changed to an array access using setNewAccessRelation().
1032 bool isLatestAnyPHIKind() const {
1033 return isLatestPHIKind() || isLatestExitPHIKind();
1036 /// Old name of isOriginalAnyPHIKind().
1037 bool isAnyPHIKind() const { return isOriginalAnyPHIKind(); }
1039 /// Get the statement that contains this memory access.
1040 ScopStmt
*getStatement() const { return Statement
; }
1042 /// Get the reduction type of this access
1043 ReductionType
getReductionType() const { return RedType
; }
1045 /// Set the array descriptor corresponding to the Array on which the
1046 /// memory access is performed.
1047 void setFortranArrayDescriptor(Value
*FAD
);
1049 /// Update the original access relation.
1051 /// We need to update the original access relation during scop construction,
1052 /// when unifying the memory accesses that access the same scop array info
1053 /// object. After the scop has been constructed, the original access relation
1054 /// should not be changed any more. Instead setNewAccessRelation should
1056 void setAccessRelation(isl::map AccessRelation
);
1058 /// Set the updated access relation read from JSCOP file.
1059 void setNewAccessRelation(isl::map NewAccessRelation
);
1061 /// Return whether the MemoryyAccess is a partial access. That is, the access
1062 /// is not executed in some instances of the parent statement's domain.
1063 bool isLatestPartialAccess() const;
1065 /// Mark this a reduction like access
1066 void markAsReductionLike(ReductionType RT
) { RedType
= RT
; }
1068 /// Align the parameters in the access relation to the scop context
1069 void realignParams();
1071 /// Update the dimensionality of the memory access.
1073 /// During scop construction some memory accesses may not be constructed with
1074 /// their full dimensionality, but outer dimensions may have been omitted if
1075 /// they took the value 'zero'. By updating the dimensionality of the
1076 /// statement we add additional zero-valued dimensions to match the
1077 /// dimensionality of the ScopArrayInfo object that belongs to this memory
1079 void updateDimensionality();
1081 /// Get identifier for the memory access.
1083 /// This identifier is unique for all accesses that belong to the same scop
1085 isl::id
getId() const;
1087 /// Print the MemoryAccess.
1089 /// @param OS The output stream the MemoryAccess is printed to.
1090 void print(raw_ostream
&OS
) const;
1092 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1093 /// Print the MemoryAccess to stderr.
1097 /// Is the memory access affine?
1098 bool isAffine() const { return IsAffine
; }
1101 raw_ostream
&operator<<(raw_ostream
&OS
, MemoryAccess::ReductionType RT
);
1103 /// Ordered list type to hold accesses.
1104 using MemoryAccessList
= std::forward_list
<MemoryAccess
*>;
1106 /// Helper structure for invariant memory accesses.
1107 struct InvariantAccess
{
1108 /// The memory access that is (partially) invariant.
1111 /// The context under which the access is not invariant.
1112 isl::set NonHoistableCtx
;
1115 /// Ordered container type to hold invariant accesses.
1116 using InvariantAccessesTy
= SmallVector
<InvariantAccess
, 8>;
1118 /// Type for equivalent invariant accesses and their domain context.
1119 struct InvariantEquivClassTy
{
1120 /// The pointer that identifies this equivalence class
1121 const SCEV
*IdentifyingPointer
;
1123 /// Memory accesses now treated invariant
1125 /// These memory accesses access the pointer location that identifies
1126 /// this equivalence class. They are treated as invariant and hoisted during
1127 /// code generation.
1128 MemoryAccessList InvariantAccesses
;
1130 /// The execution context under which the memory location is accessed
1132 /// It is the union of the execution domains of the memory accesses in the
1133 /// InvariantAccesses list.
1134 isl::set ExecutionContext
;
1136 /// The type of the invariant access
1138 /// It is used to differentiate between differently typed invariant loads from
1139 /// the same location.
1143 /// Type for invariant accesses equivalence classes.
1144 using InvariantEquivClassesTy
= SmallVector
<InvariantEquivClassTy
, 8>;
1146 /// Statement of the Scop
1148 /// A Scop statement represents an instruction in the Scop.
1150 /// It is further described by its iteration domain, its schedule and its data
1152 /// At the moment every statement represents a single basic block of LLVM-IR.
1154 friend class ScopBuilder
;
1157 /// Create the ScopStmt from a BasicBlock.
1158 ScopStmt(Scop
&parent
, BasicBlock
&bb
, StringRef Name
, Loop
*SurroundingLoop
,
1159 std::vector
<Instruction
*> Instructions
);
1161 /// Create an overapproximating ScopStmt for the region @p R.
1163 /// @param EntryBlockInstructions The list of instructions that belong to the
1164 /// entry block of the region statement.
1165 /// Instructions are only tracked for entry
1166 /// blocks for now. We currently do not allow
1167 /// to modify the instructions of blocks later
1168 /// in the region statement.
1169 ScopStmt(Scop
&parent
, Region
&R
, StringRef Name
, Loop
*SurroundingLoop
,
1170 std::vector
<Instruction
*> EntryBlockInstructions
);
1172 /// Create a copy statement.
1174 /// @param Stmt The parent statement.
1175 /// @param SourceRel The source location.
1176 /// @param TargetRel The target location.
1177 /// @param Domain The original domain under which the copy statement would
1179 ScopStmt(Scop
&parent
, isl::map SourceRel
, isl::map TargetRel
,
1182 ScopStmt(const ScopStmt
&) = delete;
1183 const ScopStmt
&operator=(const ScopStmt
&) = delete;
1187 /// Polyhedral description
1190 /// The Scop containing this ScopStmt.
1193 /// The domain under which this statement is not modeled precisely.
1195 /// The invalid domain for a statement describes all parameter combinations
1196 /// under which the statement looks to be executed but is in fact not because
1197 /// some assumption/restriction makes the statement/scop invalid.
1198 isl::set InvalidDomain
;
1200 /// The iteration domain describes the set of iterations for which this
1201 /// statement is executed.
1204 /// for (i = 0; i < 100 + b; ++i)
1205 /// for (j = 0; j < i; ++j)
1208 /// 'S' is executed for different values of i and j. A vector of all
1209 /// induction variables around S (i, j) is called iteration vector.
1210 /// The domain describes the set of possible iteration vectors.
1212 /// In this case it is:
1214 /// Domain: 0 <= i <= 100 + b
1217 /// A pair of statement and iteration vector (S, (5,3)) is called statement
1221 /// The memory accesses of this statement.
1223 /// The only side effects of a statement are its memory accesses.
1224 using MemoryAccessVec
= SmallVector
<MemoryAccess
*, 8>;
1225 MemoryAccessVec MemAccs
;
1227 /// Mapping from instructions to (scalar) memory accesses.
1228 DenseMap
<const Instruction
*, MemoryAccessList
> InstructionToAccess
;
1230 /// The set of values defined elsewhere required in this ScopStmt and
1231 /// their MemoryKind::Value READ MemoryAccesses.
1232 DenseMap
<Value
*, MemoryAccess
*> ValueReads
;
1234 /// The set of values defined in this ScopStmt that are required
1235 /// elsewhere, mapped to their MemoryKind::Value WRITE MemoryAccesses.
1236 DenseMap
<Instruction
*, MemoryAccess
*> ValueWrites
;
1238 /// Map from PHI nodes to its incoming value when coming from this
1241 /// Non-affine subregions can have multiple exiting blocks that are incoming
1242 /// blocks of the PHI nodes. This map ensures that there is only one write
1243 /// operation for the complete subregion. A PHI selecting the relevant value
1244 /// will be inserted.
1245 DenseMap
<PHINode
*, MemoryAccess
*> PHIWrites
;
1247 /// Map from PHI nodes to its read access in this statement.
1248 DenseMap
<PHINode
*, MemoryAccess
*> PHIReads
;
1252 /// A SCoP statement represents either a basic block (affine/precise case) or
1253 /// a whole region (non-affine case).
1255 /// Only one of the following two members will therefore be set and indicate
1256 /// which kind of statement this is.
1260 /// The BasicBlock represented by this statement (in the affine case).
1261 BasicBlock
*BB
= nullptr;
1263 /// The region represented by this statement (in the non-affine case).
1264 Region
*R
= nullptr;
1268 /// The isl AST build for the new generated AST.
1269 isl::ast_build Build
;
1271 SmallVector
<Loop
*, 4> NestLoops
;
1273 std::string BaseName
;
1275 /// The closest loop that contains this statement.
1276 Loop
*SurroundingLoop
;
1278 /// Vector for Instructions in this statement.
1279 std::vector
<Instruction
*> Instructions
;
1281 /// Remove @p MA from dictionaries pointing to them.
1282 void removeAccessData(MemoryAccess
*MA
);
1285 /// Get an isl_ctx pointer.
1286 isl::ctx
getIslCtx() const;
1288 /// Get the iteration domain of this ScopStmt.
1290 /// @return The iteration domain of this ScopStmt.
1291 isl::set
getDomain() const;
1293 /// Get the space of the iteration domain
1295 /// @return The space of the iteration domain
1296 isl::space
getDomainSpace() const;
1298 /// Get the id of the iteration domain space
1300 /// @return The id of the iteration domain space
1301 isl::id
getDomainId() const;
1303 /// Get an isl string representing this domain.
1304 std::string
getDomainStr() const;
1306 /// Get the schedule function of this ScopStmt.
1308 /// @return The schedule function of this ScopStmt, if it does not contain
1309 /// extension nodes, and nullptr, otherwise.
1310 isl::map
getSchedule() const;
1312 /// Get an isl string representing this schedule.
1314 /// @return An isl string representing this schedule, if it does not contain
1315 /// extension nodes, and an empty string, otherwise.
1316 std::string
getScheduleStr() const;
1318 /// Get the invalid domain for this statement.
1319 isl::set
getInvalidDomain() const { return InvalidDomain
; }
1321 /// Get the invalid context for this statement.
1322 isl::set
getInvalidContext() const { return getInvalidDomain().params(); }
1324 /// Set the invalid context for this statement to @p ID.
1325 void setInvalidDomain(isl::set ID
);
1327 /// Get the BasicBlock represented by this ScopStmt (if any).
1329 /// @return The BasicBlock represented by this ScopStmt, or null if the
1330 /// statement represents a region.
1331 BasicBlock
*getBasicBlock() const { return BB
; }
1333 /// Return true if this statement represents a single basic block.
1334 bool isBlockStmt() const { return BB
!= nullptr; }
1336 /// Return true if this is a copy statement.
1337 bool isCopyStmt() const { return BB
== nullptr && R
== nullptr; }
1339 /// Get the region represented by this ScopStmt (if any).
1341 /// @return The region represented by this ScopStmt, or null if the statement
1342 /// represents a basic block.
1343 Region
*getRegion() const { return R
; }
1345 /// Return true if this statement represents a whole region.
1346 bool isRegionStmt() const { return R
!= nullptr; }
1348 /// Return a BasicBlock from this statement.
1350 /// For block statements, it returns the BasicBlock itself. For subregion
1351 /// statements, return its entry block.
1352 BasicBlock
*getEntryBlock() const;
1354 /// Return whether @p L is boxed within this statement.
1355 bool contains(const Loop
*L
) const {
1356 // Block statements never contain loops.
1360 return getRegion()->contains(L
);
1363 /// Return whether this statement represents @p BB.
1364 bool represents(BasicBlock
*BB
) const {
1368 return BB
== getBasicBlock();
1369 return getRegion()->contains(BB
);
1372 /// Return whether this statement contains @p Inst.
1373 bool contains(Instruction
*Inst
) const {
1377 return std::find(Instructions
.begin(), Instructions
.end(), Inst
) !=
1379 return represents(Inst
->getParent());
1382 /// Return the closest innermost loop that contains this statement, but is not
1383 /// contained in it.
1385 /// For block statement, this is just the loop that contains the block. Region
1386 /// statements can contain boxed loops, so getting the loop of one of the
1387 /// region's BBs might return such an inner loop. For instance, the region's
1388 /// entry could be a header of a loop, but the region might extend to BBs
1389 /// after the loop exit. Similarly, the region might only contain parts of the
1390 /// loop body and still include the loop header.
1392 /// Most of the time the surrounding loop is the top element of #NestLoops,
1393 /// except when it is empty. In that case it return the loop that the whole
1394 /// SCoP is contained in. That can be nullptr if there is no such loop.
1395 Loop
*getSurroundingLoop() const {
1396 assert(!isCopyStmt() &&
1397 "No surrounding loop for artificially created statements");
1398 return SurroundingLoop
;
1401 /// Return true if this statement does not contain any accesses.
1402 bool isEmpty() const { return MemAccs
.empty(); }
1404 /// Find all array accesses for @p Inst.
1406 /// @param Inst The instruction accessing an array.
1408 /// @return A list of array accesses (MemoryKind::Array) accessed by @p Inst.
1409 /// If there is no such access, it returns nullptr.
1410 const MemoryAccessList
*
1411 lookupArrayAccessesFor(const Instruction
*Inst
) const {
1412 auto It
= InstructionToAccess
.find(Inst
);
1413 if (It
== InstructionToAccess
.end())
1415 if (It
->second
.empty())
1420 /// Return the only array access for @p Inst, if existing.
1422 /// @param Inst The instruction for which to look up the access.
1423 /// @returns The unique array memory access related to Inst or nullptr if
1424 /// no array access exists
1425 MemoryAccess
*getArrayAccessOrNULLFor(const Instruction
*Inst
) const {
1426 auto It
= InstructionToAccess
.find(Inst
);
1427 if (It
== InstructionToAccess
.end())
1430 MemoryAccess
*ArrayAccess
= nullptr;
1432 for (auto Access
: It
->getSecond()) {
1433 if (!Access
->isArrayKind())
1436 assert(!ArrayAccess
&& "More then one array access for instruction");
1438 ArrayAccess
= Access
;
1444 /// Return the only array access for @p Inst.
1446 /// @param Inst The instruction for which to look up the access.
1447 /// @returns The unique array memory access related to Inst.
1448 MemoryAccess
&getArrayAccessFor(const Instruction
*Inst
) const {
1449 MemoryAccess
*ArrayAccess
= getArrayAccessOrNULLFor(Inst
);
1451 assert(ArrayAccess
&& "No array access found for instruction!");
1452 return *ArrayAccess
;
1455 /// Return the MemoryAccess that writes the value of an instruction
1456 /// defined in this statement, or nullptr if not existing, respectively
1458 MemoryAccess
*lookupValueWriteOf(Instruction
*Inst
) const {
1459 assert((isRegionStmt() && R
->contains(Inst
)) ||
1460 (!isRegionStmt() && Inst
->getParent() == BB
));
1461 return ValueWrites
.lookup(Inst
);
1464 /// Return the MemoryAccess that reloads a value, or nullptr if not
1465 /// existing, respectively not yet added.
1466 MemoryAccess
*lookupValueReadOf(Value
*Inst
) const {
1467 return ValueReads
.lookup(Inst
);
1470 /// Return the MemoryAccess that loads a PHINode value, or nullptr if not
1471 /// existing, respectively not yet added.
1472 MemoryAccess
*lookupPHIReadOf(PHINode
*PHI
) const {
1473 return PHIReads
.lookup(PHI
);
1476 /// Return the PHI write MemoryAccess for the incoming values from any
1477 /// basic block in this ScopStmt, or nullptr if not existing,
1478 /// respectively not yet added.
1479 MemoryAccess
*lookupPHIWriteOf(PHINode
*PHI
) const {
1480 assert(isBlockStmt() || R
->getExit() == PHI
->getParent());
1481 return PHIWrites
.lookup(PHI
);
1484 /// Return the input access of the value, or null if no such MemoryAccess
1487 /// The input access is the MemoryAccess that makes an inter-statement value
1488 /// available in this statement by reading it at the start of this statement.
1489 /// This can be a MemoryKind::Value if defined in another statement or a
1490 /// MemoryKind::PHI if the value is a PHINode in this statement.
1491 MemoryAccess
*lookupInputAccessOf(Value
*Val
) const {
1492 if (isa
<PHINode
>(Val
))
1493 if (auto InputMA
= lookupPHIReadOf(cast
<PHINode
>(Val
))) {
1494 assert(!lookupValueReadOf(Val
) && "input accesses must be unique; a "
1495 "statement cannot read a .s2a and "
1496 ".phiops simultaneously");
1500 if (auto *InputMA
= lookupValueReadOf(Val
))
1506 /// Add @p Access to this statement's list of accesses.
1508 /// @param Access The access to add.
1509 /// @param Prepend If true, will add @p Access before all other instructions
1510 /// (instead of appending it).
1511 void addAccess(MemoryAccess
*Access
, bool Preprend
= false);
1513 /// Remove a MemoryAccess from this statement.
1515 /// Note that scalar accesses that are caused by MA will
1516 /// be eliminated too.
1517 void removeMemoryAccess(MemoryAccess
*MA
);
1519 /// Remove @p MA from this statement.
1521 /// In contrast to removeMemoryAccess(), no other access will be eliminated.
1523 /// @param MA The MemoryAccess to be removed.
1524 /// @param AfterHoisting If true, also remove from data access lists.
1525 /// These lists are filled during
1526 /// ScopBuilder::buildAccessRelations. Therefore, if this
1527 /// method is called before buildAccessRelations, false
1529 void removeSingleMemoryAccess(MemoryAccess
*MA
, bool AfterHoisting
= true);
1531 using iterator
= MemoryAccessVec::iterator
;
1532 using const_iterator
= MemoryAccessVec::const_iterator
;
1534 iterator
begin() { return MemAccs
.begin(); }
1535 iterator
end() { return MemAccs
.end(); }
1536 const_iterator
begin() const { return MemAccs
.begin(); }
1537 const_iterator
end() const { return MemAccs
.end(); }
1538 size_t size() const { return MemAccs
.size(); }
1540 unsigned getNumIterators() const;
1542 Scop
*getParent() { return &Parent
; }
1543 const Scop
*getParent() const { return &Parent
; }
1545 const std::vector
<Instruction
*> &getInstructions() const {
1546 return Instructions
;
1549 /// Set the list of instructions for this statement. It replaces the current
1551 void setInstructions(ArrayRef
<Instruction
*> Range
) {
1552 Instructions
.assign(Range
.begin(), Range
.end());
1555 std::vector
<Instruction
*>::const_iterator
insts_begin() const {
1556 return Instructions
.begin();
1559 std::vector
<Instruction
*>::const_iterator
insts_end() const {
1560 return Instructions
.end();
1563 /// The range of instructions in this statement.
1564 iterator_range
<std::vector
<Instruction
*>::const_iterator
> insts() const {
1565 return {insts_begin(), insts_end()};
1568 /// Insert an instruction before all other instructions in this statement.
1569 void prependInstruction(Instruction
*Inst
) {
1570 Instructions
.insert(Instructions
.begin(), Inst
);
1573 const char *getBaseName() const;
1575 /// Set the isl AST build.
1576 void setAstBuild(isl::ast_build B
) { Build
= B
; }
1578 /// Get the isl AST build.
1579 isl::ast_build
getAstBuild() const { return Build
; }
1581 /// Restrict the domain of the statement.
1583 /// @param NewDomain The new statement domain.
1584 void restrictDomain(isl::set NewDomain
);
1586 /// Get the loop for a dimension.
1588 /// @param Dimension The dimension of the induction variable
1589 /// @return The loop at a certain dimension.
1590 Loop
*getLoopForDimension(unsigned Dimension
) const;
1592 /// Align the parameters in the statement to the scop context
1593 void realignParams();
1595 /// Print the ScopStmt.
1597 /// @param OS The output stream the ScopStmt is printed to.
1598 /// @param PrintInstructions Whether to print the statement's instructions as
1600 void print(raw_ostream
&OS
, bool PrintInstructions
) const;
1602 /// Print the instructions in ScopStmt.
1604 void printInstructions(raw_ostream
&OS
) const;
1606 /// Check whether there is a value read access for @p V in this statement, and
1607 /// if not, create one.
1609 /// This allows to add MemoryAccesses after the initial creation of the Scop
1612 /// @return The already existing or newly created MemoryKind::Value READ
1615 /// @see ScopBuilder::ensureValueRead(Value*,ScopStmt*)
1616 MemoryAccess
*ensureValueRead(Value
*V
);
1618 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1619 /// Print the ScopStmt to stderr.
1624 /// Print ScopStmt S to raw_ostream OS.
1625 raw_ostream
&operator<<(raw_ostream
&OS
, const ScopStmt
&S
);
1627 /// Helper struct to remember assumptions.
1629 /// The kind of the assumption (e.g., WRAPPING).
1630 AssumptionKind Kind
;
1632 /// Flag to distinguish assumptions and restrictions.
1633 AssumptionSign Sign
;
1635 /// The valid/invalid context if this is an assumption/restriction.
1638 /// The location that caused this assumption.
1641 /// An optional block whose domain can simplify the assumption.
1645 /// Build the conditions sets for the branch condition @p Condition in
1648 /// This will fill @p ConditionSets with the conditions under which control
1649 /// will be moved from @p TI to its successors. Hence, @p ConditionSets will
1650 /// have as many elements as @p TI has successors. If @p TI is nullptr the
1651 /// context under which @p Condition is true/false will be returned as the
1652 /// new elements of @p ConditionSets.
1653 bool buildConditionSets(Scop
&S
, BasicBlock
*BB
, Value
*Condition
,
1654 Instruction
*TI
, Loop
*L
, __isl_keep isl_set
*Domain
,
1655 DenseMap
<BasicBlock
*, isl::set
> &InvalidDomainMap
,
1656 SmallVectorImpl
<__isl_give isl_set
*> &ConditionSets
);
1658 /// Build condition sets for unsigned ICmpInst(s).
1659 /// Special handling is required for unsigned operands to ensure that if
1660 /// MSB (aka the Sign bit) is set for an operands in an unsigned ICmpInst
1661 /// it should wrap around.
1663 /// @param IsStrictUpperBound holds information on the predicate relation
1664 /// between TestVal and UpperBound, i.e,
1665 /// TestVal < UpperBound OR TestVal <= UpperBound
1666 __isl_give isl_set
*
1667 buildUnsignedConditionSets(Scop
&S
, BasicBlock
*BB
, Value
*Condition
,
1668 __isl_keep isl_set
*Domain
, const SCEV
*SCEV_TestVal
,
1669 const SCEV
*SCEV_UpperBound
,
1670 DenseMap
<BasicBlock
*, isl::set
> &InvalidDomainMap
,
1671 bool IsStrictUpperBound
);
1673 /// Build the conditions sets for the terminator @p TI in the @p Domain.
1675 /// This will fill @p ConditionSets with the conditions under which control
1676 /// will be moved from @p TI to its successors. Hence, @p ConditionSets will
1677 /// have as many elements as @p TI has successors.
1678 bool buildConditionSets(Scop
&S
, BasicBlock
*BB
, Instruction
*TI
, Loop
*L
,
1679 __isl_keep isl_set
*Domain
,
1680 DenseMap
<BasicBlock
*, isl::set
> &InvalidDomainMap
,
1681 SmallVectorImpl
<__isl_give isl_set
*> &ConditionSets
);
1683 /// Static Control Part
1685 /// A Scop is the polyhedral representation of a control flow region detected
1686 /// by the Scop detection. It is generated by translating the LLVM-IR and
1687 /// abstracting its effects.
1689 /// A Scop consists of a set of:
1691 /// * A set of statements executed in the Scop.
1693 /// * A set of global parameters
1694 /// Those parameters are scalar integer values, which are constant during
1698 /// This context contains information about the values the parameters
1699 /// can take and relations between different parameters.
1702 /// Type to represent a pair of minimal/maximal access to an array.
1703 using MinMaxAccessTy
= std::pair
<isl::pw_multi_aff
, isl::pw_multi_aff
>;
1705 /// Vector of minimal/maximal accesses to different arrays.
1706 using MinMaxVectorTy
= SmallVector
<MinMaxAccessTy
, 4>;
1708 /// Pair of minimal/maximal access vectors representing
1709 /// read write and read only accesses
1710 using MinMaxVectorPairTy
= std::pair
<MinMaxVectorTy
, MinMaxVectorTy
>;
1712 /// Vector of pair of minimal/maximal access vectors representing
1713 /// non read only and read only accesses for each alias group.
1714 using MinMaxVectorPairVectorTy
= SmallVector
<MinMaxVectorPairTy
, 4>;
1717 friend class ScopBuilder
;
1721 /// We need a shared_ptr with reference counter to delete the context when all
1722 /// isl objects are deleted. We will distribute the shared_ptr to all objects
1723 /// that use the context to create isl objects, and increase the reference
1724 /// counter. By doing this, we guarantee that the context is deleted when we
1725 /// delete the last object that creates isl objects with the context. This
1726 /// declaration needs to be the first in class to gracefully destroy all isl
1727 /// objects before the context.
1728 std::shared_ptr
<isl_ctx
> IslCtx
;
1730 ScalarEvolution
*SE
;
1733 /// The underlying Region.
1736 /// The name of the SCoP (identical to the regions name)
1737 Optional
<std::string
> name
;
1739 /// The ID to be assigned to the next Scop in a function
1740 static int NextScopID
;
1742 /// The name of the function currently under consideration
1743 static std::string CurrentFunc
;
1745 // Access functions of the SCoP.
1747 // This owns all the MemoryAccess objects of the Scop created in this pass.
1748 AccFuncVector AccessFunctions
;
1750 /// Flag to indicate that the scheduler actually optimized the SCoP.
1751 bool IsOptimized
= false;
1753 /// True if the underlying region has a single exiting block.
1754 bool HasSingleExitEdge
;
1756 /// Flag to remember if the SCoP contained an error block or not.
1757 bool HasErrorBlock
= false;
1760 unsigned MaxLoopDepth
= 0;
1762 /// Number of copy statements.
1763 unsigned CopyStmtsNum
= 0;
1765 /// Flag to indicate if the Scop is to be skipped.
1766 bool SkipScop
= false;
1768 using StmtSet
= std::list
<ScopStmt
>;
1770 /// The statements in this Scop.
1773 /// Parameters of this Scop
1774 ParameterSetTy Parameters
;
1776 /// Mapping from parameters to their ids.
1777 DenseMap
<const SCEV
*, isl::id
> ParameterIds
;
1779 /// The context of the SCoP created during SCoP detection.
1780 ScopDetection::DetectionContext
&DC
;
1782 /// OptimizationRemarkEmitter object for displaying diagnostic remarks
1783 OptimizationRemarkEmitter
&ORE
;
1785 /// A map from basic blocks to vector of SCoP statements. Currently this
1786 /// vector comprises only of a single statement.
1787 DenseMap
<BasicBlock
*, std::vector
<ScopStmt
*>> StmtMap
;
1789 /// A map from instructions to SCoP statements.
1790 DenseMap
<Instruction
*, ScopStmt
*> InstStmtMap
;
1792 /// A map from basic blocks to their domains.
1793 DenseMap
<BasicBlock
*, isl::set
> DomainMap
;
1795 /// Constraints on parameters.
1796 isl::set Context
= nullptr;
1798 /// The affinator used to translate SCEVs to isl expressions.
1799 SCEVAffinator Affinator
;
1801 using ArrayInfoMapTy
=
1802 std::map
<std::pair
<AssertingVH
<const Value
>, MemoryKind
>,
1803 std::unique_ptr
<ScopArrayInfo
>>;
1805 using ArrayNameMapTy
= StringMap
<std::unique_ptr
<ScopArrayInfo
>>;
1807 using ArrayInfoSetTy
= SetVector
<ScopArrayInfo
*>;
1809 /// A map to remember ScopArrayInfo objects for all base pointers.
1811 /// As PHI nodes may have two array info objects associated, we add a flag
1812 /// that distinguishes between the PHI node specific ArrayInfo object
1813 /// and the normal one.
1814 ArrayInfoMapTy ScopArrayInfoMap
;
1816 /// A map to remember ScopArrayInfo objects for all names of memory
1818 ArrayNameMapTy ScopArrayNameMap
;
1820 /// A set to remember ScopArrayInfo objects.
1821 /// @see Scop::ScopArrayInfoMap
1822 ArrayInfoSetTy ScopArrayInfoSet
;
1824 /// The assumptions under which this scop was built.
1826 /// When constructing a scop sometimes the exact representation of a statement
1827 /// or condition would be very complex, but there is a common case which is a
1828 /// lot simpler, but which is only valid under certain assumptions. The
1829 /// assumed context records the assumptions taken during the construction of
1830 /// this scop and that need to be code generated as a run-time test.
1831 isl::set AssumedContext
;
1833 /// The restrictions under which this SCoP was built.
1835 /// The invalid context is similar to the assumed context as it contains
1836 /// constraints over the parameters. However, while we need the constraints
1837 /// in the assumed context to be "true" the constraints in the invalid context
1838 /// need to be "false". Otherwise they behave the same.
1839 isl::set InvalidContext
;
1841 using RecordedAssumptionsTy
= SmallVector
<Assumption
, 8>;
1842 /// Collection to hold taken assumptions.
1844 /// There are two reasons why we want to record assumptions first before we
1845 /// add them to the assumed/invalid context:
1846 /// 1) If the SCoP is not profitable or otherwise invalid without the
1847 /// assumed/invalid context we do not have to compute it.
1848 /// 2) Information about the context are gathered rather late in the SCoP
1849 /// construction (basically after we know all parameters), thus the user
1850 /// might see overly complicated assumptions to be taken while they will
1851 /// only be simplified later on.
1852 RecordedAssumptionsTy RecordedAssumptions
;
1854 /// The schedule of the SCoP
1856 /// The schedule of the SCoP describes the execution order of the statements
1857 /// in the scop by assigning each statement instance a possibly
1858 /// multi-dimensional execution time. The schedule is stored as a tree of
1861 /// The most common nodes in a schedule tree are so-called band nodes. Band
1862 /// nodes map statement instances into a multi dimensional schedule space.
1863 /// This space can be seen as a multi-dimensional clock.
1867 /// <S,(5,4)> may be mapped to (5,4) by this schedule:
1869 /// s0 = i (Year of execution)
1870 /// s1 = j (Day of execution)
1872 /// or to (9, 20) by this schedule:
1874 /// s0 = i + j (Year of execution)
1875 /// s1 = 20 (Day of execution)
1877 /// The order statement instances are executed is defined by the
1878 /// schedule vectors they are mapped to. A statement instance
1879 /// <A, (i, j, ..)> is executed before a statement instance <B, (i', ..)>, if
1880 /// the schedule vector of A is lexicographic smaller than the schedule
1883 /// Besides band nodes, schedule trees contain additional nodes that specify
1884 /// a textual ordering between two subtrees or filter nodes that filter the
1885 /// set of statement instances that will be scheduled in a subtree. There
1886 /// are also several other nodes. A full description of the different nodes
1887 /// in a schedule tree is given in the isl manual.
1888 isl::schedule Schedule
= nullptr;
1890 /// Whether the schedule has been modified after derived from the CFG by
1892 bool ScheduleModified
= false;
1894 /// The set of minimal/maximal accesses for each alias group.
1896 /// When building runtime alias checks we look at all memory instructions and
1897 /// build so called alias groups. Each group contains a set of accesses to
1898 /// different base arrays which might alias with each other. However, between
1899 /// alias groups there is no aliasing possible.
1901 /// In a program with int and float pointers annotated with tbaa information
1902 /// we would probably generate two alias groups, one for the int pointers and
1903 /// one for the float pointers.
1905 /// During code generation we will create a runtime alias check for each alias
1906 /// group to ensure the SCoP is executed in an alias free environment.
1907 MinMaxVectorPairVectorTy MinMaxAliasGroups
;
1909 /// Mapping from invariant loads to the representing invariant load of
1910 /// their equivalence class.
1911 ValueToValueMap InvEquivClassVMap
;
1913 /// List of invariant accesses.
1914 InvariantEquivClassesTy InvariantEquivClasses
;
1916 /// The smallest array index not yet assigned.
1919 /// The smallest statement index not yet assigned.
1922 /// A number that uniquely represents a Scop within its function
1925 /// Map of values to the MemoryAccess that writes its definition.
1927 /// There must be at most one definition per llvm::Instruction in a SCoP.
1928 DenseMap
<Value
*, MemoryAccess
*> ValueDefAccs
;
1930 /// Map of values to the MemoryAccess that reads a PHI.
1931 DenseMap
<PHINode
*, MemoryAccess
*> PHIReadAccs
;
1933 /// List of all uses (i.e. read MemoryAccesses) for a MemoryKind::Value
1935 DenseMap
<const ScopArrayInfo
*, SmallVector
<MemoryAccess
*, 4>> ValueUseAccs
;
1937 /// List of all incoming values (write MemoryAccess) of a MemoryKind::PHI or
1938 /// MemoryKind::ExitPHI scalar.
1939 DenseMap
<const ScopArrayInfo
*, SmallVector
<MemoryAccess
*, 4>>
1942 /// Return the ID for a new Scop within a function
1943 static int getNextID(std::string ParentFunc
);
1945 /// Scop constructor; invoked from ScopBuilder::buildScop.
1946 Scop(Region
&R
, ScalarEvolution
&SE
, LoopInfo
&LI
, DominatorTree
&DT
,
1947 ScopDetection::DetectionContext
&DC
, OptimizationRemarkEmitter
&ORE
);
1951 /// Initialize this ScopBuilder.
1952 void init(AliasAnalysis
&AA
, AssumptionCache
&AC
, DominatorTree
&DT
,
1955 /// Add parameter constraints to @p C that imply a non-empty domain.
1956 isl::set
addNonEmptyDomainConstraints(isl::set C
) const;
1958 /// Return the access for the base ptr of @p MA if any.
1959 MemoryAccess
*lookupBasePtrAccess(MemoryAccess
*MA
);
1961 /// Create an id for @p Param and store it in the ParameterIds map.
1962 void createParameterId(const SCEV
*Param
);
1964 /// Build the Context of the Scop.
1965 void buildContext();
1967 /// Add the bounds of the parameters to the context.
1968 void addParameterBounds();
1970 /// Simplify the assumed and invalid context.
1971 void simplifyContexts();
1973 /// Create a new SCoP statement for @p BB.
1975 /// A new statement for @p BB will be created and added to the statement
1979 /// @param BB The basic block we build the statement for.
1980 /// @param Name The name of the new statement.
1981 /// @param SurroundingLoop The loop the created statement is contained in.
1982 /// @param Instructions The instructions in the statement.
1983 void addScopStmt(BasicBlock
*BB
, StringRef Name
, Loop
*SurroundingLoop
,
1984 std::vector
<Instruction
*> Instructions
);
1986 /// Create a new SCoP statement for @p R.
1988 /// A new statement for @p R will be created and added to the statement vector
1991 /// @param R The region we build the statement for.
1992 /// @param Name The name of the new statement.
1993 /// @param SurroundingLoop The loop the created statement is contained
1995 /// @param EntryBlockInstructions The (interesting) instructions in the
1996 /// entry block of the region statement.
1997 void addScopStmt(Region
*R
, StringRef Name
, Loop
*SurroundingLoop
,
1998 std::vector
<Instruction
*> EntryBlockInstructions
);
2000 /// Remove statements from the list of scop statements.
2002 /// @param ShouldDelete A function that returns true if the statement passed
2003 /// to it should be deleted.
2004 /// @param AfterHoisting If true, also remove from data access lists.
2005 /// These lists are filled during
2006 /// ScopBuilder::buildAccessRelations. Therefore, if this
2007 /// method is called before buildAccessRelations, false
2009 void removeStmts(std::function
<bool(ScopStmt
&)> ShouldDelete
,
2010 bool AfterHoisting
= true);
2012 /// Removes @p Stmt from the StmtMap.
2013 void removeFromStmtMap(ScopStmt
&Stmt
);
2015 /// Removes all statements where the entry block of the statement does not
2016 /// have a corresponding domain in the domain map (or it is empty).
2017 void removeStmtNotInDomainMap();
2019 /// Collect all memory access relations of a given type.
2021 /// @param Predicate A predicate function that returns true if an access is
2022 /// of a given type.
2024 /// @returns The set of memory accesses in the scop that match the predicate.
2026 getAccessesOfType(std::function
<bool(MemoryAccess
&)> Predicate
);
2028 /// @name Helper functions for printing the Scop.
2031 void printContext(raw_ostream
&OS
) const;
2032 void printArrayInfo(raw_ostream
&OS
) const;
2033 void printStatements(raw_ostream
&OS
, bool PrintInstructions
) const;
2034 void printAliasAssumptions(raw_ostream
&OS
) const;
2038 Scop(const Scop
&) = delete;
2039 Scop
&operator=(const Scop
&) = delete;
2042 /// Increment actual number of aliasing assumptions taken
2044 /// @param Step Number of new aliasing assumptions which should be added to
2045 /// the number of already taken assumptions.
2046 static void incrementNumberOfAliasingAssumptions(unsigned Step
);
2048 /// Get the count of copy statements added to this Scop.
2050 /// @return The count of copy statements added to this Scop.
2051 unsigned getCopyStmtsNum() { return CopyStmtsNum
; }
2053 /// Create a new copy statement.
2055 /// A new statement will be created and added to the statement vector.
2057 /// @param Stmt The parent statement.
2058 /// @param SourceRel The source location.
2059 /// @param TargetRel The target location.
2060 /// @param Domain The original domain under which the copy statement would
2062 ScopStmt
*addScopStmt(isl::map SourceRel
, isl::map TargetRel
,
2065 /// Add the access function to all MemoryAccess objects of the Scop
2066 /// created in this pass.
2067 void addAccessFunction(MemoryAccess
*Access
) {
2068 AccessFunctions
.emplace_back(Access
);
2070 // Register value definitions.
2071 if (Access
->isWrite() && Access
->isOriginalValueKind()) {
2072 assert(!ValueDefAccs
.count(Access
->getAccessValue()) &&
2073 "there can be just one definition per value");
2074 ValueDefAccs
[Access
->getAccessValue()] = Access
;
2075 } else if (Access
->isRead() && Access
->isOriginalPHIKind()) {
2076 PHINode
*PHI
= cast
<PHINode
>(Access
->getAccessInstruction());
2077 assert(!PHIReadAccs
.count(PHI
) &&
2078 "there can be just one PHI read per PHINode");
2079 PHIReadAccs
[PHI
] = Access
;
2083 /// Add metadata for @p Access.
2084 void addAccessData(MemoryAccess
*Access
);
2086 /// Add new invariant access equivalence class
2088 addInvariantEquivClass(const InvariantEquivClassTy
&InvariantEquivClass
) {
2089 InvariantEquivClasses
.emplace_back(InvariantEquivClass
);
2092 /// Add mapping from invariant loads to the representing invariant load of
2093 /// their equivalence class.
2094 void addInvariantLoadMapping(const Value
*LoadInst
, Value
*ClassRep
) {
2095 InvEquivClassVMap
[LoadInst
] = ClassRep
;
2098 /// Remove the metadata stored for @p Access.
2099 void removeAccessData(MemoryAccess
*Access
);
2101 /// Return the scalar evolution.
2102 ScalarEvolution
*getSE() const;
2104 /// Return the dominator tree.
2105 DominatorTree
*getDT() const { return DT
; }
2107 /// Return the LoopInfo used for this Scop.
2108 LoopInfo
*getLI() const { return Affinator
.getLI(); }
2110 /// Get the count of parameters used in this Scop.
2112 /// @return The count of parameters used in this Scop.
2113 size_t getNumParams() const { return Parameters
.size(); }
2115 /// Return whether given SCEV is used as the parameter in this Scop.
2116 bool isParam(const SCEV
*Param
) const { return Parameters
.count(Param
); }
2118 /// Take a list of parameters and add the new ones to the scop.
2119 void addParams(const ParameterSetTy
&NewParameters
);
2121 /// Return an iterator range containing the scop parameters.
2122 iterator_range
<ParameterSetTy::iterator
> parameters() const {
2123 return make_range(Parameters
.begin(), Parameters
.end());
2126 /// Return an iterator range containing invariant accesses.
2127 iterator_range
<InvariantEquivClassesTy::iterator
> invariantEquivClasses() {
2128 return make_range(InvariantEquivClasses
.begin(),
2129 InvariantEquivClasses
.end());
2132 /// Return an iterator range containing hold assumptions.
2133 iterator_range
<RecordedAssumptionsTy::const_iterator
>
2134 recorded_assumptions() const {
2135 return make_range(RecordedAssumptions
.begin(), RecordedAssumptions
.end());
2138 /// Return an iterator range containing all the MemoryAccess objects of the
2140 iterator_range
<AccFuncVector::iterator
> access_functions() {
2141 return make_range(AccessFunctions
.begin(), AccessFunctions
.end());
2144 /// Return whether this scop is empty, i.e. contains no statements that
2145 /// could be executed.
2146 bool isEmpty() const { return Stmts
.empty(); }
2148 StringRef
getName() {
2150 name
= R
.getNameStr();
2154 using array_iterator
= ArrayInfoSetTy::iterator
;
2155 using const_array_iterator
= ArrayInfoSetTy::const_iterator
;
2156 using array_range
= iterator_range
<ArrayInfoSetTy::iterator
>;
2157 using const_array_range
= iterator_range
<ArrayInfoSetTy::const_iterator
>;
2159 inline array_iterator
array_begin() { return ScopArrayInfoSet
.begin(); }
2161 inline array_iterator
array_end() { return ScopArrayInfoSet
.end(); }
2163 inline const_array_iterator
array_begin() const {
2164 return ScopArrayInfoSet
.begin();
2167 inline const_array_iterator
array_end() const {
2168 return ScopArrayInfoSet
.end();
2171 inline array_range
arrays() {
2172 return array_range(array_begin(), array_end());
2175 inline const_array_range
arrays() const {
2176 return const_array_range(array_begin(), array_end());
2179 /// Return the isl_id that represents a certain parameter.
2181 /// @param Parameter A SCEV that was recognized as a Parameter.
2183 /// @return The corresponding isl_id or NULL otherwise.
2184 isl::id
getIdForParam(const SCEV
*Parameter
) const;
2186 /// Get the maximum region of this static control part.
2188 /// @return The maximum region of this static control part.
2189 inline const Region
&getRegion() const { return R
; }
2190 inline Region
&getRegion() { return R
; }
2192 /// Return the function this SCoP is in.
2193 Function
&getFunction() const { return *R
.getEntry()->getParent(); }
2195 /// Check if @p L is contained in the SCoP.
2196 bool contains(const Loop
*L
) const { return R
.contains(L
); }
2198 /// Check if @p BB is contained in the SCoP.
2199 bool contains(const BasicBlock
*BB
) const { return R
.contains(BB
); }
2201 /// Check if @p I is contained in the SCoP.
2202 bool contains(const Instruction
*I
) const { return R
.contains(I
); }
2204 /// Return the unique exit block of the SCoP.
2205 BasicBlock
*getExit() const { return R
.getExit(); }
2207 /// Return the unique exiting block of the SCoP if any.
2208 BasicBlock
*getExitingBlock() const { return R
.getExitingBlock(); }
2210 /// Return the unique entry block of the SCoP.
2211 BasicBlock
*getEntry() const { return R
.getEntry(); }
2213 /// Return the unique entering block of the SCoP if any.
2214 BasicBlock
*getEnteringBlock() const { return R
.getEnteringBlock(); }
2216 /// Return true if @p BB is the exit block of the SCoP.
2217 bool isExit(BasicBlock
*BB
) const { return getExit() == BB
; }
2219 /// Return a range of all basic blocks in the SCoP.
2220 Region::block_range
blocks() const { return R
.blocks(); }
2222 /// Return true if and only if @p BB dominates the SCoP.
2223 bool isDominatedBy(const DominatorTree
&DT
, BasicBlock
*BB
) const;
2225 /// Get the maximum depth of the loop.
2227 /// @return The maximum depth of the loop.
2228 inline unsigned getMaxLoopDepth() const { return MaxLoopDepth
; }
2230 /// Return the invariant equivalence class for @p Val if any.
2231 InvariantEquivClassTy
*lookupInvariantEquivClass(Value
*Val
);
2233 /// Return the set of invariant accesses.
2234 InvariantEquivClassesTy
&getInvariantAccesses() {
2235 return InvariantEquivClasses
;
2238 /// Check if the scop has any invariant access.
2239 bool hasInvariantAccesses() { return !InvariantEquivClasses
.empty(); }
2241 /// Mark the SCoP as optimized by the scheduler.
2242 void markAsOptimized() { IsOptimized
= true; }
2244 /// Check if the SCoP has been optimized by the scheduler.
2245 bool isOptimized() const { return IsOptimized
; }
2247 /// Mark the SCoP to be skipped by ScopPass passes.
2248 void markAsToBeSkipped() { SkipScop
= true; }
2250 /// Check if the SCoP is to be skipped by ScopPass passes.
2251 bool isToBeSkipped() const { return SkipScop
; }
2253 /// Return the ID of the Scop
2254 int getID() const { return ID
; }
2256 /// Get the name of the entry and exit blocks of this Scop.
2258 /// These along with the function name can uniquely identify a Scop.
2260 /// @return std::pair whose first element is the entry name & second element
2261 /// is the exit name.
2262 std::pair
<std::string
, std::string
> getEntryExitStr() const;
2264 /// Get the name of this Scop.
2265 std::string
getNameStr() const;
2267 /// Get the constraint on parameter of this Scop.
2269 /// @return The constraint on parameter of this Scop.
2270 isl::set
getContext() const;
2272 /// Return space of isl context parameters.
2274 /// Returns the set of context parameters that are currently constrained. In
2275 /// case the full set of parameters is needed, see @getFullParamSpace.
2276 isl::space
getParamSpace() const;
2278 /// Return the full space of parameters.
2280 /// getParamSpace will only return the parameters of the context that are
2281 /// actually constrained, whereas getFullParamSpace will return all
2282 // parameters. This is useful in cases, where we need to ensure all
2283 // parameters are available, as certain isl functions will abort if this is
2285 isl::space
getFullParamSpace() const;
2287 /// Get the assumed context for this Scop.
2289 /// @return The assumed context of this Scop.
2290 isl::set
getAssumedContext() const;
2292 /// Return true if the optimized SCoP can be executed.
2294 /// In addition to the runtime check context this will also utilize the domain
2295 /// constraints to decide it the optimized version can actually be executed.
2297 /// @returns True if the optimized SCoP can be executed.
2298 bool hasFeasibleRuntimeContext() const;
2300 /// Clear assumptions which have been already processed.
2301 void clearRecordedAssumptions() { return RecordedAssumptions
.clear(); }
2303 /// Check if the assumption in @p Set is trivial or not.
2305 /// @param Set The relations between parameters that are assumed to hold.
2306 /// @param Sign Enum to indicate if the assumptions in @p Set are positive
2307 /// (needed/assumptions) or negative (invalid/restrictions).
2309 /// @returns True if the assumption @p Set is not trivial.
2310 bool isEffectiveAssumption(isl::set Set
, AssumptionSign Sign
);
2312 /// Track and report an assumption.
2314 /// Use 'clang -Rpass-analysis=polly-scops' or 'opt
2315 /// -pass-remarks-analysis=polly-scops' to output the assumptions.
2317 /// @param Kind The assumption kind describing the underlying cause.
2318 /// @param Set The relations between parameters that are assumed to hold.
2319 /// @param Loc The location in the source that caused this assumption.
2320 /// @param Sign Enum to indicate if the assumptions in @p Set are positive
2321 /// (needed/assumptions) or negative (invalid/restrictions).
2322 /// @param BB The block in which this assumption was taken. Used to
2323 /// calculate hotness when emitting remark.
2325 /// @returns True if the assumption is not trivial.
2326 bool trackAssumption(AssumptionKind Kind
, isl::set Set
, DebugLoc Loc
,
2327 AssumptionSign Sign
, BasicBlock
*BB
);
2329 /// Add assumptions to assumed context.
2331 /// The assumptions added will be assumed to hold during the execution of the
2332 /// scop. However, as they are generally not statically provable, at code
2333 /// generation time run-time checks will be generated that ensure the
2334 /// assumptions hold.
2336 /// WARNING: We currently exploit in simplifyAssumedContext the knowledge
2337 /// that assumptions do not change the set of statement instances
2340 /// @param Kind The assumption kind describing the underlying cause.
2341 /// @param Set The relations between parameters that are assumed to hold.
2342 /// @param Loc The location in the source that caused this assumption.
2343 /// @param Sign Enum to indicate if the assumptions in @p Set are positive
2344 /// (needed/assumptions) or negative (invalid/restrictions).
2345 /// @param BB The block in which this assumption was taken. Used to
2346 /// calculate hotness when emitting remark.
2347 void addAssumption(AssumptionKind Kind
, isl::set Set
, DebugLoc Loc
,
2348 AssumptionSign Sign
, BasicBlock
*BB
);
2350 /// Record an assumption for later addition to the assumed context.
2352 /// This function will add the assumption to the RecordedAssumptions. This
2353 /// collection will be added (@see addAssumption) to the assumed context once
2354 /// all paramaters are known and the context is fully built.
2356 /// @param Kind The assumption kind describing the underlying cause.
2357 /// @param Set The relations between parameters that are assumed to hold.
2358 /// @param Loc The location in the source that caused this assumption.
2359 /// @param Sign Enum to indicate if the assumptions in @p Set are positive
2360 /// (needed/assumptions) or negative (invalid/restrictions).
2361 /// @param BB The block in which this assumption was taken. If it is
2362 /// set, the domain of that block will be used to simplify the
2363 /// actual assumption in @p Set once it is added. This is useful
2364 /// if the assumption was created prior to the domain.
2365 void recordAssumption(AssumptionKind Kind
, isl::set Set
, DebugLoc Loc
,
2366 AssumptionSign Sign
, BasicBlock
*BB
= nullptr);
2368 /// Mark the scop as invalid.
2370 /// This method adds an assumption to the scop that is always invalid. As a
2371 /// result, the scop will not be optimized later on. This function is commonly
2372 /// called when a condition makes it impossible (or too compile time
2373 /// expensive) to process this scop any further.
2375 /// @param Kind The assumption kind describing the underlying cause.
2376 /// @param Loc The location in the source that triggered .
2377 /// @param BB The BasicBlock where it was triggered.
2378 void invalidate(AssumptionKind Kind
, DebugLoc Loc
, BasicBlock
*BB
= nullptr);
2380 /// Get the invalid context for this Scop.
2382 /// @return The invalid context of this Scop.
2383 isl::set
getInvalidContext() const;
2385 /// Return true if and only if the InvalidContext is trivial (=empty).
2386 bool hasTrivialInvalidContext() const { return InvalidContext
.is_empty(); }
2388 /// Return all alias groups for this SCoP.
2389 const MinMaxVectorPairVectorTy
&getAliasGroups() const {
2390 return MinMaxAliasGroups
;
2393 void addAliasGroup(MinMaxVectorTy
&MinMaxAccessesReadWrite
,
2394 MinMaxVectorTy
&MinMaxAccessesReadOnly
) {
2395 MinMaxAliasGroups
.emplace_back();
2396 MinMaxAliasGroups
.back().first
= MinMaxAccessesReadWrite
;
2397 MinMaxAliasGroups
.back().second
= MinMaxAccessesReadOnly
;
2399 /// Get an isl string representing the context.
2400 std::string
getContextStr() const;
2402 /// Get an isl string representing the assumed context.
2403 std::string
getAssumedContextStr() const;
2405 /// Get an isl string representing the invalid context.
2406 std::string
getInvalidContextStr() const;
2408 /// Return the list of ScopStmts that represent the given @p BB.
2409 ArrayRef
<ScopStmt
*> getStmtListFor(BasicBlock
*BB
) const;
2411 /// Get the statement to put a PHI WRITE into.
2413 /// @param U The operand of a PHINode.
2414 ScopStmt
*getIncomingStmtFor(const Use
&U
) const;
2416 /// Return the last statement representing @p BB.
2418 /// Of the sequence of statements that represent a @p BB, this is the last one
2419 /// to be executed. It is typically used to determine which instruction to add
2420 /// a MemoryKind::PHI WRITE to. For this purpose, it is not strictly required
2421 /// to be executed last, only that the incoming value is available in it.
2422 ScopStmt
*getLastStmtFor(BasicBlock
*BB
) const;
2424 /// Return the ScopStmts that represents the Region @p R, or nullptr if
2425 /// it is not represented by any statement in this Scop.
2426 ArrayRef
<ScopStmt
*> getStmtListFor(Region
*R
) const;
2428 /// Return the ScopStmts that represents @p RN; can return nullptr if
2429 /// the RegionNode is not within the SCoP or has been removed due to
2430 /// simplifications.
2431 ArrayRef
<ScopStmt
*> getStmtListFor(RegionNode
*RN
) const;
2433 /// Return the ScopStmt an instruction belongs to, or nullptr if it
2434 /// does not belong to any statement in this Scop.
2435 ScopStmt
*getStmtFor(Instruction
*Inst
) const {
2436 return InstStmtMap
.lookup(Inst
);
2439 /// Return the number of statements in the SCoP.
2440 size_t getSize() const { return Stmts
.size(); }
2442 /// @name Statements Iterators
2444 /// These iterators iterate over all statements of this Scop.
2446 using iterator
= StmtSet::iterator
;
2447 using const_iterator
= StmtSet::const_iterator
;
2449 iterator
begin() { return Stmts
.begin(); }
2450 iterator
end() { return Stmts
.end(); }
2451 const_iterator
begin() const { return Stmts
.begin(); }
2452 const_iterator
end() const { return Stmts
.end(); }
2454 using reverse_iterator
= StmtSet::reverse_iterator
;
2455 using const_reverse_iterator
= StmtSet::const_reverse_iterator
;
2457 reverse_iterator
rbegin() { return Stmts
.rbegin(); }
2458 reverse_iterator
rend() { return Stmts
.rend(); }
2459 const_reverse_iterator
rbegin() const { return Stmts
.rbegin(); }
2460 const_reverse_iterator
rend() const { return Stmts
.rend(); }
2463 /// Return the set of required invariant loads.
2464 const InvariantLoadsSetTy
&getRequiredInvariantLoads() const {
2465 return DC
.RequiredILS
;
2468 /// Add @p LI to the set of required invariant loads.
2469 void addRequiredInvariantLoad(LoadInst
*LI
) { DC
.RequiredILS
.insert(LI
); }
2471 /// Return the set of boxed (thus overapproximated) loops.
2472 const BoxedLoopsSetTy
&getBoxedLoops() const { return DC
.BoxedLoopsSet
; }
2474 /// Return true if and only if @p R is a non-affine subregion.
2475 bool isNonAffineSubRegion(const Region
*R
) {
2476 return DC
.NonAffineSubRegionSet
.count(R
);
2479 const MapInsnToMemAcc
&getInsnToMemAccMap() const { return DC
.InsnToMemAcc
; }
2481 /// Return the (possibly new) ScopArrayInfo object for @p Access.
2483 /// @param ElementType The type of the elements stored in this array.
2484 /// @param Kind The kind of the array info object.
2485 /// @param BaseName The optional name of this memory reference.
2486 ScopArrayInfo
*getOrCreateScopArrayInfo(Value
*BasePtr
, Type
*ElementType
,
2487 ArrayRef
<const SCEV
*> Sizes
,
2489 const char *BaseName
= nullptr);
2491 /// Create an array and return the corresponding ScopArrayInfo object.
2493 /// @param ElementType The type of the elements stored in this array.
2494 /// @param BaseName The name of this memory reference.
2495 /// @param Sizes The sizes of dimensions.
2496 ScopArrayInfo
*createScopArrayInfo(Type
*ElementType
,
2497 const std::string
&BaseName
,
2498 const std::vector
<unsigned> &Sizes
);
2500 /// Return the cached ScopArrayInfo object for @p BasePtr.
2502 /// @param BasePtr The base pointer the object has been stored for.
2503 /// @param Kind The kind of array info object.
2505 /// @returns The ScopArrayInfo pointer or NULL if no such pointer is
2507 const ScopArrayInfo
*getScopArrayInfoOrNull(Value
*BasePtr
, MemoryKind Kind
);
2509 /// Return the cached ScopArrayInfo object for @p BasePtr.
2511 /// @param BasePtr The base pointer the object has been stored for.
2512 /// @param Kind The kind of array info object.
2514 /// @returns The ScopArrayInfo pointer (may assert if no such pointer is
2516 const ScopArrayInfo
*getScopArrayInfo(Value
*BasePtr
, MemoryKind Kind
);
2518 /// Invalidate ScopArrayInfo object for base address.
2520 /// @param BasePtr The base pointer of the ScopArrayInfo object to invalidate.
2521 /// @param Kind The Kind of the ScopArrayInfo object.
2522 void invalidateScopArrayInfo(Value
*BasePtr
, MemoryKind Kind
) {
2523 auto It
= ScopArrayInfoMap
.find(std::make_pair(BasePtr
, Kind
));
2524 if (It
== ScopArrayInfoMap
.end())
2526 ScopArrayInfoSet
.remove(It
->second
.get());
2527 ScopArrayInfoMap
.erase(It
);
2530 /// Set new isl context.
2531 void setContext(isl::set NewContext
);
2533 /// Update maximal loop depth. If @p Depth is smaller than current value,
2534 /// then maximal loop depth is not updated.
2535 void updateMaxLoopDepth(unsigned Depth
) {
2536 MaxLoopDepth
= std::max(MaxLoopDepth
, Depth
);
2539 /// Align the parameters in the statement to the scop context
2540 void realignParams();
2542 /// Return true if this SCoP can be profitably optimized.
2544 /// @param ScalarsAreUnprofitable Never consider statements with scalar writes
2545 /// as profitably optimizable.
2547 /// @return Whether this SCoP can be profitably optimized.
2548 bool isProfitable(bool ScalarsAreUnprofitable
) const;
2550 /// Return true if the SCoP contained at least one error block.
2551 bool hasErrorBlock() const { return HasErrorBlock
; }
2553 /// Notify SCoP that it contains an error block
2554 void notifyErrorBlock() { HasErrorBlock
= true; }
2556 /// Return true if the underlying region has a single exiting block.
2557 bool hasSingleExitEdge() const { return HasSingleExitEdge
; }
2559 /// Print the static control part.
2561 /// @param OS The output stream the static control part is printed to.
2562 /// @param PrintInstructions Whether to print the statement's instructions as
2564 void print(raw_ostream
&OS
, bool PrintInstructions
) const;
2566 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2567 /// Print the ScopStmt to stderr.
2571 /// Get the isl context of this static control part.
2573 /// @return The isl context of this static control part.
2574 isl::ctx
getIslCtx() const;
2576 /// Directly return the shared_ptr of the context.
2577 const std::shared_ptr
<isl_ctx
> &getSharedIslCtx() const { return IslCtx
; }
2579 /// Compute the isl representation for the SCEV @p E
2581 /// @param E The SCEV that should be translated.
2582 /// @param BB An (optional) basic block in which the isl_pw_aff is computed.
2583 /// SCEVs known to not reference any loops in the SCoP can be
2584 /// passed without a @p BB.
2585 /// @param NonNegative Flag to indicate the @p E has to be non-negative.
2587 /// Note that this function will always return a valid isl_pw_aff. However, if
2588 /// the translation of @p E was deemed to complex the SCoP is invalidated and
2589 /// a dummy value of appropriate dimension is returned. This allows to bail
2590 /// for complex cases without "error handling code" needed on the users side.
2591 PWACtx
getPwAff(const SCEV
*E
, BasicBlock
*BB
= nullptr,
2592 bool NonNegative
= false);
2594 /// Compute the isl representation for the SCEV @p E
2596 /// This function is like @see Scop::getPwAff() but strips away the invalid
2597 /// domain part associated with the piecewise affine function.
2598 isl::pw_aff
getPwAffOnly(const SCEV
*E
, BasicBlock
*BB
= nullptr);
2600 /// Check if an <nsw> AddRec for the loop L is cached.
2601 bool hasNSWAddRecForLoop(Loop
*L
) { return Affinator
.hasNSWAddRecForLoop(L
); }
2603 /// Return the domain of @p Stmt.
2605 /// @param Stmt The statement for which the conditions should be returned.
2606 isl::set
getDomainConditions(const ScopStmt
*Stmt
) const;
2608 /// Return the domain of @p BB.
2610 /// @param BB The block for which the conditions should be returned.
2611 isl::set
getDomainConditions(BasicBlock
*BB
) const;
2613 /// Return the domain of @p BB. If it does not exist, create an empty one.
2614 isl::set
&getOrInitEmptyDomain(BasicBlock
*BB
) { return DomainMap
[BB
]; }
2616 /// Check if domain is determined for @p BB.
2617 bool isDomainDefined(BasicBlock
*BB
) const { return DomainMap
.count(BB
) > 0; }
2619 /// Set domain for @p BB.
2620 void setDomain(BasicBlock
*BB
, isl::set
&Domain
) { DomainMap
[BB
] = Domain
; }
2622 /// Get a union set containing the iteration domains of all statements.
2623 isl::union_set
getDomains() const;
2625 /// Get a union map of all may-writes performed in the SCoP.
2626 isl::union_map
getMayWrites();
2628 /// Get a union map of all must-writes performed in the SCoP.
2629 isl::union_map
getMustWrites();
2631 /// Get a union map of all writes performed in the SCoP.
2632 isl::union_map
getWrites();
2634 /// Get a union map of all reads performed in the SCoP.
2635 isl::union_map
getReads();
2637 /// Get a union map of all memory accesses performed in the SCoP.
2638 isl::union_map
getAccesses();
2640 /// Get a union map of all memory accesses performed in the SCoP.
2642 /// @param Array The array to which the accesses should belong.
2643 isl::union_map
getAccesses(ScopArrayInfo
*Array
);
2645 /// Get the schedule of all the statements in the SCoP.
2647 /// @return The schedule of all the statements in the SCoP, if the schedule of
2648 /// the Scop does not contain extension nodes, and nullptr, otherwise.
2649 isl::union_map
getSchedule() const;
2651 /// Get a schedule tree describing the schedule of all statements.
2652 isl::schedule
getScheduleTree() const;
2654 /// Update the current schedule
2656 /// NewSchedule The new schedule (given as a flat union-map).
2657 void setSchedule(isl::union_map NewSchedule
);
2659 /// Update the current schedule
2661 /// NewSchedule The new schedule (given as schedule tree).
2662 void setScheduleTree(isl::schedule NewSchedule
);
2664 /// Whether the schedule is the original schedule as derived from the CFG by
2666 bool isOriginalSchedule() const { return !ScheduleModified
; }
2668 /// Intersects the domains of all statements in the SCoP.
2670 /// @return true if a change was made
2671 bool restrictDomains(isl::union_set Domain
);
2673 /// Get the depth of a loop relative to the outermost loop in the Scop.
2675 /// This will return
2676 /// 0 if @p L is an outermost loop in the SCoP
2677 /// >0 for other loops in the SCoP
2678 /// -1 if @p L is nullptr or there is no outermost loop in the SCoP
2679 int getRelativeLoopDepth(const Loop
*L
) const;
2681 /// Find the ScopArrayInfo associated with an isl Id
2682 /// that has name @p Name.
2683 ScopArrayInfo
*getArrayInfoByName(const std::string BaseName
);
2685 /// Simplify the SCoP representation.
2687 /// @param AfterHoisting Whether it is called after invariant load hoisting.
2688 /// When true, also removes statements without
2690 void simplifySCoP(bool AfterHoisting
);
2692 /// Get the next free array index.
2694 /// This function returns a unique index which can be used to identify an
2696 long getNextArrayIdx() { return ArrayIdx
++; }
2698 /// Get the next free statement index.
2700 /// This function returns a unique index which can be used to identify a
2702 long getNextStmtIdx() { return StmtIdx
++; }
2704 /// Get the representing SCEV for @p S if applicable, otherwise @p S.
2706 /// Invariant loads of the same location are put in an equivalence class and
2707 /// only one of them is chosen as a representing element that will be
2708 /// modeled as a parameter. The others have to be normalized, i.e.,
2709 /// replaced by the representing element of their equivalence class, in order
2710 /// to get the correct parameter value, e.g., in the SCEVAffinator.
2712 /// @param S The SCEV to normalize.
2714 /// @return The representing SCEV for invariant loads or @p S if none.
2715 const SCEV
*getRepresentingInvariantLoadSCEV(const SCEV
*S
) const;
2717 /// Return the MemoryAccess that writes an llvm::Value, represented by a
2720 /// There can be at most one such MemoryAccess per llvm::Value in the SCoP.
2721 /// Zero is possible for read-only values.
2722 MemoryAccess
*getValueDef(const ScopArrayInfo
*SAI
) const;
2724 /// Return all MemoryAccesses that us an llvm::Value, represented by a
2726 ArrayRef
<MemoryAccess
*> getValueUses(const ScopArrayInfo
*SAI
) const;
2728 /// Return the MemoryAccess that represents an llvm::PHINode.
2730 /// ExitPHIs's PHINode is not within the SCoPs. This function returns nullptr
2732 MemoryAccess
*getPHIRead(const ScopArrayInfo
*SAI
) const;
2734 /// Return all MemoryAccesses for all incoming statements of a PHINode,
2735 /// represented by a ScopArrayInfo.
2736 ArrayRef
<MemoryAccess
*> getPHIIncomings(const ScopArrayInfo
*SAI
) const;
2738 /// Return whether @p Inst has a use outside of this SCoP.
2739 bool isEscaping(Instruction
*Inst
);
2741 struct ScopStatistics
{
2742 int NumAffineLoops
= 0;
2743 int NumBoxedLoops
= 0;
2745 int NumValueWrites
= 0;
2746 int NumValueWritesInLoops
= 0;
2747 int NumPHIWrites
= 0;
2748 int NumPHIWritesInLoops
= 0;
2749 int NumSingletonWrites
= 0;
2750 int NumSingletonWritesInLoops
= 0;
2753 /// Collect statistic about this SCoP.
2755 /// These are most commonly used for LLVM's static counters (Statistic.h) in
2756 /// various places. If statistics are disabled, only zeros are returned to
2757 /// avoid the overhead.
2758 ScopStatistics
getStatistics() const;
2761 /// Print Scop scop to raw_ostream OS.
2762 raw_ostream
&operator<<(raw_ostream
&OS
, const Scop
&scop
);
2764 /// The legacy pass manager's analysis pass to compute scop information
2766 class ScopInfoRegionPass
: public RegionPass
{
2767 /// The Scop pointer which is used to construct a Scop.
2768 std::unique_ptr
<Scop
> S
;
2771 static char ID
; // Pass identification, replacement for typeid
2773 ScopInfoRegionPass() : RegionPass(ID
) {}
2774 ~ScopInfoRegionPass() override
= default;
2776 /// Build Scop object, the Polly IR of static control
2777 /// part for the current SESE-Region.
2779 /// @return If the current region is a valid for a static control part,
2780 /// return the Polly IR representing this static control part,
2781 /// return null otherwise.
2782 Scop
*getScop() { return S
.get(); }
2783 const Scop
*getScop() const { return S
.get(); }
2785 /// Calculate the polyhedral scop information for a given Region.
2786 bool runOnRegion(Region
*R
, RGPassManager
&RGM
) override
;
2788 void releaseMemory() override
{ S
.reset(); }
2790 void print(raw_ostream
&O
, const Module
*M
= nullptr) const override
;
2792 void getAnalysisUsage(AnalysisUsage
&AU
) const override
;
2797 using RegionToScopMapTy
= MapVector
<Region
*, std::unique_ptr
<Scop
>>;
2798 using reverse_iterator
= RegionToScopMapTy::reverse_iterator
;
2799 using const_reverse_iterator
= RegionToScopMapTy::const_reverse_iterator
;
2800 using iterator
= RegionToScopMapTy::iterator
;
2801 using const_iterator
= RegionToScopMapTy::const_iterator
;
2804 /// A map of Region to its Scop object containing
2805 /// Polly IR of static control part.
2806 RegionToScopMapTy RegionToScopMap
;
2807 const DataLayout
&DL
;
2809 ScalarEvolution
&SE
;
2813 AssumptionCache
&AC
;
2814 OptimizationRemarkEmitter
&ORE
;
2817 ScopInfo(const DataLayout
&DL
, ScopDetection
&SD
, ScalarEvolution
&SE
,
2818 LoopInfo
&LI
, AliasAnalysis
&AA
, DominatorTree
&DT
,
2819 AssumptionCache
&AC
, OptimizationRemarkEmitter
&ORE
);
2821 /// Get the Scop object for the given Region.
2823 /// @return If the given region is the maximal region within a scop, return
2824 /// the scop object. If the given region is a subregion, return a
2825 /// nullptr. Top level region containing the entry block of a function
2826 /// is not considered in the scop creation.
2827 Scop
*getScop(Region
*R
) const {
2828 auto MapIt
= RegionToScopMap
.find(R
);
2829 if (MapIt
!= RegionToScopMap
.end())
2830 return MapIt
->second
.get();
2834 /// Recompute the Scop-Information for a function.
2836 /// This invalidates any iterators.
2839 /// Handle invalidation explicitly
2840 bool invalidate(Function
&F
, const PreservedAnalyses
&PA
,
2841 FunctionAnalysisManager::Invalidator
&Inv
);
2843 iterator
begin() { return RegionToScopMap
.begin(); }
2844 iterator
end() { return RegionToScopMap
.end(); }
2845 const_iterator
begin() const { return RegionToScopMap
.begin(); }
2846 const_iterator
end() const { return RegionToScopMap
.end(); }
2847 reverse_iterator
rbegin() { return RegionToScopMap
.rbegin(); }
2848 reverse_iterator
rend() { return RegionToScopMap
.rend(); }
2849 const_reverse_iterator
rbegin() const { return RegionToScopMap
.rbegin(); }
2850 const_reverse_iterator
rend() const { return RegionToScopMap
.rend(); }
2851 bool empty() const { return RegionToScopMap
.empty(); }
2854 struct ScopInfoAnalysis
: public AnalysisInfoMixin
<ScopInfoAnalysis
> {
2855 static AnalysisKey Key
;
2857 using Result
= ScopInfo
;
2859 Result
run(Function
&, FunctionAnalysisManager
&);
2862 struct ScopInfoPrinterPass
: public PassInfoMixin
<ScopInfoPrinterPass
> {
2863 ScopInfoPrinterPass(raw_ostream
&OS
) : Stream(OS
) {}
2865 PreservedAnalyses
run(Function
&, FunctionAnalysisManager
&);
2867 raw_ostream
&Stream
;
2870 //===----------------------------------------------------------------------===//
2871 /// The legacy pass manager's analysis pass to compute scop information
2872 /// for the whole function.
2874 /// This pass will maintain a map of the maximal region within a scop to its
2875 /// scop object for all the feasible scops present in a function.
2876 /// This pass is an alternative to the ScopInfoRegionPass in order to avoid a
2877 /// region pass manager.
2878 class ScopInfoWrapperPass
: public FunctionPass
{
2879 std::unique_ptr
<ScopInfo
> Result
;
2882 ScopInfoWrapperPass() : FunctionPass(ID
) {}
2883 ~ScopInfoWrapperPass() override
= default;
2885 static char ID
; // Pass identification, replacement for typeid
2887 ScopInfo
*getSI() { return Result
.get(); }
2888 const ScopInfo
*getSI() const { return Result
.get(); }
2890 /// Calculate all the polyhedral scops for a given function.
2891 bool runOnFunction(Function
&F
) override
;
2893 void releaseMemory() override
{ Result
.reset(); }
2895 void print(raw_ostream
&O
, const Module
*M
= nullptr) const override
;
2897 void getAnalysisUsage(AnalysisUsage
&AU
) const override
;
2899 } // end namespace polly
2901 #endif // POLLY_SCOPINFO_H