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/Support/InstructionCost.h" 29 30 namespace llvm { 31 32 class LoopInfo; 33 class LoopVectorizationLegality; 34 class LoopVectorizationCostModel; 35 class PredicatedScalarEvolution; 36 class LoopVectorizeHints; 37 class OptimizationRemarkEmitter; 38 class TargetTransformInfo; 39 class TargetLibraryInfo; 40 class VPRecipeBuilder; 41 42 /// VPlan-based builder utility analogous to IRBuilder. 43 class VPBuilder { 44 VPBasicBlock *BB = nullptr; 45 VPBasicBlock::iterator InsertPt = VPBasicBlock::iterator(); 46 47 VPInstruction *createInstruction(unsigned Opcode, 48 ArrayRef<VPValue *> Operands, DebugLoc DL, 49 const Twine &Name = "") { 50 VPInstruction *Instr = new VPInstruction(Opcode, Operands, DL, Name); 51 if (BB) 52 BB->insert(Instr, InsertPt); 53 return Instr; 54 } 55 56 VPInstruction *createInstruction(unsigned Opcode, 57 std::initializer_list<VPValue *> Operands, 58 DebugLoc DL, const Twine &Name = "") { 59 return createInstruction(Opcode, ArrayRef<VPValue *>(Operands), DL, Name); 60 } 61 62 public: 63 VPBuilder() = default; 64 65 /// Clear the insertion point: created instructions will not be inserted into 66 /// a block. 67 void clearInsertionPoint() { 68 BB = nullptr; 69 InsertPt = VPBasicBlock::iterator(); 70 } 71 72 VPBasicBlock *getInsertBlock() const { return BB; } 73 VPBasicBlock::iterator getInsertPoint() const { return InsertPt; } 74 75 /// InsertPoint - A saved insertion point. 76 class VPInsertPoint { 77 VPBasicBlock *Block = nullptr; 78 VPBasicBlock::iterator Point; 79 80 public: 81 /// Creates a new insertion point which doesn't point to anything. 82 VPInsertPoint() = default; 83 84 /// Creates a new insertion point at the given location. 85 VPInsertPoint(VPBasicBlock *InsertBlock, VPBasicBlock::iterator InsertPoint) 86 : Block(InsertBlock), Point(InsertPoint) {} 87 88 /// Returns true if this insert point is set. 89 bool isSet() const { return Block != nullptr; } 90 91 VPBasicBlock *getBlock() const { return Block; } 92 VPBasicBlock::iterator getPoint() const { return Point; } 93 }; 94 95 /// Sets the current insert point to a previously-saved location. 96 void restoreIP(VPInsertPoint IP) { 97 if (IP.isSet()) 98 setInsertPoint(IP.getBlock(), IP.getPoint()); 99 else 100 clearInsertionPoint(); 101 } 102 103 /// This specifies that created VPInstructions should be appended to the end 104 /// of the specified block. 105 void setInsertPoint(VPBasicBlock *TheBB) { 106 assert(TheBB && "Attempting to set a null insert point"); 107 BB = TheBB; 108 InsertPt = BB->end(); 109 } 110 111 /// This specifies that created instructions should be inserted at the 112 /// specified point. 113 void setInsertPoint(VPBasicBlock *TheBB, VPBasicBlock::iterator IP) { 114 BB = TheBB; 115 InsertPt = IP; 116 } 117 118 /// Insert and return the specified instruction. 119 VPInstruction *insert(VPInstruction *I) const { 120 BB->insert(I, InsertPt); 121 return I; 122 } 123 124 /// Create an N-ary operation with \p Opcode, \p Operands and set \p Inst as 125 /// its underlying Instruction. 126 VPValue *createNaryOp(unsigned Opcode, ArrayRef<VPValue *> Operands, 127 Instruction *Inst = nullptr, const Twine &Name = "") { 128 DebugLoc DL; 129 if (Inst) 130 DL = Inst->getDebugLoc(); 131 VPInstruction *NewVPInst = createInstruction(Opcode, Operands, DL, Name); 132 NewVPInst->setUnderlyingValue(Inst); 133 return NewVPInst; 134 } 135 VPValue *createNaryOp(unsigned Opcode, ArrayRef<VPValue *> Operands, 136 DebugLoc DL, const Twine &Name = "") { 137 return createInstruction(Opcode, Operands, DL, Name); 138 } 139 140 VPValue *createNot(VPValue *Operand, DebugLoc DL, const Twine &Name = "") { 141 return createInstruction(VPInstruction::Not, {Operand}, DL, Name); 142 } 143 144 VPValue *createAnd(VPValue *LHS, VPValue *RHS, DebugLoc DL, 145 const Twine &Name = "") { 146 return createInstruction(Instruction::BinaryOps::And, {LHS, RHS}, DL, Name); 147 } 148 149 VPValue *createOr(VPValue *LHS, VPValue *RHS, DebugLoc DL, 150 const Twine &Name = "") { 151 return createInstruction(Instruction::BinaryOps::Or, {LHS, RHS}, DL, Name); 152 } 153 154 VPValue *createSelect(VPValue *Cond, VPValue *TrueVal, VPValue *FalseVal, 155 DebugLoc DL, const Twine &Name = "") { 156 return createNaryOp(Instruction::Select, {Cond, TrueVal, FalseVal}, DL, 157 Name); 158 } 159 160 //===--------------------------------------------------------------------===// 161 // RAII helpers. 162 //===--------------------------------------------------------------------===// 163 164 /// RAII object that stores the current insertion point and restores it when 165 /// the object is destroyed. 166 class InsertPointGuard { 167 VPBuilder &Builder; 168 VPBasicBlock *Block; 169 VPBasicBlock::iterator Point; 170 171 public: 172 InsertPointGuard(VPBuilder &B) 173 : Builder(B), Block(B.getInsertBlock()), Point(B.getInsertPoint()) {} 174 175 InsertPointGuard(const InsertPointGuard &) = delete; 176 InsertPointGuard &operator=(const InsertPointGuard &) = delete; 177 178 ~InsertPointGuard() { Builder.restoreIP(VPInsertPoint(Block, Point)); } 179 }; 180 }; 181 182 /// TODO: The following VectorizationFactor was pulled out of 183 /// LoopVectorizationCostModel class. LV also deals with 184 /// VectorizerParams::VectorizationFactor and VectorizationCostTy. 185 /// We need to streamline them. 186 187 /// Information about vectorization costs. 188 struct VectorizationFactor { 189 /// Vector width with best cost. 190 ElementCount Width; 191 /// Cost of the loop with that width. 192 InstructionCost Cost; 193 194 /// Cost of the scalar loop. 195 InstructionCost ScalarCost; 196 197 /// The minimum trip count required to make vectorization profitable, e.g. due 198 /// to runtime checks. 199 ElementCount MinProfitableTripCount; 200 201 VectorizationFactor(ElementCount Width, InstructionCost Cost, 202 InstructionCost ScalarCost) 203 : Width(Width), Cost(Cost), ScalarCost(ScalarCost) {} 204 205 /// Width 1 means no vectorization, cost 0 means uncomputed cost. 206 static VectorizationFactor Disabled() { 207 return {ElementCount::getFixed(1), 0, 0}; 208 } 209 210 bool operator==(const VectorizationFactor &rhs) const { 211 return Width == rhs.Width && Cost == rhs.Cost; 212 } 213 214 bool operator!=(const VectorizationFactor &rhs) const { 215 return !(*this == rhs); 216 } 217 }; 218 219 /// A class that represents two vectorization factors (initialized with 0 by 220 /// default). One for fixed-width vectorization and one for scalable 221 /// vectorization. This can be used by the vectorizer to choose from a range of 222 /// fixed and/or scalable VFs in order to find the most cost-effective VF to 223 /// vectorize with. 224 struct FixedScalableVFPair { 225 ElementCount FixedVF; 226 ElementCount ScalableVF; 227 228 FixedScalableVFPair() 229 : FixedVF(ElementCount::getFixed(0)), 230 ScalableVF(ElementCount::getScalable(0)) {} 231 FixedScalableVFPair(const ElementCount &Max) : FixedScalableVFPair() { 232 *(Max.isScalable() ? &ScalableVF : &FixedVF) = Max; 233 } 234 FixedScalableVFPair(const ElementCount &FixedVF, 235 const ElementCount &ScalableVF) 236 : FixedVF(FixedVF), ScalableVF(ScalableVF) { 237 assert(!FixedVF.isScalable() && ScalableVF.isScalable() && 238 "Invalid scalable properties"); 239 } 240 241 static FixedScalableVFPair getNone() { return FixedScalableVFPair(); } 242 243 /// \return true if either fixed- or scalable VF is non-zero. 244 explicit operator bool() const { return FixedVF || ScalableVF; } 245 246 /// \return true if either fixed- or scalable VF is a valid vector VF. 247 bool hasVector() const { return FixedVF.isVector() || ScalableVF.isVector(); } 248 }; 249 250 /// Planner drives the vectorization process after having passed 251 /// Legality checks. 252 class LoopVectorizationPlanner { 253 /// The loop that we evaluate. 254 Loop *OrigLoop; 255 256 /// Loop Info analysis. 257 LoopInfo *LI; 258 259 /// Target Library Info. 260 const TargetLibraryInfo *TLI; 261 262 /// Target Transform Info. 263 const TargetTransformInfo *TTI; 264 265 /// The legality analysis. 266 LoopVectorizationLegality *Legal; 267 268 /// The profitability analysis. 269 LoopVectorizationCostModel &CM; 270 271 /// The interleaved access analysis. 272 InterleavedAccessInfo &IAI; 273 274 PredicatedScalarEvolution &PSE; 275 276 const LoopVectorizeHints &Hints; 277 278 OptimizationRemarkEmitter *ORE; 279 280 SmallVector<VPlanPtr, 4> VPlans; 281 282 /// A builder used to construct the current plan. 283 VPBuilder Builder; 284 285 public: 286 LoopVectorizationPlanner(Loop *L, LoopInfo *LI, const TargetLibraryInfo *TLI, 287 const TargetTransformInfo *TTI, 288 LoopVectorizationLegality *Legal, 289 LoopVectorizationCostModel &CM, 290 InterleavedAccessInfo &IAI, 291 PredicatedScalarEvolution &PSE, 292 const LoopVectorizeHints &Hints, 293 OptimizationRemarkEmitter *ORE) 294 : OrigLoop(L), LI(LI), TLI(TLI), TTI(TTI), Legal(Legal), CM(CM), IAI(IAI), 295 PSE(PSE), Hints(Hints), ORE(ORE) {} 296 297 /// Plan how to best vectorize, return the best VF and its cost, or None if 298 /// vectorization and interleaving should be avoided up front. 299 Optional<VectorizationFactor> plan(ElementCount UserVF, unsigned UserIC); 300 301 /// Use the VPlan-native path to plan how to best vectorize, return the best 302 /// VF and its cost. 303 VectorizationFactor planInVPlanNativePath(ElementCount UserVF); 304 305 /// Return the best VPlan for \p VF. 306 VPlan &getBestPlanFor(ElementCount VF) const; 307 308 /// Generate the IR code for the body of the vectorized loop according to the 309 /// best selected \p VF, \p UF and VPlan \p BestPlan. 310 /// TODO: \p IsEpilogueVectorization is needed to avoid issues due to epilogue 311 /// vectorization re-using plans for both the main and epilogue vector loops. 312 /// It should be removed once the re-use issue has been fixed. 313 void executePlan(ElementCount VF, unsigned UF, VPlan &BestPlan, 314 InnerLoopVectorizer &LB, DominatorTree *DT, 315 bool IsEpilogueVectorization); 316 317 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 318 void printPlans(raw_ostream &O); 319 #endif 320 321 /// Look through the existing plans and return true if we have one with all 322 /// the vectorization factors in question. 323 bool hasPlanWithVF(ElementCount VF) const { 324 return any_of(VPlans, 325 [&](const VPlanPtr &Plan) { return Plan->hasVF(VF); }); 326 } 327 328 /// Test a \p Predicate on a \p Range of VF's. Return the value of applying 329 /// \p Predicate on Range.Start, possibly decreasing Range.End such that the 330 /// returned value holds for the entire \p Range. 331 static bool 332 getDecisionAndClampRange(const std::function<bool(ElementCount)> &Predicate, 333 VFRange &Range); 334 335 /// Check if the number of runtime checks exceeds the threshold. 336 bool requiresTooManyRuntimeChecks() const; 337 338 protected: 339 /// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive, 340 /// according to the information gathered by Legal when it checked if it is 341 /// legal to vectorize the loop. 342 void buildVPlans(ElementCount MinVF, ElementCount MaxVF); 343 344 private: 345 /// Build a VPlan according to the information gathered by Legal. \return a 346 /// VPlan for vectorization factors \p Range.Start and up to \p Range.End 347 /// exclusive, possibly decreasing \p Range.End. 348 VPlanPtr buildVPlan(VFRange &Range); 349 350 /// Build a VPlan using VPRecipes according to the information gather by 351 /// Legal. This method is only used for the legacy inner loop vectorizer. 352 VPlanPtr buildVPlanWithVPRecipes( 353 VFRange &Range, SmallPtrSetImpl<Instruction *> &DeadInstructions, 354 const MapVector<Instruction *, Instruction *> &SinkAfter); 355 356 /// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive, 357 /// according to the information gathered by Legal when it checked if it is 358 /// legal to vectorize the loop. This method creates VPlans using VPRecipes. 359 void buildVPlansWithVPRecipes(ElementCount MinVF, ElementCount MaxVF); 360 361 // Adjust the recipes for reductions. For in-loop reductions the chain of 362 // instructions leading from the loop exit instr to the phi need to be 363 // converted to reductions, with one operand being vector and the other being 364 // the scalar reduction chain. For other reductions, a select is introduced 365 // between the phi and live-out recipes when folding the tail. 366 void adjustRecipesForReductions(VPBasicBlock *LatchVPBB, VPlanPtr &Plan, 367 VPRecipeBuilder &RecipeBuilder, 368 ElementCount MinVF); 369 }; 370 371 } // namespace llvm 372 373 #endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H 374