| | 1 | The Poletto-Sarkar linear scan register allocator ([http://www.cs.ucla.edu/~palsberg/course/cs132/linearscan.pdf]) is reasonably efficient, reasonably effective, easy to implement, and suitable for an infinite register machine such as Parrot. It requires scanning a compilation unit linearly once to find liveness intervals for all unique registers. In pseudo-code: |
| | 2 | |
| | 3 | * Walk through all instructions, start to finish in linear order of appearance in the source code |
| | 4 | * For every register reference found: |
| | 5 | * Add the register to a list indexed by its start position, if it does not exist in list |
| | 6 | * Update the register's last position, if it's already in the list |
| | 7 | * After the linear scan has finished, walk the list |
| | 8 | * At every start position |
| | 9 | * Fetch the index of the next available register |
| | 10 | * Assign that to the current register reference |
| | 11 | * At every end position: |
| | 12 | * Recycle the index of the register reference |
| | 13 | |
| | 14 | This should be robust even in the face of calls and branches, both forward and backwards. It should survive manual register allocation (though at some potential performance degradation). It does not require identifying or tracking basic blocks. It could work concurrently with PIR emission from POST. It appears to use the most efficient total number of registers, even if it does not arrange them in any particular order (such is the job of the register number recycler). It does not require the use of SSA, but it does not preclude it. |
