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 LLVM_LIBRARY_VISIBILITY 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    DenseMap<const MachineBasicBlock *, int> FuncletMembership;
58
59    class SameTailElt {
60      MPIterator MPIter;
61      MachineBasicBlock::iterator TailStartPos;
62    public:
63      SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp)
64        : MPIter(mp), TailStartPos(tsp) {}
65
66      MPIterator getMPIter() const {
67        return MPIter;
68      }
69      MergePotentialsElt &getMergePotentialsElt() const {
70        return *getMPIter();
71      }
72      MachineBasicBlock::iterator getTailStartPos() const {
73        return TailStartPos;
74      }
75      unsigned getHash() const {
76        return getMergePotentialsElt().getHash();
77      }
78      MachineBasicBlock *getBlock() const {
79        return getMergePotentialsElt().getBlock();
80      }
81      bool tailIsWholeBlock() const {
82        return TailStartPos == getBlock()->begin();
83      }
84
85      void setBlock(MachineBasicBlock *MBB) {
86        getMergePotentialsElt().setBlock(MBB);
87      }
88      void setTailStartPos(MachineBasicBlock::iterator Pos) {
89        TailStartPos = Pos;
90      }
91    };
92    std::vector<SameTailElt> SameTails;
93
94    bool EnableTailMerge;
95    bool EnableHoistCommonCode;
96    const TargetInstrInfo *TII;
97    const TargetRegisterInfo *TRI;
98    MachineModuleInfo *MMI;
99    RegScavenger *RS;
100
101    /// \brief This class keeps track of branch frequencies of newly created
102    /// blocks and tail-merged blocks.
103    class MBFIWrapper {
104    public:
105      MBFIWrapper(const MachineBlockFrequencyInfo &I) : MBFI(I) {}
106      BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const;
107      void setBlockFreq(const MachineBasicBlock *MBB, BlockFrequency F);
108
109    private:
110      const MachineBlockFrequencyInfo &MBFI;
111      DenseMap<const MachineBasicBlock *, BlockFrequency> MergedBBFreq;
112    };
113
114    MBFIWrapper MBBFreqInfo;
115    const MachineBranchProbabilityInfo &MBPI;
116
117    bool TailMergeBlocks(MachineFunction &MF);
118    bool TryTailMergeBlocks(MachineBasicBlock* SuccBB,
119                       MachineBasicBlock* PredBB);
120    void setCommonTailEdgeWeights(MachineBasicBlock &TailMBB);
121    void MaintainLiveIns(MachineBasicBlock *CurMBB,
122                         MachineBasicBlock *NewMBB);
123    void ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
124                                 MachineBasicBlock *NewDest);
125    MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB,
126                                  MachineBasicBlock::iterator BBI1,
127                                  const BasicBlock *BB);
128    unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength,
129                              MachineBasicBlock *SuccBB,
130                              MachineBasicBlock *PredBB);
131    void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock* SuccBB,
132                                                MachineBasicBlock* PredBB);
133    bool CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
134                                   MachineBasicBlock *SuccBB,
135                                   unsigned maxCommonTailLength,
136                                   unsigned &commonTailIndex);
137
138    bool OptimizeBranches(MachineFunction &MF);
139    bool OptimizeBlock(MachineBasicBlock *MBB);
140    void RemoveDeadBlock(MachineBasicBlock *MBB);
141    bool OptimizeImpDefsBlock(MachineBasicBlock *MBB);
142
143    bool HoistCommonCode(MachineFunction &MF);
144    bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB);
145  };
146}
147
148#endif /* LLVM_CODEGEN_BRANCHFOLDING_HPP */
149