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