reg.c

   1 /* neatcc global register allocation */
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include "ncc.h"
   5
   6 #define IC_LOC(ic, i)           ((ic)[i].arg1)
   7 #define IC_LLD(ic, i)           (O_C((ic)[i].op) == (O_LD | O_LOC))
   8 #define IC_LST(ic, i)           (O_C((ic)[i].op) == (O_ST | O_LOC))
   9
  10 /* local live region */
  11 struct rgn {
  12         long loc;       /* local number */
  13         long beg;       /* region start (instruction number) */
  14         long end;       /* region end */
  15         long cnt;       /* number of accesses */
  16         int reg;        /* register allocated to this region */
  17 };
  18
  19 static struct rgn *rgn;         /* live regions */
  20 static int rgn_n;               /* number of entries in rgn[] */
  21 static int rgn_sz;              /* size of rgn[] */
  22
  23 static int *loc_ptr;            /* if the address of locals is accessed */
  24 static int loc_n;               /* number of locals */
  25
  26 static long *dst_head;          /* lists of jumps to each instruction */
  27 static long *dst_next;          /* next entries in dst_head[] lists */
  28
  29 static void rgn_add(long loc, long beg, long end, long cnt)
  30 {
  31         int i;
  32         for (i = 0; i < rgn_n; i++) {
  33                 if (rgn[i].loc == loc && rgn[i].beg < end && rgn[i].end > beg) {
  34                         if (beg > rgn[i].beg)
  35                                 beg = rgn[i].beg;
  36                         if (end < rgn[i].end)
  37                                 end = rgn[i].end;
  38                         cnt += rgn[i].cnt;
  39                         rgn[i].loc = -1;
  40                 }
  41         }
  42         for (i = 0; i < rgn_n; i++)
  43                 if (rgn[i].loc < 0)
  44                         break;
  45         if (i == rgn_n) {
  46                 if (rgn_n >= rgn_sz) {
  47                         rgn_sz = MAX(16, rgn_sz * 2);
  48                         rgn = mextend(rgn, rgn_n, rgn_sz, sizeof(rgn[0]));
  49                 }
  50                 rgn_n++;
  51         }
  52         rgn[i].loc = loc;
  53         rgn[i].beg = beg;
  54         rgn[i].end = end;
  55         rgn[i].cnt = cnt;
  56         rgn[i].reg = -1;
  57 }
  58
  59 /* return nonzero if register reg is free from beg till end */
  60 static int rgn_available(long beg, long end, int reg)
  61 {
  62         int i;
  63         for (i = 0; i < rgn_n; i++)
  64                 if (rgn[i].reg == reg)
  65                         if (rgn[i].beg < end && rgn[i].end > beg)
  66                                 return 0;
  67         return 1;
  68 }
  69
  70 static long reg_region(struct ic *ic, long ic_n, long loc, long pos,
  71                 long *beg, long *end, char *mark)
  72 {
  73         long cnt = 0;
  74         long dst;
  75         for (; pos >= 0; pos--) {
  76                 if (pos < *beg)
  77                         *beg = pos;
  78                 if (pos + 1 > *end)
  79                         *end = pos + 1;
  80                 if (mark[pos])
  81                         break;
  82                 mark[pos] = 1;
  83                 if (IC_LST(ic, pos) && IC_LOC(ic, pos) == loc)
  84                         break;
  85                 if (IC_LLD(ic, pos) && IC_LOC(ic, pos) == loc)
  86                         cnt++;
  87                 dst = dst_head[pos];
  88                 while (dst >= 0) {
  89                         cnt += reg_region(ic, ic_n, loc, dst, beg, end, mark);
  90                         dst = dst_next[dst];
  91                 }
  92                 if (pos > 0 && ic[pos - 1].op & O_JMP)
  93                         break;
  94         }
  95         return cnt;
  96 }
  97
  98 /* compute local's live regions */
  99 static void reg_regions(struct ic *ic, long ic_n, long loc)
 100 {
 101         char *mark;
 102         long beg, end;
 103         long cnt;
 104         long i;
 105         mark = calloc(ic_n, sizeof(mark[0]));
 106         for (i = 0; i < ic_n; i++) {
 107                 if (IC_LLD(ic, i) && IC_LOC(ic, i) == loc && !mark[i]) {
 108                         beg = i;
 109                         end = i + 1;
 110                         cnt = reg_region(ic, ic_n, loc, i, &beg, &end, mark);
 111                         rgn_add(loc, beg, end, cnt);
 112                 }
 113         }
 114         for (i = 0; i < ic_n; i++)
 115                 if (IC_LST(ic, i) && IC_LOC(ic, i) == loc && !mark[i])
 116                         rgn_add(loc, i, i + 1, 1);
 117         free(mark);
 118 }
 119
 120 /* perform global register allocation */
 121 static void reg_glob(int leaf)
 122 {
 123         int *srt;
 124         int regs[N_REGS];
 125         int i, j;
 126         int regs_max = MIN(N_TMPS >> 1, 4);
 127         long regs_mask = leaf ? R_TMPS : R_PERM;
 128         int regs_n = 0;
 129         for (i = leaf ? 1 : 3; i < N_TMPS && regs_n < regs_max; i++)
 130                 if ((1 << i) & regs_mask)
 131                         regs[regs_n++] = i;
 132         srt = malloc(rgn_n * sizeof(srt[0]));
 133         /* sorting locals */
 134         for (i = 0; i < rgn_n; i++) {
 135                 for (j = i - 1; j >= 0 && rgn[i].cnt > rgn[srt[j]].cnt; j--)
 136                         srt[j + 1] = srt[j];
 137                 srt[j + 1] = i;
 138         }
 139         /* allocating registers */
 140         for (i = 0; i < rgn_n; i++) {
 141                 int r = srt[i];
 142                 long loc = rgn[r].loc;
 143                 long beg = rgn[r].beg;
 144                 long end = rgn[r].end;
 145                 if (loc < 0 || loc_ptr[loc])
 146                         continue;
 147                 if (leaf && loc < N_ARGS && beg == 0 &&
 148                                 rgn_available(beg, end, argregs[loc])) {
 149                         rgn[r].reg = argregs[loc];
 150                         continue;
 151                 }
 152                 for (j = 0; j < regs_n; j++)
 153                         if (rgn_available(beg, end, regs[j]))
 154                                 break;
 155                 if (j < regs_n)
 156                         rgn[r].reg = regs[j];
 157         }
 158         free(srt);
 159 }
 160
 161 void reg_init(struct ic *ic, long ic_n)
 162 {
 163         int *loc_sz;
 164         int leaf = 1;
 165         long i;
 166         for (i = 0; i < ic_n; i++)
 167                 if (ic[i].op & O_LOC && loc_n < IC_LOC(ic, i) + 1)
 168                         loc_n = IC_LOC(ic, i) + 1;
 169         loc_ptr = calloc(loc_n, sizeof(loc_ptr[0]));
 170         loc_sz = calloc(loc_n, sizeof(loc_sz[0]));
 171         for (i = 0; i < ic_n; i++) {
 172                 long oc = O_C(ic[i].op);
 173                 if (oc == (O_LD | O_LOC) || oc == (O_ST | O_LOC)) {
 174                         int loc = IC_LOC(ic, i);
 175                         int sz = T_SZ(O_T(ic[i].op));
 176                         if (!loc_sz[loc])
 177                                 loc_sz[loc] = sz;
 178                         if (ic[i].arg2 || sz < 2 || sz != loc_sz[loc])
 179                                 loc_ptr[loc]++;
 180                 }
 181                 if (oc == (O_MOV | O_LOC))
 182                         loc_ptr[IC_LOC(ic, i)]++;
 183         }
 184         free(loc_sz);
 185         for (i = 0; i < ic_n; i++)
 186                 if (ic[i].op & O_CALL)
 187                         leaf = 0;
 188         dst_head = malloc(ic_n * sizeof(dst_head[0]));
 189         dst_next = malloc(ic_n * sizeof(dst_next[0]));
 190         for (i = 0; i < ic_n; i++)
 191                 dst_head[i] = -1;
 192         for (i = 0; i < ic_n; i++)
 193                 dst_next[i] = -1;
 194         for (i = 0; i < ic_n; i++) {
 195                 if (ic[i].op & O_JXX) {
 196                         dst_next[i] = dst_head[ic[i].arg2];
 197                         dst_head[ic[i].arg2] = i;
 198                 }
 199         }
 200         for (i = 0; i < loc_n; i++)
 201                 if (!loc_ptr[i])
 202                         reg_regions(ic, ic_n, i);
 203         reg_glob(leaf);
 204 }
 205
 206 long reg_mask(void)
 207 {
 208         long ret = 0;
 209         int i;
 210         for (i = 0; i < rgn_n; i++)
 211                 if (rgn[i].reg >= 0)
 212                         ret |= 1 << rgn[i].reg;
 213         return ret;
 214 }
 215
 216 /* return the allocated register of local loc */
 217 int reg_lmap(long c, long loc)
 218 {
 219         int i;
 220         for (i = 0; i < rgn_n; i++)
 221                 if (rgn[i].loc == loc)
 222                         if (rgn[i].beg <= c && rgn[i].end > c)
 223                                 return rgn[i].reg;
 224         return -1;
 225 }
 226
 227 /* return the local to which register reg is allocated */
 228 int reg_rmap(long c, long reg)
 229 {
 230         int i;
 231         for (i = 0; i < rgn_n; i++)
 232                 if (rgn[i].reg == reg)
 233                         if (rgn[i].beg <= c && rgn[i].end > c)
 234                                 return rgn[i].loc;
 235         return -1;
 236 }
 237
 238 void reg_done(void)
 239 {
 240         free(dst_head);
 241         free(dst_next);
 242         free(loc_ptr);
 243         free(rgn);
 244         loc_ptr = NULL;
 245         rgn = NULL;
 246         rgn_sz = 0;
 247         rgn_n = 0;
 248         loc_n = 0;
 249 }
 250
 251 int reg_safe(long loc)
 252 {
 253         return loc < loc_n && !loc_ptr[loc];
 254 }