4 ms·

Although this isn't about the 6502, this reminds me of how I had to write x86_64 assembly for class, and was trying to use LEA to avoid a multiplication. After

Although this isn't about the 6502, this reminds me of how I had to write x86_64 assembly for class, and was trying to use LEA to avoid a multiplication. After I wrote it, I wondered if the compiler did the same thing I did, but it didn't; the compiler's version used a register unnecessarily. Compare: ;; Goal: r8 := 10 * r9 ;; Mine: ;; 10x = x + 9x ;; 9x = x + 8x lea r8, [r9 + 8 * r9] add r8, r9 ;; Compiler's code: ;; 10x = 2 * 5x = 5x + 5x ;; 5x = x + 4x lea rdi, [r9 + 4 * r9] lea r8, [rdi + rdi] At first, I wondered why the compiler introduced a temporary. However, I had just done the exercises from the book The Structure and Interpretation of Computer Programs that ask you to create recursive and iterative routines that multiply integers through successive doubling and halving, by taking advantage of the fact that Cx = C + (C - 1)x, if C is odd, and Cx = 2 * (C / 2)x, if C is even (although that's not exactly how they explained it; I don't perfectly remember and I don't feel like looking it up, even though this wasn't that long ago). I realized: the compiler must be using a variant of the Russian peasant method of multiplication (which was the name of the method, as the book had explained) as a form of strength reduction. I was impressed, but I also realized that this meant that it was suboptimal for minimizing temporary registers. However, I couldn't think of some algorithm that would multiply it the way I did when I wrote that assembly, since I hadn't really had an algorithm in mind when writing it.

jlokier 3y ago
> I was impressed, but I also realized that this meant that it was suboptimal for minimizing temporary registers. However, I couldn't think of some algorithm that would multiply it the way I did when I wrote that assembly, since I hadn't really had an algorithm in mind when writing it. If the compiler were minimising touched architectural registers, it could use the same multiplication method it already does, but output this code: lea r8, [r9 + 4 * r9] lea r8, [r8 + r8] Or this: lea r8, [r9 + 4 * r9] add r8, r8 If it used your multiplication method, but with the register allocation decisions it appears to use, it could output this code: lea rdi, [r9 + 8 * r9] lea r8, [rdi + r9] So the compiler's decision to use temporary RDI looks to me like a register allocation decision only, independent of multiplication method. (But maybe affected by an lea/add decision).
- trealira 3y ago
  You're right. I don't know why, but I didn't realize that neither method of multiplication required you to use more than 2 registers here. The use of a temporary register was probably coincidental. Maybe it wouldn't have used an extra register if it had needed to spill to the stack in order to use one, and instead maybe it would have written one of the alternatives you wrote. Thanks for letting me know.
rwmj 3y ago
lea has some performance issues on x86-64, although only in some variations: https://reviews.llvm.org/D32277 https://reviews.llvm.org/D32277

jlokier 3y ago

> I was impressed, but I also realized that this meant that it was suboptimal for minimizing temporary registers. However, I couldn't think of some algorithm that would multiply it the way I did when I wrote that assembly, since I hadn't really had an algorithm in mind when writing it. If the compiler were minimising touched architectural registers, it could use the same multiplication method it already does, but output this code: lea r8, [r9 + 4 * r9] lea r8, [r8 + r8] Or this: lea r8, [r9 + 4 * r9] add r8, r8 If it used your multiplication method, but with the register allocation decisions it appears to use, it could output this code: lea rdi, [r9 + 8 * r9] lea r8, [rdi + r9] So the compiler's decision to use temporary RDI looks to me like a register allocation decision only, independent of multiplication method. (But maybe affected by an lea/add decision).

trealira 3y ago
You're right. I don't know why, but I didn't realize that neither method of multiplication required you to use more than 2 registers here. The use of a temporary register was probably coincidental. Maybe it wouldn't have used an extra register if it had needed to spill to the stack in order to use one, and instead maybe it would have written one of the alternatives you wrote. Thanks for letting me know.

rwmj 3y ago

lea has some performance issues on x86-64, although only in some variations: https://reviews.llvm.org/D32277 https://reviews.llvm.org/D32277