LoopUtils.h revision 360784
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 35namespace llvm { 36 37class AliasSet; 38class AliasSetTracker; 39class BasicBlock; 40class DataLayout; 41class Loop; 42class LoopInfo; 43class MemoryAccess; 44class MemorySSAUpdater; 45class OptimizationRemarkEmitter; 46class PredicatedScalarEvolution; 47class PredIteratorCache; 48class ScalarEvolution; 49class SCEV; 50class TargetLibraryInfo; 51class TargetTransformInfo; 52 53BasicBlock *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. 61bool 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. 75bool 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. 91bool 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. 102bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, 103 ScalarEvolution *SE); 104 105struct 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. 121bool 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. 134bool 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 150void 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. 161bool 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. 170SmallVector<DomTreeNode *, 16> collectChildrenInLoop(DomTreeNode *N, 171 const Loop *CurLoop); 172 173/// Returns the instructions that use values defined in the loop. 174SmallVector<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. 181Optional<const MDOperand *> findStringMetadataForLoop(const Loop *TheLoop, 182 StringRef Name); 183 184/// Find named metadata for a loop with an integer value. 185llvm::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. 211Optional<MDNode *> 212makeFollowupLoopID(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. 217bool hasDisableAllTransformsHint(const Loop *L); 218 219/// Look for the loop attribute that disables the LICM transformation heuristics. 220bool hasDisableLICMTransformsHint(const Loop *L); 221 222/// The mode sets how eager a transformation should be applied. 223enum 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. 251TransformationMode hasUnrollTransformation(Loop *L); 252TransformationMode hasUnrollAndJamTransformation(Loop *L); 253TransformationMode hasVectorizeTransformation(Loop *L); 254TransformationMode hasDistributeTransformation(Loop *L); 255TransformationMode 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. 261void 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. 267Optional<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. 272bool 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. 279void 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. 290bool 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. 297Value *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. 302Value * 303getOrderedReduction(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. 310Value *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. 321Value *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. 332Value *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. 341void 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. 345bool 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. 349bool 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. 353bool 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. 357bool 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