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