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