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/MachineBasicBlock.h"
15 #include "llvm/Support/BlockFrequency.h"
19 class MachineBlockFrequencyInfo;
20 class MachineBranchProbabilityInfo;
21 class MachineFunction;
22 class MachineModuleInfo;
24 class TargetInstrInfo;
25 class TargetRegisterInfo;
27 class LLVM_LIBRARY_VISIBILITY BranchFolder {
29 explicit BranchFolder(bool defaultEnableTailMerge, bool CommonHoist,
30 const MachineBlockFrequencyInfo &MBFI,
31 const MachineBranchProbabilityInfo &MBPI);
33 bool OptimizeFunction(MachineFunction &MF,
34 const TargetInstrInfo *tii,
35 const TargetRegisterInfo *tri,
36 MachineModuleInfo *mmi);
38 class MergePotentialsElt {
40 MachineBasicBlock *Block;
42 MergePotentialsElt(unsigned h, MachineBasicBlock *b)
43 : Hash(h), Block(b) {}
45 unsigned getHash() const { return Hash; }
46 MachineBasicBlock *getBlock() const { return Block; }
48 void setBlock(MachineBasicBlock *MBB) {
52 bool operator<(const MergePotentialsElt &) const;
54 typedef std::vector<MergePotentialsElt>::iterator MPIterator;
55 std::vector<MergePotentialsElt> MergePotentials;
56 SmallPtrSet<const MachineBasicBlock*, 2> TriedMerging;
57 DenseMap<const MachineBasicBlock *, int> FuncletMembership;
61 MachineBasicBlock::iterator TailStartPos;
63 SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp)
64 : MPIter(mp), TailStartPos(tsp) {}
66 MPIterator getMPIter() const {
69 MergePotentialsElt &getMergePotentialsElt() const {
72 MachineBasicBlock::iterator getTailStartPos() const {
75 unsigned getHash() const {
76 return getMergePotentialsElt().getHash();
78 MachineBasicBlock *getBlock() const {
79 return getMergePotentialsElt().getBlock();
81 bool tailIsWholeBlock() const {
82 return TailStartPos == getBlock()->begin();
85 void setBlock(MachineBasicBlock *MBB) {
86 getMergePotentialsElt().setBlock(MBB);
88 void setTailStartPos(MachineBasicBlock::iterator Pos) {
92 std::vector<SameTailElt> SameTails;
95 bool EnableHoistCommonCode;
96 const TargetInstrInfo *TII;
97 const TargetRegisterInfo *TRI;
98 MachineModuleInfo *MMI;
101 /// \brief This class keeps track of branch frequencies of newly created
102 /// blocks and tail-merged blocks.
105 MBFIWrapper(const MachineBlockFrequencyInfo &I) : MBFI(I) {}
106 BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const;
107 void setBlockFreq(const MachineBasicBlock *MBB, BlockFrequency F);
110 const MachineBlockFrequencyInfo &MBFI;
111 DenseMap<const MachineBasicBlock *, BlockFrequency> MergedBBFreq;
114 MBFIWrapper MBBFreqInfo;
115 const MachineBranchProbabilityInfo &MBPI;
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);
138 bool OptimizeBranches(MachineFunction &MF);
139 bool OptimizeBlock(MachineBasicBlock *MBB);
140 void RemoveDeadBlock(MachineBasicBlock *MBB);
141 bool OptimizeImpDefsBlock(MachineBasicBlock *MBB);
143 bool HoistCommonCode(MachineFunction &MF);
144 bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB);
148 #endif /* LLVM_CODEGEN_BRANCHFOLDING_HPP */