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(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 auto Builder = VPBuilder::getToInsertAfter(R: EVL.getDefiningRecipe());
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(IP: Header->begin());
515 VPBuilder Builder(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: not_equal_to(Arg&: CanonicalIVIncrement));
555 // TODO: support unroll factor > 1.
556 Plan.setUF(1);
557}
558
559void VPlanTransforms::convertToVariableLengthStep(VPlan &Plan) {
560 // Find the vector loop entry by locating VPCurrentIterationPHIRecipe.
561 // There should be only one VPCurrentIteration in the entire plan.
562 VPCurrentIterationPHIRecipe *CurrentIteration = nullptr;
563
564 for (VPBasicBlock *VPBB : VPBlockUtils::blocksAs<VPBasicBlock>(
565 Range: vp_depth_first_shallow(G: Plan.getEntry())))
566 for (VPCurrentIterationPHIRecipe &PhiR :
567 make_isa_range<VPCurrentIterationPHIRecipe>(Range: VPBB->phis())) {
568 assert(!CurrentIteration &&
569 "Found multiple CurrentIteration. Only one expected");
570 CurrentIteration = &PhiR;
571 }
572
573 // Early return if it is not variable-length stepping.
574 if (!CurrentIteration)
575 return;
576
577 VPBasicBlock *HeaderVPBB = CurrentIteration->getParent();
578 VPValue *CurrentIterationIncr = CurrentIteration->getBackedgeValue();
579
580 // Convert CurrentIteration to concrete recipe.
581 auto *ScalarR =
582 VPBuilder(CurrentIteration)
583 .createScalarPhi(
584 IncomingValues: {CurrentIteration->getStartValue(), CurrentIterationIncr},
585 DL: CurrentIteration->getDebugLoc(), Name: "current.iteration.iv");
586 CurrentIteration->replaceAllUsesWith(New: ScalarR);
587 CurrentIteration->eraseFromParent();
588
589 // Replace CanonicalIVInc with CurrentIteration increment if it exists.
590 auto *CanonicalIV = cast<VPPhi>(Val: &*HeaderVPBB->begin());
591 if (auto *CanIVInc = findSingleUser<VPInstruction>(
592 V: CanonicalIV, P: m_c_Add(Op0: m_VPValue(), Op1: m_Specific(VPV: &Plan.getVFxUF())))) {
593 CanIVInc->replaceAllUsesWith(New: CurrentIterationIncr);
594 CanIVInc->eraseFromParent();
595 }
596}
597
598void VPlanTransforms::convertEVLExitCond(VPlan &Plan) {
599 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();
600 if (!LoopRegion)
601 return;
602 VPBasicBlock *Header = LoopRegion->getEntryBasicBlock();
603 if (Header->empty())
604 return;
605 // The EVL IV is always at the beginning.
606 auto *EVLPhi = dyn_cast<VPCurrentIterationPHIRecipe>(Val: &Header->front());
607 if (!EVLPhi)
608 return;
609
610 // Bail if not an EVL tail folded loop.
611 VPValue *AVL;
612 if (!match(V: EVLPhi->getBackedgeValue(),
613 P: m_c_Add(Op0: m_ZExtOrSelf(Op0: m_EVL(Op0: m_VPValue(V&: AVL))), Op1: m_Specific(VPV: EVLPhi))))
614 return;
615
616 // The AVL may be capped to a safe distance.
617 VPValue *SafeAVL, *UnsafeAVL;
618 if (match(V: AVL,
619 P: m_Select(Op0: m_SpecificICmp(MatchPred: CmpInst::ICMP_ULT, Op0: m_VPValue(V&: UnsafeAVL),
620 Op1: m_VPValue(V&: SafeAVL)),
621 Op1: m_Deferred(V: UnsafeAVL), Op2: m_Deferred(V: SafeAVL))))
622 AVL = UnsafeAVL;
623
624 VPValue *AVLNext;
625 [[maybe_unused]] bool FoundAVLNext =
626 match(V: AVL, P: m_VPInstruction<Instruction::PHI>(
627 Ops: m_Specific(VPV: Plan.getTripCount()), Ops: m_VPValue(V&: AVLNext)));
628 assert(FoundAVLNext && "Didn't find AVL backedge?");
629
630 VPBasicBlock *Latch = LoopRegion->getExitingBasicBlock();
631 auto *LatchBr = cast<VPInstruction>(Val: Latch->getTerminator());
632 if (match(V: LatchBr, P: m_BranchOnCond(Op0: m_True())))
633 return;
634
635 VPValue *CanIVInc;
636 [[maybe_unused]] bool FoundIncrement = match(
637 V: LatchBr,
638 P: m_BranchOnCond(Op0: m_SpecificCmp(MatchPred: CmpInst::ICMP_EQ, Op0: m_VPValue(V&: CanIVInc),
639 Op1: m_Specific(VPV: &Plan.getVectorTripCount()))));
640 assert(FoundIncrement &&
641 match(CanIVInc, m_Add(m_Specific(LoopRegion->getCanonicalIV()),
642 m_Specific(&Plan.getVFxUF()))) &&
643 "Expected BranchOnCond with ICmp comparing CanIV + VFxUF with vector "
644 "trip count");
645
646 Type *AVLTy = AVLNext->getScalarType();
647 VPBuilder Builder(LatchBr);
648 LatchBr->setOperand(
649 I: 0, New: Builder.createICmp(Pred: CmpInst::ICMP_EQ, A: AVLNext, B: Plan.getZero(Ty: AVLTy)));
650}
651
652void VPlanTransforms::foldPredicateMerge(VPlan &Plan, VPCostContext &CostCtx) {
653 if (Plan.hasScalarVFOnly())
654 return;
655
656 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
657 Range: vp_depth_first_deep(G: Plan.getVectorLoopRegion()))) {
658 for (VPRecipeBase &R : make_early_inc_range(Range&: *VPBB)) {
659 // Wrap in-loop operations and the vp.merge (cleanup tail poison) to
660 // expression recipes since the vp.merge will be optmized out in the
661 // backend.
662 VPValue *True;
663 if (!match(V: &R,
664 P: m_Intrinsic<Intrinsic::vp_merge>(Ops: m_VPValue(), Ops: m_VPValue(V&: True),
665 Ops: m_VPValue(), Ops: m_VPValue())))
666 continue;
667
668 auto *VPMerge = cast<VPWidenIntrinsicRecipe>(Val: &R);
669 VPSingleDefRecipe *InLoopOp =
670 dyn_cast<VPSingleDefRecipe>(Val: VPMerge->getOperand(N: 1));
671 // TODO: Support cmp-select reductions.
672 if (!InLoopOp || !isa<VPWidenRecipe, VPWidenIntrinsicRecipe>(Val: InLoopOp) ||
673 match(R: InLoopOp, P: m_Select(Op0: m_VPValue(), Op1: m_VPValue(), Op2: m_VPValue())))
674 continue;
675
676 // Backend can only fold vp.merge to true operand when 1) vp.merge is the
677 // only user 2) vp.merge and the true operand are in the same block.
678 if (!True->hasOneUse() || VPMerge->getParent() != InLoopOp->getParent())
679 continue;
680
681 // Query TTI to check if vp.merge can be folded.
682 if (any_of(Range: Plan.vectorFactors(), P: [&](ElementCount VF) {
683 return VPMerge->computeCost(VF, Ctx&: CostCtx) != 0;
684 }))
685 continue;
686
687 // Only convert the in-loop operations with tail-folding predication to
688 // expression recipe.
689 if (!all_of(Range: VPMerge->users(), P: [](VPUser *U) {
690 return isa<VPReductionPHIRecipe>(Val: U) ||
691 match(U, P: m_ComputeReductionResult(Op0: m_VPValue()));
692 }))
693 continue;
694
695 auto IP = std::next(x: VPMerge->getIterator());
696 auto *Expr = new VPExpressionRecipe(InLoopOp, VPMerge);
697 Expr->insertBefore(IP);
698 VPMerge->replaceAllUsesWith(New: Expr);
699 }
700 }
701}
702