From d44ba4a7c6103a1e0543f02b342d87f17063560a Mon Sep 17 00:00:00 2001 From: James Molloy Date: Thu, 24 Sep 2015 16:06:32 +0000 Subject: [PATCH] [ValueTracking] Teach isKnownNonZero a new trick If the shifter operand is a constant, and all of the bits shifted out are known to be zero, then if X is known non-zero at least one non-zero bit must remain. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@248508 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/ValueTracking.cpp | 17 +++++++++++++++++ test/Analysis/ValueTracking/knownzero-shift.ll | 14 ++++++++++++++ 2 files changed, 31 insertions(+) create mode 100644 test/Analysis/ValueTracking/knownzero-shift.ll diff --git a/lib/Analysis/ValueTracking.cpp b/lib/Analysis/ValueTracking.cpp index 10776a03cae..417122be0d8 100644 --- a/lib/Analysis/ValueTracking.cpp +++ b/lib/Analysis/ValueTracking.cpp @@ -1827,6 +1827,23 @@ bool isKnownNonZero(Value *V, const DataLayout &DL, unsigned Depth, ComputeSignBit(X, XKnownNonNegative, XKnownNegative, DL, Depth, Q); if (XKnownNegative) return true; + + // If the shifter operand is a constant, and all of the bits shifted + // out are known to be zero, and X is known non-zero then at least one + // non-zero bit must remain. + if (ConstantInt *Shift = dyn_cast(Y)) { + APInt KnownZero(BitWidth, 0); + APInt KnownOne(BitWidth, 0); + computeKnownBits(X, KnownZero, KnownOne, DL, Depth, Q); + + auto ShiftVal = Shift->getLimitedValue(BitWidth - 1); + // Is there a known one in the portion not shifted out? + if (KnownOne.countLeadingZeros() < BitWidth - ShiftVal) + return true; + // Are all the bits to be shifted out known zero? + if (KnownZero.countTrailingOnes() >= ShiftVal) + return isKnownNonZero(X, DL, Depth, Q); + } } // div exact can only produce a zero if the dividend is zero. else if (match(V, m_Exact(m_IDiv(m_Value(X), m_Value())))) { diff --git a/test/Analysis/ValueTracking/knownzero-shift.ll b/test/Analysis/ValueTracking/knownzero-shift.ll new file mode 100644 index 00000000000..835d87a9d9c --- /dev/null +++ b/test/Analysis/ValueTracking/knownzero-shift.ll @@ -0,0 +1,14 @@ +; RUN: opt -instsimplify -S < %s | FileCheck %s + +; CHECK-LABEL: @test +define i1 @test(i8 %p, i8* %pq) { + %q = load i8, i8* %pq, !range !0 ; %q is known nonzero; no known bits + %1 = or i8 %p, 2 ; %1[1] = 1 + %2 = and i8 %1, 254 ; %2[0] = 0, %2[1] = 1 + %A = lshr i8 %2, 1 ; We should know that %A is nonzero. + %x = icmp eq i8 %A, 0 + ; CHECK: ret i1 false + ret i1 %x +} + +!0 = !{ i8 1, i8 5 } -- 2.34.1