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/IR/Dominators.h" 19 #include "llvm/IR/IRBuilder.h" 20 21 namespace llvm { 22 class AliasAnalysis; 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 LICMSafetyInfoLICMSafetyInfo42 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 RecurrenceDescriptor()86 RecurrenceDescriptor() 87 : StartValue(nullptr), LoopExitInstr(nullptr), Kind(RK_NoRecurrence), 88 MinMaxKind(MRK_Invalid) {} 89 RecurrenceDescriptor(Value * Start,Instruction * Exit,RecurrenceKind K,MinMaxRecurrenceKind MK)90 RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K, 91 MinMaxRecurrenceKind MK) 92 : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK) {} 93 94 /// This POD struct holds information about a potential recurrence operation. 95 class InstDesc { 96 97 public: InstDesc(bool IsRecur,Instruction * I)98 InstDesc(bool IsRecur, Instruction *I) 99 : IsRecurrence(IsRecur), PatternLastInst(I), MinMaxKind(MRK_Invalid) {} 100 InstDesc(Instruction * I,MinMaxRecurrenceKind K)101 InstDesc(Instruction *I, MinMaxRecurrenceKind K) 102 : IsRecurrence(true), PatternLastInst(I), MinMaxKind(K) {} 103 isRecurrence()104 bool isRecurrence() { return IsRecurrence; } 105 getMinMaxKind()106 MinMaxRecurrenceKind getMinMaxKind() { return MinMaxKind; } 107 getPatternInst()108 Instruction *getPatternInst() { return PatternLastInst; } 109 110 private: 111 // Is this instruction a recurrence candidate. 112 bool IsRecurrence; 113 // The last instruction in a min/max pattern (select of the select(icmp()) 114 // pattern), or the current recurrence instruction otherwise. 115 Instruction *PatternLastInst; 116 // If this is a min/max pattern the comparison predicate. 117 MinMaxRecurrenceKind MinMaxKind; 118 }; 119 120 /// Returns a struct describing if the instruction 'I' can be a recurrence 121 /// variable of type 'Kind'. If the recurrence is a min/max pattern of 122 /// select(icmp()) this function advances the instruction pointer 'I' from the 123 /// compare instruction to the select instruction and stores this pointer in 124 /// 'PatternLastInst' member of the returned struct. 125 static InstDesc isRecurrenceInstr(Instruction *I, RecurrenceKind Kind, 126 InstDesc &Prev, bool HasFunNoNaNAttr); 127 128 /// Returns true if instuction I has multiple uses in Insts 129 static bool hasMultipleUsesOf(Instruction *I, 130 SmallPtrSetImpl<Instruction *> &Insts); 131 132 /// Returns true if all uses of the instruction I is within the Set. 133 static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set); 134 135 /// Returns a struct describing if the instruction if the instruction is a 136 /// Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y) 137 /// or max(X, Y). 138 static InstDesc isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev); 139 140 /// Returns identity corresponding to the RecurrenceKind. 141 static Constant *getRecurrenceIdentity(RecurrenceKind K, Type *Tp); 142 143 /// Returns the opcode of binary operation corresponding to the 144 /// RecurrenceKind. 145 static unsigned getRecurrenceBinOp(RecurrenceKind Kind); 146 147 /// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind. 148 static Value *createMinMaxOp(IRBuilder<> &Builder, MinMaxRecurrenceKind RK, 149 Value *Left, Value *Right); 150 151 /// Returns true if Phi is a reduction of type Kind and adds it to the 152 /// RecurrenceDescriptor. 153 static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop, 154 bool HasFunNoNaNAttr, 155 RecurrenceDescriptor &RedDes); 156 157 /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor is 158 /// returned in RedDes. 159 static bool isReductionPHI(PHINode *Phi, Loop *TheLoop, 160 RecurrenceDescriptor &RedDes); 161 getRecurrenceKind()162 RecurrenceKind getRecurrenceKind() { return Kind; } 163 getMinMaxRecurrenceKind()164 MinMaxRecurrenceKind getMinMaxRecurrenceKind() { return MinMaxKind; } 165 getRecurrenceStartValue()166 TrackingVH<Value> getRecurrenceStartValue() { return StartValue; } 167 getLoopExitInstr()168 Instruction *getLoopExitInstr() { return LoopExitInstr; } 169 170 private: 171 // The starting value of the recurrence. 172 // It does not have to be zero! 173 TrackingVH<Value> StartValue; 174 // The instruction who's value is used outside the loop. 175 Instruction *LoopExitInstr; 176 // The kind of the recurrence. 177 RecurrenceKind Kind; 178 // If this a min/max recurrence the kind of recurrence. 179 MinMaxRecurrenceKind MinMaxKind; 180 }; 181 182 BasicBlock *InsertPreheaderForLoop(Loop *L, Pass *P); 183 184 /// \brief Simplify each loop in a loop nest recursively. 185 /// 186 /// This takes a potentially un-simplified loop L (and its children) and turns 187 /// it into a simplified loop nest with preheaders and single backedges. It 188 /// will optionally update \c AliasAnalysis and \c ScalarEvolution analyses if 189 /// passed into it. 190 bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, Pass *PP, 191 AliasAnalysis *AA = nullptr, ScalarEvolution *SE = nullptr, 192 AssumptionCache *AC = nullptr); 193 194 /// \brief Put loop into LCSSA form. 195 /// 196 /// Looks at all instructions in the loop which have uses outside of the 197 /// current loop. For each, an LCSSA PHI node is inserted and the uses outside 198 /// the loop are rewritten to use this node. 199 /// 200 /// LoopInfo and DominatorTree are required and preserved. 201 /// 202 /// If ScalarEvolution is passed in, it will be preserved. 203 /// 204 /// Returns true if any modifications are made to the loop. 205 bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, 206 ScalarEvolution *SE = nullptr); 207 208 /// \brief Put a loop nest into LCSSA form. 209 /// 210 /// This recursively forms LCSSA for a loop nest. 211 /// 212 /// LoopInfo and DominatorTree are required and preserved. 213 /// 214 /// If ScalarEvolution is passed in, it will be preserved. 215 /// 216 /// Returns true if any modifications are made to the loop. 217 bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, 218 ScalarEvolution *SE = nullptr); 219 220 /// \brief Walk the specified region of the CFG (defined by all blocks 221 /// dominated by the specified block, and that are in the current loop) in 222 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit 223 /// uses before definitions, allowing us to sink a loop body in one pass without 224 /// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, 225 /// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all 226 /// instructions of the loop and loop safety information as arguments. 227 /// It returns changed status. 228 bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, 229 TargetLibraryInfo *, Loop *, AliasSetTracker *, 230 LICMSafetyInfo *); 231 232 /// \brief Walk the specified region of the CFG (defined by all blocks 233 /// dominated by the specified block, and that are in the current loop) in depth 234 /// first order w.r.t the DominatorTree. This allows us to visit definitions 235 /// before uses, allowing us to hoist a loop body in one pass without iteration. 236 /// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout, 237 /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the 238 /// loop and loop safety information as arguments. It returns changed status. 239 bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, 240 TargetLibraryInfo *, Loop *, AliasSetTracker *, 241 LICMSafetyInfo *); 242 243 /// \brief Try to promote memory values to scalars by sinking stores out of 244 /// the loop and moving loads to before the loop. We do this by looping over 245 /// the stores in the loop, looking for stores to Must pointers which are 246 /// loop invariant. It takes AliasSet, Loop exit blocks vector, loop exit blocks 247 /// insertion point vector, PredIteratorCache, LoopInfo, DominatorTree, Loop, 248 /// AliasSet information for all instructions of the loop and loop safety 249 /// information as arguments. It returns changed status. 250 bool promoteLoopAccessesToScalars(AliasSet &, SmallVectorImpl<BasicBlock*> &, 251 SmallVectorImpl<Instruction*> &, 252 PredIteratorCache &, LoopInfo *, 253 DominatorTree *, Loop *, AliasSetTracker *, 254 LICMSafetyInfo *); 255 256 /// \brief Computes safety information for a loop 257 /// checks loop body & header for the possiblity of may throw 258 /// exception, it takes LICMSafetyInfo and loop as argument. 259 /// Updates safety information in LICMSafetyInfo argument. 260 void computeLICMSafetyInfo(LICMSafetyInfo *, Loop *); 261 262 /// \brief Checks if the given PHINode in a loop header is an induction 263 /// variable. Returns true if this is an induction PHI along with the step 264 /// value. 265 bool isInductionPHI(PHINode *, ScalarEvolution *, ConstantInt *&); 266 } 267 268 #endif 269