1 //===- llvm/Transforms/Utils/LoopUtils.h - Loop utilities -*- C++ -*-=========// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file defines some loop transformation utilities. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_TRANSFORMS_UTILS_LOOPUTILS_H 15 #define LLVM_TRANSFORMS_UTILS_LOOPUTILS_H 16 17 #include "llvm/ADT/SmallVector.h" 18 #include "llvm/Analysis/AliasAnalysis.h" 19 #include "llvm/Analysis/EHPersonalities.h" 20 #include "llvm/IR/Dominators.h" 21 #include "llvm/IR/IRBuilder.h" 22 23 namespace llvm { 24 class AliasSet; 25 class AliasSetTracker; 26 class AssumptionCache; 27 class BasicBlock; 28 class DataLayout; 29 class DominatorTree; 30 class Loop; 31 class LoopInfo; 32 class Pass; 33 class PredicatedScalarEvolution; 34 class PredIteratorCache; 35 class ScalarEvolution; 36 class SCEV; 37 class TargetLibraryInfo; 38 39 /// \brief Captures loop safety information. 40 /// It keep information for loop & its header may throw exception. 41 struct LoopSafetyInfo { 42 bool MayThrow; // The current loop contains an instruction which 43 // may throw. 44 bool HeaderMayThrow; // Same as previous, but specific to loop header 45 // Used to update funclet bundle operands. 46 DenseMap<BasicBlock *, ColorVector> BlockColors; 47 LoopSafetyInfo() : MayThrow(false), HeaderMayThrow(false) {} 48 }; 49 50 /// The RecurrenceDescriptor is used to identify recurrences variables in a 51 /// loop. Reduction is a special case of recurrence that has uses of the 52 /// recurrence variable outside the loop. The method isReductionPHI identifies 53 /// reductions that are basic recurrences. 54 /// 55 /// Basic recurrences are defined as the summation, product, OR, AND, XOR, min, 56 /// or max of a set of terms. For example: for(i=0; i<n; i++) { total += 57 /// array[i]; } is a summation of array elements. Basic recurrences are a 58 /// special case of chains of recurrences (CR). See ScalarEvolution for CR 59 /// references. 60 61 /// This struct holds information about recurrence variables. 62 class RecurrenceDescriptor { 63 64 public: 65 /// This enum represents the kinds of recurrences that we support. 66 enum RecurrenceKind { 67 RK_NoRecurrence, ///< Not a recurrence. 68 RK_IntegerAdd, ///< Sum of integers. 69 RK_IntegerMult, ///< Product of integers. 70 RK_IntegerOr, ///< Bitwise or logical OR of numbers. 71 RK_IntegerAnd, ///< Bitwise or logical AND of numbers. 72 RK_IntegerXor, ///< Bitwise or logical XOR of numbers. 73 RK_IntegerMinMax, ///< Min/max implemented in terms of select(cmp()). 74 RK_FloatAdd, ///< Sum of floats. 75 RK_FloatMult, ///< Product of floats. 76 RK_FloatMinMax ///< Min/max implemented in terms of select(cmp()). 77 }; 78 79 // This enum represents the kind of minmax recurrence. 80 enum MinMaxRecurrenceKind { 81 MRK_Invalid, 82 MRK_UIntMin, 83 MRK_UIntMax, 84 MRK_SIntMin, 85 MRK_SIntMax, 86 MRK_FloatMin, 87 MRK_FloatMax 88 }; 89 90 RecurrenceDescriptor() 91 : StartValue(nullptr), LoopExitInstr(nullptr), Kind(RK_NoRecurrence), 92 MinMaxKind(MRK_Invalid), UnsafeAlgebraInst(nullptr), 93 RecurrenceType(nullptr), IsSigned(false) {} 94 95 RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K, 96 MinMaxRecurrenceKind MK, Instruction *UAI, Type *RT, 97 bool Signed, SmallPtrSetImpl<Instruction *> &CI) 98 : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK), 99 UnsafeAlgebraInst(UAI), RecurrenceType(RT), IsSigned(Signed) { 100 CastInsts.insert(CI.begin(), CI.end()); 101 } 102 103 /// This POD struct holds information about a potential recurrence operation. 104 class InstDesc { 105 106 public: 107 InstDesc(bool IsRecur, Instruction *I, Instruction *UAI = nullptr) 108 : IsRecurrence(IsRecur), PatternLastInst(I), MinMaxKind(MRK_Invalid), 109 UnsafeAlgebraInst(UAI) {} 110 111 InstDesc(Instruction *I, MinMaxRecurrenceKind K, Instruction *UAI = nullptr) 112 : IsRecurrence(true), PatternLastInst(I), MinMaxKind(K), 113 UnsafeAlgebraInst(UAI) {} 114 115 bool isRecurrence() { return IsRecurrence; } 116 117 bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; } 118 119 Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; } 120 121 MinMaxRecurrenceKind getMinMaxKind() { return MinMaxKind; } 122 123 Instruction *getPatternInst() { return PatternLastInst; } 124 125 private: 126 // Is this instruction a recurrence candidate. 127 bool IsRecurrence; 128 // The last instruction in a min/max pattern (select of the select(icmp()) 129 // pattern), or the current recurrence instruction otherwise. 130 Instruction *PatternLastInst; 131 // If this is a min/max pattern the comparison predicate. 132 MinMaxRecurrenceKind MinMaxKind; 133 // Recurrence has unsafe algebra. 134 Instruction *UnsafeAlgebraInst; 135 }; 136 137 /// Returns a struct describing if the instruction 'I' can be a recurrence 138 /// variable of type 'Kind'. If the recurrence is a min/max pattern of 139 /// select(icmp()) this function advances the instruction pointer 'I' from the 140 /// compare instruction to the select instruction and stores this pointer in 141 /// 'PatternLastInst' member of the returned struct. 142 static InstDesc isRecurrenceInstr(Instruction *I, RecurrenceKind Kind, 143 InstDesc &Prev, bool HasFunNoNaNAttr); 144 145 /// Returns true if instruction I has multiple uses in Insts 146 static bool hasMultipleUsesOf(Instruction *I, 147 SmallPtrSetImpl<Instruction *> &Insts); 148 149 /// Returns true if all uses of the instruction I is within the Set. 150 static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set); 151 152 /// Returns a struct describing if the instruction if the instruction is a 153 /// Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y) 154 /// or max(X, Y). 155 static InstDesc isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev); 156 157 /// Returns identity corresponding to the RecurrenceKind. 158 static Constant *getRecurrenceIdentity(RecurrenceKind K, Type *Tp); 159 160 /// Returns the opcode of binary operation corresponding to the 161 /// RecurrenceKind. 162 static unsigned getRecurrenceBinOp(RecurrenceKind Kind); 163 164 /// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind. 165 static Value *createMinMaxOp(IRBuilder<> &Builder, MinMaxRecurrenceKind RK, 166 Value *Left, Value *Right); 167 168 /// Returns true if Phi is a reduction of type Kind and adds it to the 169 /// RecurrenceDescriptor. 170 static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop, 171 bool HasFunNoNaNAttr, 172 RecurrenceDescriptor &RedDes); 173 174 /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor is 175 /// returned in RedDes. 176 static bool isReductionPHI(PHINode *Phi, Loop *TheLoop, 177 RecurrenceDescriptor &RedDes); 178 179 /// Returns true if Phi is a first-order recurrence. A first-order recurrence 180 /// is a non-reduction recurrence relation in which the value of the 181 /// recurrence in the current loop iteration equals a value defined in the 182 /// previous iteration. 183 static bool isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop, 184 DominatorTree *DT); 185 186 RecurrenceKind getRecurrenceKind() { return Kind; } 187 188 MinMaxRecurrenceKind getMinMaxRecurrenceKind() { return MinMaxKind; } 189 190 TrackingVH<Value> getRecurrenceStartValue() { return StartValue; } 191 192 Instruction *getLoopExitInstr() { return LoopExitInstr; } 193 194 /// Returns true if the recurrence has unsafe algebra which requires a relaxed 195 /// floating-point model. 196 bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; } 197 198 /// Returns first unsafe algebra instruction in the PHI node's use-chain. 199 Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; } 200 201 /// Returns true if the recurrence kind is an integer kind. 202 static bool isIntegerRecurrenceKind(RecurrenceKind Kind); 203 204 /// Returns true if the recurrence kind is a floating point kind. 205 static bool isFloatingPointRecurrenceKind(RecurrenceKind Kind); 206 207 /// Returns true if the recurrence kind is an arithmetic kind. 208 static bool isArithmeticRecurrenceKind(RecurrenceKind Kind); 209 210 /// Determines if Phi may have been type-promoted. If Phi has a single user 211 /// that ANDs the Phi with a type mask, return the user. RT is updated to 212 /// account for the narrower bit width represented by the mask, and the AND 213 /// instruction is added to CI. 214 static Instruction *lookThroughAnd(PHINode *Phi, Type *&RT, 215 SmallPtrSetImpl<Instruction *> &Visited, 216 SmallPtrSetImpl<Instruction *> &CI); 217 218 /// Returns true if all the source operands of a recurrence are either 219 /// SExtInsts or ZExtInsts. This function is intended to be used with 220 /// lookThroughAnd to determine if the recurrence has been type-promoted. The 221 /// source operands are added to CI, and IsSigned is updated to indicate if 222 /// all source operands are SExtInsts. 223 static bool getSourceExtensionKind(Instruction *Start, Instruction *Exit, 224 Type *RT, bool &IsSigned, 225 SmallPtrSetImpl<Instruction *> &Visited, 226 SmallPtrSetImpl<Instruction *> &CI); 227 228 /// Returns the type of the recurrence. This type can be narrower than the 229 /// actual type of the Phi if the recurrence has been type-promoted. 230 Type *getRecurrenceType() { return RecurrenceType; } 231 232 /// Returns a reference to the instructions used for type-promoting the 233 /// recurrence. 234 SmallPtrSet<Instruction *, 8> &getCastInsts() { return CastInsts; } 235 236 /// Returns true if all source operands of the recurrence are SExtInsts. 237 bool isSigned() { return IsSigned; } 238 239 private: 240 // The starting value of the recurrence. 241 // It does not have to be zero! 242 TrackingVH<Value> StartValue; 243 // The instruction who's value is used outside the loop. 244 Instruction *LoopExitInstr; 245 // The kind of the recurrence. 246 RecurrenceKind Kind; 247 // If this a min/max recurrence the kind of recurrence. 248 MinMaxRecurrenceKind MinMaxKind; 249 // First occurance of unasfe algebra in the PHI's use-chain. 250 Instruction *UnsafeAlgebraInst; 251 // The type of the recurrence. 252 Type *RecurrenceType; 253 // True if all source operands of the recurrence are SExtInsts. 254 bool IsSigned; 255 // Instructions used for type-promoting the recurrence. 256 SmallPtrSet<Instruction *, 8> CastInsts; 257 }; 258 259 /// A struct for saving information about induction variables. 260 class InductionDescriptor { 261 public: 262 /// This enum represents the kinds of inductions that we support. 263 enum InductionKind { 264 IK_NoInduction, ///< Not an induction variable. 265 IK_IntInduction, ///< Integer induction variable. Step = C. 266 IK_PtrInduction ///< Pointer induction var. Step = C / sizeof(elem). 267 }; 268 269 public: 270 /// Default constructor - creates an invalid induction. 271 InductionDescriptor() 272 : StartValue(nullptr), IK(IK_NoInduction), Step(nullptr) {} 273 274 /// Get the consecutive direction. Returns: 275 /// 0 - unknown or non-consecutive. 276 /// 1 - consecutive and increasing. 277 /// -1 - consecutive and decreasing. 278 int getConsecutiveDirection() const; 279 280 /// Compute the transformed value of Index at offset StartValue using step 281 /// StepValue. 282 /// For integer induction, returns StartValue + Index * StepValue. 283 /// For pointer induction, returns StartValue[Index * StepValue]. 284 /// FIXME: The newly created binary instructions should contain nsw/nuw 285 /// flags, which can be found from the original scalar operations. 286 Value *transform(IRBuilder<> &B, Value *Index, ScalarEvolution *SE, 287 const DataLayout& DL) const; 288 289 Value *getStartValue() const { return StartValue; } 290 InductionKind getKind() const { return IK; } 291 const SCEV *getStep() const { return Step; } 292 ConstantInt *getConstIntStepValue() const; 293 294 /// Returns true if \p Phi is an induction. If \p Phi is an induction, 295 /// the induction descriptor \p D will contain the data describing this 296 /// induction. If by some other means the caller has a better SCEV 297 /// expression for \p Phi than the one returned by the ScalarEvolution 298 /// analysis, it can be passed through \p Expr. 299 static bool isInductionPHI(PHINode *Phi, ScalarEvolution *SE, 300 InductionDescriptor &D, 301 const SCEV *Expr = nullptr); 302 303 /// Returns true if \p Phi is an induction, in the context associated with 304 /// the run-time predicate of PSE. If \p Assume is true, this can add further 305 /// SCEV predicates to \p PSE in order to prove that \p Phi is an induction. 306 /// If \p Phi is an induction, \p D will contain the data describing this 307 /// induction. 308 static bool isInductionPHI(PHINode *Phi, PredicatedScalarEvolution &PSE, 309 InductionDescriptor &D, bool Assume = false); 310 311 private: 312 /// Private constructor - used by \c isInductionPHI. 313 InductionDescriptor(Value *Start, InductionKind K, const SCEV *Step); 314 315 /// Start value. 316 TrackingVH<Value> StartValue; 317 /// Induction kind. 318 InductionKind IK; 319 /// Step value. 320 const SCEV *Step; 321 }; 322 323 BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, 324 bool PreserveLCSSA); 325 326 /// \brief Put loop into LCSSA form. 327 /// 328 /// Looks at all instructions in the loop which have uses outside of the 329 /// current loop. For each, an LCSSA PHI node is inserted and the uses outside 330 /// the loop are rewritten to use this node. 331 /// 332 /// LoopInfo and DominatorTree are required and preserved. 333 /// 334 /// If ScalarEvolution is passed in, it will be preserved. 335 /// 336 /// Returns true if any modifications are made to the loop. 337 bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE); 338 339 /// \brief Put a loop nest into LCSSA form. 340 /// 341 /// This recursively forms LCSSA for a loop nest. 342 /// 343 /// LoopInfo and DominatorTree are required and preserved. 344 /// 345 /// If ScalarEvolution is passed in, it will be preserved. 346 /// 347 /// Returns true if any modifications are made to the loop. 348 bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, 349 ScalarEvolution *SE); 350 351 /// \brief Walk the specified region of the CFG (defined by all blocks 352 /// dominated by the specified block, and that are in the current loop) in 353 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit 354 /// uses before definitions, allowing us to sink a loop body in one pass without 355 /// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, 356 /// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all 357 /// instructions of the loop and loop safety information as arguments. 358 /// It returns changed status. 359 bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, 360 TargetLibraryInfo *, Loop *, AliasSetTracker *, 361 LoopSafetyInfo *); 362 363 /// \brief Walk the specified region of the CFG (defined by all blocks 364 /// dominated by the specified block, and that are in the current loop) in depth 365 /// first order w.r.t the DominatorTree. This allows us to visit definitions 366 /// before uses, allowing us to hoist a loop body in one pass without iteration. 367 /// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout, 368 /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the 369 /// loop and loop safety information as arguments. It returns changed status. 370 bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, 371 TargetLibraryInfo *, Loop *, AliasSetTracker *, 372 LoopSafetyInfo *); 373 374 /// \brief Try to promote memory values to scalars by sinking stores out of 375 /// the loop and moving loads to before the loop. We do this by looping over 376 /// the stores in the loop, looking for stores to Must pointers which are 377 /// loop invariant. It takes AliasSet, Loop exit blocks vector, loop exit blocks 378 /// insertion point vector, PredIteratorCache, LoopInfo, DominatorTree, Loop, 379 /// AliasSet information for all instructions of the loop and loop safety 380 /// information as arguments. It returns changed status. 381 bool promoteLoopAccessesToScalars(AliasSet &, SmallVectorImpl<BasicBlock *> &, 382 SmallVectorImpl<Instruction *> &, 383 PredIteratorCache &, LoopInfo *, 384 DominatorTree *, const TargetLibraryInfo *, 385 Loop *, AliasSetTracker *, LoopSafetyInfo *); 386 387 /// \brief Computes safety information for a loop 388 /// checks loop body & header for the possibility of may throw 389 /// exception, it takes LoopSafetyInfo and loop as argument. 390 /// Updates safety information in LoopSafetyInfo argument. 391 void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *); 392 393 /// Returns true if the instruction in a loop is guaranteed to execute at least 394 /// once. 395 bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, 396 const Loop *CurLoop, 397 const LoopSafetyInfo *SafetyInfo); 398 399 /// \brief Returns the instructions that use values defined in the loop. 400 SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L); 401 402 /// \brief Find string metadata for loop 403 /// 404 /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an 405 /// operand or null otherwise. If the string metadata is not found return 406 /// Optional's not-a-value. 407 Optional<const MDOperand *> findStringMetadataForLoop(Loop *TheLoop, 408 StringRef Name); 409 410 /// \brief Set input string into loop metadata by keeping other values intact. 411 void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, 412 unsigned V = 0); 413 414 /// Helper to consistently add the set of standard passes to a loop pass's \c 415 /// AnalysisUsage. 416 /// 417 /// All loop passes should call this as part of implementing their \c 418 /// getAnalysisUsage. 419 void getLoopAnalysisUsage(AnalysisUsage &AU); 420 } 421 422 #endif 423
