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/Transforms/Scalar/LoopPassManager.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 unsigned TripCount; 71 bool Force; 72 bool AllowRuntime; 73 bool AllowExpensiveTripCount; 74 bool PreserveCondBr; 75 bool PreserveOnlyFirst; 76 unsigned TripMultiple; 77 unsigned PeelCount; 78 bool UnrollRemainder; 79 bool ForgetAllSCEV; 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 89 bool UnrollRuntimeLoopRemainder( 90 Loop *L, unsigned Count, bool AllowExpensiveTripCount, 91 bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV, 92 LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, 93 const TargetTransformInfo *TTI, bool PreserveLCSSA, 94 Loop **ResultLoop = nullptr); 95 96 LoopUnrollResult UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount, 97 unsigned TripMultiple, bool UnrollRemainder, 98 LoopInfo *LI, ScalarEvolution *SE, 99 DominatorTree *DT, AssumptionCache *AC, 100 const TargetTransformInfo *TTI, 101 OptimizationRemarkEmitter *ORE, LPMUpdater *U, 102 Loop **EpilogueLoop = nullptr); 103 104 bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT, 105 DependenceInfo &DI, LoopInfo &LI); 106 107 bool computeUnrollCount(Loop *L, const TargetTransformInfo &TTI, 108 DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE, 109 const SmallPtrSetImpl<const Value *> &EphValues, 110 OptimizationRemarkEmitter *ORE, unsigned &TripCount, 111 unsigned MaxTripCount, bool MaxOrZero, 112 unsigned &TripMultiple, unsigned LoopSize, 113 TargetTransformInfo::UnrollingPreferences &UP, 114 TargetTransformInfo::PeelingPreferences &PP, 115 bool &UseUpperBound); 116 117 void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, 118 ScalarEvolution *SE, DominatorTree *DT, 119 AssumptionCache *AC, 120 const TargetTransformInfo *TTI); 121 122 MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name); 123 124 TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences( 125 Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, 126 BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, int OptLevel, 127 Optional<unsigned> UserThreshold, Optional<unsigned> UserCount, 128 Optional<bool> UserAllowPartial, Optional<bool> UserRuntime, 129 Optional<bool> UserUpperBound, Optional<unsigned> UserFullUnrollMaxCount); 130 131 unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls, 132 bool &NotDuplicatable, bool &Convergent, 133 const TargetTransformInfo &TTI, 134 const SmallPtrSetImpl<const Value *> &EphValues, 135 unsigned BEInsns); 136 137 } // end namespace llvm 138 139 #endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H 140