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
17namespace 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                                  const BasicBlock *BB);
105    unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength,
106                              MachineBasicBlock *SuccBB,
107                              MachineBasicBlock *PredBB);
108    void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock* SuccBB,
109                                                MachineBasicBlock* PredBB);
110    bool CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
111                                   MachineBasicBlock *SuccBB,
112                                   unsigned maxCommonTailLength,
113                                   unsigned &commonTailIndex);
114
115    bool OptimizeBranches(MachineFunction &MF);
116    bool OptimizeBlock(MachineBasicBlock *MBB);
117    void RemoveDeadBlock(MachineBasicBlock *MBB);
118    bool OptimizeImpDefsBlock(MachineBasicBlock *MBB);
119
120    bool HoistCommonCode(MachineFunction &MF);
121    bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB);
122  };
123}
124
125#endif /* LLVM_CODEGEN_BRANCHFOLDING_HPP */
126