include/llvm/Analysis/IVDescriptors.h

   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"
  22 #include "llvm/Analysis/AliasAnalysis.h"
  23 #include "llvm/Analysis/DemandedBits.h"
  24 #include "llvm/Analysis/EHPersonalities.h"
  25 #include "llvm/Analysis/MustExecute.h"
  26 #include "llvm/Analysis/TargetTransformInfo.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.
  62 class RecurrenceDescriptor {
  63 public:
  64   /// This enum represents the kinds of recurrences that we support.
  65   enum RecurrenceKind {
  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.
  79   enum MinMaxRecurrenceKind {
  80     MRK_Invalid,
  81     MRK_UIntMin,
  82     MRK_UIntMax,
  83     MRK_SIntMin,
  84     MRK_SIntMax,
  85     MRK_FloatMin,
  86     MRK_FloatMax
  87   };
  88
  89   RecurrenceDescriptor() = default;
  90
  91   RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K,
  92                        FastMathFlags FMF, MinMaxRecurrenceKind MK,
  93                        Instruction *UAI, Type *RT, bool Signed,
  94                        SmallPtrSetImpl<Instruction *> &CI)
  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
 108     InstDesc(Instruction *I, MinMaxRecurrenceKind K, Instruction *UAI = nullptr)
 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.
 139   static InstDesc isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
 140                                     InstDesc &Prev, bool HasFunNoNaNAttr);
 141
 142   /// Returns true if instruction I has multiple uses in Insts
 143   static bool hasMultipleUsesOf(Instruction *I,
 144                                 SmallPtrSetImpl<Instruction *> &Insts,
 145                                 unsigned MaxNumUses);
 146
 147   /// Returns true if all uses of the instruction I is within the Set.
 148   static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &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).
 153   static InstDesc isMinMaxSelectCmpPattern(Instruction *I, 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(RecurrenceKind Kind, Instruction *I);
 158
 159   /// Returns identity corresponding to the RecurrenceKind.
 160   static Constant *getRecurrenceIdentity(RecurrenceKind K, Type *Tp);
 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,
 196                          DenseMap<Instruction *, Instruction *> &SinkAfter,
 197                          DominatorTree *DT);
 198
 199   RecurrenceKind getRecurrenceKind() { return Kind; }
 200
 201   MinMaxRecurrenceKind getMinMaxRecurrenceKind() { return MinMaxKind; }
 202
 203   FastMathFlags getFastMathFlags() { return FMF; }
 204
 205   TrackingVH<Value> getRecurrenceStartValue() { return StartValue; }
 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.
 220   static bool isFloatingPointRecurrenceKind(RecurrenceKind 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.
 231   SmallPtrSet<Instruction *, 8> &getCastInsts() { return CastInsts; }
 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.
 243   RecurrenceKind Kind = RK_NoRecurrence;
 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.
 256   SmallPtrSet<Instruction *, 8> CastInsts;
 257 };
 258
 259 /// A struct for saving information about induction variables.
 260 class InductionDescriptor {
 261 public:
 262   /// This enum represents the kinds of inductions that we support.
 263   enum InductionKind {
 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,
 302                                InductionDescriptor &D);
 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,
 311                              PredicatedScalarEvolution &PSE,
 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.
 317   bool hasUnsafeAlgebra() {
 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.
 324   Instruction *getUnsafeAlgebraInst() {
 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.
 334   Instruction::BinaryOps getInductionOpcode() const {
 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.
 342   const SmallVectorImpl<Instruction *> &getCastInsts() const {
 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