InstCombineCompares.cpp File Reference

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

Include dependency graph for InstCombineCompares.cpp:

Go to the source code of this file.

Functions
static ConstantInt *	getOne (Constant *C)
static Constant *	AddOne (Constant *C)
	AddOne - Add one to a ConstantInt. More...
static Constant *	SubOne (Constant *C)
	SubOne - Subtract one from a ConstantInt. More...
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 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 descision 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. More...

Function Documentation

static Constant* AddOne ( Constant *  C )

static

AddOne - Add one to a ConstantInt.

Definition at line 32 of file InstCombineCompares.cpp.

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

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

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 57 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 177 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 201 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 2007 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 514 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(), llvm::ConstantInt::isZero(), and TD.

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

static ConstantInt* ExtractElement ( Constant *  V, Constant *  Idx  )

static

Definition at line 40 of file InstCombineCompares.cpp.

References llvm::ConstantExpr::getExtractElement().

Referenced by AddWithOverflow(), llvm::ExtractElementInst::classof(), collectFailStats(), llvm::ConstantFoldInstOperands(), llvm::ConstantCreator< ConstantExpr, Type, ExprMapKeyType >::create(), llvm::ConstantExpr::getAsInstruction(), llvm::ConstantExpr::getExtractElement(), llvm::objcarc::GetInstructionClass(), llvm::Instruction::getOpcodeName(), llvm::ConstantExpr::getWithOperands(), llvm::TargetLoweringBase::InstructionOpcodeToISD(), SubWithOverflow(), WriteConstants(), and WriteInstruction().

static ConstantInt* getOne ( Constant *  C )

static

Definition at line 27 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 44 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 78 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 169 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 117 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 145 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 1975 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(), llvm::IRBuilderBase::SetInsertPoint(), and llvm::Intrinsic::uadd_with_overflow.

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 1893 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::Intrinsic::sadd_with_overflow, llvm::IRBuilderBase::SetInsertPoint(), llvm::Value::use_begin(), and llvm::Value::use_end().

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

static Constant* SubOne ( Constant *  C )

static

SubOne - Subtract one from a ConstantInt.

Definition at line 36 of file InstCombineCompares.cpp.

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

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

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 92 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 descision 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 2049 of file InstCombineCompares.cpp.

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

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