include/llvm/Transforms/Utils/LoopUtils.h

   1 //===- llvm/Transforms/Utils/LoopUtils.h - Loop utilities -*- C++ -*-=========//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines some loop transformation utilities.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
  15 #define LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
  16
  17 #include "llvm/ADT/SmallVector.h"
  18 #include "llvm/Analysis/AliasAnalysis.h"
  19 #include "llvm/IR/Dominators.h"
  20 #include "llvm/IR/IRBuilder.h"
  21
  22 namespace llvm {
  23 class AliasSet;
  24 class AliasSetTracker;
  25 class AssumptionCache;
  26 class BasicBlock;
  27 class DataLayout;
  28 class DominatorTree;
  29 class Loop;
  30 class LoopInfo;
  31 class Pass;
  32 class PredIteratorCache;
  33 class ScalarEvolution;
  34 class TargetLibraryInfo;
  35
  36 /// \brief Captures loop safety information.
  37 /// It keep information for loop & its header may throw exception.
  38 struct LICMSafetyInfo {
  39   bool MayThrow;           // The current loop contains an instruction which
  40                            // may throw.
  41   bool HeaderMayThrow;     // Same as previous, but specific to loop header
  42   LICMSafetyInfo() : MayThrow(false), HeaderMayThrow(false)
  43   {}
  44 };
  45
  46 /// The RecurrenceDescriptor is used to identify recurrences variables in a
  47 /// loop. Reduction is a special case of recurrence that has uses of the
  48 /// recurrence variable outside the loop. The method isReductionPHI identifies
  49 /// reductions that are basic recurrences.
  50 ///
  51 /// Basic recurrences are defined as the summation, product, OR, AND, XOR, min,
  52 /// or max of a set of terms. For example: for(i=0; i<n; i++) { total +=
  53 /// array[i]; } is a summation of array elements. Basic recurrences are a
  54 /// special case of chains of recurrences (CR). See ScalarEvolution for CR
  55 /// references.
  56
  57 /// This struct holds information about recurrence variables.
  58 class RecurrenceDescriptor {
  59
  60 public:
  61   /// This enum represents the kinds of recurrences that we support.
  62   enum RecurrenceKind {
  63     RK_NoRecurrence,  ///< Not a recurrence.
  64     RK_IntegerAdd,    ///< Sum of integers.
  65     RK_IntegerMult,   ///< Product of integers.
  66     RK_IntegerOr,     ///< Bitwise or logical OR of numbers.
  67     RK_IntegerAnd,    ///< Bitwise or logical AND of numbers.
  68     RK_IntegerXor,    ///< Bitwise or logical XOR of numbers.
  69     RK_IntegerMinMax, ///< Min/max implemented in terms of select(cmp()).
  70     RK_FloatAdd,      ///< Sum of floats.
  71     RK_FloatMult,     ///< Product of floats.
  72     RK_FloatMinMax    ///< Min/max implemented in terms of select(cmp()).
  73   };
  74
  75   // This enum represents the kind of minmax recurrence.
  76   enum MinMaxRecurrenceKind {
  77     MRK_Invalid,
  78     MRK_UIntMin,
  79     MRK_UIntMax,
  80     MRK_SIntMin,
  81     MRK_SIntMax,
  82     MRK_FloatMin,
  83     MRK_FloatMax
  84   };
  85
  86   RecurrenceDescriptor()
  87       : StartValue(nullptr), LoopExitInstr(nullptr), Kind(RK_NoRecurrence),
  88         MinMaxKind(MRK_Invalid), UnsafeAlgebraInst(nullptr),
  89         RecurrenceType(nullptr), IsSigned(false) {}
  90
  91   RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K,
  92                        MinMaxRecurrenceKind MK, Instruction *UAI, Type *RT,
  93                        bool Signed, SmallPtrSetImpl<Instruction *> &CI)
  94       : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK),
  95         UnsafeAlgebraInst(UAI), RecurrenceType(RT), IsSigned(Signed) {
  96     CastInsts.insert(CI.begin(), CI.end());
  97   }
  98
  99   /// This POD struct holds information about a potential recurrence operation.
 100   class InstDesc {
 101
 102   public:
 103     InstDesc(bool IsRecur, Instruction *I, Instruction *UAI = nullptr)
 104         : IsRecurrence(IsRecur), PatternLastInst(I), MinMaxKind(MRK_Invalid),
 105           UnsafeAlgebraInst(UAI) {}
 106
 107     InstDesc(Instruction *I, MinMaxRecurrenceKind K, Instruction *UAI = nullptr)
 108         : IsRecurrence(true), PatternLastInst(I), MinMaxKind(K),
 109           UnsafeAlgebraInst(UAI) {}
 110
 111     bool isRecurrence() { return IsRecurrence; }
 112
 113     bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
 114
 115     Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
 116
 117     MinMaxRecurrenceKind getMinMaxKind() { return MinMaxKind; }
 118
 119     Instruction *getPatternInst() { return PatternLastInst; }
 120
 121   private:
 122     // Is this instruction a recurrence candidate.
 123     bool IsRecurrence;
 124     // The last instruction in a min/max pattern (select of the select(icmp())
 125     // pattern), or the current recurrence instruction otherwise.
 126     Instruction *PatternLastInst;
 127     // If this is a min/max pattern the comparison predicate.
 128     MinMaxRecurrenceKind MinMaxKind;
 129     // Recurrence has unsafe algebra.
 130     Instruction *UnsafeAlgebraInst;
 131   };
 132
 133   /// Returns a struct describing if the instruction 'I' can be a recurrence
 134   /// variable of type 'Kind'. If the recurrence is a min/max pattern of
 135   /// select(icmp()) this function advances the instruction pointer 'I' from the
 136   /// compare instruction to the select instruction and stores this pointer in
 137   /// 'PatternLastInst' member of the returned struct.
 138   static InstDesc isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
 139                                     InstDesc &Prev, bool HasFunNoNaNAttr);
 140
 141   /// Returns true if instruction I has multiple uses in Insts
 142   static bool hasMultipleUsesOf(Instruction *I,
 143                                 SmallPtrSetImpl<Instruction *> &Insts);
 144
 145   /// Returns true if all uses of the instruction I is within the Set.
 146   static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set);
 147
 148   /// Returns a struct describing if the instruction if the instruction is a
 149   /// Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y)
 150   /// or max(X, Y).
 151   static InstDesc isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev);
 152
 153   /// Returns identity corresponding to the RecurrenceKind.
 154   static Constant *getRecurrenceIdentity(RecurrenceKind K, Type *Tp);
 155
 156   /// Returns the opcode of binary operation corresponding to the
 157   /// RecurrenceKind.
 158   static unsigned getRecurrenceBinOp(RecurrenceKind Kind);
 159
 160   /// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
 161   static Value *createMinMaxOp(IRBuilder<> &Builder, MinMaxRecurrenceKind RK,
 162                                Value *Left, Value *Right);
 163
 164   /// Returns true if Phi is a reduction of type Kind and adds it to the
 165   /// RecurrenceDescriptor.
 166   static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop,
 167                               bool HasFunNoNaNAttr,
 168                               RecurrenceDescriptor &RedDes);
 169
 170   /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor is
 171   /// returned in RedDes.
 172   static bool isReductionPHI(PHINode *Phi, Loop *TheLoop,
 173                              RecurrenceDescriptor &RedDes);
 174
 175   RecurrenceKind getRecurrenceKind() { return Kind; }
 176
 177   MinMaxRecurrenceKind getMinMaxRecurrenceKind() { return MinMaxKind; }
 178
 179   TrackingVH<Value> getRecurrenceStartValue() { return StartValue; }
 180
 181   Instruction *getLoopExitInstr() { return LoopExitInstr; }
 182
 183   /// Returns true if the recurrence has unsafe algebra which requires a relaxed
 184   /// floating-point model.
 185   bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
 186
 187   /// Returns first unsafe algebra instruction in the PHI node's use-chain.
 188   Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
 189
 190   /// Returns true if the recurrence kind is an integer kind.
 191   static bool isIntegerRecurrenceKind(RecurrenceKind Kind);
 192
 193   /// Returns true if the recurrence kind is a floating point kind.
 194   static bool isFloatingPointRecurrenceKind(RecurrenceKind Kind);
 195
 196   /// Returns true if the recurrence kind is an arithmetic kind.
 197   static bool isArithmeticRecurrenceKind(RecurrenceKind Kind);
 198
 199   /// Determines if Phi may have been type-promoted. If Phi has a single user
 200   /// that ANDs the Phi with a type mask, return the user. RT is updated to
 201   /// account for the narrower bit width represented by the mask, and the AND
 202   /// instruction is added to CI.
 203   static Instruction *lookThroughAnd(PHINode *Phi, Type *&RT,
 204                                      SmallPtrSetImpl<Instruction *> &Visited,
 205                                      SmallPtrSetImpl<Instruction *> &CI);
 206
 207   /// Returns true if all the source operands of a recurrence are either
 208   /// SExtInsts or ZExtInsts. This function is intended to be used with
 209   /// lookThroughAnd to determine if the recurrence has been type-promoted. The
 210   /// source operands are added to CI, and IsSigned is updated to indicate if
 211   /// all source operands are SExtInsts.
 212   static bool getSourceExtensionKind(Instruction *Start, Instruction *Exit,
 213                                      Type *RT, bool &IsSigned,
 214                                      SmallPtrSetImpl<Instruction *> &Visited,
 215                                      SmallPtrSetImpl<Instruction *> &CI);
 216
 217   /// Returns the type of the recurrence. This type can be narrower than the
 218   /// actual type of the Phi if the recurrence has been type-promoted.
 219   Type *getRecurrenceType() { return RecurrenceType; }
 220
 221   /// Returns a reference to the instructions used for type-promoting the
 222   /// recurrence.
 223   SmallPtrSet<Instruction *, 8> &getCastInsts() { return CastInsts; }
 224
 225   /// Returns true if all source operands of the recurrence are SExtInsts.
 226   bool isSigned() { return IsSigned; }
 227
 228 private:
 229   // The starting value of the recurrence.
 230   // It does not have to be zero!
 231   TrackingVH<Value> StartValue;
 232   // The instruction who's value is used outside the loop.
 233   Instruction *LoopExitInstr;
 234   // The kind of the recurrence.
 235   RecurrenceKind Kind;
 236   // If this a min/max recurrence the kind of recurrence.
 237   MinMaxRecurrenceKind MinMaxKind;
 238   // First occurance of unasfe algebra in the PHI's use-chain.
 239   Instruction *UnsafeAlgebraInst;
 240   // The type of the recurrence.
 241   Type *RecurrenceType;
 242   // True if all source operands of the recurrence are SExtInsts.
 243   bool IsSigned;
 244   // Instructions used for type-promoting the recurrence.
 245   SmallPtrSet<Instruction *, 8> CastInsts;
 246 };
 247
 248 /// A struct for saving information about induction variables.
 249 class InductionDescriptor {
 250 public:
 251   /// This enum represents the kinds of inductions that we support.
 252   enum InductionKind {
 253     IK_NoInduction,  ///< Not an induction variable.
 254     IK_IntInduction, ///< Integer induction variable. Step = C.
 255     IK_PtrInduction  ///< Pointer induction var. Step = C / sizeof(elem).
 256   };
 257
 258 public:
 259   /// Default constructor - creates an invalid induction.
 260   InductionDescriptor()
 261     : StartValue(nullptr), IK(IK_NoInduction), StepValue(nullptr) {}
 262
 263   /// Get the consecutive direction. Returns:
 264   ///   0 - unknown or non-consecutive.
 265   ///   1 - consecutive and increasing.
 266   ///  -1 - consecutive and decreasing.
 267   int getConsecutiveDirection() const;
 268
 269   /// Compute the transformed value of Index at offset StartValue using step
 270   /// StepValue.
 271   /// For integer induction, returns StartValue + Index * StepValue.
 272   /// For pointer induction, returns StartValue[Index * StepValue].
 273   /// FIXME: The newly created binary instructions should contain nsw/nuw
 274   /// flags, which can be found from the original scalar operations.
 275   Value *transform(IRBuilder<> &B, Value *Index) const;
 276
 277   Value *getStartValue() const { return StartValue; }
 278   InductionKind getKind() const { return IK; }
 279   ConstantInt *getStepValue() const { return StepValue; }
 280
 281   static bool isInductionPHI(PHINode *Phi, ScalarEvolution *SE,
 282                              InductionDescriptor &D);
 283
 284 private:
 285   /// Private constructor - used by \c isInductionPHI.
 286   InductionDescriptor(Value *Start, InductionKind K, ConstantInt *Step);
 287
 288   /// Start value.
 289   TrackingVH<Value> StartValue;
 290   /// Induction kind.
 291   InductionKind IK;
 292   /// Step value.
 293   ConstantInt *StepValue;
 294 };
 295
 296 BasicBlock *InsertPreheaderForLoop(Loop *L, Pass *P);
 297
 298 /// \brief Simplify each loop in a loop nest recursively.
 299 ///
 300 /// This takes a potentially un-simplified loop L (and its children) and turns
 301 /// it into a simplified loop nest with preheaders and single backedges. It
 302 /// will optionally update \c AliasAnalysis and \c ScalarEvolution analyses if
 303 /// passed into it.
 304 bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, Pass *PP,
 305                   ScalarEvolution *SE, AssumptionCache *AC);
 306
 307 /// \brief Put loop into LCSSA form.
 308 ///
 309 /// Looks at all instructions in the loop which have uses outside of the
 310 /// current loop. For each, an LCSSA PHI node is inserted and the uses outside
 311 /// the loop are rewritten to use this node.
 312 ///
 313 /// LoopInfo and DominatorTree are required and preserved.
 314 ///
 315 /// If ScalarEvolution is passed in, it will be preserved.
 316 ///
 317 /// Returns true if any modifications are made to the loop.
 318 bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI,
 319                ScalarEvolution *SE);
 320
 321 /// \brief Put a loop nest into LCSSA form.
 322 ///
 323 /// This recursively forms LCSSA for a loop nest.
 324 ///
 325 /// LoopInfo and DominatorTree are required and preserved.
 326 ///
 327 /// If ScalarEvolution is passed in, it will be preserved.
 328 ///
 329 /// Returns true if any modifications are made to the loop.
 330 bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI,
 331                           ScalarEvolution *SE);
 332
 333 /// \brief Walk the specified region of the CFG (defined by all blocks
 334 /// dominated by the specified block, and that are in the current loop) in
 335 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit
 336 /// uses before definitions, allowing us to sink a loop body in one pass without
 337 /// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree,
 338 /// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all
 339 /// instructions of the loop and loop safety information as arguments.
 340 /// It returns changed status.
 341 bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
 342                 TargetLibraryInfo *, Loop *, AliasSetTracker *,
 343                 LICMSafetyInfo *);
 344
 345 /// \brief Walk the specified region of the CFG (defined by all blocks
 346 /// dominated by the specified block, and that are in the current loop) in depth
 347 /// first order w.r.t the DominatorTree.  This allows us to visit definitions
 348 /// before uses, allowing us to hoist a loop body in one pass without iteration.
 349 /// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout,
 350 /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
 351 /// loop and loop safety information as arguments. It returns changed status.
 352 bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
 353                  TargetLibraryInfo *, Loop *, AliasSetTracker *,
 354                  LICMSafetyInfo *);
 355
 356 /// \brief Try to promote memory values to scalars by sinking stores out of
 357 /// the loop and moving loads to before the loop.  We do this by looping over
 358 /// the stores in the loop, looking for stores to Must pointers which are
 359 /// loop invariant. It takes AliasSet, Loop exit blocks vector, loop exit blocks
 360 /// insertion point vector, PredIteratorCache, LoopInfo, DominatorTree, Loop,
 361 /// AliasSet information for all instructions of the loop and loop safety
 362 /// information as arguments. It returns changed status.
 363 bool promoteLoopAccessesToScalars(AliasSet &, SmallVectorImpl<BasicBlock*> &,
 364                                   SmallVectorImpl<Instruction*> &,
 365                                   PredIteratorCache &, LoopInfo *,
 366                                   DominatorTree *, Loop *, AliasSetTracker *,
 367                                   LICMSafetyInfo *);
 368
 369 /// \brief Computes safety information for a loop
 370 /// checks loop body & header for the possibility of may throw
 371 /// exception, it takes LICMSafetyInfo and loop as argument.
 372 /// Updates safety information in LICMSafetyInfo argument.
 373 void computeLICMSafetyInfo(LICMSafetyInfo *, Loop *);
 374
 375 /// \brief Returns the instructions that use values defined in the loop.
 376 SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L);
 377 }
 378
 379 #endif