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::isGuaranteedNotToBePoison(const Value *V,
225 AssumptionCache *AC) {
226 auto [It, Inserted] = NotPoisonCache.try_emplace(Key: V, Args: false);
227 if (Inserted)
228 It->second = llvm::isGuaranteedNotToBePoison(V, AC);
229 return It->second;
230}
231
232/// Builds compress-like mask for shuffles for the given \p PointerOps, ordered
233/// with \p Order.
234/// \return true if the mask represents strided access, false - otherwise.
235static bool buildCompressMask(ArrayRef<Value *> PointerOps,
236 ArrayRef<unsigned> Order, Type *ScalarTy,
237 const DataLayout &DL, ScalarEvolution &SE,
238 SmallVectorImpl<int> &CompressMask,
239 SLPAnalysisCache &Cache) {
240 const unsigned Sz = PointerOps.size();
241 CompressMask.assign(NumElts: Sz, Elt: PoisonMaskElem);
242 // The first element always set.
243 CompressMask[0] = 0;
244 // Check if the mask represents strided access.
245 std::optional<unsigned> Stride = 0;
246 Value *Ptr0 = Order.empty() ? PointerOps.front() : PointerOps[Order.front()];
247 for (unsigned I : seq<unsigned>(Begin: 1, End: Sz)) {
248 Value *Ptr = Order.empty() ? PointerOps[I] : PointerOps[Order[I]];
249 std::optional<int64_t> OptPos =
250 Cache.getPointersDiff(ElemTyA: ScalarTy, PtrA: Ptr0, ElemTyB: ScalarTy, PtrB: Ptr, DL, SE);
251 if (!OptPos || OptPos > std::numeric_limits<unsigned>::max())
252 return false;
253 unsigned Pos = static_cast<unsigned>(*OptPos);
254 CompressMask[I] = Pos;
255 if (!Stride)
256 continue;
257 if (*Stride == 0) {
258 *Stride = Pos;
259 continue;
260 }
261 if (Pos != *Stride * I)
262 Stride.reset();
263 }
264 return Stride.has_value();
265}
266
267/// Checks if the \p VL can be transformed to a (masked)load + compress or
268/// (masked) interleaved load.
269bool isMaskedLoadCompress(
270 ArrayRef<Value *> VL, ArrayRef<Value *> PointerOps,
271 ArrayRef<unsigned> Order, const TargetTransformInfo &TTI,
272 const DataLayout &DL, ScalarEvolution &SE, AssumptionCache &AC,
273 const DominatorTree &DT, const TargetLibraryInfo &TLI,
274 const TargetTransformInfo::TargetCostKind CostKind,
275 const function_ref<bool(Value *)> AreAllUsersVectorized, bool ReVec,
276 bool &IsMasked, unsigned &InterleaveFactor,
277 SmallVectorImpl<int> &CompressMask, VectorType *&LoadVecTy,
278 SLPAnalysisCache &Cache) {
279 InterleaveFactor = 0;
280 Type *ScalarTy = VL.front()->getType();
281 const size_t Sz = VL.size();
282 auto *VecTy = cast<VectorType>(Val: getWidenedType(ScalarTy, VF: Sz));
283 SmallVector<int> Mask;
284 if (!Order.empty())
285 inversePermutation(Indices: Order, Mask);
286 // Check external uses.
287 for (const auto [I, V] : enumerate(First&: VL)) {
288 if (AreAllUsersVectorized(V))
289 continue;
290 InstructionCost ExtractCost =
291 TTI.getVectorInstrCost(Opcode: Instruction::ExtractElement, Val: VecTy, CostKind,
292 Index: Mask.empty() ? I : Mask[I]);
293 InstructionCost ScalarCost =
294 TTI.getInstructionCost(U: cast<Instruction>(Val: V), CostKind);
295 if (ExtractCost <= ScalarCost)
296 return false;
297 }
298 Value *Ptr0;
299 Value *PtrN;
300 if (Order.empty()) {
301 Ptr0 = PointerOps.front();
302 PtrN = PointerOps.back();
303 } else {
304 Ptr0 = PointerOps[Order.front()];
305 PtrN = PointerOps[Order.back()];
306 }
307 std::optional<int64_t> Diff =
308 Cache.getPointersDiff(ElemTyA: ScalarTy, PtrA: Ptr0, ElemTyB: ScalarTy, PtrB: PtrN, DL, SE);
309 if (!Diff)
310 return false;
311 const size_t MaxRegSize =
312 TTI.getRegisterBitWidth(K: TargetTransformInfo::RGK_FixedWidthVector)
313 .getFixedValue();
314 // Check for very large distances between elements.
315 if (*Diff / Sz >= MaxRegSize / 8)
316 return false;
317 LoadVecTy = cast<FixedVectorType>(Val: getWidenedType(ScalarTy, VF: *Diff + 1));
318 auto *LI = cast<LoadInst>(Val: Order.empty() ? VL.front() : VL[Order.front()]);
319 Align CommonAlignment = LI->getAlign();
320 SimplifyQuery SQ(
321 DL, &TLI, &DT, &AC,
322 cast<LoadInst>(Val: Order.empty() ? VL.back() : VL[Order.back()]));
323 IsMasked = !isSafeToLoadUnconditionally(V: Ptr0, Ty: LoadVecTy, Alignment: CommonAlignment, SQ);
324 if (IsMasked && !TTI.isLegalMaskedLoad(DataType: LoadVecTy, Alignment: CommonAlignment,
325 AddressSpace: LI->getPointerAddressSpace()))
326 return false;
327 // TODO: perform the analysis of each scalar load for better
328 // safe-load-unconditionally analysis.
329 bool IsStrided = buildCompressMask(PointerOps, Order, ScalarTy, DL, SE,
330 CompressMask, Cache);
331 assert(CompressMask.size() >= 2 && "At least two elements are required");
332 SmallVector<Value *> OrderedPointerOps(PointerOps);
333 if (!Order.empty())
334 reorderScalars(Scalars&: OrderedPointerOps, Mask);
335 auto [ScalarGEPCost, VectorGEPCost] =
336 getGEPCosts(TTI, Ptrs: OrderedPointerOps, BasePtr: OrderedPointerOps.front(),
337 Opcode: Instruction::Load, CostKind, ScalarTy, VecTy: LoadVecTy);
338 // The cost of scalar loads.
339 InstructionCost ScalarLoadsCost =
340 accumulate(Range&: VL, Init: InstructionCost(),
341 Op: [&](InstructionCost C, Value *V) {
342 return C + TTI.getInstructionCost(U: cast<Instruction>(Val: V),
343 CostKind);
344 }) +
345 ScalarGEPCost;
346 APInt DemandedElts = APInt::getAllOnes(numBits: Sz);
347 InstructionCost GatherCost =
348 getScalarizationOverhead(TTI, ReVec, ScalarTy, Ty: VecTy, DemandedElts,
349 /*Insert=*/true,
350 /*Extract=*/false, CostKind) +
351 ScalarLoadsCost;
352 InstructionCost LoadCost = 0;
353 if (IsMasked) {
354 LoadCost = TTI.getMemIntrinsicInstrCost(
355 MICA: MemIntrinsicCostAttributes(Intrinsic::masked_load, LoadVecTy,
356 CommonAlignment,
357 LI->getPointerAddressSpace()),
358 CostKind);
359 } else {
360 LoadCost =
361 TTI.getMemoryOpCost(Opcode: Instruction::Load, Src: LoadVecTy, Alignment: CommonAlignment,
362 AddressSpace: LI->getPointerAddressSpace(), CostKind,
363 OpdInfo: TTI::getOperandInfo(V: LI->getPointerOperand()));
364 }
365 if (IsStrided && !IsMasked && Order.empty()) {
366 // Check for potential segmented(interleaved) loads.
367 VectorType *AlignedLoadVecTy = cast<VectorType>(Val: getWidenedType(
368 ScalarTy,
369 VF: getFullVectorNumberOfElements(TTI, Ty: ScalarTy, Sz: *Diff + 1, ReVec)));
370 SimplifyQuery SQ(DL, &TLI, &DT, &AC, cast<LoadInst>(Val: VL.back()));
371 if (!isSafeToLoadUnconditionally(V: Ptr0, Ty: AlignedLoadVecTy, Alignment: CommonAlignment,
372 SQ))
373 AlignedLoadVecTy = LoadVecTy;
374 if (TTI.isLegalInterleavedAccessType(VTy: AlignedLoadVecTy, Factor: CompressMask[1],
375 Alignment: CommonAlignment,
376 AddrSpace: LI->getPointerAddressSpace())) {
377 InstructionCost InterleavedCost =
378 VectorGEPCost + TTI.getInterleavedMemoryOpCost(
379 Opcode: Instruction::Load, VecTy: AlignedLoadVecTy,
380 Factor: CompressMask[1], Indices: {}, Alignment: CommonAlignment,
381 AddressSpace: LI->getPointerAddressSpace(), CostKind, UseMaskForCond: IsMasked);
382 if (InterleavedCost < GatherCost) {
383 InterleaveFactor = CompressMask[1];
384 LoadVecTy = AlignedLoadVecTy;
385 return true;
386 }
387 }
388 }
389 // Estimating the compression shuffle cost below can be extremely expensive
390 // for a very wide LoadVecTy, which is split into a large number of vector
391 // registers (see processShuffleMasks). The shuffle cost is always
392 // non-negative, so if the load cost alone already reaches the gather cost the
393 // masked-load-compress cannot be profitable. Bail out before the costly
394 // shuffle cost estimation in that case.
395 if (VectorGEPCost + LoadCost >= GatherCost)
396 return false;
397 // For REVEC the scalars are vectors, and the emitted shuffle uses the
398 // compress mask expanded to the individual elements. Cost that mask.
399 SmallVector<int> CostMask(CompressMask.begin(), CompressMask.end());
400 transformScalarShuffleIndiciesToVector(VecTyNumElements: getNumElements(Ty: ScalarTy), Mask&: CostMask);
401 InstructionCost CompressCost = getShuffleCost(TTI, Kind: TTI::SK_PermuteSingleSrc,
402 Tp: LoadVecTy, CostKind, Mask: CostMask);
403 if (!Order.empty()) {
404 SmallVector<int> NewMask(Sz, PoisonMaskElem);
405 for (unsigned I : seq<unsigned>(Size: Sz)) {
406 NewMask[I] = CompressMask[Mask[I]];
407 }
408 CompressMask.swap(RHS&: NewMask);
409 }
410 InstructionCost TotalVecCost = VectorGEPCost + LoadCost + CompressCost;
411 return TotalVecCost < GatherCost;
412}
413
414/// Checks if the \p VL can be transformed to a (masked)load + compress or
415/// (masked) interleaved load.
416bool isMaskedLoadCompress(
417 ArrayRef<Value *> VL, ArrayRef<Value *> PointerOps,
418 ArrayRef<unsigned> Order, const TargetTransformInfo &TTI,
419 const DataLayout &DL, ScalarEvolution &SE, AssumptionCache &AC,
420 const DominatorTree &DT, const TargetLibraryInfo &TLI,
421 const TargetTransformInfo::TargetCostKind CostKind,
422 const function_ref<bool(Value *)> AreAllUsersVectorized, bool ReVec,
423 SLPAnalysisCache &Cache) {
424 bool IsMasked;
425 unsigned InterleaveFactor;
426 SmallVector<int> CompressMask;
427 VectorType *LoadVecTy;
428 return isMaskedLoadCompress(VL, PointerOps, Order, TTI, DL, SE, AC, DT, TLI,
429 CostKind, AreAllUsersVectorized, ReVec, IsMasked,
430 InterleaveFactor, CompressMask, LoadVecTy, Cache);
431}
432
433bool canWidenLoadsOverUndefLanes(ArrayRef<Value *> VL, const DataLayout &DL,
434 ScalarEvolution &SE, AssumptionCache &AC,
435 const DominatorTree &DT,
436 const TargetLibraryInfo &TLI) {
437 if (count_if(Range&: VL, P: IsaPred<LoadInst>) < 2)
438 return false;
439 const auto *FirstIt = find_if(Range&: VL, P: IsaPred<LoadInst>);
440 const unsigned FirstLane = std::distance(first: VL.begin(), last: FirstIt);
441 auto *FirstLI = cast<LoadInst>(Val: *FirstIt);
442 // The wide load may read the memory with a different tag.
443 if (FirstLI->getFunction()->hasFnAttribute(Kind: Attribute::SanitizeMemTag))
444 return false;
445 Type *ScalarTy = FirstLI->getType();
446 Value *Ptr0 = FirstLI->getPointerOperand();
447 LoadInst *LastLI = FirstLI;
448 for (auto [Lane, V] : enumerate(First&: VL)) {
449 if (isa<UndefValue>(Val: V))
450 continue;
451 auto *LI = dyn_cast<LoadInst>(Val: V);
452 if (!LI || !LI->isSimple() || mustSuppressSpeculation(LI: *LI))
453 return false;
454 std::optional<int64_t> Dist =
455 getPointersDiff(ElemTyA: ScalarTy, PtrA: Ptr0, ElemTyB: ScalarTy, PtrB: LI->getPointerOperand(), DL,
456 SE, /*StrictCheck=*/true);
457 if (!Dist || *Dist != static_cast<int64_t>(Lane) - FirstLane)
458 return false;
459 if (LastLI->comesBefore(Other: LI))
460 LastLI = LI;
461 }
462 // The wide load starts before the first load, so check the range as the one
463 // starting at the underlying object.
464 const uint64_t EltSize = DL.getTypeAllocSize(Ty: ScalarTy).getFixedValue();
465 const unsigned BitWidth = DL.getIndexTypeSizeInBits(Ty: Ptr0->getType());
466 APInt Offset(BitWidth, 0);
467 const Value *Base = Ptr0->stripAndAccumulateConstantOffsets(
468 DL, Offset, /*AllowNonInbounds=*/true);
469 bool Overflow = false;
470 APInt Start = Offset.ssub_ov(RHS: APInt(BitWidth, FirstLane * EltSize), Overflow);
471 if (Overflow || Start.isNegative())
472 return false;
473 APInt End = Start.sadd_ov(RHS: APInt(BitWidth, VL.size() * EltSize), Overflow);
474 return !Overflow &&
475 isDereferenceableAndAlignedPointer(
476 V: Base, Alignment: Align(1), Size: End, Q: SimplifyQuery(DL, &TLI, &DT, &AC, LastLI));
477}
478
479uint64_t getVectorLoadShift(ArrayRef<Value *> Scalars) {
480 const auto *It = find_if(Range&: Scalars, P: IsaPred<LoadInst>);
481 auto *LI = cast<LoadInst>(Val: *It);
482 return std::distance(first: Scalars.begin(), last: It) *
483 LI->getDataLayout().getTypeAllocSize(Ty: LI->getType()).getFixedValue();
484}
485
486/// Checks if the stores \p VL with pointers \p PointerOps can be lowered as a
487/// single masked store. On success \p StoreVecTy is the widened store type and
488/// \p ReuseShuffleIndices is the expand mask that places each stored value at
489/// its element offset from the base (poison in the gaps).
490bool isMaskedStoreCompress(ArrayRef<Value *> VL, ArrayRef<Value *> PointerOps,
491 ArrayRef<unsigned> Order,
492 const TargetTransformInfo &TTI, const DataLayout &DL,
493 ScalarEvolution &SE, Align CommonAlignment,
494 SmallVectorImpl<int> &ReuseShuffleIndices,
495 FixedVectorType *&StoreVecTy,
496 SLPAnalysisCache &Cache) {
497 Type *ScalarTy = cast<StoreInst>(Val: VL.front())->getValueOperand()->getType();
498 const size_t Sz = VL.size();
499 // Only simple scalar element types are supported.
500 if (Sz < 2 || (!ScalarTy->isIntOrPtrTy() && !ScalarTy->isFloatingPointTy()))
501 return false;
502 Value *Ptr0 = Order.empty() ? PointerOps.front() : PointerOps[Order.front()];
503 Value *PtrN = Order.empty() ? PointerOps.back() : PointerOps[Order.back()];
504 std::optional<int64_t> Diff =
505 Cache.getPointersDiff(ElemTyA: ScalarTy, PtrA: Ptr0, ElemTyB: ScalarTy, PtrB: PtrN, DL, SE);
506 if (!Diff || *Diff <= 0)
507 return false;
508 // Avoid widened vectors with very large gaps between the stored elements.
509 const unsigned MaxRegSize =
510 TTI.getRegisterBitWidth(K: TargetTransformInfo::RGK_FixedWidthVector)
511 .getFixedValue();
512 const unsigned ScalarBits = DL.getTypeSizeInBits(Ty: ScalarTy).getFixedValue();
513 if (ScalarBits == 0 ||
514 static_cast<uint64_t>(*Diff) / Sz >= MaxRegSize / ScalarBits)
515 return false;
516 StoreVecTy = cast<FixedVectorType>(Val: getWidenedType(ScalarTy, VF: *Diff + 1));
517 unsigned AS = cast<StoreInst>(Val: VL.front())->getPointerAddressSpace();
518 if (!TTI.isLegalMaskedStore(DataType: StoreVecTy, Alignment: CommonAlignment, AddressSpace: AS,
519 MaskKind: TTI::ConstantMask))
520 return false;
521 // Build the expand mask: store I (in address-sorted order) is placed at its
522 // element offset from the base, other widened lanes are poison.
523 ReuseShuffleIndices.assign(NumElts: *Diff + 1, Elt: PoisonMaskElem);
524 int64_t Prev = -1;
525 for (unsigned I : seq<unsigned>(Size: Sz)) {
526 Value *Ptr = Order.empty() ? PointerOps[I] : PointerOps[Order[I]];
527 std::optional<int64_t> Off =
528 Cache.getPointersDiff(ElemTyA: ScalarTy, PtrA: Ptr0, ElemTyB: ScalarTy, PtrB: Ptr, DL, SE);
529 if (!Off || *Off <= Prev || *Off > *Diff)
530 return false;
531 ReuseShuffleIndices[*Off] = static_cast<int>(I);
532 Prev = *Off;
533 }
534 return true;
535}
536
537bool clusterSortPtrAccesses(ArrayRef<Value *> VL, ArrayRef<BasicBlock *> BBs,
538 Type *ElemTy, const DataLayout &DL,
539 ScalarEvolution &SE, unsigned MaxDepth,
540 SmallVectorImpl<unsigned> &SortedIndices,
541 SLPAnalysisCache &Cache) {
542 assert(
543 all_of(VL, [](const Value *V) { return V->getType()->isPointerTy(); }) &&
544 "Expected list of pointer operands.");
545 // Map from bases to a vector of (Ptr, Offset, OrigIdx), which we insert each
546 // Ptr into, sort and return the sorted indices with values next to one
547 // another.
548 SmallMapVector<
549 std::pair<BasicBlock *, Value *>,
550 SmallVector<SmallVector<std::tuple<Value *, int64_t, unsigned>>>, 8>
551 Bases;
552 Bases
553 .try_emplace(Key: std::make_pair(x: BBs.front(),
554 y: getUnderlyingObject(V: VL.front(), MaxLookup: MaxDepth)))
555 .first->second.emplace_back()
556 .emplace_back(Args: VL.front(), Args: 0U, Args: 0U);
557
558 SortedIndices.clear();
559 for (auto [Cnt, Ptr] : enumerate(First: VL.drop_front())) {
560 auto Key = std::make_pair(x: BBs[Cnt + 1], y: getUnderlyingObject(V: Ptr, MaxLookup: MaxDepth));
561 bool Found = any_of(Range&: Bases.try_emplace(Key).first->second,
562 P: [&, &Cnt = Cnt, &Ptr = Ptr](auto &Base) {
563 std::optional<int64_t> Diff = Cache.getPointersDiff(
564 ElemTyA: ElemTy, PtrA: std::get<0>(Base.front()), ElemTyB: ElemTy, PtrB: Ptr,
565 DL, SE, /*StrictCheck=*/true);
566 if (!Diff)
567 return false;
568
569 Base.emplace_back(Ptr, *Diff, Cnt + 1);
570 return true;
571 });
572
573 if (!Found) {
574 // If we haven't found enough to usefully cluster, return early.
575 if (Bases.size() > VL.size() / 2 - 1)
576 return false;
577
578 // Not found already - add a new Base
579 Bases.find(Key)->second.emplace_back().emplace_back(Args: Ptr, Args: 0, Args: Cnt + 1);
580 }
581 }
582
583 if (Bases.size() == VL.size())
584 return false;
585
586 if (Bases.size() == 1 && (Bases.front().second.size() == 1 ||
587 Bases.front().second.size() == VL.size()))
588 return false;
589
590 // For each of the bases sort the pointers by Offset and check if any of the
591 // base become consecutively allocated.
592 auto ComparePointers = [MaxDepth](Value *Ptr1, Value *Ptr2) {
593 SmallPtrSet<Value *, 13> FirstPointers;
594 SmallPtrSet<Value *, 13> SecondPointers;
595 Value *P1 = Ptr1;
596 Value *P2 = Ptr2;
597 unsigned Depth = 0;
598 while (!FirstPointers.contains(Ptr: P2) && !SecondPointers.contains(Ptr: P1)) {
599 if (P1 == P2 || Depth > MaxDepth)
600 return false;
601 FirstPointers.insert(Ptr: P1);
602 SecondPointers.insert(Ptr: P2);
603 P1 = getUnderlyingObject(V: P1, /*MaxLookup=*/1);
604 P2 = getUnderlyingObject(V: P2, /*MaxLookup=*/1);
605 ++Depth;
606 }
607 assert((FirstPointers.contains(P2) || SecondPointers.contains(P1)) &&
608 "Unable to find matching root.");
609 return FirstPointers.contains(Ptr: P2) && !SecondPointers.contains(Ptr: P1);
610 };
611 for (auto &Base : Bases) {
612 for (auto &Vec : Base.second) {
613 if (Vec.size() > 1) {
614 stable_sort(Range&: Vec, C: llvm::less_second());
615 int64_t InitialOffset = std::get<1>(t&: Vec[0]);
616 bool AnyConsecutive =
617 all_of(Range: enumerate(First&: Vec), P: [InitialOffset](const auto &P) {
618 return std::get<1>(P.value()) ==
619 int64_t(P.index()) + InitialOffset;
620 });
621 // Fill SortedIndices array only if it looks worth-while to sort the
622 // ptrs.
623 if (!AnyConsecutive)
624 return false;
625 }
626 }
627 stable_sort(Range&: Base.second, C: [&](const auto &V1, const auto &V2) {
628 return ComparePointers(std::get<0>(V1.front()), std::get<0>(V2.front()));
629 });
630 }
631
632 for (auto &T : Bases)
633 for (const auto &Vec : T.second)
634 for (const auto &P : Vec)
635 SortedIndices.push_back(Elt: std::get<2>(t: P));
636
637 assert(SortedIndices.size() == VL.size() &&
638 "Expected SortedIndices to be the size of VL");
639 return true;
640}
641
642} // namespace llvm::slpvectorizer
643