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