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 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);
103 bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT,
104 DependenceInfo &DI, LoopInfo &LI);
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);
116 void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI,
117 ScalarEvolution *SE, DominatorTree *DT,
119 const TargetTransformInfo *TTI);
121 MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name);
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);
130 unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls,
131 bool &NotDuplicatable, bool &Convergent,
132 const TargetTransformInfo &TTI,
133 const SmallPtrSetImpl<const Value *> &EphValues,
136 } // end namespace llvm
138 #endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H