diff options
Diffstat (limited to 'llvm/include/llvm/Transforms/Utils/LoopUtils.h')
| -rw-r--r-- | llvm/include/llvm/Transforms/Utils/LoopUtils.h | 156 |
1 files changed, 121 insertions, 35 deletions
diff --git a/llvm/include/llvm/Transforms/Utils/LoopUtils.h b/llvm/include/llvm/Transforms/Utils/LoopUtils.h index 9ed96809ed998..60446bca53174 100644 --- a/llvm/include/llvm/Transforms/Utils/LoopUtils.h +++ b/llvm/include/llvm/Transforms/Utils/LoopUtils.h @@ -13,42 +13,44 @@ #ifndef LLVM_TRANSFORMS_UTILS_LOOPUTILS_H #define LLVM_TRANSFORMS_UTILS_LOOPUTILS_H -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/Optional.h" -#include "llvm/ADT/SetVector.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringRef.h" -#include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/DemandedBits.h" -#include "llvm/Analysis/EHPersonalities.h" #include "llvm/Analysis/IVDescriptors.h" -#include "llvm/Analysis/MustExecute.h" #include "llvm/Analysis/TargetTransformInfo.h" -#include "llvm/IR/Dominators.h" -#include "llvm/IR/IRBuilder.h" -#include "llvm/IR/InstrTypes.h" -#include "llvm/IR/Operator.h" -#include "llvm/IR/ValueHandle.h" -#include "llvm/Support/Casting.h" +#include "llvm/Transforms/Utils/ValueMapper.h" namespace llvm { +template <typename T> class DomTreeNodeBase; +using DomTreeNode = DomTreeNodeBase<BasicBlock>; +class AAResults; class AliasSet; class AliasSetTracker; class BasicBlock; -class DataLayout; +class IRBuilderBase; class Loop; class LoopInfo; class MemoryAccess; +class MemorySSA; class MemorySSAUpdater; class OptimizationRemarkEmitter; -class PredicatedScalarEvolution; class PredIteratorCache; class ScalarEvolution; class SCEV; +class SCEVExpander; class TargetLibraryInfo; class TargetTransformInfo; +class LPPassManager; +class Instruction; +struct RuntimeCheckingPtrGroup; +typedef std::pair<const RuntimeCheckingPtrGroup *, + const RuntimeCheckingPtrGroup *> + RuntimePointerCheck; + +template <typename T> class Optional; +template <typename T, unsigned N> class SmallSetVector; +template <typename T, unsigned N> class SmallVector; +template <typename T> class SmallVectorImpl; +template <typename T, unsigned N> class SmallPriorityWorklist; BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA); @@ -73,7 +75,7 @@ bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, /// /// Returns true if any modifications are made. bool formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist, - DominatorTree &DT, LoopInfo &LI, + const DominatorTree &DT, const LoopInfo &LI, ScalarEvolution *SE); /// Put loop into LCSSA form. @@ -88,7 +90,8 @@ bool formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist, /// If ScalarEvolution is passed in, it will be preserved. /// /// Returns true if any modifications are made to the loop. -bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE); +bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI, + ScalarEvolution *SE); /// Put a loop nest into LCSSA form. /// @@ -99,7 +102,7 @@ bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE); /// If ScalarEvolution is passed in, it will be preserved. /// /// Returns true if any modifications are made to the loop. -bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, +bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE); struct SinkAndHoistLICMFlags { @@ -114,11 +117,11 @@ struct SinkAndHoistLICMFlags { /// dominated by the specified block, and that are in the current loop) in /// reverse depth first order w.r.t the DominatorTree. This allows us to visit /// uses before definitions, allowing us to sink a loop body in one pass without -/// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, -/// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all +/// iteration. Takes DomTreeNode, AAResults, LoopInfo, DominatorTree, +/// TargetLibraryInfo, Loop, AliasSet information for all /// instructions of the loop and loop safety information as /// arguments. Diagnostics is emitted via \p ORE. It returns changed status. -bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, +bool sinkRegion(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, TargetTransformInfo *, Loop *, AliasSetTracker *, MemorySSAUpdater *, ICFLoopSafetyInfo *, SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *); @@ -127,11 +130,11 @@ bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, /// dominated by the specified block, and that are in the current loop) in depth /// first order w.r.t the DominatorTree. This allows us to visit definitions /// before uses, allowing us to hoist a loop body in one pass without iteration. -/// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout, +/// Takes DomTreeNode, AAResults, LoopInfo, DominatorTree, /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the /// loop and loop safety information as arguments. Diagnostics is emitted via \p /// ORE. It returns changed status. -bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, +bool hoistRegion(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, Loop *, AliasSetTracker *, MemorySSAUpdater *, ScalarEvolution *, ICFLoopSafetyInfo *, SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *); @@ -143,12 +146,12 @@ bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, /// - The loop needs to have a Preheader /// - A unique dedicated exit block must exist /// -/// This also updates the relevant analysis information in \p DT, \p SE, and \p -/// LI if pointers to those are provided. +/// This also updates the relevant analysis information in \p DT, \p SE, \p LI +/// and \p MSSA if pointers to those are provided. /// It also updates the loop PM if an updater struct is provided. void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, - LoopInfo *LI); + LoopInfo *LI, MemorySSA *MSSA = nullptr); /// Try to promote memory values to scalars by sinking stores out of /// the loop and moving loads to before the loop. We do this by looping over @@ -261,10 +264,22 @@ TransformationMode hasLICMVersioningTransformation(Loop *L); void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, unsigned V = 0); -/// Get a loop's estimated trip count based on branch weight metadata. +/// Returns a loop's estimated trip count based on branch weight metadata. +/// In addition if \p EstimatedLoopInvocationWeight is not null it is +/// initialized with weight of loop's latch leading to the exit. /// Returns 0 when the count is estimated to be 0, or None when a meaningful /// estimate can not be made. -Optional<unsigned> getLoopEstimatedTripCount(Loop *L); +Optional<unsigned> +getLoopEstimatedTripCount(Loop *L, + unsigned *EstimatedLoopInvocationWeight = nullptr); + +/// Set a loop's branch weight metadata to reflect that loop has \p +/// EstimatedTripCount iterations and \p EstimatedLoopInvocationWeight exits +/// through latch. Returns true if metadata is successfully updated, false +/// otherwise. Note that loop must have a latch block which controls loop exit +/// in order to succeed. +bool setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount, + unsigned EstimatedLoopInvocationWeight); /// Check inner loop (L) backedge count is known to be invariant on all /// iterations of its outer loop. If the loop has no parent, this is trivially @@ -294,20 +309,20 @@ bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, OptimizationRemarkEmitter *ORE = nullptr); /// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind. -Value *createMinMaxOp(IRBuilder<> &Builder, +Value *createMinMaxOp(IRBuilderBase &Builder, RecurrenceDescriptor::MinMaxRecurrenceKind RK, Value *Left, Value *Right); /// Generates an ordered vector reduction using extracts to reduce the value. Value * -getOrderedReduction(IRBuilder<> &Builder, Value *Acc, Value *Src, unsigned Op, +getOrderedReduction(IRBuilderBase &Builder, Value *Acc, Value *Src, unsigned Op, RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind = RecurrenceDescriptor::MRK_Invalid, ArrayRef<Value *> RedOps = None); /// Generates a vector reduction using shufflevectors to reduce the value. /// Fast-math-flags are propagated using the IRBuilder's setting. -Value *getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op, +Value *getShuffleReduction(IRBuilderBase &Builder, Value *Src, unsigned Op, RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind = RecurrenceDescriptor::MRK_Invalid, ArrayRef<Value *> RedOps = None); @@ -318,7 +333,7 @@ Value *getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op, /// The target is queried to determine if intrinsics or shuffle sequences are /// required to implement the reduction. /// Fast-math-flags are propagated using the IRBuilder's setting. -Value *createSimpleTargetReduction(IRBuilder<> &B, +Value *createSimpleTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI, unsigned Opcode, Value *Src, TargetTransformInfo::ReductionFlags Flags = @@ -329,7 +344,7 @@ Value *createSimpleTargetReduction(IRBuilder<> &B, /// The target is queried to determine if intrinsics or shuffle sequences are /// required to implement the reduction. /// Fast-math-flags are propagated using the RecurrenceDescriptor. -Value *createTargetReduction(IRBuilder<> &B, const TargetTransformInfo *TTI, +Value *createTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI, RecurrenceDescriptor &Desc, Value *Src, bool NoNaN = false); @@ -357,6 +372,77 @@ bool cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, bool cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, bool Signed); +enum ReplaceExitVal { NeverRepl, OnlyCheapRepl, NoHardUse, AlwaysRepl }; + +/// If the final value of any expressions that are recurrent in the loop can +/// be computed, substitute the exit values from the loop into any instructions +/// outside of the loop that use the final values of the current expressions. +/// Return the number of loop exit values that have been replaced, and the +/// corresponding phi node will be added to DeadInsts. +int rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI, + ScalarEvolution *SE, const TargetTransformInfo *TTI, + SCEVExpander &Rewriter, DominatorTree *DT, + ReplaceExitVal ReplaceExitValue, + SmallVector<WeakTrackingVH, 16> &DeadInsts); + +/// Set weights for \p UnrolledLoop and \p RemainderLoop based on weights for +/// \p OrigLoop and the following distribution of \p OrigLoop iteration among \p +/// UnrolledLoop and \p RemainderLoop. \p UnrolledLoop receives weights that +/// reflect TC/UF iterations, and \p RemainderLoop receives weights that reflect +/// the remaining TC%UF iterations. +/// +/// Note that \p OrigLoop may be equal to either \p UnrolledLoop or \p +/// RemainderLoop in which case weights for \p OrigLoop are updated accordingly. +/// Note also behavior is undefined if \p UnrolledLoop and \p RemainderLoop are +/// equal. \p UF must be greater than zero. +/// If \p OrigLoop has no profile info associated nothing happens. +/// +/// This utility may be useful for such optimizations as unroller and +/// vectorizer as it's typical transformation for them. +void setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop, + Loop *RemainderLoop, uint64_t UF); + +/// Utility that implements appending of loops onto a worklist given a range. +/// We want to process loops in postorder, but the worklist is a LIFO data +/// structure, so we append to it in *reverse* postorder. +/// For trees, a preorder traversal is a viable reverse postorder, so we +/// actually append using a preorder walk algorithm. +template <typename RangeT> +void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist<Loop *, 4> &); +/// Utility that implements appending of loops onto a worklist given a range. +/// It has the same behavior as appendLoopsToWorklist, but assumes the range of +/// loops has already been reversed, so it processes loops in the given order. +template <typename RangeT> +void appendReversedLoopsToWorklist(RangeT &&, + SmallPriorityWorklist<Loop *, 4> &); + +/// Utility that implements appending of loops onto a worklist given LoopInfo. +/// Calls the templated utility taking a Range of loops, handing it the Loops +/// in LoopInfo, iterated in reverse. This is because the loops are stored in +/// RPO w.r.t. the control flow graph in LoopInfo. For the purpose of unrolling, +/// loop deletion, and LICM, we largely want to work forward across the CFG so +/// that we visit defs before uses and can propagate simplifications from one +/// loop nest into the next. Calls appendReversedLoopsToWorklist with the +/// already reversed loops in LI. +/// FIXME: Consider changing the order in LoopInfo. +void appendLoopsToWorklist(LoopInfo &, SmallPriorityWorklist<Loop *, 4> &); + +/// Recursively clone the specified loop and all of its children, +/// mapping the blocks with the specified map. +Loop *cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, + LoopInfo *LI, LPPassManager *LPM); + +/// Add code that checks at runtime if the accessed arrays in \p PointerChecks +/// overlap. +/// +/// Returns a pair of instructions where the first element is the first +/// instruction generated in possibly a sequence of instructions and the +/// second value is the final comparator value or NULL if no check is needed. +std::pair<Instruction *, Instruction *> +addRuntimeChecks(Instruction *Loc, Loop *TheLoop, + const SmallVectorImpl<RuntimePointerCheck> &PointerChecks, + ScalarEvolution *SE); + } // end namespace llvm #endif // LLVM_TRANSFORMS_UTILS_LOOPUTILS_H |