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