1 //===- llvm/Analysis/IVDescriptors.h - IndVar Descriptors -------*- C++ -*-===// 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 // This file "describes" induction and recurrence variables. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_ANALYSIS_IVDESCRIPTORS_H 14 #define LLVM_ANALYSIS_IVDESCRIPTORS_H 15 16 #include "llvm/ADT/DenseMap.h" 17 #include "llvm/ADT/SmallPtrSet.h" 18 #include "llvm/ADT/SmallVector.h" 19 #include "llvm/ADT/StringRef.h" 20 #include "llvm/IR/InstrTypes.h" 21 #include "llvm/IR/Instruction.h" 22 #include "llvm/IR/Operator.h" 23 #include "llvm/IR/ValueHandle.h" 24 #include "llvm/Support/Casting.h" 25 26 namespace llvm { 27 28 class DemandedBits; 29 class AssumptionCache; 30 class Loop; 31 class PredicatedScalarEvolution; 32 class ScalarEvolution; 33 class SCEV; 34 class DominatorTree; 35 class ICFLoopSafetyInfo; 36 37 /// The RecurrenceDescriptor is used to identify recurrences variables in a 38 /// loop. Reduction is a special case of recurrence that has uses of the 39 /// recurrence variable outside the loop. The method isReductionPHI identifies 40 /// reductions that are basic recurrences. 41 /// 42 /// Basic recurrences are defined as the summation, product, OR, AND, XOR, min, 43 /// or max of a set of terms. For example: for(i=0; i<n; i++) { total += 44 /// array[i]; } is a summation of array elements. Basic recurrences are a 45 /// special case of chains of recurrences (CR). See ScalarEvolution for CR 46 /// references. 47 48 /// This struct holds information about recurrence variables. 49 class RecurrenceDescriptor { 50 public: 51 /// This enum represents the kinds of recurrences that we support. 52 enum RecurrenceKind { 53 RK_NoRecurrence, ///< Not a recurrence. 54 RK_IntegerAdd, ///< Sum of integers. 55 RK_IntegerMult, ///< Product of integers. 56 RK_IntegerOr, ///< Bitwise or logical OR of numbers. 57 RK_IntegerAnd, ///< Bitwise or logical AND of numbers. 58 RK_IntegerXor, ///< Bitwise or logical XOR of numbers. 59 RK_IntegerMinMax, ///< Min/max implemented in terms of select(cmp()). 60 RK_FloatAdd, ///< Sum of floats. 61 RK_FloatMult, ///< Product of floats. 62 RK_FloatMinMax ///< Min/max implemented in terms of select(cmp()). 63 }; 64 65 // This enum represents the kind of minmax recurrence. 66 enum MinMaxRecurrenceKind { 67 MRK_Invalid, 68 MRK_UIntMin, 69 MRK_UIntMax, 70 MRK_SIntMin, 71 MRK_SIntMax, 72 MRK_FloatMin, 73 MRK_FloatMax 74 }; 75 76 RecurrenceDescriptor() = default; 77 RecurrenceDescriptor(Value * Start,Instruction * Exit,RecurrenceKind K,FastMathFlags FMF,MinMaxRecurrenceKind MK,Instruction * UAI,Type * RT,bool Signed,SmallPtrSetImpl<Instruction * > & CI)78 RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K, 79 FastMathFlags FMF, MinMaxRecurrenceKind MK, 80 Instruction *UAI, Type *RT, bool Signed, 81 SmallPtrSetImpl<Instruction *> &CI) 82 : StartValue(Start), LoopExitInstr(Exit), Kind(K), FMF(FMF), 83 MinMaxKind(MK), UnsafeAlgebraInst(UAI), RecurrenceType(RT), 84 IsSigned(Signed) { 85 CastInsts.insert(CI.begin(), CI.end()); 86 } 87 88 /// This POD struct holds information about a potential recurrence operation. 89 class InstDesc { 90 public: 91 InstDesc(bool IsRecur, Instruction *I, Instruction *UAI = nullptr) IsRecurrence(IsRecur)92 : IsRecurrence(IsRecur), PatternLastInst(I), MinMaxKind(MRK_Invalid), 93 UnsafeAlgebraInst(UAI) {} 94 95 InstDesc(Instruction *I, MinMaxRecurrenceKind K, Instruction *UAI = nullptr) IsRecurrence(true)96 : IsRecurrence(true), PatternLastInst(I), MinMaxKind(K), 97 UnsafeAlgebraInst(UAI) {} 98 isRecurrence()99 bool isRecurrence() { return IsRecurrence; } 100 hasUnsafeAlgebra()101 bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; } 102 getUnsafeAlgebraInst()103 Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; } 104 getMinMaxKind()105 MinMaxRecurrenceKind getMinMaxKind() { return MinMaxKind; } 106 getPatternInst()107 Instruction *getPatternInst() { return PatternLastInst; } 108 109 private: 110 // Is this instruction a recurrence candidate. 111 bool IsRecurrence; 112 // The last instruction in a min/max pattern (select of the select(icmp()) 113 // pattern), or the current recurrence instruction otherwise. 114 Instruction *PatternLastInst; 115 // If this is a min/max pattern the comparison predicate. 116 MinMaxRecurrenceKind MinMaxKind; 117 // Recurrence has unsafe algebra. 118 Instruction *UnsafeAlgebraInst; 119 }; 120 121 /// Returns a struct describing if the instruction 'I' can be a recurrence 122 /// variable of type 'Kind'. If the recurrence is a min/max pattern of 123 /// select(icmp()) this function advances the instruction pointer 'I' from the 124 /// compare instruction to the select instruction and stores this pointer in 125 /// 'PatternLastInst' member of the returned struct. 126 static InstDesc isRecurrenceInstr(Instruction *I, RecurrenceKind Kind, 127 InstDesc &Prev, bool HasFunNoNaNAttr); 128 129 /// Returns true if instruction I has multiple uses in Insts 130 static bool hasMultipleUsesOf(Instruction *I, 131 SmallPtrSetImpl<Instruction *> &Insts, 132 unsigned MaxNumUses); 133 134 /// Returns true if all uses of the instruction I is within the Set. 135 static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set); 136 137 /// Returns a struct describing if the instruction if the instruction is a 138 /// Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y) 139 /// or max(X, Y). 140 static InstDesc isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev); 141 142 /// Returns a struct describing if the instruction is a 143 /// Select(FCmp(X, Y), (Z = X op PHINode), PHINode) instruction pattern. 144 static InstDesc isConditionalRdxPattern(RecurrenceKind Kind, Instruction *I); 145 146 /// Returns identity corresponding to the RecurrenceKind. 147 static Constant *getRecurrenceIdentity(RecurrenceKind K, Type *Tp); 148 149 /// Returns the opcode of binary operation corresponding to the 150 /// RecurrenceKind. 151 static unsigned getRecurrenceBinOp(RecurrenceKind Kind); 152 153 /// Returns true if Phi is a reduction of type Kind and adds it to the 154 /// RecurrenceDescriptor. If either \p DB is non-null or \p AC and \p DT are 155 /// non-null, the minimal bit width needed to compute the reduction will be 156 /// computed. 157 static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop, 158 bool HasFunNoNaNAttr, 159 RecurrenceDescriptor &RedDes, 160 DemandedBits *DB = nullptr, 161 AssumptionCache *AC = nullptr, 162 DominatorTree *DT = nullptr); 163 164 /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor 165 /// is returned in RedDes. If either \p DB is non-null or \p AC and \p DT are 166 /// non-null, the minimal bit width needed to compute the reduction will be 167 /// computed. 168 static bool isReductionPHI(PHINode *Phi, Loop *TheLoop, 169 RecurrenceDescriptor &RedDes, 170 DemandedBits *DB = nullptr, 171 AssumptionCache *AC = nullptr, 172 DominatorTree *DT = nullptr); 173 174 /// Returns true if Phi is a first-order recurrence. A first-order recurrence 175 /// is a non-reduction recurrence relation in which the value of the 176 /// recurrence in the current loop iteration equals a value defined in the 177 /// previous iteration. \p SinkAfter includes pairs of instructions where the 178 /// first will be rescheduled to appear after the second if/when the loop is 179 /// vectorized. It may be augmented with additional pairs if needed in order 180 /// to handle Phi as a first-order recurrence. 181 static bool 182 isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop, 183 DenseMap<Instruction *, Instruction *> &SinkAfter, 184 DominatorTree *DT); 185 getRecurrenceKind()186 RecurrenceKind getRecurrenceKind() { return Kind; } 187 getMinMaxRecurrenceKind()188 MinMaxRecurrenceKind getMinMaxRecurrenceKind() { return MinMaxKind; } 189 getFastMathFlags()190 FastMathFlags getFastMathFlags() { return FMF; } 191 getRecurrenceStartValue()192 TrackingVH<Value> getRecurrenceStartValue() { return StartValue; } 193 getLoopExitInstr()194 Instruction *getLoopExitInstr() { return LoopExitInstr; } 195 196 /// Returns true if the recurrence has unsafe algebra which requires a relaxed 197 /// floating-point model. hasUnsafeAlgebra()198 bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; } 199 200 /// Returns first unsafe algebra instruction in the PHI node's use-chain. getUnsafeAlgebraInst()201 Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; } 202 203 /// Returns true if the recurrence kind is an integer kind. 204 static bool isIntegerRecurrenceKind(RecurrenceKind Kind); 205 206 /// Returns true if the recurrence kind is a floating point kind. 207 static bool isFloatingPointRecurrenceKind(RecurrenceKind Kind); 208 209 /// Returns true if the recurrence kind is an arithmetic kind. 210 static bool isArithmeticRecurrenceKind(RecurrenceKind Kind); 211 212 /// Returns the type of the recurrence. This type can be narrower than the 213 /// actual type of the Phi if the recurrence has been type-promoted. getRecurrenceType()214 Type *getRecurrenceType() { return RecurrenceType; } 215 216 /// Returns a reference to the instructions used for type-promoting the 217 /// recurrence. getCastInsts()218 SmallPtrSet<Instruction *, 8> &getCastInsts() { return CastInsts; } 219 220 /// Returns true if all source operands of the recurrence are SExtInsts. isSigned()221 bool isSigned() { return IsSigned; } 222 223 private: 224 // The starting value of the recurrence. 225 // It does not have to be zero! 226 TrackingVH<Value> StartValue; 227 // The instruction who's value is used outside the loop. 228 Instruction *LoopExitInstr = nullptr; 229 // The kind of the recurrence. 230 RecurrenceKind Kind = RK_NoRecurrence; 231 // The fast-math flags on the recurrent instructions. We propagate these 232 // fast-math flags into the vectorized FP instructions we generate. 233 FastMathFlags FMF; 234 // If this a min/max recurrence the kind of recurrence. 235 MinMaxRecurrenceKind MinMaxKind = MRK_Invalid; 236 // First occurrence of unasfe algebra in the PHI's use-chain. 237 Instruction *UnsafeAlgebraInst = nullptr; 238 // The type of the recurrence. 239 Type *RecurrenceType = nullptr; 240 // True if all source operands of the recurrence are SExtInsts. 241 bool IsSigned = false; 242 // Instructions used for type-promoting the recurrence. 243 SmallPtrSet<Instruction *, 8> CastInsts; 244 }; 245 246 /// A struct for saving information about induction variables. 247 class InductionDescriptor { 248 public: 249 /// This enum represents the kinds of inductions that we support. 250 enum InductionKind { 251 IK_NoInduction, ///< Not an induction variable. 252 IK_IntInduction, ///< Integer induction variable. Step = C. 253 IK_PtrInduction, ///< Pointer induction var. Step = C / sizeof(elem). 254 IK_FpInduction ///< Floating point induction variable. 255 }; 256 257 public: 258 /// Default constructor - creates an invalid induction. 259 InductionDescriptor() = default; 260 261 /// Get the consecutive direction. Returns: 262 /// 0 - unknown or non-consecutive. 263 /// 1 - consecutive and increasing. 264 /// -1 - consecutive and decreasing. 265 int getConsecutiveDirection() const; 266 getStartValue()267 Value *getStartValue() const { return StartValue; } getKind()268 InductionKind getKind() const { return IK; } getStep()269 const SCEV *getStep() const { return Step; } getInductionBinOp()270 BinaryOperator *getInductionBinOp() const { return InductionBinOp; } 271 ConstantInt *getConstIntStepValue() const; 272 273 /// Returns true if \p Phi is an induction in the loop \p L. If \p Phi is an 274 /// induction, the induction descriptor \p D will contain the data describing 275 /// this induction. If by some other means the caller has a better SCEV 276 /// expression for \p Phi than the one returned by the ScalarEvolution 277 /// analysis, it can be passed through \p Expr. If the def-use chain 278 /// associated with the phi includes casts (that we know we can ignore 279 /// under proper runtime checks), they are passed through \p CastsToIgnore. 280 static bool 281 isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, 282 InductionDescriptor &D, const SCEV *Expr = nullptr, 283 SmallVectorImpl<Instruction *> *CastsToIgnore = nullptr); 284 285 /// Returns true if \p Phi is a floating point induction in the loop \p L. 286 /// If \p Phi is an induction, the induction descriptor \p D will contain 287 /// the data describing this induction. 288 static bool isFPInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, 289 InductionDescriptor &D); 290 291 /// Returns true if \p Phi is a loop \p L induction, in the context associated 292 /// with the run-time predicate of PSE. If \p Assume is true, this can add 293 /// further SCEV predicates to \p PSE in order to prove that \p Phi is an 294 /// induction. 295 /// If \p Phi is an induction, \p D will contain the data describing this 296 /// induction. 297 static bool isInductionPHI(PHINode *Phi, const Loop *L, 298 PredicatedScalarEvolution &PSE, 299 InductionDescriptor &D, bool Assume = false); 300 301 /// Returns true if the induction type is FP and the binary operator does 302 /// not have the "fast-math" property. Such operation requires a relaxed FP 303 /// mode. hasUnsafeAlgebra()304 bool hasUnsafeAlgebra() { 305 return (IK == IK_FpInduction) && InductionBinOp && 306 !cast<FPMathOperator>(InductionBinOp)->isFast(); 307 } 308 309 /// Returns induction operator that does not have "fast-math" property 310 /// and requires FP unsafe mode. getUnsafeAlgebraInst()311 Instruction *getUnsafeAlgebraInst() { 312 if (IK != IK_FpInduction) 313 return nullptr; 314 315 if (!InductionBinOp || cast<FPMathOperator>(InductionBinOp)->isFast()) 316 return nullptr; 317 return InductionBinOp; 318 } 319 320 /// Returns binary opcode of the induction operator. getInductionOpcode()321 Instruction::BinaryOps getInductionOpcode() const { 322 return InductionBinOp ? InductionBinOp->getOpcode() 323 : Instruction::BinaryOpsEnd; 324 } 325 326 /// Returns a reference to the type cast instructions in the induction 327 /// update chain, that are redundant when guarded with a runtime 328 /// SCEV overflow check. getCastInsts()329 const SmallVectorImpl<Instruction *> &getCastInsts() const { 330 return RedundantCasts; 331 } 332 333 private: 334 /// Private constructor - used by \c isInductionPHI. 335 InductionDescriptor(Value *Start, InductionKind K, const SCEV *Step, 336 BinaryOperator *InductionBinOp = nullptr, 337 SmallVectorImpl<Instruction *> *Casts = nullptr); 338 339 /// Start value. 340 TrackingVH<Value> StartValue; 341 /// Induction kind. 342 InductionKind IK = IK_NoInduction; 343 /// Step value. 344 const SCEV *Step = nullptr; 345 // Instruction that advances induction variable. 346 BinaryOperator *InductionBinOp = nullptr; 347 // Instructions used for type-casts of the induction variable, 348 // that are redundant when guarded with a runtime SCEV overflow check. 349 SmallVector<Instruction *, 2> RedundantCasts; 350 }; 351 352 } // end namespace llvm 353 354 #endif // LLVM_ANALYSIS_IVDESCRIPTORS_H 355