LLVM 17.0.0git
LoopUtils.h
Go to the documentation of this file.
1//===- llvm/Transforms/Utils/LoopUtils.h - Loop utilities -------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines some loop transformation utilities.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
14#define LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
15
19
20namespace llvm {
21
22template <typename T> class DomTreeNodeBase;
23using DomTreeNode = DomTreeNodeBase<BasicBlock>;
24class AssumptionCache;
25class StringRef;
26class AnalysisUsage;
27class TargetTransformInfo;
28class AAResults;
29class BasicBlock;
30class ICFLoopSafetyInfo;
31class IRBuilderBase;
32class Loop;
33class LoopInfo;
34class MemoryAccess;
35class MemorySSA;
36class MemorySSAUpdater;
37class OptimizationRemarkEmitter;
38class PredIteratorCache;
39class ScalarEvolution;
40class SCEV;
41class SCEVExpander;
42class TargetLibraryInfo;
43class LPPassManager;
44class Instruction;
45struct RuntimeCheckingPtrGroup;
46typedef std::pair<const RuntimeCheckingPtrGroup *,
47 const RuntimeCheckingPtrGroup *>
49
50template <typename T, unsigned N> class SmallSetVector;
51template <typename T, unsigned N> class SmallPriorityWorklist;
52
53BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,
54 MemorySSAUpdater *MSSAU, bool PreserveLCSSA);
55
56/// Ensure that all exit blocks of the loop are dedicated exits.
57///
58/// For any loop exit block with non-loop predecessors, we split the loop
59/// predecessors to use a dedicated loop exit block. We update the dominator
60/// tree and loop info if provided, and will preserve LCSSA if requested.
61bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
62 MemorySSAUpdater *MSSAU, bool PreserveLCSSA);
63
64/// Ensures LCSSA form for every instruction from the Worklist in the scope of
65/// innermost containing loop.
66///
67/// For the given instruction which have uses outside of the loop, an LCSSA PHI
68/// node is inserted and the uses outside the loop are rewritten to use this
69/// node.
70///
71/// LoopInfo and DominatorTree are required and, since the routine makes no
72/// changes to CFG, preserved.
73///
74/// Returns true if any modifications are made.
75///
76/// This function may introduce unused PHI nodes. If \p PHIsToRemove is not
77/// nullptr, those are added to it (before removing, the caller has to check if
78/// they still do not have any uses). Otherwise the PHIs are directly removed.
80 SmallVectorImpl<Instruction *> &Worklist, const DominatorTree &DT,
81 const LoopInfo &LI, ScalarEvolution *SE, IRBuilderBase &Builder,
82 SmallVectorImpl<PHINode *> *PHIsToRemove = nullptr);
83
84/// Put loop into LCSSA form.
85///
86/// Looks at all instructions in the loop which have uses outside of the
87/// current loop. For each, an LCSSA PHI node is inserted and the uses outside
88/// the loop are rewritten to use this node. Sub-loops must be in LCSSA form
89/// already.
90///
91/// LoopInfo and DominatorTree are required and preserved.
92///
93/// If ScalarEvolution is passed in, it will be preserved.
94///
95/// Returns true if any modifications are made to the loop.
96bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI,
97 ScalarEvolution *SE);
98
99/// Put a loop nest into LCSSA form.
100///
101/// This recursively forms LCSSA for a loop nest.
102///
103/// LoopInfo and DominatorTree are required and preserved.
104///
105/// If ScalarEvolution is passed in, it will be preserved.
106///
107/// Returns true if any modifications are made to the loop.
108bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI,
109 ScalarEvolution *SE);
110
111/// Flags controlling how much is checked when sinking or hoisting
112/// instructions. The number of memory access in the loop (and whether there
113/// are too many) is determined in the constructors when using MemorySSA.
115public:
116 // Explicitly set limits.
119 Loop *L = nullptr, MemorySSA *MSSA = nullptr);
120 // Use default limits.
121 SinkAndHoistLICMFlags(bool IsSink, Loop *L = nullptr,
122 MemorySSA *MSSA = nullptr);
123
124 void setIsSink(bool B) { IsSink = B; }
125 bool getIsSink() { return IsSink; }
129
130protected:
131 bool NoOfMemAccTooLarge = false;
132 unsigned LicmMssaOptCounter = 0;
135 bool IsSink;
136};
137
138/// Walk the specified region of the CFG (defined by all blocks
139/// dominated by the specified block, and that are in the current loop) in
140/// reverse depth first order w.r.t the DominatorTree. This allows us to visit
141/// uses before definitions, allowing us to sink a loop body in one pass without
142/// iteration. Takes DomTreeNode, AAResults, LoopInfo, DominatorTree,
143/// TargetLibraryInfo, Loop, AliasSet information for all
144/// instructions of the loop and loop safety information as
145/// arguments. Diagnostics is emitted via \p ORE. It returns changed status.
146/// \p CurLoop is a loop to do sinking on. \p OutermostLoop is used only when
147/// this function is called by \p sinkRegionForLoopNest.
152 Loop *OutermostLoop = nullptr);
153
154/// Call sinkRegion on loops contained within the specified loop
155/// in order from innermost to outermost.
161
162/// Walk the specified region of the CFG (defined by all blocks
163/// dominated by the specified block, and that are in the current loop) in depth
164/// first order w.r.t the DominatorTree. This allows us to visit definitions
165/// before uses, allowing us to hoist a loop body in one pass without iteration.
166/// Takes DomTreeNode, AAResults, LoopInfo, DominatorTree,
167/// TargetLibraryInfo, Loop, AliasSet information for all
168/// instructions of the loop and loop safety information as arguments.
169/// Diagnostics is emitted via \p ORE. It returns changed status.
170/// \p AllowSpeculation is whether values should be hoisted even if they are not
171/// guaranteed to execute in the loop, but are safe to speculatively execute.
176 bool AllowSpeculation);
177
178/// Return true if the induction variable \p IV in a Loop whose latch is
179/// \p LatchBlock would become dead if the exit test \p Cond were removed.
180/// Conservatively returns false if analysis is insufficient.
181bool isAlmostDeadIV(PHINode *IV, BasicBlock *LatchBlock, Value *Cond);
182
183/// This function deletes dead loops. The caller of this function needs to
184/// guarantee that the loop is infact dead.
185/// The function requires a bunch or prerequisites to be present:
186/// - The loop needs to be in LCSSA form
187/// - The loop needs to have a Preheader
188/// - A unique dedicated exit block must exist
189///
190/// This also updates the relevant analysis information in \p DT, \p SE, \p LI
191/// and \p MSSA if pointers to those are provided.
192/// It also updates the loop PM if an updater struct is provided.
193
195 LoopInfo *LI, MemorySSA *MSSA = nullptr);
196
197/// Remove the backedge of the specified loop. Handles loop nests and general
198/// loop structures subject to the precondition that the loop has no parent
199/// loop and has a single latch block. Preserves all listed analyses.
201 LoopInfo &LI, MemorySSA *MSSA);
202
203/// Try to promote memory values to scalars by sinking stores out of
204/// the loop and moving loads to before the loop. We do this by looping over
205/// the stores in the loop, looking for stores to Must pointers which are
206/// loop invariant. It takes a set of must-alias values, Loop exit blocks
207/// vector, loop exit blocks insertion point vector, PredIteratorCache,
208/// LoopInfo, DominatorTree, Loop, AliasSet information for all instructions
209/// of the loop and loop safety information as arguments.
210/// Diagnostics is emitted via \p ORE. It returns changed status.
211/// \p AllowSpeculation is whether values should be hoisted even if they are not
212/// guaranteed to execute in the loop, but are safe to speculatively execute.
219 bool AllowSpeculation, bool HasReadsOutsideSet);
220
221/// Does a BFS from a given node to all of its children inside a given loop.
222/// The returned vector of nodes includes the starting point.
224 const Loop *CurLoop);
225
226/// Returns the instructions that use values defined in the loop.
228
229/// Find a combination of metadata ("llvm.loop.vectorize.width" and
230/// "llvm.loop.vectorize.scalable.enable") for a loop and use it to construct a
231/// ElementCount. If the metadata "llvm.loop.vectorize.width" cannot be found
232/// then std::nullopt is returned.
233std::optional<ElementCount>
235
236/// Create a new loop identifier for a loop created from a loop transformation.
237///
238/// @param OrigLoopID The loop ID of the loop before the transformation.
239/// @param FollowupAttrs List of attribute names that contain attributes to be
240/// added to the new loop ID.
241/// @param InheritOptionsAttrsPrefix Selects which attributes should be inherited
242/// from the original loop. The following values
243/// are considered:
244/// nullptr : Inherit all attributes from @p OrigLoopID.
245/// "" : Do not inherit any attribute from @p OrigLoopID; only use
246/// those specified by a followup attribute.
247/// "<prefix>": Inherit all attributes except those which start with
248/// <prefix>; commonly used to remove metadata for the
249/// applied transformation.
250/// @param AlwaysNew If true, do not try to reuse OrigLoopID and never return
251/// std::nullopt.
252///
253/// @return The loop ID for the after-transformation loop. The following values
254/// can be returned:
255/// std::nullopt : No followup attribute was found; it is up to the
256/// transformation to choose attributes that make sense.
257/// @p OrigLoopID: The original identifier can be reused.
258/// nullptr : The new loop has no attributes.
259/// MDNode* : A new unique loop identifier.
260std::optional<MDNode *>
261makeFollowupLoopID(MDNode *OrigLoopID, ArrayRef<StringRef> FollowupAttrs,
262 const char *InheritOptionsAttrsPrefix = "",
263 bool AlwaysNew = false);
264
265/// Look for the loop attribute that disables all transformation heuristic.
266bool hasDisableAllTransformsHint(const Loop *L);
267
268/// Look for the loop attribute that disables the LICM transformation heuristics.
270
271/// The mode sets how eager a transformation should be applied.
273 /// The pass can use heuristics to determine whether a transformation should
274 /// be applied.
276
277 /// The transformation should be applied without considering a cost model.
279
280 /// The transformation should not be applied.
282
283 /// Force is a flag and should not be used alone.
284 TM_Force = 0x04,
285
286 /// The transformation was directed by the user, e.g. by a #pragma in
287 /// the source code. If the transformation could not be applied, a
288 /// warning should be emitted.
290
291 /// The transformation must not be applied. For instance, `#pragma clang loop
292 /// unroll(disable)` explicitly forbids any unrolling to take place. Unlike
293 /// general loop metadata, it must not be dropped. Most passes should not
294 /// behave differently under TM_Disable and TM_SuppressedByUser.
297
298/// @{
299/// Get the mode for LLVM's supported loop transformations.
305/// @}
306
307/// Set input string into loop metadata by keeping other values intact.
308/// If the string is already in loop metadata update value if it is
309/// different.
310void addStringMetadataToLoop(Loop *TheLoop, const char *MDString,
311 unsigned V = 0);
312
313/// Returns a loop's estimated trip count based on branch weight metadata.
314/// In addition if \p EstimatedLoopInvocationWeight is not null it is
315/// initialized with weight of loop's latch leading to the exit.
316/// Returns 0 when the count is estimated to be 0, or std::nullopt when a
317/// meaningful estimate can not be made.
318std::optional<unsigned>
320 unsigned *EstimatedLoopInvocationWeight = nullptr);
321
322/// Set a loop's branch weight metadata to reflect that loop has \p
323/// EstimatedTripCount iterations and \p EstimatedLoopInvocationWeight exits
324/// through latch. Returns true if metadata is successfully updated, false
325/// otherwise. Note that loop must have a latch block which controls loop exit
326/// in order to succeed.
327bool setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount,
328 unsigned EstimatedLoopInvocationWeight);
329
330/// Check inner loop (L) backedge count is known to be invariant on all
331/// iterations of its outer loop. If the loop has no parent, this is trivially
332/// true.
333bool hasIterationCountInvariantInParent(Loop *L, ScalarEvolution &SE);
334
335/// Helper to consistently add the set of standard passes to a loop pass's \c
336/// AnalysisUsage.
337///
338/// All loop passes should call this as part of implementing their \c
339/// getAnalysisUsage.
340void getLoopAnalysisUsage(AnalysisUsage &AU);
341
342/// Returns true if is legal to hoist or sink this instruction disregarding the
343/// possible introduction of faults. Reasoning about potential faulting
344/// instructions is the responsibility of the caller since it is challenging to
345/// do efficiently from within this routine.
346/// \p TargetExecutesOncePerLoop is true only when it is guaranteed that the
347/// target executes at most once per execution of the loop body. This is used
348/// to assess the legality of duplicating atomic loads. Generally, this is
349/// true when moving out of loop and not true when moving into loops.
350/// If \p ORE is set use it to emit optimization remarks.
351bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
352 Loop *CurLoop, MemorySSAUpdater &MSSAU,
353 bool TargetExecutesOncePerLoop,
354 SinkAndHoistLICMFlags &LICMFlags,
355 OptimizationRemarkEmitter *ORE = nullptr);
356
357/// Returns the comparison predicate used when expanding a min/max reduction.
359
360/// See RecurrenceDescriptor::isSelectCmpPattern for a description of the
361/// pattern we are trying to match. In this pattern we are only ever selecting
362/// between two values: 1) an initial PHI start value, and 2) a loop invariant
363/// value. This function uses \p LoopExitInst to determine 2), which we then use
364/// to select between \p Left and \p Right. Any lane value in \p Left that
365/// matches 2) will be merged into \p Right.
366Value *createSelectCmpOp(IRBuilderBase &Builder, Value *StartVal, RecurKind RK,
367 Value *Left, Value *Right);
368
369/// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
370/// The Builder's fast-math-flags must be set to propagate the expected values.
371Value *createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left,
372 Value *Right);
373
374/// Generates an ordered vector reduction using extracts to reduce the value.
375Value *getOrderedReduction(IRBuilderBase &Builder, Value *Acc, Value *Src,
376 unsigned Op, RecurKind MinMaxKind = RecurKind::None);
377
378/// Generates a vector reduction using shufflevectors to reduce the value.
379/// Fast-math-flags are propagated using the IRBuilder's setting.
380Value *getShuffleReduction(IRBuilderBase &Builder, Value *Src, unsigned Op,
381 RecurKind MinMaxKind = RecurKind::None);
382
383/// Create a target reduction of the given vector. The reduction operation
384/// is described by the \p Opcode parameter. min/max reductions require
385/// additional information supplied in \p RdxKind.
386/// The target is queried to determine if intrinsics or shuffle sequences are
387/// required to implement the reduction.
388/// Fast-math-flags are propagated using the IRBuilder's setting.
389Value *createSimpleTargetReduction(IRBuilderBase &B,
390 const TargetTransformInfo *TTI, Value *Src,
391 RecurKind RdxKind);
392
393/// Create a target reduction of the given vector \p Src for a reduction of the
394/// kind RecurKind::SelectICmp or RecurKind::SelectFCmp. The reduction operation
395/// is described by \p Desc.
396Value *createSelectCmpTargetReduction(IRBuilderBase &B,
397 const TargetTransformInfo *TTI,
398 Value *Src,
399 const RecurrenceDescriptor &Desc,
400 PHINode *OrigPhi);
401
402/// Create a generic target reduction using a recurrence descriptor \p Desc
403/// The target is queried to determine if intrinsics or shuffle sequences are
404/// required to implement the reduction.
405/// Fast-math-flags are propagated using the RecurrenceDescriptor.
406Value *createTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI,
407 const RecurrenceDescriptor &Desc, Value *Src,
408 PHINode *OrigPhi = nullptr);
409
410/// Create an ordered reduction intrinsic using the given recurrence
411/// descriptor \p Desc.
412Value *createOrderedReduction(IRBuilderBase &B,
413 const RecurrenceDescriptor &Desc, Value *Src,
414 Value *Start);
415
416/// Get the intersection (logical and) of all of the potential IR flags
417/// of each scalar operation (VL) that will be converted into a vector (I).
418/// If OpValue is non-null, we only consider operations similar to OpValue
419/// when intersecting.
420/// Flag set: NSW, NUW (if IncludeWrapFlags is true), exact, and all of
421/// fast-math.
422void propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue = nullptr,
423 bool IncludeWrapFlags = true);
424
425/// Returns true if we can prove that \p S is defined and always negative in
426/// loop \p L.
427bool isKnownNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE);
428
429/// Returns true if we can prove that \p S is defined and always non-negative in
430/// loop \p L.
431bool isKnownNonNegativeInLoop(const SCEV *S, const Loop *L,
432 ScalarEvolution &SE);
433
434/// Returns true if \p S is defined and never is equal to signed/unsigned max.
435bool cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
436 bool Signed);
437
438/// Returns true if \p S is defined and never is equal to signed/unsigned min.
439bool cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
440 bool Signed);
441
449
450/// If the final value of any expressions that are recurrent in the loop can
451/// be computed, substitute the exit values from the loop into any instructions
452/// outside of the loop that use the final values of the current expressions.
453/// Return the number of loop exit values that have been replaced, and the
454/// corresponding phi node will be added to DeadInsts.
455int rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI,
456 ScalarEvolution *SE, const TargetTransformInfo *TTI,
457 SCEVExpander &Rewriter, DominatorTree *DT,
459 SmallVector<WeakTrackingVH, 16> &DeadInsts);
460
461/// Set weights for \p UnrolledLoop and \p RemainderLoop based on weights for
462/// \p OrigLoop and the following distribution of \p OrigLoop iteration among \p
463/// UnrolledLoop and \p RemainderLoop. \p UnrolledLoop receives weights that
464/// reflect TC/UF iterations, and \p RemainderLoop receives weights that reflect
465/// the remaining TC%UF iterations.
466///
467/// Note that \p OrigLoop may be equal to either \p UnrolledLoop or \p
468/// RemainderLoop in which case weights for \p OrigLoop are updated accordingly.
469/// Note also behavior is undefined if \p UnrolledLoop and \p RemainderLoop are
470/// equal. \p UF must be greater than zero.
471/// If \p OrigLoop has no profile info associated nothing happens.
472///
473/// This utility may be useful for such optimizations as unroller and
474/// vectorizer as it's typical transformation for them.
475void setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop,
476 Loop *RemainderLoop, uint64_t UF);
477
478/// Utility that implements appending of loops onto a worklist given a range.
479/// We want to process loops in postorder, but the worklist is a LIFO data
480/// structure, so we append to it in *reverse* postorder.
481/// For trees, a preorder traversal is a viable reverse postorder, so we
482/// actually append using a preorder walk algorithm.
483template <typename RangeT>
484void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist<Loop *, 4> &);
485/// Utility that implements appending of loops onto a worklist given a range.
486/// It has the same behavior as appendLoopsToWorklist, but assumes the range of
487/// loops has already been reversed, so it processes loops in the given order.
488template <typename RangeT>
489void appendReversedLoopsToWorklist(RangeT &&,
490 SmallPriorityWorklist<Loop *, 4> &);
491
492/// Utility that implements appending of loops onto a worklist given LoopInfo.
493/// Calls the templated utility taking a Range of loops, handing it the Loops
494/// in LoopInfo, iterated in reverse. This is because the loops are stored in
495/// RPO w.r.t. the control flow graph in LoopInfo. For the purpose of unrolling,
496/// loop deletion, and LICM, we largely want to work forward across the CFG so
497/// that we visit defs before uses and can propagate simplifications from one
498/// loop nest into the next. Calls appendReversedLoopsToWorklist with the
499/// already reversed loops in LI.
500/// FIXME: Consider changing the order in LoopInfo.
501void appendLoopsToWorklist(LoopInfo &, SmallPriorityWorklist<Loop *, 4> &);
502
503/// Recursively clone the specified loop and all of its children,
504/// mapping the blocks with the specified map.
505Loop *cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM,
506 LoopInfo *LI, LPPassManager *LPM);
507
508/// Add code that checks at runtime if the accessed arrays in \p PointerChecks
509/// overlap. Returns the final comparator value or NULL if no check is needed.
510Value *
511addRuntimeChecks(Instruction *Loc, Loop *TheLoop,
512 const SmallVectorImpl<RuntimePointerCheck> &PointerChecks,
513 SCEVExpander &Expander);
514
516 Instruction *Loc, ArrayRef<PointerDiffInfo> Checks, SCEVExpander &Expander,
517 function_ref<Value *(IRBuilderBase &, unsigned)> GetVF, unsigned IC);
518
519/// Struct to hold information about a partially invariant condition.
521 /// Instructions that need to be duplicated and checked for the unswitching
522 /// condition.
524
525 /// Constant to indicate for which value the condition is invariant.
527
528 /// True if the partially invariant path is no-op (=does not have any
529 /// side-effects and no loop value is used outside the loop).
530 bool PathIsNoop = true;
531
532 /// If the partially invariant path reaches a single exit block, ExitForPath
533 /// is set to that block. Otherwise it is nullptr.
535};
536
537/// Check if the loop header has a conditional branch that is not
538/// loop-invariant, because it involves load instructions. If all paths from
539/// either the true or false successor to the header or loop exists do not
540/// modify the memory feeding the condition, perform 'partial unswitching'. That
541/// is, duplicate the instructions feeding the condition in the pre-header. Then
542/// unswitch on the duplicated condition. The condition is now known in the
543/// unswitched version for the 'invariant' path through the original loop.
544///
545/// If the branch condition of the header is partially invariant, return a pair
546/// containing the instructions to duplicate and a boolean Constant to update
547/// the condition in the loops created for the true or false successors.
548std::optional<IVConditionInfo> hasPartialIVCondition(const Loop &L,
549 unsigned MSSAThreshold,
550 const MemorySSA &MSSA,
551 AAResults &AA);
552
553} // end namespace llvm
554
555#endif // LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
SmallVector< MachineOperand, 4 > Cond
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
early cse Early CSE w MemorySSA
Definition: EarlyCSE.cpp:1809
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(UnusedIndVarInLoop, "unusedindvarinloop", "only replace exit value when it is an unused " "induction variable in the loop and has cheap replacement cost"), clEnumValN(NoHardUse, "noharduse", "only replace exit values when loop def likely dead"), clEnumValN(AlwaysRepl, "always", "always replace exit value whenever possible")))
#define I(x, y, z)
Definition: MD5.cpp:58
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)
static const uint32_t IV[8]
Definition: blake3_impl.h:77
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:718
This is an important base class in LLVM.
Definition: Constant.h:41
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to give precise answers on "may...
Definition: MustExecute.h:132
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
Metadata node.
Definition: Metadata.h:943
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:700
The optimization diagnostic interface.
PredIteratorCache - This class is an extremely trivial cache for predecessor iterator queries.
The main scalar evolution driver.
Flags controlling how much is checked when sinking or hoisting instructions.
Definition: LoopUtils.h:114
unsigned LicmMssaNoAccForPromotionCap
Definition: LoopUtils.h:134
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:301
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
Provides information about what library functions are available for the current target.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
LLVM Value Representation.
Definition: Value.h:74
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
std::optional< ElementCount > getOptionalElementCountLoopAttribute(const Loop *TheLoop)
Find a combination of metadata ("llvm.loop.vectorize.width" and "llvm.loop.vectorize....
Definition: LoopUtils.cpp:250
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.
Definition: LoopUtils.cpp:450
std::optional< unsigned > getLoopEstimatedTripCount(Loop *L, unsigned *EstimatedLoopInvocationWeight=nullptr)
Returns a loop's estimated trip count based on branch weight metadata.
Definition: LoopUtils.cpp:824
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...
std::pair< const RuntimeCheckingPtrGroup *, const RuntimeCheckingPtrGroup * > RuntimePointerCheck
A memcheck which made up of a pair of grouped pointers.
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 ...
Definition: LICM.cpp:1165
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.
Definition: LoopUtils.cpp:915
Value * createSimpleTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI, Value *Src, RecurKind RdxKind)
Create a target reduction of the given vector.
Definition: LoopUtils.cpp:1038
void appendReversedLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
Definition: LoopUtils.cpp:1512
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...
Definition: LoopUtils.cpp:1076
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
Definition: LCSSA.cpp:410
std::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.
Definition: LoopUtils.cpp:263
Value * createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left, Value *Right)
Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
Definition: LoopUtils.cpp:924
void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, unsigned V=0)
Set input string into loop metadata by keeping other values intact.
Definition: LoopUtils.cpp:214
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.
Definition: LoopUtils.cpp:1150
TransformationMode hasVectorizeTransformation(const Loop *L)
Definition: LoopUtils.cpp:391
bool hoistRegion(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *, AssumptionCache *, 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,...
Definition: LICM.cpp:865
SmallVector< Instruction *, 8 > findDefsUsedOutsideOfLoop(Loop *L)
Returns the instructions that use values defined in the loop.
Definition: LoopUtils.cpp:123
TransformationMode hasUnrollAndJamTransformation(const Loop *L)
Definition: LoopUtils.cpp:373
void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI, MemorySSA *MSSA=nullptr)
This function deletes dead loops.
Definition: LoopUtils.cpp:482
Value * getShuffleReduction(IRBuilderBase &Builder, Value *Src, unsigned Op, RecurKind MinMaxKind=RecurKind::None)
Generates a vector reduction using shufflevectors to reduce the value.
Definition: LoopUtils.cpp:958
bool hasDisableAllTransformsHint(const Loop *L)
Look for the loop attribute that disables all transformation heuristic.
Definition: LoopUtils.cpp:344
Value * createOrderedReduction(IRBuilderBase &B, const RecurrenceDescriptor &Desc, Value *Src, Value *Start)
Create an ordered reduction intrinsic using the given recurrence descriptor Desc.
Definition: LoopUtils.cpp:1093
TransformationMode hasUnrollTransformation(const Loop *L)
Definition: LoopUtils.cpp:352
DomTreeNodeBase< BasicBlock > DomTreeNode
Definition: Dominators.h:96
TransformationMode hasDistributeTransformation(const Loop *L)
Definition: LoopUtils.cpp:427
void breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA)
Remove the backedge of the specified loop.
Definition: LoopUtils.cpp:699
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
Definition: LoopUtils.cpp:141
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...
Definition: LoopUtils.cpp:1105
TargetTransformInfo TTI
CmpInst::Predicate getMinMaxReductionPredicate(RecurKind RK)
Returns the comparison predicate used when expanding a min/max reduction.
Definition: LoopUtils.cpp:896
TransformationMode hasLICMVersioningTransformation(const Loop *L)
Definition: LoopUtils.cpp:437
TransformationMode
The mode sets how eager a transformation should be applied.
Definition: LoopUtils.h:272
@ TM_Unspecified
The pass can use heuristics to determine whether a transformation should be applied.
Definition: LoopUtils.h:275
@ TM_SuppressedByUser
The transformation must not be applied.
Definition: LoopUtils.h:295
@ TM_ForcedByUser
The transformation was directed by the user, e.g.
Definition: LoopUtils.h:289
@ TM_Disable
The transformation should not be applied.
Definition: LoopUtils.h:281
@ TM_Force
Force is a flag and should not be used alone.
Definition: LoopUtils.h:284
@ TM_Enable
The transformation should be applied without considering a cost model.
Definition: LoopUtils.h:278
bool hasDisableLICMTransformsHint(const Loop *L)
Look for the loop attribute that disables the LICM transformation heuristics.
Definition: LoopUtils.cpp:348
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.
Definition: LoopUtils.cpp:1626
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.
Definition: LCSSA.cpp:78
RecurKind
These are the kinds of recurrences that we support.
Definition: IVDescriptors.h:35
@ None
Not a recurrence.
bool setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount, unsigned EstimatedLoopInvocationWeight)
Set a loop's branch weight metadata to reflect that loop has EstimatedTripCount iterations and Estima...
Definition: LoopUtils.cpp:842
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...
Definition: LoopUtils.cpp:1484
bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Ensure that all exit blocks of the loop are dedicated exits.
Definition: LoopUtils.cpp:57
void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
Definition: LoopUtils.cpp:1537
bool promoteLoopAccessesToScalars(const SmallSetVector< Value *, 8 > &, SmallVectorImpl< BasicBlock * > &, SmallVectorImpl< Instruction * > &, SmallVectorImpl< MemoryAccess * > &, PredIteratorCache &, LoopInfo *, DominatorTree *, AssumptionCache *AC, const TargetLibraryInfo *, TargetTransformInfo *, Loop *, MemorySSAUpdater &, ICFLoopSafetyInfo *, OptimizationRemarkEmitter *, bool AllowSpeculation, bool HasReadsOutsideSet)
Try to promote memory values to scalars by sinking stores out of the loop and moving loads to before ...
Definition: LICM.cpp:1967
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.
Definition: LoopUtils.cpp:1125
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...
Definition: LoopUtils.cpp:998
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
bool hasIterationCountInvariantInParent(Loop *L, ScalarEvolution &SE)
Check inner loop (L) backedge count is known to be invariant on all iterations of its outer loop.
Definition: LoopUtils.cpp:874
bool isAlmostDeadIV(PHINode *IV, BasicBlock *LatchBlock, Value *Cond)
Return true if the induction variable IV in a Loop whose latch is LatchBlock would become dead if the...
Definition: LoopUtils.cpp:469
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,...
Definition: LoopUtils.cpp:1272
bool sinkRegion(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *, 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,...
Definition: LICM.cpp:545
Value * addDiffRuntimeChecks(Instruction *Loc, ArrayRef< PointerDiffInfo > Checks, SCEVExpander &Expander, function_ref< Value *(IRBuilderBase &, unsigned)> GetVF, unsigned IC)
Definition: LoopUtils.cpp:1681
ReplaceExitVal
Definition: LoopUtils.h:442
@ UnusedIndVarInLoop
Definition: LoopUtils.h:446
@ OnlyCheapRepl
Definition: LoopUtils.h:444
@ NeverRepl
Definition: LoopUtils.h:443
@ NoHardUse
Definition: LoopUtils.h:445
@ AlwaysRepl
Definition: LoopUtils.h:447
std::optional< IVConditionInfo > hasPartialIVCondition(const Loop &L, unsigned MSSAThreshold, const MemorySSA &MSSA, AAResults &AA)
Check if the loop header has a conditional branch that is not loop-invariant, because it involves loa...
Definition: LoopUtils.cpp:1720
bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put loop into LCSSA form.
Definition: LCSSA.cpp:341
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.
Definition: LoopUtils.cpp:1139
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.
Definition: LoopUtils.cpp:1132
bool sinkRegionForLoopNest(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, TargetTransformInfo *, Loop *, MemorySSAUpdater &, ICFLoopSafetyInfo *, SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *)
Call sinkRegion on loops contained within the specified loop in order from innermost to outermost.
Definition: LICM.cpp:612
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.
Definition: LoopUtils.cpp:933
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...
Definition: LoopUtils.cpp:1554
#define N
Struct to hold information about a partially invariant condition.
Definition: LoopUtils.h:520
BasicBlock * ExitForPath
If the partially invariant path reaches a single exit block, ExitForPath is set to that block.
Definition: LoopUtils.h:534
SmallVector< Instruction * > InstToDuplicate
Instructions that need to be duplicated and checked for the unswitching condition.
Definition: LoopUtils.h:523
Constant * KnownValue
Constant to indicate for which value the condition is invariant.
Definition: LoopUtils.h:526
bool PathIsNoop
True if the partially invariant path is no-op (=does not have any side-effects and no loop value is u...
Definition: LoopUtils.h:530