LLVM  6.0.0svn
Macros | Functions | Variables
BranchFolding.cpp File Reference
#include "BranchFolding.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/Analysis.h"
#include "llvm/CodeGen/LivePhysRegs.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineJumpTableInfo.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetOpcodes.h"
#include "llvm/CodeGen/TargetPassConfig.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/Function.h"
#include "llvm/MC/LaneBitmask.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/Pass.h"
#include "llvm/Support/BlockFrequency.h"
#include "llvm/Support/BranchProbability.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetMachine.h"
#include <cassert>
#include <cstddef>
#include <iterator>
#include <numeric>
#include <vector>
Include dependency graph for BranchFolding.cpp:

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "branch-folder"
 

Functions

 STATISTIC (NumDeadBlocks, "Number of dead blocks removed")
 
 STATISTIC (NumBranchOpts, "Number of branches optimized")
 
 STATISTIC (NumTailMerge, "Number of block tails merged")
 
 STATISTIC (NumHoist, "Number of times common instructions are hoisted")
 
 STATISTIC (NumTailCalls, "Number of tail calls optimized")
 
 INITIALIZE_PASS (BranchFolderPass, DEBUG_TYPE, "Control Flow Optimizer", false, false) bool BranchFolderPass
 
static unsigned HashMachineInstr (const MachineInstr &MI)
 HashMachineInstr - Compute a hash value for MI and its operands. More...
 
static unsigned HashEndOfMBB (const MachineBasicBlock &MBB)
 HashEndOfMBB - Hash the last instruction in the MBB. More...
 
static unsigned ComputeCommonTailLength (MachineBasicBlock *MBB1, MachineBasicBlock *MBB2, MachineBasicBlock::iterator &I1, MachineBasicBlock::iterator &I2)
 ComputeCommonTailLength - Given two machine basic blocks, compute the number of instructions they actually have in common together at their end. More...
 
static unsigned EstimateRuntime (MachineBasicBlock::iterator I, MachineBasicBlock::iterator E)
 EstimateRuntime - Make a rough estimate for how long it will take to run the specified code. More...
 
static void FixTail (MachineBasicBlock *CurMBB, MachineBasicBlock *SuccBB, const TargetInstrInfo *TII)
 
static unsigned CountTerminators (MachineBasicBlock *MBB, MachineBasicBlock::iterator &I)
 CountTerminators - Count the number of terminators in the given block and set I to the position of the first non-terminator, if there is one, or MBB->end() otherwise. More...
 
static bool blockEndsInUnreachable (const MachineBasicBlock *MBB)
 A no successor, non-return block probably ends in unreachable and is cold. More...
 
static bool ProfitableToMerge (MachineBasicBlock *MBB1, MachineBasicBlock *MBB2, unsigned MinCommonTailLength, unsigned &CommonTailLen, MachineBasicBlock::iterator &I1, MachineBasicBlock::iterator &I2, MachineBasicBlock *SuccBB, MachineBasicBlock *PredBB, DenseMap< const MachineBasicBlock *, int > &FuncletMembership, bool AfterPlacement)
 ProfitableToMerge - Check if two machine basic blocks have a common tail and decide if it would be profitable to merge those tails. More...
 
static void mergeOperations (MachineBasicBlock::iterator MBBIStartPos, MachineBasicBlock &MBBCommon)
 
static bool IsEmptyBlock (MachineBasicBlock *MBB)
 
static bool IsBranchOnlyBlock (MachineBasicBlock *MBB)
 
static bool IsBetterFallthrough (MachineBasicBlock *MBB1, MachineBasicBlock *MBB2)
 IsBetterFallthrough - Return true if it would be clearly better to fall-through to MBB1 than to fall through into MBB2. More...
 
static DebugLoc getBranchDebugLoc (MachineBasicBlock &MBB)
 getBranchDebugLoc - Find and return, if any, the DebugLoc of the branch instructions on the block. More...
 
static MachineBasicBlockfindFalseBlock (MachineBasicBlock *BB, MachineBasicBlock *TrueBB)
 findFalseBlock - BB has a fallthrough. More...
 
template<class Container >
static void addRegAndItsAliases (unsigned Reg, const TargetRegisterInfo *TRI, Container &Set)
 
static MachineBasicBlock::iterator findHoistingInsertPosAndDeps (MachineBasicBlock *MBB, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI, SmallSet< unsigned, 4 > &Uses, SmallSet< unsigned, 4 > &Defs)
 findHoistingInsertPosAndDeps - Find the location to move common instructions in successors to. More...
 

Variables

static cl::opt< cl::boolOrDefaultFlagEnableTailMerge ("enable-tail-merge", cl::init(cl::BOU_UNSET), cl::Hidden)
 
static cl::opt< unsignedTailMergeThreshold ("tail-merge-threshold", cl::desc("Max number of predecessors to consider tail merging"), cl::init(150), cl::Hidden)
 
static cl::opt< unsignedTailMergeSize ("tail-merge-size", cl::desc("Min number of instructions to consider tail merging"), cl::init(3), cl::Hidden)
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "branch-folder"

Definition at line 68 of file BranchFolding.cpp.

Function Documentation

◆ addRegAndItsAliases()

template<class Container >
static void addRegAndItsAliases ( unsigned  Reg,
const TargetRegisterInfo TRI,
Container &  Set 
)
static

◆ blockEndsInUnreachable()

static bool blockEndsInUnreachable ( const MachineBasicBlock MBB)
static

A no successor, non-return block probably ends in unreachable and is cold.

Also consider a block that ends in an indirect branch to be a return block, since many targets use plain indirect branches to return.

Definition at line 571 of file BranchFolding.cpp.

References llvm::MachineBasicBlock::back(), llvm::MachineBasicBlock::empty(), llvm::MachineInstr::isIndirectBranch(), llvm::MachineInstr::isReturn(), and llvm::MachineBasicBlock::succ_empty().

Referenced by ProfitableToMerge().

◆ ComputeCommonTailLength()

static unsigned ComputeCommonTailLength ( MachineBasicBlock MBB1,
MachineBasicBlock MBB2,
MachineBasicBlock::iterator I1,
MachineBasicBlock::iterator I2 
)
static

◆ CountTerminators()

static unsigned CountTerminators ( MachineBasicBlock MBB,
MachineBasicBlock::iterator I 
)
static

CountTerminators - Count the number of terminators in the given block and set I to the position of the first non-terminator, if there is one, or MBB->end() otherwise.

Definition at line 552 of file BranchFolding.cpp.

References llvm::MachineBasicBlock::begin(), llvm::MachineBasicBlock::end(), and I.

Referenced by ProfitableToMerge().

◆ EstimateRuntime()

static unsigned EstimateRuntime ( MachineBasicBlock::iterator  I,
MachineBasicBlock::iterator  E 
)
static

EstimateRuntime - Make a rough estimate for how long it will take to run the specified code.

Definition at line 453 of file BranchFolding.cpp.

References E, and I.

Referenced by ProfitableToMerge().

◆ findFalseBlock()

static MachineBasicBlock* findFalseBlock ( MachineBasicBlock BB,
MachineBasicBlock TrueBB 
)
static

findFalseBlock - BB has a fallthrough.

Find its 'false' successor given its 'true' successor.

Definition at line 1777 of file BranchFolding.cpp.

References llvm::MachineBasicBlock::successors().

Referenced by findHoistingInsertPosAndDeps().

◆ findHoistingInsertPosAndDeps()

static MachineBasicBlock::iterator findHoistingInsertPosAndDeps ( MachineBasicBlock MBB,
const TargetInstrInfo TII,
const TargetRegisterInfo TRI,
SmallSet< unsigned, 4 > &  Uses,
SmallSet< unsigned, 4 > &  Defs 
)
static

findHoistingInsertPosAndDeps - Find the location to move common instructions in successors to.

The location is usually just before the terminator, however if the terminator is a conditional branch and its previous instruction is the flag setting instruction, the previous instruction is the preferred location. This function also gathers uses and defs of the instructions from the insertion point to the end of the block. The data is used by HoistCommonCodeInSuccs to ensure safety.

Definition at line 1804 of file BranchFolding.cpp.

References llvm::MachineBasicBlock::addLiveIn(), addRegAndItsAliases(), llvm::TargetInstrInfo::analyzeBranch(), llvm::MachineBasicBlock::begin(), llvm::MachineInstr::CheckKillDead, llvm::SmallSet< T, N, C >::count(), llvm::tgtok::Def, llvm::SmallSet< T, N, C >::empty(), llvm::SmallVectorBase::empty(), llvm::MachineBasicBlock::end(), llvm::SmallSet< T, N, C >::erase(), findFalseBlock(), llvm::MachineBasicBlock::getFirstTerminator(), llvm::TargetRegisterInfo::isPhysicalRegister(), llvm::TargetInstrInfo::isPredicated(), llvm::TargetInstrInfo::isUnpredicatedTerminator(), llvm::MCRegisterInfo::DiffListIterator::isValid(), llvm::MCRegAliasIterator::isValid(), llvm::TargetRegisterInfo::isVirtualRegister(), llvm::MachineBasicBlock::pred_size(), llvm::SmallVectorTemplateBase< T, isPodLike >::push_back(), llvm::MachineBasicBlock::removeLiveIn(), llvm::SmallVectorTemplateCommon< T, typename >::size(), llvm::skipDebugInstructionsBackward(), llvm::skipDebugInstructionsForward(), llvm::MachineBasicBlock::sortUniqueLiveIns(), and llvm::MachineBasicBlock::splice().

◆ FixTail()

static void FixTail ( MachineBasicBlock CurMBB,
MachineBasicBlock SuccBB,
const TargetInstrInfo TII 
)
static

◆ getBranchDebugLoc()

static DebugLoc getBranchDebugLoc ( MachineBasicBlock MBB)
static

getBranchDebugLoc - Find and return, if any, the DebugLoc of the branch instructions on the block.

Definition at line 1318 of file BranchFolding.cpp.

References llvm::TargetInstrInfo::analyzeBranch(), assert(), llvm::MachineFunction::back(), llvm::MachineBasicBlock::begin(), llvm::MachineFunction::begin(), llvm::MachineBasicBlock::canFallThrough(), llvm::TargetInstrInfo::canMakeTailCallConditional(), llvm::SmallVectorImpl< T >::clear(), llvm::MachineBasicBlock::CorrectExtraCFGEdges(), llvm::dbgs(), DEBUG, E, llvm::SmallVectorBase::empty(), llvm::MachineBasicBlock::empty(), llvm::MachineBasicBlock::end(), llvm::MachineFunction::end(), llvm::MachineBasicBlock::erase(), llvm::MachineInstr::eraseFromParent(), llvm::MachineBasicBlock::getFirstNonDebugInstr(), llvm::MachineFunction::getFunction(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::MachineFunction::getJumpTableInfo(), llvm::MachineBasicBlock::getLastNonDebugInstr(), llvm::MachineBasicBlock::getNumber(), llvm::MachineBasicBlock::getParent(), llvm::MachineBasicBlock::hasAddressTaken(), I, llvm::TargetInstrInfo::insertBranch(), IsBetterFallthrough(), IsBranchOnlyBlock(), llvm::MachineBasicBlock::isEHPad(), IsEmptyBlock(), llvm::MachineBasicBlock::isSuccessor(), llvm::TargetInstrInfo::isUnconditionalTailCall(), llvm::MachineBasicBlock::moveAfter(), llvm::MachineBasicBlock::moveBefore(), llvm::Function::optForSize(), llvm::MachineBasicBlock::pred_begin(), llvm::MachineBasicBlock::pred_empty(), llvm::MachineBasicBlock::pred_end(), llvm::MachineBasicBlock::pred_size(), llvm::MachineBasicBlock::predecessors(), llvm::TargetInstrInfo::removeBranch(), llvm::MachineBasicBlock::removeSuccessor(), llvm::TargetInstrInfo::replaceBranchWithTailCall(), llvm::MachineBasicBlock::ReplaceUsesOfBlockWith(), llvm::TargetInstrInfo::reverseBranchCondition(), llvm::MachineBasicBlock::splice(), llvm::MachineBasicBlock::succ_begin(), llvm::MachineBasicBlock::succ_empty(), llvm::MachineBasicBlock::succ_size(), llvm::MachineBasicBlock::successors(), llvm::MipsISD::TailCall, and llvm::MachineBasicBlock::transferSuccessors().

◆ HashEndOfMBB()

static unsigned HashEndOfMBB ( const MachineBasicBlock MBB)
static

HashEndOfMBB - Hash the last instruction in the MBB.

Definition at line 291 of file BranchFolding.cpp.

References llvm::MachineBasicBlock::end(), llvm::MachineBasicBlock::getLastNonDebugInstr(), HashMachineInstr(), and I.

Referenced by mergeOperations().

◆ HashMachineInstr()

static unsigned HashMachineInstr ( const MachineInstr MI)
static

◆ INITIALIZE_PASS()

INITIALIZE_PASS ( BranchFolderPass  ,
DEBUG_TYPE  ,
"Control Flow Optimizer ,
false  ,
false   
)

◆ IsBetterFallthrough()

static bool IsBetterFallthrough ( MachineBasicBlock MBB1,
MachineBasicBlock MBB2 
)
static

IsBetterFallthrough - Return true if it would be clearly better to fall-through to MBB1 than to fall through into MBB2.

This has to return a strict ordering, returning true for both (MBB1,MBB2) and (MBB2,MBB1) will result in infinite loops.

Definition at line 1297 of file BranchFolding.cpp.

References llvm::MachineBasicBlock::end(), llvm::MachineBasicBlock::getLastNonDebugInstr(), and llvm::MachineBasicBlock::isSuccessor().

Referenced by getBranchDebugLoc().

◆ IsBranchOnlyBlock()

static bool IsBranchOnlyBlock ( MachineBasicBlock MBB)
static

◆ IsEmptyBlock()

static bool IsEmptyBlock ( MachineBasicBlock MBB)
static

◆ mergeOperations()

static void mergeOperations ( MachineBasicBlock::iterator  MBBIStartPos,
MachineBasicBlock MBBCommon 
)
static

Definition at line 798 of file BranchFolding.cpp.

References llvm::addLiveIns(), llvm::LivePhysRegs::addLiveOuts(), llvm::TargetInstrInfo::analyzeBranch(), llvm::array_pod_sort(), assert(), llvm::LivePhysRegs::available(), llvm::MachineBasicBlock::begin(), llvm::MachineFunction::begin(), llvm::BuildMI(), llvm::computeLiveIns(), llvm::dbgs(), DEBUG, E, llvm::SmallVectorBase::empty(), llvm::sys::path::end(), llvm::MachineBasicBlock::end(), llvm::MachineFunction::end(), FixTail(), llvm::MCInstrInfo::get(), llvm::BranchFolder::MBFIWrapper::getBlockFreq(), llvm::BranchProbability::getBranchProbability(), llvm::MachineBranchProbabilityInfo::getEdgeProbability(), llvm::getFuncletMembership(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::MachineLoopInfo::getLoopFor(), llvm::DILocation::getMergedLocation(), llvm::MachineBasicBlock::getNumber(), HashEndOfMBB(), I, llvm::LivePhysRegs::init(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::TargetInstrInfo::insertBranch(), llvm::MachineBasicBlock::isEHPad(), llvm::MachineOperand::isReg(), llvm::MachineOperand::isUndef(), MI, llvm::MachineBasicBlock::pred_empty(), llvm::MachineBasicBlock::predecessors(), llvm::MachineBasicBlock::rbegin(), llvm::TargetInstrInfo::removeBranch(), llvm::MachineBasicBlock::rend(), llvm::MachineFunction::RenumberBlocks(), llvm::TargetInstrInfo::reverseBranchCondition(), llvm::BranchFolder::MBFIWrapper::setBlockFreq(), llvm::MachineOperand::setIsUndef(), llvm::MachineBasicBlock::setSuccProbability(), llvm::MachineBasicBlock::succ_begin(), llvm::MachineBasicBlock::succ_empty(), llvm::MachineBasicBlock::succ_end(), llvm::MachineBasicBlock::succ_size(), and TailMergeThreshold.

◆ ProfitableToMerge()

static bool ProfitableToMerge ( MachineBasicBlock MBB1,
MachineBasicBlock MBB2,
unsigned  MinCommonTailLength,
unsigned CommonTailLen,
MachineBasicBlock::iterator I1,
MachineBasicBlock::iterator I2,
MachineBasicBlock SuccBB,
MachineBasicBlock PredBB,
DenseMap< const MachineBasicBlock *, int > &  FuncletMembership,
bool  AfterPlacement 
)
static

ProfitableToMerge - Check if two machine basic blocks have a common tail and decide if it would be profitable to merge those tails.

Return the length of the common tail and iterators to the first common instruction in each block. MBB1, MBB2 The blocks to check MinCommonTailLength Minimum size of tail block to be merged. CommonTailLen Out parameter to record the size of the shared tail between MBB1 and MBB2 I1, I2 Iterator references that will be changed to point to the first instruction in the common tail shared by MBB1,MBB2 SuccBB A common successor of MBB1, MBB2 which are in a canonical form relative to SuccBB PredBB The layout predecessor of SuccBB, if any. FuncletMembership map from block to funclet #. AfterPlacement True if we are merging blocks after layout. Stricter thresholds apply to prevent undoing tail-duplication.

Definition at line 596 of file BranchFolding.cpp.

References assert(), B, llvm::MachineBasicBlock::back(), llvm::sys::path::begin(), llvm::MachineBasicBlock::begin(), llvm::MachineFunction::begin(), blockEndsInUnreachable(), llvm::MachineBasicBlock::canFallThrough(), ComputeCommonTailLength(), CountTerminators(), llvm::dbgs(), DEBUG, llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::empty(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::end(), EstimateRuntime(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::find(), FixTail(), llvm::MachineBasicBlock::getBasicBlock(), llvm::MachineFunction::getFunction(), llvm::MachineBasicBlock::getNumber(), llvm::MachineBasicBlock::getParent(), I, llvm::MachineInstr::isBarrier(), llvm::MachineBasicBlock::isLayoutSuccessor(), llvm::Function::optForSize(), and llvm::MachineBasicBlock::succ_size().

◆ STATISTIC() [1/5]

STATISTIC ( NumDeadBlocks  ,
"Number of dead blocks removed"   
)

◆ STATISTIC() [2/5]

STATISTIC ( NumBranchOpts  ,
"Number of branches optimized"   
)

◆ STATISTIC() [3/5]

STATISTIC ( NumTailMerge  ,
"Number of block tails merged"   
)

◆ STATISTIC() [4/5]

STATISTIC ( NumHoist  ,
"Number of times common instructions are hoisted"   
)

◆ STATISTIC() [5/5]

STATISTIC ( NumTailCalls  ,
"Number of tail calls optimized"   
)

Variable Documentation

◆ FlagEnableTailMerge

cl::opt<cl::boolOrDefault> FlagEnableTailMerge("enable-tail-merge", cl::init(cl::BOU_UNSET), cl::Hidden)
static

◆ TailMergeSize

cl::opt<unsigned> TailMergeSize("tail-merge-size", cl::desc("Min number of instructions to consider tail merging"), cl::init(3), cl::Hidden)
static

◆ TailMergeThreshold

cl::opt<unsigned> TailMergeThreshold("tail-merge-threshold", cl::desc("Max number of predecessors to consider tail merging"), cl::init(150), cl::Hidden)
static

Referenced by mergeOperations().