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
@@ -536,6 +536,39 @@
   return mul(WideLHS, WideRHS).extractBits(BitWidth, BitWidth);
 }
 
+static KnownBits divComputeLowBit(const KnownBits &Known, const KnownBits &LHS,
+                                  const KnownBits &RHS, bool Exact) {
+
+  if (!Exact)
+    return Known;
+
+  // If we already have a constant, we can skip this.
+  unsigned BitWidth = LHS.getBitWidth();
+  KnownBits KnownOut(Known);
+  unsigned LHSMinTZ = LHS.countMinTrailingZeros();
+  assert(LHSMinTZ < BitWidth && "We should have already handled Zero LHS");
+
+  // Odd / X -> Odd
+  //    X must be odd, otherwise the div is not exact.
+  // EvenX / EvenY [if TZ(X) == TZ(Y)] -> Odd
+  if (LHS.One[LHSMinTZ] &&
+      (LHSMinTZ == 0 ||
+       (RHS.countMinTrailingZeros() == LHSMinTZ && RHS.One[LHSMinTZ])))
+    KnownOut.One.setBit(0);
+
+  // For exact TZ(LHS) - TZ(RHS) bits must all be zero.
+  // This also covers Even / Odd -> Even
+  if (LHSMinTZ > RHS.countMaxTrailingZeros())
+    KnownOut.Zero.setLowBits(LHSMinTZ - RHS.countMaxTrailingZeros());
+
+  // In the KnownBits exhaustive tests, we have poison inputs for exact values
+  // a LOT. If we have a conflict, just return all zeros.
+  if (KnownOut.hasConflict())
+    KnownOut.setAllZero();
+
+  return KnownOut;
+}
+
 KnownBits KnownBits::sdiv(const KnownBits &LHS, const KnownBits &RHS,
                           bool Exact) {
   // Equivalent of `udiv`. We must have caught this before it was folded.
@@ -599,20 +632,7 @@
     }
   }
 
-  if (Exact) {
-    // Odd / Odd -> Odd
-    if (LHS.One[0] && RHS.One[0]) {
-      Known.Zero.clearBit(0);
-      Known.One.setBit(0);
-    }
-    // Even / Odd -> Even
-    else if (LHS.Zero[0] && RHS.One[0]) {
-      Known.One.clearBit(0);
-      Known.Zero.setBit(0);
-    }
-    // Odd / Even -> impossible
-    // Even / Even -> unknown
-  }
+  Known = divComputeLowBit(Known, LHS, RHS, Exact);
 
   assert(!Known.hasConflict() && "Bad Output");
   return Known;
@@ -640,20 +660,7 @@
   unsigned LeadZ = MaxRes.countLeadingZeros();
 
   Known.Zero.setHighBits(LeadZ);
-  if (Exact) {
-    // Odd / Odd -> Odd
-    if (LHS.One[0] && RHS.One[0]) {
-      Known.Zero.clearBit(0);
-      Known.One.setBit(0);
-    }
-    // Even / Odd -> Even
-    else if (LHS.Zero[0] && RHS.One[0]) {
-      Known.One.clearBit(0);
-      Known.Zero.setBit(0);
-    }
-    // Odd / Even -> impossible
-    // Even / Even -> unknown
-  }
+  Known = divComputeLowBit(Known, LHS, RHS, Exact);
 
   assert(!Known.hasConflict() && "Bad Output");
   return Known;