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/Support/InstructionCost.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 bool Force; 71 bool Runtime; 72 bool AllowExpensiveTripCount; 73 bool UnrollRemainder; 74 bool ForgetAllSCEV; 75 }; 76 77 LoopUnrollResult UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI, 78 ScalarEvolution *SE, DominatorTree *DT, 79 AssumptionCache *AC, 80 const llvm::TargetTransformInfo *TTI, 81 OptimizationRemarkEmitter *ORE, bool PreserveLCSSA, 82 Loop **RemainderLoop = nullptr); 83 84 bool UnrollRuntimeLoopRemainder( 85 Loop *L, unsigned Count, bool AllowExpensiveTripCount, 86 bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV, 87 LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, 88 const TargetTransformInfo *TTI, bool PreserveLCSSA, 89 Loop **ResultLoop = nullptr); 90 91 LoopUnrollResult UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount, 92 unsigned TripMultiple, bool UnrollRemainder, 93 LoopInfo *LI, ScalarEvolution *SE, 94 DominatorTree *DT, AssumptionCache *AC, 95 const TargetTransformInfo *TTI, 96 OptimizationRemarkEmitter *ORE, 97 Loop **EpilogueLoop = nullptr); 98 99 bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT, 100 DependenceInfo &DI, LoopInfo &LI); 101 102 void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, 103 ScalarEvolution *SE, DominatorTree *DT, 104 AssumptionCache *AC, 105 const TargetTransformInfo *TTI); 106 107 MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name); 108 109 TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences( 110 Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, 111 BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, 112 llvm::OptimizationRemarkEmitter &ORE, int OptLevel, 113 std::optional<unsigned> UserThreshold, std::optional<unsigned> UserCount, 114 std::optional<bool> UserAllowPartial, std::optional<bool> UserRuntime, 115 std::optional<bool> UserUpperBound, 116 std::optional<unsigned> UserFullUnrollMaxCount); 117 118 /// Produce an estimate of the unrolled cost of the specified loop. This 119 /// is used to a) produce a cost estimate for partial unrolling and b) to 120 /// cheaply estimate cost for full unrolling when we don't want to symbolically 121 /// evaluate all iterations. 122 class UnrollCostEstimator { 123 InstructionCost LoopSize; 124 bool NotDuplicatable; 125 126 public: 127 unsigned NumInlineCandidates; 128 bool Convergent; 129 130 UnrollCostEstimator(const Loop *L, const TargetTransformInfo &TTI, 131 const SmallPtrSetImpl<const Value *> &EphValues, 132 unsigned BEInsns); 133 134 /// Whether it is legal to unroll this loop. canUnroll()135 bool canUnroll() const { return LoopSize.isValid() && !NotDuplicatable; } 136 getRolledLoopSize()137 uint64_t getRolledLoopSize() const { return *LoopSize.getValue(); } 138 139 /// Returns loop size estimation for unrolled loop, given the unrolling 140 /// configuration specified by UP. 141 uint64_t 142 getUnrolledLoopSize(const TargetTransformInfo::UnrollingPreferences &UP, 143 unsigned CountOverwrite = 0) const; 144 }; 145 146 bool computeUnrollCount(Loop *L, const TargetTransformInfo &TTI, 147 DominatorTree &DT, LoopInfo *LI, AssumptionCache *AC, 148 ScalarEvolution &SE, 149 const SmallPtrSetImpl<const Value *> &EphValues, 150 OptimizationRemarkEmitter *ORE, unsigned TripCount, 151 unsigned MaxTripCount, bool MaxOrZero, 152 unsigned TripMultiple, const UnrollCostEstimator &UCE, 153 TargetTransformInfo::UnrollingPreferences &UP, 154 TargetTransformInfo::PeelingPreferences &PP, 155 bool &UseUpperBound); 156 157 } // end namespace llvm 158 159 #endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H 160