BranchFolding.h revision 223017 
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_CODEGEN_BRANCHFOLDING_HPP
11#define LLVM_CODEGEN_BRANCHFOLDING_HPP
12
13#include "llvm/CodeGen/MachineBasicBlock.h"
14#include <vector>
15
16namespace llvm {
17  class MachineFunction;
18  class MachineModuleInfo;
19  class RegScavenger;
20  class TargetInstrInfo;
21  class TargetRegisterInfo;
22
23  class BranchFolder {
24  public:
25    explicit BranchFolder(bool defaultEnableTailMerge, bool CommonHoist);
26
27    bool OptimizeFunction(MachineFunction &MF,
28                          const TargetInstrInfo *tii,
29                          const TargetRegisterInfo *tri,
30                          MachineModuleInfo *mmi);
31  private:
32    class MergePotentialsElt {
33      unsigned Hash;
34      MachineBasicBlock *Block;
35    public:
36      MergePotentialsElt(unsigned h, MachineBasicBlock *b)
37        : Hash(h), Block(b) {}
38
39      unsigned getHash() const { return Hash; }
40      MachineBasicBlock *getBlock() const { return Block; }
41
42      void setBlock(MachineBasicBlock *MBB) {
43        Block = MBB;
44      }
45
46      bool operator<(const MergePotentialsElt &) const;
47    };
48    typedef std::vector<MergePotentialsElt>::iterator MPIterator;
49    std::vector<MergePotentialsElt> MergePotentials;
50
51    class SameTailElt {
52      MPIterator MPIter;
53      MachineBasicBlock::iterator TailStartPos;
54    public:
55      SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp)
56        : MPIter(mp), TailStartPos(tsp) {}
57
58      MPIterator getMPIter() const {
59        return MPIter;
60      }
61      MergePotentialsElt &getMergePotentialsElt() const {
62        return *getMPIter();
63      }
64      MachineBasicBlock::iterator getTailStartPos() const {
65        return TailStartPos;
66      }
67      unsigned getHash() const {
68        return getMergePotentialsElt().getHash();
69      }
70      MachineBasicBlock *getBlock() const {
71        return getMergePotentialsElt().getBlock();
72      }
73      bool tailIsWholeBlock() const {
74        return TailStartPos == getBlock()->begin();
75      }
76
77      void setBlock(MachineBasicBlock *MBB) {
78        getMergePotentialsElt().setBlock(MBB);
79      }
80      void setTailStartPos(MachineBasicBlock::iterator Pos) {
81        TailStartPos = Pos;
82      }
83    };
84    std::vector<SameTailElt> SameTails;
85
86    bool EnableTailMerge;
87    bool EnableHoistCommonCode;
88    const TargetInstrInfo *TII;
89    const TargetRegisterInfo *TRI;
90    MachineModuleInfo *MMI;
91    RegScavenger *RS;
92
93    bool TailMergeBlocks(MachineFunction &MF);
94    bool TryTailMergeBlocks(MachineBasicBlock* SuccBB,
95                       MachineBasicBlock* PredBB);
96    void ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
97                                 MachineBasicBlock *NewDest);
98    MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB,
99                                  MachineBasicBlock::iterator BBI1);
100    unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength,
101                              MachineBasicBlock *SuccBB,
102                              MachineBasicBlock *PredBB);
103    void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock* SuccBB,
104                                                MachineBasicBlock* PredBB);
105    bool CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
106                                   unsigned maxCommonTailLength,
107                                   unsigned &commonTailIndex);
108
109    bool OptimizeBranches(MachineFunction &MF);
110    bool OptimizeBlock(MachineBasicBlock *MBB);
111    void RemoveDeadBlock(MachineBasicBlock *MBB);
112    bool OptimizeImpDefsBlock(MachineBasicBlock *MBB);
113
114    bool HoistCommonCode(MachineFunction &MF);
115    bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB);
116  };
117}
118
119#endif /* LLVM_CODEGEN_BRANCHFOLDING_HPP */
120