LLVM  9.0.0svn
LoopVectorizationPlanner.h
Go to the documentation of this file.
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"
31 
32 namespace llvm {
33 
34 /// VPlan-based builder utility analogous to IRBuilder.
35 class VPBuilder {
36 private:
37  VPBasicBlock *BB = nullptr;
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.
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;
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.
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.
88  if (IP.isSet())
89  setInsertPoint(IP.getBlock(), IP.getPoint());
90  else
92  }
93 
94  /// This specifies that created VPInstructions should be appended to the end
95  /// of the specified block.
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.
105  BB = TheBB;
106  InsertPt = IP;
107  }
108 
109  /// Insert and return the specified instruction.
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 
134  return createInstruction(Instruction::BinaryOps::And, {LHS, RHS});
135  }
136 
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.
148  VPBuilder &Builder;
149  VPBasicBlock *Block;
151 
152  public:
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
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.
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.
200 
201  /// The profitability analysis.
203 
205 
206  /// This class is used to enable the VPlan to invoke a method of ILV. This is
207  /// needed until the method is refactored out of ILV and becomes reusable.
208  struct VPCallbackILV : public VPCallback {
209  InnerLoopVectorizer &ILV;
210 
211  VPCallbackILV(InnerLoopVectorizer &ILV) : ILV(ILV) {}
212 
213  Value *getOrCreateVectorValues(Value *V, unsigned Part) override;
214  };
215 
216  /// A builder used to construct the current plan.
217  VPBuilder Builder;
218 
219  unsigned BestVF = 0;
220  unsigned BestUF = 0;
221 
222 public:
224  const TargetTransformInfo *TTI,
227  : OrigLoop(L), LI(LI), TLI(TLI), TTI(TTI), Legal(Legal), CM(CM) {}
228 
229  /// Plan how to best vectorize, return the best VF and its cost, or None if
230  /// vectorization and interleaving should be avoided up front.
231  Optional<VectorizationFactor> plan(bool OptForSize, unsigned UserVF);
232 
233  /// Use the VPlan-native path to plan how to best vectorize, return the best
234  /// VF and its cost.
235  VectorizationFactor planInVPlanNativePath(bool OptForSize, unsigned UserVF);
236 
237  /// Finalize the best decision and dispose of all other VPlans.
238  void setBestPlan(unsigned VF, unsigned UF);
239 
240  /// Generate the IR code for the body of the vectorized loop according to the
241  /// best selected VPlan.
242  void executePlan(InnerLoopVectorizer &LB, DominatorTree *DT);
243 
245  for (const auto &Plan : VPlans)
246  O << *Plan;
247  }
248 
249  /// Test a \p Predicate on a \p Range of VF's. Return the value of applying
250  /// \p Predicate on Range.Start, possibly decreasing Range.End such that the
251  /// returned value holds for the entire \p Range.
252  static bool
253  getDecisionAndClampRange(const std::function<bool(unsigned)> &Predicate,
254  VFRange &Range);
255 
256 protected:
257  /// Collect the instructions from the original loop that would be trivially
258  /// dead in the vectorized loop if generated.
259  void collectTriviallyDeadInstructions(
260  SmallPtrSetImpl<Instruction *> &DeadInstructions);
261 
262  /// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive,
263  /// according to the information gathered by Legal when it checked if it is
264  /// legal to vectorize the loop.
265  void buildVPlans(unsigned MinVF, unsigned MaxVF);
266 
267 private:
268  /// Build a VPlan according to the information gathered by Legal. \return a
269  /// VPlan for vectorization factors \p Range.Start and up to \p Range.End
270  /// exclusive, possibly decreasing \p Range.End.
271  VPlanPtr buildVPlan(VFRange &Range);
272 
273  /// Build a VPlan using VPRecipes according to the information gather by
274  /// Legal. This method is only used for the legacy inner loop vectorizer.
275  VPlanPtr
276  buildVPlanWithVPRecipes(VFRange &Range, SmallPtrSetImpl<Value *> &NeedDef,
277  SmallPtrSetImpl<Instruction *> &DeadInstructions);
278 
279  /// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive,
280  /// according to the information gathered by Legal when it checked if it is
281  /// legal to vectorize the loop. This method creates VPlans using VPRecipes.
282  void buildVPlansWithVPRecipes(unsigned MinVF, unsigned MaxVF);
283 };
284 
285 } // namespace llvm
286 
287 #endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H
RAII object that stores the current insertion point and restores it when the object is destroyed...
bool isSet() const
Returns true if this insert point is set.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
InnerLoopVectorizer vectorizes loops which contain only one basic block to a specified vectorization ...
TODO: The following VectorizationFactor was pulled out of LoopVectorizationCostModel class...
void setUnderlyingValue(Value *Val)
Definition: VPlanValue.h:67
LoopVectorizationLegality checks if it is legal to vectorize a loop, and to what vectorization factor...
VPInsertPoint()=default
Creates a new insertion point which doesn&#39;t point to anything.
static VectorizationFactor Disabled()
VPValue * createNot(VPValue *Operand)
LoopVectorizationPlanner(Loop *L, LoopInfo *LI, const TargetLibraryInfo *TLI, const TargetTransformInfo *TTI, LoopVectorizationLegality *Legal, LoopVectorizationCostModel &CM)
void insert(VPRecipeBase *Recipe, iterator InsertPt)
Definition: VPlan.h:1038
VPValue * createNaryOp(unsigned Opcode, std::initializer_list< VPValue *> Operands, Instruction *Inst=nullptr)
RecipeListTy::iterator iterator
Instruction iterators...
Definition: VPlan.h:1000
This class is used to enable the VPlan to invoke a method of ILV.
Definition: VPlan.h:226
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
VPlan-based builder utility analogous to IRBuilder.
This file contains the declarations of the Vectorization Plan base classes:
VPValue * createNaryOp(unsigned Opcode, ArrayRef< VPValue *> Operands, Instruction *Inst=nullptr)
Create an N-ary operation with Opcode, Operands and set Inst as its underlying Instruction.
std::unique_ptr< VPlan > VPlanPtr
Definition: VPlan.h:75
InsertPoint - A saved insertion point.
VPBasicBlock::iterator getPoint() const
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:982
Planner drives the vectorization process after having passed Legality checks.
Iterator for intrusive lists based on ilist_node.
A range of powers-of-2 vectorization factors with fixed start and adjustable end. ...
Definition: VPlan.h:67
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Provides information about what library functions are available for the current target.
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:26
void setInsertPoint(VPBasicBlock *TheBB, VPBasicBlock::iterator IP)
This specifies that created instructions should be inserted at the specified point.
VPValue * createOr(VPValue *LHS, VPValue *RHS)
void clearInsertionPoint()
Clear the insertion point: created instructions will not be inserted into a block.
VPInstruction * insert(VPInstruction *I) const
Insert and return the specified instruction.
VPBasicBlock::iterator getInsertPoint() const
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:506
#define I(x, y, z)
Definition: MD5.cpp:58
VPBasicBlock * getInsertBlock() const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
iterator end()
Definition: VPlan.h:1010
LoopVectorizationCostModel - estimates the expected speedups due to vectorization.
LLVM Value Representation.
Definition: Value.h:72
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
print Print MemDeps of function
VPValue * createAnd(VPValue *LHS, VPValue *RHS)
void restoreIP(VPInsertPoint IP)
Sets the current insert point to a previously-saved location.
void setInsertPoint(VPBasicBlock *TheBB)
This specifies that created VPInstructions should be appended to the end of the specified block...
This pass exposes codegen information to IR-level passes.
VPInsertPoint(VPBasicBlock *InsertBlock, VPBasicBlock::iterator InsertPoint)
Creates a new insertion point at the given location.
This is a concrete Recipe that models a single VPlan-level instruction.
Definition: VPlan.h:628
bool operator==(const VectorizationFactor &rhs) const
The operation is expected to be selectable directly by the target, and no transformation is necessary...
Definition: LegalizerInfo.h:47