Home | History | Annotate | Download | only in CodeGen 
      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 */
    161