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