This article seems a little oversimplified. In a complex ISA like x86, some instructions expect things to be in particular registers, or write to particular registers. Some instructions can operate on multiple registers, but not all registers. Some constraints exist by convention, because if a function calling convention places the first four arguments in rcx, rdx, r8 and r9, the optimal place for data might be determined by a later function call. Some registers are guaranteed to be preserved across a function call, but others are not, which limits the lifetime of registers. At some point this becomes like most compiler optimizations, where the compiler has to balance competing factors: is the benefit of having this value in edi to perform an iteration worth the cost of pushing other data onto the stack to make way for it? Etc.
I agree, there are things that I left out, especially in regards to applying this to a real system. I didn’t want to muddy up the idea with some of the nuances that complex ISAs have. Linear scan does a pretty terrible job at keeping track of these things, so most “real” compilers using it (LLVM < 3) have a second rewrite stage. LLVM is very interesting in this regard because the current algorithm they use is very similar to linear scanning in terms of its greedy roots, and the heuristic weights for choosing a register to assign or spill are generated by analyzing the code. It does not need to go back and forth, because the “weightings” are pre-determined. I’m interested to see how LLVM handles limited instructions as you mentioned, I’ve never thought deeply about that.
Linear-scan register allocation is linear in the number of nodes in the control flow graph. Is there an algorithm that is linear in the number of edges? This would be an interesting middle ground between linear scan and graph colouring.
I read a comment on HN claiming that LLVM uses a neural net for register allocation - can anyone here confirm (ideally with some kind of a reference/citation link) or deny?
Sort of, LLVM has their own improvement upon the basic linear scanning algorithm which allows for multiple different weights and heuristics along the way. They use something called a hopfield network, a 1 layer NN, to determine which variable gets spilled.There’s also been research, not under LLVM as far as I’m aware, on using neural networks to decide which algorithm to run at compile time.
This article seems a little oversimplified. In a complex ISA like x86, some instructions expect things to be in particular registers, or write to particular registers. Some instructions can operate on multiple registers, but not all registers. Some constraints exist by convention, because if a function calling convention places the first four arguments in rcx, rdx, r8 and r9, the optimal place for data might be determined by a later function call. Some registers are guaranteed to be preserved across a function call, but others are not, which limits the lifetime of registers. At some point this becomes like most compiler optimizations, where the compiler has to balance competing factors: is the benefit of having this value in edi to perform an iteration worth the cost of pushing other data onto the stack to make way for it? Etc.
I agree, there are things that I left out, especially in regards to applying this to a real system. I didn’t want to muddy up the idea with some of the nuances that complex ISAs have. Linear scan does a pretty terrible job at keeping track of these things, so most “real” compilers using it (LLVM < 3) have a second rewrite stage. LLVM is very interesting in this regard because the current algorithm they use is very similar to linear scanning in terms of its greedy roots, and the heuristic weights for choosing a register to assign or spill are generated by analyzing the code. It does not need to go back and forth, because the “weightings” are pre-determined. I’m interested to see how LLVM handles limited instructions as you mentioned, I’ve never thought deeply about that.
Linear-scan register allocation is linear in the number of nodes in the control flow graph. Is there an algorithm that is linear in the number of edges? This would be an interesting middle ground between linear scan and graph colouring.
I read a comment on HN claiming that LLVM uses a neural net for register allocation - can anyone here confirm (ideally with some kind of a reference/citation link) or deny?
Sort of, LLVM has their own improvement upon the basic linear scanning algorithm which allows for multiple different weights and heuristics along the way. They use something called a hopfield network, a 1 layer NN, to determine which variable gets spilled.There’s also been research, not under LLVM as far as I’m aware, on using neural networks to decide which algorithm to run at compile time.
Sources: https://www.slideshare.net/mobile/chimerawang/llvm-register-allocation-59885569 https://llvm.org/doxygen/SpillPlacement_8cpp_source.html