I am wondering if there is an optimal algorithm for register allocation in a pure dataflow scenario (or any papers pursuing as much).
The case I am interested in is all local register allocation with no phi nodes or CFG edges.
The optimization questions, as far as I understand it, is how to schedule the instructions s.t the interference graph is as suitable as possible to easy allocation. But haven't found much/anything that hits the nail on the head (aside from this locked papers whose title is intriguing but I can't read)
From looking around, I've found the Sethi & Ullman Algorithm but after implementing it, I've found it's not what I'm looking for.
The closest I've found in this MCFN register allocation schema (proposed for global register allocation, but should be applicable to local register allocation).
If anyone knows an algorithm or paper that points to one I would much appreciated.
For reference the best I'm able to do now is use strahler numbering to choose node traversal and breaking ties by total number of children. Then between each iteration scheduling each instruction that ends the live-range of more registers than it creates.