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/Support/InstructionCost.h"
30
31namespace llvm {
32
33class LoopInfo;
34class DominatorTree;
35class LoopVectorizationLegality;
36class LoopVectorizationCostModel;
37class PredicatedScalarEvolution;
38class LoopVectorizeHints;
39class OptimizationRemarkEmitter;
40class TargetTransformInfo;
41class TargetLibraryInfo;
42class VPRecipeBuilder;
43
44/// VPlan-based builder utility analogous to IRBuilder.
45class VPBuilder {
46 VPBasicBlock *BB = nullptr;
47 VPBasicBlock::iterator InsertPt = VPBasicBlock::iterator();
48
49 /// Insert \p VPI in BB at InsertPt if BB is set.
50 VPInstruction *tryInsertInstruction(VPInstruction *VPI) {
51 if (BB)
52 BB->insert(Recipe: VPI, InsertPt);
53 return VPI;
54 }
55
56 VPInstruction *createInstruction(unsigned Opcode,
57 ArrayRef<VPValue *> Operands, DebugLoc DL,
58 const Twine &Name = "") {
59 return tryInsertInstruction(VPI: new VPInstruction(Opcode, Operands, DL, Name));
60 }
61
62 VPInstruction *createInstruction(unsigned Opcode,
63 std::initializer_list<VPValue *> Operands,
64 DebugLoc DL, const Twine &Name = "") {
65 return createInstruction(Opcode, Operands: ArrayRef<VPValue *>(Operands), DL, Name);
66 }
67
68public:
69 VPBuilder() = default;
70 VPBuilder(VPBasicBlock *InsertBB) { setInsertPoint(InsertBB); }
71 VPBuilder(VPRecipeBase *InsertPt) {
72 setInsertPoint(TheBB: InsertPt->getParent(), IP: InsertPt->getIterator());
73 }
74
75 /// Clear the insertion point: created instructions will not be inserted into
76 /// a block.
77 void clearInsertionPoint() {
78 BB = nullptr;
79 InsertPt = VPBasicBlock::iterator();
80 }
81
82 VPBasicBlock *getInsertBlock() const { return BB; }
83 VPBasicBlock::iterator getInsertPoint() const { return InsertPt; }
84
85 /// Create a VPBuilder to insert after \p R.
86 static VPBuilder getToInsertAfter(VPRecipeBase *R) {
87 VPBuilder B;
88 B.setInsertPoint(TheBB: R->getParent(), IP: std::next(x: R->getIterator()));
89 return B;
90 }
91
92 /// InsertPoint - A saved insertion point.
93 class VPInsertPoint {
94 VPBasicBlock *Block = nullptr;
95 VPBasicBlock::iterator Point;
96
97 public:
98 /// Creates a new insertion point which doesn't point to anything.
99 VPInsertPoint() = default;
100
101 /// Creates a new insertion point at the given location.
102 VPInsertPoint(VPBasicBlock *InsertBlock, VPBasicBlock::iterator InsertPoint)
103 : Block(InsertBlock), Point(InsertPoint) {}
104
105 /// Returns true if this insert point is set.
106 bool isSet() const { return Block != nullptr; }
107
108 VPBasicBlock *getBlock() const { return Block; }
109 VPBasicBlock::iterator getPoint() const { return Point; }
110 };
111
112 /// Sets the current insert point to a previously-saved location.
113 void restoreIP(VPInsertPoint IP) {
114 if (IP.isSet())
115 setInsertPoint(TheBB: IP.getBlock(), IP: IP.getPoint());
116 else
117 clearInsertionPoint();
118 }
119
120 /// This specifies that created VPInstructions should be appended to the end
121 /// of the specified block.
122 void setInsertPoint(VPBasicBlock *TheBB) {
123 assert(TheBB && "Attempting to set a null insert point");
124 BB = TheBB;
125 InsertPt = BB->end();
126 }
127
128 /// This specifies that created instructions should be inserted at the
129 /// specified point.
130 void setInsertPoint(VPBasicBlock *TheBB, VPBasicBlock::iterator IP) {
131 BB = TheBB;
132 InsertPt = IP;
133 }
134
135 /// This specifies that created instructions should be inserted at the
136 /// specified point.
137 void setInsertPoint(VPRecipeBase *IP) {
138 BB = IP->getParent();
139 InsertPt = IP->getIterator();
140 }
141
142 /// Create an N-ary operation with \p Opcode, \p Operands and set \p Inst as
143 /// its underlying Instruction.
144 VPInstruction *createNaryOp(unsigned Opcode, ArrayRef<VPValue *> Operands,
145 Instruction *Inst = nullptr,
146 const Twine &Name = "") {
147 DebugLoc DL;
148 if (Inst)
149 DL = Inst->getDebugLoc();
150 VPInstruction *NewVPInst = createInstruction(Opcode, Operands, DL, Name);
151 NewVPInst->setUnderlyingValue(Inst);
152 return NewVPInst;
153 }
154 VPInstruction *createNaryOp(unsigned Opcode, ArrayRef<VPValue *> Operands,
155 DebugLoc DL, const Twine &Name = "") {
156 return createInstruction(Opcode, Operands, DL, Name);
157 }
158
159 VPInstruction *createOverflowingOp(unsigned Opcode,
160 std::initializer_list<VPValue *> Operands,
161 VPRecipeWithIRFlags::WrapFlagsTy WrapFlags,
162 DebugLoc DL = {}, const Twine &Name = "") {
163 return tryInsertInstruction(
164 VPI: new VPInstruction(Opcode, Operands, WrapFlags, DL, Name));
165 }
166 VPValue *createNot(VPValue *Operand, DebugLoc DL = {},
167 const Twine &Name = "") {
168 return createInstruction(Opcode: VPInstruction::Not, Operands: {Operand}, DL, Name);
169 }
170
171 VPValue *createAnd(VPValue *LHS, VPValue *RHS, DebugLoc DL = {},
172 const Twine &Name = "") {
173 return createInstruction(Opcode: Instruction::BinaryOps::And, Operands: {LHS, RHS}, DL, Name);
174 }
175
176 VPValue *createOr(VPValue *LHS, VPValue *RHS, DebugLoc DL = {},
177 const Twine &Name = "") {
178
179 return tryInsertInstruction(VPI: new VPInstruction(
180 Instruction::BinaryOps::Or, {LHS, RHS},
181 VPRecipeWithIRFlags::DisjointFlagsTy(false), DL, Name));
182 }
183
184 VPValue *createSelect(VPValue *Cond, VPValue *TrueVal, VPValue *FalseVal,
185 DebugLoc DL = {}, const Twine &Name = "",
186 std::optional<FastMathFlags> FMFs = std::nullopt) {
187 auto *Select =
188 FMFs ? new VPInstruction(Instruction::Select, {Cond, TrueVal, FalseVal},
189 *FMFs, DL, Name)
190 : new VPInstruction(Instruction::Select, {Cond, TrueVal, FalseVal},
191 DL, Name);
192 return tryInsertInstruction(VPI: Select);
193 }
194
195 /// Create a new ICmp VPInstruction with predicate \p Pred and operands \p A
196 /// and \p B.
197 /// TODO: add createFCmp when needed.
198 VPValue *createICmp(CmpInst::Predicate Pred, VPValue *A, VPValue *B,
199 DebugLoc DL = {}, const Twine &Name = "");
200
201 //===--------------------------------------------------------------------===//
202 // RAII helpers.
203 //===--------------------------------------------------------------------===//
204
205 /// RAII object that stores the current insertion point and restores it when
206 /// the object is destroyed.
207 class InsertPointGuard {
208 VPBuilder &Builder;
209 VPBasicBlock *Block;
210 VPBasicBlock::iterator Point;
211
212 public:
213 InsertPointGuard(VPBuilder &B)
214 : Builder(B), Block(B.getInsertBlock()), Point(B.getInsertPoint()) {}
215
216 InsertPointGuard(const InsertPointGuard &) = delete;
217 InsertPointGuard &operator=(const InsertPointGuard &) = delete;
218
219 ~InsertPointGuard() { Builder.restoreIP(IP: VPInsertPoint(Block, Point)); }
220 };
221};
222
223/// TODO: The following VectorizationFactor was pulled out of
224/// LoopVectorizationCostModel class. LV also deals with
225/// VectorizerParams::VectorizationFactor and VectorizationCostTy.
226/// We need to streamline them.
227
228/// Information about vectorization costs.
229struct VectorizationFactor {
230 /// Vector width with best cost.
231 ElementCount Width;
232
233 /// Cost of the loop with that width.
234 InstructionCost Cost;
235
236 /// Cost of the scalar loop.
237 InstructionCost ScalarCost;
238
239 /// The minimum trip count required to make vectorization profitable, e.g. due
240 /// to runtime checks.
241 ElementCount MinProfitableTripCount;
242
243 VectorizationFactor(ElementCount Width, InstructionCost Cost,
244 InstructionCost ScalarCost)
245 : Width(Width), Cost(Cost), ScalarCost(ScalarCost) {}
246
247 /// Width 1 means no vectorization, cost 0 means uncomputed cost.
248 static VectorizationFactor Disabled() {
249 return {ElementCount::getFixed(MinVal: 1), 0, 0};
250 }
251
252 bool operator==(const VectorizationFactor &rhs) const {
253 return Width == rhs.Width && Cost == rhs.Cost;
254 }
255
256 bool operator!=(const VectorizationFactor &rhs) const {
257 return !(*this == rhs);
258 }
259};
260
261/// ElementCountComparator creates a total ordering for ElementCount
262/// for the purposes of using it in a set structure.
263struct ElementCountComparator {
264 bool operator()(const ElementCount &LHS, const ElementCount &RHS) const {
265 return std::make_tuple(args: LHS.isScalable(), args: LHS.getKnownMinValue()) <
266 std::make_tuple(args: RHS.isScalable(), args: RHS.getKnownMinValue());
267 }
268};
269using ElementCountSet = SmallSet<ElementCount, 16, ElementCountComparator>;
270
271/// A class that represents two vectorization factors (initialized with 0 by
272/// default). One for fixed-width vectorization and one for scalable
273/// vectorization. This can be used by the vectorizer to choose from a range of
274/// fixed and/or scalable VFs in order to find the most cost-effective VF to
275/// vectorize with.
276struct FixedScalableVFPair {
277 ElementCount FixedVF;
278 ElementCount ScalableVF;
279
280 FixedScalableVFPair()
281 : FixedVF(ElementCount::getFixed(MinVal: 0)),
282 ScalableVF(ElementCount::getScalable(MinVal: 0)) {}
283 FixedScalableVFPair(const ElementCount &Max) : FixedScalableVFPair() {
284 *(Max.isScalable() ? &ScalableVF : &FixedVF) = Max;
285 }
286 FixedScalableVFPair(const ElementCount &FixedVF,
287 const ElementCount &ScalableVF)
288 : FixedVF(FixedVF), ScalableVF(ScalableVF) {
289 assert(!FixedVF.isScalable() && ScalableVF.isScalable() &&
290 "Invalid scalable properties");
291 }
292
293 static FixedScalableVFPair getNone() { return FixedScalableVFPair(); }
294
295 /// \return true if either fixed- or scalable VF is non-zero.
296 explicit operator bool() const { return FixedVF || ScalableVF; }
297
298 /// \return true if either fixed- or scalable VF is a valid vector VF.
299 bool hasVector() const { return FixedVF.isVector() || ScalableVF.isVector(); }
300};
301
302/// Planner drives the vectorization process after having passed
303/// Legality checks.
304class LoopVectorizationPlanner {
305 /// The loop that we evaluate.
306 Loop *OrigLoop;
307
308 /// Loop Info analysis.
309 LoopInfo *LI;
310
311 /// The dominator tree.
312 DominatorTree *DT;
313
314 /// Target Library Info.
315 const TargetLibraryInfo *TLI;
316
317 /// Target Transform Info.
318 const TargetTransformInfo &TTI;
319
320 /// The legality analysis.
321 LoopVectorizationLegality *Legal;
322
323 /// The profitability analysis.
324 LoopVectorizationCostModel &CM;
325
326 /// The interleaved access analysis.
327 InterleavedAccessInfo &IAI;
328
329 PredicatedScalarEvolution &PSE;
330
331 const LoopVectorizeHints &Hints;
332
333 OptimizationRemarkEmitter *ORE;
334
335 SmallVector<VPlanPtr, 4> VPlans;
336
337 /// Profitable vector factors.
338 SmallVector<VectorizationFactor, 8> ProfitableVFs;
339
340 /// A builder used to construct the current plan.
341 VPBuilder Builder;
342
343public:
344 LoopVectorizationPlanner(
345 Loop *L, LoopInfo *LI, DominatorTree *DT, const TargetLibraryInfo *TLI,
346 const TargetTransformInfo &TTI, LoopVectorizationLegality *Legal,
347 LoopVectorizationCostModel &CM, InterleavedAccessInfo &IAI,
348 PredicatedScalarEvolution &PSE, const LoopVectorizeHints &Hints,
349 OptimizationRemarkEmitter *ORE)
350 : OrigLoop(L), LI(LI), DT(DT), TLI(TLI), TTI(TTI), Legal(Legal), CM(CM),
351 IAI(IAI), PSE(PSE), Hints(Hints), ORE(ORE) {}
352
353 /// Plan how to best vectorize, return the best VF and its cost, or
354 /// std::nullopt if vectorization and interleaving should be avoided up front.
355 std::optional<VectorizationFactor> plan(ElementCount UserVF, unsigned UserIC);
356
357 /// Use the VPlan-native path to plan how to best vectorize, return the best
358 /// VF and its cost.
359 VectorizationFactor planInVPlanNativePath(ElementCount UserVF);
360
361 /// Return the best VPlan for \p VF.
362 VPlan &getBestPlanFor(ElementCount VF) const;
363
364 /// Generate the IR code for the vectorized loop captured in VPlan \p BestPlan
365 /// according to the best selected \p VF and \p UF.
366 ///
367 /// TODO: \p IsEpilogueVectorization is needed to avoid issues due to epilogue
368 /// vectorization re-using plans for both the main and epilogue vector loops.
369 /// It should be removed once the re-use issue has been fixed.
370 /// \p ExpandedSCEVs is passed during execution of the plan for epilogue loop
371 /// to re-use expansion results generated during main plan execution.
372 ///
373 /// Returns a mapping of SCEVs to their expanded IR values and a mapping for
374 /// the reduction resume values. Note that this is a temporary workaround
375 /// needed due to the current epilogue handling.
376 std::pair<DenseMap<const SCEV *, Value *>,
377 DenseMap<const RecurrenceDescriptor *, Value *>>
378 executePlan(ElementCount VF, unsigned UF, VPlan &BestPlan,
379 InnerLoopVectorizer &LB, DominatorTree *DT,
380 bool IsEpilogueVectorization,
381 const DenseMap<const SCEV *, Value *> *ExpandedSCEVs = nullptr);
382
383#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
384 void printPlans(raw_ostream &O);
385#endif
386
387 /// Look through the existing plans and return true if we have one with
388 /// vectorization factor \p VF.
389 bool hasPlanWithVF(ElementCount VF) const {
390 return any_of(Range: VPlans,
391 P: [&](const VPlanPtr &Plan) { return Plan->hasVF(VF); });
392 }
393
394 /// Test a \p Predicate on a \p Range of VF's. Return the value of applying
395 /// \p Predicate on Range.Start, possibly decreasing Range.End such that the
396 /// returned value holds for the entire \p Range.
397 static bool
398 getDecisionAndClampRange(const std::function<bool(ElementCount)> &Predicate,
399 VFRange &Range);
400
401 /// \return The most profitable vectorization factor and the cost of that VF
402 /// for vectorizing the epilogue. Returns VectorizationFactor::Disabled if
403 /// epilogue vectorization is not supported for the loop.
404 VectorizationFactor
405 selectEpilogueVectorizationFactor(const ElementCount MaxVF, unsigned IC);
406
407protected:
408 /// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive,
409 /// according to the information gathered by Legal when it checked if it is
410 /// legal to vectorize the loop.
411 void buildVPlans(ElementCount MinVF, ElementCount MaxVF);
412
413private:
414 /// Build a VPlan according to the information gathered by Legal. \return a
415 /// VPlan for vectorization factors \p Range.Start and up to \p Range.End
416 /// exclusive, possibly decreasing \p Range.End.
417 VPlanPtr buildVPlan(VFRange &Range);
418
419 /// Build a VPlan using VPRecipes according to the information gather by
420 /// Legal. This method is only used for the legacy inner loop vectorizer.
421 /// \p Range's largest included VF is restricted to the maximum VF the
422 /// returned VPlan is valid for. If no VPlan can be built for the input range,
423 /// set the largest included VF to the maximum VF for which no plan could be
424 /// built.
425 VPlanPtr tryToBuildVPlanWithVPRecipes(VFRange &Range);
426
427 /// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive,
428 /// according to the information gathered by Legal when it checked if it is
429 /// legal to vectorize the loop. This method creates VPlans using VPRecipes.
430 void buildVPlansWithVPRecipes(ElementCount MinVF, ElementCount MaxVF);
431
432 // Adjust the recipes for reductions. For in-loop reductions the chain of
433 // instructions leading from the loop exit instr to the phi need to be
434 // converted to reductions, with one operand being vector and the other being
435 // the scalar reduction chain. For other reductions, a select is introduced
436 // between the phi and live-out recipes when folding the tail.
437 void adjustRecipesForReductions(VPBasicBlock *LatchVPBB, VPlanPtr &Plan,
438 VPRecipeBuilder &RecipeBuilder,
439 ElementCount MinVF);
440
441 /// \return The most profitable vectorization factor and the cost of that VF.
442 /// This method checks every VF in \p CandidateVFs.
443 VectorizationFactor
444 selectVectorizationFactor(const ElementCountSet &CandidateVFs);
445
446 /// Returns true if the per-lane cost of VectorizationFactor A is lower than
447 /// that of B.
448 bool isMoreProfitable(const VectorizationFactor &A,
449 const VectorizationFactor &B) const;
450
451 /// Determines if we have the infrastructure to vectorize the loop and its
452 /// epilogue, assuming the main loop is vectorized by \p VF.
453 bool isCandidateForEpilogueVectorization(const ElementCount VF) const;
454};
455
456} // namespace llvm
457
458#endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H
459

source code of llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h