4 ms·

I find it a little amusing that the given example function does a computation which could've easily been simplified into a single instruction on x86, which need

I find it a little amusing that the given example function does a computation which could've easily been simplified into a single instruction on x86, which needs only a single register (assuming the input x and the return value are both in eax): lea eax, [eax+eax*4+7] ...and it's likely that a compiler would do such simplifications even before attempting register allocation, since it can only make the latter easier. This is particularly likely to be necessary if the desired instruction is already using indirect addressing, and both register allocation and instruction selection must take those constraints into account. As a long-time Asm programmer, I believe that instruction selection and register allocation are inseparable and really need to be considered at the same time; attempting to separate them, like what most if not all compilers do, results in (sometimes very) suboptimal results which is easily noticeable in compiler-generated vs human-generated code.

Sharlin 2y ago
Yeah, but x86 is perverse like that :^D
aengelke 2y ago
> attempting to separate them, like what most if not all compilers do, results in (sometimes very) suboptimal results Not separating them would have a big disadvantage: all register allocation decisions need to be strictly local, because information about upcoming instructions and their register constraints is not available. Even simple graph coloring algorithms give much better code than algorithms with local decisions only. In our baseline/unoptimized compiler, we do ISel+RegAlloc(+Encoding) combined in a single step and we get lots of easily avoidable moves and spills. (These typically don't hurt performance that much on modern out-of-order CPUs with store forwarding, but substantially increase the code size.)
virgilp 2y ago
You're not wrong - in that ALL optimizations are inter-dependent. But, for reasons that I think are rather obvious, it's really hard to do them optimally, all at once. So typically you'd do things like "register-pressure-aware" selection & scheduling, repeated optimization steps (like, do a register-pressure-aware first scheduling, RA, then schedule again) etc. It's all just heuristics, in the end. > since it can only make the latter easier. Not necessarily. For a simple case, yes; but in general, committing to early to reuse a virtual register may have very bad performance implications, since it limits code mobility, freedom to select a particular register, and may increase register pressure in critical sections of the code (say you have "A conflicts with B, B with C and C with D"; you can put all of these in 2 registers: A=R0, B=R1, C=R0, D=R1. But if you committed too early to unify the lifetimes of A and D - eg. for instruction selection purposes - now you need 3 registers. Which is fine, and likely the best solution if you actually end up having 3 registers available - but very likely sub-optimal if you only had 2).
saagarjha 2y ago
Interestingly clang does not lower down to that (instead it multiplies by 7 in a separate step) while GCC does.
- thebolt00 2y ago
  It actually depends on what flags you pass to clang, and for a good reason. 3 term lea uses "complex decoding" and thus has higher latency (and less possible execution ports) on intel arches before icelake. If you run clang -O2 -mtune=icelake-client or -mtune=znver3 (or later architectures) it will generate the single lea instruction. As always in optimization choices it comes down to cost modelling and trade-offs.
  - saagarjha 2y ago
    Interesting. I guess GCC’s cost modeling is different, then? Or does it default to a newer machine?
bjourne 2y ago
A compiler would probably emit shift-and-add by constants. Which may very well be faster than a lea.
rwmj 2y ago
Isn't that one of the "slow lea" cases? https://reviews.llvm.org/D32277 https://reviews.llvm.org/D32277 (I can't quite parse whether using EBP/RBP/R13 is necessary to hit the slow case, or if it's any of those bullet points that cause slowness.)
- dzaima 2y ago
  rbp/r13 are there because the funky way x86 encodes ModR/M means that they get a "+ 0" forced onto them, i.e. [rbp + rax*8] actually must be [rbp + rax*8 + 0] and as such behaves like a 3-operand lea. (same for [rbp] → [rbp+0] but that's irrelevant here as that's still two-operand)

Sharlin 2y ago

Yeah, but x86 is perverse like that :^D

aengelke 2y ago

> attempting to separate them, like what most if not all compilers do, results in (sometimes very) suboptimal results Not separating them would have a big disadvantage: all register allocation decisions need to be strictly local, because information about upcoming instructions and their register constraints is not available. Even simple graph coloring algorithms give much better code than algorithms with local decisions only. In our baseline/unoptimized compiler, we do ISel+RegAlloc(+Encoding) combined in a single step and we get lots of easily avoidable moves and spills. (These typically don't hurt performance that much on modern out-of-order CPUs with store forwarding, but substantially increase the code size.)

virgilp 2y ago

You're not wrong - in that ALL optimizations are inter-dependent. But, for reasons that I think are rather obvious, it's really hard to do them optimally, all at once. So typically you'd do things like "register-pressure-aware" selection & scheduling, repeated optimization steps (like, do a register-pressure-aware first scheduling, RA, then schedule again) etc. It's all just heuristics, in the end. > since it can only make the latter easier. Not necessarily. For a simple case, yes; but in general, committing to early to reuse a virtual register may have very bad performance implications, since it limits code mobility, freedom to select a particular register, and may increase register pressure in critical sections of the code (say you have "A conflicts with B, B with C and C with D"; you can put all of these in 2 registers: A=R0, B=R1, C=R0, D=R1. But if you committed too early to unify the lifetimes of A and D - eg. for instruction selection purposes - now you need 3 registers. Which is fine, and likely the best solution if you actually end up having 3 registers available - but very likely sub-optimal if you only had 2).

saagarjha 2y ago

Interestingly clang does not lower down to that (instead it multiplies by 7 in a separate step) while GCC does.

thebolt00 2y ago
It actually depends on what flags you pass to clang, and for a good reason. 3 term lea uses "complex decoding" and thus has higher latency (and less possible execution ports) on intel arches before icelake. If you run clang -O2 -mtune=icelake-client or -mtune=znver3 (or later architectures) it will generate the single lea instruction. As always in optimization choices it comes down to cost modelling and trade-offs.
- saagarjha 2y ago
  Interesting. I guess GCC’s cost modeling is different, then? Or does it default to a newer machine?

bjourne 2y ago

A compiler would probably emit shift-and-add by constants. Which may very well be faster than a lea.

rwmj 2y ago

Isn't that one of the "slow lea" cases? https://reviews.llvm.org/D32277 https://reviews.llvm.org/D32277 (I can't quite parse whether using EBP/RBP/R13 is necessary to hit the slow case, or if it's any of those bullet points that cause slowness.)

dzaima 2y ago
rbp/r13 are there because the funky way x86 encodes ModR/M means that they get a "+ 0" forced onto them, i.e. [rbp + rax*8] actually must be [rbp + rax*8 + 0] and as such behaves like a 3-operand lea. (same for [rbp] → [rbp+0] but that's irrelevant here as that's still two-operand)