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