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