[InstSimplify] recognize trunc + icmp sgt/slt variants of select simplifications (PR28466)

[spatel]

Summary

rL245171 exposed a hole in InstSimplify that manifested in a strange way in PR28466:
https://llvm.org/bugs/show_bug.cgi?id=28466

It's possible to use trunc + icmp sgt/slt in place of an and + icmp eq/ne, so we need to recognize that pattern to eliminate selects that are choosing between some value and some bitmasked version of that value.

[eli.friedman]

It looks like there are other places that look for bit-tests which are affected... see https://github.com/llvm-mirror/llvm/blob/dba9c3285e87768e80da6ca60f73b8913392dd98/lib/Transforms/InstCombine/InstCombineSelect.cpp#L579 , https://github.com/llvm-mirror/llvm/blob/65165b21da2aaed908f7bde1b8a16e7a8fe0c955/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp#L597 . Maybe we want a separate utility function to condense this functionality, so we don't end up with so many versions of it?

lib/Analysis/InstructionSimplify.cpp

3411

Do we want to look through the truncate in something like "(trunc X) & C == C2 ? X : Y"?

3414

getScalarSizeInBits? (This could be a vector select.)

[spatel]

In D22537#489198, @eli.friedman wrote:

It looks like there are other places that look for bit-tests which are affected... see https://github.com/llvm-mirror/llvm/blob/dba9c3285e87768e80da6ca60f73b8913392dd98/lib/Transforms/InstCombine/InstCombineSelect.cpp#L579 , https://github.com/llvm-mirror/llvm/blob/65165b21da2aaed908f7bde1b8a16e7a8fe0c955/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp#L597 . Maybe we want a separate utility function to condense this functionality, so we don't end up with so many versions of it?

Yikes - I didn't realize it was so blatantly copied in other places. That is pretty shameful. Let me see if there's a quick fix, otherwise I'll mark it as a FIXME for this patch.

lib/Analysis/InstructionSimplify.cpp

3411

Is this the pattern in the last 4 tests of this patch, or something more general?

3414

Yes - this was copied from the existing code. I was going to enable vectors as a follow-up to this patch.

[eli.friedman]

lib/Analysis/InstructionSimplify.cpp

3411

I was thinking of a case where instead of trunc+slt, you have trunc+and+eq. Looking through a truncate isn't really specific to slt.

[spatel]

lib/Analysis/InstructionSimplify.cpp

3414

But now it can't wait:
http://lists.llvm.org/pipermail/llvm-dev/2016-July/102583.html

AFAICT, the bug was present before the refactoring in rL275911, but nobody noticed until now.

[spatel]

Patch updated:

1. D22602 forced us to deal with the vector bug, so I've added some vector test cases.
2. FIXME comments for refactoring were also added because D22602 exposed the code duplication sin.

I'd prefer to wait to add more patterns until I get some of the refactoring done. I don't see any quick fix here:
To refactor these cmp instruction analyzers properly, we should make the alternate code in decomposeBitTestICmp() vector-friendly and that means breaking artificial limits (dyn_cast<ConstantInt> vs. m_APInt()) on a very large number of transforms.

[eli.friedman]

LGTM for now, I guess.

lib/Analysis/InstructionSimplify.cpp

if (Y->isPowerOf2()) {
     if (TrueVal == X && match(FalseVal, m_Or(m_Specific(X), m_APInt(C))) &&
         *Y == *C)
       return TrueWhenUnset ? TrueVal : FalseVal;
   }
   
   return nullptr;
 }
 
+/// An alternative way to test if a bit is set or not uses sgt/slt instead of
+/// eq/ne.
+static Value *simplifySelectWithFakeICmpEq(Value *CmpLHS, Value *TrueVal,
+                                           Value *FalseVal,
+                                           bool TrueWhenUnset) {
+  unsigned BitWidth = TrueVal->getType()->getScalarSizeInBits();
+  APInt MinSignedValue;
+  Value *X;
+  if (match(CmpLHS, m_Trunc(m_Value(X))) && (X == TrueVal || X == FalseVal)) {
+    // icmp slt (trunc X), 0  <--> icmp ne (and X, C), 0
+    // icmp sgt (trunc X), -1 <--> icmp eq (and X, C), 0
+    unsigned DestSize = CmpLHS->getType()->getScalarSizeInBits();
+    MinSignedValue = APInt::getSignedMinValue(DestSize).zext(BitWidth);
+  } else {
+    // icmp slt X, 0  <--> icmp ne (and X, C), 0
+    // icmp sgt X, -1 <--> icmp eq (and X, C), 0
+    X = CmpLHS;
+    MinSignedValue = APInt::getSignedMinValue(BitWidth);
+  }
+
+  if (Value *V = simplifySelectBitTest(TrueVal, FalseVal, X, &MinSignedValue,
+                                       TrueWhenUnset))
+    return V;
+
+  return nullptr;
+}
+
 /// Try to simplify a select instruction when its condition operand is an
 /// integer comparison.
 static Value *simplifySelectWithICmpCond(Value *CondVal, Value *TrueVal,
                                          Value *FalseVal, const Query &Q,
                                          unsigned MaxRecurse) {
   ICmpInst::Predicate Pred;
   Value *CmpLHS, *CmpRHS;
   if (!match(CondVal, m_ICmp(Pred, m_Value(CmpLHS), m_Value(CmpRHS))))
     return nullptr;
 
   // FIXME: This code is nearly duplicated in InstCombine. Using/refactoring
   // decomposeBitTestICmp() might help.
-  unsigned BitWidth =
-      Q.DL.getTypeSizeInBits(TrueVal->getType()->getScalarType());
-  APInt MinSignedValue = APInt::getSignBit(BitWidth);
   if (ICmpInst::isEquality(Pred) && match(CmpRHS, m_Zero())) {
     Value *X;
     const APInt *Y;
     if (match(CmpLHS, m_And(m_Value(X), m_APInt(Y))))
       if (Value *V = simplifySelectBitTest(TrueVal, FalseVal, X, Y,
                                            Pred == ICmpInst::ICMP_EQ))
         return V;
   } else if (Pred == ICmpInst::ICMP_SLT && match(CmpRHS, m_Zero())) {
-    if (Value *V = simplifySelectBitTest(TrueVal, FalseVal, CmpLHS,
-                                         &MinSignedValue, false))
+    // Comparing signed-less-than 0 checks if the sign bit is set.
+    if (Value *V = simplifySelectWithFakeICmpEq(CmpLHS, TrueVal, FalseVal,
+                                                false))
       return V;
   } else if (Pred == ICmpInst::ICMP_SGT && match(CmpRHS, m_AllOnes())) {
-    if (Value *V = simplifySelectBitTest(TrueVal, FalseVal, CmpLHS,
-                                         &MinSignedValue, true))
+    // Comparing signed-greater-than -1 checks if the sign bit is not set.
+    if (Value *V = simplifySelectWithFakeICmpEq(CmpLHS, TrueVal, FalseVal,
+                                                true))
       return V;
   }
 
   if (CondVal->hasOneUse()) {
     const APInt *C;
     if (match(CmpRHS, m_APInt(C))) {
       // X < MIN ? T : F  -->  F
       if (Pred == ICmpInst::ICMP_SLT && C->isMinSignedValue())

test/Transforms/InstSimplify/select.ll

 }
 
 ; PR28466: https://llvm.org/bugs/show_bug.cgi?id=28466
 ; Each of the previous 8 patterns has a variant that replaces the
 ; 'and' with a 'trunc' and the icmp eq/ne with icmp slt/sgt.
 
 define i32 @select_icmp_trunc_8_ne_0_or_128(i32 %x) {
 ; CHECK-LABEL: @select_icmp_trunc_8_ne_0_or_128(
-; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 %x to i8
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i8 [[TRUNC]], -1
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 %x, 128
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i32 [[OR]], i32 %x
-; CHECK-NEXT:    ret i32 [[SEL]]
+; CHECK-NEXT:    ret i32 [[OR]]
 ;
   %trunc = trunc i32 %x to i8
   %cmp = icmp sgt i8 %trunc, -1
   %or = or i32 %x, 128
   %sel = select i1 %cmp, i32 %or, i32 %x
   ret i32 %sel
 }
 
 define i32 @select_icmp_trunc_8_ne_0_or_128_alt(i32 %x) {
 ; CHECK-LABEL: @select_icmp_trunc_8_ne_0_or_128_alt(
-; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 %x to i8
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[TRUNC]], 0
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 %x, 128
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i32 %x, i32 [[OR]]
-; CHECK-NEXT:    ret i32 [[SEL]]
+; CHECK-NEXT:    ret i32 [[OR]]
 ;
   %trunc = trunc i32 %x to i8
   %cmp = icmp slt i8 %trunc, 0
   %or = or i32 %x, 128
   %sel = select i1 %cmp, i32 %x, i32 %or
   ret i32 %sel
 }
 
 define i32 @select_icmp_trunc_8_eq_0_or_128(i32 %x) {
 ; CHECK-LABEL: @select_icmp_trunc_8_eq_0_or_128(
-; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 %x to i8
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[TRUNC]], 0
-; CHECK-NEXT:    [[OR:%.*]] = or i32 %x, 128
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i32 [[OR]], i32 %x
-; CHECK-NEXT:    ret i32 [[SEL]]
+; CHECK-NEXT:    ret i32 %x
 ;
   %trunc = trunc i32 %x to i8
   %cmp = icmp slt i8 %trunc, 0
   %or = or i32 %x, 128
   %sel = select i1 %cmp, i32 %or, i32 %x
   ret i32 %sel
 }
 
 define i32 @select_icmp_trunc_8_eq_0_or_128_alt(i32 %x) {
 ; CHECK-LABEL: @select_icmp_trunc_8_eq_0_or_128_alt(
-; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 %x to i8
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i8 [[TRUNC]], -1
-; CHECK-NEXT:    [[OR:%.*]] = or i32 %x, 128
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i32 %x, i32 [[OR]]
-; CHECK-NEXT:    ret i32 [[SEL]]
+; CHECK-NEXT:    ret i32 %x
 ;
   %trunc = trunc i32 %x to i8
   %cmp = icmp sgt i8 %trunc, -1
   %or = or i32 %x, 128
   %sel = select i1 %cmp, i32 %x, i32 %or
   ret i32 %sel
 }
 
 define i32 @select_icmp_trunc_8_eq_0_and_not_8(i32 %x) {
 ; CHECK-LABEL: @select_icmp_trunc_8_eq_0_and_not_8(
-; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 %x to i4
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i4 [[TRUNC]], -1
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 %x, -9
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i32 %x, i32 [[AND]]
-; CHECK-NEXT:    ret i32 [[SEL]]
+; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %trunc = trunc i32 %x to i4
   %cmp = icmp sgt i4 %trunc, -1
   %and = and i32 %x, -9
   %sel = select i1 %cmp, i32 %x, i32 %and
   ret i32 %sel
 }
 
 define i32 @select_icmp_trunc_8_eq_0_and_not_8_alt(i32 %x) {
 ; CHECK-LABEL: @select_icmp_trunc_8_eq_0_and_not_8_alt(
-; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 %x to i4
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i4 [[TRUNC]], 0
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 %x, -9
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i32 [[AND]], i32 %x
-; CHECK-NEXT:    ret i32 [[SEL]]
+; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %trunc = trunc i32 %x to i4
   %cmp = icmp slt i4 %trunc, 0
   %and = and i32 %x, -9
   %sel = select i1 %cmp, i32 %and, i32 %x
   ret i32 %sel
 }
 
 define i32 @select_icmp_trunc_8_ne_0_and_not_8(i32 %x) {
 ; CHECK-LABEL: @select_icmp_trunc_8_ne_0_and_not_8(
-; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 %x to i4
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i4 [[TRUNC]], 0
-; CHECK-NEXT:    [[AND:%.*]] = and i32 %x, -9
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i32 %x, i32 [[AND]]
-; CHECK-NEXT:    ret i32 [[SEL]]
+; CHECK-NEXT:    ret i32 %x
 ;
   %trunc = trunc i32 %x to i4
   %cmp = icmp slt i4 %trunc, 0
   %and = and i32 %x, -9
   %sel = select i1 %cmp, i32 %x, i32 %and
   ret i32 %sel
 }
 
 define i32 @select_icmp_trunc_8_ne_0_and_not_8_alt(i32 %x) {
 ; CHECK-LABEL: @select_icmp_trunc_8_ne_0_and_not_8_alt(
-; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 %x to i4
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i4 [[TRUNC]], -1
-; CHECK-NEXT:    [[AND:%.*]] = and i32 %x, -9
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i32 [[AND]], i32 %x
-; CHECK-NEXT:    ret i32 [[SEL]]
+; CHECK-NEXT:    ret i32 %x
 ;
   %trunc = trunc i32 %x to i4
   %cmp = icmp sgt i4 %trunc, -1
   %and = and i32 %x, -9
   %sel = select i1 %cmp, i32 %and, i32 %x
   ret i32 %sel
 }
 
 ; Make sure that at least a few of the same patterns are repeated with vector types.
 
 define <2 x i32> @select_icmp_and_8_ne_0_and_not_8_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @select_icmp_and_8_ne_0_and_not_8_vec(
 ; CHECK-NEXT:    ret <2 x i32> %x
 ;
   %and = and <2 x i32> %x, <i32 8, i32 8>
   %cmp = icmp ne <2 x i32> %and, zeroinitializer
   %and1 = and <2 x i32> %x, <i32 -9, i32 -9>
   %sel = select <2 x i1> %cmp, <2 x i32> %x, <2 x i32> %and1
   ret <2 x i32> %sel
 }
 
 define <2 x i32> @select_icmp_trunc_8_ne_0_and_not_8_alt_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @select_icmp_trunc_8_ne_0_and_not_8_alt_vec(
-; CHECK-NEXT:    [[TRUNC:%.*]] = trunc <2 x i32> %x to <2 x i4>
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt <2 x i4> [[TRUNC]], <i4 -1, i4 -1>
-; CHECK-NEXT:    [[AND:%.*]] = and <2 x i32> %x, <i32 -9, i32 -9>
-; CHECK-NEXT:    [[SEL:%.*]] = select <2 x i1> [[CMP]], <2 x i32> [[AND]], <2 x i32> %x
-; CHECK-NEXT:    ret <2 x i32> [[SEL]]
+; CHECK-NEXT:    ret <2 x i32> %x
 ;
   %trunc = trunc <2 x i32> %x to <2 x i4>
   %cmp = icmp sgt <2 x i4> %trunc, <i4 -1, i4 -1>
   %and = and <2 x i32> %x, <i32 -9, i32 -9>
   %sel = select <2 x i1> %cmp, <2 x i32> %and, <2 x i32> %x
   ret <2 x i32> %sel
 }