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
14#include "LoopVectorizationPlanner.h"
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"
22#include "llvm/ADT/SmallVector.h"
23#include "llvm/ADT/SmallVectorExtras.h"
24#include "llvm/ADT/Twine.h"
25#include "llvm/Analysis/AssumptionCache.h"
26#include "llvm/Analysis/BlockFrequencyInfoImpl.h"
27#include "llvm/Analysis/IVDescriptors.h"
28#include "llvm/Analysis/LoopInfo.h"
29#include "llvm/Analysis/ScalarEvolutionExpressions.h"
30#include "llvm/IR/AttributeMask.h"
31#include "llvm/IR/BasicBlock.h"
32#include "llvm/IR/IRBuilder.h"
33#include "llvm/IR/Instruction.h"
34#include "llvm/IR/Instructions.h"
35#include "llvm/IR/Intrinsics.h"
36#include "llvm/IR/ProfDataUtils.h"
37#include "llvm/IR/Type.h"
38#include "llvm/IR/Value.h"
39#include "llvm/Support/Casting.h"
40#include "llvm/Support/Debug.h"
41#include "llvm/Support/raw_ostream.h"
42#include "llvm/Transforms/Utils/BasicBlockUtils.h"
43#include "llvm/Transforms/Utils/LoopUtils.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).
55static unsigned getCalledFnOperandIndex(ArrayRef<VPValue *> Operands) {
56 unsigned NumOps = Operands.size();
57 auto *LastOp = dyn_cast<VPIRValue>(Val: Operands[NumOps - 1]);
58 if (LastOp && isa<Function>(Val: LastOp->getValue()))
59 return NumOps - 1;
60 assert(isa<Function>(cast<VPIRValue>(Operands[NumOps - 2])->getValue()) &&
61 "expected function operand");
62 return NumOps - 2;
63}
64
65/// For call VPInstruction operands, return the called function.
66static Function *getCalledFunction(ArrayRef<VPValue *> Operands) {
67 unsigned Idx = getCalledFnOperandIndex(Operands);
68 return cast<Function>(Val: cast<VPIRValue>(Val: Operands[Idx])->getValue());
69}
70
71/// Return the function attributes of the callee of \p VPI, which must be a
72/// call or intrinsic VPInstruction.
73static AttributeSet getCalleeFnAttrs(const VPInstruction &VPI) {
74 if (VPI.getOpcode() == VPInstruction::Intrinsic)
75 return Intrinsic::getFnAttributes(C&: VPI.getScalarType()->getContext(),
76 id: vputils::getIntrinsicID(R: &VPI));
77 return getCalledFunction(Operands: VPI.operands())->getAttributes().getFnAttrs();
78}
79
80bool VPRecipeBase::mayWriteToMemory() const {
81 switch (getVPRecipeID()) {
82 case VPExpressionSC:
83 return cast<VPExpressionRecipe>(Val: this)->mayReadOrWriteMemory();
84 case VPInstructionSC: {
85 auto *VPI = cast<VPInstruction>(Val: 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>(Val: this)->getNumStoreOperands() > 0;
95 case VPWidenStoreEVLSC:
96 case VPWidenStoreSC:
97 return true;
98 case VPReplicateSC:
99 return cast<Instruction>(Val: getVPSingleValue()->getUnderlyingValue())
100 ->mayWriteToMemory();
101 case VPWidenCallSC:
102 return !cast<VPWidenCallRecipe>(Val: this)
103 ->getCalledScalarFunction()
104 ->onlyReadsMemory();
105 case VPWidenMemIntrinsicSC:
106 case VPWidenIntrinsicSC:
107 return cast<VPWidenIntrinsicRecipe>(Val: 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>(Val: 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
145bool VPRecipeBase::mayReadFromMemory() const {
146 switch (getVPRecipeID()) {
147 case VPExpressionSC:
148 return cast<VPExpressionRecipe>(Val: this)->mayReadOrWriteMemory();
149 case VPInstructionSC: {
150 auto *VPI = cast<VPInstruction>(Val: 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>(Val: getVPSingleValue()->getUnderlyingValue())
161 ->mayReadFromMemory();
162 case VPWidenCallSC:
163 return !cast<VPWidenCallRecipe>(Val: this)
164 ->getCalledScalarFunction()
165 ->onlyWritesMemory();
166 case VPWidenMemIntrinsicSC:
167 case VPWidenIntrinsicSC:
168 return cast<VPWidenIntrinsicRecipe>(Val: 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>(Val: 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
207bool VPRecipeBase::mayHaveSideEffects() const {
208 switch (getVPRecipeID()) {
209 case VPExpressionSC:
210 return cast<VPExpressionRecipe>(Val: 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>(Val: this);
223 if (VPI->getOpcode() == Instruction::Call ||
224 VPI->getOpcode() == VPInstruction::Intrinsic) {
225 AttributeSet CalleeFnAttrs = getCalleeFnAttrs(VPI: *VPI);
226 return mayWriteToMemory() ||
227 !VPI->hasFnAttr(Kind: Attribute::NoUnwind, CalleeFnAttrs) ||
228 !VPI->hasFnAttr(Kind: 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>(Val: this)->getCalledScalarFunction();
237 return mayWriteToMemory() || !Fn->doesNotThrow() || !Fn->willReturn();
238 }
239 case VPWidenMemIntrinsicSC:
240 case VPWidenIntrinsicSC:
241 return cast<VPWidenIntrinsicRecipe>(Val: 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>(Val: 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() ==
270 mayWriteToMemory() &&
271 "mayHaveSideffects result for ingredient differs from this "
272 "implementation");
273 return mayWriteToMemory();
274 case VPReplicateSC: {
275 auto *R = cast<VPReplicateRecipe>(Val: this);
276 return R->getUnderlyingInstr()->mayHaveSideEffects();
277 }
278 default:
279 return true;
280 }
281}
282
283bool VPRecipeBase::isSafeToSpeculativelyExecute() const {
284 switch (getVPRecipeID()) {
285 default:
286 return false;
287 case VPInstructionSC: {
288 unsigned Opcode = cast<VPInstruction>(Val: 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:
301 case VPInstruction::Intrinsic:
302 return getCalleeFnAttrs(VPI: *cast<VPInstruction>(Val: this))
303 .hasAttribute(Kind: Attribute::Speculatable);
304 }
305 }
306 }
307}
308
309void VPRecipeBase::insertBefore(VPRecipeBase *InsertPos) {
310 insertBefore(IP: InsertPos->getIterator());
311}
312
313void VPRecipeBase::insertBefore(RecipeListTy::iterator I) {
314 assert(!getParent() && "Recipe already in some VPBasicBlock");
315 assert(I.getNodeParent() && "Insertion position not in any VPBasicBlock");
316 I.getNodeParent()->insert(Recipe: this, InsertPt: I);
317}
318
319void VPRecipeBase::insertAfter(VPRecipeBase *InsertPos) {
320 assert(InsertPos->getParent() &&
321 "Insertion position not in any VPBasicBlock");
322 insertBefore(I: std::next(x: InsertPos->getIterator()));
323}
324
325void VPRecipeBase::removeFromParent() {
326 assert(getParent() && "Recipe not in any VPBasicBlock");
327 getParent()->getRecipeList().remove(IT: getIterator());
328 setParent(nullptr);
329}
330
331VPRecipeBase::RecipeListTy::iterator VPRecipeBase::eraseFromParent() {
332 assert(getParent() && "Recipe not in any VPBasicBlock");
333 return getParent()->getRecipeList().erase(where: getIterator());
334}
335
336void VPRecipeBase::moveAfter(VPRecipeBase *InsertPos) {
337 removeFromParent();
338 insertAfter(InsertPos);
339}
340
341void VPRecipeBase::moveBefore(RecipeListTy::iterator I) {
342 removeFromParent();
343 insertBefore(I);
344}
345
346InstructionCost VPRecipeBase::cost(ElementCount VF, VPCostContext &Ctx) {
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>(Val: this))
353 UI = dyn_cast_or_null<Instruction>(Val: S->getUnderlyingValue());
354 else if (auto *IG = dyn_cast<VPInterleaveBase>(Val: this))
355 UI = IG->getInsertPos();
356 else if (auto *WidenMem = dyn_cast<VPWidenMemoryRecipe>(Val: 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>(Val: this);
363 bool ReplicatesScalable =
364 RepR && VF.isScalable() && RepR->doesGeneratePerAllLanes();
365 InstructionCost RecipeCost;
366 if (UI && Ctx.skipCostComputation(UI, IsVector: 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 ||
374 isa<VPDerivedIVRecipe, VPScalarIVStepsRecipe, VPBranchOnMaskRecipe>(
375 Val: 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
394InstructionCost VPRecipeBase::computeCost(ElementCount VF,
395 VPCostContext &Ctx) const {
396 llvm_unreachable("subclasses should implement computeCost");
397}
398
399bool VPRecipeBase::isPhi() const {
400 return (getVPRecipeID() >= VPFirstPHISC && getVPRecipeID() <= VPLastPHISC) ||
401 isa<VPPhi, VPIRPhi>(Val: this);
402}
403
404void VPIRFlags::intersectFlags(const VPIRFlags &Other) {
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
452FastMathFlags VPIRFlags::getFastMathFlagsOrNone() const {
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)
468void VPSingleDefRecipe::dump() const { VPRecipeBase::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))
479 Metadata->print(O, SlotTracker);
480}
481#endif
482
483VPExpandSCEVRecipe::VPExpandSCEVRecipe(const SCEV *Expr, bool ExpandInIR)
484 : VPSingleDefRecipe(VPRecipeBase::VPExpandSCEVSC, {}, Expr->getType()),
485 Expr(Expr), ExpandInIR(ExpandInIR) {}
486
487static SmallVector<unsigned> getExtractValueIndices(ArrayRef<VPValue *> Ops) {
488 return map_to_vector(C: drop_begin(RangeOrContainer&: Ops), F: [](VPValue *Op) {
489 return unsigned(cast<VPConstantInt>(Val: Op)->getZExtValue());
490 });
491}
492
493Type *llvm::computeScalarTypeForInstruction(unsigned Opcode,
494 ArrayRef<VPValue *> Operands) {
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) {
510 case VPInstruction::BranchOnCond:
511 assert(Op0Ty->isIntegerTy(1) && "expected bool condition");
512 return Type::getVoidTy(C&: Ctx);
513 case VPInstruction::BranchOnTwoConds:
514 assert(Op0Ty->isIntegerTy(1) && "expected bool condition");
515 AssertOperandType(1, IntegerType::get(C&: Ctx, NumBits: 1));
516 return Type::getVoidTy(C&: Ctx);
517 case VPInstruction::BranchOnCount:
518 assert(Op0Ty->isIntegerTy() && "expected integer operand");
519 AssertOperandType(1, Op0Ty);
520 return Type::getVoidTy(C&: Ctx);
521 case VPInstruction::CanonicalIVIncrementForPart:
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(C&: Ctx);
530 case VPInstruction::WideVectorStore:
531 case Instruction::Store:
532 return Type::getVoidTy(C&: Ctx);
533 case Instruction::ICmp:
534 assert(Op0Ty->isIntOrPtrTy() && "expected integer or pointer operand");
535 AssertOperandType(1, Op0Ty);
536 return IntegerType::get(C&: Ctx, NumBits: 1);
537 case Instruction::FCmp:
538 assert(Op0Ty->isFloatingPointTy() && "expected floating-point operand");
539 AssertOperandType(1, Op0Ty);
540 return IntegerType::get(C&: Ctx, NumBits: 1);
541 case VPInstruction::ActiveLaneMask:
542 case VPInstruction::WideActiveLaneMask:
543 assert(Op0Ty->isIntegerTy() && "expected integer operand");
544 AssertOperandType(1, Op0Ty);
545 return IntegerType::get(C&: Ctx, NumBits: 1);
546 case VPInstruction::MaskedCond:
547 assert(Op0Ty->isIntegerTy(1) && "expected bool operand");
548 return IntegerType::get(C&: Ctx, NumBits: 1);
549 case VPInstruction::LogicalAnd:
550 case VPInstruction::LogicalOr:
551 assert(Op0Ty->isIntegerTy(1) && "expected bool operand");
552 AssertOperandType(1, Op0Ty);
553 return IntegerType::get(C&: Ctx, NumBits: 1);
554 case VPInstruction::AnyOf:
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(C&: Ctx, NumBits: 1);
559 case VPInstruction::ExplicitVectorLength:
560 assert(Op0Ty->isIntegerTy() && "expected integer operand");
561 return IntegerType::get(C&: Ctx, NumBits: 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;
576 case VPInstruction::ReductionStartVector:
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;
581 case VPInstruction::ExtractLane: {
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 }
591 case VPInstruction::PtrAdd:
592 case VPInstruction::WidePtrAdd:
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:
599 return ExtractValueInst::getIndexedType(Agg: Op0Ty,
600 Idxs: getExtractValueIndices(Ops: Operands));
601 case VPInstruction::WideVectorLoad:
602 case VPInstruction::FirstActiveLane:
603 case VPInstruction::LastActiveLane:
604 case VPInstruction::NumActiveLanes:
605 case VPInstruction::IncomingAliasMask:
606 case Instruction::Load:
607 case Instruction::Alloca:
608 llvm_unreachable("type must be passed explicitly");
609 case Instruction::Call:
610 return getCalledFunction(Operands)->getReturnType();
611 case VPInstruction::BuildVector:
612 assert(VectorType::isValidElementType(Op0Ty) &&
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) ||
625 is_contained(Set: {VPInstruction::FirstOrderRecurrenceSplice,
626 VPInstruction::BuildVector,
627 VPInstruction::ConcatVectors},
628 Element: Opcode);
629 if (AllOperandsSameType)
630 for (unsigned Idx = 1; Idx != Operands.size(); ++Idx)
631 AssertOperandType(Idx, Op0Ty);
632
633 return Op0Ty;
634}
635
636Type *VPReplicateRecipe::computeScalarType(const Instruction *I,
637 ArrayRef<VPValue *> Operands) {
638 unsigned Opcode = I->getOpcode();
639 if (Instruction::isCast(Opcode) ||
640 is_contained(Range: ArrayRef<unsigned>({Instruction::Load, Instruction::Alloca}),
641 Element: Opcode))
642 return I->getType();
643 return computeScalarTypeForInstruction(Opcode, Operands);
644}
645
646VPInstruction::VPInstruction(unsigned Opcode, ArrayRef<VPValue *> Operands,
647 const VPIRFlags &Flags, const VPIRMetadata &MD,
648 DebugLoc DL, const Twine &Name, Type *ResultTy,
649 const VPIRAttributes &Attrs)
650 : VPRecipeWithIRFlags(
651 VPRecipeBase::VPInstructionSC, Operands,
652 ResultTy ? ResultTy
653 : computeScalarTypeForInstruction(Opcode, Operands),
654 Flags, DL),
655 VPIRMetadata(MD), VPIRAttributes(Attrs), Opcode(Opcode),
656 Name(Name.str()) {
657 assert(flagsValidForOpcode(getOpcode()) &&
658 "Set flags not supported for the provided opcode");
659 assert(hasRequiredFlagsForOpcode(getOpcode(), getScalarType()) &&
660 "Opcode requires specific flags to be set");
661 assert((getNumOperandsForOpcode() == -1u ||
662 getNumOperandsForOpcode() == getNumOperands() ||
663 (isMasked() && getNumOperandsForOpcode() + 1 == getNumOperands())) &&
664 "number of operands does not match opcode");
665}
666
667unsigned VPInstruction::getNumOperandsForOpcode() const {
668 if (Instruction::isUnaryOp(Opcode) || Instruction::isCast(Opcode))
669 return 1;
670
671 if (Instruction::isBinaryOp(Opcode))
672 return 2;
673
674 switch (Opcode) {
675 case VPInstruction::StepVector:
676 case VPInstruction::IncomingAliasMask:
677 return 0;
678 case Instruction::Alloca:
679 case Instruction::Freeze:
680 case Instruction::Load:
681 case VPInstruction::BranchOnCond:
682 case VPInstruction::Broadcast:
683 case VPInstruction::ExitingIVValue:
684 case VPInstruction::ExplicitVectorLength:
685 case VPInstruction::ExtractLastLane:
686 case VPInstruction::ExtractLastPart:
687 case VPInstruction::ExtractPenultimateElement:
688 case VPInstruction::MaskedCond:
689 case VPInstruction::Not:
690 case VPInstruction::Reverse:
691 case VPInstruction::Unpack:
692 case VPInstruction::NumActiveLanes:
693 return 1;
694 case Instruction::ICmp:
695 case Instruction::FCmp:
696 case Instruction::ExtractElement:
697 case Instruction::Store:
698 case VPInstruction::ActiveLaneMask:
699 case VPInstruction::BranchOnCount:
700 case VPInstruction::BranchOnTwoConds:
701 case VPInstruction::FirstOrderRecurrenceSplice:
702 case VPInstruction::LogicalAnd:
703 case VPInstruction::LogicalOr:
704 case VPInstruction::PtrAdd:
705 case VPInstruction::WidePtrAdd:
706 case VPInstruction::WideIVStep:
707 case VPInstruction::ResumeForEpilogue:
708 case VPInstruction::ExtractVectorForPart:
709 return 2;
710 case Instruction::InsertElement:
711 case Instruction::Select:
712 case VPInstruction::WideActiveLaneMask:
713 case VPInstruction::ReductionStartVector:
714 case VPInstruction::WideVectorLoad:
715 return 3;
716 case VPInstruction::WideVectorStore:
717 return 4;
718 case Instruction::Call:
719 return getCalledFnOperandIndex(Operands: 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:
727 case VPInstruction::AnyOf:
728 case VPInstruction::BuildVector:
729 case VPInstruction::Intrinsic:
730 case VPInstruction::CanonicalIVIncrementForPart:
731 case VPInstruction::ComputeReductionResult:
732 case VPInstruction::FirstActiveLane:
733 case VPInstruction::LastActiveLane:
734 case VPInstruction::ExtractLane:
735 case VPInstruction::ExtractLastActive:
736 case VPInstruction::ConcatVectors:
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
743bool VPInstruction::doesGeneratePerAllLanes() const {
744 return Opcode == VPInstruction::Unpack ||
745 (Opcode == VPInstruction::PtrAdd && !vputils::onlyFirstLaneUsed(Def: this));
746}
747
748bool VPInstruction::doesGenerateSingleScalar() const {
749 if (isSingleScalar() || isVectorToScalar())
750 return true;
751 switch (Opcode) {
752 case Instruction::Freeze:
753 case Instruction::ICmp:
754 case Instruction::PHI:
755 case Instruction::Select:
756 case VPInstruction::BranchOnCond:
757 case VPInstruction::BranchOnTwoConds:
758 case VPInstruction::BranchOnCount:
759 case VPInstruction::CanonicalIVIncrementForPart:
760 case VPInstruction::PtrAdd:
761 case VPInstruction::ExplicitVectorLength:
762 case VPInstruction::AnyOf:
763 case VPInstruction::Not:
764 return vputils::onlyFirstLaneUsed(Def: this);
765 default:
766 return Instruction::isBinaryOp(Opcode) && vputils::onlyFirstLaneUsed(Def: this);
767 }
768}
769
770static Instruction::BinaryOps getSubRecurOpcode(RecurKind Kind) {
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
782 if (Instruction::isBinaryOp(Opcode: getOpcode())) {
783 Value *A = State.get(Def: getOperand(N: 0), NeedsSingleScalar: GenerateSingleScalar);
784 Value *B = State.get(Def: getOperand(N: 1), NeedsSingleScalar: GenerateSingleScalar);
785 auto *Res =
786 Builder.CreateBinOp(Opc: (Instruction::BinaryOps)getOpcode(), LHS: A, RHS: B, Name);
787 if (auto *I = dyn_cast<Instruction>(Val: Res))
788 applyFlags(I&: *I);
789 return Res;
790 }
791 if (Instruction::isCast(Opcode: getOpcode())) {
792 Value *Op = State.get(Def: getOperand(N: 0), Lane: VPLane(0));
793 Value *Res = State.Builder.CreateCast(Op: Instruction::CastOps(getOpcode()), V: Op,
794 DestTy: getScalarType());
795 if (auto *CastOp = dyn_cast<Instruction>(Val: Res)) {
796 applyFlags(I&: *CastOp);
797 applyMetadata(I&: *CastOp);
798 }
799 return Res;
800 }
801
802 switch (getOpcode()) {
803 case VPInstruction::Not: {
804 Value *A = State.get(Def: getOperand(N: 0), NeedsSingleScalar: GenerateSingleScalar);
805 return Builder.CreateNot(V: A, Name);
806 }
807 case VPInstruction::LogicalAnd: {
808 // TODO: Use IsSingleScalar to produce a scalar value.
809 Value *A = State.get(Def: getOperand(N: 0));
810 Value *B = State.get(Def: getOperand(N: 1));
811 return Builder.CreateLogicalAnd(Cond1: A, Cond2: B, Name);
812 }
813 case VPInstruction::LogicalOr: {
814 // TODO: Use IsSingleScalar to produce a scalar value.
815 Value *A = State.get(Def: getOperand(N: 0));
816 Value *B = State.get(Def: getOperand(N: 1));
817 return Builder.CreateLogicalOr(Cond1: A, Cond2: 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>(Val: getOperand(N: 1)))
824 return State.get(Def: getOperand(N: 0), Lane: VPLane(Idx->getZExtValue()));
825 Value *Vec = State.get(Def: getOperand(N: 0));
826 Value *Idx = State.get(Def: getOperand(N: 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(Def: getOperand(N: 0), /*NeedsSingleScalar=*/false);
834 Value *Elt = State.get(Def: getOperand(N: 1), /*NeedsSingleScalar=*/true);
835 Value *Idx = State.get(Def: getOperand(N: 2), /*NeedsSingleScalar=*/true);
836 return Builder.CreateInsertElement(Vec, NewElt: Elt, Idx, Name);
837 }
838 case Instruction::Freeze: {
839 Value *Op = State.get(Def: getOperand(N: 0), NeedsSingleScalar: GenerateSingleScalar);
840 return Builder.CreateFreeze(V: Op, Name);
841 }
842 case Instruction::FCmp:
843 case Instruction::ICmp: {
844 Value *A = State.get(Def: getOperand(N: 0), NeedsSingleScalar: GenerateSingleScalar);
845 Value *B = State.get(Def: getOperand(N: 1), NeedsSingleScalar: GenerateSingleScalar);
846 return Builder.CreateCmp(Pred: getPredicate(), LHS: A, RHS: 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(Def: getOperand(N: 0), NeedsSingleScalar: GenerateSingleScalar ||
854 vputils::isSingleScalar(VPV: getOperand(N: 0)));
855 Value *Op1 = State.get(Def: getOperand(N: 1), NeedsSingleScalar: GenerateSingleScalar);
856 Value *Op2 = State.get(Def: getOperand(N: 2), NeedsSingleScalar: GenerateSingleScalar);
857 Value *Sel =
858 Builder.CreateSelectFMF(C: Cond, True: Op1, False: Op2, FMFSource: getFastMathFlagsOrNone(), Name);
859 if (auto *I = dyn_cast<Instruction>(Val: Sel))
860 applyMetadata(I&: *I);
861 return Sel;
862 }
863 case VPInstruction::ActiveLaneMask:
864 case VPInstruction::WideActiveLaneMask: {
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(Def: getOperand(N: 0), Lane: VPLane(0));
869 // Get the original loop tripcount.
870 Value *ScalarTC = State.get(Def: getOperand(N: 1), Lane: VPLane(0));
871
872 uint64_t Multiplier =
873 getOpcode() == VPInstruction::WideActiveLaneMask
874 ? cast<VPConstantInt>(Val: getOperand(N: 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(Pred: CmpInst::Predicate::ICMP_ULT, LHS: VIVElem0, RHS: ScalarTC,
881 Name);
882
883 auto *PredTy = VectorType::get(ElementType: Builder.getInt1Ty(), EC: State.VF * Multiplier);
884 return Builder.CreateIntrinsic(ID: Intrinsic::get_active_lane_mask,
885 OverloadTypes: {PredTy, ScalarTC->getType()},
886 Args: {VIVElem0, ScalarTC}, FMFSource: nullptr, Name);
887 }
888 case VPInstruction::NumActiveLanes: {
889 assert(GenerateSingleScalar &&
890 "Can only generate first lane for NumActiveLanes");
891 Value *Op = State.get(Def: getOperand(N: 0));
892 auto *VecTy = cast<VectorType>(Val: 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 Op: Instruction::ZExt, V: Op, DestTy: VectorType::get(ElementType: Ty, EC: VecTy->getElementCount()));
899 Value *NumActive =
900 Builder.CreateUnaryIntrinsic(ID: Intrinsic::vector_reduce_add, Op: ZExt);
901 return NumActive;
902 }
903 case VPInstruction::FirstOrderRecurrenceSplice: {
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(Def: getOperand(N: 0));
917 if (!V1->getType()->isVectorTy())
918 return V1;
919 Value *V2 = State.get(Def: getOperand(N: 1));
920 return Builder.CreateVectorSpliceRight(V1, V2, Offset: 1, Name);
921 }
922 case VPInstruction::ExplicitVectorLength: {
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(Def: getOperand(N: 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(C: State.VF.getKnownMinValue());
934
935 Value *EVL = Builder.CreateIntrinsic(
936 RetTy: Builder.getInt32Ty(), ID: Intrinsic::experimental_get_vector_length,
937 Args: {AVL, VFArg, Builder.getTrue()});
938 return EVL;
939 }
940 case VPInstruction::BranchOnCond: {
941 assert(GenerateSingleScalar &&
942 "Can only generate first lane for BranchOnCond");
943 Value *Cond = State.get(Def: getOperand(N: 0), Lane: 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>(Val: getParent()->getSuccessors()[1]);
950 BasicBlock *SecondIRSucc = State.CFG.VPBB2IRBB.lookup(Val: SecondVPSucc);
951 BasicBlock *IRBB = State.CFG.VPBB2IRBB[getParent()];
952 auto *Br = Builder.CreateCondBr(Cond, True: IRBB, False: SecondIRSucc);
953 // First successor is always forward, reset it to nullptr.
954 Br->setSuccessor(idx: 0, NewSucc: nullptr);
955 IRBB->getTerminator()->eraseFromParent();
956 applyMetadata(I&: *Br);
957 return Br;
958 }
959 case VPInstruction::Broadcast: {
960 assert(!GenerateSingleScalar &&
961 "Cannot generate scalar value for Broadcast");
962 return Builder.CreateVectorSplat(
963 EC: State.VF, V: State.get(Def: getOperand(N: 0), /*NeedsSingleScalar=*/true),
964 Name: "broadcast");
965 }
966 case VPInstruction::BuildVector: {
967 assert(!GenerateSingleScalar &&
968 "Cannot generate scalar value for BuildVector");
969 Value *Res = PoisonValue::get(
970 T: FixedVectorType::get(ElementType: getScalarType(), NumElts: getNumOperands()));
971 for (const auto &[Idx, Op] : enumerate(First: operands()))
972 Res = Builder.CreateInsertElement(Vec: Res, NewElt: State.get(Def: Op, NeedsSingleScalar: true),
973 Idx: Builder.getInt64(C: Idx));
974 return Res;
975 }
976 case VPInstruction::ConcatVectors: {
977 Type *ScalarTy = getScalarType();
978 auto *WideTy = VectorType::get(ElementType: ScalarTy, EC: State.VF * getNumOperands());
979 Value *Res = PoisonValue::get(T: WideTy);
980 for (const auto &[Idx, Op] : enumerate(First: operands()))
981 Res = Builder.CreateInsertVector(DstType: WideTy, SrcVec: Res, SubVec: State.get(Def: Op),
982 Idx: Idx * State.VF.getKnownMinValue());
983 return Res;
984 }
985 case VPInstruction::ReductionStartVector: {
986 if (State.VF.isScalar())
987 return State.get(Def: getOperand(N: 0), NeedsSingleScalar: true);
988 IRBuilderBase::FastMathFlagGuard FMFG(Builder);
989 Builder.setFastMathFlags(getFastMathFlagsOrNone());
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 RHS: cast<VPConstantInt>(Val: getOperand(N: 2))->getZExtValue());
994 auto *Iden = Builder.CreateVectorSplat(EC: VF, V: State.get(Def: getOperand(N: 1), NeedsSingleScalar: true));
995 return Builder.CreateInsertElement(Vec: Iden, NewElt: State.get(Def: getOperand(N: 0), NeedsSingleScalar: true),
996 Idx: Builder.getInt64(C: 0));
997 }
998 case VPInstruction::ComputeReductionResult: {
999 assert(GenerateSingleScalar &&
1000 "Can only generate first lane for ComputeReductionResult");
1001 RecurKind RK = getRecurKind();
1002 bool IsOrdered = isReductionOrdered();
1003 bool IsInLoop = isReductionInLoop();
1004 assert(!RecurrenceDescriptor::isFindIVRecurrenceKind(RK) &&
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(Def: getOperand(N: Part), NeedsSingleScalar: IsInLoop);
1012
1013 IRBuilderBase::FastMathFlagGuard FMFG(Builder);
1014 Builder.setFastMathFlags(getFastMathFlagsOrNone());
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];
1024 if (RecurrenceDescriptor::isMinMaxRecurrenceKind(Kind: RK))
1025 ReducedPartRdx = createMinMaxOp(Builder, RK, Left: ReducedPartRdx, Right: 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 =
1030 RecurrenceDescriptor::isSubRecurrenceKind(Kind: RK)
1031 ? getSubRecurOpcode(Kind: RK)
1032 : (Instruction::BinaryOps)RecurrenceDescriptor::getOpcode(Kind: RK);
1033 ReducedPartRdx =
1034 Builder.CreateBinOp(Opc: Opcode, LHS: RdxPart, RHS: ReducedPartRdx, Name: "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(B&: Builder, Src: ReducedPartRdx, RdxKind: RK);
1046 }
1047
1048 return ReducedPartRdx;
1049 }
1050 case VPInstruction::ExtractLastLane:
1051 case VPInstruction::ExtractPenultimateElement: {
1052 assert(GenerateSingleScalar &&
1053 "Can only generate first lane for ExtractLane and "
1054 "ExtractPenultimateElement");
1055 unsigned Offset =
1056 getOpcode() == VPInstruction::ExtractPenultimateElement ? 2 : 1;
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(Def: getOperand(N: 0), Lane: VPLane::getLaneFromEnd(VF: 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(Def: getOperand(N: 0));
1067 }
1068 if (isa<ExtractElementInst>(Val: 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(Def: getOperand(N: 0), Lane: VPLane(0));
1075 Value *Addend = State.get(Def: getOperand(N: 1), Lane: VPLane(0));
1076 // TODO: Require that offset matches index type in VPlan.
1077 Addend = Builder.CreateSExtOrTrunc(
1078 V: Addend, DestTy: Builder.getDataLayout().getIndexType(PtrTy: Ptr->getType()));
1079 return Builder.CreatePtrAdd(Ptr, Offset: Addend, Name, NW: getGEPNoWrapFlags());
1080 }
1081 case VPInstruction::WidePtrAdd: {
1082 assert(!GenerateSingleScalar &&
1083 "Cannot generate scalar value for WidePtrAdd");
1084 Value *Ptr =
1085 State.get(Def: getOperand(N: 0), NeedsSingleScalar: vputils::isSingleScalar(VPV: getOperand(N: 0)));
1086 Value *Addend = State.get(Def: getOperand(N: 1));
1087 return Builder.CreatePtrAdd(Ptr, Offset: Addend, Name, NW: getGEPNoWrapFlags());
1088 }
1089 case VPInstruction::AnyOf: {
1090 assert(GenerateSingleScalar && "Can only generate first lane for AnyOf");
1091 Value *Res = State.get(Def: getOperand(N: 0));
1092 for (VPValue *Op : drop_begin(RangeOrContainer: operands()))
1093 Res = Builder.CreateOr(LHS: Res, RHS: State.get(Def: Op));
1094 return State.VF.isScalar() ? Res : Builder.CreateOrReduce(Src: Res);
1095 }
1096 case VPInstruction::ExtractLane: {
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(Def: getOperand(N: 0), NeedsSingleScalar: true);
1102 Type *IdxTy = getOperand(N: 0)->getScalarType();
1103 Value *Res = nullptr;
1104 Value *RuntimeVF = getRuntimeVF(B&: Builder, Ty: IdxTy, VF: State.VF);
1105
1106 for (unsigned Idx = 1; Idx != getNumOperands(); ++Idx) {
1107 Value *VectorStart =
1108 Builder.CreateMul(LHS: RuntimeVF, RHS: ConstantInt::get(Ty: IdxTy, V: Idx - 1));
1109 Value *VectorIdx = Idx == 1
1110 ? LaneToExtract
1111 : Builder.CreateSub(LHS: LaneToExtract, RHS: VectorStart);
1112 Value *Ext = State.VF.isScalar()
1113 ? State.get(Def: getOperand(N: Idx))
1114 : Builder.CreateExtractElement(
1115 Vec: State.get(Def: getOperand(N: Idx)), Idx: VectorIdx);
1116 if (Res) {
1117 Value *Cmp = Builder.CreateICmpUGE(LHS: LaneToExtract, RHS: VectorStart);
1118 Res = Builder.CreateSelect(C: Cmp, True: Ext, False: Res);
1119 } else {
1120 Res = Ext;
1121 }
1122 }
1123 return Res;
1124 }
1125 case VPInstruction::FirstActiveLane: {
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(Def: getOperand(N: 0));
1131 return Builder.CreateCountTrailingZeroElems(ResTy: 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(B&: Builder, Ty, VF: 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 V: Builder.CreateICmpEQ(LHS: State.get(Def: getOperand(N: Idx)),
1145 RHS: Builder.getFalse()),
1146 DestTy: Ty)
1147 : Builder.CreateCountTrailingZeroElems(
1148 ResTy: Ty, Mask: State.get(Def: getOperand(N: Idx)),
1149 /*ZeroIsPoison=*/false, Name);
1150 Value *Current = Builder.CreateAdd(
1151 LHS: Builder.CreateMul(LHS: RuntimeVF, RHS: ConstantInt::get(Ty, V: Idx)),
1152 RHS: TrailingZeros);
1153 if (Res) {
1154 Value *Cmp = Builder.CreateICmpNE(LHS: TrailingZeros, RHS: RuntimeVF);
1155 Res = Builder.CreateSelect(C: Cmp, True: Current, False: Res);
1156 } else {
1157 Res = Current;
1158 }
1159 }
1160
1161 return Res;
1162 }
1163 case VPInstruction::ResumeForEpilogue:
1164 assert(GenerateSingleScalar &&
1165 "Can only generate first lane for ResumeForEpilogue");
1166 return State.get(Def: getOperand(N: 0), NeedsSingleScalar: true);
1167 case VPInstruction::Reverse:
1168 assert(!GenerateSingleScalar && "Cannot generate scalar value for Reverse");
1169 return Builder.CreateVectorReverse(V: State.get(Def: getOperand(N: 0)), Name: "reverse");
1170 case VPInstruction::ExtractLastActive: {
1171 assert(GenerateSingleScalar &&
1172 "Can only generate first lane for ExtractLastActive");
1173 Value *Result = State.get(Def: getOperand(N: 0), /*NeedsSingleScalar=*/true);
1174 for (unsigned Idx = 1; Idx < getNumOperands(); Idx += 2) {
1175 Value *Data = State.get(Def: getOperand(N: Idx));
1176 Value *Mask = State.get(Def: getOperand(N: Idx + 1));
1177 Type *VTy = Data->getType();
1178
1179 if (State.VF.isScalar())
1180 Result = Builder.CreateSelect(C: Mask, True: Data, False: Result);
1181 else
1182 Result = Builder.CreateIntrinsic(
1183 ID: Intrinsic::experimental_vector_extract_last_active, OverloadTypes: {VTy},
1184 Args: {Data, Mask, Result});
1185 }
1186
1187 return Result;
1188 }
1189 case VPInstruction::ExtractVectorForPart: {
1190 assert(!GenerateSingleScalar &&
1191 "Cannot generate scalar value for ExtractVectorForPart");
1192 Value *Src = State.get(Def: getOperand(N: 0));
1193 Type *DstTy = VectorType::get(ElementType: getScalarType(), EC: State.VF);
1194 uint64_t Part = cast<VPConstantInt>(Val: getOperand(N: 1))->getZExtValue();
1195
1196 if (Src->getType() == DstTy)
1197 return Src;
1198
1199 return Builder.CreateExtractVector(
1200 DstType: DstTy, SrcVec: Src, Idx: Builder.getInt64(C: State.VF.getKnownMinValue() * Part), Name);
1201 }
1202 case VPInstruction::StepVector:
1203 assert(!GenerateSingleScalar &&
1204 "Cannot generate scalar value for StepVector");
1205 return State.Builder.CreateStepVector(
1206 DstType: VectorType::get(ElementType: getScalarType(), EC: State.VF));
1207 case VPInstruction::Intrinsic: {
1208 assert(GenerateSingleScalar &&
1209 "Can only generate first lane for Intrinsic");
1210 SmallVector<Value *, 2> Args;
1211 for (VPValue *Op : drop_end(RangeOrContainer: operands()))
1212 Args.push_back(Elt: State.get(Def: Op, /*NeedsSingleScalar=*/true));
1213 return State.Builder.CreateIntrinsic(RetTy: getScalarType(),
1214 ID: vputils::getIntrinsicID(R: this), Args,
1215 /*FMFSource=*/nullptr, Name: getName());
1216 }
1217 case VPInstruction::WideVectorLoad: {
1218 unsigned Multiplier = cast<VPConstantInt>(Val: getOperand(N: 0))->getZExtValue();
1219 auto *WideDataTy = VectorType::get(ElementType: getScalarType(), EC: State.VF * Multiplier);
1220
1221 Value *Addr = State.get(Def: getOperand(N: 1), /*IsScalar=*/NeedsSingleScalar: true);
1222 Align Alignment = Align(cast<VPConstantInt>(Val: getOperand(N: 2))->getZExtValue());
1223 Instruction *WideLI;
1224 if (isMasked()) {
1225 Value *Mask = State.get(Def: getMask());
1226 WideLI = Builder.CreateMaskedLoad(Ty: WideDataTy, Ptr: Addr, Alignment, Mask);
1227 } else {
1228 WideLI = Builder.CreateAlignedLoad(Ty: WideDataTy, Ptr: Addr, Align: Alignment);
1229 }
1230 applyMetadata(I&: *WideLI);
1231 return WideLI;
1232 }
1233 case VPInstruction::WideVectorStore: {
1234 unsigned Multiplier = cast<VPConstantInt>(Val: getOperand(N: 0))->getZExtValue();
1235 Value *WideData = State.get(Def: getOperand(N: 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(Def: getOperand(N: 1), /*IsScalar=*/NeedsSingleScalar: true);
1242 Align Alignment = Align(cast<VPConstantInt>(Val: getOperand(N: 2))->getZExtValue());
1243 Instruction *WideSI;
1244 if (isMasked()) {
1245 Value *Mask = State.get(Def: getMask());
1246 WideSI = Builder.CreateMaskedStore(Val: WideData, Ptr: Addr, Alignment, Mask);
1247 } else {
1248 WideSI = Builder.CreateAlignedStore(Val: WideData, Ptr: Addr, Align: Alignment);
1249 }
1250 applyMetadata(I&: *WideSI);
1251 return WideSI;
1252 }
1253 case VPInstruction::MaskedCond:
1254 llvm_unreachable("Should have been lowered in VPlanPredicator");
1255 default:
1256 llvm_unreachable("Unsupported opcode for instruction");
1257 }
1258}
1259
1260InstructionCost VPRecipeWithIRFlags::getCostForRecipeWithOpcode(
1261 unsigned Opcode, ElementCount VF, VPCostContext &Ctx) const {
1262 Type *ScalarTy = this->getScalarType();
1263 Type *ResultTy = VF.isVector() ? toVectorTy(Scalar: ScalarTy, EC: VF) : ScalarTy;
1264 switch (Opcode) {
1265 case Instruction::FNeg:
1266 return Ctx.TTI.getArithmeticInstrCost(Opcode, Ty: ResultTy, CostKind: 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(N: 1);
1288 TargetTransformInfo::OperandValueInfo RHSInfo = Ctx.getOperandInfo(V: RHS);
1289
1290 if (RHSInfo.Kind == TargetTransformInfo::OK_AnyValue &&
1291 getOperand(N: 1)->isDefinedOutsideLoopRegions())
1292 RHSInfo.Kind = TargetTransformInfo::OK_UniformValue;
1293
1294 Instruction *CtxI = dyn_cast_or_null<Instruction>(Val: getUnderlyingValue());
1295 SmallVector<const Value *, 4> Operands;
1296 if (CtxI)
1297 Operands.append(in_start: CtxI->value_op_begin(), in_end: CtxI->value_op_end());
1298 return Ctx.TTI.getArithmeticInstrCost(
1299 Opcode, Ty: ResultTy, CostKind: Ctx.CostKind,
1300 Opd1Info: {.Kind: TargetTransformInfo::OK_AnyValue, .Properties: TargetTransformInfo::OP_None},
1301 Opd2Info: RHSInfo, Args: Operands, CtxI, TLibInfo: &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(Opcode: Instruction::ExtractValue,
1312 CostKind: Ctx.CostKind);
1313 case Instruction::ICmp:
1314 case Instruction::FCmp: {
1315 Type *ScalarOpTy = getOperand(N: 0)->getScalarType();
1316 Type *OpTy = VF.isVector() ? toVectorTy(Scalar: ScalarOpTy, EC: VF) : ScalarOpTy;
1317 Instruction *CtxI = dyn_cast_or_null<Instruction>(Val: getUnderlyingValue());
1318 return Ctx.TTI.getCmpSelInstrCost(
1319 Opcode, ValTy: OpTy, CondTy: CmpInst::makeCmpResultType(opnd_type: OpTy), VecPred: getPredicate(),
1320 CostKind: Ctx.CostKind, Op1Info: {.Kind: TTI::OK_AnyValue, .Properties: TTI::OP_None},
1321 Op2Info: {.Kind: TTI::OK_AnyValue, .Properties: TTI::OP_None}, I: 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>(Val: R))
1345 return TTI::CastContextHint::Interleave;
1346 if (const auto *ReplicateRecipe = dyn_cast<VPReplicateRecipe>(Val: 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>(Val: ReplicateRecipe->getUnderlyingValue());
1350 if (!isa<LoadInst, StoreInst>(Val: UI))
1351 return TTI::CastContextHint::None;
1352 return ReplicateRecipe->isPredicated() ? TTI::CastContextHint::Masked
1353 : TTI::CastContextHint::Normal;
1354 }
1355 const auto *WidenMemoryRecipe = dyn_cast<VPWidenMemoryRecipe>(Val: R);
1356 if (WidenMemoryRecipe == nullptr)
1357 return TTI::CastContextHint::None;
1358 if (VF.isScalar())
1359 return TTI::CastContextHint::Normal;
1360 if (!WidenMemoryRecipe->isConsecutive())
1361 return TTI::CastContextHint::GatherScatter;
1362 if (WidenMemoryRecipe->isMasked())
1363 return TTI::CastContextHint::Masked;
1364 return TTI::CastContextHint::Normal;
1365 };
1366
1367 VPValue *Operand = getOperand(N: 0);
1368 TTI::CastContextHint CCH = TTI::CastContextHint::None;
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>(Val: getSingleUser())) {
1373 if (match(V: Recipe,
1374 P: m_CombineOr(
1375 Ps: m_Reverse(Op0: m_VPValue()),
1376 Ps: m_Intrinsic<Intrinsic::experimental_vp_reverse>()))) {
1377 IsReverse = true;
1378 Recipe = cast_or_null<VPRecipeBase>(
1379 Val: 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(V: Recipe,
1391 P: m_CombineOr(Ps: m_Reverse(Op0: m_VPValue(V&: ReverseOp)),
1392 Ps: m_Intrinsic<Intrinsic::experimental_vp_reverse>(
1393 Ops: m_VPValue(V&: 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)
1402 CCH = TTI::CastContextHint::Reversed;
1403
1404 auto *ScalarSrcTy = Operand->getScalarType();
1405 Type *SrcTy = VF.isVector() ? toVectorTy(Scalar: ScalarSrcTy, EC: VF) : ScalarSrcTy;
1406 // Arm TTI will use the underlying instruction to determine the cost.
1407 return Ctx.TTI.getCastInstrCost(
1408 Opcode, Dst: ResultTy, Src: SrcTy, CCH, CostKind: Ctx.CostKind,
1409 I: dyn_cast_if_present<Instruction>(Val: getUnderlyingValue()));
1410 }
1411 case Instruction::Select: {
1412 SelectInst *SI = cast_or_null<SelectInst>(Val: getUnderlyingValue());
1413 bool IsScalarCond = getOperand(N: 0)->isDefinedOutsideLoopRegions();
1414 Type *ScalarTy = this->getScalarType();
1415
1416 VPValue *Op0, *Op1;
1417 bool IsLogicalAnd =
1418 match(V: this, P: m_c_LogicalAnd(Op0: m_VPValue(V&: Op0), Op1: m_VPValue(V&: Op1)));
1419 bool IsLogicalOr =
1420 match(V: this, P: m_c_LogicalOr(Op0: m_VPValue(V&: Op0), Op1: m_VPValue(V&: 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(V: this, P: m_Select(Op0: m_VPValue(V&: Op0), Op1: m_False(), Op2: m_VPValue(V&: Op1)));
1426 IsLogicalOr |=
1427 match(V: this, P: m_Select(Op0: m_VPValue(V&: Op0), Op1: m_VPValue(V&: Op1), Op2: 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(V: Op0);
1434 const auto [Op2VK, Op2VP] = Ctx.getOperandInfo(V: Op1);
1435
1436 SmallVector<const Value *, 2> Operands;
1437 if (SI && all_of(Range: operands(),
1438 P: [](VPValue *Op) { return Op->getUnderlyingValue(); }))
1439 append_range(C&: Operands, R: SI->operands());
1440 return Ctx.TTI.getArithmeticInstrCost(
1441 Opcode: IsLogicalOr ? Instruction::Or : Instruction::And, Ty: ResultTy,
1442 CostKind: Ctx.CostKind, Opd1Info: {.Kind: Op1VK, .Properties: Op1VP}, Opd2Info: {.Kind: Op2VK, .Properties: Op2VP}, Args: Operands, CtxI: SI);
1443 }
1444
1445 Type *CondTy = getOperand(N: 0)->getScalarType();
1446 if (!IsScalarCond && VF.isVector())
1447 CondTy = VectorType::get(ElementType: CondTy, EC: VF);
1448
1449 llvm::CmpPredicate Pred;
1450 if (!match(V: getOperand(N: 0), P: m_Cmp(Pred, Op0: m_VPValue(), Op1: m_VPValue())))
1451 if (auto *CondIRV = dyn_cast<VPIRValue>(Val: getOperand(N: 0)))
1452 if (auto *Cmp = dyn_cast<CmpInst>(Val: CondIRV->getValue()))
1453 Pred = Cmp->getPredicate();
1454 Type *VectorTy = toVectorTy(Scalar: this->getScalarType(), EC: VF);
1455 return Ctx.TTI.getCmpSelInstrCost(
1456 Opcode: Instruction::Select, ValTy: VectorTy, CondTy, VecPred: Pred, CostKind: Ctx.CostKind,
1457 Op1Info: {.Kind: TTI::OK_AnyValue, .Properties: TTI::OP_None}, Op2Info: {.Kind: TTI::OK_AnyValue, .Properties: TTI::OP_None}, I: SI);
1458 }
1459 }
1460 llvm_unreachable("called for unsupported opcode");
1461}
1462
1463InstructionCost VPInstruction::computeCost(ElementCount VF,
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.
1468 if (Instruction::isCast(Opcode: getOpcode())) {
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(V: this, P: m_ZExtOrTrunc(Op0: m_EVL(Op0: m_VPValue()))))
1473 return 0;
1474 return getCostForRecipeWithOpcode(Opcode: getOpcode(), VF: ElementCount::getFixed(MinVal: 1),
1475 Ctx);
1476 }
1477
1478 if (Instruction::isBinaryOp(Opcode: getOpcode())) {
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
1485 assert(!doesGeneratePerAllLanes() &&
1486 "Should only generate a vector value or single scalar, not scalars "
1487 "for all lanes.");
1488 return getCostForRecipeWithOpcode(
1489 Opcode: getOpcode(),
1490 VF: vputils::onlyFirstLaneUsed(Def: this) ? ElementCount::getFixed(MinVal: 1) : VF, Ctx);
1491 }
1492
1493 switch (getOpcode()) {
1494 case Instruction::Select: {
1495 llvm::CmpPredicate Pred = CmpInst::BAD_ICMP_PREDICATE;
1496 match(V: getOperand(N: 0), P: m_Cmp(Pred, Op0: m_VPValue(), Op1: m_VPValue()));
1497 auto *CondTy = getOperand(N: 0)->getScalarType();
1498 auto *VecTy = getOperand(N: 1)->getScalarType();
1499 if (!vputils::onlyFirstLaneUsed(Def: this)) {
1500 CondTy = toVectorTy(Scalar: CondTy, EC: VF);
1501 VecTy = toVectorTy(Scalar: VecTy, EC: VF);
1502 }
1503 return Ctx.TTI.getCmpSelInstrCost(Opcode: Instruction::Select, ValTy: VecTy, CondTy, VecPred: Pred,
1504 CostKind: Ctx.CostKind);
1505 }
1506 case Instruction::ExtractElement:
1507 case VPInstruction::ExtractLane: {
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(Scalar: getScalarType(), EC: VF);
1516 return Ctx.TTI.getVectorInstrCost(Opcode: Instruction::ExtractElement, Val: VecTy,
1517 CostKind: Ctx.CostKind);
1518 }
1519 case VPInstruction::AnyOf: {
1520 auto *VecTy = toVectorTy(Scalar: this->getScalarType(), EC: VF);
1521 return Ctx.TTI.getArithmeticReductionCost(
1522 Opcode: Instruction::Or, Ty: cast<VectorType>(Val: VecTy), FMF: std::nullopt, CostKind: Ctx.CostKind);
1523 }
1524 case VPInstruction::FirstActiveLane: {
1525 Type *Ty = this->getScalarType();
1526 Type *ScalarTy = getOperand(N: 0)->getScalarType();
1527 if (VF.isScalar())
1528 return Ctx.TTI.getCmpSelInstrCost(Opcode: Instruction::ICmp, ValTy: ScalarTy,
1529 CondTy: CmpInst::makeCmpResultType(opnd_type: ScalarTy),
1530 VecPred: CmpInst::ICMP_EQ, CostKind: Ctx.CostKind);
1531 // Calculate the cost of determining the lane index.
1532 auto *PredTy = toVectorTy(Scalar: ScalarTy, EC: VF);
1533 IntrinsicCostAttributes Attrs(Intrinsic::experimental_cttz_elts, Ty,
1534 {PredTy, Type::getInt1Ty(C&: Ctx.LLVMCtx)});
1535 return Ctx.TTI.getIntrinsicInstrCost(ICA: Attrs, CostKind: Ctx.CostKind);
1536 }
1537 case VPInstruction::LastActiveLane: {
1538 Type *Ty = this->getScalarType();
1539 Type *ScalarTy = getOperand(N: 0)->getScalarType();
1540 if (VF.isScalar())
1541 return Ctx.TTI.getCmpSelInstrCost(Opcode: Instruction::ICmp, ValTy: ScalarTy,
1542 CondTy: CmpInst::makeCmpResultType(opnd_type: ScalarTy),
1543 VecPred: CmpInst::ICMP_EQ, CostKind: Ctx.CostKind);
1544 // Calculate the cost of determining the lane index: NOT + cttz_elts + SUB.
1545 auto *PredTy = toVectorTy(Scalar: ScalarTy, EC: VF);
1546 IntrinsicCostAttributes Attrs(Intrinsic::experimental_cttz_elts, Ty,
1547 {PredTy, Type::getInt1Ty(C&: Ctx.LLVMCtx)});
1548 InstructionCost Cost = Ctx.TTI.getIntrinsicInstrCost(ICA: Attrs, CostKind: Ctx.CostKind);
1549 // Add cost of NOT operation on the predicate.
1550 Cost += Ctx.TTI.getArithmeticInstrCost(
1551 Opcode: Instruction::Xor, Ty: PredTy, CostKind: Ctx.CostKind,
1552 Opd1Info: {.Kind: TargetTransformInfo::OK_AnyValue, .Properties: TargetTransformInfo::OP_None},
1553 Opd2Info: {.Kind: TargetTransformInfo::OK_UniformConstantValue,
1554 .Properties: TargetTransformInfo::OP_None});
1555 // Add cost of SUB operation on the index.
1556 Cost += Ctx.TTI.getArithmeticInstrCost(Opcode: Instruction::Sub, Ty, CostKind: Ctx.CostKind);
1557 return Cost;
1558 }
1559 case VPInstruction::ExtractLastActive: {
1560 Type *ScalarTy = this->getScalarType();
1561 Type *VecTy = toVectorTy(Scalar: ScalarTy, EC: VF);
1562 Type *MaskTy = toVectorTy(Scalar: Type::getInt1Ty(C&: Ctx.LLVMCtx), EC: VF);
1563 IntrinsicCostAttributes ICA(
1564 Intrinsic::experimental_vector_extract_last_active, ScalarTy,
1565 {VecTy, MaskTy, ScalarTy});
1566 return Ctx.TTI.getIntrinsicInstrCost(ICA, CostKind: Ctx.CostKind);
1567 }
1568 case VPInstruction::FirstOrderRecurrenceSplice: {
1569 assert(VF.isVector() && "Scalar FirstOrderRecurrenceSplice?");
1570 Type *VectorTy = toVectorTy(Scalar: this->getScalarType(), EC: VF);
1571 return Ctx.TTI.getShuffleCost(
1572 Kind: TargetTransformInfo::SK_Splice, DstTy: cast<VectorType>(Val: VectorTy),
1573 SrcTy: cast<VectorType>(Val: VectorTy), CostKind: Ctx.CostKind, Mask: {}, Index: -1);
1574 }
1575 case VPInstruction::ActiveLaneMask:
1576 case VPInstruction::WideActiveLaneMask: {
1577 Type *ArgTy = getOperand(N: 0)->getScalarType();
1578 uint64_t Multiplier =
1579 getOpcode() == VPInstruction::WideActiveLaneMask
1580 ? cast<VPConstantInt>(Val: getOperand(N: 2))->getZExtValue()
1581 : 1;
1582 Type *RetTy = toVectorTy(Scalar: Type::getInt1Ty(C&: Ctx.LLVMCtx), EC: VF * Multiplier);
1583 IntrinsicCostAttributes Attrs(Intrinsic::get_active_lane_mask, RetTy,
1584 {ArgTy, ArgTy});
1585 return Ctx.TTI.getIntrinsicInstrCost(ICA: Attrs, CostKind: Ctx.CostKind);
1586 }
1587 case VPInstruction::ExplicitVectorLength: {
1588 Type *Arg0Ty = getOperand(N: 0)->getScalarType();
1589 Type *I32Ty = Type::getInt32Ty(C&: Ctx.LLVMCtx);
1590 Type *I1Ty = Type::getInt1Ty(C&: Ctx.LLVMCtx);
1591 IntrinsicCostAttributes Attrs(Intrinsic::experimental_get_vector_length,
1592 I32Ty, {Arg0Ty, I32Ty, I1Ty});
1593 return Ctx.TTI.getIntrinsicInstrCost(ICA: Attrs, CostKind: Ctx.CostKind);
1594 }
1595 case VPInstruction::Reverse: {
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(BitWidth: 1))
1602 return 0;
1603 auto *VectorTy = cast<VectorType>(Val: toVectorTy(Scalar: EltTy, EC: VF));
1604 return Ctx.TTI.getShuffleCost(Kind: TargetTransformInfo::SK_Reverse, DstTy: VectorTy,
1605 SrcTy: VectorTy, CostKind: Ctx.CostKind, /*Mask=*/{},
1606 /*Index=*/0);
1607 }
1608 case VPInstruction::ExtractLastLane: {
1609 // Add on the cost of extracting the element.
1610 auto *VecTy = toVectorTy(Scalar: getOperand(N: 0)->getScalarType(), EC: VF);
1611 return Ctx.TTI.getIndexedVectorInstrCostFromEnd(Opcode: Instruction::ExtractElement,
1612 Val: VecTy, CostKind: Ctx.CostKind, Index: 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, P: m_BranchOnCond(Op0: m_VPValue())))
1619 return 0;
1620 if (!vputils::onlyFirstLaneUsed(Def: this))
1621 ValTy = toVectorTy(Scalar: ValTy, EC: VF);
1622 return Ctx.TTI.getArithmeticInstrCost(Opcode: Instruction::Xor, Ty: ValTy,
1623 CostKind: Ctx.CostKind);
1624 }
1625 case VPInstruction::NumActiveLanes: {
1626 Type *ElementTy = getOperand(N: 0)->getScalarType();
1627 auto *MaskTy = cast<VectorType>(Val: toVectorTy(Scalar: ElementTy, EC: VF));
1628 return Ctx.TTI.getExtendedReductionCost(
1629 Opcode: Instruction::Add, /*IsUnsigned=*/true, ResTy: getScalarType(), Ty: MaskTy,
1630 /*FMF=*/{}, CostKind: Ctx.CostKind);
1631 }
1632 case VPInstruction::BranchOnCount: {
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(Plan: *getParent()->getPlan(), VF))
1642 return 0;
1643 // Otherwise BranchOnCount generates ICmpEQ followed by a branch.
1644 Type *ValTy = getOperand(N: 0)->getScalarType();
1645 return Ctx.TTI.getCmpSelInstrCost(Opcode: Instruction::ICmp, ValTy,
1646 CondTy: CmpInst::makeCmpResultType(opnd_type: ValTy),
1647 VecPred: CmpInst::ICMP_EQ, CostKind: Ctx.CostKind);
1648 }
1649 case VPInstruction::Intrinsic: {
1650 Type *Ty = getScalarType();
1651 SmallVector<Type *, 2> ArgTys;
1652 for (const VPValue *Op : drop_end(RangeOrContainer: operands()))
1653 ArgTys.push_back(Elt: Op->getScalarType());
1654 IntrinsicCostAttributes Attrs(vputils::getIntrinsicID(R: this), Ty, ArgTys);
1655 return Ctx.TTI.getIntrinsicInstrCost(ICA: Attrs, CostKind: Ctx.CostKind);
1656 }
1657 case VPInstruction::StepVector:
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;
1664 case VPInstruction::WideIVStep:
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:
1670 return getCostForRecipeWithOpcode(
1671 Opcode: getOpcode(),
1672 VF: vputils::onlyFirstLaneUsed(Def: this) ? ElementCount::getFixed(MinVal: 1) : VF, Ctx);
1673 case VPInstruction::ExtractPenultimateElement:
1674 if (VF == ElementCount::getScalable(MinVal: 1))
1675 return InstructionCost::getInvalid();
1676 [[fallthrough]];
1677 default:
1678 // TODO: Compute cost other VPInstructions once the legacy cost model has
1679 // been retired.
1680 assert(!getUnderlyingValue() &&
1681 "unexpected VPInstruction witht underlying value");
1682 return 0;
1683 }
1684}
1685
1686bool VPInstruction::isVectorToScalar() const {
1687 return getOpcode() == VPInstruction::ExtractLastLane ||
1688 getOpcode() == VPInstruction::ExtractPenultimateElement ||
1689 getOpcode() == Instruction::ExtractElement ||
1690 getOpcode() == VPInstruction::ExtractLane ||
1691 getOpcode() == VPInstruction::FirstActiveLane ||
1692 getOpcode() == VPInstruction::LastActiveLane ||
1693 getOpcode() == VPInstruction::ExtractLastActive ||
1694 getOpcode() == VPInstruction::ComputeReductionResult ||
1695 getOpcode() == VPInstruction::AnyOf ||
1696 getOpcode() == VPInstruction::NumActiveLanes;
1697}
1698
1699bool VPInstruction::isSingleScalar() const {
1700 switch (getOpcode()) {
1701 case Instruction::Load:
1702 case Instruction::PHI:
1703 case VPInstruction::ExplicitVectorLength:
1704 case VPInstruction::ResumeForEpilogue:
1705 case VPInstruction::Intrinsic:
1706 return true;
1707 default:
1708 return Instruction::isCast(Opcode: getOpcode());
1709 }
1710}
1711
1712void VPInstruction::addOperand(VPValue *Op) {
1713#ifndef NDEBUG
1714 Type *Ty = Op->getScalarType();
1715 switch (getOpcode()) {
1716 case VPInstruction::AnyOf:
1717 case VPInstruction::FirstActiveLane:
1718 case VPInstruction::LastActiveLane:
1719 assert(Ty == getOperand(0)->getScalarType() &&
1720 "types of operand 0 and new operand must match");
1721 break;
1722 case VPInstruction::ComputeReductionResult:
1723 case VPInstruction::BuildVector:
1724 case VPInstruction::ConcatVectors:
1725 assert(Ty == getOperand(0)->getScalarType() &&
1726 "appended operand must match operand 0's scalar type");
1727 break;
1728 case VPInstruction::ExtractLane:
1729 assert(Ty == getOperand(1)->getScalarType() &&
1730 "appended operand must match operand 1's scalar type");
1731 break;
1732 case VPInstruction::ExtractLastActive: {
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
1750 VPUser::addOperand(Operand: Op);
1751}
1752
1753void VPInstruction::execute(VPTransformState &State) {
1754 assert(!isAbstract() && "cannot execute this VPInstruction");
1755 IRBuilderBase::FastMathFlagGuard FMFGuard(State.Builder);
1756 assert(flagsValidForOpcode(getOpcode()) &&
1757 "Set flags not supported for the provided opcode");
1758 assert(hasRequiredFlagsForOpcode(getOpcode(), getScalarType()) &&
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(Def: this, V: GeneratedValue, IsScalar: GenerateSingleScalar);
1769 if (getOpcode() == VPInstruction::ResumeForEpilogue ||
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
1779bool VPInstruction::opcodeMayReadOrWriteFromMemory() const {
1780 if (Instruction::isBinaryOp(Opcode: getOpcode()) ||
1781 Instruction::isUnaryOp(Opcode: getOpcode()) || Instruction::isCast(Opcode: getOpcode()))
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:
1793 case VPInstruction::AnyOf:
1794 case VPInstruction::BranchOnCond:
1795 case VPInstruction::BranchOnTwoConds:
1796 case VPInstruction::BranchOnCount:
1797 case VPInstruction::Broadcast:
1798 case VPInstruction::BuildVector:
1799 case VPInstruction::ConcatVectors:
1800 case VPInstruction::CanonicalIVIncrementForPart:
1801 case VPInstruction::ComputeReductionResult:
1802 case VPInstruction::ExtractLane:
1803 case VPInstruction::ExtractLastLane:
1804 case VPInstruction::ExtractLastPart:
1805 case VPInstruction::ExtractPenultimateElement:
1806 case VPInstruction::ActiveLaneMask:
1807 case VPInstruction::WideActiveLaneMask:
1808 case VPInstruction::IncomingAliasMask:
1809 case VPInstruction::ExitingIVValue:
1810 case VPInstruction::ExplicitVectorLength:
1811 case VPInstruction::FirstActiveLane:
1812 case VPInstruction::LastActiveLane:
1813 case VPInstruction::ExtractLastActive:
1814 case VPInstruction::ExtractVectorForPart:
1815 case VPInstruction::FirstOrderRecurrenceSplice:
1816 case VPInstruction::LogicalAnd:
1817 case VPInstruction::LogicalOr:
1818 case VPInstruction::MaskedCond:
1819 case VPInstruction::Not:
1820 case VPInstruction::PtrAdd:
1821 case VPInstruction::WideIVStep:
1822 case VPInstruction::WidePtrAdd:
1823 case VPInstruction::StepVector:
1824 case VPInstruction::ReductionStartVector:
1825 case VPInstruction::Reverse:
1826 case VPInstruction::Unpack:
1827 case VPInstruction::NumActiveLanes:
1828 return false;
1829 case VPInstruction::Intrinsic:
1830 case Instruction::Call:
1831 return !getMemoryEffects(CalleeFnAttrs: getCalleeFnAttrs(VPI: *this)).doesNotAccessMemory();
1832 default:
1833 return true;
1834 }
1835}
1836
1837bool VPInstruction::usesFirstLaneOnly(const VPValue *Op) const {
1838 assert(is_contained(operands(), Op) && "Op must be an operand of the recipe");
1839 if (vputils::propagatesFirstLaneUse(U: this, Op))
1840 return vputils::onlyFirstLaneUsed(Def: this);
1841
1842 switch (getOpcode()) {
1843 default:
1844 return false;
1845 case Instruction::ExtractElement:
1846 return Op == getOperand(N: 1);
1847 case Instruction::InsertElement:
1848 return Op == getOperand(N: 1) || Op == getOperand(N: 2);
1849 case VPInstruction::ExtractLastActive:
1850 return Op == getOperand(N: 0);
1851 case Instruction::PHI:
1852 case Instruction::Load:
1853 case VPInstruction::ActiveLaneMask:
1854 case VPInstruction::WideActiveLaneMask:
1855 case VPInstruction::ExplicitVectorLength:
1856 case VPInstruction::CanonicalIVIncrementForPart:
1857 case VPInstruction::BranchOnCount:
1858 case VPInstruction::BranchOnCond:
1859 case VPInstruction::BranchOnTwoConds:
1860 case VPInstruction::Broadcast:
1861 case VPInstruction::Intrinsic:
1862 case VPInstruction::ReductionStartVector:
1863 case VPInstruction::ResumeForEpilogue:
1864 case VPInstruction::BuildVector:
1865 return true;
1866 case VPInstruction::WideVectorLoad:
1867 case VPInstruction::WideVectorStore:
1868 return Op == getOperand(N: 0) || Op == getOperand(N: 1) || Op == getOperand(N: 2);
1869 case VPInstruction::PtrAdd:
1870 case VPInstruction::ExitingIVValue:
1871 case VPInstruction::ExtractLane:
1872 return Op == getOperand(N: 0);
1873 }
1874}
1875
1876bool VPInstruction::usesFirstPartOnly() const {
1877 switch (getOpcode()) {
1878 default:
1879 return false;
1880 case VPInstruction::BranchOnCount:
1881 case VPInstruction::BranchOnCond:
1882 case VPInstruction::BranchOnTwoConds:
1883 case VPInstruction::CanonicalIVIncrementForPart:
1884 return true;
1885 };
1886}
1887
1888#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1889void VPInstruction::dump() const {
1890 VPSlotTracker SlotTracker(getParent()->getPlan());
1891 printRecipe(dbgs(), "", SlotTracker);
1892}
1893
1894void VPInstruction::printRecipe(raw_ostream &O, const Twine &Indent,
1895 VPSlotTracker &SlotTracker) const {
1896 O << Indent << "EMIT" << (isSingleScalar() ? "-SCALAR" : "") << " ";
1897
1898 if (hasResult()) {
1899 printAsOperand(O, SlotTracker);
1900 O << " = ";
1901 }
1902
1903 switch (getOpcode()) {
1904 case VPInstruction::Not:
1905 O << "not";
1906 break;
1907 case VPInstruction::ActiveLaneMask:
1908 O << "active lane mask";
1909 break;
1910 case VPInstruction::WideActiveLaneMask:
1911 O << "wide active lane mask";
1912 break;
1913 case VPInstruction::WideVectorLoad:
1914 O << "wide vector load";
1915 break;
1916 case VPInstruction::WideVectorStore:
1917 O << "wide vector store";
1918 break;
1919 case VPInstruction::ConcatVectors:
1920 O << "concat-vectors";
1921 break;
1922 case VPInstruction::IncomingAliasMask:
1923 O << "incoming-alias-mask";
1924 break;
1925 case VPInstruction::ExplicitVectorLength:
1926 O << "EXPLICIT-VECTOR-LENGTH";
1927 break;
1928 case VPInstruction::FirstOrderRecurrenceSplice:
1929 O << "first-order splice";
1930 break;
1931 case VPInstruction::BranchOnCond:
1932 O << "branch-on-cond";
1933 break;
1934 case VPInstruction::BranchOnTwoConds:
1935 O << "branch-on-two-conds";
1936 break;
1937 case VPInstruction::CanonicalIVIncrementForPart:
1938 O << "VF * Part +";
1939 break;
1940 case VPInstruction::BranchOnCount:
1941 O << "branch-on-count";
1942 break;
1943 case VPInstruction::Broadcast:
1944 O << "broadcast";
1945 break;
1946 case VPInstruction::BuildVector:
1947 O << "buildvector";
1948 break;
1949 case VPInstruction::ExitingIVValue:
1950 O << "exiting-iv-value";
1951 break;
1952 case VPInstruction::MaskedCond:
1953 O << "masked-cond";
1954 break;
1955 case VPInstruction::ExtractLane:
1956 O << "extract-lane";
1957 break;
1958 case VPInstruction::ExtractLastLane:
1959 O << "extract-last-lane";
1960 break;
1961 case VPInstruction::ExtractLastPart:
1962 O << "extract-last-part";
1963 break;
1964 case VPInstruction::ExtractPenultimateElement:
1965 O << "extract-penultimate-element";
1966 break;
1967 case VPInstruction::ExtractVectorForPart:
1968 O << "extract-vector-for-part";
1969 break;
1970 case VPInstruction::ComputeReductionResult:
1971 O << "compute-reduction-result";
1972 break;
1973 case VPInstruction::LogicalAnd:
1974 O << "logical-and";
1975 break;
1976 case VPInstruction::LogicalOr:
1977 O << "logical-or";
1978 break;
1979 case VPInstruction::PtrAdd:
1980 O << "ptradd";
1981 break;
1982 case VPInstruction::WidePtrAdd:
1983 O << "wide-ptradd";
1984 break;
1985 case VPInstruction::AnyOf:
1986 O << "any-of";
1987 break;
1988 case VPInstruction::FirstActiveLane:
1989 O << "first-active-lane";
1990 break;
1991 case VPInstruction::LastActiveLane:
1992 O << "last-active-lane";
1993 break;
1994 case VPInstruction::ReductionStartVector:
1995 O << "reduction-start-vector";
1996 break;
1997 case VPInstruction::ResumeForEpilogue:
1998 O << "resume-for-epilogue";
1999 break;
2000 case VPInstruction::Reverse:
2001 O << "reverse";
2002 break;
2003 case VPInstruction::Unpack:
2004 O << "unpack";
2005 break;
2006 case VPInstruction::ExtractLastActive:
2007 O << "extract-last-active";
2008 break;
2009 case VPInstruction::NumActiveLanes:
2010 O << "num-active-lanes";
2011 break;
2012 case VPInstruction::WideIVStep:
2013 O << "wide-iv-step";
2014 break;
2015 case VPInstruction::StepVector:
2016 O << "step-vector " << *getScalarType();
2017 break;
2018 case VPInstruction::Intrinsic:
2019 case Instruction::Call: {
2020 O << "call";
2021 printFlags(O);
2022 printRetAttrs(O);
2023 O << *getScalarType() << " ";
2024 unsigned NumArgs;
2025 if (getOpcode() == VPInstruction::Intrinsic) {
2026 O << "@" << Intrinsic::getBaseName(vputils::getIntrinsicID(this));
2027 NumArgs = getNumOperands() - 1;
2028 } else {
2029 getCalledFunction(operands())->printAsOperand(O, /*PrintType=*/false);
2030 NumArgs = getCalledFnOperandIndex(operands());
2031 }
2032 O << "(";
2033 interleaveComma(enumerate(drop_end(operands(), getNumOperands() - NumArgs)),
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:
2051 O << Instruction::getOpcodeName(getOpcode());
2052 }
2053
2054 if (!operands_empty()) {
2055 printFlags(O);
2056 printOperands(O, SlotTracker);
2057 }
2058 if (Instruction::isCast(getOpcode()))
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().
2067static void executePhiRecipe(VPSingleDefRecipe *R, VPPhiAccessors &Phi,
2068 VPTransformState &State, bool IsScalar,
2069 const Twine &Name) {
2070 unsigned NumIncoming = VPBlockUtils::isHeader(VPB: R->getParent(), VPDT: State.VPDT)
2071 ? 1
2072 : Phi.getNumIncoming();
2073 Value *FirstInc = State.get(Def: Phi.getIncomingValue(Idx: 0), NeedsSingleScalar: IsScalar);
2074 PHINode *NewPhi = State.Builder.CreatePHI(Ty: FirstInc->getType(), NumReservedValues: 2, Name);
2075 NewPhi->addIncoming(V: FirstInc,
2076 BB: State.CFG.VPBB2IRBB.at(Val: Phi.getIncomingBlock(Idx: 0)));
2077 for (unsigned Idx = 1; Idx != NumIncoming; ++Idx)
2078 NewPhi->addIncoming(V: State.get(Def: Phi.getIncomingValue(Idx), NeedsSingleScalar: IsScalar),
2079 BB: State.CFG.VPBB2IRBB.at(Val: Phi.getIncomingBlock(Idx)));
2080 State.set(Def: R, V: NewPhi, IsScalar);
2081}
2082
2083void VPPhi::execute(VPTransformState &State) {
2084 executePhiRecipe(R: this, Phi&: *this, State, /*IsScalar=*/true, Name: 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" : "") << " ";
2091 printAsOperand(O, SlotTracker);
2092 O << " = phi";
2093 printFlags(O);
2094 printPhiOperands(O, SlotTracker);
2095}
2096#endif
2097
2098VPIRInstruction *VPIRInstruction ::create(Instruction &I) {
2099 if (auto *Phi = dyn_cast<PHINode>(Val: &I))
2100 return new VPIRPhi(*Phi);
2101 return new VPIRInstruction(I);
2102}
2103
2104void VPIRInstruction::execute(VPTransformState &State) {
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(x: I.getIterator()));
2110}
2111
2112InstructionCost VPIRInstruction::computeCost(ElementCount VF,
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)
2120void VPIRInstruction::printRecipe(raw_ostream &O, const Twine &Indent,
2121 VPSlotTracker &SlotTracker) const {
2122 O << Indent << "IR " << I;
2123}
2124#endif
2125
2126void VPIRPhi::execute(VPTransformState &State) {
2127 PHINode *Phi = &getIRPhi();
2128 for (const auto &[Idx, Op] : enumerate(First: operands())) {
2129 VPValue *ExitValue = Op;
2130 auto Lane = vputils::isSingleScalar(VPV: ExitValue)
2131 ? VPLane::getFirstLane()
2132 : VPLane::getLastLaneForVF(VF: 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(Def: ExitValue, Lane: 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(BB: PredBB) == -1)
2143 Phi->addIncoming(V, BB: PredBB);
2144 else
2145 Phi->setIncomingValueForBlock(BB: 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(x: Phi->getIterator()));
2151}
2152
2153void VPPhiAccessors::removeIncomingValueFor(VPBlockBase *IncomingBlock) const {
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(Pred: IncomingBlock);
2158 R->removeOperand(Idx: Position);
2159}
2160
2161VPValue *
2162VPPhiAccessors::getIncomingValueForBlock(const VPBasicBlock *VPBB) const {
2163 VPRecipeBase *R = const_cast<VPRecipeBase *>(getAsRecipe());
2164 return getIncomingValue(Idx: R->getParent()->getIndexForPredecessor(Pred: VPBB));
2165}
2166
2167void VPPhiAccessors::setIncomingValueForBlock(const VPBasicBlock *VPBB,
2168 VPValue *V) const {
2169 VPRecipeBase *R = const_cast<VPRecipeBase *>(getAsRecipe());
2170 R->setOperand(I: R->getParent()->getIndexForPredecessor(Pred: VPBB), New: V);
2171}
2172
2173#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2174void VPPhiAccessors::printPhiOperands(raw_ostream &O,
2175 VPSlotTracker &SlotTracker) const {
2176 interleaveComma(incoming_values_and_blocks(), O, [&O, &SlotTracker](auto Op) {
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)
2187void VPIRPhi::printRecipe(raw_ostream &O, const Twine &Indent,
2188 VPSlotTracker &SlotTracker) const {
2189 VPIRInstruction::printRecipe(O, Indent, SlotTracker);
2190
2191 if (getNumOperands() != 0) {
2192 O << " (extra operand" << (getNumOperands() > 1 ? "s" : "") << ": ";
2193 interleaveComma(incoming_values_and_blocks(), O,
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
2204void VPIRMetadata::applyMetadata(Instruction &I) const {
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(Kind: ExecutionFrequencyMDName);
2210 unsigned EstProfKind = getMDKindID(Kind: EstimatedProfileMDName);
2211 for (const auto &[Kind, Node] : Metadata)
2212 if (Kind != ExecFreqKind && Kind != EstProfKind)
2213 I.setMetadata(KindID: Kind, Node);
2214}
2215
2216/// Returns the execution frequency recorded in \p Node.
2217static VPExecutionFrequency getExecutionFrequencyFromMD(const MDNode *Node) {
2218 assert(Node->getNumOperands() <= 2 && "unexpected frequency node shape");
2219 uint64_t Freq =
2220 mdconst::extract<ConstantInt>(MD: Node->getOperand(I: 0))->getZExtValue();
2221 assert(Freq <= BlockFrequencyInfoImplBase::BlockMass::getFull().getMass() &&
2222 "frequency cannot exceed the one of an always executing block");
2223 return {BlockFrequency(Freq), Node->getNumOperands() == 2};
2224}
2225
2226void VPIRMetadata::setExecutionFrequency(
2227 std::optional<VPExecutionFrequency> Freq, LLVMContext &Ctx) {
2228 // A recipe that always executes needs no annotation.
2229 if (!Freq || vputils::getExecutionProbability(Freq: Freq->Freq).isOne())
2230 return;
2231 SmallVector<llvm::Metadata *, 2> Ops = {ConstantAsMetadata::get(
2232 C: ConstantInt::get(Ty: Type::getInt64Ty(C&: Ctx), V: Freq->Freq.getFrequency()))};
2233 if (Freq->IsEstimated)
2234 Ops.push_back(Elt: ConstantAsMetadata::get(C: ConstantInt::getTrue(Context&: Ctx)));
2235 setMetadata(Kind: Ctx.getMDKindID(Name: ExecutionFrequencyMDName), Node: MDNode::get(Context&: Ctx, MDs: Ops));
2236}
2237
2238std::optional<VPExecutionFrequency>
2239VPIRMetadata::getExecutionFrequency() const {
2240 if (MDNode *Node = getInternalMetadata(Kind: ExecutionFrequencyMDName))
2241 return getExecutionFrequencyFromMD(Node);
2242 return std::nullopt;
2243}
2244
2245void VPIRMetadata::clearExecutionFrequency() {
2246 if (Metadata.empty())
2247 return;
2248 unsigned ID = getMDKindID(Kind: ExecutionFrequencyMDName);
2249 erase_if(C&: Metadata, P: [ID](const auto &P) { return P.first == ID; });
2250}
2251
2252void VPIRMetadata::intersect(const VPIRMetadata &Other) {
2253 erase_if(C&: Metadata,
2254 P: [&](const auto &MD) { return !is_contained(Other.Metadata, MD); });
2255}
2256
2257#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2258void VPIRMetadata::print(raw_ostream &O, VPSlotTracker &SlotTracker) const {
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 =
2286 BlockFrequencyInfoImplBase::BlockMass::getFull().getMass();
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
2301VPIRAttributes::VPIRAttributes(const VPInstruction &Call,
2302 FunctionType *WideTy) {
2303 assert(Call.getOpcode() == Instruction::Call && "expected call");
2304 unsigned NumArgs = getCalledFnOperandIndex(Operands: 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(Kind: K) && !Incompatible.contains(A: K))
2324 AB.addAttribute(A: AS.getAttribute(Kind: K));
2325 return AttributeSet::get(C&: Ctx, B: 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: I);
2340 bool IsWidenedArg = WideArgTy != Call.getOperand(N: I)->getScalarType();
2341 if (Call.isMasked() && (!IsMaskedVariant || !IsWidenedArg))
2342 continue;
2343 ArgAttrs[I] = Filter(WideArgTy, ScalarAttrs.getParamAttrs(ArgNo: I));
2344 }
2345
2346 CallAttrs = AttributeList::get(C&: Ctx, FnAttrs: AttributeSet(), RetAttrs, ArgAttrs);
2347}
2348
2349void VPIRAttributes::intersectAttrs(const VPIRAttributes &Other,
2350 LLVMContext &Ctx) {
2351 CallAttrs =
2352 CallAttrs.intersectWith(C&: Ctx, Other: Other.CallAttrs).value_or(u: AttributeList());
2353}
2354
2355#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2356void VPIRAttributes::printRetAttrs(raw_ostream &O) const {
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
2368void VPIRAttributes::printFnAttrs(raw_ostream &O) const {
2369 AttributeSet FnAttrs = CallAttrs.getFnAttrs();
2370 if (FnAttrs.hasAttributes())
2371 O << " " << FnAttrs.getAsString();
2372}
2373#endif
2374
2375void VPWidenCallRecipe::execute(VPTransformState &State) {
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.
2381 SmallVector<Value *, 4> Args;
2382 for (const auto &I : enumerate(First: 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: I.index())->isVectorTy())
2388 Arg = State.get(Def: I.value(), Lane: VPLane(0));
2389 else
2390 Arg = State.get(Def: I.value(), NeedsSingleScalar: usesFirstLaneOnly(Op: I.value()));
2391 Args.push_back(Elt: Arg);
2392 }
2393
2394 CallInst *V = State.Builder.CreateCall(Callee: Variant, Args);
2395 applyFlags(I&: *V);
2396 applyMetadata(I&: *V);
2397 applyAttrs(WideCall&: *V);
2398 V->setCallingConv(Variant->getCallingConv());
2399
2400 if (!V->getType()->isVoidTy())
2401 State.set(Def: this, V);
2402}
2403
2404InstructionCost VPWidenCallRecipe::computeCost(ElementCount VF,
2405 VPCostContext &Ctx) const {
2406 assert(getVectorizedTypeVF(Variant->getReturnType()) == VF &&
2407 "Variant return type must match VF");
2408 return computeCallCost(Variant, Ctx);
2409}
2410
2411InstructionCost VPWidenCallRecipe::computeCallCost(Function *Variant,
2412 VPCostContext &Ctx) {
2413 return Ctx.TTI.getCallInstrCost(F: nullptr, RetTy: Variant->getReturnType(),
2414 Tys: Variant->getFunctionType()->params(),
2415 CostKind: Ctx.CostKind);
2416}
2417
2418bool VPWidenCallRecipe::usesFirstLaneOnly(const VPValue *Op) const {
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(Range: enumerate(First: args()), P: [VFTy, &Op](const auto &Arg) {
2423 auto [Idx, V] = Arg;
2424 Type *ArgTy = VFTy->getParamType(i: 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)
2431void VPWidenCallRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
2432 VPSlotTracker &SlotTracker) const {
2433 O << Indent << "WIDEN-CALL ";
2434
2435 Function *CalledFn = getCalledScalarFunction();
2436 if (CalledFn->getReturnType()->isVoidTy())
2437 O << "void ";
2438 else {
2439 printAsOperand(O, SlotTracker);
2440 O << " = ";
2441 }
2442
2443 O << "call";
2444 printFlags(O);
2445 printRetAttrs(O);
2446 O << "@" << CalledFn->getName() << "(";
2447 interleaveComma(enumerate(args()), O,
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
2462CallInst *VPWidenIntrinsicRecipe::createVectorCall(VPTransformState &State) {
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(ID: VectorIntrinsicID, OpdIdx: -1,
2468 TTI: State.TTI)) {
2469 Type *RetTy = toVectorizedTy(Ty: getScalarType(), EC: State.VF);
2470 ArrayRef<Type *> ContainedTys = getContainedTypes(Ty: RetTy);
2471 for (auto [Idx, Ty] : enumerate(First&: ContainedTys)) {
2472 if (isVectorIntrinsicWithStructReturnOverloadAtField(ID: VectorIntrinsicID,
2473 RetIdx: Idx, TTI: State.TTI))
2474 TysForDecl.push_back(Elt: Ty);
2475 }
2476 }
2477 SmallVector<Value *, 4> Args;
2478 for (const auto &I : enumerate(First: operands())) {
2479 // Some intrinsics have a scalar argument - don't replace it with a
2480 // vector.
2481 Value *Arg;
2482 if (isVectorIntrinsicWithScalarOpAtArg(ID: VectorIntrinsicID, ScalarOpdIdx: I.index(),
2483 TTI: State.TTI))
2484 Arg = State.get(Def: I.value(), Lane: VPLane(0));
2485 else
2486 Arg = State.get(Def: I.value(), NeedsSingleScalar: usesFirstLaneOnly(Op: I.value()));
2487 if (isVectorIntrinsicWithOverloadTypeAtArg(ID: VectorIntrinsicID, OpdIdx: I.index(),
2488 TTI: State.TTI))
2489 TysForDecl.push_back(Elt: Arg->getType());
2490 Args.push_back(Elt: Arg);
2491 }
2492
2493 // Use vector version of the intrinsic.
2494 Module *M = State.Builder.getModule();
2495 Function *VectorF =
2496 Intrinsic::getOrInsertDeclaration(M, id: VectorIntrinsicID, OverloadTys: TysForDecl);
2497 assert(VectorF &&
2498 "Can't retrieve vector intrinsic or vector-predication intrinsics.");
2499
2500 CallInst *V = State.Builder.CreateCall(Callee: VectorF, Args);
2501
2502 applyFlags(I&: *V);
2503 applyMetadata(I&: *V);
2504
2505 return V;
2506}
2507
2508void VPWidenIntrinsicRecipe::execute(VPTransformState &State) {
2509 CallInst *V = createVectorCall(State);
2510 if (!V->getType()->isVoidTy())
2511 State.set(Def: this, V);
2512}
2513
2514InstructionCost VPWidenIntrinsicRecipe::computeCallCost(
2515 Intrinsic::ID ID, ArrayRef<const VPValue *> Operands,
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(BitWidth: 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.
2529 SmallVector<const Value *> Arguments;
2530 for (const auto &[Idx, Op] : enumerate(First&: Operands)) {
2531 auto *V = Op->getUnderlyingValue();
2532 if (!V) {
2533 if (auto *UI = dyn_cast_or_null<CallBase>(Val: R.getUnderlyingValue())) {
2534 Arguments.push_back(Elt: UI->getArgOperand(i: Idx));
2535 continue;
2536 }
2537 Arguments.clear();
2538 break;
2539 }
2540 Arguments.push_back(Elt: V);
2541 }
2542
2543 Type *RetTy = VF.isVector() ? toVectorizedTy(Ty: ScalarRetTy, EC: VF) : ScalarRetTy;
2544 SmallVector<Type *> ParamTys =
2545 map_to_vector(C&: Operands, F: [&](const VPValue *Op) {
2546 return toVectorTy(Scalar: Op->getScalarType(), EC: VF);
2547 });
2548
2549 VectorInstrContext VIC = VectorInstrContext::None;
2550 for (const VPValue *Op : Operands) {
2551 if (isa<VPWidenRecipe>(Val: Op) &&
2552 Instruction::isBinaryOp(Opcode: cast<VPWidenRecipe>(Val: Op)->getOpcode())) {
2553 VIC = VectorInstrContext::BinaryOp;
2554 break;
2555 }
2556 if (auto *WidenIntrinsic = dyn_cast<VPWidenIntrinsicRecipe>(Val: Op)) {
2557 if (is_contained(Set: {Intrinsic::umin, Intrinsic::umax, Intrinsic::smin,
2558 Intrinsic::smax},
2559 Element: WidenIntrinsic->getVectorIntrinsicID())) {
2560 VIC = VectorInstrContext::BinaryOp;
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>(Val: R.getUnderlyingValue()),
2570 InstructionCost::getInvalid(), VIC);
2571 return Ctx.TTI.getIntrinsicInstrCost(ICA: CostAttrs, CostKind: Ctx.CostKind);
2572}
2573
2574InstructionCost VPWidenIntrinsicRecipe::computeCost(ElementCount VF,
2575 VPCostContext &Ctx) const {
2576 return computeCallCost(ID: VectorIntrinsicID, Operands: operands(), R: *this, VF, Ctx);
2577}
2578
2579StringRef VPWidenIntrinsicRecipe::getIntrinsicName() const {
2580 return Intrinsic::getBaseName(id: VectorIntrinsicID);
2581}
2582
2583bool VPWidenIntrinsicRecipe::usesFirstLaneOnly(const VPValue *Op) const {
2584 assert(is_contained(operands(), Op) && "Op must be an operand of the recipe");
2585 return all_of(Range: enumerate(First: operands()), P: [this, &Op](const auto &X) {
2586 auto [Idx, V] = X;
2587 return V != Op || isVectorIntrinsicWithScalarOpAtArg(getVectorIntrinsicID(),
2588 Idx, nullptr);
2589 });
2590}
2591
2592#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2593void VPWidenIntrinsicRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
2594 VPSlotTracker &SlotTracker) const {
2595 O << Indent << "WIDEN-INTRINSIC ";
2596 if (getScalarType()->isVoidTy()) {
2597 O << "void ";
2598 } else {
2599 printAsOperand(O, SlotTracker);
2600 O << " = ";
2601 }
2602
2603 O << "call";
2604 printFlags(O);
2605 O << getIntrinsicName() << "(";
2606 printOperands(O, SlotTracker);
2607 O << ")";
2608}
2609#endif
2610
2611void VPWidenMemIntrinsicRecipe::execute(VPTransformState &State) {
2612 CallInst *MemI = createVectorCall(State);
2613 MemI->addParamAttr(ArgNo: getAddrOpIdx(), Attr: Attribute::getWithAlignment(
2614 Context&: MemI->getContext(), Alignment));
2615 if (!MemI->getType()->isVoidTy())
2616 State.set(Def: this, V: MemI);
2617}
2618
2619VPValue *VPWidenMemIntrinsicRecipe::getMask() const {
2620 auto MaskPos = getVectorIntrinsicMaskArgIdx(ID: getVectorIntrinsicID());
2621 assert(MaskPos && "Expected a memory intrinsic with a valid mask position");
2622 return getOperand(N: *MaskPos);
2623}
2624
2625unsigned VPWidenMemIntrinsicRecipe::getAddrOpIdx() const {
2626 auto PtrPos = getVectorMemoryIntrinsicPointerArgIdx(ID: getVectorIntrinsicID());
2627 assert(PtrPos && "Expected a memory intrinsic with a valid pointer position");
2628 return *PtrPos;
2629}
2630
2631Type *VPWidenMemIntrinsicRecipe::getAccessType(ElementCount VF) const {
2632 Type *DataTy;
2633 if (auto DataPos = getVectorStoreIntrinsicDataArgIdx(ID: getVectorIntrinsicID()))
2634 DataTy = getOperand(N: *DataPos)->getScalarType();
2635 else
2636 DataTy = getScalarType();
2637 assert(!DataTy->isVoidTy() && "Expected a non-void data type");
2638 return toVectorTy(Scalar: DataTy, EC: VF);
2639}
2640
2641InstructionCost VPWidenMemIntrinsicRecipe::computeMemIntrinsicCost(
2642 Intrinsic::ID IID, Type *Ty, bool IsMasked, Align Alignment,
2643 VPCostContext &Ctx) {
2644 return Ctx.TTI.getMemIntrinsicInstrCost(
2645 MICA: MemIntrinsicCostAttributes(IID, Ty, /*Ptr=*/nullptr, IsMasked, Alignment),
2646 CostKind: Ctx.CostKind);
2647}
2648
2649InstructionCost
2650VPWidenMemIntrinsicRecipe::computeCost(ElementCount VF,
2651 VPCostContext &Ctx) const {
2652 return computeMemIntrinsicCost(IID: getVectorIntrinsicID(), Ty: getAccessType(VF),
2653 IsMasked: !match(V: getMask(), P: m_True()), Alignment, Ctx);
2654}
2655
2656void VPHistogramRecipe::execute(VPTransformState &State) {
2657 IRBuilderBase &Builder = State.Builder;
2658
2659 Value *Address = State.get(Def: getOperand(N: 0));
2660 Value *IncAmt = State.get(Def: getOperand(N: 1), /*NeedsSingleScalar=*/true);
2661 VectorType *VTy = cast<VectorType>(Val: 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(Def: VPMask);
2669 else
2670 Mask =
2671 Builder.CreateVectorSplat(EC: VTy->getElementCount(), V: Builder.getInt1(V: 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(V: IncAmt);
2677
2678 Instruction *HistogramInst = State.Builder.CreateIntrinsicWithoutFolding(
2679 ID: getHistogramIntrinsicID(), OverloadTypes: {VTy, IncAmt->getType()},
2680 Args: {Address, IncAmt, Mask});
2681 applyMetadata(I&: *HistogramInst);
2682}
2683
2684Intrinsic::ID VPHistogramRecipe::getHistogramIntrinsicID() const {
2685 switch (UpdateKind) {
2686 case HistogramUpdateKind::Add:
2687 case HistogramUpdateKind::Sub:
2688 return Intrinsic::experimental_vector_histogram_add;
2689 case HistogramUpdateKind::UAddSat:
2690 return Intrinsic::experimental_vector_histogram_uadd_sat;
2691 case HistogramUpdateKind::UMax:
2692 return Intrinsic::experimental_vector_histogram_umax;
2693 case HistogramUpdateKind::UMin:
2694 return Intrinsic::experimental_vector_histogram_umin;
2695 }
2696 llvm_unreachable("Unknown HistogramUpdateKind");
2697}
2698
2699InstructionCost VPHistogramRecipe::computeCost(ElementCount VF,
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(N: 0)->getScalarType();
2708 VPValue *IncAmt = getOperand(N: 1);
2709 Type *IncTy = IncAmt->getScalarType();
2710 VectorType *VTy = VectorType::get(ElementType: IncTy, EC: 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.
2715 InstructionCost MulCost = TTI::TCC_Free;
2716 if (!match(V: IncAmt, P: m_One()) && UpdateKind != HistogramUpdateKind::UMax &&
2717 UpdateKind != HistogramUpdateKind::UMin)
2718 MulCost =
2719 Ctx.TTI.getArithmeticInstrCost(Opcode: Instruction::Mul, Ty: VTy, CostKind: Ctx.CostKind);
2720
2721 // Find the cost of the histogram operation itself.
2722 Type *PtrTy = VectorType::get(ElementType: AddressTy, EC: VF);
2723 Type *MaskTy = VectorType::get(ElementType: Type::getInt1Ty(C&: Ctx.LLVMCtx), EC: VF);
2724 IntrinsicCostAttributes ICA(getHistogramIntrinsicID(),
2725 Type::getVoidTy(C&: 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, CostKind: Ctx.CostKind) + MulCost;
2731}
2732
2733#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2734void VPHistogramRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
2735 VPSlotTracker &SlotTracker) const {
2736 O << Indent << "WIDEN-HISTOGRAM buckets: ";
2737 getOperand(0)->printAsOperand(O, SlotTracker);
2738
2739 switch (UpdateKind) {
2740 case HistogramUpdateKind::Add:
2741 O << ", inc: ";
2742 break;
2743 case HistogramUpdateKind::Sub:
2744 O << ", dec: ";
2745 break;
2746 case HistogramUpdateKind::UAddSat:
2747 O << ", saturated inc: ";
2748 break;
2749 case HistogramUpdateKind::UMax:
2750 O << ", max: ";
2751 break;
2752 case HistogramUpdateKind::UMin:
2753 O << ", min: ";
2754 break;
2755 }
2756 getOperand(1)->printAsOperand(O, SlotTracker);
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:
2781 case VPInstruction::CanonicalIVIncrementForPart:
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:
2793 case VPInstruction::PtrAdd:
2794 case VPInstruction::WidePtrAdd:
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.
2813 if (FPMathOperator::isSupportedFloatingPointType(Ty: ResultTy))
2814 return FastMathFlags();
2815 return VPIRFlags();
2816 case Instruction::ICmp:
2817 case Instruction::FCmp:
2818 case VPInstruction::ComputeReductionResult:
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 ||
2852 Opcode == VPInstruction::ReductionStartVector;
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:
2860 return Opcode == VPInstruction::ComputeReductionResult;
2861 case OperationType::Other:
2862 return true;
2863 }
2864 llvm_unreachable("Unknown OperationType enum");
2865}
2866
2867bool VPIRFlags::hasRequiredFlagsForOpcode(unsigned Opcode,
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;
2874 if (Opcode == VPInstruction::ComputeReductionResult)
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;
2894 case RecurKind::AddChainWithSubs:
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;
2924 case RecurKind::FAddChainWithSubs:
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;
2945 case RecurKind::FMinimum:
2946 OS << "fminimum";
2947 break;
2948 case RecurKind::FMaximum:
2949 OS << "fmaximum";
2950 break;
2951 case RecurKind::FMinimumNum:
2952 OS << "fminimumnum";
2953 break;
2954 case RecurKind::FMaximumNum:
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;
2966 case RecurKind::FindLast:
2967 OS << "find-last";
2968 break;
2969 }
2970}
2971
2972void VPIRFlags::printFlags(raw_ostream &O) const {
2973 switch (OpType) {
2974 case OperationType::Cmp:
2975 O << " " << CmpInst::getPredicateName(getPredicate());
2976 break;
2977 case OperationType::FCmp:
2978 O << " " << CmpInst::getPredicateName(getPredicate());
2979 getFastMathFlagsOrNone().print(O);
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:
3002 getFastMathFlagsOrNone().print(O);
3003 break;
3004 case OperationType::GEPOp: {
3005 GEPNoWrapFlags Flags = getGEPNoWrapFlags();
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 << " (";
3020 printRecurrenceKind(O, getRecurKind());
3021 if (isReductionInLoop())
3022 O << ", in-loop";
3023 if (isReductionOrdered())
3024 O << ", ordered";
3025 O << ")";
3026 getFastMathFlagsOrNone().print(O);
3027 break;
3028 }
3029 case OperationType::Other:
3030 break;
3031 }
3032 O << " ";
3033}
3034#endif
3035
3036void VPWidenRecipe::execute(VPTransformState &State) {
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.
3065 SmallVector<Value *, 2> Ops;
3066 for (VPValue *VPOp : operands())
3067 Ops.push_back(Elt: State.get(Def: VPOp));
3068
3069 Value *V = Builder.CreateNAryOp(Opc: Opcode, Ops);
3070
3071 if (auto *VecOp = dyn_cast<Instruction>(Val: V)) {
3072 applyFlags(I&: *VecOp);
3073 applyMetadata(I&: *VecOp);
3074 }
3075
3076 // Use this vector value for all users of the original instruction.
3077 State.set(Def: this, V);
3078 break;
3079 }
3080 case Instruction::ExtractValue: {
3081 Value *Op = State.get(Def: getOperand(N: 0));
3082 Value *Extract =
3083 Builder.CreateExtractValue(Agg: Op, Idxs: getExtractValueIndices(Ops: operands()));
3084 State.set(Def: this, V: Extract);
3085 break;
3086 }
3087 case Instruction::Freeze: {
3088 Value *Op = State.get(Def: getOperand(N: 0));
3089 Value *Freeze = Builder.CreateFreeze(V: Op);
3090 State.set(Def: this, V: 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(Def: getOperand(N: 0));
3098 Value *B = State.get(Def: getOperand(N: 1));
3099 Value *C = nullptr;
3100 if (FCmp) {
3101 C = Builder.CreateFCmp(P: getPredicate(), LHS: A, RHS: B);
3102 } else {
3103 C = Builder.CreateICmp(P: getPredicate(), LHS: A, RHS: B);
3104 }
3105 if (auto *I = dyn_cast<Instruction>(Val: C)) {
3106 applyFlags(I&: *I);
3107 applyMetadata(I&: *I);
3108 }
3109 State.set(Def: this, V: C);
3110 break;
3111 }
3112 case Instruction::Select: {
3113 VPValue *CondOp = getOperand(N: 0);
3114 Value *Cond = State.get(Def: CondOp, NeedsSingleScalar: vputils::isSingleScalar(VPV: CondOp));
3115 Value *Op0 = State.get(Def: getOperand(N: 1));
3116 Value *Op1 = State.get(Def: getOperand(N: 2));
3117 Value *Sel = State.Builder.CreateSelect(C: Cond, True: Op0, False: Op1);
3118 State.set(Def: this, V: Sel);
3119 if (auto *I = dyn_cast<Instruction>(Val: Sel)) {
3120 if (isa<FPMathOperator>(Val: I))
3121 applyFlags(I&: *I);
3122 applyMetadata(I&: *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
3142InstructionCost VPWidenRecipe::computeCost(ElementCount VF,
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(Opcode: getOpcode(), VF, Ctx);
3174 default:
3175 llvm_unreachable("Unsupported opcode for instruction");
3176 }
3177}
3178
3179#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3180void VPWidenRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
3181 VPSlotTracker &SlotTracker) const {
3182 O << Indent << "WIDEN ";
3183 printAsOperand(O, SlotTracker);
3184 O << " = " << Instruction::getOpcodeName(Opcode);
3185 printFlags(O);
3186 printOperands(O, SlotTracker);
3187}
3188#endif
3189
3190void VPWidenCastRecipe::execute(VPTransformState &State) {
3191 auto &Builder = State.Builder;
3192 /// Vectorize casts.
3193 assert(State.VF.isVector() && "Not vectorizing?");
3194 Type *DestTy = VectorType::get(ElementType: getScalarType(), EC: State.VF);
3195 VPValue *Op = getOperand(N: 0);
3196 Value *A = State.get(Def: Op);
3197 Value *Cast = Builder.CreateCast(Op: Instruction::CastOps(Opcode), V: A, DestTy);
3198 State.set(Def: this, V: Cast);
3199 if (auto *CastOp = dyn_cast<Instruction>(Val: Cast)) {
3200 applyFlags(I&: *CastOp);
3201 applyMetadata(I&: *CastOp);
3202 }
3203}
3204
3205InstructionCost VPWidenCastRecipe::computeCost(ElementCount VF,
3206 VPCostContext &Ctx) const {
3207 return getCostForRecipeWithOpcode(Opcode: getOpcode(), VF, Ctx);
3208}
3209
3210#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3211void VPWidenCastRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
3212 VPSlotTracker &SlotTracker) const {
3213 O << Indent << "WIDEN-CAST ";
3214 printAsOperand(O, SlotTracker);
3215 O << " = " << Instruction::getOpcodeName(Opcode);
3216 printFlags(O);
3217 printOperands(O, SlotTracker);
3218 O << " to " << *getScalarType();
3219}
3220#endif
3221
3222InstructionCost VPHeaderPHIRecipe::computeCost(ElementCount VF,
3223 VPCostContext &Ctx) const {
3224 return Ctx.TTI.getCFInstrCost(Opcode: Instruction::PHI, CostKind: Ctx.CostKind);
3225}
3226
3227#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3228void VPWidenIntOrFpInductionRecipe::printRecipe(
3229 raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const {
3230 O << Indent;
3231 printAsOperand(O, SlotTracker);
3232 O << " = WIDEN-INDUCTION";
3233 printFlags(O);
3234 printOperands(O, SlotTracker);
3235
3236 if (isTruncated())
3237 O << " (truncated to " << *getScalarType() << ")";
3238}
3239#endif
3240
3241bool VPWidenIntOrFpInductionRecipe::isCanonical() const {
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(V: getStartValue(), P: m_ZeroInt()) &&
3246 match(V: getStepValue(), P: m_One()) &&
3247 getScalarType() == getRegion()->getCanonicalIVType();
3248}
3249
3250InstructionCost
3251VPWidenIntOrFpInductionRecipe::computeCost(ElementCount VF,
3252 VPCostContext &Ctx) const {
3253 // A widened induction generates a vector phi and increments it by the
3254 // splatted step each iteration.
3255 const InductionDescriptor &ID = getInductionDescriptor();
3256 InstructionCost Cost = Ctx.TTI.getCFInstrCost(Opcode: Instruction::PHI, CostKind: 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(Opcode: IncOpc, Ty: toVectorTy(Scalar: StepTy, EC: VF),
3264 CostKind: 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>(Val: V);
3270 return C ? dyn_cast<ConstantFP>(Val: C->getConstant()) : nullptr;
3271}
3272
3273InstructionCost VPDerivedIVRecipe::computeCost(ElementCount VF,
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;
3283 case InductionDescriptor::IK_IntInduction: {
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(Def: 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>(Val: 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();
3301 InstructionCost Cost(0);
3302 if (auto *StepC = dyn_cast<VPConstantInt>(Val: 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 Opcode: CastOpc, Dst: StepTy, Src: IndexTy, CCH: TTI::CastContextHint::None, CostKind: Ctx.CostKind);
3329 }
3330
3331 if (NeedsMul)
3332 Cost += Ctx.TTI.getArithmeticInstrCost(Opcode: Instruction::Mul, Ty: StepTy,
3333 CostKind: Ctx.CostKind);
3334 if (NeedsShl)
3335 Cost += Ctx.TTI.getArithmeticInstrCost(
3336 Opcode: Instruction::Shl, Ty: StepTy, CostKind: Ctx.CostKind,
3337 Opd1Info: {.Kind: TargetTransformInfo::OK_AnyValue, .Properties: TargetTransformInfo::OP_None},
3338 Opd2Info: {.Kind: TargetTransformInfo::OK_UniformConstantValue,
3339 .Properties: TargetTransformInfo::OP_None});
3340 if (NeedsAdd)
3341 Cost += Ctx.TTI.getArithmeticInstrCost(Opcode: Instruction::Add, Ty: StepTy,
3342 CostKind: Ctx.CostKind);
3343 return Cost;
3344 }
3345 case InductionDescriptor::IK_FpInduction: {
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(Def: 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();
3356 InstructionCost Cost =
3357 Ctx.TTI.getCastInstrCost(Opcode: Instruction::UIToFP, Dst: StepTy, Src: IndexTy,
3358 CCH: TTI::CastContextHint::None, CostKind: 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(V: 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(V: getStartValue());
3371 bool AddFolds = getFPBinOp()->getOpcode() == Instruction::FAdd && StartC &&
3372 StartC->isZero() && (StartC->isNegZero() || !NeedsMul);
3373
3374 if (NeedsMul)
3375 Cost += Ctx.TTI.getArithmeticInstrCost(Opcode: Instruction::FMul, Ty: StepTy,
3376 CostKind: Ctx.CostKind);
3377 if (!AddFolds)
3378 Cost += Ctx.TTI.getArithmeticInstrCost(Opcode: getFPBinOp()->getOpcode(), Ty: StepTy,
3379 CostKind: Ctx.CostKind);
3380 return Cost;
3381 }
3382 }
3383
3384 return 0;
3385}
3386
3387#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3388void VPDerivedIVRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
3389 VPSlotTracker &SlotTracker) const {
3390 O << Indent;
3391 printAsOperand(O, SlotTracker);
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
3402bool VPScalarIVStepsRecipe::doesGeneratePerAllLanes() const {
3403 return !vputils::onlyFirstLaneUsed(Def: this);
3404}
3405
3406InstructionCost VPScalarIVStepsRecipe::computeCost(ElementCount VF,
3407 VPCostContext &Ctx) const {
3408 Type *BaseIVTy = getOperand(N: 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.
3414 if (vputils::onlyFirstLaneUsed(Def: this))
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(Plan: *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.
3428 InstructionCost Cost;
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(Opcode: InductionOpcode, Ty: BaseIVTy,
3435 CostKind: 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(Opcode: Instruction::Add, Ty: BaseIVTy,
3451 CostKind: 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 Freq: Region->getEntryBranchOnMask()->getExecutionFrequency());
3460 return Cost;
3461}
3462
3463void VPScalarIVStepsRecipe::execute(VPTransformState &State) {
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(Def: getOperand(N: 0), Lane: VPLane(0));
3472 Value *Step = State.get(Def: getStepValue(), Lane: 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.
3481 Instruction::BinaryOps AddOp;
3482 Instruction::BinaryOps MulOp;
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(Def: getStartIndex(), NeedsSingleScalar: true)
3496 : Constant::getNullValue(Ty: BaseIVTy);
3497 auto *Mul = Builder.CreateBinOp(Opc: MulOp, LHS: StartIdx, RHS: Step);
3498 auto *Add = Builder.CreateBinOp(Opc: AddOp, LHS: BaseIV, RHS: Mul);
3499 State.set(Def: this, V: Add, Lane: VPLane(0));
3500}
3501
3502#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3503void VPScalarIVStepsRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
3504 VPSlotTracker &SlotTracker) const {
3505 O << Indent;
3506 printAsOperand(O, SlotTracker);
3507 O << " = SCALAR-STEPS ";
3508 printOperands(O, SlotTracker);
3509}
3510#endif
3511
3512bool VPWidenGEPRecipe::usesFirstLaneOnly(const VPValue *Op) const {
3513 assert(is_contained(operands(), Op) && "Op must be an operand of the recipe");
3514 return vputils::isSingleScalar(VPV: Op);
3515}
3516
3517void VPWidenGEPRecipe::execute(VPTransformState &State) {
3518 assert(State.VF.isVector() && "not widening");
3519 auto Ops = map_to_vector(C: operands(), F: [&](VPValue *Op) {
3520 return State.get(Def: Op, NeedsSingleScalar: vputils::isSingleScalar(VPV: Op));
3521 });
3522 auto *GEP =
3523 State.Builder.CreateGEP(Ty: getSourceElementType(), Ptr: Ops.front(),
3524 IdxList: drop_begin(RangeOrContainer&: Ops), Name: "wide.gep", NW: getGEPNoWrapFlags());
3525 State.set(Def: this, V: GEP, IsScalar: vputils::isSingleScalar(VPV: this));
3526}
3527
3528#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3529void VPWidenGEPRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
3530 VPSlotTracker &SlotTracker) const {
3531 O << Indent << "WIDEN-GEP ";
3532 printAsOperand(O, SlotTracker);
3533 O << " = getelementptr";
3534 printFlags(O);
3535 printOperands(O, SlotTracker);
3536}
3537#endif
3538
3539void VPVectorEndPointerRecipe::materializeOffset(unsigned Part) {
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(PtrTy: this->getScalarType());
3546 VPValue *Stride =
3547 Plan.getConstantInt(Ty: IndexTy, Val: getStride(), /*IsSigned=*/true);
3548 VPValue *VF =
3549 Builder.createScalarZExtOrTrunc(Op: VFVal, ResultTy: IndexTy, DL: DebugLoc::getUnknown());
3550
3551 // Offset for Part0 = Offset0 = Stride * (VF - 1).
3552 VPInstruction *VFMinusOne =
3553 Builder.createSub(LHS: VF, RHS: Plan.getConstantInt(Ty: IndexTy, Val: 1u),
3554 DL: DebugLoc::getUnknown(), Name: "", WrapFlags: {true, true});
3555 VPInstruction *Offset0 =
3556 Builder.createOverflowingOp(Opcode: Instruction::Mul, Operands: {VFMinusOne, Stride});
3557
3558 // Offset for PartN = Offset0 + Part * Stride * VF.
3559 VPValue *PartxStride =
3560 Plan.getConstantInt(Ty: IndexTy, Val: Part * getStride(), /*IsSigned=*/true);
3561 VPValue *Offset = Builder.createAdd(
3562 LHS: Offset0,
3563 RHS: Builder.createOverflowingOp(Opcode: Instruction::Mul, Operands: {PartxStride, VF}));
3564 addOffset(Offset);
3565}
3566
3567void VPVectorEndPointerRecipe::execute(VPTransformState &State) {
3568 auto &Builder = State.Builder;
3569 assert(getOffset() && "Expected prior materialization of offset");
3570 Value *Ptr = State.get(Def: getPointer(), NeedsSingleScalar: true);
3571 Value *Offset = State.get(Def: getOffset(), NeedsSingleScalar: true);
3572 Value *ResultPtr = Builder.CreateGEP(Ty: getSourceElementType(), Ptr, IdxList: Offset, Name: "",
3573 NW: getGEPNoWrapFlags());
3574 State.set(Def: this, V: ResultPtr, /*IsScalar*/ true);
3575}
3576
3577#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3578void VPVectorEndPointerRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
3579 VPSlotTracker &SlotTracker) const {
3580 O << Indent;
3581 printAsOperand(O, SlotTracker);
3582 O << " = vector-end-pointer";
3583 printFlags(O);
3584 getSourceElementType()->print(O);
3585 O << ", ";
3586 printOperands(O, SlotTracker);
3587}
3588#endif
3589
3590void VPVectorPointerRecipe::execute(VPTransformState &State) {
3591 assert(getVFxPart() &&
3592 "Expected prior simplification of recipe without VFxPart");
3593
3594 auto &Builder = State.Builder;
3595 Value *Ptr = State.get(Def: getOperand(N: 0), Lane: VPLane(0));
3596 Value *Offset = State.get(Def: getVFxPart(), NeedsSingleScalar: true);
3597 // TODO: Expand to VPInstruction to support constant folding.
3598 if (!match(V: getStride(), P: m_One())) {
3599 Value *Stride = Builder.CreateZExtOrTrunc(V: State.get(Def: getStride(), NeedsSingleScalar: true),
3600 DestTy: Offset->getType());
3601 Offset = Builder.CreateMul(LHS: Offset, RHS: Stride);
3602 }
3603 Value *ResultPtr = Builder.CreateGEP(Ty: getSourceElementType(), Ptr, IdxList: Offset, Name: "",
3604 NW: getGEPNoWrapFlags());
3605 State.set(Def: this, V: ResultPtr, /*IsScalar*/ true);
3606}
3607
3608#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3609void VPVectorPointerRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
3610 VPSlotTracker &SlotTracker) const {
3611 O << Indent;
3612 printAsOperand(O, SlotTracker);
3613 O << " = vector-pointer";
3614 printFlags(O);
3615 getSourceElementType()->print(O);
3616 O << ", ";
3617 printOperands(O, SlotTracker);
3618}
3619#endif
3620
3621InstructionCost VPBlendRecipe::computeCost(ElementCount VF,
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.
3625 if (vputils::onlyFirstLaneUsed(Def: this))
3626 VF = ElementCount::getFixed(MinVal: 1);
3627
3628 Type *ResultTy = toVectorTy(Scalar: this->getScalarType(), EC: VF);
3629 Type *CmpTy = toVectorTy(Scalar: Type::getInt1Ty(C&: Ctx.LLVMCtx), EC: VF);
3630
3631 InstructionCost Cost = 0;
3632 for (unsigned I = 1, E = getNumIncomingValues(); I != E; ++I) {
3633 CmpPredicate Pred;
3634 if (!match(V: getMask(Idx: I), P: m_Cmp(Pred, Op0: m_VPValue(), Op1: m_VPValue())))
3635 Pred = getScalarType()->isFloatingPointTy() ? CmpInst::BAD_FCMP_PREDICATE
3636 : CmpInst::BAD_ICMP_PREDICATE;
3637 Cost += Ctx.TTI.getCmpSelInstrCost(Opcode: Instruction::Select, ValTy: ResultTy, CondTy: CmpTy,
3638 VecPred: Pred, CostKind: Ctx.CostKind);
3639 }
3640 return Cost;
3641}
3642
3643#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3644void VPBlendRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
3645 VPSlotTracker &SlotTracker) const {
3646 O << Indent << "BLEND ";
3647 printAsOperand(O, SlotTracker);
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
3668void VPReductionRecipe::execute(VPTransformState &State) {
3669 RecurKind Kind = getRecurrenceKind();
3670 assert(!RecurrenceDescriptor::isAnyOfRecurrenceKind(Kind) &&
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(Def: getVecOp());
3676 if (VPValue *Cond = getCondOp()) {
3677 Value *NewCond = State.get(Def: Cond, NeedsSingleScalar: State.VF.isScalar());
3678 VectorType *VecTy = dyn_cast<VectorType>(Val: NewVecOp->getType());
3679 Type *ElementTy = VecTy ? VecTy->getElementType() : NewVecOp->getType();
3680
3681 Value *Start =
3682 getRecurrenceIdentity(K: Kind, Tp: ElementTy, FMF: getFastMathFlagsOrNone());
3683 if (State.VF.isVector())
3684 Start = State.Builder.CreateVectorSplat(EC: VecTy->getElementCount(), V: Start);
3685
3686 Value *Select = State.Builder.CreateSelect(C: NewCond, True: NewVecOp, False: Start);
3687 NewVecOp = Select;
3688 }
3689 Value *NewRed;
3690 Value *NextInChain;
3691 if (isOrdered()) {
3692 Value *PrevInChain = State.get(Def: getChainOp(), /*NeedsSingleScalar=*/true);
3693 if (State.VF.isVector())
3694 NewRed =
3695 createOrderedReduction(B&: State.Builder, RdxKind: Kind, Src: NewVecOp, Start: PrevInChain);
3696 else
3697 NewRed = State.Builder.CreateBinOp(
3698 Opc: (Instruction::BinaryOps)RecurrenceDescriptor::getOpcode(Kind),
3699 LHS: PrevInChain, RHS: 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(Def: getChainOp(), /*NeedsSingleScalar=*/false);
3706 NewRed = State.Builder.CreateIntrinsic(
3707 RetTy: PrevInChain->getType(),
3708 ID: Kind == RecurKind::Add ? Intrinsic::vector_partial_reduce_add
3709 : Intrinsic::vector_partial_reduce_fadd,
3710 Args: {PrevInChain, NewVecOp}, FMFSource: State.Builder.getFastMathFlags(),
3711 Name: "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(Def: getChainOp(), /*NeedsSingleScalar=*/true);
3718 NewRed = createSimpleReduction(B&: State.Builder, Src: NewVecOp, RdxKind: Kind);
3719 if (RecurrenceDescriptor::isMinMaxRecurrenceKind(Kind))
3720 NextInChain = createMinMaxOp(Builder&: State.Builder, RK: Kind, Left: NewRed, Right: PrevInChain);
3721 else
3722 NextInChain = State.Builder.CreateBinOp(
3723 Opc: (Instruction::BinaryOps)RecurrenceDescriptor::getOpcode(Kind),
3724 LHS: PrevInChain, RHS: NewRed);
3725 }
3726 State.set(Def: this, V: NextInChain, /*IsScalar*/ !isPartialReduction());
3727}
3728
3729void VPReductionEVLRecipe::execute(VPTransformState &State) {
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
3738 RecurKind Kind = getRecurrenceKind();
3739 Value *Prev =
3740 State.get(Def: getChainOp(), /*NeedsSingleScalar=*/!isPartialReduction());
3741 Value *VecOp = State.get(Def: getVecOp());
3742 Value *EVL = State.get(Def: getEVL(), Lane: VPLane(0));
3743
3744 Value *Mask;
3745 if (VPValue *CondOp = getCondOp())
3746 Mask = State.get(Def: CondOp);
3747 else
3748 Mask = Builder.CreateVectorSplat(EC: State.VF, V: 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>(Val: VecOp->getType());
3756 Value *Identity = getRecurrenceIdentity(K: Kind, Tp: VecTy->getElementType(),
3757 FMF: getFastMathFlagsOrNone());
3758 Identity =
3759 State.Builder.CreateVectorSplat(EC: VecTy->getElementCount(), V: Identity);
3760
3761 // TODO: Calculate the predicate cost for the partial reduction.
3762 Value *NewVecOp = State.Builder.CreateIntrinsic(
3763 RetTy: VecTy, ID: Intrinsic::vp_merge, Args: {Mask, VecOp, Identity, EVL});
3764 assert((Kind == RecurKind::Add || Kind == RecurKind::FAdd) &&
3765 "Unexpected partial reduction kind");
3766 NewRed = State.Builder.CreateIntrinsic(
3767 RetTy: Prev->getType(),
3768 ID: Kind == RecurKind::Add ? Intrinsic::vector_partial_reduce_add
3769 : Intrinsic::vector_partial_reduce_fadd,
3770 Args: {Prev, NewVecOp}, FMFSource: State.Builder.getFastMathFlags(), Name: "partial.reduce");
3771 } else if (isOrdered()) {
3772 NewRed = createOrderedReduction(B&: Builder, RdxKind: Kind, Src: VecOp, Start: Prev, Mask, EVL);
3773 } else {
3774 NewRed = createSimpleReduction(B&: Builder, Src: VecOp, RdxKind: Kind, Mask, EVL);
3775 if (RecurrenceDescriptor::isMinMaxRecurrenceKind(Kind))
3776 NewRed = createMinMaxOp(Builder, RK: Kind, Left: NewRed, Right: Prev);
3777 else
3778 NewRed = Builder.CreateBinOp(
3779 Opc: (Instruction::BinaryOps)RecurrenceDescriptor::getOpcode(Kind), LHS: NewRed,
3780 RHS: Prev);
3781 }
3782 State.set(Def: this, V: NewRed, IsScalar: !isPartialReduction());
3783}
3784
3785InstructionCost VPReductionRecipe::computeCost(ElementCount VF,
3786 VPCostContext &Ctx) const {
3787 RecurKind RdxKind = getRecurrenceKind();
3788 Type *ElementTy = this->getScalarType();
3789 auto *VectorTy = cast<VectorType>(Val: toVectorTy(Scalar: ElementTy, EC: VF));
3790 unsigned Opcode = RecurrenceDescriptor::getOpcode(Kind: RdxKind);
3791 FastMathFlags FMFs = getFastMathFlagsOrNone();
3792 std::optional<FastMathFlags> OptionalFMF =
3793 ElementTy->isFloatingPointTy() ? std::make_optional(t&: FMFs) : std::nullopt;
3794
3795 if (isPartialReduction()) {
3796 InstructionCost CondCost = 0;
3797 if (isConditional()) {
3798 CmpInst::Predicate Pred = CmpInst::BAD_ICMP_PREDICATE;
3799 auto *CondTy =
3800 cast<VectorType>(Val: toVectorTy(Scalar: getCondOp()->getScalarType(), EC: VF));
3801 CondCost = Ctx.TTI.getCmpSelInstrCost(Opcode: Instruction::Select, ValTy: VectorTy,
3802 CondTy, VecPred: Pred, CostKind: Ctx.CostKind);
3803 }
3804 return CondCost + Ctx.TTI.getPartialReductionCost(
3805 Opcode, InputTypeA: ElementTy, InputTypeB: nullptr, AccumType: ElementTy, VF,
3806 OpAExtend: TTI::PR_None, OpBExtend: TTI::PR_None, BinOp: {}, CostKind: Ctx.CostKind,
3807 FMF: OptionalFMF);
3808 }
3809
3810 // TODO: Support any-of reductions.
3811 assert(
3812 (!RecurrenceDescriptor::isAnyOfRecurrenceKind(RdxKind) ||
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().
3818 if (RecurrenceDescriptor::isMinMaxRecurrenceKind(Kind: RdxKind)) {
3819 Intrinsic::ID Id = getMinMaxReductionIntrinsicOp(RK: RdxKind);
3820 return Ctx.TTI.getMinMaxReductionCost(IID: Id, Ty: VectorTy, FMF: FMFs, CostKind: 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, Ty: VectorTy, FMF: OptionalFMF,
3826 CostKind: Ctx.CostKind);
3827}
3828
3829VPExpressionRecipe::VPExpressionRecipe(
3830 ExpressionTypes ExpressionType,
3831 ArrayRef<VPSingleDefRecipe *> ExpressionRecipes)
3832 : VPSingleDefRecipe(VPRecipeBase::VPExpressionSC, {},
3833 [&]() {
3834 if (ExpressionType == ExpressionTypes::FoldedVPMerge)
3835 return ExpressionRecipes.back()->getScalarType();
3836 return cast<VPReductionRecipe>(
3837 Val: 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(Ptr: 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(C&: ExpressionRecipes)) {
3857 if (R != ExpressionRecipes.back() &&
3858 any_of(Range: R->users(), P: [&ExpressionRecipesAsSetOfUsers](VPUser *U) {
3859 return !ExpressionRecipesAsSetOfUsers.contains(Ptr: 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(New: CopyForExtUsers,
3865 ShouldReplace: [&ExpressionRecipesAsSetOfUsers](VPUser *U) {
3866 return !ExpressionRecipesAsSetOfUsers.contains(Ptr: U);
3867 });
3868 CopyForExtUsers->insertBefore(InsertPos: 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(First: R->operands())) {
3880 auto *Def = Op->getDefiningRecipe();
3881 if (Def && ExpressionRecipesAsSetOfUsers.contains(Ptr: Def))
3882 continue;
3883 addOperand(Operand: Op);
3884 LiveInPlaceholders.push_back(Elt: 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(t: operands(), u&: LiveInPlaceholders))
3892 R->replaceUsesOfWith(From: LiveIn, To: Tmp);
3893}
3894
3895SmallVector<VPSingleDefRecipe *> VPExpressionRecipe::decompose() {
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(InsertPos: this);
3901
3902 for (const auto &[Idx, Op] : enumerate(First: operands()))
3903 LiveInPlaceholders[Idx]->replaceAllUsesWith(New: Op);
3904
3905 replaceAllUsesWith(New: ExpressionRecipes.back());
3906 SmallVector<VPSingleDefRecipe *> DecomposedRecipes(ExpressionRecipes);
3907 ExpressionRecipes.clear();
3908 return DecomposedRecipes;
3909}
3910
3911bool VPExpressionRecipe::usesFirstLaneOnly(const VPValue *Op) const {
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
3924InstructionCost VPExpressionRecipe::computeCost(ElementCount VF,
3925 VPCostContext &Ctx) const {
3926 // The last recipes in the chain will be optimized away, so igonre the cost.
3927 if (ExpressionType == ExpressionTypes::FoldedVPMerge) {
3928 InstructionCost Cost = 0;
3929 for (auto *R : drop_end(RangeOrContainer: ExpressionRecipes))
3930 Cost += R->cost(VF, Ctx);
3931 return Cost;
3932 }
3933
3934 Type *RedTy = this->getScalarType();
3935 auto *SrcVecTy =
3936 cast<VectorType>(Val: toVectorTy(Scalar: getOperand(N: 0)->getScalarType(), EC: VF));
3937 unsigned Opcode = RecurrenceDescriptor::getOpcode(
3938 Kind: cast<VPReductionRecipe>(Val: 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>(Val: ExpressionRecipes.back());
3947 auto *ExtR = cast<VPWidenCastRecipe>(Val: ExpressionRecipes[0]);
3948
3949 if (RedR->isPartialReduction())
3950 return Ctx.TTI.getPartialReductionCost(
3951 Opcode, InputTypeA: getOperand(N: 0)->getScalarType(), InputTypeB: nullptr, AccumType: RedTy, VF,
3952 OpAExtend: TargetTransformInfo::getPartialReductionExtendKind(CastOpc: ExtR->getOpcode()),
3953 OpBExtend: TargetTransformInfo::PR_None, BinOp: std::nullopt, CostKind: Ctx.CostKind,
3954 FMF: 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, IsUnsigned: ExtR->getOpcode() == Instruction::ZExt, ResTy: RedTy, Ty: SrcVecTy,
3961 FMF: std::nullopt, CostKind: Ctx.CostKind);
3962 else
3963 return InstructionCost::getInvalid();
3964 }
3965 case ExpressionTypes::MulAccReduction:
3966 return Ctx.TTI.getMulAccReductionCost(IsUnsigned: false, RedOpcode: Opcode, ResTy: RedTy, Ty: SrcVecTy,
3967 CostKind: 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>(Val: ExpressionRecipes.back());
3983 if (RedR->isPartialReduction()) {
3984 auto *Ext0R = cast<VPWidenCastRecipe>(Val: ExpressionRecipes[0]);
3985 auto *Ext1R = cast<VPWidenCastRecipe>(Val: ExpressionRecipes[1]);
3986 auto *Mul = cast<VPWidenRecipe>(Val: ExpressionRecipes[2]);
3987 return Ctx.TTI.getPartialReductionCost(
3988 Opcode, InputTypeA: getOperand(N: 0)->getScalarType(),
3989 InputTypeB: getOperand(N: 1)->getScalarType(), AccumType: RedTy, VF,
3990 OpAExtend: TargetTransformInfo::getPartialReductionExtendKind(
3991 CastOpc: Ext0R->getOpcode()),
3992 OpBExtend: TargetTransformInfo::getPartialReductionExtendKind(
3993 CastOpc: Ext1R->getOpcode()),
3994 BinOp: Mul->getOpcode(), CostKind: Ctx.CostKind,
3995 FMF: 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 IsUnsigned: cast<VPWidenCastRecipe>(Val: ExpressionRecipes.front())->getOpcode() ==
4002 Instruction::ZExt,
4003 RedOpcode: Opcode, ResTy: RedTy, Ty: SrcVecTy, CostKind: 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
4011bool VPExpressionRecipe::mayReadOrWriteMemory() const {
4012 return any_of(Range: ExpressionRecipes, P: [](VPSingleDefRecipe *R) {
4013 return R->mayReadFromMemory() || R->mayWriteToMemory();
4014 });
4015}
4016
4017bool VPExpressionRecipe::mayHaveSideEffects() const {
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
4025bool VPExpressionRecipe::isVectorToScalar() const {
4026 auto *RR = dyn_cast<VPReductionRecipe>(Val: ExpressionRecipes.back());
4027 return RR && !RR->isPartialReduction();
4028}
4029
4030#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4031
4032void VPExpressionRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
4033 VPSlotTracker &SlotTracker) const {
4034 O << Indent << "EXPRESSION ";
4035 printAsOperand(O, SlotTracker);
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 =
4075 isa<VPReductionEVLRecipe>(Red)
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;
4095 getLastOperand()->printAsOperand(O, SlotTracker);
4096 O << " + " << (Red->isPartialReduction() ? "partial." : "") << "reduce.";
4097 O << Instruction::getOpcodeName(Opcode) << " (";
4098 if (Negated)
4099 O << (Opcode == Instruction::Add ? "sub (0, " : "fneg(");
4100 getOperand(0)->printAsOperand(O, SlotTracker);
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.";
4115 O << Instruction::getOpcodeName(
4116 RecurrenceDescriptor::getOpcode(Red->getRecurrenceKind()))
4117 << " (sub (0, mul";
4118 auto *Mul = cast<VPWidenRecipe>(ExpressionRecipes[2]);
4119 Mul->printFlags(O);
4120 O << "(";
4121 getOperand(0)->printAsOperand(O, SlotTracker);
4122 auto *Ext0 = cast<VPWidenCastRecipe>(ExpressionRecipes[0]);
4123 O << " " << Instruction::getOpcodeName(Ext0->getOpcode()) << " to "
4124 << *Ext0->getScalarType() << "), (";
4125 getOperand(1)->printAsOperand(O, SlotTracker);
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.";
4137 O << Instruction::getOpcodeName(
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 << "(";
4147 getOperand(0)->printAsOperand(O, SlotTracker);
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 }
4155 getOperand(1)->printAsOperand(O, SlotTracker);
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
4170void VPReductionRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
4171 VPSlotTracker &SlotTracker) const {
4172 if (isPartialReduction())
4173 O << Indent << "PARTIAL-REDUCE ";
4174 else
4175 O << Indent << "REDUCE ";
4176 printAsOperand(O, SlotTracker);
4177 O << " = ";
4178 getChainOp()->printAsOperand(O, SlotTracker);
4179 O << " +";
4180 printFlags(O);
4181 O << " reduce.";
4182 printRecurrenceKind(O, getRecurrenceKind());
4183 O << " (";
4184 getVecOp()->printAsOperand(O, SlotTracker);
4185 if (isConditional()) {
4186 O << ", ";
4187 getCondOp()->printAsOperand(O, SlotTracker);
4188 }
4189 O << ")";
4190}
4191
4192void VPReductionEVLRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
4193 VPSlotTracker &SlotTracker) const {
4194 if (isPartialReduction())
4195 O << Indent << "PARTIAL-REDUCE ";
4196 else
4197 O << Indent << "REDUCE ";
4198 printAsOperand(O, SlotTracker);
4199 O << " = ";
4200 getChainOp()->printAsOperand(O, SlotTracker);
4201 O << " +";
4202 printFlags(O);
4203 O << " vp.reduce."
4204 << Instruction::getOpcodeName(
4205 RecurrenceDescriptor::getOpcode(getRecurrenceKind()))
4206 << " (";
4207 getVecOp()->printAsOperand(O, SlotTracker);
4208 O << ", ";
4209 getEVL()->printAsOperand(O, SlotTracker);
4210 if (isConditional()) {
4211 O << ", ";
4212 getCondOp()->printAsOperand(O, SlotTracker);
4213 }
4214 O << ")";
4215}
4216
4217#endif
4218
4219void VPReplicateRecipe::execute(VPTransformState &State) {
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(Ty: ResultTy);
4232 }
4233
4234 Cloned->dropUBImplyingAttrsAndUnknownMetadata();
4235 Cloned->dropPoisonGeneratingAttributes();
4236 Cloned->dropPoisonGeneratingFlags();
4237 applyFlags(I&: *Cloned);
4238 applyMetadata(I&: *Cloned);
4239
4240 if (hasPredicate())
4241 cast<CmpInst>(Val: 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(Size: Cloned->getNumOperands()))
4246 Cloned->setOperand(i: Idx, Val: State.get(Def: getOperand(N: Idx), NeedsSingleScalar: true));
4247
4248 // Place the cloned scalar in the new loop.
4249 State.Builder.Insert(I: Cloned);
4250
4251 State.set(Def: this, V: Cloned, IsScalar: true);
4252
4253 // If we just cloned a new assumption, add it the assumption cache.
4254 if (auto *II = dyn_cast<AssumeInst>(Val: Cloned))
4255 State.AC->registerAssumption(CI: 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,
4264 PredicatedScalarEvolution &PSE,
4265 const Loop *L) {
4266 const SCEV *Addr = vputils::getSCEVExprForVPValue(V: Ptr, PSE, L);
4267 if (isa<SCEVCouldNotCompute>(Val: Addr))
4268 return Addr;
4269
4270 return vputils::isAddressSCEVForCost(Addr, SE&: *PSE.getSE(), L) ? Addr : nullptr;
4271}
4272
4273InstructionCost VPReplicateRecipe::computeCost(ElementCount VF,
4274 VPCostContext &Ctx) const {
4275 Instruction *UI = cast<Instruction>(Val: getUnderlyingValue());
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(Ptr: UI);
4279
4280 if (VF.isScalable() && !isSingleScalar())
4281 return InstructionCost::getInvalid();
4282
4283 switch (UI->getOpcode()) {
4284 case Instruction::Alloca:
4285 if (VF.isScalable())
4286 return InstructionCost::getInvalid();
4287 return Ctx.TTI.getArithmeticInstrCost(Opcode: Instruction::Mul,
4288 Ty: this->getScalarType(), CostKind: 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>(Val: getLastOperand()->getLiveInIRValue());
4297 Type *ResultTy = this->getScalarType();
4298 return computeCallCost(CalledFn, ResultTy, ArgOps: drop_end(RangeOrContainer: operands()),
4299 IsSingleScalar: 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:
4319 return getCostForRecipeWithOpcode(Opcode: getOpcode(), VF: ElementCount::getFixed(MinVal: 1),
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 =
4327 getCostForRecipeWithOpcode(Opcode: getOpcode(), VF: ElementCount::getFixed(MinVal: 1), Ctx);
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(Range: operands(), P: [&Ctx, VF](VPValue *Op) {
4335 auto *PredR = dyn_cast<VPPredInstPHIRecipe>(Val: Op);
4336 if (!PredR)
4337 return false;
4338 return Ctx.skipCostComputation(
4339 UI: dyn_cast_or_null<Instruction>(
4340 Val: PredR->getOperand(N: 0)->getUnderlyingValue()),
4341 IsVector: VF.isVector());
4342 }))
4343 return Ctx.getLegacyCost(UI, VF);
4344
4345 ScalarCost = ScalarCost * VF.getFixedValue() +
4346 Ctx.getScalarizationOverhead(ResultTy: this->getScalarType(),
4347 Operands: to_vector(Range: 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(Opcode: Instruction::PHI, CostKind: 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 Freq: 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(N: !IsLoad);
4368 const SCEV *PtrSCEV = getAddressAccessSCEV(Ptr: PtrOp, PSE&: Ctx.PSE, L: Ctx.L);
4369 if (isa_and_nonnull<SCEVCouldNotCompute>(Val: PtrSCEV)) {
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 return Ctx.getLegacyCost(UI, VF);
4375 PtrSCEV = nullptr;
4376 }
4377
4378 Type *ValTy = (IsLoad ? this : getOperand(N: 0))->getScalarType();
4379 Type *ScalarPtrTy = PtrOp->getScalarType();
4380 const Align Alignment = getLoadStoreAlignment(I: UI);
4381 unsigned AS = cast<PointerType>(Val: ScalarPtrTy)->getAddressSpace();
4382 TTI::OperandValueInfo OpInfo = TTI::getOperandInfo(V: UI->getOperand(i: 0));
4383 bool PreferVectorizedAddressing = Ctx.TTI.prefersVectorizedAddressing();
4384 bool UsedByLoadStoreAddress =
4385 !PreferVectorizedAddressing && vputils::isUsedByLoadStoreAddress(V: this);
4386 InstructionCost ScalarMemOpCost = Ctx.TTI.getMemoryOpCost(
4387 Opcode: UI->getOpcode(), Src: ValTy, Alignment, AddressSpace: AS, CostKind: Ctx.CostKind, OpdInfo: OpInfo,
4388 I: UsedByLoadStoreAddress ? UI : nullptr);
4389
4390 Type *PtrTy = isSingleScalar() ? ScalarPtrTy : toVectorTy(Scalar: ScalarPtrTy, EC: VF);
4391 InstructionCost ScalarCost =
4392 ScalarMemOpCost +
4393 Ctx.TTI.getAddressComputationCost(
4394 PtrTy, SE: UsedByLoadStoreAddress ? nullptr : Ctx.PSE.getSE(), Ptr: PtrSCEV,
4395 CostKind: Ctx.CostKind);
4396 if (isSingleScalar())
4397 return ScalarCost;
4398
4399 SmallVector<const VPValue *> OpsToScalarize;
4400 Type *ResultTy = Type::getVoidTy(C&: 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(C&: OpsToScalarize, R: operands());
4411
4412 if (!EfficientVectorLoadStore)
4413 ResultTy = this->getScalarType();
4414 }
4415
4416 TTI::VectorInstrContext VIC =
4417 IsLoad ? TTI::VectorInstrContext::Load : TTI::VectorInstrContext::Store;
4418 InstructionCost Cost =
4419 (ScalarCost * VF.getFixedValue()) +
4420 Ctx.getScalarizationOverhead(ResultTy, Operands: OpsToScalarize, VF, VIC, AlwaysIncludeReplicatingR: 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 Freq: ParentRegion->getEntryBranchOnMask()->getExecutionFrequency());
4427
4428 if (Ctx.useEmulatedMaskMemRefHack(R: 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: {
4451 return getCostForRecipeWithOpcode(Opcode: getOpcode(), VF: ElementCount::getFixed(MinVal: 1),
4452 Ctx) *
4453 (isSingleScalar() ? 1 : VF.getFixedValue());
4454 }
4455 case Instruction::ExtractValue:
4456 return Ctx.TTI.getInsertExtractValueCost(Opcode: getOpcode(), CostKind: Ctx.CostKind);
4457 default:
4458 // This opcode is unknown. Assume that it is the same as 'mul'.
4459 return Ctx.TTI.getArithmeticInstrCost(Opcode: Instruction::Mul,
4460 Ty: this->getScalarType(), CostKind: Ctx.CostKind) *
4461 (isSingleScalar() ? 1 : VF.getFixedValue());
4462 }
4463}
4464
4465InstructionCost VPReplicateRecipe::computeCallCost(
4466 Function *CalledFn, Type *ResultTy, ArrayRef<const VPValue *> ArgOps,
4467 bool IsSingleScalar, ElementCount VF, VPCostContext &Ctx) {
4468 SmallVector<Type *, 4> Tys = map_to_vector<4>(
4469 C&: ArgOps, F: [&](const VPValue *Op) { return Op->getScalarType(); });
4470
4471 Intrinsic::ID IntrinID = CalledFn->getIntrinsicID();
4472 auto GetIntrinsicCost = [&] {
4473 if (!IntrinID)
4474 return InstructionCost::getInvalid();
4475 return Ctx.TTI.getIntrinsicInstrCost(
4476 ICA: IntrinsicCostAttributes(IntrinID, ResultTy, Tys), CostKind: Ctx.CostKind);
4477 };
4478
4479 if (IntrinID && VPCostContext::isFreeScalarIntrinsic(ID: IntrinID)) {
4480 assert(GetIntrinsicCost() == 0 && "scalarizing intrinsic should be free");
4481 return 0;
4482 }
4483
4484 InstructionCost ScalarCallCost =
4485 Ctx.TTI.getCallInstrCost(F: CalledFn, RetTy: ResultTy, Tys, CostKind: Ctx.CostKind);
4486 if (IsSingleScalar) {
4487 ScalarCallCost = std::min(a: ScalarCallCost, b: GetIntrinsicCost());
4488 return ScalarCallCost;
4489 }
4490
4491 // Scalarization overhead is undefined for scalable VFs.
4492 if (VF.isScalable())
4493 return InstructionCost::getInvalid();
4494
4495 return ScalarCallCost * VF.getFixedValue() +
4496 Ctx.getScalarizationOverhead(ResultTy, Operands: ArgOps, VF);
4497}
4498
4499#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4500void VPReplicateRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
4501 VPSlotTracker &SlotTracker) const {
4502 O << Indent << (IsSingleScalar ? "CLONE " : "REPLICATE ");
4503
4504 if (!getScalarType()->isVoidTy()) {
4505 printAsOperand(O, SlotTracker);
4506 O << " = ";
4507 }
4508 if (auto *CB = dyn_cast<CallBase>(getUnderlyingInstr())) {
4509 O << "call";
4510 printFlags(O);
4511 O << "@" << CB->getCalledFunction()->getName() << "(";
4512 interleaveComma(drop_end(operands()), O, [&O, &SlotTracker](VPValue *Op) {
4513 Op->printAsOperand(O, SlotTracker);
4514 });
4515 O << ")";
4516 } else {
4517 O << Instruction::getOpcodeName(getUnderlyingInstr()->getOpcode());
4518 printFlags(O);
4519 printOperands(O, SlotTracker);
4520 }
4521
4522 // Find if the recipe is used by a widened recipe via an intervening
4523 // VPPredInstPHIRecipe. In this case, also pack the scalar values in a vector.
4524 if (any_of(users(), [](const VPUser *U) {
4525 if (auto *PredR = dyn_cast<VPPredInstPHIRecipe>(U))
4526 return !vputils::onlyScalarValuesUsed(PredR);
4527 return false;
4528 }))
4529 O << " (S->V)";
4530}
4531#endif
4532
4533void VPBranchOnMaskRecipe::execute(VPTransformState &State) {
4534 llvm_unreachable("recipe must be removed when dissolving replicate region");
4535}
4536
4537InstructionCost VPBranchOnMaskRecipe::computeCost(ElementCount VF,
4538 VPCostContext &Ctx) const {
4539 // Replicating isn't supported for scalable vectors.
4540 if (VF.isScalable())
4541 return InstructionCost::getInvalid();
4542 auto *VecI1Ty = VectorType::get(ElementType: Type::getInt1Ty(C&: Ctx.LLVMCtx), EC: VF);
4543 return Ctx.TTI.getScalarizationOverhead(
4544 Ty: VecI1Ty, DemandedElts: APInt::getAllOnes(numBits: VF.getFixedValue()),
4545 /*Insert=*/false, /*Extract=*/true, CostKind: Ctx.CostKind) +
4546 VF.getFixedValue() *
4547 Ctx.TTI.getCFInstrCost(Opcode: Instruction::CondBr, CostKind: Ctx.CostKind);
4548}
4549
4550void VPPredInstPHIRecipe::execute(VPTransformState &State) {
4551 llvm_unreachable("recipe must be removed when dissolving replicate region");
4552}
4553
4554#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4555void VPPredInstPHIRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
4556 VPSlotTracker &SlotTracker) const {
4557 O << Indent << "PHI-PREDICATED-INSTRUCTION ";
4558 printAsOperand(O, SlotTracker);
4559 O << " = ";
4560 printOperands(O, SlotTracker);
4561}
4562#endif
4563
4564VPRecipeBase *VPWidenLoadRecipe::getAsRecipe() { return this; }
4565const VPRecipeBase *VPWidenLoadRecipe::getAsRecipe() const { return this; }
4566
4567VPRecipeBase *VPWidenLoadEVLRecipe::getAsRecipe() { return this; }
4568const VPRecipeBase *VPWidenLoadEVLRecipe::getAsRecipe() const { return this; }
4569
4570VPRecipeBase *VPWidenStoreRecipe::getAsRecipe() { return this; }
4571const VPRecipeBase *VPWidenStoreRecipe::getAsRecipe() const { return this; }
4572
4573VPRecipeBase *VPWidenStoreEVLRecipe::getAsRecipe() { return this; }
4574const VPRecipeBase *VPWidenStoreEVLRecipe::getAsRecipe() const { return this; }
4575
4576InstructionCost VPWidenMemoryRecipe::computeCost(ElementCount VF,
4577 VPCostContext &Ctx) const {
4578 const VPRecipeBase *R = getAsRecipe();
4579 bool IsLoad = isa<VPWidenLoadRecipe, VPWidenLoadEVLRecipe>(Val: R);
4580 Type *ScalarTy = IsLoad ? cast<VPSingleDefRecipe>(Val: R)->getScalarType()
4581 : R->getOperand(N: 1)->getScalarType();
4582 Type *Ty = toVectorTy(Scalar: ScalarTy, EC: VF);
4583 unsigned AS =
4584 cast<PointerType>(Val: getAddr()->getScalarType())->getAddressSpace();
4585 unsigned Opcode = IsLoad ? Instruction::Load : Instruction::Store;
4586
4587 if (!Consecutive) {
4588 // TODO: Using the original IR may not be accurate.
4589 // Currently, ARM will use the underlying IR to calculate gather/scatter
4590 // instruction cost.
4591 Type *PtrTy = getAddr()->getScalarType();
4592 const Value *Ptr = getAddr()->getUnderlyingValue();
4593
4594 // If the address value is uniform across all lanes, then the address can be
4595 // calculated with scalar type and broadcast.
4596 if (!vputils::isSingleScalar(VPV: getAddr()))
4597 PtrTy = toVectorTy(Scalar: PtrTy, EC: VF);
4598
4599 unsigned IID = isa<VPWidenLoadRecipe>(Val: R) ? Intrinsic::masked_gather
4600 : isa<VPWidenStoreRecipe>(Val: R) ? Intrinsic::masked_scatter
4601 : isa<VPWidenLoadEVLRecipe>(Val: R) ? Intrinsic::vp_gather
4602 : Intrinsic::vp_scatter;
4603 return Ctx.TTI.getAddressComputationCost(PtrTy, SE: nullptr, Ptr: nullptr,
4604 CostKind: Ctx.CostKind) +
4605 Ctx.TTI.getMemIntrinsicInstrCost(
4606 MICA: MemIntrinsicCostAttributes(IID, Ty, Ptr, IsMasked, Alignment,
4607 &Ingredient),
4608 CostKind: Ctx.CostKind);
4609 }
4610
4611 InstructionCost Cost = 0;
4612 if (IsMasked) {
4613 unsigned IID = isa<VPWidenLoadRecipe>(Val: R) ? Intrinsic::masked_load
4614 : Intrinsic::masked_store;
4615 Cost += Ctx.TTI.getMemIntrinsicInstrCost(
4616 MICA: MemIntrinsicCostAttributes(IID, Ty, Alignment, AS), CostKind: Ctx.CostKind);
4617 } else {
4618 TTI::OperandValueInfo OpInfo = Ctx.getOperandInfo(
4619 V: isa<VPWidenLoadRecipe, VPWidenLoadEVLRecipe>(Val: R) ? R->getOperand(N: 0)
4620 : R->getOperand(N: 1));
4621 Cost += Ctx.TTI.getMemoryOpCost(Opcode, Src: Ty, Alignment, AddressSpace: AS, CostKind: Ctx.CostKind,
4622 OpdInfo: OpInfo, I: &Ingredient);
4623 }
4624 return Cost;
4625}
4626
4627void VPWidenLoadRecipe::execute(VPTransformState &State) {
4628 Type *ScalarDataTy = getScalarType();
4629 auto *DataTy = VectorType::get(ElementType: ScalarDataTy, EC: State.VF);
4630 bool CreateGather = !isConsecutive();
4631
4632 auto &Builder = State.Builder;
4633 Value *Mask = nullptr;
4634 if (auto *VPMask = getMask())
4635 Mask = State.get(Def: VPMask);
4636
4637 Value *Addr = State.get(Def: getAddr(), /*NeedsSingleScalar=*/!CreateGather);
4638 Value *NewLI;
4639 if (CreateGather) {
4640 NewLI = Builder.CreateMaskedGather(Ty: DataTy, Ptrs: Addr, Alignment, Mask, PassThru: nullptr,
4641 Name: "wide.masked.gather");
4642 } else if (Mask) {
4643 NewLI =
4644 Builder.CreateMaskedLoad(Ty: DataTy, Ptr: Addr, Alignment, Mask,
4645 PassThru: PoisonValue::get(T: DataTy), Name: "wide.masked.load");
4646 } else {
4647 NewLI = Builder.CreateAlignedLoad(Ty: DataTy, Ptr: Addr, Align: Alignment, Name: "wide.load");
4648 }
4649 applyMetadata(I&: *cast<Instruction>(Val: NewLI));
4650 State.set(Def: this, V: NewLI);
4651}
4652
4653#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4654void VPWidenLoadRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
4655 VPSlotTracker &SlotTracker) const {
4656 O << Indent << "WIDEN ";
4657 printAsOperand(O, SlotTracker);
4658 O << " = load ";
4659 printOperands(O, SlotTracker);
4660 O << ", align " << getAlign().value();
4661}
4662#endif
4663
4664void VPWidenLoadEVLRecipe::execute(VPTransformState &State) {
4665 Type *ScalarDataTy = getScalarType();
4666 auto *DataTy = VectorType::get(ElementType: ScalarDataTy, EC: State.VF);
4667 bool CreateGather = !isConsecutive();
4668
4669 auto &Builder = State.Builder;
4670 CallInst *NewLI;
4671 Value *EVL = State.get(Def: getEVL(), Lane: VPLane(0));
4672 Value *Addr = State.get(Def: getAddr(), NeedsSingleScalar: !CreateGather);
4673 Value *Mask = nullptr;
4674 if (VPValue *VPMask = getMask())
4675 Mask = State.get(Def: VPMask);
4676 else
4677 Mask = Builder.CreateVectorSplat(EC: State.VF, V: Builder.getTrue());
4678
4679 if (CreateGather) {
4680 NewLI = Builder.CreateIntrinsicWithoutFolding(RetTy: DataTy, ID: Intrinsic::vp_gather,
4681 Args: {Addr, Mask, EVL}, FMFSource: nullptr,
4682 Name: "wide.masked.gather");
4683 } else {
4684 NewLI = Builder.CreateIntrinsicWithoutFolding(
4685 RetTy: DataTy, ID: Intrinsic::vp_load, Args: {Addr, Mask, EVL}, FMFSource: nullptr, Name: "vp.op.load");
4686 }
4687 NewLI->addParamAttr(
4688 ArgNo: 0, Attr: Attribute::getWithAlignment(Context&: NewLI->getContext(), Alignment));
4689 applyMetadata(I&: *NewLI);
4690 State.set(Def: this, V: NewLI);
4691}
4692
4693InstructionCost VPWidenLoadEVLRecipe::computeCost(ElementCount VF,
4694 VPCostContext &Ctx) const {
4695 if (!Consecutive || IsMasked)
4696 return VPWidenMemoryRecipe::computeCost(VF, Ctx);
4697
4698 // We need to use the getMemIntrinsicInstrCost() instead of getMemoryOpCost()
4699 // here because the EVL recipes using EVL to replace the tail mask. But in the
4700 // legacy model, it will always calculate the cost of mask.
4701 // TODO: Using getMemoryOpCost() instead of getMemIntrinsicInstrCost when we
4702 // don't need to compare to the legacy cost model.
4703 Type *Ty = toVectorTy(Scalar: getScalarType(), EC: VF);
4704 unsigned AS =
4705 cast<PointerType>(Val: getAddr()->getScalarType())->getAddressSpace();
4706 return Ctx.TTI.getMemIntrinsicInstrCost(
4707 MICA: MemIntrinsicCostAttributes(Intrinsic::vp_load, Ty, Alignment, AS),
4708 CostKind: Ctx.CostKind);
4709}
4710
4711#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4712void VPWidenLoadEVLRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
4713 VPSlotTracker &SlotTracker) const {
4714 O << Indent << "WIDEN ";
4715 printAsOperand(O, SlotTracker);
4716 O << " = vp.load ";
4717 printOperands(O, SlotTracker);
4718 O << ", align " << getAlign().value();
4719}
4720#endif
4721
4722void VPWidenStoreRecipe::execute(VPTransformState &State) {
4723 VPValue *StoredVPValue = getStoredValue();
4724 bool CreateScatter = !isConsecutive();
4725
4726 auto &Builder = State.Builder;
4727
4728 Value *Mask = nullptr;
4729 if (auto *VPMask = getMask())
4730 Mask = State.get(Def: VPMask);
4731
4732 Value *StoredVal = State.get(Def: StoredVPValue);
4733 Value *Addr = State.get(Def: getAddr(), /*NeedsSingleScalar=*/!CreateScatter);
4734 Instruction *NewSI = nullptr;
4735 if (CreateScatter)
4736 NewSI = Builder.CreateMaskedScatter(Val: StoredVal, Ptrs: Addr, Alignment, Mask);
4737 else if (Mask)
4738 NewSI = Builder.CreateMaskedStore(Val: StoredVal, Ptr: Addr, Alignment, Mask);
4739 else
4740 NewSI = Builder.CreateAlignedStore(Val: StoredVal, Ptr: Addr, Align: Alignment);
4741 applyMetadata(I&: *NewSI);
4742}
4743
4744#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4745void VPWidenStoreRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
4746 VPSlotTracker &SlotTracker) const {
4747 O << Indent << "WIDEN store ";
4748 printOperands(O, SlotTracker);
4749 O << ", align " << getAlign().value();
4750}
4751#endif
4752
4753void VPWidenStoreEVLRecipe::execute(VPTransformState &State) {
4754 VPValue *StoredValue = getStoredValue();
4755 bool CreateScatter = !isConsecutive();
4756
4757 auto &Builder = State.Builder;
4758
4759 CallInst *NewSI = nullptr;
4760 Value *StoredVal = State.get(Def: StoredValue);
4761 Value *EVL = State.get(Def: getEVL(), Lane: VPLane(0));
4762 Value *Mask = nullptr;
4763 if (VPValue *VPMask = getMask())
4764 Mask = State.get(Def: VPMask);
4765 else
4766 Mask = Builder.CreateVectorSplat(EC: State.VF, V: Builder.getTrue());
4767
4768 Value *Addr = State.get(Def: getAddr(), NeedsSingleScalar: !CreateScatter);
4769 if (CreateScatter) {
4770 NewSI = Builder.CreateIntrinsicWithoutFolding(
4771 RetTy: Type::getVoidTy(C&: EVL->getContext()), ID: Intrinsic::vp_scatter,
4772 Args: {StoredVal, Addr, Mask, EVL});
4773 } else {
4774 NewSI = Builder.CreateIntrinsicWithoutFolding(
4775 RetTy: Type::getVoidTy(C&: EVL->getContext()), ID: Intrinsic::vp_store,
4776 Args: {StoredVal, Addr, Mask, EVL});
4777 }
4778 NewSI->addParamAttr(
4779 ArgNo: 1, Attr: Attribute::getWithAlignment(Context&: NewSI->getContext(), Alignment));
4780 applyMetadata(I&: *NewSI);
4781}
4782
4783InstructionCost VPWidenStoreEVLRecipe::computeCost(ElementCount VF,
4784 VPCostContext &Ctx) const {
4785 if (!Consecutive || IsMasked)
4786 return VPWidenMemoryRecipe::computeCost(VF, Ctx);
4787
4788 // We need to use the getMemIntrinsicInstrCost() instead of getMemoryOpCost()
4789 // here because the EVL recipes using EVL to replace the tail mask. But in the
4790 // legacy model, it will always calculate the cost of mask.
4791 // TODO: Using getMemoryOpCost() instead of getMemIntrinsicInstrCost when we
4792 // don't need to compare to the legacy cost model.
4793 Type *Ty = toVectorTy(Scalar: getStoredValue()->getScalarType(), EC: VF);
4794 unsigned AS =
4795 cast<PointerType>(Val: getAddr()->getScalarType())->getAddressSpace();
4796 return Ctx.TTI.getMemIntrinsicInstrCost(
4797 MICA: MemIntrinsicCostAttributes(Intrinsic::vp_store, Ty, Alignment, AS),
4798 CostKind: Ctx.CostKind);
4799}
4800
4801#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4802void VPWidenStoreEVLRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
4803 VPSlotTracker &SlotTracker) const {
4804 O << Indent << "WIDEN vp.store ";
4805 printOperands(O, SlotTracker);
4806 O << ", align " << getAlign().value();
4807}
4808#endif
4809
4810static Value *createBitOrPointerCast(IRBuilderBase &Builder, Value *V,
4811 VectorType *DstVTy, const DataLayout &DL) {
4812 // Verify that V is a vector type with same number of elements as DstVTy.
4813 auto VF = DstVTy->getElementCount();
4814 auto *SrcVecTy = cast<VectorType>(Val: V->getType());
4815 assert(VF == SrcVecTy->getElementCount() && "Vector dimensions do not match");
4816 Type *SrcElemTy = SrcVecTy->getElementType();
4817 Type *DstElemTy = DstVTy->getElementType();
4818 assert((DL.getTypeSizeInBits(SrcElemTy) == DL.getTypeSizeInBits(DstElemTy)) &&
4819 "Vector elements must have same size");
4820
4821 // Do a direct cast if element types are castable.
4822 if (CastInst::isBitOrNoopPointerCastable(SrcTy: SrcElemTy, DestTy: DstElemTy, DL)) {
4823 return Builder.CreateBitOrPointerCast(V, DestTy: DstVTy);
4824 }
4825 // V cannot be directly casted to desired vector type.
4826 // May happen when V is a floating point vector but DstVTy is a vector of
4827 // pointers or vice-versa. Handle this using a two-step bitcast using an
4828 // intermediate Integer type for the bitcast i.e. Ptr <-> Int <-> Float.
4829 assert((DstElemTy->isPointerTy() != SrcElemTy->isPointerTy()) &&
4830 "Only one type should be a pointer type");
4831 assert((DstElemTy->isFloatingPointTy() != SrcElemTy->isFloatingPointTy()) &&
4832 "Only one type should be a floating point type");
4833 Type *IntTy =
4834 IntegerType::getIntNTy(C&: V->getContext(), N: DL.getTypeSizeInBits(Ty: SrcElemTy));
4835 auto *VecIntTy = VectorType::get(ElementType: IntTy, EC: VF);
4836 Value *CastVal = Builder.CreateBitOrPointerCast(V, DestTy: VecIntTy);
4837 return Builder.CreateBitOrPointerCast(V: CastVal, DestTy: DstVTy);
4838}
4839
4840/// Return a vector containing interleaved elements from multiple
4841/// smaller input vectors.
4842static Value *interleaveVectors(IRBuilderBase &Builder, ArrayRef<Value *> Vals,
4843 const Twine &Name) {
4844 unsigned Factor = Vals.size();
4845 assert(Factor > 1 && "Tried to interleave invalid number of vectors");
4846
4847 VectorType *VecTy = cast<VectorType>(Val: Vals[0]->getType());
4848#ifndef NDEBUG
4849 for (Value *Val : Vals)
4850 assert(Val->getType() == VecTy && "Tried to interleave mismatched types");
4851#endif
4852
4853 // Scalable vectors cannot use arbitrary shufflevectors (only splats), so
4854 // must use intrinsics to interleave.
4855 if (VecTy->isScalableTy()) {
4856 assert(Factor <= 8 && "Unsupported interleave factor for scalable vectors");
4857 return Builder.CreateVectorInterleave(Ops: Vals, Name);
4858 }
4859
4860 // Fixed length. Start by concatenating all vectors into a wide vector.
4861 Value *WideVec = concatenateVectors(Builder, Vecs: Vals);
4862
4863 // Interleave the elements into the wide vector.
4864 const unsigned NumElts = VecTy->getElementCount().getFixedValue();
4865 return Builder.CreateShuffleVector(
4866 V: WideVec, Mask: createInterleaveMask(VF: NumElts, NumVecs: Factor), Name);
4867}
4868
4869// Try to vectorize the interleave group that \p Instr belongs to.
4870//
4871// E.g. Translate following interleaved load group (factor = 3):
4872// for (i = 0; i < N; i+=3) {
4873// R = Pic[i]; // Member of index 0
4874// G = Pic[i+1]; // Member of index 1
4875// B = Pic[i+2]; // Member of index 2
4876// ... // do something to R, G, B
4877// }
4878// To:
4879// %wide.vec = load <12 x i32> ; Read 4 tuples of R,G,B
4880// %R.vec = shuffle %wide.vec, poison, <0, 3, 6, 9> ; R elements
4881// %G.vec = shuffle %wide.vec, poison, <1, 4, 7, 10> ; G elements
4882// %B.vec = shuffle %wide.vec, poison, <2, 5, 8, 11> ; B elements
4883//
4884// Or translate following interleaved store group (factor = 3):
4885// for (i = 0; i < N; i+=3) {
4886// ... do something to R, G, B
4887// Pic[i] = R; // Member of index 0
4888// Pic[i+1] = G; // Member of index 1
4889// Pic[i+2] = B; // Member of index 2
4890// }
4891// To:
4892// %R_G.vec = shuffle %R.vec, %G.vec, <0, 1, 2, ..., 7>
4893// %B_U.vec = shuffle %B.vec, poison, <0, 1, 2, 3, u, u, u, u>
4894// %interleaved.vec = shuffle %R_G.vec, %B_U.vec,
4895// <0, 4, 8, 1, 5, 9, 2, 6, 10, 3, 7, 11> ; Interleave R,G,B elements
4896// store <12 x i32> %interleaved.vec ; Write 4 tuples of R,G,B
4897void VPInterleaveRecipe::execute(VPTransformState &State) {
4898 assert((!needsMaskForGaps() || !State.VF.isScalable()) &&
4899 "Masking gaps for scalable vectors is not yet supported.");
4900 const InterleaveGroup<Instruction> *Group = getInterleaveGroup();
4901 Instruction *Instr = Group->getInsertPos();
4902
4903 // Prepare for the vector type of the interleaved load/store.
4904 Type *ScalarTy = getLoadStoreType(I: Instr);
4905 unsigned InterleaveFactor = Group->getFactor();
4906 auto *VecTy = VectorType::get(ElementType: ScalarTy, EC: State.VF * InterleaveFactor);
4907
4908 VPValue *BlockInMask = getMask();
4909 VPValue *Addr = getAddr();
4910 Value *ResAddr = State.get(Def: Addr, Lane: VPLane(0));
4911
4912 auto CreateGroupMask = [&BlockInMask, &State,
4913 &InterleaveFactor](Value *MaskForGaps) -> Value * {
4914 if (State.VF.isScalable()) {
4915 assert(!MaskForGaps && "Interleaved groups with gaps are not supported.");
4916 assert(InterleaveFactor <= 8 &&
4917 "Unsupported deinterleave factor for scalable vectors");
4918 auto *ResBlockInMask = State.get(Def: BlockInMask);
4919 SmallVector<Value *> Ops(InterleaveFactor, ResBlockInMask);
4920 return interleaveVectors(Builder&: State.Builder, Vals: Ops, Name: "interleaved.mask");
4921 }
4922
4923 if (!BlockInMask)
4924 return MaskForGaps;
4925
4926 Value *ResBlockInMask = State.get(Def: BlockInMask);
4927 Value *ShuffledMask = State.Builder.CreateShuffleVector(
4928 V: ResBlockInMask,
4929 Mask: createReplicatedMask(ReplicationFactor: InterleaveFactor, VF: State.VF.getFixedValue()),
4930 Name: "interleaved.mask");
4931 return MaskForGaps ? State.Builder.CreateBinOp(Opc: Instruction::And,
4932 LHS: ShuffledMask, RHS: MaskForGaps)
4933 : ShuffledMask;
4934 };
4935
4936 const DataLayout &DL = Instr->getDataLayout();
4937 // Vectorize the interleaved load group.
4938 if (isa<LoadInst>(Val: Instr)) {
4939 Value *MaskForGaps = nullptr;
4940 if (needsMaskForGaps()) {
4941 MaskForGaps =
4942 createBitMaskForGaps(Builder&: State.Builder, VF: State.VF.getFixedValue(), Group: *Group);
4943 assert(MaskForGaps && "Mask for Gaps is required but it is null");
4944 }
4945
4946 Instruction *NewLoad;
4947 if (BlockInMask || MaskForGaps) {
4948 Value *GroupMask = CreateGroupMask(MaskForGaps);
4949 Value *PoisonVec = PoisonValue::get(T: VecTy);
4950 NewLoad = State.Builder.CreateMaskedLoad(Ty: VecTy, Ptr: ResAddr,
4951 Alignment: Group->getAlign(), Mask: GroupMask,
4952 PassThru: PoisonVec, Name: "wide.masked.vec");
4953 } else
4954 NewLoad = State.Builder.CreateAlignedLoad(Ty: VecTy, Ptr: ResAddr,
4955 Align: Group->getAlign(), Name: "wide.vec");
4956 applyMetadata(I&: *NewLoad);
4957 // TODO: Also manage existing metadata using VPIRMetadata.
4958 Group->addMetadata(NewInst: NewLoad);
4959
4960 ArrayRef<VPRecipeValue *> VPDefs = definedValues();
4961 if (VecTy->isScalableTy()) {
4962 // Scalable vectors cannot use arbitrary shufflevectors (only splats),
4963 // so must use intrinsics to deinterleave.
4964 assert(InterleaveFactor <= 8 &&
4965 "Unsupported deinterleave factor for scalable vectors");
4966 NewLoad = State.Builder.CreateIntrinsicWithoutFolding(
4967 ID: Intrinsic::getDeinterleaveIntrinsicID(Factor: InterleaveFactor),
4968 OverloadTypes: NewLoad->getType(), Args: NewLoad,
4969 /*FMFSource=*/nullptr, Name: "strided.vec");
4970 }
4971
4972 auto CreateStridedVector = [&InterleaveFactor, &State,
4973 &NewLoad](unsigned Index) -> Value * {
4974 assert(Index < InterleaveFactor && "Illegal group index");
4975 if (State.VF.isScalable())
4976 return State.Builder.CreateExtractValue(Agg: NewLoad, Idxs: Index);
4977
4978 // For fixed length VF, use shuffle to extract the sub-vectors from the
4979 // wide load.
4980 auto StrideMask =
4981 createStrideMask(Start: Index, Stride: InterleaveFactor, VF: State.VF.getFixedValue());
4982 return State.Builder.CreateShuffleVector(V: NewLoad, Mask: StrideMask,
4983 Name: "strided.vec");
4984 };
4985
4986 for (unsigned I = 0, J = 0; I < InterleaveFactor; ++I) {
4987 Instruction *Member = Group->getMember(Index: I);
4988
4989 // Skip the gaps in the group.
4990 if (!Member)
4991 continue;
4992
4993 Value *StridedVec = CreateStridedVector(I);
4994
4995 // If this member has different type, cast the result type.
4996 if (Member->getType() != ScalarTy) {
4997 VectorType *OtherVTy = VectorType::get(ElementType: Member->getType(), EC: State.VF);
4998 StridedVec =
4999 createBitOrPointerCast(Builder&: State.Builder, V: StridedVec, DstVTy: OtherVTy, DL);
5000 }
5001
5002 if (Group->isReverse())
5003 StridedVec = State.Builder.CreateVectorReverse(V: StridedVec, Name: "reverse");
5004
5005 State.set(Def: VPDefs[J], V: StridedVec);
5006 ++J;
5007 }
5008 return;
5009 }
5010
5011 // The sub vector type for current instruction.
5012 auto *SubVT = VectorType::get(ElementType: ScalarTy, EC: State.VF);
5013
5014 // Vectorize the interleaved store group.
5015 Value *MaskForGaps =
5016 createBitMaskForGaps(Builder&: State.Builder, VF: State.VF.getKnownMinValue(), Group: *Group);
5017 assert(((MaskForGaps != nullptr) == needsMaskForGaps()) &&
5018 "Mismatch between NeedsMaskForGaps and MaskForGaps");
5019 ArrayRef<VPValue *> StoredValues = getStoredValues();
5020 // Collect the stored vector from each member.
5021 SmallVector<Value *, 4> StoredVecs;
5022 unsigned StoredIdx = 0;
5023 for (unsigned i = 0; i < InterleaveFactor; i++) {
5024 assert((Group->getMember(i) || MaskForGaps) &&
5025 "Fail to get a member from an interleaved store group");
5026 Instruction *Member = Group->getMember(Index: i);
5027
5028 // Skip the gaps in the group.
5029 if (!Member) {
5030 Value *Undef = PoisonValue::get(T: SubVT);
5031 StoredVecs.push_back(Elt: Undef);
5032 continue;
5033 }
5034
5035 Value *StoredVec = State.get(Def: StoredValues[StoredIdx]);
5036 ++StoredIdx;
5037
5038 if (Group->isReverse())
5039 StoredVec = State.Builder.CreateVectorReverse(V: StoredVec, Name: "reverse");
5040
5041 // If this member has different type, cast it to a unified type.
5042
5043 if (StoredVec->getType() != SubVT)
5044 StoredVec = createBitOrPointerCast(Builder&: State.Builder, V: StoredVec, DstVTy: SubVT, DL);
5045
5046 StoredVecs.push_back(Elt: StoredVec);
5047 }
5048
5049 // Interleave all the smaller vectors into one wider vector.
5050 Value *IVec = interleaveVectors(Builder&: State.Builder, Vals: StoredVecs, Name: "interleaved.vec");
5051 Instruction *NewStoreInstr;
5052 if (BlockInMask || MaskForGaps) {
5053 Value *GroupMask = CreateGroupMask(MaskForGaps);
5054 NewStoreInstr = State.Builder.CreateMaskedStore(
5055 Val: IVec, Ptr: ResAddr, Alignment: Group->getAlign(), Mask: GroupMask);
5056 } else
5057 NewStoreInstr =
5058 State.Builder.CreateAlignedStore(Val: IVec, Ptr: ResAddr, Align: Group->getAlign());
5059
5060 applyMetadata(I&: *NewStoreInstr);
5061 // TODO: Also manage existing metadata using VPIRMetadata.
5062 Group->addMetadata(NewInst: NewStoreInstr);
5063}
5064
5065#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
5066void VPInterleaveRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
5067 VPSlotTracker &SlotTracker) const {
5068 const InterleaveGroup<Instruction> *IG = getInterleaveGroup();
5069 O << Indent << "INTERLEAVE-GROUP with factor " << IG->getFactor() << ", ";
5070 getAddr()->printAsOperand(O, SlotTracker);
5071 VPValue *Mask = getMask();
5072 if (Mask) {
5073 O << ", ";
5074 Mask->printAsOperand(O, SlotTracker);
5075 }
5076
5077 unsigned OpIdx = 0;
5078 for (unsigned i = 0; i < IG->getFactor(); ++i) {
5079 if (!IG->getMember(i))
5080 continue;
5081 if (getNumStoreOperands() > 0) {
5082 O << "\n" << Indent << " store ";
5083 getOperand(1 + OpIdx)->printAsOperand(O, SlotTracker);
5084 O << " to index " << i;
5085 } else {
5086 O << "\n" << Indent << " ";
5087 getVPValue(OpIdx)->printAsOperand(O, SlotTracker);
5088 O << " = load from index " << i;
5089 }
5090 ++OpIdx;
5091 }
5092}
5093#endif
5094
5095void VPInterleaveEVLRecipe::execute(VPTransformState &State) {
5096 assert(State.VF.isScalable() &&
5097 "Only support scalable VF for EVL tail-folding.");
5098 assert(!needsMaskForGaps() &&
5099 "Masking gaps for scalable vectors is not yet supported.");
5100 const InterleaveGroup<Instruction> *Group = getInterleaveGroup();
5101 Instruction *Instr = Group->getInsertPos();
5102
5103 // Prepare for the vector type of the interleaved load/store.
5104 Type *ScalarTy = getLoadStoreType(I: Instr);
5105 unsigned InterleaveFactor = Group->getFactor();
5106 assert(InterleaveFactor <= 8 &&
5107 "Unsupported deinterleave/interleave factor for scalable vectors");
5108 ElementCount WideVF = State.VF * InterleaveFactor;
5109 auto *VecTy = VectorType::get(ElementType: ScalarTy, EC: WideVF);
5110
5111 VPValue *Addr = getAddr();
5112 Value *ResAddr = State.get(Def: Addr, Lane: VPLane(0));
5113 Value *EVL = State.get(Def: getEVL(), Lane: VPLane(0));
5114 Value *InterleaveEVL = State.Builder.CreateMul(
5115 LHS: EVL, RHS: ConstantInt::get(Ty: EVL->getType(), V: InterleaveFactor), Name: "interleave.evl",
5116 /* NUW= */ HasNUW: true, /* NSW= */ HasNSW: true);
5117 LLVMContext &Ctx = State.Builder.getContext();
5118
5119 Value *GroupMask = nullptr;
5120 if (VPValue *BlockInMask = getMask()) {
5121 SmallVector<Value *> Ops(InterleaveFactor, State.get(Def: BlockInMask));
5122 GroupMask = interleaveVectors(Builder&: State.Builder, Vals: Ops, Name: "interleaved.mask");
5123 } else {
5124 GroupMask =
5125 State.Builder.CreateVectorSplat(EC: WideVF, V: State.Builder.getTrue());
5126 }
5127
5128 // Vectorize the interleaved load group.
5129 if (isa<LoadInst>(Val: Instr)) {
5130 CallInst *NewLoad = State.Builder.CreateIntrinsicWithoutFolding(
5131 RetTy: VecTy, ID: Intrinsic::vp_load, Args: {ResAddr, GroupMask, InterleaveEVL}, FMFSource: nullptr,
5132 Name: "wide.vp.load");
5133 NewLoad->addParamAttr(ArgNo: 0,
5134 Attr: Attribute::getWithAlignment(Context&: Ctx, Alignment: Group->getAlign()));
5135
5136 applyMetadata(I&: *NewLoad);
5137 // TODO: Also manage existing metadata using VPIRMetadata.
5138 Group->addMetadata(NewInst: NewLoad);
5139
5140 // Scalable vectors cannot use arbitrary shufflevectors (only splats),
5141 // so must use intrinsics to deinterleave.
5142 NewLoad = State.Builder.CreateIntrinsicWithoutFolding(
5143 ID: Intrinsic::getDeinterleaveIntrinsicID(Factor: InterleaveFactor),
5144 OverloadTypes: NewLoad->getType(), Args: NewLoad,
5145 /*FMFSource=*/nullptr, Name: "strided.vec");
5146
5147 const DataLayout &DL = Instr->getDataLayout();
5148 for (unsigned I = 0, J = 0; I < InterleaveFactor; ++I) {
5149 Instruction *Member = Group->getMember(Index: I);
5150 // Skip the gaps in the group.
5151 if (!Member)
5152 continue;
5153
5154 Value *StridedVec = State.Builder.CreateExtractValue(Agg: NewLoad, Idxs: I);
5155 // If this member has different type, cast the result type.
5156 if (Member->getType() != ScalarTy) {
5157 VectorType *OtherVTy = VectorType::get(ElementType: Member->getType(), EC: State.VF);
5158 StridedVec =
5159 createBitOrPointerCast(Builder&: State.Builder, V: StridedVec, DstVTy: OtherVTy, DL);
5160 }
5161
5162 State.set(Def: getVPValue(I: J), V: StridedVec);
5163 ++J;
5164 }
5165 return;
5166 } // End for interleaved load.
5167
5168 // The sub vector type for current instruction.
5169 auto *SubVT = VectorType::get(ElementType: ScalarTy, EC: State.VF);
5170 // Vectorize the interleaved store group.
5171 ArrayRef<VPValue *> StoredValues = getStoredValues();
5172 // Collect the stored vector from each member.
5173 SmallVector<Value *, 4> StoredVecs;
5174 const DataLayout &DL = Instr->getDataLayout();
5175 for (unsigned I = 0, StoredIdx = 0; I < InterleaveFactor; I++) {
5176 Instruction *Member = Group->getMember(Index: I);
5177 // Skip the gaps in the group.
5178 if (!Member) {
5179 StoredVecs.push_back(Elt: PoisonValue::get(T: SubVT));
5180 continue;
5181 }
5182
5183 Value *StoredVec = State.get(Def: StoredValues[StoredIdx]);
5184 // If this member has different type, cast it to a unified type.
5185 if (StoredVec->getType() != SubVT)
5186 StoredVec = createBitOrPointerCast(Builder&: State.Builder, V: StoredVec, DstVTy: SubVT, DL);
5187
5188 StoredVecs.push_back(Elt: StoredVec);
5189 ++StoredIdx;
5190 }
5191
5192 // Interleave all the smaller vectors into one wider vector.
5193 Value *IVec = interleaveVectors(Builder&: State.Builder, Vals: StoredVecs, Name: "interleaved.vec");
5194 CallInst *NewStore = State.Builder.CreateIntrinsicWithoutFolding(
5195 RetTy: Type::getVoidTy(C&: Ctx), ID: Intrinsic::vp_store,
5196 Args: {IVec, ResAddr, GroupMask, InterleaveEVL});
5197
5198 NewStore->addParamAttr(ArgNo: 1,
5199 Attr: Attribute::getWithAlignment(Context&: Ctx, Alignment: Group->getAlign()));
5200
5201 applyMetadata(I&: *NewStore);
5202 // TODO: Also manage existing metadata using VPIRMetadata.
5203 Group->addMetadata(NewInst: NewStore);
5204}
5205
5206#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
5207void VPInterleaveEVLRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
5208 VPSlotTracker &SlotTracker) const {
5209 const InterleaveGroup<Instruction> *IG = getInterleaveGroup();
5210 O << Indent << "INTERLEAVE-GROUP with factor " << IG->getFactor() << ", ";
5211 getAddr()->printAsOperand(O, SlotTracker);
5212 O << ", ";
5213 getEVL()->printAsOperand(O, SlotTracker);
5214 if (VPValue *Mask = getMask()) {
5215 O << ", ";
5216 Mask->printAsOperand(O, SlotTracker);
5217 }
5218
5219 unsigned OpIdx = 0;
5220 for (unsigned i = 0; i < IG->getFactor(); ++i) {
5221 if (!IG->getMember(i))
5222 continue;
5223 if (getNumStoreOperands() > 0) {
5224 O << "\n" << Indent << " vp.store ";
5225 getOperand(2 + OpIdx)->printAsOperand(O, SlotTracker);
5226 O << " to index " << i;
5227 } else {
5228 O << "\n" << Indent << " ";
5229 getVPValue(OpIdx)->printAsOperand(O, SlotTracker);
5230 O << " = vp.load from index " << i;
5231 }
5232 ++OpIdx;
5233 }
5234}
5235#endif
5236
5237InstructionCost VPInterleaveBase::computeCost(ElementCount VF,
5238 VPCostContext &Ctx) const {
5239 Instruction *InsertPos = getInsertPos();
5240 // Find the VPValue index of the interleave group. We need to skip gaps.
5241 unsigned InsertPosIdx = 0;
5242 for (unsigned Idx = 0; IG->getFactor(); ++Idx)
5243 if (auto *Member = IG->getMember(Index: Idx)) {
5244 if (Member == InsertPos)
5245 break;
5246 InsertPosIdx++;
5247 }
5248 const VPValue *ValV = getNumDefinedValues() > 0
5249 ? getVPValue(I: InsertPosIdx)
5250 : getStoredValues()[InsertPosIdx];
5251 Type *ValTy = ValV->getScalarType();
5252 auto *VectorTy = cast<VectorType>(Val: toVectorTy(Scalar: ValTy, EC: VF));
5253 unsigned AS =
5254 cast<PointerType>(Val: getAddr()->getScalarType())->getAddressSpace();
5255
5256 unsigned InterleaveFactor = IG->getFactor();
5257 auto *WideVecTy = VectorType::get(ElementType: ValTy, EC: VF * InterleaveFactor);
5258
5259 // Holds the indices of existing members in the interleaved group.
5260 SmallVector<unsigned, 4> Indices;
5261 for (unsigned IF = 0; IF < InterleaveFactor; IF++)
5262 if (IG->getMember(Index: IF))
5263 Indices.push_back(Elt: IF);
5264
5265 // Calculate the cost of the whole interleaved group.
5266 InstructionCost Cost = Ctx.TTI.getInterleavedMemoryOpCost(
5267 Opcode: InsertPos->getOpcode(), VecTy: WideVecTy, Factor: IG->getFactor(), Indices,
5268 Alignment: IG->getAlign(), AddressSpace: AS, CostKind: Ctx.CostKind, UseMaskForCond: getMask(), UseMaskForGaps: NeedsMaskForGaps);
5269
5270 if (!IG->isReverse())
5271 return Cost;
5272
5273 return Cost + IG->getNumMembers() *
5274 Ctx.TTI.getShuffleCost(Kind: TargetTransformInfo::SK_Reverse,
5275 DstTy: VectorTy, SrcTy: VectorTy, CostKind: Ctx.CostKind, Mask: {},
5276 Index: 0);
5277}
5278
5279InstructionCost
5280VPWidenPointerInductionRecipe::computeCost(ElementCount VF,
5281 VPCostContext &Ctx) const {
5282 // The recipe creates a scalar phi, a GEP to increment the induction and
5283 // vector add to compute the vector of pointers.
5284 // TODO: Charge costs for induction increment and vector add as well.
5285 return Ctx.TTI.getCFInstrCost(Opcode: Instruction::PHI, CostKind: Ctx.CostKind);
5286}
5287
5288bool VPWidenPointerInductionRecipe::onlyScalarsGenerated(bool IsScalable) {
5289 return vputils::onlyScalarValuesUsed(Def: this) &&
5290 (!IsScalable || vputils::onlyFirstLaneUsed(Def: this));
5291}
5292
5293#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
5294void VPWidenPointerInductionRecipe::printRecipe(
5295 raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const {
5296 assert((getNumOperands() == 3 || getNumOperands() == 5) &&
5297 "unexpected number of operands");
5298 O << Indent << "EMIT ";
5299 printAsOperand(O, SlotTracker);
5300 O << " = WIDEN-POINTER-INDUCTION ";
5301 getStartValue()->printAsOperand(O, SlotTracker);
5302 O << ", ";
5303 getStepValue()->printAsOperand(O, SlotTracker);
5304 O << ", ";
5305 getOperand(2)->printAsOperand(O, SlotTracker);
5306 if (getNumOperands() == 5) {
5307 O << ", ";
5308 getOperand(3)->printAsOperand(O, SlotTracker);
5309 O << ", ";
5310 getOperand(4)->printAsOperand(O, SlotTracker);
5311 }
5312}
5313
5314void VPExpandSCEVRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
5315 VPSlotTracker &SlotTracker) const {
5316 O << Indent << "EMIT ";
5317 printAsOperand(O, SlotTracker);
5318 O << " = EXPAND SCEV " << *Expr;
5319 if (ExpandInIR)
5320 O << " (in IR)";
5321}
5322#endif
5323
5324#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
5325void VPWidenCanonicalIVRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
5326 VPSlotTracker &SlotTracker) const {
5327 O << Indent << "EMIT ";
5328 printAsOperand(O, SlotTracker);
5329 O << " = WIDEN-CANONICAL-INDUCTION";
5330 printFlags(O);
5331 printOperands(O, SlotTracker);
5332}
5333#endif
5334
5335void VPFirstOrderRecurrencePHIRecipe::execute(VPTransformState &State) {
5336 auto &Builder = State.Builder;
5337 // Create a vector from the initial value.
5338 auto *VectorInit = getStartValue()->getLiveInIRValue();
5339
5340 Type *VecTy = State.VF.isScalar()
5341 ? VectorInit->getType()
5342 : VectorType::get(ElementType: VectorInit->getType(), EC: State.VF);
5343
5344 BasicBlock *VectorPH =
5345 State.CFG.VPBB2IRBB.at(Val: getParent()->getCFGPredecessor(Idx: 0));
5346 if (State.VF.isVector()) {
5347 auto *IdxTy = Builder.getInt32Ty();
5348 auto *One = ConstantInt::get(Ty: IdxTy, V: 1);
5349 IRBuilder<>::InsertPointGuard Guard(Builder);
5350 Builder.SetInsertPoint(VectorPH->getTerminator());
5351 auto *RuntimeVF = getRuntimeVF(B&: Builder, Ty: IdxTy, VF: State.VF);
5352 auto *LastIdx = Builder.CreateSub(LHS: RuntimeVF, RHS: One);
5353 VectorInit = Builder.CreateInsertElement(
5354 Vec: PoisonValue::get(T: VecTy), NewElt: VectorInit, Idx: LastIdx, Name: "vector.recur.init");
5355 }
5356
5357 // Create a phi node for the new recurrence.
5358 PHINode *Phi = PHINode::Create(Ty: VecTy, NumReservedValues: 2, NameStr: "vector.recur");
5359 Phi->insertBefore(InsertPos: State.CFG.PrevBB->getFirstInsertionPt());
5360 Phi->addIncoming(V: VectorInit, BB: VectorPH);
5361 State.set(Def: this, V: Phi);
5362}
5363
5364InstructionCost
5365VPFirstOrderRecurrencePHIRecipe::computeCost(ElementCount VF,
5366 VPCostContext &Ctx) const {
5367 if (VF.isScalar())
5368 return Ctx.TTI.getCFInstrCost(Opcode: Instruction::PHI, CostKind: Ctx.CostKind);
5369
5370 return 0;
5371}
5372
5373#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
5374void VPFirstOrderRecurrencePHIRecipe::printRecipe(
5375 raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const {
5376 O << Indent << "FIRST-ORDER-RECURRENCE-PHI ";
5377 printAsOperand(O, SlotTracker);
5378 O << " = phi ";
5379 printOperands(O, SlotTracker);
5380}
5381#endif
5382
5383void VPReductionPHIRecipe::execute(VPTransformState &State) {
5384 // Reductions do not have to start at zero. They can start with
5385 // any loop invariant values.
5386 VPValue *StartVPV = getStartValue();
5387
5388 // In order to support recurrences we need to be able to vectorize Phi nodes.
5389 // Phi nodes have cycles, so we need to vectorize them in two stages. This is
5390 // stage #1: We create a new vector PHI node with no incoming edges. We'll use
5391 // this value when we vectorize all of the instructions that use the PHI.
5392 BasicBlock *VectorPH =
5393 State.CFG.VPBB2IRBB.at(Val: getParent()->getCFGPredecessor(Idx: 0));
5394 bool ScalarPHI = State.VF.isScalar() || isInLoop();
5395 Value *StartV = State.get(Def: StartVPV, NeedsSingleScalar: ScalarPHI);
5396 Type *VecTy = StartV->getType();
5397
5398 BasicBlock *HeaderBB = State.CFG.PrevBB;
5399 assert(State.CurrentParentLoop->getHeader() == HeaderBB &&
5400 "recipe must be in the vector loop header");
5401 auto *Phi = PHINode::Create(Ty: VecTy, NumReservedValues: 2, NameStr: "vec.phi");
5402 Phi->insertBefore(InsertPos: HeaderBB->getFirstInsertionPt());
5403 State.set(Def: this, V: Phi, IsScalar: isInLoop());
5404
5405 Phi->addIncoming(V: StartV, BB: VectorPH);
5406}
5407
5408#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
5409void VPReductionPHIRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
5410 VPSlotTracker &SlotTracker) const {
5411 O << Indent << "WIDEN-REDUCTION-PHI ";
5412
5413 printAsOperand(O, SlotTracker);
5414 O << " = phi (";
5415 printRecurrenceKind(O, Kind);
5416 O << ")";
5417 printFlags(O);
5418 printOperands(O, SlotTracker);
5419 if (getVFScaleFactor() > 1)
5420 O << " (VF scaled by 1/" << getVFScaleFactor() << ")";
5421}
5422#endif
5423
5424bool VPBlendRecipe::usesFirstLaneOnly(const VPValue *Op) const {
5425 assert(is_contained(operands(), Op) && "Op must be an operand of the recipe");
5426 assert(vputils::propagatesFirstLaneUse(this, Op) &&
5427 "Blend should propagate first lane use");
5428 return vputils::onlyFirstLaneUsed(Def: this);
5429}
5430
5431InstructionCost
5432VPConditionalInductionPHIRecipe::computeCost(ElementCount VF,
5433 VPCostContext &Ctx) const {
5434 return Ctx.TTI.getCFInstrCost(Opcode: Instruction::PHI, CostKind: Ctx.CostKind);
5435}
5436
5437#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
5438void VPConditionalInductionPHIRecipe::printRecipe(
5439 raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const {
5440 O << Indent << "CONDITIONAL-INDUCTION-PHI ";
5441
5442 printAsOperand(O, SlotTracker);
5443 O << " = phi ";
5444 printOperands(O, SlotTracker);
5445}
5446#endif
5447
5448void VPWidenPHIRecipe::execute(VPTransformState &State) {
5449 executePhiRecipe(R: this, Phi&: *this, State, /*IsScalar=*/false, Name);
5450}
5451
5452InstructionCost VPWidenPHIRecipe::computeCost(ElementCount VF,
5453 VPCostContext &Ctx) const {
5454 return Ctx.TTI.getCFInstrCost(Opcode: Instruction::PHI, CostKind: Ctx.CostKind);
5455}
5456
5457#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
5458void VPWidenPHIRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
5459 VPSlotTracker &SlotTracker) const {
5460 O << Indent << "WIDEN-PHI ";
5461
5462 printAsOperand(O, SlotTracker);
5463 O << " = phi ";
5464 printPhiOperands(O, SlotTracker);
5465}
5466#endif
5467
5468void VPActiveLaneMaskPHIRecipe::execute(VPTransformState &State) {
5469 BasicBlock *VectorPH =
5470 State.CFG.VPBB2IRBB.at(Val: getParent()->getCFGPredecessor(Idx: 0));
5471 Value *StartMask = State.get(Def: getOperand(N: 0));
5472 PHINode *Phi =
5473 State.Builder.CreatePHI(Ty: StartMask->getType(), NumReservedValues: 2, Name: "active.lane.mask");
5474 Phi->addIncoming(V: StartMask, BB: VectorPH);
5475 State.set(Def: this, V: Phi);
5476}
5477
5478#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
5479void VPActiveLaneMaskPHIRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
5480 VPSlotTracker &SlotTracker) const {
5481 O << Indent << "ACTIVE-LANE-MASK-PHI ";
5482
5483 printAsOperand(O, SlotTracker);
5484 O << " = phi ";
5485 printOperands(O, SlotTracker);
5486}
5487#endif
5488
5489#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
5490void VPCurrentIterationPHIRecipe::printRecipe(
5491 raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const {
5492 O << Indent << "CURRENT-ITERATION-PHI ";
5493
5494 printAsOperand(O, SlotTracker);
5495 O << " = phi ";
5496 printOperands(O, SlotTracker);
5497}
5498#endif
5499