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