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