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