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