diff --git a/llvm/include/llvm/Support/KnownBits.h b/llvm/include/llvm/Support/KnownBits.h
--- a/llvm/include/llvm/Support/KnownBits.h
+++ b/llvm/include/llvm/Support/KnownBits.h
@@ -326,7 +326,8 @@
                         bool Exact = false);
 
   /// Compute known bits for udiv(LHS, RHS).
-  static KnownBits udiv(const KnownBits &LHS, const KnownBits &RHS);
+  static KnownBits udiv(const KnownBits &LHS, const KnownBits &RHS,
+                        bool Exact = false);
 
   /// Compute known bits for urem(LHS, RHS).
   static KnownBits urem(const KnownBits &LHS, const KnownBits &RHS);
diff --git a/llvm/lib/Support/KnownBits.cpp b/llvm/lib/Support/KnownBits.cpp
--- a/llvm/lib/Support/KnownBits.cpp
+++ b/llvm/lib/Support/KnownBits.cpp
@@ -532,7 +532,7 @@
                           bool Exact) {
   // Equivilent of `udiv`. We must have caught this before it was folded.
   if (LHS.isNonNegative() && RHS.isNonNegative())
-    return udiv(LHS, RHS);
+    return udiv(LHS, RHS, Exact);
 
   unsigned BitWidth = LHS.getBitWidth();
   assert(!LHS.hasConflict() && !RHS.hasConflict());
@@ -591,7 +591,8 @@
   return Known;
 }
 
-KnownBits KnownBits::udiv(const KnownBits &LHS, const KnownBits &RHS) {
+KnownBits KnownBits::udiv(const KnownBits &LHS, const KnownBits &RHS,
+                          bool Exact) {
   unsigned BitWidth = LHS.getBitWidth();
   assert(!LHS.hasConflict() && !RHS.hasConflict());
   KnownBits Known(BitWidth);
@@ -599,13 +600,24 @@
   // For the purposes of computing leading zeros we can conservatively
   // treat a udiv as a logical right shift by the power of 2 known to
   // be less than the denominator.
-  unsigned LeadZ = LHS.countMinLeadingZeros();
-  unsigned RHSMaxLeadingZeros = RHS.countMaxLeadingZeros();
+  APInt MinDenum = RHS.getMinValue();
+  APInt MaxNum = LHS.getMaxValue();
+  APInt MaxRes = MinDenum.isZero() ? MaxNum : MaxNum.udiv(MinDenum);
 
-  if (RHSMaxLeadingZeros != BitWidth)
-    LeadZ = std::min(BitWidth, LeadZ + BitWidth - RHSMaxLeadingZeros - 1);
+  unsigned LeadZ = MaxRes.countLeadingZeros();
 
   Known.Zero.setHighBits(LeadZ);
+  if (Exact) {
+      // Odd / Odd -> Odd
+    if (LHS.One[0] && RHS.One[0])
+      Known.One.setBit(0);
+    // Even / Odd -> Even
+    else if (LHS.Zero[0] && RHS.One[0])
+      Known.Zero.setBit(0);
+    // Odd / Even -> impossible
+    // Even / Even -> unknown
+  }
+
   return Known;
 }
 
diff --git a/llvm/test/Analysis/ValueTracking/knownbits-div.ll b/llvm/test/Analysis/ValueTracking/knownbits-div.ll
--- a/llvm/test/Analysis/ValueTracking/knownbits-div.ll
+++ b/llvm/test/Analysis/ValueTracking/knownbits-div.ll
@@ -185,12 +185,7 @@
 
 define i1 @udiv_high_bits(i8 %x, i8 %y) {
 ; CHECK-LABEL: @udiv_high_bits(
-; CHECK-NEXT:    [[NUM:%.*]] = and i8 [[X:%.*]], -127
-; CHECK-NEXT:    [[DENUM:%.*]] = or i8 [[Y:%.*]], 31
-; CHECK-NEXT:    [[DIV:%.*]] = udiv i8 [[NUM]], [[DENUM]]
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[DIV]], 8
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[AND]], 8
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %num = and i8 %x, 129
   %denum = or i8 %y, 31
diff --git a/llvm/unittests/Support/KnownBitsTest.cpp b/llvm/unittests/Support/KnownBitsTest.cpp
--- a/llvm/unittests/Support/KnownBitsTest.cpp
+++ b/llvm/unittests/Support/KnownBitsTest.cpp
@@ -114,6 +114,7 @@
       KnownBits KnownMulHS(KnownAnd);
       KnownBits KnownMulHU(KnownAnd);
       KnownBits KnownUDiv(KnownAnd);
+      KnownBits KnownUDivExact(KnownAnd);
       KnownBits KnownSDiv(KnownAnd);
       KnownBits KnownSDivExact(KnownAnd);
       KnownBits KnownURem(KnownAnd);
@@ -171,6 +172,11 @@
             KnownUDiv.One &= Res;
             KnownUDiv.Zero &= ~Res;
 
+            if (N1.urem(N2).isZero()) {
+              KnownUDivExact.One &= Res;
+              KnownUDivExact.Zero &= ~Res;
+            }
+
             Res = N1.urem(N2);
             KnownURem.One &= Res;
             KnownURem.Zero &= ~Res;
@@ -247,10 +253,14 @@
       EXPECT_TRUE(ComputedMulHU.Zero.isSubsetOf(KnownMulHU.Zero));
       EXPECT_TRUE(ComputedMulHU.One.isSubsetOf(KnownMulHU.One));
 
-      KnownBits ComputedUDiv = KnownBits::udiv(Known1, Known2);
+      KnownBits ComputedUDiv = KnownBits::udiv(Known1, Known2, false);
       EXPECT_TRUE(ComputedUDiv.Zero.isSubsetOf(KnownUDiv.Zero));
       EXPECT_TRUE(ComputedUDiv.One.isSubsetOf(KnownUDiv.One));
 
+      KnownBits ComputedUDivExact = KnownBits::udiv(Known1, Known2, true);
+      EXPECT_TRUE(ComputedUDivExact.Zero.isSubsetOf(KnownUDivExact.Zero));
+      EXPECT_TRUE(ComputedUDivExact.One.isSubsetOf(KnownUDivExact.One));
+
       KnownBits ComputedSDiv = KnownBits::sdiv(Known1, Known2, false);
       EXPECT_TRUE(ComputedSDiv.Zero.isSubsetOf(KnownSDiv.Zero));
       EXPECT_TRUE(ComputedSDiv.One.isSubsetOf(KnownSDiv.One));