LLVM 24.0.0git
VPlanUnroll.cpp
Go to the documentation of this file.
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"
23#include "llvm/ADT/STLExtras.h"
24#include "llvm/ADT/ScopeExit.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(CanIVIntTy, 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>(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(OrigR->definedValues())) {
96 const auto &[V, _] = VPV2Parts.try_emplace(VPV);
97 assert(V->second.size() == Part - 1 && "earlier parts not set");
98 V->second.push_back(CopyR->getVPValue(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(R);
105 assert(Inserted && "uniform value already added");
106 for (unsigned Part = 0; Part != UF; ++Part)
107 V->second.push_back(R);
108 }
109
110 bool contains(VPValue *VPV) const { return VPV2Parts.contains(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(OpIdx);
116 R->setOperand(OpIdx, getValueForPart(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(R->operands()))
122 R->setOperand(OpIdx, getValueForPart(Op, Part));
123 }
124};
125} // namespace
126
128 unsigned Part, VPlan &Plan) {
129 if (Part == 0)
130 return;
131
132 VPBuilder Builder(Steps);
133 Type *BaseIVTy = Steps->getOperand(0)->getScalarType();
134 Type *IntStepTy =
135 IntegerType::get(BaseIVTy->getContext(), BaseIVTy->getScalarSizeInBits());
136 VPValue *StartIndex = Steps->getVFValue();
137 if (Part > 1) {
138 StartIndex = Builder.createOverflowingOp(
139 Instruction::Mul,
140 {StartIndex, Plan.getConstantInt(StartIndex->getScalarType(), Part)});
141 }
142 StartIndex = Builder.createScalarSExtOrTrunc(StartIndex, IntStepTy,
143 Steps->getDebugLoc());
144
145 if (BaseIVTy->isFloatingPointTy())
146 StartIndex = Builder.createScalarCast(Instruction::SIToFP, StartIndex,
147 BaseIVTy, 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(Copy, InsertPt);
157
158 auto PartI = vp_depth_first_shallow(Copy->getEntry());
159 auto Part0 = vp_depth_first_shallow(VPR->getEntry());
160 for (const auto &[PartIVPBB, Part0VPBB] :
163 for (const auto &[PartIR, Part0R] : zip(*PartIVPBB, *Part0VPBB)) {
164 remapOperands(&PartIR, Part);
165 if (auto *Steps = dyn_cast<VPScalarIVStepsRecipe>(&PartIR))
166 addStartIndexForScalarSteps(Steps, Part, Plan);
167
168 addRecipeForPart(&Part0R, &PartIR, Part);
169 }
170 }
171 }
172}
173
174void UnrollState::unrollWidenInductionByUF(
175 VPWidenInductionRecipe *IV, VPBasicBlock::iterator InsertPtForPhi) {
176 VPBasicBlock *PH = cast<VPBasicBlock>(
177 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>(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 VPInstruction::WideIVStep, {&Plan.getVF(), ScalarStep}, VectorStepTy, FMF,
192 IV->getDebugLoc());
193
194 ToSkip.insert(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()) {
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;
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(Part) : "step.add";
227
228 VPInstruction *Add =
229 Builder.createNaryOp(AddOpc,
230 {
231 Prev,
232 VectorStep,
233 },
234 AddFlags, IV->getDebugLoc(), Name);
235 ToSkip.insert(Add);
236 addRecipeForPart(IV, Add, Part);
237 Prev = Add;
238 }
239 IV->addUnrolledPartOperands(VectorStep, 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.
247 return;
248
249 // Generate step vectors for each unrolled part.
250 if (auto *IV = dyn_cast<VPWidenInductionRecipe>(R)) {
251 unrollWidenInductionByUF(IV, InsertPtForPhi);
252 return;
253 }
254
255 auto *RdxPhi = dyn_cast<VPReductionPHIRecipe>(R);
256 if (RdxPhi && RdxPhi->isOrdered())
257 return;
258
259 auto InsertPt = std::next(R->getIterator());
260 for (unsigned Part = 1; Part != UF; ++Part) {
261 VPRecipeBase *Copy = R->clone();
262 Copy->insertBefore(InsertPt);
263 addRecipeForPart(R, 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>(RdxPhi->getStartValue())) {
270 assert(VPI->getOpcode() == VPInstruction::ReductionStartVector &&
271 "unexpected start VPInstruction");
272 if (Part != 1)
273 continue;
274 VPValue *StartV;
275 if (match(VPI->getOperand(2), m_One())) {
276 StartV = VPI->getOperand(1);
277 } else {
278 auto *C = VPI->clone();
279 C->setOperand(0, C->getOperand(1));
280 C->insertAfter(VPI);
281 StartV = C;
282 }
283 for (unsigned Part = 1; Part != UF; ++Part)
284 VPV2Parts[VPI][Part - 1] = StartV;
285 }
286 } else {
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(&R, 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>(&R)) {
301 if (!VPI->mayHaveSideEffects() && vputils::onlyFirstPartUsed(VPI)) {
302 addUniformForAllParts(VPI);
303 return;
304 }
305 }
306
307 if (auto *RepR = dyn_cast<VPReplicateRecipe>(&R)) {
308 if (isa<StoreInst>(RepR->getUnderlyingValue()) &&
309 RepR->getOperand(1)->isDefinedOutsideLoopRegions()) {
310 // Stores to an invariant address only need to store the last part.
311 remapOperands(&R, UF - 1);
312 return;
313 }
314 if (match(RepR,
316 addUniformForAllParts(RepR);
317 return;
318 }
319 }
320
321 // Unroll non-uniform recipes.
322 auto InsertPt = std::next(R.getIterator());
323 for (unsigned Part = 1; Part != UF; ++Part) {
324 VPRecipeBase *Copy = R.clone();
325 Copy->insertBefore(InsertPt);
326 addRecipeForPart(&R, Copy, Part);
327
328 // Phi operands are updated once all other recipes have been unrolled.
329 if (isa<VPWidenPHIRecipe>(Copy))
330 continue;
331
332 VPValue *Op;
334 m_VPValue(), m_VPValue(Op)))) {
335 Copy->setOperand(0, getValueForPart(Op, Part - 1));
336 Copy->setOperand(1, getValueForPart(Op, Part));
337 continue;
338 }
340 m_VPValue(Op), m_VPValue()))) {
341 Copy->setOperand(0, Op);
342 Copy->setOperand(1, Plan.getConstantInt(64, Part));
343 continue;
344 }
346 VPBuilder Builder(&R);
347 const DataLayout &DL = Plan.getDataLayout();
348 Type *IndexTy =
351 : DL.getIndexType(R.getVPSingleValue()->getScalarType());
352 VPValue *VF = Builder.createScalarZExtOrTrunc(&Plan.getVF(), IndexTy,
354 // VFxUF does not wrap, so VF * Part also cannot wrap.
355 VPValue *VFxPart = Builder.createOverflowingOp(
356 Instruction::Mul, {VF, Plan.getConstantInt(IndexTy, Part)},
357 {true, true});
358 if (auto *VecPtr = dyn_cast<VPVectorPointerRecipe>(Copy))
359 VecPtr->addPerPartOffset(VFxPart);
360 else
361 cast<VPWidenCanonicalIVRecipe>(Copy)->addPerPartStep(VFxPart);
362 continue;
363 }
364 if (auto *Red = dyn_cast<VPReductionRecipe>(&R)) {
365 auto *Phi = dyn_cast<VPReductionPHIRecipe>(R.getOperand(0));
366 if (Phi && Phi->isOrdered()) {
367 auto &Parts = VPV2Parts[Phi];
368 if (Part == 1) {
369 Parts.clear();
370 Parts.push_back(Red);
371 }
372 Parts.push_back(Copy->getVPSingleValue());
373 Phi->setOperand(1, Copy->getVPSingleValue());
374 }
375 }
376 if (auto *VEPR = dyn_cast<VPVectorEndPointerRecipe>(Copy)) {
377 // Materialize PartN offset for VectorEndPointer.
378 VEPR->setOperand(0, R.getOperand(0));
379 VEPR->setOperand(1, R.getOperand(1));
380 VEPR->materializeOffset(Part);
381 continue;
382 }
383
384 remapOperands(Copy, Part);
385
386 if (auto *ScalarIVSteps = dyn_cast<VPScalarIVStepsRecipe>(Copy))
387 addStartIndexForScalarSteps(ScalarIVSteps, Part, Plan);
388
389 if (match(Copy,
391 VPBuilder Builder(Copy);
392 VPValue *ScaledByPart = Builder.createOverflowingOp(
393 Instruction::Mul, {Copy->getOperand(1), getConstantInt(Part)});
394 Copy->setOperand(1, ScaledByPart);
395 }
396 }
397 if (auto *VEPR = dyn_cast<VPVectorEndPointerRecipe>(&R)) {
398 // Materialize Part0 offset for VectorEndPointer.
399 VEPR->materializeOffset();
400 }
401 if (auto *WideCanIV = dyn_cast<VPWidenCanonicalIVRecipe>(&R)) {
402 // Set Part0 step for WidenCanonicalIV.
403 WideCanIV->addPerPartStep(getConstantInt(0));
404 }
405}
406
407void UnrollState::unrollBlock(VPBlockBase *VPB) {
408 auto *VPR = dyn_cast<VPRegionBlock>(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>(VPB);
424 auto InsertPtForPhi = VPBB->getFirstNonPhi();
425 for (VPRecipeBase &R : make_early_inc_range(*VPBB)) {
426 if (ToSkip.contains(&R) || isa<VPIRInstruction>(&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;
434 match(&R,
436 match(&R, m_FirstActiveLane(m_VPValue(Op1))) ||
437 match(&R, m_LastActiveLane(m_VPValue(Op1))) ||
439 auto *VPI = cast<VPInstruction>(&R);
440 addUniformForAllParts(VPI);
441 for (unsigned Part = 1; Part != UF; ++Part)
442 VPI->addOperand(getValueForPart(Op1, Part));
443 continue;
444 }
445 VPValue *Op0;
446 if (match(&R, m_ExtractLane(m_VPValue(Op0), m_VPValue(Op1)))) {
447 auto *VPI = cast<VPInstruction>(&R);
448 addUniformForAllParts(VPI);
449 for (unsigned Part = 1; Part != UF; ++Part)
450 VPI->addOperand(getValueForPart(Op1, Part));
451 continue;
452 }
453
454 VPValue *Op2;
456 m_VPValue(Op2)))) {
457 auto *VPI = cast<VPInstruction>(&R);
458 addUniformForAllParts(VPI);
459 for (unsigned Part = 1; Part != UF; ++Part) {
460 VPI->addOperand(getValueForPart(Op1, Part));
461 VPI->addOperand(getValueForPart(Op2, Part));
462 }
463 continue;
464 }
465
466 if (Plan.hasScalarVFOnly()) {
467 if (match(&R, m_ExtractLastPart(m_VPValue(Op0))) ||
469 auto *I = cast<VPInstruction>(&R);
470 bool IsPenultimatePart =
472 unsigned PartIdx = IsPenultimatePart ? UF - 2 : UF - 1;
473 // For scalar VF, directly use the scalar part value.
474 I->replaceAllUsesWith(getValueForPart(Op0, PartIdx));
475 continue;
476 }
477 }
478 // For vector VF, the penultimate element is always extracted from the last part.
481 addUniformForAllParts(cast<VPSingleDefRecipe>(&R));
482 R.setOperand(0, getValueForPart(Op0, UF - 1));
483 continue;
484 }
485
486 if (match(&R,
488 auto *ALM = cast<VPInstruction>(&R);
489 ALM->setOperand(2, getConstantInt(UF));
490 continue;
491 }
492
494 if (ALM && match(ALM->getBackedgeValue(),
496 addUniformForAllParts(ALM);
497 continue;
498 }
499
500 if (match(&R,
503 cast<VPInstruction>(&R)->setOperand(0, Plan.getConstantInt(64, UF));
504 continue;
505 }
506
507 auto *SingleDef = dyn_cast<VPSingleDefRecipe>(&R);
508 if (SingleDef && vputils::isUniformAcrossVFsAndUFs(SingleDef)) {
509 addUniformForAllParts(SingleDef);
510 continue;
511 }
512
513 if (auto *H = dyn_cast<VPHeaderPHIRecipe>(&R)) {
514 unrollHeaderPHIByUF(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(Plan.getEntry());
527 // Remove recipes that are redundant after unrolling.
529 for (VPInstruction &VPI :
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(&VPI, m_ExtractLastPart(m_VPValue(Op)))) {
535 if (UF == 1)
536 VPI.replaceAllUsesWith(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(1) == &Plan.getVF()) {
544 VPI.replaceAllUsesWith(VPI.getOperand(0));
545 VPI.eraseFromParent();
546 }
547 }
548 }
549
550 Type *TCTy = Plan.getTripCount()->getScalarType();
551 Plan.getUF().replaceAllUsesWith(Plan.getConstantInt(TCTy, 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.
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 :
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.
577 Unroller.remapOperand(&H, 1, UF - 1);
578 continue;
579 }
580 if (Unroller.contains(H.getVPSingleValue())) {
581 Part = 1;
582 continue;
583 }
584 Unroller.remapOperands(&H, Part);
585 Part++;
586 }
587
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(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(ConstantFP::get(BaseIVTy, Lane));
606 AddOpcode = Instruction::FAdd;
607 Flags = VPIRFlags(FastMathFlags());
608 } else {
609 unsigned BaseIVBits = BaseIVTy->getScalarSizeInBits();
610 LaneOffset = Plan.getConstantInt(
611 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(AddOpcode, {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) {
633 "DefR must be a VPReplicateRecipe, VPInstruction or "
634 "VPScalarIVStepsRecipe");
635 VPValue *Op;
637 auto LaneDefs = Def2LaneDefs.find(Op);
638 if (LaneDefs != Def2LaneDefs.end())
639 return LaneDefs->second[Lane];
640
641 VPValue *Idx = Plan.getConstantInt(IdxTy, Lane);
642 return Builder.createNaryOp(Instruction::ExtractElement, {Op, Idx});
643 }
644
645 // Collect the operands at Lane, creating extracts as needed.
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(Op);
651 if (LaneDefs != Def2LaneDefs.end()) {
652 NewOps.push_back(LaneDefs->second[Lane]);
653 continue;
654 }
656 NewOps.push_back(Op);
657 continue;
658 }
659
660 VPValue *Idx = Plan.getConstantInt(IdxTy, Lane);
661 VPValue *Ext = Builder.createNaryOp(Instruction::ExtractElement, {Op, Idx});
662 NewOps.push_back(Ext);
663 }
664
666 if (auto *RepR = dyn_cast<VPReplicateRecipe>(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?)
671 RepR->getOpcode(), NewOps, /*Mask=*/nullptr, *RepR, *RepR,
672 RepR->getDebugLoc(), RepR->getScalarType(), RepR->getUnderlyingInstr());
673 } else {
674 New = DefR->clone();
675 for (const auto &[Idx, Op] : enumerate(NewOps)) {
676 New->setOperand(Idx, Op);
677 }
678 if (auto *Steps = dyn_cast<VPScalarIVStepsRecipe>(New)) {
679 // Skip lane 0: an absent start index is implicitly zero.
680 if (Lane != 0)
681 addLaneToStartIndex(Steps, Lane, Plan, DefR);
682 }
683 }
684 New->insertBefore(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;
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(Taken, NotTaken);
703 return MDBuilder(Ctx).createBranchWeights(Taken / GCD, 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.
712 VPBlockBase *Entry,
713 ElementCount VF) {
714 VPValue *Idx0 = Plan.getZero(IdxTy);
715 for (VPBlockBase *VPB : vp_depth_first_shallow(Entry)) {
717 assert(
718 !isa<VPWidenPHIRecipe>(&OldR) &&
719 !match(&OldR,
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(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();
736 DefR->getParent() == VPB) ||
738 continue;
739
740 // Extract lane zero from values defined outside the region.
741 VPValue *Extract = Builder.createNaryOp(Instruction::ExtractElement,
742 {Op, Idx0}, OldDL);
743 OldR.setOperand(I, Extract);
744 }
745 }
746
747 if (auto *RepR = dyn_cast<VPReplicateRecipe>(&OldR)) {
749 RepR->getOpcode(), to_vector(RepR->operands()), /*Mask=*/nullptr,
750 *RepR, *RepR, OldDL, RepR->getScalarType(),
751 RepR->getUnderlyingInstr());
752 NewR->insertBefore(RepR);
753 RepR->replaceAllUsesWith(NewR);
754 RepR->eraseFromParent();
755 } else if (auto *BranchOnMask = dyn_cast<VPBranchOnMaskRecipe>(&OldR)) {
756 // Turn the frequency of the predicated block into branch weights.
757 auto *BOC = Builder.createNaryOp(VPInstruction::BranchOnCond,
758 {BranchOnMask->getOperand(0)}, OldDL);
760 BranchOnMask->getExecutionFrequency(), Plan.getContext()))
761 BOC->setMetadata(LLVMContext::MD_prof, Weights);
762 BranchOnMask->eraseFromParent();
763 } else if (auto *PredPhi = dyn_cast<VPPredInstPHIRecipe>(&OldR)) {
764 VPValue *PredOp = PredPhi->getOperand(0);
765 Type *PredTy = PredOp->getScalarType();
766 VPValue *Poison = Plan.getPoison(PredTy);
767 VPPhi *NewPhi = Builder.createScalarPhi({Poison, PredOp}, OldDL);
768 PredPhi->replaceAllUsesWith(NewPhi);
769 PredPhi->eraseFromParent();
770 } else {
771 // TODO: Support isSingleScalar for VPScalarIVStepsRecipe.
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(IdxTy, Lane);
788 for (const auto &[OldBB, NewBB] :
790 vp_depth_first_shallow(NewEntry))) {
791 for (auto &&[OldR, NewR] :
793 for (const auto &[OldV, NewV] :
794 zip_equal(OldR.definedValues(), NewR.definedValues()))
795 Old2NewVPValues[OldV] = NewV;
796
797 // Remap operands to use lane-specific values.
798 for (const auto &[I, OldOp] : enumerate(NewR.operands())) {
799 // Use cloned value if operand was defined in the region.
800 if (auto *NewOp = Old2NewVPValues.lookup(OldOp))
801 NewR.setOperand(I, NewOp);
802 }
803
804 if (auto *Steps = dyn_cast<VPScalarIVStepsRecipe>(&NewR)) {
805 addLaneToStartIndex(Steps, Lane, Plan, Steps);
806 } else if (match(&NewR, m_ExtractElement(m_VPValue(), m_VPValue()))) {
807 assert(match(NewR.getOperand(1), m_ZeroInt()) &&
808 "extract indices must be zero");
809 NewR.setOperand(1, IdxLane);
810 } else if (auto *NewPhi = dyn_cast<VPPhi>(&NewR)) {
811 auto *OldPhi = cast<VPPhi>(&OldR);
813 "VPPhis expected to have only first lane used");
814 auto *BVUser = dyn_cast_or_null<VPInstruction>(OldPhi->getSingleUser());
815 if (BVUser && match(BVUser, m_BuildVector())) {
816 assert(BVUser->getOperand(0) == OldPhi &&
817 "Unexpected first operand of build vector user");
818 BVUser->setOperand(Lane, 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.
829 VPlan &Plan, Type *IdxTy) {
830 auto *FirstLaneEntry = cast<VPBasicBlock>(Region->getEntry());
831 auto *FirstLaneExiting = cast<VPBasicBlock>(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>(Region->getSingleSuccessor());
839
840 VPRegionBlock *ParentRegion = Region->getParent();
841 for (VPBlockBase *VPB : vp_depth_first_shallow(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, 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(Predecessor, FirstLaneEntry);
852 VPBlockUtils::connectBlocks(FirstLaneExiting, 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 (VPPhi &Phi : map_range(FirstLaneExiting->phis(), CastTo<VPPhi>)) {
869 continue;
870
871 Type *ScalarTy = Phi.getScalarType();
872 VPValue *Poison = Plan.getPoison(ScalarTy);
873 SmallVector<VPValue *> BVOps(NumLanes, Poison);
874 auto *BV = new VPInstruction(VPInstruction::BuildVector, BVOps);
876 BuildVectors.push_back(BV);
877 Phi.replaceAllUsesWith(BV);
878 BV->setOperand(0, &Phi);
879 BV->insertBefore(Successor->getFirstNonPhi());
880 }
881
882 // Clone converted blocks for remaining lanes and process each in reverse
883 // order, connecting each lane's Exiting block to the subsequent lane's entry.
884 VPBlockBase *NextLaneEntry = Successor;
885 for (int Lane = NumLanes - 1; Lane > 0; --Lane) {
886 const auto &[CurrentLaneEntry, CurrentLaneExiting] =
887 VPBlockUtils::cloneFrom(FirstLaneEntry);
888 for (VPBlockBase *VPB : vp_depth_first_shallow(CurrentLaneEntry))
889 VPB->setParent(ParentRegion);
890 processLaneForReplicateRegion(Plan, IdxTy, Lane,
891 cast<VPBasicBlock>(FirstLaneEntry),
892 cast<VPBasicBlock>(CurrentLaneEntry));
893 VPBlockUtils::connectBlocks(CurrentLaneExiting, NextLaneEntry);
894 NextLaneEntry = CurrentLaneEntry;
895 }
896
897 // Connect Predecessor to FirstLaneEntry, and FirstLaneRegionExit to
898 // NextLaneEntry which is the second lane region entry. The latter is
899 // done last so that earlier clonings from FirstLaneEntry stop at
900 // FirstLaneExiting.
901 VPBlockUtils::connectBlocks(Predecessor, FirstLaneEntry);
902 VPBlockUtils::connectBlocks(FirstLaneExiting, NextLaneEntry);
903
904 // Fold BuildVector fed by scalar phis into VPWidenPHIRecipes with
905 // InsertElement per lane.
906 // TODO: check if this folding should be dropped.
907 for (VPInstruction *BV : BuildVectors) {
908 assert(BV->getNumOperands() == NumLanes &&
909 "BuildVector must have one operand per lane");
910 for (const auto &[Idx, Op] : enumerate(BV->operands())) {
911 auto *ScalarPhi = cast<VPPhi>(Op);
912 auto DL = ScalarPhi->getDebugLoc();
913 auto *PredOp = cast<VPSingleDefRecipe>(ScalarPhi->getOperand(1));
914 VPValue *Poison = ScalarPhi->getOperand(0);
915 VPValue *PrevVal = Idx == 0 ? Poison : BV->getOperand(Idx - 1);
916 auto Builder = VPBuilder::getToInsertAfter(PredOp->getDefiningRecipe());
917 auto *Insert = Builder.createNaryOp(
918 Instruction::InsertElement,
919 {PrevVal, PredOp, Plan.getConstantInt(64, Idx)}, DL);
920 Builder.setInsertPoint(ScalarPhi);
921 auto *NewPhi = Builder.createWidenPhi({PrevVal, Insert}, DL);
922 ScalarPhi->replaceAllUsesWith(NewPhi);
923 ScalarPhi->eraseFromParent();
924 }
925 BV->replaceAllUsesWith(BV->getOperand(NumLanes - 1));
926 BV->eraseFromParent();
927 }
928}
929
930/// Collect and dissolve all replicate regions in the vector loop, replicating
931/// their blocks and recipes for each lane of \p VF.
933 Type *IdxTy) {
934 // Collect all replicate regions before modifying the CFG.
935 SmallVector<VPRegionBlock *> ReplicateRegions;
938 if (Region->isReplicator())
939 ReplicateRegions.push_back(Region);
940 }
941
942 assert((ReplicateRegions.empty() || !VF.isScalable()) &&
943 "cannot replicate across scalable VFs");
944
945 // Dissolve replicate regions by replicating their blocks for each lane.
946 // Traversing regions in reverse ensures that the successor of every region
947 // being processed is a basic-block, rather than another region.
948 for (VPRegionBlock *Region : reverse(ReplicateRegions))
949 dissolveReplicateRegion(Region, VF, Plan, IdxTy);
950
952}
953
955 Type *IdxTy = IntegerType::get(
957
958 if (Plan.hasScalarVFOnly()) {
959 // When Plan is only unrolled by UF, replicating by VF amounts to dissolving
960 // replicate regions.
961 replicateReplicateRegionsByVF(Plan, VF, IdxTy);
962 return;
963 }
964
965 // Visit all VPBBs outside the loop region and directly inside the top-level
966 // loop region.
967 auto VPBBsOutsideLoopRegion = VPBlockUtils::blocksOnly<VPBasicBlock>(
969 auto VPBBsInsideLoopRegion = VPBlockUtils::blocksOnly<VPBasicBlock>(
971 auto VPBBsToUnroll =
972 concat<VPBasicBlock *>(VPBBsOutsideLoopRegion, VPBBsInsideLoopRegion);
973 // A mapping of current VPValue definitions to collections of new VPValues
974 // defined per lane. Serves to hook-up potential users of current VPValue
975 // definition that are replicated-per-VF later.
977 // The removal of current recipes being replaced by new ones needs to be
978 // delayed after Def2LaneDefs is no longer in use.
980 for (VPBasicBlock *VPBB : VPBBsToUnroll) {
981 for (VPRecipeBase &R : make_early_inc_range(*VPBB)) {
983 continue;
984
985 auto *DefR = cast<VPSingleDefRecipe>(&R);
986 VPBuilder Builder(DefR);
987 if (DefR->user_empty()) {
988 // Create single-scalar version of DefR for all lanes.
989 for (unsigned I = 0; I != VF.getKnownMinValue(); ++I)
990 cloneForLane(Plan, Builder, IdxTy, DefR, I, Def2LaneDefs);
991 DefR->eraseFromParent();
992 continue;
993 }
994 /// Create single-scalar version of DefR for all lanes.
995 SmallVector<VPValue *> LaneDefs;
996 for (unsigned I = 0; I != VF.getKnownMinValue(); ++I)
997 LaneDefs.push_back(
998 cloneForLane(Plan, Builder, IdxTy, DefR, I, Def2LaneDefs));
999
1000 Def2LaneDefs[DefR] = LaneDefs;
1001 // Pack the lanes for vector users.
1002 if (!vputils::onlyScalarValuesUsed(DefR)) {
1003 DefR->replaceUsesWithIf(
1004 Builder.createNaryOp(VPInstruction::BuildVector, LaneDefs),
1005 [DefR](VPUser *U) { return !U->usesScalars(DefR); });
1006 }
1007 /// Users that only demand the first lane can use the definition for lane
1008 /// 0. If DefR is a single scalar, all lanes are equal and all scalar
1009 /// users can use lane 0.
1010 bool IsSingleScalar = vputils::isSingleScalar(DefR);
1011 DefR->replaceUsesWithIf(LaneDefs[0], [DefR, IsSingleScalar](VPUser *U) {
1012 if (U->usesFirstLaneOnly(DefR) ||
1013 (IsSingleScalar && U->usesScalars(DefR)))
1014 return true;
1015 auto *VPI = dyn_cast<VPInstruction>(U);
1016 return VPI && Instruction::isCast(VPI->getOpcode());
1017 });
1018 ToRemove.push_back(DefR);
1019 }
1020 }
1021
1022 replicateReplicateRegionsByVF(Plan, VF, IdxTy);
1023 // Replace the lane extracts created when dissolving replicate regions.
1024 for (VPSingleDefRecipe *DefR : reverse(ToRemove)) {
1025 for (VPUser *U : to_vector(DefR->users())) {
1026 uint64_t Lane;
1027 [[maybe_unused]] bool Match =
1029 assert(Match && "unexpected remaining user");
1030 auto *Ext = cast<VPInstruction>(U);
1031 Ext->replaceAllUsesWith(Def2LaneDefs.at(DefR)[Lane]);
1032 Ext->eraseFromParent();
1033 }
1034 DefR->eraseFromParent();
1035 }
1036}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
ReachingDefInfo InstSet & ToRemove
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static bool isCanonical(const MDString *S)
ManagedStatic< HTTPClientCleanup > Cleanup
#define _
#define I(x, y, z)
Definition MD5.cpp:57
#define H(x, y, z)
Definition MD5.cpp:56
#define P(N)
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
This file contains some templates that are useful if you are working with the STL at all.
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Definition Value.cpp:479
This file defines the scope_exit class, which executes user-defined cleanup logic at scope exit.
static ConstantInt * getConstantInt(Value *V, const DataLayout &DL)
Extract ConstantInt from value, looking through IntToPtr and PointerNullValue.
This file contains the declarations of different VPlan-related auxiliary helpers.
This file provides utility VPlan to VPlan transformations.
static void addLaneToStartIndex(VPScalarIVStepsRecipe *Steps, unsigned Lane, VPlan &Plan, VPRecipeBase *InsertPt)
Add a lane offset to the start index of Steps.
static void replicateReplicateRegionsByVF(VPlan &Plan, ElementCount VF, Type *IdxTy)
Collect and dissolve all replicate regions in the vector loop, replicating their blocks and recipes f...
static VPValue * cloneForLane(VPlan &Plan, VPBuilder &Builder, Type *IdxTy, VPSingleDefRecipe *DefR, unsigned Lane, const DenseMap< VPValue *, SmallVector< VPValue * > > &Def2LaneDefs)
Create a single-scalar clone of DefR (must be a VPReplicateRecipe, VPInstruction or VPScalarIVStepsRe...
static MDNode * convertFrequencyToBranchWeights(std::optional< VPExecutionFrequency > Freq, LLVMContext &Ctx)
Converts the frequency Freq with which a block is entered to branch weights for the branch guarding i...
static void addStartIndexForScalarSteps(VPScalarIVStepsRecipe *Steps, unsigned Part, VPlan &Plan)
static void convertRecipesInRegionBlocksToSingleScalar(VPlan &Plan, Type *IdxTy, VPBlockBase *Entry, ElementCount VF)
Convert recipes in region blocks to operate on a single lane 0.
static void dissolveReplicateRegion(VPRegionBlock *Region, ElementCount VF, VPlan &Plan, Type *IdxTy)
Dissolve a single replicate region by replicating its blocks for each lane of VF.
static void processLaneForReplicateRegion(VPlan &Plan, Type *IdxTy, unsigned Lane, VPBasicBlock *OldEntry, VPBasicBlock *NewEntry)
Update recipes in the cloned blocks rooted at NewEntry to match Lane, using the original blocks roote...
static void remapOperands(VPBlockBase *Entry, VPBlockBase *NewEntry, DenseMap< VPValue *, VPValue * > &Old2NewVPValues)
Definition VPlan.cpp:1182
This file contains the declarations of the Vectorization Plan base classes:
static const uint32_t IV[8]
Definition blake3_impl.h:83
Class for arbitrary precision integers.
Definition APInt.h:78
LLVM_ABI LLVMContext & getContext() const
Get the context in which this basic block lives.
A debug info location.
Definition DebugLoc.h:126
static DebugLoc getUnknown()
Definition DebugLoc.h:153
ValueT & at(const_arg_type_t< KeyT > Val)
Return the entry for the specified key, or abort if no such entry exists.
Definition DenseMap.h:811
ValueT lookup(const_arg_type_t< KeyT > Val) const
Return the entry for the specified key, or a default constructed value if no such entry exists.
Definition DenseMap.h:793
constexpr bool isScalar() const
Exactly one element.
Definition TypeSize.h:317
Convenience struct for specifying and reasoning about fast-math flags.
Definition FMF.h:23
static GEPNoWrapFlags none()
bool isCast() const
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition Type.cpp:333
This is an important class for using LLVM in a threaded context.
Definition LLVMContext.h:76
LLVM_ABI MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight, bool IsExpected=false)
Return metadata containing two branch weights.
Definition MDBuilder.cpp:38
Metadata node.
Definition Metadata.h:1087
RegionT * getParent() const
Get the parent of the Region.
Definition RegionInfo.h:365
BlockT * getEntry() const
Get the entry BasicBlock of the Region.
Definition RegionInfo.h:323
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition Type.h:46
bool isPointerTy() const
True if this is an instance of PointerType.
Definition Type.h:277
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
Definition Type.h:354
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
Definition Type.h:130
bool isFloatingPointTy() const
Return true if this is one of the floating-point types.
Definition Type.h:186
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition VPlan.h:4540
RecipeListTy::iterator iterator
Instruction iterators...
Definition VPlan.h:4571
iterator_range< iterator > phis()
Returns an iterator range over the PHI-like recipes in the block.
Definition VPlan.h:4634
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition VPlan.h:95
const VPBasicBlock * getEntryBasicBlock() const
Definition VPlan.cpp:179
void setParent(VPRegionBlock *P)
Definition VPlan.h:203
VPBlockBase * getSingleSuccessor() const
Definition VPlan.h:233
static auto blocksAs(T &&Range)
Return an iterator range over Range with each block cast to BlockTy.
Definition VPlanUtils.h:465
static void connectBlocks(VPBlockBase *From, VPBlockBase *To, unsigned PredIdx=-1u, unsigned SuccIdx=-1u)
Connect VPBlockBases From and To bi-directionally.
Definition VPlanUtils.h:392
static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To)
Disconnect VPBlockBases From and To bi-directionally.
Definition VPlanUtils.h:410
static void insertBlockBefore(VPBlockBase *NewBlock, VPBlockBase *BlockPtr)
Insert disconnected block NewBlock before Blockptr.
Definition VPlanUtils.h:359
static auto blocksOnly(T &&Range)
Return an iterator range over Range which only includes BlockTy blocks.
Definition VPlanUtils.h:458
static std::pair< VPBlockBase *, VPBlockBase * > cloneFrom(VPBlockBase *Entry)
Clone the CFG for all nodes reachable from Entry, including cloning the blocks and their recipes.
Definition VPlan.cpp:653
static VPBuilderBase getToInsertAfter(VPRecipeBase *R)
static VPSingleDefRecipe * createSingleScalarOp(unsigned Opcode, ArrayRef< VPValue * > Operands, VPValue *Mask, const VPIRFlags &Flags, const VPIRMetadata &Metadata, DebugLoc DL, Type *ResultTy, Instruction *UV)
VPValue * getVPValue(unsigned I)
Returns the VPValue with index I defined by the VPDef.
Definition VPlanValue.h:557
ArrayRef< VPRecipeValue * > definedValues()
Returns an ArrayRef of the values defined by the VPDef.
Definition VPlanValue.h:567
BasicBlock * getIRBasicBlock() const
Definition VPlan.h:4723
Class to record and manage LLVM IR flags.
Definition VPlan.h:683
This is a concrete Recipe that models a single VPlan-level instruction.
Definition VPlan.h:1322
@ WideIVStep
Scale the first operand (vector step) by the second operand (scalar-step).
Definition VPlan.h:1445
@ ReductionStartVector
Start vector for reductions with 3 operands: the original start value, the identity value for the red...
Definition VPlan.h:1423
@ BuildVector
Creates a fixed-width vector containing all operands.
Definition VPlan.h:1373
@ CanonicalIVIncrementForPart
Definition VPlan.h:1358
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition VPlan.h:402
DebugLoc getDebugLoc() const
Returns the debug location of the recipe.
Definition VPlan.h:547
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition VPlan.h:4771
VPRegionBlock * clone() override
Clone all blocks in the single-entry single-exit region of the block and their recipes without updati...
Definition VPlan.cpp:710
const VPBlockBase * getEntry() const
Definition VPlan.h:4815
bool isReplicator() const
An indicator whether this region is to generate multiple replicated instances of output IR correspond...
Definition VPlan.h:4847
Type * getCanonicalIVType() const
Return the type of the canonical IV for loop regions.
Definition VPlan.h:4899
A recipe for handling phi nodes of integer and floating-point inductions, producing their scalar valu...
Definition VPlan.h:4371
void setStartIndex(VPValue *StartIndex)
Set or add the StartIndex operand.
Definition VPlan.h:4415
VPValue * getStartIndex() const
Return the StartIndex, or null if known to be zero, valid only after unrolling.
Definition VPlan.h:4410
VPValue * getVFValue() const
Return the number of scalars to produce per unroll part, used to compute StartIndex during unrolling.
Definition VPlan.h:4406
VPSingleDefRecipe is a base class for recipes that model a sequence of one or more output IR that def...
Definition VPlan.h:605
VPSingleDefRecipe * clone() override=0
Clone the current recipe.
This class augments VPValue with operands which provide the inverse def-use edges from VPValue's user...
Definition VPlanValue.h:396
operand_range operands()
Definition VPlanValue.h:472
VPValue * getOperand(unsigned N) const
Definition VPlanValue.h:437
This is the base class of the VPlan Def/Use graph, used for modeling the data flow into,...
Definition VPlanValue.h:50
Type * getScalarType() const
Returns the scalar type of this VPValue, dispatching based on the concrete subclass.
Definition VPlan.cpp:138
void replaceAllUsesWith(VPValue *New)
Definition VPlan.cpp:1470
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition VPlan.h:4958
const DataLayout & getDataLayout() const
Definition VPlan.h:5159
LLVMContext & getContext() const
Definition VPlan.h:5155
VPBasicBlock * getEntry()
Definition VPlan.h:5050
VPValue * getTripCount() const
The trip count of the original loop.
Definition VPlan.h:5122
VPIRValue * getPoison(Type *Ty)
Return a VPIRValue wrapping a poison value of type Ty.
Definition VPlan.h:5282
VPIRValue * getOrAddLiveIn(Value *V)
Gets the live-in VPIRValue for V or adds a new live-in (if none exists yet) for V.
Definition VPlan.h:5231
VPIRValue * getZero(Type *Ty)
Return a VPIRValue wrapping the null value of type Ty.
Definition VPlan.h:5257
LLVM_ABI_FOR_TEST VPRegionBlock * getVectorLoopRegion()
Returns the VPRegionBlock of the vector loop.
Definition VPlan.cpp:1060
VPSymbolicValue & getUF()
Returns the UF of the vector loop region.
Definition VPlan.h:5150
bool hasScalarVFOnly() const
Definition VPlan.h:5199
VPIRBasicBlock * getScalarHeader() const
Return the VPIRBasicBlock wrapping the header of the scalar loop.
Definition VPlan.h:5112
VPSymbolicValue & getVF()
Returns the VF of the vector loop region.
Definition VPlan.h:5146
void setUF(unsigned UF)
Definition VPlan.h:5214
VPIRValue * getConstantInt(Type *Ty, uint64_t Val, bool IsSigned=false)
Return a VPIRValue wrapping a ConstantInt with the given type and value.
Definition VPlan.h:5265
constexpr ScalarTy getFixedValue() const
Definition TypeSize.h:201
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
Definition TypeSize.h:169
constexpr ScalarTy getKnownMinValue() const
Returns the minimum value this quantity can represent.
Definition TypeSize.h:166
SpecificConstantMatch m_ZeroInt()
Convenience matchers for specific integer values.
match_combine_or< Ty... > m_CombineOr(const Ty &...Ps)
Combine pattern matchers matching any of Ps patterns.
bool match(Val *V, const Pattern &P)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
auto m_Intrinsic(const Ts &...Ops)
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
auto m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
VPInstruction_match< VPInstruction::ExtractLastLane, VPInstruction_match< VPInstruction::ExtractLastPart, Op0_t > > m_ExtractLastLaneOfLastPart(const Op0_t &Op0)
VPInstruction_match< VPInstruction::ComputeReductionResult, Op0_t > m_ComputeReductionResult(const Op0_t &Op0)
VPInstruction_match< Instruction::InsertElement, Op0_t, Op1_t, Op2_t > m_InsertElement(const Op0_t &Op0, const Op1_t &Op1, const Op2_t &Op2)
VPInstruction_match< VPInstruction::LastActiveLane, Op0_t > m_LastActiveLane(const Op0_t &Op0)
VPInstruction_match< VPInstruction::ExtractLastActive, Op0_t, Op1_t, Op2_t > m_ExtractLastActive(const Op0_t &Op0, const Op1_t &Op1, const Op2_t &Op2)
VPInstruction_match< Instruction::ExtractElement, Op0_t, Op1_t > m_ExtractElement(const Op0_t &Op0, const Op1_t &Op1)
auto m_VPValue()
Match an arbitrary VPValue and ignore it.
VPInstruction_match< VPInstruction::ExtractLastPart, Op0_t > m_ExtractLastPart(const Op0_t &Op0)
VPInstruction_match< VPInstruction::BuildVector > m_BuildVector()
BuildVector is matches only its opcode, w/o matching its operands as the number of operands is not fi...
VPInstruction_match< VPInstruction::ExtractPenultimateElement, Op0_t > m_ExtractPenultimateElement(const Op0_t &Op0)
match_bind< VPInstruction > m_VPInstruction(VPInstruction *&V)
Match a VPInstruction, capturing if we match.
VPInstruction_match< VPInstruction::FirstActiveLane, Op0_t > m_FirstActiveLane(const Op0_t &Op0)
VPInstruction_match< VPInstruction::WideActiveLaneMask, Op_t... > m_WideActiveLaneMask(const Op_t &...Op)
VPInstruction_match< VPInstruction::ExtractLane, Op0_t, Op1_t > m_ExtractLane(const Op0_t &Op0, const Op1_t &Op1)
NodeAddr< PhiNode * > Phi
Definition RDFGraph.h:390
BranchProbability getExecutionProbability(BlockFrequency Freq)
Returns Freq as a BranchProbability, relative to the full mass.
bool isSingleScalar(const VPValue *VPV)
Returns true if VPV is a single scalar, either because it produces the same value for all lanes or on...
bool onlyFirstPartUsed(const VPValue *Def)
Returns true if only the first part of Def is used by all users.
bool onlyFirstLaneUsed(const VPValue *Def)
Returns true if only the first lane of Def is used by all users.
bool doesGeneratePerAllLanes(const VPRecipeBase *R)
Returns true if R produces scalar values for all VF lanes.
bool onlyScalarValuesOrLanesUsed(const VPValue *Def)
Returns true if only scalar values of Def are used by all users, either directly or by extracting a c...
bool onlyScalarValuesUsed(const VPValue *Def)
Returns true if only scalar values of Def are used by all users.
LLVM_ABI_FOR_TEST bool isUniformAcrossVFsAndUFs(const VPValue *V)
Checks if V is uniform across all VF lanes and UF parts.
This is an optimization pass for GlobalISel generic memory operations.
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
Definition STLExtras.h:846
detail::zippy< detail::zip_first, T, U, Args... > zip_equal(T &&t, U &&u, Args &&...args)
zip iterator that assumes that all iteratees have the same length.
Definition STLExtras.h:856
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are tuples (A, B,...
Definition STLExtras.h:2575
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
VPBuilderBase<> VPBuilder
Definition VPlan.h:66
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition STLExtras.h:649
iterator_range< df_iterator< VPBlockShallowTraversalWrapper< VPBlockBase * > > > vp_depth_first_shallow(VPBlockBase *G)
Returns an iterator range to traverse the graph starting at G in depth-first order.
Definition VPlanCFG.h:250
iterator_range< df_iterator< VPBlockDeepTraversalWrapper< VPBlockBase * > > > vp_depth_first_deep(VPBlockBase *G)
Returns an iterator range to traverse the graph starting at G in depth-first order while traversing t...
Definition VPlanCFG.h:285
auto map_range(ContainerTy &&C, FuncTy F)
Return a range that applies F to the elements of C.
Definition STLExtras.h:366
detail::concat_range< ValueT, RangeTs... > concat(RangeTs &&...Ranges)
Returns a concatenated range across two or more ranges.
Definition STLExtras.h:1167
auto make_isa_range(RangeT &&Range)
Return a range over Range containing only elements for which isa<T> holds, casting each of them to T.
Definition STLExtras.h:567
auto dyn_cast_or_null(const Y &Val)
Definition Casting.h:753
auto reverse(ContainerTy &&C)
Definition STLExtras.h:408
bool isa_and_present(const Y &Val)
isa_and_present<X> - Functionally identical to isa, except that a null value is accepted.
Definition Casting.h:669
SmallVector< ValueTypeFromRangeType< R >, Size > to_vector(R &&Range)
Given a range of type R, iterate the entire range and return a SmallVector with elements of the vecto...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:547
@ Add
Sum of integers.
DWARFExpression::Operation Op
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
constexpr detail::CastFunc< To > CastTo
Definition Casting.h:884
static void unrollByUF(VPlan &Plan, unsigned UF)
Explicitly unroll Plan by UF.
static bool mergeBlocksIntoPredecessors(VPlan &Plan)
Remove redundant VPBasicBlocks by merging them into their single predecessor if the latter has a sing...
static void removeDeadRecipes(VPlan &Plan)
Remove dead recipes from Plan.
static void replicateByVF(VPlan &Plan, ElementCount VF)
Replace replicating VPReplicateRecipe, VPScalarIVStepsRecipe and VPInstruction in Plan with VF single...