From af1480aea6dc3e393e8acc02feba65b4ad7e2b10 Mon Sep 17 00:00:00 2001 From: James Molloy Date: Thu, 22 Oct 2015 13:18:42 +0000 Subject: [PATCH] [ValueTracking] Add a new predicate: isKnownNonEqual() isKnownNonEqual(A, B) returns true if it can be determined that A != B. At the moment it only knows two facts, that a non-wrapping add of nonzero to a value cannot be that value: A + B != A [where B != 0, addition is nsw or nuw] and that contradictory known bits imply two values are not equal. This patch also hooks this up to InstSimplify; InstSimplify had a peephole for the first fact but not the second so this teaches InstSimplify a new trick too (alas no measured performance impact!) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@251012 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/ValueTracking.h | 7 +++ lib/Analysis/InstructionSimplify.cpp | 8 +++ lib/Analysis/ValueTracking.cpp | 56 +++++++++++++++++++ .../Analysis/ValueTracking/known-non-equal.ll | 21 +++++++ 4 files changed, 92 insertions(+) create mode 100644 test/Analysis/ValueTracking/known-non-equal.ll diff --git a/include/llvm/Analysis/ValueTracking.h b/include/llvm/Analysis/ValueTracking.h index 53b2e61ee6e..90c8b1e7bc9 100644 --- a/include/llvm/Analysis/ValueTracking.h +++ b/include/llvm/Analysis/ValueTracking.h @@ -90,6 +90,13 @@ namespace llvm { const Instruction *CxtI = nullptr, const DominatorTree *DT = nullptr); + /// isKnownNonEqual - Return true if the given values are known to be + /// non-equal when defined. Supports scalar integer types only. + bool isKnownNonEqual(Value *V1, Value *V2, const DataLayout &DL, + AssumptionCache *AC = nullptr, + const Instruction *CxtI = nullptr, + const DominatorTree *DT = nullptr); + /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use /// this predicate to simplify operations downstream. Mask is known to be /// zero for bits that V cannot have. diff --git a/lib/Analysis/InstructionSimplify.cpp b/lib/Analysis/InstructionSimplify.cpp index 8175fbd76d6..be5ce2960ea 100644 --- a/lib/Analysis/InstructionSimplify.cpp +++ b/lib/Analysis/InstructionSimplify.cpp @@ -2642,6 +2642,14 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, } } + // icmp eq|ne X, Y -> false|true if X != Y + if ((Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE) && + isKnownNonEqual(LHS, RHS, Q.DL, Q.AC, Q.CxtI, Q.DT)) { + LLVMContext &Ctx = LHS->getType()->getContext(); + return Pred == ICmpInst::ICMP_NE ? + ConstantInt::getTrue(Ctx) : ConstantInt::getFalse(Ctx); + } + // Special logic for binary operators. BinaryOperator *LBO = dyn_cast(LHS); BinaryOperator *RBO = dyn_cast(RHS); diff --git a/lib/Analysis/ValueTracking.cpp b/lib/Analysis/ValueTracking.cpp index e83a5793bf3..ad6be85f87a 100644 --- a/lib/Analysis/ValueTracking.cpp +++ b/lib/Analysis/ValueTracking.cpp @@ -193,6 +193,17 @@ bool llvm::isKnownNonNegative(Value *V, const DataLayout &DL, unsigned Depth, return NonNegative; } +static bool isKnownNonEqual(Value *V1, Value *V2, const DataLayout &DL, + const Query &Q); + +bool llvm::isKnownNonEqual(Value *V1, Value *V2, const DataLayout &DL, + AssumptionCache *AC, const Instruction *CxtI, + const DominatorTree *DT) { + return ::isKnownNonEqual(V1, V2, DL, Query(AC, + safeCxtI(V1, safeCxtI(V2, CxtI)), + DT)); +} + static bool MaskedValueIsZero(Value *V, const APInt &Mask, const DataLayout &DL, unsigned Depth, const Query &Q); @@ -1950,6 +1961,51 @@ bool isKnownNonZero(Value *V, const DataLayout &DL, unsigned Depth, return KnownOne != 0; } +/// Return true if V2 == V1 + X, where X is known non-zero. +static bool isAddOfNonZero(Value *V1, Value *V2, const DataLayout &DL, + const Query &Q) { + BinaryOperator *BO = dyn_cast(V1); + if (!BO || BO->getOpcode() != Instruction::Add) + return false; + Value *Op = nullptr; + if (V2 == BO->getOperand(0)) + Op = BO->getOperand(1); + else if (V2 == BO->getOperand(1)) + Op = BO->getOperand(0); + else + return false; + return isKnownNonZero(Op, DL, 0, Q); +} + +/// Return true if it is known that V1 != V2. +static bool isKnownNonEqual(Value *V1, Value *V2, const DataLayout &DL, + const Query &Q) { + if (V1->getType()->isVectorTy() || V1 == V2) + return false; + if (V1->getType() != V2->getType()) + // We can't look through casts yet. + return false; + if (isAddOfNonZero(V1, V2, DL, Q) || isAddOfNonZero(V2, V1, DL, Q)) + return true; + + if (IntegerType *Ty = dyn_cast(V1->getType())) { + // Are any known bits in V1 contradictory to known bits in V2? If V1 + // has a known zero where V2 has a known one, they must not be equal. + auto BitWidth = Ty->getBitWidth(); + APInt KnownZero1(BitWidth, 0); + APInt KnownOne1(BitWidth, 0); + computeKnownBits(V1, KnownZero1, KnownOne1, DL, 0, Q); + APInt KnownZero2(BitWidth, 0); + APInt KnownOne2(BitWidth, 0); + computeKnownBits(V2, KnownZero2, KnownOne2, DL, 0, Q); + + auto OppositeBits = (KnownZero1 & KnownOne2) | (KnownZero2 & KnownOne1); + if (OppositeBits.getBoolValue()) + return true; + } + return false; +} + /// Return true if 'V & Mask' is known to be zero. We use this predicate to /// simplify operations downstream. Mask is known to be zero for bits that V /// cannot have. diff --git a/test/Analysis/ValueTracking/known-non-equal.ll b/test/Analysis/ValueTracking/known-non-equal.ll new file mode 100644 index 00000000000..d28b3f4f63a --- /dev/null +++ b/test/Analysis/ValueTracking/known-non-equal.ll @@ -0,0 +1,21 @@ +; RUN: opt -instsimplify < %s -S | FileCheck %s + +; CHECK: define i1 @test +define i1 @test(i8* %pq, i8 %B) { + %q = load i8, i8* %pq, !range !0 ; %q is known nonzero; no known bits + %A = add nsw i8 %B, %q + %cmp = icmp eq i8 %A, %B + ; CHECK: ret i1 false + ret i1 %cmp +} + +; CHECK: define i1 @test2 +define i1 @test2(i8 %a, i8 %b) { + %A = or i8 %a, 2 ; %A[1] = 1 + %B = and i8 %b, -3 ; %B[1] = 0 + %cmp = icmp eq i8 %A, %B ; %A[1] and %B[1] are contradictory. + ; CHECK: ret i1 false + ret i1 %cmp +} + +!0 = !{ i8 1, i8 5 } -- 2.34.1