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   // Width 1 means no vectorization, cost 0 means uncomputed cost.
176   static VectorizationFactor Disabled() { return {1, 0}; }
177 
178   bool operator==(const VectorizationFactor &rhs) const {
179     return Width == rhs.Width && Cost == rhs.Cost;
180   }
181 };
182 
183 /// Planner drives the vectorization process after having passed
184 /// Legality checks.
185 class LoopVectorizationPlanner {
186   /// The loop that we evaluate.
187   Loop *OrigLoop;
188 
189   /// Loop Info analysis.
190   LoopInfo *LI;
191 
192   /// Target Library Info.
193   const TargetLibraryInfo *TLI;
194 
195   /// Target Transform Info.
196   const TargetTransformInfo *TTI;
197 
198   /// The legality analysis.
199   LoopVectorizationLegality *Legal;
200 
201   /// The profitability analysis.
202   LoopVectorizationCostModel &CM;
203 
204   /// The interleaved access analysis.
205   InterleavedAccessInfo &IAI;
206 
207   SmallVector<VPlanPtr, 4> VPlans;
208 
209   /// This class is used to enable the VPlan to invoke a method of ILV. This is
210   /// needed until the method is refactored out of ILV and becomes reusable.
211   struct VPCallbackILV : public VPCallback {
212     InnerLoopVectorizer &ILV;
213 
214     VPCallbackILV(InnerLoopVectorizer &ILV) : ILV(ILV) {}
215 
216     Value *getOrCreateVectorValues(Value *V, unsigned Part) override;
217     Value *getOrCreateScalarValue(Value *V,
218                                   const VPIteration &Instance) override;
219   };
220 
221   /// A builder used to construct the current plan.
222   VPBuilder Builder;
223 
224   unsigned BestVF = 0;
225   unsigned BestUF = 0;
226 
227 public:
228   LoopVectorizationPlanner(Loop *L, LoopInfo *LI, const TargetLibraryInfo *TLI,
229                            const TargetTransformInfo *TTI,
230                            LoopVectorizationLegality *Legal,
231                            LoopVectorizationCostModel &CM,
232                            InterleavedAccessInfo &IAI)
233       : OrigLoop(L), LI(LI), TLI(TLI), TTI(TTI), Legal(Legal), CM(CM),
234         IAI(IAI) {}
235 
236   /// Plan how to best vectorize, return the best VF and its cost, or None if
237   /// vectorization and interleaving should be avoided up front.
238   Optional<VectorizationFactor> plan(unsigned UserVF);
239 
240   /// Use the VPlan-native path to plan how to best vectorize, return the best
241   /// VF and its cost.
242   VectorizationFactor planInVPlanNativePath(unsigned UserVF);
243 
244   /// Finalize the best decision and dispose of all other VPlans.
245   void setBestPlan(unsigned VF, unsigned UF);
246 
247   /// Generate the IR code for the body of the vectorized loop according to the
248   /// best selected VPlan.
249   void executePlan(InnerLoopVectorizer &LB, DominatorTree *DT);
250 
251   void printPlans(raw_ostream &O) {
252     for (const auto &Plan : VPlans)
253       O << *Plan;
254   }
255 
256   /// Test a \p Predicate on a \p Range of VF's. Return the value of applying
257   /// \p Predicate on Range.Start, possibly decreasing Range.End such that the
258   /// returned value holds for the entire \p Range.
259   static bool
260   getDecisionAndClampRange(const std::function<bool(unsigned)> &Predicate,
261                            VFRange &Range);
262 
263 protected:
264   /// Collect the instructions from the original loop that would be trivially
265   /// dead in the vectorized loop if generated.
266   void collectTriviallyDeadInstructions(
267       SmallPtrSetImpl<Instruction *> &DeadInstructions);
268 
269   /// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive,
270   /// according to the information gathered by Legal when it checked if it is
271   /// legal to vectorize the loop.
272   void buildVPlans(unsigned MinVF, unsigned MaxVF);
273 
274 private:
275   /// Build a VPlan according to the information gathered by Legal. \return a
276   /// VPlan for vectorization factors \p Range.Start and up to \p Range.End
277   /// exclusive, possibly decreasing \p Range.End.
278   VPlanPtr buildVPlan(VFRange &Range);
279 
280   /// Build a VPlan using VPRecipes according to the information gather by
281   /// Legal. This method is only used for the legacy inner loop vectorizer.
282   VPlanPtr buildVPlanWithVPRecipes(
283       VFRange &Range, SmallPtrSetImpl<Value *> &NeedDef,
284       SmallPtrSetImpl<Instruction *> &DeadInstructions,
285       const DenseMap<Instruction *, Instruction *> &SinkAfter);
286 
287   /// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive,
288   /// according to the information gathered by Legal when it checked if it is
289   /// legal to vectorize the loop. This method creates VPlans using VPRecipes.
290   void buildVPlansWithVPRecipes(unsigned MinVF, unsigned MaxVF);
291 };
292 
293 } // namespace llvm
294 
295 #endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H
296