Hacker News Reader

Comment by userbinator | Hacker News Reader

Register allocation is a classically hard (NP-hard!) problem

I thought one of the huge advantages of using SSA is linear-time register allocation?

No. First, most compilers actually abandon SSA by the time they begin register allocation through phi elimination, and once you do this you have given up that property. Beyond that, coloring a perfect graph (an SSA graph) can be done in quadratic time, but coloring is not the most interesting part of the process, since you almost always have to insert spills which modifies the interference graph. Register allocation is more than just coloring. On top of that, most ISAs have complications like specific registers needing to be pinned for specific operations, or register aliasing on x86-64, that make things hairier.

In practice, theoretical optimality matters far less than the actual heuristics you use (e.g. avoid spills inside of a loop.)

Whenever one sees "heuristic", I think "Bitter Lesson" [1] and how can we apply brute force computation to the problem.

It would seem like there is still ample space to study the application of neural networks to register allocation. [2] They already gave pretty good results to branch prediction. [3]

What are your thoughts on the application of NN for RA and how would you structure the training set?

[1] http://incompleteideas.net/IncIdeas/BitterLesson.html

[2] https://www.semanticscholar.org/paper/Real-time-physical-reg... I haven't read the paper, just found in a quick search.

[3] https://cseweb.ucsd.edu/~atsmith/rnn_branch.pdf

The second paper you are referencing is not quite what you think it is. It is the application of a neural network to the processor itself, to assist in performing physical register renaming, at runtime, in order to achieve out-of-order execution. This is a very different problem than a compiler's register allocator (for one you're dealing with hundreds of potential registers vs like, 16-30.)

On that topic, NN for branch prediction are, in some sense, nothing new; perceptron and perceptron-based designs have existed for at least 20 years. But I'm not aware of anything concrete or specific in current BP designs as of recently (beyond marketing hype) but I haven't kept up with it; maybe some variation of TAGE with model-assistance is out there, but I'm not sure.

I do not know what a training set or neural network model for performing register allocation on real-world programs would look like at this moment.

The second paper is more of an existence proof that folks are thinking about the problem. From a high level, register file selection and register renaming is similar problem to register allocation in a compiler. The paper itself is dealing with hundreds of virtual registers and how to map them to renamer.

TAGE is what I was thinking of [1,2]. Thanks for the reminder.

I found some relevant research in neural register allocation, "2020 LLVM in HPC Workshop: Deep Learning-based Approx. Graph-Coloring for Register Allocation"

https://www.youtube.com/watch?v=4FW7iznzIoE

There is also some nascent work on applying neural techniques to constraint optimization problems.

[1] https://www.semanticscholar.org/paper/A-case-for-(partially)...

[2] https://www.semanticscholar.org/search?q=TAGE%20branch%20pre...

One can do optimal regalloc over SSA if one doesn't have to spill, or split to make the spilling better, but spilling and splitting are the most interesting and relevant part of practical register allocation -- so in practice this isn't quite true.

Reply on news.ycombinator.com