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/TargetTransformInfo.h"
  27 #include "llvm/IR/Dominators.h"
  28 #include "llvm/IR/IRBuilder.h"
  29 #include "llvm/IR/InstrTypes.h"
  30 #include "llvm/IR/Operator.h"
  31 #include "llvm/IR/ValueHandle.h"
  32 #include "llvm/Support/Casting.h"
  33
  34 namespace llvm {
  35
  36 class AliasSet;
  37 class AliasSetTracker;
  38 class BasicBlock;
  39 class DataLayout;
  40 class Loop;
  41 class LoopInfo;
  42 class OptimizationRemarkEmitter;
  43 class PredicatedScalarEvolution;
  44 class PredIteratorCache;
  45 class ScalarEvolution;
  46 class SCEV;
  47 class TargetLibraryInfo;
  48 class TargetTransformInfo;
  49
  50 /// \brief Captures loop safety information.
  51 /// It keep information for loop & its header may throw exception.
  52 struct LoopSafetyInfo {
  53   bool MayThrow = false;       // The current loop contains an instruction which
  54                                // may throw.
  55   bool HeaderMayThrow = false; // Same as previous, but specific to loop header
  56   // Used to update funclet bundle operands.
  57   DenseMap<BasicBlock *, ColorVector> BlockColors;
  58
  59   LoopSafetyInfo() = default;
  60 };
  61
  62 /// The RecurrenceDescriptor is used to identify recurrences variables in a
  63 /// loop. Reduction is a special case of recurrence that has uses of the
  64 /// recurrence variable outside the loop. The method isReductionPHI identifies
  65 /// reductions that are basic recurrences.
  66 ///
  67 /// Basic recurrences are defined as the summation, product, OR, AND, XOR, min,
  68 /// or max of a set of terms. For example: for(i=0; i<n; i++) { total +=
  69 /// array[i]; } is a summation of array elements. Basic recurrences are a
  70 /// special case of chains of recurrences (CR). See ScalarEvolution for CR
  71 /// references.
  72
  73 /// This struct holds information about recurrence variables.
  74 class RecurrenceDescriptor {
  75 public:
  76   /// This enum represents the kinds of recurrences that we support.
  77   enum RecurrenceKind {
  78     RK_NoRecurrence,  ///< Not a recurrence.
  79     RK_IntegerAdd,    ///< Sum of integers.
  80     RK_IntegerMult,   ///< Product of integers.
  81     RK_IntegerOr,     ///< Bitwise or logical OR of numbers.
  82     RK_IntegerAnd,    ///< Bitwise or logical AND of numbers.
  83     RK_IntegerXor,    ///< Bitwise or logical XOR of numbers.
  84     RK_IntegerMinMax, ///< Min/max implemented in terms of select(cmp()).
  85     RK_FloatAdd,      ///< Sum of floats.
  86     RK_FloatMult,     ///< Product of floats.
  87     RK_FloatMinMax    ///< Min/max implemented in terms of select(cmp()).
  88   };
  89
  90   // This enum represents the kind of minmax recurrence.
  91   enum MinMaxRecurrenceKind {
  92     MRK_Invalid,
  93     MRK_UIntMin,
  94     MRK_UIntMax,
  95     MRK_SIntMin,
  96     MRK_SIntMax,
  97     MRK_FloatMin,
  98     MRK_FloatMax
  99   };
 100
 101   RecurrenceDescriptor() = default;
 102
 103   RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K,
 104                        MinMaxRecurrenceKind MK, Instruction *UAI, Type *RT,
 105                        bool Signed, SmallPtrSetImpl<Instruction *> &CI)
 106       : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK),
 107         UnsafeAlgebraInst(UAI), RecurrenceType(RT), IsSigned(Signed) {
 108     CastInsts.insert(CI.begin(), CI.end());
 109   }
 110
 111   /// This POD struct holds information about a potential recurrence operation.
 112   class InstDesc {
 113   public:
 114     InstDesc(bool IsRecur, Instruction *I, Instruction *UAI = nullptr)
 115         : IsRecurrence(IsRecur), PatternLastInst(I), MinMaxKind(MRK_Invalid),
 116           UnsafeAlgebraInst(UAI) {}
 117
 118     InstDesc(Instruction *I, MinMaxRecurrenceKind K, Instruction *UAI = nullptr)
 119         : IsRecurrence(true), PatternLastInst(I), MinMaxKind(K),
 120           UnsafeAlgebraInst(UAI) {}
 121
 122     bool isRecurrence() { return IsRecurrence; }
 123
 124     bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
 125
 126     Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
 127
 128     MinMaxRecurrenceKind getMinMaxKind() { return MinMaxKind; }
 129
 130     Instruction *getPatternInst() { return PatternLastInst; }
 131
 132   private:
 133     // Is this instruction a recurrence candidate.
 134     bool IsRecurrence;
 135     // The last instruction in a min/max pattern (select of the select(icmp())
 136     // pattern), or the current recurrence instruction otherwise.
 137     Instruction *PatternLastInst;
 138     // If this is a min/max pattern the comparison predicate.
 139     MinMaxRecurrenceKind MinMaxKind;
 140     // Recurrence has unsafe algebra.
 141     Instruction *UnsafeAlgebraInst;
 142   };
 143
 144   /// Returns a struct describing if the instruction 'I' can be a recurrence
 145   /// variable of type 'Kind'. If the recurrence is a min/max pattern of
 146   /// select(icmp()) this function advances the instruction pointer 'I' from the
 147   /// compare instruction to the select instruction and stores this pointer in
 148   /// 'PatternLastInst' member of the returned struct.
 149   static InstDesc isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
 150                                     InstDesc &Prev, bool HasFunNoNaNAttr);
 151
 152   /// Returns true if instruction I has multiple uses in Insts
 153   static bool hasMultipleUsesOf(Instruction *I,
 154                                 SmallPtrSetImpl<Instruction *> &Insts);
 155
 156   /// Returns true if all uses of the instruction I is within the Set.
 157   static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set);
 158
 159   /// Returns a struct describing if the instruction if the instruction is a
 160   /// Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y)
 161   /// or max(X, Y).
 162   static InstDesc isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev);
 163
 164   /// Returns identity corresponding to the RecurrenceKind.
 165   static Constant *getRecurrenceIdentity(RecurrenceKind K, Type *Tp);
 166
 167   /// Returns the opcode of binary operation corresponding to the
 168   /// RecurrenceKind.
 169   static unsigned getRecurrenceBinOp(RecurrenceKind Kind);
 170
 171   /// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
 172   static Value *createMinMaxOp(IRBuilder<> &Builder, MinMaxRecurrenceKind RK,
 173                                Value *Left, Value *Right);
 174
 175   /// Returns true if Phi is a reduction of type Kind and adds it to the
 176   /// RecurrenceDescriptor. If either \p DB is non-null or \p AC and \p DT are
 177   /// non-null, the minimal bit width needed to compute the reduction will be
 178   /// computed.
 179   static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop,
 180                               bool HasFunNoNaNAttr,
 181                               RecurrenceDescriptor &RedDes,
 182                               DemandedBits *DB = nullptr,
 183                               AssumptionCache *AC = nullptr,
 184                               DominatorTree *DT = nullptr);
 185
 186   /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor
 187   /// is returned in RedDes. If either \p DB is non-null or \p AC and \p DT are
 188   /// non-null, the minimal bit width needed to compute the reduction will be
 189   /// computed.
 190   static bool isReductionPHI(PHINode *Phi, Loop *TheLoop,
 191                              RecurrenceDescriptor &RedDes,
 192                              DemandedBits *DB = nullptr,
 193                              AssumptionCache *AC = nullptr,
 194                              DominatorTree *DT = nullptr);
 195
 196   /// Returns true if Phi is a first-order recurrence. A first-order recurrence
 197   /// is a non-reduction recurrence relation in which the value of the
 198   /// recurrence in the current loop iteration equals a value defined in the
 199   /// previous iteration. \p SinkAfter includes pairs of instructions where the
 200   /// first will be rescheduled to appear after the second if/when the loop is
 201   /// vectorized. It may be augmented with additional pairs if needed in order
 202   /// to handle Phi as a first-order recurrence.
 203   static bool
 204   isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop,
 205                          DenseMap<Instruction *, Instruction *> &SinkAfter,
 206                          DominatorTree *DT);
 207
 208   RecurrenceKind getRecurrenceKind() { return Kind; }
 209
 210   MinMaxRecurrenceKind getMinMaxRecurrenceKind() { return MinMaxKind; }
 211
 212   TrackingVH<Value> getRecurrenceStartValue() { return StartValue; }
 213
 214   Instruction *getLoopExitInstr() { return LoopExitInstr; }
 215
 216   /// Returns true if the recurrence has unsafe algebra which requires a relaxed
 217   /// floating-point model.
 218   bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
 219
 220   /// Returns first unsafe algebra instruction in the PHI node's use-chain.
 221   Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
 222
 223   /// Returns true if the recurrence kind is an integer kind.
 224   static bool isIntegerRecurrenceKind(RecurrenceKind Kind);
 225
 226   /// Returns true if the recurrence kind is a floating point kind.
 227   static bool isFloatingPointRecurrenceKind(RecurrenceKind Kind);
 228
 229   /// Returns true if the recurrence kind is an arithmetic kind.
 230   static bool isArithmeticRecurrenceKind(RecurrenceKind Kind);
 231
 232   /// Returns the type of the recurrence. This type can be narrower than the
 233   /// actual type of the Phi if the recurrence has been type-promoted.
 234   Type *getRecurrenceType() { return RecurrenceType; }
 235
 236   /// Returns a reference to the instructions used for type-promoting the
 237   /// recurrence.
 238   SmallPtrSet<Instruction *, 8> &getCastInsts() { return CastInsts; }
 239
 240   /// Returns true if all source operands of the recurrence are SExtInsts.
 241   bool isSigned() { return IsSigned; }
 242
 243 private:
 244   // The starting value of the recurrence.
 245   // It does not have to be zero!
 246   TrackingVH<Value> StartValue;
 247   // The instruction who's value is used outside the loop.
 248   Instruction *LoopExitInstr = nullptr;
 249   // The kind of the recurrence.
 250   RecurrenceKind Kind = RK_NoRecurrence;
 251   // If this a min/max recurrence the kind of recurrence.
 252   MinMaxRecurrenceKind MinMaxKind = MRK_Invalid;
 253   // First occurrence of unasfe algebra in the PHI's use-chain.
 254   Instruction *UnsafeAlgebraInst = nullptr;
 255   // The type of the recurrence.
 256   Type *RecurrenceType = nullptr;
 257   // True if all source operands of the recurrence are SExtInsts.
 258   bool IsSigned = false;
 259   // Instructions used for type-promoting the recurrence.
 260   SmallPtrSet<Instruction *, 8> CastInsts;
 261 };
 262
 263 /// A struct for saving information about induction variables.
 264 class InductionDescriptor {
 265 public:
 266   /// This enum represents the kinds of inductions that we support.
 267   enum InductionKind {
 268     IK_NoInduction,  ///< Not an induction variable.
 269     IK_IntInduction, ///< Integer induction variable. Step = C.
 270     IK_PtrInduction, ///< Pointer induction var. Step = C / sizeof(elem).
 271     IK_FpInduction   ///< Floating point induction variable.
 272   };
 273
 274 public:
 275   /// Default constructor - creates an invalid induction.
 276   InductionDescriptor() = default;
 277
 278   /// Get the consecutive direction. Returns:
 279   ///   0 - unknown or non-consecutive.
 280   ///   1 - consecutive and increasing.
 281   ///  -1 - consecutive and decreasing.
 282   int getConsecutiveDirection() const;
 283
 284   /// Compute the transformed value of Index at offset StartValue using step
 285   /// StepValue.
 286   /// For integer induction, returns StartValue + Index * StepValue.
 287   /// For pointer induction, returns StartValue[Index * StepValue].
 288   /// FIXME: The newly created binary instructions should contain nsw/nuw
 289   /// flags, which can be found from the original scalar operations.
 290   Value *transform(IRBuilder<> &B, Value *Index, ScalarEvolution *SE,
 291                    const DataLayout& DL) const;
 292
 293   Value *getStartValue() const { return StartValue; }
 294   InductionKind getKind() const { return IK; }
 295   const SCEV *getStep() const { return Step; }
 296   ConstantInt *getConstIntStepValue() const;
 297
 298   /// Returns true if \p Phi is an induction in the loop \p L. If \p Phi is an
 299   /// induction, the induction descriptor \p D will contain the data describing
 300   /// this induction. If by some other means the caller has a better SCEV
 301   /// expression for \p Phi than the one returned by the ScalarEvolution
 302   /// analysis, it can be passed through \p Expr. If the def-use chain
 303   /// associated with the phi includes casts (that we know we can ignore
 304   /// under proper runtime checks), they are passed through \p CastsToIgnore.
 305   static bool
 306   isInductionPHI(PHINode *Phi, const Loop* L, ScalarEvolution *SE,
 307                  InductionDescriptor &D, const SCEV *Expr = nullptr,
 308                  SmallVectorImpl<Instruction *> *CastsToIgnore = nullptr);
 309
 310   /// Returns true if \p Phi is a floating point induction in the loop \p L.
 311   /// If \p Phi is an induction, the induction descriptor \p D will contain
 312   /// the data describing this induction.
 313   static bool isFPInductionPHI(PHINode *Phi, const Loop* L,
 314                                ScalarEvolution *SE, InductionDescriptor &D);
 315
 316   /// Returns true if \p Phi is a loop \p L induction, in the context associated
 317   /// with the run-time predicate of PSE. If \p Assume is true, this can add
 318   /// further SCEV predicates to \p PSE in order to prove that \p Phi is an
 319   /// induction.
 320   /// If \p Phi is an induction, \p D will contain the data describing this
 321   /// induction.
 322   static bool isInductionPHI(PHINode *Phi, const Loop* L,
 323                              PredicatedScalarEvolution &PSE,
 324                              InductionDescriptor &D, bool Assume = false);
 325
 326   /// Returns true if the induction type is FP and the binary operator does
 327   /// not have the "fast-math" property. Such operation requires a relaxed FP
 328   /// mode.
 329   bool hasUnsafeAlgebra() {
 330     return InductionBinOp && !cast<FPMathOperator>(InductionBinOp)->isFast();
 331   }
 332
 333   /// Returns induction operator that does not have "fast-math" property
 334   /// and requires FP unsafe mode.
 335   Instruction *getUnsafeAlgebraInst() {
 336     if (!InductionBinOp || cast<FPMathOperator>(InductionBinOp)->isFast())
 337       return nullptr;
 338     return InductionBinOp;
 339   }
 340
 341   /// Returns binary opcode of the induction operator.
 342   Instruction::BinaryOps getInductionOpcode() const {
 343     return InductionBinOp ? InductionBinOp->getOpcode() :
 344       Instruction::BinaryOpsEnd;
 345   }
 346
 347   /// Returns a reference to the type cast instructions in the induction
 348   /// update chain, that are redundant when guarded with a runtime
 349   /// SCEV overflow check.
 350   const SmallVectorImpl<Instruction *> &getCastInsts() const {
 351     return RedundantCasts;
 352   }
 353
 354 private:
 355   /// Private constructor - used by \c isInductionPHI.
 356   InductionDescriptor(Value *Start, InductionKind K, const SCEV *Step,
 357                       BinaryOperator *InductionBinOp = nullptr,
 358                       SmallVectorImpl<Instruction *> *Casts = nullptr);
 359
 360   /// Start value.
 361   TrackingVH<Value> StartValue;
 362   /// Induction kind.
 363   InductionKind IK = IK_NoInduction;
 364   /// Step value.
 365   const SCEV *Step = nullptr;
 366   // Instruction that advances induction variable.
 367   BinaryOperator *InductionBinOp = nullptr;
 368   // Instructions used for type-casts of the induction variable,
 369   // that are redundant when guarded with a runtime SCEV overflow check.
 370   SmallVector<Instruction *, 2> RedundantCasts;
 371 };
 372
 373 BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,
 374                                    bool PreserveLCSSA);
 375
 376 /// Ensure that all exit blocks of the loop are dedicated exits.
 377 ///
 378 /// For any loop exit block with non-loop predecessors, we split the loop
 379 /// predecessors to use a dedicated loop exit block. We update the dominator
 380 /// tree and loop info if provided, and will preserve LCSSA if requested.
 381 bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
 382                              bool PreserveLCSSA);
 383
 384 /// Ensures LCSSA form for every instruction from the Worklist in the scope of
 385 /// innermost containing loop.
 386 ///
 387 /// For the given instruction which have uses outside of the loop, an LCSSA PHI
 388 /// node is inserted and the uses outside the loop are rewritten to use this
 389 /// node.
 390 ///
 391 /// LoopInfo and DominatorTree are required and, since the routine makes no
 392 /// changes to CFG, preserved.
 393 ///
 394 /// Returns true if any modifications are made.
 395 bool formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist,
 396                               DominatorTree &DT, LoopInfo &LI);
 397
 398 /// \brief Put loop into LCSSA form.
 399 ///
 400 /// Looks at all instructions in the loop which have uses outside of the
 401 /// current loop. For each, an LCSSA PHI node is inserted and the uses outside
 402 /// the loop are rewritten to use this node.
 403 ///
 404 /// LoopInfo and DominatorTree are required and preserved.
 405 ///
 406 /// If ScalarEvolution is passed in, it will be preserved.
 407 ///
 408 /// Returns true if any modifications are made to the loop.
 409 bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE);
 410
 411 /// \brief Put a loop nest into LCSSA form.
 412 ///
 413 /// This recursively forms LCSSA for a loop nest.
 414 ///
 415 /// LoopInfo and DominatorTree are required and preserved.
 416 ///
 417 /// If ScalarEvolution is passed in, it will be preserved.
 418 ///
 419 /// Returns true if any modifications are made to the loop.
 420 bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI,
 421                           ScalarEvolution *SE);
 422
 423 /// \brief Walk the specified region of the CFG (defined by all blocks
 424 /// dominated by the specified block, and that are in the current loop) in
 425 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit
 426 /// uses before definitions, allowing us to sink a loop body in one pass without
 427 /// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree,
 428 /// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all
 429 /// instructions of the loop and loop safety information as
 430 /// arguments. Diagnostics is emitted via \p ORE. It returns changed status.
 431 bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
 432                 TargetLibraryInfo *, TargetTransformInfo *, Loop *,
 433                 AliasSetTracker *, LoopSafetyInfo *,
 434                 OptimizationRemarkEmitter *ORE);
 435
 436 /// \brief Walk the specified region of the CFG (defined by all blocks
 437 /// dominated by the specified block, and that are in the current loop) in depth
 438 /// first order w.r.t the DominatorTree.  This allows us to visit definitions
 439 /// before uses, allowing us to hoist a loop body in one pass without iteration.
 440 /// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout,
 441 /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
 442 /// loop and loop safety information as arguments. Diagnostics is emitted via \p
 443 /// ORE. It returns changed status.
 444 bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
 445                  TargetLibraryInfo *, Loop *, AliasSetTracker *,
 446                  LoopSafetyInfo *, OptimizationRemarkEmitter *ORE);
 447
 448 /// This function deletes dead loops. The caller of this function needs to
 449 /// guarantee that the loop is infact dead.
 450 /// The function requires a bunch or prerequisites to be present:
 451 ///   - The loop needs to be in LCSSA form
 452 ///   - The loop needs to have a Preheader
 453 ///   - A unique dedicated exit block must exist
 454 ///
 455 /// This also updates the relevant analysis information in \p DT, \p SE, and \p
 456 /// LI if pointers to those are provided.
 457 /// It also updates the loop PM if an updater struct is provided.
 458
 459 void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE,
 460                     LoopInfo *LI);
 461
 462 /// \brief Try to promote memory values to scalars by sinking stores out of
 463 /// the loop and moving loads to before the loop.  We do this by looping over
 464 /// the stores in the loop, looking for stores to Must pointers which are
 465 /// loop invariant. It takes a set of must-alias values, Loop exit blocks
 466 /// vector, loop exit blocks insertion point vector, PredIteratorCache,
 467 /// LoopInfo, DominatorTree, Loop, AliasSet information for all instructions
 468 /// of the loop and loop safety information as arguments.
 469 /// Diagnostics is emitted via \p ORE. It returns changed status.
 470 bool promoteLoopAccessesToScalars(const SmallSetVector<Value *, 8> &,
 471                                   SmallVectorImpl<BasicBlock *> &,
 472                                   SmallVectorImpl<Instruction *> &,
 473                                   PredIteratorCache &, LoopInfo *,
 474                                   DominatorTree *, const TargetLibraryInfo *,
 475                                   Loop *, AliasSetTracker *, LoopSafetyInfo *,
 476                                   OptimizationRemarkEmitter *);
 477
 478 /// Does a BFS from a given node to all of its children inside a given loop.
 479 /// The returned vector of nodes includes the starting point.
 480 SmallVector<DomTreeNode *, 16> collectChildrenInLoop(DomTreeNode *N,
 481                                                      const Loop *CurLoop);
 482
 483 /// \brief Computes safety information for a loop
 484 /// checks loop body & header for the possibility of may throw
 485 /// exception, it takes LoopSafetyInfo and loop as argument.
 486 /// Updates safety information in LoopSafetyInfo argument.
 487 void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *);
 488
 489 /// Returns true if the instruction in a loop is guaranteed to execute at least
 490 /// once.
 491 bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT,
 492                            const Loop *CurLoop,
 493                            const LoopSafetyInfo *SafetyInfo);
 494
 495 /// \brief Returns the instructions that use values defined in the loop.
 496 SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L);
 497
 498 /// \brief Find string metadata for loop
 499 ///
 500 /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
 501 /// operand or null otherwise.  If the string metadata is not found return
 502 /// Optional's not-a-value.
 503 Optional<const MDOperand *> findStringMetadataForLoop(Loop *TheLoop,
 504                                                       StringRef Name);
 505
 506 /// \brief Set input string into loop metadata by keeping other values intact.
 507 void addStringMetadataToLoop(Loop *TheLoop, const char *MDString,
 508                              unsigned V = 0);
 509
 510 /// \brief Get a loop's estimated trip count based on branch weight metadata.
 511 /// Returns 0 when the count is estimated to be 0, or None when a meaningful
 512 /// estimate can not be made.
 513 Optional<unsigned> getLoopEstimatedTripCount(Loop *L);
 514
 515 /// Helper to consistently add the set of standard passes to a loop pass's \c
 516 /// AnalysisUsage.
 517 ///
 518 /// All loop passes should call this as part of implementing their \c
 519 /// getAnalysisUsage.
 520 void getLoopAnalysisUsage(AnalysisUsage &AU);
 521
 522 /// Returns true if the hoister and sinker can handle this instruction.
 523 /// If SafetyInfo is null, we are checking for sinking instructions from
 524 /// preheader to loop body (no speculation).
 525 /// If SafetyInfo is not null, we are checking for hoisting/sinking
 526 /// instructions from loop body to preheader/exit. Check if the instruction
 527 /// can execute speculatively.
 528 /// If \p ORE is set use it to emit optimization remarks.
 529 bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
 530                         Loop *CurLoop, AliasSetTracker *CurAST,
 531                         LoopSafetyInfo *SafetyInfo,
 532                         OptimizationRemarkEmitter *ORE = nullptr);
 533
 534 /// Generates a vector reduction using shufflevectors to reduce the value.
 535 Value *getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op,
 536                            RecurrenceDescriptor::MinMaxRecurrenceKind
 537                                MinMaxKind = RecurrenceDescriptor::MRK_Invalid,
 538                            ArrayRef<Value *> RedOps = ArrayRef<Value *>());
 539
 540 /// Create a target reduction of the given vector. The reduction operation
 541 /// is described by the \p Opcode parameter. min/max reductions require
 542 /// additional information supplied in \p Flags.
 543 /// The target is queried to determine if intrinsics or shuffle sequences are
 544 /// required to implement the reduction.
 545 Value *
 546 createSimpleTargetReduction(IRBuilder<> &B, const TargetTransformInfo *TTI,
 547                             unsigned Opcode, Value *Src,
 548                             TargetTransformInfo::ReductionFlags Flags =
 549                                 TargetTransformInfo::ReductionFlags(),
 550                             ArrayRef<Value *> RedOps = ArrayRef<Value *>());
 551
 552 /// Create a generic target reduction using a recurrence descriptor \p Desc
 553 /// The target is queried to determine if intrinsics or shuffle sequences are
 554 /// required to implement the reduction.
 555 Value *createTargetReduction(IRBuilder<> &B, const TargetTransformInfo *TTI,
 556                              RecurrenceDescriptor &Desc, Value *Src,
 557                              bool NoNaN = false);
 558
 559 /// Get the intersection (logical and) of all of the potential IR flags
 560 /// of each scalar operation (VL) that will be converted into a vector (I).
 561 /// If OpValue is non-null, we only consider operations similar to OpValue
 562 /// when intersecting.
 563 /// Flag set: NSW, NUW, exact, and all of fast-math.
 564 void propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue = nullptr);
 565
 566 } // end namespace llvm
 567
 568 #endif // LLVM_TRANSFORMS_UTILS_LOOPUTILS_H