Missed DCE when popcount of multiplication of two integers but arg1 is 1 in icelake-client

[BreadTom]

Godbolt
Flags were -O3 -Wall -Wextra -march=icelake-client

#include <stdint.h>

int f0(uint64_t arg0, uint64_t arg1){
    uint64_t tmp0;
    int tmp1;
    if(arg1 % 2 == 0)
        __builtin_unreachable();
    if(!__builtin_mul_overflow(arg0, arg1, &tmp0))
        __builtin_unreachable();
    tmp1 = __builtin_popcountg(tmp0);
    return tmp1;
}

int f0_slow(uint64_t arg0, uint64_t arg1){
    uint64_t tmp0;
    int tmp1;
    if(arg1 % 2 == 0)
        __builtin_unreachable();
    if(!__builtin_mul_overflow(arg0, arg1, &tmp0))
        __builtin_unreachable();
    if(arg1 == 1)
        return __builtin_popcountg(arg0);
    tmp1 = __builtin_popcountg(tmp0);
    return tmp1;
}

define dso_local range(i32 0, 65) i32 @f0(i64 noundef %arg0, i64 noundef %arg1) local_unnamed_addr {
entry:
  %rem = and i64 %arg1, 1
  %cmp = icmp ne i64 %rem, 0
  tail call void @llvm.assume(i1 %cmp)
  %0 = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 %arg0, i64 %arg1)
  %1 = extractvalue { i64, i1 } %0, 1
  %2 = extractvalue { i64, i1 } %0, 0
  tail call void @llvm.assume(i1 %1)
  %3 = tail call range(i64 0, 65) i64 @llvm.ctpop.i64(i64 %2)
  %cast = trunc nuw nsw i64 %3 to i32
  ret i32 %cast
}

declare { i64, i1 } @llvm.umul.with.overflow.i64(i64, i64) #1

declare i64 @llvm.ctpop.i64(i64) #1

define dso_local range(i32 0, 65) i32 @f0_slow(i64 noundef %arg0, i64 noundef %arg1) local_unnamed_addr {
entry:
  %rem = and i64 %arg1, 1
  %cmp = icmp ne i64 %rem, 0
  tail call void @llvm.assume(i1 %cmp)
  %0 = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 %arg0, i64 %arg1)
  %1 = extractvalue { i64, i1 } %0, 1
  tail call void @llvm.assume(i1 %1)
  %cmp3 = icmp eq i64 %arg1, 1
  %2 = tail call range(i64 0, 65) i64 @llvm.ctpop.i64(i64 %arg0)
  %3 = extractvalue { i64, i1 } %0, 0
  %4 = tail call range(i64 0, 65) i64 @llvm.ctpop.i64(i64 %3)
  %retval.0.in = select i1 %cmp3, i64 %2, i64 %4
  %retval.0 = trunc nuw nsw i64 %retval.0.in to i32
  ret i32 %retval.0
}

declare void @llvm.assume(i1 noundef) #2

GCC does use only one popcnt but LLVM does not optimize if(arg1 == 1)

[dtcxzyw]

@BreadTom Does this pattern exist in some real-world applications? It looks strange that a program assumes the overflow always occurs.

[BreadTom]

@BreadTom Does this pattern exist in some real-world applications? It looks strange that a program assumes the overflow always occurs.

I don't know if this shows up in real world applications. I was playing around other optimizations. Reducing without overflow shows with -O3 -march=icelake-client shows:
Godbolt

#include <stdint.h>

int f0(uint64_t arg0, uint64_t arg1){
    uint64_t tmp0;
    int tmp1;
    tmp0 = arg0 * arg1;
    tmp1 = __builtin_popcountg(tmp0);
    return tmp1;
}

int f0_slow(uint64_t arg0, uint64_t arg1){
    uint64_t tmp0;
    int tmp1;
    if(arg1 == 1)
        return __builtin_popcountg(arg0);
    tmp0 = arg0 * arg1;
    tmp1 = __builtin_popcountg(tmp0);
    return tmp1;
}

define dso_local range(i32 0, 65) i32 @f0(i64 noundef %arg0, i64 noundef %arg1) local_unnamed_addr {
entry:
  %mul = mul i64 %arg1, %arg0
  %0 = tail call range(i64 0, 65) i64 @llvm.ctpop.i64(i64 %mul)
  %cast = trunc nuw nsw i64 %0 to i32
  ret i32 %cast
}

declare i64 @llvm.ctpop.i64(i64) #1

define dso_local range(i32 0, 65) i32 @f0_slow(i64 noundef %arg0, i64 noundef %arg1) local_unnamed_addr {
entry:
  %cmp = icmp eq i64 %arg1, 1
  %0 = tail call range(i64 0, 65) i64 @llvm.ctpop.i64(i64 %arg0)
  %mul = mul i64 %arg1, %arg0
  %1 = tail call range(i64 0, 65) i64 @llvm.ctpop.i64(i64 %mul)
  %retval.0.in = select i1 %cmp, i64 %0, i64 %1
  %retval.0 = trunc nuw nsw i64 %retval.0.in to i32
  ret i32 %retval.0
}

GCC optimizes better than LLVM in this reduce case.

[dtcxzyw]

This issue can be fixed by folding select Cond, (unop_intrinsic TV), (unop_intrinsic TV) -> unop_intrinsic (select Cond, TV, FV): https://alive2.llvm.org/ce/z/NB4CvX
It would be good to start with ctpop/ctlz/cttz/abs.

After this fold, select (arg1 == 1), arg0, arg1 * arg0 will be folded into arg1 * arg0: https://godbolt.org/z/zeETjrsjo

[llvmbot]

Hi!

This issue may be a good introductory issue for people new to working on LLVM. If you would like to work on this issue, your first steps are:

1. Check that no other contributor has already been assigned to this issue. If you believe that no one is actually working on it despite an assignment, ping the person. After one week without a response, the assignee may be changed.
2. In the comments of this issue, request for it to be assigned to you, or just create a pull request after following the steps below. Mention this issue in the description of the pull request.
3. Fix the issue locally.
4. Run the test suite locally. Remember that the subdirectories under test/ create fine-grained testing targets, so you can e.g. use make check-clang-ast to only run Clang's AST tests.
5. Create a Git commit.
6. Run git clang-format HEAD~1 to format your changes.
7. Open a pull request to the upstream repository on GitHub. Detailed instructions can be found in GitHub's documentation. Mention this issue in the description of the pull request.

If you have any further questions about this issue, don't hesitate to ask via a comment in the thread below.

[llvmbot]

@llvm/issue-subscribers-good-first-issue

Author: None (BreadTom)

[Godbolt](https://godbolt.org/z/nGesTMMK4) Flags were -O3 -Wall -Wextra -march=icelake-client ``` #include <stdint.h>

int f0(uint64_t arg0, uint64_t arg1){
uint64_t tmp0;
int tmp1;
if(arg1 % 2 == 0)
__builtin_unreachable();
if(!__builtin_mul_overflow(arg0, arg1, &tmp0))
__builtin_unreachable();
tmp1 = __builtin_popcountg(tmp0);
return tmp1;
}

int f0_slow(uint64_t arg0, uint64_t arg1){
uint64_t tmp0;
int tmp1;
if(arg1 % 2 == 0)
__builtin_unreachable();
if(!__builtin_mul_overflow(arg0, arg1, &tmp0))
__builtin_unreachable();
if(arg1 == 1)
return __builtin_popcountg(arg0);
tmp1 = __builtin_popcountg(tmp0);
return tmp1;
}

define dso_local range(i32 0, 65) i32 @f0(i64 noundef %arg0, i64 noundef %arg1) local_unnamed_addr {
entry:
%rem = and i64 %arg1, 1
%cmp = icmp ne i64 %rem, 0
tail call void @llvm.assume(i1 %cmp)
%0 = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 %arg0, i64 %arg1)
%1 = extractvalue { i64, i1 } %0, 1
%2 = extractvalue { i64, i1 } %0, 0
tail call void @llvm.assume(i1 %1)
%3 = tail call range(i64 0, 65) i64 @llvm.ctpop.i64(i64 %2)
%cast = trunc nuw nsw i64 %3 to i32
ret i32 %cast
}

declare { i64, i1 } @llvm.umul.with.overflow.i64(i64, i64) #1

declare i64 @llvm.ctpop.i64(i64) #1

define dso_local range(i32 0, 65) i32 @f0_slow(i64 noundef %arg0, i64 noundef %arg1) local_unnamed_addr {
entry:
%rem = and i64 %arg1, 1
%cmp = icmp ne i64 %rem, 0
tail call void @llvm.assume(i1 %cmp)
%0 = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 %arg0, i64 %arg1)
%1 = extractvalue { i64, i1 } %0, 1
tail call void @llvm.assume(i1 %1)
%cmp3 = icmp eq i64 %arg1, 1
%2 = tail call range(i64 0, 65) i64 @llvm.ctpop.i64(i64 %arg0)
%3 = extractvalue { i64, i1 } %0, 0
%4 = tail call range(i64 0, 65) i64 @llvm.ctpop.i64(i64 %3)
%retval.0.in = select i1 %cmp3, i64 %2, i64 %4
%retval.0 = trunc nuw nsw i64 %retval.0.in to i32
ret i32 %retval.0
}

declare void @llvm.assume(i1 noundef) #2

GCC does use only one popcnt but LLVM does not optimize if(arg1 == 1)
</details>

[youngbash88]

Hey, I'd like to work on this issue. Could someone assign it to me?