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 {
71 bool AllowExpensiveTripCount;
76 LoopUnrollResult UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI,
77 ScalarEvolution *SE, DominatorTree *DT,
79 const llvm::TargetTransformInfo *TTI,
80 OptimizationRemarkEmitter *ORE, bool PreserveLCSSA,
81 Loop **RemainderLoop = nullptr);
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);
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);
98 bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT,
99 DependenceInfo &DI, LoopInfo &LI);
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);
111 void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI,
112 ScalarEvolution *SE, DominatorTree *DT,
114 const TargetTransformInfo *TTI);
116 MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name);
118 TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences(
119 Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI,
120 BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI,
121 llvm::OptimizationRemarkEmitter &ORE, int OptLevel,
122 Optional<unsigned> UserThreshold, Optional<unsigned> UserCount,
123 Optional<bool> UserAllowPartial, Optional<bool> UserRuntime,
124 Optional<bool> UserUpperBound, Optional<unsigned> UserFullUnrollMaxCount);
126 unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls,
127 bool &NotDuplicatable, bool &Convergent,
128 const TargetTransformInfo &TTI,
129 const SmallPtrSetImpl<const Value *> &EphValues,
132 } // end namespace llvm
134 #endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H