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 
18 namespace llvm {
19   class MachineBlockFrequencyInfo;
20   class MachineBranchProbabilityInfo;
21   class MachineFunction;
22   class MachineModuleInfo;
23   class MachineLoopInfo;
24   class RegScavenger;
25   class TargetInstrInfo;
26   class TargetRegisterInfo;
27 
28   class LLVM_LIBRARY_VISIBILITY BranchFolder {
29   public:
30     class MBFIWrapper;
31 
32     explicit BranchFolder(bool defaultEnableTailMerge, bool CommonHoist,
33                           MBFIWrapper &MBFI,
34                           const MachineBranchProbabilityInfo &MBPI);
35 
36     bool OptimizeFunction(MachineFunction &MF, const TargetInstrInfo *tii,
37                           const TargetRegisterInfo *tri, MachineModuleInfo *mmi,
38                           MachineLoopInfo *mli = nullptr,
39                           bool AfterPlacement = false);
40 
41   private:
42     class MergePotentialsElt {
43       unsigned Hash;
44       MachineBasicBlock *Block;
45     public:
46       MergePotentialsElt(unsigned h, MachineBasicBlock *b)
47         : Hash(h), Block(b) {}
48 
49       unsigned getHash() const { return Hash; }
50       MachineBasicBlock *getBlock() const { return Block; }
51 
52       void setBlock(MachineBasicBlock *MBB) {
53         Block = MBB;
54       }
55 
56       bool operator<(const MergePotentialsElt &) const;
57     };
58     typedef std::vector<MergePotentialsElt>::iterator MPIterator;
59     std::vector<MergePotentialsElt> MergePotentials;
60     SmallPtrSet<const MachineBasicBlock*, 2> TriedMerging;
61     DenseMap<const MachineBasicBlock *, int> FuncletMembership;
62 
63     class SameTailElt {
64       MPIterator MPIter;
65       MachineBasicBlock::iterator TailStartPos;
66     public:
67       SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp)
68         : MPIter(mp), TailStartPos(tsp) {}
69 
70       MPIterator getMPIter() const {
71         return MPIter;
72       }
73       MergePotentialsElt &getMergePotentialsElt() const {
74         return *getMPIter();
75       }
76       MachineBasicBlock::iterator getTailStartPos() const {
77         return TailStartPos;
78       }
79       unsigned getHash() const {
80         return getMergePotentialsElt().getHash();
81       }
82       MachineBasicBlock *getBlock() const {
83         return getMergePotentialsElt().getBlock();
84       }
85       bool tailIsWholeBlock() const {
86         return TailStartPos == getBlock()->begin();
87       }
88 
89       void setBlock(MachineBasicBlock *MBB) {
90         getMergePotentialsElt().setBlock(MBB);
91       }
92       void setTailStartPos(MachineBasicBlock::iterator Pos) {
93         TailStartPos = Pos;
94       }
95     };
96     std::vector<SameTailElt> SameTails;
97 
98     bool AfterBlockPlacement;
99     bool EnableTailMerge;
100     bool EnableHoistCommonCode;
101     const TargetInstrInfo *TII;
102     const TargetRegisterInfo *TRI;
103     MachineModuleInfo *MMI;
104     MachineLoopInfo *MLI;
105     RegScavenger *RS;
106 
107   public:
108     /// \brief This class keeps track of branch frequencies of newly created
109     /// blocks and tail-merged blocks.
110     class MBFIWrapper {
111     public:
112       MBFIWrapper(const MachineBlockFrequencyInfo &I) : MBFI(I) {}
113       BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const;
114       void setBlockFreq(const MachineBasicBlock *MBB, BlockFrequency F);
115       raw_ostream &printBlockFreq(raw_ostream &OS,
116                                   const MachineBasicBlock *MBB) const;
117       raw_ostream &printBlockFreq(raw_ostream &OS,
118                                   const BlockFrequency Freq) const;
119 
120     private:
121       const MachineBlockFrequencyInfo &MBFI;
122       DenseMap<const MachineBasicBlock *, BlockFrequency> MergedBBFreq;
123     };
124 
125   private:
126     MBFIWrapper &MBBFreqInfo;
127     const MachineBranchProbabilityInfo &MBPI;
128 
129     bool TailMergeBlocks(MachineFunction &MF);
130     bool TryTailMergeBlocks(MachineBasicBlock* SuccBB,
131                        MachineBasicBlock* PredBB);
132     void setCommonTailEdgeWeights(MachineBasicBlock &TailMBB);
133     void MaintainLiveIns(MachineBasicBlock *CurMBB,
134                          MachineBasicBlock *NewMBB);
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);
149 
150     bool OptimizeBranches(MachineFunction &MF);
151     bool OptimizeBlock(MachineBasicBlock *MBB);
152     void RemoveDeadBlock(MachineBasicBlock *MBB);
153     bool OptimizeImpDefsBlock(MachineBasicBlock *MBB);
154 
155     bool HoistCommonCode(MachineFunction &MF);
156     bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB);
157   };
158 }
159 
160 #endif /* LLVM_CODEGEN_BRANCHFOLDING_HPP */
161