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 the vectorized code is emitted
48/// and the scalars are erased, so the cache is cleared after each successful
49/// vectorizeTree().
50class SLPAnalysisCache {
51public:
52 /// Cached llvm::getPointersDiff(), a miss may require SCEV analysis. The
53 /// result for (\p PtrA, \p PtrB) also serves the query for the swapped
54 /// pointers.
55 std::optional<int64_t>
56 getPointersDiff(Type *ElemTyA, Value *PtrA, Type *ElemTyB, Value *PtrB,
57 const DataLayout &DL, ScalarEvolution &SE,
58 bool StrictCheck = false, bool CheckType = true);
59
60 /// Cached llvm::isGuaranteedNotToBePoison().
61 bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC);
62
63 void clear() {
64 PtrsDiffCache.clear();
65 NotPoisonCache.clear();
66 }
67
68private:
69 using PtrsDiffKeyT = std::tuple<Type *, Value *, Type *, Value *, unsigned>;
70 SmallDenseMap<PtrsDiffKeyT, std::optional<int64_t>, 16> PtrsDiffCache;
71 SmallDenseMap<const Value *, bool, 16> NotPoisonCache;
72};
73
74/// \p MaxDepth is the recursion limit for getUnderlyingObject.
75bool arePointersCompatible(Value *Ptr1, Value *Ptr2,
76 const TargetLibraryInfo &TLI, unsigned MaxDepth,
77 bool CompareOpcodes = true);
78
79/// Returns \p Stride scaled by the allocation size of \p ScalarTy, negated if
80/// \p IsReverse is set, or nullptr if \p Stride is not a constant.
81ConstantInt *getStrideBytesIfConstant(Value *Stride, Type *ScalarTy,
82 const DataLayout &DL,
83 bool IsReverse = false);
84
85/// Casts \p V between the widened strided access type and the entry vector
86/// type \p DstTy.
87Value *createWidenedStridedCast(IRBuilderBase &Builder, Value *V, Type *DstTy,
88 const DataLayout &DL);
89
90/// Calculates minimal alignment as a common alignment.
91template <typename T> Align computeCommonAlignment(ArrayRef<Value *> VL);
92
93/// Checks if the provided list of pointers \p Pointers represents the strided
94/// pointers for type ElemTy. If they are not, nullptr is returned.
95/// Otherwise, SCEV* of the stride value is returned.
96/// If `PointerOps` can be rearranged into the following sequence:
97/// ```
98/// %x + c_0 * stride,
99/// %x + c_1 * stride,
100/// %x + c_2 * stride
101/// ...
102/// ```
103/// where each `c_i` is constant. The SCEV of the `stride` will be returned.
104const SCEV *calculateRtStride(ArrayRef<Value *> PointerOps, Type *ElemTy,
105 const DataLayout &DL, ScalarEvolution &SE,
106 SmallVectorImpl<unsigned> &SortedIndices);
107
108/// Checks if the \p VL can be transformed to a (masked)load + compress or
109/// (masked) interleaved load.
110bool isMaskedLoadCompress(
111 ArrayRef<Value *> VL, ArrayRef<Value *> PointerOps,
112 ArrayRef<unsigned> Order, const TargetTransformInfo &TTI,
113 const DataLayout &DL, ScalarEvolution &SE, AssumptionCache &AC,
114 const DominatorTree &DT, const TargetLibraryInfo &TLI,
115 const TargetTransformInfo::TargetCostKind CostKind,
116 const function_ref<bool(Value *)> AreAllUsersVectorized, bool ReVec,
117 bool &IsMasked, unsigned &InterleaveFactor,
118 SmallVectorImpl<int> &CompressMask, VectorType *&LoadVecTy,
119 SLPAnalysisCache &Cache);
120
121/// Checks if the \p VL can be transformed to a (masked)load + compress or
122/// (masked) interleaved load.
123bool isMaskedLoadCompress(
124 ArrayRef<Value *> VL, ArrayRef<Value *> PointerOps,
125 ArrayRef<unsigned> Order, const TargetTransformInfo &TTI,
126 const DataLayout &DL, ScalarEvolution &SE, AssumptionCache &AC,
127 const DominatorTree &DT, const TargetLibraryInfo &TLI,
128 const TargetTransformInfo::TargetCostKind CostKind,
129 const function_ref<bool(Value *)> AreAllUsersVectorized, bool ReVec,
130 SLPAnalysisCache &Cache);
131
132/// Checks if the simple loads of \p VL, mixed with the undef and poison lanes,
133/// can be replaced by a single load of the whole \p VL width. The loads must be
134/// consecutive and match their lanes, and the whole accessed range must be safe
135/// to load unconditionally.
136bool canWidenLoadsOverUndefLanes(ArrayRef<Value *> VL, const DataLayout &DL,
137 ScalarEvolution &SE, AssumptionCache &AC,
138 const DominatorTree &DT,
139 const TargetLibraryInfo &TLI);
140
141/// Returns the distance in bytes from the start of the vector load to the
142/// first load of \p Scalars: the leading undef lanes are covered by the vector
143/// load.
144uint64_t getVectorLoadShift(ArrayRef<Value *> Scalars);
145
146/// Checks if the stores \p VL with pointers \p PointerOps can be lowered as a
147/// single masked store. On success \p StoreVecTy is the widened store type and
148/// \p ReuseShuffleIndices is the expand mask that places each stored value at
149/// its element offset from the base (poison in the gaps).
150bool isMaskedStoreCompress(ArrayRef<Value *> VL, ArrayRef<Value *> PointerOps,
151 ArrayRef<unsigned> Order,
152 const TargetTransformInfo &TTI, const DataLayout &DL,
153 ScalarEvolution &SE, Align CommonAlignment,
154 SmallVectorImpl<int> &ReuseShuffleIndices,
155 FixedVectorType *&StoreVecTy,
156 SLPAnalysisCache &Cache);
157
158/// Clusters \p VL pointers by (basic block, underlying object) pair and sorts
159/// each cluster by offset. Returns false and leaves \p SortedIndices empty if
160/// the accesses are not worth reordering.
161bool clusterSortPtrAccesses(ArrayRef<Value *> VL, ArrayRef<BasicBlock *> BBs,
162 Type *ElemTy, const DataLayout &DL,
163 ScalarEvolution &SE, unsigned MaxDepth,
164 SmallVectorImpl<unsigned> &SortedIndices,
165 SLPAnalysisCache &Cache);
166
167} // namespace llvm::slpvectorizer
168
169#endif // LLVM_LIB_TRANSFORMS_VECTORIZE_SLPVECTORIZER_SLPMEMORYUTILS_H
170