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