Line data Source code
1 : //===- BranchFolding.h - Fold machine code branch instructions --*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 :
10 : #ifndef LLVM_LIB_CODEGEN_BRANCHFOLDING_H
11 : #define LLVM_LIB_CODEGEN_BRANCHFOLDING_H
12 :
13 : #include "llvm/ADT/DenseMap.h"
14 : #include "llvm/ADT/SmallPtrSet.h"
15 : #include "llvm/CodeGen/LivePhysRegs.h"
16 : #include "llvm/CodeGen/MachineBasicBlock.h"
17 : #include "llvm/Support/BlockFrequency.h"
18 : #include "llvm/Support/Compiler.h"
19 : #include <cstdint>
20 : #include <vector>
21 :
22 : namespace llvm {
23 :
24 : class BasicBlock;
25 : class MachineBlockFrequencyInfo;
26 : class MachineBranchProbabilityInfo;
27 : class MachineFunction;
28 : class MachineLoopInfo;
29 : class MachineModuleInfo;
30 : class MachineRegisterInfo;
31 : class raw_ostream;
32 : class TargetInstrInfo;
33 : class TargetRegisterInfo;
34 :
35 : class LLVM_LIBRARY_VISIBILITY BranchFolder {
36 : public:
37 : class MBFIWrapper;
38 :
39 : explicit BranchFolder(bool defaultEnableTailMerge,
40 : bool CommonHoist,
41 : MBFIWrapper &FreqInfo,
42 : const MachineBranchProbabilityInfo &ProbInfo,
43 : // Min tail length to merge. Defaults to commandline
44 : // flag. Ignored for optsize.
45 : unsigned MinTailLength = 0);
46 :
47 : /// Perhaps branch folding, tail merging and other CFG optimizations on the
48 : /// given function. Block placement changes the layout and may create new
49 : /// tail merging opportunities.
50 : bool OptimizeFunction(MachineFunction &MF, const TargetInstrInfo *tii,
51 : const TargetRegisterInfo *tri, MachineModuleInfo *mmi,
52 : MachineLoopInfo *mli = nullptr,
53 : bool AfterPlacement = false);
54 :
55 : private:
56 : class MergePotentialsElt {
57 : unsigned Hash;
58 : MachineBasicBlock *Block;
59 :
60 : public:
61 : MergePotentialsElt(unsigned h, MachineBasicBlock *b)
62 862005 : : Hash(h), Block(b) {}
63 :
64 0 : unsigned getHash() const { return Hash; }
65 0 : MachineBasicBlock *getBlock() const { return Block; }
66 :
67 0 : void setBlock(MachineBasicBlock *MBB) {
68 7802 : Block = MBB;
69 0 : }
70 :
71 : bool operator<(const MergePotentialsElt &) const;
72 : };
73 :
74 : using MPIterator = std::vector<MergePotentialsElt>::iterator;
75 :
76 : std::vector<MergePotentialsElt> MergePotentials;
77 : SmallPtrSet<const MachineBasicBlock*, 2> TriedMerging;
78 : DenseMap<const MachineBasicBlock *, int> EHScopeMembership;
79 :
80 : class SameTailElt {
81 : MPIterator MPIter;
82 : MachineBasicBlock::iterator TailStartPos;
83 :
84 : public:
85 : SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp)
86 47611 : : MPIter(mp), TailStartPos(tsp) {}
87 :
88 0 : MPIterator getMPIter() const {
89 0 : return MPIter;
90 : }
91 :
92 : MergePotentialsElt &getMergePotentialsElt() const {
93 : return *getMPIter();
94 : }
95 :
96 0 : MachineBasicBlock::iterator getTailStartPos() const {
97 0 : return TailStartPos;
98 : }
99 :
100 : unsigned getHash() const {
101 : return getMergePotentialsElt().getHash();
102 : }
103 :
104 : MachineBasicBlock *getBlock() const {
105 145703 : return getMergePotentialsElt().getBlock();
106 : }
107 :
108 : bool tailIsWholeBlock() const {
109 : return TailStartPos == getBlock()->begin();
110 : }
111 :
112 : void setBlock(MachineBasicBlock *MBB) {
113 : getMergePotentialsElt().setBlock(MBB);
114 : }
115 :
116 0 : void setTailStartPos(MachineBasicBlock::iterator Pos) {
117 7802 : TailStartPos = Pos;
118 0 : }
119 : };
120 : std::vector<SameTailElt> SameTails;
121 :
122 : bool AfterBlockPlacement;
123 : bool EnableTailMerge;
124 : bool EnableHoistCommonCode;
125 : bool UpdateLiveIns;
126 : unsigned MinCommonTailLength;
127 : const TargetInstrInfo *TII;
128 : const MachineRegisterInfo *MRI;
129 : const TargetRegisterInfo *TRI;
130 : MachineModuleInfo *MMI;
131 : MachineLoopInfo *MLI;
132 : LivePhysRegs LiveRegs;
133 :
134 : public:
135 : /// This class keeps track of branch frequencies of newly created
136 : /// blocks and tail-merged blocks.
137 0 : class MBFIWrapper {
138 : public:
139 248557 : MBFIWrapper(const MachineBlockFrequencyInfo &I) : MBFI(I) {}
140 :
141 : BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const;
142 : void setBlockFreq(const MachineBasicBlock *MBB, BlockFrequency F);
143 : raw_ostream &printBlockFreq(raw_ostream &OS,
144 : const MachineBasicBlock *MBB) const;
145 : raw_ostream &printBlockFreq(raw_ostream &OS,
146 : const BlockFrequency Freq) const;
147 : void view(const Twine &Name, bool isSimple = true);
148 : uint64_t getEntryFreq() const;
149 :
150 : private:
151 : const MachineBlockFrequencyInfo &MBFI;
152 : DenseMap<const MachineBasicBlock *, BlockFrequency> MergedBBFreq;
153 : };
154 :
155 : private:
156 : MBFIWrapper &MBBFreqInfo;
157 : const MachineBranchProbabilityInfo &MBPI;
158 :
159 : bool TailMergeBlocks(MachineFunction &MF);
160 : bool TryTailMergeBlocks(MachineBasicBlock* SuccBB,
161 : MachineBasicBlock* PredBB,
162 : unsigned MinCommonTailLength);
163 : void setCommonTailEdgeWeights(MachineBasicBlock &TailMBB);
164 :
165 : /// Delete the instruction OldInst and everything after it, replacing it
166 : /// with an unconditional branch to NewDest.
167 : void replaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
168 : MachineBasicBlock &NewDest);
169 :
170 : /// Given a machine basic block and an iterator into it, split the MBB so
171 : /// that the part before the iterator falls into the part starting at the
172 : /// iterator. This returns the new MBB.
173 : MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB,
174 : MachineBasicBlock::iterator BBI1,
175 : const BasicBlock *BB);
176 :
177 : /// Look through all the blocks in MergePotentials that have hash CurHash
178 : /// (guaranteed to match the last element). Build the vector SameTails of
179 : /// all those that have the (same) largest number of instructions in common
180 : /// of any pair of these blocks. SameTails entries contain an iterator into
181 : /// MergePotentials (from which the MachineBasicBlock can be found) and a
182 : /// MachineBasicBlock::iterator into that MBB indicating the instruction
183 : /// where the matching code sequence begins. Order of elements in SameTails
184 : /// is the reverse of the order in which those blocks appear in
185 : /// MergePotentials (where they are not necessarily consecutive).
186 : unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength,
187 : MachineBasicBlock *SuccBB,
188 : MachineBasicBlock *PredBB);
189 :
190 : /// Remove all blocks with hash CurHash from MergePotentials, restoring
191 : /// branches at ends of blocks as appropriate.
192 : void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock* SuccBB,
193 : MachineBasicBlock* PredBB);
194 :
195 : /// None of the blocks to be tail-merged consist only of the common tail.
196 : /// Create a block that does by splitting one.
197 : bool CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
198 : MachineBasicBlock *SuccBB,
199 : unsigned maxCommonTailLength,
200 : unsigned &commonTailIndex);
201 :
202 : /// Create merged DebugLocs of identical instructions across SameTails and
203 : /// assign it to the instruction in common tail; merge MMOs and undef flags.
204 : void mergeCommonTails(unsigned commonTailIndex);
205 :
206 : bool OptimizeBranches(MachineFunction &MF);
207 :
208 : /// Analyze and optimize control flow related to the specified block. This
209 : /// is never called on the entry block.
210 : bool OptimizeBlock(MachineBasicBlock *MBB);
211 :
212 : /// Remove the specified dead machine basic block from the function,
213 : /// updating the CFG.
214 : void RemoveDeadBlock(MachineBasicBlock *MBB);
215 :
216 : /// Hoist common instruction sequences at the start of basic blocks to their
217 : /// common predecessor.
218 : bool HoistCommonCode(MachineFunction &MF);
219 :
220 : /// If the successors of MBB has common instruction sequence at the start of
221 : /// the function, move the instructions before MBB terminator if it's legal.
222 : bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB);
223 : };
224 :
225 : } // end namespace llvm
226 :
227 : #endif // LLVM_LIB_CODEGEN_BRANCHFOLDING_H
|
