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