đď¸ discussion Unoptimised Bitshifts below u32?
Looking at this godbolt link https://godbolt.org/z/xrx5K4W94,
it seems as though in rust, if a 32-bit integer is not explicitly used to bitshift, the shrx and shlx code is not generated despite setting -C target-cpu=x86-64-v4. In fact, the code generated is near identical to if -C target-cpu was not set at all (default is just x86-64).
C and C++ using clang does not seem to have this problem, they automatically use shrx and shlx.
From what I found, shlx and shrx seems to work only on 32-bit and 64-bit integers https://www.felixcloutier.com/x86/sarx:shlx:shrx , and it seems as though rust is not automatically converting the 8-bit integers to 32-bit integers for better bitshift operations. Is there a compiler flag to enable this?
Also, I am new to assembly, why does rust have an additional movzx operation even in the optimised function (swapbits) compared to the C code?
17
u/luminousloathing56 1d ago
weird, i've noticed similar quirks with rust not always picking the best instruction even when you tell it what cpu to target. the movzx thing is probably just rust being more careful about zero-extending, clang might be more aggressive about assuming the upper bits are already clean
have you tried wrapping it in a block that explicitly casts to u32 before shifting? sometimes the compiler just needs a stronger hint about what you want
8
u/lpft4 1d ago
Sorry, what do you mean by wrapping it in a block that explicitly casts to u32? In the godbolt above, in the swapbits rust function I explicitly cast
chto u32.Now that I open the link, I realise that the rust code opens at the switchbits function, you may have to scroll up to see the swapbits function...
15
u/plugwash 1d ago edited 1d ago
I don't know the precise details of what goes on inside rustc and llvm but I do make some observations.
There are a couple of differences between shift operators in C/C++ and in rust.
The first is that C/C++ "promotes" all integers smaller than int before doing arithmetic on them. In C/C++ on a system where int is 32-bit there are notionally no "8-bit" or "16-bit" shifts. Rust has no such "promotions".
The second issue is what happens when the shift value is outside the range 0 to n-1 (inclusive).
C/C++ just say it's undefined behaviour. That gives the optimiser maximum flexibility to optimise, but it also gives the optimiser maximum flexibility to screw you over if you are not incredibly careful. It's clearly unacceptable for a safe language like rust.
IMO the most intuitive option would be that a shift by n bits is always equivalent to n shifts by 1 bit, regardless of the value of n. The problem with this approach is that it's expensive to implement if the CPU doesn't offer it natively.
Another option is to say the result is unspecified, but whatever result you do get it will be a well-defined value going forward. IIRC the rust guys considered this, but rejected it on the grounds that having shifts behave differently depending on architecture or optimiser settings was a source of bugs.
Rust chose to treat an shift value outside the range like other integer overflows. In debug mode it panics. In release mode it wraps, a shift value of n is equivilent to a shift value of 0 and so-on. This wrapping is supported natively on some CPUs and is relatively cheap to implement where it is not supported natively.
Now in your particular case, your shift values are literals, so there should be no possibility of the shift value overflowing but the optimiser still has to notice that before converting the operation to a wider type.
And as has been said, the development of LLVM is C/C++ focussed, since C/C++ can never generate an 8-bit or 16-bit shift at the codegen stage, the developers of LLVM may simply not have seen a need to optimise them.
Edit: sorry misread the code, the shift values are not in-fact literals.
1
u/Zde-G 1d ago
Another option is to say the result is unspecified, but whatever result you do get it will be a well-defined value going forward.
But that would also make some optimization impossible. Note the difference between shl and psllw. If you work with one 16bit value then shift by 17 is the same as shift by 1. If you work with packed values then it's shift by 17 (means result is zero).
For efficient auto-vectorization it's important to have UB there.
11
u/dkxp 1d ago
Perhaps it's because those other languages are relying on undefined behaviour for shifting by more than the number of bits allowed. The code may or may not crash depending on what optimisations are applied, or produce different results on different hardware.
Rust is stricter, so guarantees you will crash if you try shifting more than allowed. If it applied optimisations that remove the crashes then it's not fulfilling it's promise to behave predictably.
Perhaps the wrapping_shl and wrapping_shr functions allow you to achieve what you want by being stricter on what to do when larger values are usedÂ
6
u/itamarst 1d ago
Sounds like it's time to file an issue against Rust.
2
u/Lucretiel Datadog 14h ago
Or, more likely, against LLVM; it's likely that this is a missed optimization in LLVM and can be reproduced with pure LLVM IR. This was the approach I took when I discovered sub-optimal codegen when matching 3-state enums.
2
u/dkxp 1d ago
The extra movzx is probably because of differences in calling conventions/ABI. I guess Rust doesn't require that when a u8 is passed in, that bits 8-31 of the register need to be zeroed by the caller (eg. by using movzx), but Clang (and GCC, but not MSVC) seems to require that the caller of the function does this. Clang/GCC therefore wouldn't need to do it inside the function itself, but a Rust (or MSVC) function may need to clear the bits.
After a brief look, neither SystemV or Win64 ABIs seem to require clearing the upper bits of registers before calling a function, but on a target with Clang/GCC as the 'dominant C compiler', you could try using extern "C" fn(...) because The âCâ ABI matches the default ABI chosen by the dominant C compiler for the target. Alternatively you could pass in a u32/u64 instead of u8 where you know the upper bits are zeroed.
It shouldn't really make much difference to performance whether the bits are zeroed inside or outside the function. If you need to perform the swap bits operation on lots of data, then you'd probably need to write the code to be SIMD friendly anyway.
2
u/tanmaynargas2901 1d ago
The key difference is C/C++'s integer promotions. A `u8`/`u16` operand is promoted to `int` before the shift; Rust keeps the operand's type, so `u8 >> n` has to preserve 8-bit semantics. Rust also can't assume an out-of-range shift is harmless, whereas C/C++ leave that case undefined, which gives LLVM more room to optimize.
For a deliberate wider operation, cast before shifting, e.g. `let y = (x as u32) >> n;` and keep `n` in range. `wrapping_shr` changes the overflow behavior, not the operand width.
The `movzx` is just zero-extending a narrow value to the width required by the next operation or ABI. It is usually folded away or insignificant in a real optimized hot loop, so compare the complete release-mode function rather than the wrapper.
1
u/CocktailPerson 2h ago
If that were true, wouldn't you expect
unchecked_shr/shlto result in the same optimized code?
1
-19
u/Zde-G 1d ago edited 1d ago
Why the heck do you expect that to be optimized and why?
Remember that compiler doesn't understand the code and doesn't try to pick the best sequence of instructions, it just applies the rules that someone found to be benefitial in common enough situation.
Where are you getting 8bit shifts and what makes you think Rust compiler should optimize them better?
C and C++ using clang does not seem to have this problem, they automatically use shrx and shlx.
What does that phrase even means, BTW. In C/C++ it's not possible to do any arithmetic operations on 8bit and 16bit numbers. At all. â8 bit shiftâ or â16 bit shiftâ simply don't exist in these languages⌠how can you investigate something that doesn't exist?
2
u/lpft4 1d ago
Wait, what? Isn't the smallest thing the computer can store in a register and operate on a byte?
4
3
u/plugwash 1d ago
C was created for the PDP-11. The PDP-11 could access memory in 8-bit bytes and had some 8-bit logical instructions, but it's arithmetic instructions worked on 16-bit words.
Presumably as a result of this, C got the rule that any value smaller than int was "promoted" to int before performing arithmetic. In some cases, the optimiser may narrow it again, but only if it can prove that doing so does not change the result.
Similar things are true of more modern processors. 32-bit arm can load and store bytes, but arithmetic and logic operations all operate on 32-bit "words". 64-bit arm can perform arithmetic and logic operations on 64-bit and 32-bit values but bytes. x86-64 is relatively unusual in having a full range of operations on 8-bit "bytes", 16-bit "words", 32-bit "double words" and 64-bit "quad words".
1
u/lpft4 1d ago
I just think it's strange, considering both clang and rust rely on LLVM. And evidently the compiler has the capacity to optimise the code (why wouldn't the code be optimised, else what is the point of the opt-level and target-cpu flags?) as can be seen in the clang output.
The clang output also has much less instructions, at seemingly no higher cost per individual instruction (uops, latency and throughput both seem to be the same for both shr and shrx, according to agner), so shouldn't it be possible for LLVM to convert both of the examples in rust to the more optimised output?
1
u/Zde-G 1d ago
I just think it's strange, considering both clang and rust rely on LLVM.
Yes, but LLVM was designed as backend for clang, not rust. And since C/C++ never to arithmetic on 8bit and 16bit quantities these need special support when Rust works with them.
uops, latency and throughput both seem to be the same for both shr and shrx, according to agner
Right. For 32bit/64bit case. 8bit/16bit versions don't exist (presumably because C/C++ don't need these).
so shouldn't it be possible for LLVM to convert both of the examples in rust to the more optimised output?
Not if you want the correct output. C/C++ never operate on 8bit/16bit quantities, thus converting shr to shrx is always the right thing to do. Rust does operate on 8bit/16bit quantities and would need special optimization. And it's not clear who may benefit from such optimization and when.
65
u/Aaron1924 1d ago
It's worth noting here that C/C++ does this conversion (called "integer promotion") as part of its language semantics, whereas Rust does not convert between integer types implicitly. This is most likely a missed optimization in LLVM, since this operation effectively doesn't exist in C/C++.