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