1 //===- llvm/Transforms/Utils/UnrollLoop.h - Unrolling utilities -*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines some loop unrolling utilities. It does not define any
11 // actual pass or policy, but provides a single function to perform loop
12 // unrolling.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #ifndef LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
17 #define LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
18 
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/StringRef.h"
21 #include "llvm/Analysis/TargetTransformInfo.h"
22 #include "llvm/Transforms/Utils/ValueMapper.h"
23 
24 namespace llvm {
25 
26 class AssumptionCache;
27 class BasicBlock;
28 class DependenceInfo;
29 class DominatorTree;
30 class Loop;
31 class LoopInfo;
32 class MDNode;
33 class OptimizationRemarkEmitter;
34 class ScalarEvolution;
35 
36 using NewLoopsMap = SmallDenseMap<const Loop *, Loop *, 4>;
37 
38 /// @{
39 /// Metadata attribute names
40 const char *const LLVMLoopUnrollFollowupAll = "llvm.loop.unroll.followup_all";
41 const char *const LLVMLoopUnrollFollowupUnrolled =
42     "llvm.loop.unroll.followup_unrolled";
43 const char *const LLVMLoopUnrollFollowupRemainder =
44     "llvm.loop.unroll.followup_remainder";
45 /// @}
46 
47 const Loop* addClonedBlockToLoopInfo(BasicBlock *OriginalBB,
48                                      BasicBlock *ClonedBB, LoopInfo *LI,
49                                      NewLoopsMap &NewLoops);
50 
51 /// Represents the result of a \c UnrollLoop invocation.
52 enum class LoopUnrollResult {
53   /// The loop was not modified.
54   Unmodified,
55 
56   /// The loop was partially unrolled -- we still have a loop, but with a
57   /// smaller trip count.  We may also have emitted epilogue loop if the loop
58   /// had a non-constant trip count.
59   PartiallyUnrolled,
60 
61   /// The loop was fully unrolled into straight-line code.  We no longer have
62   /// any back-edges.
63   FullyUnrolled
64 };
65 
66 LoopUnrollResult UnrollLoop(Loop *L, unsigned Count, unsigned TripCount,
67                             bool Force, bool AllowRuntime,
68                             bool AllowExpensiveTripCount, bool PreserveCondBr,
69                             bool PreserveOnlyFirst, unsigned TripMultiple,
70                             unsigned PeelCount, bool UnrollRemainder,
71                             LoopInfo *LI, ScalarEvolution *SE,
72                             DominatorTree *DT, AssumptionCache *AC,
73                             OptimizationRemarkEmitter *ORE, bool PreserveLCSSA,
74                             Loop **RemainderLoop = nullptr);
75 
76 bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count,
77                                 bool AllowExpensiveTripCount,
78                                 bool UseEpilogRemainder, bool UnrollRemainder,
79                                 LoopInfo *LI, ScalarEvolution *SE,
80                                 DominatorTree *DT, AssumptionCache *AC,
81                                 bool PreserveLCSSA,
82                                 Loop **ResultLoop = nullptr);
83 
84 void computePeelCount(Loop *L, unsigned LoopSize,
85                       TargetTransformInfo::UnrollingPreferences &UP,
86                       unsigned &TripCount, ScalarEvolution &SE);
87 
88 bool canPeel(Loop *L);
89 
90 bool peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI, ScalarEvolution *SE,
91               DominatorTree *DT, AssumptionCache *AC, bool PreserveLCSSA);
92 
93 LoopUnrollResult UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount,
94                                   unsigned TripMultiple, bool UnrollRemainder,
95                                   LoopInfo *LI, ScalarEvolution *SE,
96                                   DominatorTree *DT, AssumptionCache *AC,
97                                   OptimizationRemarkEmitter *ORE,
98                                   Loop **EpilogueLoop = nullptr);
99 
100 bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT,
101                           DependenceInfo &DI);
102 
103 bool computeUnrollCount(Loop *L, const TargetTransformInfo &TTI,
104                         DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE,
105                         const SmallPtrSetImpl<const Value *> &EphValues,
106                         OptimizationRemarkEmitter *ORE, unsigned &TripCount,
107                         unsigned MaxTripCount, unsigned &TripMultiple,
108                         unsigned LoopSize,
109                         TargetTransformInfo::UnrollingPreferences &UP,
110                         bool &UseUpperBound);
111 
112 BasicBlock *foldBlockIntoPredecessor(BasicBlock *BB, LoopInfo *LI,
113                                      ScalarEvolution *SE, DominatorTree *DT);
114 
115 void remapInstruction(Instruction *I, ValueToValueMapTy &VMap);
116 
117 void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI,
118                              ScalarEvolution *SE, DominatorTree *DT,
119                              AssumptionCache *AC);
120 
121 MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name);
122 
123 TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences(
124     Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, int OptLevel,
125     Optional<unsigned> UserThreshold, Optional<unsigned> UserCount,
126     Optional<bool> UserAllowPartial, Optional<bool> UserRuntime,
127     Optional<bool> UserUpperBound, Optional<bool> UserAllowPeeling);
128 
129 unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls,
130                              bool &NotDuplicatable, bool &Convergent,
131                              const TargetTransformInfo &TTI,
132                              const SmallPtrSetImpl<const Value *> &EphValues,
133                              unsigned BEInsns);
134 
135 } // end namespace llvm
136 
137 #endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
138