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/CodeMetrics.h" 20 #include "llvm/Analysis/TargetTransformInfo.h" 21 #include "llvm/Support/Compiler.h" 22 #include "llvm/Support/InstructionCost.h" 23 24 namespace llvm { 25 26 class AssumptionCache; 27 class AAResults; 28 class BasicBlock; 29 class BlockFrequencyInfo; 30 class DependenceInfo; 31 class DominatorTree; 32 class Loop; 33 class LoopInfo; 34 class MDNode; 35 class ProfileSummaryInfo; 36 class OptimizationRemarkEmitter; 37 class ScalarEvolution; 38 class StringRef; 39 class Value; 40 41 using NewLoopsMap = SmallDenseMap<const Loop *, Loop *, 4>; 42 43 /// @{ 44 /// Metadata attribute names 45 const char *const LLVMLoopUnrollFollowupAll = "llvm.loop.unroll.followup_all"; 46 const char *const LLVMLoopUnrollFollowupUnrolled = 47 "llvm.loop.unroll.followup_unrolled"; 48 const char *const LLVMLoopUnrollFollowupRemainder = 49 "llvm.loop.unroll.followup_remainder"; 50 /// @} 51 52 LLVM_ABI const Loop *addClonedBlockToLoopInfo(BasicBlock *OriginalBB, 53 BasicBlock *ClonedBB, 54 LoopInfo *LI, 55 NewLoopsMap &NewLoops); 56 57 /// Represents the result of a \c UnrollLoop invocation. 58 enum class LoopUnrollResult { 59 /// The loop was not modified. 60 Unmodified, 61 62 /// The loop was partially unrolled -- we still have a loop, but with a 63 /// smaller trip count. We may also have emitted epilogue loop if the loop 64 /// had a non-constant trip count. 65 PartiallyUnrolled, 66 67 /// The loop was fully unrolled into straight-line code. We no longer have 68 /// any back-edges. 69 FullyUnrolled 70 }; 71 72 struct UnrollLoopOptions { 73 unsigned Count; 74 bool Force; 75 bool Runtime; 76 bool AllowExpensiveTripCount; 77 bool UnrollRemainder; 78 bool ForgetAllSCEV; 79 const Instruction *Heart = nullptr; 80 unsigned SCEVExpansionBudget; 81 bool RuntimeUnrollMultiExit = false; 82 }; 83 84 LLVM_ABI LoopUnrollResult UnrollLoop(Loop *L, UnrollLoopOptions ULO, 85 LoopInfo *LI, ScalarEvolution *SE, 86 DominatorTree *DT, AssumptionCache *AC, 87 const llvm::TargetTransformInfo *TTI, 88 OptimizationRemarkEmitter *ORE, 89 bool PreserveLCSSA, 90 Loop **RemainderLoop = nullptr, 91 AAResults *AA = nullptr); 92 93 LLVM_ABI bool UnrollRuntimeLoopRemainder( 94 Loop *L, unsigned Count, bool AllowExpensiveTripCount, 95 bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV, 96 LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, 97 const TargetTransformInfo *TTI, bool PreserveLCSSA, 98 unsigned SCEVExpansionBudget, bool RuntimeUnrollMultiExit, 99 Loop **ResultLoop = nullptr); 100 101 LLVM_ABI LoopUnrollResult UnrollAndJamLoop( 102 Loop *L, unsigned Count, unsigned TripCount, unsigned TripMultiple, 103 bool UnrollRemainder, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, 104 AssumptionCache *AC, const TargetTransformInfo *TTI, 105 OptimizationRemarkEmitter *ORE, Loop **EpilogueLoop = nullptr); 106 107 LLVM_ABI bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, 108 DominatorTree &DT, DependenceInfo &DI, 109 LoopInfo &LI); 110 111 LLVM_ABI void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, 112 ScalarEvolution *SE, DominatorTree *DT, 113 AssumptionCache *AC, 114 const TargetTransformInfo *TTI, 115 AAResults *AA = nullptr); 116 117 LLVM_ABI MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name); 118 119 LLVM_ABI TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences( 120 Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, 121 BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, 122 llvm::OptimizationRemarkEmitter &ORE, int OptLevel, 123 std::optional<unsigned> UserThreshold, std::optional<unsigned> UserCount, 124 std::optional<bool> UserAllowPartial, std::optional<bool> UserRuntime, 125 std::optional<bool> UserUpperBound, 126 std::optional<unsigned> UserFullUnrollMaxCount); 127 128 /// Produce an estimate of the unrolled cost of the specified loop. This 129 /// is used to a) produce a cost estimate for partial unrolling and b) to 130 /// cheaply estimate cost for full unrolling when we don't want to symbolically 131 /// evaluate all iterations. 132 class UnrollCostEstimator { 133 InstructionCost LoopSize; 134 bool NotDuplicatable; 135 136 public: 137 unsigned NumInlineCandidates; 138 ConvergenceKind Convergence; 139 bool ConvergenceAllowsRuntime; 140 141 LLVM_ABI UnrollCostEstimator(const Loop *L, const TargetTransformInfo &TTI, 142 const SmallPtrSetImpl<const Value *> &EphValues, 143 unsigned BEInsns); 144 145 /// Whether it is legal to unroll this loop. 146 LLVM_ABI bool canUnroll() const; 147 getRolledLoopSize()148 uint64_t getRolledLoopSize() const { return LoopSize.getValue(); } 149 150 /// Returns loop size estimation for unrolled loop, given the unrolling 151 /// configuration specified by UP. 152 LLVM_ABI uint64_t 153 getUnrolledLoopSize(const TargetTransformInfo::UnrollingPreferences &UP, 154 unsigned CountOverwrite = 0) const; 155 }; 156 157 LLVM_ABI bool computeUnrollCount( 158 Loop *L, const TargetTransformInfo &TTI, DominatorTree &DT, LoopInfo *LI, 159 AssumptionCache *AC, ScalarEvolution &SE, 160 const SmallPtrSetImpl<const Value *> &EphValues, 161 OptimizationRemarkEmitter *ORE, unsigned TripCount, unsigned MaxTripCount, 162 bool MaxOrZero, unsigned TripMultiple, const UnrollCostEstimator &UCE, 163 TargetTransformInfo::UnrollingPreferences &UP, 164 TargetTransformInfo::PeelingPreferences &PP, bool &UseUpperBound); 165 166 } // end namespace llvm 167 168 #endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H 169