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
21namespace llvm {
22
23class AssumptionCache;
24class BasicBlock;
25class BlockFrequencyInfo;
26class DependenceInfo;
27class DominatorTree;
28class Loop;
29class LoopInfo;
30class MDNode;
31class ProfileSummaryInfo;
32class OptimizationRemarkEmitter;
33class ScalarEvolution;
34class StringRef;
35class Value;
36
37using NewLoopsMap = SmallDenseMap<const Loop *, Loop *, 4>;
38
39/// @{
40/// Metadata attribute names
41const char *const LLVMLoopUnrollFollowupAll = "llvm.loop.unroll.followup_all";
42const char *const LLVMLoopUnrollFollowupUnrolled =
43 "llvm.loop.unroll.followup_unrolled";
44const char *const LLVMLoopUnrollFollowupRemainder =
45 "llvm.loop.unroll.followup_remainder";
46/// @}
47
48const Loop* addClonedBlockToLoopInfo(BasicBlock *OriginalBB,
49 BasicBlock *ClonedBB, LoopInfo *LI,
50 NewLoopsMap &NewLoops);
51
52/// Represents the result of a \c UnrollLoop invocation.
53enum class LoopUnrollResult {
54 /// The loop was not modified.
55 Unmodified,
56
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.
60 PartiallyUnrolled,
61
62 /// The loop was fully unrolled into straight-line code. We no longer have
63 /// any back-edges.
64 FullyUnrolled
65};
66
67struct UnrollLoopOptions {
68 unsigned Count;
69 unsigned TripCount;
70 bool Force;
71 bool AllowRuntime;
72 bool AllowExpensiveTripCount;
73 bool PreserveCondBr;
74 bool PreserveOnlyFirst;
75 unsigned TripMultiple;
76 unsigned PeelCount;
77 bool UnrollRemainder;
78 bool ForgetAllSCEV;
79};
80
81LoopUnrollResult UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI,
82 ScalarEvolution *SE, DominatorTree *DT,
83 AssumptionCache *AC,
84 const llvm::TargetTransformInfo *TTI,
85 OptimizationRemarkEmitter *ORE, bool PreserveLCSSA,
86 Loop **RemainderLoop = 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
106bool 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);
115
116void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI,
117 ScalarEvolution *SE, DominatorTree *DT,
118 AssumptionCache *AC,
119 const TargetTransformInfo *TTI);
120
121MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name);
122
123TargetTransformInfo::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);
129
130unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls,
131 bool &NotDuplicatable, bool &Convergent,
132 const TargetTransformInfo &TTI,
133 const SmallPtrSetImpl<const Value *> &EphValues,
134 unsigned BEInsns);
135
136} // end namespace llvm
137
138#endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
139