[InstSimplify] use knownbits to fold more udiv/urem

[spatel]

Summary

We could use knownbits on both operands for even more folds (and there are already tests in place for that), but this is enough to recover the example from:
https://github.com/llvm/llvm-project/issues/51934
(the tests are derived from the code in that example)

I am assuming no noticeable compile-time impact from this because udiv/urem are rare opcodes, but I could check that if there is concern.

[foad]

It seems like you're using knownbits information to derive range information. It would be good to do this more universally, and in both directions.

llvm/lib/Analysis/InstructionSimplify.cpp

1088–1089

Can't you just test if (KnownX.getMaxValue().ult(*C))?

[spatel]

In D116616#3221740, @foad wrote:

It seems like you're using knownbits information to derive range information. It would be good to do this more universally, and in both directions.

Yes - we do have a combination analysis called "computeConstantRangeIncludingKnownBits", so that should be more powerful.
But that is currently a static helper function in ValueTracking, so it would have to be made visible, and it would be good to have more tests to show where the extra logic gives us a better result. Ok to make that a TODO item?

llvm/lib/Analysis/InstructionSimplify.cpp

1088–1089

Yes, that's shorter and faster. Thanks!

[spatel]

Patch updated:
Use KnownBits::getMaxValue() - no functional diff intended from previous revision, but more efficient.

[foad]

In D116616#3222181, @spatel wrote:

In D116616#3221740, @foad wrote:

It seems like you're using knownbits information to derive range information. It would be good to do this more universally, and in both directions.

Yes - we do have a combination analysis called "computeConstantRangeIncludingKnownBits", so that should be more powerful.
But that is currently a static helper function in ValueTracking, so it would have to be made visible, and it would be good to have more tests to show where the extra logic gives us a better result. Ok to make that a TODO item?

Sure. I don't object to the current patch. Just wanted to understand if there's a way of doing this more universally in future.

[spatel]

Patch updated (NFCI with previous revision again):

1. Added TODO comment about range analysis.
2. Removed check for zero divisor (it is always handled earlier, so could be an assert).

[spatel]

Patch updated:
I removed the MaxRecurse usage from the call to computeKnownBits. Similar calls around this file don't do that (ie, we're ok using the full recursive power of knownbits independent of whether we are recursing within InstSimplify calls themselves).

This allows the call to fit neatly within 80-cols, so the patch is just a single 'if' check now. :)

[lebedev.ri]

LG

llvm/lib/Analysis/InstructionSimplify.cpp

if (match(Y, m_APInt(C))) {
       if (isICmpTrue(CmpInst::ICMP_SGT, X, NegDivisorC, Q, MaxRecurse) &&
           isICmpTrue(CmpInst::ICMP_SLT, X, PosDivisorC, Q, MaxRecurse))
         return true;
     }
     return false;
   }
 
   // IsSigned == false.
+
+  // Is the unsigned dividend known to be less than a constant divisor?
+  // TODO: Convert this (and above) to range analysis
+  //      ("computeConstantRangeIncludingKnownBits")?
+  const APInt *C;
+  if (match(Y, m_APInt(C)) &&
+      computeKnownBits(X, Q.DL, 0, Q.AC, Q.CxtI, Q.DT).getMaxValue().ult(*C))
+    return true;
+
+  // Try again for any divisor:
   // Is the dividend unsigned less than the divisor?
   return isICmpTrue(ICmpInst::ICMP_ULT, X, Y, Q, MaxRecurse);
 }
 
 /// These are simplifications common to SDiv and UDiv.
 static Value *simplifyDiv(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
                           const SimplifyQuery &Q, unsigned MaxRecurse) {
   if (Constant *C = foldOrCommuteConstant(Opcode, Op0, Op1, Q))

llvm/test/Transforms/InstSimplify/div.ll

 ;
   %or = or i32 %x, 251
   %div = udiv i32 251, %or
   ret i32 %div
 }
 
 define i8 @udiv_dividend_known_smaller_than_constant_divisor2(i1 %b) {
 ; CHECK-LABEL: @udiv_dividend_known_smaller_than_constant_divisor2(
-; CHECK-NEXT:    [[T0:%.*]] = zext i1 [[B:%.*]] to i8
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[T0]], 12
-; CHECK-NEXT:    [[R:%.*]] = udiv i8 [[XOR]], 14
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 0
 ;
   %t0 = zext i1 %b to i8
   %xor = xor i8 %t0, 12
   %r = udiv i8 %xor, 14
   ret i8 %r
 }
 
+; negative test - dividend can equal 13
+
 define i8 @not_udiv_dividend_known_smaller_than_constant_divisor2(i1 %b) {
 ; CHECK-LABEL: @not_udiv_dividend_known_smaller_than_constant_divisor2(
 ; CHECK-NEXT:    [[T0:%.*]] = zext i1 [[B:%.*]] to i8
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[T0]], 12
 ; CHECK-NEXT:    [[R:%.*]] = udiv i8 [[XOR]], 13
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %t0 = zext i1 %b to i8

llvm/test/Transforms/InstSimplify/rem.ll

;
   %r = urem i32 %and, 251
   ret i32 %r
 }
 
 define i8 @urem_dividend_known_smaller_than_constant_divisor2(i1 %b) {
 ; CHECK-LABEL: @urem_dividend_known_smaller_than_constant_divisor2(
 ; CHECK-NEXT:    [[T0:%.*]] = zext i1 [[B:%.*]] to i8
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[T0]], 12
-; CHECK-NEXT:    [[R:%.*]] = urem i8 [[XOR]], 14
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 [[XOR]]
 ;
   %t0 = zext i1 %b to i8
   %xor = xor i8 %t0, 12
   %r = urem i8 %xor, 14
   ret i8 %r
 }
 
+; negative test - dividend can equal 13
+
 define i8 @not_urem_dividend_known_smaller_than_constant_divisor2(i1 %b) {
 ; CHECK-LABEL: @not_urem_dividend_known_smaller_than_constant_divisor2(
 ; CHECK-NEXT:    [[T0:%.*]] = zext i1 [[B:%.*]] to i8
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[T0]], 12
 ; CHECK-NEXT:    [[R:%.*]] = urem i8 [[XOR]], 13
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %t0 = zext i1 %b to i8