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 "llvm/CodeGen/MachineFunctionPass.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);
  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     unsigned CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
 106                                        unsigned maxCommonTailLength);
 107
 108     bool TailDuplicate(MachineBasicBlock *TailBB,
 109                        bool PrevFallsThrough,
 110                        MachineFunction &MF);
 111
 112     bool OptimizeBranches(MachineFunction &MF);
 113     bool OptimizeBlock(MachineBasicBlock *MBB);
 114     void RemoveDeadBlock(MachineBasicBlock *MBB);
 115     bool OptimizeImpDefsBlock(MachineBasicBlock *MBB);
 116
 117     bool CanFallThrough(MachineBasicBlock *CurBB);
 118     bool CanFallThrough(MachineBasicBlock *CurBB, bool BranchUnAnalyzable,
 119                         MachineBasicBlock *TBB, MachineBasicBlock *FBB,
 120                         const SmallVectorImpl<MachineOperand> &Cond);
 121   };
 122
 123
 124   /// BranchFolderPass - Wrap branch folder in a machine function pass.
 125   class BranchFolderPass : public MachineFunctionPass,
 126                            public BranchFolder {
 127   public:
 128     static char ID;
 129     explicit BranchFolderPass(bool defaultEnableTailMerge)
 130       :  MachineFunctionPass(&ID), BranchFolder(defaultEnableTailMerge) {}
 131
 132     virtual bool runOnMachineFunction(MachineFunction &MF);
 133     virtual const char *getPassName() const { return "Control Flow Optimizer"; }
 134   };
 135 }
 136
 137 #endif /* LLVM_CODEGEN_BRANCHFOLDING_HPP */