1//===-- VPlanUnroll.cpp - VPlan unroller ----------------------------------===//
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 explicit unrolling for VPlans.
11///
12//===----------------------------------------------------------------------===//
13
14#include "VPRecipeBuilder.h"
15#include "VPlan.h"
16#include "VPlanAnalysis.h"
17#include "VPlanCFG.h"
18#include "VPlanHelpers.h"
19#include "VPlanPatternMatch.h"
20#include "VPlanTransforms.h"
21#include "VPlanUtils.h"
22#include "llvm/ADT/PostOrderIterator.h"
23#include "llvm/ADT/STLExtras.h"
24#include "llvm/ADT/ScopeExit.h"
25#include "llvm/Analysis/IVDescriptors.h"
26#include "llvm/IR/Constants.h"
27#include "llvm/IR/Intrinsics.h"
28
29using namespace llvm;
30using namespace llvm::VPlanPatternMatch;
31
32namespace {
33
34/// Helper to hold state needed for unrolling. It holds the Plan to unroll by
35/// UF. It also holds copies of VPValues across UF-1 unroll parts to facilitate
36/// the unrolling transformation, where the original VPValues are retained for
37/// part zero.
38class UnrollState {
39 /// Plan to unroll.
40 VPlan &Plan;
41 /// Unroll factor to unroll by.
42 const unsigned UF;
43
44 /// Unrolling may create recipes that should not be unrolled themselves.
45 /// Those are tracked in ToSkip.
46 SmallPtrSet<VPRecipeBase *, 8> ToSkip;
47
48 // Associate with each VPValue of part 0 its unrolled instances of parts 1,
49 // ..., UF-1.
50 DenseMap<VPValue *, SmallVector<VPValue *>> VPV2Parts;
51
52 /// Unroll replicate region \p VPR by cloning the region UF - 1 times.
53 void unrollReplicateRegionByUF(VPRegionBlock *VPR);
54
55 /// Unroll recipe \p R by cloning it UF - 1 times, unless it is uniform across
56 /// all parts.
57 void unrollRecipeByUF(VPRecipeBase &R);
58
59 /// Unroll header phi recipe \p R. How exactly the recipe gets unrolled
60 /// depends on the concrete header phi. Inserts newly created recipes at \p
61 /// InsertPtForPhi.
62 void unrollHeaderPHIByUF(VPHeaderPHIRecipe *R,
63 VPBasicBlock::iterator InsertPtForPhi);
64
65 /// Unroll a widen induction recipe \p IV. This introduces recipes to compute
66 /// the induction steps for each part.
67 void unrollWidenInductionByUF(VPWidenInductionRecipe *IV,
68 VPBasicBlock::iterator InsertPtForPhi);
69
70 VPValue *getConstantInt(unsigned Part) {
71 Type *CanIVIntTy = Plan.getVectorLoopRegion()->getCanonicalIVType();
72 return Plan.getConstantInt(Ty: CanIVIntTy, Val: Part);
73 }
74
75public:
76 UnrollState(VPlan &Plan, unsigned UF) : Plan(Plan), UF(UF) {}
77
78 void unrollBlock(VPBlockBase *VPB);
79
80 VPValue *getValueForPart(VPValue *V, unsigned Part) {
81 if (Part == 0 || isa<VPIRValue, VPSymbolicValue>(Val: V))
82 return V;
83 assert((VPV2Parts.contains(V) && VPV2Parts[V].size() >= Part) &&
84 "accessed value does not exist");
85 return VPV2Parts[V][Part - 1];
86 }
87
88 /// Given a single original recipe \p OrigR (of part zero), and its copy \p
89 /// CopyR for part \p Part, map every VPValue defined by \p OrigR to its
90 /// corresponding VPValue defined by \p CopyR.
91 void addRecipeForPart(VPRecipeBase *OrigR, VPRecipeBase *CopyR,
92 unsigned Part) {
93 for (const auto &[Idx, VPV] : enumerate(First: OrigR->definedValues())) {
94 const auto &[V, _] = VPV2Parts.try_emplace(Key: VPV);
95 assert(V->second.size() == Part - 1 && "earlier parts not set");
96 V->second.push_back(Elt: CopyR->getVPValue(I: Idx));
97 }
98 }
99
100 /// Given a uniform recipe \p R, add it for all parts.
101 void addUniformForAllParts(VPSingleDefRecipe *R) {
102 const auto &[V, Inserted] = VPV2Parts.try_emplace(Key: R);
103 assert(Inserted && "uniform value already added");
104 for (unsigned Part = 0; Part != UF; ++Part)
105 V->second.push_back(Elt: R);
106 }
107
108 bool contains(VPValue *VPV) const { return VPV2Parts.contains(Val: VPV); }
109
110 /// Update \p R's operand at \p OpIdx with its corresponding VPValue for part
111 /// \p P.
112 void remapOperand(VPRecipeBase *R, unsigned OpIdx, unsigned Part) {
113 auto *Op = R->getOperand(N: OpIdx);
114 R->setOperand(I: OpIdx, New: getValueForPart(V: Op, Part));
115 }
116
117 /// Update \p R's operands with their corresponding VPValues for part \p P.
118 void remapOperands(VPRecipeBase *R, unsigned Part) {
119 for (const auto &[OpIdx, Op] : enumerate(First: R->operands()))
120 R->setOperand(I: OpIdx, New: getValueForPart(V: Op, Part));
121 }
122};
123} // namespace
124
125static void addStartIndexForScalarSteps(VPScalarIVStepsRecipe *Steps,
126 unsigned Part, VPlan &Plan) {
127 if (Part == 0)
128 return;
129
130 VPBuilder Builder(Steps);
131 Type *BaseIVTy = Steps->getOperand(N: 0)->getScalarType();
132 Type *IntStepTy =
133 IntegerType::get(C&: BaseIVTy->getContext(), NumBits: BaseIVTy->getScalarSizeInBits());
134 VPValue *StartIndex = Steps->getVFValue();
135 if (Part > 1) {
136 StartIndex = Builder.createOverflowingOp(
137 Opcode: Instruction::Mul,
138 Operands: {StartIndex, Plan.getConstantInt(Ty: StartIndex->getScalarType(), Val: Part)});
139 }
140 StartIndex = Builder.createScalarSExtOrTrunc(Op: StartIndex, ResultTy: IntStepTy,
141 DL: Steps->getDebugLoc());
142
143 if (BaseIVTy->isFloatingPointTy())
144 StartIndex = Builder.createScalarCast(Opcode: Instruction::SIToFP, Op: StartIndex,
145 ResultTy: BaseIVTy, DL: Steps->getDebugLoc());
146
147 Steps->setStartIndex(StartIndex);
148}
149
150void UnrollState::unrollReplicateRegionByUF(VPRegionBlock *VPR) {
151 VPBlockBase *InsertPt = VPR->getSingleSuccessor();
152 for (unsigned Part = 1; Part != UF; ++Part) {
153 auto *Copy = VPR->clone();
154 VPBlockUtils::insertBlockBefore(NewBlock: Copy, BlockPtr: InsertPt);
155
156 auto PartI = vp_depth_first_shallow(G: Copy->getEntry());
157 auto Part0 = vp_depth_first_shallow(G: VPR->getEntry());
158 for (const auto &[PartIVPBB, Part0VPBB] :
159 zip(t: VPBlockUtils::blocksAs<VPBasicBlock>(Range&: PartI),
160 u: VPBlockUtils::blocksAs<VPBasicBlock>(Range&: Part0))) {
161 for (const auto &[PartIR, Part0R] : zip(t&: *PartIVPBB, u&: *Part0VPBB)) {
162 remapOperands(R: &PartIR, Part);
163 if (auto *Steps = dyn_cast<VPScalarIVStepsRecipe>(Val: &PartIR))
164 addStartIndexForScalarSteps(Steps, Part, Plan);
165
166 addRecipeForPart(OrigR: &Part0R, CopyR: &PartIR, Part);
167 }
168 }
169 }
170}
171
172void UnrollState::unrollWidenInductionByUF(
173 VPWidenInductionRecipe *IV, VPBasicBlock::iterator InsertPtForPhi) {
174 VPBasicBlock *PH = cast<VPBasicBlock>(
175 Val: IV->getParent()->getEnclosingLoopRegion()->getSinglePredecessor());
176 Type *IVTy = IV->getScalarType();
177 auto &ID = IV->getInductionDescriptor();
178 FastMathFlags FMF;
179 VPIRFlags::WrapFlagsTy WrapFlags(false, false);
180 if (auto *IntOrFPInd = dyn_cast<VPWidenIntOrFpInductionRecipe>(Val: IV)) {
181 FMF = IntOrFPInd->getFastMathFlagsOrNone();
182 WrapFlags = IntOrFPInd->getNoWrapFlagsOrNone();
183 }
184
185 VPValue *ScalarStep = IV->getStepValue();
186 VPBuilder Builder(PH);
187 Type *VectorStepTy = IVTy->isPointerTy() ? ScalarStep->getScalarType() : IVTy;
188 VPInstruction *VectorStep = Builder.createNaryOp(
189 Opcode: VPInstruction::WideIVStep, Operands: {&Plan.getVF(), ScalarStep}, ResultTy: VectorStepTy, Flags: FMF,
190 DL: IV->getDebugLoc());
191
192 ToSkip.insert(Ptr: VectorStep);
193
194 // Now create recipes to compute the induction steps for part 1 .. UF. Part 0
195 // remains the header phi. Parts > 0 are computed by adding Step to the
196 // previous part. The header phi recipe will get 2 new operands: the step
197 // value for a single part and the last part, used to compute the backedge
198 // value during VPWidenInductionRecipe::execute.
199 // %Part.0 = VPWidenInductionRecipe %Start, %ScalarStep, %VectorStep, %Part.3
200 // %Part.1 = %Part.0 + %VectorStep
201 // %Part.2 = %Part.1 + %VectorStep
202 // %Part.3 = %Part.2 + %VectorStep
203 //
204 // The newly added recipes are added to ToSkip to avoid interleaving them
205 // again.
206 VPValue *Prev = IV;
207 Builder.setInsertPoint(TheBB: IV->getParent(), IP: InsertPtForPhi);
208 unsigned AddOpc;
209 VPIRFlags AddFlags;
210 if (IVTy->isPointerTy()) {
211 AddOpc = VPInstruction::WidePtrAdd;
212 AddFlags = GEPNoWrapFlags::none();
213 } else if (IVTy->isFloatingPointTy()) {
214 AddOpc = ID.getInductionOpcode();
215 AddFlags = FMF;
216 } else {
217 AddOpc = Instruction::Add;
218 AddFlags = WrapFlags;
219 if (cast<VPWidenIntOrFpInductionRecipe>(Val: IV)->isCanonical())
220 AddFlags = VPIRFlags::WrapFlagsTy(/*NUW=*/true, /*NSW=*/false);
221 }
222 for (unsigned Part = 1; Part != UF; ++Part) {
223 std::string Name =
224 Part > 1 ? "step.add." + std::to_string(val: Part) : "step.add";
225
226 VPInstruction *Add =
227 Builder.createNaryOp(Opcode: AddOpc,
228 Operands: {
229 Prev,
230 VectorStep,
231 },
232 Flags: AddFlags, DL: IV->getDebugLoc(), Name);
233 ToSkip.insert(Ptr: Add);
234 addRecipeForPart(OrigR: IV, CopyR: Add, Part);
235 Prev = Add;
236 }
237 IV->addUnrolledPartOperands(SplatVFStep: VectorStep, LastPart: Prev);
238}
239
240void UnrollState::unrollHeaderPHIByUF(VPHeaderPHIRecipe *R,
241 VPBasicBlock::iterator InsertPtForPhi) {
242 // First-order recurrences pass a single vector or scalar through their header
243 // phis, irrespective of interleaving.
244 if (isa<VPFirstOrderRecurrencePHIRecipe>(Val: R))
245 return;
246
247 // Generate step vectors for each unrolled part.
248 if (auto *IV = dyn_cast<VPWidenInductionRecipe>(Val: R)) {
249 unrollWidenInductionByUF(IV, InsertPtForPhi);
250 return;
251 }
252
253 auto *RdxPhi = dyn_cast<VPReductionPHIRecipe>(Val: R);
254 if (RdxPhi && RdxPhi->isOrdered())
255 return;
256
257 auto InsertPt = std::next(x: R->getIterator());
258 for (unsigned Part = 1; Part != UF; ++Part) {
259 VPRecipeBase *Copy = R->clone();
260 Copy->insertBefore(BB&: *R->getParent(), IP: InsertPt);
261 addRecipeForPart(OrigR: R, CopyR: Copy, Part);
262 if (RdxPhi) {
263 // If the start value is a ReductionStartVector, use the identity value
264 // (second operand) for unrolled parts. If the scaling factor is > 1,
265 // create a new ReductionStartVector with the scale factor and both
266 // operands set to the identity value.
267 if (auto *VPI = dyn_cast<VPInstruction>(Val: RdxPhi->getStartValue())) {
268 assert(VPI->getOpcode() == VPInstruction::ReductionStartVector &&
269 "unexpected start VPInstruction");
270 if (Part != 1)
271 continue;
272 VPValue *StartV;
273 if (match(V: VPI->getOperand(N: 2), P: m_One())) {
274 StartV = VPI->getOperand(N: 1);
275 } else {
276 auto *C = VPI->clone();
277 C->setOperand(I: 0, New: C->getOperand(N: 1));
278 C->insertAfter(InsertPos: VPI);
279 StartV = C;
280 }
281 for (unsigned Part = 1; Part != UF; ++Part)
282 VPV2Parts[VPI][Part - 1] = StartV;
283 }
284 } else {
285 assert(isa<VPActiveLaneMaskPHIRecipe>(R) &&
286 "unexpected header phi recipe not needing unrolled part");
287 }
288 }
289}
290
291/// Handle non-header-phi recipes.
292void UnrollState::unrollRecipeByUF(VPRecipeBase &R) {
293 if (match(V: &R, P: m_CombineOr(Ps: m_BranchOnCond(), Ps: m_BranchOnCount())))
294 return;
295
296 if (auto *VPI = dyn_cast<VPInstruction>(Val: &R)) {
297 if (vputils::onlyFirstPartUsed(Def: VPI)) {
298 addUniformForAllParts(R: VPI);
299 return;
300 }
301 }
302 if (auto *RepR = dyn_cast<VPReplicateRecipe>(Val: &R)) {
303 if (isa<StoreInst>(Val: RepR->getUnderlyingValue()) &&
304 RepR->getOperand(N: 1)->isDefinedOutsideLoopRegions()) {
305 // Stores to an invariant address only need to store the last part.
306 remapOperands(R: &R, Part: UF - 1);
307 return;
308 }
309 if (match(V: RepR,
310 P: m_Intrinsic<Intrinsic::experimental_noalias_scope_decl>())) {
311 addUniformForAllParts(R: RepR);
312 return;
313 }
314 }
315
316 // Unroll non-uniform recipes.
317 auto InsertPt = std::next(x: R.getIterator());
318 VPBasicBlock &VPBB = *R.getParent();
319 for (unsigned Part = 1; Part != UF; ++Part) {
320 VPRecipeBase *Copy = R.clone();
321 Copy->insertBefore(BB&: VPBB, IP: InsertPt);
322 addRecipeForPart(OrigR: &R, CopyR: Copy, Part);
323
324 // Phi operands are updated once all other recipes have been unrolled.
325 if (isa<VPWidenPHIRecipe>(Val: Copy))
326 continue;
327
328 VPValue *Op;
329 if (match(V: &R, P: m_VPInstruction<VPInstruction::FirstOrderRecurrenceSplice>(
330 Ops: m_VPValue(), Ops: m_VPValue(V&: Op)))) {
331 Copy->setOperand(I: 0, New: getValueForPart(V: Op, Part: Part - 1));
332 Copy->setOperand(I: 1, New: getValueForPart(V: Op, Part));
333 continue;
334 }
335 if (match(V: &R, P: m_VPInstruction<VPInstruction::ExtractVectorForPart>(
336 Ops: m_VPValue(V&: Op), Ops: m_VPValue()))) {
337 Copy->setOperand(I: 0, New: Op);
338 Copy->setOperand(I: 1, New: Plan.getConstantInt(BitWidth: 64, Val: Part));
339 continue;
340 }
341 if (isa<VPVectorPointerRecipe, VPWidenCanonicalIVRecipe>(Val: R)) {
342 VPBuilder Builder(&R);
343 const DataLayout &DL = Plan.getDataLayout();
344 Type *IndexTy =
345 isa<VPWidenCanonicalIVRecipe>(Val: R)
346 ? Plan.getVectorLoopRegion()->getCanonicalIVType()
347 : DL.getIndexType(PtrTy: R.getVPSingleValue()->getScalarType());
348 VPValue *VF = Builder.createScalarZExtOrTrunc(Op: &Plan.getVF(), ResultTy: IndexTy,
349 DL: DebugLoc::getUnknown());
350 // VFxUF does not wrap, so VF * Part also cannot wrap.
351 VPValue *VFxPart = Builder.createOverflowingOp(
352 Opcode: Instruction::Mul, Operands: {VF, Plan.getConstantInt(Ty: IndexTy, Val: Part)},
353 WrapFlags: {true, true});
354 if (auto *VecPtr = dyn_cast<VPVectorPointerRecipe>(Val: Copy))
355 VecPtr->addPerPartOffset(VFxPart);
356 else
357 cast<VPWidenCanonicalIVRecipe>(Val: Copy)->addPerPartStep(Step: VFxPart);
358 continue;
359 }
360 if (auto *Red = dyn_cast<VPReductionRecipe>(Val: &R)) {
361 auto *Phi = dyn_cast<VPReductionPHIRecipe>(Val: R.getOperand(N: 0));
362 if (Phi && Phi->isOrdered()) {
363 auto &Parts = VPV2Parts[Phi];
364 if (Part == 1) {
365 Parts.clear();
366 Parts.push_back(Elt: Red);
367 }
368 Parts.push_back(Elt: Copy->getVPSingleValue());
369 Phi->setOperand(I: 1, New: Copy->getVPSingleValue());
370 }
371 }
372 if (auto *VEPR = dyn_cast<VPVectorEndPointerRecipe>(Val: Copy)) {
373 // Materialize PartN offset for VectorEndPointer.
374 VEPR->setOperand(I: 0, New: R.getOperand(N: 0));
375 VEPR->setOperand(I: 1, New: R.getOperand(N: 1));
376 VEPR->materializeOffset(Part);
377 continue;
378 }
379
380 remapOperands(R: Copy, Part);
381
382 if (auto *ScalarIVSteps = dyn_cast<VPScalarIVStepsRecipe>(Val: Copy))
383 addStartIndexForScalarSteps(Steps: ScalarIVSteps, Part, Plan);
384
385 if (match(V: Copy,
386 P: m_VPInstruction<VPInstruction::CanonicalIVIncrementForPart>())) {
387 VPBuilder Builder(Copy);
388 VPValue *ScaledByPart = Builder.createOverflowingOp(
389 Opcode: Instruction::Mul, Operands: {Copy->getOperand(N: 1), getConstantInt(Part)});
390 Copy->setOperand(I: 1, New: ScaledByPart);
391 }
392 }
393 if (auto *VEPR = dyn_cast<VPVectorEndPointerRecipe>(Val: &R)) {
394 // Materialize Part0 offset for VectorEndPointer.
395 VEPR->materializeOffset();
396 }
397 if (auto *WideCanIV = dyn_cast<VPWidenCanonicalIVRecipe>(Val: &R)) {
398 // Set Part0 step for WidenCanonicalIV.
399 WideCanIV->addPerPartStep(Step: getConstantInt(Part: 0));
400 }
401}
402
403void UnrollState::unrollBlock(VPBlockBase *VPB) {
404 auto *VPR = dyn_cast<VPRegionBlock>(Val: VPB);
405 if (VPR) {
406 if (VPR->isReplicator())
407 return unrollReplicateRegionByUF(VPR);
408
409 // Traverse blocks in region in RPO to ensure defs are visited before uses
410 // across blocks.
411 ReversePostOrderTraversal<VPBlockShallowTraversalWrapper<VPBlockBase *>>
412 RPOT(VPR->getEntry());
413 for (VPBlockBase *VPB : RPOT)
414 unrollBlock(VPB);
415 return;
416 }
417
418 // VPB is a VPBasicBlock; unroll it, i.e., unroll its recipes.
419 auto *VPBB = cast<VPBasicBlock>(Val: VPB);
420 auto InsertPtForPhi = VPBB->getFirstNonPhi();
421 for (VPRecipeBase &R : make_early_inc_range(Range&: *VPBB)) {
422 if (ToSkip.contains(Ptr: &R) || isa<VPIRInstruction>(Val: &R))
423 continue;
424
425 // Add all VPValues for all parts to AnyOf, FirstActiveLaneMask and
426 // ComputeReductionResult which combine all parts to compute the final
427 // value.
428 VPValue *Op1;
429 if (match(V: &R, P: m_VPInstruction<VPInstruction::AnyOf>(Ops: m_VPValue(V&: Op1))) ||
430 match(V: &R, P: m_FirstActiveLane(Op0: m_VPValue(V&: Op1))) ||
431 match(V: &R, P: m_LastActiveLane(Op0: m_VPValue(V&: Op1))) ||
432 match(V: &R, P: m_ComputeReductionResult(Op0: m_VPValue(V&: Op1)))) {
433 auto *VPI = cast<VPInstruction>(Val: &R);
434 addUniformForAllParts(R: VPI);
435 for (unsigned Part = 1; Part != UF; ++Part)
436 VPI->addOperand(Op: getValueForPart(V: Op1, Part));
437 continue;
438 }
439 VPValue *Op0;
440 if (match(V: &R, P: m_ExtractLane(Op0: m_VPValue(V&: Op0), Op1: m_VPValue(V&: Op1)))) {
441 auto *VPI = cast<VPInstruction>(Val: &R);
442 addUniformForAllParts(R: VPI);
443 for (unsigned Part = 1; Part != UF; ++Part)
444 VPI->addOperand(Op: getValueForPart(V: Op1, Part));
445 continue;
446 }
447
448 VPValue *Op2;
449 if (match(V: &R, P: m_ExtractLastActive(Op0: m_VPValue(), Op1: m_VPValue(V&: Op1),
450 Op2: m_VPValue(V&: Op2)))) {
451 auto *VPI = cast<VPInstruction>(Val: &R);
452 addUniformForAllParts(R: VPI);
453 for (unsigned Part = 1; Part != UF; ++Part) {
454 VPI->addOperand(Op: getValueForPart(V: Op1, Part));
455 VPI->addOperand(Op: getValueForPart(V: Op2, Part));
456 }
457 continue;
458 }
459
460 if (Plan.hasScalarVFOnly()) {
461 if (match(V: &R, P: m_ExtractLastPart(Op0: m_VPValue(V&: Op0))) ||
462 match(V: &R, P: m_ExtractPenultimateElement(Op0: m_VPValue(V&: Op0)))) {
463 auto *I = cast<VPInstruction>(Val: &R);
464 bool IsPenultimatePart =
465 I->getOpcode() == VPInstruction::ExtractPenultimateElement;
466 unsigned PartIdx = IsPenultimatePart ? UF - 2 : UF - 1;
467 // For scalar VF, directly use the scalar part value.
468 I->replaceAllUsesWith(New: getValueForPart(V: Op0, Part: PartIdx));
469 continue;
470 }
471 }
472 // For vector VF, the penultimate element is always extracted from the last part.
473 if (match(V: &R, P: m_ExtractLastLaneOfLastPart(Op0: m_VPValue(V&: Op0))) ||
474 match(V: &R, P: m_ExtractPenultimateElement(Op0: m_VPValue(V&: Op0)))) {
475 addUniformForAllParts(R: cast<VPSingleDefRecipe>(Val: &R));
476 R.setOperand(I: 0, New: getValueForPart(V: Op0, Part: UF - 1));
477 continue;
478 }
479
480 if (match(V: &R,
481 P: m_WideActiveLaneMask(Op0: m_VPValue(), Op1: m_VPValue(), Op2: m_VPValue()))) {
482 auto *ALM = cast<VPInstruction>(Val: &R);
483 ALM->setOperand(I: 2, New: getConstantInt(Part: UF));
484 continue;
485 }
486
487 auto *SingleDef = dyn_cast<VPSingleDefRecipe>(Val: &R);
488 if (SingleDef && vputils::isUniformAcrossVFsAndUFs(V: SingleDef)) {
489 addUniformForAllParts(R: SingleDef);
490 continue;
491 }
492
493 if (auto *H = dyn_cast<VPHeaderPHIRecipe>(Val: &R)) {
494 unrollHeaderPHIByUF(R: H, InsertPtForPhi);
495 continue;
496 }
497
498 unrollRecipeByUF(R);
499 }
500}
501
502void VPlanTransforms::unrollByUF(VPlan &Plan, unsigned UF) {
503 assert(UF > 0 && "Unroll factor must be positive");
504 Plan.setUF(UF);
505 llvm::scope_exit Cleanup([&Plan, UF]() {
506 auto Iter = vp_depth_first_deep(G: Plan.getEntry());
507 // Remove recipes that are redundant after unrolling.
508 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(Range&: Iter)) {
509 for (VPRecipeBase &R : make_early_inc_range(Range&: *VPBB)) {
510 auto *VPI = dyn_cast<VPInstruction>(Val: &R);
511 if (VPI &&
512 VPI->getOpcode() == VPInstruction::CanonicalIVIncrementForPart &&
513 VPI->getOperand(N: 1) == &Plan.getVF()) {
514 VPI->replaceAllUsesWith(New: VPI->getOperand(N: 0));
515 VPI->eraseFromParent();
516 }
517 }
518 }
519
520 Type *TCTy = Plan.getTripCount()->getScalarType();
521 Plan.getUF().replaceAllUsesWith(New: Plan.getConstantInt(Ty: TCTy, Val: UF));
522 });
523 if (UF == 1) {
524 return;
525 }
526
527 UnrollState Unroller(Plan, UF);
528
529 // Iterate over all blocks in the plan starting from Entry, and unroll
530 // recipes inside them. This includes the vector preheader and middle blocks,
531 // which may set up or post-process per-part values.
532 ReversePostOrderTraversal<VPBlockShallowTraversalWrapper<VPBlockBase *>> RPOT(
533 Plan.getEntry());
534 for (VPBlockBase *VPB : RPOT)
535 Unroller.unrollBlock(VPB);
536
537 unsigned Part = 1;
538 // Remap operands of cloned header phis to update backedge values. The header
539 // phis cloned during unrolling are just after the header phi for part 0.
540 // Reset Part to 1 when reaching the first (part 0) recipe of a block.
541 for (VPRecipeBase &H :
542 Plan.getVectorLoopRegion()->getEntryBasicBlock()->phis()) {
543 // The second operand of Fixed Order Recurrence phi's, feeding the spliced
544 // value across the backedge, needs to remap to the last part of the spliced
545 // value.
546 if (isa<VPFirstOrderRecurrencePHIRecipe>(Val: &H)) {
547 Unroller.remapOperand(R: &H, OpIdx: 1, Part: UF - 1);
548 continue;
549 }
550 if (Unroller.contains(VPV: H.getVPSingleValue())) {
551 Part = 1;
552 continue;
553 }
554 Unroller.remapOperands(R: &H, Part);
555 Part++;
556 }
557
558 VPlanTransforms::removeDeadRecipes(Plan);
559}
560
561/// Add a lane offset to the start index of \p Steps.
562static void addLaneToStartIndex(VPScalarIVStepsRecipe *Steps, unsigned Lane,
563 VPlan &Plan, VPRecipeBase *InsertPt) {
564 assert(Lane > 0 && "Zero lane adds no offset to start index");
565 Type *BaseIVTy = Steps->getOperand(N: 0)->getScalarType();
566
567 VPValue *OldStartIndex = Steps->getStartIndex();
568 VPValue *LaneOffset;
569 unsigned AddOpcode;
570 // TODO: Retrieve the flags from Steps unconditionally.
571 VPIRFlags Flags;
572 if (BaseIVTy->isFloatingPointTy()) {
573 int SignedLane = static_cast<int>(Lane);
574 if (!OldStartIndex && Steps->getInductionOpcode() == Instruction::FSub)
575 SignedLane = -SignedLane;
576 LaneOffset = Plan.getOrAddLiveIn(V: ConstantFP::get(Ty: BaseIVTy, V: SignedLane));
577 AddOpcode = Steps->getInductionOpcode();
578 Flags = VPIRFlags(FastMathFlags());
579 } else {
580 unsigned BaseIVBits = BaseIVTy->getScalarSizeInBits();
581 LaneOffset = Plan.getConstantInt(
582 Val: APInt(BaseIVBits, Lane, /*isSigned*/ false, /*implicitTrunc*/ true));
583 AddOpcode = Instruction::Add;
584 Flags = VPIRFlags(VPIRFlags::WrapFlagsTy(false, false));
585 }
586
587 VPValue *NewStartIndex = LaneOffset;
588 if (OldStartIndex) {
589 VPBuilder Builder(InsertPt);
590 NewStartIndex =
591 Builder.createNaryOp(Opcode: AddOpcode, Operands: {OldStartIndex, LaneOffset}, Flags);
592 }
593 Steps->setStartIndex(NewStartIndex);
594}
595
596/// Create a single-scalar clone of \p DefR (must be a VPReplicateRecipe,
597/// VPInstruction or VPScalarIVStepsRecipe) for lane \p Lane. Use \p
598/// Def2LaneDefs to look up scalar definitions for operands of \DefR.
599static VPValue *
600cloneForLane(VPlan &Plan, VPBuilder &Builder, Type *IdxTy,
601 VPSingleDefRecipe *DefR, VPLane Lane,
602 const DenseMap<VPValue *, SmallVector<VPValue *>> &Def2LaneDefs) {
603 assert((isa<VPInstruction, VPReplicateRecipe, VPScalarIVStepsRecipe>(DefR)) &&
604 "DefR must be a VPReplicateRecipe, VPInstruction or "
605 "VPScalarIVStepsRecipe");
606 VPValue *Op;
607 if (match(R: DefR, P: m_VPInstruction<VPInstruction::Unpack>(Ops: m_VPValue(V&: Op)))) {
608 auto LaneDefs = Def2LaneDefs.find(Val: Op);
609 if (LaneDefs != Def2LaneDefs.end())
610 return LaneDefs->second[Lane.getKnownLane()];
611
612 VPValue *Idx = Plan.getConstantInt(Ty: IdxTy, Val: Lane.getKnownLane());
613 return Builder.createNaryOp(Opcode: Instruction::ExtractElement, Operands: {Op, Idx});
614 }
615
616 // Collect the operands at Lane, creating extracts as needed.
617 SmallVector<VPValue *> NewOps;
618 for (VPValue *Op : DefR->operands()) {
619 // If Op is a definition that has been unrolled, directly use the clone for
620 // the corresponding lane.
621 auto LaneDefs = Def2LaneDefs.find(Val: Op);
622 if (LaneDefs != Def2LaneDefs.end()) {
623 NewOps.push_back(Elt: LaneDefs->second[Lane.getKnownLane()]);
624 continue;
625 }
626 if (Lane.getKind() == VPLane::Kind::ScalableLast) {
627 // Look through mandatory Unpack.
628 [[maybe_unused]] bool Matched =
629 match(V: Op, P: m_VPInstruction<VPInstruction::Unpack>(Ops: m_VPValue(V&: Op)));
630 assert(Matched && "original op must have been Unpack");
631 auto *ExtractPart =
632 Builder.createNaryOp(Opcode: VPInstruction::ExtractLastPart, Operands: {Op});
633 NewOps.push_back(
634 Elt: Builder.createNaryOp(Opcode: VPInstruction::ExtractLastLane, Operands: {ExtractPart}));
635 continue;
636 }
637 if (vputils::isSingleScalar(VPV: Op)) {
638 NewOps.push_back(Elt: Op);
639 continue;
640 }
641
642 // Look through buildvector to avoid unnecessary extracts.
643 if (match(V: Op, P: m_BuildVector())) {
644 NewOps.push_back(
645 Elt: cast<VPInstruction>(Val: Op)->getOperand(N: Lane.getKnownLane()));
646 continue;
647 }
648 VPValue *Idx = Plan.getConstantInt(Ty: IdxTy, Val: Lane.getKnownLane());
649 VPValue *Ext = Builder.createNaryOp(Opcode: Instruction::ExtractElement, Operands: {Op, Idx});
650 NewOps.push_back(Elt: Ext);
651 }
652
653 VPSingleDefRecipe *New;
654 if (auto *RepR = dyn_cast<VPReplicateRecipe>(Val: DefR)) {
655 // TODO: have cloning of replicate recipes also provide the desired result
656 // coupled with setting its operands to NewOps (deriving IsSingleScalar and
657 // Mask from the operands?)
658 New = VPBuilder::createSingleScalarOp(
659 Opcode: RepR->getOpcode(), Operands: NewOps, /*Mask=*/nullptr, Flags: *RepR, Metadata: *RepR,
660 DL: RepR->getDebugLoc(), UV: RepR->getUnderlyingInstr());
661 } else {
662 New = DefR->clone();
663 for (const auto &[Idx, Op] : enumerate(First&: NewOps)) {
664 New->setOperand(I: Idx, New: Op);
665 }
666 if (auto *Steps = dyn_cast<VPScalarIVStepsRecipe>(Val: New)) {
667 // Skip lane 0: an absent start index is implicitly zero.
668 unsigned KnownLane = Lane.getKnownLane();
669 if (KnownLane != 0)
670 addLaneToStartIndex(Steps, Lane: KnownLane, Plan, InsertPt: DefR);
671 }
672 }
673 New->insertBefore(InsertPos: DefR);
674 return New;
675}
676
677/// Convert recipes in region blocks to operate on a single lane 0.
678/// VPReplicateRecipes are converted to single-scalar ones, branch-on-mask is
679/// converted into BranchOnCond, PredInstPhi recipes are replaced by scalar phi
680/// recipes with an additional poison operand, and extracts are created as
681/// needed.
682static void convertRecipesInRegionBlocksToSingleScalar(VPlan &Plan, Type *IdxTy,
683 VPBlockBase *Entry,
684 ElementCount VF) {
685 VPValue *Idx0 = Plan.getZero(Ty: IdxTy);
686 for (VPBlockBase *VPB : vp_depth_first_shallow(G: Entry)) {
687 for (VPRecipeBase &OldR : make_early_inc_range(Range&: cast<VPBasicBlock>(Val&: *VPB))) {
688 assert(
689 !isa<VPWidenPHIRecipe>(&OldR) &&
690 !match(&OldR,
691 m_CombineOr(
692 m_InsertElement(m_VPValue(), m_VPValue(), m_VPValue()),
693 m_ExtractElement(m_VPValue(), m_VPValue()))) &&
694 "must not contain wide phis, inserts or extracts before conversion");
695
696 VPBuilder Builder(&OldR);
697 DebugLoc OldDL = OldR.getDebugLoc();
698 // For scalar VF, operands are already scalar; no extraction needed.
699 if (!VF.isScalar()) {
700 for (const auto &[I, Op] : enumerate(First: OldR.operands())) {
701 // Skip operands that don't need extraction: values defined in the
702 // same block (already scalar), or values that are already single
703 // scalars.
704 // TODO: Support isSingleScalar for VPScalarIVStepsRecipe.
705 auto *DefR = Op->getDefiningRecipe();
706 if ((isa_and_present<VPScalarIVStepsRecipe>(Val: DefR) &&
707 DefR->getParent() == VPB) ||
708 vputils::isSingleScalar(VPV: Op))
709 continue;
710
711 // Extract lane zero from values defined outside the region.
712 VPValue *Extract = Builder.createNaryOp(Opcode: Instruction::ExtractElement,
713 Operands: {Op, Idx0}, DL: OldDL);
714 OldR.setOperand(I, New: Extract);
715 }
716 }
717
718 if (auto *RepR = dyn_cast<VPReplicateRecipe>(Val: &OldR)) {
719 auto *NewR = VPBuilder::createSingleScalarOp(
720 Opcode: RepR->getOpcode(), Operands: to_vector(Range: RepR->operands()), /*Mask=*/nullptr,
721 Flags: *RepR, Metadata: *RepR, DL: OldDL, UV: RepR->getUnderlyingInstr());
722 NewR->insertBefore(InsertPos: RepR);
723 RepR->replaceAllUsesWith(New: NewR);
724 RepR->eraseFromParent();
725 } else if (auto *BranchOnMask = dyn_cast<VPBranchOnMaskRecipe>(Val: &OldR)) {
726 Builder.createNaryOp(Opcode: VPInstruction::BranchOnCond,
727 Operands: {BranchOnMask->getOperand(N: 0)}, DL: OldDL);
728 BranchOnMask->eraseFromParent();
729 } else if (auto *PredPhi = dyn_cast<VPPredInstPHIRecipe>(Val: &OldR)) {
730 VPValue *PredOp = PredPhi->getOperand(N: 0);
731 Type *PredTy = PredOp->getScalarType();
732 VPValue *Poison = Plan.getPoison(Ty: PredTy);
733 VPPhi *NewPhi = Builder.createScalarPhi(IncomingValues: {Poison, PredOp}, DL: OldDL);
734 PredPhi->replaceAllUsesWith(New: NewPhi);
735 PredPhi->eraseFromParent();
736 } else {
737 // TODO: Support isSingleScalar for VPScalarIVStepsRecipe.
738 assert((isa<VPScalarIVStepsRecipe>(OldR) ||
739 (isa<VPInstruction>(OldR) &&
740 vputils::isSingleScalar(OldR.getVPSingleValue()))) &&
741 "unexpected unhandled recipe");
742 }
743 }
744 }
745}
746
747/// Update recipes in the cloned blocks rooted at \p NewEntry to match \p Lane,
748/// using the original blocks rooted at \p OldEntry as reference.
749static void processLaneForReplicateRegion(VPlan &Plan, Type *IdxTy,
750 unsigned Lane, VPBasicBlock *OldEntry,
751 VPBasicBlock *NewEntry) {
752 DenseMap<VPValue *, VPValue *> Old2NewVPValues;
753 VPValue *IdxLane = Plan.getConstantInt(Ty: IdxTy, Val: Lane);
754 for (const auto &[OldBB, NewBB] :
755 zip_equal(t: vp_depth_first_shallow(G: OldEntry),
756 u: vp_depth_first_shallow(G: NewEntry))) {
757 for (auto &&[OldR, NewR] :
758 zip_equal(t&: *cast<VPBasicBlock>(Val: OldBB), u&: *cast<VPBasicBlock>(Val: NewBB))) {
759 for (const auto &[OldV, NewV] :
760 zip_equal(t: OldR.definedValues(), u: NewR.definedValues()))
761 Old2NewVPValues[OldV] = NewV;
762
763 // Remap operands to use lane-specific values.
764 for (const auto &[I, OldOp] : enumerate(First: NewR.operands())) {
765 // Use cloned value if operand was defined in the region.
766 if (auto *NewOp = Old2NewVPValues.lookup(Val: OldOp))
767 NewR.setOperand(I, New: NewOp);
768 }
769
770 if (auto *Steps = dyn_cast<VPScalarIVStepsRecipe>(Val: &NewR)) {
771 addLaneToStartIndex(Steps, Lane, Plan, InsertPt: Steps);
772 } else if (match(V: &NewR, P: m_ExtractElement(Op0: m_VPValue(), Op1: m_VPValue()))) {
773 assert(match(NewR.getOperand(1), m_ZeroInt()) &&
774 "extract indices must be zero");
775 NewR.setOperand(I: 1, New: IdxLane);
776 } else if (auto *NewPhi = dyn_cast<VPPhi>(Val: &NewR)) {
777 auto *OldPhi = cast<VPPhi>(Val: &OldR);
778 assert(vputils::onlyFirstLaneUsed(OldPhi) &&
779 "VPPhis expected to have only first lane used");
780 auto *BVUser = dyn_cast_or_null<VPInstruction>(Val: OldPhi->getSingleUser());
781 if (BVUser && match(V: BVUser, P: m_CombineOr(Ps: m_BuildVector(),
782 Ps: m_BuildStructVector()))) {
783 assert(BVUser->getOperand(0) == OldPhi &&
784 "Unexpected first operand of build vector user");
785 BVUser->setOperand(I: Lane, New: NewPhi);
786 }
787 }
788 }
789 }
790}
791
792/// Dissolve a single replicate region by replicating its blocks for each lane
793/// of \p VF. The region is disconnected, its blocks are reparented, cloned for
794/// each lane, and reconnected in sequence.
795static void dissolveReplicateRegion(VPRegionBlock *Region, ElementCount VF,
796 VPlan &Plan, Type *IdxTy) {
797 auto *FirstLaneEntry = cast<VPBasicBlock>(Val: Region->getEntry());
798 auto *FirstLaneExiting = cast<VPBasicBlock>(Val: Region->getExiting());
799
800 // Disconnect and dissolve the region.
801 VPBlockBase *Predecessor = Region->getSinglePredecessor();
802 assert(Predecessor && "Replicate region must have a single predecessor");
803 auto *Successor = cast<VPBasicBlock>(Val: Region->getSingleSuccessor());
804 VPBlockUtils::disconnectBlocks(From: Predecessor, To: Region);
805 VPBlockUtils::disconnectBlocks(From: Region, To: Successor);
806
807 VPRegionBlock *ParentRegion = Region->getParent();
808 for (VPBlockBase *VPB : vp_depth_first_shallow(G: FirstLaneEntry))
809 VPB->setParent(ParentRegion);
810
811 // Process the original blocks for lane 0: converting their recipes to
812 // single-scalar.
813 convertRecipesInRegionBlocksToSingleScalar(Plan, IdxTy, Entry: FirstLaneEntry, VF);
814
815 // For scalar VF, just wire the blocks and return; no cloning or packing
816 // needed.
817 if (VF.isScalar()) {
818 VPBlockUtils::connectBlocks(From: Predecessor, To: FirstLaneEntry);
819 VPBlockUtils::connectBlocks(From: FirstLaneExiting, To: Successor);
820 return;
821 }
822
823 // Create a BuildVector or BuildStructVector in successor block for every
824 // VPPhi in (first lane's) exiting block having vector uses. All their
825 // operands are initialized to poison and will be replaced when processing
826 // each clone, except for the operand of the first lane which set here.
827 // BuildVectors are recorded to be replaced later by chains of insert-element
828 // and widen phi's.
829 unsigned NumLanes = VF.getFixedValue();
830 SmallVector<VPInstruction *> BuildVectors;
831 for (auto &R : FirstLaneExiting->phis()) {
832 auto *Phi = cast<VPPhi>(Val: &R);
833 if (vputils::onlyFirstLaneUsed(Def: Phi))
834 continue;
835
836 Type *ScalarTy = Phi->getScalarType();
837 bool IsStruct = isa<StructType>(Val: ScalarTy);
838 VPValue *Poison = Plan.getPoison(Ty: ScalarTy);
839 SmallVector<VPValue *> BVOps(NumLanes, Poison);
840 auto *BV = new VPInstruction(IsStruct ? VPInstruction::BuildStructVector
841 : VPInstruction::BuildVector,
842 BVOps);
843 if (!IsStruct)
844 BuildVectors.push_back(Elt: BV);
845 Phi->replaceAllUsesWith(New: BV);
846 BV->setOperand(I: 0, New: Phi);
847 BV->insertBefore(BB&: *Successor, IP: Successor->getFirstNonPhi());
848 }
849
850 // Clone converted blocks for remaining lanes and process each in reverse
851 // order, connecting each lane's Exiting block to the subsequent lane's entry.
852 VPBlockBase *NextLaneEntry = Successor;
853 for (int Lane = NumLanes - 1; Lane > 0; --Lane) {
854 const auto &[CurrentLaneEntry, CurrentLaneExiting] =
855 VPBlockUtils::cloneFrom(Entry: FirstLaneEntry);
856 for (VPBlockBase *VPB : vp_depth_first_shallow(G: CurrentLaneEntry))
857 VPB->setParent(ParentRegion);
858 processLaneForReplicateRegion(Plan, IdxTy, Lane,
859 OldEntry: cast<VPBasicBlock>(Val: FirstLaneEntry),
860 NewEntry: cast<VPBasicBlock>(Val: CurrentLaneEntry));
861 VPBlockUtils::connectBlocks(From: CurrentLaneExiting, To: NextLaneEntry);
862 NextLaneEntry = CurrentLaneEntry;
863 }
864
865 // Connect Predecessor to FirstLaneEntry, and FirstLaneRegionExit to
866 // NextLaneEntry which is the second lane region entry. The latter is
867 // done last so that earlier clonings from FirstLaneEntry stop at
868 // FirstLaneExiting.
869 VPBlockUtils::connectBlocks(From: Predecessor, To: FirstLaneEntry);
870 VPBlockUtils::connectBlocks(From: FirstLaneExiting, To: NextLaneEntry);
871
872 // Fold BuildVector fed by scalar phis into VPWidenPHIRecipes with
873 // InsertElement per lane.
874 // TODO: check if this folding should be dropped.
875 for (VPInstruction *BV : BuildVectors) {
876 assert(BV->getNumOperands() == NumLanes &&
877 "BuildVector must have one operand per lane");
878 for (const auto &[Idx, Op] : enumerate(First: BV->operands())) {
879 auto *ScalarPhi = cast<VPPhi>(Val: Op);
880 auto DL = ScalarPhi->getDebugLoc();
881 auto *PredOp = cast<VPSingleDefRecipe>(Val: ScalarPhi->getOperand(N: 1));
882 VPValue *Poison = ScalarPhi->getOperand(N: 0);
883 VPValue *PrevVal = Idx == 0 ? Poison : BV->getOperand(N: Idx - 1);
884 auto Builder = VPBuilder::getToInsertAfter(R: PredOp->getDefiningRecipe());
885 auto *Insert = Builder.createNaryOp(
886 Opcode: Instruction::InsertElement,
887 Operands: {PrevVal, PredOp, Plan.getConstantInt(BitWidth: 64, Val: Idx)}, DL);
888 Builder.setInsertPoint(ScalarPhi);
889 auto *NewPhi = Builder.createWidenPhi(IncomingValues: {PrevVal, Insert}, DL);
890 ScalarPhi->replaceAllUsesWith(New: NewPhi);
891 ScalarPhi->eraseFromParent();
892 }
893 BV->replaceAllUsesWith(New: BV->getOperand(N: NumLanes - 1));
894 BV->eraseFromParent();
895 }
896}
897
898/// Collect and dissolve all replicate regions in the vector loop, replicating
899/// their blocks and recipes for each lane of \p VF.
900static void replicateReplicateRegionsByVF(VPlan &Plan, ElementCount VF,
901 Type *IdxTy) {
902 // Collect all replicate regions before modifying the CFG.
903 SmallVector<VPRegionBlock *> ReplicateRegions;
904 for (VPRegionBlock *Region : VPBlockUtils::blocksOnly<VPRegionBlock>(
905 Range: vp_depth_first_shallow(G: Plan.getVectorLoopRegion()->getEntry()))) {
906 if (Region->isReplicator())
907 ReplicateRegions.push_back(Elt: Region);
908 }
909
910 assert((ReplicateRegions.empty() || !VF.isScalable()) &&
911 "cannot replicate across scalable VFs");
912
913 // Dissolve replicate regions by replicating their blocks for each lane.
914 // Traversing regions in reverse ensures that the successor of every region
915 // being processed is a basic-block, rather than another region.
916 for (VPRegionBlock *Region : reverse(C&: ReplicateRegions))
917 dissolveReplicateRegion(Region, VF, Plan, IdxTy);
918
919 VPlanTransforms::mergeBlocksIntoPredecessors(Plan);
920}
921
922void VPlanTransforms::replicateByVF(VPlan &Plan, ElementCount VF) {
923 Type *IdxTy = IntegerType::get(
924 C&: Plan.getScalarHeader()->getIRBasicBlock()->getContext(), NumBits: 32);
925
926 if (Plan.hasScalarVFOnly()) {
927 // When Plan is only unrolled by UF, replicating by VF amounts to dissolving
928 // replicate regions.
929 replicateReplicateRegionsByVF(Plan, VF, IdxTy);
930 return;
931 }
932
933 // Visit all VPBBs outside the loop region and directly inside the top-level
934 // loop region.
935 auto VPBBsOutsideLoopRegion = VPBlockUtils::blocksOnly<VPBasicBlock>(
936 Range: vp_depth_first_shallow(G: Plan.getEntry()));
937 auto VPBBsInsideLoopRegion = VPBlockUtils::blocksOnly<VPBasicBlock>(
938 Range: vp_depth_first_shallow(G: Plan.getVectorLoopRegion()->getEntry()));
939 auto VPBBsToUnroll =
940 concat<VPBasicBlock *>(Ranges&: VPBBsOutsideLoopRegion, Ranges&: VPBBsInsideLoopRegion);
941 // A mapping of current VPValue definitions to collections of new VPValues
942 // defined per lane. Serves to hook-up potential users of current VPValue
943 // definition that are replicated-per-VF later.
944 DenseMap<VPValue *, SmallVector<VPValue *>> Def2LaneDefs;
945 // The removal of current recipes being replaced by new ones needs to be
946 // delayed after Def2LaneDefs is no longer in use.
947 SmallVector<VPRecipeBase *> ToRemove;
948 for (VPBasicBlock *VPBB : VPBBsToUnroll) {
949 for (VPRecipeBase &R : make_early_inc_range(Range&: *VPBB)) {
950 if (!vputils::doesGeneratePerAllLanes(R: &R))
951 continue;
952
953 auto *DefR = cast<VPSingleDefRecipe>(Val: &R);
954 VPBuilder Builder(DefR);
955 if (DefR->user_empty()) {
956 // Create single-scalar version of DefR for all lanes.
957 for (unsigned I = 0; I != VF.getKnownMinValue(); ++I)
958 cloneForLane(Plan, Builder, IdxTy, DefR, Lane: VPLane(I), Def2LaneDefs);
959 DefR->eraseFromParent();
960 continue;
961 }
962 /// Create single-scalar version of DefR for all lanes.
963 SmallVector<VPValue *> LaneDefs;
964 for (unsigned I = 0; I != VF.getKnownMinValue(); ++I)
965 LaneDefs.push_back(
966 Elt: cloneForLane(Plan, Builder, IdxTy, DefR, Lane: VPLane(I), Def2LaneDefs));
967
968 Def2LaneDefs[DefR] = LaneDefs;
969 /// Users that only demand the first lane can use the definition for lane
970 /// 0.
971 DefR->replaceUsesWithIf(New: LaneDefs[0], ShouldReplace: [DefR](VPUser &U, unsigned) {
972 if (U.usesFirstLaneOnly(Op: DefR))
973 return true;
974 auto *VPI = dyn_cast<VPInstructionWithType>(Val: &U);
975 return VPI && Instruction::isCast(Opcode: VPI->getOpcode());
976 });
977
978 // Update each build vector user that currently has DefR as its only
979 // operand, to have all LaneDefs as its operands.
980 for (VPUser *U : to_vector(Range: DefR->users())) {
981 auto *VPI = dyn_cast<VPInstruction>(Val: U);
982 if (!VPI || (VPI->getOpcode() != VPInstruction::BuildVector &&
983 VPI->getOpcode() != VPInstruction::BuildStructVector))
984 continue;
985 assert(VPI->getNumOperands() == 1 &&
986 "Build(Struct)Vector must have a single operand before "
987 "replicating by VF");
988 VPI->setOperand(I: 0, New: LaneDefs[0]);
989 for (VPValue *LaneDef : drop_begin(RangeOrContainer&: LaneDefs))
990 VPI->addOperand(Op: LaneDef);
991 }
992 ToRemove.push_back(Elt: DefR);
993 }
994 }
995 for (auto *R : reverse(C&: ToRemove))
996 R->eraseFromParent();
997
998 replicateReplicateRegionsByVF(Plan, VF, IdxTy);
999}
1000