Register allocation

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.

The interval construction takes place in the bottom half of this file baste-pass3.church and the register allocator is in baste-pass4.church

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] 


One Reply to “Register allocation”

Comments are closed.