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 21 namespace llvm { 22 23 class AssumptionCache; 24 class BasicBlock; 25 class BlockFrequencyInfo; 26 class DependenceInfo; 27 class DominatorTree; 28 class Loop; 29 class LoopInfo; 30 class MDNode; 31 class ProfileSummaryInfo; 32 class OptimizationRemarkEmitter; 33 class ScalarEvolution; 34 class StringRef; 35 class Value; 36 37 using NewLoopsMap = SmallDenseMap<const Loop *, Loop *, 4>; 38 39 /// @{ 40 /// Metadata attribute names 41 const char *const LLVMLoopUnrollFollowupAll = "llvm.loop.unroll.followup_all"; 42 const char *const LLVMLoopUnrollFollowupUnrolled = 43 "llvm.loop.unroll.followup_unrolled"; 44 const char *const LLVMLoopUnrollFollowupRemainder = 45 "llvm.loop.unroll.followup_remainder"; 46 /// @} 47 48 const Loop* addClonedBlockToLoopInfo(BasicBlock *OriginalBB, 49 BasicBlock *ClonedBB, LoopInfo *LI, 50 NewLoopsMap &NewLoops); 51 52 /// Represents the result of a \c UnrollLoop invocation. 53 enum class LoopUnrollResult { 54 /// The loop was not modified. 55 Unmodified, 56 57 /// The loop was partially unrolled -- we still have a loop, but with a 58 /// smaller trip count. We may also have emitted epilogue loop if the loop 59 /// had a non-constant trip count. 60 PartiallyUnrolled, 61 62 /// The loop was fully unrolled into straight-line code. We no longer have 63 /// any back-edges. 64 FullyUnrolled 65 }; 66 67 struct UnrollLoopOptions { 68 unsigned Count; 69 bool Force; 70 bool Runtime; 71 bool AllowExpensiveTripCount; 72 bool UnrollRemainder; 73 bool ForgetAllSCEV; 74 }; 75 76 LoopUnrollResult UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI, 77 ScalarEvolution *SE, DominatorTree *DT, 78 AssumptionCache *AC, 79 const llvm::TargetTransformInfo *TTI, 80 OptimizationRemarkEmitter *ORE, bool PreserveLCSSA, 81 Loop **RemainderLoop = nullptr); 82 83 bool UnrollRuntimeLoopRemainder( 84 Loop *L, unsigned Count, bool AllowExpensiveTripCount, 85 bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV, 86 LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, 87 const TargetTransformInfo *TTI, bool PreserveLCSSA, 88 Loop **ResultLoop = nullptr); 89 90 LoopUnrollResult UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount, 91 unsigned TripMultiple, bool UnrollRemainder, 92 LoopInfo *LI, ScalarEvolution *SE, 93 DominatorTree *DT, AssumptionCache *AC, 94 const TargetTransformInfo *TTI, 95 OptimizationRemarkEmitter *ORE, 96 Loop **EpilogueLoop = nullptr); 97 98 bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT, 99 DependenceInfo &DI, LoopInfo &LI); 100 101 bool computeUnrollCount(Loop *L, const TargetTransformInfo &TTI, 102 DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE, 103 const SmallPtrSetImpl<const Value *> &EphValues, 104 OptimizationRemarkEmitter *ORE, unsigned TripCount, 105 unsigned MaxTripCount, bool MaxOrZero, 106 unsigned TripMultiple, unsigned LoopSize, 107 TargetTransformInfo::UnrollingPreferences &UP, 108 TargetTransformInfo::PeelingPreferences &PP, 109 bool &UseUpperBound); 110 111 void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, 112 ScalarEvolution *SE, DominatorTree *DT, 113 AssumptionCache *AC, 114 const TargetTransformInfo *TTI); 115 116 MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name); 117 118 TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences( 119 Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, 120 BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, int OptLevel, 121 Optional<unsigned> UserThreshold, Optional<unsigned> UserCount, 122 Optional<bool> UserAllowPartial, Optional<bool> UserRuntime, 123 Optional<bool> UserUpperBound, Optional<unsigned> UserFullUnrollMaxCount); 124 125 unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls, 126 bool &NotDuplicatable, bool &Convergent, 127 const TargetTransformInfo &TTI, 128 const SmallPtrSetImpl<const Value *> &EphValues, 129 unsigned BEInsns); 130 131 } // end namespace llvm 132 133 #endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H 134