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