[InstCombine] Demand bits of UMAX

[dmgreen]

Summary

This is part of of D52508. It uses the demand bits of umax(A, C) to prove we use just A, so long as:
"The lowest non-zero bit of DemandMask is higher than the highest non-zero bit of C"

https://rise4fun.com/Alive/q4Z

Conceptually, this works because:
if A > C, we pick A. No big deal.
if A < C then all the demanded bits of A == demanded bits of C, so we can pick either and get the same result. So we pick A.

[lebedev.ri]

Unfortunately I don't have a great way to prove this with Alive, as I don't believe it can do clz/ctz's in preconditions.

WDYM?
Seems to work fine https://rise4fun.com/Alive/BKg
https://github.com/nunoplopes/alive/blob/eda494ab9ad668fe1bce02978bd018b917d88230/constants.py#L257-L258

[dmgreen]

Ah, I must have been looking at the wrong bit of code. Thanks!

In that case, https://rise4fun.com/Alive/q4Z

[lebedev.ri]

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

326–327

I wonder if it's any cleaner to write this as

C->countLeadingZeros() + DemandedMask.countTrailingZeros() => C->getBitWidth()

https://rise4fun.com/Alive/o49
I.e. that leading zeros (in high bits), and trailing zeros (in low bits) overlap/touch.

[craig.topper]

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

326–327

How about DemandedMask.countTrailingZeros() >= C->getActiveBits()

[dmgreen]

Updated to use activeBits. Thanks for the suggestions.

[lebedev.ri]

Looks good, but maybe wait a bit for someone else to confirm.

[spatel]

LGTM

[spatel]

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

323

Add period at end of sentence.

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

if (Instruction *LHSInst = dyn_cast<Instruction>(I->getOperand(0)))
       }
 
     // Output known-0 bits are known if clear or set in both the LHS & RHS.
     Known.Zero = std::move(IKnownZero);
     // Output known-1 are known to be set if set in only one of the LHS, RHS.
     Known.One  = std::move(IKnownOne);
     break;
   }
-  case Instruction::Select:
-    // If this is a select as part of a min/max pattern, don't simplify any
-    // further in case we break the structure.
+  case Instruction::Select: {
     Value *LHS, *RHS;
-    if (matchSelectPattern(I, LHS, RHS).Flavor != SPF_UNKNOWN)
+    SelectPatternFlavor SPF = matchSelectPattern(I, LHS, RHS).Flavor;
+    if (SPF == SPF_UMAX) {
+      // UMax(A, C) == A if ...
+      // The lowest non-zero bit of DemandMask is higher than the highest
+      // non-zero bit of C
+      const APInt *C;
+      if (match(RHS, m_APInt(C)) &&
+          DemandedMask.countTrailingZeros() + 1 >
+              C->getBitWidth() - C->countLeadingZeros())
+        return LHS;
+    }
+
+    // If this is a select as part of any other min/max pattern, don't simplify
+    // any further in case we break the structure.
+    if (SPF != SPF_UNKNOWN)
       return nullptr;
 
     if (SimplifyDemandedBits(I, 2, DemandedMask, RHSKnown, Depth + 1) ||
         SimplifyDemandedBits(I, 1, DemandedMask, LHSKnown, Depth + 1))
       return I;
     assert(!RHSKnown.hasConflict() && "Bits known to be one AND zero?");
     assert(!LHSKnown.hasConflict() && "Bits known to be one AND zero?");
 
     // If the operands are constants, see if we can simplify them.
     if (ShrinkDemandedConstant(I, 1, DemandedMask) ||
         ShrinkDemandedConstant(I, 2, DemandedMask))
       return I;
 
     // Only known if known in both the LHS and RHS.
     Known.One = RHSKnown.One & LHSKnown.One;
     Known.Zero = RHSKnown.Zero & LHSKnown.Zero;
     break;
+  }
   case Instruction::ZExt:
   case Instruction::Trunc: {
     unsigned SrcBitWidth = I->getOperand(0)->getType()->getScalarSizeInBits();
 
     APInt InputDemandedMask = DemandedMask.zextOrTrunc(SrcBitWidth);
     KnownBits InputKnown(SrcBitWidth);
     if (SimplifyDemandedBits(I, 0, InputDemandedMask, InputKnown, Depth + 1))
       return I;

test/Transforms/InstCombine/minmax-demandbits.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -instcombine < %s | FileCheck %s
 
 
 define i32 @and_umax_less(i32 %A) {
 ; CHECK-LABEL: @and_umax_less(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i32 [[A:%.*]], 31
-; CHECK-NEXT:    [[L1:%.*]] = select i1 [[TMP1]], i32 [[A]], i32 31
-; CHECK-NEXT:    [[X:%.*]] = and i32 [[L1]], -32
+; CHECK-NEXT:    [[X:%.*]] = and i32 [[A:%.*]], -32
 ; CHECK-NEXT:    ret i32 [[X]]
 ;
   %l0 = icmp ugt i32 31, %A
   %l1 = select i1 %l0, i32 31, i32 %A
   %x = and i32 %l1, -32
   ret i32 %x
 }
 
 define i32 @and_umax_muchless(i32 %A) {
 ; CHECK-LABEL: @and_umax_muchless(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i32 [[A:%.*]], 12
-; CHECK-NEXT:    [[L1:%.*]] = select i1 [[TMP1]], i32 [[A]], i32 12
-; CHECK-NEXT:    [[X:%.*]] = and i32 [[L1]], -32
+; CHECK-NEXT:    [[X:%.*]] = and i32 [[A:%.*]], -32
 ; CHECK-NEXT:    ret i32 [[X]]
 ;
   %l0 = icmp ugt i32 12, %A
   %l1 = select i1 %l0, i32 12, i32 %A
   %x = and i32 %l1, -32
   ret i32 %x
 }
 
 define i32 @and_umax_more(i32 %A) {
 ; CHECK-LABEL: @and_umax_more(
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i32 [[A:%.*]], 32
 ; CHECK-NEXT:    [[L1:%.*]] = select i1 [[TMP1]], i32 [[A]], i32 32
 ; CHECK-NEXT:    [[X:%.*]] = and i32 [[L1]], -32
 ; CHECK-NEXT:    ret i32 [[X]]
 ;
   %l0 = icmp ugt i32 32, %A
   %l1 = select i1 %l0, i32 32, i32 %A
   %x = and i32 %l1, -32
   ret i32 %x
 }
 
 define i32 @shr_umax(i32 %A) {
 ; CHECK-LABEL: @shr_umax(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i32 [[A:%.*]], 15
-; CHECK-NEXT:    [[L1:%.*]] = select i1 [[TMP1]], i32 [[A]], i32 15
-; CHECK-NEXT:    [[X:%.*]] = lshr i32 [[L1]], 4
+; CHECK-NEXT:    [[X:%.*]] = lshr i32 [[A:%.*]], 4
 ; CHECK-NEXT:    ret i32 [[X]]
 ;
   %l0 = icmp ugt i32 15, %A
   %l1 = select i1 %l0, i32 15, i32 %A
   %x = lshr i32 %l1, 4
   ret i32 %x
 }
 
;
   %l2 = icmp ugt i8 %A, 0
   %l1 = select i1 %l2, i8 %A, i8 0
   %x = and i8 %l1, 10
   ret i8 %x
 }
 
 define i8 @t_1_10(i8 %A) {
 ; CHECK-LABEL: @t_1_10(
-; CHECK-NEXT:    [[L2:%.*]] = icmp ugt i8 [[A:%.*]], 1
-; CHECK-NEXT:    [[L1:%.*]] = select i1 [[L2]], i8 [[A]], i8 1
-; CHECK-NEXT:    [[X:%.*]] = and i8 [[L1]], 10
+; CHECK-NEXT:    [[X:%.*]] = and i8 [[A:%.*]], 10
 ; CHECK-NEXT:    ret i8 [[X]]
 ;
   %l2 = icmp ugt i8 %A, 1
   %l1 = select i1 %l2, i8 %A, i8 1
   %x = and i8 %l1, 10
   ret i8 %x
 }
 
 define i8 @t_2_4(i8 %A) {
 ; CHECK-LABEL: @t_2_4(
-; CHECK-NEXT:    [[L2:%.*]] = icmp ugt i8 [[A:%.*]], 2
-; CHECK-NEXT:    [[L1:%.*]] = select i1 [[L2]], i8 [[A]], i8 2
-; CHECK-NEXT:    [[X:%.*]] = and i8 [[L1]], 4
+; CHECK-NEXT:    [[X:%.*]] = and i8 [[A:%.*]], 4
 ; CHECK-NEXT:    ret i8 [[X]]
 ;
   %l2 = icmp ugt i8 %A, 2
   %l1 = select i1 %l2, i8 %A, i8 2
   %x = and i8 %l1, 4
   ret i8 %x
 }
 
 define i8 @t_2_192(i8 %A) {
 ; CHECK-LABEL: @t_2_192(
-; CHECK-NEXT:    [[L2:%.*]] = icmp ugt i8 [[A:%.*]], 2
-; CHECK-NEXT:    [[L1:%.*]] = select i1 [[L2]], i8 [[A]], i8 2
-; CHECK-NEXT:    [[X:%.*]] = and i8 [[L1]], -64
+; CHECK-NEXT:    [[X:%.*]] = and i8 [[A:%.*]], -64
 ; CHECK-NEXT:    ret i8 [[X]]
 ;
   %l2 = icmp ugt i8 %A, 2
   %l1 = select i1 %l2, i8 %A, i8 2
   %x = and i8 %l1, 192
   ret i8 %x
 }