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     typedef std::pair<unsigned,MachineBasicBlock*> MergePotentialsElt;
  34     typedef std::vector<MergePotentialsElt>::iterator MPIterator;
  35     std::vector<MergePotentialsElt> MergePotentials;
  36
  37     typedef std::pair<MPIterator, MachineBasicBlock::iterator> SameTailElt;
  38     std::vector<SameTailElt> SameTails;
  39
  40     bool EnableTailMerge;
  41     const TargetInstrInfo *TII;
  42     const TargetRegisterInfo *TRI;
  43     MachineModuleInfo *MMI;
  44     RegScavenger *RS;
  45
  46     bool TailMergeBlocks(MachineFunction &MF);
  47     bool TryTailMergeBlocks(MachineBasicBlock* SuccBB,
  48                        MachineBasicBlock* PredBB);
  49     void ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
  50                                  MachineBasicBlock *NewDest);
  51     MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB,
  52                                   MachineBasicBlock::iterator BBI1);
  53     unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength,
  54                               MachineBasicBlock *SuccBB,
  55                               MachineBasicBlock *PredBB);
  56     void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock* SuccBB,
  57                                                 MachineBasicBlock* PredBB);
  58     unsigned CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
  59                                        unsigned maxCommonTailLength);
  60
  61     bool TailDuplicate(MachineBasicBlock *TailBB,
  62                        bool PrevFallsThrough,
  63                        MachineFunction &MF);
  64
  65     bool OptimizeBranches(MachineFunction &MF);
  66     bool OptimizeBlock(MachineBasicBlock *MBB);
  67     void RemoveDeadBlock(MachineBasicBlock *MBB);
  68     bool OptimizeImpDefsBlock(MachineBasicBlock *MBB);
  69
  70     bool CanFallThrough(MachineBasicBlock *CurBB);
  71     bool CanFallThrough(MachineBasicBlock *CurBB, bool BranchUnAnalyzable,
  72                         MachineBasicBlock *TBB, MachineBasicBlock *FBB,
  73                         const SmallVectorImpl<MachineOperand> &Cond);
  74   };
  75
  76
  77   /// BranchFolderPass - Wrap branch folder in a machine function pass.
  78   class BranchFolderPass : public MachineFunctionPass,
  79                            public BranchFolder {
  80   public:
  81     static char ID;
  82     explicit BranchFolderPass(bool defaultEnableTailMerge)
  83       :  MachineFunctionPass(&ID), BranchFolder(defaultEnableTailMerge) {}
  84
  85     virtual bool runOnMachineFunction(MachineFunction &MF);
  86     virtual const char *getPassName() const { return "Control Flow Optimizer"; }
  87   };
  88 }
  89
  90 #endif /* LLVM_CODEGEN_BRANCHFOLDING_HPP */