reg.c

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