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