reg.c

   1 /* neatcc register allocation */
   2 #include <stdio.h>
   3 #include <string.h>
   4 #include "gen.h"
   5 #include "ncc.h"
   6 #include "reg.h"
   7
   8 static int l_sz[NLOCALS];       /* size of locals */
   9 static int l_nr[NLOCALS];       /* # of reads */
  10 static int l_nw[NLOCALS];       /* # of writes */
  11 static int l_na[NLOCALS];       /* # of address accesses */
  12 static int l_reg[NLOCALS];      /* register mapped to locals */
  13 static int l_n;                 /* # of locals */
  14
  15 static int f_argc;              /* number of arguments */
  16 static int f_varg;              /* function has variable argument list */
  17 static int f_lregs;             /* mask of R_TMPS allocated to locals */
  18 static int f_sargs;             /* mask of R_ARGS to be saved */
  19
  20 void r_func(int nargs, int varg)
  21 {
  22         int i;
  23         f_varg = varg;
  24         f_argc = nargs;
  25         f_lregs = 0;
  26         l_n = 0;
  27         for (i = 0; i < f_argc; i++)
  28                 r_mk(LONGSZ);
  29         f_sargs = f_varg ? R_ARGS : 0;
  30         for (i = 0; i < f_argc && i < N_ARGS; i++)
  31                 f_sargs |= 1 << argregs[i];
  32 }
  33
  34 void r_mk(int sz)
  35 {
  36         if (!f_lregs) {
  37                 l_sz[l_n] = sz;
  38                 l_nr[l_n] = 0;
  39                 l_nw[l_n] = 0;
  40                 l_na[l_n] = 0;
  41                 l_reg[l_n] = -1;
  42                 l_n++;
  43         }
  44 }
  45
  46 void r_rm(int id)
  47 {
  48 }
  49
  50 void r_read(int id)
  51 {
  52         l_nr[id]++;
  53 }
  54
  55 void r_write(int id)
  56 {
  57         l_nw[id]++;
  58 }
  59
  60 void r_addr(int id)
  61 {
  62         l_na[id]++;
  63 }
  64
  65 void r_label(int l)
  66 {
  67 }
  68
  69 void r_jmp(int l)
  70 {
  71 }
  72
  73 int r_regmap(int id)
  74 {
  75         return l_reg[id];
  76 }
  77
  78 int r_lregs(void)
  79 {
  80         return f_lregs;
  81 }
  82
  83 int r_sargs(void)
  84 {
  85         return f_sargs;
  86 }
  87
  88 /* sort locals for register allocation based on the number of accesses */
  89 static int *sortedlocals(void)
  90 {
  91         static int ord[NLOCALS];
  92         int i, j;
  93         for (i = 0; i < l_n; i++) {
  94                 for (j = i - 1; j >= 0; j--) {
  95                         if (l_nr[i] + l_nw[i] <= l_nw[ord[j]] + l_nr[ord[j]])
  96                                 break;
  97                         ord[j + 1] = ord[j];
  98                 }
  99                 ord[j + 1] = i;
 100         }
 101         return ord;
 102 }
 103
 104 int r_alloc(int leaf, int used)
 105 {
 106         int nlocregs = 0;
 107         int *ord = sortedlocals();
 108         int idx = 0;
 109         int i;
 110         f_lregs = 0;
 111         f_sargs = f_varg ? R_ARGS : 0;
 112         /* except unused arguments, save all arguments on the stack */
 113         for (i = 0; i < f_argc && i < N_ARGS; i++)
 114                 if (f_varg || l_nr[i] + l_nw[i] + l_na[i])
 115                         f_sargs |= 1 << argregs[i];
 116         /* letting arguments stay in their registers for leaf functions */
 117         if (!f_varg && leaf) {
 118                 for (i = 0; i < f_argc && i < N_ARGS; i++) {
 119                         if (l_sz[i] > LONGSZ || (1 << argregs[i]) & used)
 120                                 continue;
 121                         if (l_nr[i] + l_nw[i] && !l_na[i]) {
 122                                 l_reg[i] = argregs[i];
 123                                 f_sargs &= ~(1 << argregs[i]);
 124                                 f_lregs |= (1 << argregs[i]);
 125                                 nlocregs++;
 126                         }
 127                 }
 128         }
 129         /* try finding a register for each local */
 130         for (i = 0; i < l_n; i++) {
 131                 int l = ord[i];
 132                 int nmask = (leaf ? 0 : ~R_SAVED) | used | f_lregs;
 133                 if (l_reg[l] >= 0 || (f_varg && l < f_argc))
 134                         continue;
 135                 /* find a free register */
 136                 while (idx < N_TMPS && ((1 << tmpregs[idx]) & nmask))
 137                         idx++;
 138                 if (idx >= N_TMPS)
 139                         break;
 140                 if (l_sz[l] > LONGSZ || l_na[l])
 141                         continue;
 142                 if (l_nr[l] + l_nw[l] > (leaf ? 0 : 1)) {
 143                         l_reg[l] = tmpregs[idx];
 144                         f_lregs |= 1 << tmpregs[idx];
 145                         if (l < N_ARGS && l < f_argc)
 146                                 f_sargs &= ~(1 << argregs[l]);
 147                         nlocregs++;
 148                         idx++;
 149                 }
 150         }
 151         return nlocregs;
 152 }