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 /* number of times a local is accessed */
 136 static long reg_loccnt(struct ic *ic, long ic_n, long loc)
 137 {
 138         long cnt = 0;
 139         long i;
 140         for (i = 0; i < ic_n; i++)
 141                 if (IC_LLD(ic, i) == loc || IC_LST(ic, i) == loc)
 142                         cnt++;
 143         return cnt;
 144 }
 145
 146 /* perform global register allocation */
 147 static void reg_glob(int leaf)
 148 {
 149         int *srt;
 150         int regs[N_REGS];
 151         int i, j;
 152         int regs_max = MIN(N_TMPS >> 1, 4);
 153         long regs_mask = leaf ? R_TMPS : R_PERM;
 154         int regs_n = 0;
 155         for (i = leaf ? 1 : 3; i < N_TMPS && regs_n < regs_max; i++)
 156                 if ((1 << i) & regs_mask)
 157                         regs[regs_n++] = i;
 158         srt = malloc(rgn_n * sizeof(srt[0]));
 159         /* sorting locals */
 160         for (i = 0; i < rgn_n; i++) {
 161                 for (j = i - 1; j >= 0 && rgn[i].cnt > rgn[srt[j]].cnt; j--)
 162                         srt[j + 1] = srt[j];
 163                 srt[j + 1] = i;
 164         }
 165         /* allocating registers */
 166         for (i = 0; i < rgn_n; i++) {
 167                 int r = srt[i];
 168                 long loc = rgn[r].loc;
 169                 long beg = rgn[r].beg;
 170                 long end = rgn[r].end;
 171                 if (loc < 0 || loc_ptr[loc])
 172                         continue;
 173                 if (leaf && loc < N_ARGS && beg == 0 &&
 174                                 rgn_available(beg, end, argregs[loc])) {
 175                         rgn[r].reg = argregs[loc];
 176                         continue;
 177                 }
 178                 for (j = 0; j < regs_n; j++)
 179                         if (rgn_available(beg, end, regs[j]))
 180                                 break;
 181                 if (j < regs_n)
 182                         rgn[r].reg = regs[j];
 183         }
 184         free(srt);
 185 }
 186
 187 void reg_init(struct ic *ic, long ic_n)
 188 {
 189         long loc, off;
 190         int *loc_sz;
 191         int leaf = 1;
 192         long i;
 193         for (i = 0; i < ic_n; i++)
 194                 if (ic[i].op & O_LOC && !ic_loc(ic, i, &loc, &off))
 195                         if (loc + 1 >= loc_n)
 196                                 loc_n = loc + 1;
 197         loc_ptr = calloc(loc_n, sizeof(loc_ptr[0]));
 198         loc_sz = calloc(loc_n, sizeof(loc_sz[0]));
 199         for (i = 0; i < loc_n; i++)
 200                 loc_ptr[i] = !opt(1);
 201         for (i = 0; i < ic_n; i++) {
 202                 long oc = O_C(ic[i].op);
 203                 if (ic_loc(ic, i, &loc, &off))
 204                         continue;
 205                 if (oc == (O_LD | O_LOC) || oc == (O_ST | O_LOC)) {
 206                         int sz = T_SZ(O_T(ic[i].op));
 207                         if (!loc_sz[loc])
 208                                 loc_sz[loc] = sz;
 209                         if (off || sz < 2 || sz != loc_sz[loc])
 210                                 loc_ptr[loc]++;
 211                 }
 212                 if (oc == (O_MOV | O_LOC))
 213                         loc_ptr[loc]++;
 214         }
 215         free(loc_sz);
 216         for (i = 0; i < ic_n; i++)
 217                 if (ic[i].op & O_CALL)
 218                         leaf = 0;
 219         dst_head = malloc(ic_n * sizeof(dst_head[0]));
 220         dst_next = malloc(ic_n * sizeof(dst_next[0]));
 221         for (i = 0; i < ic_n; i++)
 222                 dst_head[i] = -1;
 223         for (i = 0; i < ic_n; i++)
 224                 dst_next[i] = -1;
 225         for (i = 0; i < ic_n; i++) {
 226                 if (ic[i].op & O_JXX) {
 227                         dst_next[i] = dst_head[ic[i].a3];
 228                         dst_head[ic[i].a3] = i;
 229                 }
 230         }
 231         for (i = 0; i < loc_n; i++) {
 232                 if (!loc_ptr[i] && opt(2))
 233                         reg_regions(ic, ic_n, i);
 234                 if (!loc_ptr[i] && !opt(2))
 235                         rgn_add(i, 0, ic_n, reg_loccnt(ic, ic_n, i));
 236         }
 237         reg_glob(leaf);
 238 }
 239
 240 long reg_mask(void)
 241 {
 242         long ret = 0;
 243         int i;
 244         for (i = 0; i < rgn_n; i++)
 245                 if (rgn[i].reg >= 0)
 246                         ret |= 1 << rgn[i].reg;
 247         return ret;
 248 }
 249
 250 /* return the allocated register of local loc */
 251 int reg_lmap(long c, long loc)
 252 {
 253         int i;
 254         for (i = 0; i < rgn_n; i++)
 255                 if (rgn[i].loc == loc)
 256                         if (rgn[i].beg <= c && rgn[i].end > c)
 257                                 return rgn[i].reg;
 258         return -1;
 259 }
 260
 261 /* return the local to which register reg is allocated */
 262 int reg_rmap(long c, long reg)
 263 {
 264         int i;
 265         for (i = 0; i < rgn_n; i++)
 266                 if (rgn[i].reg == reg)
 267                         if (rgn[i].beg <= c && rgn[i].end > c)
 268                                 return rgn[i].loc;
 269         return -1;
 270 }
 271
 272 void reg_done(void)
 273 {
 274         free(dst_head);
 275         free(dst_next);
 276         free(loc_ptr);
 277         free(rgn);
 278         loc_ptr = NULL;
 279         rgn = NULL;
 280         rgn_sz = 0;
 281         rgn_n = 0;
 282         loc_n = 0;
 283 }
 284
 285 int reg_safe(long loc)
 286 {
 287         return loc < loc_n && !loc_ptr[loc];
 288 }