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/InitializePasses.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 "llvm/Target/CGPassBuilderOption.h"
#include <algorithm>
#include <cassert>
#include <iterator>
#include <utility>

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.
	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)
static cl::opt< bool >	ForceAll ("x86-cmov-converter-force-all", cl::desc("Convert all cmovs to branches."), cl::init(false), 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 78 of file X86CmovConversion.cpp.

Function Documentation

checkEFLAGSLive()

static bool checkEFLAGSLive ( MachineInstr *  MI )

static

Definition at line 584 of file X86CmovConversion.cpp.

References llvm::MachineBasicBlock::end(), I, MI, and llvm::MachineBasicBlock::successors().

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 385 of file X86CmovConversion.cpp.

References llvm::divideCeil().

INITIALIZE_PASS_BEGIN()

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

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 613 of file X86CmovConversion.cpp.

References assert(), llvm::X86::COND_INVALID, llvm::First, llvm::X86::getCondFromCMov(), I, llvm::MachineBasicBlock::insertAfter(), llvm::Last, MBB, MI, and llvm::SmallVectorTemplateBase< T, bool >::push_back().

STATISTIC() [1/4]

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

STATISTIC() [2/4]

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

STATISTIC() [3/4]

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

STATISTIC() [4/4]

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

Variable Documentation

Conversion

X86 cmov Conversion

Definition at line 893 of file X86CmovConversion.cpp.

Referenced by performVectorTruncZeroCombine().

DEBUG_TYPE

DEBUG_TYPE

Definition at line 893 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) ( "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 894 of file X86CmovConversion.cpp.

ForceAll

cl::opt< bool > ForceAll("x86-cmov-converter-force-all", cl::desc("Convert all cmovs to branches."), cl::init(false), cl::Hidden) ( "x86-cmov-converter-force-all"  , cl::desc("Convert all cmovs to branches.")  , cl::init(false)  , cl::Hidden    )

static

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) ( "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) ( "x86-cmov-converter-threshold"  , cl::desc("Minimum gain per loop (in cycles) threshold.")  , cl::init(4)  , cl::Hidden    )

static