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(
378 New: EVLAsIdx, ShouldReplace: IsaPred<VPWidenIntOrFpInductionRecipe, VPScalarIVStepsRecipe>);
379
380 // Only replace uses in VPWidenPointerInductionRecipe; The increment of the
381 // canonical induction must not be updated.
382 Plan.getVFxUF().replaceUsesWithIf(New: EVLAsIdx,
383 ShouldReplace: IsaPred<VPWidenPointerInductionRecipe>);
384
385 // Create a scalar phi to track the previous EVL if fixed-order recurrence is
386 // contained.
387 bool ContainsFORs =
388 any_of(Range: Header->phis(), P: IsaPred<VPFirstOrderRecurrencePHIRecipe>);
389 if (ContainsFORs) {
390 // TODO: Use VPInstruction::ExplicitVectorLength to get maximum EVL.
391 VPValue *MaxEVL = &Plan.getVF();
392 // Emit VPScalarCastRecipe in preheader if VF is not a 32 bits integer.
393 VPBuilder Builder(LoopRegion->getPreheaderVPBB());
394 MaxEVL = Builder.createScalarZExtOrTrunc(
395 Op: MaxEVL, ResultTy: Type::getInt32Ty(C&: Plan.getContext()), DL: DebugLoc::getUnknown());
396
397 Builder.setInsertPoint(TheBB: Header, IP: Header->getFirstNonPhi());
398 VPValue *PrevEVL = Builder.createScalarPhi(
399 IncomingValues: {MaxEVL, &EVL}, DL: DebugLoc::getUnknown(), Name: "prev.evl");
400
401 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
402 Range: vp_depth_first_deep(G: Plan.getVectorLoopRegion()->getEntry()))) {
403 for (VPRecipeBase &R : *VPBB) {
404 VPValue *V1, *V2;
405 if (!match(V: &R,
406 P: m_VPInstruction<VPInstruction::FirstOrderRecurrenceSplice>(
407 Ops: m_VPValue(V&: V1), Ops: m_VPValue(V&: V2))))
408 continue;
409 VPValue *Imm = Plan.getOrAddLiveIn(
410 V: ConstantInt::getSigned(Ty: Type::getInt32Ty(C&: Plan.getContext()), V: -1));
411 VPWidenIntrinsicRecipe *VPSplice = new VPWidenIntrinsicRecipe(
412 Intrinsic::experimental_vp_splice,
413 {V1, V2, Imm, Plan.getTrue(), PrevEVL, &EVL},
414 R.getVPSingleValue()->getScalarType(), {}, {}, R.getDebugLoc());
415 VPSplice->insertBefore(InsertPos: &R);
416 R.getVPSingleValue()->replaceAllUsesWith(New: VPSplice);
417 }
418 }
419 }
420
421 VPValue *HeaderMask = LoopRegion->getHeaderMask();
422 if (!HeaderMask)
423 return;
424
425 // Ensure that any reduction that uses a select to mask off tail lanes does so
426 // in the vector loop, not the middle block, since EVL tail folding can have
427 // tail elements in the penultimate iteration.
428 assert(all_of(*Plan.getMiddleBlock(), [&Plan, HeaderMask](VPRecipeBase &R) {
429 if (match(&R, m_ComputeReductionResult(m_Select(m_Specific(HeaderMask),
430 m_VPValue(), m_VPValue()))))
431 return R.getOperand(0)->getDefiningRecipe()->getRegion() ==
432 Plan.getVectorLoopRegion();
433 return true;
434 }));
435
436 // Replace the abstract header mask with a mask equivalent to predicating by
437 // EVL: icmp ult step-vector, EVL
438 VPRecipeBase *EVLR = EVL.getDefiningRecipe();
439 VPBuilder Builder(EVLR->getParent(), std::next(x: EVLR->getIterator()));
440 Type *EVLType = EVL.getScalarType();
441 VPValue *EVLMask = Builder.createICmp(
442 Pred: CmpInst::ICMP_ULT,
443 A: Builder.createNaryOp(Opcode: VPInstruction::StepVector, Operands: {}, ResultTy: EVLType), B: &EVL);
444 HeaderMask->replaceAllUsesWith(New: EVLMask);
445}
446
447/// Converts a tail folded vector loop region to step by
448/// VPInstruction::ExplicitVectorLength elements instead of VF elements each
449/// iteration.
450///
451/// - Add a VPCurrentIterationPHIRecipe and related recipes to \p Plan and
452/// replaces all uses of the canonical IV except for the canonical IV
453/// increment with a VPCurrentIterationPHIRecipe. The canonical IV is used
454/// only for loop iterations counting after this transformation.
455///
456/// - The header mask is replaced with a header mask based on the EVL.
457///
458/// - Plans with FORs have a new phi added to keep track of the EVL of the
459/// previous iteration, and VPFirstOrderRecurrencePHIRecipes are replaced with
460/// @llvm.vp.splice.
461///
462/// The function uses the following definitions:
463/// %StartV is the canonical induction start value.
464///
465/// The function adds the following recipes:
466///
467/// vector.ph:
468/// ...
469///
470/// vector.body:
471/// ...
472/// %CurrentIter = CURRENT-ITERATION-PHI [ %StartV, %vector.ph ],
473/// [ %NextIter, %vector.body ]
474/// %AVL = phi [ trip-count, %vector.ph ], [ %NextAVL, %vector.body ]
475/// %VPEVL = EXPLICIT-VECTOR-LENGTH %AVL
476/// ...
477/// %OpEVL = cast i32 %VPEVL to IVSize
478/// %NextIter = add IVSize %OpEVL, %CurrentIter
479/// %NextAVL = sub IVSize nuw %AVL, %OpEVL
480/// ...
481///
482/// If MaxSafeElements is provided, the function adds the following recipes:
483/// vector.ph:
484/// ...
485///
486/// vector.body:
487/// ...
488/// %CurrentIter = CURRENT-ITERATION-PHI [ %StartV, %vector.ph ],
489/// [ %NextIter, %vector.body ]
490/// %AVL = phi [ trip-count, %vector.ph ], [ %NextAVL, %vector.body ]
491/// %cmp = cmp ult %AVL, MaxSafeElements
492/// %SAFE_AVL = select %cmp, %AVL, MaxSafeElements
493/// %VPEVL = EXPLICIT-VECTOR-LENGTH %SAFE_AVL
494/// ...
495/// %OpEVL = cast i32 %VPEVL to IVSize
496/// %NextIter = add IVSize %OpEVL, %CurrentIter
497/// %NextAVL = sub IVSize nuw %AVL, %OpEVL
498/// ...
499///
500void VPlanTransforms::addExplicitVectorLength(
501 VPlan &Plan, const std::optional<unsigned> &MaxSafeElements) {
502 if (Plan.hasScalarVFOnly())
503 return;
504 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();
505 VPBasicBlock *Header = LoopRegion->getEntryBasicBlock();
506
507 auto *CanonicalIV = LoopRegion->getCanonicalIV();
508 auto *CanIVTy = LoopRegion->getCanonicalIVType();
509 VPValue *StartV = Plan.getZero(Ty: CanIVTy);
510 auto *CanonicalIVIncrement = LoopRegion->getOrCreateCanonicalIVIncrement();
511
512 // Create the CurrentIteration recipe in the vector loop.
513 auto *CurrentIteration =
514 new VPCurrentIterationPHIRecipe(StartV, DebugLoc::getUnknown());
515 CurrentIteration->insertBefore(BB&: *Header, IP: Header->begin());
516 VPBuilder Builder(Header, Header->getFirstNonPhi());
517 // Create the AVL (application vector length), starting from TC -> 0 in steps
518 // of EVL.
519 VPPhi *AVLPhi = Builder.createScalarPhi(
520 IncomingValues: {Plan.getTripCount()}, DL: DebugLoc::getCompilerGenerated(), Name: "avl");
521 VPValue *AVL = AVLPhi;
522
523 if (MaxSafeElements) {
524 // Support for MaxSafeDist for correct loop emission.
525 VPValue *AVLSafe = Plan.getConstantInt(Ty: CanIVTy, Val: *MaxSafeElements);
526 VPValue *Cmp = Builder.createICmp(Pred: ICmpInst::ICMP_ULT, A: AVL, B: AVLSafe);
527 AVL = Builder.createSelect(Cond: Cmp, TrueVal: AVL, FalseVal: AVLSafe, DL: DebugLoc::getUnknown(),
528 Name: "safe_avl");
529 }
530 auto *VPEVL = Builder.createNaryOp(Opcode: VPInstruction::ExplicitVectorLength, Operands: AVL,
531 DL: DebugLoc::getUnknown(), Name: "evl");
532
533 Builder.setInsertPoint(CanonicalIVIncrement);
534 VPValue *OpVPEVL = VPEVL;
535
536 OpVPEVL = Builder.createScalarZExtOrTrunc(
537 Op: OpVPEVL, ResultTy: CanIVTy, DL: CanonicalIVIncrement->getDebugLoc());
538
539 auto *NextIter = Builder.createAdd(
540 LHS: OpVPEVL, RHS: CurrentIteration, DL: CanonicalIVIncrement->getDebugLoc(),
541 Name: "current.iteration.next", WrapFlags: CanonicalIVIncrement->getNoWrapFlags());
542 CurrentIteration->addBackedgeValue(V: NextIter);
543
544 VPValue *NextAVL =
545 Builder.createSub(LHS: AVLPhi, RHS: OpVPEVL, DL: DebugLoc::getCompilerGenerated(),
546 Name: "avl.next", WrapFlags: {/*NUW=*/true, /*NSW=*/false});
547 AVLPhi->addIncoming(IncomingV: NextAVL);
548
549 fixupVFUsersForEVL(Plan, EVL&: *VPEVL);
550 removeDeadRecipes(Plan);
551
552 // Replace all uses of the canonical IV with VPCurrentIterationPHIRecipe
553 // except for the canonical IV increment.
554 CanonicalIV->replaceUsesWithIf(New: CurrentIteration,
555 ShouldReplace: not_equal_to(Arg&: CanonicalIVIncrement));
556 // TODO: support unroll factor > 1.
557 Plan.setUF(1);
558}
559
560void VPlanTransforms::convertToVariableLengthStep(VPlan &Plan) {
561 // Find the vector loop entry by locating VPCurrentIterationPHIRecipe.
562 // There should be only one VPCurrentIteration in the entire plan.
563 VPCurrentIterationPHIRecipe *CurrentIteration = nullptr;
564
565 for (VPBasicBlock *VPBB : VPBlockUtils::blocksAs<VPBasicBlock>(
566 Range: vp_depth_first_shallow(G: Plan.getEntry())))
567 for (VPCurrentIterationPHIRecipe &PhiR :
568 make_isa_range<VPCurrentIterationPHIRecipe>(Range: VPBB->phis())) {
569 assert(!CurrentIteration &&
570 "Found multiple CurrentIteration. Only one expected");
571 CurrentIteration = &PhiR;
572 }
573
574 // Early return if it is not variable-length stepping.
575 if (!CurrentIteration)
576 return;
577
578 VPBasicBlock *HeaderVPBB = CurrentIteration->getParent();
579 VPValue *CurrentIterationIncr = CurrentIteration->getBackedgeValue();
580
581 // Convert CurrentIteration to concrete recipe.
582 auto *ScalarR =
583 VPBuilder(CurrentIteration)
584 .createScalarPhi(
585 IncomingValues: {CurrentIteration->getStartValue(), CurrentIterationIncr},
586 DL: CurrentIteration->getDebugLoc(), Name: "current.iteration.iv");
587 CurrentIteration->replaceAllUsesWith(New: ScalarR);
588 CurrentIteration->eraseFromParent();
589
590 // Replace CanonicalIVInc with CurrentIteration increment if it exists.
591 auto *CanonicalIV = cast<VPPhi>(Val: &*HeaderVPBB->begin());
592 if (auto *CanIVInc = findUserOf(
593 V: CanonicalIV, P: m_c_Add(Op0: m_VPValue(), Op1: m_Specific(VPV: &Plan.getVFxUF())))) {
594 cast<VPInstruction>(Val: CanIVInc)->replaceAllUsesWith(New: CurrentIterationIncr);
595 CanIVInc->eraseFromParent();
596 }
597}
598
599void VPlanTransforms::convertEVLExitCond(VPlan &Plan) {
600 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();
601 if (!LoopRegion)
602 return;
603 VPBasicBlock *Header = LoopRegion->getEntryBasicBlock();
604 if (Header->empty())
605 return;
606 // The EVL IV is always at the beginning.
607 auto *EVLPhi = dyn_cast<VPCurrentIterationPHIRecipe>(Val: &Header->front());
608 if (!EVLPhi)
609 return;
610
611 // Bail if not an EVL tail folded loop.
612 VPValue *AVL;
613 if (!match(V: EVLPhi->getBackedgeValue(),
614 P: m_c_Add(Op0: m_ZExtOrSelf(Op0: m_EVL(Op0: m_VPValue(V&: AVL))), Op1: m_Specific(VPV: EVLPhi))))
615 return;
616
617 // The AVL may be capped to a safe distance.
618 VPValue *SafeAVL, *UnsafeAVL;
619 if (match(V: AVL,
620 P: m_Select(Op0: m_SpecificICmp(MatchPred: CmpInst::ICMP_ULT, Op0: m_VPValue(V&: UnsafeAVL),
621 Op1: m_VPValue(V&: SafeAVL)),
622 Op1: m_Deferred(V: UnsafeAVL), Op2: m_Deferred(V: SafeAVL))))
623 AVL = UnsafeAVL;
624
625 VPValue *AVLNext;
626 [[maybe_unused]] bool FoundAVLNext =
627 match(V: AVL, P: m_VPInstruction<Instruction::PHI>(
628 Ops: m_Specific(VPV: Plan.getTripCount()), Ops: m_VPValue(V&: AVLNext)));
629 assert(FoundAVLNext && "Didn't find AVL backedge?");
630
631 VPBasicBlock *Latch = LoopRegion->getExitingBasicBlock();
632 auto *LatchBr = cast<VPInstruction>(Val: Latch->getTerminator());
633 if (match(V: LatchBr, P: m_BranchOnCond(Op0: m_True())))
634 return;
635
636 VPValue *CanIVInc;
637 [[maybe_unused]] bool FoundIncrement = match(
638 V: LatchBr,
639 P: m_BranchOnCond(Op0: m_SpecificCmp(MatchPred: CmpInst::ICMP_EQ, Op0: m_VPValue(V&: CanIVInc),
640 Op1: m_Specific(VPV: &Plan.getVectorTripCount()))));
641 assert(FoundIncrement &&
642 match(CanIVInc, m_Add(m_Specific(LoopRegion->getCanonicalIV()),
643 m_Specific(&Plan.getVFxUF()))) &&
644 "Expected BranchOnCond with ICmp comparing CanIV + VFxUF with vector "
645 "trip count");
646
647 Type *AVLTy = AVLNext->getScalarType();
648 VPBuilder Builder(LatchBr);
649 LatchBr->setOperand(
650 I: 0, New: Builder.createICmp(Pred: CmpInst::ICMP_EQ, A: AVLNext, B: Plan.getZero(Ty: AVLTy)));
651}
652