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