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