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