[ValueTracking] Pass `exact` flag to `KnownBits::udiv` in `computeKnownBits`

[goldstein.w.n]

Summary

This information was previously missing but we can use it for
determining the low-bits.

[RKSimon]

LGTM

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

llvm/lib/Analysis/ValueTracking.cpp

case Instruction::Mul: {
     bool NSW = Q.IIQ.hasNoSignedWrap(cast<OverflowingBinaryOperator>(I));
     computeKnownBitsMul(I->getOperand(0), I->getOperand(1), NSW, DemandedElts,
                         Known, Known2, Depth, Q);
     break;
   }
   case Instruction::UDiv: {
     computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);
     computeKnownBits(I->getOperand(1), Known2, Depth + 1, Q);
-    Known = KnownBits::udiv(Known, Known2);
+    Known =
+        KnownBits::udiv(Known, Known2, Q.IIQ.isExact(cast<BinaryOperator>(I)));
     break;
   }
   case Instruction::Select: {
     const Value *LHS = nullptr, *RHS = nullptr;
     SelectPatternFlavor SPF = matchSelectPattern(I, LHS, RHS).Flavor;
     if (SelectPatternResult::isMinOrMax(SPF)) {
       computeKnownBits(RHS, Known, Depth + 1, Q);
       computeKnownBits(LHS, Known2, Depth + 1, Q);

llvm/test/Analysis/ValueTracking/knownbits-div.ll

;
   %div = udiv i8 %num, %denum
   %and = and i8 %div, 8
   %r = icmp eq i8 %and, 8
   ret i1 %r
 }
 
 define i1 @udiv_exact_odd_odd(i8 %x, i8 %y) {
 ; CHECK-LABEL: @udiv_exact_odd_odd(
-; CHECK-NEXT:    [[NUM:%.*]] = or i8 [[X:%.*]], 1
-; CHECK-NEXT:    [[DENUM:%.*]] = or i8 [[Y:%.*]], 1
-; CHECK-NEXT:    [[DIV:%.*]] = udiv exact i8 [[NUM]], [[DENUM]]
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[DIV]], 1
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[AND]], 0
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %num = or i8 %x, 1
   %denum = or i8 %y, 1
   %div = udiv exact i8 %num, %denum
   %and = and i8 %div, 1
   %r = icmp eq i8 %and, 0
   ret i1 %r
 }
 
 define i1 @udiv_exact_even_odd(i8 %x, i8 %y) {
 ; CHECK-LABEL: @udiv_exact_even_odd(
-; CHECK-NEXT:    [[NUM:%.*]] = and i8 [[X:%.*]], -2
-; CHECK-NEXT:    [[DENUM:%.*]] = or i8 [[Y:%.*]], 1
-; CHECK-NEXT:    [[DIV:%.*]] = udiv exact i8 [[NUM]], [[DENUM]]
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[DIV]], 1
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[AND]], 1
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %num = and i8 %x, -2
   %denum = or i8 %y, 1
   %div = udiv exact i8 %num, %denum
   %and = and i8 %div, 1
   %r = icmp eq i8 %and, 1
   ret i1 %r
 }