#include "InstCombine.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/GetElementPtrTypeIterator.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Target/TargetLibraryInfo.h"

Include dependency graph for InstCombineCompares.cpp:

Defines
#define	DEBUG_TYPE "instcombine"
Functions
static ConstantInt *	getOne (Constant *C)
static ConstantInt *	ExtractElement (Constant V, Constant Idx)
static bool	HasAddOverflow (ConstantInt Result, ConstantInt In1, ConstantInt *In2, bool IsSigned)
static bool	AddWithOverflow (Constant &Result, Constant In1, Constant *In2, bool IsSigned=false)
static bool	HasSubOverflow (ConstantInt Result, ConstantInt In1, ConstantInt *In2, bool IsSigned)
static bool	SubWithOverflow (Constant &Result, Constant In1, Constant *In2, bool IsSigned=false)
static bool	isSignBitCheck (ICmpInst::Predicate pred, ConstantInt *RHS, bool &TrueIfSigned)
static bool	isSignTest (ICmpInst::Predicate &pred, const ConstantInt *RHS)
static bool	isHighOnes (const ConstantInt *CI)
static void	ComputeSignedMinMaxValuesFromKnownBits (const APInt &KnownZero, const APInt &KnownOne, APInt &Min, APInt &Max)
static void	ComputeUnsignedMinMaxValuesFromKnownBits (const APInt &KnownZero, const APInt &KnownOne, APInt &Min, APInt &Max)
static Value *	EvaluateGEPOffsetExpression (User *GEP, InstCombiner &IC)
static Instruction *	ProcessUGT_ADDCST_ADD (ICmpInst &I, Value A, Value B, ConstantInt CI2, ConstantInt CI1, InstCombiner &IC)
static Instruction *	ProcessUAddIdiom (Instruction &I, Value *OrigAddV, InstCombiner &IC)
static Instruction *	ProcessUMulZExtIdiom (ICmpInst &I, Value MulVal, Value OtherVal, InstCombiner &IC)
	Recognize and process idiom involving test for multiplication overflow.
static APInt	DemandedBitsLHSMask (ICmpInst &I, unsigned BitWidth, bool isSignCheck)
static bool	swapMayExposeCSEOpportunities (const Value Op0, const Value Op1)
	Check if the order of `Op0` and `Op1` as operand in an ICmpInst should be swapped. The decision is based on how many times these two operands are reused as subtract operands and their positions in those instructions. The rational is that several architectures use the same instruction for both subtract and cmp, thus it is better if the order of those operands match.

Define Documentation

#define DEBUG_TYPE "instcombine"

Definition at line 27 of file InstCombineCompares.cpp.

Function Documentation

static bool AddWithOverflow	(	Constant *&	Result,
		Constant *	In1,
		Constant *	In2,
		bool	IsSigned = `false`
	)		`[static]`

AddWithOverflow - Compute Result = In1+In2, returning true if the result overflowed for this type.

Definition at line 50 of file InstCombineCompares.cpp.

References ExtractElement(), llvm::ConstantInt::get(), llvm::ConstantExpr::getAdd(), llvm::Value::getContext(), llvm::Type::getInt32Ty(), llvm::Value::getType(), and HasAddOverflow().

Referenced by llvm::InstCombiner::FoldICmpDivCst().

static void ComputeSignedMinMaxValuesFromKnownBits	(	const APInt &	KnownZero,
		const APInt &	KnownOne,
		APInt &	Min,
		APInt &	Max
	)		`[static]`

ComputeSignedMinMaxValuesFromKnownBits - Given a signed integer type and a set of known zero and one bits, compute the maximum and minimum values that could have the specified known zero and known one bits, returning them in min/max.

Definition at line 170 of file InstCombineCompares.cpp.

References llvm::APInt::clearBit(), llvm::APInt::getBitWidth(), and llvm::APInt::setBit().

Referenced by llvm::InstCombiner::visitICmpInst().

static void ComputeUnsignedMinMaxValuesFromKnownBits	(	const APInt &	KnownZero,
		const APInt &	KnownOne,
		APInt &	Min,
		APInt &	Max
	)		`[static]`

Definition at line 194 of file InstCombineCompares.cpp.

References llvm::APInt::getBitWidth().

Referenced by llvm::InstCombiner::visitICmpInst().

static APInt DemandedBitsLHSMask	(	ICmpInst &	I,
		unsigned	BitWidth,
		bool	isSignCheck
	)		`[static]`

Definition at line 2357 of file InstCombineCompares.cpp.

References llvm::APInt::countTrailingOnes(), llvm::APInt::countTrailingZeros(), llvm::dyn_cast(), llvm::APInt::getAllOnesValue(), llvm::APInt::getLowBitsSet(), llvm::User::getOperand(), llvm::CmpInst::getPredicate(), llvm::APInt::getSignBit(), llvm::ConstantInt::getValue(), llvm::CmpInst::ICMP_UGT, and llvm::CmpInst::ICMP_ULT.

Referenced by llvm::InstCombiner::visitICmpInst().

static Value* EvaluateGEPOffsetExpression	(	User *	GEP,
		InstCombiner &	IC
	)		`[static]`

EvaluateGEPOffsetExpression - Return a value that can be used to compare the *offset* implied by a GEP to zero. For example, if we have &A[i], we want to return 'i' for "icmp ne i, 0". Note that, in general, indices can be complex, and scales are involved. The above expression would also be legal to codegen as "icmp ne (i*4), 0" (assuming A is a pointer to i32). This later form is less amenable to optimization though, and we are allowed to generate the first by knowing that pointer arithmetic doesn't overflow.

If we can't emit an optimized form for this expression, this returns null.

Definition at line 507 of file InstCombineCompares.cpp.

References llvm::InstCombiner::Builder, llvm::IRBuilder< preserveNames, T, Inserter >::CreateAdd(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateIntCast(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateTrunc(), llvm::dyn_cast(), llvm::gep_type_begin(), llvm::ConstantInt::get(), llvm::InstCombiner::getDataLayout(), llvm::StructLayout::getElementOffset(), llvm::generic_gep_type_iterator< ItTy >::getIndexedType(), llvm::Type::getIntegerBitWidth(), llvm::DataLayout::getIntPtrType(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::Type::getPrimitiveSizeInBits(), llvm::ConstantInt::getSExtValue(), llvm::DataLayout::getStructLayout(), llvm::Value::getType(), llvm::DataLayout::getTypeAllocSize(), llvm::ConstantInt::getZExtValue(), and llvm::ConstantInt::isZero().

Referenced by llvm::InstCombiner::FoldGEPICmp().

static ConstantInt* ExtractElement	(	Constant *	V,
		Constant *	Idx
	)		`[static]`

Definition at line 33 of file InstCombineCompares.cpp.

References llvm::ConstantExpr::getExtractElement().

Referenced by AddWithOverflow(), llvm::ExtractElementInst::classof(), collectFailStats(), ComputeSpeculationCost(), llvm::ConstantFoldInstOperands(), llvm::ConstantExprKeyType::create(), llvm::ConstantExpr::getAsInstruction(), llvm::ConstantExpr::getExtractElement(), llvm::objcarc::GetInstructionClass(), llvm::Instruction::getOpcodeName(), llvm::ConstantExpr::getWithOperands(), llvm::TargetLoweringBase::InstructionOpcodeToISD(), SubWithOverflow(), tryPromoteAllocaToVector(), WriteConstants(), and WriteInstruction().

static ConstantInt* getOne ( Constant * C ) [static]

Definition at line 29 of file InstCombineCompares.cpp.

References llvm::ConstantInt::get(), and llvm::Value::getType().

Referenced by llvm::InstCombiner::FoldICmpDivCst().

static bool HasAddOverflow	(	ConstantInt *	Result,
		ConstantInt *	In1,
		ConstantInt *	In2,
		bool	IsSigned
	)		`[static]`

Definition at line 37 of file InstCombineCompares.cpp.

References llvm::ConstantInt::getValue(), llvm::ConstantInt::isNegative(), llvm::APInt::sgt(), llvm::APInt::slt(), and llvm::APInt::ult().

Referenced by AddWithOverflow().

static bool HasSubOverflow	(	ConstantInt *	Result,
		ConstantInt *	In1,
		ConstantInt *	In2,
		bool	IsSigned
	)		`[static]`

Definition at line 71 of file InstCombineCompares.cpp.

References llvm::ConstantInt::getValue(), llvm::ConstantInt::isNegative(), llvm::APInt::sgt(), llvm::APInt::slt(), and llvm::APInt::ugt().

Referenced by SubWithOverflow().

static bool isHighOnes ( const ConstantInt * CI ) [static]

Definition at line 162 of file InstCombineCompares.cpp.

References llvm::ConstantInt::getValue().

Referenced by llvm::InstCombiner::visitICmpInstWithInstAndIntCst().

static bool isSignBitCheck	(	ICmpInst::Predicate	pred,
		ConstantInt *	RHS,
		bool &	TrueIfSigned
	)		`[static]`

isSignBitCheck - Given an exploded icmp instruction, return true if the comparison only checks the sign bit. If it only checks the sign bit, set TrueIfSigned if the result of the comparison is true when the input value is signed.

Definition at line 110 of file InstCombineCompares.cpp.

References llvm::ConstantInt::getValue(), llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_SLT, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_UGT, llvm::Constant::isAllOnesValue(), llvm::ConstantInt::isMaxValue(), llvm::APInt::isSignBit(), and llvm::ConstantInt::isZero().

Referenced by llvm::InstCombiner::visitICmpInst(), and llvm::InstCombiner::visitICmpInstWithInstAndIntCst().

static bool isSignTest	(	ICmpInst::Predicate &	pred,
		const ConstantInt *	RHS
	)		`[static]`

Returns true if the exploded icmp can be expressed as a signed comparison to zero and updates the predicate accordingly. The signedness of the comparison is preserved.

Definition at line 138 of file InstCombineCompares.cpp.

References llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_SLT, llvm::Constant::isAllOnesValue(), llvm::ConstantInt::isOne(), llvm::ICmpInst::isRelational(), llvm::CmpInst::isSigned(), and llvm::ConstantInt::isZero().

Referenced by llvm::InstCombiner::visitICmpInstWithInstAndIntCst().

static Instruction* ProcessUAddIdiom	(	Instruction &	I,
		Value *	OrigAddV,
		InstCombiner &	IC
	)		`[static]`

Definition at line 2091 of file InstCombineCompares.cpp.

References llvm::InstCombiner::Builder, llvm::Call, llvm::ExtractValueInst::Create(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateCall2(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateExtractValue(), llvm::dyn_cast(), F(), llvm::Intrinsic::getDeclaration(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::GlobalValue::getParent(), llvm::Value::getType(), llvm::InstCombiner::ReplaceInstUsesWith(), and llvm::IRBuilderBase::SetInsertPoint().

Referenced by llvm::InstCombiner::visitICmpInst().

static Instruction* ProcessUGT_ADDCST_ADD	(	ICmpInst &	I,
		Value *	A,
		Value *	B,
		ConstantInt *	CI2,
		ConstantInt *	CI1,
		InstCombiner &	IC
	)		`[static]`

ProcessUGT_ADDCST_ADD - The caller has matched a pattern of the form: I = icmp ugt (add (add A, B), CI2), CI1 If this is of the form: sum = a + b if (sum+128 >u 255) Then replace it with llvm.sadd.with.overflow.i8.

Definition at line 2010 of file InstCombineCompares.cpp.

References llvm::InstCombiner::Builder, llvm::Call, llvm::InstCombiner::ComputeNumSignBits(), llvm::APInt::countTrailingZeros(), llvm::ExtractValueInst::Create(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateCall2(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateExtractValue(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateTrunc(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateZExt(), llvm::dyn_cast(), F(), llvm::IntegerType::get(), llvm::ConstantInt::getBitWidth(), llvm::Value::getContext(), llvm::Intrinsic::getDeclaration(), llvm::APInt::getLowBitsSet(), llvm::Value::getName(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::GlobalValue::getParent(), llvm::Type::getPrimitiveSizeInBits(), llvm::Value::getType(), llvm::ConstantInt::getValue(), llvm::Value::hasOneUse(), llvm::APInt::isPowerOf2(), llvm::InstCombiner::ReplaceInstUsesWith(), llvm::IRBuilderBase::SetInsertPoint(), and llvm::Value::users().

Referenced by llvm::InstCombiner::visitICmpInst().

static Instruction* ProcessUMulZExtIdiom	(	ICmpInst &	I,
		Value *	MulVal,
		Value *	OtherVal,
		InstCombiner &	IC
	)		`[static]`

Recognize and process idiom involving test for multiplication overflow.

The caller has matched a pattern of the form: I = cmp u (mul(zext A, zext B), V The function checks if this is a test for overflow and if so replaces multiplication with call to 'mul.with.overflow' intrinsic.

Parameters:

I	Compare instruction.
MulVal	Result of 'mult' instruction. It is one of the arguments of the compare instruction. Must be of integer type.
OtherVal	The other argument of compare instruction.

Returns:: Instruction which must replace the compare instruction, NULL if no replacement required.

Definition at line 2134 of file InstCombineCompares.cpp.

References llvm::ARM_PROC::A, llvm::InstCombineWorklist::Add(), llvm::APIntOps::And(), llvm::InstCombiner::Builder, llvm::Call, llvm::APInt::countLeadingZeros(), llvm::ExtractValueInst::Create(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateAnd(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateCall2(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateExtractValue(), llvm::BinaryOperator::CreateNot(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateZExt(), llvm::APInt::eq(), F(), llvm::ConstantInt::getBitWidth(), llvm::APInt::getBitWidth(), llvm::Intrinsic::getDeclaration(), llvm::APInt::getMaxValue(), llvm::APInt::getOneBitSet(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::GlobalValue::getParent(), llvm::CmpInst::getPredicate(), llvm::Type::getPrimitiveSizeInBits(), llvm::Value::getType(), llvm::ConstantInt::getValue(), llvm::Value::hasNUsesOrMore(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULE, llvm::CmpInst::ICMP_ULT, llvm::APInt::isPowerOf2(), llvm_unreachable, llvm::APInt::logBase2(), llvm::PatternMatch::m_And(), llvm::PatternMatch::m_ConstantInt(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::InstCombiner::ReplaceInstUsesWith(), llvm::IRBuilderBase::SetInsertPoint(), llvm::User::setOperand(), llvm::Trunc, llvm::APInt::trunc(), llvm::Value::users(), llvm::InstCombiner::Worklist, and llvm::APInt::zext().

Referenced by llvm::InstCombiner::visitICmpInst().

static bool SubWithOverflow	(	Constant *&	Result,
		Constant *	In1,
		Constant *	In2,
		bool	IsSigned = `false`
	)		`[static]`

SubWithOverflow - Compute Result = In1-In2, returning true if the result overflowed for this type.

Definition at line 85 of file InstCombineCompares.cpp.

References ExtractElement(), llvm::ConstantInt::get(), llvm::Value::getContext(), llvm::Type::getInt32Ty(), llvm::ConstantExpr::getSub(), llvm::Value::getType(), and HasSubOverflow().

Referenced by llvm::InstCombiner::FoldICmpDivCst().

static bool swapMayExposeCSEOpportunities	(	const Value *	Op0,
		const Value *	Op1
	)		`[static]`

Check if the order of Op0 and Op1 as operand in an ICmpInst should be swapped. The decision is based on how many times these two operands are reused as subtract operands and their positions in those instructions. The rational is that several architectures use the same instruction for both subtract and cmp, thus it is better if the order of those operands match.

Returns:: true if Op0 and Op1 should be swapped.

Definition at line 2399 of file InstCombineCompares.cpp.

References llvm::dyn_cast(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::Value::getType(), llvm::Type::isPointerTy(), and llvm::Value::users().

Referenced by llvm::InstCombiner::visitICmpInst().

Defines

Functions

Define Documentation

Function Documentation