I’ve been reading a lot about register allocation algorithms, register allocation is probably one of the most complex parts of a compiler.
A SURVEY OF REGISTER ALLOCATION TECHNIQUES by Jonathan Protzenko is a great overview of what algorithms are suited to a particular compilation scenario.
I focused on the family of linear-scan register allocators first proposed by Poletto and Sarkar. The `c compiler has a really clean implementation of linear scan in C but I discovered later that the machine architectures that they targeted are all “register-rich” architectures which can easily accommodate a few registers reserved as “scratch registers”. Since I think that the “register poor” 32-bit x86 code is still important I researched more complex algorithms such as Linear scan with Interval Splitting and Extended Linear Scan.
Initially I was hoping for a really lightweight algorithm that could be used for generating code on the fly with the potential for an optimizing compiler to kick in later when necessary. As I implemented some of the interval splitting logic I realised that the implementation was getting too complex and I decided to fall back to a simple linear scan algorithm that uses an SCC (Strongly Connected Components) analysis to determine interval lifetimes. The implementation (on 64-bit x86) requires three scratch registers to be reserved and should probably be reconsidered for a 32-bit implementation.
The SCC analysis works by tracing out the control flow of the basic blocks and determines sets where each node can reach every other node. These are loops. Identifying loops is important for the lifetime of a variable because you need to keep it alive up until the end of the loop and at the top of the loop until the first use.
The intervals calculated by SCC are very coarse and as a result the allocator generates a lot of spills that could be avoided with a more fine-grained analysis or through interval splitting.
I implemented some rough visualizations of the interval lifetimes and allocations, unfortunately it doesn’t display very well here. Each range has a hex number indicating which register is has been allocated or “S” if it is spilled. On x86-64 we have to be careful to preserve function arguments which are passed via register (and also used in calls). I do this with “fixed intervals” which guarantee that a specific register is available for these special cases.
Int. M Spill Reg Ranges v26(f) 7777777777777777777777777 [0-24] v25(e) 8888888888888888888888888 [0-24] v24(d) 9999999999999999999999999 [0-24] v23(c) AAAAAAAAAAAAAAAAAAAAAAAAA [0-24] v22(b) BBBBBBBBBBBBBBBBBBBBBBBBB [0-24] v21(a) CCCCCCCCCCCCCCCCCCCCCCCCC [0-24] v5 5555555555555555555555555 [0-24] v4 44444444444444444444444 [0-22] v3 333333333333333333333 [0-20] v2 2222222222222222222 [0-18] v1 11111111111111111 [0-16] v0 000000000000000 [0-14] v15(x) 88888888888888888888888 [26-48] v27 777777 [26-31] v31 77777777777777777 [32-48] v30 99999999999999999 [32-48] v29 AAAAAAAAAAAAAAAAA [32-48] v28 BBBBBBBBBBBBBBBBB [32-48] v32 CCCC [48-51] v16(y) 88888888888888888888888 [52-74] v33 CCCCCC [52-57] v37 CCCCCCCCCCCCCCCCC [58-74] v36 77777777777777777 [58-74] v35 99999999999999999 [58-74] v34 AAAAAAAAAAAAAAAAA [58-74] v38 BBBB [74-77] v17(z) 88888888888888888888888 [78-100] v39 BBBBBB [78-83] v43 BBBBBBBBBBBBBBBBB [84-100] v42 CCCCCCCCCCCCCCCCC [84-100] v41 77777777777777777 [84-100] v40 99999999999999999 [84-100] v44 AAAA [100-103] v18(x1) 88888888888888888888888 [104-126] v45 AAAAAA [104-109] v49 AAAAAAAAAAAAAAAAA [110-126] v48 BBBBBBBBBBBBBBBBB [110-126] v47 CCCCCCCCCCCCCCCCC [110-126] v46 77777777777777777 [110-126] v50 9999 [126-129] v19(x2) 88888888888888888888888 [130-152] v51 999999 [130-135] v55 99999999999999999 [136-152] v54 AAAAAAAAAAAAAAAAA [136-152] v53 BBBBBBBBBBBBBBBBB [136-152] v52 CCCCCCCCCCCCCCCCC [136-152] v56 7777 [152-155] v20(x3) 88888888888888888888888 [156-178] v57 777777 [156-161] v61 77777777777777777 [162-178] v60 99999999999999999 [162-178] v59 AAAAAAAAAAAAAAAAA [162-178] v58 BBBBBBBBBBBBBBBBB [162-178] v62 CCCC [178-181] v63 CCCCCCC [182-188]