Index: llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
===================================================================
--- llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
+++ llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
@@ -4319,6 +4319,99 @@
                             Constant::getNullValue(WidestTy));
 }
 
+/// Fold icmp (udiv X, Y), Z.
+static Value *foldICmpUDiv(ICmpInst &Cmp, InstCombiner::BuilderTy &Builder) {
+  if (Cmp.isSigned())
+    return nullptr;
+
+  Value *X = nullptr;
+  Value *Y = nullptr;
+  Value *Z = nullptr;
+
+  ICmpInst::Predicate Pred;
+  if (!match(&Cmp, m_c_ICmp(Pred, m_OneUse(m_UDiv(m_Value(X), m_Value(Y))),
+                            m_Value(Z))))
+    return nullptr;
+
+  Type *ExtendedType = X->getType()->getExtendedType();
+  unsigned IntegerBitWidth = ExtendedType->getScalarSizeInBits();
+
+  // Apply following transformations.
+  // Assuming that x, y, z are extended to types that are twice as wide.
+  //
+  // Greater:
+  // x / y > z --> x >= y * (z + 1)
+  //
+  // Greater or equal:
+  // x / y >= z --> x >= y * z
+  //
+  // Less:
+  // x / y < z --> x < y * z
+  //
+  // Less or equal:
+  // x / y <= z --> x < y * (z + 1)
+  //
+  // Equal:
+  // x / y == z -->
+  // is_less = x < y * z;
+  // is_less_or_equal = x < y * z + y;
+  // result = is_less_or_equal && !is_less
+  //
+  // Not equal:
+  // x / y != z -->
+  // is_less = x < y * z;
+  // is_greater = x >= y * z + y;
+  // result = is_less || is_greater
+  //
+
+  X = Builder.CreateZExt(X, ExtendedType);
+  Y = Builder.CreateZExt(Y, ExtendedType);
+  Z = Builder.CreateZExt(Z, ExtendedType);
+
+  switch (Cmp.getPredicate()) {
+  case ICmpInst::ICMP_EQ: {
+    Value *YMultiplyZ = Builder.CreateNUWMul(Y, Z);
+    Value *IsLess = Builder.CreateICmpULT(X, YMultiplyZ);
+    Value *IsLessOrEqual =
+        Builder.CreateICmpULT(X, Builder.CreateNUWAdd(YMultiplyZ, Y));
+
+    return Builder.CreateAnd(Builder.CreateNot(IsLess), IsLessOrEqual);
+  }
+  case ICmpInst::ICMP_NE: {
+    Value *YMultiplyZ = Builder.CreateNUWMul(Y, Z);
+    Value *IsLess = Builder.CreateICmpULT(X, YMultiplyZ);
+    Value *IsGreater =
+        Builder.CreateICmpUGE(X, Builder.CreateNUWAdd(YMultiplyZ, Y));
+
+    return Builder.CreateOr(IsLess, IsGreater);
+  }
+  case ICmpInst::ICMP_UGT: {
+    Value *ConstantOne = ConstantVector::getIntegerValue(
+        ExtendedType, APInt::getOneBitSet(IntegerBitWidth, 0));
+    return Builder.CreateICmpUGE(
+        X, Builder.CreateNUWMul(Y, Builder.CreateAdd(Z, ConstantOne, {},
+                                                     /*HasNUW*/ true,
+                                                     /*HasNSW*/ true)));
+  }
+  case ICmpInst::ICMP_UGE:
+    return Builder.CreateICmpUGE(X, Builder.CreateNUWMul(Y, Z));
+  case ICmpInst::ICMP_ULT:
+    return Builder.CreateICmpULT(X, Builder.CreateNUWMul(Y, Z));
+  case ICmpInst::ICMP_ULE: {
+    Value *ConstantOne = ConstantVector::getIntegerValue(
+        ExtendedType, APInt::getOneBitSet(IntegerBitWidth, 0));
+    return Builder.CreateICmpULT(
+        X, Builder.CreateNUWMul(Y, Builder.CreateAdd(Z, ConstantOne, {},
+                                                     /*HasNUW*/ true,
+                                                     /*HasNSW*/ true)));
+  }
+  default:
+    llvm_unreachable("Unsupported predicate");
+  }
+
+  return nullptr;
+}
+
 /// Fold
 ///   (-1 u/ x) u< y
 ///   ((x * y) ?/ x) != y
@@ -6838,6 +6931,10 @@
   if (Instruction *Res = foldICmpInstWithConstant(I))
     return Res;
 
+  if (Value *V = foldICmpUDiv(I, Builder)) {
+    return replaceInstUsesWith(I, V);
+  }
+
   // Try to match comparison as a sign bit test. Intentionally do this after
   // foldICmpInstWithConstant() to potentially let other folds to happen first.
   if (Instruction *New = foldSignBitTest(I))
Index: llvm/test/Transforms/InstCombine/icmp-add.ll
===================================================================
--- llvm/test/Transforms/InstCombine/icmp-add.ll
+++ llvm/test/Transforms/InstCombine/icmp-add.ll
@@ -1125,12 +1125,12 @@
 
 define i1 @icmp_add_add_C_comm2(i32 %X, i32 %b) {
 ; CHECK-LABEL: @icmp_add_add_C_comm2(
-; CHECK-NEXT:    [[A:%.*]] = udiv i32 42, [[X:%.*]]
+; CHECK-NEXT:    [[A:%.*]] = sdiv i32 42, [[X:%.*]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 0, [[B:%.*]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[A]], [[TMP1]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
-  %a = udiv i32 42, %X ; thwart complexity-based canonicalization
+  %a = sdiv i32 42, %X ; thwart complexity-based canonicalization
   %add1 = add i32 %a, %b
   %add2 = add i32 %add1, -1
   %cmp = icmp ugt i32 %a, %add2
@@ -1139,12 +1139,12 @@
 
 define i1 @icmp_add_add_C_comm2_pred(i32 %X, i32 %b) {
 ; CHECK-LABEL: @icmp_add_add_C_comm2_pred(
-; CHECK-NEXT:    [[A:%.*]] = udiv i32 42, [[X:%.*]]
+; CHECK-NEXT:    [[A:%.*]] = sdiv i32 42, [[X:%.*]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 0, [[B:%.*]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i32 [[A]], [[TMP1]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
-  %a = udiv i32 42, %X ; thwart complexity-based canonicalization
+  %a = sdiv i32 42, %X ; thwart complexity-based canonicalization
   %add1 = add i32 %a, %b
   %add2 = add i32 %add1, -1
   %cmp = icmp ule i32 %a, %add2
@@ -1168,9 +1168,12 @@
 
 define i1 @icmp_add_add_C_comm3(i32 %X, i32 %b) {
 ; CHECK-LABEL: @icmp_add_add_C_comm3(
-; CHECK-NEXT:    [[A:%.*]] = udiv i32 42, [[X:%.*]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 0, [[B:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[A]], [[TMP1]]
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i32 [[X:%.*]] to i64
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i32 [[TMP1]] to i64
+; CHECK-NEXT:    [[TMP4:%.*]] = add nuw nsw i64 [[TMP3]], 1
+; CHECK-NEXT:    [[TMP5:%.*]] = mul nuw i64 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i64 [[TMP5]], 43
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %a = udiv i32 42, %X ; thwart complexity-based canonicalization
Index: llvm/test/Transforms/InstCombine/icmp-div-constant.ll
===================================================================
--- llvm/test/Transforms/InstCombine/icmp-div-constant.ll
+++ llvm/test/Transforms/InstCombine/icmp-div-constant.ll
@@ -248,8 +248,13 @@
 
 define i1 @udiv_eq_not_big(i8 %x, i8 %y) {
 ; CHECK-LABEL: @udiv_eq_not_big(
-; CHECK-NEXT:    [[D:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[D]], 127
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[Y:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = mul nuw nsw i16 [[TMP2]], 127
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp ule i16 [[TMP3]], [[TMP1]]
+; CHECK-NEXT:    [[TMP5:%.*]] = shl nuw nsw i16 [[TMP2]], 7
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ugt i16 [[TMP5]], [[TMP1]]
+; CHECK-NEXT:    [[R:%.*]] = and i1 [[TMP4]], [[TMP6]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %d = udiv i8 %x, %y
Index: llvm/test/Transforms/InstCombine/icmp-ext-ext.ll
===================================================================
--- llvm/test/Transforms/InstCombine/icmp-ext-ext.ll
+++ llvm/test/Transforms/InstCombine/icmp-ext-ext.ll
@@ -342,8 +342,13 @@
 
 define i1 @sext_zext_ne_known_nonneg(i8 %x, i8 %y) {
 ; CHECK-LABEL: @sext_zext_ne_known_nonneg(
-; CHECK-NEXT:    [[N:%.*]] = udiv i8 [[Y:%.*]], 6
-; CHECK-NEXT:    [[C:%.*]] = icmp ne i8 [[N]], [[X:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[Y:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = mul nuw nsw i16 [[TMP2]], 6
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp ugt i16 [[TMP3]], [[TMP1]]
+; CHECK-NEXT:    [[TMP5:%.*]] = add nuw nsw i16 [[TMP3]], 6
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ule i16 [[TMP5]], [[TMP1]]
+; CHECK-NEXT:    [[C:%.*]] = or i1 [[TMP4]], [[TMP6]]
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %a = sext i8 %x to i32
Index: llvm/test/Transforms/InstCombine/icmp-select.ll
===================================================================
--- llvm/test/Transforms/InstCombine/icmp-select.ll
+++ llvm/test/Transforms/InstCombine/icmp-select.ll
@@ -33,13 +33,13 @@
 
 define i1 @icmp_select_var_commuted(i8 %x, i8 %y, i8 %_z) {
 ; CHECK-LABEL: @icmp_select_var_commuted(
-; CHECK-NEXT:    [[Z:%.*]] = udiv i8 42, [[_Z:%.*]]
+; CHECK-NEXT:    [[Z:%.*]] = sdiv i8 42, [[_Z:%.*]]
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[X:%.*]], 0
 ; CHECK-NEXT:    [[CMP21:%.*]] = icmp eq i8 [[Z]], [[Y:%.*]]
 ; CHECK-NEXT:    [[CMP2:%.*]] = select i1 [[CMP1]], i1 true, i1 [[CMP21]]
 ; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
-  %z = udiv i8 42, %_z ; thwart complexity-based canonicalization
+  %z = sdiv i8 42, %_z ; thwart complexity-based canonicalization
   %cmp1 = icmp eq i8 %x, 0
   %sel = select i1 %cmp1, i8 %z, i8 %y
   %cmp2 = icmp eq i8 %z, %sel
Index: llvm/test/Transforms/InstCombine/icmp-udiv.ll
===================================================================
--- llvm/test/Transforms/InstCombine/icmp-udiv.ll
+++ llvm/test/Transforms/InstCombine/icmp-udiv.ll
@@ -5,9 +5,15 @@
 
 define i1 @udiv_icmp_eq_i8(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @udiv_icmp_eq_i8(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i8 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[Y:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i8 [[Z:%.*]] to i16
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i16 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ule i16 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    [[TMP6:%.*]] = add nuw i16 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp ugt i16 [[TMP6]], [[TMP1]]
+; CHECK-NEXT:    [[TMP8:%.*]] = and i1 [[TMP5]], [[TMP7]]
+; CHECK-NEXT:    ret i1 [[TMP8]]
 ;
   %1 = udiv i8 %x, %y
   %2 = icmp eq i8 %1, %z
@@ -16,9 +22,15 @@
 
 define i1 @udiv_icmp_eq_i8_commuted(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @udiv_icmp_eq_i8_commuted(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i8 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[Y:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i8 [[Z:%.*]] to i16
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i16 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ule i16 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    [[TMP6:%.*]] = add nuw i16 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp ugt i16 [[TMP6]], [[TMP1]]
+; CHECK-NEXT:    [[TMP8:%.*]] = and i1 [[TMP5]], [[TMP7]]
+; CHECK-NEXT:    ret i1 [[TMP8]]
 ;
   %1 = udiv i8 %x, %y
   %2 = icmp eq i8 %z, %1
@@ -27,9 +39,14 @@
 
 define i1 @udiv_icmp_eq_i8_constant(i8 %x, i8 %y) {
 ; CHECK-LABEL: @udiv_icmp_eq_i8_constant(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i8 [[TMP1]], 5
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[Y:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = mul nuw nsw i16 [[TMP2]], 5
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp ule i16 [[TMP3]], [[TMP1]]
+; CHECK-NEXT:    [[TMP5:%.*]] = mul nuw nsw i16 [[TMP2]], 6
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ugt i16 [[TMP5]], [[TMP1]]
+; CHECK-NEXT:    [[TMP7:%.*]] = and i1 [[TMP4]], [[TMP6]]
+; CHECK-NEXT:    ret i1 [[TMP7]]
 ;
   %1 = udiv i8 %x, %y
   %2 = icmp eq i8 %1, 5
@@ -38,9 +55,15 @@
 
 define i1 @udiv_icmp_eq_i16(i16 %x, i16 %y, i16 %z) {
 ; CHECK-LABEL: @udiv_icmp_eq_i16(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i16 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i16 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i16 [[X:%.*]] to i32
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i16 [[Y:%.*]] to i32
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i16 [[Z:%.*]] to i32
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i32 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ule i32 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    [[TMP6:%.*]] = add nuw i32 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp ugt i32 [[TMP6]], [[TMP1]]
+; CHECK-NEXT:    [[TMP8:%.*]] = and i1 [[TMP5]], [[TMP7]]
+; CHECK-NEXT:    ret i1 [[TMP8]]
 ;
   %1 = udiv i16 %x, %y
   %2 = icmp eq i16 %1, %z
@@ -49,9 +72,15 @@
 
 define i1 @udiv_icmp_eq_i32(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @udiv_icmp_eq_i32(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[X:%.*]] to i64
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i32 [[Y:%.*]] to i64
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i32 [[Z:%.*]] to i64
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i64 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ule i64 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    [[TMP6:%.*]] = add nuw i64 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp ugt i64 [[TMP6]], [[TMP1]]
+; CHECK-NEXT:    [[TMP8:%.*]] = and i1 [[TMP5]], [[TMP7]]
+; CHECK-NEXT:    ret i1 [[TMP8]]
 ;
   %1 = udiv i32 %x, %y
   %2 = icmp eq i32 %1, %z
@@ -60,9 +89,15 @@
 
 define i1 @udiv_icmp_eq_i64(i64 %x, i64 %y, i64 %z) {
 ; CHECK-LABEL: @udiv_icmp_eq_i64(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i64 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i64 [[X:%.*]] to i128
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i64 [[Y:%.*]] to i128
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i64 [[Z:%.*]] to i128
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i128 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ule i128 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    [[TMP6:%.*]] = add nuw i128 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp ugt i128 [[TMP6]], [[TMP1]]
+; CHECK-NEXT:    [[TMP8:%.*]] = and i1 [[TMP5]], [[TMP7]]
+; CHECK-NEXT:    ret i1 [[TMP8]]
 ;
   %1 = udiv i64 %x, %y
   %2 = icmp eq i64 %1, %z
@@ -71,9 +106,15 @@
 
 define i1 @udiv_icmp_eq_i128(i128 %x, i128 %y, i128 %z) {
 ; CHECK-LABEL: @udiv_icmp_eq_i128(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i128 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i128 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i128 [[X:%.*]] to i256
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i128 [[Y:%.*]] to i256
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i128 [[Z:%.*]] to i256
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i256 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ule i256 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    [[TMP6:%.*]] = add nuw i256 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp ugt i256 [[TMP6]], [[TMP1]]
+; CHECK-NEXT:    [[TMP8:%.*]] = and i1 [[TMP5]], [[TMP7]]
+; CHECK-NEXT:    ret i1 [[TMP8]]
 ;
   %1 = udiv i128 %x, %y
   %2 = icmp eq i128 %1, %z
@@ -82,9 +123,15 @@
 
 define <2 x i1> @udiv_icmp_eq_i8_vector(<2 x i8> %x, <2 x i8> %y, <2 x i8> %z) {
 ; CHECK-LABEL: @udiv_icmp_eq_i8_vector(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv <2 x i8> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq <2 x i8> [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret <2 x i1> [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext <2 x i8> [[X:%.*]] to <2 x i16>
+; CHECK-NEXT:    [[TMP2:%.*]] = zext <2 x i8> [[Y:%.*]] to <2 x i16>
+; CHECK-NEXT:    [[TMP3:%.*]] = zext <2 x i8> [[Z:%.*]] to <2 x i16>
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw <2 x i16> [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ule <2 x i16> [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    [[TMP6:%.*]] = add nuw <2 x i16> [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp ugt <2 x i16> [[TMP6]], [[TMP1]]
+; CHECK-NEXT:    [[TMP8:%.*]] = and <2 x i1> [[TMP5]], [[TMP7]]
+; CHECK-NEXT:    ret <2 x i1> [[TMP8]]
 ;
   %1 = udiv <2 x i8> %x, %y
   %2 = icmp eq <2 x i8> %1, %z
@@ -93,9 +140,15 @@
 
 define i1 @udiv_icmp_ne_i8(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @udiv_icmp_ne_i8(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i8 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[Y:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i8 [[Z:%.*]] to i16
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i16 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ugt i16 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    [[TMP6:%.*]] = add nuw i16 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp ule i16 [[TMP6]], [[TMP1]]
+; CHECK-NEXT:    [[TMP8:%.*]] = or i1 [[TMP5]], [[TMP7]]
+; CHECK-NEXT:    ret i1 [[TMP8]]
 ;
   %1 = udiv i8 %x, %y
   %2 = icmp ne i8 %1, %z
@@ -104,9 +157,15 @@
 
 define i1 @udiv_icmp_ne_i8_commuted(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @udiv_icmp_ne_i8_commuted(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i8 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[Y:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i8 [[Z:%.*]] to i16
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i16 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ugt i16 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    [[TMP6:%.*]] = add nuw i16 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp ule i16 [[TMP6]], [[TMP1]]
+; CHECK-NEXT:    [[TMP8:%.*]] = or i1 [[TMP5]], [[TMP7]]
+; CHECK-NEXT:    ret i1 [[TMP8]]
 ;
   %1 = udiv i8 %x, %y
   %2 = icmp ne i8 %z, %1
@@ -115,9 +174,14 @@
 
 define i1 @udiv_icmp_ne_i8_constant(i8 %x, i8 %y) {
 ; CHECK-LABEL: @udiv_icmp_ne_i8_constant(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i8 [[TMP1]], 5
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[Y:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = mul nuw nsw i16 [[TMP2]], 5
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp ugt i16 [[TMP3]], [[TMP1]]
+; CHECK-NEXT:    [[TMP5:%.*]] = mul nuw nsw i16 [[TMP2]], 6
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ule i16 [[TMP5]], [[TMP1]]
+; CHECK-NEXT:    [[TMP7:%.*]] = or i1 [[TMP4]], [[TMP6]]
+; CHECK-NEXT:    ret i1 [[TMP7]]
 ;
   %1 = udiv i8 %x, %y
   %2 = icmp ne i8 %1, 5
@@ -126,9 +190,15 @@
 
 define i1 @udiv_icmp_ne_i16(i16 %x, i16 %y, i16 %z) {
 ; CHECK-LABEL: @udiv_icmp_ne_i16(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i16 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i16 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i16 [[X:%.*]] to i32
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i16 [[Y:%.*]] to i32
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i16 [[Z:%.*]] to i32
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i32 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ugt i32 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    [[TMP6:%.*]] = add nuw i32 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp ule i32 [[TMP6]], [[TMP1]]
+; CHECK-NEXT:    [[TMP8:%.*]] = or i1 [[TMP5]], [[TMP7]]
+; CHECK-NEXT:    ret i1 [[TMP8]]
 ;
   %1 = udiv i16 %x, %y
   %2 = icmp ne i16 %1, %z
@@ -137,9 +207,15 @@
 
 define i1 @udiv_icmp_ne_i32(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @udiv_icmp_ne_i32(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i32 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[X:%.*]] to i64
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i32 [[Y:%.*]] to i64
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i32 [[Z:%.*]] to i64
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i64 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ugt i64 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    [[TMP6:%.*]] = add nuw i64 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp ule i64 [[TMP6]], [[TMP1]]
+; CHECK-NEXT:    [[TMP8:%.*]] = or i1 [[TMP5]], [[TMP7]]
+; CHECK-NEXT:    ret i1 [[TMP8]]
 ;
   %1 = udiv i32 %x, %y
   %2 = icmp ne i32 %1, %z
@@ -148,9 +224,15 @@
 
 define i1 @udiv_icmp_ne_i64(i64 %x, i64 %y, i64 %z) {
 ; CHECK-LABEL: @udiv_icmp_ne_i64(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i64 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i64 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i64 [[X:%.*]] to i128
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i64 [[Y:%.*]] to i128
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i64 [[Z:%.*]] to i128
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i128 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ugt i128 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    [[TMP6:%.*]] = add nuw i128 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp ule i128 [[TMP6]], [[TMP1]]
+; CHECK-NEXT:    [[TMP8:%.*]] = or i1 [[TMP5]], [[TMP7]]
+; CHECK-NEXT:    ret i1 [[TMP8]]
 ;
   %1 = udiv i64 %x, %y
   %2 = icmp ne i64 %1, %z
@@ -159,9 +241,15 @@
 
 define i1 @udiv_icmp_ne_i128(i128 %x, i128 %y, i128 %z) {
 ; CHECK-LABEL: @udiv_icmp_ne_i128(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i128 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i128 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i128 [[X:%.*]] to i256
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i128 [[Y:%.*]] to i256
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i128 [[Z:%.*]] to i256
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i256 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ugt i256 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    [[TMP6:%.*]] = add nuw i256 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp ule i256 [[TMP6]], [[TMP1]]
+; CHECK-NEXT:    [[TMP8:%.*]] = or i1 [[TMP5]], [[TMP7]]
+; CHECK-NEXT:    ret i1 [[TMP8]]
 ;
   %1 = udiv i128 %x, %y
   %2 = icmp ne i128 %1, %z
@@ -170,9 +258,15 @@
 
 define <2 x i1> @udiv_icmp_ne_i8_vector(<2 x i8> %x, <2 x i8> %y, <2 x i8> %z) {
 ; CHECK-LABEL: @udiv_icmp_ne_i8_vector(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv <2 x i8> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne <2 x i8> [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret <2 x i1> [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext <2 x i8> [[X:%.*]] to <2 x i16>
+; CHECK-NEXT:    [[TMP2:%.*]] = zext <2 x i8> [[Y:%.*]] to <2 x i16>
+; CHECK-NEXT:    [[TMP3:%.*]] = zext <2 x i8> [[Z:%.*]] to <2 x i16>
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw <2 x i16> [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ugt <2 x i16> [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    [[TMP6:%.*]] = add nuw <2 x i16> [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp ule <2 x i16> [[TMP6]], [[TMP1]]
+; CHECK-NEXT:    [[TMP8:%.*]] = or <2 x i1> [[TMP5]], [[TMP7]]
+; CHECK-NEXT:    ret <2 x i1> [[TMP8]]
 ;
   %1 = udiv <2 x i8> %x, %y
   %2 = icmp ne <2 x i8> %1, %z
@@ -181,9 +275,13 @@
 
 define i1 @udiv_icmp_ugt_i8(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @udiv_icmp_ugt_i8(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ugt i8 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[Y:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i8 [[Z:%.*]] to i16
+; CHECK-NEXT:    [[TMP4:%.*]] = add nuw nsw i16 [[TMP3]], 1
+; CHECK-NEXT:    [[TMP5:%.*]] = mul nuw i16 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ule i16 [[TMP5]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP6]]
 ;
   %1 = udiv i8 %x, %y
   %2 = icmp ugt i8 %1, %z
@@ -192,9 +290,13 @@
 
 define i1 @udiv_icmp_ugt_reverse_i8(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @udiv_icmp_ugt_reverse_i8(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ugt i8 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[Y:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i8 [[Z:%.*]] to i16
+; CHECK-NEXT:    [[TMP4:%.*]] = add nuw nsw i16 [[TMP3]], 1
+; CHECK-NEXT:    [[TMP5:%.*]] = mul nuw i16 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ule i16 [[TMP5]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP6]]
 ;
   %1 = udiv i8 %x, %y
   %2 = icmp ult i8 %z, %1
@@ -203,9 +305,11 @@
 
 define i1 @udiv_icmp_ugt_i8_constant(i8 %x, i8 %y) {
 ; CHECK-LABEL: @udiv_icmp_ugt_i8_constant(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ugt i8 [[TMP1]], 5
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[Y:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = mul nuw nsw i16 [[TMP2]], 6
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp ule i16 [[TMP3]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP4]]
 ;
   %1 = udiv i8 %x, %y
   %2 = icmp ugt i8 %1, 5
@@ -214,9 +318,13 @@
 
 define i1 @udiv_icmp_ugt_i16(i16 %x, i16 %y, i16 %z) {
 ; CHECK-LABEL: @udiv_icmp_ugt_i16(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i16 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ugt i16 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i16 [[X:%.*]] to i32
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i16 [[Y:%.*]] to i32
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i16 [[Z:%.*]] to i32
+; CHECK-NEXT:    [[TMP4:%.*]] = add nuw nsw i32 [[TMP3]], 1
+; CHECK-NEXT:    [[TMP5:%.*]] = mul nuw i32 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ule i32 [[TMP5]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP6]]
 ;
   %1 = udiv i16 %x, %y
   %2 = icmp ugt i16 %1, %z
@@ -225,9 +333,13 @@
 
 define i1 @udiv_icmp_ugt_i32(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @udiv_icmp_ugt_i32(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ugt i32 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[X:%.*]] to i64
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i32 [[Y:%.*]] to i64
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i32 [[Z:%.*]] to i64
+; CHECK-NEXT:    [[TMP4:%.*]] = add nuw nsw i64 [[TMP3]], 1
+; CHECK-NEXT:    [[TMP5:%.*]] = mul nuw i64 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ule i64 [[TMP5]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP6]]
 ;
   %1 = udiv i32 %x, %y
   %2 = icmp ugt i32 %1, %z
@@ -236,9 +348,13 @@
 
 define i1 @udiv_icmp_ugt_i64(i64 %x, i64 %y, i64 %z) {
 ; CHECK-LABEL: @udiv_icmp_ugt_i64(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i64 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ugt i64 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i64 [[X:%.*]] to i128
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i64 [[Y:%.*]] to i128
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i64 [[Z:%.*]] to i128
+; CHECK-NEXT:    [[TMP4:%.*]] = add nuw nsw i128 [[TMP3]], 1
+; CHECK-NEXT:    [[TMP5:%.*]] = mul nuw i128 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ule i128 [[TMP5]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP6]]
 ;
   %1 = udiv i64 %x, %y
   %2 = icmp ugt i64 %1, %z
@@ -247,9 +363,13 @@
 
 define i1 @udiv_icmp_ugt_i128(i128 %x, i128 %y, i128 %z) {
 ; CHECK-LABEL: @udiv_icmp_ugt_i128(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i128 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ugt i128 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i128 [[X:%.*]] to i256
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i128 [[Y:%.*]] to i256
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i128 [[Z:%.*]] to i256
+; CHECK-NEXT:    [[TMP4:%.*]] = add nuw nsw i256 [[TMP3]], 1
+; CHECK-NEXT:    [[TMP5:%.*]] = mul nuw i256 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ule i256 [[TMP5]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP6]]
 ;
   %1 = udiv i128 %x, %y
   %2 = icmp ugt i128 %1, %z
@@ -258,9 +378,13 @@
 
 define <2 x i1> @udiv_icmp_ugt_i8_vector(<2 x i8> %x, <2 x i8> %y, <2 x i8> %z) {
 ; CHECK-LABEL: @udiv_icmp_ugt_i8_vector(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv <2 x i8> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ugt <2 x i8> [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret <2 x i1> [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext <2 x i8> [[X:%.*]] to <2 x i16>
+; CHECK-NEXT:    [[TMP2:%.*]] = zext <2 x i8> [[Y:%.*]] to <2 x i16>
+; CHECK-NEXT:    [[TMP3:%.*]] = zext <2 x i8> [[Z:%.*]] to <2 x i16>
+; CHECK-NEXT:    [[TMP4:%.*]] = add nuw nsw <2 x i16> [[TMP3]], <i16 1, i16 1>
+; CHECK-NEXT:    [[TMP5:%.*]] = mul nuw <2 x i16> [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ule <2 x i16> [[TMP5]], [[TMP1]]
+; CHECK-NEXT:    ret <2 x i1> [[TMP6]]
 ;
   %1 = udiv <2 x i8> %x, %y
   %2 = icmp ugt <2 x i8> %1, %z
@@ -269,9 +393,12 @@
 
 define i1 @udiv_icmp_uge_i8(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @udiv_icmp_uge_i8(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp uge i8 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[Y:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i8 [[Z:%.*]] to i16
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i16 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ule i16 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP5]]
 ;
   %1 = udiv i8 %x, %y
   %2 = icmp uge i8 %1, %z
@@ -280,9 +407,12 @@
 
 define i1 @udiv_icmp_uge_reverse_i8(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @udiv_icmp_uge_reverse_i8(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp uge i8 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[Y:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i8 [[Z:%.*]] to i16
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i16 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ule i16 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP5]]
 ;
   %1 = udiv i8 %x, %y
   %2 = icmp ule i8 %z, %1
@@ -291,9 +421,11 @@
 
 define i1 @udiv_icmp_uge_i8_constant(i8 %x, i8 %y) {
 ; CHECK-LABEL: @udiv_icmp_uge_i8_constant(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ugt i8 [[TMP1]], 4
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[Y:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = mul nuw nsw i16 [[TMP2]], 5
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp ule i16 [[TMP3]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP4]]
 ;
   %1 = udiv i8 %x, %y
   %2 = icmp uge i8 %1, 5
@@ -302,9 +434,12 @@
 
 define i1 @udiv_icmp_uge_i16(i16 %x, i16 %y, i16 %z) {
 ; CHECK-LABEL: @udiv_icmp_uge_i16(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i16 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp uge i16 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i16 [[X:%.*]] to i32
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i16 [[Y:%.*]] to i32
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i16 [[Z:%.*]] to i32
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i32 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ule i32 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP5]]
 ;
   %1 = udiv i16 %x, %y
   %2 = icmp uge i16 %1, %z
@@ -313,9 +448,12 @@
 
 define i1 @udiv_icmp_uge_i32(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @udiv_icmp_uge_i32(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp uge i32 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[X:%.*]] to i64
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i32 [[Y:%.*]] to i64
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i32 [[Z:%.*]] to i64
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i64 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ule i64 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP5]]
 ;
   %1 = udiv i32 %x, %y
   %2 = icmp uge i32 %1, %z
@@ -324,9 +462,12 @@
 
 define i1 @udiv_icmp_uge_i64(i64 %x, i64 %y, i64 %z) {
 ; CHECK-LABEL: @udiv_icmp_uge_i64(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i64 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp uge i64 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i64 [[X:%.*]] to i128
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i64 [[Y:%.*]] to i128
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i64 [[Z:%.*]] to i128
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i128 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ule i128 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP5]]
 ;
   %1 = udiv i64 %x, %y
   %2 = icmp uge i64 %1, %z
@@ -335,9 +476,12 @@
 
 define i1 @udiv_icmp_uge_i128(i128 %x, i128 %y, i128 %z) {
 ; CHECK-LABEL: @udiv_icmp_uge_i128(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i128 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp uge i128 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i128 [[X:%.*]] to i256
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i128 [[Y:%.*]] to i256
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i128 [[Z:%.*]] to i256
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i256 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ule i256 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP5]]
 ;
   %1 = udiv i128 %x, %y
   %2 = icmp uge i128 %1, %z
@@ -346,9 +490,12 @@
 
 define <2 x i1> @udiv_icmp_uge_i8_vector(<2 x i8> %x, <2 x i8> %y, <2 x i8> %z) {
 ; CHECK-LABEL: @udiv_icmp_uge_i8_vector(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv <2 x i8> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp uge <2 x i8> [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret <2 x i1> [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext <2 x i8> [[X:%.*]] to <2 x i16>
+; CHECK-NEXT:    [[TMP2:%.*]] = zext <2 x i8> [[Y:%.*]] to <2 x i16>
+; CHECK-NEXT:    [[TMP3:%.*]] = zext <2 x i8> [[Z:%.*]] to <2 x i16>
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw <2 x i16> [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ule <2 x i16> [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    ret <2 x i1> [[TMP5]]
 ;
   %1 = udiv <2 x i8> %x, %y
   %2 = icmp uge <2 x i8> %1, %z
@@ -357,9 +504,12 @@
 
 define i1 @udiv_icmp_ult_i8(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @udiv_icmp_ult_i8(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i8 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[Y:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i8 [[Z:%.*]] to i16
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i16 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ugt i16 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP5]]
 ;
   %1 = udiv i8 %x, %y
   %2 = icmp ult i8 %1, %z
@@ -368,9 +518,12 @@
 
 define i1 @udiv_icmp_ult_reverse_i8(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @udiv_icmp_ult_reverse_i8(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i8 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[Y:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i8 [[Z:%.*]] to i16
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i16 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ugt i16 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP5]]
 ;
   %1 = udiv i8 %x, %y
   %2 = icmp ugt i8 %z, %1
@@ -379,9 +532,11 @@
 
 define i1 @udiv_icmp_ult_i8_constant(i8 %x, i8 %y) {
 ; CHECK-LABEL: @udiv_icmp_ult_i8_constant(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i8 [[TMP1]], 5
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[Y:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = mul nuw nsw i16 [[TMP2]], 5
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp ugt i16 [[TMP3]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP4]]
 ;
   %1 = udiv i8 %x, %y
   %2 = icmp ult i8 %1, 5
@@ -390,9 +545,12 @@
 
 define i1 @udiv_icmp_ult_i16(i16 %x, i16 %y, i16 %z) {
 ; CHECK-LABEL: @udiv_icmp_ult_i16(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i16 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i16 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i16 [[X:%.*]] to i32
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i16 [[Y:%.*]] to i32
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i16 [[Z:%.*]] to i32
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i32 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ugt i32 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP5]]
 ;
   %1 = udiv i16 %x, %y
   %2 = icmp ult i16 %1, %z
@@ -401,9 +559,12 @@
 
 define i1 @udiv_icmp_ult_i32(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @udiv_icmp_ult_i32(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i32 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[X:%.*]] to i64
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i32 [[Y:%.*]] to i64
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i32 [[Z:%.*]] to i64
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i64 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ugt i64 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP5]]
 ;
   %1 = udiv i32 %x, %y
   %2 = icmp ult i32 %1, %z
@@ -412,9 +573,12 @@
 
 define i1 @udiv_icmp_ult_i64(i64 %x, i64 %y, i64 %z) {
 ; CHECK-LABEL: @udiv_icmp_ult_i64(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i64 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i64 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i64 [[X:%.*]] to i128
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i64 [[Y:%.*]] to i128
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i64 [[Z:%.*]] to i128
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i128 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ugt i128 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP5]]
 ;
   %1 = udiv i64 %x, %y
   %2 = icmp ult i64 %1, %z
@@ -423,9 +587,12 @@
 
 define i1 @udiv_icmp_ult_i128(i128 %x, i128 %y, i128 %z) {
 ; CHECK-LABEL: @udiv_icmp_ult_i128(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i128 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i128 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i128 [[X:%.*]] to i256
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i128 [[Y:%.*]] to i256
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i128 [[Z:%.*]] to i256
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i256 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ugt i256 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP5]]
 ;
   %1 = udiv i128 %x, %y
   %2 = icmp ult i128 %1, %z
@@ -434,9 +601,12 @@
 
 define <2 x i1> @udiv_icmp_ult_i8_vector(<2 x i8> %x, <2 x i8> %y, <2 x i8> %z) {
 ; CHECK-LABEL: @udiv_icmp_ult_i8_vector(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv <2 x i8> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult <2 x i8> [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret <2 x i1> [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext <2 x i8> [[X:%.*]] to <2 x i16>
+; CHECK-NEXT:    [[TMP2:%.*]] = zext <2 x i8> [[Y:%.*]] to <2 x i16>
+; CHECK-NEXT:    [[TMP3:%.*]] = zext <2 x i8> [[Z:%.*]] to <2 x i16>
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw <2 x i16> [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ugt <2 x i16> [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    ret <2 x i1> [[TMP5]]
 ;
   %1 = udiv <2 x i8> %x, %y
   %2 = icmp ult <2 x i8> %1, %z
@@ -445,9 +615,13 @@
 
 define i1 @udiv_icmp_ule_i8(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @udiv_icmp_ule_i8(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ule i8 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[Y:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i8 [[Z:%.*]] to i16
+; CHECK-NEXT:    [[TMP4:%.*]] = add nuw nsw i16 [[TMP3]], 1
+; CHECK-NEXT:    [[TMP5:%.*]] = mul nuw i16 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ugt i16 [[TMP5]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP6]]
 ;
   %1 = udiv i8 %x, %y
   %2 = icmp ule i8 %1, %z
@@ -456,9 +630,13 @@
 
 define i1 @udiv_icmp_ule_reverse_i8(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @udiv_icmp_ule_reverse_i8(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ule i8 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[Y:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i8 [[Z:%.*]] to i16
+; CHECK-NEXT:    [[TMP4:%.*]] = add nuw nsw i16 [[TMP3]], 1
+; CHECK-NEXT:    [[TMP5:%.*]] = mul nuw i16 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ugt i16 [[TMP5]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP6]]
 ;
   %1 = udiv i8 %x, %y
   %2 = icmp uge i8 %z, %1
@@ -467,9 +645,11 @@
 
 define i1 @udiv_icmp_ule_i8_constant(i8 %x, i8 %y) {
 ; CHECK-LABEL: @udiv_icmp_ule_i8_constant(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i8 [[TMP1]], 6
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[Y:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = mul nuw nsw i16 [[TMP2]], 6
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp ugt i16 [[TMP3]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP4]]
 ;
   %1 = udiv i8 %x, %y
   %2 = icmp ule i8 %1, 5
@@ -478,9 +658,13 @@
 
 define i1 @udiv_icmp_ule_i16(i16 %x, i16 %y, i16 %z) {
 ; CHECK-LABEL: @udiv_icmp_ule_i16(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i16 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ule i16 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i16 [[X:%.*]] to i32
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i16 [[Y:%.*]] to i32
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i16 [[Z:%.*]] to i32
+; CHECK-NEXT:    [[TMP4:%.*]] = add nuw nsw i32 [[TMP3]], 1
+; CHECK-NEXT:    [[TMP5:%.*]] = mul nuw i32 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ugt i32 [[TMP5]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP6]]
 ;
   %1 = udiv i16 %x, %y
   %2 = icmp ule i16 %1, %z
@@ -489,9 +673,13 @@
 
 define i1 @udiv_icmp_ule_i32(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @udiv_icmp_ule_i32(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ule i32 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[X:%.*]] to i64
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i32 [[Y:%.*]] to i64
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i32 [[Z:%.*]] to i64
+; CHECK-NEXT:    [[TMP4:%.*]] = add nuw nsw i64 [[TMP3]], 1
+; CHECK-NEXT:    [[TMP5:%.*]] = mul nuw i64 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ugt i64 [[TMP5]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP6]]
 ;
   %1 = udiv i32 %x, %y
   %2 = icmp ule i32 %1, %z
@@ -500,9 +688,13 @@
 
 define i1 @udiv_icmp_ule_i64(i64 %x, i64 %y, i64 %z) {
 ; CHECK-LABEL: @udiv_icmp_ule_i64(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i64 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ule i64 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i64 [[X:%.*]] to i128
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i64 [[Y:%.*]] to i128
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i64 [[Z:%.*]] to i128
+; CHECK-NEXT:    [[TMP4:%.*]] = add nuw nsw i128 [[TMP3]], 1
+; CHECK-NEXT:    [[TMP5:%.*]] = mul nuw i128 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ugt i128 [[TMP5]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP6]]
 ;
   %1 = udiv i64 %x, %y
   %2 = icmp ule i64 %1, %z
@@ -511,9 +703,13 @@
 
 define i1 @udiv_icmp_ule_i128(i128 %x, i128 %y, i128 %z) {
 ; CHECK-LABEL: @udiv_icmp_ule_i128(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i128 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ule i128 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i128 [[X:%.*]] to i256
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i128 [[Y:%.*]] to i256
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i128 [[Z:%.*]] to i256
+; CHECK-NEXT:    [[TMP4:%.*]] = add nuw nsw i256 [[TMP3]], 1
+; CHECK-NEXT:    [[TMP5:%.*]] = mul nuw i256 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ugt i256 [[TMP5]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP6]]
 ;
   %1 = udiv i128 %x, %y
   %2 = icmp ule i128 %1, %z
@@ -522,9 +718,13 @@
 
 define <2 x i1> @udiv_icmp_ule_i8_vector(<2 x i8> %x, <2 x i8> %y, <2 x i8> %z) {
 ; CHECK-LABEL: @udiv_icmp_ule_i8_vector(
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv <2 x i8> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ule <2 x i8> [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    ret <2 x i1> [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext <2 x i8> [[X:%.*]] to <2 x i16>
+; CHECK-NEXT:    [[TMP2:%.*]] = zext <2 x i8> [[Y:%.*]] to <2 x i16>
+; CHECK-NEXT:    [[TMP3:%.*]] = zext <2 x i8> [[Z:%.*]] to <2 x i16>
+; CHECK-NEXT:    [[TMP4:%.*]] = add nuw nsw <2 x i16> [[TMP3]], <i16 1, i16 1>
+; CHECK-NEXT:    [[TMP5:%.*]] = mul nuw <2 x i16> [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ugt <2 x i16> [[TMP5]], [[TMP1]]
+; CHECK-NEXT:    ret <2 x i1> [[TMP6]]
 ;
   %1 = udiv <2 x i8> %x, %y
   %2 = icmp ule <2 x i8> %1, %z
Index: llvm/test/Transforms/InstCombine/icmp.ll
===================================================================
--- llvm/test/Transforms/InstCombine/icmp.ll
+++ llvm/test/Transforms/InstCombine/icmp.ll
@@ -580,11 +580,11 @@
 
 define i1 @ugt_sub(i32 %xsrc, i32 %y) {
 ; CHECK-LABEL: @ugt_sub(
-; CHECK-NEXT:    [[X:%.*]] = udiv i32 [[XSRC:%.*]], 42
+; CHECK-NEXT:    [[X:%.*]] = sdiv i32 [[XSRC:%.*]], 42
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[X]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
-  %x = udiv i32 %xsrc, 42 ; thwart complexity-based canonicalization
+  %x = sdiv i32 %xsrc, 42 ; thwart complexity-based canonicalization
   %sub = sub i32 %x, %y
   %cmp = icmp ugt i32 %sub, %x
   ret i1 %cmp
@@ -594,11 +594,11 @@
 
 define <2 x i1> @ult_sub(<2 x i8> %xsrc, <2 x i8> %y) {
 ; CHECK-LABEL: @ult_sub(
-; CHECK-NEXT:    [[X:%.*]] = udiv <2 x i8> [[XSRC:%.*]], <i8 42, i8 -42>
+; CHECK-NEXT:    [[X:%.*]] = sdiv <2 x i8> [[XSRC:%.*]], <i8 42, i8 -42>
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult <2 x i8> [[X]], [[Y:%.*]]
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
-  %x = udiv <2 x i8> %xsrc, <i8 42, i8 -42> ; thwart complexity-based canonicalization
+  %x = sdiv <2 x i8> %xsrc, <i8 42, i8 -42> ; thwart complexity-based canonicalization
   %sub = sub <2 x i8> %x, %y
   %cmp = icmp ult <2 x i8> %x, %sub
   ret <2 x i1> %cmp
Index: llvm/test/Transforms/InstCombine/unsigned-mul-lack-of-overflow-check-via-mul-udiv.ll
===================================================================
--- llvm/test/Transforms/InstCombine/unsigned-mul-lack-of-overflow-check-via-mul-udiv.ll
+++ llvm/test/Transforms/InstCombine/unsigned-mul-lack-of-overflow-check-via-mul-udiv.ll
@@ -136,8 +136,14 @@
 define i1 @n8_different_x(i8 %x0, i8 %x1, i8 %y) {
 ; CHECK-LABEL: @n8_different_x(
 ; CHECK-NEXT:    [[T0:%.*]] = mul i8 [[X0:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = udiv i8 [[T0]], [[X1:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[T1]], [[Y]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[T0]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[X1:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i8 [[Y]] to i16
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i16 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ule i16 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    [[TMP6:%.*]] = add nuw i16 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp ugt i16 [[TMP6]], [[TMP1]]
+; CHECK-NEXT:    [[R:%.*]] = and i1 [[TMP5]], [[TMP7]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %t0 = mul i8 %x0, %y
@@ -149,8 +155,14 @@
 define i1 @n9_different_y(i8 %x, i8 %y0, i8 %y1) {
 ; CHECK-LABEL: @n9_different_y(
 ; CHECK-NEXT:    [[T0:%.*]] = mul i8 [[X:%.*]], [[Y0:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = udiv i8 [[T0]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[T1]], [[Y1:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[T0]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[X]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i8 [[Y1:%.*]] to i16
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i16 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ule i16 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    [[TMP6:%.*]] = add nuw i16 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp ugt i16 [[TMP6]], [[TMP1]]
+; CHECK-NEXT:    [[R:%.*]] = and i1 [[TMP5]], [[TMP7]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %t0 = mul i8 %x, %y0
@@ -162,8 +174,11 @@
 define i1 @n10_wrong_pred(i8 %x, i8 %y) {
 ; CHECK-LABEL: @n10_wrong_pred(
 ; CHECK-NEXT:    [[T0:%.*]] = mul i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = udiv i8 [[T0]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ult i8 [[T1]], [[Y]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[T0]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[X]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i8 [[Y]] to i16
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i16 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i16 [[TMP4]], [[TMP1]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %t0 = mul i8 %x, %y
Index: llvm/test/Transforms/InstCombine/unsigned-mul-lack-of-overflow-check-via-udiv-of-allones.ll
===================================================================
--- llvm/test/Transforms/InstCombine/unsigned-mul-lack-of-overflow-check-via-udiv-of-allones.ll
+++ llvm/test/Transforms/InstCombine/unsigned-mul-lack-of-overflow-check-via-udiv-of-allones.ll
@@ -77,8 +77,10 @@
 
 define i1 @n5_not_negone(i8 %x, i8 %y) {
 ; CHECK-LABEL: @n5_not_negone(
-; CHECK-NEXT:    [[T0:%.*]] = udiv i8 -2, [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp uge i8 [[T0]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[Y:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = mul nuw i16 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ult i16 [[TMP3]], 255
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %t0 = udiv i8 -2, %x ; not -1
@@ -88,8 +90,11 @@
 
 define i1 @n6_wrong_pred0(i8 %x, i8 %y) {
 ; CHECK-LABEL: @n6_wrong_pred0(
-; CHECK-NEXT:    [[T0:%.*]] = udiv i8 -1, [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ule i8 [[T0]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[Y:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = add nuw nsw i16 [[TMP2]], 1
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i16 [[TMP3]], [[TMP1]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i16 [[TMP4]], 255
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %t0 = udiv i8 -1, %x
@@ -99,8 +104,11 @@
 
 define i1 @n6_wrong_pred1(i8 %x, i8 %y) {
 ; CHECK-LABEL: @n6_wrong_pred1(
-; CHECK-NEXT:    [[T0:%.*]] = udiv i8 -1, [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[T0]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[Y:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = add nuw nsw i16 [[TMP2]], 1
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i16 [[TMP3]], [[TMP1]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ult i16 [[TMP4]], 256
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %t0 = udiv i8 -1, %x
Index: llvm/test/Transforms/InstCombine/unsigned-mul-overflow-check-via-mul-udiv.ll
===================================================================
--- llvm/test/Transforms/InstCombine/unsigned-mul-overflow-check-via-mul-udiv.ll
+++ llvm/test/Transforms/InstCombine/unsigned-mul-overflow-check-via-mul-udiv.ll
@@ -130,8 +130,14 @@
 define i1 @n8_different_x(i8 %x0, i8 %x1, i8 %y) {
 ; CHECK-LABEL: @n8_different_x(
 ; CHECK-NEXT:    [[T0:%.*]] = mul i8 [[X0:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = udiv i8 [[T0]], [[X1:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[T1]], [[Y]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[T0]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[X1:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i8 [[Y]] to i16
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i16 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ugt i16 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    [[TMP6:%.*]] = add nuw i16 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp ule i16 [[TMP6]], [[TMP1]]
+; CHECK-NEXT:    [[R:%.*]] = or i1 [[TMP5]], [[TMP7]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %t0 = mul i8 %x0, %y
@@ -143,8 +149,14 @@
 define i1 @n9_different_y(i8 %x, i8 %y0, i8 %y1) {
 ; CHECK-LABEL: @n9_different_y(
 ; CHECK-NEXT:    [[T0:%.*]] = mul i8 [[X:%.*]], [[Y0:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = udiv i8 [[T0]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[T1]], [[Y1:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[T0]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[X]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i8 [[Y1:%.*]] to i16
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i16 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ugt i16 [[TMP4]], [[TMP1]]
+; CHECK-NEXT:    [[TMP6:%.*]] = add nuw i16 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp ule i16 [[TMP6]], [[TMP1]]
+; CHECK-NEXT:    [[R:%.*]] = or i1 [[TMP5]], [[TMP7]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %t0 = mul i8 %x, %y0
@@ -156,8 +168,12 @@
 define i1 @n10_wrong_pred(i8 %x, i8 %y) {
 ; CHECK-LABEL: @n10_wrong_pred(
 ; CHECK-NEXT:    [[T0:%.*]] = mul i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = udiv i8 [[T0]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[T1]], [[Y]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[T0]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[X]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = zext i8 [[Y]] to i16
+; CHECK-NEXT:    [[TMP4:%.*]] = add nuw nsw i16 [[TMP3]], 1
+; CHECK-NEXT:    [[TMP5:%.*]] = mul nuw i16 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ule i16 [[TMP5]], [[TMP1]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %t0 = mul i8 %x, %y
Index: llvm/test/Transforms/InstCombine/unsigned-mul-overflow-check-via-udiv-of-allones.ll
===================================================================
--- llvm/test/Transforms/InstCombine/unsigned-mul-overflow-check-via-udiv-of-allones.ll
+++ llvm/test/Transforms/InstCombine/unsigned-mul-overflow-check-via-udiv-of-allones.ll
@@ -73,8 +73,10 @@
 
 define i1 @n5_not_negone(i8 %x, i8 %y) {
 ; CHECK-LABEL: @n5_not_negone(
-; CHECK-NEXT:    [[T0:%.*]] = udiv i8 -2, [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ult i8 [[T0]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[Y:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = mul nuw i16 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i16 [[TMP3]], 254
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %t0 = udiv i8 -2, %x ; not -1
@@ -84,8 +86,11 @@
 
 define i1 @n6_wrong_pred0(i8 %x, i8 %y) {
 ; CHECK-LABEL: @n6_wrong_pred0(
-; CHECK-NEXT:    [[T0:%.*]] = udiv i8 -1, [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ule i8 [[T0]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[Y:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = add nuw nsw i16 [[TMP2]], 1
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i16 [[TMP3]], [[TMP1]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i16 [[TMP4]], 255
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %t0 = udiv i8 -1, %x
@@ -95,8 +100,11 @@
 
 define i1 @n6_wrong_pred1(i8 %x, i8 %y) {
 ; CHECK-LABEL: @n6_wrong_pred1(
-; CHECK-NEXT:    [[T0:%.*]] = udiv i8 -1, [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[T0]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[Y:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = add nuw nsw i16 [[TMP2]], 1
+; CHECK-NEXT:    [[TMP4:%.*]] = mul nuw i16 [[TMP3]], [[TMP1]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ult i16 [[TMP4]], 256
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %t0 = udiv i8 -1, %x