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