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