LLVM  9.0.0svn
IVDescriptors.h
Go to the documentation of this file.
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/Optional.h"
18 #include "llvm/ADT/SetVector.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/ADT/StringRef.h"
27 #include "llvm/IR/Dominators.h"
28 #include "llvm/IR/IRBuilder.h"
29 #include "llvm/IR/InstrTypes.h"
30 #include "llvm/IR/Operator.h"
31 #include "llvm/IR/ValueHandle.h"
32 #include "llvm/Support/Casting.h"
33 
34 namespace llvm {
35 
36 class AliasSet;
37 class AliasSetTracker;
38 class BasicBlock;
39 class DataLayout;
40 class Loop;
41 class LoopInfo;
42 class OptimizationRemarkEmitter;
43 class PredicatedScalarEvolution;
44 class PredIteratorCache;
45 class ScalarEvolution;
46 class SCEV;
47 class TargetLibraryInfo;
48 class TargetTransformInfo;
49 
50 /// The RecurrenceDescriptor is used to identify recurrences variables in a
51 /// loop. Reduction is a special case of recurrence that has uses of the
52 /// recurrence variable outside the loop. The method isReductionPHI identifies
53 /// reductions that are basic recurrences.
54 ///
55 /// Basic recurrences are defined as the summation, product, OR, AND, XOR, min,
56 /// or max of a set of terms. For example: for(i=0; i<n; i++) { total +=
57 /// array[i]; } is a summation of array elements. Basic recurrences are a
58 /// special case of chains of recurrences (CR). See ScalarEvolution for CR
59 /// references.
60 
61 /// This struct holds information about recurrence variables.
63 public:
64  /// This enum represents the kinds of recurrences that we support.
66  RK_NoRecurrence, ///< Not a recurrence.
67  RK_IntegerAdd, ///< Sum of integers.
68  RK_IntegerMult, ///< Product of integers.
69  RK_IntegerOr, ///< Bitwise or logical OR of numbers.
70  RK_IntegerAnd, ///< Bitwise or logical AND of numbers.
71  RK_IntegerXor, ///< Bitwise or logical XOR of numbers.
72  RK_IntegerMinMax, ///< Min/max implemented in terms of select(cmp()).
73  RK_FloatAdd, ///< Sum of floats.
74  RK_FloatMult, ///< Product of floats.
75  RK_FloatMinMax ///< Min/max implemented in terms of select(cmp()).
76  };
77 
78  // This enum represents the kind of minmax recurrence.
87  };
88 
89  RecurrenceDescriptor() = default;
90 
93  Instruction *UAI, Type *RT, bool Signed,
95  : StartValue(Start), LoopExitInstr(Exit), Kind(K), FMF(FMF),
96  MinMaxKind(MK), UnsafeAlgebraInst(UAI), RecurrenceType(RT),
97  IsSigned(Signed) {
98  CastInsts.insert(CI.begin(), CI.end());
99  }
100 
101  /// This POD struct holds information about a potential recurrence operation.
102  class InstDesc {
103  public:
104  InstDesc(bool IsRecur, Instruction *I, Instruction *UAI = nullptr)
105  : IsRecurrence(IsRecur), PatternLastInst(I), MinMaxKind(MRK_Invalid),
106  UnsafeAlgebraInst(UAI) {}
107 
109  : IsRecurrence(true), PatternLastInst(I), MinMaxKind(K),
110  UnsafeAlgebraInst(UAI) {}
111 
112  bool isRecurrence() { return IsRecurrence; }
113 
114  bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
115 
116  Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
117 
118  MinMaxRecurrenceKind getMinMaxKind() { return MinMaxKind; }
119 
120  Instruction *getPatternInst() { return PatternLastInst; }
121 
122  private:
123  // Is this instruction a recurrence candidate.
124  bool IsRecurrence;
125  // The last instruction in a min/max pattern (select of the select(icmp())
126  // pattern), or the current recurrence instruction otherwise.
127  Instruction *PatternLastInst;
128  // If this is a min/max pattern the comparison predicate.
129  MinMaxRecurrenceKind MinMaxKind;
130  // Recurrence has unsafe algebra.
131  Instruction *UnsafeAlgebraInst;
132  };
133 
134  /// Returns a struct describing if the instruction 'I' can be a recurrence
135  /// variable of type 'Kind'. If the recurrence is a min/max pattern of
136  /// select(icmp()) this function advances the instruction pointer 'I' from the
137  /// compare instruction to the select instruction and stores this pointer in
138  /// 'PatternLastInst' member of the returned struct.
140  InstDesc &Prev, bool HasFunNoNaNAttr);
141 
142  /// Returns true if instruction I has multiple uses in Insts
143  static bool hasMultipleUsesOf(Instruction *I,
145  unsigned MaxNumUses);
146 
147  /// Returns true if all uses of the instruction I is within the Set.
149 
150  /// Returns a struct describing if the instruction if the instruction is a
151  /// Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y)
152  /// or max(X, Y).
154 
155  /// Returns a struct describing if the instruction is a
156  /// Select(FCmp(X, Y), (Z = X op PHINode), PHINode) instruction pattern.
158 
159  /// Returns identity corresponding to the RecurrenceKind.
161 
162  /// Returns the opcode of binary operation corresponding to the
163  /// RecurrenceKind.
164  static unsigned getRecurrenceBinOp(RecurrenceKind Kind);
165 
166  /// Returns true if Phi is a reduction of type Kind and adds it to the
167  /// RecurrenceDescriptor. If either \p DB is non-null or \p AC and \p DT are
168  /// non-null, the minimal bit width needed to compute the reduction will be
169  /// computed.
170  static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop,
171  bool HasFunNoNaNAttr,
172  RecurrenceDescriptor &RedDes,
173  DemandedBits *DB = nullptr,
174  AssumptionCache *AC = nullptr,
175  DominatorTree *DT = nullptr);
176 
177  /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor
178  /// is returned in RedDes. If either \p DB is non-null or \p AC and \p DT are
179  /// non-null, the minimal bit width needed to compute the reduction will be
180  /// computed.
181  static bool isReductionPHI(PHINode *Phi, Loop *TheLoop,
182  RecurrenceDescriptor &RedDes,
183  DemandedBits *DB = nullptr,
184  AssumptionCache *AC = nullptr,
185  DominatorTree *DT = nullptr);
186 
187  /// Returns true if Phi is a first-order recurrence. A first-order recurrence
188  /// is a non-reduction recurrence relation in which the value of the
189  /// recurrence in the current loop iteration equals a value defined in the
190  /// previous iteration. \p SinkAfter includes pairs of instructions where the
191  /// first will be rescheduled to appear after the second if/when the loop is
192  /// vectorized. It may be augmented with additional pairs if needed in order
193  /// to handle Phi as a first-order recurrence.
194  static bool
195  isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop,
197  DominatorTree *DT);
198 
200 
202 
203  FastMathFlags getFastMathFlags() { return FMF; }
204 
206 
207  Instruction *getLoopExitInstr() { return LoopExitInstr; }
208 
209  /// Returns true if the recurrence has unsafe algebra which requires a relaxed
210  /// floating-point model.
211  bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
212 
213  /// Returns first unsafe algebra instruction in the PHI node's use-chain.
214  Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
215 
216  /// Returns true if the recurrence kind is an integer kind.
217  static bool isIntegerRecurrenceKind(RecurrenceKind Kind);
218 
219  /// Returns true if the recurrence kind is a floating point kind.
221 
222  /// Returns true if the recurrence kind is an arithmetic kind.
223  static bool isArithmeticRecurrenceKind(RecurrenceKind Kind);
224 
225  /// Returns the type of the recurrence. This type can be narrower than the
226  /// actual type of the Phi if the recurrence has been type-promoted.
227  Type *getRecurrenceType() { return RecurrenceType; }
228 
229  /// Returns a reference to the instructions used for type-promoting the
230  /// recurrence.
232 
233  /// Returns true if all source operands of the recurrence are SExtInsts.
234  bool isSigned() { return IsSigned; }
235 
236 private:
237  // The starting value of the recurrence.
238  // It does not have to be zero!
239  TrackingVH<Value> StartValue;
240  // The instruction who's value is used outside the loop.
241  Instruction *LoopExitInstr = nullptr;
242  // The kind of the recurrence.
244  // The fast-math flags on the recurrent instructions. We propagate these
245  // fast-math flags into the vectorized FP instructions we generate.
246  FastMathFlags FMF;
247  // If this a min/max recurrence the kind of recurrence.
248  MinMaxRecurrenceKind MinMaxKind = MRK_Invalid;
249  // First occurrence of unasfe algebra in the PHI's use-chain.
250  Instruction *UnsafeAlgebraInst = nullptr;
251  // The type of the recurrence.
252  Type *RecurrenceType = nullptr;
253  // True if all source operands of the recurrence are SExtInsts.
254  bool IsSigned = false;
255  // Instructions used for type-promoting the recurrence.
257 };
258 
259 /// A struct for saving information about induction variables.
261 public:
262  /// This enum represents the kinds of inductions that we support.
264  IK_NoInduction, ///< Not an induction variable.
265  IK_IntInduction, ///< Integer induction variable. Step = C.
266  IK_PtrInduction, ///< Pointer induction var. Step = C / sizeof(elem).
267  IK_FpInduction ///< Floating point induction variable.
268  };
269 
270 public:
271  /// Default constructor - creates an invalid induction.
272  InductionDescriptor() = default;
273 
274  /// Get the consecutive direction. Returns:
275  /// 0 - unknown or non-consecutive.
276  /// 1 - consecutive and increasing.
277  /// -1 - consecutive and decreasing.
278  int getConsecutiveDirection() const;
279 
280  Value *getStartValue() const { return StartValue; }
281  InductionKind getKind() const { return IK; }
282  const SCEV *getStep() const { return Step; }
283  BinaryOperator *getInductionBinOp() const { return InductionBinOp; }
284  ConstantInt *getConstIntStepValue() const;
285 
286  /// Returns true if \p Phi is an induction in the loop \p L. If \p Phi is an
287  /// induction, the induction descriptor \p D will contain the data describing
288  /// this induction. If by some other means the caller has a better SCEV
289  /// expression for \p Phi than the one returned by the ScalarEvolution
290  /// analysis, it can be passed through \p Expr. If the def-use chain
291  /// associated with the phi includes casts (that we know we can ignore
292  /// under proper runtime checks), they are passed through \p CastsToIgnore.
293  static bool
294  isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE,
295  InductionDescriptor &D, const SCEV *Expr = nullptr,
296  SmallVectorImpl<Instruction *> *CastsToIgnore = nullptr);
297 
298  /// Returns true if \p Phi is a floating point induction in the loop \p L.
299  /// If \p Phi is an induction, the induction descriptor \p D will contain
300  /// the data describing this induction.
301  static bool isFPInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE,
303 
304  /// Returns true if \p Phi is a loop \p L induction, in the context associated
305  /// with the run-time predicate of PSE. If \p Assume is true, this can add
306  /// further SCEV predicates to \p PSE in order to prove that \p Phi is an
307  /// induction.
308  /// If \p Phi is an induction, \p D will contain the data describing this
309  /// induction.
310  static bool isInductionPHI(PHINode *Phi, const Loop *L,
312  InductionDescriptor &D, bool Assume = false);
313 
314  /// Returns true if the induction type is FP and the binary operator does
315  /// not have the "fast-math" property. Such operation requires a relaxed FP
316  /// mode.
318  return (IK == IK_FpInduction) && InductionBinOp &&
319  !cast<FPMathOperator>(InductionBinOp)->isFast();
320  }
321 
322  /// Returns induction operator that does not have "fast-math" property
323  /// and requires FP unsafe mode.
325  if (IK != IK_FpInduction)
326  return nullptr;
327 
328  if (!InductionBinOp || cast<FPMathOperator>(InductionBinOp)->isFast())
329  return nullptr;
330  return InductionBinOp;
331  }
332 
333  /// Returns binary opcode of the induction operator.
335  return InductionBinOp ? InductionBinOp->getOpcode()
336  : Instruction::BinaryOpsEnd;
337  }
338 
339  /// Returns a reference to the type cast instructions in the induction
340  /// update chain, that are redundant when guarded with a runtime
341  /// SCEV overflow check.
343  return RedundantCasts;
344  }
345 
346 private:
347  /// Private constructor - used by \c isInductionPHI.
348  InductionDescriptor(Value *Start, InductionKind K, const SCEV *Step,
349  BinaryOperator *InductionBinOp = nullptr,
350  SmallVectorImpl<Instruction *> *Casts = nullptr);
351 
352  /// Start value.
353  TrackingVH<Value> StartValue;
354  /// Induction kind.
355  InductionKind IK = IK_NoInduction;
356  /// Step value.
357  const SCEV *Step = nullptr;
358  // Instruction that advances induction variable.
359  BinaryOperator *InductionBinOp = nullptr;
360  // Instructions used for type-casts of the induction variable,
361  // that are redundant when guarded with a runtime SCEV overflow check.
362  SmallVector<Instruction *, 2> RedundantCasts;
363 };
364 
365 } // end namespace llvm
366 
367 #endif // LLVM_ANALYSIS_IVDESCRIPTORS_H
Bitwise or logical XOR of numbers.
Definition: IVDescriptors.h:71
static bool isArithmeticRecurrenceKind(RecurrenceKind Kind)
Returns true if the recurrence kind is an arithmetic kind.
BinaryOperator * getInductionBinOp() const
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Instruction * getUnsafeAlgebraInst()
Returns first unsafe algebra instruction in the PHI node&#39;s use-chain.
Various leaf nodes.
Definition: ISDOpcodes.h:59
Min/max implemented in terms of select(cmp()).
Definition: IVDescriptors.h:72
InstDesc(bool IsRecur, Instruction *I, Instruction *UAI=nullptr)
Instruction::BinaryOps getInductionOpcode() const
Returns binary opcode of the induction operator.
static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop, bool HasFunNoNaNAttr, RecurrenceDescriptor &RedDes, DemandedBits *DB=nullptr, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Returns true if Phi is a reduction of type Kind and adds it to the RecurrenceDescriptor.
The main scalar evolution driver.
A cache of @llvm.assume calls within a function.
MinMaxRecurrenceKind getMinMaxRecurrenceKind()
InductionKind getKind() const
block Block Frequency true
Value * getStartValue() const
static InstDesc isRecurrenceInstr(Instruction *I, RecurrenceKind Kind, InstDesc &Prev, bool HasFunNoNaNAttr)
Returns a struct describing if the instruction &#39;I&#39; can be a recurrence variable of type &#39;Kind&#39;...
static bool hasMultipleUsesOf(Instruction *I, SmallPtrSetImpl< Instruction *> &Insts, unsigned MaxNumUses)
Returns true if instruction I has multiple uses in Insts.
bool isSigned()
Returns true if all source operands of the recurrence are SExtInsts.
bool hasUnsafeAlgebra()
Returns true if the recurrence has unsafe algebra which requires a relaxed floating-point model...
static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl< Instruction *> &Set)
Returns true if all uses of the instruction I is within the Set.
static InstDesc isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev)
Returns a struct describing if the instruction if the instruction is a Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y) or max(X, Y).
Contains a collection of routines for determining if a given instruction is guaranteed to execute if ...
This POD struct holds information about a potential recurrence operation.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
Bitwise or logical AND of numbers.
Definition: IVDescriptors.h:70
Pointer induction var. Step = C / sizeof(elem).
Integer induction variable. Step = C.
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
Min/max implemented in terms of select(cmp()).
Definition: IVDescriptors.h:75
Value handle that tracks a Value across RAUW.
Definition: ValueHandle.h:327
This is an important base class in LLVM.
Definition: Constant.h:41
Instruction * getUnsafeAlgebraInst()
Returns induction operator that does not have "fast-math" property and requires FP unsafe mode...
const SCEV * getStep() const
InstDesc(Instruction *I, MinMaxRecurrenceKind K, Instruction *UAI=nullptr)
static bool isReductionPHI(PHINode *Phi, Loop *TheLoop, RecurrenceDescriptor &RedDes, DemandedBits *DB=nullptr, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Returns true if Phi is a reduction in TheLoop.
static InstDesc isConditionalRdxPattern(RecurrenceKind Kind, Instruction *I)
Returns a struct describing if the instruction is a Select(FCmp(X, Y), (Z = X op PHINode), PHINode) instruction pattern.
RecurrenceKind getRecurrenceKind()
static unsigned getRecurrenceBinOp(RecurrenceKind Kind)
Returns the opcode of binary operation corresponding to the RecurrenceKind.
static bool isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop, DenseMap< Instruction *, Instruction *> &SinkAfter, DominatorTree *DT)
Returns true if Phi is a first-order recurrence.
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
Definition: IVDescriptors.h:62
MinMaxRecurrenceKind getMinMaxKind()
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
A struct for saving information about induction variables.
Bitwise or logical OR of numbers.
Definition: IVDescriptors.h:69
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
static bool isFloatingPointRecurrenceKind(RecurrenceKind Kind)
Returns true if the recurrence kind is a floating point kind.
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static Constant * getRecurrenceIdentity(RecurrenceKind K, Type *Tp)
Returns identity corresponding to the RecurrenceKind.
bool hasUnsafeAlgebra()
Returns true if the induction type is FP and the binary operator does not have the "fast-math" proper...
const SmallVectorImpl< Instruction * > & getCastInsts() const
Returns a reference to the type cast instructions in the induction update chain, that are redundant w...
iterator begin() const
Definition: SmallPtrSet.h:396
This class represents an analyzed expression in the program.
static bool isIntegerRecurrenceKind(RecurrenceKind Kind)
Returns true if the recurrence kind is an integer kind.
Instruction * getLoopExitInstr()
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:465
#define I(x, y, z)
Definition: MD5.cpp:58
FastMathFlags getFastMathFlags()
iterator end() const
Definition: SmallPtrSet.h:401
SmallPtrSet< Instruction *, 8 > & getCastInsts()
Returns a reference to the instructions used for type-promoting the recurrence.
LLVM Value Representation.
Definition: Value.h:72
TrackingVH< Value > getRecurrenceStartValue()
Convenience struct for specifying and reasoning about fast-math flags.
Definition: Operator.h:159
This pass exposes codegen information to IR-level passes.
InductionKind
This enum represents the kinds of inductions that we support.
RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K, FastMathFlags FMF, MinMaxRecurrenceKind MK, Instruction *UAI, Type *RT, bool Signed, SmallPtrSetImpl< Instruction *> &CI)
Definition: IVDescriptors.h:91
RecurrenceKind
This enum represents the kinds of recurrences that we support.
Definition: IVDescriptors.h:65
Type * getRecurrenceType()
Returns the type of the recurrence.