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