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