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