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/IR/Dominators.h"
  19 #include "llvm/IR/IRBuilder.h"
  20
  21 namespace llvm {
  22 class AliasAnalysis;
  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
  90   RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K,
  91                        MinMaxRecurrenceKind MK,
  92                        Instruction *UAI /*Unsafe Algebra Inst*/)
  93       : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK),
  94         UnsafeAlgebraInst(UAI) {}
  95
  96   /// This POD struct holds information about a potential recurrence operation.
  97   class InstDesc {
  98
  99   public:
 100     InstDesc(bool IsRecur, Instruction *I, Instruction *UAI = nullptr)
 101         : IsRecurrence(IsRecur), PatternLastInst(I), MinMaxKind(MRK_Invalid),
 102           UnsafeAlgebraInst(UAI) {}
 103
 104     InstDesc(Instruction *I, MinMaxRecurrenceKind K, Instruction *UAI = nullptr)
 105         : IsRecurrence(true), PatternLastInst(I), MinMaxKind(K),
 106           UnsafeAlgebraInst(UAI) {}
 107
 108     bool isRecurrence() { return IsRecurrence; }
 109
 110     bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
 111
 112     Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
 113
 114     MinMaxRecurrenceKind getMinMaxKind() { return MinMaxKind; }
 115
 116     Instruction *getPatternInst() { return PatternLastInst; }
 117
 118   private:
 119     // Is this instruction a recurrence candidate.
 120     bool IsRecurrence;
 121     // The last instruction in a min/max pattern (select of the select(icmp())
 122     // pattern), or the current recurrence instruction otherwise.
 123     Instruction *PatternLastInst;
 124     // If this is a min/max pattern the comparison predicate.
 125     MinMaxRecurrenceKind MinMaxKind;
 126     // Recurrence has unsafe algebra.
 127     Instruction *UnsafeAlgebraInst;
 128   };
 129
 130   /// Returns a struct describing if the instruction 'I' can be a recurrence
 131   /// variable of type 'Kind'. If the recurrence is a min/max pattern of
 132   /// select(icmp()) this function advances the instruction pointer 'I' from the
 133   /// compare instruction to the select instruction and stores this pointer in
 134   /// 'PatternLastInst' member of the returned struct.
 135   static InstDesc isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
 136                                     InstDesc &Prev, bool HasFunNoNaNAttr);
 137
 138   /// Returns true if instruction I has multiple uses in Insts
 139   static bool hasMultipleUsesOf(Instruction *I,
 140                                 SmallPtrSetImpl<Instruction *> &Insts);
 141
 142   /// Returns true if all uses of the instruction I is within the Set.
 143   static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set);
 144
 145   /// Returns a struct describing if the instruction if the instruction is a
 146   /// Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y)
 147   /// or max(X, Y).
 148   static InstDesc isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev);
 149
 150   /// Returns identity corresponding to the RecurrenceKind.
 151   static Constant *getRecurrenceIdentity(RecurrenceKind K, Type *Tp);
 152
 153   /// Returns the opcode of binary operation corresponding to the
 154   /// RecurrenceKind.
 155   static unsigned getRecurrenceBinOp(RecurrenceKind Kind);
 156
 157   /// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
 158   static Value *createMinMaxOp(IRBuilder<> &Builder, MinMaxRecurrenceKind RK,
 159                                Value *Left, Value *Right);
 160
 161   /// Returns true if Phi is a reduction of type Kind and adds it to the
 162   /// RecurrenceDescriptor.
 163   static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop,
 164                               bool HasFunNoNaNAttr,
 165                               RecurrenceDescriptor &RedDes);
 166
 167   /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor is
 168   /// returned in RedDes.
 169   static bool isReductionPHI(PHINode *Phi, Loop *TheLoop,
 170                              RecurrenceDescriptor &RedDes);
 171
 172   RecurrenceKind getRecurrenceKind() { return Kind; }
 173
 174   MinMaxRecurrenceKind getMinMaxRecurrenceKind() { return MinMaxKind; }
 175
 176   TrackingVH<Value> getRecurrenceStartValue() { return StartValue; }
 177
 178   Instruction *getLoopExitInstr() { return LoopExitInstr; }
 179
 180   /// Returns true if the recurrence has unsafe algebra which requires a relaxed
 181   /// floating-point model.
 182   bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
 183
 184   /// Returns first unsafe algebra instruction in the PHI node's use-chain.
 185   Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
 186
 187 private:
 188   // The starting value of the recurrence.
 189   // It does not have to be zero!
 190   TrackingVH<Value> StartValue;
 191   // The instruction who's value is used outside the loop.
 192   Instruction *LoopExitInstr;
 193   // The kind of the recurrence.
 194   RecurrenceKind Kind;
 195   // If this a min/max recurrence the kind of recurrence.
 196   MinMaxRecurrenceKind MinMaxKind;
 197   // First occurance of unasfe algebra in the PHI's use-chain.
 198   Instruction *UnsafeAlgebraInst;
 199 };
 200
 201 BasicBlock *InsertPreheaderForLoop(Loop *L, Pass *P);
 202
 203 /// \brief Simplify each loop in a loop nest recursively.
 204 ///
 205 /// This takes a potentially un-simplified loop L (and its children) and turns
 206 /// it into a simplified loop nest with preheaders and single backedges. It
 207 /// will optionally update \c AliasAnalysis and \c ScalarEvolution analyses if
 208 /// passed into it.
 209 bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, Pass *PP,
 210                   ScalarEvolution *SE = nullptr, AssumptionCache *AC = nullptr);
 211
 212 /// \brief Put loop into LCSSA form.
 213 ///
 214 /// Looks at all instructions in the loop which have uses outside of the
 215 /// current loop. For each, an LCSSA PHI node is inserted and the uses outside
 216 /// the loop are rewritten to use this node.
 217 ///
 218 /// LoopInfo and DominatorTree are required and preserved.
 219 ///
 220 /// If ScalarEvolution is passed in, it will be preserved.
 221 ///
 222 /// Returns true if any modifications are made to the loop.
 223 bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI,
 224                ScalarEvolution *SE = nullptr);
 225
 226 /// \brief Put a loop nest into LCSSA form.
 227 ///
 228 /// This recursively forms LCSSA for a loop nest.
 229 ///
 230 /// LoopInfo and DominatorTree are required and preserved.
 231 ///
 232 /// If ScalarEvolution is passed in, it will be preserved.
 233 ///
 234 /// Returns true if any modifications are made to the loop.
 235 bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI,
 236                           ScalarEvolution *SE = nullptr);
 237
 238 /// \brief Walk the specified region of the CFG (defined by all blocks
 239 /// dominated by the specified block, and that are in the current loop) in
 240 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit
 241 /// uses before definitions, allowing us to sink a loop body in one pass without
 242 /// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree,
 243 /// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all
 244 /// instructions of the loop and loop safety information as arguments.
 245 /// It returns changed status.
 246 bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
 247                 TargetLibraryInfo *, Loop *, AliasSetTracker *,
 248                 LICMSafetyInfo *);
 249
 250 /// \brief Walk the specified region of the CFG (defined by all blocks
 251 /// dominated by the specified block, and that are in the current loop) in depth
 252 /// first order w.r.t the DominatorTree.  This allows us to visit definitions
 253 /// before uses, allowing us to hoist a loop body in one pass without iteration.
 254 /// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout,
 255 /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
 256 /// loop and loop safety information as arguments. It returns changed status.
 257 bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
 258                  TargetLibraryInfo *, Loop *, AliasSetTracker *,
 259                  LICMSafetyInfo *);
 260
 261 /// \brief Try to promote memory values to scalars by sinking stores out of
 262 /// the loop and moving loads to before the loop.  We do this by looping over
 263 /// the stores in the loop, looking for stores to Must pointers which are
 264 /// loop invariant. It takes AliasSet, Loop exit blocks vector, loop exit blocks
 265 /// insertion point vector, PredIteratorCache, LoopInfo, DominatorTree, Loop,
 266 /// AliasSet information for all instructions of the loop and loop safety
 267 /// information as arguments. It returns changed status.
 268 bool promoteLoopAccessesToScalars(AliasSet &, SmallVectorImpl<BasicBlock*> &,
 269                                   SmallVectorImpl<Instruction*> &,
 270                                   PredIteratorCache &, LoopInfo *,
 271                                   DominatorTree *, Loop *, AliasSetTracker *,
 272                                   LICMSafetyInfo *);
 273
 274 /// \brief Computes safety information for a loop
 275 /// checks loop body & header for the possibility of may throw
 276 /// exception, it takes LICMSafetyInfo and loop as argument.
 277 /// Updates safety information in LICMSafetyInfo argument.
 278 void computeLICMSafetyInfo(LICMSafetyInfo *, Loop *);
 279
 280 /// \brief Checks if the given PHINode in a loop header is an induction
 281 /// variable. Returns true if this is an induction PHI along with the step
 282 /// value.
 283 bool isInductionPHI(PHINode *, ScalarEvolution *, ConstantInt *&);
 284
 285 /// \brief Returns the instructions that use values defined in the loop.
 286 SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L);
 287 }
 288
 289 #endif