BranchFolding.cpp File Reference

#include "BranchFolding.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineJumpTableInfo.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/RegisterScavenging.h"
#include "llvm/IR/Function.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/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetSubtargetInfo.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")
	STATISTIC (NumHoist,"Number of times common instructions are hoisted")
	INITIALIZE_PASS (BranchFolderPass,"branch-folder","Control Flow Optimizer", false, false) bool BranchFolderPass
static unsigned	HashMachineInstr (const MachineInstr *MI)
	HashMachineInstr - Compute a hash value for MI and its operands.
static unsigned	HashEndOfMBB (const MachineBasicBlock *MBB)
	HashEndOfMBB - Hash the last instruction in the MBB.
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 unsigned	CountTerminators (MachineBasicBlock *MBB, MachineBasicBlock::iterator &I)
static bool	ProfitableToMerge (MachineBasicBlock *MBB1, MachineBasicBlock *MBB2, unsigned minCommonTailLength, unsigned &CommonTailLen, MachineBasicBlock::iterator &I1, MachineBasicBlock::iterator &I2, MachineBasicBlock *SuccBB, MachineBasicBlock *PredBB)
static bool	IsEmptyBlock (MachineBasicBlock *MBB)
static bool	IsBranchOnlyBlock (MachineBasicBlock *MBB)
static bool	IsBetterFallthrough (MachineBasicBlock *MBB1, MachineBasicBlock *MBB2)
static DebugLoc	getBranchDebugLoc (MachineBasicBlock &MBB)
static MachineBasicBlock *	findFalseBlock (MachineBasicBlock *BB, MachineBasicBlock *TrueBB)
static MachineBasicBlock::iterator	findHoistingInsertPosAndDeps (MachineBasicBlock *MBB, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI, SmallSet< unsigned, 4 > &Uses, SmallSet< unsigned, 4 > &Defs)
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)
static cl::opt< unsigned >	TailMergeSize ("tail-merge-size", cl::desc("Min number of instructions to consider tail merging"), cl::init(3), cl::Hidden)

---

Define Documentation

#define DEBUG_TYPE   "branchfolding"

Definition at line 43 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 320 of file BranchFolding.cpp.

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

Referenced by ProfitableToMerge().

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

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

Referenced by ProfitableToMerge().

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

References I.

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

findFalseBlock - BB has a fallthrough. Find its 'false' successor given its 'true' successor.

Definition at line 1535 of file BranchFolding.cpp.

References llvm::MachineBasicBlock::succ_begin(), and llvm::MachineBasicBlock::succ_end().

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

References llvm::MachineBasicBlock::begin(), llvm::SmallSet< T, N, C >::count(), llvm::SmallSet< T, N, C >::empty(), llvm::MachineBasicBlock::end(), llvm::SmallSet< T, N, C >::erase(), llvm::MachineBasicBlock::getFirstTerminator(), llvm::MachineOperand::getReg(), llvm::SmallSet< T, N, C >::insert(), llvm::MachineOperand::isDead(), llvm::TargetInstrInfo::isPredicated(), llvm::MachineOperand::isReg(), llvm::MachineOperand::isRegMask(), llvm::TargetInstrInfo::isUnpredicatedTerminator(), llvm::MachineOperand::isUse(), llvm::MCRegisterInfo::DiffListIterator::isValid(), and llvm::MCRegAliasIterator::isValid().

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

Definition at line 474 of file BranchFolding.cpp.

References llvm::TargetInstrInfo::AnalyzeBranch(), llvm::SmallVectorBase::empty(), llvm::MachineFunction::end(), llvm::MachineBasicBlock::getParent(), I, llvm::TargetInstrInfo::InsertBranch(), llvm::TargetInstrInfo::RemoveBranch(), and llvm::TargetInstrInfo::ReverseBranchCondition().

static DebugLoc getBranchDebugLoc

(

MachineBasicBlock &

MBB

)

[static]

getBranchDebugLoc - Find and return, if any, the DebugLoc of the branch instructions on the block. Always use the DebugLoc of the first branching instruction found unless its absent, in which case use the DebugLoc of the second if present.

Definition at line 1117 of file BranchFolding.cpp.

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

static unsigned HashEndOfMBB

(

const MachineBasicBlock *

MBB

)

[static]

HashEndOfMBB - Hash the last instruction in the MBB.

Definition at line 301 of file BranchFolding.cpp.

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

static unsigned HashMachineInstr

(

const MachineInstr *

MI

)

[static]

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

Definition at line 268 of file BranchFolding.cpp.

References llvm::MachineOperand::getImm(), llvm::MachineOperand::getIndex(), llvm::MachineOperand::getMBB(), llvm::MachineBasicBlock::getNumber(), llvm::MachineInstr::getNumOperands(), llvm::MachineOperand::getOffset(), llvm::MachineInstr::getOpcode(), llvm::MachineInstr::getOperand(), llvm::MachineOperand::getReg(), llvm::MachineOperand::getType(), llvm::MachineOperand::MO_ConstantPoolIndex, llvm::MachineOperand::MO_ExternalSymbol, llvm::MachineOperand::MO_FrameIndex, llvm::MachineOperand::MO_GlobalAddress, llvm::MachineOperand::MO_Immediate, llvm::MachineOperand::MO_JumpTableIndex, llvm::MachineOperand::MO_MachineBasicBlock, and llvm::MachineOperand::MO_Register.

Referenced by HashEndOfMBB().

INITIALIZE_PASS	(	BranchFolderPass	,
		"branch-folder"	,
		"Control Flow Optimizer"	,
		false	,
		false
	)

Definition at line 87 of file BranchFolding.cpp.

References llvm::TargetPassConfig::getEnableTailMerge(), and llvm::BranchFolder::OptimizeFunction().

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

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

static bool IsBranchOnlyBlock

(

MachineBasicBlock *

MBB

)

[static]

Definition at line 1076 of file BranchFolding.cpp.

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

static bool IsEmptyBlock

(

MachineBasicBlock *

MBB

)

[static]

Definition at line 1063 of file BranchFolding.cpp.

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

Referenced by IsBetterFallthrough().

static bool ProfitableToMerge	(	MachineBasicBlock *	MBB1,
		MachineBasicBlock *	MBB2,
		unsigned	minCommonTailLength,
		unsigned &	CommonTailLen,
		MachineBasicBlock::iterator &	I1,
		MachineBasicBlock::iterator &	I2,
		MachineBasicBlock *	SuccBB,
		MachineBasicBlock *	PredBB
	)		[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.

Definition at line 553 of file BranchFolding.cpp.

References llvm::MachineBasicBlock::back(), llvm::MachineBasicBlock::begin(), ComputeCommonTailLength(), CountTerminators(), llvm::dbgs(), DEBUG, llvm::AttributeSet::FunctionIndex, llvm::Function::getAttributes(), llvm::MachineFunction::getFunction(), llvm::MachineBasicBlock::getNumber(), llvm::MachineBasicBlock::getParent(), I, llvm::MachineInstr::isBarrier(), llvm::MachineBasicBlock::isLayoutSuccessor(), and llvm::Attribute::OptimizeForSize.

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"
	)

---

Variable Documentation

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

Referenced by llvm::BranchFolder::BranchFolder().

cl::opt<unsigned> TailMergeSize("tail-merge-size", cl::desc("Min number of instructions to consider tail merging"), cl::init(3), 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) [static]