LLVM  15.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 StringRef;
25 class AnalysisUsage;
26 class TargetTransformInfo;
27 class AAResults;
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 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 /// BlockFrequencyInfo, 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  OptimizationRemarkEmitter *, Loop *OutermostLoop = nullptr);
154 
155 /// Call sinkRegion on loops contained within the specified loop
156 /// in order from innermost to outermost.
163 
164 /// Walk the specified region of the CFG (defined by all blocks
165 /// dominated by the specified block, and that are in the current loop) in depth
166 /// first order w.r.t the DominatorTree. This allows us to visit definitions
167 /// before uses, allowing us to hoist a loop body in one pass without iteration.
168 /// Takes DomTreeNode, AAResults, LoopInfo, DominatorTree,
169 /// BlockFrequencyInfo, TargetLibraryInfo, Loop, AliasSet information for all
170 /// instructions of the loop and loop safety information as arguments.
171 /// Diagnostics is emitted via \p ORE. It returns changed status.
172 /// \p AllowSpeculation is whether values should be hoisted even if they are not
173 /// guaranteed to execute in the loop, but are safe to speculatively execute.
178  bool AllowSpeculation);
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.
208 /// \p AllowSpeculation is whether values should be hoisted even if they are not
209 /// guaranteed to execute in the loop, but are safe to speculatively execute.
215  OptimizationRemarkEmitter *, 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 
439 
440 /// If the final value of any expressions that are recurrent in the loop can
441 /// be computed, substitute the exit values from the loop into any instructions
442 /// outside of the loop that use the final values of the current expressions.
443 /// Return the number of loop exit values that have been replaced, and the
444 /// corresponding phi node will be added to DeadInsts.
445 int rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI,
446  ScalarEvolution *SE, const TargetTransformInfo *TTI,
447  SCEVExpander &Rewriter, DominatorTree *DT,
449  SmallVector<WeakTrackingVH, 16> &DeadInsts);
450 
451 /// Set weights for \p UnrolledLoop and \p RemainderLoop based on weights for
452 /// \p OrigLoop and the following distribution of \p OrigLoop iteration among \p
453 /// UnrolledLoop and \p RemainderLoop. \p UnrolledLoop receives weights that
454 /// reflect TC/UF iterations, and \p RemainderLoop receives weights that reflect
455 /// the remaining TC%UF iterations.
456 ///
457 /// Note that \p OrigLoop may be equal to either \p UnrolledLoop or \p
458 /// RemainderLoop in which case weights for \p OrigLoop are updated accordingly.
459 /// Note also behavior is undefined if \p UnrolledLoop and \p RemainderLoop are
460 /// equal. \p UF must be greater than zero.
461 /// If \p OrigLoop has no profile info associated nothing happens.
462 ///
463 /// This utility may be useful for such optimizations as unroller and
464 /// vectorizer as it's typical transformation for them.
465 void setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop,
466  Loop *RemainderLoop, uint64_t UF);
467 
468 /// Utility that implements appending of loops onto a worklist given a range.
469 /// We want to process loops in postorder, but the worklist is a LIFO data
470 /// structure, so we append to it in *reverse* postorder.
471 /// For trees, a preorder traversal is a viable reverse postorder, so we
472 /// actually append using a preorder walk algorithm.
473 template <typename RangeT>
474 void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist<Loop *, 4> &);
475 /// Utility that implements appending of loops onto a worklist given a range.
476 /// It has the same behavior as appendLoopsToWorklist, but assumes the range of
477 /// loops has already been reversed, so it processes loops in the given order.
478 template <typename RangeT>
479 void appendReversedLoopsToWorklist(RangeT &&,
480  SmallPriorityWorklist<Loop *, 4> &);
481 
482 /// Utility that implements appending of loops onto a worklist given LoopInfo.
483 /// Calls the templated utility taking a Range of loops, handing it the Loops
484 /// in LoopInfo, iterated in reverse. This is because the loops are stored in
485 /// RPO w.r.t. the control flow graph in LoopInfo. For the purpose of unrolling,
486 /// loop deletion, and LICM, we largely want to work forward across the CFG so
487 /// that we visit defs before uses and can propagate simplifications from one
488 /// loop nest into the next. Calls appendReversedLoopsToWorklist with the
489 /// already reversed loops in LI.
490 /// FIXME: Consider changing the order in LoopInfo.
491 void appendLoopsToWorklist(LoopInfo &, SmallPriorityWorklist<Loop *, 4> &);
492 
493 /// Recursively clone the specified loop and all of its children,
494 /// mapping the blocks with the specified map.
495 Loop *cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM,
496  LoopInfo *LI, LPPassManager *LPM);
497 
498 /// Add code that checks at runtime if the accessed arrays in \p PointerChecks
499 /// overlap. Returns the final comparator value or NULL if no check is needed.
500 Value *
501 addRuntimeChecks(Instruction *Loc, Loop *TheLoop,
502  const SmallVectorImpl<RuntimePointerCheck> &PointerChecks,
503  SCEVExpander &Expander);
504 
505 Value *
506 addDiffRuntimeChecks(Instruction *Loc, Loop *TheLoop,
507  ArrayRef<PointerDiffInfo> Checks, SCEVExpander &Expander,
508  function_ref<Value *(IRBuilderBase &, unsigned)> GetVF,
509  unsigned IC);
510 
511 /// Struct to hold information about a partially invariant condition.
513  /// Instructions that need to be duplicated and checked for the unswitching
514  /// condition.
516 
517  /// Constant to indicate for which value the condition is invariant.
518  Constant *KnownValue = nullptr;
519 
520  /// True if the partially invariant path is no-op (=does not have any
521  /// side-effects and no loop value is used outside the loop).
522  bool PathIsNoop = true;
523 
524  /// If the partially invariant path reaches a single exit block, ExitForPath
525  /// is set to that block. Otherwise it is nullptr.
527 };
528 
529 /// Check if the loop header has a conditional branch that is not
530 /// loop-invariant, because it involves load instructions. If all paths from
531 /// either the true or false successor to the header or loop exists do not
532 /// modify the memory feeding the condition, perform 'partial unswitching'. That
533 /// is, duplicate the instructions feeding the condition in the pre-header. Then
534 /// unswitch on the duplicated condition. The condition is now known in the
535 /// unswitched version for the 'invariant' path through the original loop.
536 ///
537 /// If the branch condition of the header is partially invariant, return a pair
538 /// containing the instructions to duplicate and a boolean Constant to update
539 /// the condition in the loops created for the true or false successors.
541  MemorySSA &MSSA, AAResults &AA);
542 
543 } // end namespace llvm
544 
545 #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:335
llvm::hasUnrollTransformation
TransformationMode hasUnrollTransformation(const Loop *L)
Definition: LoopUtils.cpp:355
Signed
@ Signed
Definition: NVPTXISelLowering.cpp:4637
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:1247
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::RuntimePointerCheck
std::pair< const RuntimeCheckingPtrGroup *, const RuntimeCheckingPtrGroup * > RuntimePointerCheck
A memcheck which made up of a pair of grouped pointers.
Definition: LoopAccessAnalysis.h:366
ValueMapper.h
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:947
llvm::hoistRegion
bool hoistRegion(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *, BlockFrequencyInfo *, 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:847
llvm::hasDisableAllTransformsHint
bool hasDisableAllTransformsHint(const Loop *L)
Look for the loop attribute that disables all transformation heuristic.
Definition: LoopUtils.cpp:347
llvm::OnlyCheapRepl
@ OnlyCheapRepl
Definition: LoopUtils.h:438
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
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:1414
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:1094
llvm::deleteDeadLoop
void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI, MemorySSA *MSSA=nullptr)
This function deletes dead loops.
Definition: LoopUtils.cpp:472
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
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:526
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:266
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:144
llvm::NeverRepl
@ NeverRepl
Definition: LoopUtils.h:438
llvm::findDefsUsedOutsideOfLoop
SmallVector< Instruction *, 8 > findDefsUsedOutsideOfLoop(Loop *L)
Returns the instructions that use values defined in the loop.
Definition: LoopUtils.cpp:126
llvm::hasDisableLICMTransformsHint
bool hasDisableLICMTransformsHint(const Loop *L)
Look for the loop attribute that disables the LICM transformation heuristics.
Definition: LoopUtils.cpp:351
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:404
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:904
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:1137
llvm::getMinMaxReductionPredicate
CmpInst::Predicate getMinMaxReductionPredicate(RecurKind RK)
Returns the comparison predicate used when expanding a min/max reduction.
Definition: LoopUtils.cpp:885
llvm::createSimpleTargetReduction
Value * createSimpleTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI, Value *Src, RecurKind RdxKind)
Create a target reduction of the given vector.
Definition: LoopUtils.cpp:1027
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:596
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::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:430
Rewriter
Virtual Register Rewriter
Definition: VirtRegMap.cpp:237
llvm::AAResults
Definition: AliasAnalysis.h:511
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:922
llvm::SinkAndHoistLICMFlags::SinkAndHoistLICMFlags
SinkAndHoistLICMFlags(unsigned LicmMssaOptCap, unsigned LicmMssaNoAccForPromotionCap, bool IsSink, Loop *L=nullptr, MemorySSA *MSSA=nullptr)
Definition: LICM.cpp:358
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:1114
llvm::SinkAndHoistLICMFlags
Flags controlling how much is checked when sinking or hoisting instructions.
Definition: LoopUtils.h:115
llvm::promoteLoopAccessesToScalars
bool promoteLoopAccessesToScalars(const SmallSetVector< Value *, 8 > &, SmallVectorImpl< BasicBlock * > &, SmallVectorImpl< Instruction * > &, SmallVectorImpl< MemoryAccess * > &, PredIteratorCache &, LoopInfo *, DominatorTree *, const TargetLibraryInfo *, 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:1907
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:1128
llvm::NoHardUse
@ NoHardUse
Definition: LoopUtils.h:438
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:1484
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:440
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:1556
IVDescriptors.h
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:1121
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:522
llvm::breakLoopBackedge
void breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA)
Remove the backedge of the specified loop.
Definition: LoopUtils.cpp:689
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:863
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:376
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:217
llvm::MemorySSA
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::AlwaysRepl
@ AlwaysRepl
Definition: LoopUtils.h:438
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:1065
llvm::IVConditionInfo::KnownValue
Constant * KnownValue
Constant to indicate for which value the condition is invariant.
Definition: LoopUtils.h:518
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:1139
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:163
llvm::IVConditionInfo::InstToDuplicate
SmallVector< Instruction * > InstToDuplicate
Instructions that need to be duplicated and checked for the unswitching condition.
Definition: LoopUtils.h:515
llvm::MDNode
Metadata node.
Definition: Metadata.h:937
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:453
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::SinkAndHoistLICMFlags::NoOfMemAccTooLarge
bool NoOfMemAccTooLarge
Definition: LoopUtils.h:132
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:1102
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: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:253
llvm::appendLoopsToWorklist
void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
Definition: LoopUtils.cpp:1467
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:831
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::cl::Optional
@ Optional
Definition: CommandLine.h:115
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:57
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:1442
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:345
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:222
llvm::IVConditionInfo
Struct to hold information about a partially invariant condition.
Definition: LoopUtils.h:512
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:1650
llvm::createMinMaxOp
Value * createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left, Value *Right)
Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
Definition: LoopUtils.cpp:913
AA
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:1082
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:394
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:1775
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:813
llvm::addDiffRuntimeChecks
Value * addDiffRuntimeChecks(Instruction *Loc, Loop *TheLoop, ArrayRef< PointerDiffInfo > Checks, SCEVExpander &Expander, function_ref< Value *(IRBuilderBase &, unsigned)> GetVF, unsigned IC)
Definition: LoopUtils.cpp:1611
llvm::TransformationMode
TransformationMode
The mode sets how eager a transformation should be applied.
Definition: LoopUtils.h:268
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:528
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:987
llvm::SinkAndHoistLICMFlags::getIsSink
bool getIsSink()
Definition: LoopUtils.h:126