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/Analysis/TargetTransformInfo.h" 19 #include "llvm/Support/Compiler.h" 20 #include "llvm/Transforms/Utils/ValueMapper.h" 21 22 namespace llvm { 23 24 template <typename T> class DomTreeNodeBase; 25 using DomTreeNode = DomTreeNodeBase<BasicBlock>; 26 class AssumptionCache; 27 class StringRef; 28 class AnalysisUsage; 29 class TargetTransformInfo; 30 class AAResults; 31 class BasicBlock; 32 class ICFLoopSafetyInfo; 33 class IRBuilderBase; 34 class Loop; 35 class LoopInfo; 36 class MemoryAccess; 37 class MemorySSA; 38 class MemorySSAUpdater; 39 class OptimizationRemarkEmitter; 40 class PredIteratorCache; 41 class ScalarEvolution; 42 class SCEV; 43 class SCEVExpander; 44 class TargetLibraryInfo; 45 class LPPassManager; 46 class Instruction; 47 struct RuntimeCheckingPtrGroup; 48 typedef std::pair<const RuntimeCheckingPtrGroup *, 49 const RuntimeCheckingPtrGroup *> 50 RuntimePointerCheck; 51 52 template <typename T, unsigned N> class SmallSetVector; 53 template <typename T, unsigned N> class SmallPriorityWorklist; 54 55 LLVM_ABI BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, 56 LoopInfo *LI, 57 MemorySSAUpdater *MSSAU, 58 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 LLVM_ABI bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, 66 MemorySSAUpdater *MSSAU, 67 bool PreserveLCSSA); 68 69 /// Ensures LCSSA form for every instruction from the Worklist in the scope of 70 /// innermost containing loop. 71 /// 72 /// For the given instruction which have uses outside of the loop, an LCSSA PHI 73 /// node is inserted and the uses outside the loop are rewritten to use this 74 /// node. 75 /// 76 /// LoopInfo and DominatorTree are required and, since the routine makes no 77 /// changes to CFG, preserved. 78 /// 79 /// Returns true if any modifications are made. 80 /// 81 /// This function may introduce unused PHI nodes. If \p PHIsToRemove is not 82 /// nullptr, those are added to it (before removing, the caller has to check if 83 /// they still do not have any uses). Otherwise the PHIs are directly removed. 84 /// 85 /// If \p InsertedPHIs is not nullptr, inserted phis will be added to this 86 /// vector. 87 LLVM_ABI bool 88 formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist, 89 const DominatorTree &DT, const LoopInfo &LI, 90 ScalarEvolution *SE, 91 SmallVectorImpl<PHINode *> *PHIsToRemove = nullptr, 92 SmallVectorImpl<PHINode *> *InsertedPHIs = nullptr); 93 94 /// Put loop into LCSSA form. 95 /// 96 /// Looks at all instructions in the loop which have uses outside of the 97 /// current loop. For each, an LCSSA PHI node is inserted and the uses outside 98 /// the loop are rewritten to use this node. Sub-loops must be in LCSSA form 99 /// already. 100 /// 101 /// LoopInfo and DominatorTree are required and preserved. 102 /// 103 /// If ScalarEvolution is passed in, it will be preserved. 104 /// 105 /// Returns true if any modifications are made to the loop. 106 LLVM_ABI bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI, 107 ScalarEvolution *SE); 108 109 /// Put a loop nest into LCSSA form. 110 /// 111 /// This recursively forms LCSSA for a loop nest. 112 /// 113 /// LoopInfo and DominatorTree are required and preserved. 114 /// 115 /// If ScalarEvolution is passed in, it will be preserved. 116 /// 117 /// Returns true if any modifications are made to the loop. 118 LLVM_ABI bool formLCSSARecursively(Loop &L, const DominatorTree &DT, 119 const LoopInfo *LI, ScalarEvolution *SE); 120 121 /// Flags controlling how much is checked when sinking or hoisting 122 /// instructions. The number of memory access in the loop (and whether there 123 /// are too many) is determined in the constructors when using MemorySSA. 124 class SinkAndHoistLICMFlags { 125 public: 126 // Explicitly set limits. 127 LLVM_ABI SinkAndHoistLICMFlags(unsigned LicmMssaOptCap, 128 unsigned LicmMssaNoAccForPromotionCap, 129 bool IsSink, Loop &L, MemorySSA &MSSA); 130 // Use default limits. 131 LLVM_ABI SinkAndHoistLICMFlags(bool IsSink, Loop &L, MemorySSA &MSSA); 132 setIsSink(bool B)133 void setIsSink(bool B) { IsSink = B; } getIsSink()134 bool getIsSink() { return IsSink; } tooManyMemoryAccesses()135 bool tooManyMemoryAccesses() { return NoOfMemAccTooLarge; } tooManyClobberingCalls()136 bool tooManyClobberingCalls() { return LicmMssaOptCounter >= LicmMssaOptCap; } incrementClobberingCalls()137 void incrementClobberingCalls() { ++LicmMssaOptCounter; } 138 139 protected: 140 bool NoOfMemAccTooLarge = false; 141 unsigned LicmMssaOptCounter = 0; 142 unsigned LicmMssaOptCap; 143 unsigned LicmMssaNoAccForPromotionCap; 144 bool IsSink; 145 }; 146 147 /// Walk the specified region of the CFG (defined by all blocks 148 /// dominated by the specified block, and that are in the current loop) in 149 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit 150 /// uses before definitions, allowing us to sink a loop body in one pass without 151 /// iteration. Takes DomTreeNode, AAResults, LoopInfo, DominatorTree, 152 /// TargetLibraryInfo, Loop, AliasSet information for all 153 /// instructions of the loop and loop safety information as 154 /// arguments. Diagnostics is emitted via \p ORE. It returns changed status. 155 /// \p CurLoop is a loop to do sinking on. \p OutermostLoop is used only when 156 /// this function is called by \p sinkRegionForLoopNest. 157 LLVM_ABI bool sinkRegion(DomTreeNode *, AAResults *, LoopInfo *, 158 DominatorTree *, TargetLibraryInfo *, 159 TargetTransformInfo *, Loop *CurLoop, 160 MemorySSAUpdater &, ICFLoopSafetyInfo *, 161 SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *, 162 Loop *OutermostLoop = nullptr); 163 164 /// Call sinkRegion on loops contained within the specified loop 165 /// in order from innermost to outermost. 166 LLVM_ABI bool sinkRegionForLoopNest(DomTreeNode *, AAResults *, LoopInfo *, 167 DominatorTree *, TargetLibraryInfo *, 168 TargetTransformInfo *, Loop *, 169 MemorySSAUpdater &, ICFLoopSafetyInfo *, 170 SinkAndHoistLICMFlags &, 171 OptimizationRemarkEmitter *); 172 173 /// Walk the specified region of the CFG (defined by all blocks 174 /// dominated by the specified block, and that are in the current loop) in depth 175 /// first order w.r.t the DominatorTree. This allows us to visit definitions 176 /// before uses, allowing us to hoist a loop body in one pass without iteration. 177 /// Takes DomTreeNode, AAResults, LoopInfo, DominatorTree, 178 /// TargetLibraryInfo, Loop, AliasSet information for all 179 /// instructions of the loop and loop safety information as arguments. 180 /// Diagnostics is emitted via \p ORE. It returns changed status. 181 /// \p AllowSpeculation is whether values should be hoisted even if they are not 182 /// guaranteed to execute in the loop, but are safe to speculatively execute. 183 LLVM_ABI bool hoistRegion(DomTreeNode *, AAResults *, LoopInfo *, 184 DominatorTree *, AssumptionCache *, 185 TargetLibraryInfo *, Loop *, MemorySSAUpdater &, 186 ScalarEvolution *, ICFLoopSafetyInfo *, 187 SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *, 188 bool, bool AllowSpeculation); 189 190 /// Return true if the induction variable \p IV in a Loop whose latch is 191 /// \p LatchBlock would become dead if the exit test \p Cond were removed. 192 /// Conservatively returns false if analysis is insufficient. 193 LLVM_ABI bool isAlmostDeadIV(PHINode *IV, BasicBlock *LatchBlock, Value *Cond); 194 195 /// This function deletes dead loops. The caller of this function needs to 196 /// guarantee that the loop is infact dead. 197 /// The function requires a bunch or prerequisites to be present: 198 /// - The loop needs to be in LCSSA form 199 /// - The loop needs to have a Preheader 200 /// - A unique dedicated exit block must exist 201 /// 202 /// This also updates the relevant analysis information in \p DT, \p SE, \p LI 203 /// and \p MSSA if pointers to those are provided. 204 /// It also updates the loop PM if an updater struct is provided. 205 206 LLVM_ABI void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, 207 LoopInfo *LI, MemorySSA *MSSA = nullptr); 208 209 /// Remove the backedge of the specified loop. Handles loop nests and general 210 /// loop structures subject to the precondition that the loop has no parent 211 /// loop and has a single latch block. Preserves all listed analyses. 212 LLVM_ABI void breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE, 213 LoopInfo &LI, MemorySSA *MSSA); 214 215 /// Try to promote memory values to scalars by sinking stores out of 216 /// the loop and moving loads to before the loop. We do this by looping over 217 /// the stores in the loop, looking for stores to Must pointers which are 218 /// loop invariant. It takes a set of must-alias values, Loop exit blocks 219 /// vector, loop exit blocks insertion point vector, PredIteratorCache, 220 /// LoopInfo, DominatorTree, Loop, AliasSet information for all instructions 221 /// of the loop and loop safety information as arguments. 222 /// Diagnostics is emitted via \p ORE. It returns changed status. 223 /// \p AllowSpeculation is whether values should be hoisted even if they are not 224 /// guaranteed to execute in the loop, but are safe to speculatively execute. 225 LLVM_ABI bool promoteLoopAccessesToScalars( 226 const SmallSetVector<Value *, 8> &, SmallVectorImpl<BasicBlock *> &, 227 SmallVectorImpl<BasicBlock::iterator> &, SmallVectorImpl<MemoryAccess *> &, 228 PredIteratorCache &, LoopInfo *, DominatorTree *, AssumptionCache *AC, 229 const TargetLibraryInfo *, TargetTransformInfo *, Loop *, 230 MemorySSAUpdater &, ICFLoopSafetyInfo *, OptimizationRemarkEmitter *, 231 bool AllowSpeculation, bool HasReadsOutsideSet); 232 233 /// Does a BFS from a given node to all of its children inside a given loop. 234 /// The returned vector of basic blocks includes the starting point. 235 LLVM_ABI SmallVector<BasicBlock *, 16> 236 collectChildrenInLoop(DominatorTree *DT, DomTreeNode *N, const Loop *CurLoop); 237 238 /// Returns the instructions that use values defined in the loop. 239 LLVM_ABI SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L); 240 241 /// Find a combination of metadata ("llvm.loop.vectorize.width" and 242 /// "llvm.loop.vectorize.scalable.enable") for a loop and use it to construct a 243 /// ElementCount. If the metadata "llvm.loop.vectorize.width" cannot be found 244 /// then std::nullopt is returned. 245 LLVM_ABI std::optional<ElementCount> 246 getOptionalElementCountLoopAttribute(const Loop *TheLoop); 247 248 /// Create a new loop identifier for a loop created from a loop transformation. 249 /// 250 /// @param OrigLoopID The loop ID of the loop before the transformation. 251 /// @param FollowupAttrs List of attribute names that contain attributes to be 252 /// added to the new loop ID. 253 /// @param InheritOptionsAttrsPrefix Selects which attributes should be inherited 254 /// from the original loop. The following values 255 /// are considered: 256 /// nullptr : Inherit all attributes from @p OrigLoopID. 257 /// "" : Do not inherit any attribute from @p OrigLoopID; only use 258 /// those specified by a followup attribute. 259 /// "<prefix>": Inherit all attributes except those which start with 260 /// <prefix>; commonly used to remove metadata for the 261 /// applied transformation. 262 /// @param AlwaysNew If true, do not try to reuse OrigLoopID and never return 263 /// std::nullopt. 264 /// 265 /// @return The loop ID for the after-transformation loop. The following values 266 /// can be returned: 267 /// std::nullopt : No followup attribute was found; it is up to the 268 /// transformation to choose attributes that make sense. 269 /// @p OrigLoopID: The original identifier can be reused. 270 /// nullptr : The new loop has no attributes. 271 /// MDNode* : A new unique loop identifier. 272 LLVM_ABI std::optional<MDNode *> 273 makeFollowupLoopID(MDNode *OrigLoopID, ArrayRef<StringRef> FollowupAttrs, 274 const char *InheritOptionsAttrsPrefix = "", 275 bool AlwaysNew = false); 276 277 /// Look for the loop attribute that disables all transformation heuristic. 278 LLVM_ABI bool hasDisableAllTransformsHint(const Loop *L); 279 280 /// Look for the loop attribute that disables the LICM transformation heuristics. 281 LLVM_ABI bool hasDisableLICMTransformsHint(const Loop *L); 282 283 /// The mode sets how eager a transformation should be applied. 284 enum TransformationMode { 285 /// The pass can use heuristics to determine whether a transformation should 286 /// be applied. 287 TM_Unspecified, 288 289 /// The transformation should be applied without considering a cost model. 290 TM_Enable, 291 292 /// The transformation should not be applied. 293 TM_Disable, 294 295 /// Force is a flag and should not be used alone. 296 TM_Force = 0x04, 297 298 /// The transformation was directed by the user, e.g. by a #pragma in 299 /// the source code. If the transformation could not be applied, a 300 /// warning should be emitted. 301 TM_ForcedByUser = TM_Enable | TM_Force, 302 303 /// The transformation must not be applied. For instance, `#pragma clang loop 304 /// unroll(disable)` explicitly forbids any unrolling to take place. Unlike 305 /// general loop metadata, it must not be dropped. Most passes should not 306 /// behave differently under TM_Disable and TM_SuppressedByUser. 307 TM_SuppressedByUser = TM_Disable | TM_Force 308 }; 309 310 /// @{ 311 /// Get the mode for LLVM's supported loop transformations. 312 LLVM_ABI TransformationMode hasUnrollTransformation(const Loop *L); 313 LLVM_ABI TransformationMode hasUnrollAndJamTransformation(const Loop *L); 314 LLVM_ABI TransformationMode hasVectorizeTransformation(const Loop *L); 315 LLVM_ABI TransformationMode hasDistributeTransformation(const Loop *L); 316 LLVM_ABI TransformationMode hasLICMVersioningTransformation(const Loop *L); 317 /// @} 318 319 /// Set input string into loop metadata by keeping other values intact. 320 /// If the string is already in loop metadata update value if it is 321 /// different. 322 LLVM_ABI void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, 323 unsigned V = 0); 324 325 /// Returns a loop's estimated trip count based on branch weight metadata. 326 /// In addition if \p EstimatedLoopInvocationWeight is not null it is 327 /// initialized with weight of loop's latch leading to the exit. 328 /// Returns a valid positive trip count, saturated at UINT_MAX, or std::nullopt 329 /// when a meaningful estimate cannot be made. 330 LLVM_ABI std::optional<unsigned> 331 getLoopEstimatedTripCount(Loop *L, 332 unsigned *EstimatedLoopInvocationWeight = nullptr); 333 334 /// Set a loop's branch weight metadata to reflect that loop has \p 335 /// EstimatedTripCount iterations and \p EstimatedLoopInvocationWeight exits 336 /// through latch. Returns true if metadata is successfully updated, false 337 /// otherwise. Note that loop must have a latch block which controls loop exit 338 /// in order to succeed. 339 LLVM_ABI bool setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount, 340 unsigned EstimatedLoopInvocationWeight); 341 342 /// Check inner loop (L) backedge count is known to be invariant on all 343 /// iterations of its outer loop. If the loop has no parent, this is trivially 344 /// true. 345 LLVM_ABI bool hasIterationCountInvariantInParent(Loop *L, ScalarEvolution &SE); 346 347 /// Helper to consistently add the set of standard passes to a loop pass's \c 348 /// AnalysisUsage. 349 /// 350 /// All loop passes should call this as part of implementing their \c 351 /// getAnalysisUsage. 352 LLVM_ABI void getLoopAnalysisUsage(AnalysisUsage &AU); 353 354 /// Returns true if is legal to hoist or sink this instruction disregarding the 355 /// possible introduction of faults. Reasoning about potential faulting 356 /// instructions is the responsibility of the caller since it is challenging to 357 /// do efficiently from within this routine. 358 /// \p TargetExecutesOncePerLoop is true only when it is guaranteed that the 359 /// target executes at most once per execution of the loop body. This is used 360 /// to assess the legality of duplicating atomic loads. Generally, this is 361 /// true when moving out of loop and not true when moving into loops. 362 /// If \p ORE is set use it to emit optimization remarks. 363 LLVM_ABI bool canSinkOrHoistInst(Instruction &I, AAResults *AA, 364 DominatorTree *DT, Loop *CurLoop, 365 MemorySSAUpdater &MSSAU, 366 bool TargetExecutesOncePerLoop, 367 SinkAndHoistLICMFlags &LICMFlags, 368 OptimizationRemarkEmitter *ORE = nullptr); 369 370 /// Returns the llvm.vector.reduce intrinsic that corresponds to the recurrence 371 /// kind. 372 LLVM_ABI constexpr Intrinsic::ID getReductionIntrinsicID(RecurKind RK); 373 374 /// Returns the arithmetic instruction opcode used when expanding a reduction. 375 LLVM_ABI unsigned getArithmeticReductionInstruction(Intrinsic::ID RdxID); 376 /// Returns the reduction intrinsic id corresponding to the binary operation. 377 LLVM_ABI Intrinsic::ID getReductionForBinop(Instruction::BinaryOps Opc); 378 379 /// Returns the min/max intrinsic used when expanding a min/max reduction. 380 LLVM_ABI Intrinsic::ID getMinMaxReductionIntrinsicOp(Intrinsic::ID RdxID); 381 382 /// Returns the min/max intrinsic used when expanding a min/max reduction. 383 LLVM_ABI Intrinsic::ID getMinMaxReductionIntrinsicOp(RecurKind RK); 384 385 /// Returns the recurence kind used when expanding a min/max reduction. 386 LLVM_ABI RecurKind getMinMaxReductionRecurKind(Intrinsic::ID RdxID); 387 388 /// Returns the comparison predicate used when expanding a min/max reduction. 389 LLVM_ABI CmpInst::Predicate getMinMaxReductionPredicate(RecurKind RK); 390 391 /// Given information about an @llvm.vector.reduce.* intrinsic, return 392 /// the identity value for the reduction. 393 LLVM_ABI Value *getReductionIdentity(Intrinsic::ID RdxID, Type *Ty, 394 FastMathFlags FMF); 395 396 /// Given information about an recurrence kind, return the identity 397 /// for the @llvm.vector.reduce.* used to generate it. 398 LLVM_ABI Value *getRecurrenceIdentity(RecurKind K, Type *Tp, FastMathFlags FMF); 399 400 /// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind. 401 /// The Builder's fast-math-flags must be set to propagate the expected values. 402 LLVM_ABI Value *createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, 403 Value *Left, Value *Right); 404 405 /// Generates an ordered vector reduction using extracts to reduce the value. 406 LLVM_ABI Value *getOrderedReduction(IRBuilderBase &Builder, Value *Acc, 407 Value *Src, unsigned Op, 408 RecurKind MinMaxKind = RecurKind::None); 409 410 /// Generates a vector reduction using shufflevectors to reduce the value. 411 /// Fast-math-flags are propagated using the IRBuilder's setting. 412 LLVM_ABI Value *getShuffleReduction(IRBuilderBase &Builder, Value *Src, 413 unsigned Op, 414 TargetTransformInfo::ReductionShuffle RS, 415 RecurKind MinMaxKind = RecurKind::None); 416 417 /// Create a reduction of the given vector. The reduction operation 418 /// is described by the \p Opcode parameter. min/max reductions require 419 /// additional information supplied in \p RdxKind. 420 /// Fast-math-flags are propagated using the IRBuilder's setting. 421 LLVM_ABI Value *createSimpleReduction(IRBuilderBase &B, Value *Src, 422 RecurKind RdxKind); 423 /// Overloaded function to generate vector-predication intrinsics for 424 /// reduction. 425 LLVM_ABI Value *createSimpleReduction(IRBuilderBase &B, Value *Src, 426 RecurKind RdxKind, Value *Mask, 427 Value *EVL); 428 429 /// Create a reduction of the given vector \p Src for a reduction of kind 430 /// RecurKind::AnyOf. The start value of the reduction is \p InitVal. 431 LLVM_ABI Value *createAnyOfReduction(IRBuilderBase &B, Value *Src, 432 Value *InitVal, PHINode *OrigPhi); 433 434 /// Create a reduction of the given vector \p Src for a reduction of the 435 /// kind RecurKind::FindLastIV. 436 LLVM_ABI Value *createFindLastIVReduction(IRBuilderBase &B, Value *Src, 437 RecurKind RdxKind, Value *Start, 438 Value *Sentinel); 439 440 /// Create an ordered reduction intrinsic using the given recurrence 441 /// kind \p RdxKind. 442 LLVM_ABI Value *createOrderedReduction(IRBuilderBase &B, RecurKind RdxKind, 443 Value *Src, Value *Start); 444 /// Overloaded function to generate vector-predication intrinsics for ordered 445 /// reduction. 446 LLVM_ABI Value *createOrderedReduction(IRBuilderBase &B, RecurKind RdxKind, 447 Value *Src, Value *Start, Value *Mask, 448 Value *EVL); 449 450 /// Get the intersection (logical and) of all of the potential IR flags 451 /// of each scalar operation (VL) that will be converted into a vector (I). 452 /// If OpValue is non-null, we only consider operations similar to OpValue 453 /// when intersecting. 454 /// Flag set: NSW, NUW (if IncludeWrapFlags is true), exact, and all of 455 /// fast-math. 456 LLVM_ABI void propagateIRFlags(Value *I, ArrayRef<Value *> VL, 457 Value *OpValue = nullptr, 458 bool IncludeWrapFlags = true); 459 460 /// Returns true if we can prove that \p S is defined and always negative in 461 /// loop \p L. 462 LLVM_ABI bool isKnownNegativeInLoop(const SCEV *S, const Loop *L, 463 ScalarEvolution &SE); 464 465 /// Returns true if we can prove that \p S is defined and always non-negative in 466 /// loop \p L. 467 LLVM_ABI bool isKnownNonNegativeInLoop(const SCEV *S, const Loop *L, 468 ScalarEvolution &SE); 469 /// Returns true if we can prove that \p S is defined and always positive in 470 /// loop \p L. 471 LLVM_ABI bool isKnownPositiveInLoop(const SCEV *S, const Loop *L, 472 ScalarEvolution &SE); 473 474 /// Returns true if we can prove that \p S is defined and always non-positive in 475 /// loop \p L. 476 LLVM_ABI bool isKnownNonPositiveInLoop(const SCEV *S, const Loop *L, 477 ScalarEvolution &SE); 478 479 /// Returns true if \p S is defined and never is equal to signed/unsigned max. 480 LLVM_ABI bool cannotBeMaxInLoop(const SCEV *S, const Loop *L, 481 ScalarEvolution &SE, bool Signed); 482 483 /// Returns true if \p S is defined and never is equal to signed/unsigned min. 484 LLVM_ABI bool cannotBeMinInLoop(const SCEV *S, const Loop *L, 485 ScalarEvolution &SE, bool Signed); 486 487 enum ReplaceExitVal { 488 NeverRepl, 489 OnlyCheapRepl, 490 NoHardUse, 491 UnusedIndVarInLoop, 492 AlwaysRepl 493 }; 494 495 /// If the final value of any expressions that are recurrent in the loop can 496 /// be computed, substitute the exit values from the loop into any instructions 497 /// outside of the loop that use the final values of the current expressions. 498 /// Return the number of loop exit values that have been replaced, and the 499 /// corresponding phi node will be added to DeadInsts. 500 LLVM_ABI int rewriteLoopExitValues(Loop *L, LoopInfo *LI, 501 TargetLibraryInfo *TLI, ScalarEvolution *SE, 502 const TargetTransformInfo *TTI, 503 SCEVExpander &Rewriter, DominatorTree *DT, 504 ReplaceExitVal ReplaceExitValue, 505 SmallVector<WeakTrackingVH, 16> &DeadInsts); 506 507 /// Set weights for \p UnrolledLoop and \p RemainderLoop based on weights for 508 /// \p OrigLoop and the following distribution of \p OrigLoop iteration among \p 509 /// UnrolledLoop and \p RemainderLoop. \p UnrolledLoop receives weights that 510 /// reflect TC/UF iterations, and \p RemainderLoop receives weights that reflect 511 /// the remaining TC%UF iterations. 512 /// 513 /// Note that \p OrigLoop may be equal to either \p UnrolledLoop or \p 514 /// RemainderLoop in which case weights for \p OrigLoop are updated accordingly. 515 /// Note also behavior is undefined if \p UnrolledLoop and \p RemainderLoop are 516 /// equal. \p UF must be greater than zero. 517 /// If \p OrigLoop has no profile info associated nothing happens. 518 /// 519 /// This utility may be useful for such optimizations as unroller and 520 /// vectorizer as it's typical transformation for them. 521 LLVM_ABI void setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop, 522 Loop *RemainderLoop, uint64_t UF); 523 524 /// Utility that implements appending of loops onto a worklist given a range. 525 /// We want to process loops in postorder, but the worklist is a LIFO data 526 /// structure, so we append to it in *reverse* postorder. 527 /// For trees, a preorder traversal is a viable reverse postorder, so we 528 /// actually append using a preorder walk algorithm. 529 template <typename RangeT> 530 LLVM_TEMPLATE_ABI void 531 appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist<Loop *, 4> &); 532 /// Utility that implements appending of loops onto a worklist given a range. 533 /// It has the same behavior as appendLoopsToWorklist, but assumes the range of 534 /// loops has already been reversed, so it processes loops in the given order. 535 template <typename RangeT> 536 void appendReversedLoopsToWorklist(RangeT &&, 537 SmallPriorityWorklist<Loop *, 4> &); 538 539 extern template LLVM_TEMPLATE_ABI void 540 appendLoopsToWorklist<ArrayRef<Loop *> &>( 541 ArrayRef<Loop *> &Loops, SmallPriorityWorklist<Loop *, 4> &Worklist); 542 543 extern template LLVM_TEMPLATE_ABI void 544 appendLoopsToWorklist<Loop &>(Loop &L, 545 SmallPriorityWorklist<Loop *, 4> &Worklist); 546 547 /// Utility that implements appending of loops onto a worklist given LoopInfo. 548 /// Calls the templated utility taking a Range of loops, handing it the Loops 549 /// in LoopInfo, iterated in reverse. This is because the loops are stored in 550 /// RPO w.r.t. the control flow graph in LoopInfo. For the purpose of unrolling, 551 /// loop deletion, and LICM, we largely want to work forward across the CFG so 552 /// that we visit defs before uses and can propagate simplifications from one 553 /// loop nest into the next. Calls appendReversedLoopsToWorklist with the 554 /// already reversed loops in LI. 555 /// FIXME: Consider changing the order in LoopInfo. 556 LLVM_ABI void appendLoopsToWorklist(LoopInfo &, 557 SmallPriorityWorklist<Loop *, 4> &); 558 559 /// Recursively clone the specified loop and all of its children, 560 /// mapping the blocks with the specified map. 561 LLVM_ABI Loop *cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, LoopInfo *LI, 562 LPPassManager *LPM); 563 564 /// Add code that checks at runtime if the accessed arrays in \p PointerChecks 565 /// overlap. Returns the final comparator value or NULL if no check is needed. 566 LLVM_ABI Value * 567 addRuntimeChecks(Instruction *Loc, Loop *TheLoop, 568 const SmallVectorImpl<RuntimePointerCheck> &PointerChecks, 569 SCEVExpander &Expander, bool HoistRuntimeChecks = false); 570 571 LLVM_ABI Value *addDiffRuntimeChecks( 572 Instruction *Loc, ArrayRef<PointerDiffInfo> Checks, SCEVExpander &Expander, 573 function_ref<Value *(IRBuilderBase &, unsigned)> GetVF, unsigned IC); 574 575 /// Struct to hold information about a partially invariant condition. 576 struct IVConditionInfo { 577 /// Instructions that need to be duplicated and checked for the unswitching 578 /// condition. 579 SmallVector<Instruction *> InstToDuplicate; 580 581 /// Constant to indicate for which value the condition is invariant. 582 Constant *KnownValue = nullptr; 583 584 /// True if the partially invariant path is no-op (=does not have any 585 /// side-effects and no loop value is used outside the loop). 586 bool PathIsNoop = true; 587 588 /// If the partially invariant path reaches a single exit block, ExitForPath 589 /// is set to that block. Otherwise it is nullptr. 590 BasicBlock *ExitForPath = nullptr; 591 }; 592 593 /// Check if the loop header has a conditional branch that is not 594 /// loop-invariant, because it involves load instructions. If all paths from 595 /// either the true or false successor to the header or loop exists do not 596 /// modify the memory feeding the condition, perform 'partial unswitching'. That 597 /// is, duplicate the instructions feeding the condition in the pre-header. Then 598 /// unswitch on the duplicated condition. The condition is now known in the 599 /// unswitched version for the 'invariant' path through the original loop. 600 /// 601 /// If the branch condition of the header is partially invariant, return a pair 602 /// containing the instructions to duplicate and a boolean Constant to update 603 /// the condition in the loops created for the true or false successors. 604 LLVM_ABI std::optional<IVConditionInfo> 605 hasPartialIVCondition(const Loop &L, unsigned MSSAThreshold, 606 const MemorySSA &MSSA, AAResults &AA); 607 608 } // end namespace llvm 609 610 #endif // LLVM_TRANSFORMS_UTILS_LOOPUTILS_H 611