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