1 //===- BranchFolding.h - Fold machine code branch instructions --*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 #ifndef LLVM_LIB_CODEGEN_BRANCHFOLDING_H
10 #define LLVM_LIB_CODEGEN_BRANCHFOLDING_H
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"
23 class MachineBranchProbabilityInfo
;
24 class MachineFunction
;
25 class MachineLoopInfo
;
26 class MachineModuleInfo
;
27 class MachineRegisterInfo
;
29 class ProfileSummaryInfo
;
30 class TargetInstrInfo
;
31 class TargetRegisterInfo
;
33 class LLVM_LIBRARY_VISIBILITY BranchFolder
{
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);
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);
52 class MergePotentialsElt
{
54 MachineBasicBlock
*Block
;
57 MergePotentialsElt(unsigned h
, MachineBasicBlock
*b
)
58 : Hash(h
), Block(b
) {}
60 unsigned getHash() const { return Hash
; }
61 MachineBasicBlock
*getBlock() const { return Block
; }
63 void setBlock(MachineBasicBlock
*MBB
) {
67 bool operator<(const MergePotentialsElt
&) const;
70 using MPIterator
= std::vector
<MergePotentialsElt
>::iterator
;
72 std::vector
<MergePotentialsElt
> MergePotentials
;
73 SmallPtrSet
<const MachineBasicBlock
*, 2> TriedMerging
;
74 DenseMap
<const MachineBasicBlock
*, int> EHScopeMembership
;
78 MachineBasicBlock::iterator TailStartPos
;
81 SameTailElt(MPIterator mp
, MachineBasicBlock::iterator tsp
)
82 : MPIter(mp
), TailStartPos(tsp
) {}
84 MPIterator
getMPIter() const {
88 MergePotentialsElt
&getMergePotentialsElt() const {
92 MachineBasicBlock::iterator
getTailStartPos() const {
96 unsigned getHash() const {
97 return getMergePotentialsElt().getHash();
100 MachineBasicBlock
*getBlock() const {
101 return getMergePotentialsElt().getBlock();
104 bool tailIsWholeBlock() const {
105 return TailStartPos
== getBlock()->begin();
108 void setBlock(MachineBasicBlock
*MBB
) {
109 getMergePotentialsElt().setBlock(MBB
);
112 void setTailStartPos(MachineBasicBlock::iterator Pos
) {
116 std::vector
<SameTailElt
> SameTails
;
118 bool AfterBlockPlacement
;
119 bool EnableTailMerge
;
120 bool EnableHoistCommonCode
;
122 unsigned MinCommonTailLength
;
123 const TargetInstrInfo
*TII
;
124 const MachineRegisterInfo
*MRI
;
125 const TargetRegisterInfo
*TRI
;
126 MachineLoopInfo
*MLI
;
127 LivePhysRegs LiveRegs
;
130 MBFIWrapper
&MBBFreqInfo
;
131 const MachineBranchProbabilityInfo
&MBPI
;
132 ProfileSummaryInfo
*PSI
;
134 bool TailMergeBlocks(MachineFunction
&MF
);
135 bool TryTailMergeBlocks(MachineBasicBlock
* SuccBB
,
136 MachineBasicBlock
* PredBB
,
137 unsigned MinCommonTailLength
);
138 void setCommonTailEdgeWeights(MachineBasicBlock
&TailMBB
);
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
);
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
);
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
);
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
);
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
);
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
);
181 bool OptimizeBranches(MachineFunction
&MF
);
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
);
187 /// Remove the specified dead machine basic block from the function,
188 /// updating the CFG.
189 void RemoveDeadBlock(MachineBasicBlock
*MBB
);
191 /// Hoist common instruction sequences at the start of basic blocks to their
192 /// common predecessor.
193 bool HoistCommonCode(MachineFunction
&MF
);
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
);
200 } // end namespace llvm
202 #endif // LLVM_LIB_CODEGEN_BRANCHFOLDING_H