Missed optimization with movzx and mov

[Hintro]

I came across this when examining a loop that runs slower than I expected. It involves explicit and implicit conversions between 8-bit and 32/64-bit values, and as I looked through the generated assembly using Godbolt compiler explorer, I found lots of movzx instructions that don't seem to break dependency or play a role in correctness, not to mention many use the same register like movzx eax al, which cannot be eliminated.

I then tried some simple examples on Godbolt, and found that this behavior is persistent and easily reproducible, even when I specify -march=skylake. Here's an example:

#include <stdint.h>

int add2bytes(uint8_t* a, uint8_t* b) {
    return uint8_t(*a + *b);
}

Clang 14 -O3

add2bytes(unsigned char*, unsigned char*):                       # @add2bytes(unsigned char*, unsigned char*)
        mov     al, byte ptr [rsi]
        add     al, byte ptr [rdi]
        movzx   eax, al
        ret

movzx would be better in place of the mov instead of being at the end, so that dependency on old RAX value can be broken from the start and also clearing the upper bits of RAX in the process.

I also asked this on Stack Overflow and [Peter Cordes] has a detailed response (https://stackoverflow.com/a/72953035/14730360) explaining how this behavior is bad for pretty much all X86 processors.

Godbolt link with code for examples: https://godbolt.org/z/z45xr4hq1
Here's one that's closer to what I was originally examining:

int foo(uint8_t* a, uint8_t i, uint8_t j) {
    return a[a[i] | a[j]];
}

Clang 14 -O3:

foo(unsigned char*, unsigned char, unsigned char):                             # @foo(unsigned char*, unsigned char, unsigned char)
        mov     eax, esi
        mov     ecx, edx
        mov     cl, byte ptr [rdi + rcx]
        or      cl, byte ptr [rdi + rax]
        movzx   eax, cl
        movzx   eax, byte ptr [rdi + rax]
        ret

movzx eax, cl here just seems unnecessary. The upper bits of RCX should already be clean as it is used as index in mov cl, byte ptr [rdi + rcx]. The subsequent or does not affect its upper bits, and the dependency of RCX on this or is not something that movzx eax cl can break. So I think it's better to just do movzx eax, byte ptr [rdi + rcx] after the or.

[llvmbot]

@llvm/issue-subscribers-backend-x86

[topperc]

llvm turns 8-bit loads into movzx pretty late in X86FixupBWInsts pass. I think it only does if the code is in a loop because the movzx encoding is 1 byte longer.

[pcordes]

llvm turns 8-bit loads into movzx pretty late in X86FixupBWInsts pass. I think it only does if the code is in a loop because the movzx encoding is 1 byte longer.

I'd guess that 1 extra byte is worth it in general to avoid a false dependency and the extra load latency of an ALU merge with the full register. I'd recommend changing that, especially if anyone has time to benchmark some interesting codebases to look for regressions (I-cache / uop-cache misses) or improvements. Except maybe with -Os, and definitely not with -Oz (except in cases like this where a later movzx can fold into an 8-bit load.)

CPUs that work around the false dependency (by renaming AL separate from RAX) are over a decade old, the last one being Sandybridge (or maybe IvB).

On Intel CPUs after Sandybridge, mov al, [rdi] decodes as a micro-fused load+ALU-merge uop. I expect AMD is similar, involving an ALU uop, given that their mem->result and addr->result latencies are 1 higher for mov r8l, m8 than for movzx r32, m8, like on Intel. (Except Zen3, where the mem->result store-forwarding latency is the same for both versions, but the address->result latency is still different by 1).

This uops.info search brings up the relevant results, but the table only shows at most 2 latencies, and the r8l destination has a latency for merging into the destination, like movzx r16, m8. But the movzx r32, m8 doesn't even have a latency for that, just address and data. So click on the actual latency numbers to expand to the test results.

Unfortunately uops.info doesn't have integer port breakdowns for AMD. Also, I was thinking Zen2's 0-latency store-forwarding special case would come into play (https://www.agner.org/forum/viewtopic.php?t=41), but it only works for 32 or 64-bit sizes.

Of course, small changes in code size can align things differently, creating noise in branch-prediction, how things pack into the uop cache, etc. And on Skylake, how much padding is needed for -mbranches-within-32B-boundaries to avoid the pothole created by the JCC erratum microcode workaround. But over a few codebases with multiple hot loops, hopefully those would average out.

Related:

• https://stackoverflow.com/questions/41573502/why-doesnt-gcc-use-partial-registers (includes an overview of how various x86 CPUs handle partial registers)
• https://stackoverflow.com/questions/72949175/strange-uses-of-movzx-by-clang-and-gcc/72953035#72953035 - another summary of the same
• https://stackoverflow.com/questions/45660139/how-exactly-do-partial-registers-on-haswell-skylake-perform-writing-al-seems-to - details on Haswell/Skylake not renaming low8 partial regs separate from the full reg, but still renaming AH/BH/CH/DH. Hence uops.info distinguishing r8l and r8h. (A merging uop for a high-8 register still has to issue in a cycle by itself, IIRC from last time I tested on Skylake, like Intel documented for Sandybridge.)

---

Clang/LLVM being cavalier about false dependencies makes some sense when it saves a whole instruction (like xorps zeroing before cvtsi2ss or sqrtss xmm0, mem), although even that can end up creating a loop-carried dep chain across function boundaries, as in the 5x slowdown in https://stackoverflow.com/questions/60688348/why-does-adding-an-xorps-instruction-make-this-function-using-cvtsi2ss-and-addss

But saving 1 byte of code size on a byte load (that's not folded into an ALU operation) seems much less valuable. And has an actual downside of higher load latency and an extra back-end uop taking space in the scheduler (RS) until it executes. (Unlike skipping an xor-zeroing, where the other instruction is going to do its merging regardless.)

[rotateright]

I drafted a patch that removes the loop restriction in X86FixupBWInsts, and there are 200+ regression test files that fail. So far, the diffs look as expected, but it's going to take some time to update everything and confirm.

[rotateright]

Proposal to use the zero-extending load outside of loops:
https://reviews.llvm.org/D129775

[RKSimon]

resolving - this was fixed in 15.x