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 a Min/Max operation corresponding to MinMaxRecurrenceKind.
352 /// The Builder's fast-math-flags must be set to propagate the expected values.
353 Value *createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left,
354  Value *Right);
355 
356 /// Generates an ordered vector reduction using extracts to reduce the value.
357 Value *getOrderedReduction(IRBuilderBase &Builder, Value *Acc, Value *Src,
358  unsigned Op, RecurKind MinMaxKind = RecurKind::None,
359  ArrayRef<Value *> RedOps = None);
360 
361 /// Generates a vector reduction using shufflevectors to reduce the value.
362 /// Fast-math-flags are propagated using the IRBuilder's setting.
363 Value *getShuffleReduction(IRBuilderBase &Builder, Value *Src, unsigned Op,
364  RecurKind MinMaxKind = RecurKind::None,
365  ArrayRef<Value *> RedOps = None);
366 
367 /// Create a target reduction of the given vector. The reduction operation
368 /// is described by the \p Opcode parameter. min/max reductions require
369 /// additional information supplied in \p RdxKind.
370 /// The target is queried to determine if intrinsics or shuffle sequences are
371 /// required to implement the reduction.
372 /// Fast-math-flags are propagated using the IRBuilder's setting.
373 Value *createSimpleTargetReduction(IRBuilderBase &B,
374  const TargetTransformInfo *TTI, Value *Src,
375  RecurKind RdxKind,
376  ArrayRef<Value *> RedOps = None);
377 
378 /// Create a generic target reduction using a recurrence descriptor \p Desc
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 RecurrenceDescriptor.
382 Value *createTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI,
383  const RecurrenceDescriptor &Desc, Value *Src);
384 
385 /// Create an ordered reduction intrinsic using the given recurrence
386 /// descriptor \p Desc.
387 Value *createOrderedReduction(IRBuilderBase &B,
388  const RecurrenceDescriptor &Desc, Value *Src,
389  Value *Start);
390 
391 /// Get the intersection (logical and) of all of the potential IR flags
392 /// of each scalar operation (VL) that will be converted into a vector (I).
393 /// If OpValue is non-null, we only consider operations similar to OpValue
394 /// when intersecting.
395 /// Flag set: NSW, NUW, exact, and all of fast-math.
396 void propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue = nullptr);
397 
398 /// Returns true if we can prove that \p S is defined and always negative in
399 /// loop \p L.
400 bool isKnownNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE);
401 
402 /// Returns true if we can prove that \p S is defined and always non-negative in
403 /// loop \p L.
404 bool isKnownNonNegativeInLoop(const SCEV *S, const Loop *L,
405  ScalarEvolution &SE);
406 
407 /// Returns true if \p S is defined and never is equal to signed/unsigned max.
408 bool cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
409  bool Signed);
410 
411 /// Returns true if \p S is defined and never is equal to signed/unsigned min.
412 bool cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
413  bool Signed);
414 
416 
417 /// If the final value of any expressions that are recurrent in the loop can
418 /// be computed, substitute the exit values from the loop into any instructions
419 /// outside of the loop that use the final values of the current expressions.
420 /// Return the number of loop exit values that have been replaced, and the
421 /// corresponding phi node will be added to DeadInsts.
422 int rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI,
423  ScalarEvolution *SE, const TargetTransformInfo *TTI,
424  SCEVExpander &Rewriter, DominatorTree *DT,
426  SmallVector<WeakTrackingVH, 16> &DeadInsts);
427 
428 /// Set weights for \p UnrolledLoop and \p RemainderLoop based on weights for
429 /// \p OrigLoop and the following distribution of \p OrigLoop iteration among \p
430 /// UnrolledLoop and \p RemainderLoop. \p UnrolledLoop receives weights that
431 /// reflect TC/UF iterations, and \p RemainderLoop receives weights that reflect
432 /// the remaining TC%UF iterations.
433 ///
434 /// Note that \p OrigLoop may be equal to either \p UnrolledLoop or \p
435 /// RemainderLoop in which case weights for \p OrigLoop are updated accordingly.
436 /// Note also behavior is undefined if \p UnrolledLoop and \p RemainderLoop are
437 /// equal. \p UF must be greater than zero.
438 /// If \p OrigLoop has no profile info associated nothing happens.
439 ///
440 /// This utility may be useful for such optimizations as unroller and
441 /// vectorizer as it's typical transformation for them.
442 void setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop,
443  Loop *RemainderLoop, uint64_t UF);
444 
445 /// Utility that implements appending of loops onto a worklist given a range.
446 /// We want to process loops in postorder, but the worklist is a LIFO data
447 /// structure, so we append to it in *reverse* postorder.
448 /// For trees, a preorder traversal is a viable reverse postorder, so we
449 /// actually append using a preorder walk algorithm.
450 template <typename RangeT>
451 void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist<Loop *, 4> &);
452 /// Utility that implements appending of loops onto a worklist given a range.
453 /// It has the same behavior as appendLoopsToWorklist, but assumes the range of
454 /// loops has already been reversed, so it processes loops in the given order.
455 template <typename RangeT>
456 void appendReversedLoopsToWorklist(RangeT &&,
457  SmallPriorityWorklist<Loop *, 4> &);
458 
459 /// Utility that implements appending of loops onto a worklist given LoopInfo.
460 /// Calls the templated utility taking a Range of loops, handing it the Loops
461 /// in LoopInfo, iterated in reverse. This is because the loops are stored in
462 /// RPO w.r.t. the control flow graph in LoopInfo. For the purpose of unrolling,
463 /// loop deletion, and LICM, we largely want to work forward across the CFG so
464 /// that we visit defs before uses and can propagate simplifications from one
465 /// loop nest into the next. Calls appendReversedLoopsToWorklist with the
466 /// already reversed loops in LI.
467 /// FIXME: Consider changing the order in LoopInfo.
468 void appendLoopsToWorklist(LoopInfo &, SmallPriorityWorklist<Loop *, 4> &);
469 
470 /// Recursively clone the specified loop and all of its children,
471 /// mapping the blocks with the specified map.
472 Loop *cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM,
473  LoopInfo *LI, LPPassManager *LPM);
474 
475 /// Add code that checks at runtime if the accessed arrays in \p PointerChecks
476 /// overlap.
477 ///
478 /// Returns a pair of instructions where the first element is the first
479 /// instruction generated in possibly a sequence of instructions and the
480 /// second value is the final comparator value or NULL if no check is needed.
481 std::pair<Instruction *, Instruction *>
482 addRuntimeChecks(Instruction *Loc, Loop *TheLoop,
483  const SmallVectorImpl<RuntimePointerCheck> &PointerChecks,
484  SCEVExpander &Expander);
485 
486 /// Struct to hold information about a partially invariant condition.
488  /// Instructions that need to be duplicated and checked for the unswitching
489  /// condition.
491 
492  /// Constant to indicate for which value the condition is invariant.
493  Constant *KnownValue = nullptr;
494 
495  /// True if the partially invariant path is no-op (=does not have any
496  /// side-effects and no loop value is used outside the loop).
497  bool PathIsNoop = true;
498 
499  /// If the partially invariant path reaches a single exit block, ExitForPath
500  /// is set to that block. Otherwise it is nullptr.
502 };
503 
504 /// Check if the loop header has a conditional branch that is not
505 /// loop-invariant, because it involves load instructions. If all paths from
506 /// either the true or false successor to the header or loop exists do not
507 /// modify the memory feeding the condition, perform 'partial unswitching'. That
508 /// is, duplicate the instructions feeding the condition in the pre-header. Then
509 /// unswitch on the duplicated condition. The condition is now known in the
510 /// unswitched version for the 'invariant' path through the original loop.
511 ///
512 /// If the branch condition of the header is partially invariant, return a pair
513 /// containing the instructions to duplicate and a boolean Constant to update
514 /// the condition in the loops created for the true or false successors.
516  MemorySSA &MSSA, AAResults &AA);
517 
518 } // end namespace llvm
519 
520 #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:4636
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:1208
llvm
---------------------— PointerInfo ------------------------------------—
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:1056
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:415
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:856
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:415
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:1984
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:1376
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: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:576
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:461
llvm::IVConditionInfo::ExitForPath
BasicBlock * ExitForPath
If the partially invariant path reaches a single exit block, ExitForPath is set to that block.
Definition: LoopUtils.h:501
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:415
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:953
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::SinkAndHoistLICMFlags::LicmMssaNoAccForPromotionCap
unsigned LicmMssaNoAccForPromotionCap
Definition: LoopUtils.h:138
llvm::SinkAndHoistLICMFlags::incrementClobberingCalls
void incrementClobberingCalls()
Definition: LoopUtils.h:132
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:38
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:924
llvm::AAResults
Definition: AliasAnalysis.h:456
llvm::SinkAndHoistLICMFlags::SinkAndHoistLICMFlags
SinkAndHoistLICMFlags(unsigned LicmMssaOptCap, unsigned LicmMssaNoAccForPromotionCap, bool IsSink, Loop *L=nullptr, MemorySSA *MSSA=nullptr)
Definition: LICM.cpp:338
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:1075
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:1089
llvm::NoHardUse
@ NoHardUse
Definition: LoopUtils.h:415
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:1446
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
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:1082
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:497
llvm::breakLoopBackedge
void breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA)
Remove the backedge of the specified loop.
Definition: LoopUtils.cpp:704
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:507
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:870
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:415
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::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:1154
llvm::IVConditionInfo::KnownValue
Constant * KnownValue
Constant to indicate for which value the condition is invariant.
Definition: LoopUtils.h:493
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:1100
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:163
llvm::IVConditionInfo::InstToDuplicate
SmallVector< Instruction * > InstToDuplicate
Instructions that need to be duplicated and checked for the unswitching condition.
Definition: LoopUtils.h:490
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:1429
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:839
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:1404
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
llvm::ICFLoopSafetyInfo
This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to give precise answers on "may...
Definition: MustExecute.h:132
llvm::addRuntimeChecks
std::pair< Instruction *, Instruction * > 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:1514
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:219
llvm::IVConditionInfo
Struct to hold information about a partially invariant condition.
Definition: LoopUtils.h:487
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:1593
llvm::createMinMaxOp
Value * createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left, Value *Right)
Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
Definition: LoopUtils.cpp:892
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:1045
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::createTargetReduction
Value * createTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI, const RecurrenceDescriptor &Desc, Value *Src)
Create a generic target reduction using a recurrence descriptor Desc The target is queried to determi...
Definition: LoopUtils.cpp:1033
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:995
MemorySSA
early cse Early CSE w MemorySSA
Definition: EarlyCSE.cpp:1745
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:807
llvm::TransformationMode
TransformationMode
The mode sets how eager a transformation should be applied.
Definition: LoopUtils.h:266
llvm::SinkAndHoistLICMFlags::getIsSink
bool getIsSink()
Definition: LoopUtils.h:129