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 RegScavenger;
24   class TargetInstrInfo;
25   class TargetRegisterInfo;
26 
27   class LLVM_LIBRARY_VISIBILITY BranchFolder {
28   public:
29     explicit BranchFolder(bool defaultEnableTailMerge, bool CommonHoist,
30                           const MachineBlockFrequencyInfo &MBFI,
31                           const MachineBranchProbabilityInfo &MBPI);
32 
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:
MergePotentialsElt(unsigned h,MachineBasicBlock * b)42       MergePotentialsElt(unsigned h, MachineBasicBlock *b)
43         : Hash(h), Block(b) {}
44 
getHash()45       unsigned getHash() const { return Hash; }
getBlock()46       MachineBasicBlock *getBlock() const { return Block; }
47 
setBlock(MachineBasicBlock * MBB)48       void setBlock(MachineBasicBlock *MBB) {
49         Block = MBB;
50       }
51 
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;
57     DenseMap<const MachineBasicBlock *, int> FuncletMembership;
58 
59     class SameTailElt {
60       MPIterator MPIter;
61       MachineBasicBlock::iterator TailStartPos;
62     public:
SameTailElt(MPIterator mp,MachineBasicBlock::iterator tsp)63       SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp)
64         : MPIter(mp), TailStartPos(tsp) {}
65 
getMPIter()66       MPIterator getMPIter() const {
67         return MPIter;
68       }
getMergePotentialsElt()69       MergePotentialsElt &getMergePotentialsElt() const {
70         return *getMPIter();
71       }
getTailStartPos()72       MachineBasicBlock::iterator getTailStartPos() const {
73         return TailStartPos;
74       }
getHash()75       unsigned getHash() const {
76         return getMergePotentialsElt().getHash();
77       }
getBlock()78       MachineBasicBlock *getBlock() const {
79         return getMergePotentialsElt().getBlock();
80       }
tailIsWholeBlock()81       bool tailIsWholeBlock() const {
82         return TailStartPos == getBlock()->begin();
83       }
84 
setBlock(MachineBasicBlock * MBB)85       void setBlock(MachineBasicBlock *MBB) {
86         getMergePotentialsElt().setBlock(MBB);
87       }
setTailStartPos(MachineBasicBlock::iterator Pos)88       void setTailStartPos(MachineBasicBlock::iterator Pos) {
89         TailStartPos = Pos;
90       }
91     };
92     std::vector<SameTailElt> SameTails;
93 
94     bool EnableTailMerge;
95     bool EnableHoistCommonCode;
96     const TargetInstrInfo *TII;
97     const TargetRegisterInfo *TRI;
98     MachineModuleInfo *MMI;
99     RegScavenger *RS;
100 
101     /// \brief This class keeps track of branch frequencies of newly created
102     /// blocks and tail-merged blocks.
103     class MBFIWrapper {
104     public:
MBFIWrapper(const MachineBlockFrequencyInfo & I)105       MBFIWrapper(const MachineBlockFrequencyInfo &I) : MBFI(I) {}
106       BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const;
107       void setBlockFreq(const MachineBasicBlock *MBB, BlockFrequency F);
108 
109     private:
110       const MachineBlockFrequencyInfo &MBFI;
111       DenseMap<const MachineBasicBlock *, BlockFrequency> MergedBBFreq;
112     };
113 
114     MBFIWrapper MBBFreqInfo;
115     const MachineBranchProbabilityInfo &MBPI;
116 
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);
137 
138     bool OptimizeBranches(MachineFunction &MF);
139     bool OptimizeBlock(MachineBasicBlock *MBB);
140     void RemoveDeadBlock(MachineBasicBlock *MBB);
141     bool OptimizeImpDefsBlock(MachineBasicBlock *MBB);
142 
143     bool HoistCommonCode(MachineFunction &MF);
144     bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB);
145   };
146 }
147 
148 #endif /* LLVM_CODEGEN_BRANCHFOLDING_HPP */
149