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/DenseMap.h" 17 #include "llvm/ADT/Optional.h" 18 #include "llvm/ADT/SetVector.h" 19 #include "llvm/ADT/SmallPtrSet.h" 20 #include "llvm/ADT/SmallVector.h" 21 #include "llvm/ADT/StringRef.h" 22 #include "llvm/Analysis/AliasAnalysis.h" 23 #include "llvm/Analysis/DemandedBits.h" 24 #include "llvm/Analysis/EHPersonalities.h" 25 #include "llvm/Analysis/IVDescriptors.h" 26 #include "llvm/Analysis/MustExecute.h" 27 #include "llvm/Analysis/TargetTransformInfo.h" 28 #include "llvm/IR/Dominators.h" 29 #include "llvm/IR/IRBuilder.h" 30 #include "llvm/IR/InstrTypes.h" 31 #include "llvm/IR/Operator.h" 32 #include "llvm/IR/ValueHandle.h" 33 #include "llvm/Support/Casting.h" 34 35 namespace llvm { 36 37 class AliasSet; 38 class AliasSetTracker; 39 class BasicBlock; 40 class DataLayout; 41 class Loop; 42 class LoopInfo; 43 class MemoryAccess; 44 class MemorySSAUpdater; 45 class OptimizationRemarkEmitter; 46 class PredicatedScalarEvolution; 47 class PredIteratorCache; 48 class ScalarEvolution; 49 class SCEV; 50 class TargetLibraryInfo; 51 class TargetTransformInfo; 52 53 BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, 54 MemorySSAUpdater *MSSAU, bool PreserveLCSSA); 55 56 /// Ensure that all exit blocks of the loop are dedicated exits. 57 /// 58 /// For any loop exit block with non-loop predecessors, we split the loop 59 /// predecessors to use a dedicated loop exit block. We update the dominator 60 /// tree and loop info if provided, and will preserve LCSSA if requested. 61 bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, 62 MemorySSAUpdater *MSSAU, bool PreserveLCSSA); 63 64 /// Ensures LCSSA form for every instruction from the Worklist in the scope of 65 /// innermost containing loop. 66 /// 67 /// For the given instruction which have uses outside of the loop, an LCSSA PHI 68 /// node is inserted and the uses outside the loop are rewritten to use this 69 /// node. 70 /// 71 /// LoopInfo and DominatorTree are required and, since the routine makes no 72 /// changes to CFG, preserved. 73 /// 74 /// Returns true if any modifications are made. 75 bool formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist, 76 DominatorTree &DT, LoopInfo &LI, 77 ScalarEvolution *SE); 78 79 /// Put loop into LCSSA form. 80 /// 81 /// Looks at all instructions in the loop which have uses outside of the 82 /// current loop. For each, an LCSSA PHI node is inserted and the uses outside 83 /// the loop are rewritten to use this node. Sub-loops must be in LCSSA form 84 /// already. 85 /// 86 /// LoopInfo and DominatorTree are required and preserved. 87 /// 88 /// If ScalarEvolution is passed in, it will be preserved. 89 /// 90 /// Returns true if any modifications are made to the loop. 91 bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE); 92 93 /// Put a loop nest into LCSSA form. 94 /// 95 /// This recursively forms LCSSA for a loop nest. 96 /// 97 /// LoopInfo and DominatorTree are required and preserved. 98 /// 99 /// If ScalarEvolution is passed in, it will be preserved. 100 /// 101 /// Returns true if any modifications are made to the loop. 102 bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, 103 ScalarEvolution *SE); 104 105 struct SinkAndHoistLICMFlags { 106 bool NoOfMemAccTooLarge; 107 unsigned LicmMssaOptCounter; 108 unsigned LicmMssaOptCap; 109 unsigned LicmMssaNoAccForPromotionCap; 110 bool IsSink; 111 }; 112 113 /// Walk the specified region of the CFG (defined by all blocks 114 /// dominated by the specified block, and that are in the current loop) in 115 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit 116 /// uses before definitions, allowing us to sink a loop body in one pass without 117 /// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, 118 /// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all 119 /// instructions of the loop and loop safety information as 120 /// arguments. Diagnostics is emitted via \p ORE. It returns changed status. 121 bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, 122 TargetLibraryInfo *, TargetTransformInfo *, Loop *, 123 AliasSetTracker *, MemorySSAUpdater *, ICFLoopSafetyInfo *, 124 SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *); 125 126 /// Walk the specified region of the CFG (defined by all blocks 127 /// dominated by the specified block, and that are in the current loop) in depth 128 /// first order w.r.t the DominatorTree. This allows us to visit definitions 129 /// before uses, allowing us to hoist a loop body in one pass without iteration. 130 /// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout, 131 /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the 132 /// loop and loop safety information as arguments. Diagnostics is emitted via \p 133 /// ORE. It returns changed status. 134 bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, 135 TargetLibraryInfo *, Loop *, AliasSetTracker *, 136 MemorySSAUpdater *, ScalarEvolution *, ICFLoopSafetyInfo *, 137 SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *); 138 139 /// This function deletes dead loops. The caller of this function needs to 140 /// guarantee that the loop is infact dead. 141 /// The function requires a bunch or prerequisites to be present: 142 /// - The loop needs to be in LCSSA form 143 /// - The loop needs to have a Preheader 144 /// - A unique dedicated exit block must exist 145 /// 146 /// This also updates the relevant analysis information in \p DT, \p SE, and \p 147 /// LI if pointers to those are provided. 148 /// It also updates the loop PM if an updater struct is provided. 149 150 void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, 151 LoopInfo *LI); 152 153 /// Try to promote memory values to scalars by sinking stores out of 154 /// the loop and moving loads to before the loop. We do this by looping over 155 /// the stores in the loop, looking for stores to Must pointers which are 156 /// loop invariant. It takes a set of must-alias values, Loop exit blocks 157 /// vector, loop exit blocks insertion point vector, PredIteratorCache, 158 /// LoopInfo, DominatorTree, Loop, AliasSet information for all instructions 159 /// of the loop and loop safety information as arguments. 160 /// Diagnostics is emitted via \p ORE. It returns changed status. 161 bool promoteLoopAccessesToScalars( 162 const SmallSetVector<Value *, 8> &, SmallVectorImpl<BasicBlock *> &, 163 SmallVectorImpl<Instruction *> &, SmallVectorImpl<MemoryAccess *> &, 164 PredIteratorCache &, LoopInfo *, DominatorTree *, const TargetLibraryInfo *, 165 Loop *, AliasSetTracker *, MemorySSAUpdater *, ICFLoopSafetyInfo *, 166 OptimizationRemarkEmitter *); 167 168 /// Does a BFS from a given node to all of its children inside a given loop. 169 /// The returned vector of nodes includes the starting point. 170 SmallVector<DomTreeNode *, 16> collectChildrenInLoop(DomTreeNode *N, 171 const Loop *CurLoop); 172 173 /// Returns the instructions that use values defined in the loop. 174 SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L); 175 176 /// Find string metadata for loop 177 /// 178 /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an 179 /// operand or null otherwise. If the string metadata is not found return 180 /// Optional's not-a-value. 181 Optional<const MDOperand *> findStringMetadataForLoop(const Loop *TheLoop, 182 StringRef Name); 183 184 /// Find named metadata for a loop with an integer value. 185 llvm::Optional<int> getOptionalIntLoopAttribute(Loop *TheLoop, StringRef Name); 186 187 /// Create a new loop identifier for a loop created from a loop transformation. 188 /// 189 /// @param OrigLoopID The loop ID of the loop before the transformation. 190 /// @param FollowupAttrs List of attribute names that contain attributes to be 191 /// added to the new loop ID. 192 /// @param InheritOptionsAttrsPrefix Selects which attributes should be inherited 193 /// from the original loop. The following values 194 /// are considered: 195 /// nullptr : Inherit all attributes from @p OrigLoopID. 196 /// "" : Do not inherit any attribute from @p OrigLoopID; only use 197 /// those specified by a followup attribute. 198 /// "<prefix>": Inherit all attributes except those which start with 199 /// <prefix>; commonly used to remove metadata for the 200 /// applied transformation. 201 /// @param AlwaysNew If true, do not try to reuse OrigLoopID and never return 202 /// None. 203 /// 204 /// @return The loop ID for the after-transformation loop. The following values 205 /// can be returned: 206 /// None : No followup attribute was found; it is up to the 207 /// transformation to choose attributes that make sense. 208 /// @p OrigLoopID: The original identifier can be reused. 209 /// nullptr : The new loop has no attributes. 210 /// MDNode* : A new unique loop identifier. 211 Optional<MDNode *> 212 makeFollowupLoopID(MDNode *OrigLoopID, ArrayRef<StringRef> FollowupAttrs, 213 const char *InheritOptionsAttrsPrefix = "", 214 bool AlwaysNew = false); 215 216 /// Look for the loop attribute that disables all transformation heuristic. 217 bool hasDisableAllTransformsHint(const Loop *L); 218 219 /// Look for the loop attribute that disables the LICM transformation heuristics. 220 bool hasDisableLICMTransformsHint(const Loop *L); 221 222 /// The mode sets how eager a transformation should be applied. 223 enum TransformationMode { 224 /// The pass can use heuristics to determine whether a transformation should 225 /// be applied. 226 TM_Unspecified, 227 228 /// The transformation should be applied without considering a cost model. 229 TM_Enable, 230 231 /// The transformation should not be applied. 232 TM_Disable, 233 234 /// Force is a flag and should not be used alone. 235 TM_Force = 0x04, 236 237 /// The transformation was directed by the user, e.g. by a #pragma in 238 /// the source code. If the transformation could not be applied, a 239 /// warning should be emitted. 240 TM_ForcedByUser = TM_Enable | TM_Force, 241 242 /// The transformation must not be applied. For instance, `#pragma clang loop 243 /// unroll(disable)` explicitly forbids any unrolling to take place. Unlike 244 /// general loop metadata, it must not be dropped. Most passes should not 245 /// behave differently under TM_Disable and TM_SuppressedByUser. 246 TM_SuppressedByUser = TM_Disable | TM_Force 247 }; 248 249 /// @{ 250 /// Get the mode for LLVM's supported loop transformations. 251 TransformationMode hasUnrollTransformation(Loop *L); 252 TransformationMode hasUnrollAndJamTransformation(Loop *L); 253 TransformationMode hasVectorizeTransformation(Loop *L); 254 TransformationMode hasDistributeTransformation(Loop *L); 255 TransformationMode hasLICMVersioningTransformation(Loop *L); 256 /// @} 257 258 /// Set input string into loop metadata by keeping other values intact. 259 /// If the string is already in loop metadata update value if it is 260 /// different. 261 void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, 262 unsigned V = 0); 263 264 /// Get a loop's estimated trip count based on branch weight metadata. 265 /// Returns 0 when the count is estimated to be 0, or None when a meaningful 266 /// estimate can not be made. 267 Optional<unsigned> getLoopEstimatedTripCount(Loop *L); 268 269 /// Check inner loop (L) backedge count is known to be invariant on all 270 /// iterations of its outer loop. If the loop has no parent, this is trivially 271 /// true. 272 bool hasIterationCountInvariantInParent(Loop *L, ScalarEvolution &SE); 273 274 /// Helper to consistently add the set of standard passes to a loop pass's \c 275 /// AnalysisUsage. 276 /// 277 /// All loop passes should call this as part of implementing their \c 278 /// getAnalysisUsage. 279 void getLoopAnalysisUsage(AnalysisUsage &AU); 280 281 /// Returns true if is legal to hoist or sink this instruction disregarding the 282 /// possible introduction of faults. Reasoning about potential faulting 283 /// instructions is the responsibility of the caller since it is challenging to 284 /// do efficiently from within this routine. 285 /// \p TargetExecutesOncePerLoop is true only when it is guaranteed that the 286 /// target executes at most once per execution of the loop body. This is used 287 /// to assess the legality of duplicating atomic loads. Generally, this is 288 /// true when moving out of loop and not true when moving into loops. 289 /// If \p ORE is set use it to emit optimization remarks. 290 bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, 291 Loop *CurLoop, AliasSetTracker *CurAST, 292 MemorySSAUpdater *MSSAU, bool TargetExecutesOncePerLoop, 293 SinkAndHoistLICMFlags *LICMFlags = nullptr, 294 OptimizationRemarkEmitter *ORE = nullptr); 295 296 /// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind. 297 Value *createMinMaxOp(IRBuilder<> &Builder, 298 RecurrenceDescriptor::MinMaxRecurrenceKind RK, 299 Value *Left, Value *Right); 300 301 /// Generates an ordered vector reduction using extracts to reduce the value. 302 Value * 303 getOrderedReduction(IRBuilder<> &Builder, Value *Acc, Value *Src, unsigned Op, 304 RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind = 305 RecurrenceDescriptor::MRK_Invalid, 306 ArrayRef<Value *> RedOps = None); 307 308 /// Generates a vector reduction using shufflevectors to reduce the value. 309 /// Fast-math-flags are propagated using the IRBuilder's setting. 310 Value *getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op, 311 RecurrenceDescriptor::MinMaxRecurrenceKind 312 MinMaxKind = RecurrenceDescriptor::MRK_Invalid, 313 ArrayRef<Value *> RedOps = None); 314 315 /// Create a target reduction of the given vector. The reduction operation 316 /// is described by the \p Opcode parameter. min/max reductions require 317 /// additional information supplied in \p Flags. 318 /// The target is queried to determine if intrinsics or shuffle sequences are 319 /// required to implement the reduction. 320 /// Fast-math-flags are propagated using the IRBuilder's setting. 321 Value *createSimpleTargetReduction(IRBuilder<> &B, 322 const TargetTransformInfo *TTI, 323 unsigned Opcode, Value *Src, 324 TargetTransformInfo::ReductionFlags Flags = 325 TargetTransformInfo::ReductionFlags(), 326 ArrayRef<Value *> RedOps = None); 327 328 /// Create a generic target reduction using a recurrence descriptor \p Desc 329 /// The target is queried to determine if intrinsics or shuffle sequences are 330 /// required to implement the reduction. 331 /// Fast-math-flags are propagated using the RecurrenceDescriptor. 332 Value *createTargetReduction(IRBuilder<> &B, const TargetTransformInfo *TTI, 333 RecurrenceDescriptor &Desc, Value *Src, 334 bool NoNaN = false); 335 336 /// Get the intersection (logical and) of all of the potential IR flags 337 /// of each scalar operation (VL) that will be converted into a vector (I). 338 /// If OpValue is non-null, we only consider operations similar to OpValue 339 /// when intersecting. 340 /// Flag set: NSW, NUW, exact, and all of fast-math. 341 void propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue = nullptr); 342 343 /// Returns true if we can prove that \p S is defined and always negative in 344 /// loop \p L. 345 bool isKnownNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE); 346 347 /// Returns true if we can prove that \p S is defined and always non-negative in 348 /// loop \p L. 349 bool isKnownNonNegativeInLoop(const SCEV *S, const Loop *L, 350 ScalarEvolution &SE); 351 352 /// Returns true if \p S is defined and never is equal to signed/unsigned max. 353 bool cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, 354 bool Signed); 355 356 /// Returns true if \p S is defined and never is equal to signed/unsigned min. 357 bool cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, 358 bool Signed); 359 360 } // end namespace llvm 361 362 #endif // LLVM_TRANSFORMS_UTILS_LOOPUTILS_H 363