[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

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

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

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

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

335

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.

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;
       if (match(RHS, m_APInt(C)) &&
           DemandedMask.countTrailingZeros() >= 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 about from some maths on the above umax example
+      const APInt *C;
+      if (match(RHS, m_APInt(C)) &&
+          DemandedMask.countTrailingZeros() >=
+              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) ||

test/Transforms/InstCombine/minmax-demandbits.ll

 ; CHECK-LABEL: @or_umin(
 ; CHECK-NEXT:    ret i32 31
 ;
   %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 @or_min_7_6(i8 %A) {
 ; CHECK-LABEL: @or_min_7_6(
-; CHECK-NEXT:    [[L2:%.*]] = icmp ult i8 [[A:%.*]], -6
-; CHECK-NEXT:    [[MIN:%.*]] = select i1 [[L2]], i8 [[A]], i8 -6
-; CHECK-NEXT:    [[R:%.*]] = or i8 [[MIN]], 7
+; CHECK-NEXT:    [[R:%.*]] = or i8 [[A:%.*]], 7
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %l2 = icmp ult i8 %A, -6
   %min = select i1 %l2, i8 %A, i8 -6
   %r = or i8 %min, 7
   ret i8 %r
 }
 
 define i8 @or_min_7_5(i8 %A) {
 ; CHECK-LABEL: @or_min_7_5(
-; CHECK-NEXT:    [[L2:%.*]] = icmp ult i8 [[A:%.*]], -5
-; CHECK-NEXT:    [[MIN:%.*]] = select i1 [[L2]], i8 [[A]], i8 -5
-; CHECK-NEXT:    [[R:%.*]] = or i8 [[MIN]], 7
+; CHECK-NEXT:    [[R:%.*]] = or i8 [[A:%.*]], 7
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %l2 = icmp ult i8 %A, -5
   %min = select i1 %l2, i8 %A, i8 -5
   %r = or i8 %min, 7
   ret i8 %r
 }