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