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 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 */