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#include "llvm/Support/InstructionCost.h"
21
22namespace llvm {
23
24class AssumptionCache;
25class BasicBlock;
26class BlockFrequencyInfo;
27class DependenceInfo;
28class DominatorTree;
29class Loop;
30class LoopInfo;
31class MDNode;
32class ProfileSummaryInfo;
33class OptimizationRemarkEmitter;
34class ScalarEvolution;
35class StringRef;
36class Value;
37
38using NewLoopsMap = SmallDenseMap<const Loop *, Loop *, 4>;
39
40/// @{
41/// Metadata attribute names
42const char *const LLVMLoopUnrollFollowupAll = "llvm.loop.unroll.followup_all";
43const char *const LLVMLoopUnrollFollowupUnrolled =
44 "llvm.loop.unroll.followup_unrolled";
45const char *const LLVMLoopUnrollFollowupRemainder =
46 "llvm.loop.unroll.followup_remainder";
47/// @}
48
49const Loop* addClonedBlockToLoopInfo(BasicBlock *OriginalBB,
50 BasicBlock *ClonedBB, LoopInfo *LI,
51 NewLoopsMap &NewLoops);
52
53/// Represents the result of a \c UnrollLoop invocation.
54enum class LoopUnrollResult {
55 /// The loop was not modified.
56 Unmodified,
57
58 /// The loop was partially unrolled -- we still have a loop, but with a
59 /// smaller trip count. We may also have emitted epilogue loop if the loop
60 /// had a non-constant trip count.
61 PartiallyUnrolled,
62
63 /// The loop was fully unrolled into straight-line code. We no longer have
64 /// any back-edges.
65 FullyUnrolled
66};
67
68struct UnrollLoopOptions {
69 unsigned Count;
70 bool Force;
71 bool Runtime;
72 bool AllowExpensiveTripCount;
73 bool UnrollRemainder;
74 bool ForgetAllSCEV;
75};
76
77LoopUnrollResult UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI,
78 ScalarEvolution *SE, DominatorTree *DT,
79 AssumptionCache *AC,
80 const llvm::TargetTransformInfo *TTI,
81 OptimizationRemarkEmitter *ORE, bool PreserveLCSSA,
82 Loop **RemainderLoop = nullptr);
83
84bool UnrollRuntimeLoopRemainder(
85 Loop *L, unsigned Count, bool AllowExpensiveTripCount,
86 bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV,
87 LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC,
88 const TargetTransformInfo *TTI, bool PreserveLCSSA,
89 Loop **ResultLoop = nullptr);
90
91LoopUnrollResult UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount,
92 unsigned TripMultiple, bool UnrollRemainder,
93 LoopInfo *LI, ScalarEvolution *SE,
94 DominatorTree *DT, AssumptionCache *AC,
95 const TargetTransformInfo *TTI,
96 OptimizationRemarkEmitter *ORE,
97 Loop **EpilogueLoop = nullptr);
98
99bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT,
100 DependenceInfo &DI, LoopInfo &LI);
101
102void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI,
103 ScalarEvolution *SE, DominatorTree *DT,
104 AssumptionCache *AC,
105 const TargetTransformInfo *TTI);
106
107MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name);
108
109TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences(
110 Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI,
111 BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI,
112 llvm::OptimizationRemarkEmitter &ORE, int OptLevel,
113 std::optional<unsigned> UserThreshold, std::optional<unsigned> UserCount,
114 std::optional<bool> UserAllowPartial, std::optional<bool> UserRuntime,
115 std::optional<bool> UserUpperBound,
116 std::optional<unsigned> UserFullUnrollMaxCount);
117
118/// Produce an estimate of the unrolled cost of the specified loop. This
119/// is used to a) produce a cost estimate for partial unrolling and b) to
120/// cheaply estimate cost for full unrolling when we don't want to symbolically
121/// evaluate all iterations.
122class UnrollCostEstimator {
123 InstructionCost LoopSize;
124 bool NotDuplicatable;
125
126public:
127 unsigned NumInlineCandidates;
128 bool Convergent;
129
130 UnrollCostEstimator(const Loop *L, const TargetTransformInfo &TTI,
131 const SmallPtrSetImpl<const Value *> &EphValues,
132 unsigned BEInsns);
133
134 /// Whether it is legal to unroll this loop.
135 bool canUnroll() const { return LoopSize.isValid() && !NotDuplicatable; }
136
137 uint64_t getRolledLoopSize() const { return *LoopSize.getValue(); }
138
139 /// Returns loop size estimation for unrolled loop, given the unrolling
140 /// configuration specified by UP.
141 uint64_t
142 getUnrolledLoopSize(const TargetTransformInfo::UnrollingPreferences &UP,
143 unsigned CountOverwrite = 0) const;
144};
145
146bool computeUnrollCount(Loop *L, const TargetTransformInfo &TTI,
147 DominatorTree &DT, LoopInfo *LI, AssumptionCache *AC,
148 ScalarEvolution &SE,
149 const SmallPtrSetImpl<const Value *> &EphValues,
150 OptimizationRemarkEmitter *ORE, unsigned TripCount,
151 unsigned MaxTripCount, bool MaxOrZero,
152 unsigned TripMultiple, const UnrollCostEstimator &UCE,
153 TargetTransformInfo::UnrollingPreferences &UP,
154 TargetTransformInfo::PeelingPreferences &PP,
155 bool &UseUpperBound);
156
157} // end namespace llvm
158
159#endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
160

source code of llvm/include/llvm/Transforms/Utils/UnrollLoop.h