X86CmovConversion.cpp File Reference

This file implements a pass that converts X86 cmov instructions into branches when profitable. More...

#include "X86.h"
#include "X86InstrInfo.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSchedule.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/MC/MCSchedule.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <iterator>
#include <utility>

Include dependency graph for X86CmovConversion.cpp:

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "x86-cmov-conversion"

Functions
	STATISTIC (NumOfSkippedCmovGroups, "Number of unsupported CMOV-groups")
	STATISTIC (NumOfCmovGroupCandidate, "Number of CMOV-group candidates")
	STATISTIC (NumOfLoopCandidate, "Number of CMOV-conversion profitable loops")
	STATISTIC (NumOfOptimizedCmovGroups, "Number of optimized CMOV-groups")
static unsigned	getDepthOfOptCmov (unsigned TrueOpDepth, unsigned FalseOpDepth)
static bool	checkEFLAGSLive (MachineInstr *MI)
static void	packCmovGroup (MachineInstr *First, MachineInstr *Last)
	Given /p First CMOV instruction and /p Last CMOV instruction representing a group of CMOV instructions, which may contain debug instructions in between, move all debug instructions to after the last CMOV instruction, making the CMOV group consecutive. More...
	INITIALIZE_PASS_BEGIN (X86CmovConverterPass, DEBUG_TYPE, "X86 cmov Conversion", false, false) INITIALIZE_PASS_END(X86CmovConverterPass

Variables
static cl::opt< bool >	EnableCmovConverter ("x86-cmov-converter", cl::desc("Enable the X86 cmov-to-branch optimization."), cl::init(true), cl::Hidden)
static cl::opt< unsigned >	GainCycleThreshold ("x86-cmov-converter-threshold", cl::desc("Minimum gain per loop (in cycles) threshold."), cl::init(4), cl::Hidden)
static cl::opt< bool >	ForceMemOperand ("x86-cmov-converter-force-mem-operand", cl::desc("Convert cmovs to branches whenever they have memory operands."), cl::init(true), cl::Hidden)
	DEBUG_TYPE
X86 cmov	Conversion
X86 cmov	false

Detailed Description

This file implements a pass that converts X86 cmov instructions into branches when profitable.

This pass is conservative. It transforms if and only if it can guarantee a gain with high confidence.

Thus, the optimization applies under the following conditions:

1. Consider as candidates only CMOVs in innermost loops (assume that most hotspots are represented by these loops).
2. Given a group of CMOV instructions that are using the same EFLAGS def instruction: a. Consider them as candidates only if all have the same code condition or the opposite one to prevent generating more than one conditional jump per EFLAGS def instruction. b. Consider them as candidates only if all are profitable to be converted (assume that one bad conversion may cause a degradation).
3. Apply conversion only for loops that are found profitable and only for CMOV candidates that were found profitable. a. A loop is considered profitable only if conversion will reduce its depth cost by some threshold. b. CMOV is considered profitable if the cost of its condition is higher than the average cost of its true-value and false-value by 25% of branch-misprediction-penalty. This assures no degradation even with 25% branch misprediction.

Note: This pass is assumed to run on SSA machine code.

Definition in file X86CmovConversion.cpp.

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "x86-cmov-conversion"

Definition at line 77 of file X86CmovConversion.cpp.

Referenced by packCmovGroup().

Function Documentation

checkEFLAGSLive()

static bool checkEFLAGSLive ( MachineInstr *  MI )

static

Definition at line 566 of file X86CmovConversion.cpp.

References E, llvm::MachineBasicBlock::end(), llvm::MachineInstr::getParent(), I, llvm::MachineInstr::killsRegister(), MI, llvm::MachineBasicBlock::succ_begin(), and llvm::MachineBasicBlock::succ_end().

Referenced by packCmovGroup().

getDepthOfOptCmov()

static unsigned getDepthOfOptCmov ( unsigned  TrueOpDepth, unsigned  FalseOpDepth  )

static

Returns

Depth of CMOV instruction as if it was converted into branch.

Parameters

TrueOpDepth	depth cost of CMOV true value operand.
FalseOpDepth	depth cost of CMOV false value operand.

Definition at line 367 of file X86CmovConversion.cpp.

References llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::clear(), llvm::SmallPtrSetImpl< PtrType >::count(), DefMI, llvm::Depth, GainCycleThreshold, I, Info, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::TargetRegisterInfo::isVirtualRegister(), llvm::Latency, llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), llvm::max(), MaxDepth, MI, MRI, Reg, and std::swap().

INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	X86CmovConverterPass	,
		DEBUG_TYPE	,
		"X86 cmov Conversion"	,
		false	,
		false
	)

Referenced by packCmovGroup().

packCmovGroup()

static void packCmovGroup ( MachineInstr *  First, MachineInstr *  Last  )

static

Given /p First CMOV instruction and /p Last CMOV instruction representing a group of CMOV instructions, which may contain debug instructions in between, move all debug instructions to after the last CMOV instruction, making the CMOV group consecutive.

Definition at line 596 of file X86CmovConversion.cpp.

References llvm::MachineBasicBlock::addLiveIn(), llvm::MachineInstrBuilder::addMBB(), llvm::MachineInstrBuilder::addReg(), llvm::MachineBasicBlock::addSuccessor(), llvm::any_of(), assert(), llvm::SmallVectorTemplateCommon< T, typename >::back(), llvm::MachineBasicBlock::begin(), llvm::BuildMI(), checkEFLAGSLive(), llvm::X86::COND_INVALID, llvm::MachineFunction::CreateMachineBasicBlock(), llvm::dbgs(), DEBUG_TYPE, llvm::MachineInstr::dump(), E, llvm::SmallVectorBase::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::MachineBasicBlock::end(), llvm::MachineBasicBlock::erase(), F(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::SmallVectorTemplateCommon< T, typename >::front(), llvm::MachineBasicBlock::getBasicBlock(), llvm::X86::GetCondBranchFromCond(), llvm::X86::getCondFromCMovOpc(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::MachineInstr::getOpcode(), llvm::X86::GetOppositeBranchCondition(), llvm::MachineBasicBlock::getParent(), llvm::MachineInstr::getParent(), I, INITIALIZE_PASS_BEGIN(), INITIALIZE_PASS_DEPENDENCY, llvm::MachineBasicBlock::insert(), llvm::MachineFunction::insert(), llvm::MachineBasicBlock::insertAfter(), LLVM_DEBUG, llvm::MachineInstr::mayLoad(), MI, MRI, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::MachineBasicBlock::splice(), std::swap(), TII, and llvm::MachineBasicBlock::transferSuccessorsAndUpdatePHIs().

STATISTIC() [1/4]

STATISTIC	(	NumOfSkippedCmovGroups	,
		"Number of unsupported CMOV-groups"
	)

STATISTIC() [2/4]

STATISTIC	(	NumOfCmovGroupCandidate	,
		"Number of CMOV-group candidates"
	)

STATISTIC() [3/4]

STATISTIC	(	NumOfLoopCandidate	,
		"Number of CMOV-conversion profitable loops"
	)

STATISTIC() [4/4]

STATISTIC	(	NumOfOptimizedCmovGroups	,
		"Number of optimized CMOV-groups"
	)

Variable Documentation

Conversion

X86 cmov Conversion

Definition at line 857 of file X86CmovConversion.cpp.

DEBUG_TYPE

DEBUG_TYPE

Definition at line 857 of file X86CmovConversion.cpp.

EnableCmovConverter

cl::opt<bool> EnableCmovConverter("x86-cmov-converter", cl::desc("Enable the X86 cmov-to-branch optimization."), cl::init(true), cl::Hidden)

static

false

X86 cmov false

Definition at line 857 of file X86CmovConversion.cpp.

ForceMemOperand

cl::opt<bool> ForceMemOperand("x86-cmov-converter-force-mem-operand", cl::desc("Convert cmovs to branches whenever they have memory operands."), cl::init(true), cl::Hidden)

static

GainCycleThreshold

cl::opt<unsigned> GainCycleThreshold("x86-cmov-converter-threshold", cl::desc("Minimum gain per loop (in cycles) threshold."), cl::init(4), cl::Hidden)

static

Referenced by getDepthOfOptCmov().