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