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