123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540 |
- /* $Id$ */
- /*
- * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
- * See the copyright notice in the ACK home directory, in the file "Copyright".
- */
- /* R E G I S T E R A L L O C A T I O N
- *
- * R A _ X F O R M . C
- */
- #include <em_mnem.h>
- #include <em_spec.h>
- #include <em_pseu.h>
- #include <em_mes.h>
- #include <em_ego.h>
- #include <em_reg.h>
- #include "../share/types.h"
- #include "../share/debug.h"
- #include "../share/def.h"
- #include "../share/global.h"
- #include "../share/lset.h"
- #include "../share/aux.h"
- #include "../share/alloc.h"
- #include "ra.h"
- #include "ra_interv.h"
- #include "ra_xform.h"
- #include "ra_items.h"
- /* The replacement table is used to transform instructions that reference
- * items other than local variables (i.e. the address of a local or global
- * variable or a single/double constant; the transformation of an instruction
- * that references a local variable is very simple).
- * The generated code depends on the word and pointer size of the target
- * machine.
- */
- struct repl {
- short r_instr; /* instruction */
- short r_op; /* operand */
- };
- /* REGNR,NO and STOP should not equal the wordsize or pointer size
- * of any machine.
- */
- #define REGNR -3
- #define NO -2
- #define STOP -1
- #define PS 0
- #define PS2 1
- #define WS 2
- #define WS2 3
- #define LOAD_POINTER op_nop
- #define BLANK {0, STOP}
- #define NRREPLACEMENTS 13
- #define REPL_LENGTH 3
- struct repl repl_tab[NRREPLACEMENTS][REPL_LENGTH] = {
- /* 0 */ {{op_lil, REGNR}, BLANK, BLANK},
- /* 1 */ {{LOAD_POINTER,REGNR}, {op_loi,PS}, {op_loi,WS}},
- /* 2 */ {{LOAD_POINTER,REGNR}, BLANK, BLANK},
- /* 3 */ {{LOAD_POINTER,REGNR}, {op_loi,WS2}, BLANK},
- /* 4 */ {{op_sil,REGNR}, BLANK, BLANK},
- /* 5 */ {{LOAD_POINTER,REGNR}, {op_loi,PS}, {op_sti,WS}},
- /* 6 */ {{LOAD_POINTER,REGNR}, {op_sti,WS2}, BLANK},
- /* 7 */ {{op_lil,REGNR}, {op_inc,NO}, {op_sil,REGNR}},
- /* 8 */ {{op_lil,REGNR}, {op_dec,NO}, {op_sil,REGNR}},
- /* 9 */ {{op_zer,WS}, {op_sil,REGNR}, BLANK},
- /*10 */ {{op_lol,REGNR}, BLANK, BLANK},
- /*11 */ {{op_ldl,REGNR}, BLANK, BLANK},
- /*12 */ {{LOAD_POINTER,REGNR}, {op_cai,NO}, BLANK},
- };
- void init_replacements(short psize, short wsize)
- {
- /* The replacement code to be generated depends on the
- * wordsize and pointer size of the target machine.
- * The replacement table is initialized with a description
- * of which sizes to use. This routine inserts the real sizes.
- * It also inserts the actual EM instruction to be used
- * as a 'Load pointer' instruction.
- */
- int i,j;
- short load_pointer;
- struct repl *r;
- assert (psize == wsize || psize == 2*wsize);
- load_pointer = (psize == wsize ? op_lol : op_ldl);
- for (i = 0; i < NRREPLACEMENTS; i++) {
- for (j = 0; j < REPL_LENGTH; j++) {
- r = &repl_tab[i][j];
- if (r->r_op == STOP) break;
- if (r->r_instr == LOAD_POINTER) {
- r->r_instr = load_pointer;
- }
- switch (r->r_op) {
- /* initially r_op describes how to compute
- * the real operand of the instruction. */
- case PS2:
- r->r_op = 2*psize;
- break;
- case PS:
- r->r_op = psize;
- break;
- case WS2:
- r->r_op = 2*wsize;
- break;
- case WS:
- r->r_op = wsize;
- break;
- case NO:
- case REGNR: /* use offset of dummy local,
- * will be filled in later.
- */
- break;
- default: assert(FALSE);
- }
- }
- }
- }
- static int repl_index(line_p l)
- {
- return itemtab[INSTR(l) - sp_fmnem].id_replindex;
- }
- static bool is_current(alloc_p alloc, short t)
- {
- /* Is time t part of alloc's timespan? */
- return contains(t,alloc->al_timespan);
- }
- static int match_item(item_p item, line_p l)
- {
- /* See if the item used by l is the same one as 'item' */
- struct item thisitem;
- fill_item(&thisitem,l);
- if (item->it_type == LOCAL_ADDR && thisitem.it_type == LOCALVAR) {
- /* The usage of a local variable is also considered to
- * be the usage of the address of that variable.
- */
- thisitem.it_type = LOCAL_ADDR;
- }
- return (item->it_type == thisitem.it_type) && same_item(item,&thisitem);
- }
- static alloc_p find_alloc(alloc_p alloclist, line_p l, short t)
- {
- /* See if any of the allocations of the list applies to instruction
- * l at time t.
- */
- alloc_p alloc,m;
- for (alloc = alloclist; alloc != (alloc_p) 0; alloc = alloc->al_next) {
- for (m = alloc; m != (alloc_p) 0; m = m->al_mates) {
- if (is_current(m,t) && match_item(m->al_item,l)) {
- return m;
- }
- }
- }
- return (alloc_p) 0;
- }
- static void replace_line(line_p l, bblock_p b, line_p list)
- {
- if (b->b_start == l) {
- b->b_start = list;
- } else {
- PREV(l)->l_next = list;
- }
- PREV(list) = PREV(l);
- while (list->l_next != (line_p) 0) {
- list = list->l_next;
- }
- list->l_next = l->l_next;
- if (l->l_next != (line_p) 0) {
- PREV(l->l_next) = list;
- }
- oldline(l);
- }
- static line_p repl_code(line_p lnp, offset regnr)
- {
- line_p head,*q,l,prev = (line_p) 0;
- int i,index;
- struct repl *r;
- q = &head;
- index = repl_index(lnp);
- for (i = 0; i < REPL_LENGTH; i++) {
- r = &repl_tab[index][i];
- if (r->r_op == STOP) break; /* replacement < REPL_LENGTH */
- switch(r->r_op) {
- case REGNR:
- l = int_line(regnr);
- break;
- case NO:
- l = newline(OPNO);
- break;
- default:
- l = newline(OPSHORT);
- SHORT(l) = r->r_op;
- break;
- }
- *q = l;
- l->l_instr = r->r_instr;
- PREV(l) = prev;
- prev = l;
- q = &l->l_next;
- }
- return head;
- }
- static void apply_alloc(bblock_p b, line_p l, alloc_p alloc)
- {
- /* 'l' is an EM instruction using an item that will be put in
- * a register. Generate new code that uses the register instead
- * of the item.
- * If the item is a local variable the new code is the same as
- * the old code, except for the fact that the offset of the
- * local is changed (it now uses the dummy local that will be
- * put in a register by the code generator).
- * If the item is a constant, the new code is a LOL or LDL.
- * If the item is the address of a local or global variable, things
- * get more complicated. The new code depends on the instruction
- * that uses the item (i.e. l). The new code, which may consist of
- * several instructions, is obtained by consulting a replacement
- * table.
- */
- line_p newcode;
- if (alloc->al_item->it_type == LOCALVAR) {
- if ((short) (alloc->al_dummy) == alloc->al_dummy) {
- TYPE(l) = OPSHORT;
- SHORT(l) = alloc->al_dummy;
- }
- else {
- TYPE(l) = OPOFFSET;
- OFFSET(l) = alloc->al_dummy;
- }
- } else {
- newcode = repl_code(l,alloc->al_dummy);
- replace_line(l,b,newcode);
- }
- }
- static int loaditem_tab[NRITEMTYPES][2] =
- { /* WS 2 * WS */
- /*LOCALVAR*/ { op_lol, op_ldl },
- /*LOCAL_ADDR*/ { op_lal, op_lal },
- /*GLOBL_ADDR*/ { op_lae, op_lae },
- /*PROC_ADDR*/ { op_lpi, op_lpi },
- /*CONST*/ { op_loc, op_nop },
- /*DCONST*/ { op_nop, op_ldc }
- };
- static line_p load_item(item_p item)
- {
- /* Generate an EM instruction that loads the item on the stack */
- line_p l;
- switch (item->it_type) {
- case GLOBL_ADDR:
- l = newline(OPOBJECT);
- OBJ(l) = item->i_t.it_obj;
- break;
- case PROC_ADDR:
- l = newline(OPPROC);
- PROC(l) = item->i_t.it_proc;
- break;
- default:
- l = int_line(item->i_t.it_off);
- }
- l->l_instr = loaditem_tab[item->it_type][item->it_size == ws ? 0 : 1];
- assert(l->l_instr != op_nop);
- return l;
- }
- static line_p store_local(short size, offset off)
- {
- line_p l = int_line(off);
- l->l_instr = (size == ws ? op_stl : op_sdl);
- return l;
- }
- static line_p init_place(bblock_p b)
- {
- line_p l,prev;
- prev = (line_p) 0;
- for (l = b->b_start; l != (line_p) 0; l = l->l_next) {
- switch(INSTR(l)) {
- case ps_mes:
- case ps_pro:
- case op_lab:
- break;
- default:
- return prev;
- }
- prev =l;
- }
- return prev;
- }
- static void append_code(line_p l1, line_p l2, bblock_p b)
- {
- /* Append instruction l1 and l2 at begin of block b */
- line_p l;
- DLINK(l1,l2);
- l = init_place(b);
- if (l == (line_p) 0) {
- l2->l_next = b->b_start;
- b->b_start = l1;
- PREV(l1) = (line_p) 0;
- } else {
- l2->l_next = l->l_next;
- DLINK(l,l1);
- }
- if (l2->l_next != (line_p) 0) {
- PREV(l2->l_next) = l2;
- }
- }
- static void emit_init_code(alloc_p list)
- {
- /* Emit initialization code for all packed allocations.
- * This code looks like "dummy_local := item", e.g.
- * "LOC 25 ; STL -10" in EM terminology.
- */
- alloc_p alloc,m;
- Lindex bi;
- bblock_p b;
- for (alloc = list; alloc != (alloc_p) 0; alloc = alloc->al_next) {
- for (m = alloc; m != (alloc_p) 0; m = m->al_mates) {
- for (bi = Lfirst(m->al_inits); bi != (Lindex) 0;
- bi = Lnext(bi,m->al_inits)) {
- /* "inits" contains all initialization points */
- b = (bblock_p) Lelem(bi);
- append_code(load_item(m->al_item),
- store_local(m->al_item->it_size,
- m->al_dummy),
- b);
- }
- }
- }
- }
- static void emit_mesregs(proc_p p, alloc_p alloclist)
- {
- line_p l,m,x;
- alloc_p alloc;
- l = p->p_start->b_start;
- x = l->l_next;
- for (alloc = alloclist; alloc != (alloc_p) 0; alloc = alloc->al_next) {
- m = reg_mes(alloc->al_dummy,alloc->al_item->it_size,
- alloc->al_regtype,INFINITE);
- DLINK(l,m);
- l = m;
- }
- if (x != (line_p) 0) DLINK(l,x);
- }
- #define is_mesreg(l) (INSTR(l) == ps_mes && aoff(ARG(l),0) == ms_reg)
- static void rem_mes(proc_p p)
- {
- bblock_p b;
- line_p l,next;
- offset m;
- for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
- for (l = b->b_start; l != (line_p) 0; l = next) {
- next = l->l_next;
- if (INSTR(l) == ps_mes
- && aoff(ARG(l),0) == ms_ego
- && ((m = aoff(ARG(l),1)) == ego_live
- || m == ego_dead)) {
- /* remove live/dead messages */
- rm_line(l,b);
- }
- }
- }
- }
- void xform_proc(proc_p p, alloc_p alloclist, short nrinstrs, line_p instrmap[])
- {
- /* Transform every instruction of procedure p that uses an item
- * at a point where the item is kept in a register.
- */
- short now = 0;
- line_p l,next;
- bblock_p b;
- alloc_p alloc;
- for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
- for (l = b->b_start; l != (line_p) 0; l = next) {
- next = l->l_next;
- if (is_mesreg(l) && ARG(l)->a_next != (arg_p) 0 &&
- aoff(ARG(l),4) != INFINITE) {
- /* All register messages for local variables
- * that were not assigned a register get
- * their 'count' fields* set to 0.
- */
- ARG(l)->a_next->a_next->a_next
- ->a_next->a_a.a_offset = 0;
- }
- if (is_item(l) &&
- (alloc = find_alloc(alloclist,l,now))
- != (alloc_p) 0 ) {
- apply_alloc(b,l,alloc);
- }
- now++;
- }
- }
- emit_init_code(alloclist);
- emit_mesregs(p,alloclist);
- rem_mes(p);
- }
- bool always_in_reg(offset off, alloc_p allocs, short *size_out)
- {
- /* See if the local variable with the given offset is stored
- * in a register during its entire lifetime. As a side effect,
- * return the size of the local.
- */
- alloc_p alloc,m;
- item_p item;
- for (alloc = allocs; alloc != (alloc_p) 0; alloc = alloc->al_next) {
- for (m = alloc; m != (alloc_p) 0; m = m->al_mates) {
- item = m->al_item;
- if (m->al_iswholeproc &&
- item->it_type == LOCALVAR &&
- item->i_t.it_off == off) {
- *size_out = item->it_size;
- return TRUE;
- }
- }
- }
- return FALSE;
- }
- void rem_locals(proc_p p, alloc_p allocs)
- {
- /* Try to decrease the number of locals of procedure p, by
- * looking at which locals are always stored in a register.
- */
- offset nrlocals = p->p_localbytes;
- short size;
- while (nrlocals > 0) {
- /* A local can only be removed if all locals with
- * higher offsets are removed too.
- */
- if (always_in_reg(-nrlocals,allocs,&size)) {
- OUTVERBOSE("local %d removed from proc %d\n",
- nrlocals,p->p_id);
- nrlocals -= size;
- } else {
- break;
- }
- }
- p->p_localbytes = nrlocals;
- }
- void rem_formals(proc_p p, alloc_p allocs)
- {
- /* Try to decrease the number of formals of procedure p, by
- * looking at which formals are always stored in a register.
- */
- offset nrformals = p->p_nrformals;
- offset off = 0;
- short size;
- if (nrformals == UNKNOWN_SIZE) return;
- while (off < nrformals) {
- if (always_in_reg(off,allocs,&size)) {
- OUTVERBOSE("formal %d removed from proc %d\n",
- off,p->p_id);
- off += size;
- } else {
- break;
- }
- }
- if (nrformals == off) {
- OUTVERBOSE("all formals of procedure %d removed\n",p->p_id,0);
- p->p_nrformals = 0;
- }
- }
|