LLVM 20.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
21
22namespace llvm {
23
24template <typename T> class DomTreeNodeBase;
25using DomTreeNode = DomTreeNodeBase<BasicBlock>;
26class AssumptionCache;
27class StringRef;
28class AnalysisUsage;
29class TargetTransformInfo;
30class AAResults;
31class BasicBlock;
32class ICFLoopSafetyInfo;
33class IRBuilderBase;
34class Loop;
35class LoopInfo;
36class MemoryAccess;
37class MemorySSA;
38class MemorySSAUpdater;
39class OptimizationRemarkEmitter;
40class PredIteratorCache;
41class ScalarEvolution;
42class SCEV;
43class SCEVExpander;
44class TargetLibraryInfo;
45class LPPassManager;
46class Instruction;
47struct RuntimeCheckingPtrGroup;
48typedef std::pair<const RuntimeCheckingPtrGroup *,
49 const RuntimeCheckingPtrGroup *>
51
52template <typename T, unsigned N> class SmallSetVector;
53template <typename T, unsigned N> class SmallPriorityWorklist;
54
55BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,
56 MemorySSAUpdater *MSSAU, bool PreserveLCSSA);
57
58/// Ensure that all exit blocks of the loop are dedicated exits.
59///
60/// For any loop exit block with non-loop predecessors, we split the loop
61/// predecessors to use a dedicated loop exit block. We update the dominator
62/// tree and loop info if provided, and will preserve LCSSA if requested.
63bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
64 MemorySSAUpdater *MSSAU, bool PreserveLCSSA);
65
66/// Ensures LCSSA form for every instruction from the Worklist in the scope of
67/// innermost containing loop.
68///
69/// For the given instruction which have uses outside of the loop, an LCSSA PHI
70/// node is inserted and the uses outside the loop are rewritten to use this
71/// node.
72///
73/// LoopInfo and DominatorTree are required and, since the routine makes no
74/// changes to CFG, preserved.
75///
76/// Returns true if any modifications are made.
77///
78/// This function may introduce unused PHI nodes. If \p PHIsToRemove is not
79/// nullptr, those are added to it (before removing, the caller has to check if
80/// they still do not have any uses). Otherwise the PHIs are directly removed.
81///
82/// If \p InsertedPHIs is not nullptr, inserted phis will be added to this
83/// vector.
85 SmallVectorImpl<Instruction *> &Worklist, const DominatorTree &DT,
86 const LoopInfo &LI, ScalarEvolution *SE,
87 SmallVectorImpl<PHINode *> *PHIsToRemove = nullptr,
88 SmallVectorImpl<PHINode *> *InsertedPHIs = nullptr);
89
90/// Put loop into LCSSA form.
91///
92/// Looks at all instructions in the loop which have uses outside of the
93/// current loop. For each, an LCSSA PHI node is inserted and the uses outside
94/// the loop are rewritten to use this node. Sub-loops must be in LCSSA form
95/// already.
96///
97/// LoopInfo and DominatorTree are required and preserved.
98///
99/// If ScalarEvolution is passed in, it will be preserved.
100///
101/// Returns true if any modifications are made to the loop.
102bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI,
103 ScalarEvolution *SE);
104
105/// Put a loop nest into LCSSA form.
106///
107/// This recursively forms LCSSA for a loop nest.
108///
109/// LoopInfo and DominatorTree are required and preserved.
110///
111/// If ScalarEvolution is passed in, it will be preserved.
112///
113/// Returns true if any modifications are made to the loop.
114bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI,
115 ScalarEvolution *SE);
116
117/// Flags controlling how much is checked when sinking or hoisting
118/// instructions. The number of memory access in the loop (and whether there
119/// are too many) is determined in the constructors when using MemorySSA.
121public:
122 // Explicitly set limits.
125 Loop &L, MemorySSA &MSSA);
126 // Use default limits.
128
129 void setIsSink(bool B) { IsSink = B; }
130 bool getIsSink() { return IsSink; }
134
135protected:
136 bool NoOfMemAccTooLarge = false;
137 unsigned LicmMssaOptCounter = 0;
140 bool IsSink;
141};
142
143/// Walk the specified region of the CFG (defined by all blocks
144/// dominated by the specified block, and that are in the current loop) in
145/// reverse depth first order w.r.t the DominatorTree. This allows us to visit
146/// uses before definitions, allowing us to sink a loop body in one pass without
147/// iteration. Takes DomTreeNode, AAResults, LoopInfo, DominatorTree,
148/// TargetLibraryInfo, Loop, AliasSet information for all
149/// instructions of the loop and loop safety information as
150/// arguments. Diagnostics is emitted via \p ORE. It returns changed status.
151/// \p CurLoop is a loop to do sinking on. \p OutermostLoop is used only when
152/// this function is called by \p sinkRegionForLoopNest.
157 Loop *OutermostLoop = nullptr);
158
159/// Call sinkRegion on loops contained within the specified loop
160/// in order from innermost to outermost.
166
167/// Walk the specified region of the CFG (defined by all blocks
168/// dominated by the specified block, and that are in the current loop) in depth
169/// first order w.r.t the DominatorTree. This allows us to visit definitions
170/// before uses, allowing us to hoist a loop body in one pass without iteration.
171/// Takes DomTreeNode, AAResults, LoopInfo, DominatorTree,
172/// TargetLibraryInfo, Loop, AliasSet information for all
173/// instructions of the loop and loop safety information as arguments.
174/// Diagnostics is emitted via \p ORE. It returns changed status.
175/// \p AllowSpeculation is whether values should be hoisted even if they are not
176/// guaranteed to execute in the loop, but are safe to speculatively execute.
181 bool AllowSpeculation);
182
183/// Return true if the induction variable \p IV in a Loop whose latch is
184/// \p LatchBlock would become dead if the exit test \p Cond were removed.
185/// Conservatively returns false if analysis is insufficient.
186bool isAlmostDeadIV(PHINode *IV, BasicBlock *LatchBlock, Value *Cond);
187
188/// This function deletes dead loops. The caller of this function needs to
189/// guarantee that the loop is infact dead.
190/// The function requires a bunch or prerequisites to be present:
191/// - The loop needs to be in LCSSA form
192/// - The loop needs to have a Preheader
193/// - A unique dedicated exit block must exist
194///
195/// This also updates the relevant analysis information in \p DT, \p SE, \p LI
196/// and \p MSSA if pointers to those are provided.
197/// It also updates the loop PM if an updater struct is provided.
198
200 LoopInfo *LI, MemorySSA *MSSA = nullptr);
201
202/// Remove the backedge of the specified loop. Handles loop nests and general
203/// loop structures subject to the precondition that the loop has no parent
204/// loop and has a single latch block. Preserves all listed analyses.
206 LoopInfo &LI, MemorySSA *MSSA);
207
208/// Try to promote memory values to scalars by sinking stores out of
209/// the loop and moving loads to before the loop. We do this by looping over
210/// the stores in the loop, looking for stores to Must pointers which are
211/// loop invariant. It takes a set of must-alias values, Loop exit blocks
212/// vector, loop exit blocks insertion point vector, PredIteratorCache,
213/// LoopInfo, DominatorTree, Loop, AliasSet information for all instructions
214/// of the loop and loop safety information as arguments.
215/// Diagnostics is emitted via \p ORE. It returns changed status.
216/// \p AllowSpeculation is whether values should be hoisted even if they are not
217/// guaranteed to execute in the loop, but are safe to speculatively execute.
224 bool AllowSpeculation, bool HasReadsOutsideSet);
225
226/// Does a BFS from a given node to all of its children inside a given loop.
227/// The returned vector of nodes includes the starting point.
229 const Loop *CurLoop);
230
231/// Returns the instructions that use values defined in the loop.
233
234/// Find a combination of metadata ("llvm.loop.vectorize.width" and
235/// "llvm.loop.vectorize.scalable.enable") for a loop and use it to construct a
236/// ElementCount. If the metadata "llvm.loop.vectorize.width" cannot be found
237/// then std::nullopt is returned.
238std::optional<ElementCount>
240
241/// Create a new loop identifier for a loop created from a loop transformation.
242///
243/// @param OrigLoopID The loop ID of the loop before the transformation.
244/// @param FollowupAttrs List of attribute names that contain attributes to be
245/// added to the new loop ID.
246/// @param InheritOptionsAttrsPrefix Selects which attributes should be inherited
247/// from the original loop. The following values
248/// are considered:
249/// nullptr : Inherit all attributes from @p OrigLoopID.
250/// "" : Do not inherit any attribute from @p OrigLoopID; only use
251/// those specified by a followup attribute.
252/// "<prefix>": Inherit all attributes except those which start with
253/// <prefix>; commonly used to remove metadata for the
254/// applied transformation.
255/// @param AlwaysNew If true, do not try to reuse OrigLoopID and never return
256/// std::nullopt.
257///
258/// @return The loop ID for the after-transformation loop. The following values
259/// can be returned:
260/// std::nullopt : No followup attribute was found; it is up to the
261/// transformation to choose attributes that make sense.
262/// @p OrigLoopID: The original identifier can be reused.
263/// nullptr : The new loop has no attributes.
264/// MDNode* : A new unique loop identifier.
265std::optional<MDNode *>
266makeFollowupLoopID(MDNode *OrigLoopID, ArrayRef<StringRef> FollowupAttrs,
267 const char *InheritOptionsAttrsPrefix = "",
268 bool AlwaysNew = false);
269
270/// Look for the loop attribute that disables all transformation heuristic.
271bool hasDisableAllTransformsHint(const Loop *L);
272
273/// Look for the loop attribute that disables the LICM transformation heuristics.
275
276/// The mode sets how eager a transformation should be applied.
278 /// The pass can use heuristics to determine whether a transformation should
279 /// be applied.
281
282 /// The transformation should be applied without considering a cost model.
284
285 /// The transformation should not be applied.
287
288 /// Force is a flag and should not be used alone.
289 TM_Force = 0x04,
290
291 /// The transformation was directed by the user, e.g. by a #pragma in
292 /// the source code. If the transformation could not be applied, a
293 /// warning should be emitted.
295
296 /// The transformation must not be applied. For instance, `#pragma clang loop
297 /// unroll(disable)` explicitly forbids any unrolling to take place. Unlike
298 /// general loop metadata, it must not be dropped. Most passes should not
299 /// behave differently under TM_Disable and TM_SuppressedByUser.
302
303/// @{
304/// Get the mode for LLVM's supported loop transformations.
310/// @}
311
312/// Set input string into loop metadata by keeping other values intact.
313/// If the string is already in loop metadata update value if it is
314/// different.
315void addStringMetadataToLoop(Loop *TheLoop, const char *MDString,
316 unsigned V = 0);
317
318/// Returns a loop's estimated trip count based on branch weight metadata.
319/// In addition if \p EstimatedLoopInvocationWeight is not null it is
320/// initialized with weight of loop's latch leading to the exit.
321/// Returns 0 when the count is estimated to be 0, or std::nullopt when a
322/// meaningful estimate can not be made.
323std::optional<unsigned>
325 unsigned *EstimatedLoopInvocationWeight = nullptr);
326
327/// Set a loop's branch weight metadata to reflect that loop has \p
328/// EstimatedTripCount iterations and \p EstimatedLoopInvocationWeight exits
329/// through latch. Returns true if metadata is successfully updated, false
330/// otherwise. Note that loop must have a latch block which controls loop exit
331/// in order to succeed.
332bool setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount,
333 unsigned EstimatedLoopInvocationWeight);
334
335/// Check inner loop (L) backedge count is known to be invariant on all
336/// iterations of its outer loop. If the loop has no parent, this is trivially
337/// true.
338bool hasIterationCountInvariantInParent(Loop *L, ScalarEvolution &SE);
339
340/// Helper to consistently add the set of standard passes to a loop pass's \c
341/// AnalysisUsage.
342///
343/// All loop passes should call this as part of implementing their \c
344/// getAnalysisUsage.
345void getLoopAnalysisUsage(AnalysisUsage &AU);
346
347/// Returns true if is legal to hoist or sink this instruction disregarding the
348/// possible introduction of faults. Reasoning about potential faulting
349/// instructions is the responsibility of the caller since it is challenging to
350/// do efficiently from within this routine.
351/// \p TargetExecutesOncePerLoop is true only when it is guaranteed that the
352/// target executes at most once per execution of the loop body. This is used
353/// to assess the legality of duplicating atomic loads. Generally, this is
354/// true when moving out of loop and not true when moving into loops.
355/// If \p ORE is set use it to emit optimization remarks.
356bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
357 Loop *CurLoop, MemorySSAUpdater &MSSAU,
358 bool TargetExecutesOncePerLoop,
359 SinkAndHoistLICMFlags &LICMFlags,
360 OptimizationRemarkEmitter *ORE = nullptr);
361
362/// Returns the llvm.vector.reduce intrinsic that corresponds to the recurrence
363/// kind.
365
366/// Returns the arithmetic instruction opcode used when expanding a reduction.
368
369/// Returns the min/max intrinsic used when expanding a min/max reduction.
371
372/// Returns the min/max intrinsic used when expanding a min/max reduction.
374
375/// Returns the recurence kind used when expanding a min/max reduction.
377
378/// Returns the comparison predicate used when expanding a min/max reduction.
380
381/// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
382/// The Builder's fast-math-flags must be set to propagate the expected values.
383Value *createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left,
384 Value *Right);
385
386/// Generates an ordered vector reduction using extracts to reduce the value.
387Value *getOrderedReduction(IRBuilderBase &Builder, Value *Acc, Value *Src,
388 unsigned Op, RecurKind MinMaxKind = RecurKind::None);
389
390/// Generates a vector reduction using shufflevectors to reduce the value.
391/// Fast-math-flags are propagated using the IRBuilder's setting.
392Value *getShuffleReduction(IRBuilderBase &Builder, Value *Src, unsigned Op,
394 RecurKind MinMaxKind = RecurKind::None);
395
396/// Create a target reduction of the given vector. The reduction operation
397/// is described by the \p Opcode parameter. min/max reductions require
398/// additional information supplied in \p RdxKind.
399/// The target is queried to determine if intrinsics or shuffle sequences are
400/// required to implement the reduction.
401/// Fast-math-flags are propagated using the IRBuilder's setting.
402Value *createSimpleTargetReduction(IRBuilderBase &B, Value *Src,
403 RecurKind RdxKind);
404/// Overloaded function to generate vector-predication intrinsics for target
405/// reduction.
406Value *createSimpleTargetReduction(VectorBuilder &VB, Value *Src,
407 const RecurrenceDescriptor &Desc);
408
409/// Create a target reduction of the given vector \p Src for a reduction of the
410/// kind RecurKind::IAnyOf or RecurKind::FAnyOf. The reduction operation is
411/// described by \p Desc.
412Value *createAnyOfTargetReduction(IRBuilderBase &B, Value *Src,
413 const RecurrenceDescriptor &Desc,
414 PHINode *OrigPhi);
415
416/// Create a generic target reduction using a recurrence descriptor \p Desc
417/// The target is queried to determine if intrinsics or shuffle sequences are
418/// required to implement the reduction.
419/// Fast-math-flags are propagated using the RecurrenceDescriptor.
420Value *createTargetReduction(IRBuilderBase &B, const RecurrenceDescriptor &Desc,
421 Value *Src, PHINode *OrigPhi = nullptr);
422
423/// Create an ordered reduction intrinsic using the given recurrence
424/// descriptor \p Desc.
425Value *createOrderedReduction(IRBuilderBase &B,
426 const RecurrenceDescriptor &Desc, Value *Src,
427 Value *Start);
428/// Overloaded function to generate vector-predication intrinsics for ordered
429/// reduction.
430Value *createOrderedReduction(VectorBuilder &VB,
431 const RecurrenceDescriptor &Desc, Value *Src,
432 Value *Start);
433
434/// Get the intersection (logical and) of all of the potential IR flags
435/// of each scalar operation (VL) that will be converted into a vector (I).
436/// If OpValue is non-null, we only consider operations similar to OpValue
437/// when intersecting.
438/// Flag set: NSW, NUW (if IncludeWrapFlags is true), exact, and all of
439/// fast-math.
440void propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue = nullptr,
441 bool IncludeWrapFlags = true);
442
443/// Returns true if we can prove that \p S is defined and always negative in
444/// loop \p L.
445bool isKnownNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE);
446
447/// Returns true if we can prove that \p S is defined and always non-negative in
448/// loop \p L.
449bool isKnownNonNegativeInLoop(const SCEV *S, const Loop *L,
450 ScalarEvolution &SE);
451/// Returns true if we can prove that \p S is defined and always positive in
452/// loop \p L.
453bool isKnownPositiveInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE);
454
455/// Returns true if we can prove that \p S is defined and always non-positive in
456/// loop \p L.
457bool isKnownNonPositiveInLoop(const SCEV *S, const Loop *L,
458 ScalarEvolution &SE);
459
460/// Returns true if \p S is defined and never is equal to signed/unsigned max.
461bool cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
462 bool Signed);
463
464/// Returns true if \p S is defined and never is equal to signed/unsigned min.
465bool cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
466 bool Signed);
467
475
476/// If the final value of any expressions that are recurrent in the loop can
477/// be computed, substitute the exit values from the loop into any instructions
478/// outside of the loop that use the final values of the current expressions.
479/// Return the number of loop exit values that have been replaced, and the
480/// corresponding phi node will be added to DeadInsts.
481int rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI,
482 ScalarEvolution *SE, const TargetTransformInfo *TTI,
483 SCEVExpander &Rewriter, DominatorTree *DT,
485 SmallVector<WeakTrackingVH, 16> &DeadInsts);
486
487/// Set weights for \p UnrolledLoop and \p RemainderLoop based on weights for
488/// \p OrigLoop and the following distribution of \p OrigLoop iteration among \p
489/// UnrolledLoop and \p RemainderLoop. \p UnrolledLoop receives weights that
490/// reflect TC/UF iterations, and \p RemainderLoop receives weights that reflect
491/// the remaining TC%UF iterations.
492///
493/// Note that \p OrigLoop may be equal to either \p UnrolledLoop or \p
494/// RemainderLoop in which case weights for \p OrigLoop are updated accordingly.
495/// Note also behavior is undefined if \p UnrolledLoop and \p RemainderLoop are
496/// equal. \p UF must be greater than zero.
497/// If \p OrigLoop has no profile info associated nothing happens.
498///
499/// This utility may be useful for such optimizations as unroller and
500/// vectorizer as it's typical transformation for them.
501void setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop,
502 Loop *RemainderLoop, uint64_t UF);
503
504/// Utility that implements appending of loops onto a worklist given a range.
505/// We want to process loops in postorder, but the worklist is a LIFO data
506/// structure, so we append to it in *reverse* postorder.
507/// For trees, a preorder traversal is a viable reverse postorder, so we
508/// actually append using a preorder walk algorithm.
509template <typename RangeT>
510void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist<Loop *, 4> &);
511/// Utility that implements appending of loops onto a worklist given a range.
512/// It has the same behavior as appendLoopsToWorklist, but assumes the range of
513/// loops has already been reversed, so it processes loops in the given order.
514template <typename RangeT>
515void appendReversedLoopsToWorklist(RangeT &&,
516 SmallPriorityWorklist<Loop *, 4> &);
517
518/// Utility that implements appending of loops onto a worklist given LoopInfo.
519/// Calls the templated utility taking a Range of loops, handing it the Loops
520/// in LoopInfo, iterated in reverse. This is because the loops are stored in
521/// RPO w.r.t. the control flow graph in LoopInfo. For the purpose of unrolling,
522/// loop deletion, and LICM, we largely want to work forward across the CFG so
523/// that we visit defs before uses and can propagate simplifications from one
524/// loop nest into the next. Calls appendReversedLoopsToWorklist with the
525/// already reversed loops in LI.
526/// FIXME: Consider changing the order in LoopInfo.
527void appendLoopsToWorklist(LoopInfo &, SmallPriorityWorklist<Loop *, 4> &);
528
529/// Recursively clone the specified loop and all of its children,
530/// mapping the blocks with the specified map.
531Loop *cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM,
532 LoopInfo *LI, LPPassManager *LPM);
533
534/// Add code that checks at runtime if the accessed arrays in \p PointerChecks
535/// overlap. Returns the final comparator value or NULL if no check is needed.
536Value *
537addRuntimeChecks(Instruction *Loc, Loop *TheLoop,
538 const SmallVectorImpl<RuntimePointerCheck> &PointerChecks,
539 SCEVExpander &Expander, bool HoistRuntimeChecks = false);
540
542 Instruction *Loc, ArrayRef<PointerDiffInfo> Checks, SCEVExpander &Expander,
543 function_ref<Value *(IRBuilderBase &, unsigned)> GetVF, unsigned IC);
544
545/// Struct to hold information about a partially invariant condition.
547 /// Instructions that need to be duplicated and checked for the unswitching
548 /// condition.
550
551 /// Constant to indicate for which value the condition is invariant.
553
554 /// True if the partially invariant path is no-op (=does not have any
555 /// side-effects and no loop value is used outside the loop).
556 bool PathIsNoop = true;
557
558 /// If the partially invariant path reaches a single exit block, ExitForPath
559 /// is set to that block. Otherwise it is nullptr.
561};
562
563/// Check if the loop header has a conditional branch that is not
564/// loop-invariant, because it involves load instructions. If all paths from
565/// either the true or false successor to the header or loop exists do not
566/// modify the memory feeding the condition, perform 'partial unswitching'. That
567/// is, duplicate the instructions feeding the condition in the pre-header. Then
568/// unswitch on the duplicated condition. The condition is now known in the
569/// unswitched version for the 'invariant' path through the original loop.
570///
571/// If the branch condition of the header is partially invariant, return a pair
572/// containing the instructions to duplicate and a boolean Constant to update
573/// the condition in the loops created for the true or false successors.
574std::optional<IVConditionInfo> hasPartialIVCondition(const Loop &L,
575 unsigned MSSAThreshold,
576 const MemorySSA &MSSA,
577 AAResults &AA);
578
579} // end namespace llvm
580
581#endif // LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
early cse Early CSE w MemorySSA
Definition: EarlyCSE.cpp:1948
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")))
static cl::opt< bool, true > HoistRuntimeChecks("hoist-runtime-checks", cl::Hidden, cl::desc("Hoist inner loop runtime memory checks to outer loop if possible"), cl::location(VectorizerParams::HoistRuntimeChecks), cl::init(true))
#define I(x, y, z)
Definition: MD5.cpp:58
const SmallVectorImpl< MachineOperand > & Cond
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)
This pass exposes codegen information to IR-level passes.
static const uint32_t IV[8]
Definition: blake3_impl.h:78
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:61
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:757
This is an important base class in LLVM.
Definition: Constant.h:42
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
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:44
Metadata node.
Definition: Metadata.h:1069
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:701
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:120
unsigned LicmMssaNoAccForPromotionCap
Definition: LoopUtils.h:139
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:587
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1210
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
Value * addRuntimeChecks(Instruction *Loc, Loop *TheLoop, const SmallVectorImpl< RuntimePointerCheck > &PointerChecks, SCEVExpander &Expander, bool HoistRuntimeChecks=false)
Add code that checks at runtime if the accessed arrays in PointerChecks overlap.
Definition: LoopUtils.cpp:1894
std::optional< unsigned > getLoopEstimatedTripCount(Loop *L, unsigned *EstimatedLoopInvocationWeight=nullptr)
Returns a loop's estimated trip count based on branch weight metadata.
Definition: LoopUtils.cpp:849
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...
Intrinsic::ID getMinMaxReductionIntrinsicOp(Intrinsic::ID RdxID)
Returns the min/max intrinsic used when expanding a min/max reduction.
Definition: LoopUtils.cpp:988
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:1162
bool isKnownNonPositiveInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)
Returns true if we can prove that S is defined and always non-positive in loop L.
Definition: LoopUtils.cpp:1349
Value * createSimpleTargetReduction(IRBuilderBase &B, Value *Src, RecurKind RdxKind)
Create a target reduction of the given vector.
Definition: LoopUtils.cpp:1210
void appendReversedLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
Definition: LoopUtils.cpp:1729
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
Definition: LCSSA.cpp:465
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
unsigned getArithmeticReductionInstruction(Intrinsic::ID RdxID)
Returns the arithmetic instruction opcode used when expanding a reduction.
Definition: LoopUtils.cpp:959
Op::Description Desc
Value * createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left, Value *Right)
Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
Definition: LoopUtils.cpp:1075
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:1367
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:876
SmallVector< Instruction *, 8 > findDefsUsedOutsideOfLoop(Loop *L)
Returns the instructions that use values defined in the loop.
Definition: LoopUtils.cpp:123
constexpr Intrinsic::ID getReductionIntrinsicID(RecurKind RK)
Returns the llvm.vector.reduce intrinsic that corresponds to the recurrence kind.
Definition: LoopUtils.cpp:921
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:483
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:1281
Value * getShuffleReduction(IRBuilderBase &Builder, Value *Src, unsigned Op, TargetTransformInfo::ReductionShuffle RS, RecurKind MinMaxKind=RecurKind::None)
Generates a vector reduction using shufflevectors to reduce the value.
Definition: LoopUtils.cpp:1117
TransformationMode hasUnrollTransformation(const Loop *L)
Definition: LoopUtils.cpp:352
DomTreeNodeBase< BasicBlock > DomTreeNode
Definition: Dominators.h:92
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:724
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:1308
bool isKnownPositiveInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)
Returns true if we can prove that S is defined and always positive in loop L.
Definition: LoopUtils.cpp:1342
TargetTransformInfo TTI
CmpInst::Predicate getMinMaxReductionPredicate(RecurKind RK)
Returns the comparison predicate used when expanding a min/max reduction.
Definition: LoopUtils.cpp:1053
TransformationMode hasLICMVersioningTransformation(const Loop *L)
Definition: LoopUtils.cpp:437
TransformationMode
The mode sets how eager a transformation should be applied.
Definition: LoopUtils.h:277
@ TM_Unspecified
The pass can use heuristics to determine whether a transformation should be applied.
Definition: LoopUtils.h:280
@ TM_SuppressedByUser
The transformation must not be applied.
Definition: LoopUtils.h:300
@ TM_ForcedByUser
The transformation was directed by the user, e.g.
Definition: LoopUtils.h:294
@ TM_Disable
The transformation should not be applied.
Definition: LoopUtils.h:286
@ TM_Force
Force is a flag and should not be used alone.
Definition: LoopUtils.h:289
@ TM_Enable
The transformation should be applied without considering a cost model.
Definition: LoopUtils.h:283
bool hasDisableLICMTransformsHint(const Loop *L)
Look for the loop attribute that disables the LICM transformation heuristics.
Definition: LoopUtils.cpp:348
RecurKind
These are the kinds of recurrences that we support.
Definition: IVDescriptors.h:34
@ 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:867
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:1701
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
DWARFExpression::Operation Op
void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
Definition: LoopUtils.cpp:1754
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:1328
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
bool formLCSSAForInstructions(SmallVectorImpl< Instruction * > &Worklist, const DominatorTree &DT, const LoopInfo &LI, ScalarEvolution *SE, SmallVectorImpl< PHINode * > *PHIsToRemove=nullptr, SmallVectorImpl< PHINode * > *InsertedPHIs=nullptr)
Ensures LCSSA form for every instruction from the Worklist in the scope of innermost containing loop.
Definition: LCSSA.cpp:325
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:899
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:1489
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:555
Value * addDiffRuntimeChecks(Instruction *Loc, ArrayRef< PointerDiffInfo > Checks, SCEVExpander &Expander, function_ref< Value *(IRBuilderBase &, unsigned)> GetVF, unsigned IC)
Definition: LoopUtils.cpp:1952
RecurKind getMinMaxReductionRecurKind(Intrinsic::ID RdxID)
Returns the recurence kind used when expanding a min/max reduction.
Definition: LoopUtils.cpp:1034
ReplaceExitVal
Definition: LoopUtils.h:468
@ UnusedIndVarInLoop
Definition: LoopUtils.h:472
@ OnlyCheapRepl
Definition: LoopUtils.h:470
@ NeverRepl
Definition: LoopUtils.h:469
@ NoHardUse
Definition: LoopUtils.h:471
@ AlwaysRepl
Definition: LoopUtils.h:473
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:1998
bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put loop into LCSSA form.
Definition: LCSSA.cpp:443
bool promoteLoopAccessesToScalars(const SmallSetVector< Value *, 8 > &, SmallVectorImpl< BasicBlock * > &, SmallVectorImpl< BasicBlock::iterator > &, 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:1966
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:1356
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:1335
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:623
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:1092
Value * createTargetReduction(IRBuilderBase &B, 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:1265
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:1771
Value * createAnyOfTargetReduction(IRBuilderBase &B, Value *Src, const RecurrenceDescriptor &Desc, PHINode *OrigPhi)
Create a target reduction of the given vector Src for a reduction of the kind RecurKind::IAnyOf or Re...
Definition: LoopUtils.cpp:1175
#define N
Struct to hold information about a partially invariant condition.
Definition: LoopUtils.h:546
BasicBlock * ExitForPath
If the partially invariant path reaches a single exit block, ExitForPath is set to that block.
Definition: LoopUtils.h:560
SmallVector< Instruction * > InstToDuplicate
Instructions that need to be duplicated and checked for the unswitching condition.
Definition: LoopUtils.h:549
Constant * KnownValue
Constant to indicate for which value the condition is invariant.
Definition: LoopUtils.h:552
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:556