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 
21 namespace llvm {
22 
23 class AssumptionCache;
24 class BasicBlock;
25 class BlockFrequencyInfo;
26 class DependenceInfo;
27 class DominatorTree;
28 class Loop;
29 class LoopInfo;
30 class MDNode;
31 class ProfileSummaryInfo;
32 class OptimizationRemarkEmitter;
33 class ScalarEvolution;
34 class StringRef;
35 class Value;
36 
37 using NewLoopsMap = SmallDenseMap<const Loop *, Loop *, 4>;
38 
39 /// @{
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";
46 /// @}
47 
48 const Loop* addClonedBlockToLoopInfo(BasicBlock *OriginalBB,
49                                      BasicBlock *ClonedBB, LoopInfo *LI,
50                                      NewLoopsMap &NewLoops);
51 
52 /// Represents the result of a \c UnrollLoop invocation.
53 enum 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 
67 struct 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 
81 LoopUnrollResult 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 
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);
94 
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);
102 
103 bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT,
104                           DependenceInfo &DI, LoopInfo &LI);
105 
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);
115 
116 void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI,
117                              ScalarEvolution *SE, DominatorTree *DT,
118                              AssumptionCache *AC,
119                              const TargetTransformInfo *TTI);
120 
121 MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name);
122 
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);
129 
130 unsigned 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