LLVM 19.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.
79///
80/// If \p InsertedPHIs is not nullptr, inserted phis will be added to this
81/// vector.
83 SmallVectorImpl<Instruction *> &Worklist, const DominatorTree &DT,
84 const LoopInfo &LI, ScalarEvolution *SE,
85 SmallVectorImpl<PHINode *> *PHIsToRemove = nullptr,
86 SmallVectorImpl<PHINode *> *InsertedPHIs = nullptr);
87
88/// Put loop into LCSSA form.
89///
90/// Looks at all instructions in the loop which have uses outside of the
91/// current loop. For each, an LCSSA PHI node is inserted and the uses outside
92/// the loop are rewritten to use this node. Sub-loops must be in LCSSA form
93/// already.
94///
95/// LoopInfo and DominatorTree are required and preserved.
96///
97/// If ScalarEvolution is passed in, it will be preserved.
98///
99/// Returns true if any modifications are made to the loop.
100bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI,
101 ScalarEvolution *SE);
102
103/// Put a loop nest into LCSSA form.
104///
105/// This recursively forms LCSSA for a loop nest.
106///
107/// LoopInfo and DominatorTree are required and preserved.
108///
109/// If ScalarEvolution is passed in, it will be preserved.
110///
111/// Returns true if any modifications are made to the loop.
112bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI,
113 ScalarEvolution *SE);
114
115/// Flags controlling how much is checked when sinking or hoisting
116/// instructions. The number of memory access in the loop (and whether there
117/// are too many) is determined in the constructors when using MemorySSA.
119public:
120 // Explicitly set limits.
123 Loop &L, MemorySSA &MSSA);
124 // Use default limits.
126
127 void setIsSink(bool B) { IsSink = B; }
128 bool getIsSink() { return IsSink; }
132
133protected:
134 bool NoOfMemAccTooLarge = false;
135 unsigned LicmMssaOptCounter = 0;
138 bool IsSink;
139};
140
141/// Walk the specified region of the CFG (defined by all blocks
142/// dominated by the specified block, and that are in the current loop) in
143/// reverse depth first order w.r.t the DominatorTree. This allows us to visit
144/// uses before definitions, allowing us to sink a loop body in one pass without
145/// iteration. Takes DomTreeNode, AAResults, LoopInfo, DominatorTree,
146/// TargetLibraryInfo, Loop, AliasSet information for all
147/// instructions of the loop and loop safety information as
148/// arguments. Diagnostics is emitted via \p ORE. It returns changed status.
149/// \p CurLoop is a loop to do sinking on. \p OutermostLoop is used only when
150/// this function is called by \p sinkRegionForLoopNest.
155 Loop *OutermostLoop = nullptr);
156
157/// Call sinkRegion on loops contained within the specified loop
158/// in order from innermost to outermost.
164
165/// Walk the specified region of the CFG (defined by all blocks
166/// dominated by the specified block, and that are in the current loop) in depth
167/// first order w.r.t the DominatorTree. This allows us to visit definitions
168/// before uses, allowing us to hoist a loop body in one pass without iteration.
169/// Takes DomTreeNode, AAResults, LoopInfo, DominatorTree,
170/// TargetLibraryInfo, Loop, AliasSet information for all
171/// instructions of the loop and loop safety information as arguments.
172/// Diagnostics is emitted via \p ORE. It returns changed status.
173/// \p AllowSpeculation is whether values should be hoisted even if they are not
174/// guaranteed to execute in the loop, but are safe to speculatively execute.
179 bool AllowSpeculation);
180
181/// Return true if the induction variable \p IV in a Loop whose latch is
182/// \p LatchBlock would become dead if the exit test \p Cond were removed.
183/// Conservatively returns false if analysis is insufficient.
184bool isAlmostDeadIV(PHINode *IV, BasicBlock *LatchBlock, Value *Cond);
185
186/// This function deletes dead loops. The caller of this function needs to
187/// guarantee that the loop is infact dead.
188/// The function requires a bunch or prerequisites to be present:
189/// - The loop needs to be in LCSSA form
190/// - The loop needs to have a Preheader
191/// - A unique dedicated exit block must exist
192///
193/// This also updates the relevant analysis information in \p DT, \p SE, \p LI
194/// and \p MSSA if pointers to those are provided.
195/// It also updates the loop PM if an updater struct is provided.
196
198 LoopInfo *LI, MemorySSA *MSSA = nullptr);
199
200/// Remove the backedge of the specified loop. Handles loop nests and general
201/// loop structures subject to the precondition that the loop has no parent
202/// loop and has a single latch block. Preserves all listed analyses.
204 LoopInfo &LI, MemorySSA *MSSA);
205
206/// Try to promote memory values to scalars by sinking stores out of
207/// the loop and moving loads to before the loop. We do this by looping over
208/// the stores in the loop, looking for stores to Must pointers which are
209/// loop invariant. It takes a set of must-alias values, Loop exit blocks
210/// vector, loop exit blocks insertion point vector, PredIteratorCache,
211/// LoopInfo, DominatorTree, Loop, AliasSet information for all instructions
212/// of the loop and loop safety information as arguments.
213/// Diagnostics is emitted via \p ORE. It returns changed status.
214/// \p AllowSpeculation is whether values should be hoisted even if they are not
215/// guaranteed to execute in the loop, but are safe to speculatively execute.
222 bool AllowSpeculation, bool HasReadsOutsideSet);
223
224/// Does a BFS from a given node to all of its children inside a given loop.
225/// The returned vector of nodes includes the starting point.
227 const Loop *CurLoop);
228
229/// Returns the instructions that use values defined in the loop.
231
232/// Find a combination of metadata ("llvm.loop.vectorize.width" and
233/// "llvm.loop.vectorize.scalable.enable") for a loop and use it to construct a
234/// ElementCount. If the metadata "llvm.loop.vectorize.width" cannot be found
235/// then std::nullopt is returned.
236std::optional<ElementCount>
238
239/// Create a new loop identifier for a loop created from a loop transformation.
240///
241/// @param OrigLoopID The loop ID of the loop before the transformation.
242/// @param FollowupAttrs List of attribute names that contain attributes to be
243/// added to the new loop ID.
244/// @param InheritOptionsAttrsPrefix Selects which attributes should be inherited
245/// from the original loop. The following values
246/// are considered:
247/// nullptr : Inherit all attributes from @p OrigLoopID.
248/// "" : Do not inherit any attribute from @p OrigLoopID; only use
249/// those specified by a followup attribute.
250/// "<prefix>": Inherit all attributes except those which start with
251/// <prefix>; commonly used to remove metadata for the
252/// applied transformation.
253/// @param AlwaysNew If true, do not try to reuse OrigLoopID and never return
254/// std::nullopt.
255///
256/// @return The loop ID for the after-transformation loop. The following values
257/// can be returned:
258/// std::nullopt : No followup attribute was found; it is up to the
259/// transformation to choose attributes that make sense.
260/// @p OrigLoopID: The original identifier can be reused.
261/// nullptr : The new loop has no attributes.
262/// MDNode* : A new unique loop identifier.
263std::optional<MDNode *>
264makeFollowupLoopID(MDNode *OrigLoopID, ArrayRef<StringRef> FollowupAttrs,
265 const char *InheritOptionsAttrsPrefix = "",
266 bool AlwaysNew = false);
267
268/// Look for the loop attribute that disables all transformation heuristic.
269bool hasDisableAllTransformsHint(const Loop *L);
270
271/// Look for the loop attribute that disables the LICM transformation heuristics.
273
274/// The mode sets how eager a transformation should be applied.
276 /// The pass can use heuristics to determine whether a transformation should
277 /// be applied.
279
280 /// The transformation should be applied without considering a cost model.
282
283 /// The transformation should not be applied.
285
286 /// Force is a flag and should not be used alone.
287 TM_Force = 0x04,
288
289 /// The transformation was directed by the user, e.g. by a #pragma in
290 /// the source code. If the transformation could not be applied, a
291 /// warning should be emitted.
293
294 /// The transformation must not be applied. For instance, `#pragma clang loop
295 /// unroll(disable)` explicitly forbids any unrolling to take place. Unlike
296 /// general loop metadata, it must not be dropped. Most passes should not
297 /// behave differently under TM_Disable and TM_SuppressedByUser.
300
301/// @{
302/// Get the mode for LLVM's supported loop transformations.
308/// @}
309
310/// Set input string into loop metadata by keeping other values intact.
311/// If the string is already in loop metadata update value if it is
312/// different.
313void addStringMetadataToLoop(Loop *TheLoop, const char *MDString,
314 unsigned V = 0);
315
316/// Returns a loop's estimated trip count based on branch weight metadata.
317/// In addition if \p EstimatedLoopInvocationWeight is not null it is
318/// initialized with weight of loop's latch leading to the exit.
319/// Returns 0 when the count is estimated to be 0, or std::nullopt when a
320/// meaningful estimate can not be made.
321std::optional<unsigned>
323 unsigned *EstimatedLoopInvocationWeight = nullptr);
324
325/// Set a loop's branch weight metadata to reflect that loop has \p
326/// EstimatedTripCount iterations and \p EstimatedLoopInvocationWeight exits
327/// through latch. Returns true if metadata is successfully updated, false
328/// otherwise. Note that loop must have a latch block which controls loop exit
329/// in order to succeed.
330bool setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount,
331 unsigned EstimatedLoopInvocationWeight);
332
333/// Check inner loop (L) backedge count is known to be invariant on all
334/// iterations of its outer loop. If the loop has no parent, this is trivially
335/// true.
336bool hasIterationCountInvariantInParent(Loop *L, ScalarEvolution &SE);
337
338/// Helper to consistently add the set of standard passes to a loop pass's \c
339/// AnalysisUsage.
340///
341/// All loop passes should call this as part of implementing their \c
342/// getAnalysisUsage.
343void getLoopAnalysisUsage(AnalysisUsage &AU);
344
345/// Returns true if is legal to hoist or sink this instruction disregarding the
346/// possible introduction of faults. Reasoning about potential faulting
347/// instructions is the responsibility of the caller since it is challenging to
348/// do efficiently from within this routine.
349/// \p TargetExecutesOncePerLoop is true only when it is guaranteed that the
350/// target executes at most once per execution of the loop body. This is used
351/// to assess the legality of duplicating atomic loads. Generally, this is
352/// true when moving out of loop and not true when moving into loops.
353/// If \p ORE is set use it to emit optimization remarks.
354bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
355 Loop *CurLoop, MemorySSAUpdater &MSSAU,
356 bool TargetExecutesOncePerLoop,
357 SinkAndHoistLICMFlags &LICMFlags,
358 OptimizationRemarkEmitter *ORE = nullptr);
359
360/// Returns the arithmetic instruction opcode used when expanding a reduction.
362
363/// Returns the min/max intrinsic used when expanding a min/max reduction.
365
366/// Returns the min/max intrinsic used when expanding a min/max reduction.
368
369/// Returns the recurence kind used when expanding a min/max reduction.
371
372/// Returns the comparison predicate used when expanding a min/max reduction.
374
375/// See RecurrenceDescriptor::isAnyOfPattern for a description of the pattern we
376/// are trying to match. In this pattern, we are only ever selecting between two
377/// values: 1) an initial start value \p StartVal of the reduction PHI, and 2) a
378/// loop invariant value. If any of lane value in \p Left, \p Right is not equal
379/// to \p StartVal, select the loop invariant value. This is done by selecting
380/// \p Right iff \p Left is equal to \p StartVal.
381Value *createAnyOfOp(IRBuilderBase &Builder, Value *StartVal, RecurKind RK,
382 Value *Left, Value *Right);
383
384/// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
385/// The Builder's fast-math-flags must be set to propagate the expected values.
386Value *createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left,
387 Value *Right);
388
389/// Generates an ordered vector reduction using extracts to reduce the value.
390Value *getOrderedReduction(IRBuilderBase &Builder, Value *Acc, Value *Src,
391 unsigned Op, RecurKind MinMaxKind = RecurKind::None);
392
393/// Generates a vector reduction using shufflevectors to reduce the value.
394/// Fast-math-flags are propagated using the IRBuilder's setting.
395Value *getShuffleReduction(IRBuilderBase &Builder, Value *Src, unsigned Op,
396 RecurKind MinMaxKind = RecurKind::None);
397
398/// Create a target reduction of the given vector. The reduction operation
399/// is described by the \p Opcode parameter. min/max reductions require
400/// additional information supplied in \p RdxKind.
401/// The target is queried to determine if intrinsics or shuffle sequences are
402/// required to implement the reduction.
403/// Fast-math-flags are propagated using the IRBuilder's setting.
404Value *createSimpleTargetReduction(IRBuilderBase &B, Value *Src,
405 RecurKind RdxKind);
406
407/// Create a target reduction of the given vector \p Src for a reduction of the
408/// kind RecurKind::IAnyOf or RecurKind::FAnyOf. The reduction operation is
409/// described by \p Desc.
410Value *createAnyOfTargetReduction(IRBuilderBase &B, Value *Src,
411 const RecurrenceDescriptor &Desc,
412 PHINode *OrigPhi);
413
414/// Create a generic target reduction using a recurrence descriptor \p Desc
415/// The target is queried to determine if intrinsics or shuffle sequences are
416/// required to implement the reduction.
417/// Fast-math-flags are propagated using the RecurrenceDescriptor.
418Value *createTargetReduction(IRBuilderBase &B, const RecurrenceDescriptor &Desc,
419 Value *Src, PHINode *OrigPhi = nullptr);
420
421/// Create an ordered reduction intrinsic using the given recurrence
422/// descriptor \p Desc.
423Value *createOrderedReduction(IRBuilderBase &B,
424 const RecurrenceDescriptor &Desc, Value *Src,
425 Value *Start);
426
427/// Get the intersection (logical and) of all of the potential IR flags
428/// of each scalar operation (VL) that will be converted into a vector (I).
429/// If OpValue is non-null, we only consider operations similar to OpValue
430/// when intersecting.
431/// Flag set: NSW, NUW (if IncludeWrapFlags is true), exact, and all of
432/// fast-math.
433void propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue = nullptr,
434 bool IncludeWrapFlags = true);
435
436/// Returns true if we can prove that \p S is defined and always negative in
437/// loop \p L.
438bool isKnownNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE);
439
440/// Returns true if we can prove that \p S is defined and always non-negative in
441/// loop \p L.
442bool isKnownNonNegativeInLoop(const SCEV *S, const Loop *L,
443 ScalarEvolution &SE);
444/// Returns true if we can prove that \p S is defined and always positive in
445/// loop \p L.
446bool isKnownPositiveInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE);
447
448/// Returns true if we can prove that \p S is defined and always non-positive in
449/// loop \p L.
450bool isKnownNonPositiveInLoop(const SCEV *S, const Loop *L,
451 ScalarEvolution &SE);
452
453/// Returns true if \p S is defined and never is equal to signed/unsigned max.
454bool cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
455 bool Signed);
456
457/// Returns true if \p S is defined and never is equal to signed/unsigned min.
458bool cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
459 bool Signed);
460
468
469/// If the final value of any expressions that are recurrent in the loop can
470/// be computed, substitute the exit values from the loop into any instructions
471/// outside of the loop that use the final values of the current expressions.
472/// Return the number of loop exit values that have been replaced, and the
473/// corresponding phi node will be added to DeadInsts.
474int rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI,
475 ScalarEvolution *SE, const TargetTransformInfo *TTI,
476 SCEVExpander &Rewriter, DominatorTree *DT,
478 SmallVector<WeakTrackingVH, 16> &DeadInsts);
479
480/// Set weights for \p UnrolledLoop and \p RemainderLoop based on weights for
481/// \p OrigLoop and the following distribution of \p OrigLoop iteration among \p
482/// UnrolledLoop and \p RemainderLoop. \p UnrolledLoop receives weights that
483/// reflect TC/UF iterations, and \p RemainderLoop receives weights that reflect
484/// the remaining TC%UF iterations.
485///
486/// Note that \p OrigLoop may be equal to either \p UnrolledLoop or \p
487/// RemainderLoop in which case weights for \p OrigLoop are updated accordingly.
488/// Note also behavior is undefined if \p UnrolledLoop and \p RemainderLoop are
489/// equal. \p UF must be greater than zero.
490/// If \p OrigLoop has no profile info associated nothing happens.
491///
492/// This utility may be useful for such optimizations as unroller and
493/// vectorizer as it's typical transformation for them.
494void setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop,
495 Loop *RemainderLoop, uint64_t UF);
496
497/// Utility that implements appending of loops onto a worklist given a range.
498/// We want to process loops in postorder, but the worklist is a LIFO data
499/// structure, so we append to it in *reverse* postorder.
500/// For trees, a preorder traversal is a viable reverse postorder, so we
501/// actually append using a preorder walk algorithm.
502template <typename RangeT>
503void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist<Loop *, 4> &);
504/// Utility that implements appending of loops onto a worklist given a range.
505/// It has the same behavior as appendLoopsToWorklist, but assumes the range of
506/// loops has already been reversed, so it processes loops in the given order.
507template <typename RangeT>
508void appendReversedLoopsToWorklist(RangeT &&,
509 SmallPriorityWorklist<Loop *, 4> &);
510
511/// Utility that implements appending of loops onto a worklist given LoopInfo.
512/// Calls the templated utility taking a Range of loops, handing it the Loops
513/// in LoopInfo, iterated in reverse. This is because the loops are stored in
514/// RPO w.r.t. the control flow graph in LoopInfo. For the purpose of unrolling,
515/// loop deletion, and LICM, we largely want to work forward across the CFG so
516/// that we visit defs before uses and can propagate simplifications from one
517/// loop nest into the next. Calls appendReversedLoopsToWorklist with the
518/// already reversed loops in LI.
519/// FIXME: Consider changing the order in LoopInfo.
520void appendLoopsToWorklist(LoopInfo &, SmallPriorityWorklist<Loop *, 4> &);
521
522/// Recursively clone the specified loop and all of its children,
523/// mapping the blocks with the specified map.
524Loop *cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM,
525 LoopInfo *LI, LPPassManager *LPM);
526
527/// Add code that checks at runtime if the accessed arrays in \p PointerChecks
528/// overlap. Returns the final comparator value or NULL if no check is needed.
529Value *
530addRuntimeChecks(Instruction *Loc, Loop *TheLoop,
531 const SmallVectorImpl<RuntimePointerCheck> &PointerChecks,
532 SCEVExpander &Expander, bool HoistRuntimeChecks = false);
533
535 Instruction *Loc, ArrayRef<PointerDiffInfo> Checks, SCEVExpander &Expander,
536 function_ref<Value *(IRBuilderBase &, unsigned)> GetVF, unsigned IC);
537
538/// Struct to hold information about a partially invariant condition.
540 /// Instructions that need to be duplicated and checked for the unswitching
541 /// condition.
543
544 /// Constant to indicate for which value the condition is invariant.
546
547 /// True if the partially invariant path is no-op (=does not have any
548 /// side-effects and no loop value is used outside the loop).
549 bool PathIsNoop = true;
550
551 /// If the partially invariant path reaches a single exit block, ExitForPath
552 /// is set to that block. Otherwise it is nullptr.
554};
555
556/// Check if the loop header has a conditional branch that is not
557/// loop-invariant, because it involves load instructions. If all paths from
558/// either the true or false successor to the header or loop exists do not
559/// modify the memory feeding the condition, perform 'partial unswitching'. That
560/// is, duplicate the instructions feeding the condition in the pre-header. Then
561/// unswitch on the duplicated condition. The condition is now known in the
562/// unswitched version for the 'invariant' path through the original loop.
563///
564/// If the branch condition of the header is partially invariant, return a pair
565/// containing the instructions to duplicate and a boolean Constant to update
566/// the condition in the loops created for the true or false successors.
567std::optional<IVConditionInfo> hasPartialIVCondition(const Loop &L,
568 unsigned MSSAThreshold,
569 const MemorySSA &MSSA,
570 AAResults &AA);
571
572} // end namespace llvm
573
574#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)
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:60
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:965
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: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:1067
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:118
unsigned LicmMssaNoAccForPromotionCap
Definition: LoopUtils.h:137
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:586
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
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:1819
std::optional< unsigned > getLoopEstimatedTripCount(Loop *L, unsigned *EstimatedLoopInvocationWeight=nullptr)
Returns a loop's estimated trip count based on branch weight metadata.
Definition: LoopUtils.cpp:848
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:949
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:1158
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:1275
Value * createSimpleTargetReduction(IRBuilderBase &B, Value *Src, RecurKind RdxKind)
Create a target reduction of the given vector.
Definition: LoopUtils.cpp:1165
void appendReversedLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
Definition: LoopUtils.cpp:1655
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
Definition: LCSSA.cpp:425
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:920
Op::Description Desc
Value * createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left, Value *Right)
Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
Definition: LoopUtils.cpp:1045
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:1293
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:874
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:1087
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:1222
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:723
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:1234
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:1268
TargetTransformInfo TTI
CmpInst::Predicate getMinMaxReductionPredicate(RecurKind RK)
Returns the comparison predicate used when expanding a min/max reduction.
Definition: LoopUtils.cpp:1014
TransformationMode hasLICMVersioningTransformation(const Loop *L)
Definition: LoopUtils.cpp:437
TransformationMode
The mode sets how eager a transformation should be applied.
Definition: LoopUtils.h:275
@ TM_Unspecified
The pass can use heuristics to determine whether a transformation should be applied.
Definition: LoopUtils.h:278
@ TM_SuppressedByUser
The transformation must not be applied.
Definition: LoopUtils.h:298
@ TM_ForcedByUser
The transformation was directed by the user, e.g.
Definition: LoopUtils.h:292
@ TM_Disable
The transformation should not be applied.
Definition: LoopUtils.h:284
@ TM_Force
Force is a flag and should not be used alone.
Definition: LoopUtils.h:287
@ TM_Enable
The transformation should be applied without considering a cost model.
Definition: LoopUtils.h:281
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:866
Value * createAnyOfOp(IRBuilderBase &Builder, Value *StartVal, RecurKind RK, Value *Left, Value *Right)
See RecurrenceDescriptor::isAnyOfPattern for a description of the pattern we are trying to match.
Definition: LoopUtils.cpp:1036
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:1627
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:1680
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:1254
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:77
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:898
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:1415
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:553
Value * addDiffRuntimeChecks(Instruction *Loc, ArrayRef< PointerDiffInfo > Checks, SCEVExpander &Expander, function_ref< Value *(IRBuilderBase &, unsigned)> GetVF, unsigned IC)
Definition: LoopUtils.cpp:1879
RecurKind getMinMaxReductionRecurKind(Intrinsic::ID RdxID)
Returns the recurence kind used when expanding a min/max reduction.
Definition: LoopUtils.cpp:995
ReplaceExitVal
Definition: LoopUtils.h:461
@ UnusedIndVarInLoop
Definition: LoopUtils.h:465
@ OnlyCheapRepl
Definition: LoopUtils.h:463
@ NeverRepl
Definition: LoopUtils.h:462
@ NoHardUse
Definition: LoopUtils.h:464
@ AlwaysRepl
Definition: LoopUtils.h:466
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:1926
bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put loop into LCSSA form.
Definition: LCSSA.cpp:363
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:1961
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:1282
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:1261
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:621
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:1062
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:1206
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:1697
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:1127
#define N
Struct to hold information about a partially invariant condition.
Definition: LoopUtils.h:539
BasicBlock * ExitForPath
If the partially invariant path reaches a single exit block, ExitForPath is set to that block.
Definition: LoopUtils.h:553
SmallVector< Instruction * > InstToDuplicate
Instructions that need to be duplicated and checked for the unswitching condition.
Definition: LoopUtils.h:542
Constant * KnownValue
Constant to indicate for which value the condition is invariant.
Definition: LoopUtils.h:545
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:549