Go to the documentation of this file.
13 #ifndef LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
14 #define LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
22 template <
typename T>
class DomTreeNodeBase;
26 class TargetTransformInfo;
29 class BlockFrequencyInfo;
30 class ICFLoopSafetyInfo;
36 class MemorySSAUpdater;
37 class OptimizationRemarkEmitter;
38 class PredIteratorCache;
39 class ScalarEvolution;
42 class TargetLibraryInfo;
45 struct RuntimeCheckingPtrGroup;
46 typedef std::pair<
const RuntimeCheckingPtrGroup *,
47 const RuntimeCheckingPtrGroup *>
50 template <
typename T>
class Optional;
51 template <
typename T,
unsigned N>
class SmallSetVector;
52 template <
typename T,
unsigned N>
class SmallPriorityWorklist;
55 MemorySSAUpdater *MSSAU,
bool PreserveLCSSA);
63 MemorySSAUpdater *MSSAU,
bool PreserveLCSSA);
81 SmallVectorImpl<Instruction *> &Worklist,
const DominatorTree &DT,
82 const LoopInfo &LI, ScalarEvolution *SE, IRBuilderBase &
Builder,
83 SmallVectorImpl<PHINode *> *PHIsToRemove =
nullptr);
97 bool formLCSSA(Loop &L,
const DominatorTree &DT,
const LoopInfo *LI,
110 ScalarEvolution *SE);
178 bool AllowSpeculation);
220 const Loop *CurLoop);
258 const char *InheritOptionsAttrsPrefix =
"",
259 bool AlwaysNew =
false);
316 unsigned *EstimatedLoopInvocationWeight =
nullptr);
324 unsigned EstimatedLoopInvocationWeight);
348 Loop *CurLoop, MemorySSAUpdater &MSSAU,
349 bool TargetExecutesOncePerLoop,
350 SinkAndHoistLICMFlags &LICMFlags,
351 OptimizationRemarkEmitter *ORE =
nullptr);
386 const TargetTransformInfo *
TTI,
Value *Src,
393 const TargetTransformInfo *
TTI,
395 const RecurrenceDescriptor &Desc,
403 const RecurrenceDescriptor &Desc,
Value *Src,
404 PHINode *OrigPhi =
nullptr);
409 const RecurrenceDescriptor &Desc,
Value *Src,
419 bool IncludeWrapFlags =
true);
428 ScalarEvolution &SE);
446 ScalarEvolution *SE,
const TargetTransformInfo *
TTI,
447 SCEVExpander &
Rewriter, DominatorTree *DT,
449 SmallVector<WeakTrackingVH, 16> &DeadInsts);
473 template <
typename RangeT>
478 template <
typename RangeT>
480 SmallPriorityWorklist<Loop *, 4> &);
496 LoopInfo *LI, LPPassManager *LPM);
502 const SmallVectorImpl<RuntimePointerCheck> &PointerChecks,
503 SCEVExpander &Expander);
507 ArrayRef<PointerDiffInfo> Checks, SCEVExpander &Expander,
508 function_ref<
Value *(IRBuilderBase &,
unsigned)> GetVF,
545 #endif // LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put loop into LCSSA form.
TransformationMode hasUnrollTransformation(const Loop *L)
int rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI, ScalarEvolution *SE, const TargetTransformInfo *TTI, SCEVExpander &Rewriter, DominatorTree *DT, ReplaceExitVal ReplaceExitValue, SmallVector< WeakTrackingVH, 16 > &DeadInsts)
If the final value of any expressions that are recurrent in the loop can be computed,...
This is an optimization pass for GlobalISel generic memory operations.
std::pair< const RuntimeCheckingPtrGroup *, const RuntimeCheckingPtrGroup * > RuntimePointerCheck
A memcheck which made up of a pair of grouped pointers.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Value * getShuffleReduction(IRBuilderBase &Builder, Value *Src, unsigned Op, RecurKind MinMaxKind=RecurKind::None)
Generates a vector reduction using shufflevectors to reduce the value.
bool hoistRegion(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *, BlockFrequencyInfo *, TargetLibraryInfo *, Loop *, MemorySSAUpdater &, ScalarEvolution *, ICFLoopSafetyInfo *, SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *, bool, bool AllowSpeculation)
Walk the specified region of the CFG (defined by all blocks dominated by the specified block,...
bool hasDisableAllTransformsHint(const Loop *L)
Look for the loop attribute that disables all transformation heuristic.
Represents a single loop in the control flow graph.
PredIteratorCache - This class is an extremely trivial cache for predecessor iterator queries.
void setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop, Loop *RemainderLoop, uint64_t UF)
Set weights for UnrolledLoop and RemainderLoop based on weights for OrigLoop and the following distri...
DomTreeNodeBase< BasicBlock > DomTreeNode
void propagateIRFlags(Value *I, ArrayRef< Value * > VL, Value *OpValue=nullptr, bool IncludeWrapFlags=true)
Get the intersection (logical and) of all of the potential IR flags of each scalar operation (VL) tha...
void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI, MemorySSA *MSSA=nullptr)
This function deletes dead loops.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
The main scalar evolution driver.
BasicBlock * ExitForPath
If the partially invariant path reaches a single exit block, ExitForPath is set to that block.
Optional< MDNode * > makeFollowupLoopID(MDNode *OrigLoopID, ArrayRef< StringRef > FollowupAttrs, const char *InheritOptionsAttrsPrefix="", bool AlwaysNew=false)
Create a new loop identifier for a loop created from a loop transformation.
bool tooManyClobberingCalls()
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
SmallVector< Instruction *, 8 > findDefsUsedOutsideOfLoop(Loop *L)
Returns the instructions that use values defined in the loop.
bool hasDisableLICMTransformsHint(const Loop *L)
Look for the loop attribute that disables the LICM transformation heuristics.
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
Value * createSelectCmpOp(IRBuilderBase &Builder, Value *StartVal, RecurKind RK, Value *Left, Value *Right)
See RecurrenceDescriptor::isSelectCmpPattern for a description of the pattern we are trying to match.
unsigned LicmMssaNoAccForPromotionCap
void incrementClobberingCalls()
bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, Loop *CurLoop, MemorySSAUpdater &MSSAU, bool TargetExecutesOncePerLoop, SinkAndHoistLICMFlags &LICMFlags, OptimizationRemarkEmitter *ORE=nullptr)
Returns true if is legal to hoist or sink this instruction disregarding the possible introduction of ...
CmpInst::Predicate getMinMaxReductionPredicate(RecurKind RK)
Returns the comparison predicate used when expanding a min/max reduction.
Value * createSimpleTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI, Value *Src, RecurKind RdxKind)
Create a target reduction of the given vector.
bool sinkRegionForLoopNest(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *, BlockFrequencyInfo *, TargetLibraryInfo *, TargetTransformInfo *, Loop *, MemorySSAUpdater &, ICFLoopSafetyInfo *, SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *)
Call sinkRegion on loops contained within the specified loop in order from innermost to outermost.
LLVM Basic Block Representation.
RecurKind
These are the kinds of recurrences that we support.
@ TM_Enable
The transformation should be applied without considering a cost model.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
TransformationMode hasDistributeTransformation(const Loop *L)
Virtual Register Rewriter
Value * getOrderedReduction(IRBuilderBase &Builder, Value *Acc, Value *Src, unsigned Op, RecurKind MinMaxKind=RecurKind::None)
Generates an ordered vector reduction using extracts to reduce the value.
SinkAndHoistLICMFlags(unsigned LicmMssaOptCap, unsigned LicmMssaNoAccForPromotionCap, bool IsSink, Loop *L=nullptr, MemorySSA *MSSA=nullptr)
bool isKnownNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)
Returns true if we can prove that S is defined and always negative in loop L.
Flags controlling how much is checked when sinking or hoisting instructions.
bool promoteLoopAccessesToScalars(const SmallSetVector< Value *, 8 > &, SmallVectorImpl< BasicBlock * > &, SmallVectorImpl< Instruction * > &, SmallVectorImpl< MemoryAccess * > &, PredIteratorCache &, LoopInfo *, DominatorTree *, const TargetLibraryInfo *, Loop *, MemorySSAUpdater &, ICFLoopSafetyInfo *, OptimizationRemarkEmitter *, bool AllowSpeculation)
Try to promote memory values to scalars by sinking stores out of the loop and moving loads to before ...
bool cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, bool Signed)
Returns true if S is defined and never is equal to signed/unsigned min.
Loop * cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, LoopInfo *LI, LPPassManager *LPM)
Recursively clone the specified loop and all of its children, mapping the blocks with the specified m...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
@ TM_SuppressedByUser
The transformation must not be applied.
TransformationMode hasLICMVersioningTransformation(const Loop *L)
Value * addRuntimeChecks(Instruction *Loc, Loop *TheLoop, const SmallVectorImpl< RuntimePointerCheck > &PointerChecks, SCEVExpander &Expander)
Add code that checks at runtime if the accessed arrays in PointerChecks overlap.
bool isKnownNonNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)
Returns true if we can prove that S is defined and always non-negative in loop L.
bool PathIsNoop
True if the partially invariant path is no-op (=does not have any side-effects and no loop value is u...
void breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA)
Remove the backedge of the specified loop.
unsigned LicmMssaOptCounter
BasicBlock * InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
InsertPreheaderForLoop - Once we discover that a loop doesn't have a preheader, this method is called...
bool hasIterationCountInvariantInParent(Loop *L, ScalarEvolution &SE)
Check inner loop (L) backedge count is known to be invariant on all iterations of its outer loop.
This is an important base class in LLVM.
TransformationMode hasUnrollAndJamTransformation(const Loop *L)
void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, unsigned V=0)
Set input string into loop metadata by keeping other values intact.
Encapsulates MemorySSA, including all data associated with memory accesses.
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
@ TM_Disable
The transformation should not be applied.
Value * createTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI, const RecurrenceDescriptor &Desc, Value *Src, PHINode *OrigPhi=nullptr)
Create a generic target reduction using a recurrence descriptor Desc The target is queried to determi...
Constant * KnownValue
Constant to indicate for which value the condition is invariant.
bool cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, bool Signed)
Returns true if S is defined and never is equal to signed/unsigned max.
@ TM_Unspecified
The pass can use heuristics to determine whether a transformation should be applied.
@ BasicBlock
Various leaf nodes.
SmallVector< Instruction * > InstToDuplicate
Instructions that need to be duplicated and checked for the unswitching condition.
SmallVector< DomTreeNode *, 16 > collectChildrenInLoop(DomTreeNode *N, const Loop *CurLoop)
Does a BFS from a given node to all of its children inside a given loop.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
@ TM_ForcedByUser
The transformation was directed by the user, e.g.
Optional< ElementCount > getOptionalElementCountLoopAttribute(const Loop *TheLoop)
Find a combination of metadata ("llvm.loop.vectorize.width" and "llvm.loop.vectorize....
void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
bool setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount, unsigned EstimatedLoopInvocationWeight)
Set a loop's branch weight metadata to reflect that loop has EstimatedTripCount iterations and Estima...
@ TM_Force
Force is a flag and should not be used alone.
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Ensure that all exit blocks of the loop are dedicated exits.
static cl::opt< unsigned > MSSAThreshold("simple-loop-unswitch-memoryssa-threshold", cl::desc("Max number of memory uses to explore during " "partial unswitching analysis"), cl::init(100), cl::Hidden)
void appendReversedLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to give precise answers on "may...
Provides information about what library functions are available for the current target.
Struct to hold information about a partially invariant condition.
Optional< IVConditionInfo > hasPartialIVCondition(Loop &L, unsigned MSSAThreshold, MemorySSA &MSSA, AAResults &AA)
Check if the loop header has a conditional branch that is not loop-invariant, because it involves loa...
Value * createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left, Value *Right)
Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
static cl::opt< ReplaceExitVal > ReplaceExitValue("replexitval", cl::Hidden, cl::init(OnlyCheapRepl), cl::desc("Choose the strategy to replace exit value in IndVarSimplify"), cl::values(clEnumValN(NeverRepl, "never", "never replace exit value"), clEnumValN(OnlyCheapRepl, "cheap", "only replace exit value when the cost is cheap"), clEnumValN(NoHardUse, "noharduse", "only replace exit values when loop def likely dead"), clEnumValN(AlwaysRepl, "always", "always replace exit value whenever possible")))
Value * createOrderedReduction(IRBuilderBase &B, const RecurrenceDescriptor &Desc, Value *Src, Value *Start)
Create an ordered reduction intrinsic using the given recurrence descriptor Desc.
bool formLCSSAForInstructions(SmallVectorImpl< Instruction * > &Worklist, const DominatorTree &DT, const LoopInfo &LI, ScalarEvolution *SE, IRBuilderBase &Builder, SmallVectorImpl< PHINode * > *PHIsToRemove=nullptr)
Ensures LCSSA form for every instruction from the Worklist in the scope of innermost containing loop.
TransformationMode hasVectorizeTransformation(const Loop *L)
A SetVector that performs no allocations if smaller than a certain size.
bool tooManyMemoryAccesses()
early cse Early CSE w MemorySSA
Optional< unsigned > getLoopEstimatedTripCount(Loop *L, unsigned *EstimatedLoopInvocationWeight=nullptr)
Returns a loop's estimated trip count based on branch weight metadata.
Value * addDiffRuntimeChecks(Instruction *Loc, Loop *TheLoop, ArrayRef< PointerDiffInfo > Checks, SCEVExpander &Expander, function_ref< Value *(IRBuilderBase &, unsigned)> GetVF, unsigned IC)
TransformationMode
The mode sets how eager a transformation should be applied.
bool sinkRegion(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *, BlockFrequencyInfo *, TargetLibraryInfo *, TargetTransformInfo *, Loop *CurLoop, MemorySSAUpdater &, ICFLoopSafetyInfo *, SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *, Loop *OutermostLoop=nullptr)
Walk the specified region of the CFG (defined by all blocks dominated by the specified block,...
Value * createSelectCmpTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI, Value *Src, const RecurrenceDescriptor &Desc, PHINode *OrigPhi)
Create a target reduction of the given vector Src for a reduction of the kind RecurKind::SelectICmp o...