2 ms·

Is the compiler in a better position to allocate registers than the CPU? Considering it's a hard problem, but really only needs to be solved once, I can see how

Is the compiler in a better position to allocate registers than the CPU? Considering it's a hard problem, but really only needs to be solved once, I can see how pushing that from the CPU to the compiler would help.

AstralStorm 5y ago
Very modestly. It's better to provide simple 4 bit "hotness" probability similar to what CPUs do on their own in branch prediction and cache allocation. Considering all the "blobby" multicore and SMT architecture, you could argue CPU has better information about registers. Just keep register format even and you'd be fine. Not too much to allocate when you have a lot of them and fast. The general hotness would especially help with reducing execution costs in JIT compilation, where new code is generated and CPU does not have accurate prediction data.
ithkuil 5y ago
A register based ISA implicitly conveys dependencies between instructions. This allows the CPU to infer which instructions can be executed in parallel (superscalar execution). Extracting instructions level parallelism (ILP) from a stack oriented is harder, but if a compiler can do it, technically a CPU could do the same. The question is: what would be the advantage? ILP extraction can be done statically. Doing it on a CPU at runtime would cost time and power. OTOH, stack based instruction sets tend to be more compact, so there is less pressure to the memory hierarchy to pull in the code, leaving more bandwidth for operands, and thus reducing stalls. CPU design is a tradeoff in a tradeoff in a tradeoff.
astrange 5y ago
It's better to think of the compiler allocating register names rather than registers. CPUs usually have far more physical registers which they allocate the ISA registers to, with some weird constraints, like some Intel CPUs have a penalty if you try to read a register that hasn't been written in a few hundred cycles. But that problem is simpler than allocating a stack to physical registers.

AstralStorm 5y ago

Very modestly. It's better to provide simple 4 bit "hotness" probability similar to what CPUs do on their own in branch prediction and cache allocation. Considering all the "blobby" multicore and SMT architecture, you could argue CPU has better information about registers. Just keep register format even and you'd be fine. Not too much to allocate when you have a lot of them and fast. The general hotness would especially help with reducing execution costs in JIT compilation, where new code is generated and CPU does not have accurate prediction data.

ithkuil 5y ago

A register based ISA implicitly conveys dependencies between instructions. This allows the CPU to infer which instructions can be executed in parallel (superscalar execution). Extracting instructions level parallelism (ILP) from a stack oriented is harder, but if a compiler can do it, technically a CPU could do the same. The question is: what would be the advantage? ILP extraction can be done statically. Doing it on a CPU at runtime would cost time and power. OTOH, stack based instruction sets tend to be more compact, so there is less pressure to the memory hierarchy to pull in the code, leaving more bandwidth for operands, and thus reducing stalls. CPU design is a tradeoff in a tradeoff in a tradeoff.

astrange 5y ago

It's better to think of the compiler allocating register names rather than registers. CPUs usually have far more physical registers which they allocate the ISA registers to, with some weird constraints, like some Intel CPUs have a penalty if you try to read a register that hasn't been written in a few hundred cycles. But that problem is simpler than allocating a stack to physical registers.