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