1 //===- LoopVectorizationPlanner.h - Planner for LoopVectorization ---------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// This file provides a LoopVectorizationPlanner class.
12 /// InnerLoopVectorizer vectorizes loops which contain only one basic
13 /// LoopVectorizationPlanner - drives the vectorization process after having
14 /// passed Legality checks.
15 /// The planner builds and optimizes the Vectorization Plans which record the
16 /// decisions how to vectorize the given loop. In particular, represent the
17 /// control-flow of the vectorized version, the replication of instructions that
18 /// are to be scalarized, and interleave access groups.
19 ///
20 /// Also provides a VPlan-based builder utility analogous to IRBuilder.
21 /// It provides an instruction-level API for generating VPInstructions while
22 /// abstracting away the Recipe manipulation details.
23 //===----------------------------------------------------------------------===//
24 
25 #ifndef LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H
26 #define LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H
27 
28 #include "VPlan.h"
29 #include "llvm/Analysis/LoopInfo.h"
30 #include "llvm/Analysis/TargetLibraryInfo.h"
31 #include "llvm/Analysis/TargetTransformInfo.h"
32 
33 namespace llvm {
34 
35 /// VPlan-based builder utility analogous to IRBuilder.
36 class VPBuilder {
37 private:
38   VPBasicBlock *BB = nullptr;
39   VPBasicBlock::iterator InsertPt = VPBasicBlock::iterator();
40 
41   VPInstruction *createInstruction(unsigned Opcode,
42                                    std::initializer_list<VPValue *> Operands) {
43     VPInstruction *Instr = new VPInstruction(Opcode, Operands);
44     BB->insert(Instr, InsertPt);
45     return Instr;
46   }
47 
48 public:
49   VPBuilder() {}
50 
51   /// This specifies that created VPInstructions should be appended to
52   /// the end of the specified block.
53   void setInsertPoint(VPBasicBlock *TheBB) {
54     assert(TheBB && "Attempting to set a null insert point");
55     BB = TheBB;
56     InsertPt = BB->end();
57   }
58 
59   VPValue *createNot(VPValue *Operand) {
60     return createInstruction(VPInstruction::Not, {Operand});
61   }
62 
63   VPValue *createAnd(VPValue *LHS, VPValue *RHS) {
64     return createInstruction(Instruction::BinaryOps::And, {LHS, RHS});
65   }
66 
67   VPValue *createOr(VPValue *LHS, VPValue *RHS) {
68     return createInstruction(Instruction::BinaryOps::Or, {LHS, RHS});
69   }
70 };
71 
72 
73 /// TODO: The following VectorizationFactor was pulled out of
74 /// LoopVectorizationCostModel class. LV also deals with
75 /// VectorizerParams::VectorizationFactor and VectorizationCostTy.
76 /// We need to streamline them.
77 
78 /// Information about vectorization costs
79 struct VectorizationFactor {
80   // Vector width with best cost
81   unsigned Width;
82   // Cost of the loop with that width
83   unsigned Cost;
84 };
85 
86 /// Planner drives the vectorization process after having passed
87 /// Legality checks.
88 class LoopVectorizationPlanner {
89   /// The loop that we evaluate.
90   Loop *OrigLoop;
91 
92   /// Loop Info analysis.
93   LoopInfo *LI;
94 
95   /// Target Library Info.
96   const TargetLibraryInfo *TLI;
97 
98   /// Target Transform Info.
99   const TargetTransformInfo *TTI;
100 
101   /// The legality analysis.
102   LoopVectorizationLegality *Legal;
103 
104   /// The profitablity analysis.
105   LoopVectorizationCostModel &CM;
106 
107   using VPlanPtr = std::unique_ptr<VPlan>;
108 
109   SmallVector<VPlanPtr, 4> VPlans;
110 
111   /// This class is used to enable the VPlan to invoke a method of ILV. This is
112   /// needed until the method is refactored out of ILV and becomes reusable.
113   struct VPCallbackILV : public VPCallback {
114     InnerLoopVectorizer &ILV;
115 
116     VPCallbackILV(InnerLoopVectorizer &ILV) : ILV(ILV) {}
117 
118     Value *getOrCreateVectorValues(Value *V, unsigned Part) override;
119   };
120 
121   /// A builder used to construct the current plan.
122   VPBuilder Builder;
123 
124   /// When we if-convert we need to create edge masks. We have to cache values
125   /// so that we don't end up with exponential recursion/IR. Note that
126   /// if-conversion currently takes place during VPlan-construction, so these
127   /// caches are only used at that stage.
128   using EdgeMaskCacheTy =
129       DenseMap<std::pair<BasicBlock *, BasicBlock *>, VPValue *>;
130   using BlockMaskCacheTy = DenseMap<BasicBlock *, VPValue *>;
131   EdgeMaskCacheTy EdgeMaskCache;
132   BlockMaskCacheTy BlockMaskCache;
133 
134   unsigned BestVF = 0;
135   unsigned BestUF = 0;
136 
137 public:
138   LoopVectorizationPlanner(Loop *L, LoopInfo *LI, const TargetLibraryInfo *TLI,
139                            const TargetTransformInfo *TTI,
140                            LoopVectorizationLegality *Legal,
141                            LoopVectorizationCostModel &CM)
142       : OrigLoop(L), LI(LI), TLI(TLI), TTI(TTI), Legal(Legal), CM(CM) {}
143 
144   /// Plan how to best vectorize, return the best VF and its cost.
145   VectorizationFactor plan(bool OptForSize, unsigned UserVF);
146 
147   /// Use the VPlan-native path to plan how to best vectorize, return the best
148   /// VF and its cost.
149   VectorizationFactor planInVPlanNativePath(bool OptForSize, unsigned UserVF);
150 
151   /// Finalize the best decision and dispose of all other VPlans.
152   void setBestPlan(unsigned VF, unsigned UF);
153 
154   /// Generate the IR code for the body of the vectorized loop according to the
155   /// best selected VPlan.
156   void executePlan(InnerLoopVectorizer &LB, DominatorTree *DT);
157 
158   void printPlans(raw_ostream &O) {
159     for (const auto &Plan : VPlans)
160       O << *Plan;
161   }
162 
163 protected:
164   /// Collect the instructions from the original loop that would be trivially
165   /// dead in the vectorized loop if generated.
166   void collectTriviallyDeadInstructions(
167       SmallPtrSetImpl<Instruction *> &DeadInstructions);
168 
169   /// A range of powers-of-2 vectorization factors with fixed start and
170   /// adjustable end. The range includes start and excludes end, e.g.,:
171   /// [1, 9) = {1, 2, 4, 8}
172   struct VFRange {
173     // A power of 2.
174     const unsigned Start;
175 
176     // Need not be a power of 2. If End <= Start range is empty.
177     unsigned End;
178   };
179 
180   /// Test a \p Predicate on a \p Range of VF's. Return the value of applying
181   /// \p Predicate on Range.Start, possibly decreasing Range.End such that the
182   /// returned value holds for the entire \p Range.
183   bool getDecisionAndClampRange(const std::function<bool(unsigned)> &Predicate,
184                                 VFRange &Range);
185 
186   /// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive,
187   /// according to the information gathered by Legal when it checked if it is
188   /// legal to vectorize the loop.
189   void buildVPlans(unsigned MinVF, unsigned MaxVF);
190 
191 private:
192   /// A helper function that computes the predicate of the block BB, assuming
193   /// that the header block of the loop is set to True. It returns the *entry*
194   /// mask for the block BB.
195   VPValue *createBlockInMask(BasicBlock *BB, VPlanPtr &Plan);
196 
197   /// A helper function that computes the predicate of the edge between SRC
198   /// and DST.
199   VPValue *createEdgeMask(BasicBlock *Src, BasicBlock *Dst, VPlanPtr &Plan);
200 
201   /// Check if \I belongs to an Interleave Group within the given VF \p Range,
202   /// \return true in the first returned value if so and false otherwise.
203   /// Build a new VPInterleaveGroup Recipe if \I is the primary member of an IG
204   /// for \p Range.Start, and provide it as the second returned value.
205   /// Note that if \I is an adjunct member of an IG for \p Range.Start, the
206   /// \return value is <true, nullptr>, as it is handled by another recipe.
207   /// \p Range.End may be decreased to ensure same decision from \p Range.Start
208   /// to \p Range.End.
209   VPInterleaveRecipe *tryToInterleaveMemory(Instruction *I, VFRange &Range);
210 
211   // Check if \I is a memory instruction to be widened for \p Range.Start and
212   // potentially masked. Such instructions are handled by a recipe that takes an
213   // additional VPInstruction for the mask.
214   VPWidenMemoryInstructionRecipe *tryToWidenMemory(Instruction *I,
215                                                    VFRange &Range,
216                                                    VPlanPtr &Plan);
217 
218   /// Check if an induction recipe should be constructed for \I within the given
219   /// VF \p Range. If so build and return it. If not, return null. \p Range.End
220   /// may be decreased to ensure same decision from \p Range.Start to
221   /// \p Range.End.
222   VPWidenIntOrFpInductionRecipe *tryToOptimizeInduction(Instruction *I,
223                                                         VFRange &Range);
224 
225   /// Handle non-loop phi nodes. Currently all such phi nodes are turned into
226   /// a sequence of select instructions as the vectorizer currently performs
227   /// full if-conversion.
228   VPBlendRecipe *tryToBlend(Instruction *I, VPlanPtr &Plan);
229 
230   /// Check if \p I can be widened within the given VF \p Range. If \p I can be
231   /// widened for \p Range.Start, check if the last recipe of \p VPBB can be
232   /// extended to include \p I or else build a new VPWidenRecipe for it and
233   /// append it to \p VPBB. Return true if \p I can be widened for Range.Start,
234   /// false otherwise. Range.End may be decreased to ensure same decision from
235   /// \p Range.Start to \p Range.End.
236   bool tryToWiden(Instruction *I, VPBasicBlock *VPBB, VFRange &Range);
237 
238   /// Build a VPReplicationRecipe for \p I and enclose it within a Region if it
239   /// is predicated. \return \p VPBB augmented with this new recipe if \p I is
240   /// not predicated, otherwise \return a new VPBasicBlock that succeeds the new
241   /// Region. Update the packing decision of predicated instructions if they
242   /// feed \p I. Range.End may be decreased to ensure same recipe behavior from
243   /// \p Range.Start to \p Range.End.
244   VPBasicBlock *handleReplication(
245       Instruction *I, VFRange &Range, VPBasicBlock *VPBB,
246       DenseMap<Instruction *, VPReplicateRecipe *> &PredInst2Recipe,
247       VPlanPtr &Plan);
248 
249   /// Create a replicating region for instruction \p I that requires
250   /// predication. \p PredRecipe is a VPReplicateRecipe holding \p I.
251   VPRegionBlock *createReplicateRegion(Instruction *I, VPRecipeBase *PredRecipe,
252                                        VPlanPtr &Plan);
253 
254   /// Build a VPlan according to the information gathered by Legal. \return a
255   /// VPlan for vectorization factors \p Range.Start and up to \p Range.End
256   /// exclusive, possibly decreasing \p Range.End.
257   VPlanPtr buildVPlan(VFRange &Range,
258                                     const SmallPtrSetImpl<Value *> &NeedDef);
259 };
260 
261 } // namespace llvm
262 
263 #endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H
264