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 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, 84 const llvm::TargetTransformInfo *TTI, 85 OptimizationRemarkEmitter *ORE, bool PreserveLCSSA, 86 Loop **RemainderLoop = 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 bool computeUnrollCount(Loop *L, const TargetTransformInfo &TTI, 107 DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE, 108 const SmallPtrSetImpl<const Value *> &EphValues, 109 OptimizationRemarkEmitter *ORE, unsigned &TripCount, 110 unsigned MaxTripCount, bool MaxOrZero, 111 unsigned &TripMultiple, unsigned LoopSize, 112 TargetTransformInfo::UnrollingPreferences &UP, 113 TargetTransformInfo::PeelingPreferences &PP, 114 bool &UseUpperBound); 115 116 void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, 117 ScalarEvolution *SE, DominatorTree *DT, 118 AssumptionCache *AC, 119 const TargetTransformInfo *TTI); 120 121 MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name); 122 123 TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences( 124 Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, 125 BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, int OptLevel, 126 Optional<unsigned> UserThreshold, Optional<unsigned> UserCount, 127 Optional<bool> UserAllowPartial, Optional<bool> UserRuntime, 128 Optional<bool> UserUpperBound, Optional<unsigned> UserFullUnrollMaxCount); 129 130 unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls, 131 bool &NotDuplicatable, bool &Convergent, 132 const TargetTransformInfo &TTI, 133 const SmallPtrSetImpl<const Value *> &EphValues, 134 unsigned BEInsns); 135 136 } // end namespace llvm 137 138 #endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H 139