6 ms·

This is perhaps my favorite Stack Overflow answer of all time. I don't remember when I last saw such an approachable explanation of something so critical yet co

This is perhaps my favorite Stack Overflow answer of all time. I don't remember when I last saw such an approachable explanation of something so critical yet complicated. > One of the canonical approaches, graph coloring, was first proposed in 1981. This is about as far as my professor took this topic in class ~13 years ago. Nevertheless the slides that he used to illustrate how the graph coloring problem applied to register allocation stick with me to this day as one of the most elegant applications of CS I've ever seen (which are admittedly few as I'm not nearly as studied as I ought to be). > Code generation is a surprisingly challenging and underappreciated aspect of compiler implementation, and quite a lot can happen under the hood even after a compiler’s IR optimization pipeline has finished. Register allocation is one of those things, and like many compilers topics, entire books could be written on it alone. Our class final project targeted a register-based VM [1] for this exact reason. I also found writing MIPS assembly simpler than Y86 [2] because of the larger number of registers at my disposal (among the other obvious differences). [1] https://www.lua.org/doc/jucs05.pdf https://www.lua.org/doc/jucs05.pdf [2] https://esolangs.org/wiki/Y86 https://esolangs.org/wiki/Y86

userbinator 2y ago
Unfortunately, just like with parser generators and more powerful parsing algorithms (in particular bottom-up LR and such), the practice proved very different than the theory. Linear-scan and variants of it have become the norm for register allocation.
- virgilp 2y ago
  Is this true though? Last time I worked on a compiler (admittedly quite a few years ago) Briggs was the bare minimum; our compiler in particular used an improvement over Callahan's hierarchical register allocation (the basic idea of which is that you should prioritize allocation in innermost loops, over a better "global" graph coloring, since spilling once in the inner loop costs way more than spilling several registers in the linear/ setup part of the code). I would expect that only compilers for immature languages (that don't care about optimization) use naive RA.
  - Leszek 2y ago
    Or JIT compilers, where compilation time is an important factor -- e.g. V8 uses variations on linear scan.
- Sharlin 2y ago
  At least GCC appears to use a graph coloring algorithm. LLVM seems to have moved from linear scan to a custom algorithm in version 3; I have no idea what they're using nowadays.
  - deleted 2y ago
    [deleted]
  - cyco130 2y ago
    LLVM now uses something they call the "Greedy Register Allocator". As far as I can tell, it's a variation on the linear allocator with some heuristics. Here's a presentation: https://www.youtube.com/watch?v=hf8kD-eAaxg https://www.youtube.com/watch?v=hf8kD-eAaxg
- fweimer 2y ago
  GCC uses a region-based allocator with graph coloring, based to some extent on Callahan/Koblenz's work I think: https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=gcc/ira.cc https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=gcc/ira.cc Note that in the GCC context, LRA means Local Register Allocator, not linear scan: https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=gcc/lra.cc https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=gcc/lra.cc (There was much more talk recently of GCC's LRA than IRA because completing the reload-to-LRA transition in the compiler threatened the removal of some targets still without reload support.)
  - thechao 2y ago
    I've had a lot of success using chordal graph allocators. They provide plenty of extra dimensions of 'relaxation' to tune them, they're incremental (so they allow pinning), and they decay nicely when their constraints are violated. Because of their incremental nature & "niceness" of decay, they can be forced into a nice hierarchical form ("middle out" on the loops). The main driving algorithm (maximum cardinality search) is a little harebrained; but, if you just relax and write up the code, you'll find it is surprisingly short & robust, and highly amenable to unit testing. Spilling/filling is a bit exciting, since chordal coloring doesn't provide a lot of direction, but I've found that pressure heuristics fill in the gap nicely. The whole thing relies on having a robust interference graph — which more than kind of sucks — but, we don't get into compilers unless we've weaponized our bit-set data-structures in the first place.
saagarjha 2y ago
Compilers are of course on of the purest applications of theoretical computer science.
- stkdump 2y ago
  Just that none of the parsing methods I learned are actually used commonly in most real compilers.
  - saagarjha 2y ago
    Applying pure computer science to real-world problems is of course its own field of study ;)
artemonster 2y ago
[flagged]
qwery 2y ago
> Stack Overflow This is on 'Programming Language Design and Implementation Stack Exchange'[0] -- I'm not pointing this out to tell you that you're wrong -- I think the various 'Stacks Exchange' often have better, more thoughtful answers than the average Stack Overflow question. [0] really rolls off the tongue
- travisgriggs 2y ago
  Amen to that. It’s amazing (to me) the difference in cultures of the different exchanges. I see some of the most awesome answers and explanations on aviation SE. Whereas I rarely try to post (answer or question) to SO anymore, because it feels like navigating the DMV.
- smcin 2y ago
  For more theoretical and pure CS stuff, yes they do since some point between ~2012-5 when SO got overrun by web developers and people grinding coding challenges. And of course the mushrooming number of specialist SE network sites [https://stackexchange.com/sites https://stackexchange.com/sites] like PLD, Theoretical CS, CodeReview, Computational Science, DBA, SWE, CrossValidated etc. + SO in several non-English languages [https://stackoverflow.com/help/non-english-questions https://stackoverflow.com/help/non-english-questions]. Even the standards of behavior between different tags on SO itself vary greatly (in terms of how well-written a question is, whether it has an MCVE, whether the OP check it wasn't a dupe and searched existing Q&A, etc.). If you want to chronicle the descent, look at Meta posts about "give me teh codez"-type questions [https://meta.stackoverflow.com/search?q=%22give+me+teh+codez%22 https://meta.stackoverflow.com/search?q=%22give+me+teh+codez...].
- mhh__ 2y ago
  Stackexchanges are some of favourite things to idly read. Short, snappy, nice LaTeX and so on. And then you sometimes you have just sublimely creative people answering e.g. Ron Maimon's answers on physics SE are a goldmine
  - mhh__ 2y ago
    This is actually also the main thing I have ChatGPT write for me e.g. I can have it dial the level of mathematics to exactly where I can be bothered to tolerate (sometimes life is too short for symbols)
chowells 2y ago
Oh, it's from Alexis King. No wonder it's written so well.

userbinator 2y ago

Unfortunately, just like with parser generators and more powerful parsing algorithms (in particular bottom-up LR and such), the practice proved very different than the theory. Linear-scan and variants of it have become the norm for register allocation.

virgilp 2y ago
Is this true though? Last time I worked on a compiler (admittedly quite a few years ago) Briggs was the bare minimum; our compiler in particular used an improvement over Callahan's hierarchical register allocation (the basic idea of which is that you should prioritize allocation in innermost loops, over a better "global" graph coloring, since spilling once in the inner loop costs way more than spilling several registers in the linear/ setup part of the code). I would expect that only compilers for immature languages (that don't care about optimization) use naive RA.
- Leszek 2y ago
  Or JIT compilers, where compilation time is an important factor -- e.g. V8 uses variations on linear scan.
Sharlin 2y ago
At least GCC appears to use a graph coloring algorithm. LLVM seems to have moved from linear scan to a custom algorithm in version 3; I have no idea what they're using nowadays.
- deleted 2y ago
  [deleted]
- cyco130 2y ago
  LLVM now uses something they call the "Greedy Register Allocator". As far as I can tell, it's a variation on the linear allocator with some heuristics. Here's a presentation: https://www.youtube.com/watch?v=hf8kD-eAaxg https://www.youtube.com/watch?v=hf8kD-eAaxg
fweimer 2y ago
GCC uses a region-based allocator with graph coloring, based to some extent on Callahan/Koblenz's work I think: https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=gcc/ira.cc https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=gcc/ira.cc Note that in the GCC context, LRA means Local Register Allocator, not linear scan: https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=gcc/lra.cc https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=gcc/lra.cc (There was much more talk recently of GCC's LRA than IRA because completing the reload-to-LRA transition in the compiler threatened the removal of some targets still without reload support.)
- thechao 2y ago
  I've had a lot of success using chordal graph allocators. They provide plenty of extra dimensions of 'relaxation' to tune them, they're incremental (so they allow pinning), and they decay nicely when their constraints are violated. Because of their incremental nature & "niceness" of decay, they can be forced into a nice hierarchical form ("middle out" on the loops). The main driving algorithm (maximum cardinality search) is a little harebrained; but, if you just relax and write up the code, you'll find it is surprisingly short & robust, and highly amenable to unit testing. Spilling/filling is a bit exciting, since chordal coloring doesn't provide a lot of direction, but I've found that pressure heuristics fill in the gap nicely. The whole thing relies on having a robust interference graph — which more than kind of sucks — but, we don't get into compilers unless we've weaponized our bit-set data-structures in the first place.

saagarjha 2y ago

Compilers are of course on of the purest applications of theoretical computer science.

stkdump 2y ago
Just that none of the parsing methods I learned are actually used commonly in most real compilers.
- saagarjha 2y ago
  Applying pure computer science to real-world problems is of course its own field of study ;)

artemonster 2y ago

[flagged]

qwery 2y ago

> Stack Overflow This is on 'Programming Language Design and Implementation Stack Exchange'[0] -- I'm not pointing this out to tell you that you're wrong -- I think the various 'Stacks Exchange' often have better, more thoughtful answers than the average Stack Overflow question. [0] really rolls off the tongue

travisgriggs 2y ago
Amen to that. It’s amazing (to me) the difference in cultures of the different exchanges. I see some of the most awesome answers and explanations on aviation SE. Whereas I rarely try to post (answer or question) to SO anymore, because it feels like navigating the DMV.
smcin 2y ago
For more theoretical and pure CS stuff, yes they do since some point between ~2012-5 when SO got overrun by web developers and people grinding coding challenges. And of course the mushrooming number of specialist SE network sites [https://stackexchange.com/sites https://stackexchange.com/sites] like PLD, Theoretical CS, CodeReview, Computational Science, DBA, SWE, CrossValidated etc. + SO in several non-English languages [https://stackoverflow.com/help/non-english-questions https://stackoverflow.com/help/non-english-questions]. Even the standards of behavior between different tags on SO itself vary greatly (in terms of how well-written a question is, whether it has an MCVE, whether the OP check it wasn't a dupe and searched existing Q&A, etc.). If you want to chronicle the descent, look at Meta posts about "give me teh codez"-type questions [https://meta.stackoverflow.com/search?q=%22give+me+teh+codez%22 https://meta.stackoverflow.com/search?q=%22give+me+teh+codez...].
mhh__ 2y ago
Stackexchanges are some of favourite things to idly read. Short, snappy, nice LaTeX and so on. And then you sometimes you have just sublimely creative people answering e.g. Ron Maimon's answers on physics SE are a goldmine
- mhh__ 2y ago
  This is actually also the main thing I have ChatGPT write for me e.g. I can have it dial the level of mathematics to exactly where I can be bothered to tolerate (sometimes life is too short for symbols)

chowells 2y ago

Oh, it's from Alexis King. No wonder it's written so well.