[InstCombine] Fold '((%x * %y) u/ %x) != %y' to '@llvm.umul.with.overflow' + overflow bit extraction

[lebedev.ri]

Summary

((%x * %y) u/ %x) != %y is one of (3?) common ways to check that
some unsigned multiplication (will not) overflow.
Currently, we don't catch it. We could:

$ /repositories/alive2/build-Clang-unknown/alive -root-only ~/llvm-patch1.ll 
Processing /home/lebedevri/llvm-patch1.ll..

----------------------------------------
Name: no overflow
  %o0 = mul i4 %y, %x
  %o1 = udiv i4 %o0, %x
  %r = icmp ne i4 %o1, %y
  ret i1 %r
=>
  %n0 = umul_overflow i4 %x, %y
  %o0 = extractvalue {i4, i1} %n0, 0
  %o1 = udiv %o0, %x
  %r = extractvalue {i4, i1} %n0, 1
  ret %r

Done: 1
Optimization is correct!

----------------------------------------
Name: no overflow
  %o0 = mul i4 %y, %x
  %o1 = udiv i4 %o0, %x
  %r = icmp eq i4 %o1, %y
  ret i1 %r
=>
  %n0 = umul_overflow i4 %x, %y
  %o0 = extractvalue {i4, i1} %n0, 0
  %o1 = udiv %o0, %x
  %n1 = extractvalue {i4, i1} %n0, 1
  %r = xor %n1, -1
  ret i1 %r

Done: 1
Optimization is correct!

[xbolva00]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

3341 ↗

(On Diff #211287)

Instruction *Mul = nullptr;?

3347 ↗

(On Diff #211287)

..remove

3378 ↗

(On Diff #211287)

Also add multi use check?

bool HasMultiUseMul = Mul && !Mul->hasOneUse();
if (..)

[lebedev.ri]

NFC, rebase, improve comments.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

3347 ↗

(On Diff #211287)

Why i believe this is the conceptually-wrong solution:
Consider this:

void *data;
bool something = false;
if(some_check(&data, &something))
else if(another_check(&data))
else return;

if(something)
  ...

The problem is that while this may seem ok, we did zero-init something initially after all,
we then did pass it to some_check(), and it may have changed it's value.
Now, if some_check() returned false, we do another_check(),
but there we don't do anything with something.
We might intended to keep whatever we got there from some_check(),
or maybe we did not and simply forgot to re-zero-init it.
And in latter case something is essentially undefined, and we have a bug that won't be fun to debug.

Compare with:

void *data;
bool something; // if we do not init it before using MSAN will catch it.
if(some_check(&data, &something))
else if(another_check(&data))
  something = false; // yay
else return;

if(something) // all certainly good here.
  ...

Does this make sense?

3378 ↗

(On Diff #211287)

If we insert in place of old mul only if mul had extra uses,
then maybe this intrinsic will still be hoisted back into that
other basic block because it's loop-invariant.
Or maybe it we always place insert in place of old mul
it will get sinked into some other only basic block where it's used.

I'm honestly not sure what the best solution here is,
we just don't have enough information to make the final
(the one that won't be altered by later passes) choice here.
Either choice that passes -verify is good.

Consistently placing it in place of the old mul seemed least arbitrary to me.

Maybe others have some other ideas?

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

3378 ↗

(On Diff #211287)

Maybe others have some other ideas?

Err, what i meant to say is, maybe there is some consistent justification that points
to some particular location being the correct one to insert to?

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

3378 ↗

(On Diff #211287)

I don't think it really matters either way, but my preference here would be (for the one-use case) to insert everything together, both because that is the default behavior (what we would do if we were matching for one-use in the first place and had no special handling) and because that makes the condition here and below consistent.

[lebedev.ri]

Insert everything together if no mul/mul was oneuse.

[nikic]

LGTM

[lebedev.ri]

Thank you for the review.

[lebedev.ri]

Rebased, NFC.

llvm/trunk/lib/Transforms/InstCombine/InstCombineCompares.cpp

Value *T0 = XShiftOpcode == Instruction::BinaryOps::LShr
                   : Builder.CreateShl(X, NewShAmt);
   Value *T1 = Builder.CreateAnd(T0, Y);
   return Builder.CreateICmp(I.getPredicate(), T1,
                             Constant::getNullValue(WidestTy));
 }
 
 /// Fold
 ///   (-1 u/ x) u< y
+///   ((x * y) u/ x) != y
 /// to
 ///   @llvm.umul.with.overflow(x, y) plus extraction of overflow bit
-/// Note that the comparison is commutative, while inverted (u>=) predicate
+/// Note that the comparison is commutative, while inverted (u>=, ==) predicate
 /// will mean that we are looking for the opposite answer.
-static Value *
-foldUnsignedMultiplicationOverflowCheck(ICmpInst &I,
-                                        InstCombiner::BuilderTy &Builder) {
+Value *InstCombiner::foldUnsignedMultiplicationOverflowCheck(ICmpInst &I) {
   ICmpInst::Predicate Pred;
   Value *X, *Y;
+  Instruction *Mul;
   bool NeedNegation;
   // Look for: (-1 u/ x) u</u>= y
   if (!I.isEquality() &&
       match(&I, m_c_ICmp(Pred, m_OneUse(m_UDiv(m_AllOnes(), m_Value(X))),
                          m_Value(Y)))) {
+    Mul = nullptr;
     // Canonicalize as-if y was on RHS.
     if (I.getOperand(1) != Y)
       Pred = I.getSwappedPredicate();
 
     // Are we checking that overflow does not happen, or does happen?
     switch (Pred) {
     case ICmpInst::Predicate::ICMP_ULT:
       NeedNegation = false;
       break; // OK
     case ICmpInst::Predicate::ICMP_UGE:
       NeedNegation = true;
       break; // OK
     default:
       return nullptr; // Wrong predicate.
     }
+  } else // Look for: ((x * y) u/ x) !=/== y
+      if (I.isEquality() &&
+          match(&I, m_c_ICmp(Pred, m_Value(Y),
+                             m_OneUse(m_UDiv(m_CombineAnd(m_c_Mul(m_Deferred(Y),
+                                                                  m_Value(X)),
+                                                          m_Instruction(Mul)),
+                                             m_Deferred(X)))))) {
+    NeedNegation = Pred == ICmpInst::Predicate::ICMP_EQ;
   } else
     return nullptr;
 
+  BuilderTy::InsertPointGuard Guard(Builder);
+  // If the pattern included (x * y), we'll want to insert new instructions
+  // right before that original multiplication so that we can replace it.
+  bool MulHadOtherUses = Mul && !Mul->hasOneUse();
+  if (MulHadOtherUses)
+    Builder.SetInsertPoint(Mul);
+
   Function *F = Intrinsic::getDeclaration(
       I.getModule(), Intrinsic::umul_with_overflow, X->getType());
   CallInst *Call = Builder.CreateCall(F, {X, Y}, "umul");
+
+  // If the multiplication was used elsewhere, to ensure that we don't leave
+  // "duplicate" instructions, replace uses of that original multiplication
+  // with the multiplication result from the with.overflow intrinsic.
+  if (MulHadOtherUses)
+    replaceInstUsesWith(*Mul, Builder.CreateExtractValue(Call, 0, "umul.val"));
+
   Value *Res = Builder.CreateExtractValue(Call, 1, "umul.ov");
   if (NeedNegation) // This technically increases instruction count.
     Res = Builder.CreateNot(Res, "umul.not.ov");
 
   return Res;
 }
 
 /// Try to fold icmp (binop), X or icmp X, (binop).
if (BO0) {
     auto BitwiseAnd = m_c_And(m_Value(), LSubOne);
 
     if (match(BO0, BitwiseAnd) && Pred == ICmpInst::ICMP_ULT) {
       auto *Zero = Constant::getNullValue(BO0->getType());
       return new ICmpInst(ICmpInst::ICMP_NE, Op1, Zero);
     }
   }
 
-  if (Value *V = foldUnsignedMultiplicationOverflowCheck(I, Builder))
+  if (Value *V = foldUnsignedMultiplicationOverflowCheck(I))
     return replaceInstUsesWith(I, V);
 
   if (Value *V = foldICmpWithLowBitMaskedVal(I, Builder))
     return replaceInstUsesWith(I, V);
 
   if (Value *V = foldICmpWithTruncSignExtendedVal(I, Builder))
     return replaceInstUsesWith(I, V);
 

llvm/trunk/lib/Transforms/InstCombine/InstCombineInternal.h

private:
   Instruction *foldICmpWithConstant(ICmpInst &Cmp);
   Instruction *foldICmpInstWithConstant(ICmpInst &Cmp);
   Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp);
   Instruction *foldICmpBinOp(ICmpInst &Cmp);
   Instruction *foldICmpEquality(ICmpInst &Cmp);
   Instruction *foldIRemByPowerOfTwoToBitTest(ICmpInst &I);
   Instruction *foldICmpWithZero(ICmpInst &Cmp);
 
+  Value *foldUnsignedMultiplicationOverflowCheck(ICmpInst &Cmp);
+
   Instruction *foldICmpSelectConstant(ICmpInst &Cmp, SelectInst *Select,
                                       ConstantInt *C);
   Instruction *foldICmpTruncConstant(ICmpInst &Cmp, TruncInst *Trunc,
                                      const APInt &C);
   Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And,
                                    const APInt &C);
   Instruction *foldICmpXorConstant(ICmpInst &Cmp, BinaryOperator *Xor,
                                    const APInt &C);

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt %s -instcombine -S | FileCheck %s
 
 ; Fold
 ;   ((%x * %y) u/ %x) == %y
 ; to
 ;   @llvm.umul.with.overflow(%x, %y) + extractvalue + not
 
 define i1 @t0_basic(i8 %x, i8 %y) {
 ; CHECK-LABEL: @t0_basic(
-; CHECK-NEXT:    [[T0:%.*]] = mul i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = udiv i8 [[T0]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[T1]], [[Y]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    [[UMUL:%.*]] = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 [[X:%.*]], i8 [[Y:%.*]])
+; CHECK-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i8, i1 } [[UMUL]], 1
+; CHECK-NEXT:    [[UMUL_NOT_OV:%.*]] = xor i1 [[UMUL_OV]], true
+; CHECK-NEXT:    ret i1 [[UMUL_NOT_OV]]
 ;
   %t0 = mul i8 %x, %y
   %t1 = udiv i8 %t0, %x
   %r = icmp eq i8 %t1, %y
   ret i1 %r
 }
 
 define <2 x i1> @t1_vec(<2 x i8> %x, <2 x i8> %y) {
 ; CHECK-LABEL: @t1_vec(
-; CHECK-NEXT:    [[T0:%.*]] = mul <2 x i8> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = udiv <2 x i8> [[T0]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq <2 x i8> [[T1]], [[Y]]
-; CHECK-NEXT:    ret <2 x i1> [[R]]
+; CHECK-NEXT:    [[UMUL:%.*]] = call { <2 x i8>, <2 x i1> } @llvm.umul.with.overflow.v2i8(<2 x i8> [[X:%.*]], <2 x i8> [[Y:%.*]])
+; CHECK-NEXT:    [[UMUL_OV:%.*]] = extractvalue { <2 x i8>, <2 x i1> } [[UMUL]], 1
+; CHECK-NEXT:    [[UMUL_NOT_OV:%.*]] = xor <2 x i1> [[UMUL_OV]], <i1 true, i1 true>
+; CHECK-NEXT:    ret <2 x i1> [[UMUL_NOT_OV]]
 ;
   %t0 = mul <2 x i8> %x, %y
   %t1 = udiv <2 x i8> %t0, %x
   %r = icmp eq <2 x i8> %t1, %y
   ret <2 x i1> %r
 }
 
 declare i8 @gen8()
 
 define i1 @t2_commutative(i8 %x) {
 ; CHECK-LABEL: @t2_commutative(
 ; CHECK-NEXT:    [[Y:%.*]] = call i8 @gen8()
-; CHECK-NEXT:    [[T0:%.*]] = mul i8 [[Y]], [[X:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = udiv i8 [[T0]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[T1]], [[Y]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    [[UMUL:%.*]] = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 [[X:%.*]], i8 [[Y]])
+; CHECK-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i8, i1 } [[UMUL]], 1
+; CHECK-NEXT:    [[UMUL_NOT_OV:%.*]] = xor i1 [[UMUL_OV]], true
+; CHECK-NEXT:    ret i1 [[UMUL_NOT_OV]]
 ;
   %y = call i8 @gen8()
   %t0 = mul i8 %y, %x ; swapped
   %t1 = udiv i8 %t0, %x
   %r = icmp eq i8 %t1, %y
   ret i1 %r
 }
 
 define i1 @t3_commutative(i8 %x) {
 ; CHECK-LABEL: @t3_commutative(
 ; CHECK-NEXT:    [[Y:%.*]] = call i8 @gen8()
-; CHECK-NEXT:    [[T0:%.*]] = mul i8 [[Y]], [[X:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = udiv i8 [[T0]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[T1]], [[Y]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    [[UMUL:%.*]] = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 [[X:%.*]], i8 [[Y]])
+; CHECK-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i8, i1 } [[UMUL]], 1
+; CHECK-NEXT:    [[UMUL_NOT_OV:%.*]] = xor i1 [[UMUL_OV]], true
+; CHECK-NEXT:    ret i1 [[UMUL_NOT_OV]]
 ;
   %y = call i8 @gen8()
   %t0 = mul i8 %y, %x ; swapped
   %t1 = udiv i8 %t0, %x
   %r = icmp eq i8 %t1, %y
   ret i1 %r
 }
 
 define i1 @t4_commutative(i8 %x) {
 ; CHECK-LABEL: @t4_commutative(
 ; CHECK-NEXT:    [[Y:%.*]] = call i8 @gen8()
-; CHECK-NEXT:    [[T0:%.*]] = mul i8 [[Y]], [[X:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = udiv i8 [[T0]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[Y]], [[T1]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    [[UMUL:%.*]] = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 [[X:%.*]], i8 [[Y]])
+; CHECK-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i8, i1 } [[UMUL]], 1
+; CHECK-NEXT:    [[UMUL_NOT_OV:%.*]] = xor i1 [[UMUL_OV]], true
+; CHECK-NEXT:    ret i1 [[UMUL_NOT_OV]]
 ;
   %y = call i8 @gen8()
   %t0 = mul i8 %y, %x ; swapped
   %t1 = udiv i8 %t0, %x
   %r = icmp eq i8 %y, %t1 ; swapped
   ret i1 %r
 }
 
 ; Extra-use tests
 
 declare void @use8(i8)
 
 define i1 @t5_extrause0(i8 %x, i8 %y) {
 ; CHECK-LABEL: @t5_extrause0(
-; CHECK-NEXT:    [[T0:%.*]] = mul i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    call void @use8(i8 [[T0]])
-; CHECK-NEXT:    [[T1:%.*]] = udiv i8 [[T0]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[T1]], [[Y]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    [[UMUL:%.*]] = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 [[X:%.*]], i8 [[Y:%.*]])
+; CHECK-NEXT:    [[UMUL_VAL:%.*]] = extractvalue { i8, i1 } [[UMUL]], 0
+; CHECK-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i8, i1 } [[UMUL]], 1
+; CHECK-NEXT:    [[UMUL_NOT_OV:%.*]] = xor i1 [[UMUL_OV]], true
+; CHECK-NEXT:    call void @use8(i8 [[UMUL_VAL]])
+; CHECK-NEXT:    ret i1 [[UMUL_NOT_OV]]
 ;
   %t0 = mul i8 %x, %y
   call void @use8(i8 %t0)
   %t1 = udiv i8 %t0, %x
   %r = icmp eq i8 %t1, %y
   ret i1 %r
 }
 

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt %s -instcombine -S | FileCheck %s
 
 ; Fold
 ;   ((%x * %y) u/ %x) != %y
 ; to
 ;   @llvm.umul.with.overflow(%x, %y) + extractvalue
 
 define i1 @t0_basic(i8 %x, i8 %y) {
 ; CHECK-LABEL: @t0_basic(
-; CHECK-NEXT:    [[T0:%.*]] = mul i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = udiv i8 [[T0]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[T1]], [[Y]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    [[UMUL:%.*]] = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 [[X:%.*]], i8 [[Y:%.*]])
+; CHECK-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i8, i1 } [[UMUL]], 1
+; CHECK-NEXT:    ret i1 [[UMUL_OV]]
 ;
   %t0 = mul i8 %x, %y
   %t1 = udiv i8 %t0, %x
   %r = icmp ne i8 %t1, %y
   ret i1 %r
 }
 
 define <2 x i1> @t1_vec(<2 x i8> %x, <2 x i8> %y) {
 ; CHECK-LABEL: @t1_vec(
-; CHECK-NEXT:    [[T0:%.*]] = mul <2 x i8> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = udiv <2 x i8> [[T0]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ne <2 x i8> [[T1]], [[Y]]
-; CHECK-NEXT:    ret <2 x i1> [[R]]
+; CHECK-NEXT:    [[UMUL:%.*]] = call { <2 x i8>, <2 x i1> } @llvm.umul.with.overflow.v2i8(<2 x i8> [[X:%.*]], <2 x i8> [[Y:%.*]])
+; CHECK-NEXT:    [[UMUL_OV:%.*]] = extractvalue { <2 x i8>, <2 x i1> } [[UMUL]], 1
+; CHECK-NEXT:    ret <2 x i1> [[UMUL_OV]]
 ;
   %t0 = mul <2 x i8> %x, %y
   %t1 = udiv <2 x i8> %t0, %x
   %r = icmp ne <2 x i8> %t1, %y
   ret <2 x i1> %r
 }
 
 declare i8 @gen8()
 
 define i1 @t2_commutative(i8 %x) {
 ; CHECK-LABEL: @t2_commutative(
 ; CHECK-NEXT:    [[Y:%.*]] = call i8 @gen8()
-; CHECK-NEXT:    [[T0:%.*]] = mul i8 [[Y]], [[X:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = udiv i8 [[T0]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[T1]], [[Y]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    [[UMUL:%.*]] = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 [[X:%.*]], i8 [[Y]])
+; CHECK-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i8, i1 } [[UMUL]], 1
+; CHECK-NEXT:    ret i1 [[UMUL_OV]]
 ;
   %y = call i8 @gen8()
   %t0 = mul i8 %y, %x ; swapped
   %t1 = udiv i8 %t0, %x
   %r = icmp ne i8 %t1, %y
   ret i1 %r
 }
 
 define i1 @t3_commutative(i8 %x) {
 ; CHECK-LABEL: @t3_commutative(
 ; CHECK-NEXT:    [[Y:%.*]] = call i8 @gen8()
-; CHECK-NEXT:    [[T0:%.*]] = mul i8 [[Y]], [[X:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = udiv i8 [[T0]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[T1]], [[Y]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    [[UMUL:%.*]] = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 [[X:%.*]], i8 [[Y]])
+; CHECK-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i8, i1 } [[UMUL]], 1
+; CHECK-NEXT:    ret i1 [[UMUL_OV]]
 ;
   %y = call i8 @gen8()
   %t0 = mul i8 %y, %x ; swapped
   %t1 = udiv i8 %t0, %x
   %r = icmp ne i8 %t1, %y
   ret i1 %r
 }
 
 define i1 @t4_commutative(i8 %x) {
 ; CHECK-LABEL: @t4_commutative(
 ; CHECK-NEXT:    [[Y:%.*]] = call i8 @gen8()
-; CHECK-NEXT:    [[T0:%.*]] = mul i8 [[Y]], [[X:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = udiv i8 [[T0]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[Y]], [[T1]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    [[UMUL:%.*]] = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 [[X:%.*]], i8 [[Y]])
+; CHECK-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i8, i1 } [[UMUL]], 1
+; CHECK-NEXT:    ret i1 [[UMUL_OV]]
 ;
   %y = call i8 @gen8()
   %t0 = mul i8 %y, %x ; swapped
   %t1 = udiv i8 %t0, %x
   %r = icmp ne i8 %y, %t1 ; swapped
   ret i1 %r
 }
 
 ; Extra-use tests
 
 declare void @use8(i8)
 
 define i1 @t5_extrause0(i8 %x, i8 %y) {
 ; CHECK-LABEL: @t5_extrause0(
-; CHECK-NEXT:    [[T0:%.*]] = mul i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    call void @use8(i8 [[T0]])
-; CHECK-NEXT:    [[T1:%.*]] = udiv i8 [[T0]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[T1]], [[Y]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    [[UMUL:%.*]] = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 [[X:%.*]], i8 [[Y:%.*]])
+; CHECK-NEXT:    [[UMUL_VAL:%.*]] = extractvalue { i8, i1 } [[UMUL]], 0
+; CHECK-NEXT:    [[UMUL_OV:%.*]] = extractvalue { i8, i1 } [[UMUL]], 1
+; CHECK-NEXT:    call void @use8(i8 [[UMUL_VAL]])
+; CHECK-NEXT:    ret i1 [[UMUL_OV]]
 ;
   %t0 = mul i8 %x, %y
   call void @use8(i8 %t0)
   %t1 = udiv i8 %t0, %x
   %r = icmp ne i8 %t1, %y
   ret i1 %r
 }