Transforms/Utils/UnrollLoop.h

0001 //===- llvm/Transforms/Utils/UnrollLoop.h - Unrolling utilities -*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This file defines some loop unrolling utilities. It does not define any
0010 // actual pass or policy, but provides a single function to perform loop
0011 // unrolling.
0012 //
0013 //===----------------------------------------------------------------------===//
0014
0015 #ifndef LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
0016 #define LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
0017
0018 #include "llvm/ADT/DenseMap.h"
0019 #include "llvm/Analysis/CodeMetrics.h"
0020 #include "llvm/Analysis/TargetTransformInfo.h"
0021 #include "llvm/Support/InstructionCost.h"
0022
0023 namespace llvm {
0024
0025 class AssumptionCache;
0026 class AAResults;
0027 class BasicBlock;
0028 class BlockFrequencyInfo;
0029 class DependenceInfo;
0030 class DominatorTree;
0031 class Loop;
0032 class LoopInfo;
0033 class MDNode;
0034 class ProfileSummaryInfo;
0035 class OptimizationRemarkEmitter;
0036 class ScalarEvolution;
0037 class StringRef;
0038 class Value;
0039
0040 using NewLoopsMap = SmallDenseMap<const Loop *, Loop *, 4>;
0041
0042 /// @{
0043 /// Metadata attribute names
0044 const char *const LLVMLoopUnrollFollowupAll = "llvm.loop.unroll.followup_all";
0045 const char *const LLVMLoopUnrollFollowupUnrolled =
0046     "llvm.loop.unroll.followup_unrolled";
0047 const char *const LLVMLoopUnrollFollowupRemainder =
0048     "llvm.loop.unroll.followup_remainder";
0049 /// @}
0050
0051 const Loop* addClonedBlockToLoopInfo(BasicBlock *OriginalBB,
0052                                      BasicBlock *ClonedBB, LoopInfo *LI,
0053                                      NewLoopsMap &NewLoops);
0054
0055 /// Represents the result of a \c UnrollLoop invocation.
0056 enum class LoopUnrollResult {
0057   /// The loop was not modified.
0058   Unmodified,
0059
0060   /// The loop was partially unrolled -- we still have a loop, but with a
0061   /// smaller trip count.  We may also have emitted epilogue loop if the loop
0062   /// had a non-constant trip count.
0063   PartiallyUnrolled,
0064
0065   /// The loop was fully unrolled into straight-line code.  We no longer have
0066   /// any back-edges.
0067   FullyUnrolled
0068 };
0069
0070 struct UnrollLoopOptions {
0071   unsigned Count;
0072   bool Force;
0073   bool Runtime;
0074   bool AllowExpensiveTripCount;
0075   bool UnrollRemainder;
0076   bool ForgetAllSCEV;
0077   const Instruction *Heart = nullptr;
0078   unsigned SCEVExpansionBudget;
0079   bool RuntimeUnrollMultiExit = false;
0080 };
0081
0082 LoopUnrollResult UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI,
0083                             ScalarEvolution *SE, DominatorTree *DT,
0084                             AssumptionCache *AC,
0085                             const llvm::TargetTransformInfo *TTI,
0086                             OptimizationRemarkEmitter *ORE, bool PreserveLCSSA,
0087                             Loop **RemainderLoop = nullptr,
0088                             AAResults *AA = nullptr);
0089
0090 bool UnrollRuntimeLoopRemainder(
0091     Loop *L, unsigned Count, bool AllowExpensiveTripCount,
0092     bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV,
0093     LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC,
0094     const TargetTransformInfo *TTI, bool PreserveLCSSA,
0095     unsigned SCEVExpansionBudget, bool RuntimeUnrollMultiExit,
0096     Loop **ResultLoop = nullptr);
0097
0098 LoopUnrollResult UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount,
0099                                   unsigned TripMultiple, bool UnrollRemainder,
0100                                   LoopInfo *LI, ScalarEvolution *SE,
0101                                   DominatorTree *DT, AssumptionCache *AC,
0102                                   const TargetTransformInfo *TTI,
0103                                   OptimizationRemarkEmitter *ORE,
0104                                   Loop **EpilogueLoop = nullptr);
0105
0106 bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT,
0107                           DependenceInfo &DI, LoopInfo &LI);
0108
0109 void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI,
0110                              ScalarEvolution *SE, DominatorTree *DT,
0111                              AssumptionCache *AC,
0112                              const TargetTransformInfo *TTI,
0113                              AAResults *AA = nullptr);
0114
0115 MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name);
0116
0117 TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences(
0118     Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI,
0119     BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI,
0120     llvm::OptimizationRemarkEmitter &ORE, int OptLevel,
0121     std::optional<unsigned> UserThreshold, std::optional<unsigned> UserCount,
0122     std::optional<bool> UserAllowPartial, std::optional<bool> UserRuntime,
0123     std::optional<bool> UserUpperBound,
0124     std::optional<unsigned> UserFullUnrollMaxCount);
0125
0126 /// Produce an estimate of the unrolled cost of the specified loop.  This
0127 /// is used to a) produce a cost estimate for partial unrolling and b) to
0128 /// cheaply estimate cost for full unrolling when we don't want to symbolically
0129 /// evaluate all iterations.
0130 class UnrollCostEstimator {
0131   InstructionCost LoopSize;
0132   bool NotDuplicatable;
0133
0134 public:
0135   unsigned NumInlineCandidates;
0136   ConvergenceKind Convergence;
0137   bool ConvergenceAllowsRuntime;
0138
0139   UnrollCostEstimator(const Loop *L, const TargetTransformInfo &TTI,
0140                       const SmallPtrSetImpl<const Value *> &EphValues,
0141                       unsigned BEInsns);
0142
0143   /// Whether it is legal to unroll this loop.
0144   bool canUnroll() const;
0145
0146   uint64_t getRolledLoopSize() const { return *LoopSize.getValue(); }
0147
0148   /// Returns loop size estimation for unrolled loop, given the unrolling
0149   /// configuration specified by UP.
0150   uint64_t
0151   getUnrolledLoopSize(const TargetTransformInfo::UnrollingPreferences &UP,
0152                       unsigned CountOverwrite = 0) const;
0153 };
0154
0155 bool computeUnrollCount(Loop *L, const TargetTransformInfo &TTI,
0156                         DominatorTree &DT, LoopInfo *LI, AssumptionCache *AC,
0157                         ScalarEvolution &SE,
0158                         const SmallPtrSetImpl<const Value *> &EphValues,
0159                         OptimizationRemarkEmitter *ORE, unsigned TripCount,
0160                         unsigned MaxTripCount, bool MaxOrZero,
0161                         unsigned TripMultiple, const UnrollCostEstimator &UCE,
0162                         TargetTransformInfo::UnrollingPreferences &UP,
0163                         TargetTransformInfo::PeelingPreferences &PP,
0164                         bool &UseUpperBound);
0165
0166 } // end namespace llvm
0167
0168 #endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H