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_CODEGEN_BRANCHFOLDING_HPP
     11 #define LLVM_CODEGEN_BRANCHFOLDING_HPP
     12 
     13 #include "llvm/ADT/SmallPtrSet.h"
     14 #include "llvm/CodeGen/MachineBasicBlock.h"
     15 #include <vector>
     16 
     17 namespace llvm {
     18   class MachineFunction;
     19   class MachineModuleInfo;
     20   class RegScavenger;
     21   class TargetInstrInfo;
     22   class TargetRegisterInfo;
     23 
     24   class BranchFolder {
     25   public:
     26     explicit BranchFolder(bool defaultEnableTailMerge, bool CommonHoist);
     27 
     28     bool OptimizeFunction(MachineFunction &MF,
     29                           const TargetInstrInfo *tii,
     30                           const TargetRegisterInfo *tri,
     31                           MachineModuleInfo *mmi);
     32   private:
     33     class MergePotentialsElt {
     34       unsigned Hash;
     35       MachineBasicBlock *Block;
     36     public:
     37       MergePotentialsElt(unsigned h, MachineBasicBlock *b)
     38         : Hash(h), Block(b) {}
     39 
     40       unsigned getHash() const { return Hash; }
     41       MachineBasicBlock *getBlock() const { return Block; }
     42 
     43       void setBlock(MachineBasicBlock *MBB) {
     44         Block = MBB;
     45       }
     46 
     47       bool operator<(const MergePotentialsElt &) const;
     48     };
     49     typedef std::vector<MergePotentialsElt>::iterator MPIterator;
     50     std::vector<MergePotentialsElt> MergePotentials;
     51     SmallPtrSet<const MachineBasicBlock*, 2> TriedMerging;
     52 
     53     class SameTailElt {
     54       MPIterator MPIter;
     55       MachineBasicBlock::iterator TailStartPos;
     56     public:
     57       SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp)
     58         : MPIter(mp), TailStartPos(tsp) {}
     59 
     60       MPIterator getMPIter() const {
     61         return MPIter;
     62       }
     63       MergePotentialsElt &getMergePotentialsElt() const {
     64         return *getMPIter();
     65       }
     66       MachineBasicBlock::iterator getTailStartPos() const {
     67         return TailStartPos;
     68       }
     69       unsigned getHash() const {
     70         return getMergePotentialsElt().getHash();
     71       }
     72       MachineBasicBlock *getBlock() const {
     73         return getMergePotentialsElt().getBlock();
     74       }
     75       bool tailIsWholeBlock() const {
     76         return TailStartPos == getBlock()->begin();
     77       }
     78 
     79       void setBlock(MachineBasicBlock *MBB) {
     80         getMergePotentialsElt().setBlock(MBB);
     81       }
     82       void setTailStartPos(MachineBasicBlock::iterator Pos) {
     83         TailStartPos = Pos;
     84       }
     85     };
     86     std::vector<SameTailElt> SameTails;
     87 
     88     bool EnableTailMerge;
     89     bool EnableHoistCommonCode;
     90     const TargetInstrInfo *TII;
     91     const TargetRegisterInfo *TRI;
     92     MachineModuleInfo *MMI;
     93     RegScavenger *RS;
     94 
     95     bool TailMergeBlocks(MachineFunction &MF);
     96     bool TryTailMergeBlocks(MachineBasicBlock* SuccBB,
     97                        MachineBasicBlock* PredBB);
     98     void MaintainLiveIns(MachineBasicBlock *CurMBB,
     99                          MachineBasicBlock *NewMBB);
    100     void ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
    101                                  MachineBasicBlock *NewDest);
    102     MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB,
    103                                   MachineBasicBlock::iterator BBI1,
    104                                   const BasicBlock *BB);
    105     unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength,
    106                               MachineBasicBlock *SuccBB,
    107                               MachineBasicBlock *PredBB);
    108     void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock* SuccBB,
    109                                                 MachineBasicBlock* PredBB);
    110     bool CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
    111                                    MachineBasicBlock *SuccBB,
    112                                    unsigned maxCommonTailLength,
    113                                    unsigned &commonTailIndex);
    114 
    115     bool OptimizeBranches(MachineFunction &MF);
    116     bool OptimizeBlock(MachineBasicBlock *MBB);
    117     void RemoveDeadBlock(MachineBasicBlock *MBB);
    118     bool OptimizeImpDefsBlock(MachineBasicBlock *MBB);
    119 
    120     bool HoistCommonCode(MachineFunction &MF);
    121     bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB);
    122   };
    123 }
    124 
    125 #endif /* LLVM_CODEGEN_BRANCHFOLDING_HPP */
    126