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/DataLayout.h"
27#include "llvm/IR/DerivedTypes.h"
28#include "llvm/IR/Instructions.h"
29#include "llvm/IR/Intrinsics.h"
30#include "llvm/Support/InstructionCost.h"
31
32#include <algorithm>
33#include <limits>
34#include <optional>
35#include <set>
36#include <tuple>
37#include <utility>
38
39using namespace llvm;
40
41namespace llvm::slpvectorizer {
42
43bool arePointersCompatible(Value *Ptr1, Value *Ptr2,
44 const TargetLibraryInfo &TLI, unsigned MaxDepth,
45 bool CompareOpcodes) {
46 if (getUnderlyingObject(V: Ptr1, MaxLookup: MaxDepth) !=
47 getUnderlyingObject(V: Ptr2, MaxLookup: MaxDepth))
48 return false;
49 auto *GEP1 = dyn_cast<GetElementPtrInst>(Val: Ptr1);
50 auto *GEP2 = dyn_cast<GetElementPtrInst>(Val: Ptr2);
51 return (!GEP1 || GEP1->getNumOperands() == 2) &&
52 (!GEP2 || GEP2->getNumOperands() == 2) &&
53 (((!GEP1 || isConstant(V: GEP1->getOperand(i_nocapture: 1))) &&
54 (!GEP2 || isConstant(V: GEP2->getOperand(i_nocapture: 1)))) ||
55 !CompareOpcodes ||
56 (GEP1 && GEP2 &&
57 getSameOpcode(VL: {GEP1->getOperand(i_nocapture: 1), GEP2->getOperand(i_nocapture: 1)}, TLI)));
58}
59
60/// Calculates minimal alignment as a common alignment.
61template <typename T> Align computeCommonAlignment(ArrayRef<Value *> VL) {
62 Align CommonAlignment = cast<T>(VL.consume_front())->getAlign();
63 for (Value *V : VL)
64 CommonAlignment = std::min(CommonAlignment, cast<T>(V)->getAlign());
65 return CommonAlignment;
66}
67
68template Align computeCommonAlignment<LoadInst>(ArrayRef<Value *>);
69template Align computeCommonAlignment<StoreInst>(ArrayRef<Value *>);
70
71const SCEV *calculateRtStride(ArrayRef<Value *> PointerOps, Type *ElemTy,
72 const DataLayout &DL, ScalarEvolution &SE,
73 SmallVectorImpl<unsigned> &SortedIndices) {
74 SmallVector<const SCEV *> SCEVs;
75 const SCEV *PtrSCEVLowest = nullptr;
76 const SCEV *PtrSCEVHighest = nullptr;
77 // Find lower/upper pointers from the PointerOps (i.e. with lowest and highest
78 // addresses).
79 for (Value *Ptr : PointerOps) {
80 const SCEV *PtrSCEV = SE.getSCEV(V: Ptr);
81 if (!PtrSCEV)
82 return nullptr;
83 SCEVs.push_back(Elt: PtrSCEV);
84 if (!PtrSCEVLowest && !PtrSCEVHighest) {
85 PtrSCEVLowest = PtrSCEVHighest = PtrSCEV;
86 continue;
87 }
88 const SCEV *Diff = SE.getMinusSCEV(LHS: PtrSCEV, RHS: PtrSCEVLowest);
89 if (isa<SCEVCouldNotCompute>(Val: Diff))
90 return nullptr;
91 if (Diff->isNonConstantNegative()) {
92 PtrSCEVLowest = PtrSCEV;
93 continue;
94 }
95 const SCEV *Diff1 = SE.getMinusSCEV(LHS: PtrSCEVHighest, RHS: PtrSCEV);
96 if (isa<SCEVCouldNotCompute>(Val: Diff1))
97 return nullptr;
98 if (Diff1->isNonConstantNegative()) {
99 PtrSCEVHighest = PtrSCEV;
100 continue;
101 }
102 }
103 // Dist = PtrSCEVHighest - PtrSCEVLowest;
104 const SCEV *Dist = SE.getMinusSCEV(LHS: PtrSCEVHighest, RHS: PtrSCEVLowest);
105 if (isa<SCEVCouldNotCompute>(Val: Dist))
106 return nullptr;
107 int Size = DL.getTypeStoreSize(Ty: ElemTy);
108 auto TryGetStride = [&](const SCEV *Dist,
109 const SCEV *Multiplier) -> const SCEV * {
110 if (const auto *M = dyn_cast<SCEVMulExpr>(Val: Dist)) {
111 if (M->getOperand(i: 0) == Multiplier)
112 return M->getOperand(i: 1);
113 if (M->getOperand(i: 1) == Multiplier)
114 return M->getOperand(i: 0);
115 return nullptr;
116 }
117 if (Multiplier == Dist)
118 return SE.getConstant(Ty: Dist->getType(), V: 1);
119 return SE.getUDivExactExpr(LHS: Dist, RHS: Multiplier);
120 };
121 // Stride_in_elements = Dist / element_size * (num_elems - 1).
122 const SCEV *Stride = nullptr;
123 if (Size != 1 || SCEVs.size() > 1) {
124 const SCEV *Sz = SE.getConstant(Ty: Dist->getType(), V: Size * (SCEVs.size() - 1));
125 Stride = TryGetStride(Dist, Sz);
126 if (!Stride)
127 return nullptr;
128 }
129 if (!Stride || isa<SCEVConstant>(Val: Stride))
130 return nullptr;
131 // Iterate through all pointers and check if all distances are
132 // unique multiple of Stride.
133 using DistOrdPair = std::pair<int64_t, int>;
134 auto Compare = llvm::less_first();
135 std::set<DistOrdPair, decltype(Compare)> Offsets(Compare);
136 bool IsConsecutive = true;
137 for (const auto [Idx, PtrSCEV] : enumerate(First&: SCEVs)) {
138 unsigned Dist = 0;
139 if (PtrSCEV != PtrSCEVLowest) {
140 const SCEV *Diff = SE.getMinusSCEV(LHS: PtrSCEV, RHS: PtrSCEVLowest);
141 const SCEV *Coeff = TryGetStride(Diff, Stride);
142 if (!Coeff)
143 return nullptr;
144 const auto *SC = dyn_cast<SCEVConstant>(Val: Coeff);
145 if (!SC || isa<SCEVCouldNotCompute>(Val: SC))
146 return nullptr;
147 if (!SE.getMinusSCEV(LHS: PtrSCEV, RHS: SE.getAddExpr(LHS: PtrSCEVLowest,
148 RHS: SE.getMulExpr(LHS: Stride, RHS: SC)))
149 ->isZero())
150 return nullptr;
151 Dist = SC->getAPInt().getZExtValue();
152 }
153 // If the strides are not the same or repeated, we can't vectorize.
154 if ((Dist / Size) * Size != Dist || (Dist / Size) >= SCEVs.size())
155 return nullptr;
156 auto Res = Offsets.emplace(args&: Dist, args&: Idx);
157 if (!Res.second)
158 return nullptr;
159 // Consecutive order if the inserted element is the last one.
160 IsConsecutive = IsConsecutive && std::next(x: Res.first) == Offsets.end();
161 }
162 SortedIndices.clear();
163 if (!IsConsecutive) {
164 // Fill SortedIndices array only if it is non-consecutive.
165 SortedIndices.resize(N: PointerOps.size());
166 for (const auto [Idx, Pair] : enumerate(First&: Offsets))
167 SortedIndices[Idx] = Pair.second;
168 }
169 return Stride;
170}
171
172/// Builds compress-like mask for shuffles for the given \p PointerOps, ordered
173/// with \p Order.
174/// \return true if the mask represents strided access, false - otherwise.
175static bool buildCompressMask(ArrayRef<Value *> PointerOps,
176 ArrayRef<unsigned> Order, Type *ScalarTy,
177 const DataLayout &DL, ScalarEvolution &SE,
178 SmallVectorImpl<int> &CompressMask) {
179 const unsigned Sz = PointerOps.size();
180 CompressMask.assign(NumElts: Sz, Elt: PoisonMaskElem);
181 // The first element always set.
182 CompressMask[0] = 0;
183 // Check if the mask represents strided access.
184 std::optional<unsigned> Stride = 0;
185 Value *Ptr0 = Order.empty() ? PointerOps.front() : PointerOps[Order.front()];
186 for (unsigned I : seq<unsigned>(Begin: 1, End: Sz)) {
187 Value *Ptr = Order.empty() ? PointerOps[I] : PointerOps[Order[I]];
188 std::optional<int64_t> OptPos =
189 getPointersDiff(ElemTyA: ScalarTy, PtrA: Ptr0, ElemTyB: ScalarTy, PtrB: Ptr, DL, SE);
190 if (!OptPos || OptPos > std::numeric_limits<unsigned>::max())
191 return false;
192 unsigned Pos = static_cast<unsigned>(*OptPos);
193 CompressMask[I] = Pos;
194 if (!Stride)
195 continue;
196 if (*Stride == 0) {
197 *Stride = Pos;
198 continue;
199 }
200 if (Pos != *Stride * I)
201 Stride.reset();
202 }
203 return Stride.has_value();
204}
205
206/// Checks if the \p VL can be transformed to a (masked)load + compress or
207/// (masked) interleaved load.
208bool isMaskedLoadCompress(
209 ArrayRef<Value *> VL, ArrayRef<Value *> PointerOps,
210 ArrayRef<unsigned> Order, const TargetTransformInfo &TTI,
211 const DataLayout &DL, ScalarEvolution &SE, AssumptionCache &AC,
212 const DominatorTree &DT, const TargetLibraryInfo &TLI,
213 const TargetTransformInfo::TargetCostKind CostKind,
214 const function_ref<bool(Value *)> AreAllUsersVectorized, bool ReVec,
215 bool &IsMasked, unsigned &InterleaveFactor,
216 SmallVectorImpl<int> &CompressMask, VectorType *&LoadVecTy) {
217 InterleaveFactor = 0;
218 Type *ScalarTy = VL.front()->getType();
219 const size_t Sz = VL.size();
220 auto *VecTy = cast<VectorType>(Val: getWidenedType(ScalarTy, VF: Sz));
221 SmallVector<int> Mask;
222 if (!Order.empty())
223 inversePermutation(Indices: Order, Mask);
224 // Check external uses.
225 for (const auto [I, V] : enumerate(First&: VL)) {
226 if (AreAllUsersVectorized(V))
227 continue;
228 InstructionCost ExtractCost =
229 TTI.getVectorInstrCost(Opcode: Instruction::ExtractElement, Val: VecTy, CostKind,
230 Index: Mask.empty() ? I : Mask[I]);
231 InstructionCost ScalarCost =
232 TTI.getInstructionCost(U: cast<Instruction>(Val: V), CostKind);
233 if (ExtractCost <= ScalarCost)
234 return false;
235 }
236 Value *Ptr0;
237 Value *PtrN;
238 if (Order.empty()) {
239 Ptr0 = PointerOps.front();
240 PtrN = PointerOps.back();
241 } else {
242 Ptr0 = PointerOps[Order.front()];
243 PtrN = PointerOps[Order.back()];
244 }
245 std::optional<int64_t> Diff =
246 getPointersDiff(ElemTyA: ScalarTy, PtrA: Ptr0, ElemTyB: ScalarTy, PtrB: PtrN, DL, SE);
247 if (!Diff)
248 return false;
249 const size_t MaxRegSize =
250 TTI.getRegisterBitWidth(K: TargetTransformInfo::RGK_FixedWidthVector)
251 .getFixedValue();
252 // Check for very large distances between elements.
253 if (*Diff / Sz >= MaxRegSize / 8)
254 return false;
255 LoadVecTy = cast<FixedVectorType>(Val: getWidenedType(ScalarTy, VF: *Diff + 1));
256 auto *LI = cast<LoadInst>(Val: Order.empty() ? VL.front() : VL[Order.front()]);
257 Align CommonAlignment = LI->getAlign();
258 SimplifyQuery SQ(
259 DL, &TLI, &DT, &AC,
260 cast<LoadInst>(Val: Order.empty() ? VL.back() : VL[Order.back()]));
261 IsMasked = !isSafeToLoadUnconditionally(V: Ptr0, Ty: LoadVecTy, Alignment: CommonAlignment, SQ);
262 if (IsMasked && !TTI.isLegalMaskedLoad(DataType: LoadVecTy, Alignment: CommonAlignment,
263 AddressSpace: LI->getPointerAddressSpace()))
264 return false;
265 // TODO: perform the analysis of each scalar load for better
266 // safe-load-unconditionally analysis.
267 bool IsStrided =
268 buildCompressMask(PointerOps, Order, ScalarTy, DL, SE, CompressMask);
269 assert(CompressMask.size() >= 2 && "At least two elements are required");
270 SmallVector<Value *> OrderedPointerOps(PointerOps);
271 if (!Order.empty())
272 reorderScalars(Scalars&: OrderedPointerOps, Mask);
273 auto [ScalarGEPCost, VectorGEPCost] =
274 getGEPCosts(TTI, Ptrs: OrderedPointerOps, BasePtr: OrderedPointerOps.front(),
275 Opcode: Instruction::Load, CostKind, ScalarTy, VecTy: LoadVecTy);
276 // The cost of scalar loads.
277 InstructionCost ScalarLoadsCost =
278 accumulate(Range&: VL, Init: InstructionCost(),
279 Op: [&](InstructionCost C, Value *V) {
280 return C + TTI.getInstructionCost(U: cast<Instruction>(Val: V),
281 CostKind);
282 }) +
283 ScalarGEPCost;
284 APInt DemandedElts = APInt::getAllOnes(numBits: Sz);
285 InstructionCost GatherCost =
286 getScalarizationOverhead(TTI, ReVec, ScalarTy, Ty: VecTy, DemandedElts,
287 /*Insert=*/true,
288 /*Extract=*/false, CostKind) +
289 ScalarLoadsCost;
290 InstructionCost LoadCost = 0;
291 if (IsMasked) {
292 LoadCost = TTI.getMemIntrinsicInstrCost(
293 MICA: MemIntrinsicCostAttributes(Intrinsic::masked_load, LoadVecTy,
294 CommonAlignment,
295 LI->getPointerAddressSpace()),
296 CostKind);
297 } else {
298 LoadCost =
299 TTI.getMemoryOpCost(Opcode: Instruction::Load, Src: LoadVecTy, Alignment: CommonAlignment,
300 AddressSpace: LI->getPointerAddressSpace(), CostKind);
301 }
302 if (IsStrided && !IsMasked && Order.empty()) {
303 // Check for potential segmented(interleaved) loads.
304 VectorType *AlignedLoadVecTy = cast<VectorType>(Val: getWidenedType(
305 ScalarTy,
306 VF: getFullVectorNumberOfElements(TTI, Ty: ScalarTy, Sz: *Diff + 1, ReVec)));
307 SimplifyQuery SQ(DL, &TLI, &DT, &AC, cast<LoadInst>(Val: VL.back()));
308 if (!isSafeToLoadUnconditionally(V: Ptr0, Ty: AlignedLoadVecTy, Alignment: CommonAlignment,
309 SQ))
310 AlignedLoadVecTy = LoadVecTy;
311 if (TTI.isLegalInterleavedAccessType(VTy: AlignedLoadVecTy, Factor: CompressMask[1],
312 Alignment: CommonAlignment,
313 AddrSpace: LI->getPointerAddressSpace())) {
314 InstructionCost InterleavedCost =
315 VectorGEPCost + TTI.getInterleavedMemoryOpCost(
316 Opcode: Instruction::Load, VecTy: AlignedLoadVecTy,
317 Factor: CompressMask[1], Indices: {}, Alignment: CommonAlignment,
318 AddressSpace: LI->getPointerAddressSpace(), CostKind, UseMaskForCond: IsMasked);
319 if (InterleavedCost < GatherCost) {
320 InterleaveFactor = CompressMask[1];
321 LoadVecTy = AlignedLoadVecTy;
322 return true;
323 }
324 }
325 }
326 // Estimating the compression shuffle cost below can be extremely expensive
327 // for a very wide LoadVecTy, which is split into a large number of vector
328 // registers (see processShuffleMasks). The shuffle cost is always
329 // non-negative, so if the load cost alone already reaches the gather cost the
330 // masked-load-compress cannot be profitable. Bail out before the costly
331 // shuffle cost estimation in that case.
332 if (VectorGEPCost + LoadCost >= GatherCost)
333 return false;
334 InstructionCost CompressCost = getShuffleCost(
335 TTI, Kind: TTI::SK_PermuteSingleSrc, Tp: LoadVecTy, CostKind, Mask: CompressMask);
336 if (!Order.empty()) {
337 SmallVector<int> NewMask(Sz, PoisonMaskElem);
338 for (unsigned I : seq<unsigned>(Size: Sz)) {
339 NewMask[I] = CompressMask[Mask[I]];
340 }
341 CompressMask.swap(RHS&: NewMask);
342 }
343 InstructionCost TotalVecCost = VectorGEPCost + LoadCost + CompressCost;
344 return TotalVecCost < GatherCost;
345}
346
347/// Checks if the \p VL can be transformed to a (masked)load + compress or
348/// (masked) interleaved load.
349bool isMaskedLoadCompress(
350 ArrayRef<Value *> VL, ArrayRef<Value *> PointerOps,
351 ArrayRef<unsigned> Order, const TargetTransformInfo &TTI,
352 const DataLayout &DL, ScalarEvolution &SE, AssumptionCache &AC,
353 const DominatorTree &DT, const TargetLibraryInfo &TLI,
354 const TargetTransformInfo::TargetCostKind CostKind,
355 const function_ref<bool(Value *)> AreAllUsersVectorized, bool ReVec) {
356 bool IsMasked;
357 unsigned InterleaveFactor;
358 SmallVector<int> CompressMask;
359 VectorType *LoadVecTy;
360 return isMaskedLoadCompress(VL, PointerOps, Order, TTI, DL, SE, AC, DT, TLI,
361 CostKind, AreAllUsersVectorized, ReVec, IsMasked,
362 InterleaveFactor, CompressMask, LoadVecTy);
363}
364
365/// Checks if the stores \p VL with pointers \p PointerOps can be lowered as a
366/// single masked store. On success \p StoreVecTy is the widened store type and
367/// \p ReuseShuffleIndices is the expand mask that places each stored value at
368/// its element offset from the base (poison in the gaps).
369bool isMaskedStoreCompress(ArrayRef<Value *> VL, ArrayRef<Value *> PointerOps,
370 ArrayRef<unsigned> Order,
371 const TargetTransformInfo &TTI, const DataLayout &DL,
372 ScalarEvolution &SE, Align CommonAlignment,
373 SmallVectorImpl<int> &ReuseShuffleIndices,
374 FixedVectorType *&StoreVecTy) {
375 Type *ScalarTy = cast<StoreInst>(Val: VL.front())->getValueOperand()->getType();
376 const size_t Sz = VL.size();
377 // Only simple scalar element types are supported.
378 if (Sz < 2 || (!ScalarTy->isIntOrPtrTy() && !ScalarTy->isFloatingPointTy()))
379 return false;
380 Value *Ptr0 = Order.empty() ? PointerOps.front() : PointerOps[Order.front()];
381 Value *PtrN = Order.empty() ? PointerOps.back() : PointerOps[Order.back()];
382 std::optional<int64_t> Diff =
383 getPointersDiff(ElemTyA: ScalarTy, PtrA: Ptr0, ElemTyB: ScalarTy, PtrB: PtrN, DL, SE);
384 if (!Diff || *Diff <= 0)
385 return false;
386 // Avoid widened vectors with very large gaps between the stored elements.
387 const unsigned MaxRegSize =
388 TTI.getRegisterBitWidth(K: TargetTransformInfo::RGK_FixedWidthVector)
389 .getFixedValue();
390 const unsigned ScalarBits = DL.getTypeSizeInBits(Ty: ScalarTy).getFixedValue();
391 if (ScalarBits == 0 ||
392 static_cast<uint64_t>(*Diff) / Sz >= MaxRegSize / ScalarBits)
393 return false;
394 StoreVecTy = cast<FixedVectorType>(Val: getWidenedType(ScalarTy, VF: *Diff + 1));
395 unsigned AS = cast<StoreInst>(Val: VL.front())->getPointerAddressSpace();
396 if (!TTI.isLegalMaskedStore(DataType: StoreVecTy, Alignment: CommonAlignment, AddressSpace: AS,
397 MaskKind: TTI::ConstantMask))
398 return false;
399 // Build the expand mask: store I (in address-sorted order) is placed at its
400 // element offset from the base, other widened lanes are poison.
401 ReuseShuffleIndices.assign(NumElts: *Diff + 1, Elt: PoisonMaskElem);
402 int64_t Prev = -1;
403 for (unsigned I : seq<unsigned>(Size: Sz)) {
404 Value *Ptr = Order.empty() ? PointerOps[I] : PointerOps[Order[I]];
405 std::optional<int64_t> Off =
406 getPointersDiff(ElemTyA: ScalarTy, PtrA: Ptr0, ElemTyB: ScalarTy, PtrB: Ptr, DL, SE);
407 if (!Off || *Off <= Prev || *Off > *Diff)
408 return false;
409 ReuseShuffleIndices[*Off] = static_cast<int>(I);
410 Prev = *Off;
411 }
412 return true;
413}
414
415bool clusterSortPtrAccesses(ArrayRef<Value *> VL, ArrayRef<BasicBlock *> BBs,
416 Type *ElemTy, const DataLayout &DL,
417 ScalarEvolution &SE, unsigned MaxDepth,
418 SmallVectorImpl<unsigned> &SortedIndices) {
419 assert(
420 all_of(VL, [](const Value *V) { return V->getType()->isPointerTy(); }) &&
421 "Expected list of pointer operands.");
422 // Map from bases to a vector of (Ptr, Offset, OrigIdx), which we insert each
423 // Ptr into, sort and return the sorted indices with values next to one
424 // another.
425 SmallMapVector<
426 std::pair<BasicBlock *, Value *>,
427 SmallVector<SmallVector<std::tuple<Value *, int64_t, unsigned>>>, 8>
428 Bases;
429 Bases
430 .try_emplace(Key: std::make_pair(x: BBs.front(),
431 y: getUnderlyingObject(V: VL.front(), MaxLookup: MaxDepth)))
432 .first->second.emplace_back()
433 .emplace_back(Args: VL.front(), Args: 0U, Args: 0U);
434
435 SortedIndices.clear();
436 for (auto [Cnt, Ptr] : enumerate(First: VL.drop_front())) {
437 auto Key = std::make_pair(x: BBs[Cnt + 1], y: getUnderlyingObject(V: Ptr, MaxLookup: MaxDepth));
438 bool Found = any_of(Range&: Bases.try_emplace(Key).first->second,
439 P: [&, &Cnt = Cnt, &Ptr = Ptr](auto &Base) {
440 std::optional<int64_t> Diff =
441 getPointersDiff(ElemTy, std::get<0>(Base.front()),
442 ElemTy, Ptr, DL, SE,
443 /*StrictCheck=*/true);
444 if (!Diff)
445 return false;
446
447 Base.emplace_back(Ptr, *Diff, Cnt + 1);
448 return true;
449 });
450
451 if (!Found) {
452 // If we haven't found enough to usefully cluster, return early.
453 if (Bases.size() > VL.size() / 2 - 1)
454 return false;
455
456 // Not found already - add a new Base
457 Bases.find(Key)->second.emplace_back().emplace_back(Args: Ptr, Args: 0, Args: Cnt + 1);
458 }
459 }
460
461 if (Bases.size() == VL.size())
462 return false;
463
464 if (Bases.size() == 1 && (Bases.front().second.size() == 1 ||
465 Bases.front().second.size() == VL.size()))
466 return false;
467
468 // For each of the bases sort the pointers by Offset and check if any of the
469 // base become consecutively allocated.
470 auto ComparePointers = [MaxDepth](Value *Ptr1, Value *Ptr2) {
471 SmallPtrSet<Value *, 13> FirstPointers;
472 SmallPtrSet<Value *, 13> SecondPointers;
473 Value *P1 = Ptr1;
474 Value *P2 = Ptr2;
475 unsigned Depth = 0;
476 while (!FirstPointers.contains(Ptr: P2) && !SecondPointers.contains(Ptr: P1)) {
477 if (P1 == P2 || Depth > MaxDepth)
478 return false;
479 FirstPointers.insert(Ptr: P1);
480 SecondPointers.insert(Ptr: P2);
481 P1 = getUnderlyingObject(V: P1, /*MaxLookup=*/1);
482 P2 = getUnderlyingObject(V: P2, /*MaxLookup=*/1);
483 ++Depth;
484 }
485 assert((FirstPointers.contains(P2) || SecondPointers.contains(P1)) &&
486 "Unable to find matching root.");
487 return FirstPointers.contains(Ptr: P2) && !SecondPointers.contains(Ptr: P1);
488 };
489 for (auto &Base : Bases) {
490 for (auto &Vec : Base.second) {
491 if (Vec.size() > 1) {
492 stable_sort(Range&: Vec, C: llvm::less_second());
493 int64_t InitialOffset = std::get<1>(t&: Vec[0]);
494 bool AnyConsecutive =
495 all_of(Range: enumerate(First&: Vec), P: [InitialOffset](const auto &P) {
496 return std::get<1>(P.value()) ==
497 int64_t(P.index()) + InitialOffset;
498 });
499 // Fill SortedIndices array only if it looks worth-while to sort the
500 // ptrs.
501 if (!AnyConsecutive)
502 return false;
503 }
504 }
505 stable_sort(Range&: Base.second, C: [&](const auto &V1, const auto &V2) {
506 return ComparePointers(std::get<0>(V1.front()), std::get<0>(V2.front()));
507 });
508 }
509
510 for (auto &T : Bases)
511 for (const auto &Vec : T.second)
512 for (const auto &P : Vec)
513 SortedIndices.push_back(Elt: std::get<2>(t: P));
514
515 assert(SortedIndices.size() == VL.size() &&
516 "Expected SortedIndices to be the size of VL");
517 return true;
518}
519
520} // namespace llvm::slpvectorizer
521