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