Skip to content

1 << cttz(z) should be folded into z & -z even on machines with cttz built-in #91305

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
Validark opened this issue May 7, 2024 · 4 comments
Closed

Comments

@Validark
Copy link

Validark commented May 7, 2024

https://alive2.llvm.org/ce/z/on8IIK suggests 1 << cttz(z) = z & -z is already folded by instcombine

Originally posted by @RKSimon in #90000 (comment)

This code:

export fn bar(y: u64) u64 {
    if (y == 0) return 0;
    return @as(u64, 1) << @intCast(@ctz(y));
}

Gives me this emit for the risc-v sifive u74:

bar:
        neg     a1, a0
        and     a0, a0, a1
        ret

Exactly what we want.

Now, let's "upgrade" to the sifive x280:

bar:
        ctz     a1, a0
        li      a2, 1
        sll     a1, a2, a1
        bnez    a0, .LBB0_2
        li      a1, 0
.LBB0_2:
        mv      a0, a1
        ret

Oops! Same problem occurs on x86 Zen 3:

bar:
        tzcnt   rax, rdi
        mov     ecx, 1
        shlx    rax, rcx, rax
        cmovb   rax, rdi
        ret

And on aarch64 apple_latest:

bar:
        rbit    x8, x0
        clz     x8, x8
        mov     w9, #1
        lsl     x8, x9, x8
        cmp     x0, #0
        csel    x0, xzr, x8, eq
        ret

Godbolt link

Related: #84763 #90000

@dtcxzyw
Copy link
Member

dtcxzyw commented May 7, 2024

Can you try #85066?

@Validark
Copy link
Author

Validark commented May 7, 2024

@dtcxzyw Looks like the transformation does not happen due to the AND with 63.

https://alive2.llvm.org/ce/z/_tyFCK

@dtcxzyw
Copy link
Member

dtcxzyw commented May 7, 2024

@dtcxzyw Looks like the transformation does not happen due to the AND with 63.

https://alive2.llvm.org/ce/z/_tyFCK

This is a codegen patch. And it hasn't been merged into main. You should apply this patch and run llc on your local machine.

does not happen due to the AND with 63.

is_zero_poison should be marked as true (based on the dominating condition), then the and inst will be eliminated.

BTW, opt -O3 already folds this pattern as you expected. Doesn't zig compiler use the default optimization pipeline?
godbolt: https://zig.godbolt.org/z/7qoEjox3K

@RKSimon
Copy link
Collaborator

RKSimon commented Feb 25, 2025

Fixed in trunk: https://zig.godbolt.org/z/ch7Yo1jdb

@RKSimon RKSimon closed this as completed Feb 25, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

3 participants