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/MachineBasicBlock.h"
  15 #include "llvm/Support/BlockFrequency.h"
  16 #include <vector>
  17
  18 namespace 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 */