From edde21b09435101be83efd8e6a7f7a8c6d35fdf4 Mon Sep 17 00:00:00 2001 From: Ali Gholami Rudi Date: Tue, 23 Aug 2016 02:01:44 +0430 Subject: [PATCH] reg: the new global register algorithm --- Makefile | 2 +- gen.c | 210 ++++++++++++++++++++++------------------------------ ncc.c | 1 + ncc.h | 8 ++ reg.c | 254 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 351 insertions(+), 124 deletions(-) create mode 100644 reg.c diff --git a/Makefile b/Makefile index 967fd39..b42a481 100644 --- a/Makefile +++ b/Makefile @@ -5,7 +5,7 @@ CC = cc CFLAGS = -Wall -O2 -DNEATCC_`echo $(OUT) | tr xarm XARM` LDFLAGS = -OBJS = ncc.o tok.o out.o cpp.o gen.o int.o mem.o $(OUT).o +OBJS = ncc.o tok.o out.o cpp.o gen.o int.o reg.o mem.o $(OUT).o all: ncc %.o: %.c ncc.h diff --git a/gen.c b/gen.c index d97ad6f..5a2031c 100644 --- a/gen.c +++ b/gen.c @@ -7,13 +7,15 @@ static struct mem ds; /* data segment */ static struct mem cs; /* code segment */ static long bsslen; /* bss segment size */ +static struct ic *ic; /* current instruction stream */ +static long ic_n; /* number of instructions in ic[] */ +static long ic_i; /* current instruction */ +static long *ic_luse; /* last instruction in which values are used */ static long *loc_off; /* offset of locals on the stack */ static long loc_n, loc_sz; /* number of locals */ static long loc_pos; /* current stack position */ -static int *loc_mem; /* local memory was accessed */ -static int *loc_ptr; /* the address of this local is fetched */ -static int *loc_dat; /* the number of data accesses of this local */ +static int *loc_mem; /* local was accessed on the stack */ static char (*ds_name)[NAMELEN];/* data section symbols */ static long *ds_off; /* data section offsets */ @@ -23,12 +25,10 @@ static int func_argc; /* number of arguments */ static int func_varg; /* varargs */ static int func_regs; /* used registers */ static int func_maxargs; /* the maximum number of arguments on the stack */ -static int func_leaf; /* a leaf function */ static long *ic_bbeg; /* whether each instruction begins a basic block */ static long ra_vmap[N_REGS]; /* register to intermediate value assignments */ static long ra_lmap[N_REGS]; /* register to local assignments */ -static long ra_lmapglob[N_REGS]; /* global register to local assignments */ static long *ra_gmask; /* the mask of good registers for each value */ static long ra_live[NTMPS]; /* live values */ static int ra_vmax; /* the number of values stored on the stack */ @@ -187,28 +187,29 @@ static long ra_regcheap(long mask) ~ra_lmask() & ~ra_vmask()); } -/* allocate registers for a 3-operand instruction */ -static void ra_map(struct ic *ic, int *r0, int *r1, int *r2, long *mt) +/* allocate registers for the current instruction */ +static void ra_map(int *r0, int *r1, int *r2, long *mt) { long m0, m1, m2; + struct ic *c = &ic[ic_i]; long all = 0; - int n = ic_regcnt(ic); - int oc = O_C(ic->op); + int n = ic_regcnt(c); + int oc = O_C(c->op); int i; *r0 = -1; *r1 = -1; *r2 = -1; *mt = 0; /* optimizing loading locals: point to local's register */ - if (oc == (O_LD | O_LOC) && ra_lreg(ic->arg1) >= 0 && - ra_vmap[ra_lreg(ic->arg1)] < 0) { - *r0 = ra_lreg(ic->arg1); + if (oc == (O_LD | O_LOC) && ra_lreg(c->arg1) >= 0 && + ra_vmap[ra_lreg(c->arg1)] < 0) { + *r0 = ra_lreg(c->arg1); func_regs |= 1 << *r0; return; } /* do not use argument registers to hold call destination */ if (oc & O_CALL) - for (i = 0; i < MIN(ic->arg2, N_ARGS); i++) + for (i = 0; i < MIN(c->arg2, N_ARGS); i++) all |= (1 << argregs[i]); /* instructions on locals can be simplified */ if (oc & O_LOC) { @@ -217,33 +218,33 @@ static void ra_map(struct ic *ic, int *r0, int *r1, int *r2, long *mt) if (oc & (O_ST | O_LD)) oc = (oc & ~O_LOC) & O_NUM; } - if (i_reg(ic->op, &m0, &m1, &m2, mt)) - die("neatcc: instruction %08lx not supported\n", ic->op); + if (i_reg(c->op, &m0, &m1, &m2, mt)) + die("neatcc: instruction %08lx not supported\n", c->op); /* * the registers used in global register allocation should not * be used in the last instruction of a basic block. */ - if (ic->op & (O_JZ | O_JCC)) + if (c->op & (O_JZ | O_JCC)) for (i = 0; i < LEN(ra_lmap); i++) - if (ra_lmapglob[i] >= 0 && ra_lmap[i] != ra_lmapglob[i]) + if (reg_rmap(ic_i, i) >= 0 && ra_lmap[i] != reg_rmap(ic_i, i)) all |= (1 << i); /* allocating registers for the operands */ if (n >= 3) { - *r2 = ra_regget(ic->arg2, m2, m2, all); + *r2 = ra_regget(c->arg2, m2, m2, all); all |= (1 << *r2); } if (n >= 2) { - *r1 = ra_regget(ic->arg1, m1, m1, all); + *r1 = ra_regget(c->arg1, m1, m1, all); all |= (1 << *r1); } if (n >= 1 && m0) { - int wop = ic->op & O_OUT; - if (wop && n >= 3 && m0 & (1 << *r2)) + int wop = c->op & O_OUT; + if (wop && n >= 3 && m0 & (1 << *r2) && ic_luse[*r2] <= ic_i) *r0 = *r2; - else if (wop && n >= 2 && m0 & (1 << *r1)) + else if (wop && n >= 2 && m0 & (1 << *r1) && ic_luse[*r1] <= ic_i) *r0 = *r1; else - *r0 = ra_regget(ic->arg0, ra_gmask[ic->arg0], + *r0 = ra_regget(c->arg0, ra_gmask[c->arg0], m0, wop ? 0 : all); } if (n >= 1 && !m0) @@ -251,9 +252,9 @@ static void ra_map(struct ic *ic, int *r0, int *r1, int *r2, long *mt) /* if r0 is overwritten and it is a local; use another register */ if (n >= 1 && oc & O_OUT && ra_lmap[*r0] >= 0) { long m3 = (m0 ? m0 : m1) & ~(all | (1 << *r0)); - long arg3 = m0 ? ic->arg0 : ic->arg1; + long arg3 = m0 ? c->arg0 : c->arg1; if (m3 != 0) { - int r3 = ra_regget(arg3, ra_gmask[ic->arg0], m3, 0); + int r3 = ra_regget(arg3, ra_gmask[c->arg0], m3, 0); if (n >= 2 && *r0 == *r1) *r1 = r3; if (n >= 3 && *r0 == *r2) @@ -299,6 +300,16 @@ static void loc_toadd(long loc, long off, int reg) i_ins(O_ADD | O_NUM, reg, REG_FP, -loc_off[loc] + off); } +/* return nonzero if the local is read at least once in this basic block */ +static int loc_isread(long loc) +{ + int i; + for (i = ic_i + 1; i < ic_n && !ic_bbeg[i]; i++) + if (ic[i].op & O_LOC) + return ic[i].op & O_LD; + return 0; +} + static void val_toreg(long val, int reg) { i_ins(O_MK(O_LD | O_NUM, ULNG), reg, REG_FP, -iv_addr(iv_rank(val))); @@ -319,7 +330,7 @@ static void ra_spill(int reg) ra_vmap[reg] = -1; } if (ra_lmap[reg] >= 0) { - if (ra_lmap[reg] == ra_lmapglob[reg]) + if (ra_lmap[reg] == reg_rmap(ic_i, reg)) loc_tomem(ra_lmap[reg], 0, reg, ULNG); ra_lmap[reg] = -1; } @@ -382,7 +393,23 @@ static void ra_vmove(long iv, long mask) /* load the value of local loc into register reg */ static void ra_lload(long loc, long off, int reg, int bt) { - if (ra_lreg(loc) < 0 && !loc_ptr[loc] && loc_dat[loc] > 2) { + int greg = reg_lmap(ic_i, loc); + if (greg >= 0) { + int lreg = ra_lreg(loc); + /* values using the same register */ + if (ra_vmap[greg] >= 0) + ra_vmove(ra_vmap[greg], + ra_gmask[ra_vmap[greg]] & ~(1 << reg)); + if (lreg >= 0) { + ra_lmap[lreg] = -1; + if (lreg != greg) + i_ins(O_MK(O_MOV, bt), greg, lreg, 0); + } else { + loc_toreg(loc, off, greg, bt); + } + ra_lmap[greg] = loc; + } + if (ra_lreg(loc) < 0 && reg_safe(loc) && loc_isread(loc)) { ra_lmap[reg] = loc; loc_toreg(loc, off, reg, bt); } @@ -398,16 +425,20 @@ static void ra_lload(long loc, long off, int reg, int bt) static void ra_lsave(long loc, long off, int reg, int bt) { int lreg = ra_lreg(loc); - if (lreg >= 0 && ra_lmapglob[lreg] == ra_lmap[lreg]) { - if (ra_vmap[lreg] >= 0) /* values using the same register */ - ra_vmove(ra_vmap[lreg], - ra_gmask[ra_vmap[lreg]] & ~(1 << reg)); - i_ins(O_MK(O_MOV, bt), lreg, reg, 0); + int greg = reg_lmap(ic_i, loc); + if (greg >= 0) { + if (lreg >= 0 && lreg != greg) + ra_lmap[lreg] = -1; + if (ra_vmap[greg] >= 0) /* values using the same register */ + ra_vmove(ra_vmap[greg], + ra_gmask[ra_vmap[greg]] & ~(1 << reg)); + i_ins(O_MK(O_MOV, bt), greg, reg, 0); + ra_lmap[greg] = loc; } else { if (lreg >= 0) ra_lmap[lreg] = -1; loc_tomem(loc, off, reg, bt); - if (!loc_ptr[loc] && loc_dat[loc] > 2 && ra_lmap[reg] < 0) + if (ra_lmap[reg] < 0 && reg_safe(loc) && loc_isread(loc)) ra_lmap[reg] = loc; } } @@ -422,62 +453,20 @@ static void ra_bbend(void) ra_spill(i); /* dropping local caches */ for (i = 0; i < LEN(ra_lmap); i++) - if (ra_lmap[i] != ra_lmapglob[i] && ra_lmap[i] >= 0) + if (ra_lmap[i] != reg_rmap(ic_i, i) && ra_lmap[i] >= 0) ra_spill(i); /* load global register allocations from memory */ for (i = 0; i < LEN(ra_lmap); i++) { - if (ra_lmap[i] != ra_lmapglob[i]) { - ra_lmap[i] = ra_lmapglob[i]; + if (ra_lmap[i] != reg_rmap(ic_i, i)) { + ra_lmap[i] = reg_rmap(ic_i, i); loc_toreg(ra_lmap[i], 0, i, ULNG); } } } -/* perform global register allocation */ -static void ra_glob(struct ic *ic, int ic_n) -{ - int *srt; - long mask; - int nregs; - int i, j; - mask = func_leaf ? R_TMPS : R_PERM; - nregs = MIN(N_TMPS >> 1, 4); - srt = malloc(loc_n * sizeof(srt[0])); - /* sorting locals */ - for (i = 0; i < loc_n; i++) { - for (j = i - 1; j >= 0 && loc_dat[i] > loc_dat[srt[j]]; j--) - srt[j + 1] = srt[j]; - srt[j + 1] = i; - } - /* allocating registers */ - for (i = 0; i < loc_n && nregs > 0; i++) { - int l = srt[i]; - if (loc_ptr[l]) - continue; - if (func_leaf && l < N_ARGS && l < func_argc && - ra_lmapglob[argregs[l]] < 0) { - ra_lmapglob[argregs[l]] = l; - nregs--; - continue; - } - if (loc_dat[l] < 2) - continue; - for (j = func_leaf ? 1 : 3; j < N_TMPS; j++) { - int r = tmpregs[j]; - if (ra_lmapglob[r] < 0 && (1 << r) & mask) { - ra_lmapglob[r] = l; - nregs--; - break; - } - } - } - free(srt); -} - -static void ra_init(struct ic *ic, int ic_n) +static void ra_init(struct ic *ic, long ic_n) { long m0, m1, m2, mt; - int *loc_sz; int i, j; ic_bbeg = calloc(ic_n, sizeof(ic_bbeg[0])); ra_gmask = calloc(ic_n, sizeof(ra_gmask[0])); @@ -504,42 +493,13 @@ static void ra_init(struct ic *ic, int ic_n) for (j = 0; j < MIN(N_ARGS, ic[i].arg2); j++) ra_gmask[ic[i].args[j]] = 1 << argregs[j]; } - /* loc_ptr and loc_dat */ - loc_ptr = calloc(loc_n, sizeof(loc_ptr[0])); - loc_dat = calloc(loc_n, sizeof(loc_dat[0])); - loc_sz = calloc(loc_n, sizeof(loc_sz[0])); - for (i = 0; i < ic_n; i++) { - long oc = O_C(ic[i].op); - if (oc == (O_LD | O_LOC) || oc == (O_ST | O_LOC)) { - int loc = ic[i].arg1; - int sz = T_SZ(O_T(ic[i].op)); - if (!loc_sz[loc]) - loc_sz[loc] = sz; - if (ic[i].arg2 || sz < 2 || sz != loc_sz[loc]) - loc_ptr[loc]++; - else - loc_dat[loc]++; - } - if (oc == (O_MOV | O_LOC)) - loc_ptr[ic[i].arg1]++; - } - free(loc_sz); - /* func_leaf */ - func_leaf = 1; - for (i = 0; i < ic_n; i++) - if (ic[i].op & O_CALL) - func_leaf = 0; /* ra_vmap */ for (i = 0; i < LEN(ra_vmap); i++) ra_vmap[i] = -1; /* ra_lmap */ - for (i = 0; i < N_REGS; i++) - ra_lmapglob[i] = -1; - ra_glob(ic, ic_n); - memcpy(ra_lmap, ra_lmapglob, sizeof(ra_lmap)); - for (i = 0; i < LEN(ra_lmapglob); i++) - if (ra_lmapglob[i] >= 0) - func_regs |= (1 << i); + for (i = 0; i < LEN(ra_lmap); i++) + ra_lmap[i] = reg_rmap(0, i); + func_regs |= reg_mask(); /* ra_live */ for (i = 0; i < LEN(ra_live); i++) ra_live[i] = -1; @@ -552,17 +512,13 @@ static void ra_done(void) free(ic_bbeg); free(ra_gmask); free(loc_mem); - free(loc_ptr); - free(loc_dat); } -static void ic_gencode(struct ic *ic, int ic_n) +static void ic_gencode(struct ic *ic, long ic_n) { int r0, r1, r2; long mt; int i, j; - long *ic_luse; - ic_luse = ic_lastuse(ic, ic_n); /* loading arguments in their allocated registers */ for (i = 0; i < LEN(ra_lmap); i++) { int loc = ra_lmap[i]; @@ -575,8 +531,9 @@ static void ic_gencode(struct ic *ic, int ic_n) long op = ic[i].op; long oc = O_C(op); int n = ic_regcnt(ic + i); + ic_i = i; i_label(i); - ra_map(ic + i, &r0, &r1, &r2, &mt); + ra_map(&r0, &r1, &r2, &mt); if (oc & O_CALL) { int argc = ic[i].arg2; int aregs = MIN(N_ARGS, argc); @@ -633,7 +590,7 @@ static void ic_gencode(struct ic *ic, int ic_n) if (oc == O_RET) i_ins(op, r0, 0, 0); if (oc == O_MOV) - i_ins(op, r0, r0, 0); + i_ins(op, r0, r1, 0); if (oc == (O_MOV | O_NUM)) i_ins(op, r0, ic[i].arg1, 0); if (oc == (O_MOV | O_LOC)) @@ -655,13 +612,12 @@ static void ic_gencode(struct ic *ic, int ic_n) if (oc == O_MCPY) i_ins(op, r0, r1, r2); /* saving back the output register */ - if (oc & O_OUT) + if (oc & O_OUT && ic_luse[i] > i) ra_vsave(ic[i].arg0, r0); /* after the last instruction of a basic block */ if (i + 1 < ic_n && ic_bbeg[i + 1] && !(oc & O_JXX)) ra_bbend(); } - free(ic_luse); i_label(ic_n); } @@ -696,18 +652,21 @@ void o_code(char *name, char *c, long c_len) void o_func_end(void) { - struct ic *ic; - long ic_n, spsub; + long spsub; long sargs = 0; long sargs_last = -1; long sregs_pos; char *c; long c_len, *rsym, *rflg, *roff, rcnt; + int leaf = 1; int locs = 0; /* accessing locals on the stack */ int i; ic_get(&ic, &ic_n); /* the intermediate code */ + reg_init(ic, ic_n); /* global register allocation */ ra_init(ic, ic_n); /* initialize register allocation */ + ic_luse = ic_lastuse(ic, ic_n); ic_gencode(ic, ic_n); /* generating machine code */ + free(ic_luse); /* deciding which arguments to save */ for (i = 0; i < func_argc; i++) if (loc_mem[i]) @@ -724,8 +683,12 @@ void o_func_end(void) spsub += ULNG; sregs_pos = spsub; spsub += func_maxargs * ULNG; + /* leaf functions */ + for (i = 0; i < ic_n; i++) + if (ic[i].op & O_CALL) + leaf = 0; /* adding function prologue and epilogue */ - i_wrap(func_argc, sargs, spsub, spsub || locs || !func_leaf, + i_wrap(func_argc, sargs, spsub, spsub || locs || !leaf, func_regs & R_PERM, -sregs_pos); ra_done(); i_code(&c, &c_len, &rsym, &rflg, &roff, &rcnt); @@ -739,6 +702,7 @@ void o_func_end(void) for (i = 0; i < ic_n; i++) ic_free(&ic[i]); free(ic); + reg_done(); ic_reset(); } diff --git a/ncc.c b/ncc.c index bad8b17..28e88dd 100644 --- a/ncc.c +++ b/ncc.c @@ -1337,6 +1337,7 @@ static void localdef(long data, struct name *name, unsigned flags) name->addr = o_mklocal(type_totsz(&name->type)); local_add(name); if (!tok_jmp("=")) { + /* this is not necessary for "struct x = y" */ if (t->flags & (T_ARRAY | T_STRUCT) && !t->ptr) { o_local(name->addr); o_num(0); diff --git a/ncc.h b/ncc.h index c3fac76..0053cad 100644 --- a/ncc.h +++ b/ncc.h @@ -192,6 +192,14 @@ long *ic_lastuse(struct ic *ic, long ic_n); void ic_free(struct ic *ic); int ic_regcnt(struct ic *ic); +/* global register allocation */ +void reg_init(struct ic *ic, long ic_n); +long reg_mask(void); +int reg_lmap(long ic, long loc); +int reg_rmap(long ic, long reg); +int reg_safe(long loc); +void reg_done(void); + /* SECTION FOUR: Final Code Generation */ /* * To make maintaining different architectures easier and to unify the diff --git a/reg.c b/reg.c new file mode 100644 index 0000000..d9d0e5b --- /dev/null +++ b/reg.c @@ -0,0 +1,254 @@ +/* neatcc global register allocation */ +#include +#include +#include "ncc.h" + +#define IC_LOC(ic, i) ((ic)[i].arg1) +#define IC_LLD(ic, i) (O_C((ic)[i].op) == (O_LD | O_LOC)) +#define IC_LST(ic, i) (O_C((ic)[i].op) == (O_ST | O_LOC)) + +/* local live region */ +struct rgn { + long loc; /* local number */ + long beg; /* region start (instruction number) */ + long end; /* region end */ + long cnt; /* number of accesses */ + int reg; /* register allocated to this region */ +}; + +static struct rgn *rgn; /* live regions */ +static int rgn_n; /* number of entries in rgn[] */ +static int rgn_sz; /* size of rgn[] */ + +static int *loc_ptr; /* if the address of locals is accessed */ +static int loc_n; /* number of locals */ + +static long *dst_head; /* lists of jumps to each instruction */ +static long *dst_next; /* next entries in dst_head[] lists */ + +static void rgn_add(long loc, long beg, long end, long cnt) +{ + int i; + for (i = 0; i < rgn_n; i++) { + if (rgn[i].loc == loc && rgn[i].beg < end && rgn[i].end > beg) { + if (beg > rgn[i].beg) + beg = rgn[i].beg; + if (end < rgn[i].end) + end = rgn[i].end; + cnt += rgn[i].cnt; + rgn[i].loc = -1; + } + } + for (i = 0; i < rgn_n; i++) + if (rgn[i].loc < 0) + break; + if (i == rgn_n) { + if (rgn_n >= rgn_sz) { + rgn_sz = MAX(16, rgn_sz * 2); + rgn = mextend(rgn, rgn_n, rgn_sz, sizeof(rgn[0])); + } + rgn_n++; + } + rgn[i].loc = loc; + rgn[i].beg = beg; + rgn[i].end = end; + rgn[i].cnt = cnt; + rgn[i].reg = -1; +} + +/* return nonzero if register reg is free from beg till end */ +static int rgn_available(long beg, long end, int reg) +{ + int i; + for (i = 0; i < rgn_n; i++) + if (rgn[i].reg == reg) + if (rgn[i].beg < end && rgn[i].end > beg) + return 0; + return 1; +} + +static long reg_region(struct ic *ic, long ic_n, long loc, long pos, + long *beg, long *end, char *mark) +{ + long cnt = 0; + long dst; + for (; pos >= 0; pos--) { + if (pos < *beg) + *beg = pos; + if (pos + 1 > *end) + *end = pos + 1; + if (mark[pos]) + break; + mark[pos] = 1; + if (IC_LST(ic, pos) && IC_LOC(ic, pos) == loc) + break; + if (IC_LLD(ic, pos) && IC_LOC(ic, pos) == loc) + cnt++; + dst = dst_head[pos]; + while (dst >= 0) { + cnt += reg_region(ic, ic_n, loc, dst, beg, end, mark); + dst = dst_next[dst]; + } + if (pos > 0 && ic[pos - 1].op & O_JMP) + break; + } + return cnt; +} + +/* compute local's live regions */ +static void reg_regions(struct ic *ic, long ic_n, long loc) +{ + char *mark; + long beg, end; + long cnt; + long i; + mark = calloc(ic_n, sizeof(mark[0])); + for (i = 0; i < ic_n; i++) { + if (IC_LLD(ic, i) && IC_LOC(ic, i) == loc && !mark[i]) { + beg = i; + end = i + 1; + cnt = reg_region(ic, ic_n, loc, i, &beg, &end, mark); + rgn_add(loc, beg, end, cnt); + } + } + for (i = 0; i < ic_n; i++) + if (IC_LST(ic, i) && IC_LOC(ic, i) == loc && !mark[i]) + rgn_add(loc, i, i + 1, 1); + free(mark); +} + +/* perform global register allocation */ +static void reg_glob(int leaf) +{ + int *srt; + int regs[N_REGS]; + int i, j; + int regs_max = MIN(N_TMPS >> 1, 4); + long regs_mask = leaf ? R_TMPS : R_PERM; + int regs_n = 0; + for (i = leaf ? 1 : 3; i < N_TMPS && regs_n < regs_max; i++) + if ((1 << i) & regs_mask) + regs[regs_n++] = i; + srt = malloc(rgn_n * sizeof(srt[0])); + /* sorting locals */ + for (i = 0; i < rgn_n; i++) { + for (j = i - 1; j >= 0 && rgn[i].cnt > rgn[srt[j]].cnt; j--) + srt[j + 1] = srt[j]; + srt[j + 1] = i; + } + /* allocating registers */ + for (i = 0; i < rgn_n; i++) { + int r = srt[i]; + long loc = rgn[r].loc; + long beg = rgn[r].beg; + long end = rgn[r].end; + if (loc < 0 || loc_ptr[loc]) + continue; + if (leaf && loc < N_ARGS && beg == 0 && + rgn_available(beg, end, argregs[loc])) { + rgn[r].reg = argregs[loc]; + continue; + } + for (j = 0; j < regs_n; j++) + if (rgn_available(beg, end, regs[j])) + break; + if (j < regs_n) + rgn[r].reg = regs[j]; + } + free(srt); +} + +void reg_init(struct ic *ic, long ic_n) +{ + int *loc_sz; + int leaf = 1; + long i; + for (i = 0; i < ic_n; i++) + if (ic[i].op & O_LOC && loc_n < IC_LOC(ic, i) + 1) + loc_n = IC_LOC(ic, i) + 1; + loc_ptr = calloc(loc_n, sizeof(loc_ptr[0])); + loc_sz = calloc(loc_n, sizeof(loc_sz[0])); + for (i = 0; i < ic_n; i++) { + long oc = O_C(ic[i].op); + if (oc == (O_LD | O_LOC) || oc == (O_ST | O_LOC)) { + int loc = IC_LOC(ic, i); + int sz = T_SZ(O_T(ic[i].op)); + if (!loc_sz[loc]) + loc_sz[loc] = sz; + if (ic[i].arg2 || sz < 2 || sz != loc_sz[loc]) + loc_ptr[loc]++; + } + if (oc == (O_MOV | O_LOC)) + loc_ptr[IC_LOC(ic, i)]++; + } + free(loc_sz); + for (i = 0; i < ic_n; i++) + if (ic[i].op & O_CALL) + leaf = 0; + dst_head = malloc(ic_n * sizeof(dst_head[0])); + dst_next = malloc(ic_n * sizeof(dst_next[0])); + for (i = 0; i < ic_n; i++) + dst_head[i] = -1; + for (i = 0; i < ic_n; i++) + dst_next[i] = -1; + for (i = 0; i < ic_n; i++) { + if (ic[i].op & O_JXX) { + dst_next[i] = dst_head[ic[i].arg2]; + dst_head[ic[i].arg2] = i; + } + } + for (i = 0; i < loc_n; i++) + if (!loc_ptr[i]) + reg_regions(ic, ic_n, i); + reg_glob(leaf); +} + +long reg_mask(void) +{ + long ret = 0; + int i; + for (i = 0; i < rgn_n; i++) + if (rgn[i].reg >= 0) + ret |= 1 << rgn[i].reg; + return ret; +} + +/* return the allocated register of local loc */ +int reg_lmap(long c, long loc) +{ + int i; + for (i = 0; i < rgn_n; i++) + if (rgn[i].loc == loc) + if (rgn[i].beg <= c && rgn[i].end > c) + return rgn[i].reg; + return -1; +} + +/* return the local to which register reg is allocated */ +int reg_rmap(long c, long reg) +{ + int i; + for (i = 0; i < rgn_n; i++) + if (rgn[i].reg == reg) + if (rgn[i].beg <= c && rgn[i].end > c) + return rgn[i].loc; + return -1; +} + +void reg_done(void) +{ + free(dst_head); + free(dst_next); + free(loc_ptr); + free(rgn); + loc_ptr = NULL; + rgn = NULL; + rgn_sz = 0; + rgn_n = 0; + loc_n = 0; +} + +int reg_safe(long loc) +{ + return loc < loc_n && !loc_ptr[loc]; +} -- 2.11.4.GIT