Index: llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
===================================================================
--- llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
+++ llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
@@ -3083,13 +3083,35 @@
         return BinaryOperator::Create(BinOp, LHS, RHS);
       }
 
+      assert(*EV.idx_begin() == 1);
+
       // If the normal result of the add is dead, and the RHS is a constant,
-      // we can transform this into a range comparison.
-      // overflow = uadd a, -4  -->  overflow = icmp ugt a, 3
-      if (WO->getIntrinsicID() == Intrinsic::uadd_with_overflow)
+      // we can transform this into a range comparison for many cases.
+      // TODO: We can generalize these for non-constant rhs when the newly
+      // formed expressions are known to simplify.  Constants are merely one
+      // such case.
+      switch(WO->getIntrinsicID()) {
+      default:
+        break;
+      case Intrinsic::uadd_with_overflow:
+        // overflow = uadd a, -4  -->  overflow = icmp ugt a, 3
         if (ConstantInt *CI = dyn_cast<ConstantInt>(WO->getRHS()))
           return new ICmpInst(ICmpInst::ICMP_UGT, WO->getLHS(),
                               ConstantExpr::getNot(CI));
+        break;
+      case Intrinsic::umul_with_overflow:
+        // overflow for umul a, C  --> a > UINT_MAX udiv C
+        // (unless C == 0, in which case no overflow ever occurs)
+        if (ConstantInt *CI = dyn_cast<ConstantInt>(WO->getRHS())) {
+          assert(!CI->isZero() && "handled by instruction simplify");
+          auto UMax = APInt::getMaxValue(CI->getType()->getBitWidth());
+          auto *Op =
+            ConstantExpr::getUDiv(ConstantInt::get(CI->getType(), UMax), CI);
+          return new ICmpInst(ICmpInst::ICMP_UGT, WO->getLHS(), Op);
+        }
+        break;
+      };
+
     }
   }
   if (LoadInst *L = dyn_cast<LoadInst>(Agg))
Index: llvm/test/Transforms/InstCombine/umulo.ll
===================================================================
--- /dev/null
+++ llvm/test/Transforms/InstCombine/umulo.ll
@@ -0,0 +1,85 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+declare { i64, i1 } @llvm.umul.with.overflow.i64(i64, i64)
+declare { i8, i1 } @llvm.umul.with.overflow.i8(i8, i8)
+
+define i1 @test_generic(i64 %a, i64 %b) {
+; CHECK-LABEL: @test_generic(
+; CHECK-NEXT:    [[RES:%.*]] = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 [[A:%.*]], i64 [[B:%.*]])
+; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i64, i1 } [[RES]], 1
+; CHECK-NEXT:    ret i1 [[OVERFLOW]]
+;
+  %res = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 %a, i64 %b)
+  %overflow = extractvalue { i64, i1 } %res, 1
+  ret i1 %overflow
+}
+
+define i1 @test_constant0(i8 %a) {
+; CHECK-LABEL: @test_constant0(
+; CHECK-NEXT:    ret i1 false
+;
+  %res = tail call { i8, i1 } @llvm.umul.with.overflow.i8(i8 %a, i8 0)
+  %overflow = extractvalue { i8, i1 } %res, 1
+  ret i1 %overflow
+}
+
+define i1 @test_constant1(i8 %a) {
+; CHECK-LABEL: @test_constant1(
+; CHECK-NEXT:    ret i1 false
+;
+  %res = tail call { i8, i1 } @llvm.umul.with.overflow.i8(i8 %a, i8 1)
+  %overflow = extractvalue { i8, i1 } %res, 1
+  ret i1 %overflow
+}
+
+define i1 @test_constant2(i8 %a) {
+; CHECK-LABEL: @test_constant2(
+; CHECK-NEXT:    [[OVERFLOW:%.*]] = icmp slt i8 [[A:%.*]], 0
+; CHECK-NEXT:    ret i1 [[OVERFLOW]]
+;
+  %res = tail call { i8, i1 } @llvm.umul.with.overflow.i8(i8 %a, i8 2)
+  %overflow = extractvalue { i8, i1 } %res, 1
+  ret i1 %overflow
+}
+
+define i1 @test_constant3(i8 %a) {
+; CHECK-LABEL: @test_constant3(
+; CHECK-NEXT:    [[OVERFLOW:%.*]] = icmp ugt i8 [[A:%.*]], 85
+; CHECK-NEXT:    ret i1 [[OVERFLOW]]
+;
+  %res = tail call { i8, i1 } @llvm.umul.with.overflow.i8(i8 %a, i8 3)
+  %overflow = extractvalue { i8, i1 } %res, 1
+  ret i1 %overflow
+}
+
+define i1 @test_constant127(i8 %a) {
+; CHECK-LABEL: @test_constant127(
+; CHECK-NEXT:    [[OVERFLOW:%.*]] = icmp ugt i8 [[A:%.*]], 2
+; CHECK-NEXT:    ret i1 [[OVERFLOW]]
+;
+  %res = tail call { i8, i1 } @llvm.umul.with.overflow.i8(i8 %a, i8 127)
+  %overflow = extractvalue { i8, i1 } %res, 1
+  ret i1 %overflow
+}
+
+define i1 @test_constant128(i8 %a) {
+; CHECK-LABEL: @test_constant128(
+; CHECK-NEXT:    [[OVERFLOW:%.*]] = icmp ugt i8 [[A:%.*]], 1
+; CHECK-NEXT:    ret i1 [[OVERFLOW]]
+;
+  %res = tail call { i8, i1 } @llvm.umul.with.overflow.i8(i8 %a, i8 128)
+  %overflow = extractvalue { i8, i1 } %res, 1
+  ret i1 %overflow
+}
+
+define i1 @test_constant255(i8 %a) {
+; CHECK-LABEL: @test_constant255(
+; CHECK-NEXT:    [[OVERFLOW:%.*]] = icmp ugt i8 [[A:%.*]], 1
+; CHECK-NEXT:    ret i1 [[OVERFLOW]]
+;
+  %res = tail call { i8, i1 } @llvm.umul.with.overflow.i8(i8 %a, i8 255)
+  %overflow = extractvalue { i8, i1 } %res, 1
+  ret i1 %overflow
+}
+