contrib/llvm/include/llvm/Transforms/Utils/LoopUtils.h

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