[x86] Eliminate `movzx` when upper part of register is irrelevant or overwritten

[Validark]

export fn foo(x: u8) u32 {
    return @ctz(x >> 1);
}

foo:
        shr     dil
        movzx   eax, dil
        or      eax, 256
        tzcnt   eax, eax
        ret

Could be:

foo:
        shr     dil
        or      edi, 256
        tzcnt   eax, edi
        ret

The compiler could also look for things like or eax, -256 and eliminate movzx eax, al since the relevant bits are overwritten anyway.

[llvmbot]

@llvm/issue-subscribers-backend-x86

Author: Niles Salter (Validark)

```zig export fn foo(x: u8) u32 { return @ctz(x >> 1); } ```

foo:
        shr     dil
        movzx   eax, dil
        or      eax, 256
        tzcnt   eax, eax
        ret

Could be:

foo:
        shr     dil
        or      edi, 256
        tzcnt   eax, edi
        ret

The compiler could also look for things like or eax, -256 and eliminate movzx eax, al since the relevant bits are overwritten anyway.

[RKSimon]

define i32 @src(i8 %a0) {
  %s = lshr i8 %a0, 1
  %r = call i8 @llvm.cttz.i8(i8 %s, i1 0)
  %x = zext i8 %r to i32
  ret i32 %x
}

x86 promotes this to i32 and adds the or to correctly clamp the trailing zero range to something closer to:

define i32 @tgt(i8 %a0) {
  %s = lshr i8 %a0, 1
  %x = zext i8 %s to i32
  %m = or i32 %x, 256
  %r = call i32 @llvm.cttz.i32(i32 %m, i1 0)
  ret i32 %r
}

https://zig.godbolt.org/z/GEb1v45xb

Either way - this can probably be handled as a generic SimplifyDemandedBits ISD::CTTZ fold by determining the KnownBits min trailing zero count and only demanding those bits.

[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 is working on this issue. If someone is assigned to the issue or claimed to be working on it, ping the person. After one week without a response, the assignee may be changed.
2. Leave a comment indicating that you are working on the issue, 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: Niles Salter (Validark)

```zig export fn foo(x: u8) u32 { return @ctz(x >> 1); } ```

foo:
        shr     dil
        movzx   eax, dil
        or      eax, 256
        tzcnt   eax, eax
        ret

Could be:

foo:
        shr     dil
        or      edi, 256
        tzcnt   eax, edi
        ret

The compiler could also look for things like or eax, -256 and eliminate movzx eax, al since the relevant bits are overwritten anyway.

[stomfaig]

Would be happy to work on this.

[GrumpyPigSkin]

I had a look at this in more detail, and it seems that removing the movzx doesn't actually produce a noticeable improvement, looking at llvm-mca the version without the movzx has quite a big increase in register pressure due to the CPU having to merge registers dil into edi. In hardware edi and dil are more than likely not the same physical register due to register renaming. The movzx basically breaks the dependency between the "real" dil and edi even though it adds an extra instruction.

In reality this means at least for my machine (14900k) both versions of code end up around the same performance:

-------------------------------------------------------
Benchmark             Time             CPU   Iterations
-------------------------------------------------------
with_move         0.400 ns        0.400 ns   1624654268
without_move      0.401 ns        0.401 ns   1749617271
-------------------------------------------------------
Benchmark             Time             CPU   Iterations
-------------------------------------------------------
with_move         0.429 ns        0.429 ns   1626836291
without_move      0.411 ns        0.411 ns   1809053849
-------------------------------------------------------
Benchmark             Time             CPU   Iterations
-------------------------------------------------------
with_move         0.399 ns        0.399 ns   1360337986
without_move      0.416 ns        0.416 ns   1782558884

@RKSimon Do you think it is worth getting rid of the movzx in this instance, or is there something I have missed?