LCOV - code coverage report
Current view: top level - include/llvm/Transforms/Utils - LoopUtils.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 21 21 100.0 %
Date: 2017-09-14 15:23:50 Functions: 4 5 80.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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/DenseMap.h"
      18             : #include "llvm/ADT/Optional.h"
      19             : #include "llvm/ADT/SetVector.h"
      20             : #include "llvm/ADT/SmallPtrSet.h"
      21             : #include "llvm/ADT/SmallVector.h"
      22             : #include "llvm/ADT/StringRef.h"
      23             : #include "llvm/Analysis/AliasAnalysis.h"
      24             : #include "llvm/Analysis/EHPersonalities.h"
      25             : #include "llvm/Analysis/TargetTransformInfo.h"
      26             : #include "llvm/IR/Dominators.h"
      27             : #include "llvm/IR/IRBuilder.h"
      28             : #include "llvm/IR/InstrTypes.h"
      29             : #include "llvm/IR/Operator.h"
      30             : #include "llvm/IR/ValueHandle.h"
      31             : #include "llvm/Support/Casting.h"
      32             : 
      33             : namespace llvm {
      34             : 
      35             : class AliasSet;
      36             : class AliasSetTracker;
      37             : class BasicBlock;
      38             : class DataLayout;
      39             : class Loop;
      40             : class LoopInfo;
      41             : class OptimizationRemarkEmitter;
      42             : class PredicatedScalarEvolution;
      43             : class PredIteratorCache;
      44             : class ScalarEvolution;
      45             : class SCEV;
      46             : class TargetLibraryInfo;
      47             : class TargetTransformInfo;
      48             : 
      49             : /// \brief Captures loop safety information.
      50             : /// It keep information for loop & its header may throw exception.
      51       22106 : struct LoopSafetyInfo {
      52             :   bool MayThrow = false;       // The current loop contains an instruction which
      53             :                                // may throw.
      54             :   bool HeaderMayThrow = false; // Same as previous, but specific to loop header
      55             :   // Used to update funclet bundle operands.
      56             :   DenseMap<BasicBlock *, ColorVector> BlockColors;
      57             : 
      58       22106 :   LoopSafetyInfo() = default;
      59             : };
      60             : 
      61             : /// The RecurrenceDescriptor is used to identify recurrences variables in a
      62             : /// loop. Reduction is a special case of recurrence that has uses of the
      63             : /// recurrence variable outside the loop. The method isReductionPHI identifies
      64             : /// reductions that are basic recurrences.
      65             : ///
      66             : /// Basic recurrences are defined as the summation, product, OR, AND, XOR, min,
      67             : /// or max of a set of terms. For example: for(i=0; i<n; i++) { total +=
      68             : /// array[i]; } is a summation of array elements. Basic recurrences are a
      69             : /// special case of chains of recurrences (CR). See ScalarEvolution for CR
      70             : /// references.
      71             : 
      72             : /// This struct holds information about recurrence variables.
      73       11523 : class RecurrenceDescriptor {
      74             : public:
      75             :   /// This enum represents the kinds of recurrences that we support.
      76             :   enum RecurrenceKind {
      77             :     RK_NoRecurrence,  ///< Not a recurrence.
      78             :     RK_IntegerAdd,    ///< Sum of integers.
      79             :     RK_IntegerMult,   ///< Product of integers.
      80             :     RK_IntegerOr,     ///< Bitwise or logical OR of numbers.
      81             :     RK_IntegerAnd,    ///< Bitwise or logical AND of numbers.
      82             :     RK_IntegerXor,    ///< Bitwise or logical XOR of numbers.
      83             :     RK_IntegerMinMax, ///< Min/max implemented in terms of select(cmp()).
      84             :     RK_FloatAdd,      ///< Sum of floats.
      85             :     RK_FloatMult,     ///< Product of floats.
      86             :     RK_FloatMinMax    ///< Min/max implemented in terms of select(cmp()).
      87             :   };
      88             : 
      89             :   // This enum represents the kind of minmax recurrence.
      90             :   enum MinMaxRecurrenceKind {
      91             :     MRK_Invalid,
      92             :     MRK_UIntMin,
      93             :     MRK_UIntMax,
      94             :     MRK_SIntMin,
      95             :     MRK_SIntMax,
      96             :     MRK_FloatMin,
      97             :     MRK_FloatMax
      98             :   };
      99             : 
     100        6945 :   RecurrenceDescriptor() = default;
     101             : 
     102         255 :   RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K,
     103             :                        MinMaxRecurrenceKind MK, Instruction *UAI, Type *RT,
     104             :                        bool Signed, SmallPtrSetImpl<Instruction *> &CI)
     105         255 :       : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK),
     106         765 :         UnsafeAlgebraInst(UAI), RecurrenceType(RT), IsSigned(Signed) {
     107         255 :     CastInsts.insert(CI.begin(), CI.end());
     108         255 :   }
     109             : 
     110             :   /// This POD struct holds information about a potential recurrence operation.
     111             :   class InstDesc {
     112             :   public:
     113             :     InstDesc(bool IsRecur, Instruction *I, Instruction *UAI = nullptr)
     114       49400 :         : IsRecurrence(IsRecur), PatternLastInst(I), MinMaxKind(MRK_Invalid),
     115       49400 :           UnsafeAlgebraInst(UAI) {}
     116             : 
     117             :     InstDesc(Instruction *I, MinMaxRecurrenceKind K, Instruction *UAI = nullptr)
     118         134 :         : IsRecurrence(true), PatternLastInst(I), MinMaxKind(K),
     119         134 :           UnsafeAlgebraInst(UAI) {}
     120             : 
     121             :     bool isRecurrence() { return IsRecurrence; }
     122             : 
     123             :     bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
     124             : 
     125             :     Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
     126             : 
     127             :     MinMaxRecurrenceKind getMinMaxKind() { return MinMaxKind; }
     128             : 
     129             :     Instruction *getPatternInst() { return PatternLastInst; }
     130             : 
     131             :   private:
     132             :     // Is this instruction a recurrence candidate.
     133             :     bool IsRecurrence;
     134             :     // The last instruction in a min/max pattern (select of the select(icmp())
     135             :     // pattern), or the current recurrence instruction otherwise.
     136             :     Instruction *PatternLastInst;
     137             :     // If this is a min/max pattern the comparison predicate.
     138             :     MinMaxRecurrenceKind MinMaxKind;
     139             :     // Recurrence has unsafe algebra.
     140             :     Instruction *UnsafeAlgebraInst;
     141             :   };
     142             : 
     143             :   /// Returns a struct describing if the instruction 'I' can be a recurrence
     144             :   /// variable of type 'Kind'. If the recurrence is a min/max pattern of
     145             :   /// select(icmp()) this function advances the instruction pointer 'I' from the
     146             :   /// compare instruction to the select instruction and stores this pointer in
     147             :   /// 'PatternLastInst' member of the returned struct.
     148             :   static InstDesc isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
     149             :                                     InstDesc &Prev, bool HasFunNoNaNAttr);
     150             : 
     151             :   /// Returns true if instruction I has multiple uses in Insts
     152             :   static bool hasMultipleUsesOf(Instruction *I,
     153             :                                 SmallPtrSetImpl<Instruction *> &Insts);
     154             : 
     155             :   /// Returns true if all uses of the instruction I is within the Set.
     156             :   static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set);
     157             : 
     158             :   /// Returns a struct describing if the instruction if the instruction is a
     159             :   /// Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y)
     160             :   /// or max(X, Y).
     161             :   static InstDesc isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev);
     162             : 
     163             :   /// Returns identity corresponding to the RecurrenceKind.
     164             :   static Constant *getRecurrenceIdentity(RecurrenceKind K, Type *Tp);
     165             : 
     166             :   /// Returns the opcode of binary operation corresponding to the
     167             :   /// RecurrenceKind.
     168             :   static unsigned getRecurrenceBinOp(RecurrenceKind Kind);
     169             : 
     170             :   /// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
     171             :   static Value *createMinMaxOp(IRBuilder<> &Builder, MinMaxRecurrenceKind RK,
     172             :                                Value *Left, Value *Right);
     173             : 
     174             :   /// Returns true if Phi is a reduction of type Kind and adds it to the
     175             :   /// RecurrenceDescriptor.
     176             :   static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop,
     177             :                               bool HasFunNoNaNAttr,
     178             :                               RecurrenceDescriptor &RedDes);
     179             : 
     180             :   /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor is
     181             :   /// returned in RedDes.
     182             :   static bool isReductionPHI(PHINode *Phi, Loop *TheLoop,
     183             :                              RecurrenceDescriptor &RedDes);
     184             : 
     185             :   /// Returns true if Phi is a first-order recurrence. A first-order recurrence
     186             :   /// is a non-reduction recurrence relation in which the value of the
     187             :   /// recurrence in the current loop iteration equals a value defined in the
     188             :   /// previous iteration. \p SinkAfter includes pairs of instructions where the
     189             :   /// first will be rescheduled to appear after the second if/when the loop is
     190             :   /// vectorized. It may be augmented with additional pairs if needed in order
     191             :   /// to handle Phi as a first-order recurrence.
     192             :   static bool
     193             :   isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop,
     194             :                          DenseMap<Instruction *, Instruction *> &SinkAfter,
     195             :                          DominatorTree *DT);
     196             : 
     197             :   RecurrenceKind getRecurrenceKind() { return Kind; }
     198             : 
     199             :   MinMaxRecurrenceKind getMinMaxRecurrenceKind() { return MinMaxKind; }
     200             : 
     201         358 :   TrackingVH<Value> getRecurrenceStartValue() { return StartValue; }
     202             : 
     203             :   Instruction *getLoopExitInstr() { return LoopExitInstr; }
     204             : 
     205             :   /// Returns true if the recurrence has unsafe algebra which requires a relaxed
     206             :   /// floating-point model.
     207             :   bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
     208             : 
     209             :   /// Returns first unsafe algebra instruction in the PHI node's use-chain.
     210             :   Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
     211             : 
     212             :   /// Returns true if the recurrence kind is an integer kind.
     213             :   static bool isIntegerRecurrenceKind(RecurrenceKind Kind);
     214             : 
     215             :   /// Returns true if the recurrence kind is a floating point kind.
     216             :   static bool isFloatingPointRecurrenceKind(RecurrenceKind Kind);
     217             : 
     218             :   /// Returns true if the recurrence kind is an arithmetic kind.
     219             :   static bool isArithmeticRecurrenceKind(RecurrenceKind Kind);
     220             : 
     221             :   /// Determines if Phi may have been type-promoted. If Phi has a single user
     222             :   /// that ANDs the Phi with a type mask, return the user. RT is updated to
     223             :   /// account for the narrower bit width represented by the mask, and the AND
     224             :   /// instruction is added to CI.
     225             :   static Instruction *lookThroughAnd(PHINode *Phi, Type *&RT,
     226             :                                      SmallPtrSetImpl<Instruction *> &Visited,
     227             :                                      SmallPtrSetImpl<Instruction *> &CI);
     228             : 
     229             :   /// Returns true if all the source operands of a recurrence are either
     230             :   /// SExtInsts or ZExtInsts. This function is intended to be used with
     231             :   /// lookThroughAnd to determine if the recurrence has been type-promoted. The
     232             :   /// source operands are added to CI, and IsSigned is updated to indicate if
     233             :   /// all source operands are SExtInsts.
     234             :   static bool getSourceExtensionKind(Instruction *Start, Instruction *Exit,
     235             :                                      Type *RT, bool &IsSigned,
     236             :                                      SmallPtrSetImpl<Instruction *> &Visited,
     237             :                                      SmallPtrSetImpl<Instruction *> &CI);
     238             : 
     239             :   /// Returns the type of the recurrence. This type can be narrower than the
     240             :   /// actual type of the Phi if the recurrence has been type-promoted.
     241             :   Type *getRecurrenceType() { return RecurrenceType; }
     242             : 
     243             :   /// Returns a reference to the instructions used for type-promoting the
     244             :   /// recurrence.
     245             :   SmallPtrSet<Instruction *, 8> &getCastInsts() { return CastInsts; }
     246             : 
     247             :   /// Returns true if all source operands of the recurrence are SExtInsts.
     248             :   bool isSigned() { return IsSigned; }
     249             : 
     250             : private:
     251             :   // The starting value of the recurrence.
     252             :   // It does not have to be zero!
     253             :   TrackingVH<Value> StartValue;
     254             :   // The instruction who's value is used outside the loop.
     255             :   Instruction *LoopExitInstr = nullptr;
     256             :   // The kind of the recurrence.
     257             :   RecurrenceKind Kind = RK_NoRecurrence;
     258             :   // If this a min/max recurrence the kind of recurrence.
     259             :   MinMaxRecurrenceKind MinMaxKind = MRK_Invalid;
     260             :   // First occurrence of unasfe algebra in the PHI's use-chain.
     261             :   Instruction *UnsafeAlgebraInst = nullptr;
     262             :   // The type of the recurrence.
     263             :   Type *RecurrenceType = nullptr;
     264             :   // True if all source operands of the recurrence are SExtInsts.
     265             :   bool IsSigned = false;
     266             :   // Instructions used for type-promoting the recurrence.
     267             :   SmallPtrSet<Instruction *, 8> CastInsts;
     268             : };
     269             : 
     270             : /// A struct for saving information about induction variables.
     271       42308 : class InductionDescriptor {
     272             : public:
     273             :   /// This enum represents the kinds of inductions that we support.
     274             :   enum InductionKind {
     275             :     IK_NoInduction,  ///< Not an induction variable.
     276             :     IK_IntInduction, ///< Integer induction variable. Step = C.
     277             :     IK_PtrInduction, ///< Pointer induction var. Step = C / sizeof(elem).
     278             :     IK_FpInduction   ///< Floating point induction variable.
     279             :   };
     280             : 
     281             : public:
     282             :   /// Default constructor - creates an invalid induction.
     283        7498 :   InductionDescriptor() = default;
     284             : 
     285             :   /// Get the consecutive direction. Returns:
     286             :   ///   0 - unknown or non-consecutive.
     287             :   ///   1 - consecutive and increasing.
     288             :   ///  -1 - consecutive and decreasing.
     289             :   int getConsecutiveDirection() const;
     290             : 
     291             :   /// Compute the transformed value of Index at offset StartValue using step
     292             :   /// StepValue.
     293             :   /// For integer induction, returns StartValue + Index * StepValue.
     294             :   /// For pointer induction, returns StartValue[Index * StepValue].
     295             :   /// FIXME: The newly created binary instructions should contain nsw/nuw
     296             :   /// flags, which can be found from the original scalar operations.
     297             :   Value *transform(IRBuilder<> &B, Value *Index, ScalarEvolution *SE,
     298             :                    const DataLayout& DL) const;
     299             : 
     300        6560 :   Value *getStartValue() const { return StartValue; }
     301             :   InductionKind getKind() const { return IK; }
     302             :   const SCEV *getStep() const { return Step; }
     303             :   ConstantInt *getConstIntStepValue() const;
     304             : 
     305             :   /// Returns true if \p Phi is an induction in the loop \p L. If \p Phi is an
     306             :   /// induction, the induction descriptor \p D will contain the data describing
     307             :   /// this induction. If by some other means the caller has a better SCEV
     308             :   /// expression for \p Phi than the one returned by the ScalarEvolution
     309             :   /// analysis, it can be passed through \p Expr.
     310             :   static bool isInductionPHI(PHINode *Phi, const Loop* L, ScalarEvolution *SE,
     311             :                              InductionDescriptor &D,
     312             :                              const SCEV *Expr = nullptr);
     313             : 
     314             :   /// Returns true if \p Phi is a floating point induction in the loop \p L.
     315             :   /// If \p Phi is an induction, the induction descriptor \p D will contain 
     316             :   /// the data describing this induction.
     317             :   static bool isFPInductionPHI(PHINode *Phi, const Loop* L,
     318             :                                ScalarEvolution *SE, InductionDescriptor &D);
     319             : 
     320             :   /// Returns true if \p Phi is a loop \p L induction, in the context associated
     321             :   /// with the run-time predicate of PSE. If \p Assume is true, this can add
     322             :   /// further SCEV predicates to \p PSE in order to prove that \p Phi is an
     323             :   /// induction.
     324             :   /// If \p Phi is an induction, \p D will contain the data describing this
     325             :   /// induction.
     326             :   static bool isInductionPHI(PHINode *Phi, const Loop* L,
     327             :                              PredicatedScalarEvolution &PSE,
     328             :                              InductionDescriptor &D, bool Assume = false);
     329             : 
     330             :   /// Returns true if the induction type is FP and the binary operator does
     331             :   /// not have the "fast-math" property. Such operation requires a relaxed FP
     332             :   /// mode.
     333             :   bool hasUnsafeAlgebra() {
     334        1552 :     return InductionBinOp &&
     335          84 :       !cast<FPMathOperator>(InductionBinOp)->hasUnsafeAlgebra();
     336             :   }
     337             : 
     338             :   /// Returns induction operator that does not have "fast-math" property
     339             :   /// and requires FP unsafe mode.
     340             :   Instruction *getUnsafeAlgebraInst() {
     341             :     if (!InductionBinOp ||
     342           4 :         cast<FPMathOperator>(InductionBinOp)->hasUnsafeAlgebra())
     343             :       return nullptr;
     344             :     return InductionBinOp;
     345             :   }
     346             : 
     347             :   /// Returns binary opcode of the induction operator.
     348             :   Instruction::BinaryOps getInductionOpcode() const {
     349        1295 :     return InductionBinOp ? InductionBinOp->getOpcode() :
     350             :       Instruction::BinaryOpsEnd;
     351             :   }
     352             : 
     353             : private:
     354             :   /// Private constructor - used by \c isInductionPHI.
     355             :   InductionDescriptor(Value *Start, InductionKind K, const SCEV *Step,
     356             :                       BinaryOperator *InductionBinOp = nullptr);
     357             : 
     358             :   /// Start value.
     359             :   TrackingVH<Value> StartValue;
     360             :   /// Induction kind.
     361             :   InductionKind IK = IK_NoInduction;
     362             :   /// Step value.
     363             :   const SCEV *Step = nullptr;
     364             :   // Instruction that advances induction variable.
     365             :   BinaryOperator *InductionBinOp = nullptr;
     366             : };
     367             : 
     368             : BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,
     369             :                                    bool PreserveLCSSA);
     370             : 
     371             : /// Ensure that all exit blocks of the loop are dedicated exits.
     372             : ///
     373             : /// For any loop exit block with non-loop predecessors, we split the loop
     374             : /// predecessors to use a dedicated loop exit block. We update the dominator
     375             : /// tree and loop info if provided, and will preserve LCSSA if requested.
     376             : bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
     377             :                              bool PreserveLCSSA);
     378             : 
     379             : /// Ensures LCSSA form for every instruction from the Worklist in the scope of
     380             : /// innermost containing loop.
     381             : ///
     382             : /// For the given instruction which have uses outside of the loop, an LCSSA PHI
     383             : /// node is inserted and the uses outside the loop are rewritten to use this
     384             : /// node.
     385             : ///
     386             : /// LoopInfo and DominatorTree are required and, since the routine makes no
     387             : /// changes to CFG, preserved.
     388             : ///
     389             : /// Returns true if any modifications are made.
     390             : bool formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist,
     391             :                               DominatorTree &DT, LoopInfo &LI);
     392             : 
     393             : /// \brief Put loop into LCSSA form.
     394             : ///
     395             : /// Looks at all instructions in the loop which have uses outside of the
     396             : /// current loop. For each, an LCSSA PHI node is inserted and the uses outside
     397             : /// the loop are rewritten to use this node.
     398             : ///
     399             : /// LoopInfo and DominatorTree are required and preserved.
     400             : ///
     401             : /// If ScalarEvolution is passed in, it will be preserved.
     402             : ///
     403             : /// Returns true if any modifications are made to the loop.
     404             : bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE);
     405             : 
     406             : /// \brief Put a loop nest into LCSSA form.
     407             : ///
     408             : /// This recursively forms LCSSA for a loop nest.
     409             : ///
     410             : /// LoopInfo and DominatorTree are required and preserved.
     411             : ///
     412             : /// If ScalarEvolution is passed in, it will be preserved.
     413             : ///
     414             : /// Returns true if any modifications are made to the loop.
     415             : bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI,
     416             :                           ScalarEvolution *SE);
     417             : 
     418             : /// \brief Walk the specified region of the CFG (defined by all blocks
     419             : /// dominated by the specified block, and that are in the current loop) in
     420             : /// reverse depth first order w.r.t the DominatorTree. This allows us to visit
     421             : /// uses before definitions, allowing us to sink a loop body in one pass without
     422             : /// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree,
     423             : /// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all
     424             : /// instructions of the loop and loop safety information as
     425             : /// arguments. Diagnostics is emitted via \p ORE. It returns changed status.
     426             : bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
     427             :                 TargetLibraryInfo *, Loop *, AliasSetTracker *,
     428             :                 LoopSafetyInfo *, OptimizationRemarkEmitter *ORE);
     429             : 
     430             : /// \brief Walk the specified region of the CFG (defined by all blocks
     431             : /// dominated by the specified block, and that are in the current loop) in depth
     432             : /// first order w.r.t the DominatorTree.  This allows us to visit definitions
     433             : /// before uses, allowing us to hoist a loop body in one pass without iteration.
     434             : /// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout,
     435             : /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
     436             : /// loop and loop safety information as arguments. Diagnostics is emitted via \p
     437             : /// ORE. It returns changed status.
     438             : bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
     439             :                  TargetLibraryInfo *, Loop *, AliasSetTracker *,
     440             :                  LoopSafetyInfo *, OptimizationRemarkEmitter *ORE);
     441             : 
     442             : /// \brief Try to promote memory values to scalars by sinking stores out of
     443             : /// the loop and moving loads to before the loop.  We do this by looping over
     444             : /// the stores in the loop, looking for stores to Must pointers which are
     445             : /// loop invariant. It takes a set of must-alias values, Loop exit blocks
     446             : /// vector, loop exit blocks insertion point vector, PredIteratorCache,
     447             : /// LoopInfo, DominatorTree, Loop, AliasSet information for all instructions
     448             : /// of the loop and loop safety information as arguments.
     449             : /// Diagnostics is emitted via \p ORE. It returns changed status.
     450             : bool promoteLoopAccessesToScalars(const SmallSetVector<Value *, 8> &,
     451             :                                   SmallVectorImpl<BasicBlock *> &,
     452             :                                   SmallVectorImpl<Instruction *> &,
     453             :                                   PredIteratorCache &, LoopInfo *,
     454             :                                   DominatorTree *, const TargetLibraryInfo *,
     455             :                                   Loop *, AliasSetTracker *, LoopSafetyInfo *,
     456             :                                   OptimizationRemarkEmitter *);
     457             : 
     458             : /// \brief Computes safety information for a loop
     459             : /// checks loop body & header for the possibility of may throw
     460             : /// exception, it takes LoopSafetyInfo and loop as argument.
     461             : /// Updates safety information in LoopSafetyInfo argument.
     462             : void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *);
     463             : 
     464             : /// Returns true if the instruction in a loop is guaranteed to execute at least
     465             : /// once.
     466             : bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT,
     467             :                            const Loop *CurLoop,
     468             :                            const LoopSafetyInfo *SafetyInfo);
     469             : 
     470             : /// \brief Returns the instructions that use values defined in the loop.
     471             : SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L);
     472             : 
     473             : /// \brief Find string metadata for loop
     474             : ///
     475             : /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
     476             : /// operand or null otherwise.  If the string metadata is not found return
     477             : /// Optional's not-a-value.
     478             : Optional<const MDOperand *> findStringMetadataForLoop(Loop *TheLoop,
     479             :                                                       StringRef Name);
     480             : 
     481             : /// \brief Set input string into loop metadata by keeping other values intact.
     482             : void addStringMetadataToLoop(Loop *TheLoop, const char *MDString,
     483             :                              unsigned V = 0);
     484             : 
     485             : /// \brief Get a loop's estimated trip count based on branch weight metadata.
     486             : /// Returns 0 when the count is estimated to be 0, or None when a meaningful
     487             : /// estimate can not be made.
     488             : Optional<unsigned> getLoopEstimatedTripCount(Loop *L);
     489             : 
     490             : /// Helper to consistently add the set of standard passes to a loop pass's \c
     491             : /// AnalysisUsage.
     492             : ///
     493             : /// All loop passes should call this as part of implementing their \c
     494             : /// getAnalysisUsage.
     495             : void getLoopAnalysisUsage(AnalysisUsage &AU);
     496             : 
     497             : /// Returns true if the hoister and sinker can handle this instruction.
     498             : /// If SafetyInfo is null, we are checking for sinking instructions from
     499             : /// preheader to loop body (no speculation).
     500             : /// If SafetyInfo is not null, we are checking for hoisting/sinking
     501             : /// instructions from loop body to preheader/exit. Check if the instruction
     502             : /// can execute speculatively.
     503             : /// If \p ORE is set use it to emit optimization remarks.
     504             : bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
     505             :                         Loop *CurLoop, AliasSetTracker *CurAST,
     506             :                         LoopSafetyInfo *SafetyInfo,
     507             :                         OptimizationRemarkEmitter *ORE = nullptr);
     508             : 
     509             : /// Generates a vector reduction using shufflevectors to reduce the value.
     510             : Value *getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op,
     511             :                            RecurrenceDescriptor::MinMaxRecurrenceKind
     512             :                                MinMaxKind = RecurrenceDescriptor::MRK_Invalid,
     513             :                            ArrayRef<Value *> RedOps = ArrayRef<Value *>());
     514             : 
     515             : /// Create a target reduction of the given vector. The reduction operation
     516             : /// is described by the \p Opcode parameter. min/max reductions require
     517             : /// additional information supplied in \p Flags.
     518             : /// The target is queried to determine if intrinsics or shuffle sequences are
     519             : /// required to implement the reduction.
     520             : Value *
     521             : createSimpleTargetReduction(IRBuilder<> &B, const TargetTransformInfo *TTI,
     522             :                             unsigned Opcode, Value *Src,
     523             :                             TargetTransformInfo::ReductionFlags Flags =
     524             :                                 TargetTransformInfo::ReductionFlags(),
     525             :                             ArrayRef<Value *> RedOps = ArrayRef<Value *>());
     526             : 
     527             : /// Create a generic target reduction using a recurrence descriptor \p Desc
     528             : /// The target is queried to determine if intrinsics or shuffle sequences are
     529             : /// required to implement the reduction.
     530             : Value *createTargetReduction(IRBuilder<> &B, const TargetTransformInfo *TTI,
     531             :                              RecurrenceDescriptor &Desc, Value *Src,
     532             :                              bool NoNaN = false);
     533             : 
     534             : /// Get the intersection (logical and) of all of the potential IR flags
     535             : /// of each scalar operation (VL) that will be converted into a vector (I).
     536             : /// If OpValue is non-null, we only consider operations similar to OpValue
     537             : /// when intersecting.
     538             : /// Flag set: NSW, NUW, exact, and all of fast-math.
     539             : void propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue = nullptr);
     540             : 
     541             : } // end namespace llvm
     542             : 
     543             : #endif // LLVM_TRANSFORMS_UTILS_LOOPUTILS_H

Generated by: LCOV version 1.13