IfConversion.cpp File Reference

#include "BranchFolding.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopeExit.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/SparseSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/iterator_range.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/MachineModuleInfo.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetLowering.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSchedule.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/Pass.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 <algorithm>
#include <cassert>
#include <functional>
#include <iterator>
#include <memory>
#include <utility>
#include <vector>

Include dependency graph for IfConversion.cpp:

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "if-converter"

Functions
	STATISTIC (NumSimple, "Number of simple if-conversions performed")
	STATISTIC (NumSimpleFalse, "Number of simple (F) if-conversions performed")
	STATISTIC (NumTriangle, "Number of triangle if-conversions performed")
	STATISTIC (NumTriangleRev, "Number of triangle (R) if-conversions performed")
	STATISTIC (NumTriangleFalse,"Number of triangle (F) if-conversions performed")
	STATISTIC (NumTriangleFRev, "Number of triangle (F/R) if-conversions performed")
	STATISTIC (NumDiamonds, "Number of diamond if-conversions performed")
	STATISTIC (NumForkedDiamonds, "Number of forked-diamond if-conversions performed")
	STATISTIC (NumIfConvBBs, "Number of if-converted blocks")
	STATISTIC (NumDupBBs, "Number of duplicated blocks")
	STATISTIC (NumUnpred, "Number of true blocks of diamonds unpredicated")
static MachineBasicBlock *	findFalseBlock (MachineBasicBlock *BB, MachineBasicBlock *TrueBB)
	BB has a fallthrough. Find its 'false' successor given its 'true' successor. More...
static MachineBasicBlock *	getNextBlock (MachineBasicBlock &MBB)
	Returns the next block in the function blocks ordering. More...
static void	verifySameBranchInstructions (MachineBasicBlock *MBB1, MachineBasicBlock *MBB2)
static bool	canFallThroughTo (MachineBasicBlock &MBB, MachineBasicBlock &ToMBB)
	Returns true either if ToMBB is the next block after MBB or that all the intervening blocks are empty (given MBB can fall through to its next block). More...
static void	InsertUncondBranch (MachineBasicBlock &MBB, MachineBasicBlock &ToMBB, const TargetInstrInfo *TII)
	Inserts an unconditional branch from MBB to ToMBB. More...
static void	UpdatePredRedefs (MachineInstr &MI, LivePhysRegs &Redefs)
	Behaves like LiveRegUnits::StepForward() but also adds implicit uses to all values defined in MI which are also live/used by MI. More...
static bool	MaySpeculate (const MachineInstr &MI, SmallSet< MCPhysReg, 4 > &LaterRedefs)

Variables
static cl::opt< int >	IfCvtFnStart ("ifcvt-fn-start", cl::init(-1), cl::Hidden)
static cl::opt< int >	IfCvtFnStop ("ifcvt-fn-stop", cl::init(-1), cl::Hidden)
static cl::opt< int >	IfCvtLimit ("ifcvt-limit", cl::init(-1), cl::Hidden)
static cl::opt< bool >	DisableSimple ("disable-ifcvt-simple", cl::init(false), cl::Hidden)
static cl::opt< bool >	DisableSimpleF ("disable-ifcvt-simple-false", cl::init(false), cl::Hidden)
static cl::opt< bool >	DisableTriangle ("disable-ifcvt-triangle", cl::init(false), cl::Hidden)
static cl::opt< bool >	DisableTriangleR ("disable-ifcvt-triangle-rev", cl::init(false), cl::Hidden)
static cl::opt< bool >	DisableTriangleF ("disable-ifcvt-triangle-false", cl::init(false), cl::Hidden)
static cl::opt< bool >	DisableTriangleFR ("disable-ifcvt-triangle-false-rev", cl::init(false), cl::Hidden)
static cl::opt< bool >	DisableDiamond ("disable-ifcvt-diamond", cl::init(false), cl::Hidden)
static cl::opt< bool >	DisableForkedDiamond ("disable-ifcvt-forked-diamond", cl::init(false), cl::Hidden)
static cl::opt< bool >	IfCvtBranchFold ("ifcvt-branch-fold", cl::init(true), cl::Hidden)

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "if-converter"

Definition at line 57 of file IfConversion.cpp.

Function Documentation

canFallThroughTo()

static bool canFallThroughTo ( MachineBasicBlock &  MBB, MachineBasicBlock &  ToMBB  )

static

Returns true either if ToMBB is the next block after MBB or that all the intervening blocks are empty (given MBB can fall through to its next block).

Definition at line 1325 of file IfConversion.cpp.

References E, llvm::MachineFunction::end(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::MachineBasicBlock::getParent(), I, and llvm::MachineBasicBlock::predecessors().

Referenced by UpdatePredRedefs().

findFalseBlock()

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

static

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

Definition at line 509 of file IfConversion.cpp.

References llvm::TargetInstrInfo::insertBranch(), llvm::TargetInstrInfo::removeBranch(), llvm::TargetInstrInfo::reverseBranchCondition(), llvm::MachineBasicBlock::successors(), and std::swap().

Referenced by verifySameBranchInstructions().

getNextBlock()

static MachineBasicBlock* getNextBlock ( MachineBasicBlock &  MBB )

inlinestatic

Returns the next block in the function blocks ordering.

If it is the end, returns NULL.

Definition at line 533 of file IfConversion.cpp.

References llvm::TargetInstrInfo::DefinesPredicate(), E, llvm::MachineFunction::end(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::MachineBasicBlock::getParent(), llvm::MachineInstrBundleIterator< Ty, IsReverse >::getReverse(), I, llvm::TargetInstrInfo::isProfitableToDupForIfCvt(), Size, llvm::skipDebugInstructionsForward(), and llvm::MachineBasicBlock::succ_empty().

Referenced by MaySpeculate(), UpdatePredRedefs(), and verifySameBranchInstructions().

InsertUncondBranch()

static void InsertUncondBranch ( MachineBasicBlock &  MBB, MachineBasicBlock &  ToMBB, const TargetInstrInfo *  TII  )

static

Inserts an unconditional branch from MBB to ToMBB.

Definition at line 1354 of file IfConversion.cpp.

References llvm::TargetInstrInfo::insertBranch().

Referenced by UpdatePredRedefs().

MaySpeculate()

static bool MaySpeculate ( const MachineInstr &  MI, SmallSet< MCPhysReg, 4 > &  LaterRedefs  )

static

Definition at line 1978 of file IfConversion.cpp.

References assert(), llvm::SmallVectorTemplateCommon< T >::begin(), llvm::MachineBasicBlock::begin(), llvm::MachineFunction::CloneMachineInstr(), llvm::SmallSet< T, N, C >::count(), llvm::dbgs(), E, llvm::SmallVectorTemplateCommon< T >::end(), llvm::MachineBasicBlock::end(), llvm::find(), llvm::MachineBranchProbabilityInfo::getEdgeProbability(), llvm::MachineBasicBlock::getFirstTerminator(), getNextBlock(), llvm::MachineBasicBlock::getParent(), llvm::TargetInstrInfo::getPredicationCost(), llvm::BranchProbability::getZero(), llvm::MachineBasicBlock::hasAddressTaken(), I, llvm::MachineInstr::isDebugInstr(), llvm::TargetInstrInfo::isPredicated(), llvm::MachineInstr::isSafeToMove(), llvm_unreachable, llvm::make_range(), MI, llvm::MachineBasicBlock::moveAfter(), llvm::MachineInstr::operands(), llvm::TargetInstrInfo::PredicateInstruction(), llvm::MachineFunction::rbegin(), Reg, llvm::MachineBasicBlock::removeSuccessor(), llvm::MachineBasicBlock::succ_begin(), llvm::MachineBasicBlock::succ_end(), and UpdatePredRedefs().

STATISTIC() [1/11]

STATISTIC	(	NumSimple	,
		"Number of simple if-conversions performed"
	)

STATISTIC() [2/11]

STATISTIC	(	NumSimpleFalse	,
		"Number of simple (F) if-conversions performed"
	)

STATISTIC() [3/11]

STATISTIC	(	NumTriangle	,
		"Number of triangle if-conversions performed"
	)

STATISTIC() [4/11]

STATISTIC	(	NumTriangleRev	,
		"Number of triangle (R) if-conversions performed"
	)

STATISTIC() [5/11]

STATISTIC	(	NumTriangleFalse	,
		"Number of triangle (F) if-conversions performed"
	)

STATISTIC() [6/11]

STATISTIC	(	NumTriangleFRev	,
		"Number of triangle (F/R) if-conversions performed"
	)

STATISTIC() [7/11]

STATISTIC	(	NumDiamonds	,
		"Number of diamond if-conversions performed"
	)

STATISTIC() [8/11]

STATISTIC	(	NumForkedDiamonds	,
		"Number of forked-diamond if-conversions performed"
	)

STATISTIC() [9/11]

STATISTIC	(	NumIfConvBBs	,
		"Number of if-converted blocks"
	)

STATISTIC() [10/11]

STATISTIC	(	NumDupBBs	,
		"Number of duplicated blocks"
	)

STATISTIC() [11/11]

STATISTIC	(	NumUnpred	,
		"Number of true blocks of diamonds unpredicated"
	)

UpdatePredRedefs()

static void UpdatePredRedefs ( MachineInstr &  MI, LivePhysRegs &  Redefs  )

static

Behaves like LiveRegUnits::StepForward() but also adds implicit uses to all values defined in MI which are also live/used by MI.

Definition at line 1363 of file IfConversion.cpp.

References llvm::LivePhysRegs::addLiveIns(), llvm::MachineInstrBuilder::addReg(), assert(), llvm::MachineBasicBlock::begin(), canFallThroughTo(), llvm::SmallSet< T, N, C >::count(), llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::count(), llvm::RegState::Define, llvm::NVPTXISD::Dummy, llvm::MachineBasicBlock::empty(), llvm::MachineBasicBlock::end(), llvm::MachineBasicBlock::erase(), llvm::find(), llvm::MachineBranchProbabilityInfo::getEdgeProbability(), llvm::MachineBasicBlock::getFirstNonDebugInstr(), llvm::MachineBasicBlock::getFirstTerminator(), llvm::MachineInstr::getMF(), getNextBlock(), llvm::MachineBasicBlock::getNumber(), llvm::MCRegisterInfo::getNumRegs(), llvm::BranchProbability::getOne(), llvm::MachineOperand::getParent(), llvm::TargetSubtargetInfo::getRegisterInfo(), llvm::MachineFunction::getSubtarget(), llvm::MachineBasicBlock::hasAddressTaken(), llvm::RegState::Implicit, llvm::LivePhysRegs::init(), llvm::SmallSet< T, N, C >::insert(), llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::insert(), llvm::TargetInstrInfo::insertBranch(), InsertUncondBranch(), llvm::TargetInstrInfo::isPredicated(), llvm::TargetInstrInfo::isProfitableToUnpredicate(), llvm::MachineOperand::isRegMask(), llvm::MCRegisterInfo::DiffListIterator::isValid(), Kind, llvm_unreachable, llvm::make_range(), MI, llvm::MachineBasicBlock::pred_begin(), llvm::MachineBasicBlock::pred_size(), llvm::MachineBasicBlock::predecessors(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), Reg, llvm::TargetInstrInfo::removeBranch(), llvm::TargetInstrInfo::reverseBranchCondition(), llvm::SparseSet< ValueT, KeyFunctorT, SparseT >::setUniverse(), llvm::LivePhysRegs::stepForward(), std::swap(), llvm::MachineRegisterInfo::tracksLiveness(), and verifySameBranchInstructions().

Referenced by MaySpeculate().

verifySameBranchInstructions()

static void verifySameBranchInstructions ( MachineBasicBlock *  MBB1, MachineBasicBlock *  MBB2  )

static

Definition at line 726 of file IfConversion.cpp.

References llvm::TargetInstrInfo::analyzeBranch(), assert(), findFalseBlock(), getNextBlock(), llvm::make_scope_exit(), llvm::MachineBasicBlock::rbegin(), llvm::MachineBasicBlock::rend(), llvm::TargetInstrInfo::reverseBranchCondition(), and llvm::skipDebugInstructionsForward().

Referenced by UpdatePredRedefs().

Variable Documentation

DisableDiamond

cl::opt<bool> DisableDiamond("disable-ifcvt-diamond", cl::init(false), cl::Hidden)

static

DisableForkedDiamond

cl::opt<bool> DisableForkedDiamond("disable-ifcvt-forked-diamond", cl::init(false), cl::Hidden)

static

DisableSimple

cl::opt<bool> DisableSimple("disable-ifcvt-simple", cl::init(false), cl::Hidden)

static

DisableSimpleF

cl::opt<bool> DisableSimpleF("disable-ifcvt-simple-false", cl::init(false), cl::Hidden)

static

DisableTriangle

cl::opt<bool> DisableTriangle("disable-ifcvt-triangle", cl::init(false), cl::Hidden)

static

DisableTriangleF

cl::opt<bool> DisableTriangleF("disable-ifcvt-triangle-false", cl::init(false), cl::Hidden)

static

DisableTriangleFR

cl::opt<bool> DisableTriangleFR("disable-ifcvt-triangle-false-rev", cl::init(false), cl::Hidden)

static

DisableTriangleR

cl::opt<bool> DisableTriangleR("disable-ifcvt-triangle-rev", cl::init(false), cl::Hidden)

static

IfCvtBranchFold

cl::opt<bool> IfCvtBranchFold("ifcvt-branch-fold", cl::init(true), cl::Hidden)

static

IfCvtFnStart

cl::opt<int> IfCvtFnStart("ifcvt-fn-start", cl::init(-1), cl::Hidden)

static

IfCvtFnStop

cl::opt<int> IfCvtFnStop("ifcvt-fn-stop", cl::init(-1), cl::Hidden)

static

IfCvtLimit

cl::opt<int> IfCvtLimit("ifcvt-limit", cl::init(-1), cl::Hidden)

static