1//===- LoopVectorizationPlanner.h - Planner for LoopVectorization ---------===//
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 provides a LoopVectorizationPlanner class.
11/// LoopVectorizationPlanner - drives the vectorization process after having
12/// passed Legality checks.
13/// The planner builds and optimizes the Vectorization Plans which record the
14/// decisions how to vectorize the given loop. In particular, represent the
15/// control-flow of the vectorized version, the replication of instructions that
16/// are to be scalarized, and interleave access groups.
17///
18/// Also provides a VPlan-based builder utility analogous to IRBuilder.
19/// It provides an instruction-level API for generating VPInstructions while
20/// abstracting away the Recipe manipulation details.
21//===----------------------------------------------------------------------===//
22
23#ifndef LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H
24#define LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H
25
26#include "VPlan.h"
27#include "VPlanUtils.h"
28#include "llvm/ADT/SmallSet.h"
29#include "llvm/Analysis/TargetTransformInfo.h"
30#include "llvm/Support/InstructionCost.h"
31#include <optional>
32
33namespace {
34class GeneratedRTChecks;
35}
36
37namespace llvm {
38
39class BranchProbabilityInfo;
40class LoopInfo;
41class DominatorTree;
42class LoopVectorizationLegality;
43class LoopVectorizationCostModel;
44class PredicatedScalarEvolution;
45class LoopVectorizeHints;
46class RecurrenceDescriptor;
47class OptimizationRemarkEmitter;
48class TargetLibraryInfo;
49struct VPRegisterUsage;
50struct VFRange;
51struct VectorizeOptions;
52
53/// \return An upper bound for vscale based on TTI or the vscale_range
54/// attribute.
55std::optional<unsigned> getMaxVScale(const Function &F);
56
57/// \return The upper bound for the runtime value of \p EC, or std::nullopt
58/// if the upper bound is unknown.
59std::optional<uint64_t>
60getMaxRuntimeElementCount(ElementCount EC, const Function &F);
61
62// Utility functions that are used by different vectorization classes
63namespace LoopVectorizationUtils {
64
65/// Reports a vectorization failure: print \p DebugMsg for debugging
66/// purposes along with the corresponding optimization remark \p RemarkName.
67/// If \p I is passed, it is an instruction that prevents vectorization.
68/// Otherwise, the loop \p TheLoop is used for the location of the remark.
69void reportVectorizationFailure(const StringRef DebugMsg,
70 const StringRef OREMsg, const StringRef ORETag,
71 OptimizationRemarkEmitter *ORE,
72 const Loop *TheLoop, Instruction *I = nullptr);
73
74/// Same as above, but the debug message and optimization remark are identical
75inline void reportVectorizationFailure(const StringRef DebugMsg,
76 const StringRef ORETag,
77 OptimizationRemarkEmitter *ORE,
78 const Loop *TheLoop,
79 Instruction *I = nullptr) {
80 reportVectorizationFailure(DebugMsg, OREMsg: DebugMsg, ORETag, ORE, TheLoop, I);
81}
82
83/// Reports an informative message: print \p Msg for debugging purposes as well
84/// as an optimization remark. Uses either \p I as location of the remark, or
85/// otherwise \p TheLoop. If \p DL is passed, use it as debug location for the
86/// remark.
87void reportVectorizationInfo(const StringRef Msg, const StringRef ORETag,
88 OptimizationRemarkEmitter *ORE,
89 const Loop *TheLoop, Instruction *I = nullptr,
90 DebugLoc DL = {});
91
92/// Report successful vectorization of the loop. In case an outer loop is
93/// vectorized, prepend "outer" to the vectorization remark.
94void reportVectorization(OptimizationRemarkEmitter *ORE, Loop *TheLoop,
95 ElementCount VFWidth, unsigned IC);
96
97} // namespace LoopVectorizationUtils
98
99/// Default inserter for VPBuilderBase, inserting \p R before \p It.
100struct VPBuilderDefaultInserter {
101 void insertHelper(VPRecipeBase *R, VPBasicBlock::iterator It) {
102 R->insertBefore(IP: It);
103 }
104};
105
106/// VPlan-based builder utility similar to IRBuilder. Recipes are inserted via
107/// \p InserterTy.
108template <typename InserterTy> class VPBuilderBase : public InserterTy {
109private:
110 class VPInsertPoint {
111 VPBasicBlock::iterator Iterator;
112
113 public:
114 /// Creates a new insertion point which doesn't point to anything.
115 VPInsertPoint() = default;
116
117 /// Creates a new insertion point to insert before \p Iterator.
118 VPInsertPoint(VPBasicBlock::iterator Iterator) : Iterator(Iterator) {}
119
120 /// Creates a new insertion point to insert before \p R.
121 VPInsertPoint(VPRecipeBase *R) : Iterator(R->getIterator()) {}
122
123 /// Creates a new insertion point to insert at the end of \p Block.
124 VPInsertPoint(VPBasicBlock *Block) : Iterator(Block->end()) {}
125
126 /// Returns true if this insert point is set.
127 operator bool() const { return Iterator.isValid(); }
128
129 VPBasicBlock *getBlock() const {
130 return Iterator.isValid() ? Iterator.getNodeParent() : nullptr;
131 }
132 VPBasicBlock::iterator getIterator() const { return Iterator; }
133
134 operator VPRecipeBase *() const {
135 return Iterator == getBlock()->end() ? nullptr : &*Iterator;
136 }
137 };
138
139 VPInsertPoint InsertPt;
140
141protected:
142 /// Insert \p R at InsertPt if InsertPt is set.
143 template <typename T> T *tryInsertInstruction(T *R) {
144 if (InsertPt)
145 InserterTy::insertHelper(R, InsertPt.getIterator());
146 return R;
147 }
148
149 VPInstruction *createInstruction(unsigned Opcode,
150 ArrayRef<VPValue *> Operands,
151 const VPIRMetadata &MD, DebugLoc DL,
152 const Twine &Name = "") {
153 return tryInsertInstruction(
154 new VPInstruction(Opcode, Operands, {}, MD, DL, Name));
155 }
156
157public:
158 VPlan &getPlan() const {
159 assert(InsertPt && "Insert block must be set");
160 return *InsertPt.getBlock()->getPlan();
161 }
162
163 VPBuilderBase() = default;
164 VPBuilderBase(const VPInsertPoint &IP) : InsertPt(IP) {}
165 VPBuilderBase(InserterTy Inserter) : InserterTy(Inserter) {}
166
167 /// Get the recipe at the current insert point or nullptr if the insert point
168 /// is the end of the block.
169 VPRecipeBase *getRecipeAtInsertPoint() const { return InsertPt; }
170
171 VPBasicBlock *getInsertBlock() const { return InsertPt.getBlock(); }
172
173 /// Create a builder to insert after \p R.
174 static VPBuilderBase getToInsertAfter(VPRecipeBase *R) {
175 return VPBuilderBase(std::next(x: R->getIterator()));
176 }
177
178 /// Sets the current insert point to a previously-saved location.
179 void restoreIP(VPInsertPoint IP) { InsertPt = IP; }
180
181 /// Set the current insert point.
182 void setInsertPoint(const VPInsertPoint &IP) {
183 assert(IP && "Attempting to set a null insert point");
184 InsertPt = IP;
185 }
186
187 /// Insert \p R at the current insertion point. Returns \p R unchanged.
188 template <typename T> [[maybe_unused]] T *insert(T *R) {
189 InserterTy::insertHelper(R, InsertPt.getIterator());
190 return R;
191 }
192
193 /// Create an N-ary operation with \p Opcode, \p Operands and set \p Inst as
194 /// its underlying Instruction.
195 VPInstruction *createNaryOp(unsigned Opcode, ArrayRef<VPValue *> Operands,
196 Instruction *Inst = nullptr,
197 const VPIRFlags &Flags = {},
198 const VPIRMetadata &MD = {},
199 DebugLoc DL = DebugLoc::getUnknown(),
200 const Twine &Name = "", Type *ResultTy = nullptr,
201 const VPIRAttributes &Attrs = {}) {
202 VPInstruction *NewVPInst = tryInsertInstruction(new VPInstruction(
203 Opcode, Operands, Flags, MD, DL, Name, ResultTy, Attrs));
204 NewVPInst->setUnderlyingValue(Inst);
205 return NewVPInst;
206 }
207 VPInstruction *createNaryOp(unsigned Opcode, ArrayRef<VPValue *> Operands,
208 DebugLoc DL, const Twine &Name = "") {
209 return createInstruction(Opcode, Operands, MD: {}, DL, Name);
210 }
211 VPInstruction *createNaryOp(unsigned Opcode, ArrayRef<VPValue *> Operands,
212 const VPIRFlags &Flags,
213 DebugLoc DL = DebugLoc::getUnknown(),
214 const Twine &Name = "") {
215 return tryInsertInstruction(
216 new VPInstruction(Opcode, Operands, Flags, {}, DL, Name));
217 }
218
219 VPInstruction *createNaryOp(unsigned Opcode, ArrayRef<VPValue *> Operands,
220 Type *ResultTy, const VPIRFlags &Flags = {},
221 DebugLoc DL = DebugLoc::getUnknown(),
222 const Twine &Name = "") {
223 return tryInsertInstruction(
224 new VPInstruction(Opcode, Operands, Flags, {}, DL, Name, ResultTy));
225 }
226
227 VPInstruction *createFirstActiveLane(ArrayRef<VPValue *> Masks,
228 DebugLoc DL = DebugLoc::getUnknown(),
229 const Twine &Name = "") {
230 // Assume that the maximum possible number of elements in a vector fits
231 // within the index type for the default address space.
232 VPlan &Plan = getPlan();
233 Type *IndexTy = Plan.getDataLayout().getIndexType(C&: Plan.getContext(), AddressSpace: 0);
234 return tryInsertInstruction(new VPInstruction(
235 VPInstruction::FirstActiveLane, Masks, {}, {}, DL, Name, IndexTy));
236 }
237
238 VPInstruction *createLastActiveLane(ArrayRef<VPValue *> Masks,
239 DebugLoc DL = DebugLoc::getUnknown(),
240 const Twine &Name = "") {
241 // Assume that the maximum possible number of elements in a vector fits
242 // within the index type for the default address space.
243 VPlan &Plan = getPlan();
244 Type *IndexTy = Plan.getDataLayout().getIndexType(C&: Plan.getContext(), AddressSpace: 0);
245 return tryInsertInstruction(new VPInstruction(
246 VPInstruction::LastActiveLane, Masks, {}, {}, DL, Name, IndexTy));
247 }
248
249 VPInstruction *createOverflowingOp(
250 unsigned Opcode, ArrayRef<VPValue *> Operands,
251 VPRecipeWithIRFlags::WrapFlagsTy WrapFlags = {false, false},
252 DebugLoc DL = DebugLoc::getUnknown(), const Twine &Name = "") {
253 return tryInsertInstruction(
254 new VPInstruction(Opcode, Operands, WrapFlags, {}, DL, Name));
255 }
256
257 VPInstruction *createNot(VPValue *Operand,
258 DebugLoc DL = DebugLoc::getUnknown(),
259 const Twine &Name = "") {
260 return createInstruction(Opcode: VPInstruction::Not, Operands: {Operand}, MD: {}, DL, Name);
261 }
262
263 VPInstruction *createAnd(VPValue *LHS, VPValue *RHS,
264 DebugLoc DL = DebugLoc::getUnknown(),
265 const Twine &Name = "") {
266 return createInstruction(Opcode: Instruction::BinaryOps::And, Operands: {LHS, RHS}, MD: {}, DL,
267 Name);
268 }
269
270 VPInstruction *createOr(VPValue *LHS, VPValue *RHS,
271 DebugLoc DL = DebugLoc::getUnknown(),
272 const Twine &Name = "") {
273
274 return tryInsertInstruction(new VPInstruction(
275 Instruction::BinaryOps::Or, {LHS, RHS},
276 VPRecipeWithIRFlags::DisjointFlagsTy(false), {}, DL, Name));
277 }
278
279 VPInstruction *
280 createAdd(VPValue *LHS, VPValue *RHS, DebugLoc DL = DebugLoc::getUnknown(),
281 const Twine &Name = "",
282 VPRecipeWithIRFlags::WrapFlagsTy WrapFlags = {false, false}) {
283 return createOverflowingOp(Opcode: Instruction::Add, Operands: {LHS, RHS}, WrapFlags, DL,
284 Name);
285 }
286
287 VPInstruction *
288 createSub(VPValue *LHS, VPValue *RHS, DebugLoc DL = DebugLoc::getUnknown(),
289 const Twine &Name = "",
290 VPRecipeWithIRFlags::WrapFlagsTy WrapFlags = {false, false}) {
291 return createOverflowingOp(Opcode: Instruction::Sub, Operands: {LHS, RHS}, WrapFlags, DL,
292 Name);
293 }
294
295 VPInstruction *createLogicalAnd(VPValue *LHS, VPValue *RHS,
296 DebugLoc DL = DebugLoc::getUnknown(),
297 const Twine &Name = "") {
298 return createNaryOp(VPInstruction::LogicalAnd, {LHS, RHS}, DL, Name);
299 }
300
301 VPInstruction *createLogicalOr(VPValue *LHS, VPValue *RHS,
302 DebugLoc DL = DebugLoc::getUnknown(),
303 const Twine &Name = "") {
304 return createNaryOp(VPInstruction::LogicalOr, {LHS, RHS}, DL, Name);
305 }
306
307 /// Create a select of \p TrueVal and \p FalseVal based on \p Cond, using the
308 /// default flags for the result type, unless \p Flags is set.
309 VPInstruction *createSelect(VPValue *Cond, VPValue *TrueVal,
310 VPValue *FalseVal,
311 DebugLoc DL = DebugLoc::getUnknown(),
312 const Twine &Name = "",
313 std::optional<VPIRFlags> Flags = std::nullopt) {
314 return tryInsertInstruction(
315 new VPInstruction(Instruction::Select, {Cond, TrueVal, FalseVal},
316 Flags.value_or(u: VPIRFlags::getDefaultFlags(
317 Opcode: Instruction::Select, ResultTy: TrueVal->getScalarType())),
318 {}, DL, Name));
319 }
320
321 /// Create a new ICmp VPInstruction with predicate \p Pred and operands \p A
322 /// and \p B.
323 VPInstruction *createICmp(CmpInst::Predicate Pred, VPValue *A, VPValue *B,
324 DebugLoc DL = DebugLoc::getUnknown(),
325 const Twine &Name = "") {
326 assert(Pred >= CmpInst::FIRST_ICMP_PREDICATE &&
327 Pred <= CmpInst::LAST_ICMP_PREDICATE && "invalid predicate");
328 return tryInsertInstruction(
329 new VPInstruction(Instruction::ICmp, {A, B}, Pred, {}, DL, Name));
330 }
331
332 /// Create a new FCmp VPInstruction with predicate \p Pred and operands \p A
333 /// and \p B.
334 VPInstruction *createFCmp(CmpInst::Predicate Pred, VPValue *A, VPValue *B,
335 DebugLoc DL = DebugLoc::getUnknown(),
336 const Twine &Name = "") {
337 assert(Pred >= CmpInst::FIRST_FCMP_PREDICATE &&
338 Pred <= CmpInst::LAST_FCMP_PREDICATE && "invalid predicate");
339 return tryInsertInstruction(
340 new VPInstruction(Instruction::FCmp, {A, B},
341 VPIRFlags(Pred, FastMathFlags()), {}, DL, Name));
342 }
343
344 /// Create an AnyOf reduction pattern: or-reduce \p ChainOp, freeze the
345 /// result, then select between \p TrueVal and \p FalseVal.
346 VPInstruction *createAnyOfReduction(VPValue *ChainOp, VPValue *TrueVal,
347 VPValue *FalseVal,
348 DebugLoc DL = DebugLoc::getUnknown()) {
349 assert(ChainOp->getScalarType()->isIntegerTy(1) &&
350 "ChainOp must be i1 for AnyOf reduction");
351 VPIRFlags Flags(RecurKind::Or, /*IsOrdered=*/false, /*IsInLoop=*/false,
352 FastMathFlags());
353 auto *OrReduce = createNaryOp(VPInstruction::ComputeReductionResult,
354 {ChainOp}, Flags, DL);
355 auto *Freeze = createNaryOp(Instruction::Freeze, {OrReduce}, DL);
356 return createSelect(Cond: Freeze, TrueVal, FalseVal, DL, Name: "rdx.select");
357 }
358
359 VPInstruction *createPtrAdd(VPValue *Ptr, VPValue *Offset,
360 DebugLoc DL = DebugLoc::getUnknown(),
361 const Twine &Name = "") {
362 return createNoWrapPtrAdd(Ptr, Offset, GEPFlags: GEPNoWrapFlags::none(), DL, Name);
363 }
364
365 VPInstruction *createNoWrapPtrAdd(VPValue *Ptr, VPValue *Offset,
366 GEPNoWrapFlags GEPFlags,
367 DebugLoc DL = DebugLoc::getUnknown(),
368 const Twine &Name = "") {
369 return tryInsertInstruction(new VPInstruction(
370 VPInstruction::PtrAdd, {Ptr, Offset}, GEPFlags, {}, DL, Name));
371 }
372
373 VPInstruction *createWidePtrAdd(VPValue *Ptr, VPValue *Offset,
374 DebugLoc DL = DebugLoc::getUnknown(),
375 const Twine &Name = "") {
376 return tryInsertInstruction(
377 new VPInstruction(VPInstruction::WidePtrAdd, {Ptr, Offset},
378 GEPNoWrapFlags::none(), {}, DL, Name));
379 }
380
381 /// Create a phi with \p IncomingValues, using the default flags for the
382 /// result type, unless \p Flags is set.
383 VPPhi *createScalarPhi(ArrayRef<VPValue *> IncomingValues,
384 DebugLoc DL = DebugLoc::getUnknown(),
385 const Twine &Name = "",
386 std::optional<VPIRFlags> Flags = std::nullopt,
387 Type *ResultTy = nullptr) {
388 Type *ScalarTy = ResultTy ? ResultTy : IncomingValues[0]->getScalarType();
389 return tryInsertInstruction(new VPPhi(
390 IncomingValues,
391 Flags.value_or(u: VPIRFlags::getDefaultFlags(Opcode: Instruction::PHI, ResultTy: ScalarTy)),
392 DL, Name, ResultTy));
393 }
394
395 VPWidenPHIRecipe *createWidenPhi(ArrayRef<VPValue *> IncomingValues,
396 DebugLoc DL = DebugLoc::getUnknown(),
397 const Twine &Name = "") {
398 return tryInsertInstruction(new VPWidenPHIRecipe(IncomingValues, DL, Name));
399 }
400
401 VPValue *createElementCount(Type *Ty, ElementCount EC) {
402 VPlan &Plan = getPlan();
403 unsigned MinEC = EC.getKnownMinValue();
404 if (EC.isScalable()) {
405 VPValue *VScale = createVScale(ResultTy: Ty);
406 if (MinEC == 1)
407 return VScale;
408 // TODO: Move this optimization into createOverflowingOp directly.
409 if (isPowerOf2_32(Value: MinEC)) {
410 VPValue *ShtAmt = Plan.getConstantInt(Ty, Val: Log2_32(Value: MinEC));
411 return createOverflowingOp(Opcode: Instruction::Shl, Operands: {VScale, ShtAmt},
412 WrapFlags: {true, false});
413 }
414 VPValue *MulAmt = Plan.getConstantInt(Ty, Val: MinEC);
415 return createOverflowingOp(Opcode: Instruction::Mul, Operands: {VScale, MulAmt},
416 WrapFlags: {true, false});
417 }
418 return Plan.getConstantInt(Ty, Val: MinEC);
419 }
420
421 /// Convert \p Current to \p Start + \p Current * \p Step.
422 VPDerivedIVRecipe *createDerivedIV(InductionDescriptor::InductionKind Kind,
423 FPMathOperator *FPBinOp, VPValue *Start,
424 VPValue *Current, VPValue *Step,
425 const VPIRFlags::WrapFlagsTy &Flags = {}) {
426 return tryInsertInstruction(
427 new VPDerivedIVRecipe(Kind, FPBinOp, Start, Current, Step, Flags));
428 }
429
430 VPInstruction *createScalarCast(Instruction::CastOps Opcode, VPValue *Op,
431 Type *ResultTy, DebugLoc DL,
432 std::optional<VPIRFlags> Flags = std::nullopt,
433 const VPIRMetadata &Metadata = {}) {
434 return tryInsertInstruction(new VPInstruction(
435 Opcode, Op, Flags.value_or(u: VPIRFlags::getDefaultFlags(Opcode)),
436 Metadata, DL, "", ResultTy));
437 }
438
439 /// Create a scalar call to the intrinsic \p IntrinsicID with \p Operands, and
440 /// result type \p ResultTy
441 VPInstruction *createScalarIntrinsic(Intrinsic::ID IntrinsicID,
442 ArrayRef<VPValue *> Operands,
443 Type *ResultTy, DebugLoc DL,
444 const Twine &Name = "") {
445 VPlan &Plan = getPlan();
446 SmallVector<VPValue *, 2> Ops(Operands);
447 Ops.push_back(Elt: Plan.getConstantInt(BitWidth: 8 * sizeof(IntrinsicID), Val: IntrinsicID));
448 return tryInsertInstruction(new VPInstruction(VPInstruction::Intrinsic, Ops,
449 {}, {}, DL, Name, ResultTy));
450 }
451
452 /// Create a scalar llvm.vscale call.
453 VPInstruction *createVScale(Type *ResultTy,
454 DebugLoc DL = DebugLoc::getUnknown()) {
455 return createScalarIntrinsic(IntrinsicID: Intrinsic::vscale, Operands: {}, ResultTy, DL);
456 }
457
458 VPValue *createScalarZExtOrTrunc(VPValue *Op, Type *ResultTy, DebugLoc DL) {
459 Type *SrcTy = Op->getScalarType();
460 if (ResultTy == SrcTy)
461 return Op;
462 Instruction::CastOps CastOp =
463 ResultTy->getScalarSizeInBits() < SrcTy->getScalarSizeInBits()
464 ? Instruction::Trunc
465 : Instruction::ZExt;
466 return createScalarCast(Opcode: CastOp, Op, ResultTy, DL);
467 }
468
469 VPValue *createScalarSExtOrTrunc(VPValue *Op, Type *ResultTy, DebugLoc DL) {
470 Type *SrcTy = Op->getScalarType();
471 if (ResultTy == SrcTy)
472 return Op;
473 Instruction::CastOps CastOp =
474 ResultTy->getScalarSizeInBits() < SrcTy->getScalarSizeInBits()
475 ? Instruction::Trunc
476 : Instruction::SExt;
477 return createScalarCast(Opcode: CastOp, Op, ResultTy, DL);
478 }
479
480 VPInstruction *createFreeze(VPValue *Op, DebugLoc DL = DebugLoc::getUnknown(),
481 const Twine &Name = "") {
482 return createNaryOp(Instruction::Freeze, Op, DL, Name);
483 }
484
485 VPWidenCastRecipe *createWidenCast(Instruction::CastOps Opcode, VPValue *Op,
486 Type *ResultTy) {
487 assert(Op->getScalarType() != ResultTy &&
488 "must not create a no-op cast recipe");
489 return tryInsertInstruction(new VPWidenCastRecipe(
490 Opcode, Op, ResultTy, nullptr, VPIRFlags::getDefaultFlags(Opcode)));
491 }
492
493 /// Create a single-scalar recipe with \p Opcode and \p Operands without
494 /// inserting it.
495 static VPSingleDefRecipe *
496 createSingleScalarOp(unsigned Opcode, ArrayRef<VPValue *> Operands,
497 VPValue *Mask, const VPIRFlags &Flags,
498 const VPIRMetadata &Metadata, DebugLoc DL,
499 Type *ResultTy, Instruction *UV) {
500 if (Instruction::isCast(Opcode)) {
501 assert(!Mask && "Cast cannot be predicated");
502 auto *VPI = new VPInstruction(Opcode, Operands, Flags, Metadata, DL,
503 UV->getName(), ResultTy);
504 VPI->setUnderlyingValue(UV);
505 return VPI;
506 }
507 auto *RepR = new VPReplicateRecipe(UV, Operands, /*IsSingleScalar=*/true,
508 Mask, Flags, Metadata, DL);
509 assert(RepR->getScalarType() == ResultTy && "unexpected result type");
510 return RepR;
511 }
512
513 VPScalarIVStepsRecipe *
514 createScalarIVSteps(Instruction::BinaryOps InductionOpcode,
515 FPMathOperator *FPBinOp, VPValue *IV, VPValue *Step,
516 VPValue *VF, DebugLoc DL) {
517 return tryInsertInstruction(new VPScalarIVStepsRecipe(
518 IV, Step, VF, InductionOpcode,
519 FPBinOp ? FPBinOp->getFastMathFlags() : FastMathFlags(), DL));
520 }
521
522 VPExpandSCEVRecipe *createExpandSCEV(const SCEV *Expr) {
523 return tryInsertInstruction(new VPExpandSCEVRecipe(Expr));
524 }
525
526 VPVectorPointerRecipe *
527 createVectorPointer(VPValue *Ptr, Type *SourceElementTy, VPValue *Stride,
528 GEPNoWrapFlags GEPFlags, DebugLoc DL) {
529 return tryInsertInstruction(
530 new VPVectorPointerRecipe(Ptr, SourceElementTy, Stride, GEPFlags, DL));
531 }
532
533 /// Create a vector pointer recipe for a consecutive memory access to \p Ptr
534 /// with element type \p SourceElementTy.
535 VPSingleDefRecipe *createConsecutiveVectorPointer(VPValue *Ptr,
536 Type *SourceElementTy,
537 bool Reverse, DebugLoc DL) {
538 VPlan &Plan = getPlan();
539 GEPNoWrapFlags Flags = vputils::getGEPFlagsForPtr(Ptr);
540 if (Reverse) {
541 // When folding the tail, we may compute an address that we don't in the
542 // original scalar loop: drop the GEP no-wrap flags in this case.
543 // Otherwise preserve existing flags without no-unsigned-wrap, as we will
544 // emit negative indices.
545 GEPNoWrapFlags ReverseFlags = Plan.hasTailFolded()
546 ? GEPNoWrapFlags::none()
547 : Flags.withoutNoUnsignedWrap();
548 return tryInsertInstruction(
549 new VPVectorEndPointerRecipe(Ptr, &Plan.getVF(), SourceElementTy,
550 /*Stride=*/-1, ReverseFlags, DL));
551 }
552 Type *StrideTy = Plan.getDataLayout().getIndexType(PtrTy: Ptr->getScalarType());
553 VPValue *StrideOne = Plan.getConstantInt(Ty: StrideTy, Val: 1);
554 return createVectorPointer(Ptr, SourceElementTy, Stride: StrideOne, GEPFlags: Flags, DL);
555 }
556
557 VPWidenIntrinsicRecipe *
558 createWidenIntrinsic(Intrinsic::ID VectorIntrinsicID,
559 ArrayRef<VPValue *> CallArguments, Type *Ty,
560 const VPIRFlags &Flags = {}, const VPIRMetadata &MD = {},
561 DebugLoc DL = DebugLoc::getUnknown()) {
562 return tryInsertInstruction(new VPWidenIntrinsicRecipe(
563 VectorIntrinsicID, CallArguments, Ty, Flags, MD, DL));
564 }
565
566 VPWidenMemIntrinsicRecipe *createWidenMemIntrinsic(
567 Intrinsic::ID VectorIntrinsicID, ArrayRef<VPValue *> CallArguments,
568 Type *Ty, Align Alignment, const VPIRMetadata &MD, DebugLoc DL) {
569 return tryInsertInstruction(new VPWidenMemIntrinsicRecipe(
570 VectorIntrinsicID, CallArguments, Ty, Alignment, MD, DL));
571 }
572
573 /// Create a recipe widening \p Load, loading from \p Addr with \p Mask (may
574 /// be null).
575 VPWidenLoadRecipe *createWidenLoad(LoadInst &Load, VPValue *Addr,
576 VPValue *Mask, bool Consecutive,
577 Align Alignment,
578 const VPIRMetadata &Metadata,
579 DebugLoc DL) {
580 return tryInsertInstruction(new VPWidenLoadRecipe(
581 Load, Addr, Mask, Consecutive, Alignment, Metadata, DL));
582 }
583
584 /// Create a recipe widening \p Store, storing \p StoredVal to \p Addr with
585 /// \p Mask (may be null).
586 VPWidenStoreRecipe *createWidenStore(StoreInst &Store, VPValue *Addr,
587 VPValue *StoredVal, VPValue *Mask,
588 bool Consecutive, Align Alignment,
589 const VPIRMetadata &Metadata,
590 DebugLoc DL) {
591 return tryInsertInstruction(new VPWidenStoreRecipe(
592 Store, Addr, StoredVal, Mask, Consecutive, Alignment, Metadata, DL));
593 }
594
595 //===--------------------------------------------------------------------===//
596 // RAII helpers.
597 //===--------------------------------------------------------------------===//
598
599 /// RAII object that stores the current insertion point and restores it when
600 /// the object is destroyed.
601 class InsertPointGuard {
602 VPBuilderBase &Builder;
603 VPInsertPoint InsertPt;
604
605 public:
606 InsertPointGuard(VPBuilderBase &B) : Builder(B), InsertPt(B.InsertPt) {}
607
608 InsertPointGuard(const InsertPointGuard &) = delete;
609 InsertPointGuard &operator=(const InsertPointGuard &) = delete;
610
611 ~InsertPointGuard() { Builder.restoreIP(IP: InsertPt); }
612 };
613};
614
615/// TODO: The following VectorizationFactor was pulled out of
616/// LoopVectorizationCostModel class. LV also deals with
617/// VectorizerParams::VectorizationFactor.
618/// We need to streamline them.
619
620/// Information about vectorization costs.
621struct VectorizationFactor {
622 /// Vector width with best cost.
623 ElementCount Width;
624
625 /// Cost of the loop with that width.
626 InstructionCost Cost;
627
628 /// Cost of the scalar loop.
629 InstructionCost ScalarCost;
630
631 /// The minimum trip count required to make vectorization profitable, e.g. due
632 /// to runtime checks.
633 ElementCount MinProfitableTripCount;
634
635 VectorizationFactor(ElementCount Width, InstructionCost Cost,
636 InstructionCost ScalarCost)
637 : Width(Width), Cost(Cost), ScalarCost(ScalarCost) {}
638
639 /// Width 1 means no vectorization, cost 0 means uncomputed cost.
640 static VectorizationFactor Disabled() {
641 return {ElementCount::getFixed(MinVal: 1), 0, 0};
642 }
643};
644
645/// A class that represents two vectorization factors (initialized with 0 by
646/// default). One for fixed-width vectorization and one for scalable
647/// vectorization. This can be used by the vectorizer to choose from a range of
648/// fixed and/or scalable VFs in order to find the most cost-effective VF to
649/// vectorize with.
650struct FixedScalableVFPair {
651 ElementCount FixedVF;
652 ElementCount ScalableVF;
653
654 FixedScalableVFPair()
655 : FixedVF(ElementCount::getFixed(MinVal: 0)),
656 ScalableVF(ElementCount::getScalable(MinVal: 0)) {}
657 FixedScalableVFPair(const ElementCount &Max) : FixedScalableVFPair() {
658 *(Max.isScalable() ? &ScalableVF : &FixedVF) = Max;
659 }
660 FixedScalableVFPair(const ElementCount &FixedVF,
661 const ElementCount &ScalableVF)
662 : FixedVF(FixedVF), ScalableVF(ScalableVF) {
663 assert(!FixedVF.isScalable() && ScalableVF.isScalable() &&
664 "Invalid scalable properties");
665 }
666
667 static FixedScalableVFPair getNone() { return FixedScalableVFPair(); }
668
669 /// \return true if either fixed- or scalable VF is non-zero.
670 explicit operator bool() const { return FixedVF || ScalableVF; }
671};
672
673/// Holds state needed to make cost decisions before computing costs per-VF,
674/// including the maximum VFs.
675class VFSelectionContext {
676 using VectorKind = TargetTransformInfo::VectorKind;
677 /// \return True if maximizing vector bandwidth is enabled by the target or
678 /// user options, for the given register kind (scalable or fixed-width).
679 bool useMaxBandwidth(VectorKind Kind, Type *ElementTy = nullptr) const;
680 bool useMaxBandwidth(bool IsScalable, Type *ElementTy = nullptr) const {
681 return useMaxBandwidth(
682 Kind: IsScalable ? VectorKind::Scalable : VectorKind::FixedWidth, ElementTy);
683 }
684
685 struct TypeWidths {
686 unsigned SmallestTypeForMaxBandwidth;
687 unsigned SmallestType;
688 unsigned WidestType;
689 };
690
691 /// \return The size (in bits) of the of the types used to determine the
692 /// possible VFs. That is the widest type in the loop and the smallest type
693 /// the target wants to maximize vector bandwidth for. We ignore values that
694 /// remain scalar such as 64 bit loop indices.
695 TypeWidths getTypeWidthsForVFSelection() const;
696
697 /// \return the maximized element count based on the targets vector
698 /// registers and the loop trip-count, but limited to a maximum safe VF.
699 /// This is a helper function of computeFeasibleMaxVF.
700 ElementCount getMaximizedVFForTarget(unsigned MaxTripCount,
701 const TypeWidths &TyWidths,
702 ElementCount MaxSafeVF, unsigned UserIC,
703 bool FoldTailByMasking,
704 bool RequiresScalarEpilogue);
705
706 /// If \p VF * \p UserIC > MaxTripcount, clamps VF to the next lower VF
707 /// that results in VF * UserIC <= MaxTripCount.
708 ElementCount clampVFByMaxTripCount(ElementCount VF, unsigned MaxTripCount,
709 unsigned UserIC, bool FoldTailByMasking,
710 bool RequiresScalarEpilogue) const;
711
712 /// Checks if scalable vectorization is supported and enabled. Caches the
713 /// result to avoid repeated debug dumps for repeated queries.
714 bool isScalableVectorizationAllowed();
715
716 /// \return the maximum legal scalable VF, based on the safe max number
717 /// of elements.
718 ElementCount getMaxLegalScalableVF(unsigned MaxSafeElements);
719
720 /// Initializes the value of vscale used for tuning the cost model. If
721 /// vscale_range.min == vscale_range.max then return vscale_range.max, else
722 /// return the value returned by the corresponding TTI method.
723 void initializeVScaleForTuning();
724
725 const VectorizeOptions &Opts;
726 const TargetTransformInfo &TTI;
727 const LoopVectorizationLegality *Legal;
728 const Loop *TheLoop;
729 const Function &F;
730 PredicatedScalarEvolution &PSE;
731 DemandedBits *DB;
732 OptimizationRemarkEmitter *ORE;
733 const LoopVectorizeHints *Hints;
734
735 /// Cached result of isScalableVectorizationAllowed.
736 std::optional<bool> IsScalableVectorizationAllowed;
737
738 /// Used to store the value of vscale used for tuning the cost model. It is
739 /// initialized during object construction.
740 std::optional<unsigned> VScaleForTuning;
741
742 /// The highest VF possible for this loop, without using MaxBandwidth.
743 FixedScalableVFPair MaxPermissibleVFWithoutMaxBW;
744
745 /// All element types found in the loop.
746 SmallPtrSet<Type *, 16> ElementTypesInLoop;
747
748 /// PHINodes of the reductions that should be expanded in-loop. Set by
749 /// collectInLoopReductions.
750 SmallPtrSet<PHINode *, 4> InLoopReductions;
751
752 /// Maximum safe number of elements to be processed per vector iteration,
753 /// which do not prevent store-load forwarding and are safe with regard to the
754 /// memory dependencies. Required for EVL-based vectorization, where this
755 /// value is used as the upper bound of the safe AVL. Set by
756 /// computeFeasibleMaxVF.
757 std::optional<unsigned> MaxSafeElements;
758
759 /// Map of scalar integer values to the smallest bitwidth they can be legally
760 /// represented as. The vector equivalents of these values should be truncated
761 /// to this type.
762 MapVector<Instruction *, uint64_t> MinBWs;
763
764public:
765 /// The kind of cost that we are calculating.
766 const TTI::TargetCostKind CostKind;
767
768 /// Whether this loop should be optimized for size based on function attribute
769 /// or profile information.
770 const bool OptForSize;
771
772 VFSelectionContext(const VectorizeOptions &Opts,
773 const TargetTransformInfo &TTI,
774 const LoopVectorizationLegality *Legal,
775 const Loop *TheLoop, const Function &F,
776 PredicatedScalarEvolution &PSE, DemandedBits *DB,
777 OptimizationRemarkEmitter *ORE,
778 const LoopVectorizeHints *Hints, bool OptForSize)
779 : Opts(Opts), TTI(TTI), Legal(Legal), TheLoop(TheLoop), F(F), PSE(PSE),
780 DB(DB), ORE(ORE), Hints(Hints),
781 CostKind(F.hasMinSize() ? TTI::TCK_CodeSize : TTI::TCK_RecipThroughput),
782 OptForSize(OptForSize) {
783 initializeVScaleForTuning();
784 }
785
786 /// \return The vscale value used for tuning the cost model.
787 std::optional<unsigned> getVScaleForTuning() const { return VScaleForTuning; }
788
789 const VectorizeOptions &getOpts() const { return Opts; }
790
791 const TargetTransformInfo &getTTI() const { return TTI; }
792
793 PredicatedScalarEvolution &getPSE() const { return PSE; }
794
795 /// \return The loop being analyzed.
796 const Loop *getLoop() const { return TheLoop; }
797
798 /// \return The vectorization hints for the loop being analyzed.
799 const LoopVectorizeHints &getHints() const { return *Hints; }
800
801 /// Returns true if epilogue vectorization is considered profitable for a
802 /// main loop with vectorization factor \p VF and interleave count \p IC.
803 bool isEpilogueVectorizationProfitable(ElementCount VF, unsigned IC) const;
804
805 /// \return True if register pressure should be considered for the given VF.
806 bool shouldConsiderRegPressureForVF(ElementCount VF) const;
807
808 /// \return True if scalable vectors are supported by the target or forced.
809 bool supportsScalableVectors() const;
810
811 /// Collect element types in the loop that need widening.
812 void collectElementTypesForWidening(
813 const SmallPtrSetImpl<const Value *> *ValuesToIgnore = nullptr);
814
815 /// \return An upper bound for the vectorization factors for both
816 /// fixed and scalable vectorization, where the minimum-known number of
817 /// elements is a power-of-2 larger than zero. If scalable vectorization is
818 /// disabled or unsupported, then the scalable part will be equal to
819 /// ElementCount::getScalable(0). Also sets MaxSafeElements.
820 FixedScalableVFPair computeFeasibleMaxVF(unsigned MaxTripCount,
821 ElementCount UserVF, unsigned UserIC,
822 bool FoldTailByMasking,
823 bool RequiresScalarEpilogue);
824
825 /// Return maximum safe number of elements to be processed per vector
826 /// iteration, which do not prevent store-load forwarding and are safe with
827 /// regard to the memory dependencies. Required for EVL-based VPlans to
828 /// correctly calculate AVL (application vector length) as min(remaining AVL,
829 /// MaxSafeElements). Set by computeFeasibleMaxVF.
830 /// TODO: need to consider adjusting cost model to use this value as a
831 /// vectorization factor for EVL-based vectorization.
832 std::optional<unsigned> getMaxSafeElements() const { return MaxSafeElements; }
833
834 /// Returns true if we should use strict in-order reductions for the given
835 /// RdxDesc. This is true if the -enable-strict-reductions flag is passed,
836 /// the IsOrdered flag of RdxDesc is set and we do not allow reordering
837 /// of FP operations.
838 bool useOrderedReductions(const RecurrenceDescriptor &RdxDesc) const;
839
840 /// Returns true if the target machine supports a masked load (if \p IsLoad)
841 /// or masked store of scalar type \p ScalarTy with \p Alignment in address
842 /// space \p AddressSpace. The caller must ensure the access is consecutive or
843 /// part of an interleave group.
844 bool isLegalMaskedLoadOrStore(bool IsLoad, Type *ScalarTy, Align Alignment,
845 unsigned AddressSpace) const;
846
847 /// Returns true if the target machine supports a gather (if \p IsLoad)
848 /// or scatter of scalar type \p ScalarTy with \p Alignment for vectorization
849 /// factor \p VF.
850 bool isLegalGatherOrScatter(bool IsLoad, Type *ScalarTy, Align Alignment,
851 ElementCount VF) const;
852
853 /// Split reductions into those that happen in the loop, and those that
854 /// happen outside. In-loop reductions are collected into InLoopReductions.
855 void collectInLoopReductions();
856
857 /// Returns true if the Phi is part of an inloop reduction.
858 bool isInLoopReduction(PHINode *Phi) const {
859 return InLoopReductions.contains(Ptr: Phi);
860 }
861
862 /// Returns the set of in-loop reduction PHIs.
863 const SmallPtrSetImpl<PHINode *> &getInLoopReductions() const {
864 return InLoopReductions;
865 }
866
867 /// Check whether vectorization would require runtime checks. When optimizing
868 /// for size, returning true here aborts vectorization.
869 bool runtimeChecksRequired();
870
871 /// Returns a scalable VF to use for outer-loop vectorization if the target
872 /// supports it and a fixed VF otherwise.
873 FixedScalableVFPair computeVPlanOuterloopVF(ElementCount UserVF);
874
875 /// Compute smallest bitwidth each instruction can be represented with.
876 /// The vector equivalents of these instructions should be truncated to this
877 /// type.
878 void computeMinimalBitwidths();
879
880 /// \returns The smallest bitwidth each instruction can be represented with.
881 const MapVector<Instruction *, uint64_t> &getMinimalBitwidths() const {
882 return MinBWs;
883 }
884};
885
886/// Planner drives the vectorization process after having passed
887/// Legality checks.
888class LoopVectorizationPlanner {
889 const VectorizeOptions &Opts;
890
891 /// The loop that we evaluate.
892 Loop *OrigLoop;
893
894 /// Loop Info analysis.
895 LoopInfo *LI;
896
897 /// The dominator tree.
898 DominatorTree *DT;
899
900 /// Target Library Info.
901 const TargetLibraryInfo *TLI;
902
903 /// Target Transform Info.
904 const TargetTransformInfo &TTI;
905
906 /// The legality analysis.
907 LoopVectorizationLegality *Legal;
908
909 /// The profitability analysis. Cleared after making cost based decisions.
910 /// This instance should never be used in any function that takes an explicit
911 /// PlanCM reference, since that instance overrides this one.
912 std::unique_ptr<LoopVectorizationCostModel> CM;
913
914 /// VF selection state independent of cost-modeling decisions.
915 VFSelectionContext &Config;
916
917 PredicatedScalarEvolution &PSE;
918
919 OptimizationRemarkEmitter *ORE;
920
921 /// Lazily fetch BranchProbabilityInfo, independent of BlockFrequencyInfo.
922 std::function<const BranchProbabilityInfo &()> GetBPI;
923
924 SmallVector<VPlanPtr, 4> VPlans;
925
926 /// Profitable vector factors.
927 SmallVector<VectorizationFactor, 8> ProfitableVFs;
928
929 /// A builder used to construct the current plan.
930 VPBuilder Builder;
931
932 /// Computes the cost of \p Plan for vectorization factor \p VF, using
933 /// \p PlanCM as the cost model.
934 ///
935 /// The current implementation requires access to the
936 /// LoopVectorizationLegality to handle inductions and reductions, which is
937 /// why it is kept separate from the VPlan-only cost infrastructure.
938 ///
939 /// TODO: Move to VPlan::cost once the use of LoopVectorizationLegality has
940 /// been retired.
941 InstructionCost cost(VPlan &Plan, ElementCount VF, VPRegisterUsage *RU,
942 LoopVectorizationCostModel &PlanCM) const;
943
944 /// Precompute costs for certain instructions using the legacy cost model. The
945 /// function is used to bring up the VPlan-based cost model to initially avoid
946 /// taking different decisions due to inaccuracies in the legacy cost model.
947 InstructionCost precomputeCosts(VPlan &Plan, ElementCount VF,
948 VPCostContext &CostCtx) const;
949
950public:
951 LoopVectorizationPlanner(
952 Loop *L, LoopInfo *LI, DominatorTree *DT, const TargetLibraryInfo *TLI,
953 const TargetTransformInfo &TTI, LoopVectorizationLegality *Legal,
954 std::unique_ptr<LoopVectorizationCostModel> CM,
955 VFSelectionContext &Config, PredicatedScalarEvolution &PSE,
956 OptimizationRemarkEmitter *ORE,
957 std::function<const BranchProbabilityInfo &()> GetBPI);
958
959 ~LoopVectorizationPlanner();
960
961 /// Return the cost model. Must not be called after clearCostModel().
962 LoopVectorizationCostModel &getCostModel() {
963 assert(CM && "Cost model has already been cleared");
964 return *CM;
965 }
966
967 /// Destroy the cost model.
968 void clearCostModel();
969
970 /// Return true if there is at least one VPlan for a vector VF
971 bool hasVectorPlan() const {
972 return any_of(
973 Range: VPlans, P: [&](const VPlanPtr &Plan) { return !Plan->hasScalarVFOnly(); });
974 }
975
976 /// Returns true if there is at least one VPlan.
977 bool hasAPlan() const { return !VPlans.empty(); }
978
979 /// Build VPlans for the specified \p UserVF and \p UserIC if they are
980 /// non-zero or all applicable candidate VFs otherwise. If vectorization and
981 /// interleaving should be avoided up-front, no plans are generated.
982 void plan(ElementCount UserVF, unsigned UserIC);
983
984 /// Return the VPlan for \p VF. At the moment, there is always a single VPlan
985 /// for each VF.
986 VPlan &getPlanFor(ElementCount VF) const;
987
988 /// Compute and return the most profitable vectorization factor and the
989 /// corresponding best VPlan. Also collect all profitable VFs in
990 /// ProfitableVFs.
991 std::pair<VectorizationFactor, VPlan *> computeBestVF();
992
993 /// \return The desired interleave count.
994 /// If interleave count has been specified by metadata it will be returned.
995 /// Otherwise, the interleave count is computed and returned. VF and LoopCost
996 /// are the selected vectorization factor and the cost of the selected VF.
997 unsigned selectInterleaveCount(VPlan &Plan, ElementCount VF,
998 InstructionCost LoopCost);
999
1000 /// Generate the IR code for the vectorized loop captured in VPlan \p BestPlan
1001 /// according to the best selected \p VF and \p UF. \p HasRuntimeChecks is
1002 /// used to decide whether runtime unrolling of the scalar loop is disabled.
1003 ///
1004 /// TODO: \p EpilogueVecKind should be removed once the re-use issue has been
1005 /// fixed.
1006 ///
1007 /// When vectorizing the main loop, \p TrackedBlocks are updated to the
1008 /// VPIRBasicBlocks wrapping the blocks generated for them.
1009 ///
1010 /// Returns a mapping of SCEVs to their expanded IR values.
1011 /// Note that this is a temporary workaround needed due to the current
1012 /// epilogue handling.
1013 enum class EpilogueVectorizationKind {
1014 None, ///< Not part of epilogue vectorization.
1015 MainLoop, ///< Vectorizing the main loop of epilogue vectorization.
1016 Epilogue ///< Vectorizing the epilogue loop.
1017 };
1018 DenseMap<const SCEV *, Value *>
1019 executePlan(ElementCount VF, unsigned UF, VPlan &BestPlan,
1020 bool HasRuntimeChecks,
1021 EpilogueVectorizationKind EpilogueVecKind =
1022 EpilogueVectorizationKind::None,
1023 MutableArrayRef<VPBasicBlock *> TrackedBlocks = {});
1024
1025#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1026 void printPlans(raw_ostream &O);
1027#endif
1028
1029 /// Look through the existing plans and return true if we have one with
1030 /// vectorization factor \p VF.
1031 bool hasPlanWithVF(ElementCount VF) const {
1032 return any_of(Range: VPlans,
1033 P: [&](const VPlanPtr &Plan) { return Plan->hasVF(VF); });
1034 }
1035
1036 /// Test a \p Predicate on a \p Range of VF's. Return the value of applying
1037 /// \p Predicate on Range.Start, possibly decreasing Range.End such that the
1038 /// returned value holds for the entire \p Range.
1039 static bool
1040 getDecisionAndClampRange(const std::function<bool(ElementCount)> &Predicate,
1041 VFRange &Range);
1042
1043 /// \return A VPlan for the most profitable epilogue vectorization, with its
1044 /// VF narrowed to the chosen factor. The returned plan is a duplicate.
1045 /// Returns nullptr if epilogue vectorization is not supported or not
1046 /// profitable for the loop. \p ScalarEpilogueAllowed indicates whether the
1047 /// epilogue lowering policy permits creating a scalar epilogue at all.
1048 std::unique_ptr<VPlan> selectBestEpiloguePlan(VPlan &MainPlan,
1049 ElementCount MainLoopVF,
1050 unsigned IC,
1051 bool ScalarEpilogueAllowed);
1052
1053 /// Emit remarks for recipes with invalid costs in the available VPlans.
1054 void emitInvalidCostRemarks(OptimizationRemarkEmitter *ORE);
1055
1056 /// Create a check to \p Plan to see if the vector loop should be executed
1057 /// based on its trip count. When \p TailFoldedEpilogue is true, the
1058 /// tail-folded vector epilogue executes all iterations not executed by
1059 /// the main vector loop, so the check never needs to branch to the scalar
1060 /// loop.
1061 void addMinimumIterationCheck(VPlan &Plan, ElementCount VF, unsigned UF,
1062 ElementCount MinProfitableTripCount,
1063 bool TailFoldedEpilogue) const;
1064
1065 /// Attach the runtime checks of \p RTChecks to \p Plan. \p VF and \p UF are
1066 /// used to compute the thresholds of difference checks.
1067 void attachRuntimeChecks(VPlan &Plan, GeneratedRTChecks &RTChecks,
1068 ElementCount VF, unsigned UF,
1069 bool HasBranchWeights) const;
1070
1071 /// Update loop metadata and profile info for both the scalar remainder loop
1072 /// and \p VectorLoop, if it exists. Keeps all loop hints from the original
1073 /// loop on the vector loop and replaces vectorizer-specific metadata. The
1074 /// loop ID of the original loop \p OrigLoopID must be passed, together with
1075 /// the average trip count and invocation weight of the original loop (\p
1076 /// OrigAverageTripCount and \p OrigLoopInvocationWeight respectively). They
1077 /// cannot be retrieved after the plan has been executed, as the original loop
1078 /// may have been removed. \p UnrollVectorizedLoop indicates whether the
1079 /// target wants the vector loop left eligible for runtime unrolling.
1080 void updateLoopMetadataAndProfileInfo(
1081 Loop *VectorLoop, VPBasicBlock *HeaderVPBB, const VPlan &Plan,
1082 bool VectorizingEpilogue, MDNode *OrigLoopID,
1083 std::optional<unsigned> OrigAverageTripCount,
1084 unsigned OrigLoopInvocationWeight, unsigned EstimatedVFxUF,
1085 bool DisableRuntimeUnroll, bool UnrollVectorizedLoop);
1086
1087private:
1088 /// Build VPlan for the forced epilogue VF. If vectorization and tail-folding
1089 /// should be avoided up-front, no tail-folded plans are generated.
1090 bool planForEpilogueTF();
1091
1092 /// Build an initial VPlan, with HCFG wrapping the original scalar loop and
1093 /// scalar transformations applied. Returns null if an initial VPlan cannot
1094 /// be built. \p PlanCM is the cost model to use for decisions made while
1095 /// building the plan.
1096 VPlanPtr tryToBuildVPlan1(LoopVectorizationCostModel &PlanCM);
1097
1098 /// Build a VPlan using VPRecipes according to the information gathered by
1099 /// Legal and VPlan-based analysis. For outer loops, performs basic recipe
1100 /// conversion only. For inner loops, \p Range's largest included VF is
1101 /// restricted to the maximum VF the returned VPlan is valid for. If no VPlan
1102 /// can be built for the input range, set the largest included VF to the
1103 /// maximum VF for which no plan could be built. Each VPlan is built starting
1104 /// from a copy of \p InitialPlan, which is a plain CFG VPlan wrapping the
1105 /// original scalar loop. \p PlanCM is the cost model used for legality
1106 /// and widening decisions while building the plan.
1107 VPlanPtr tryToBuildVPlan(VPlanPtr InitialPlan, VFRange &Range,
1108 LoopVectorizationCostModel &PlanCM);
1109
1110 /// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive,
1111 /// based on \p VPlan1 and according to the information gathered by Legal
1112 /// when it checked if it is legal to vectorize the loop. \p PlanCM is
1113 /// the cost model to build these VPlans.
1114 void buildVPlans(VPlan &VPlan1, ElementCount MinVF, ElementCount MaxVF,
1115 LoopVectorizationCostModel &PlanCM);
1116
1117 /// Add ComputeReductionResult recipes to the middle block to compute the
1118 /// final reduction results. Add Select recipes to the latch block when
1119 /// folding tail, to feed ComputeReductionResult with the last or penultimate
1120 /// iteration values according to the header mask. \p PlanCM is the cost
1121 /// model used to build \p Plan.
1122 void addReductionResultComputation(VPlanPtr &Plan, ElementCount MinVF,
1123 LoopVectorizationCostModel &PlanCM);
1124
1125 /// Returns true if the per-lane cost of VectorizationFactor A is lower than
1126 /// that of B.
1127 bool isMoreProfitable(const VectorizationFactor &A,
1128 const VectorizationFactor &B, bool HasTail,
1129 bool IsEpilogue = false) const;
1130
1131 /// Returns true if the per-lane cost of VectorizationFactor A is lower than
1132 /// that of B in the context of vectorizing a loop with known \p MaxTripCount.
1133 bool isMoreProfitable(const VectorizationFactor &A,
1134 const VectorizationFactor &B,
1135 const unsigned MaxTripCount, bool HasTail,
1136 bool IsEpilogue = false) const;
1137
1138 /// Determines if we have the infrastructure to vectorize the loop and its
1139 /// epilogue, assuming the main loop is vectorized by \p MainPlan.
1140 bool isCandidateForEpilogueVectorization(VPlan &MainPlan) const;
1141};
1142
1143} // namespace llvm
1144
1145#endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H
1146