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

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