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

   1 //===- llvm/Transforms/Utils/UnrollLoop.h - Unrolling 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 unrolling utilities. It does not define any
  11 // actual pass or policy, but provides a single function to perform loop
  12 // unrolling.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
  17 #define LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
  18
  19 #include "llvm/ADT/DenseMap.h"
  20 #include "llvm/ADT/StringRef.h"
  21 #include "llvm/Analysis/TargetTransformInfo.h"
  22 #include "llvm/Transforms/Utils/ValueMapper.h"
  23
  24 namespace llvm {
  25
  26 class AssumptionCache;
  27 class BasicBlock;
  28 class DependenceInfo;
  29 class DominatorTree;
  30 class Loop;
  31 class LoopInfo;
  32 class MDNode;
  33 class OptimizationRemarkEmitter;
  34 class ScalarEvolution;
  35
  36 using NewLoopsMap = SmallDenseMap<const Loop *, Loop *, 4>;
  37
  38 /// @{
  39 /// Metadata attribute names
  40 const char *const LLVMLoopUnrollFollowupAll = "llvm.loop.unroll.followup_all";
  41 const char *const LLVMLoopUnrollFollowupUnrolled =
  42     "llvm.loop.unroll.followup_unrolled";
  43 const char *const LLVMLoopUnrollFollowupRemainder =
  44     "llvm.loop.unroll.followup_remainder";
  45 /// @}
  46
  47 const Loop* addClonedBlockToLoopInfo(BasicBlock *OriginalBB,
  48                                      BasicBlock *ClonedBB, LoopInfo *LI,
  49                                      NewLoopsMap &NewLoops);
  50
  51 /// Represents the result of a \c UnrollLoop invocation.
  52 enum class LoopUnrollResult {
  53   /// The loop was not modified.
  54   Unmodified,
  55
  56   /// The loop was partially unrolled -- we still have a loop, but with a
  57   /// smaller trip count.  We may also have emitted epilogue loop if the loop
  58   /// had a non-constant trip count.
  59   PartiallyUnrolled,
  60
  61   /// The loop was fully unrolled into straight-line code.  We no longer have
  62   /// any back-edges.
  63   FullyUnrolled
  64 };
  65
  66 LoopUnrollResult UnrollLoop(Loop *L, unsigned Count, unsigned TripCount,
  67                             bool Force, bool AllowRuntime,
  68                             bool AllowExpensiveTripCount, bool PreserveCondBr,
  69                             bool PreserveOnlyFirst, unsigned TripMultiple,
  70                             unsigned PeelCount, bool UnrollRemainder,
  71                             LoopInfo *LI, ScalarEvolution *SE,
  72                             DominatorTree *DT, AssumptionCache *AC,
  73                             OptimizationRemarkEmitter *ORE, bool PreserveLCSSA,
  74                             Loop **RemainderLoop = nullptr);
  75
  76 bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count,
  77                                 bool AllowExpensiveTripCount,
  78                                 bool UseEpilogRemainder, bool UnrollRemainder,
  79                                 LoopInfo *LI, ScalarEvolution *SE,
  80                                 DominatorTree *DT, AssumptionCache *AC,
  81                                 bool PreserveLCSSA,
  82                                 Loop **ResultLoop = nullptr);
  83
  84 void computePeelCount(Loop *L, unsigned LoopSize,
  85                       TargetTransformInfo::UnrollingPreferences &UP,
  86                       unsigned &TripCount, ScalarEvolution &SE);
  87
  88 bool canPeel(Loop *L);
  89
  90 bool peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI, ScalarEvolution *SE,
  91               DominatorTree *DT, AssumptionCache *AC, bool PreserveLCSSA);
  92
  93 LoopUnrollResult UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount,
  94                                   unsigned TripMultiple, bool UnrollRemainder,
  95                                   LoopInfo *LI, ScalarEvolution *SE,
  96                                   DominatorTree *DT, AssumptionCache *AC,
  97                                   OptimizationRemarkEmitter *ORE,
  98                                   Loop **EpilogueLoop = nullptr);
  99
 100 bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT,
 101                           DependenceInfo &DI);
 102
 103 bool computeUnrollCount(Loop *L, const TargetTransformInfo &TTI,
 104                         DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE,
 105                         const SmallPtrSetImpl<const Value *> &EphValues,
 106                         OptimizationRemarkEmitter *ORE, unsigned &TripCount,
 107                         unsigned MaxTripCount, unsigned &TripMultiple,
 108                         unsigned LoopSize,
 109                         TargetTransformInfo::UnrollingPreferences &UP,
 110                         bool &UseUpperBound);
 111
 112 BasicBlock *foldBlockIntoPredecessor(BasicBlock *BB, LoopInfo *LI,
 113                                      ScalarEvolution *SE, DominatorTree *DT);
 114
 115 void remapInstruction(Instruction *I, ValueToValueMapTy &VMap);
 116
 117 void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI,
 118                              ScalarEvolution *SE, DominatorTree *DT,
 119                              AssumptionCache *AC);
 120
 121 MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name);
 122
 123 TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences(
 124     Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, int OptLevel,
 125     Optional<unsigned> UserThreshold, Optional<unsigned> UserCount,
 126     Optional<bool> UserAllowPartial, Optional<bool> UserRuntime,
 127     Optional<bool> UserUpperBound, Optional<bool> UserAllowPeeling);
 128
 129 unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls,
 130                              bool &NotDuplicatable, bool &Convergent,
 131                              const TargetTransformInfo &TTI,
 132                              const SmallPtrSetImpl<const Value *> &EphValues,
 133                              unsigned BEInsns);
 134
 135 } // end namespace llvm
 136
 137 #endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H