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