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_CODEGEN_BRANCHFOLDING_HPP 11 #define LLVM_CODEGEN_BRANCHFOLDING_HPP 12 13 #include "llvm/ADT/SmallPtrSet.h" 14 #include "llvm/CodeGen/MachineBasicBlock.h" 15 #include <vector> 16 17 namespace llvm { 18 class MachineFunction; 19 class MachineModuleInfo; 20 class RegScavenger; 21 class TargetInstrInfo; 22 class TargetRegisterInfo; 23 24 class BranchFolder { 25 public: 26 explicit BranchFolder(bool defaultEnableTailMerge, bool CommonHoist); 27 28 bool OptimizeFunction(MachineFunction &MF, 29 const TargetInstrInfo *tii, 30 const TargetRegisterInfo *tri, 31 MachineModuleInfo *mmi); 32 private: 33 class MergePotentialsElt { 34 unsigned Hash; 35 MachineBasicBlock *Block; 36 public: MergePotentialsElt(unsigned h,MachineBasicBlock * b)37 MergePotentialsElt(unsigned h, MachineBasicBlock *b) 38 : Hash(h), Block(b) {} 39 getHash()40 unsigned getHash() const { return Hash; } getBlock()41 MachineBasicBlock *getBlock() const { return Block; } 42 setBlock(MachineBasicBlock * MBB)43 void setBlock(MachineBasicBlock *MBB) { 44 Block = MBB; 45 } 46 47 bool operator<(const MergePotentialsElt &) const; 48 }; 49 typedef std::vector<MergePotentialsElt>::iterator MPIterator; 50 std::vector<MergePotentialsElt> MergePotentials; 51 SmallPtrSet<const MachineBasicBlock*, 2> TriedMerging; 52 53 class SameTailElt { 54 MPIterator MPIter; 55 MachineBasicBlock::iterator TailStartPos; 56 public: SameTailElt(MPIterator mp,MachineBasicBlock::iterator tsp)57 SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp) 58 : MPIter(mp), TailStartPos(tsp) {} 59 getMPIter()60 MPIterator getMPIter() const { 61 return MPIter; 62 } getMergePotentialsElt()63 MergePotentialsElt &getMergePotentialsElt() const { 64 return *getMPIter(); 65 } getTailStartPos()66 MachineBasicBlock::iterator getTailStartPos() const { 67 return TailStartPos; 68 } getHash()69 unsigned getHash() const { 70 return getMergePotentialsElt().getHash(); 71 } getBlock()72 MachineBasicBlock *getBlock() const { 73 return getMergePotentialsElt().getBlock(); 74 } tailIsWholeBlock()75 bool tailIsWholeBlock() const { 76 return TailStartPos == getBlock()->begin(); 77 } 78 setBlock(MachineBasicBlock * MBB)79 void setBlock(MachineBasicBlock *MBB) { 80 getMergePotentialsElt().setBlock(MBB); 81 } setTailStartPos(MachineBasicBlock::iterator Pos)82 void setTailStartPos(MachineBasicBlock::iterator Pos) { 83 TailStartPos = Pos; 84 } 85 }; 86 std::vector<SameTailElt> SameTails; 87 88 bool EnableTailMerge; 89 bool EnableHoistCommonCode; 90 const TargetInstrInfo *TII; 91 const TargetRegisterInfo *TRI; 92 MachineModuleInfo *MMI; 93 RegScavenger *RS; 94 95 bool TailMergeBlocks(MachineFunction &MF); 96 bool TryTailMergeBlocks(MachineBasicBlock* SuccBB, 97 MachineBasicBlock* PredBB); 98 void MaintainLiveIns(MachineBasicBlock *CurMBB, 99 MachineBasicBlock *NewMBB); 100 void ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst, 101 MachineBasicBlock *NewDest); 102 MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB, 103 MachineBasicBlock::iterator BBI1, 104 const BasicBlock *BB); 105 unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength, 106 MachineBasicBlock *SuccBB, 107 MachineBasicBlock *PredBB); 108 void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock* SuccBB, 109 MachineBasicBlock* PredBB); 110 bool CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB, 111 MachineBasicBlock *SuccBB, 112 unsigned maxCommonTailLength, 113 unsigned &commonTailIndex); 114 115 bool OptimizeBranches(MachineFunction &MF); 116 bool OptimizeBlock(MachineBasicBlock *MBB); 117 void RemoveDeadBlock(MachineBasicBlock *MBB); 118 bool OptimizeImpDefsBlock(MachineBasicBlock *MBB); 119 120 bool HoistCommonCode(MachineFunction &MF); 121 bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB); 122 }; 123 } 124 125 #endif /* LLVM_CODEGEN_BRANCHFOLDING_HPP */ 126