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