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/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 <algorithm>

Include dependency graph for BranchFolding.cpp:

Go to the source code of this file.

Macros
#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. 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)
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)

Macro Definition 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 305 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 502 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 438 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 1461 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 1480 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 458 of file BranchFolding.cpp.

References llvm::TargetInstrInfo::AnalyzeBranch(), llvm::SmallVectorBase::empty(), llvm::MachineFunction::end(), llvm::MachineBasicBlock::getParent(), I, llvm::TargetInstrInfo::InsertBranch(), llvm::next(), 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 1044 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 286 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 253 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 81 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 1016 of file BranchFolding.cpp.

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

static bool IsBranchOnlyBlock ( MachineBasicBlock *  MBB )

static

Definition at line 1003 of file BranchFolding.cpp.

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

static bool IsEmptyBlock ( MachineBasicBlock *  MBB )

static

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

References llvm::MachineBasicBlock::back(), llvm::MachineBasicBlock::begin(), ComputeCommonTailLength(), CountTerminators(), llvm::dbgs(), DEBUG, 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