LoopVectorizationPlanner.h revision 360784 
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
32namespace llvm {
33
34/// VPlan-based builder utility analogous to IRBuilder.
35class VPBuilder {
36private:
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
53public:
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
169struct 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.
185class 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
227public:
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
263protected:
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
274private:
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