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