1//===- VPlanLowering.cpp - VPlan-to-VPlan lowering 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 VPlan-to-VPlan lowering transformations, which
11/// prepare an optimized VPlan for execution.
12///
13//===----------------------------------------------------------------------===//
14
15#include "LoopVectorizationPlanner.h"
16#include "VPlan.h"
17#include "VPlanAnalysis.h"
18#include "VPlanCFG.h"
19#include "VPlanDominatorTree.h"
20#include "VPlanHelpers.h"
21#include "VPlanPatternMatch.h"
22#include "VPlanTransforms.h"
23#include "VPlanUtils.h"
24#include "llvm/ADT/APInt.h"
25#include "llvm/ADT/STLExtras.h"
26#include "llvm/Analysis/IVDescriptors.h"
27#include "llvm/Analysis/LoopAccessAnalysis.h"
28#include "llvm/Analysis/ScalarEvolutionPatternMatch.h"
29#include "llvm/IR/Intrinsics.h"
30#include "llvm/IR/MDBuilder.h"
31#include "llvm/IR/Metadata.h"
32#include "llvm/Support/Casting.h"
33#include "llvm/Support/TypeSize.h"
34#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
35
36using namespace llvm;
37using namespace VPlanPatternMatch;
38using namespace SCEVPatternMatch;
39
40void VPlanTransforms::replaceWideCanonicalIVWithWideIV(
41 VPlan &Plan, ScalarEvolution &SE, const TargetTransformInfo &TTI,
42 TargetTransformInfo::TargetCostKind CostKind, ElementCount VF,
43 unsigned UF) {
44 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();
45 if (!LoopRegion)
46 return;
47
48 auto *WideCanIV =
49 findUserOf<VPWidenCanonicalIVRecipe>(V: LoopRegion->getCanonicalIV());
50 if (!WideCanIV)
51 return;
52
53 Type *CanIVTy = LoopRegion->getCanonicalIVType();
54
55 // Replace the wide canonical IV with a scalar-iv-steps over the canonical
56 // IV.
57 if (Plan.hasScalarVFOnly() || vputils::onlyFirstLaneUsed(Def: WideCanIV)) {
58 VPBuilder Builder(WideCanIV);
59 WideCanIV->replaceAllUsesWith(New: vputils::createScalarIVSteps(
60 Plan, Kind: InductionDescriptor::IK_IntInduction, InductionOpcode: Instruction::Add, FPBinOp: nullptr,
61 TruncI: nullptr, StartV: Plan.getZero(Ty: CanIVTy), Step: Plan.getConstantInt(Ty: CanIVTy, Val: 1),
62 DL: WideCanIV->getDebugLoc(), Builder,
63 Flags: {static_cast<bool>(WideCanIV->getNoWrapFlags().HasNUW), false}));
64 WideCanIV->eraseFromParent();
65 return;
66 }
67
68 if (vputils::onlyScalarValuesUsed(Def: WideCanIV))
69 return;
70
71 // If a canonical VPWidenIntOrFpInductionRecipe already produces vector lanes
72 // in the header, reuse it instead of introducing another wide induction phi.
73 VPBasicBlock *Header = LoopRegion->getEntryBasicBlock();
74 for (VPRecipeBase &Phi : Header->phis()) {
75 VPWidenIntOrFpInductionRecipe *WidenIV;
76 if (!match(V: &Phi, P: m_CanonicalWidenIV(V&: WidenIV)))
77 continue;
78 // The reused wide IV feeds the header mask, whose lanes may extend past
79 // the trip count; drop flags that only hold inside the scalar loop.
80 WidenIV->dropPoisonGeneratingFlags();
81 WideCanIV->replaceAllUsesWith(New: WidenIV);
82 WideCanIV->eraseFromParent();
83 return;
84 }
85
86 // Introduce a new VPWidenIntOrFpInductionRecipe if profitable.
87 auto *VecTy = VectorType::get(ElementType: CanIVTy, EC: VF);
88 InstructionCost BroadcastCost = TTI.getShuffleCost(
89 Kind: TargetTransformInfo::SK_Broadcast, DstTy: VecTy, SrcTy: VecTy, CostKind);
90 InstructionCost PHICost = TTI.getCFInstrCost(Opcode: Instruction::PHI, CostKind);
91 if (PHICost > BroadcastCost)
92 return;
93
94 // Bail out if the additional wide induction phi increase the expected spill
95 // cost.
96 VPRegisterUsage UnrolledBase =
97 calculateRegisterUsageForPlan(Plan, VFs: VF, TTI)[0];
98 for (unsigned &NumUsers : make_second_range(c&: UnrolledBase.MaxLocalUsers))
99 NumUsers *= UF;
100 unsigned RegClass = TTI.getRegisterClassForType(/*Vector=*/true, Ty: VecTy);
101 VPRegisterUsage Projected = UnrolledBase;
102 Projected.MaxLocalUsers[RegClass] += TTI.getRegUsageForType(Ty: VecTy);
103 if (Projected.spillCost(TTI, CostKind) >
104 UnrolledBase.spillCost(TTI, CostKind))
105 return;
106
107 InductionDescriptor ID =
108 InductionDescriptor::getCanonicalIntInduction(Ty: CanIVTy, SE);
109 VPValue *StepV = Plan.getConstantInt(Ty: CanIVTy, Val: 1);
110 auto *NewWideIV = new VPWidenIntOrFpInductionRecipe(
111 /*IV=*/nullptr, Plan.getZero(Ty: CanIVTy), StepV, &Plan.getVF(), ID,
112 WideCanIV->getNoWrapFlags(), WideCanIV->getDebugLoc());
113 NewWideIV->insertBefore(InsertPos: &*Header->getFirstNonPhi());
114 WideCanIV->replaceAllUsesWith(New: NewWideIV);
115 WideCanIV->eraseFromParent();
116}
117
118// Add a VPActiveLaneMaskPHIRecipe and related recipes to \p Plan and replace
119// the loop terminator with a branch-on-cond recipe with the negated
120// wide-active-lane-mask as operand. Note that this turns the loop into an
121// uncountable one. Only the existing terminator is replaced, all other existing
122// recipes/users remain unchanged, except for poison-generating flags being
123// dropped from the canonical IV increment. Return the created
124// VPActiveLaneMaskPHIRecipe.
125//
126// The function adds the following recipes:
127//
128// vector.ph:
129// %EntryInc = canonical-iv-increment-for-part CanonicalIVStart
130// %EntryALM = wide-active-lane-mask %EntryInc, TC
131// %EntryALMPart = extract-vector-for-part %EntryALM, ir<0>
132//
133// vector.body:
134// ...
135// %P = active-lane-mask-phi [ %EntryALMPart, %vector.ph ],
136// [ %ALMPart, %vector.body ]
137// ...
138// %InLoopInc = canonical-iv-increment-for-part CanonicalIVIncrement
139// %ALM = wide-active-lane-mask %InLoopInc, TC
140// %ALMPart = extract-vector-for-part %ALM, ir<0>
141// %Negated = Not %ALMPart
142// branch-on-cond %Negated
143//
144static VPActiveLaneMaskPHIRecipe *
145addVPLaneMaskPhiAndUpdateExitBranch(VPlan &Plan) {
146 VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
147 VPBasicBlock *EB = TopRegion->getExitingBasicBlock();
148 VPValue *StartV = Plan.getZero(Ty: TopRegion->getCanonicalIVType());
149 auto *CanonicalIVIncrement = TopRegion->getOrCreateCanonicalIVIncrement();
150 // TODO: Check if dropping the flags is needed.
151 TopRegion->clearCanonicalIVNUW(Increment: CanonicalIVIncrement);
152 DebugLoc DL = CanonicalIVIncrement->getDebugLoc();
153 auto *VecPreheader = Plan.getVectorPreheader();
154 VPBuilder Builder(VecPreheader);
155 VPValue *TC = Plan.getTripCount();
156
157 // Create the wide active lane mask instruction in the VPlan preheader.
158 VPValue *ALMMultiplier =
159 Plan.getConstantInt(Ty: TopRegion->getCanonicalIVType(), Val: 1);
160 auto *EntryALM = Builder.createNaryOp(Opcode: VPInstruction::WideActiveLaneMask,
161 Operands: {StartV, TC, ALMMultiplier}, DL,
162 Name: "active.lane.mask.entry");
163 EntryALM = Builder.createNaryOp(Opcode: VPInstruction::ExtractVectorForPart,
164 Operands: {EntryALM, Plan.getConstantInt(BitWidth: 64, Val: 0)}, DL,
165 Name: "extract.entry.alm.part");
166
167 // Now create the ActiveLaneMaskPhi recipe in the main loop using the
168 // preheader WideActiveLaneMask instruction.
169 auto *LaneMaskPhi =
170 new VPActiveLaneMaskPHIRecipe(EntryALM, DebugLoc::getUnknown());
171 auto *HeaderVPBB = TopRegion->getEntryBasicBlock();
172 LaneMaskPhi->insertBefore(BB&: *HeaderVPBB, IP: HeaderVPBB->begin());
173
174 // Create the active lane mask for the next iteration of the loop before the
175 // original terminator.
176 VPRecipeBase *OriginalTerminator = EB->getTerminator();
177 Builder.setInsertPoint(OriginalTerminator);
178 auto *ALM = Builder.createNaryOp(Opcode: VPInstruction::WideActiveLaneMask,
179 Operands: {CanonicalIVIncrement, TC, ALMMultiplier},
180 DL, Name: "active.lane.mask.next");
181 ALM = Builder.createNaryOp(Opcode: VPInstruction::ExtractVectorForPart,
182 Operands: {ALM, Plan.getConstantInt(BitWidth: 64, Val: 0)}, DL,
183 Name: "extract.next.alm.part");
184 LaneMaskPhi->addBackedgeValue(V: ALM);
185
186 // Replace the original terminator with BranchOnCond. We have to invert the
187 // mask here because a true condition means jumping to the exit block.
188 auto *NotMask = Builder.createNot(Operand: ALM, DL);
189 Builder.createNaryOp(Opcode: VPInstruction::BranchOnCond, Operands: {NotMask}, DL);
190 OriginalTerminator->eraseFromParent();
191 return LaneMaskPhi;
192}
193
194void VPlanTransforms::materializeHeaderMask(
195 VPlan &Plan, bool UseActiveLaneMask, bool UseActiveLaneMaskForControlFlow) {
196 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();
197 VPValue *HeaderMask = LoopRegion->getUsedHeaderMask();
198 if (!HeaderMask)
199 return;
200
201 if (UseActiveLaneMaskForControlFlow) {
202 HeaderMask->replaceAllUsesWith(New: addVPLaneMaskPhiAndUpdateExitBranch(Plan));
203 return;
204 }
205
206 VPBasicBlock *Header = LoopRegion->getEntryBasicBlock();
207 VPBuilder Builder(Header, Header->getFirstNonPhi());
208 auto *WideCanonicalIV = Builder.insert(R: new VPWidenCanonicalIVRecipe(
209 LoopRegion->getCanonicalIV(),
210 VPIRFlags::WrapFlagsTy(/*HasNUW=*/true, /*HasNSW=*/false)));
211 VPValue *Mask;
212 if (UseActiveLaneMask) {
213 Mask = Builder.createNaryOp(Opcode: VPInstruction::ActiveLaneMask,
214 Operands: {WideCanonicalIV, Plan.getTripCount()}, DL: nullptr,
215 Name: "active.lane.mask");
216 } else {
217 Mask = Builder.createICmp(Pred: CmpInst::ICMP_ULE, A: WideCanonicalIV,
218 B: Plan.getOrCreateBackedgeTakenCount());
219 }
220 HeaderMask->replaceAllUsesWith(New: Mask);
221}
222
223/// Expand a VPWidenIntOrFpInduction into executable recipes, for the initial
224/// value, phi and backedge value. In the following example:
225///
226/// vector.ph:
227/// Successor(s): vector loop
228///
229/// <x1> vector loop: {
230/// vector.body:
231/// WIDEN-INDUCTION %i = phi %start, %step, %vf
232/// ...
233/// EMIT branch-on-count ...
234/// No successors
235/// }
236///
237/// WIDEN-INDUCTION will get expanded to:
238///
239/// vector.ph:
240/// ...
241/// vp<%induction.start> = ...
242/// vp<%induction.increment> = ...
243///
244/// Successor(s): vector loop
245///
246/// <x1> vector loop: {
247/// vector.body:
248/// ir<%i> = WIDEN-PHI vp<%induction.start>, vp<%vec.ind.next>
249/// ...
250/// vp<%vec.ind.next> = add ir<%i>, vp<%induction.increment>
251/// EMIT branch-on-count ...
252/// No successors
253/// }
254static void
255expandVPWidenIntOrFpInduction(VPWidenIntOrFpInductionRecipe *WidenIVR) {
256 VPlan *Plan = WidenIVR->getParent()->getPlan();
257 VPValue *Start = WidenIVR->getStartValue();
258 VPValue *Step = WidenIVR->getStepValue();
259 VPValue *VF = WidenIVR->getVFValue();
260 DebugLoc DL = WidenIVR->getDebugLoc();
261
262 // The value from the original loop to which we are mapping the new induction
263 // variable.
264 Type *Ty = WidenIVR->getScalarType();
265
266 const InductionDescriptor &ID = WidenIVR->getInductionDescriptor();
267 Instruction::BinaryOps AddOp;
268 Instruction::BinaryOps MulOp;
269 VPIRFlags Flags = *WidenIVR;
270 if (ID.getKind() == InductionDescriptor::IK_IntInduction) {
271 AddOp = Instruction::Add;
272 MulOp = Instruction::Mul;
273 } else {
274 AddOp = ID.getInductionOpcode();
275 MulOp = Instruction::FMul;
276 }
277
278 // If the phi is truncated, truncate the start and step values.
279 VPBuilder Builder(Plan->getVectorPreheader());
280 Type *StepTy = Step->getScalarType();
281 if (Ty->getScalarSizeInBits() < StepTy->getScalarSizeInBits()) {
282 assert(StepTy->isIntegerTy() && "Truncation requires an integer type");
283 Step = Builder.createScalarCast(Opcode: Instruction::Trunc, Op: Step, ResultTy: Ty, DL);
284 Start = Builder.createScalarCast(Opcode: Instruction::Trunc, Op: Start, ResultTy: Ty, DL);
285 StepTy = Ty;
286 }
287
288 // Construct the initial value of the vector IV in the vector loop preheader.
289 Type *IVIntTy =
290 IntegerType::get(C&: Plan->getContext(), NumBits: StepTy->getScalarSizeInBits());
291 VPValue *Init = Builder.createNaryOp(Opcode: VPInstruction::StepVector, Operands: {}, ResultTy: IVIntTy);
292 if (StepTy->isFloatingPointTy())
293 Init = Builder.createWidenCast(Opcode: Instruction::UIToFP, Op: Init, ResultTy: StepTy);
294
295 VPValue *SplatStart = Builder.createNaryOp(Opcode: VPInstruction::Broadcast, Operands: Start);
296 VPValue *SplatStep = Builder.createNaryOp(Opcode: VPInstruction::Broadcast, Operands: Step);
297
298 Init = Builder.createNaryOp(Opcode: MulOp, Operands: {Init, SplatStep}, Flags);
299 Init = Builder.createNaryOp(Opcode: AddOp, Operands: {SplatStart, Init}, Flags,
300 DL: DebugLoc::getUnknown(), Name: "induction");
301
302 // Create the widened phi of the vector IV.
303 auto *WidePHI = VPBuilder(WidenIVR).createWidenPhi(
304 IncomingValues: Init, DL: WidenIVR->getDebugLoc(), Name: "vec.ind");
305
306 // Create the backedge value for the vector IV.
307 VPValue *Inc;
308 VPValue *Prev;
309 // If unrolled, use the increment and prev value from the operands.
310 if (auto *SplatVF = WidenIVR->getSplatVFValue()) {
311 Inc = SplatVF;
312 Prev = WidenIVR->getLastUnrolledPartOperand();
313 } else {
314 // Move the insertion point after the VF definition when the VF is defined
315 // inside a loop, such as for EVL tail-folding.
316 if (VPRecipeBase *R = VF->getDefiningRecipe())
317 if (R->getParent()->getEnclosingLoopRegion())
318 Builder.setInsertPoint(TheBB: R->getParent(), IP: std::next(x: R->getIterator()));
319
320 // Multiply the vectorization factor by the step using integer or
321 // floating-point arithmetic as appropriate.
322 if (StepTy->isFloatingPointTy())
323 VF = Builder.createScalarCast(Opcode: Instruction::CastOps::UIToFP, Op: VF, ResultTy: StepTy,
324 DL);
325 else
326 VF = Builder.createScalarZExtOrTrunc(Op: VF, ResultTy: StepTy, DL);
327
328 Inc = Builder.createNaryOp(Opcode: MulOp, Operands: {Step, VF}, Flags);
329 Inc = Builder.createNaryOp(Opcode: VPInstruction::Broadcast, Operands: Inc);
330 Prev = WidePHI;
331 }
332
333 VPBasicBlock *ExitingBB = Plan->getVectorLoopRegion()->getExitingBasicBlock();
334 Builder.setInsertPoint(TheBB: ExitingBB, IP: ExitingBB->getTerminator()->getIterator());
335 auto *Next = Builder.createNaryOp(Opcode: AddOp, Operands: {Prev, Inc}, Flags,
336 DL: WidenIVR->getDebugLoc(), Name: "vec.ind.next");
337
338 WidePHI->addIncoming(IncomingV: Next);
339
340 WidenIVR->replaceAllUsesWith(New: WidePHI);
341}
342
343/// Expand a VPWidenPointerInductionRecipe into executable recipes, for the
344/// initial value, phi and backedge value. In the following example:
345///
346/// <x1> vector loop: {
347/// vector.body:
348/// EMIT ir<%ptr.iv> = WIDEN-POINTER-INDUCTION %start, %step, %vf
349/// ...
350/// EMIT branch-on-count ...
351/// }
352///
353/// WIDEN-POINTER-INDUCTION will get expanded to:
354///
355/// <x1> vector loop: {
356/// vector.body:
357/// EMIT-SCALAR %pointer.phi = phi %start, %ptr.ind
358/// EMIT %mul = mul %stepvector, %step
359/// EMIT %vector.gep = wide-ptradd %pointer.phi, %mul
360/// ...
361/// EMIT %ptr.ind = ptradd %pointer.phi, %vf
362/// EMIT branch-on-count ...
363/// }
364static void expandVPWidenPointerInduction(VPWidenPointerInductionRecipe *R) {
365 VPlan *Plan = R->getParent()->getPlan();
366 VPValue *Start = R->getStartValue();
367 VPValue *Step = R->getStepValue();
368 VPValue *VF = R->getVFValue();
369
370 assert(R->getInductionDescriptor().getKind() ==
371 InductionDescriptor::IK_PtrInduction &&
372 "Not a pointer induction according to InductionDescriptor!");
373 assert(R->getScalarType()->isPointerTy() && "Unexpected type.");
374 assert(!R->onlyScalarsGenerated(Plan->hasScalableVF()) &&
375 "Recipe should have been replaced");
376
377 VPBuilder Builder(R);
378 DebugLoc DL = R->getDebugLoc();
379
380 // Build a scalar pointer phi.
381 VPPhi *ScalarPtrPhi = Builder.createScalarPhi(IncomingValues: Start, DL, Name: "pointer.phi");
382
383 // Create actual address geps that use the pointer phi as base and a
384 // vectorized version of the step value (<step*0, ..., step*N>) as offset.
385 Builder.setInsertPoint(TheBB: R->getParent(), IP: R->getParent()->getFirstNonPhi());
386 Type *StepTy = Step->getScalarType();
387 VPValue *Offset = Builder.createNaryOp(Opcode: VPInstruction::StepVector, Operands: {}, ResultTy: StepTy);
388 Offset = Builder.createOverflowingOp(Opcode: Instruction::Mul, Operands: {Offset, Step});
389 VPValue *PtrAdd =
390 Builder.createWidePtrAdd(Ptr: ScalarPtrPhi, Offset, DL, Name: "vector.gep");
391 R->replaceAllUsesWith(New: PtrAdd);
392
393 // Create the backedge value for the scalar pointer phi.
394 VPBasicBlock *ExitingBB = Plan->getVectorLoopRegion()->getExitingBasicBlock();
395 Builder.setInsertPoint(TheBB: ExitingBB, IP: ExitingBB->getTerminator()->getIterator());
396 VF = Builder.createScalarZExtOrTrunc(Op: VF, ResultTy: StepTy, DL);
397 VPValue *Inc = Builder.createOverflowingOp(Opcode: Instruction::Mul, Operands: {Step, VF});
398
399 VPValue *InductionGEP =
400 Builder.createPtrAdd(Ptr: ScalarPtrPhi, Offset: Inc, DL, Name: "ptr.ind");
401 ScalarPtrPhi->addIncoming(IncomingV: InductionGEP);
402}
403
404/// Expand a VPDerivedIVRecipe into executable recipes.
405static void expandVPDerivedIV(VPDerivedIVRecipe *R) {
406 VPBuilder Builder(R);
407 VPValue *Start = R->getStartValue();
408 VPValue *Step = R->getStepValue();
409 VPValue *Index = R->getIndex();
410 Type *StepTy = Step->getScalarType();
411 Index = StepTy->isIntegerTy()
412 ? Builder.createScalarZExtOrTrunc(
413 Op: Index, ResultTy: StepTy, DL: DebugLoc::getCompilerGenerated())
414 : Builder.createScalarCast(Opcode: Instruction::SIToFP, Op: Index, ResultTy: StepTy,
415 DL: DebugLoc::getCompilerGenerated());
416 VPIRFlags::WrapFlagsTy Flags = R->getNoWrapFlags();
417 switch (R->getInductionKind()) {
418 case InductionDescriptor::IK_IntInduction: {
419 assert(Index->getScalarType() == Start->getScalarType() &&
420 "Index type does not match StartValue type");
421 return R->replaceAllUsesWith(New: Builder.createAdd(
422 LHS: Start,
423 RHS: Builder.createOverflowingOp(Opcode: Instruction::Mul, Operands: {Index, Step}, WrapFlags: Flags),
424 DL: DebugLoc::getUnknown(), Name: "", WrapFlags: Flags));
425 }
426 case InductionDescriptor::IK_PtrInduction:
427 return R->replaceAllUsesWith(New: Builder.createPtrAdd(
428 Ptr: Start,
429 Offset: Builder.createOverflowingOp(Opcode: Instruction::Mul, Operands: {Index, Step}, WrapFlags: Flags)));
430 case InductionDescriptor::IK_FpInduction: {
431 assert(StepTy->isFloatingPointTy() && "Expected FP Step value");
432 const FPMathOperator *FPBinOp = R->getFPBinOp();
433 assert(FPBinOp &&
434 (FPBinOp->getOpcode() == Instruction::FAdd ||
435 FPBinOp->getOpcode() == Instruction::FSub) &&
436 "Original BinOp should be defined for FP induction");
437 FastMathFlags FMF = FPBinOp->getFastMathFlags();
438 VPValue *FMul = Builder.createNaryOp(Opcode: Instruction::FMul, Operands: {Step, Index}, Flags: FMF);
439 return R->replaceAllUsesWith(
440 New: Builder.createNaryOp(Opcode: FPBinOp->getOpcode(), Operands: {Start, FMul}, Flags: FMF));
441 }
442 case InductionDescriptor::IK_NoInduction:
443 return;
444 }
445 llvm_unreachable("Unhandled induction kind");
446}
447
448void VPlanTransforms::dissolveLoopRegions(VPlan &Plan) {
449 // Replace loop regions with explicity CFG.
450 SmallVector<VPRegionBlock *> LoopRegions;
451 for (VPRegionBlock *R : VPBlockUtils::blocksOnly<VPRegionBlock>(
452 Range: vp_depth_first_deep(G: Plan.getEntry()))) {
453 if (!R->isReplicator())
454 LoopRegions.push_back(Elt: R);
455 }
456 for (VPRegionBlock *R : LoopRegions)
457 R->dissolveToCFGLoop();
458}
459
460void VPlanTransforms::expandBranchOnTwoConds(VPlan &Plan) {
461 SmallVector<VPInstruction *> WorkList;
462 // The transform runs after dissolving loop regions, so all VPBasicBlocks
463 // terminated with BranchOnTwoConds are reached via a shallow traversal.
464 for (VPBasicBlock *VPBB : VPBlockUtils::blocksAs<VPBasicBlock>(
465 Range: vp_depth_first_shallow(G: Plan.getEntry()))) {
466 if (!VPBB->empty() && match(V: &VPBB->back(), P: m_BranchOnTwoConds()))
467 WorkList.push_back(Elt: cast<VPInstruction>(Val: &VPBB->back()));
468 }
469
470 // Expand BranchOnTwoConds instructions into explicit CFG with two new
471 // single-condition branches:
472 // 1. A branch that replaces BranchOnTwoConds, jumps to the first successor if
473 // the first condition is true, and otherwise jumps to a new interim block.
474 // 2. A branch that ends the interim block, jumps to the second successor if
475 // the second condition is true, and otherwise jumps to the third
476 // successor.
477 for (VPInstruction *Br : WorkList) {
478 assert(Br->getNumOperands() == 2 &&
479 "BranchOnTwoConds must have exactly 2 conditions");
480 DebugLoc DL = Br->getDebugLoc();
481 VPBasicBlock *BrOnTwoCondsBB = Br->getParent();
482 const auto Successors = to_vector(Range&: BrOnTwoCondsBB->getSuccessors());
483 assert(Successors.size() == 3 &&
484 "BranchOnTwoConds must have exactly 3 successors");
485
486 for (VPBlockBase *Succ : Successors)
487 VPBlockUtils::disconnectBlocks(From: BrOnTwoCondsBB, To: Succ);
488
489 VPValue *Cond0 = Br->getOperand(N: 0);
490 VPValue *Cond1 = Br->getOperand(N: 1);
491 VPBlockBase *Succ0 = Successors[0];
492 VPBlockBase *Succ1 = Successors[1];
493 VPBlockBase *Succ2 = Successors[2];
494
495 // If the successor block for both conditions is the same, then combine the
496 // two conditions and plant a single conditional branch.
497 if (Succ0 == Succ1) {
498 VPBuilder Builder(Br);
499 VPValue *Combined = Builder.createOr(LHS: Cond0, RHS: Cond1, DL);
500 Builder.createNaryOp(Opcode: VPInstruction::BranchOnCond, Operands: {Combined}, DL);
501 VPBlockUtils::connectBlocks(From: BrOnTwoCondsBB, To: Succ0);
502 VPBlockUtils::connectBlocks(From: BrOnTwoCondsBB, To: Succ2);
503 Br->eraseFromParent();
504 continue;
505 }
506
507 assert(!Succ0->getParent() && !Succ1->getParent() && !Succ2->getParent() &&
508 !BrOnTwoCondsBB->getParent() && "regions must already be dissolved");
509
510 VPBasicBlock *InterimBB =
511 Plan.createVPBasicBlock(Name: BrOnTwoCondsBB->getName() + ".interim");
512
513 VPBuilder(BrOnTwoCondsBB)
514 .createNaryOp(Opcode: VPInstruction::BranchOnCond, Operands: {Cond0}, DL);
515 VPBlockUtils::connectBlocks(From: BrOnTwoCondsBB, To: Succ0);
516 VPBlockUtils::connectBlocks(From: BrOnTwoCondsBB, To: InterimBB);
517
518 VPBuilder(InterimBB).createNaryOp(Opcode: VPInstruction::BranchOnCond, Operands: {Cond1}, DL);
519 VPBlockUtils::connectBlocks(From: InterimBB, To: Succ1);
520 VPBlockUtils::connectBlocks(From: InterimBB, To: Succ2);
521 Br->eraseFromParent();
522 }
523}
524
525void VPlanTransforms::convertToConcreteRecipes(VPlan &Plan) {
526 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
527 Range: vp_depth_first_deep(G: Plan.getEntry()))) {
528 for (VPRecipeBase &R : make_early_inc_range(Range&: *VPBB)) {
529 VPBuilder Builder(&R);
530 if (auto *WidenIVR = dyn_cast<VPWidenIntOrFpInductionRecipe>(Val: &R)) {
531 expandVPWidenIntOrFpInduction(WidenIVR);
532 WidenIVR->eraseFromParent();
533 continue;
534 }
535
536 if (auto *WidenIVR = dyn_cast<VPWidenPointerInductionRecipe>(Val: &R)) {
537 // If the recipe only generates scalars, scalarize it instead of
538 // expanding it.
539 if (WidenIVR->onlyScalarsGenerated(IsScalable: Plan.hasScalableVF())) {
540 VPValue *PtrAdd = vputils::scalarizeVPWidenPointerInduction(
541 PtrIV: WidenIVR, Plan, Builder);
542 WidenIVR->replaceAllUsesWith(New: PtrAdd);
543 WidenIVR->eraseFromParent();
544 continue;
545 }
546 expandVPWidenPointerInduction(R: WidenIVR);
547 WidenIVR->eraseFromParent();
548 continue;
549 }
550
551 if (auto *DerivedIVR = dyn_cast<VPDerivedIVRecipe>(Val: &R)) {
552 expandVPDerivedIV(R: DerivedIVR);
553 DerivedIVR->eraseFromParent();
554 continue;
555 }
556
557 if (auto *WideCanIV = dyn_cast<VPWidenCanonicalIVRecipe>(Val: &R)) {
558 VPValue *CanIV = WideCanIV->getCanonicalIV();
559 Type *CanIVTy = CanIV->getScalarType();
560 VPValue *Step = WideCanIV->getStepValue();
561 if (!Step) {
562 assert(Plan.getConcreteUF() == 1 &&
563 "Expected unroller to have materialized step for UF != 1");
564 Step = Plan.getZero(Ty: CanIVTy);
565 }
566 CanIV = Builder.createNaryOp(Opcode: VPInstruction::Broadcast, Operands: CanIV);
567 Step = Builder.createNaryOp(Opcode: VPInstruction::Broadcast, Operands: Step);
568 Step = Builder.createAdd(
569 LHS: Step, RHS: Builder.createNaryOp(Opcode: VPInstruction::StepVector, Operands: {}, ResultTy: CanIVTy));
570 VPValue *CanVecIV =
571 Builder.createAdd(LHS: CanIV, RHS: Step, DL: WideCanIV->getDebugLoc(), Name: "vec.iv",
572 WrapFlags: WideCanIV->getNoWrapFlags());
573 WideCanIV->replaceAllUsesWith(New: CanVecIV);
574 WideCanIV->eraseFromParent();
575 continue;
576 }
577
578 // Expand VPBlendRecipe into VPInstruction::Select.
579 if (auto *Blend = dyn_cast<VPBlendRecipe>(Val: &R)) {
580 VPValue *Select = Blend->getIncomingValue(Idx: 0);
581 for (unsigned I = 1; I != Blend->getNumIncomingValues(); ++I)
582 Select = Builder.createSelect(Cond: Blend->getMask(Idx: I),
583 TrueVal: Blend->getIncomingValue(Idx: I), FalseVal: Select,
584 DL: R.getDebugLoc(), Name: "predphi", Flags: *Blend);
585 Blend->replaceAllUsesWith(New: Select);
586 Blend->eraseFromParent();
587 continue;
588 }
589
590 if (auto *VEPR = dyn_cast<VPVectorEndPointerRecipe>(Val: &R)) {
591 if (!VEPR->getOffset()) {
592 assert(Plan.getConcreteUF() == 1 &&
593 "Expected unroller to have materialized offset for UF != 1");
594 VEPR->materializeOffset();
595 }
596 continue;
597 }
598
599 if (auto *Expr = dyn_cast<VPExpressionRecipe>(Val: &R)) {
600 Expr->decompose();
601 Expr->eraseFromParent();
602 continue;
603 }
604
605 // Expand LastActiveLane into Not + FirstActiveLane + Sub.
606 auto *LastActiveL = dyn_cast<VPInstruction>(Val: &R);
607 if (LastActiveL &&
608 LastActiveL->getOpcode() == VPInstruction::LastActiveLane) {
609 // Create Not(Mask) for all operands.
610 SmallVector<VPValue *, 2> NotMasks;
611 for (VPValue *Op : LastActiveL->operands()) {
612 VPValue *NotMask = Builder.createNot(Operand: Op, DL: LastActiveL->getDebugLoc());
613 NotMasks.push_back(Elt: NotMask);
614 }
615
616 // Create FirstActiveLane on the inverted masks.
617 VPValue *FirstInactiveLane = Builder.createFirstActiveLane(
618 Masks: NotMasks, DL: LastActiveL->getDebugLoc(), Name: "first.inactive.lane");
619
620 // Subtract 1 to get the last active lane.
621 VPValue *One =
622 Plan.getConstantInt(Ty: FirstInactiveLane->getScalarType(), Val: 1);
623 VPValue *LastLane =
624 Builder.createSub(LHS: FirstInactiveLane, RHS: One,
625 DL: LastActiveL->getDebugLoc(), Name: "last.active.lane");
626
627 LastActiveL->replaceAllUsesWith(New: LastLane);
628 LastActiveL->eraseFromParent();
629 continue;
630 }
631
632 // Lower MaskedCond with block mask to LogicalAnd.
633 if (match(V: &R, P: m_VPInstruction<VPInstruction::MaskedCond>())) {
634 auto *VPI = cast<VPInstruction>(Val: &R);
635 assert(VPI->isMasked() &&
636 "Unmasked MaskedCond should be simplified earlier");
637 VPI->replaceAllUsesWith(New: Builder.createNaryOp(
638 Opcode: VPInstruction::LogicalAnd, Operands: {VPI->getMask(), VPI->getOperand(N: 0)}));
639 VPI->eraseFromParent();
640 continue;
641 }
642
643 // Lower CanonicalIVIncrementForPart to plain Add.
644 if (match(
645 V: &R,
646 P: m_VPInstruction<VPInstruction::CanonicalIVIncrementForPart>())) {
647 auto *VPI = cast<VPInstruction>(Val: &R);
648 VPValue *Add = Builder.createOverflowingOp(
649 Opcode: Instruction::Add, Operands: VPI->operands(), WrapFlags: VPI->getNoWrapFlags(),
650 DL: VPI->getDebugLoc());
651 VPI->replaceAllUsesWith(New: Add);
652 VPI->eraseFromParent();
653 continue;
654 }
655
656 // Lower BranchOnCount to ICmp + BranchOnCond.
657 VPValue *IV, *TC;
658 if (match(V: &R, P: m_BranchOnCount(Op0: m_VPValue(V&: IV), Op1: m_VPValue(V&: TC)))) {
659 auto *BranchOnCountInst = cast<VPInstruction>(Val: &R);
660 DebugLoc DL = BranchOnCountInst->getDebugLoc();
661 VPValue *Cond = Builder.createICmp(Pred: CmpInst::ICMP_EQ, A: IV, B: TC, DL);
662 Builder.createNaryOp(Opcode: VPInstruction::BranchOnCond, Operands: Cond, DL);
663 BranchOnCountInst->eraseFromParent();
664 continue;
665 }
666
667 VPValue *VectorStep;
668 VPValue *ScalarStep;
669 if (!match(V: &R, P: m_VPInstruction<VPInstruction::WideIVStep>(
670 Ops: m_VPValue(V&: VectorStep), Ops: m_VPValue(V&: ScalarStep))))
671 continue;
672
673 // Expand WideIVStep.
674 auto *VPI = cast<VPInstruction>(Val: &R);
675 Type *IVTy = VPI->getScalarType();
676 if (VectorStep->getScalarType() != IVTy) {
677 Instruction::CastOps CastOp = IVTy->isFloatingPointTy()
678 ? Instruction::UIToFP
679 : Instruction::Trunc;
680 VectorStep = Builder.createWidenCast(Opcode: CastOp, Op: VectorStep, ResultTy: IVTy);
681 }
682
683 assert(!match(ScalarStep, m_One()) && "Expected non-unit scalar-step");
684 if (ScalarStep->getScalarType() != IVTy) {
685 ScalarStep =
686 Builder.createWidenCast(Opcode: Instruction::Trunc, Op: ScalarStep, ResultTy: IVTy);
687 }
688
689 VPIRFlags Flags;
690 unsigned MulOpc;
691 if (IVTy->isFloatingPointTy()) {
692 MulOpc = Instruction::FMul;
693 Flags = VPI->getFastMathFlagsOrNone();
694 } else {
695 MulOpc = Instruction::Mul;
696 Flags = VPIRFlags::getDefaultFlags(Opcode: MulOpc);
697 }
698
699 VPInstruction *Mul = Builder.createNaryOp(
700 Opcode: MulOpc, Operands: {VectorStep, ScalarStep}, Flags, DL: R.getDebugLoc());
701 VectorStep = Mul;
702 VPI->replaceAllUsesWith(New: VectorStep);
703 VPI->eraseFromParent();
704 }
705 }
706}
707
708void VPlanTransforms::materializeBroadcasts(VPlan &Plan) {
709 if (Plan.hasScalarVFOnly())
710 return;
711
712#ifndef NDEBUG
713 VPDominatorTree VPDT(Plan);
714#endif
715
716 SmallVector<VPValue *> VPValues;
717 if (VPValue *BTC = Plan.getBackedgeTakenCount())
718 VPValues.push_back(Elt: BTC);
719 append_range(C&: VPValues, R: Plan.getLiveIns());
720 for (VPRecipeBase &R : *Plan.getEntry())
721 append_range(C&: VPValues, R: R.definedValues());
722
723 auto *VectorPreheader = Plan.getVectorPreheader();
724 for (VPValue *VPV : VPValues) {
725 if (vputils::onlyScalarValuesUsed(Def: VPV) || isa<VPConstant>(Val: VPV))
726 continue;
727
728 // Add explicit broadcast at the insert point that dominates all users.
729 VPBasicBlock *HoistBlock = VectorPreheader;
730 VPBasicBlock::iterator HoistPoint = VectorPreheader->end();
731 for (VPUser *User : VPV->users()) {
732 if (User->usesScalars(Op: VPV))
733 continue;
734 if (cast<VPRecipeBase>(Val: User)->getParent() == VectorPreheader)
735 HoistPoint = HoistBlock->getFirstNonPhi();
736 else
737 assert(VPDT.dominates(VectorPreheader,
738 cast<VPRecipeBase>(User)->getParent()) &&
739 "All users must be in the vector preheader or dominated by it");
740 }
741
742 VPBuilder Builder(cast<VPBasicBlock>(Val: HoistBlock), HoistPoint);
743 auto *Broadcast = Builder.createNaryOp(Opcode: VPInstruction::Broadcast, Operands: {VPV});
744 VPV->replaceUsesWithIf(New: Broadcast,
745 ShouldReplace: [VPV, Broadcast](VPUser &U, unsigned Idx) {
746 return Broadcast != &U && !U.usesScalars(Op: VPV);
747 });
748 }
749}
750
751void VPlanTransforms::materializeConstantVectorTripCount(
752 VPlan &Plan, ElementCount BestVF, unsigned BestUF,
753 PredicatedScalarEvolution &PSE) {
754 assert(Plan.hasVF(BestVF) && "BestVF is not available in Plan");
755 assert(Plan.hasUF(BestUF) && "BestUF is not available in Plan");
756
757 VPValue *TC = Plan.getTripCount();
758 if (TC->user_empty())
759 return;
760
761 // Skip cases for which the trip count may be non-trivial to materialize.
762 // I.e., when a scalar tail is absent - due to tail folding, or when a scalar
763 // tail is required.
764 if (Plan.hasTailFolded() || !Plan.hasScalarTail() ||
765 Plan.getMiddleBlock()->getSingleSuccessor() ==
766 Plan.getScalarPreheader() ||
767 !isa<VPIRValue>(Val: TC))
768 return;
769
770 // Materialize vector trip counts for constants early if it can simply
771 // be computed as (Original TC / VF * UF) * VF * UF.
772 // TODO: Compute vector trip counts for loops requiring a scalar epilogue and
773 // tail-folded loops.
774 ScalarEvolution &SE = *PSE.getSE();
775 auto *TCScev = SE.getSCEV(V: TC->getLiveInIRValue());
776 if (!isa<SCEVConstant>(Val: TCScev))
777 return;
778 const SCEV *VFxUF = SE.getElementCount(Ty: TCScev->getType(), EC: BestVF * BestUF);
779 const SCEV *VecTCScev = SE.getMulExpr(LHS: SE.getUDivExpr(LHS: TCScev, RHS: VFxUF), RHS: VFxUF);
780 if (auto *ConstVecTC = dyn_cast<SCEVConstant>(Val: VecTCScev))
781 Plan.getVectorTripCount().setUnderlyingValue(ConstVecTC->getValue());
782}
783
784void VPlanTransforms::materializeBackedgeTakenCount(VPlan &Plan,
785 VPBasicBlock *VectorPH) {
786 VPValue *BTC = Plan.getOrCreateBackedgeTakenCount();
787 if (BTC->user_empty())
788 return;
789
790 VPBuilder Builder(VectorPH, VectorPH->getFirstNonPhi());
791 auto *TCTy = Plan.getTripCount()->getScalarType();
792 auto *TCMO =
793 Builder.createSub(LHS: Plan.getTripCount(), RHS: Plan.getConstantInt(Ty: TCTy, Val: 1),
794 DL: DebugLoc::getCompilerGenerated(), Name: "trip.count.minus.1");
795 BTC->replaceAllUsesWith(New: TCMO);
796}
797
798void VPlanTransforms::materializePacksAndUnpacks(VPlan &Plan) {
799 if (Plan.hasScalarVFOnly())
800 return;
801
802 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();
803 auto VPBBsOutsideLoopRegion = VPBlockUtils::blocksOnly<VPBasicBlock>(
804 Range: vp_depth_first_shallow(G: Plan.getEntry()));
805 auto VPBBsInsideLoopRegion = VPBlockUtils::blocksOnly<VPBasicBlock>(
806 Range: vp_depth_first_shallow(G: LoopRegion->getEntry()));
807 // Materialize Build(Struct)Vector for all replicating VPReplicateRecipes,
808 // VPScalarIVStepsRecipe and VPInstructions, excluding ones in replicate
809 // regions. Those are not materialized explicitly yet.
810 // TODO: materialize build vectors for replicating recipes in replicating
811 // regions.
812 for (VPBasicBlock *VPBB :
813 concat<VPBasicBlock *>(Ranges&: VPBBsOutsideLoopRegion, Ranges&: VPBBsInsideLoopRegion)) {
814 for (VPRecipeBase &R : make_early_inc_range(Range&: *VPBB)) {
815 if (!vputils::doesGeneratePerAllLanes(R: &R))
816 continue;
817 auto *DefR = cast<VPSingleDefRecipe>(Val: &R);
818 auto UsesVectorOrInsideReplicateRegion = [DefR, LoopRegion](VPUser *U) {
819 VPRegionBlock *ParentRegion = cast<VPRecipeBase>(Val: U)->getRegion();
820 return !U->usesScalars(Op: DefR) || ParentRegion != LoopRegion;
821 };
822 if (none_of(Range: DefR->users(), P: UsesVectorOrInsideReplicateRegion))
823 continue;
824
825 Type *ScalarTy = DefR->getScalarType();
826 unsigned Opcode = ScalarTy->isStructTy()
827 ? VPInstruction::BuildStructVector
828 : VPInstruction::BuildVector;
829 auto *BuildVector = new VPInstruction(Opcode, {DefR});
830 BuildVector->insertAfter(InsertPos: DefR);
831
832 DefR->replaceUsesWithIf(
833 New: BuildVector, ShouldReplace: [BuildVector, &UsesVectorOrInsideReplicateRegion](
834 VPUser &U, unsigned) {
835 return &U != BuildVector && UsesVectorOrInsideReplicateRegion(&U);
836 });
837 }
838 }
839
840 // Create explicit VPInstructions to convert vectors to scalars. The current
841 // implementation is conservative - it may miss some cases that may or may not
842 // be vector values. TODO: introduce Unpacks speculatively - remove them later
843 // if they are known to operate on scalar values.
844 for (VPBasicBlock *VPBB : VPBBsInsideLoopRegion) {
845 for (VPRecipeBase &R : make_early_inc_range(Range&: *VPBB)) {
846 if (isa<VPReplicateRecipe, VPInstruction, VPScalarIVStepsRecipe,
847 VPDerivedIVRecipe>(Val: &R))
848 continue;
849 for (VPValue *Def : R.definedValues()) {
850 // Skip recipes that are single-scalar.
851 // TODO: The Defs skipped here may or may not be vector values.
852 // Introduce Unpacks, and remove them later, if they are guaranteed to
853 // produce scalar values.
854 if (vputils::isSingleScalar(VPV: Def))
855 continue;
856
857 // Only introduce an Unpack if some, but not all, users use the first
858 // lane only.
859 unsigned NumFirstLaneUsers = count_if(Range: Def->users(), P: [&Def](VPUser *U) {
860 return U->usesFirstLaneOnly(Op: Def);
861 });
862 if (!NumFirstLaneUsers || NumFirstLaneUsers == Def->getNumUsers())
863 continue;
864
865 auto *Unpack = new VPInstruction(VPInstruction::Unpack, {Def});
866 if (R.isPhi())
867 Unpack->insertBefore(BB&: *VPBB, IP: VPBB->getFirstNonPhi());
868 else
869 Unpack->insertAfter(InsertPos: &R);
870 Def->replaceUsesWithIf(New: Unpack, ShouldReplace: [&Def](VPUser &U, unsigned) {
871 return U.usesFirstLaneOnly(Op: Def);
872 });
873 }
874 }
875 }
876}
877
878void VPlanTransforms::materializeVectorTripCount(
879 VPlan &Plan, VPBasicBlock *VectorPHVPBB, bool TailByMasking,
880 bool RequiresScalarEpilogue, VPValue *Step,
881 std::optional<uint64_t> MaxRuntimeStep) {
882 VPSymbolicValue &VectorTC = Plan.getVectorTripCount();
883 // There's nothing to do if there are no users of the vector trip count or its
884 // IR value has already been set.
885 if (VectorTC.user_empty() || VectorTC.getUnderlyingValue())
886 return;
887
888 VPValue *TC = Plan.getTripCount();
889 Type *TCTy = TC->getScalarType();
890 VPBasicBlock::iterator InsertPt = VectorPHVPBB->getFirstNonPhi();
891 if (auto *StepR = Step->getDefiningRecipe()) {
892 assert(VPDominatorTree(Plan).dominates(StepR->getParent(), VectorPHVPBB) &&
893 "Step VPBB must dominate VectorPHVPBB");
894 // Insert after Step's definition to maintain valid def-use ordering.
895 InsertPt = std::next(x: StepR->getIterator());
896 }
897 VPBuilder Builder(VectorPHVPBB, InsertPt);
898
899 // For scalable steps, if TC is a constant and is divisible by the maximum
900 // possible runtime step, then TC % Step == 0 for all valid vscale values
901 // and the vector trip count equals TC directly.
902 const APInt *TCVal;
903 if (!RequiresScalarEpilogue && match(V: TC, P: m_APInt(C&: TCVal)) && MaxRuntimeStep &&
904 TCVal->urem(RHS: *MaxRuntimeStep) == 0) {
905 VectorTC.replaceAllUsesWith(New: TC);
906 return;
907 }
908
909 // If the tail is to be folded by masking, round the number of iterations N
910 // up to a multiple of Step instead of rounding down. This is done by first
911 // adding Step-1 and then rounding down. Note that it's ok if this addition
912 // overflows: the vector induction variable will eventually wrap to zero given
913 // that it starts at zero and its Step is a power of two; the loop will then
914 // exit, with the last early-exit vector comparison also producing all-true.
915 if (TailByMasking) {
916 TC = Builder.createAdd(
917 LHS: TC, RHS: Builder.createSub(LHS: Step, RHS: Plan.getConstantInt(Ty: TCTy, Val: 1)),
918 DL: DebugLoc::getCompilerGenerated(), Name: "n.rnd.up");
919 }
920
921 // Now we need to generate the expression for the part of the loop that the
922 // vectorized body will execute. This is equal to N - (N % Step) if scalar
923 // iterations are not required for correctness, or N - Step, otherwise. Step
924 // is equal to the vectorization factor (number of SIMD elements) times the
925 // unroll factor (number of SIMD instructions).
926 VPValue *R =
927 Builder.createNaryOp(Opcode: Instruction::URem, Operands: {TC, Step},
928 DL: DebugLoc::getCompilerGenerated(), Name: "n.mod.vf");
929
930 // There are cases where we *must* run at least one iteration in the remainder
931 // loop. See the cost model for when this can happen. If the step evenly
932 // divides the trip count, we set the remainder to be equal to the step. If
933 // the step does not evenly divide the trip count, no adjustment is necessary
934 // since there will already be scalar iterations. Note that the minimum
935 // iterations check ensures that N >= Step.
936 if (RequiresScalarEpilogue) {
937 assert(!TailByMasking &&
938 "requiring scalar epilogue is not supported with fail folding");
939 VPValue *IsZero =
940 Builder.createICmp(Pred: CmpInst::ICMP_EQ, A: R, B: Plan.getZero(Ty: TCTy));
941 R = Builder.createSelect(Cond: IsZero, TrueVal: Step, FalseVal: R);
942 }
943
944 VPValue *Res =
945 Builder.createSub(LHS: TC, RHS: R, DL: DebugLoc::getCompilerGenerated(), Name: "n.vec");
946 VectorTC.replaceAllUsesWith(New: Res);
947}
948
949void VPlanTransforms::materializeFactors(VPlan &Plan, VPBasicBlock *VectorPH,
950 ElementCount VFEC) {
951 // If VF and VFxUF have already been materialized (no remaining users),
952 // there's nothing more to do.
953 if (Plan.getVF().isMaterialized()) {
954 assert(Plan.getVFxUF().isMaterialized() &&
955 "VF and VFxUF must be materialized together");
956 return;
957 }
958
959 VPBuilder Builder(VectorPH, VectorPH->getFirstNonPhi());
960 Type *TCTy = Plan.getTripCount()->getScalarType();
961 VPValue &VF = Plan.getVF();
962 VPValue &VFxUF = Plan.getVFxUF();
963 // If there are no users of the runtime VF, compute VFxUF by constant folding
964 // the multiplication of VF and UF.
965 if (VF.user_empty()) {
966 VPValue *RuntimeVFxUF =
967 Builder.createElementCount(Ty: TCTy, EC: VFEC * Plan.getConcreteUF());
968 VFxUF.replaceAllUsesWith(New: RuntimeVFxUF);
969 return;
970 }
971
972 // For users of the runtime VF, compute it as VF * vscale, and VFxUF as (VF *
973 // vscale) * UF.
974 VPValue *RuntimeVF = Builder.createElementCount(Ty: TCTy, EC: VFEC);
975 if (!vputils::onlyScalarValuesUsed(Def: &VF)) {
976 VPValue *BC = Builder.createNaryOp(Opcode: VPInstruction::Broadcast, Operands: RuntimeVF);
977 VF.replaceUsesWithIf(
978 New: BC, ShouldReplace: [&VF](VPUser &U, unsigned) { return !U.usesScalars(Op: &VF); });
979 }
980 VF.replaceAllUsesWith(New: RuntimeVF);
981
982 VPValue *MulByUF =
983 Builder.createElementCount(Ty: TCTy, EC: VFEC * Plan.getConcreteUF());
984 VFxUF.replaceAllUsesWith(New: MulByUF);
985}
986
987VPValue *
988VPlanTransforms::materializeAliasMask(VPlan &Plan, VPBasicBlock *AliasCheckVPBB,
989 ArrayRef<PointerDiffInfo> DiffChecks) {
990 VPBuilder Builder(AliasCheckVPBB);
991 Type *I1Ty = IntegerType::getInt1Ty(C&: Plan.getContext());
992
993 VPValue *IncomingAliasMask = vputils::findIncomingAliasMask(Plan);
994 assert(IncomingAliasMask && "Expected an alias mask!");
995
996 VPValue *AliasMask = nullptr;
997 for (const PointerDiffInfo &Check : DiffChecks) {
998 VPValue *Src = vputils::getOrCreateVPValueForSCEVExpr(Plan, Expr: Check.SrcStart);
999 VPValue *Sink =
1000 vputils::getOrCreateVPValueForSCEVExpr(Plan, Expr: Check.SinkStart);
1001 Type *AddrType = Src->getScalarType();
1002
1003 // TODO: Only freeze the required pointer (not both src and sink).
1004 if (Check.NeedsFreeze) {
1005 Src = Builder.createFreeze(Op: Src);
1006 Sink = Builder.createFreeze(Op: Sink);
1007 }
1008
1009 // TODO: Generate loop_dependence_raw_mask when there's a read-after-write
1010 // dependency between the source and the sink. This is not necessary for
1011 // correctness of the mask, but using the "raw" variant prevents loads
1012 // depending on the completion of stores.
1013 VPWidenIntrinsicRecipe *WARMask = Builder.insert(R: new VPWidenIntrinsicRecipe(
1014 Intrinsic::loop_dependence_war_mask,
1015 {Src, Sink, Plan.getConstantInt(Ty: AddrType, Val: Check.AccessSize)}, I1Ty));
1016
1017 if (AliasMask)
1018 AliasMask = Builder.createAnd(LHS: AliasMask, RHS: WARMask);
1019 else
1020 AliasMask = WARMask;
1021 }
1022
1023 Type *IVTy = Plan.getVectorLoopRegion()->getCanonicalIVType();
1024 Type *IndexTy = Plan.getDataLayout().getIndexType(C&: Plan.getContext(), AddressSpace: 0);
1025 VPValue *NumActive = Builder.createNaryOp(
1026 Opcode: VPInstruction::NumActiveLanes, Operands: {AliasMask}, Inst: nullptr, Flags: {}, MD: {},
1027 DL: DebugLoc::getUnknown(), Name: "num.active.lanes", ResultTy: IndexTy);
1028 VPValue *ClampedVF = Builder.createScalarZExtOrTrunc(
1029 Op: NumActive, ResultTy: IVTy, DL: DebugLoc::getCompilerGenerated());
1030
1031 IncomingAliasMask->replaceAllUsesWith(New: AliasMask);
1032
1033 return ClampedVF;
1034}
1035
1036void VPlanTransforms::materializeAliasMaskCheckBlock(
1037 VPlan &Plan, ArrayRef<PointerDiffInfo> DiffChecks, bool HasBranchWeights) {
1038 VPBasicBlock *ClampedVFCheck =
1039 Plan.createVPBasicBlock(Name: "vector.clamped.vf.check");
1040
1041 VPValue *ClampedVF = materializeAliasMask(Plan, AliasCheckVPBB: ClampedVFCheck, DiffChecks);
1042 VPBuilder Builder(ClampedVFCheck);
1043 DebugLoc DL = DebugLoc::getCompilerGenerated();
1044 Type *TCTy = Plan.getTripCount()->getScalarType();
1045
1046 // Check the "ClampedVF" from the alias mask is larger than one.
1047 VPValue *IsScalar =
1048 Builder.createICmp(Pred: CmpInst::ICMP_ULE, A: ClampedVF,
1049 B: Plan.getConstantInt(Ty: TCTy, Val: 1), DL, Name: "vf.is.scalar");
1050
1051 VPValue *TripCount = Plan.getTripCount();
1052 VPValue *MaxUIntTripCount =
1053 Plan.getConstantInt(Val: cast<IntegerType>(Val: TCTy)->getMask());
1054 VPValue *DistanceToMax = Builder.createSub(LHS: MaxUIntTripCount, RHS: TripCount);
1055
1056 // For tail-folding: Don't execute the vector loop if (UMax - n) < ClampedVF.
1057 // Note: The ClampedVF may not be a power-of-two. This means the loop exit
1058 // condition (index.next == n.vec) may not be correct in the case of an
1059 // overflow. The issue is `n.vec` could be zero due to an overflow, but
1060 // index.next is not guaranteed to overflow to zero as the ClampedVF is not a
1061 // power-of-two).
1062 VPValue *TripCountCheck = Builder.createICmp(
1063 Pred: ICmpInst::ICMP_ULT, A: DistanceToMax, B: ClampedVF, DL, Name: "vf.step.overflow");
1064
1065 VPValue *Cond = Builder.createOr(LHS: IsScalar, RHS: TripCountCheck, DL);
1066 attachVPCheckBlock(Plan, Cond, CheckBlock: ClampedVFCheck, AddBranchWeights: HasBranchWeights);
1067
1068 // Materialize the trip count early as this will add a use of (VFxUF) that
1069 // needs to be replaced with the ClampedVF.
1070 materializeVectorTripCount(Plan, VectorPHVPBB: Plan.getVectorPreheader(),
1071 /*TailByMasking=*/true,
1072 /*RequiresScalarEpilogue=*/false,
1073 Step: &Plan.getVFxUF());
1074
1075 assert(Plan.getConcreteUF() == 1 &&
1076 "Clamped VF not supported with interleaving");
1077 Plan.getVF().replaceAllUsesWith(New: ClampedVF);
1078 Plan.getVFxUF().replaceAllUsesWith(New: ClampedVF);
1079}
1080
1081void VPlanTransforms::expandSCEVsToVPInstructions(VPlan &Plan,
1082 ScalarEvolution &SE) {
1083 auto *Entry = Plan.getEntry();
1084 VPBuilder Builder(Entry, Entry->begin());
1085 DebugLoc DL = cast<VPIRBasicBlock>(Val: Entry)
1086 ->getIRBasicBlock()
1087 ->getTerminator()
1088 ->getDebugLoc();
1089 VPSCEVExpander Expander(Builder, SE, DL);
1090
1091 // Expand VPExpandSCEVRecipes to VPInstructions using VPSCEVExpander.
1092 for (VPExpandSCEVRecipe &ExpSCEV :
1093 make_early_inc_range(Range: make_isa_range<VPExpandSCEVRecipe>(Range&: *Entry))) {
1094 if (ExpSCEV.user_empty())
1095 continue;
1096 Builder.setInsertPoint(&ExpSCEV);
1097 VPValue *Expanded = Expander.expand(S: ExpSCEV.getSCEV());
1098 ExpSCEV.replaceAllUsesWith(New: Expanded);
1099 // TripCount should not be used after expansion to VPInstructions. Reset to
1100 // poison to avoid dangling references.
1101 if (Plan.getTripCount() == &ExpSCEV)
1102 Plan.resetTripCount(NewTripCount: Plan.getPoison(Ty: ExpSCEV.getScalarType()));
1103 ExpSCEV.eraseFromParent();
1104 }
1105}
1106
1107DenseMap<const SCEV *, Value *>
1108VPlanTransforms::expandSCEVs(VPlan &Plan, ScalarEvolution &SE) {
1109 SCEVExpander Expander(SE, "induction", /*PreserveLCSSA=*/false);
1110
1111 auto *Entry = cast<VPIRBasicBlock>(Val: Plan.getEntry());
1112 BasicBlock *EntryBB = Entry->getIRBasicBlock();
1113 DenseMap<const SCEV *, Value *> ExpandedSCEVs;
1114 // Expand remaining VPExpandSCEVRecipes to IR instructions using SCEVExpander.
1115 for (VPExpandSCEVRecipe &ExpSCEV :
1116 make_early_inc_range(Range: make_isa_range<VPExpandSCEVRecipe>(Range&: *Entry))) {
1117 const SCEV *Expr = ExpSCEV.getSCEV();
1118 Value *Res =
1119 Expander.expandCodeFor(SH: Expr, Ty: Expr->getType(), I: EntryBB->getTerminator());
1120 ExpandedSCEVs[Expr] = Res;
1121 VPValue *Exp = Plan.getOrAddLiveIn(V: Res);
1122 ExpSCEV.replaceAllUsesWith(New: Exp);
1123 if (Plan.getTripCount() == &ExpSCEV)
1124 Plan.resetTripCount(NewTripCount: Exp);
1125 ExpSCEV.eraseFromParent();
1126 }
1127 assert(none_of(*Entry, IsaPred<VPExpandSCEVRecipe>) &&
1128 "all VPExpandSCEVRecipes must have been expanded");
1129 // Add IR instructions in the entry basic block but not in the VPIRBasicBlock
1130 // to the VPIRBasicBlock.
1131 auto EI = Entry->begin();
1132 for (Instruction &I : drop_end(RangeOrContainer&: *EntryBB)) {
1133 if (EI != Entry->end() && isa<VPIRInstruction>(Val: *EI) &&
1134 &cast<VPIRInstruction>(Val: &*EI)->getInstruction() == &I) {
1135 EI++;
1136 continue;
1137 }
1138 VPIRInstruction::create(I)->insertBefore(BB&: *Entry, IP: EI);
1139 }
1140
1141 return ExpandedSCEVs;
1142}
1143
1144/// Add branch weight metadata, if the \p Plan's middle block is terminated by a
1145/// BranchOnCond recipe.
1146void VPlanTransforms::addBranchWeightToMiddleTerminator(
1147 VPlan &Plan, ElementCount VF, std::optional<unsigned> VScaleForTuning) {
1148 VPBasicBlock *MiddleVPBB = Plan.getMiddleBlock();
1149 auto *MiddleTerm =
1150 dyn_cast_or_null<VPInstruction>(Val: MiddleVPBB->getTerminator());
1151 // Only add branch metadata if there is a (conditional) terminator.
1152 if (!MiddleTerm)
1153 return;
1154
1155 assert(MiddleTerm->getOpcode() == VPInstruction::BranchOnCond &&
1156 "must have a BranchOnCond");
1157 // Assume that `TripCount % VectorStep ` is equally distributed.
1158 unsigned VectorStep = Plan.getConcreteUF() * VF.getKnownMinValue();
1159 if (VF.isScalable() && VScaleForTuning.has_value())
1160 VectorStep *= *VScaleForTuning;
1161 assert(VectorStep > 0 && "trip count should not be zero");
1162 MDBuilder MDB(Plan.getContext());
1163 MDNode *BranchWeights =
1164 MDB.createBranchWeights(Weights: {1, VectorStep - 1}, /*IsExpected=*/false);
1165 MiddleTerm->setMetadata(Kind: LLVMContext::MD_prof, Node: BranchWeights);
1166}
1167