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