[ORC] Add std::tuple support to SimplePackedSerialization.
[llvm-project.git] / llvm / lib / CodeGen / BranchFolding.h
blob2a4ea92a92aa60d67f4b66bbfeaaff13bbfff5a3
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 //===----------------------------------------------------------------------===//
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"
17 #include <cstdint>
18 #include <vector>
20 namespace llvm {
22 class BasicBlock;
23 class MachineBranchProbabilityInfo;
24 class MachineFunction;
25 class MachineLoopInfo;
26 class MachineModuleInfo;
27 class MachineRegisterInfo;
28 class MBFIWrapper;
29 class ProfileSummaryInfo;
30 class TargetInstrInfo;
31 class TargetRegisterInfo;
33 class LLVM_LIBRARY_VISIBILITY BranchFolder {
34 public:
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);
51 private:
52 class MergePotentialsElt {
53 unsigned Hash;
54 MachineBasicBlock *Block;
56 public:
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) {
64 Block = 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;
76 class SameTailElt {
77 MPIterator MPIter;
78 MachineBasicBlock::iterator TailStartPos;
80 public:
81 SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp)
82 : MPIter(mp), TailStartPos(tsp) {}
84 MPIterator getMPIter() const {
85 return MPIter;
88 MergePotentialsElt &getMergePotentialsElt() const {
89 return *getMPIter();
92 MachineBasicBlock::iterator getTailStartPos() const {
93 return TailStartPos;
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) {
113 TailStartPos = Pos;
116 std::vector<SameTailElt> SameTails;
118 bool AfterBlockPlacement;
119 bool EnableTailMerge;
120 bool EnableHoistCommonCode;
121 bool UpdateLiveIns;
122 unsigned MinCommonTailLength;
123 const TargetInstrInfo *TII;
124 const MachineRegisterInfo *MRI;
125 const TargetRegisterInfo *TRI;
126 MachineLoopInfo *MLI;
127 LivePhysRegs LiveRegs;
129 private:
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