[InstCombine] Demand bits of UMin

[dmgreen]

Summary

This is the umin alternative to the umax code from D53033, If I'm getting the maths correct.

As Sanjay suggested, we can use De Morgan's law on the umax case to bring us to the same thing on umin, but using countLeadingOnes, not countLeadingZeros.

https://rise4fun.com/Alive/O9i

[lebedev.ri]

Same comments as with D53033 (alive + inverse of https://reviews.llvm.org/D53033#inline-467182)

[dmgreen]

Luckily, it appears that Alive can do countLeadingOnes too (although I don't see it anywhere in the sources I have).
https://rise4fun.com/Alive/O9i

[lebedev.ri]

In D53036#1260222, @dmgreen wrote:

Luckily, it appears that Alive can do countLeadingOnes too (although I don't see it anywhere in the sources I have).
https://rise4fun.com/Alive/O9i

Huh https://github.com/nunoplopes/alive/search?utf8=%E2%9C%93&q=countLeadingOnes&type=
CC @nlopes

[lebedev.ri]

Same as with D53033, looks ok, but maybe wait a bit for someone else.

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

335–336 ↗

(On Diff #168973)

Nit, probably ignore:
Is

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

worse?
I guess you could write it as

DemandedMask.countTrailingZeros() >= (~C)->getActiveBits()

but that will be less readable, and may be worse if the compiler won't see through the bitwise-inversion.

test/Transforms/InstCombine/minmax-demandbits.ll

190 ↗

(On Diff #168973)

There are negative tests here for this fold?

[dmgreen]

Just added a new test, and changed some of the others around a little.

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

335–336 ↗

(On Diff #168973)

Yeah, I was trying to make it look like the above umax example. With DemandedMask.countTrailingZeros() >= <something>. I have no strong opinion, let me know if I should change it.

[spatel]

In D53036#1260230, @lebedev.ri wrote:

In D53036#1260222, @dmgreen wrote:

Luckily, it appears that Alive can do countLeadingOnes too (although I don't see it anywhere in the sources I have).
https://rise4fun.com/Alive/O9i

Huh https://github.com/nunoplopes/alive/search?utf8=%E2%9C%93&q=countLeadingOnes&type=
CC @nlopes

This is the page I look at as reference for alive coding:
https://github.com/nunoplopes/alive/blob/newsema/rise4fun/language

[spatel]

LGTM - see inline for a couple of nits.

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

330–332 ↗

(On Diff #169002)

Period at end of each sentence. Rather than random math, note this as the DeMorgan'd version of the umax logic.

335 ↗

(On Diff #169002)

Might read easier and fit better in 80-cols if we give the CTZ a name and use it here and for umax:
unsigned LowestDemandedBit = DemandedMask.countTrailingZeros();

[dmgreen]

This is the page I look at as reference for alive coding:
https://github.com/nunoplopes/alive/blob/newsema/rise4fun/language

Thanks. Different branch, that makes sense.

llvm/trunk/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

case Instruction::Select: {
     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;
       unsigned CTZ = DemandedMask.countTrailingZeros();
       if (match(RHS, m_APInt(C)) && CTZ >= C->getActiveBits())
         return LHS;
+    } else if (SPF == SPF_UMIN) {
+      // UMin(A, C) == A if ...
+      // The lowest non-zero bit of DemandMask is higher than the highest
+      // non-one bit of C.
+      // This comes from using DeMorgans on the above umax example.
+      const APInt *C;
+      unsigned CTZ = DemandedMask.countTrailingZeros();
+      if (match(RHS, m_APInt(C)) &&
+          CTZ >= C->getBitWidth() - C->countLeadingOnes())
+        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) ||

llvm/trunk/test/Transforms/InstCombine/minmax-demandbits.ll

;
   %l0 = icmp ult i32 15, %A
   %l1 = select i1 %l0, i32 15, i32 %A
   %x = or i32 %l1, 31
   ret i32 %x
 }
 
 define i8 @or_min_31_30(i8 %A) {
 ; CHECK-LABEL: @or_min_31_30(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[A:%.*]], -30
-; CHECK-NEXT:    [[MIN:%.*]] = select i1 [[CMP]], i8 [[A]], i8 -30
-; CHECK-NEXT:    [[R:%.*]] = or i8 [[MIN]], 31
+; CHECK-NEXT:    [[R:%.*]] = or i8 [[A:%.*]], 31
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %cmp = icmp ult i8 %A, -30
   %min = select i1 %cmp, i8 %A, i8 -30
   %r = or i8 %min, 31
   ret i8 %r
 }
 
 define i8 @and_min_7_7(i8 %A) {
 ; CHECK-LABEL: @and_min_7_7(
-; CHECK-NEXT:    [[L2:%.*]] = icmp ult i8 [[A:%.*]], -7
-; CHECK-NEXT:    [[MIN:%.*]] = select i1 [[L2]], i8 [[A]], i8 -7
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[MIN]], -8
+; CHECK-NEXT:    [[R:%.*]] = and i8 [[A:%.*]], -8
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %l2 = icmp ult i8 %A, -7
   %min = select i1 %l2, i8 %A, i8 -7
   %r = and i8 %min, -8
   ret i8 %r
 }
 
 define i8 @and_min_7_8(i8 %A) {
 ; CHECK-LABEL: @and_min_7_8(
-; CHECK-NEXT:    [[L2:%.*]] = icmp ult i8 [[A:%.*]], -8
-; CHECK-NEXT:    [[MIN:%.*]] = select i1 [[L2]], i8 [[A]], i8 -8
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[MIN]], -8
+; CHECK-NEXT:    [[R:%.*]] = and i8 [[A:%.*]], -8
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %l2 = icmp ult i8 %A, -8
   %min = select i1 %l2, i8 %A, i8 -8
   %r = and i8 %min, -8
   ret i8 %r
 }