LLVM 19.0.0git
BranchFolding.h
Go to the documentation of this file.
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"
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
32 public:
33 explicit BranchFolder(bool DefaultEnableTailMerge, bool CommonHoist,
34 MBFIWrapper &FreqInfo,
35 const MachineBranchProbabilityInfo &ProbInfo,
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
54 public:
55 MergePotentialsElt(unsigned h, MachineBasicBlock *b)
56 : Hash(h), Block(b) {}
57
58 unsigned getHash() const { return Hash; }
59 MachineBasicBlock *getBlock() const { return Block; }
60
61 void setBlock(MachineBasicBlock *MBB) {
62 Block = MBB;
63 }
64
65 bool operator<(const MergePotentialsElt &) const;
66 };
67
68 using MPIterator = std::vector<MergePotentialsElt>::iterator;
69
70 std::vector<MergePotentialsElt> MergePotentials;
73
74 class SameTailElt {
75 MPIterator MPIter;
76 MachineBasicBlock::iterator TailStartPos;
77
78 public:
79 SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp)
80 : MPIter(mp), TailStartPos(tsp) {}
81
82 MPIterator getMPIter() const {
83 return MPIter;
84 }
85
86 MergePotentialsElt &getMergePotentialsElt() const {
87 return *getMPIter();
88 }
89
90 MachineBasicBlock::iterator getTailStartPos() const {
91 return TailStartPos;
92 }
93
94 unsigned getHash() const {
95 return getMergePotentialsElt().getHash();
96 }
97
98 MachineBasicBlock *getBlock() const {
99 return getMergePotentialsElt().getBlock();
100 }
101
102 bool tailIsWholeBlock() const {
103 return TailStartPos == getBlock()->begin();
104 }
105
106 void setBlock(MachineBasicBlock *MBB) {
107 getMergePotentialsElt().setBlock(MBB);
108 }
109
110 void setTailStartPos(MachineBasicBlock::iterator Pos) {
111 TailStartPos = Pos;
112 }
113 };
114 std::vector<SameTailElt> SameTails;
115
116 bool AfterBlockPlacement = false;
117 bool EnableTailMerge = false;
118 bool EnableHoistCommonCode = false;
119 bool UpdateLiveIns = false;
120 unsigned MinCommonTailLength;
121 const TargetInstrInfo *TII = nullptr;
122 const MachineRegisterInfo *MRI = nullptr;
123 const TargetRegisterInfo *TRI = nullptr;
124 MachineLoopInfo *MLI = nullptr;
125 LivePhysRegs LiveRegs;
126
127 private:
128 MBFIWrapper &MBBFreqInfo;
131
132 bool TailMergeBlocks(MachineFunction &MF);
133 bool TryTailMergeBlocks(MachineBasicBlock* SuccBB,
134 MachineBasicBlock* PredBB,
135 unsigned MinCommonTailLength);
136 void setCommonTailEdgeWeights(MachineBasicBlock &TailMBB);
137
138 /// Delete the instruction OldInst and everything after it, replacing it
139 /// with an unconditional branch to NewDest.
140 void replaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
141 MachineBasicBlock &NewDest);
142
143 /// Given a machine basic block and an iterator into it, split the MBB so
144 /// that the part before the iterator falls into the part starting at the
145 /// iterator. This returns the new MBB.
146 MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB,
148 const BasicBlock *BB);
149
150 /// Look through all the blocks in MergePotentials that have hash CurHash
151 /// (guaranteed to match the last element). Build the vector SameTails of
152 /// all those that have the (same) largest number of instructions in common
153 /// of any pair of these blocks. SameTails entries contain an iterator into
154 /// MergePotentials (from which the MachineBasicBlock can be found) and a
155 /// MachineBasicBlock::iterator into that MBB indicating the instruction
156 /// where the matching code sequence begins. Order of elements in SameTails
157 /// is the reverse of the order in which those blocks appear in
158 /// MergePotentials (where they are not necessarily consecutive).
159 unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength,
160 MachineBasicBlock *SuccBB,
161 MachineBasicBlock *PredBB);
162
163 /// Remove all blocks with hash CurHash from MergePotentials, restoring
164 /// branches at ends of blocks as appropriate.
165 void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock* SuccBB,
166 MachineBasicBlock* PredBB);
167
168 /// None of the blocks to be tail-merged consist only of the common tail.
169 /// Create a block that does by splitting one.
170 bool CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
171 MachineBasicBlock *SuccBB,
172 unsigned maxCommonTailLength,
173 unsigned &commonTailIndex);
174
175 /// Create merged DebugLocs of identical instructions across SameTails and
176 /// assign it to the instruction in common tail; merge MMOs and undef flags.
177 void mergeCommonTails(unsigned commonTailIndex);
178
179 bool OptimizeBranches(MachineFunction &MF);
180
181 /// Analyze and optimize control flow related to the specified block. This
182 /// is never called on the entry block.
183 bool OptimizeBlock(MachineBasicBlock *MBB);
184
185 /// Remove the specified dead machine basic block from the function,
186 /// updating the CFG.
187 void RemoveDeadBlock(MachineBasicBlock *MBB);
188
189 /// Hoist common instruction sequences at the start of basic blocks to their
190 /// common predecessor.
191 bool HoistCommonCode(MachineFunction &MF);
192
193 /// If the successors of MBB has common instruction sequence at the start of
194 /// the function, move the instructions before MBB terminator if it's legal.
195 bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB);
196 };
197
198} // end namespace llvm
199
200#endif // LLVM_LIB_CODEGEN_BRANCHFOLDING_H
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
#define LLVM_LIBRARY_VISIBILITY
Definition: Compiler.h:131
This file defines the DenseMap class.
const HexagonInstrInfo * TII
bool operator<(const DeltaInfo &LHS, int64_t Delta)
Definition: LineTable.cpp:30
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
unsigned const TargetRegisterInfo * TRI
This file defines the SmallPtrSet class.
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:50
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Analysis providing profile information.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
TargetInstrInfo - Interface to description of machine instruction set.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18