LLVM  6.0.0svn
Macros | Functions
InstCombineCompares.cpp File Reference
#include "InstCombineInternal.h"
#include "llvm/ADT/APSInt.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/VectorUtils.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/Support/Debug.h"
#include "llvm/Support/KnownBits.h"
Include dependency graph for InstCombineCompares.cpp:

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "instcombine"
 

Functions

 STATISTIC (NumSel, "Number of select opts")
 
static ConstantIntextractElement (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)
 Compute Result = In1+In2, returning true if the result overflowed for this type. More...
 
static bool hasSubOverflow (ConstantInt *Result, ConstantInt *In1, ConstantInt *In2, bool IsSigned)
 
static bool subWithOverflow (Constant *&Result, Constant *In1, Constant *In2, bool IsSigned=false)
 Compute Result = In1-In2, returning true if the result overflowed for this type. More...
 
static bool hasBranchUse (ICmpInst &I)
 Given an icmp instruction, return true if any use of this comparison is a branch on sign bit comparison. More...
 
static bool isSignBitCheck (ICmpInst::Predicate Pred, const APInt &RHS, bool &TrueIfSigned)
 Given an exploded icmp instruction, return true if the comparison only checks the sign bit. More...
 
static bool isSignTest (ICmpInst::Predicate &Pred, const APInt &C)
 Returns true if the exploded icmp can be expressed as a signed comparison to zero and updates the predicate accordingly. More...
 
static void computeSignedMinMaxValuesFromKnownBits (const KnownBits &Known, APInt &Min, APInt &Max)
 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. More...
 
static void computeUnsignedMinMaxValuesFromKnownBits (const KnownBits &Known, APInt &Min, APInt &Max)
 Given an unsigned 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. More...
 
static ValueevaluateGEPOffsetExpression (User *GEP, InstCombiner &IC, const DataLayout &DL)
 Return a value that can be used to compare the offset implied by a GEP to zero. More...
 
static bool canRewriteGEPAsOffset (Value *Start, Value *Base, const DataLayout &DL, SetVector< Value *> &Explored)
 Returns true if we can rewrite Start as a GEP with pointer Base and some integer offset. More...
 
static void setInsertionPoint (IRBuilder<> &Builder, Value *V, bool Before=true)
 
static ValuerewriteGEPAsOffset (Value *Start, Value *Base, const DataLayout &DL, SetVector< Value *> &Explored)
 Returns a re-written value of Start as an indexed GEP using Base as a pointer. More...
 
static std::pair< Value *, Value * > getAsConstantIndexedAddress (Value *V, const DataLayout &DL)
 Looks through GEPs, IntToPtrInsts and PtrToIntInsts in order to express the input Value as a constant indexed GEP. More...
 
static InstructiontransformToIndexedCompare (GEPOperator *GEPLHS, Value *RHS, ICmpInst::Predicate Cond, const DataLayout &DL)
 Converts (CMP GEPLHS, RHS) if this change would make RHS a constant. More...
 
static InstructionprocessUGT_ADDCST_ADD (ICmpInst &I, Value *A, Value *B, ConstantInt *CI2, ConstantInt *CI1, InstCombiner &IC)
 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. More...
 
static InstructionfoldICmpShlOne (ICmpInst &Cmp, Instruction *Shl, const APInt *C)
 Fold icmp (shl 1, Y), C. More...
 
static InstructionfoldICmpWithMinMax (ICmpInst &Cmp)
 Fold icmp Pred min|max(X, Y), X. More...
 
static InstructionprocessUMulZExtIdiom (ICmpInst &I, Value *MulVal, Value *OtherVal, InstCombiner &IC)
 Recognize and process idiom involving test for multiplication overflow. More...
 
static APInt getDemandedBitsLHSMask (ICmpInst &I, unsigned BitWidth, bool isSignCheck)
 When performing a comparison against a constant, it is possible that not all the bits in the LHS are demanded. More...
 
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. More...
 
static bool isChainSelectCmpBranch (const SelectInst *SI)
 Return true when the instruction sequence within a block is select-cmp-br. More...
 
static ICmpInstcanonicalizeCmpWithConstant (ICmpInst &I)
 If we have an icmp le or icmp ge instruction with a constant operand, turn it into the appropriate icmp lt or icmp gt instruction. More...
 
static InstructioncanonicalizeICmpBool (ICmpInst &I, InstCombiner::BuilderTy &Builder)
 Integer compare with boolean values can always be turned into bitwise ops. More...
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "instcombine"

Definition at line 34 of file InstCombineCompares.cpp.

Function Documentation

◆ addWithOverflow()

static bool addWithOverflow ( Constant *&  Result,
Constant In1,
Constant In2,
bool  IsSigned = false 
)
static

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 foldICmpShlOne().

◆ canonicalizeCmpWithConstant()

static ICmpInst* canonicalizeCmpWithConstant ( ICmpInst I)
static

◆ canonicalizeICmpBool()

static Instruction* canonicalizeICmpBool ( ICmpInst I,
InstCombiner::BuilderTy Builder 
)
static

◆ canRewriteGEPAsOffset()

static bool canRewriteGEPAsOffset ( Value Start,
Value Base,
const DataLayout DL,
SetVector< Value *> &  Explored 
)
static

◆ computeSignedMinMaxValuesFromKnownBits()

static void computeSignedMinMaxValuesFromKnownBits ( const KnownBits Known,
APInt Min,
APInt Max 
)
static

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.

TODO: Move to method on KnownBits struct?

Definition at line 180 of file InstCombineCompares.cpp.

References assert(), llvm::APInt::clearSignBit(), llvm::KnownBits::getBitWidth(), llvm::APInt::getBitWidth(), llvm::KnownBits::One, llvm::APInt::setSignBit(), and llvm::KnownBits::Zero.

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

◆ computeUnsignedMinMaxValuesFromKnownBits()

static void computeUnsignedMinMaxValuesFromKnownBits ( const KnownBits Known,
APInt Min,
APInt Max 
)
static

◆ evaluateGEPOffsetExpression()

static Value* evaluateGEPOffsetExpression ( User GEP,
InstCombiner IC,
const DataLayout DL 
)
static

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 latter 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 504 of file InstCombineCompares.cpp.

References llvm::InstCombiner::Builder, llvm::IRBuilder< T, Inserter >::CreateAdd(), llvm::IRBuilder< T, Inserter >::CreateIntCast(), llvm::IRBuilder< T, Inserter >::CreateTrunc(), llvm::dyn_cast(), llvm::gep_type_begin(), llvm::ConstantInt::get(), 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::generic_gep_type_iterator< ItTy >::getStructTypeOrNull(), llvm::Value::getType(), llvm::DataLayout::getTypeAllocSize(), llvm::ConstantInt::getZExtValue(), llvm::ConstantInt::isZero(), and llvm::AMDGPU::CodeObject::Kernel::Arg::Key::Size.

Referenced by transformToIndexedCompare().

◆ extractElement()

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

Definition at line 40 of file InstCombineCompares.cpp.

References llvm::ConstantExpr::getExtractElement().

Referenced by addWithOverflow(), and subWithOverflow().

◆ foldICmpShlOne()

static Instruction* foldICmpShlOne ( ICmpInst Cmp,
Instruction Shl,
const APInt C 
)
static

Fold icmp (shl 1, Y), C.

Definition at line 1859 of file InstCombineCompares.cpp.

References A, llvm::APInt::abs(), llvm::MCID::Add, llvm::AddOne(), addWithOverflow(), llvm::APInt::ashr(), assert(), B, llvm::APInt::byteSwap(), C, llvm::APInt::countTrailingZeros(), llvm::SelectInst::Create(), D, llvm::dyn_cast(), llvm::object::Equal, llvm::IntegerType::get(), llvm::ConstantInt::get(), llvm::VectorType::get(), llvm::Constant::getAllOnesValue(), llvm::CallInst::getArgOperand(), llvm::APInt::getBitWidth(), llvm::ConstantExpr::getCompare(), llvm::SelectInst::getCondition(), llvm::Value::getContext(), llvm::ConstantInt::getFalse(), llvm::SelectInst::getFalseValue(), llvm::APInt::getHighBitsSet(), llvm::ConstantExpr::getICmp(), llvm::IntrinsicInst::getIntrinsicID(), llvm::APInt::getLowBitsSet(), llvm::ConstantExpr::getMul(), llvm::Value::getName(), llvm::ConstantExpr::getNeg(), llvm::ConstantExpr::getNot(), llvm::Constant::getNullValue(), llvm::APInt::getOneBitSet(), llvm::Instruction::getOpcode(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::CmpInst::getPredicate(), llvm::ConstantExpr::getSDiv(), llvm::ICmpInst::getSignedPredicate(), llvm::ConstantExpr::getSub(), llvm::CmpInst::getSwappedPredicate(), llvm::ConstantInt::getTrue(), llvm::SelectInst::getTrueValue(), llvm::Value::getType(), llvm::ConstantExpr::getUDiv(), llvm::Constant::getUniqueInteger(), llvm::ICmpInst::getUnsignedPredicate(), llvm::Type::getVectorNumElements(), llvm::ConstantExpr::getXor(), llvm::GlobalVariable::hasDefinitiveInitializer(), llvm::Instruction::hasNoSignedWrap(), llvm::Instruction::hasNoUnsignedWrap(), llvm::Value::hasOneUse(), I, llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_SLT, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULE, llvm::CmpInst::ICMP_ULT, llvm::Constant::isAllOnesValue(), llvm::APInt::isAllOnesValue(), llvm::GlobalVariable::isConstant(), llvm::ICmpInst::isEquality(), llvm::Instruction::isExact(), llvm::APInt::isMaxSignedValue(), llvm::APInt::isMaxValue(), llvm::APInt::isMinSignedValue(), llvm::APInt::isMinValue(), llvm::APInt::isNegative(), llvm::Constant::isNullValue(), llvm::APInt::isNullValue(), llvm::APInt::isOneValue(), llvm::APInt::isPowerOf2(), isSignBitCheck(), llvm::CmpInst::isSigned(), llvm::APInt::isSignMask(), isSignTest(), llvm::APInt::isStrictlyPositive(), llvm::CmpInst::isUnsigned(), llvm::Type::isVectorTy(), isVolatile(), llvm::ConstantInt::isZero(), llvm::CodeGenOpt::Less, LLVM_FALLTHROUGH, llvm_unreachable, llvm::SPII::Load, llvm::APInt::logBase2(), llvm::Lower, llvm::APInt::lshr(), llvm::PatternMatch::m_Add(), llvm::PatternMatch::m_AllOnes(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_BinOp(), llvm::PatternMatch::m_c_And(), llvm::PatternMatch::m_ConstantInt(), llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_Instruction(), llvm::PatternMatch::m_Neg(), llvm::PatternMatch::m_One(), llvm::PatternMatch::m_Select(), llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), llvm::ConstantRange::makeExactICmpRegion(), llvm::BitmaskEnumDetail::Mask(), llvm::PatternMatch::match(), llvm::MCID::Select, llvm::User::setOperand(), llvm::APInt::sgt(), llvm::APInt::shl(), SI, llvm::APInt::ssub_ov(), llvm::SubOne(), llvm::ConstantRange::subtract(), subWithOverflow(), llvm::Value::takeName(), llvm::APInt::trunc(), llvm::APInt::udiv(), llvm::APInt::uge(), llvm::APInt::ugt(), llvm::Upper, X, Y, llvm::Z, and Zero.

◆ foldICmpWithMinMax()

static Instruction* foldICmpWithMinMax ( ICmpInst Cmp)
static

Fold icmp Pred min|max(X, Y), X.

Definition at line 3230 of file InstCombineCompares.cpp.

References A, llvm::AlwaysOverflows, assert(), B, C, llvm::computeOverflowForUnsignedAdd(), llvm::computeOverflowForUnsignedMul(), llvm::BinaryOperator::CreateNot(), D, llvm::dyn_cast(), llvm::UndefValue::get(), llvm::Constant::getAllOnesValue(), getBitWidth(), llvm::ConstantInt::getBitWidth(), llvm::ConstantExpr::getCast(), llvm::Type::getIntegerBitWidth(), llvm::ConstantExpr::getIntToPtr(), llvm::ConstantInt::getLimitedValue(), llvm::APInt::getLowBitsSet(), llvm::Value::getName(), llvm::Constant::getNullValue(), llvm::APInt::getOneBitSet(), llvm::CastInst::getOpcode(), llvm::User::getOperand(), llvm::Type::getPointerAddressSpace(), llvm::CmpInst::getPredicate(), llvm::Type::getPrimitiveSizeInBits(), llvm::CmpInst::getSwappedPredicate(), llvm::ConstantExpr::getTrunc(), llvm::ConstantInt::getType(), llvm::Value::getType(), llvm::ICmpInst::getUnsignedPredicate(), llvm::ConstantInt::getValue(), llvm::Value::hasOneUse(), I, llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_SLT, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULE, llvm::CmpInst::ICMP_ULT, llvm::Instruction::isCommutative(), llvm::ICmpInst::isEquality(), llvm::APInt::isPowerOf2(), llvm::CmpInst::isSigned(), LLVM_FALLTHROUGH, llvm_unreachable, llvm::APInt::logBase2(), llvm::PatternMatch::m_And(), llvm::PatternMatch::m_AShr(), llvm::PatternMatch::m_BitReverse(), llvm::PatternMatch::m_BSwap(), llvm::PatternMatch::m_c_SMax(), llvm::PatternMatch::m_c_SMin(), llvm::PatternMatch::m_c_UMax(), llvm::PatternMatch::m_c_UMin(), llvm::PatternMatch::m_ConstantInt(), llvm::PatternMatch::m_LShr(), llvm::PatternMatch::m_One(), llvm::PatternMatch::m_OneUse(), llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Trunc(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_Xor(), llvm::PatternMatch::m_Zero(), llvm::PatternMatch::m_ZExt(), llvm::BitmaskEnumDetail::Mask(), llvm::PatternMatch::match(), NC, llvm::NeverOverflows, llvm::OCF_INVALID, llvm::OCF_SIGNED_ADD, llvm::OCF_SIGNED_MUL, llvm::OCF_SIGNED_SUB, llvm::OCF_UNSIGNED_ADD, llvm::OCF_UNSIGNED_MUL, llvm::OCF_UNSIGNED_SUB, OR, llvm::User::setOperand(), std::swap(), llvm::Value::takeName(), Y, llvm::Z, and llvm::APInt::zext().

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

◆ getAsConstantIndexedAddress()

static std::pair<Value *, Value *> getAsConstantIndexedAddress ( Value V,
const DataLayout DL 
)
static

◆ getDemandedBitsLHSMask()

static APInt getDemandedBitsLHSMask ( ICmpInst I,
unsigned  BitWidth,
bool  isSignCheck 
)
static

When performing a comparison against a constant, it is possible that not all the bits in the LHS are demanded.

This helper method computes the mask that IS demanded.

Definition at line 3927 of file InstCombineCompares.cpp.

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

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

◆ hasAddOverflow()

static bool hasAddOverflow ( ConstantInt Result,
ConstantInt In1,
ConstantInt In2,
bool  IsSigned 
)
static

◆ hasBranchUse()

static bool hasBranchUse ( ICmpInst I)
static

Given an icmp instruction, return true if any use of this comparison is a branch on sign bit comparison.

Definition at line 115 of file InstCombineCompares.cpp.

References llvm::Value::users().

Referenced by processUGT_ADDCST_ADD().

◆ hasSubOverflow()

static bool hasSubOverflow ( ConstantInt Result,
ConstantInt In1,
ConstantInt In2,
bool  IsSigned 
)
static

◆ isChainSelectCmpBranch()

static bool isChainSelectCmpBranch ( const SelectInst SI)
static

Return true when the instruction sequence within a block is select-cmp-br.

Definition at line 4031 of file InstCombineCompares.cpp.

References llvm::dyn_cast(), llvm::User::getOperand(), llvm::Instruction::getParent(), and llvm::BasicBlock::getTerminator().

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

◆ isSignBitCheck()

static bool isSignBitCheck ( ICmpInst::Predicate  Pred,
const APInt RHS,
bool TrueIfSigned 
)
static

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 125 of file InstCombineCompares.cpp.

References llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_SLT, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_UGT, llvm::APInt::isAllOnesValue(), llvm::APInt::isMaxSignedValue(), llvm::APInt::isNullValue(), and llvm::APInt::isSignMask().

Referenced by foldICmpShlOne(), processUGT_ADDCST_ADD(), and llvm::InstCombiner::replacedSelectWithOperand().

◆ isSignTest()

static bool isSignTest ( ICmpInst::Predicate &  Pred,
const APInt C 
)
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. TODO: Refactor with decomposeBitTestICmp()?

Definition at line 154 of file InstCombineCompares.cpp.

References llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_SLT, llvm::APInt::isAllOnesValue(), llvm::APInt::isNullValue(), llvm::APInt::isOneValue(), llvm::ICmpInst::isRelational(), and llvm::CmpInst::isSigned().

Referenced by foldICmpShlOne(), and processUGT_ADDCST_ADD().

◆ processUGT_ADDCST_ADD()

static Instruction* processUGT_ADDCST_ADD ( ICmpInst I,
Value A,
Value B,
ConstantInt CI2,
ConstantInt CI1,
InstCombiner IC 
)
static

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 1287 of file InstCombineCompares.cpp.

References A, llvm::MCID::Add, llvm::AddOne(), B, llvm::InstCombiner::Builder, C, llvm::computeKnownBits(), llvm::InstCombiner::ComputeNumSignBits(), llvm::APInt::countTrailingZeros(), llvm::BinaryOperator::Create(), llvm::ExtractValueInst::Create(), llvm::ConstantRange::difference(), llvm::dyn_cast(), llvm::APInt::exactLogBase2(), F, llvm::SelectPatternResult::Flavor, llvm::IntegerType::get(), llvm::ConstantInt::get(), llvm::VectorType::get(), llvm::ConstantInt::getBitWidth(), llvm::APInt::getBitWidth(), llvm::Value::getContext(), llvm::Intrinsic::getDeclaration(), llvm::ConstantInt::getFalse(), llvm::APInt::getHighBitsSet(), llvm::CmpInst::getInversePredicate(), llvm::APInt::getLowBitsSet(), llvm::Instruction::getModule(), llvm::Value::getName(), llvm::Constant::getNullValue(), llvm::ConstantExpr::getNUWShl(), llvm::APInt::getOneBitSet(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::ConstantExpr::getOr(), llvm::Instruction::getParent(), llvm::CmpInst::getPredicate(), llvm::Type::getPrimitiveSizeInBits(), llvm::Type::getScalarSizeInBits(), llvm::ICmpInst::getSignedPredicate(), llvm::ConstantRange::getSingleElement(), llvm::BasicBlock::getSinglePredecessor(), llvm::CmpInst::getSwappedPredicate(), llvm::BasicBlock::getTerminator(), llvm::ConstantInt::getTrue(), llvm::Value::getType(), llvm::ICmpInst::getUnsignedPredicate(), llvm::ConstantInt::getValue(), llvm::Type::getVectorNumElements(), hasBranchUse(), llvm::GlobalVariable::hasDefinitiveInitializer(), llvm::Instruction::hasNoSignedWrap(), llvm::Value::hasOneUse(), I, llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLT, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULE, llvm::CmpInst::ICMP_ULT, llvm::ConstantRange::intersectWith(), llvm::APInt::isAllOnesValue(), llvm::Instruction::isArithmeticShift(), llvm::GlobalVariable::isConstant(), llvm::ConstantRange::isEmptySet(), llvm::ICmpInst::isEquality(), llvm::isKnownPositive(), llvm::APInt::isMaxSignedValue(), llvm::APInt::isNegative(), llvm::APInt::isNullValue(), llvm::APInt::isOneValue(), llvm::APInt::isPowerOf2(), llvm::Instruction::isShift(), isSignBitCheck(), llvm::CmpInst::isSigned(), llvm::APInt::isSignMask(), isSignTest(), llvm::Type::isVectorTy(), llvm::APInt::lshr(), llvm::PatternMatch::m_Add(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_Br(), llvm::PatternMatch::m_ConstantInt(), llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_LShr(), llvm::PatternMatch::m_One(), llvm::PatternMatch::m_OneUse(), llvm::PatternMatch::m_Or(), llvm::PatternMatch::m_PtrToInt(), llvm::PatternMatch::m_Signum(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Trunc(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_Xor(), llvm::ConstantRange::makeAllowedICmpRegion(), llvm::ConstantRange::makeExactICmpRegion(), llvm::PatternMatch::match(), llvm::matchSelectPattern(), llvm::KnownBits::One, P, llvm::InstCombiner::replaceInstUsesWith(), llvm::IRBuilderBase::SetInsertPoint(), llvm::User::setOperand(), llvm::APInt::shl(), llvm::SPF_SMIN, llvm::SubOne(), llvm::Value::users(), Y, Zero, llvm::KnownBits::Zero, and llvm::APInt::zext().

◆ processUMulZExtIdiom()

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
ICompare instruction.
MulValResult of 'mult' instruction. It is one of the arguments of the compare instruction. Must be of integer type.
OtherValThe other argument of compare instruction.
Returns
Instruction which must replace the compare instruction, NULL if no replacement required.

Definition at line 3698 of file InstCombineCompares.cpp.

References A, llvm::InstCombineWorklist::Add(), assert(), B, llvm::InstCombiner::Builder, llvm::APInt::countLeadingZeros(), llvm::ExtractValueInst::Create(), llvm::IRBuilder< T, Inserter >::CreateAnd(), llvm::IRBuilder< T, Inserter >::CreateCall(), llvm::IRBuilder< T, Inserter >::CreateExtractValue(), llvm::BinaryOperator::CreateNot(), llvm::IRBuilder< T, Inserter >::CreateZExt(), llvm::dyn_cast(), llvm::APInt::eq(), F, llvm::ConstantInt::getBitWidth(), llvm::APInt::getBitWidth(), llvm::Intrinsic::getDeclaration(), llvm::APInt::getMaxValue(), llvm::Instruction::getModule(), llvm::APInt::getOneBitSet(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), 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::APInt::trunc(), llvm::Value::users(), llvm::InstCombiner::Worklist, and llvm::APInt::zext().

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

◆ rewriteGEPAsOffset()

static Value* rewriteGEPAsOffset ( Value Start,
Value Base,
const DataLayout DL,
SetVector< Value *> &  Explored 
)
static

◆ setInsertionPoint()

static void setInsertionPoint ( IRBuilder<> &  Builder,
Value V,
bool  Before = true 
)
static

◆ STATISTIC()

STATISTIC ( NumSel  ,
"Number of select opts"   
)

◆ subWithOverflow()

static bool subWithOverflow ( Constant *&  Result,
Constant In1,
Constant In2,
bool  IsSigned = false 
)
static

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 foldICmpShlOne().

◆ swapMayExposeCSEOpportunities()

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 3966 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().

◆ transformToIndexedCompare()

static Instruction* transformToIndexedCompare ( GEPOperator GEPLHS,
Value RHS,
ICmpInst::Predicate  Cond,
const DataLayout DL 
)
static

Converts (CMP GEPLHS, RHS) if this change would make RHS a constant.

We can look through PHIs, GEPs and casts in order to determine a common base between GEPLHS and RHS.

Definition at line 882 of file InstCombineCompares.cpp.

References A, llvm::APInt::ashr(), assert(), C, canRewriteGEPAsOffset(), llvm::APInt::countLeadingOnes(), llvm::APInt::countLeadingZeros(), llvm::APInt::countTrailingZeros(), llvm::EmitGEPOffset(), llvm::SmallVectorBase::empty(), evaluateGEPOffsetExpression(), llvm::ConstantInt::get(), llvm::Constant::getAllOnesValue(), getAsConstantIndexedAddress(), llvm::APInt::getBitWidth(), llvm::Value::getContext(), llvm::CmpInst::getInversePredicate(), llvm::ConstantExpr::getNeg(), llvm::Constant::getNullValue(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::CmpInst::getPredicate(), llvm::Type::getPrimitiveSizeInBits(), llvm::APInt::getSignedMaxValue(), llvm::ICmpInst::getSignedPredicate(), llvm::ConstantExpr::getSub(), llvm::CmpInst::getSwappedPredicate(), llvm::ConstantInt::getType(), llvm::Value::getType(), llvm::ConstantInt::getValue(), llvm::GEPOperator::hasAllConstantIndices(), llvm::GEPOperator::hasAllZeroIndices(), llvm::Value::hasOneUse(), I, llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_SLT, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULE, llvm::CmpInst::ICMP_ULT, llvm::APInt::isAllOnesValue(), llvm::ICmpInst::isEquality(), llvm::GEPOperator::isInBounds(), llvm::APInt::isNegative(), llvm::APInt::isNullValue(), llvm::APInt::isPowerOf2(), llvm::CmpInst::isSigned(), llvm::CmpInst::isTrueWhenEqual(), llvm::APInt::logBase2(), llvm::APInt::lshr(), llvm::CmpInst::makeCmpResultType(), Other, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), rewriteGEPAsOffset(), llvm::APInt::sgt(), llvm::APInt::shl(), SI, llvm::SmallVectorTemplateCommon< T >::size(), llvm::Value::stripPointerCasts(), llvm::Value::uses(), and X.