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