Index: lib/Transforms/InstCombine/InstCombineCompares.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineCompares.cpp
+++ lib/Transforms/InstCombine/InstCombineCompares.cpp
@@ -3250,6 +3250,23 @@
 
   bool isSignBit = false;
 
+  // a > (UINT_MAX /u b) is a portable way to check if a * b overflows --
+  // replace it with a umul_with_overflow
+  {
+    ConstantInt *CI;
+    Value *R;
+    if (I.getPredicate() == ICmpInst::ICMP_ULT &&
+        match(Op0, m_UDiv(m_ConstantInt(CI), m_Value(R))) &&
+        CI->isMaxValue(false)) {
+      Type *T = IntegerType::get(I.getContext(), CI->getBitWidth());
+      Value *F = Intrinsic::getDeclaration(I.getModule(),
+                                           Intrinsic::umul_with_overflow, T);
+      Builder->SetInsertPoint(&I);
+      CallInst *Call = Builder->CreateCall(F, {I.getOperand(1), R}, "umul");
+      return ExtractValueInst::Create(Call, 1, "umul.overflow");
+    }
+  }
+
   // See if we are doing a comparison with a constant.
   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
     Value *A = nullptr, *B = nullptr;
Index: test/Transforms/InstCombine/overflow-mul.ll
===================================================================
--- test/Transforms/InstCombine/overflow-mul.ll
+++ test/Transforms/InstCombine/overflow-mul.ll
@@ -174,7 +174,31 @@
   ret <4 x i32> %vcgez.i
 }
 
+; a > (UINT_MAX /u b)  -->  mul.with.overflow(a, b)
+define i32 @div_elim32(i32 %a, i32 %b) #0 {
+; CHECK-LABEL: div_elim32
+; CHECK-NOT: udiv
+; CHECK: umul.with.overflow
+entry:
+  %div = udiv i32 -1, %b
+  %cmp = icmp ult i32 %div, %a
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
 
+; a > (UINT_MAX /u b)  -->  mul.with.overflow(a, b)
+define i32 @div_elim64(i64 %a, i64 %b) #0 {
+; CHECK-LABEL: div_elim64
+; CHECK-NOT: udiv
+; CHECK: umul.with.overflow
+entry:
+  %div = udiv i64 -1, %b
+  %cmp = icmp ult i64 %div, %a
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
+
+
 ; The last test needs this weird datalayout.
 target datalayout = "i32:8:8"
 ; Without it, InstCombine will align the pointed on 4 Bytes