BranchFolding.cpp

//===-- BranchFolding.cpp - Fold machine code branch instructions ---------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass forwards branches to unconditional branches to make them branch
// directly to the target block.  This pass often results in dead MBB's, which
// it then removes.
//
// Note that this pass must be run after register allocation, it cannot handle
// SSA form.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "branchfolding"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineJumpTableInfo.h"
#include "llvm/CodeGen/RegisterScavenging.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include <algorithm>
using namespace llvm;

STATISTIC(NumDeadBlocks, "Number of dead blocks removed");
STATISTIC(NumBranchOpts, "Number of branches optimized");
STATISTIC(NumTailMerge , "Number of block tails merged");
static cl::opt<cl::boolOrDefault> FlagEnableTailMerge("enable-tail-merge", 
                              cl::init(cl::BOU_UNSET), cl::Hidden);
// Throttle for huge numbers of predecessors (compile speed problems)
static cl::opt<unsigned>
TailMergeThreshold("tail-merge-threshold", 
          cl::desc("Max number of predecessors to consider tail merging"),
          cl::init(100), cl::Hidden);

namespace {
  struct VISIBILITY_HIDDEN BranchFolder : public MachineFunctionPass {
    static char ID;
    explicit BranchFolder(bool defaultEnableTailMerge) : 
        MachineFunctionPass((intptr_t)&ID) {
          switch (FlagEnableTailMerge) {
          case cl::BOU_UNSET: EnableTailMerge = defaultEnableTailMerge; break;
          case cl::BOU_TRUE: EnableTailMerge = true; break;
          case cl::BOU_FALSE: EnableTailMerge = false; break;
          }
    }

    virtual bool runOnMachineFunction(MachineFunction &MF);
    virtual const char *getPassName() const { return "Control Flow Optimizer"; }
    const TargetInstrInfo *TII;
    MachineModuleInfo *MMI;
    bool MadeChange;
  private:
    // Tail Merging.
    bool EnableTailMerge;
    bool TailMergeBlocks(MachineFunction &MF);
    bool TryMergeBlocks(MachineBasicBlock* SuccBB,
                        MachineBasicBlock* PredBB);
    void ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
                                 MachineBasicBlock *NewDest);
    MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB,
                                  MachineBasicBlock::iterator BBI1);
    unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength);
    void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock* SuccBB,
                                                MachineBasicBlock* PredBB);
    unsigned CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
                                       unsigned maxCommonTailLength);

    typedef std::pair<unsigned,MachineBasicBlock*> MergePotentialsElt;
    typedef std::vector<MergePotentialsElt>::iterator MPIterator;
    std::vector<MergePotentialsElt> MergePotentials;

    typedef std::pair<MPIterator, MachineBasicBlock::iterator> SameTailElt;
    std::vector<SameTailElt> SameTails;

    const TargetRegisterInfo *RegInfo;
    RegScavenger *RS;
    // Branch optzn.
    bool OptimizeBranches(MachineFunction &MF);
    void OptimizeBlock(MachineBasicBlock *MBB);
    void RemoveDeadBlock(MachineBasicBlock *MBB);
    bool OptimizeImpDefsBlock(MachineBasicBlock *MBB);
    
    bool CanFallThrough(MachineBasicBlock *CurBB);
    bool CanFallThrough(MachineBasicBlock *CurBB, bool BranchUnAnalyzable,
                        MachineBasicBlock *TBB, MachineBasicBlock *FBB,
                        const SmallVectorImpl<MachineOperand> &Cond);
  };
  char BranchFolder::ID = 0;
}

FunctionPass *llvm::createBranchFoldingPass(bool DefaultEnableTailMerge) { 
      return new BranchFolder(DefaultEnableTailMerge); }

/// RemoveDeadBlock - Remove the specified dead machine basic block from the
/// function, updating the CFG.
void BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) {
  assert(MBB->pred_empty() && "MBB must be dead!");
  DOUT << "\nRemoving MBB: " << *MBB;
  
  MachineFunction *MF = MBB->getParent();
  // drop all successors.
  while (!MBB->succ_empty())
    MBB->removeSuccessor(MBB->succ_end()-1);
  
  // If there are any labels in the basic block, unregister them from
  // MachineModuleInfo.
  if (MMI && !MBB->empty()) {
    for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
         I != E; ++I) {
      if (I->isLabel())
        // The label ID # is always operand #0, an immediate.
        MMI->InvalidateLabel(I->getOperand(0).getImm());
    }
  }
  
  // Remove the block.
  MF->erase(MBB);
}

/// OptimizeImpDefsBlock - If a basic block is just a bunch of implicit_def
/// followed by terminators, and if the implicitly defined registers are not
/// used by the terminators, remove those implicit_def's. e.g.
/// BB1:
///   r0 = implicit_def
///   r1 = implicit_def
///   br
/// This block can be optimized away later if the implicit instructions are
/// removed.
bool BranchFolder::OptimizeImpDefsBlock(MachineBasicBlock *MBB) {
  SmallSet<unsigned, 4> ImpDefRegs;
  MachineBasicBlock::iterator I = MBB->begin();
  while (I != MBB->end()) {
    if (I->getOpcode() != TargetInstrInfo::IMPLICIT_DEF)
      break;
    unsigned Reg = I->getOperand(0).getReg();
    ImpDefRegs.insert(Reg);
    for (const unsigned *SubRegs = RegInfo->getSubRegisters(Reg);
         unsigned SubReg = *SubRegs; ++SubRegs)
      ImpDefRegs.insert(SubReg);
    ++I;
  }
  if (ImpDefRegs.empty())
    return false;

  MachineBasicBlock::iterator FirstTerm = I;
  while (I != MBB->end()) {
    if (!TII->isUnpredicatedTerminator(I))
      return false;
    // See if it uses any of the implicitly defined registers.
    for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
      MachineOperand &MO = I->getOperand(i);
      if (!MO.isReg() || !MO.isUse())
        continue;
      unsigned Reg = MO.getReg();
      if (ImpDefRegs.count(Reg))
        return false;
    }
    ++I;
  }

  I = MBB->begin();
  while (I != FirstTerm) {
    MachineInstr *ImpDefMI = &*I;
    ++I;
    MBB->erase(ImpDefMI);
  }

  return true;
}

bool BranchFolder::runOnMachineFunction(MachineFunction &MF) {
  TII = MF.getTarget().getInstrInfo();
  if (!TII) return false;

  RegInfo = MF.getTarget().getRegisterInfo();

  // Fix CFG.  The later algorithms expect it to be right.
  bool EverMadeChange = false;
  for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; I++) {
    MachineBasicBlock *MBB = I, *TBB = 0, *FBB = 0;
    SmallVector<MachineOperand, 4> Cond;
    if (!TII->AnalyzeBranch(*MBB, TBB, FBB, Cond))
      EverMadeChange |= MBB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty());
    EverMadeChange |= OptimizeImpDefsBlock(MBB);
  }

  RS = RegInfo->requiresRegisterScavenging(MF) ? new RegScavenger() : NULL;