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