Loving this series! I'm currently implementing a z80 emulator (gameboy) and it's my first real introduction to CISC, and is really pushing my assembly / machine code skills - so having these blog posts coming from the "other direction" are really interesting and give me some good context.
I've implemented toy languages and bytecode compilers/vms before but seeing it from a professional perspective is just fascinating.
That being said it was totally unexpected to find out we can use "addresses" for addition on x86.
Honestly, x86 is not nearly as CISC as those go. It just has a somewhat developed addressing modes comparing to the utterly anemic "register plus constant offset" one, and you are allowed to fold some load-arithmetic-store combinations into a single instruction. But that's it, no double- or triple-indexing or anything like what VAXen had.
Would this matter for performance? You already have so many execution units that are actually difficult to keep fully fed even when decoding instructions and data at the speed of cache.
One of my biggest bugbears in CS instruction is the overdue emphasis on RISC v CISC, especially as there aren't any really good models to show you what the differences are, given the winnowing of ISAs. In John Mashey's infamous posts [1] sort of delineating an ordered list from most RISCy to most CISCy, the architectures that are the most successful have been the ones that really crowded the RISC/CISC line--ARM and x86.
It also doesn't help that, since x86 is the main goto example for CISC, people end up not having a strong grasp on what features of x86 make it actually CISC. A lot of people go straight to its prefix encoding structure or its ModR/M encoding structure, but honestly, the latter is pretty much just a "compressed encoding" of RISC-like semantics, and the former is far less insane than most people give it credit for. But x86 does have a few weird, decidedly-CISC instruction semantics in it--these are the string instructions like REP MOVSB. Honestly, take out about a dozen instructions, and you could make a solid argument that modern x86 is a RISC architecture!
> Using `lea` […] is useful if both of the operands are still needed later on in other calculations (as it leaves them unchanged)
As well as making it possible to preserve the values of both operands, it’s also occasionally useful to use `lea` instead of `add` because it preserves the CPU flags.
Funny to see a comment on HN raising this exact point, when just ~2 hours ago I was writing inline asm that used `lea` precisely to preserve the carry flag before a jump table! :)
>However, in this case it doesn’t matter; those top bits5 are discarded when the result is written to the 32-bit eax.
>Those top bits should be zero, as the ABI requires it: the compiler relies on this here. Try editing the example above to pass and return longs to compare.
Sorry, I don't understand. How could the compiler both discard the top bits, and also rely on the top bits being zero? If it's discarding the top bits, it won't matter whether the top bits are zero or not, so it's not relying on that.
(Almost) any instruction on x64 that writes to a 32-bit register as destination, writes the lower 32-bits of the value into the lower 32 bits of the full 64-bit register and zeroes out the upper 32 bits of the full register. He touched on it in his previous note "why xor eax, eax".
But the funny thing is, the x64-specific supplement for SysV ABI doesn't actually specify whether the top bits should be zeroes or not (and so, if the compiler could rely on e.g. function returning ints to have upper 32 bits zeroes, or those could be garbage), and historically GCC and Clang diverged in their behaviour.
He's actually wrong on the ABI requiring the top bits to be 0. It only requires that the bottom 32 bits match the parameter, but the top bits of a 32-bit parameter passed in a 64-bit register can be anything (at least on Linux).
The reason the code in his post works is because the upper 32 bits of the parameters going into an addition can't affect the low 32 bits of the result, and he's only storing the low 32 bits.
As a side note of appreciation, I think that we can't do better than what he did for being transparent that LLM was used but still just for the proof-reading.
Do we really know that LEA is using the hardware memory address computation units? What if the CPU frontend just redirects it to the standard integer add units/execution ports? What if the hardware memory address units use those too?
It would be weird to have 2 sets of different adders.
What's the current best resources to learn assembly? So that I can understand output of simple functions. I don't want to learn to write it properly, I just want to be able to understand on what's happening.
This triggers a vague memory of trying to figure out why my assembler (masm?) was outputting a LEA instead of a MOV. I can't remember why. Maybe LEA was more efficient, or MOV didn't really support the addressing mode and the assembler just quietly fixed it for you.
In any case, I felt slightly betrayed by the assembler for silently outputting something I didn't tell it to.
> x86 is unusual in mostly having a maximum of two operands per instruction[2]
Perhaps interesting for those who aren't up to date, the recent APX extension allows 3-operand versions of most of the ALU instructions with a new data destination, so we don't need to use temporary registers - making them more RISC-like.
The downside is they're EVEX encoded, which adds a 4-byte prefix to the instruction. It's still cheaper to use `lea` for an addition, but now we will be able to do things like
> However, in this case it doesn’t matter; those top bits are discarded when the result is written to the 32-bit eax.
Fun (but useless) fact: This being x86, of course there are at least three different ways [1] to encode this instruction: the way it was shown, with an address size override prefix (giving `lea eax, [edi+esi]`), or with both a REX prefix and an address size override prefix (giving `lea rax, [edi+esi]`).
And if you have a segment with base=0 around you can also add in a segment for fun: `lea rax, cs:[edi+esi]`
[1]: not counting redundant prefixes and different ModRMs
This trick is something we teach our students when we do 6809 assembly (mainly as a trick to do addition on the index registers). I had no idea it was used as an optimisation in x86.
28 comments
[ 2.5 ms ] story [ 57.5 ms ] threadI've implemented toy languages and bytecode compilers/vms before but seeing it from a professional perspective is just fascinating.
That being said it was totally unexpected to find out we can use "addresses" for addition on x86.
But the main thing that makes x86 CISC to me is not the actual instruction set, but the byte encoding, and the complexity there.
It also doesn't help that, since x86 is the main goto example for CISC, people end up not having a strong grasp on what features of x86 make it actually CISC. A lot of people go straight to its prefix encoding structure or its ModR/M encoding structure, but honestly, the latter is pretty much just a "compressed encoding" of RISC-like semantics, and the former is far less insane than most people give it credit for. But x86 does have a few weird, decidedly-CISC instruction semantics in it--these are the string instructions like REP MOVSB. Honestly, take out about a dozen instructions, and you could make a solid argument that modern x86 is a RISC architecture!
[1] https://yarchive.net/comp/risc_definition.html
As well as making it possible to preserve the values of both operands, it’s also occasionally useful to use `lea` instead of `add` because it preserves the CPU flags.
A lot of people think it's a "teaching programming" game, and it sorta is, but it's actually teaching assembly language skills!
>Those top bits should be zero, as the ABI requires it: the compiler relies on this here. Try editing the example above to pass and return longs to compare.
Sorry, I don't understand. How could the compiler both discard the top bits, and also rely on the top bits being zero? If it's discarding the top bits, it won't matter whether the top bits are zero or not, so it's not relying on that.
But the funny thing is, the x64-specific supplement for SysV ABI doesn't actually specify whether the top bits should be zeroes or not (and so, if the compiler could rely on e.g. function returning ints to have upper 32 bits zeroes, or those could be garbage), and historically GCC and Clang diverged in their behaviour.
You can see that in this godbolt example: https://godbolt.org/z/M1ze74Gh6
The reason the code in his post works is because the upper 32 bits of the parameters going into an addition can't affect the low 32 bits of the result, and he's only storing the low 32 bits.
I'd love to know why that is.
I think the calculation is also done during instruction decode rather than on the ALU, but I could be wrong about that.
It would be weird to have 2 sets of different adders.
E.g. for x * 5 gcc issues lea eax, [rdi+rdi*4].
In any case, I felt slightly betrayed by the assembler for silently outputting something I didn't tell it to.
Loving it so far!
It took several tries to understand zero is a verb
Perhaps interesting for those who aren't up to date, the recent APX extension allows 3-operand versions of most of the ALU instructions with a new data destination, so we don't need to use temporary registers - making them more RISC-like.
The downside is they're EVEX encoded, which adds a 4-byte prefix to the instruction. It's still cheaper to use `lea` for an addition, but now we will be able to do things like
https://www.intel.com/content/www/us/en/developer/articles/t...Fun (but useless) fact: This being x86, of course there are at least three different ways [1] to encode this instruction: the way it was shown, with an address size override prefix (giving `lea eax, [edi+esi]`), or with both a REX prefix and an address size override prefix (giving `lea rax, [edi+esi]`).
And if you have a segment with base=0 around you can also add in a segment for fun: `lea rax, cs:[edi+esi]`
[1]: not counting redundant prefixes and different ModRMs