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/Analysis/IVDescriptors.h" 17 #include "llvm/Analysis/LoopAccessAnalysis.h" 18 #include "llvm/Transforms/Utils/ValueMapper.h" 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 *> 48 RuntimePointerCheck; 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. 80 bool formLCSSAForInstructions( 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. 115 class SinkAndHoistLICMFlags { 116 public: 117 // Explicitly set limits. 118 SinkAndHoistLICMFlags(unsigned LicmMssaOptCap, 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; } 127 bool tooManyMemoryAccesses() { return NoOfMemAccTooLarge; } 128 bool tooManyClobberingCalls() { return LicmMssaOptCounter >= LicmMssaOptCap; } 129 void incrementClobberingCalls() { ++LicmMssaOptCounter; } 130 131 protected: 132 bool NoOfMemAccTooLarge = false; 133 unsigned LicmMssaOptCounter = 0; 134 unsigned LicmMssaOptCap; 135 unsigned LicmMssaNoAccForPromotionCap; 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. 149 bool sinkRegion(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *, 150 BlockFrequencyInfo *, TargetLibraryInfo *, 151 TargetTransformInfo *, Loop *CurLoop, MemorySSAUpdater &, 152 ICFLoopSafetyInfo *, SinkAndHoistLICMFlags &, 153 OptimizationRemarkEmitter *, Loop *OutermostLoop = nullptr); 154 155 /// Call sinkRegion on loops contained within the specified loop 156 /// in order from innermost to outermost. 157 bool sinkRegionForLoopNest(DomTreeNode *, AAResults *, LoopInfo *, 158 DominatorTree *, BlockFrequencyInfo *, 159 TargetLibraryInfo *, TargetTransformInfo *, Loop *, 160 MemorySSAUpdater &, ICFLoopSafetyInfo *, 161 SinkAndHoistLICMFlags &, 162 OptimizationRemarkEmitter *); 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. 174 bool hoistRegion(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *, 175 BlockFrequencyInfo *, TargetLibraryInfo *, Loop *, 176 MemorySSAUpdater &, ScalarEvolution *, ICFLoopSafetyInfo *, 177 SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *, bool, 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 191 void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, 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. 197 void breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE, 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. 210 bool promoteLoopAccessesToScalars( 211 const SmallSetVector<Value *, 8> &, SmallVectorImpl<BasicBlock *> &, 212 SmallVectorImpl<Instruction *> &, SmallVectorImpl<MemoryAccess *> &, 213 PredIteratorCache &, LoopInfo *, DominatorTree *, const TargetLibraryInfo *, 214 Loop *, MemorySSAUpdater &, ICFLoopSafetyInfo *, 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. 219 SmallVector<DomTreeNode *, 16> collectChildrenInLoop(DomTreeNode *N, 220 const Loop *CurLoop); 221 222 /// Returns the instructions that use values defined in the loop. 223 SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L); 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. 229 Optional<ElementCount> 230 getOptionalElementCountLoopAttribute(const Loop *TheLoop); 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. 256 Optional<MDNode *> 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. 268 enum TransformationMode { 269 /// The pass can use heuristics to determine whether a transformation should 270 /// be applied. 271 TM_Unspecified, 272 273 /// The transformation should be applied without considering a cost model. 274 TM_Enable, 275 276 /// The transformation should not be applied. 277 TM_Disable, 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. 285 TM_ForcedByUser = TM_Enable | TM_Force, 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. 291 TM_SuppressedByUser = TM_Disable | TM_Force 292 }; 293 294 /// @{ 295 /// Get the mode for LLVM's supported loop transformations. 296 TransformationMode hasUnrollTransformation(const Loop *L); 297 TransformationMode hasUnrollAndJamTransformation(const Loop *L); 298 TransformationMode hasVectorizeTransformation(const Loop *L); 299 TransformationMode hasDistributeTransformation(const Loop *L); 300 TransformationMode hasLICMVersioningTransformation(const Loop *L); 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> 315 getLoopEstimatedTripCount(Loop *L, 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. 354 CmpInst::Predicate getMinMaxReductionPredicate(RecurKind RK); 355 356 /// See RecurrenceDescriptor::isSelectCmpPattern for a description of the 357 /// pattern we are trying to match. In this pattern we are only ever selecting 358 /// between two values: 1) an initial PHI start value, and 2) a loop invariant 359 /// value. This function uses \p LoopExitInst to determine 2), which we then use 360 /// to select between \p Left and \p Right. Any lane value in \p Left that 361 /// matches 2) will be merged into \p Right. 362 Value *createSelectCmpOp(IRBuilderBase &Builder, Value *StartVal, RecurKind RK, 363 Value *Left, Value *Right); 364 365 /// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind. 366 /// The Builder's fast-math-flags must be set to propagate the expected values. 367 Value *createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left, 368 Value *Right); 369 370 /// Generates an ordered vector reduction using extracts to reduce the value. 371 Value *getOrderedReduction(IRBuilderBase &Builder, Value *Acc, Value *Src, 372 unsigned Op, RecurKind MinMaxKind = RecurKind::None); 373 374 /// Generates a vector reduction using shufflevectors to reduce the value. 375 /// Fast-math-flags are propagated using the IRBuilder's setting. 376 Value *getShuffleReduction(IRBuilderBase &Builder, Value *Src, unsigned Op, 377 RecurKind MinMaxKind = RecurKind::None); 378 379 /// Create a target reduction of the given vector. The reduction operation 380 /// is described by the \p Opcode parameter. min/max reductions require 381 /// additional information supplied in \p RdxKind. 382 /// The target is queried to determine if intrinsics or shuffle sequences are 383 /// required to implement the reduction. 384 /// Fast-math-flags are propagated using the IRBuilder's setting. 385 Value *createSimpleTargetReduction(IRBuilderBase &B, 386 const TargetTransformInfo *TTI, Value *Src, 387 RecurKind RdxKind); 388 389 /// Create a target reduction of the given vector \p Src for a reduction of the 390 /// kind RecurKind::SelectICmp or RecurKind::SelectFCmp. The reduction operation 391 /// is described by \p Desc. 392 Value *createSelectCmpTargetReduction(IRBuilderBase &B, 393 const TargetTransformInfo *TTI, 394 Value *Src, 395 const RecurrenceDescriptor &Desc, 396 PHINode *OrigPhi); 397 398 /// Create a generic target reduction using a recurrence descriptor \p Desc 399 /// The target is queried to determine if intrinsics or shuffle sequences are 400 /// required to implement the reduction. 401 /// Fast-math-flags are propagated using the RecurrenceDescriptor. 402 Value *createTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI, 403 const RecurrenceDescriptor &Desc, Value *Src, 404 PHINode *OrigPhi = nullptr); 405 406 /// Create an ordered reduction intrinsic using the given recurrence 407 /// descriptor \p Desc. 408 Value *createOrderedReduction(IRBuilderBase &B, 409 const RecurrenceDescriptor &Desc, Value *Src, 410 Value *Start); 411 412 /// Get the intersection (logical and) of all of the potential IR flags 413 /// of each scalar operation (VL) that will be converted into a vector (I). 414 /// If OpValue is non-null, we only consider operations similar to OpValue 415 /// when intersecting. 416 /// Flag set: NSW, NUW (if IncludeWrapFlags is true), exact, and all of 417 /// fast-math. 418 void propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue = nullptr, 419 bool IncludeWrapFlags = true); 420 421 /// Returns true if we can prove that \p S is defined and always negative in 422 /// loop \p L. 423 bool isKnownNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE); 424 425 /// Returns true if we can prove that \p S is defined and always non-negative in 426 /// loop \p L. 427 bool isKnownNonNegativeInLoop(const SCEV *S, const Loop *L, 428 ScalarEvolution &SE); 429 430 /// Returns true if \p S is defined and never is equal to signed/unsigned max. 431 bool cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, 432 bool Signed); 433 434 /// Returns true if \p S is defined and never is equal to signed/unsigned min. 435 bool cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, 436 bool Signed); 437 438 enum ReplaceExitVal { 439 NeverRepl, 440 OnlyCheapRepl, 441 NoHardUse, 442 UnusedIndVarInLoop, 443 AlwaysRepl 444 }; 445 446 /// If the final value of any expressions that are recurrent in the loop can 447 /// be computed, substitute the exit values from the loop into any instructions 448 /// outside of the loop that use the final values of the current expressions. 449 /// Return the number of loop exit values that have been replaced, and the 450 /// corresponding phi node will be added to DeadInsts. 451 int rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI, 452 ScalarEvolution *SE, const TargetTransformInfo *TTI, 453 SCEVExpander &Rewriter, DominatorTree *DT, 454 ReplaceExitVal ReplaceExitValue, 455 SmallVector<WeakTrackingVH, 16> &DeadInsts); 456 457 /// Set weights for \p UnrolledLoop and \p RemainderLoop based on weights for 458 /// \p OrigLoop and the following distribution of \p OrigLoop iteration among \p 459 /// UnrolledLoop and \p RemainderLoop. \p UnrolledLoop receives weights that 460 /// reflect TC/UF iterations, and \p RemainderLoop receives weights that reflect 461 /// the remaining TC%UF iterations. 462 /// 463 /// Note that \p OrigLoop may be equal to either \p UnrolledLoop or \p 464 /// RemainderLoop in which case weights for \p OrigLoop are updated accordingly. 465 /// Note also behavior is undefined if \p UnrolledLoop and \p RemainderLoop are 466 /// equal. \p UF must be greater than zero. 467 /// If \p OrigLoop has no profile info associated nothing happens. 468 /// 469 /// This utility may be useful for such optimizations as unroller and 470 /// vectorizer as it's typical transformation for them. 471 void setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop, 472 Loop *RemainderLoop, uint64_t UF); 473 474 /// Utility that implements appending of loops onto a worklist given a range. 475 /// We want to process loops in postorder, but the worklist is a LIFO data 476 /// structure, so we append to it in *reverse* postorder. 477 /// For trees, a preorder traversal is a viable reverse postorder, so we 478 /// actually append using a preorder walk algorithm. 479 template <typename RangeT> 480 void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist<Loop *, 4> &); 481 /// Utility that implements appending of loops onto a worklist given a range. 482 /// It has the same behavior as appendLoopsToWorklist, but assumes the range of 483 /// loops has already been reversed, so it processes loops in the given order. 484 template <typename RangeT> 485 void appendReversedLoopsToWorklist(RangeT &&, 486 SmallPriorityWorklist<Loop *, 4> &); 487 488 /// Utility that implements appending of loops onto a worklist given LoopInfo. 489 /// Calls the templated utility taking a Range of loops, handing it the Loops 490 /// in LoopInfo, iterated in reverse. This is because the loops are stored in 491 /// RPO w.r.t. the control flow graph in LoopInfo. For the purpose of unrolling, 492 /// loop deletion, and LICM, we largely want to work forward across the CFG so 493 /// that we visit defs before uses and can propagate simplifications from one 494 /// loop nest into the next. Calls appendReversedLoopsToWorklist with the 495 /// already reversed loops in LI. 496 /// FIXME: Consider changing the order in LoopInfo. 497 void appendLoopsToWorklist(LoopInfo &, SmallPriorityWorklist<Loop *, 4> &); 498 499 /// Recursively clone the specified loop and all of its children, 500 /// mapping the blocks with the specified map. 501 Loop *cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, 502 LoopInfo *LI, LPPassManager *LPM); 503 504 /// Add code that checks at runtime if the accessed arrays in \p PointerChecks 505 /// overlap. Returns the final comparator value or NULL if no check is needed. 506 Value * 507 addRuntimeChecks(Instruction *Loc, Loop *TheLoop, 508 const SmallVectorImpl<RuntimePointerCheck> &PointerChecks, 509 SCEVExpander &Expander); 510 511 Value * 512 addDiffRuntimeChecks(Instruction *Loc, Loop *TheLoop, 513 ArrayRef<PointerDiffInfo> Checks, SCEVExpander &Expander, 514 function_ref<Value *(IRBuilderBase &, unsigned)> GetVF, 515 unsigned IC); 516 517 /// Struct to hold information about a partially invariant condition. 518 struct IVConditionInfo { 519 /// Instructions that need to be duplicated and checked for the unswitching 520 /// condition. 521 SmallVector<Instruction *> InstToDuplicate; 522 523 /// Constant to indicate for which value the condition is invariant. 524 Constant *KnownValue = nullptr; 525 526 /// True if the partially invariant path is no-op (=does not have any 527 /// side-effects and no loop value is used outside the loop). 528 bool PathIsNoop = true; 529 530 /// If the partially invariant path reaches a single exit block, ExitForPath 531 /// is set to that block. Otherwise it is nullptr. 532 BasicBlock *ExitForPath = nullptr; 533 }; 534 535 /// Check if the loop header has a conditional branch that is not 536 /// loop-invariant, because it involves load instructions. If all paths from 537 /// either the true or false successor to the header or loop exists do not 538 /// modify the memory feeding the condition, perform 'partial unswitching'. That 539 /// is, duplicate the instructions feeding the condition in the pre-header. Then 540 /// unswitch on the duplicated condition. The condition is now known in the 541 /// unswitched version for the 'invariant' path through the original loop. 542 /// 543 /// If the branch condition of the header is partially invariant, return a pair 544 /// containing the instructions to duplicate and a boolean Constant to update 545 /// the condition in the loops created for the true or false successors. 546 Optional<IVConditionInfo> hasPartialIVCondition(Loop &L, unsigned MSSAThreshold, 547 MemorySSA &MSSA, AAResults &AA); 548 549 } // end namespace llvm 550 551 #endif // LLVM_TRANSFORMS_UTILS_LOOPUTILS_H 552