llvm / llvm/llvm-project

[InstCombine] Missing ctpop parity optimization for Add and Sub

Open
#186,957 0 comments 0 reactions 1 assignee Claimed by @Xinlong-Wu View on GitHub
llvm:instcombine missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

InstCombine already folds `(ctpop(X) ^ ctpop(Y)) & 1` → `ctpop(X ^ Y) & 1 ` for `Instruction::Xor` when DemandedMask == 1.
The identical parity identity holds for addition and subtraction, but they are not carried by the same matching fold.

In the following case:

```llvm
define i1 @src(i32 %x, i32 %y) {
%px = call i32 @llvm.ctpop.i32(i32 %x)
%py = call i32 @llvm.ctpop.i32(i32 %y)
%add = add i32 %px, %py
%res = trunc i32 %add to i1
ret i1 %res
}
```

we except it can be folded as:

```llvm
define i1 @tgt(i32 %x, i32 %y) {
%xor = xor i32 %x, %y
%pop = call i32 @llvm.ctpop.i32(i32 %xor)
%res = trunc i32 %pop to i1
ret i1 %res
}
```

but it actually not: https://godbolt.org/z/fbv4q4v1e

Alive2: https://alive2.llvm.org/ce/z/4_qtec (for add)
https://alive2.llvm.org/ce/z/y9aFak (for sub)

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.