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/Analysis/LoopInfo.h"
29 #include "llvm/Analysis/TargetLibraryInfo.h"
30 #include "llvm/Analysis/TargetTransformInfo.h"
31 
32 namespace llvm {
33 
34 /// VPlan-based builder utility analogous to IRBuilder.
35 class VPBuilder {
36 private:
37   VPBasicBlock *BB = nullptr;
38   VPBasicBlock::iterator InsertPt = VPBasicBlock::iterator();
39 
40   VPInstruction *createInstruction(unsigned Opcode,
41                                    ArrayRef<VPValue *> Operands) {
42     VPInstruction *Instr = new VPInstruction(Opcode, Operands);
43     if (BB)
44       BB->insert(Instr, InsertPt);
45     return Instr;
46   }
47 
48   VPInstruction *createInstruction(unsigned Opcode,
49                                    std::initializer_list<VPValue *> Operands) {
50     return createInstruction(Opcode, ArrayRef<VPValue *>(Operands));
51   }
52 
53 public:
54   VPBuilder() {}
55 
56   /// Clear the insertion point: created instructions will not be inserted into
57   /// a block.
58   void clearInsertionPoint() {
59     BB = nullptr;
60     InsertPt = VPBasicBlock::iterator();
61   }
62 
63   VPBasicBlock *getInsertBlock() const { return BB; }
64   VPBasicBlock::iterator getInsertPoint() const { return InsertPt; }
65 
66   /// InsertPoint - A saved insertion point.
67   class VPInsertPoint {
68     VPBasicBlock *Block = nullptr;
69     VPBasicBlock::iterator Point;
70 
71   public:
72     /// Creates a new insertion point which doesn't point to anything.
73     VPInsertPoint() = default;
74 
75     /// Creates a new insertion point at the given location.
76     VPInsertPoint(VPBasicBlock *InsertBlock, VPBasicBlock::iterator InsertPoint)
77         : Block(InsertBlock), Point(InsertPoint) {}
78 
79     /// Returns true if this insert point is set.
80     bool isSet() const { return Block != nullptr; }
81 
82     VPBasicBlock *getBlock() const { return Block; }
83     VPBasicBlock::iterator getPoint() const { return Point; }
84   };
85 
86   /// Sets the current insert point to a previously-saved location.
87   void restoreIP(VPInsertPoint IP) {
88     if (IP.isSet())
89       setInsertPoint(IP.getBlock(), IP.getPoint());
90     else
91       clearInsertionPoint();
92   }
93 
94   /// This specifies that created VPInstructions should be appended to the end
95   /// of the specified block.
96   void setInsertPoint(VPBasicBlock *TheBB) {
97     assert(TheBB && "Attempting to set a null insert point");
98     BB = TheBB;
99     InsertPt = BB->end();
100   }
101 
102   /// This specifies that created instructions should be inserted at the
103   /// specified point.
104   void setInsertPoint(VPBasicBlock *TheBB, VPBasicBlock::iterator IP) {
105     BB = TheBB;
106     InsertPt = IP;
107   }
108 
109   /// Insert and return the specified instruction.
110   VPInstruction *insert(VPInstruction *I) const {
111     BB->insert(I, InsertPt);
112     return I;
113   }
114 
115   /// Create an N-ary operation with \p Opcode, \p Operands and set \p Inst as
116   /// its underlying Instruction.
117   VPValue *createNaryOp(unsigned Opcode, ArrayRef<VPValue *> Operands,
118                         Instruction *Inst = nullptr) {
119     VPInstruction *NewVPInst = createInstruction(Opcode, Operands);
120     NewVPInst->setUnderlyingValue(Inst);
121     return NewVPInst;
122   }
123   VPValue *createNaryOp(unsigned Opcode,
124                         std::initializer_list<VPValue *> Operands,
125                         Instruction *Inst = nullptr) {
126     return createNaryOp(Opcode, ArrayRef<VPValue *>(Operands), Inst);
127   }
128 
129   VPValue *createNot(VPValue *Operand) {
130     return createInstruction(VPInstruction::Not, {Operand});
131   }
132 
133   VPValue *createAnd(VPValue *LHS, VPValue *RHS) {
134     return createInstruction(Instruction::BinaryOps::And, {LHS, RHS});
135   }
136 
137   VPValue *createOr(VPValue *LHS, VPValue *RHS) {
138     return createInstruction(Instruction::BinaryOps::Or, {LHS, RHS});
139   }
140 
141   //===--------------------------------------------------------------------===//
142   // RAII helpers.
143   //===--------------------------------------------------------------------===//
144 
145   /// RAII object that stores the current insertion point and restores it when
146   /// the object is destroyed.
147   class InsertPointGuard {
148     VPBuilder &Builder;
149     VPBasicBlock *Block;
150     VPBasicBlock::iterator Point;
151 
152   public:
153     InsertPointGuard(VPBuilder &B)
154         : Builder(B), Block(B.getInsertBlock()), Point(B.getInsertPoint()) {}
155 
156     InsertPointGuard(const InsertPointGuard &) = delete;
157     InsertPointGuard &operator=(const InsertPointGuard &) = delete;
158 
159     ~InsertPointGuard() { Builder.restoreIP(VPInsertPoint(Block, Point)); }
160   };
161 };
162 
163 /// TODO: The following VectorizationFactor was pulled out of
164 /// LoopVectorizationCostModel class. LV also deals with
165 /// VectorizerParams::VectorizationFactor and VectorizationCostTy.
166 /// We need to streamline them.
167 
168 /// Information about vectorization costs
169 struct VectorizationFactor {
170   // Vector width with best cost
171   unsigned Width;
172   // Cost of the loop with that width
173   unsigned Cost;
174 };
175 
176 /// Planner drives the vectorization process after having passed
177 /// Legality checks.
178 class LoopVectorizationPlanner {
179   /// The loop that we evaluate.
180   Loop *OrigLoop;
181 
182   /// Loop Info analysis.
183   LoopInfo *LI;
184 
185   /// Target Library Info.
186   const TargetLibraryInfo *TLI;
187 
188   /// Target Transform Info.
189   const TargetTransformInfo *TTI;
190 
191   /// The legality analysis.
192   LoopVectorizationLegality *Legal;
193 
194   /// The profitablity analysis.
195   LoopVectorizationCostModel &CM;
196 
197   using VPlanPtr = std::unique_ptr<VPlan>;
198 
199   SmallVector<VPlanPtr, 4> VPlans;
200 
201   /// This class is used to enable the VPlan to invoke a method of ILV. This is
202   /// needed until the method is refactored out of ILV and becomes reusable.
203   struct VPCallbackILV : public VPCallback {
204     InnerLoopVectorizer &ILV;
205 
206     VPCallbackILV(InnerLoopVectorizer &ILV) : ILV(ILV) {}
207 
208     Value *getOrCreateVectorValues(Value *V, unsigned Part) override;
209   };
210 
211   /// A builder used to construct the current plan.
212   VPBuilder Builder;
213 
214   unsigned BestVF = 0;
215   unsigned BestUF = 0;
216 
217 public:
218   LoopVectorizationPlanner(Loop *L, LoopInfo *LI, const TargetLibraryInfo *TLI,
219                            const TargetTransformInfo *TTI,
220                            LoopVectorizationLegality *Legal,
221                            LoopVectorizationCostModel &CM)
222       : OrigLoop(L), LI(LI), TLI(TLI), TTI(TTI), Legal(Legal), CM(CM) {}
223 
224   /// Plan how to best vectorize, return the best VF and its cost.
225   VectorizationFactor plan(bool OptForSize, unsigned UserVF);
226 
227   /// Use the VPlan-native path to plan how to best vectorize, return the best
228   /// VF and its cost.
229   VectorizationFactor planInVPlanNativePath(bool OptForSize, unsigned UserVF);
230 
231   /// Finalize the best decision and dispose of all other VPlans.
232   void setBestPlan(unsigned VF, unsigned UF);
233 
234   /// Generate the IR code for the body of the vectorized loop according to the
235   /// best selected VPlan.
236   void executePlan(InnerLoopVectorizer &LB, DominatorTree *DT);
237 
238   void printPlans(raw_ostream &O) {
239     for (const auto &Plan : VPlans)
240       O << *Plan;
241   }
242 
243   /// Test a \p Predicate on a \p Range of VF's. Return the value of applying
244   /// \p Predicate on Range.Start, possibly decreasing Range.End such that the
245   /// returned value holds for the entire \p Range.
246   static bool
247   getDecisionAndClampRange(const std::function<bool(unsigned)> &Predicate,
248                            VFRange &Range);
249 
250 protected:
251   /// Collect the instructions from the original loop that would be trivially
252   /// dead in the vectorized loop if generated.
253   void collectTriviallyDeadInstructions(
254       SmallPtrSetImpl<Instruction *> &DeadInstructions);
255 
256   /// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive,
257   /// according to the information gathered by Legal when it checked if it is
258   /// legal to vectorize the loop.
259   void buildVPlans(unsigned MinVF, unsigned MaxVF);
260 
261 private:
262   /// Build a VPlan according to the information gathered by Legal. \return a
263   /// VPlan for vectorization factors \p Range.Start and up to \p Range.End
264   /// exclusive, possibly decreasing \p Range.End.
265   VPlanPtr buildVPlan(VFRange &Range);
266 
267   /// Build a VPlan using VPRecipes according to the information gather by
268   /// Legal. This method is only used for the legacy inner loop vectorizer.
269   VPlanPtr
270   buildVPlanWithVPRecipes(VFRange &Range, SmallPtrSetImpl<Value *> &NeedDef,
271                           SmallPtrSetImpl<Instruction *> &DeadInstructions);
272 
273   /// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive,
274   /// according to the information gathered by Legal when it checked if it is
275   /// legal to vectorize the loop. This method creates VPlans using VPRecipes.
276   void buildVPlansWithVPRecipes(unsigned MinVF, unsigned MaxVF);
277 };
278 
279 } // namespace llvm
280 
281 #endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H
282