Line data Source code
1 : //===- llvm/Analysis/IVDescriptors.h - IndVar Descriptors -------*- 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 "describes" induction and recurrence variables.
11 : //
12 : //===----------------------------------------------------------------------===//
13 :
14 : #ifndef LLVM_ANALYSIS_IVDESCRIPTORS_H
15 : #define LLVM_ANALYSIS_IVDESCRIPTORS_H
16 :
17 : #include "llvm/ADT/DenseMap.h"
18 : #include "llvm/ADT/Optional.h"
19 : #include "llvm/ADT/SetVector.h"
20 : #include "llvm/ADT/SmallPtrSet.h"
21 : #include "llvm/ADT/SmallVector.h"
22 : #include "llvm/ADT/StringRef.h"
23 : #include "llvm/Analysis/AliasAnalysis.h"
24 : #include "llvm/Analysis/DemandedBits.h"
25 : #include "llvm/Analysis/EHPersonalities.h"
26 : #include "llvm/Analysis/MustExecute.h"
27 : #include "llvm/Analysis/TargetTransformInfo.h"
28 : #include "llvm/IR/Dominators.h"
29 : #include "llvm/IR/IRBuilder.h"
30 : #include "llvm/IR/InstrTypes.h"
31 : #include "llvm/IR/Operator.h"
32 : #include "llvm/IR/ValueHandle.h"
33 : #include "llvm/Support/Casting.h"
34 :
35 : namespace llvm {
36 :
37 : class AliasSet;
38 : class AliasSetTracker;
39 : class BasicBlock;
40 : class DataLayout;
41 : class Loop;
42 : class LoopInfo;
43 : class OptimizationRemarkEmitter;
44 : class PredicatedScalarEvolution;
45 : class PredIteratorCache;
46 : class ScalarEvolution;
47 : class SCEV;
48 : class TargetLibraryInfo;
49 : class TargetTransformInfo;
50 :
51 : /// The RecurrenceDescriptor is used to identify recurrences variables in a
52 : /// loop. Reduction is a special case of recurrence that has uses of the
53 : /// recurrence variable outside the loop. The method isReductionPHI identifies
54 : /// reductions that are basic recurrences.
55 : ///
56 : /// Basic recurrences are defined as the summation, product, OR, AND, XOR, min,
57 : /// or max of a set of terms. For example: for(i=0; i<n; i++) { total +=
58 : /// array[i]; } is a summation of array elements. Basic recurrences are a
59 : /// special case of chains of recurrences (CR). See ScalarEvolution for CR
60 : /// references.
61 :
62 : /// This struct holds information about recurrence variables.
63 : class RecurrenceDescriptor {
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 3792 : RecurrenceDescriptor() = default;
91 :
92 466 : RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K,
93 : MinMaxRecurrenceKind MK, Instruction *UAI, Type *RT,
94 : bool Signed, SmallPtrSetImpl<Instruction *> &CI)
95 466 : : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK),
96 466 : UnsafeAlgebraInst(UAI), RecurrenceType(RT), IsSigned(Signed) {
97 466 : CastInsts.insert(CI.begin(), CI.end());
98 466 : }
99 :
100 : /// This POD struct holds information about a potential recurrence operation.
101 : class InstDesc {
102 : public:
103 : InstDesc(bool IsRecur, Instruction *I, Instruction *UAI = nullptr)
104 81691 : : IsRecurrence(IsRecur), PatternLastInst(I), MinMaxKind(MRK_Invalid),
105 81691 : UnsafeAlgebraInst(UAI) {}
106 :
107 : InstDesc(Instruction *I, MinMaxRecurrenceKind K, Instruction *UAI = nullptr)
108 247 : : IsRecurrence(true), PatternLastInst(I), MinMaxKind(K),
109 247 : UnsafeAlgebraInst(UAI) {}
110 :
111 0 : bool isRecurrence() { return IsRecurrence; }
112 :
113 : bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
114 :
115 0 : Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
116 :
117 0 : 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 : unsigned MaxNumUses);
145 :
146 : /// Returns true if all uses of the instruction I is within the Set.
147 : static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set);
148 :
149 : /// Returns a struct describing if the instruction if the instruction is a
150 : /// Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y)
151 : /// or max(X, Y).
152 : static InstDesc isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev);
153 :
154 : /// Returns a struct describing if the instruction is a
155 : /// Select(FCmp(X, Y), (Z = X op PHINode), PHINode) instruction pattern.
156 : static InstDesc isConditionalRdxPattern(RecurrenceKind Kind, Instruction *I);
157 :
158 : /// Returns identity corresponding to the RecurrenceKind.
159 : static Constant *getRecurrenceIdentity(RecurrenceKind K, Type *Tp);
160 :
161 : /// Returns the opcode of binary operation corresponding to the
162 : /// RecurrenceKind.
163 : static unsigned getRecurrenceBinOp(RecurrenceKind Kind);
164 :
165 : /// Returns true if Phi is a reduction of type Kind and adds it to the
166 : /// RecurrenceDescriptor. If either \p DB is non-null or \p AC and \p DT are
167 : /// non-null, the minimal bit width needed to compute the reduction will be
168 : /// computed.
169 : static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop,
170 : bool HasFunNoNaNAttr,
171 : RecurrenceDescriptor &RedDes,
172 : DemandedBits *DB = nullptr,
173 : AssumptionCache *AC = nullptr,
174 : DominatorTree *DT = nullptr);
175 :
176 : /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor
177 : /// is returned in RedDes. If either \p DB is non-null or \p AC and \p DT are
178 : /// non-null, the minimal bit width needed to compute the reduction will be
179 : /// computed.
180 : static bool isReductionPHI(PHINode *Phi, Loop *TheLoop,
181 : RecurrenceDescriptor &RedDes,
182 : DemandedBits *DB = nullptr,
183 : AssumptionCache *AC = nullptr,
184 : DominatorTree *DT = nullptr);
185 :
186 : /// Returns true if Phi is a first-order recurrence. A first-order recurrence
187 : /// is a non-reduction recurrence relation in which the value of the
188 : /// recurrence in the current loop iteration equals a value defined in the
189 : /// previous iteration. \p SinkAfter includes pairs of instructions where the
190 : /// first will be rescheduled to appear after the second if/when the loop is
191 : /// vectorized. It may be augmented with additional pairs if needed in order
192 : /// to handle Phi as a first-order recurrence.
193 : static bool
194 : isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop,
195 : DenseMap<Instruction *, Instruction *> &SinkAfter,
196 : DominatorTree *DT);
197 :
198 0 : RecurrenceKind getRecurrenceKind() { return Kind; }
199 :
200 0 : MinMaxRecurrenceKind getMinMaxRecurrenceKind() { return MinMaxKind; }
201 :
202 : TrackingVH<Value> getRecurrenceStartValue() { return StartValue; }
203 :
204 0 : Instruction *getLoopExitInstr() { return LoopExitInstr; }
205 :
206 : /// Returns true if the recurrence has unsafe algebra which requires a relaxed
207 : /// floating-point model.
208 0 : bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
209 :
210 : /// Returns first unsafe algebra instruction in the PHI node's use-chain.
211 0 : Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
212 :
213 : /// Returns true if the recurrence kind is an integer kind.
214 : static bool isIntegerRecurrenceKind(RecurrenceKind Kind);
215 :
216 : /// Returns true if the recurrence kind is a floating point kind.
217 : static bool isFloatingPointRecurrenceKind(RecurrenceKind Kind);
218 :
219 : /// Returns true if the recurrence kind is an arithmetic kind.
220 : static bool isArithmeticRecurrenceKind(RecurrenceKind Kind);
221 :
222 : /// Returns the type of the recurrence. This type can be narrower than the
223 : /// actual type of the Phi if the recurrence has been type-promoted.
224 0 : Type *getRecurrenceType() { return RecurrenceType; }
225 :
226 : /// Returns a reference to the instructions used for type-promoting the
227 : /// recurrence.
228 : SmallPtrSet<Instruction *, 8> &getCastInsts() { return CastInsts; }
229 :
230 : /// Returns true if all source operands of the recurrence are SExtInsts.
231 0 : bool isSigned() { return IsSigned; }
232 :
233 : private:
234 : // The starting value of the recurrence.
235 : // It does not have to be zero!
236 : TrackingVH<Value> StartValue;
237 : // The instruction who's value is used outside the loop.
238 : Instruction *LoopExitInstr = nullptr;
239 : // The kind of the recurrence.
240 : RecurrenceKind Kind = RK_NoRecurrence;
241 : // If this a min/max recurrence the kind of recurrence.
242 : MinMaxRecurrenceKind MinMaxKind = MRK_Invalid;
243 : // First occurrence of unasfe algebra in the PHI's use-chain.
244 : Instruction *UnsafeAlgebraInst = nullptr;
245 : // The type of the recurrence.
246 : Type *RecurrenceType = nullptr;
247 : // True if all source operands of the recurrence are SExtInsts.
248 : bool IsSigned = false;
249 : // Instructions used for type-promoting the recurrence.
250 : SmallPtrSet<Instruction *, 8> CastInsts;
251 : };
252 :
253 : /// A struct for saving information about induction variables.
254 : class InductionDescriptor {
255 : public:
256 : /// This enum represents the kinds of inductions that we support.
257 : enum InductionKind {
258 : IK_NoInduction, ///< Not an induction variable.
259 : IK_IntInduction, ///< Integer induction variable. Step = C.
260 : IK_PtrInduction, ///< Pointer induction var. Step = C / sizeof(elem).
261 : IK_FpInduction ///< Floating point induction variable.
262 : };
263 :
264 : public:
265 : /// Default constructor - creates an invalid induction.
266 2907 : InductionDescriptor() = default;
267 :
268 : /// Get the consecutive direction. Returns:
269 : /// 0 - unknown or non-consecutive.
270 : /// 1 - consecutive and increasing.
271 : /// -1 - consecutive and decreasing.
272 : int getConsecutiveDirection() const;
273 :
274 : Value *getStartValue() const { return StartValue; }
275 0 : InductionKind getKind() const { return IK; }
276 0 : const SCEV *getStep() const { return Step; }
277 0 : BinaryOperator *getInductionBinOp() const { return InductionBinOp; }
278 : ConstantInt *getConstIntStepValue() const;
279 :
280 : /// Returns true if \p Phi is an induction in the loop \p L. If \p Phi is an
281 : /// induction, the induction descriptor \p D will contain the data describing
282 : /// this induction. If by some other means the caller has a better SCEV
283 : /// expression for \p Phi than the one returned by the ScalarEvolution
284 : /// analysis, it can be passed through \p Expr. If the def-use chain
285 : /// associated with the phi includes casts (that we know we can ignore
286 : /// under proper runtime checks), they are passed through \p CastsToIgnore.
287 : static bool
288 : isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE,
289 : InductionDescriptor &D, const SCEV *Expr = nullptr,
290 : SmallVectorImpl<Instruction *> *CastsToIgnore = nullptr);
291 :
292 : /// Returns true if \p Phi is a floating point induction in the loop \p L.
293 : /// If \p Phi is an induction, the induction descriptor \p D will contain
294 : /// the data describing this induction.
295 : static bool isFPInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE,
296 : InductionDescriptor &D);
297 :
298 : /// Returns true if \p Phi is a loop \p L induction, in the context associated
299 : /// with the run-time predicate of PSE. If \p Assume is true, this can add
300 : /// further SCEV predicates to \p PSE in order to prove that \p Phi is an
301 : /// induction.
302 : /// If \p Phi is an induction, \p D will contain the data describing this
303 : /// induction.
304 : static bool isInductionPHI(PHINode *Phi, const Loop *L,
305 : PredicatedScalarEvolution &PSE,
306 : InductionDescriptor &D, bool Assume = false);
307 :
308 : /// Returns true if the induction type is FP and the binary operator does
309 : /// not have the "fast-math" property. Such operation requires a relaxed FP
310 : /// mode.
311 0 : bool hasUnsafeAlgebra() {
312 2516 : return InductionBinOp && !cast<FPMathOperator>(InductionBinOp)->isFast();
313 : }
314 :
315 : /// Returns induction operator that does not have "fast-math" property
316 : /// and requires FP unsafe mode.
317 0 : Instruction *getUnsafeAlgebraInst() {
318 0 : if (!InductionBinOp || cast<FPMathOperator>(InductionBinOp)->isFast())
319 0 : return nullptr;
320 : return InductionBinOp;
321 : }
322 :
323 : /// Returns binary opcode of the induction operator.
324 0 : Instruction::BinaryOps getInductionOpcode() const {
325 1472 : return InductionBinOp ? InductionBinOp->getOpcode()
326 0 : : Instruction::BinaryOpsEnd;
327 : }
328 :
329 : /// Returns a reference to the type cast instructions in the induction
330 : /// update chain, that are redundant when guarded with a runtime
331 : /// SCEV overflow check.
332 : const SmallVectorImpl<Instruction *> &getCastInsts() const {
333 : return RedundantCasts;
334 : }
335 :
336 : private:
337 : /// Private constructor - used by \c isInductionPHI.
338 : InductionDescriptor(Value *Start, InductionKind K, const SCEV *Step,
339 : BinaryOperator *InductionBinOp = nullptr,
340 : SmallVectorImpl<Instruction *> *Casts = nullptr);
341 :
342 : /// Start value.
343 : TrackingVH<Value> StartValue;
344 : /// Induction kind.
345 : InductionKind IK = IK_NoInduction;
346 : /// Step value.
347 : const SCEV *Step = nullptr;
348 : // Instruction that advances induction variable.
349 : BinaryOperator *InductionBinOp = nullptr;
350 : // Instructions used for type-casts of the induction variable,
351 : // that are redundant when guarded with a runtime SCEV overflow check.
352 : SmallVector<Instruction *, 2> RedundantCasts;
353 : };
354 :
355 : } // end namespace llvm
356 :
357 : #endif // LLVM_ANALYSIS_IVDESCRIPTORS_H
|
