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 18namespace 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 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: 42 MergePotentialsElt(unsigned h, MachineBasicBlock *b) 43 : Hash(h), Block(b) {} 44 45 unsigned getHash() const { return Hash; } 46 MachineBasicBlock *getBlock() const { return Block; } 47 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 58 class SameTailElt { 59 MPIterator MPIter; 60 MachineBasicBlock::iterator TailStartPos; 61 public: 62 SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp) 63 : MPIter(mp), TailStartPos(tsp) {} 64 65 MPIterator getMPIter() const { 66 return MPIter; 67 } 68 MergePotentialsElt &getMergePotentialsElt() const { 69 return *getMPIter(); 70 } 71 MachineBasicBlock::iterator getTailStartPos() const { 72 return TailStartPos; 73 } 74 unsigned getHash() const { 75 return getMergePotentialsElt().getHash(); 76 } 77 MachineBasicBlock *getBlock() const { 78 return getMergePotentialsElt().getBlock(); 79 } 80 bool tailIsWholeBlock() const { 81 return TailStartPos == getBlock()->begin(); 82 } 83 84 void setBlock(MachineBasicBlock *MBB) { 85 getMergePotentialsElt().setBlock(MBB); 86 } 87 void setTailStartPos(MachineBasicBlock::iterator Pos) { 88 TailStartPos = Pos; 89 } 90 }; 91 std::vector<SameTailElt> SameTails; 92 93 bool EnableTailMerge; 94 bool EnableHoistCommonCode; 95 const TargetInstrInfo *TII; 96 const TargetRegisterInfo *TRI; 97 MachineModuleInfo *MMI; 98 RegScavenger *RS; 99 100 /// \brief This class keeps track of branch frequencies of newly created 101 /// blocks and tail-merged blocks. 102 class MBFIWrapper { 103 public: 104 MBFIWrapper(const MachineBlockFrequencyInfo &I) : MBFI(I) {} 105 BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const; 106 void setBlockFreq(const MachineBasicBlock *MBB, BlockFrequency F); 107 108 private: 109 const MachineBlockFrequencyInfo &MBFI; 110 DenseMap<const MachineBasicBlock *, BlockFrequency> MergedBBFreq; 111 }; 112 113 MBFIWrapper MBBFreqInfo; 114 const MachineBranchProbabilityInfo &MBPI; 115 116 bool TailMergeBlocks(MachineFunction &MF); 117 bool TryTailMergeBlocks(MachineBasicBlock* SuccBB, 118 MachineBasicBlock* PredBB); 119 void setCommonTailEdgeWeights(MachineBasicBlock &TailMBB); 120 void MaintainLiveIns(MachineBasicBlock *CurMBB, 121 MachineBasicBlock *NewMBB); 122 void ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst, 123 MachineBasicBlock *NewDest); 124 MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB, 125 MachineBasicBlock::iterator BBI1, 126 const BasicBlock *BB); 127 unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength, 128 MachineBasicBlock *SuccBB, 129 MachineBasicBlock *PredBB); 130 void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock* SuccBB, 131 MachineBasicBlock* PredBB); 132 bool CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB, 133 MachineBasicBlock *SuccBB, 134 unsigned maxCommonTailLength, 135 unsigned &commonTailIndex); 136 137 bool OptimizeBranches(MachineFunction &MF); 138 bool OptimizeBlock(MachineBasicBlock *MBB); 139 void RemoveDeadBlock(MachineBasicBlock *MBB); 140 bool OptimizeImpDefsBlock(MachineBasicBlock *MBB); 141 142 bool HoistCommonCode(MachineFunction &MF); 143 bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB); 144 }; 145} 146 147#endif /* LLVM_CODEGEN_BRANCHFOLDING_HPP */ 148