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