aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp')
-rw-r--r--llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp1087
1 files changed, 613 insertions, 474 deletions
diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
index 656f04370e17..e42e011bd436 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
@@ -12,12 +12,14 @@
#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"
@@ -26,6 +28,7 @@
#include "llvm/IR/PatternMatch.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Transforms/InstCombine/InstCombiner.h"
+#include <bitset>
using namespace llvm;
using namespace PatternMatch;
@@ -412,7 +415,7 @@ Instruction *InstCombinerImpl::foldCmpLoadFromIndexedGlobal(
/// Returns true if we can rewrite Start as a GEP with pointer Base
/// and some integer offset. The nodes that need to be re-written
/// for this transformation will be added to Explored.
-static bool canRewriteGEPAsOffset(Type *ElemTy, Value *Start, Value *Base,
+static bool canRewriteGEPAsOffset(Value *Start, Value *Base,
const DataLayout &DL,
SetVector<Value *> &Explored) {
SmallVector<Value *, 16> WorkList(1, Start);
@@ -440,27 +443,15 @@ static bool canRewriteGEPAsOffset(Type *ElemTy, Value *Start, Value *Base,
continue;
}
- if (!isa<IntToPtrInst>(V) && !isa<PtrToIntInst>(V) &&
- !isa<GetElementPtrInst>(V) && !isa<PHINode>(V))
+ if (!isa<GetElementPtrInst>(V) && !isa<PHINode>(V))
// We've found some value that we can't explore which is different from
// the base. Therefore we can't do this transformation.
return false;
- if (isa<IntToPtrInst>(V) || isa<PtrToIntInst>(V)) {
- auto *CI = cast<CastInst>(V);
- if (!CI->isNoopCast(DL))
- return false;
-
- if (!Explored.contains(CI->getOperand(0)))
- WorkList.push_back(CI->getOperand(0));
- }
-
if (auto *GEP = dyn_cast<GEPOperator>(V)) {
- // We're limiting the GEP to having one index. This will preserve
- // the original pointer type. We could handle more cases in the
- // future.
- if (GEP->getNumIndices() != 1 || !GEP->isInBounds() ||
- GEP->getSourceElementType() != ElemTy)
+ // Only allow inbounds GEPs with at most one variable offset.
+ auto IsNonConst = [](Value *V) { return !isa<ConstantInt>(V); };
+ if (!GEP->isInBounds() || count_if(GEP->indices(), IsNonConst) > 1)
return false;
if (!Explored.contains(GEP->getOperand(0)))
@@ -514,7 +505,8 @@ static bool canRewriteGEPAsOffset(Type *ElemTy, Value *Start, Value *Base,
static void setInsertionPoint(IRBuilder<> &Builder, Value *V,
bool Before = true) {
if (auto *PHI = dyn_cast<PHINode>(V)) {
- Builder.SetInsertPoint(&*PHI->getParent()->getFirstInsertionPt());
+ BasicBlock *Parent = PHI->getParent();
+ Builder.SetInsertPoint(Parent, Parent->getFirstInsertionPt());
return;
}
if (auto *I = dyn_cast<Instruction>(V)) {
@@ -526,7 +518,7 @@ static void setInsertionPoint(IRBuilder<> &Builder, Value *V,
if (auto *A = dyn_cast<Argument>(V)) {
// Set the insertion point in the entry block.
BasicBlock &Entry = A->getParent()->getEntryBlock();
- Builder.SetInsertPoint(&*Entry.getFirstInsertionPt());
+ Builder.SetInsertPoint(&Entry, Entry.getFirstInsertionPt());
return;
}
// Otherwise, this is a constant and we don't need to set a new
@@ -536,7 +528,7 @@ static void setInsertionPoint(IRBuilder<> &Builder, Value *V,
/// Returns a re-written value of Start as an indexed GEP using Base as a
/// pointer.
-static Value *rewriteGEPAsOffset(Type *ElemTy, Value *Start, Value *Base,
+static Value *rewriteGEPAsOffset(Value *Start, Value *Base,
const DataLayout &DL,
SetVector<Value *> &Explored,
InstCombiner &IC) {
@@ -567,36 +559,18 @@ static Value *rewriteGEPAsOffset(Type *ElemTy, Value *Start, Value *Base,
// Create all the other instructions.
for (Value *Val : Explored) {
-
if (NewInsts.contains(Val))
continue;
- if (auto *CI = dyn_cast<CastInst>(Val)) {
- // Don't get rid of the intermediate variable here; the store can grow
- // the map which will invalidate the reference to the input value.
- Value *V = NewInsts[CI->getOperand(0)];
- NewInsts[CI] = V;
- continue;
- }
if (auto *GEP = dyn_cast<GEPOperator>(Val)) {
- Value *Index = NewInsts[GEP->getOperand(1)] ? NewInsts[GEP->getOperand(1)]
- : GEP->getOperand(1);
setInsertionPoint(Builder, GEP);
- // Indices might need to be sign extended. GEPs will magically do
- // this, but we need to do it ourselves here.
- if (Index->getType()->getScalarSizeInBits() !=
- NewInsts[GEP->getOperand(0)]->getType()->getScalarSizeInBits()) {
- Index = Builder.CreateSExtOrTrunc(
- Index, NewInsts[GEP->getOperand(0)]->getType(),
- GEP->getOperand(0)->getName() + ".sext");
- }
-
- auto *Op = NewInsts[GEP->getOperand(0)];
+ Value *Op = NewInsts[GEP->getOperand(0)];
+ Value *OffsetV = emitGEPOffset(&Builder, DL, GEP);
if (isa<ConstantInt>(Op) && cast<ConstantInt>(Op)->isZero())
- NewInsts[GEP] = Index;
+ NewInsts[GEP] = OffsetV;
else
NewInsts[GEP] = Builder.CreateNSWAdd(
- Op, Index, GEP->getOperand(0)->getName() + ".add");
+ Op, OffsetV, GEP->getOperand(0)->getName() + ".add");
continue;
}
if (isa<PHINode>(Val))
@@ -624,23 +598,14 @@ static Value *rewriteGEPAsOffset(Type *ElemTy, Value *Start, Value *Base,
}
}
- PointerType *PtrTy =
- ElemTy->getPointerTo(Start->getType()->getPointerAddressSpace());
for (Value *Val : Explored) {
if (Val == Base)
continue;
- // Depending on the type, for external users we have to emit
- // a GEP or a GEP + ptrtoint.
setInsertionPoint(Builder, Val, false);
-
- // Cast base to the expected type.
- Value *NewVal = Builder.CreateBitOrPointerCast(
- Base, PtrTy, Start->getName() + "to.ptr");
- NewVal = Builder.CreateInBoundsGEP(ElemTy, NewVal, ArrayRef(NewInsts[Val]),
- Val->getName() + ".ptr");
- NewVal = Builder.CreateBitOrPointerCast(
- NewVal, Val->getType(), Val->getName() + ".conv");
+ // Create GEP for external users.
+ Value *NewVal = Builder.CreateInBoundsGEP(
+ Builder.getInt8Ty(), Base, NewInsts[Val], Val->getName() + ".ptr");
IC.replaceInstUsesWith(*cast<Instruction>(Val), NewVal);
// Add old instruction to worklist for DCE. We don't directly remove it
// here because the original compare is one of the users.
@@ -650,48 +615,6 @@ static Value *rewriteGEPAsOffset(Type *ElemTy, Value *Start, Value *Base,
return NewInsts[Start];
}
-/// Looks through GEPs, IntToPtrInsts and PtrToIntInsts in order to express
-/// the input Value as a constant indexed GEP. Returns a pair containing
-/// the GEPs Pointer and Index.
-static std::pair<Value *, Value *>
-getAsConstantIndexedAddress(Type *ElemTy, Value *V, const DataLayout &DL) {
- Type *IndexType = IntegerType::get(V->getContext(),
- DL.getIndexTypeSizeInBits(V->getType()));
-
- Constant *Index = ConstantInt::getNullValue(IndexType);
- while (true) {
- if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
- // We accept only inbouds GEPs here to exclude the possibility of
- // overflow.
- if (!GEP->isInBounds())
- break;
- if (GEP->hasAllConstantIndices() && GEP->getNumIndices() == 1 &&
- GEP->getSourceElementType() == ElemTy) {
- V = GEP->getOperand(0);
- Constant *GEPIndex = static_cast<Constant *>(GEP->getOperand(1));
- Index = ConstantExpr::getAdd(
- Index, ConstantExpr::getSExtOrTrunc(GEPIndex, IndexType));
- continue;
- }
- break;
- }
- if (auto *CI = dyn_cast<IntToPtrInst>(V)) {
- if (!CI->isNoopCast(DL))
- break;
- V = CI->getOperand(0);
- continue;
- }
- if (auto *CI = dyn_cast<PtrToIntInst>(V)) {
- if (!CI->isNoopCast(DL))
- break;
- V = CI->getOperand(0);
- continue;
- }
- break;
- }
- return {V, Index};
-}
-
/// 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.
@@ -706,14 +629,19 @@ static Instruction *transformToIndexedCompare(GEPOperator *GEPLHS, Value *RHS,
if (!GEPLHS->hasAllConstantIndices())
return nullptr;
- Type *ElemTy = GEPLHS->getSourceElementType();
- Value *PtrBase, *Index;
- std::tie(PtrBase, Index) = getAsConstantIndexedAddress(ElemTy, GEPLHS, DL);
+ APInt Offset(DL.getIndexTypeSizeInBits(GEPLHS->getType()), 0);
+ Value *PtrBase =
+ GEPLHS->stripAndAccumulateConstantOffsets(DL, Offset,
+ /*AllowNonInbounds*/ false);
+
+ // Bail if we looked through addrspacecast.
+ if (PtrBase->getType() != GEPLHS->getType())
+ return nullptr;
// The set of nodes that will take part in this transformation.
SetVector<Value *> Nodes;
- if (!canRewriteGEPAsOffset(ElemTy, RHS, PtrBase, DL, Nodes))
+ if (!canRewriteGEPAsOffset(RHS, PtrBase, DL, Nodes))
return nullptr;
// We know we can re-write this as
@@ -722,13 +650,14 @@ static Instruction *transformToIndexedCompare(GEPOperator *GEPLHS, Value *RHS,
// can't have overflow on either side. We can therefore re-write
// this as:
// OFFSET1 cmp OFFSET2
- Value *NewRHS = rewriteGEPAsOffset(ElemTy, RHS, PtrBase, DL, Nodes, IC);
+ Value *NewRHS = rewriteGEPAsOffset(RHS, PtrBase, DL, Nodes, IC);
// RewriteGEPAsOffset has replaced RHS and all of its uses with a re-written
// GEP having PtrBase as the pointer base, and has returned in NewRHS the
// offset. Since Index is the offset of LHS to the base pointer, we will now
// compare the offsets instead of comparing the pointers.
- return new ICmpInst(ICmpInst::getSignedPredicate(Cond), Index, NewRHS);
+ return new ICmpInst(ICmpInst::getSignedPredicate(Cond),
+ IC.Builder.getInt(Offset), NewRHS);
}
/// Fold comparisons between a GEP instruction and something else. At this point
@@ -844,17 +773,6 @@ Instruction *InstCombinerImpl::foldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
return transformToIndexedCompare(GEPLHS, RHS, Cond, DL, *this);
}
- // If one of the GEPs has all zero indices, recurse.
- // FIXME: Handle vector of pointers.
- if (!GEPLHS->getType()->isVectorTy() && GEPLHS->hasAllZeroIndices())
- return foldGEPICmp(GEPRHS, GEPLHS->getOperand(0),
- ICmpInst::getSwappedPredicate(Cond), I);
-
- // If the other GEP has all zero indices, recurse.
- // FIXME: Handle vector of pointers.
- if (!GEPRHS->getType()->isVectorTy() && GEPRHS->hasAllZeroIndices())
- return foldGEPICmp(GEPLHS, GEPRHS->getOperand(0), Cond, I);
-
bool GEPsInBounds = GEPLHS->isInBounds() && GEPRHS->isInBounds();
if (GEPLHS->getNumOperands() == GEPRHS->getNumOperands() &&
GEPLHS->getSourceElementType() == GEPRHS->getSourceElementType()) {
@@ -894,8 +812,8 @@ Instruction *InstCombinerImpl::foldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
// Only lower this if the icmp is the only user of the GEP or if we expect
// the result to fold to a constant!
if ((GEPsInBounds || CmpInst::isEquality(Cond)) &&
- (isa<ConstantExpr>(GEPLHS) || GEPLHS->hasOneUse()) &&
- (isa<ConstantExpr>(GEPRHS) || GEPRHS->hasOneUse())) {
+ (GEPLHS->hasAllConstantIndices() || GEPLHS->hasOneUse()) &&
+ (GEPRHS->hasAllConstantIndices() || GEPRHS->hasOneUse())) {
// ((gep Ptr, OFFSET1) cmp (gep Ptr, OFFSET2) ---> (OFFSET1 cmp OFFSET2)
Value *L = EmitGEPOffset(GEPLHS);
Value *R = EmitGEPOffset(GEPRHS);
@@ -1285,9 +1203,9 @@ Instruction *InstCombinerImpl::foldICmpWithZero(ICmpInst &Cmp) {
if (Pred == ICmpInst::ICMP_SGT) {
Value *A, *B;
if (match(Cmp.getOperand(0), m_SMin(m_Value(A), m_Value(B)))) {
- if (isKnownPositive(A, DL, 0, &AC, &Cmp, &DT))
+ if (isKnownPositive(A, SQ.getWithInstruction(&Cmp)))
return new ICmpInst(Pred, B, Cmp.getOperand(1));
- if (isKnownPositive(B, DL, 0, &AC, &Cmp, &DT))
+ if (isKnownPositive(B, SQ.getWithInstruction(&Cmp)))
return new ICmpInst(Pred, A, Cmp.getOperand(1));
}
}
@@ -1554,6 +1472,61 @@ Instruction *InstCombinerImpl::foldICmpTruncConstant(ICmpInst &Cmp,
return nullptr;
}
+/// Fold icmp (trunc X), (trunc Y).
+/// Fold icmp (trunc X), (zext Y).
+Instruction *
+InstCombinerImpl::foldICmpTruncWithTruncOrExt(ICmpInst &Cmp,
+ const SimplifyQuery &Q) {
+ if (Cmp.isSigned())
+ return nullptr;
+
+ Value *X, *Y;
+ ICmpInst::Predicate Pred;
+ bool YIsZext = false;
+ // Try to match icmp (trunc X), (trunc Y)
+ if (match(&Cmp, m_ICmp(Pred, m_Trunc(m_Value(X)), m_Trunc(m_Value(Y))))) {
+ if (X->getType() != Y->getType() &&
+ (!Cmp.getOperand(0)->hasOneUse() || !Cmp.getOperand(1)->hasOneUse()))
+ return nullptr;
+ if (!isDesirableIntType(X->getType()->getScalarSizeInBits()) &&
+ isDesirableIntType(Y->getType()->getScalarSizeInBits())) {
+ std::swap(X, Y);
+ Pred = Cmp.getSwappedPredicate(Pred);
+ }
+ }
+ // Try to match icmp (trunc X), (zext Y)
+ else if (match(&Cmp, m_c_ICmp(Pred, m_Trunc(m_Value(X)),
+ m_OneUse(m_ZExt(m_Value(Y))))))
+
+ YIsZext = true;
+ else
+ return nullptr;
+
+ Type *TruncTy = Cmp.getOperand(0)->getType();
+ unsigned TruncBits = TruncTy->getScalarSizeInBits();
+
+ // If this transform will end up changing from desirable types -> undesirable
+ // types skip it.
+ if (isDesirableIntType(TruncBits) &&
+ !isDesirableIntType(X->getType()->getScalarSizeInBits()))
+ return nullptr;
+
+ // Check if the trunc is unneeded.
+ KnownBits KnownX = llvm::computeKnownBits(X, /*Depth*/ 0, Q);
+ if (KnownX.countMaxActiveBits() > TruncBits)
+ return nullptr;
+
+ if (!YIsZext) {
+ // If Y is also a trunc, make sure it is unneeded.
+ KnownBits KnownY = llvm::computeKnownBits(Y, /*Depth*/ 0, Q);
+ if (KnownY.countMaxActiveBits() > TruncBits)
+ return nullptr;
+ }
+
+ Value *NewY = Builder.CreateZExtOrTrunc(Y, X->getType());
+ return new ICmpInst(Pred, X, NewY);
+}
+
/// Fold icmp (xor X, Y), C.
Instruction *InstCombinerImpl::foldICmpXorConstant(ICmpInst &Cmp,
BinaryOperator *Xor,
@@ -1944,19 +1917,18 @@ Instruction *InstCombinerImpl::foldICmpAndConstant(ICmpInst &Cmp,
return nullptr;
}
-/// Fold icmp eq/ne (or (xor (X1, X2), xor(X3, X4))), 0.
-static Value *foldICmpOrXorChain(ICmpInst &Cmp, BinaryOperator *Or,
- InstCombiner::BuilderTy &Builder) {
- // Are we using xors to bitwise check for a pair or pairs of (in)equalities?
- // Convert to a shorter form that has more potential to be folded even
- // further.
- // ((X1 ^ X2) || (X3 ^ X4)) == 0 --> (X1 == X2) && (X3 == X4)
- // ((X1 ^ X2) || (X3 ^ X4)) != 0 --> (X1 != X2) || (X3 != X4)
- // ((X1 ^ X2) || (X3 ^ X4) || (X5 ^ X6)) == 0 -->
+/// Fold icmp eq/ne (or (xor/sub (X1, X2), xor/sub (X3, X4))), 0.
+static Value *foldICmpOrXorSubChain(ICmpInst &Cmp, BinaryOperator *Or,
+ InstCombiner::BuilderTy &Builder) {
+ // Are we using xors or subs to bitwise check for a pair or pairs of
+ // (in)equalities? Convert to a shorter form that has more potential to be
+ // folded even further.
+ // ((X1 ^/- X2) || (X3 ^/- X4)) == 0 --> (X1 == X2) && (X3 == X4)
+ // ((X1 ^/- X2) || (X3 ^/- X4)) != 0 --> (X1 != X2) || (X3 != X4)
+ // ((X1 ^/- X2) || (X3 ^/- X4) || (X5 ^/- X6)) == 0 -->
// (X1 == X2) && (X3 == X4) && (X5 == X6)
- // ((X1 ^ X2) || (X3 ^ X4) || (X5 ^ X6)) != 0 -->
+ // ((X1 ^/- X2) || (X3 ^/- X4) || (X5 ^/- X6)) != 0 -->
// (X1 != X2) || (X3 != X4) || (X5 != X6)
- // TODO: Implement for sub
SmallVector<std::pair<Value *, Value *>, 2> CmpValues;
SmallVector<Value *, 16> WorkList(1, Or);
@@ -1967,9 +1939,16 @@ static Value *foldICmpOrXorChain(ICmpInst &Cmp, BinaryOperator *Or,
if (match(OrOperatorArgument,
m_OneUse(m_Xor(m_Value(Lhs), m_Value(Rhs))))) {
CmpValues.emplace_back(Lhs, Rhs);
- } else {
- WorkList.push_back(OrOperatorArgument);
+ return;
}
+
+ if (match(OrOperatorArgument,
+ m_OneUse(m_Sub(m_Value(Lhs), m_Value(Rhs))))) {
+ CmpValues.emplace_back(Lhs, Rhs);
+ return;
+ }
+
+ WorkList.push_back(OrOperatorArgument);
};
Value *CurrentValue = WorkList.pop_back_val();
@@ -2082,7 +2061,7 @@ Instruction *InstCombinerImpl::foldICmpOrConstant(ICmpInst &Cmp,
return BinaryOperator::Create(BOpc, CmpP, CmpQ);
}
- if (Value *V = foldICmpOrXorChain(Cmp, Or, Builder))
+ if (Value *V = foldICmpOrXorSubChain(Cmp, Or, Builder))
return replaceInstUsesWith(Cmp, V);
return nullptr;
@@ -2443,7 +2422,7 @@ Instruction *InstCombinerImpl::foldICmpShrConstant(ICmpInst &Cmp,
// constant-value-based preconditions in the folds below, then we could assert
// those conditions rather than checking them. This is difficult because of
// undef/poison (PR34838).
- if (IsAShr) {
+ if (IsAShr && Shr->hasOneUse()) {
if (IsExact || Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_ULT) {
// When ShAmtC can be shifted losslessly:
// icmp PRED (ashr exact X, ShAmtC), C --> icmp PRED X, (C << ShAmtC)
@@ -2483,7 +2462,7 @@ Instruction *InstCombinerImpl::foldICmpShrConstant(ICmpInst &Cmp,
ConstantInt::getAllOnesValue(ShrTy));
}
}
- } else {
+ } else if (!IsAShr) {
if (Pred == CmpInst::ICMP_ULT || (Pred == CmpInst::ICMP_UGT && IsExact)) {
// icmp ult (lshr X, ShAmtC), C --> icmp ult X, (C << ShAmtC)
// icmp ugt (lshr exact X, ShAmtC), C --> icmp ugt X, (C << ShAmtC)
@@ -2888,19 +2867,97 @@ Instruction *InstCombinerImpl::foldICmpSubConstant(ICmpInst &Cmp,
return new ICmpInst(SwappedPred, Add, ConstantInt::get(Ty, ~C));
}
+static Value *createLogicFromTable(const std::bitset<4> &Table, Value *Op0,
+ Value *Op1, IRBuilderBase &Builder,
+ bool HasOneUse) {
+ auto FoldConstant = [&](bool Val) {
+ Constant *Res = Val ? Builder.getTrue() : Builder.getFalse();
+ if (Op0->getType()->isVectorTy())
+ Res = ConstantVector::getSplat(
+ cast<VectorType>(Op0->getType())->getElementCount(), Res);
+ return Res;
+ };
+
+ switch (Table.to_ulong()) {
+ case 0: // 0 0 0 0
+ return FoldConstant(false);
+ case 1: // 0 0 0 1
+ return HasOneUse ? Builder.CreateNot(Builder.CreateOr(Op0, Op1)) : nullptr;
+ case 2: // 0 0 1 0
+ return HasOneUse ? Builder.CreateAnd(Builder.CreateNot(Op0), Op1) : nullptr;
+ case 3: // 0 0 1 1
+ return Builder.CreateNot(Op0);
+ case 4: // 0 1 0 0
+ return HasOneUse ? Builder.CreateAnd(Op0, Builder.CreateNot(Op1)) : nullptr;
+ case 5: // 0 1 0 1
+ return Builder.CreateNot(Op1);
+ case 6: // 0 1 1 0
+ return Builder.CreateXor(Op0, Op1);
+ case 7: // 0 1 1 1
+ return HasOneUse ? Builder.CreateNot(Builder.CreateAnd(Op0, Op1)) : nullptr;
+ case 8: // 1 0 0 0
+ return Builder.CreateAnd(Op0, Op1);
+ case 9: // 1 0 0 1
+ return HasOneUse ? Builder.CreateNot(Builder.CreateXor(Op0, Op1)) : nullptr;
+ case 10: // 1 0 1 0
+ return Op1;
+ case 11: // 1 0 1 1
+ return HasOneUse ? Builder.CreateOr(Builder.CreateNot(Op0), Op1) : nullptr;
+ case 12: // 1 1 0 0
+ return Op0;
+ case 13: // 1 1 0 1
+ return HasOneUse ? Builder.CreateOr(Op0, Builder.CreateNot(Op1)) : nullptr;
+ case 14: // 1 1 1 0
+ return Builder.CreateOr(Op0, Op1);
+ case 15: // 1 1 1 1
+ return FoldConstant(true);
+ default:
+ llvm_unreachable("Invalid Operation");
+ }
+ return nullptr;
+}
+
/// Fold icmp (add X, Y), C.
Instruction *InstCombinerImpl::foldICmpAddConstant(ICmpInst &Cmp,
BinaryOperator *Add,
const APInt &C) {
Value *Y = Add->getOperand(1);
+ Value *X = Add->getOperand(0);
+
+ Value *Op0, *Op1;
+ Instruction *Ext0, *Ext1;
+ const CmpInst::Predicate Pred = Cmp.getPredicate();
+ if (match(Add,
+ m_Add(m_CombineAnd(m_Instruction(Ext0), m_ZExtOrSExt(m_Value(Op0))),
+ m_CombineAnd(m_Instruction(Ext1),
+ m_ZExtOrSExt(m_Value(Op1))))) &&
+ Op0->getType()->isIntOrIntVectorTy(1) &&
+ Op1->getType()->isIntOrIntVectorTy(1)) {
+ unsigned BW = C.getBitWidth();
+ std::bitset<4> Table;
+ auto ComputeTable = [&](bool Op0Val, bool Op1Val) {
+ int Res = 0;
+ if (Op0Val)
+ Res += isa<ZExtInst>(Ext0) ? 1 : -1;
+ if (Op1Val)
+ Res += isa<ZExtInst>(Ext1) ? 1 : -1;
+ return ICmpInst::compare(APInt(BW, Res, true), C, Pred);
+ };
+
+ Table[0] = ComputeTable(false, false);
+ Table[1] = ComputeTable(false, true);
+ Table[2] = ComputeTable(true, false);
+ Table[3] = ComputeTable(true, true);
+ if (auto *Cond =
+ createLogicFromTable(Table, Op0, Op1, Builder, Add->hasOneUse()))
+ return replaceInstUsesWith(Cmp, Cond);
+ }
const APInt *C2;
if (Cmp.isEquality() || !match(Y, m_APInt(C2)))
return nullptr;
// Fold icmp pred (add X, C2), C.
- Value *X = Add->getOperand(0);
Type *Ty = Add->getType();
- const CmpInst::Predicate Pred = Cmp.getPredicate();
// If the add does not wrap, we can always adjust the compare by subtracting
// the constants. Equality comparisons are handled elsewhere. SGE/SLE/UGE/ULE
@@ -3172,18 +3229,6 @@ Instruction *InstCombinerImpl::foldICmpBitCast(ICmpInst &Cmp) {
}
}
- // Test to see if the operands of the icmp are casted versions of other
- // values. If the ptr->ptr cast can be stripped off both arguments, do so.
- if (DstType->isPointerTy() && (isa<Constant>(Op1) || isa<BitCastInst>(Op1))) {
- // If operand #1 is a bitcast instruction, it must also be a ptr->ptr cast
- // so eliminate it as well.
- if (auto *BC2 = dyn_cast<BitCastInst>(Op1))
- Op1 = BC2->getOperand(0);
-
- Op1 = Builder.CreateBitCast(Op1, SrcType);
- return new ICmpInst(Pred, BCSrcOp, Op1);
- }
-
const APInt *C;
if (!match(Cmp.getOperand(1), m_APInt(C)) || !DstType->isIntegerTy() ||
!SrcType->isIntOrIntVectorTy())
@@ -3196,10 +3241,12 @@ Instruction *InstCombinerImpl::foldICmpBitCast(ICmpInst &Cmp) {
// icmp eq/ne (bitcast (not X) to iN), -1 --> icmp eq/ne (bitcast X to iN), 0
// Example: are all elements equal? --> are zero elements not equal?
// TODO: Try harder to reduce compare of 2 freely invertible operands?
- if (Cmp.isEquality() && C->isAllOnes() && Bitcast->hasOneUse() &&
- isFreeToInvert(BCSrcOp, BCSrcOp->hasOneUse())) {
- Value *Cast = Builder.CreateBitCast(Builder.CreateNot(BCSrcOp), DstType);
- return new ICmpInst(Pred, Cast, ConstantInt::getNullValue(DstType));
+ if (Cmp.isEquality() && C->isAllOnes() && Bitcast->hasOneUse()) {
+ if (Value *NotBCSrcOp =
+ getFreelyInverted(BCSrcOp, BCSrcOp->hasOneUse(), &Builder)) {
+ Value *Cast = Builder.CreateBitCast(NotBCSrcOp, DstType);
+ return new ICmpInst(Pred, Cast, ConstantInt::getNullValue(DstType));
+ }
}
// If this is checking if all elements of an extended vector are clear or not,
@@ -3878,21 +3925,9 @@ Instruction *InstCombinerImpl::foldICmpInstWithConstantNotInt(ICmpInst &I) {
return nullptr;
switch (LHSI->getOpcode()) {
- case Instruction::GetElementPtr:
- // icmp pred GEP (P, int 0, int 0, int 0), null -> icmp pred P, null
- 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:
- // Only fold icmp into the PHI if the phi and icmp are in the same
- // block. If in the same block, we're encouraging jump threading. If
- // not, we are just pessimizing the code by making an i1 phi.
- if (LHSI->getParent() == I.getParent())
- if (Instruction *NV = foldOpIntoPhi(I, cast<PHINode>(LHSI)))
- return NV;
+ if (Instruction *NV = foldOpIntoPhi(I, cast<PHINode>(LHSI)))
+ return NV;
break;
case Instruction::IntToPtr:
// icmp pred inttoptr(X), null -> icmp pred X, 0
@@ -4243,7 +4278,12 @@ foldShiftIntoShiftInAnotherHandOfAndInICmp(ICmpInst &I, const SimplifyQuery SQ,
/*isNUW=*/false, SQ.getWithInstruction(&I)));
if (!NewShAmt)
return nullptr;
- NewShAmt = ConstantExpr::getZExtOrBitCast(NewShAmt, WidestTy);
+ if (NewShAmt->getType() != WidestTy) {
+ NewShAmt =
+ ConstantFoldCastOperand(Instruction::ZExt, NewShAmt, WidestTy, SQ.DL);
+ if (!NewShAmt)
+ return nullptr;
+ }
unsigned WidestBitWidth = WidestTy->getScalarSizeInBits();
// Is the new shift amount smaller than the bit width?
@@ -4424,6 +4464,65 @@ static Instruction *foldICmpXNegX(ICmpInst &I,
return nullptr;
}
+static Instruction *foldICmpAndXX(ICmpInst &I, const SimplifyQuery &Q,
+ InstCombinerImpl &IC) {
+ Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1), *A;
+ // Normalize and operand as operand 0.
+ CmpInst::Predicate Pred = I.getPredicate();
+ if (match(Op1, m_c_And(m_Specific(Op0), m_Value()))) {
+ std::swap(Op0, Op1);
+ Pred = ICmpInst::getSwappedPredicate(Pred);
+ }
+
+ if (!match(Op0, m_c_And(m_Specific(Op1), m_Value(A))))
+ return nullptr;
+
+ // (icmp (X & Y) u< X --> (X & Y) != X
+ if (Pred == ICmpInst::ICMP_ULT)
+ return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1);
+
+ // (icmp (X & Y) u>= X --> (X & Y) == X
+ if (Pred == ICmpInst::ICMP_UGE)
+ return new ICmpInst(ICmpInst::ICMP_EQ, Op0, Op1);
+
+ return nullptr;
+}
+
+static Instruction *foldICmpOrXX(ICmpInst &I, const SimplifyQuery &Q,
+ InstCombinerImpl &IC) {
+ Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1), *A;
+
+ // Normalize or operand as operand 0.
+ CmpInst::Predicate Pred = I.getPredicate();
+ if (match(Op1, m_c_Or(m_Specific(Op0), m_Value(A)))) {
+ std::swap(Op0, Op1);
+ Pred = ICmpInst::getSwappedPredicate(Pred);
+ } else if (!match(Op0, m_c_Or(m_Specific(Op1), m_Value(A)))) {
+ return nullptr;
+ }
+
+ // icmp (X | Y) u<= X --> (X | Y) == X
+ if (Pred == ICmpInst::ICMP_ULE)
+ return new ICmpInst(ICmpInst::ICMP_EQ, Op0, Op1);
+
+ // icmp (X | Y) u> X --> (X | Y) != X
+ if (Pred == ICmpInst::ICMP_UGT)
+ return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1);
+
+ if (ICmpInst::isEquality(Pred) && Op0->hasOneUse()) {
+ // icmp (X | Y) eq/ne Y --> (X & ~Y) eq/ne 0 if Y is freely invertible
+ if (Value *NotOp1 =
+ IC.getFreelyInverted(Op1, Op1->hasOneUse(), &IC.Builder))
+ return new ICmpInst(Pred, IC.Builder.CreateAnd(A, NotOp1),
+ Constant::getNullValue(Op1->getType()));
+ // icmp (X | Y) eq/ne Y --> (~X | Y) eq/ne -1 if X is freely invertible.
+ if (Value *NotA = IC.getFreelyInverted(A, A->hasOneUse(), &IC.Builder))
+ return new ICmpInst(Pred, IC.Builder.CreateOr(Op1, NotA),
+ Constant::getAllOnesValue(Op1->getType()));
+ }
+ return nullptr;
+}
+
static Instruction *foldICmpXorXX(ICmpInst &I, const SimplifyQuery &Q,
InstCombinerImpl &IC) {
Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1), *A;
@@ -4746,6 +4845,8 @@ Instruction *InstCombinerImpl::foldICmpBinOp(ICmpInst &I,
if (Instruction * R = foldICmpXorXX(I, Q, *this))
return R;
+ if (Instruction *R = foldICmpOrXX(I, Q, *this))
+ return R;
{
// Try to remove shared multiplier from comparison:
@@ -4915,6 +5016,9 @@ Instruction *InstCombinerImpl::foldICmpBinOp(ICmpInst &I,
if (Value *V = foldICmpWithLowBitMaskedVal(I, Builder))
return replaceInstUsesWith(I, V);
+ if (Instruction *R = foldICmpAndXX(I, Q, *this))
+ return R;
+
if (Value *V = foldICmpWithTruncSignExtendedVal(I, Builder))
return replaceInstUsesWith(I, V);
@@ -4924,88 +5028,153 @@ Instruction *InstCombinerImpl::foldICmpBinOp(ICmpInst &I,
return nullptr;
}
-/// Fold icmp Pred min|max(X, Y), X.
-static Instruction *foldICmpWithMinMax(ICmpInst &Cmp) {
- ICmpInst::Predicate Pred = Cmp.getPredicate();
- Value *Op0 = Cmp.getOperand(0);
- Value *X = Cmp.getOperand(1);
-
- // Canonicalize minimum or maximum operand to LHS of the icmp.
- if (match(X, m_c_SMin(m_Specific(Op0), m_Value())) ||
- match(X, m_c_SMax(m_Specific(Op0), m_Value())) ||
- match(X, m_c_UMin(m_Specific(Op0), m_Value())) ||
- match(X, m_c_UMax(m_Specific(Op0), m_Value()))) {
- std::swap(Op0, X);
- Pred = Cmp.getSwappedPredicate();
- }
-
- Value *Y;
- if (match(Op0, m_c_SMin(m_Specific(X), m_Value(Y)))) {
- // smin(X, Y) == X --> X s<= Y
- // smin(X, Y) s>= X --> X s<= Y
- if (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_SGE)
- return new ICmpInst(ICmpInst::ICMP_SLE, X, Y);
-
- // smin(X, Y) != X --> X s> Y
- // smin(X, Y) s< X --> X s> Y
- if (Pred == CmpInst::ICMP_NE || Pred == CmpInst::ICMP_SLT)
- return new ICmpInst(ICmpInst::ICMP_SGT, X, Y);
-
- // These cases should be handled in InstSimplify:
- // smin(X, Y) s<= X --> true
- // smin(X, Y) s> X --> false
+/// Fold icmp Pred min|max(X, Y), Z.
+Instruction *
+InstCombinerImpl::foldICmpWithMinMaxImpl(Instruction &I,
+ MinMaxIntrinsic *MinMax, Value *Z,
+ ICmpInst::Predicate Pred) {
+ Value *X = MinMax->getLHS();
+ Value *Y = MinMax->getRHS();
+ if (ICmpInst::isSigned(Pred) && !MinMax->isSigned())
return nullptr;
- }
-
- if (match(Op0, m_c_SMax(m_Specific(X), m_Value(Y)))) {
- // smax(X, Y) == X --> X s>= Y
- // smax(X, Y) s<= X --> X s>= Y
- if (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_SLE)
- return new ICmpInst(ICmpInst::ICMP_SGE, X, Y);
-
- // smax(X, Y) != X --> X s< Y
- // smax(X, Y) s> X --> X s< Y
- if (Pred == CmpInst::ICMP_NE || Pred == CmpInst::ICMP_SGT)
- return new ICmpInst(ICmpInst::ICMP_SLT, X, Y);
-
- // These cases should be handled in InstSimplify:
- // smax(X, Y) s>= X --> true
- // smax(X, Y) s< X --> false
+ if (ICmpInst::isUnsigned(Pred) && MinMax->isSigned())
return nullptr;
+ SimplifyQuery Q = SQ.getWithInstruction(&I);
+ auto IsCondKnownTrue = [](Value *Val) -> std::optional<bool> {
+ if (!Val)
+ return std::nullopt;
+ if (match(Val, m_One()))
+ return true;
+ if (match(Val, m_Zero()))
+ return false;
+ return std::nullopt;
+ };
+ auto CmpXZ = IsCondKnownTrue(simplifyICmpInst(Pred, X, Z, Q));
+ auto CmpYZ = IsCondKnownTrue(simplifyICmpInst(Pred, Y, Z, Q));
+ if (!CmpXZ.has_value() && !CmpYZ.has_value())
+ return nullptr;
+ if (!CmpXZ.has_value()) {
+ std::swap(X, Y);
+ std::swap(CmpXZ, CmpYZ);
}
- if (match(Op0, m_c_UMin(m_Specific(X), m_Value(Y)))) {
- // umin(X, Y) == X --> X u<= Y
- // umin(X, Y) u>= X --> X u<= Y
- if (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_UGE)
- return new ICmpInst(ICmpInst::ICMP_ULE, X, Y);
-
- // umin(X, Y) != X --> X u> Y
- // umin(X, Y) u< X --> X u> Y
- if (Pred == CmpInst::ICMP_NE || Pred == CmpInst::ICMP_ULT)
- return new ICmpInst(ICmpInst::ICMP_UGT, X, Y);
+ auto FoldIntoCmpYZ = [&]() -> Instruction * {
+ if (CmpYZ.has_value())
+ return replaceInstUsesWith(I, ConstantInt::getBool(I.getType(), *CmpYZ));
+ return ICmpInst::Create(Instruction::ICmp, Pred, Y, Z);
+ };
- // These cases should be handled in InstSimplify:
- // umin(X, Y) u<= X --> true
- // umin(X, Y) u> X --> false
- return nullptr;
+ switch (Pred) {
+ case ICmpInst::ICMP_EQ:
+ case ICmpInst::ICMP_NE: {
+ // If X == Z:
+ // Expr Result
+ // min(X, Y) == Z X <= Y
+ // max(X, Y) == Z X >= Y
+ // min(X, Y) != Z X > Y
+ // max(X, Y) != Z X < Y
+ if ((Pred == ICmpInst::ICMP_EQ) == *CmpXZ) {
+ ICmpInst::Predicate NewPred =
+ ICmpInst::getNonStrictPredicate(MinMax->getPredicate());
+ if (Pred == ICmpInst::ICMP_NE)
+ NewPred = ICmpInst::getInversePredicate(NewPred);
+ return ICmpInst::Create(Instruction::ICmp, NewPred, X, Y);
+ }
+ // Otherwise (X != Z):
+ ICmpInst::Predicate NewPred = MinMax->getPredicate();
+ auto MinMaxCmpXZ = IsCondKnownTrue(simplifyICmpInst(NewPred, X, Z, Q));
+ if (!MinMaxCmpXZ.has_value()) {
+ std::swap(X, Y);
+ std::swap(CmpXZ, CmpYZ);
+ // Re-check pre-condition X != Z
+ if (!CmpXZ.has_value() || (Pred == ICmpInst::ICMP_EQ) == *CmpXZ)
+ break;
+ MinMaxCmpXZ = IsCondKnownTrue(simplifyICmpInst(NewPred, X, Z, Q));
+ }
+ if (!MinMaxCmpXZ.has_value())
+ break;
+ if (*MinMaxCmpXZ) {
+ // Expr Fact Result
+ // min(X, Y) == Z X < Z false
+ // max(X, Y) == Z X > Z false
+ // min(X, Y) != Z X < Z true
+ // max(X, Y) != Z X > Z true
+ return replaceInstUsesWith(
+ I, ConstantInt::getBool(I.getType(), Pred == ICmpInst::ICMP_NE));
+ } else {
+ // Expr Fact Result
+ // min(X, Y) == Z X > Z Y == Z
+ // max(X, Y) == Z X < Z Y == Z
+ // min(X, Y) != Z X > Z Y != Z
+ // max(X, Y) != Z X < Z Y != Z
+ return FoldIntoCmpYZ();
+ }
+ break;
+ }
+ case ICmpInst::ICMP_SLT:
+ case ICmpInst::ICMP_ULT:
+ case ICmpInst::ICMP_SLE:
+ case ICmpInst::ICMP_ULE:
+ case ICmpInst::ICMP_SGT:
+ case ICmpInst::ICMP_UGT:
+ case ICmpInst::ICMP_SGE:
+ case ICmpInst::ICMP_UGE: {
+ bool IsSame = MinMax->getPredicate() == ICmpInst::getStrictPredicate(Pred);
+ if (*CmpXZ) {
+ if (IsSame) {
+ // Expr Fact Result
+ // min(X, Y) < Z X < Z true
+ // min(X, Y) <= Z X <= Z true
+ // max(X, Y) > Z X > Z true
+ // max(X, Y) >= Z X >= Z true
+ return replaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
+ } else {
+ // Expr Fact Result
+ // max(X, Y) < Z X < Z Y < Z
+ // max(X, Y) <= Z X <= Z Y <= Z
+ // min(X, Y) > Z X > Z Y > Z
+ // min(X, Y) >= Z X >= Z Y >= Z
+ return FoldIntoCmpYZ();
+ }
+ } else {
+ if (IsSame) {
+ // Expr Fact Result
+ // min(X, Y) < Z X >= Z Y < Z
+ // min(X, Y) <= Z X > Z Y <= Z
+ // max(X, Y) > Z X <= Z Y > Z
+ // max(X, Y) >= Z X < Z Y >= Z
+ return FoldIntoCmpYZ();
+ } else {
+ // Expr Fact Result
+ // max(X, Y) < Z X >= Z false
+ // max(X, Y) <= Z X > Z false
+ // min(X, Y) > Z X <= Z false
+ // min(X, Y) >= Z X < Z false
+ return replaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
+ }
+ }
+ break;
+ }
+ default:
+ break;
}
- if (match(Op0, m_c_UMax(m_Specific(X), m_Value(Y)))) {
- // umax(X, Y) == X --> X u>= Y
- // umax(X, Y) u<= X --> X u>= Y
- if (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_ULE)
- return new ICmpInst(ICmpInst::ICMP_UGE, X, Y);
+ return nullptr;
+}
+Instruction *InstCombinerImpl::foldICmpWithMinMax(ICmpInst &Cmp) {
+ ICmpInst::Predicate Pred = Cmp.getPredicate();
+ Value *Lhs = Cmp.getOperand(0);
+ Value *Rhs = Cmp.getOperand(1);
- // umax(X, Y) != X --> X u< Y
- // umax(X, Y) u> X --> X u< Y
- if (Pred == CmpInst::ICMP_NE || Pred == CmpInst::ICMP_UGT)
- return new ICmpInst(ICmpInst::ICMP_ULT, X, Y);
+ if (MinMaxIntrinsic *MinMax = dyn_cast<MinMaxIntrinsic>(Lhs)) {
+ if (Instruction *Res = foldICmpWithMinMaxImpl(Cmp, MinMax, Rhs, Pred))
+ return Res;
+ }
- // These cases should be handled in InstSimplify:
- // umax(X, Y) u>= X --> true
- // umax(X, Y) u< X --> false
- return nullptr;
+ if (MinMaxIntrinsic *MinMax = dyn_cast<MinMaxIntrinsic>(Rhs)) {
+ if (Instruction *Res = foldICmpWithMinMaxImpl(
+ Cmp, MinMax, Lhs, ICmpInst::getSwappedPredicate(Pred)))
+ return Res;
}
return nullptr;
@@ -5173,35 +5342,6 @@ Instruction *InstCombinerImpl::foldICmpEquality(ICmpInst &I) {
return new ICmpInst(Pred, A, Builder.CreateTrunc(B, A->getType()));
}
- // Test if 2 values have different or same signbits:
- // (X u>> BitWidth - 1) == zext (Y s> -1) --> (X ^ Y) < 0
- // (X u>> BitWidth - 1) != zext (Y s> -1) --> (X ^ Y) > -1
- // (X s>> BitWidth - 1) == sext (Y s> -1) --> (X ^ Y) < 0
- // (X s>> BitWidth - 1) != sext (Y s> -1) --> (X ^ Y) > -1
- Instruction *ExtI;
- if (match(Op1, m_CombineAnd(m_Instruction(ExtI), m_ZExtOrSExt(m_Value(A)))) &&
- (Op0->hasOneUse() || Op1->hasOneUse())) {
- unsigned OpWidth = Op0->getType()->getScalarSizeInBits();
- Instruction *ShiftI;
- Value *X, *Y;
- ICmpInst::Predicate Pred2;
- if (match(Op0, m_CombineAnd(m_Instruction(ShiftI),
- m_Shr(m_Value(X),
- m_SpecificIntAllowUndef(OpWidth - 1)))) &&
- match(A, m_ICmp(Pred2, m_Value(Y), m_AllOnes())) &&
- Pred2 == ICmpInst::ICMP_SGT && X->getType() == Y->getType()) {
- unsigned ExtOpc = ExtI->getOpcode();
- unsigned ShiftOpc = ShiftI->getOpcode();
- if ((ExtOpc == Instruction::ZExt && ShiftOpc == Instruction::LShr) ||
- (ExtOpc == Instruction::SExt && ShiftOpc == Instruction::AShr)) {
- Value *Xor = Builder.CreateXor(X, Y, "xor.signbits");
- Value *R = (Pred == ICmpInst::ICMP_EQ) ? Builder.CreateIsNeg(Xor)
- : Builder.CreateIsNotNeg(Xor);
- return replaceInstUsesWith(I, R);
- }
- }
- }
-
// (A >> C) == (B >> C) --> (A^B) u< (1 << C)
// For lshr and ashr pairs.
const APInt *AP1, *AP2;
@@ -5307,6 +5447,40 @@ Instruction *InstCombinerImpl::foldICmpEquality(ICmpInst &I) {
Pred, A,
Builder.CreateIntrinsic(Op0->getType(), Intrinsic::fshl, {A, A, B}));
+ // Canonicalize:
+ // icmp eq/ne OneUse(A ^ Cst), B --> icmp eq/ne (A ^ B), Cst
+ Constant *Cst;
+ if (match(&I, m_c_ICmp(PredUnused,
+ m_OneUse(m_Xor(m_Value(A), m_ImmConstant(Cst))),
+ m_CombineAnd(m_Value(B), m_Unless(m_ImmConstant())))))
+ return new ICmpInst(Pred, Builder.CreateXor(A, B), Cst);
+
+ {
+ // (icmp eq/ne (and (add/sub/xor X, P2), P2), P2)
+ auto m_Matcher =
+ m_CombineOr(m_CombineOr(m_c_Add(m_Value(B), m_Deferred(A)),
+ m_c_Xor(m_Value(B), m_Deferred(A))),
+ m_Sub(m_Value(B), m_Deferred(A)));
+ std::optional<bool> IsZero = std::nullopt;
+ if (match(&I, m_c_ICmp(PredUnused, m_OneUse(m_c_And(m_Value(A), m_Matcher)),
+ m_Deferred(A))))
+ IsZero = false;
+ // (icmp eq/ne (and (add/sub/xor X, P2), P2), 0)
+ else if (match(&I,
+ m_ICmp(PredUnused, m_OneUse(m_c_And(m_Value(A), m_Matcher)),
+ m_Zero())))
+ IsZero = true;
+
+ if (IsZero && isKnownToBeAPowerOfTwo(A, /* OrZero */ true, /*Depth*/ 0, &I))
+ // (icmp eq/ne (and (add/sub/xor X, P2), P2), P2)
+ // -> (icmp eq/ne (and X, P2), 0)
+ // (icmp eq/ne (and (add/sub/xor X, P2), P2), 0)
+ // -> (icmp eq/ne (and X, P2), P2)
+ return new ICmpInst(Pred, Builder.CreateAnd(B, A),
+ *IsZero ? A
+ : ConstantInt::getNullValue(A->getType()));
+ }
+
return nullptr;
}
@@ -5383,8 +5557,8 @@ Instruction *InstCombinerImpl::foldICmpWithZextOrSext(ICmpInst &ICmp) {
// icmp Pred (ext X), (ext Y)
Value *Y;
if (match(ICmp.getOperand(1), m_ZExtOrSExt(m_Value(Y)))) {
- bool IsZext0 = isa<ZExtOperator>(ICmp.getOperand(0));
- bool IsZext1 = isa<ZExtOperator>(ICmp.getOperand(1));
+ bool IsZext0 = isa<ZExtInst>(ICmp.getOperand(0));
+ bool IsZext1 = isa<ZExtInst>(ICmp.getOperand(1));
if (IsZext0 != IsZext1) {
// If X and Y and both i1
@@ -5396,11 +5570,16 @@ Instruction *InstCombinerImpl::foldICmpWithZextOrSext(ICmpInst &ICmp) {
return new ICmpInst(ICmp.getPredicate(), Builder.CreateOr(X, Y),
Constant::getNullValue(X->getType()));
- // If we have mismatched casts, treat the zext of a non-negative source as
- // a sext to simulate matching casts. Otherwise, we are done.
- // TODO: Can we handle some predicates (equality) without non-negative?
- if ((IsZext0 && isKnownNonNegative(X, DL, 0, &AC, &ICmp, &DT)) ||
- (IsZext1 && isKnownNonNegative(Y, DL, 0, &AC, &ICmp, &DT)))
+ // If we have mismatched casts and zext has the nneg flag, we can
+ // treat the "zext nneg" as "sext". Otherwise, we cannot fold and quit.
+
+ auto *NonNegInst0 = dyn_cast<PossiblyNonNegInst>(ICmp.getOperand(0));
+ auto *NonNegInst1 = dyn_cast<PossiblyNonNegInst>(ICmp.getOperand(1));
+
+ bool IsNonNeg0 = NonNegInst0 && NonNegInst0->hasNonNeg();
+ bool IsNonNeg1 = NonNegInst1 && NonNegInst1->hasNonNeg();
+
+ if ((IsZext0 && IsNonNeg0) || (IsZext1 && IsNonNeg1))
IsSignedExt = true;
else
return nullptr;
@@ -5442,25 +5621,20 @@ Instruction *InstCombinerImpl::foldICmpWithZextOrSext(ICmpInst &ICmp) {
if (!C)
return nullptr;
- // Compute the constant that would happen if we truncated to SrcTy then
- // re-extended to DestTy.
+ // If a lossless truncate is possible...
Type *SrcTy = CastOp0->getSrcTy();
- Type *DestTy = CastOp0->getDestTy();
- Constant *Res1 = ConstantExpr::getTrunc(C, SrcTy);
- Constant *Res2 = ConstantExpr::getCast(CastOp0->getOpcode(), Res1, DestTy);
-
- // If the re-extended constant didn't change...
- if (Res2 == C) {
+ Constant *Res = getLosslessTrunc(C, SrcTy, CastOp0->getOpcode());
+ if (Res) {
if (ICmp.isEquality())
- return new ICmpInst(ICmp.getPredicate(), X, Res1);
+ return new ICmpInst(ICmp.getPredicate(), X, Res);
// A signed comparison of sign extended values simplifies into a
// signed comparison.
if (IsSignedExt && IsSignedCmp)
- return new ICmpInst(ICmp.getPredicate(), X, Res1);
+ return new ICmpInst(ICmp.getPredicate(), X, Res);
// The other three cases all fold into an unsigned comparison.
- return new ICmpInst(ICmp.getUnsignedPredicate(), X, Res1);
+ return new ICmpInst(ICmp.getUnsignedPredicate(), X, Res);
}
// The re-extended constant changed, partly changed (in the case of a vector),
@@ -5518,13 +5692,8 @@ Instruction *InstCombinerImpl::foldICmpWithCastOp(ICmpInst &ICmp) {
Value *NewOp1 = nullptr;
if (auto *PtrToIntOp1 = dyn_cast<PtrToIntOperator>(ICmp.getOperand(1))) {
Value *PtrSrc = PtrToIntOp1->getOperand(0);
- if (PtrSrc->getType()->getPointerAddressSpace() ==
- Op0Src->getType()->getPointerAddressSpace()) {
+ if (PtrSrc->getType() == Op0Src->getType())
NewOp1 = PtrToIntOp1->getOperand(0);
- // If the pointer types don't match, insert a bitcast.
- if (Op0Src->getType() != NewOp1->getType())
- NewOp1 = Builder.CreateBitCast(NewOp1, Op0Src->getType());
- }
} else if (auto *RHSC = dyn_cast<Constant>(ICmp.getOperand(1))) {
NewOp1 = ConstantExpr::getIntToPtr(RHSC, SrcTy);
}
@@ -5641,22 +5810,20 @@ bool InstCombinerImpl::OptimizeOverflowCheck(Instruction::BinaryOps BinaryOp,
/// \returns Instruction which must replace the compare instruction, NULL if no
/// replacement required.
static Instruction *processUMulZExtIdiom(ICmpInst &I, Value *MulVal,
- Value *OtherVal,
+ const APInt *OtherVal,
InstCombinerImpl &IC) {
// Don't bother doing this transformation for pointers, don't do it for
// vectors.
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);
auto *MulInstr = dyn_cast<Instruction>(MulVal);
if (!MulInstr)
return nullptr;
assert(MulInstr->getOpcode() == Instruction::Mul);
- auto *LHS = cast<ZExtOperator>(MulInstr->getOperand(0)),
- *RHS = cast<ZExtOperator>(MulInstr->getOperand(1));
+ auto *LHS = cast<ZExtInst>(MulInstr->getOperand(0)),
+ *RHS = cast<ZExtInst>(MulInstr->getOperand(1));
assert(LHS->getOpcode() == Instruction::ZExt);
assert(RHS->getOpcode() == Instruction::ZExt);
Value *A = LHS->getOperand(0), *B = RHS->getOperand(0);
@@ -5709,70 +5876,26 @@ static Instruction *processUMulZExtIdiom(ICmpInst &I, Value *MulVal,
// Recognize patterns
switch (I.getPredicate()) {
- case ICmpInst::ICMP_EQ:
- case ICmpInst::ICMP_NE:
- // Recognize pattern:
- // mulval = mul(zext A, zext B)
- // cmp eq/neq mulval, and(mulval, mask), mask selects low MulWidth bits.
- 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; // Recognized
- }
- }
- return nullptr;
-
- case ICmpInst::ICMP_UGT:
+ case ICmpInst::ICMP_UGT: {
// Recognize pattern:
// mulval = mul(zext A, zext B)
// cmp ugt mulval, max
- if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal)) {
- APInt MaxVal = APInt::getMaxValue(MulWidth);
- MaxVal = MaxVal.zext(CI->getBitWidth());
- if (MaxVal.eq(CI->getValue()))
- break; // Recognized
- }
- return nullptr;
-
- case ICmpInst::ICMP_UGE:
- // Recognize pattern:
- // mulval = mul(zext A, zext B)
- // cmp uge mulval, max+1
- if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal)) {
- APInt MaxVal = APInt::getOneBitSet(CI->getBitWidth(), MulWidth);
- if (MaxVal.eq(CI->getValue()))
- break; // Recognized
- }
- return nullptr;
-
- case ICmpInst::ICMP_ULE:
- // Recognize pattern:
- // mulval = mul(zext A, zext B)
- // cmp ule mulval, max
- if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal)) {
- APInt MaxVal = APInt::getMaxValue(MulWidth);
- MaxVal = MaxVal.zext(CI->getBitWidth());
- if (MaxVal.eq(CI->getValue()))
- break; // Recognized
- }
+ APInt MaxVal = APInt::getMaxValue(MulWidth);
+ MaxVal = MaxVal.zext(OtherVal->getBitWidth());
+ if (MaxVal.eq(*OtherVal))
+ break; // Recognized
return nullptr;
+ }
- case ICmpInst::ICMP_ULT:
+ case ICmpInst::ICMP_ULT: {
// Recognize pattern:
// mulval = mul(zext A, zext B)
// cmp ule mulval, max + 1
- if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal)) {
- APInt MaxVal = APInt::getOneBitSet(CI->getBitWidth(), MulWidth);
- if (MaxVal.eq(CI->getValue()))
- break; // Recognized
- }
+ APInt MaxVal = APInt::getOneBitSet(OtherVal->getBitWidth(), MulWidth);
+ if (MaxVal.eq(*OtherVal))
+ break; // Recognized
return nullptr;
+ }
default:
return nullptr;
@@ -5798,7 +5921,7 @@ static Instruction *processUMulZExtIdiom(ICmpInst &I, Value *MulVal,
if (MulVal->hasNUsesOrMore(2)) {
Value *Mul = Builder.CreateExtractValue(Call, 0, "umul.value");
for (User *U : make_early_inc_range(MulVal->users())) {
- if (U == &I || U == OtherVal)
+ if (U == &I)
continue;
if (TruncInst *TI = dyn_cast<TruncInst>(U)) {
if (TI->getType()->getPrimitiveSizeInBits() == MulWidth)
@@ -5819,34 +5942,10 @@ static Instruction *processUMulZExtIdiom(ICmpInst &I, Value *MulVal,
IC.addToWorklist(cast<Instruction>(U));
}
}
- if (isa<Instruction>(OtherVal))
- IC.addToWorklist(cast<Instruction>(OtherVal));
// The original icmp gets replaced with the overflow value, maybe inverted
// depending on predicate.
- 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) {
+ if (I.getPredicate() == ICmpInst::ICMP_ULT) {
Value *Res = Builder.CreateExtractValue(Call, 1);
return BinaryOperator::CreateNot(Res);
}
@@ -6015,13 +6114,19 @@ Instruction *InstCombinerImpl::foldICmpUsingKnownBits(ICmpInst &I) {
KnownBits Op0Known(BitWidth);
KnownBits Op1Known(BitWidth);
- if (SimplifyDemandedBits(&I, 0,
- getDemandedBitsLHSMask(I, BitWidth),
- Op0Known, 0))
- return &I;
+ {
+ // Don't use dominating conditions when folding icmp using known bits. This
+ // may convert signed into unsigned predicates in ways that other passes
+ // (especially IndVarSimplify) may not be able to reliably undo.
+ SQ.DC = nullptr;
+ auto _ = make_scope_exit([&]() { SQ.DC = &DC; });
+ if (SimplifyDemandedBits(&I, 0, getDemandedBitsLHSMask(I, BitWidth),
+ Op0Known, 0))
+ return &I;
- if (SimplifyDemandedBits(&I, 1, APInt::getAllOnes(BitWidth), Op1Known, 0))
- return &I;
+ if (SimplifyDemandedBits(&I, 1, APInt::getAllOnes(BitWidth), Op1Known, 0))
+ return &I;
+ }
// Given the known and unknown bits, compute a range that the LHS could be
// in. Compute the Min, Max and RHS values based on the known bits. For the
@@ -6269,57 +6374,70 @@ Instruction *InstCombinerImpl::foldICmpUsingBoolRange(ICmpInst &I) {
Y->getType()->isIntOrIntVectorTy(1) && Pred == ICmpInst::ICMP_ULE)
return BinaryOperator::CreateOr(Builder.CreateIsNull(X), Y);
+ // icmp eq/ne X, (zext/sext (icmp eq/ne X, C))
+ ICmpInst::Predicate Pred1, Pred2;
const APInt *C;
- if (match(I.getOperand(0), m_c_Add(m_ZExt(m_Value(X)), m_SExt(m_Value(Y)))) &&
- match(I.getOperand(1), m_APInt(C)) &&
- X->getType()->isIntOrIntVectorTy(1) &&
- Y->getType()->isIntOrIntVectorTy(1)) {
- unsigned BitWidth = C->getBitWidth();
- Pred = I.getPredicate();
- APInt Zero = APInt::getZero(BitWidth);
- APInt MinusOne = APInt::getAllOnes(BitWidth);
- APInt One(BitWidth, 1);
- if ((C->sgt(Zero) && Pred == ICmpInst::ICMP_SGT) ||
- (C->slt(Zero) && Pred == ICmpInst::ICMP_SLT))
- return replaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
- if ((C->sgt(One) && Pred == ICmpInst::ICMP_SLT) ||
- (C->slt(MinusOne) && Pred == ICmpInst::ICMP_SGT))
- return replaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
-
- if (I.getOperand(0)->hasOneUse()) {
- APInt NewC = *C;
- // canonicalize predicate to eq/ne
- if ((*C == Zero && Pred == ICmpInst::ICMP_SLT) ||
- (*C != Zero && *C != MinusOne && Pred == ICmpInst::ICMP_UGT)) {
- // x s< 0 in [-1, 1] --> x == -1
- // x u> 1(or any const !=0 !=-1) in [-1, 1] --> x == -1
- NewC = MinusOne;
- Pred = ICmpInst::ICMP_EQ;
- } else if ((*C == MinusOne && Pred == ICmpInst::ICMP_SGT) ||
- (*C != Zero && *C != One && Pred == ICmpInst::ICMP_ULT)) {
- // x s> -1 in [-1, 1] --> x != -1
- // x u< -1 in [-1, 1] --> x != -1
- Pred = ICmpInst::ICMP_NE;
- } else if (*C == Zero && Pred == ICmpInst::ICMP_SGT) {
- // x s> 0 in [-1, 1] --> x == 1
- NewC = One;
- Pred = ICmpInst::ICMP_EQ;
- } else if (*C == One && Pred == ICmpInst::ICMP_SLT) {
- // x s< 1 in [-1, 1] --> x != 1
- Pred = ICmpInst::ICMP_NE;
+ Instruction *ExtI;
+ if (match(&I, m_c_ICmp(Pred1, m_Value(X),
+ m_CombineAnd(m_Instruction(ExtI),
+ m_ZExtOrSExt(m_ICmp(Pred2, m_Deferred(X),
+ m_APInt(C)))))) &&
+ ICmpInst::isEquality(Pred1) && ICmpInst::isEquality(Pred2)) {
+ bool IsSExt = ExtI->getOpcode() == Instruction::SExt;
+ bool HasOneUse = ExtI->hasOneUse() && ExtI->getOperand(0)->hasOneUse();
+ auto CreateRangeCheck = [&] {
+ Value *CmpV1 =
+ Builder.CreateICmp(Pred1, X, Constant::getNullValue(X->getType()));
+ Value *CmpV2 = Builder.CreateICmp(
+ Pred1, X, ConstantInt::getSigned(X->getType(), IsSExt ? -1 : 1));
+ return BinaryOperator::Create(
+ Pred1 == ICmpInst::ICMP_EQ ? Instruction::Or : Instruction::And,
+ CmpV1, CmpV2);
+ };
+ if (C->isZero()) {
+ if (Pred2 == ICmpInst::ICMP_EQ) {
+ // icmp eq X, (zext/sext (icmp eq X, 0)) --> false
+ // icmp ne X, (zext/sext (icmp eq X, 0)) --> true
+ return replaceInstUsesWith(
+ I, ConstantInt::getBool(I.getType(), Pred1 == ICmpInst::ICMP_NE));
+ } else if (!IsSExt || HasOneUse) {
+ // icmp eq X, (zext (icmp ne X, 0)) --> X == 0 || X == 1
+ // icmp ne X, (zext (icmp ne X, 0)) --> X != 0 && X != 1
+ // icmp eq X, (sext (icmp ne X, 0)) --> X == 0 || X == -1
+ // icmp ne X, (sext (icmp ne X, 0)) --> X != 0 && X == -1
+ return CreateRangeCheck();
}
-
- if (NewC == MinusOne) {
- if (Pred == ICmpInst::ICMP_EQ)
- return BinaryOperator::CreateAnd(Builder.CreateNot(X), Y);
- if (Pred == ICmpInst::ICMP_NE)
- return BinaryOperator::CreateOr(X, Builder.CreateNot(Y));
- } else if (NewC == One) {
- if (Pred == ICmpInst::ICMP_EQ)
- return BinaryOperator::CreateAnd(X, Builder.CreateNot(Y));
- if (Pred == ICmpInst::ICMP_NE)
- return BinaryOperator::CreateOr(Builder.CreateNot(X), Y);
+ } else if (IsSExt ? C->isAllOnes() : C->isOne()) {
+ if (Pred2 == ICmpInst::ICMP_NE) {
+ // icmp eq X, (zext (icmp ne X, 1)) --> false
+ // icmp ne X, (zext (icmp ne X, 1)) --> true
+ // icmp eq X, (sext (icmp ne X, -1)) --> false
+ // icmp ne X, (sext (icmp ne X, -1)) --> true
+ return replaceInstUsesWith(
+ I, ConstantInt::getBool(I.getType(), Pred1 == ICmpInst::ICMP_NE));
+ } else if (!IsSExt || HasOneUse) {
+ // icmp eq X, (zext (icmp eq X, 1)) --> X == 0 || X == 1
+ // icmp ne X, (zext (icmp eq X, 1)) --> X != 0 && X != 1
+ // icmp eq X, (sext (icmp eq X, -1)) --> X == 0 || X == -1
+ // icmp ne X, (sext (icmp eq X, -1)) --> X != 0 && X == -1
+ return CreateRangeCheck();
}
+ } else {
+ // when C != 0 && C != 1:
+ // icmp eq X, (zext (icmp eq X, C)) --> icmp eq X, 0
+ // icmp eq X, (zext (icmp ne X, C)) --> icmp eq X, 1
+ // icmp ne X, (zext (icmp eq X, C)) --> icmp ne X, 0
+ // icmp ne X, (zext (icmp ne X, C)) --> icmp ne X, 1
+ // when C != 0 && C != -1:
+ // icmp eq X, (sext (icmp eq X, C)) --> icmp eq X, 0
+ // icmp eq X, (sext (icmp ne X, C)) --> icmp eq X, -1
+ // icmp ne X, (sext (icmp eq X, C)) --> icmp ne X, 0
+ // icmp ne X, (sext (icmp ne X, C)) --> icmp ne X, -1
+ return ICmpInst::Create(
+ Instruction::ICmp, Pred1, X,
+ ConstantInt::getSigned(X->getType(), Pred2 == ICmpInst::ICMP_NE
+ ? (IsSExt ? -1 : 1)
+ : 0));
}
}
@@ -6783,6 +6901,9 @@ Instruction *InstCombinerImpl::visitICmpInst(ICmpInst &I) {
if (Instruction *Res = foldICmpUsingKnownBits(I))
return Res;
+ if (Instruction *Res = foldICmpTruncWithTruncOrExt(I, Q))
+ return Res;
+
// Test if the ICmpInst instruction is used exclusively by a select as
// part of a minimum or maximum operation. If so, refrain from doing
// any other folding. This helps out other analyses which understand
@@ -6913,38 +7034,40 @@ Instruction *InstCombinerImpl::visitICmpInst(ICmpInst &I) {
return Res;
{
- Value *A, *B;
- // Transform (A & ~B) == 0 --> (A & B) != 0
- // and (A & ~B) != 0 --> (A & B) == 0
+ Value *X, *Y;
+ // Transform (X & ~Y) == 0 --> (X & Y) != 0
+ // and (X & ~Y) != 0 --> (X & Y) == 0
// if A is a power of 2.
- if (match(Op0, m_And(m_Value(A), m_Not(m_Value(B)))) &&
- match(Op1, m_Zero()) &&
- isKnownToBeAPowerOfTwo(A, false, 0, &I) && I.isEquality())
- return new ICmpInst(I.getInversePredicate(), Builder.CreateAnd(A, B),
+ if (match(Op0, m_And(m_Value(X), m_Not(m_Value(Y)))) &&
+ match(Op1, m_Zero()) && isKnownToBeAPowerOfTwo(X, false, 0, &I) &&
+ I.isEquality())
+ return new ICmpInst(I.getInversePredicate(), Builder.CreateAnd(X, Y),
Op1);
- // ~X < ~Y --> Y < X
- // ~X < C --> X > ~C
- if (match(Op0, m_Not(m_Value(A)))) {
- if (match(Op1, m_Not(m_Value(B))))
- return new ICmpInst(I.getPredicate(), B, A);
-
- const APInt *C;
- if (match(Op1, m_APInt(C)))
- return new ICmpInst(I.getSwappedPredicate(), A,
- ConstantInt::get(Op1->getType(), ~(*C)));
+ // Op0 pred Op1 -> ~Op1 pred ~Op0, if this allows us to drop an instruction.
+ if (Op0->getType()->isIntOrIntVectorTy()) {
+ bool ConsumesOp0, ConsumesOp1;
+ if (isFreeToInvert(Op0, Op0->hasOneUse(), ConsumesOp0) &&
+ isFreeToInvert(Op1, Op1->hasOneUse(), ConsumesOp1) &&
+ (ConsumesOp0 || ConsumesOp1)) {
+ Value *InvOp0 = getFreelyInverted(Op0, Op0->hasOneUse(), &Builder);
+ Value *InvOp1 = getFreelyInverted(Op1, Op1->hasOneUse(), &Builder);
+ assert(InvOp0 && InvOp1 &&
+ "Mismatch between isFreeToInvert and getFreelyInverted");
+ return new ICmpInst(I.getSwappedPredicate(), InvOp0, InvOp1);
+ }
}
Instruction *AddI = nullptr;
- if (match(&I, m_UAddWithOverflow(m_Value(A), m_Value(B),
+ if (match(&I, m_UAddWithOverflow(m_Value(X), m_Value(Y),
m_Instruction(AddI))) &&
- isa<IntegerType>(A->getType())) {
+ isa<IntegerType>(X->getType())) {
Value *Result;
Constant *Overflow;
// m_UAddWithOverflow can match patterns that do not include an explicit
// "add" instruction, so check the opcode of the matched op.
if (AddI->getOpcode() == Instruction::Add &&
- OptimizeOverflowCheck(Instruction::Add, /*Signed*/ false, A, B, *AddI,
+ OptimizeOverflowCheck(Instruction::Add, /*Signed*/ false, X, Y, *AddI,
Result, Overflow)) {
replaceInstUsesWith(*AddI, Result);
eraseInstFromFunction(*AddI);
@@ -6952,14 +7075,37 @@ Instruction *InstCombinerImpl::visitICmpInst(ICmpInst &I) {
}
}
- // (zext a) * (zext b) --> llvm.umul.with.overflow.
- if (match(Op0, m_NUWMul(m_ZExt(m_Value(A)), m_ZExt(m_Value(B))))) {
- if (Instruction *R = processUMulZExtIdiom(I, Op0, Op1, *this))
+ // (zext X) * (zext Y) --> llvm.umul.with.overflow.
+ if (match(Op0, m_NUWMul(m_ZExt(m_Value(X)), m_ZExt(m_Value(Y)))) &&
+ match(Op1, m_APInt(C))) {
+ if (Instruction *R = processUMulZExtIdiom(I, Op0, C, *this))
return R;
}
- if (match(Op1, m_NUWMul(m_ZExt(m_Value(A)), m_ZExt(m_Value(B))))) {
- if (Instruction *R = processUMulZExtIdiom(I, Op1, Op0, *this))
- return R;
+
+ // Signbit test folds
+ // Fold (X u>> BitWidth - 1 Pred ZExt(i1)) --> X s< 0 Pred i1
+ // Fold (X s>> BitWidth - 1 Pred SExt(i1)) --> X s< 0 Pred i1
+ Instruction *ExtI;
+ if ((I.isUnsigned() || I.isEquality()) &&
+ match(Op1,
+ m_CombineAnd(m_Instruction(ExtI), m_ZExtOrSExt(m_Value(Y)))) &&
+ Y->getType()->getScalarSizeInBits() == 1 &&
+ (Op0->hasOneUse() || Op1->hasOneUse())) {
+ unsigned OpWidth = Op0->getType()->getScalarSizeInBits();
+ Instruction *ShiftI;
+ if (match(Op0, m_CombineAnd(m_Instruction(ShiftI),
+ m_Shr(m_Value(X), m_SpecificIntAllowUndef(
+ OpWidth - 1))))) {
+ unsigned ExtOpc = ExtI->getOpcode();
+ unsigned ShiftOpc = ShiftI->getOpcode();
+ if ((ExtOpc == Instruction::ZExt && ShiftOpc == Instruction::LShr) ||
+ (ExtOpc == Instruction::SExt && ShiftOpc == Instruction::AShr)) {
+ Value *SLTZero =
+ Builder.CreateICmpSLT(X, Constant::getNullValue(X->getType()));
+ Value *Cmp = Builder.CreateICmp(Pred, SLTZero, Y, I.getName());
+ return replaceInstUsesWith(I, Cmp);
+ }
+ }
}
}
@@ -7177,17 +7323,14 @@ Instruction *InstCombinerImpl::foldFCmpIntToFPConst(FCmpInst &I,
}
// Okay, now we know that the FP constant fits in the range [SMIN, SMAX] or
- // [0, UMAX], but it may still be fractional. See if it is fractional by
- // casting the FP value to the integer value and back, checking for equality.
+ // [0, UMAX], but it may still be fractional. Check whether this is the case
+ // using the IsExact flag.
// Don't do this for zero, because -0.0 is not fractional.
- Constant *RHSInt = LHSUnsigned
- ? ConstantExpr::getFPToUI(RHSC, IntTy)
- : ConstantExpr::getFPToSI(RHSC, IntTy);
+ APSInt RHSInt(IntWidth, LHSUnsigned);
+ bool IsExact;
+ RHS.convertToInteger(RHSInt, APFloat::rmTowardZero, &IsExact);
if (!RHS.isZero()) {
- bool Equal = LHSUnsigned
- ? ConstantExpr::getUIToFP(RHSInt, RHSC->getType()) == RHSC
- : ConstantExpr::getSIToFP(RHSInt, RHSC->getType()) == RHSC;
- if (!Equal) {
+ if (!IsExact) {
// If we had a comparison against a fractional value, we have to adjust
// the compare predicate and sometimes the value. RHSC is rounded towards
// zero at this point.
@@ -7253,7 +7396,7 @@ Instruction *InstCombinerImpl::foldFCmpIntToFPConst(FCmpInst &I,
// Lower this FP comparison into an appropriate integer version of the
// comparison.
- return new ICmpInst(Pred, LHSI->getOperand(0), RHSInt);
+ return new ICmpInst(Pred, LHSI->getOperand(0), Builder.getInt(RHSInt));
}
/// Fold (C / X) < 0.0 --> X < 0.0 if possible. Swap predicate if necessary.
@@ -7532,12 +7675,8 @@ Instruction *InstCombinerImpl::visitFCmpInst(FCmpInst &I) {
if (match(Op0, m_Instruction(LHSI)) && match(Op1, m_Constant(RHSC))) {
switch (LHSI->getOpcode()) {
case Instruction::PHI:
- // Only fold fcmp into the PHI if the phi and fcmp are in the same
- // block. If in the same block, we're encouraging jump threading. If
- // not, we are just pessimizing the code by making an i1 phi.
- if (LHSI->getParent() == I.getParent())
- if (Instruction *NV = foldOpIntoPhi(I, cast<PHINode>(LHSI)))
- return NV;
+ if (Instruction *NV = foldOpIntoPhi(I, cast<PHINode>(LHSI)))
+ return NV;
break;
case Instruction::SIToFP:
case Instruction::UIToFP:
generated by cgit v1.3 (git 2.53.0) at 2026-05-06 03:32:25 +0000