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_LIB_CODEGEN_BRANCHFOLDING_H
11#define LLVM_LIB_CODEGEN_BRANCHFOLDING_H
12
13#include "llvm/ADT/SmallPtrSet.h"
14#include "llvm/CodeGen/MachineBasicBlock.h"
15#include "llvm/Support/BlockFrequency.h"
16#include <vector>
17
18namespace llvm {
19  class MachineBlockFrequencyInfo;
20  class MachineBranchProbabilityInfo;
21  class MachineFunction;
22  class MachineModuleInfo;
23  class RegScavenger;
24  class TargetInstrInfo;
25  class TargetRegisterInfo;
26
27  class BranchFolder {
28  public:
29    explicit BranchFolder(bool defaultEnableTailMerge, bool CommonHoist,
30                          const MachineBlockFrequencyInfo &MBFI,
31                          const MachineBranchProbabilityInfo &MBPI);
32
33    bool OptimizeFunction(MachineFunction &MF,
34                          const TargetInstrInfo *tii,
35                          const TargetRegisterInfo *tri,
36                          MachineModuleInfo *mmi);
37  private:
38    class MergePotentialsElt {
39      unsigned Hash;
40      MachineBasicBlock *Block;
41    public:
42      MergePotentialsElt(unsigned h, MachineBasicBlock *b)
43        : Hash(h), Block(b) {}
44
45      unsigned getHash() const { return Hash; }
46      MachineBasicBlock *getBlock() const { return Block; }
47
48      void setBlock(MachineBasicBlock *MBB) {
49        Block = MBB;
50      }
51
52      bool operator<(const MergePotentialsElt &) const;
53    };
54    typedef std::vector<MergePotentialsElt>::iterator MPIterator;
55    std::vector<MergePotentialsElt> MergePotentials;
56    SmallPtrSet<const MachineBasicBlock*, 2> TriedMerging;
57
58    class SameTailElt {
59      MPIterator MPIter;
60      MachineBasicBlock::iterator TailStartPos;
61    public:
62      SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp)
63        : MPIter(mp), TailStartPos(tsp) {}
64
65      MPIterator getMPIter() const {
66        return MPIter;
67      }
68      MergePotentialsElt &getMergePotentialsElt() const {
69        return *getMPIter();
70      }
71      MachineBasicBlock::iterator getTailStartPos() const {
72        return TailStartPos;
73      }
74      unsigned getHash() const {
75        return getMergePotentialsElt().getHash();
76      }
77      MachineBasicBlock *getBlock() const {
78        return getMergePotentialsElt().getBlock();
79      }
80      bool tailIsWholeBlock() const {
81        return TailStartPos == getBlock()->begin();
82      }
83
84      void setBlock(MachineBasicBlock *MBB) {
85        getMergePotentialsElt().setBlock(MBB);
86      }
87      void setTailStartPos(MachineBasicBlock::iterator Pos) {
88        TailStartPos = Pos;
89      }
90    };
91    std::vector<SameTailElt> SameTails;
92
93    bool EnableTailMerge;
94    bool EnableHoistCommonCode;
95    const TargetInstrInfo *TII;
96    const TargetRegisterInfo *TRI;
97    MachineModuleInfo *MMI;
98    RegScavenger *RS;
99
100    /// \brief This class keeps track of branch frequencies of newly created
101    /// blocks and tail-merged blocks.
102    class MBFIWrapper {
103    public:
104      MBFIWrapper(const MachineBlockFrequencyInfo &I) : MBFI(I) {}
105      BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const;
106      void setBlockFreq(const MachineBasicBlock *MBB, BlockFrequency F);
107
108    private:
109      const MachineBlockFrequencyInfo &MBFI;
110      DenseMap<const MachineBasicBlock *, BlockFrequency> MergedBBFreq;
111    };
112
113    MBFIWrapper MBBFreqInfo;
114    const MachineBranchProbabilityInfo &MBPI;
115
116    bool TailMergeBlocks(MachineFunction &MF);
117    bool TryTailMergeBlocks(MachineBasicBlock* SuccBB,
118                       MachineBasicBlock* PredBB);
119    void setCommonTailEdgeWeights(MachineBasicBlock &TailMBB);
120    void MaintainLiveIns(MachineBasicBlock *CurMBB,
121                         MachineBasicBlock *NewMBB);
122    void ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
123                                 MachineBasicBlock *NewDest);
124    MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB,
125                                  MachineBasicBlock::iterator BBI1,
126                                  const BasicBlock *BB);
127    unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength,
128                              MachineBasicBlock *SuccBB,
129                              MachineBasicBlock *PredBB);
130    void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock* SuccBB,
131                                                MachineBasicBlock* PredBB);
132    bool CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
133                                   MachineBasicBlock *SuccBB,
134                                   unsigned maxCommonTailLength,
135                                   unsigned &commonTailIndex);
136
137    bool OptimizeBranches(MachineFunction &MF);
138    bool OptimizeBlock(MachineBasicBlock *MBB);
139    void RemoveDeadBlock(MachineBasicBlock *MBB);
140    bool OptimizeImpDefsBlock(MachineBasicBlock *MBB);
141
142    bool HoistCommonCode(MachineFunction &MF);
143    bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB);
144  };
145}
146
147#endif /* LLVM_CODEGEN_BRANCHFOLDING_HPP */
148