llvm::SwitchInst
[oota-llvm.git] / lib / CodeGen / BranchFolding.h
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/ADT/SmallPtrSet.h"
14 #include "llvm/CodeGen/MachineBasicBlock.h"
15 #include <vector>
16
17 namespace llvm {
18   class MachineFunction;
19   class MachineModuleInfo;
20   class RegScavenger;
21   class TargetInstrInfo;
22   class TargetRegisterInfo;
23
24   class BranchFolder {
25   public:
26     explicit BranchFolder(bool defaultEnableTailMerge, bool CommonHoist);
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     SmallPtrSet<const MachineBasicBlock*, 2> TriedMerging;
52
53     class SameTailElt {
54       MPIterator MPIter;
55       MachineBasicBlock::iterator TailStartPos;
56     public:
57       SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp)
58         : MPIter(mp), TailStartPos(tsp) {}
59
60       MPIterator getMPIter() const {
61         return MPIter;
62       }
63       MergePotentialsElt &getMergePotentialsElt() const {
64         return *getMPIter();
65       }
66       MachineBasicBlock::iterator getTailStartPos() const {
67         return TailStartPos;
68       }
69       unsigned getHash() const {
70         return getMergePotentialsElt().getHash();
71       }
72       MachineBasicBlock *getBlock() const {
73         return getMergePotentialsElt().getBlock();
74       }
75       bool tailIsWholeBlock() const {
76         return TailStartPos == getBlock()->begin();
77       }
78
79       void setBlock(MachineBasicBlock *MBB) {
80         getMergePotentialsElt().setBlock(MBB);
81       }
82       void setTailStartPos(MachineBasicBlock::iterator Pos) {
83         TailStartPos = Pos;
84       }
85     };
86     std::vector<SameTailElt> SameTails;
87
88     bool EnableTailMerge;
89     bool EnableHoistCommonCode;
90     const TargetInstrInfo *TII;
91     const TargetRegisterInfo *TRI;
92     MachineModuleInfo *MMI;
93     RegScavenger *RS;
94
95     bool TailMergeBlocks(MachineFunction &MF);
96     bool TryTailMergeBlocks(MachineBasicBlock* SuccBB,
97                        MachineBasicBlock* PredBB);
98     void MaintainLiveIns(MachineBasicBlock *CurMBB,
99                          MachineBasicBlock *NewMBB);
100     void ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
101                                  MachineBasicBlock *NewDest);
102     MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB,
103                                   MachineBasicBlock::iterator BBI1);
104     unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength,
105                               MachineBasicBlock *SuccBB,
106                               MachineBasicBlock *PredBB);
107     void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock* SuccBB,
108                                                 MachineBasicBlock* PredBB);
109     bool CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
110                                    unsigned maxCommonTailLength,
111                                    unsigned &commonTailIndex);
112
113     bool OptimizeBranches(MachineFunction &MF);
114     bool OptimizeBlock(MachineBasicBlock *MBB);
115     void RemoveDeadBlock(MachineBasicBlock *MBB);
116     bool OptimizeImpDefsBlock(MachineBasicBlock *MBB);
117
118     bool HoistCommonCode(MachineFunction &MF);
119     bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB);
120   };
121 }
122
123 #endif /* LLVM_CODEGEN_BRANCHFOLDING_HPP */