1//===- llvm/Analysis/IVDescriptors.h - IndVar Descriptors -------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file "describes" induction and recurrence variables.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_ANALYSIS_IVDESCRIPTORS_H
14#define LLVM_ANALYSIS_IVDESCRIPTORS_H
15
16#include "llvm/ADT/MapVector.h"
17#include "llvm/ADT/SmallPtrSet.h"
18#include "llvm/ADT/SmallVector.h"
19#include "llvm/IR/IntrinsicInst.h"
20#include "llvm/IR/ValueHandle.h"
21
22namespace llvm {
23
24class AssumptionCache;
25class DemandedBits;
26class DominatorTree;
27class Instruction;
28class Loop;
29class PredicatedScalarEvolution;
30class ScalarEvolution;
31class SCEV;
32class StoreInst;
33
34/// These are the kinds of recurrences that we support.
35enum class RecurKind {
36 None, ///< Not a recurrence.
37 Add, ///< Sum of integers.
38 Mul, ///< Product of integers.
39 Or, ///< Bitwise or logical OR of integers.
40 And, ///< Bitwise or logical AND of integers.
41 Xor, ///< Bitwise or logical XOR of integers.
42 SMin, ///< Signed integer min implemented in terms of select(cmp()).
43 SMax, ///< Signed integer max implemented in terms of select(cmp()).
44 UMin, ///< Unisgned integer min implemented in terms of select(cmp()).
45 UMax, ///< Unsigned integer max implemented in terms of select(cmp()).
46 FAdd, ///< Sum of floats.
47 FMul, ///< Product of floats.
48 FMin, ///< FP min implemented in terms of select(cmp()).
49 FMax, ///< FP max implemented in terms of select(cmp()).
50 FMulAdd, ///< Fused multiply-add of floats (a * b + c).
51 SelectICmp, ///< Integer select(icmp(),x,y) where one of (x,y) is loop
52 ///< invariant
53 SelectFCmp ///< Integer select(fcmp(),x,y) where one of (x,y) is loop
54 ///< invariant
55};
56
57/// The RecurrenceDescriptor is used to identify recurrences variables in a
58/// loop. Reduction is a special case of recurrence that has uses of the
59/// recurrence variable outside the loop. The method isReductionPHI identifies
60/// reductions that are basic recurrences.
61///
62/// Basic recurrences are defined as the summation, product, OR, AND, XOR, min,
63/// or max of a set of terms. For example: for(i=0; i<n; i++) { total +=
64/// array[i]; } is a summation of array elements. Basic recurrences are a
65/// special case of chains of recurrences (CR). See ScalarEvolution for CR
66/// references.
67
68/// This struct holds information about recurrence variables.
69class RecurrenceDescriptor {
70public:
71 RecurrenceDescriptor() = default;
72
73 RecurrenceDescriptor(Value *Start, Instruction *Exit, StoreInst *Store,
74 RecurKind K, FastMathFlags FMF, Instruction *ExactFP,
75 Type *RT, bool Signed, bool Ordered,
76 SmallPtrSetImpl<Instruction *> &CI,
77 unsigned MinWidthCastToRecurTy)
78 : IntermediateStore(Store), StartValue(Start), LoopExitInstr(Exit),
79 Kind(K), FMF(FMF), ExactFPMathInst(ExactFP), RecurrenceType(RT),
80 IsSigned(Signed), IsOrdered(Ordered),
81 MinWidthCastToRecurrenceType(MinWidthCastToRecurTy) {
82 CastInsts.insert(CI.begin(), CI.end());
83 }
84
85 /// This POD struct holds information about a potential recurrence operation.
86 class InstDesc {
87 public:
88 InstDesc(bool IsRecur, Instruction *I, Instruction *ExactFP = nullptr)
89 : IsRecurrence(IsRecur), PatternLastInst(I),
90 RecKind(RecurKind::None), ExactFPMathInst(ExactFP) {}
91
92 InstDesc(Instruction *I, RecurKind K, Instruction *ExactFP = nullptr)
93 : IsRecurrence(true), PatternLastInst(I), RecKind(K),
94 ExactFPMathInst(ExactFP) {}
95
96 bool isRecurrence() const { return IsRecurrence; }
97
98 bool needsExactFPMath() const { return ExactFPMathInst != nullptr; }
99
100 Instruction *getExactFPMathInst() const { return ExactFPMathInst; }
101
102 RecurKind getRecKind() const { return RecKind; }
103
104 Instruction *getPatternInst() const { return PatternLastInst; }
105
106 private:
107 // Is this instruction a recurrence candidate.
108 bool IsRecurrence;
109 // The last instruction in a min/max pattern (select of the select(icmp())
110 // pattern), or the current recurrence instruction otherwise.
111 Instruction *PatternLastInst;
112 // If this is a min/max pattern.
113 RecurKind RecKind;
114 // Recurrence does not allow floating-point reassociation.
115 Instruction *ExactFPMathInst;
116 };
117
118 /// Returns a struct describing if the instruction 'I' can be a recurrence
119 /// variable of type 'Kind' for a Loop \p L and reduction PHI \p Phi.
120 /// If the recurrence is a min/max pattern of select(icmp()) this function
121 /// advances the instruction pointer 'I' from the compare instruction to the
122 /// select instruction and stores this pointer in 'PatternLastInst' member of
123 /// the returned struct.
124 static InstDesc isRecurrenceInstr(Loop *L, PHINode *Phi, Instruction *I,
125 RecurKind Kind, InstDesc &Prev,
126 FastMathFlags FuncFMF);
127
128 /// Returns true if instruction I has multiple uses in Insts
129 static bool hasMultipleUsesOf(Instruction *I,
130 SmallPtrSetImpl<Instruction *> &Insts,
131 unsigned MaxNumUses);
132
133 /// Returns true if all uses of the instruction I is within the Set.
134 static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set);
135
136 /// Returns a struct describing if the instruction is a llvm.(s/u)(min/max),
137 /// llvm.minnum/maxnum or a Select(ICmp(X, Y), X, Y) pair of instructions
138 /// corresponding to a min(X, Y) or max(X, Y), matching the recurrence kind \p
139 /// Kind. \p Prev specifies the description of an already processed select
140 /// instruction, so its corresponding cmp can be matched to it.
141 static InstDesc isMinMaxPattern(Instruction *I, RecurKind Kind,
142 const InstDesc &Prev);
143
144 /// Returns a struct describing whether the instruction is either a
145 /// Select(ICmp(A, B), X, Y), or
146 /// Select(FCmp(A, B), X, Y)
147 /// where one of (X, Y) is a loop invariant integer and the other is a PHI
148 /// value. \p Prev specifies the description of an already processed select
149 /// instruction, so its corresponding cmp can be matched to it.
150 static InstDesc isSelectCmpPattern(Loop *Loop, PHINode *OrigPhi,
151 Instruction *I, InstDesc &Prev);
152
153 /// Returns a struct describing if the instruction is a
154 /// Select(FCmp(X, Y), (Z = X op PHINode), PHINode) instruction pattern.
155 static InstDesc isConditionalRdxPattern(RecurKind Kind, Instruction *I);
156
157 /// Returns identity corresponding to the RecurrenceKind.
158 Value *getRecurrenceIdentity(RecurKind K, Type *Tp, FastMathFlags FMF) const;
159
160 /// Returns the opcode corresponding to the RecurrenceKind.
161 static unsigned getOpcode(RecurKind Kind);
162
163 /// Returns true if Phi is a reduction of type Kind and adds it to the
164 /// RecurrenceDescriptor. If either \p DB is non-null or \p AC and \p DT are
165 /// non-null, the minimal bit width needed to compute the reduction will be
166 /// computed.
167 static bool
168 AddReductionVar(PHINode *Phi, RecurKind Kind, Loop *TheLoop,
169 FastMathFlags FuncFMF, RecurrenceDescriptor &RedDes,
170 DemandedBits *DB = nullptr, AssumptionCache *AC = nullptr,
171 DominatorTree *DT = nullptr, ScalarEvolution *SE = nullptr);
172
173 /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor
174 /// is returned in RedDes. If either \p DB is non-null or \p AC and \p DT are
175 /// non-null, the minimal bit width needed to compute the reduction will be
176 /// computed. If \p SE is non-null, store instructions to loop invariant
177 /// addresses are processed.
178 static bool
179 isReductionPHI(PHINode *Phi, Loop *TheLoop, RecurrenceDescriptor &RedDes,
180 DemandedBits *DB = nullptr, AssumptionCache *AC = nullptr,
181 DominatorTree *DT = nullptr, ScalarEvolution *SE = nullptr);
182
183 /// Returns true if Phi is a first-order recurrence. A first-order recurrence
184 /// is a non-reduction recurrence relation in which the value of the
185 /// recurrence in the current loop iteration equals a value defined in the
186 /// previous iteration. \p SinkAfter includes pairs of instructions where the
187 /// first will be rescheduled to appear after the second if/when the loop is
188 /// vectorized. It may be augmented with additional pairs if needed in order
189 /// to handle Phi as a first-order recurrence.
190 static bool
191 isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop,
192 MapVector<Instruction *, Instruction *> &SinkAfter,
193 DominatorTree *DT);
194
195 RecurKind getRecurrenceKind() const { return Kind; }
196
197 unsigned getOpcode() const { return getOpcode(getRecurrenceKind()); }
198
199 FastMathFlags getFastMathFlags() const { return FMF; }
200
201 TrackingVH<Value> getRecurrenceStartValue() const { return StartValue; }
202
203 Instruction *getLoopExitInstr() const { return LoopExitInstr; }
204
205 /// Returns true if the recurrence has floating-point math that requires
206 /// precise (ordered) operations.
207 bool hasExactFPMath() const { return ExactFPMathInst != nullptr; }
208
209 /// Returns 1st non-reassociative FP instruction in the PHI node's use-chain.
210 Instruction *getExactFPMathInst() const { return ExactFPMathInst; }
211
212 /// Returns true if the recurrence kind is an integer kind.
213 static bool isIntegerRecurrenceKind(RecurKind Kind);
214
215 /// Returns true if the recurrence kind is a floating point kind.
216 static bool isFloatingPointRecurrenceKind(RecurKind Kind);
217
218 /// Returns true if the recurrence kind is an integer min/max kind.
219 static bool isIntMinMaxRecurrenceKind(RecurKind Kind) {
220 return Kind == RecurKind::UMin || Kind == RecurKind::UMax ||
221 Kind == RecurKind::SMin || Kind == RecurKind::SMax;
222 }
223
224 /// Returns true if the recurrence kind is a floating-point min/max kind.
225 static bool isFPMinMaxRecurrenceKind(RecurKind Kind) {
226 return Kind == RecurKind::FMin || Kind == RecurKind::FMax;
227 }
228
229 /// Returns true if the recurrence kind is any min/max kind.
230 static bool isMinMaxRecurrenceKind(RecurKind Kind) {
231 return isIntMinMaxRecurrenceKind(Kind) || isFPMinMaxRecurrenceKind(Kind);
232 }
233
234 /// Returns true if the recurrence kind is of the form
235 /// select(cmp(),x,y) where one of (x,y) is loop invariant.
236 static bool isSelectCmpRecurrenceKind(RecurKind Kind) {
237 return Kind == RecurKind::SelectICmp || Kind == RecurKind::SelectFCmp;
238 }
239
240 /// Returns the type of the recurrence. This type can be narrower than the
241 /// actual type of the Phi if the recurrence has been type-promoted.
242 Type *getRecurrenceType() const { return RecurrenceType; }
243
244 /// Returns a reference to the instructions used for type-promoting the
245 /// recurrence.
246 const SmallPtrSet<Instruction *, 8> &getCastInsts() const { return CastInsts; }
247
248 /// Returns the minimum width used by the recurrence in bits.
249 unsigned getMinWidthCastToRecurrenceTypeInBits() const {
250 return MinWidthCastToRecurrenceType;
251 }
252
253 /// Returns true if all source operands of the recurrence are SExtInsts.
254 bool isSigned() const { return IsSigned; }
255
256 /// Expose an ordered FP reduction to the instance users.
257 bool isOrdered() const { return IsOrdered; }
258
259 /// Attempts to find a chain of operations from Phi to LoopExitInst that can
260 /// be treated as a set of reductions instructions for in-loop reductions.
261 SmallVector<Instruction *, 4> getReductionOpChain(PHINode *Phi,
262 Loop *L) const;
263
264 /// Returns true if the instruction is a call to the llvm.fmuladd intrinsic.
265 static bool isFMulAddIntrinsic(Instruction *I) {
266 return isa<IntrinsicInst>(I) &&
267 cast<IntrinsicInst>(I)->getIntrinsicID() == Intrinsic::fmuladd;
268 }
269
270 /// Reductions may store temporary or final result to an invariant address.
271 /// If there is such a store in the loop then, after successfull run of
272 /// AddReductionVar method, this field will be assigned the last met store.
273 StoreInst *IntermediateStore = nullptr;
274
275private:
276 // The starting value of the recurrence.
277 // It does not have to be zero!
278 TrackingVH<Value> StartValue;
279 // The instruction who's value is used outside the loop.
280 Instruction *LoopExitInstr = nullptr;
281 // The kind of the recurrence.
282 RecurKind Kind = RecurKind::None;
283 // The fast-math flags on the recurrent instructions. We propagate these
284 // fast-math flags into the vectorized FP instructions we generate.
285 FastMathFlags FMF;
286 // First instance of non-reassociative floating-point in the PHI's use-chain.
287 Instruction *ExactFPMathInst = nullptr;
288 // The type of the recurrence.
289 Type *RecurrenceType = nullptr;
290 // True if all source operands of the recurrence are SExtInsts.
291 bool IsSigned = false;
292 // True if this recurrence can be treated as an in-order reduction.
293 // Currently only a non-reassociative FAdd can be considered in-order,
294 // if it is also the only FAdd in the PHI's use chain.
295 bool IsOrdered = false;
296 // Instructions used for type-promoting the recurrence.
297 SmallPtrSet<Instruction *, 8> CastInsts;
298 // The minimum width used by the recurrence.
299 unsigned MinWidthCastToRecurrenceType;
300};
301
302/// A struct for saving information about induction variables.
303class InductionDescriptor {
304public:
305 /// This enum represents the kinds of inductions that we support.
306 enum InductionKind {
307 IK_NoInduction, ///< Not an induction variable.
308 IK_IntInduction, ///< Integer induction variable. Step = C.
309 IK_PtrInduction, ///< Pointer induction var. Step = C / sizeof(elem).
310 IK_FpInduction ///< Floating point induction variable.
311 };
312
313public:
314 /// Default constructor - creates an invalid induction.
315 InductionDescriptor() = default;
316
317 Value *getStartValue() const { return StartValue; }
318 InductionKind getKind() const { return IK; }
319 const SCEV *getStep() const { return Step; }
320 BinaryOperator *getInductionBinOp() const { return InductionBinOp; }
321 ConstantInt *getConstIntStepValue() const;
322
323 /// Returns true if \p Phi is an induction in the loop \p L. If \p Phi is an
324 /// induction, the induction descriptor \p D will contain the data describing
325 /// this induction. If by some other means the caller has a better SCEV
326 /// expression for \p Phi than the one returned by the ScalarEvolution
327 /// analysis, it can be passed through \p Expr. If the def-use chain
328 /// associated with the phi includes casts (that we know we can ignore
329 /// under proper runtime checks), they are passed through \p CastsToIgnore.
330 static bool
331 isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE,
332 InductionDescriptor &D, const SCEV *Expr = nullptr,
333 SmallVectorImpl<Instruction *> *CastsToIgnore = nullptr);
334
335 /// Returns true if \p Phi is a floating point induction in the loop \p L.
336 /// If \p Phi is an induction, the induction descriptor \p D will contain
337 /// the data describing this induction.
338 static bool isFPInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE,
339 InductionDescriptor &D);
340
341 /// Returns true if \p Phi is a loop \p L induction, in the context associated
342 /// with the run-time predicate of PSE. If \p Assume is true, this can add
343 /// further SCEV predicates to \p PSE in order to prove that \p Phi is an
344 /// induction.
345 /// If \p Phi is an induction, \p D will contain the data describing this
346 /// induction.
347 static bool isInductionPHI(PHINode *Phi, const Loop *L,
348 PredicatedScalarEvolution &PSE,
349 InductionDescriptor &D, bool Assume = false);
350
351 /// Returns floating-point induction operator that does not allow
352 /// reassociation (transforming the induction requires an override of normal
353 /// floating-point rules).
354 Instruction *getExactFPMathInst() {
355 if (IK == IK_FpInduction && InductionBinOp &&
356 !InductionBinOp->hasAllowReassoc())
357 return InductionBinOp;
358 return nullptr;
359 }
360
361 /// Returns binary opcode of the induction operator.
362 Instruction::BinaryOps getInductionOpcode() const {
363 return InductionBinOp ? InductionBinOp->getOpcode()
364 : Instruction::BinaryOpsEnd;
365 }
366
367 Type *getElementType() const {
368 assert(IK == IK_PtrInduction && "Only pointer induction has element type");
369 return ElementType;
370 }
371
372 /// Returns a reference to the type cast instructions in the induction
373 /// update chain, that are redundant when guarded with a runtime
374 /// SCEV overflow check.
375 const SmallVectorImpl<Instruction *> &getCastInsts() const {
376 return RedundantCasts;
377 }
378
379private:
380 /// Private constructor - used by \c isInductionPHI.
381 InductionDescriptor(Value *Start, InductionKind K, const SCEV *Step,
382 BinaryOperator *InductionBinOp = nullptr,
383 Type *ElementType = nullptr,
384 SmallVectorImpl<Instruction *> *Casts = nullptr);
385
386 /// Start value.
387 TrackingVH<Value> StartValue;
388 /// Induction kind.
389 InductionKind IK = IK_NoInduction;
390 /// Step value.
391 const SCEV *Step = nullptr;
392 // Instruction that advances induction variable.
393 BinaryOperator *InductionBinOp = nullptr;
394 // Element type for pointer induction variables.
395 // TODO: This can be dropped once support for typed pointers is removed.
396 Type *ElementType = nullptr;
397 // Instructions used for type-casts of the induction variable,
398 // that are redundant when guarded with a runtime SCEV overflow check.
399 SmallVector<Instruction *, 2> RedundantCasts;
400};
401
402} // end namespace llvm
403
404#endif // LLVM_ANALYSIS_IVDESCRIPTORS_H
405

source code of llvm/include/llvm/Analysis/IVDescriptors.h