Addressing the adding situation
xania.org
xania.org
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.
Never for performance. If I wanted to hand optimise code I'd be more likely to use SIMD intrinsics, play with C until the compiler does the right thing, or write the entire function in a separate asm file for better highlighting and easier handing of state at ABI boundary rather than mid-function like the carry flags mentioned above.
Those writing assembler typically/often think/know they can do better than the compiler. That means that isn’t necessarily a good thing.
(Similarly, veltas comment above about “play with C until the compiler does the right thing” is brittle. You don’t even need to change compiler flags to make it suddenly not do the right thing anymore (on the other hand, when compiling for a different version of the CPU architecture, the compiler can fix things, too)
It's brittle depending on your methods. If you understand a little about optimizers and give the compiler the hints it needs to do the right things, then that should work with any modern compiler, and is more portable (and easier) than hand-optimizing in assembly straight away.
gcc optimised it correctly though.
Generally playing with the C until the compiler does the right thing is slightly brittle in terms of performance but not in terms of functionality. Different compiler flags or a different architecture may give you worse performance, but the code will still work.
“Advanced chess is a form of chess in which each human player uses a computer chess engine to explore the possible results of candidate moves. With this computer assistance, the human player controls and decides the game.
Also called cyborg chess or centaur chess, advanced chess was introduced for the first time by grandmaster Garry Kasparov, with the aim of bringing together human and computer skills to achieve the following results:
- increasing the level of play to heights never before seen in chess;
- producing blunder-free games with the qualities and the beauty of both perfect tactical play and highly meaningful strategic plans;
- offering the public an overview of the mental processes of strong human chess players and powerful chess computers, and the combination of their forces.”
In general case you're right. Modern compilers are beasts.
And that was already after copious `assert_unchecked`s to have the compiler assume as many invariants as it could!
This is one of the remaining cases where the current compilers optimize rather poorly: when you have a tight loop around a huge switch-statement, with each case-statement performing a very small operation on common data.
In that case, a human writing assembler can often beat a compiler with a huge margin.
https://blog.reverberate.org/2025/02/10/tail-call-updates.ht...
It still happens in 2025
LLVM codegen has been almost always sufficient, but for a routine that essentially amounts to adding two fixed-size bigints (e.g. 1024-bit ints represented as `[u64; 16]`), codegen was very very bad.
Writing a jump table by hand literally made the code 3× faster :)
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
or rax, rdx, rcx
A lot of people think it's a "teaching programming" game, and it sorta is, but it's actually teaching assembly language skills!
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.
Your colleagues would probably prefer if you forget this.
Wouldn't that be more verbose and less confusing? (genuinely asking)
This is, I am sure, one of the stupid legacy reasons we still write "lr a0, 4(a1)" instead of more sensible "lr a0, a1[4]". The other one is that FORTRAN used round parentheses for both array access and function calls, so it stuck somehow.
.equ car, 0
.equ cdr, 8
.globl length
length: test %rdi, %rdi # nil?
jz 1f # return 0
mov cdr(%rdi), %rdi # recurse on tail of list
call length
inc %rax
ret
1: xor %eax, %eax
ret
Alternatively, on non-RISC architectures, where the immediate constant isn't constrained to a few bits, it can be the address of an array, and the (possibly scaled) register is an index into it. So you might have startindex(,%rdi,4) for the %rdi'th start index:
.data
startindex:
.long 1024
.text
.globl length
length: mov (startindex+4)(,%rdi,4), %eax
sub startindex(,%rdi,4), %eax
ret
This is not very popular nowadays both because it isn't RISC-compatible and because it isn't reentrant. AMD64 in particular is a kind of peculiar compromise—the immediate "offset" for startindex and endindex is 32 bits, even though the address space is 64 bits, so you could conceivably make this code fail to link by placing your data segment in the wrong place.
(Despite stupid factionalist stuff, I think I come down on the side of preferring the Intel syntax over the AT&T syntax.)
Matt Godbolt is, obviously, extremely smart and has a lot of interesting insight as a domain expert. But... this was LLM-assisted.
So, anyone who has previously said they'll never (knowingly) read anything that an ai has touched (or similar sentiment) are you going to skip this series? Make an exception?
I've been throwing my PR diffs at Claude over the last few weeks. It spits a lot of useless or straight up wrong stuff, but sometimes among the insanity it manages to get one or another typo that a human missed, and between letting a bug pass or spending extra 10m per PR going through the nothingburguers Claude throws at me, I'd rather lose the 10m.
Just not use it. I couldn't care less if other people spend hours prompt engineering to get something that approaches useful output. If they want their reputation staked on it's output that's on them. The results are already in and they're not pretty.
I just personally think it's absurd to spend trillions of dollars and watts to create an advanced spell checker. Even more so to see this as a "revolution" of any sort or to not expect a new AI-winter once this bubble pops.
In any case, I felt slightly betrayed by the assembler for silently outputting something I didn't tell it to.
e.g. If base + (index * scale) + offset = 42, and the value at address 42 is 3, then:
LEA rax, [base + index * scale + offset] will set rax = 42
MOV rax, [base + index * scale + offset] will set rax = 3
LEA eax, [ebx]
instead of:
MOV eax, ebx
But of course:
MOV eax, [ebx]
is not the same.
E.g. for x * 5 gcc issues lea eax, [rdi+rdi*4].
So I guess this trick then only works for multiplication by 2, 3, 4, 5, 8 or 9?
x * 6:
lea eax, [rdi+rdi*2]
add eax, eax
x * 7:
lea eax, [0+rdi*8]
sub eax, edi
x * 11:
lea eax, [rdi+rdi*4]
lea eax, [rdi+rax*2]
And on modern CPUs multiplication might not be actually all that slow (but there may be fewer multiply units).
>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.
https://github.com/llvm/llvm-project/issues/12579 https://groups.google.com/g/x86-64-abi/c/h7FFh30oS3s/m/Gksan... https://gitlab.com/x86-psABIs/x86-64-ABI/-/merge_requests/61
It would be weird to have 2 sets of different adders.
Modern CPUs can execute up to between 6 and 10 instructions within a clock cycle, and up to between 3 and 5 of those may be load and store instructions.
So they have a set of execution units that allow the concurrent execution of a typical mix of instructions. Because a large fraction of the instructions generate load or store micro-operations, there are dedicated units for address computation, to not interfere with other concurrent operations.
Or is it guaranteed that a LEA instruction will always execute on an AGU, and an ADD instruction always on an ALU?
No recent Intel/AMD CPU executes directly LEA or other instructions, they are decoded into 1 or more micro-operations.
The LEA instructions are typically decoded into either 1 or 2 micro-operations. The addressing modes that add 3 components are usually decoded into 2 micro-operations, like also the obsolete 16-bit addressing modes.
The AGUs probably have some special forwarding paths for the results towards the load/store units, which do not exist in ALUs. So it is likely that 1 of the up to 2 LEA micro-operations are executed only in AGUs. On the other hand, when there are 2 micro-operations it is likely that 1 of them can be executed in any ALU. It is also possible for the micro-operations generated by a LEA to be different from those of actual load/store instructions, so that they may also be executed in ALUs. This is decided by the CPU designer and it would not be surprising if LEAs are processed differently in various CPU models.
Not too versed here, but given that ADD seems to have more execution ports to pick from (e.g. on Skylake), I'm not sure that's an argument in favor of lea. I'd guess that LEA not touching flags and consuming fewer uops (comparing a single simple LEA to 2 ADDs) might be better for out of order execution though (no dependencies, friendlier to reorder buffer)
Not really. CPUs often have limited address math available separately from the ALU. On simple cores, it looks like a separate incrementer for the Program Counter, on x86 you have a lot of addressing modes that need a little bit of math; having address units for these kinds of things allows more effective pipelining.
> Do we really know that LEA is using the hardware memory address computation units?
There are ways to confirm. You need an instruction stream that fully loads the ALUs, without fully loading dispatch/commit, so that ALU throughput is the limit on your loop; then if you add an LEA into that instruction stream, it shouldn't increase the cycle count because you're still bottlenecked on ALU throughput and the LEA does address math separately.
You might be able to determine if LEAs can be dispatched to the general purpose ALUs if your instruction stream is something like all LEAs... if the throughput is higher than what could be managed with only address units, it must also use ALUs. But you may end up bottlenecked on instruction commit rather than math.
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
Loving it so far!
It took several tries to understand zero is a verb
Yesterday we saw how compilers zero out registers efficiently.
Yesterday we saw how compilers set the values in registers to zero efficiently.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.
Fun question: what does the last line of this do?
MOV BP,12 LEA AX,[BP] MOV BX,34 LEA AX,BX
Why is this written
lea eax, [rdi + rsi]
lea eax, rdi + rsi
?LEA would normally be used for things like calculating address of an array element, or doing pointer math.
[1] On a hardware level, the ModR/M encoding of most x86 instructions allows you to specify a register operand and either a memory or a register operand. The LEA instruction only allows a register and a memory operand to be specified; if you try to use a register and register operand, it is instead decoded as an illegal instruction.
Not quite unique: the now-deprecated Intel MPX instructions had similar semantics, e.g. BNDCU or BNDMK. BNDLDX/BNDSTX are even weirder as they don't compute the address as specified but treat the index part of the memory operand separately.
In `op reg1, reg2`, the two registers are encoded as 3 bits each the ModRM byte which follows the opcode. Obviously, we can't fit 3 registers in the ModRM byte because it's only 8-bits.
In `op reg1, [reg2 + reg3]`, reg1 is encoded in the ModRM byte. The 3 bits that were previously used for reg2 are instead `0b100`, which indicates a SIB byte follows the ModRM byte. The SIB (Scale-Index-Base) byte uses 3 bits each for reg2 and reg3 as the base and index registers.
In any other instruction, the SIB byte is used for addressing, so syntax of `lea` is consistent with the way it is encoded.
Encoding details of ModRM/SIB are in Volume2, Section 2.1.5 of the ISA manual: https://www.intel.com/content/www/us/en/developer/articles/t...
Instead of reading from memory at "computed address value" it returns "computed address value" to you to use elsewhere.
The intent was likely to compute the address values for MOVS/MOVSB/MOVSW/MOVSD/MOVSQ when setting up a REP MOVS (or other repeated string operation). But it turned out they were useful for doing three operand adds as well.
You can select the assembly output (I like RISCV but you can pick ARM, x86, mips, etc with your choice of compiler) and write your own simple functions. Then put the original function and the assembly output into an LLM prompt window and ask for a line-by-line explanation.
Also very useful to get a copy of Computer Organization and Design RISC-V Edition: The Hardware Software Interface, by Patterson and Hennessy.
BINOP disp(rd1+rd2 shl #N), rs
vs.
SHL rTMP1, rd2, #N
ADD rTMP1, rTMP1, rd1
LOAD rTMP2, disp(rTMP1)
BINOP rTMP2, rTMP2, rs
STORE disp(rTMP1), rTMP2
But the main thing that makes x86 CISC to me is not the actual instruction set, but the byte encoding, and the complexity there.
Edit: the very, very compressed TL;DR is that if you do only one memory load (or one memory load + store back into this exact location) per instruction, it scales fine. But the moment you start doing chained loads, with pre- and post-increments which are supposed to write back changed values into the memory and be visible, and you have several memory sources, and your memory model is actually "strong consistency", well, you're in a world of pain.
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!
> these are the string instructions like REP MOVSB
AArch64 nowadays has somewhat similar CPY* and SET* instructions. Does that make AArch64 CISC? :-) (Maybe REP SCASB/CMPSB/LODSB (the latter being particularly useless) is a better example.)