1//===- VPlanEVLTailFolding.cpp - EVL tail folding transforms --------------===//
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/// \file
10/// This file implements the VPlan-to-VPlan transforms related to explicit
11/// vector length (EVL) tail folding support.
12///
13//===----------------------------------------------------------------------===//
14
15#include "LoopVectorizationPlanner.h"
16#include "VPlan.h"
17#include "VPlanCFG.h"
18#include "VPlanHelpers.h"
19#include "VPlanPatternMatch.h"
20#include "VPlanTransforms.h"
21#include "VPlanUtils.h"
22#include "llvm/Analysis/ScalarEvolution.h"
23#include "llvm/IR/Intrinsics.h"
24
25using namespace llvm;
26using namespace VPlanPatternMatch;
27
28/// From the definition of llvm.experimental.get.vector.length,
29/// VPInstruction::ExplicitVectorLength(%AVL) = %AVL when %AVL <= VF.
30bool VPlanTransforms::simplifyKnownEVL(VPlan &Plan, ElementCount VF,
31 PredicatedScalarEvolution &PSE) {
32 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
33 Range: vp_depth_first_deep(G: Plan.getEntry()))) {
34 for (VPRecipeBase &R : *VPBB) {
35 VPValue *AVL;
36 if (!match(V: &R, P: m_EVL(Op0: m_VPValue(V&: AVL))))
37 continue;
38
39 const SCEV *AVLSCEV = vputils::getSCEVExprForVPValue(V: AVL, PSE);
40 if (isa<SCEVCouldNotCompute>(Val: AVLSCEV))
41 continue;
42 ScalarEvolution &SE = *PSE.getSE();
43 const SCEV *VFSCEV = SE.getElementCount(Ty: AVLSCEV->getType(), EC: VF);
44 if (!SE.isKnownPredicate(Pred: CmpInst::ICMP_ULE, LHS: AVLSCEV, RHS: VFSCEV))
45 continue;
46
47 VPValue *Trunc = VPBuilder(&R).createScalarZExtOrTrunc(
48 Op: AVL, ResultTy: Type::getInt32Ty(C&: Plan.getContext()), DL: R.getDebugLoc());
49 if (Trunc != AVL) {
50 auto *TruncR = cast<VPSingleDefRecipe>(Val: Trunc);
51 const DataLayout &DL = Plan.getDataLayout();
52 if (VPValue *Folded =
53 vputils::tryToFoldLiveIns(R&: *TruncR, Operands: TruncR->operands(), DL))
54 Trunc = Folded;
55 }
56 R.getVPSingleValue()->replaceAllUsesWith(New: Trunc);
57 return true;
58 }
59 }
60 return false;
61}
62
63template <typename Op0_t, typename Op1_t> struct RemoveMask_match {
64 Op0_t In;
65 Op1_t &Out;
66
67 RemoveMask_match(const Op0_t &In, Op1_t &Out) : In(In), Out(Out) {}
68
69 template <typename OpTy> bool match(OpTy *V) const {
70 if (m_Specific(In).match(V)) {
71 Out = nullptr;
72 return true;
73 }
74 return m_LogicalAnd(m_Specific(In), m_VPValue(Out)).match(V);
75 }
76};
77
78/// Match a specific mask \p In, or a combination of it (logical-and In, Out).
79/// Returns the remaining part \p Out if so, or nullptr otherwise.
80template <typename Op0_t, typename Op1_t>
81static inline RemoveMask_match<Op0_t, Op1_t> m_RemoveMask(const Op0_t &In,
82 Op1_t &Out) {
83 return RemoveMask_match<Op0_t, Op1_t>(In, Out);
84}
85
86static std::optional<Intrinsic::ID> getVPDivRemIntrinsic(Intrinsic::ID IntrID) {
87 switch (IntrID) {
88 case Intrinsic::masked_udiv:
89 return Intrinsic::vp_udiv;
90 case Intrinsic::masked_sdiv:
91 return Intrinsic::vp_sdiv;
92 case Intrinsic::masked_urem:
93 return Intrinsic::vp_urem;
94 case Intrinsic::masked_srem:
95 return Intrinsic::vp_srem;
96 default:
97 return std::nullopt;
98 }
99}
100
101/// Try to optimize a \p CurRecipe masked by \p HeaderMask to a corresponding
102/// EVL-based recipe without the header mask. Returns nullptr if no EVL-based
103/// recipe could be created.
104/// \p HeaderMask Header Mask.
105/// \p CurRecipe Recipe to be transform.
106/// \p EVL The explicit vector length parameter of vector-predication
107/// intrinsics.
108static VPRecipeBase *optimizeMaskToEVL(VPValue *HeaderMask,
109 VPRecipeBase &CurRecipe, VPValue &EVL) {
110 VPlan *Plan = CurRecipe.getParent()->getPlan();
111 DebugLoc DL = CurRecipe.getDebugLoc();
112 VPValue *Addr, *Mask, *EndPtr;
113
114 /// Adjust any end pointers so that they point to the end of EVL lanes not VF.
115 auto AdjustEndPtr = [&CurRecipe, &EVL](VPValue *EndPtr) {
116 auto *EVLEndPtr = cast<VPVectorEndPointerRecipe>(Val: EndPtr)->clone();
117 EVLEndPtr->insertBefore(InsertPos: &CurRecipe);
118 // Cast EVL (i32) to match the VF operand's type.
119 VPValue *EVLAsVF = VPBuilder(EVLEndPtr).createScalarZExtOrTrunc(
120 Op: &EVL, ResultTy: EVLEndPtr->getOperand(N: 1)->getScalarType(),
121 DL: DebugLoc::getUnknown());
122 EVLEndPtr->setOperand(I: 1, New: EVLAsVF);
123 return EVLEndPtr;
124 };
125
126 auto GetVPReverse = [&CurRecipe, &EVL, Plan,
127 DL](VPValue *V) -> VPWidenIntrinsicRecipe * {
128 if (!V)
129 return nullptr;
130 auto *Reverse = new VPWidenIntrinsicRecipe(
131 Intrinsic::experimental_vp_reverse, {V, Plan->getTrue(), &EVL},
132 V->getScalarType(), {}, {}, DL);
133 Reverse->insertBefore(InsertPos: &CurRecipe);
134 return Reverse;
135 };
136
137 if (match(V: &CurRecipe,
138 P: m_MaskedLoad(Addr: m_VPValue(V&: Addr), Mask: m_RemoveMask(In: HeaderMask, Out&: Mask))))
139 return new VPWidenLoadEVLRecipe(cast<VPWidenLoadRecipe>(Val&: CurRecipe), Addr,
140 EVL, Mask);
141
142 if (match(V: &CurRecipe,
143 P: m_MaskedLoad(Addr: m_VPValue(V&: EndPtr),
144 Mask: m_Reverse(Op0: m_RemoveMask(In: HeaderMask, Out&: Mask)))) &&
145 match(V: EndPtr, P: m_VecEndPtr(Op0: m_VPValue(), Op1: m_Specific(VPV: &Plan->getVF())))) {
146 Mask = GetVPReverse(Mask);
147 Addr = AdjustEndPtr(EndPtr);
148 auto *LoadR = new VPWidenLoadEVLRecipe(cast<VPWidenLoadRecipe>(Val&: CurRecipe),
149 Addr, EVL, Mask);
150 LoadR->insertBefore(InsertPos: &CurRecipe);
151 VPValue *Poison = Plan->getPoison(Ty: LoadR->getScalarType());
152 return new VPWidenIntrinsicRecipe(Intrinsic::vector_splice_left,
153 {Poison, LoadR, &EVL},
154 LoadR->getScalarType(), {}, {}, DL);
155 }
156
157 VPValue *Stride;
158 if (match(V: &CurRecipe, P: m_Intrinsic<Intrinsic::experimental_vp_strided_load>(
159 Ops: m_VPValue(V&: Addr), Ops: m_VPValue(V&: Stride),
160 Ops: m_RemoveMask(In: HeaderMask, Out&: Mask),
161 Ops: m_TruncOrSelf(Op0: m_Specific(VPV: &Plan->getVF()))))) {
162 if (!Mask)
163 Mask = Plan->getTrue();
164 auto *NewLoad = cast<VPWidenMemIntrinsicRecipe>(Val: &CurRecipe)->clone();
165 NewLoad->setOperand(I: 2, New: Mask);
166 NewLoad->setOperand(I: 3, New: &EVL);
167 return NewLoad;
168 }
169
170 VPValue *StoredVal;
171 if (match(V: &CurRecipe, P: m_MaskedStore(Addr: m_VPValue(V&: Addr), Val: m_VPValue(V&: StoredVal),
172 Mask: m_RemoveMask(In: HeaderMask, Out&: Mask))))
173 return new VPWidenStoreEVLRecipe(cast<VPWidenStoreRecipe>(Val&: CurRecipe), Addr,
174 StoredVal, EVL, Mask);
175
176 if (match(V: &CurRecipe,
177 P: m_MaskedStore(Addr: m_VPValue(V&: EndPtr), Val: m_VPValue(V&: StoredVal),
178 Mask: m_Reverse(Op0: m_RemoveMask(In: HeaderMask, Out&: Mask)))) &&
179 match(V: EndPtr, P: m_VecEndPtr(Op0: m_VPValue(), Op1: m_Specific(VPV: &Plan->getVF())))) {
180 Mask = GetVPReverse(Mask);
181 Addr = AdjustEndPtr(EndPtr);
182 VPValue *Poison = Plan->getPoison(Ty: StoredVal->getScalarType());
183 auto *SpliceR = new VPWidenIntrinsicRecipe(
184 Intrinsic::vector_splice_right, {StoredVal, Poison, &EVL},
185 StoredVal->getScalarType(), {}, {}, DL);
186 SpliceR->insertBefore(InsertPos: &CurRecipe);
187 return new VPWidenStoreEVLRecipe(cast<VPWidenStoreRecipe>(Val&: CurRecipe), Addr,
188 SpliceR, EVL, Mask);
189 }
190
191 if (auto *Rdx = dyn_cast<VPReductionRecipe>(Val: &CurRecipe))
192 if (Rdx->isConditional() &&
193 match(V: Rdx->getCondOp(), P: m_RemoveMask(In: HeaderMask, Out&: Mask)))
194 return new VPReductionEVLRecipe(*Rdx, EVL, Mask);
195
196 if (auto *Interleave = dyn_cast<VPInterleaveRecipe>(Val: &CurRecipe))
197 if (Interleave->getMask() &&
198 match(V: Interleave->getMask(), P: m_RemoveMask(In: HeaderMask, Out&: Mask)))
199 return new VPInterleaveEVLRecipe(*Interleave, EVL, Mask);
200
201 VPValue *LHS, *RHS;
202 if (match(V: &CurRecipe, P: m_SelectLike(Op0: m_RemoveMask(In: HeaderMask, Out&: Mask),
203 Op1: m_VPValue(V&: LHS), Op2: m_VPValue(V&: RHS))))
204 return new VPWidenIntrinsicRecipe(
205 Intrinsic::vp_merge, {Mask ? Mask : Plan->getTrue(), LHS, RHS, &EVL},
206 LHS->getScalarType(), {}, {}, DL);
207
208 if (match(V: &CurRecipe, P: m_LastActiveLane(Op0: m_Specific(VPV: HeaderMask)))) {
209 Type *Ty = CurRecipe.getVPSingleValue()->getScalarType();
210 VPValue *ZExt = VPBuilder(&CurRecipe).createScalarZExtOrTrunc(Op: &EVL, ResultTy: Ty, DL);
211 return new VPInstruction(
212 Instruction::Sub, {ZExt, Plan->getConstantInt(Ty, Val: 1)},
213 VPIRFlags::getDefaultFlags(Opcode: Instruction::Sub), {}, DL);
214 }
215
216 // lhs | (headermask && rhs) -> vp.merge rhs, true, lhs, evl
217 if (match(V: &CurRecipe,
218 P: m_c_BinaryOr(Op0: m_VPValue(V&: LHS),
219 Op1: m_LogicalAnd(Op0: m_Specific(VPV: HeaderMask), Op1: m_VPValue(V&: RHS)))))
220 return new VPWidenIntrinsicRecipe(Intrinsic::vp_merge,
221 {RHS, Plan->getTrue(), LHS, &EVL},
222 LHS->getScalarType(), {}, {}, DL);
223
224 if (auto *IntrR = dyn_cast<VPWidenIntrinsicRecipe>(Val: &CurRecipe))
225 if (auto VPID = getVPDivRemIntrinsic(IntrID: IntrR->getVectorIntrinsicID()))
226 if (match(V: IntrR->getOperand(N: 2), P: m_RemoveMask(In: HeaderMask, Out&: Mask)))
227 return new VPWidenIntrinsicRecipe(*VPID,
228 {IntrR->getOperand(N: 0),
229 IntrR->getOperand(N: 1),
230 Mask ? Mask : Plan->getTrue(), &EVL},
231 IntrR->getScalarType(), {}, {}, DL);
232
233 return nullptr;
234}
235
236/// Optimize away any EVL-based header masks to VP intrinsic based recipes.
237/// The transforms here need to preserve the original semantics.
238void VPlanTransforms::optimizeEVLMasks(VPlan &Plan) {
239 // Find the EVL-based header mask if it exists: icmp ult step-vector, EVL
240 VPValue *HeaderMask = nullptr, *EVL = nullptr;
241 for (VPRecipeBase &R : *Plan.getVectorLoopRegion()->getEntryBasicBlock()) {
242 if (match(V: &R, P: m_SpecificICmp(MatchPred: CmpInst::ICMP_ULT, Op0: m_StepVector(),
243 Op1: m_VPValue(V&: EVL))) &&
244 match(V: EVL, P: m_EVL(Op0: m_VPValue()))) {
245 HeaderMask = R.getVPSingleValue();
246 break;
247 }
248 }
249 if (!HeaderMask)
250 return;
251
252 SmallVector<VPRecipeBase *> OldRecipes;
253 for (VPUser *U : vputils::collectUsersRecursively(V: HeaderMask)) {
254 VPRecipeBase *R = cast<VPRecipeBase>(Val: U);
255 if (auto *NewR = optimizeMaskToEVL(HeaderMask, CurRecipe&: *R, EVL&: *EVL)) {
256 NewR->insertBefore(InsertPos: R);
257 for (auto [Old, New] :
258 zip_equal(t: R->definedValues(), u: NewR->definedValues()))
259 Old->replaceAllUsesWith(New);
260 OldRecipes.push_back(Elt: R);
261 }
262 }
263
264 // Replace remaining (HeaderMask && Mask) with vp.merge (True, Mask,
265 // False, EVL)
266 for (VPUser *U : vputils::collectUsersRecursively(V: HeaderMask)) {
267 VPValue *Mask;
268 if (match(U, P: m_LogicalAnd(Op0: m_Specific(VPV: HeaderMask), Op1: m_VPValue(V&: Mask)))) {
269 auto *LogicalAnd = cast<VPInstruction>(Val: U);
270 auto *Merge = new VPWidenIntrinsicRecipe(
271 Intrinsic::vp_merge, {Plan.getTrue(), Mask, Plan.getFalse(), EVL},
272 Mask->getScalarType(), {}, {}, LogicalAnd->getDebugLoc());
273 Merge->insertBefore(InsertPos: LogicalAnd);
274 LogicalAnd->replaceAllUsesWith(New: Merge);
275 OldRecipes.push_back(Elt: LogicalAnd);
276 }
277 }
278
279 // Pull out left splices from any elementwise op.
280 // binop(splice.left(poison, x, evl), live-in)
281 // -> splice.left(poison, binop(x,live-in), evl)
282 vputils::pullOutPermutations(
283 Plan,
284 Perm: [&EVL](VPValue *&X) {
285 return m_Intrinsic<Intrinsic::vector_splice_left>(
286 Ops: m_Poison(), Ops: m_VPValue(V&: X), Ops: m_Specific(VPV: EVL));
287 },
288 Build: [&Plan, &EVL](auto *X) {
289 return new VPWidenIntrinsicRecipe(
290 Intrinsic::vector_splice_left,
291 {Plan.getPoison(Ty: X->getScalarType()), X, EVL}, X->getScalarType(),
292 {}, {}, X->getDebugLoc());
293 });
294
295 // Fold the following splice patterns:
296 // splice.right(splice.left(poison, x, evl), poison, evl) -> x
297 // vector.reverse(splice.left(poison, x, evl)) -> vp.reverse(x, true, evl)
298 // splice.right(vector.reverse(x), poison, evl) -> vp.reverse(x, true, evl)
299 for (VPUser *U : vputils::collectUsersRecursively(V: EVL)) {
300 auto *R = cast<VPRecipeBase>(Val: U);
301 // Remove potentially dead left splices from the transform above.
302 if (match(U, P: m_Intrinsic<Intrinsic::vector_splice_left>()) &&
303 R->getVPSingleValue()->getNumUsers() == 0) {
304 OldRecipes.push_back(Elt: R);
305 continue;
306 }
307
308 VPValue *X;
309 if (match(U, P: m_Intrinsic<Intrinsic::vector_splice_right>(
310 Ops: m_Intrinsic<Intrinsic::vector_splice_left>(
311 Ops: m_Poison(), Ops: m_VPValue(V&: X), Ops: m_Specific(VPV: EVL)),
312 Ops: m_Poison(), Ops: m_Specific(VPV: EVL)))) {
313 R->getVPSingleValue()->replaceAllUsesWith(New: X);
314 OldRecipes.push_back(Elt: R);
315 continue;
316 }
317
318 if (!match(U,
319 P: m_CombineOr(
320 Ps: m_Reverse(Op0: m_Intrinsic<Intrinsic::vector_splice_left>(
321 Ops: m_Poison(), Ops: m_VPValue(V&: X), Ops: m_Specific(VPV: EVL))),
322 Ps: m_Intrinsic<Intrinsic::vector_splice_right>(
323 Ops: m_Reverse(Op0: m_VPValue(V&: X)), Ops: m_Poison(), Ops: m_Specific(VPV: EVL)))))
324 continue;
325
326 auto *VPReverse = new VPWidenIntrinsicRecipe(
327 Intrinsic::experimental_vp_reverse, {X, Plan.getTrue(), EVL},
328 X->getScalarType(), {}, {}, R->getDebugLoc());
329 VPReverse->insertBefore(InsertPos: R);
330 R->getVPSingleValue()->replaceAllUsesWith(New: VPReverse);
331 OldRecipes.push_back(Elt: R);
332 }
333
334 for (VPRecipeBase *R : reverse(C&: OldRecipes)) {
335 SmallVector<VPValue *> PossiblyDead(R->operands());
336 R->eraseFromParent();
337 for (VPValue *Op : PossiblyDead)
338 vputils::recursivelyDeleteDeadRecipes(V: Op);
339 }
340}
341
342/// After replacing the canonical IV with a EVL-based IV, fixup recipes that use
343/// VF to use the EVL instead to avoid incorrect updates on the penultimate
344/// iteration.
345static void fixupVFUsersForEVL(VPlan &Plan, VPValue &EVL) {
346 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();
347 VPBasicBlock *Header = LoopRegion->getEntryBasicBlock();
348
349 // EVL is i32 but VF/VFxUF are IdxTy. Convert as needed.
350 VPValue *EVLAsIdx =
351 VPBuilder::getToInsertAfter(R: EVL.getDefiningRecipe())
352 .createScalarZExtOrTrunc(Op: &EVL, ResultTy: Plan.getVF().getScalarType(),
353 DL: DebugLoc::getUnknown());
354
355 assert(all_of(Plan.getVF().users(),
356 [&Plan](VPUser *U) {
357 auto IsAllowedUser =
358 IsaPred<VPVectorEndPointerRecipe, VPScalarIVStepsRecipe,
359 VPWidenIntOrFpInductionRecipe,
360 VPWidenMemIntrinsicRecipe>;
361 if (match(U, m_Trunc(m_Specific(&Plan.getVF()))))
362 return all_of(cast<VPSingleDefRecipe>(U)->users(),
363 IsAllowedUser);
364 return IsAllowedUser(U);
365 }) &&
366 "User of VF that we can't transform to EVL.");
367 Plan.getVF().replaceUsesWithIf(New: EVLAsIdx, ShouldReplace: [](VPUser &U, unsigned Idx) {
368 return isa<VPWidenIntOrFpInductionRecipe, VPScalarIVStepsRecipe>(Val: U);
369 });
370
371 assert(all_of(Plan.getVFxUF().users(),
372 match_fn(m_CombineOr(
373 m_c_Add(m_Specific(LoopRegion->getCanonicalIV()),
374 m_Specific(&Plan.getVFxUF())),
375 m_Isa<VPWidenPointerInductionRecipe>()))) &&
376 "Only users of VFxUF should be VPWidenPointerInductionRecipe and the "
377 "increment of the canonical induction.");
378 Plan.getVFxUF().replaceUsesWithIf(New: EVLAsIdx, ShouldReplace: [](VPUser &U, unsigned Idx) {
379 // Only replace uses in VPWidenPointerInductionRecipe; The increment of the
380 // canonical induction must not be updated.
381 return isa<VPWidenPointerInductionRecipe>(Val: U);
382 });
383
384 // Create a scalar phi to track the previous EVL if fixed-order recurrence is
385 // contained.
386 bool ContainsFORs =
387 any_of(Range: Header->phis(), P: IsaPred<VPFirstOrderRecurrencePHIRecipe>);
388 if (ContainsFORs) {
389 // TODO: Use VPInstruction::ExplicitVectorLength to get maximum EVL.
390 VPValue *MaxEVL = &Plan.getVF();
391 // Emit VPScalarCastRecipe in preheader if VF is not a 32 bits integer.
392 VPBuilder Builder(LoopRegion->getPreheaderVPBB());
393 MaxEVL = Builder.createScalarZExtOrTrunc(
394 Op: MaxEVL, ResultTy: Type::getInt32Ty(C&: Plan.getContext()), DL: DebugLoc::getUnknown());
395
396 Builder.setInsertPoint(TheBB: Header, IP: Header->getFirstNonPhi());
397 VPValue *PrevEVL = Builder.createScalarPhi(
398 IncomingValues: {MaxEVL, &EVL}, DL: DebugLoc::getUnknown(), Name: "prev.evl");
399
400 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
401 Range: vp_depth_first_deep(G: Plan.getVectorLoopRegion()->getEntry()))) {
402 for (VPRecipeBase &R : *VPBB) {
403 VPValue *V1, *V2;
404 if (!match(V: &R,
405 P: m_VPInstruction<VPInstruction::FirstOrderRecurrenceSplice>(
406 Ops: m_VPValue(V&: V1), Ops: m_VPValue(V&: V2))))
407 continue;
408 VPValue *Imm = Plan.getOrAddLiveIn(
409 V: ConstantInt::getSigned(Ty: Type::getInt32Ty(C&: Plan.getContext()), V: -1));
410 VPWidenIntrinsicRecipe *VPSplice = new VPWidenIntrinsicRecipe(
411 Intrinsic::experimental_vp_splice,
412 {V1, V2, Imm, Plan.getTrue(), PrevEVL, &EVL},
413 R.getVPSingleValue()->getScalarType(), {}, {}, R.getDebugLoc());
414 VPSplice->insertBefore(InsertPos: &R);
415 R.getVPSingleValue()->replaceAllUsesWith(New: VPSplice);
416 }
417 }
418 }
419
420 VPValue *HeaderMask = LoopRegion->getHeaderMask();
421 if (!HeaderMask)
422 return;
423
424 // Ensure that any reduction that uses a select to mask off tail lanes does so
425 // in the vector loop, not the middle block, since EVL tail folding can have
426 // tail elements in the penultimate iteration.
427 assert(all_of(*Plan.getMiddleBlock(), [&Plan, HeaderMask](VPRecipeBase &R) {
428 if (match(&R, m_ComputeReductionResult(m_Select(m_Specific(HeaderMask),
429 m_VPValue(), m_VPValue()))))
430 return R.getOperand(0)->getDefiningRecipe()->getRegion() ==
431 Plan.getVectorLoopRegion();
432 return true;
433 }));
434
435 // Replace the abstract header mask with a mask equivalent to predicating by
436 // EVL: icmp ult step-vector, EVL
437 VPRecipeBase *EVLR = EVL.getDefiningRecipe();
438 VPBuilder Builder(EVLR->getParent(), std::next(x: EVLR->getIterator()));
439 Type *EVLType = EVL.getScalarType();
440 VPValue *EVLMask = Builder.createICmp(
441 Pred: CmpInst::ICMP_ULT,
442 A: Builder.createNaryOp(Opcode: VPInstruction::StepVector, Operands: {}, ResultTy: EVLType), B: &EVL);
443 HeaderMask->replaceAllUsesWith(New: EVLMask);
444}
445
446/// Converts a tail folded vector loop region to step by
447/// VPInstruction::ExplicitVectorLength elements instead of VF elements each
448/// iteration.
449///
450/// - Add a VPCurrentIterationPHIRecipe and related recipes to \p Plan and
451/// replaces all uses of the canonical IV except for the canonical IV
452/// increment with a VPCurrentIterationPHIRecipe. The canonical IV is used
453/// only for loop iterations counting after this transformation.
454///
455/// - The header mask is replaced with a header mask based on the EVL.
456///
457/// - Plans with FORs have a new phi added to keep track of the EVL of the
458/// previous iteration, and VPFirstOrderRecurrencePHIRecipes are replaced with
459/// @llvm.vp.splice.
460///
461/// The function uses the following definitions:
462/// %StartV is the canonical induction start value.
463///
464/// The function adds the following recipes:
465///
466/// vector.ph:
467/// ...
468///
469/// vector.body:
470/// ...
471/// %CurrentIter = CURRENT-ITERATION-PHI [ %StartV, %vector.ph ],
472/// [ %NextIter, %vector.body ]
473/// %AVL = phi [ trip-count, %vector.ph ], [ %NextAVL, %vector.body ]
474/// %VPEVL = EXPLICIT-VECTOR-LENGTH %AVL
475/// ...
476/// %OpEVL = cast i32 %VPEVL to IVSize
477/// %NextIter = add IVSize %OpEVL, %CurrentIter
478/// %NextAVL = sub IVSize nuw %AVL, %OpEVL
479/// ...
480///
481/// If MaxSafeElements is provided, the function adds the following recipes:
482/// vector.ph:
483/// ...
484///
485/// vector.body:
486/// ...
487/// %CurrentIter = CURRENT-ITERATION-PHI [ %StartV, %vector.ph ],
488/// [ %NextIter, %vector.body ]
489/// %AVL = phi [ trip-count, %vector.ph ], [ %NextAVL, %vector.body ]
490/// %cmp = cmp ult %AVL, MaxSafeElements
491/// %SAFE_AVL = select %cmp, %AVL, MaxSafeElements
492/// %VPEVL = EXPLICIT-VECTOR-LENGTH %SAFE_AVL
493/// ...
494/// %OpEVL = cast i32 %VPEVL to IVSize
495/// %NextIter = add IVSize %OpEVL, %CurrentIter
496/// %NextAVL = sub IVSize nuw %AVL, %OpEVL
497/// ...
498///
499void VPlanTransforms::addExplicitVectorLength(
500 VPlan &Plan, const std::optional<unsigned> &MaxSafeElements) {
501 if (Plan.hasScalarVFOnly())
502 return;
503 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();
504 VPBasicBlock *Header = LoopRegion->getEntryBasicBlock();
505
506 auto *CanonicalIV = LoopRegion->getCanonicalIV();
507 auto *CanIVTy = LoopRegion->getCanonicalIVType();
508 VPValue *StartV = Plan.getZero(Ty: CanIVTy);
509 auto *CanonicalIVIncrement = LoopRegion->getOrCreateCanonicalIVIncrement();
510
511 // Create the CurrentIteration recipe in the vector loop.
512 auto *CurrentIteration =
513 new VPCurrentIterationPHIRecipe(StartV, DebugLoc::getUnknown());
514 CurrentIteration->insertBefore(BB&: *Header, IP: Header->begin());
515 VPBuilder Builder(Header, Header->getFirstNonPhi());
516 // Create the AVL (application vector length), starting from TC -> 0 in steps
517 // of EVL.
518 VPPhi *AVLPhi = Builder.createScalarPhi(
519 IncomingValues: {Plan.getTripCount()}, DL: DebugLoc::getCompilerGenerated(), Name: "avl");
520 VPValue *AVL = AVLPhi;
521
522 if (MaxSafeElements) {
523 // Support for MaxSafeDist for correct loop emission.
524 VPValue *AVLSafe = Plan.getConstantInt(Ty: CanIVTy, Val: *MaxSafeElements);
525 VPValue *Cmp = Builder.createICmp(Pred: ICmpInst::ICMP_ULT, A: AVL, B: AVLSafe);
526 AVL = Builder.createSelect(Cond: Cmp, TrueVal: AVL, FalseVal: AVLSafe, DL: DebugLoc::getUnknown(),
527 Name: "safe_avl");
528 }
529 auto *VPEVL = Builder.createNaryOp(Opcode: VPInstruction::ExplicitVectorLength, Operands: AVL,
530 DL: DebugLoc::getUnknown(), Name: "evl");
531
532 Builder.setInsertPoint(CanonicalIVIncrement);
533 VPValue *OpVPEVL = VPEVL;
534
535 OpVPEVL = Builder.createScalarZExtOrTrunc(
536 Op: OpVPEVL, ResultTy: CanIVTy, DL: CanonicalIVIncrement->getDebugLoc());
537
538 auto *NextIter = Builder.createAdd(
539 LHS: OpVPEVL, RHS: CurrentIteration, DL: CanonicalIVIncrement->getDebugLoc(),
540 Name: "current.iteration.next", WrapFlags: CanonicalIVIncrement->getNoWrapFlags());
541 CurrentIteration->addBackedgeValue(V: NextIter);
542
543 VPValue *NextAVL =
544 Builder.createSub(LHS: AVLPhi, RHS: OpVPEVL, DL: DebugLoc::getCompilerGenerated(),
545 Name: "avl.next", WrapFlags: {/*NUW=*/true, /*NSW=*/false});
546 AVLPhi->addIncoming(IncomingV: NextAVL);
547
548 fixupVFUsersForEVL(Plan, EVL&: *VPEVL);
549 removeDeadRecipes(Plan);
550
551 // Replace all uses of the canonical IV with VPCurrentIterationPHIRecipe
552 // except for the canonical IV increment.
553 CanonicalIV->replaceUsesWithIf(New: CurrentIteration,
554 ShouldReplace: [CanonicalIVIncrement](VPUser &U, unsigned) {
555 return &U != CanonicalIVIncrement;
556 });
557 // TODO: support unroll factor > 1.
558 Plan.setUF(1);
559}
560
561void VPlanTransforms::convertToVariableLengthStep(VPlan &Plan) {
562 // Find the vector loop entry by locating VPCurrentIterationPHIRecipe.
563 // There should be only one VPCurrentIteration in the entire plan.
564 VPCurrentIterationPHIRecipe *CurrentIteration = nullptr;
565
566 for (VPBasicBlock *VPBB : VPBlockUtils::blocksAs<VPBasicBlock>(
567 Range: vp_depth_first_shallow(G: Plan.getEntry())))
568 for (VPRecipeBase &R : VPBB->phis())
569 if (auto *PhiR = dyn_cast<VPCurrentIterationPHIRecipe>(Val: &R)) {
570 assert(!CurrentIteration &&
571 "Found multiple CurrentIteration. Only one expected");
572 CurrentIteration = PhiR;
573 }
574
575 // Early return if it is not variable-length stepping.
576 if (!CurrentIteration)
577 return;
578
579 VPBasicBlock *HeaderVPBB = CurrentIteration->getParent();
580 VPValue *CurrentIterationIncr = CurrentIteration->getBackedgeValue();
581
582 // Convert CurrentIteration to concrete recipe.
583 auto *ScalarR =
584 VPBuilder(CurrentIteration)
585 .createScalarPhi(
586 IncomingValues: {CurrentIteration->getStartValue(), CurrentIterationIncr},
587 DL: CurrentIteration->getDebugLoc(), Name: "current.iteration.iv");
588 CurrentIteration->replaceAllUsesWith(New: ScalarR);
589 CurrentIteration->eraseFromParent();
590
591 // Replace CanonicalIVInc with CurrentIteration increment if it exists.
592 auto *CanonicalIV = cast<VPPhi>(Val: &*HeaderVPBB->begin());
593 if (auto *CanIVInc = findUserOf(
594 V: CanonicalIV, P: m_c_Add(Op0: m_VPValue(), Op1: m_Specific(VPV: &Plan.getVFxUF())))) {
595 cast<VPInstruction>(Val: CanIVInc)->replaceAllUsesWith(New: CurrentIterationIncr);
596 CanIVInc->eraseFromParent();
597 }
598}
599
600void VPlanTransforms::convertEVLExitCond(VPlan &Plan) {
601 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();
602 if (!LoopRegion)
603 return;
604 VPBasicBlock *Header = LoopRegion->getEntryBasicBlock();
605 if (Header->empty())
606 return;
607 // The EVL IV is always at the beginning.
608 auto *EVLPhi = dyn_cast<VPCurrentIterationPHIRecipe>(Val: &Header->front());
609 if (!EVLPhi)
610 return;
611
612 // Bail if not an EVL tail folded loop.
613 VPValue *AVL;
614 if (!match(V: EVLPhi->getBackedgeValue(),
615 P: m_c_Add(Op0: m_ZExtOrSelf(Op0: m_EVL(Op0: m_VPValue(V&: AVL))), Op1: m_Specific(VPV: EVLPhi))))
616 return;
617
618 // The AVL may be capped to a safe distance.
619 VPValue *SafeAVL, *UnsafeAVL;
620 if (match(V: AVL,
621 P: m_Select(Op0: m_SpecificICmp(MatchPred: CmpInst::ICMP_ULT, Op0: m_VPValue(V&: UnsafeAVL),
622 Op1: m_VPValue(V&: SafeAVL)),
623 Op1: m_Deferred(V: UnsafeAVL), Op2: m_Deferred(V: SafeAVL))))
624 AVL = UnsafeAVL;
625
626 VPValue *AVLNext;
627 [[maybe_unused]] bool FoundAVLNext =
628 match(V: AVL, P: m_VPInstruction<Instruction::PHI>(
629 Ops: m_Specific(VPV: Plan.getTripCount()), Ops: m_VPValue(V&: AVLNext)));
630 assert(FoundAVLNext && "Didn't find AVL backedge?");
631
632 VPBasicBlock *Latch = LoopRegion->getExitingBasicBlock();
633 auto *LatchBr = cast<VPInstruction>(Val: Latch->getTerminator());
634 if (match(V: LatchBr, P: m_BranchOnCond(Op0: m_True())))
635 return;
636
637 VPValue *CanIVInc;
638 [[maybe_unused]] bool FoundIncrement = match(
639 V: LatchBr,
640 P: m_BranchOnCond(Op0: m_SpecificCmp(MatchPred: CmpInst::ICMP_EQ, Op0: m_VPValue(V&: CanIVInc),
641 Op1: m_Specific(VPV: &Plan.getVectorTripCount()))));
642 assert(FoundIncrement &&
643 match(CanIVInc, m_Add(m_Specific(LoopRegion->getCanonicalIV()),
644 m_Specific(&Plan.getVFxUF()))) &&
645 "Expected BranchOnCond with ICmp comparing CanIV + VFxUF with vector "
646 "trip count");
647
648 Type *AVLTy = AVLNext->getScalarType();
649 VPBuilder Builder(LatchBr);
650 LatchBr->setOperand(
651 I: 0, New: Builder.createICmp(Pred: CmpInst::ICMP_EQ, A: AVLNext, B: Plan.getZero(Ty: AVLTy)));
652}
653