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 "llvm/ADT/STLExtras.h"
20#include "llvm/ADT/SmallVector.h"
21#include "llvm/ADT/SmallVectorExtras.h"
22#include "llvm/ADT/Twine.h"
23#include "llvm/Analysis/AssumptionCache.h"
24#include "llvm/Analysis/IVDescriptors.h"
25#include "llvm/Analysis/LoopInfo.h"
26#include "llvm/Analysis/ScalarEvolutionExpressions.h"
27#include "llvm/IR/BasicBlock.h"
28#include "llvm/IR/IRBuilder.h"
29#include "llvm/IR/Instruction.h"
30#include "llvm/IR/Instructions.h"
31#include "llvm/IR/Intrinsics.h"
32#include "llvm/IR/Type.h"
33#include "llvm/IR/Value.h"
34#include "llvm/Support/Casting.h"
35#include "llvm/Support/CommandLine.h"
36#include "llvm/Support/Debug.h"
37#include "llvm/Support/raw_ostream.h"
38#include "llvm/Transforms/Utils/BasicBlockUtils.h"
39#include "llvm/Transforms/Utils/LoopUtils.h"
40#include <cassert>
41
42using namespace llvm;
43using namespace llvm::VPlanPatternMatch;
44
45using VectorParts = SmallVector<Value *, 2>;
46
47#define LV_NAME "loop-vectorize"
48#define DEBUG_TYPE LV_NAME
49
50#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
51// It is sometimes necessary to disable printing of metadata in tests in order
52// to avoid non-deterministic behaviour due to metadata introduced by VPlan
53// that wasn't present in the original scalar IR.
54static cl::opt<bool> VPlanPrintMetadata(
55 "vplan-print-metadata", cl::init(true), cl::Hidden,
56 cl::desc("Controls the printing of recipe metadata when debugging."));
57#endif
58
59bool VPRecipeBase::mayWriteToMemory() const {
60 switch (getVPRecipeID()) {
61 case VPExpressionSC:
62 return cast<VPExpressionRecipe>(Val: this)->mayReadOrWriteMemory();
63 case VPInstructionSC: {
64 auto *VPI = cast<VPInstruction>(Val: this);
65 // Loads read from memory but don't write to memory.
66 if (VPI->getOpcode() == Instruction::Load)
67 return false;
68 return VPI->opcodeMayReadOrWriteFromMemory();
69 }
70 case VPInterleaveEVLSC:
71 case VPInterleaveSC:
72 return cast<VPInterleaveBase>(Val: this)->getNumStoreOperands() > 0;
73 case VPWidenStoreEVLSC:
74 case VPWidenStoreSC:
75 return true;
76 case VPReplicateSC:
77 return cast<Instruction>(Val: getVPSingleValue()->getUnderlyingValue())
78 ->mayWriteToMemory();
79 case VPWidenCallSC:
80 return !cast<VPWidenCallRecipe>(Val: this)
81 ->getCalledScalarFunction()
82 ->onlyReadsMemory();
83 case VPWidenMemIntrinsicSC:
84 case VPWidenIntrinsicSC:
85 return cast<VPWidenIntrinsicRecipe>(Val: this)->mayWriteToMemory();
86 case VPActiveLaneMaskPHISC:
87 case VPCurrentIterationPHISC:
88 case VPBranchOnMaskSC:
89 case VPDerivedIVSC:
90 case VPFirstOrderRecurrencePHISC:
91 case VPReductionPHISC:
92 case VPScalarIVStepsSC:
93 case VPPredInstPHISC:
94 return false;
95 case VPBlendSC:
96 case VPReductionEVLSC:
97 case VPReductionSC:
98 case VPVectorPointerSC:
99 case VPWidenCanonicalIVSC:
100 case VPWidenCastSC:
101 case VPWidenGEPSC:
102 case VPWidenIntOrFpInductionSC:
103 case VPWidenLoadEVLSC:
104 case VPWidenLoadSC:
105 case VPWidenPHISC:
106 case VPWidenPointerInductionSC:
107 case VPWidenSC: {
108 const Instruction *I =
109 dyn_cast_or_null<Instruction>(Val: getVPSingleValue()->getUnderlyingValue());
110 (void)I;
111 assert((!I || !I->mayWriteToMemory()) &&
112 "underlying instruction may write to memory");
113 return false;
114 }
115 default:
116 return true;
117 }
118}
119
120bool VPRecipeBase::mayReadFromMemory() const {
121 switch (getVPRecipeID()) {
122 case VPExpressionSC:
123 return cast<VPExpressionRecipe>(Val: this)->mayReadOrWriteMemory();
124 case VPInstructionSC:
125 return cast<VPInstruction>(Val: this)->opcodeMayReadOrWriteFromMemory();
126 case VPWidenLoadEVLSC:
127 case VPWidenLoadSC:
128 return true;
129 case VPReplicateSC:
130 return cast<Instruction>(Val: getVPSingleValue()->getUnderlyingValue())
131 ->mayReadFromMemory();
132 case VPWidenCallSC:
133 return !cast<VPWidenCallRecipe>(Val: this)
134 ->getCalledScalarFunction()
135 ->onlyWritesMemory();
136 case VPWidenMemIntrinsicSC:
137 case VPWidenIntrinsicSC:
138 return cast<VPWidenIntrinsicRecipe>(Val: this)->mayReadFromMemory();
139 case VPBranchOnMaskSC:
140 case VPDerivedIVSC:
141 case VPCurrentIterationPHISC:
142 case VPFirstOrderRecurrencePHISC:
143 case VPReductionPHISC:
144 case VPPredInstPHISC:
145 case VPScalarIVStepsSC:
146 case VPWidenStoreEVLSC:
147 case VPWidenStoreSC:
148 return false;
149 case VPBlendSC:
150 case VPReductionEVLSC:
151 case VPReductionSC:
152 case VPVectorPointerSC:
153 case VPWidenCanonicalIVSC:
154 case VPWidenCastSC:
155 case VPWidenGEPSC:
156 case VPWidenIntOrFpInductionSC:
157 case VPWidenPHISC:
158 case VPWidenPointerInductionSC:
159 case VPWidenSC: {
160 const Instruction *I =
161 dyn_cast_or_null<Instruction>(Val: getVPSingleValue()->getUnderlyingValue());
162 (void)I;
163 assert((!I || !I->mayReadFromMemory()) &&
164 "underlying instruction may read from memory");
165 return false;
166 }
167 default:
168 // FIXME: Return false if the recipe represents an interleaved store.
169 return true;
170 }
171}
172
173bool VPRecipeBase::mayHaveSideEffects() const {
174 switch (getVPRecipeID()) {
175 case VPExpressionSC:
176 return cast<VPExpressionRecipe>(Val: this)->mayHaveSideEffects();
177 case VPActiveLaneMaskPHISC:
178 case VPDerivedIVSC:
179 case VPCurrentIterationPHISC:
180 case VPFirstOrderRecurrencePHISC:
181 case VPReductionPHISC:
182 case VPPredInstPHISC:
183 case VPVectorEndPointerSC:
184 return false;
185 case VPInstructionSC: {
186 auto *VPI = cast<VPInstruction>(Val: this);
187 return mayWriteToMemory() ||
188 VPI->getOpcode() == VPInstruction::BranchOnCount ||
189 VPI->getOpcode() == VPInstruction::BranchOnCond ||
190 VPI->getOpcode() == VPInstruction::BranchOnTwoConds;
191 }
192 case VPWidenCallSC: {
193 Function *Fn = cast<VPWidenCallRecipe>(Val: this)->getCalledScalarFunction();
194 return mayWriteToMemory() || !Fn->doesNotThrow() || !Fn->willReturn();
195 }
196 case VPWidenMemIntrinsicSC:
197 case VPWidenIntrinsicSC:
198 return cast<VPWidenIntrinsicRecipe>(Val: this)->mayHaveSideEffects();
199 case VPBlendSC:
200 case VPReductionEVLSC:
201 case VPReductionSC:
202 case VPScalarIVStepsSC:
203 case VPVectorPointerSC:
204 case VPWidenCanonicalIVSC:
205 case VPWidenCastSC:
206 case VPWidenGEPSC:
207 case VPWidenIntOrFpInductionSC:
208 case VPWidenPHISC:
209 case VPWidenPointerInductionSC:
210 case VPWidenSC: {
211 const Instruction *I =
212 dyn_cast_or_null<Instruction>(Val: getVPSingleValue()->getUnderlyingValue());
213 (void)I;
214 assert((!I || !I->mayHaveSideEffects()) &&
215 "underlying instruction has side-effects");
216 return false;
217 }
218 case VPInterleaveEVLSC:
219 case VPInterleaveSC:
220 return mayWriteToMemory();
221 case VPWidenLoadEVLSC:
222 case VPWidenLoadSC:
223 case VPWidenStoreEVLSC:
224 case VPWidenStoreSC:
225 assert(
226 cast<VPWidenMemoryRecipe>(this)->getIngredient().mayHaveSideEffects() ==
227 mayWriteToMemory() &&
228 "mayHaveSideffects result for ingredient differs from this "
229 "implementation");
230 return mayWriteToMemory();
231 case VPReplicateSC: {
232 auto *R = cast<VPReplicateRecipe>(Val: this);
233 return R->getUnderlyingInstr()->mayHaveSideEffects();
234 }
235 default:
236 return true;
237 }
238}
239
240bool VPRecipeBase::isSafeToSpeculativelyExecute() const {
241 switch (getVPRecipeID()) {
242 default:
243 return false;
244 case VPInstructionSC: {
245 unsigned Opcode = cast<VPInstruction>(Val: this)->getOpcode();
246 if (Instruction::isCast(Opcode))
247 return true;
248
249 switch (Opcode) {
250 default:
251 return false;
252 case Instruction::Add:
253 case Instruction::Sub:
254 case Instruction::Mul:
255 case Instruction::GetElementPtr:
256 return true;
257 }
258 }
259 }
260}
261
262void VPRecipeBase::insertBefore(VPRecipeBase *InsertPos) {
263 assert(!Parent && "Recipe already in some VPBasicBlock");
264 assert(InsertPos->getParent() &&
265 "Insertion position not in any VPBasicBlock");
266 InsertPos->getParent()->insert(Recipe: this, InsertPt: InsertPos->getIterator());
267}
268
269void VPRecipeBase::insertBefore(VPBasicBlock &BB,
270 iplist<VPRecipeBase>::iterator I) {
271 assert(!Parent && "Recipe already in some VPBasicBlock");
272 assert(I == BB.end() || I->getParent() == &BB);
273 BB.insert(Recipe: this, InsertPt: I);
274}
275
276void VPRecipeBase::insertAfter(VPRecipeBase *InsertPos) {
277 assert(!Parent && "Recipe already in some VPBasicBlock");
278 assert(InsertPos->getParent() &&
279 "Insertion position not in any VPBasicBlock");
280 InsertPos->getParent()->insert(Recipe: this, InsertPt: std::next(x: InsertPos->getIterator()));
281}
282
283void VPRecipeBase::removeFromParent() {
284 assert(getParent() && "Recipe not in any VPBasicBlock");
285 getParent()->getRecipeList().remove(IT: getIterator());
286 Parent = nullptr;
287}
288
289iplist<VPRecipeBase>::iterator VPRecipeBase::eraseFromParent() {
290 assert(getParent() && "Recipe not in any VPBasicBlock");
291 return getParent()->getRecipeList().erase(where: getIterator());
292}
293
294void VPRecipeBase::moveAfter(VPRecipeBase *InsertPos) {
295 removeFromParent();
296 insertAfter(InsertPos);
297}
298
299void VPRecipeBase::moveBefore(VPBasicBlock &BB,
300 iplist<VPRecipeBase>::iterator I) {
301 removeFromParent();
302 insertBefore(BB, I);
303}
304
305InstructionCost VPRecipeBase::cost(ElementCount VF, VPCostContext &Ctx) {
306 // Get the underlying instruction for the recipe, if there is one. It is used
307 // to
308 // * decide if cost computation should be skipped for this recipe,
309 // * apply forced target instruction cost.
310 Instruction *UI = nullptr;
311 if (auto *S = dyn_cast<VPSingleDefRecipe>(Val: this))
312 UI = dyn_cast_or_null<Instruction>(Val: S->getUnderlyingValue());
313 else if (auto *IG = dyn_cast<VPInterleaveBase>(Val: this))
314 UI = IG->getInsertPos();
315 else if (auto *WidenMem = dyn_cast<VPWidenMemoryRecipe>(Val: this))
316 UI = &WidenMem->getIngredient();
317
318 InstructionCost RecipeCost;
319 if (UI && Ctx.skipCostComputation(UI, IsVector: VF.isVector())) {
320 RecipeCost = 0;
321 } else {
322 RecipeCost = computeCost(VF, Ctx);
323 if (ForceTargetInstructionCost.getNumOccurrences() > 0 &&
324 RecipeCost.isValid()) {
325 if (UI)
326 RecipeCost = InstructionCost(ForceTargetInstructionCost);
327 else
328 RecipeCost = InstructionCost(0);
329 }
330 }
331
332 LLVM_DEBUG({
333 dbgs() << "Cost of " << RecipeCost << " for VF " << VF << ": ";
334 dump();
335 });
336 return RecipeCost;
337}
338
339InstructionCost VPRecipeBase::computeCost(ElementCount VF,
340 VPCostContext &Ctx) const {
341 llvm_unreachable("subclasses should implement computeCost");
342}
343
344bool VPRecipeBase::isPhi() const {
345 return (getVPRecipeID() >= VPFirstPHISC && getVPRecipeID() <= VPLastPHISC) ||
346 isa<VPPhi, VPIRPhi>(Val: this);
347}
348
349void VPIRFlags::intersectFlags(const VPIRFlags &Other) {
350 assert(OpType == Other.OpType && "OpType must match");
351 switch (OpType) {
352 case OperationType::OverflowingBinOp:
353 WrapFlags.HasNUW &= Other.WrapFlags.HasNUW;
354 WrapFlags.HasNSW &= Other.WrapFlags.HasNSW;
355 break;
356 case OperationType::Trunc:
357 TruncFlags.HasNUW &= Other.TruncFlags.HasNUW;
358 TruncFlags.HasNSW &= Other.TruncFlags.HasNSW;
359 break;
360 case OperationType::DisjointOp:
361 DisjointFlags.IsDisjoint &= Other.DisjointFlags.IsDisjoint;
362 break;
363 case OperationType::PossiblyExactOp:
364 ExactFlags.IsExact &= Other.ExactFlags.IsExact;
365 break;
366 case OperationType::GEPOp:
367 GEPFlagsStorage &= Other.GEPFlagsStorage;
368 break;
369 case OperationType::FPMathOp:
370 case OperationType::FCmp:
371 assert((OpType != OperationType::FCmp ||
372 FCmpFlags.CmpPredStorage == Other.FCmpFlags.CmpPredStorage) &&
373 "Cannot drop CmpPredicate");
374 getFMFsRef() = getFastMathFlagsOrNone() & Other.getFastMathFlagsOrNone();
375 break;
376 case OperationType::NonNegOp:
377 NonNegFlags.NonNeg &= Other.NonNegFlags.NonNeg;
378 break;
379 case OperationType::Cmp:
380 assert(CmpPredStorage == Other.CmpPredStorage &&
381 "Cannot drop CmpPredicate");
382 break;
383 case OperationType::ReductionOp:
384 assert(ReductionFlags.Kind == Other.ReductionFlags.Kind &&
385 "Cannot change RecurKind");
386 assert(ReductionFlags.IsOrdered == Other.ReductionFlags.IsOrdered &&
387 "Cannot change IsOrdered");
388 assert(ReductionFlags.IsInLoop == Other.ReductionFlags.IsInLoop &&
389 "Cannot change IsInLoop");
390 getFMFsRef() = getFastMathFlagsOrNone() & Other.getFastMathFlagsOrNone();
391 break;
392 case OperationType::Other:
393 break;
394 }
395}
396
397FastMathFlags VPIRFlags::getFastMathFlagsOrNone() const {
398 if (!hasFastMathFlags())
399 return {};
400 const FastMathFlagsTy &F = getFMFsRef();
401 FastMathFlags Res;
402 Res.setAllowReassoc(F.AllowReassoc);
403 Res.setNoNaNs(F.NoNaNs);
404 Res.setNoInfs(F.NoInfs);
405 Res.setNoSignedZeros(F.NoSignedZeros);
406 Res.setAllowReciprocal(F.AllowReciprocal);
407 Res.setAllowContract(F.AllowContract);
408 Res.setApproxFunc(F.ApproxFunc);
409 return Res;
410}
411
412#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
413void VPSingleDefRecipe::dump() const { VPRecipeBase::dump(); }
414
415void VPRecipeBase::print(raw_ostream &O, const Twine &Indent,
416 VPSlotTracker &SlotTracker) const {
417 printRecipe(O, Indent, SlotTracker);
418 if (auto DL = getDebugLoc()) {
419 O << ", !dbg ";
420 DL.print(O);
421 }
422
423 if (auto *Metadata = dyn_cast<VPIRMetadata>(this))
424 Metadata->print(O, SlotTracker);
425}
426#endif
427
428VPExpandSCEVRecipe::VPExpandSCEVRecipe(const SCEV *Expr)
429 : VPSingleDefRecipe(VPRecipeBase::VPExpandSCEVSC, {}, Expr->getType()),
430 Expr(Expr) {}
431
432/// For call VPInstruction operands, return the operand index of the called
433/// function. The function is either the last operand (for unmasked calls) or
434/// the second-to-last operand (for masked calls).
435static unsigned getCalledFnOperandIndex(ArrayRef<VPValue *> Operands) {
436 unsigned NumOps = Operands.size();
437 auto *LastOp = dyn_cast<VPIRValue>(Val: Operands[NumOps - 1]);
438 if (LastOp && isa<Function>(Val: LastOp->getValue()))
439 return NumOps - 1;
440 assert(isa<Function>(cast<VPIRValue>(Operands[NumOps - 2])->getValue()) &&
441 "expected function operand");
442 return NumOps - 2;
443}
444
445/// For call VPInstruction operands, return the called function.
446static Function *getCalledFunction(ArrayRef<VPValue *> Operands) {
447 unsigned Idx = getCalledFnOperandIndex(Operands);
448 return cast<Function>(Val: cast<VPIRValue>(Val: Operands[Idx])->getValue());
449}
450
451Type *llvm::computeScalarTypeForInstruction(unsigned Opcode,
452 ArrayRef<VPValue *> Operands) {
453 assert(!Operands.empty() &&
454 "zero-operand VPInstruction opcodes must pass explicit ResultTy");
455 // Assert operand \p Idx (if present and typed) has type \p ExpectedTy.
456 [[maybe_unused]] auto AssertOperandType = [&Operands](unsigned Idx,
457 Type *ExpectedTy) {
458 if (!ExpectedTy || Operands.size() <= Idx)
459 return;
460 [[maybe_unused]] Type *OpTy = Operands[Idx]->getScalarType();
461 assert((!OpTy || OpTy == ExpectedTy) &&
462 "different types inferred for different operands");
463 };
464
465 Type *Op0Ty = Operands[0]->getScalarType();
466 LLVMContext &Ctx = Op0Ty->getContext();
467 switch (Opcode) {
468 case VPInstruction::BranchOnCond:
469 assert(Op0Ty->isIntegerTy(1) && "expected bool condition");
470 return Type::getVoidTy(C&: Ctx);
471 case VPInstruction::BranchOnTwoConds:
472 assert(Op0Ty->isIntegerTy(1) && "expected bool condition");
473 AssertOperandType(1, IntegerType::get(C&: Ctx, NumBits: 1));
474 return Type::getVoidTy(C&: Ctx);
475 case VPInstruction::BranchOnCount:
476 assert(Op0Ty->isIntegerTy() && "expected integer operand");
477 AssertOperandType(1, Op0Ty);
478 return Type::getVoidTy(C&: Ctx);
479 case VPInstruction::CalculateTripCountMinusVF:
480 case VPInstruction::CanonicalIVIncrementForPart:
481 assert(Op0Ty->isIntegerTy() && "expected integer operand");
482 for (unsigned Idx = 1; Idx != Operands.size(); ++Idx)
483 AssertOperandType(Idx, Op0Ty);
484 return Op0Ty;
485 case Instruction::Switch:
486 for (unsigned Idx = 1; Idx != Operands.size(); ++Idx)
487 AssertOperandType(Idx, Op0Ty);
488 return Type::getVoidTy(C&: Ctx);
489 case Instruction::Store:
490 return Type::getVoidTy(C&: Ctx);
491 case Instruction::ICmp:
492 assert(Op0Ty->isIntOrPtrTy() && "expected integer or pointer operand");
493 AssertOperandType(1, Op0Ty);
494 return IntegerType::get(C&: Ctx, NumBits: 1);
495 case Instruction::FCmp:
496 assert(Op0Ty->isFloatingPointTy() && "expected floating-point operand");
497 AssertOperandType(1, Op0Ty);
498 return IntegerType::get(C&: Ctx, NumBits: 1);
499 case VPInstruction::ActiveLaneMask:
500 assert(Op0Ty->isIntegerTy() && "expected integer operand");
501 AssertOperandType(1, Op0Ty);
502 return IntegerType::get(C&: Ctx, NumBits: 1);
503 case VPInstruction::MaskedCond:
504 assert(Op0Ty->isIntegerTy(1) && "expected bool operand");
505 return IntegerType::get(C&: Ctx, NumBits: 1);
506 case VPInstruction::LogicalAnd:
507 case VPInstruction::LogicalOr:
508 assert(Op0Ty->isIntegerTy(1) && "expected bool operand");
509 AssertOperandType(1, Op0Ty);
510 return IntegerType::get(C&: Ctx, NumBits: 1);
511 case VPInstruction::AnyOf:
512 assert(Op0Ty->isIntegerTy(1) && "expected bool operand");
513 for (unsigned Idx = 1; Idx != Operands.size(); ++Idx)
514 AssertOperandType(Idx, Op0Ty);
515 return IntegerType::get(C&: Ctx, NumBits: 1);
516 case VPInstruction::ExplicitVectorLength:
517 assert(Op0Ty->isIntegerTy() && "expected integer operand");
518 return IntegerType::get(C&: Ctx, NumBits: 32);
519 case Instruction::Select: {
520 assert((!Op0Ty || Op0Ty->isIntegerTy(1)) &&
521 "select condition must be bool");
522 Type *Op1Ty = Operands[1]->getScalarType();
523 AssertOperandType(2, Op1Ty);
524 return Op1Ty;
525 }
526 case Instruction::InsertElement:
527 // The inserted scalar (operand 1) must match the vector element type;
528 // operand 2 must be an integer.
529 AssertOperandType(1, Op0Ty);
530 assert(Operands[2]->getScalarType()->isIntegerTy() &&
531 "expected integer operand");
532 return Op0Ty;
533 case VPInstruction::ReductionStartVector:
534 // The start value and the identity value (operands 0 and 1) fill the same
535 // vector and must match in type; operand 2 is the scaling factor.
536 AssertOperandType(1, Op0Ty);
537 return Op0Ty;
538 case VPInstruction::ExtractLane: {
539 assert(Operands.size() >= 2 && "ExtractLane requires a lane operand and "
540 "at least one source vector operand");
541 // Operand 0 is the lane index, used for integer arithmetic.
542 assert(Op0Ty->isIntegerTy() && "expected integer operand");
543 Type *Op1Ty = Operands[1]->getScalarType();
544 for (unsigned Idx = 2; Idx != Operands.size(); ++Idx)
545 AssertOperandType(Idx, Op1Ty);
546 return Op1Ty;
547 }
548 case VPInstruction::PtrAdd:
549 case VPInstruction::WidePtrAdd:
550 assert(Operands[0]->getScalarType()->isPointerTy() &&
551 "expected pointer operand");
552 assert(Operands[1]->getScalarType()->isIntegerTy() &&
553 "expected integer operand");
554 return Op0Ty;
555 case Instruction::ExtractValue: {
556 assert(Operands.size() == 2 && "expected single level extractvalue");
557 auto *StructTy = cast<StructType>(Val: Op0Ty);
558 return StructTy->getTypeAtIndex(
559 N: cast<VPConstantInt>(Val: Operands[1])->getZExtValue());
560 }
561 case VPInstruction::FirstActiveLane:
562 case VPInstruction::LastActiveLane:
563 case VPInstruction::NumActiveLanes:
564 case VPInstruction::IncomingAliasMask:
565 case Instruction::Load:
566 case Instruction::Alloca:
567 llvm_unreachable("type must be passed explicitly");
568 case Instruction::Call:
569 return getCalledFunction(Operands)->getReturnType();
570 default:
571 break;
572 }
573
574 // Opcodes that require all operands to share the same scalar type as the
575 // result.
576 bool AllOperandsSameType =
577 Instruction::isBinaryOp(Opcode) ||
578 is_contained(Set: {VPInstruction::FirstOrderRecurrenceSplice,
579 VPInstruction::BuildVector,
580 VPInstruction::BuildStructVector},
581 Element: Opcode);
582 if (AllOperandsSameType)
583 for (unsigned Idx = 1; Idx != Operands.size(); ++Idx)
584 AssertOperandType(Idx, Op0Ty);
585
586 return Op0Ty;
587}
588
589Type *VPReplicateRecipe::computeScalarType(const Instruction *I,
590 ArrayRef<VPValue *> Operands) {
591 unsigned Opcode = I->getOpcode();
592 if (Instruction::isCast(Opcode) ||
593 is_contained(Range: ArrayRef<unsigned>({Instruction::ExtractValue,
594 Instruction::Load, Instruction::Alloca}),
595 Element: Opcode))
596 return I->getType();
597 return computeScalarTypeForInstruction(Opcode, Operands);
598}
599
600VPInstruction::VPInstruction(unsigned Opcode, ArrayRef<VPValue *> Operands,
601 const VPIRFlags &Flags, const VPIRMetadata &MD,
602 DebugLoc DL, const Twine &Name, Type *ResultTy)
603 : VPRecipeWithIRFlags(
604 VPRecipeBase::VPInstructionSC, Operands,
605 ResultTy ? ResultTy
606 : computeScalarTypeForInstruction(Opcode, Operands),
607 Flags, DL),
608 VPIRMetadata(MD), Opcode(Opcode), Name(Name.str()) {
609 assert(flagsValidForOpcode(getOpcode()) &&
610 "Set flags not supported for the provided opcode");
611 assert(hasRequiredFlagsForOpcode(getOpcode()) &&
612 "Opcode requires specific flags to be set");
613 assert((getNumOperandsForOpcode() == -1u ||
614 getNumOperandsForOpcode() == getNumOperands() ||
615 (isMasked() && getNumOperandsForOpcode() + 1 == getNumOperands())) &&
616 "number of operands does not match opcode");
617}
618
619unsigned VPInstruction::getNumOperandsForOpcode() const {
620 if (Instruction::isUnaryOp(Opcode) || Instruction::isCast(Opcode))
621 return 1;
622
623 if (Instruction::isBinaryOp(Opcode))
624 return 2;
625
626 switch (Opcode) {
627 case VPInstruction::StepVector:
628 case VPInstruction::IncomingAliasMask:
629 return 0;
630 case Instruction::Alloca:
631 case Instruction::ExtractValue:
632 case Instruction::Freeze:
633 case Instruction::Load:
634 case VPInstruction::BranchOnCond:
635 case VPInstruction::Broadcast:
636 case VPInstruction::ExitingIVValue:
637 case VPInstruction::ExplicitVectorLength:
638 case VPInstruction::ExtractLastLane:
639 case VPInstruction::ExtractLastPart:
640 case VPInstruction::ExtractPenultimateElement:
641 case VPInstruction::MaskedCond:
642 case VPInstruction::Not:
643 case VPInstruction::Reverse:
644 case VPInstruction::Unpack:
645 case VPInstruction::NumActiveLanes:
646 return 1;
647 case Instruction::ICmp:
648 case Instruction::FCmp:
649 case Instruction::ExtractElement:
650 case Instruction::Store:
651 case VPInstruction::BranchOnCount:
652 case VPInstruction::BranchOnTwoConds:
653 case VPInstruction::FirstOrderRecurrenceSplice:
654 case VPInstruction::LogicalAnd:
655 case VPInstruction::LogicalOr:
656 case VPInstruction::PtrAdd:
657 case VPInstruction::WidePtrAdd:
658 case VPInstruction::WideIVStep:
659 case VPInstruction::CalculateTripCountMinusVF:
660 case VPInstruction::ResumeForEpilogue:
661 return 2;
662 case Instruction::InsertElement:
663 case Instruction::Select:
664 case VPInstruction::ActiveLaneMask:
665 case VPInstruction::ReductionStartVector:
666 return 3;
667 case Instruction::Call:
668 return getCalledFnOperandIndex(Operands: ArrayRef<VPValue *>(op_begin(), op_end())) +
669 1;
670 case Instruction::GetElementPtr:
671 case Instruction::PHI:
672 case Instruction::Switch:
673 case Instruction::AtomicRMW:
674 case Instruction::AtomicCmpXchg:
675 case Instruction::Fence:
676 case VPInstruction::AnyOf:
677 case VPInstruction::BuildStructVector:
678 case VPInstruction::BuildVector:
679 case VPInstruction::Intrinsic:
680 case VPInstruction::CanonicalIVIncrementForPart:
681 case VPInstruction::ComputeReductionResult:
682 case VPInstruction::FirstActiveLane:
683 case VPInstruction::LastActiveLane:
684 case VPInstruction::ExtractLane:
685 case VPInstruction::ExtractLastActive:
686 // Cannot determine the number of operands from the opcode.
687 return -1u;
688 }
689 llvm_unreachable("all cases should be handled above");
690}
691
692bool VPInstruction::doesGeneratePerAllLanes() const {
693 return Opcode == VPInstruction::Unpack ||
694 (Opcode == VPInstruction::PtrAdd && !vputils::onlyFirstLaneUsed(Def: this));
695}
696
697bool VPInstruction::canGenerateScalarForFirstLane() const {
698 if (Instruction::isBinaryOp(Opcode: getOpcode()) || Instruction::isCast(Opcode: getOpcode()))
699 return true;
700 if (isSingleScalar() || isVectorToScalar())
701 return true;
702 switch (Opcode) {
703 case Instruction::Freeze:
704 case Instruction::ICmp:
705 case Instruction::PHI:
706 case Instruction::Select:
707 case VPInstruction::BranchOnCond:
708 case VPInstruction::BranchOnTwoConds:
709 case VPInstruction::BranchOnCount:
710 case VPInstruction::CalculateTripCountMinusVF:
711 case VPInstruction::CanonicalIVIncrementForPart:
712 case VPInstruction::PtrAdd:
713 case VPInstruction::ExplicitVectorLength:
714 case VPInstruction::AnyOf:
715 case VPInstruction::Not:
716 return true;
717 default:
718 return false;
719 }
720}
721
722static Instruction::BinaryOps getSubRecurOpcode(RecurKind Kind) {
723 if (Kind == RecurKind::Sub)
724 return Instruction::Add;
725 if (Kind == RecurKind::FSub)
726 return Instruction::FAdd;
727 llvm_unreachable("RecurKind should be Sub/FSub.");
728}
729
730Value *VPInstruction::generate(VPTransformState &State) {
731 IRBuilderBase &Builder = State.Builder;
732
733 if (Instruction::isBinaryOp(Opcode: getOpcode())) {
734 bool OnlyFirstLaneUsed = vputils::onlyFirstLaneUsed(Def: this);
735 Value *A = State.get(Def: getOperand(N: 0), IsScalar: OnlyFirstLaneUsed);
736 Value *B = State.get(Def: getOperand(N: 1), IsScalar: OnlyFirstLaneUsed);
737 auto *Res =
738 Builder.CreateBinOp(Opc: (Instruction::BinaryOps)getOpcode(), LHS: A, RHS: B, Name);
739 if (auto *I = dyn_cast<Instruction>(Val: Res))
740 applyFlags(I&: *I);
741 return Res;
742 }
743
744 switch (getOpcode()) {
745 case VPInstruction::Not: {
746 bool OnlyFirstLaneUsed = vputils::onlyFirstLaneUsed(Def: this);
747 Value *A = State.get(Def: getOperand(N: 0), IsScalar: OnlyFirstLaneUsed);
748 return Builder.CreateNot(V: A, Name);
749 }
750 case Instruction::ExtractElement: {
751 assert(State.VF.isVector() && "Only extract elements from vectors");
752 if (auto *Idx = dyn_cast<VPConstantInt>(Val: getOperand(N: 1)))
753 return State.get(Def: getOperand(N: 0), Lane: VPLane(Idx->getZExtValue()));
754 Value *Vec = State.get(Def: getOperand(N: 0));
755 Value *Idx = State.get(Def: getOperand(N: 1), /*IsScalar=*/true);
756 return Builder.CreateExtractElement(Vec, Idx, Name);
757 }
758 case Instruction::InsertElement: {
759 assert(State.VF.isVector() && "Can only insert elements into vectors");
760 Value *Vec = State.get(Def: getOperand(N: 0), /*IsScalar=*/false);
761 Value *Elt = State.get(Def: getOperand(N: 1), /*IsScalar=*/true);
762 Value *Idx = State.get(Def: getOperand(N: 2), /*IsScalar=*/true);
763 return Builder.CreateInsertElement(Vec, NewElt: Elt, Idx, Name);
764 }
765 case Instruction::Freeze: {
766 Value *Op = State.get(Def: getOperand(N: 0), IsScalar: vputils::onlyFirstLaneUsed(Def: this));
767 return Builder.CreateFreeze(V: Op, Name);
768 }
769 case Instruction::FCmp:
770 case Instruction::ICmp: {
771 bool OnlyFirstLaneUsed = vputils::onlyFirstLaneUsed(Def: this);
772 Value *A = State.get(Def: getOperand(N: 0), IsScalar: OnlyFirstLaneUsed);
773 Value *B = State.get(Def: getOperand(N: 1), IsScalar: OnlyFirstLaneUsed);
774 return Builder.CreateCmp(Pred: getPredicate(), LHS: A, RHS: B, Name);
775 }
776 case Instruction::PHI: {
777 llvm_unreachable("should be handled by VPPhi::execute");
778 }
779 case Instruction::Select: {
780 bool OnlyFirstLaneUsed = vputils::onlyFirstLaneUsed(Def: this);
781 Value *Cond =
782 State.get(Def: getOperand(N: 0),
783 IsScalar: OnlyFirstLaneUsed || vputils::isSingleScalar(VPV: getOperand(N: 0)));
784 Value *Op1 = State.get(Def: getOperand(N: 1), IsScalar: OnlyFirstLaneUsed);
785 Value *Op2 = State.get(Def: getOperand(N: 2), IsScalar: OnlyFirstLaneUsed);
786 return Builder.CreateSelectFMF(C: Cond, True: Op1, False: Op2, FMFSource: getFastMathFlagsOrNone(),
787 Name);
788 }
789 case VPInstruction::ActiveLaneMask: {
790 // Get first lane of vector induction variable.
791 Value *VIVElem0 = State.get(Def: getOperand(N: 0), Lane: VPLane(0));
792 // Get the original loop tripcount.
793 Value *ScalarTC = State.get(Def: getOperand(N: 1), Lane: VPLane(0));
794
795 // If this part of the active lane mask is scalar, generate the CMP directly
796 // to avoid unnecessary extracts.
797 if (State.VF.isScalar())
798 return Builder.CreateCmp(Pred: CmpInst::Predicate::ICMP_ULT, LHS: VIVElem0, RHS: ScalarTC,
799 Name);
800
801 ElementCount EC = State.VF.multiplyCoefficientBy(
802 RHS: cast<VPConstantInt>(Val: getOperand(N: 2))->getZExtValue());
803 auto *PredTy = VectorType::get(ElementType: Builder.getInt1Ty(), EC);
804 return Builder.CreateIntrinsic(ID: Intrinsic::get_active_lane_mask,
805 OverloadTypes: {PredTy, ScalarTC->getType()},
806 Args: {VIVElem0, ScalarTC}, FMFSource: nullptr, Name);
807 }
808 case VPInstruction::NumActiveLanes: {
809 Value *Op = State.get(Def: getOperand(N: 0));
810 auto *VecTy = cast<VectorType>(Val: Op->getType());
811 assert(VecTy->getScalarSizeInBits() == 1 &&
812 "NumActiveLanes only implemented for i1 vectors");
813
814 Type *Ty = getScalarType();
815 Value *ZExt = Builder.CreateCast(
816 Op: Instruction::ZExt, V: Op, DestTy: VectorType::get(ElementType: Ty, EC: VecTy->getElementCount()));
817 Value *NumActive =
818 Builder.CreateUnaryIntrinsic(ID: Intrinsic::vector_reduce_add, Op: ZExt);
819 return NumActive;
820 }
821 case VPInstruction::FirstOrderRecurrenceSplice: {
822 // Generate code to combine the previous and current values in vector v3.
823 //
824 // vector.ph:
825 // v_init = vector(..., ..., ..., a[-1])
826 // br vector.body
827 //
828 // vector.body
829 // i = phi [0, vector.ph], [i+4, vector.body]
830 // v1 = phi [v_init, vector.ph], [v2, vector.body]
831 // v2 = a[i, i+1, i+2, i+3];
832 // v3 = vector(v1(3), v2(0, 1, 2))
833
834 auto *V1 = State.get(Def: getOperand(N: 0));
835 if (!V1->getType()->isVectorTy())
836 return V1;
837 Value *V2 = State.get(Def: getOperand(N: 1));
838 return Builder.CreateVectorSpliceRight(V1, V2, Offset: 1, Name);
839 }
840 case VPInstruction::CalculateTripCountMinusVF: {
841 Value *ScalarTC = State.get(Def: getOperand(N: 0), Lane: VPLane(0));
842 Value *VFxUF = State.get(Def: getOperand(N: 1), Lane: VPLane(0));
843 Value *Sub = Builder.CreateSub(LHS: ScalarTC, RHS: VFxUF);
844 Value *Cmp =
845 Builder.CreateICmp(P: CmpInst::Predicate::ICMP_UGT, LHS: ScalarTC, RHS: VFxUF);
846 Value *Zero = ConstantInt::getNullValue(Ty: ScalarTC->getType());
847 return Builder.CreateSelect(C: Cmp, True: Sub, False: Zero);
848 }
849 case VPInstruction::ExplicitVectorLength: {
850 // TODO: Restructure this code with an explicit remainder loop, vsetvli can
851 // be outside of the main loop.
852 Value *AVL = State.get(Def: getOperand(N: 0), /*IsScalar*/ true);
853 // Compute EVL
854 assert(AVL->getType()->isIntegerTy() &&
855 "Requested vector length should be an integer.");
856
857 assert(State.VF.isScalable() && "Expected scalable vector factor.");
858 Value *VFArg = Builder.getInt32(C: State.VF.getKnownMinValue());
859
860 Value *EVL = Builder.CreateIntrinsic(
861 RetTy: Builder.getInt32Ty(), ID: Intrinsic::experimental_get_vector_length,
862 Args: {AVL, VFArg, Builder.getTrue()});
863 return EVL;
864 }
865 case VPInstruction::BranchOnCond: {
866 Value *Cond = State.get(Def: getOperand(N: 0), Lane: VPLane(0));
867 // Replace the temporary unreachable terminator with a new conditional
868 // branch, hooking it up to backward destination for latch blocks now, and
869 // to forward destination(s) later when they are created.
870 // Second successor may be backwards - iff it is already in VPBB2IRBB.
871 VPBasicBlock *SecondVPSucc =
872 cast<VPBasicBlock>(Val: getParent()->getSuccessors()[1]);
873 BasicBlock *SecondIRSucc = State.CFG.VPBB2IRBB.lookup(Val: SecondVPSucc);
874 BasicBlock *IRBB = State.CFG.VPBB2IRBB[getParent()];
875 auto *Br = Builder.CreateCondBr(Cond, True: IRBB, False: SecondIRSucc);
876 // First successor is always forward, reset it to nullptr.
877 Br->setSuccessor(idx: 0, NewSucc: nullptr);
878 IRBB->getTerminator()->eraseFromParent();
879 applyMetadata(I&: *Br);
880 return Br;
881 }
882 case VPInstruction::Broadcast: {
883 return Builder.CreateVectorSplat(
884 EC: State.VF, V: State.get(Def: getOperand(N: 0), /*IsScalar*/ true), Name: "broadcast");
885 }
886 case VPInstruction::BuildStructVector: {
887 // For struct types, we need to build a new 'wide' struct type, where each
888 // element is widened, i.e., we create a struct of vectors.
889 auto *StructTy = cast<StructType>(Val: getOperand(N: 0)->getScalarType());
890 Value *Res = PoisonValue::get(T: toVectorizedTy(Ty: StructTy, EC: State.VF));
891 for (const auto &[LaneIndex, Op] : enumerate(First: operands())) {
892 for (unsigned FieldIndex = 0; FieldIndex != StructTy->getNumElements();
893 FieldIndex++) {
894 Value *ScalarValue =
895 Builder.CreateExtractValue(Agg: State.get(Def: Op, IsScalar: true), Idxs: FieldIndex);
896 Value *VectorValue = Builder.CreateExtractValue(Agg: Res, Idxs: FieldIndex);
897 VectorValue =
898 Builder.CreateInsertElement(Vec: VectorValue, NewElt: ScalarValue, Idx: LaneIndex);
899 Res = Builder.CreateInsertValue(Agg: Res, Val: VectorValue, Idxs: FieldIndex);
900 }
901 }
902 return Res;
903 }
904 case VPInstruction::BuildVector: {
905 auto *ScalarTy = getOperand(N: 0)->getScalarType();
906 auto NumOfElements = ElementCount::getFixed(MinVal: getNumOperands());
907 Value *Res = PoisonValue::get(T: toVectorizedTy(Ty: ScalarTy, EC: NumOfElements));
908 for (const auto &[Idx, Op] : enumerate(First: operands()))
909 Res = Builder.CreateInsertElement(Vec: Res, NewElt: State.get(Def: Op, IsScalar: true),
910 Idx: Builder.getInt32(C: Idx));
911 return Res;
912 }
913 case VPInstruction::ReductionStartVector: {
914 if (State.VF.isScalar())
915 return State.get(Def: getOperand(N: 0), IsScalar: true);
916 IRBuilderBase::FastMathFlagGuard FMFG(Builder);
917 Builder.setFastMathFlags(getFastMathFlagsOrNone());
918 // If this start vector is scaled then it should produce a vector with fewer
919 // elements than the VF.
920 ElementCount VF = State.VF.divideCoefficientBy(
921 RHS: cast<VPConstantInt>(Val: getOperand(N: 2))->getZExtValue());
922 auto *Iden = Builder.CreateVectorSplat(EC: VF, V: State.get(Def: getOperand(N: 1), IsScalar: true));
923 return Builder.CreateInsertElement(Vec: Iden, NewElt: State.get(Def: getOperand(N: 0), IsScalar: true),
924 Idx: Builder.getInt32(C: 0));
925 }
926 case VPInstruction::ComputeReductionResult: {
927 RecurKind RK = getRecurKind();
928 bool IsOrdered = isReductionOrdered();
929 bool IsInLoop = isReductionInLoop();
930 assert(!RecurrenceDescriptor::isFindIVRecurrenceKind(RK) &&
931 "FindIV should use min/max reduction kinds");
932
933 // The recipe may have multiple operands to be reduced together.
934 unsigned NumOperandsToReduce = getNumOperands();
935 VectorParts RdxParts(NumOperandsToReduce);
936 for (unsigned Part = 0; Part < NumOperandsToReduce; ++Part)
937 RdxParts[Part] = State.get(Def: getOperand(N: Part), IsScalar: IsInLoop);
938
939 IRBuilderBase::FastMathFlagGuard FMFG(Builder);
940 Builder.setFastMathFlags(getFastMathFlagsOrNone());
941
942 // Reduce multiple operands into one.
943 Value *ReducedPartRdx = RdxParts[0];
944 if (IsOrdered) {
945 ReducedPartRdx = RdxParts[NumOperandsToReduce - 1];
946 } else {
947 // Floating-point operations should have some FMF to enable the reduction.
948 for (unsigned Part = 1; Part < NumOperandsToReduce; ++Part) {
949 Value *RdxPart = RdxParts[Part];
950 if (RecurrenceDescriptor::isMinMaxRecurrenceKind(Kind: RK))
951 ReducedPartRdx = createMinMaxOp(Builder, RK, Left: ReducedPartRdx, Right: RdxPart);
952 else {
953 // For sub-recurrences, each part's reduction variable is already
954 // negative, we need to do: reduce.add(-acc_uf0 + -acc_uf1)
955 Instruction::BinaryOps Opcode =
956 RecurrenceDescriptor::isSubRecurrenceKind(Kind: RK)
957 ? getSubRecurOpcode(Kind: RK)
958 : (Instruction::BinaryOps)RecurrenceDescriptor::getOpcode(Kind: RK);
959 ReducedPartRdx =
960 Builder.CreateBinOp(Opc: Opcode, LHS: RdxPart, RHS: ReducedPartRdx, Name: "bin.rdx");
961 }
962 }
963 }
964
965 // Create the reduction after the loop. Note that inloop reductions create
966 // the target reduction in the loop using a Reduction recipe.
967 if (State.VF.isVector() && !IsInLoop) {
968 // TODO: Support in-order reductions based on the recurrence descriptor.
969 // All ops in the reduction inherit fast-math-flags from the recurrence
970 // descriptor.
971 ReducedPartRdx = createSimpleReduction(B&: Builder, Src: ReducedPartRdx, RdxKind: RK);
972 }
973
974 return ReducedPartRdx;
975 }
976 case VPInstruction::ExtractLastLane:
977 case VPInstruction::ExtractPenultimateElement: {
978 unsigned Offset =
979 getOpcode() == VPInstruction::ExtractPenultimateElement ? 2 : 1;
980 Value *Res;
981 if (State.VF.isVector()) {
982 assert(Offset <= State.VF.getKnownMinValue() &&
983 "invalid offset to extract from");
984 // Extract lane VF - Offset from the operand.
985 Res = State.get(Def: getOperand(N: 0), Lane: VPLane::getLaneFromEnd(VF: State.VF, Offset));
986 } else {
987 // TODO: Remove ExtractLastLane for scalar VFs.
988 assert(Offset <= 1 && "invalid offset to extract from");
989 Res = State.get(Def: getOperand(N: 0));
990 }
991 if (isa<ExtractElementInst>(Val: Res))
992 Res->setName(Name);
993 return Res;
994 }
995 case VPInstruction::LogicalAnd: {
996 Value *A = State.get(Def: getOperand(N: 0));
997 Value *B = State.get(Def: getOperand(N: 1));
998 return Builder.CreateLogicalAnd(Cond1: A, Cond2: B, Name);
999 }
1000 case VPInstruction::LogicalOr: {
1001 Value *A = State.get(Def: getOperand(N: 0));
1002 Value *B = State.get(Def: getOperand(N: 1));
1003 return Builder.CreateLogicalOr(Cond1: A, Cond2: B, Name);
1004 }
1005 case VPInstruction::PtrAdd: {
1006 assert((State.VF.isScalar() || vputils::onlyFirstLaneUsed(this)) &&
1007 "can only generate first lane for PtrAdd");
1008 Value *Ptr = State.get(Def: getOperand(N: 0), Lane: VPLane(0));
1009 Value *Addend = State.get(Def: getOperand(N: 1), Lane: VPLane(0));
1010 return Builder.CreatePtrAdd(Ptr, Offset: Addend, Name, NW: getGEPNoWrapFlags());
1011 }
1012 case VPInstruction::WidePtrAdd: {
1013 Value *Ptr =
1014 State.get(Def: getOperand(N: 0), IsScalar: vputils::isSingleScalar(VPV: getOperand(N: 0)));
1015 Value *Addend = State.get(Def: getOperand(N: 1));
1016 return Builder.CreatePtrAdd(Ptr, Offset: Addend, Name, NW: getGEPNoWrapFlags());
1017 }
1018 case VPInstruction::AnyOf: {
1019 Value *Res = Builder.CreateFreeze(V: State.get(Def: getOperand(N: 0)));
1020 for (VPValue *Op : drop_begin(RangeOrContainer: operands()))
1021 Res = Builder.CreateOr(LHS: Res, RHS: Builder.CreateFreeze(V: State.get(Def: Op)));
1022 return State.VF.isScalar() ? Res : Builder.CreateOrReduce(Src: Res);
1023 }
1024 case VPInstruction::ExtractLane: {
1025 assert(getNumOperands() != 2 && "ExtractLane from single source should be "
1026 "simplified to ExtractElement.");
1027 Value *LaneToExtract = State.get(Def: getOperand(N: 0), IsScalar: true);
1028 Type *IdxTy = getOperand(N: 0)->getScalarType();
1029 Value *Res = nullptr;
1030 Value *RuntimeVF = getRuntimeVF(B&: Builder, Ty: IdxTy, VF: State.VF);
1031
1032 for (unsigned Idx = 1; Idx != getNumOperands(); ++Idx) {
1033 Value *VectorStart =
1034 Builder.CreateMul(LHS: RuntimeVF, RHS: ConstantInt::get(Ty: IdxTy, V: Idx - 1));
1035 Value *VectorIdx = Idx == 1
1036 ? LaneToExtract
1037 : Builder.CreateSub(LHS: LaneToExtract, RHS: VectorStart);
1038 Value *Ext = State.VF.isScalar()
1039 ? State.get(Def: getOperand(N: Idx))
1040 : Builder.CreateExtractElement(
1041 Vec: State.get(Def: getOperand(N: Idx)), Idx: VectorIdx);
1042 if (Res) {
1043 Value *Cmp = Builder.CreateICmpUGE(LHS: LaneToExtract, RHS: VectorStart);
1044 Res = Builder.CreateSelect(C: Cmp, True: Ext, False: Res);
1045 } else {
1046 Res = Ext;
1047 }
1048 }
1049 return Res;
1050 }
1051 case VPInstruction::FirstActiveLane: {
1052 Type *Ty = this->getScalarType();
1053 if (getNumOperands() == 1) {
1054 Value *Mask = State.get(Def: getOperand(N: 0));
1055 return Builder.CreateCountTrailingZeroElems(ResTy: Ty, Mask,
1056 /*ZeroIsPoison=*/false, Name);
1057 }
1058 // If there are multiple operands, create a chain of selects to pick the
1059 // first operand with an active lane and add the number of lanes of the
1060 // preceding operands.
1061 Value *RuntimeVF = getRuntimeVF(B&: Builder, Ty, VF: State.VF);
1062 unsigned LastOpIdx = getNumOperands() - 1;
1063 Value *Res = nullptr;
1064 for (int Idx = LastOpIdx; Idx >= 0; --Idx) {
1065 Value *TrailingZeros =
1066 State.VF.isScalar()
1067 ? Builder.CreateZExt(
1068 V: Builder.CreateICmpEQ(LHS: State.get(Def: getOperand(N: Idx)),
1069 RHS: Builder.getFalse()),
1070 DestTy: Ty)
1071 : Builder.CreateCountTrailingZeroElems(
1072 ResTy: Ty, Mask: State.get(Def: getOperand(N: Idx)),
1073 /*ZeroIsPoison=*/false, Name);
1074 Value *Current = Builder.CreateAdd(
1075 LHS: Builder.CreateMul(LHS: RuntimeVF, RHS: ConstantInt::get(Ty, V: Idx)),
1076 RHS: TrailingZeros);
1077 if (Res) {
1078 Value *Cmp = Builder.CreateICmpNE(LHS: TrailingZeros, RHS: RuntimeVF);
1079 Res = Builder.CreateSelect(C: Cmp, True: Current, False: Res);
1080 } else {
1081 Res = Current;
1082 }
1083 }
1084
1085 return Res;
1086 }
1087 case VPInstruction::ResumeForEpilogue:
1088 return State.get(Def: getOperand(N: 0), IsScalar: true);
1089 case VPInstruction::Reverse:
1090 return Builder.CreateVectorReverse(V: State.get(Def: getOperand(N: 0)), Name: "reverse");
1091 case VPInstruction::ExtractLastActive: {
1092 Value *Result = State.get(Def: getOperand(N: 0), /*IsScalar=*/true);
1093 for (unsigned Idx = 1; Idx < getNumOperands(); Idx += 2) {
1094 Value *Data = State.get(Def: getOperand(N: Idx));
1095 Value *Mask = State.get(Def: getOperand(N: Idx + 1));
1096 Type *VTy = Data->getType();
1097
1098 if (State.VF.isScalar())
1099 Result = Builder.CreateSelect(C: Mask, True: Data, False: Result);
1100 else
1101 Result = Builder.CreateIntrinsic(
1102 ID: Intrinsic::experimental_vector_extract_last_active, OverloadTypes: {VTy},
1103 Args: {Data, Mask, Result});
1104 }
1105
1106 return Result;
1107 }
1108 default:
1109 llvm_unreachable("Unsupported opcode for instruction");
1110 }
1111}
1112
1113InstructionCost VPRecipeWithIRFlags::getCostForRecipeWithOpcode(
1114 unsigned Opcode, ElementCount VF, VPCostContext &Ctx) const {
1115 Type *ScalarTy = this->getScalarType();
1116 Type *ResultTy = VF.isVector() ? toVectorTy(Scalar: ScalarTy, EC: VF) : ScalarTy;
1117 switch (Opcode) {
1118 case Instruction::FNeg:
1119 return Ctx.TTI.getArithmeticInstrCost(Opcode, Ty: ResultTy, CostKind: Ctx.CostKind);
1120 case Instruction::UDiv:
1121 case Instruction::SDiv:
1122 case Instruction::SRem:
1123 case Instruction::URem:
1124 case Instruction::Add:
1125 case Instruction::FAdd:
1126 case Instruction::Sub:
1127 case Instruction::FSub:
1128 case Instruction::Mul:
1129 case Instruction::FMul:
1130 case Instruction::FDiv:
1131 case Instruction::FRem:
1132 case Instruction::Shl:
1133 case Instruction::LShr:
1134 case Instruction::AShr:
1135 case Instruction::And:
1136 case Instruction::Or:
1137 case Instruction::Xor: {
1138 // Certain instructions can be cheaper if they have a constant second
1139 // operand. One example of this are shifts on x86.
1140 VPValue *RHS = getOperand(N: 1);
1141 TargetTransformInfo::OperandValueInfo RHSInfo = Ctx.getOperandInfo(V: RHS);
1142
1143 if (RHSInfo.Kind == TargetTransformInfo::OK_AnyValue &&
1144 getOperand(N: 1)->isDefinedOutsideLoopRegions())
1145 RHSInfo.Kind = TargetTransformInfo::OK_UniformValue;
1146
1147 Instruction *CtxI = dyn_cast_or_null<Instruction>(Val: getUnderlyingValue());
1148 SmallVector<const Value *, 4> Operands;
1149 if (CtxI)
1150 Operands.append(in_start: CtxI->value_op_begin(), in_end: CtxI->value_op_end());
1151 return Ctx.TTI.getArithmeticInstrCost(
1152 Opcode, Ty: ResultTy, CostKind: Ctx.CostKind,
1153 Opd1Info: {.Kind: TargetTransformInfo::OK_AnyValue, .Properties: TargetTransformInfo::OP_None},
1154 Opd2Info: RHSInfo, Args: Operands, CxtI: CtxI, TLibInfo: &Ctx.TLI);
1155 }
1156 case Instruction::Freeze:
1157 // NOTE: The only way to ask for the cost is via getInstructionCost, which
1158 // requires the actual vector instruction. Instead, both here and in the
1159 // LoopVectorizationCostModel::getInstructionCost the costs mirror the
1160 // current behaviour in llvm/Analysis/TargetTransformInfoImpl.h to keep
1161 // them in sync.
1162 return TTI::TCC_Free;
1163 case Instruction::ExtractValue:
1164 return Ctx.TTI.getInsertExtractValueCost(Opcode: Instruction::ExtractValue,
1165 CostKind: Ctx.CostKind);
1166 case Instruction::ICmp:
1167 case Instruction::FCmp: {
1168 Type *ScalarOpTy = getOperand(N: 0)->getScalarType();
1169 Type *OpTy = VF.isVector() ? toVectorTy(Scalar: ScalarOpTy, EC: VF) : ScalarOpTy;
1170 Instruction *CtxI = dyn_cast_or_null<Instruction>(Val: getUnderlyingValue());
1171 return Ctx.TTI.getCmpSelInstrCost(
1172 Opcode, ValTy: OpTy, CondTy: CmpInst::makeCmpResultType(opnd_type: OpTy), VecPred: getPredicate(),
1173 CostKind: Ctx.CostKind, Op1Info: {.Kind: TTI::OK_AnyValue, .Properties: TTI::OP_None},
1174 Op2Info: {.Kind: TTI::OK_AnyValue, .Properties: TTI::OP_None}, I: CtxI);
1175 }
1176 case Instruction::BitCast: {
1177 Type *ScalarTy = this->getScalarType();
1178 if (ScalarTy->isPointerTy())
1179 return 0;
1180 [[fallthrough]];
1181 }
1182 case Instruction::SExt:
1183 case Instruction::ZExt:
1184 case Instruction::FPToUI:
1185 case Instruction::FPToSI:
1186 case Instruction::FPExt:
1187 case Instruction::PtrToInt:
1188 case Instruction::PtrToAddr:
1189 case Instruction::IntToPtr:
1190 case Instruction::SIToFP:
1191 case Instruction::UIToFP:
1192 case Instruction::Trunc:
1193 case Instruction::FPTrunc:
1194 case Instruction::AddrSpaceCast: {
1195 // Computes the CastContextHint from a recipe that may access memory.
1196 auto ComputeCCH = [&](const VPRecipeBase *R) -> TTI::CastContextHint {
1197 if (isa<VPInterleaveBase>(Val: R))
1198 return TTI::CastContextHint::Interleave;
1199 if (const auto *ReplicateRecipe = dyn_cast<VPReplicateRecipe>(Val: R)) {
1200 // Only compute CCH for memory operations, matching the legacy model
1201 // which only considers loads/stores for cast context hints.
1202 auto *UI = cast<Instruction>(Val: ReplicateRecipe->getUnderlyingValue());
1203 if (!isa<LoadInst, StoreInst>(Val: UI))
1204 return TTI::CastContextHint::None;
1205 return ReplicateRecipe->isPredicated() ? TTI::CastContextHint::Masked
1206 : TTI::CastContextHint::Normal;
1207 }
1208 const auto *WidenMemoryRecipe = dyn_cast<VPWidenMemoryRecipe>(Val: R);
1209 if (WidenMemoryRecipe == nullptr)
1210 return TTI::CastContextHint::None;
1211 if (VF.isScalar())
1212 return TTI::CastContextHint::Normal;
1213 if (!WidenMemoryRecipe->isConsecutive())
1214 return TTI::CastContextHint::GatherScatter;
1215 if (WidenMemoryRecipe->isMasked())
1216 return TTI::CastContextHint::Masked;
1217 return TTI::CastContextHint::Normal;
1218 };
1219
1220 VPValue *Operand = getOperand(N: 0);
1221 TTI::CastContextHint CCH = TTI::CastContextHint::None;
1222 bool IsReverse = false;
1223 // For Trunc/FPTrunc, get the context from the only user.
1224 if (Opcode == Instruction::Trunc || Opcode == Instruction::FPTrunc) {
1225 if (auto *Recipe = cast_or_null<VPRecipeBase>(Val: getSingleUser())) {
1226 if (match(V: Recipe,
1227 P: m_CombineOr(
1228 Ps: m_Reverse(Op0: m_VPValue()),
1229 Ps: m_Intrinsic<Intrinsic::experimental_vp_reverse>()))) {
1230 IsReverse = true;
1231 Recipe = cast_or_null<VPRecipeBase>(
1232 Val: Recipe->getVPSingleValue()->getSingleUser());
1233 }
1234 if (Recipe)
1235 CCH = ComputeCCH(Recipe);
1236 }
1237 }
1238 // For Z/Sext, get the context from the operand.
1239 else if (Opcode == Instruction::ZExt || Opcode == Instruction::SExt ||
1240 Opcode == Instruction::FPExt) {
1241 if (auto *Recipe = Operand->getDefiningRecipe()) {
1242 VPValue *ReverseOp;
1243 if (match(V: Recipe,
1244 P: m_CombineOr(Ps: m_Reverse(Op0: m_VPValue(V&: ReverseOp)),
1245 Ps: m_Intrinsic<Intrinsic::experimental_vp_reverse>(
1246 Ops: m_VPValue(V&: ReverseOp))))) {
1247 Recipe = ReverseOp->getDefiningRecipe();
1248 IsReverse = true;
1249 }
1250 if (Recipe)
1251 CCH = ComputeCCH(Recipe);
1252 }
1253 }
1254 if (IsReverse && CCH != TTI::CastContextHint::None)
1255 CCH = TTI::CastContextHint::Reversed;
1256
1257 auto *ScalarSrcTy = Operand->getScalarType();
1258 Type *SrcTy = VF.isVector() ? toVectorTy(Scalar: ScalarSrcTy, EC: VF) : ScalarSrcTy;
1259 // Arm TTI will use the underlying instruction to determine the cost.
1260 return Ctx.TTI.getCastInstrCost(
1261 Opcode, Dst: ResultTy, Src: SrcTy, CCH, CostKind: Ctx.CostKind,
1262 I: dyn_cast_if_present<Instruction>(Val: getUnderlyingValue()));
1263 }
1264 case Instruction::Select: {
1265 SelectInst *SI = cast_or_null<SelectInst>(Val: getUnderlyingValue());
1266 bool IsScalarCond = getOperand(N: 0)->isDefinedOutsideLoopRegions();
1267 Type *ScalarTy = this->getScalarType();
1268
1269 VPValue *Op0, *Op1;
1270 bool IsLogicalAnd =
1271 match(V: this, P: m_c_LogicalAnd(Op0: m_VPValue(V&: Op0), Op1: m_VPValue(V&: Op1)));
1272 bool IsLogicalOr =
1273 match(V: this, P: m_c_LogicalOr(Op0: m_VPValue(V&: Op0), Op1: m_VPValue(V&: Op1)));
1274 // Also match the inverted forms:
1275 // select x, false, y --> !x & y (still AND)
1276 // select x, y, true --> !x | y (still OR)
1277 IsLogicalAnd |=
1278 match(V: this, P: m_Select(Op0: m_VPValue(V&: Op0), Op1: m_False(), Op2: m_VPValue(V&: Op1)));
1279 IsLogicalOr |=
1280 match(V: this, P: m_Select(Op0: m_VPValue(V&: Op0), Op1: m_VPValue(V&: Op1), Op2: m_True()));
1281
1282 if (!IsScalarCond && ScalarTy->getScalarSizeInBits() == 1 &&
1283 (IsLogicalAnd || IsLogicalOr)) {
1284 // select x, y, false --> x & y
1285 // select x, true, y --> x | y
1286 const auto [Op1VK, Op1VP] = Ctx.getOperandInfo(V: Op0);
1287 const auto [Op2VK, Op2VP] = Ctx.getOperandInfo(V: Op1);
1288
1289 SmallVector<const Value *, 2> Operands;
1290 if (SI && all_of(Range: operands(),
1291 P: [](VPValue *Op) { return Op->getUnderlyingValue(); }))
1292 append_range(C&: Operands, R: SI->operands());
1293 return Ctx.TTI.getArithmeticInstrCost(
1294 Opcode: IsLogicalOr ? Instruction::Or : Instruction::And, Ty: ResultTy,
1295 CostKind: Ctx.CostKind, Opd1Info: {.Kind: Op1VK, .Properties: Op1VP}, Opd2Info: {.Kind: Op2VK, .Properties: Op2VP}, Args: Operands, CxtI: SI);
1296 }
1297
1298 Type *CondTy = getOperand(N: 0)->getScalarType();
1299 if (!IsScalarCond && VF.isVector())
1300 CondTy = VectorType::get(ElementType: CondTy, EC: VF);
1301
1302 llvm::CmpPredicate Pred;
1303 if (!match(V: getOperand(N: 0), P: m_Cmp(Pred, Op0: m_VPValue(), Op1: m_VPValue())))
1304 if (auto *CondIRV = dyn_cast<VPIRValue>(Val: getOperand(N: 0)))
1305 if (auto *Cmp = dyn_cast<CmpInst>(Val: CondIRV->getValue()))
1306 Pred = Cmp->getPredicate();
1307 Type *VectorTy = toVectorTy(Scalar: this->getScalarType(), EC: VF);
1308 return Ctx.TTI.getCmpSelInstrCost(
1309 Opcode: Instruction::Select, ValTy: VectorTy, CondTy, VecPred: Pred, CostKind: Ctx.CostKind,
1310 Op1Info: {.Kind: TTI::OK_AnyValue, .Properties: TTI::OP_None}, Op2Info: {.Kind: TTI::OK_AnyValue, .Properties: TTI::OP_None}, I: SI);
1311 }
1312 }
1313 llvm_unreachable("called for unsupported opcode");
1314}
1315
1316InstructionCost VPInstruction::computeCost(ElementCount VF,
1317 VPCostContext &Ctx) const {
1318 if (Instruction::isBinaryOp(Opcode: getOpcode())) {
1319 if (!getUnderlyingValue() && getOpcode() != Instruction::FMul) {
1320 // TODO: Compute cost for VPInstructions without underlying values once
1321 // the legacy cost model has been retired.
1322 return 0;
1323 }
1324
1325 assert(!doesGeneratePerAllLanes() &&
1326 "Should only generate a vector value or single scalar, not scalars "
1327 "for all lanes.");
1328 return getCostForRecipeWithOpcode(
1329 Opcode: getOpcode(),
1330 VF: vputils::onlyFirstLaneUsed(Def: this) ? ElementCount::getFixed(MinVal: 1) : VF, Ctx);
1331 }
1332
1333 switch (getOpcode()) {
1334 case Instruction::Select: {
1335 llvm::CmpPredicate Pred = CmpInst::BAD_ICMP_PREDICATE;
1336 match(V: getOperand(N: 0), P: m_Cmp(Pred, Op0: m_VPValue(), Op1: m_VPValue()));
1337 auto *CondTy = getOperand(N: 0)->getScalarType();
1338 auto *VecTy = getOperand(N: 1)->getScalarType();
1339 if (!vputils::onlyFirstLaneUsed(Def: this)) {
1340 CondTy = toVectorTy(Scalar: CondTy, EC: VF);
1341 VecTy = toVectorTy(Scalar: VecTy, EC: VF);
1342 }
1343 return Ctx.TTI.getCmpSelInstrCost(Opcode: Instruction::Select, ValTy: VecTy, CondTy, VecPred: Pred,
1344 CostKind: Ctx.CostKind);
1345 }
1346 case Instruction::ExtractElement:
1347 case VPInstruction::ExtractLane: {
1348 if (VF.isScalar()) {
1349 // ExtractLane with VF=1 takes care of handling extracting across multiple
1350 // parts.
1351 return 0;
1352 }
1353
1354 // Add on the cost of extracting the element.
1355 auto *VecTy = toVectorTy(Scalar: getOperand(N: 0)->getScalarType(), EC: VF);
1356 return Ctx.TTI.getVectorInstrCost(Opcode: Instruction::ExtractElement, Val: VecTy,
1357 CostKind: Ctx.CostKind);
1358 }
1359 case VPInstruction::AnyOf: {
1360 auto *VecTy = toVectorTy(Scalar: this->getScalarType(), EC: VF);
1361 return Ctx.TTI.getArithmeticReductionCost(
1362 Opcode: Instruction::Or, Ty: cast<VectorType>(Val: VecTy), FMF: std::nullopt, CostKind: Ctx.CostKind);
1363 }
1364 case VPInstruction::FirstActiveLane: {
1365 Type *Ty = this->getScalarType();
1366 Type *ScalarTy = getOperand(N: 0)->getScalarType();
1367 if (VF.isScalar())
1368 return Ctx.TTI.getCmpSelInstrCost(Opcode: Instruction::ICmp, ValTy: ScalarTy,
1369 CondTy: CmpInst::makeCmpResultType(opnd_type: ScalarTy),
1370 VecPred: CmpInst::ICMP_EQ, CostKind: Ctx.CostKind);
1371 // Calculate the cost of determining the lane index.
1372 auto *PredTy = toVectorTy(Scalar: ScalarTy, EC: VF);
1373 IntrinsicCostAttributes Attrs(Intrinsic::experimental_cttz_elts, Ty,
1374 {PredTy, Type::getInt1Ty(C&: Ctx.LLVMCtx)});
1375 return Ctx.TTI.getIntrinsicInstrCost(ICA: Attrs, CostKind: Ctx.CostKind);
1376 }
1377 case VPInstruction::LastActiveLane: {
1378 Type *Ty = this->getScalarType();
1379 Type *ScalarTy = getOperand(N: 0)->getScalarType();
1380 if (VF.isScalar())
1381 return Ctx.TTI.getCmpSelInstrCost(Opcode: Instruction::ICmp, ValTy: ScalarTy,
1382 CondTy: CmpInst::makeCmpResultType(opnd_type: ScalarTy),
1383 VecPred: CmpInst::ICMP_EQ, CostKind: Ctx.CostKind);
1384 // Calculate the cost of determining the lane index: NOT + cttz_elts + SUB.
1385 auto *PredTy = toVectorTy(Scalar: ScalarTy, EC: VF);
1386 IntrinsicCostAttributes Attrs(Intrinsic::experimental_cttz_elts, Ty,
1387 {PredTy, Type::getInt1Ty(C&: Ctx.LLVMCtx)});
1388 InstructionCost Cost = Ctx.TTI.getIntrinsicInstrCost(ICA: Attrs, CostKind: Ctx.CostKind);
1389 // Add cost of NOT operation on the predicate.
1390 Cost += Ctx.TTI.getArithmeticInstrCost(
1391 Opcode: Instruction::Xor, Ty: PredTy, CostKind: Ctx.CostKind,
1392 Opd1Info: {.Kind: TargetTransformInfo::OK_AnyValue, .Properties: TargetTransformInfo::OP_None},
1393 Opd2Info: {.Kind: TargetTransformInfo::OK_UniformConstantValue,
1394 .Properties: TargetTransformInfo::OP_None});
1395 // Add cost of SUB operation on the index.
1396 Cost += Ctx.TTI.getArithmeticInstrCost(Opcode: Instruction::Sub, Ty, CostKind: Ctx.CostKind);
1397 return Cost;
1398 }
1399 case VPInstruction::ExtractLastActive: {
1400 Type *ScalarTy = this->getScalarType();
1401 Type *VecTy = toVectorTy(Scalar: ScalarTy, EC: VF);
1402 Type *MaskTy = toVectorTy(Scalar: Type::getInt1Ty(C&: Ctx.LLVMCtx), EC: VF);
1403 IntrinsicCostAttributes ICA(
1404 Intrinsic::experimental_vector_extract_last_active, ScalarTy,
1405 {VecTy, MaskTy, ScalarTy});
1406 return Ctx.TTI.getIntrinsicInstrCost(ICA, CostKind: Ctx.CostKind);
1407 }
1408 case VPInstruction::FirstOrderRecurrenceSplice: {
1409 assert(VF.isVector() && "Scalar FirstOrderRecurrenceSplice?");
1410 Type *VectorTy = toVectorTy(Scalar: this->getScalarType(), EC: VF);
1411 return Ctx.TTI.getShuffleCost(
1412 Kind: TargetTransformInfo::SK_Splice, DstTy: cast<VectorType>(Val: VectorTy),
1413 SrcTy: cast<VectorType>(Val: VectorTy), Mask: {}, CostKind: Ctx.CostKind, Index: -1);
1414 }
1415 case VPInstruction::ActiveLaneMask: {
1416 Type *ArgTy = getOperand(N: 0)->getScalarType();
1417 unsigned Multiplier = cast<VPConstantInt>(Val: getOperand(N: 2))->getZExtValue();
1418 Type *RetTy = toVectorTy(Scalar: Type::getInt1Ty(C&: Ctx.LLVMCtx), EC: VF * Multiplier);
1419 IntrinsicCostAttributes Attrs(Intrinsic::get_active_lane_mask, RetTy,
1420 {ArgTy, ArgTy});
1421 return Ctx.TTI.getIntrinsicInstrCost(ICA: Attrs, CostKind: Ctx.CostKind);
1422 }
1423 case VPInstruction::ExplicitVectorLength: {
1424 Type *Arg0Ty = getOperand(N: 0)->getScalarType();
1425 Type *I32Ty = Type::getInt32Ty(C&: Ctx.LLVMCtx);
1426 Type *I1Ty = Type::getInt1Ty(C&: Ctx.LLVMCtx);
1427 IntrinsicCostAttributes Attrs(Intrinsic::experimental_get_vector_length,
1428 I32Ty, {Arg0Ty, I32Ty, I1Ty});
1429 return Ctx.TTI.getIntrinsicInstrCost(ICA: Attrs, CostKind: Ctx.CostKind);
1430 }
1431 case VPInstruction::Reverse: {
1432 assert(VF.isVector() && "Reverse operation must be vector type");
1433 Type *EltTy = this->getScalarType();
1434 // Skip the reverse operation cost for the mask.
1435 // FIXME: Remove this once redundant mask reverse operations can be
1436 // eliminated by VPlanTransforms::cse before cost computation.
1437 if (EltTy->isIntegerTy(BitWidth: 1))
1438 return 0;
1439 auto *VectorTy = cast<VectorType>(Val: toVectorTy(Scalar: EltTy, EC: VF));
1440 return Ctx.TTI.getShuffleCost(Kind: TargetTransformInfo::SK_Reverse, DstTy: VectorTy,
1441 SrcTy: VectorTy, /*Mask=*/{}, CostKind: Ctx.CostKind,
1442 /*Index=*/0);
1443 }
1444 case VPInstruction::ExtractLastLane: {
1445 // Add on the cost of extracting the element.
1446 auto *VecTy = toVectorTy(Scalar: getOperand(N: 0)->getScalarType(), EC: VF);
1447 return Ctx.TTI.getIndexedVectorInstrCostFromEnd(Opcode: Instruction::ExtractElement,
1448 Val: VecTy, CostKind: Ctx.CostKind, Index: 0);
1449 }
1450 case VPInstruction::Not: {
1451 Type *ValTy = this->getScalarType();
1452 // InstCombine will fold `xor` to the conditional branch.
1453 if (auto *U = const_cast<VPUser *>(getSingleUser()))
1454 if (match(U, P: m_BranchOnCond(Op0: m_VPValue())))
1455 return 0;
1456 if (!vputils::onlyFirstLaneUsed(Def: this))
1457 ValTy = toVectorTy(Scalar: ValTy, EC: VF);
1458 return Ctx.TTI.getArithmeticInstrCost(Opcode: Instruction::Xor, Ty: ValTy,
1459 CostKind: Ctx.CostKind);
1460 }
1461 case VPInstruction::BranchOnCount: {
1462 // If TC <= VF then this is just a branch.
1463 // FIXME: Removing the branch happens in simplifyBranchConditionForVFAndUF
1464 // where it checks TC <= VF * UF, but we don't know UF yet. This means in
1465 // some cases we get a cost that's too high due to counting a cmp that
1466 // later gets removed.
1467 // FIXME: The compare could also be removed if TC = M * vscale,
1468 // VF = N * vscale, and M <= N. Detecting that would require having the
1469 // trip count as a SCEV though.
1470 Value *TC = getParent()->getPlan()->getTripCount()->getUnderlyingValue();
1471 ConstantInt *TCConst = dyn_cast_if_present<ConstantInt>(Val: TC);
1472 if (TCConst && TCConst->getValue().ule(RHS: VF.getKnownMinValue()))
1473 return 0;
1474 // Otherwise BranchOnCount generates ICmpEQ followed by a branch.
1475 Type *ValTy = getOperand(N: 0)->getScalarType();
1476 return Ctx.TTI.getCmpSelInstrCost(Opcode: Instruction::ICmp, ValTy,
1477 CondTy: CmpInst::makeCmpResultType(opnd_type: ValTy),
1478 VecPred: CmpInst::ICMP_EQ, CostKind: Ctx.CostKind);
1479 }
1480 case Instruction::FCmp:
1481 case Instruction::ICmp:
1482 return getCostForRecipeWithOpcode(
1483 Opcode: getOpcode(),
1484 VF: vputils::onlyFirstLaneUsed(Def: this) ? ElementCount::getFixed(MinVal: 1) : VF, Ctx);
1485 case VPInstruction::ExtractPenultimateElement:
1486 if (VF == ElementCount::getScalable(MinVal: 1))
1487 return InstructionCost::getInvalid();
1488 [[fallthrough]];
1489 default:
1490 // TODO: Compute cost other VPInstructions once the legacy cost model has
1491 // been retired.
1492 assert(!getUnderlyingValue() &&
1493 "unexpected VPInstruction witht underlying value");
1494 return 0;
1495 }
1496}
1497
1498bool VPInstruction::isVectorToScalar() const {
1499 return getOpcode() == VPInstruction::ExtractLastLane ||
1500 getOpcode() == VPInstruction::ExtractPenultimateElement ||
1501 getOpcode() == Instruction::ExtractElement ||
1502 getOpcode() == VPInstruction::ExtractLane ||
1503 getOpcode() == VPInstruction::FirstActiveLane ||
1504 getOpcode() == VPInstruction::LastActiveLane ||
1505 getOpcode() == VPInstruction::ExtractLastActive ||
1506 getOpcode() == VPInstruction::ComputeReductionResult ||
1507 getOpcode() == VPInstruction::AnyOf ||
1508 getOpcode() == VPInstruction::NumActiveLanes;
1509}
1510
1511bool VPInstruction::isSingleScalar() const {
1512 switch (getOpcode()) {
1513 case Instruction::Load:
1514 case Instruction::PHI:
1515 case VPInstruction::ExplicitVectorLength:
1516 case VPInstruction::ResumeForEpilogue:
1517 case VPInstruction::Intrinsic:
1518 return true;
1519 default:
1520 return Instruction::isCast(Opcode: getOpcode());
1521 }
1522}
1523
1524void VPInstruction::addOperand(VPValue *Op) {
1525#ifndef NDEBUG
1526 Type *Ty = Op->getScalarType();
1527 switch (getOpcode()) {
1528 case VPInstruction::AnyOf:
1529 case VPInstruction::FirstActiveLane:
1530 case VPInstruction::LastActiveLane:
1531 assert(Ty == getOperand(0)->getScalarType() &&
1532 "types of operand 0 and new operand must match");
1533 break;
1534 case VPInstruction::ComputeReductionResult:
1535 case VPInstruction::BuildVector:
1536 case VPInstruction::BuildStructVector:
1537 assert(Ty == getOperand(0)->getScalarType() &&
1538 "appended operand must match operand 0's scalar type");
1539 break;
1540 case VPInstruction::ExtractLane:
1541 assert(Ty == getOperand(1)->getScalarType() &&
1542 "appended operand must match operand 1's scalar type");
1543 break;
1544 case VPInstruction::ExtractLastActive: {
1545 // The recipe is constructed with 3 operands (result, data, mask). Extra
1546 // operands beyond that are appended in (data, mask) pairs.
1547 constexpr unsigned NumInitialOperands = 3;
1548 assert(getNumOperands() >= NumInitialOperands &&
1549 "ExtractLastActive must have at least the initial 3 operands");
1550 bool IsMaskSlot = ((getNumOperands() - NumInitialOperands) & 1u) == 1u;
1551 assert((IsMaskSlot ? Ty->isIntegerTy(1)
1552 : Ty == getOperand(1)->getScalarType()) &&
1553 "ExtractLastActive expects alternating data/mask operands "
1554 "matching operand 1's type and i1, respectively");
1555 break;
1556 }
1557 default:
1558 llvm_unreachable("opcode does not support growing the operand list "
1559 "outside of construction");
1560 }
1561#endif
1562 VPUser::addOperand(Operand: Op);
1563}
1564
1565void VPInstruction::execute(VPTransformState &State) {
1566 assert(!isMasked() && "cannot execute masked VPInstruction");
1567 IRBuilderBase::FastMathFlagGuard FMFGuard(State.Builder);
1568 assert(flagsValidForOpcode(getOpcode()) &&
1569 "Set flags not supported for the provided opcode");
1570 assert(hasRequiredFlagsForOpcode(getOpcode()) &&
1571 "Opcode requires specific flags to be set");
1572 State.Builder.setFastMathFlags(getFastMathFlagsOrNone());
1573 Value *GeneratedValue = generate(State);
1574 if (!hasResult())
1575 return;
1576 assert(GeneratedValue && "generate must produce a value");
1577 bool GeneratesPerFirstLaneOnly = canGenerateScalarForFirstLane() &&
1578 (vputils::onlyFirstLaneUsed(Def: this) ||
1579 isVectorToScalar() || isSingleScalar());
1580 assert((((GeneratedValue->getType()->isVectorTy() ||
1581 GeneratedValue->getType()->isStructTy()) ==
1582 !GeneratesPerFirstLaneOnly) ||
1583 State.VF.isScalar()) &&
1584 "scalar value but not only first lane defined");
1585 State.set(Def: this, V: GeneratedValue,
1586 /*IsScalar*/ GeneratesPerFirstLaneOnly);
1587 if (getOpcode() == VPInstruction::ResumeForEpilogue ||
1588 getOpcode() == Instruction::Freeze) {
1589 // FIXME: This is a workaround to enable reliable updates of the scalar loop
1590 // resume phis, and to let epilogue vectorization recover the frozen
1591 // reduction start from the main plan. Must be removed once epilogue
1592 // vectorization explicitly connects VPlans.
1593 setUnderlyingValue(GeneratedValue);
1594 }
1595}
1596
1597bool VPInstruction::opcodeMayReadOrWriteFromMemory() const {
1598 if (Instruction::isBinaryOp(Opcode: getOpcode()) ||
1599 Instruction::isUnaryOp(Opcode: getOpcode()) || Instruction::isCast(Opcode: getOpcode()))
1600 return false;
1601 switch (getOpcode()) {
1602 case Instruction::ExtractValue:
1603 case Instruction::InsertValue:
1604 case Instruction::GetElementPtr:
1605 case Instruction::ExtractElement:
1606 case Instruction::InsertElement:
1607 case Instruction::Freeze:
1608 case Instruction::FCmp:
1609 case Instruction::ICmp:
1610 case Instruction::Select:
1611 case Instruction::PHI:
1612 case VPInstruction::AnyOf:
1613 case VPInstruction::BranchOnCond:
1614 case VPInstruction::BranchOnTwoConds:
1615 case VPInstruction::BranchOnCount:
1616 case VPInstruction::Broadcast:
1617 case VPInstruction::BuildStructVector:
1618 case VPInstruction::BuildVector:
1619 case VPInstruction::CalculateTripCountMinusVF:
1620 case VPInstruction::CanonicalIVIncrementForPart:
1621 case VPInstruction::ExtractLane:
1622 case VPInstruction::ExtractLastLane:
1623 case VPInstruction::ExtractLastPart:
1624 case VPInstruction::ExtractPenultimateElement:
1625 case VPInstruction::ActiveLaneMask:
1626 case VPInstruction::IncomingAliasMask:
1627 case VPInstruction::ExitingIVValue:
1628 case VPInstruction::ExplicitVectorLength:
1629 case VPInstruction::FirstActiveLane:
1630 case VPInstruction::LastActiveLane:
1631 case VPInstruction::ExtractLastActive:
1632 case VPInstruction::FirstOrderRecurrenceSplice:
1633 case VPInstruction::LogicalAnd:
1634 case VPInstruction::LogicalOr:
1635 case VPInstruction::MaskedCond:
1636 case VPInstruction::Not:
1637 case VPInstruction::PtrAdd:
1638 case VPInstruction::WideIVStep:
1639 case VPInstruction::WidePtrAdd:
1640 case VPInstruction::StepVector:
1641 case VPInstruction::ReductionStartVector:
1642 case VPInstruction::Reverse:
1643 case VPInstruction::Unpack:
1644 return false;
1645 case VPInstruction::Intrinsic: {
1646 LLVMContext &Ctx = getScalarType()->getContext();
1647 AttributeSet Attrs =
1648 Intrinsic::getFnAttributes(C&: Ctx, id: vputils::getIntrinsicID(R: this));
1649 return !Attrs.getMemoryEffects().doesNotAccessMemory();
1650 }
1651 case Instruction::Call:
1652 return !getCalledFunction(Operands: ArrayRef<VPValue *>(op_begin(), op_end()))
1653 ->doesNotAccessMemory();
1654 default:
1655 return true;
1656 }
1657}
1658
1659bool VPInstruction::usesFirstLaneOnly(const VPValue *Op) const {
1660 assert(is_contained(operands(), Op) && "Op must be an operand of the recipe");
1661 if (Instruction::isBinaryOp(Opcode: getOpcode()) || Instruction::isCast(Opcode: getOpcode()))
1662 return vputils::onlyFirstLaneUsed(Def: this);
1663
1664 switch (getOpcode()) {
1665 default:
1666 return false;
1667 case Instruction::ExtractElement:
1668 return Op == getOperand(N: 1);
1669 case Instruction::InsertElement:
1670 return Op == getOperand(N: 1) || Op == getOperand(N: 2);
1671 case Instruction::PHI:
1672 return true;
1673 case Instruction::FCmp:
1674 case Instruction::ICmp:
1675 case Instruction::Select:
1676 case Instruction::Or:
1677 case Instruction::Freeze:
1678 case VPInstruction::Not:
1679 // TODO: Cover additional opcodes.
1680 return vputils::onlyFirstLaneUsed(Def: this);
1681 case Instruction::Load:
1682 case VPInstruction::ActiveLaneMask:
1683 case VPInstruction::ExplicitVectorLength:
1684 case VPInstruction::CalculateTripCountMinusVF:
1685 case VPInstruction::CanonicalIVIncrementForPart:
1686 case VPInstruction::BranchOnCount:
1687 case VPInstruction::BranchOnCond:
1688 case VPInstruction::BranchOnTwoConds:
1689 case VPInstruction::Broadcast:
1690 case VPInstruction::Intrinsic:
1691 case VPInstruction::ReductionStartVector:
1692 case VPInstruction::ResumeForEpilogue:
1693 return true;
1694 case VPInstruction::BuildStructVector:
1695 case VPInstruction::BuildVector:
1696 // Before replicating by VF, Build(Struct)Vector uses all lanes of the
1697 // operand, after replicating its operands only the first lane is used.
1698 // Before replicating, it will have only a single operand.
1699 return getNumOperands() > 1;
1700 case VPInstruction::PtrAdd:
1701 return Op == getOperand(N: 0) || vputils::onlyFirstLaneUsed(Def: this);
1702 case VPInstruction::WidePtrAdd:
1703 // WidePtrAdd supports scalar and vector base addresses.
1704 return false;
1705 case VPInstruction::ExitingIVValue:
1706 case VPInstruction::ExtractLane:
1707 return Op == getOperand(N: 0);
1708 };
1709 llvm_unreachable("switch should return");
1710}
1711
1712bool VPInstruction::usesFirstPartOnly(const VPValue *Op) const {
1713 assert(is_contained(operands(), Op) && "Op must be an operand of the recipe");
1714 if (Instruction::isBinaryOp(Opcode: getOpcode()))
1715 return vputils::onlyFirstPartUsed(Def: this);
1716
1717 switch (getOpcode()) {
1718 default:
1719 return false;
1720 case Instruction::FCmp:
1721 case Instruction::ICmp:
1722 case Instruction::Select:
1723 return vputils::onlyFirstPartUsed(Def: this);
1724 case VPInstruction::BranchOnCount:
1725 case VPInstruction::BranchOnCond:
1726 case VPInstruction::BranchOnTwoConds:
1727 case VPInstruction::CanonicalIVIncrementForPart:
1728 return true;
1729 };
1730 llvm_unreachable("switch should return");
1731}
1732
1733#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1734void VPInstruction::dump() const {
1735 VPSlotTracker SlotTracker(getParent()->getPlan());
1736 printRecipe(dbgs(), "", SlotTracker);
1737}
1738
1739void VPInstruction::printRecipe(raw_ostream &O, const Twine &Indent,
1740 VPSlotTracker &SlotTracker) const {
1741 O << Indent << "EMIT" << (isSingleScalar() ? "-SCALAR" : "") << " ";
1742
1743 if (hasResult()) {
1744 printAsOperand(O, SlotTracker);
1745 O << " = ";
1746 }
1747
1748 switch (getOpcode()) {
1749 case VPInstruction::Not:
1750 O << "not";
1751 break;
1752 case VPInstruction::ActiveLaneMask:
1753 O << "active lane mask";
1754 break;
1755 case VPInstruction::IncomingAliasMask:
1756 O << "incoming-alias-mask";
1757 break;
1758 case VPInstruction::ExplicitVectorLength:
1759 O << "EXPLICIT-VECTOR-LENGTH";
1760 break;
1761 case VPInstruction::FirstOrderRecurrenceSplice:
1762 O << "first-order splice";
1763 break;
1764 case VPInstruction::BranchOnCond:
1765 O << "branch-on-cond";
1766 break;
1767 case VPInstruction::BranchOnTwoConds:
1768 O << "branch-on-two-conds";
1769 break;
1770 case VPInstruction::CalculateTripCountMinusVF:
1771 O << "TC > VF ? TC - VF : 0";
1772 break;
1773 case VPInstruction::CanonicalIVIncrementForPart:
1774 O << "VF * Part +";
1775 break;
1776 case VPInstruction::BranchOnCount:
1777 O << "branch-on-count";
1778 break;
1779 case VPInstruction::Broadcast:
1780 O << "broadcast";
1781 break;
1782 case VPInstruction::BuildStructVector:
1783 O << "buildstructvector";
1784 break;
1785 case VPInstruction::BuildVector:
1786 O << "buildvector";
1787 break;
1788 case VPInstruction::ExitingIVValue:
1789 O << "exiting-iv-value";
1790 break;
1791 case VPInstruction::MaskedCond:
1792 O << "masked-cond";
1793 break;
1794 case VPInstruction::ExtractLane:
1795 O << "extract-lane";
1796 break;
1797 case VPInstruction::ExtractLastLane:
1798 O << "extract-last-lane";
1799 break;
1800 case VPInstruction::ExtractLastPart:
1801 O << "extract-last-part";
1802 break;
1803 case VPInstruction::ExtractPenultimateElement:
1804 O << "extract-penultimate-element";
1805 break;
1806 case VPInstruction::ComputeReductionResult:
1807 O << "compute-reduction-result";
1808 break;
1809 case VPInstruction::LogicalAnd:
1810 O << "logical-and";
1811 break;
1812 case VPInstruction::LogicalOr:
1813 O << "logical-or";
1814 break;
1815 case VPInstruction::PtrAdd:
1816 O << "ptradd";
1817 break;
1818 case VPInstruction::WidePtrAdd:
1819 O << "wide-ptradd";
1820 break;
1821 case VPInstruction::AnyOf:
1822 O << "any-of";
1823 break;
1824 case VPInstruction::FirstActiveLane:
1825 O << "first-active-lane";
1826 break;
1827 case VPInstruction::LastActiveLane:
1828 O << "last-active-lane";
1829 break;
1830 case VPInstruction::ReductionStartVector:
1831 O << "reduction-start-vector";
1832 break;
1833 case VPInstruction::ResumeForEpilogue:
1834 O << "resume-for-epilogue";
1835 break;
1836 case VPInstruction::Reverse:
1837 O << "reverse";
1838 break;
1839 case VPInstruction::Unpack:
1840 O << "unpack";
1841 break;
1842 case VPInstruction::ExtractLastActive:
1843 O << "extract-last-active";
1844 break;
1845 case VPInstruction::NumActiveLanes:
1846 O << "num-active-lanes";
1847 break;
1848 default:
1849 O << Instruction::getOpcodeName(getOpcode());
1850 }
1851
1852 printFlags(O);
1853 printOperands(O, SlotTracker);
1854}
1855#endif
1856
1857void VPInstructionWithType::execute(VPTransformState &State) {
1858 Type *ResultTy = getResultType();
1859 if (Instruction::isCast(Opcode: getOpcode())) {
1860 Value *Op = State.get(Def: getOperand(N: 0), Lane: VPLane(0));
1861 Value *Cast = State.Builder.CreateCast(Op: Instruction::CastOps(getOpcode()),
1862 V: Op, DestTy: ResultTy);
1863 if (auto *CastOp = dyn_cast<Instruction>(Val: Cast)) {
1864 applyFlags(I&: *CastOp);
1865 applyMetadata(I&: *CastOp);
1866 }
1867 State.set(Def: this, V: Cast, Lane: VPLane(0));
1868 return;
1869 }
1870 switch (getOpcode()) {
1871 case VPInstruction::StepVector: {
1872 Value *StepVector =
1873 State.Builder.CreateStepVector(DstType: VectorType::get(ElementType: ResultTy, EC: State.VF));
1874 State.set(Def: this, V: StepVector);
1875 break;
1876 }
1877 case VPInstruction::Intrinsic: {
1878 SmallVector<Value *, 2> Args;
1879 for (VPValue *Op : drop_end(RangeOrContainer: operands()))
1880 Args.push_back(Elt: State.get(Def: Op, /*IsSingleScalar=*/IsScalar: true));
1881 Value *Call =
1882 State.Builder.CreateIntrinsic(RetTy: ResultTy, ID: vputils::getIntrinsicID(R: this),
1883 Args, /*FMFSource=*/nullptr, Name: getName());
1884 State.set(Def: this, V: Call, IsScalar: true);
1885 break;
1886 }
1887
1888 default:
1889 llvm_unreachable("opcode not implemented yet");
1890 }
1891}
1892
1893InstructionCost VPInstructionWithType::computeCost(ElementCount VF,
1894 VPCostContext &Ctx) const {
1895 // NOTE: At the moment it seems only possible to expose this path for
1896 // the trunc, zext and sext opcodes. However, isScalarCast also covers
1897 // int<>fp conversions, bitcasts, ptr<>int conversions, etc.
1898 if (Instruction::isCast(Opcode: getOpcode()))
1899 return getCostForRecipeWithOpcode(Opcode: getOpcode(), VF: ElementCount::getFixed(MinVal: 1),
1900 Ctx);
1901
1902 switch (getOpcode()) {
1903 case VPInstruction::StepVector:
1904 // TODO: This isn't quite right since even if the step-vector is hoisted
1905 // out of the loop it has a non-zero cost in the middle block, etc.
1906 // Once the stepvector is correctly hoisted out of the vector loop by the
1907 // licm transform we can add the cost here so that it doesn't incorrectly
1908 // affect the choice of VF.
1909 return 0;
1910 case VPInstruction::Intrinsic: {
1911 Type *Ty = getScalarType();
1912 SmallVector<Type *, 2> ArgTys;
1913 for (const VPValue *Op : drop_end(RangeOrContainer: operands()))
1914 ArgTys.push_back(Elt: Op->getScalarType());
1915 IntrinsicCostAttributes Attrs(vputils::getIntrinsicID(R: this), Ty, ArgTys);
1916 return Ctx.TTI.getIntrinsicInstrCost(ICA: Attrs, CostKind: Ctx.CostKind);
1917 }
1918 default:
1919 // Although VPInstructionWithType is also used for
1920 // VPInstruction::WideIVStep it isn't currently possible to expose cases
1921 // where the cost is queried.
1922 llvm_unreachable("Unhandled opcode");
1923 }
1924 return 0;
1925}
1926
1927#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1928void VPInstructionWithType::printRecipe(raw_ostream &O, const Twine &Indent,
1929 VPSlotTracker &SlotTracker) const {
1930 O << Indent << "EMIT" << (isSingleScalar() ? "-SCALAR" : "") << " ";
1931 printAsOperand(O, SlotTracker);
1932 O << " = ";
1933
1934 Type *ResultTy = getResultType();
1935 switch (getOpcode()) {
1936 case VPInstruction::WideIVStep:
1937 O << "wide-iv-step ";
1938 printOperands(O, SlotTracker);
1939 break;
1940 case VPInstruction::StepVector:
1941 O << "step-vector " << *ResultTy;
1942 break;
1943 case VPInstruction::Intrinsic: {
1944 O << "call " << *ResultTy << " @"
1945 << Intrinsic::getBaseName(vputils::getIntrinsicID(this)) << "(";
1946 interleaveComma(drop_end(operands()), O, [&O, &SlotTracker](VPValue *Op) {
1947 Op->printAsOperand(O, SlotTracker);
1948 });
1949 O << ")";
1950 break;
1951 }
1952 case Instruction::Load:
1953 O << "load ";
1954 printOperands(O, SlotTracker);
1955 break;
1956 default:
1957 assert(Instruction::isCast(getOpcode()) && "unhandled opcode");
1958 O << Instruction::getOpcodeName(getOpcode());
1959 printFlags(O);
1960 printOperands(O, SlotTracker);
1961 O << " to " << *ResultTy;
1962 }
1963}
1964#endif
1965
1966/// Shared execute logic for VPPhi and VPWidenPHIRecipe. Creates a PHI node,
1967/// adds incoming values, and stores the result in State. For header phis, only
1968/// the preheader incoming value is added; the backedge is fixed up later by
1969/// VPlan::execute().
1970static void executePhiRecipe(VPSingleDefRecipe *R, VPPhiAccessors &Phi,
1971 VPTransformState &State, bool IsScalar,
1972 const Twine &Name) {
1973 unsigned NumIncoming = VPBlockUtils::isHeader(VPB: R->getParent(), VPDT: State.VPDT)
1974 ? 1
1975 : Phi.getNumIncoming();
1976 Value *FirstInc = State.get(Def: Phi.getIncomingValue(Idx: 0), IsScalar);
1977 PHINode *NewPhi = State.Builder.CreatePHI(Ty: FirstInc->getType(), NumReservedValues: 2, Name);
1978 NewPhi->addIncoming(V: FirstInc,
1979 BB: State.CFG.VPBB2IRBB.at(Val: Phi.getIncomingBlock(Idx: 0)));
1980 for (unsigned Idx = 1; Idx != NumIncoming; ++Idx)
1981 NewPhi->addIncoming(V: State.get(Def: Phi.getIncomingValue(Idx), IsScalar),
1982 BB: State.CFG.VPBB2IRBB.at(Val: Phi.getIncomingBlock(Idx)));
1983 State.set(Def: R, V: NewPhi, IsScalar);
1984}
1985
1986void VPPhi::execute(VPTransformState &State) {
1987 executePhiRecipe(R: this, Phi&: *this, State, /*IsScalar=*/true, Name: getName());
1988}
1989
1990#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1991void VPPhi::printRecipe(raw_ostream &O, const Twine &Indent,
1992 VPSlotTracker &SlotTracker) const {
1993 O << Indent << "EMIT" << (isSingleScalar() ? "-SCALAR" : "") << " ";
1994 printAsOperand(O, SlotTracker);
1995 O << " = phi";
1996 printFlags(O);
1997 printPhiOperands(O, SlotTracker);
1998}
1999#endif
2000
2001VPIRInstruction *VPIRInstruction ::create(Instruction &I) {
2002 if (auto *Phi = dyn_cast<PHINode>(Val: &I))
2003 return new VPIRPhi(*Phi);
2004 return new VPIRInstruction(I);
2005}
2006
2007void VPIRInstruction::execute(VPTransformState &State) {
2008 assert(!isa<VPIRPhi>(this) && getNumOperands() == 0 &&
2009 "PHINodes must be handled by VPIRPhi");
2010 // Advance the insert point after the wrapped IR instruction. This allows
2011 // interleaving VPIRInstructions and other recipes.
2012 State.Builder.SetInsertPoint(TheBB: I.getParent(), IP: std::next(x: I.getIterator()));
2013}
2014
2015InstructionCost VPIRInstruction::computeCost(ElementCount VF,
2016 VPCostContext &Ctx) const {
2017 // The recipe wraps an existing IR instruction on the border of VPlan's scope,
2018 // hence it does not contribute to the cost-modeling for the VPlan.
2019 return 0;
2020}
2021
2022#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2023void VPIRInstruction::printRecipe(raw_ostream &O, const Twine &Indent,
2024 VPSlotTracker &SlotTracker) const {
2025 O << Indent << "IR " << I;
2026}
2027#endif
2028
2029void VPIRPhi::execute(VPTransformState &State) {
2030 PHINode *Phi = &getIRPhi();
2031 for (const auto &[Idx, Op] : enumerate(First: operands())) {
2032 VPValue *ExitValue = Op;
2033 auto Lane = vputils::isSingleScalar(VPV: ExitValue)
2034 ? VPLane::getFirstLane()
2035 : VPLane::getLastLaneForVF(VF: State.VF);
2036 VPBlockBase *Pred = getParent()->getPredecessors()[Idx];
2037 auto *PredVPBB = Pred->getExitingBasicBlock();
2038 BasicBlock *PredBB = State.CFG.VPBB2IRBB[PredVPBB];
2039 // Set insertion point in PredBB in case an extract needs to be generated.
2040 // TODO: Model extracts explicitly.
2041 State.Builder.SetInsertPoint(PredBB->getTerminator());
2042 Value *V = State.get(Def: ExitValue, Lane: VPLane(Lane));
2043 // If there is no existing block for PredBB in the phi, add a new incoming
2044 // value. Otherwise update the existing incoming value for PredBB.
2045 if (Phi->getBasicBlockIndex(BB: PredBB) == -1)
2046 Phi->addIncoming(V, BB: PredBB);
2047 else
2048 Phi->setIncomingValueForBlock(BB: PredBB, V);
2049 }
2050
2051 // Advance the insert point after the wrapped IR instruction. This allows
2052 // interleaving VPIRInstructions and other recipes.
2053 State.Builder.SetInsertPoint(TheBB: Phi->getParent(), IP: std::next(x: Phi->getIterator()));
2054}
2055
2056void VPPhiAccessors::removeIncomingValueFor(VPBlockBase *IncomingBlock) const {
2057 VPRecipeBase *R = const_cast<VPRecipeBase *>(getAsRecipe());
2058 assert(R->getNumOperands() == R->getParent()->getNumPredecessors() &&
2059 "Number of phi operands must match number of predecessors");
2060 unsigned Position = R->getParent()->getIndexForPredecessor(Pred: IncomingBlock);
2061 R->removeOperand(Idx: Position);
2062}
2063
2064VPValue *
2065VPPhiAccessors::getIncomingValueForBlock(const VPBasicBlock *VPBB) const {
2066 VPRecipeBase *R = const_cast<VPRecipeBase *>(getAsRecipe());
2067 return getIncomingValue(Idx: R->getParent()->getIndexForPredecessor(Pred: VPBB));
2068}
2069
2070void VPPhiAccessors::setIncomingValueForBlock(const VPBasicBlock *VPBB,
2071 VPValue *V) const {
2072 VPRecipeBase *R = const_cast<VPRecipeBase *>(getAsRecipe());
2073 R->setOperand(I: R->getParent()->getIndexForPredecessor(Pred: VPBB), New: V);
2074}
2075
2076#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2077void VPPhiAccessors::printPhiOperands(raw_ostream &O,
2078 VPSlotTracker &SlotTracker) const {
2079 interleaveComma(incoming_values_and_blocks(), O, [&O, &SlotTracker](auto Op) {
2080 O << "[ ";
2081 std::get<0>(Op)->printAsOperand(O, SlotTracker);
2082 O << ", ";
2083 std::get<1>(Op)->printAsOperand(O);
2084 O << " ]";
2085 });
2086}
2087#endif
2088
2089#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2090void VPIRPhi::printRecipe(raw_ostream &O, const Twine &Indent,
2091 VPSlotTracker &SlotTracker) const {
2092 VPIRInstruction::printRecipe(O, Indent, SlotTracker);
2093
2094 if (getNumOperands() != 0) {
2095 O << " (extra operand" << (getNumOperands() > 1 ? "s" : "") << ": ";
2096 interleaveComma(incoming_values_and_blocks(), O,
2097 [&O, &SlotTracker](auto Op) {
2098 std::get<0>(Op)->printAsOperand(O, SlotTracker);
2099 O << " from ";
2100 std::get<1>(Op)->printAsOperand(O);
2101 });
2102 O << ")";
2103 }
2104}
2105#endif
2106
2107void VPIRMetadata::applyMetadata(Instruction &I) const {
2108 for (const auto &[Kind, Node] : Metadata)
2109 I.setMetadata(KindID: Kind, Node);
2110}
2111
2112void VPIRMetadata::intersect(const VPIRMetadata &Other) {
2113 SmallVector<std::pair<unsigned, MDNode *>> MetadataIntersection;
2114 for (const auto &[KindA, MDA] : Metadata) {
2115 for (const auto &[KindB, MDB] : Other.Metadata) {
2116 if (KindA == KindB && MDA == MDB) {
2117 MetadataIntersection.emplace_back(Args: KindA, Args: MDA);
2118 break;
2119 }
2120 }
2121 }
2122 Metadata = std::move(MetadataIntersection);
2123}
2124
2125#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2126void VPIRMetadata::print(raw_ostream &O, VPSlotTracker &SlotTracker) const {
2127 const Module *M = SlotTracker.getModule();
2128 if (Metadata.empty() || !M || !VPlanPrintMetadata)
2129 return;
2130
2131 ArrayRef<StringRef> MDNames = SlotTracker.getMDNames();
2132 O << " (";
2133 interleaveComma(Metadata, O, [&](const auto &KindNodePair) {
2134 auto [Kind, Node] = KindNodePair;
2135 assert(Kind < MDNames.size() && !MDNames[Kind].empty() &&
2136 "Unexpected unnamed metadata kind");
2137 O << "!" << MDNames[Kind] << " ";
2138 Node->printAsOperand(O, M);
2139 });
2140 O << ")";
2141}
2142#endif
2143
2144void VPWidenCallRecipe::execute(VPTransformState &State) {
2145 assert(State.VF.isVector() && "not widening");
2146 assert(Variant != nullptr && "Can't create vector function.");
2147
2148 FunctionType *VFTy = Variant->getFunctionType();
2149 // Add return type if intrinsic is overloaded on it.
2150 SmallVector<Value *, 4> Args;
2151 for (const auto &I : enumerate(First: args())) {
2152 Value *Arg;
2153 // Some vectorized function variants may also take a scalar argument,
2154 // e.g. linear parameters for pointers. This needs to be the scalar value
2155 // from the start of the respective part when interleaving.
2156 if (!VFTy->getParamType(i: I.index())->isVectorTy())
2157 Arg = State.get(Def: I.value(), Lane: VPLane(0));
2158 else
2159 Arg = State.get(Def: I.value(), IsScalar: usesFirstLaneOnly(Op: I.value()));
2160 Args.push_back(Elt: Arg);
2161 }
2162
2163 auto *CI = cast_or_null<CallInst>(Val: getUnderlyingValue());
2164 SmallVector<OperandBundleDef, 1> OpBundles;
2165 if (CI)
2166 CI->getOperandBundlesAsDefs(Defs&: OpBundles);
2167
2168 CallInst *V = State.Builder.CreateCall(Callee: Variant, Args, OpBundles);
2169 applyFlags(I&: *V);
2170 applyMetadata(I&: *V);
2171 V->setCallingConv(Variant->getCallingConv());
2172
2173 if (!V->getType()->isVoidTy())
2174 State.set(Def: this, V);
2175}
2176
2177InstructionCost VPWidenCallRecipe::computeCost(ElementCount VF,
2178 VPCostContext &Ctx) const {
2179 assert(getVectorizedTypeVF(Variant->getReturnType()) == VF &&
2180 "Variant return type must match VF");
2181 return computeCallCost(Variant, Ctx);
2182}
2183
2184InstructionCost VPWidenCallRecipe::computeCallCost(Function *Variant,
2185 VPCostContext &Ctx) {
2186 return Ctx.TTI.getCallInstrCost(F: nullptr, RetTy: Variant->getReturnType(),
2187 Tys: Variant->getFunctionType()->params(),
2188 CostKind: Ctx.CostKind);
2189}
2190
2191bool VPWidenCallRecipe::usesFirstLaneOnly(const VPValue *Op) const {
2192 assert(is_contained(operands(), Op) && "Op must be an operand of the recipe");
2193 assert(Variant && "Variant not set");
2194 FunctionType *VFTy = Variant->getFunctionType();
2195 return all_of(Range: enumerate(First: args()), P: [VFTy, &Op](const auto &Arg) {
2196 auto [Idx, V] = Arg;
2197 Type *ArgTy = VFTy->getParamType(i: Idx);
2198 return V != Op || ArgTy->isIntegerTy() || ArgTy->isFloatingPointTy() ||
2199 ArgTy->isPointerTy() || ArgTy->isByteTy();
2200 });
2201}
2202
2203#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2204void VPWidenCallRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
2205 VPSlotTracker &SlotTracker) const {
2206 O << Indent << "WIDEN-CALL ";
2207
2208 Function *CalledFn = getCalledScalarFunction();
2209 if (CalledFn->getReturnType()->isVoidTy())
2210 O << "void ";
2211 else {
2212 printAsOperand(O, SlotTracker);
2213 O << " = ";
2214 }
2215
2216 O << "call";
2217 printFlags(O);
2218 O << " @" << CalledFn->getName() << "(";
2219 interleaveComma(args(), O, [&O, &SlotTracker](VPValue *Op) {
2220 Op->printAsOperand(O, SlotTracker);
2221 });
2222 O << ")";
2223
2224 O << " (using library function";
2225 if (Variant->hasName())
2226 O << ": " << Variant->getName();
2227 O << ")";
2228}
2229#endif
2230
2231CallInst *VPWidenIntrinsicRecipe::createVectorCall(VPTransformState &State) {
2232 assert(State.VF.isVector() && "not widening");
2233
2234 SmallVector<Type *, 2> TysForDecl;
2235 // Add return type if intrinsic is overloaded on it.
2236 if (isVectorIntrinsicWithOverloadTypeAtArg(ID: VectorIntrinsicID, OpdIdx: -1,
2237 TTI: State.TTI)) {
2238 Type *RetTy = toVectorizedTy(Ty: getScalarType(), EC: State.VF);
2239 ArrayRef<Type *> ContainedTys = getContainedTypes(Ty: RetTy);
2240 for (auto [Idx, Ty] : enumerate(First&: ContainedTys)) {
2241 if (isVectorIntrinsicWithStructReturnOverloadAtField(ID: VectorIntrinsicID,
2242 RetIdx: Idx, TTI: State.TTI))
2243 TysForDecl.push_back(Elt: Ty);
2244 }
2245 }
2246 SmallVector<Value *, 4> Args;
2247 for (const auto &I : enumerate(First: operands())) {
2248 // Some intrinsics have a scalar argument - don't replace it with a
2249 // vector.
2250 Value *Arg;
2251 if (isVectorIntrinsicWithScalarOpAtArg(ID: VectorIntrinsicID, ScalarOpdIdx: I.index(),
2252 TTI: State.TTI))
2253 Arg = State.get(Def: I.value(), Lane: VPLane(0));
2254 else
2255 Arg = State.get(Def: I.value(), IsScalar: usesFirstLaneOnly(Op: I.value()));
2256 if (isVectorIntrinsicWithOverloadTypeAtArg(ID: VectorIntrinsicID, OpdIdx: I.index(),
2257 TTI: State.TTI))
2258 TysForDecl.push_back(Elt: Arg->getType());
2259 Args.push_back(Elt: Arg);
2260 }
2261
2262 // Use vector version of the intrinsic.
2263 Module *M = State.Builder.GetInsertBlock()->getModule();
2264 Function *VectorF =
2265 Intrinsic::getOrInsertDeclaration(M, id: VectorIntrinsicID, OverloadTys: TysForDecl);
2266 assert(VectorF &&
2267 "Can't retrieve vector intrinsic or vector-predication intrinsics.");
2268
2269 auto *CI = cast_or_null<CallInst>(Val: getUnderlyingValue());
2270 SmallVector<OperandBundleDef, 1> OpBundles;
2271 if (CI)
2272 CI->getOperandBundlesAsDefs(Defs&: OpBundles);
2273
2274 CallInst *V = State.Builder.CreateCall(Callee: VectorF, Args, OpBundles);
2275
2276 applyFlags(I&: *V);
2277 applyMetadata(I&: *V);
2278
2279 return V;
2280}
2281
2282void VPWidenIntrinsicRecipe::execute(VPTransformState &State) {
2283 CallInst *V = createVectorCall(State);
2284 if (!V->getType()->isVoidTy())
2285 State.set(Def: this, V);
2286}
2287
2288InstructionCost VPWidenIntrinsicRecipe::computeCallCost(
2289 Intrinsic::ID ID, ArrayRef<const VPValue *> Operands,
2290 const VPRecipeWithIRFlags &R, ElementCount VF, VPCostContext &Ctx) {
2291 Type *ScalarRetTy = R.getScalarType();
2292 // Skip the reverse operation cost for the mask.
2293 // FIXME: Remove this once redundant mask reverse operations can be eliminated
2294 // by VPlanTransforms::cse before cost computation.
2295 if (ID == Intrinsic::experimental_vp_reverse && ScalarRetTy->isIntegerTy(BitWidth: 1))
2296 return InstructionCost(0);
2297
2298 // Some backends analyze intrinsic arguments to determine cost. Use the
2299 // underlying value for the operand if it has one. Otherwise try to use the
2300 // operand of the underlying call instruction, if there is one. Otherwise
2301 // clear Arguments.
2302 // TODO: Rework TTI interface to be independent of concrete IR values.
2303 SmallVector<const Value *> Arguments;
2304 for (const auto &[Idx, Op] : enumerate(First&: Operands)) {
2305 auto *V = Op->getUnderlyingValue();
2306 if (!V) {
2307 if (auto *UI = dyn_cast_or_null<CallBase>(Val: R.getUnderlyingValue())) {
2308 Arguments.push_back(Elt: UI->getArgOperand(i: Idx));
2309 continue;
2310 }
2311 Arguments.clear();
2312 break;
2313 }
2314 Arguments.push_back(Elt: V);
2315 }
2316
2317 Type *RetTy = VF.isVector() ? toVectorizedTy(Ty: ScalarRetTy, EC: VF) : ScalarRetTy;
2318 SmallVector<Type *> ParamTys =
2319 map_to_vector(C&: Operands, F: [&](const VPValue *Op) {
2320 return toVectorTy(Scalar: Op->getScalarType(), EC: VF);
2321 });
2322
2323 VectorInstrContext VIC = VectorInstrContext::None;
2324 for (const VPValue *Op : Operands)
2325 if (isa<VPWidenRecipe>(Val: Op) &&
2326 Instruction::isBinaryOp(Opcode: cast<VPWidenRecipe>(Val: Op)->getOpcode())) {
2327 VIC = VectorInstrContext::BinaryOp;
2328 break;
2329 }
2330
2331 // TODO: Rework TTI interface to avoid reliance on underlying IntrinsicInst.
2332 IntrinsicCostAttributes CostAttrs(
2333 ID, RetTy, Arguments, ParamTys, R.getFastMathFlagsOrNone(),
2334 dyn_cast_or_null<IntrinsicInst>(Val: R.getUnderlyingValue()),
2335 InstructionCost::getInvalid(), VIC);
2336 return Ctx.TTI.getIntrinsicInstrCost(ICA: CostAttrs, CostKind: Ctx.CostKind);
2337}
2338
2339InstructionCost VPWidenIntrinsicRecipe::computeCost(ElementCount VF,
2340 VPCostContext &Ctx) const {
2341 return computeCallCost(ID: VectorIntrinsicID, Operands: operands(), R: *this, VF, Ctx);
2342}
2343
2344StringRef VPWidenIntrinsicRecipe::getIntrinsicName() const {
2345 return Intrinsic::getBaseName(id: VectorIntrinsicID);
2346}
2347
2348bool VPWidenIntrinsicRecipe::usesFirstLaneOnly(const VPValue *Op) const {
2349 assert(is_contained(operands(), Op) && "Op must be an operand of the recipe");
2350 return all_of(Range: enumerate(First: operands()), P: [this, &Op](const auto &X) {
2351 auto [Idx, V] = X;
2352 return V != Op || isVectorIntrinsicWithScalarOpAtArg(getVectorIntrinsicID(),
2353 Idx, nullptr);
2354 });
2355}
2356
2357#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2358void VPWidenIntrinsicRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
2359 VPSlotTracker &SlotTracker) const {
2360 O << Indent << "WIDEN-INTRINSIC ";
2361 if (getScalarType()->isVoidTy()) {
2362 O << "void ";
2363 } else {
2364 printAsOperand(O, SlotTracker);
2365 O << " = ";
2366 }
2367
2368 O << "call";
2369 printFlags(O);
2370 O << getIntrinsicName() << "(";
2371 printOperands(O, SlotTracker);
2372 O << ")";
2373}
2374#endif
2375
2376void VPWidenMemIntrinsicRecipe::execute(VPTransformState &State) {
2377 CallInst *MemI = createVectorCall(State);
2378 MemI->addParamAttr(
2379 ArgNo: 0, Attr: Attribute::getWithAlignment(Context&: MemI->getContext(), Alignment));
2380 State.set(Def: this, V: MemI);
2381}
2382
2383InstructionCost VPWidenMemIntrinsicRecipe::computeMemIntrinsicCost(
2384 Intrinsic::ID IID, Type *Ty, bool IsMasked, Align Alignment,
2385 VPCostContext &Ctx) {
2386 return Ctx.TTI.getMemIntrinsicInstrCost(
2387 MICA: MemIntrinsicCostAttributes(IID, Ty, /*Ptr=*/nullptr, IsMasked, Alignment),
2388 CostKind: Ctx.CostKind);
2389}
2390
2391InstructionCost
2392VPWidenMemIntrinsicRecipe::computeCost(ElementCount VF,
2393 VPCostContext &Ctx) const {
2394 Type *Ty = toVectorTy(Scalar: getScalarType(), EC: VF);
2395 return computeMemIntrinsicCost(IID: getVectorIntrinsicID(), Ty,
2396 IsMasked: !match(V: getOperand(N: 2), P: m_True()), Alignment,
2397 Ctx);
2398}
2399
2400void VPHistogramRecipe::execute(VPTransformState &State) {
2401 IRBuilderBase &Builder = State.Builder;
2402
2403 Value *Address = State.get(Def: getOperand(N: 0));
2404 Value *IncAmt = State.get(Def: getOperand(N: 1), /*IsScalar=*/true);
2405 VectorType *VTy = cast<VectorType>(Val: Address->getType());
2406
2407 // The histogram intrinsic requires a mask even if the recipe doesn't;
2408 // if the mask operand was omitted then all lanes should be executed and
2409 // we just need to synthesize an all-true mask.
2410 Value *Mask = nullptr;
2411 if (VPValue *VPMask = getMask())
2412 Mask = State.get(Def: VPMask);
2413 else
2414 Mask =
2415 Builder.CreateVectorSplat(EC: VTy->getElementCount(), V: Builder.getInt1(V: 1));
2416
2417 // If this is a subtract, we want to invert the increment amount. We may
2418 // add a separate intrinsic in future, but for now we'll try this.
2419 if (Opcode == Instruction::Sub)
2420 IncAmt = Builder.CreateNeg(V: IncAmt);
2421 else
2422 assert(Opcode == Instruction::Add && "only add or sub supported for now");
2423
2424 Instruction *HistogramInst = State.Builder.CreateIntrinsicWithoutFolding(
2425 ID: Intrinsic::experimental_vector_histogram_add, OverloadTypes: {VTy, IncAmt->getType()},
2426 Args: {Address, IncAmt, Mask});
2427 applyMetadata(I&: *HistogramInst);
2428}
2429
2430InstructionCost VPHistogramRecipe::computeCost(ElementCount VF,
2431 VPCostContext &Ctx) const {
2432 // FIXME: Take the gather and scatter into account as well. For now we're
2433 // generating the same cost as the fallback path, but we'll likely
2434 // need to create a new TTI method for determining the cost, including
2435 // whether we can use base + vec-of-smaller-indices or just
2436 // vec-of-pointers.
2437 assert(VF.isVector() && "Invalid VF for histogram cost");
2438 Type *AddressTy = getOperand(N: 0)->getScalarType();
2439 VPValue *IncAmt = getOperand(N: 1);
2440 Type *IncTy = IncAmt->getScalarType();
2441 VectorType *VTy = VectorType::get(ElementType: IncTy, EC: VF);
2442
2443 // Assume that a non-constant update value (or a constant != 1) requires
2444 // a multiply, and add that into the cost.
2445 InstructionCost MulCost =
2446 Ctx.TTI.getArithmeticInstrCost(Opcode: Instruction::Mul, Ty: VTy, CostKind: Ctx.CostKind);
2447 if (match(V: IncAmt, P: m_One()))
2448 MulCost = TTI::TCC_Free;
2449
2450 // Find the cost of the histogram operation itself.
2451 Type *PtrTy = VectorType::get(ElementType: AddressTy, EC: VF);
2452 Type *MaskTy = VectorType::get(ElementType: Type::getInt1Ty(C&: Ctx.LLVMCtx), EC: VF);
2453 IntrinsicCostAttributes ICA(Intrinsic::experimental_vector_histogram_add,
2454 Type::getVoidTy(C&: Ctx.LLVMCtx),
2455 {PtrTy, IncTy, MaskTy});
2456
2457 // Add the costs together with the add/sub operation.
2458 return Ctx.TTI.getIntrinsicInstrCost(ICA, CostKind: Ctx.CostKind) + MulCost +
2459 Ctx.TTI.getArithmeticInstrCost(Opcode, Ty: VTy, CostKind: Ctx.CostKind);
2460}
2461
2462#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2463void VPHistogramRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
2464 VPSlotTracker &SlotTracker) const {
2465 O << Indent << "WIDEN-HISTOGRAM buckets: ";
2466 getOperand(0)->printAsOperand(O, SlotTracker);
2467
2468 if (Opcode == Instruction::Sub)
2469 O << ", dec: ";
2470 else {
2471 assert(Opcode == Instruction::Add);
2472 O << ", inc: ";
2473 }
2474 getOperand(1)->printAsOperand(O, SlotTracker);
2475
2476 if (VPValue *Mask = getMask()) {
2477 O << ", mask: ";
2478 Mask->printAsOperand(O, SlotTracker);
2479 }
2480}
2481#endif
2482
2483VPIRFlags::FastMathFlagsTy::FastMathFlagsTy(const FastMathFlags &FMF) {
2484 AllowReassoc = FMF.allowReassoc();
2485 NoNaNs = FMF.noNaNs();
2486 NoInfs = FMF.noInfs();
2487 NoSignedZeros = FMF.noSignedZeros();
2488 AllowReciprocal = FMF.allowReciprocal();
2489 AllowContract = FMF.allowContract();
2490 ApproxFunc = FMF.approxFunc();
2491}
2492
2493VPIRFlags VPIRFlags::getDefaultFlags(unsigned Opcode) {
2494 switch (Opcode) {
2495 case Instruction::Add:
2496 case Instruction::Sub:
2497 case Instruction::Mul:
2498 case Instruction::Shl:
2499 case VPInstruction::CanonicalIVIncrementForPart:
2500 return WrapFlagsTy(false, false);
2501 case Instruction::Trunc:
2502 return TruncFlagsTy(false, false);
2503 case Instruction::Or:
2504 return DisjointFlagsTy(false);
2505 case Instruction::AShr:
2506 case Instruction::LShr:
2507 case Instruction::UDiv:
2508 case Instruction::SDiv:
2509 return ExactFlagsTy(false);
2510 case Instruction::GetElementPtr:
2511 case VPInstruction::PtrAdd:
2512 case VPInstruction::WidePtrAdd:
2513 return GEPNoWrapFlags::none();
2514 case Instruction::ZExt:
2515 case Instruction::UIToFP:
2516 return NonNegFlagsTy(false);
2517 case Instruction::FAdd:
2518 case Instruction::FSub:
2519 case Instruction::FMul:
2520 case Instruction::FDiv:
2521 case Instruction::FRem:
2522 case Instruction::FNeg:
2523 case Instruction::FPExt:
2524 case Instruction::FPTrunc:
2525 return FastMathFlags();
2526 case Instruction::ICmp:
2527 case Instruction::FCmp:
2528 case VPInstruction::ComputeReductionResult:
2529 llvm_unreachable("opcode requires explicit flags");
2530 default:
2531 return VPIRFlags();
2532 }
2533}
2534
2535#if !defined(NDEBUG)
2536bool VPIRFlags::flagsValidForOpcode(unsigned Opcode) const {
2537 switch (OpType) {
2538 case OperationType::OverflowingBinOp:
2539 return Opcode == Instruction::Add || Opcode == Instruction::Sub ||
2540 Opcode == Instruction::Mul || Opcode == Instruction::Shl ||
2541 Opcode == VPInstruction::VPInstruction::CanonicalIVIncrementForPart;
2542 case OperationType::Trunc:
2543 return Opcode == Instruction::Trunc;
2544 case OperationType::DisjointOp:
2545 return Opcode == Instruction::Or;
2546 case OperationType::PossiblyExactOp:
2547 return Opcode == Instruction::AShr || Opcode == Instruction::LShr ||
2548 Opcode == Instruction::UDiv || Opcode == Instruction::SDiv;
2549 case OperationType::GEPOp:
2550 return Opcode == Instruction::GetElementPtr ||
2551 Opcode == VPInstruction::PtrAdd ||
2552 Opcode == VPInstruction::WidePtrAdd;
2553 case OperationType::FPMathOp:
2554 return Opcode == Instruction::Call || Opcode == Instruction::FAdd ||
2555 Opcode == Instruction::FMul || Opcode == Instruction::FSub ||
2556 Opcode == Instruction::FNeg || Opcode == Instruction::FDiv ||
2557 Opcode == Instruction::FRem || Opcode == Instruction::FPExt ||
2558 Opcode == Instruction::FPTrunc || Opcode == Instruction::PHI ||
2559 Opcode == Instruction::Select || Opcode == Instruction::SIToFP ||
2560 Opcode == Instruction::UIToFP ||
2561 Opcode == VPInstruction::WideIVStep ||
2562 Opcode == VPInstruction::ReductionStartVector;
2563 case OperationType::FCmp:
2564 return Opcode == Instruction::FCmp;
2565 case OperationType::NonNegOp:
2566 return Opcode == Instruction::ZExt || Opcode == Instruction::UIToFP;
2567 case OperationType::Cmp:
2568 return Opcode == Instruction::FCmp || Opcode == Instruction::ICmp;
2569 case OperationType::ReductionOp:
2570 return Opcode == VPInstruction::ComputeReductionResult;
2571 case OperationType::Other:
2572 return true;
2573 }
2574 llvm_unreachable("Unknown OperationType enum");
2575}
2576
2577bool VPIRFlags::hasRequiredFlagsForOpcode(unsigned Opcode) const {
2578 // Handle opcodes without default flags.
2579 if (Opcode == Instruction::ICmp)
2580 return OpType == OperationType::Cmp;
2581 if (Opcode == Instruction::FCmp)
2582 return OpType == OperationType::FCmp;
2583 if (Opcode == VPInstruction::ComputeReductionResult)
2584 return OpType == OperationType::ReductionOp;
2585
2586 OperationType Required = getDefaultFlags(Opcode).OpType;
2587 return Required == OperationType::Other || Required == OpType;
2588}
2589#endif
2590
2591#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2592static void printRecurrenceKind(raw_ostream &OS, const RecurKind &Kind) {
2593 switch (Kind) {
2594 case RecurKind::None:
2595 OS << "none";
2596 break;
2597 case RecurKind::Add:
2598 OS << "add";
2599 break;
2600 case RecurKind::Sub:
2601 OS << "sub";
2602 break;
2603 case RecurKind::AddChainWithSubs:
2604 OS << "add-chain-with-subs";
2605 break;
2606 case RecurKind::Mul:
2607 OS << "mul";
2608 break;
2609 case RecurKind::Or:
2610 OS << "or";
2611 break;
2612 case RecurKind::And:
2613 OS << "and";
2614 break;
2615 case RecurKind::Xor:
2616 OS << "xor";
2617 break;
2618 case RecurKind::SMin:
2619 OS << "smin";
2620 break;
2621 case RecurKind::SMax:
2622 OS << "smax";
2623 break;
2624 case RecurKind::UMin:
2625 OS << "umin";
2626 break;
2627 case RecurKind::UMax:
2628 OS << "umax";
2629 break;
2630 case RecurKind::FAdd:
2631 OS << "fadd";
2632 break;
2633 case RecurKind::FAddChainWithSubs:
2634 OS << "fadd-chain-with-subs";
2635 break;
2636 case RecurKind::FSub:
2637 OS << "fsub";
2638 break;
2639 case RecurKind::FMul:
2640 OS << "fmul";
2641 break;
2642 case RecurKind::FMin:
2643 OS << "fmin";
2644 break;
2645 case RecurKind::FMax:
2646 OS << "fmax";
2647 break;
2648 case RecurKind::FMinNum:
2649 OS << "fminnum";
2650 break;
2651 case RecurKind::FMaxNum:
2652 OS << "fmaxnum";
2653 break;
2654 case RecurKind::FMinimum:
2655 OS << "fminimum";
2656 break;
2657 case RecurKind::FMaximum:
2658 OS << "fmaximum";
2659 break;
2660 case RecurKind::FMinimumNum:
2661 OS << "fminimumnum";
2662 break;
2663 case RecurKind::FMaximumNum:
2664 OS << "fmaximumnum";
2665 break;
2666 case RecurKind::FMulAdd:
2667 OS << "fmuladd";
2668 break;
2669 case RecurKind::AnyOf:
2670 OS << "any-of";
2671 break;
2672 case RecurKind::FindIV:
2673 OS << "find-iv";
2674 break;
2675 case RecurKind::FindLast:
2676 OS << "find-last";
2677 break;
2678 }
2679}
2680
2681void VPIRFlags::printFlags(raw_ostream &O) const {
2682 switch (OpType) {
2683 case OperationType::Cmp:
2684 O << " " << CmpInst::getPredicateName(getPredicate());
2685 break;
2686 case OperationType::FCmp:
2687 O << " " << CmpInst::getPredicateName(getPredicate());
2688 getFastMathFlagsOrNone().print(O);
2689 break;
2690 case OperationType::DisjointOp:
2691 if (DisjointFlags.IsDisjoint)
2692 O << " disjoint";
2693 break;
2694 case OperationType::PossiblyExactOp:
2695 if (ExactFlags.IsExact)
2696 O << " exact";
2697 break;
2698 case OperationType::OverflowingBinOp:
2699 if (WrapFlags.HasNUW)
2700 O << " nuw";
2701 if (WrapFlags.HasNSW)
2702 O << " nsw";
2703 break;
2704 case OperationType::Trunc:
2705 if (TruncFlags.HasNUW)
2706 O << " nuw";
2707 if (TruncFlags.HasNSW)
2708 O << " nsw";
2709 break;
2710 case OperationType::FPMathOp:
2711 getFastMathFlagsOrNone().print(O);
2712 break;
2713 case OperationType::GEPOp: {
2714 GEPNoWrapFlags Flags = getGEPNoWrapFlags();
2715 if (Flags.isInBounds())
2716 O << " inbounds";
2717 else if (Flags.hasNoUnsignedSignedWrap())
2718 O << " nusw";
2719 if (Flags.hasNoUnsignedWrap())
2720 O << " nuw";
2721 break;
2722 }
2723 case OperationType::NonNegOp:
2724 if (NonNegFlags.NonNeg)
2725 O << " nneg";
2726 break;
2727 case OperationType::ReductionOp: {
2728 O << " (";
2729 printRecurrenceKind(O, getRecurKind());
2730 if (isReductionInLoop())
2731 O << ", in-loop";
2732 if (isReductionOrdered())
2733 O << ", ordered";
2734 O << ")";
2735 getFastMathFlagsOrNone().print(O);
2736 break;
2737 }
2738 case OperationType::Other:
2739 break;
2740 }
2741 O << " ";
2742}
2743#endif
2744
2745void VPWidenRecipe::execute(VPTransformState &State) {
2746 auto &Builder = State.Builder;
2747 switch (Opcode) {
2748 case Instruction::Call:
2749 case Instruction::UncondBr:
2750 case Instruction::CondBr:
2751 case Instruction::PHI:
2752 case Instruction::GetElementPtr:
2753 llvm_unreachable("This instruction is handled by a different recipe.");
2754 case Instruction::UDiv:
2755 case Instruction::SDiv:
2756 case Instruction::SRem:
2757 case Instruction::URem:
2758 case Instruction::Add:
2759 case Instruction::FAdd:
2760 case Instruction::Sub:
2761 case Instruction::FSub:
2762 case Instruction::FNeg:
2763 case Instruction::Mul:
2764 case Instruction::FMul:
2765 case Instruction::FDiv:
2766 case Instruction::FRem:
2767 case Instruction::Shl:
2768 case Instruction::LShr:
2769 case Instruction::AShr:
2770 case Instruction::And:
2771 case Instruction::Or:
2772 case Instruction::Xor: {
2773 // Just widen unops and binops.
2774 SmallVector<Value *, 2> Ops;
2775 for (VPValue *VPOp : operands())
2776 Ops.push_back(Elt: State.get(Def: VPOp));
2777
2778 Value *V = Builder.CreateNAryOp(Opc: Opcode, Ops);
2779
2780 if (auto *VecOp = dyn_cast<Instruction>(Val: V)) {
2781 applyFlags(I&: *VecOp);
2782 applyMetadata(I&: *VecOp);
2783 }
2784
2785 // Use this vector value for all users of the original instruction.
2786 State.set(Def: this, V);
2787 break;
2788 }
2789 case Instruction::ExtractValue: {
2790 assert(getNumOperands() == 2 && "expected single level extractvalue");
2791 Value *Op = State.get(Def: getOperand(N: 0));
2792 Value *Extract = Builder.CreateExtractValue(
2793 Agg: Op, Idxs: cast<VPConstantInt>(Val: getOperand(N: 1))->getZExtValue());
2794 State.set(Def: this, V: Extract);
2795 break;
2796 }
2797 case Instruction::Freeze: {
2798 Value *Op = State.get(Def: getOperand(N: 0));
2799 Value *Freeze = Builder.CreateFreeze(V: Op);
2800 State.set(Def: this, V: Freeze);
2801 break;
2802 }
2803 case Instruction::ICmp:
2804 case Instruction::FCmp: {
2805 // Widen compares. Generate vector compares.
2806 bool FCmp = Opcode == Instruction::FCmp;
2807 Value *A = State.get(Def: getOperand(N: 0));
2808 Value *B = State.get(Def: getOperand(N: 1));
2809 Value *C = nullptr;
2810 if (FCmp) {
2811 C = Builder.CreateFCmp(P: getPredicate(), LHS: A, RHS: B);
2812 } else {
2813 C = Builder.CreateICmp(P: getPredicate(), LHS: A, RHS: B);
2814 }
2815 if (auto *I = dyn_cast<Instruction>(Val: C)) {
2816 applyFlags(I&: *I);
2817 applyMetadata(I&: *I);
2818 }
2819 State.set(Def: this, V: C);
2820 break;
2821 }
2822 case Instruction::Select: {
2823 VPValue *CondOp = getOperand(N: 0);
2824 Value *Cond = State.get(Def: CondOp, IsScalar: vputils::isSingleScalar(VPV: CondOp));
2825 Value *Op0 = State.get(Def: getOperand(N: 1));
2826 Value *Op1 = State.get(Def: getOperand(N: 2));
2827 Value *Sel = State.Builder.CreateSelect(C: Cond, True: Op0, False: Op1);
2828 State.set(Def: this, V: Sel);
2829 if (auto *I = dyn_cast<Instruction>(Val: Sel)) {
2830 if (isa<FPMathOperator>(Val: I))
2831 applyFlags(I&: *I);
2832 applyMetadata(I&: *I);
2833 }
2834 break;
2835 }
2836 default:
2837 // This instruction is not vectorized by simple widening.
2838 LLVM_DEBUG(dbgs() << "LV: Found an unhandled opcode : "
2839 << Instruction::getOpcodeName(Opcode));
2840 llvm_unreachable("Unhandled instruction!");
2841 } // end of switch.
2842
2843#if !defined(NDEBUG)
2844 // Verify that VPlan type inference results agree with the type of the
2845 // generated values.
2846 assert(VectorType::get(this->getScalarType(), State.VF) ==
2847 State.get(this)->getType() &&
2848 "inferred type and type from generated instructions do not match");
2849#endif
2850}
2851
2852InstructionCost VPWidenRecipe::computeCost(ElementCount VF,
2853 VPCostContext &Ctx) const {
2854 switch (Opcode) {
2855 case Instruction::UDiv:
2856 case Instruction::SDiv:
2857 case Instruction::SRem:
2858 case Instruction::URem:
2859 // If the div/rem operation isn't safe to speculate and requires
2860 // predication, then the only way we can even create a vplan is to insert
2861 // a select on the second input operand to ensure we use the value of 1
2862 // for the inactive lanes. The select will be costed separately.
2863 case Instruction::FNeg:
2864 case Instruction::Add:
2865 case Instruction::FAdd:
2866 case Instruction::Sub:
2867 case Instruction::FSub:
2868 case Instruction::Mul:
2869 case Instruction::FMul:
2870 case Instruction::FDiv:
2871 case Instruction::FRem:
2872 case Instruction::Shl:
2873 case Instruction::LShr:
2874 case Instruction::AShr:
2875 case Instruction::And:
2876 case Instruction::Or:
2877 case Instruction::Xor:
2878 case Instruction::Freeze:
2879 case Instruction::ExtractValue:
2880 case Instruction::ICmp:
2881 case Instruction::FCmp:
2882 case Instruction::Select:
2883 return getCostForRecipeWithOpcode(Opcode: getOpcode(), VF, Ctx);
2884 default:
2885 llvm_unreachable("Unsupported opcode for instruction");
2886 }
2887}
2888
2889#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2890void VPWidenRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
2891 VPSlotTracker &SlotTracker) const {
2892 O << Indent << "WIDEN ";
2893 printAsOperand(O, SlotTracker);
2894 O << " = " << Instruction::getOpcodeName(Opcode);
2895 printFlags(O);
2896 printOperands(O, SlotTracker);
2897}
2898#endif
2899
2900void VPWidenCastRecipe::execute(VPTransformState &State) {
2901 auto &Builder = State.Builder;
2902 /// Vectorize casts.
2903 assert(State.VF.isVector() && "Not vectorizing?");
2904 Type *DestTy = VectorType::get(ElementType: getScalarType(), EC: State.VF);
2905 VPValue *Op = getOperand(N: 0);
2906 Value *A = State.get(Def: Op);
2907 Value *Cast = Builder.CreateCast(Op: Instruction::CastOps(Opcode), V: A, DestTy);
2908 State.set(Def: this, V: Cast);
2909 if (auto *CastOp = dyn_cast<Instruction>(Val: Cast)) {
2910 applyFlags(I&: *CastOp);
2911 applyMetadata(I&: *CastOp);
2912 }
2913}
2914
2915InstructionCost VPWidenCastRecipe::computeCost(ElementCount VF,
2916 VPCostContext &Ctx) const {
2917 return getCostForRecipeWithOpcode(Opcode: getOpcode(), VF, Ctx);
2918}
2919
2920#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2921void VPWidenCastRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
2922 VPSlotTracker &SlotTracker) const {
2923 O << Indent << "WIDEN-CAST ";
2924 printAsOperand(O, SlotTracker);
2925 O << " = " << Instruction::getOpcodeName(Opcode);
2926 printFlags(O);
2927 printOperands(O, SlotTracker);
2928 O << " to " << *getScalarType();
2929}
2930#endif
2931
2932InstructionCost VPHeaderPHIRecipe::computeCost(ElementCount VF,
2933 VPCostContext &Ctx) const {
2934 return Ctx.TTI.getCFInstrCost(Opcode: Instruction::PHI, CostKind: Ctx.CostKind);
2935}
2936
2937#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2938void VPWidenIntOrFpInductionRecipe::printRecipe(
2939 raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const {
2940 O << Indent;
2941 printAsOperand(O, SlotTracker);
2942 O << " = WIDEN-INDUCTION";
2943 printFlags(O);
2944 printOperands(O, SlotTracker);
2945
2946 if (auto *TI = getTruncInst())
2947 O << " (truncated to " << *TI->getType() << ")";
2948}
2949#endif
2950
2951bool VPWidenIntOrFpInductionRecipe::isCanonical() const {
2952 // The step may be defined by a recipe in the preheader (e.g. if it requires
2953 // SCEV expansion), but for the canonical induction the step is required to be
2954 // 1, which is represented as live-in.
2955 return match(V: getStartValue(), P: m_ZeroInt()) &&
2956 match(V: getStepValue(), P: m_One()) &&
2957 getScalarType() == getRegion()->getCanonicalIVType();
2958}
2959
2960InstructionCost VPDerivedIVRecipe::computeCost(ElementCount VF,
2961 VPCostContext &Ctx) const {
2962 // The cost model for this is modelled on expandVPDerivedIV in
2963 // VPlanTransforms.cpp. In order to avoid overly pessimistic costs that can
2964 // negatively affect vectorization it takes into account any expected
2965 // simplifications that happen in simplifyRecipe.
2966 switch (getInductionKind()) {
2967 default:
2968 // TODO: Compute cost for remaining kinds.
2969 break;
2970 case InductionDescriptor::IK_IntInduction: {
2971 // There are currently no tests that expose a path where all lanes are
2972 // used, so it's better to bail out for now.
2973 if (!vputils::onlyFirstLaneUsed(Def: this))
2974 break;
2975
2976 // Start off by assuming we need both mul and add, then refine this.
2977 bool NeedsMul = true, NeedsAdd = true, NeedsShl = false;
2978
2979 // If the start value is zero the add gets folded away.
2980 if (auto *StartC = dyn_cast<VPConstantInt>(Val: getStartValue()))
2981 NeedsAdd = !StartC->isZero();
2982
2983 // For some values of step the arithmetic changes:
2984 // 1. A step of 1 requires no operation.
2985 // 2. A step of -1 requires a negate.
2986 // 3. A power-of-2 step will use a shl, instead of a mul.
2987 Type *StepTy = getStepValue()->getScalarType();
2988 InstructionCost Cost(0);
2989 if (auto *StepC = dyn_cast<VPConstantInt>(Val: getStepValue())) {
2990 if (StepC->isOne())
2991 NeedsMul = false;
2992 else if (StepC->getAPInt().isAllOnes()) {
2993 // This will most likely end up as a negate in simplifyRecipe, and
2994 // the negate will be combined with the add to make a sub.
2995 // NOTE: This is perhaps an invalid assumption that the cost of an
2996 // 'add' is the same as a 'sub'.
2997 NeedsMul = false;
2998 NeedsAdd = true;
2999 } else if (StepC->getAPInt().isPowerOf2()) {
3000 // This will most likely end up as a shift-left in simplifyRecipe
3001 NeedsMul = false;
3002 NeedsShl = true;
3003 }
3004 }
3005
3006 // Add the cost of the conversion from index to step type if the index
3007 // will be used.
3008 Type *IndexTy = getIndex()->getScalarType();
3009 unsigned StepTySize = StepTy->getScalarSizeInBits();
3010 unsigned IndexTySize = IndexTy->getScalarSizeInBits();
3011 if ((NeedsAdd || NeedsMul || NeedsShl) && StepTySize != IndexTySize) {
3012 unsigned CastOpc =
3013 StepTySize < IndexTySize ? Instruction::Trunc : Instruction::SExt;
3014 Cost += Ctx.TTI.getCastInstrCost(
3015 Opcode: CastOpc, Dst: StepTy, Src: IndexTy, CCH: TTI::CastContextHint::None, CostKind: Ctx.CostKind);
3016 }
3017
3018 if (NeedsMul)
3019 Cost += Ctx.TTI.getArithmeticInstrCost(Opcode: Instruction::Mul, Ty: StepTy,
3020 CostKind: Ctx.CostKind);
3021 if (NeedsShl)
3022 Cost += Ctx.TTI.getArithmeticInstrCost(
3023 Opcode: Instruction::Shl, Ty: StepTy, CostKind: Ctx.CostKind,
3024 Opd1Info: {.Kind: TargetTransformInfo::OK_AnyValue, .Properties: TargetTransformInfo::OP_None},
3025 Opd2Info: {.Kind: TargetTransformInfo::OK_UniformConstantValue,
3026 .Properties: TargetTransformInfo::OP_None});
3027 if (NeedsAdd)
3028 Cost += Ctx.TTI.getArithmeticInstrCost(Opcode: Instruction::Add, Ty: StepTy,
3029 CostKind: Ctx.CostKind);
3030 return Cost;
3031 }
3032 }
3033
3034 return 0;
3035}
3036
3037#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3038void VPDerivedIVRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
3039 VPSlotTracker &SlotTracker) const {
3040 O << Indent;
3041 printAsOperand(O, SlotTracker);
3042 O << " = DERIVED-IV ";
3043 getStartValue()->printAsOperand(O, SlotTracker);
3044 O << " + ";
3045 getOperand(1)->printAsOperand(O, SlotTracker);
3046 O << " * ";
3047 getStepValue()->printAsOperand(O, SlotTracker);
3048}
3049#endif
3050
3051bool VPScalarIVStepsRecipe::doesGeneratePerAllLanes() const {
3052 return !vputils::onlyFirstLaneUsed(Def: this);
3053}
3054
3055InstructionCost VPScalarIVStepsRecipe::computeCost(ElementCount VF,
3056 VPCostContext &Ctx) const {
3057 // TODO: Add costs for floating point.
3058 Type *BaseIVTy = getOperand(N: 0)->getScalarType();
3059 if (!BaseIVTy->isIntegerTy())
3060 return 0;
3061
3062 // TODO: Add support for predicated regions. Requires scaling the cost by the
3063 // probability of entering the block.
3064 if (getRegion() && getRegion()->isReplicator())
3065 return 0;
3066
3067 // If only the first lane is used, then there won't be any code that remains
3068 // in the loop for the first unrolled part.
3069 if (vputils::onlyFirstLaneUsed(Def: this))
3070 return 0;
3071
3072 // Typically the operations are:
3073 // 1. Add the start index to each lane value.
3074 // 2. Multiply the start index by the step.
3075 // 3. Add the scaled start index to base IV.
3076 // Any code generated for 1 and 2 should be loop invariant and therefore
3077 // hoisted out of the loop. We only need to add on the cost of 3.
3078
3079 // Given the users of VPScalarIVStepsRecipe tend to be scalarized GEPs, i.e.
3080 // %add1 = add i32 %iv, 0
3081 // %add2 = add i32 %iv, 1
3082 // %gep1 = getelementptr i8, ptr %p, i32 %add1
3083 // %gep2 = getelementptr i8, ptr %p, i32 %add2
3084 // it's very likely that these GEPs will all be rewritten to have a common
3085 // base such that what's left is just
3086 // %base_gep = getelementptr i8, ptr %p, i32 %iv
3087 // %gep1 = getelementptr i8, ptr %base_gep, i32 0
3088 // %gep2 = getelementptr i8, ptr %base_gep, i32 1
3089 // Therefore, in reality the cost is somewhere betwen 1*AddCost and
3090 // (NumLanes - 1) * AddCost. For now, assume the cost of a single add.
3091 return Ctx.TTI.getArithmeticInstrCost(Opcode: Instruction::Add, Ty: BaseIVTy,
3092 CostKind: Ctx.CostKind);
3093}
3094
3095void VPScalarIVStepsRecipe::execute(VPTransformState &State) {
3096 // Fast-math-flags propagate from the original induction instruction.
3097 IRBuilder<>::FastMathFlagGuard FMFG(State.Builder);
3098 State.Builder.setFastMathFlags(getFastMathFlagsOrNone());
3099
3100 /// Compute scalar induction steps. \p ScalarIV is the scalar induction
3101 /// variable on which to base the steps, \p Step is the size of the step.
3102
3103 Value *BaseIV = State.get(Def: getOperand(N: 0), Lane: VPLane(0));
3104 Value *Step = State.get(Def: getStepValue(), Lane: VPLane(0));
3105 IRBuilderBase &Builder = State.Builder;
3106
3107 // Ensure step has the same type as that of scalar IV.
3108 Type *BaseIVTy = BaseIV->getType()->getScalarType();
3109 assert(BaseIVTy == Step->getType() && "Types of BaseIV and Step must match!");
3110
3111 // We build scalar steps for both integer and floating-point induction
3112 // variables. Here, we determine the kind of arithmetic we will perform.
3113 Instruction::BinaryOps AddOp;
3114 Instruction::BinaryOps MulOp;
3115 if (BaseIVTy->isIntegerTy()) {
3116 AddOp = Instruction::Add;
3117 MulOp = Instruction::Mul;
3118 } else {
3119 AddOp = InductionOpcode;
3120 MulOp = Instruction::FMul;
3121 }
3122
3123 // Determine the number of scalars we need to generate.
3124 bool FirstLaneOnly = vputils::onlyFirstLaneUsed(Def: this);
3125 // Compute the scalar steps and save the results in State.
3126
3127 unsigned EndLane = FirstLaneOnly ? 1 : State.VF.getKnownMinValue();
3128 Value *StartIdx0 = getStartIndex() ? State.get(Def: getStartIndex(), IsScalar: true)
3129 : Constant::getNullValue(Ty: BaseIVTy);
3130
3131 for (unsigned Lane = 0; Lane < EndLane; ++Lane) {
3132 // It is okay if the induction variable type cannot hold the lane number,
3133 // we expect truncation in this case.
3134 Constant *LaneValue =
3135 BaseIVTy->isIntegerTy()
3136 ? ConstantInt::get(Ty: BaseIVTy, V: Lane, /*IsSigned=*/false,
3137 /*ImplicitTrunc=*/true)
3138 : ConstantFP::get(Ty: BaseIVTy, V: Lane);
3139 Value *StartIdx = Builder.CreateBinOp(Opc: AddOp, LHS: StartIdx0, RHS: LaneValue);
3140 assert((State.VF.isScalable() || isa<Constant>(StartIdx)) &&
3141 "Expected StartIdx to be folded to a constant when VF is not "
3142 "scalable");
3143 auto *Mul = Builder.CreateBinOp(Opc: MulOp, LHS: StartIdx, RHS: Step);
3144 auto *Add = Builder.CreateBinOp(Opc: AddOp, LHS: BaseIV, RHS: Mul);
3145 State.set(Def: this, V: Add, Lane: VPLane(Lane));
3146 }
3147}
3148
3149#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3150void VPScalarIVStepsRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
3151 VPSlotTracker &SlotTracker) const {
3152 O << Indent;
3153 printAsOperand(O, SlotTracker);
3154 O << " = SCALAR-STEPS ";
3155 printOperands(O, SlotTracker);
3156}
3157#endif
3158
3159bool VPWidenGEPRecipe::usesFirstLaneOnly(const VPValue *Op) const {
3160 assert(is_contained(operands(), Op) && "Op must be an operand of the recipe");
3161 return vputils::isSingleScalar(VPV: Op);
3162}
3163
3164void VPWidenGEPRecipe::execute(VPTransformState &State) {
3165 assert(State.VF.isVector() && "not widening");
3166 auto Ops = map_to_vector(C: operands(), F: [&](VPValue *Op) {
3167 return State.get(Def: Op, IsScalar: vputils::isSingleScalar(VPV: Op));
3168 });
3169 auto *GEP =
3170 State.Builder.CreateGEP(Ty: getSourceElementType(), Ptr: Ops.front(),
3171 IdxList: drop_begin(RangeOrContainer&: Ops), Name: "wide.gep", NW: getGEPNoWrapFlags());
3172 State.set(Def: this, V: GEP, IsScalar: vputils::isSingleScalar(VPV: this));
3173}
3174
3175#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3176void VPWidenGEPRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
3177 VPSlotTracker &SlotTracker) const {
3178 O << Indent << "WIDEN-GEP ";
3179 printAsOperand(O, SlotTracker);
3180 O << " = getelementptr";
3181 printFlags(O);
3182 printOperands(O, SlotTracker);
3183}
3184#endif
3185
3186void VPVectorEndPointerRecipe::materializeOffset(unsigned Part) {
3187 assert(!getOffset() && "Unexpected offset operand");
3188 VPBuilder Builder(this);
3189 VPlan &Plan = *getParent()->getPlan();
3190 VPValue *VFVal = getVFValue();
3191 const DataLayout &DL = Plan.getDataLayout();
3192 Type *IndexTy = DL.getIndexType(PtrTy: this->getScalarType());
3193 VPValue *Stride =
3194 Plan.getConstantInt(Ty: IndexTy, Val: getStride(), /*IsSigned=*/true);
3195 VPValue *VF =
3196 Builder.createScalarZExtOrTrunc(Op: VFVal, ResultTy: IndexTy, DL: DebugLoc::getUnknown());
3197
3198 // Offset for Part0 = Offset0 = Stride * (VF - 1).
3199 VPInstruction *VFMinusOne =
3200 Builder.createSub(LHS: VF, RHS: Plan.getConstantInt(Ty: IndexTy, Val: 1u),
3201 DL: DebugLoc::getUnknown(), Name: "", WrapFlags: {true, true});
3202 VPInstruction *Offset0 =
3203 Builder.createOverflowingOp(Opcode: Instruction::Mul, Operands: {VFMinusOne, Stride});
3204
3205 // Offset for PartN = Offset0 + Part * Stride * VF.
3206 VPValue *PartxStride =
3207 Plan.getConstantInt(Ty: IndexTy, Val: Part * getStride(), /*IsSigned=*/true);
3208 VPValue *Offset = Builder.createAdd(
3209 LHS: Offset0,
3210 RHS: Builder.createOverflowingOp(Opcode: Instruction::Mul, Operands: {PartxStride, VF}));
3211 addOffset(Offset);
3212}
3213
3214void VPVectorEndPointerRecipe::execute(VPTransformState &State) {
3215 auto &Builder = State.Builder;
3216 assert(getOffset() && "Expected prior materialization of offset");
3217 Value *Ptr = State.get(Def: getPointer(), IsScalar: true);
3218 Value *Offset = State.get(Def: getOffset(), IsScalar: true);
3219 Value *ResultPtr = Builder.CreateGEP(Ty: getSourceElementType(), Ptr, IdxList: Offset, Name: "",
3220 NW: getGEPNoWrapFlags());
3221 State.set(Def: this, V: ResultPtr, /*IsScalar*/ true);
3222}
3223
3224#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3225void VPVectorEndPointerRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
3226 VPSlotTracker &SlotTracker) const {
3227 O << Indent;
3228 printAsOperand(O, SlotTracker);
3229 O << " = vector-end-pointer";
3230 printFlags(O);
3231 printOperands(O, SlotTracker);
3232}
3233#endif
3234
3235void VPVectorPointerRecipe::execute(VPTransformState &State) {
3236 assert(getVFxPart() &&
3237 "Expected prior simplification of recipe without VFxPart");
3238
3239 auto &Builder = State.Builder;
3240 Value *Ptr = State.get(Def: getOperand(N: 0), Lane: VPLane(0));
3241 Value *Offset = State.get(Def: getVFxPart(), IsScalar: true);
3242 // TODO: Expand to VPInstruction to support constant folding.
3243 if (!match(V: getStride(), P: m_One())) {
3244 Value *Stride = Builder.CreateZExtOrTrunc(V: State.get(Def: getStride(), IsScalar: true),
3245 DestTy: Offset->getType());
3246 Offset = Builder.CreateMul(LHS: Offset, RHS: Stride);
3247 }
3248 Value *ResultPtr = Builder.CreateGEP(Ty: getSourceElementType(), Ptr, IdxList: Offset, Name: "",
3249 NW: getGEPNoWrapFlags());
3250 State.set(Def: this, V: ResultPtr, /*IsScalar*/ true);
3251}
3252
3253#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3254void VPVectorPointerRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
3255 VPSlotTracker &SlotTracker) const {
3256 O << Indent;
3257 printAsOperand(O, SlotTracker);
3258 O << " = vector-pointer";
3259 printFlags(O);
3260 printOperands(O, SlotTracker);
3261}
3262#endif
3263
3264InstructionCost VPBlendRecipe::computeCost(ElementCount VF,
3265 VPCostContext &Ctx) const {
3266 // A blend will be expanded to a select VPInstruction, which will generate a
3267 // scalar select if only the first lane is used.
3268 if (vputils::onlyFirstLaneUsed(Def: this))
3269 VF = ElementCount::getFixed(MinVal: 1);
3270
3271 Type *ResultTy = toVectorTy(Scalar: this->getScalarType(), EC: VF);
3272 Type *CmpTy = toVectorTy(Scalar: Type::getInt1Ty(C&: Ctx.LLVMCtx), EC: VF);
3273 return (getNumIncomingValues() - 1) *
3274 Ctx.TTI.getCmpSelInstrCost(Opcode: Instruction::Select, ValTy: ResultTy, CondTy: CmpTy,
3275 VecPred: CmpInst::BAD_ICMP_PREDICATE, CostKind: Ctx.CostKind);
3276}
3277
3278#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3279void VPBlendRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
3280 VPSlotTracker &SlotTracker) const {
3281 O << Indent << "BLEND ";
3282 printAsOperand(O, SlotTracker);
3283 O << " =";
3284 printFlags(O);
3285 if (getNumIncomingValues() == 1) {
3286 // Not a User of any mask: not really blending, this is a
3287 // single-predecessor phi.
3288 getIncomingValue(0)->printAsOperand(O, SlotTracker);
3289 } else {
3290 for (unsigned I = 0, E = getNumIncomingValues(); I < E; ++I) {
3291 if (I != 0)
3292 O << " ";
3293 getIncomingValue(I)->printAsOperand(O, SlotTracker);
3294 if (I == 0 && isNormalized())
3295 continue;
3296 O << "/";
3297 getMask(I)->printAsOperand(O, SlotTracker);
3298 }
3299 }
3300}
3301#endif
3302
3303void VPReductionRecipe::execute(VPTransformState &State) {
3304 RecurKind Kind = getRecurrenceKind();
3305 assert(!RecurrenceDescriptor::isAnyOfRecurrenceKind(Kind) &&
3306 "In-loop AnyOf reductions aren't currently supported");
3307 // Propagate the fast-math flags carried by the underlying instruction.
3308 IRBuilderBase::FastMathFlagGuard FMFGuard(State.Builder);
3309 State.Builder.setFastMathFlags(getFastMathFlagsOrNone());
3310 Value *NewVecOp = State.get(Def: getVecOp());
3311 if (VPValue *Cond = getCondOp()) {
3312 Value *NewCond = State.get(Def: Cond, IsScalar: State.VF.isScalar());
3313 VectorType *VecTy = dyn_cast<VectorType>(Val: NewVecOp->getType());
3314 Type *ElementTy = VecTy ? VecTy->getElementType() : NewVecOp->getType();
3315
3316 Value *Start =
3317 getRecurrenceIdentity(K: Kind, Tp: ElementTy, FMF: getFastMathFlagsOrNone());
3318 if (State.VF.isVector())
3319 Start = State.Builder.CreateVectorSplat(EC: VecTy->getElementCount(), V: Start);
3320
3321 Value *Select = State.Builder.CreateSelect(C: NewCond, True: NewVecOp, False: Start);
3322 NewVecOp = Select;
3323 }
3324 Value *NewRed;
3325 Value *NextInChain;
3326 if (isOrdered()) {
3327 Value *PrevInChain = State.get(Def: getChainOp(), /*IsScalar*/ true);
3328 if (State.VF.isVector())
3329 NewRed =
3330 createOrderedReduction(B&: State.Builder, RdxKind: Kind, Src: NewVecOp, Start: PrevInChain);
3331 else
3332 NewRed = State.Builder.CreateBinOp(
3333 Opc: (Instruction::BinaryOps)RecurrenceDescriptor::getOpcode(Kind),
3334 LHS: PrevInChain, RHS: NewVecOp);
3335 PrevInChain = NewRed;
3336 NextInChain = NewRed;
3337 } else if (isPartialReduction()) {
3338 assert((Kind == RecurKind::Add || Kind == RecurKind::FAdd) &&
3339 "Unexpected partial reduction kind");
3340 Value *PrevInChain = State.get(Def: getChainOp(), /*IsScalar*/ false);
3341 NewRed = State.Builder.CreateIntrinsic(
3342 RetTy: PrevInChain->getType(),
3343 ID: Kind == RecurKind::Add ? Intrinsic::vector_partial_reduce_add
3344 : Intrinsic::vector_partial_reduce_fadd,
3345 Args: {PrevInChain, NewVecOp}, FMFSource: State.Builder.getFastMathFlags(),
3346 Name: "partial.reduce");
3347 PrevInChain = NewRed;
3348 NextInChain = NewRed;
3349 } else {
3350 assert(isInLoop() &&
3351 "The reduction must either be ordered, partial or in-loop");
3352 Value *PrevInChain = State.get(Def: getChainOp(), /*IsScalar*/ true);
3353 NewRed = createSimpleReduction(B&: State.Builder, Src: NewVecOp, RdxKind: Kind);
3354 if (RecurrenceDescriptor::isMinMaxRecurrenceKind(Kind))
3355 NextInChain = createMinMaxOp(Builder&: State.Builder, RK: Kind, Left: NewRed, Right: PrevInChain);
3356 else
3357 NextInChain = State.Builder.CreateBinOp(
3358 Opc: (Instruction::BinaryOps)RecurrenceDescriptor::getOpcode(Kind),
3359 LHS: PrevInChain, RHS: NewRed);
3360 }
3361 State.set(Def: this, V: NextInChain, /*IsScalar*/ !isPartialReduction());
3362}
3363
3364void VPReductionEVLRecipe::execute(VPTransformState &State) {
3365
3366 auto &Builder = State.Builder;
3367 // Propagate the fast-math flags carried by the underlying instruction.
3368 IRBuilderBase::FastMathFlagGuard FMFGuard(Builder);
3369 Builder.setFastMathFlags(getFastMathFlagsOrNone());
3370
3371 RecurKind Kind = getRecurrenceKind();
3372 Value *Prev = State.get(Def: getChainOp(), /*IsScalar*/ true);
3373 Value *VecOp = State.get(Def: getVecOp());
3374 Value *EVL = State.get(Def: getEVL(), Lane: VPLane(0));
3375
3376 Value *Mask;
3377 if (VPValue *CondOp = getCondOp())
3378 Mask = State.get(Def: CondOp);
3379 else
3380 Mask = Builder.CreateVectorSplat(EC: State.VF, V: Builder.getTrue());
3381
3382 Value *NewRed;
3383 if (isOrdered()) {
3384 NewRed = createOrderedReduction(B&: Builder, RdxKind: Kind, Src: VecOp, Start: Prev, Mask, EVL);
3385 } else {
3386 NewRed = createSimpleReduction(B&: Builder, Src: VecOp, RdxKind: Kind, Mask, EVL);
3387 if (RecurrenceDescriptor::isMinMaxRecurrenceKind(Kind))
3388 NewRed = createMinMaxOp(Builder, RK: Kind, Left: NewRed, Right: Prev);
3389 else
3390 NewRed = Builder.CreateBinOp(
3391 Opc: (Instruction::BinaryOps)RecurrenceDescriptor::getOpcode(Kind), LHS: NewRed,
3392 RHS: Prev);
3393 }
3394 State.set(Def: this, V: NewRed, /*IsScalar*/ true);
3395}
3396
3397InstructionCost VPReductionRecipe::computeCost(ElementCount VF,
3398 VPCostContext &Ctx) const {
3399 RecurKind RdxKind = getRecurrenceKind();
3400 Type *ElementTy = this->getScalarType();
3401 auto *VectorTy = cast<VectorType>(Val: toVectorTy(Scalar: ElementTy, EC: VF));
3402 unsigned Opcode = RecurrenceDescriptor::getOpcode(Kind: RdxKind);
3403 FastMathFlags FMFs = getFastMathFlagsOrNone();
3404 std::optional<FastMathFlags> OptionalFMF =
3405 ElementTy->isFloatingPointTy() ? std::make_optional(t&: FMFs) : std::nullopt;
3406
3407 if (isPartialReduction()) {
3408 InstructionCost CondCost = 0;
3409 if (isConditional()) {
3410 CmpInst::Predicate Pred = CmpInst::BAD_ICMP_PREDICATE;
3411 auto *CondTy =
3412 cast<VectorType>(Val: toVectorTy(Scalar: getCondOp()->getScalarType(), EC: VF));
3413 CondCost = Ctx.TTI.getCmpSelInstrCost(Opcode: Instruction::Select, ValTy: VectorTy,
3414 CondTy, VecPred: Pred, CostKind: Ctx.CostKind);
3415 }
3416 return CondCost + Ctx.TTI.getPartialReductionCost(
3417 Opcode, InputTypeA: ElementTy, InputTypeB: ElementTy, AccumType: ElementTy, VF,
3418 OpAExtend: TTI::PR_None, OpBExtend: TTI::PR_None, BinOp: {}, CostKind: Ctx.CostKind,
3419 FMF: OptionalFMF);
3420 }
3421
3422 // TODO: Support any-of reductions.
3423 assert(
3424 (!RecurrenceDescriptor::isAnyOfRecurrenceKind(RdxKind) ||
3425 ForceTargetInstructionCost.getNumOccurrences() > 0) &&
3426 "Any-of reduction not implemented in VPlan-based cost model currently.");
3427
3428 // Note that TTI should model the cost of moving result to the scalar register
3429 // and the BinOp cost in the getMinMaxReductionCost().
3430 if (RecurrenceDescriptor::isMinMaxRecurrenceKind(Kind: RdxKind)) {
3431 Intrinsic::ID Id = getMinMaxReductionIntrinsicOp(RK: RdxKind);
3432 return Ctx.TTI.getMinMaxReductionCost(IID: Id, Ty: VectorTy, FMF: FMFs, CostKind: Ctx.CostKind);
3433 }
3434
3435 // Note that TTI should model the cost of moving result to the scalar register
3436 // and the BinOp cost in the getArithmeticReductionCost().
3437 return Ctx.TTI.getArithmeticReductionCost(Opcode, Ty: VectorTy, FMF: OptionalFMF,
3438 CostKind: Ctx.CostKind);
3439}
3440
3441VPExpressionRecipe::VPExpressionRecipe(
3442 ExpressionTypes ExpressionType,
3443 ArrayRef<VPSingleDefRecipe *> ExpressionRecipes)
3444 : VPSingleDefRecipe(VPRecipeBase::VPExpressionSC, {},
3445 cast<VPReductionRecipe>(Val: ExpressionRecipes.back())
3446 ->getChainOp()
3447 ->getScalarType()),
3448 ExpressionRecipes(ExpressionRecipes), ExpressionType(ExpressionType) {
3449 assert(!ExpressionRecipes.empty() && "Nothing to combine?");
3450 assert(
3451 none_of(ExpressionRecipes,
3452 [](VPSingleDefRecipe *R) { return R->mayHaveSideEffects(); }) &&
3453 "expression cannot contain recipes with side-effects");
3454
3455 // Maintain a copy of the expression recipes as a set of users.
3456 SmallPtrSet<VPUser *, 4> ExpressionRecipesAsSetOfUsers;
3457 for (auto *R : ExpressionRecipes)
3458 ExpressionRecipesAsSetOfUsers.insert(Ptr: R);
3459
3460 // Recipes in the expression, except the last one, must only be used by
3461 // (other) recipes inside the expression. If there are other users, external
3462 // to the expression, use a clone of the recipe for external users.
3463 for (VPSingleDefRecipe *R : reverse(C&: ExpressionRecipes)) {
3464 if (R != ExpressionRecipes.back() &&
3465 any_of(Range: R->users(), P: [&ExpressionRecipesAsSetOfUsers](VPUser *U) {
3466 return !ExpressionRecipesAsSetOfUsers.contains(Ptr: U);
3467 })) {
3468 // There are users outside of the expression. Clone the recipe and use the
3469 // clone those external users.
3470 VPSingleDefRecipe *CopyForExtUsers = R->clone();
3471 R->replaceUsesWithIf(New: CopyForExtUsers, ShouldReplace: [&ExpressionRecipesAsSetOfUsers](
3472 VPUser &U, unsigned) {
3473 return !ExpressionRecipesAsSetOfUsers.contains(Ptr: &U);
3474 });
3475 CopyForExtUsers->insertBefore(InsertPos: R);
3476 }
3477 if (R->getParent())
3478 R->removeFromParent();
3479 }
3480
3481 // Internalize all external operands to the expression recipes. To do so,
3482 // create new temporary VPValues for all operands defined by a recipe outside
3483 // the expression. The original operands are added as operands of the
3484 // VPExpressionRecipe itself.
3485 for (auto *R : ExpressionRecipes) {
3486 for (const auto &[Idx, Op] : enumerate(First: R->operands())) {
3487 auto *Def = Op->getDefiningRecipe();
3488 if (Def && ExpressionRecipesAsSetOfUsers.contains(Ptr: Def))
3489 continue;
3490 addOperand(Operand: Op);
3491 LiveInPlaceholders.push_back(Elt: new VPSymbolicValue(Op->getScalarType()));
3492 }
3493 }
3494
3495 // Replace each external operand with the first one created for it in
3496 // LiveInPlaceholders.
3497 for (auto *R : ExpressionRecipes)
3498 for (auto const &[LiveIn, Tmp] : zip(t: operands(), u&: LiveInPlaceholders))
3499 R->replaceUsesOfWith(From: LiveIn, To: Tmp);
3500}
3501
3502void VPExpressionRecipe::decompose() {
3503 for (auto *R : ExpressionRecipes)
3504 // Since the list could contain duplicates, make sure the recipe hasn't
3505 // already been inserted.
3506 if (!R->getParent())
3507 R->insertBefore(InsertPos: this);
3508
3509 for (const auto &[Idx, Op] : enumerate(First: operands()))
3510 LiveInPlaceholders[Idx]->replaceAllUsesWith(New: Op);
3511
3512 replaceAllUsesWith(New: ExpressionRecipes.back());
3513 ExpressionRecipes.clear();
3514}
3515
3516InstructionCost VPExpressionRecipe::computeCost(ElementCount VF,
3517 VPCostContext &Ctx) const {
3518 Type *RedTy = this->getScalarType();
3519 auto *SrcVecTy =
3520 cast<VectorType>(Val: toVectorTy(Scalar: getOperand(N: 0)->getScalarType(), EC: VF));
3521 unsigned Opcode = RecurrenceDescriptor::getOpcode(
3522 Kind: cast<VPReductionRecipe>(Val: ExpressionRecipes.back())->getRecurrenceKind());
3523 switch (ExpressionType) {
3524 case ExpressionTypes::NegatedExtendedReduction:
3525 assert((Opcode == Instruction::Add || Opcode == Instruction::FAdd) &&
3526 "Unexpected opcode");
3527 Opcode = Opcode == Instruction::Add ? Instruction::Sub : Instruction::FSub;
3528 [[fallthrough]];
3529 case ExpressionTypes::ExtendedReduction: {
3530 auto *RedR = cast<VPReductionRecipe>(Val: ExpressionRecipes.back());
3531 auto *ExtR = cast<VPWidenCastRecipe>(Val: ExpressionRecipes[0]);
3532
3533 if (RedR->isPartialReduction())
3534 return Ctx.TTI.getPartialReductionCost(
3535 Opcode, InputTypeA: getOperand(N: 0)->getScalarType(), InputTypeB: nullptr, AccumType: RedTy, VF,
3536 OpAExtend: TargetTransformInfo::getPartialReductionExtendKind(CastOpc: ExtR->getOpcode()),
3537 OpBExtend: TargetTransformInfo::PR_None, BinOp: std::nullopt, CostKind: Ctx.CostKind,
3538 FMF: RedTy->isFloatingPointTy()
3539 ? std::optional{RedR->getFastMathFlagsOrNone()}
3540 : std::nullopt);
3541 else if (!RedTy->isFloatingPointTy())
3542 // TTI::getExtendedReductionCost only supports integer types.
3543 return Ctx.TTI.getExtendedReductionCost(
3544 Opcode, IsUnsigned: ExtR->getOpcode() == Instruction::ZExt, ResTy: RedTy, Ty: SrcVecTy,
3545 FMF: std::nullopt, CostKind: Ctx.CostKind);
3546 else
3547 return InstructionCost::getInvalid();
3548 }
3549 case ExpressionTypes::MulAccReduction:
3550 return Ctx.TTI.getMulAccReductionCost(IsUnsigned: false, RedOpcode: Opcode, ResTy: RedTy, Ty: SrcVecTy,
3551 CostKind: Ctx.CostKind);
3552
3553 case ExpressionTypes::ExtNegatedMulAccReduction:
3554 switch (Opcode) {
3555 case Instruction::Add:
3556 Opcode = Instruction::Sub;
3557 break;
3558 case Instruction::FAdd:
3559 Opcode = Instruction::FSub;
3560 break;
3561 default:
3562 llvm_unreachable("Unsupported opcode for ExtNegatedMulAccReduction");
3563 }
3564 [[fallthrough]];
3565 case ExpressionTypes::ExtMulAccReduction: {
3566 auto *RedR = cast<VPReductionRecipe>(Val: ExpressionRecipes.back());
3567 if (RedR->isPartialReduction()) {
3568 auto *Ext0R = cast<VPWidenCastRecipe>(Val: ExpressionRecipes[0]);
3569 auto *Ext1R = cast<VPWidenCastRecipe>(Val: ExpressionRecipes[1]);
3570 auto *Mul = cast<VPWidenRecipe>(Val: ExpressionRecipes[2]);
3571 return Ctx.TTI.getPartialReductionCost(
3572 Opcode, InputTypeA: getOperand(N: 0)->getScalarType(),
3573 InputTypeB: getOperand(N: 1)->getScalarType(), AccumType: RedTy, VF,
3574 OpAExtend: TargetTransformInfo::getPartialReductionExtendKind(
3575 CastOpc: Ext0R->getOpcode()),
3576 OpBExtend: TargetTransformInfo::getPartialReductionExtendKind(
3577 CastOpc: Ext1R->getOpcode()),
3578 BinOp: Mul->getOpcode(), CostKind: Ctx.CostKind,
3579 FMF: RedTy->isFloatingPointTy()
3580 ? std::optional{RedR->getFastMathFlagsOrNone()}
3581 : std::nullopt);
3582 }
3583 assert(Opcode != Instruction::FSub && "Only integer types are supported");
3584 return Ctx.TTI.getMulAccReductionCost(
3585 IsUnsigned: cast<VPWidenCastRecipe>(Val: ExpressionRecipes.front())->getOpcode() ==
3586 Instruction::ZExt,
3587 RedOpcode: Opcode, ResTy: RedTy, Ty: SrcVecTy, CostKind: Ctx.CostKind);
3588 }
3589 }
3590 llvm_unreachable("Unknown VPExpressionRecipe::ExpressionTypes enum");
3591}
3592
3593bool VPExpressionRecipe::mayReadOrWriteMemory() const {
3594 return any_of(Range: ExpressionRecipes, P: [](VPSingleDefRecipe *R) {
3595 return R->mayReadFromMemory() || R->mayWriteToMemory();
3596 });
3597}
3598
3599bool VPExpressionRecipe::mayHaveSideEffects() const {
3600 assert(
3601 none_of(ExpressionRecipes,
3602 [](VPSingleDefRecipe *R) { return R->mayHaveSideEffects(); }) &&
3603 "expression cannot contain recipes with side-effects");
3604 return false;
3605}
3606
3607bool VPExpressionRecipe::isVectorToScalar() const {
3608 auto *RR = dyn_cast<VPReductionRecipe>(Val: ExpressionRecipes.back());
3609 return RR && !RR->isPartialReduction();
3610}
3611
3612#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3613
3614void VPExpressionRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
3615 VPSlotTracker &SlotTracker) const {
3616 O << Indent << "EXPRESSION ";
3617 printAsOperand(O, SlotTracker);
3618 O << " = ";
3619 auto *Red = cast<VPReductionRecipe>(ExpressionRecipes.back());
3620 unsigned Opcode = RecurrenceDescriptor::getOpcode(Red->getRecurrenceKind());
3621 VPValue *RdxStart =
3622 getOperand(getNumOperands() - (Red->isConditional() ? 2 : 1));
3623
3624 switch (ExpressionType) {
3625 case ExpressionTypes::NegatedExtendedReduction:
3626 case ExpressionTypes::ExtendedReduction: {
3627 bool Negated = ExpressionType == ExpressionTypes::NegatedExtendedReduction;
3628 getOperand(getNumOperands() - 1)->printAsOperand(O, SlotTracker);
3629 O << " + " << (Red->isPartialReduction() ? "partial." : "") << "reduce.";
3630 O << Instruction::getOpcodeName(Opcode) << " (";
3631 if (Negated)
3632 O << (Opcode == Instruction::Add ? "sub (0, " : "fneg(");
3633 getOperand(0)->printAsOperand(O, SlotTracker);
3634 if (Negated)
3635 O << ")";
3636 Red->printFlags(O);
3637
3638 auto *Ext0 = cast<VPWidenCastRecipe>(ExpressionRecipes[0]);
3639 O << Instruction::getOpcodeName(Ext0->getOpcode()) << " to "
3640 << *Ext0->getScalarType();
3641 if (Red->isConditional()) {
3642 O << ", ";
3643 getOperand(getNumOperands() - 1)->printAsOperand(O, SlotTracker);
3644 }
3645 O << ")";
3646 break;
3647 }
3648 case ExpressionTypes::ExtNegatedMulAccReduction: {
3649 RdxStart->printAsOperand(O, SlotTracker);
3650 O << " + " << (Red->isPartialReduction() ? "partial." : "") << "reduce.";
3651 O << Instruction::getOpcodeName(
3652 RecurrenceDescriptor::getOpcode(Red->getRecurrenceKind()))
3653 << " (sub (0, mul";
3654 auto *Mul = cast<VPWidenRecipe>(ExpressionRecipes[2]);
3655 Mul->printFlags(O);
3656 O << "(";
3657 getOperand(0)->printAsOperand(O, SlotTracker);
3658 auto *Ext0 = cast<VPWidenCastRecipe>(ExpressionRecipes[0]);
3659 O << " " << Instruction::getOpcodeName(Ext0->getOpcode()) << " to "
3660 << *Ext0->getScalarType() << "), (";
3661 getOperand(1)->printAsOperand(O, SlotTracker);
3662 auto *Ext1 = cast<VPWidenCastRecipe>(ExpressionRecipes[1]);
3663 O << " " << Instruction::getOpcodeName(Ext1->getOpcode()) << " to "
3664 << *Ext1->getScalarType() << ")";
3665 if (Red->isConditional()) {
3666 O << ", ";
3667 getOperand(getNumOperands() - 1)->printAsOperand(O, SlotTracker);
3668 }
3669 O << "))";
3670 break;
3671 }
3672 case ExpressionTypes::MulAccReduction:
3673 case ExpressionTypes::ExtMulAccReduction: {
3674 RdxStart->printAsOperand(O, SlotTracker);
3675 O << " + " << (Red->isPartialReduction() ? "partial." : "") << "reduce.";
3676 O << Instruction::getOpcodeName(
3677 RecurrenceDescriptor::getOpcode(Red->getRecurrenceKind()))
3678 << " (";
3679 O << "mul";
3680 bool IsExtended = ExpressionType == ExpressionTypes::ExtMulAccReduction;
3681 auto *Mul = cast<VPWidenRecipe>(IsExtended ? ExpressionRecipes[2]
3682 : ExpressionRecipes[0]);
3683 Mul->printFlags(O);
3684 if (IsExtended)
3685 O << "(";
3686 getOperand(0)->printAsOperand(O, SlotTracker);
3687 if (IsExtended) {
3688 auto *Ext0 = cast<VPWidenCastRecipe>(ExpressionRecipes[0]);
3689 O << " " << Instruction::getOpcodeName(Ext0->getOpcode()) << " to "
3690 << *Ext0->getScalarType() << "), (";
3691 } else {
3692 O << ", ";
3693 }
3694 getOperand(1)->printAsOperand(O, SlotTracker);
3695 if (IsExtended) {
3696 auto *Ext1 = cast<VPWidenCastRecipe>(ExpressionRecipes[1]);
3697 O << " " << Instruction::getOpcodeName(Ext1->getOpcode()) << " to "
3698 << *Ext1->getScalarType() << ")";
3699 }
3700 if (Red->isConditional()) {
3701 O << ", ";
3702 getOperand(getNumOperands() - 1)->printAsOperand(O, SlotTracker);
3703 }
3704 O << ")";
3705 break;
3706 }
3707 }
3708}
3709
3710void VPReductionRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
3711 VPSlotTracker &SlotTracker) const {
3712 if (isPartialReduction())
3713 O << Indent << "PARTIAL-REDUCE ";
3714 else
3715 O << Indent << "REDUCE ";
3716 printAsOperand(O, SlotTracker);
3717 O << " = ";
3718 getChainOp()->printAsOperand(O, SlotTracker);
3719 O << " +";
3720 printFlags(O);
3721 O << " reduce.";
3722 printRecurrenceKind(O, getRecurrenceKind());
3723 O << " (";
3724 getVecOp()->printAsOperand(O, SlotTracker);
3725 if (isConditional()) {
3726 O << ", ";
3727 getCondOp()->printAsOperand(O, SlotTracker);
3728 }
3729 O << ")";
3730}
3731
3732void VPReductionEVLRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
3733 VPSlotTracker &SlotTracker) const {
3734 O << Indent << "REDUCE ";
3735 printAsOperand(O, SlotTracker);
3736 O << " = ";
3737 getChainOp()->printAsOperand(O, SlotTracker);
3738 O << " +";
3739 printFlags(O);
3740 O << " vp.reduce."
3741 << Instruction::getOpcodeName(
3742 RecurrenceDescriptor::getOpcode(getRecurrenceKind()))
3743 << " (";
3744 getVecOp()->printAsOperand(O, SlotTracker);
3745 O << ", ";
3746 getEVL()->printAsOperand(O, SlotTracker);
3747 if (isConditional()) {
3748 O << ", ";
3749 getCondOp()->printAsOperand(O, SlotTracker);
3750 }
3751 O << ")";
3752}
3753
3754#endif
3755
3756void VPReplicateRecipe::execute(VPTransformState &State) {
3757 assert(IsSingleScalar &&
3758 "VPReplicateRecipes must be unrolled before ::execute");
3759 auto *Instr = getUnderlyingInstr();
3760 Instruction *Cloned = Instr->clone();
3761 Type *ResultTy = getScalarType();
3762 if (!ResultTy->isVoidTy()) {
3763 Cloned->setName(Instr->getName() + ".cloned");
3764 // The operands of the replicate recipe may have been narrowed, resulting in
3765 // a narrower result type. Update the type of the cloned instruction to the
3766 // correct type.
3767 if (ResultTy != Cloned->getType())
3768 Cloned->mutateType(Ty: ResultTy);
3769 }
3770
3771 applyFlags(I&: *Cloned);
3772 applyMetadata(I&: *Cloned);
3773
3774 if (hasPredicate())
3775 cast<CmpInst>(Val: Cloned)->setPredicate(getPredicate());
3776
3777 // Replace the operands of the cloned instructions with their scalar
3778 // equivalents in the new loop.
3779 for (const auto &[Idx, V] : enumerate(First: operands()))
3780 Cloned->setOperand(i: Idx, Val: State.get(Def: V, IsScalar: true));
3781
3782 // Place the cloned scalar in the new loop.
3783 State.Builder.Insert(I: Cloned);
3784
3785 State.set(Def: this, V: Cloned, IsScalar: true);
3786
3787 // If we just cloned a new assumption, add it the assumption cache.
3788 if (auto *II = dyn_cast<AssumeInst>(Val: Cloned))
3789 State.AC->registerAssumption(CI: II);
3790}
3791
3792/// Returns a SCEV expression for \p Ptr if it is a pointer computation for
3793/// which the legacy cost model computes a SCEV expression when computing the
3794/// address cost. Computing SCEVs for VPValues is incomplete and returns
3795/// SCEVCouldNotCompute in cases the legacy cost model can compute SCEVs. In
3796/// those cases we fall back to the legacy cost model. Otherwise return nullptr.
3797static const SCEV *getAddressAccessSCEV(const VPValue *Ptr,
3798 PredicatedScalarEvolution &PSE,
3799 const Loop *L) {
3800 const SCEV *Addr = vputils::getSCEVExprForVPValue(V: Ptr, PSE, L);
3801 if (isa<SCEVCouldNotCompute>(Val: Addr))
3802 return Addr;
3803
3804 return vputils::isAddressSCEVForCost(Addr, SE&: *PSE.getSE(), L) ? Addr : nullptr;
3805}
3806
3807InstructionCost VPReplicateRecipe::computeCost(ElementCount VF,
3808 VPCostContext &Ctx) const {
3809 Instruction *UI = cast<Instruction>(Val: getUnderlyingValue());
3810 // VPReplicateRecipe may be cloned as part of an existing VPlan-to-VPlan
3811 // transform, avoid computing their cost multiple times for now.
3812 Ctx.SkipCostComputation.insert(Ptr: UI);
3813
3814 if (VF.isScalable() && !isSingleScalar())
3815 return InstructionCost::getInvalid();
3816
3817 switch (UI->getOpcode()) {
3818 case Instruction::Alloca:
3819 if (VF.isScalable())
3820 return InstructionCost::getInvalid();
3821 return Ctx.TTI.getArithmeticInstrCost(Opcode: Instruction::Mul,
3822 Ty: this->getScalarType(), CostKind: Ctx.CostKind);
3823 case Instruction::GetElementPtr:
3824 // We mark this instruction as zero-cost because the cost of GEPs in
3825 // vectorized code depends on whether the corresponding memory instruction
3826 // is scalarized or not. Therefore, we handle GEPs with the memory
3827 // instruction cost.
3828 return 0;
3829 case Instruction::Call: {
3830 auto *CalledFn =
3831 cast<Function>(Val: getOperand(N: getNumOperands() - 1)->getLiveInIRValue());
3832 Type *ResultTy = this->getScalarType();
3833 return computeCallCost(CalledFn, ResultTy, ArgOps: drop_end(RangeOrContainer: operands()),
3834 IsSingleScalar: isSingleScalar(), VF, Ctx);
3835 }
3836 case Instruction::Add:
3837 case Instruction::Sub:
3838 case Instruction::FAdd:
3839 case Instruction::FSub:
3840 case Instruction::Mul:
3841 case Instruction::FMul:
3842 case Instruction::FDiv:
3843 case Instruction::FRem:
3844 case Instruction::Shl:
3845 case Instruction::LShr:
3846 case Instruction::AShr:
3847 case Instruction::And:
3848 case Instruction::Or:
3849 case Instruction::Xor:
3850 case Instruction::ICmp:
3851 case Instruction::FCmp:
3852 return getCostForRecipeWithOpcode(Opcode: getOpcode(), VF: ElementCount::getFixed(MinVal: 1),
3853 Ctx) *
3854 (isSingleScalar() ? 1 : VF.getFixedValue());
3855 case Instruction::SDiv:
3856 case Instruction::UDiv:
3857 case Instruction::SRem:
3858 case Instruction::URem: {
3859 InstructionCost ScalarCost =
3860 getCostForRecipeWithOpcode(Opcode: getOpcode(), VF: ElementCount::getFixed(MinVal: 1), Ctx);
3861 if (isSingleScalar())
3862 return ScalarCost;
3863
3864 // If any of the operands is from a different replicate region and has its
3865 // cost skipped, it may have been forced to scalar. Fall back to legacy cost
3866 // model to avoid cost mis-match.
3867 if (any_of(Range: operands(), P: [&Ctx, VF](VPValue *Op) {
3868 auto *PredR = dyn_cast<VPPredInstPHIRecipe>(Val: Op);
3869 if (!PredR)
3870 return false;
3871 return Ctx.skipCostComputation(
3872 UI: dyn_cast_or_null<Instruction>(
3873 Val: PredR->getOperand(N: 0)->getUnderlyingValue()),
3874 IsVector: VF.isVector());
3875 }))
3876 break;
3877
3878 ScalarCost = ScalarCost * VF.getFixedValue() +
3879 Ctx.getScalarizationOverhead(ResultTy: this->getScalarType(),
3880 Operands: to_vector(Range: operands()), VF);
3881 // If the recipe is not predicated (i.e. not in a replicate region), return
3882 // the scalar cost. Otherwise handle predicated cost.
3883 if (!getRegion()->isReplicator())
3884 return ScalarCost;
3885
3886 // Account for the phi nodes that we will create.
3887 ScalarCost += VF.getFixedValue() *
3888 Ctx.TTI.getCFInstrCost(Opcode: Instruction::PHI, CostKind: Ctx.CostKind);
3889 // Scale the cost by the probability of executing the predicated blocks.
3890 // This assumes the predicated block for each vector lane is equally
3891 // likely.
3892 ScalarCost /= Ctx.getPredBlockCostDivisor(BB: UI->getParent());
3893 return ScalarCost;
3894 }
3895 case Instruction::Load:
3896 case Instruction::Store: {
3897 bool IsLoad = UI->getOpcode() == Instruction::Load;
3898 const VPValue *PtrOp = getOperand(N: !IsLoad);
3899 const SCEV *PtrSCEV = getAddressAccessSCEV(Ptr: PtrOp, PSE&: Ctx.PSE, L: Ctx.L);
3900 if (isa_and_nonnull<SCEVCouldNotCompute>(Val: PtrSCEV))
3901 break;
3902
3903 Type *ValTy = (IsLoad ? this : getOperand(N: 0))->getScalarType();
3904 Type *ScalarPtrTy = PtrOp->getScalarType();
3905 const Align Alignment = getLoadStoreAlignment(I: UI);
3906 unsigned AS = cast<PointerType>(Val: ScalarPtrTy)->getAddressSpace();
3907 TTI::OperandValueInfo OpInfo = TTI::getOperandInfo(V: UI->getOperand(i: 0));
3908 bool PreferVectorizedAddressing = Ctx.TTI.prefersVectorizedAddressing();
3909 bool UsedByLoadStoreAddress =
3910 !PreferVectorizedAddressing && vputils::isUsedByLoadStoreAddress(V: this);
3911 InstructionCost ScalarMemOpCost = Ctx.TTI.getMemoryOpCost(
3912 Opcode: UI->getOpcode(), Src: ValTy, Alignment, AddressSpace: AS, CostKind: Ctx.CostKind, OpdInfo: OpInfo,
3913 I: UsedByLoadStoreAddress ? UI : nullptr);
3914
3915 Type *PtrTy = isSingleScalar() ? ScalarPtrTy : toVectorTy(Scalar: ScalarPtrTy, EC: VF);
3916 InstructionCost ScalarCost =
3917 ScalarMemOpCost +
3918 Ctx.TTI.getAddressComputationCost(
3919 PtrTy, SE: UsedByLoadStoreAddress ? nullptr : Ctx.PSE.getSE(), Ptr: PtrSCEV,
3920 CostKind: Ctx.CostKind);
3921 if (isSingleScalar())
3922 return ScalarCost;
3923
3924 SmallVector<const VPValue *> OpsToScalarize;
3925 Type *ResultTy = Type::getVoidTy(C&: PtrTy->getContext());
3926 // Set ResultTy and OpsToScalarize, if scalarization is needed. Currently we
3927 // don't assign scalarization overhead in general, if the target prefers
3928 // vectorized addressing or the loaded value is used as part of an address
3929 // of another load or store.
3930 if (!UsedByLoadStoreAddress) {
3931 bool EfficientVectorLoadStore =
3932 Ctx.TTI.supportsEfficientVectorElementLoadStore();
3933 if (!(IsLoad && !PreferVectorizedAddressing) &&
3934 !(!IsLoad && EfficientVectorLoadStore))
3935 append_range(C&: OpsToScalarize, R: operands());
3936
3937 if (!EfficientVectorLoadStore)
3938 ResultTy = this->getScalarType();
3939 }
3940
3941 TTI::VectorInstrContext VIC =
3942 IsLoad ? TTI::VectorInstrContext::Load : TTI::VectorInstrContext::Store;
3943 InstructionCost Cost =
3944 (ScalarCost * VF.getFixedValue()) +
3945 Ctx.getScalarizationOverhead(ResultTy, Operands: OpsToScalarize, VF, VIC, AlwaysIncludeReplicatingR: true);
3946
3947 const VPRegionBlock *ParentRegion = getRegion();
3948 if (ParentRegion && ParentRegion->isReplicator()) {
3949 if (!PtrSCEV)
3950 break;
3951 Cost /= Ctx.getPredBlockCostDivisor(BB: UI->getParent());
3952 Cost += Ctx.TTI.getCFInstrCost(Opcode: Instruction::CondBr, CostKind: Ctx.CostKind);
3953
3954 auto *VecI1Ty = VectorType::get(
3955 ElementType: IntegerType::getInt1Ty(C&: Ctx.L->getHeader()->getContext()), EC: VF);
3956 Cost += Ctx.TTI.getScalarizationOverhead(
3957 Ty: VecI1Ty, DemandedElts: APInt::getAllOnes(numBits: VF.getFixedValue()),
3958 /*Insert=*/false, /*Extract=*/true, CostKind: Ctx.CostKind);
3959
3960 if (Ctx.useEmulatedMaskMemRefHack(R: this, VF)) {
3961 // Artificially setting to a high enough value to practically disable
3962 // vectorization with such operations.
3963 return 3000000;
3964 }
3965 }
3966 return Cost;
3967 }
3968 case Instruction::SExt:
3969 case Instruction::ZExt:
3970 case Instruction::FPToUI:
3971 case Instruction::FPToSI:
3972 case Instruction::FPExt:
3973 case Instruction::PtrToInt:
3974 case Instruction::PtrToAddr:
3975 case Instruction::IntToPtr:
3976 case Instruction::SIToFP:
3977 case Instruction::UIToFP:
3978 case Instruction::Trunc:
3979 case Instruction::FPTrunc:
3980 case Instruction::Select:
3981 case Instruction::AddrSpaceCast: {
3982 return getCostForRecipeWithOpcode(Opcode: getOpcode(), VF: ElementCount::getFixed(MinVal: 1),
3983 Ctx) *
3984 (isSingleScalar() ? 1 : VF.getFixedValue());
3985 }
3986 case Instruction::ExtractValue:
3987 case Instruction::InsertValue:
3988 return Ctx.TTI.getInsertExtractValueCost(Opcode: getOpcode(), CostKind: Ctx.CostKind);
3989 }
3990
3991 return Ctx.getLegacyCost(UI, VF);
3992}
3993
3994InstructionCost VPReplicateRecipe::computeCallCost(
3995 Function *CalledFn, Type *ResultTy, ArrayRef<const VPValue *> ArgOps,
3996 bool IsSingleScalar, ElementCount VF, VPCostContext &Ctx) {
3997 SmallVector<Type *, 4> Tys = map_to_vector<4>(
3998 C&: ArgOps, F: [&](const VPValue *Op) { return Op->getScalarType(); });
3999
4000 Intrinsic::ID IntrinID = CalledFn->getIntrinsicID();
4001 auto GetIntrinsicCost = [&] {
4002 if (!IntrinID)
4003 return InstructionCost::getInvalid();
4004 return Ctx.TTI.getIntrinsicInstrCost(
4005 ICA: IntrinsicCostAttributes(IntrinID, ResultTy, Tys), CostKind: Ctx.CostKind);
4006 };
4007
4008 if (IntrinID && VPCostContext::isFreeScalarIntrinsic(ID: IntrinID)) {
4009 assert(GetIntrinsicCost() == 0 && "scalarizing intrinsic should be free");
4010 return 0;
4011 }
4012
4013 InstructionCost ScalarCallCost =
4014 Ctx.TTI.getCallInstrCost(F: CalledFn, RetTy: ResultTy, Tys, CostKind: Ctx.CostKind);
4015 if (IsSingleScalar) {
4016 ScalarCallCost = std::min(a: ScalarCallCost, b: GetIntrinsicCost());
4017 return ScalarCallCost;
4018 }
4019
4020 // Scalarization overhead is undefined for scalable VFs.
4021 if (VF.isScalable())
4022 return InstructionCost::getInvalid();
4023
4024 return ScalarCallCost * VF.getFixedValue() +
4025 Ctx.getScalarizationOverhead(ResultTy, Operands: ArgOps, VF);
4026}
4027
4028#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4029void VPReplicateRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
4030 VPSlotTracker &SlotTracker) const {
4031 O << Indent << (IsSingleScalar ? "CLONE " : "REPLICATE ");
4032
4033 if (!getScalarType()->isVoidTy()) {
4034 printAsOperand(O, SlotTracker);
4035 O << " = ";
4036 }
4037 if (auto *CB = dyn_cast<CallBase>(getUnderlyingInstr())) {
4038 O << "call";
4039 printFlags(O);
4040 O << "@" << CB->getCalledFunction()->getName() << "(";
4041 interleaveComma(drop_end(operands()), O, [&O, &SlotTracker](VPValue *Op) {
4042 Op->printAsOperand(O, SlotTracker);
4043 });
4044 O << ")";
4045 } else {
4046 O << Instruction::getOpcodeName(getUnderlyingInstr()->getOpcode());
4047 printFlags(O);
4048 printOperands(O, SlotTracker);
4049 }
4050
4051 // Find if the recipe is used by a widened recipe via an intervening
4052 // VPPredInstPHIRecipe. In this case, also pack the scalar values in a vector.
4053 if (any_of(users(), [](const VPUser *U) {
4054 if (auto *PredR = dyn_cast<VPPredInstPHIRecipe>(U))
4055 return !vputils::onlyScalarValuesUsed(PredR);
4056 return false;
4057 }))
4058 O << " (S->V)";
4059}
4060#endif
4061
4062void VPBranchOnMaskRecipe::execute(VPTransformState &State) {
4063 llvm_unreachable("recipe must be removed when dissolving replicate region");
4064}
4065
4066InstructionCost VPBranchOnMaskRecipe::computeCost(ElementCount VF,
4067 VPCostContext &Ctx) const {
4068 // The legacy cost model doesn't assign costs to branches for individual
4069 // replicate regions. Match the current behavior in the VPlan cost model for
4070 // now.
4071 return 0;
4072}
4073
4074void VPPredInstPHIRecipe::execute(VPTransformState &State) {
4075 llvm_unreachable("recipe must be removed when dissolving replicate region");
4076}
4077
4078#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4079void VPPredInstPHIRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
4080 VPSlotTracker &SlotTracker) const {
4081 O << Indent << "PHI-PREDICATED-INSTRUCTION ";
4082 printAsOperand(O, SlotTracker);
4083 O << " = ";
4084 printOperands(O, SlotTracker);
4085}
4086#endif
4087
4088VPRecipeBase *VPWidenLoadRecipe::getAsRecipe() { return this; }
4089const VPRecipeBase *VPWidenLoadRecipe::getAsRecipe() const { return this; }
4090
4091VPRecipeBase *VPWidenLoadEVLRecipe::getAsRecipe() { return this; }
4092const VPRecipeBase *VPWidenLoadEVLRecipe::getAsRecipe() const { return this; }
4093
4094VPRecipeBase *VPWidenStoreRecipe::getAsRecipe() { return this; }
4095const VPRecipeBase *VPWidenStoreRecipe::getAsRecipe() const { return this; }
4096
4097VPRecipeBase *VPWidenStoreEVLRecipe::getAsRecipe() { return this; }
4098const VPRecipeBase *VPWidenStoreEVLRecipe::getAsRecipe() const { return this; }
4099
4100InstructionCost VPWidenMemoryRecipe::computeCost(ElementCount VF,
4101 VPCostContext &Ctx) const {
4102 const VPRecipeBase *R = getAsRecipe();
4103 bool IsLoad = isa<VPWidenLoadRecipe, VPWidenLoadEVLRecipe>(Val: R);
4104 Type *ScalarTy = IsLoad ? cast<VPSingleDefRecipe>(Val: R)->getScalarType()
4105 : R->getOperand(N: 1)->getScalarType();
4106 Type *Ty = toVectorTy(Scalar: ScalarTy, EC: VF);
4107 unsigned AS =
4108 cast<PointerType>(Val: getAddr()->getScalarType())->getAddressSpace();
4109 unsigned Opcode = IsLoad ? Instruction::Load : Instruction::Store;
4110
4111 if (!Consecutive) {
4112 // TODO: Using the original IR may not be accurate.
4113 // Currently, ARM will use the underlying IR to calculate gather/scatter
4114 // instruction cost.
4115 Type *PtrTy = getAddr()->getScalarType();
4116 const Value *Ptr = getAddr()->getUnderlyingValue();
4117
4118 // If the address value is uniform across all lanes, then the address can be
4119 // calculated with scalar type and broadcast.
4120 if (!vputils::isSingleScalar(VPV: getAddr()))
4121 PtrTy = toVectorTy(Scalar: PtrTy, EC: VF);
4122
4123 unsigned IID = isa<VPWidenLoadRecipe>(Val: R) ? Intrinsic::masked_gather
4124 : isa<VPWidenStoreRecipe>(Val: R) ? Intrinsic::masked_scatter
4125 : isa<VPWidenLoadEVLRecipe>(Val: R) ? Intrinsic::vp_gather
4126 : Intrinsic::vp_scatter;
4127 return Ctx.TTI.getAddressComputationCost(PtrTy, SE: nullptr, Ptr: nullptr,
4128 CostKind: Ctx.CostKind) +
4129 Ctx.TTI.getMemIntrinsicInstrCost(
4130 MICA: MemIntrinsicCostAttributes(IID, Ty, Ptr, IsMasked, Alignment,
4131 &Ingredient),
4132 CostKind: Ctx.CostKind);
4133 }
4134
4135 InstructionCost Cost = 0;
4136 if (IsMasked) {
4137 unsigned IID = isa<VPWidenLoadRecipe>(Val: R) ? Intrinsic::masked_load
4138 : Intrinsic::masked_store;
4139 Cost += Ctx.TTI.getMemIntrinsicInstrCost(
4140 MICA: MemIntrinsicCostAttributes(IID, Ty, Alignment, AS), CostKind: Ctx.CostKind);
4141 } else {
4142 TTI::OperandValueInfo OpInfo = Ctx.getOperandInfo(
4143 V: isa<VPWidenLoadRecipe, VPWidenLoadEVLRecipe>(Val: R) ? R->getOperand(N: 0)
4144 : R->getOperand(N: 1));
4145 Cost += Ctx.TTI.getMemoryOpCost(Opcode, Src: Ty, Alignment, AddressSpace: AS, CostKind: Ctx.CostKind,
4146 OpdInfo: OpInfo, I: &Ingredient);
4147 }
4148 return Cost;
4149}
4150
4151void VPWidenLoadRecipe::execute(VPTransformState &State) {
4152 Type *ScalarDataTy = getScalarType();
4153 auto *DataTy = VectorType::get(ElementType: ScalarDataTy, EC: State.VF);
4154 bool CreateGather = !isConsecutive();
4155
4156 auto &Builder = State.Builder;
4157 Value *Mask = nullptr;
4158 if (auto *VPMask = getMask())
4159 Mask = State.get(Def: VPMask);
4160
4161 Value *Addr = State.get(Def: getAddr(), /*IsScalar*/ !CreateGather);
4162 Value *NewLI;
4163 if (CreateGather) {
4164 NewLI = Builder.CreateMaskedGather(Ty: DataTy, Ptrs: Addr, Alignment, Mask, PassThru: nullptr,
4165 Name: "wide.masked.gather");
4166 } else if (Mask) {
4167 NewLI =
4168 Builder.CreateMaskedLoad(Ty: DataTy, Ptr: Addr, Alignment, Mask,
4169 PassThru: PoisonValue::get(T: DataTy), Name: "wide.masked.load");
4170 } else {
4171 NewLI = Builder.CreateAlignedLoad(Ty: DataTy, Ptr: Addr, Align: Alignment, Name: "wide.load");
4172 }
4173 applyMetadata(I&: *cast<Instruction>(Val: NewLI));
4174 State.set(Def: this, V: NewLI);
4175}
4176
4177#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4178void VPWidenLoadRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
4179 VPSlotTracker &SlotTracker) const {
4180 O << Indent << "WIDEN ";
4181 printAsOperand(O, SlotTracker);
4182 O << " = load ";
4183 printOperands(O, SlotTracker);
4184}
4185#endif
4186
4187void VPWidenLoadEVLRecipe::execute(VPTransformState &State) {
4188 Type *ScalarDataTy = getScalarType();
4189 auto *DataTy = VectorType::get(ElementType: ScalarDataTy, EC: State.VF);
4190 bool CreateGather = !isConsecutive();
4191
4192 auto &Builder = State.Builder;
4193 CallInst *NewLI;
4194 Value *EVL = State.get(Def: getEVL(), Lane: VPLane(0));
4195 Value *Addr = State.get(Def: getAddr(), IsScalar: !CreateGather);
4196 Value *Mask = nullptr;
4197 if (VPValue *VPMask = getMask())
4198 Mask = State.get(Def: VPMask);
4199 else
4200 Mask = Builder.CreateVectorSplat(EC: State.VF, V: Builder.getTrue());
4201
4202 if (CreateGather) {
4203 NewLI = Builder.CreateIntrinsicWithoutFolding(RetTy: DataTy, ID: Intrinsic::vp_gather,
4204 Args: {Addr, Mask, EVL}, FMFSource: nullptr,
4205 Name: "wide.masked.gather");
4206 } else {
4207 NewLI = Builder.CreateIntrinsicWithoutFolding(
4208 RetTy: DataTy, ID: Intrinsic::vp_load, Args: {Addr, Mask, EVL}, FMFSource: nullptr, Name: "vp.op.load");
4209 }
4210 NewLI->addParamAttr(
4211 ArgNo: 0, Attr: Attribute::getWithAlignment(Context&: NewLI->getContext(), Alignment));
4212 applyMetadata(I&: *NewLI);
4213 State.set(Def: this, V: NewLI);
4214}
4215
4216InstructionCost VPWidenLoadEVLRecipe::computeCost(ElementCount VF,
4217 VPCostContext &Ctx) const {
4218 if (!Consecutive || IsMasked)
4219 return VPWidenMemoryRecipe::computeCost(VF, Ctx);
4220
4221 // We need to use the getMemIntrinsicInstrCost() instead of getMemoryOpCost()
4222 // here because the EVL recipes using EVL to replace the tail mask. But in the
4223 // legacy model, it will always calculate the cost of mask.
4224 // TODO: Using getMemoryOpCost() instead of getMemIntrinsicInstrCost when we
4225 // don't need to compare to the legacy cost model.
4226 Type *Ty = toVectorTy(Scalar: getScalarType(), EC: VF);
4227 unsigned AS =
4228 cast<PointerType>(Val: getAddr()->getScalarType())->getAddressSpace();
4229 return Ctx.TTI.getMemIntrinsicInstrCost(
4230 MICA: MemIntrinsicCostAttributes(Intrinsic::vp_load, Ty, Alignment, AS),
4231 CostKind: Ctx.CostKind);
4232}
4233
4234#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4235void VPWidenLoadEVLRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
4236 VPSlotTracker &SlotTracker) const {
4237 O << Indent << "WIDEN ";
4238 printAsOperand(O, SlotTracker);
4239 O << " = vp.load ";
4240 printOperands(O, SlotTracker);
4241}
4242#endif
4243
4244void VPWidenStoreRecipe::execute(VPTransformState &State) {
4245 VPValue *StoredVPValue = getStoredValue();
4246 bool CreateScatter = !isConsecutive();
4247
4248 auto &Builder = State.Builder;
4249
4250 Value *Mask = nullptr;
4251 if (auto *VPMask = getMask())
4252 Mask = State.get(Def: VPMask);
4253
4254 Value *StoredVal = State.get(Def: StoredVPValue);
4255 Value *Addr = State.get(Def: getAddr(), /*IsScalar*/ !CreateScatter);
4256 Instruction *NewSI = nullptr;
4257 if (CreateScatter)
4258 NewSI = Builder.CreateMaskedScatter(Val: StoredVal, Ptrs: Addr, Alignment, Mask);
4259 else if (Mask)
4260 NewSI = Builder.CreateMaskedStore(Val: StoredVal, Ptr: Addr, Alignment, Mask);
4261 else
4262 NewSI = Builder.CreateAlignedStore(Val: StoredVal, Ptr: Addr, Align: Alignment);
4263 applyMetadata(I&: *NewSI);
4264}
4265
4266#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4267void VPWidenStoreRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
4268 VPSlotTracker &SlotTracker) const {
4269 O << Indent << "WIDEN store ";
4270 printOperands(O, SlotTracker);
4271}
4272#endif
4273
4274void VPWidenStoreEVLRecipe::execute(VPTransformState &State) {
4275 VPValue *StoredValue = getStoredValue();
4276 bool CreateScatter = !isConsecutive();
4277
4278 auto &Builder = State.Builder;
4279
4280 CallInst *NewSI = nullptr;
4281 Value *StoredVal = State.get(Def: StoredValue);
4282 Value *EVL = State.get(Def: getEVL(), Lane: VPLane(0));
4283 Value *Mask = nullptr;
4284 if (VPValue *VPMask = getMask())
4285 Mask = State.get(Def: VPMask);
4286 else
4287 Mask = Builder.CreateVectorSplat(EC: State.VF, V: Builder.getTrue());
4288
4289 Value *Addr = State.get(Def: getAddr(), IsScalar: !CreateScatter);
4290 if (CreateScatter) {
4291 NewSI = Builder.CreateIntrinsicWithoutFolding(
4292 RetTy: Type::getVoidTy(C&: EVL->getContext()), ID: Intrinsic::vp_scatter,
4293 Args: {StoredVal, Addr, Mask, EVL});
4294 } else {
4295 NewSI = Builder.CreateIntrinsicWithoutFolding(
4296 RetTy: Type::getVoidTy(C&: EVL->getContext()), ID: Intrinsic::vp_store,
4297 Args: {StoredVal, Addr, Mask, EVL});
4298 }
4299 NewSI->addParamAttr(
4300 ArgNo: 1, Attr: Attribute::getWithAlignment(Context&: NewSI->getContext(), Alignment));
4301 applyMetadata(I&: *NewSI);
4302}
4303
4304InstructionCost VPWidenStoreEVLRecipe::computeCost(ElementCount VF,
4305 VPCostContext &Ctx) const {
4306 if (!Consecutive || IsMasked)
4307 return VPWidenMemoryRecipe::computeCost(VF, Ctx);
4308
4309 // We need to use the getMemIntrinsicInstrCost() instead of getMemoryOpCost()
4310 // here because the EVL recipes using EVL to replace the tail mask. But in the
4311 // legacy model, it will always calculate the cost of mask.
4312 // TODO: Using getMemoryOpCost() instead of getMemIntrinsicInstrCost when we
4313 // don't need to compare to the legacy cost model.
4314 Type *Ty = toVectorTy(Scalar: getStoredValue()->getScalarType(), EC: VF);
4315 unsigned AS =
4316 cast<PointerType>(Val: getAddr()->getScalarType())->getAddressSpace();
4317 return Ctx.TTI.getMemIntrinsicInstrCost(
4318 MICA: MemIntrinsicCostAttributes(Intrinsic::vp_store, Ty, Alignment, AS),
4319 CostKind: Ctx.CostKind);
4320}
4321
4322#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4323void VPWidenStoreEVLRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
4324 VPSlotTracker &SlotTracker) const {
4325 O << Indent << "WIDEN vp.store ";
4326 printOperands(O, SlotTracker);
4327}
4328#endif
4329
4330static Value *createBitOrPointerCast(IRBuilderBase &Builder, Value *V,
4331 VectorType *DstVTy, const DataLayout &DL) {
4332 // Verify that V is a vector type with same number of elements as DstVTy.
4333 auto VF = DstVTy->getElementCount();
4334 auto *SrcVecTy = cast<VectorType>(Val: V->getType());
4335 assert(VF == SrcVecTy->getElementCount() && "Vector dimensions do not match");
4336 Type *SrcElemTy = SrcVecTy->getElementType();
4337 Type *DstElemTy = DstVTy->getElementType();
4338 assert((DL.getTypeSizeInBits(SrcElemTy) == DL.getTypeSizeInBits(DstElemTy)) &&
4339 "Vector elements must have same size");
4340
4341 // Do a direct cast if element types are castable.
4342 if (CastInst::isBitOrNoopPointerCastable(SrcTy: SrcElemTy, DestTy: DstElemTy, DL)) {
4343 return Builder.CreateBitOrPointerCast(V, DestTy: DstVTy);
4344 }
4345 // V cannot be directly casted to desired vector type.
4346 // May happen when V is a floating point vector but DstVTy is a vector of
4347 // pointers or vice-versa. Handle this using a two-step bitcast using an
4348 // intermediate Integer type for the bitcast i.e. Ptr <-> Int <-> Float.
4349 assert((DstElemTy->isPointerTy() != SrcElemTy->isPointerTy()) &&
4350 "Only one type should be a pointer type");
4351 assert((DstElemTy->isFloatingPointTy() != SrcElemTy->isFloatingPointTy()) &&
4352 "Only one type should be a floating point type");
4353 Type *IntTy =
4354 IntegerType::getIntNTy(C&: V->getContext(), N: DL.getTypeSizeInBits(Ty: SrcElemTy));
4355 auto *VecIntTy = VectorType::get(ElementType: IntTy, EC: VF);
4356 Value *CastVal = Builder.CreateBitOrPointerCast(V, DestTy: VecIntTy);
4357 return Builder.CreateBitOrPointerCast(V: CastVal, DestTy: DstVTy);
4358}
4359
4360/// Return a vector containing interleaved elements from multiple
4361/// smaller input vectors.
4362static Value *interleaveVectors(IRBuilderBase &Builder, ArrayRef<Value *> Vals,
4363 const Twine &Name) {
4364 unsigned Factor = Vals.size();
4365 assert(Factor > 1 && "Tried to interleave invalid number of vectors");
4366
4367 VectorType *VecTy = cast<VectorType>(Val: Vals[0]->getType());
4368#ifndef NDEBUG
4369 for (Value *Val : Vals)
4370 assert(Val->getType() == VecTy && "Tried to interleave mismatched types");
4371#endif
4372
4373 // Scalable vectors cannot use arbitrary shufflevectors (only splats), so
4374 // must use intrinsics to interleave.
4375 if (VecTy->isScalableTy()) {
4376 assert(Factor <= 8 && "Unsupported interleave factor for scalable vectors");
4377 return Builder.CreateVectorInterleave(Ops: Vals, Name);
4378 }
4379
4380 // Fixed length. Start by concatenating all vectors into a wide vector.
4381 Value *WideVec = concatenateVectors(Builder, Vecs: Vals);
4382
4383 // Interleave the elements into the wide vector.
4384 const unsigned NumElts = VecTy->getElementCount().getFixedValue();
4385 return Builder.CreateShuffleVector(
4386 V: WideVec, Mask: createInterleaveMask(VF: NumElts, NumVecs: Factor), Name);
4387}
4388
4389// Try to vectorize the interleave group that \p Instr belongs to.
4390//
4391// E.g. Translate following interleaved load group (factor = 3):
4392// for (i = 0; i < N; i+=3) {
4393// R = Pic[i]; // Member of index 0
4394// G = Pic[i+1]; // Member of index 1
4395// B = Pic[i+2]; // Member of index 2
4396// ... // do something to R, G, B
4397// }
4398// To:
4399// %wide.vec = load <12 x i32> ; Read 4 tuples of R,G,B
4400// %R.vec = shuffle %wide.vec, poison, <0, 3, 6, 9> ; R elements
4401// %G.vec = shuffle %wide.vec, poison, <1, 4, 7, 10> ; G elements
4402// %B.vec = shuffle %wide.vec, poison, <2, 5, 8, 11> ; B elements
4403//
4404// Or translate following interleaved store group (factor = 3):
4405// for (i = 0; i < N; i+=3) {
4406// ... do something to R, G, B
4407// Pic[i] = R; // Member of index 0
4408// Pic[i+1] = G; // Member of index 1
4409// Pic[i+2] = B; // Member of index 2
4410// }
4411// To:
4412// %R_G.vec = shuffle %R.vec, %G.vec, <0, 1, 2, ..., 7>
4413// %B_U.vec = shuffle %B.vec, poison, <0, 1, 2, 3, u, u, u, u>
4414// %interleaved.vec = shuffle %R_G.vec, %B_U.vec,
4415// <0, 4, 8, 1, 5, 9, 2, 6, 10, 3, 7, 11> ; Interleave R,G,B elements
4416// store <12 x i32> %interleaved.vec ; Write 4 tuples of R,G,B
4417void VPInterleaveRecipe::execute(VPTransformState &State) {
4418 assert((!needsMaskForGaps() || !State.VF.isScalable()) &&
4419 "Masking gaps for scalable vectors is not yet supported.");
4420 const InterleaveGroup<Instruction> *Group = getInterleaveGroup();
4421 Instruction *Instr = Group->getInsertPos();
4422
4423 // Prepare for the vector type of the interleaved load/store.
4424 Type *ScalarTy = getLoadStoreType(I: Instr);
4425 unsigned InterleaveFactor = Group->getFactor();
4426 auto *VecTy = VectorType::get(ElementType: ScalarTy, EC: State.VF * InterleaveFactor);
4427
4428 VPValue *BlockInMask = getMask();
4429 VPValue *Addr = getAddr();
4430 Value *ResAddr = State.get(Def: Addr, Lane: VPLane(0));
4431
4432 auto CreateGroupMask = [&BlockInMask, &State,
4433 &InterleaveFactor](Value *MaskForGaps) -> Value * {
4434 if (State.VF.isScalable()) {
4435 assert(!MaskForGaps && "Interleaved groups with gaps are not supported.");
4436 assert(InterleaveFactor <= 8 &&
4437 "Unsupported deinterleave factor for scalable vectors");
4438 auto *ResBlockInMask = State.get(Def: BlockInMask);
4439 SmallVector<Value *> Ops(InterleaveFactor, ResBlockInMask);
4440 return interleaveVectors(Builder&: State.Builder, Vals: Ops, Name: "interleaved.mask");
4441 }
4442
4443 if (!BlockInMask)
4444 return MaskForGaps;
4445
4446 Value *ResBlockInMask = State.get(Def: BlockInMask);
4447 Value *ShuffledMask = State.Builder.CreateShuffleVector(
4448 V: ResBlockInMask,
4449 Mask: createReplicatedMask(ReplicationFactor: InterleaveFactor, VF: State.VF.getFixedValue()),
4450 Name: "interleaved.mask");
4451 return MaskForGaps ? State.Builder.CreateBinOp(Opc: Instruction::And,
4452 LHS: ShuffledMask, RHS: MaskForGaps)
4453 : ShuffledMask;
4454 };
4455
4456 const DataLayout &DL = Instr->getDataLayout();
4457 // Vectorize the interleaved load group.
4458 if (isa<LoadInst>(Val: Instr)) {
4459 Value *MaskForGaps = nullptr;
4460 if (needsMaskForGaps()) {
4461 MaskForGaps =
4462 createBitMaskForGaps(Builder&: State.Builder, VF: State.VF.getFixedValue(), Group: *Group);
4463 assert(MaskForGaps && "Mask for Gaps is required but it is null");
4464 }
4465
4466 Instruction *NewLoad;
4467 if (BlockInMask || MaskForGaps) {
4468 Value *GroupMask = CreateGroupMask(MaskForGaps);
4469 Value *PoisonVec = PoisonValue::get(T: VecTy);
4470 NewLoad = State.Builder.CreateMaskedLoad(Ty: VecTy, Ptr: ResAddr,
4471 Alignment: Group->getAlign(), Mask: GroupMask,
4472 PassThru: PoisonVec, Name: "wide.masked.vec");
4473 } else
4474 NewLoad = State.Builder.CreateAlignedLoad(Ty: VecTy, Ptr: ResAddr,
4475 Align: Group->getAlign(), Name: "wide.vec");
4476 applyMetadata(I&: *NewLoad);
4477 // TODO: Also manage existing metadata using VPIRMetadata.
4478 Group->addMetadata(NewInst: NewLoad);
4479
4480 ArrayRef<VPRecipeValue *> VPDefs = definedValues();
4481 if (VecTy->isScalableTy()) {
4482 // Scalable vectors cannot use arbitrary shufflevectors (only splats),
4483 // so must use intrinsics to deinterleave.
4484 assert(InterleaveFactor <= 8 &&
4485 "Unsupported deinterleave factor for scalable vectors");
4486 NewLoad = State.Builder.CreateIntrinsicWithoutFolding(
4487 ID: Intrinsic::getDeinterleaveIntrinsicID(Factor: InterleaveFactor),
4488 OverloadTypes: NewLoad->getType(), Args: NewLoad,
4489 /*FMFSource=*/nullptr, Name: "strided.vec");
4490 }
4491
4492 auto CreateStridedVector = [&InterleaveFactor, &State,
4493 &NewLoad](unsigned Index) -> Value * {
4494 assert(Index < InterleaveFactor && "Illegal group index");
4495 if (State.VF.isScalable())
4496 return State.Builder.CreateExtractValue(Agg: NewLoad, Idxs: Index);
4497
4498 // For fixed length VF, use shuffle to extract the sub-vectors from the
4499 // wide load.
4500 auto StrideMask =
4501 createStrideMask(Start: Index, Stride: InterleaveFactor, VF: State.VF.getFixedValue());
4502 return State.Builder.CreateShuffleVector(V: NewLoad, Mask: StrideMask,
4503 Name: "strided.vec");
4504 };
4505
4506 for (unsigned I = 0, J = 0; I < InterleaveFactor; ++I) {
4507 Instruction *Member = Group->getMember(Index: I);
4508
4509 // Skip the gaps in the group.
4510 if (!Member)
4511 continue;
4512
4513 Value *StridedVec = CreateStridedVector(I);
4514
4515 // If this member has different type, cast the result type.
4516 if (Member->getType() != ScalarTy) {
4517 VectorType *OtherVTy = VectorType::get(ElementType: Member->getType(), EC: State.VF);
4518 StridedVec =
4519 createBitOrPointerCast(Builder&: State.Builder, V: StridedVec, DstVTy: OtherVTy, DL);
4520 }
4521
4522 if (Group->isReverse())
4523 StridedVec = State.Builder.CreateVectorReverse(V: StridedVec, Name: "reverse");
4524
4525 State.set(Def: VPDefs[J], V: StridedVec);
4526 ++J;
4527 }
4528 return;
4529 }
4530
4531 // The sub vector type for current instruction.
4532 auto *SubVT = VectorType::get(ElementType: ScalarTy, EC: State.VF);
4533
4534 // Vectorize the interleaved store group.
4535 Value *MaskForGaps =
4536 createBitMaskForGaps(Builder&: State.Builder, VF: State.VF.getKnownMinValue(), Group: *Group);
4537 assert(((MaskForGaps != nullptr) == needsMaskForGaps()) &&
4538 "Mismatch between NeedsMaskForGaps and MaskForGaps");
4539 ArrayRef<VPValue *> StoredValues = getStoredValues();
4540 // Collect the stored vector from each member.
4541 SmallVector<Value *, 4> StoredVecs;
4542 unsigned StoredIdx = 0;
4543 for (unsigned i = 0; i < InterleaveFactor; i++) {
4544 assert((Group->getMember(i) || MaskForGaps) &&
4545 "Fail to get a member from an interleaved store group");
4546 Instruction *Member = Group->getMember(Index: i);
4547
4548 // Skip the gaps in the group.
4549 if (!Member) {
4550 Value *Undef = PoisonValue::get(T: SubVT);
4551 StoredVecs.push_back(Elt: Undef);
4552 continue;
4553 }
4554
4555 Value *StoredVec = State.get(Def: StoredValues[StoredIdx]);
4556 ++StoredIdx;
4557
4558 if (Group->isReverse())
4559 StoredVec = State.Builder.CreateVectorReverse(V: StoredVec, Name: "reverse");
4560
4561 // If this member has different type, cast it to a unified type.
4562
4563 if (StoredVec->getType() != SubVT)
4564 StoredVec = createBitOrPointerCast(Builder&: State.Builder, V: StoredVec, DstVTy: SubVT, DL);
4565
4566 StoredVecs.push_back(Elt: StoredVec);
4567 }
4568
4569 // Interleave all the smaller vectors into one wider vector.
4570 Value *IVec = interleaveVectors(Builder&: State.Builder, Vals: StoredVecs, Name: "interleaved.vec");
4571 Instruction *NewStoreInstr;
4572 if (BlockInMask || MaskForGaps) {
4573 Value *GroupMask = CreateGroupMask(MaskForGaps);
4574 NewStoreInstr = State.Builder.CreateMaskedStore(
4575 Val: IVec, Ptr: ResAddr, Alignment: Group->getAlign(), Mask: GroupMask);
4576 } else
4577 NewStoreInstr =
4578 State.Builder.CreateAlignedStore(Val: IVec, Ptr: ResAddr, Align: Group->getAlign());
4579
4580 applyMetadata(I&: *NewStoreInstr);
4581 // TODO: Also manage existing metadata using VPIRMetadata.
4582 Group->addMetadata(NewInst: NewStoreInstr);
4583}
4584
4585#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4586void VPInterleaveRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
4587 VPSlotTracker &SlotTracker) const {
4588 const InterleaveGroup<Instruction> *IG = getInterleaveGroup();
4589 O << Indent << "INTERLEAVE-GROUP with factor " << IG->getFactor() << ", ";
4590 getAddr()->printAsOperand(O, SlotTracker);
4591 VPValue *Mask = getMask();
4592 if (Mask) {
4593 O << ", ";
4594 Mask->printAsOperand(O, SlotTracker);
4595 }
4596
4597 unsigned OpIdx = 0;
4598 for (unsigned i = 0; i < IG->getFactor(); ++i) {
4599 if (!IG->getMember(i))
4600 continue;
4601 if (getNumStoreOperands() > 0) {
4602 O << "\n" << Indent << " store ";
4603 getOperand(1 + OpIdx)->printAsOperand(O, SlotTracker);
4604 O << " to index " << i;
4605 } else {
4606 O << "\n" << Indent << " ";
4607 getVPValue(OpIdx)->printAsOperand(O, SlotTracker);
4608 O << " = load from index " << i;
4609 }
4610 ++OpIdx;
4611 }
4612}
4613#endif
4614
4615void VPInterleaveEVLRecipe::execute(VPTransformState &State) {
4616 assert(State.VF.isScalable() &&
4617 "Only support scalable VF for EVL tail-folding.");
4618 assert(!needsMaskForGaps() &&
4619 "Masking gaps for scalable vectors is not yet supported.");
4620 const InterleaveGroup<Instruction> *Group = getInterleaveGroup();
4621 Instruction *Instr = Group->getInsertPos();
4622
4623 // Prepare for the vector type of the interleaved load/store.
4624 Type *ScalarTy = getLoadStoreType(I: Instr);
4625 unsigned InterleaveFactor = Group->getFactor();
4626 assert(InterleaveFactor <= 8 &&
4627 "Unsupported deinterleave/interleave factor for scalable vectors");
4628 ElementCount WideVF = State.VF * InterleaveFactor;
4629 auto *VecTy = VectorType::get(ElementType: ScalarTy, EC: WideVF);
4630
4631 VPValue *Addr = getAddr();
4632 Value *ResAddr = State.get(Def: Addr, Lane: VPLane(0));
4633 Value *EVL = State.get(Def: getEVL(), Lane: VPLane(0));
4634 Value *InterleaveEVL = State.Builder.CreateMul(
4635 LHS: EVL, RHS: ConstantInt::get(Ty: EVL->getType(), V: InterleaveFactor), Name: "interleave.evl",
4636 /* NUW= */ HasNUW: true, /* NSW= */ HasNSW: true);
4637 LLVMContext &Ctx = State.Builder.getContext();
4638
4639 Value *GroupMask = nullptr;
4640 if (VPValue *BlockInMask = getMask()) {
4641 SmallVector<Value *> Ops(InterleaveFactor, State.get(Def: BlockInMask));
4642 GroupMask = interleaveVectors(Builder&: State.Builder, Vals: Ops, Name: "interleaved.mask");
4643 } else {
4644 GroupMask =
4645 State.Builder.CreateVectorSplat(EC: WideVF, V: State.Builder.getTrue());
4646 }
4647
4648 // Vectorize the interleaved load group.
4649 if (isa<LoadInst>(Val: Instr)) {
4650 CallInst *NewLoad = State.Builder.CreateIntrinsicWithoutFolding(
4651 RetTy: VecTy, ID: Intrinsic::vp_load, Args: {ResAddr, GroupMask, InterleaveEVL}, FMFSource: nullptr,
4652 Name: "wide.vp.load");
4653 NewLoad->addParamAttr(ArgNo: 0,
4654 Attr: Attribute::getWithAlignment(Context&: Ctx, Alignment: Group->getAlign()));
4655
4656 applyMetadata(I&: *NewLoad);
4657 // TODO: Also manage existing metadata using VPIRMetadata.
4658 Group->addMetadata(NewInst: NewLoad);
4659
4660 // Scalable vectors cannot use arbitrary shufflevectors (only splats),
4661 // so must use intrinsics to deinterleave.
4662 NewLoad = State.Builder.CreateIntrinsicWithoutFolding(
4663 ID: Intrinsic::getDeinterleaveIntrinsicID(Factor: InterleaveFactor),
4664 OverloadTypes: NewLoad->getType(), Args: NewLoad,
4665 /*FMFSource=*/nullptr, Name: "strided.vec");
4666
4667 const DataLayout &DL = Instr->getDataLayout();
4668 for (unsigned I = 0, J = 0; I < InterleaveFactor; ++I) {
4669 Instruction *Member = Group->getMember(Index: I);
4670 // Skip the gaps in the group.
4671 if (!Member)
4672 continue;
4673
4674 Value *StridedVec = State.Builder.CreateExtractValue(Agg: NewLoad, Idxs: I);
4675 // If this member has different type, cast the result type.
4676 if (Member->getType() != ScalarTy) {
4677 VectorType *OtherVTy = VectorType::get(ElementType: Member->getType(), EC: State.VF);
4678 StridedVec =
4679 createBitOrPointerCast(Builder&: State.Builder, V: StridedVec, DstVTy: OtherVTy, DL);
4680 }
4681
4682 State.set(Def: getVPValue(I: J), V: StridedVec);
4683 ++J;
4684 }
4685 return;
4686 } // End for interleaved load.
4687
4688 // The sub vector type for current instruction.
4689 auto *SubVT = VectorType::get(ElementType: ScalarTy, EC: State.VF);
4690 // Vectorize the interleaved store group.
4691 ArrayRef<VPValue *> StoredValues = getStoredValues();
4692 // Collect the stored vector from each member.
4693 SmallVector<Value *, 4> StoredVecs;
4694 const DataLayout &DL = Instr->getDataLayout();
4695 for (unsigned I = 0, StoredIdx = 0; I < InterleaveFactor; I++) {
4696 Instruction *Member = Group->getMember(Index: I);
4697 // Skip the gaps in the group.
4698 if (!Member) {
4699 StoredVecs.push_back(Elt: PoisonValue::get(T: SubVT));
4700 continue;
4701 }
4702
4703 Value *StoredVec = State.get(Def: StoredValues[StoredIdx]);
4704 // If this member has different type, cast it to a unified type.
4705 if (StoredVec->getType() != SubVT)
4706 StoredVec = createBitOrPointerCast(Builder&: State.Builder, V: StoredVec, DstVTy: SubVT, DL);
4707
4708 StoredVecs.push_back(Elt: StoredVec);
4709 ++StoredIdx;
4710 }
4711
4712 // Interleave all the smaller vectors into one wider vector.
4713 Value *IVec = interleaveVectors(Builder&: State.Builder, Vals: StoredVecs, Name: "interleaved.vec");
4714 CallInst *NewStore = State.Builder.CreateIntrinsicWithoutFolding(
4715 RetTy: Type::getVoidTy(C&: Ctx), ID: Intrinsic::vp_store,
4716 Args: {IVec, ResAddr, GroupMask, InterleaveEVL});
4717
4718 NewStore->addParamAttr(ArgNo: 1,
4719 Attr: Attribute::getWithAlignment(Context&: Ctx, Alignment: Group->getAlign()));
4720
4721 applyMetadata(I&: *NewStore);
4722 // TODO: Also manage existing metadata using VPIRMetadata.
4723 Group->addMetadata(NewInst: NewStore);
4724}
4725
4726#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4727void VPInterleaveEVLRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
4728 VPSlotTracker &SlotTracker) const {
4729 const InterleaveGroup<Instruction> *IG = getInterleaveGroup();
4730 O << Indent << "INTERLEAVE-GROUP with factor " << IG->getFactor() << ", ";
4731 getAddr()->printAsOperand(O, SlotTracker);
4732 O << ", ";
4733 getEVL()->printAsOperand(O, SlotTracker);
4734 if (VPValue *Mask = getMask()) {
4735 O << ", ";
4736 Mask->printAsOperand(O, SlotTracker);
4737 }
4738
4739 unsigned OpIdx = 0;
4740 for (unsigned i = 0; i < IG->getFactor(); ++i) {
4741 if (!IG->getMember(i))
4742 continue;
4743 if (getNumStoreOperands() > 0) {
4744 O << "\n" << Indent << " vp.store ";
4745 getOperand(2 + OpIdx)->printAsOperand(O, SlotTracker);
4746 O << " to index " << i;
4747 } else {
4748 O << "\n" << Indent << " ";
4749 getVPValue(OpIdx)->printAsOperand(O, SlotTracker);
4750 O << " = vp.load from index " << i;
4751 }
4752 ++OpIdx;
4753 }
4754}
4755#endif
4756
4757InstructionCost VPInterleaveBase::computeCost(ElementCount VF,
4758 VPCostContext &Ctx) const {
4759 Instruction *InsertPos = getInsertPos();
4760 // Find the VPValue index of the interleave group. We need to skip gaps.
4761 unsigned InsertPosIdx = 0;
4762 for (unsigned Idx = 0; IG->getFactor(); ++Idx)
4763 if (auto *Member = IG->getMember(Index: Idx)) {
4764 if (Member == InsertPos)
4765 break;
4766 InsertPosIdx++;
4767 }
4768 const VPValue *ValV = getNumDefinedValues() > 0
4769 ? getVPValue(I: InsertPosIdx)
4770 : getStoredValues()[InsertPosIdx];
4771 Type *ValTy = ValV->getScalarType();
4772 auto *VectorTy = cast<VectorType>(Val: toVectorTy(Scalar: ValTy, EC: VF));
4773 unsigned AS =
4774 cast<PointerType>(Val: getAddr()->getScalarType())->getAddressSpace();
4775
4776 unsigned InterleaveFactor = IG->getFactor();
4777 auto *WideVecTy = VectorType::get(ElementType: ValTy, EC: VF * InterleaveFactor);
4778
4779 // Holds the indices of existing members in the interleaved group.
4780 SmallVector<unsigned, 4> Indices;
4781 for (unsigned IF = 0; IF < InterleaveFactor; IF++)
4782 if (IG->getMember(Index: IF))
4783 Indices.push_back(Elt: IF);
4784
4785 // Calculate the cost of the whole interleaved group.
4786 InstructionCost Cost = Ctx.TTI.getInterleavedMemoryOpCost(
4787 Opcode: InsertPos->getOpcode(), VecTy: WideVecTy, Factor: IG->getFactor(), Indices,
4788 Alignment: IG->getAlign(), AddressSpace: AS, CostKind: Ctx.CostKind, UseMaskForCond: getMask(), UseMaskForGaps: NeedsMaskForGaps);
4789
4790 if (!IG->isReverse())
4791 return Cost;
4792
4793 return Cost + IG->getNumMembers() *
4794 Ctx.TTI.getShuffleCost(Kind: TargetTransformInfo::SK_Reverse,
4795 DstTy: VectorTy, SrcTy: VectorTy, Mask: {}, CostKind: Ctx.CostKind,
4796 Index: 0);
4797}
4798
4799bool VPWidenPointerInductionRecipe::onlyScalarsGenerated(bool IsScalable) {
4800 return vputils::onlyScalarValuesUsed(Def: this) &&
4801 (!IsScalable || vputils::onlyFirstLaneUsed(Def: this));
4802}
4803
4804#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4805void VPWidenPointerInductionRecipe::printRecipe(
4806 raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const {
4807 assert((getNumOperands() == 3 || getNumOperands() == 5) &&
4808 "unexpected number of operands");
4809 O << Indent << "EMIT ";
4810 printAsOperand(O, SlotTracker);
4811 O << " = WIDEN-POINTER-INDUCTION ";
4812 getStartValue()->printAsOperand(O, SlotTracker);
4813 O << ", ";
4814 getStepValue()->printAsOperand(O, SlotTracker);
4815 O << ", ";
4816 getOperand(2)->printAsOperand(O, SlotTracker);
4817 if (getNumOperands() == 5) {
4818 O << ", ";
4819 getOperand(3)->printAsOperand(O, SlotTracker);
4820 O << ", ";
4821 getOperand(4)->printAsOperand(O, SlotTracker);
4822 }
4823}
4824
4825void VPExpandSCEVRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
4826 VPSlotTracker &SlotTracker) const {
4827 O << Indent << "EMIT ";
4828 printAsOperand(O, SlotTracker);
4829 O << " = EXPAND SCEV " << *Expr;
4830}
4831#endif
4832
4833#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4834void VPWidenCanonicalIVRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
4835 VPSlotTracker &SlotTracker) const {
4836 O << Indent << "EMIT ";
4837 printAsOperand(O, SlotTracker);
4838 O << " = WIDEN-CANONICAL-INDUCTION";
4839 printFlags(O);
4840 printOperands(O, SlotTracker);
4841}
4842#endif
4843
4844void VPFirstOrderRecurrencePHIRecipe::execute(VPTransformState &State) {
4845 auto &Builder = State.Builder;
4846 // Create a vector from the initial value.
4847 auto *VectorInit = getStartValue()->getLiveInIRValue();
4848
4849 Type *VecTy = State.VF.isScalar()
4850 ? VectorInit->getType()
4851 : VectorType::get(ElementType: VectorInit->getType(), EC: State.VF);
4852
4853 BasicBlock *VectorPH =
4854 State.CFG.VPBB2IRBB.at(Val: getParent()->getCFGPredecessor(Idx: 0));
4855 if (State.VF.isVector()) {
4856 auto *IdxTy = Builder.getInt32Ty();
4857 auto *One = ConstantInt::get(Ty: IdxTy, V: 1);
4858 IRBuilder<>::InsertPointGuard Guard(Builder);
4859 Builder.SetInsertPoint(VectorPH->getTerminator());
4860 auto *RuntimeVF = getRuntimeVF(B&: Builder, Ty: IdxTy, VF: State.VF);
4861 auto *LastIdx = Builder.CreateSub(LHS: RuntimeVF, RHS: One);
4862 VectorInit = Builder.CreateInsertElement(
4863 Vec: PoisonValue::get(T: VecTy), NewElt: VectorInit, Idx: LastIdx, Name: "vector.recur.init");
4864 }
4865
4866 // Create a phi node for the new recurrence.
4867 PHINode *Phi = PHINode::Create(Ty: VecTy, NumReservedValues: 2, NameStr: "vector.recur");
4868 Phi->insertBefore(InsertPos: State.CFG.PrevBB->getFirstInsertionPt());
4869 Phi->addIncoming(V: VectorInit, BB: VectorPH);
4870 State.set(Def: this, V: Phi);
4871}
4872
4873InstructionCost
4874VPFirstOrderRecurrencePHIRecipe::computeCost(ElementCount VF,
4875 VPCostContext &Ctx) const {
4876 if (VF.isScalar())
4877 return Ctx.TTI.getCFInstrCost(Opcode: Instruction::PHI, CostKind: Ctx.CostKind);
4878
4879 return 0;
4880}
4881
4882#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4883void VPFirstOrderRecurrencePHIRecipe::printRecipe(
4884 raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const {
4885 O << Indent << "FIRST-ORDER-RECURRENCE-PHI ";
4886 printAsOperand(O, SlotTracker);
4887 O << " = phi ";
4888 printOperands(O, SlotTracker);
4889}
4890#endif
4891
4892void VPReductionPHIRecipe::execute(VPTransformState &State) {
4893 // Reductions do not have to start at zero. They can start with
4894 // any loop invariant values.
4895 VPValue *StartVPV = getStartValue();
4896
4897 // In order to support recurrences we need to be able to vectorize Phi nodes.
4898 // Phi nodes have cycles, so we need to vectorize them in two stages. This is
4899 // stage #1: We create a new vector PHI node with no incoming edges. We'll use
4900 // this value when we vectorize all of the instructions that use the PHI.
4901 BasicBlock *VectorPH =
4902 State.CFG.VPBB2IRBB.at(Val: getParent()->getCFGPredecessor(Idx: 0));
4903 bool ScalarPHI = State.VF.isScalar() || isInLoop();
4904 Value *StartV = State.get(Def: StartVPV, IsScalar: ScalarPHI);
4905 Type *VecTy = StartV->getType();
4906
4907 BasicBlock *HeaderBB = State.CFG.PrevBB;
4908 assert(State.CurrentParentLoop->getHeader() == HeaderBB &&
4909 "recipe must be in the vector loop header");
4910 auto *Phi = PHINode::Create(Ty: VecTy, NumReservedValues: 2, NameStr: "vec.phi");
4911 Phi->insertBefore(InsertPos: HeaderBB->getFirstInsertionPt());
4912 State.set(Def: this, V: Phi, IsScalar: isInLoop());
4913
4914 Phi->addIncoming(V: StartV, BB: VectorPH);
4915}
4916
4917#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4918void VPReductionPHIRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
4919 VPSlotTracker &SlotTracker) const {
4920 O << Indent << "WIDEN-REDUCTION-PHI ";
4921
4922 printAsOperand(O, SlotTracker);
4923 O << " = phi (";
4924 printRecurrenceKind(O, Kind);
4925 O << ")";
4926 printFlags(O);
4927 printOperands(O, SlotTracker);
4928 if (getVFScaleFactor() > 1)
4929 O << " (VF scaled by 1/" << getVFScaleFactor() << ")";
4930}
4931#endif
4932
4933bool VPBlendRecipe::usesFirstLaneOnly(const VPValue *Op) const {
4934 assert(is_contained(operands(), Op) && "Op must be an operand of the recipe");
4935 return vputils::onlyFirstLaneUsed(Def: this);
4936}
4937
4938void VPWidenPHIRecipe::execute(VPTransformState &State) {
4939 executePhiRecipe(R: this, Phi&: *this, State, /*IsScalar=*/false, Name);
4940}
4941
4942InstructionCost VPWidenPHIRecipe::computeCost(ElementCount VF,
4943 VPCostContext &Ctx) const {
4944 return Ctx.TTI.getCFInstrCost(Opcode: Instruction::PHI, CostKind: Ctx.CostKind);
4945}
4946
4947#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4948void VPWidenPHIRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
4949 VPSlotTracker &SlotTracker) const {
4950 O << Indent << "WIDEN-PHI ";
4951
4952 printAsOperand(O, SlotTracker);
4953 O << " = phi ";
4954 printPhiOperands(O, SlotTracker);
4955}
4956#endif
4957
4958void VPActiveLaneMaskPHIRecipe::execute(VPTransformState &State) {
4959 BasicBlock *VectorPH =
4960 State.CFG.VPBB2IRBB.at(Val: getParent()->getCFGPredecessor(Idx: 0));
4961 Value *StartMask = State.get(Def: getOperand(N: 0));
4962 PHINode *Phi =
4963 State.Builder.CreatePHI(Ty: StartMask->getType(), NumReservedValues: 2, Name: "active.lane.mask");
4964 Phi->addIncoming(V: StartMask, BB: VectorPH);
4965 State.set(Def: this, V: Phi);
4966}
4967
4968#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4969void VPActiveLaneMaskPHIRecipe::printRecipe(raw_ostream &O, const Twine &Indent,
4970 VPSlotTracker &SlotTracker) const {
4971 O << Indent << "ACTIVE-LANE-MASK-PHI ";
4972
4973 printAsOperand(O, SlotTracker);
4974 O << " = phi ";
4975 printOperands(O, SlotTracker);
4976}
4977#endif
4978
4979#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4980void VPCurrentIterationPHIRecipe::printRecipe(
4981 raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const {
4982 O << Indent << "CURRENT-ITERATION-PHI ";
4983
4984 printAsOperand(O, SlotTracker);
4985 O << " = phi ";
4986 printOperands(O, SlotTracker);
4987}
4988#endif
4989