xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/BranchFolding.h (revision 2f513db72b034fd5ef7f080b11be5c711c15186a)
1 //===- BranchFolding.h - Fold machine code branch instructions --*- 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 #ifndef LLVM_LIB_CODEGEN_BRANCHFOLDING_H
10 #define LLVM_LIB_CODEGEN_BRANCHFOLDING_H
11 
12 #include "llvm/ADT/DenseMap.h"
13 #include "llvm/ADT/SmallPtrSet.h"
14 #include "llvm/CodeGen/LivePhysRegs.h"
15 #include "llvm/CodeGen/MachineBasicBlock.h"
16 #include "llvm/Support/BlockFrequency.h"
17 #include "llvm/Support/Compiler.h"
18 #include <cstdint>
19 #include <vector>
20 
21 namespace llvm {
22 
23 class BasicBlock;
24 class MachineBlockFrequencyInfo;
25 class MachineBranchProbabilityInfo;
26 class MachineFunction;
27 class MachineLoopInfo;
28 class MachineModuleInfo;
29 class MachineRegisterInfo;
30 class raw_ostream;
31 class TargetInstrInfo;
32 class TargetRegisterInfo;
33 
34   class LLVM_LIBRARY_VISIBILITY BranchFolder {
35   public:
36     class MBFIWrapper;
37 
38     explicit BranchFolder(bool defaultEnableTailMerge,
39                           bool CommonHoist,
40                           MBFIWrapper &FreqInfo,
41                           const MachineBranchProbabilityInfo &ProbInfo,
42                           // Min tail length to merge. Defaults to commandline
43                           // flag. Ignored for optsize.
44                           unsigned MinTailLength = 0);
45 
46     /// Perhaps branch folding, tail merging and other CFG optimizations on the
47     /// given function.  Block placement changes the layout and may create new
48     /// tail merging opportunities.
49     bool OptimizeFunction(MachineFunction &MF, const TargetInstrInfo *tii,
50                           const TargetRegisterInfo *tri, MachineModuleInfo *mmi,
51                           MachineLoopInfo *mli = nullptr,
52                           bool AfterPlacement = false);
53 
54   private:
55     class MergePotentialsElt {
56       unsigned Hash;
57       MachineBasicBlock *Block;
58 
59     public:
60       MergePotentialsElt(unsigned h, MachineBasicBlock *b)
61         : Hash(h), Block(b) {}
62 
63       unsigned getHash() const { return Hash; }
64       MachineBasicBlock *getBlock() const { return Block; }
65 
66       void setBlock(MachineBasicBlock *MBB) {
67         Block = MBB;
68       }
69 
70       bool operator<(const MergePotentialsElt &) const;
71     };
72 
73     using MPIterator = std::vector<MergePotentialsElt>::iterator;
74 
75     std::vector<MergePotentialsElt> MergePotentials;
76     SmallPtrSet<const MachineBasicBlock*, 2> TriedMerging;
77     DenseMap<const MachineBasicBlock *, int> EHScopeMembership;
78 
79     class SameTailElt {
80       MPIterator MPIter;
81       MachineBasicBlock::iterator TailStartPos;
82 
83     public:
84       SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp)
85         : MPIter(mp), TailStartPos(tsp) {}
86 
87       MPIterator getMPIter() const {
88         return MPIter;
89       }
90 
91       MergePotentialsElt &getMergePotentialsElt() const {
92         return *getMPIter();
93       }
94 
95       MachineBasicBlock::iterator getTailStartPos() const {
96         return TailStartPos;
97       }
98 
99       unsigned getHash() const {
100         return getMergePotentialsElt().getHash();
101       }
102 
103       MachineBasicBlock *getBlock() const {
104         return getMergePotentialsElt().getBlock();
105       }
106 
107       bool tailIsWholeBlock() const {
108         return TailStartPos == getBlock()->begin();
109       }
110 
111       void setBlock(MachineBasicBlock *MBB) {
112         getMergePotentialsElt().setBlock(MBB);
113       }
114 
115       void setTailStartPos(MachineBasicBlock::iterator Pos) {
116         TailStartPos = Pos;
117       }
118     };
119     std::vector<SameTailElt> SameTails;
120 
121     bool AfterBlockPlacement;
122     bool EnableTailMerge;
123     bool EnableHoistCommonCode;
124     bool UpdateLiveIns;
125     unsigned MinCommonTailLength;
126     const TargetInstrInfo *TII;
127     const MachineRegisterInfo *MRI;
128     const TargetRegisterInfo *TRI;
129     MachineModuleInfo *MMI;
130     MachineLoopInfo *MLI;
131     LivePhysRegs LiveRegs;
132 
133   public:
134     /// This class keeps track of branch frequencies of newly created
135     /// blocks and tail-merged blocks.
136     class MBFIWrapper {
137     public:
138       MBFIWrapper(const MachineBlockFrequencyInfo &I) : MBFI(I) {}
139 
140       BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const;
141       void setBlockFreq(const MachineBasicBlock *MBB, BlockFrequency F);
142       raw_ostream &printBlockFreq(raw_ostream &OS,
143                                   const MachineBasicBlock *MBB) const;
144       raw_ostream &printBlockFreq(raw_ostream &OS,
145                                   const BlockFrequency Freq) const;
146       void view(const Twine &Name, bool isSimple = true);
147       uint64_t getEntryFreq() const;
148 
149     private:
150       const MachineBlockFrequencyInfo &MBFI;
151       DenseMap<const MachineBasicBlock *, BlockFrequency> MergedBBFreq;
152     };
153 
154   private:
155     MBFIWrapper &MBBFreqInfo;
156     const MachineBranchProbabilityInfo &MBPI;
157 
158     bool TailMergeBlocks(MachineFunction &MF);
159     bool TryTailMergeBlocks(MachineBasicBlock* SuccBB,
160                        MachineBasicBlock* PredBB,
161                        unsigned MinCommonTailLength);
162     void setCommonTailEdgeWeights(MachineBasicBlock &TailMBB);
163 
164     /// Delete the instruction OldInst and everything after it, replacing it
165     /// with an unconditional branch to NewDest.
166     void replaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
167                                  MachineBasicBlock &NewDest);
168 
169     /// Given a machine basic block and an iterator into it, split the MBB so
170     /// that the part before the iterator falls into the part starting at the
171     /// iterator.  This returns the new MBB.
172     MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB,
173                                   MachineBasicBlock::iterator BBI1,
174                                   const BasicBlock *BB);
175 
176     /// Look through all the blocks in MergePotentials that have hash CurHash
177     /// (guaranteed to match the last element).  Build the vector SameTails of
178     /// all those that have the (same) largest number of instructions in common
179     /// of any pair of these blocks.  SameTails entries contain an iterator into
180     /// MergePotentials (from which the MachineBasicBlock can be found) and a
181     /// MachineBasicBlock::iterator into that MBB indicating the instruction
182     /// where the matching code sequence begins.  Order of elements in SameTails
183     /// is the reverse of the order in which those blocks appear in
184     /// MergePotentials (where they are not necessarily consecutive).
185     unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength,
186                               MachineBasicBlock *SuccBB,
187                               MachineBasicBlock *PredBB);
188 
189     /// Remove all blocks with hash CurHash from MergePotentials, restoring
190     /// branches at ends of blocks as appropriate.
191     void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock* SuccBB,
192                                                 MachineBasicBlock* PredBB);
193 
194     /// None of the blocks to be tail-merged consist only of the common tail.
195     /// Create a block that does by splitting one.
196     bool CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
197                                    MachineBasicBlock *SuccBB,
198                                    unsigned maxCommonTailLength,
199                                    unsigned &commonTailIndex);
200 
201     /// Create merged DebugLocs of identical instructions across SameTails and
202     /// assign it to the instruction in common tail; merge MMOs and undef flags.
203     void mergeCommonTails(unsigned commonTailIndex);
204 
205     bool OptimizeBranches(MachineFunction &MF);
206 
207     /// Analyze and optimize control flow related to the specified block. This
208     /// is never called on the entry block.
209     bool OptimizeBlock(MachineBasicBlock *MBB);
210 
211     /// Remove the specified dead machine basic block from the function,
212     /// updating the CFG.
213     void RemoveDeadBlock(MachineBasicBlock *MBB);
214 
215     /// Hoist common instruction sequences at the start of basic blocks to their
216     /// common predecessor.
217     bool HoistCommonCode(MachineFunction &MF);
218 
219     /// If the successors of MBB has common instruction sequence at the start of
220     /// the function, move the instructions before MBB terminator if it's legal.
221     bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB);
222   };
223 
224 } // end namespace llvm
225 
226 #endif // LLVM_LIB_CODEGEN_BRANCHFOLDING_H
227