1 //===- llvm/Transforms/Utils/UnrollLoop.h - Unrolling utilities -*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
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
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
16 #define LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/Analysis/TargetTransformInfo.h"
23 class AssumptionCache;
25 class BlockFrequencyInfo;
31 class ProfileSummaryInfo;
32 class OptimizationRemarkEmitter;
33 class ScalarEvolution;
37 using NewLoopsMap = SmallDenseMap<const Loop *, Loop *, 4>;
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";
48 const Loop* addClonedBlockToLoopInfo(BasicBlock *OriginalBB,
49 BasicBlock *ClonedBB, LoopInfo *LI,
50 NewLoopsMap &NewLoops);
52 /// Represents the result of a \c UnrollLoop invocation.
53 enum class LoopUnrollResult {
54 /// The loop was not modified.
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.
62 /// The loop was fully unrolled into straight-line code. We no longer have
67 struct UnrollLoopOptions {
72 bool AllowExpensiveTripCount;
74 bool PreserveOnlyFirst;
75 unsigned TripMultiple;
81 LoopUnrollResult UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI,
82 ScalarEvolution *SE, DominatorTree *DT,
84 const llvm::TargetTransformInfo *TTI,
85 OptimizationRemarkEmitter *ORE, bool PreserveLCSSA,
86 Loop **RemainderLoop = nullptr);
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);
95 void computePeelCount(Loop *L, unsigned LoopSize,
96 TargetTransformInfo::UnrollingPreferences &UP,
97 TargetTransformInfo::PeelingPreferences &PP,
98 unsigned &TripCount, ScalarEvolution &SE);
100 bool canPeel(Loop *L);
102 bool peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI, ScalarEvolution *SE,
103 DominatorTree *DT, AssumptionCache *AC, bool PreserveLCSSA);
105 LoopUnrollResult UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount,
106 unsigned TripMultiple, bool UnrollRemainder,
107 LoopInfo *LI, ScalarEvolution *SE,
108 DominatorTree *DT, AssumptionCache *AC,
109 const TargetTransformInfo *TTI,
110 OptimizationRemarkEmitter *ORE,
111 Loop **EpilogueLoop = nullptr);
113 bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT,
114 DependenceInfo &DI, LoopInfo &LI);
116 bool computeUnrollCount(Loop *L, const TargetTransformInfo &TTI,
117 DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE,
118 const SmallPtrSetImpl<const Value *> &EphValues,
119 OptimizationRemarkEmitter *ORE, unsigned &TripCount,
120 unsigned MaxTripCount, bool MaxOrZero,
121 unsigned &TripMultiple, unsigned LoopSize,
122 TargetTransformInfo::UnrollingPreferences &UP,
123 TargetTransformInfo::PeelingPreferences &PP,
125 bool &UseUpperBound);
127 void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI,
128 ScalarEvolution *SE, DominatorTree *DT,
130 const TargetTransformInfo *TTI);
132 MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name);
134 TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences(
135 Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI,
136 BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, int OptLevel,
137 Optional<unsigned> UserThreshold, Optional<unsigned> UserCount,
138 Optional<bool> UserAllowPartial, Optional<bool> UserRuntime,
139 Optional<bool> UserUpperBound, Optional<unsigned> UserFullUnrollMaxCount);
141 TargetTransformInfo::PeelingPreferences
142 gatherPeelingPreferences(Loop *L, ScalarEvolution &SE,
143 const TargetTransformInfo &TTI,
144 Optional<bool> UserAllowPeeling,
145 Optional<bool> UserAllowProfileBasedPeeling);
147 unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls,
148 bool &NotDuplicatable, bool &Convergent,
149 const TargetTransformInfo &TTI,
150 const SmallPtrSetImpl<const Value *> &EphValues,
153 } // end namespace llvm
155 #endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H