[ValueTracking] recognize more variants of smin/smax

[spatel]

Summary

Try harder to detect obfuscated min/max patterns: the initial pattern was added with D9352 / rL236202. There was a bug fix for PR27137 at rL264996, but I think we can do better by folding the corresponding smax pattern and commuted variants.

For the PR27137 test case, we could further transform that to a mask with the smeared sign bit (ashr/and/not), but I'm not sure if we want to do that in IR?

[efriedma]

Code changes look fine.

test/Transforms/InstCombine/max-of-nots.ll

143

Is there really no better way to write a testcase for this? I guess there are a limited number of transforms which use min/max formation, but this seems awkward.

[spatel]

test/Transforms/InstCombine/max-of-nots.ll

143

Agree - I thought it was best to add to the existing IR test, and I assumed there wasn't a better instcombine way to expose this.

However, as shown in the related D26096, we can see the difference in vector codegen with the minimal IR patterns. Let me add similar tests here. I still think it's best if we keep these instcombine tests for bonus coverage though, but let me know if you think that's overkill.

Thanks for the prompt review!

lib/Analysis/ValueTracking.cpp

if ((CmpLHS == TrueVal && match(FalseVal, m_Neg(m_Specific(CmpLHS)))) ||
 
       // ABS(X) ==> (X <s 0) ? -X : X and (X <s 1) ? -X : X
       // NABS(X) ==> (X <s 0) ? X : -X and (X <s 1) ? X : -X
       if (Pred == ICmpInst::ICMP_SLT && (*C1 == 0 || *C1 == 1)) {
         return {(CmpLHS == FalseVal) ? SPF_ABS : SPF_NABS, SPNB_NA, false};
       }
     }
 
-    // Y >s C ? ~Y : ~C == ~Y <s ~C ? ~Y : ~C = SMIN(~Y, ~C)
+    // (X >s C) ? ~X : ~C ==> (~X <s ~C) ? ~X : ~C ==> SMIN(~X, ~C)
+    // (X <s C) ? ~X : ~C ==> (~X >s ~C) ? ~X : ~C ==> SMAX(~X, ~C)
     const APInt *C2;
-    if (match(FalseVal, m_APInt(C2))) {
-      if (Pred == ICmpInst::ICMP_SGT &&
-          CmpRHS->getType() == FalseVal->getType() && ~(*C1) == *C2 &&
-          (match(TrueVal, m_Not(m_Specific(CmpLHS))) ||
-           match(CmpLHS, m_Not(m_Specific(TrueVal))))) {
-        LHS = TrueVal;
-        RHS = FalseVal;
-        return {SPF_SMIN, SPNB_NA, false};
-      }
+    if (match(TrueVal, m_Not(m_Specific(CmpLHS))) &&
+        match(FalseVal, m_APInt(C2)) && ~(*C1) == *C2 &&
+        (Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SLT)) {
+      return {Pred == CmpInst::ICMP_SGT ? SPF_SMIN : SPF_SMAX, SPNB_NA, false};
+
+    // (X >s C) ? ~C : ~X ==> (~X <s ~C) ? ~C : ~X ==> SMAX(~C, ~X)
+    // (X <s C) ? ~C : ~X ==> (~X >s ~C) ? ~C : ~X ==> SMIN(~C, ~X)
+    if (match(FalseVal, m_Not(m_Specific(CmpLHS))) &&
+        match(TrueVal, m_APInt(C2)) && ~(*C1) == *C2 &&
+        (Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SLT)) {
+      LHS = TrueVal;
+      RHS = FalseVal;
+      return {Pred == CmpInst::ICMP_SGT ? SPF_SMAX : SPF_SMIN, SPNB_NA, false};
     }
   }
 
   // TODO: (X > 4) ? X : 5   -->  (X >= 5) ? X : 5  -->  MAX(X, 5)
 
   return {SPF_UNKNOWN, SPNB_NA, false};
 }
 

test/Transforms/InstCombine/max-of-nots.ll

;
   %c1 = icmp sgt i32 %s0, -1
   %s1 = select i1 %c1, i32 %s0, i32 -1
   ret i32 %s1
 }
 
 ; max(min(%a, -1), -1) == -1 (swap predicate and select ops)
 define i32 @max_of_min_swap(i32 %a) {
 ; CHECK-LABEL: @max_of_min_swap(
-; CHECK-NEXT:    [[NOT_A:%.*]] = xor i32 %a, -1
-; CHECK-NEXT:    [[C0:%.*]] = icmp slt i32 %a, 0
-; CHECK-NEXT:    [[S0:%.*]] = select i1 [[C0]], i32 -1, i32 [[NOT_A]]
-; CHECK-NEXT:    [[C1:%.*]] = icmp sgt i32 [[S0]], -1
-; CHECK-NEXT:    [[S1:%.*]] = select i1 [[C1]], i32 [[S0]], i32 -1
-; CHECK-NEXT:    ret i32 [[S1]]
+; CHECK-NEXT:    ret i32 -1
 ;
   %not_a = xor i32 %a, -1
   %c0 = icmp slt i32 %a, 0
   %s0 = select i1 %c0, i32 -1, i32 %not_a
   %c1 = icmp sgt i32 %s0, -1
   %s1 = select i1 %c1, i32 %s0, i32 -1
   ret i32 %s1
 }
 
 ; min(max(%a, -1), -1) == -1
 define i32 @min_of_max(i32 %a) {
 ; CHECK-LABEL: @min_of_max(
-; CHECK-NEXT:    [[NOT_A:%.*]] = xor i32 %a, -1
-; CHECK-NEXT:    [[C0:%.*]] = icmp slt i32 %a, 0
-; CHECK-NEXT:    [[S0:%.*]] = select i1 [[C0]], i32 [[NOT_A]], i32 -1
-; CHECK-NEXT:    [[C1:%.*]] = icmp slt i32 [[S0]], -1
-; CHECK-NEXT:    [[S1:%.*]] = select i1 [[C1]], i32 [[S0]], i32 -1
-; CHECK-NEXT:    ret i32 [[S1]]
+; CHECK-NEXT:    ret i32 -1
 ;
   %not_a = xor i32 %a, -1
   %c0 = icmp slt i32 %a, 0
   %s0 = select i1 %c0, i32 %not_a, i32 -1
   %c1 = icmp slt i32 %s0, -1
   %s1 = select i1 %c1, i32 %s0, i32 -1
   ret i32 %s1
 }
 
 ; min(max(%a, -1), -1) == -1 (swap predicate and select ops)
 define i32 @min_of_max_swap(i32 %a) {
 ; CHECK-LABEL: @min_of_max_swap(
-; CHECK-NEXT:    [[NOT_A:%.*]] = xor i32 %a, -1
-; CHECK-NEXT:    [[C0:%.*]] = icmp sgt i32 %a, 0
-; CHECK-NEXT:    [[S0:%.*]] = select i1 [[C0]], i32 -1, i32 [[NOT_A]]
-; CHECK-NEXT:    [[C1:%.*]] = icmp slt i32 [[S0]], -1
-; CHECK-NEXT:    [[S1:%.*]] = select i1 [[C1]], i32 [[S0]], i32 -1
-; CHECK-NEXT:    ret i32 [[S1]]
+; CHECK-NEXT:    ret i32 -1
 ;
   %not_a = xor i32 %a, -1
   %c0 = icmp sgt i32 %a, 0
   %s0 = select i1 %c0, i32 -1, i32 %not_a
   %c1 = icmp slt i32 %s0, -1
   %s1 = select i1 %c1, i32 %s0, i32 -1
   ret i32 %s1
 }

test/Transforms/InstCombine/select.ll

-; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 ; PR1822
 
 target datalayout = "e-p:64:64-p1:16:16-p2:32:32:32-p3:64:64:64"
 
 define i32 @test1(i32 %A, i32 %B) {
         %C = select i1 false, i32 %A, i32 %B

 ; CHECK-NEXT: %[[sel:.*]] = select i1 %[[cmp]], i32 -2147483648, i32 %[[add]]
 ; CHECK-NEXT: ret i32 %[[sel]]
   %cmp = icmp eq i32 %x, 2147483647
   %add = add nsw i32 %x, 1
   %sel = select i1 %cmp, i32 -2147483648, i32 %add
   ret i32 %sel
 }
 
+; max(max(~a, -1), -1) --> max(~a, -1)
+
 define i32 @PR27137(i32 %a) {
 ; CHECK-LABEL: @PR27137(
-; CHECK-NEXT:  %not_a = xor i32 %a, -1
-; CHECK-NEXT:  %c0 = icmp slt i32 %a, 0
-; CHECK-NEXT:  %s0 = select i1 %c0, i32 %not_a, i32 -1
-; CHECK-NEXT:  %c1 = icmp sgt i32 %s0, -1
-; CHECK-NEXT:  %s1 = select i1 %c1, i32 %s0, i32 -1
-; CHECK-NEXT:  ret i32 %s1
+; CHECK-NEXT:    [[NOT_A:%.*]] = xor i32 %a, -1
+; CHECK-NEXT:    [[C0:%.*]] = icmp slt i32 %a, 0
+; CHECK-NEXT:    [[S0:%.*]] = select i1 [[C0]], i32 [[NOT_A]], i32 -1
+; CHECK-NEXT:    ret i32 [[S0]]
+;
 
   %not_a = xor i32 %a, -1
   %c0 = icmp slt i32 %a, 0
   %s0 = select i1 %c0, i32 %not_a, i32 -1
   %c1 = icmp sgt i32 %s0, -1
   %s1 = select i1 %c1, i32 %s0, i32 -1
   ret i32 %s1
 }