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/ADT/StringRef.h" 20 #include "llvm/Analysis/TargetTransformInfo.h" 21 #include "llvm/Transforms/Utils/ValueMapper.h" 22 23 namespace llvm { 24 25 class AssumptionCache; 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 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 unsigned TripCount; 70 bool Force; 71 bool AllowRuntime; 72 bool AllowExpensiveTripCount; 73 bool PreserveCondBr; 74 bool PreserveOnlyFirst; 75 unsigned TripMultiple; 76 unsigned PeelCount; 77 bool UnrollRemainder; 78 bool ForgetAllSCEV; 79 }; 80 81 LoopUnrollResult UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI, 82 ScalarEvolution *SE, DominatorTree *DT, 83 AssumptionCache *AC, OptimizationRemarkEmitter *ORE, 84 bool PreserveLCSSA, Loop **RemainderLoop = nullptr); 85 86 bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, 87 bool AllowExpensiveTripCount, 88 bool UseEpilogRemainder, bool UnrollRemainder, 89 bool ForgetAllSCEV, LoopInfo *LI, 90 ScalarEvolution *SE, DominatorTree *DT, 91 AssumptionCache *AC, bool PreserveLCSSA, 92 Loop **ResultLoop = nullptr); 93 94 void computePeelCount(Loop *L, unsigned LoopSize, 95 TargetTransformInfo::UnrollingPreferences &UP, 96 unsigned &TripCount, ScalarEvolution &SE); 97 98 bool canPeel(Loop *L); 99 100 bool peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI, ScalarEvolution *SE, 101 DominatorTree *DT, AssumptionCache *AC, bool PreserveLCSSA); 102 103 LoopUnrollResult UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount, 104 unsigned TripMultiple, bool UnrollRemainder, 105 LoopInfo *LI, ScalarEvolution *SE, 106 DominatorTree *DT, AssumptionCache *AC, 107 OptimizationRemarkEmitter *ORE, 108 Loop **EpilogueLoop = nullptr); 109 110 bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT, 111 DependenceInfo &DI); 112 113 bool computeUnrollCount(Loop *L, const TargetTransformInfo &TTI, 114 DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE, 115 const SmallPtrSetImpl<const Value *> &EphValues, 116 OptimizationRemarkEmitter *ORE, unsigned &TripCount, 117 unsigned MaxTripCount, bool MaxOrZero, 118 unsigned &TripMultiple, unsigned LoopSize, 119 TargetTransformInfo::UnrollingPreferences &UP, 120 bool &UseUpperBound); 121 122 void remapInstruction(Instruction *I, ValueToValueMapTy &VMap); 123 124 void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, 125 ScalarEvolution *SE, DominatorTree *DT, 126 AssumptionCache *AC); 127 128 MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name); 129 130 TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences( 131 Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, 132 BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, int OptLevel, 133 Optional<unsigned> UserThreshold, Optional<unsigned> UserCount, 134 Optional<bool> UserAllowPartial, Optional<bool> UserRuntime, 135 Optional<bool> UserUpperBound, Optional<bool> UserAllowPeeling, 136 Optional<bool> UserAllowProfileBasedPeeling, 137 Optional<unsigned> UserFullUnrollMaxCount); 138 139 unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls, 140 bool &NotDuplicatable, bool &Convergent, 141 const TargetTransformInfo &TTI, 142 const SmallPtrSetImpl<const Value *> &EphValues, 143 unsigned BEInsns); 144 145 } // end namespace llvm 146 147 #endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H 148