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