2 ms·
Register allocation is a solved problem. The optimal solution can be found in polynomial time for SSA code. SIMD is no different.
by pcwalton 9y ago
Register allocation is a solved problem. The optimal solution can be found in polynomial time for SSA code. SIMD is no different.
- acqq 9y agoSolved in the papers or in the available products? Can you please write a little more?
- DSrcl 9y agoRegister allocation in general is np-complete[1][2]. Having polynomial-time coloring algorithm for SSA doesn't make the allocation optimal -- you still need to "lower" the SSA to proper machine code. [1] http://www.cs.cmu.edu/afs/cs/academic/class/15745-s07/www/papers/pereira-fossacs06.pdf http://www.cs.cmu.edu/afs/cs/academic/class/15745-s07/www/pa... [2] http://pharm.ece.wisc.edu/wddd/2006/papers/wddd_05.pdf http://pharm.ece.wisc.edu/wddd/2006/papers/wddd_05.pdf