llvm.org GIT mirror llvm / 71f7f73 lib / CodeGen / BranchFolding.h

Tree @71f7f73 (Download .tar.gz)

BranchFolding.h @71f7f73raw · history · blame

//===-- BranchFolding.h - Fold machine code branch instructions --*- C++ -*===//
//                     The LLVM Compiler Infrastructure
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.


#include "llvm/CodeGen/MachineBasicBlock.h"
#include <vector>

namespace llvm {
  class MachineFunction;
  class MachineModuleInfo;
  class RegScavenger;
  class TargetInstrInfo;
  class TargetRegisterInfo;
  template<typename T> class SmallVectorImpl;

  class BranchFolder {
    explicit BranchFolder(bool defaultEnableTailMerge);

    bool OptimizeFunction(MachineFunction &MF,
                          const TargetInstrInfo *tii,
                          const TargetRegisterInfo *tri,
                          MachineModuleInfo *mmi);
    class MergePotentialsElt {
      unsigned Hash;
      MachineBasicBlock *Block;
      MergePotentialsElt(unsigned h, MachineBasicBlock *b)
        : Hash(h), Block(b) {}

      unsigned getHash() const { return Hash; }
      MachineBasicBlock *getBlock() const { return Block; }

      void setBlock(MachineBasicBlock *MBB) {
        Block = MBB;

      bool operator<(const MergePotentialsElt &) const;
    typedef std::vector<MergePotentialsElt>::iterator MPIterator;
    std::vector<MergePotentialsElt> MergePotentials;

    class SameTailElt {
      MPIterator MPIter;
      MachineBasicBlock::iterator TailStartPos;
      SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp)
        : MPIter(mp), TailStartPos(tsp) {}

      MPIterator getMPIter() const {
        return MPIter;
      MergePotentialsElt &getMergePotentialsElt() const {
        return *getMPIter();
      MachineBasicBlock::iterator getTailStartPos() const {
        return TailStartPos;
      unsigned getHash() const {
        return getMergePotentialsElt().getHash();
      MachineBasicBlock *getBlock() const {
        return getMergePotentialsElt().getBlock();
      bool tailIsWholeBlock() const {
        return TailStartPos == getBlock()->begin();

      void setBlock(MachineBasicBlock *MBB) {
      void setTailStartPos(MachineBasicBlock::iterator Pos) {
        TailStartPos = Pos;
    std::vector<SameTailElt> SameTails;

    bool EnableTailMerge;
    const TargetInstrInfo *TII;
    const TargetRegisterInfo *TRI;
    MachineModuleInfo *MMI;
    RegScavenger *RS;

    bool TailMergeBlocks(MachineFunction &MF);
    bool TryTailMergeBlocks(MachineBasicBlock* SuccBB,
                       MachineBasicBlock* PredBB);
    void ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
                                 MachineBasicBlock *NewDest);
    MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB,
                                  MachineBasicBlock::iterator BBI1);
    unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength,
                              MachineBasicBlock *SuccBB,
                              MachineBasicBlock *PredBB);
    void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock* SuccBB,
                                                MachineBasicBlock* PredBB);
    bool CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
                                   unsigned maxCommonTailLength,
                                   unsigned &commonTailIndex);

    bool OptimizeBranches(MachineFunction &MF);
    bool OptimizeBlock(MachineBasicBlock *MBB);
    void RemoveDeadBlock(MachineBasicBlock *MBB);
    bool OptimizeImpDefsBlock(MachineBasicBlock *MBB);