Vector constants are not hoisted out of loops when there's a lot of non-vector code around them

[hsivonen]

Summary

An ldr corresponding to materializing const uint8x16_t ZERO_LT_AMP_CR = {0, 2, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 4, 1, 1, 1}; is obviously always loop-invariant. Furthermore, when the whole function has fewer vector values than there are vector registers, there cannot be too much register pressure on the vector registers, and such a constant should be hoisted to the top of the function.

When the function is small, LICM happens properly for such constants.

When the function is large, the ldr for the constant moves to immediately before use, and the load is from static memory.

In between these cases, each constant is loaded at the top of the function and immediately spilled to the stack. Then the constant is reloaded from the stack immediately before use.

Steps to reproduce

1. Download nsHtml5TokenizerSIMD-expanded.cpp
2. On Apple Silicon Mac using clang trunk, compile it with clang++ -Wno-everything -isysroot "/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX15.2.sdk" nsHtml5TokenizerSIMD-expanded.cpp -O3 -S
3. Inspect nsHtml5TokenizerSIMD-expanded.s.
4. Comment out the line following the comment // Commenting out the following line allows vector constant LICM!
5. Recompile and inspect the assembly again.

Actual results

On first compilation, the only tbl.16b instruction is preceded by ldr q3, [sp, #32] ; 16-byte Folded Reload.

On the second compilation, the ldr has moved upwards out of the loops.

Expected results

Expected vector constants always to be hoisted out of loops when there aren't more live vector values than there are vector registers regardless of how much ALU code exists in the overall function.

Additional info

I tried flipping the various boolean return values in MachineLICM.cpp to see if one of them was at fault, but I didn't find the cause.

Compiling on Mac differs from Compiler Explorer's armv8-a target. LLVM says it used the following on Mac:

Features:+aes,+altnzcv,+ccdp,+ccidx,+ccpp,+complxnum,+crc,+dit,+dotprod,+flagm,+fp-armv8,+fp16fml,+fptoint,+fullfp16,+jsconv,+lse,+neon,+pauth,+perfmon,+predres,+ras,+rcpc,+rdm,+sb,+sha2,+sha3,+specrestrict,+ssbs,+v8.1a,+v8.2a,+v8.3a,+v8.4a,+v8a
CPU:apple-m1
TuneCPU:apple-m1

[llvmbot]

@llvm/issue-subscribers-backend-aarch64

Author: Henri Sivonen (hsivonen)

# Summary

An ldr corresponding to materizing const uint8x16_t ZERO_LT_AMP_CR = {0, 2, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 4, 1, 1, 1}; is obviously always loop-invariant. Furthermore, when the whole function has fewer vertor values than there are vector registers, there cannot be too much register pressure on the vector registers, and such a constant should be hoisted to the top of the function.

When the function is small, LICM happens properly for such constants.

When the function is large, the ldr for the constant moves to immediately before use, and the load is from static memory.

In between these cases, there each constant is loaded at the top of the function and immediately spilled to the stack. Then the constant is reloaded from the stack immediately before use.

Steps to reproduce

1. Download nsHtml5TokenizerSIMD-expanded.cpp
2. On Apple Silicon Mac using clang trunk, compile it with clang++ -Wno-everything -isysroot "/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX15.2.sdk" nsHtml5TokenizerSIMD-expanded.cpp -O3 -S
3. Inspect nsHtml5TokenizerSIMD-expanded.s.
4. Comment out the line following the comment // Commenting out the following line allows vector constant LICM!
5. Recompile and inspect the assembly again.

Actual results

On first compilation, the only tbl.16b instruction is preceded by ldr q3, [sp, #<!-- -->32] ; 16-byte Folded Reload.

On the second compilation, the ldr has moved upwards out of the loops.

Expected results

Expected vector constants always to be hoisted out of loops when there aren't more live vector values than there are vector registers regardless of how much ALU code exists in the overall function.

Additional info

I tried flipping the various boolean return values in MachineLICM.cpp to see if one of them was at fault, but I didn't find the cause.

Compiling on Mac differs from Compiler Explorer's armv8-a target. LLVM says it used the following on Mac:

Features:+aes,+altnzcv,+ccdp,+ccidx,+ccpp,+complxnum,+crc,+dit,+dotprod,+flagm,+fp-armv8,+fp16fml,+fptoint,+fullfp16,+jsconv,+lse,+neon,+pauth,+perfmon,+predres,+ras,+rcpc,+rdm,+sb,+sha2,+sha3,+specrestrict,+ssbs,+v8.1a,+v8.2a,+v8.3a,+v8.4a,+v8a
CPU:apple-m1
TuneCPU:apple-m1

[efriedma-quic]

Does https://godbolt.org/z/1j418YT1P look like what you're seeing locally?

[hsivonen]

Does https://godbolt.org/z/1j418YT1P look like what you're seeing locally?

Structurally, yes, though the register syntax differs and on Compiler Explorer the load intruction is ldur and locally it's ldr.

[davemgreen]

I saw another case of this recently, where the constant (in my case a MOVi64imm expanded into 4 mov/movk's) was hoisted but then re-materialized into the loop during register allocation. The live range is not split around the loop like you would expect.

[hsivonen]

It turns out that the LICM failure happens also on x86_64: https://godbolt.org/z/rfeosezvG (asm line 578)

(It just happens that the resulting code on x86_64 still has better perf than ALU code, so I noticed that optimizations were going wrong on aarch64 despite the same optimization going wrong on x86_64, too.)

[hsivonen]

Here's an attached version of the x86_64 version of the test case: nsHtml5TokenizerSIMD-expanded.cpp

When I compile this using clang trunk on x86_64 Linux with clang++ nsHtml5TokenizerSIMD-expanded.cpp -O3 -S -mavx2 -mbmi, I see the same thing of LICM not taking place for SIMD constants as I saw on Apple Silicon Mac. And if I comment out the same line that in the earlier test case was marked as a candidate for commenting out, LICM takes place for SIMD constants.

I tried tweaking the threshold numbers in llvm/lib/Transforms/Scalar/LICM.cpp but didn't find anything interesting.

[serge-sans-paille]

Slightly reduced to repro.cpp
Running ./bin/clang++ -O3 -S -mavx2 -mbmi repro.cpp -o- -emit-llvm > repro.txt to extract the following bitcode (txt to workaround github limitation) : repro.txt
Then running ./bin/llc repro.txt -o - -print-after-all 2>&1 | less
I've been able to identify what happens.

1. early-machinelicm moves the constant loading out of the loop
2. Greedy Register Allocator rematerialize them
3. no further pass is able to move them again.

Changing the register allocator to other type doesn't fix the issue.

[serge-sans-paille]

@hsivonen : outlining the loop body that performs the simd instruction to a dedicated function marked as noinline seems to fix the issue (giving more room to the register allocation, I guess, not my area of expertise).

[hsivonen]

2. Greedy Register Allocator rematerialize them

Thank you!

outlining the loop body that performs the simd instruction to a dedicated function marked as noinline seems to fix the issue

This is what I'm currently pursuing as a partial workaround. This only hoists the constants out of the innermost loop, which is better than not hoisting at all, but is still less hoisting than what logically should be possible and what would be useful for my use case.

(giving more room to the register allocation, I guess, not my area of expertise).

The bug then is that the ALU code can affect how register allocation sees the availability of vector registers which are actually available enough that it should be possible to load the vector constants at the top of the huge function and let them stay in the vector registers regardless of what happens with ALU register pressure.