1//===- SLPMemoryUtils.cpp - SLP pointer/stride helpers --------------------===//
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#include "SLPMemoryUtils.h"
10#include "SLPCompatibilityAnalysis.h"
11#include "SLPCostAnalysis.h"
12#include "SLPTypeUtils.h"
13#include "SLPUtils.h"
14
15#include "llvm/ADT/APInt.h"
16#include "llvm/ADT/MapVector.h"
17#include "llvm/ADT/STLExtras.h"
18#include "llvm/ADT/Sequence.h"
19#include "llvm/ADT/SmallPtrSet.h"
20#include "llvm/Analysis/Loads.h"
21#include "llvm/Analysis/LoopAccessAnalysis.h"
22#include "llvm/Analysis/ScalarEvolution.h"
23#include "llvm/Analysis/ScalarEvolutionExpressions.h"
24#include "llvm/Analysis/TargetTransformInfo.h"
25#include "llvm/Analysis/ValueTracking.h"
26#include "llvm/IR/Constants.h"
27#include "llvm/IR/DataLayout.h"
28#include "llvm/IR/DerivedTypes.h"
29#include "llvm/IR/Function.h"
30#include "llvm/IR/IRBuilder.h"
31#include "llvm/IR/Instructions.h"
32#include "llvm/IR/Intrinsics.h"
33#include "llvm/Support/InstructionCost.h"
34
35#include <algorithm>
36#include <limits>
37#include <optional>
38#include <set>
39#include <tuple>
40#include <utility>
41
42using namespace llvm;
43
44namespace llvm::slpvectorizer {
45
46Value *createWidenedStridedCast(IRBuilderBase &Builder, Value *V, Type *DstTy,
47 const DataLayout &DL) {
48 bool ToPtr = cast<VectorType>(Val: DstTy)->getElementType()->isPointerTy();
49 if (ToPtr == cast<VectorType>(Val: V->getType())->getElementType()->isPointerTy())
50 return Builder.CreateBitOrPointerCast(V, DestTy: DstTy);
51 if (ToPtr)
52 return Builder.CreateIntToPtr(
53 V: Builder.CreateBitCast(V, DestTy: DL.getIntPtrType(DstTy)), DestTy: DstTy);
54 return Builder.CreateBitCast(
55 V: Builder.CreatePtrToInt(V, DestTy: DL.getIntPtrType(V->getType())), DestTy: DstTy);
56}
57
58ConstantInt *getStrideBytesIfConstant(Value *Stride, Type *ScalarTy,
59 const DataLayout &DL, bool IsReverse) {
60 auto *CI = dyn_cast_or_null<ConstantInt>(Val: Stride);
61 if (!CI)
62 return nullptr;
63
64 uint64_t ElementSize = DL.getTypeAllocSize(Ty: ScalarTy).getFixedValue();
65 APInt Bytes = CI->getValue() * ElementSize;
66 return ConstantInt::get(Context&: CI->getContext(), V: IsReverse ? -Bytes : Bytes);
67}
68
69bool arePointersCompatible(Value *Ptr1, Value *Ptr2,
70 const TargetLibraryInfo &TLI, unsigned MaxDepth,
71 bool CompareOpcodes) {
72 if (getUnderlyingObject(V: Ptr1, MaxLookup: MaxDepth) !=
73 getUnderlyingObject(V: Ptr2, MaxLookup: MaxDepth))
74 return false;
75 auto *GEP1 = dyn_cast<GetElementPtrInst>(Val: Ptr1);
76 auto *GEP2 = dyn_cast<GetElementPtrInst>(Val: Ptr2);
77 return (!GEP1 || GEP1->getNumOperands() == 2) &&
78 (!GEP2 || GEP2->getNumOperands() == 2) &&
79 (((!GEP1 || isConstant(V: GEP1->getOperand(i_nocapture: 1))) &&
80 (!GEP2 || isConstant(V: GEP2->getOperand(i_nocapture: 1)))) ||
81 !CompareOpcodes ||
82 (GEP1 && GEP2 &&
83 getSameOpcode(VL: {GEP1->getOperand(i_nocapture: 1), GEP2->getOperand(i_nocapture: 1)}, TLI)));
84}
85
86/// Calculates minimal alignment as a common alignment.
87template <typename T> Align computeCommonAlignment(ArrayRef<Value *> VL) {
88 Align CommonAlignment = cast<T>(VL.consume_front())->getAlign();
89 for (Value *V : VL)
90 CommonAlignment = std::min(CommonAlignment, cast<T>(V)->getAlign());
91 return CommonAlignment;
92}
93
94template Align computeCommonAlignment<LoadInst>(ArrayRef<Value *>);
95template Align computeCommonAlignment<StoreInst>(ArrayRef<Value *>);
96
97const SCEV *calculateRtStride(ArrayRef<Value *> PointerOps, Type *ElemTy,
98 const DataLayout &DL, ScalarEvolution &SE,
99 SmallVectorImpl<unsigned> &SortedIndices) {
100 SmallVector<const SCEV *> SCEVs;
101 const SCEV *PtrSCEVLowest = nullptr;
102 const SCEV *PtrSCEVHighest = nullptr;
103 // Find lower/upper pointers from the PointerOps (i.e. with lowest and highest
104 // addresses).
105 for (Value *Ptr : PointerOps) {
106 const SCEV *PtrSCEV = SE.getSCEV(V: Ptr);
107 if (!PtrSCEV)
108 return nullptr;
109 SCEVs.push_back(Elt: PtrSCEV);
110 if (!PtrSCEVLowest && !PtrSCEVHighest) {
111 PtrSCEVLowest = PtrSCEVHighest = PtrSCEV;
112 continue;
113 }
114 const SCEV *Diff = SE.getMinusSCEV(LHS: PtrSCEV, RHS: PtrSCEVLowest);
115 if (isa<SCEVCouldNotCompute>(Val: Diff))
116 return nullptr;
117 if (Diff->isNonConstantNegative()) {
118 PtrSCEVLowest = PtrSCEV;
119 continue;
120 }
121 const SCEV *Diff1 = SE.getMinusSCEV(LHS: PtrSCEVHighest, RHS: PtrSCEV);
122 if (isa<SCEVCouldNotCompute>(Val: Diff1))
123 return nullptr;
124 if (Diff1->isNonConstantNegative()) {
125 PtrSCEVHighest = PtrSCEV;
126 continue;
127 }
128 }
129 // Dist = PtrSCEVHighest - PtrSCEVLowest;
130 const SCEV *Dist = SE.getMinusSCEV(LHS: PtrSCEVHighest, RHS: PtrSCEVLowest);
131 if (isa<SCEVCouldNotCompute>(Val: Dist))
132 return nullptr;
133 int Size = DL.getTypeStoreSize(Ty: ElemTy);
134 auto TryGetStride = [&](const SCEV *Dist,
135 const SCEV *Multiplier) -> const SCEV * {
136 if (const auto *M = dyn_cast<SCEVMulExpr>(Val: Dist)) {
137 if (M->getOperand(i: 0) == Multiplier)
138 return M->getOperand(i: 1);
139 if (M->getOperand(i: 1) == Multiplier)
140 return M->getOperand(i: 0);
141 return nullptr;
142 }
143 if (Multiplier == Dist)
144 return SE.getConstant(Ty: Dist->getType(), V: 1);
145 return SE.getUDivExactExpr(LHS: Dist, RHS: Multiplier);
146 };
147 // Stride_in_elements = Dist / element_size * (num_elems - 1).
148 const SCEV *Stride = nullptr;
149 if (Size != 1 || SCEVs.size() > 1) {
150 const SCEV *Sz = SE.getConstant(Ty: Dist->getType(), V: Size * (SCEVs.size() - 1));
151 Stride = TryGetStride(Dist, Sz);
152 if (!Stride)
153 return nullptr;
154 }
155 if (!Stride || isa<SCEVConstant>(Val: Stride))
156 return nullptr;
157 // Iterate through all pointers and check if all distances are
158 // unique multiple of Stride.
159 using DistOrdPair = std::pair<int64_t, int>;
160 auto Compare = llvm::less_first();
161 std::set<DistOrdPair, decltype(Compare)> Offsets(Compare);
162 bool IsConsecutive = true;
163 for (const auto [Idx, PtrSCEV] : enumerate(First&: SCEVs)) {
164 unsigned Dist = 0;
165 if (PtrSCEV != PtrSCEVLowest) {
166 const SCEV *Diff = SE.getMinusSCEV(LHS: PtrSCEV, RHS: PtrSCEVLowest);
167 const SCEV *Coeff = TryGetStride(Diff, Stride);
168 if (!Coeff)
169 return nullptr;
170 const auto *SC = dyn_cast<SCEVConstant>(Val: Coeff);
171 if (!SC || isa<SCEVCouldNotCompute>(Val: SC))
172 return nullptr;
173 if (!SE.getMinusSCEV(LHS: PtrSCEV, RHS: SE.getAddExpr(LHS: PtrSCEVLowest,
174 RHS: SE.getMulExpr(LHS: Stride, RHS: SC)))
175 ->isZero())
176 return nullptr;
177 Dist = SC->getAPInt().getZExtValue();
178 }
179 // If the strides are not the same or repeated, we can't vectorize.
180 if ((Dist / Size) * Size != Dist || (Dist / Size) >= SCEVs.size())
181 return nullptr;
182 auto Res = Offsets.emplace(args&: Dist, args&: Idx);
183 if (!Res.second)
184 return nullptr;
185 // Consecutive order if the inserted element is the last one.
186 IsConsecutive = IsConsecutive && std::next(x: Res.first) == Offsets.end();
187 }
188 SortedIndices.clear();
189 if (!IsConsecutive) {
190 // Fill SortedIndices array only if it is non-consecutive.
191 SortedIndices.resize(N: PointerOps.size());
192 for (const auto [Idx, Pair] : enumerate(First&: Offsets))
193 SortedIndices[Idx] = Pair.second;
194 }
195 return Stride;
196}
197
198std::optional<int64_t>
199SLPAnalysisCache::getPointersDiff(Type *ElemTyA, Value *PtrA, Type *ElemTyB,
200 Value *PtrB, const DataLayout &DL,
201 ScalarEvolution &SE, bool StrictCheck,
202 bool CheckType) {
203 if (PtrA == PtrB)
204 return 0;
205 unsigned Flags = unsigned(StrictCheck) | (unsigned(CheckType) << 1);
206 PtrsDiffKeyT Key(ElemTyA, PtrA, ElemTyB, PtrB, Flags);
207 auto [It, Inserted] = PtrsDiffCache.try_emplace(Key);
208 if (!Inserted)
209 return It->second;
210 std::optional<int64_t> Diff = llvm::getPointersDiff(
211 ElemTyA, PtrA, ElemTyB, PtrB, DL, SE, StrictCheck, CheckType);
212 // Set before the reverse insertion below, which may rehash.
213 It->second = Diff;
214 // The distance is counted in elements of ElemTyA, so querying the pair the
215 // other way round gives the negation, provided both elements have the same
216 // size. A failed query is recorded for this order only.
217 if (Diff && *Diff != std::numeric_limits<int64_t>::min() &&
218 DL.getTypeStoreSize(Ty: ElemTyA) == DL.getTypeStoreSize(Ty: ElemTyB))
219 PtrsDiffCache.try_emplace(Key: PtrsDiffKeyT(ElemTyB, PtrB, ElemTyA, PtrA, Flags),
220 Args: -*Diff);
221 return Diff;
222}
223
224bool SLPAnalysisCache::sortPtrAccesses(
225 ArrayRef<Value *> VL, Type *ElemTy, const DataLayout &DL,
226 ScalarEvolution &SE, SmallVectorImpl<unsigned> &SortedIndices) {
227 using DistOrdPair = std::pair<int64_t, unsigned>;
228 auto Compare = less_first();
229 std::set<DistOrdPair, decltype(Compare)> Offsets(Compare);
230 Offsets.emplace(args: 0, args: 0);
231 bool IsConsecutive = true;
232 for (auto [Idx, Ptr] : drop_begin(RangeOrContainer: enumerate(First&: VL))) {
233 std::optional<int64_t> Diff =
234 getPointersDiff(ElemTyA: ElemTy, PtrA: VL.front(), ElemTyB: ElemTy, PtrB: Ptr, DL, SE,
235 /*StrictCheck=*/true);
236 if (!Diff)
237 return false;
238 auto [It, IsInserted] = Offsets.emplace(args&: *Diff, args&: Idx);
239 if (!IsInserted)
240 return false;
241 IsConsecutive &= std::next(x: It) == Offsets.end();
242 }
243 SortedIndices.clear();
244 if (!IsConsecutive) {
245 SortedIndices.resize(N: VL.size());
246 for (auto [Idx, Off] : enumerate(First&: Offsets))
247 SortedIndices[Idx] = Off.second;
248 }
249 return true;
250}
251
252bool SLPAnalysisCache::isGuaranteedNotToBePoison(const Value *V,
253 AssumptionCache *AC) {
254 auto [It, Inserted] = NotPoisonCache.try_emplace(Key: V, Args: false);
255 if (Inserted)
256 It->second = llvm::isGuaranteedNotToBePoison(V, AC);
257 return It->second;
258}
259
260/// Builds compress-like mask for shuffles for the given \p PointerOps, ordered
261/// with \p Order.
262/// \return true if the mask represents strided access, false - otherwise.
263static bool buildCompressMask(ArrayRef<Value *> PointerOps,
264 ArrayRef<unsigned> Order, Type *ScalarTy,
265 const DataLayout &DL, ScalarEvolution &SE,
266 SmallVectorImpl<int> &CompressMask,
267 SLPAnalysisCache &Cache) {
268 const unsigned Sz = PointerOps.size();
269 CompressMask.assign(NumElts: Sz, Elt: PoisonMaskElem);
270 // The first element always set.
271 CompressMask[0] = 0;
272 // Check if the mask represents strided access.
273 std::optional<unsigned> Stride = 0;
274 Value *Ptr0 = Order.empty() ? PointerOps.front() : PointerOps[Order.front()];
275 for (unsigned I : seq<unsigned>(Begin: 1, End: Sz)) {
276 Value *Ptr = Order.empty() ? PointerOps[I] : PointerOps[Order[I]];
277 std::optional<int64_t> OptPos =
278 Cache.getPointersDiff(ElemTyA: ScalarTy, PtrA: Ptr0, ElemTyB: ScalarTy, PtrB: Ptr, DL, SE);
279 if (!OptPos || OptPos > std::numeric_limits<unsigned>::max())
280 return false;
281 unsigned Pos = static_cast<unsigned>(*OptPos);
282 CompressMask[I] = Pos;
283 if (!Stride)
284 continue;
285 if (*Stride == 0) {
286 *Stride = Pos;
287 continue;
288 }
289 if (Pos != *Stride * I)
290 Stride.reset();
291 }
292 return Stride.has_value();
293}
294
295/// Checks if the \p VL can be transformed to a (masked)load + compress or
296/// (masked) interleaved load.
297bool isMaskedLoadCompress(
298 ArrayRef<Value *> VL, ArrayRef<Value *> PointerOps,
299 ArrayRef<unsigned> Order, const TargetTransformInfo &TTI,
300 const DataLayout &DL, ScalarEvolution &SE, AssumptionCache &AC,
301 const DominatorTree &DT, const TargetLibraryInfo &TLI,
302 const TargetTransformInfo::TargetCostKind CostKind,
303 const function_ref<bool(Value *)> AreAllUsersVectorized, bool ReVec,
304 bool &IsMasked, unsigned &InterleaveFactor,
305 SmallVectorImpl<int> &CompressMask, VectorType *&LoadVecTy,
306 SLPAnalysisCache &Cache) {
307 InterleaveFactor = 0;
308 Type *ScalarTy = VL.front()->getType();
309 const size_t Sz = VL.size();
310 auto *VecTy = cast<VectorType>(Val: getWidenedType(ScalarTy, VF: Sz));
311 SmallVector<int> Mask;
312 if (!Order.empty())
313 inversePermutation(Indices: Order, Mask);
314 // Check external uses.
315 for (const auto [I, V] : enumerate(First&: VL)) {
316 if (AreAllUsersVectorized(V))
317 continue;
318 InstructionCost ExtractCost =
319 TTI.getVectorInstrCost(Opcode: Instruction::ExtractElement, Val: VecTy, CostKind,
320 Index: Mask.empty() ? I : Mask[I]);
321 InstructionCost ScalarCost =
322 TTI.getInstructionCost(U: cast<Instruction>(Val: V), CostKind);
323 if (ExtractCost <= ScalarCost)
324 return false;
325 }
326 Value *Ptr0;
327 Value *PtrN;
328 if (Order.empty()) {
329 Ptr0 = PointerOps.front();
330 PtrN = PointerOps.back();
331 } else {
332 Ptr0 = PointerOps[Order.front()];
333 PtrN = PointerOps[Order.back()];
334 }
335 std::optional<int64_t> Diff =
336 Cache.getPointersDiff(ElemTyA: ScalarTy, PtrA: Ptr0, ElemTyB: ScalarTy, PtrB: PtrN, DL, SE);
337 if (!Diff)
338 return false;
339 const size_t MaxRegSize =
340 TTI.getRegisterBitWidth(K: TargetTransformInfo::RGK_FixedWidthVector)
341 .getFixedValue();
342 // Check for very large distances between elements.
343 if (*Diff / Sz >= MaxRegSize / 8)
344 return false;
345 LoadVecTy = cast<FixedVectorType>(Val: getWidenedType(ScalarTy, VF: *Diff + 1));
346 auto *LI = cast<LoadInst>(Val: Order.empty() ? VL.front() : VL[Order.front()]);
347 Align CommonAlignment = LI->getAlign();
348 SimplifyQuery SQ(
349 DL, &TLI, &DT, &AC,
350 cast<LoadInst>(Val: Order.empty() ? VL.back() : VL[Order.back()]));
351 IsMasked = !isSafeToLoadUnconditionally(V: Ptr0, Ty: LoadVecTy, Alignment: CommonAlignment, SQ);
352 if (IsMasked && !TTI.isLegalMaskedLoad(DataType: LoadVecTy, Alignment: CommonAlignment,
353 AddressSpace: LI->getPointerAddressSpace()))
354 return false;
355 // TODO: perform the analysis of each scalar load for better
356 // safe-load-unconditionally analysis.
357 bool IsStrided = buildCompressMask(PointerOps, Order, ScalarTy, DL, SE,
358 CompressMask, Cache);
359 assert(CompressMask.size() >= 2 && "At least two elements are required");
360 SmallVector<Value *> OrderedPointerOps(PointerOps);
361 if (!Order.empty())
362 reorderScalars(Scalars&: OrderedPointerOps, Mask);
363 auto [ScalarGEPCost, VectorGEPCost] =
364 getGEPCosts(TTI, Ptrs: OrderedPointerOps, BasePtr: OrderedPointerOps.front(),
365 Opcode: Instruction::Load, CostKind, ScalarTy, VecTy: LoadVecTy);
366 // The cost of scalar loads.
367 InstructionCost ScalarLoadsCost =
368 accumulate(Range&: VL, Init: InstructionCost(),
369 Op: [&](InstructionCost C, Value *V) {
370 return C + TTI.getInstructionCost(U: cast<Instruction>(Val: V),
371 CostKind);
372 }) +
373 ScalarGEPCost;
374 APInt DemandedElts = APInt::getAllOnes(numBits: Sz);
375 InstructionCost GatherCost =
376 getScalarizationOverhead(TTI, ReVec, ScalarTy, Ty: VecTy, DemandedElts,
377 /*Insert=*/true,
378 /*Extract=*/false, CostKind) +
379 ScalarLoadsCost;
380 InstructionCost LoadCost = 0;
381 if (IsMasked) {
382 LoadCost = TTI.getMemIntrinsicInstrCost(
383 MICA: MemIntrinsicCostAttributes(Intrinsic::masked_load, LoadVecTy,
384 CommonAlignment,
385 LI->getPointerAddressSpace()),
386 CostKind);
387 } else {
388 LoadCost =
389 TTI.getMemoryOpCost(Opcode: Instruction::Load, Src: LoadVecTy, Alignment: CommonAlignment,
390 AddressSpace: LI->getPointerAddressSpace(), CostKind,
391 OpdInfo: TTI::getOperandInfo(V: LI->getPointerOperand()));
392 }
393 if (IsStrided && !IsMasked && Order.empty()) {
394 // Check for potential segmented(interleaved) loads.
395 VectorType *AlignedLoadVecTy = cast<VectorType>(Val: getWidenedType(
396 ScalarTy,
397 VF: getFullVectorNumberOfElements(TTI, Ty: ScalarTy, Sz: *Diff + 1, ReVec)));
398 SimplifyQuery SQ(DL, &TLI, &DT, &AC, cast<LoadInst>(Val: VL.back()));
399 if (!isSafeToLoadUnconditionally(V: Ptr0, Ty: AlignedLoadVecTy, Alignment: CommonAlignment,
400 SQ))
401 AlignedLoadVecTy = LoadVecTy;
402 if (TTI.isLegalInterleavedAccessType(VTy: AlignedLoadVecTy, Factor: CompressMask[1],
403 Alignment: CommonAlignment,
404 AddrSpace: LI->getPointerAddressSpace())) {
405 InstructionCost InterleavedCost =
406 VectorGEPCost + TTI.getInterleavedMemoryOpCost(
407 Opcode: Instruction::Load, VecTy: AlignedLoadVecTy,
408 Factor: CompressMask[1], Indices: {}, Alignment: CommonAlignment,
409 AddressSpace: LI->getPointerAddressSpace(), CostKind, UseMaskForCond: IsMasked);
410 if (InterleavedCost < GatherCost) {
411 InterleaveFactor = CompressMask[1];
412 LoadVecTy = AlignedLoadVecTy;
413 return true;
414 }
415 }
416 }
417 // Estimating the compression shuffle cost below can be extremely expensive
418 // for a very wide LoadVecTy, which is split into a large number of vector
419 // registers (see processShuffleMasks). The shuffle cost is always
420 // non-negative, so if the load cost alone already reaches the gather cost the
421 // masked-load-compress cannot be profitable. Bail out before the costly
422 // shuffle cost estimation in that case.
423 if (VectorGEPCost + LoadCost >= GatherCost)
424 return false;
425 // For REVEC the scalars are vectors, and the emitted shuffle uses the
426 // compress mask expanded to the individual elements. Cost that mask.
427 SmallVector<int> CostMask(CompressMask.begin(), CompressMask.end());
428 transformScalarShuffleIndiciesToVector(VecTyNumElements: getNumElements(Ty: ScalarTy), Mask&: CostMask);
429 InstructionCost CompressCost = getShuffleCost(TTI, Kind: TTI::SK_PermuteSingleSrc,
430 Tp: LoadVecTy, CostKind, Mask: CostMask);
431 if (!Order.empty()) {
432 SmallVector<int> NewMask(Sz, PoisonMaskElem);
433 for (unsigned I : seq<unsigned>(Size: Sz)) {
434 NewMask[I] = CompressMask[Mask[I]];
435 }
436 CompressMask.swap(RHS&: NewMask);
437 }
438 InstructionCost TotalVecCost = VectorGEPCost + LoadCost + CompressCost;
439 return TotalVecCost < GatherCost;
440}
441
442/// Checks if the \p VL can be transformed to a (masked)load + compress or
443/// (masked) interleaved load.
444bool isMaskedLoadCompress(
445 ArrayRef<Value *> VL, ArrayRef<Value *> PointerOps,
446 ArrayRef<unsigned> Order, const TargetTransformInfo &TTI,
447 const DataLayout &DL, ScalarEvolution &SE, AssumptionCache &AC,
448 const DominatorTree &DT, const TargetLibraryInfo &TLI,
449 const TargetTransformInfo::TargetCostKind CostKind,
450 const function_ref<bool(Value *)> AreAllUsersVectorized, bool ReVec,
451 SLPAnalysisCache &Cache) {
452 bool IsMasked;
453 unsigned InterleaveFactor;
454 SmallVector<int> CompressMask;
455 VectorType *LoadVecTy;
456 return isMaskedLoadCompress(VL, PointerOps, Order, TTI, DL, SE, AC, DT, TLI,
457 CostKind, AreAllUsersVectorized, ReVec, IsMasked,
458 InterleaveFactor, CompressMask, LoadVecTy, Cache);
459}
460
461bool canWidenLoadsOverUndefLanes(ArrayRef<Value *> VL, const DataLayout &DL,
462 ScalarEvolution &SE, AssumptionCache &AC,
463 const DominatorTree &DT,
464 const TargetLibraryInfo &TLI) {
465 if (count_if(Range&: VL, P: IsaPred<LoadInst>) < 2)
466 return false;
467 const auto *FirstIt = find_if(Range&: VL, P: IsaPred<LoadInst>);
468 const unsigned FirstLane = std::distance(first: VL.begin(), last: FirstIt);
469 auto *FirstLI = cast<LoadInst>(Val: *FirstIt);
470 // The wide load may read the memory with a different tag.
471 if (FirstLI->getFunction()->hasFnAttribute(Kind: Attribute::SanitizeMemTag))
472 return false;
473 Type *ScalarTy = FirstLI->getType();
474 Value *Ptr0 = FirstLI->getPointerOperand();
475 LoadInst *LastLI = FirstLI;
476 for (auto [Lane, V] : enumerate(First&: VL)) {
477 if (isa<UndefValue>(Val: V))
478 continue;
479 auto *LI = dyn_cast<LoadInst>(Val: V);
480 if (!LI || !LI->isSimple() || mustSuppressSpeculation(LI: *LI))
481 return false;
482 std::optional<int64_t> Dist =
483 getPointersDiff(ElemTyA: ScalarTy, PtrA: Ptr0, ElemTyB: ScalarTy, PtrB: LI->getPointerOperand(), DL,
484 SE, /*StrictCheck=*/true);
485 if (!Dist || *Dist != static_cast<int64_t>(Lane) - FirstLane)
486 return false;
487 if (LastLI->comesBefore(Other: LI))
488 LastLI = LI;
489 }
490 // The wide load starts before the first load, so check the range as the one
491 // starting at the underlying object.
492 const uint64_t EltSize = DL.getTypeAllocSize(Ty: ScalarTy).getFixedValue();
493 const unsigned BitWidth = DL.getIndexTypeSizeInBits(Ty: Ptr0->getType());
494 APInt Offset(BitWidth, 0);
495 const Value *Base = Ptr0->stripAndAccumulateConstantOffsets(
496 DL, Offset, /*AllowNonInbounds=*/true);
497 bool Overflow = false;
498 APInt Start = Offset.ssub_ov(RHS: APInt(BitWidth, FirstLane * EltSize), Overflow);
499 if (Overflow || Start.isNegative())
500 return false;
501 APInt End = Start.sadd_ov(RHS: APInt(BitWidth, VL.size() * EltSize), Overflow);
502 return !Overflow &&
503 isDereferenceableAndAlignedPointer(
504 V: Base, Alignment: Align(1), Size: End, Q: SimplifyQuery(DL, &TLI, &DT, &AC, LastLI));
505}
506
507uint64_t getVectorLoadShift(ArrayRef<Value *> Scalars) {
508 const auto *It = find_if(Range&: Scalars, P: IsaPred<LoadInst>);
509 auto *LI = cast<LoadInst>(Val: *It);
510 return std::distance(first: Scalars.begin(), last: It) *
511 LI->getDataLayout().getTypeAllocSize(Ty: LI->getType()).getFixedValue();
512}
513
514/// Checks if the stores \p VL with pointers \p PointerOps can be lowered as a
515/// single masked store. On success \p StoreVecTy is the widened store type and
516/// \p ReuseShuffleIndices is the expand mask that places each stored value at
517/// its element offset from the base (poison in the gaps).
518bool isMaskedStoreCompress(ArrayRef<Value *> VL, ArrayRef<Value *> PointerOps,
519 ArrayRef<unsigned> Order,
520 const TargetTransformInfo &TTI, const DataLayout &DL,
521 ScalarEvolution &SE, Align CommonAlignment,
522 SmallVectorImpl<int> &ReuseShuffleIndices,
523 FixedVectorType *&StoreVecTy,
524 SLPAnalysisCache &Cache) {
525 Type *ScalarTy = cast<StoreInst>(Val: VL.front())->getValueOperand()->getType();
526 const size_t Sz = VL.size();
527 // Only simple scalar element types are supported.
528 if (Sz < 2 || (!ScalarTy->isIntOrPtrTy() && !ScalarTy->isFloatingPointTy()))
529 return false;
530 Value *Ptr0 = Order.empty() ? PointerOps.front() : PointerOps[Order.front()];
531 Value *PtrN = Order.empty() ? PointerOps.back() : PointerOps[Order.back()];
532 std::optional<int64_t> Diff =
533 Cache.getPointersDiff(ElemTyA: ScalarTy, PtrA: Ptr0, ElemTyB: ScalarTy, PtrB: PtrN, DL, SE);
534 if (!Diff || *Diff <= 0)
535 return false;
536 // Avoid widened vectors with very large gaps between the stored elements.
537 const unsigned MaxRegSize =
538 TTI.getRegisterBitWidth(K: TargetTransformInfo::RGK_FixedWidthVector)
539 .getFixedValue();
540 const unsigned ScalarBits = DL.getTypeSizeInBits(Ty: ScalarTy).getFixedValue();
541 if (ScalarBits == 0 ||
542 static_cast<uint64_t>(*Diff) / Sz >= MaxRegSize / ScalarBits)
543 return false;
544 StoreVecTy = cast<FixedVectorType>(Val: getWidenedType(ScalarTy, VF: *Diff + 1));
545 unsigned AS = cast<StoreInst>(Val: VL.front())->getPointerAddressSpace();
546 if (!TTI.isLegalMaskedStore(DataType: StoreVecTy, Alignment: CommonAlignment, AddressSpace: AS,
547 MaskKind: TTI::ConstantMask))
548 return false;
549 // Build the expand mask: store I (in address-sorted order) is placed at its
550 // element offset from the base, other widened lanes are poison.
551 ReuseShuffleIndices.assign(NumElts: *Diff + 1, Elt: PoisonMaskElem);
552 int64_t Prev = -1;
553 for (unsigned I : seq<unsigned>(Size: Sz)) {
554 Value *Ptr = Order.empty() ? PointerOps[I] : PointerOps[Order[I]];
555 std::optional<int64_t> Off =
556 Cache.getPointersDiff(ElemTyA: ScalarTy, PtrA: Ptr0, ElemTyB: ScalarTy, PtrB: Ptr, DL, SE);
557 if (!Off || *Off <= Prev || *Off > *Diff)
558 return false;
559 ReuseShuffleIndices[*Off] = static_cast<int>(I);
560 Prev = *Off;
561 }
562 return true;
563}
564
565bool clusterSortPtrAccesses(ArrayRef<Value *> VL, ArrayRef<BasicBlock *> BBs,
566 Type *ElemTy, const DataLayout &DL,
567 ScalarEvolution &SE, unsigned MaxDepth,
568 SmallVectorImpl<unsigned> &SortedIndices,
569 SLPAnalysisCache &Cache) {
570 assert(
571 all_of(VL, [](const Value *V) { return V->getType()->isPointerTy(); }) &&
572 "Expected list of pointer operands.");
573 // Map from bases to a vector of (Ptr, Offset, OrigIdx), which we insert each
574 // Ptr into, sort and return the sorted indices with values next to one
575 // another.
576 SmallMapVector<
577 std::pair<BasicBlock *, Value *>,
578 SmallVector<SmallVector<std::tuple<Value *, int64_t, unsigned>>>, 8>
579 Bases;
580 Bases
581 .try_emplace(Key: std::make_pair(x: BBs.front(),
582 y: getUnderlyingObject(V: VL.front(), MaxLookup: MaxDepth)))
583 .first->second.emplace_back()
584 .emplace_back(Args: VL.front(), Args: 0U, Args: 0U);
585
586 SortedIndices.clear();
587 for (auto [Cnt, Ptr] : enumerate(First: VL.drop_front())) {
588 auto Key = std::make_pair(x: BBs[Cnt + 1], y: getUnderlyingObject(V: Ptr, MaxLookup: MaxDepth));
589 bool Found = any_of(Range&: Bases.try_emplace(Key).first->second,
590 P: [&, &Cnt = Cnt, &Ptr = Ptr](auto &Base) {
591 std::optional<int64_t> Diff = Cache.getPointersDiff(
592 ElemTyA: ElemTy, PtrA: std::get<0>(Base.front()), ElemTyB: ElemTy, PtrB: Ptr,
593 DL, SE, /*StrictCheck=*/true);
594 if (!Diff)
595 return false;
596
597 Base.emplace_back(Ptr, *Diff, Cnt + 1);
598 return true;
599 });
600
601 if (!Found) {
602 // If we haven't found enough to usefully cluster, return early.
603 if (Bases.size() > VL.size() / 2 - 1)
604 return false;
605
606 // Not found already - add a new Base
607 Bases.find(Key)->second.emplace_back().emplace_back(Args: Ptr, Args: 0, Args: Cnt + 1);
608 }
609 }
610
611 if (Bases.size() == VL.size())
612 return false;
613
614 if (Bases.size() == 1 && (Bases.front().second.size() == 1 ||
615 Bases.front().second.size() == VL.size()))
616 return false;
617
618 // For each of the bases sort the pointers by Offset and check if any of the
619 // base become consecutively allocated.
620 auto ComparePointers = [MaxDepth](Value *Ptr1, Value *Ptr2) {
621 SmallPtrSet<Value *, 13> FirstPointers;
622 SmallPtrSet<Value *, 13> SecondPointers;
623 Value *P1 = Ptr1;
624 Value *P2 = Ptr2;
625 unsigned Depth = 0;
626 while (!FirstPointers.contains(Ptr: P2) && !SecondPointers.contains(Ptr: P1)) {
627 if (P1 == P2 || Depth > MaxDepth)
628 return false;
629 FirstPointers.insert(Ptr: P1);
630 SecondPointers.insert(Ptr: P2);
631 P1 = getUnderlyingObject(V: P1, /*MaxLookup=*/1);
632 P2 = getUnderlyingObject(V: P2, /*MaxLookup=*/1);
633 ++Depth;
634 }
635 assert((FirstPointers.contains(P2) || SecondPointers.contains(P1)) &&
636 "Unable to find matching root.");
637 return FirstPointers.contains(Ptr: P2) && !SecondPointers.contains(Ptr: P1);
638 };
639 for (auto &Base : Bases) {
640 for (auto &Vec : Base.second) {
641 if (Vec.size() > 1) {
642 stable_sort(Range&: Vec, C: llvm::less_second());
643 int64_t InitialOffset = std::get<1>(t&: Vec[0]);
644 bool AnyConsecutive =
645 all_of(Range: enumerate(First&: Vec), P: [InitialOffset](const auto &P) {
646 return std::get<1>(P.value()) ==
647 int64_t(P.index()) + InitialOffset;
648 });
649 // Fill SortedIndices array only if it looks worth-while to sort the
650 // ptrs.
651 if (!AnyConsecutive)
652 return false;
653 }
654 }
655 stable_sort(Range&: Base.second, C: [&](const auto &V1, const auto &V2) {
656 return ComparePointers(std::get<0>(V1.front()), std::get<0>(V2.front()));
657 });
658 }
659
660 for (auto &T : Bases)
661 for (const auto &Vec : T.second)
662 for (const auto &P : Vec)
663 SortedIndices.push_back(Elt: std::get<2>(t: P));
664
665 assert(SortedIndices.size() == VL.size() &&
666 "Expected SortedIndices to be the size of VL");
667 return true;
668}
669
670} // namespace llvm::slpvectorizer
671