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