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