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