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

Generated by: LCOV version 1.13