BranchFolding.cpp File Reference

#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>

Include dependency graph for BranchFolding.cpp:

Go to the source code of this file.

Defines

#define DEBUG_TYPE "branchfolding"

Functions

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

STATISTIC (NumBranchOpts,"Number of branches optimized")

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

FunctionPass * llvm::createBranchFoldingPass (bool DefaultEnableTailMerge)

static unsigned HashMachineInstr (const MachineInstr *MI)

HashMachineInstr - Compute a hash value for MI and its operands.

static unsigned HashEndOfMBB (const MachineBasicBlock *MBB, unsigned minCommonTailLength)

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

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

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

static bool MergeCompare (const std::pair< unsigned, MachineBasicBlock * > &p, const std::pair< unsigned, MachineBasicBlock * > &q)

static bool IsBetterFallthrough (MachineBasicBlock *MBB1, MachineBasicBlock *MBB2)

Variables

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

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

Define Documentation

#define DEBUG_TYPE "branchfolding"

Definition at line 19 of file BranchFolding.cpp.

Function Documentation

static unsigned ComputeCommonTailLength	(	MachineBasicBlock *	MBB1,
		MachineBasicBlock *	MBB2,
		MachineBasicBlock::iterator &	I1,
		MachineBasicBlock::iterator &	I2
	)			`[static]`

ComputeCommonTailLength - Given two machine basic blocks, compute the number of instructions they actually have in common together at their end. Return iterators for the first shared instruction in each block.

Definition at line 326 of file BranchFolding.cpp.

References llvm::MachineBasicBlock::begin(), llvm::MachineBasicBlock::end(), and llvm::TargetInstrInfo::INLINEASM.

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 410 of file BranchFolding.cpp.

References llvm::TargetInstrDesc::isCall(), llvm::TargetInstrDesc::mayLoad(), and llvm::TargetInstrDesc::mayStore().

static void FixTail	(	MachineBasicBlock *	CurMBB,
		MachineBasicBlock *	SuccBB,
		const TargetInstrInfo *	TII
	)			`[static]`

Definition at line 430 of file BranchFolding.cpp.

References llvm::TargetInstrInfo::AnalyzeBranch(), llvm::SmallVectorImpl< T >::empty(), llvm::MachineFunction::end(), llvm::MachineBasicBlock::getParent(), llvm::TargetInstrInfo::InsertBranch(), llvm::next(), llvm::TargetInstrInfo::RemoveBranch(), and llvm::TargetInstrInfo::ReverseBranchCondition().

static unsigned HashEndOfMBB	(	const MachineBasicBlock *	MBB,
		unsigned	minCommonTailLength
	)			`[static]`

HashEndOfMBB - Hash the last few instructions in the MBB. For blocks with no successors, we hash two instructions, because cross-jumping only saves code when at least two instructions are removed (since a branch must be inserted). For blocks with a successor, one of the two blocks to be tail-merged will end with a branch already, so it gains to cross-jump even for one instruction.

Definition at line 305 of file BranchFolding.cpp.

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

static unsigned HashMachineInstr ( const MachineInstr * MI ) [static]

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 856 of file BranchFolding.cpp.

References llvm::MachineBasicBlock::empty(), llvm::MachineBasicBlock::end(), llvm::MachineInstr::getDesc(), llvm::TargetInstrDesc::isCall(), and llvm::MachineBasicBlock::isSuccessor().

static bool MergeCompare	(	const std::pair< unsigned, MachineBasicBlock * > &	p,
		const std::pair< unsigned, MachineBasicBlock * > &	q
	)			`[static]`

Definition at line 450 of file BranchFolding.cpp.

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

STATISTIC	(	NumBranchOpts	,
		"Number of branches optimized"
	)

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

Variable Documentation

bool EnableTailMerge

Definition at line 66 of file BranchFolding.cpp.

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

char ID [static]

Definition at line 49 of file BranchFolding.cpp.

bool MadeChange

Definition at line 63 of file BranchFolding.cpp.

Referenced by llvm::MachineBasicBlock::CorrectExtraCFGEdges(), llvm::TargetInstrInfoImpl::PredicateInstruction(), llvm::MachineJumpTableInfo::ReplaceMBBInJumpTables(), llvm::DebugLabelFolder::runOnMachineFunction(), and llvm::SplitCriticalEdge().

std::vector<MergePotentialsElt> MergePotentials

Definition at line 82 of file BranchFolding.cpp.

MachineModuleInfo* MMI

Definition at line 62 of file BranchFolding.cpp.

Referenced by llvm::AsmPrinter::doInitialization(), llvm::X86RegisterInfo::emitFrameMoves(), llvm::XCoreRegisterInfo::emitPrologue(), llvm::X86RegisterInfo::emitPrologue(), llvm::SPURegisterInfo::emitPrologue(), llvm::PPCRegisterInfo::emitPrologue(), llvm::X86RegisterInfo::getCalleeSavedRegClasses(), llvm::X86RegisterInfo::getCalleeSavedRegs(), llvm::X86RegisterInfo::hasFP(), llvm::SelectionDAG::init(), llvm::SelectionDAG::isVerifiedDebugInfoDesc(), llvm::XCoreRegisterInfo::needsFrameMoves(), llvm::SelectionDAGISel::runOnFunction(), llvm::DebugLabelFolder::runOnMachineFunction(), and llvm::XCoreInstrInfo::spillCalleeSavedRegisters().

const TargetRegisterInfo* RegInfo

Definition at line 87 of file BranchFolding.cpp.

Referenced by llvm::X86InstrInfo::convertToThreeAddress(), llvm::X86InstrInfo::getGlobalBaseReg(), llvm::SelectionDAGLowering::GetRegistersForValue(), llvm::SparcTargetLowering::LowerArguments(), LowerCTPOP(), LowerFORMAL_ARGUMENT(), LowerFORMAL_ARGUMENTS(), LowerLOAD(), LowerSTORE(), and LowerVECTOR_SHUFFLE().

RegScavenger* RS

Definition at line 88 of file BranchFolding.cpp.

std::vector<SameTailElt> SameTails

Definition at line 85 of file BranchFolding.cpp.

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

const TargetInstrInfo* TII

Definition at line 61 of file BranchFolding.cpp.


Defines
#define	DEBUG_TYPE "branchfolding"
Functions
	STATISTIC (NumDeadBlocks,"Number of dead blocks removed")
	STATISTIC (NumBranchOpts,"Number of branches optimized")
	STATISTIC (NumTailMerge,"Number of block tails merged")
FunctionPass *	llvm::createBranchFoldingPass (bool DefaultEnableTailMerge)
static unsigned	HashMachineInstr (const MachineInstr *MI)
	HashMachineInstr - Compute a hash value for MI and its operands.
static unsigned	HashEndOfMBB (const MachineBasicBlock *MBB, unsigned minCommonTailLength)
static unsigned	ComputeCommonTailLength (MachineBasicBlock MBB1, MachineBasicBlock MBB2, MachineBasicBlock::iterator &I1, MachineBasicBlock::iterator &I2)
static unsigned	EstimateRuntime (MachineBasicBlock::iterator I, MachineBasicBlock::iterator E)
static void	FixTail (MachineBasicBlock CurMBB, MachineBasicBlock SuccBB, const TargetInstrInfo *TII)
static bool	MergeCompare (const std::pair< unsigned, MachineBasicBlock * > &p, const std::pair< unsigned, MachineBasicBlock * > &q)
static bool	IsBetterFallthrough (MachineBasicBlock MBB1, MachineBasicBlock MBB2)
Variables
static cl::opt< cl::boolOrDefault >	FlagEnableTailMerge ("enable-tail-merge", cl::init(cl::BOU_UNSET), cl::Hidden)
static cl::opt< unsigned >	TailMergeThreshold ("tail-merge-threshold", cl::desc("Max number of predecessors to consider tail merging"), cl::init(150), cl::Hidden)