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