logoalt Hacker News

ebiederm • yesterday at 6:07 PM • 1 reply • view on HN

The academic literature on register allocation is scary.

First is presented a linear time optimal algorithm for graph coloring then it is claimed better can be done by a O(N^2) algorithm that uses a heuristic.

I do believe the dragon book got caught with the emperor's new register allocator and the literature hasn't really recovered yet.

Replies

mrkeen • yesterday at 8:23 PM

I didn't believe the optimal algorithm is linear time, so I checked the source:

  a simple register allocation algorithm can achieve most ot the performance of the more complex algorithms: linear-scan register allocation, developed by Poletto and Sarkar
"Most of the performance" is not optimal. Were you referring to a different source?
➕ show 1 reply