LLVM 19.0.0git
Macros | Functions
InstCombineCompares.cpp File Reference
#include "InstCombineInternal.h"
#include "llvm/ADT/APSInt.h"
#include "llvm/ADT/ScopeExit.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/Utils/Local.h"
#include "llvm/Analysis/VectorUtils.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Transforms/InstCombine/InstCombiner.h"
#include <bitset>

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 (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 ValuerewriteGEPAsOffset (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 InstructiontransformToIndexedCompare (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 InstructionprocessUGT_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 ValuefoldICmpOrXorSubChain (ICmpInst &Cmp, BinaryOperator *Or, InstCombiner::BuilderTy &Builder)
 Fold icmp eq/ne (or (xor/sub (X1, X2), xor/sub (X3, X4))), 0.
 
static InstructionfoldICmpShlOne (ICmpInst &Cmp, Instruction *Shl, const APInt &C)
 Fold icmp (shl 1, Y), C.
 
static ValuecreateLogicFromTable (const std::bitset< 4 > &Table, Value *Op0, Value *Op1, IRBuilderBase &Builder, bool HasOneUse)
 
static InstructionfoldCtpopPow2Test (ICmpInst &I, IntrinsicInst *CtpopLhs, const APInt &CRhs, InstCombiner::BuilderTy &Builder, const SimplifyQuery &Q)
 
static InstructionfoldICmpIntrinsicWithIntrinsic (ICmpInst &Cmp, InstCombiner::BuilderTy &Builder)
 Fold an icmp with LLVM intrinsics.
 
static InstructionfoldICmpUSubSatOrUAddSatWithConstant (ICmpInst::Predicate Pred, SaturatingInst *II, const APInt &C, InstCombiner::BuilderTy &Builder)
 
static bool isMaskOrZero (const Value *V, bool Not, const SimplifyQuery &Q, unsigned Depth=0)
 
static ValuefoldICmpWithLowBitMaskedVal (ICmpInst::Predicate Pred, Value *Op0, Value *Op1, const SimplifyQuery &Q, InstCombiner &IC)
 Some comparisons can be simplified.
 
static ValuefoldICmpWithTruncSignExtendedVal (ICmpInst &I, InstCombiner::BuilderTy &Builder)
 Some comparisons can be simplified.
 
static ValuefoldShiftIntoShiftInAnotherHandOfAndInICmp (ICmpInst &I, const SimplifyQuery SQ, InstCombiner::BuilderTy &Builder)
 
static InstructionfoldICmpXNegX (ICmpInst &I, InstCombiner::BuilderTy &Builder)
 
static InstructionfoldICmpAndXX (ICmpInst &I, const SimplifyQuery &Q, InstCombinerImpl &IC)
 
static InstructionfoldICmpOrXX (ICmpInst &I, const SimplifyQuery &Q, InstCombinerImpl &IC)
 
static InstructionfoldICmpXorXX (ICmpInst &I, const SimplifyQuery &Q, InstCombinerImpl &IC)
 
static InstructionfoldICmpPow2Test (ICmpInst &I, InstCombiner::BuilderTy &Builder)
 
static bool isNeutralValue (Instruction::BinaryOps BinaryOp, Value *RHS, bool IsSigned)
 
static InstructionprocessUMulZExtIdiom (ICmpInst &I, Value *MulVal, const APInt *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 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.
 
static InstructioncanonicalizeICmpBool (ICmpInst &I, InstCombiner::BuilderTy &Builder)
 Integer compare with boolean values can always be turned into bitwise ops.
 
static InstructionfoldICmpWithHighBitMask (ICmpInst &Cmp, InstCombiner::BuilderTy &Builder)
 
static InstructionfoldVectorCmp (CmpInst &Cmp, InstCombiner::BuilderTy &Builder)
 
static InstructionfoldICmpOfUAddOv (ICmpInst &I)
 
static InstructionfoldICmpInvariantGroup (ICmpInst &I)
 
static InstructionfoldReductionIdiom (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 InstructionfoldFCmpReciprocalAndZero (FCmpInst &I, Instruction *LHSI, Constant *RHSC)
 Fold (C / X) < 0.0 --> X < 0.0 if possible. Swap predicate if necessary.
 
static InstructionfoldFabsWithFcmpZero (FCmpInst &I, InstCombinerImpl &IC)
 Optimize fabs(X) compared with zero.
 
static InstructionfoldFCmpFNegCommonOp (FCmpInst &I)
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "instcombine"

Definition at line 36 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 44 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 6760 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

◆ canRewriteGEPAsOffset()

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

◆ createLogicFromTable()

static Value * createLogicFromTable ( const std::bitset< 4 > &  Table,
Value Op0,
Value Op1,
IRBuilderBase Builder,
bool  HasOneUse 
)
static

◆ foldCtpopPow2Test()

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

◆ foldFabsWithFcmpZero()

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

◆ foldFCmpFNegCommonOp()

static Instruction * foldFCmpFNegCommonOp ( FCmpInst I)
static

◆ foldFCmpReciprocalAndZero()

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

◆ foldICmpAndXX()

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

◆ foldICmpIntrinsicWithIntrinsic()

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

◆ foldICmpInvariantGroup()

static Instruction * foldICmpInvariantGroup ( ICmpInst I)
static

◆ foldICmpOfUAddOv()

static Instruction * foldICmpOfUAddOv ( ICmpInst I)
static

◆ foldICmpOrXorSubChain()

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

◆ foldICmpOrXX()

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

◆ foldICmpPow2Test()

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

◆ foldICmpShlOne()

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

◆ foldICmpUSubSatOrUAddSatWithConstant()

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

◆ foldICmpWithHighBitMask()

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

◆ foldICmpWithLowBitMaskedVal()

static Value * foldICmpWithLowBitMaskedVal ( ICmpInst::Predicate  Pred,
Value Op0,
Value Op1,
const SimplifyQuery Q,
InstCombiner IC 
)
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 icmp SrcPred (x & ~Mask), ~Mask to icmp DstPred x, ~Mask icmp eq/ne (x & ~Mask), 0 to icmp DstPred x, Mask icmp eq/ne (~x | Mask), -1 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 4232 of file InstCombineCompares.cpp.

References llvm::InstCombiner::Builder, Check, llvm::IRBuilderBase::CreateICmp(), llvm::InstCombiner::getFreelyInverted(), 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::ICmpInst::isEquality(), llvm::isKnownNonNegative(), llvm::isKnownNonZero(), isMaskOrZero(), llvm::CmpInst::isSigned(), llvm::PatternMatch::m_AllOnes(), llvm::PatternMatch::m_And(), llvm::PatternMatch::m_c_And(), llvm::PatternMatch::m_NonNegative(), llvm::PatternMatch::m_OneUse(), llvm::PatternMatch::m_Or(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_Zero(), llvm::PatternMatch::match(), std::swap(), and X.

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

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

References assert(), llvm::BitWidth, llvm::IRBuilderBase::CreateAdd(), llvm::IRBuilderBase::CreateICmp(), 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

◆ foldICmpXorXX()

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

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

References llvm::CmpInst::Create(), llvm::IRBuilderBase::CreateBitCast(), DL, llvm::IRBuilderBase::getIntNTy(), 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

◆ foldVectorCmp()

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

◆ 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 6196 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::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 70 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 6257 of file InstCombineCompares.cpp.

References llvm::BasicBlock::getTerminator().

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

◆ isMaskOrZero()

static bool isMaskOrZero ( const Value V,
bool  Not,
const SimplifyQuery Q,
unsigned  Depth = 0 
)
static

◆ isNeutralValue()

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

◆ 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 81 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

◆ processUMulZExtIdiom()

static Instruction * processUMulZExtIdiom ( ICmpInst I,
Value MulVal,
const APInt 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
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 6049 of file InstCombineCompares.cpp.

References A, llvm::InstCombiner::addToWorklist(), assert(), B, llvm::InstCombiner::Builder, llvm::APInt::countl_zero(), llvm::ExtractValueInst::Create(), llvm::IRBuilderBase::CreateAnd(), llvm::IRBuilderBase::CreateCall(), llvm::IRBuilderBase::CreateExtractValue(), llvm::BinaryOperator::CreateNot(), llvm::IRBuilderBase::CreateZExt(), llvm::APInt::eq(), F, llvm::APInt::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_UGT, llvm::CmpInst::ICMP_ULT, LHS, llvm_unreachable, llvm::make_early_inc_range(), llvm::Mul, llvm::InstCombiner::replaceInstUsesWith(), RHS, llvm::IRBuilderBase::SetInsertPoint(), llvm::User::setOperand(), llvm::APInt::trunc(), llvm::Value::users(), and llvm::APInt::zext().

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

◆ rewriteGEPAsOffset()

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

◆ setInsertionPoint()

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

◆ 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 57 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 630 of file InstCombineCompares.cpp.

References llvm::InstCombiner::Builder, canRewriteGEPAsOffset(), Cond, DL, llvm::IRBuilderBase::getInt(), llvm::ICmpInst::getSignedPredicate(), llvm::Value::getType(), llvm::GEPOperator::hasAllConstantIndices(), llvm::Type::isVectorTy(), llvm::Offset, rewriteGEPAsOffset(), RHS, and llvm::Value::stripAndAccumulateConstantOffsets().

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