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