Home | History | Annotate | Download | only in Utils
      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, DominatorTree *DT, LoopInfo *LI,
    297                                    bool PreserveLCSSA);
    298 
    299 /// \brief Simplify each loop in a loop nest recursively.
    300 ///
    301 /// This takes a potentially un-simplified loop L (and its children) and turns
    302 /// it into a simplified loop nest with preheaders and single backedges. It will
    303 /// update \c AliasAnalysis and \c ScalarEvolution analyses if they're non-null.
    304 bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE,
    305                   AssumptionCache *AC, bool PreserveLCSSA);
    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
    380