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/CodeGen/MachineBasicBlock.h"
  14 #include <vector>
  15
  16 namespace llvm {
  17   class MachineFunction;
  18   class MachineModuleInfo;
  19   class RegScavenger;
  20   class TargetInstrInfo;
  21   class TargetRegisterInfo;
  22   template<typename T> class SmallVectorImpl;
  23
  24   class BranchFolder {
  25   public:
  26     explicit BranchFolder(bool defaultEnableTailMerge);
  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
  52     class SameTailElt {
  53       MPIterator MPIter;
  54       MachineBasicBlock::iterator TailStartPos;
  55     public:
  56       SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp)
  57         : MPIter(mp), TailStartPos(tsp) {}
  58
  59       MPIterator getMPIter() const {
  60         return MPIter;
  61       }
  62       MergePotentialsElt &getMergePotentialsElt() const {
  63         return *getMPIter();
  64       }
  65       MachineBasicBlock::iterator getTailStartPos() const {
  66         return TailStartPos;
  67       }
  68       unsigned getHash() const {
  69         return getMergePotentialsElt().getHash();
  70       }
  71       MachineBasicBlock *getBlock() const {
  72         return getMergePotentialsElt().getBlock();
  73       }
  74       bool tailIsWholeBlock() const {
  75         return TailStartPos == getBlock()->begin();
  76       }
  77
  78       void setBlock(MachineBasicBlock *MBB) {
  79         getMergePotentialsElt().setBlock(MBB);
  80       }
  81       void setTailStartPos(MachineBasicBlock::iterator Pos) {
  82         TailStartPos = Pos;
  83       }
  84     };
  85     std::vector<SameTailElt> SameTails;
  86
  87     bool EnableTailMerge;
  88     const TargetInstrInfo *TII;
  89     const TargetRegisterInfo *TRI;
  90     MachineModuleInfo *MMI;
  91     RegScavenger *RS;
  92
  93     bool TailMergeBlocks(MachineFunction &MF);
  94     bool TryTailMergeBlocks(MachineBasicBlock* SuccBB,
  95                        MachineBasicBlock* PredBB);
  96     void ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
  97                                  MachineBasicBlock *NewDest);
  98     MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB,
  99                                   MachineBasicBlock::iterator BBI1);
 100     unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength,
 101                               MachineBasicBlock *SuccBB,
 102                               MachineBasicBlock *PredBB);
 103     void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock* SuccBB,
 104                                                 MachineBasicBlock* PredBB);
 105     bool CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
 106                                    unsigned maxCommonTailLength,
 107                                    unsigned &commonTailIndex);
 108
 109     bool OptimizeBranches(MachineFunction &MF);
 110     bool OptimizeBlock(MachineBasicBlock *MBB);
 111     void RemoveDeadBlock(MachineBasicBlock *MBB);
 112     bool OptimizeImpDefsBlock(MachineBasicBlock *MBB);
 113   };
 114 }
 115
 116 #endif /* LLVM_CODEGEN_BRANCHFOLDING_HPP */