llvm / llvm/llvm-project

[InstCombine][VectorCombine] "Fold the set of constants by cttz into a product of the lowest set bit" should be cost-driven

Open
#216,550 5 comments 0 reactions 1 assignee Claimed by @PjDailey11 View on GitHub
backend:AArch64 backend:X86 llvm:instcombine llvm:vectorcombine missed-optimization optimization:AMDCPU regression:24
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

#214517 will fold like this:
```llvm
define i32 @src(i32 %x, i32 %y) {
%shamt = call i32 @llvm.cttz.i32(i32 %y, i1 false)
%shl = shl i32 %x, %shamt
ret i32 %shl
}

define i32 @tgt(i32 %x, i32 %y) {
%neg = sub i32 0, %y
%lsb = and i32 %y, %neg
%mul = mul i32 %x, %lsb
ret i32 %mul
}

define i32 @src2(i32 %x, i32 %y) {
%shamt = call i32 @llvm.cttz.i32(i32 %y, i1 false)
%shl = shl nuw i32 %x, %shamt
ret i32 %shl
}

define i32 @tgt2(i32 %x, i32 %y) {
%neg = sub i32 0, %y
%lsb = and i32 %y, %neg
%mul = mul nuw i32 %x, %lsb
ret i32 %mul
}
```
This is typically profitable, but that is not always true in two specific cases of x86 and aarch64:
1. zen5:
```asm
1 1 0.50 tzcntl %esi, %eax
1 1 0.50 shlxl %eax, %edi, %eax
1 5 0.50 U retq
1 1 0.25 blsil %esi, %eax
1 3 1.00 imull %edi, %eax
1 5 0.50 U retq
1 1 0.50 tzcntl %esi, %eax
1 1 0.50 shlxl %eax, %edi, %eax
1 5 0.50 U retq
1 1 0.25 blsil %esi, %eax
1 3 1.00 imull %edi, %eax
1 5 0.50 U retq
```
Although instructions count is unchanged, both latency and throughput are worse.

2. apple-m5/cssc:
```asm
1 1 0.25 ctz w8, w1
1 1 0.50 lsl w0, w0, w8
1 0 1.00 U ret
1 2 1.00 neg w8, w1
1 2 1.00 and w8, w1, w8
1 4 1.00 mul w0, w8, w0
1 0 1.00 U ret
1 1 0.25 ctz w8, w1
1 1 0.50 lsl w0, w0, w8
1 0 1.00 U ret
1 2 1.00 neg w8, w1
1 2 1.00 and w8, w1, w8
1 4 1.00 mul w0, w8, w0
1 0 1.00 U ret
```
In this case, instruction count/code size, latency, and throughput all show significant regression.

Since this fold is an irreversible transformation, backends cannot revert it without additional overhead - this fold should be moved to VectorCombine for cttz cost-aware.

https://godbolt.org/z/zoYYdbeWa

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.