1 //===- LoopVectorizationPlanner.h - Planner for LoopVectorization ---------===//
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
7 //===----------------------------------------------------------------------===//
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.
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 //===----------------------------------------------------------------------===//
24 #ifndef LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H
25 #define LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H
28 #include "llvm/Support/InstructionCost.h"
33 class LoopVectorizationLegality;
34 class LoopVectorizationCostModel;
35 class PredicatedScalarEvolution;
36 class LoopVectorizationRequirements;
37 class LoopVectorizeHints;
38 class OptimizationRemarkEmitter;
39 class TargetTransformInfo;
40 class TargetLibraryInfo;
41 class VPRecipeBuilder;
43 /// VPlan-based builder utility analogous to IRBuilder.
45 VPBasicBlock *BB = nullptr;
46 VPBasicBlock::iterator InsertPt = VPBasicBlock::iterator();
48 VPInstruction *createInstruction(unsigned Opcode,
49 ArrayRef<VPValue *> Operands, DebugLoc DL) {
50 VPInstruction *Instr = new VPInstruction(Opcode, Operands, DL);
52 BB->insert(Instr, InsertPt);
56 VPInstruction *createInstruction(unsigned Opcode,
57 std::initializer_list<VPValue *> Operands,
59 return createInstruction(Opcode, ArrayRef<VPValue *>(Operands), DL);
63 VPBuilder() = default;
65 /// Clear the insertion point: created instructions will not be inserted into
67 void clearInsertionPoint() {
69 InsertPt = VPBasicBlock::iterator();
72 VPBasicBlock *getInsertBlock() const { return BB; }
73 VPBasicBlock::iterator getInsertPoint() const { return InsertPt; }
75 /// InsertPoint - A saved insertion point.
77 VPBasicBlock *Block = nullptr;
78 VPBasicBlock::iterator Point;
81 /// Creates a new insertion point which doesn't point to anything.
82 VPInsertPoint() = default;
84 /// Creates a new insertion point at the given location.
85 VPInsertPoint(VPBasicBlock *InsertBlock, VPBasicBlock::iterator InsertPoint)
86 : Block(InsertBlock), Point(InsertPoint) {}
88 /// Returns true if this insert point is set.
89 bool isSet() const { return Block != nullptr; }
91 VPBasicBlock *getBlock() const { return Block; }
92 VPBasicBlock::iterator getPoint() const { return Point; }
95 /// Sets the current insert point to a previously-saved location.
96 void restoreIP(VPInsertPoint IP) {
98 setInsertPoint(IP.getBlock(), IP.getPoint());
100 clearInsertionPoint();
103 /// This specifies that created VPInstructions should be appended to the end
104 /// of the specified block.
105 void setInsertPoint(VPBasicBlock *TheBB) {
106 assert(TheBB && "Attempting to set a null insert point");
108 InsertPt = BB->end();
111 /// This specifies that created instructions should be inserted at the
113 void setInsertPoint(VPBasicBlock *TheBB, VPBasicBlock::iterator IP) {
118 /// Insert and return the specified instruction.
119 VPInstruction *insert(VPInstruction *I) const {
120 BB->insert(I, InsertPt);
124 /// Create an N-ary operation with \p Opcode, \p Operands and set \p Inst as
125 /// its underlying Instruction.
126 VPValue *createNaryOp(unsigned Opcode, ArrayRef<VPValue *> Operands,
127 Instruction *Inst = nullptr) {
130 DL = Inst->getDebugLoc();
131 VPInstruction *NewVPInst = createInstruction(Opcode, Operands, DL);
132 NewVPInst->setUnderlyingValue(Inst);
135 VPValue *createNaryOp(unsigned Opcode, ArrayRef<VPValue *> Operands,
137 return createInstruction(Opcode, Operands, DL);
140 VPValue *createNot(VPValue *Operand, DebugLoc DL) {
141 return createInstruction(VPInstruction::Not, {Operand}, DL);
144 VPValue *createAnd(VPValue *LHS, VPValue *RHS, DebugLoc DL) {
145 return createInstruction(Instruction::BinaryOps::And, {LHS, RHS}, DL);
148 VPValue *createOr(VPValue *LHS, VPValue *RHS, DebugLoc DL) {
149 return createInstruction(Instruction::BinaryOps::Or, {LHS, RHS}, DL);
152 VPValue *createSelect(VPValue *Cond, VPValue *TrueVal, VPValue *FalseVal,
154 return createNaryOp(Instruction::Select, {Cond, TrueVal, FalseVal}, DL);
157 //===--------------------------------------------------------------------===//
159 //===--------------------------------------------------------------------===//
161 /// RAII object that stores the current insertion point and restores it when
162 /// the object is destroyed.
163 class InsertPointGuard {
166 VPBasicBlock::iterator Point;
169 InsertPointGuard(VPBuilder &B)
170 : Builder(B), Block(B.getInsertBlock()), Point(B.getInsertPoint()) {}
172 InsertPointGuard(const InsertPointGuard &) = delete;
173 InsertPointGuard &operator=(const InsertPointGuard &) = delete;
175 ~InsertPointGuard() { Builder.restoreIP(VPInsertPoint(Block, Point)); }
179 /// TODO: The following VectorizationFactor was pulled out of
180 /// LoopVectorizationCostModel class. LV also deals with
181 /// VectorizerParams::VectorizationFactor and VectorizationCostTy.
182 /// We need to streamline them.
184 /// Information about vectorization costs.
185 struct VectorizationFactor {
186 /// Vector width with best cost.
188 /// Cost of the loop with that width.
189 InstructionCost Cost;
191 /// Cost of the scalar loop.
192 InstructionCost ScalarCost;
194 VectorizationFactor(ElementCount Width, InstructionCost Cost,
195 InstructionCost ScalarCost)
196 : Width(Width), Cost(Cost), ScalarCost(ScalarCost) {}
198 /// Width 1 means no vectorization, cost 0 means uncomputed cost.
199 static VectorizationFactor Disabled() {
200 return {ElementCount::getFixed(1), 0, 0};
203 bool operator==(const VectorizationFactor &rhs) const {
204 return Width == rhs.Width && Cost == rhs.Cost;
207 bool operator!=(const VectorizationFactor &rhs) const {
208 return !(*this == rhs);
212 /// A class that represents two vectorization factors (initialized with 0 by
213 /// default). One for fixed-width vectorization and one for scalable
214 /// vectorization. This can be used by the vectorizer to choose from a range of
215 /// fixed and/or scalable VFs in order to find the most cost-effective VF to
217 struct FixedScalableVFPair {
218 ElementCount FixedVF;
219 ElementCount ScalableVF;
221 FixedScalableVFPair()
222 : FixedVF(ElementCount::getFixed(0)),
223 ScalableVF(ElementCount::getScalable(0)) {}
224 FixedScalableVFPair(const ElementCount &Max) : FixedScalableVFPair() {
225 *(Max.isScalable() ? &ScalableVF : &FixedVF) = Max;
227 FixedScalableVFPair(const ElementCount &FixedVF,
228 const ElementCount &ScalableVF)
229 : FixedVF(FixedVF), ScalableVF(ScalableVF) {
230 assert(!FixedVF.isScalable() && ScalableVF.isScalable() &&
231 "Invalid scalable properties");
234 static FixedScalableVFPair getNone() { return FixedScalableVFPair(); }
236 /// \return true if either fixed- or scalable VF is non-zero.
237 explicit operator bool() const { return FixedVF || ScalableVF; }
239 /// \return true if either fixed- or scalable VF is a valid vector VF.
240 bool hasVector() const { return FixedVF.isVector() || ScalableVF.isVector(); }
243 /// Planner drives the vectorization process after having passed
245 class LoopVectorizationPlanner {
246 /// The loop that we evaluate.
249 /// Loop Info analysis.
252 /// Target Library Info.
253 const TargetLibraryInfo *TLI;
255 /// Target Transform Info.
256 const TargetTransformInfo *TTI;
258 /// The legality analysis.
259 LoopVectorizationLegality *Legal;
261 /// The profitability analysis.
262 LoopVectorizationCostModel &CM;
264 /// The interleaved access analysis.
265 InterleavedAccessInfo &IAI;
267 PredicatedScalarEvolution &PSE;
269 const LoopVectorizeHints &Hints;
271 LoopVectorizationRequirements &Requirements;
273 OptimizationRemarkEmitter *ORE;
275 SmallVector<VPlanPtr, 4> VPlans;
277 /// A builder used to construct the current plan.
281 LoopVectorizationPlanner(Loop *L, LoopInfo *LI, const TargetLibraryInfo *TLI,
282 const TargetTransformInfo *TTI,
283 LoopVectorizationLegality *Legal,
284 LoopVectorizationCostModel &CM,
285 InterleavedAccessInfo &IAI,
286 PredicatedScalarEvolution &PSE,
287 const LoopVectorizeHints &Hints,
288 LoopVectorizationRequirements &Requirements,
289 OptimizationRemarkEmitter *ORE)
290 : OrigLoop(L), LI(LI), TLI(TLI), TTI(TTI), Legal(Legal), CM(CM), IAI(IAI),
291 PSE(PSE), Hints(Hints), Requirements(Requirements), ORE(ORE) {}
293 /// Plan how to best vectorize, return the best VF and its cost, or None if
294 /// vectorization and interleaving should be avoided up front.
295 Optional<VectorizationFactor> plan(ElementCount UserVF, unsigned UserIC);
297 /// Use the VPlan-native path to plan how to best vectorize, return the best
299 VectorizationFactor planInVPlanNativePath(ElementCount UserVF);
301 /// Return the best VPlan for \p VF.
302 VPlan &getBestPlanFor(ElementCount VF) const;
304 /// Generate the IR code for the body of the vectorized loop according to the
305 /// best selected \p VF, \p UF and VPlan \p BestPlan.
306 /// TODO: \p IsEpilogueVectorization is needed to avoid issues due to epilogue
307 /// vectorization re-using plans for both the main and epilogue vector loops.
308 /// It should be removed once the re-use issue has been fixed.
309 void executePlan(ElementCount VF, unsigned UF, VPlan &BestPlan,
310 InnerLoopVectorizer &LB, DominatorTree *DT,
311 bool IsEpilogueVectorization);
313 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
314 void printPlans(raw_ostream &O);
317 /// Look through the existing plans and return true if we have one with all
318 /// the vectorization factors in question.
319 bool hasPlanWithVF(ElementCount VF) const {
320 return any_of(VPlans,
321 [&](const VPlanPtr &Plan) { return Plan->hasVF(VF); });
324 /// Test a \p Predicate on a \p Range of VF's. Return the value of applying
325 /// \p Predicate on Range.Start, possibly decreasing Range.End such that the
326 /// returned value holds for the entire \p Range.
328 getDecisionAndClampRange(const std::function<bool(ElementCount)> &Predicate,
331 /// Check if the number of runtime checks exceeds the threshold.
332 bool requiresTooManyRuntimeChecks() const;
335 /// Collect the instructions from the original loop that would be trivially
336 /// dead in the vectorized loop if generated.
337 void collectTriviallyDeadInstructions(
338 SmallPtrSetImpl<Instruction *> &DeadInstructions);
340 /// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive,
341 /// according to the information gathered by Legal when it checked if it is
342 /// legal to vectorize the loop.
343 void buildVPlans(ElementCount MinVF, ElementCount MaxVF);
346 /// Build a VPlan according to the information gathered by Legal. \return a
347 /// VPlan for vectorization factors \p Range.Start and up to \p Range.End
348 /// exclusive, possibly decreasing \p Range.End.
349 VPlanPtr buildVPlan(VFRange &Range);
351 /// Build a VPlan using VPRecipes according to the information gather by
352 /// Legal. This method is only used for the legacy inner loop vectorizer.
353 VPlanPtr buildVPlanWithVPRecipes(
354 VFRange &Range, SmallPtrSetImpl<Instruction *> &DeadInstructions,
355 const MapVector<Instruction *, Instruction *> &SinkAfter);
357 /// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive,
358 /// according to the information gathered by Legal when it checked if it is
359 /// legal to vectorize the loop. This method creates VPlans using VPRecipes.
360 void buildVPlansWithVPRecipes(ElementCount MinVF, ElementCount MaxVF);
362 // Adjust the recipes for reductions. For in-loop reductions the chain of
363 // instructions leading from the loop exit instr to the phi need to be
364 // converted to reductions, with one operand being vector and the other being
365 // the scalar reduction chain. For other reductions, a select is introduced
366 // between the phi and live-out recipes when folding the tail.
367 void adjustRecipesForReductions(VPBasicBlock *LatchVPBB, VPlanPtr &Plan,
368 VPRecipeBuilder &RecipeBuilder,
374 #endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H