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