BranchFolding.h revision 810ced7daebe78a8d84b94fac07e320a02cecb71 
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  template<typename T> class SmallVectorImpl;
23
24  class BranchFolder {
25  public:
26    explicit BranchFolder(bool defaultEnableTailMerge);
27
28    bool OptimizeFunction(MachineFunction &MF,
29                          const TargetInstrInfo *tii,
30                          const TargetRegisterInfo *tri,
31                          MachineModuleInfo *mmi);
32  private:
33    class MergePotentialsElt {
34      unsigned Hash;
35      MachineBasicBlock *Block;
36    public:
37      MergePotentialsElt(unsigned h, MachineBasicBlock *b)
38        : Hash(h), Block(b) {}
39
40      unsigned getHash() const { return Hash; }
41      MachineBasicBlock *getBlock() const { return Block; }
42
43      void setBlock(MachineBasicBlock *MBB) {
44        Block = MBB;
45      }
46
47      bool operator<(const MergePotentialsElt &) const;
48    };
49    typedef std::vector<MergePotentialsElt>::iterator MPIterator;
50    std::vector<MergePotentialsElt> MergePotentials;
51
52    class SameTailElt {
53      MPIterator MPIter;
54      MachineBasicBlock::iterator TailStartPos;
55    public:
56      SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp)
57        : MPIter(mp), TailStartPos(tsp) {}
58
59      MPIterator getMPIter() const {
60        return MPIter;
61      }
62      MergePotentialsElt &getMergePotentialsElt() const {
63        return *getMPIter();
64      }
65      MachineBasicBlock::iterator getTailStartPos() const {
66        return TailStartPos;
67      }
68      unsigned getHash() const {
69        return getMergePotentialsElt().getHash();
70      }
71      MachineBasicBlock *getBlock() const {
72        return getMergePotentialsElt().getBlock();
73      }
74      bool tailIsWholeBlock() const {
75        return TailStartPos == getBlock()->begin();
76      }
77
78      void setBlock(MachineBasicBlock *MBB) {
79        getMergePotentialsElt().setBlock(MBB);
80      }
81      void setTailStartPos(MachineBasicBlock::iterator Pos) {
82        TailStartPos = Pos;
83      }
84    };
85    std::vector<SameTailElt> SameTails;
86
87    bool EnableTailMerge;
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    unsigned CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
106                                       unsigned maxCommonTailLength);
107
108    bool OptimizeBranches(MachineFunction &MF);
109    bool OptimizeBlock(MachineBasicBlock *MBB);
110    void RemoveDeadBlock(MachineBasicBlock *MBB);
111    bool OptimizeImpDefsBlock(MachineBasicBlock *MBB);
112  };
113}
114
115#endif /* LLVM_CODEGEN_BRANCHFOLDING_HPP */
116