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