InstCombineCompares.cpp [plain text]
#include "InstCombine.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/GetElementPtrTypeIterator.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Target/TargetLibraryInfo.h"
using namespace llvm;
using namespace PatternMatch;
#define DEBUG_TYPE "instcombine"
static ConstantInt *getOne(Constant *C) {
return ConstantInt::get(cast<IntegerType>(C->getType()), 1);
}
static ConstantInt *ExtractElement(Constant *V, Constant *Idx) {
return cast<ConstantInt>(ConstantExpr::getExtractElement(V, Idx));
}
static bool HasAddOverflow(ConstantInt *Result,
ConstantInt *In1, ConstantInt *In2,
bool IsSigned) {
if (!IsSigned)
return Result->getValue().ult(In1->getValue());
if (In2->isNegative())
return Result->getValue().sgt(In1->getValue());
return Result->getValue().slt(In1->getValue());
}
static bool AddWithOverflow(Constant *&Result, Constant *In1,
Constant *In2, bool IsSigned = false) {
Result = ConstantExpr::getAdd(In1, In2);
if (VectorType *VTy = dyn_cast<VectorType>(In1->getType())) {
for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
Constant *Idx = ConstantInt::get(Type::getInt32Ty(In1->getContext()), i);
if (HasAddOverflow(ExtractElement(Result, Idx),
ExtractElement(In1, Idx),
ExtractElement(In2, Idx),
IsSigned))
return true;
}
return false;
}
return HasAddOverflow(cast<ConstantInt>(Result),
cast<ConstantInt>(In1), cast<ConstantInt>(In2),
IsSigned);
}
static bool HasSubOverflow(ConstantInt *Result,
ConstantInt *In1, ConstantInt *In2,
bool IsSigned) {
if (!IsSigned)
return Result->getValue().ugt(In1->getValue());
if (In2->isNegative())
return Result->getValue().slt(In1->getValue());
return Result->getValue().sgt(In1->getValue());
}
static bool SubWithOverflow(Constant *&Result, Constant *In1,
Constant *In2, bool IsSigned = false) {
Result = ConstantExpr::getSub(In1, In2);
if (VectorType *VTy = dyn_cast<VectorType>(In1->getType())) {
for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
Constant *Idx = ConstantInt::get(Type::getInt32Ty(In1->getContext()), i);
if (HasSubOverflow(ExtractElement(Result, Idx),
ExtractElement(In1, Idx),
ExtractElement(In2, Idx),
IsSigned))
return true;
}
return false;
}
return HasSubOverflow(cast<ConstantInt>(Result),
cast<ConstantInt>(In1), cast<ConstantInt>(In2),
IsSigned);
}
static bool isSignBitCheck(ICmpInst::Predicate pred, ConstantInt *RHS,
bool &TrueIfSigned) {
switch (pred) {
case ICmpInst::ICMP_SLT: TrueIfSigned = true;
return RHS->isZero();
case ICmpInst::ICMP_SLE: TrueIfSigned = true;
return RHS->isAllOnesValue();
case ICmpInst::ICMP_SGT: TrueIfSigned = false;
return RHS->isAllOnesValue();
case ICmpInst::ICMP_UGT:
TrueIfSigned = true;
return RHS->isMaxValue(true);
case ICmpInst::ICMP_UGE:
TrueIfSigned = true;
return RHS->getValue().isSignBit();
default:
return false;
}
}
static bool isSignTest(ICmpInst::Predicate &pred, const ConstantInt *RHS) {
if (!ICmpInst::isSigned(pred))
return false;
if (RHS->isZero())
return ICmpInst::isRelational(pred);
if (RHS->isOne()) {
if (pred == ICmpInst::ICMP_SLT) {
pred = ICmpInst::ICMP_SLE;
return true;
}
} else if (RHS->isAllOnesValue()) {
if (pred == ICmpInst::ICMP_SGT) {
pred = ICmpInst::ICMP_SGE;
return true;
}
}
return false;
}
static bool isHighOnes(const ConstantInt *CI) {
return (~CI->getValue() + 1).isPowerOf2();
}
static void ComputeSignedMinMaxValuesFromKnownBits(const APInt& KnownZero,
const APInt& KnownOne,
APInt& Min, APInt& Max) {
assert(KnownZero.getBitWidth() == KnownOne.getBitWidth() &&
KnownZero.getBitWidth() == Min.getBitWidth() &&
KnownZero.getBitWidth() == Max.getBitWidth() &&
"KnownZero, KnownOne and Min, Max must have equal bitwidth.");
APInt UnknownBits = ~(KnownZero|KnownOne);
Min = KnownOne;
Max = KnownOne|UnknownBits;
if (UnknownBits.isNegative()) { Min.setBit(Min.getBitWidth()-1);
Max.clearBit(Max.getBitWidth()-1);
}
}
static void ComputeUnsignedMinMaxValuesFromKnownBits(const APInt &KnownZero,
const APInt &KnownOne,
APInt &Min, APInt &Max) {
assert(KnownZero.getBitWidth() == KnownOne.getBitWidth() &&
KnownZero.getBitWidth() == Min.getBitWidth() &&
KnownZero.getBitWidth() == Max.getBitWidth() &&
"Ty, KnownZero, KnownOne and Min, Max must have equal bitwidth.");
APInt UnknownBits = ~(KnownZero|KnownOne);
Min = KnownOne;
Max = KnownOne|UnknownBits;
}
Instruction *InstCombiner::
FoldCmpLoadFromIndexedGlobal(GetElementPtrInst *GEP, GlobalVariable *GV,
CmpInst &ICI, ConstantInt *AndCst) {
if (!GEP->isInBounds() && !DL)
return nullptr;
Constant *Init = GV->getInitializer();
if (!isa<ConstantArray>(Init) && !isa<ConstantDataArray>(Init))
return nullptr;
uint64_t ArrayElementCount = Init->getType()->getArrayNumElements();
if (ArrayElementCount > 1024) return nullptr;
if (GEP->getNumOperands() < 3 ||
!isa<ConstantInt>(GEP->getOperand(1)) ||
!cast<ConstantInt>(GEP->getOperand(1))->isZero() ||
isa<Constant>(GEP->getOperand(2)))
return nullptr;
SmallVector<unsigned, 4> LaterIndices;
Type *EltTy = Init->getType()->getArrayElementType();
for (unsigned i = 3, e = GEP->getNumOperands(); i != e; ++i) {
ConstantInt *Idx = dyn_cast<ConstantInt>(GEP->getOperand(i));
if (!Idx) return nullptr;
uint64_t IdxVal = Idx->getZExtValue();
if ((unsigned)IdxVal != IdxVal) return nullptr;
if (StructType *STy = dyn_cast<StructType>(EltTy))
EltTy = STy->getElementType(IdxVal);
else if (ArrayType *ATy = dyn_cast<ArrayType>(EltTy)) {
if (IdxVal >= ATy->getNumElements()) return nullptr;
EltTy = ATy->getElementType();
} else {
return nullptr; }
LaterIndices.push_back(IdxVal);
}
enum { Overdefined = -3, Undefined = -2 };
int FirstTrueElement = Undefined, SecondTrueElement = Undefined;
int FirstFalseElement = Undefined, SecondFalseElement = Undefined;
int TrueRangeEnd = Undefined, FalseRangeEnd = Undefined;
uint64_t MagicBitvector = 0;
Constant *CompareRHS = cast<Constant>(ICI.getOperand(1));
for (unsigned i = 0, e = ArrayElementCount; i != e; ++i) {
Constant *Elt = Init->getAggregateElement(i);
if (!Elt) return nullptr;
if (!LaterIndices.empty())
Elt = ConstantExpr::getExtractValue(Elt, LaterIndices);
if (AndCst) Elt = ConstantExpr::getAnd(Elt, AndCst);
Constant *C = ConstantFoldCompareInstOperands(ICI.getPredicate(), Elt,
CompareRHS, DL, TLI);
if (isa<UndefValue>(C)) {
if (TrueRangeEnd == (int)i-1)
TrueRangeEnd = i;
if (FalseRangeEnd == (int)i-1)
FalseRangeEnd = i;
continue;
}
if (!isa<ConstantInt>(C)) return nullptr;
bool IsTrueForElt = !cast<ConstantInt>(C)->isZero();
if (IsTrueForElt) {
if (FirstTrueElement == Undefined)
FirstTrueElement = TrueRangeEnd = i; else {
if (SecondTrueElement == Undefined)
SecondTrueElement = i;
else
SecondTrueElement = Overdefined;
if (TrueRangeEnd == (int)i-1)
TrueRangeEnd = i;
else
TrueRangeEnd = Overdefined;
}
} else {
if (FirstFalseElement == Undefined)
FirstFalseElement = FalseRangeEnd = i; else {
if (SecondFalseElement == Undefined)
SecondFalseElement = i;
else
SecondFalseElement = Overdefined;
if (FalseRangeEnd == (int)i-1)
FalseRangeEnd = i;
else
FalseRangeEnd = Overdefined;
}
}
if (i < 64 && IsTrueForElt)
MagicBitvector |= 1ULL << i;
if ((i & 8) == 0 && i >= 64 && SecondTrueElement == Overdefined &&
SecondFalseElement == Overdefined && TrueRangeEnd == Overdefined &&
FalseRangeEnd == Overdefined)
return nullptr;
}
Value *Idx = GEP->getOperand(2);
if (!GEP->isInBounds()) {
Type *IntPtrTy = DL->getIntPtrType(GEP->getType());
unsigned PtrSize = IntPtrTy->getIntegerBitWidth();
if (Idx->getType()->getPrimitiveSizeInBits() > PtrSize)
Idx = Builder->CreateTrunc(Idx, IntPtrTy);
}
if (SecondTrueElement != Overdefined) {
if (FirstTrueElement == Undefined)
return ReplaceInstUsesWith(ICI, Builder->getFalse());
Value *FirstTrueIdx = ConstantInt::get(Idx->getType(), FirstTrueElement);
if (SecondTrueElement == Undefined)
return new ICmpInst(ICmpInst::ICMP_EQ, Idx, FirstTrueIdx);
Value *C1 = Builder->CreateICmpEQ(Idx, FirstTrueIdx);
Value *SecondTrueIdx = ConstantInt::get(Idx->getType(), SecondTrueElement);
Value *C2 = Builder->CreateICmpEQ(Idx, SecondTrueIdx);
return BinaryOperator::CreateOr(C1, C2);
}
if (SecondFalseElement != Overdefined) {
if (FirstFalseElement == Undefined)
return ReplaceInstUsesWith(ICI, Builder->getTrue());
Value *FirstFalseIdx = ConstantInt::get(Idx->getType(), FirstFalseElement);
if (SecondFalseElement == Undefined)
return new ICmpInst(ICmpInst::ICMP_NE, Idx, FirstFalseIdx);
Value *C1 = Builder->CreateICmpNE(Idx, FirstFalseIdx);
Value *SecondFalseIdx = ConstantInt::get(Idx->getType(),SecondFalseElement);
Value *C2 = Builder->CreateICmpNE(Idx, SecondFalseIdx);
return BinaryOperator::CreateAnd(C1, C2);
}
if (TrueRangeEnd != Overdefined) {
assert(TrueRangeEnd != FirstTrueElement && "Should emit single compare");
if (FirstTrueElement) {
Value *Offs = ConstantInt::get(Idx->getType(), -FirstTrueElement);
Idx = Builder->CreateAdd(Idx, Offs);
}
Value *End = ConstantInt::get(Idx->getType(),
TrueRangeEnd-FirstTrueElement+1);
return new ICmpInst(ICmpInst::ICMP_ULT, Idx, End);
}
if (FalseRangeEnd != Overdefined) {
assert(FalseRangeEnd != FirstFalseElement && "Should emit single compare");
if (FirstFalseElement) {
Value *Offs = ConstantInt::get(Idx->getType(), -FirstFalseElement);
Idx = Builder->CreateAdd(Idx, Offs);
}
Value *End = ConstantInt::get(Idx->getType(),
FalseRangeEnd-FirstFalseElement);
return new ICmpInst(ICmpInst::ICMP_UGT, Idx, End);
}
{
Type *Ty = nullptr;
if (ArrayElementCount <= Idx->getType()->getIntegerBitWidth())
Ty = Idx->getType();
else if (DL)
Ty = DL->getSmallestLegalIntType(Init->getContext(), ArrayElementCount);
else if (ArrayElementCount <= 32)
Ty = Type::getInt32Ty(Init->getContext());
if (Ty) {
Value *V = Builder->CreateIntCast(Idx, Ty, false);
V = Builder->CreateLShr(ConstantInt::get(Ty, MagicBitvector), V);
V = Builder->CreateAnd(ConstantInt::get(Ty, 1), V);
return new ICmpInst(ICmpInst::ICMP_NE, V, ConstantInt::get(Ty, 0));
}
}
return nullptr;
}
static Value *EvaluateGEPOffsetExpression(User *GEP, InstCombiner &IC) {
const DataLayout &DL = *IC.getDataLayout();
gep_type_iterator GTI = gep_type_begin(GEP);
unsigned i, e = GEP->getNumOperands();
int64_t Offset = 0;
for (i = 1; i != e; ++i, ++GTI) {
if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i))) {
if (CI->isZero()) continue;
if (StructType *STy = dyn_cast<StructType>(*GTI)) {
Offset += DL.getStructLayout(STy)->getElementOffset(CI->getZExtValue());
} else {
uint64_t Size = DL.getTypeAllocSize(GTI.getIndexedType());
Offset += Size*CI->getSExtValue();
}
} else {
break;
}
}
if (i == e) return nullptr;
Value *VariableIdx = GEP->getOperand(i);
uint64_t VariableScale = DL.getTypeAllocSize(GTI.getIndexedType());
for (++i, ++GTI; i != e; ++i, ++GTI) {
ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i));
if (!CI) return nullptr;
if (CI->isZero()) continue;
if (StructType *STy = dyn_cast<StructType>(*GTI)) {
Offset += DL.getStructLayout(STy)->getElementOffset(CI->getZExtValue());
} else {
uint64_t Size = DL.getTypeAllocSize(GTI.getIndexedType());
Offset += Size*CI->getSExtValue();
}
}
Type *IntPtrTy = DL.getIntPtrType(GEP->getOperand(0)->getType());
unsigned IntPtrWidth = IntPtrTy->getIntegerBitWidth();
if (Offset == 0) {
if (VariableIdx->getType()->getPrimitiveSizeInBits() > IntPtrWidth) {
VariableIdx = IC.Builder->CreateTrunc(VariableIdx, IntPtrTy);
}
return VariableIdx;
}
uint64_t PtrSizeMask = ~0ULL >> (64-IntPtrWidth);
Offset &= PtrSizeMask;
VariableScale &= PtrSizeMask;
int64_t NewOffs = Offset / (int64_t)VariableScale;
if (Offset != NewOffs*(int64_t)VariableScale)
return nullptr;
if (VariableIdx->getType() != IntPtrTy)
VariableIdx = IC.Builder->CreateIntCast(VariableIdx, IntPtrTy,
true );
Constant *OffsetVal = ConstantInt::get(IntPtrTy, NewOffs);
return IC.Builder->CreateAdd(VariableIdx, OffsetVal, "offset");
}
Instruction *InstCombiner::FoldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
ICmpInst::Predicate Cond,
Instruction &I) {
if (ICmpInst::isSigned(Cond))
return nullptr;
if (!isa<GetElementPtrInst>(RHS))
RHS = RHS->stripPointerCasts();
Value *PtrBase = GEPLHS->getOperand(0);
if (DL && PtrBase == RHS && GEPLHS->isInBounds()) {
Value *Offset = EvaluateGEPOffsetExpression(GEPLHS, *this);
if (!Offset)
Offset = EmitGEPOffset(GEPLHS);
return new ICmpInst(ICmpInst::getSignedPredicate(Cond), Offset,
Constant::getNullValue(Offset->getType()));
} else if (GEPOperator *GEPRHS = dyn_cast<GEPOperator>(RHS)) {
if (PtrBase != GEPRHS->getOperand(0)) {
bool IndicesTheSame = GEPLHS->getNumOperands()==GEPRHS->getNumOperands();
IndicesTheSame &= GEPLHS->getOperand(0)->getType() ==
GEPRHS->getOperand(0)->getType();
if (IndicesTheSame)
for (unsigned i = 1, e = GEPLHS->getNumOperands(); i != e; ++i)
if (GEPLHS->getOperand(i) != GEPRHS->getOperand(i)) {
IndicesTheSame = false;
break;
}
if (IndicesTheSame)
return new ICmpInst(Cond, GEPLHS->getOperand(0), GEPRHS->getOperand(0));
if (DL && GEPLHS->isInBounds() && GEPRHS->isInBounds() &&
(GEPLHS->hasAllConstantIndices() || GEPLHS->hasOneUse()) &&
(GEPRHS->hasAllConstantIndices() || GEPRHS->hasOneUse()) &&
PtrBase->stripPointerCasts() ==
GEPRHS->getOperand(0)->stripPointerCasts()) {
Value *LOffset = EmitGEPOffset(GEPLHS);
Value *ROffset = EmitGEPOffset(GEPRHS);
Type *LHSIndexTy = LOffset->getType();
Type *RHSIndexTy = ROffset->getType();
if (LHSIndexTy != RHSIndexTy) {
if (LHSIndexTy->getPrimitiveSizeInBits() <
RHSIndexTy->getPrimitiveSizeInBits()) {
ROffset = Builder->CreateTrunc(ROffset, LHSIndexTy);
} else
LOffset = Builder->CreateTrunc(LOffset, RHSIndexTy);
}
Value *Cmp = Builder->CreateICmp(ICmpInst::getSignedPredicate(Cond),
LOffset, ROffset);
return ReplaceInstUsesWith(I, Cmp);
}
return nullptr;
}
if (GEPLHS->hasAllZeroIndices())
return FoldGEPICmp(GEPRHS, GEPLHS->getOperand(0),
ICmpInst::getSwappedPredicate(Cond), I);
if (GEPRHS->hasAllZeroIndices())
return FoldGEPICmp(GEPLHS, GEPRHS->getOperand(0), Cond, I);
bool GEPsInBounds = GEPLHS->isInBounds() && GEPRHS->isInBounds();
if (GEPLHS->getNumOperands() == GEPRHS->getNumOperands()) {
unsigned NumDifferences = 0; unsigned DiffOperand = 0; for (unsigned i = 1, e = GEPRHS->getNumOperands(); i != e; ++i)
if (GEPLHS->getOperand(i) != GEPRHS->getOperand(i)) {
if (GEPLHS->getOperand(i)->getType()->getPrimitiveSizeInBits() !=
GEPRHS->getOperand(i)->getType()->getPrimitiveSizeInBits()) {
NumDifferences = 2;
break;
} else {
if (NumDifferences++) break;
DiffOperand = i;
}
}
if (NumDifferences == 0) return ReplaceInstUsesWith(I, Builder->getInt1(ICmpInst::isTrueWhenEqual(Cond)));
else if (NumDifferences == 1 && GEPsInBounds) {
Value *LHSV = GEPLHS->getOperand(DiffOperand);
Value *RHSV = GEPRHS->getOperand(DiffOperand);
return new ICmpInst(ICmpInst::getSignedPredicate(Cond), LHSV, RHSV);
}
}
if (DL &&
GEPsInBounds &&
(isa<ConstantExpr>(GEPLHS) || GEPLHS->hasOneUse()) &&
(isa<ConstantExpr>(GEPRHS) || GEPRHS->hasOneUse())) {
Value *L = EmitGEPOffset(GEPLHS);
Value *R = EmitGEPOffset(GEPRHS);
return new ICmpInst(ICmpInst::getSignedPredicate(Cond), L, R);
}
}
return nullptr;
}
Instruction *InstCombiner::FoldICmpAddOpCst(Instruction &ICI,
Value *X, ConstantInt *CI,
ICmpInst::Predicate Pred) {
if (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_ULE) {
Value *R =
ConstantExpr::getSub(ConstantInt::getAllOnesValue(CI->getType()), CI);
return new ICmpInst(ICmpInst::ICMP_UGT, X, R);
}
if (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE)
return new ICmpInst(ICmpInst::ICMP_ULT, X, ConstantExpr::getNeg(CI));
unsigned BitWidth = CI->getType()->getPrimitiveSizeInBits();
ConstantInt *SMax = ConstantInt::get(X->getContext(),
APInt::getSignedMaxValue(BitWidth));
if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE)
return new ICmpInst(ICmpInst::ICMP_SGT, X, ConstantExpr::getSub(SMax, CI));
assert(Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SGE);
Constant *C = Builder->getInt(CI->getValue()-1);
return new ICmpInst(ICmpInst::ICMP_SLT, X, ConstantExpr::getSub(SMax, C));
}
Instruction *InstCombiner::FoldICmpDivCst(ICmpInst &ICI, BinaryOperator *DivI,
ConstantInt *DivRHS) {
ConstantInt *CmpRHS = cast<ConstantInt>(ICI.getOperand(1));
const APInt &CmpRHSV = CmpRHS->getValue();
bool DivIsSigned = DivI->getOpcode() == Instruction::SDiv;
if (!ICI.isEquality() && DivIsSigned != ICI.isSigned())
return nullptr;
if (DivRHS->isZero())
return nullptr; if (DivIsSigned && DivRHS->isAllOnesValue())
return nullptr; if (DivRHS->isOne()) {
ICI.setOperand(0, DivI->getOperand(0)); return &ICI;
}
Constant *Prod = ConstantExpr::getMul(CmpRHS, DivRHS);
bool ProdOV = (DivIsSigned ? ConstantExpr::getSDiv(Prod, DivRHS) :
ConstantExpr::getUDiv(Prod, DivRHS)) != CmpRHS;
ICmpInst::Predicate Pred = ICI.getPredicate();
ConstantInt *RangeSize = DivI->isExact() ? getOne(Prod) : DivRHS;
int LoOverflow = 0, HiOverflow = 0;
Constant *LoBound = nullptr, *HiBound = nullptr;
if (!DivIsSigned) { LoBound = Prod;
HiOverflow = LoOverflow = ProdOV;
if (!HiOverflow) {
HiOverflow = AddWithOverflow(HiBound, LoBound, RangeSize, false);
}
} else if (DivRHS->getValue().isStrictlyPositive()) { if (CmpRHSV == 0) { LoBound = ConstantExpr::getNeg(SubOne(RangeSize));
HiBound = RangeSize;
} else if (CmpRHSV.isStrictlyPositive()) { LoBound = Prod; HiOverflow = LoOverflow = ProdOV;
if (!HiOverflow)
HiOverflow = AddWithOverflow(HiBound, Prod, RangeSize, true);
} else { HiBound = AddOne(Prod);
LoOverflow = HiOverflow = ProdOV ? -1 : 0;
if (!LoOverflow) {
ConstantInt *DivNeg =cast<ConstantInt>(ConstantExpr::getNeg(RangeSize));
LoOverflow = AddWithOverflow(LoBound, HiBound, DivNeg, true) ? -1 : 0;
}
}
} else if (DivRHS->isNegative()) { if (DivI->isExact())
RangeSize = cast<ConstantInt>(ConstantExpr::getNeg(RangeSize));
if (CmpRHSV == 0) { LoBound = AddOne(RangeSize);
HiBound = cast<ConstantInt>(ConstantExpr::getNeg(RangeSize));
if (HiBound == DivRHS) { HiOverflow = 1; HiBound = nullptr; }
} else if (CmpRHSV.isStrictlyPositive()) { HiBound = AddOne(Prod);
HiOverflow = LoOverflow = ProdOV ? -1 : 0;
if (!LoOverflow)
LoOverflow = AddWithOverflow(LoBound, HiBound, RangeSize, true) ? -1:0;
} else { LoBound = Prod; LoOverflow = HiOverflow = ProdOV;
if (!HiOverflow)
HiOverflow = SubWithOverflow(HiBound, Prod, RangeSize, true);
}
Pred = ICmpInst::getSwappedPredicate(Pred);
}
Value *X = DivI->getOperand(0);
switch (Pred) {
default: llvm_unreachable("Unhandled icmp opcode!");
case ICmpInst::ICMP_EQ:
if (LoOverflow && HiOverflow)
return ReplaceInstUsesWith(ICI, Builder->getFalse());
if (HiOverflow)
return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SGE :
ICmpInst::ICMP_UGE, X, LoBound);
if (LoOverflow)
return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SLT :
ICmpInst::ICMP_ULT, X, HiBound);
return ReplaceInstUsesWith(ICI, InsertRangeTest(X, LoBound, HiBound,
DivIsSigned, true));
case ICmpInst::ICMP_NE:
if (LoOverflow && HiOverflow)
return ReplaceInstUsesWith(ICI, Builder->getTrue());
if (HiOverflow)
return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SLT :
ICmpInst::ICMP_ULT, X, LoBound);
if (LoOverflow)
return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SGE :
ICmpInst::ICMP_UGE, X, HiBound);
return ReplaceInstUsesWith(ICI, InsertRangeTest(X, LoBound, HiBound,
DivIsSigned, false));
case ICmpInst::ICMP_ULT:
case ICmpInst::ICMP_SLT:
if (LoOverflow == +1) return ReplaceInstUsesWith(ICI, Builder->getTrue());
if (LoOverflow == -1) return ReplaceInstUsesWith(ICI, Builder->getFalse());
return new ICmpInst(Pred, X, LoBound);
case ICmpInst::ICMP_UGT:
case ICmpInst::ICMP_SGT:
if (HiOverflow == +1) return ReplaceInstUsesWith(ICI, Builder->getFalse());
if (HiOverflow == -1) return ReplaceInstUsesWith(ICI, Builder->getTrue());
if (Pred == ICmpInst::ICMP_UGT)
return new ICmpInst(ICmpInst::ICMP_UGE, X, HiBound);
return new ICmpInst(ICmpInst::ICMP_SGE, X, HiBound);
}
}
Instruction *InstCombiner::FoldICmpShrCst(ICmpInst &ICI, BinaryOperator *Shr,
ConstantInt *ShAmt) {
const APInt &CmpRHSV = cast<ConstantInt>(ICI.getOperand(1))->getValue();
uint32_t TypeBits = CmpRHSV.getBitWidth();
uint32_t ShAmtVal = (uint32_t)ShAmt->getLimitedValue(TypeBits);
if (ShAmtVal >= TypeBits || ShAmtVal == 0)
return nullptr;
if (!ICI.isEquality()) {
if (ICI.isSigned() != (Shr->getOpcode() == Instruction::AShr))
return nullptr;
if (Shr->getOpcode() == Instruction::AShr &&
(!Shr->isExact() || ShAmtVal == TypeBits - 1))
return nullptr;
Worklist.Add(Shr);
Constant *DivCst =
ConstantInt::get(Shr->getType(), APInt::getOneBitSet(TypeBits, ShAmtVal));
Value *Tmp =
Shr->getOpcode() == Instruction::AShr ?
Builder->CreateSDiv(Shr->getOperand(0), DivCst, "", Shr->isExact()) :
Builder->CreateUDiv(Shr->getOperand(0), DivCst, "", Shr->isExact());
ICI.setOperand(0, Tmp);
BinaryOperator *TheDiv = dyn_cast<BinaryOperator>(Tmp);
if (!TheDiv)
return &ICI;
assert(TheDiv->getOpcode() == Instruction::SDiv ||
TheDiv->getOpcode() == Instruction::UDiv);
Instruction *Res = FoldICmpDivCst(ICI, TheDiv, cast<ConstantInt>(DivCst));
assert(Res && "This div/cst should have folded!");
return Res;
}
APInt Comp = CmpRHSV << ShAmtVal;
ConstantInt *ShiftedCmpRHS = Builder->getInt(Comp);
if (Shr->getOpcode() == Instruction::LShr)
Comp = Comp.lshr(ShAmtVal);
else
Comp = Comp.ashr(ShAmtVal);
if (Comp != CmpRHSV) { bool IsICMP_NE = ICI.getPredicate() == ICmpInst::ICMP_NE;
Constant *Cst = Builder->getInt1(IsICMP_NE);
return ReplaceInstUsesWith(ICI, Cst);
}
if (Shr->hasOneUse() && Shr->isExact())
return new ICmpInst(ICI.getPredicate(), Shr->getOperand(0), ShiftedCmpRHS);
if (Shr->hasOneUse()) {
APInt Val(APInt::getHighBitsSet(TypeBits, TypeBits - ShAmtVal));
Constant *Mask = Builder->getInt(Val);
Value *And = Builder->CreateAnd(Shr->getOperand(0),
Mask, Shr->getName()+".mask");
return new ICmpInst(ICI.getPredicate(), And, ShiftedCmpRHS);
}
return nullptr;
}
Instruction *InstCombiner::FoldICmpCstShrCst(ICmpInst &I, Value *Op, Value *A,
ConstantInt *CI1,
ConstantInt *CI2) {
assert(I.isEquality() && "Cannot fold icmp gt/lt");
auto getConstant = [&I, this](bool IsTrue) {
if (I.getPredicate() == I.ICMP_NE)
IsTrue = !IsTrue;
return ReplaceInstUsesWith(I, ConstantInt::get(I.getType(), IsTrue));
};
auto getICmp = [&I](CmpInst::Predicate Pred, Value *LHS, Value *RHS) {
if (I.getPredicate() == I.ICMP_NE)
Pred = CmpInst::getInversePredicate(Pred);
return new ICmpInst(Pred, LHS, RHS);
};
APInt AP1 = CI1->getValue();
APInt AP2 = CI2->getValue();
if (!AP1) {
if (!AP2) {
return getConstant(true);
}
if (cast<BinaryOperator>(Op)->isExact())
return getConstant(false);
if (AP2.isNegative()) {
return getConstant(false);
}
return getICmp(I.ICMP_UGT, A,
ConstantInt::get(A->getType(), AP2.logBase2()));
}
if (!AP2) {
return getConstant(false);
}
bool IsAShr = isa<AShrOperator>(Op);
if (AP1 == AP2) {
if (AP1.isAllOnesValue() && IsAShr) {
return getConstant(true);
}
return getICmp(I.ICMP_EQ, A, ConstantInt::getNullValue(A->getType()));
}
bool IsNegative = false;
if (IsAShr) {
if (AP1.isNegative() != AP2.isNegative()) {
return getConstant(false);
}
if (AP1.isNegative()) {
if (AP1.slt(AP2))
return getConstant(false);
IsNegative = true;
}
}
if (!IsNegative && AP1.ugt(AP2))
return getConstant(false);
int Shift;
if (IsNegative)
Shift = (~AP2).logBase2() - (~AP1).logBase2();
else
Shift = AP2.logBase2() - AP1.logBase2();
if (IsAShr ? AP1 == AP2.ashr(Shift) : AP1 == AP2.lshr(Shift))
return getICmp(I.ICMP_EQ, A, ConstantInt::get(A->getType(), Shift));
return getConstant(false);
}
Instruction *InstCombiner::visitICmpInstWithInstAndIntCst(ICmpInst &ICI,
Instruction *LHSI,
ConstantInt *RHS) {
const APInt &RHSV = RHS->getValue();
switch (LHSI->getOpcode()) {
case Instruction::Trunc:
if (ICI.isEquality() && LHSI->hasOneUse()) {
unsigned DstBits = LHSI->getType()->getPrimitiveSizeInBits(),
SrcBits = LHSI->getOperand(0)->getType()->getPrimitiveSizeInBits();
APInt KnownZero(SrcBits, 0), KnownOne(SrcBits, 0);
computeKnownBits(LHSI->getOperand(0), KnownZero, KnownOne);
if ((KnownZero|KnownOne).countLeadingOnes() >= SrcBits-DstBits) {
APInt NewRHS = RHS->getValue().zext(SrcBits);
NewRHS |= KnownOne & APInt::getHighBitsSet(SrcBits, SrcBits-DstBits);
return new ICmpInst(ICI.getPredicate(), LHSI->getOperand(0),
Builder->getInt(NewRHS));
}
}
break;
case Instruction::Xor: if (ConstantInt *XorCst = dyn_cast<ConstantInt>(LHSI->getOperand(1))) {
if ((ICI.getPredicate() == ICmpInst::ICMP_SLT && RHSV == 0) ||
(ICI.getPredicate() == ICmpInst::ICMP_SGT && RHSV.isAllOnesValue())) {
Value *CompareVal = LHSI->getOperand(0);
if (!XorCst->isNegative()) {
ICI.setOperand(0, CompareVal);
Worklist.Add(LHSI);
return &ICI;
}
bool isTrueIfPositive = ICI.getPredicate() == ICmpInst::ICMP_SGT;
isTrueIfPositive ^= true;
if (isTrueIfPositive)
return new ICmpInst(ICmpInst::ICMP_SGT, CompareVal,
SubOne(RHS));
else
return new ICmpInst(ICmpInst::ICMP_SLT, CompareVal,
AddOne(RHS));
}
if (LHSI->hasOneUse()) {
if (!ICI.isEquality() && XorCst->getValue().isSignBit()) {
const APInt &SignBit = XorCst->getValue();
ICmpInst::Predicate Pred = ICI.isSigned()
? ICI.getUnsignedPredicate()
: ICI.getSignedPredicate();
return new ICmpInst(Pred, LHSI->getOperand(0),
Builder->getInt(RHSV ^ SignBit));
}
if (!ICI.isEquality() && XorCst->isMaxValue(true)) {
const APInt &NotSignBit = XorCst->getValue();
ICmpInst::Predicate Pred = ICI.isSigned()
? ICI.getUnsignedPredicate()
: ICI.getSignedPredicate();
Pred = ICI.getSwappedPredicate(Pred);
return new ICmpInst(Pred, LHSI->getOperand(0),
Builder->getInt(RHSV ^ NotSignBit));
}
}
if (ICI.getPredicate() == ICmpInst::ICMP_UGT &&
XorCst->getValue() == ~RHSV && (RHSV + 1).isPowerOf2())
return new ICmpInst(ICmpInst::ICMP_ULT, LHSI->getOperand(0), XorCst);
if (ICI.getPredicate() == ICmpInst::ICMP_ULT &&
XorCst->getValue() == -RHSV && RHSV.isPowerOf2())
return new ICmpInst(ICmpInst::ICMP_UGE, LHSI->getOperand(0), XorCst);
}
break;
case Instruction::And: if (LHSI->hasOneUse() && isa<ConstantInt>(LHSI->getOperand(1)) &&
LHSI->getOperand(0)->hasOneUse()) {
ConstantInt *AndCst = cast<ConstantInt>(LHSI->getOperand(1));
if (TruncInst *Cast = dyn_cast<TruncInst>(LHSI->getOperand(0))) {
if (ICI.isEquality() ||
(!AndCst->isNegative() && RHSV.isNonNegative())) {
Value *NewAnd =
Builder->CreateAnd(Cast->getOperand(0),
ConstantExpr::getZExt(AndCst, Cast->getSrcTy()));
NewAnd->takeName(LHSI);
return new ICmpInst(ICI.getPredicate(), NewAnd,
ConstantExpr::getZExt(RHS, Cast->getSrcTy()));
}
}
if (ZExtInst *Cast = dyn_cast<ZExtInst>(LHSI->getOperand(0))) {
IntegerType *Ty = cast<IntegerType>(Cast->getSrcTy());
if (ICI.isEquality() && RHSV.getActiveBits() <= Ty->getBitWidth()) {
Value *NewAnd =
Builder->CreateAnd(Cast->getOperand(0),
ConstantExpr::getTrunc(AndCst, Ty));
NewAnd->takeName(LHSI);
return new ICmpInst(ICI.getPredicate(), NewAnd,
ConstantExpr::getTrunc(RHS, Ty));
}
}
BinaryOperator *Shift = dyn_cast<BinaryOperator>(LHSI->getOperand(0));
if (Shift && !Shift->isShift())
Shift = nullptr;
ConstantInt *ShAmt;
ShAmt = Shift ? dyn_cast<ConstantInt>(Shift->getOperand(1)) : nullptr;
if (ShAmt) {
bool CanFold = false;
unsigned ShiftOpcode = Shift->getOpcode();
if (ShiftOpcode == Instruction::AShr) {
CanFold = false;
} else if (ShiftOpcode == Instruction::Shl) {
if (!ICI.isSigned() || (!AndCst->isNegative() && !RHS->isNegative()))
CanFold = true;
} else if (ShiftOpcode == Instruction::LShr) {
if (!ICI.isSigned())
CanFold = true;
else {
ConstantInt *ShiftedAndCst =
cast<ConstantInt>(ConstantExpr::getShl(AndCst, ShAmt));
ConstantInt *ShiftedRHSCst =
cast<ConstantInt>(ConstantExpr::getShl(RHS, ShAmt));
if (!ShiftedAndCst->isNegative() && !ShiftedRHSCst->isNegative())
CanFold = true;
}
}
if (CanFold) {
Constant *NewCst;
if (ShiftOpcode == Instruction::Shl)
NewCst = ConstantExpr::getLShr(RHS, ShAmt);
else
NewCst = ConstantExpr::getShl(RHS, ShAmt);
if (ConstantExpr::get(ShiftOpcode, NewCst, ShAmt) != RHS) {
if (ICI.getPredicate() == ICmpInst::ICMP_EQ)
return ReplaceInstUsesWith(ICI, Builder->getFalse());
if (ICI.getPredicate() == ICmpInst::ICMP_NE)
return ReplaceInstUsesWith(ICI, Builder->getTrue());
} else {
ICI.setOperand(1, NewCst);
Constant *NewAndCst;
if (ShiftOpcode == Instruction::Shl)
NewAndCst = ConstantExpr::getLShr(AndCst, ShAmt);
else
NewAndCst = ConstantExpr::getShl(AndCst, ShAmt);
LHSI->setOperand(1, NewAndCst);
LHSI->setOperand(0, Shift->getOperand(0));
Worklist.Add(Shift); return &ICI;
}
}
}
if (Shift && Shift->hasOneUse() && RHSV == 0 &&
ICI.isEquality() && !Shift->isArithmeticShift() &&
!isa<Constant>(Shift->getOperand(0))) {
Value *NS;
if (Shift->getOpcode() == Instruction::LShr) {
NS = Builder->CreateShl(AndCst, Shift->getOperand(1));
} else {
NS = Builder->CreateLShr(AndCst, Shift->getOperand(1));
}
Value *NewAnd =
Builder->CreateAnd(Shift->getOperand(0), NS, LHSI->getName());
ICI.setOperand(0, NewAnd);
return &ICI;
}
if (ICI.getPredicate() == ICmpInst::ICMP_UGT) {
unsigned NTZ = AndCst->getValue().countTrailingZeros();
if ((NTZ < AndCst->getBitWidth()) &&
APInt::getOneBitSet(AndCst->getBitWidth(), NTZ).ugt(RHSV))
return new ICmpInst(ICmpInst::ICMP_NE, LHSI,
Constant::getNullValue(RHS->getType()));
}
}
if (LoadInst *LI = dyn_cast<LoadInst>(LHSI->getOperand(0))) {
if (GetElementPtrInst *GEP =
dyn_cast<GetElementPtrInst>(LI->getOperand(0)))
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0)))
if (GV->isConstant() && GV->hasDefinitiveInitializer() &&
!LI->isVolatile() && isa<ConstantInt>(LHSI->getOperand(1))) {
ConstantInt *C = cast<ConstantInt>(LHSI->getOperand(1));
if (Instruction *Res = FoldCmpLoadFromIndexedGlobal(GEP, GV,ICI, C))
return Res;
}
}
if (ICI.isEquality() && RHS == LHSI->getOperand(1) && (-RHSV).isPowerOf2())
return new ICmpInst(
ICI.getPredicate() == ICmpInst::ICMP_EQ ? ICmpInst::ICMP_UGT
: ICmpInst::ICMP_ULE,
LHSI->getOperand(0), SubOne(RHS));
break;
case Instruction::Or: {
if (!ICI.isEquality() || !RHS->isNullValue() || !LHSI->hasOneUse())
break;
Value *P, *Q;
if (match(LHSI, m_Or(m_PtrToInt(m_Value(P)), m_PtrToInt(m_Value(Q))))) {
Value *ICIP = Builder->CreateICmp(ICI.getPredicate(), P,
Constant::getNullValue(P->getType()));
Value *ICIQ = Builder->CreateICmp(ICI.getPredicate(), Q,
Constant::getNullValue(Q->getType()));
Instruction *Op;
if (ICI.getPredicate() == ICmpInst::ICMP_EQ)
Op = BinaryOperator::CreateAnd(ICIP, ICIQ);
else
Op = BinaryOperator::CreateOr(ICIP, ICIQ);
return Op;
}
break;
}
case Instruction::Mul: { ConstantInt *Val = dyn_cast<ConstantInt>(LHSI->getOperand(1));
if (!Val) break;
ICmpInst::Predicate pred = ICI.getPredicate();
if (isSignTest(pred, RHS) && !Val->isZero() &&
cast<BinaryOperator>(LHSI)->hasNoSignedWrap())
return new ICmpInst(Val->isNegative() ?
ICmpInst::getSwappedPredicate(pred) : pred,
LHSI->getOperand(0),
Constant::getNullValue(RHS->getType()));
break;
}
case Instruction::Shl: { uint32_t TypeBits = RHSV.getBitWidth();
ConstantInt *ShAmt = dyn_cast<ConstantInt>(LHSI->getOperand(1));
if (!ShAmt) {
Value *X;
if (match(LHSI, m_Shl(m_One(), m_Value(X)))) {
bool RHSVIsPowerOf2 = RHSV.isPowerOf2();
ICmpInst::Predicate Pred = ICI.getPredicate();
if (ICI.isUnsigned()) {
if (!RHSVIsPowerOf2) {
if (Pred == ICmpInst::ICMP_ULT)
Pred = ICmpInst::ICMP_ULE;
else if (Pred == ICmpInst::ICMP_UGE)
Pred = ICmpInst::ICMP_UGT;
}
unsigned RHSLog2 = RHSV.logBase2();
if (RHSLog2 == TypeBits-1) {
if (Pred == ICmpInst::ICMP_UGE)
Pred = ICmpInst::ICMP_EQ;
else if (Pred == ICmpInst::ICMP_UGT)
return ReplaceInstUsesWith(ICI, Builder->getFalse());
else if (Pred == ICmpInst::ICMP_ULE)
return ReplaceInstUsesWith(ICI, Builder->getTrue());
else if (Pred == ICmpInst::ICMP_ULT)
Pred = ICmpInst::ICMP_NE;
}
return new ICmpInst(Pred, X,
ConstantInt::get(RHS->getType(), RHSLog2));
} else if (ICI.isSigned()) {
if (RHSV.isAllOnesValue()) {
if (Pred == ICmpInst::ICMP_SLE)
return new ICmpInst(ICmpInst::ICMP_EQ, X,
ConstantInt::get(RHS->getType(), TypeBits-1));
if (Pred == ICmpInst::ICMP_SGT)
return new ICmpInst(ICmpInst::ICMP_NE, X,
ConstantInt::get(RHS->getType(), TypeBits-1));
} else if (!RHSV) {
if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE)
return new ICmpInst(ICmpInst::ICMP_EQ, X,
ConstantInt::get(RHS->getType(), TypeBits-1));
if (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SGE)
return new ICmpInst(ICmpInst::ICMP_NE, X,
ConstantInt::get(RHS->getType(), TypeBits-1));
}
} else if (ICI.isEquality()) {
if (RHSVIsPowerOf2)
return new ICmpInst(
Pred, X, ConstantInt::get(RHS->getType(), RHSV.logBase2()));
return ReplaceInstUsesWith(
ICI, Pred == ICmpInst::ICMP_EQ ? Builder->getFalse()
: Builder->getTrue());
}
}
break;
}
if (ShAmt->uge(TypeBits))
break;
if (ICI.isEquality()) {
Constant *Comp =
ConstantExpr::getShl(ConstantExpr::getLShr(RHS, ShAmt),
ShAmt);
if (Comp != RHS) { bool IsICMP_NE = ICI.getPredicate() == ICmpInst::ICMP_NE;
Constant *Cst = Builder->getInt1(IsICMP_NE);
return ReplaceInstUsesWith(ICI, Cst);
}
if (cast<BinaryOperator>(LHSI)->hasNoUnsignedWrap())
return new ICmpInst(ICI.getPredicate(), LHSI->getOperand(0),
ConstantExpr::getLShr(RHS, ShAmt));
if (cast<BinaryOperator>(LHSI)->hasNoSignedWrap() && RHSV == 0)
return new ICmpInst(ICI.getPredicate(), LHSI->getOperand(0),
ConstantExpr::getLShr(RHS, ShAmt));
if (LHSI->hasOneUse()) {
uint32_t ShAmtVal = (uint32_t)ShAmt->getLimitedValue(TypeBits);
Constant *Mask = Builder->getInt(APInt::getLowBitsSet(TypeBits,
TypeBits - ShAmtVal));
Value *And =
Builder->CreateAnd(LHSI->getOperand(0),Mask, LHSI->getName()+".mask");
return new ICmpInst(ICI.getPredicate(), And,
ConstantExpr::getLShr(RHS, ShAmt));
}
}
ICmpInst::Predicate pred = ICI.getPredicate();
if (isSignTest(pred, RHS) &&
cast<BinaryOperator>(LHSI)->hasNoSignedWrap())
return new ICmpInst(pred,
LHSI->getOperand(0),
Constant::getNullValue(RHS->getType()));
bool TrueIfSigned = false;
if (LHSI->hasOneUse() &&
isSignBitCheck(ICI.getPredicate(), RHS, TrueIfSigned)) {
Constant *Mask = ConstantInt::get(LHSI->getOperand(0)->getType(),
APInt::getOneBitSet(TypeBits,
TypeBits-ShAmt->getZExtValue()-1));
Value *And =
Builder->CreateAnd(LHSI->getOperand(0), Mask, LHSI->getName()+".mask");
return new ICmpInst(TrueIfSigned ? ICmpInst::ICMP_NE : ICmpInst::ICMP_EQ,
And, Constant::getNullValue(And->getType()));
}
unsigned Amt = ShAmt->getLimitedValue(TypeBits-1);
if (LHSI->hasOneUse() &&
Amt != 0 && RHSV.countTrailingZeros() >= Amt) {
Type *NTy = IntegerType::get(ICI.getContext(), TypeBits - Amt);
Constant *NCI = ConstantExpr::getTrunc(
ConstantExpr::getAShr(RHS,
ConstantInt::get(RHS->getType(), Amt)),
NTy);
return new ICmpInst(ICI.getPredicate(),
Builder->CreateTrunc(LHSI->getOperand(0), NTy),
NCI);
}
break;
}
case Instruction::LShr: case Instruction::AShr: {
BinaryOperator *BO = cast<BinaryOperator>(LHSI);
if (ConstantInt *ShAmt = dyn_cast<ConstantInt>(LHSI->getOperand(1))) {
if (Instruction *Res = FoldICmpShrCst(ICI, BO, ShAmt))
return Res;
}
if (ICI.isEquality() && BO->isExact() && BO->hasOneUse()) {
if (RHSV.isMinValue())
return new ICmpInst(ICI.getPredicate(), BO->getOperand(0), RHS);
}
break;
}
case Instruction::SDiv:
case Instruction::UDiv:
if (ConstantInt *DivRHS = dyn_cast<ConstantInt>(LHSI->getOperand(1)))
if (Instruction *R = FoldICmpDivCst(ICI, cast<BinaryOperator>(LHSI),
DivRHS))
return R;
break;
case Instruction::Sub: {
ConstantInt *LHSC = dyn_cast<ConstantInt>(LHSI->getOperand(0));
if (!LHSC) break;
const APInt &LHSV = LHSC->getValue();
if (ICI.getPredicate() == ICmpInst::ICMP_ULT && LHSI->hasOneUse() &&
RHSV.isPowerOf2() && (LHSV & (RHSV - 1)) == (RHSV - 1))
return new ICmpInst(ICmpInst::ICMP_EQ,
Builder->CreateOr(LHSI->getOperand(1), RHSV - 1),
LHSC);
if (ICI.getPredicate() == ICmpInst::ICMP_UGT && LHSI->hasOneUse() &&
(RHSV + 1).isPowerOf2() && (LHSV & RHSV) == RHSV)
return new ICmpInst(ICmpInst::ICMP_NE,
Builder->CreateOr(LHSI->getOperand(1), RHSV), LHSC);
break;
}
case Instruction::Add:
if (!ICI.isEquality()) {
ConstantInt *LHSC = dyn_cast<ConstantInt>(LHSI->getOperand(1));
if (!LHSC) break;
const APInt &LHSV = LHSC->getValue();
ConstantRange CR = ICI.makeConstantRange(ICI.getPredicate(), RHSV)
.subtract(LHSV);
if (ICI.isSigned()) {
if (CR.getLower().isSignBit()) {
return new ICmpInst(ICmpInst::ICMP_SLT, LHSI->getOperand(0),
Builder->getInt(CR.getUpper()));
} else if (CR.getUpper().isSignBit()) {
return new ICmpInst(ICmpInst::ICMP_SGE, LHSI->getOperand(0),
Builder->getInt(CR.getLower()));
}
} else {
if (CR.getLower().isMinValue()) {
return new ICmpInst(ICmpInst::ICMP_ULT, LHSI->getOperand(0),
Builder->getInt(CR.getUpper()));
} else if (CR.getUpper().isMinValue()) {
return new ICmpInst(ICmpInst::ICMP_UGE, LHSI->getOperand(0),
Builder->getInt(CR.getLower()));
}
}
if (ICI.getPredicate() == ICmpInst::ICMP_ULT && LHSI->hasOneUse() &&
RHSV.isPowerOf2() && (LHSV & (RHSV - 1)) == 0)
return new ICmpInst(ICmpInst::ICMP_EQ,
Builder->CreateAnd(LHSI->getOperand(0), -RHSV),
ConstantExpr::getNeg(LHSC));
if (ICI.getPredicate() == ICmpInst::ICMP_UGT && LHSI->hasOneUse() &&
(RHSV + 1).isPowerOf2() && (LHSV & RHSV) == 0)
return new ICmpInst(ICmpInst::ICMP_NE,
Builder->CreateAnd(LHSI->getOperand(0), ~RHSV),
ConstantExpr::getNeg(LHSC));
}
break;
}
if (ICI.isEquality()) {
bool isICMP_NE = ICI.getPredicate() == ICmpInst::ICMP_NE;
if (BinaryOperator *BO = dyn_cast<BinaryOperator>(LHSI)) {
switch (BO->getOpcode()) {
case Instruction::SRem:
if (RHSV == 0 && isa<ConstantInt>(BO->getOperand(1)) &&BO->hasOneUse()){
const APInt &V = cast<ConstantInt>(BO->getOperand(1))->getValue();
if (V.sgt(1) && V.isPowerOf2()) {
Value *NewRem =
Builder->CreateURem(BO->getOperand(0), BO->getOperand(1),
BO->getName());
return new ICmpInst(ICI.getPredicate(), NewRem,
Constant::getNullValue(BO->getType()));
}
}
break;
case Instruction::Add:
if (ConstantInt *BOp1C = dyn_cast<ConstantInt>(BO->getOperand(1))) {
if (BO->hasOneUse())
return new ICmpInst(ICI.getPredicate(), BO->getOperand(0),
ConstantExpr::getSub(RHS, BOp1C));
} else if (RHSV == 0) {
Value *BOp0 = BO->getOperand(0), *BOp1 = BO->getOperand(1);
if (Value *NegVal = dyn_castNegVal(BOp1))
return new ICmpInst(ICI.getPredicate(), BOp0, NegVal);
if (Value *NegVal = dyn_castNegVal(BOp0))
return new ICmpInst(ICI.getPredicate(), NegVal, BOp1);
if (BO->hasOneUse()) {
Value *Neg = Builder->CreateNeg(BOp1);
Neg->takeName(BO);
return new ICmpInst(ICI.getPredicate(), BOp0, Neg);
}
}
break;
case Instruction::Xor:
if (Constant *BOC = dyn_cast<Constant>(BO->getOperand(1))) {
return new ICmpInst(ICI.getPredicate(), BO->getOperand(0),
ConstantExpr::getXor(RHS, BOC));
} else if (RHSV == 0) {
return new ICmpInst(ICI.getPredicate(), BO->getOperand(0),
BO->getOperand(1));
}
break;
case Instruction::Sub:
if (ConstantInt *BOp0C = dyn_cast<ConstantInt>(BO->getOperand(0))) {
if (BO->hasOneUse())
return new ICmpInst(ICI.getPredicate(), BO->getOperand(1),
ConstantExpr::getSub(BOp0C, RHS));
} else if (RHSV == 0) {
return new ICmpInst(ICI.getPredicate(), BO->getOperand(0),
BO->getOperand(1));
}
break;
case Instruction::Or:
if (ConstantInt *BOC = dyn_cast<ConstantInt>(BO->getOperand(1))) {
Constant *NotCI = ConstantExpr::getNot(RHS);
if (!ConstantExpr::getAnd(BOC, NotCI)->isNullValue())
return ReplaceInstUsesWith(ICI, Builder->getInt1(isICMP_NE));
}
break;
case Instruction::And:
if (ConstantInt *BOC = dyn_cast<ConstantInt>(BO->getOperand(1))) {
if ((RHSV & ~BOC->getValue()) != 0)
return ReplaceInstUsesWith(ICI, Builder->getInt1(isICMP_NE));
if (RHS == BOC && RHSV.isPowerOf2())
return new ICmpInst(isICMP_NE ? ICmpInst::ICMP_EQ :
ICmpInst::ICMP_NE, LHSI,
Constant::getNullValue(RHS->getType()));
if (!BO->hasOneUse())
break;
if (BOC->getValue().isSignBit()) {
Value *X = BO->getOperand(0);
Constant *Zero = Constant::getNullValue(X->getType());
ICmpInst::Predicate pred = isICMP_NE ?
ICmpInst::ICMP_SLT : ICmpInst::ICMP_SGE;
return new ICmpInst(pred, X, Zero);
}
if (RHSV == 0 && isHighOnes(BOC)) {
Value *X = BO->getOperand(0);
Constant *NegX = ConstantExpr::getNeg(BOC);
ICmpInst::Predicate pred = isICMP_NE ?
ICmpInst::ICMP_UGE : ICmpInst::ICMP_ULT;
return new ICmpInst(pred, X, NegX);
}
}
break;
case Instruction::Mul:
if (RHSV == 0 && BO->hasNoSignedWrap()) {
if (ConstantInt *BOC = dyn_cast<ConstantInt>(BO->getOperand(1))) {
if (!BOC->isZero())
return new ICmpInst(ICI.getPredicate(), BO->getOperand(0),
Constant::getNullValue(RHS->getType()));
}
}
break;
default: break;
}
} else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(LHSI)) {
switch (II->getIntrinsicID()) {
case Intrinsic::bswap:
Worklist.Add(II);
ICI.setOperand(0, II->getArgOperand(0));
ICI.setOperand(1, Builder->getInt(RHSV.byteSwap()));
return &ICI;
case Intrinsic::ctlz:
case Intrinsic::cttz:
if (RHSV == RHS->getType()->getBitWidth()) {
Worklist.Add(II);
ICI.setOperand(0, II->getArgOperand(0));
ICI.setOperand(1, ConstantInt::get(RHS->getType(), 0));
return &ICI;
}
break;
case Intrinsic::ctpop:
if (RHS->isZero()) {
Worklist.Add(II);
ICI.setOperand(0, II->getArgOperand(0));
ICI.setOperand(1, RHS);
return &ICI;
}
break;
default:
break;
}
}
}
return nullptr;
}
Instruction *InstCombiner::visitICmpInstWithCastAndCast(ICmpInst &ICI) {
const CastInst *LHSCI = cast<CastInst>(ICI.getOperand(0));
Value *LHSCIOp = LHSCI->getOperand(0);
Type *SrcTy = LHSCIOp->getType();
Type *DestTy = LHSCI->getType();
Value *RHSCIOp;
if (DL && LHSCI->getOpcode() == Instruction::PtrToInt &&
DL->getPointerTypeSizeInBits(SrcTy) == DestTy->getIntegerBitWidth()) {
Value *RHSOp = nullptr;
if (Constant *RHSC = dyn_cast<Constant>(ICI.getOperand(1))) {
RHSOp = ConstantExpr::getIntToPtr(RHSC, SrcTy);
} else if (PtrToIntInst *RHSC = dyn_cast<PtrToIntInst>(ICI.getOperand(1))) {
RHSOp = RHSC->getOperand(0);
if (LHSCIOp->getType() != RHSOp->getType())
RHSOp = Builder->CreateBitCast(RHSOp, LHSCIOp->getType());
}
if (RHSOp)
return new ICmpInst(ICI.getPredicate(), LHSCIOp, RHSOp);
}
if (LHSCI->getOpcode() != Instruction::ZExt &&
LHSCI->getOpcode() != Instruction::SExt)
return nullptr;
bool isSignedExt = LHSCI->getOpcode() == Instruction::SExt;
bool isSignedCmp = ICI.isSigned();
if (CastInst *CI = dyn_cast<CastInst>(ICI.getOperand(1))) {
RHSCIOp = CI->getOperand(0);
if (RHSCIOp->getType() != LHSCIOp->getType())
return nullptr;
if (CI->getOpcode() != LHSCI->getOpcode())
return nullptr;
if (ICI.isEquality())
return new ICmpInst(ICI.getPredicate(), LHSCIOp, RHSCIOp);
if (isSignedCmp && isSignedExt)
return new ICmpInst(ICI.getPredicate(), LHSCIOp, RHSCIOp);
return new ICmpInst(ICI.getUnsignedPredicate(), LHSCIOp, RHSCIOp);
}
ConstantInt *CI = dyn_cast<ConstantInt>(ICI.getOperand(1));
if (!CI)
return nullptr;
Constant *Res1 = ConstantExpr::getTrunc(CI, SrcTy);
Constant *Res2 = ConstantExpr::getCast(LHSCI->getOpcode(),
Res1, DestTy);
if (Res2 == CI) {
if (ICI.isEquality())
return new ICmpInst(ICI.getPredicate(), LHSCIOp, Res1);
if (isSignedExt && isSignedCmp)
return new ICmpInst(ICI.getPredicate(), LHSCIOp, Res1);
return new ICmpInst(ICI.getUnsignedPredicate(), LHSCIOp, Res1);
}
if (isSignedCmp || !isSignedExt)
return nullptr;
Constant *NegOne = Constant::getAllOnesValue(SrcTy);
Value *Result = Builder->CreateICmpSGT(LHSCIOp, NegOne, ICI.getName());
if (ICI.getPredicate() == ICmpInst::ICMP_ULT)
return ReplaceInstUsesWith(ICI, Result);
assert(ICI.getPredicate() == ICmpInst::ICMP_UGT && "ICmp should be folded!");
return BinaryOperator::CreateNot(Result);
}
static Instruction *ProcessUGT_ADDCST_ADD(ICmpInst &I, Value *A, Value *B,
ConstantInt *CI2, ConstantInt *CI1,
InstCombiner &IC) {
Instruction *AddWithCst = cast<Instruction>(I.getOperand(0));
if (!AddWithCst->hasOneUse()) return nullptr;
if (!CI2->getValue().isPowerOf2()) return nullptr;
unsigned NewWidth = CI2->getValue().countTrailingZeros();
if (NewWidth != 7 && NewWidth != 15 && NewWidth != 31) return nullptr;
++NewWidth;
if (CI1->getBitWidth() == NewWidth ||
CI1->getValue() != APInt::getLowBitsSet(CI1->getBitWidth(), NewWidth))
return nullptr;
unsigned NeededSignBits = CI1->getBitWidth() - NewWidth + 1;
if (IC.ComputeNumSignBits(A) < NeededSignBits ||
IC.ComputeNumSignBits(B) < NeededSignBits)
return nullptr;
Instruction *OrigAdd = cast<Instruction>(AddWithCst->getOperand(0));
for (User *U : OrigAdd->users()) {
if (U == AddWithCst) continue;
TruncInst *TI = dyn_cast<TruncInst>(U);
if (!TI || TI->getType()->getPrimitiveSizeInBits() > NewWidth)
return nullptr;
}
Module *M = I.getParent()->getParent()->getParent();
Type *NewType = IntegerType::get(OrigAdd->getContext(), NewWidth);
Value *F = Intrinsic::getDeclaration(M, Intrinsic::sadd_with_overflow,
NewType);
InstCombiner::BuilderTy *Builder = IC.Builder;
Builder->SetInsertPoint(OrigAdd);
Value *TruncA = Builder->CreateTrunc(A, NewType, A->getName()+".trunc");
Value *TruncB = Builder->CreateTrunc(B, NewType, B->getName()+".trunc");
CallInst *Call = Builder->CreateCall2(F, TruncA, TruncB, "sadd");
Value *Add = Builder->CreateExtractValue(Call, 0, "sadd.result");
Value *ZExt = Builder->CreateZExt(Add, OrigAdd->getType());
IC.ReplaceInstUsesWith(*OrigAdd, ZExt);
return ExtractValueInst::Create(Call, 1, "sadd.overflow");
}
static Instruction *ProcessUAddIdiom(Instruction &I, Value *OrigAddV,
InstCombiner &IC) {
if (!isa<IntegerType>(OrigAddV->getType())) return nullptr;
Instruction *OrigAdd = dyn_cast<Instruction>(OrigAddV);
if (!OrigAdd) return nullptr;
Value *LHS = OrigAdd->getOperand(0), *RHS = OrigAdd->getOperand(1);
InstCombiner::BuilderTy *Builder = IC.Builder;
Builder->SetInsertPoint(OrigAdd);
Module *M = I.getParent()->getParent()->getParent();
Type *Ty = LHS->getType();
Value *F = Intrinsic::getDeclaration(M, Intrinsic::uadd_with_overflow, Ty);
CallInst *Call = Builder->CreateCall2(F, LHS, RHS, "uadd");
Value *Add = Builder->CreateExtractValue(Call, 0);
IC.ReplaceInstUsesWith(*OrigAdd, Add);
return ExtractValueInst::Create(Call, 1, "uadd.overflow");
}
static Instruction *ProcessUMulZExtIdiom(ICmpInst &I, Value *MulVal,
Value *OtherVal, InstCombiner &IC) {
if (!isa<IntegerType>(MulVal->getType()))
return nullptr;
assert(I.getOperand(0) == MulVal || I.getOperand(1) == MulVal);
assert(I.getOperand(0) == OtherVal || I.getOperand(1) == OtherVal);
Instruction *MulInstr = cast<Instruction>(MulVal);
assert(MulInstr->getOpcode() == Instruction::Mul);
auto *LHS = cast<ZExtOperator>(MulInstr->getOperand(0)),
*RHS = cast<ZExtOperator>(MulInstr->getOperand(1));
assert(LHS->getOpcode() == Instruction::ZExt);
assert(RHS->getOpcode() == Instruction::ZExt);
Value *A = LHS->getOperand(0), *B = RHS->getOperand(0);
Type *TyA = A->getType(), *TyB = B->getType();
unsigned WidthA = TyA->getPrimitiveSizeInBits(),
WidthB = TyB->getPrimitiveSizeInBits();
unsigned MulWidth;
Type *MulType;
if (WidthB > WidthA) {
MulWidth = WidthB;
MulType = TyB;
} else {
MulWidth = WidthA;
MulType = TyA;
}
if (MulVal->hasNUsesOrMore(2))
for (User *U : MulVal->users()) {
if (U == &I)
continue;
if (TruncInst *TI = dyn_cast<TruncInst>(U)) {
unsigned TruncWidth = TI->getType()->getPrimitiveSizeInBits();
if (TruncWidth > MulWidth)
return nullptr;
} else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(U)) {
if (BO->getOpcode() != Instruction::And)
return nullptr;
if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) {
const APInt &CVal = CI->getValue();
if (CVal.getBitWidth() - CVal.countLeadingZeros() > MulWidth)
return nullptr;
}
} else {
return nullptr;
}
}
switch (I.getPredicate()) {
case ICmpInst::ICMP_EQ:
case ICmpInst::ICMP_NE:
if (ZExtInst *Zext = dyn_cast<ZExtInst>(OtherVal))
if (Zext->hasOneUse()) {
Value *ZextArg = Zext->getOperand(0);
if (TruncInst *Trunc = dyn_cast<TruncInst>(ZextArg))
if (Trunc->getType()->getPrimitiveSizeInBits() == MulWidth)
break; }
ConstantInt *CI;
Value *ValToMask;
if (match(OtherVal, m_And(m_Value(ValToMask), m_ConstantInt(CI)))) {
if (ValToMask != MulVal)
return nullptr;
const APInt &CVal = CI->getValue() + 1;
if (CVal.isPowerOf2()) {
unsigned MaskWidth = CVal.logBase2();
if (MaskWidth == MulWidth)
break; }
}
return nullptr;
case ICmpInst::ICMP_UGT:
if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal)) {
APInt MaxVal = APInt::getMaxValue(MulWidth);
MaxVal = MaxVal.zext(CI->getBitWidth());
if (MaxVal.eq(CI->getValue()))
break; }
return nullptr;
case ICmpInst::ICMP_UGE:
if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal)) {
APInt MaxVal = APInt::getOneBitSet(CI->getBitWidth(), MulWidth);
if (MaxVal.eq(CI->getValue()))
break; }
return nullptr;
case ICmpInst::ICMP_ULE:
if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal)) {
APInt MaxVal = APInt::getMaxValue(MulWidth);
MaxVal = MaxVal.zext(CI->getBitWidth());
if (MaxVal.eq(CI->getValue()))
break; }
return nullptr;
case ICmpInst::ICMP_ULT:
if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal)) {
APInt MaxVal = APInt::getOneBitSet(CI->getBitWidth(), MulWidth);
if (MaxVal.eq(CI->getValue()))
break; }
return nullptr;
default:
return nullptr;
}
InstCombiner::BuilderTy *Builder = IC.Builder;
Builder->SetInsertPoint(MulInstr);
Module *M = I.getParent()->getParent()->getParent();
Value *MulA = A, *MulB = B;
if (WidthA < MulWidth)
MulA = Builder->CreateZExt(A, MulType);
if (WidthB < MulWidth)
MulB = Builder->CreateZExt(B, MulType);
Value *F =
Intrinsic::getDeclaration(M, Intrinsic::umul_with_overflow, MulType);
CallInst *Call = Builder->CreateCall2(F, MulA, MulB, "umul");
IC.Worklist.Add(MulInstr);
if (MulVal->hasNUsesOrMore(2)) {
Value *Mul = Builder->CreateExtractValue(Call, 0, "umul.value");
for (User *U : MulVal->users()) {
if (U == &I || U == OtherVal)
continue;
if (TruncInst *TI = dyn_cast<TruncInst>(U)) {
if (TI->getType()->getPrimitiveSizeInBits() == MulWidth)
IC.ReplaceInstUsesWith(*TI, Mul);
else
TI->setOperand(0, Mul);
} else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(U)) {
assert(BO->getOpcode() == Instruction::And);
ConstantInt *CI = cast<ConstantInt>(BO->getOperand(1));
APInt ShortMask = CI->getValue().trunc(MulWidth);
Value *ShortAnd = Builder->CreateAnd(Mul, ShortMask);
Instruction *Zext =
cast<Instruction>(Builder->CreateZExt(ShortAnd, BO->getType()));
IC.Worklist.Add(Zext);
IC.ReplaceInstUsesWith(*BO, Zext);
} else {
llvm_unreachable("Unexpected Binary operation");
}
IC.Worklist.Add(cast<Instruction>(U));
}
}
if (isa<Instruction>(OtherVal))
IC.Worklist.Add(cast<Instruction>(OtherVal));
bool Inverse = false;
switch (I.getPredicate()) {
case ICmpInst::ICMP_NE:
break;
case ICmpInst::ICMP_EQ:
Inverse = true;
break;
case ICmpInst::ICMP_UGT:
case ICmpInst::ICMP_UGE:
if (I.getOperand(0) == MulVal)
break;
Inverse = true;
break;
case ICmpInst::ICMP_ULT:
case ICmpInst::ICMP_ULE:
if (I.getOperand(1) == MulVal)
break;
Inverse = true;
break;
default:
llvm_unreachable("Unexpected predicate");
}
if (Inverse) {
Value *Res = Builder->CreateExtractValue(Call, 1);
return BinaryOperator::CreateNot(Res);
}
return ExtractValueInst::Create(Call, 1);
}
static APInt DemandedBitsLHSMask(ICmpInst &I,
unsigned BitWidth, bool isSignCheck) {
if (isSignCheck)
return APInt::getSignBit(BitWidth);
ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(1));
if (!CI) return APInt::getAllOnesValue(BitWidth);
const APInt &RHS = CI->getValue();
switch (I.getPredicate()) {
case ICmpInst::ICMP_UGT: {
unsigned trailingOnes = RHS.countTrailingOnes();
APInt lowBitsSet = APInt::getLowBitsSet(BitWidth, trailingOnes);
return ~lowBitsSet;
}
case ICmpInst::ICMP_ULT: {
unsigned trailingZeros = RHS.countTrailingZeros();
APInt lowBitsSet = APInt::getLowBitsSet(BitWidth, trailingZeros);
return ~lowBitsSet;
}
default:
return APInt::getAllOnesValue(BitWidth);
}
}
static bool swapMayExposeCSEOpportunities(const Value * Op0,
const Value * Op1) {
if (Op0->getType()->isPointerTy())
return false;
int GlobalSwapBenefits = 0;
for (const User *U : Op0->users()) {
const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(U);
if (!BinOp || BinOp->getOpcode() != Instruction::Sub)
continue;
int LocalSwapBenefits = -1;
unsigned Op1Idx = 1;
if (BinOp->getOperand(Op1Idx) == Op0) {
Op1Idx = 0;
LocalSwapBenefits = 1;
}
if (BinOp->getOperand(Op1Idx) != Op1)
continue;
GlobalSwapBenefits += LocalSwapBenefits;
}
return GlobalSwapBenefits > 0;
}
Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {
bool Changed = false;
Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
unsigned Op0Cplxity = getComplexity(Op0);
unsigned Op1Cplxity = getComplexity(Op1);
if (Op0Cplxity < Op1Cplxity ||
(Op0Cplxity == Op1Cplxity &&
swapMayExposeCSEOpportunities(Op0, Op1))) {
I.swapOperands();
std::swap(Op0, Op1);
Changed = true;
}
if (Value *V = SimplifyICmpInst(I.getPredicate(), Op0, Op1, DL))
return ReplaceInstUsesWith(I, V);
if (I.getPredicate() == ICmpInst::ICMP_NE && match(Op1, m_Zero()))
{
Value *Cond, *SelectTrue, *SelectFalse;
if (match(Op0, m_Select(m_Value(Cond), m_Value(SelectTrue),
m_Value(SelectFalse)))) {
if (Value *V = dyn_castNegVal(SelectTrue)) {
if (V == SelectFalse)
return CmpInst::Create(Instruction::ICmp, I.getPredicate(), V, Op1);
}
else if (Value *V = dyn_castNegVal(SelectFalse)) {
if (V == SelectTrue)
return CmpInst::Create(Instruction::ICmp, I.getPredicate(), V, Op1);
}
}
}
Type *Ty = Op0->getType();
if (Ty->isIntegerTy(1)) {
switch (I.getPredicate()) {
default: llvm_unreachable("Invalid icmp instruction!");
case ICmpInst::ICMP_EQ: { Value *Xor = Builder->CreateXor(Op0, Op1, I.getName()+"tmp");
return BinaryOperator::CreateNot(Xor);
}
case ICmpInst::ICMP_NE: return BinaryOperator::CreateXor(Op0, Op1);
case ICmpInst::ICMP_UGT:
std::swap(Op0, Op1); case ICmpInst::ICMP_ULT:{ Value *Not = Builder->CreateNot(Op0, I.getName()+"tmp");
return BinaryOperator::CreateAnd(Not, Op1);
}
case ICmpInst::ICMP_SGT:
std::swap(Op0, Op1); case ICmpInst::ICMP_SLT: { Value *Not = Builder->CreateNot(Op1, I.getName()+"tmp");
return BinaryOperator::CreateAnd(Not, Op0);
}
case ICmpInst::ICMP_UGE:
std::swap(Op0, Op1); case ICmpInst::ICMP_ULE: { Value *Not = Builder->CreateNot(Op0, I.getName()+"tmp");
return BinaryOperator::CreateOr(Not, Op1);
}
case ICmpInst::ICMP_SGE:
std::swap(Op0, Op1); case ICmpInst::ICMP_SLE: { Value *Not = Builder->CreateNot(Op1, I.getName()+"tmp");
return BinaryOperator::CreateOr(Not, Op0);
}
}
}
unsigned BitWidth = 0;
if (Ty->isIntOrIntVectorTy())
BitWidth = Ty->getScalarSizeInBits();
else if (DL) BitWidth = DL->getTypeSizeInBits(Ty->getScalarType());
bool isSignBit = false;
if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
Value *A = nullptr, *B = nullptr;
{
ConstantInt *CI2; if (I.getPredicate() == ICmpInst::ICMP_UGT &&
match(Op0, m_Add(m_Add(m_Value(A), m_Value(B)), m_ConstantInt(CI2))))
if (Instruction *Res = ProcessUGT_ADDCST_ADD(I, A, B, CI2, CI, *this))
return Res;
}
if (I.isEquality() && CI->isZero() &&
match(Op0, m_Sub(m_Value(A), m_Value(B)))) {
return new ICmpInst(I.getPredicate(), A, B);
}
switch (I.getPredicate()) {
default: break;
case ICmpInst::ICMP_ULE:
assert(!CI->isMaxValue(false)); return new ICmpInst(ICmpInst::ICMP_ULT, Op0,
Builder->getInt(CI->getValue()+1));
case ICmpInst::ICMP_SLE:
assert(!CI->isMaxValue(true)); return new ICmpInst(ICmpInst::ICMP_SLT, Op0,
Builder->getInt(CI->getValue()+1));
case ICmpInst::ICMP_UGE:
assert(!CI->isMinValue(false)); return new ICmpInst(ICmpInst::ICMP_UGT, Op0,
Builder->getInt(CI->getValue()-1));
case ICmpInst::ICMP_SGE:
assert(!CI->isMinValue(true)); return new ICmpInst(ICmpInst::ICMP_SGT, Op0,
Builder->getInt(CI->getValue()-1));
}
if (I.isEquality()) {
ConstantInt *CI2;
if (match(Op0, m_AShr(m_ConstantInt(CI2), m_Value(A))) ||
match(Op0, m_LShr(m_ConstantInt(CI2), m_Value(A)))) {
return FoldICmpCstShrCst(I, Op0, A, CI, CI2);
}
}
bool UnusedBit;
isSignBit = isSignBitCheck(I.getPredicate(), CI, UnusedBit);
}
if (BitWidth != 0) {
APInt Op0KnownZero(BitWidth, 0), Op0KnownOne(BitWidth, 0);
APInt Op1KnownZero(BitWidth, 0), Op1KnownOne(BitWidth, 0);
if (SimplifyDemandedBits(I.getOperandUse(0),
DemandedBitsLHSMask(I, BitWidth, isSignBit),
Op0KnownZero, Op0KnownOne, 0))
return &I;
if (SimplifyDemandedBits(I.getOperandUse(1),
APInt::getAllOnesValue(BitWidth),
Op1KnownZero, Op1KnownOne, 0))
return &I;
APInt Op0Min(BitWidth, 0), Op0Max(BitWidth, 0);
APInt Op1Min(BitWidth, 0), Op1Max(BitWidth, 0);
if (I.isSigned()) {
ComputeSignedMinMaxValuesFromKnownBits(Op0KnownZero, Op0KnownOne,
Op0Min, Op0Max);
ComputeSignedMinMaxValuesFromKnownBits(Op1KnownZero, Op1KnownOne,
Op1Min, Op1Max);
} else {
ComputeUnsignedMinMaxValuesFromKnownBits(Op0KnownZero, Op0KnownOne,
Op0Min, Op0Max);
ComputeUnsignedMinMaxValuesFromKnownBits(Op1KnownZero, Op1KnownOne,
Op1Min, Op1Max);
}
if (!isa<Constant>(Op0) && Op0Min == Op0Max)
return new ICmpInst(I.getPredicate(),
ConstantInt::get(Op0->getType(), Op0Min), Op1);
if (!isa<Constant>(Op1) && Op1Min == Op1Max)
return new ICmpInst(I.getPredicate(), Op0,
ConstantInt::get(Op1->getType(), Op1Min));
switch (I.getPredicate()) {
default: llvm_unreachable("Unknown icmp opcode!");
case ICmpInst::ICMP_EQ: {
if (Op0Max.ult(Op1Min) || Op0Min.ugt(Op1Max))
return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
APInt Op0KnownZeroInverted = ~Op0KnownZero;
if (~Op1KnownZero == 0) {
Value *LHS = nullptr;
ConstantInt *LHSC = nullptr;
if (!match(Op0, m_And(m_Value(LHS), m_ConstantInt(LHSC))) ||
LHSC->getValue() != Op0KnownZeroInverted)
LHS = Op0;
Value *X = nullptr;
if (match(LHS, m_Shl(m_One(), m_Value(X)))) {
APInt ValToCheck = Op0KnownZeroInverted;
if (ValToCheck.isPowerOf2()) {
unsigned CmpVal = ValToCheck.countTrailingZeros();
return new ICmpInst(ICmpInst::ICMP_NE, X,
ConstantInt::get(X->getType(), CmpVal));
} else if ((++ValToCheck).isPowerOf2()) {
unsigned CmpVal = ValToCheck.countTrailingZeros() - 1;
return new ICmpInst(ICmpInst::ICMP_UGT, X,
ConstantInt::get(X->getType(), CmpVal));
}
}
const APInt *CI;
if (Op0KnownZeroInverted == 1 &&
match(LHS, m_LShr(m_Power2(CI), m_Value(X))))
return new ICmpInst(ICmpInst::ICMP_NE, X,
ConstantInt::get(X->getType(),
CI->countTrailingZeros()));
}
break;
}
case ICmpInst::ICMP_NE: {
if (Op0Max.ult(Op1Min) || Op0Min.ugt(Op1Max))
return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
APInt Op0KnownZeroInverted = ~Op0KnownZero;
if (~Op1KnownZero == 0) {
Value *LHS = nullptr;
ConstantInt *LHSC = nullptr;
if (!match(Op0, m_And(m_Value(LHS), m_ConstantInt(LHSC))) ||
LHSC->getValue() != Op0KnownZeroInverted)
LHS = Op0;
Value *X = nullptr;
if (match(LHS, m_Shl(m_One(), m_Value(X)))) {
APInt ValToCheck = Op0KnownZeroInverted;
if (ValToCheck.isPowerOf2()) {
unsigned CmpVal = ValToCheck.countTrailingZeros();
return new ICmpInst(ICmpInst::ICMP_EQ, X,
ConstantInt::get(X->getType(), CmpVal));
} else if ((++ValToCheck).isPowerOf2()) {
unsigned CmpVal = ValToCheck.countTrailingZeros();
return new ICmpInst(ICmpInst::ICMP_ULT, X,
ConstantInt::get(X->getType(), CmpVal));
}
}
const APInt *CI;
if (Op0KnownZeroInverted == 1 &&
match(LHS, m_LShr(m_Power2(CI), m_Value(X))))
return new ICmpInst(ICmpInst::ICMP_EQ, X,
ConstantInt::get(X->getType(),
CI->countTrailingZeros()));
}
break;
}
case ICmpInst::ICMP_ULT:
if (Op0Max.ult(Op1Min)) return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
if (Op0Min.uge(Op1Max)) return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
if (Op1Min == Op0Max) return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1);
if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
if (Op1Max == Op0Min+1) return new ICmpInst(ICmpInst::ICMP_EQ, Op0,
Builder->getInt(CI->getValue()-1));
if (CI->isMinValue(true))
return new ICmpInst(ICmpInst::ICMP_SGT, Op0,
Constant::getAllOnesValue(Op0->getType()));
}
break;
case ICmpInst::ICMP_UGT:
if (Op0Min.ugt(Op1Max)) return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
if (Op0Max.ule(Op1Min)) return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
if (Op1Max == Op0Min) return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1);
if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
if (Op1Min == Op0Max-1) return new ICmpInst(ICmpInst::ICMP_EQ, Op0,
Builder->getInt(CI->getValue()+1));
if (CI->isMaxValue(true))
return new ICmpInst(ICmpInst::ICMP_SLT, Op0,
Constant::getNullValue(Op0->getType()));
}
break;
case ICmpInst::ICMP_SLT:
if (Op0Max.slt(Op1Min)) return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
if (Op0Min.sge(Op1Max)) return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
if (Op1Min == Op0Max) return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1);
if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
if (Op1Max == Op0Min+1) return new ICmpInst(ICmpInst::ICMP_EQ, Op0,
Builder->getInt(CI->getValue()-1));
}
break;
case ICmpInst::ICMP_SGT:
if (Op0Min.sgt(Op1Max)) return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
if (Op0Max.sle(Op1Min)) return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
if (Op1Max == Op0Min) return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1);
if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
if (Op1Min == Op0Max-1) return new ICmpInst(ICmpInst::ICMP_EQ, Op0,
Builder->getInt(CI->getValue()+1));
}
break;
case ICmpInst::ICMP_SGE:
assert(!isa<ConstantInt>(Op1) && "ICMP_SGE with ConstantInt not folded!");
if (Op0Min.sge(Op1Max)) return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
if (Op0Max.slt(Op1Min)) return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
break;
case ICmpInst::ICMP_SLE:
assert(!isa<ConstantInt>(Op1) && "ICMP_SLE with ConstantInt not folded!");
if (Op0Max.sle(Op1Min)) return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
if (Op0Min.sgt(Op1Max)) return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
break;
case ICmpInst::ICMP_UGE:
assert(!isa<ConstantInt>(Op1) && "ICMP_UGE with ConstantInt not folded!");
if (Op0Min.uge(Op1Max)) return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
if (Op0Max.ult(Op1Min)) return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
break;
case ICmpInst::ICMP_ULE:
assert(!isa<ConstantInt>(Op1) && "ICMP_ULE with ConstantInt not folded!");
if (Op0Max.ule(Op1Min)) return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
if (Op0Min.ugt(Op1Max)) return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
break;
}
if (I.isSigned() &&
((Op0KnownZero.isNegative() && Op1KnownZero.isNegative()) ||
(Op0KnownOne.isNegative() && Op1KnownOne.isNegative())))
return new ICmpInst(I.getUnsignedPredicate(), Op0, Op1);
}
if (I.hasOneUse())
if (SelectInst *SI = dyn_cast<SelectInst>(*I.user_begin()))
if ((SI->getOperand(1) == Op0 && SI->getOperand(2) == Op1) ||
(SI->getOperand(2) == Op0 && SI->getOperand(1) == Op1))
return nullptr;
if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
if (Instruction *LHSI = dyn_cast<Instruction>(Op0))
if (Instruction *Res = visitICmpInstWithInstAndIntCst(I, LHSI, CI))
return Res;
}
if (Constant *RHSC = dyn_cast<Constant>(Op1)) {
if (Instruction *LHSI = dyn_cast<Instruction>(Op0))
switch (LHSI->getOpcode()) {
case Instruction::GetElementPtr:
if (RHSC->isNullValue() &&
cast<GetElementPtrInst>(LHSI)->hasAllZeroIndices())
return new ICmpInst(I.getPredicate(), LHSI->getOperand(0),
Constant::getNullValue(LHSI->getOperand(0)->getType()));
break;
case Instruction::PHI:
if (LHSI->getParent() == I.getParent())
if (Instruction *NV = FoldOpIntoPhi(I))
return NV;
break;
case Instruction::Select: {
Value *Op1 = nullptr, *Op2 = nullptr;
if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(1)))
Op1 = ConstantExpr::getICmp(I.getPredicate(), C, RHSC);
if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(2)))
Op2 = ConstantExpr::getICmp(I.getPredicate(), C, RHSC);
if ((Op1 && Op2) || (LHSI->hasOneUse() && (Op1 || Op2))) {
if (!Op1)
Op1 = Builder->CreateICmp(I.getPredicate(), LHSI->getOperand(1),
RHSC, I.getName());
if (!Op2)
Op2 = Builder->CreateICmp(I.getPredicate(), LHSI->getOperand(2),
RHSC, I.getName());
return SelectInst::Create(LHSI->getOperand(0), Op1, Op2);
}
break;
}
case Instruction::IntToPtr:
if (RHSC->isNullValue() && DL &&
DL->getIntPtrType(RHSC->getType()) ==
LHSI->getOperand(0)->getType())
return new ICmpInst(I.getPredicate(), LHSI->getOperand(0),
Constant::getNullValue(LHSI->getOperand(0)->getType()));
break;
case Instruction::Load:
if (GetElementPtrInst *GEP =
dyn_cast<GetElementPtrInst>(LHSI->getOperand(0))) {
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0)))
if (GV->isConstant() && GV->hasDefinitiveInitializer() &&
!cast<LoadInst>(LHSI)->isVolatile())
if (Instruction *Res = FoldCmpLoadFromIndexedGlobal(GEP, GV, I))
return Res;
}
break;
}
}
if (GEPOperator *GEP = dyn_cast<GEPOperator>(Op0))
if (Instruction *NI = FoldGEPICmp(GEP, Op1, I.getPredicate(), I))
return NI;
if (GEPOperator *GEP = dyn_cast<GEPOperator>(Op1))
if (Instruction *NI = FoldGEPICmp(GEP, Op0,
ICmpInst::getSwappedPredicate(I.getPredicate()), I))
return NI;
if (BitCastInst *CI = dyn_cast<BitCastInst>(Op0)) {
if (Op0->getType()->isPointerTy() &&
(isa<Constant>(Op1) || isa<BitCastInst>(Op1))) {
Op0 = CI->getOperand(0);
if (BitCastInst *CI2 = dyn_cast<BitCastInst>(Op1))
Op1 = CI2->getOperand(0);
if (Op0->getType() != Op1->getType()) {
if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
Op1 = ConstantExpr::getBitCast(Op1C, Op0->getType());
} else {
Op1 = Builder->CreateBitCast(Op1, Op0->getType());
}
}
return new ICmpInst(I.getPredicate(), Op0, Op1);
}
}
if (isa<CastInst>(Op0)) {
if (isa<Constant>(Op1) || isa<CastInst>(Op1))
if (Instruction *R = visitICmpInstWithCastAndCast(I))
return R;
}
BinaryOperator *BO0 = dyn_cast<BinaryOperator>(Op0);
BinaryOperator *BO1 = dyn_cast<BinaryOperator>(Op1);
if (BO0 || BO1) {
CmpInst::Predicate Pred = I.getPredicate();
bool NoOp0WrapProblem = false, NoOp1WrapProblem = false;
if (BO0 && isa<OverflowingBinaryOperator>(BO0))
NoOp0WrapProblem = ICmpInst::isEquality(Pred) ||
(CmpInst::isUnsigned(Pred) && BO0->hasNoUnsignedWrap()) ||
(CmpInst::isSigned(Pred) && BO0->hasNoSignedWrap());
if (BO1 && isa<OverflowingBinaryOperator>(BO1))
NoOp1WrapProblem = ICmpInst::isEquality(Pred) ||
(CmpInst::isUnsigned(Pred) && BO1->hasNoUnsignedWrap()) ||
(CmpInst::isSigned(Pred) && BO1->hasNoSignedWrap());
Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr;
if (BO0 && BO0->getOpcode() == Instruction::Add)
A = BO0->getOperand(0), B = BO0->getOperand(1);
if (BO1 && BO1->getOpcode() == Instruction::Add)
C = BO1->getOperand(0), D = BO1->getOperand(1);
if ((A == Op1 || B == Op1) && NoOp0WrapProblem)
return new ICmpInst(Pred, A == Op1 ? B : A,
Constant::getNullValue(Op1->getType()));
if ((C == Op0 || D == Op0) && NoOp1WrapProblem)
return new ICmpInst(Pred, Constant::getNullValue(Op0->getType()),
C == Op0 ? D : C);
if (A && C && (A == C || A == D || B == C || B == D) &&
NoOp0WrapProblem && NoOp1WrapProblem &&
BO0->hasOneUse() && BO1->hasOneUse()) {
Value *Y, *Z;
if (A == C) {
Y = B;
Z = D;
} else if (A == D) {
Y = B;
Z = C;
} else if (B == C) {
Y = A;
Z = D;
} else {
assert(B == D);
Y = A;
Z = C;
}
return new ICmpInst(Pred, Y, Z);
}
if (A && NoOp0WrapProblem && Pred == CmpInst::ICMP_SLT &&
match(B, m_AllOnes()))
return new ICmpInst(CmpInst::ICMP_SLE, A, Op1);
if (A && NoOp0WrapProblem && Pred == CmpInst::ICMP_SGE &&
match(B, m_AllOnes()))
return new ICmpInst(CmpInst::ICMP_SGT, A, Op1);
if (A && NoOp0WrapProblem && Pred == CmpInst::ICMP_SLE &&
match(B, m_One()))
return new ICmpInst(CmpInst::ICMP_SLT, A, Op1);
if (A && NoOp0WrapProblem && Pred == CmpInst::ICMP_SGT &&
match(B, m_One()))
return new ICmpInst(CmpInst::ICMP_SGE, A, Op1);
if (A && C && NoOp0WrapProblem && NoOp1WrapProblem &&
(BO0->hasOneUse() || BO1->hasOneUse()) && !I.isUnsigned())
if (ConstantInt *C1 = dyn_cast<ConstantInt>(B))
if (ConstantInt *C2 = dyn_cast<ConstantInt>(D)) {
const APInt &AP1 = C1->getValue();
const APInt &AP2 = C2->getValue();
if (AP1.isNegative() == AP2.isNegative()) {
APInt AP1Abs = C1->getValue().abs();
APInt AP2Abs = C2->getValue().abs();
if (AP1Abs.uge(AP2Abs)) {
ConstantInt *C3 = Builder->getInt(AP1 - AP2);
Value *NewAdd = Builder->CreateNSWAdd(A, C3);
return new ICmpInst(Pred, NewAdd, C);
} else {
ConstantInt *C3 = Builder->getInt(AP2 - AP1);
Value *NewAdd = Builder->CreateNSWAdd(C, C3);
return new ICmpInst(Pred, A, NewAdd);
}
}
}
A = nullptr; B = nullptr; C = nullptr; D = nullptr;
if (BO0 && BO0->getOpcode() == Instruction::Sub)
A = BO0->getOperand(0), B = BO0->getOperand(1);
if (BO1 && BO1->getOpcode() == Instruction::Sub)
C = BO1->getOperand(0), D = BO1->getOperand(1);
if (A == Op1 && NoOp0WrapProblem)
return new ICmpInst(Pred, Constant::getNullValue(Op1->getType()), B);
if (C == Op0 && NoOp1WrapProblem)
return new ICmpInst(Pred, D, Constant::getNullValue(Op0->getType()));
if (B && D && B == D && NoOp0WrapProblem && NoOp1WrapProblem &&
BO0->hasOneUse() && BO1->hasOneUse())
return new ICmpInst(Pred, A, C);
if (A && C && A == C && NoOp0WrapProblem && NoOp1WrapProblem &&
BO0->hasOneUse() && BO1->hasOneUse())
return new ICmpInst(Pred, D, B);
if (NoOp0WrapProblem && ICmpInst::isSigned(Pred)) {
Value *X;
if (match(BO0, m_Neg(m_Value(X))))
if (ConstantInt *RHSC = dyn_cast<ConstantInt>(Op1))
if (!RHSC->isMinValue(true))
return new ICmpInst(I.getSwappedPredicate(), X,
ConstantExpr::getNeg(RHSC));
}
BinaryOperator *SRem = nullptr;
if (BO0 && BO0->getOpcode() == Instruction::SRem &&
Op1 == BO0->getOperand(1))
SRem = BO0;
else if (BO1 && BO1->getOpcode() == Instruction::SRem &&
Op0 == BO1->getOperand(1))
SRem = BO1;
if (SRem) {
switch (SRem == BO0 ? ICmpInst::getSwappedPredicate(Pred) : Pred) {
default: break;
case ICmpInst::ICMP_EQ:
return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
case ICmpInst::ICMP_NE:
return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
case ICmpInst::ICMP_SGT:
case ICmpInst::ICMP_SGE:
return new ICmpInst(ICmpInst::ICMP_SGT, SRem->getOperand(1),
Constant::getAllOnesValue(SRem->getType()));
case ICmpInst::ICMP_SLT:
case ICmpInst::ICMP_SLE:
return new ICmpInst(ICmpInst::ICMP_SLT, SRem->getOperand(1),
Constant::getNullValue(SRem->getType()));
}
}
if (BO0 && BO1 && BO0->getOpcode() == BO1->getOpcode() &&
BO0->hasOneUse() && BO1->hasOneUse() &&
BO0->getOperand(1) == BO1->getOperand(1)) {
switch (BO0->getOpcode()) {
default: break;
case Instruction::Add:
case Instruction::Sub:
case Instruction::Xor:
if (I.isEquality()) return new ICmpInst(I.getPredicate(), BO0->getOperand(0),
BO1->getOperand(0));
if (ConstantInt *CI = dyn_cast<ConstantInt>(BO0->getOperand(1))) {
if (CI->getValue().isSignBit()) {
ICmpInst::Predicate Pred = I.isSigned()
? I.getUnsignedPredicate()
: I.getSignedPredicate();
return new ICmpInst(Pred, BO0->getOperand(0),
BO1->getOperand(0));
}
if (CI->isMaxValue(true)) {
ICmpInst::Predicate Pred = I.isSigned()
? I.getUnsignedPredicate()
: I.getSignedPredicate();
Pred = I.getSwappedPredicate(Pred);
return new ICmpInst(Pred, BO0->getOperand(0),
BO1->getOperand(0));
}
}
break;
case Instruction::Mul:
if (!I.isEquality())
break;
if (ConstantInt *CI = dyn_cast<ConstantInt>(BO0->getOperand(1))) {
if (!CI->isZero() && !CI->isOne()) {
const APInt &AP = CI->getValue();
ConstantInt *Mask = ConstantInt::get(I.getContext(),
APInt::getLowBitsSet(AP.getBitWidth(),
AP.getBitWidth() -
AP.countTrailingZeros()));
Value *And1 = Builder->CreateAnd(BO0->getOperand(0), Mask);
Value *And2 = Builder->CreateAnd(BO1->getOperand(0), Mask);
return new ICmpInst(I.getPredicate(), And1, And2);
}
}
break;
case Instruction::UDiv:
case Instruction::LShr:
if (I.isSigned())
break;
case Instruction::SDiv:
case Instruction::AShr:
if (!BO0->isExact() || !BO1->isExact())
break;
return new ICmpInst(I.getPredicate(), BO0->getOperand(0),
BO1->getOperand(0));
case Instruction::Shl: {
bool NUW = BO0->hasNoUnsignedWrap() && BO1->hasNoUnsignedWrap();
bool NSW = BO0->hasNoSignedWrap() && BO1->hasNoSignedWrap();
if (!NUW && !NSW)
break;
if (!NSW && I.isSigned())
break;
return new ICmpInst(I.getPredicate(), BO0->getOperand(0),
BO1->getOperand(0));
}
}
}
}
{ Value *A, *B;
if (match(Op0, m_And(m_Value(A), m_Not(m_Value(B)))) &&
match(Op1, m_Zero()) && isKnownToBeAPowerOfTwo(A) && I.isEquality())
return new ICmpInst(I.getInversePredicate(),
Builder->CreateAnd(A, B),
Op1);
if (match(Op0, m_Not(m_Value(A)))) {
if (match(Op1, m_Not(m_Value(B))))
return new ICmpInst(I.getPredicate(), B, A);
if (ConstantInt *RHSC = dyn_cast<ConstantInt>(Op1))
return new ICmpInst(I.getPredicate(), ConstantExpr::getNot(RHSC), A);
}
if (I.getPredicate() == ICmpInst::ICMP_ULT &&
match(Op0, m_Add(m_Value(A), m_Value(B))) &&
(Op1 == A || Op1 == B))
if (Instruction *R = ProcessUAddIdiom(I, Op0, *this))
return R;
if (I.getPredicate() == ICmpInst::ICMP_UGT &&
match(Op1, m_Add(m_Value(A), m_Value(B))) &&
(Op0 == A || Op0 == B))
if (Instruction *R = ProcessUAddIdiom(I, Op1, *this))
return R;
if (match(Op0, m_Mul(m_ZExt(m_Value(A)), m_ZExt(m_Value(B))))) {
if (Instruction *R = ProcessUMulZExtIdiom(I, Op0, Op1, *this))
return R;
}
if (match(Op1, m_Mul(m_ZExt(m_Value(A)), m_ZExt(m_Value(B))))) {
if (Instruction *R = ProcessUMulZExtIdiom(I, Op1, Op0, *this))
return R;
}
}
if (I.isEquality()) {
Value *A, *B, *C, *D;
if (match(Op0, m_Xor(m_Value(A), m_Value(B)))) {
if (A == Op1 || B == Op1) { Value *OtherVal = A == Op1 ? B : A;
return new ICmpInst(I.getPredicate(), OtherVal,
Constant::getNullValue(A->getType()));
}
if (match(Op1, m_Xor(m_Value(C), m_Value(D)))) {
ConstantInt *C1, *C2;
if (match(B, m_ConstantInt(C1)) &&
match(D, m_ConstantInt(C2)) && Op1->hasOneUse()) {
Constant *NC = Builder->getInt(C1->getValue() ^ C2->getValue());
Value *Xor = Builder->CreateXor(C, NC);
return new ICmpInst(I.getPredicate(), A, Xor);
}
if (A == C) return new ICmpInst(I.getPredicate(), B, D);
if (A == D) return new ICmpInst(I.getPredicate(), B, C);
if (B == C) return new ICmpInst(I.getPredicate(), A, D);
if (B == D) return new ICmpInst(I.getPredicate(), A, C);
}
}
if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&
(A == Op0 || B == Op0)) {
Value *OtherVal = A == Op0 ? B : A;
return new ICmpInst(I.getPredicate(), OtherVal,
Constant::getNullValue(A->getType()));
}
if (match(Op0, m_OneUse(m_And(m_Value(A), m_Value(B)))) &&
match(Op1, m_OneUse(m_And(m_Value(C), m_Value(D))))) {
Value *X = nullptr, *Y = nullptr, *Z = nullptr;
if (A == C) {
X = B; Y = D; Z = A;
} else if (A == D) {
X = B; Y = C; Z = A;
} else if (B == C) {
X = A; Y = D; Z = B;
} else if (B == D) {
X = A; Y = C; Z = B;
}
if (X) { Op1 = Builder->CreateXor(X, Y);
Op1 = Builder->CreateAnd(Op1, Z);
I.setOperand(0, Op1);
I.setOperand(1, Constant::getNullValue(Op1->getType()));
return &I;
}
}
ConstantInt *Cst1;
if ((Op0->hasOneUse() &&
match(Op0, m_ZExt(m_Value(A))) &&
match(Op1, m_And(m_Value(B), m_ConstantInt(Cst1)))) ||
(Op1->hasOneUse() &&
match(Op0, m_And(m_Value(B), m_ConstantInt(Cst1))) &&
match(Op1, m_ZExt(m_Value(A))))) {
APInt Pow2 = Cst1->getValue() + 1;
if (Pow2.isPowerOf2() && isa<IntegerType>(A->getType()) &&
Pow2.logBase2() == cast<IntegerType>(A->getType())->getBitWidth())
return new ICmpInst(I.getPredicate(), A,
Builder->CreateTrunc(B, A->getType()));
}
if ((match(Op0, m_OneUse(m_LShr(m_Value(A), m_ConstantInt(Cst1)))) &&
match(Op1, m_OneUse(m_LShr(m_Value(B), m_Specific(Cst1))))) ||
(match(Op0, m_OneUse(m_AShr(m_Value(A), m_ConstantInt(Cst1)))) &&
match(Op1, m_OneUse(m_AShr(m_Value(B), m_Specific(Cst1)))))) {
unsigned TypeBits = Cst1->getBitWidth();
unsigned ShAmt = (unsigned)Cst1->getLimitedValue(TypeBits);
if (ShAmt < TypeBits && ShAmt != 0) {
ICmpInst::Predicate Pred = I.getPredicate() == ICmpInst::ICMP_NE
? ICmpInst::ICMP_UGE
: ICmpInst::ICMP_ULT;
Value *Xor = Builder->CreateXor(A, B, I.getName() + ".unshifted");
APInt CmpVal = APInt::getOneBitSet(TypeBits, ShAmt);
return new ICmpInst(Pred, Xor, Builder->getInt(CmpVal));
}
}
uint64_t ShAmt = 0;
if (Op0->hasOneUse() &&
match(Op0, m_Trunc(m_OneUse(m_LShr(m_Value(A),
m_ConstantInt(ShAmt))))) &&
match(Op1, m_ConstantInt(Cst1)) &&
!A->hasOneUse()) {
unsigned ASize =cast<IntegerType>(A->getType())->getPrimitiveSizeInBits();
if (ShAmt < ASize) {
APInt MaskV =
APInt::getLowBitsSet(ASize, Op0->getType()->getPrimitiveSizeInBits());
MaskV <<= ShAmt;
APInt CmpV = Cst1->getValue().zext(ASize);
CmpV <<= ShAmt;
Value *Mask = Builder->CreateAnd(A, Builder->getInt(MaskV));
return new ICmpInst(I.getPredicate(), Mask, Builder->getInt(CmpV));
}
}
}
{
Value *X; ConstantInt *Cst;
if (match(Op0, m_Add(m_Value(X), m_ConstantInt(Cst))) && Op1 == X)
return FoldICmpAddOpCst(I, X, Cst, I.getPredicate());
if (match(Op1, m_Add(m_Value(X), m_ConstantInt(Cst))) && Op0 == X)
return FoldICmpAddOpCst(I, X, Cst, I.getSwappedPredicate());
}
return Changed ? &I : nullptr;
}
Instruction *InstCombiner::FoldFCmp_IntToFP_Cst(FCmpInst &I,
Instruction *LHSI,
Constant *RHSC) {
if (!isa<ConstantFP>(RHSC)) return nullptr;
const APFloat &RHS = cast<ConstantFP>(RHSC)->getValueAPF();
int MantissaWidth = LHSI->getType()->getFPMantissaWidth();
if (MantissaWidth == -1) return nullptr;
unsigned InputSize = LHSI->getOperand(0)->getType()->getScalarSizeInBits();
bool LHSUnsigned = isa<UIToFPInst>(LHSI);
if (LHSUnsigned)
++InputSize;
if ((int)InputSize > MantissaWidth)
return nullptr;
assert(!RHS.isNaN() && "NaN comparison not already folded!");
ICmpInst::Predicate Pred;
switch (I.getPredicate()) {
default: llvm_unreachable("Unexpected predicate!");
case FCmpInst::FCMP_UEQ:
case FCmpInst::FCMP_OEQ:
Pred = ICmpInst::ICMP_EQ;
break;
case FCmpInst::FCMP_UGT:
case FCmpInst::FCMP_OGT:
Pred = LHSUnsigned ? ICmpInst::ICMP_UGT : ICmpInst::ICMP_SGT;
break;
case FCmpInst::FCMP_UGE:
case FCmpInst::FCMP_OGE:
Pred = LHSUnsigned ? ICmpInst::ICMP_UGE : ICmpInst::ICMP_SGE;
break;
case FCmpInst::FCMP_ULT:
case FCmpInst::FCMP_OLT:
Pred = LHSUnsigned ? ICmpInst::ICMP_ULT : ICmpInst::ICMP_SLT;
break;
case FCmpInst::FCMP_ULE:
case FCmpInst::FCMP_OLE:
Pred = LHSUnsigned ? ICmpInst::ICMP_ULE : ICmpInst::ICMP_SLE;
break;
case FCmpInst::FCMP_UNE:
case FCmpInst::FCMP_ONE:
Pred = ICmpInst::ICMP_NE;
break;
case FCmpInst::FCMP_ORD:
return ReplaceInstUsesWith(I, Builder->getTrue());
case FCmpInst::FCMP_UNO:
return ReplaceInstUsesWith(I, Builder->getFalse());
}
IntegerType *IntTy = cast<IntegerType>(LHSI->getOperand(0)->getType());
unsigned IntWidth = IntTy->getScalarSizeInBits();
if (!LHSUnsigned) {
APFloat SMax(RHS.getSemantics());
SMax.convertFromAPInt(APInt::getSignedMaxValue(IntWidth), true,
APFloat::rmNearestTiesToEven);
if (SMax.compare(RHS) == APFloat::cmpLessThan) { if (Pred == ICmpInst::ICMP_NE || Pred == ICmpInst::ICMP_SLT ||
Pred == ICmpInst::ICMP_SLE)
return ReplaceInstUsesWith(I, Builder->getTrue());
return ReplaceInstUsesWith(I, Builder->getFalse());
}
} else {
APFloat UMax(RHS.getSemantics());
UMax.convertFromAPInt(APInt::getMaxValue(IntWidth), false,
APFloat::rmNearestTiesToEven);
if (UMax.compare(RHS) == APFloat::cmpLessThan) { if (Pred == ICmpInst::ICMP_NE || Pred == ICmpInst::ICMP_ULT ||
Pred == ICmpInst::ICMP_ULE)
return ReplaceInstUsesWith(I, Builder->getTrue());
return ReplaceInstUsesWith(I, Builder->getFalse());
}
}
if (!LHSUnsigned) {
APFloat SMin(RHS.getSemantics());
SMin.convertFromAPInt(APInt::getSignedMinValue(IntWidth), true,
APFloat::rmNearestTiesToEven);
if (SMin.compare(RHS) == APFloat::cmpGreaterThan) { if (Pred == ICmpInst::ICMP_NE || Pred == ICmpInst::ICMP_SGT ||
Pred == ICmpInst::ICMP_SGE)
return ReplaceInstUsesWith(I, Builder->getTrue());
return ReplaceInstUsesWith(I, Builder->getFalse());
}
} else {
APFloat SMin(RHS.getSemantics());
SMin.convertFromAPInt(APInt::getMinValue(IntWidth), true,
APFloat::rmNearestTiesToEven);
if (SMin.compare(RHS) == APFloat::cmpGreaterThan) { if (Pred == ICmpInst::ICMP_NE || Pred == ICmpInst::ICMP_UGT ||
Pred == ICmpInst::ICMP_UGE)
return ReplaceInstUsesWith(I, Builder->getTrue());
return ReplaceInstUsesWith(I, Builder->getFalse());
}
}
Constant *RHSInt = LHSUnsigned
? ConstantExpr::getFPToUI(RHSC, IntTy)
: ConstantExpr::getFPToSI(RHSC, IntTy);
if (!RHS.isZero()) {
bool Equal = LHSUnsigned
? ConstantExpr::getUIToFP(RHSInt, RHSC->getType()) == RHSC
: ConstantExpr::getSIToFP(RHSInt, RHSC->getType()) == RHSC;
if (!Equal) {
switch (Pred) {
default: llvm_unreachable("Unexpected integer comparison!");
case ICmpInst::ICMP_NE: return ReplaceInstUsesWith(I, Builder->getTrue());
case ICmpInst::ICMP_EQ: return ReplaceInstUsesWith(I, Builder->getFalse());
case ICmpInst::ICMP_ULE:
if (RHS.isNegative())
return ReplaceInstUsesWith(I, Builder->getFalse());
break;
case ICmpInst::ICMP_SLE:
if (RHS.isNegative())
Pred = ICmpInst::ICMP_SLT;
break;
case ICmpInst::ICMP_ULT:
if (RHS.isNegative())
return ReplaceInstUsesWith(I, Builder->getFalse());
Pred = ICmpInst::ICMP_ULE;
break;
case ICmpInst::ICMP_SLT:
if (!RHS.isNegative())
Pred = ICmpInst::ICMP_SLE;
break;
case ICmpInst::ICMP_UGT:
if (RHS.isNegative())
return ReplaceInstUsesWith(I, Builder->getTrue());
break;
case ICmpInst::ICMP_SGT:
if (RHS.isNegative())
Pred = ICmpInst::ICMP_SGE;
break;
case ICmpInst::ICMP_UGE:
if (RHS.isNegative())
return ReplaceInstUsesWith(I, Builder->getTrue());
Pred = ICmpInst::ICMP_UGT;
break;
case ICmpInst::ICMP_SGE:
if (!RHS.isNegative())
Pred = ICmpInst::ICMP_SGT;
break;
}
}
}
return new ICmpInst(Pred, LHSI->getOperand(0), RHSInt);
}
Instruction *InstCombiner::visitFCmpInst(FCmpInst &I) {
bool Changed = false;
if (getComplexity(I.getOperand(0)) < getComplexity(I.getOperand(1))) {
I.swapOperands();
Changed = true;
}
Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
if (Value *V = SimplifyFCmpInst(I.getPredicate(), Op0, Op1, DL))
return ReplaceInstUsesWith(I, V);
if (Op0 == Op1) {
switch (I.getPredicate()) {
default: llvm_unreachable("Unknown predicate!");
case FCmpInst::FCMP_UNO: case FCmpInst::FCMP_ULT: case FCmpInst::FCMP_UGT: case FCmpInst::FCMP_UNE: I.setPredicate(FCmpInst::FCMP_UNO);
I.setOperand(1, Constant::getNullValue(Op0->getType()));
return &I;
case FCmpInst::FCMP_ORD: case FCmpInst::FCMP_OEQ: case FCmpInst::FCMP_OGE: case FCmpInst::FCMP_OLE: I.setPredicate(FCmpInst::FCMP_ORD);
I.setOperand(1, Constant::getNullValue(Op0->getType()));
return &I;
}
}
if (Constant *RHSC = dyn_cast<Constant>(Op1)) {
if (Instruction *LHSI = dyn_cast<Instruction>(Op0))
switch (LHSI->getOpcode()) {
case Instruction::FPExt: {
FPExtInst *LHSExt = cast<FPExtInst>(LHSI);
ConstantFP *RHSF = dyn_cast<ConstantFP>(RHSC);
if (!RHSF)
break;
const fltSemantics *Sem;
if (LHSExt->getSrcTy()->isHalfTy())
Sem = &APFloat::IEEEhalf;
else if (LHSExt->getSrcTy()->isFloatTy())
Sem = &APFloat::IEEEsingle;
else if (LHSExt->getSrcTy()->isDoubleTy())
Sem = &APFloat::IEEEdouble;
else if (LHSExt->getSrcTy()->isFP128Ty())
Sem = &APFloat::IEEEquad;
else if (LHSExt->getSrcTy()->isX86_FP80Ty())
Sem = &APFloat::x87DoubleExtended;
else if (LHSExt->getSrcTy()->isPPC_FP128Ty())
Sem = &APFloat::PPCDoubleDouble;
else
break;
bool Lossy;
APFloat F = RHSF->getValueAPF();
F.convert(*Sem, APFloat::rmNearestTiesToEven, &Lossy);
APFloat Fabs = F;
Fabs.clearSign();
if (!Lossy &&
((Fabs.compare(APFloat::getSmallestNormalized(*Sem)) !=
APFloat::cmpLessThan) || Fabs.isZero()))
return new FCmpInst(I.getPredicate(), LHSExt->getOperand(0),
ConstantFP::get(RHSC->getContext(), F));
break;
}
case Instruction::PHI:
if (LHSI->getParent() == I.getParent())
if (Instruction *NV = FoldOpIntoPhi(I))
return NV;
break;
case Instruction::SIToFP:
case Instruction::UIToFP:
if (Instruction *NV = FoldFCmp_IntToFP_Cst(I, LHSI, RHSC))
return NV;
break;
case Instruction::FSub: {
Value *Op;
if (match(LHSI, m_FNeg(m_Value(Op))))
return new FCmpInst(I.getSwappedPredicate(), Op,
ConstantExpr::getFNeg(RHSC));
break;
}
case Instruction::Load:
if (GetElementPtrInst *GEP =
dyn_cast<GetElementPtrInst>(LHSI->getOperand(0))) {
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0)))
if (GV->isConstant() && GV->hasDefinitiveInitializer() &&
!cast<LoadInst>(LHSI)->isVolatile())
if (Instruction *Res = FoldCmpLoadFromIndexedGlobal(GEP, GV, I))
return Res;
}
break;
case Instruction::Call: {
CallInst *CI = cast<CallInst>(LHSI);
LibFunc::Func Func;
if (RHSC->isNullValue() && CI->getCalledFunction() &&
TLI->getLibFunc(CI->getCalledFunction()->getName(), Func) &&
TLI->has(Func)) {
if (Func == LibFunc::fabs || Func == LibFunc::fabsf ||
Func == LibFunc::fabsl) {
switch (I.getPredicate()) {
default: break;
case FCmpInst::FCMP_OLT:
return ReplaceInstUsesWith(I, Builder->getFalse());
case FCmpInst::FCMP_OGT:
return new FCmpInst(FCmpInst::FCMP_ONE, CI->getArgOperand(0),
RHSC);
case FCmpInst::FCMP_OLE:
return new FCmpInst(FCmpInst::FCMP_OEQ, CI->getArgOperand(0),
RHSC);
case FCmpInst::FCMP_OGE:
return new FCmpInst(FCmpInst::FCMP_ORD, CI->getArgOperand(0),
RHSC);
case FCmpInst::FCMP_OEQ:
case FCmpInst::FCMP_UEQ:
case FCmpInst::FCMP_ONE:
case FCmpInst::FCMP_UNE:
return new FCmpInst(I.getPredicate(), CI->getArgOperand(0),
RHSC);
}
}
}
}
}
}
Value *X, *Y;
if (match(Op0, m_FNeg(m_Value(X))) && match(Op1, m_FNeg(m_Value(Y))))
return new FCmpInst(I.getSwappedPredicate(), X, Y);
if (FPExtInst *LHSExt = dyn_cast<FPExtInst>(Op0))
if (FPExtInst *RHSExt = dyn_cast<FPExtInst>(Op1))
if (LHSExt->getSrcTy() == RHSExt->getSrcTy())
return new FCmpInst(I.getPredicate(), LHSExt->getOperand(0),
RHSExt->getOperand(0));
return Changed ? &I : nullptr;
}