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