1 //===------ polly/ScopInfo.h -----------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Store the polyhedral model representation of a static control flow region,
11 // also called SCoP (Static Control Part).
13 // This representation is shared among several tools in the polyhedral
14 // community, which are e.g. CLooG, Pluto, Loopo, Graphite.
16 //===----------------------------------------------------------------------===//
18 #ifndef POLLY_SCOP_INFO_H
19 #define POLLY_SCOP_INFO_H
21 #include "polly/ScopDetection.h"
22 #include "polly/Support/SCEVAffinator.h"
24 #include "llvm/ADT/MapVector.h"
25 #include "llvm/Analysis/RegionPass.h"
26 #include "llvm/IR/PassManager.h"
31 #include "isl-noexceptions.h"
34 #include <forward_list>
39 class AssumptionCache
;
43 class ScalarEvolution
;
58 struct isl_constraint
;
60 struct isl_pw_multi_aff
;
70 //===---------------------------------------------------------------------===//
72 extern bool UseInstructionNames
;
74 /// Enumeration of assumptions Polly can take.
88 /// Enum to distinguish between assumptions and restrictions.
89 enum AssumptionSign
{ AS_ASSUMPTION
, AS_RESTRICTION
};
91 /// The different memory kinds used in Polly.
93 /// We distinguish between arrays and various scalar memory objects. We use
94 /// the term ``array'' to describe memory objects that consist of a set of
95 /// individual data elements arranged in a multi-dimensional grid. A scalar
96 /// memory object describes an individual data element and is used to model
97 /// the definition and uses of llvm::Values.
99 /// The polyhedral model does traditionally not reason about SSA values. To
100 /// reason about llvm::Values we model them "as if" they were zero-dimensional
101 /// memory objects, even though they were not actually allocated in (main)
102 /// memory. Memory for such objects is only alloca[ed] at CodeGeneration
103 /// time. To relate the memory slots used during code generation with the
104 /// llvm::Values they belong to the new names for these corresponding stack
105 /// slots are derived by appending suffixes (currently ".s2a" and ".phiops")
106 /// to the name of the original llvm::Value. To describe how def/uses are
107 /// modeled exactly we use these suffixes here as well.
109 /// There are currently four different kinds of memory objects:
110 enum class MemoryKind
{
111 /// MemoryKind::Array: Models a one or multi-dimensional array
113 /// A memory object that can be described by a multi-dimensional array.
114 /// Memory objects of this type are used to model actual multi-dimensional
115 /// arrays as they exist in LLVM-IR, but they are also used to describe
117 /// - A single data element allocated on the stack using 'alloca' is
118 /// modeled as a one-dimensional, single-element array.
119 /// - A single data element allocated as a global variable is modeled as
120 /// one-dimensional, single-element array.
121 /// - Certain multi-dimensional arrays with variable size, which in
122 /// LLVM-IR are commonly expressed as a single-dimensional access with a
123 /// complicated access function, are modeled as multi-dimensional
124 /// memory objects (grep for "delinearization").
127 /// MemoryKind::Value: Models an llvm::Value
129 /// Memory objects of type MemoryKind::Value are used to model the data flow
130 /// induced by llvm::Values. For each llvm::Value that is used across
131 /// BasicBocks one ScopArrayInfo object is created. A single memory WRITE
132 /// stores the llvm::Value at its definition into the memory object and at
133 /// each use of the llvm::Value (ignoring trivial intra-block uses) a
134 /// corresponding READ is added. For instance, the use/def chain of a
135 /// llvm::Value %V depicted below
136 /// ______________________
138 /// | %V = float op ... |
139 /// ----------------------
141 /// _________________ _________________
142 /// |UseBB1: | |UseBB2: |
143 /// | use float %V | | use float %V |
144 /// ----------------- -----------------
146 /// is modeled as if the following memory accesses occurred:
148 /// __________________________
150 /// | %V.s2a = alloca float |
151 /// --------------------------
153 /// ___________________________________
155 /// | store %float %V, float* %V.s2a |
156 /// -----------------------------------
158 /// ____________________________________ ___________________________________
159 /// |UseBB1: | |UseBB2: |
160 /// | %V.reload1 = load float* %V.s2a | | %V.reload2 = load float* %V.s2a|
161 /// | use float %V.reload1 | | use float %V.reload2 |
162 /// ------------------------------------ -----------------------------------
166 /// MemoryKind::PHI: Models PHI nodes within the SCoP
168 /// Besides the MemoryKind::Value memory object used to model the normal
169 /// llvm::Value dependences described above, PHI nodes require an additional
170 /// memory object of type MemoryKind::PHI to describe the forwarding of values
174 /// As an example, a PHIInst instructions
176 /// %PHI = phi float [ %Val1, %IncomingBlock1 ], [ %Val2, %IncomingBlock2 ]
178 /// is modeled as if the accesses occurred this way:
180 /// _______________________________
182 /// | %PHI.phiops = alloca float |
183 /// -------------------------------
185 /// __________________________________ __________________________________
186 /// |IncomingBlock1: | |IncomingBlock2: |
188 /// | store float %Val1 %PHI.phiops | | store float %Val2 %PHI.phiops |
189 /// | br label % JoinBlock | | br label %JoinBlock |
190 /// ---------------------------------- ----------------------------------
193 /// _________________________________________
195 /// | %PHI = load float, float* PHI.phiops |
196 /// -----------------------------------------
198 /// Note that there can also be a scalar write access for %PHI if used in a
199 /// different BasicBlock, i.e. there can be a memory object %PHI.phiops as
200 /// well as a memory object %PHI.s2a.
203 /// MemoryKind::ExitPHI: Models PHI nodes in the SCoP's exit block
205 /// For PHI nodes in the Scop's exit block a special memory object kind is
206 /// used. The modeling used is identical to MemoryKind::PHI, with the
208 /// that there are no READs from these memory objects. The PHINode's
209 /// llvm::Value is treated as a value escaping the SCoP. WRITE accesses
210 /// write directly to the escaping value's ".s2a" alloca.
214 /// Maps from a loop to the affine function expressing its backedge taken count.
215 /// The backedge taken count already enough to express iteration domain as we
216 /// only allow loops with canonical induction variable.
217 /// A canonical induction variable is:
218 /// an integer recurrence that starts at 0 and increments by one each time
219 /// through the loop.
220 typedef std::map
<const Loop
*, const SCEV
*> LoopBoundMapType
;
222 typedef std::vector
<std::unique_ptr
<MemoryAccess
>> AccFuncVector
;
224 /// A class to store information about arrays in the SCoP.
226 /// Objects are accessible via the ScoP, MemoryAccess or the id associated with
227 /// the MemoryAccess access function.
229 class ScopArrayInfo
{
231 /// Construct a ScopArrayInfo object.
233 /// @param BasePtr The array base pointer.
234 /// @param ElementType The type of the elements stored in the array.
235 /// @param IslCtx The isl context used to create the base pointer id.
236 /// @param DimensionSizes A vector containing the size of each dimension.
237 /// @param Kind The kind of the array object.
238 /// @param DL The data layout of the module.
239 /// @param S The scop this array object belongs to.
240 /// @param BaseName The optional name of this memory reference.
241 ScopArrayInfo(Value
*BasePtr
, Type
*ElementType
, isl_ctx
*IslCtx
,
242 ArrayRef
<const SCEV
*> DimensionSizes
, MemoryKind Kind
,
243 const DataLayout
&DL
, Scop
*S
, const char *BaseName
= nullptr);
245 /// Update the element type of the ScopArrayInfo object.
247 /// Memory accesses referencing this ScopArrayInfo object may use
248 /// different element sizes. This function ensures the canonical element type
249 /// stored is small enough to model accesses to the current element type as
250 /// well as to @p NewElementType.
252 /// @param NewElementType An element type that is used to access this array.
253 void updateElementType(Type
*NewElementType
);
255 /// Update the sizes of the ScopArrayInfo object.
257 /// A ScopArrayInfo object may be created without all outer dimensions being
258 /// available. This function is called when new memory accesses are added for
259 /// this ScopArrayInfo object. It verifies that sizes are compatible and adds
260 /// additional outer array dimensions, if needed.
262 /// @param Sizes A vector of array sizes where the rightmost array
263 /// sizes need to match the innermost array sizes already
265 /// @param CheckConsistency Update sizes, even if new sizes are inconsistent
267 bool updateSizes(ArrayRef
<const SCEV
*> Sizes
, bool CheckConsistency
= true);
269 /// Make the ScopArrayInfo model a Fortran array.
270 /// It receives the Fortran array descriptor and stores this.
271 /// It also adds a piecewise expression for the outermost dimension
272 /// since this information is available for Fortran arrays at runtime.
273 void applyAndSetFAD(Value
*FAD
);
275 /// Destructor to free the isl id of the base pointer.
278 /// Set the base pointer to @p BP.
279 void setBasePtr(Value
*BP
) { BasePtr
= BP
; }
281 /// Return the base pointer.
282 Value
*getBasePtr() const { return BasePtr
; }
284 // Set IsOnHeap to the value in parameter.
285 void setIsOnHeap(bool value
) { IsOnHeap
= value
; }
287 /// For indirect accesses return the origin SAI of the BP, else null.
288 const ScopArrayInfo
*getBasePtrOriginSAI() const { return BasePtrOriginSAI
; }
290 /// The set of derived indirect SAIs for this origin SAI.
291 const SmallSetVector
<ScopArrayInfo
*, 2> &getDerivedSAIs() const {
295 /// Return the number of dimensions.
296 unsigned getNumberOfDimensions() const {
297 if (Kind
== MemoryKind::PHI
|| Kind
== MemoryKind::ExitPHI
||
298 Kind
== MemoryKind::Value
)
300 return DimensionSizes
.size();
303 /// Return the size of dimension @p dim as SCEV*.
305 // Scalars do not have array dimensions and the first dimension of
306 // a (possibly multi-dimensional) array also does not carry any size
307 // information, in case the array is not newly created.
308 const SCEV
*getDimensionSize(unsigned Dim
) const {
309 assert(Dim
< getNumberOfDimensions() && "Invalid dimension");
310 return DimensionSizes
[Dim
];
313 /// Return the size of dimension @p dim as isl_pw_aff.
315 // Scalars do not have array dimensions and the first dimension of
316 // a (possibly multi-dimensional) array also does not carry any size
317 // information, in case the array is not newly created.
318 isl::pw_aff
getDimensionSizePw(unsigned Dim
) const {
319 assert(Dim
< getNumberOfDimensions() && "Invalid dimension");
320 return DimensionSizesPw
[Dim
];
323 /// Get the canonical element type of this array.
325 /// @returns The canonical element type of this array.
326 Type
*getElementType() const { return ElementType
; }
328 /// Get element size in bytes.
329 int getElemSizeInBytes() const;
331 /// Get the name of this memory reference.
332 std::string
getName() const;
334 /// Return the isl id for the base pointer.
335 isl::id
getBasePtrId() const;
337 /// Return what kind of memory this represents.
338 MemoryKind
getKind() const { return Kind
; }
340 /// Is this array info modeling an llvm::Value?
341 bool isValueKind() const { return Kind
== MemoryKind::Value
; }
343 /// Is this array info modeling special PHI node memory?
345 /// During code generation of PHI nodes, there is a need for two kinds of
346 /// virtual storage. The normal one as it is used for all scalar dependences,
347 /// where the result of the PHI node is stored and later loaded from as well
348 /// as a second one where the incoming values of the PHI nodes are stored
349 /// into and reloaded when the PHI is executed. As both memories use the
350 /// original PHI node as virtual base pointer, we have this additional
351 /// attribute to distinguish the PHI node specific array modeling from the
352 /// normal scalar array modeling.
353 bool isPHIKind() const { return Kind
== MemoryKind::PHI
; }
355 /// Is this array info modeling an MemoryKind::ExitPHI?
356 bool isExitPHIKind() const { return Kind
== MemoryKind::ExitPHI
; }
358 /// Is this array info modeling an array?
359 bool isArrayKind() const { return Kind
== MemoryKind::Array
; }
361 /// Is this array allocated on heap
363 /// This property is only relevant if the array is allocated by Polly instead
364 /// of pre-existing. If false, it is allocated using alloca instead malloca.
365 bool isOnHeap() const { return IsOnHeap
; }
367 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
368 /// Dump a readable representation to stderr.
372 /// Print a readable representation to @p OS.
374 /// @param SizeAsPwAff Print the size as isl_pw_aff
375 void print(raw_ostream
&OS
, bool SizeAsPwAff
= false) const;
377 /// Access the ScopArrayInfo associated with an access function.
378 static const ScopArrayInfo
*
379 getFromAccessFunction(__isl_keep isl_pw_multi_aff
*PMA
);
381 /// Access the ScopArrayInfo associated with an isl Id.
382 static const ScopArrayInfo
*getFromId(__isl_take isl_id
*Id
);
384 /// Get the space of this array access.
385 isl::space
getSpace() const;
387 /// If the array is read only
390 /// Verify that @p Array is compatible to this ScopArrayInfo.
392 /// Two arrays are compatible if their dimensionality, the sizes of their
393 /// dimensions, and their element sizes match.
395 /// @param Array The array to compare against.
397 /// @returns True, if the arrays are compatible, False otherwise.
398 bool isCompatibleWith(const ScopArrayInfo
*Array
) const;
401 void addDerivedSAI(ScopArrayInfo
*DerivedSAI
) {
402 DerivedSAIs
.insert(DerivedSAI
);
405 /// For indirect accesses this is the SAI of the BP origin.
406 const ScopArrayInfo
*BasePtrOriginSAI
;
408 /// For origin SAIs the set of derived indirect SAIs.
409 SmallSetVector
<ScopArrayInfo
*, 2> DerivedSAIs
;
411 /// The base pointer.
412 AssertingVH
<Value
> BasePtr
;
414 /// The canonical element type of this array.
416 /// The canonical element type describes the minimal accessible element in
417 /// this array. Not all elements accessed, need to be of the very same type,
418 /// but the allocation size of the type of the elements loaded/stored from/to
419 /// this array needs to be a multiple of the allocation size of the canonical
423 /// The isl id for the base pointer.
426 /// True if the newly allocated array is on heap.
429 /// The sizes of each dimension as SCEV*.
430 SmallVector
<const SCEV
*, 4> DimensionSizes
;
432 /// The sizes of each dimension as isl_pw_aff.
433 SmallVector
<isl::pw_aff
, 4> DimensionSizesPw
;
435 /// The type of this scop array info object.
437 /// We distinguish between SCALAR, PHI and ARRAY objects.
440 /// The data layout of the module.
441 const DataLayout
&DL
;
443 /// The scop this SAI object belongs to.
446 /// If this array models a Fortran array, then this points
447 /// to the Fortran array descriptor.
451 /// Represent memory accesses in statements.
454 friend class ScopStmt
;
457 /// The access type of a memory access
459 /// There are three kind of access types:
463 /// A certain set of memory locations are read and may be used for internal
466 /// * A must-write access
468 /// A certain set of memory locations is definitely written. The old value is
469 /// replaced by a newly calculated value. The old value is not read or used at
472 /// * A may-write access
474 /// A certain set of memory locations may be written. The memory location may
475 /// contain a new value if there is actually a write or the old value may
476 /// remain, if no write happens.
483 /// Reduction access type
485 /// Commutative and associative binary operations suitable for reductions
487 RT_NONE
, ///< Indicate no reduction at all
488 RT_ADD
, ///< Addition
489 RT_MUL
, ///< Multiplication
490 RT_BOR
, ///< Bitwise Or
491 RT_BXOR
, ///< Bitwise XOr
492 RT_BAND
, ///< Bitwise And
496 MemoryAccess(const MemoryAccess
&) = delete;
497 const MemoryAccess
&operator=(const MemoryAccess
&) = delete;
499 /// A unique identifier for this memory access.
501 /// The identifier is unique between all memory accesses belonging to the same
505 /// What is modeled by this MemoryAccess.
509 /// Whether it a reading or writing access, and if writing, whether it
510 /// is conditional (MAY_WRITE).
511 enum AccessType AccType
;
513 /// Reduction type for reduction like accesses, RT_NONE otherwise
515 /// An access is reduction like if it is part of a load-store chain in which
516 /// both access the same memory location (use the same LLVM-IR value
517 /// as pointer reference). Furthermore, between the load and the store there
518 /// is exactly one binary operator which is known to be associative and
523 /// We can later lift the constraint that the same LLVM-IR value defines the
524 /// memory location to handle scops such as the following:
528 /// sum[i+j] = sum[i] + 3;
530 /// Here not all iterations access the same memory location, but iterations
531 /// for which j = 0 holds do. After lifting the equality check in ScopBuilder,
532 /// subsequent transformations do not only need check if a statement is
533 /// reduction like, but they also need to verify that that the reduction
534 /// property is only exploited for statement instances that load from and
535 /// store to the same data location. Doing so at dependence analysis time
536 /// could allow us to handle the above example.
537 ReductionType RedType
= RT_NONE
;
539 /// Parent ScopStmt of this access.
542 /// The domain under which this access is not modeled precisely.
544 /// The invalid domain for an access describes all parameter combinations
545 /// under which the statement looks to be executed but is in fact not because
546 /// some assumption/restriction makes the access invalid.
547 isl_set
*InvalidDomain
;
549 // Properties describing the accessed array.
550 // TODO: It might be possible to move them to ScopArrayInfo.
553 /// The base address (e.g., A for A[i+j]).
555 /// The #BaseAddr of a memory access of kind MemoryKind::Array is the base
556 /// pointer of the memory access.
557 /// The #BaseAddr of a memory access of kind MemoryKind::PHI or
558 /// MemoryKind::ExitPHI is the PHI node itself.
559 /// The #BaseAddr of a memory access of kind MemoryKind::Value is the
560 /// instruction defining the value.
561 AssertingVH
<Value
> BaseAddr
;
563 /// Type a single array element wrt. this access.
566 /// Size of each dimension of the accessed array.
567 SmallVector
<const SCEV
*, 4> Sizes
;
570 // Properties describing the accessed element.
573 /// The access instruction of this memory access.
575 /// For memory accesses of kind MemoryKind::Array the access instruction is
576 /// the Load or Store instruction performing the access.
578 /// For memory accesses of kind MemoryKind::PHI or MemoryKind::ExitPHI the
579 /// access instruction of a load access is the PHI instruction. The access
580 /// instruction of a PHI-store is the incoming's block's terminator
583 /// For memory accesses of kind MemoryKind::Value the access instruction of a
584 /// load access is nullptr because generally there can be multiple
585 /// instructions in the statement using the same llvm::Value. The access
586 /// instruction of a write access is the instruction that defines the
588 Instruction
*AccessInstruction
;
590 /// Incoming block and value of a PHINode.
591 SmallVector
<std::pair
<BasicBlock
*, Value
*>, 4> Incoming
;
593 /// The value associated with this memory access.
595 /// - For array memory accesses (MemoryKind::Array) it is the loaded result
596 /// or the stored value. If the access instruction is a memory intrinsic it
597 /// the access value is also the memory intrinsic.
598 /// - For accesses of kind MemoryKind::Value it is the access instruction
600 /// - For accesses of kind MemoryKind::PHI or MemoryKind::ExitPHI it is the
601 /// PHI node itself (for both, READ and WRITE accesses).
603 AssertingVH
<Value
> AccessValue
;
605 /// Are all the subscripts affine expression?
608 /// Subscript expression for each dimension.
609 SmallVector
<const SCEV
*, 4> Subscripts
;
611 /// Relation from statement instances to the accessed array elements.
613 /// In the common case this relation is a function that maps a set of loop
614 /// indices to the memory address from which a value is loaded/stored:
618 /// S: A[i + 3 j] = ...
620 /// => { S[i,j] -> A[i + 3j] }
622 /// In case the exact access function is not known, the access relation may
623 /// also be a one to all mapping { S[i,j] -> A[o] } describing that any
624 /// element accessible through A might be accessed.
626 /// In case of an access to a larger element belonging to an array that also
627 /// contains smaller elements, the access relation models the larger access
628 /// with multiple smaller accesses of the size of the minimal array element
634 /// S: A[i] = *((double*)&A[4 * i]);
636 /// => { S[i] -> A[i]; S[i] -> A[o] : 4i <= o <= 4i + 3 }
637 isl::map AccessRelation
;
639 /// Updated access relation read from JSCOP file.
640 isl::map NewAccessRelation
;
642 /// Fortran arrays whose sizes are not statically known are stored in terms
643 /// of a descriptor struct. This maintains a raw pointer to the memory,
644 /// along with auxiliary fields with information such as dimensions.
645 /// We hold a reference to the descriptor corresponding to a MemoryAccess
646 /// into a Fortran array. FAD for "Fortran Array Descriptor"
647 AssertingVH
<Value
> FAD
;
650 isl::basic_map
createBasicAccessMap(ScopStmt
*Statement
);
652 void assumeNoOutOfBound();
654 /// Compute bounds on an over approximated access relation.
656 /// @param ElementSize The size of one element accessed.
657 void computeBoundsOnAccessRelation(unsigned ElementSize
);
659 /// Get the original access function as read from IR.
660 isl::map
getOriginalAccessRelation() const;
662 /// Return the space in which the access relation lives in.
663 isl::space
getOriginalAccessRelationSpace() const;
665 /// Get the new access function imported or set by a pass
666 isl::map
getNewAccessRelation() const;
668 /// Fold the memory access to consider parametric offsets
670 /// To recover memory accesses with array size parameters in the subscript
671 /// expression we post-process the delinearization results.
673 /// We would normally recover from an access A[exp0(i) * N + exp1(i)] into an
674 /// array A[][N] the 2D access A[exp0(i)][exp1(i)]. However, another valid
675 /// delinearization is A[exp0(i) - 1][exp1(i) + N] which - depending on the
676 /// range of exp1(i) - may be preferable. Specifically, for cases where we
677 /// know exp1(i) is negative, we want to choose the latter expression.
679 /// As we commonly do not have any information about the range of exp1(i),
680 /// we do not choose one of the two options, but instead create a piecewise
681 /// access function that adds the (-1, N) offsets as soon as exp1(i) becomes
682 /// negative. For a 2D array such an access function is created by applying
683 /// the piecewise map:
685 /// [i,j] -> [i, j] : j >= 0
686 /// [i,j] -> [i-1, j+N] : j < 0
688 /// We can generalize this mapping to arbitrary dimensions by applying this
689 /// piecewise mapping pairwise from the rightmost to the leftmost access
690 /// dimension. It would also be possible to cover a wider range by introducing
691 /// more cases and adding multiple of Ns to these cases. However, this has
692 /// not yet been necessary.
693 /// The introduction of different cases necessarily complicates the memory
694 /// access function, but cases that can be statically proven to not happen
695 /// will be eliminated later on.
696 void foldAccessRelation();
698 /// Create the access relation for the underlying memory intrinsic.
699 void buildMemIntrinsicAccessRelation();
701 /// Assemble the access relation from all available information.
703 /// In particular, used the information passes in the constructor and the
704 /// parent ScopStmt set by setStatment().
706 /// @param SAI Info object for the accessed array.
707 void buildAccessRelation(const ScopArrayInfo
*SAI
);
709 /// Carry index overflows of dimensions with constant size to the next higher
712 /// For dimensions that have constant size, modulo the index by the size and
713 /// add up the carry (floored division) to the next higher dimension. This is
714 /// how overflow is defined in row-major order.
715 /// It happens e.g. when ScalarEvolution computes the offset to the base
716 /// pointer and would algebraically sum up all lower dimensions' indices of
721 /// A[1][6] -> A[2][2]
722 void wrapConstantDimensions();
725 /// Create a new MemoryAccess.
727 /// @param Stmt The parent statement.
728 /// @param AccessInst The instruction doing the access.
729 /// @param BaseAddr The accessed array's address.
730 /// @param ElemType The type of the accessed array elements.
731 /// @param AccType Whether read or write access.
732 /// @param IsAffine Whether the subscripts are affine expressions.
733 /// @param Kind The kind of memory accessed.
734 /// @param Subscripts Subscript expressions
735 /// @param Sizes Dimension lengths of the accessed array.
736 MemoryAccess(ScopStmt
*Stmt
, Instruction
*AccessInst
, AccessType AccType
,
737 Value
*BaseAddress
, Type
*ElemType
, bool Affine
,
738 ArrayRef
<const SCEV
*> Subscripts
, ArrayRef
<const SCEV
*> Sizes
,
739 Value
*AccessValue
, MemoryKind Kind
);
741 /// Create a new MemoryAccess that corresponds to @p AccRel.
743 /// Along with @p Stmt and @p AccType it uses information about dimension
744 /// lengths of the accessed array, the type of the accessed array elements,
745 /// the name of the accessed array that is derived from the object accessible
748 /// @param Stmt The parent statement.
749 /// @param AccType Whether read or write access.
750 /// @param AccRel The access relation that describes the memory access.
751 MemoryAccess(ScopStmt
*Stmt
, AccessType AccType
, __isl_take isl_map
*AccRel
);
755 /// Add a new incoming block/value pairs for this PHI/ExitPHI access.
757 /// @param IncomingBlock The PHI's incoming block.
758 /// @param IncomingValue The value when reaching the PHI from the @p
760 void addIncoming(BasicBlock
*IncomingBlock
, Value
*IncomingValue
) {
762 assert(isAnyPHIKind());
763 Incoming
.emplace_back(std::make_pair(IncomingBlock
, IncomingValue
));
766 /// Return the list of possible PHI/ExitPHI values.
768 /// After code generation moves some PHIs around during region simplification,
769 /// we cannot reliably locate the original PHI node and its incoming values
770 /// anymore. For this reason we remember these explicitly for all PHI-kind
772 ArrayRef
<std::pair
<BasicBlock
*, Value
*>> getIncoming() const {
773 assert(isAnyPHIKind());
777 /// Get the type of a memory access.
778 enum AccessType
getType() { return AccType
; }
780 /// Is this a reduction like access?
781 bool isReductionLike() const { return RedType
!= RT_NONE
; }
783 /// Is this a read memory access?
784 bool isRead() const { return AccType
== MemoryAccess::READ
; }
786 /// Is this a must-write memory access?
787 bool isMustWrite() const { return AccType
== MemoryAccess::MUST_WRITE
; }
789 /// Is this a may-write memory access?
790 bool isMayWrite() const { return AccType
== MemoryAccess::MAY_WRITE
; }
792 /// Is this a write memory access?
793 bool isWrite() const { return isMustWrite() || isMayWrite(); }
795 /// Is this a memory intrinsic access (memcpy, memset, memmove)?
796 bool isMemoryIntrinsic() const {
797 return isa
<MemIntrinsic
>(getAccessInstruction());
800 /// Check if a new access relation was imported or set by a pass.
801 bool hasNewAccessRelation() const { return !NewAccessRelation
.is_null(); }
803 /// Return the newest access relation of this access.
805 /// There are two possibilities:
806 /// 1) The original access relation read from the LLVM-IR.
807 /// 2) A new access relation imported from a json file or set by another
808 /// pass (e.g., for privatization).
810 /// As 2) is by construction "newer" than 1) we return the new access
811 /// relation if present.
813 isl::map
getLatestAccessRelation() const {
814 return hasNewAccessRelation() ? getNewAccessRelation()
815 : getOriginalAccessRelation();
818 /// Old name of getLatestAccessRelation().
819 isl::map
getAccessRelation() const { return getLatestAccessRelation(); }
821 /// Get an isl map describing the memory address accessed.
823 /// In most cases the memory address accessed is well described by the access
824 /// relation obtained with getAccessRelation. However, in case of arrays
825 /// accessed with types of different size the access relation maps one access
826 /// to multiple smaller address locations. This method returns an isl map that
827 /// relates each dynamic statement instance to the unique memory location
828 /// that is loaded from / stored to.
830 /// For an access relation { S[i] -> A[o] : 4i <= o <= 4i + 3 } this method
831 /// will return the address function { S[i] -> A[4i] }.
833 /// @returns The address function for this memory access.
834 isl::map
getAddressFunction() const;
836 /// Return the access relation after the schedule was applied.
838 applyScheduleToAccessRelation(isl::union_map Schedule
) const;
840 /// Get an isl string representing the access function read from IR.
841 std::string
getOriginalAccessRelationStr() const;
843 /// Get an isl string representing a new access function, if available.
844 std::string
getNewAccessRelationStr() const;
846 /// Get an isl string representing the latest access relation.
847 std::string
getAccessRelationStr() const;
849 /// Get the original base address of this access (e.g. A for A[i+j]) when
852 /// This adress may differ from the base address referenced by the Original
853 /// ScopArrayInfo to which this array belongs, as this memory access may
854 /// have been unified to a ScopArray which has a different but identically
855 /// valued base pointer in case invariant load hoisting is enabled.
856 Value
*getOriginalBaseAddr() const { return BaseAddr
; }
858 /// Get the detection-time base array isl_id for this access.
859 isl::id
getOriginalArrayId() const;
861 /// Get the base array isl_id for this access, modifiable through
862 /// setNewAccessRelation().
863 isl::id
getLatestArrayId() const;
865 /// Old name of getOriginalArrayId().
866 isl::id
getArrayId() const { return getOriginalArrayId(); }
868 /// Get the detection-time ScopArrayInfo object for the base address.
869 const ScopArrayInfo
*getOriginalScopArrayInfo() const;
871 /// Get the ScopArrayInfo object for the base address, or the one set
872 /// by setNewAccessRelation().
873 const ScopArrayInfo
*getLatestScopArrayInfo() const;
875 /// Legacy name of getOriginalScopArrayInfo().
876 const ScopArrayInfo
*getScopArrayInfo() const {
877 return getOriginalScopArrayInfo();
880 /// Return a string representation of the access's reduction type.
881 const std::string
getReductionOperatorStr() const;
883 /// Return a string representation of the reduction type @p RT.
884 static const std::string
getReductionOperatorStr(ReductionType RT
);
886 /// Return the element type of the accessed array wrt. this access.
887 Type
*getElementType() const { return ElementType
; }
889 /// Return the access value of this memory access.
890 Value
*getAccessValue() const { return AccessValue
; }
892 /// Return llvm::Value that is stored by this access, if available.
894 /// PHI nodes may not have a unique value available that is stored, as in
895 /// case of region statements one out of possibly several llvm::Values
896 /// might be stored. In this case nullptr is returned.
897 Value
*tryGetValueStored() {
898 assert(isWrite() && "Only write statement store values");
899 if (isAnyPHIKind()) {
900 if (Incoming
.size() == 1)
901 return Incoming
[0].second
;
907 /// Return the access instruction of this memory access.
908 Instruction
*getAccessInstruction() const { return AccessInstruction
; }
910 /// Return the number of access function subscript.
911 unsigned getNumSubscripts() const { return Subscripts
.size(); }
913 /// Return the access function subscript in the dimension @p Dim.
914 const SCEV
*getSubscript(unsigned Dim
) const { return Subscripts
[Dim
]; }
916 /// Compute the isl representation for the SCEV @p E wrt. this access.
918 /// Note that this function will also adjust the invalid context accordingly.
919 __isl_give isl_pw_aff
*getPwAff(const SCEV
*E
);
921 /// Get the invalid domain for this access.
922 __isl_give isl_set
*getInvalidDomain() const {
923 return isl_set_copy(InvalidDomain
);
926 /// Get the invalid context for this access.
927 __isl_give isl_set
*getInvalidContext() const {
928 return isl_set_params(getInvalidDomain());
931 /// Get the stride of this memory access in the specified Schedule. Schedule
932 /// is a map from the statement to a schedule where the innermost dimension is
933 /// the dimension of the innermost loop containing the statement.
934 __isl_give isl_set
*getStride(__isl_take
const isl_map
*Schedule
) const;
936 /// Get the FortranArrayDescriptor corresponding to this memory access if
937 /// it exists, and nullptr otherwise.
938 Value
*getFortranArrayDescriptor() const { return this->FAD
; };
940 /// Is the stride of the access equal to a certain width? Schedule is a map
941 /// from the statement to a schedule where the innermost dimension is the
942 /// dimension of the innermost loop containing the statement.
943 bool isStrideX(__isl_take
const isl_map
*Schedule
, int StrideWidth
) const;
945 /// Is consecutive memory accessed for a given statement instance set?
946 /// Schedule is a map from the statement to a schedule where the innermost
947 /// dimension is the dimension of the innermost loop containing the
949 bool isStrideOne(__isl_take
const isl_map
*Schedule
) const;
951 /// Is always the same memory accessed for a given statement instance set?
952 /// Schedule is a map from the statement to a schedule where the innermost
953 /// dimension is the dimension of the innermost loop containing the
955 bool isStrideZero(__isl_take
const isl_map
*Schedule
) const;
957 /// Return the kind when this access was first detected.
958 MemoryKind
getOriginalKind() const {
959 assert(!getOriginalScopArrayInfo() /* not yet initialized */ ||
960 getOriginalScopArrayInfo()->getKind() == Kind
);
964 /// Return the kind considering a potential setNewAccessRelation.
965 MemoryKind
getLatestKind() const {
966 return getLatestScopArrayInfo()->getKind();
969 /// Whether this is an access of an explicit load or store in the IR.
970 bool isOriginalArrayKind() const {
971 return getOriginalKind() == MemoryKind::Array
;
974 /// Whether storage memory is either an custom .s2a/.phiops alloca
975 /// (false) or an existing pointer into an array (true).
976 bool isLatestArrayKind() const {
977 return getLatestKind() == MemoryKind::Array
;
980 /// Old name of isOriginalArrayKind.
981 bool isArrayKind() const { return isOriginalArrayKind(); }
983 /// Whether this access is an array to a scalar memory object, without
984 /// considering changes by setNewAccessRelation.
986 /// Scalar accesses are accesses to MemoryKind::Value, MemoryKind::PHI or
987 /// MemoryKind::ExitPHI.
988 bool isOriginalScalarKind() const {
989 return getOriginalKind() != MemoryKind::Array
;
992 /// Whether this access is an array to a scalar memory object, also
993 /// considering changes by setNewAccessRelation.
994 bool isLatestScalarKind() const {
995 return getLatestKind() != MemoryKind::Array
;
998 /// Old name of isOriginalScalarKind.
999 bool isScalarKind() const { return isOriginalScalarKind(); }
1001 /// Was this MemoryAccess detected as a scalar dependences?
1002 bool isOriginalValueKind() const {
1003 return getOriginalKind() == MemoryKind::Value
;
1006 /// Is this MemoryAccess currently modeling scalar dependences?
1007 bool isLatestValueKind() const {
1008 return getLatestKind() == MemoryKind::Value
;
1011 /// Old name of isOriginalValueKind().
1012 bool isValueKind() const { return isOriginalValueKind(); }
1014 /// Was this MemoryAccess detected as a special PHI node access?
1015 bool isOriginalPHIKind() const {
1016 return getOriginalKind() == MemoryKind::PHI
;
1019 /// Is this MemoryAccess modeling special PHI node accesses, also
1020 /// considering a potential change by setNewAccessRelation?
1021 bool isLatestPHIKind() const { return getLatestKind() == MemoryKind::PHI
; }
1023 /// Old name of isOriginalPHIKind.
1024 bool isPHIKind() const { return isOriginalPHIKind(); }
1026 /// Was this MemoryAccess detected as the accesses of a PHI node in the
1027 /// SCoP's exit block?
1028 bool isOriginalExitPHIKind() const {
1029 return getOriginalKind() == MemoryKind::ExitPHI
;
1032 /// Is this MemoryAccess modeling the accesses of a PHI node in the
1033 /// SCoP's exit block? Can be changed to an array access using
1034 /// setNewAccessRelation().
1035 bool isLatestExitPHIKind() const {
1036 return getLatestKind() == MemoryKind::ExitPHI
;
1039 /// Old name of isOriginalExitPHIKind().
1040 bool isExitPHIKind() const { return isOriginalExitPHIKind(); }
1042 /// Was this access detected as one of the two PHI types?
1043 bool isOriginalAnyPHIKind() const {
1044 return isOriginalPHIKind() || isOriginalExitPHIKind();
1047 /// Does this access originate from one of the two PHI types? Can be
1048 /// changed to an array access using setNewAccessRelation().
1049 bool isLatestAnyPHIKind() const {
1050 return isLatestPHIKind() || isLatestExitPHIKind();
1053 /// Old name of isOriginalAnyPHIKind().
1054 bool isAnyPHIKind() const { return isOriginalAnyPHIKind(); }
1056 /// Get the statement that contains this memory access.
1057 ScopStmt
*getStatement() const { return Statement
; }
1059 /// Get the reduction type of this access
1060 ReductionType
getReductionType() const { return RedType
; }
1062 /// Set the array descriptor corresponding to the Array on which the
1063 /// memory access is performed.
1064 void setFortranArrayDescriptor(Value
*FAD
);
1066 /// Update the original access relation.
1068 /// We need to update the original access relation during scop construction,
1069 /// when unifying the memory accesses that access the same scop array info
1070 /// object. After the scop has been constructed, the original access relation
1071 /// should not be changed any more. Instead setNewAccessRelation should
1073 void setAccessRelation(__isl_take isl_map
*AccessRelation
);
1075 /// Set the updated access relation read from JSCOP file.
1076 void setNewAccessRelation(__isl_take isl_map
*NewAccessRelation
);
1078 /// Return whether the MemoryyAccess is a partial access. That is, the access
1079 /// is not executed in some instances of the parent statement's domain.
1080 bool isLatestPartialAccess() const;
1082 /// Mark this a reduction like access
1083 void markAsReductionLike(ReductionType RT
) { RedType
= RT
; }
1085 /// Align the parameters in the access relation to the scop context
1086 void realignParams();
1088 /// Update the dimensionality of the memory access.
1090 /// During scop construction some memory accesses may not be constructed with
1091 /// their full dimensionality, but outer dimensions may have been omitted if
1092 /// they took the value 'zero'. By updating the dimensionality of the
1093 /// statement we add additional zero-valued dimensions to match the
1094 /// dimensionality of the ScopArrayInfo object that belongs to this memory
1096 void updateDimensionality();
1098 /// Get identifier for the memory access.
1100 /// This identifier is unique for all accesses that belong to the same scop
1102 isl::id
getId() const;
1104 /// Print the MemoryAccess.
1106 /// @param OS The output stream the MemoryAccess is printed to.
1107 void print(raw_ostream
&OS
) const;
1109 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1110 /// Print the MemoryAccess to stderr.
1114 /// Is the memory access affine?
1115 bool isAffine() const { return IsAffine
; }
1118 llvm::raw_ostream
&operator<<(llvm::raw_ostream
&OS
,
1119 MemoryAccess::ReductionType RT
);
1121 /// Ordered list type to hold accesses.
1122 using MemoryAccessList
= std::forward_list
<MemoryAccess
*>;
1124 /// Helper structure for invariant memory accesses.
1125 struct InvariantAccess
{
1126 /// The memory access that is (partially) invariant.
1129 /// The context under which the access is not invariant.
1130 isl_set
*NonHoistableCtx
;
1133 /// Ordered container type to hold invariant accesses.
1134 using InvariantAccessesTy
= SmallVector
<InvariantAccess
, 8>;
1136 /// Type for equivalent invariant accesses and their domain context.
1137 struct InvariantEquivClassTy
{
1139 /// The pointer that identifies this equivalence class
1140 const SCEV
*IdentifyingPointer
;
1142 /// Memory accesses now treated invariant
1144 /// These memory accesses access the pointer location that identifies
1145 /// this equivalence class. They are treated as invariant and hoisted during
1146 /// code generation.
1147 MemoryAccessList InvariantAccesses
;
1149 /// The execution context under which the memory location is accessed
1151 /// It is the union of the execution domains of the memory accesses in the
1152 /// InvariantAccesses list.
1153 isl_set
*ExecutionContext
;
1155 /// The type of the invariant access
1157 /// It is used to differentiate between differently typed invariant loads from
1158 /// the same location.
1162 /// Type for invariant accesses equivalence classes.
1163 using InvariantEquivClassesTy
= SmallVector
<InvariantEquivClassTy
, 8>;
1165 /// Statement of the Scop
1167 /// A Scop statement represents an instruction in the Scop.
1169 /// It is further described by its iteration domain, its schedule and its data
1171 /// At the moment every statement represents a single basic block of LLVM-IR.
1174 ScopStmt(const ScopStmt
&) = delete;
1175 const ScopStmt
&operator=(const ScopStmt
&) = delete;
1177 /// Create the ScopStmt from a BasicBlock.
1178 ScopStmt(Scop
&parent
, BasicBlock
&bb
, Loop
*SurroundingLoop
,
1179 std::vector
<Instruction
*> Instructions
);
1181 /// Create an overapproximating ScopStmt for the region @p R.
1182 ScopStmt(Scop
&parent
, Region
&R
, Loop
*SurroundingLoop
);
1184 /// Create a copy statement.
1186 /// @param Stmt The parent statement.
1187 /// @param SourceRel The source location.
1188 /// @param TargetRel The target location.
1189 /// @param Domain The original domain under which the copy statement would
1191 ScopStmt(Scop
&parent
, __isl_take isl_map
*SourceRel
,
1192 __isl_take isl_map
*TargetRel
, __isl_take isl_set
*Domain
);
1194 /// Initialize members after all MemoryAccesses have been added.
1195 void init(LoopInfo
&LI
);
1198 /// Polyhedral description
1201 /// The Scop containing this ScopStmt.
1204 /// The domain under which this statement is not modeled precisely.
1206 /// The invalid domain for a statement describes all parameter combinations
1207 /// under which the statement looks to be executed but is in fact not because
1208 /// some assumption/restriction makes the statement/scop invalid.
1209 isl_set
*InvalidDomain
;
1211 /// The iteration domain describes the set of iterations for which this
1212 /// statement is executed.
1215 /// for (i = 0; i < 100 + b; ++i)
1216 /// for (j = 0; j < i; ++j)
1219 /// 'S' is executed for different values of i and j. A vector of all
1220 /// induction variables around S (i, j) is called iteration vector.
1221 /// The domain describes the set of possible iteration vectors.
1223 /// In this case it is:
1225 /// Domain: 0 <= i <= 100 + b
1228 /// A pair of statement and iteration vector (S, (5,3)) is called statement
1232 /// The memory accesses of this statement.
1234 /// The only side effects of a statement are its memory accesses.
1235 typedef SmallVector
<MemoryAccess
*, 8> MemoryAccessVec
;
1236 MemoryAccessVec MemAccs
;
1238 /// Mapping from instructions to (scalar) memory accesses.
1239 DenseMap
<const Instruction
*, MemoryAccessList
> InstructionToAccess
;
1241 /// The set of values defined elsewhere required in this ScopStmt and
1242 /// their MemoryKind::Value READ MemoryAccesses.
1243 DenseMap
<Value
*, MemoryAccess
*> ValueReads
;
1245 /// The set of values defined in this ScopStmt that are required
1246 /// elsewhere, mapped to their MemoryKind::Value WRITE MemoryAccesses.
1247 DenseMap
<Instruction
*, MemoryAccess
*> ValueWrites
;
1249 /// Map from PHI nodes to its incoming value when coming from this
1252 /// Non-affine subregions can have multiple exiting blocks that are incoming
1253 /// blocks of the PHI nodes. This map ensures that there is only one write
1254 /// operation for the complete subregion. A PHI selecting the relevant value
1255 /// will be inserted.
1256 DenseMap
<PHINode
*, MemoryAccess
*> PHIWrites
;
1258 /// Map from PHI nodes to its read access in this statement.
1259 DenseMap
<PHINode
*, MemoryAccess
*> PHIReads
;
1263 /// A SCoP statement represents either a basic block (affine/precise case) or
1264 /// a whole region (non-affine case).
1266 /// Only one of the following two members will therefore be set and indicate
1267 /// which kind of statement this is.
1271 /// The BasicBlock represented by this statement (in the affine case).
1274 /// The region represented by this statement (in the non-affine case).
1279 /// The isl AST build for the new generated AST.
1280 isl_ast_build
*Build
;
1282 SmallVector
<Loop
*, 4> NestLoops
;
1284 std::string BaseName
;
1286 /// The closest loop that contains this statement.
1287 Loop
*SurroundingLoop
;
1289 /// Vector for Instructions in a BB.
1290 std::vector
<Instruction
*> Instructions
;
1292 /// Build the statement.
1296 /// Fill NestLoops with loops surrounding this statement.
1297 void collectSurroundingLoops();
1299 /// Build the access relation of all memory accesses.
1300 void buildAccessRelations();
1302 /// Detect and mark reductions in the ScopStmt
1303 void checkForReductions();
1305 /// Collect loads which might form a reduction chain with @p StoreMA
1307 collectCandiateReductionLoads(MemoryAccess
*StoreMA
,
1308 llvm::SmallVectorImpl
<MemoryAccess
*> &Loads
);
1311 /// Remove @p MA from dictionaries pointing to them.
1312 void removeAccessData(MemoryAccess
*MA
);
1317 /// Get an isl_ctx pointer.
1318 isl_ctx
*getIslCtx() const;
1320 /// Get the iteration domain of this ScopStmt.
1322 /// @return The iteration domain of this ScopStmt.
1323 __isl_give isl_set
*getDomain() const;
1325 /// Get the space of the iteration domain
1327 /// @return The space of the iteration domain
1328 __isl_give isl_space
*getDomainSpace() const;
1330 /// Get the id of the iteration domain space
1332 /// @return The id of the iteration domain space
1333 __isl_give isl_id
*getDomainId() const;
1335 /// Get an isl string representing this domain.
1336 std::string
getDomainStr() const;
1338 /// Get the schedule function of this ScopStmt.
1340 /// @return The schedule function of this ScopStmt, if it does not contain
1341 /// extension nodes, and nullptr, otherwise.
1342 __isl_give isl_map
*getSchedule() const;
1344 /// Get an isl string representing this schedule.
1346 /// @return An isl string representing this schedule, if it does not contain
1347 /// extension nodes, and an empty string, otherwise.
1348 std::string
getScheduleStr() const;
1350 /// Get the invalid domain for this statement.
1351 __isl_give isl_set
*getInvalidDomain() const {
1352 return isl_set_copy(InvalidDomain
);
1355 /// Get the invalid context for this statement.
1356 __isl_give isl_set
*getInvalidContext() const {
1357 return isl_set_params(getInvalidDomain());
1360 /// Set the invalid context for this statement to @p ID.
1361 void setInvalidDomain(__isl_take isl_set
*ID
);
1363 /// Get the BasicBlock represented by this ScopStmt (if any).
1365 /// @return The BasicBlock represented by this ScopStmt, or null if the
1366 /// statement represents a region.
1367 BasicBlock
*getBasicBlock() const { return BB
; }
1369 /// Return true if this statement represents a single basic block.
1370 bool isBlockStmt() const { return BB
!= nullptr; }
1372 /// Return true if this is a copy statement.
1373 bool isCopyStmt() const { return BB
== nullptr && R
== nullptr; }
1375 /// Get the region represented by this ScopStmt (if any).
1377 /// @return The region represented by this ScopStmt, or null if the statement
1378 /// represents a basic block.
1379 Region
*getRegion() const { return R
; }
1381 /// Return true if this statement represents a whole region.
1382 bool isRegionStmt() const { return R
!= nullptr; }
1384 /// Return a BasicBlock from this statement.
1386 /// For block statements, it returns the BasicBlock itself. For subregion
1387 /// statements, return its entry block.
1388 BasicBlock
*getEntryBlock() const;
1390 /// Return whether @p L is boxed within this statement.
1391 bool contains(const Loop
*L
) const {
1392 // Block statements never contain loops.
1396 return getRegion()->contains(L
);
1399 /// Return whether this statement contains @p BB.
1400 bool contains(BasicBlock
*BB
) const {
1404 return BB
== getBasicBlock();
1405 return getRegion()->contains(BB
);
1408 /// Return whether this statement contains @p Inst.
1409 bool contains(Instruction
*Inst
) const {
1412 return contains(Inst
->getParent());
1415 /// Return the closest innermost loop that contains this statement, but is not
1416 /// contained in it.
1418 /// For block statement, this is just the loop that contains the block. Region
1419 /// statements can contain boxed loops, so getting the loop of one of the
1420 /// region's BBs might return such an inner loop. For instance, the region's
1421 /// entry could be a header of a loop, but the region might extend to BBs
1422 /// after the loop exit. Similarly, the region might only contain parts of the
1423 /// loop body and still include the loop header.
1425 /// Most of the time the surrounding loop is the top element of #NestLoops,
1426 /// except when it is empty. In that case it return the loop that the whole
1427 /// SCoP is contained in. That can be nullptr if there is no such loop.
1428 Loop
*getSurroundingLoop() const {
1429 assert(!isCopyStmt() &&
1430 "No surrounding loop for artificially created statements");
1431 return SurroundingLoop
;
1434 /// Return true if this statement does not contain any accesses.
1435 bool isEmpty() const { return MemAccs
.empty(); }
1437 /// Find all array accesses for @p Inst.
1439 /// @param Inst The instruction accessing an array.
1441 /// @return A list of array accesses (MemoryKind::Array) accessed by @p Inst.
1442 /// If there is no such access, it returns nullptr.
1443 const MemoryAccessList
*
1444 lookupArrayAccessesFor(const Instruction
*Inst
) const {
1445 auto It
= InstructionToAccess
.find(Inst
);
1446 if (It
== InstructionToAccess
.end())
1448 if (It
->second
.empty())
1453 /// Return the only array access for @p Inst, if existing.
1455 /// @param Inst The instruction for which to look up the access.
1456 /// @returns The unique array memory access related to Inst or nullptr if
1457 /// no array access exists
1458 MemoryAccess
*getArrayAccessOrNULLFor(const Instruction
*Inst
) const {
1459 auto It
= InstructionToAccess
.find(Inst
);
1460 if (It
== InstructionToAccess
.end())
1463 MemoryAccess
*ArrayAccess
= nullptr;
1465 for (auto Access
: It
->getSecond()) {
1466 if (!Access
->isArrayKind())
1469 assert(!ArrayAccess
&& "More then one array access for instruction");
1471 ArrayAccess
= Access
;
1477 /// Return the only array access for @p Inst.
1479 /// @param Inst The instruction for which to look up the access.
1480 /// @returns The unique array memory access related to Inst.
1481 MemoryAccess
&getArrayAccessFor(const Instruction
*Inst
) const {
1482 MemoryAccess
*ArrayAccess
= getArrayAccessOrNULLFor(Inst
);
1484 assert(ArrayAccess
&& "No array access found for instruction!");
1485 return *ArrayAccess
;
1488 /// Return the MemoryAccess that writes the value of an instruction
1489 /// defined in this statement, or nullptr if not existing, respectively
1491 MemoryAccess
*lookupValueWriteOf(Instruction
*Inst
) const {
1492 assert((isRegionStmt() && R
->contains(Inst
)) ||
1493 (!isRegionStmt() && Inst
->getParent() == BB
));
1494 return ValueWrites
.lookup(Inst
);
1497 /// Return the MemoryAccess that reloads a value, or nullptr if not
1498 /// existing, respectively not yet added.
1499 MemoryAccess
*lookupValueReadOf(Value
*Inst
) const {
1500 return ValueReads
.lookup(Inst
);
1503 /// Return the MemoryAccess that loads a PHINode value, or nullptr if not
1504 /// existing, respectively not yet added.
1505 MemoryAccess
*lookupPHIReadOf(PHINode
*PHI
) const {
1506 assert(isBlockStmt() || R
->getEntry() == PHI
->getParent());
1507 return PHIReads
.lookup(PHI
);
1510 /// Return the PHI write MemoryAccess for the incoming values from any
1511 /// basic block in this ScopStmt, or nullptr if not existing,
1512 /// respectively not yet added.
1513 MemoryAccess
*lookupPHIWriteOf(PHINode
*PHI
) const {
1514 assert(isBlockStmt() || R
->getExit() == PHI
->getParent());
1515 return PHIWrites
.lookup(PHI
);
1518 /// Return the input access of the value, or null if no such MemoryAccess
1521 /// The input access is the MemoryAccess that makes an inter-statement value
1522 /// available in this statement by reading it at the start of this statement.
1523 /// This can be a MemoryKind::Value if defined in another statement or a
1524 /// MemoryKind::PHI if the value is a PHINode in this statement.
1525 MemoryAccess
*lookupInputAccessOf(Value
*Val
) const {
1526 if (isa
<PHINode
>(Val
))
1527 if (auto InputMA
= lookupPHIReadOf(cast
<PHINode
>(Val
))) {
1528 assert(!lookupValueReadOf(Val
) && "input accesses must be unique; a "
1529 "statement cannot read a .s2a and "
1530 ".phiops simultaneously");
1534 if (auto *InputMA
= lookupValueReadOf(Val
))
1540 /// Add @p Access to this statement's list of accesses.
1541 void addAccess(MemoryAccess
*Access
);
1543 /// Remove a MemoryAccess from this statement.
1545 /// Note that scalar accesses that are caused by MA will
1546 /// be eliminated too.
1547 void removeMemoryAccess(MemoryAccess
*MA
);
1549 /// Remove @p MA from this statement.
1551 /// In contrast to removeMemoryAccess(), no other access will be eliminated.
1552 void removeSingleMemoryAccess(MemoryAccess
*MA
);
1554 typedef MemoryAccessVec::iterator iterator
;
1555 typedef MemoryAccessVec::const_iterator const_iterator
;
1557 iterator
begin() { return MemAccs
.begin(); }
1558 iterator
end() { return MemAccs
.end(); }
1559 const_iterator
begin() const { return MemAccs
.begin(); }
1560 const_iterator
end() const { return MemAccs
.end(); }
1561 size_t size() const { return MemAccs
.size(); }
1563 unsigned getNumIterators() const;
1565 Scop
*getParent() { return &Parent
; }
1566 const Scop
*getParent() const { return &Parent
; }
1568 const std::vector
<Instruction
*> &getInstructions() const {
1569 return Instructions
;
1572 /// Set the list of instructions for this statement. It replaces the current
1574 void setInstructions(ArrayRef
<Instruction
*> Range
) {
1575 Instructions
.assign(Range
.begin(), Range
.end());
1578 std::vector
<Instruction
*>::const_iterator
insts_begin() const {
1579 return Instructions
.begin();
1582 std::vector
<Instruction
*>::const_iterator
insts_end() const {
1583 return Instructions
.end();
1586 /// The range of instructions in this statement.
1587 llvm::iterator_range
<std::vector
<Instruction
*>::const_iterator
>
1589 return {insts_begin(), insts_end()};
1592 /// Insert an instruction before all other instructions in this statement.
1593 void prependInstruction(Instruction
*Inst
) {
1594 assert(isBlockStmt() && "Only block statements support instruction lists");
1595 Instructions
.insert(Instructions
.begin(), Inst
);
1598 const char *getBaseName() const;
1600 /// Set the isl AST build.
1601 void setAstBuild(__isl_keep isl_ast_build
*B
) { Build
= B
; }
1603 /// Get the isl AST build.
1604 __isl_keep isl_ast_build
*getAstBuild() const { return Build
; }
1606 /// Restrict the domain of the statement.
1608 /// @param NewDomain The new statement domain.
1609 void restrictDomain(__isl_take isl_set
*NewDomain
);
1611 /// Get the loop for a dimension.
1613 /// @param Dimension The dimension of the induction variable
1614 /// @return The loop at a certain dimension.
1615 Loop
*getLoopForDimension(unsigned Dimension
) const;
1617 /// Align the parameters in the statement to the scop context
1618 void realignParams();
1620 /// Print the ScopStmt.
1622 /// @param OS The output stream the ScopStmt is printed to.
1623 /// @param PrintInstructions Whether to print the statement's instructions as
1625 void print(raw_ostream
&OS
, bool PrintInstructions
) const;
1627 /// Print the instructions in ScopStmt.
1629 void printInstructions(raw_ostream
&OS
) const;
1631 /// Check whether there is a value read access for @p V in this statement, and
1632 /// if not, create one.
1634 /// This allows to add MemoryAccesses after the initial creation of the Scop
1637 /// @return The already existing or newly created MemoryKind::Value READ
1640 /// @see ScopBuilder::ensureValueRead(Value*,ScopStmt*)
1641 MemoryAccess
*ensureValueRead(Value
*V
);
1643 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1644 /// Print the ScopStmt to stderr.
1649 /// Print ScopStmt S to raw_ostream O.
1650 raw_ostream
&operator<<(raw_ostream
&O
, const ScopStmt
&S
);
1652 /// Static Control Part
1654 /// A Scop is the polyhedral representation of a control flow region detected
1655 /// by the Scop detection. It is generated by translating the LLVM-IR and
1656 /// abstracting its effects.
1658 /// A Scop consists of a set of:
1660 /// * A set of statements executed in the Scop.
1662 /// * A set of global parameters
1663 /// Those parameters are scalar integer values, which are constant during
1667 /// This context contains information about the values the parameters
1668 /// can take and relations between different parameters.
1671 /// Type to represent a pair of minimal/maximal access to an array.
1672 using MinMaxAccessTy
= std::pair
<isl_pw_multi_aff
*, isl_pw_multi_aff
*>;
1674 /// Vector of minimal/maximal accesses to different arrays.
1675 using MinMaxVectorTy
= SmallVector
<MinMaxAccessTy
, 4>;
1677 /// Pair of minimal/maximal access vectors representing
1678 /// read write and read only accesses
1679 using MinMaxVectorPairTy
= std::pair
<MinMaxVectorTy
, MinMaxVectorTy
>;
1681 /// Vector of pair of minimal/maximal access vectors representing
1682 /// non read only and read only accesses for each alias group.
1683 using MinMaxVectorPairVectorTy
= SmallVector
<MinMaxVectorPairTy
, 4>;
1686 Scop(const Scop
&) = delete;
1687 const Scop
&operator=(const Scop
&) = delete;
1689 ScalarEvolution
*SE
;
1691 /// The underlying Region.
1694 /// The name of the SCoP (identical to the regions name)
1697 /// The ID to be assigned to the next Scop in a function
1698 static int NextScopID
;
1700 /// The name of the function currently under consideration
1701 static std::string CurrentFunc
;
1703 // Access functions of the SCoP.
1705 // This owns all the MemoryAccess objects of the Scop created in this pass.
1706 AccFuncVector AccessFunctions
;
1708 /// Flag to indicate that the scheduler actually optimized the SCoP.
1711 /// True if the underlying region has a single exiting block.
1712 bool HasSingleExitEdge
;
1714 /// Flag to remember if the SCoP contained an error block or not.
1718 unsigned MaxLoopDepth
;
1720 /// Number of copy statements.
1721 unsigned CopyStmtsNum
;
1723 /// Flag to indicate if the Scop is to be skipped.
1726 typedef std::list
<ScopStmt
> StmtSet
;
1727 /// The statements in this Scop.
1730 /// Parameters of this Scop
1731 ParameterSetTy Parameters
;
1733 /// Mapping from parameters to their ids.
1734 DenseMap
<const SCEV
*, isl_id
*> ParameterIds
;
1736 /// The context of the SCoP created during SCoP detection.
1737 ScopDetection::DetectionContext
&DC
;
1739 /// OptimizationRemarkEmitter object for displaying diagnostic remarks
1740 OptimizationRemarkEmitter
&ORE
;
1744 /// We need a shared_ptr with reference counter to delete the context when all
1745 /// isl objects are deleted. We will distribute the shared_ptr to all objects
1746 /// that use the context to create isl objects, and increase the reference
1747 /// counter. By doing this, we guarantee that the context is deleted when we
1748 /// delete the last object that creates isl objects with the context.
1749 std::shared_ptr
<isl_ctx
> IslCtx
;
1751 /// A map from basic blocks to vector of SCoP statements. Currently this
1752 /// vector comprises only of a single statement.
1753 DenseMap
<BasicBlock
*, std::vector
<ScopStmt
*>> StmtMap
;
1755 /// A map from basic blocks to their domains.
1756 DenseMap
<BasicBlock
*, isl::set
> DomainMap
;
1758 /// Constraints on parameters.
1761 /// The affinator used to translate SCEVs to isl expressions.
1762 SCEVAffinator Affinator
;
1764 typedef std::map
<std::pair
<AssertingVH
<const Value
>, MemoryKind
>,
1765 std::unique_ptr
<ScopArrayInfo
>>
1768 typedef StringMap
<std::unique_ptr
<ScopArrayInfo
>> ArrayNameMapTy
;
1770 typedef SetVector
<ScopArrayInfo
*> ArrayInfoSetTy
;
1772 /// A map to remember ScopArrayInfo objects for all base pointers.
1774 /// As PHI nodes may have two array info objects associated, we add a flag
1775 /// that distinguishes between the PHI node specific ArrayInfo object
1776 /// and the normal one.
1777 ArrayInfoMapTy ScopArrayInfoMap
;
1779 /// A map to remember ScopArrayInfo objects for all names of memory
1781 ArrayNameMapTy ScopArrayNameMap
;
1783 /// A set to remember ScopArrayInfo objects.
1784 /// @see Scop::ScopArrayInfoMap
1785 ArrayInfoSetTy ScopArrayInfoSet
;
1787 /// The assumptions under which this scop was built.
1789 /// When constructing a scop sometimes the exact representation of a statement
1790 /// or condition would be very complex, but there is a common case which is a
1791 /// lot simpler, but which is only valid under certain assumptions. The
1792 /// assumed context records the assumptions taken during the construction of
1793 /// this scop and that need to be code generated as a run-time test.
1794 isl_set
*AssumedContext
;
1796 /// The restrictions under which this SCoP was built.
1798 /// The invalid context is similar to the assumed context as it contains
1799 /// constraints over the parameters. However, while we need the constraints
1800 /// in the assumed context to be "true" the constraints in the invalid context
1801 /// need to be "false". Otherwise they behave the same.
1802 isl_set
*InvalidContext
;
1804 /// Helper struct to remember assumptions.
1807 /// The kind of the assumption (e.g., WRAPPING).
1808 AssumptionKind Kind
;
1810 /// Flag to distinguish assumptions and restrictions.
1811 AssumptionSign Sign
;
1813 /// The valid/invalid context if this is an assumption/restriction.
1816 /// The location that caused this assumption.
1819 /// An optional block whose domain can simplify the assumption.
1823 /// Collection to hold taken assumptions.
1825 /// There are two reasons why we want to record assumptions first before we
1826 /// add them to the assumed/invalid context:
1827 /// 1) If the SCoP is not profitable or otherwise invalid without the
1828 /// assumed/invalid context we do not have to compute it.
1829 /// 2) Information about the context are gathered rather late in the SCoP
1830 /// construction (basically after we know all parameters), thus the user
1831 /// might see overly complicated assumptions to be taken while they will
1832 /// only be simplified later on.
1833 SmallVector
<Assumption
, 8> RecordedAssumptions
;
1835 /// The schedule of the SCoP
1837 /// The schedule of the SCoP describes the execution order of the statements
1838 /// in the scop by assigning each statement instance a possibly
1839 /// multi-dimensional execution time. The schedule is stored as a tree of
1842 /// The most common nodes in a schedule tree are so-called band nodes. Band
1843 /// nodes map statement instances into a multi dimensional schedule space.
1844 /// This space can be seen as a multi-dimensional clock.
1848 /// <S,(5,4)> may be mapped to (5,4) by this schedule:
1850 /// s0 = i (Year of execution)
1851 /// s1 = j (Day of execution)
1853 /// or to (9, 20) by this schedule:
1855 /// s0 = i + j (Year of execution)
1856 /// s1 = 20 (Day of execution)
1858 /// The order statement instances are executed is defined by the
1859 /// schedule vectors they are mapped to. A statement instance
1860 /// <A, (i, j, ..)> is executed before a statement instance <B, (i', ..)>, if
1861 /// the schedule vector of A is lexicographic smaller than the schedule
1864 /// Besides band nodes, schedule trees contain additional nodes that specify
1865 /// a textual ordering between two subtrees or filter nodes that filter the
1866 /// set of statement instances that will be scheduled in a subtree. There
1867 /// are also several other nodes. A full description of the different nodes
1868 /// in a schedule tree is given in the isl manual.
1869 isl_schedule
*Schedule
;
1871 /// The set of minimal/maximal accesses for each alias group.
1873 /// When building runtime alias checks we look at all memory instructions and
1874 /// build so called alias groups. Each group contains a set of accesses to
1875 /// different base arrays which might alias with each other. However, between
1876 /// alias groups there is no aliasing possible.
1878 /// In a program with int and float pointers annotated with tbaa information
1879 /// we would probably generate two alias groups, one for the int pointers and
1880 /// one for the float pointers.
1882 /// During code generation we will create a runtime alias check for each alias
1883 /// group to ensure the SCoP is executed in an alias free environment.
1884 MinMaxVectorPairVectorTy MinMaxAliasGroups
;
1886 /// Mapping from invariant loads to the representing invariant load of
1887 /// their equivalence class.
1888 ValueToValueMap InvEquivClassVMap
;
1890 /// List of invariant accesses.
1891 InvariantEquivClassesTy InvariantEquivClasses
;
1893 /// The smallest array index not yet assigned.
1896 /// The smallest statement index not yet assigned.
1899 /// A number that uniquely represents a Scop within its function
1902 /// List of all uses (i.e. read MemoryAccesses) for a MemoryKind::Value
1904 DenseMap
<const ScopArrayInfo
*, SmallVector
<MemoryAccess
*, 4>> ValueUseAccs
;
1906 /// List of all incoming values (write MemoryAccess) of a MemoryKind::PHI or
1907 /// MemoryKind::ExitPHI scalar.
1908 DenseMap
<const ScopArrayInfo
*, SmallVector
<MemoryAccess
*, 4>>
1911 /// Return the ID for a new Scop within a function
1912 static int getNextID(std::string ParentFunc
);
1914 /// Scop constructor; invoked from ScopBuilder::buildScop.
1915 Scop(Region
&R
, ScalarEvolution
&SE
, LoopInfo
&LI
,
1916 ScopDetection::DetectionContext
&DC
, OptimizationRemarkEmitter
&ORE
);
1920 /// Initialize this ScopBuilder.
1921 void init(AliasAnalysis
&AA
, AssumptionCache
&AC
, DominatorTree
&DT
,
1924 /// Propagate domains that are known due to graph properties.
1926 /// As a CFG is mostly structured we use the graph properties to propagate
1927 /// domains without the need to compute all path conditions. In particular, if
1928 /// a block A dominates a block B and B post-dominates A we know that the
1929 /// domain of B is a superset of the domain of A. As we do not have
1930 /// post-dominator information available here we use the less precise region
1931 /// information. Given a region R, we know that the exit is always executed if
1932 /// the entry was executed, thus the domain of the exit is a superset of the
1933 /// domain of the entry. In case the exit can only be reached from within the
1934 /// region the domains are in fact equal. This function will use this property
1935 /// to avoid the generation of condition constraints that determine when a
1936 /// branch is taken. If @p BB is a region entry block we will propagate its
1937 /// domain to the region exit block. Additionally, we put the region exit
1938 /// block in the @p FinishedExitBlocks set so we can later skip edges from
1939 /// within the region to that block.
1941 /// @param BB The block for which the domain is currently
1943 /// @param BBLoop The innermost affine loop surrounding @p BB.
1944 /// @param FinishedExitBlocks Set of region exits the domain was set for.
1945 /// @param LI The LoopInfo for the current function.
1946 /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current
1948 void propagateDomainConstraintsToRegionExit(
1949 BasicBlock
*BB
, Loop
*BBLoop
,
1950 SmallPtrSetImpl
<BasicBlock
*> &FinishedExitBlocks
, LoopInfo
&LI
,
1951 DenseMap
<BasicBlock
*, isl::set
> &InvalidDomainMap
);
1953 /// Compute the union of predecessor domains for @p BB.
1955 /// To compute the union of all domains of predecessors of @p BB this
1956 /// function applies similar reasoning on the CFG structure as described for
1957 /// @see propagateDomainConstraintsToRegionExit
1959 /// @param BB The block for which the predecessor domains are collected.
1960 /// @param Domain The domain under which BB is executed.
1961 /// @param DT The DominatorTree for the current function.
1962 /// @param LI The LoopInfo for the current function.
1964 /// @returns The domain under which @p BB is executed.
1965 __isl_give isl_set
*
1966 getPredecessorDomainConstraints(BasicBlock
*BB
, __isl_keep isl_set
*Domain
,
1967 DominatorTree
&DT
, LoopInfo
&LI
);
1969 /// Add loop carried constraints to the header block of the loop @p L.
1971 /// @param L The loop to process.
1972 /// @param LI The LoopInfo for the current function.
1973 /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current
1976 /// @returns True if there was no problem and false otherwise.
1977 bool addLoopBoundsToHeaderDomain(
1978 Loop
*L
, LoopInfo
&LI
,
1979 DenseMap
<BasicBlock
*, isl::set
> &InvalidDomainMap
);
1981 /// Compute the branching constraints for each basic block in @p R.
1983 /// @param R The region we currently build branching conditions
1985 /// @param DT The DominatorTree for the current function.
1986 /// @param LI The LoopInfo for the current function.
1987 /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current
1990 /// @returns True if there was no problem and false otherwise.
1991 bool buildDomainsWithBranchConstraints(
1992 Region
*R
, DominatorTree
&DT
, LoopInfo
&LI
,
1993 DenseMap
<BasicBlock
*, isl::set
> &InvalidDomainMap
);
1995 /// Propagate the domain constraints through the region @p R.
1997 /// @param R The region we currently build branching conditions
1999 /// @param DT The DominatorTree for the current function.
2000 /// @param LI The LoopInfo for the current function.
2001 /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current
2004 /// @returns True if there was no problem and false otherwise.
2005 bool propagateDomainConstraints(
2006 Region
*R
, DominatorTree
&DT
, LoopInfo
&LI
,
2007 DenseMap
<BasicBlock
*, isl::set
> &InvalidDomainMap
);
2009 /// Propagate invalid domains of statements through @p R.
2011 /// This method will propagate invalid statement domains through @p R and at
2012 /// the same time add error block domains to them. Additionally, the domains
2013 /// of error statements and those only reachable via error statements will be
2014 /// replaced by an empty set. Later those will be removed completely.
2016 /// @param R The currently traversed region.
2017 /// @param DT The DominatorTree for the current function.
2018 /// @param LI The LoopInfo for the current function.
2019 /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current
2022 /// @returns True if there was no problem and false otherwise.
2023 bool propagateInvalidStmtDomains(
2024 Region
*R
, DominatorTree
&DT
, LoopInfo
&LI
,
2025 DenseMap
<BasicBlock
*, isl::set
> &InvalidDomainMap
);
2027 /// Compute the domain for each basic block in @p R.
2029 /// @param R The region we currently traverse.
2030 /// @param DT The DominatorTree for the current function.
2031 /// @param LI The LoopInfo for the current function.
2032 /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current
2035 /// @returns True if there was no problem and false otherwise.
2036 bool buildDomains(Region
*R
, DominatorTree
&DT
, LoopInfo
&LI
,
2037 DenseMap
<BasicBlock
*, isl::set
> &InvalidDomainMap
);
2039 /// Add parameter constraints to @p C that imply a non-empty domain.
2040 __isl_give isl_set
*addNonEmptyDomainConstraints(__isl_take isl_set
*C
) const;
2042 /// Return the access for the base ptr of @p MA if any.
2043 MemoryAccess
*lookupBasePtrAccess(MemoryAccess
*MA
);
2045 /// Check if the base ptr of @p MA is in the SCoP but not hoistable.
2046 bool hasNonHoistableBasePtrInScop(MemoryAccess
*MA
, isl::union_map Writes
);
2048 /// Create equivalence classes for required invariant accesses.
2050 /// These classes will consolidate multiple required invariant loads from the
2051 /// same address in order to keep the number of dimensions in the SCoP
2052 /// description small. For each such class equivalence class only one
2053 /// representing element, hence one required invariant load, will be chosen
2054 /// and modeled as parameter. The method
2055 /// Scop::getRepresentingInvariantLoadSCEV() will replace each element from an
2056 /// equivalence class with the representing element that is modeled. As a
2057 /// consequence Scop::getIdForParam() will only return an id for the
2058 /// representing element of each equivalence class, thus for each required
2059 /// invariant location.
2060 void buildInvariantEquivalenceClasses();
2062 /// Return the context under which the access cannot be hoisted.
2064 /// @param Access The access to check.
2065 /// @param Writes The set of all memory writes in the scop.
2067 /// @return Return the context under which the access cannot be hoisted or a
2068 /// nullptr if it cannot be hoisted at all.
2069 isl::set
getNonHoistableCtx(MemoryAccess
*Access
, isl::union_map Writes
);
2071 /// Verify that all required invariant loads have been hoisted.
2073 /// Invariant load hoisting is not guaranteed to hoist all loads that were
2074 /// assumed to be scop invariant during scop detection. This function checks
2075 /// for cases where the hoisting failed, but where it would have been
2076 /// necessary for our scop modeling to be correct. In case of insufficient
2077 /// hoisting the scop is marked as invalid.
2079 /// In the example below Bound[1] is required to be invariant:
2081 /// for (int i = 1; i < Bound[0]; i++)
2082 /// for (int j = 1; j < Bound[1]; j++)
2085 void verifyInvariantLoads();
2087 /// Hoist invariant memory loads and check for required ones.
2089 /// We first identify "common" invariant loads, thus loads that are invariant
2090 /// and can be hoisted. Then we check if all required invariant loads have
2091 /// been identified as (common) invariant. A load is a required invariant load
2092 /// if it was assumed to be invariant during SCoP detection, e.g., to assume
2093 /// loop bounds to be affine or runtime alias checks to be placeable. In case
2094 /// a required invariant load was not identified as (common) invariant we will
2095 /// drop this SCoP. An example for both "common" as well as required invariant
2096 /// loads is given below:
2098 /// for (int i = 1; i < *LB[0]; i++)
2099 /// for (int j = 1; j < *LB[1]; j++)
2100 /// A[i][j] += A[0][0] + (*V);
2102 /// Common inv. loads: V, A[0][0], LB[0], LB[1]
2103 /// Required inv. loads: LB[0], LB[1], (V, if it may alias with A or LB)
2105 void hoistInvariantLoads();
2107 /// Canonicalize arrays with base pointers from the same equivalence class.
2109 /// Some context: in our normal model we assume that each base pointer is
2110 /// related to a single specific memory region, where memory regions
2111 /// associated with different base pointers are disjoint. Consequently we do
2112 /// not need to compute additional data dependences that model possible
2113 /// overlaps of these memory regions. To verify our assumption we compute
2114 /// alias checks that verify that modeled arrays indeed do not overlap. In
2115 /// case an overlap is detected the runtime check fails and we fall back to
2116 /// the original code.
2118 /// In case of arrays where the base pointers are know to be identical,
2119 /// because they are dynamically loaded by accesses that are in the same
2120 /// invariant load equivalence class, such run-time alias check would always
2123 /// This function makes sure that we do not generate consistently failing
2124 /// run-time checks for code that contains distinct arrays with known
2125 /// equivalent base pointers. It identifies for each invariant load
2126 /// equivalence class a single canonical array and canonicalizes all memory
2127 /// accesses that reference arrays that have base pointers that are known to
2128 /// be equal to the base pointer of such a canonical array to this canonical
2131 /// We currently do not canonicalize arrays for which certain memory accesses
2132 /// have been hoisted as loop invariant.
2133 void canonicalizeDynamicBasePtrs();
2135 /// Add invariant loads listed in @p InvMAs with the domain of @p Stmt.
2136 void addInvariantLoads(ScopStmt
&Stmt
, InvariantAccessesTy
&InvMAs
);
2138 /// Create an id for @p Param and store it in the ParameterIds map.
2139 void createParameterId(const SCEV
*Param
);
2141 /// Build the Context of the Scop.
2142 void buildContext();
2144 /// Add user provided parameter constraints to context (source code).
2145 void addUserAssumptions(AssumptionCache
&AC
, DominatorTree
&DT
, LoopInfo
&LI
,
2146 DenseMap
<BasicBlock
*, isl::set
> &InvalidDomainMap
);
2148 /// Add user provided parameter constraints to context (command line).
2149 void addUserContext();
2151 /// Add the bounds of the parameters to the context.
2152 void addParameterBounds();
2154 /// Simplify the assumed and invalid context.
2155 void simplifyContexts();
2157 /// Get the representing SCEV for @p S if applicable, otherwise @p S.
2159 /// Invariant loads of the same location are put in an equivalence class and
2160 /// only one of them is chosen as a representing element that will be
2161 /// modeled as a parameter. The others have to be normalized, i.e.,
2162 /// replaced by the representing element of their equivalence class, in order
2163 /// to get the correct parameter value, e.g., in the SCEVAffinator.
2165 /// @param S The SCEV to normalize.
2167 /// @return The representing SCEV for invariant loads or @p S if none.
2168 const SCEV
*getRepresentingInvariantLoadSCEV(const SCEV
*S
);
2170 /// Create a new SCoP statement for @p BB.
2172 /// A new statement for @p BB will be created and added to the statement
2176 /// @param BB The basic block we build the statement for.
2177 /// @param SurroundingLoop The loop the created statement is contained in.
2178 /// @param Instructions The instructions in the basic block.
2179 void addScopStmt(BasicBlock
*BB
, Loop
*SurroundingLoop
,
2180 std::vector
<Instruction
*> Instructions
);
2182 /// Create a new SCoP statement for @p R.
2184 /// A new statement for @p R will be created and added to the statement vector
2187 /// @param R The region we build the statement for.
2188 /// @param SurroundingLoop The loop the created statement is contained in.
2189 void addScopStmt(Region
*R
, Loop
*SurroundingLoop
);
2191 /// Update access dimensionalities.
2193 /// When detecting memory accesses different accesses to the same array may
2194 /// have built with different dimensionality, as outer zero-values dimensions
2195 /// may not have been recognized as separate dimensions. This function goes
2196 /// again over all memory accesses and updates their dimensionality to match
2197 /// the dimensionality of the underlying ScopArrayInfo object.
2198 void updateAccessDimensionality();
2200 /// Fold size constants to the right.
2202 /// In case all memory accesses in a given dimension are multiplied with a
2203 /// common constant, we can remove this constant from the individual access
2204 /// functions and move it to the size of the memory access. We do this as this
2205 /// increases the size of the innermost dimension, consequently widens the
2206 /// valid range the array subscript in this dimension can evaluate to, and
2207 /// as a result increases the likelihood that our delinearization is
2213 /// S[i,j] -> A[2i][2j+1]
2214 /// S[i,j] -> A[2i][2j]
2219 /// S[i,j] -> A[i][2j+1]
2220 /// S[i,j] -> A[i][2j]
2222 /// Constants in outer dimensions can arise when the elements of a parametric
2223 /// multi-dimensional array are not elementary data types, but e.g.,
2225 void foldSizeConstantsToRight();
2227 /// Fold memory accesses to handle parametric offset.
2229 /// As a post-processing step, we 'fold' memory accesses to parametric
2230 /// offsets in the access functions. @see MemoryAccess::foldAccess for
2232 void foldAccessRelations();
2234 /// Assume that all memory accesses are within bounds.
2236 /// After we have built a model of all memory accesses, we need to assume
2237 /// that the model we built matches reality -- aka. all modeled memory
2238 /// accesses always remain within bounds. We do this as last step, after
2239 /// all memory accesses have been modeled and canonicalized.
2240 void assumeNoOutOfBounds();
2242 /// Remove statements from the list of scop statements.
2244 /// @param ShouldDelete A function that returns true if the statement passed
2245 /// to it should be deleted.
2246 void removeStmts(std::function
<bool(ScopStmt
&)> ShouldDelete
);
2248 /// Removes @p Stmt from the StmtMap.
2249 void removeFromStmtMap(ScopStmt
&Stmt
);
2251 /// Removes all statements where the entry block of the statement does not
2252 /// have a corresponding domain in the domain map.
2253 void removeStmtNotInDomainMap();
2255 /// Mark arrays that have memory accesses with FortranArrayDescriptor.
2256 void markFortranArrays();
2258 /// Finalize all access relations.
2260 /// When building up access relations, temporary access relations that
2261 /// correctly represent each individual access are constructed. However, these
2262 /// access relations can be inconsistent or non-optimal when looking at the
2263 /// set of accesses as a whole. This function finalizes the memory accesses
2264 /// and constructs a globally consistent state.
2265 void finalizeAccesses();
2267 /// Construct the schedule of this SCoP.
2269 /// @param LI The LoopInfo for the current function.
2270 void buildSchedule(LoopInfo
&LI
);
2272 /// A loop stack element to keep track of per-loop information during
2273 /// schedule construction.
2274 typedef struct LoopStackElement
{
2275 // The loop for which we keep information.
2278 // The (possibly incomplete) schedule for this loop.
2279 isl_schedule
*Schedule
;
2281 // The number of basic blocks in the current loop, for which a schedule has
2282 // already been constructed.
2283 unsigned NumBlocksProcessed
;
2285 LoopStackElement(Loop
*L
, __isl_give isl_schedule
*S
,
2286 unsigned NumBlocksProcessed
)
2287 : L(L
), Schedule(S
), NumBlocksProcessed(NumBlocksProcessed
) {}
2288 } LoopStackElementTy
;
2290 /// The loop stack used for schedule construction.
2292 /// The loop stack keeps track of schedule information for a set of nested
2293 /// loops as well as an (optional) 'nullptr' loop that models the outermost
2294 /// schedule dimension. The loops in a loop stack always have a parent-child
2295 /// relation where the loop at position n is the parent of the loop at
2297 typedef SmallVector
<LoopStackElementTy
, 4> LoopStackTy
;
2299 /// Construct schedule information for a given Region and add the
2300 /// derived information to @p LoopStack.
2302 /// Given a Region we derive schedule information for all RegionNodes
2303 /// contained in this region ensuring that the assigned execution times
2304 /// correctly model the existing control flow relations.
2306 /// @param R The region which to process.
2307 /// @param LoopStack A stack of loops that are currently under
2309 /// @param LI The LoopInfo for the current function.
2310 void buildSchedule(Region
*R
, LoopStackTy
&LoopStack
, LoopInfo
&LI
);
2312 /// Build Schedule for the region node @p RN and add the derived
2313 /// information to @p LoopStack.
2315 /// In case @p RN is a BasicBlock or a non-affine Region, we construct the
2316 /// schedule for this @p RN and also finalize loop schedules in case the
2317 /// current @p RN completes the loop.
2319 /// In case @p RN is a not-non-affine Region, we delegate the construction to
2320 /// buildSchedule(Region *R, ...).
2322 /// @param RN The RegionNode region traversed.
2323 /// @param LoopStack A stack of loops that are currently under
2325 /// @param LI The LoopInfo for the current function.
2326 void buildSchedule(RegionNode
*RN
, LoopStackTy
&LoopStack
, LoopInfo
&LI
);
2328 /// Collect all memory access relations of a given type.
2330 /// @param Predicate A predicate function that returns true if an access is
2331 /// of a given type.
2333 /// @returns The set of memory accesses in the scop that match the predicate.
2334 __isl_give isl_union_map
*
2335 getAccessesOfType(std::function
<bool(MemoryAccess
&)> Predicate
);
2337 /// @name Helper functions for printing the Scop.
2340 void printContext(raw_ostream
&OS
) const;
2341 void printArrayInfo(raw_ostream
&OS
) const;
2342 void printStatements(raw_ostream
&OS
, bool PrintInstructions
) const;
2343 void printAliasAssumptions(raw_ostream
&OS
) const;
2346 friend class ScopBuilder
;
2351 /// Get the count of copy statements added to this Scop.
2353 /// @return The count of copy statements added to this Scop.
2354 unsigned getCopyStmtsNum() { return CopyStmtsNum
; }
2356 /// Create a new copy statement.
2358 /// A new statement will be created and added to the statement vector.
2360 /// @param Stmt The parent statement.
2361 /// @param SourceRel The source location.
2362 /// @param TargetRel The target location.
2363 /// @param Domain The original domain under which the copy statement would
2365 ScopStmt
*addScopStmt(__isl_take isl_map
*SourceRel
,
2366 __isl_take isl_map
*TargetRel
,
2367 __isl_take isl_set
*Domain
);
2369 /// Add the access function to all MemoryAccess objects of the Scop
2370 /// created in this pass.
2371 void addAccessFunction(MemoryAccess
*Access
) {
2372 AccessFunctions
.emplace_back(Access
);
2375 /// Add metadata for @p Access.
2376 void addAccessData(MemoryAccess
*Access
);
2378 /// Remove the metadata stored for @p Access.
2379 void removeAccessData(MemoryAccess
*Access
);
2381 ScalarEvolution
*getSE() const;
2383 /// Get the count of parameters used in this Scop.
2385 /// @return The count of parameters used in this Scop.
2386 size_t getNumParams() const { return Parameters
.size(); }
2388 /// Take a list of parameters and add the new ones to the scop.
2389 void addParams(const ParameterSetTy
&NewParameters
);
2391 /// Return an iterator range containing the scop parameters.
2392 iterator_range
<ParameterSetTy::iterator
> parameters() const {
2393 return make_range(Parameters
.begin(), Parameters
.end());
2396 /// Return whether this scop is empty, i.e. contains no statements that
2397 /// could be executed.
2398 bool isEmpty() const { return Stmts
.empty(); }
2400 const StringRef
getName() const { return name
; }
2402 typedef ArrayInfoSetTy::iterator array_iterator
;
2403 typedef ArrayInfoSetTy::const_iterator const_array_iterator
;
2404 typedef iterator_range
<ArrayInfoSetTy::iterator
> array_range
;
2405 typedef iterator_range
<ArrayInfoSetTy::const_iterator
> const_array_range
;
2407 inline array_iterator
array_begin() { return ScopArrayInfoSet
.begin(); }
2409 inline array_iterator
array_end() { return ScopArrayInfoSet
.end(); }
2411 inline const_array_iterator
array_begin() const {
2412 return ScopArrayInfoSet
.begin();
2415 inline const_array_iterator
array_end() const {
2416 return ScopArrayInfoSet
.end();
2419 inline array_range
arrays() {
2420 return array_range(array_begin(), array_end());
2423 inline const_array_range
arrays() const {
2424 return const_array_range(array_begin(), array_end());
2427 /// Return the isl_id that represents a certain parameter.
2429 /// @param Parameter A SCEV that was recognized as a Parameter.
2431 /// @return The corresponding isl_id or NULL otherwise.
2432 __isl_give isl_id
*getIdForParam(const SCEV
*Parameter
);
2434 /// Get the maximum region of this static control part.
2436 /// @return The maximum region of this static control part.
2437 inline const Region
&getRegion() const { return R
; }
2438 inline Region
&getRegion() { return R
; }
2440 /// Return the function this SCoP is in.
2441 Function
&getFunction() const { return *R
.getEntry()->getParent(); }
2443 /// Check if @p L is contained in the SCoP.
2444 bool contains(const Loop
*L
) const { return R
.contains(L
); }
2446 /// Check if @p BB is contained in the SCoP.
2447 bool contains(const BasicBlock
*BB
) const { return R
.contains(BB
); }
2449 /// Check if @p I is contained in the SCoP.
2450 bool contains(const Instruction
*I
) const { return R
.contains(I
); }
2452 /// Return the unique exit block of the SCoP.
2453 BasicBlock
*getExit() const { return R
.getExit(); }
2455 /// Return the unique exiting block of the SCoP if any.
2456 BasicBlock
*getExitingBlock() const { return R
.getExitingBlock(); }
2458 /// Return the unique entry block of the SCoP.
2459 BasicBlock
*getEntry() const { return R
.getEntry(); }
2461 /// Return the unique entering block of the SCoP if any.
2462 BasicBlock
*getEnteringBlock() const { return R
.getEnteringBlock(); }
2464 /// Return true if @p BB is the exit block of the SCoP.
2465 bool isExit(BasicBlock
*BB
) const { return getExit() == BB
; }
2467 /// Return a range of all basic blocks in the SCoP.
2468 Region::block_range
blocks() const { return R
.blocks(); }
2470 /// Return true if and only if @p BB dominates the SCoP.
2471 bool isDominatedBy(const DominatorTree
&DT
, BasicBlock
*BB
) const;
2473 /// Get the maximum depth of the loop.
2475 /// @return The maximum depth of the loop.
2476 inline unsigned getMaxLoopDepth() const { return MaxLoopDepth
; }
2478 /// Return the invariant equivalence class for @p Val if any.
2479 InvariantEquivClassTy
*lookupInvariantEquivClass(Value
*Val
);
2481 /// Return the set of invariant accesses.
2482 InvariantEquivClassesTy
&getInvariantAccesses() {
2483 return InvariantEquivClasses
;
2486 /// Check if the scop has any invariant access.
2487 bool hasInvariantAccesses() { return !InvariantEquivClasses
.empty(); }
2489 /// Mark the SCoP as optimized by the scheduler.
2490 void markAsOptimized() { IsOptimized
= true; }
2492 /// Check if the SCoP has been optimized by the scheduler.
2493 bool isOptimized() const { return IsOptimized
; }
2495 /// Mark the SCoP to be skipped by ScopPass passes.
2496 void markAsToBeSkipped() { SkipScop
= true; }
2498 /// Check if the SCoP is to be skipped by ScopPass passes.
2499 bool isToBeSkipped() const { return SkipScop
; }
2501 /// Return the ID of the Scop
2502 int getID() const { return ID
; }
2504 /// Get the name of the entry and exit blocks of this Scop.
2506 /// These along with the function name can uniquely identify a Scop.
2508 /// @return std::pair whose first element is the entry name & second element
2509 /// is the exit name.
2510 std::pair
<std::string
, std::string
> getEntryExitStr() const;
2512 /// Get the name of this Scop.
2513 std::string
getNameStr() const;
2515 /// Get the constraint on parameter of this Scop.
2517 /// @return The constraint on parameter of this Scop.
2518 __isl_give isl_set
*getContext() const;
2519 __isl_give isl_space
*getParamSpace() const;
2521 /// Get the assumed context for this Scop.
2523 /// @return The assumed context of this Scop.
2524 __isl_give isl_set
*getAssumedContext() const;
2526 /// Return true if the optimized SCoP can be executed.
2528 /// In addition to the runtime check context this will also utilize the domain
2529 /// constraints to decide it the optimized version can actually be executed.
2531 /// @returns True if the optimized SCoP can be executed.
2532 bool hasFeasibleRuntimeContext() const;
2534 /// Check if the assumption in @p Set is trivial or not.
2536 /// @param Set The relations between parameters that are assumed to hold.
2537 /// @param Sign Enum to indicate if the assumptions in @p Set are positive
2538 /// (needed/assumptions) or negative (invalid/restrictions).
2540 /// @returns True if the assumption @p Set is not trivial.
2541 bool isEffectiveAssumption(__isl_keep isl_set
*Set
, AssumptionSign Sign
);
2543 /// Track and report an assumption.
2545 /// Use 'clang -Rpass-analysis=polly-scops' or 'opt
2546 /// -pass-remarks-analysis=polly-scops' to output the assumptions.
2548 /// @param Kind The assumption kind describing the underlying cause.
2549 /// @param Set The relations between parameters that are assumed to hold.
2550 /// @param Loc The location in the source that caused this assumption.
2551 /// @param Sign Enum to indicate if the assumptions in @p Set are positive
2552 /// (needed/assumptions) or negative (invalid/restrictions).
2553 /// @param BB The block in which this assumption was taken. Used to
2554 /// calculate hotness when emitting remark.
2556 /// @returns True if the assumption is not trivial.
2557 bool trackAssumption(AssumptionKind Kind
, __isl_keep isl_set
*Set
,
2558 DebugLoc Loc
, AssumptionSign Sign
, BasicBlock
*BB
);
2560 /// Add assumptions to assumed context.
2562 /// The assumptions added will be assumed to hold during the execution of the
2563 /// scop. However, as they are generally not statically provable, at code
2564 /// generation time run-time checks will be generated that ensure the
2565 /// assumptions hold.
2567 /// WARNING: We currently exploit in simplifyAssumedContext the knowledge
2568 /// that assumptions do not change the set of statement instances
2571 /// @param Kind The assumption kind describing the underlying cause.
2572 /// @param Set The relations between parameters that are assumed to hold.
2573 /// @param Loc The location in the source that caused this assumption.
2574 /// @param Sign Enum to indicate if the assumptions in @p Set are positive
2575 /// (needed/assumptions) or negative (invalid/restrictions).
2576 /// @param BB The block in which this assumption was taken. Used to
2577 /// calculate hotness when emitting remark.
2578 void addAssumption(AssumptionKind Kind
, __isl_take isl_set
*Set
, DebugLoc Loc
,
2579 AssumptionSign Sign
, BasicBlock
*BB
);
2581 /// Record an assumption for later addition to the assumed context.
2583 /// This function will add the assumption to the RecordedAssumptions. This
2584 /// collection will be added (@see addAssumption) to the assumed context once
2585 /// all paramaters are known and the context is fully build.
2587 /// @param Kind The assumption kind describing the underlying cause.
2588 /// @param Set The relations between parameters that are assumed to hold.
2589 /// @param Loc The location in the source that caused this assumption.
2590 /// @param Sign Enum to indicate if the assumptions in @p Set are positive
2591 /// (needed/assumptions) or negative (invalid/restrictions).
2592 /// @param BB The block in which this assumption was taken. If it is
2593 /// set, the domain of that block will be used to simplify the
2594 /// actual assumption in @p Set once it is added. This is useful
2595 /// if the assumption was created prior to the domain.
2596 void recordAssumption(AssumptionKind Kind
, __isl_take isl_set
*Set
,
2597 DebugLoc Loc
, AssumptionSign Sign
,
2598 BasicBlock
*BB
= nullptr);
2600 /// Add all recorded assumptions to the assumed context.
2601 void addRecordedAssumptions();
2603 /// Mark the scop as invalid.
2605 /// This method adds an assumption to the scop that is always invalid. As a
2606 /// result, the scop will not be optimized later on. This function is commonly
2607 /// called when a condition makes it impossible (or too compile time
2608 /// expensive) to process this scop any further.
2610 /// @param Kind The assumption kind describing the underlying cause.
2611 /// @param Loc The location in the source that triggered .
2612 /// @param BB The BasicBlock where it was triggered.
2613 void invalidate(AssumptionKind Kind
, DebugLoc Loc
, BasicBlock
*BB
= nullptr);
2615 /// Get the invalid context for this Scop.
2617 /// @return The invalid context of this Scop.
2618 __isl_give isl_set
*getInvalidContext() const;
2620 /// Return true if and only if the InvalidContext is trivial (=empty).
2621 bool hasTrivialInvalidContext() const {
2622 return isl_set_is_empty(InvalidContext
);
2625 /// A vector of memory accesses that belong to an alias group.
2626 typedef SmallVector
<MemoryAccess
*, 4> AliasGroupTy
;
2628 /// A vector of alias groups.
2629 typedef SmallVector
<Scop::AliasGroupTy
, 4> AliasGroupVectorTy
;
2631 /// Build the alias checks for this SCoP.
2632 bool buildAliasChecks(AliasAnalysis
&AA
);
2634 /// Build all alias groups for this SCoP.
2636 /// @returns True if __no__ error occurred, false otherwise.
2637 bool buildAliasGroups(AliasAnalysis
&AA
);
2639 /// Build alias groups for all memory accesses in the Scop.
2641 /// Using the alias analysis and an alias set tracker we build alias sets
2642 /// for all memory accesses inside the Scop. For each alias set we then map
2643 /// the aliasing pointers back to the memory accesses we know, thus obtain
2644 /// groups of memory accesses which might alias. We also collect the set of
2645 /// arrays through which memory is written.
2647 /// @param AA A reference to the alias analysis.
2649 /// @returns A pair consistent of a vector of alias groups and a set of arrays
2650 /// through which memory is written.
2651 std::tuple
<AliasGroupVectorTy
, DenseSet
<const ScopArrayInfo
*>>
2652 buildAliasGroupsForAccesses(AliasAnalysis
&AA
);
2654 /// Split alias groups by iteration domains.
2656 /// We split each group based on the domains of the minimal/maximal accesses.
2657 /// That means two minimal/maximal accesses are only in a group if their
2658 /// access domains intersect. Otherwise, they are in different groups.
2660 /// @param AliasGroups The alias groups to split
2661 void splitAliasGroupsByDomain(AliasGroupVectorTy
&AliasGroups
);
2663 /// Build a given alias group and its access data.
2665 /// @param AliasGroup The alias group to build.
2666 /// @param HasWriteAccess A set of arrays through which memory is not only
2667 /// read, but also written.
2669 /// @returns True if __no__ error occurred, false otherwise.
2670 bool buildAliasGroup(Scop::AliasGroupTy
&AliasGroup
,
2671 DenseSet
<const ScopArrayInfo
*> HasWriteAccess
);
2673 /// Return all alias groups for this SCoP.
2674 const MinMaxVectorPairVectorTy
&getAliasGroups() const {
2675 return MinMaxAliasGroups
;
2678 /// Get an isl string representing the context.
2679 std::string
getContextStr() const;
2681 /// Get an isl string representing the assumed context.
2682 std::string
getAssumedContextStr() const;
2684 /// Get an isl string representing the invalid context.
2685 std::string
getInvalidContextStr() const;
2687 /// Return the ScopStmt for the given @p BB or nullptr if there is
2689 ScopStmt
*getStmtFor(BasicBlock
*BB
) const;
2691 /// Return the list of ScopStmts that represent the given @p BB.
2692 ArrayRef
<ScopStmt
*> getStmtListFor(BasicBlock
*BB
) const;
2694 /// Return the last statement representing @p BB.
2696 /// Of the sequence of statements that represent a @p BB, this is the last one
2697 /// to be executed. It is typically used to determine which instruction to add
2698 /// a MemoryKind::PHI WRITE to. For this purpose, it is not strictly required
2699 /// to be executed last, only that the incoming value is available in it.
2700 ScopStmt
*getLastStmtFor(BasicBlock
*BB
) const;
2702 /// Return the ScopStmts that represents the Region @p R, or nullptr if
2703 /// it is not represented by any statement in this Scop.
2704 ArrayRef
<ScopStmt
*> getStmtListFor(Region
*R
) const;
2706 /// Return the ScopStmts that represents @p RN; can return nullptr if
2707 /// the RegionNode is not within the SCoP or has been removed due to
2708 /// simplifications.
2709 ArrayRef
<ScopStmt
*> getStmtListFor(RegionNode
*RN
) const;
2711 /// Return the ScopStmt an instruction belongs to, or nullptr if it
2712 /// does not belong to any statement in this Scop.
2713 ScopStmt
*getStmtFor(Instruction
*Inst
) const {
2714 return getStmtFor(Inst
->getParent());
2717 /// Return the number of statements in the SCoP.
2718 size_t getSize() const { return Stmts
.size(); }
2720 /// @name Statements Iterators
2722 /// These iterators iterate over all statements of this Scop.
2724 typedef StmtSet::iterator iterator
;
2725 typedef StmtSet::const_iterator const_iterator
;
2727 iterator
begin() { return Stmts
.begin(); }
2728 iterator
end() { return Stmts
.end(); }
2729 const_iterator
begin() const { return Stmts
.begin(); }
2730 const_iterator
end() const { return Stmts
.end(); }
2732 typedef StmtSet::reverse_iterator reverse_iterator
;
2733 typedef StmtSet::const_reverse_iterator const_reverse_iterator
;
2735 reverse_iterator
rbegin() { return Stmts
.rbegin(); }
2736 reverse_iterator
rend() { return Stmts
.rend(); }
2737 const_reverse_iterator
rbegin() const { return Stmts
.rbegin(); }
2738 const_reverse_iterator
rend() const { return Stmts
.rend(); }
2741 /// Return the set of required invariant loads.
2742 const InvariantLoadsSetTy
&getRequiredInvariantLoads() const {
2743 return DC
.RequiredILS
;
2746 /// Add @p LI to the set of required invariant loads.
2747 void addRequiredInvariantLoad(LoadInst
*LI
) { DC
.RequiredILS
.insert(LI
); }
2749 /// Return true if and only if @p LI is a required invariant load.
2750 bool isRequiredInvariantLoad(LoadInst
*LI
) const {
2751 return getRequiredInvariantLoads().count(LI
);
2754 /// Return the set of boxed (thus overapproximated) loops.
2755 const BoxedLoopsSetTy
&getBoxedLoops() const { return DC
.BoxedLoopsSet
; }
2757 /// Return true if and only if @p R is a non-affine subregion.
2758 bool isNonAffineSubRegion(const Region
*R
) {
2759 return DC
.NonAffineSubRegionSet
.count(R
);
2762 const MapInsnToMemAcc
&getInsnToMemAccMap() const { return DC
.InsnToMemAcc
; }
2764 /// Return the (possibly new) ScopArrayInfo object for @p Access.
2766 /// @param ElementType The type of the elements stored in this array.
2767 /// @param Kind The kind of the array info object.
2768 /// @param BaseName The optional name of this memory reference.
2769 ScopArrayInfo
*getOrCreateScopArrayInfo(Value
*BasePtr
, Type
*ElementType
,
2770 ArrayRef
<const SCEV
*> Sizes
,
2772 const char *BaseName
= nullptr);
2774 /// Create an array and return the corresponding ScopArrayInfo object.
2776 /// @param ElementType The type of the elements stored in this array.
2777 /// @param BaseName The name of this memory reference.
2778 /// @param Sizes The sizes of dimensions.
2779 ScopArrayInfo
*createScopArrayInfo(Type
*ElementType
,
2780 const std::string
&BaseName
,
2781 const std::vector
<unsigned> &Sizes
);
2783 /// Return the cached ScopArrayInfo object for @p BasePtr.
2785 /// @param BasePtr The base pointer the object has been stored for.
2786 /// @param Kind The kind of array info object.
2788 /// @returns The ScopArrayInfo pointer or NULL if no such pointer is
2790 const ScopArrayInfo
*getScopArrayInfoOrNull(Value
*BasePtr
, MemoryKind Kind
);
2792 /// Return the cached ScopArrayInfo object for @p BasePtr.
2794 /// @param BasePtr The base pointer the object has been stored for.
2795 /// @param Kind The kind of array info object.
2797 /// @returns The ScopArrayInfo pointer (may assert if no such pointer is
2799 const ScopArrayInfo
*getScopArrayInfo(Value
*BasePtr
, MemoryKind Kind
);
2801 /// Invalidate ScopArrayInfo object for base address.
2803 /// @param BasePtr The base pointer of the ScopArrayInfo object to invalidate.
2804 /// @param Kind The Kind of the ScopArrayInfo object.
2805 void invalidateScopArrayInfo(Value
*BasePtr
, MemoryKind Kind
) {
2806 auto It
= ScopArrayInfoMap
.find(std::make_pair(BasePtr
, Kind
));
2807 if (It
== ScopArrayInfoMap
.end())
2809 ScopArrayInfoSet
.remove(It
->second
.get());
2810 ScopArrayInfoMap
.erase(It
);
2813 void setContext(__isl_take isl_set
*NewContext
);
2815 /// Align the parameters in the statement to the scop context
2816 void realignParams();
2818 /// Return true if this SCoP can be profitably optimized.
2820 /// @param ScalarsAreUnprofitable Never consider statements with scalar writes
2821 /// as profitably optimizable.
2823 /// @return Whether this SCoP can be profitably optimized.
2824 bool isProfitable(bool ScalarsAreUnprofitable
) const;
2826 /// Return true if the SCoP contained at least one error block.
2827 bool hasErrorBlock() const { return HasErrorBlock
; }
2829 /// Return true if the underlying region has a single exiting block.
2830 bool hasSingleExitEdge() const { return HasSingleExitEdge
; }
2832 /// Print the static control part.
2834 /// @param OS The output stream the static control part is printed to.
2835 /// @param PrintInstructions Whether to print the statement's instructions as
2837 void print(raw_ostream
&OS
, bool PrintInstructions
) const;
2839 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2840 /// Print the ScopStmt to stderr.
2844 /// Get the isl context of this static control part.
2846 /// @return The isl context of this static control part.
2847 isl_ctx
*getIslCtx() const;
2849 /// Directly return the shared_ptr of the context.
2850 const std::shared_ptr
<isl_ctx
> &getSharedIslCtx() const { return IslCtx
; }
2852 /// Compute the isl representation for the SCEV @p E
2854 /// @param E The SCEV that should be translated.
2855 /// @param BB An (optional) basic block in which the isl_pw_aff is computed.
2856 /// SCEVs known to not reference any loops in the SCoP can be
2857 /// passed without a @p BB.
2858 /// @param NonNegative Flag to indicate the @p E has to be non-negative.
2860 /// Note that this function will always return a valid isl_pw_aff. However, if
2861 /// the translation of @p E was deemed to complex the SCoP is invalidated and
2862 /// a dummy value of appropriate dimension is returned. This allows to bail
2863 /// for complex cases without "error handling code" needed on the users side.
2864 __isl_give PWACtx
getPwAff(const SCEV
*E
, BasicBlock
*BB
= nullptr,
2865 bool NonNegative
= false);
2867 /// Compute the isl representation for the SCEV @p E
2869 /// This function is like @see Scop::getPwAff() but strips away the invalid
2870 /// domain part associated with the piecewise affine function.
2871 __isl_give isl_pw_aff
*getPwAffOnly(const SCEV
*E
, BasicBlock
*BB
= nullptr);
2873 /// Return the domain of @p Stmt.
2875 /// @param Stmt The statement for which the conditions should be returned.
2876 __isl_give isl_set
*getDomainConditions(const ScopStmt
*Stmt
) const;
2878 /// Return the domain of @p BB.
2880 /// @param BB The block for which the conditions should be returned.
2881 __isl_give isl_set
*getDomainConditions(BasicBlock
*BB
) const;
2883 /// Get a union set containing the iteration domains of all statements.
2884 __isl_give isl_union_set
*getDomains() const;
2886 /// Get a union map of all may-writes performed in the SCoP.
2887 __isl_give isl_union_map
*getMayWrites();
2889 /// Get a union map of all must-writes performed in the SCoP.
2890 __isl_give isl_union_map
*getMustWrites();
2892 /// Get a union map of all writes performed in the SCoP.
2893 __isl_give isl_union_map
*getWrites();
2895 /// Get a union map of all reads performed in the SCoP.
2896 __isl_give isl_union_map
*getReads();
2898 /// Get a union map of all memory accesses performed in the SCoP.
2899 __isl_give isl_union_map
*getAccesses();
2901 /// Get the schedule of all the statements in the SCoP.
2903 /// @return The schedule of all the statements in the SCoP, if the schedule of
2904 /// the Scop does not contain extension nodes, and nullptr, otherwise.
2905 __isl_give isl_union_map
*getSchedule() const;
2907 /// Get a schedule tree describing the schedule of all statements.
2908 __isl_give isl_schedule
*getScheduleTree() const;
2910 /// Update the current schedule
2912 /// NewSchedule The new schedule (given as a flat union-map).
2913 void setSchedule(__isl_take isl_union_map
*NewSchedule
);
2915 /// Update the current schedule
2917 /// NewSchedule The new schedule (given as schedule tree).
2918 void setScheduleTree(__isl_take isl_schedule
*NewSchedule
);
2920 /// Intersects the domains of all statements in the SCoP.
2922 /// @return true if a change was made
2923 bool restrictDomains(__isl_take isl_union_set
*Domain
);
2925 /// Get the depth of a loop relative to the outermost loop in the Scop.
2927 /// This will return
2928 /// 0 if @p L is an outermost loop in the SCoP
2929 /// >0 for other loops in the SCoP
2930 /// -1 if @p L is nullptr or there is no outermost loop in the SCoP
2931 int getRelativeLoopDepth(const Loop
*L
) const;
2933 /// Find the ScopArrayInfo associated with an isl Id
2934 /// that has name @p Name.
2935 ScopArrayInfo
*getArrayInfoByName(const std::string BaseName
);
2937 /// Check whether @p Schedule contains extension nodes.
2939 /// @return true if @p Schedule contains extension nodes.
2940 static bool containsExtensionNode(__isl_keep isl_schedule
*Schedule
);
2942 /// Simplify the SCoP representation.
2944 /// @param AfterHoisting Whether it is called after invariant load hoisting.
2945 /// When true, also removes statements without
2947 void simplifySCoP(bool AfterHoisting
);
2949 /// Get the next free array index.
2951 /// This function returns a unique index which can be used to identify an
2953 long getNextArrayIdx() { return ArrayIdx
++; }
2955 /// Get the next free statement index.
2957 /// This function returns a unique index which can be used to identify a
2959 long getNextStmtIdx() { return StmtIdx
++; }
2961 /// Return the MemoryAccess that writes an llvm::Value, represented by a
2964 /// There can be at most one such MemoryAccess per llvm::Value in the SCoP.
2965 /// Zero is possible for read-only values.
2966 MemoryAccess
*getValueDef(const ScopArrayInfo
*SAI
) const;
2968 /// Return all MemoryAccesses that us an llvm::Value, represented by a
2970 ArrayRef
<MemoryAccess
*> getValueUses(const ScopArrayInfo
*SAI
) const;
2972 /// Return the MemoryAccess that represents an llvm::PHINode.
2974 /// ExitPHIs's PHINode is not within the SCoPs. This function returns nullptr
2976 MemoryAccess
*getPHIRead(const ScopArrayInfo
*SAI
) const;
2978 /// Return all MemoryAccesses for all incoming statements of a PHINode,
2979 /// represented by a ScopArrayInfo.
2980 ArrayRef
<MemoryAccess
*> getPHIIncomings(const ScopArrayInfo
*SAI
) const;
2983 /// Print Scop scop to raw_ostream O.
2984 raw_ostream
&operator<<(raw_ostream
&O
, const Scop
&scop
);
2986 /// The legacy pass manager's analysis pass to compute scop information
2988 class ScopInfoRegionPass
: public RegionPass
{
2989 /// The Scop pointer which is used to construct a Scop.
2990 std::unique_ptr
<Scop
> S
;
2993 static char ID
; // Pass identification, replacement for typeid
2995 ScopInfoRegionPass() : RegionPass(ID
) {}
2996 ~ScopInfoRegionPass() {}
2998 /// Build Scop object, the Polly IR of static control
2999 /// part for the current SESE-Region.
3001 /// @return If the current region is a valid for a static control part,
3002 /// return the Polly IR representing this static control part,
3003 /// return null otherwise.
3004 Scop
*getScop() { return S
.get(); }
3005 const Scop
*getScop() const { return S
.get(); }
3007 /// Calculate the polyhedral scop information for a given Region.
3008 bool runOnRegion(Region
*R
, RGPassManager
&RGM
) override
;
3010 void releaseMemory() override
{ S
.reset(); }
3012 void print(raw_ostream
&O
, const Module
*M
= nullptr) const override
;
3014 void getAnalysisUsage(AnalysisUsage
&AU
) const override
;
3019 using RegionToScopMapTy
= DenseMap
<Region
*, std::unique_ptr
<Scop
>>;
3020 using iterator
= RegionToScopMapTy::iterator
;
3021 using const_iterator
= RegionToScopMapTy::const_iterator
;
3024 /// A map of Region to its Scop object containing
3025 /// Polly IR of static control part.
3026 RegionToScopMapTy RegionToScopMap
;
3029 ScopInfo(const DataLayout
&DL
, ScopDetection
&SD
, ScalarEvolution
&SE
,
3030 LoopInfo
&LI
, AliasAnalysis
&AA
, DominatorTree
&DT
,
3031 AssumptionCache
&AC
);
3033 /// Get the Scop object for the given Region.
3035 /// @return If the given region is the maximal region within a scop, return
3036 /// the scop object. If the given region is a subregion, return a
3037 /// nullptr. Top level region containing the entry block of a function
3038 /// is not considered in the scop creation.
3039 Scop
*getScop(Region
*R
) const {
3040 auto MapIt
= RegionToScopMap
.find(R
);
3041 if (MapIt
!= RegionToScopMap
.end())
3042 return MapIt
->second
.get();
3046 iterator
begin() { return RegionToScopMap
.begin(); }
3047 iterator
end() { return RegionToScopMap
.end(); }
3048 const_iterator
begin() const { return RegionToScopMap
.begin(); }
3049 const_iterator
end() const { return RegionToScopMap
.end(); }
3050 bool empty() const { return RegionToScopMap
.empty(); }
3053 struct ScopInfoAnalysis
: public AnalysisInfoMixin
<ScopInfoAnalysis
> {
3054 static AnalysisKey Key
;
3055 using Result
= ScopInfo
;
3056 Result
run(Function
&, FunctionAnalysisManager
&);
3059 struct ScopInfoPrinterPass
: public PassInfoMixin
<ScopInfoPrinterPass
> {
3060 ScopInfoPrinterPass(raw_ostream
&O
) : Stream(O
) {}
3061 PreservedAnalyses
run(Function
&, FunctionAnalysisManager
&);
3062 raw_ostream
&Stream
;
3065 //===----------------------------------------------------------------------===//
3066 /// The legacy pass manager's analysis pass to compute scop information
3067 /// for the whole function.
3069 /// This pass will maintain a map of the maximal region within a scop to its
3070 /// scop object for all the feasible scops present in a function.
3071 /// This pass is an alternative to the ScopInfoRegionPass in order to avoid a
3072 /// region pass manager.
3073 class ScopInfoWrapperPass
: public FunctionPass
{
3074 std::unique_ptr
<ScopInfo
> Result
;
3077 ScopInfoWrapperPass() : FunctionPass(ID
) {}
3078 ~ScopInfoWrapperPass() = default;
3080 static char ID
; // Pass identification, replacement for typeid
3082 ScopInfo
*getSI() { return Result
.get(); }
3083 const ScopInfo
*getSI() const { return Result
.get(); }
3085 /// Calculate all the polyhedral scops for a given function.
3086 bool runOnFunction(Function
&F
) override
;
3088 void releaseMemory() override
{ Result
.reset(); }
3090 void print(raw_ostream
&O
, const Module
*M
= nullptr) const override
;
3092 void getAnalysisUsage(AnalysisUsage
&AU
) const override
;
3095 } // end namespace polly
3099 void initializeScopInfoRegionPassPass(llvm::PassRegistry
&);
3100 void initializeScopInfoWrapperPassPass(llvm::PassRegistry
&);