10b57cec5SDimitry Andric //===- llvm/Analysis/LoopAccessAnalysis.h -----------------------*- C++ -*-===//
20b57cec5SDimitry Andric //
30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
60b57cec5SDimitry Andric //
70b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
80b57cec5SDimitry Andric //
90b57cec5SDimitry Andric // This file defines the interface for the loop memory dependence framework that
100b57cec5SDimitry Andric // was originally developed for the Loop Vectorizer.
110b57cec5SDimitry Andric //
120b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
130b57cec5SDimitry Andric
140b57cec5SDimitry Andric #ifndef LLVM_ANALYSIS_LOOPACCESSANALYSIS_H
150b57cec5SDimitry Andric #define LLVM_ANALYSIS_LOOPACCESSANALYSIS_H
160b57cec5SDimitry Andric
170b57cec5SDimitry Andric #include "llvm/ADT/EquivalenceClasses.h"
180b57cec5SDimitry Andric #include "llvm/Analysis/LoopAnalysisManager.h"
190b57cec5SDimitry Andric #include "llvm/Analysis/ScalarEvolutionExpressions.h"
200b57cec5SDimitry Andric #include "llvm/IR/DiagnosticInfo.h"
21bdd1243dSDimitry Andric #include <optional>
220b57cec5SDimitry Andric
230b57cec5SDimitry Andric namespace llvm {
240b57cec5SDimitry Andric
255ffd83dbSDimitry Andric class AAResults;
260b57cec5SDimitry Andric class DataLayout;
270b57cec5SDimitry Andric class Loop;
280b57cec5SDimitry Andric class LoopAccessInfo;
295ffd83dbSDimitry Andric class raw_ostream;
305ffd83dbSDimitry Andric class SCEV;
315ffd83dbSDimitry Andric class SCEVUnionPredicate;
325ffd83dbSDimitry Andric class Value;
330b57cec5SDimitry Andric
340b57cec5SDimitry Andric /// Collection of parameters shared beetween the Loop Vectorizer and the
350b57cec5SDimitry Andric /// Loop Access Analysis.
360b57cec5SDimitry Andric struct VectorizerParams {
370b57cec5SDimitry Andric /// Maximum SIMD width.
380b57cec5SDimitry Andric static const unsigned MaxVectorWidth;
390b57cec5SDimitry Andric
400b57cec5SDimitry Andric /// VF as overridden by the user.
410b57cec5SDimitry Andric static unsigned VectorizationFactor;
420b57cec5SDimitry Andric /// Interleave factor as overridden by the user.
430b57cec5SDimitry Andric static unsigned VectorizationInterleave;
440b57cec5SDimitry Andric /// True if force-vector-interleave was specified by the user.
450b57cec5SDimitry Andric static bool isInterleaveForced();
460b57cec5SDimitry Andric
470b57cec5SDimitry Andric /// \When performing memory disambiguation checks at runtime do not
480b57cec5SDimitry Andric /// make more than this number of comparisons.
490b57cec5SDimitry Andric static unsigned RuntimeMemoryCheckThreshold;
505f757f3fSDimitry Andric
515f757f3fSDimitry Andric // When creating runtime checks for nested loops, where possible try to
525f757f3fSDimitry Andric // write the checks in a form that allows them to be easily hoisted out of
535f757f3fSDimitry Andric // the outermost loop. For example, we can do this by expanding the range of
545f757f3fSDimitry Andric // addresses considered to include the entire nested loop so that they are
555f757f3fSDimitry Andric // loop invariant.
565f757f3fSDimitry Andric static bool HoistRuntimeChecks;
570b57cec5SDimitry Andric };
580b57cec5SDimitry Andric
590b57cec5SDimitry Andric /// Checks memory dependences among accesses to the same underlying
600b57cec5SDimitry Andric /// object to determine whether there vectorization is legal or not (and at
610b57cec5SDimitry Andric /// which vectorization factor).
620b57cec5SDimitry Andric ///
630b57cec5SDimitry Andric /// Note: This class will compute a conservative dependence for access to
640b57cec5SDimitry Andric /// different underlying pointers. Clients, such as the loop vectorizer, will
650b57cec5SDimitry Andric /// sometimes deal these potential dependencies by emitting runtime checks.
660b57cec5SDimitry Andric ///
670b57cec5SDimitry Andric /// We use the ScalarEvolution framework to symbolically evalutate access
680b57cec5SDimitry Andric /// functions pairs. Since we currently don't restructure the loop we can rely
690b57cec5SDimitry Andric /// on the program order of memory accesses to determine their safety.
700b57cec5SDimitry Andric /// At the moment we will only deem accesses as safe for:
710b57cec5SDimitry Andric /// * A negative constant distance assuming program order.
720b57cec5SDimitry Andric ///
730b57cec5SDimitry Andric /// Safe: tmp = a[i + 1]; OR a[i + 1] = x;
740b57cec5SDimitry Andric /// a[i] = tmp; y = a[i];
750b57cec5SDimitry Andric ///
760b57cec5SDimitry Andric /// The latter case is safe because later checks guarantuee that there can't
770b57cec5SDimitry Andric /// be a cycle through a phi node (that is, we check that "x" and "y" is not
780b57cec5SDimitry Andric /// the same variable: a header phi can only be an induction or a reduction, a
790b57cec5SDimitry Andric /// reduction can't have a memory sink, an induction can't have a memory
800b57cec5SDimitry Andric /// source). This is important and must not be violated (or we have to
810b57cec5SDimitry Andric /// resort to checking for cycles through memory).
820b57cec5SDimitry Andric ///
830b57cec5SDimitry Andric /// * A positive constant distance assuming program order that is bigger
840b57cec5SDimitry Andric /// than the biggest memory access.
850b57cec5SDimitry Andric ///
860b57cec5SDimitry Andric /// tmp = a[i] OR b[i] = x
870b57cec5SDimitry Andric /// a[i+2] = tmp y = b[i+2];
880b57cec5SDimitry Andric ///
890b57cec5SDimitry Andric /// Safe distance: 2 x sizeof(a[0]), and 2 x sizeof(b[0]), respectively.
900b57cec5SDimitry Andric ///
910b57cec5SDimitry Andric /// * Zero distances and all accesses have the same size.
920b57cec5SDimitry Andric ///
930b57cec5SDimitry Andric class MemoryDepChecker {
940b57cec5SDimitry Andric public:
950b57cec5SDimitry Andric typedef PointerIntPair<Value *, 1, bool> MemAccessInfo;
960b57cec5SDimitry Andric typedef SmallVector<MemAccessInfo, 8> MemAccessInfoList;
970b57cec5SDimitry Andric /// Set of potential dependent memory accesses.
980b57cec5SDimitry Andric typedef EquivalenceClasses<MemAccessInfo> DepCandidates;
990b57cec5SDimitry Andric
1000b57cec5SDimitry Andric /// Type to keep track of the status of the dependence check. The order of
1010b57cec5SDimitry Andric /// the elements is important and has to be from most permissive to least
1020b57cec5SDimitry Andric /// permissive.
1030b57cec5SDimitry Andric enum class VectorizationSafetyStatus {
1040b57cec5SDimitry Andric // Can vectorize safely without RT checks. All dependences are known to be
1050b57cec5SDimitry Andric // safe.
1060b57cec5SDimitry Andric Safe,
1070b57cec5SDimitry Andric // Can possibly vectorize with RT checks to overcome unknown dependencies.
1080b57cec5SDimitry Andric PossiblySafeWithRtChecks,
1090b57cec5SDimitry Andric // Cannot vectorize due to known unsafe dependencies.
1100b57cec5SDimitry Andric Unsafe,
1110b57cec5SDimitry Andric };
1120b57cec5SDimitry Andric
1130b57cec5SDimitry Andric /// Dependece between memory access instructions.
1140b57cec5SDimitry Andric struct Dependence {
1150b57cec5SDimitry Andric /// The type of the dependence.
1160b57cec5SDimitry Andric enum DepType {
1170b57cec5SDimitry Andric // No dependence.
1180b57cec5SDimitry Andric NoDep,
1190b57cec5SDimitry Andric // We couldn't determine the direction or the distance.
1200b57cec5SDimitry Andric Unknown,
1215f757f3fSDimitry Andric // At least one of the memory access instructions may access a loop
1225f757f3fSDimitry Andric // varying object, e.g. the address of underlying object is loaded inside
1235f757f3fSDimitry Andric // the loop, like A[B[i]]. We cannot determine direction or distance in
1245f757f3fSDimitry Andric // those cases, and also are unable to generate any runtime checks.
1255f757f3fSDimitry Andric IndirectUnsafe,
1265f757f3fSDimitry Andric
1270b57cec5SDimitry Andric // Lexically forward.
1280b57cec5SDimitry Andric //
1290b57cec5SDimitry Andric // FIXME: If we only have loop-independent forward dependences (e.g. a
1300b57cec5SDimitry Andric // read and write of A[i]), LAA will locally deem the dependence "safe"
1310b57cec5SDimitry Andric // without querying the MemoryDepChecker. Therefore we can miss
1320b57cec5SDimitry Andric // enumerating loop-independent forward dependences in
1330b57cec5SDimitry Andric // getDependences. Note that as soon as there are different
1340b57cec5SDimitry Andric // indices used to access the same array, the MemoryDepChecker *is*
1350b57cec5SDimitry Andric // queried and the dependence list is complete.
1360b57cec5SDimitry Andric Forward,
1370b57cec5SDimitry Andric // Forward, but if vectorized, is likely to prevent store-to-load
1380b57cec5SDimitry Andric // forwarding.
1390b57cec5SDimitry Andric ForwardButPreventsForwarding,
1400b57cec5SDimitry Andric // Lexically backward.
1410b57cec5SDimitry Andric Backward,
1425f757f3fSDimitry Andric // Backward, but the distance allows a vectorization factor of dependent
1435f757f3fSDimitry Andric // on MinDepDistBytes.
1440b57cec5SDimitry Andric BackwardVectorizable,
1450b57cec5SDimitry Andric // Same, but may prevent store-to-load forwarding.
1460b57cec5SDimitry Andric BackwardVectorizableButPreventsForwarding
1470b57cec5SDimitry Andric };
1480b57cec5SDimitry Andric
1490b57cec5SDimitry Andric /// String version of the types.
1500b57cec5SDimitry Andric static const char *DepName[];
1510b57cec5SDimitry Andric
1520b57cec5SDimitry Andric /// Index of the source of the dependence in the InstMap vector.
1530b57cec5SDimitry Andric unsigned Source;
1540b57cec5SDimitry Andric /// Index of the destination of the dependence in the InstMap vector.
1550b57cec5SDimitry Andric unsigned Destination;
1560b57cec5SDimitry Andric /// The type of the dependence.
1570b57cec5SDimitry Andric DepType Type;
1580b57cec5SDimitry Andric
DependenceDependence1590b57cec5SDimitry Andric Dependence(unsigned Source, unsigned Destination, DepType Type)
1600b57cec5SDimitry Andric : Source(Source), Destination(Destination), Type(Type) {}
1610b57cec5SDimitry Andric
1620b57cec5SDimitry Andric /// Return the source instruction of the dependence.
1630b57cec5SDimitry Andric Instruction *getSource(const LoopAccessInfo &LAI) const;
1640b57cec5SDimitry Andric /// Return the destination instruction of the dependence.
1650b57cec5SDimitry Andric Instruction *getDestination(const LoopAccessInfo &LAI) const;
1660b57cec5SDimitry Andric
1670b57cec5SDimitry Andric /// Dependence types that don't prevent vectorization.
1680b57cec5SDimitry Andric static VectorizationSafetyStatus isSafeForVectorization(DepType Type);
1690b57cec5SDimitry Andric
1700b57cec5SDimitry Andric /// Lexically forward dependence.
1710b57cec5SDimitry Andric bool isForward() const;
1720b57cec5SDimitry Andric /// Lexically backward dependence.
1730b57cec5SDimitry Andric bool isBackward() const;
1740b57cec5SDimitry Andric
1750b57cec5SDimitry Andric /// May be a lexically backward dependence type (includes Unknown).
1760b57cec5SDimitry Andric bool isPossiblyBackward() const;
1770b57cec5SDimitry Andric
1780b57cec5SDimitry Andric /// Print the dependence. \p Instr is used to map the instruction
1790b57cec5SDimitry Andric /// indices to instructions.
1800b57cec5SDimitry Andric void print(raw_ostream &OS, unsigned Depth,
1810b57cec5SDimitry Andric const SmallVectorImpl<Instruction *> &Instrs) const;
1820b57cec5SDimitry Andric };
1830b57cec5SDimitry Andric
MemoryDepChecker(PredicatedScalarEvolution & PSE,const Loop * L)1840b57cec5SDimitry Andric MemoryDepChecker(PredicatedScalarEvolution &PSE, const Loop *L)
18504eeddc0SDimitry Andric : PSE(PSE), InnermostLoop(L) {}
1860b57cec5SDimitry Andric
1870b57cec5SDimitry Andric /// Register the location (instructions are given increasing numbers)
1880b57cec5SDimitry Andric /// of a write access.
189349cc55cSDimitry Andric void addAccess(StoreInst *SI);
1900b57cec5SDimitry Andric
1910b57cec5SDimitry Andric /// Register the location (instructions are given increasing numbers)
1920b57cec5SDimitry Andric /// of a write access.
193349cc55cSDimitry Andric void addAccess(LoadInst *LI);
1940b57cec5SDimitry Andric
1950b57cec5SDimitry Andric /// Check whether the dependencies between the accesses are safe.
1960b57cec5SDimitry Andric ///
1970b57cec5SDimitry Andric /// Only checks sets with elements in \p CheckDeps.
1980b57cec5SDimitry Andric bool areDepsSafe(DepCandidates &AccessSets, MemAccessInfoList &CheckDeps,
1995f757f3fSDimitry Andric const DenseMap<Value *, const SCEV *> &Strides,
2005f757f3fSDimitry Andric const DenseMap<Value *, SmallVector<const Value *, 16>>
2015f757f3fSDimitry Andric &UnderlyingObjects);
2020b57cec5SDimitry Andric
2030b57cec5SDimitry Andric /// No memory dependence was encountered that would inhibit
2040b57cec5SDimitry Andric /// vectorization.
isSafeForVectorization()2050b57cec5SDimitry Andric bool isSafeForVectorization() const {
2060b57cec5SDimitry Andric return Status == VectorizationSafetyStatus::Safe;
2070b57cec5SDimitry Andric }
2080b57cec5SDimitry Andric
209e8d8bef9SDimitry Andric /// Return true if the number of elements that are safe to operate on
210e8d8bef9SDimitry Andric /// simultaneously is not bounded.
isSafeForAnyVectorWidth()211e8d8bef9SDimitry Andric bool isSafeForAnyVectorWidth() const {
212e8d8bef9SDimitry Andric return MaxSafeVectorWidthInBits == UINT_MAX;
213e8d8bef9SDimitry Andric }
214e8d8bef9SDimitry Andric
2150b57cec5SDimitry Andric /// Return the number of elements that are safe to operate on
2160b57cec5SDimitry Andric /// simultaneously, multiplied by the size of the element in bits.
getMaxSafeVectorWidthInBits()217e8d8bef9SDimitry Andric uint64_t getMaxSafeVectorWidthInBits() const {
218e8d8bef9SDimitry Andric return MaxSafeVectorWidthInBits;
219e8d8bef9SDimitry Andric }
2200b57cec5SDimitry Andric
2210b57cec5SDimitry Andric /// In same cases when the dependency check fails we can still
2220b57cec5SDimitry Andric /// vectorize the loop with a dynamic array access check.
shouldRetryWithRuntimeCheck()2230b57cec5SDimitry Andric bool shouldRetryWithRuntimeCheck() const {
2240b57cec5SDimitry Andric return FoundNonConstantDistanceDependence &&
2250b57cec5SDimitry Andric Status == VectorizationSafetyStatus::PossiblySafeWithRtChecks;
2260b57cec5SDimitry Andric }
2270b57cec5SDimitry Andric
2280b57cec5SDimitry Andric /// Returns the memory dependences. If null is returned we exceeded
2290b57cec5SDimitry Andric /// the MaxDependences threshold and this information is not
2300b57cec5SDimitry Andric /// available.
getDependences()2310b57cec5SDimitry Andric const SmallVectorImpl<Dependence> *getDependences() const {
2320b57cec5SDimitry Andric return RecordDependences ? &Dependences : nullptr;
2330b57cec5SDimitry Andric }
2340b57cec5SDimitry Andric
clearDependences()2350b57cec5SDimitry Andric void clearDependences() { Dependences.clear(); }
2360b57cec5SDimitry Andric
2370b57cec5SDimitry Andric /// The vector of memory access instructions. The indices are used as
2380b57cec5SDimitry Andric /// instruction identifiers in the Dependence class.
getMemoryInstructions()2390b57cec5SDimitry Andric const SmallVectorImpl<Instruction *> &getMemoryInstructions() const {
2400b57cec5SDimitry Andric return InstMap;
2410b57cec5SDimitry Andric }
2420b57cec5SDimitry Andric
2430b57cec5SDimitry Andric /// Generate a mapping between the memory instructions and their
2440b57cec5SDimitry Andric /// indices according to program order.
generateInstructionOrderMap()2450b57cec5SDimitry Andric DenseMap<Instruction *, unsigned> generateInstructionOrderMap() const {
2460b57cec5SDimitry Andric DenseMap<Instruction *, unsigned> OrderMap;
2470b57cec5SDimitry Andric
2480b57cec5SDimitry Andric for (unsigned I = 0; I < InstMap.size(); ++I)
2490b57cec5SDimitry Andric OrderMap[InstMap[I]] = I;
2500b57cec5SDimitry Andric
2510b57cec5SDimitry Andric return OrderMap;
2520b57cec5SDimitry Andric }
2530b57cec5SDimitry Andric
2540b57cec5SDimitry Andric /// Find the set of instructions that read or write via \p Ptr.
2550b57cec5SDimitry Andric SmallVector<Instruction *, 4> getInstructionsForAccess(Value *Ptr,
2560b57cec5SDimitry Andric bool isWrite) const;
2570b57cec5SDimitry Andric
25881ad6265SDimitry Andric /// Return the program order indices for the access location (Ptr, IsWrite).
25981ad6265SDimitry Andric /// Returns an empty ArrayRef if there are no accesses for the location.
getOrderForAccess(Value * Ptr,bool IsWrite)26081ad6265SDimitry Andric ArrayRef<unsigned> getOrderForAccess(Value *Ptr, bool IsWrite) const {
26181ad6265SDimitry Andric auto I = Accesses.find({Ptr, IsWrite});
26281ad6265SDimitry Andric if (I != Accesses.end())
26381ad6265SDimitry Andric return I->second;
26481ad6265SDimitry Andric return {};
26581ad6265SDimitry Andric }
26681ad6265SDimitry Andric
getInnermostLoop()267a4a491e2SDimitry Andric const Loop *getInnermostLoop() const { return InnermostLoop; }
268a4a491e2SDimitry Andric
2690b57cec5SDimitry Andric private:
2700b57cec5SDimitry Andric /// A wrapper around ScalarEvolution, used to add runtime SCEV checks, and
2710b57cec5SDimitry Andric /// applies dynamic knowledge to simplify SCEV expressions and convert them
2720b57cec5SDimitry Andric /// to a more usable form. We need this in case assumptions about SCEV
2730b57cec5SDimitry Andric /// expressions need to be made in order to avoid unknown dependences. For
2740b57cec5SDimitry Andric /// example we might assume a unit stride for a pointer in order to prove
2750b57cec5SDimitry Andric /// that a memory access is strided and doesn't wrap.
2760b57cec5SDimitry Andric PredicatedScalarEvolution &PSE;
2770b57cec5SDimitry Andric const Loop *InnermostLoop;
2780b57cec5SDimitry Andric
2790b57cec5SDimitry Andric /// Maps access locations (ptr, read/write) to program order.
2800b57cec5SDimitry Andric DenseMap<MemAccessInfo, std::vector<unsigned> > Accesses;
2810b57cec5SDimitry Andric
2820b57cec5SDimitry Andric /// Memory access instructions in program order.
2830b57cec5SDimitry Andric SmallVector<Instruction *, 16> InstMap;
2840b57cec5SDimitry Andric
2850b57cec5SDimitry Andric /// The program order index to be used for the next instruction.
28604eeddc0SDimitry Andric unsigned AccessIdx = 0;
2870b57cec5SDimitry Andric
2885f757f3fSDimitry Andric /// The smallest dependence distance in bytes in the loop. This may not be
2895f757f3fSDimitry Andric /// the same as the maximum number of bytes that are safe to operate on
2905f757f3fSDimitry Andric /// simultaneously.
2915f757f3fSDimitry Andric uint64_t MinDepDistBytes = 0;
2920b57cec5SDimitry Andric
2930b57cec5SDimitry Andric /// Number of elements (from consecutive iterations) that are safe to
2940b57cec5SDimitry Andric /// operate on simultaneously, multiplied by the size of the element in bits.
2950b57cec5SDimitry Andric /// The size of the element is taken from the memory access that is most
2960b57cec5SDimitry Andric /// restrictive.
29704eeddc0SDimitry Andric uint64_t MaxSafeVectorWidthInBits = -1U;
2980b57cec5SDimitry Andric
2990b57cec5SDimitry Andric /// If we see a non-constant dependence distance we can still try to
3000b57cec5SDimitry Andric /// vectorize this loop with runtime checks.
30104eeddc0SDimitry Andric bool FoundNonConstantDistanceDependence = false;
3020b57cec5SDimitry Andric
3030b57cec5SDimitry Andric /// Result of the dependence checks, indicating whether the checked
3040b57cec5SDimitry Andric /// dependences are safe for vectorization, require RT checks or are known to
3050b57cec5SDimitry Andric /// be unsafe.
30604eeddc0SDimitry Andric VectorizationSafetyStatus Status = VectorizationSafetyStatus::Safe;
3070b57cec5SDimitry Andric
3080b57cec5SDimitry Andric //// True if Dependences reflects the dependences in the
3090b57cec5SDimitry Andric //// loop. If false we exceeded MaxDependences and
3100b57cec5SDimitry Andric //// Dependences is invalid.
31104eeddc0SDimitry Andric bool RecordDependences = true;
3120b57cec5SDimitry Andric
3130b57cec5SDimitry Andric /// Memory dependences collected during the analysis. Only valid if
3140b57cec5SDimitry Andric /// RecordDependences is true.
3150b57cec5SDimitry Andric SmallVector<Dependence, 8> Dependences;
3160b57cec5SDimitry Andric
3170b57cec5SDimitry Andric /// Check whether there is a plausible dependence between the two
3180b57cec5SDimitry Andric /// accesses.
3190b57cec5SDimitry Andric ///
3200b57cec5SDimitry Andric /// Access \p A must happen before \p B in program order. The two indices
3210b57cec5SDimitry Andric /// identify the index into the program order map.
3220b57cec5SDimitry Andric ///
3230b57cec5SDimitry Andric /// This function checks whether there is a plausible dependence (or the
3240b57cec5SDimitry Andric /// absence of such can't be proved) between the two accesses. If there is a
3250b57cec5SDimitry Andric /// plausible dependence but the dependence distance is bigger than one
3265f757f3fSDimitry Andric /// element access it records this distance in \p MinDepDistBytes (if this
3270b57cec5SDimitry Andric /// distance is smaller than any other distance encountered so far).
3280b57cec5SDimitry Andric /// Otherwise, this function returns true signaling a possible dependence.
3295f757f3fSDimitry Andric Dependence::DepType
3305f757f3fSDimitry Andric isDependent(const MemAccessInfo &A, unsigned AIdx, const MemAccessInfo &B,
3315f757f3fSDimitry Andric unsigned BIdx, const DenseMap<Value *, const SCEV *> &Strides,
3325f757f3fSDimitry Andric const DenseMap<Value *, SmallVector<const Value *, 16>>
3335f757f3fSDimitry Andric &UnderlyingObjects);
3340b57cec5SDimitry Andric
3350b57cec5SDimitry Andric /// Check whether the data dependence could prevent store-load
3360b57cec5SDimitry Andric /// forwarding.
3370b57cec5SDimitry Andric ///
3380b57cec5SDimitry Andric /// \return false if we shouldn't vectorize at all or avoid larger
3395f757f3fSDimitry Andric /// vectorization factors by limiting MinDepDistBytes.
3400b57cec5SDimitry Andric bool couldPreventStoreLoadForward(uint64_t Distance, uint64_t TypeByteSize);
3410b57cec5SDimitry Andric
3420b57cec5SDimitry Andric /// Updates the current safety status with \p S. We can go from Safe to
3430b57cec5SDimitry Andric /// either PossiblySafeWithRtChecks or Unsafe and from
3440b57cec5SDimitry Andric /// PossiblySafeWithRtChecks to Unsafe.
3450b57cec5SDimitry Andric void mergeInStatus(VectorizationSafetyStatus S);
3460b57cec5SDimitry Andric };
3470b57cec5SDimitry Andric
3485ffd83dbSDimitry Andric class RuntimePointerChecking;
3495ffd83dbSDimitry Andric /// A grouping of pointers. A single memcheck is required between
3505ffd83dbSDimitry Andric /// two groups.
3515ffd83dbSDimitry Andric struct RuntimeCheckingPtrGroup {
3525ffd83dbSDimitry Andric /// Create a new pointer checking group containing a single
3535ffd83dbSDimitry Andric /// pointer, with index \p Index in RtCheck.
3545ffd83dbSDimitry Andric RuntimeCheckingPtrGroup(unsigned Index, RuntimePointerChecking &RtCheck);
3555ffd83dbSDimitry Andric
3565ffd83dbSDimitry Andric /// Tries to add the pointer recorded in RtCheck at index
3575ffd83dbSDimitry Andric /// \p Index to this pointer checking group. We can only add a pointer
3585ffd83dbSDimitry Andric /// to a checking group if we will still be able to get
3595ffd83dbSDimitry Andric /// the upper and lower bounds of the check. Returns true in case
3605ffd83dbSDimitry Andric /// of success, false otherwise.
361fe6060f1SDimitry Andric bool addPointer(unsigned Index, RuntimePointerChecking &RtCheck);
362fe6060f1SDimitry Andric bool addPointer(unsigned Index, const SCEV *Start, const SCEV *End,
36381ad6265SDimitry Andric unsigned AS, bool NeedsFreeze, ScalarEvolution &SE);
3645ffd83dbSDimitry Andric
3655ffd83dbSDimitry Andric /// The SCEV expression which represents the upper bound of all the
3665ffd83dbSDimitry Andric /// pointers in this group.
3675ffd83dbSDimitry Andric const SCEV *High;
3685ffd83dbSDimitry Andric /// The SCEV expression which represents the lower bound of all the
3695ffd83dbSDimitry Andric /// pointers in this group.
3705ffd83dbSDimitry Andric const SCEV *Low;
3715ffd83dbSDimitry Andric /// Indices of all the pointers that constitute this grouping.
3725ffd83dbSDimitry Andric SmallVector<unsigned, 2> Members;
373fe6060f1SDimitry Andric /// Address space of the involved pointers.
374fe6060f1SDimitry Andric unsigned AddressSpace;
37581ad6265SDimitry Andric /// Whether the pointer needs to be frozen after expansion, e.g. because it
37681ad6265SDimitry Andric /// may be poison outside the loop.
37781ad6265SDimitry Andric bool NeedsFreeze = false;
3785ffd83dbSDimitry Andric };
3795ffd83dbSDimitry Andric
3805ffd83dbSDimitry Andric /// A memcheck which made up of a pair of grouped pointers.
3815ffd83dbSDimitry Andric typedef std::pair<const RuntimeCheckingPtrGroup *,
3825ffd83dbSDimitry Andric const RuntimeCheckingPtrGroup *>
3835ffd83dbSDimitry Andric RuntimePointerCheck;
3845ffd83dbSDimitry Andric
38581ad6265SDimitry Andric struct PointerDiffInfo {
38681ad6265SDimitry Andric const SCEV *SrcStart;
38781ad6265SDimitry Andric const SCEV *SinkStart;
38881ad6265SDimitry Andric unsigned AccessSize;
38981ad6265SDimitry Andric bool NeedsFreeze;
39081ad6265SDimitry Andric
PointerDiffInfoPointerDiffInfo39181ad6265SDimitry Andric PointerDiffInfo(const SCEV *SrcStart, const SCEV *SinkStart,
39281ad6265SDimitry Andric unsigned AccessSize, bool NeedsFreeze)
39381ad6265SDimitry Andric : SrcStart(SrcStart), SinkStart(SinkStart), AccessSize(AccessSize),
39481ad6265SDimitry Andric NeedsFreeze(NeedsFreeze) {}
39581ad6265SDimitry Andric };
39681ad6265SDimitry Andric
3970b57cec5SDimitry Andric /// Holds information about the memory runtime legality checks to verify
3980b57cec5SDimitry Andric /// that a group of pointers do not overlap.
3990b57cec5SDimitry Andric class RuntimePointerChecking {
4005ffd83dbSDimitry Andric friend struct RuntimeCheckingPtrGroup;
4015ffd83dbSDimitry Andric
4020b57cec5SDimitry Andric public:
4030b57cec5SDimitry Andric struct PointerInfo {
4040b57cec5SDimitry Andric /// Holds the pointer value that we need to check.
4050b57cec5SDimitry Andric TrackingVH<Value> PointerValue;
4060b57cec5SDimitry Andric /// Holds the smallest byte address accessed by the pointer throughout all
4070b57cec5SDimitry Andric /// iterations of the loop.
4080b57cec5SDimitry Andric const SCEV *Start;
4090b57cec5SDimitry Andric /// Holds the largest byte address accessed by the pointer throughout all
4100b57cec5SDimitry Andric /// iterations of the loop, plus 1.
4110b57cec5SDimitry Andric const SCEV *End;
4120b57cec5SDimitry Andric /// Holds the information if this pointer is used for writing to memory.
4130b57cec5SDimitry Andric bool IsWritePtr;
4140b57cec5SDimitry Andric /// Holds the id of the set of pointers that could be dependent because of a
4150b57cec5SDimitry Andric /// shared underlying object.
4160b57cec5SDimitry Andric unsigned DependencySetId;
4170b57cec5SDimitry Andric /// Holds the id of the disjoint alias set to which this pointer belongs.
4180b57cec5SDimitry Andric unsigned AliasSetId;
4190b57cec5SDimitry Andric /// SCEV for the access.
4200b57cec5SDimitry Andric const SCEV *Expr;
42181ad6265SDimitry Andric /// True if the pointer expressions needs to be frozen after expansion.
42281ad6265SDimitry Andric bool NeedsFreeze;
4230b57cec5SDimitry Andric
PointerInfoPointerInfo4240b57cec5SDimitry Andric PointerInfo(Value *PointerValue, const SCEV *Start, const SCEV *End,
4250b57cec5SDimitry Andric bool IsWritePtr, unsigned DependencySetId, unsigned AliasSetId,
42681ad6265SDimitry Andric const SCEV *Expr, bool NeedsFreeze)
4270b57cec5SDimitry Andric : PointerValue(PointerValue), Start(Start), End(End),
4280b57cec5SDimitry Andric IsWritePtr(IsWritePtr), DependencySetId(DependencySetId),
42981ad6265SDimitry Andric AliasSetId(AliasSetId), Expr(Expr), NeedsFreeze(NeedsFreeze) {}
4300b57cec5SDimitry Andric };
4310b57cec5SDimitry Andric
RuntimePointerChecking(MemoryDepChecker & DC,ScalarEvolution * SE)43281ad6265SDimitry Andric RuntimePointerChecking(MemoryDepChecker &DC, ScalarEvolution *SE)
43381ad6265SDimitry Andric : DC(DC), SE(SE) {}
4340b57cec5SDimitry Andric
4350b57cec5SDimitry Andric /// Reset the state of the pointer runtime information.
reset()4360b57cec5SDimitry Andric void reset() {
4370b57cec5SDimitry Andric Need = false;
4380b57cec5SDimitry Andric Pointers.clear();
4390b57cec5SDimitry Andric Checks.clear();
4400b57cec5SDimitry Andric }
4410b57cec5SDimitry Andric
4420b57cec5SDimitry Andric /// Insert a pointer and calculate the start and end SCEVs.
4430b57cec5SDimitry Andric /// We need \p PSE in order to compute the SCEV expression of the pointer
4440b57cec5SDimitry Andric /// according to the assumptions that we've made during the analysis.
4450b57cec5SDimitry Andric /// The method might also version the pointer stride according to \p Strides,
4460b57cec5SDimitry Andric /// and add new predicates to \p PSE.
44781ad6265SDimitry Andric void insert(Loop *Lp, Value *Ptr, const SCEV *PtrExpr, Type *AccessTy,
44881ad6265SDimitry Andric bool WritePtr, unsigned DepSetId, unsigned ASId,
44981ad6265SDimitry Andric PredicatedScalarEvolution &PSE, bool NeedsFreeze);
4500b57cec5SDimitry Andric
4510b57cec5SDimitry Andric /// No run-time memory checking is necessary.
empty()4520b57cec5SDimitry Andric bool empty() const { return Pointers.empty(); }
4530b57cec5SDimitry Andric
4540b57cec5SDimitry Andric /// Generate the checks and store it. This also performs the grouping
4550b57cec5SDimitry Andric /// of pointers to reduce the number of memchecks necessary.
4560b57cec5SDimitry Andric void generateChecks(MemoryDepChecker::DepCandidates &DepCands,
4570b57cec5SDimitry Andric bool UseDependencies);
4580b57cec5SDimitry Andric
45981ad6265SDimitry Andric /// Returns the checks that generateChecks created. They can be used to ensure
46081ad6265SDimitry Andric /// no read/write accesses overlap across all loop iterations.
getChecks()461e8d8bef9SDimitry Andric const SmallVectorImpl<RuntimePointerCheck> &getChecks() const {
4625ffd83dbSDimitry Andric return Checks;
4635ffd83dbSDimitry Andric }
4640b57cec5SDimitry Andric
46581ad6265SDimitry Andric // Returns an optional list of (pointer-difference expressions, access size)
46681ad6265SDimitry Andric // pairs that can be used to prove that there are no vectorization-preventing
46781ad6265SDimitry Andric // dependencies at runtime. There are is a vectorization-preventing dependency
46881ad6265SDimitry Andric // if any pointer-difference is <u VF * InterleaveCount * access size. Returns
469bdd1243dSDimitry Andric // std::nullopt if pointer-difference checks cannot be used.
getDiffChecks()470bdd1243dSDimitry Andric std::optional<ArrayRef<PointerDiffInfo>> getDiffChecks() const {
47181ad6265SDimitry Andric if (!CanUseDiffCheck)
472bdd1243dSDimitry Andric return std::nullopt;
47381ad6265SDimitry Andric return {DiffChecks};
47481ad6265SDimitry Andric }
47581ad6265SDimitry Andric
4760b57cec5SDimitry Andric /// Decide if we need to add a check between two groups of pointers,
4770b57cec5SDimitry Andric /// according to needsChecking.
4785ffd83dbSDimitry Andric bool needsChecking(const RuntimeCheckingPtrGroup &M,
4795ffd83dbSDimitry Andric const RuntimeCheckingPtrGroup &N) const;
4800b57cec5SDimitry Andric
4810b57cec5SDimitry Andric /// Returns the number of run-time checks required according to
4820b57cec5SDimitry Andric /// needsChecking.
getNumberOfChecks()4830b57cec5SDimitry Andric unsigned getNumberOfChecks() const { return Checks.size(); }
4840b57cec5SDimitry Andric
4850b57cec5SDimitry Andric /// Print the list run-time memory checks necessary.
4860b57cec5SDimitry Andric void print(raw_ostream &OS, unsigned Depth = 0) const;
4870b57cec5SDimitry Andric
4880b57cec5SDimitry Andric /// Print \p Checks.
4895ffd83dbSDimitry Andric void printChecks(raw_ostream &OS,
4905ffd83dbSDimitry Andric const SmallVectorImpl<RuntimePointerCheck> &Checks,
4910b57cec5SDimitry Andric unsigned Depth = 0) const;
4920b57cec5SDimitry Andric
4930b57cec5SDimitry Andric /// This flag indicates if we need to add the runtime check.
49404eeddc0SDimitry Andric bool Need = false;
4950b57cec5SDimitry Andric
4960b57cec5SDimitry Andric /// Information about the pointers that may require checking.
4970b57cec5SDimitry Andric SmallVector<PointerInfo, 2> Pointers;
4980b57cec5SDimitry Andric
4990b57cec5SDimitry Andric /// Holds a partitioning of pointers into "check groups".
5005ffd83dbSDimitry Andric SmallVector<RuntimeCheckingPtrGroup, 2> CheckingGroups;
5010b57cec5SDimitry Andric
5020b57cec5SDimitry Andric /// Check if pointers are in the same partition
5030b57cec5SDimitry Andric ///
5040b57cec5SDimitry Andric /// \p PtrToPartition contains the partition number for pointers (-1 if the
5050b57cec5SDimitry Andric /// pointer belongs to multiple partitions).
5060b57cec5SDimitry Andric static bool
5070b57cec5SDimitry Andric arePointersInSamePartition(const SmallVectorImpl<int> &PtrToPartition,
5080b57cec5SDimitry Andric unsigned PtrIdx1, unsigned PtrIdx2);
5090b57cec5SDimitry Andric
5100b57cec5SDimitry Andric /// Decide whether we need to issue a run-time check for pointer at
5110b57cec5SDimitry Andric /// index \p I and \p J to prove their independence.
5120b57cec5SDimitry Andric bool needsChecking(unsigned I, unsigned J) const;
5130b57cec5SDimitry Andric
5140b57cec5SDimitry Andric /// Return PointerInfo for pointer at index \p PtrIdx.
getPointerInfo(unsigned PtrIdx)5150b57cec5SDimitry Andric const PointerInfo &getPointerInfo(unsigned PtrIdx) const {
5160b57cec5SDimitry Andric return Pointers[PtrIdx];
5170b57cec5SDimitry Andric }
5180b57cec5SDimitry Andric
getSE()5195ffd83dbSDimitry Andric ScalarEvolution *getSE() const { return SE; }
5205ffd83dbSDimitry Andric
5210b57cec5SDimitry Andric private:
5220b57cec5SDimitry Andric /// Groups pointers such that a single memcheck is required
5230b57cec5SDimitry Andric /// between two different groups. This will clear the CheckingGroups vector
5240b57cec5SDimitry Andric /// and re-compute it. We will only group dependecies if \p UseDependencies
5250b57cec5SDimitry Andric /// is true, otherwise we will create a separate group for each pointer.
5260b57cec5SDimitry Andric void groupChecks(MemoryDepChecker::DepCandidates &DepCands,
5270b57cec5SDimitry Andric bool UseDependencies);
5280b57cec5SDimitry Andric
5290b57cec5SDimitry Andric /// Generate the checks and return them.
53081ad6265SDimitry Andric SmallVector<RuntimePointerCheck, 4> generateChecks();
53181ad6265SDimitry Andric
53281ad6265SDimitry Andric /// Try to create add a new (pointer-difference, access size) pair to
53381ad6265SDimitry Andric /// DiffCheck for checking groups \p CGI and \p CGJ. If pointer-difference
53481ad6265SDimitry Andric /// checks cannot be used for the groups, set CanUseDiffCheck to false.
53581ad6265SDimitry Andric void tryToCreateDiffCheck(const RuntimeCheckingPtrGroup &CGI,
53681ad6265SDimitry Andric const RuntimeCheckingPtrGroup &CGJ);
53781ad6265SDimitry Andric
53881ad6265SDimitry Andric MemoryDepChecker &DC;
5390b57cec5SDimitry Andric
5400b57cec5SDimitry Andric /// Holds a pointer to the ScalarEvolution analysis.
5410b57cec5SDimitry Andric ScalarEvolution *SE;
5420b57cec5SDimitry Andric
5430b57cec5SDimitry Andric /// Set of run-time checks required to establish independence of
5440b57cec5SDimitry Andric /// otherwise may-aliasing pointers in the loop.
5455ffd83dbSDimitry Andric SmallVector<RuntimePointerCheck, 4> Checks;
54681ad6265SDimitry Andric
54781ad6265SDimitry Andric /// Flag indicating if pointer-difference checks can be used
54881ad6265SDimitry Andric bool CanUseDiffCheck = true;
54981ad6265SDimitry Andric
55081ad6265SDimitry Andric /// A list of (pointer-difference, access size) pairs that can be used to
55181ad6265SDimitry Andric /// prove that there are no vectorization-preventing dependencies.
55281ad6265SDimitry Andric SmallVector<PointerDiffInfo> DiffChecks;
5530b57cec5SDimitry Andric };
5540b57cec5SDimitry Andric
5550b57cec5SDimitry Andric /// Drive the analysis of memory accesses in the loop
5560b57cec5SDimitry Andric ///
5570b57cec5SDimitry Andric /// This class is responsible for analyzing the memory accesses of a loop. It
5580b57cec5SDimitry Andric /// collects the accesses and then its main helper the AccessAnalysis class
5590b57cec5SDimitry Andric /// finds and categorizes the dependences in buildDependenceSets.
5600b57cec5SDimitry Andric ///
5610b57cec5SDimitry Andric /// For memory dependences that can be analyzed at compile time, it determines
5620b57cec5SDimitry Andric /// whether the dependence is part of cycle inhibiting vectorization. This work
5630b57cec5SDimitry Andric /// is delegated to the MemoryDepChecker class.
5640b57cec5SDimitry Andric ///
5650b57cec5SDimitry Andric /// For memory dependences that cannot be determined at compile time, it
5660b57cec5SDimitry Andric /// generates run-time checks to prove independence. This is done by
5670b57cec5SDimitry Andric /// AccessAnalysis::canCheckPtrAtRT and the checks are maintained by the
5680b57cec5SDimitry Andric /// RuntimePointerCheck class.
5690b57cec5SDimitry Andric ///
5700b57cec5SDimitry Andric /// If pointers can wrap or can't be expressed as affine AddRec expressions by
5710b57cec5SDimitry Andric /// ScalarEvolution, we will generate run-time checks by emitting a
5720b57cec5SDimitry Andric /// SCEVUnionPredicate.
5730b57cec5SDimitry Andric ///
5740b57cec5SDimitry Andric /// Checks for both memory dependences and the SCEV predicates contained in the
5750b57cec5SDimitry Andric /// PSE must be emitted in order for the results of this analysis to be valid.
5760b57cec5SDimitry Andric class LoopAccessInfo {
5770b57cec5SDimitry Andric public:
5780b57cec5SDimitry Andric LoopAccessInfo(Loop *L, ScalarEvolution *SE, const TargetLibraryInfo *TLI,
5795ffd83dbSDimitry Andric AAResults *AA, DominatorTree *DT, LoopInfo *LI);
5800b57cec5SDimitry Andric
5810b57cec5SDimitry Andric /// Return true we can analyze the memory accesses in the loop and there are
5820b57cec5SDimitry Andric /// no memory dependence cycles.
canVectorizeMemory()5830b57cec5SDimitry Andric bool canVectorizeMemory() const { return CanVecMem; }
5840b57cec5SDimitry Andric
5850b57cec5SDimitry Andric /// Return true if there is a convergent operation in the loop. There may
5860b57cec5SDimitry Andric /// still be reported runtime pointer checks that would be required, but it is
5870b57cec5SDimitry Andric /// not legal to insert them.
hasConvergentOp()5880b57cec5SDimitry Andric bool hasConvergentOp() const { return HasConvergentOp; }
5890b57cec5SDimitry Andric
getRuntimePointerChecking()5900b57cec5SDimitry Andric const RuntimePointerChecking *getRuntimePointerChecking() const {
5910b57cec5SDimitry Andric return PtrRtChecking.get();
5920b57cec5SDimitry Andric }
5930b57cec5SDimitry Andric
5940b57cec5SDimitry Andric /// Number of memchecks required to prove independence of otherwise
5950b57cec5SDimitry Andric /// may-alias pointers.
getNumRuntimePointerChecks()5960b57cec5SDimitry Andric unsigned getNumRuntimePointerChecks() const {
5970b57cec5SDimitry Andric return PtrRtChecking->getNumberOfChecks();
5980b57cec5SDimitry Andric }
5990b57cec5SDimitry Andric
6000b57cec5SDimitry Andric /// Return true if the block BB needs to be predicated in order for the loop
6010b57cec5SDimitry Andric /// to be vectorized.
6020b57cec5SDimitry Andric static bool blockNeedsPredication(BasicBlock *BB, Loop *TheLoop,
6030b57cec5SDimitry Andric DominatorTree *DT);
6040b57cec5SDimitry Andric
60506c3fb27SDimitry Andric /// Returns true if value \p V is loop invariant.
60606c3fb27SDimitry Andric bool isInvariant(Value *V) const;
6070b57cec5SDimitry Andric
getNumStores()6080b57cec5SDimitry Andric unsigned getNumStores() const { return NumStores; }
getNumLoads()6090b57cec5SDimitry Andric unsigned getNumLoads() const { return NumLoads;}
6100b57cec5SDimitry Andric
6110b57cec5SDimitry Andric /// The diagnostics report generated for the analysis. E.g. why we
6120b57cec5SDimitry Andric /// couldn't analyze the loop.
getReport()6130b57cec5SDimitry Andric const OptimizationRemarkAnalysis *getReport() const { return Report.get(); }
6140b57cec5SDimitry Andric
6150b57cec5SDimitry Andric /// the Memory Dependence Checker which can determine the
6160b57cec5SDimitry Andric /// loop-independent and loop-carried dependences between memory accesses.
getDepChecker()6170b57cec5SDimitry Andric const MemoryDepChecker &getDepChecker() const { return *DepChecker; }
6180b57cec5SDimitry Andric
6190b57cec5SDimitry Andric /// Return the list of instructions that use \p Ptr to read or write
6200b57cec5SDimitry Andric /// memory.
getInstructionsForAccess(Value * Ptr,bool isWrite)6210b57cec5SDimitry Andric SmallVector<Instruction *, 4> getInstructionsForAccess(Value *Ptr,
6220b57cec5SDimitry Andric bool isWrite) const {
6230b57cec5SDimitry Andric return DepChecker->getInstructionsForAccess(Ptr, isWrite);
6240b57cec5SDimitry Andric }
6250b57cec5SDimitry Andric
6260b57cec5SDimitry Andric /// If an access has a symbolic strides, this maps the pointer value to
6270b57cec5SDimitry Andric /// the stride symbol.
getSymbolicStrides()62806c3fb27SDimitry Andric const DenseMap<Value *, const SCEV *> &getSymbolicStrides() const {
62906c3fb27SDimitry Andric return SymbolicStrides;
63006c3fb27SDimitry Andric }
6310b57cec5SDimitry Andric
6320b57cec5SDimitry Andric /// Print the information about the memory accesses in the loop.
6330b57cec5SDimitry Andric void print(raw_ostream &OS, unsigned Depth = 0) const;
6340b57cec5SDimitry Andric
6350b57cec5SDimitry Andric /// If the loop has memory dependence involving an invariant address, i.e. two
6360b57cec5SDimitry Andric /// stores or a store and a load, then return true, else return false.
hasDependenceInvolvingLoopInvariantAddress()6370b57cec5SDimitry Andric bool hasDependenceInvolvingLoopInvariantAddress() const {
6380b57cec5SDimitry Andric return HasDependenceInvolvingLoopInvariantAddress;
6390b57cec5SDimitry Andric }
6400b57cec5SDimitry Andric
64181ad6265SDimitry Andric /// Return the list of stores to invariant addresses.
getStoresToInvariantAddresses()642bdd1243dSDimitry Andric ArrayRef<StoreInst *> getStoresToInvariantAddresses() const {
64381ad6265SDimitry Andric return StoresToInvariantAddresses;
64481ad6265SDimitry Andric }
64581ad6265SDimitry Andric
6460b57cec5SDimitry Andric /// Used to add runtime SCEV checks. Simplifies SCEV expressions and converts
6470b57cec5SDimitry Andric /// them to a more usable form. All SCEV expressions during the analysis
6480b57cec5SDimitry Andric /// should be re-written (and therefore simplified) according to PSE.
6490b57cec5SDimitry Andric /// A user of LoopAccessAnalysis will need to emit the runtime checks
6500b57cec5SDimitry Andric /// associated with this predicate.
getPSE()6510b57cec5SDimitry Andric const PredicatedScalarEvolution &getPSE() const { return *PSE; }
6520b57cec5SDimitry Andric
6530b57cec5SDimitry Andric private:
6540b57cec5SDimitry Andric /// Analyze the loop.
6555ffd83dbSDimitry Andric void analyzeLoop(AAResults *AA, LoopInfo *LI,
6560b57cec5SDimitry Andric const TargetLibraryInfo *TLI, DominatorTree *DT);
6570b57cec5SDimitry Andric
6580b57cec5SDimitry Andric /// Check if the structure of the loop allows it to be analyzed by this
6590b57cec5SDimitry Andric /// pass.
6600b57cec5SDimitry Andric bool canAnalyzeLoop();
6610b57cec5SDimitry Andric
6620b57cec5SDimitry Andric /// Save the analysis remark.
6630b57cec5SDimitry Andric ///
6640b57cec5SDimitry Andric /// LAA does not directly emits the remarks. Instead it stores it which the
6650b57cec5SDimitry Andric /// client can retrieve and presents as its own analysis
6660b57cec5SDimitry Andric /// (e.g. -Rpass-analysis=loop-vectorize).
6670b57cec5SDimitry Andric OptimizationRemarkAnalysis &recordAnalysis(StringRef RemarkName,
6680b57cec5SDimitry Andric Instruction *Instr = nullptr);
6690b57cec5SDimitry Andric
6700b57cec5SDimitry Andric /// Collect memory access with loop invariant strides.
6710b57cec5SDimitry Andric ///
6720b57cec5SDimitry Andric /// Looks for accesses like "a[i * StrideA]" where "StrideA" is loop
6730b57cec5SDimitry Andric /// invariant.
6740b57cec5SDimitry Andric void collectStridedAccess(Value *LoadOrStoreInst);
6750b57cec5SDimitry Andric
67681ad6265SDimitry Andric // Emits the first unsafe memory dependence in a loop.
67781ad6265SDimitry Andric // Emits nothing if there are no unsafe dependences
67881ad6265SDimitry Andric // or if the dependences were not recorded.
67981ad6265SDimitry Andric void emitUnsafeDependenceRemark();
68081ad6265SDimitry Andric
6810b57cec5SDimitry Andric std::unique_ptr<PredicatedScalarEvolution> PSE;
6820b57cec5SDimitry Andric
6830b57cec5SDimitry Andric /// We need to check that all of the pointers in this list are disjoint
6840b57cec5SDimitry Andric /// at runtime. Using std::unique_ptr to make using move ctor simpler.
6850b57cec5SDimitry Andric std::unique_ptr<RuntimePointerChecking> PtrRtChecking;
6860b57cec5SDimitry Andric
6870b57cec5SDimitry Andric /// the Memory Dependence Checker which can determine the
6880b57cec5SDimitry Andric /// loop-independent and loop-carried dependences between memory accesses.
6890b57cec5SDimitry Andric std::unique_ptr<MemoryDepChecker> DepChecker;
6900b57cec5SDimitry Andric
6910b57cec5SDimitry Andric Loop *TheLoop;
6920b57cec5SDimitry Andric
69304eeddc0SDimitry Andric unsigned NumLoads = 0;
69404eeddc0SDimitry Andric unsigned NumStores = 0;
6950b57cec5SDimitry Andric
6960b57cec5SDimitry Andric /// Cache the result of analyzeLoop.
69704eeddc0SDimitry Andric bool CanVecMem = false;
69804eeddc0SDimitry Andric bool HasConvergentOp = false;
6990b57cec5SDimitry Andric
7000b57cec5SDimitry Andric /// Indicator that there are non vectorizable stores to a uniform address.
70104eeddc0SDimitry Andric bool HasDependenceInvolvingLoopInvariantAddress = false;
7020b57cec5SDimitry Andric
70381ad6265SDimitry Andric /// List of stores to invariant addresses.
70481ad6265SDimitry Andric SmallVector<StoreInst *> StoresToInvariantAddresses;
70581ad6265SDimitry Andric
7060b57cec5SDimitry Andric /// The diagnostics report generated for the analysis. E.g. why we
7070b57cec5SDimitry Andric /// couldn't analyze the loop.
7080b57cec5SDimitry Andric std::unique_ptr<OptimizationRemarkAnalysis> Report;
7090b57cec5SDimitry Andric
7100b57cec5SDimitry Andric /// If an access has a symbolic strides, this maps the pointer value to
7110b57cec5SDimitry Andric /// the stride symbol.
71206c3fb27SDimitry Andric DenseMap<Value *, const SCEV *> SymbolicStrides;
7130b57cec5SDimitry Andric };
7140b57cec5SDimitry Andric
7150b57cec5SDimitry Andric /// Return the SCEV corresponding to a pointer with the symbolic stride
7160b57cec5SDimitry Andric /// replaced with constant one, assuming the SCEV predicate associated with
7170b57cec5SDimitry Andric /// \p PSE is true.
7180b57cec5SDimitry Andric ///
7190b57cec5SDimitry Andric /// If necessary this method will version the stride of the pointer according
7200b57cec5SDimitry Andric /// to \p PtrToStride and therefore add further predicates to \p PSE.
7210b57cec5SDimitry Andric ///
722349cc55cSDimitry Andric /// \p PtrToStride provides the mapping between the pointer value and its
7230b57cec5SDimitry Andric /// stride as collected by LoopVectorizationLegality::collectStridedAccess.
72406c3fb27SDimitry Andric const SCEV *
72506c3fb27SDimitry Andric replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE,
72606c3fb27SDimitry Andric const DenseMap<Value *, const SCEV *> &PtrToStride,
727349cc55cSDimitry Andric Value *Ptr);
7280b57cec5SDimitry Andric
729349cc55cSDimitry Andric /// If the pointer has a constant stride return it in units of the access type
730bdd1243dSDimitry Andric /// size. Otherwise return std::nullopt.
7310b57cec5SDimitry Andric ///
7320b57cec5SDimitry Andric /// Ensure that it does not wrap in the address space, assuming the predicate
7330b57cec5SDimitry Andric /// associated with \p PSE is true.
7340b57cec5SDimitry Andric ///
7350b57cec5SDimitry Andric /// If necessary this method will version the stride of the pointer according
7360b57cec5SDimitry Andric /// to \p PtrToStride and therefore add further predicates to \p PSE.
7370b57cec5SDimitry Andric /// The \p Assume parameter indicates if we are allowed to make additional
7380b57cec5SDimitry Andric /// run-time assumptions.
73906c3fb27SDimitry Andric ///
74006c3fb27SDimitry Andric /// Note that the analysis results are defined if-and-only-if the original
74106c3fb27SDimitry Andric /// memory access was defined. If that access was dead, or UB, then the
74206c3fb27SDimitry Andric /// result of this function is undefined.
743bdd1243dSDimitry Andric std::optional<int64_t>
744bdd1243dSDimitry Andric getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr,
745349cc55cSDimitry Andric const Loop *Lp,
74606c3fb27SDimitry Andric const DenseMap<Value *, const SCEV *> &StridesMap = DenseMap<Value *, const SCEV *>(),
7470b57cec5SDimitry Andric bool Assume = false, bool ShouldCheckWrap = true);
7480b57cec5SDimitry Andric
749fe6060f1SDimitry Andric /// Returns the distance between the pointers \p PtrA and \p PtrB iff they are
750fe6060f1SDimitry Andric /// compatible and it is possible to calculate the distance between them. This
751fe6060f1SDimitry Andric /// is a simple API that does not depend on the analysis pass.
752fe6060f1SDimitry Andric /// \param StrictCheck Ensure that the calculated distance matches the
753fe6060f1SDimitry Andric /// type-based one after all the bitcasts removal in the provided pointers.
754bdd1243dSDimitry Andric std::optional<int> getPointersDiff(Type *ElemTyA, Value *PtrA, Type *ElemTyB,
755fe6060f1SDimitry Andric Value *PtrB, const DataLayout &DL,
756bdd1243dSDimitry Andric ScalarEvolution &SE,
757bdd1243dSDimitry Andric bool StrictCheck = false,
758fe6060f1SDimitry Andric bool CheckType = true);
759fe6060f1SDimitry Andric
7600b57cec5SDimitry Andric /// Attempt to sort the pointers in \p VL and return the sorted indices
7610b57cec5SDimitry Andric /// in \p SortedIndices, if reordering is required.
7620b57cec5SDimitry Andric ///
7630b57cec5SDimitry Andric /// Returns 'true' if sorting is legal, otherwise returns 'false'.
7640b57cec5SDimitry Andric ///
7650b57cec5SDimitry Andric /// For example, for a given \p VL of memory accesses in program order, a[i+4],
7660b57cec5SDimitry Andric /// a[i+0], a[i+1] and a[i+7], this function will sort the \p VL and save the
7670b57cec5SDimitry Andric /// sorted indices in \p SortedIndices as a[i+0], a[i+1], a[i+4], a[i+7] and
7680b57cec5SDimitry Andric /// saves the mask for actual memory accesses in program order in
7690b57cec5SDimitry Andric /// \p SortedIndices as <1,2,0,3>
770fe6060f1SDimitry Andric bool sortPtrAccesses(ArrayRef<Value *> VL, Type *ElemTy, const DataLayout &DL,
7710b57cec5SDimitry Andric ScalarEvolution &SE,
7720b57cec5SDimitry Andric SmallVectorImpl<unsigned> &SortedIndices);
7730b57cec5SDimitry Andric
7740b57cec5SDimitry Andric /// Returns true if the memory operations \p A and \p B are consecutive.
7750b57cec5SDimitry Andric /// This is a simple API that does not depend on the analysis pass.
7760b57cec5SDimitry Andric bool isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL,
7770b57cec5SDimitry Andric ScalarEvolution &SE, bool CheckType = true);
7780b57cec5SDimitry Andric
779bdd1243dSDimitry Andric class LoopAccessInfoManager {
780bdd1243dSDimitry Andric /// The cache.
781bdd1243dSDimitry Andric DenseMap<Loop *, std::unique_ptr<LoopAccessInfo>> LoopAccessInfoMap;
782bdd1243dSDimitry Andric
783bdd1243dSDimitry Andric // The used analysis passes.
784bdd1243dSDimitry Andric ScalarEvolution &SE;
785bdd1243dSDimitry Andric AAResults &AA;
786bdd1243dSDimitry Andric DominatorTree &DT;
787bdd1243dSDimitry Andric LoopInfo &LI;
788bdd1243dSDimitry Andric const TargetLibraryInfo *TLI = nullptr;
789bdd1243dSDimitry Andric
790bdd1243dSDimitry Andric public:
LoopAccessInfoManager(ScalarEvolution & SE,AAResults & AA,DominatorTree & DT,LoopInfo & LI,const TargetLibraryInfo * TLI)791bdd1243dSDimitry Andric LoopAccessInfoManager(ScalarEvolution &SE, AAResults &AA, DominatorTree &DT,
792bdd1243dSDimitry Andric LoopInfo &LI, const TargetLibraryInfo *TLI)
793bdd1243dSDimitry Andric : SE(SE), AA(AA), DT(DT), LI(LI), TLI(TLI) {}
794bdd1243dSDimitry Andric
795bdd1243dSDimitry Andric const LoopAccessInfo &getInfo(Loop &L);
796bdd1243dSDimitry Andric
clear()797bdd1243dSDimitry Andric void clear() { LoopAccessInfoMap.clear(); }
798bdd1243dSDimitry Andric
79906c3fb27SDimitry Andric bool invalidate(Function &F, const PreservedAnalyses &PA,
80006c3fb27SDimitry Andric FunctionAnalysisManager::Invalidator &Inv);
8010b57cec5SDimitry Andric };
8020b57cec5SDimitry Andric
8030b57cec5SDimitry Andric /// This analysis provides dependence information for the memory
8040b57cec5SDimitry Andric /// accesses of a loop.
8050b57cec5SDimitry Andric ///
8060b57cec5SDimitry Andric /// It runs the analysis for a loop on demand. This can be initiated by
8070b57cec5SDimitry Andric /// querying the loop access info via AM.getResult<LoopAccessAnalysis>.
8080b57cec5SDimitry Andric /// getResult return a LoopAccessInfo object. See this class for the
8090b57cec5SDimitry Andric /// specifics of what information is provided.
8100b57cec5SDimitry Andric class LoopAccessAnalysis
8110b57cec5SDimitry Andric : public AnalysisInfoMixin<LoopAccessAnalysis> {
8120b57cec5SDimitry Andric friend AnalysisInfoMixin<LoopAccessAnalysis>;
8130b57cec5SDimitry Andric static AnalysisKey Key;
8140b57cec5SDimitry Andric
8150b57cec5SDimitry Andric public:
816bdd1243dSDimitry Andric typedef LoopAccessInfoManager Result;
8170b57cec5SDimitry Andric
818bdd1243dSDimitry Andric Result run(Function &F, FunctionAnalysisManager &AM);
8190b57cec5SDimitry Andric };
8200b57cec5SDimitry Andric
getSource(const LoopAccessInfo & LAI)8210b57cec5SDimitry Andric inline Instruction *MemoryDepChecker::Dependence::getSource(
8220b57cec5SDimitry Andric const LoopAccessInfo &LAI) const {
8230b57cec5SDimitry Andric return LAI.getDepChecker().getMemoryInstructions()[Source];
8240b57cec5SDimitry Andric }
8250b57cec5SDimitry Andric
getDestination(const LoopAccessInfo & LAI)8260b57cec5SDimitry Andric inline Instruction *MemoryDepChecker::Dependence::getDestination(
8270b57cec5SDimitry Andric const LoopAccessInfo &LAI) const {
8280b57cec5SDimitry Andric return LAI.getDepChecker().getMemoryInstructions()[Destination];
8290b57cec5SDimitry Andric }
8300b57cec5SDimitry Andric
8310b57cec5SDimitry Andric } // End llvm namespace
8320b57cec5SDimitry Andric
8330b57cec5SDimitry Andric #endif
834