From 05cff99a29b2df17142907aa81ae488559756f01 Mon Sep 17 00:00:00 2001 From: Noah Goldstein Date: Thu, 28 Mar 2024 14:24:01 -0500 Subject: [ValueTracking] Infer known bits fromfrom `(icmp eq (and/or x,y), C)` In `(icmp eq (and x,y), C)` all 1s in `C` must also be set in both `x`/`y`. In `(icmp eq (or x,y), C)` all 0s in `C` must also be set in both `x`/`y`. Closes #87143 --- llvm/lib/Analysis/ValueTracking.cpp | 21 +++++++++++++++------ llvm/test/Transforms/InstCombine/known-bits.ll | 14 +++++--------- llvm/test/Transforms/InstCombine/zext-or-icmp.ll | 10 +++++----- 3 files changed, 25 insertions(+), 20 deletions(-) (limited to 'llvm') diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp index b5e8a1d..33a6986 100644 --- a/llvm/lib/Analysis/ValueTracking.cpp +++ b/llvm/lib/Analysis/ValueTracking.cpp @@ -648,6 +648,7 @@ static void computeKnownBitsFromCmp(const Value *V, CmpInst::Predicate Pred, auto m_V = m_CombineOr(m_Specific(V), m_PtrToIntSameSize(Q.DL, m_Specific(V))); + Value *Y; const APInt *Mask, *C; uint64_t ShAmt; switch (Pred) { @@ -656,16 +657,18 @@ static void computeKnownBitsFromCmp(const Value *V, CmpInst::Predicate Pred, if (match(LHS, m_V) && match(RHS, m_APInt(C))) { Known = Known.unionWith(KnownBits::makeConstant(*C)); // assume(V & Mask = C) - } else if (match(LHS, m_And(m_V, m_APInt(Mask))) && + } else if (match(LHS, m_c_And(m_V, m_Value(Y))) && match(RHS, m_APInt(C))) { // For one bits in Mask, we can propagate bits from C to V. - Known.Zero |= ~*C & *Mask; - Known.One |= *C & *Mask; + Known.One |= *C; + if (match(Y, m_APInt(Mask))) + Known.Zero |= ~*C & *Mask; // assume(V | Mask = C) - } else if (match(LHS, m_Or(m_V, m_APInt(Mask))) && match(RHS, m_APInt(C))) { + } else if (match(LHS, m_c_Or(m_V, m_Value(Y))) && match(RHS, m_APInt(C))) { // For zero bits in Mask, we can propagate bits from C to V. - Known.Zero |= ~*C & ~*Mask; - Known.One |= *C & ~*Mask; + Known.Zero |= ~*C; + if (match(Y, m_APInt(Mask))) + Known.One |= *C & ~*Mask; // assume(V ^ Mask = C) } else if (match(LHS, m_Xor(m_V, m_APInt(Mask))) && match(RHS, m_APInt(C))) { @@ -9276,11 +9279,17 @@ void llvm::findValuesAffectedByCondition( if (ICmpInst::isEquality(Pred)) { if (match(B, m_ConstantInt())) { + Value *Y; // (X & C) or (X | C) or (X ^ C). // (X << C) or (X >>_s C) or (X >>_u C). if (match(A, m_BitwiseLogic(m_Value(X), m_ConstantInt())) || match(A, m_Shift(m_Value(X), m_ConstantInt()))) AddAffected(X); + else if (match(A, m_And(m_Value(X), m_Value(Y))) || + match(A, m_Or(m_Value(X), m_Value(Y)))) { + AddAffected(X); + AddAffected(Y); + } } } else { // Handle (A + C1) u< C2, which is the canonical form of diff --git a/llvm/test/Transforms/InstCombine/known-bits.ll b/llvm/test/Transforms/InstCombine/known-bits.ll index af3db82..769f766 100644 --- a/llvm/test/Transforms/InstCombine/known-bits.ll +++ b/llvm/test/Transforms/InstCombine/known-bits.ll @@ -534,8 +534,7 @@ define i8 @and_eq_bits_must_be_set(i8 %x, i8 %y) { ; CHECK-NEXT: [[XY:%.*]] = and i8 [[X:%.*]], [[Y:%.*]] ; CHECK-NEXT: [[CMP:%.*]] = icmp eq i8 [[XY]], 123 ; CHECK-NEXT: call void @llvm.assume(i1 [[CMP]]) -; CHECK-NEXT: [[R:%.*]] = and i8 [[X]], 1 -; CHECK-NEXT: ret i8 [[R]] +; CHECK-NEXT: ret i8 1 ; %xy = and i8 %x, %y %cmp = icmp eq i8 %xy, 123 @@ -549,8 +548,7 @@ define i8 @and_eq_bits_must_be_set2(i8 %x, i8 %y) { ; CHECK-NEXT: [[XY:%.*]] = and i8 [[X:%.*]], [[Y:%.*]] ; CHECK-NEXT: [[CMP:%.*]] = icmp eq i8 [[XY]], 123 ; CHECK-NEXT: call void @llvm.assume(i1 [[CMP]]) -; CHECK-NEXT: [[R:%.*]] = and i8 [[Y]], 11 -; CHECK-NEXT: ret i8 [[R]] +; CHECK-NEXT: ret i8 11 ; %xy = and i8 %x, %y %cmp = icmp eq i8 %xy, 123 @@ -579,8 +577,7 @@ define i8 @or_eq_bits_must_be_unset(i8 %x, i8 %y) { ; CHECK-NEXT: [[XY:%.*]] = or i8 [[X:%.*]], [[Y:%.*]] ; CHECK-NEXT: [[CMP:%.*]] = icmp eq i8 [[XY]], 124 ; CHECK-NEXT: call void @llvm.assume(i1 [[CMP]]) -; CHECK-NEXT: [[R:%.*]] = and i8 [[X]], 3 -; CHECK-NEXT: ret i8 [[R]] +; CHECK-NEXT: ret i8 0 ; %xy = or i8 %x, %y %cmp = icmp eq i8 %xy, 124 @@ -594,8 +591,7 @@ define i8 @or_eq_bits_must_be_unset2(i8 %x, i8 %y) { ; CHECK-NEXT: [[XY:%.*]] = or i8 [[X:%.*]], [[Y:%.*]] ; CHECK-NEXT: [[CMP:%.*]] = icmp eq i8 [[XY]], 124 ; CHECK-NEXT: call void @llvm.assume(i1 [[CMP]]) -; CHECK-NEXT: [[R:%.*]] = and i8 [[Y]], 1 -; CHECK-NEXT: ret i8 [[R]] +; CHECK-NEXT: ret i8 0 ; %xy = or i8 %x, %y %cmp = icmp eq i8 %xy, 124 @@ -609,7 +605,7 @@ define i8 @or_eq_bits_must_be_unset2_partial_fail(i8 %x, i8 %y) { ; CHECK-NEXT: [[XY:%.*]] = or i8 [[X:%.*]], [[Y:%.*]] ; CHECK-NEXT: [[CMP:%.*]] = icmp eq i8 [[XY]], 124 ; CHECK-NEXT: call void @llvm.assume(i1 [[CMP]]) -; CHECK-NEXT: [[R:%.*]] = and i8 [[Y]], 7 +; CHECK-NEXT: [[R:%.*]] = and i8 [[Y]], 4 ; CHECK-NEXT: ret i8 [[R]] ; %xy = or i8 %x, %y diff --git a/llvm/test/Transforms/InstCombine/zext-or-icmp.ll b/llvm/test/Transforms/InstCombine/zext-or-icmp.ll index 661c360..a4b74aa 100644 --- a/llvm/test/Transforms/InstCombine/zext-or-icmp.ll +++ b/llvm/test/Transforms/InstCombine/zext-or-icmp.ll @@ -1,5 +1,5 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt < %s -passes=instcombine -S | FileCheck %s +; RUN: opt < %s -passes='instcombine' -S | FileCheck %s define i8 @zext_or_icmp_icmp(i8 %a, i8 %b) { ; CHECK-LABEL: @zext_or_icmp_icmp( @@ -180,11 +180,11 @@ define i8 @PR49475_infloop(i32 %t0, i16 %insert, i64 %e, i8 %i162) { ; CHECK-NEXT: [[SEXT:%.*]] = shl i64 [[SUB17]], 32 ; CHECK-NEXT: [[CONV18:%.*]] = ashr exact i64 [[SEXT]], 32 ; CHECK-NEXT: [[CMP:%.*]] = icmp sge i64 [[XOR]], [[CONV18]] -; CHECK-NEXT: [[CONV19:%.*]] = zext i1 [[CMP]] to i16 -; CHECK-NEXT: [[OR21:%.*]] = or i16 [[CONV19]], [[INSERT]] -; CHECK-NEXT: [[TOBOOL23_NOT:%.*]] = icmp eq i16 [[OR21]], 0 +; CHECK-NEXT: [[TRUNC44:%.*]] = zext i1 [[CMP]] to i8 +; CHECK-NEXT: [[INC:%.*]] = add i8 [[TRUNC44]], [[I162]] +; CHECK-NEXT: [[TOBOOL23_NOT:%.*]] = xor i1 [[CMP]], true ; CHECK-NEXT: call void @llvm.assume(i1 [[TOBOOL23_NOT]]) -; CHECK-NEXT: ret i8 [[I162]] +; CHECK-NEXT: ret i8 [[INC]] ; %b = icmp eq i32 %t0, 0 %b2 = icmp eq i16 %insert, 0 -- cgit v1.1