[InstCombine] Optimize test for same-sign of values

[emgullufsen]

Summary

Add pattern-matching code for instructions testing for same-sign of two inputs, and reduce. e.g:

define i1 @samesign(i32 %x, i32 %y) {
  %a = and i32 %x, %y
  %lt = icmp slt i32 %a, 0
  %o = or i32 %x, %y
  %gt = icmp sgt i32 %o, -1
  %r = or i1 %lt, %gt
  ret i1 %r
}

becomes =>

define i1 @samesign(i32 %x, i32 %y) {
  %a = xor i32 %x, %y
  %r = icmp sgt i32 %a, -1
  ret i1 %r
}

alive2 example
godbolt

Also now covering the inverted form (example):

define i1 @samesign_inverted(i32 %x, i32 %y) {
  %a = and i32 %x, %y
  %gt = icmp sgt i32 %a, -1
  %o = or i32 %x, %y
  %lt = icmp slt i32 %o, 0
  %r = and i1 %gt, %lt
  ret i1 %r
}

becomes =>

define i1 @samesign_inverted(i32 %x, i32 %y) {
  %3 = xor i32 %x, %y
  %4 = icmp slt i32 %3, 0
  ret i1 %4
}

godbolt for inverted form
alive2 for inverted form
issue #55988

[emgullufsen]

I am in the process of writing more regression tests, but I may need to ask a few questions on that - thank you for your help thus far.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2638

It's fine to ignore the inverted logic pattern that ends with an 'and' instruction, but please put a TODO comment on this, so we know it can be handled in a follow-up patch.

2643

Have a look at the m_Specific matcher - we really only have 2 variables in this pattern, so you can just call them X and Y as shown in your code comment.

To match commuted patterns, see m_c_Or / m_c_And.

Check this file for examples of existing code that uses those calls.

2651

ConstantInt::getAllOnesValue()

llvm/test/Transforms/InstCombine/same-sign-naive.ll

3

You can tack more tests on to the end of related tests in "and-or-icmps.ll".
You can also get an idea about how to vary tests to get better coverage by looking at existing tests.
One common variation to test (and code for): what happens if the intermediate values have other uses?

[emgullufsen]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2638

Ah good call - will amend in updated patch (and will start looking at the inverted pattern (for a separate patch).

2643

ack - I ought to have thought to use the commutative m_c_ matchers - thank you, will amend in updated patch

2651

very cool thank you I knew there had to be a better way for that construction - will amend in updated patch

[emgullufsen]

llvm/test/Transforms/InstCombine/same-sign-naive.ll

3

Ah I see - roger that - I'll have more tests in update patch - thank you!

[emgullufsen]

Updated patch to cover the inverted form as well and wrote 5 more tests.
Trying to ensure we only reduce iff intermediate values have one use only.

[spatel]

The uploaded diff is against the previous revision of this patch. Please rebase so it is against (and can be applied cleanly to) the main branch.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2643

It doesn't make sense to use the commutative matcher on the first match - we're matching 2 arbitrary values, so it will succeed either way.

llvm/test/Transforms/InstCombine/and-or-icmps.ll

2103

We should have tests for commuted patterns like:

define i1 @samesign_commute1(i32 %x, i32 %y) {
	%a = and i32 %x, %y
	%lt = icmp slt i32 %a, 0
	%o = or i32 %x, %y
	%gt = icmp sgt i32 %o, -1
	%r = or i1 %gt, %lt  ; compares are swapped
	ret i1 %r
}

define i1 @samesign_commute2(i32 %x, i32 %y) {
	%a = and i32 %x, %y
	%lt = icmp slt i32 %a, 0
	%o = or i32 %y, %x  ; source values are commuted
	%gt = icmp sgt i32 %o, -1
	%r = or i1 %lt, %gt
	ret i1 %r
}

define i1 @samesign_commute3(i32 %x, i32 %y) {
	%a = and i32 %x, %y
	%lt = icmp slt i32 %a, 0
	%o = or i32 %y, %x  ; source values are commuted
	%gt = icmp sgt i32 %o, -1
	%r = or i1 %gt, %lt ; compares are swapped
	ret i1 %r
}

2156

We should have "negative" tests for patterns that fail to match one or more of the constraints. Example:

define i1 @samesign_inverted_wrong_cmp(i32 %x, i32 %y) {
  %a = and i32 %x, %y
  %gt = icmp sgt i32 %a, 0 ; this is not a sign-bit test
  %o = or i32 %x, %y
  %lt = icmp slt i32 %o, 0
  %r = and i1 %gt, %lt
  ret i1 %r
}

[emgullufsen]

Ah of course - sorry for that - I will submit a new diff for this revision (including suggested changes) against the main branch (not previous diff).

[emgullufsen]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2643

Good call, that makes sense - will amend in updated diff (which will be against main, not stacked on previous diff).

llvm/test/Transforms/InstCombine/and-or-icmps.ll

2103

Oh yes I see - cool thank you I will get these commuted tests included in next diff.

2156

Ah I see, gotcha - thanks for your help I really appreciate it!

[emgullufsen]

Not using m_c matchers on first match and added "Negative" tests and tests for commutativity of inputs and compares.

[emgullufsen]

A few of the tests contained incorrect syntax in the CHECK lines. They were re-capturing variables (i.e. [[x:%.*]]) instead of matching where needed [[x]].

[emgullufsen]

Fixed more incorrect use of capture in CHECK line in one test.

[emgullufsen]

Fixed one more incorrect use of capturing in CHECK line.

[spatel]

In D127903#3594030, @emgullufsen wrote:

Fixed one more incorrect use of capturing in CHECK line.

Did you generate the CHECK lines manually? We don't want to do that generally.
Sorry - I should have mentioned this earlier, but we prefer to use a script that is shown on the first line of the test file :
; NOTE: Assertions have been autogenerated by utils/update_test_checks.py

[emgullufsen]

Oh dang my bad on that - I had actually read in the testing infra guide about those scripts, and really ought to have used them - I'll do so now.

[emgullufsen]

Assertions in test CHECK lines now generated via utils/update_test_checks.py

[emgullufsen]

Added four more negative tests that violate constraints.

[emgullufsen]

Added tests to make sure other sign-bit tests are picked up as well

[spatel]

I committed the tests with baseline results, so we have those in place independently of the code change. I then updated the tests to provide a bit more coverage. Please rebase/update after:
feb4b336acc71

It's programmer preference, but I think it'd be easier to read with less IsAnd ? () :() constructs, so something like this:

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
index cc06e2fd45db..4f8814475e12 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -2647,6 +2647,38 @@ Value *InstCombinerImpl::foldAndOrOfICmps(ICmpInst *LHS, ICmpInst *RHS,
     }
   }
 
+  // Match naive pattern (and its inverted form) for checking if two values
+  // share same sign. An example of the pattern: (icmp slt (X & Y), 0) | (icmp
+  // sgt (X | Y), -1) -> (icmp sgt (X ^ Y), -1) Inverted form (example): (icmp
+  // slt (X | Y), 0) & (icmp sgt (X & Y), -1) -> (icmp slt (X ^ Y), 0)
+  bool TrueIfSignedL, TrueIfSignedR;
+  if (InstCombiner::isSignBitCheck(PredL, *LHSC, TrueIfSignedL) &&
+      InstCombiner::isSignBitCheck(PredR, *RHSC, TrueIfSignedR) &&
+      (RHS->hasOneUse() || LHS->hasOneUse())) {
+    Value *X, *Y;
+    if (IsAnd) {
+      if ((TrueIfSignedL && !TrueIfSignedR &&
+           match(LHS0, m_Or(m_Value(X), m_Value(Y))) &&
+           match(RHS0, m_c_And(m_Specific(X), m_Specific(Y)))) ||
+          (!TrueIfSignedL && TrueIfSignedR &&
+           match(LHS0, m_And(m_Value(X), m_Value(Y))) &&
+           match(RHS0, m_c_Or(m_Specific(X), m_Specific(Y))))) {
+        Value *NewXor = Builder.CreateXor(X, Y);
+        return Builder.CreateIsNeg(NewXor);
+      }
+    } else {
+      if (((TrueIfSignedL && !TrueIfSignedR &&
+            match(LHS0, m_And(m_Value(X), m_Value(Y))) &&
+            match(RHS0, m_c_Or(m_Specific(X), m_Specific(Y))))) ||
+          (!TrueIfSignedL && TrueIfSignedR &&
+           match(LHS0, m_Or(m_Value(X), m_Value(Y))) &&
+           match(RHS0, m_c_And(m_Specific(X), m_Specific(Y))))) {
+        Value *NewXor = Builder.CreateXor(X, Y);
+        return Builder.CreateIsNotNeg(NewXor);
+      }
+    }
+  }
+
   return foldAndOrOfICmpsUsingRanges(LHS, RHS, IsAnd);
 }

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2640

The use checks are too strict. This optimization should be a win as long as any one of the intermediate values has one use. We are creating 2 new values, so as long as we can remove one of the old ones + the final value, it is an improvement.

I'd make this:

(LHS->hasOneUse() || RHS->hasOneUse())

..and remove the use checks for LHS0 and RHS0 under here.

2654–2658

There's a Builder shortcut to create the new ICmp: CreateIsNeg / CreateIsNotNeg.

[emgullufsen]

In D127903#3594645, @spatel wrote:

I committed the tests with baseline results, so we have those in place independently of the code change. I then updated the tests to provide a bit more coverage. Please rebase/update after:
feb4b336acc71

Sounds good will do, thank you!

It's programmer preference, but I think it'd be easier to read with less IsAnd ? () :() constructs, so something like this:

Sounds good, I prefer with less ternary operator as well - I had been a bit myopic about only building the returned instructions (calling Builder.CreateXor and the like) once. This is definitely nicer without so many conditionals - will amend in updated diff. Thank you for the diff (and copious help) as well!

[emgullufsen]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2640

Alrighty I see now - sounds good thank you - will amend in updated diff.

2654–2658

Aha very cool thank you - will amend in updated diff.

[emgullufsen]

Prefer less IsAnd constructs in matching logic, update test results.

[spatel]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (SmallC && BigC) {
         Value *NewAnd = Builder.CreateAnd(V, Low | *AndC);
         APInt N = SmallC->zext(BigBitSize) | *BigC;
         Value *NewVal = ConstantInt::get(NewAnd->getType(), N);
         return Builder.CreateICmp(PredL, NewAnd, NewVal);
       }
     }
   }
 
-  // match naive pattern for checking if two values share same sign,
-  // an example of the pattern:
-  // (icmp slt (X & Y), 0) | (icmp sgt (X | Y), -1) -> (icmp sgt (X ^ Y), -1)
-  // first, check if icmp on both sides are sign-bit-checks
+  // Match naive pattern (and its inverted form) for checking if two values
+  // share same sign. An example of the pattern: (icmp slt (X & Y), 0) | (icmp
+  // sgt (X | Y), -1) -> (icmp sgt (X ^ Y), -1) Inverted form (example): (icmp
+  // slt (X | Y), 0) & (icmp sgt (X & Y), -1) -> (icmp slt (X ^ Y), 0)
   bool TrueIfSignedL, TrueIfSignedR;
-  if (!IsAnd && InstCombiner::isSignBitCheck(PredL, *LHSC, TrueIfSignedL) &&
-      InstCombiner::isSignBitCheck(PredR, *RHSC, TrueIfSignedR)) {
-    Value *LHSX, *LHSY, *RHSX, *RHSY;
+  if (InstCombiner::isSignBitCheck(PredL, *LHSC, TrueIfSignedL) &&
+      InstCombiner::isSignBitCheck(PredR, *RHSC, TrueIfSignedR) &&
+      RHS->hasOneUse() && LHS->hasOneUse()) {
+    Value *X, *Y;
     if (((TrueIfSignedL && !TrueIfSignedR &&
-          match(LHS0, m_And(m_Value(LHSX), m_Value(LHSY))) &&
-          match(RHS0, m_Or(m_Value(RHSX), m_Value(RHSY)))) ||
+          (IsAnd ? match(LHS0, m_c_Or(m_Value(X), m_Value(Y)))
+                 : match(LHS0, m_c_And(m_Value(X), m_Value(Y)))) &&
+          (IsAnd ? match(RHS0, m_c_And(m_Specific(X), m_Specific(Y)))
+                 : match(RHS0, m_c_Or(m_Specific(X), m_Specific(Y))))) ||
          (!TrueIfSignedL && TrueIfSignedR &&
-          match(RHS0, m_And(m_Value(RHSX), m_Value(RHSY))) &&
-          match(LHS0, m_Or(m_Value(LHSX), m_Value(LHSY))))) &&
-        ((LHSX == RHSX && LHSY == RHSY) || (LHSX == RHSY && LHSY == RHSX))) {
-      // build return inst
-      Value *NewXor = Builder.CreateXor(LHSX, LHSY);
-      APInt W = APInt(32, -1, true);
-      Value *NewC = ConstantInt::get(NewXor->getType(), W);
-      return Builder.CreateICmp(ICmpInst::ICMP_SGT, NewXor, NewC);
+          (IsAnd ? match(LHS0, m_c_And(m_Value(X), m_Value(Y)))
+                 : match(LHS0, m_c_Or(m_Value(X), m_Value(Y)))) &&
+          (IsAnd ? match(RHS0, m_c_Or(m_Specific(X), m_Specific(Y)))
+                 : match(RHS0, m_c_And(m_Specific(X), m_Specific(Y)))))) &&
+        LHS0->hasOneUse() && RHS0->hasOneUse()) {
+      Value *NewXor = Builder.CreateXor(X, Y);
+      Value *NewC = IsAnd ? ConstantInt::getNullValue(NewXor->getType())
+                          : ConstantInt::getAllOnesValue(NewXor->getType());
+      ICmpInst::Predicate NewPred =
+          IsAnd ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_SGT;
+      return Builder.CreateICmp(NewPred, NewXor, NewC);
     }
   }
 
   return foldAndOrOfICmpsUsingRanges(LHS, RHS, IsAnd);
 }
 
 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
 // here. We should standardize that construct where it is needed or choose some

llvm/test/Transforms/InstCombine/and-or-icmps.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 declare void @use(i1)
+declare void @use32(i32)
 
 define i1 @PR1817_1(i32 %X) {
 ; CHECK-LABEL: @PR1817_1(
 ; CHECK-NEXT:    [[B:%.*]] = icmp ult i32 [[X:%.*]], 10
 ; CHECK-NEXT:    ret i1 [[B]]
 ;
   %A = icmp slt i32 %X, 10
   %B = icmp ult i32 %X, 10
;
   %x.m1 = and i32 %x, 8
   %c1 = icmp eq i32 %x.m1, 8
   %and1 = select i1 %c1, i1 %c, i1 false
   %x.m2 = and i32 %x, %y
   %c2 = icmp eq i32 %x.m2, %y
   %and2 = and i1 %and1, %c2
   ret i1 %and2
 }
+
+define i1 @samesign(i32 %x, i32 %y) {
+; CHECK-LABEL: @samesign(
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[x:%.*]], [[y:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i32 [[TMP1]], -1
+; CHECK-NEXT:    ret i1 [[TMP2]]
+  %a = and i32 %x, %y
+  %lt = icmp slt i32 %a, 0
+  %o = or i32 %x, %y
+  %gt = icmp sgt i32 %o, -1
+  %r = or i1 %lt, %gt
+  ret i1 %r
+}
+
+define i1 @samesign_mult_use(i32 %x, i32 %y) {
+  ; CHECK-LABEL: @samesign_mult_use(
+  ; CHECK-NEXT:  [[a:%.*]] = and i32 [[x:%.*]], [[y:%.*]]
+  ; CHECK-NEXT:  call void @use32(i32 [[a]])
+  ; CHECK-NEXT:  [[lt:%.*]] = icmp slt i32 [[a]], 0
+  ; CHECK-NEXT:  [[o:%.*]] = or i32 [[x:%.*]], [[y:%.*]]
+  ; CHECK-NEXT:  call void @use32(i32 [[o]])
+  ; CHECK-NEXT:  [[gt:%.*]] = icmp sgt i32 [[o:%.*]], -1
+  ; CHECK-NEXT:  [[r:%.*]] = and i1 [[lt:%.*]], [[gt:%.*]]
+  ; CHECK-NEXT:  ret i1 [[r:%.*]]
+  %a = and i32 %x, %y
+  call void @use32(i32 %a)
+  %lt = icmp slt i32 %a, 0
+  %o = or i32 %x, %y
+  call void @use32(i32 %o)
+  %gt = icmp sgt i32 %o, -1
+  %r = and i1 %lt, %gt
+  ret i1 %r
+}
+
+define i1 @samesign_mult_use2(i32 %x, i32 %y) {
+  ; CHECK-LABEL: @samesign_mult_use2(
+  ; CHECK-NEXT:  [[a:%.*]] = and i32 [[x:%.*]], [[y:%.*]]
+  ; CHECK-NEXT:  [[lt:%.*]] = icmp slt i32 [[a]], 0
+  ; CHECK-NEXT:  call void @use(i1 [[lt]])
+  ; CHECK-NEXT:  [[o:%.*]] = or i32 [[x:%.*]], [[y:%.*]]
+  ; CHECK-NEXT:  [[gt:%.*]] = icmp sgt i32 [[o]], -1
+  ; CHECK-NEXT:  call void @use(i1 [[gt]])
+  ; CHECK-NEXT:  [[r:%.*]] = and i1 [[lt]], [[gt]]
+  ; CHECK-NEXT:  ret i1 [[r:%.*]]
+  %a = and i32 %x, %y
+  %lt = icmp slt i32 %a, 0
+  call void @use(i1 %lt)
+  %o = or i32 %x, %y
+  %gt = icmp sgt i32 %o, -1
+  call void @use(i1 %gt)
+  %r = and i1 %lt, %gt
+  ret i1 %r
+}
+
+define i1 @samesign_inverted(i32 %x, i32 %y) {
+  ; CHECK-LABEL: @samesign_inverted(
+  ; CHECK-NEXT:  [[TMP1:%.*]] = xor i32 [[x:%.*]], [[y:%.*]]
+  ; CHECK-NEXT:  [[TMP2:%.*]] = icmp slt i32 [[TMP1]], 0
+  ; CHECK-NEXT:  ret i1 [[TMP2]]
+  %a = and i32 %x, %y
+  %gt = icmp sgt i32 %a, -1
+  %o = or i32 %x, %y
+  %lt = icmp slt i32 %o, 0
+  %r = and i1 %gt, %lt
+  ret i1 %r
+}
+
+define i1 @samesign_inverted_mult_use(i32 %x, i32 %y) {
+  ; CHECK-LABEL: @samesign_inverted_mult_use(
+  ; CHECK-NEXT:  [[a:%.*]] = and i32 [[x:%.*]], [[y:%.*]]
+  ; CHECK-NEXT:  call void @use32(i32 [[a]])
+  ; CHECK-NEXT:  [[gt:%.*]] = icmp sgt i32 [[a]], -1
+  ; CHECK-NEXT:  [[o:%.*]] = or i32 [[x:%.*]], [[y:%.*]]
+  ; CHECK-NEXT:  call void @use32(i32 [[o]])
+  ; CHECK-NEXT:  [[lt:%.*]] = icmp slt i32 [[o]], 0
+  ; CHECK-NEXT:  [[r:%.*]] = and i1 [[gt]], [[lt]]
+  ; CHECK-NEXT:  ret i1 [[r:%.*]]
+  %a = and i32 %x, %y
+  call void @use32(i32 %a)
+  %gt = icmp sgt i32 %a, -1
+  %o = or i32 %x, %y
+  call void @use32(i32 %o)
+  %lt = icmp slt i32 %o, 0
+  %r = and i1 %gt, %lt
+  ret i1 %r
+}
+
+define i1 @samesign_inverted_mult_use2(i32 %x, i32 %y) {
+  ; CHECK-LABEL: @samesign_inverted_mult_use2(
+  ; CHECK-NEXT:  [[a:%.*]] = and i32 [[x:%.*]], [[y:%.*]]
+  ; CHECK-NEXT:  [[gt:%.*]] = icmp sgt i32 [[a]], -1
+  ; CHECK-NEXT:  call void @use(i1 [[gt]])
+  ; CHECK-NEXT:  [[o:%.*]] = or i32 [[x:%.*]], [[y:%.*]]
+  ; CHECK-NEXT:  [[lt:%.*]] = icmp slt i32 [[o]], 0
+  ; CHECK-NEXT:  call void @use(i1 [[lt]])
+  ; CHECK-NEXT:  [[r:%.*]] = and i1 [[gt]], [[lt]]
+  ; CHECK-NEXT:  ret i1 [[r]]
+  %a = and i32 %x, %y
+  %gt = icmp sgt i32 %a, -1
+  call void @use(i1 %gt)
+  %o = or i32 %x, %y
+  %lt = icmp slt i32 %o, 0
+  call void @use(i1 %lt)
+  %r = and i1 %gt, %lt
+  ret i1 %r
+}

llvm/test/Transforms/InstCombine/same-sign-naive.ll

-; RUN: opt < %s -passes=instcombine -S | FileCheck %s
-
-define i1 @samesign(i32 %x, i32 %y) {
-; CHECK-LABEL: @samesign(
-; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[x:%.*]], [[y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i32 [[TMP1]], -1
-; CHECK-NEXT:    ret i1 [[TMP2]]
-  %a = and i32 %x, %y
-  %lt = icmp slt i32 %a, 0
-  %o = or i32 %x, %y
-  %gt = icmp sgt i32 %o, -1
-  %r = or i1 %lt, %gt
-  ret i1 %r
-}