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 //===----------------------------------------------------------------------===//
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"
16 #include <vector>
18 namespace llvm {
19 class MachineBlockFrequencyInfo;
20 class MachineBranchProbabilityInfo;
21 class MachineFunction;
22 class MachineModuleInfo;
23 class RegScavenger;
24 class TargetInstrInfo;
25 class TargetRegisterInfo;
27 class BranchFolder {
28 public:
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);
37 private:
38 class MergePotentialsElt {
39 unsigned Hash;
40 MachineBasicBlock *Block;
41 public:
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) {
49 Block = MBB;
50 }
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;
58 class SameTailElt {
59 MPIterator MPIter;
60 MachineBasicBlock::iterator TailStartPos;
61 public:
62 SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp)
63 : MPIter(mp), TailStartPos(tsp) {}
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 }
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;
93 bool EnableTailMerge;
94 bool EnableHoistCommonCode;
95 const TargetInstrInfo *TII;
96 const TargetRegisterInfo *TRI;
97 MachineModuleInfo *MMI;
98 RegScavenger *RS;
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);
108 private:
109 const MachineBlockFrequencyInfo &MBFI;
110 DenseMap<const MachineBasicBlock *, BlockFrequency> MergedBBFreq;
111 };
113 MBFIWrapper MBBFreqInfo;
114 const MachineBranchProbabilityInfo &MBPI;
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);
137 bool OptimizeBranches(MachineFunction &MF);
138 bool OptimizeBlock(MachineBasicBlock *MBB);
139 void RemoveDeadBlock(MachineBasicBlock *MBB);
140 bool OptimizeImpDefsBlock(MachineBasicBlock *MBB);
142 bool HoistCommonCode(MachineFunction &MF);
143 bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB);
144 };
145 }
147 #endif /* LLVM_CODEGEN_BRANCHFOLDING_HPP */