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