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 /// This POD struct holds information about a potential reduction operation.
  47 class ReductionInstDesc {
  48
  49 public:
  50   // This enum represents the kind of minmax reduction.
  51   enum MinMaxReductionKind {
  52     MRK_Invalid,
  53     MRK_UIntMin,
  54     MRK_UIntMax,
  55     MRK_SIntMin,
  56     MRK_SIntMax,
  57     MRK_FloatMin,
  58     MRK_FloatMax
  59   };
  60   ReductionInstDesc(bool IsRedux, Instruction *I)
  61       : IsReduction(IsRedux), PatternLastInst(I), MinMaxKind(MRK_Invalid) {}
  62
  63   ReductionInstDesc(Instruction *I, MinMaxReductionKind K)
  64       : IsReduction(true), PatternLastInst(I), MinMaxKind(K) {}
  65
  66   bool isReduction() { return IsReduction; }
  67
  68   MinMaxReductionKind getMinMaxKind() { return MinMaxKind; }
  69
  70   Instruction *getPatternInst() { return PatternLastInst; }
  71
  72 private:
  73   // Is this instruction a reduction candidate.
  74   bool IsReduction;
  75   // The last instruction in a min/max pattern (select of the select(icmp())
  76   // pattern), or the current reduction instruction otherwise.
  77   Instruction *PatternLastInst;
  78   // If this is a min/max pattern the comparison predicate.
  79   MinMaxReductionKind MinMaxKind;
  80 };
  81
  82 /// This struct holds information about reduction variables.
  83 class ReductionDescriptor {
  84
  85 public:
  86   /// This enum represents the kinds of reductions that we support.
  87   enum ReductionKind {
  88     RK_NoReduction,   ///< Not a reduction.
  89     RK_IntegerAdd,    ///< Sum of integers.
  90     RK_IntegerMult,   ///< Product of integers.
  91     RK_IntegerOr,     ///< Bitwise or logical OR of numbers.
  92     RK_IntegerAnd,    ///< Bitwise or logical AND of numbers.
  93     RK_IntegerXor,    ///< Bitwise or logical XOR of numbers.
  94     RK_IntegerMinMax, ///< Min/max implemented in terms of select(cmp()).
  95     RK_FloatAdd,      ///< Sum of floats.
  96     RK_FloatMult,     ///< Product of floats.
  97     RK_FloatMinMax    ///< Min/max implemented in terms of select(cmp()).
  98   };
  99
 100   ReductionDescriptor()
 101       : StartValue(nullptr), LoopExitInstr(nullptr), Kind(RK_NoReduction),
 102         MinMaxKind(ReductionInstDesc::MRK_Invalid) {}
 103
 104   ReductionDescriptor(Value *Start, Instruction *Exit, ReductionKind K,
 105                       ReductionInstDesc::MinMaxReductionKind MK)
 106       : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK) {}
 107
 108   /// Returns a struct describing if the instruction 'I' can be a reduction
 109   /// variable of type 'Kind'. If the reduction is a min/max pattern of
 110   /// select(icmp()) this function advances the instruction pointer 'I' from the
 111   /// compare instruction to the select instruction and stores this pointer in
 112   /// 'PatternLastInst' member of the returned struct.
 113   static ReductionInstDesc isReductionInstr(Instruction *I, ReductionKind Kind,
 114                                             ReductionInstDesc &Prev,
 115                                             bool HasFunNoNaNAttr);
 116
 117   /// Returns true if instuction I has multiple uses in Insts
 118   static bool hasMultipleUsesOf(Instruction *I,
 119                                 SmallPtrSetImpl<Instruction *> &Insts);
 120
 121   /// Returns true if all uses of the instruction I is within the Set.
 122   static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set);
 123
 124   /// Returns a struct describing if the instruction if the instruction is a
 125   /// Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y)
 126   /// or max(X, Y).
 127   static ReductionInstDesc isMinMaxSelectCmpPattern(Instruction *I,
 128                                                     ReductionInstDesc &Prev);
 129
 130   /// Returns identity corresponding to the ReductionKind.
 131   static Constant *getReductionIdentity(ReductionKind K, Type *Tp);
 132
 133   /// Returns the opcode of binary operation corresponding to the ReductionKind.
 134   static unsigned getReductionBinOp(ReductionKind Kind);
 135
 136   /// Returns a Min/Max operation corresponding to MinMaxReductionKind.
 137   static Value *createMinMaxOp(IRBuilder<> &Builder,
 138                                ReductionInstDesc::MinMaxReductionKind RK,
 139                                Value *Left, Value *Right);
 140
 141   /// Returns true if Phi is a reduction of type Kind and adds it to the
 142   /// ReductionDescriptor.
 143   static bool AddReductionVar(PHINode *Phi, ReductionKind Kind, Loop *TheLoop,
 144                               bool HasFunNoNaNAttr,
 145                               ReductionDescriptor &RedDes);
 146
 147   /// Returns true if Phi is a reduction in TheLoop. The ReductionDescriptor is
 148   /// returned in RedDes.
 149   static bool isReductionPHI(PHINode *Phi, Loop *TheLoop,
 150                              ReductionDescriptor &RedDes);
 151
 152   ReductionKind getReductionKind() { return Kind; }
 153
 154   ReductionInstDesc::MinMaxReductionKind getMinMaxReductionKind() {
 155     return MinMaxKind;
 156   }
 157
 158   TrackingVH<Value> getReductionStartValue() { return StartValue; }
 159
 160   Instruction *getLoopExitInstr() { return LoopExitInstr; }
 161
 162 private:
 163   // The starting value of the reduction.
 164   // It does not have to be zero!
 165   TrackingVH<Value> StartValue;
 166   // The instruction who's value is used outside the loop.
 167   Instruction *LoopExitInstr;
 168   // The kind of the reduction.
 169   ReductionKind Kind;
 170   // If this a min/max reduction the kind of reduction.
 171   ReductionInstDesc::MinMaxReductionKind MinMaxKind;
 172 };
 173
 174 BasicBlock *InsertPreheaderForLoop(Loop *L, Pass *P);
 175
 176 /// \brief Simplify each loop in a loop nest recursively.
 177 ///
 178 /// This takes a potentially un-simplified loop L (and its children) and turns
 179 /// it into a simplified loop nest with preheaders and single backedges. It
 180 /// will optionally update \c AliasAnalysis and \c ScalarEvolution analyses if
 181 /// passed into it.
 182 bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, Pass *PP,
 183                   AliasAnalysis *AA = nullptr, ScalarEvolution *SE = nullptr,
 184                   AssumptionCache *AC = nullptr);
 185
 186 /// \brief Put loop into LCSSA form.
 187 ///
 188 /// Looks at all instructions in the loop which have uses outside of the
 189 /// current loop. For each, an LCSSA PHI node is inserted and the uses outside
 190 /// the loop are rewritten to use this node.
 191 ///
 192 /// LoopInfo and DominatorTree are required and preserved.
 193 ///
 194 /// If ScalarEvolution is passed in, it will be preserved.
 195 ///
 196 /// Returns true if any modifications are made to the loop.
 197 bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI,
 198                ScalarEvolution *SE = nullptr);
 199
 200 /// \brief Put a loop nest into LCSSA form.
 201 ///
 202 /// This recursively forms LCSSA for a loop nest.
 203 ///
 204 /// LoopInfo and DominatorTree are required and preserved.
 205 ///
 206 /// If ScalarEvolution is passed in, it will be preserved.
 207 ///
 208 /// Returns true if any modifications are made to the loop.
 209 bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI,
 210                           ScalarEvolution *SE = nullptr);
 211
 212 /// \brief Walk the specified region of the CFG (defined by all blocks
 213 /// dominated by the specified block, and that are in the current loop) in
 214 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit
 215 /// uses before definitions, allowing us to sink a loop body in one pass without
 216 /// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree,
 217 /// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all
 218 /// instructions of the loop and loop safety information as arguments.
 219 /// It returns changed status.
 220 bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
 221                 TargetLibraryInfo *, Loop *, AliasSetTracker *,
 222                 LICMSafetyInfo *);
 223
 224 /// \brief Walk the specified region of the CFG (defined by all blocks
 225 /// dominated by the specified block, and that are in the current loop) in depth
 226 /// first order w.r.t the DominatorTree.  This allows us to visit definitions
 227 /// before uses, allowing us to hoist a loop body in one pass without iteration.
 228 /// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout,
 229 /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
 230 /// loop and loop safety information as arguments. It returns changed status.
 231 bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
 232                  TargetLibraryInfo *, Loop *, AliasSetTracker *,
 233                  LICMSafetyInfo *);
 234
 235 /// \brief Try to promote memory values to scalars by sinking stores out of
 236 /// the loop and moving loads to before the loop.  We do this by looping over
 237 /// the stores in the loop, looking for stores to Must pointers which are
 238 /// loop invariant. It takes AliasSet, Loop exit blocks vector, loop exit blocks
 239 /// insertion point vector, PredIteratorCache, LoopInfo, DominatorTree, Loop,
 240 /// AliasSet information for all instructions of the loop and loop safety
 241 /// information as arguments. It returns changed status.
 242 bool promoteLoopAccessesToScalars(AliasSet &, SmallVectorImpl<BasicBlock*> &,
 243                                   SmallVectorImpl<Instruction*> &,
 244                                   PredIteratorCache &, LoopInfo *,
 245                                   DominatorTree *, Loop *, AliasSetTracker *,
 246                                   LICMSafetyInfo *);
 247
 248 /// \brief Computes safety information for a loop
 249 /// checks loop body & header for the possiblity of may throw
 250 /// exception, it takes LICMSafetyInfo and loop as argument.
 251 /// Updates safety information in LICMSafetyInfo argument.
 252 void computeLICMSafetyInfo(LICMSafetyInfo *, Loop *);
 253
 254 /// \brief Checks if the given PHINode in a loop header is an induction
 255 /// variable. Returns true if this is an induction PHI along with the step
 256 /// value.
 257 bool isInductionPHI(PHINode *, ScalarEvolution *, ConstantInt *&);
 258 }
 259
 260 #endif