1 //===-- BranchFolding.h - Fold machine code branch instructions -*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #ifndef LLVM_LIB_CODEGEN_BRANCHFOLDING_H 11 #define LLVM_LIB_CODEGEN_BRANCHFOLDING_H 12 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 <vector> 18 19 namespace llvm { 20 class MachineBlockFrequencyInfo; 21 class MachineBranchProbabilityInfo; 22 class MachineFunction; 23 class MachineModuleInfo; 24 class MachineLoopInfo; 25 class TargetInstrInfo; 26 class TargetRegisterInfo; 27 28 class LLVM_LIBRARY_VISIBILITY BranchFolder { 29 public: 30 class MBFIWrapper; 31 32 explicit BranchFolder(bool defaultEnableTailMerge, bool CommonHoist, 33 MBFIWrapper &MBFI, 34 const MachineBranchProbabilityInfo &MBPI); 35 36 bool OptimizeFunction(MachineFunction &MF, const TargetInstrInfo *tii, 37 const TargetRegisterInfo *tri, MachineModuleInfo *mmi, 38 MachineLoopInfo *mli = nullptr, 39 bool AfterPlacement = false); 40 41 private: 42 class MergePotentialsElt { 43 unsigned Hash; 44 MachineBasicBlock *Block; 45 public: MergePotentialsElt(unsigned h,MachineBasicBlock * b)46 MergePotentialsElt(unsigned h, MachineBasicBlock *b) 47 : Hash(h), Block(b) {} 48 getHash()49 unsigned getHash() const { return Hash; } getBlock()50 MachineBasicBlock *getBlock() const { return Block; } 51 setBlock(MachineBasicBlock * MBB)52 void setBlock(MachineBasicBlock *MBB) { 53 Block = MBB; 54 } 55 56 bool operator<(const MergePotentialsElt &) const; 57 }; 58 typedef std::vector<MergePotentialsElt>::iterator MPIterator; 59 std::vector<MergePotentialsElt> MergePotentials; 60 SmallPtrSet<const MachineBasicBlock*, 2> TriedMerging; 61 DenseMap<const MachineBasicBlock *, int> FuncletMembership; 62 63 class SameTailElt { 64 MPIterator MPIter; 65 MachineBasicBlock::iterator TailStartPos; 66 public: SameTailElt(MPIterator mp,MachineBasicBlock::iterator tsp)67 SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp) 68 : MPIter(mp), TailStartPos(tsp) {} 69 getMPIter()70 MPIterator getMPIter() const { 71 return MPIter; 72 } getMergePotentialsElt()73 MergePotentialsElt &getMergePotentialsElt() const { 74 return *getMPIter(); 75 } getTailStartPos()76 MachineBasicBlock::iterator getTailStartPos() const { 77 return TailStartPos; 78 } getHash()79 unsigned getHash() const { 80 return getMergePotentialsElt().getHash(); 81 } getBlock()82 MachineBasicBlock *getBlock() const { 83 return getMergePotentialsElt().getBlock(); 84 } tailIsWholeBlock()85 bool tailIsWholeBlock() const { 86 return TailStartPos == getBlock()->begin(); 87 } 88 setBlock(MachineBasicBlock * MBB)89 void setBlock(MachineBasicBlock *MBB) { 90 getMergePotentialsElt().setBlock(MBB); 91 } setTailStartPos(MachineBasicBlock::iterator Pos)92 void setTailStartPos(MachineBasicBlock::iterator Pos) { 93 TailStartPos = Pos; 94 } 95 }; 96 std::vector<SameTailElt> SameTails; 97 98 bool AfterBlockPlacement; 99 bool EnableTailMerge; 100 bool EnableHoistCommonCode; 101 bool UpdateLiveIns; 102 const TargetInstrInfo *TII; 103 const TargetRegisterInfo *TRI; 104 MachineModuleInfo *MMI; 105 MachineLoopInfo *MLI; 106 LivePhysRegs LiveRegs; 107 108 public: 109 /// \brief This class keeps track of branch frequencies of newly created 110 /// blocks and tail-merged blocks. 111 class MBFIWrapper { 112 public: MBFIWrapper(const MachineBlockFrequencyInfo & I)113 MBFIWrapper(const MachineBlockFrequencyInfo &I) : MBFI(I) {} 114 BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const; 115 void setBlockFreq(const MachineBasicBlock *MBB, BlockFrequency F); 116 raw_ostream &printBlockFreq(raw_ostream &OS, 117 const MachineBasicBlock *MBB) const; 118 raw_ostream &printBlockFreq(raw_ostream &OS, 119 const BlockFrequency Freq) const; 120 121 private: 122 const MachineBlockFrequencyInfo &MBFI; 123 DenseMap<const MachineBasicBlock *, BlockFrequency> MergedBBFreq; 124 }; 125 126 private: 127 MBFIWrapper &MBBFreqInfo; 128 const MachineBranchProbabilityInfo &MBPI; 129 130 bool TailMergeBlocks(MachineFunction &MF); 131 bool TryTailMergeBlocks(MachineBasicBlock* SuccBB, 132 MachineBasicBlock* PredBB); 133 void setCommonTailEdgeWeights(MachineBasicBlock &TailMBB); 134 void computeLiveIns(MachineBasicBlock &MBB); 135 void ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst, 136 MachineBasicBlock *NewDest); 137 MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB, 138 MachineBasicBlock::iterator BBI1, 139 const BasicBlock *BB); 140 unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength, 141 MachineBasicBlock *SuccBB, 142 MachineBasicBlock *PredBB); 143 void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock* SuccBB, 144 MachineBasicBlock* PredBB); 145 bool CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB, 146 MachineBasicBlock *SuccBB, 147 unsigned maxCommonTailLength, 148 unsigned &commonTailIndex); 149 150 bool OptimizeBranches(MachineFunction &MF); 151 bool OptimizeBlock(MachineBasicBlock *MBB); 152 void RemoveDeadBlock(MachineBasicBlock *MBB); 153 bool OptimizeImpDefsBlock(MachineBasicBlock *MBB); 154 155 bool HoistCommonCode(MachineFunction &MF); 156 bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB); 157 }; 158 } 159 160 #endif /* LLVM_CODEGEN_BRANCHFOLDING_HPP */ 161