1 //===-- BranchFolding.h - Fold machine code branch instructions -*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #ifndef LLVM_LIB_CODEGEN_BRANCHFOLDING_H
11 #define LLVM_LIB_CODEGEN_BRANCHFOLDING_H
13 #include "llvm/ADT/SmallPtrSet.h"
14 #include "llvm/CodeGen/LivePhysRegs.h"
15 #include "llvm/CodeGen/MachineBasicBlock.h"
16 #include "llvm/Support/BlockFrequency.h"
20 class MachineBlockFrequencyInfo;
21 class MachineBranchProbabilityInfo;
22 class MachineFunction;
23 class MachineModuleInfo;
24 class MachineLoopInfo;
25 class TargetInstrInfo;
26 class TargetRegisterInfo;
28 class LLVM_LIBRARY_VISIBILITY BranchFolder {
32 explicit BranchFolder(bool defaultEnableTailMerge, bool CommonHoist,
34 const MachineBranchProbabilityInfo &MBPI);
36 bool OptimizeFunction(MachineFunction &MF, const TargetInstrInfo *tii,
37 const TargetRegisterInfo *tri, MachineModuleInfo *mmi,
38 MachineLoopInfo *mli = nullptr,
39 bool AfterPlacement = false);
42 class MergePotentialsElt {
44 MachineBasicBlock *Block;
46 MergePotentialsElt(unsigned h, MachineBasicBlock *b)
47 : Hash(h), Block(b) {}
49 unsigned getHash() const { return Hash; }
50 MachineBasicBlock *getBlock() const { return Block; }
52 void setBlock(MachineBasicBlock *MBB) {
56 bool operator<(const MergePotentialsElt &) const;
58 typedef std::vector<MergePotentialsElt>::iterator MPIterator;
59 std::vector<MergePotentialsElt> MergePotentials;
60 SmallPtrSet<const MachineBasicBlock*, 2> TriedMerging;
61 DenseMap<const MachineBasicBlock *, int> FuncletMembership;
65 MachineBasicBlock::iterator TailStartPos;
67 SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp)
68 : MPIter(mp), TailStartPos(tsp) {}
70 MPIterator getMPIter() const {
73 MergePotentialsElt &getMergePotentialsElt() const {
76 MachineBasicBlock::iterator getTailStartPos() const {
79 unsigned getHash() const {
80 return getMergePotentialsElt().getHash();
82 MachineBasicBlock *getBlock() const {
83 return getMergePotentialsElt().getBlock();
85 bool tailIsWholeBlock() const {
86 return TailStartPos == getBlock()->begin();
89 void setBlock(MachineBasicBlock *MBB) {
90 getMergePotentialsElt().setBlock(MBB);
92 void setTailStartPos(MachineBasicBlock::iterator Pos) {
96 std::vector<SameTailElt> SameTails;
98 bool AfterBlockPlacement;
100 bool EnableHoistCommonCode;
102 const TargetInstrInfo *TII;
103 const TargetRegisterInfo *TRI;
104 MachineModuleInfo *MMI;
105 MachineLoopInfo *MLI;
106 LivePhysRegs LiveRegs;
109 /// \brief This class keeps track of branch frequencies of newly created
110 /// blocks and tail-merged blocks.
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;
122 const MachineBlockFrequencyInfo &MBFI;
123 DenseMap<const MachineBasicBlock *, BlockFrequency> MergedBBFreq;
127 MBFIWrapper &MBBFreqInfo;
128 const MachineBranchProbabilityInfo &MBPI;
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);
150 bool OptimizeBranches(MachineFunction &MF);
151 bool OptimizeBlock(MachineBasicBlock *MBB);
152 void RemoveDeadBlock(MachineBasicBlock *MBB);
153 bool OptimizeImpDefsBlock(MachineBasicBlock *MBB);
155 bool HoistCommonCode(MachineFunction &MF);
156 bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB);
160 #endif /* LLVM_CODEGEN_BRANCHFOLDING_HPP */