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