[InstCombine] icmp udiv transform

[kitaisreal]

Summary

Transform icmp udiv into simpler instructions.
https://github.com/llvm/llvm-project/issues/55695.
Depends D156028.
More efficient solutions:

Unsigned division, unsigned > (godbolt, alive)

bool src(uint32_t x, uint32_t y, uint32_t z) { return x / y > z; }

bool tgt(uint32_t x, uint32_t y, uint32_t z) {
    uint64_t zPlusOne = (uint64_t)(z) + 1;
    return x >= (uint64_t)y * zPlusOne;
}

Unsigned division, unsigned >= (godbolt, alive)

bool src(uint32_t x, uint32_t y, uint32_t z) { return x / y >= z; }

bool tgt(uint32_t x, uint32_t y, uint32_t z) {
    return x >= (uint64_t)y * z;
}

Unsigned division, unsigned < (godbolt, alive)

bool src(uint32_t x, uint32_t y, uint32_t z) { return x / y < z; }

bool tgt(uint32_t x, uint32_t y, uint32_t z) {
    return x < (uint64_t)y * z;
}

Unsigned division, unsigned <= (godbolt, alive)

bool src(uint32_t x, uint32_t y, uint32_t z) { return x / y <= z; }

bool tgt(uint32_t x, uint32_t y, uint32_t z) {
    uint64_t zPlusOne = (uint64_t)(z) + 1;
    return x < (uint64_t)y * zPlusOne;
}

Unsigned division, == (godbolt, alive)

bool src(uint32_t x, uint32_t y, uint32_t z) { return x / y == z; }

bool tgt(uint32_t x, uint32_t y, uint32_t z) {
    uint64_t y_multiply_z = (uint64_t)y * z;
    bool is_less = x < y_multiply_z;
    bool is_less_or_equal = x < y_multiply_z + y;

    return is_less_or_equal && !is_less;
}

Unsigned division, != (godbolt, alive)

bool src(uint32_t x, uint32_t y, uint32_t z) { return x / y != z; }

bool tgt(uint32_t x, uint32_t y, uint32_t z) {
    uint64_t y_multiply_z = (uint64_t)y * z;
    bool is_less = x < y_multiply_z;
    bool is_greater = x >= y_multiply_z + y;

    return is_greater || is_less;
}

[kitaisreal]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4328

We probably can check that if udiv is used only in unsigned comparisons we can optimize it. Example:

bool test(uint8_t x, uint8_t y, uint8_t z) {
    return x / y < z && x / y > 5;
}

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4325

!isSigned?

4339

GetScalarSizeInBits?

4341

Why the > 128 threshold?

4370

This really needs alive2 links. Can you please add to the summary.

4374

Why only support udiv as operand 0?

4376

This isn't used by all predicates, can you only build this on the paths that req it?

llvm/test/Transforms/InstCombine/icmp-udiv.ll

99

It's not clear this is more canonical or universally better. It's true we occasionally add instructions to avoid div, but this is a lot. Maybe this transform belongs in the backend?

llvm/test/Transforms/InstCombine/unsigned-mul-overflow-check-via-udiv-of-allones.ll

111

Can you add some vector tests?

[nikic]

llvm/test/Transforms/InstCombine/icmp-udiv.ll

99

Yeah, this does not seem like a good canonicalization from an IR perspective.

I'm also wondering whether it would be preferable to use MULO instead of extending to double-width. Though it seems like codegen ends up being very similar for most targets (https://llvm.godbolt.org/z/73Phv83hT). Apparently muls that set overflow flags without computing a wide multiply aren't really a thing.

[kitaisreal]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4341

It seems that this check is not required at all.
For i128 https://llvm.godbolt.org/z/rK7Wvfrso and i256 https://llvm.godbolt.org/z/xeEPa6voY if we apply transformation result assembly looks much better.

llvm/test/Transforms/InstCombine/icmp-udiv.ll

99

It seems that for less, greater, less or equal, greater or equal this optimization is universally better.
We trade udiv for 3 zest, 1 mul and for greater and greater or equal we also need 1 add. In final assembly it also looks much better.

99

For equals and not equals it seems that it provides slightly more instructions, but I still think that if we can avoid division it is worth it.
I think it is okay to move this optimization in Backend, althought I am afraid that if we will not keep this optimization in IR, such construction will not be autovectorized.
For such code:

void test(uint32_t * __restrict x, uint32_t * __restrict y, uint8_t * result, uint32_t z, size_t size) {
    for (size_t i = 0; i < size; ++i) {
        result[i] = x[i] / y[i] == z;
    }
}

Result vectorized loop after this patch:

.LBB0_4:                                # %vector.body
                                        # =>This Inner Loop Header: Depth=1
	movdqu	(%rdi,%r9,4), %xmm4
	movdqu	(%rsi,%r9,4), %xmm9
	movdqa	%xmm4, %xmm5
	punpckldq	%xmm1, %xmm5            # xmm5 = xmm5[0],xmm1[0],xmm5[1],xmm1[1]
	punpckhdq	%xmm1, %xmm4            # xmm4 = xmm4[2],xmm1[2],xmm4[3],xmm1[3]
	movdqa	%xmm9, %xmm10
	punpckhdq	%xmm1, %xmm10           # xmm10 = xmm10[2],xmm1[2],xmm10[3],xmm1[3]
	punpckldq	%xmm1, %xmm9            # xmm9 = xmm9[0],xmm1[0],xmm9[1],xmm1[1]
	movdqa	%xmm0, %xmm6
	pmuludq	%xmm9, %xmm6
	movdqa	%xmm0, %xmm8
	pmuludq	%xmm10, %xmm8
	pxor	%xmm2, %xmm4
	movdqa	%xmm8, %xmm11
	pxor	%xmm2, %xmm11
	movdqa	%xmm11, %xmm12
	pcmpgtd	%xmm4, %xmm12
	pxor	%xmm2, %xmm5
	movdqa	%xmm6, %xmm13
	pxor	%xmm2, %xmm13
	movdqa	%xmm13, %xmm7
	pcmpgtd	%xmm5, %xmm7
	movdqa	%xmm7, %xmm14
	shufps	$136, %xmm12, %xmm14            # xmm14 = xmm14[0,2],xmm12[0,2]
	pcmpeqd	%xmm4, %xmm11
	pcmpeqd	%xmm5, %xmm13
	shufps	$221, %xmm11, %xmm13            # xmm13 = xmm13[1,3],xmm11[1,3]
	andps	%xmm14, %xmm13
	shufps	$221, %xmm12, %xmm7             # xmm7 = xmm7[1,3],xmm12[1,3]
	orps	%xmm13, %xmm7
	paddq	%xmm9, %xmm6
	paddq	%xmm10, %xmm8
	pxor	%xmm2, %xmm8
	movdqa	%xmm8, %xmm9
	pcmpgtd	%xmm4, %xmm9
	pxor	%xmm2, %xmm6
	movdqa	%xmm6, %xmm10
	pcmpgtd	%xmm5, %xmm10
	movdqa	%xmm10, %xmm11
	shufps	$136, %xmm9, %xmm11             # xmm11 = xmm11[0,2],xmm9[0,2]
	pcmpeqd	%xmm4, %xmm8
	pcmpeqd	%xmm5, %xmm6
	shufps	$221, %xmm8, %xmm6              # xmm6 = xmm6[1,3],xmm8[1,3]
	andps	%xmm11, %xmm6
	shufps	$221, %xmm9, %xmm10             # xmm10 = xmm10[1,3],xmm9[1,3]
	orps	%xmm6, %xmm10
	andnps	%xmm10, %xmm7
	andps	%xmm3, %xmm7
	packuswb	%xmm7, %xmm7
	packuswb	%xmm7, %xmm7
	movd	%xmm7, (%rdx,%r9)
	addq	$4, %r9
	cmpq	%r9, %rcx
	jne	.LBB0_4

In clang-16 result loop:

.LBB0_7:                                # =>This Inner Loop Header: Depth=1
	movl	(%rdi,%r10,4), %eax
	xorl	%edx, %edx
	divl	(%rsi,%r10,4)
	cmpl	%ecx, %eax
	sete	(%r9,%r10)
	movl	4(%rdi,%r10,4), %eax
	xorl	%edx, %edx
	divl	4(%rsi,%r10,4)
	cmpl	%ecx, %eax
	sete	1(%r9,%r10)
	addq	$2, %r10
	cmpq	%r10, %r11
	jne	.LBB0_7

llvm/test/Transforms/InstCombine/unsigned-mul-overflow-check-via-udiv-of-allones.ll

111

I am not sure if I need to add vector tests here, as I just regenerated output here.

[kitaisreal]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4370

Added links to the summary.

[kitaisreal]

Updated implementation.

[goldstein.w.n]

llvm/test/Transforms/InstCombine/icmp-udiv.ll

99

For equals and not equals it seems that it provides slightly more instructions, but I still think that if we can avoid division it is worth it.
I think it is okay to move this optimization in Backend, althought I am afraid that if we will not keep this optimization in IR, such construction will not be autovectorized.
For such code:

void test(uint32_t * __restrict x, uint32_t * __restrict y, uint8_t * result, uint32_t z, size_t size) {
    for (size_t i = 0; i < size; ++i) {
        result[i] = x[i] / y[i] == z;
    }
}

Result vectorized loop after this patch:

.LBB0_4:                                # %vector.body
                                        # =>This Inner Loop Header: Depth=1
	movdqu	(%rdi,%r9,4), %xmm4
	movdqu	(%rsi,%r9,4), %xmm9
	movdqa	%xmm4, %xmm5
	punpckldq	%xmm1, %xmm5            # xmm5 = xmm5[0],xmm1[0],xmm5[1],xmm1[1]
	punpckhdq	%xmm1, %xmm4            # xmm4 = xmm4[2],xmm1[2],xmm4[3],xmm1[3]
	movdqa	%xmm9, %xmm10
	punpckhdq	%xmm1, %xmm10           # xmm10 = xmm10[2],xmm1[2],xmm10[3],xmm1[3]
	punpckldq	%xmm1, %xmm9            # xmm9 = xmm9[0],xmm1[0],xmm9[1],xmm1[1]
	movdqa	%xmm0, %xmm6
	pmuludq	%xmm9, %xmm6
	movdqa	%xmm0, %xmm8
	pmuludq	%xmm10, %xmm8
	pxor	%xmm2, %xmm4
	movdqa	%xmm8, %xmm11
	pxor	%xmm2, %xmm11
	movdqa	%xmm11, %xmm12
	pcmpgtd	%xmm4, %xmm12
	pxor	%xmm2, %xmm5
	movdqa	%xmm6, %xmm13
	pxor	%xmm2, %xmm13
	movdqa	%xmm13, %xmm7
	pcmpgtd	%xmm5, %xmm7
	movdqa	%xmm7, %xmm14
	shufps	$136, %xmm12, %xmm14            # xmm14 = xmm14[0,2],xmm12[0,2]
	pcmpeqd	%xmm4, %xmm11
	pcmpeqd	%xmm5, %xmm13
	shufps	$221, %xmm11, %xmm13            # xmm13 = xmm13[1,3],xmm11[1,3]
	andps	%xmm14, %xmm13
	shufps	$221, %xmm12, %xmm7             # xmm7 = xmm7[1,3],xmm12[1,3]
	orps	%xmm13, %xmm7
	paddq	%xmm9, %xmm6
	paddq	%xmm10, %xmm8
	pxor	%xmm2, %xmm8
	movdqa	%xmm8, %xmm9
	pcmpgtd	%xmm4, %xmm9
	pxor	%xmm2, %xmm6
	movdqa	%xmm6, %xmm10
	pcmpgtd	%xmm5, %xmm10
	movdqa	%xmm10, %xmm11
	shufps	$136, %xmm9, %xmm11             # xmm11 = xmm11[0,2],xmm9[0,2]
	pcmpeqd	%xmm4, %xmm8
	pcmpeqd	%xmm5, %xmm6
	shufps	$221, %xmm8, %xmm6              # xmm6 = xmm6[1,3],xmm8[1,3]
	andps	%xmm11, %xmm6
	shufps	$221, %xmm9, %xmm10             # xmm10 = xmm10[1,3],xmm9[1,3]
	orps	%xmm6, %xmm10
	andnps	%xmm10, %xmm7
	andps	%xmm3, %xmm7
	packuswb	%xmm7, %xmm7
	packuswb	%xmm7, %xmm7
	movd	%xmm7, (%rdx,%r9)
	addq	$4, %r9
	cmpq	%r9, %rcx
	jne	.LBB0_4

In clang-16 result loop:

.LBB0_7:                                # =>This Inner Loop Header: Depth=1
	movl	(%rdi,%r10,4), %eax
	xorl	%edx, %edx
	divl	(%rsi,%r10,4)
	cmpl	%ecx, %eax
	sete	(%r9,%r10)
	movl	4(%rdi,%r10,4), %eax
	xorl	%edx, %edx
	divl	4(%rsi,%r10,4)
	cmpl	%ecx, %eax
	sete	1(%r9,%r10)
	addq	$2, %r10
	cmpq	%r10, %r11
	jne	.LBB0_7

The concern is not whether this can get better codegen, its whether it belongs in InstCombine or in something like the DAGCombiner. If the argument for this is "it gets better codegen" it probably belongs in DAGCombiner. If the argument is "it makes the IR simpler" it probably belongs in InstCombine.

Is there a reason not to do this in DAGCombiner instead?

[kitaisreal]

llvm/test/Transforms/InstCombine/icmp-udiv.ll

99

I am not very familiar with CodeGen part where DAGCombiner is placed, but I am afraid that if I move this optimization into it, construction like

for (size_t i = 0; i < size; ++i) {
    result[i] = x[i] / y[i] == z;
}

will not be autovectorized, because this optimization is part of IR transformations. Please correct me if I am wrong.

[nikic]

llvm/test/Transforms/InstCombine/icmp-udiv.ll

99

That is correct, but you lose other things in turn. For example, consider what happens if you apply this transform, and then the divisor becomes a known constant after inlining. For a divisor like 4 which can be converted into a shift, we'll go from (the optimal)

define i1 @src(i8 %x, i8 %z) {
  %div1 = lshr i8 %x, 2
  %cmp = icmp eq i8 %div1, %z
  ret i1 %cmp
}

to something like

define i1 @tgt(i8 %x, i8 %z) {
  %x.ext = zext i8 %x to i16
  %z.ext = zext i8 %z to i16
  %mul = shl nuw nsw i16 %z.ext, 2
  %cmp1 = icmp ule i16 %mul, %x.ext
  %add = add nuw nsw i16 %mul, 4
  %cmp2 = icmp ugt i16 %add, %x.ext
  %and = and i1 %cmp1, %cmp2
  ret i1 %and
}

This pattern can in theory be reduced back to the efficient original form, but we certainly don't do that currently.

While udiv is a bit borderline, doing these kinds of expansion transforms in the middle-end is usually a bad idea.

[goldstein.w.n]

llvm/test/Transforms/InstCombine/icmp-udiv.ll

99

I am not very familiar with CodeGen part where DAGCombiner is placed, but I am afraid that if I move this optimization into it, construction like

To see an example of what a port looks like I recently had to do the same here:
D154678 (InstCombine) was ported to D154805 (DAGCombiner). Admittedly DAGCombiner is not as nice to code in (no match(...) support), but its not anything unintuitive.

for (size_t i = 0; i < size; ++i) {
    result[i] = x[i] / y[i] == z;
}

will not be autovectorized, because this optimization is part of IR transformations. Please correct me if I am wrong.

Does udiv in that type of loop not already auto-vectorize?

[kitaisreal]

llvm/test/Transforms/InstCombine/icmp-udiv.ll

99

Thanks. I will try to move this into DAGCombiner.
Such loop is not autovectorized by clang or gcc https://godbolt.org/z/EMneWbjev.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

foldShiftIntoShiftInAnotherHandOfAndInICmp(ICmpInst &I, const SimplifyQuery SQ,
   Value *T0 = XShiftOpcode == Instruction::BinaryOps::LShr
                   ? Builder.CreateLShr(X, NewShAmt)
                   : Builder.CreateShl(X, NewShAmt);
   Value *T1 = Builder.CreateAnd(T0, Y);
   return Builder.CreateICmp(I.getPredicate(), T1,
                             Constant::getNullValue(WidestTy));
 }
 
+/// Fold icmp (udiv X, Y), Z.
+static Value *foldICmpUDiv(ICmpInst &Cmp, BinaryOperator *UDiv,
+                           InstCombiner::BuilderTy &Builder) {
+  if (!Cmp.isUnsigned() && !Cmp.isEquality())
+    return nullptr;
+
+  if (!UDiv->hasOneUse())
+    return nullptr;
+
+  Type *ExtendedType = UDiv->getType()->getExtendedType();
+  unsigned IntegerBitWidth = 0;
+
+  if (ExtendedType->isVectorTy()) {
+    IntegerBitWidth =
+        cast<VectorType>(ExtendedType)->getElementType()->getIntegerBitWidth();
+  } else {
+    IntegerBitWidth = ExtendedType->getIntegerBitWidth();
+  }
+
+  if (IntegerBitWidth > 128)
+    return nullptr;
+
+  // 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
+  //
+
+  Value *X = Builder.CreateZExt(UDiv->getOperand(0), ExtendedType);
+  Value *Y = Builder.CreateZExt(UDiv->getOperand(1), ExtendedType);
+  Value *Z = Builder.CreateZExt(Cmp.getOperand(1), ExtendedType);
+
+  Value *ConstantOne = ConstantVector::getIntegerValue(
+      ExtendedType, APInt::getOneBitSet(IntegerBitWidth, 0));
+
+  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:
+    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:
+    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
 /// to
 ///   @llvm.?mul.with.overflow(x, y) plus extraction of overflow bit
 /// Note that the comparison is commutative, while inverted (u>=, ==) predicate
 /// will mean that we are looking for the opposite answer.
 Value *InstCombinerImpl::foldMultiplicationOverflowCheck(ICmpInst &I) {
Instruction *InstCombinerImpl::visitICmpInst(ICmpInst &I) {
   //        unnecessary. It may also be moot if we canonicalize to min/max
   //        intrinsics.
   if (Instruction *Res = foldICmpBinOp(I, Q))
     return Res;
 
   if (Instruction *Res = foldICmpInstWithConstant(I))
     return Res;
 
+  BinaryOperator *BO0 = dyn_cast<BinaryOperator>(Op0);
+  if (BO0 && BO0->getOpcode() == Instruction::UDiv) {
+    if (Value *V = foldICmpUDiv(I, BO0, 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))
     return New;
 
   if (Instruction *Res = foldICmpInstWithConstantNotInt(I))
     return Res;
 

llvm/test/Transforms/InstCombine/icmp-add.ll

;
   %add1 = add i32 %b, %a
   %add2 = add i32 %add1, -1
   %cmp = icmp ult i32 %add2, %a
   ret i1 %cmp
 }
 
 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
   ret i1 %cmp
 }
 
 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
   ret i1 %cmp
 }
 
 define i1 @icmp_add_add_C_comm2_wrong_pred(i32 %X, i32 %b) {
 ; CHECK-LABEL: @icmp_add_add_C_comm2_wrong_pred(
 ; CHECK-NEXT:    [[A:%.*]] = udiv i32 42, [[X:%.*]]
 ; CHECK-NEXT:    [[ADD1:%.*]] = add i32 [[A]], [[B:%.*]]
 ; CHECK-NEXT:    [[ADD2:%.*]] = add i32 [[ADD1]], -1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[A]], [[ADD2]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %a = udiv i32 42, %X ; thwart complexity-based canonicalization
   %add1 = add i32 %a, %b
   %add2 = add i32 %add1, -1
   %cmp = icmp ult i32 %a, %add2
   ret i1 %cmp
 }
 
 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
   %add1 = add i32 %b, %a
   %add2 = add i32 %add1, -1
   %cmp = icmp ugt i32 %a, %add2
   ret i1 %cmp
 }

llvm/test/Transforms/InstCombine/icmp-div-constant.ll

;
   %r = icmp ne i8 %d, 128
   ret i1 %r
 }
 
 ; negative test - must have negative compare constant
 
 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
   %r = icmp eq i8 %d, 127
   ret i1 %r
 }
 
 ; negative test - must be equality predicate

llvm/test/Transforms/InstCombine/icmp-ext-ext.ll

;
   %n = lshr i8 %y, 6
   %b = zext i8 %n to i32
   %c = icmp ult i32 %a, %b
   ret i1 %c
 }
 
 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
   %n = udiv i8 %y, 6
   %b = zext i8 %n to i32
   %c = icmp ne i32 %a, %b
   ret i1 %c
 }

llvm/test/Transforms/InstCombine/icmp-select.ll

;
   %cmp1 = icmp eq i8 %x, 0
   %sel = select i1 %cmp1, i8 %z, i8 %y
   %cmp2 = icmp eq i8 %sel, %z
   ret i1 %cmp2
 }
 
 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
   ret i1 %cmp2
 }
 
 define i1 @icmp_select_var_select(i8 %x, i8 %y, i1 %c) {
 ; CHECK-LABEL: @icmp_select_var_select(

llvm/test/Transforms/InstCombine/icmp-udiv.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 ; Fold icmp (udiv X, Y), Z.
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 ; negative test - extended integer type bit width is greater than 128
 
 define i1 @udiv_icmp_eq_i128_fail(i128 %x, i128 %y, i128 %z) {
 ; CHECK-LABEL: @udiv_icmp_eq_i128_fail(
 ; CHECK-NEXT:    [[TMP1:%.*]] = udiv i128 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i128 [[TMP1]], [[Z:%.*]]
 ; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %1 = udiv i128 %x, %y
   %2 = icmp eq i128 %1, %z
   ret i1 %2
 }
 
 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
   ret <2 x i1> %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 ; negative test - extended integer type bit width is greater than 128
 
 define i1 @udiv_icmp_ne_i128_fail(i128 %x, i128 %y, i128 %z) {
 ; CHECK-LABEL: @udiv_icmp_ne_i128_fail(
 ; CHECK-NEXT:    [[TMP1:%.*]] = udiv i128 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i128 [[TMP1]], [[Z:%.*]]
 ; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %1 = udiv i128 %x, %y
   %2 = icmp ne i128 %1, %z
   ret i1 %2
 }
 
 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
   ret <2 x i1> %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 ; negative test - extended integer type bit width is greater than 128
 
 define i1 @udiv_icmp_ugt_i128_fail(i128 %x, i128 %y, i128 %z) {
 ; CHECK-LABEL: @udiv_icmp_ugt_i128_fail(
 ; CHECK-NEXT:    [[TMP1:%.*]] = udiv i128 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp ugt i128 [[TMP1]], [[Z:%.*]]
 ; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %1 = udiv i128 %x, %y
   %2 = icmp ugt i128 %1, %z
   ret i1 %2
 }
 
 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
   ret <2 x i1> %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 ; negative test - extended integer type bit width is greater than 128
 
 define i1 @udiv_icmp_uge_i128_fail(i128 %x, i128 %y, i128 %z) {
 ; CHECK-LABEL: @udiv_icmp_uge_i128_fail(
 ; CHECK-NEXT:    [[TMP1:%.*]] = udiv i128 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp uge i128 [[TMP1]], [[Z:%.*]]
 ; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %1 = udiv i128 %x, %y
   %2 = icmp uge i128 %1, %z
   ret i1 %2
 }
 
 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
   ret <2 x i1> %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 ; negative test - extended integer type bit width is greater than 128
 
 define i1 @udiv_icmp_ult_i128_fail(i128 %x, i128 %y, i128 %z) {
 ; CHECK-LABEL: @udiv_icmp_ult_i128_fail(
 ; CHECK-NEXT:    [[TMP1:%.*]] = udiv i128 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i128 [[TMP1]], [[Z:%.*]]
 ; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %1 = udiv i128 %x, %y
   %2 = icmp ult i128 %1, %z
   ret i1 %2
 }
 
 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
   ret <2 x i1> %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 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
   ret i1 %2
 }
 
 ; negative test - extended integer type bit width is greater than 128
 
 define i1 @udiv_icmp_ule_i128_fail(i128 %x, i128 %y, i128 %z) {
 ; CHECK-LABEL: @udiv_icmp_ule_i128_fail(
 ; CHECK-NEXT:    [[TMP1:%.*]] = udiv i128 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp ule i128 [[TMP1]], [[Z:%.*]]
 ; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %1 = udiv i128 %x, %y
   %2 = icmp ule i128 %1, %z
   ret i1 %2
 }
 
 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
   ret <2 x i1> %2
 }
 
 ; negative test - multiple usage
 

llvm/test/Transforms/InstCombine/icmp.ll

;
   %c = icmp ugt i32 %lhs, %rhs
   ret i1 %c
 }
 
 ; PR36969 - https://bugs.llvm.org/show_bug.cgi?id=36969
 
 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
 }
 
 ; Swap operands and predicate. Try a vector type to verify that works too.
 
 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
 }
 
 ; X - Y > X -> 0 > Y if there is no overflow.
 define i1 @test33(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test33(

llvm/test/Transforms/InstCombine/unsigned-mul-lack-of-overflow-check-via-mul-udiv.ll

;
   ret i1 %r
 }
 
 ; Negative tests
 
 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
   %t1 = udiv i8 %t0, %x1
   %r = icmp eq i8 %t1, %y
   ret i1 %r
 }
 
 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
   %t1 = udiv i8 %t0, %x
   %r = icmp eq i8 %t1, %y1
   ret i1 %r
 }
 
 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
   %t1 = udiv i8 %t0, %x
   %r = icmp ult i8 %t1, %y
   ret i1 %r
 }

llvm/test/Transforms/InstCombine/unsigned-mul-lack-of-overflow-check-via-udiv-of-allones.ll

;
   %t0 = udiv i8 -1, %x
   call void @use8(i8 %t0)
   %r = icmp uge i8 %t0, %y
   ret i1 %r
 }
 
 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
   %r = icmp uge i8 %t0, %y
   ret i1 %r
 }
 
 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
   %r = icmp ule i8 %t0, %y ; not uge
   ret i1 %r
 }
 
 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
   %r = icmp ugt i8 %t0, %y ; not uge
   ret i1 %r
 }

llvm/test/Transforms/InstCombine/unsigned-mul-overflow-check-via-mul-udiv.ll

;
   ret i1 %r
 }
 
 ; Negative tests
 
 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
   %t1 = udiv i8 %t0, %x1
   %r = icmp ne i8 %t1, %y
   ret i1 %r
 }
 
 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
   %t1 = udiv i8 %t0, %x
   %r = icmp ne i8 %t1, %y1
   ret i1 %r
 }
 
 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
   %t1 = udiv i8 %t0, %x
   %r = icmp ugt i8 %t1, %y
   ret i1 %r
 }

llvm/test/Transforms/InstCombine/unsigned-mul-overflow-check-via-udiv-of-allones.ll

;
   %t0 = udiv i8 -1, %x
   call void @use8(i8 %t0)
   %r = icmp ult i8 %t0, %y
   ret i1 %r
 }
 
 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
   %r = icmp ult i8 %t0, %y
   ret i1 %r
 }
 
 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
   %r = icmp ule i8 %t0, %y ; not ult
   ret i1 %r
 }
 
 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
   %r = icmp ugt i8 %t0, %y ; not ult
   ret i1 %r
 }