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