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