BranchFolding.h revision 41cdc16e7301c91d2460aa14412f592695b0d4ed 
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    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}
115
116#endif /* LLVM_CODEGEN_BRANCHFOLDING_HPP */
117