1 //===- llvm/Transforms/Utils/LoopUtils.h - Loop utilities -*- C++ -*-=========//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines some loop transformation utilities.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
15 #define LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/IR/Dominators.h"
19 #include "llvm/IR/IRBuilder.h"
24 class AliasSetTracker
;
25 class AssumptionCache
;
32 class PredIteratorCache
;
33 class ScalarEvolution
;
34 class TargetLibraryInfo
;
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
41 bool HeaderMayThrow
; // Same as previous, but specific to loop header
42 LICMSafetyInfo() : MayThrow(false), HeaderMayThrow(false)
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.
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
57 /// This struct holds information about recurrence variables.
58 class RecurrenceDescriptor
{
61 /// This enum represents the kinds of recurrences that we support.
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()).
75 // This enum represents the kind of minmax recurrence.
76 enum MinMaxRecurrenceKind
{
86 RecurrenceDescriptor()
87 : StartValue(nullptr), LoopExitInstr(nullptr), Kind(RK_NoRecurrence
),
88 MinMaxKind(MRK_Invalid
), UnsafeAlgebraInst(nullptr),
89 RecurrenceType(nullptr), IsSigned(false) {}
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());
99 /// This POD struct holds information about a potential recurrence operation.
103 InstDesc(bool IsRecur
, Instruction
*I
, Instruction
*UAI
= nullptr)
104 : IsRecurrence(IsRecur
), PatternLastInst(I
), MinMaxKind(MRK_Invalid
),
105 UnsafeAlgebraInst(UAI
) {}
107 InstDesc(Instruction
*I
, MinMaxRecurrenceKind K
, Instruction
*UAI
= nullptr)
108 : IsRecurrence(true), PatternLastInst(I
), MinMaxKind(K
),
109 UnsafeAlgebraInst(UAI
) {}
111 bool isRecurrence() { return IsRecurrence
; }
113 bool hasUnsafeAlgebra() { return UnsafeAlgebraInst
!= nullptr; }
115 Instruction
*getUnsafeAlgebraInst() { return UnsafeAlgebraInst
; }
117 MinMaxRecurrenceKind
getMinMaxKind() { return MinMaxKind
; }
119 Instruction
*getPatternInst() { return PatternLastInst
; }
122 // Is this instruction a recurrence candidate.
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
;
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
);
141 /// Returns true if instruction I has multiple uses in Insts
142 static bool hasMultipleUsesOf(Instruction
*I
,
143 SmallPtrSetImpl
<Instruction
*> &Insts
);
145 /// Returns true if all uses of the instruction I is within the Set.
146 static bool areAllUsesIn(Instruction
*I
, SmallPtrSetImpl
<Instruction
*> &Set
);
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)
151 static InstDesc
isMinMaxSelectCmpPattern(Instruction
*I
, InstDesc
&Prev
);
153 /// Returns identity corresponding to the RecurrenceKind.
154 static Constant
*getRecurrenceIdentity(RecurrenceKind K
, Type
*Tp
);
156 /// Returns the opcode of binary operation corresponding to the
158 static unsigned getRecurrenceBinOp(RecurrenceKind Kind
);
160 /// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
161 static Value
*createMinMaxOp(IRBuilder
<> &Builder
, MinMaxRecurrenceKind RK
,
162 Value
*Left
, Value
*Right
);
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
);
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
);
175 RecurrenceKind
getRecurrenceKind() { return Kind
; }
177 MinMaxRecurrenceKind
getMinMaxRecurrenceKind() { return MinMaxKind
; }
179 TrackingVH
<Value
> getRecurrenceStartValue() { return StartValue
; }
181 Instruction
*getLoopExitInstr() { return LoopExitInstr
; }
183 /// Returns true if the recurrence has unsafe algebra which requires a relaxed
184 /// floating-point model.
185 bool hasUnsafeAlgebra() { return UnsafeAlgebraInst
!= nullptr; }
187 /// Returns first unsafe algebra instruction in the PHI node's use-chain.
188 Instruction
*getUnsafeAlgebraInst() { return UnsafeAlgebraInst
; }
190 /// Returns true if the recurrence kind is an integer kind.
191 static bool isIntegerRecurrenceKind(RecurrenceKind Kind
);
193 /// Returns true if the recurrence kind is a floating point kind.
194 static bool isFloatingPointRecurrenceKind(RecurrenceKind Kind
);
196 /// Returns true if the recurrence kind is an arithmetic kind.
197 static bool isArithmeticRecurrenceKind(RecurrenceKind Kind
);
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
);
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
);
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
; }
221 /// Returns a reference to the instructions used for type-promoting the
223 SmallPtrSet
<Instruction
*, 8> &getCastInsts() { return CastInsts
; }
225 /// Returns true if all source operands of the recurrence are SExtInsts.
226 bool isSigned() { return IsSigned
; }
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.
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.
244 // Instructions used for type-promoting the recurrence.
245 SmallPtrSet
<Instruction
*, 8> CastInsts
;
248 /// A struct for saving information about induction variables.
249 class InductionDescriptor
{
251 /// This enum represents the kinds of inductions that we support.
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).
259 /// Default constructor - creates an invalid induction.
260 InductionDescriptor()
261 : StartValue(nullptr), IK(IK_NoInduction
), StepValue(nullptr) {}
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;
269 /// Compute the transformed value of Index at offset StartValue using step
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;
277 Value
*getStartValue() const { return StartValue
; }
278 InductionKind
getKind() const { return IK
; }
279 ConstantInt
*getStepValue() const { return StepValue
; }
281 static bool isInductionPHI(PHINode
*Phi
, ScalarEvolution
*SE
,
282 InductionDescriptor
&D
);
285 /// Private constructor - used by \c isInductionPHI.
286 InductionDescriptor(Value
*Start
, InductionKind K
, ConstantInt
*Step
);
289 TrackingVH
<Value
> StartValue
;
293 ConstantInt
*StepValue
;
296 BasicBlock
*InsertPreheaderForLoop(Loop
*L
, Pass
*P
);
298 /// \brief Simplify each loop in a loop nest recursively.
300 /// This takes a potentially un-simplified loop L (and its children) and turns
301 /// it into a simplified loop nest with preheaders and single backedges. It
302 /// will optionally update \c AliasAnalysis and \c ScalarEvolution analyses if
304 bool simplifyLoop(Loop
*L
, DominatorTree
*DT
, LoopInfo
*LI
, Pass
*PP
,
305 ScalarEvolution
*SE
= nullptr, AssumptionCache
*AC
= nullptr);
307 /// \brief Put loop into LCSSA form.
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.
313 /// LoopInfo and DominatorTree are required and preserved.
315 /// If ScalarEvolution is passed in, it will be preserved.
317 /// Returns true if any modifications are made to the loop.
318 bool formLCSSA(Loop
&L
, DominatorTree
&DT
, LoopInfo
*LI
,
319 ScalarEvolution
*SE
= nullptr);
321 /// \brief Put a loop nest into LCSSA form.
323 /// This recursively forms LCSSA for a loop nest.
325 /// LoopInfo and DominatorTree are required and preserved.
327 /// If ScalarEvolution is passed in, it will be preserved.
329 /// Returns true if any modifications are made to the loop.
330 bool formLCSSARecursively(Loop
&L
, DominatorTree
&DT
, LoopInfo
*LI
,
331 ScalarEvolution
*SE
= nullptr);
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
*,
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
*,
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
*,
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
*);
375 /// \brief Returns the instructions that use values defined in the loop.
376 SmallVector
<Instruction
*, 8> findDefsUsedOutsideOfLoop(Loop
*L
);