LLVM 24.0.0git
VPlanLowering.cpp
Go to the documentation of this file.
1//===- VPlanLowering.cpp - VPlan-to-VPlan lowering transforms -------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// This file implements VPlan-to-VPlan lowering transformations, which
11/// prepare an optimized VPlan for execution.
12///
13//===----------------------------------------------------------------------===//
14
16#include "VPlan.h"
17#include "VPlanAnalysis.h"
18#include "VPlanCFG.h"
19#include "VPlanDominatorTree.h"
20#include "VPlanHelpers.h"
21#include "VPlanPatternMatch.h"
22#include "VPlanTransforms.h"
23#include "VPlanUtils.h"
24#include "llvm/ADT/APInt.h"
25#include "llvm/ADT/STLExtras.h"
29#include "llvm/IR/Intrinsics.h"
30#include "llvm/IR/MDBuilder.h"
31#include "llvm/IR/Metadata.h"
35
36using namespace llvm;
37using namespace VPlanPatternMatch;
38using namespace SCEVPatternMatch;
39
43 unsigned UF) {
44 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();
45 if (!LoopRegion)
46 return;
47
48 auto *WideCanIV =
50 if (!WideCanIV)
51 return;
52
53 Type *CanIVTy = LoopRegion->getCanonicalIVType();
54
55 // Replace the wide canonical IV with a scalar-iv-steps over the canonical
56 // IV.
57 if (Plan.hasScalarVFOnly() || vputils::onlyFirstLaneUsed(WideCanIV)) {
58 VPBuilder Builder(WideCanIV);
59 WideCanIV->replaceAllUsesWith(vputils::createScalarIVSteps(
60 Plan, InductionDescriptor::IK_IntInduction, Instruction::Add, nullptr,
61 CanIVTy, Plan.getZero(CanIVTy), Plan.getConstantInt(CanIVTy, 1),
62 WideCanIV->getDebugLoc(), Builder,
63 WideCanIV->getNoWrapFlags().withoutNoSignedWrap()));
64 WideCanIV->eraseFromParent();
65 return;
66 }
67
68 if (vputils::onlyScalarValuesUsed(WideCanIV))
69 return;
70
71 // If a canonical VPWidenIntOrFpInductionRecipe already produces vector lanes
72 // in the header, reuse it instead of introducing another wide induction phi.
73 VPBasicBlock *Header = LoopRegion->getEntryBasicBlock();
74 for (VPRecipeBase &Phi : Header->phis()) {
76 if (!match(&Phi, m_CanonicalWidenIV(WidenIV)))
77 continue;
78 // The reused wide IV feeds the header mask, whose lanes may extend past
79 // the trip count; drop flags that only hold inside the scalar loop.
81 WideCanIV->replaceAllUsesWith(WidenIV);
82 WideCanIV->eraseFromParent();
83 return;
84 }
85
86 // Introduce a new VPWidenIntOrFpInductionRecipe if profitable.
87 auto *VecTy = VectorType::get(CanIVTy, VF);
88 InstructionCost BroadcastCost = TTI.getShuffleCost(
89 TargetTransformInfo::SK_Broadcast, VecTy, VecTy, CostKind);
90 InstructionCost PHICost = TTI.getCFInstrCost(Instruction::PHI, CostKind);
91 if (PHICost > BroadcastCost)
92 return;
93
94 // Bail out if the additional wide induction phi increase the expected spill
95 // cost.
96 VPRegisterUsage UnrolledBase =
98 for (unsigned &NumUsers : make_second_range(UnrolledBase.MaxLocalUsers))
99 NumUsers *= UF;
100 unsigned RegClass = TTI.getRegisterClassForType(/*Vector=*/true, VecTy);
101 VPRegisterUsage Projected = UnrolledBase;
102 Projected.MaxLocalUsers[RegClass] += TTI.getRegUsageForType(VecTy);
103 if (Projected.spillCost(TTI, CostKind) >
104 UnrolledBase.spillCost(TTI, CostKind))
105 return;
106
109 VPValue *StepV = Plan.getConstantInt(CanIVTy, 1);
110 auto *NewWideIV = new VPWidenIntOrFpInductionRecipe(
111 /*IV=*/nullptr, Plan.getZero(CanIVTy), StepV, &Plan.getVF(), ID,
112 WideCanIV->getNoWrapFlags(), WideCanIV->getDebugLoc());
113 NewWideIV->insertBefore(&*Header->getFirstNonPhi());
114 WideCanIV->replaceAllUsesWith(NewWideIV);
115 WideCanIV->eraseFromParent();
116}
117
118// Add a VPActiveLaneMaskPHIRecipe and related recipes to \p Plan and replace
119// the latch exit check with the negated wide-active-lane-mask. Note that this
120// turns the loop into an uncountable one. Other exit conditions combined with
121// the latch exit check are kept, all other existing recipes/users remain
122// unchanged. Return the created VPActiveLaneMaskPHIRecipe.
123//
124// The function adds the following recipes:
125//
126// vector.ph:
127// %EntryInc = canonical-iv-increment-for-part CanonicalIVStart
128// %EntryALM = wide-active-lane-mask %EntryInc, TC
129// %EntryALMPart = extract-vector-for-part %EntryALM, ir<0>
130//
131// vector.body:
132// ...
133// %P = active-lane-mask-phi [ %EntryALMPart, %vector.ph ],
134// [ %ALMPart, %vector.body ]
135// ...
136// %InLoopInc = canonical-iv-increment-for-part CanonicalIVIncrement
137// %ALM = wide-active-lane-mask %InLoopInc, TC
138// %ALMPart = extract-vector-for-part %ALM, ir<0>
139// %Negated = Not %ALMPart
140// branch-on-cond %Negated
141//
144 VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
145 VPBasicBlock *EB = TopRegion->getExitingBasicBlock();
146 VPValue *StartV = Plan.getZero(TopRegion->getCanonicalIVType());
147 auto *CanonicalIVIncrement = TopRegion->getOrCreateCanonicalIVIncrement();
148 DebugLoc DL = CanonicalIVIncrement->getDebugLoc();
149 auto *VecPreheader = Plan.getVectorPreheader();
150 VPBuilder Builder(VecPreheader);
151 VPValue *TC = Plan.getTripCount();
152
153 // Create the wide active lane mask instruction in the VPlan preheader.
154 VPValue *ALMMultiplier =
155 Plan.getConstantInt(TopRegion->getCanonicalIVType(), 1);
156 auto *EntryALM = Builder.createNaryOp(VPInstruction::WideActiveLaneMask,
157 {StartV, TC, ALMMultiplier}, DL,
158 "active.lane.mask.entry");
159 EntryALM = Builder.createNaryOp(VPInstruction::ExtractVectorForPart,
160 {EntryALM, Plan.getConstantInt(64, 0)}, DL,
161 "extract.entry.alm.part");
162
163 // Now create the ActiveLaneMaskPhi recipe in the main loop using the
164 // preheader WideActiveLaneMask instruction.
165 auto *LaneMaskPhi =
167 auto *HeaderVPBB = TopRegion->getEntryBasicBlock();
168 LaneMaskPhi->insertBefore(HeaderVPBB->begin());
169
170 // If the canonical IV increment could overflow, adjust the trip count (TC)
171 // to TC - VF * UF.
172 VPValue *IncrementValue = CanonicalIVIncrement;
173 if (!TopRegion->hasCanonicalIVNUW() &&
175 IncrementValue = TopRegion->getCanonicalIV();
176 VPValue &VFxUF = Plan.getVFxUF();
177 TC = Builder.createScalarIntrinsic(Intrinsic::usub_sat, {TC, &VFxUF},
178 TC->getScalarType(), DL,
179 "trip.count.minus.vf");
180 }
181
182 // The latch exit check is either the terminator or a compare combined with
183 // other exit conditions, e.g. by handleMaxMinNumReductions.
184 auto *LatchExit = cast<VPInstruction>(EB->getTerminator());
185 bool IsBranchOnCount = match(LatchExit, m_BranchOnCount());
186 if (!IsBranchOnCount) {
188 CanonicalIVIncrement,
189 m_SpecificICmp(CmpInst::ICMP_EQ, m_Specific(CanonicalIVIncrement),
191 assert(LatchExit && "expected latch exit compare");
192 }
193
194 // Create the active lane mask for the next iteration of the loop before the
195 // latch exit check.
196 Builder.setInsertPoint(LatchExit);
197 auto *ALM = Builder.createNaryOp(VPInstruction::WideActiveLaneMask,
198 {IncrementValue, TC, ALMMultiplier}, DL,
199 "active.lane.mask.next");
200 ALM = Builder.createNaryOp(VPInstruction::ExtractVectorForPart,
201 {ALM, Plan.getConstantInt(64, 0)}, DL,
202 "extract.next.alm.part");
203 LaneMaskPhi->addBackedgeValue(ALM);
204
205 // Replace the latch exit check with the negated mask. We have to invert the
206 // mask here because a true condition means jumping to the exit block.
207 auto *NotMask = Builder.createNot(ALM, DL);
208 if (IsBranchOnCount)
209 Builder.createNaryOp(VPInstruction::BranchOnCond, {NotMask}, DL);
210 else {
211 assert(LatchExit->getSingleUser()->usesFirstLaneOnly(LatchExit) &&
212 "Single user of latch exit compare must only use the first lane");
213 LatchExit->replaceAllUsesWith(NotMask);
214 }
215 LatchExit->eraseFromParent();
216 return LaneMaskPhi;
217}
218
220 VPlan &Plan, bool UseActiveLaneMask, bool UseActiveLaneMaskForControlFlow) {
221 VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion();
222 VPValue *HeaderMask = LoopRegion->getUsedHeaderMask();
223 if (!HeaderMask)
224 return;
225
226 if (UseActiveLaneMaskForControlFlow) {
228 return;
229 }
230
231 VPBasicBlock *Header = LoopRegion->getEntryBasicBlock();
232 VPBuilder Builder(Header->getFirstNonPhi());
233 auto *WideCanonicalIV = Builder.insert(new VPWidenCanonicalIVRecipe(
234 LoopRegion->getCanonicalIV(),
235 VPIRFlags::WrapFlagsTy(/*HasNUW=*/true, /*HasNSW=*/false)));
236 VPValue *Mask;
237 if (UseActiveLaneMask) {
238 Mask = Builder.createNaryOp(VPInstruction::ActiveLaneMask,
239 {WideCanonicalIV, Plan.getTripCount()}, nullptr,
240 "active.lane.mask");
241 } else {
242 // Compare against the backedge-taken count, TC - 1, computed in the vector
243 // preheader.
244 VPBasicBlock *VectorPH = Plan.getVectorPreheader();
245 VPValue *TC = Plan.getTripCount();
246 VPValue *BTC =
247 VPBuilder(VectorPH->getFirstNonPhi())
248 .createSub(TC, Plan.getConstantInt(TC->getScalarType(), 1),
249 DebugLoc::getCompilerGenerated(), "trip.count.minus.1");
250 if (!Plan.hasScalarVFOnly())
251 BTC = VPBuilder(VectorPH).createNaryOp(VPInstruction::Broadcast, BTC);
252 Mask = Builder.createICmp(CmpInst::ICMP_ULE, WideCanonicalIV, BTC);
253 }
254 HeaderMask->replaceAllUsesWith(Mask);
255}
256
257/// Expand a VPWidenIntOrFpInduction into executable recipes, for the initial
258/// value, phi and backedge value. In the following example:
259///
260/// vector.ph:
261/// Successor(s): vector loop
262///
263/// <x1> vector loop: {
264/// vector.body:
265/// WIDEN-INDUCTION %i = phi %start, %step, %vf
266/// ...
267/// EMIT branch-on-count ...
268/// No successors
269/// }
270///
271/// WIDEN-INDUCTION will get expanded to:
272///
273/// vector.ph:
274/// ...
275/// vp<%induction.start> = ...
276/// vp<%induction.increment> = ...
277///
278/// Successor(s): vector loop
279///
280/// <x1> vector loop: {
281/// vector.body:
282/// ir<%i> = WIDEN-PHI vp<%induction.start>, vp<%vec.ind.next>
283/// ...
284/// vp<%vec.ind.next> = add ir<%i>, vp<%induction.increment>
285/// EMIT branch-on-count ...
286/// No successors
287/// }
288static void
290 VPlan *Plan = WidenIVR->getParent()->getPlan();
291 VPValue *Start = WidenIVR->getStartValue();
292 VPValue *Step = WidenIVR->getStepValue();
293 VPValue *VF = WidenIVR->getVFValue();
294 DebugLoc DL = WidenIVR->getDebugLoc();
295
296 // The value from the original loop to which we are mapping the new induction
297 // variable.
298 Type *Ty = WidenIVR->getScalarType();
299
300 const InductionDescriptor &ID = WidenIVR->getInductionDescriptor();
303 VPIRFlags Flags = *WidenIVR;
304 if (ID.getKind() == InductionDescriptor::IK_IntInduction) {
305 AddOp = Instruction::Add;
306 MulOp = Instruction::Mul;
307 } else {
308 AddOp = ID.getInductionOpcode();
309 MulOp = Instruction::FMul;
310 }
311
312 // If the phi is truncated, truncate the start and step values.
313 VPBuilder Builder(Plan->getVectorPreheader());
314 Type *StepTy = Step->getScalarType();
315 if (Ty->getScalarSizeInBits() < StepTy->getScalarSizeInBits()) {
316 assert(StepTy->isIntegerTy() && "Truncation requires an integer type");
317 Step = Builder.createScalarCast(Instruction::Trunc, Step, Ty, DL);
318 Start = Builder.createScalarCast(Instruction::Trunc, Start, Ty, DL);
319 StepTy = Ty;
320 }
321
322 // Construct the initial value of the vector IV in the vector loop preheader.
323 Type *IVIntTy =
325 VPValue *Init = Builder.createNaryOp(VPInstruction::StepVector, {}, IVIntTy);
326 if (StepTy->isFloatingPointTy())
327 Init = Builder.createWidenCast(Instruction::UIToFP, Init, StepTy);
328
329 VPValue *SplatStart = Builder.createNaryOp(VPInstruction::Broadcast, Start);
330 VPValue *SplatStep = Builder.createNaryOp(VPInstruction::Broadcast, Step);
331
332 Init = Builder.createNaryOp(MulOp, {Init, SplatStep}, Flags);
333 Init = Builder.createNaryOp(AddOp, {SplatStart, Init}, Flags,
334 DebugLoc::getUnknown(), "induction");
335
336 // Create the widened phi of the vector IV.
337 auto *WidePHI = VPBuilder(WidenIVR).createWidenPhi(
338 Init, WidenIVR->getDebugLoc(), "vec.ind");
339
340 // Create the backedge value for the vector IV.
341 VPValue *Inc;
342 VPValue *Prev;
343 // If unrolled, use the increment and prev value from the operands.
344 if (auto *SplatVF = WidenIVR->getSplatVFValue()) {
345 Inc = SplatVF;
346 Prev = WidenIVR->getLastUnrolledPartOperand();
347 } else {
348 // Move the insertion point after the VF definition when the VF is defined
349 // inside a loop, such as for EVL tail-folding.
350 if (VPRecipeBase *R = VF->getDefiningRecipe())
351 if (R->getParent()->getEnclosingLoopRegion())
352 Builder.setInsertPoint(std::next(R->getIterator()));
353
354 // Multiply the vectorization factor by the step using integer or
355 // floating-point arithmetic as appropriate.
356 if (StepTy->isFloatingPointTy())
357 VF = Builder.createScalarCast(Instruction::CastOps::UIToFP, VF, StepTy,
358 DL);
359 else
360 VF = Builder.createScalarZExtOrTrunc(VF, StepTy, DL);
361
362 Inc = Builder.createNaryOp(MulOp, {Step, VF}, Flags);
363 Inc = Builder.createNaryOp(VPInstruction::Broadcast, Inc);
364 Prev = WidePHI;
365 }
366
368 Builder.setInsertPoint(ExitingBB->getTerminator());
369 auto *Next = Builder.createNaryOp(AddOp, {Prev, Inc}, Flags,
370 WidenIVR->getDebugLoc(), "vec.ind.next");
371
372 WidePHI->addIncoming(Next);
373
374 WidenIVR->replaceAllUsesWith(WidePHI);
375}
376
377/// Expand a VPWidenPointerInductionRecipe into executable recipes, for the
378/// initial value, phi and backedge value. In the following example:
379///
380/// <x1> vector loop: {
381/// vector.body:
382/// EMIT ir<%ptr.iv> = WIDEN-POINTER-INDUCTION %start, %step, %vf
383/// ...
384/// EMIT branch-on-count ...
385/// }
386///
387/// WIDEN-POINTER-INDUCTION will get expanded to:
388///
389/// <x1> vector loop: {
390/// vector.body:
391/// EMIT-SCALAR %pointer.phi = phi %start, %ptr.ind
392/// EMIT %mul = mul %stepvector, %step
393/// EMIT %vector.gep = wide-ptradd %pointer.phi, %mul
394/// ...
395/// EMIT %ptr.ind = ptradd %pointer.phi, %vf
396/// EMIT branch-on-count ...
397/// }
399 VPlan *Plan = R->getParent()->getPlan();
400 VPValue *Start = R->getStartValue();
401 VPValue *Step = R->getStepValue();
402 VPValue *VF = R->getVFValue();
403
404 assert(R->getInductionDescriptor().getKind() ==
406 "Not a pointer induction according to InductionDescriptor!");
407 assert(R->getScalarType()->isPointerTy() && "Unexpected type.");
408 assert(!R->onlyScalarsGenerated(Plan->hasScalableVF()) &&
409 "Recipe should have been replaced");
410
411 VPBuilder Builder(R);
412 DebugLoc DL = R->getDebugLoc();
413
414 // Build a scalar pointer phi.
415 VPPhi *ScalarPtrPhi = Builder.createScalarPhi(Start, DL, "pointer.phi");
416
417 // Create actual address geps that use the pointer phi as base and a
418 // vectorized version of the step value (<step*0, ..., step*N>) as offset.
419 Builder.setInsertPoint(R->getParent()->getFirstNonPhi());
420 Type *StepTy = Step->getScalarType();
421 VPValue *Offset = Builder.createNaryOp(VPInstruction::StepVector, {}, StepTy);
422 Offset = Builder.createOverflowingOp(Instruction::Mul, {Offset, Step});
423 VPValue *PtrAdd =
424 Builder.createWidePtrAdd(ScalarPtrPhi, Offset, DL, "vector.gep");
425 R->replaceAllUsesWith(PtrAdd);
426
427 // Create the backedge value for the scalar pointer phi.
429 Builder.setInsertPoint(ExitingBB->getTerminator());
430 VF = Builder.createScalarZExtOrTrunc(VF, StepTy, DL);
431 VPValue *Inc = Builder.createOverflowingOp(Instruction::Mul, {Step, VF});
432
433 VPValue *InductionGEP =
434 Builder.createPtrAdd(ScalarPtrPhi, Inc, DL, "ptr.ind");
435 ScalarPtrPhi->addIncoming(InductionGEP);
436}
437
438/// Expand a VPDerivedIVRecipe into executable recipes.
440 VPBuilder Builder(R);
441 VPValue *Start = R->getStartValue();
442 VPValue *Step = R->getStepValue();
443 VPValue *Index = R->getIndex();
444 Type *StepTy = Step->getScalarType();
445 Index = StepTy->isIntegerTy()
446 ? Builder.createScalarZExtOrTrunc(
447 Index, StepTy, DebugLoc::getCompilerGenerated())
448 : Builder.createScalarCast(Instruction::UIToFP, Index, StepTy,
450 VPIRFlags::WrapFlagsTy Flags = R->getNoWrapFlags();
451 switch (R->getInductionKind()) {
453 assert(Index->getScalarType() == Start->getScalarType() &&
454 "Index type does not match StartValue type");
455 return R->replaceAllUsesWith(Builder.createAdd(
456 Start,
457 Builder.createOverflowingOp(Instruction::Mul, {Index, Step}, Flags),
458 DebugLoc::getUnknown(), "", Flags));
459 }
461 return R->replaceAllUsesWith(Builder.createPtrAdd(
462 Start,
463 Builder.createOverflowingOp(Instruction::Mul, {Index, Step}, Flags)));
465 assert(StepTy->isFloatingPointTy() && "Expected FP Step value");
466 const FPMathOperator *FPBinOp = R->getFPBinOp();
467 assert(FPBinOp &&
468 (FPBinOp->getOpcode() == Instruction::FAdd ||
469 FPBinOp->getOpcode() == Instruction::FSub) &&
470 "Original BinOp should be defined for FP induction");
471 FastMathFlags FMF = FPBinOp->getFastMathFlags();
472 VPValue *FMul = Builder.createNaryOp(Instruction::FMul, {Step, Index}, FMF);
473 return R->replaceAllUsesWith(
474 Builder.createNaryOp(FPBinOp->getOpcode(), {Start, FMul}, FMF));
475 }
477 return;
478 }
479 llvm_unreachable("Unhandled induction kind");
480}
481
483 // Replace loop regions with explicity CFG.
486 vp_depth_first_deep(Plan.getEntry()))) {
487 if (!R->isReplicator())
488 LoopRegions.push_back(R);
489 }
490 for (VPRegionBlock *R : LoopRegions)
491 R->dissolveToCFGLoop();
492}
493
496 // The transform runs after dissolving loop regions, so all VPBasicBlocks
497 // terminated with BranchOnTwoConds are reached via a shallow traversal.
500 if (!VPBB->empty() && match(&VPBB->back(), m_BranchOnTwoConds()))
501 WorkList.push_back(cast<VPInstruction>(&VPBB->back()));
502 }
503
504 // Expand BranchOnTwoConds instructions into explicit CFG with two new
505 // single-condition branches:
506 // 1. A branch that replaces BranchOnTwoConds, jumps to the first successor if
507 // the first condition is true, and otherwise jumps to a new interim block.
508 // 2. A branch that ends the interim block, jumps to the second successor if
509 // the second condition is true, and otherwise jumps to the third
510 // successor.
511 for (VPInstruction *Br : WorkList) {
512 assert(Br->getNumOperands() == 2 &&
513 "BranchOnTwoConds must have exactly 2 conditions");
514 DebugLoc DL = Br->getDebugLoc();
515 VPBasicBlock *BrOnTwoCondsBB = Br->getParent();
516 const auto Successors = to_vector(BrOnTwoCondsBB->getSuccessors());
517 assert(Successors.size() == 3 &&
518 "BranchOnTwoConds must have exactly 3 successors");
519
520 for (VPBlockBase *Succ : Successors)
521 VPBlockUtils::disconnectBlocks(BrOnTwoCondsBB, Succ);
522
523 VPValue *Cond0 = Br->getOperand(0);
524 VPValue *Cond1 = Br->getOperand(1);
525 VPBlockBase *Succ0 = Successors[0];
526 VPBlockBase *Succ1 = Successors[1];
527 VPBlockBase *Succ2 = Successors[2];
528
529 // If the successor block for both conditions is the same, then combine the
530 // two conditions and plant a single conditional branch.
531 if (Succ0 == Succ1) {
532 VPBuilder Builder(Br);
533 VPValue *Combined = Builder.createOr(Cond0, Cond1, DL);
534 Builder.createNaryOp(VPInstruction::BranchOnCond, {Combined}, DL);
535 VPBlockUtils::connectBlocks(BrOnTwoCondsBB, Succ0);
536 VPBlockUtils::connectBlocks(BrOnTwoCondsBB, Succ2);
537 Br->eraseFromParent();
538 continue;
539 }
540
541 assert(!Succ0->getParent() && !Succ1->getParent() && !Succ2->getParent() &&
542 !BrOnTwoCondsBB->getParent() && "regions must already be dissolved");
543
544 VPBasicBlock *InterimBB =
545 Plan.createVPBasicBlock(BrOnTwoCondsBB->getName() + ".interim");
546
547 VPBuilder(BrOnTwoCondsBB)
549 VPBlockUtils::connectBlocks(BrOnTwoCondsBB, Succ0);
550 VPBlockUtils::connectBlocks(BrOnTwoCondsBB, InterimBB);
551
553 VPBlockUtils::connectBlocks(InterimBB, Succ1);
554 VPBlockUtils::connectBlocks(InterimBB, Succ2);
555 Br->eraseFromParent();
556 }
557}
558
561 vp_depth_first_deep(Plan.getEntry()))) {
562 for (VPRecipeBase &R : make_early_inc_range(*VPBB)) {
563 VPBuilder Builder(&R);
564 // !prof is only supported on scalar selects.
565 if (auto *Widen = dyn_cast<VPWidenRecipe>(&R)) {
566 if (Widen->getOpcode() == Instruction::Select &&
567 !vputils::isSingleScalar(Widen->getOperand(0)))
568 Widen->eraseMetadata(LLVMContext::MD_prof);
569 }
570
571 if (auto *WidenIVR = dyn_cast<VPWidenIntOrFpInductionRecipe>(&R)) {
573 WidenIVR->eraseFromParent();
574 continue;
575 }
576
577 if (auto *WidenIVR = dyn_cast<VPWidenPointerInductionRecipe>(&R)) {
578 // If the recipe only generates scalars, scalarize it instead of
579 // expanding it.
580 if (WidenIVR->onlyScalarsGenerated(Plan.hasScalableVF())) {
582 WidenIVR, Plan, Builder);
583 WidenIVR->replaceAllUsesWith(PtrAdd);
584 WidenIVR->eraseFromParent();
585 continue;
586 }
588 WidenIVR->eraseFromParent();
589 continue;
590 }
591
592 if (auto *CondIV = dyn_cast<VPConditionalInductionPHIRecipe>(&R)) {
593 VPPhi *CondIVPhi = Builder.createScalarPhi(
594 CondIV->getStartValue(), CondIV->getDebugLoc(), "conditional.iv");
595 CondIVPhi->addIncoming(CondIV->getBackedgeValue());
596 CondIV->replaceAllUsesWith(CondIVPhi);
597 CondIV->eraseFromParent();
598 continue;
599 }
600
601 if (auto *DerivedIVR = dyn_cast<VPDerivedIVRecipe>(&R)) {
602 expandVPDerivedIV(DerivedIVR);
603 DerivedIVR->eraseFromParent();
604 continue;
605 }
606
607 if (auto *WideCanIV = dyn_cast<VPWidenCanonicalIVRecipe>(&R)) {
608 VPValue *CanIV = WideCanIV->getCanonicalIV();
609 Type *CanIVTy = CanIV->getScalarType();
610 VPValue *Step = WideCanIV->getStepValue();
611 if (!Step) {
612 assert(Plan.getConcreteUF() == 1 &&
613 "Expected unroller to have materialized step for UF != 1");
614 Step = Plan.getZero(CanIVTy);
615 }
616 CanIV = Builder.createNaryOp(VPInstruction::Broadcast, CanIV);
617 Step = Builder.createNaryOp(VPInstruction::Broadcast, Step);
618 Step = Builder.createAdd(
619 Step, Builder.createNaryOp(VPInstruction::StepVector, {}, CanIVTy));
620 VPValue *CanVecIV =
621 Builder.createAdd(CanIV, Step, WideCanIV->getDebugLoc(), "vec.iv",
622 WideCanIV->getNoWrapFlags());
623 WideCanIV->replaceAllUsesWith(CanVecIV);
624 WideCanIV->eraseFromParent();
625 continue;
626 }
627
628 // Expand VPBlendRecipe into VPInstruction::Select.
629 if (auto *Blend = dyn_cast<VPBlendRecipe>(&R)) {
630 VPValue *Select = Blend->getIncomingValue(0);
631 for (unsigned I = 1; I != Blend->getNumIncomingValues(); ++I)
632 Select = Builder.createSelect(Blend->getMask(I),
633 Blend->getIncomingValue(I), Select,
634 R.getDebugLoc(), "predphi", *Blend);
635 Blend->replaceAllUsesWith(Select);
636 Blend->eraseFromParent();
637 continue;
638 }
639
640 if (auto *VEPR = dyn_cast<VPVectorEndPointerRecipe>(&R)) {
641 if (!VEPR->getOffset()) {
642 assert(Plan.getConcreteUF() == 1 &&
643 "Expected unroller to have materialized offset for UF != 1");
644 VEPR->materializeOffset();
645 }
646 continue;
647 }
648
649 if (auto *Expr = dyn_cast<VPExpressionRecipe>(&R)) {
650 Expr->decompose();
651 Expr->eraseFromParent();
652 continue;
653 }
654
655 // Expand LastActiveLane into Not + FirstActiveLane + Sub.
656 auto *LastActiveL = dyn_cast<VPInstruction>(&R);
657 if (LastActiveL &&
658 LastActiveL->getOpcode() == VPInstruction::LastActiveLane) {
659 // Create Not(Mask) for all operands.
661 for (VPValue *Op : LastActiveL->operands()) {
662 VPValue *NotMask = Builder.createNot(Op, LastActiveL->getDebugLoc());
663 NotMasks.push_back(NotMask);
664 }
665
666 // Create FirstActiveLane on the inverted masks.
667 VPValue *FirstInactiveLane = Builder.createFirstActiveLane(
668 NotMasks, LastActiveL->getDebugLoc(), "first.inactive.lane");
669
670 // Subtract 1 to get the last active lane.
671 VPValue *One =
672 Plan.getConstantInt(FirstInactiveLane->getScalarType(), 1);
673 VPValue *LastLane =
674 Builder.createSub(FirstInactiveLane, One,
675 LastActiveL->getDebugLoc(), "last.active.lane");
676
677 LastActiveL->replaceAllUsesWith(LastLane);
678 LastActiveL->eraseFromParent();
679 continue;
680 }
681
682 // Lower CanonicalIVIncrementForPart to plain Add.
683 if (match(
684 &R,
686 auto *VPI = cast<VPInstruction>(&R);
687 VPValue *Add = Builder.createOverflowingOp(
688 Instruction::Add, VPI->operands(), VPI->getNoWrapFlags(),
689 VPI->getDebugLoc());
690 VPI->replaceAllUsesWith(Add);
691 VPI->eraseFromParent();
692 continue;
693 }
694
695 // Lower BranchOnCount to ICmp + BranchOnCond.
696 VPValue *IV, *TC;
697 if (match(&R, m_BranchOnCount(m_VPValue(IV), m_VPValue(TC)))) {
698 auto *BranchOnCountInst = cast<VPInstruction>(&R);
699 DebugLoc DL = BranchOnCountInst->getDebugLoc();
700 VPValue *Cond = Builder.createICmp(CmpInst::ICMP_EQ, IV, TC, DL);
701 Builder.createNaryOp(VPInstruction::BranchOnCond, Cond, DL);
702 BranchOnCountInst->eraseFromParent();
703 continue;
704 }
705
706 VPValue *VectorStep;
707 VPValue *ScalarStep;
709 m_VPValue(VectorStep), m_VPValue(ScalarStep))))
710 continue;
711
712 // Expand WideIVStep.
713 auto *VPI = cast<VPInstruction>(&R);
714 Type *IVTy = VPI->getScalarType();
715 if (VectorStep->getScalarType() != IVTy) {
717 ? Instruction::UIToFP
718 : Instruction::Trunc;
719 VectorStep = Builder.createWidenCast(CastOp, VectorStep, IVTy);
720 }
721
722 assert(!match(ScalarStep, m_One()) && "Expected non-unit scalar-step");
723 if (ScalarStep->getScalarType() != IVTy) {
724 ScalarStep =
725 Builder.createWidenCast(Instruction::Trunc, ScalarStep, IVTy);
726 }
727
728 VPIRFlags Flags;
729 unsigned MulOpc;
730 if (IVTy->isFloatingPointTy()) {
731 MulOpc = Instruction::FMul;
732 Flags = VPI->getFastMathFlagsOrNone();
733 } else {
734 MulOpc = Instruction::Mul;
735 Flags = VPIRFlags::getDefaultFlags(MulOpc);
736 }
737
738 VPInstruction *Mul = Builder.createNaryOp(
739 MulOpc, {VectorStep, ScalarStep}, Flags, R.getDebugLoc());
740 VectorStep = Mul;
741 VPI->replaceAllUsesWith(VectorStep);
742 VPI->eraseFromParent();
743 }
744 }
745}
746
748 if (Plan.hasScalarVFOnly())
749 return;
750
751#ifndef NDEBUG
752 VPDominatorTree VPDT(Plan);
753#endif
754
755 SmallVector<VPValue *> VPValues;
756 append_range(VPValues, Plan.getLiveIns());
757 for (VPRecipeBase &R : *Plan.getEntry())
758 append_range(VPValues, R.definedValues());
759
760 auto *VectorPreheader = Plan.getVectorPreheader();
761 for (VPValue *VPV : VPValues) {
763 continue;
764
765 // Add explicit broadcast at the insert point that dominates all users.
766 VPBasicBlock::iterator HoistPoint = VectorPreheader->end();
767 for (VPUser *User : VPV->users()) {
768 if (User->usesScalars(VPV))
769 continue;
770 if (cast<VPRecipeBase>(User)->getParent() == VectorPreheader)
771 HoistPoint = VectorPreheader->getFirstNonPhi();
772 else
773 assert(VPDT.dominates(VectorPreheader,
774 cast<VPRecipeBase>(User)->getParent()) &&
775 "All users must be in the vector preheader or dominated by it");
776 }
777
778 VPBuilder Builder(HoistPoint);
779 auto *Broadcast = Builder.createNaryOp(VPInstruction::Broadcast, {VPV});
780 VPV->replaceUsesWithIf(Broadcast, [VPV, Broadcast](VPUser *U) {
781 return Broadcast != U && !U->usesScalars(VPV);
782 });
783 }
784}
785
787 VPlan &Plan, ElementCount BestVF, unsigned BestUF,
789 assert(Plan.hasVF(BestVF) && "BestVF is not available in Plan");
790 assert(Plan.hasUF(BestUF) && "BestUF is not available in Plan");
791
792 VPValue *TC = Plan.getTripCount();
793 if (TC->user_empty())
794 return;
795
796 // Skip cases for which the trip count may be non-trivial to materialize.
797 // I.e., when a scalar tail is absent - due to tail folding, or when a scalar
798 // tail is required.
799 if (Plan.hasTailFolded() || !Plan.hasScalarTail() ||
801 Plan.getScalarPreheader() ||
802 !isa<VPIRValue>(TC))
803 return;
804
805 // Materialize vector trip counts for constants early if it can simply
806 // be computed as (Original TC / VF * UF) * VF * UF.
807 // TODO: Compute vector trip counts for loops requiring a scalar epilogue and
808 // tail-folded loops.
809 ScalarEvolution &SE = *PSE.getSE();
810 auto *TCScev = SE.getSCEV(TC->getLiveInIRValue());
811 if (!isa<SCEVConstant>(TCScev))
812 return;
813 const SCEV *VFxUF = SE.getElementCount(TCScev->getType(), BestVF * BestUF);
814 const SCEV *VecTCScev = SE.getMulExpr(SE.getUDivExpr(TCScev, VFxUF), VFxUF);
815 if (auto *ConstVecTC = dyn_cast<SCEVConstant>(VecTCScev))
816 Plan.getVectorTripCount().setUnderlyingValue(ConstVecTC->getValue());
817}
818
820 if (Plan.hasScalarVFOnly())
821 return;
822
823 auto VPBBsInsideLoopRegion = VPBlockUtils::blocksOnly<VPBasicBlock>(
825 // Create explicit VPInstructions to convert vectors to scalars. The current
826 // implementation is conservative - it may miss some cases that may or may not
827 // be vector values. TODO: introduce Unpacks speculatively - remove them later
828 // if they are known to operate on scalar values.
829 for (VPBasicBlock *VPBB : VPBBsInsideLoopRegion) {
830 for (VPRecipeBase &R : make_early_inc_range(*VPBB)) {
833 continue;
834 for (VPValue *Def : R.definedValues()) {
835 // Skip recipes that are single-scalar.
836 // TODO: The Defs skipped here may or may not be vector values.
837 // Introduce Unpacks, and remove them later, if they are guaranteed to
838 // produce scalar values.
840 continue;
841
842 // Only introduce an Unpack if some, but not all, users use the first
843 // lane only.
844 unsigned NumFirstLaneUsers = count_if(Def->users(), [&Def](VPUser *U) {
845 return U->usesFirstLaneOnly(Def);
846 });
847 if (!NumFirstLaneUsers || NumFirstLaneUsers == Def->getNumUsers())
848 continue;
849
850 auto *Unpack = new VPInstruction(VPInstruction::Unpack, {Def});
851 if (R.isPhi())
852 Unpack->insertBefore(VPBB->getFirstNonPhi());
853 else
854 Unpack->insertAfter(&R);
855 Def->replaceUsesWithIf(
856 Unpack, [&Def](VPUser *U) { return U->usesFirstLaneOnly(Def); });
857 }
858 }
859 }
860}
861
863 VPlan &Plan, VPBasicBlock *VectorPHVPBB, bool TailByMasking,
864 bool RequiresScalarEpilogue, VPValue *Step,
865 std::optional<uint64_t> MaxRuntimeStep) {
866 VPSymbolicValue &VectorTC = Plan.getVectorTripCount();
867 // There's nothing to do if there are no users of the vector trip count or its
868 // IR value has already been set.
869 if (VectorTC.user_empty() || VectorTC.getUnderlyingValue())
870 return;
871
872 VPValue *TC = Plan.getTripCount();
873 Type *TCTy = TC->getScalarType();
875 if (auto *StepR = Step->getDefiningRecipe()) {
876 assert(VPDominatorTree(Plan).dominates(StepR->getParent(), VectorPHVPBB) &&
877 "Step VPBB must dominate VectorPHVPBB");
878 // Insert after Step's definition to maintain valid def-use ordering.
879 InsertPt = std::next(StepR->getIterator());
880 }
881 VPBuilder Builder(InsertPt);
882
883 // For scalable steps, if TC is a constant and is divisible by the maximum
884 // possible runtime step, then TC % Step == 0 for all valid vscale values
885 // and the vector trip count equals TC directly.
886 const APInt *TCVal;
887 if (!RequiresScalarEpilogue && match(TC, m_APInt(TCVal)) && MaxRuntimeStep &&
888 TCVal->urem(*MaxRuntimeStep) == 0) {
889 VectorTC.replaceAllUsesWith(TC);
890 return;
891 }
892
893 // If the tail is to be folded by masking, round the number of iterations N
894 // up to a multiple of Step instead of rounding down. This is done by first
895 // adding Step-1 and then rounding down. Note that it's ok if this addition
896 // overflows: the vector induction variable will eventually wrap to zero given
897 // that it starts at zero and its Step is a power of two; the loop will then
898 // exit, with the last early-exit vector comparison also producing all-true.
899 if (TailByMasking) {
900 TC = Builder.createAdd(
901 TC, Builder.createSub(Step, Plan.getConstantInt(TCTy, 1)),
902 DebugLoc::getCompilerGenerated(), "n.rnd.up");
903 }
904
905 // Now we need to generate the expression for the part of the loop that the
906 // vectorized body will execute. This is equal to N - (N % Step) if scalar
907 // iterations are not required for correctness, or N - Step, otherwise. Step
908 // is equal to the vectorization factor (number of SIMD elements) times the
909 // unroll factor (number of SIMD instructions).
910 VPValue *R =
911 Builder.createNaryOp(Instruction::URem, {TC, Step},
912 DebugLoc::getCompilerGenerated(), "n.mod.vf");
913
914 // There are cases where we *must* run at least one iteration in the remainder
915 // loop. See the cost model for when this can happen. If the step evenly
916 // divides the trip count, we set the remainder to be equal to the step. If
917 // the step does not evenly divide the trip count, no adjustment is necessary
918 // since there will already be scalar iterations. Note that the minimum
919 // iterations check ensures that N >= Step.
920 if (RequiresScalarEpilogue) {
921 assert(!TailByMasking &&
922 "requiring scalar epilogue is not supported with fail folding");
923 VPValue *IsZero =
924 Builder.createICmp(CmpInst::ICMP_EQ, R, Plan.getZero(TCTy));
925 R = Builder.createSelect(IsZero, Step, R);
926 }
927
928 VPValue *Res =
929 Builder.createSub(TC, R, DebugLoc::getCompilerGenerated(), "n.vec");
930 VectorTC.replaceAllUsesWith(Res);
931}
932
934 ElementCount VFEC) {
935 // If VF and VFxUF have already been materialized (no remaining users),
936 // there's nothing more to do.
937 if (Plan.getVF().isMaterialized()) {
938 assert(Plan.getVFxUF().isMaterialized() &&
939 "VF and VFxUF must be materialized together");
940 return;
941 }
942
943 VPBuilder Builder(VectorPH->getFirstNonPhi());
944 Type *TCTy = Plan.getTripCount()->getScalarType();
945 VPValue &VF = Plan.getVF();
946 VPValue &VFxUF = Plan.getVFxUF();
947 // If there are no users of the runtime VF, compute VFxUF by constant folding
948 // the multiplication of VF and UF.
949 if (VF.user_empty()) {
950 VPValue *RuntimeVFxUF =
951 Builder.createElementCount(TCTy, VFEC * Plan.getConcreteUF());
952 VFxUF.replaceAllUsesWith(RuntimeVFxUF);
953 return;
954 }
955
956 // For users of the runtime VF, compute it as VF * vscale, and VFxUF as (VF *
957 // vscale) * UF.
958 VPValue *RuntimeVF = Builder.createElementCount(TCTy, VFEC);
960 VPValue *BC = Builder.createNaryOp(VPInstruction::Broadcast, RuntimeVF);
961 VF.replaceUsesWithIf(BC, [&VF](VPUser *U) { return !U->usesScalars(&VF); });
962 }
963 VF.replaceAllUsesWith(RuntimeVF);
964
965 VPValue *MulByUF =
966 Builder.createElementCount(TCTy, VFEC * Plan.getConcreteUF());
967 VFxUF.replaceAllUsesWith(MulByUF);
968}
969
970VPValue *
972 ArrayRef<PointerDiffInfo> DiffChecks,
973 ScalarEvolution &SE) {
974 VPBuilder Builder(AliasCheckVPBB);
975 VPSCEVExpander Expander(Builder, SE, DebugLoc::getCompilerGenerated());
976 Type *I1Ty = IntegerType::getInt1Ty(Plan.getContext());
977
978 VPValue *IncomingAliasMask = vputils::findIncomingAliasMask(Plan);
979 assert(IncomingAliasMask && "Expected an alias mask!");
980
981 VPValue *AliasMask = nullptr;
982 for (const PointerDiffInfo &Check : DiffChecks) {
983 VPValue *Src = Expander.expand(Check.SrcStart);
984 VPValue *Sink = Expander.expand(Check.SinkStart);
985 Type *AddrType = Src->getScalarType();
986
987 // TODO: Only freeze the required pointer (not both src and sink).
988 if (Check.NeedsFreeze) {
989 Src = Builder.createFreeze(Src);
990 Sink = Builder.createFreeze(Sink);
991 }
992
993 // TODO: Generate loop_dependence_raw_mask when there's a read-after-write
994 // dependency between the source and the sink. This is not necessary for
995 // correctness of the mask, but using the "raw" variant prevents loads
996 // depending on the completion of stores.
997 VPWidenIntrinsicRecipe *WARMask = Builder.insert(new VPWidenIntrinsicRecipe(
998 Intrinsic::loop_dependence_war_mask,
999 {Src, Sink, Plan.getConstantInt(AddrType, Check.AccessSize)}, I1Ty));
1000
1001 if (AliasMask)
1002 AliasMask = Builder.createAnd(AliasMask, WARMask);
1003 else
1004 AliasMask = WARMask;
1005 }
1006
1008 Type *IndexTy = Plan.getDataLayout().getIndexType(Plan.getContext(), 0);
1009 VPValue *NumActive = Builder.createNaryOp(
1010 VPInstruction::NumActiveLanes, {AliasMask}, nullptr, {}, {},
1011 DebugLoc::getUnknown(), "num.active.lanes", IndexTy);
1012 VPValue *ClampedVF = Builder.createScalarZExtOrTrunc(
1013 NumActive, IVTy, DebugLoc::getCompilerGenerated());
1014
1015 IncomingAliasMask->replaceAllUsesWith(AliasMask);
1016
1017 return ClampedVF;
1018}
1019
1021 VPlan &Plan, ArrayRef<PointerDiffInfo> DiffChecks, ScalarEvolution &SE,
1022 bool HasBranchWeights) {
1023 VPBasicBlock *ClampedVFCheck =
1024 Plan.createVPBasicBlock("vector.clamped.vf.check");
1025
1026 VPValue *ClampedVF =
1027 materializeAliasMask(Plan, ClampedVFCheck, DiffChecks, SE);
1028 VPBuilder Builder(ClampedVFCheck);
1030 Type *TCTy = Plan.getTripCount()->getScalarType();
1031
1032 // Check the "ClampedVF" from the alias mask is larger than one.
1033 VPValue *IsScalar =
1034 Builder.createICmp(CmpInst::ICMP_ULE, ClampedVF,
1035 Plan.getConstantInt(TCTy, 1), DL, "vf.is.scalar");
1036
1037 VPValue *TripCount = Plan.getTripCount();
1038 VPValue *MaxUIntTripCount =
1040 VPValue *DistanceToMax = Builder.createSub(MaxUIntTripCount, TripCount);
1041
1042 // For tail-folding: Don't execute the vector loop if (UMax - n) < ClampedVF.
1043 // Note: The ClampedVF may not be a power-of-two. This means the loop exit
1044 // condition (index.next == n.vec) may not be correct in the case of an
1045 // overflow. The issue is `n.vec` could be zero due to an overflow, but
1046 // index.next is not guaranteed to overflow to zero as the ClampedVF is not a
1047 // power-of-two).
1048 VPValue *TripCountCheck = Builder.createICmp(
1049 ICmpInst::ICMP_ULT, DistanceToMax, ClampedVF, DL, "vf.step.overflow");
1050
1051 VPValue *Cond = Builder.createOr(IsScalar, TripCountCheck, DL);
1052 attachVPCheckBlock(Plan, Cond, ClampedVFCheck, HasBranchWeights);
1053
1054 // Materialize the trip count early as this will add a use of (VFxUF) that
1055 // needs to be replaced with the ClampedVF.
1057 /*TailByMasking=*/true,
1058 /*RequiresScalarEpilogue=*/false,
1059 &Plan.getVFxUF());
1060
1061 assert(Plan.getConcreteUF() == 1 &&
1062 "Clamped VF not supported with interleaving");
1063 Plan.getVF().replaceAllUsesWith(ClampedVF);
1064 Plan.getVFxUF().replaceAllUsesWith(ClampedVF);
1065}
1066
1068 ScalarEvolution &SE) {
1069 auto *Entry = Plan.getEntry();
1070 VPBuilder Builder(Entry->begin());
1072 ->getIRBasicBlock()
1073 ->getTerminator()
1074 ->getDebugLoc();
1075 VPSCEVExpander Expander(Builder, SE, DL);
1076
1077 // Expand VPExpandSCEVRecipes to VPInstructions using VPSCEVExpander.
1078 for (VPExpandSCEVRecipe &ExpSCEV :
1080 if (ExpSCEV.user_empty())
1081 continue;
1082 Builder.setInsertPoint(&ExpSCEV);
1083 VPValue *Expanded = Expander.expand(ExpSCEV);
1084 if (Expanded == &ExpSCEV)
1085 continue;
1086 ExpSCEV.replaceAllUsesWith(Expanded);
1087 // TripCount should not be used after expansion to VPInstructions. Reset to
1088 // poison to avoid dangling references.
1089 if (Plan.getTripCount() == &ExpSCEV)
1090 Plan.resetTripCount(Plan.getPoison(ExpSCEV.getScalarType()));
1091 ExpSCEV.eraseFromParent();
1092 }
1093}
1094
1097 // The IR SCEVExpander may expand expressions early, where they may cause UB.
1098 // Use SafeDivisorMode.
1099 SCEVExpander Expander(SE, "induction", /*PreserveLCSSA=*/false,
1100 /*SafeDivisorMode=*/true);
1101
1102 auto *Entry = cast<VPIRBasicBlock>(Plan.getEntry());
1103 BasicBlock *EntryBB = Entry->getIRBasicBlock();
1104 DenseMap<const SCEV *, Value *> ExpandedSCEVs;
1105 // Expand remaining VPExpandSCEVRecipes to IR instructions using SCEVExpander.
1106 for (VPExpandSCEVRecipe &ExpSCEV :
1108 const SCEV *Expr = ExpSCEV.getSCEV();
1109 Value *Res =
1110 Expander.expandCodeFor(Expr, Expr->getType(), EntryBB->getTerminator());
1111 ExpandedSCEVs[Expr] = Res;
1112 VPValue *Exp = Plan.getOrAddLiveIn(Res);
1113 ExpSCEV.replaceAllUsesWith(Exp);
1114 if (Plan.getTripCount() == &ExpSCEV)
1115 Plan.resetTripCount(Exp);
1116 ExpSCEV.eraseFromParent();
1117 }
1119 "all VPExpandSCEVRecipes must have been expanded");
1120 // Add IR instructions in the entry basic block but not in the VPIRBasicBlock
1121 // to the VPIRBasicBlock.
1122 auto EI = Entry->begin();
1123 for (Instruction &I : drop_end(*EntryBB)) {
1124 if (EI != Entry->end() && isa<VPIRInstruction>(*EI) &&
1125 &cast<VPIRInstruction>(&*EI)->getInstruction() == &I) {
1126 EI++;
1127 continue;
1128 }
1130 }
1131
1132 return ExpandedSCEVs;
1133}
1134
1135/// Add branch weight metadata, if the \p Plan's middle block is terminated by a
1136/// BranchOnCond recipe.
1138 VPlan &Plan, ElementCount VF, std::optional<unsigned> VScaleForTuning) {
1139 VPBasicBlock *MiddleVPBB = Plan.getMiddleBlock();
1140 auto *MiddleTerm =
1142 // Only add branch metadata if there is a (conditional) terminator.
1143 if (!MiddleTerm)
1144 return;
1145
1146 assert(MiddleTerm->getOpcode() == VPInstruction::BranchOnCond &&
1147 "must have a BranchOnCond");
1148 // Assume that `TripCount % VectorStep ` is equally distributed.
1149 unsigned VectorStep = Plan.getConcreteUF() * VF.getKnownMinValue();
1150 if (VF.isScalable() && VScaleForTuning.has_value())
1151 VectorStep *= *VScaleForTuning;
1152 assert(VectorStep > 0 && "trip count should not be zero");
1153 MDBuilder MDB(Plan.getContext());
1154 MDNode *BranchWeights =
1155 MDB.createBranchWeights({1, VectorStep - 1}, /*IsExpected=*/false);
1156 MiddleTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
1157}
static SDValue Widen(SelectionDAG *CurDAG, SDValue N)
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
const AArch64InstrInfo MachineBasicBlock::iterator InsertPt
AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static const Function * getParent(const Value *V)
static std::pair< Value *, APInt > getMask(Value *WideMask, unsigned Factor, ElementCount LeafValueEC)
This file provides a LoopVectorizationPlanner class.
#define I(x, y, z)
Definition MD5.cpp:57
This file contains the declarations for metadata subclasses.
SmallVector< MachineOperand, 4 > Cond
static bool dominates(InstrPosIndexes &PosIndexes, const MachineInstr &A, const MachineInstr &B)
This file contains some templates that are useful if you are working with the STL at all.
This file implements dominator tree analysis for a single level of a VPlan's H-CFG.
This file contains the declarations of different VPlan-related auxiliary helpers.
static VPActiveLaneMaskPHIRecipe * addVPLaneMaskPhiAndUpdateExitBranch(VPlan &Plan)
static void expandVPDerivedIV(VPDerivedIVRecipe *R)
Expand a VPDerivedIVRecipe into executable recipes.
static void expandVPWidenIntOrFpInduction(VPWidenIntOrFpInductionRecipe *WidenIVR)
Expand a VPWidenIntOrFpInduction into executable recipes, for the initial value, phi and backedge val...
static void expandVPWidenPointerInduction(VPWidenPointerInductionRecipe *R)
Expand a VPWidenPointerInductionRecipe into executable recipes, for the initial value,...
This file provides utility VPlan to VPlan transformations.
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 APInt urem(const APInt &RHS) const
Unsigned remainder operation.
Definition APInt.cpp:1695
Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition ArrayRef.h:40
LLVM Basic Block Representation.
Definition BasicBlock.h:62
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
Definition BasicBlock.h:237
@ ICMP_ULT
unsigned less than
Definition InstrTypes.h:765
@ ICMP_ULE
unsigned less or equal
Definition InstrTypes.h:766
LLVM_ABI IntegerType * getIndexType(LLVMContext &C, unsigned AddressSpace) const
Returns the type of a GEP index in AddressSpace.
A debug info location.
Definition DebugLoc.h:126
static DebugLoc getCompilerGenerated()
Definition DebugLoc.h:154
static DebugLoc getUnknown()
Definition DebugLoc.h:153
bool dominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
dominates - Returns true iff A dominates B.
Utility class for floating point operations which can have information about relaxed accuracy require...
Definition Operator.h:202
FastMathFlags getFastMathFlags() const
Convenience function for getting all the fast-math flags.
Definition Operator.h:291
Convenience struct for specifying and reasoning about fast-math flags.
Definition FMF.h:23
A struct for saving information about induction variables.
static LLVM_ABI InductionDescriptor getCanonicalIntInduction(Type *Ty, ScalarEvolution &SE)
Returns the canonical integer induction for type Ty with start = 0 and step = 1.
@ IK_NoInduction
Not an induction variable.
@ IK_FpInduction
Floating point induction variable.
@ IK_PtrInduction
Pointer induction var. Step = C.
@ IK_IntInduction
Integer induction variable. Step = C.
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition Type.cpp:333
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:1081
unsigned getOpcode() const
Return the opcode for this Instruction or ConstantExpr.
Definition Operator.h:43
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
This class uses information about analyze scalars to rewrite expressions in canonical form.
LLVM_ABI Value * expandCodeFor(SCEVUse SH, Type *Ty, BasicBlock::iterator I)
Insert code to directly compute the specified SCEV expression into the program.
This class represents an analyzed expression in the program.
Type * getType() const
Return the LLVM type of this SCEV expression.
The main scalar evolution driver.
LLVM_ABI const SCEV * getUDivExpr(SCEVUse LHS, SCEVUse RHS)
Get a canonical unsigned division expression, or something simpler if possible.
LLVM_ABI const SCEV * getElementCount(Type *Ty, ElementCount EC, SCEVFlags Flags=SCEV::FlagNone)
LLVM_ABI const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
LLVM_ABI SCEVUse getMulExpr(SmallVectorImpl< SCEVUse > &Ops, SCEVFlagsPair Flags={}, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
TargetCostKind
The kind of cost model.
@ SK_Broadcast
Broadcast element 0 to all other elements.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition Type.h:46
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
Definition Type.h:354
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
Definition Type.h:370
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
Definition Type.cpp:291
bool isFloatingPointTy() const
Return true if this is one of the floating-point types.
Definition Type.h:186
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition Type.h:252
A recipe for generating the active lane mask for the vector loop that is used to predicate the vector...
Definition VPlan.h:4177
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 getFirstNonPhi()
Return the position of the first non-phi node recipe in the block.
Definition VPlan.cpp:224
VPRecipeBase * getTerminator()
If the block has multiple successors, return the branch recipe terminating the block.
Definition VPlan.cpp:604
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition VPlan.h:95
VPRegionBlock * getParent()
Definition VPlan.h:193
const VPBasicBlock * getExitingBasicBlock() const
Definition VPlan.cpp:194
const std::string & getName() const
Definition VPlan.h:184
const VPBasicBlock * getEntryBasicBlock() const
Definition VPlan.cpp:179
VPBlockBase * getSingleSuccessor() const
Definition VPlan.h:233
const VPBlocksTy & getSuccessors() const
Definition VPlan.h:217
static auto blocksAs(T &&Range)
Return an iterator range over Range with each block cast to BlockTy.
Definition VPlanUtils.h:464
static void connectBlocks(VPBlockBase *From, VPBlockBase *To, unsigned PredIdx=-1u, unsigned SuccIdx=-1u)
Connect VPBlockBases From and To bi-directionally.
Definition VPlanUtils.h:391
static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To)
Disconnect VPBlockBases From and To bi-directionally.
Definition VPlanUtils.h:409
static auto blocksOnly(T &&Range)
Return an iterator range over Range which only includes BlockTy blocks.
Definition VPlanUtils.h:457
VPInstruction * createNaryOp(unsigned Opcode, ArrayRef< VPValue * > Operands, Instruction *Inst=nullptr, const VPIRFlags &Flags={}, const VPIRMetadata &MD={}, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="", Type *ResultTy=nullptr, const VPIRAttributes &Attrs={})
Create an N-ary operation with Opcode, Operands and set Inst as its underlying Instruction.
VPInstruction * createSub(VPValue *LHS, VPValue *RHS, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="", VPRecipeWithIRFlags::WrapFlagsTy WrapFlags={false, false})
VPWidenPHIRecipe * createWidenPhi(ArrayRef< VPValue * > IncomingValues, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="")
A recipe for converting Current into Start + Current * Step.
Definition VPlan.h:4310
Template specialization of the standard LLVM dominator tree utility for VPBlockBases.
Recipe to expand a SCEV expression.
Definition VPlan.h:4134
VPValue * getStartValue()
Returns the start value of the phi, if one is set.
Definition VPlan.h:2512
Class to record and manage LLVM IR flags.
Definition VPlan.h:683
static LLVM_ABI_FOR_TEST VPIRFlags getDefaultFlags(unsigned Opcode, Type *ResultTy=nullptr)
Returns default flags for Opcode and scalar ResultTy for opcodes that support it, asserts otherwise.
void dropPoisonGeneratingFlags()
Drop all poison-generating flags.
Definition VPlan.h:878
static LLVM_ABI_FOR_TEST VPIRInstruction * create(Instruction &I)
Create a new VPIRPhi for \I , if it is a PHINode, otherwise create a VPIRInstruction.
This is a concrete Recipe that models a single VPlan-level instruction.
Definition VPlan.h:1322
@ Unpack
Extracts all lanes from its (non-scalable) vector operand.
Definition VPlan.h:1378
void addIncoming(VPValue *IncomingV)
Append IncomingV as an incoming value to the phi-like recipe.
Definition VPlan.h:1680
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
void insertBefore(VPRecipeBase *InsertPos)
Insert an unlinked recipe into a basic block immediately before the specified recipe.
Type * getScalarType() const
Returns the scalar type of this VPRecipeValue.
Definition VPlanValue.h:349
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition VPlan.h:4771
const VPBlockBase * getEntry() const
Definition VPlan.h:4815
VPRegionValue * getUsedHeaderMask() const
Return the header mask if it exists and is used, or null otherwise.
Definition VPlan.h:4911
VPInstruction * getOrCreateCanonicalIVIncrement()
Get the canonical IV increment instruction if it exists.
Definition VPlan.cpp:881
Type * getCanonicalIVType() const
Return the type of the canonical IV for loop regions.
Definition VPlan.h:4899
bool hasCanonicalIVNUW() const
Indicates if NUW is set for the canonical IV increment, for loop regions.
Definition VPlan.h:4935
VPRegionValue * getCanonicalIV()
Return the canonical induction variable of the region, null for replicating regions.
Definition VPlan.h:4891
VPReplicateRecipe replicates a given instruction producing multiple scalar copies of the original sca...
Definition VPlan.h:3488
Lightweight SCEV-to-VPlan expander.
Definition VPlanUtils.h:285
VPValue * expand(const SCEV *S)
Expand S into recipes and live-ins using the builder.
A recipe for handling phi nodes of integer and floating-point inductions, producing their scalar valu...
Definition VPlan.h:4371
A symbolic live-in VPValue, used for values like vector trip count, VF, and VFxUF.
Definition VPlanValue.h:212
bool isMaterialized() const
Returns true if this value has been materialized.
Definition VPlanValue.h:230
This class augments VPValue with operands which provide the inverse def-use edges from VPValue's user...
Definition VPlanValue.h:396
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
Value * getLiveInIRValue() const
Return the underlying IR value for a VPIRValue.
Definition VPlan.cpp:132
VPRecipeBase * getDefiningRecipe()
Returns the recipe defining this VPValue or nullptr if it is not defined by a recipe,...
Definition VPlan.cpp:119
Value * getUnderlyingValue() const
Return the underlying Value attached to this VPValue.
Definition VPlanValue.h:75
void replaceUsesWithIf(VPValue *New, llvm::function_ref< bool(VPUser *U)> ShouldReplace)
Go through the uses list for this VPValue and make each use point to New if the callback ShouldReplac...
Definition VPlan.cpp:1476
bool user_empty() const
Definition VPlanValue.h:161
void setUnderlyingValue(Value *Val)
Definition VPlanValue.h:204
void replaceAllUsesWith(VPValue *New)
Definition VPlan.cpp:1470
A Recipe for widening the canonical induction variable of the vector loop.
Definition VPlan.h:4253
VPValue * getStepValue()
Returns the step value of the induction.
Definition VPlan.h:2590
const InductionDescriptor & getInductionDescriptor() const
Returns the induction descriptor for the recipe.
Definition VPlan.h:2607
A recipe for handling phi nodes of integer and floating-point inductions, producing their vector valu...
Definition VPlan.h:2636
VPValue * getSplatVFValue() const
If the recipe has been unrolled, return the VPValue for the induction increment, otherwise return nul...
Definition VPlan.h:2678
VPValue * getLastUnrolledPartOperand()
Returns the VPValue representing the value of this induction at the last unrolled part,...
Definition VPlan.h:2707
A recipe for widening vector intrinsics.
Definition VPlan.h:1944
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition VPlan.h:4958
bool hasVF(ElementCount VF) const
Definition VPlan.h:5181
const DataLayout & getDataLayout() const
Definition VPlan.h:5159
LLVMContext & getContext() const
Definition VPlan.h:5155
VPBasicBlock * getEntry()
Definition VPlan.h:5050
bool hasScalableVF() const
Definition VPlan.h:5182
VPValue * getTripCount() const
The trip count of the original loop.
Definition VPlan.h:5122
VPSymbolicValue & getVFxUF()
Returns VF * UF of the vector loop region.
Definition VPlan.h:5153
auto getLiveIns() const
Return the list of live-in VPValues available in the VPlan.
Definition VPlan.h:5291
bool hasUF(unsigned UF) const
Definition VPlan.h:5206
VPIRValue * getPoison(Type *Ty)
Return a VPIRValue wrapping a poison value of type Ty.
Definition VPlan.h:5282
VPSymbolicValue & getVectorTripCount()
The vector trip count.
Definition VPlan.h:5143
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
unsigned getConcreteUF() const
Returns the concrete UF of the plan, after unrolling.
Definition VPlan.h:5209
void resetTripCount(VPValue *NewTripCount)
Resets the trip count for the VPlan.
Definition VPlan.h:5136
VPBasicBlock * getMiddleBlock()
Returns the 'middle' block of the plan, that is the block that selects whether to execute the scalar ...
Definition VPlan.h:5092
VPBasicBlock * createVPBasicBlock(const Twine &Name, VPRecipeBase *Recipe=nullptr)
Create a new VPBasicBlock with Name and containing Recipe if present.
Definition VPlan.h:5314
VPBasicBlock * getVectorPreheader() const
Returns the preheader of the vector loop region, if one exists, or null otherwise.
Definition VPlan.h:5055
bool hasScalarVFOnly() const
Definition VPlan.h:5199
VPBasicBlock * getScalarPreheader() const
Return the VPBasicBlock for the preheader of the scalar loop.
Definition VPlan.h:5106
bool hasTailFolded() const
Returns true if the vector loop region is tail-folded.
Definition VPlan.h:5071
VPSymbolicValue & getVF()
Returns the VF of the vector loop region.
Definition VPlan.h:5146
bool hasScalarTail() const
Returns true if the scalar tail may execute after the vector loop, i.e.
Definition VPlan.h:5375
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
LLVM Value Representation.
Definition Value.h:75
iterator_range< user_iterator > users()
Definition Value.h:428
static LLVM_ABI VectorType * get(Type *ElementType, ElementCount EC)
This static method is the primary way to construct an VectorType.
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
const ParentTy * getParent() const
Definition ilist_node.h:34
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
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.
SpecificCmpClass_match< LHS, RHS, ICmpInst > m_SpecificICmp(CmpPredicate MatchPred, const LHS &L, const RHS &R)
RecipeTy * findSingleUser(VPValue *V, const MatchT &P)
Return the sole user of V matching pattern P, casting it to RecipeTy, or nullptr.
VPInstruction_match< VPInstruction::BranchOnTwoConds > m_BranchOnTwoConds()
canonical_widen_iv_match m_CanonicalWidenIV()
VPInstruction_match< VPInstruction::BranchOnCount > m_BranchOnCount()
auto m_VPValue()
Match an arbitrary VPValue and ignore it.
match_bind< VPInstruction > m_VPInstruction(VPInstruction *&V)
Match a VPInstruction, capturing if we match.
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 onlyFirstLaneUsed(const VPValue *Def)
Returns true if only the first lane of Def is used by all users.
VPValue * findIncomingAliasMask(const VPlan &Plan)
Finds the incoming alias-mask within the vector preheader.
VPScalarIVStepsRecipe * createScalarIVSteps(VPlan &Plan, InductionDescriptor::InductionKind Kind, Instruction::BinaryOps InductionOpcode, FPMathOperator *FPBinOp, Type *ResultTy, VPValue *StartV, VPValue *Step, DebugLoc DL, VPBuilder &Builder, const VPIRFlags::WrapFlagsTy &Flags={})
Create a scalar-iv-steps recipe over Plan's canonical IV for an induction of Kind with InductionOpcod...
bool onlyScalarValuesUsed(const VPValue *Def)
Returns true if only scalar values of Def are used by all users.
VPValue * scalarizeVPWidenPointerInduction(VPWidenPointerInductionRecipe *PtrIV, VPlan &Plan, VPBuilder &Builder)
Scalarize a VPWidenPointerInductionRecipe by replacing it with a PtrAdd (IndStart,...
This is an optimization pass for GlobalISel generic memory operations.
@ Offset
Definition DWP.cpp:577
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
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition STLExtras.h:2224
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 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
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1769
SmallVector< VPRegisterUsage, 8 > calculateRegisterUsageForPlan(VPlan &Plan, ArrayRef< ElementCount > VFs, const TargetTransformInfo &TTI)
Estimate the register usage for Plan and vectorization factors in VFs by calculating the highest numb...
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
auto drop_end(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the last N elements excluded.
Definition STLExtras.h:323
TargetTransformInfo TTI
@ Mul
Product of integers.
@ FMul
Product of floats.
@ Add
Sum of integers.
DWARFExpression::Operation Op
auto make_second_range(ContainerTy &&c)
Given a container of pairs, return a range over the second elements.
Definition STLExtras.h:1425
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
Definition STLExtras.h:2035
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Next
Definition InstrProf.h:147
constexpr detail::IsaCheckPredicate< Types... > IsaPred
Function object wrapper for the llvm::isa type check.
Definition Casting.h:866
A struct that represents some properties of the register usage of a loop.
SmallMapVector< unsigned, unsigned, 4 > MaxLocalUsers
Holds the maximum number of concurrent live intervals in the loop.
InstructionCost spillCost(const TargetTransformInfo &TTI, TargetTransformInfo::TargetCostKind CostKind, unsigned OverrideMaxNumRegs=0) const
Calculate the estimated cost of any spills due to using more registers than the number available for ...
static void expandSCEVsToVPInstructions(VPlan &Plan, ScalarEvolution &SE)
Expand VPExpandSCEVRecipes in Plan's entry block to VPInstructions.
static void materializeBroadcasts(VPlan &Plan)
Add explicit broadcasts for live-ins and VPValues defined in Plan's entry block if they are used as v...
static void materializeFactors(VPlan &Plan, VPBasicBlock *VectorPH, ElementCount VF)
Materialize UF, VF and VFxUF to be computed explicitly using VPInstructions.
static void materializeHeaderMask(VPlan &Plan, bool UseActiveLaneMask, bool UseActiveLaneMaskForControlFlow)
Materialize the abstract header mask of the loop region into concrete recipes: an active-lane-mask if...
static void addBranchWeightToMiddleTerminator(VPlan &Plan, ElementCount VF, std::optional< unsigned > VScaleForTuning)
Add branch weight metadata, if the Plan's middle block is terminated by a BranchOnCond recipe.
static void materializeAliasMaskCheckBlock(VPlan &Plan, ArrayRef< PointerDiffInfo > DiffChecks, ScalarEvolution &SE, bool HasBranchWeights)
Materializes the alias mask within a check block before the loop.
static DenseMap< const SCEV *, Value * > expandSCEVs(VPlan &Plan, ScalarEvolution &SE)
Expand remaining VPExpandSCEVRecipes in Plan's entry block using SCEVExpander.
static void convertToConcreteRecipes(VPlan &Plan)
Lower abstract recipes to concrete ones, that can be codegen'd.
static VPValue * materializeAliasMask(VPlan &Plan, VPBasicBlock *AliasCheckVPBB, ArrayRef< PointerDiffInfo > DiffChecks, ScalarEvolution &SE)
Materializes the alias mask within AliasCheckVPBB, which must be dominated by the SCEV checks,...
static void expandBranchOnTwoConds(VPlan &Plan)
Expand BranchOnTwoConds instructions into explicit CFG with BranchOnCond instructions.
static void materializeVectorTripCount(VPlan &Plan, VPBasicBlock *VectorPHVPBB, bool TailByMasking, bool RequiresScalarEpilogue, VPValue *Step, std::optional< uint64_t > MaxRuntimeStep=std::nullopt)
Materialize vector trip count computations to a set of VPInstructions.
static void materializeConstantVectorTripCount(VPlan &Plan, ElementCount BestVF, unsigned BestUF, PredicatedScalarEvolution &PSE)
static void replaceWideCanonicalIVWithWideIV(VPlan &Plan, ScalarEvolution &SE, const TargetTransformInfo &TTI, TargetTransformInfo::TargetCostKind CostKind, ElementCount VF, unsigned UF)
Replace a VPWidenCanonicalIVRecipe if it is present in Plan, with a VPWidenIntOrFpInductionRecipe,...
static void materializeUnpacks(VPlan &Plan)
Add explicit Unpack recipes to extract scalars from vectors as needed.
static void attachVPCheckBlock(VPlan &Plan, VPValue *Cond, VPBasicBlock *CheckBlock, bool AddBranchWeights)
Connect CheckBlock to Plan, branching on Cond.
static void dissolveLoopRegions(VPlan &Plan)
Replace loop regions with explicit CFG.