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/CaptureTracking.h"
#include "llvm/Analysis/CmpInstAnalysis.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.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/KnownBits.h"
#include "llvm/Transforms/InstCombine/InstCombiner.h"

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "instcombine"

Functions
	STATISTIC (NumSel, "Number of select opts")
static bool	addWithOverflow (APInt &Result, const APInt &In1, const APInt &In2, bool IsSigned=false)
	Compute Result = In1+In2, returning true if the result overflowed for this type.
static bool	subWithOverflow (APInt &Result, const APInt &In1, const APInt &In2, bool IsSigned=false)
	Compute Result = In1-In2, returning true if the result overflowed for this type.
static bool	hasBranchUse (ICmpInst &I)
	Given an icmp instruction, return true if any use of this comparison is a branch on sign bit comparison.
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.
static bool	canRewriteGEPAsOffset (Type *ElemTy, 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.
static void	setInsertionPoint (IRBuilder<> &Builder, Value *V, bool Before=true)
static Value *	rewriteGEPAsOffset (Type *ElemTy, Value *Start, Value *Base, const DataLayout &DL, SetVector< Value * > &Explored, InstCombiner &IC)
	Returns a re-written value of Start as an indexed GEP using Base as a pointer.
static std::pair< Value *, Value * >	getAsConstantIndexedAddress (Type *ElemTy, Value *V, const DataLayout &DL)
	Looks through GEPs, IntToPtrInsts and PtrToIntInsts in order to express the input Value as a constant indexed GEP.
static Instruction *	transformToIndexedCompare (GEPOperator *GEPLHS, Value *RHS, ICmpInst::Predicate Cond, const DataLayout &DL, InstCombiner &IC)
	Converts (CMP GEPLHS, RHS) if this change would make RHS a constant.
static Instruction *	processUGT_ADDCST_ADD (ICmpInst &I, Value *A, Value *B, ConstantInt *CI2, ConstantInt *CI1, InstCombinerImpl &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.
static Value *	foldICmpOrXorSubChain (ICmpInst &Cmp, BinaryOperator *Or, InstCombiner::BuilderTy &Builder)
	Fold icmp eq/ne (or (xor/sub (X1, X2), xor/sub (X3, X4))), 0.
static Instruction *	foldICmpShlOne (ICmpInst &Cmp, Instruction *Shl, const APInt &C)
	Fold icmp (shl 1, Y), C.
static Instruction *	foldCtpopPow2Test (ICmpInst &I, IntrinsicInst *CtpopLhs, const APInt &CRhs, InstCombiner::BuilderTy &Builder, const SimplifyQuery &Q)
static Instruction *	foldICmpIntrinsicWithIntrinsic (ICmpInst &Cmp, InstCombiner::BuilderTy &Builder)
	Fold an icmp with LLVM intrinsics.
static Instruction *	foldICmpUSubSatOrUAddSatWithConstant (ICmpInst::Predicate Pred, SaturatingInst *II, const APInt &C, InstCombiner::BuilderTy &Builder)
static Value *	foldICmpWithLowBitMaskedVal (ICmpInst &I, InstCombiner::BuilderTy &Builder)
	Some comparisons can be simplified.
static Value *	foldICmpWithTruncSignExtendedVal (ICmpInst &I, InstCombiner::BuilderTy &Builder)
	Some comparisons can be simplified.
static Value *	foldShiftIntoShiftInAnotherHandOfAndInICmp (ICmpInst &I, const SimplifyQuery SQ, InstCombiner::BuilderTy &Builder)
static Instruction *	foldICmpXNegX (ICmpInst &I, InstCombiner::BuilderTy &Builder)
static Instruction *	foldICmpAndXX (ICmpInst &I, const SimplifyQuery &Q, InstCombinerImpl &IC)
static Instruction *	foldICmpOrXX (ICmpInst &I, const SimplifyQuery &Q, InstCombinerImpl &IC)
static Instruction *	foldICmpXorXX (ICmpInst &I, const SimplifyQuery &Q, InstCombinerImpl &IC)
static Instruction *	foldICmpPow2Test (ICmpInst &I, InstCombiner::BuilderTy &Builder)
static bool	isNeutralValue (Instruction::BinaryOps BinaryOp, Value *RHS, bool IsSigned)
static Instruction *	processUMulZExtIdiom (ICmpInst &I, Value *MulVal, Value *OtherVal, InstCombinerImpl &IC)
	Recognize and process idiom involving test for multiplication overflow.
static APInt	getDemandedBitsLHSMask (ICmpInst &I, unsigned BitWidth)
	When performing a comparison against a constant, it is possible that not all the bits in the LHS are demanded.
static bool	isChainSelectCmpBranch (const SelectInst *SI)
	Return true when the instruction sequence within a block is select-cmp-br.
static ICmpInst *	canonicalizeCmpWithConstant (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.
static Instruction *	canonicalizeICmpBool (ICmpInst &I, InstCombiner::BuilderTy &Builder)
	Integer compare with boolean values can always be turned into bitwise ops.
static Instruction *	foldICmpWithHighBitMask (ICmpInst &Cmp, InstCombiner::BuilderTy &Builder)
static Instruction *	foldVectorCmp (CmpInst &Cmp, InstCombiner::BuilderTy &Builder)
static Instruction *	foldICmpOfUAddOv (ICmpInst &I)
static Instruction *	foldICmpInvariantGroup (ICmpInst &I)
static Instruction *	foldReductionIdiom (ICmpInst &I, InstCombiner::BuilderTy &Builder, const DataLayout &DL)
	This function folds patterns produced by lowering of reduce idioms, such as llvm.vector.reduce.and which are lowered into instruction chains.
static Instruction *	foldFCmpReciprocalAndZero (FCmpInst &I, Instruction *LHSI, Constant *RHSC)
	Fold (C / X) < 0.0 --> X < 0.0 if possible. Swap predicate if necessary.
static Instruction *	foldFabsWithFcmpZero (FCmpInst &I, InstCombinerImpl &IC)
	Optimize fabs(X) compared with zero.
static Instruction *	foldFCmpFNegCommonOp (FCmpInst &I)

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "instcombine"

Definition at line 33 of file InstCombineCompares.cpp.

Function Documentation

addWithOverflow()

static bool addWithOverflow ( APInt &  Result, const APInt &  In1, const APInt &  In2, bool  IsSigned = false  )

static

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

Definition at line 41 of file InstCombineCompares.cpp.

References llvm::APInt::sadd_ov(), and llvm::APInt::uadd_ov().

Referenced by llvm::InstCombinerImpl::foldICmpDivConstant().

canonicalizeCmpWithConstant()

static ICmpInst * canonicalizeCmpWithConstant ( ICmpInst &  I )

static

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.

This transform allows them to be folded in visitICmpInst.

Definition at line 6509 of file InstCombineCompares.cpp.

References llvm::InstCombiner::getFlippedStrictnessPredicateAndConstant(), I, llvm::InstCombiner::isCanonicalPredicate(), llvm::ICmpInst::isEquality(), and llvm::CmpInst::isIntPredicate().

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

canonicalizeICmpBool()

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

static

Integer compare with boolean values can always be turned into bitwise ops.

Definition at line 6553 of file InstCombineCompares.cpp.

References A, assert(), B, Builder, llvm::BinaryOperator::CreateNot(), 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_unreachable, llvm::PatternMatch::m_One(), llvm::PatternMatch::m_Zero(), llvm::PatternMatch::match(), and std::swap().

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

canRewriteGEPAsOffset()

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

static

Returns true if we can rewrite Start as a GEP with pointer Base and some integer offset.

The nodes that need to be re-written for this transformation will be added to Explored.

Definition at line 415 of file InstCombineCompares.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::back(), llvm::sampleprof::Base, llvm::SetVector< T, Vector, Set, N >::contains(), DL, llvm::SmallVectorBase< Size_T >::empty(), GEP, llvm::SetVector< T, Vector, Set, N >::insert(), PHI, llvm::SmallVectorTemplateBase< T, bool >::pop_back(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SetVector< T, Vector, Set, N >::size(), and llvm::Value::uses().

Referenced by transformToIndexedCompare().

foldCtpopPow2Test()

static Instruction * foldCtpopPow2Test ( ICmpInst &  I, IntrinsicInst *  CtpopLhs, const APInt &  CRhs, InstCombiner::BuilderTy &  Builder, const SimplifyQuery &  Q  )

static

Definition at line 3409 of file InstCombineCompares.cpp.

References llvm::SimplifyQuery::AC, llvm::And, assert(), Builder, llvm::computeKnownBits(), llvm::KnownBits::countMinPopulation(), llvm::SimplifyQuery::CxtI, llvm::SimplifyQuery::DL, llvm::SimplifyQuery::DT, llvm::CallBase::getArgOperand(), llvm::Constant::getIntegerValue(), llvm::IntrinsicInst::getIntrinsicID(), llvm::Constant::getNullValue(), llvm::Value::hasOneUse(), I, llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULT, and llvm::KnownBits::One.

Referenced by llvm::InstCombinerImpl::foldICmpIntrinsicWithConstant().

foldFabsWithFcmpZero()

static Instruction * foldFabsWithFcmpZero ( FCmpInst &  I, InstCombinerImpl &  IC  )

static

Optimize fabs(X) compared with zero.

Definition at line 7418 of file InstCombineCompares.cpp.

References assert(), llvm::CallingConv::C, F, llvm::CmpInst::FCMP_OEQ, llvm::CmpInst::FCMP_OGE, llvm::CmpInst::FCMP_OGT, llvm::CmpInst::FCMP_OLE, llvm::CmpInst::FCMP_OLT, llvm::CmpInst::FCMP_ONE, llvm::CmpInst::FCMP_ORD, llvm::CmpInst::FCMP_UEQ, llvm::CmpInst::FCMP_UGE, llvm::CmpInst::FCMP_UGT, llvm::CmpInst::FCMP_ULE, llvm::CmpInst::FCMP_ULT, llvm::CmpInst::FCMP_UNE, llvm::CmpInst::FCMP_UNO, llvm::ConstantFP::getZero(), I, llvm_unreachable, llvm::PatternMatch::m_APFloat(), llvm::PatternMatch::m_FAbs(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), P, llvm::DenormalMode::PositiveZero, llvm::DenormalMode::PreserveSign, llvm::InstCombiner::replaceOperand(), and X.

Referenced by llvm::InstCombinerImpl::visitFCmpInst().

foldFCmpFNegCommonOp()

static Instruction * foldFCmpFNegCommonOp ( FCmpInst &  I )

static

Definition at line 7518 of file InstCombineCompares.cpp.

References llvm::Value::getType(), llvm::ConstantFP::getZero(), I, llvm::PatternMatch::m_FNeg(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and std::swap().

Referenced by llvm::InstCombinerImpl::visitFCmpInst().

foldFCmpReciprocalAndZero()

static Instruction * foldFCmpReciprocalAndZero ( FCmpInst &  I, Instruction *  LHSI, Constant *  RHSC  )

static

Fold (C / X) < 0.0 --> X < 0.0 if possible. Swap predicate if necessary.

Definition at line 7371 of file InstCombineCompares.cpp.

References llvm::CallingConv::C, llvm::CmpInst::FCMP_OGE, llvm::CmpInst::FCMP_OGT, llvm::CmpInst::FCMP_OLE, llvm::CmpInst::FCMP_OLT, llvm::User::getOperand(), llvm::Instruction::hasNoInfs(), I, llvm::PatternMatch::m_AnyZeroFP(), llvm::PatternMatch::m_APFloat(), and llvm::PatternMatch::match().

Referenced by llvm::InstCombinerImpl::visitFCmpInst().

foldICmpAndXX()

static Instruction * foldICmpAndXX ( ICmpInst &  I, const SimplifyQuery &  Q, InstCombinerImpl &  IC  )

static

Definition at line 4430 of file InstCombineCompares.cpp.

References A, llvm::CmpInst::getSwappedPredicate(), I, llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_ULT, llvm::PatternMatch::m_c_And(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and std::swap().

Referenced by llvm::InstCombinerImpl::foldICmpBinOp().

foldICmpIntrinsicWithIntrinsic()

static Instruction * foldICmpIntrinsicWithIntrinsic ( ICmpInst &  Cmp, InstCombiner::BuilderTy &  Builder  )

static

Fold an icmp with LLVM intrinsics.

Definition at line 3556 of file InstCombineCompares.cpp.

References assert(), Builder, llvm::Value::getType(), llvm::PatternMatch::m_ImmConstant(), and llvm::PatternMatch::match().

Referenced by llvm::InstCombinerImpl::foldICmpEquality().

foldICmpInvariantGroup()

static Instruction * foldICmpInvariantGroup ( ICmpInst &  I )

static

Definition at line 6773 of file InstCombineCompares.cpp.

References llvm::CmpInst::Create(), I, llvm::PatternMatch::m_Instruction(), llvm::PatternMatch::m_Zero(), llvm::PatternMatch::match(), and llvm::NullPointerIsDefined().

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

foldICmpOfUAddOv()

static Instruction * foldICmpOfUAddOv ( ICmpInst &  I )

static

Definition at line 6745 of file InstCombineCompares.cpp.

References A, B, llvm::ExtractValueInst::Create(), I, llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULT, llvm::PatternMatch::m_AllOnes(), llvm::PatternMatch::m_One(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_ZeroInt(), and llvm::PatternMatch::match().

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

foldICmpOrXorSubChain()

static Value * foldICmpOrXorSubChain ( ICmpInst &  Cmp, BinaryOperator *  Or, InstCombiner::BuilderTy &  Builder  )

static

Fold icmp eq/ne (or (xor/sub (X1, X2), xor/sub (X3, X4))), 0.

Definition at line 1949 of file InstCombineCompares.cpp.

References Builder, llvm::SmallVectorImpl< T >::emplace_back(), llvm::SmallVectorBase< Size_T >::empty(), llvm::CmpInst::ICMP_EQ, llvm::PatternMatch::m_OneUse(), llvm::PatternMatch::m_Or(), llvm::PatternMatch::m_Sub(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_Xor(), llvm::PatternMatch::match(), llvm::Or, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SmallVectorTemplateCommon< T, typename >::rbegin(), and llvm::SmallVectorTemplateCommon< T, typename >::rend().

Referenced by llvm::InstCombinerImpl::foldICmpOrConstant().

foldICmpOrXX()

static Instruction * foldICmpOrXX ( ICmpInst &  I, const SimplifyQuery &  Q, InstCombinerImpl &  IC  )

static

Definition at line 4454 of file InstCombineCompares.cpp.

References A, llvm::InstCombiner::Builder, llvm::IRBuilderBase::CreateAnd(), llvm::IRBuilderBase::CreateNot(), llvm::IRBuilderBase::CreateOr(), llvm::Constant::getAllOnesValue(), llvm::Constant::getNullValue(), llvm::CmpInst::getSwappedPredicate(), llvm::Value::hasOneUse(), I, llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULE, llvm::ICmpInst::isEquality(), llvm::InstCombiner::isFreeToInvert(), llvm::PatternMatch::m_c_Or(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and std::swap().

Referenced by llvm::InstCombinerImpl::foldICmpBinOp().

foldICmpPow2Test()

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

static

Definition at line 5126 of file InstCombineCompares.cpp.

References A, Builder, llvm::ConstantInt::get(), I, llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULE, llvm::CmpInst::ICMP_ULT, llvm::CmpInst::isUnsigned(), llvm::PatternMatch::m_Add(), llvm::PatternMatch::m_AllOnes(), llvm::PatternMatch::m_c_And(), llvm::PatternMatch::m_c_Xor(), llvm::PatternMatch::m_Deferred(), llvm::PatternMatch::m_Neg(), llvm::PatternMatch::m_OneUse(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_ZeroInt(), and llvm::PatternMatch::match().

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

foldICmpShlOne()

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

static

Fold icmp (shl 1, Y), C.

Definition at line 2190 of file InstCombineCompares.cpp.

References llvm::CallingConv::C, llvm::ConstantInt::get(), llvm::Value::getType(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, 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::PatternMatch::m_One(), llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and Y.

Referenced by llvm::InstCombinerImpl::foldICmpShlConstant().

foldICmpUSubSatOrUAddSatWithConstant()

static Instruction * foldICmpUSubSatOrUAddSatWithConstant ( ICmpInst::Predicate  Pred, SaturatingInst *  II, const APInt &  C, InstCombiner::BuilderTy &  Builder  )

static

Definition at line 3692 of file InstCombineCompares.cpp.

References llvm::ConstantRange::add(), Builder, llvm::CallingConv::C, llvm::ICmpInst::compare(), llvm::ConstantRange::exactIntersectWith(), llvm::ConstantRange::exactUnionWith(), llvm::ConstantInt::get(), llvm::APInt::getAllOnes(), llvm::BinaryOpIntrinsic::getBinaryOp(), llvm::IntrinsicInst::getIntrinsicID(), llvm::BinaryOpIntrinsic::getNoWrapKind(), llvm::User::getOperand(), llvm::Value::getType(), llvm::APInt::getZero(), llvm::Value::hasOneUse(), llvm::ConstantRange::inverse(), llvm_unreachable, llvm::PatternMatch::m_APInt(), llvm::ConstantRange::makeExactICmpRegion(), llvm::ConstantRange::makeExactNoWrapRegion(), llvm::PatternMatch::match(), and llvm::ConstantRange::sub().

Referenced by llvm::InstCombinerImpl::foldICmpIntrinsicWithConstant().

foldICmpWithHighBitMask()

static Instruction * foldICmpWithHighBitMask ( ICmpInst &  Cmp, InstCombiner::BuilderTy &  Builder  )

static

Definition at line 6632 of file InstCombineCompares.cpp.

References Builder, llvm::CmpInst::Create(), llvm::Constant::getNullValue(), llvm::Value::getType(), 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::PatternMatch::m_Add(), llvm::PatternMatch::m_AllOnes(), llvm::PatternMatch::m_c_ICmp(), llvm::PatternMatch::m_CombineOr(), llvm::PatternMatch::m_Not(), llvm::PatternMatch::m_One(), llvm::PatternMatch::m_OneUse(), llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), X, and Y.

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

foldICmpWithLowBitMaskedVal()

static Value * foldICmpWithLowBitMaskedVal ( ICmpInst &  I, InstCombiner::BuilderTy &  Builder  )

static

Some comparisons can be simplified.

In this case, we are looking for comparisons that look like a check for a lossy truncation. Folds: icmp SrcPred (x & Mask), x to icmp DstPred x, Mask Where Mask is some pattern that produces all-ones in low bits: (-1 >> y) ((-1 << y) >> y) <- non-canonical, has extra uses ~(-1 << y) ((1 << y) + (-1)) <- non-canonical, has extra uses The Mask can be a constant, too. For some predicates, the operands are commutative. For others, x can only be on a specific side.

Definition at line 3991 of file InstCombineCompares.cpp.

References assert(), Builder, llvm::Constant::getAggregateElement(), 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_unreachable, llvm::PatternMatch::m_Add(), llvm::PatternMatch::m_AllOnes(), llvm::PatternMatch::m_c_And(), llvm::PatternMatch::m_c_ICmp(), llvm::PatternMatch::m_CombineAnd(), llvm::PatternMatch::m_CombineOr(), llvm::PatternMatch::m_Constant(), llvm::PatternMatch::m_Deferred(), llvm::PatternMatch::m_LowBitMask(), llvm::PatternMatch::m_LShr(), llvm::PatternMatch::m_NonNegative(), llvm::PatternMatch::m_Not(), llvm::PatternMatch::m_One(), llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::Constant::replaceUndefsWith(), X, and Y.

Referenced by llvm::InstCombinerImpl::foldICmpBinOp().

foldICmpWithTruncSignExtendedVal()

static Value * foldICmpWithTruncSignExtendedVal ( ICmpInst &  I, InstCombiner::BuilderTy &  Builder  )

static

Some comparisons can be simplified.

In this case, we are looking for comparisons that look like a check for a lossy signed truncation. Folds: (MaskedBits is a constant.) ((x << MaskedBits) a>> MaskedBits) SrcPred x Into: (add x, (1 << (KeptBits-1))) DstPred (1 << KeptBits) Where KeptBits = bitwidth(x) - MaskedBits

Definition at line 4085 of file InstCombineCompares.cpp.

References assert(), llvm::BitWidth, Builder, llvm::ConstantInt::get(), I, llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_ULT, llvm::APInt::isPowerOf2(), llvm::APInt::lshr(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_AShr(), llvm::PatternMatch::m_c_ICmp(), llvm::PatternMatch::m_Deferred(), llvm::PatternMatch::m_OneUse(), llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::APInt::shl(), T1, llvm::APInt::ugt(), llvm::APInt::ult(), and X.

Referenced by llvm::InstCombinerImpl::foldICmpBinOp().

foldICmpXNegX()

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

static

Definition at line 4398 of file InstCombineCompares.cpp.

References llvm::And, llvm::BitWidth, Builder, llvm::CmpInst::Create(), llvm::ConstantInt::get(), llvm::Constant::getNullValue(), llvm::Type::getScalarSizeInBits(), llvm::APInt::getSignedMaxValue(), llvm::ICmpInst::getSignedPredicate(), llvm::CmpInst::getSwappedPredicate(), I, llvm::ICmpInst::isEquality(), llvm::CmpInst::isSigned(), llvm::CmpInst::isUnsigned(), llvm::PatternMatch::m_c_ICmp(), llvm::PatternMatch::m_Deferred(), llvm::PatternMatch::m_Neg(), llvm::PatternMatch::m_NSWNeg(), llvm::PatternMatch::m_OneUse(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and X.

Referenced by llvm::InstCombinerImpl::foldICmpBinOp().

foldICmpXorXX()

static Instruction * foldICmpXorXX ( ICmpInst &  I, const SimplifyQuery &  Q, InstCombinerImpl &  IC  )

static

Definition at line 4490 of file InstCombineCompares.cpp.

References A, llvm::SimplifyQuery::AC, llvm::SimplifyQuery::CxtI, llvm::SimplifyQuery::DL, llvm::SimplifyQuery::DT, llvm::CmpInst::getStrictPredicate(), llvm::CmpInst::getSwappedPredicate(), I, llvm::isKnownNonZero(), llvm::PatternMatch::m_c_Xor(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and std::swap().

Referenced by llvm::InstCombinerImpl::foldICmpBinOp().

foldReductionIdiom()

static Instruction * foldReductionIdiom ( ICmpInst &  I, InstCombiner::BuilderTy &  Builder, const DataLayout &  DL  )

static

This function folds patterns produced by lowering of reduce idioms, such as llvm.vector.reduce.and which are lowered into instruction chains.

This code attempts to generate fewer number of scalar comparisons instead of vector comparisons when possible.

vec_ne = icmp ne <8 x i8> lhs, rhs scalar_ne = bitcast <8 x i1> vec_ne to i8 res = icmp <pred> i8 scalar_ne, 0

into

lhs.scalar = bitcast <8 x i8> lhs to i64 rhs.scalar = bitcast <8 x i8> rhs to i64 res = icmp <pred> i64 lhs.scalar, rhs.scalar

for <pred> in {ne, eq}.

Definition at line 6794 of file InstCombineCompares.cpp.

References Builder, llvm::CmpInst::Create(), DL, llvm::Value::getName(), llvm::Value::getType(), I, llvm::CmpInst::ICMP_NE, llvm::ICmpInst::isEquality(), LHS, llvm::PatternMatch::m_BitCast(), llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_OneUse(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_Zero(), llvm::PatternMatch::match(), and RHS.

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

foldShiftIntoShiftInAnotherHandOfAndInICmp()

static Value * foldShiftIntoShiftInAnotherHandOfAndInICmp ( ICmpInst &  I, const SimplifyQuery  SQ, InstCombiner::BuilderTy &  Builder  )

static

Definition at line 4159 of file InstCombineCompares.cpp.

References assert(), Builder, llvm::CallingConv::C, llvm::computeKnownBits(), llvm::KnownBits::countMinLeadingZeros(), llvm::APInt::getAllOnes(), llvm::KnownBits::getBitWidth(), llvm::Constant::getNullValue(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::Type::getScalarSizeInBits(), llvm::Value::getType(), llvm::Constant::getUniqueInteger(), llvm::SimplifyQuery::getWithInstruction(), llvm::ConstantExpr::getZExtOrBitCast(), llvm::Value::hasOneUse(), I, llvm::CmpInst::ICMP_ULT, llvm::Constant::isNullValue(), llvm::Type::isVectorTy(), llvm::PatternMatch::m_BinOp(), llvm::PatternMatch::m_c_And(), llvm::PatternMatch::m_CombineAnd(), llvm::PatternMatch::m_Instruction(), llvm::PatternMatch::m_LogicalShift(), llvm::PatternMatch::m_LShr(), llvm::PatternMatch::m_OneUse(), llvm::PatternMatch::m_SpecificInt_ICMP(), llvm::PatternMatch::m_TruncOrSelf(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_Zero(), llvm::PatternMatch::m_ZExtOrSelf(), llvm::PatternMatch::match(), llvm::simplifyAddInst(), std::swap(), T1, llvm::APInt::ule(), llvm::APInt::ult(), X, and Y.

Referenced by llvm::InstCombinerImpl::foldICmpBinOp().

foldVectorCmp()

static Instruction * foldVectorCmp ( CmpInst &  Cmp, InstCombiner::BuilderTy &  Builder  )

static

Definition at line 6675 of file InstCombineCompares.cpp.

References Builder, llvm::CallingConv::C, llvm::CallInst::Create(), F, llvm::Intrinsic::getDeclaration(), llvm::ConstantVector::getSplat(), llvm::Value::getType(), llvm::Value::hasOneUse(), I, llvm::isSplatValue(), LHS, llvm::PatternMatch::m_Constant(), llvm::PatternMatch::m_OneUse(), llvm::PatternMatch::m_Shuffle(), llvm::PatternMatch::m_Undef(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_VecReverse(), llvm::PatternMatch::match(), RHS, X, and Y.

Referenced by llvm::InstCombinerImpl::visitFCmpInst(), and llvm::InstCombinerImpl::visitICmpInst().

getAsConstantIndexedAddress()

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

static

Looks through GEPs, IntToPtrInsts and PtrToIntInsts in order to express the input Value as a constant indexed GEP.

Returns a pair containing the GEPs Pointer and Index.

Definition at line 658 of file InstCombineCompares.cpp.

References DL, GEP, llvm::IntegerType::get(), llvm::ConstantExpr::getAdd(), llvm::Constant::getNullValue(), and llvm::ConstantExpr::getSExtOrTrunc().

Referenced by transformToIndexedCompare().

getDemandedBitsLHSMask()

static APInt getDemandedBitsLHSMask ( ICmpInst &  I, unsigned  BitWidth  )

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

References llvm::BitWidth, llvm::APInt::getAllOnes(), llvm::APInt::getBitsSetFrom(), llvm::APInt::getSignMask(), I, llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULT, llvm::InstCombiner::isSignBitCheck(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::match(), and RHS.

Referenced by llvm::InstCombinerImpl::foldICmpUsingKnownBits().

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

References I.

Referenced by llvm::InstCombinerImpl::foldICmpWithDominatingICmp().

isChainSelectCmpBranch()

static bool isChainSelectCmpBranch ( const SelectInst *  SI )

static

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

Definition at line 6032 of file InstCombineCompares.cpp.

References llvm::BasicBlock::getTerminator().

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

isNeutralValue()

static bool isNeutralValue ( Instruction::BinaryOps  BinaryOp, Value *  RHS, bool  IsSigned  )

static

Definition at line 5653 of file InstCombineCompares.cpp.

References llvm::Value::getType(), llvm::Type::isIntOrIntVectorTy(), llvm_unreachable, llvm::PatternMatch::m_One(), llvm::PatternMatch::m_Zero(), llvm::PatternMatch::match(), and RHS.

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

References llvm::CallingConv::C, and llvm::ICmpInst::isRelational().

Referenced by llvm::InstCombinerImpl::foldICmpMulConstant().

processUGT_ADDCST_ADD()

static Instruction * processUGT_ADDCST_ADD ( ICmpInst &  I, Value *  A, Value *  B, ConstantInt *  CI2, ConstantInt *  CI1, InstCombinerImpl &  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 1143 of file InstCombineCompares.cpp.

References A, llvm::Add, B, llvm::InstCombiner::Builder, Builder, llvm::InstCombiner::ComputeMaxSignificantBits(), llvm::APInt::countr_zero(), llvm::ExtractValueInst::Create(), llvm::InstCombinerImpl::eraseInstFromFunction(), F, llvm::IntegerType::get(), llvm::ConstantInt::getBitWidth(), llvm::Value::getContext(), llvm::Intrinsic::getDeclaration(), llvm::APInt::getLowBitsSet(), llvm::User::getOperand(), llvm::Type::getPrimitiveSizeInBits(), llvm::Value::getType(), llvm::ConstantInt::getValue(), llvm::Value::hasOneUse(), I, llvm::APInt::isPowerOf2(), llvm::InstCombiner::replaceInstUsesWith(), and llvm::Value::users().

Referenced by llvm::InstCombinerImpl::foldICmpWithConstant().

processUMulZExtIdiom()

static Instruction * processUMulZExtIdiom ( ICmpInst &  I, Value *  MulVal, Value *  OtherVal, InstCombinerImpl &  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 5754 of file InstCombineCompares.cpp.

References A, llvm::InstCombiner::addToWorklist(), assert(), B, llvm::InstCombiner::Builder, Builder, llvm::APInt::countl_zero(), llvm::ExtractValueInst::Create(), llvm::BinaryOperator::CreateNot(), llvm::APInt::eq(), F, llvm::APInt::getBitWidth(), llvm::ConstantInt::getBitWidth(), llvm::Intrinsic::getDeclaration(), llvm::APInt::getMaxValue(), llvm::APInt::getOneBitSet(), llvm::Type::getPrimitiveSizeInBits(), llvm::Value::getType(), llvm::ConstantInt::getValue(), llvm::Value::hasNUsesOrMore(), I, 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(), LHS, llvm_unreachable, llvm::APInt::logBase2(), llvm::PatternMatch::m_And(), llvm::PatternMatch::m_ConstantInt(), llvm::PatternMatch::m_Value(), llvm::make_early_inc_range(), llvm::PatternMatch::match(), llvm::Mul, llvm::InstCombiner::replaceInstUsesWith(), RHS, llvm::User::setOperand(), llvm::APInt::trunc(), llvm::Value::users(), and llvm::APInt::zext().

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

rewriteGEPAsOffset()

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

static

Returns a re-written value of Start as an indexed GEP using Base as a pointer.

Definition at line 540 of file InstCombineCompares.cpp.

References llvm::PHINode::addIncoming(), llvm::InstCombiner::addToWorklist(), llvm::sampleprof::Base, Builder, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::contains(), llvm::PHINode::Create(), DL, E, GEP, llvm::IntegerType::get(), llvm::PointerType::get(), llvm::Constant::getNullValue(), llvm::Value::getType(), I, isZero(), llvm_unreachable, PHI, llvm::InstCombiner::replaceInstUsesWith(), and setInsertionPoint().

Referenced by transformToIndexedCompare().

setInsertionPoint()

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

static

Definition at line 514 of file InstCombineCompares.cpp.

References A, assert(), Builder, llvm::BasicBlock::getFirstInsertionPt(), I, and PHI.

Referenced by rewriteGEPAsOffset().

STATISTIC()

STATISTIC	(	NumSel	,
		"Number of select opts"
	)

subWithOverflow()

static bool subWithOverflow ( APInt &  Result, const APInt &  In1, const APInt &  In2, bool  IsSigned = false  )

static

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

Definition at line 54 of file InstCombineCompares.cpp.

References llvm::APInt::ssub_ov(), and llvm::APInt::usub_ov().

Referenced by llvm::InstCombinerImpl::foldICmpDivConstant(), and llvm::InstCombinerImpl::foldICmpSubConstant().

transformToIndexedCompare()

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

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

References canRewriteGEPAsOffset(), Cond, DL, getAsConstantIndexedAddress(), llvm::ICmpInst::getSignedPredicate(), llvm::GEPOperator::getSourceElementType(), llvm::Value::getType(), llvm::GEPOperator::hasAllConstantIndices(), llvm::Type::isVectorTy(), rewriteGEPAsOffset(), and RHS.

Referenced by llvm::InstCombinerImpl::foldGEPICmp().