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, exact, and all of fast-math.
417 void propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue = nullptr);
418 
419 /// Returns true if we can prove that \p S is defined and always negative in
420 /// loop \p L.
421 bool isKnownNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE);
422 
423 /// Returns true if we can prove that \p S is defined and always non-negative in
424 /// loop \p L.
425 bool isKnownNonNegativeInLoop(const SCEV *S, const Loop *L,
426  ScalarEvolution &SE);
427 
428 /// Returns true if \p S is defined and never is equal to signed/unsigned max.
429 bool cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
430  bool Signed);
431 
432 /// Returns true if \p S is defined and never is equal to signed/unsigned min.
433 bool cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
434  bool Signed);
435 
437 
438 /// If the final value of any expressions that are recurrent in the loop can
439 /// be computed, substitute the exit values from the loop into any instructions
440 /// outside of the loop that use the final values of the current expressions.
441 /// Return the number of loop exit values that have been replaced, and the
442 /// corresponding phi node will be added to DeadInsts.
443 int rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI,
444  ScalarEvolution *SE, const TargetTransformInfo *TTI,
445  SCEVExpander &Rewriter, DominatorTree *DT,
447  SmallVector<WeakTrackingVH, 16> &DeadInsts);
448 
449 /// Set weights for \p UnrolledLoop and \p RemainderLoop based on weights for
450 /// \p OrigLoop and the following distribution of \p OrigLoop iteration among \p
451 /// UnrolledLoop and \p RemainderLoop. \p UnrolledLoop receives weights that
452 /// reflect TC/UF iterations, and \p RemainderLoop receives weights that reflect
453 /// the remaining TC%UF iterations.
454 ///
455 /// Note that \p OrigLoop may be equal to either \p UnrolledLoop or \p
456 /// RemainderLoop in which case weights for \p OrigLoop are updated accordingly.
457 /// Note also behavior is undefined if \p UnrolledLoop and \p RemainderLoop are
458 /// equal. \p UF must be greater than zero.
459 /// If \p OrigLoop has no profile info associated nothing happens.
460 ///
461 /// This utility may be useful for such optimizations as unroller and
462 /// vectorizer as it's typical transformation for them.
463 void setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop,
464  Loop *RemainderLoop, uint64_t UF);
465 
466 /// Utility that implements appending of loops onto a worklist given a range.
467 /// We want to process loops in postorder, but the worklist is a LIFO data
468 /// structure, so we append to it in *reverse* postorder.
469 /// For trees, a preorder traversal is a viable reverse postorder, so we
470 /// actually append using a preorder walk algorithm.
471 template <typename RangeT>
472 void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist<Loop *, 4> &);
473 /// Utility that implements appending of loops onto a worklist given a range.
474 /// It has the same behavior as appendLoopsToWorklist, but assumes the range of
475 /// loops has already been reversed, so it processes loops in the given order.
476 template <typename RangeT>
477 void appendReversedLoopsToWorklist(RangeT &&,
478  SmallPriorityWorklist<Loop *, 4> &);
479 
480 /// Utility that implements appending of loops onto a worklist given LoopInfo.
481 /// Calls the templated utility taking a Range of loops, handing it the Loops
482 /// in LoopInfo, iterated in reverse. This is because the loops are stored in
483 /// RPO w.r.t. the control flow graph in LoopInfo. For the purpose of unrolling,
484 /// loop deletion, and LICM, we largely want to work forward across the CFG so
485 /// that we visit defs before uses and can propagate simplifications from one
486 /// loop nest into the next. Calls appendReversedLoopsToWorklist with the
487 /// already reversed loops in LI.
488 /// FIXME: Consider changing the order in LoopInfo.
489 void appendLoopsToWorklist(LoopInfo &, SmallPriorityWorklist<Loop *, 4> &);
490 
491 /// Recursively clone the specified loop and all of its children,
492 /// mapping the blocks with the specified map.
493 Loop *cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM,
494  LoopInfo *LI, LPPassManager *LPM);
495 
496 /// Add code that checks at runtime if the accessed arrays in \p PointerChecks
497 /// overlap. Returns the final comparator value or NULL if no check is needed.
498 Value *
499 addRuntimeChecks(Instruction *Loc, Loop *TheLoop,
500  const SmallVectorImpl<RuntimePointerCheck> &PointerChecks,
501  SCEVExpander &Expander);
502 
503 Value *
504 addDiffRuntimeChecks(Instruction *Loc, Loop *TheLoop,
505  ArrayRef<PointerDiffInfo> Checks, SCEVExpander &Expander,
506  function_ref<Value *(IRBuilderBase &, unsigned)> GetVF,
507  unsigned IC);
508 
509 /// Struct to hold information about a partially invariant condition.
511  /// Instructions that need to be duplicated and checked for the unswitching
512  /// condition.
514 
515  /// Constant to indicate for which value the condition is invariant.
516  Constant *KnownValue = nullptr;
517 
518  /// True if the partially invariant path is no-op (=does not have any
519  /// side-effects and no loop value is used outside the loop).
520  bool PathIsNoop = true;
521 
522  /// If the partially invariant path reaches a single exit block, ExitForPath
523  /// is set to that block. Otherwise it is nullptr.
525 };
526 
527 /// Check if the loop header has a conditional branch that is not
528 /// loop-invariant, because it involves load instructions. If all paths from
529 /// either the true or false successor to the header or loop exists do not
530 /// modify the memory feeding the condition, perform 'partial unswitching'. That
531 /// is, duplicate the instructions feeding the condition in the pre-header. Then
532 /// unswitch on the duplicated condition. The condition is now known in the
533 /// unswitched version for the 'invariant' path through the original loop.
534 ///
535 /// If the branch condition of the header is partially invariant, return a pair
536 /// containing the instructions to duplicate and a boolean Constant to update
537 /// the condition in the loops created for the true or false successors.
539  MemorySSA &MSSA, AAResults &AA);
540 
541 } // end namespace llvm
542 
543 #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:1252
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:1100
llvm::RuntimePointerCheck
std::pair< const RuntimeCheckingPtrGroup *, const RuntimeCheckingPtrGroup * > RuntimePointerCheck
A memcheck which made up of a pair of grouped pointers.
Definition: LoopAccessAnalysis.h:369
ValueMapper.h
llvm::ReplaceExitVal
ReplaceExitVal
Definition: LoopUtils.h:436
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:953
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:436
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
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:1419
llvm::DomTreeNode
DomTreeNodeBase< BasicBlock > DomTreeNode
Definition: Dominators.h:96
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:167
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:524
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:436
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:910
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:891
llvm::createSimpleTargetReduction
Value * createSimpleTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI, Value *Src, RecurKind RdxKind)
Create a target reduction of the given vector.
Definition: LoopUtils.cpp:1033
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:928
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:1119
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:1133
llvm::NoHardUse
@ NoHardUse
Definition: LoopUtils.h:436
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:1489
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:1126
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:520
llvm::breakLoopBackedge
void breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA)
Remove the backedge of the specified loop.
Definition: LoopUtils.cpp:695
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:869
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:436
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:1071
llvm::IVConditionInfo::KnownValue
Constant * KnownValue
Constant to indicate for which value the condition is invariant.
Definition: LoopUtils.h:516
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:1144
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:162
llvm::IVConditionInfo::InstToDuplicate
SmallVector< Instruction * > InstToDuplicate
Instructions that need to be duplicated and checked for the unswitching condition.
Definition: LoopUtils.h:513
llvm::MDNode
Metadata node.
Definition: Metadata.h:926
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: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: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:1472
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:837
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:1447
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:341
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:510
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:1645
llvm::createMinMaxOp
Value * createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left, Value *Right)
Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
Definition: LoopUtils.cpp:919
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:1088
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:819
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:993
llvm::SinkAndHoistLICMFlags::getIsSink
bool getIsSink()
Definition: LoopUtils.h:126