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 192 /// Cost of the loop with that width. 193 InstructionCost Cost; 194 195 /// Cost of the scalar loop. 196 InstructionCost ScalarCost; 197 198 /// The minimum trip count required to make vectorization profitable, e.g. due 199 /// to runtime checks. 200 ElementCount MinProfitableTripCount; 201 202 VectorizationFactor(ElementCount Width, InstructionCost Cost, 203 InstructionCost ScalarCost) 204 : Width(Width), Cost(Cost), ScalarCost(ScalarCost) {} 205 206 /// Width 1 means no vectorization, cost 0 means uncomputed cost. 207 static VectorizationFactor Disabled() { 208 return {ElementCount::getFixed(1), 0, 0}; 209 } 210 211 bool operator==(const VectorizationFactor &rhs) const { 212 return Width == rhs.Width && Cost == rhs.Cost; 213 } 214 215 bool operator!=(const VectorizationFactor &rhs) const { 216 return !(*this == rhs); 217 } 218 }; 219 220 /// A class that represents two vectorization factors (initialized with 0 by 221 /// default). One for fixed-width vectorization and one for scalable 222 /// vectorization. This can be used by the vectorizer to choose from a range of 223 /// fixed and/or scalable VFs in order to find the most cost-effective VF to 224 /// vectorize with. 225 struct FixedScalableVFPair { 226 ElementCount FixedVF; 227 ElementCount ScalableVF; 228 229 FixedScalableVFPair() 230 : FixedVF(ElementCount::getFixed(0)), 231 ScalableVF(ElementCount::getScalable(0)) {} 232 FixedScalableVFPair(const ElementCount &Max) : FixedScalableVFPair() { 233 *(Max.isScalable() ? &ScalableVF : &FixedVF) = Max; 234 } 235 FixedScalableVFPair(const ElementCount &FixedVF, 236 const ElementCount &ScalableVF) 237 : FixedVF(FixedVF), ScalableVF(ScalableVF) { 238 assert(!FixedVF.isScalable() && ScalableVF.isScalable() && 239 "Invalid scalable properties"); 240 } 241 242 static FixedScalableVFPair getNone() { return FixedScalableVFPair(); } 243 244 /// \return true if either fixed- or scalable VF is non-zero. 245 explicit operator bool() const { return FixedVF || ScalableVF; } 246 247 /// \return true if either fixed- or scalable VF is a valid vector VF. 248 bool hasVector() const { return FixedVF.isVector() || ScalableVF.isVector(); } 249 }; 250 251 /// Planner drives the vectorization process after having passed 252 /// Legality checks. 253 class LoopVectorizationPlanner { 254 /// The loop that we evaluate. 255 Loop *OrigLoop; 256 257 /// Loop Info analysis. 258 LoopInfo *LI; 259 260 /// Target Library Info. 261 const TargetLibraryInfo *TLI; 262 263 /// Target Transform Info. 264 const TargetTransformInfo *TTI; 265 266 /// The legality analysis. 267 LoopVectorizationLegality *Legal; 268 269 /// The profitability analysis. 270 LoopVectorizationCostModel &CM; 271 272 /// The interleaved access analysis. 273 InterleavedAccessInfo &IAI; 274 275 PredicatedScalarEvolution &PSE; 276 277 const LoopVectorizeHints &Hints; 278 279 OptimizationRemarkEmitter *ORE; 280 281 SmallVector<VPlanPtr, 4> VPlans; 282 283 /// A builder used to construct the current plan. 284 VPBuilder Builder; 285 286 public: 287 LoopVectorizationPlanner(Loop *L, LoopInfo *LI, const TargetLibraryInfo *TLI, 288 const TargetTransformInfo *TTI, 289 LoopVectorizationLegality *Legal, 290 LoopVectorizationCostModel &CM, 291 InterleavedAccessInfo &IAI, 292 PredicatedScalarEvolution &PSE, 293 const LoopVectorizeHints &Hints, 294 OptimizationRemarkEmitter *ORE) 295 : OrigLoop(L), LI(LI), TLI(TLI), TTI(TTI), Legal(Legal), CM(CM), IAI(IAI), 296 PSE(PSE), Hints(Hints), ORE(ORE) {} 297 298 /// Plan how to best vectorize, return the best VF and its cost, or 299 /// std::nullopt if vectorization and interleaving should be avoided up front. 300 std::optional<VectorizationFactor> plan(ElementCount UserVF, unsigned UserIC); 301 302 /// Use the VPlan-native path to plan how to best vectorize, return the best 303 /// VF and its cost. 304 VectorizationFactor planInVPlanNativePath(ElementCount UserVF); 305 306 /// Return the best VPlan for \p VF. 307 VPlan &getBestPlanFor(ElementCount VF) const; 308 309 /// Generate the IR code for the body of the vectorized loop according to the 310 /// best selected \p VF, \p UF and VPlan \p BestPlan. 311 /// TODO: \p IsEpilogueVectorization is needed to avoid issues due to epilogue 312 /// vectorization re-using plans for both the main and epilogue vector loops. 313 /// It should be removed once the re-use issue has been fixed. 314 void executePlan(ElementCount VF, unsigned UF, VPlan &BestPlan, 315 InnerLoopVectorizer &LB, DominatorTree *DT, 316 bool IsEpilogueVectorization); 317 318 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 319 void printPlans(raw_ostream &O); 320 #endif 321 322 /// Look through the existing plans and return true if we have one with all 323 /// the vectorization factors in question. 324 bool hasPlanWithVF(ElementCount VF) const { 325 return any_of(VPlans, 326 [&](const VPlanPtr &Plan) { return Plan->hasVF(VF); }); 327 } 328 329 /// Test a \p Predicate on a \p Range of VF's. Return the value of applying 330 /// \p Predicate on Range.Start, possibly decreasing Range.End such that the 331 /// returned value holds for the entire \p Range. 332 static bool 333 getDecisionAndClampRange(const std::function<bool(ElementCount)> &Predicate, 334 VFRange &Range); 335 336 /// Check if the number of runtime checks exceeds the threshold. 337 bool requiresTooManyRuntimeChecks() const; 338 339 protected: 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