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