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