LLVM  6.0.0svn
Namespaces | Macros | Functions | Variables
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.

Namespaces

 llvm
 Compute iterated dominance frontiers using a linear time algorithm.
 

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")
 
void llvm::initializeX86CmovConverterPassPass (PassRegistry &)
 
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< boolEnableCmovConverter ("x86-cmov-converter", cl::desc("Enable the X86 cmov-to-branch optimization."), cl::init(true), cl::Hidden)
 
static cl::opt< unsignedGainCycleThreshold ("x86-cmov-converter-threshold", cl::desc("Minimum gain per loop (in cycles) threshold."), cl::init(4), cl::Hidden)
 
static cl::opt< boolForceMemOperand ("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

◆ getDepthOfOptCmov()

static unsigned getDepthOfOptCmov ( unsigned  TrueOpDepth,
unsigned  FalseOpDepth 
)
static

◆ 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 602 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, 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::MachineInstr::getParent(), llvm::MachineBasicBlock::getParent(), I, INITIALIZE_PASS_BEGIN(), INITIALIZE_PASS_DEPENDENCY, llvm::MachineBasicBlock::insert(), llvm::MachineFunction::insert(), llvm::MachineBasicBlock::insertAfter(), llvm::MachineInstr::mayLoad(), MI, MRI, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::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 863 of file X86CmovConversion.cpp.

Referenced by emitSETCC().

◆ DEBUG_TYPE

DEBUG_TYPE

Definition at line 863 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 863 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().