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 (isa<VPVectorPointerRecipe, VPWidenCanonicalIVRecipe>(Val: R)) {
336 VPBuilder Builder(&R);
337 const DataLayout &DL = Plan.getDataLayout();
338 Type *IndexTy =
339 isa<VPWidenCanonicalIVRecipe>(Val: R)
340 ? Plan.getVectorLoopRegion()->getCanonicalIVType()
341 : DL.getIndexType(PtrTy: R.getVPSingleValue()->getScalarType());
342 VPValue *VF = Builder.createScalarZExtOrTrunc(Op: &Plan.getVF(), ResultTy: IndexTy,
343 DL: DebugLoc::getUnknown());
344 // VFxUF does not wrap, so VF * Part also cannot wrap.
345 VPValue *VFxPart = Builder.createOverflowingOp(
346 Opcode: Instruction::Mul, Operands: {VF, Plan.getConstantInt(Ty: IndexTy, Val: Part)},
347 WrapFlags: {true, true});
348 if (auto *VecPtr = dyn_cast<VPVectorPointerRecipe>(Val: Copy))
349 VecPtr->addPerPartOffset(VFxPart);
350 else
351 cast<VPWidenCanonicalIVRecipe>(Val: Copy)->addPerPartStep(Step: VFxPart);
352 continue;
353 }
354 if (auto *Red = dyn_cast<VPReductionRecipe>(Val: &R)) {
355 auto *Phi = dyn_cast<VPReductionPHIRecipe>(Val: R.getOperand(N: 0));
356 if (Phi && Phi->isOrdered()) {
357 auto &Parts = VPV2Parts[Phi];
358 if (Part == 1) {
359 Parts.clear();
360 Parts.push_back(Elt: Red);
361 }
362 Parts.push_back(Elt: Copy->getVPSingleValue());
363 Phi->setOperand(I: 1, New: Copy->getVPSingleValue());
364 }
365 }
366 if (auto *VEPR = dyn_cast<VPVectorEndPointerRecipe>(Val: Copy)) {
367 // Materialize PartN offset for VectorEndPointer.
368 VEPR->setOperand(I: 0, New: R.getOperand(N: 0));
369 VEPR->setOperand(I: 1, New: R.getOperand(N: 1));
370 VEPR->materializeOffset(Part);
371 continue;
372 }
373
374 remapOperands(R: Copy, Part);
375
376 if (auto *ScalarIVSteps = dyn_cast<VPScalarIVStepsRecipe>(Val: Copy))
377 addStartIndexForScalarSteps(Steps: ScalarIVSteps, Part, Plan);
378
379 if (match(V: Copy,
380 P: m_VPInstruction<VPInstruction::CanonicalIVIncrementForPart>())) {
381 VPBuilder Builder(Copy);
382 VPValue *ScaledByPart = Builder.createOverflowingOp(
383 Opcode: Instruction::Mul, Operands: {Copy->getOperand(N: 1), getConstantInt(Part)});
384 Copy->setOperand(I: 1, New: ScaledByPart);
385 }
386 }
387 if (auto *VEPR = dyn_cast<VPVectorEndPointerRecipe>(Val: &R)) {
388 // Materialize Part0 offset for VectorEndPointer.
389 VEPR->materializeOffset();
390 }
391 if (auto *WideCanIV = dyn_cast<VPWidenCanonicalIVRecipe>(Val: &R)) {
392 // Set Part0 step for WidenCanonicalIV.
393 WideCanIV->addPerPartStep(Step: getConstantInt(Part: 0));
394 }
395}
396
397void UnrollState::unrollBlock(VPBlockBase *VPB) {
398 auto *VPR = dyn_cast<VPRegionBlock>(Val: VPB);
399 if (VPR) {
400 if (VPR->isReplicator())
401 return unrollReplicateRegionByUF(VPR);
402
403 // Traverse blocks in region in RPO to ensure defs are visited before uses
404 // across blocks.
405 ReversePostOrderTraversal<VPBlockShallowTraversalWrapper<VPBlockBase *>>
406 RPOT(VPR->getEntry());
407 for (VPBlockBase *VPB : RPOT)
408 unrollBlock(VPB);
409 return;
410 }
411
412 // VPB is a VPBasicBlock; unroll it, i.e., unroll its recipes.
413 auto *VPBB = cast<VPBasicBlock>(Val: VPB);
414 auto InsertPtForPhi = VPBB->getFirstNonPhi();
415 for (VPRecipeBase &R : make_early_inc_range(Range&: *VPBB)) {
416 if (ToSkip.contains(Ptr: &R) || isa<VPIRInstruction>(Val: &R))
417 continue;
418
419 // Add all VPValues for all parts to AnyOf, FirstActiveLaneMask and
420 // ComputeReductionResult which combine all parts to compute the final
421 // value.
422 VPValue *Op1;
423 if (match(V: &R, P: m_VPInstruction<VPInstruction::AnyOf>(Ops: m_VPValue(V&: Op1))) ||
424 match(V: &R, P: m_FirstActiveLane(Op0: m_VPValue(V&: Op1))) ||
425 match(V: &R, P: m_LastActiveLane(Op0: m_VPValue(V&: Op1))) ||
426 match(V: &R, P: m_ComputeReductionResult(Op0: m_VPValue(V&: Op1)))) {
427 auto *VPI = cast<VPInstruction>(Val: &R);
428 addUniformForAllParts(R: VPI);
429 for (unsigned Part = 1; Part != UF; ++Part)
430 VPI->addOperand(Op: getValueForPart(V: Op1, Part));
431 continue;
432 }
433 VPValue *Op0;
434 if (match(V: &R, P: m_ExtractLane(Op0: m_VPValue(V&: Op0), Op1: m_VPValue(V&: Op1)))) {
435 auto *VPI = cast<VPInstruction>(Val: &R);
436 addUniformForAllParts(R: VPI);
437 for (unsigned Part = 1; Part != UF; ++Part)
438 VPI->addOperand(Op: getValueForPart(V: Op1, Part));
439 continue;
440 }
441
442 VPValue *Op2;
443 if (match(V: &R, P: m_ExtractLastActive(Op0: m_VPValue(), Op1: m_VPValue(V&: Op1),
444 Op2: m_VPValue(V&: Op2)))) {
445 auto *VPI = cast<VPInstruction>(Val: &R);
446 addUniformForAllParts(R: VPI);
447 for (unsigned Part = 1; Part != UF; ++Part) {
448 VPI->addOperand(Op: getValueForPart(V: Op1, Part));
449 VPI->addOperand(Op: getValueForPart(V: Op2, Part));
450 }
451 continue;
452 }
453
454 if (Plan.hasScalarVFOnly()) {
455 if (match(V: &R, P: m_ExtractLastPart(Op0: m_VPValue(V&: Op0))) ||
456 match(V: &R, P: m_ExtractPenultimateElement(Op0: m_VPValue(V&: Op0)))) {
457 auto *I = cast<VPInstruction>(Val: &R);
458 bool IsPenultimatePart =
459 I->getOpcode() == VPInstruction::ExtractPenultimateElement;
460 unsigned PartIdx = IsPenultimatePart ? UF - 2 : UF - 1;
461 // For scalar VF, directly use the scalar part value.
462 I->replaceAllUsesWith(New: getValueForPart(V: Op0, Part: PartIdx));
463 continue;
464 }
465 }
466 // For vector VF, the penultimate element is always extracted from the last part.
467 if (match(V: &R, P: m_ExtractLastLaneOfLastPart(Op0: m_VPValue(V&: Op0))) ||
468 match(V: &R, P: m_ExtractPenultimateElement(Op0: m_VPValue(V&: Op0)))) {
469 addUniformForAllParts(R: cast<VPSingleDefRecipe>(Val: &R));
470 R.setOperand(I: 0, New: getValueForPart(V: Op0, Part: UF - 1));
471 continue;
472 }
473
474 auto *SingleDef = dyn_cast<VPSingleDefRecipe>(Val: &R);
475 if (SingleDef && vputils::isUniformAcrossVFsAndUFs(V: SingleDef)) {
476 addUniformForAllParts(R: SingleDef);
477 continue;
478 }
479
480 if (auto *H = dyn_cast<VPHeaderPHIRecipe>(Val: &R)) {
481 unrollHeaderPHIByUF(R: H, InsertPtForPhi);
482 continue;
483 }
484
485 unrollRecipeByUF(R);
486 }
487}
488
489void VPlanTransforms::unrollByUF(VPlan &Plan, unsigned UF) {
490 assert(UF > 0 && "Unroll factor must be positive");
491 Plan.setUF(UF);
492 llvm::scope_exit Cleanup([&Plan, UF]() {
493 auto Iter = vp_depth_first_deep(G: Plan.getEntry());
494 // Remove recipes that are redundant after unrolling.
495 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(Range&: Iter)) {
496 for (VPRecipeBase &R : make_early_inc_range(Range&: *VPBB)) {
497 auto *VPI = dyn_cast<VPInstruction>(Val: &R);
498 if (VPI &&
499 VPI->getOpcode() == VPInstruction::CanonicalIVIncrementForPart &&
500 VPI->getOperand(N: 1) == &Plan.getVF()) {
501 VPI->replaceAllUsesWith(New: VPI->getOperand(N: 0));
502 VPI->eraseFromParent();
503 }
504 }
505 }
506
507 Type *TCTy = Plan.getTripCount()->getScalarType();
508 Plan.getUF().replaceAllUsesWith(New: Plan.getConstantInt(Ty: TCTy, Val: UF));
509 });
510 if (UF == 1) {
511 return;
512 }
513
514 UnrollState Unroller(Plan, UF);
515
516 // Iterate over all blocks in the plan starting from Entry, and unroll
517 // recipes inside them. This includes the vector preheader and middle blocks,
518 // which may set up or post-process per-part values.
519 ReversePostOrderTraversal<VPBlockShallowTraversalWrapper<VPBlockBase *>> RPOT(
520 Plan.getEntry());
521 for (VPBlockBase *VPB : RPOT)
522 Unroller.unrollBlock(VPB);
523
524 unsigned Part = 1;
525 // Remap operands of cloned header phis to update backedge values. The header
526 // phis cloned during unrolling are just after the header phi for part 0.
527 // Reset Part to 1 when reaching the first (part 0) recipe of a block.
528 for (VPRecipeBase &H :
529 Plan.getVectorLoopRegion()->getEntryBasicBlock()->phis()) {
530 // The second operand of Fixed Order Recurrence phi's, feeding the spliced
531 // value across the backedge, needs to remap to the last part of the spliced
532 // value.
533 if (isa<VPFirstOrderRecurrencePHIRecipe>(Val: &H)) {
534 Unroller.remapOperand(R: &H, OpIdx: 1, Part: UF - 1);
535 continue;
536 }
537 if (Unroller.contains(VPV: H.getVPSingleValue())) {
538 Part = 1;
539 continue;
540 }
541 Unroller.remapOperands(R: &H, Part);
542 Part++;
543 }
544
545 VPlanTransforms::removeDeadRecipes(Plan);
546}
547
548/// Add a lane offset to the start index of \p Steps.
549static void addLaneToStartIndex(VPScalarIVStepsRecipe *Steps, unsigned Lane,
550 VPlan &Plan, VPRecipeBase *InsertPt) {
551 assert(Lane > 0 && "Zero lane adds no offset to start index");
552 Type *BaseIVTy = Steps->getOperand(N: 0)->getScalarType();
553
554 VPValue *OldStartIndex = Steps->getStartIndex();
555 VPValue *LaneOffset;
556 unsigned AddOpcode;
557 // TODO: Retrieve the flags from Steps unconditionally.
558 VPIRFlags Flags;
559 if (BaseIVTy->isFloatingPointTy()) {
560 int SignedLane = static_cast<int>(Lane);
561 if (!OldStartIndex && Steps->getInductionOpcode() == Instruction::FSub)
562 SignedLane = -SignedLane;
563 LaneOffset = Plan.getOrAddLiveIn(V: ConstantFP::get(Ty: BaseIVTy, V: SignedLane));
564 AddOpcode = Steps->getInductionOpcode();
565 Flags = VPIRFlags(FastMathFlags());
566 } else {
567 unsigned BaseIVBits = BaseIVTy->getScalarSizeInBits();
568 LaneOffset = Plan.getConstantInt(
569 Val: APInt(BaseIVBits, Lane, /*isSigned*/ false, /*implicitTrunc*/ true));
570 AddOpcode = Instruction::Add;
571 Flags = VPIRFlags(VPIRFlags::WrapFlagsTy(false, false));
572 }
573
574 VPValue *NewStartIndex = LaneOffset;
575 if (OldStartIndex) {
576 VPBuilder Builder(InsertPt);
577 NewStartIndex =
578 Builder.createNaryOp(Opcode: AddOpcode, Operands: {OldStartIndex, LaneOffset}, Flags);
579 }
580 Steps->setStartIndex(NewStartIndex);
581}
582
583/// Create a single-scalar clone of \p DefR (must be a VPReplicateRecipe,
584/// VPInstruction or VPScalarIVStepsRecipe) for lane \p Lane. Use \p
585/// Def2LaneDefs to look up scalar definitions for operands of \DefR.
586static VPValue *
587cloneForLane(VPlan &Plan, VPBuilder &Builder, Type *IdxTy,
588 VPSingleDefRecipe *DefR, VPLane Lane,
589 const DenseMap<VPValue *, SmallVector<VPValue *>> &Def2LaneDefs) {
590 assert((isa<VPInstruction, VPReplicateRecipe, VPScalarIVStepsRecipe>(DefR)) &&
591 "DefR must be a VPReplicateRecipe, VPInstruction or "
592 "VPScalarIVStepsRecipe");
593 VPValue *Op;
594 if (match(R: DefR, P: m_VPInstruction<VPInstruction::Unpack>(Ops: m_VPValue(V&: Op)))) {
595 auto LaneDefs = Def2LaneDefs.find(Val: Op);
596 if (LaneDefs != Def2LaneDefs.end())
597 return LaneDefs->second[Lane.getKnownLane()];
598
599 VPValue *Idx = Plan.getConstantInt(Ty: IdxTy, Val: Lane.getKnownLane());
600 return Builder.createNaryOp(Opcode: Instruction::ExtractElement, Operands: {Op, Idx});
601 }
602
603 // Collect the operands at Lane, creating extracts as needed.
604 SmallVector<VPValue *> NewOps;
605 for (VPValue *Op : DefR->operands()) {
606 // If Op is a definition that has been unrolled, directly use the clone for
607 // the corresponding lane.
608 auto LaneDefs = Def2LaneDefs.find(Val: Op);
609 if (LaneDefs != Def2LaneDefs.end()) {
610 NewOps.push_back(Elt: LaneDefs->second[Lane.getKnownLane()]);
611 continue;
612 }
613 if (Lane.getKind() == VPLane::Kind::ScalableLast) {
614 // Look through mandatory Unpack.
615 [[maybe_unused]] bool Matched =
616 match(V: Op, P: m_VPInstruction<VPInstruction::Unpack>(Ops: m_VPValue(V&: Op)));
617 assert(Matched && "original op must have been Unpack");
618 auto *ExtractPart =
619 Builder.createNaryOp(Opcode: VPInstruction::ExtractLastPart, Operands: {Op});
620 NewOps.push_back(
621 Elt: Builder.createNaryOp(Opcode: VPInstruction::ExtractLastLane, Operands: {ExtractPart}));
622 continue;
623 }
624 if (vputils::isSingleScalar(VPV: Op)) {
625 NewOps.push_back(Elt: Op);
626 continue;
627 }
628
629 // Look through buildvector to avoid unnecessary extracts.
630 if (match(V: Op, P: m_BuildVector())) {
631 NewOps.push_back(
632 Elt: cast<VPInstruction>(Val: Op)->getOperand(N: Lane.getKnownLane()));
633 continue;
634 }
635 VPValue *Idx = Plan.getConstantInt(Ty: IdxTy, Val: Lane.getKnownLane());
636 VPValue *Ext = Builder.createNaryOp(Opcode: Instruction::ExtractElement, Operands: {Op, Idx});
637 NewOps.push_back(Elt: Ext);
638 }
639
640 VPSingleDefRecipe *New;
641 if (auto *RepR = dyn_cast<VPReplicateRecipe>(Val: DefR)) {
642 // TODO: have cloning of replicate recipes also provide the desired result
643 // coupled with setting its operands to NewOps (deriving IsSingleScalar and
644 // Mask from the operands?)
645 New = VPBuilder::createSingleScalarOp(
646 Opcode: RepR->getOpcode(), Operands: NewOps, /*Mask=*/nullptr, Flags: *RepR, Metadata: *RepR,
647 DL: RepR->getDebugLoc(), UV: RepR->getUnderlyingInstr());
648 } else {
649 New = DefR->clone();
650 for (const auto &[Idx, Op] : enumerate(First&: NewOps)) {
651 New->setOperand(I: Idx, New: Op);
652 }
653 if (auto *Steps = dyn_cast<VPScalarIVStepsRecipe>(Val: New)) {
654 // Skip lane 0: an absent start index is implicitly zero.
655 unsigned KnownLane = Lane.getKnownLane();
656 if (KnownLane != 0)
657 addLaneToStartIndex(Steps, Lane: KnownLane, Plan, InsertPt: DefR);
658 }
659 }
660 New->insertBefore(InsertPos: DefR);
661 return New;
662}
663
664/// Convert recipes in region blocks to operate on a single lane 0.
665/// VPReplicateRecipes are converted to single-scalar ones, branch-on-mask is
666/// converted into BranchOnCond, PredInstPhi recipes are replaced by scalar phi
667/// recipes with an additional poison operand, and extracts are created as
668/// needed.
669static void convertRecipesInRegionBlocksToSingleScalar(VPlan &Plan, Type *IdxTy,
670 VPBlockBase *Entry,
671 ElementCount VF) {
672 VPValue *Idx0 = Plan.getZero(Ty: IdxTy);
673 for (VPBlockBase *VPB : vp_depth_first_shallow(G: Entry)) {
674 for (VPRecipeBase &OldR : make_early_inc_range(Range&: cast<VPBasicBlock>(Val&: *VPB))) {
675 assert(
676 !isa<VPWidenPHIRecipe>(&OldR) &&
677 !match(&OldR,
678 m_CombineOr(
679 m_InsertElement(m_VPValue(), m_VPValue(), m_VPValue()),
680 m_ExtractElement(m_VPValue(), m_VPValue()))) &&
681 "must not contain wide phis, inserts or extracts before conversion");
682
683 VPBuilder Builder(&OldR);
684 DebugLoc OldDL = OldR.getDebugLoc();
685 // For scalar VF, operands are already scalar; no extraction needed.
686 if (!VF.isScalar()) {
687 for (const auto &[I, Op] : enumerate(First: OldR.operands())) {
688 // Skip operands that don't need extraction: values defined in the
689 // same block (already scalar), or values that are already single
690 // scalars.
691 // TODO: Support isSingleScalar for VPScalarIVStepsRecipe.
692 auto *DefR = Op->getDefiningRecipe();
693 if ((isa_and_present<VPScalarIVStepsRecipe>(Val: DefR) &&
694 DefR->getParent() == VPB) ||
695 vputils::isSingleScalar(VPV: Op))
696 continue;
697
698 // Extract lane zero from values defined outside the region.
699 VPValue *Extract = Builder.createNaryOp(Opcode: Instruction::ExtractElement,
700 Operands: {Op, Idx0}, DL: OldDL);
701 OldR.setOperand(I, New: Extract);
702 }
703 }
704
705 if (auto *RepR = dyn_cast<VPReplicateRecipe>(Val: &OldR)) {
706 auto *NewR = VPBuilder::createSingleScalarOp(
707 Opcode: RepR->getOpcode(), Operands: to_vector(Range: RepR->operands()), /*Mask=*/nullptr,
708 Flags: *RepR, Metadata: *RepR, DL: OldDL, UV: RepR->getUnderlyingInstr());
709 NewR->insertBefore(InsertPos: RepR);
710 RepR->replaceAllUsesWith(New: NewR);
711 RepR->eraseFromParent();
712 } else if (auto *BranchOnMask = dyn_cast<VPBranchOnMaskRecipe>(Val: &OldR)) {
713 Builder.createNaryOp(Opcode: VPInstruction::BranchOnCond,
714 Operands: {BranchOnMask->getOperand(N: 0)}, DL: OldDL);
715 BranchOnMask->eraseFromParent();
716 } else if (auto *PredPhi = dyn_cast<VPPredInstPHIRecipe>(Val: &OldR)) {
717 VPValue *PredOp = PredPhi->getOperand(N: 0);
718 Type *PredTy = PredOp->getScalarType();
719 VPValue *Poison = Plan.getPoison(Ty: PredTy);
720 VPPhi *NewPhi = Builder.createScalarPhi(IncomingValues: {Poison, PredOp}, DL: OldDL);
721 PredPhi->replaceAllUsesWith(New: NewPhi);
722 PredPhi->eraseFromParent();
723 } else {
724 // TODO: Support isSingleScalar for VPScalarIVStepsRecipe.
725 assert((isa<VPScalarIVStepsRecipe>(OldR) ||
726 (isa<VPInstruction>(OldR) &&
727 vputils::isSingleScalar(OldR.getVPSingleValue()))) &&
728 "unexpected unhandled recipe");
729 }
730 }
731 }
732}
733
734/// Update recipes in the cloned blocks rooted at \p NewEntry to match \p Lane,
735/// using the original blocks rooted at \p OldEntry as reference.
736static void processLaneForReplicateRegion(VPlan &Plan, Type *IdxTy,
737 unsigned Lane, VPBasicBlock *OldEntry,
738 VPBasicBlock *NewEntry) {
739 DenseMap<VPValue *, VPValue *> Old2NewVPValues;
740 VPValue *IdxLane = Plan.getConstantInt(Ty: IdxTy, Val: Lane);
741 for (const auto &[OldBB, NewBB] :
742 zip_equal(t: vp_depth_first_shallow(G: OldEntry),
743 u: vp_depth_first_shallow(G: NewEntry))) {
744 for (auto &&[OldR, NewR] :
745 zip_equal(t&: *cast<VPBasicBlock>(Val: OldBB), u&: *cast<VPBasicBlock>(Val: NewBB))) {
746 for (const auto &[OldV, NewV] :
747 zip_equal(t: OldR.definedValues(), u: NewR.definedValues()))
748 Old2NewVPValues[OldV] = NewV;
749
750 // Remap operands to use lane-specific values.
751 for (const auto &[I, OldOp] : enumerate(First: NewR.operands())) {
752 // Use cloned value if operand was defined in the region.
753 if (auto *NewOp = Old2NewVPValues.lookup(Val: OldOp))
754 NewR.setOperand(I, New: NewOp);
755 }
756
757 if (auto *Steps = dyn_cast<VPScalarIVStepsRecipe>(Val: &NewR)) {
758 addLaneToStartIndex(Steps, Lane, Plan, InsertPt: Steps);
759 } else if (match(V: &NewR, P: m_ExtractElement(Op0: m_VPValue(), Op1: m_VPValue()))) {
760 assert(match(NewR.getOperand(1), m_ZeroInt()) &&
761 "extract indices must be zero");
762 NewR.setOperand(I: 1, New: IdxLane);
763 } else if (auto *NewPhi = dyn_cast<VPPhi>(Val: &NewR)) {
764 auto *OldPhi = cast<VPPhi>(Val: &OldR);
765 assert(vputils::onlyFirstLaneUsed(OldPhi) &&
766 "VPPhis expected to have only first lane used");
767 auto *BVUser = dyn_cast_or_null<VPInstruction>(Val: OldPhi->getSingleUser());
768 if (BVUser && match(V: BVUser, P: m_CombineOr(Ps: m_BuildVector(),
769 Ps: m_BuildStructVector()))) {
770 assert(BVUser->getOperand(0) == OldPhi &&
771 "Unexpected first operand of build vector user");
772 BVUser->setOperand(I: Lane, New: NewPhi);
773 }
774 }
775 }
776 }
777}
778
779/// Dissolve a single replicate region by replicating its blocks for each lane
780/// of \p VF. The region is disconnected, its blocks are reparented, cloned for
781/// each lane, and reconnected in sequence.
782static void dissolveReplicateRegion(VPRegionBlock *Region, ElementCount VF,
783 VPlan &Plan, Type *IdxTy) {
784 auto *FirstLaneEntry = cast<VPBasicBlock>(Val: Region->getEntry());
785 auto *FirstLaneExiting = cast<VPBasicBlock>(Val: Region->getExiting());
786
787 // Disconnect and dissolve the region.
788 VPBlockBase *Predecessor = Region->getSinglePredecessor();
789 assert(Predecessor && "Replicate region must have a single predecessor");
790 auto *Successor = cast<VPBasicBlock>(Val: Region->getSingleSuccessor());
791 VPBlockUtils::disconnectBlocks(From: Predecessor, To: Region);
792 VPBlockUtils::disconnectBlocks(From: Region, To: Successor);
793
794 VPRegionBlock *ParentRegion = Region->getParent();
795 for (VPBlockBase *VPB : vp_depth_first_shallow(G: FirstLaneEntry))
796 VPB->setParent(ParentRegion);
797
798 // Process the original blocks for lane 0: converting their recipes to
799 // single-scalar.
800 convertRecipesInRegionBlocksToSingleScalar(Plan, IdxTy, Entry: FirstLaneEntry, VF);
801
802 // For scalar VF, just wire the blocks and return; no cloning or packing
803 // needed.
804 if (VF.isScalar()) {
805 VPBlockUtils::connectBlocks(From: Predecessor, To: FirstLaneEntry);
806 VPBlockUtils::connectBlocks(From: FirstLaneExiting, To: Successor);
807 return;
808 }
809
810 // Create a BuildVector or BuildStructVector in successor block for every
811 // VPPhi in (first lane's) exiting block having vector uses. All their
812 // operands are initialized to poison and will be replaced when processing
813 // each clone, except for the operand of the first lane which set here.
814 // BuildVectors are recorded to be replaced later by chains of insert-element
815 // and widen phi's.
816 unsigned NumLanes = VF.getFixedValue();
817 SmallVector<VPInstruction *> BuildVectors;
818 for (auto &R : FirstLaneExiting->phis()) {
819 auto *Phi = cast<VPPhi>(Val: &R);
820 if (vputils::onlyFirstLaneUsed(Def: Phi))
821 continue;
822
823 Type *ScalarTy = Phi->getScalarType();
824 bool IsStruct = isa<StructType>(Val: ScalarTy);
825 VPValue *Poison = Plan.getPoison(Ty: ScalarTy);
826 SmallVector<VPValue *> BVOps(NumLanes, Poison);
827 auto *BV = new VPInstruction(IsStruct ? VPInstruction::BuildStructVector
828 : VPInstruction::BuildVector,
829 BVOps);
830 if (!IsStruct)
831 BuildVectors.push_back(Elt: BV);
832 Phi->replaceAllUsesWith(New: BV);
833 BV->setOperand(I: 0, New: Phi);
834 BV->insertBefore(BB&: *Successor, IP: Successor->getFirstNonPhi());
835 }
836
837 // Clone converted blocks for remaining lanes and process each in reverse
838 // order, connecting each lane's Exiting block to the subsequent lane's entry.
839 VPBlockBase *NextLaneEntry = Successor;
840 for (int Lane = NumLanes - 1; Lane > 0; --Lane) {
841 const auto &[CurrentLaneEntry, CurrentLaneExiting] =
842 VPBlockUtils::cloneFrom(Entry: FirstLaneEntry);
843 for (VPBlockBase *VPB : vp_depth_first_shallow(G: CurrentLaneEntry))
844 VPB->setParent(ParentRegion);
845 processLaneForReplicateRegion(Plan, IdxTy, Lane,
846 OldEntry: cast<VPBasicBlock>(Val: FirstLaneEntry),
847 NewEntry: cast<VPBasicBlock>(Val: CurrentLaneEntry));
848 VPBlockUtils::connectBlocks(From: CurrentLaneExiting, To: NextLaneEntry);
849 NextLaneEntry = CurrentLaneEntry;
850 }
851
852 // Connect Predecessor to FirstLaneEntry, and FirstLaneRegionExit to
853 // NextLaneEntry which is the second lane region entry. The latter is
854 // done last so that earlier clonings from FirstLaneEntry stop at
855 // FirstLaneExiting.
856 VPBlockUtils::connectBlocks(From: Predecessor, To: FirstLaneEntry);
857 VPBlockUtils::connectBlocks(From: FirstLaneExiting, To: NextLaneEntry);
858
859 // Fold BuildVector fed by scalar phis into VPWidenPHIRecipes with
860 // InsertElement per lane.
861 // TODO: check if this folding should be dropped.
862 for (VPInstruction *BV : BuildVectors) {
863 assert(BV->getNumOperands() == NumLanes &&
864 "BuildVector must have one operand per lane");
865 for (const auto &[Idx, Op] : enumerate(First: BV->operands())) {
866 auto *ScalarPhi = cast<VPPhi>(Val: Op);
867 auto DL = ScalarPhi->getDebugLoc();
868 auto *PredOp = cast<VPSingleDefRecipe>(Val: ScalarPhi->getOperand(N: 1));
869 VPValue *Poison = ScalarPhi->getOperand(N: 0);
870 VPValue *PrevVal = Idx == 0 ? Poison : BV->getOperand(N: Idx - 1);
871 auto Builder = VPBuilder::getToInsertAfter(R: PredOp->getDefiningRecipe());
872 auto *Insert = Builder.createNaryOp(
873 Opcode: Instruction::InsertElement,
874 Operands: {PrevVal, PredOp, Plan.getConstantInt(BitWidth: 64, Val: Idx)}, DL);
875 Builder.setInsertPoint(ScalarPhi);
876 auto *NewPhi = Builder.createWidenPhi(IncomingValues: {PrevVal, Insert}, DL);
877 ScalarPhi->replaceAllUsesWith(New: NewPhi);
878 ScalarPhi->eraseFromParent();
879 }
880 BV->replaceAllUsesWith(New: BV->getOperand(N: NumLanes - 1));
881 BV->eraseFromParent();
882 }
883}
884
885/// Collect and dissolve all replicate regions in the vector loop, replicating
886/// their blocks and recipes for each lane of \p VF.
887static void replicateReplicateRegionsByVF(VPlan &Plan, ElementCount VF,
888 Type *IdxTy) {
889 // Collect all replicate regions before modifying the CFG.
890 SmallVector<VPRegionBlock *> ReplicateRegions;
891 for (VPRegionBlock *Region : VPBlockUtils::blocksOnly<VPRegionBlock>(
892 Range: vp_depth_first_shallow(G: Plan.getVectorLoopRegion()->getEntry()))) {
893 if (Region->isReplicator())
894 ReplicateRegions.push_back(Elt: Region);
895 }
896
897 assert((ReplicateRegions.empty() || !VF.isScalable()) &&
898 "cannot replicate across scalable VFs");
899
900 // Dissolve replicate regions by replicating their blocks for each lane.
901 // Traversing regions in reverse ensures that the successor of every region
902 // being processed is a basic-block, rather than another region.
903 for (VPRegionBlock *Region : reverse(C&: ReplicateRegions))
904 dissolveReplicateRegion(Region, VF, Plan, IdxTy);
905
906 VPlanTransforms::mergeBlocksIntoPredecessors(Plan);
907}
908
909void VPlanTransforms::replicateByVF(VPlan &Plan, ElementCount VF) {
910 Type *IdxTy = IntegerType::get(
911 C&: Plan.getScalarHeader()->getIRBasicBlock()->getContext(), NumBits: 32);
912
913 if (Plan.hasScalarVFOnly()) {
914 // When Plan is only unrolled by UF, replicating by VF amounts to dissolving
915 // replicate regions.
916 replicateReplicateRegionsByVF(Plan, VF, IdxTy);
917 return;
918 }
919
920 // Visit all VPBBs outside the loop region and directly inside the top-level
921 // loop region.
922 auto VPBBsOutsideLoopRegion = VPBlockUtils::blocksOnly<VPBasicBlock>(
923 Range: vp_depth_first_shallow(G: Plan.getEntry()));
924 auto VPBBsInsideLoopRegion = VPBlockUtils::blocksOnly<VPBasicBlock>(
925 Range: vp_depth_first_shallow(G: Plan.getVectorLoopRegion()->getEntry()));
926 auto VPBBsToUnroll =
927 concat<VPBasicBlock *>(Ranges&: VPBBsOutsideLoopRegion, Ranges&: VPBBsInsideLoopRegion);
928 // A mapping of current VPValue definitions to collections of new VPValues
929 // defined per lane. Serves to hook-up potential users of current VPValue
930 // definition that are replicated-per-VF later.
931 DenseMap<VPValue *, SmallVector<VPValue *>> Def2LaneDefs;
932 // The removal of current recipes being replaced by new ones needs to be
933 // delayed after Def2LaneDefs is no longer in use.
934 SmallVector<VPRecipeBase *> ToRemove;
935 for (VPBasicBlock *VPBB : VPBBsToUnroll) {
936 for (VPRecipeBase &R : make_early_inc_range(Range&: *VPBB)) {
937 if (!vputils::doesGeneratePerAllLanes(R: &R))
938 continue;
939
940 auto *DefR = cast<VPSingleDefRecipe>(Val: &R);
941 VPBuilder Builder(DefR);
942 if (DefR->user_empty()) {
943 // Create single-scalar version of DefR for all lanes.
944 for (unsigned I = 0; I != VF.getKnownMinValue(); ++I)
945 cloneForLane(Plan, Builder, IdxTy, DefR, Lane: VPLane(I), Def2LaneDefs);
946 DefR->eraseFromParent();
947 continue;
948 }
949 /// Create single-scalar version of DefR for all lanes.
950 SmallVector<VPValue *> LaneDefs;
951 for (unsigned I = 0; I != VF.getKnownMinValue(); ++I)
952 LaneDefs.push_back(
953 Elt: cloneForLane(Plan, Builder, IdxTy, DefR, Lane: VPLane(I), Def2LaneDefs));
954
955 Def2LaneDefs[DefR] = LaneDefs;
956 /// Users that only demand the first lane can use the definition for lane
957 /// 0.
958 DefR->replaceUsesWithIf(New: LaneDefs[0], ShouldReplace: [DefR](VPUser &U, unsigned) {
959 if (U.usesFirstLaneOnly(Op: DefR))
960 return true;
961 auto *VPI = dyn_cast<VPInstructionWithType>(Val: &U);
962 return VPI && Instruction::isCast(Opcode: VPI->getOpcode());
963 });
964
965 // Update each build vector user that currently has DefR as its only
966 // operand, to have all LaneDefs as its operands.
967 for (VPUser *U : to_vector(Range: DefR->users())) {
968 auto *VPI = dyn_cast<VPInstruction>(Val: U);
969 if (!VPI || (VPI->getOpcode() != VPInstruction::BuildVector &&
970 VPI->getOpcode() != VPInstruction::BuildStructVector))
971 continue;
972 assert(VPI->getNumOperands() == 1 &&
973 "Build(Struct)Vector must have a single operand before "
974 "replicating by VF");
975 VPI->setOperand(I: 0, New: LaneDefs[0]);
976 for (VPValue *LaneDef : drop_begin(RangeOrContainer&: LaneDefs))
977 VPI->addOperand(Op: LaneDef);
978 }
979 ToRemove.push_back(Elt: DefR);
980 }
981 }
982 for (auto *R : reverse(C&: ToRemove))
983 R->eraseFromParent();
984
985 replicateReplicateRegionsByVF(Plan, VF, IdxTy);
986}
987