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 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 SmallVector;
53 template <typename T> class SmallVectorImpl;
54 template <typename T, unsigned N> class SmallPriorityWorklist;
55 
56 BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,
57  MemorySSAUpdater *MSSAU, bool PreserveLCSSA);
58 
59 /// Ensure that all exit blocks of the loop are dedicated exits.
60 ///
61 /// For any loop exit block with non-loop predecessors, we split the loop
62 /// predecessors to use a dedicated loop exit block. We update the dominator
63 /// tree and loop info if provided, and will preserve LCSSA if requested.
64 bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
65  MemorySSAUpdater *MSSAU, bool PreserveLCSSA);
66 
67 /// Ensures LCSSA form for every instruction from the Worklist in the scope of
68 /// innermost containing loop.
69 ///
70 /// For the given instruction which have uses outside of the loop, an LCSSA PHI
71 /// node is inserted and the uses outside the loop are rewritten to use this
72 /// node.
73 ///
74 /// LoopInfo and DominatorTree are required and, since the routine makes no
75 /// changes to CFG, preserved.
76 ///
77 /// Returns true if any modifications are made.
78 ///
79 /// This function may introduce unused PHI nodes. If \p PHIsToRemove is not
80 /// nullptr, those are added to it (before removing, the caller has to check if
81 /// they still do not have any uses). Otherwise the PHIs are directly removed.
83  SmallVectorImpl<Instruction *> &Worklist, const DominatorTree &DT,
84  const LoopInfo &LI, ScalarEvolution *SE, IRBuilderBase &Builder,
85  SmallVectorImpl<PHINode *> *PHIsToRemove = nullptr);
86 
87 /// Put loop into LCSSA form.
88 ///
89 /// Looks at all instructions in the loop which have uses outside of the
90 /// current loop. For each, an LCSSA PHI node is inserted and the uses outside
91 /// the loop are rewritten to use this node. Sub-loops must be in LCSSA form
92 /// already.
93 ///
94 /// LoopInfo and DominatorTree are required and preserved.
95 ///
96 /// If ScalarEvolution is passed in, it will be preserved.
97 ///
98 /// Returns true if any modifications are made to the loop.
99 bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI,
100  ScalarEvolution *SE);
101 
102 /// Put a loop nest into LCSSA form.
103 ///
104 /// This recursively forms LCSSA for a loop nest.
105 ///
106 /// LoopInfo and DominatorTree are required and preserved.
107 ///
108 /// If ScalarEvolution is passed in, it will be preserved.
109 ///
110 /// Returns true if any modifications are made to the loop.
111 bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI,
112  ScalarEvolution *SE);
113 
114 /// Flags controlling how much is checked when sinking or hoisting
115 /// instructions. The number of memory access in the loop (and whether there
116 /// are too many) is determined in the constructors when using MemorySSA.
118 public:
119  // Explicitly set limits.
121  unsigned LicmMssaNoAccForPromotionCap, bool IsSink,
122  Loop *L = nullptr, MemorySSA *MSSA = nullptr);
123  // Use default limits.
124  SinkAndHoistLICMFlags(bool IsSink, Loop *L = nullptr,
125  MemorySSA *MSSA = nullptr);
126 
127  void setIsSink(bool B) { IsSink = B; }
128  bool getIsSink() { return IsSink; }
132 
133 protected:
134  bool NoOfMemAccTooLarge = false;
135  unsigned LicmMssaOptCounter = 0;
136  unsigned LicmMssaOptCap;
138  bool IsSink;
139 };
140 
141 /// Walk the specified region of the CFG (defined by all blocks
142 /// dominated by the specified block, and that are in the current loop) in
143 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit
144 /// uses before definitions, allowing us to sink a loop body in one pass without
145 /// iteration. Takes DomTreeNode, AAResults, LoopInfo, DominatorTree,
146 /// BlockFrequencyInfo, TargetLibraryInfo, Loop, AliasSet information for all
147 /// instructions of the loop and loop safety information as
148 /// arguments. Diagnostics is emitted via \p ORE. It returns changed status.
149 /// \p CurLoop is a loop to do sinking on. \p OutermostLoop is used only when
150 /// this function is called by \p sinkRegionForLoopNest.
155  OptimizationRemarkEmitter *, Loop *OutermostLoop = nullptr);
156 
157 /// Call sinkRegion on loops contained within the specified loop
158 /// in order from innermost to outermost.
165 
166 /// Walk the specified region of the CFG (defined by all blocks
167 /// dominated by the specified block, and that are in the current loop) in depth
168 /// first order w.r.t the DominatorTree. This allows us to visit definitions
169 /// before uses, allowing us to hoist a loop body in one pass without iteration.
170 /// Takes DomTreeNode, AAResults, LoopInfo, DominatorTree,
171 /// BlockFrequencyInfo, TargetLibraryInfo, Loop, AliasSet information for all
172 /// instructions of the loop and loop safety information as arguments.
173 /// Diagnostics is emitted via \p ORE. It returns changed status.
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.
213 
214 /// Does a BFS from a given node to all of its children inside a given loop.
215 /// The returned vector of nodes includes the starting point.
217  const Loop *CurLoop);
218 
219 /// Returns the instructions that use values defined in the loop.
221 
222 /// Find a combination of metadata ("llvm.loop.vectorize.width" and
223 /// "llvm.loop.vectorize.scalable.enable") for a loop and use it to construct a
224 /// ElementCount. If the metadata "llvm.loop.vectorize.width" cannot be found
225 /// then None is returned.
228 
229 /// Create a new loop identifier for a loop created from a loop transformation.
230 ///
231 /// @param OrigLoopID The loop ID of the loop before the transformation.
232 /// @param FollowupAttrs List of attribute names that contain attributes to be
233 /// added to the new loop ID.
234 /// @param InheritOptionsAttrsPrefix Selects which attributes should be inherited
235 /// from the original loop. The following values
236 /// are considered:
237 /// nullptr : Inherit all attributes from @p OrigLoopID.
238 /// "" : Do not inherit any attribute from @p OrigLoopID; only use
239 /// those specified by a followup attribute.
240 /// "<prefix>": Inherit all attributes except those which start with
241 /// <prefix>; commonly used to remove metadata for the
242 /// applied transformation.
243 /// @param AlwaysNew If true, do not try to reuse OrigLoopID and never return
244 /// None.
245 ///
246 /// @return The loop ID for the after-transformation loop. The following values
247 /// can be returned:
248 /// None : No followup attribute was found; it is up to the
249 /// transformation to choose attributes that make sense.
250 /// @p OrigLoopID: The original identifier can be reused.
251 /// nullptr : The new loop has no attributes.
252 /// MDNode* : A new unique loop identifier.
254 makeFollowupLoopID(MDNode *OrigLoopID, ArrayRef<StringRef> FollowupAttrs,
255  const char *InheritOptionsAttrsPrefix = "",
256  bool AlwaysNew = false);
257 
258 /// Look for the loop attribute that disables all transformation heuristic.
259 bool hasDisableAllTransformsHint(const Loop *L);
260 
261 /// Look for the loop attribute that disables the LICM transformation heuristics.
262 bool hasDisableLICMTransformsHint(const Loop *L);
263 
264 /// The mode sets how eager a transformation should be applied.
266  /// The pass can use heuristics to determine whether a transformation should
267  /// be applied.
269 
270  /// The transformation should be applied without considering a cost model.
272 
273  /// The transformation should not be applied.
275 
276  /// Force is a flag and should not be used alone.
277  TM_Force = 0x04,
278 
279  /// The transformation was directed by the user, e.g. by a #pragma in
280  /// the source code. If the transformation could not be applied, a
281  /// warning should be emitted.
283 
284  /// The transformation must not be applied. For instance, `#pragma clang loop
285  /// unroll(disable)` explicitly forbids any unrolling to take place. Unlike
286  /// general loop metadata, it must not be dropped. Most passes should not
287  /// behave differently under TM_Disable and TM_SuppressedByUser.
289 };
290 
291 /// @{
292 /// Get the mode for LLVM's supported loop transformations.
298 /// @}
299 
300 /// Set input string into loop metadata by keeping other values intact.
301 /// If the string is already in loop metadata update value if it is
302 /// different.
303 void addStringMetadataToLoop(Loop *TheLoop, const char *MDString,
304  unsigned V = 0);
305 
306 /// Returns a loop's estimated trip count based on branch weight metadata.
307 /// In addition if \p EstimatedLoopInvocationWeight is not null it is
308 /// initialized with weight of loop's latch leading to the exit.
309 /// Returns 0 when the count is estimated to be 0, or None when a meaningful
310 /// estimate can not be made.
311 Optional<unsigned>
313  unsigned *EstimatedLoopInvocationWeight = nullptr);
314 
315 /// Set a loop's branch weight metadata to reflect that loop has \p
316 /// EstimatedTripCount iterations and \p EstimatedLoopInvocationWeight exits
317 /// through latch. Returns true if metadata is successfully updated, false
318 /// otherwise. Note that loop must have a latch block which controls loop exit
319 /// in order to succeed.
320 bool setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount,
321  unsigned EstimatedLoopInvocationWeight);
322 
323 /// Check inner loop (L) backedge count is known to be invariant on all
324 /// iterations of its outer loop. If the loop has no parent, this is trivially
325 /// true.
326 bool hasIterationCountInvariantInParent(Loop *L, ScalarEvolution &SE);
327 
328 /// Helper to consistently add the set of standard passes to a loop pass's \c
329 /// AnalysisUsage.
330 ///
331 /// All loop passes should call this as part of implementing their \c
332 /// getAnalysisUsage.
333 void getLoopAnalysisUsage(AnalysisUsage &AU);
334 
335 /// Returns true if is legal to hoist or sink this instruction disregarding the
336 /// possible introduction of faults. Reasoning about potential faulting
337 /// instructions is the responsibility of the caller since it is challenging to
338 /// do efficiently from within this routine.
339 /// \p TargetExecutesOncePerLoop is true only when it is guaranteed that the
340 /// target executes at most once per execution of the loop body. This is used
341 /// to assess the legality of duplicating atomic loads. Generally, this is
342 /// true when moving out of loop and not true when moving into loops.
343 /// If \p ORE is set use it to emit optimization remarks.
344 bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
345  Loop *CurLoop, AliasSetTracker *CurAST,
346  MemorySSAUpdater *MSSAU, bool TargetExecutesOncePerLoop,
347  SinkAndHoistLICMFlags *LICMFlags = nullptr,
348  OptimizationRemarkEmitter *ORE = nullptr);
349 
350 /// Returns the comparison predicate used when expanding a min/max reduction.
352 
353 /// See RecurrenceDescriptor::isSelectCmpPattern for a description of the
354 /// pattern we are trying to match. In this pattern we are only ever selecting
355 /// between two values: 1) an initial PHI start value, and 2) a loop invariant
356 /// value. This function uses \p LoopExitInst to determine 2), which we then use
357 /// to select between \p Left and \p Right. Any lane value in \p Left that
358 /// matches 2) will be merged into \p Right.
359 Value *createSelectCmpOp(IRBuilderBase &Builder, Value *StartVal, RecurKind RK,
360  Value *Left, Value *Right);
361 
362 /// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
363 /// The Builder's fast-math-flags must be set to propagate the expected values.
364 Value *createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left,
365  Value *Right);
366 
367 /// Generates an ordered vector reduction using extracts to reduce the value.
368 Value *getOrderedReduction(IRBuilderBase &Builder, Value *Acc, Value *Src,
369  unsigned Op, RecurKind MinMaxKind = RecurKind::None);
370 
371 /// Generates a vector reduction using shufflevectors to reduce the value.
372 /// Fast-math-flags are propagated using the IRBuilder's setting.
373 Value *getShuffleReduction(IRBuilderBase &Builder, Value *Src, unsigned Op,
374  RecurKind MinMaxKind = RecurKind::None);
375 
376 /// Create a target reduction of the given vector. The reduction operation
377 /// is described by the \p Opcode parameter. min/max reductions require
378 /// additional information supplied in \p RdxKind.
379 /// The target is queried to determine if intrinsics or shuffle sequences are
380 /// required to implement the reduction.
381 /// Fast-math-flags are propagated using the IRBuilder's setting.
382 Value *createSimpleTargetReduction(IRBuilderBase &B,
383  const TargetTransformInfo *TTI, Value *Src,
384  RecurKind RdxKind);
385 
386 /// Create a target reduction of the given vector \p Src for a reduction of the
387 /// kind RecurKind::SelectICmp or RecurKind::SelectFCmp. The reduction operation
388 /// is described by \p Desc.
389 Value *createSelectCmpTargetReduction(IRBuilderBase &B,
390  const TargetTransformInfo *TTI,
391  Value *Src,
392  const RecurrenceDescriptor &Desc,
393  PHINode *OrigPhi);
394 
395 /// Create a generic target reduction using a recurrence descriptor \p Desc
396 /// The target is queried to determine if intrinsics or shuffle sequences are
397 /// required to implement the reduction.
398 /// Fast-math-flags are propagated using the RecurrenceDescriptor.
399 Value *createTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI,
400  const RecurrenceDescriptor &Desc, Value *Src,
401  PHINode *OrigPhi = nullptr);
402 
403 /// Create an ordered reduction intrinsic using the given recurrence
404 /// descriptor \p Desc.
405 Value *createOrderedReduction(IRBuilderBase &B,
406  const RecurrenceDescriptor &Desc, Value *Src,
407  Value *Start);
408 
409 /// Get the intersection (logical and) of all of the potential IR flags
410 /// of each scalar operation (VL) that will be converted into a vector (I).
411 /// If OpValue is non-null, we only consider operations similar to OpValue
412 /// when intersecting.
413 /// Flag set: NSW, NUW, exact, and all of fast-math.
414 void propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue = nullptr);
415 
416 /// Returns true if we can prove that \p S is defined and always negative in
417 /// loop \p L.
418 bool isKnownNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE);
419 
420 /// Returns true if we can prove that \p S is defined and always non-negative in
421 /// loop \p L.
422 bool isKnownNonNegativeInLoop(const SCEV *S, const Loop *L,
423  ScalarEvolution &SE);
424 
425 /// Returns true if \p S is defined and never is equal to signed/unsigned max.
426 bool cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
427  bool Signed);
428 
429 /// Returns true if \p S is defined and never is equal to signed/unsigned min.
430 bool cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
431  bool Signed);
432 
434 
435 /// If the final value of any expressions that are recurrent in the loop can
436 /// be computed, substitute the exit values from the loop into any instructions
437 /// outside of the loop that use the final values of the current expressions.
438 /// Return the number of loop exit values that have been replaced, and the
439 /// corresponding phi node will be added to DeadInsts.
440 int rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI,
441  ScalarEvolution *SE, const TargetTransformInfo *TTI,
442  SCEVExpander &Rewriter, DominatorTree *DT,
444  SmallVector<WeakTrackingVH, 16> &DeadInsts);
445 
446 /// Set weights for \p UnrolledLoop and \p RemainderLoop based on weights for
447 /// \p OrigLoop and the following distribution of \p OrigLoop iteration among \p
448 /// UnrolledLoop and \p RemainderLoop. \p UnrolledLoop receives weights that
449 /// reflect TC/UF iterations, and \p RemainderLoop receives weights that reflect
450 /// the remaining TC%UF iterations.
451 ///
452 /// Note that \p OrigLoop may be equal to either \p UnrolledLoop or \p
453 /// RemainderLoop in which case weights for \p OrigLoop are updated accordingly.
454 /// Note also behavior is undefined if \p UnrolledLoop and \p RemainderLoop are
455 /// equal. \p UF must be greater than zero.
456 /// If \p OrigLoop has no profile info associated nothing happens.
457 ///
458 /// This utility may be useful for such optimizations as unroller and
459 /// vectorizer as it's typical transformation for them.
460 void setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop,
461  Loop *RemainderLoop, uint64_t UF);
462 
463 /// Utility that implements appending of loops onto a worklist given a range.
464 /// We want to process loops in postorder, but the worklist is a LIFO data
465 /// structure, so we append to it in *reverse* postorder.
466 /// For trees, a preorder traversal is a viable reverse postorder, so we
467 /// actually append using a preorder walk algorithm.
468 template <typename RangeT>
469 void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist<Loop *, 4> &);
470 /// Utility that implements appending of loops onto a worklist given a range.
471 /// It has the same behavior as appendLoopsToWorklist, but assumes the range of
472 /// loops has already been reversed, so it processes loops in the given order.
473 template <typename RangeT>
474 void appendReversedLoopsToWorklist(RangeT &&,
475  SmallPriorityWorklist<Loop *, 4> &);
476 
477 /// Utility that implements appending of loops onto a worklist given LoopInfo.
478 /// Calls the templated utility taking a Range of loops, handing it the Loops
479 /// in LoopInfo, iterated in reverse. This is because the loops are stored in
480 /// RPO w.r.t. the control flow graph in LoopInfo. For the purpose of unrolling,
481 /// loop deletion, and LICM, we largely want to work forward across the CFG so
482 /// that we visit defs before uses and can propagate simplifications from one
483 /// loop nest into the next. Calls appendReversedLoopsToWorklist with the
484 /// already reversed loops in LI.
485 /// FIXME: Consider changing the order in LoopInfo.
486 void appendLoopsToWorklist(LoopInfo &, SmallPriorityWorklist<Loop *, 4> &);
487 
488 /// Recursively clone the specified loop and all of its children,
489 /// mapping the blocks with the specified map.
490 Loop *cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM,
491  LoopInfo *LI, LPPassManager *LPM);
492 
493 /// Add code that checks at runtime if the accessed arrays in \p PointerChecks
494 /// overlap. Returns the final comparator value or NULL if no check is needed.
495 Value *
496 addRuntimeChecks(Instruction *Loc, Loop *TheLoop,
497  const SmallVectorImpl<RuntimePointerCheck> &PointerChecks,
498  SCEVExpander &Expander);
499 
500 /// Struct to hold information about a partially invariant condition.
502  /// Instructions that need to be duplicated and checked for the unswitching
503  /// condition.
505 
506  /// Constant to indicate for which value the condition is invariant.
507  Constant *KnownValue = nullptr;
508 
509  /// True if the partially invariant path is no-op (=does not have any
510  /// side-effects and no loop value is used outside the loop).
511  bool PathIsNoop = true;
512 
513  /// If the partially invariant path reaches a single exit block, ExitForPath
514  /// is set to that block. Otherwise it is nullptr.
516 };
517 
518 /// Check if the loop header has a conditional branch that is not
519 /// loop-invariant, because it involves load instructions. If all paths from
520 /// either the true or false successor to the header or loop exists do not
521 /// modify the memory feeding the condition, perform 'partial unswitching'. That
522 /// is, duplicate the instructions feeding the condition in the pre-header. Then
523 /// unswitch on the duplicated condition. The condition is now known in the
524 /// unswitched version for the 'invariant' path through the original loop.
525 ///
526 /// If the branch condition of the header is partially invariant, return a pair
527 /// containing the instructions to duplicate and a boolean Constant to update
528 /// the condition in the loops created for the true or false successors.
530  MemorySSA &MSSA, AAResults &AA);
531 
532 } // end namespace llvm
533 
534 #endif // LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
llvm::SinkAndHoistLICMFlags::IsSink
bool IsSink
Definition: LoopUtils.h:138
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:361
Signed
@ Signed
Definition: NVPTXISelLowering.cpp:4645
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:1258
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:22
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:1106
llvm::RuntimePointerCheck
std::pair< const RuntimeCheckingPtrGroup *, const RuntimeCheckingPtrGroup * > RuntimePointerCheck
A memcheck which made up of a pair of grouped pointers.
Definition: LoopAccessAnalysis.h:360
ValueMapper.h
llvm::ReplaceExitVal
ReplaceExitVal
Definition: LoopUtils.h:433
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:721
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:959
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:353
llvm::OnlyCheapRepl
@ OnlyCheapRepl
Definition: LoopUtils.h:433
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:1952
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:1425
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:478
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1175
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
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:515
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:272
llvm::SinkAndHoistLICMFlags::tooManyClobberingCalls
bool tooManyClobberingCalls()
Definition: LoopUtils.h:130
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:150
llvm::NeverRepl
@ NeverRepl
Definition: LoopUtils.h:433
llvm::findDefsUsedOutsideOfLoop
SmallVector< Instruction *, 8 > findDefsUsedOutsideOfLoop(Loop *L)
Returns the instructions that use values defined in the loop.
Definition: LoopUtils.cpp:132
llvm::hasDisableLICMTransformsHint
bool hasDisableLICMTransformsHint(const Loop *L)
Look for the loop attribute that disables the LICM transformation heuristics.
Definition: LoopUtils.cpp:357
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:405
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:916
llvm::SinkAndHoistLICMFlags::LicmMssaNoAccForPromotionCap
unsigned LicmMssaNoAccForPromotionCap
Definition: LoopUtils.h:137
llvm::SinkAndHoistLICMFlags::incrementClobberingCalls
void incrementClobberingCalls()
Definition: LoopUtils.h:131
llvm::getMinMaxReductionPredicate
CmpInst::Predicate getMinMaxReductionPredicate(RecurKind RK)
Returns the comparison predicate used when expanding a min/max reduction.
Definition: LoopUtils.cpp:897
llvm::createSimpleTargetReduction
Value * createSimpleTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI, Value *Src, RecurKind RdxKind)
Create a target reduction of the given vector.
Definition: LoopUtils.cpp:1039
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:271
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:436
llvm::SmallVector
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
Definition: SmallVector.h:1102
Rewriter
Virtual Register Rewriter
Definition: VirtRegMap.cpp:237
llvm::AAResults
Definition: AliasAnalysis.h:507
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:934
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:1125
llvm::SinkAndHoistLICMFlags
Flags controlling how much is checked when sinking or hoisting instructions.
Definition: LoopUtils.h:117
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:1139
llvm::NoHardUse
@ NoHardUse
Definition: LoopUtils.h:433
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:1495
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:288
llvm::AArch64CC::PL
@ PL
Definition: AArch64BaseInfo.h:260
llvm::RecurKind::None
@ None
Not a recurrence.
llvm::SinkAndHoistLICMFlags::LicmMssaOptCap
unsigned LicmMssaOptCap
Definition: LoopUtils.h:136
llvm::hasLICMVersioningTransformation
TransformationMode hasLICMVersioningTransformation(const Loop *L)
Definition: LoopUtils.cpp:446
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:1562
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:1132
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:511
llvm::breakLoopBackedge
void breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA)
Remove the backedge of the specified loop.
Definition: LoopUtils.cpp:701
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:135
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:875
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:382
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:55
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:223
llvm::MemorySSA
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:704
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::AlwaysRepl
@ AlwaysRepl
Definition: LoopUtils.h:433
llvm::ValueToValueMapTy
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
Definition: MemorySSAUpdater.h:51
llvm::TM_Disable
@ TM_Disable
The transformation should not be applied.
Definition: LoopUtils.h:274
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:1077
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:507
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:1150
llvm::TM_Unspecified
@ TM_Unspecified
The pass can use heuristics to determine whether a transformation should be applied.
Definition: LoopUtils.h:268
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:504
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:459
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:134
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:1086
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:282
llvm::getOptionalElementCountLoopAttribute
Optional< ElementCount > getOptionalElementCountLoopAttribute(const Loop *TheLoop)
Find a combination of metadata ("llvm.loop.vectorize.width" and "llvm.loop.vectorize....
Definition: LoopUtils.cpp:259
llvm::appendLoopsToWorklist
void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
Definition: LoopUtils.cpp:1478
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:843
llvm::TM_Force
@ TM_Force
Force is a flag and should not be used alone.
Definition: LoopUtils.h:277
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:63
llvm::appendReversedLoopsToWorklist
void appendReversedLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
Definition: LoopUtils.cpp:1453
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:501
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:1617
llvm::createMinMaxOp
Value * createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left, Value *Right)
Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
Definition: LoopUtils.cpp:925
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:1094
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:400
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:306
llvm::SinkAndHoistLICMFlags::setIsSink
void setIsSink(bool B)
Definition: LoopUtils.h:127
llvm::SinkAndHoistLICMFlags::tooManyMemoryAccesses
bool tooManyMemoryAccesses()
Definition: LoopUtils.h:129
MemorySSA
early cse Early CSE w MemorySSA
Definition: EarlyCSE.cpp:1762
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:825
llvm::TransformationMode
TransformationMode
The mode sets how eager a transformation should be applied.
Definition: LoopUtils.h:265
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:999
llvm::SinkAndHoistLICMFlags::getIsSink
bool getIsSink()
Definition: LoopUtils.h:128