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

Generated by: LCOV version 1.13