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/MachineBasicBlock.h" 15 #include "llvm/Support/BlockFrequency.h" 16 #include <vector> 17 18 namespace llvm { 19 class MachineBlockFrequencyInfo; 20 class MachineBranchProbabilityInfo; 21 class MachineFunction; 22 class MachineModuleInfo; 23 class RegScavenger; 24 class TargetInstrInfo; 25 class TargetRegisterInfo; 26 27 class LLVM_LIBRARY_VISIBILITY BranchFolder { 28 public: 29 explicit BranchFolder(bool defaultEnableTailMerge, bool CommonHoist, 30 const MachineBlockFrequencyInfo &MBFI, 31 const MachineBranchProbabilityInfo &MBPI); 32 33 bool OptimizeFunction(MachineFunction &MF, 34 const TargetInstrInfo *tii, 35 const TargetRegisterInfo *tri, 36 MachineModuleInfo *mmi); 37 private: 38 class MergePotentialsElt { 39 unsigned Hash; 40 MachineBasicBlock *Block; 41 public: MergePotentialsElt(unsigned h,MachineBasicBlock * b)42 MergePotentialsElt(unsigned h, MachineBasicBlock *b) 43 : Hash(h), Block(b) {} 44 getHash()45 unsigned getHash() const { return Hash; } getBlock()46 MachineBasicBlock *getBlock() const { return Block; } 47 setBlock(MachineBasicBlock * MBB)48 void setBlock(MachineBasicBlock *MBB) { 49 Block = MBB; 50 } 51 52 bool operator<(const MergePotentialsElt &) const; 53 }; 54 typedef std::vector<MergePotentialsElt>::iterator MPIterator; 55 std::vector<MergePotentialsElt> MergePotentials; 56 SmallPtrSet<const MachineBasicBlock*, 2> TriedMerging; 57 DenseMap<const MachineBasicBlock *, int> FuncletMembership; 58 59 class SameTailElt { 60 MPIterator MPIter; 61 MachineBasicBlock::iterator TailStartPos; 62 public: SameTailElt(MPIterator mp,MachineBasicBlock::iterator tsp)63 SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp) 64 : MPIter(mp), TailStartPos(tsp) {} 65 getMPIter()66 MPIterator getMPIter() const { 67 return MPIter; 68 } getMergePotentialsElt()69 MergePotentialsElt &getMergePotentialsElt() const { 70 return *getMPIter(); 71 } getTailStartPos()72 MachineBasicBlock::iterator getTailStartPos() const { 73 return TailStartPos; 74 } getHash()75 unsigned getHash() const { 76 return getMergePotentialsElt().getHash(); 77 } getBlock()78 MachineBasicBlock *getBlock() const { 79 return getMergePotentialsElt().getBlock(); 80 } tailIsWholeBlock()81 bool tailIsWholeBlock() const { 82 return TailStartPos == getBlock()->begin(); 83 } 84 setBlock(MachineBasicBlock * MBB)85 void setBlock(MachineBasicBlock *MBB) { 86 getMergePotentialsElt().setBlock(MBB); 87 } setTailStartPos(MachineBasicBlock::iterator Pos)88 void setTailStartPos(MachineBasicBlock::iterator Pos) { 89 TailStartPos = Pos; 90 } 91 }; 92 std::vector<SameTailElt> SameTails; 93 94 bool EnableTailMerge; 95 bool EnableHoistCommonCode; 96 const TargetInstrInfo *TII; 97 const TargetRegisterInfo *TRI; 98 MachineModuleInfo *MMI; 99 RegScavenger *RS; 100 101 /// \brief This class keeps track of branch frequencies of newly created 102 /// blocks and tail-merged blocks. 103 class MBFIWrapper { 104 public: MBFIWrapper(const MachineBlockFrequencyInfo & I)105 MBFIWrapper(const MachineBlockFrequencyInfo &I) : MBFI(I) {} 106 BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const; 107 void setBlockFreq(const MachineBasicBlock *MBB, BlockFrequency F); 108 109 private: 110 const MachineBlockFrequencyInfo &MBFI; 111 DenseMap<const MachineBasicBlock *, BlockFrequency> MergedBBFreq; 112 }; 113 114 MBFIWrapper MBBFreqInfo; 115 const MachineBranchProbabilityInfo &MBPI; 116 117 bool TailMergeBlocks(MachineFunction &MF); 118 bool TryTailMergeBlocks(MachineBasicBlock* SuccBB, 119 MachineBasicBlock* PredBB); 120 void setCommonTailEdgeWeights(MachineBasicBlock &TailMBB); 121 void MaintainLiveIns(MachineBasicBlock *CurMBB, 122 MachineBasicBlock *NewMBB); 123 void ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst, 124 MachineBasicBlock *NewDest); 125 MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB, 126 MachineBasicBlock::iterator BBI1, 127 const BasicBlock *BB); 128 unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength, 129 MachineBasicBlock *SuccBB, 130 MachineBasicBlock *PredBB); 131 void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock* SuccBB, 132 MachineBasicBlock* PredBB); 133 bool CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB, 134 MachineBasicBlock *SuccBB, 135 unsigned maxCommonTailLength, 136 unsigned &commonTailIndex); 137 138 bool OptimizeBranches(MachineFunction &MF); 139 bool OptimizeBlock(MachineBasicBlock *MBB); 140 void RemoveDeadBlock(MachineBasicBlock *MBB); 141 bool OptimizeImpDefsBlock(MachineBasicBlock *MBB); 142 143 bool HoistCommonCode(MachineFunction &MF); 144 bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB); 145 }; 146 } 147 148 #endif /* LLVM_CODEGEN_BRANCHFOLDING_HPP */ 149