1//===- SLPMemoryUtils.h - SLP pointer/stride helpers -----------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Internal header used by SLPVectorizer.cpp. It declares free pointer and
10// stride helpers that do not depend on BoUpSLP or any other SLP-private type.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_LIB_TRANSFORMS_VECTORIZE_SLPVECTORIZER_SLPMEMORYUTILS_H
15#define LLVM_LIB_TRANSFORMS_VECTORIZE_SLPVECTORIZER_SLPMEMORYUTILS_H
16
17#include "llvm/ADT/ArrayRef.h"
18#include "llvm/ADT/DenseMap.h"
19#include "llvm/ADT/STLFunctionalExtras.h"
20#include "llvm/Analysis/TargetTransformInfo.h"
21#include "llvm/Support/Alignment.h"
22
23#include <cstdint>
24#include <optional>
25#include <tuple>
26
27namespace llvm {
28class AssumptionCache;
29class BasicBlock;
30class ConstantInt;
31class DataLayout;
32class DominatorTree;
33class FixedVectorType;
34class IRBuilderBase;
35class SCEV;
36class ScalarEvolution;
37class TargetLibraryInfo;
38class Type;
39class Value;
40class VectorType;
41} // namespace llvm
42
43namespace llvm::slpvectorizer {
44
45/// Caches the results of the expensive analyses that are queried repeatedly
46/// for the same values while the vectorization trees are built and their costs
47/// are estimated. The results may change once new code replaces the scalars,
48/// so the cache is cleared each time the replaced scalars are erased.
49class SLPAnalysisCache {
50public:
51 /// Cached llvm::getPointersDiff(), a miss may require SCEV analysis. The
52 /// result for (\p PtrA, \p PtrB) also serves the query for the swapped
53 /// pointers.
54 std::optional<int64_t>
55 getPointersDiff(Type *ElemTyA, Value *PtrA, Type *ElemTyB, Value *PtrB,
56 const DataLayout &DL, ScalarEvolution &SE,
57 bool StrictCheck = false, bool CheckType = true);
58
59 /// llvm::sortPtrAccesses() with the cached pointer distances.
60 bool sortPtrAccesses(ArrayRef<Value *> VL, Type *ElemTy, const DataLayout &DL,
61 ScalarEvolution &SE,
62 SmallVectorImpl<unsigned> &SortedIndices);
63
64 /// Cached llvm::isGuaranteedNotToBePoison().
65 bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC);
66
67 void clear() {
68 PtrsDiffCache.clear();
69 NotPoisonCache.clear();
70 }
71
72private:
73 using PtrsDiffKeyT = std::tuple<Type *, Value *, Type *, Value *, unsigned>;
74 SmallDenseMap<PtrsDiffKeyT, std::optional<int64_t>, 16> PtrsDiffCache;
75 SmallDenseMap<const Value *, bool, 16> NotPoisonCache;
76};
77
78/// \p MaxDepth is the recursion limit for getUnderlyingObject.
79bool arePointersCompatible(Value *Ptr1, Value *Ptr2,
80 const TargetLibraryInfo &TLI, unsigned MaxDepth,
81 bool CompareOpcodes = true);
82
83/// Returns \p Stride scaled by the allocation size of \p ScalarTy, negated if
84/// \p IsReverse is set, or nullptr if \p Stride is not a constant.
85ConstantInt *getStrideBytesIfConstant(Value *Stride, Type *ScalarTy,
86 const DataLayout &DL,
87 bool IsReverse = false);
88
89/// Casts \p V between the widened strided access type and the entry vector
90/// type \p DstTy.
91Value *createWidenedStridedCast(IRBuilderBase &Builder, Value *V, Type *DstTy,
92 const DataLayout &DL);
93
94/// Calculates minimal alignment as a common alignment.
95template <typename T> Align computeCommonAlignment(ArrayRef<Value *> VL);
96
97/// Checks if the provided list of pointers \p Pointers represents the strided
98/// pointers for type ElemTy. If they are not, nullptr is returned.
99/// Otherwise, SCEV* of the stride value is returned.
100/// If `PointerOps` can be rearranged into the following sequence:
101/// ```
102/// %x + c_0 * stride,
103/// %x + c_1 * stride,
104/// %x + c_2 * stride
105/// ...
106/// ```
107/// where each `c_i` is constant. The SCEV of the `stride` will be returned.
108const SCEV *calculateRtStride(ArrayRef<Value *> PointerOps, Type *ElemTy,
109 const DataLayout &DL, ScalarEvolution &SE,
110 SmallVectorImpl<unsigned> &SortedIndices);
111
112/// Checks if the \p VL can be transformed to a (masked)load + compress or
113/// (masked) interleaved load.
114bool isMaskedLoadCompress(
115 ArrayRef<Value *> VL, ArrayRef<Value *> PointerOps,
116 ArrayRef<unsigned> Order, const TargetTransformInfo &TTI,
117 const DataLayout &DL, ScalarEvolution &SE, AssumptionCache &AC,
118 const DominatorTree &DT, const TargetLibraryInfo &TLI,
119 const TargetTransformInfo::TargetCostKind CostKind,
120 const function_ref<bool(Value *)> AreAllUsersVectorized, bool ReVec,
121 bool &IsMasked, unsigned &InterleaveFactor,
122 SmallVectorImpl<int> &CompressMask, VectorType *&LoadVecTy,
123 SLPAnalysisCache &Cache);
124
125/// Checks if the \p VL can be transformed to a (masked)load + compress or
126/// (masked) interleaved load.
127bool isMaskedLoadCompress(
128 ArrayRef<Value *> VL, ArrayRef<Value *> PointerOps,
129 ArrayRef<unsigned> Order, const TargetTransformInfo &TTI,
130 const DataLayout &DL, ScalarEvolution &SE, AssumptionCache &AC,
131 const DominatorTree &DT, const TargetLibraryInfo &TLI,
132 const TargetTransformInfo::TargetCostKind CostKind,
133 const function_ref<bool(Value *)> AreAllUsersVectorized, bool ReVec,
134 SLPAnalysisCache &Cache);
135
136/// Checks if the simple loads of \p VL, mixed with the undef and poison lanes,
137/// can be replaced by a single load of the whole \p VL width. The loads must be
138/// consecutive and match their lanes, and the whole accessed range must be safe
139/// to load unconditionally.
140bool canWidenLoadsOverUndefLanes(ArrayRef<Value *> VL, const DataLayout &DL,
141 ScalarEvolution &SE, AssumptionCache &AC,
142 const DominatorTree &DT,
143 const TargetLibraryInfo &TLI);
144
145/// Returns the distance in bytes from the start of the vector load to the
146/// first load of \p Scalars: the leading undef lanes are covered by the vector
147/// load.
148uint64_t getVectorLoadShift(ArrayRef<Value *> Scalars);
149
150/// Checks if the stores \p VL with pointers \p PointerOps can be lowered as a
151/// single masked store. On success \p StoreVecTy is the widened store type and
152/// \p ReuseShuffleIndices is the expand mask that places each stored value at
153/// its element offset from the base (poison in the gaps).
154bool isMaskedStoreCompress(ArrayRef<Value *> VL, ArrayRef<Value *> PointerOps,
155 ArrayRef<unsigned> Order,
156 const TargetTransformInfo &TTI, const DataLayout &DL,
157 ScalarEvolution &SE, Align CommonAlignment,
158 SmallVectorImpl<int> &ReuseShuffleIndices,
159 FixedVectorType *&StoreVecTy,
160 SLPAnalysisCache &Cache);
161
162/// Clusters \p VL pointers by (basic block, underlying object) pair and sorts
163/// each cluster by offset. Returns false and leaves \p SortedIndices empty if
164/// the accesses are not worth reordering.
165bool clusterSortPtrAccesses(ArrayRef<Value *> VL, ArrayRef<BasicBlock *> BBs,
166 Type *ElemTy, const DataLayout &DL,
167 ScalarEvolution &SE, unsigned MaxDepth,
168 SmallVectorImpl<unsigned> &SortedIndices,
169 SLPAnalysisCache &Cache);
170
171} // namespace llvm::slpvectorizer
172
173#endif // LLVM_LIB_TRANSFORMS_VECTORIZE_SLPVECTORIZER_SLPMEMORYUTILS_H
174