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 
22 namespace llvm {
23 
24 class AssumptionCache;
25 class BasicBlock;
26 class BlockFrequencyInfo;
27 class DependenceInfo;
28 class DominatorTree;
29 class Loop;
30 class LoopInfo;
31 class MDNode;
32 class ProfileSummaryInfo;
33 class OptimizationRemarkEmitter;
34 class ScalarEvolution;
35 class StringRef;
36 class Value;
37 
38 using NewLoopsMap = SmallDenseMap<const Loop *, Loop *, 4>;
39 
40 /// @{
41 /// Metadata attribute names
42 const char *const LLVMLoopUnrollFollowupAll = "llvm.loop.unroll.followup_all";
43 const char *const LLVMLoopUnrollFollowupUnrolled =
44     "llvm.loop.unroll.followup_unrolled";
45 const char *const LLVMLoopUnrollFollowupRemainder =
46     "llvm.loop.unroll.followup_remainder";
47 /// @}
48 
49 const Loop* addClonedBlockToLoopInfo(BasicBlock *OriginalBB,
50                                      BasicBlock *ClonedBB, LoopInfo *LI,
51                                      NewLoopsMap &NewLoops);
52 
53 /// Represents the result of a \c UnrollLoop invocation.
54 enum 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 
68 struct UnrollLoopOptions {
69   unsigned Count;
70   bool Force;
71   bool Runtime;
72   bool AllowExpensiveTripCount;
73   bool UnrollRemainder;
74   bool ForgetAllSCEV;
75 };
76 
77 LoopUnrollResult 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 
84 bool 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 
91 LoopUnrollResult 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 
99 bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT,
100                           DependenceInfo &DI, LoopInfo &LI);
101 
102 bool computeUnrollCount(Loop *L, const TargetTransformInfo &TTI,
103                         DominatorTree &DT, LoopInfo *LI, AssumptionCache *AC,
104                         ScalarEvolution &SE,
105                         const SmallPtrSetImpl<const Value *> &EphValues,
106                         OptimizationRemarkEmitter *ORE, unsigned TripCount,
107                         unsigned MaxTripCount, bool MaxOrZero,
108                         unsigned TripMultiple, unsigned LoopSize,
109                         TargetTransformInfo::UnrollingPreferences &UP,
110                         TargetTransformInfo::PeelingPreferences &PP,
111                         bool &UseUpperBound);
112 
113 void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI,
114                              ScalarEvolution *SE, DominatorTree *DT,
115                              AssumptionCache *AC,
116                              const TargetTransformInfo *TTI);
117 
118 MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name);
119 
120 TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences(
121     Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI,
122     BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI,
123     llvm::OptimizationRemarkEmitter &ORE, int OptLevel,
124     std::optional<unsigned> UserThreshold, std::optional<unsigned> UserCount,
125     std::optional<bool> UserAllowPartial, std::optional<bool> UserRuntime,
126     std::optional<bool> UserUpperBound,
127     std::optional<unsigned> UserFullUnrollMaxCount);
128 
129 InstructionCost ApproximateLoopSize(const Loop *L, unsigned &NumCalls,
130     bool &NotDuplicatable, bool &Convergent, const TargetTransformInfo &TTI,
131     const SmallPtrSetImpl<const Value *> &EphValues, unsigned BEInsns);
132 
133 } // end namespace llvm
134 
135 #endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
136