LLVM 24.0.0git
VPlanRecipes.cpp
Go to the documentation of this file.
1//===- VPlanRecipes.cpp - Implementations for VPlan recipes ---------------===//
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 contains implementations for different VPlan recipes.
11///
12//===----------------------------------------------------------------------===//
13
15#include "VPlan.h"
16#include "VPlanHelpers.h"
17#include "VPlanPatternMatch.h"
18#include "VPlanUtils.h"
19#include "VectorizeOptions.h"
20#include "llvm/ADT/APFloat.h"
21#include "llvm/ADT/STLExtras.h"
24#include "llvm/ADT/Twine.h"
31#include "llvm/IR/BasicBlock.h"
32#include "llvm/IR/IRBuilder.h"
33#include "llvm/IR/Instruction.h"
35#include "llvm/IR/Intrinsics.h"
37#include "llvm/IR/Type.h"
38#include "llvm/IR/Value.h"
40#include "llvm/Support/Debug.h"
44#include <cassert>
45
46using namespace llvm;
47using namespace llvm::VPlanPatternMatch;
48
49#define LV_NAME "loop-vectorize"
50#define DEBUG_TYPE LV_NAME
51
52/// For call VPInstruction operands, return the operand index of the called
53/// function. The function is either the last operand (for unmasked calls) or
54/// the second-to-last operand (for masked calls).
56 unsigned NumOps = Operands.size();
57 auto *LastOp = dyn_cast<VPIRValue>(Operands[NumOps - 1]);
58 if (LastOp && isa<Function>(LastOp->getValue()))
59 return NumOps - 1;
61 "expected function operand");
62 return NumOps - 2;
63}
64
65/// For call VPInstruction operands, return the called function.
70
71/// Return the function attributes of the callee of \p VPI, which must be a
72/// call or intrinsic VPInstruction.
79
81 switch (getVPRecipeID()) {
82 case VPExpressionSC:
83 return cast<VPExpressionRecipe>(this)->mayReadOrWriteMemory();
84 case VPInstructionSC: {
85 auto *VPI = cast<VPInstruction>(this);
86 // Loads read from memory but don't write to memory.
87 if (VPI->getOpcode() == Instruction::Load ||
88 VPI->getOpcode() == VPInstruction::WideVectorLoad)
89 return false;
90 return VPI->opcodeMayReadOrWriteFromMemory();
91 }
92 case VPInterleaveEVLSC:
93 case VPInterleaveSC:
94 return cast<VPInterleaveBase>(this)->getNumStoreOperands() > 0;
95 case VPWidenStoreEVLSC:
96 case VPWidenStoreSC:
97 return true;
98 case VPReplicateSC:
99 return cast<Instruction>(getVPSingleValue()->getUnderlyingValue())
100 ->mayWriteToMemory();
101 case VPWidenCallSC:
102 return !cast<VPWidenCallRecipe>(this)
103 ->getCalledScalarFunction()
104 ->onlyReadsMemory();
105 case VPWidenMemIntrinsicSC:
106 case VPWidenIntrinsicSC:
107 return cast<VPWidenIntrinsicRecipe>(this)->mayWriteToMemory();
108 case VPActiveLaneMaskPHISC:
109 case VPCurrentIterationPHISC:
110 case VPBranchOnMaskSC:
111 case VPDerivedIVSC:
112 case VPFirstOrderRecurrencePHISC:
113 case VPReductionPHISC:
114 case VPScalarIVStepsSC:
115 case VPPredInstPHISC:
116 case VPExpandSCEVSC:
117 case VPConditionalInductionPHISC:
118 return false;
119 case VPBlendSC:
120 case VPReductionEVLSC:
121 case VPReductionSC:
122 case VPVectorPointerSC:
123 case VPVectorEndPointerSC:
124 case VPWidenCanonicalIVSC:
125 case VPWidenCastSC:
126 case VPWidenGEPSC:
127 case VPWidenIntOrFpInductionSC:
128 case VPWidenLoadEVLSC:
129 case VPWidenLoadSC:
130 case VPWidenPHISC:
131 case VPWidenPointerInductionSC:
132 case VPWidenSC: {
133 const Instruction *I =
134 dyn_cast_or_null<Instruction>(getVPSingleValue()->getUnderlyingValue());
135 (void)I;
136 assert((!I || !I->mayWriteToMemory()) &&
137 "underlying instruction may write to memory");
138 return false;
139 }
140 default:
141 return true;
142 }
143}
144
146 switch (getVPRecipeID()) {
147 case VPExpressionSC:
148 return cast<VPExpressionRecipe>(this)->mayReadOrWriteMemory();
149 case VPInstructionSC: {
150 auto *VPI = cast<VPInstruction>(this);
151 // Stores write to memory but don't read from memory.
152 if (VPI->getOpcode() == VPInstruction::WideVectorStore)
153 return false;
154 return VPI->opcodeMayReadOrWriteFromMemory();
155 }
156 case VPWidenLoadEVLSC:
157 case VPWidenLoadSC:
158 return true;
159 case VPReplicateSC:
160 return cast<Instruction>(getVPSingleValue()->getUnderlyingValue())
161 ->mayReadFromMemory();
162 case VPWidenCallSC:
163 return !cast<VPWidenCallRecipe>(this)
164 ->getCalledScalarFunction()
165 ->onlyWritesMemory();
166 case VPWidenMemIntrinsicSC:
167 case VPWidenIntrinsicSC:
168 return cast<VPWidenIntrinsicRecipe>(this)->mayReadFromMemory();
169 case VPActiveLaneMaskPHISC:
170 case VPBranchOnMaskSC:
171 case VPDerivedIVSC:
172 case VPCurrentIterationPHISC:
173 case VPFirstOrderRecurrencePHISC:
174 case VPReductionPHISC:
175 case VPPredInstPHISC:
176 case VPScalarIVStepsSC:
177 case VPWidenStoreEVLSC:
178 case VPWidenStoreSC:
179 case VPExpandSCEVSC:
180 case VPConditionalInductionPHISC:
181 return false;
182 case VPBlendSC:
183 case VPReductionEVLSC:
184 case VPReductionSC:
185 case VPVectorPointerSC:
186 case VPVectorEndPointerSC:
187 case VPWidenCanonicalIVSC:
188 case VPWidenCastSC:
189 case VPWidenGEPSC:
190 case VPWidenIntOrFpInductionSC:
191 case VPWidenPHISC:
192 case VPWidenPointerInductionSC:
193 case VPWidenSC: {
194 const Instruction *I =
195 dyn_cast_or_null<Instruction>(getVPSingleValue()->getUnderlyingValue());
196 (void)I;
197 assert((!I || !I->mayReadFromMemory()) &&
198 "underlying instruction may read from memory");
199 return false;
200 }
201 default:
202 // FIXME: Return false if the recipe represents an interleaved store.
203 return true;
204 }
205}
206
208 switch (getVPRecipeID()) {
209 case VPExpressionSC:
210 return cast<VPExpressionRecipe>(this)->mayHaveSideEffects();
211 case VPActiveLaneMaskPHISC:
212 case VPDerivedIVSC:
213 case VPCurrentIterationPHISC:
214 case VPFirstOrderRecurrencePHISC:
215 case VPReductionPHISC:
216 case VPPredInstPHISC:
217 case VPVectorEndPointerSC:
218 case VPExpandSCEVSC:
219 case VPConditionalInductionPHISC:
220 return false;
221 case VPInstructionSC: {
222 auto *VPI = cast<VPInstruction>(this);
223 if (VPI->getOpcode() == Instruction::Call ||
224 VPI->getOpcode() == VPInstruction::Intrinsic) {
225 AttributeSet CalleeFnAttrs = getCalleeFnAttrs(*VPI);
226 return mayWriteToMemory() ||
227 !VPI->hasFnAttr(Attribute::NoUnwind, CalleeFnAttrs) ||
228 !VPI->hasFnAttr(Attribute::WillReturn, CalleeFnAttrs);
229 }
230 return mayWriteToMemory() ||
231 VPI->getOpcode() == VPInstruction::BranchOnCount ||
232 VPI->getOpcode() == VPInstruction::BranchOnCond ||
233 VPI->getOpcode() == VPInstruction::BranchOnTwoConds;
234 }
235 case VPWidenCallSC: {
236 Function *Fn = cast<VPWidenCallRecipe>(this)->getCalledScalarFunction();
237 return mayWriteToMemory() || !Fn->doesNotThrow() || !Fn->willReturn();
238 }
239 case VPWidenMemIntrinsicSC:
240 case VPWidenIntrinsicSC:
241 return cast<VPWidenIntrinsicRecipe>(this)->mayHaveSideEffects();
242 case VPBlendSC:
243 case VPReductionEVLSC:
244 case VPReductionSC:
245 case VPScalarIVStepsSC:
246 case VPVectorPointerSC:
247 case VPWidenCanonicalIVSC:
248 case VPWidenCastSC:
249 case VPWidenGEPSC:
250 case VPWidenIntOrFpInductionSC:
251 case VPWidenPHISC:
252 case VPWidenPointerInductionSC:
253 case VPWidenSC: {
254 const Instruction *I =
255 dyn_cast_or_null<Instruction>(getVPSingleValue()->getUnderlyingValue());
256 (void)I;
257 assert((!I || !I->mayHaveSideEffects()) &&
258 "underlying instruction has side-effects");
259 return false;
260 }
261 case VPInterleaveEVLSC:
262 case VPInterleaveSC:
263 return mayWriteToMemory();
264 case VPWidenLoadEVLSC:
265 case VPWidenLoadSC:
266 case VPWidenStoreEVLSC:
267 case VPWidenStoreSC:
268 assert(
269 cast<VPWidenMemoryRecipe>(this)->getIngredient().mayHaveSideEffects() ==
271 "mayHaveSideffects result for ingredient differs from this "
272 "implementation");
273 return mayWriteToMemory();
274 case VPReplicateSC: {
275 auto *R = cast<VPReplicateRecipe>(this);
276 return R->getUnderlyingInstr()->mayHaveSideEffects();
277 }
278 default:
279 return true;
280 }
281}
282
284 switch (getVPRecipeID()) {
285 default:
286 return false;
287 case VPInstructionSC: {
288 unsigned Opcode = cast<VPInstruction>(this)->getOpcode();
289 if (Instruction::isCast(Opcode))
290 return true;
291
292 switch (Opcode) {
293 default:
294 return false;
295 case Instruction::Add:
296 case Instruction::Sub:
297 case Instruction::Mul:
298 case Instruction::GetElementPtr:
299 return true;
300 case Instruction::Call:
303 .hasAttribute(Attribute::Speculatable);
304 }
305 }
306 }
307}
308
310 insertBefore(InsertPos->getIterator());
311}
312
314 assert(!getParent() && "Recipe already in some VPBasicBlock");
315 assert(I.getNodeParent() && "Insertion position not in any VPBasicBlock");
316 I.getNodeParent()->insert(this, I);
317}
318
320 assert(InsertPos->getParent() &&
321 "Insertion position not in any VPBasicBlock");
322 insertBefore(std::next(InsertPos->getIterator()));
323}
324
326 assert(getParent() && "Recipe not in any VPBasicBlock");
327 getParent()->getRecipeList().remove(getIterator());
328 setParent(nullptr);
329}
330
332 assert(getParent() && "Recipe not in any VPBasicBlock");
333 return getParent()->getRecipeList().erase(getIterator());
334}
335
338 insertAfter(InsertPos);
339}
340
345
347 // Get the underlying instruction for the recipe, if there is one. It is used
348 // to
349 // * decide if cost computation should be skipped for this recipe,
350 // * apply forced target instruction cost.
351 Instruction *UI = nullptr;
352 if (auto *S = dyn_cast<VPSingleDefRecipe>(this))
353 UI = dyn_cast_or_null<Instruction>(S->getUnderlyingValue());
354 else if (auto *IG = dyn_cast<VPInterleaveBase>(this))
355 UI = IG->getInsertPos();
356 else if (auto *WidenMem = dyn_cast<VPWidenMemoryRecipe>(this))
357 UI = &WidenMem->getIngredient();
358
359 // Replicating per lane is invalid for scalable VFs. Don't skip such recipes
360 // even if the legacy cost model ignores UI, e.g. as an address of an
361 // interleave group member, assuming the group is widened.
362 auto *RepR = dyn_cast<VPReplicateRecipe>(this);
363 bool ReplicatesScalable =
364 RepR && VF.isScalable() && RepR->doesGeneratePerAllLanes();
365 InstructionCost RecipeCost;
366 if (UI && Ctx.skipCostComputation(UI, VF.isVector()) && !ReplicatesScalable) {
367 RecipeCost = 0;
368 } else {
369 RecipeCost = computeCost(VF, Ctx);
370 if (Ctx.Opts.force_target_instruction_cost && RecipeCost.isValid()) {
371 // VPDerivedIVRecipe, VPScalarIVStepsRecipe and VPBranchOnMaskRecipe never
372 // have underlying instructions.
373 if (UI ||
375 this))
376 RecipeCost = InstructionCost(*Ctx.Opts.force_target_instruction_cost);
377 else
378 RecipeCost = InstructionCost(0);
379 }
380 }
381
382 LLVM_DEBUG({
383 dbgs() << "Cost of " << RecipeCost << " for VF " << VF << ": ";
384 if (VPSlotTracker *SlotTracker = Ctx.getSlotTracker()) {
385 print(dbgs(), "", *SlotTracker);
386 dbgs() << "\n";
387 } else {
388 dump();
389 }
390 });
391 return RecipeCost;
392}
393
395 VPCostContext &Ctx) const {
396 llvm_unreachable("subclasses should implement computeCost");
397}
398
400 return (getVPRecipeID() >= VPFirstPHISC && getVPRecipeID() <= VPLastPHISC) ||
402}
403
405 assert(OpType == Other.OpType && "OpType must match");
406 switch (OpType) {
407 case OperationType::OverflowingBinOp:
408 WrapFlags.HasNUW &= Other.WrapFlags.HasNUW;
409 WrapFlags.HasNSW &= Other.WrapFlags.HasNSW;
410 break;
411 case OperationType::Trunc:
412 TruncFlags.HasNUW &= Other.TruncFlags.HasNUW;
413 TruncFlags.HasNSW &= Other.TruncFlags.HasNSW;
414 break;
415 case OperationType::DisjointOp:
416 DisjointFlags.IsDisjoint &= Other.DisjointFlags.IsDisjoint;
417 break;
418 case OperationType::PossiblyExactOp:
419 ExactFlags.IsExact &= Other.ExactFlags.IsExact;
420 break;
421 case OperationType::GEPOp:
422 GEPFlagsStorage &= Other.GEPFlagsStorage;
423 break;
424 case OperationType::FPMathOp:
425 case OperationType::FCmp:
426 assert((OpType != OperationType::FCmp ||
427 FCmpFlags.CmpPredStorage == Other.FCmpFlags.CmpPredStorage) &&
428 "Cannot drop CmpPredicate");
429 getFMFsRef() = getFastMathFlagsOrNone() & Other.getFastMathFlagsOrNone();
430 break;
431 case OperationType::NonNegOp:
432 NonNegFlags.NonNeg &= Other.NonNegFlags.NonNeg;
433 break;
434 case OperationType::Cmp:
435 assert(CmpPredStorage == Other.CmpPredStorage &&
436 "Cannot drop CmpPredicate");
437 break;
438 case OperationType::ReductionOp:
439 assert(ReductionFlags.Kind == Other.ReductionFlags.Kind &&
440 "Cannot change RecurKind");
441 assert(ReductionFlags.IsOrdered == Other.ReductionFlags.IsOrdered &&
442 "Cannot change IsOrdered");
443 assert(ReductionFlags.IsInLoop == Other.ReductionFlags.IsInLoop &&
444 "Cannot change IsInLoop");
445 getFMFsRef() = getFastMathFlagsOrNone() & Other.getFastMathFlagsOrNone();
446 break;
447 case OperationType::Other:
448 break;
449 }
450}
451
453 if (!hasFastMathFlags())
454 return {};
455 const FastMathFlagsTy &F = getFMFsRef();
456 FastMathFlags Res;
457 Res.setAllowReassoc(F.AllowReassoc);
458 Res.setNoNaNs(F.NoNaNs);
459 Res.setNoInfs(F.NoInfs);
460 Res.setNoSignedZeros(F.NoSignedZeros);
461 Res.setAllowReciprocal(F.AllowReciprocal);
462 Res.setAllowContract(F.AllowContract);
463 Res.setApproxFunc(F.ApproxFunc);
464 return Res;
465}
466
467#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
469
470void VPRecipeBase::print(raw_ostream &O, const Twine &Indent,
471 VPSlotTracker &SlotTracker) const {
472 printRecipe(O, Indent, SlotTracker);
473 if (auto DL = getDebugLoc()) {
474 O << ", !dbg ";
475 DL.print(O);
476 }
477
478 if (auto *Metadata = dyn_cast<VPIRMetadata>(this))
480}
481#endif
482
483VPExpandSCEVRecipe::VPExpandSCEVRecipe(const SCEV *Expr, bool ExpandInIR)
484 : VPSingleDefRecipe(VPRecipeBase::VPExpandSCEVSC, {}, Expr->getType()),
485 Expr(Expr), ExpandInIR(ExpandInIR) {}
486
492
495 assert(!Operands.empty() &&
496 "zero-operand VPInstruction opcodes must pass explicit ResultTy");
497 // Assert operand \p Idx (if present and typed) has type \p ExpectedTy.
498 [[maybe_unused]] auto AssertOperandType = [&Operands](unsigned Idx,
499 Type *ExpectedTy) {
500 if (!ExpectedTy || Operands.size() <= Idx)
501 return;
502 [[maybe_unused]] Type *OpTy = Operands[Idx]->getScalarType();
503 assert((!OpTy || OpTy == ExpectedTy) &&
504 "different types inferred for different operands");
505 };
506
507 Type *Op0Ty = Operands[0]->getScalarType();
508 LLVMContext &Ctx = Op0Ty->getContext();
509 switch (Opcode) {
511 assert(Op0Ty->isIntegerTy(1) && "expected bool condition");
512 return Type::getVoidTy(Ctx);
514 assert(Op0Ty->isIntegerTy(1) && "expected bool condition");
515 AssertOperandType(1, IntegerType::get(Ctx, 1));
516 return Type::getVoidTy(Ctx);
518 assert(Op0Ty->isIntegerTy() && "expected integer operand");
519 AssertOperandType(1, Op0Ty);
520 return Type::getVoidTy(Ctx);
522 assert(Op0Ty->isIntegerTy() && "expected integer operand");
523 for (unsigned Idx = 1; Idx != Operands.size(); ++Idx)
524 AssertOperandType(Idx, Op0Ty);
525 return Op0Ty;
526 case Instruction::Switch:
527 for (unsigned Idx = 1; Idx != Operands.size(); ++Idx)
528 AssertOperandType(Idx, Op0Ty);
529 return Type::getVoidTy(Ctx);
531 case Instruction::Store:
532 return Type::getVoidTy(Ctx);
533 case Instruction::ICmp:
534 assert(Op0Ty->isIntOrPtrTy() && "expected integer or pointer operand");
535 AssertOperandType(1, Op0Ty);
536 return IntegerType::get(Ctx, 1);
537 case Instruction::FCmp:
538 assert(Op0Ty->isFloatingPointTy() && "expected floating-point operand");
539 AssertOperandType(1, Op0Ty);
540 return IntegerType::get(Ctx, 1);
543 assert(Op0Ty->isIntegerTy() && "expected integer operand");
544 AssertOperandType(1, Op0Ty);
545 return IntegerType::get(Ctx, 1);
547 assert(Op0Ty->isIntegerTy(1) && "expected bool operand");
548 return IntegerType::get(Ctx, 1);
551 assert(Op0Ty->isIntegerTy(1) && "expected bool operand");
552 AssertOperandType(1, Op0Ty);
553 return IntegerType::get(Ctx, 1);
555 assert(Op0Ty->isIntegerTy(1) && "expected bool operand");
556 for (unsigned Idx = 1; Idx != Operands.size(); ++Idx)
557 AssertOperandType(Idx, Op0Ty);
558 return IntegerType::get(Ctx, 1);
560 assert(Op0Ty->isIntegerTy() && "expected integer operand");
561 return IntegerType::get(Ctx, 32);
562 case Instruction::Select: {
563 assert((!Op0Ty || Op0Ty->isIntegerTy(1)) &&
564 "select condition must be bool");
565 Type *Op1Ty = Operands[1]->getScalarType();
566 AssertOperandType(2, Op1Ty);
567 return Op1Ty;
568 }
569 case Instruction::InsertElement:
570 // The inserted scalar (operand 1) must match the vector element type;
571 // operand 2 must be an integer.
572 AssertOperandType(1, Op0Ty);
573 assert(Operands[2]->getScalarType()->isIntegerTy() &&
574 "expected integer operand");
575 return Op0Ty;
577 // The start value and the identity value (operands 0 and 1) fill the same
578 // vector and must match in type; operand 2 is the scaling factor.
579 AssertOperandType(1, Op0Ty);
580 return Op0Ty;
582 assert(Operands.size() >= 2 && "ExtractLane requires a lane operand and "
583 "at least one source vector operand");
584 // Operand 0 is the lane index, used for integer arithmetic.
585 assert(Op0Ty->isIntegerTy() && "expected integer operand");
586 Type *Op1Ty = Operands[1]->getScalarType();
587 for (unsigned Idx = 2; Idx != Operands.size(); ++Idx)
588 AssertOperandType(Idx, Op1Ty);
589 return Op1Ty;
590 }
593 assert(Operands[0]->getScalarType()->isPointerTy() &&
594 "expected pointer operand");
595 assert(Operands[1]->getScalarType()->isIntegerTy() &&
596 "expected integer operand");
597 return Op0Ty;
598 case Instruction::ExtractValue:
606 case Instruction::Load:
607 case Instruction::Alloca:
608 llvm_unreachable("type must be passed explicitly");
609 case Instruction::Call:
613 "BuildVector operands must be valid vector elements");
614 break;
615 default:
616 if (Instruction::isCast(Opcode))
617 llvm_unreachable("type must be passed explicitly");
618 break;
619 }
620
621 // Opcodes that require all operands to share the same scalar type as the
622 // result.
623 bool AllOperandsSameType =
624 Instruction::isBinaryOp(Opcode) ||
628 Opcode);
629 if (AllOperandsSameType)
630 for (unsigned Idx = 1; Idx != Operands.size(); ++Idx)
631 AssertOperandType(Idx, Op0Ty);
632
633 return Op0Ty;
634}
635
638 unsigned Opcode = I->getOpcode();
639 if (Instruction::isCast(Opcode) ||
640 is_contained(ArrayRef<unsigned>({Instruction::Load, Instruction::Alloca}),
641 Opcode))
642 return I->getType();
644}
645
647 const VPIRFlags &Flags, const VPIRMetadata &MD,
648 DebugLoc DL, const Twine &Name, Type *ResultTy,
649 const VPIRAttributes &Attrs)
651 VPRecipeBase::VPInstructionSC, Operands,
652 ResultTy ? ResultTy
654 Flags, DL),
655 VPIRMetadata(MD), VPIRAttributes(Attrs), Opcode(Opcode),
656 Name(Name.str()) {
658 "Set flags not supported for the provided opcode");
660 "Opcode requires specific flags to be set");
664 "number of operands does not match opcode");
665}
666
668 if (Instruction::isUnaryOp(Opcode) || Instruction::isCast(Opcode))
669 return 1;
670
671 if (Instruction::isBinaryOp(Opcode))
672 return 2;
673
674 switch (Opcode) {
677 return 0;
678 case Instruction::Alloca:
679 case Instruction::Freeze:
680 case Instruction::Load:
693 return 1;
694 case Instruction::ICmp:
695 case Instruction::FCmp:
696 case Instruction::ExtractElement:
697 case Instruction::Store:
709 return 2;
710 case Instruction::InsertElement:
711 case Instruction::Select:
715 return 3;
717 return 4;
718 case Instruction::Call:
719 return getCalledFnOperandIndex(operands()) + 1;
720 case Instruction::GetElementPtr:
721 case Instruction::PHI:
722 case Instruction::Switch:
723 case Instruction::AtomicRMW:
724 case Instruction::AtomicCmpXchg:
725 case Instruction::ExtractValue:
726 case Instruction::Fence:
737 // Cannot determine the number of operands from the opcode.
738 return -1u;
739 }
740 llvm_unreachable("all cases should be handled above");
741}
742
744 return Opcode == VPInstruction::Unpack ||
746}
747
748bool VPInstruction::doesGenerateSingleScalar() const {
750 return true;
751 switch (Opcode) {
752 case Instruction::Freeze:
753 case Instruction::ICmp:
754 case Instruction::PHI:
755 case Instruction::Select:
764 return vputils::onlyFirstLaneUsed(this);
765 default:
767 }
768}
769
771 if (Kind == RecurKind::Sub)
772 return Instruction::Add;
773 if (Kind == RecurKind::FSub)
774 return Instruction::FAdd;
775 llvm_unreachable("RecurKind should be Sub/FSub.");
776}
777
778Value *VPInstruction::generate(VPTransformState &State,
779 bool GenerateSingleScalar) {
780 IRBuilderBase &Builder = State.Builder;
781
783 Value *A = State.get(getOperand(0), GenerateSingleScalar);
784 Value *B = State.get(getOperand(1), GenerateSingleScalar);
785 auto *Res =
786 Builder.CreateBinOp((Instruction::BinaryOps)getOpcode(), A, B, Name);
787 if (auto *I = dyn_cast<Instruction>(Res))
788 applyFlags(*I);
789 return Res;
790 }
792 Value *Op = State.get(getOperand(0), VPLane(0));
794 getScalarType());
795 if (auto *CastOp = dyn_cast<Instruction>(Res)) {
796 applyFlags(*CastOp);
797 applyMetadata(*CastOp);
798 }
799 return Res;
800 }
801
802 switch (getOpcode()) {
803 case VPInstruction::Not: {
804 Value *A = State.get(getOperand(0), GenerateSingleScalar);
805 return Builder.CreateNot(A, Name);
806 }
808 // TODO: Use IsSingleScalar to produce a scalar value.
809 Value *A = State.get(getOperand(0));
810 Value *B = State.get(getOperand(1));
811 return Builder.CreateLogicalAnd(A, B, Name);
812 }
814 // TODO: Use IsSingleScalar to produce a scalar value.
815 Value *A = State.get(getOperand(0));
816 Value *B = State.get(getOperand(1));
817 return Builder.CreateLogicalOr(A, B, Name);
818 }
819 case Instruction::ExtractElement: {
820 assert(GenerateSingleScalar &&
821 "Can only generate first lane for ExtractElement");
822 assert(State.VF.isVector() && "Only extract elements from vectors");
823 if (auto *Idx = dyn_cast<VPConstantInt>(getOperand(1)))
824 return State.get(getOperand(0), VPLane(Idx->getZExtValue()));
825 Value *Vec = State.get(getOperand(0));
826 Value *Idx = State.get(getOperand(1), /*NeedsSingleScalar=*/true);
827 return Builder.CreateExtractElement(Vec, Idx, Name);
828 }
829 case Instruction::InsertElement: {
830 assert(!GenerateSingleScalar &&
831 "Cannot generate scalar value for InsertElement");
832 assert(State.VF.isVector() && "Can only insert elements into vectors");
833 Value *Vec = State.get(getOperand(0), /*NeedsSingleScalar=*/false);
834 Value *Elt = State.get(getOperand(1), /*NeedsSingleScalar=*/true);
835 Value *Idx = State.get(getOperand(2), /*NeedsSingleScalar=*/true);
836 return Builder.CreateInsertElement(Vec, Elt, Idx, Name);
837 }
838 case Instruction::Freeze: {
839 Value *Op = State.get(getOperand(0), GenerateSingleScalar);
840 return Builder.CreateFreeze(Op, Name);
841 }
842 case Instruction::FCmp:
843 case Instruction::ICmp: {
844 Value *A = State.get(getOperand(0), GenerateSingleScalar);
845 Value *B = State.get(getOperand(1), GenerateSingleScalar);
846 return Builder.CreateCmp(getPredicate(), A, B, Name);
847 }
848 case Instruction::PHI: {
849 llvm_unreachable("should be handled by VPPhi::execute");
850 }
851 case Instruction::Select: {
852 Value *Cond =
853 State.get(getOperand(0), GenerateSingleScalar ||
855 Value *Op1 = State.get(getOperand(1), GenerateSingleScalar);
856 Value *Op2 = State.get(getOperand(2), GenerateSingleScalar);
857 Value *Sel =
858 Builder.CreateSelectFMF(Cond, Op1, Op2, getFastMathFlagsOrNone(), Name);
859 if (auto *I = dyn_cast<Instruction>(Sel))
861 return Sel;
862 }
865 // Can produce either a scalar value as a icmp of a phi, or a vector value,
866 // as a get.active.lane.mask intrinsic.
867 // Get first lane of vector induction variable.
868 Value *VIVElem0 = State.get(getOperand(0), VPLane(0));
869 // Get the original loop tripcount.
870 Value *ScalarTC = State.get(getOperand(1), VPLane(0));
871
872 uint64_t Multiplier =
874 ? cast<VPConstantInt>(getOperand(2))->getZExtValue()
875 : 1;
876
877 // If this part of the active lane mask is scalar, generate the CMP directly
878 // to avoid unnecessary extracts.
879 if (State.VF.isScalar() && Multiplier == 1)
880 return Builder.CreateCmp(CmpInst::Predicate::ICMP_ULT, VIVElem0, ScalarTC,
881 Name);
882
883 auto *PredTy = VectorType::get(Builder.getInt1Ty(), State.VF * Multiplier);
884 return Builder.CreateIntrinsic(Intrinsic::get_active_lane_mask,
885 {PredTy, ScalarTC->getType()},
886 {VIVElem0, ScalarTC}, nullptr, Name);
887 }
889 assert(GenerateSingleScalar &&
890 "Can only generate first lane for NumActiveLanes");
891 Value *Op = State.get(getOperand(0));
892 auto *VecTy = cast<VectorType>(Op->getType());
893 assert(VecTy->getScalarSizeInBits() == 1 &&
894 "NumActiveLanes only implemented for i1 vectors");
895
896 Type *Ty = getScalarType();
897 Value *ZExt = Builder.CreateCast(
898 Instruction::ZExt, Op, VectorType::get(Ty, VecTy->getElementCount()));
899 Value *NumActive =
900 Builder.CreateUnaryIntrinsic(Intrinsic::vector_reduce_add, ZExt);
901 return NumActive;
902 }
904 // Generate code to combine the previous and current values in vector v3.
905 //
906 // vector.ph:
907 // v_init = vector(..., ..., ..., a[-1])
908 // br vector.body
909 //
910 // vector.body
911 // i = phi [0, vector.ph], [i+4, vector.body]
912 // v1 = phi [v_init, vector.ph], [v2, vector.body]
913 // v2 = a[i, i+1, i+2, i+3];
914 // v3 = vector(v1(3), v2(0, 1, 2))
915
916 auto *V1 = State.get(getOperand(0));
917 if (!V1->getType()->isVectorTy())
918 return V1;
919 Value *V2 = State.get(getOperand(1));
920 return Builder.CreateVectorSpliceRight(V1, V2, 1, Name);
921 }
923 // TODO: Restructure this code with an explicit remainder loop, vsetvli can
924 // be outside of the main loop.
925 assert(GenerateSingleScalar &&
926 "Can only generate first lane for ExplicitVectorLength");
927 Value *AVL = State.get(getOperand(0), /*NeedsSingleScalar=*/true);
928 // Compute EVL
929 assert(AVL->getType()->isIntegerTy() &&
930 "Requested vector length should be an integer.");
931
932 assert(State.VF.isScalable() && "Expected scalable vector factor.");
933 Value *VFArg = Builder.getInt32(State.VF.getKnownMinValue());
934
935 Value *EVL = Builder.CreateIntrinsic(
936 Builder.getInt32Ty(), Intrinsic::experimental_get_vector_length,
937 {AVL, VFArg, Builder.getTrue()});
938 return EVL;
939 }
941 assert(GenerateSingleScalar &&
942 "Can only generate first lane for BranchOnCond");
943 Value *Cond = State.get(getOperand(0), VPLane(0));
944 // Replace the temporary unreachable terminator with a new conditional
945 // branch, hooking it up to backward destination for latch blocks now, and
946 // to forward destination(s) later when they are created.
947 // Second successor may be backwards - iff it is already in VPBB2IRBB.
948 VPBasicBlock *SecondVPSucc =
949 cast<VPBasicBlock>(getParent()->getSuccessors()[1]);
950 BasicBlock *SecondIRSucc = State.CFG.VPBB2IRBB.lookup(SecondVPSucc);
951 BasicBlock *IRBB = State.CFG.VPBB2IRBB[getParent()];
952 auto *Br = Builder.CreateCondBr(Cond, IRBB, SecondIRSucc);
953 // First successor is always forward, reset it to nullptr.
954 Br->setSuccessor(0, nullptr);
956 applyMetadata(*Br);
957 return Br;
958 }
960 assert(!GenerateSingleScalar &&
961 "Cannot generate scalar value for Broadcast");
962 return Builder.CreateVectorSplat(
963 State.VF, State.get(getOperand(0), /*NeedsSingleScalar=*/true),
964 "broadcast");
965 }
967 assert(!GenerateSingleScalar &&
968 "Cannot generate scalar value for BuildVector");
969 Value *Res = PoisonValue::get(
971 for (const auto &[Idx, Op] : enumerate(operands()))
972 Res = Builder.CreateInsertElement(Res, State.get(Op, true),
973 Builder.getInt64(Idx));
974 return Res;
975 }
977 Type *ScalarTy = getScalarType();
978 auto *WideTy = VectorType::get(ScalarTy, State.VF * getNumOperands());
979 Value *Res = PoisonValue::get(WideTy);
980 for (const auto &[Idx, Op] : enumerate(operands()))
981 Res = Builder.CreateInsertVector(WideTy, Res, State.get(Op),
982 Idx * State.VF.getKnownMinValue());
983 return Res;
984 }
986 if (State.VF.isScalar())
987 return State.get(getOperand(0), true);
988 IRBuilderBase::FastMathFlagGuard FMFG(Builder);
990 // If this start vector is scaled then it should produce a vector with fewer
991 // elements than the VF.
992 ElementCount VF = State.VF.divideCoefficientBy(
993 cast<VPConstantInt>(getOperand(2))->getZExtValue());
994 auto *Iden = Builder.CreateVectorSplat(VF, State.get(getOperand(1), true));
995 return Builder.CreateInsertElement(Iden, State.get(getOperand(0), true),
996 Builder.getInt64(0));
997 }
999 assert(GenerateSingleScalar &&
1000 "Can only generate first lane for ComputeReductionResult");
1001 RecurKind RK = getRecurKind();
1002 bool IsOrdered = isReductionOrdered();
1003 bool IsInLoop = isReductionInLoop();
1005 "FindIV should use min/max reduction kinds");
1006
1007 // The recipe may have multiple operands to be reduced together.
1008 unsigned NumOperandsToReduce = getNumOperands();
1009 SmallVector<Value *, 2> RdxParts(NumOperandsToReduce);
1010 for (unsigned Part = 0; Part < NumOperandsToReduce; ++Part)
1011 RdxParts[Part] = State.get(getOperand(Part), IsInLoop);
1012
1013 IRBuilderBase::FastMathFlagGuard FMFG(Builder);
1015
1016 // Reduce multiple operands into one.
1017 Value *ReducedPartRdx = RdxParts[0];
1018 if (IsOrdered) {
1019 ReducedPartRdx = RdxParts[NumOperandsToReduce - 1];
1020 } else {
1021 // Floating-point operations should have some FMF to enable the reduction.
1022 for (unsigned Part = 1; Part < NumOperandsToReduce; ++Part) {
1023 Value *RdxPart = RdxParts[Part];
1025 ReducedPartRdx = createMinMaxOp(Builder, RK, ReducedPartRdx, RdxPart);
1026 else {
1027 // For sub-recurrences, each part's reduction variable is already
1028 // negative, we need to do: reduce.add(-acc_uf0 + -acc_uf1)
1029 Instruction::BinaryOps Opcode =
1031 ? getSubRecurOpcode(RK)
1032 : (Instruction::BinaryOps)RecurrenceDescriptor::getOpcode(RK);
1033 ReducedPartRdx =
1034 Builder.CreateBinOp(Opcode, RdxPart, ReducedPartRdx, "bin.rdx");
1035 }
1036 }
1037 }
1038
1039 // Create the reduction after the loop. Note that inloop reductions create
1040 // the target reduction in the loop using a Reduction recipe.
1041 if (State.VF.isVector() && !IsInLoop) {
1042 // TODO: Support in-order reductions based on the recurrence descriptor.
1043 // All ops in the reduction inherit fast-math-flags from the recurrence
1044 // descriptor.
1045 ReducedPartRdx = createSimpleReduction(Builder, ReducedPartRdx, RK);
1046 }
1047
1048 return ReducedPartRdx;
1049 }
1052 assert(GenerateSingleScalar &&
1053 "Can only generate first lane for ExtractLane and "
1054 "ExtractPenultimateElement");
1055 unsigned Offset =
1057 Value *Res;
1058 if (State.VF.isVector()) {
1059 assert(Offset <= State.VF.getKnownMinValue() &&
1060 "invalid offset to extract from");
1061 // Extract lane VF - Offset from the operand.
1062 Res = State.get(getOperand(0), VPLane::getLaneFromEnd(State.VF, Offset));
1063 } else {
1064 // TODO: Remove ExtractLastLane for scalar VFs.
1065 assert(Offset <= 1 && "invalid offset to extract from");
1066 Res = State.get(getOperand(0));
1067 }
1068 if (isa<ExtractElementInst>(Res))
1069 Res->setName(Name);
1070 return Res;
1071 }
1072 case VPInstruction::PtrAdd: {
1073 assert(GenerateSingleScalar && "Can only generate first lane for PtrAdd");
1074 Value *Ptr = State.get(getOperand(0), VPLane(0));
1075 Value *Addend = State.get(getOperand(1), VPLane(0));
1076 // TODO: Require that offset matches index type in VPlan.
1077 Addend = Builder.CreateSExtOrTrunc(
1078 Addend, Builder.getDataLayout().getIndexType(Ptr->getType()));
1079 return Builder.CreatePtrAdd(Ptr, Addend, Name, getGEPNoWrapFlags());
1080 }
1082 assert(!GenerateSingleScalar &&
1083 "Cannot generate scalar value for WidePtrAdd");
1084 Value *Ptr =
1086 Value *Addend = State.get(getOperand(1));
1087 return Builder.CreatePtrAdd(Ptr, Addend, Name, getGEPNoWrapFlags());
1088 }
1089 case VPInstruction::AnyOf: {
1090 assert(GenerateSingleScalar && "Can only generate first lane for AnyOf");
1091 Value *Res = State.get(getOperand(0));
1092 for (VPValue *Op : drop_begin(operands()))
1093 Res = Builder.CreateOr(Res, State.get(Op));
1094 return State.VF.isScalar() ? Res : Builder.CreateOrReduce(Res);
1095 }
1097 assert(GenerateSingleScalar &&
1098 "Can only generate first lane for ExtractLane");
1099 assert(getNumOperands() != 2 && "ExtractLane from single source should be "
1100 "simplified to ExtractElement.");
1101 Value *LaneToExtract = State.get(getOperand(0), true);
1102 Type *IdxTy = getOperand(0)->getScalarType();
1103 Value *Res = nullptr;
1104 Value *RuntimeVF = getRuntimeVF(Builder, IdxTy, State.VF);
1105
1106 for (unsigned Idx = 1; Idx != getNumOperands(); ++Idx) {
1107 Value *VectorStart =
1108 Builder.CreateMul(RuntimeVF, ConstantInt::get(IdxTy, Idx - 1));
1109 Value *VectorIdx = Idx == 1
1110 ? LaneToExtract
1111 : Builder.CreateSub(LaneToExtract, VectorStart);
1112 Value *Ext = State.VF.isScalar()
1113 ? State.get(getOperand(Idx))
1114 : Builder.CreateExtractElement(
1115 State.get(getOperand(Idx)), VectorIdx);
1116 if (Res) {
1117 Value *Cmp = Builder.CreateICmpUGE(LaneToExtract, VectorStart);
1118 Res = Builder.CreateSelect(Cmp, Ext, Res);
1119 } else {
1120 Res = Ext;
1121 }
1122 }
1123 return Res;
1124 }
1126 assert(GenerateSingleScalar &&
1127 "Can only generate first lane for FirstActiveLane");
1128 Type *Ty = this->getScalarType();
1129 if (getNumOperands() == 1) {
1130 Value *Mask = State.get(getOperand(0));
1131 return Builder.CreateCountTrailingZeroElems(Ty, Mask,
1132 /*ZeroIsPoison=*/false, Name);
1133 }
1134 // If there are multiple operands, create a chain of selects to pick the
1135 // first operand with an active lane and add the number of lanes of the
1136 // preceding operands.
1137 Value *RuntimeVF = getRuntimeVF(Builder, Ty, State.VF);
1138 unsigned LastOpIdx = getNumOperands() - 1;
1139 Value *Res = nullptr;
1140 for (int Idx = LastOpIdx; Idx >= 0; --Idx) {
1141 Value *TrailingZeros =
1142 State.VF.isScalar()
1143 ? Builder.CreateZExt(
1144 Builder.CreateICmpEQ(State.get(getOperand(Idx)),
1145 Builder.getFalse()),
1146 Ty)
1148 Ty, State.get(getOperand(Idx)),
1149 /*ZeroIsPoison=*/false, Name);
1150 Value *Current = Builder.CreateAdd(
1151 Builder.CreateMul(RuntimeVF, ConstantInt::get(Ty, Idx)),
1152 TrailingZeros);
1153 if (Res) {
1154 Value *Cmp = Builder.CreateICmpNE(TrailingZeros, RuntimeVF);
1155 Res = Builder.CreateSelect(Cmp, Current, Res);
1156 } else {
1157 Res = Current;
1158 }
1159 }
1160
1161 return Res;
1162 }
1164 assert(GenerateSingleScalar &&
1165 "Can only generate first lane for ResumeForEpilogue");
1166 return State.get(getOperand(0), true);
1168 assert(!GenerateSingleScalar && "Cannot generate scalar value for Reverse");
1169 return Builder.CreateVectorReverse(State.get(getOperand(0)), "reverse");
1171 assert(GenerateSingleScalar &&
1172 "Can only generate first lane for ExtractLastActive");
1173 Value *Result = State.get(getOperand(0), /*NeedsSingleScalar=*/true);
1174 for (unsigned Idx = 1; Idx < getNumOperands(); Idx += 2) {
1175 Value *Data = State.get(getOperand(Idx));
1176 Value *Mask = State.get(getOperand(Idx + 1));
1177 Type *VTy = Data->getType();
1178
1179 if (State.VF.isScalar())
1180 Result = Builder.CreateSelect(Mask, Data, Result);
1181 else
1182 Result = Builder.CreateIntrinsic(
1183 Intrinsic::experimental_vector_extract_last_active, {VTy},
1184 {Data, Mask, Result});
1185 }
1186
1187 return Result;
1188 }
1190 assert(!GenerateSingleScalar &&
1191 "Cannot generate scalar value for ExtractVectorForPart");
1192 Value *Src = State.get(getOperand(0));
1193 Type *DstTy = VectorType::get(getScalarType(), State.VF);
1194 uint64_t Part = cast<VPConstantInt>(getOperand(1))->getZExtValue();
1195
1196 if (Src->getType() == DstTy)
1197 return Src;
1198
1199 return Builder.CreateExtractVector(
1200 DstTy, Src, Builder.getInt64(State.VF.getKnownMinValue() * Part), Name);
1201 }
1203 assert(!GenerateSingleScalar &&
1204 "Cannot generate scalar value for StepVector");
1205 return State.Builder.CreateStepVector(
1206 VectorType::get(getScalarType(), State.VF));
1208 assert(GenerateSingleScalar &&
1209 "Can only generate first lane for Intrinsic");
1210 SmallVector<Value *, 2> Args;
1211 for (VPValue *Op : drop_end(operands()))
1212 Args.push_back(State.get(Op, /*NeedsSingleScalar=*/true));
1213 return State.Builder.CreateIntrinsic(getScalarType(),
1214 vputils::getIntrinsicID(this), Args,
1215 /*FMFSource=*/nullptr, getName());
1216 }
1218 unsigned Multiplier = cast<VPConstantInt>(getOperand(0))->getZExtValue();
1219 auto *WideDataTy = VectorType::get(getScalarType(), State.VF * Multiplier);
1220
1221 Value *Addr = State.get(getOperand(1), /*IsScalar=*/true);
1222 Align Alignment = Align(cast<VPConstantInt>(getOperand(2))->getZExtValue());
1223 Instruction *WideLI;
1224 if (isMasked()) {
1225 Value *Mask = State.get(getMask());
1226 WideLI = Builder.CreateMaskedLoad(WideDataTy, Addr, Alignment, Mask);
1227 } else {
1228 WideLI = Builder.CreateAlignedLoad(WideDataTy, Addr, Alignment);
1229 }
1230 applyMetadata(*WideLI);
1231 return WideLI;
1232 }
1234 unsigned Multiplier = cast<VPConstantInt>(getOperand(0))->getZExtValue();
1235 Value *WideData = State.get(getOperand(3));
1236 assert(cast<VectorType>(WideData->getType())->getElementCount() ==
1237 State.VF * Multiplier &&
1238 "stored value does not match wide element count");
1239 (void)Multiplier;
1240
1241 Value *Addr = State.get(getOperand(1), /*IsScalar=*/true);
1242 Align Alignment = Align(cast<VPConstantInt>(getOperand(2))->getZExtValue());
1243 Instruction *WideSI;
1244 if (isMasked()) {
1245 Value *Mask = State.get(getMask());
1246 WideSI = Builder.CreateMaskedStore(WideData, Addr, Alignment, Mask);
1247 } else {
1248 WideSI = Builder.CreateAlignedStore(WideData, Addr, Alignment);
1249 }
1250 applyMetadata(*WideSI);
1251 return WideSI;
1252 }
1254 llvm_unreachable("Should have been lowered in VPlanPredicator");
1255 default:
1256 llvm_unreachable("Unsupported opcode for instruction");
1257 }
1258}
1259
1261 unsigned Opcode, ElementCount VF, VPCostContext &Ctx) const {
1262 Type *ScalarTy = this->getScalarType();
1263 Type *ResultTy = VF.isVector() ? toVectorTy(ScalarTy, VF) : ScalarTy;
1264 switch (Opcode) {
1265 case Instruction::FNeg:
1266 return Ctx.TTI.getArithmeticInstrCost(Opcode, ResultTy, Ctx.CostKind);
1267 case Instruction::UDiv:
1268 case Instruction::SDiv:
1269 case Instruction::SRem:
1270 case Instruction::URem:
1271 case Instruction::Add:
1272 case Instruction::FAdd:
1273 case Instruction::Sub:
1274 case Instruction::FSub:
1275 case Instruction::Mul:
1276 case Instruction::FMul:
1277 case Instruction::FDiv:
1278 case Instruction::FRem:
1279 case Instruction::Shl:
1280 case Instruction::LShr:
1281 case Instruction::AShr:
1282 case Instruction::And:
1283 case Instruction::Or:
1284 case Instruction::Xor: {
1285 // Certain instructions can be cheaper if they have a constant second
1286 // operand. One example of this are shifts on x86.
1287 VPValue *RHS = getOperand(1);
1288 TargetTransformInfo::OperandValueInfo RHSInfo = Ctx.getOperandInfo(RHS);
1289
1290 if (RHSInfo.Kind == TargetTransformInfo::OK_AnyValue &&
1293
1296 if (CtxI)
1297 Operands.append(CtxI->value_op_begin(), CtxI->value_op_end());
1298 return Ctx.TTI.getArithmeticInstrCost(
1299 Opcode, ResultTy, Ctx.CostKind,
1300 {TargetTransformInfo::OK_AnyValue, TargetTransformInfo::OP_None},
1301 RHSInfo, Operands, CtxI, &Ctx.TLI);
1302 }
1303 case Instruction::Freeze:
1304 // NOTE: The only way to ask for the cost is via getInstructionCost, which
1305 // requires the actual vector instruction. Instead, both here and in the
1306 // LoopVectorizationCostModel::getInstructionCost the costs mirror the
1307 // current behaviour in llvm/Analysis/TargetTransformInfoImpl.h to keep
1308 // them in sync.
1309 return TTI::TCC_Free;
1310 case Instruction::ExtractValue:
1311 return Ctx.TTI.getInsertExtractValueCost(Instruction::ExtractValue,
1312 Ctx.CostKind);
1313 case Instruction::ICmp:
1314 case Instruction::FCmp: {
1315 Type *ScalarOpTy = getOperand(0)->getScalarType();
1316 Type *OpTy = VF.isVector() ? toVectorTy(ScalarOpTy, VF) : ScalarOpTy;
1318 return Ctx.TTI.getCmpSelInstrCost(
1320 Ctx.CostKind, {TTI::OK_AnyValue, TTI::OP_None},
1321 {TTI::OK_AnyValue, TTI::OP_None}, CtxI);
1322 }
1323 case Instruction::BitCast: {
1324 Type *ScalarTy = this->getScalarType();
1325 if (ScalarTy->isPointerTy())
1326 return 0;
1327 [[fallthrough]];
1328 }
1329 case Instruction::SExt:
1330 case Instruction::ZExt:
1331 case Instruction::FPToUI:
1332 case Instruction::FPToSI:
1333 case Instruction::FPExt:
1334 case Instruction::PtrToInt:
1335 case Instruction::PtrToAddr:
1336 case Instruction::IntToPtr:
1337 case Instruction::SIToFP:
1338 case Instruction::UIToFP:
1339 case Instruction::Trunc:
1340 case Instruction::FPTrunc:
1341 case Instruction::AddrSpaceCast: {
1342 // Computes the CastContextHint from a recipe that may access memory.
1343 auto ComputeCCH = [&](const VPRecipeBase *R) -> TTI::CastContextHint {
1344 if (isa<VPInterleaveBase>(R))
1346 if (const auto *ReplicateRecipe = dyn_cast<VPReplicateRecipe>(R)) {
1347 // Only compute CCH for memory operations, matching the legacy model
1348 // which only considers loads/stores for cast context hints.
1349 auto *UI = cast<Instruction>(ReplicateRecipe->getUnderlyingValue());
1350 if (!isa<LoadInst, StoreInst>(UI))
1352 return ReplicateRecipe->isPredicated() ? TTI::CastContextHint::Masked
1354 }
1355 const auto *WidenMemoryRecipe = dyn_cast<VPWidenMemoryRecipe>(R);
1356 if (WidenMemoryRecipe == nullptr)
1358 if (VF.isScalar())
1360 if (!WidenMemoryRecipe->isConsecutive())
1362 if (WidenMemoryRecipe->isMasked())
1365 };
1366
1367 VPValue *Operand = getOperand(0);
1369 bool IsReverse = false;
1370 // For Trunc/FPTrunc, get the context from the only user.
1371 if (Opcode == Instruction::Trunc || Opcode == Instruction::FPTrunc) {
1372 if (auto *Recipe = cast_or_null<VPRecipeBase>(getSingleUser())) {
1373 if (match(Recipe,
1377 IsReverse = true;
1379 Recipe->getVPSingleValue()->getSingleUser());
1380 }
1381 if (Recipe)
1382 CCH = ComputeCCH(Recipe);
1383 }
1384 }
1385 // For Z/Sext, get the context from the operand.
1386 else if (Opcode == Instruction::ZExt || Opcode == Instruction::SExt ||
1387 Opcode == Instruction::FPExt) {
1388 if (auto *Recipe = Operand->getDefiningRecipe()) {
1389 VPValue *ReverseOp;
1390 if (match(Recipe,
1391 m_CombineOr(m_Reverse(m_VPValue(ReverseOp)),
1393 m_VPValue(ReverseOp))))) {
1394 Recipe = ReverseOp->getDefiningRecipe();
1395 IsReverse = true;
1396 }
1397 if (Recipe)
1398 CCH = ComputeCCH(Recipe);
1399 }
1400 }
1401 if (IsReverse && CCH != TTI::CastContextHint::None)
1403
1404 auto *ScalarSrcTy = Operand->getScalarType();
1405 Type *SrcTy = VF.isVector() ? toVectorTy(ScalarSrcTy, VF) : ScalarSrcTy;
1406 // Arm TTI will use the underlying instruction to determine the cost.
1407 return Ctx.TTI.getCastInstrCost(
1408 Opcode, ResultTy, SrcTy, CCH, Ctx.CostKind,
1410 }
1411 case Instruction::Select: {
1413 bool IsScalarCond = getOperand(0)->isDefinedOutsideLoopRegions();
1414 Type *ScalarTy = this->getScalarType();
1415
1416 VPValue *Op0, *Op1;
1417 bool IsLogicalAnd =
1418 match(this, m_c_LogicalAnd(m_VPValue(Op0), m_VPValue(Op1)));
1419 bool IsLogicalOr =
1420 match(this, m_c_LogicalOr(m_VPValue(Op0), m_VPValue(Op1)));
1421 // Also match the inverted forms:
1422 // select x, false, y --> !x & y (still AND)
1423 // select x, y, true --> !x | y (still OR)
1424 IsLogicalAnd |=
1425 match(this, m_Select(m_VPValue(Op0), m_False(), m_VPValue(Op1)));
1426 IsLogicalOr |=
1427 match(this, m_Select(m_VPValue(Op0), m_VPValue(Op1), m_True()));
1428
1429 if (!IsScalarCond && ScalarTy->getScalarSizeInBits() == 1 &&
1430 (IsLogicalAnd || IsLogicalOr)) {
1431 // select x, y, false --> x & y
1432 // select x, true, y --> x | y
1433 const auto [Op1VK, Op1VP] = Ctx.getOperandInfo(Op0);
1434 const auto [Op2VK, Op2VP] = Ctx.getOperandInfo(Op1);
1435
1437 if (SI && all_of(operands(),
1438 [](VPValue *Op) { return Op->getUnderlyingValue(); }))
1439 append_range(Operands, SI->operands());
1440 return Ctx.TTI.getArithmeticInstrCost(
1441 IsLogicalOr ? Instruction::Or : Instruction::And, ResultTy,
1442 Ctx.CostKind, {Op1VK, Op1VP}, {Op2VK, Op2VP}, Operands, SI);
1443 }
1444
1445 Type *CondTy = getOperand(0)->getScalarType();
1446 if (!IsScalarCond && VF.isVector())
1447 CondTy = VectorType::get(CondTy, VF);
1448
1449 llvm::CmpPredicate Pred;
1450 if (!match(getOperand(0), m_Cmp(Pred, m_VPValue(), m_VPValue())))
1451 if (auto *CondIRV = dyn_cast<VPIRValue>(getOperand(0)))
1452 if (auto *Cmp = dyn_cast<CmpInst>(CondIRV->getValue()))
1453 Pred = Cmp->getPredicate();
1454 Type *VectorTy = toVectorTy(this->getScalarType(), VF);
1455 return Ctx.TTI.getCmpSelInstrCost(
1456 Instruction::Select, VectorTy, CondTy, Pred, Ctx.CostKind,
1457 {TTI::OK_AnyValue, TTI::OP_None}, {TTI::OK_AnyValue, TTI::OP_None}, SI);
1458 }
1459 }
1460 llvm_unreachable("called for unsupported opcode");
1461}
1462
1464 VPCostContext &Ctx) const {
1465 // NOTE: At the moment it seems only possible to expose this path for
1466 // the trunc, zext and sext opcodes.
1467 // TODO: Update VF arg to use onlyFirstLaneUsed once WidenCast is unified.
1469 // A scalar zext/trunc that only adjusts the width of an
1470 // ExplicitVectorLength to the canonical IV type is free: it feeds only
1471 // the IV increment and AVL decrement, which are modeled as free below.
1472 if (match(this, m_ZExtOrTrunc(m_EVL(m_VPValue()))))
1473 return 0;
1475 Ctx);
1476 }
1477
1479 if (!getUnderlyingValue() && getOpcode() != Instruction::FMul) {
1480 // TODO: Compute cost for VPInstructions without underlying values once
1481 // the legacy cost model has been retired.
1482 return 0;
1483 }
1484
1486 "Should only generate a vector value or single scalar, not scalars "
1487 "for all lanes.");
1489 getOpcode(),
1491 }
1492
1493 switch (getOpcode()) {
1494 case Instruction::Select: {
1496 match(getOperand(0), m_Cmp(Pred, m_VPValue(), m_VPValue()));
1497 auto *CondTy = getOperand(0)->getScalarType();
1498 auto *VecTy = getOperand(1)->getScalarType();
1499 if (!vputils::onlyFirstLaneUsed(this)) {
1500 CondTy = toVectorTy(CondTy, VF);
1501 VecTy = toVectorTy(VecTy, VF);
1502 }
1503 return Ctx.TTI.getCmpSelInstrCost(Instruction::Select, VecTy, CondTy, Pred,
1504 Ctx.CostKind);
1505 }
1506 case Instruction::ExtractElement:
1508 if (VF.isScalar()) {
1509 // ExtractLane with VF=1 takes care of handling extracting across multiple
1510 // parts.
1511 return 0;
1512 }
1513
1514 // Add on the cost of extracting the element.
1515 auto *VecTy = toVectorTy(getScalarType(), VF);
1516 return Ctx.TTI.getVectorInstrCost(Instruction::ExtractElement, VecTy,
1517 Ctx.CostKind);
1518 }
1519 case VPInstruction::AnyOf: {
1520 auto *VecTy = toVectorTy(this->getScalarType(), VF);
1521 return Ctx.TTI.getArithmeticReductionCost(
1522 Instruction::Or, cast<VectorType>(VecTy), std::nullopt, Ctx.CostKind);
1523 }
1525 Type *Ty = this->getScalarType();
1526 Type *ScalarTy = getOperand(0)->getScalarType();
1527 if (VF.isScalar())
1528 return Ctx.TTI.getCmpSelInstrCost(Instruction::ICmp, ScalarTy,
1530 CmpInst::ICMP_EQ, Ctx.CostKind);
1531 // Calculate the cost of determining the lane index.
1532 auto *PredTy = toVectorTy(ScalarTy, VF);
1533 IntrinsicCostAttributes Attrs(Intrinsic::experimental_cttz_elts, Ty,
1534 {PredTy, Type::getInt1Ty(Ctx.LLVMCtx)});
1535 return Ctx.TTI.getIntrinsicInstrCost(Attrs, Ctx.CostKind);
1536 }
1538 Type *Ty = this->getScalarType();
1539 Type *ScalarTy = getOperand(0)->getScalarType();
1540 if (VF.isScalar())
1541 return Ctx.TTI.getCmpSelInstrCost(Instruction::ICmp, ScalarTy,
1543 CmpInst::ICMP_EQ, Ctx.CostKind);
1544 // Calculate the cost of determining the lane index: NOT + cttz_elts + SUB.
1545 auto *PredTy = toVectorTy(ScalarTy, VF);
1546 IntrinsicCostAttributes Attrs(Intrinsic::experimental_cttz_elts, Ty,
1547 {PredTy, Type::getInt1Ty(Ctx.LLVMCtx)});
1548 InstructionCost Cost = Ctx.TTI.getIntrinsicInstrCost(Attrs, Ctx.CostKind);
1549 // Add cost of NOT operation on the predicate.
1550 Cost += Ctx.TTI.getArithmeticInstrCost(
1551 Instruction::Xor, PredTy, Ctx.CostKind,
1552 {TargetTransformInfo::OK_AnyValue, TargetTransformInfo::OP_None},
1553 {TargetTransformInfo::OK_UniformConstantValue,
1554 TargetTransformInfo::OP_None});
1555 // Add cost of SUB operation on the index.
1556 Cost += Ctx.TTI.getArithmeticInstrCost(Instruction::Sub, Ty, Ctx.CostKind);
1557 return Cost;
1558 }
1560 Type *ScalarTy = this->getScalarType();
1561 Type *VecTy = toVectorTy(ScalarTy, VF);
1562 Type *MaskTy = toVectorTy(Type::getInt1Ty(Ctx.LLVMCtx), VF);
1564 Intrinsic::experimental_vector_extract_last_active, ScalarTy,
1565 {VecTy, MaskTy, ScalarTy});
1566 return Ctx.TTI.getIntrinsicInstrCost(ICA, Ctx.CostKind);
1567 }
1569 assert(VF.isVector() && "Scalar FirstOrderRecurrenceSplice?");
1570 Type *VectorTy = toVectorTy(this->getScalarType(), VF);
1571 return Ctx.TTI.getShuffleCost(
1573 cast<VectorType>(VectorTy), Ctx.CostKind, {}, -1);
1574 }
1577 Type *ArgTy = getOperand(0)->getScalarType();
1578 uint64_t Multiplier =
1580 ? cast<VPConstantInt>(getOperand(2))->getZExtValue()
1581 : 1;
1582 Type *RetTy = toVectorTy(Type::getInt1Ty(Ctx.LLVMCtx), VF * Multiplier);
1583 IntrinsicCostAttributes Attrs(Intrinsic::get_active_lane_mask, RetTy,
1584 {ArgTy, ArgTy});
1585 return Ctx.TTI.getIntrinsicInstrCost(Attrs, Ctx.CostKind);
1586 }
1588 Type *Arg0Ty = getOperand(0)->getScalarType();
1589 Type *I32Ty = Type::getInt32Ty(Ctx.LLVMCtx);
1590 Type *I1Ty = Type::getInt1Ty(Ctx.LLVMCtx);
1591 IntrinsicCostAttributes Attrs(Intrinsic::experimental_get_vector_length,
1592 I32Ty, {Arg0Ty, I32Ty, I1Ty});
1593 return Ctx.TTI.getIntrinsicInstrCost(Attrs, Ctx.CostKind);
1594 }
1596 assert(VF.isVector() && "Reverse operation must be vector type");
1597 Type *EltTy = this->getScalarType();
1598 // Skip the reverse operation cost for the mask.
1599 // FIXME: Remove this once redundant mask reverse operations can be
1600 // eliminated by VPlanTransforms::cse before cost computation.
1601 if (EltTy->isIntegerTy(1))
1602 return 0;
1603 auto *VectorTy = cast<VectorType>(toVectorTy(EltTy, VF));
1604 return Ctx.TTI.getShuffleCost(TargetTransformInfo::SK_Reverse, VectorTy,
1605 VectorTy, Ctx.CostKind, /*Mask=*/{},
1606 /*Index=*/0);
1607 }
1609 // Add on the cost of extracting the element.
1610 auto *VecTy = toVectorTy(getOperand(0)->getScalarType(), VF);
1611 return Ctx.TTI.getIndexedVectorInstrCostFromEnd(Instruction::ExtractElement,
1612 VecTy, Ctx.CostKind, 0);
1613 }
1614 case VPInstruction::Not: {
1615 Type *ValTy = this->getScalarType();
1616 // InstCombine will fold `xor` to the conditional branch.
1617 if (auto *U = const_cast<VPUser *>(getSingleUser()))
1618 if (match(U, m_BranchOnCond(m_VPValue())))
1619 return 0;
1620 if (!vputils::onlyFirstLaneUsed(this))
1621 ValTy = toVectorTy(ValTy, VF);
1622 return Ctx.TTI.getArithmeticInstrCost(Instruction::Xor, ValTy,
1623 Ctx.CostKind);
1624 }
1626 Type *ElementTy = getOperand(0)->getScalarType();
1627 auto *MaskTy = cast<VectorType>(toVectorTy(ElementTy, VF));
1628 return Ctx.TTI.getExtendedReductionCost(
1629 Instruction::Add, /*IsUnsigned=*/true, getScalarType(), MaskTy,
1630 /*FMF=*/{}, Ctx.CostKind);
1631 }
1633 // If TC <= VF then this is just a branch.
1634 // FIXME: Removing the branch happens in simplifyBranchConditionForVFAndUF
1635 // where it checks TC <= VF * UF, but we don't know UF yet. This means in
1636 // some cases we get a cost that's too high due to counting a cmp that
1637 // later gets removed.
1638 // FIXME: The compare could also be removed if TC = M * vscale,
1639 // VF = N * vscale, and M <= N. Detecting that would require having the
1640 // trip count as a SCEV though.
1641 if (VPCostContext::executesAtMostOnce(*getParent()->getPlan(), VF))
1642 return 0;
1643 // Otherwise BranchOnCount generates ICmpEQ followed by a branch.
1644 Type *ValTy = getOperand(0)->getScalarType();
1645 return Ctx.TTI.getCmpSelInstrCost(Instruction::ICmp, ValTy,
1647 CmpInst::ICMP_EQ, Ctx.CostKind);
1648 }
1650 Type *Ty = getScalarType();
1652 for (const VPValue *Op : drop_end(operands()))
1653 ArgTys.push_back(Op->getScalarType());
1654 IntrinsicCostAttributes Attrs(vputils::getIntrinsicID(this), Ty, ArgTys);
1655 return Ctx.TTI.getIntrinsicInstrCost(Attrs, Ctx.CostKind);
1656 }
1658 // TODO: This isn't quite right since even if the step-vector is hoisted
1659 // out of the loop it has a non-zero cost in the middle block, etc.
1660 // Once the stepvector is correctly hoisted out of the vector loop by the
1661 // licm transform we can add the cost here so that it doesn't incorrectly
1662 // affect the choice of VF.
1663 return 0;
1665 // It isn't currently possible to expose cases where WideIVStep's cost is
1666 // queried.
1667 llvm_unreachable("Unhandled opcode");
1668 case Instruction::FCmp:
1669 case Instruction::ICmp:
1671 getOpcode(),
1674 if (VF == ElementCount::getScalable(1))
1676 [[fallthrough]];
1677 default:
1678 // TODO: Compute cost other VPInstructions once the legacy cost model has
1679 // been retired.
1681 "unexpected VPInstruction witht underlying value");
1682 return 0;
1683 }
1684}
1685
1698
1700 switch (getOpcode()) {
1701 case Instruction::Load:
1702 case Instruction::PHI:
1706 return true;
1707 default:
1709 }
1710}
1711
1713#ifndef NDEBUG
1714 Type *Ty = Op->getScalarType();
1715 switch (getOpcode()) {
1719 assert(Ty == getOperand(0)->getScalarType() &&
1720 "types of operand 0 and new operand must match");
1721 break;
1725 assert(Ty == getOperand(0)->getScalarType() &&
1726 "appended operand must match operand 0's scalar type");
1727 break;
1729 assert(Ty == getOperand(1)->getScalarType() &&
1730 "appended operand must match operand 1's scalar type");
1731 break;
1733 // The recipe is constructed with 3 operands (result, data, mask). Extra
1734 // operands beyond that are appended in (data, mask) pairs.
1735 constexpr unsigned NumInitialOperands = 3;
1736 assert(getNumOperands() >= NumInitialOperands &&
1737 "ExtractLastActive must have at least the initial 3 operands");
1738 bool IsMaskSlot = ((getNumOperands() - NumInitialOperands) & 1u) == 1u;
1739 assert((IsMaskSlot ? Ty->isIntegerTy(1)
1740 : Ty == getOperand(1)->getScalarType()) &&
1741 "ExtractLastActive expects alternating data/mask operands "
1742 "matching operand 1's type and i1, respectively");
1743 break;
1744 }
1745 default:
1746 llvm_unreachable("opcode does not support growing the operand list "
1747 "outside of construction");
1748 }
1749#endif
1751}
1752
1754 assert(!isAbstract() && "cannot execute this VPInstruction");
1755 IRBuilderBase::FastMathFlagGuard FMFGuard(State.Builder);
1757 "Set flags not supported for the provided opcode");
1759 "Opcode requires specific flags to be set");
1760 State.Builder.setFastMathFlags(getFastMathFlagsOrNone());
1761 bool GenerateSingleScalar = State.VF.isScalar() || doesGenerateSingleScalar();
1762 Value *GeneratedValue = generate(State, GenerateSingleScalar);
1763 if (!hasResult())
1764 return;
1765 assert(GeneratedValue && "generate must produce a value");
1766 assert(GeneratedValue->getType()->isVectorTy() == !GenerateSingleScalar &&
1767 "scalar value but not only first lane defined");
1768 State.set(this, GeneratedValue, GenerateSingleScalar);
1770 getOpcode() == Instruction::Freeze) {
1771 // FIXME: This is a workaround to enable reliable updates of the scalar loop
1772 // resume phis, and to let epilogue vectorization recover the frozen
1773 // reduction start from the main plan. Must be removed once epilogue
1774 // vectorization explicitly connects VPlans.
1775 setUnderlyingValue(GeneratedValue);
1776 }
1777}
1778
1782 return false;
1783 switch (getOpcode()) {
1784 case Instruction::ExtractValue:
1785 case Instruction::GetElementPtr:
1786 case Instruction::ExtractElement:
1787 case Instruction::InsertElement:
1788 case Instruction::Freeze:
1789 case Instruction::FCmp:
1790 case Instruction::ICmp:
1791 case Instruction::Select:
1792 case Instruction::PHI:
1819 case VPInstruction::Not:
1828 return false;
1830 case Instruction::Call:
1832 default:
1833 return true;
1834 }
1835}
1836
1838 assert(is_contained(operands(), Op) && "Op must be an operand of the recipe");
1840 return vputils::onlyFirstLaneUsed(this);
1841
1842 switch (getOpcode()) {
1843 default:
1844 return false;
1845 case Instruction::ExtractElement:
1846 return Op == getOperand(1);
1847 case Instruction::InsertElement:
1848 return Op == getOperand(1) || Op == getOperand(2);
1850 return Op == getOperand(0);
1851 case Instruction::PHI:
1852 case Instruction::Load:
1865 return true;
1868 return Op == getOperand(0) || Op == getOperand(1) || Op == getOperand(2);
1872 return Op == getOperand(0);
1873 }
1874}
1875
1877 switch (getOpcode()) {
1878 default:
1879 return false;
1884 return true;
1885 };
1886}
1887
1888#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1890 VPSlotTracker SlotTracker(getParent()->getPlan());
1892}
1893
1895 VPSlotTracker &SlotTracker) const {
1896 O << Indent << "EMIT" << (isSingleScalar() ? "-SCALAR" : "") << " ";
1897
1898 if (hasResult()) {
1900 O << " = ";
1901 }
1902
1903 switch (getOpcode()) {
1904 case VPInstruction::Not:
1905 O << "not";
1906 break;
1908 O << "active lane mask";
1909 break;
1911 O << "wide active lane mask";
1912 break;
1914 O << "wide vector load";
1915 break;
1917 O << "wide vector store";
1918 break;
1920 O << "concat-vectors";
1921 break;
1923 O << "incoming-alias-mask";
1924 break;
1926 O << "EXPLICIT-VECTOR-LENGTH";
1927 break;
1929 O << "first-order splice";
1930 break;
1932 O << "branch-on-cond";
1933 break;
1935 O << "branch-on-two-conds";
1936 break;
1938 O << "VF * Part +";
1939 break;
1941 O << "branch-on-count";
1942 break;
1944 O << "broadcast";
1945 break;
1947 O << "buildvector";
1948 break;
1950 O << "exiting-iv-value";
1951 break;
1953 O << "masked-cond";
1954 break;
1956 O << "extract-lane";
1957 break;
1959 O << "extract-last-lane";
1960 break;
1962 O << "extract-last-part";
1963 break;
1965 O << "extract-penultimate-element";
1966 break;
1968 O << "extract-vector-for-part";
1969 break;
1971 O << "compute-reduction-result";
1972 break;
1974 O << "logical-and";
1975 break;
1977 O << "logical-or";
1978 break;
1980 O << "ptradd";
1981 break;
1983 O << "wide-ptradd";
1984 break;
1986 O << "any-of";
1987 break;
1989 O << "first-active-lane";
1990 break;
1992 O << "last-active-lane";
1993 break;
1995 O << "reduction-start-vector";
1996 break;
1998 O << "resume-for-epilogue";
1999 break;
2001 O << "reverse";
2002 break;
2004 O << "unpack";
2005 break;
2007 O << "extract-last-active";
2008 break;
2010 O << "num-active-lanes";
2011 break;
2013 O << "wide-iv-step";
2014 break;
2016 O << "step-vector " << *getScalarType();
2017 break;
2019 case Instruction::Call: {
2020 O << "call";
2021 printFlags(O);
2022 printRetAttrs(O);
2023 O << *getScalarType() << " ";
2024 unsigned NumArgs;
2027 NumArgs = getNumOperands() - 1;
2028 } else {
2029 getCalledFunction(operands())->printAsOperand(O, /*PrintType=*/false);
2030 NumArgs = getCalledFnOperandIndex(operands());
2031 }
2032 O << "(";
2034 O, [&O, &SlotTracker, this](const auto &IndexedOp) {
2035 auto [Idx, Op] = IndexedOp;
2036 printParamAttrs(O, Idx);
2037 Op->printAsOperand(O, SlotTracker);
2038 });
2039 O << ")";
2040 printFnAttrs(O);
2041 if (VPValue *Mask = getMask()) {
2042 O << ", ";
2043 Mask->printAsOperand(O, SlotTracker);
2044 }
2045 return;
2046 }
2047 case Instruction::Load:
2048 O << "load";
2049 break;
2050 default:
2052 }
2053
2054 if (!operands_empty()) {
2055 printFlags(O);
2057 }
2059 O << " to " << *getScalarType();
2060}
2061#endif
2062
2063/// Shared execute logic for VPPhi and VPWidenPHIRecipe. Creates a PHI node,
2064/// adds incoming values, and stores the result in State. For header phis, only
2065/// the preheader incoming value is added; the backedge is fixed up later by
2066/// VPlan::execute().
2068 VPTransformState &State, bool IsScalar,
2069 const Twine &Name) {
2070 unsigned NumIncoming = VPBlockUtils::isHeader(R->getParent(), State.VPDT)
2071 ? 1
2072 : Phi.getNumIncoming();
2073 Value *FirstInc = State.get(Phi.getIncomingValue(0), IsScalar);
2074 PHINode *NewPhi = State.Builder.CreatePHI(FirstInc->getType(), 2, Name);
2075 NewPhi->addIncoming(FirstInc,
2076 State.CFG.VPBB2IRBB.at(Phi.getIncomingBlock(0)));
2077 for (unsigned Idx = 1; Idx != NumIncoming; ++Idx)
2078 NewPhi->addIncoming(State.get(Phi.getIncomingValue(Idx), IsScalar),
2079 State.CFG.VPBB2IRBB.at(Phi.getIncomingBlock(Idx)));
2080 State.set(R, NewPhi, IsScalar);
2081}
2082
2084 executePhiRecipe(this, *this, State, /*IsScalar=*/true, getName());
2085}
2086
2087#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2088void VPPhi::printRecipe(raw_ostream &O, const Twine &Indent,
2089 VPSlotTracker &SlotTracker) const {
2090 O << Indent << "EMIT" << (isSingleScalar() ? "-SCALAR" : "") << " ";
2092 O << " = phi";
2093 printFlags(O);
2095}
2096#endif
2097
2098VPIRInstruction *VPIRInstruction ::create(Instruction &I) {
2099 if (auto *Phi = dyn_cast<PHINode>(&I))
2100 return new VPIRPhi(*Phi);
2101 return new VPIRInstruction(I);
2102}
2103
2105 assert(!isa<VPIRPhi>(this) && getNumOperands() == 0 &&
2106 "PHINodes must be handled by VPIRPhi");
2107 // Advance the insert point after the wrapped IR instruction. This allows
2108 // interleaving VPIRInstructions and other recipes.
2109 State.Builder.SetInsertPoint(std::next(I.getIterator()));
2110}
2111
2113 VPCostContext &Ctx) const {
2114 // The recipe wraps an existing IR instruction on the border of VPlan's scope,
2115 // hence it does not contribute to the cost-modeling for the VPlan.
2116 return 0;
2117}
2118
2119#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2121 VPSlotTracker &SlotTracker) const {
2122 O << Indent << "IR " << I;
2123}
2124#endif
2125
2127 PHINode *Phi = &getIRPhi();
2128 for (const auto &[Idx, Op] : enumerate(operands())) {
2129 VPValue *ExitValue = Op;
2130 auto Lane = vputils::isSingleScalar(ExitValue)
2132 : VPLane::getLastLaneForVF(State.VF);
2133 VPBlockBase *Pred = getParent()->getPredecessors()[Idx];
2134 auto *PredVPBB = Pred->getExitingBasicBlock();
2135 BasicBlock *PredBB = State.CFG.VPBB2IRBB[PredVPBB];
2136 // Set insertion point in PredBB in case an extract needs to be generated.
2137 // TODO: Model extracts explicitly.
2138 State.Builder.SetInsertPoint(PredBB->getTerminator());
2139 Value *V = State.get(ExitValue, VPLane(Lane));
2140 // If there is no existing block for PredBB in the phi, add a new incoming
2141 // value. Otherwise update the existing incoming value for PredBB.
2142 if (Phi->getBasicBlockIndex(PredBB) == -1)
2143 Phi->addIncoming(V, PredBB);
2144 else
2145 Phi->setIncomingValueForBlock(PredBB, V);
2146 }
2147
2148 // Advance the insert point after the wrapped IR instruction. This allows
2149 // interleaving VPIRInstructions and other recipes.
2150 State.Builder.SetInsertPoint(std::next(Phi->getIterator()));
2151}
2152
2154 VPRecipeBase *R = const_cast<VPRecipeBase *>(getAsRecipe());
2155 assert(R->getNumOperands() == R->getParent()->getNumPredecessors() &&
2156 "Number of phi operands must match number of predecessors");
2157 unsigned Position = R->getParent()->getIndexForPredecessor(IncomingBlock);
2158 R->removeOperand(Position);
2159}
2160
2161VPValue *
2163 VPRecipeBase *R = const_cast<VPRecipeBase *>(getAsRecipe());
2164 return getIncomingValue(R->getParent()->getIndexForPredecessor(VPBB));
2165}
2166
2168 VPValue *V) const {
2169 VPRecipeBase *R = const_cast<VPRecipeBase *>(getAsRecipe());
2170 R->setOperand(R->getParent()->getIndexForPredecessor(VPBB), V);
2171}
2172
2173#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2175 VPSlotTracker &SlotTracker) const {
2177 O << "[ ";
2178 std::get<0>(Op)->printAsOperand(O, SlotTracker);
2179 O << ", ";
2180 std::get<1>(Op)->printAsOperand(O);
2181 O << " ]";
2182 });
2183}
2184#endif
2185
2186#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2188 VPSlotTracker &SlotTracker) const {
2190
2191 if (getNumOperands() != 0) {
2192 O << " (extra operand" << (getNumOperands() > 1 ? "s" : "") << ": ";
2194 [&O, &SlotTracker](auto Op) {
2195 std::get<0>(Op)->printAsOperand(O, SlotTracker);
2196 O << " from ";
2197 std::get<1>(Op)->printAsOperand(O);
2198 });
2199 O << ")";
2200 }
2201}
2202#endif
2203
2205 if (Metadata.empty())
2206 return;
2207 // Frequencies and estimated branch weights are VPlan-internal and must not
2208 // reach IR.
2209 unsigned ExecFreqKind = getMDKindID(ExecutionFrequencyMDName);
2210 unsigned EstProfKind = getMDKindID(EstimatedProfileMDName);
2211 for (const auto &[Kind, Node] : Metadata)
2212 if (Kind != ExecFreqKind && Kind != EstProfKind)
2213 I.setMetadata(Kind, Node);
2214}
2215
2216/// Returns the execution frequency recorded in \p Node.
2218 assert(Node->getNumOperands() <= 2 && "unexpected frequency node shape");
2219 uint64_t Freq =
2220 mdconst::extract<ConstantInt>(Node->getOperand(0))->getZExtValue();
2222 "frequency cannot exceed the one of an always executing block");
2223 return {BlockFrequency(Freq), Node->getNumOperands() == 2};
2224}
2225
2227 std::optional<VPExecutionFrequency> Freq, LLVMContext &Ctx) {
2228 // A recipe that always executes needs no annotation.
2229 if (!Freq || vputils::getExecutionProbability(Freq->Freq).isOne())
2230 return;
2232 ConstantInt::get(Type::getInt64Ty(Ctx), Freq->Freq.getFrequency()))};
2233 if (Freq->IsEstimated)
2235 setMetadata(Ctx.getMDKindID(ExecutionFrequencyMDName), MDNode::get(Ctx, Ops));
2236}
2237
2238std::optional<VPExecutionFrequency>
2240 if (MDNode *Node = getInternalMetadata(ExecutionFrequencyMDName))
2242 return std::nullopt;
2243}
2244
2246 if (Metadata.empty())
2247 return;
2248 unsigned ID = getMDKindID(ExecutionFrequencyMDName);
2249 erase_if(Metadata, [ID](const auto &P) { return P.first == ID; });
2250}
2251
2253 erase_if(Metadata,
2254 [&](const auto &MD) { return !is_contained(Other.Metadata, MD); });
2255}
2256
2257#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2259 const Module *M = SlotTracker.getModule();
2260 if (Metadata.empty() || !M)
2261 return;
2262
2263 ArrayRef<StringRef> MDNames = SlotTracker.getMDNames();
2264 O << " (";
2265 interleaveComma(Metadata, O, [&](const auto &KindNodePair) {
2266 auto [Kind, Node] = KindNodePair;
2267 assert(Kind < MDNames.size() && !MDNames[Kind].empty() &&
2268 "Unexpected unnamed metadata kind");
2269 O << "!" << MDNames[Kind] << " ";
2270 // Print the values of branch weights, which are more informative than the
2271 // ID of the metadata node holding them.
2272 SmallVector<uint32_t> Weights;
2273 bool IsEstimatedProfile = MDNames[Kind] == EstimatedProfileMDName;
2274 if ((Kind == LLVMContext::MD_prof || IsEstimatedProfile) &&
2275 extractBranchWeights(Node, Weights)) {
2276 if (IsEstimatedProfile)
2277 O << "estimated ";
2278 O << "{";
2279 interleaveComma(Weights, O);
2280 O << "}";
2281 } else if (MDNames[Kind] == ExecutionFrequencyMDName) {
2282 // Print the frequency together with the probability it corresponds to.
2283 auto [Freq, IsEstimated] = getExecutionFrequencyFromMD(Node);
2284 const fltSemantics &Sem = APFloat::IEEEdouble();
2285 uint64_t Full =
2287 APFloat Percent = APFloat(Sem, Freq.getFrequency()) * APFloat(Sem, 100) /
2288 APFloat(Sem, Full);
2289 SmallString<16> PercentStr;
2290 Percent.toString(PercentStr, /*FormatPrecision=*/4);
2291 O << Freq.getFrequency() << " (" << PercentStr << "%"
2292 << (IsEstimated ? ", estimated" : "") << ")";
2293 } else {
2294 SlotTracker.printMetadataAsOperand(O, Node);
2295 }
2296 });
2297 O << ")";
2298}
2299#endif
2300
2302 FunctionType *WideTy) {
2303 assert(Call.getOpcode() == Instruction::Call && "expected call");
2304 unsigned NumArgs = getCalledFnOperandIndex(Call.operands());
2305 assert(NumArgs <= WideTy->getNumParams() &&
2306 "widened call must take all scalar arguments");
2307 LLVMContext &Ctx = WideTy->getContext();
2308 AttributeList ScalarAttrs = Call.CallAttrs;
2309
2310 // Limit initial supported set of attributes to subset of poison-generating
2311 // ones that can be transferred to the widened return value and arguments.
2312 // TODO: Support additional attributes.
2313 static constexpr Attribute::AttrKind PropagatableAttrKinds[] = {
2314 Attribute::Alignment, Attribute::NonNull, Attribute::NoFPClass,
2315 Attribute::Range};
2316
2317 // Only keep allowed attributes (which do not trigger UB) and ones that are
2318 // compatible with the widened type Ty.
2319 auto Filter = [&](Type *Ty, AttributeSet AS) {
2320 AttributeMask Incompatible = AttributeFuncs::typeIncompatible(Ty, AS);
2321 AttrBuilder AB(Ctx);
2322 for (Attribute::AttrKind K : PropagatableAttrKinds)
2323 if (AS.hasAttribute(K) && !Incompatible.contains(K))
2324 AB.addAttribute(AS.getAttribute(K));
2325 return AttributeSet::get(Ctx, AB);
2326 };
2327
2328 AttributeSet RetAttrs =
2329 Filter(WideTy->getReturnType(), ScalarAttrs.getRetAttrs());
2330
2331 // For masked calls, the widened call also executes for lanes the scalar call
2332 // did not execute for. Masked variants ignore the inactive lanes of widened
2333 // arguments, but scalar (uniform or linear) arguments are shared by all
2334 // lanes, e.g. linear arguments pass the value of the first lane, which may
2335 // be inactive. Unmasked variants process all lanes.
2336 bool IsMaskedVariant = WideTy->getNumParams() > NumArgs;
2337 SmallVector<AttributeSet> ArgAttrs(WideTy->getNumParams());
2338 for (unsigned I = 0; I != NumArgs; ++I) {
2339 Type *WideArgTy = WideTy->getParamType(I);
2340 bool IsWidenedArg = WideArgTy != Call.getOperand(I)->getScalarType();
2341 if (Call.isMasked() && (!IsMaskedVariant || !IsWidenedArg))
2342 continue;
2343 ArgAttrs[I] = Filter(WideArgTy, ScalarAttrs.getParamAttrs(I));
2344 }
2345
2346 CallAttrs = AttributeList::get(Ctx, AttributeSet(), RetAttrs, ArgAttrs);
2347}
2348
2350 LLVMContext &Ctx) {
2351 CallAttrs =
2352 CallAttrs.intersectWith(Ctx, Other.CallAttrs).value_or(AttributeList());
2353}
2354
2355#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2357 AttributeSet RetAttrs = CallAttrs.getRetAttrs();
2358 if (RetAttrs.hasAttributes())
2359 O << RetAttrs.getAsString() << " ";
2360}
2361
2362void VPIRAttributes::printParamAttrs(raw_ostream &O, unsigned ArgIdx) const {
2363 AttributeSet PA = CallAttrs.getParamAttrs(ArgIdx);
2364 if (PA.hasAttributes())
2365 O << PA.getAsString() << " ";
2366}
2367
2369 AttributeSet FnAttrs = CallAttrs.getFnAttrs();
2370 if (FnAttrs.hasAttributes())
2371 O << " " << FnAttrs.getAsString();
2372}
2373#endif
2374
2376 assert(State.VF.isVector() && "not widening");
2377 assert(Variant != nullptr && "Can't create vector function.");
2378
2379 FunctionType *VFTy = Variant->getFunctionType();
2380 // Add return type if intrinsic is overloaded on it.
2382 for (const auto &I : enumerate(args())) {
2383 Value *Arg;
2384 // Some vectorized function variants may also take a scalar argument,
2385 // e.g. linear parameters for pointers. This needs to be the scalar value
2386 // from the start of the respective part when interleaving.
2387 if (!VFTy->getParamType(I.index())->isVectorTy())
2388 Arg = State.get(I.value(), VPLane(0));
2389 else
2390 Arg = State.get(I.value(), usesFirstLaneOnly(I.value()));
2391 Args.push_back(Arg);
2392 }
2393
2394 CallInst *V = State.Builder.CreateCall(Variant, Args);
2395 applyFlags(*V);
2396 applyMetadata(*V);
2397 applyAttrs(*V);
2398 V->setCallingConv(Variant->getCallingConv());
2399
2400 if (!V->getType()->isVoidTy())
2401 State.set(this, V);
2402}
2403
2405 VPCostContext &Ctx) const {
2406 assert(getVectorizedTypeVF(Variant->getReturnType()) == VF &&
2407 "Variant return type must match VF");
2408 return computeCallCost(Variant, Ctx);
2409}
2410
2412 VPCostContext &Ctx) {
2413 return Ctx.TTI.getCallInstrCost(nullptr, Variant->getReturnType(),
2414 Variant->getFunctionType()->params(),
2415 Ctx.CostKind);
2416}
2417
2419 assert(is_contained(operands(), Op) && "Op must be an operand of the recipe");
2420 assert(Variant && "Variant not set");
2421 FunctionType *VFTy = Variant->getFunctionType();
2422 return all_of(enumerate(args()), [VFTy, &Op](const auto &Arg) {
2423 auto [Idx, V] = Arg;
2424 Type *ArgTy = VFTy->getParamType(Idx);
2425 return V != Op || ArgTy->isIntegerTy() || ArgTy->isFloatingPointTy() ||
2426 ArgTy->isPointerTy() || ArgTy->isByteTy();
2427 });
2428}
2429
2430#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2432 VPSlotTracker &SlotTracker) const {
2433 O << Indent << "WIDEN-CALL ";
2434
2435 Function *CalledFn = getCalledScalarFunction();
2436 if (CalledFn->getReturnType()->isVoidTy())
2437 O << "void ";
2438 else {
2440 O << " = ";
2441 }
2442
2443 O << "call";
2444 printFlags(O);
2445 printRetAttrs(O);
2446 O << "@" << CalledFn->getName() << "(";
2448 [&O, &SlotTracker, this](const auto &IndexedOp) {
2449 auto [Idx, Op] = IndexedOp;
2450 printParamAttrs(O, Idx);
2451 Op->printAsOperand(O, SlotTracker);
2452 });
2453 O << ")";
2454
2455 O << " (using library function";
2456 if (Variant->hasName())
2457 O << ": " << Variant->getName();
2458 O << ")";
2459}
2460#endif
2461
2463 assert(State.VF.isVector() && "not widening");
2464
2465 SmallVector<Type *, 2> TysForDecl;
2466 // Add return type if intrinsic is overloaded on it.
2467 if (isVectorIntrinsicWithOverloadTypeAtArg(VectorIntrinsicID, -1,
2468 State.TTI)) {
2469 Type *RetTy = toVectorizedTy(getScalarType(), State.VF);
2470 ArrayRef<Type *> ContainedTys = getContainedTypes(RetTy);
2471 for (auto [Idx, Ty] : enumerate(ContainedTys)) {
2473 Idx, State.TTI))
2474 TysForDecl.push_back(Ty);
2475 }
2476 }
2478 for (const auto &I : enumerate(operands())) {
2479 // Some intrinsics have a scalar argument - don't replace it with a
2480 // vector.
2481 Value *Arg;
2482 if (isVectorIntrinsicWithScalarOpAtArg(VectorIntrinsicID, I.index(),
2483 State.TTI))
2484 Arg = State.get(I.value(), VPLane(0));
2485 else
2486 Arg = State.get(I.value(), usesFirstLaneOnly(I.value()));
2487 if (isVectorIntrinsicWithOverloadTypeAtArg(VectorIntrinsicID, I.index(),
2488 State.TTI))
2489 TysForDecl.push_back(Arg->getType());
2490 Args.push_back(Arg);
2491 }
2492
2493 // Use vector version of the intrinsic.
2494 Module *M = State.Builder.getModule();
2495 Function *VectorF =
2496 Intrinsic::getOrInsertDeclaration(M, VectorIntrinsicID, TysForDecl);
2497 assert(VectorF &&
2498 "Can't retrieve vector intrinsic or vector-predication intrinsics.");
2499
2500 CallInst *V = State.Builder.CreateCall(VectorF, Args);
2501
2502 applyFlags(*V);
2503 applyMetadata(*V);
2504
2505 return V;
2506}
2507
2509 CallInst *V = createVectorCall(State);
2510 if (!V->getType()->isVoidTy())
2511 State.set(this, V);
2512}
2513
2516 const VPRecipeWithIRFlags &R, ElementCount VF, VPCostContext &Ctx) {
2517 Type *ScalarRetTy = R.getScalarType();
2518 // Skip the reverse operation cost for the mask.
2519 // FIXME: Remove this once redundant mask reverse operations can be eliminated
2520 // by VPlanTransforms::cse before cost computation.
2521 if (ID == Intrinsic::experimental_vp_reverse && ScalarRetTy->isIntegerTy(1))
2522 return InstructionCost(0);
2523
2524 // Some backends analyze intrinsic arguments to determine cost. Use the
2525 // underlying value for the operand if it has one. Otherwise try to use the
2526 // operand of the underlying call instruction, if there is one. Otherwise
2527 // clear Arguments.
2528 // TODO: Rework TTI interface to be independent of concrete IR values.
2530 for (const auto &[Idx, Op] : enumerate(Operands)) {
2531 auto *V = Op->getUnderlyingValue();
2532 if (!V) {
2533 if (auto *UI = dyn_cast_or_null<CallBase>(R.getUnderlyingValue())) {
2534 Arguments.push_back(UI->getArgOperand(Idx));
2535 continue;
2536 }
2537 Arguments.clear();
2538 break;
2539 }
2540 Arguments.push_back(V);
2541 }
2542
2543 Type *RetTy = VF.isVector() ? toVectorizedTy(ScalarRetTy, VF) : ScalarRetTy;
2544 SmallVector<Type *> ParamTys =
2545 map_to_vector(Operands, [&](const VPValue *Op) {
2546 return toVectorTy(Op->getScalarType(), VF);
2547 });
2548
2550 for (const VPValue *Op : Operands) {
2551 if (isa<VPWidenRecipe>(Op) &&
2554 break;
2555 }
2556 if (auto *WidenIntrinsic = dyn_cast<VPWidenIntrinsicRecipe>(Op)) {
2557 if (is_contained({Intrinsic::umin, Intrinsic::umax, Intrinsic::smin,
2558 Intrinsic::smax},
2559 WidenIntrinsic->getVectorIntrinsicID())) {
2561 break;
2562 }
2563 }
2564 }
2565
2566 // TODO: Rework TTI interface to avoid reliance on underlying IntrinsicInst.
2567 IntrinsicCostAttributes CostAttrs(
2568 ID, RetTy, Arguments, ParamTys, R.getFastMathFlagsOrNone(),
2569 dyn_cast_or_null<IntrinsicInst>(R.getUnderlyingValue()),
2571 return Ctx.TTI.getIntrinsicInstrCost(CostAttrs, Ctx.CostKind);
2572}
2573
2575 VPCostContext &Ctx) const {
2576 return computeCallCost(VectorIntrinsicID, operands(), *this, VF, Ctx);
2577}
2578
2580 return Intrinsic::getBaseName(VectorIntrinsicID);
2581}
2582
2584 assert(is_contained(operands(), Op) && "Op must be an operand of the recipe");
2585 return all_of(enumerate(operands()), [this, &Op](const auto &X) {
2586 auto [Idx, V] = X;
2588 Idx, nullptr);
2589 });
2590}
2591
2592#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2594 VPSlotTracker &SlotTracker) const {
2595 O << Indent << "WIDEN-INTRINSIC ";
2596 if (getScalarType()->isVoidTy()) {
2597 O << "void ";
2598 } else {
2600 O << " = ";
2601 }
2602
2603 O << "call";
2604 printFlags(O);
2605 O << getIntrinsicName() << "(";
2607 O << ")";
2608}
2609#endif
2610
2612 CallInst *MemI = createVectorCall(State);
2614 MemI->getContext(), Alignment));
2615 if (!MemI->getType()->isVoidTy())
2616 State.set(this, MemI);
2617}
2618
2621 assert(MaskPos && "Expected a memory intrinsic with a valid mask position");
2622 return getOperand(*MaskPos);
2623}
2624
2627 assert(PtrPos && "Expected a memory intrinsic with a valid pointer position");
2628 return *PtrPos;
2629}
2630
2632 Type *DataTy;
2634 DataTy = getOperand(*DataPos)->getScalarType();
2635 else
2636 DataTy = getScalarType();
2637 assert(!DataTy->isVoidTy() && "Expected a non-void data type");
2638 return toVectorTy(DataTy, VF);
2639}
2640
2642 Intrinsic::ID IID, Type *Ty, bool IsMasked, Align Alignment,
2643 VPCostContext &Ctx) {
2644 return Ctx.TTI.getMemIntrinsicInstrCost(
2645 MemIntrinsicCostAttributes(IID, Ty, /*Ptr=*/nullptr, IsMasked, Alignment),
2646 Ctx.CostKind);
2647}
2648
2655
2657 IRBuilderBase &Builder = State.Builder;
2658
2659 Value *Address = State.get(getOperand(0));
2660 Value *IncAmt = State.get(getOperand(1), /*NeedsSingleScalar=*/true);
2661 VectorType *VTy = cast<VectorType>(Address->getType());
2662
2663 // The histogram intrinsic requires a mask even if the recipe doesn't;
2664 // if the mask operand was omitted then all lanes should be executed and
2665 // we just need to synthesize an all-true mask.
2666 Value *Mask = nullptr;
2667 if (VPValue *VPMask = getMask())
2668 Mask = State.get(VPMask);
2669 else
2670 Mask =
2671 Builder.CreateVectorSplat(VTy->getElementCount(), Builder.getInt1(1));
2672
2673 // If this is a subtract, we want to invert the increment amount and use
2674 // the histogram_add intrinsic.
2675 if (mustNegateIncrement())
2676 IncAmt = Builder.CreateNeg(IncAmt);
2677
2678 Instruction *HistogramInst = State.Builder.CreateIntrinsicWithoutFolding(
2679 getHistogramIntrinsicID(), {VTy, IncAmt->getType()},
2680 {Address, IncAmt, Mask});
2681 applyMetadata(*HistogramInst);
2682}
2683
2684Intrinsic::ID VPHistogramRecipe::getHistogramIntrinsicID() const {
2685 switch (UpdateKind) {
2688 return Intrinsic::experimental_vector_histogram_add;
2690 return Intrinsic::experimental_vector_histogram_uadd_sat;
2692 return Intrinsic::experimental_vector_histogram_umax;
2694 return Intrinsic::experimental_vector_histogram_umin;
2695 }
2696 llvm_unreachable("Unknown HistogramUpdateKind");
2697}
2698
2700 VPCostContext &Ctx) const {
2701 // FIXME: Take the gather and scatter into account as well. For now we're
2702 // generating the same cost as the fallback path, but we'll likely
2703 // need to create a new TTI method for determining the cost, including
2704 // whether we can use base + vec-of-smaller-indices or just
2705 // vec-of-pointers.
2706 assert(VF.isVector() && "Invalid VF for histogram cost");
2707 Type *AddressTy = getOperand(0)->getScalarType();
2708 VPValue *IncAmt = getOperand(1);
2709 Type *IncTy = IncAmt->getScalarType();
2710 VectorType *VTy = VectorType::get(IncTy, VF);
2711
2712 // For umin/umax, there's no multiplication — the increment value is compared
2713 // directly. For add/sub/uadd.sat, assume that a non-constant update value
2714 // (or a constant != 1) requires a multiply.
2716 if (!match(IncAmt, m_One()) && UpdateKind != HistogramUpdateKind::UMax &&
2717 UpdateKind != HistogramUpdateKind::UMin)
2718 MulCost =
2719 Ctx.TTI.getArithmeticInstrCost(Instruction::Mul, VTy, Ctx.CostKind);
2720
2721 // Find the cost of the histogram operation itself.
2722 Type *PtrTy = VectorType::get(AddressTy, VF);
2723 Type *MaskTy = VectorType::get(Type::getInt1Ty(Ctx.LLVMCtx), VF);
2724 IntrinsicCostAttributes ICA(getHistogramIntrinsicID(),
2725 Type::getVoidTy(Ctx.LLVMCtx),
2726 {PtrTy, IncTy, MaskTy});
2727
2728 // The histogram intrinsic's TTI cost already includes the update operation
2729 // (load + update + store), so no separate UpdateCost is needed.
2730 return Ctx.TTI.getIntrinsicInstrCost(ICA, Ctx.CostKind) + MulCost;
2731}
2732
2733#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2735 VPSlotTracker &SlotTracker) const {
2736 O << Indent << "WIDEN-HISTOGRAM buckets: ";
2738
2739 switch (UpdateKind) {
2741 O << ", inc: ";
2742 break;
2744 O << ", dec: ";
2745 break;
2747 O << ", saturated inc: ";
2748 break;
2750 O << ", max: ";
2751 break;
2753 O << ", min: ";
2754 break;
2755 }
2757
2758 if (VPValue *Mask = getMask()) {
2759 O << ", mask: ";
2760 Mask->printAsOperand(O, SlotTracker);
2761 }
2762}
2763#endif
2764
2765VPIRFlags::FastMathFlagsTy::FastMathFlagsTy(const FastMathFlags &FMF) {
2766 AllowReassoc = FMF.allowReassoc();
2767 NoNaNs = FMF.noNaNs();
2768 NoInfs = FMF.noInfs();
2769 NoSignedZeros = FMF.noSignedZeros();
2770 AllowReciprocal = FMF.allowReciprocal();
2771 AllowContract = FMF.allowContract();
2772 ApproxFunc = FMF.approxFunc();
2773}
2774
2775VPIRFlags VPIRFlags::getDefaultFlags(unsigned Opcode, Type *ResultTy) {
2776 switch (Opcode) {
2777 case Instruction::Add:
2778 case Instruction::Sub:
2779 case Instruction::Mul:
2780 case Instruction::Shl:
2782 return WrapFlagsTy(false, false);
2783 case Instruction::Trunc:
2784 return TruncFlagsTy(false, false);
2785 case Instruction::Or:
2786 return DisjointFlagsTy(false);
2787 case Instruction::AShr:
2788 case Instruction::LShr:
2789 case Instruction::UDiv:
2790 case Instruction::SDiv:
2791 return ExactFlagsTy(false);
2792 case Instruction::GetElementPtr:
2795 return GEPNoWrapFlags::none();
2796 case Instruction::ZExt:
2797 case Instruction::UIToFP:
2798 return NonNegFlagsTy(false);
2799 case Instruction::FAdd:
2800 case Instruction::FSub:
2801 case Instruction::FMul:
2802 case Instruction::FDiv:
2803 case Instruction::FRem:
2804 case Instruction::FNeg:
2805 case Instruction::FPExt:
2806 case Instruction::FPTrunc:
2807 return FastMathFlags();
2808 case Instruction::Select:
2809 case Instruction::PHI:
2810 case Instruction::Call:
2811 // Selects, phis and calls only have fast-math flags if they have a
2812 // supported floating-point result type.
2814 return FastMathFlags();
2815 return VPIRFlags();
2816 case Instruction::ICmp:
2817 case Instruction::FCmp:
2819 llvm_unreachable("opcode requires explicit flags");
2820 default:
2821 return VPIRFlags();
2822 }
2823}
2824
2825#if !defined(NDEBUG)
2826bool VPIRFlags::flagsValidForOpcode(unsigned Opcode) const {
2827 switch (OpType) {
2828 case OperationType::OverflowingBinOp:
2829 return Opcode == Instruction::Add || Opcode == Instruction::Sub ||
2830 Opcode == Instruction::Mul || Opcode == Instruction::Shl ||
2831 Opcode == VPInstruction::VPInstruction::CanonicalIVIncrementForPart;
2832 case OperationType::Trunc:
2833 return Opcode == Instruction::Trunc;
2834 case OperationType::DisjointOp:
2835 return Opcode == Instruction::Or;
2836 case OperationType::PossiblyExactOp:
2837 return Opcode == Instruction::AShr || Opcode == Instruction::LShr ||
2838 Opcode == Instruction::UDiv || Opcode == Instruction::SDiv;
2839 case OperationType::GEPOp:
2840 return Opcode == Instruction::GetElementPtr ||
2841 Opcode == VPInstruction::PtrAdd ||
2842 Opcode == VPInstruction::WidePtrAdd;
2843 case OperationType::FPMathOp:
2844 return Opcode == Instruction::Call || Opcode == Instruction::FAdd ||
2845 Opcode == Instruction::FMul || Opcode == Instruction::FSub ||
2846 Opcode == Instruction::FNeg || Opcode == Instruction::FDiv ||
2847 Opcode == Instruction::FRem || Opcode == Instruction::FPExt ||
2848 Opcode == Instruction::FPTrunc || Opcode == Instruction::PHI ||
2849 Opcode == Instruction::Select || Opcode == Instruction::SIToFP ||
2850 Opcode == Instruction::UIToFP ||
2851 Opcode == VPInstruction::WideIVStep ||
2853 case OperationType::FCmp:
2854 return Opcode == Instruction::FCmp;
2855 case OperationType::NonNegOp:
2856 return Opcode == Instruction::ZExt || Opcode == Instruction::UIToFP;
2857 case OperationType::Cmp:
2858 return Opcode == Instruction::FCmp || Opcode == Instruction::ICmp;
2859 case OperationType::ReductionOp:
2861 case OperationType::Other:
2862 return true;
2863 }
2864 llvm_unreachable("Unknown OperationType enum");
2865}
2866
2868 Type *ResultTy) const {
2869 // Handle opcodes without default flags.
2870 if (Opcode == Instruction::ICmp)
2871 return OpType == OperationType::Cmp;
2872 if (Opcode == Instruction::FCmp)
2873 return OpType == OperationType::FCmp;
2875 return OpType == OperationType::ReductionOp;
2876
2877 OperationType Required = getDefaultFlags(Opcode, ResultTy).OpType;
2878 return Required == OperationType::Other || Required == OpType;
2879}
2880#endif
2881
2882#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2883static void printRecurrenceKind(raw_ostream &OS, const RecurKind &Kind) {
2884 switch (Kind) {
2885 case RecurKind::None:
2886 OS << "none";
2887 break;
2888 case RecurKind::Add:
2889 OS << "add";
2890 break;
2891 case RecurKind::Sub:
2892 OS << "sub";
2893 break;
2895 OS << "add-chain-with-subs";
2896 break;
2897 case RecurKind::Mul:
2898 OS << "mul";
2899 break;
2900 case RecurKind::Or:
2901 OS << "or";
2902 break;
2903 case RecurKind::And:
2904 OS << "and";
2905 break;
2906 case RecurKind::Xor:
2907 OS << "xor";
2908 break;
2909 case RecurKind::SMin:
2910 OS << "smin";
2911 break;
2912 case RecurKind::SMax:
2913 OS << "smax";
2914 break;
2915 case RecurKind::UMin:
2916 OS << "umin";
2917 break;
2918 case RecurKind::UMax:
2919 OS << "umax";
2920 break;
2921 case RecurKind::FAdd:
2922 OS << "fadd";
2923 break;
2925 OS << "fadd-chain-with-subs";
2926 break;
2927 case RecurKind::FSub:
2928 OS << "fsub";
2929 break;
2930 case RecurKind::FMul:
2931 OS << "fmul";
2932 break;
2933 case RecurKind::FMin:
2934 OS << "fmin";
2935 break;
2936 case RecurKind::FMax:
2937 OS << "fmax";
2938 break;
2939 case RecurKind::FMinNum:
2940 OS << "fminnum";
2941 break;
2942 case RecurKind::FMaxNum:
2943 OS << "fmaxnum";
2944 break;
2946 OS << "fminimum";
2947 break;
2949 OS << "fmaximum";
2950 break;
2952 OS << "fminimumnum";
2953 break;
2955 OS << "fmaximumnum";
2956 break;
2957 case RecurKind::FMulAdd:
2958 OS << "fmuladd";
2959 break;
2960 case RecurKind::AnyOf:
2961 OS << "any-of";
2962 break;
2963 case RecurKind::FindIV:
2964 OS << "find-iv";
2965 break;
2967 OS << "find-last";
2968 break;
2969 }
2970}
2971
2973 switch (OpType) {
2974 case OperationType::Cmp:
2976 break;
2977 case OperationType::FCmp:
2980 break;
2981 case OperationType::DisjointOp:
2982 if (DisjointFlags.IsDisjoint)
2983 O << " disjoint";
2984 break;
2985 case OperationType::PossiblyExactOp:
2986 if (ExactFlags.IsExact)
2987 O << " exact";
2988 break;
2989 case OperationType::OverflowingBinOp:
2990 if (WrapFlags.HasNUW)
2991 O << " nuw";
2992 if (WrapFlags.HasNSW)
2993 O << " nsw";
2994 break;
2995 case OperationType::Trunc:
2996 if (TruncFlags.HasNUW)
2997 O << " nuw";
2998 if (TruncFlags.HasNSW)
2999 O << " nsw";
3000 break;
3001 case OperationType::FPMathOp:
3003 break;
3004 case OperationType::GEPOp: {
3006 if (Flags.isInBounds())
3007 O << " inbounds";
3008 else if (Flags.hasNoUnsignedSignedWrap())
3009 O << " nusw";
3010 if (Flags.hasNoUnsignedWrap())
3011 O << " nuw";
3012 break;
3013 }
3014 case OperationType::NonNegOp:
3015 if (NonNegFlags.NonNeg)
3016 O << " nneg";
3017 break;
3018 case OperationType::ReductionOp: {
3019 O << " (";
3021 if (isReductionInLoop())
3022 O << ", in-loop";
3023 if (isReductionOrdered())
3024 O << ", ordered";
3025 O << ")";
3027 break;
3028 }
3029 case OperationType::Other:
3030 break;
3031 }
3032 O << " ";
3033}
3034#endif
3035
3037 auto &Builder = State.Builder;
3038 switch (Opcode) {
3039 case Instruction::Call:
3040 case Instruction::UncondBr:
3041 case Instruction::CondBr:
3042 case Instruction::PHI:
3043 case Instruction::GetElementPtr:
3044 llvm_unreachable("This instruction is handled by a different recipe.");
3045 case Instruction::UDiv:
3046 case Instruction::SDiv:
3047 case Instruction::SRem:
3048 case Instruction::URem:
3049 case Instruction::Add:
3050 case Instruction::FAdd:
3051 case Instruction::Sub:
3052 case Instruction::FSub:
3053 case Instruction::FNeg:
3054 case Instruction::Mul:
3055 case Instruction::FMul:
3056 case Instruction::FDiv:
3057 case Instruction::FRem:
3058 case Instruction::Shl:
3059 case Instruction::LShr:
3060 case Instruction::AShr:
3061 case Instruction::And:
3062 case Instruction::Or:
3063 case Instruction::Xor: {
3064 // Just widen unops and binops.
3066 for (VPValue *VPOp : operands())
3067 Ops.push_back(State.get(VPOp));
3068
3069 Value *V = Builder.CreateNAryOp(Opcode, Ops);
3070
3071 if (auto *VecOp = dyn_cast<Instruction>(V)) {
3072 applyFlags(*VecOp);
3073 applyMetadata(*VecOp);
3074 }
3075
3076 // Use this vector value for all users of the original instruction.
3077 State.set(this, V);
3078 break;
3079 }
3080 case Instruction::ExtractValue: {
3081 Value *Op = State.get(getOperand(0));
3082 Value *Extract =
3083 Builder.CreateExtractValue(Op, getExtractValueIndices(operands()));
3084 State.set(this, Extract);
3085 break;
3086 }
3087 case Instruction::Freeze: {
3088 Value *Op = State.get(getOperand(0));
3089 Value *Freeze = Builder.CreateFreeze(Op);
3090 State.set(this, Freeze);
3091 break;
3092 }
3093 case Instruction::ICmp:
3094 case Instruction::FCmp: {
3095 // Widen compares. Generate vector compares.
3096 bool FCmp = Opcode == Instruction::FCmp;
3097 Value *A = State.get(getOperand(0));
3098 Value *B = State.get(getOperand(1));
3099 Value *C = nullptr;
3100 if (FCmp) {
3101 C = Builder.CreateFCmp(getPredicate(), A, B);
3102 } else {
3103 C = Builder.CreateICmp(getPredicate(), A, B);
3104 }
3105 if (auto *I = dyn_cast<Instruction>(C)) {
3106 applyFlags(*I);
3107 applyMetadata(*I);
3108 }
3109 State.set(this, C);
3110 break;
3111 }
3112 case Instruction::Select: {
3113 VPValue *CondOp = getOperand(0);
3114 Value *Cond = State.get(CondOp, vputils::isSingleScalar(CondOp));
3115 Value *Op0 = State.get(getOperand(1));
3116 Value *Op1 = State.get(getOperand(2));
3117 Value *Sel = State.Builder.CreateSelect(Cond, Op0, Op1);
3118 State.set(this, Sel);
3119 if (auto *I = dyn_cast<Instruction>(Sel)) {
3121 applyFlags(*I);
3122 applyMetadata(*I);
3123 }
3124 break;
3125 }
3126 default:
3127 // This instruction is not vectorized by simple widening.
3128 LLVM_DEBUG(dbgs() << "LV: Found an unhandled opcode : "
3129 << Instruction::getOpcodeName(Opcode));
3130 llvm_unreachable("Unhandled instruction!");
3131 } // end of switch.
3132
3133#if !defined(NDEBUG)
3134 // Verify that VPlan type inference results agree with the type of the
3135 // generated values.
3136 assert(VectorType::get(this->getScalarType(), State.VF) ==
3137 State.get(this)->getType() &&
3138 "inferred type and type from generated instructions do not match");
3139#endif
3140}
3141
3143 VPCostContext &Ctx) const {
3144 switch (Opcode) {
3145 case Instruction::UDiv:
3146 case Instruction::SDiv:
3147 case Instruction::SRem:
3148 case Instruction::URem:
3149 // If the div/rem operation isn't safe to speculate and requires
3150 // predication, then the only way we can even create a vplan is to insert
3151 // a select on the second input operand to ensure we use the value of 1
3152 // for the inactive lanes. The select will be costed separately.
3153 case Instruction::FNeg:
3154 case Instruction::Add:
3155 case Instruction::FAdd:
3156 case Instruction::Sub:
3157 case Instruction::FSub:
3158 case Instruction::Mul:
3159 case Instruction::FMul:
3160 case Instruction::FDiv:
3161 case Instruction::FRem:
3162 case Instruction::Shl:
3163 case Instruction::LShr:
3164 case Instruction::AShr:
3165 case Instruction::And:
3166 case Instruction::Or:
3167 case Instruction::Xor:
3168 case Instruction::Freeze:
3169 case Instruction::ExtractValue:
3170 case Instruction::ICmp:
3171 case Instruction::FCmp:
3172 case Instruction::Select:
3173 return getCostForRecipeWithOpcode(getOpcode(), VF, Ctx);
3174 default:
3175 llvm_unreachable("Unsupported opcode for instruction");
3176 }
3177}
3178
3179#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3181 VPSlotTracker &SlotTracker) const {
3182 O << Indent << "WIDEN ";
3184 O << " = " << Instruction::getOpcodeName(Opcode);
3185 printFlags(O);
3187}
3188#endif
3189
3191 auto &Builder = State.Builder;
3192 /// Vectorize casts.
3193 assert(State.VF.isVector() && "Not vectorizing?");
3194 Type *DestTy = VectorType::get(getScalarType(), State.VF);
3195 VPValue *Op = getOperand(0);
3196 Value *A = State.get(Op);
3197 Value *Cast = Builder.CreateCast(Instruction::CastOps(Opcode), A, DestTy);
3198 State.set(this, Cast);
3199 if (auto *CastOp = dyn_cast<Instruction>(Cast)) {
3200 applyFlags(*CastOp);
3201 applyMetadata(*CastOp);
3202 }
3203}
3204
3209
3210#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3212 VPSlotTracker &SlotTracker) const {
3213 O << Indent << "WIDEN-CAST ";
3215 O << " = " << Instruction::getOpcodeName(Opcode);
3216 printFlags(O);
3218 O << " to " << *getScalarType();
3219}
3220#endif
3221
3223 VPCostContext &Ctx) const {
3224 return Ctx.TTI.getCFInstrCost(Instruction::PHI, Ctx.CostKind);
3225}
3226
3227#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3229 raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const {
3230 O << Indent;
3232 O << " = WIDEN-INDUCTION";
3233 printFlags(O);
3235
3236 if (isTruncated())
3237 O << " (truncated to " << *getScalarType() << ")";
3238}
3239#endif
3240
3242 // The step may be defined by a recipe in the preheader (e.g. if it requires
3243 // SCEV expansion), but for the canonical induction the step is required to be
3244 // 1, which is represented as live-in.
3245 return match(getStartValue(), m_ZeroInt()) &&
3246 match(getStepValue(), m_One()) &&
3247 getScalarType() == getRegion()->getCanonicalIVType();
3248}
3249
3252 VPCostContext &Ctx) const {
3253 // A widened induction generates a vector phi and increments it by the
3254 // splatted step each iteration.
3256 InstructionCost Cost = Ctx.TTI.getCFInstrCost(Instruction::PHI, Ctx.CostKind);
3257 Type *StepTy = getScalarType();
3258 unsigned IncOpc = ID.getKind() == InductionDescriptor::IK_IntInduction
3259 ? Instruction::Add
3260 : ID.getInductionOpcode();
3261 assert(IncOpc != Instruction::BinaryOpsEnd &&
3262 "induction must have a valid increment opcode");
3263 return Cost + Ctx.TTI.getArithmeticInstrCost(IncOpc, toVectorTy(StepTy, VF),
3264 Ctx.CostKind);
3265}
3266
3267/// Returns the ConstantFP \p V wraps, or nullptr if it does not wrap one.
3268static const ConstantFP *getConstantFP(const VPValue *V) {
3269 auto *C = dyn_cast<VPConstant>(V);
3270 return C ? dyn_cast<ConstantFP>(C->getConstant()) : nullptr;
3271}
3272
3274 VPCostContext &Ctx) const {
3275 // The cost model for this is modelled on expandVPDerivedIV in
3276 // VPlanTransforms.cpp. In order to avoid overly pessimistic costs that can
3277 // negatively affect vectorization it takes into account any expected
3278 // simplifications that happen in simplifyRecipe.
3279 switch (getInductionKind()) {
3280 default:
3281 // TODO: Compute cost for remaining kinds.
3282 break;
3284 // There are currently no tests that expose a path where all lanes are
3285 // used, so it's better to bail out for now.
3286 if (!vputils::onlyFirstLaneUsed(this))
3287 break;
3288
3289 // Start off by assuming we need both mul and add, then refine this.
3290 bool NeedsMul = true, NeedsAdd = true, NeedsShl = false;
3291
3292 // If the start value is zero the add gets folded away.
3293 if (auto *StartC = dyn_cast<VPConstantInt>(getStartValue()))
3294 NeedsAdd = !StartC->isZero();
3295
3296 // For some values of step the arithmetic changes:
3297 // 1. A step of 1 requires no operation.
3298 // 2. A step of -1 requires a negate.
3299 // 3. A power-of-2 step will use a shl, instead of a mul.
3300 Type *StepTy = getStepValue()->getScalarType();
3302 if (auto *StepC = dyn_cast<VPConstantInt>(getStepValue())) {
3303 if (StepC->isOne())
3304 NeedsMul = false;
3305 else if (StepC->getAPInt().isAllOnes()) {
3306 // This will most likely end up as a negate in simplifyRecipe, and
3307 // the negate will be combined with the add to make a sub.
3308 // NOTE: This is perhaps an invalid assumption that the cost of an
3309 // 'add' is the same as a 'sub'.
3310 NeedsMul = false;
3311 NeedsAdd = true;
3312 } else if (StepC->getAPInt().isPowerOf2()) {
3313 // This will most likely end up as a shift-left in simplifyRecipe
3314 NeedsMul = false;
3315 NeedsShl = true;
3316 }
3317 }
3318
3319 // Add the cost of the conversion from index to step type if the index
3320 // will be used.
3321 Type *IndexTy = getIndex()->getScalarType();
3322 unsigned StepTySize = StepTy->getScalarSizeInBits();
3323 unsigned IndexTySize = IndexTy->getScalarSizeInBits();
3324 if ((NeedsAdd || NeedsMul || NeedsShl) && StepTySize != IndexTySize) {
3325 unsigned CastOpc =
3326 StepTySize < IndexTySize ? Instruction::Trunc : Instruction::ZExt;
3327 Cost += Ctx.TTI.getCastInstrCost(
3328 CastOpc, StepTy, IndexTy, TTI::CastContextHint::None, Ctx.CostKind);
3329 }
3330
3331 if (NeedsMul)
3332 Cost += Ctx.TTI.getArithmeticInstrCost(Instruction::Mul, StepTy,
3333 Ctx.CostKind);
3334 if (NeedsShl)
3335 Cost += Ctx.TTI.getArithmeticInstrCost(
3336 Instruction::Shl, StepTy, Ctx.CostKind,
3337 {TargetTransformInfo::OK_AnyValue, TargetTransformInfo::OP_None},
3338 {TargetTransformInfo::OK_UniformConstantValue,
3339 TargetTransformInfo::OP_None});
3340 if (NeedsAdd)
3341 Cost += Ctx.TTI.getArithmeticInstrCost(Instruction::Add, StepTy,
3342 Ctx.CostKind);
3343 return Cost;
3344 }
3346 // There are currently no tests that expose a path where all lanes are
3347 // used, so it's better to bail out for now.
3348 if (!vputils::onlyFirstLaneUsed(this))
3349 break;
3350
3351 // Unlike the integer case, converting the index to the FP step type is
3352 // unavoidable: the index is always the integer canonical IV, so this
3353 // cast is never folded away.
3354 Type *StepTy = getStepValue()->getScalarType();
3355 Type *IndexTy = getIndex()->getScalarType();
3357 Ctx.TTI.getCastInstrCost(Instruction::UIToFP, StepTy, IndexTy,
3358 TTI::CastContextHint::None, Ctx.CostKind);
3359
3360 // If the step is 1.0, the multiply is an exact identity and gets folded
3361 // away, independent of fast-math flags.
3362 const ConstantFP *StepC = getConstantFP(getStepValue());
3363 bool NeedsMul = !StepC || !StepC->isOne();
3364
3365 // "fadd -0.0, X" folds to X unconditionally, but "fadd 0.0, X" only folds
3366 // to X without nsz if X can be proven to never be -0.0, which we cannot, as
3367 // Step may be -0.0.
3368 // TODO: Consider fast-math flags when they are available in
3369 // VPDerivedIVRecipe.
3370 const ConstantFP *StartC = getConstantFP(getStartValue());
3371 bool AddFolds = getFPBinOp()->getOpcode() == Instruction::FAdd && StartC &&
3372 StartC->isZero() && (StartC->isNegZero() || !NeedsMul);
3373
3374 if (NeedsMul)
3375 Cost += Ctx.TTI.getArithmeticInstrCost(Instruction::FMul, StepTy,
3376 Ctx.CostKind);
3377 if (!AddFolds)
3378 Cost += Ctx.TTI.getArithmeticInstrCost(getFPBinOp()->getOpcode(), StepTy,
3379 Ctx.CostKind);
3380 return Cost;
3381 }
3382 }
3383
3384 return 0;
3385}
3386
3387#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3389 VPSlotTracker &SlotTracker) const {
3390 O << Indent;
3392 O << " = DERIVED-IV";
3393 printFlags(O);
3394 getStartValue()->printAsOperand(O, SlotTracker);
3395 O << " + ";
3396 getOperand(1)->printAsOperand(O, SlotTracker);
3397 O << " * ";
3398 getStepValue()->printAsOperand(O, SlotTracker);
3399}
3400#endif
3401
3405
3407 VPCostContext &Ctx) const {
3408 Type *BaseIVTy = getOperand(0)->getScalarType();
3409 assert((BaseIVTy->isIntegerTy() || BaseIVTy->isFloatingPointTy()) &&
3410 "VPScalarIVStepsRecipe is only created for integer and FP inductions");
3411
3412 // If only the first lane is used, then there won't be any code that remains
3413 // in the loop for the first unrolled part.
3415 return 0;
3416
3417 // If the vector body executes at most once, the canonical IV is a constant
3418 // and every lane's step folds away with it.
3419 if (VPCostContext::executesAtMostOnce(*getParent()->getPlan(), VF))
3420 return 0;
3421
3422 // Typically the operations are:
3423 // 1. Add the start index to each lane value.
3424 // 2. Multiply the start index by the step.
3425 // 3. Add the scaled start index to base IV.
3426 // Any code generated for 1 and 2 should be loop invariant and therefore
3427 // hoisted out of the loop. We only need to add on the cost of 3.
3429 if (BaseIVTy->isFloatingPointTy()) {
3430 // Unlike the integer case, the users of an FP induction cannot be re-based
3431 // on a common value, so each lane needs its own FAdd/FSub.
3432 assert(!VF.isScalable() &&
3433 "FP scalar steps for all lanes are only created for fixed VFs");
3434 Cost = Ctx.TTI.getArithmeticInstrCost(InductionOpcode, BaseIVTy,
3435 Ctx.CostKind) *
3436 (VF.getFixedValue() - 1);
3437 } else {
3438 // Given the users of VPScalarIVStepsRecipe tend to be scalarized GEPs, i.e.
3439 // %add1 = add i32 %iv, 0
3440 // %add2 = add i32 %iv, 1
3441 // %gep1 = getelementptr i8, ptr %p, i32 %add1
3442 // %gep2 = getelementptr i8, ptr %p, i32 %add2
3443 // it's very likely that these GEPs will all be rewritten to have a common
3444 // base such that what's left is just
3445 // %base_gep = getelementptr i8, ptr %p, i32 %iv
3446 // %gep1 = getelementptr i8, ptr %base_gep, i32 0
3447 // %gep2 = getelementptr i8, ptr %base_gep, i32 1
3448 // Therefore, in reality the cost is somewhere betwen 1*AddCost and
3449 // (NumLanes - 1) * AddCost. For now, assume the cost of a single add.
3450 Cost = Ctx.TTI.getArithmeticInstrCost(Instruction::Add, BaseIVTy,
3451 Ctx.CostKind);
3452 }
3453
3454 // If the steps are generated inside a replicate region, scale by execution
3455 // probability.
3456 const VPRegionBlock *Region = getRegion();
3457 if (Region && Region->isReplicator())
3458 Cost /= Ctx.getCostDivisor(
3459 Region->getEntryBranchOnMask()->getExecutionFrequency());
3460 return Cost;
3461}
3462
3464 // Fast-math-flags propagate from the original induction instruction.
3465 IRBuilder<>::FastMathFlagGuard FMFG(State.Builder);
3466 State.Builder.setFastMathFlags(getFastMathFlagsOrNone());
3467
3468 /// Compute scalar induction steps. \p ScalarIV is the scalar induction
3469 /// variable on which to base the steps, \p Step is the size of the step.
3470
3471 Value *BaseIV = State.get(getOperand(0), VPLane(0));
3472 Value *Step = State.get(getStepValue(), VPLane(0));
3473 IRBuilderBase &Builder = State.Builder;
3474
3475 // Ensure step has the same type as that of scalar IV.
3476 Type *BaseIVTy = BaseIV->getType()->getScalarType();
3477 assert(BaseIVTy == Step->getType() && "Types of BaseIV and Step must match!");
3478
3479 // We build scalar steps for both integer and floating-point induction
3480 // variables. Here, we determine the kind of arithmetic we will perform.
3483 if (BaseIVTy->isIntegerTy()) {
3484 AddOp = Instruction::Add;
3485 MulOp = Instruction::Mul;
3486 } else {
3487 AddOp = InductionOpcode;
3488 MulOp = Instruction::FMul;
3489 }
3490
3491 // Lanes other than the first have been materialized as separate
3492 // single-scalar recipes by replicateByVF, each with its own start index.
3493 assert((vputils::onlyFirstLaneUsed(this) || State.VF.isScalar()) &&
3494 "must have been replicated by VF");
3495 Value *StartIdx = getStartIndex() ? State.get(getStartIndex(), true)
3496 : Constant::getNullValue(BaseIVTy);
3497 auto *Mul = Builder.CreateBinOp(MulOp, StartIdx, Step);
3498 auto *Add = Builder.CreateBinOp(AddOp, BaseIV, Mul);
3499 State.set(this, Add, VPLane(0));
3500}
3501
3502#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3504 VPSlotTracker &SlotTracker) const {
3505 O << Indent;
3507 O << " = SCALAR-STEPS ";
3509}
3510#endif
3511
3513 assert(is_contained(operands(), Op) && "Op must be an operand of the recipe");
3515}
3516
3518 assert(State.VF.isVector() && "not widening");
3519 auto Ops = map_to_vector(operands(), [&](VPValue *Op) {
3520 return State.get(Op, vputils::isSingleScalar(Op));
3521 });
3522 auto *GEP =
3523 State.Builder.CreateGEP(getSourceElementType(), Ops.front(),
3524 drop_begin(Ops), "wide.gep", getGEPNoWrapFlags());
3525 State.set(this, GEP, vputils::isSingleScalar(this));
3526}
3527
3528#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3530 VPSlotTracker &SlotTracker) const {
3531 O << Indent << "WIDEN-GEP ";
3533 O << " = getelementptr";
3534 printFlags(O);
3536}
3537#endif
3538
3540 assert(!getOffset() && "Unexpected offset operand");
3541 VPBuilder Builder(this);
3542 VPlan &Plan = *getParent()->getPlan();
3543 VPValue *VFVal = getVFValue();
3544 const DataLayout &DL = Plan.getDataLayout();
3545 Type *IndexTy = DL.getIndexType(this->getScalarType());
3546 VPValue *Stride =
3547 Plan.getConstantInt(IndexTy, getStride(), /*IsSigned=*/true);
3548 VPValue *VF =
3549 Builder.createScalarZExtOrTrunc(VFVal, IndexTy, DebugLoc::getUnknown());
3550
3551 // Offset for Part0 = Offset0 = Stride * (VF - 1).
3552 VPInstruction *VFMinusOne =
3553 Builder.createSub(VF, Plan.getConstantInt(IndexTy, 1u),
3554 DebugLoc::getUnknown(), "", {true, true});
3555 VPInstruction *Offset0 =
3556 Builder.createOverflowingOp(Instruction::Mul, {VFMinusOne, Stride});
3557
3558 // Offset for PartN = Offset0 + Part * Stride * VF.
3559 VPValue *PartxStride =
3560 Plan.getConstantInt(IndexTy, Part * getStride(), /*IsSigned=*/true);
3561 VPValue *Offset = Builder.createAdd(
3562 Offset0,
3563 Builder.createOverflowingOp(Instruction::Mul, {PartxStride, VF}));
3565}
3566
3568 auto &Builder = State.Builder;
3569 assert(getOffset() && "Expected prior materialization of offset");
3570 Value *Ptr = State.get(getPointer(), true);
3571 Value *Offset = State.get(getOffset(), true);
3572 Value *ResultPtr = Builder.CreateGEP(getSourceElementType(), Ptr, Offset, "",
3574 State.set(this, ResultPtr, /*IsScalar*/ true);
3575}
3576
3577#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3579 VPSlotTracker &SlotTracker) const {
3580 O << Indent;
3582 O << " = vector-end-pointer";
3583 printFlags(O);
3584 getSourceElementType()->print(O);
3585 O << ", ";
3587}
3588#endif
3589
3591 assert(getVFxPart() &&
3592 "Expected prior simplification of recipe without VFxPart");
3593
3594 auto &Builder = State.Builder;
3595 Value *Ptr = State.get(getOperand(0), VPLane(0));
3596 Value *Offset = State.get(getVFxPart(), true);
3597 // TODO: Expand to VPInstruction to support constant folding.
3598 if (!match(getStride(), m_One())) {
3599 Value *Stride = Builder.CreateZExtOrTrunc(State.get(getStride(), true),
3600 Offset->getType());
3601 Offset = Builder.CreateMul(Offset, Stride);
3602 }
3603 Value *ResultPtr = Builder.CreateGEP(getSourceElementType(), Ptr, Offset, "",
3605 State.set(this, ResultPtr, /*IsScalar*/ true);
3606}
3607
3608#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3610 VPSlotTracker &SlotTracker) const {
3611 O << Indent;
3613 O << " = vector-pointer";
3614 printFlags(O);
3615 getSourceElementType()->print(O);
3616 O << ", ";
3618}
3619#endif
3620
3622 VPCostContext &Ctx) const {
3623 // A blend will be expanded to a select VPInstruction, which will generate a
3624 // scalar select if only the first lane is used.
3626 VF = ElementCount::getFixed(1);
3627
3628 Type *ResultTy = toVectorTy(this->getScalarType(), VF);
3629 Type *CmpTy = toVectorTy(Type::getInt1Ty(Ctx.LLVMCtx), VF);
3630
3632 for (unsigned I = 1, E = getNumIncomingValues(); I != E; ++I) {
3633 CmpPredicate Pred;
3634 if (!match(getMask(I), m_Cmp(Pred, m_VPValue(), m_VPValue())))
3635 Pred = getScalarType()->isFloatingPointTy() ? CmpInst::BAD_FCMP_PREDICATE
3637 Cost += Ctx.TTI.getCmpSelInstrCost(Instruction::Select, ResultTy, CmpTy,
3638 Pred, Ctx.CostKind);
3639 }
3640 return Cost;
3641}
3642
3643#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3645 VPSlotTracker &SlotTracker) const {
3646 O << Indent << "BLEND ";
3648 O << " =";
3649 printFlags(O);
3650 if (getNumIncomingValues() == 1) {
3651 // Not a User of any mask: not really blending, this is a
3652 // single-predecessor phi.
3653 getIncomingValue(0)->printAsOperand(O, SlotTracker);
3654 } else {
3655 for (unsigned I = 0, E = getNumIncomingValues(); I < E; ++I) {
3656 if (I != 0)
3657 O << " ";
3658 getIncomingValue(I)->printAsOperand(O, SlotTracker);
3659 if (I == 0 && isNormalized())
3660 continue;
3661 O << "/";
3662 getMask(I)->printAsOperand(O, SlotTracker);
3663 }
3664 }
3665}
3666#endif
3667
3671 "In-loop AnyOf reductions aren't currently supported");
3672 // Propagate the fast-math flags carried by the underlying instruction.
3673 IRBuilderBase::FastMathFlagGuard FMFGuard(State.Builder);
3674 State.Builder.setFastMathFlags(getFastMathFlagsOrNone());
3675 Value *NewVecOp = State.get(getVecOp());
3676 if (VPValue *Cond = getCondOp()) {
3677 Value *NewCond = State.get(Cond, State.VF.isScalar());
3678 VectorType *VecTy = dyn_cast<VectorType>(NewVecOp->getType());
3679 Type *ElementTy = VecTy ? VecTy->getElementType() : NewVecOp->getType();
3680
3681 Value *Start =
3683 if (State.VF.isVector())
3684 Start = State.Builder.CreateVectorSplat(VecTy->getElementCount(), Start);
3685
3686 Value *Select = State.Builder.CreateSelect(NewCond, NewVecOp, Start);
3687 NewVecOp = Select;
3688 }
3689 Value *NewRed;
3690 Value *NextInChain;
3691 if (isOrdered()) {
3692 Value *PrevInChain = State.get(getChainOp(), /*NeedsSingleScalar=*/true);
3693 if (State.VF.isVector())
3694 NewRed =
3695 createOrderedReduction(State.Builder, Kind, NewVecOp, PrevInChain);
3696 else
3697 NewRed = State.Builder.CreateBinOp(
3699 PrevInChain, NewVecOp);
3700 PrevInChain = NewRed;
3701 NextInChain = NewRed;
3702 } else if (isPartialReduction()) {
3703 assert((Kind == RecurKind::Add || Kind == RecurKind::FAdd) &&
3704 "Unexpected partial reduction kind");
3705 Value *PrevInChain = State.get(getChainOp(), /*NeedsSingleScalar=*/false);
3706 NewRed = State.Builder.CreateIntrinsic(
3707 PrevInChain->getType(),
3708 Kind == RecurKind::Add ? Intrinsic::vector_partial_reduce_add
3709 : Intrinsic::vector_partial_reduce_fadd,
3710 {PrevInChain, NewVecOp}, State.Builder.getFastMathFlags(),
3711 "partial.reduce");
3712 PrevInChain = NewRed;
3713 NextInChain = NewRed;
3714 } else {
3715 assert(isInLoop() &&
3716 "The reduction must either be ordered, partial or in-loop");
3717 Value *PrevInChain = State.get(getChainOp(), /*NeedsSingleScalar=*/true);
3718 NewRed = createSimpleReduction(State.Builder, NewVecOp, Kind);
3720 NextInChain = createMinMaxOp(State.Builder, Kind, NewRed, PrevInChain);
3721 else
3722 NextInChain = State.Builder.CreateBinOp(
3724 PrevInChain, NewRed);
3725 }
3726 State.set(this, NextInChain, /*IsScalar*/ !isPartialReduction());
3727}
3728
3730
3731 assert(State.VF.isVector() &&
3732 "Shouldn't generate VPReductionEVLRecipe with scalar VF");
3733 auto &Builder = State.Builder;
3734 // Propagate the fast-math flags carried by the underlying instruction.
3735 IRBuilderBase::FastMathFlagGuard FMFGuard(Builder);
3736 Builder.setFastMathFlags(getFastMathFlagsOrNone());
3737
3739 Value *Prev =
3740 State.get(getChainOp(), /*NeedsSingleScalar=*/!isPartialReduction());
3741 Value *VecOp = State.get(getVecOp());
3742 Value *EVL = State.get(getEVL(), VPLane(0));
3743
3744 Value *Mask;
3745 if (VPValue *CondOp = getCondOp())
3746 Mask = State.get(CondOp);
3747 else
3748 Mask = Builder.CreateVectorSplat(State.VF, Builder.getTrue());
3749
3750 Value *NewRed;
3751 if (isPartialReduction()) {
3752 // For partial reductions, we need to generate a predicated select
3753 // (vp.merge) since `@llvm.vector.partial.reduce()` doesn't have a vector
3754 // predicated version.
3755 VectorType *VecTy = cast<VectorType>(VecOp->getType());
3756 Value *Identity = getRecurrenceIdentity(Kind, VecTy->getElementType(),
3758 Identity =
3759 State.Builder.CreateVectorSplat(VecTy->getElementCount(), Identity);
3760
3761 // TODO: Calculate the predicate cost for the partial reduction.
3762 Value *NewVecOp = State.Builder.CreateIntrinsic(
3763 VecTy, Intrinsic::vp_merge, {Mask, VecOp, Identity, EVL});
3764 assert((Kind == RecurKind::Add || Kind == RecurKind::FAdd) &&
3765 "Unexpected partial reduction kind");
3766 NewRed = State.Builder.CreateIntrinsic(
3767 Prev->getType(),
3768 Kind == RecurKind::Add ? Intrinsic::vector_partial_reduce_add
3769 : Intrinsic::vector_partial_reduce_fadd,
3770 {Prev, NewVecOp}, State.Builder.getFastMathFlags(), "partial.reduce");
3771 } else if (isOrdered()) {
3772 NewRed = createOrderedReduction(Builder, Kind, VecOp, Prev, Mask, EVL);
3773 } else {
3774 NewRed = createSimpleReduction(Builder, VecOp, Kind, Mask, EVL);
3776 NewRed = createMinMaxOp(Builder, Kind, NewRed, Prev);
3777 else
3778 NewRed = Builder.CreateBinOp(
3780 Prev);
3781 }
3782 State.set(this, NewRed, !isPartialReduction());
3783}
3784
3786 VPCostContext &Ctx) const {
3787 RecurKind RdxKind = getRecurrenceKind();
3788 Type *ElementTy = this->getScalarType();
3789 auto *VectorTy = cast<VectorType>(toVectorTy(ElementTy, VF));
3790 unsigned Opcode = RecurrenceDescriptor::getOpcode(RdxKind);
3792 std::optional<FastMathFlags> OptionalFMF =
3793 ElementTy->isFloatingPointTy() ? std::make_optional(FMFs) : std::nullopt;
3794
3795 if (isPartialReduction()) {
3796 InstructionCost CondCost = 0;
3797 if (isConditional()) {
3799 auto *CondTy =
3801 CondCost = Ctx.TTI.getCmpSelInstrCost(Instruction::Select, VectorTy,
3802 CondTy, Pred, Ctx.CostKind);
3803 }
3804 return CondCost + Ctx.TTI.getPartialReductionCost(
3805 Opcode, ElementTy, nullptr, ElementTy, VF,
3806 TTI::PR_None, TTI::PR_None, {}, Ctx.CostKind,
3807 OptionalFMF);
3808 }
3809
3810 // TODO: Support any-of reductions.
3811 assert(
3813 Ctx.Opts.force_target_instruction_cost) &&
3814 "Any-of reduction not implemented in VPlan-based cost model currently.");
3815
3816 // Note that TTI should model the cost of moving result to the scalar register
3817 // and the BinOp cost in the getMinMaxReductionCost().
3820 return Ctx.TTI.getMinMaxReductionCost(Id, VectorTy, FMFs, Ctx.CostKind);
3821 }
3822
3823 // Note that TTI should model the cost of moving result to the scalar register
3824 // and the BinOp cost in the getArithmeticReductionCost().
3825 return Ctx.TTI.getArithmeticReductionCost(Opcode, VectorTy, OptionalFMF,
3826 Ctx.CostKind);
3827}
3828
3830 ExpressionTypes ExpressionType,
3831 ArrayRef<VPSingleDefRecipe *> ExpressionRecipes)
3832 : VPSingleDefRecipe(VPRecipeBase::VPExpressionSC, {},
3833 [&]() {
3834 if (ExpressionType == ExpressionTypes::FoldedVPMerge)
3835 return ExpressionRecipes.back()->getScalarType();
3837 ExpressionRecipes.back())
3838 ->getChainOp()
3839 ->getScalarType();
3840 }()),
3841 ExpressionRecipes(ExpressionRecipes), ExpressionType(ExpressionType) {
3842 assert(!ExpressionRecipes.empty() && "Nothing to combine?");
3843 assert(
3844 none_of(ExpressionRecipes,
3845 [](VPSingleDefRecipe *R) { return R->mayHaveSideEffects(); }) &&
3846 "expression cannot contain recipes with side-effects");
3847
3848 // Maintain a copy of the expression recipes as a set of users.
3849 SmallPtrSet<VPUser *, 4> ExpressionRecipesAsSetOfUsers;
3850 for (auto *R : ExpressionRecipes)
3851 ExpressionRecipesAsSetOfUsers.insert(R);
3852
3853 // Recipes in the expression, except the last one, must only be used by
3854 // (other) recipes inside the expression. If there are other users, external
3855 // to the expression, use a clone of the recipe for external users.
3856 for (VPSingleDefRecipe *R : reverse(ExpressionRecipes)) {
3857 if (R != ExpressionRecipes.back() &&
3858 any_of(R->users(), [&ExpressionRecipesAsSetOfUsers](VPUser *U) {
3859 return !ExpressionRecipesAsSetOfUsers.contains(U);
3860 })) {
3861 // There are users outside of the expression. Clone the recipe and use the
3862 // clone those external users.
3863 VPSingleDefRecipe *CopyForExtUsers = R->clone();
3864 R->replaceUsesWithIf(CopyForExtUsers,
3865 [&ExpressionRecipesAsSetOfUsers](VPUser *U) {
3866 return !ExpressionRecipesAsSetOfUsers.contains(U);
3867 });
3868 CopyForExtUsers->insertBefore(R);
3869 }
3870 if (R->getParent())
3871 R->removeFromParent();
3872 }
3873
3874 // Internalize all external operands to the expression recipes. To do so,
3875 // create new temporary VPValues for all operands defined by a recipe outside
3876 // the expression. The original operands are added as operands of the
3877 // VPExpressionRecipe itself.
3878 for (auto *R : ExpressionRecipes) {
3879 for (const auto &[Idx, Op] : enumerate(R->operands())) {
3880 auto *Def = Op->getDefiningRecipe();
3881 if (Def && ExpressionRecipesAsSetOfUsers.contains(Def))
3882 continue;
3883 addOperand(Op);
3884 LiveInPlaceholders.push_back(new VPSymbolicValue(Op->getScalarType()));
3885 }
3886 }
3887
3888 // Replace each external operand with the first one created for it in
3889 // LiveInPlaceholders.
3890 for (auto *R : ExpressionRecipes)
3891 for (auto const &[LiveIn, Tmp] : zip(operands(), LiveInPlaceholders))
3892 R->replaceUsesOfWith(LiveIn, Tmp);
3893}
3894
3896 for (auto *R : ExpressionRecipes)
3897 // Since the list could contain duplicates, make sure the recipe hasn't
3898 // already been inserted.
3899 if (!R->getParent())
3900 R->insertBefore(this);
3901
3902 for (const auto &[Idx, Op] : enumerate(operands()))
3903 LiveInPlaceholders[Idx]->replaceAllUsesWith(Op);
3904
3905 replaceAllUsesWith(ExpressionRecipes.back());
3906 SmallVector<VPSingleDefRecipe *> DecomposedRecipes(ExpressionRecipes);
3907 ExpressionRecipes.clear();
3908 return DecomposedRecipes;
3909}
3910
3912 assert(is_contained(operands(), Op) && "Op must be an operand of the recipe");
3913 // The last operand of a folded operation is the vp.merge EVL.
3914 if (ExpressionType == ExpressionTypes::FoldedVPMerge &&
3915 Op == getLastOperand()) {
3916 assert(match(Op, m_EVL(m_VPValue())) &&
3917 "Expected an explicit vector length recipe");
3918 return true;
3919 }
3920
3921 return false;
3922}
3923
3925 VPCostContext &Ctx) const {
3926 // The last recipes in the chain will be optimized away, so igonre the cost.
3927 if (ExpressionType == ExpressionTypes::FoldedVPMerge) {
3929 for (auto *R : drop_end(ExpressionRecipes))
3930 Cost += R->cost(VF, Ctx);
3931 return Cost;
3932 }
3933
3934 Type *RedTy = this->getScalarType();
3935 auto *SrcVecTy =
3937 unsigned Opcode = RecurrenceDescriptor::getOpcode(
3938 cast<VPReductionRecipe>(ExpressionRecipes.back())->getRecurrenceKind());
3939 switch (ExpressionType) {
3940 case ExpressionTypes::NegatedExtendedReduction:
3941 assert((Opcode == Instruction::Add || Opcode == Instruction::FAdd) &&
3942 "Unexpected opcode");
3943 Opcode = Opcode == Instruction::Add ? Instruction::Sub : Instruction::FSub;
3944 [[fallthrough]];
3945 case ExpressionTypes::ExtendedReduction: {
3946 auto *RedR = cast<VPReductionRecipe>(ExpressionRecipes.back());
3947 auto *ExtR = cast<VPWidenCastRecipe>(ExpressionRecipes[0]);
3948
3949 if (RedR->isPartialReduction())
3950 return Ctx.TTI.getPartialReductionCost(
3951 Opcode, getOperand(0)->getScalarType(), nullptr, RedTy, VF,
3953 TargetTransformInfo::PR_None, std::nullopt, Ctx.CostKind,
3954 RedTy->isFloatingPointTy()
3955 ? std::optional{RedR->getFastMathFlagsOrNone()}
3956 : std::nullopt);
3957 else if (!RedTy->isFloatingPointTy())
3958 // TTI::getExtendedReductionCost only supports integer types.
3959 return Ctx.TTI.getExtendedReductionCost(
3960 Opcode, ExtR->getOpcode() == Instruction::ZExt, RedTy, SrcVecTy,
3961 std::nullopt, Ctx.CostKind);
3962 else
3964 }
3965 case ExpressionTypes::MulAccReduction:
3966 return Ctx.TTI.getMulAccReductionCost(false, Opcode, RedTy, SrcVecTy,
3967 Ctx.CostKind);
3968
3969 case ExpressionTypes::ExtNegatedMulAccReduction:
3970 switch (Opcode) {
3971 case Instruction::Add:
3972 Opcode = Instruction::Sub;
3973 break;
3974 case Instruction::FAdd:
3975 Opcode = Instruction::FSub;
3976 break;
3977 default:
3978 llvm_unreachable("Unsupported opcode for ExtNegatedMulAccReduction");
3979 }
3980 [[fallthrough]];
3981 case ExpressionTypes::ExtMulAccReduction: {
3982 auto *RedR = cast<VPReductionRecipe>(ExpressionRecipes.back());
3983 if (RedR->isPartialReduction()) {
3984 auto *Ext0R = cast<VPWidenCastRecipe>(ExpressionRecipes[0]);
3985 auto *Ext1R = cast<VPWidenCastRecipe>(ExpressionRecipes[1]);
3986 auto *Mul = cast<VPWidenRecipe>(ExpressionRecipes[2]);
3987 return Ctx.TTI.getPartialReductionCost(
3988 Opcode, getOperand(0)->getScalarType(),
3989 getOperand(1)->getScalarType(), RedTy, VF,
3991 Ext0R->getOpcode()),
3993 Ext1R->getOpcode()),
3994 Mul->getOpcode(), Ctx.CostKind,
3995 RedTy->isFloatingPointTy()
3996 ? std::optional{RedR->getFastMathFlagsOrNone()}
3997 : std::nullopt);
3998 }
3999 assert(Opcode != Instruction::FSub && "Only integer types are supported");
4000 return Ctx.TTI.getMulAccReductionCost(
4001 cast<VPWidenCastRecipe>(ExpressionRecipes.front())->getOpcode() ==
4002 Instruction::ZExt,
4003 Opcode, RedTy, SrcVecTy, Ctx.CostKind);
4004 }
4005 case ExpressionTypes::FoldedVPMerge:
4006 llvm_unreachable("Folded vp.merge expression should be handled eariler");
4007 }
4008 llvm_unreachable("Unknown VPExpressionRecipe::ExpressionTypes enum");
4009}
4010
4012 return any_of(ExpressionRecipes, [](VPSingleDefRecipe *R) {
4013 return R->mayReadFromMemory() || R->mayWriteToMemory();
4014 });
4015}
4016
4018 assert(
4019 none_of(ExpressionRecipes,
4020 [](VPSingleDefRecipe *R) { return R->mayHaveSideEffects(); }) &&
4021 "expression cannot contain recipes with side-effects");
4022 return false;
4023}
4024
4026 auto *RR = dyn_cast<VPReductionRecipe>(ExpressionRecipes.back());
4027 return RR && !RR->isPartialReduction();
4028}
4029
4030#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4031
4033 VPSlotTracker &SlotTracker) const {
4034 O << Indent << "EXPRESSION ";
4036 O << " = ";
4037 if (ExpressionType == ExpressionTypes::FoldedVPMerge) {
4038 VPSingleDefRecipe *InLoopOp = ExpressionRecipes[0];
4039 unsigned NumInLoopOps = InLoopOp->getNumOperands();
4040 O << "vp.merge ";
4041 getOperand(NumInLoopOps)->printAsOperand(O, SlotTracker);
4042 O << ", ";
4043 auto PrintInLoopOperands = [&]() {
4044 O << "(";
4045 interleaveComma(make_range(op_begin(), op_begin() + NumInLoopOps), O,
4046 [&O, &SlotTracker](VPValue *Op) {
4047 Op->printAsOperand(O, SlotTracker);
4048 });
4049 O << ")";
4050 };
4051
4052 if (auto *WidenIntrinsic = dyn_cast<VPWidenIntrinsicRecipe>(InLoopOp)) {
4053 O << WidenIntrinsic->getIntrinsicName();
4054 WidenIntrinsic->printFlags(O);
4055 PrintInLoopOperands();
4056 } else if (auto *Widen = dyn_cast<VPWidenRecipe>(InLoopOp)) {
4057 O << Instruction::getOpcodeName(Widen->getOpcode());
4058 Widen->printFlags(O);
4059 PrintInLoopOperands();
4060 }
4061 O << ", ";
4062 interleaveComma(make_range(op_begin() + NumInLoopOps + 1,
4063 op_begin() + NumInLoopOps + 3),
4064 O, [&O, &SlotTracker](VPValue *Op) {
4065 Op->printAsOperand(O, SlotTracker);
4066 });
4067
4068 return;
4069 }
4070
4071 auto *Red = cast<VPReductionRecipe>(ExpressionRecipes.back());
4072 unsigned Opcode = RecurrenceDescriptor::getOpcode(Red->getRecurrenceKind());
4073 VPValue *Mask = getLastOperand();
4074 VPValue *EVL =
4076 ? getOperand(getNumOperands() - (Red->isConditional() ? 2 : 1))
4077 : nullptr;
4078 VPValue *RdxStart = getOperand(
4079 getNumOperands() - (Red->isConditional() ? 2 : 1) - (EVL ? 1 : 0));
4080 auto PrintEVLAndMask = [&]() {
4081 if (EVL) {
4082 O << ", ";
4083 EVL->printAsOperand(O, SlotTracker);
4084 }
4085 if (Red->isConditional()) {
4086 O << ", ";
4087 Mask->printAsOperand(O, SlotTracker);
4088 }
4089 };
4090
4091 switch (ExpressionType) {
4092 case ExpressionTypes::NegatedExtendedReduction:
4093 case ExpressionTypes::ExtendedReduction: {
4094 bool Negated = ExpressionType == ExpressionTypes::NegatedExtendedReduction;
4096 O << " + " << (Red->isPartialReduction() ? "partial." : "") << "reduce.";
4097 O << Instruction::getOpcodeName(Opcode) << " (";
4098 if (Negated)
4099 O << (Opcode == Instruction::Add ? "sub (0, " : "fneg(");
4101 if (Negated)
4102 O << ")";
4103 Red->printFlags(O);
4104
4105 auto *Ext0 = cast<VPWidenCastRecipe>(ExpressionRecipes[0]);
4106 O << Instruction::getOpcodeName(Ext0->getOpcode()) << " to "
4107 << *Ext0->getScalarType();
4108 PrintEVLAndMask();
4109 O << ")";
4110 break;
4111 }
4112 case ExpressionTypes::ExtNegatedMulAccReduction: {
4113 RdxStart->printAsOperand(O, SlotTracker);
4114 O << " + " << (Red->isPartialReduction() ? "partial." : "") << "reduce.";
4116 RecurrenceDescriptor::getOpcode(Red->getRecurrenceKind()))
4117 << " (sub (0, mul";
4118 auto *Mul = cast<VPWidenRecipe>(ExpressionRecipes[2]);
4119 Mul->printFlags(O);
4120 O << "(";
4122 auto *Ext0 = cast<VPWidenCastRecipe>(ExpressionRecipes[0]);
4123 O << " " << Instruction::getOpcodeName(Ext0->getOpcode()) << " to "
4124 << *Ext0->getScalarType() << "), (";
4126 auto *Ext1 = cast<VPWidenCastRecipe>(ExpressionRecipes[1]);
4127 O << " " << Instruction::getOpcodeName(Ext1->getOpcode()) << " to "
4128 << *Ext1->getScalarType() << ")";
4129 PrintEVLAndMask();
4130 O << "))";
4131 break;
4132 }
4133 case ExpressionTypes::MulAccReduction:
4134 case ExpressionTypes::ExtMulAccReduction: {
4135 RdxStart->printAsOperand(O, SlotTracker);
4136 O << " + " << (Red->isPartialReduction() ? "partial." : "") << "reduce.";
4138 RecurrenceDescriptor::getOpcode(Red->getRecurrenceKind()))
4139 << " (";
4140 O << "mul";
4141 bool IsExtended = ExpressionType == ExpressionTypes::ExtMulAccReduction;
4142 auto *Mul = cast<VPWidenRecipe>(IsExtended ? ExpressionRecipes[2]
4143 : ExpressionRecipes[0]);
4144 Mul->printFlags(O);
4145 if (IsExtended)
4146 O << "(";
4148 if (IsExtended) {
4149 auto *Ext0 = cast<VPWidenCastRecipe>(ExpressionRecipes[0]);
4150 O << " " << Instruction::getOpcodeName(Ext0->getOpcode()) << " to "
4151 << *Ext0->getScalarType() << "), (";
4152 } else {
4153 O << ", ";
4154 }
4156 if (IsExtended) {
4157 auto *Ext1 = cast<VPWidenCastRecipe>(ExpressionRecipes[1]);
4158 O << " " << Instruction::getOpcodeName(Ext1->getOpcode()) << " to "
4159 << *Ext1->getScalarType() << ")";
4160 }
4161 PrintEVLAndMask();
4162 O << ")";
4163 break;
4164 }
4165 default:
4166 llvm_unreachable("Unhandled VPExpressionRecipe::ExpressionTypes enum");
4167 }
4168}
4169
4171 VPSlotTracker &SlotTracker) const {
4172 if (isPartialReduction())
4173 O << Indent << "PARTIAL-REDUCE ";
4174 else
4175 O << Indent << "REDUCE ";
4177 O << " = ";
4179 O << " +";
4180 printFlags(O);
4181 O << " reduce.";
4183 O << " (";
4185 if (isConditional()) {
4186 O << ", ";
4188 }
4189 O << ")";
4190}
4191
4193 VPSlotTracker &SlotTracker) const {
4194 if (isPartialReduction())
4195 O << Indent << "PARTIAL-REDUCE ";
4196 else
4197 O << Indent << "REDUCE ";
4199 O << " = ";
4201 O << " +";
4202 printFlags(O);
4203 O << " vp.reduce."
4206 << " (";
4208 O << ", ";
4210 if (isConditional()) {
4211 O << ", ";
4213 }
4214 O << ")";
4215}
4216
4217#endif
4218
4220 assert(IsSingleScalar &&
4221 "VPReplicateRecipes must be unrolled before ::execute");
4222 auto *Instr = getUnderlyingInstr();
4223 Instruction *Cloned = Instr->clone();
4224 Type *ResultTy = getScalarType();
4225 if (!ResultTy->isVoidTy()) {
4226 Cloned->setName(Instr->getName() + ".cloned");
4227 // The operands of the replicate recipe may have been narrowed, resulting in
4228 // a narrower result type. Update the type of the cloned instruction to the
4229 // correct type.
4230 if (ResultTy != Cloned->getType())
4231 Cloned->mutateType(ResultTy);
4232 }
4233
4236 Cloned->dropPoisonGeneratingFlags();
4237 applyFlags(*Cloned);
4238 applyMetadata(*Cloned);
4239
4240 if (hasPredicate())
4241 cast<CmpInst>(Cloned)->setPredicate(getPredicate());
4242
4243 // Replace the operands of the cloned instructions with their scalar
4244 // equivalents in the new loop.
4245 for (unsigned Idx : seq(Cloned->getNumOperands()))
4246 Cloned->setOperand(Idx, State.get(getOperand(Idx), true));
4247
4248 // Place the cloned scalar in the new loop.
4249 State.Builder.Insert(Cloned);
4250
4251 State.set(this, Cloned, true);
4252
4253 // If we just cloned a new assumption, add it the assumption cache.
4254 if (auto *II = dyn_cast<AssumeInst>(Cloned))
4255 State.AC->registerAssumption(II);
4256}
4257
4258/// Returns a SCEV expression for \p Ptr if it is a pointer computation for
4259/// which the legacy cost model computes a SCEV expression when computing the
4260/// address cost. Computing SCEVs for VPValues is incomplete and returns
4261/// SCEVCouldNotCompute in cases the legacy cost model can compute SCEVs. In
4262/// those cases we fall back to the legacy cost model. Otherwise return nullptr.
4263static const SCEV *getAddressAccessSCEV(const VPValue *Ptr,
4265 const Loop *L) {
4266 const SCEV *Addr = vputils::getSCEVExprForVPValue(Ptr, PSE, L);
4267 if (isa<SCEVCouldNotCompute>(Addr))
4268 return Addr;
4269
4270 return vputils::isAddressSCEVForCost(Addr, *PSE.getSE(), L) ? Addr : nullptr;
4271}
4272
4274 VPCostContext &Ctx) const {
4276 // VPReplicateRecipe may be cloned as part of an existing VPlan-to-VPlan
4277 // transform, avoid computing their cost multiple times for now.
4278 Ctx.SkipCostComputation.insert(UI);
4279
4280 if (VF.isScalable() && !isSingleScalar())
4282
4283 switch (UI->getOpcode()) {
4284 case Instruction::Alloca:
4285 if (VF.isScalable())
4287 return Ctx.TTI.getArithmeticInstrCost(Instruction::Mul,
4288 this->getScalarType(), Ctx.CostKind);
4289 case Instruction::GetElementPtr:
4290 // We mark this instruction as zero-cost because the cost of GEPs in
4291 // vectorized code depends on whether the corresponding memory instruction
4292 // is scalarized or not. Therefore, we handle GEPs with the memory
4293 // instruction cost.
4294 return 0;
4295 case Instruction::Call: {
4296 auto *CalledFn = cast<Function>(getLastOperand()->getLiveInIRValue());
4297 Type *ResultTy = this->getScalarType();
4298 return computeCallCost(CalledFn, ResultTy, drop_end(operands()),
4299 isSingleScalar(), VF, Ctx);
4300 }
4301 case Instruction::FNeg:
4302 case Instruction::Add:
4303 case Instruction::Sub:
4304 case Instruction::FAdd:
4305 case Instruction::FSub:
4306 case Instruction::Mul:
4307 case Instruction::FMul:
4308 case Instruction::FDiv:
4309 case Instruction::FRem:
4310 case Instruction::Shl:
4311 case Instruction::LShr:
4312 case Instruction::AShr:
4313 case Instruction::And:
4314 case Instruction::Or:
4315 case Instruction::Xor:
4316 case Instruction::ICmp:
4317 case Instruction::FCmp:
4318 case Instruction::Freeze:
4320 Ctx) *
4321 (isSingleScalar() ? 1 : VF.getFixedValue());
4322 case Instruction::SDiv:
4323 case Instruction::UDiv:
4324 case Instruction::SRem:
4325 case Instruction::URem: {
4326 InstructionCost ScalarCost =
4328 if (isSingleScalar())
4329 return ScalarCost;
4330
4331 // If any of the operands is from a different replicate region and has its
4332 // cost skipped, it may have been forced to scalar. Fall back to legacy cost
4333 // model to avoid cost mis-match.
4334 if (any_of(operands(), [&Ctx, VF](VPValue *Op) {
4335 auto *PredR = dyn_cast<VPPredInstPHIRecipe>(Op);
4336 if (!PredR)
4337 return false;
4338 return Ctx.skipCostComputation(
4340 PredR->getOperand(0)->getUnderlyingValue()),
4341 VF.isVector());
4342 }))
4343 break;
4344
4345 ScalarCost = ScalarCost * VF.getFixedValue() +
4346 Ctx.getScalarizationOverhead(this->getScalarType(),
4347 to_vector(operands()), VF);
4348 // If the recipe is not predicated (i.e. not in a replicate region), return
4349 // the scalar cost. Otherwise handle predicated cost.
4350 const VPRegionBlock *ParentRegion = getRegion();
4351 if (!ParentRegion || !ParentRegion->isReplicator())
4352 return ScalarCost;
4353
4354 // Account for the phi nodes that we will create.
4355 ScalarCost += VF.getFixedValue() *
4356 Ctx.TTI.getCFInstrCost(Instruction::PHI, Ctx.CostKind);
4357 // Scale the cost by the probability of executing the predicated blocks.
4358 // This assumes the predicated block for each vector lane is equally
4359 // likely.
4360 ScalarCost /= Ctx.getCostDivisor(
4361 ParentRegion->getEntryBranchOnMask()->getExecutionFrequency());
4362 return ScalarCost;
4363 }
4364 case Instruction::Load:
4365 case Instruction::Store: {
4366 bool IsLoad = UI->getOpcode() == Instruction::Load;
4367 const VPValue *PtrOp = getOperand(!IsLoad);
4368 const SCEV *PtrSCEV = getAddressAccessSCEV(PtrOp, Ctx.PSE, Ctx.L);
4370 // Fall back to the legacy cost model, unless the access is single-scalar
4371 // (PtrSCEV is unused) or predicated (legacy cost includes the region).
4372 const VPRegionBlock *ParentRegion = getRegion();
4373 if (!isSingleScalar() && (!ParentRegion || !ParentRegion->isReplicator()))
4374 break;
4375 PtrSCEV = nullptr;
4376 }
4377
4378 Type *ValTy = (IsLoad ? this : getOperand(0))->getScalarType();
4379 Type *ScalarPtrTy = PtrOp->getScalarType();
4380 const Align Alignment = getLoadStoreAlignment(UI);
4381 unsigned AS = cast<PointerType>(ScalarPtrTy)->getAddressSpace();
4383 bool PreferVectorizedAddressing = Ctx.TTI.prefersVectorizedAddressing();
4384 bool UsedByLoadStoreAddress =
4385 !PreferVectorizedAddressing && vputils::isUsedByLoadStoreAddress(this);
4386 InstructionCost ScalarMemOpCost = Ctx.TTI.getMemoryOpCost(
4387 UI->getOpcode(), ValTy, Alignment, AS, Ctx.CostKind, OpInfo,
4388 UsedByLoadStoreAddress ? UI : nullptr);
4389
4390 Type *PtrTy = isSingleScalar() ? ScalarPtrTy : toVectorTy(ScalarPtrTy, VF);
4391 InstructionCost ScalarCost =
4392 ScalarMemOpCost +
4393 Ctx.TTI.getAddressComputationCost(
4394 PtrTy, UsedByLoadStoreAddress ? nullptr : Ctx.PSE.getSE(), PtrSCEV,
4395 Ctx.CostKind);
4396 if (isSingleScalar())
4397 return ScalarCost;
4398
4399 SmallVector<const VPValue *> OpsToScalarize;
4400 Type *ResultTy = Type::getVoidTy(PtrTy->getContext());
4401 // Set ResultTy and OpsToScalarize, if scalarization is needed. Currently we
4402 // don't assign scalarization overhead in general, if the target prefers
4403 // vectorized addressing or the loaded value is used as part of an address
4404 // of another load or store.
4405 if (!UsedByLoadStoreAddress) {
4406 bool EfficientVectorLoadStore =
4407 Ctx.TTI.supportsEfficientVectorElementLoadStore();
4408 if (!(IsLoad && !PreferVectorizedAddressing) &&
4409 !(!IsLoad && EfficientVectorLoadStore))
4410 append_range(OpsToScalarize, operands());
4411
4412 if (!EfficientVectorLoadStore)
4413 ResultTy = this->getScalarType();
4414 }
4415
4417 IsLoad ? TTI::VectorInstrContext::Load : TTI::VectorInstrContext::Store;
4419 (ScalarCost * VF.getFixedValue()) +
4420 Ctx.getScalarizationOverhead(ResultTy, OpsToScalarize, VF, VIC, true);
4421
4422 const VPRegionBlock *ParentRegion = getRegion();
4423 if (ParentRegion && ParentRegion->isReplicator()) {
4424 // The cost of the branches is accounted for by the replicate region.
4425 Cost /= Ctx.getCostDivisor(
4426 ParentRegion->getEntryBranchOnMask()->getExecutionFrequency());
4427
4428 if (Ctx.useEmulatedMaskMemRefHack(this, VF)) {
4429 // Artificially setting to a high enough value to practically disable
4430 // vectorization with such operations.
4431 return 3000000;
4432 }
4433 }
4434 return Cost;
4435 }
4436 case Instruction::BitCast:
4437 case Instruction::SExt:
4438 case Instruction::ZExt:
4439 case Instruction::FPToUI:
4440 case Instruction::FPToSI:
4441 case Instruction::FPExt:
4442 case Instruction::PtrToInt:
4443 case Instruction::PtrToAddr:
4444 case Instruction::IntToPtr:
4445 case Instruction::SIToFP:
4446 case Instruction::UIToFP:
4447 case Instruction::Trunc:
4448 case Instruction::FPTrunc:
4449 case Instruction::Select:
4450 case Instruction::AddrSpaceCast: {
4452 Ctx) *
4453 (isSingleScalar() ? 1 : VF.getFixedValue());
4454 }
4455 case Instruction::ExtractValue:
4456 return Ctx.TTI.getInsertExtractValueCost(getOpcode(), Ctx.CostKind);
4457 }
4458
4459 return Ctx.getLegacyCost(UI, VF);
4460}
4461
4463 Function *CalledFn, Type *ResultTy, ArrayRef<const VPValue *> ArgOps,
4464 bool IsSingleScalar, ElementCount VF, VPCostContext &Ctx) {
4466 ArgOps, [&](const VPValue *Op) { return Op->getScalarType(); });
4467
4468 Intrinsic::ID IntrinID = CalledFn->getIntrinsicID();
4469 auto GetIntrinsicCost = [&] {
4470 if (!IntrinID)
4472 return Ctx.TTI.getIntrinsicInstrCost(
4473 IntrinsicCostAttributes(IntrinID, ResultTy, Tys), Ctx.CostKind);
4474 };
4475
4476 if (IntrinID && VPCostContext::isFreeScalarIntrinsic(IntrinID)) {
4477 assert(GetIntrinsicCost() == 0 && "scalarizing intrinsic should be free");
4478 return 0;
4479 }
4480
4481 InstructionCost ScalarCallCost =
4482 Ctx.TTI.getCallInstrCost(CalledFn, ResultTy, Tys, Ctx.CostKind);
4483 if (IsSingleScalar) {
4484 ScalarCallCost = std::min(ScalarCallCost, GetIntrinsicCost());
4485 return ScalarCallCost;
4486 }
4487
4488 // Scalarization overhead is undefined for scalable VFs.
4489 if (VF.isScalable())
4491
4492 return ScalarCallCost * VF.getFixedValue() +
4493 Ctx.getScalarizationOverhead(ResultTy, ArgOps, VF);
4494}
4495
4496#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4498 VPSlotTracker &SlotTracker) const {
4499 O << Indent << (IsSingleScalar ? "CLONE " : "REPLICATE ");
4500
4501 if (!getScalarType()->isVoidTy()) {
4503 O << " = ";
4504 }
4505 if (auto *CB = dyn_cast<CallBase>(getUnderlyingInstr())) {
4506 O << "call";
4507 printFlags(O);
4508 O << "@" << CB->getCalledFunction()->getName() << "(";
4510 Op->printAsOperand(O, SlotTracker);
4511 });
4512 O << ")";
4513 } else {
4515 printFlags(O);
4517 }
4518
4519 // Find if the recipe is used by a widened recipe via an intervening
4520 // VPPredInstPHIRecipe. In this case, also pack the scalar values in a vector.
4521 if (any_of(users(), [](const VPUser *U) {
4522 if (auto *PredR = dyn_cast<VPPredInstPHIRecipe>(U))
4523 return !vputils::onlyScalarValuesUsed(PredR);
4524 return false;
4525 }))
4526 O << " (S->V)";
4527}
4528#endif
4529
4531 llvm_unreachable("recipe must be removed when dissolving replicate region");
4532}
4533
4535 VPCostContext &Ctx) const {
4536 // Replicating isn't supported for scalable vectors.
4537 if (VF.isScalable())
4539 auto *VecI1Ty = VectorType::get(Type::getInt1Ty(Ctx.LLVMCtx), VF);
4540 return Ctx.TTI.getScalarizationOverhead(
4541 VecI1Ty, APInt::getAllOnes(VF.getFixedValue()),
4542 /*Insert=*/false, /*Extract=*/true, Ctx.CostKind) +
4543 VF.getFixedValue() *
4544 Ctx.TTI.getCFInstrCost(Instruction::CondBr, Ctx.CostKind);
4545}
4546
4548 llvm_unreachable("recipe must be removed when dissolving replicate region");
4549}
4550
4551#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4553 VPSlotTracker &SlotTracker) const {
4554 O << Indent << "PHI-PREDICATED-INSTRUCTION ";
4556 O << " = ";
4558}
4559#endif
4560
4562const VPRecipeBase *VPWidenLoadRecipe::getAsRecipe() const { return this; }
4563
4566
4568const VPRecipeBase *VPWidenStoreRecipe::getAsRecipe() const { return this; }
4569
4572
4574 VPCostContext &Ctx) const {
4575 const VPRecipeBase *R = getAsRecipe();
4577 Type *ScalarTy = IsLoad ? cast<VPSingleDefRecipe>(R)->getScalarType()
4578 : R->getOperand(1)->getScalarType();
4579 Type *Ty = toVectorTy(ScalarTy, VF);
4580 unsigned AS =
4581 cast<PointerType>(getAddr()->getScalarType())->getAddressSpace();
4582 unsigned Opcode = IsLoad ? Instruction::Load : Instruction::Store;
4583
4584 if (!Consecutive) {
4585 // TODO: Using the original IR may not be accurate.
4586 // Currently, ARM will use the underlying IR to calculate gather/scatter
4587 // instruction cost.
4588 Type *PtrTy = getAddr()->getScalarType();
4589 const Value *Ptr = getAddr()->getUnderlyingValue();
4590
4591 // If the address value is uniform across all lanes, then the address can be
4592 // calculated with scalar type and broadcast.
4594 PtrTy = toVectorTy(PtrTy, VF);
4595
4596 unsigned IID = isa<VPWidenLoadRecipe>(R) ? Intrinsic::masked_gather
4597 : isa<VPWidenStoreRecipe>(R) ? Intrinsic::masked_scatter
4598 : isa<VPWidenLoadEVLRecipe>(R) ? Intrinsic::vp_gather
4599 : Intrinsic::vp_scatter;
4600 return Ctx.TTI.getAddressComputationCost(PtrTy, nullptr, nullptr,
4601 Ctx.CostKind) +
4602 Ctx.TTI.getMemIntrinsicInstrCost(
4604 &Ingredient),
4605 Ctx.CostKind);
4606 }
4607
4609 if (IsMasked) {
4610 unsigned IID = isa<VPWidenLoadRecipe>(R) ? Intrinsic::masked_load
4611 : Intrinsic::masked_store;
4612 Cost += Ctx.TTI.getMemIntrinsicInstrCost(
4613 MemIntrinsicCostAttributes(IID, Ty, Alignment, AS), Ctx.CostKind);
4614 } else {
4615 TTI::OperandValueInfo OpInfo = Ctx.getOperandInfo(
4617 : R->getOperand(1));
4618 Cost += Ctx.TTI.getMemoryOpCost(Opcode, Ty, Alignment, AS, Ctx.CostKind,
4619 OpInfo, &Ingredient);
4620 }
4621 return Cost;
4622}
4623
4625 Type *ScalarDataTy = getScalarType();
4626 auto *DataTy = VectorType::get(ScalarDataTy, State.VF);
4627 bool CreateGather = !isConsecutive();
4628
4629 auto &Builder = State.Builder;
4630 Value *Mask = nullptr;
4631 if (auto *VPMask = getMask())
4632 Mask = State.get(VPMask);
4633
4634 Value *Addr = State.get(getAddr(), /*NeedsSingleScalar=*/!CreateGather);
4635 Value *NewLI;
4636 if (CreateGather) {
4637 NewLI = Builder.CreateMaskedGather(DataTy, Addr, Alignment, Mask, nullptr,
4638 "wide.masked.gather");
4639 } else if (Mask) {
4640 NewLI =
4641 Builder.CreateMaskedLoad(DataTy, Addr, Alignment, Mask,
4642 PoisonValue::get(DataTy), "wide.masked.load");
4643 } else {
4644 NewLI = Builder.CreateAlignedLoad(DataTy, Addr, Alignment, "wide.load");
4645 }
4647 State.set(this, NewLI);
4648}
4649
4650#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4652 VPSlotTracker &SlotTracker) const {
4653 O << Indent << "WIDEN ";
4655 O << " = load ";
4657 O << ", align " << getAlign().value();
4658}
4659#endif
4660
4662 Type *ScalarDataTy = getScalarType();
4663 auto *DataTy = VectorType::get(ScalarDataTy, State.VF);
4664 bool CreateGather = !isConsecutive();
4665
4666 auto &Builder = State.Builder;
4667 CallInst *NewLI;
4668 Value *EVL = State.get(getEVL(), VPLane(0));
4669 Value *Addr = State.get(getAddr(), !CreateGather);
4670 Value *Mask = nullptr;
4671 if (VPValue *VPMask = getMask())
4672 Mask = State.get(VPMask);
4673 else
4674 Mask = Builder.CreateVectorSplat(State.VF, Builder.getTrue());
4675
4676 if (CreateGather) {
4677 NewLI = Builder.CreateIntrinsicWithoutFolding(DataTy, Intrinsic::vp_gather,
4678 {Addr, Mask, EVL}, nullptr,
4679 "wide.masked.gather");
4680 } else {
4681 NewLI = Builder.CreateIntrinsicWithoutFolding(
4682 DataTy, Intrinsic::vp_load, {Addr, Mask, EVL}, nullptr, "vp.op.load");
4683 }
4684 NewLI->addParamAttr(
4686 applyMetadata(*NewLI);
4687 State.set(this, NewLI);
4688}
4689
4691 VPCostContext &Ctx) const {
4692 if (!Consecutive || IsMasked)
4693 return VPWidenMemoryRecipe::computeCost(VF, Ctx);
4694
4695 // We need to use the getMemIntrinsicInstrCost() instead of getMemoryOpCost()
4696 // here because the EVL recipes using EVL to replace the tail mask. But in the
4697 // legacy model, it will always calculate the cost of mask.
4698 // TODO: Using getMemoryOpCost() instead of getMemIntrinsicInstrCost when we
4699 // don't need to compare to the legacy cost model.
4700 Type *Ty = toVectorTy(getScalarType(), VF);
4701 unsigned AS =
4702 cast<PointerType>(getAddr()->getScalarType())->getAddressSpace();
4703 return Ctx.TTI.getMemIntrinsicInstrCost(
4704 MemIntrinsicCostAttributes(Intrinsic::vp_load, Ty, Alignment, AS),
4705 Ctx.CostKind);
4706}
4707
4708#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4710 VPSlotTracker &SlotTracker) const {
4711 O << Indent << "WIDEN ";
4713 O << " = vp.load ";
4715 O << ", align " << getAlign().value();
4716}
4717#endif
4718
4720 VPValue *StoredVPValue = getStoredValue();
4721 bool CreateScatter = !isConsecutive();
4722
4723 auto &Builder = State.Builder;
4724
4725 Value *Mask = nullptr;
4726 if (auto *VPMask = getMask())
4727 Mask = State.get(VPMask);
4728
4729 Value *StoredVal = State.get(StoredVPValue);
4730 Value *Addr = State.get(getAddr(), /*NeedsSingleScalar=*/!CreateScatter);
4731 Instruction *NewSI = nullptr;
4732 if (CreateScatter)
4733 NewSI = Builder.CreateMaskedScatter(StoredVal, Addr, Alignment, Mask);
4734 else if (Mask)
4735 NewSI = Builder.CreateMaskedStore(StoredVal, Addr, Alignment, Mask);
4736 else
4737 NewSI = Builder.CreateAlignedStore(StoredVal, Addr, Alignment);
4738 applyMetadata(*NewSI);
4739}
4740
4741#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4743 VPSlotTracker &SlotTracker) const {
4744 O << Indent << "WIDEN store ";
4746 O << ", align " << getAlign().value();
4747}
4748#endif
4749
4751 VPValue *StoredValue = getStoredValue();
4752 bool CreateScatter = !isConsecutive();
4753
4754 auto &Builder = State.Builder;
4755
4756 CallInst *NewSI = nullptr;
4757 Value *StoredVal = State.get(StoredValue);
4758 Value *EVL = State.get(getEVL(), VPLane(0));
4759 Value *Mask = nullptr;
4760 if (VPValue *VPMask = getMask())
4761 Mask = State.get(VPMask);
4762 else
4763 Mask = Builder.CreateVectorSplat(State.VF, Builder.getTrue());
4764
4765 Value *Addr = State.get(getAddr(), !CreateScatter);
4766 if (CreateScatter) {
4767 NewSI = Builder.CreateIntrinsicWithoutFolding(
4768 Type::getVoidTy(EVL->getContext()), Intrinsic::vp_scatter,
4769 {StoredVal, Addr, Mask, EVL});
4770 } else {
4771 NewSI = Builder.CreateIntrinsicWithoutFolding(
4772 Type::getVoidTy(EVL->getContext()), Intrinsic::vp_store,
4773 {StoredVal, Addr, Mask, EVL});
4774 }
4775 NewSI->addParamAttr(
4777 applyMetadata(*NewSI);
4778}
4779
4781 VPCostContext &Ctx) const {
4782 if (!Consecutive || IsMasked)
4783 return VPWidenMemoryRecipe::computeCost(VF, Ctx);
4784
4785 // We need to use the getMemIntrinsicInstrCost() instead of getMemoryOpCost()
4786 // here because the EVL recipes using EVL to replace the tail mask. But in the
4787 // legacy model, it will always calculate the cost of mask.
4788 // TODO: Using getMemoryOpCost() instead of getMemIntrinsicInstrCost when we
4789 // don't need to compare to the legacy cost model.
4790 Type *Ty = toVectorTy(getStoredValue()->getScalarType(), VF);
4791 unsigned AS =
4792 cast<PointerType>(getAddr()->getScalarType())->getAddressSpace();
4793 return Ctx.TTI.getMemIntrinsicInstrCost(
4794 MemIntrinsicCostAttributes(Intrinsic::vp_store, Ty, Alignment, AS),
4795 Ctx.CostKind);
4796}
4797
4798#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4800 VPSlotTracker &SlotTracker) const {
4801 O << Indent << "WIDEN vp.store ";
4803 O << ", align " << getAlign().value();
4804}
4805#endif
4806
4808 VectorType *DstVTy, const DataLayout &DL) {
4809 // Verify that V is a vector type with same number of elements as DstVTy.
4810 auto VF = DstVTy->getElementCount();
4811 auto *SrcVecTy = cast<VectorType>(V->getType());
4812 assert(VF == SrcVecTy->getElementCount() && "Vector dimensions do not match");
4813 Type *SrcElemTy = SrcVecTy->getElementType();
4814 Type *DstElemTy = DstVTy->getElementType();
4815 assert((DL.getTypeSizeInBits(SrcElemTy) == DL.getTypeSizeInBits(DstElemTy)) &&
4816 "Vector elements must have same size");
4817
4818 // Do a direct cast if element types are castable.
4819 if (CastInst::isBitOrNoopPointerCastable(SrcElemTy, DstElemTy, DL)) {
4820 return Builder.CreateBitOrPointerCast(V, DstVTy);
4821 }
4822 // V cannot be directly casted to desired vector type.
4823 // May happen when V is a floating point vector but DstVTy is a vector of
4824 // pointers or vice-versa. Handle this using a two-step bitcast using an
4825 // intermediate Integer type for the bitcast i.e. Ptr <-> Int <-> Float.
4826 assert((DstElemTy->isPointerTy() != SrcElemTy->isPointerTy()) &&
4827 "Only one type should be a pointer type");
4828 assert((DstElemTy->isFloatingPointTy() != SrcElemTy->isFloatingPointTy()) &&
4829 "Only one type should be a floating point type");
4830 Type *IntTy =
4831 IntegerType::getIntNTy(V->getContext(), DL.getTypeSizeInBits(SrcElemTy));
4832 auto *VecIntTy = VectorType::get(IntTy, VF);
4833 Value *CastVal = Builder.CreateBitOrPointerCast(V, VecIntTy);
4834 return Builder.CreateBitOrPointerCast(CastVal, DstVTy);
4835}
4836
4837/// Return a vector containing interleaved elements from multiple
4838/// smaller input vectors.
4840 const Twine &Name) {
4841 unsigned Factor = Vals.size();
4842 assert(Factor > 1 && "Tried to interleave invalid number of vectors");
4843
4844 VectorType *VecTy = cast<VectorType>(Vals[0]->getType());
4845#ifndef NDEBUG
4846 for (Value *Val : Vals)
4847 assert(Val->getType() == VecTy && "Tried to interleave mismatched types");
4848#endif
4849
4850 // Scalable vectors cannot use arbitrary shufflevectors (only splats), so
4851 // must use intrinsics to interleave.
4852 if (VecTy->isScalableTy()) {
4853 assert(Factor <= 8 && "Unsupported interleave factor for scalable vectors");
4854 return Builder.CreateVectorInterleave(Vals, Name);
4855 }
4856
4857 // Fixed length. Start by concatenating all vectors into a wide vector.
4858 Value *WideVec = concatenateVectors(Builder, Vals);
4859
4860 // Interleave the elements into the wide vector.
4861 const unsigned NumElts = VecTy->getElementCount().getFixedValue();
4862 return Builder.CreateShuffleVector(
4863 WideVec, createInterleaveMask(NumElts, Factor), Name);
4864}
4865
4866// Try to vectorize the interleave group that \p Instr belongs to.
4867//
4868// E.g. Translate following interleaved load group (factor = 3):
4869// for (i = 0; i < N; i+=3) {
4870// R = Pic[i]; // Member of index 0
4871// G = Pic[i+1]; // Member of index 1
4872// B = Pic[i+2]; // Member of index 2
4873// ... // do something to R, G, B
4874// }
4875// To:
4876// %wide.vec = load <12 x i32> ; Read 4 tuples of R,G,B
4877// %R.vec = shuffle %wide.vec, poison, <0, 3, 6, 9> ; R elements
4878// %G.vec = shuffle %wide.vec, poison, <1, 4, 7, 10> ; G elements
4879// %B.vec = shuffle %wide.vec, poison, <2, 5, 8, 11> ; B elements
4880//
4881// Or translate following interleaved store group (factor = 3):
4882// for (i = 0; i < N; i+=3) {
4883// ... do something to R, G, B
4884// Pic[i] = R; // Member of index 0
4885// Pic[i+1] = G; // Member of index 1
4886// Pic[i+2] = B; // Member of index 2
4887// }
4888// To:
4889// %R_G.vec = shuffle %R.vec, %G.vec, <0, 1, 2, ..., 7>
4890// %B_U.vec = shuffle %B.vec, poison, <0, 1, 2, 3, u, u, u, u>
4891// %interleaved.vec = shuffle %R_G.vec, %B_U.vec,
4892// <0, 4, 8, 1, 5, 9, 2, 6, 10, 3, 7, 11> ; Interleave R,G,B elements
4893// store <12 x i32> %interleaved.vec ; Write 4 tuples of R,G,B
4895 assert((!needsMaskForGaps() || !State.VF.isScalable()) &&
4896 "Masking gaps for scalable vectors is not yet supported.");
4898 Instruction *Instr = Group->getInsertPos();
4899
4900 // Prepare for the vector type of the interleaved load/store.
4901 Type *ScalarTy = getLoadStoreType(Instr);
4902 unsigned InterleaveFactor = Group->getFactor();
4903 auto *VecTy = VectorType::get(ScalarTy, State.VF * InterleaveFactor);
4904
4905 VPValue *BlockInMask = getMask();
4906 VPValue *Addr = getAddr();
4907 Value *ResAddr = State.get(Addr, VPLane(0));
4908
4909 auto CreateGroupMask = [&BlockInMask, &State,
4910 &InterleaveFactor](Value *MaskForGaps) -> Value * {
4911 if (State.VF.isScalable()) {
4912 assert(!MaskForGaps && "Interleaved groups with gaps are not supported.");
4913 assert(InterleaveFactor <= 8 &&
4914 "Unsupported deinterleave factor for scalable vectors");
4915 auto *ResBlockInMask = State.get(BlockInMask);
4916 SmallVector<Value *> Ops(InterleaveFactor, ResBlockInMask);
4917 return interleaveVectors(State.Builder, Ops, "interleaved.mask");
4918 }
4919
4920 if (!BlockInMask)
4921 return MaskForGaps;
4922
4923 Value *ResBlockInMask = State.get(BlockInMask);
4924 Value *ShuffledMask = State.Builder.CreateShuffleVector(
4925 ResBlockInMask,
4926 createReplicatedMask(InterleaveFactor, State.VF.getFixedValue()),
4927 "interleaved.mask");
4928 return MaskForGaps ? State.Builder.CreateBinOp(Instruction::And,
4929 ShuffledMask, MaskForGaps)
4930 : ShuffledMask;
4931 };
4932
4933 const DataLayout &DL = Instr->getDataLayout();
4934 // Vectorize the interleaved load group.
4935 if (isa<LoadInst>(Instr)) {
4936 Value *MaskForGaps = nullptr;
4937 if (needsMaskForGaps()) {
4938 MaskForGaps =
4939 createBitMaskForGaps(State.Builder, State.VF.getFixedValue(), *Group);
4940 assert(MaskForGaps && "Mask for Gaps is required but it is null");
4941 }
4942
4943 Instruction *NewLoad;
4944 if (BlockInMask || MaskForGaps) {
4945 Value *GroupMask = CreateGroupMask(MaskForGaps);
4946 Value *PoisonVec = PoisonValue::get(VecTy);
4947 NewLoad = State.Builder.CreateMaskedLoad(VecTy, ResAddr,
4948 Group->getAlign(), GroupMask,
4949 PoisonVec, "wide.masked.vec");
4950 } else
4951 NewLoad = State.Builder.CreateAlignedLoad(VecTy, ResAddr,
4952 Group->getAlign(), "wide.vec");
4953 applyMetadata(*NewLoad);
4954 // TODO: Also manage existing metadata using VPIRMetadata.
4955 Group->addMetadata(NewLoad);
4956
4958 if (VecTy->isScalableTy()) {
4959 // Scalable vectors cannot use arbitrary shufflevectors (only splats),
4960 // so must use intrinsics to deinterleave.
4961 assert(InterleaveFactor <= 8 &&
4962 "Unsupported deinterleave factor for scalable vectors");
4963 NewLoad = State.Builder.CreateIntrinsicWithoutFolding(
4964 Intrinsic::getDeinterleaveIntrinsicID(InterleaveFactor),
4965 NewLoad->getType(), NewLoad,
4966 /*FMFSource=*/nullptr, "strided.vec");
4967 }
4968
4969 auto CreateStridedVector = [&InterleaveFactor, &State,
4970 &NewLoad](unsigned Index) -> Value * {
4971 assert(Index < InterleaveFactor && "Illegal group index");
4972 if (State.VF.isScalable())
4973 return State.Builder.CreateExtractValue(NewLoad, Index);
4974
4975 // For fixed length VF, use shuffle to extract the sub-vectors from the
4976 // wide load.
4977 auto StrideMask =
4978 createStrideMask(Index, InterleaveFactor, State.VF.getFixedValue());
4979 return State.Builder.CreateShuffleVector(NewLoad, StrideMask,
4980 "strided.vec");
4981 };
4982
4983 for (unsigned I = 0, J = 0; I < InterleaveFactor; ++I) {
4984 Instruction *Member = Group->getMember(I);
4985
4986 // Skip the gaps in the group.
4987 if (!Member)
4988 continue;
4989
4990 Value *StridedVec = CreateStridedVector(I);
4991
4992 // If this member has different type, cast the result type.
4993 if (Member->getType() != ScalarTy) {
4994 VectorType *OtherVTy = VectorType::get(Member->getType(), State.VF);
4995 StridedVec =
4996 createBitOrPointerCast(State.Builder, StridedVec, OtherVTy, DL);
4997 }
4998
4999 if (Group->isReverse())
5000 StridedVec = State.Builder.CreateVectorReverse(StridedVec, "reverse");
5001
5002 State.set(VPDefs[J], StridedVec);
5003 ++J;
5004 }
5005 return;
5006 }
5007
5008 // The sub vector type for current instruction.
5009 auto *SubVT = VectorType::get(ScalarTy, State.VF);
5010
5011 // Vectorize the interleaved store group.
5012 Value *MaskForGaps =
5013 createBitMaskForGaps(State.Builder, State.VF.getKnownMinValue(), *Group);
5014 assert(((MaskForGaps != nullptr) == needsMaskForGaps()) &&
5015 "Mismatch between NeedsMaskForGaps and MaskForGaps");
5016 ArrayRef<VPValue *> StoredValues = getStoredValues();
5017 // Collect the stored vector from each member.
5018 SmallVector<Value *, 4> StoredVecs;
5019 unsigned StoredIdx = 0;
5020 for (unsigned i = 0; i < InterleaveFactor; i++) {
5021 assert((Group->getMember(i) || MaskForGaps) &&
5022 "Fail to get a member from an interleaved store group");
5023 Instruction *Member = Group->getMember(i);
5024
5025 // Skip the gaps in the group.
5026 if (!Member) {
5027 Value *Undef = PoisonValue::get(SubVT);
5028 StoredVecs.push_back(Undef);
5029 continue;
5030 }
5031
5032 Value *StoredVec = State.get(StoredValues[StoredIdx]);
5033 ++StoredIdx;
5034
5035 if (Group->isReverse())
5036 StoredVec = State.Builder.CreateVectorReverse(StoredVec, "reverse");
5037
5038 // If this member has different type, cast it to a unified type.
5039
5040 if (StoredVec->getType() != SubVT)
5041 StoredVec = createBitOrPointerCast(State.Builder, StoredVec, SubVT, DL);
5042
5043 StoredVecs.push_back(StoredVec);
5044 }
5045
5046 // Interleave all the smaller vectors into one wider vector.
5047 Value *IVec = interleaveVectors(State.Builder, StoredVecs, "interleaved.vec");
5048 Instruction *NewStoreInstr;
5049 if (BlockInMask || MaskForGaps) {
5050 Value *GroupMask = CreateGroupMask(MaskForGaps);
5051 NewStoreInstr = State.Builder.CreateMaskedStore(
5052 IVec, ResAddr, Group->getAlign(), GroupMask);
5053 } else
5054 NewStoreInstr =
5055 State.Builder.CreateAlignedStore(IVec, ResAddr, Group->getAlign());
5056
5057 applyMetadata(*NewStoreInstr);
5058 // TODO: Also manage existing metadata using VPIRMetadata.
5059 Group->addMetadata(NewStoreInstr);
5060}
5061
5062#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
5064 VPSlotTracker &SlotTracker) const {
5066 O << Indent << "INTERLEAVE-GROUP with factor " << IG->getFactor() << ", ";
5068 VPValue *Mask = getMask();
5069 if (Mask) {
5070 O << ", ";
5071 Mask->printAsOperand(O, SlotTracker);
5072 }
5073
5074 unsigned OpIdx = 0;
5075 for (unsigned i = 0; i < IG->getFactor(); ++i) {
5076 if (!IG->getMember(i))
5077 continue;
5078 if (getNumStoreOperands() > 0) {
5079 O << "\n" << Indent << " store ";
5080 getOperand(1 + OpIdx)->printAsOperand(O, SlotTracker);
5081 O << " to index " << i;
5082 } else {
5083 O << "\n" << Indent << " ";
5085 O << " = load from index " << i;
5086 }
5087 ++OpIdx;
5088 }
5089}
5090#endif
5091
5093 assert(State.VF.isScalable() &&
5094 "Only support scalable VF for EVL tail-folding.");
5096 "Masking gaps for scalable vectors is not yet supported.");
5098 Instruction *Instr = Group->getInsertPos();
5099
5100 // Prepare for the vector type of the interleaved load/store.
5101 Type *ScalarTy = getLoadStoreType(Instr);
5102 unsigned InterleaveFactor = Group->getFactor();
5103 assert(InterleaveFactor <= 8 &&
5104 "Unsupported deinterleave/interleave factor for scalable vectors");
5105 ElementCount WideVF = State.VF * InterleaveFactor;
5106 auto *VecTy = VectorType::get(ScalarTy, WideVF);
5107
5108 VPValue *Addr = getAddr();
5109 Value *ResAddr = State.get(Addr, VPLane(0));
5110 Value *EVL = State.get(getEVL(), VPLane(0));
5111 Value *InterleaveEVL = State.Builder.CreateMul(
5112 EVL, ConstantInt::get(EVL->getType(), InterleaveFactor), "interleave.evl",
5113 /* NUW= */ true, /* NSW= */ true);
5114 LLVMContext &Ctx = State.Builder.getContext();
5115
5116 Value *GroupMask = nullptr;
5117 if (VPValue *BlockInMask = getMask()) {
5118 SmallVector<Value *> Ops(InterleaveFactor, State.get(BlockInMask));
5119 GroupMask = interleaveVectors(State.Builder, Ops, "interleaved.mask");
5120 } else {
5121 GroupMask =
5122 State.Builder.CreateVectorSplat(WideVF, State.Builder.getTrue());
5123 }
5124
5125 // Vectorize the interleaved load group.
5126 if (isa<LoadInst>(Instr)) {
5127 CallInst *NewLoad = State.Builder.CreateIntrinsicWithoutFolding(
5128 VecTy, Intrinsic::vp_load, {ResAddr, GroupMask, InterleaveEVL}, nullptr,
5129 "wide.vp.load");
5130 NewLoad->addParamAttr(0,
5131 Attribute::getWithAlignment(Ctx, Group->getAlign()));
5132
5133 applyMetadata(*NewLoad);
5134 // TODO: Also manage existing metadata using VPIRMetadata.
5135 Group->addMetadata(NewLoad);
5136
5137 // Scalable vectors cannot use arbitrary shufflevectors (only splats),
5138 // so must use intrinsics to deinterleave.
5139 NewLoad = State.Builder.CreateIntrinsicWithoutFolding(
5140 Intrinsic::getDeinterleaveIntrinsicID(InterleaveFactor),
5141 NewLoad->getType(), NewLoad,
5142 /*FMFSource=*/nullptr, "strided.vec");
5143
5144 const DataLayout &DL = Instr->getDataLayout();
5145 for (unsigned I = 0, J = 0; I < InterleaveFactor; ++I) {
5146 Instruction *Member = Group->getMember(I);
5147 // Skip the gaps in the group.
5148 if (!Member)
5149 continue;
5150
5151 Value *StridedVec = State.Builder.CreateExtractValue(NewLoad, I);
5152 // If this member has different type, cast the result type.
5153 if (Member->getType() != ScalarTy) {
5154 VectorType *OtherVTy = VectorType::get(Member->getType(), State.VF);
5155 StridedVec =
5156 createBitOrPointerCast(State.Builder, StridedVec, OtherVTy, DL);
5157 }
5158
5159 State.set(getVPValue(J), StridedVec);
5160 ++J;
5161 }
5162 return;
5163 } // End for interleaved load.
5164
5165 // The sub vector type for current instruction.
5166 auto *SubVT = VectorType::get(ScalarTy, State.VF);
5167 // Vectorize the interleaved store group.
5168 ArrayRef<VPValue *> StoredValues = getStoredValues();
5169 // Collect the stored vector from each member.
5170 SmallVector<Value *, 4> StoredVecs;
5171 const DataLayout &DL = Instr->getDataLayout();
5172 for (unsigned I = 0, StoredIdx = 0; I < InterleaveFactor; I++) {
5173 Instruction *Member = Group->getMember(I);
5174 // Skip the gaps in the group.
5175 if (!Member) {
5176 StoredVecs.push_back(PoisonValue::get(SubVT));
5177 continue;
5178 }
5179
5180 Value *StoredVec = State.get(StoredValues[StoredIdx]);
5181 // If this member has different type, cast it to a unified type.
5182 if (StoredVec->getType() != SubVT)
5183 StoredVec = createBitOrPointerCast(State.Builder, StoredVec, SubVT, DL);
5184
5185 StoredVecs.push_back(StoredVec);
5186 ++StoredIdx;
5187 }
5188
5189 // Interleave all the smaller vectors into one wider vector.
5190 Value *IVec = interleaveVectors(State.Builder, StoredVecs, "interleaved.vec");
5191 CallInst *NewStore = State.Builder.CreateIntrinsicWithoutFolding(
5192 Type::getVoidTy(Ctx), Intrinsic::vp_store,
5193 {IVec, ResAddr, GroupMask, InterleaveEVL});
5194
5195 NewStore->addParamAttr(1,
5196 Attribute::getWithAlignment(Ctx, Group->getAlign()));
5197
5198 applyMetadata(*NewStore);
5199 // TODO: Also manage existing metadata using VPIRMetadata.
5200 Group->addMetadata(NewStore);
5201}
5202
5203#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
5205 VPSlotTracker &SlotTracker) const {
5207 O << Indent << "INTERLEAVE-GROUP with factor " << IG->getFactor() << ", ";
5209 O << ", ";
5211 if (VPValue *Mask = getMask()) {
5212 O << ", ";
5213 Mask->printAsOperand(O, SlotTracker);
5214 }
5215
5216 unsigned OpIdx = 0;
5217 for (unsigned i = 0; i < IG->getFactor(); ++i) {
5218 if (!IG->getMember(i))
5219 continue;
5220 if (getNumStoreOperands() > 0) {
5221 O << "\n" << Indent << " vp.store ";
5222 getOperand(2 + OpIdx)->printAsOperand(O, SlotTracker);
5223 O << " to index " << i;
5224 } else {
5225 O << "\n" << Indent << " ";
5227 O << " = vp.load from index " << i;
5228 }
5229 ++OpIdx;
5230 }
5231}
5232#endif
5233
5235 VPCostContext &Ctx) const {
5236 Instruction *InsertPos = getInsertPos();
5237 // Find the VPValue index of the interleave group. We need to skip gaps.
5238 unsigned InsertPosIdx = 0;
5239 for (unsigned Idx = 0; IG->getFactor(); ++Idx)
5240 if (auto *Member = IG->getMember(Idx)) {
5241 if (Member == InsertPos)
5242 break;
5243 InsertPosIdx++;
5244 }
5245 const VPValue *ValV = getNumDefinedValues() > 0
5246 ? getVPValue(InsertPosIdx)
5247 : getStoredValues()[InsertPosIdx];
5248 Type *ValTy = ValV->getScalarType();
5249 auto *VectorTy = cast<VectorType>(toVectorTy(ValTy, VF));
5250 unsigned AS =
5251 cast<PointerType>(getAddr()->getScalarType())->getAddressSpace();
5252
5253 unsigned InterleaveFactor = IG->getFactor();
5254 auto *WideVecTy = VectorType::get(ValTy, VF * InterleaveFactor);
5255
5256 // Holds the indices of existing members in the interleaved group.
5258 for (unsigned IF = 0; IF < InterleaveFactor; IF++)
5259 if (IG->getMember(IF))
5260 Indices.push_back(IF);
5261
5262 // Calculate the cost of the whole interleaved group.
5263 InstructionCost Cost = Ctx.TTI.getInterleavedMemoryOpCost(
5264 InsertPos->getOpcode(), WideVecTy, IG->getFactor(), Indices,
5265 IG->getAlign(), AS, Ctx.CostKind, getMask(), NeedsMaskForGaps);
5266
5267 if (!IG->isReverse())
5268 return Cost;
5269
5270 return Cost + IG->getNumMembers() *
5271 Ctx.TTI.getShuffleCost(TargetTransformInfo::SK_Reverse,
5272 VectorTy, VectorTy, Ctx.CostKind, {},
5273 0);
5274}
5275
5278 VPCostContext &Ctx) const {
5279 // The recipe creates a scalar phi, a GEP to increment the induction and
5280 // vector add to compute the vector of pointers.
5281 // TODO: Charge costs for induction increment and vector add as well.
5282 return Ctx.TTI.getCFInstrCost(Instruction::PHI, Ctx.CostKind);
5283}
5284
5289
5290#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
5292 raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const {
5293 assert((getNumOperands() == 3 || getNumOperands() == 5) &&
5294 "unexpected number of operands");
5295 O << Indent << "EMIT ";
5297 O << " = WIDEN-POINTER-INDUCTION ";
5299 O << ", ";
5301 O << ", ";
5303 if (getNumOperands() == 5) {
5304 O << ", ";
5306 O << ", ";
5308 }
5309}
5310
5312 VPSlotTracker &SlotTracker) const {
5313 O << Indent << "EMIT ";
5315 O << " = EXPAND SCEV " << *Expr;
5316 if (ExpandInIR)
5317 O << " (in IR)";
5318}
5319#endif
5320
5321#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
5323 VPSlotTracker &SlotTracker) const {
5324 O << Indent << "EMIT ";
5326 O << " = WIDEN-CANONICAL-INDUCTION";
5327 printFlags(O);
5329}
5330#endif
5331
5333 auto &Builder = State.Builder;
5334 // Create a vector from the initial value.
5335 auto *VectorInit = getStartValue()->getLiveInIRValue();
5336
5337 Type *VecTy = State.VF.isScalar()
5338 ? VectorInit->getType()
5339 : VectorType::get(VectorInit->getType(), State.VF);
5340
5341 BasicBlock *VectorPH =
5342 State.CFG.VPBB2IRBB.at(getParent()->getCFGPredecessor(0));
5343 if (State.VF.isVector()) {
5344 auto *IdxTy = Builder.getInt32Ty();
5345 auto *One = ConstantInt::get(IdxTy, 1);
5346 IRBuilder<>::InsertPointGuard Guard(Builder);
5347 Builder.SetInsertPoint(VectorPH->getTerminator());
5348 auto *RuntimeVF = getRuntimeVF(Builder, IdxTy, State.VF);
5349 auto *LastIdx = Builder.CreateSub(RuntimeVF, One);
5350 VectorInit = Builder.CreateInsertElement(
5351 PoisonValue::get(VecTy), VectorInit, LastIdx, "vector.recur.init");
5352 }
5353
5354 // Create a phi node for the new recurrence.
5355 PHINode *Phi = PHINode::Create(VecTy, 2, "vector.recur");
5356 Phi->insertBefore(State.CFG.PrevBB->getFirstInsertionPt());
5357 Phi->addIncoming(VectorInit, VectorPH);
5358 State.set(this, Phi);
5359}
5360
5363 VPCostContext &Ctx) const {
5364 if (VF.isScalar())
5365 return Ctx.TTI.getCFInstrCost(Instruction::PHI, Ctx.CostKind);
5366
5367 return 0;
5368}
5369
5370#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
5372 raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const {
5373 O << Indent << "FIRST-ORDER-RECURRENCE-PHI ";
5375 O << " = phi ";
5377}
5378#endif
5379
5381 // Reductions do not have to start at zero. They can start with
5382 // any loop invariant values.
5383 VPValue *StartVPV = getStartValue();
5384
5385 // In order to support recurrences we need to be able to vectorize Phi nodes.
5386 // Phi nodes have cycles, so we need to vectorize them in two stages. This is
5387 // stage #1: We create a new vector PHI node with no incoming edges. We'll use
5388 // this value when we vectorize all of the instructions that use the PHI.
5389 BasicBlock *VectorPH =
5390 State.CFG.VPBB2IRBB.at(getParent()->getCFGPredecessor(0));
5391 bool ScalarPHI = State.VF.isScalar() || isInLoop();
5392 Value *StartV = State.get(StartVPV, ScalarPHI);
5393 Type *VecTy = StartV->getType();
5394
5395 BasicBlock *HeaderBB = State.CFG.PrevBB;
5396 assert(State.CurrentParentLoop->getHeader() == HeaderBB &&
5397 "recipe must be in the vector loop header");
5398 auto *Phi = PHINode::Create(VecTy, 2, "vec.phi");
5399 Phi->insertBefore(HeaderBB->getFirstInsertionPt());
5400 State.set(this, Phi, isInLoop());
5401
5402 Phi->addIncoming(StartV, VectorPH);
5403}
5404
5405#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
5407 VPSlotTracker &SlotTracker) const {
5408 O << Indent << "WIDEN-REDUCTION-PHI ";
5409
5411 O << " = phi (";
5412 printRecurrenceKind(O, Kind);
5413 O << ")";
5414 printFlags(O);
5416 if (getVFScaleFactor() > 1)
5417 O << " (VF scaled by 1/" << getVFScaleFactor() << ")";
5418}
5419#endif
5420
5422 assert(is_contained(operands(), Op) && "Op must be an operand of the recipe");
5424 "Blend should propagate first lane use");
5425 return vputils::onlyFirstLaneUsed(this);
5426}
5427
5430 VPCostContext &Ctx) const {
5431 return Ctx.TTI.getCFInstrCost(Instruction::PHI, Ctx.CostKind);
5432}
5433
5434#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
5436 raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const {
5437 O << Indent << "CONDITIONAL-INDUCTION-PHI ";
5438
5440 O << " = phi ";
5442}
5443#endif
5444
5446 executePhiRecipe(this, *this, State, /*IsScalar=*/false, Name);
5447}
5448
5450 VPCostContext &Ctx) const {
5451 return Ctx.TTI.getCFInstrCost(Instruction::PHI, Ctx.CostKind);
5452}
5453
5454#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
5456 VPSlotTracker &SlotTracker) const {
5457 O << Indent << "WIDEN-PHI ";
5458
5460 O << " = phi ";
5462}
5463#endif
5464
5466 BasicBlock *VectorPH =
5467 State.CFG.VPBB2IRBB.at(getParent()->getCFGPredecessor(0));
5468 Value *StartMask = State.get(getOperand(0));
5469 PHINode *Phi =
5470 State.Builder.CreatePHI(StartMask->getType(), 2, "active.lane.mask");
5471 Phi->addIncoming(StartMask, VectorPH);
5472 State.set(this, Phi);
5473}
5474
5475#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
5477 VPSlotTracker &SlotTracker) const {
5478 O << Indent << "ACTIVE-LANE-MASK-PHI ";
5479
5481 O << " = phi ";
5483}
5484#endif
5485
5486#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
5488 raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const {
5489 O << Indent << "CURRENT-ITERATION-PHI ";
5490
5492 O << " = phi ";
5494}
5495#endif
static SDValue Widen(SelectionDAG *CurDAG, SDValue N)
bool IsScalable
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
uint64_t uint64_t
static MCDisassembler::DecodeStatus addOperand(MCInst &Inst, const MCOperand &Opnd)
AMDGPU Lower Kernel Arguments
AMDGPU Register Bank Select
This file declares a class to represent arbitrary precision floating point values and provide a varie...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static const Function * getParent(const Value *V)
#define X(NUM, ENUM, NAME)
Definition ELF.h:665
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static void replaceAllUsesWith(Value *Old, Value *New, SmallPtrSet< BasicBlock *, 32 > &FreshBBs, bool IsHuge)
Replace all old uses with new ones, and push the updated BBs into FreshBBs.
Hexagon Common GEP
Value * getPointer(Value *Ptr)
iv users
Definition IVUsers.cpp:48
static constexpr Value * getValue(Ty &ValueOrUse)
static std::pair< Value *, APInt > getMask(Value *WideMask, unsigned Factor, ElementCount LeafValueEC)
const size_t AbstractManglingParser< Derived, Alloc >::NumOps
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
This file provides a LoopVectorizationPlanner class.
static const SCEV * getAddressAccessSCEV(Value *Ptr, PredicatedScalarEvolution &PSE, const Loop *TheLoop)
Gets the address access SCEV for Ptr, if it should be used for cost modeling according to isAddressSC...
#define F(x, y, z)
Definition MD5.cpp:54
#define I(x, y, z)
Definition MD5.cpp:57
static const Function * getCalledFunction(const Value *V)
static bool isOrdered(const Instruction *I)
uint64_t IntrinsicInst * II
#define P(N)
This file contains the declarations for profiling metadata utility functions.
SmallVector< MachineOperand, 4 > Cond
SI Fold Operands
static SDValue getFPBinOp(SelectionDAG &DAG, unsigned Opcode, const SDLoc &SL, EVT VT, SDValue A, SDValue B, SDValue GlueChain, SDNodeFlags Flags)
This file contains some templates that are useful if you are working with the STL at all.
This file defines less commonly used SmallVector utilities.
This file defines the SmallVector class.
#define LLVM_DEBUG(...)
Definition Debug.h:119
static SymbolRef::Type getType(const Symbol *Sym)
Definition TapiFile.cpp:39
This file contains the declarations of different VPlan-related auxiliary helpers.
static Value * interleaveVectors(IRBuilderBase &Builder, ArrayRef< Value * > Vals, const Twine &Name)
Return a vector containing interleaved elements from multiple smaller input vectors.
static AttributeSet getCalleeFnAttrs(const VPInstruction &VPI)
Return the function attributes of the callee of VPI, which must be a call or intrinsic VPInstruction.
static const ConstantFP * getConstantFP(const VPValue *V)
Returns the ConstantFP V wraps, or nullptr if it does not wrap one.
static SmallVector< unsigned > getExtractValueIndices(ArrayRef< VPValue * > Ops)
static void executePhiRecipe(VPSingleDefRecipe *R, VPPhiAccessors &Phi, VPTransformState &State, bool IsScalar, const Twine &Name)
Shared execute logic for VPPhi and VPWidenPHIRecipe.
static Value * createBitOrPointerCast(IRBuilderBase &Builder, Value *V, VectorType *DstVTy, const DataLayout &DL)
static Instruction::BinaryOps getSubRecurOpcode(RecurKind Kind)
static Function * getCalledFunction(ArrayRef< VPValue * > Operands)
For call VPInstruction operands, return the called function.
static VPExecutionFrequency getExecutionFrequencyFromMD(const MDNode *Node)
Returns the execution frequency recorded in Node.
static void printRecurrenceKind(raw_ostream &OS, const RecurKind &Kind)
static unsigned getCalledFnOperandIndex(ArrayRef< VPValue * > Operands)
For call VPInstruction operands, return the operand index of the called function.
This file contains the declarations of the Vectorization Plan base classes:
static const fltSemantics & IEEEdouble()
Definition APFloat.h:305
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition APInt.h:230
Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition ArrayRef.h:40
size_t size() const
Get the array size.
Definition ArrayRef.h:141
bool empty() const
Check if the array is empty.
Definition ArrayRef.h:136
This class stores enough information to efficiently remove some attributes from an existing AttrBuild...
bool contains(Attribute::AttrKind A) const
Return true if the builder has the specified attribute.
This class holds the attributes for a particular argument, parameter, function, or return value.
Definition Attributes.h:448
bool hasAttributes() const
Return true if attributes exists in this set.
Definition Attributes.h:529
bool hasAttribute(Attribute::AttrKind Kind) const
Return true if the attribute exists in this set.
Definition Attributes.h:532
LLVM_ABI std::string getAsString(bool InAttrGrp=false) const
static LLVM_ABI AttributeSet get(LLVMContext &C, const AttrBuilder &B)
AttrKind
This enumeration lists the attributes that can be associated with parameters, function results,...
Definition Attributes.h:126
static LLVM_ABI Attribute getWithAlignment(LLVMContext &Context, Align Alignment)
Return a uniquified Attribute object that has the specific alignment set.
LLVM Basic Block Representation.
Definition BasicBlock.h:62
LLVM_ABI const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
Definition BasicBlock.h:237
void addParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
Adds the attribute to the indicated argument.
This class represents a function call, abstracting a target machine's calling convention.
static LLVM_ABI bool isBitOrNoopPointerCastable(Type *SrcTy, Type *DestTy, const DataLayout &DL)
Check whether a bitcast, inttoptr, or ptrtoint cast between these types is valid and a no-op.
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition InstrTypes.h:740
@ ICMP_ULT
unsigned less than
Definition InstrTypes.h:765
static LLVM_ABI StringRef getPredicateName(Predicate P)
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
static ConstantAsMetadata * get(Constant *C)
Definition Metadata.h:548
ConstantFP - Floating Point Values [float, double].
Definition Constants.h:420
bool isNegZero() const
Return true if the value is negative zero.
Definition Constants.h:473
bool isOne() const
Returns true if this value is exactly +1.0.
Definition Constants.h:485
bool isZero() const
Return true if the value is positive or negative zero.
Definition Constants.h:467
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
A parsed version of the target data layout string in and methods for querying it.
Definition DataLayout.h:64
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 getUnknown()
Definition DebugLoc.h:153
constexpr bool isVector() const
One or more elements.
Definition TypeSize.h:321
static constexpr ElementCount getScalable(ScalarTy MinVal)
Definition TypeSize.h:309
static constexpr ElementCount getFixed(ScalarTy MinVal)
Definition TypeSize.h:306
constexpr bool isScalar() const
Exactly one element.
Definition TypeSize.h:317
static LLVM_ABI Type * getIndexedType(Type *Agg, ArrayRef< unsigned > Idxs)
Returns the type of the element that would be extracted with an extractvalue instruction with the spe...
static bool isSupportedFloatingPointType(Type *Ty)
Returns true if Ty is a supported floating-point type for phi, select, or call FPMathOperators.
Definition Operator.h:302
Convenience struct for specifying and reasoning about fast-math flags.
Definition FMF.h:23
LLVM_ABI void print(raw_ostream &O) const
Print fast-math flags to O.
Definition Operator.cpp:290
void setAllowContract(bool B=true)
Definition FMF.h:90
bool noSignedZeros() const
Definition FMF.h:67
bool noInfs() const
Definition FMF.h:66
void setAllowReciprocal(bool B=true)
Definition FMF.h:87
bool allowReciprocal() const
Definition FMF.h:68
void setNoSignedZeros(bool B=true)
Definition FMF.h:84
bool allowReassoc() const
Flag queries.
Definition FMF.h:64
bool approxFunc() const
Definition FMF.h:70
void setNoNaNs(bool B=true)
Definition FMF.h:78
void setAllowReassoc(bool B=true)
Flag setters.
Definition FMF.h:75
bool noNaNs() const
Definition FMF.h:65
void setApproxFunc(bool B=true)
Definition FMF.h:93
void setNoInfs(bool B=true)
Definition FMF.h:81
bool allowContract() const
Definition FMF.h:69
static LLVM_ABI FixedVectorType * get(Type *ElementType, unsigned NumElts)
Definition Type.cpp:838
Class to represent function types.
unsigned getNumParams() const
Return the number of fixed parameters this function type requires.
Type * getParamType(unsigned i) const
Parameter type accessors.
Type * getReturnType() const
bool willReturn() const
Determine if the function will return.
Definition Function.h:647
Intrinsic::ID getIntrinsicID() const LLVM_READONLY
getIntrinsicID - This method returns the ID number of the specified function, or Intrinsic::not_intri...
Definition Function.h:247
AttributeList getAttributes() const
Return the attribute list for this Function.
Definition Function.h:329
bool doesNotThrow() const
Determine if the function cannot unwind.
Definition Function.h:577
Type * getReturnType() const
Returns the type of the ret val.
Definition Function.h:217
Represents flags for the getelementptr instruction/expression.
static GEPNoWrapFlags none()
Common base class shared among various IRBuilders.
Definition IRBuilder.h:111
const DataLayout & getDataLayout() const
Get data layout.
Definition IRBuilder.h:182
Value * CreateInsertElement(Type *VecTy, Value *NewElt, Value *Idx, const Twine &Name="")
Definition IRBuilder.h:2748
IntegerType * getInt1Ty()
Fetch the type representing a single bit.
Definition IRBuilder.h:513
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
Definition IRBuilder.h:2736
LLVM_ABI Value * CreateVectorSpliceRight(Value *V1, Value *V2, Value *Offset, const Twine &Name="")
Create a vector.splice.right intrinsic call, or a shufflevector that produces the same result if the ...
LoadInst * CreateAlignedLoad(Type *Ty, Value *Ptr, MaybeAlign Align, const char *Name)
Definition IRBuilder.h:1940
CondBrInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
Definition IRBuilder.h:1218
LLVM_ABI Value * CreateSelectFMF(Value *C, Value *True, Value *False, FMFSource FMFSource, const Twine &Name="", Instruction *MDFrom=nullptr)
LLVM_ABI Value * CreateVectorSplat(unsigned NumElts, Value *V, const Twine &Name="")
Return a vector value that contains.
LLVM_ABI CallInst * CreateMaskedLoad(Type *Ty, Value *Ptr, Align Alignment, Value *Mask, Value *PassThru=nullptr, const Twine &Name="")
Create a call to Masked Load intrinsic.
LLVM_ABI Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Value * CreateFreeze(Value *V, const Twine &Name="")
Definition IRBuilder.h:2814
IntegerType * getInt32Ty()
Fetch the type representing a 32-bit integer.
Definition IRBuilder.h:528
Value * CreateExtractVector(Type *DstType, Value *SrcVec, Value *Idx, const Twine &Name="")
Create a call to the vector.extract intrinsic.
Definition IRBuilder.h:1114
Value * CreatePtrAdd(Value *Ptr, Value *Offset, const Twine &Name="", GEPNoWrapFlags NW=GEPNoWrapFlags::none())
Definition IRBuilder.h:2094
Value * CreateCast(Instruction::CastOps Op, Value *V, Type *DestTy, const Twine &Name="", MDNode *FPMathTag=nullptr, FMFSource FMFSource={})
Definition IRBuilder.h:2360
void setFastMathFlags(FastMathFlags NewFMF)
Set the fast-math flags to be used with generated fp-math operators.
Definition IRBuilder.h:289
LLVM_ABI Value * CreateVectorReverse(Value *V, const Twine &Name="")
Return a vector value that contains the vector V reversed.
Value * CreateICmpNE(Value *LHS, Value *RHS, const Twine &Name="")
Definition IRBuilder.h:2462
ConstantInt * getInt64(uint64_t C)
Get a constant 64-bit value.
Definition IRBuilder.h:476
Value * CreateLogicalAnd(Value *Cond1, Value *Cond2, const Twine &Name="", Instruction *MDFrom=nullptr)
Definition IRBuilder.h:1772
LLVM_ABI Value * CreateOrReduce(Value *Src)
Create a vector int OR reduction intrinsic of the source vector.
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Definition IRBuilder.h:471
Value * CreateCmp(CmpInst::Predicate Pred, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition IRBuilder.h:2595
Value * CreateNot(Value *V, const Twine &Name="")
Definition IRBuilder.h:1856
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
Definition IRBuilder.h:2458
Value * CreateCountTrailingZeroElems(Type *ResTy, Value *Mask, bool ZeroIsPoison=true, const Twine &Name="")
Create a call to llvm.experimental_cttz_elts.
Definition IRBuilder.h:1156
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition IRBuilder.h:1441
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
Definition IRBuilder.h:2197
LLVM_ABI Value * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > OverloadTypes, ArrayRef< Value * > Args, FMFSource FMFSource={}, const Twine &Name="", ArrayRef< OperandBundleDef > OpBundles={}, function_ref< void(CallInst *)> SetFn=[](CallInst *) {})
Variant to create a possibly constant-folded intrinsic.
LLVM_ABI CallInst * CreateMaskedStore(Value *Val, Value *Ptr, Align Alignment, Value *Mask)
Create a call to Masked Store intrinsic.
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition IRBuilder.h:1424
ConstantInt * getFalse()
Get the constant value for i1 false.
Definition IRBuilder.h:456
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition IRBuilder.h:1733
Value * CreateICmpUGE(Value *LHS, Value *RHS, const Twine &Name="")
Definition IRBuilder.h:2470
Value * CreateLogicalOr(Value *Cond1, Value *Cond2, const Twine &Name="", Instruction *MDFrom=nullptr)
Definition IRBuilder.h:1780
StoreInst * CreateAlignedStore(Value *Val, Value *Ptr, MaybeAlign Align, bool isVolatile=false)
Definition IRBuilder.h:1959
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="", bool IsDisjoint=false)
Definition IRBuilder.h:1594
LLVM_ABI Value * CreateStepVector(Type *DstType, const Twine &Name="")
Creates a vector of type DstType with the linear sequence <0, 1, ...>
Value * CreateSExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a SExt or Trunc from the integer value V to DestTy.
Definition IRBuilder.h:2230
Value * CreateInsertVector(Type *DstType, Value *SrcVec, Value *SubVec, Value *Idx, const Twine &Name="")
Create a call to the vector.insert intrinsic.
Definition IRBuilder.h:1128
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition IRBuilder.h:1458
LLVM_ABI Value * CreateUnaryIntrinsic(Intrinsic::ID ID, Value *Op, FMFSource FMFSource={}, const Twine &Name="")
Create a call to intrinsic ID with 1 operand which is mangled on its type.
A struct for saving information about induction variables.
@ IK_FpInduction
Floating point induction variable.
@ IK_IntInduction
Integer induction variable. Step = C.
static InstructionCost getInvalid(CostType Val=0)
bool isCast() const
bool isBinaryOp() const
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
const char * getOpcodeName() const
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
LLVM_ABI void dropPoisonGeneratingFlags()
Drops flags that may cause this instruction to evaluate to poison despite having non-poison inputs.
LLVM_ABI void dropPoisonGeneratingAttributes()
Drops attributes that may generate poison.
LLVM_ABI void dropUBImplyingAttrsAndUnknownMetadata(ArrayRef< unsigned > KnownIDs={})
This function drops non-debug unknown metadata (through dropUnknownNonDebugMetadata).
bool isUnaryOp() 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
The group of interleaved loads/stores sharing the same stride and close to each other.
uint32_t getFactor() const
InstTy * getMember(uint32_t Index) const
Get the member with the given index Index.
bool isReverse() const
InstTy * getInsertPos() const
void addMetadata(InstTy *NewInst) const
Add metadata (e.g.
Align getAlign() const
This is an important class for using LLVM in a threaded context.
Definition LLVMContext.h:76
Represents a single loop in the control flow graph.
Definition LoopInfo.h:40
Metadata node.
Definition Metadata.h:1081
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition Metadata.h:1582
Information for memory intrinsic cost model.
bool doesNotAccessMemory() const
Whether this function accesses no memory.
Definition ModRef.h:246
Root of the metadata hierarchy.
Definition Metadata.h:64
LLVM_ABI void print(raw_ostream &OS, const Module *M=nullptr, bool IsForDebug=false) const
Print.
A Module instance is used to store all the information related to an LLVM module.
Definition Module.h:68
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
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.
static LLVM_ABI unsigned getOpcode(RecurKind Kind)
Returns the opcode corresponding to the RecurrenceKind.
static bool isAnyOfRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...
static LLVM_ABI bool isSubRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is for a sub operation.
static bool isFindIVRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...
static bool isMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is any min/max kind.
This class represents an analyzed expression in the program.
unsigned getOpcode() const
Return the SelectionDAG opcode value for this node.
This class represents the LLVM 'select' instruction.
This class provides computation of slot numbers for LLVM Assembly writing.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
SmallString - A SmallString is just a SmallVector with methods and accessors that make it work better...
Definition SmallString.h:28
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Represent a constant reference to a string, i.e.
Definition StringRef.h:56
static LLVM_ABI PartialReductionExtendKind getPartialReductionExtendKind(Instruction *I)
Get the kind of extension that an instruction represents.
static LLVM_ABI OperandValueInfo getOperandInfo(const Value *V)
Collect properties of V used in cost analysis, e.g. OP_PowerOf2.
llvm::VectorInstrContext VectorInstrContext
@ TCC_Free
Expected to fold away in lowering.
@ SK_Splice
Concatenates elements from the first input vector with elements of the second input vector.
@ SK_Reverse
Reverse the order of the vector.
CastContextHint
Represents a hint about the context in which a cast is used.
@ Reversed
The cast is used with a reversed load/store.
@ Masked
The cast is used with a masked load/store.
@ Normal
The cast is used with a normal load/store.
@ Interleave
The cast is used with an interleaved load/store.
@ GatherScatter
The cast is used with a gather/scatter.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition Twine.h:82
The instances of the Type class are immutable: once they are created, they are never changed.
Definition Type.h:46
static LLVM_ABI IntegerType * getInt64Ty(LLVMContext &C)
Definition Type.cpp:295
bool isByteTy() const
True if this is an instance of ByteType.
Definition Type.h:237
bool isVectorTy() const
True if this is an instance of VectorType.
Definition Type.h:283
static LLVM_ABI IntegerType * getInt32Ty(LLVMContext &C)
Definition Type.cpp:294
bool isPointerTy() const
True if this is an instance of PointerType.
Definition Type.h:277
static LLVM_ABI Type * getVoidTy(LLVMContext &C)
Definition Type.cpp:267
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
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
Definition Type.h:130
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 isIntOrPtrTy() const
Return true if this is an integer type or a pointer type.
Definition Type.h:265
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition Type.h:252
static LLVM_ABI IntegerType * getIntNTy(LLVMContext &C, unsigned N)
Definition Type.cpp:298
bool isVoidTy() const
Return true if this is 'void'.
Definition Type.h:141
value_op_iterator value_op_end()
Definition User.h:288
void setOperand(unsigned i, Value *Val)
Definition User.h:212
Value * getOperand(unsigned i) const
Definition User.h:207
value_op_iterator value_op_begin()
Definition User.h:285
unsigned getNumOperands() const
Definition User.h:229
void execute(VPTransformState &State) override
Generate the active lane mask phi of the vector loop.
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition VPlan.h:4540
InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const override
Return the cost of this VPWidenMemoryRecipe.
VPValue * getIncomingValue(unsigned Idx) const
Return incoming value number Idx.
Definition VPlan.h:3091
unsigned getNumIncomingValues() const
Return the number of incoming values, taking into account when normalized the first incoming value wi...
Definition VPlan.h:3086
bool usesFirstLaneOnly(const VPValue *Op) const override
Returns true if the recipe only uses the first lane of operand Op.
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
bool isNormalized() const
A normalized blend is one that has an odd number of operands, whereby the first operand does not have...
Definition VPlan.h:3082
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition VPlan.h:95
const VPBlocksTy & getPredecessors() const
Definition VPlan.h:228
static bool isHeader(const VPBlockBase *VPB, const VPDominatorTree &VPDT)
Returns true if VPB is a loop header, based on regions or VPDT in their absence.
InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const override
Return the cost of this VPBranchOnMaskRecipe.
void execute(VPTransformState &State) override
Generate the extraction of the appropriate bit from the block mask and the conditional branch.
InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const override
Compute the cost of this recipe either using a recipe's specialized implementation or using the legac...
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
unsigned getNumDefinedValues() const
Returns the number of values defined by the VPDef.
Definition VPlanValue.h:572
VPValue * getVPSingleValue()
Returns the only VPValue defined by the VPDef.
Definition VPlanValue.h:545
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
InductionDescriptor::InductionKind getInductionKind() const
Definition VPlan.h:4347
VPValue * getIndex() const
Definition VPlan.h:4344
VPValue * getStepValue() const
Definition VPlan.h:4345
InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const override
Return the cost of this VPDerivedIVRecipe.
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
VPValue * getStartValue() const
Definition VPlan.h:4343
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
VPExpandSCEVRecipe(const SCEV *Expr, bool ExpandInIR=false)
bool isVectorToScalar() const
Returns true if this VPExpressionRecipe produces a single scalar.
SmallVector< VPSingleDefRecipe * > decompose()
Return and insert the recipes of the expression back into the VPlan, directly before the current reci...
bool usesFirstLaneOnly(const VPValue *Op) const override
Returns true if the recipe only uses the first lane of operand Op.
bool mayHaveSideEffects() const
Returns true if this expression contains recipes that may have side effects.
InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const override
Compute the cost of this recipe either using a recipe's specialized implementation or using the legac...
bool mayReadOrWriteMemory() const
Returns true if this expression contains recipes that may read from or write to memory.
VPExpressionRecipe(ExpressionTypes ExpressionType, ArrayRef< VPSingleDefRecipe * > ExpressionRecipes)
Construct a new VPExpressionRecipe by internalizing recipes in ExpressionRecipes.
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const override
Return the cost of this header phi recipe.
VPValue * getStartValue()
Returns the start value of the phi, if one is set.
Definition VPlan.h:2512
void execute(VPTransformState &State) override
Produce a vectorized histogram operation.
InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const override
Return the cost of this VPHistogramRecipe.
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
VPValue * getMask() const
Return the mask operand if one was provided, or a null pointer if all lanes should be executed uncond...
Definition VPlan.h:2224
void printFnAttrs(raw_ostream &O) const
Print function attributes carried with this object.
void printRetAttrs(raw_ostream &O) const
Print return-value attributes carried with this object.
MemoryEffects getMemoryEffects(AttributeSet CalleeFnAttrs) const
Returns the memory effects of a call with these attributes to a callee with function attributes Calle...
Definition VPlan.h:1293
VPIRAttributes()=default
void intersectAttrs(const VPIRAttributes &Other, LLVMContext &Ctx)
Keep only the attributes valid for both this and Other.
void printParamAttrs(raw_ostream &O, unsigned ArgIdx) const
Print per-arg attributes for argument ArgIdx.
void applyAttrs(CallInst &WideCall) const
Apply the stored attributes to the widened call WideCall.
Definition VPlan.h:1287
Class to record and manage LLVM IR flags.
Definition VPlan.h:683
FastMathFlagsTy FMFs
Definition VPlan.h:775
ReductionFlagsTy ReductionFlags
Definition VPlan.h:777
LLVM_ABI_FOR_TEST bool flagsValidForOpcode(unsigned Opcode) const
Returns true if the set flags are valid for Opcode.
WrapFlagsTy WrapFlags
Definition VPlan.h:769
void printFlags(raw_ostream &O) const
bool hasFastMathFlags() const
Returns true if the recipe has fast-math flags.
Definition VPlan.h:978
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.
bool isReductionOrdered() const
Definition VPlan.h:1033
TruncFlagsTy TruncFlags
Definition VPlan.h:770
CmpInst::Predicate getPredicate() const
Definition VPlan.h:950
LLVM_ABI_FOR_TEST FastMathFlags getFastMathFlagsOrNone() const
ExactFlagsTy ExactFlags
Definition VPlan.h:772
void intersectFlags(const VPIRFlags &Other)
Only keep flags also present in Other.
uint8_t GEPFlagsStorage
Definition VPlan.h:773
GEPNoWrapFlags getGEPNoWrapFlags() const
Definition VPlan.h:968
bool hasPredicate() const
Returns true if the recipe has a comparison predicate.
Definition VPlan.h:973
LLVM_ABI_FOR_TEST bool hasRequiredFlagsForOpcode(unsigned Opcode, Type *ResultTy) const
Returns true if Opcode with scalar result type ResultTy has its required flags set.
DisjointFlagsTy DisjointFlags
Definition VPlan.h:771
FCmpFlagsTy FCmpFlags
Definition VPlan.h:776
NonNegFlagsTy NonNegFlags
Definition VPlan.h:774
bool isReductionInLoop() const
Definition VPlan.h:1039
void applyFlags(Instruction &I) const
Apply the IR flags to I.
Definition VPlan.h:915
uint8_t CmpPredStorage
Definition VPlan.h:768
RecurKind getRecurKind() const
Definition VPlan.h:1027
void execute(VPTransformState &State) override
The method which generates the output IR instructions that correspond to this VPRecipe,...
LLVM_ABI_FOR_TEST InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const override
Return the cost of this VPIRInstruction.
VPIRInstruction(Instruction &I)
VPIRInstruction::create() should be used to create VPIRInstructions, as subclasses may need to be cre...
Definition VPlan.h:1742
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
std::optional< VPExecutionFrequency > getExecutionFrequency() const
Returns the frequency recorded by setExecutionFrequency, if any.
void intersect(const VPIRMetadata &MD)
Intersect this VPIRMetadata object with MD, keeping only metadata nodes that are common to both.
void clearExecutionFrequency()
Drop the frequency recorded by setExecutionFrequency, if any.
VPIRMetadata()=default
void print(raw_ostream &O, VPSlotTracker &SlotTracker) const
Print metadata with node IDs.
void applyMetadata(Instruction &I) const
Add all metadata to I.
void setMetadata(unsigned Kind, MDNode *Node)
Set metadata with kind Kind to Node.
Definition VPlan.h:1201
void setExecutionFrequency(std::optional< VPExecutionFrequency > Freq, LLVMContext &Ctx)
Record that the recipe executes with frequency Freq, relative to the entry of the loop region.
This is a concrete Recipe that models a single VPlan-level instruction.
Definition VPlan.h:1322
InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const override
Return the cost of this VPInstruction.
bool doesGeneratePerAllLanes() const
Returns true if this recipe produces scalar values for all VF lanes.
@ ExtractLastActive
Extracts the last active lane from a set of vectors.
Definition VPlan.h:1437
@ Intrinsic
Calls a scalar intrinsic. The intrinsic ID is the last operand.
Definition VPlan.h:1449
@ ExtractLane
Extracts a single lane (first operand) from a set of vector operands.
Definition VPlan.h:1427
@ ExitingIVValue
Compute the exiting value of a wide induction after vectorization, that is the value of the last lane...
Definition VPlan.h:1441
@ WideIVStep
Scale the first operand (vector step) by the second operand (scalar-step).
Definition VPlan.h:1445
@ ResumeForEpilogue
Explicit user for values in the main VPlan, used by the epilogue vector loop.
Definition VPlan.h:1431
@ Unpack
Extracts all lanes from its (non-scalable) vector operand.
Definition VPlan.h:1378
@ 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
@ ComputeReductionResult
Reduce the operands to the final reduction result using the operation specified via the operation's V...
Definition VPlan.h:1381
bool hasResult() const
Definition VPlan.h:1543
bool opcodeMayReadOrWriteFromMemory() const
Returns true if the underlying opcode may read from or write to memory.
LLVM_DUMP_METHOD void dump() const
Print the VPInstruction to dbgs() (for debugging).
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the VPInstruction to O.
StringRef getName() const
Returns the symbolic name assigned to the VPInstruction.
Definition VPlan.h:1606
unsigned getOpcode() const
Definition VPlan.h:1525
bool usesFirstPartOnly() const override
Returns true if the recipe only uses the first part of all operands.
bool usesFirstLaneOnly(const VPValue *Op) const override
Returns true if the recipe only uses the first lane of operand Op.
void addOperand(VPValue *Op)
Add Op as operand of this VPInstruction.
VPInstruction(unsigned Opcode, ArrayRef< VPValue * > Operands, const VPIRFlags &Flags={}, const VPIRMetadata &MD={}, DebugLoc DL=DebugLoc::getUnknown(), const Twine &Name="", Type *ResultTy=nullptr, const VPIRAttributes &Attrs={})
bool isVectorToScalar() const
Returns true if this VPInstruction produces a scalar value from a vector, e.g.
VPValue * getMask() const
Returns the mask for the VPInstruction.
Definition VPlan.h:1572
bool isSingleScalar() const
Returns true if the recipe produces a single scalar value.
unsigned getNumOperandsForOpcode() const
Return the number of operands determined by the opcode of the VPInstruction, excluding mask.
bool isMasked() const
Returns true if the VPInstruction has a mask operand.
Definition VPlan.h:1546
void execute(VPTransformState &State) override
The method which generates the output IR instructions that correspond to this VPRecipe,...
bool needsMaskForGaps() const
Return true if the access needs a mask because of the gaps.
Definition VPlan.h:3195
InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const override
Return the cost of this recipe.
Instruction * getInsertPos() const
Definition VPlan.h:3199
const InterleaveGroup< Instruction > * getInterleaveGroup() const
Definition VPlan.h:3197
VPValue * getMask() const
Return the mask used by this recipe.
Definition VPlan.h:3189
ArrayRef< VPValue * > getStoredValues() const
Return the VPValues stored by this interleave group.
Definition VPlan.h:3218
VPValue * getAddr() const
Return the address accessed by this recipe.
Definition VPlan.h:3183
VPValue * getEVL() const
The VPValue of the explicit vector length.
Definition VPlan.h:3292
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
unsigned getNumStoreOperands() const override
Returns the number of stored operands of this interleave group.
Definition VPlan.h:3305
void execute(VPTransformState &State) override
Generate the wide load or store, and shuffles.
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
unsigned getNumStoreOperands() const override
Returns the number of stored operands of this interleave group.
Definition VPlan.h:3255
void execute(VPTransformState &State) override
Generate the wide load or store, and shuffles.
In what follows, the term "input IR" refers to code that is fed into the vectorizer whereas the term ...
static VPLane getLastLaneForVF(const ElementCount &VF)
static VPLane getLaneFromEnd(const ElementCount &VF, unsigned Offset)
static VPLane getFirstLane()
Helper type to provide functions to access incoming values and blocks for phi-like recipes.
Definition VPlan.h:1621
virtual const VPRecipeBase * getAsRecipe() const =0
Return a VPRecipeBase* to the current object.
LLVM_ABI_FOR_TEST VPValue * getIncomingValueForBlock(const VPBasicBlock *VPBB) const
Returns the incoming value for VPBB. VPBB must be an incoming block.
void removeIncomingValueFor(VPBlockBase *IncomingBlock) const
Removes the incoming value for IncomingBlock, which must be a predecessor.
detail::zippy< llvm::detail::zip_first, VPUser::const_operand_range, const_incoming_blocks_range > incoming_values_and_blocks() const
Returns an iterator range over pairs of incoming values and corresponding incoming blocks.
Definition VPlan.h:1671
VPValue * getIncomingValue(unsigned Idx) const
Returns the incoming VPValue with index Idx.
Definition VPlan.h:1630
void printPhiOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const
Print the recipe.
void setIncomingValueForBlock(const VPBasicBlock *VPBB, VPValue *V) const
Sets the incoming value for VPBB to V.
void execute(VPTransformState &State) override
Generates phi nodes for live-outs (from a replicate region) as needed to retain SSA form.
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition VPlan.h:402
bool mayReadFromMemory() const
Returns true if the recipe may read from memory.
void moveBefore(RecipeListTy::iterator I)
Unlink this recipe and insert it before I.
bool mayHaveSideEffects() const
Returns true if the recipe may have side-effects.
virtual void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const =0
Each concrete VPRecipe prints itself, without printing common information, like debug info or metadat...
VPRegionBlock * getRegion()
Definition VPlan.h:4945
RecipeListTy::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void dump() const
Dump the recipe to stderr (for debugging).
Definition VPlan.cpp:106
bool isPhi() const
Returns true for PHI-like recipes.
bool mayWriteToMemory() const
Returns true if the recipe may write to memory.
VPRecipeTy getVPRecipeID() const
Definition VPlan.h:515
virtual InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const
Compute the cost of this recipe either using a recipe's specialized implementation or using the legac...
DebugLoc getDebugLoc() const
Returns the debug location of the recipe.
Definition VPlan.h:547
bool isSafeToSpeculativelyExecute() const
Return true if we can safely execute this recipe unconditionally even if it is masked originally.
void insertBefore(VPRecipeBase *InsertPos)
Insert an unlinked recipe into a basic block immediately before the specified recipe.
void insertAfter(VPRecipeBase *InsertPos)
Insert an unlinked Recipe into a basic block immediately after the specified Recipe.
VPRecipeBase(VPRecipeTy SC, ArrayRef< VPValue * > Operands, DebugLoc DL=DebugLoc::getUnknown())
Definition VPlan.h:462
InstructionCost cost(ElementCount VF, VPCostContext &Ctx)
Return the cost of this recipe, taking into account if the cost computation should be skipped and the...
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const
Print the recipe, delegating to printRecipe().
void removeFromParent()
This method unlinks 'this' from the containing basic block, but does not delete it.
void moveAfter(VPRecipeBase *MovePos)
Unlink this recipe from its current VPBasicBlock and insert it into the VPBasicBlock that MovePos liv...
Type * getScalarType() const
Returns the scalar type of this VPRecipeValue.
Definition VPlanValue.h:349
friend class VPValue
Definition VPlanValue.h:328
void execute(VPTransformState &State) override
Generate the reduction in the loop.
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
VPValue * getEVL() const
The VPValue of the explicit vector length.
Definition VPlan.h:3466
unsigned getVFScaleFactor() const
Get the factor that the VF of this recipe's output should be scaled by, or 1 if it isn't scaled.
Definition VPlan.h:2939
bool isInLoop() const
Returns true if the phi is part of an in-loop reduction.
Definition VPlan.h:2958
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
void execute(VPTransformState &State) override
Generate the phi/select nodes.
bool isConditional() const
Return true if the in-loop reduction is conditional.
Definition VPlan.h:3405
InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const override
Return the cost of VPReductionRecipe.
VPValue * getVecOp() const
The VPValue of the vector value to be reduced.
Definition VPlan.h:3418
VPValue * getCondOp() const
The VPValue of the condition for the block.
Definition VPlan.h:3420
RecurKind getRecurrenceKind() const
Return the recurrence kind for the in-loop reduction.
Definition VPlan.h:3401
bool isPartialReduction() const
Returns true if the reduction outputs a vector with a scaled down VF.
Definition VPlan.h:3407
VPValue * getChainOp() const
The VPValue of the scalar Chain being accumulated.
Definition VPlan.h:3416
bool isInLoop() const
Returns true if the reduction is in-loop.
Definition VPlan.h:3411
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
void execute(VPTransformState &State) override
Generate the reduction in the loop.
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition VPlan.h:4771
bool isReplicator() const
An indicator whether this region is to generate multiple replicated instances of output IR correspond...
Definition VPlan.h:4847
const VPBranchOnMaskRecipe * getEntryBranchOnMask() const
Return the VPBranchOnMaskRecipe from the entry block of this replicating region.
Definition VPlan.cpp:703
void execute(VPTransformState &State) override
Generate replicas of the desired Ingredient.
bool isSingleScalar() const
Returns true if the recipe produces a single scalar value.
Definition VPlan.h:3545
InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const override
Return the cost of this VPReplicateRecipe.
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
static Type * computeScalarType(const Instruction *I, ArrayRef< VPValue * > Operands)
Compute the scalar result type for a VPReplicateRecipe wrapping I with Operands (excluding any predic...
static InstructionCost computeCallCost(Function *CalledFn, Type *ResultTy, ArrayRef< const VPValue * > ArgOps, bool IsSingleScalar, ElementCount VF, VPCostContext &Ctx)
Return the cost of scalarizing a call to CalledFn with argument operands ArgOps for a given VF.
unsigned getOpcode() const
Definition VPlan.h:3583
InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const override
Return the cost of this VPScalarIVStepsRecipe.
bool doesGeneratePerAllLanes() const
Returns true if this recipe produces scalar values for all VF lanes.
VPValue * getStepValue() const
Definition VPlan.h:4402
VPValue * getStartIndex() const
Return the StartIndex, or null if known to be zero, valid only after unrolling.
Definition VPlan.h:4410
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
void execute(VPTransformState &State) override
Generate the scalarized versions of the phi node as needed by their users.
VPSingleDefRecipe is a base class for recipes that model a sequence of one or more output IR that def...
Definition VPlan.h:605
Instruction * getUnderlyingInstr()
Returns the underlying instruction.
Definition VPlan.h:668
VPSingleDefRecipe(VPRecipeTy SC, ArrayRef< VPValue * > Operands, Type *ResultTy, Value *UV=nullptr, DebugLoc DL=DebugLoc::getUnknown())
Definition VPlan.h:607
LLVM_DUMP_METHOD void dump() const
Print this VPSingleDefRecipe to dbgs() (for debugging).
This class can be used to assign names to VPValues.
A symbolic live-in VPValue, used for values like vector trip count, VF, and VFxUF.
Definition VPlanValue.h:212
This class augments VPValue with operands which provide the inverse def-use edges from VPValue's user...
Definition VPlanValue.h:396
void printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const
Print the operands to O.
Definition VPlan.cpp:1517
operand_range operands()
Definition VPlanValue.h:472
unsigned getNumOperands() const
Definition VPlanValue.h:436
operand_iterator op_begin()
Definition VPlanValue.h:468
VPValue * getOperand(unsigned N) const
Definition VPlanValue.h:437
bool operands_empty() const
Definition VPlanValue.h:476
VPValue * getLastOperand() const
Returns the last operand.
Definition VPlanValue.h:443
void addOperand(VPValue *Operand)
Definition VPlanValue.h:422
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
bool isDefinedOutsideLoopRegions() const
Returns true if the VPValue is defined outside any loop.
Definition VPlan.cpp:1469
VPRecipeBase * getDefiningRecipe()
Returns the recipe defining this VPValue or nullptr if it is not defined by a recipe,...
Definition VPlan.cpp:119
void printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const
Definition VPlan.cpp:1513
Value * getUnderlyingValue() const
Return the underlying Value attached to this VPValue.
Definition VPlanValue.h:75
void setUnderlyingValue(Value *Val)
Definition VPlanValue.h:204
VPUser * getSingleUser()
Return the single user of this value, or nullptr if there is not exactly one user.
Definition VPlanValue.h:179
VPValue * getVFValue() const
Definition VPlan.h:2335
void execute(VPTransformState &State) override
The method which generates the output IR instructions that correspond to this VPRecipe,...
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Type * getSourceElementType() const
Definition VPlan.h:2332
int64_t getStride() const
Definition VPlan.h:2333
void materializeOffset(unsigned Part=0)
Adds the offset operand to the recipe.
VPValue * getStride() const
Definition VPlan.h:2407
Type * getSourceElementType() const
Definition VPlan.h:2422
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
void execute(VPTransformState &State) override
The method which generates the output IR instructions that correspond to this VPRecipe,...
VPValue * getVFxPart() const
Definition VPlan.h:2409
bool usesFirstLaneOnly(const VPValue *Op) const override
Returns true if the recipe only uses the first lane of operand Op.
operand_range args()
Definition VPlan.h:2176
Function * getCalledScalarFunction() const
Definition VPlan.h:2172
InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const override
Return the cost of this VPWidenCallRecipe.
void execute(VPTransformState &State) override
Produce a widened version of the call instruction.
static InstructionCost computeCallCost(Function *Variant, VPCostContext &Ctx)
Return the cost of widening a call using the vector function Variant.
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Instruction::CastOps getOpcode() const
Definition VPlan.h:1932
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
void execute(VPTransformState &State) override
Produce widened copies of the cast.
InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const override
Return the cost of this VPWidenCastRecipe.
void execute(VPTransformState &State) override
Generate the gep nodes.
Type * getSourceElementType() const
Definition VPlan.h:2289
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
bool usesFirstLaneOnly(const VPValue *Op) const override
Returns true if the recipe only uses the first lane of operand Op.
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
InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const override
Return the cost of this VPWidenIntOrFpInductionRecipe.
bool isTruncated() const
Returns true if this induction is evaluated in a narrower type than the start value.
Definition VPlan.h:2689
bool isCanonical() const
Returns true if the induction is canonical, i.e.
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
CallInst * createVectorCall(VPTransformState &State)
Helper function to produce the widened intrinsic call.
Intrinsic::ID getVectorIntrinsicID() const
Return the ID of the intrinsic.
Definition VPlan.h:2047
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
StringRef getIntrinsicName() const
Return to name of the intrinsic as string.
static InstructionCost computeCallCost(Intrinsic::ID ID, ArrayRef< const VPValue * > Operands, const VPRecipeWithIRFlags &R, ElementCount VF, VPCostContext &Ctx)
Compute the cost of a vector intrinsic with ID and Operands.
bool usesFirstLaneOnly(const VPValue *Op) const override
Returns true if the VPUser only uses the first lane of operand Op.
void execute(VPTransformState &State) override
Produce a widened version of the vector intrinsic.
InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const override
Return the cost of this vector intrinsic.
static InstructionCost computeMemIntrinsicCost(Intrinsic::ID IID, Type *Ty, bool IsMasked, Align Alignment, VPCostContext &Ctx)
Helper function for computing the cost of vector memory intrinsic.
Type * getAccessType(ElementCount VF) const
Returns the data type of the memory access at VF.
void execute(VPTransformState &State) override
Produce a widened version of the vector memory intrinsic.
unsigned getAddrOpIdx() const
Returns the address operand index of the VPWidenMemIntrinsicRecipe.
InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const override
Return the cost of this vector memory intrinsic.
VPValue * getMask() const
Returns the mask of a predicated VPWidenMemIntrinsicRecipe.
bool IsMasked
Whether the memory access is masked.
Definition VPlan.h:3864
bool isConsecutive() const
Return whether the loaded-from / stored-to addresses are consecutive.
Definition VPlan.h:3889
Instruction & Ingredient
Definition VPlan.h:3855
InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const
Return the cost of this VPWidenMemoryRecipe.
bool Consecutive
Whether the accessed addresses are consecutive.
Definition VPlan.h:3861
VPValue * getMask() const
Return the mask used by this recipe.
Definition VPlan.h:3899
Align Alignment
Alignment information for this memory access.
Definition VPlan.h:3858
virtual VPRecipeBase * getAsRecipe()=0
Return a VPRecipeBase* to the current object.
Align getAlign() const
Returns the alignment of the memory access.
Definition VPlan.h:3906
VPValue * getAddr() const
Return the address accessed by this recipe.
Definition VPlan.h:3892
InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const override
Return the cost of this VPWidenPHIRecipe.
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
void execute(VPTransformState &State) override
Generate the phi/select nodes.
bool onlyScalarsGenerated(bool IsScalable)
Returns true if only scalar values will be generated.
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const override
Return the cost of this VPWidenPointerInductionRecipe.
InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const override
Return the cost of this VPWidenRecipe.
void execute(VPTransformState &State) override
Produce a widened instruction using the opcode and operands of the recipe, processing State....
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
unsigned getOpcode() const
Definition VPlan.h:1874
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
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
Type * getType() const
All values are typed, get the type of this value.
Definition Value.h:257
LLVM_ABI void setName(const Twine &Name)
Change the name of the value.
Definition Value.cpp:389
LLVMContext & getContext() const
All values hold a context through their type.
Definition Value.h:260
LLVM_ABI void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
void mutateType(Type *Ty)
Mutate the type of this Value to be of the specified type.
Definition Value.h:809
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
Definition Value.cpp:314
Base class of all SIMD vector types.
ElementCount getElementCount() const
Return an ElementCount instance to represent the (possibly scalable) number of elements in the vector...
static LLVM_ABI VectorType * get(Type *ElementType, ElementCount EC)
This static method is the primary way to construct an VectorType.
static LLVM_ABI bool isValidElementType(Type *ElemTy)
Return true if the specified type is valid as a element type.
Type * getElementType() const
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
constexpr LeafTy divideCoefficientBy(ScalarTy RHS) const
We do not provide the '/' operator here because division for polynomial types does not work in the sa...
Definition TypeSize.h:253
self_iterator getIterator()
Definition ilist_node.h:123
typename base_list_type::iterator iterator
Definition ilist.h:121
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
CallInst * Call
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ BasicBlock
Various leaf nodes.
Definition ISDOpcodes.h:83
LLVM_ABI Intrinsic::ID getDeinterleaveIntrinsicID(unsigned Factor)
Returns the corresponding llvm.vector.deinterleaveN intrinsic for factor N.
LLVM_ABI Function * getOrInsertDeclaration(Module *M, ID id, ArrayRef< Type * > OverloadTys={})
Look up the Function declaration of the intrinsic id in the Module M.
LLVM_ABI AttributeSet getFnAttributes(LLVMContext &C, ID id)
Return the function attributes for an intrinsic.
LLVM_ABI StringRef getBaseName(ID id)
Return the LLVM name for an intrinsic, without encoded types for overloading, such as "llvm....
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.
auto m_Cmp()
Matches any compare instruction and ignore it.
bool match(Val *V, const Pattern &P)
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
auto m_Intrinsic(const Ts &...Ops)
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
LogicalOp_match< LHS, RHS, Instruction::And, true > m_c_LogicalAnd(const LHS &L, const RHS &R)
Matches L && R with LHS and RHS in either order.
LogicalOp_match< LHS, RHS, Instruction::Or, true > m_c_LogicalOr(const LHS &L, const RHS &R)
Matches L || R with LHS and RHS in either order.
auto m_ZExtOrTrunc(const Op0_t &Op0)
int_pred_ty< is_zero_int, 1 > m_False()
auto m_VPValue()
Match an arbitrary VPValue and ignore it.
VPInstruction_match< VPInstruction::ExplicitVectorLength, Op0_t > m_EVL(const Op0_t &Op0)
int_pred_ty< is_one, 1 > m_True()
VPInstruction_match< VPInstruction::BranchOnCond > m_BranchOnCond()
VPInstruction_match< VPInstruction::Reverse, Op0_t > m_Reverse(const Op0_t &Op0)
std::enable_if_t< detail::IsValidPointer< X, Y >::value, X * > extract(Y &&MD)
Extract a Value from Metadata.
Definition Metadata.h:679
NodeAddr< DefNode * > Def
Definition RDFGraph.h:384
friend class Instruction
Iterator for Instructions in a `BasicBlock.
Definition BasicBlock.h:73
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 isAddressSCEVForCost(const SCEV *Addr, ScalarEvolution &SE, const Loop *L)
Returns true if Addr is an address SCEV that can be passed to TTI::getAddressComputationCost,...
Intrinsic::ID getIntrinsicID(const Ty *R)
Return the intrinsic ID underlying a call.
Definition VPlanUtils.h:102
bool onlyFirstLaneUsed(const VPValue *Def)
Returns true if only the first lane of Def is used by all users.
bool propagatesFirstLaneUse(const VPUser *U, const VPValue *Op)
Returns true if checking whether U uses the first lane of Op requires recursively checking Op's users...
bool onlyScalarValuesUsed(const VPValue *Def)
Returns true if only scalar values of Def are used by all users.
bool isUsedByLoadStoreAddress(const VPValue *V)
Returns true if V is used as part of the address of another load or store.
LLVM_ABI_FOR_TEST const SCEV * getSCEVExprForVPValue(const VPValue *V, PredicatedScalarEvolution &PSE, const Loop *L=nullptr)
Return the SCEV expression for V.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition STLExtras.h:316
LLVM_ABI Value * createSimpleReduction(IRBuilderBase &B, Value *Src, RecurKind RdxKind)
Create a reduction of the given vector.
@ Offset
Definition DWP.cpp:577
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
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1755
LLVM_ABI Intrinsic::ID getMinMaxReductionIntrinsicOp(Intrinsic::ID RdxID)
Returns the min/max intrinsic used when expanding a min/max reduction.
InstructionCost Cost
@ Undef
Value of the register doesn't matter.
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:2570
LLVM_ABI std::optional< unsigned > getVectorStoreIntrinsicDataArgIdx(Intrinsic::ID ID)
Returns the argument index of the data value of the vector store intrinsic ID, or std::nullopt if the...
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
VectorInstrContext
Represents a hint about the context in which a vector instruction or intrinsic is used.
@ None
The instruction is not folded.
@ BinaryOp
One of the operands is a binary op.
VPBuilderBase<> VPBuilder
Definition VPlan.h:66
auto map_to_vector(ContainerTy &&C, FuncTy &&F)
Map a range to a SmallVector with element types deduced from the mapping.
Value * getRuntimeVF(IRBuilderBase &B, Type *Ty, ElementCount VF)
Return the runtime value for VF.
auto dyn_cast_if_present(const Y &Val)
dyn_cast_if_present<X> - Functionally identical to dyn_cast, except that a null (or none in the case ...
Definition Casting.h:732
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition STLExtras.h:2224
void interleaveComma(const Container &c, StreamT &os, UnaryFunctor each_fn)
Definition STLExtras.h:2329
auto cast_or_null(const Y &Val)
Definition Casting.h:714
LLVM_ABI Value * concatenateVectors(IRBuilderBase &Builder, ArrayRef< Value * > Vecs)
Concatenate a list of vectors.
Align getLoadStoreAlignment(const Value *I)
A helper function that returns the alignment of load or store instruction.
bool isa_and_nonnull(const Y &Val)
Definition Casting.h:676
LLVM_ABI Value * createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left, Value *Right)
Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
Definition InstrProf.h:143
auto dyn_cast_or_null(const Y &Val)
Definition Casting.h:753
static Error getOffset(const SymbolRef &Sym, SectionRef Sec, uint64_t &Result)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1762
LLVM_ABI Constant * createBitMaskForGaps(IRBuilderBase &Builder, unsigned VF, const InterleaveGroup< Instruction > &Group)
Create a mask that filters the members of an interleave group where there are gaps.
LLVM_ABI llvm::SmallVector< int, 16 > createStrideMask(unsigned Start, unsigned Stride, unsigned VF)
Create a stride shuffle mask.
auto reverse(ContainerTy &&C)
Definition STLExtras.h:408
ElementCount getVectorizedTypeVF(Type *Ty)
Returns the number of vector elements for a vectorized type.
LLVM_ABI llvm::SmallVector< int, 16 > createReplicatedMask(unsigned ReplicationFactor, unsigned VF)
Create a mask with replicated elements.
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
bool isPointerTy(const Type *T)
Definition SPIRVUtils.h:373
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< 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...
Type * toVectorizedTy(Type *Ty, ElementCount EC)
A helper for converting to vectorized types.
LLVM_ABI Type * computeScalarTypeForInstruction(unsigned Opcode, ArrayRef< VPValue * > Operands)
Compute the scalar result type for an IR Opcode given Operands.
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
LLVM_ABI bool isVectorIntrinsicWithStructReturnOverloadAtField(Intrinsic::ID ID, int RetIdx, const TargetTransformInfo *TTI)
Identifies if the vector form of the intrinsic that returns a struct is overloaded at the struct elem...
@ Other
Any other memory.
Definition ModRef.h:68
static const MachineInstrBuilder & addOffset(const MachineInstrBuilder &MIB, int Offset)
LLVM_ABI llvm::SmallVector< int, 16 > createInterleaveMask(unsigned VF, unsigned NumVecs)
Create an interleave shuffle mask.
LLVM_ABI std::optional< unsigned > getVectorMemoryIntrinsicPointerArgIdx(Intrinsic::ID ID)
Returns the argument index of the pointer parameter for the vector memory intrinsic ID,...
RecurKind
These are the kinds of recurrences that we support.
@ UMin
Unsigned integer min implemented in terms of select(cmp()).
@ FMinimumNum
FP min with llvm.minimumnum semantics.
@ FindIV
FindIV reduction with select(icmp(),x,y) where one of (x,y) is a loop induction variable (increasing ...
@ Or
Bitwise or logical OR of integers.
@ FMinimum
FP min with llvm.minimum semantics.
@ FMaxNum
FP max with llvm.maxnum semantics including NaNs.
@ Mul
Product of integers.
@ FSub
Subtraction of floats.
@ FAddChainWithSubs
A chain of fadds and fsubs.
@ None
Not a recurrence.
@ AnyOf
AnyOf reduction with select(cmp(),x,y) where one of (x,y) is loop invariant, and both x and y are int...
@ Xor
Bitwise or logical XOR of integers.
@ FindLast
FindLast reduction with select(cmp(),x,y) where x and y.
@ FMax
FP max implemented in terms of select(cmp()).
@ FMaximum
FP max with llvm.maximum semantics.
@ FMulAdd
Sum of float products with llvm.fmuladd(a * b + sum).
@ FMul
Product of floats.
@ SMax
Signed integer max implemented in terms of select(cmp()).
@ And
Bitwise or logical AND of integers.
@ SMin
Signed integer min implemented in terms of select(cmp()).
@ FMin
FP min implemented in terms of select(cmp()).
@ FMinNum
FP min with llvm.minnum semantics including NaNs.
@ Sub
Subtraction of integers.
@ Add
Sum of integers.
@ AddChainWithSubs
A chain of adds and subs.
@ FAdd
Sum of floats.
@ FMaximumNum
FP max with llvm.maximumnum semantics.
@ UMax
Unsigned integer max implemented in terms of select(cmp()).
LLVM_ABI bool isVectorIntrinsicWithScalarOpAtArg(Intrinsic::ID ID, unsigned ScalarOpdIdx, const TargetTransformInfo *TTI)
Identifies if the vector form of the intrinsic has a scalar operand.
LLVM_ABI Value * getRecurrenceIdentity(RecurKind K, Type *Tp, FastMathFlags FMF)
Given information about an recurrence kind, return the identity for the @llvm.vector....
DWARFExpression::Operation Op
LLVM_ABI std::optional< unsigned > getVectorIntrinsicMaskArgIdx(Intrinsic::ID ID)
Returns the argument index of the mask for the vector intrinsic ID, or std::nullopt if the intrinsic ...
LLVM_ABI bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
constexpr auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
Definition Sequence.h:341
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition STLExtras.h:2208
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition STLExtras.h:1963
Type * getLoadStoreType(const Value *I)
A helper function that returns the type of a load or store instruction.
LLVM_ABI Value * createOrderedReduction(IRBuilderBase &B, RecurKind RdxKind, Value *Src, Value *Start)
Create an ordered reduction intrinsic using the given recurrence kind RdxKind.
ArrayRef< Type * > getContainedTypes(Type *const &Ty)
Returns the types contained in Ty.
Type * toVectorTy(Type *Scalar, ElementCount EC)
A helper function for converting Scalar types to vector types.
LLVM_ABI bool isVectorIntrinsicWithOverloadTypeAtArg(Intrinsic::ID ID, int OpdIdx, const TargetTransformInfo *TTI)
Identifies if the vector form of the intrinsic is overloaded on the type of the operand at index OpdI...
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition Alignment.h:39
constexpr uint64_t value() const
This is a hole in the type system and should not be abused.
Definition Alignment.h:82
Struct to hold various analysis needed for cost computations.
static bool isFreeScalarIntrinsic(Intrinsic::ID ID)
Returns true if ID is a pseudo intrinsic that is dropped via scalarization rather than widened.
Definition VPlan.cpp:1929
static bool executesAtMostOnce(const VPlan &Plan, ElementCount VF)
Returns true if the vector loop body of Plan is known to execute at most once at VF,...
TargetTransformInfo::TargetCostKind CostKind
The frequency with which a recipe executes, relative to the entry of the loop region.
Definition VPlan.h:1140
void execute(VPTransformState &State) override
Generate the phi nodes.
InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const override
Return the cost of this first-order recurrence phi recipe.
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
An overlay for VPIRInstructions wrapping PHI nodes enabling convenient use cast/dyn_cast/isa and exec...
Definition VPlan.h:1797
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
PHINode & getIRPhi() const
Definition VPlan.h:1810
void execute(VPTransformState &State) override
The method which generates the output IR instructions that correspond to this VPRecipe,...
void execute(VPTransformState &State) override
The method which generates the output IR instructions that correspond to this VPRecipe,...
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
InstructionCost getCostForRecipeWithOpcode(unsigned Opcode, ElementCount VF, VPCostContext &Ctx) const
Compute the cost for this recipe for VF, using Opcode and Ctx.
VPRecipeWithIRFlags(VPRecipeTy SC, ArrayRef< VPValue * > Operands, Type *ResultTy, const VPIRFlags &Flags, DebugLoc DL=DebugLoc::getUnknown())
Definition VPlan.h:1090
SmallDenseMap< const VPBasicBlock *, BasicBlock * > VPBB2IRBB
A mapping of each VPBasicBlock to the corresponding BasicBlock.
VPTransformState holds information passed down when "executing" a VPlan, needed for generating the ou...
struct llvm::VPTransformState::CFGState CFG
IRBuilderBase & Builder
Hold a reference to the IRBuilder used to generate output IR code.
Value * get(const VPValue *Def, bool NeedsSingleScalar=false)
Get the generated vector Value for a given VPValue Def if NeedsSingleScalar is false,...
Definition VPlan.cpp:266
ElementCount VF
The chosen Vectorization Factor of the loop being vectorized.
void execute(VPTransformState &State) override
Generate the wide load or gather.
VPRecipeBase * getAsRecipe() override
Return a VPRecipeBase* to the current object.
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const override
Return the cost of this VPWidenLoadEVLRecipe.
VPValue * getEVL() const
Return the EVL operand.
Definition VPlan.h:3993
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
void execute(VPTransformState &State) override
Generate a wide load or gather.
VPRecipeBase * getAsRecipe() override
Return a VPRecipeBase* to the current object.
VPValue * getStoredValue() const
Return the address accessed by this recipe.
Definition VPlan.h:4096
void execute(VPTransformState &State) override
Generate the wide store or scatter.
VPRecipeBase * getAsRecipe() override
Return a VPRecipeBase* to the current object.
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
InstructionCost computeCost(ElementCount VF, VPCostContext &Ctx) const override
Return the cost of this VPWidenStoreEVLRecipe.
VPValue * getEVL() const
Return the EVL operand.
Definition VPlan.h:4099
void execute(VPTransformState &State) override
Generate a wide store or scatter.
void printRecipe(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
VPRecipeBase * getAsRecipe() override
Return a VPRecipeBase* to the current object.
VPValue * getStoredValue() const
Return the value stored by this recipe.
Definition VPlan.h:4043