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/MapVector.h" 17 #include "llvm/ADT/SmallPtrSet.h" 18 #include "llvm/ADT/SmallVector.h" 19 #include "llvm/IR/IntrinsicInst.h" 20 #include "llvm/IR/ValueHandle.h" 21 22 namespace llvm { 23 24 class AssumptionCache; 25 class DemandedBits; 26 class DominatorTree; 27 class Instruction; 28 class Loop; 29 class PredicatedScalarEvolution; 30 class ScalarEvolution; 31 class SCEV; 32 class StoreInst; 33 34 /// These are the kinds of recurrences that we support. 35 enum class RecurKind { 36 None, ///< Not a recurrence. 37 Add, ///< Sum of integers. 38 Mul, ///< Product of integers. 39 Or, ///< Bitwise or logical OR of integers. 40 And, ///< Bitwise or logical AND of integers. 41 Xor, ///< Bitwise or logical XOR of integers. 42 SMin, ///< Signed integer min implemented in terms of select(cmp()). 43 SMax, ///< Signed integer max implemented in terms of select(cmp()). 44 UMin, ///< Unisgned integer min implemented in terms of select(cmp()). 45 UMax, ///< Unsigned integer max implemented in terms of select(cmp()). 46 FAdd, ///< Sum of floats. 47 FMul, ///< Product of floats. 48 FMin, ///< FP min implemented in terms of select(cmp()). 49 FMax, ///< FP max implemented in terms of select(cmp()). 50 FMulAdd, ///< Fused multiply-add of floats (a * b + c). 51 SelectICmp, ///< Integer select(icmp(),x,y) where one of (x,y) is loop 52 ///< invariant 53 SelectFCmp ///< Integer select(fcmp(),x,y) where one of (x,y) is loop 54 ///< invariant 55 }; 56 57 /// The RecurrenceDescriptor is used to identify recurrences variables in a 58 /// loop. Reduction is a special case of recurrence that has uses of the 59 /// recurrence variable outside the loop. The method isReductionPHI identifies 60 /// reductions that are basic recurrences. 61 /// 62 /// Basic recurrences are defined as the summation, product, OR, AND, XOR, min, 63 /// or max of a set of terms. For example: for(i=0; i<n; i++) { total += 64 /// array[i]; } is a summation of array elements. Basic recurrences are a 65 /// special case of chains of recurrences (CR). See ScalarEvolution for CR 66 /// references. 67 68 /// This struct holds information about recurrence variables. 69 class RecurrenceDescriptor { 70 public: 71 RecurrenceDescriptor() = default; 72 73 RecurrenceDescriptor(Value *Start, Instruction *Exit, StoreInst *Store, 74 RecurKind K, FastMathFlags FMF, Instruction *ExactFP, 75 Type *RT, bool Signed, bool Ordered, 76 SmallPtrSetImpl<Instruction *> &CI, 77 unsigned MinWidthCastToRecurTy) 78 : IntermediateStore(Store), StartValue(Start), LoopExitInstr(Exit), 79 Kind(K), FMF(FMF), ExactFPMathInst(ExactFP), RecurrenceType(RT), 80 IsSigned(Signed), IsOrdered(Ordered), 81 MinWidthCastToRecurrenceType(MinWidthCastToRecurTy) { 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) 89 : IsRecurrence(IsRecur), PatternLastInst(I), 90 RecKind(RecurKind::None), ExactFPMathInst(ExactFP) {} 91 92 InstDesc(Instruction *I, RecurKind K, Instruction *ExactFP = nullptr) 93 : IsRecurrence(true), PatternLastInst(I), RecKind(K), 94 ExactFPMathInst(ExactFP) {} 95 96 bool isRecurrence() const { return IsRecurrence; } 97 98 bool needsExactFPMath() const { return ExactFPMathInst != nullptr; } 99 100 Instruction *getExactFPMathInst() const { return ExactFPMathInst; } 101 102 RecurKind getRecKind() const { return RecKind; } 103 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) const; 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 168 AddReductionVar(PHINode *Phi, RecurKind Kind, Loop *TheLoop, 169 FastMathFlags FuncFMF, RecurrenceDescriptor &RedDes, 170 DemandedBits *DB = nullptr, AssumptionCache *AC = nullptr, 171 DominatorTree *DT = nullptr, ScalarEvolution *SE = nullptr); 172 173 /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor 174 /// is returned in RedDes. If either \p DB is non-null or \p AC and \p DT are 175 /// non-null, the minimal bit width needed to compute the reduction will be 176 /// computed. If \p SE is non-null, store instructions to loop invariant 177 /// addresses are processed. 178 static bool 179 isReductionPHI(PHINode *Phi, Loop *TheLoop, RecurrenceDescriptor &RedDes, 180 DemandedBits *DB = nullptr, AssumptionCache *AC = nullptr, 181 DominatorTree *DT = nullptr, ScalarEvolution *SE = nullptr); 182 183 /// Returns true if Phi is a first-order recurrence. A first-order recurrence 184 /// is a non-reduction recurrence relation in which the value of the 185 /// recurrence in the current loop iteration equals a value defined in the 186 /// previous iteration. \p SinkAfter includes pairs of instructions where the 187 /// first will be rescheduled to appear after the second if/when the loop is 188 /// vectorized. It may be augmented with additional pairs if needed in order 189 /// to handle Phi as a first-order recurrence. 190 static bool 191 isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop, 192 MapVector<Instruction *, Instruction *> &SinkAfter, 193 DominatorTree *DT); 194 195 RecurKind getRecurrenceKind() const { return Kind; } 196 197 unsigned getOpcode() const { return getOpcode(getRecurrenceKind()); } 198 199 FastMathFlags getFastMathFlags() const { return FMF; } 200 201 TrackingVH<Value> getRecurrenceStartValue() const { return StartValue; } 202 203 Instruction *getLoopExitInstr() const { return LoopExitInstr; } 204 205 /// Returns true if the recurrence has floating-point math that requires 206 /// precise (ordered) operations. 207 bool hasExactFPMath() const { return ExactFPMathInst != nullptr; } 208 209 /// Returns 1st non-reassociative FP instruction in the PHI node's use-chain. 210 Instruction *getExactFPMathInst() const { return ExactFPMathInst; } 211 212 /// Returns true if the recurrence kind is an integer kind. 213 static bool isIntegerRecurrenceKind(RecurKind Kind); 214 215 /// Returns true if the recurrence kind is a floating point kind. 216 static bool isFloatingPointRecurrenceKind(RecurKind Kind); 217 218 /// Returns true if the recurrence kind is an integer min/max kind. 219 static bool isIntMinMaxRecurrenceKind(RecurKind Kind) { 220 return Kind == RecurKind::UMin || Kind == RecurKind::UMax || 221 Kind == RecurKind::SMin || Kind == RecurKind::SMax; 222 } 223 224 /// Returns true if the recurrence kind is a floating-point min/max kind. 225 static bool isFPMinMaxRecurrenceKind(RecurKind Kind) { 226 return Kind == RecurKind::FMin || Kind == RecurKind::FMax; 227 } 228 229 /// Returns true if the recurrence kind is any min/max kind. 230 static bool isMinMaxRecurrenceKind(RecurKind Kind) { 231 return isIntMinMaxRecurrenceKind(Kind) || isFPMinMaxRecurrenceKind(Kind); 232 } 233 234 /// Returns true if the recurrence kind is of the form 235 /// select(cmp(),x,y) where one of (x,y) is loop invariant. 236 static bool isSelectCmpRecurrenceKind(RecurKind Kind) { 237 return Kind == RecurKind::SelectICmp || Kind == RecurKind::SelectFCmp; 238 } 239 240 /// Returns the type of the recurrence. This type can be narrower than the 241 /// actual type of the Phi if the recurrence has been type-promoted. 242 Type *getRecurrenceType() const { return RecurrenceType; } 243 244 /// Returns a reference to the instructions used for type-promoting the 245 /// recurrence. 246 const SmallPtrSet<Instruction *, 8> &getCastInsts() const { return CastInsts; } 247 248 /// Returns the minimum width used by the recurrence in bits. 249 unsigned getMinWidthCastToRecurrenceTypeInBits() const { 250 return MinWidthCastToRecurrenceType; 251 } 252 253 /// Returns true if all source operands of the recurrence are SExtInsts. 254 bool isSigned() const { return IsSigned; } 255 256 /// Expose an ordered FP reduction to the instance users. 257 bool isOrdered() const { return IsOrdered; } 258 259 /// Attempts to find a chain of operations from Phi to LoopExitInst that can 260 /// be treated as a set of reductions instructions for in-loop reductions. 261 SmallVector<Instruction *, 4> getReductionOpChain(PHINode *Phi, 262 Loop *L) const; 263 264 /// Returns true if the instruction is a call to the llvm.fmuladd intrinsic. 265 static bool isFMulAddIntrinsic(Instruction *I) { 266 return isa<IntrinsicInst>(I) && 267 cast<IntrinsicInst>(I)->getIntrinsicID() == Intrinsic::fmuladd; 268 } 269 270 /// Reductions may store temporary or final result to an invariant address. 271 /// If there is such a store in the loop then, after successfull run of 272 /// AddReductionVar method, this field will be assigned the last met store. 273 StoreInst *IntermediateStore = nullptr; 274 275 private: 276 // The starting value of the recurrence. 277 // It does not have to be zero! 278 TrackingVH<Value> StartValue; 279 // The instruction who's value is used outside the loop. 280 Instruction *LoopExitInstr = nullptr; 281 // The kind of the recurrence. 282 RecurKind Kind = RecurKind::None; 283 // The fast-math flags on the recurrent instructions. We propagate these 284 // fast-math flags into the vectorized FP instructions we generate. 285 FastMathFlags FMF; 286 // First instance of non-reassociative floating-point in the PHI's use-chain. 287 Instruction *ExactFPMathInst = nullptr; 288 // The type of the recurrence. 289 Type *RecurrenceType = nullptr; 290 // True if all source operands of the recurrence are SExtInsts. 291 bool IsSigned = false; 292 // True if this recurrence can be treated as an in-order reduction. 293 // Currently only a non-reassociative FAdd can be considered in-order, 294 // if it is also the only FAdd in the PHI's use chain. 295 bool IsOrdered = false; 296 // Instructions used for type-promoting the recurrence. 297 SmallPtrSet<Instruction *, 8> CastInsts; 298 // The minimum width used by the recurrence. 299 unsigned MinWidthCastToRecurrenceType; 300 }; 301 302 /// A struct for saving information about induction variables. 303 class InductionDescriptor { 304 public: 305 /// This enum represents the kinds of inductions that we support. 306 enum InductionKind { 307 IK_NoInduction, ///< Not an induction variable. 308 IK_IntInduction, ///< Integer induction variable. Step = C. 309 IK_PtrInduction, ///< Pointer induction var. Step = C / sizeof(elem). 310 IK_FpInduction ///< Floating point induction variable. 311 }; 312 313 public: 314 /// Default constructor - creates an invalid induction. 315 InductionDescriptor() = default; 316 317 Value *getStartValue() const { return StartValue; } 318 InductionKind getKind() const { return IK; } 319 const SCEV *getStep() const { return Step; } 320 BinaryOperator *getInductionBinOp() const { return InductionBinOp; } 321 ConstantInt *getConstIntStepValue() const; 322 323 /// Returns true if \p Phi is an induction in the loop \p L. If \p Phi is an 324 /// induction, the induction descriptor \p D will contain the data describing 325 /// this induction. If by some other means the caller has a better SCEV 326 /// expression for \p Phi than the one returned by the ScalarEvolution 327 /// analysis, it can be passed through \p Expr. If the def-use chain 328 /// associated with the phi includes casts (that we know we can ignore 329 /// under proper runtime checks), they are passed through \p CastsToIgnore. 330 static bool 331 isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, 332 InductionDescriptor &D, const SCEV *Expr = nullptr, 333 SmallVectorImpl<Instruction *> *CastsToIgnore = nullptr); 334 335 /// Returns true if \p Phi is a floating point induction in the loop \p L. 336 /// If \p Phi is an induction, the induction descriptor \p D will contain 337 /// the data describing this induction. 338 static bool isFPInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, 339 InductionDescriptor &D); 340 341 /// Returns true if \p Phi is a loop \p L induction, in the context associated 342 /// with the run-time predicate of PSE. If \p Assume is true, this can add 343 /// further SCEV predicates to \p PSE in order to prove that \p Phi is an 344 /// induction. 345 /// If \p Phi is an induction, \p D will contain the data describing this 346 /// induction. 347 static bool isInductionPHI(PHINode *Phi, const Loop *L, 348 PredicatedScalarEvolution &PSE, 349 InductionDescriptor &D, bool Assume = false); 350 351 /// Returns floating-point induction operator that does not allow 352 /// reassociation (transforming the induction requires an override of normal 353 /// floating-point rules). 354 Instruction *getExactFPMathInst() { 355 if (IK == IK_FpInduction && InductionBinOp && 356 !InductionBinOp->hasAllowReassoc()) 357 return InductionBinOp; 358 return nullptr; 359 } 360 361 /// Returns binary opcode of the induction operator. 362 Instruction::BinaryOps getInductionOpcode() const { 363 return InductionBinOp ? InductionBinOp->getOpcode() 364 : Instruction::BinaryOpsEnd; 365 } 366 367 Type *getElementType() const { 368 assert(IK == IK_PtrInduction && "Only pointer induction has element type"); 369 return ElementType; 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 Type *ElementType = nullptr, 384 SmallVectorImpl<Instruction *> *Casts = nullptr); 385 386 /// Start value. 387 TrackingVH<Value> StartValue; 388 /// Induction kind. 389 InductionKind IK = IK_NoInduction; 390 /// Step value. 391 const SCEV *Step = nullptr; 392 // Instruction that advances induction variable. 393 BinaryOperator *InductionBinOp = nullptr; 394 // Element type for pointer induction variables. 395 // TODO: This can be dropped once support for typed pointers is removed. 396 Type *ElementType = nullptr; 397 // Instructions used for type-casts of the induction variable, 398 // that are redundant when guarded with a runtime SCEV overflow check. 399 SmallVector<Instruction *, 2> RedundantCasts; 400 }; 401 402 } // end namespace llvm 403 404 #endif // LLVM_ANALYSIS_IVDESCRIPTORS_H 405