[InstCombine] Simplify a umul overflow check to a != 0 && b != 0.

[fhahn]

Summary

This patch adds a simplification if an OR weakens the overflow condition
for umul.with.overflow by treating any non-zero result as overflow. In that
case, we overflow if both umul.with.overflow operands are != 0, as in that
case the result can only be 0, iff the multiplication overflows.

Code like this is generated by code using __builtin_mul_overflow with
negative integer constants, e.g.

bool test(unsigned long long v, unsigned long long *res) {
  return __builtin_mul_overflow(v, -4775807LL, res);
}

This simplification is very specific and I am not sure if visitOr is the
best place for it. Any other suggestions?

----------------------------------------
Name: D74141
  %res = umul_overflow {i8, i1} %a, %b
  %mul = extractvalue {i8, i1} %res, 0
  %overflow = extractvalue {i8, i1} %res, 1
  %cmp = icmp ne %mul, 0
  %ret = or i1 %overflow, %cmp
  ret i1 %ret
=>
  %t0 = icmp ne i8 %a, 0
  %t1 = icmp ne i8 %b, 0
  %ret = and i1 %t0, %t1
  ret i1 %ret
  %res = umul_overflow {i8, i1} %a, %b
  %mul = extractvalue {i8, i1} %res, 0
  %cmp = icmp ne %mul, 0
  %overflow = extractvalue {i8, i1} %res, 1

Done: 1
Optimization is correct!

[nikic]

Code like this is generated by code using __builtin_mul_overflow with negative integer constants

I'm missing something here, why does clang generate this kind of code? I would have thought that __builtin_mul_overflow maps pretty directly the intrinsic.

[fhahn]

In D74141#1864447, @nikic wrote:

Code like this is generated by code using __builtin_mul_overflow with negative integer constants

I'm missing something here, why does clang generate this kind of code? I would have thought that __builtin_mul_overflow maps pretty directly the intrinsic.

I am not entirely sure, but I guess the result type being unsigned forces umul_with_overflow, which treats both operands as unsigned. But if the integer operand is negative, __builtin_mul_overflow has to return true, so Clang needs to add extra checks for that. Clang could try to be a bit better with generating code here, but we would miss out on cases where we can prove that the integer operand is always negative in the middle end.

[Gerolf]

+ Duncan, Michae for clang.
+ Amara, David for another opinion. Seems straight forward & LGTM.

-Gerolf

[fhahn]

@dexonsmith, @Bigcheese please let me know if you think that this would be better/easier to do at the Clang codegen level.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2726–2743

Consider doing the following instead:

// Check if the OR weakens the overflow condition for umul.with.overflow by
// treating any non-zero result as overflow. In that case, we overflow if both
// umul.with.overflow operands are != 0, as in that case the result can only
// be 0, iff the multiplication overflows.
CmpInst::Predicate Pred;
Value *MulWithOv;
if (match(&I,
          m_c_Or(m_ICmp(Pred, m_OneUse(m_ExtractValue<0>(m_Value(MulWithOv))),
                        m_ZeroInt()),
                 m_OneUse(m_ExtractValue<1>(m_Deferred(MulWithOv))))) &&
    Pred == CmpInst::ICMP_NE) {
  Value *A, *B;
  if (match(MulWithOv, m_Intrinsic<Intrinsic::umul_with_overflow>(
                           m_Value(A), m_Value(B))))
    return BinaryOperator::CreateAnd(
        Builder.CreateICmpNE(A, ConstantInt::get(A->getType(), 0)),
        Builder.CreateICmpNE(A, ConstantInt::get(B->getType(), 0)));
}

llvm/test/Transforms/InstCombine/umul-signed.ll

23

There shouldn't be any -4775807 here, please replace it with %b

73

Please add the same test for %mul, and %res

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2726–2743

Also, use Builder.CreateIsNotNull()

[fhahn]

Address comments, thanks!

[fhahn]

(re-adding dropped reviewers)

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2726–2743

Nice, m_c_Or and m_Deferred are very helpful!

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2726–2743

Please adjust one-use checks as they were in the snippet,
both operands of or must be single-use, and we don't care if the intrinsic goes away or not.

[fhahn]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2726–2743

Please adjust one-use checks as they were in the snippet, both operands of or must be single-use

Do you mean both extractvalues? I am not sure, why do we need to restrict the number of uses for the multiplication result?

and we don't care if the intrinsic goes away or not.

Will this still be profitable if the simplification does not result in the umul.with.overflow call to go away?

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2726–2743

Actually wait, i see where this is going.
So, we need to produce 3 instructions (&, !=0, !=0),
which means that we need to be sure that we eliminate two instructions.
The input pattern is

%res = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 %a, i64 %b)
%overflow = extractvalue { i64, i1 } %res, 1
%mul = extractvalue { i64, i1 } %res, 0
%cmp  = icmp ne i64 %mul, 0
%overflow.1 = or i1 %overflow, %cmp

%overflow.1 is free to replace, and we need two extras.
They must be it's operands.

• If the %overflow is one-use, then only the %mul result of %res is used, which guarantees that %mul&%res will be combined into a simple mul instruction, thus getting rid of the %mul instruction.
• Even if %mul is one-use, %overflow might not be (if it is, see above), so we don't gain anything here.

TLDR: we only need a single use check, on %overflow = extractvalue { i64, i1 } %res, 1.
%mul = extractvalue { i64, i1 } %res, 0 is either also one-use and will go away,
or it will get folded into %res, either way we end up not increasing instruction count.

2741

TLDR: this check shouldn't be here.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2726–2743

Ah, i forgot about %cmp.

• if %cmp is one-use and %mul is also one-use we also can transform. (if %mul isn't one-use %overflow would need to be, but then see above)

[fhahn]

Remove UMulWithOv->hasNUses(2) as suggested @lebedev.ri.

[fhahn]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2741

I've removed the check and there's a test case (@test3_multiple_res_users).

In that case we end up replacing extract + icmp + or with icmp + icmp + or. Not sure if that will be better in the end, but at least it shouldn't end up worse.

[fhahn]

Match m_oneuse(m_extract<1>) || m_oneuse(m_ICmp(Pred, m_oneuse(m_ExtractValue<0>)) as suggested.

I'm not sure if there's a nicer way to do that, e.g. binding parts of a pattern to a new name, so we can do the use checks later?

[fhahn]

use m_CombineAnd as suggested by @lebedev.ri .

[lebedev.ri]

Thanks, this LGTM.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (match(&I, m_c_Or(m_OneUse(m_AShr(m_NSWSub(m_Value(Y), m_Value(X)),
                                 X);
     }
   }
 
   if (Instruction *V =
           canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(I))
     return V;
 
+  CmpInst::Predicate Pred;
+  Value *UMulWithOv;
+  // Check if the OR weakens the overflow condition for umul.with.overflow by
+  // treating any non-zero result as overflow. In that case, we overflow if both
+  // umul.with.overflow operands are != 0, as in that case the result can only
+  // be 0, iff the multiplication overflows. This transformation is limited to
+  // cases where the multiplication and overflow results are extracted exactly
+  // once and the overflow check is used exactly once. This guarantees that the
+  // uses of the check are eliminated, which in turns allows elimination of the
+  // umul.with.overflow call later on.
+  if (match(&I, m_c_Or(m_OneUse(m_ExtractValue<1>(m_Value(UMulWithOv))),
+                       m_ICmp(Pred, m_ExtractValue<0>(m_Deferred(UMulWithOv)),
+                              m_ZeroInt()))) &&
+      Pred == CmpInst::ICMP_NE) {
+    Value *A, *B;
+    if (UMulWithOv->hasNUses(2) &&
+        match(UMulWithOv, m_Intrinsic<Intrinsic::umul_with_overflow>(
+                              m_Value(A), m_Value(B))))
+
+      return BinaryOperator::CreateAnd(Builder.CreateIsNotNull(A),
+                                       Builder.CreateIsNotNull(B));
+  }
+
   return nullptr;
 }
 
 /// A ^ B can be specified using other logic ops in a variety of patterns. We
 /// can fold these early and efficiently by morphing an existing instruction.
 static Instruction *foldXorToXor(BinaryOperator &I,
                                  InstCombiner::BuilderTy &Builder) {
   assert(I.getOpcode() == Instruction::Xor);

llvm/test/Transforms/InstCombine/umul-signed.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -instcombine -S %s | FileCheck %s
 
 ; Check that we simplify llvm.umul.with.overflow, if the overflow check is
 ; weakened by or (icmp ne %res, 0) %overflow. This is generated by code using
 ; __builtin_mul_overflow with negative integer constants, e.g.
 
 ;   bool test(unsigned long long v, unsigned long long *res) {
 ;     return __builtin_mul_overflow(v, -4775807LL, res);
 ;   }
 
 declare { i64, i1 } @llvm.umul.with.overflow.i64(i64, i64) #0
 
 define i1 @test1(i64 %a, i64 %b, i64* %ptr) {
 ; CHECK-LABEL: @test1(
-; CHECK-NEXT:    [[RES:%.*]] = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 [[A:%.*]], i64 [[B:%.*]])
-; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i64, i1 } [[RES]], 1
-; CHECK-NEXT:    [[MUL:%.*]] = extractvalue { i64, i1 } [[RES]], 0
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[MUL]], 0
-; CHECK-NEXT:    [[OVERFLOW_1:%.*]] = or i1 [[OVERFLOW]], [[CMP]]
+; CHECK-NEXT:    [[MUL:%.*]] = mul i64 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i64 [[A]], 0
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i64 [[B]], 0
+; CHECK-NEXT:    [[OVERFLOW_1:%.*]] = and i1 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    store i64 [[MUL]], i64* [[PTR:%.*]], align 8
 ; CHECK-NEXT:    ret i1 [[OVERFLOW_1]]
 ;
   %res = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 %a, i64 %b)
   %overflow = extractvalue { i64, i1 } %res, 1
   %mul = extractvalue { i64, i1 } %res, 0
   %cmp  = icmp ne i64 %mul, 0
   %overflow.1 = or i1 %overflow, %cmp
   store i64 %mul, i64* %ptr, align 8
   ret i1 %overflow.1
 }
 
 define i1 @test1_or_ops_swapped(i64 %a, i64 %b, i64* %ptr) {
 ; CHECK-LABEL: @test1_or_ops_swapped(
-; CHECK-NEXT:    [[RES:%.*]] = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 [[A:%.*]], i64 [[B:%.*]])
-; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i64, i1 } [[RES]], 1
-; CHECK-NEXT:    [[MUL:%.*]] = extractvalue { i64, i1 } [[RES]], 0
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[MUL]], 0
-; CHECK-NEXT:    [[OVERFLOW_1:%.*]] = or i1 [[CMP]], [[OVERFLOW]]
+; CHECK-NEXT:    [[MUL:%.*]] = mul i64 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i64 [[A]], 0
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i64 [[B]], 0
+; CHECK-NEXT:    [[OVERFLOW_1:%.*]] = and i1 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    store i64 [[MUL]], i64* [[PTR:%.*]], align 8
 ; CHECK-NEXT:    ret i1 [[OVERFLOW_1]]
 ;
 
   %res = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 %a, i64 %b)
   %overflow = extractvalue { i64, i1 } %res, 1
   %mul = extractvalue { i64, i1 } %res, 0
   %cmp  = icmp ne i64 %mul, 0
   %overflow.1 = or i1 %cmp, %overflow
   store i64 %mul, i64* %ptr, align 8
   ret i1 %overflow.1
 }
 
 define i1 @test2(i64 %a, i64 %b, i64* %ptr) {
 ; CHECK-LABEL: @test2(
-; CHECK-NEXT:    [[RES:%.*]] = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 [[A:%.*]], i64 [[B:%.*]])
-; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i64, i1 } [[RES]], 1
-; CHECK-NEXT:    [[MUL:%.*]] = extractvalue { i64, i1 } [[RES]], 0
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[MUL]], 0
-; CHECK-NEXT:    [[OVERFLOW_1:%.*]] = or i1 [[OVERFLOW]], [[CMP]]
+; CHECK-NEXT:    [[MUL:%.*]] = mul i64 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i64 [[A]], 0
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i64 [[B]], 0
+; CHECK-NEXT:    [[OVERFLOW_1:%.*]] = and i1 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    [[NEG:%.*]] = sub i64 0, [[MUL]]
 ; CHECK-NEXT:    store i64 [[NEG]], i64* [[PTR:%.*]], align 8
 ; CHECK-NEXT:    ret i1 [[OVERFLOW_1]]
 ;
   %res = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 %a, i64 %b)
   %overflow = extractvalue { i64, i1 } %res, 1
   %mul = extractvalue { i64, i1 } %res, 0
   %cmp = icmp ne i64 %mul, 0
   %overflow.1 = or i1 %overflow, %cmp
   %neg = sub i64 0, %mul
   store i64 %neg, i64* %ptr, align 8
   ret i1 %overflow.1
 }
 
 declare void @use(i1)
 
 ; Do not simplify if %overflow has multiple uses.
 define i1 @test3_multiple_overflow_users(i64 %a, i64 %b, i64* %ptr) {
 ; CHECK-LABEL: @test3_multiple_overflow_users(
 ; CHECK-NEXT:    [[RES:%.*]] = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 [[A:%.*]], i64 [[B:%.*]])
 ; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i64, i1 } [[RES]], 1
 ; CHECK-NEXT:    [[MUL:%.*]] = extractvalue { i64, i1 } [[RES]], 0
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[MUL]], 0
 ; CHECK-NEXT:    [[OVERFLOW_1:%.*]] = or i1 [[OVERFLOW]], [[CMP]]
 ; CHECK-NEXT:    [[NEG:%.*]] = sub i64 0, [[MUL]]
;
   ret i1 %overflow.1
 }
 
 declare void @use.3(i64)
 
 ; Simplify if %mul has multiple uses.
 define i1 @test3_multiple_mul_users(i64 %a, i64 %b, i64* %ptr) {
 ; CHECK-LABEL: @test3_multiple_mul_users(
-; CHECK-NEXT:    [[RES:%.*]] = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 [[A:%.*]], i64 [[B:%.*]])
-; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i64, i1 } [[RES]], 1
-; CHECK-NEXT:    [[MUL:%.*]] = extractvalue { i64, i1 } [[RES]], 0
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[MUL]], 0
-; CHECK-NEXT:    [[OVERFLOW_1:%.*]] = or i1 [[OVERFLOW]], [[CMP]]
+; CHECK-NEXT:    [[MUL:%.*]] = mul i64 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i64 [[A]], 0
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i64 [[B]], 0
+; CHECK-NEXT:    [[OVERFLOW_1:%.*]] = and i1 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    [[NEG:%.*]] = sub i64 0, [[MUL]]
 ; CHECK-NEXT:    store i64 [[NEG]], i64* [[PTR:%.*]], align 8
 ; CHECK-NEXT:    call void @use.3(i64 [[MUL]])
 ; CHECK-NEXT:    ret i1 [[OVERFLOW_1]]
 ;
   %res = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 %a, i64 %b)
   %overflow = extractvalue { i64, i1 } %res, 1
   %mul = extractvalue { i64, i1 } %res, 0