From 9f778655a6a8890fb3793b5d3d00c5bc7e0b01bc Mon Sep 17 00:00:00 2001 From: bal Date: Mon, 26 Nov 1984 14:14:55 +0000 Subject: [PATCH] Initial revision --- util/ego/il/Makefile | 133 ++++++++ util/ego/il/il.c | 312 +++++++++++++++++ util/ego/il/il.h | 69 ++++ util/ego/il/il1_anal.c | 177 ++++++++++ util/ego/il/il1_anal.h | 17 + util/ego/il/il1_aux.c | 208 ++++++++++++ util/ego/il/il1_aux.h | 38 +++ util/ego/il/il1_cal.c | 138 ++++++++ util/ego/il/il1_cal.h | 31 ++ util/ego/il/il1_formal.c | 141 ++++++++ util/ego/il/il1_formal.h | 11 + util/ego/il/il2_aux.c | 718 +++++++++++++++++++++++++++++++++++++++ util/ego/il/il2_aux.h | 36 ++ util/ego/il/il3_aux.c | 63 ++++ util/ego/il/il3_aux.h | 15 + util/ego/il/il3_change.c | 583 +++++++++++++++++++++++++++++++ util/ego/il/il3_change.h | 41 +++ util/ego/il/il3_subst.c | 121 +++++++ util/ego/il/il3_subst.h | 17 + util/ego/il/il_aux.c | 182 ++++++++++ util/ego/il/il_aux.h | 30 ++ 21 files changed, 3081 insertions(+) create mode 100644 util/ego/il/Makefile create mode 100644 util/ego/il/il.c create mode 100644 util/ego/il/il.h create mode 100644 util/ego/il/il1_anal.c create mode 100644 util/ego/il/il1_anal.h create mode 100644 util/ego/il/il1_aux.c create mode 100644 util/ego/il/il1_aux.h create mode 100644 util/ego/il/il1_cal.c create mode 100644 util/ego/il/il1_cal.h create mode 100644 util/ego/il/il1_formal.c create mode 100644 util/ego/il/il1_formal.h create mode 100644 util/ego/il/il2_aux.c create mode 100644 util/ego/il/il2_aux.h create mode 100644 util/ego/il/il3_aux.c create mode 100644 util/ego/il/il3_aux.h create mode 100644 util/ego/il/il3_change.c create mode 100644 util/ego/il/il3_change.h create mode 100644 util/ego/il/il3_subst.c create mode 100644 util/ego/il/il3_subst.h create mode 100644 util/ego/il/il_aux.c create mode 100644 util/ego/il/il_aux.h diff --git a/util/ego/il/Makefile b/util/ego/il/Makefile new file mode 100644 index 000000000..8371ed885 --- /dev/null +++ b/util/ego/il/Makefile @@ -0,0 +1,133 @@ +EMH=../../../h +EML=../../../lib +CFLAGS=-DVERBOSE +SHARE=../share +IL=. +OBJECTS=il.o il1_anal.o il1_cal.o il1_formal.o il1_aux.o il2_aux.o \ +il3_change.o il3_subst.o il3_aux.o il_aux.o +SHOBJECTS=$(SHARE)/get.o $(SHARE)/put.o $(SHARE)/alloc.o $(SHARE)/global.o $(SHARE)/debug.o $(SHARE)/files.o $(SHARE)/map.o $(SHARE)/lset.o $(SHARE)/cset.o $(SHARE)/parser.o $(SHARE)/aux.o $(SHARE)/go.o +SRC=il.h il1_anal.h il1_cal.h il1_formal.h il1_aux.h il2_aux.h il3_subst.h il3_change.h il3_aux.h il_aux.h \ +il.c il1_anal.c il1_cal.c il1_formal.c il1_aux.c il2_aux.c il3_subst.c il3_change.c il3_aux.c il_aux.c +.c.o: + cc $(CFLAGS) -c $< +all: $(OBJECTS) +il: \ + $(OBJECTS) $(SHOBJECTS) + cc -o il -i $(OBJECTS) $(SHOBJECTS) $(EML)/em_data.a +lpr: + pr $(SRC) | lpr +dumpflop: + tar -uf /mnt/ego/il/il.tarf $(SRC) +# the next lines are generated automatically +# AUTOAUTOAUTOAUTOAUTOAUTO +il.o: ../../../h/em_mnem.h +il.o: ../../../h/em_pseu.h +il.o: ../share/alloc.h +il.o: ../share/debug.h +il.o: ../share/files.h +il.o: ../share/get.h +il.o: ../share/global.h +il.o: ../share/lset.h +il.o: ../share/map.h +il.o: ../share/put.h +il.o: ../share/types.h +il.o: il.h +il.o: il1_anal.h +il.o: il2_aux.h +il.o: il3_subst.h +il1_anal.o: ../../../h/em_mnem.h +il1_anal.o: ../../../h/em_pseu.h +il1_anal.o: ../share/alloc.h +il1_anal.o: ../share/debug.h +il1_anal.o: ../share/global.h +il1_anal.o: ../share/lset.h +il1_anal.o: ../share/put.h +il1_anal.o: ../share/types.h +il1_anal.o: il.h +il1_anal.o: il1_anal.h +il1_anal.o: il1_aux.h +il1_anal.o: il1_cal.h +il1_anal.o: il1_formal.h +il1_anal.o: il_aux.h +il1_aux.o: ../../../h/em_spec.h +il1_aux.o: ../share/alloc.h +il1_aux.o: ../share/debug.h +il1_aux.o: ../share/global.h +il1_aux.o: ../share/lset.h +il1_aux.o: ../share/types.h +il1_aux.o: il.h +il1_aux.o: il1_aux.h +il1_aux.o: il_aux.h +il1_cal.o: ../../../h/em_mnem.h +il1_cal.o: ../../../h/em_spec.h +il1_cal.o: ../share/alloc.h +il1_cal.o: ../share/debug.h +il1_cal.o: ../share/global.h +il1_cal.o: ../share/lset.h +il1_cal.o: ../share/parser.h +il1_cal.o: ../share/types.h +il1_cal.o: il.h +il1_cal.o: il1_aux.h +il1_cal.o: il1_cal.h +il1_formal.o: ../share/alloc.h +il1_formal.o: ../share/debug.h +il1_formal.o: ../share/global.h +il1_formal.o: ../share/lset.h +il1_formal.o: ../share/types.h +il1_formal.o: il.h +il1_formal.o: il1_aux.h +il1_formal.o: il1_formal.h +il2_aux.o: ../../../h/em_mnem.h +il2_aux.o: ../../../h/em_spec.h +il2_aux.o: ../share/alloc.h +il2_aux.o: ../share/debug.h +il2_aux.o: ../share/get.h +il2_aux.o: ../share/global.h +il2_aux.o: ../share/lset.h +il2_aux.o: ../share/types.h +il2_aux.o: il.h +il2_aux.o: il2_aux.h +il2_aux.o: il_aux.h +il3_aux.o: ../share/alloc.h +il3_aux.o: ../share/debug.h +il3_aux.o: ../share/global.h +il3_aux.o: ../share/types.h +il3_aux.o: il.h +il3_aux.o: il3_aux.h +il3_aux.o: il_aux.h +il3_change.o: ../../../h/em_mes.h +il3_change.o: ../../../h/em_mnem.h +il3_change.o: ../../../h/em_pseu.h +il3_change.o: ../../../h/em_spec.h +il3_change.o: ../share/alloc.h +il3_change.o: ../share/debug.h +il3_change.o: ../share/def.h +il3_change.o: ../share/get.h +il3_change.o: ../share/global.h +il3_change.o: ../share/lset.h +il3_change.o: ../share/put.h +il3_change.o: ../share/types.h +il3_change.o: il.h +il3_change.o: il3_aux.h +il3_change.o: il3_change.h +il3_change.o: il_aux.h +il3_subst.o: ../../../h/em_mnem.h +il3_subst.o: ../share/alloc.h +il3_subst.o: ../share/debug.h +il3_subst.o: ../share/get.h +il3_subst.o: ../share/global.h +il3_subst.o: ../share/lset.h +il3_subst.o: ../share/types.h +il3_subst.o: il.h +il3_subst.o: il3_aux.h +il3_subst.o: il3_change.h +il3_subst.o: il3_subst.h +il_aux.o: ../../../h/em_spec.h +il_aux.o: ../share/alloc.h +il_aux.o: ../share/debug.h +il_aux.o: ../share/global.h +il_aux.o: ../share/lset.h +il_aux.o: ../share/map.h +il_aux.o: ../share/types.h +il_aux.o: il.h +il_aux.o: il_aux.h diff --git a/util/ego/il/il.c b/util/ego/il/il.c new file mode 100644 index 000000000..124e00b22 --- /dev/null +++ b/util/ego/il/il.c @@ -0,0 +1,312 @@ +/* I N L I N E S U B S T I T U T I O N */ +#include +#include "../share/types.h" +#include "il.h" +#include "../share/debug.h" +#include "../share/alloc.h" +#include "../share/global.h" +#include "../share/lset.h" +#include "../share/files.h" +#include "../../../h/em_mnem.h" +#include "../../../h/em_pseu.h" +#include "../share/map.h" +#include "il1_anal.h" +#include "il2_aux.h" +#include "il3_subst.h" +#include "../share/get.h" +#include "../share/put.h" +#include "../share/go.h" + +int calnr; +calcnt_p cchead; /* call-count info of current proc */ +STATIC short space = 0; + +STATIC char cname[] = "/usr/tmp/ego.i1.XXXXXX"; +STATIC char ccname[] = "/usr/tmp/ego.i2.XXXXXX"; + +/* For debugging only */ +STATIC char sname[] = "/usr/tmp/ego.i3.XXXXXX"; + +int Ssubst; +#ifdef VERBOSE +int Senv,Srecursive,Slocals,Sinstrlab,Sparsefails,Spremoved,Scals; +int Sbig_caller,Sdispensable,Schangedcallee,Sbigcallee,Sspace,Szeroratio; +#endif + +/* P A S S 1 + * + * Pass 1 reads and analyses the EM text and the CFG. + * It determines for every procedure if it may be expanded + * in line and how it uses its formal parameters. + * It also collects all calls appearing in the program and + * recognizes the actual parameters of every call. + * The call descriptors are put in a file (calfile). + */ + +pass1(lnam,bnam,cnam) + char *lnam, *bnam, *cnam; +{ + FILE *f, *gf, *cf, *ccf; /* The EM input, the basic block graph, + * the call-list file and the calcnt file. + */ + long laddr; + bblock_p g; + short kind; + line_p l; + + f = openfile(lnam,"r"); + gf = openfile(bnam,"r"); + cf = openfile(cnam,"w"); + ccf = openfile(ccname,"w"); + mesregs = Lempty_set(); + apriori(fproc); + /* use information from the procedure table to + * see which calls certainly cannot be expanded. + */ + while(TRUE) { + laddr = ftell(f); + if (!getunit(gf,f,&kind,&g,&l,&curproc,TRUE)) break; + /* Read the control flow graph and EM text of + * one procedure and analyze it. + */ + if (kind == LDATA) { + remunit(LDATA,(proc_p) 0,l); + continue; + } + /* OUTTRACE("flow graph of proc %d read",curproc->p_id); */ + assert(INSTR(g->b_start) == ps_pro); + curproc->p_start = g; + curproc->P_LADDR = laddr; + /* address of em text in em-file */ + /* address of graph in basic block file */ + curproc->P_SIZE = proclength(curproc); /* #instructions */ + if (BIG_PROC(curproc)) { + /* curproc is too large to be expanded in line */ + UNSUITABLE(curproc); + } + calnr = 0; + anal_proc(curproc,cf,ccf); + /* OUTTRACE("proc %d processed",curproc->p_id); */ + remunit(LTEXT,curproc,(line_p) 0); + /* remove control flow graph + text */ + /* OUTTRACE("graph of proc %d removed",curproc->p_id); */ + Ldeleteset(mesregs); + mesregs = Lempty_set(); + } + fclose(f); + fclose(gf); + fclose(cf); + fclose(ccf); +} + + + +/* P A S S 2 + * + * Pass 2 reads the calfile and determines which calls should + * be expanded in line. It does not use the EM text. + */ + + + +STATIC char cname2[] = "/usr/tmp/ego.i4.XXXXXX"; + +pass2(cnam,space) + char *cnam; + short space; +{ + FILE *cf, *cf2, *ccf; + call_p c,a; + + cf = openfile(cnam,"r"); + cf2 = openfile(cname2,"w"); + ccf = openfile(ccname,"r"); + while ((c = getcall(cf)) != (call_p) 0) { + /* process all calls */ + if (SUITABLE(c->cl_proc)) { + /* called proc. may be put in line */ + anal_params(c); + /* see which parameters may be put in line */ + assign_ratio(c); /* assign a rank */ + a = abstract(c); /* abstract essential info */ + append_abstract(a,a->cl_caller); + /* put it in call-list of calling proc. */ + putcall(c,cf2,(short) 0); + } else { + rem_call(c); + } + } + select_calls(fproc,ccf,space); + fclose(cf); unlink(cnam); + fclose(cf2); + fclose(ccf); unlink(ccname); + cf2 = openfile(cname2,"r"); + add_actuals(fproc,cf2); + cleancals(fproc); /* remove calls that were not selected */ + /* add actual parameters to each selected call */ + fclose(cf2); unlink(cname2); +} + + + +/* P A S S 3 + * + * pass 3 reads the substitution file and performs all + * substitutions described in that file. It reads the + * original EM text and produced a new (optimized) + * EM textfile. + */ + + +pass3(lnam,lnam2) + char *lnam,*lnam2; +{ + bool verbose = TRUE; + FILE *lfile, *lfilerand, *lfile2, *sfile; + call_p c,next; + line_p l,startscan,cal; + short lastcid; /* last call-id seen */ + + lfile = openfile(lnam, "r"); + lfilerand = openfile(lnam, "r"); + lfile2 = openfile(lnam2,"w"); + if (verbose) { + sfile = openfile(sname,"w"); + } + mesregs = Lempty_set(); + while ((l = get_text(lfile,&curproc)) != (line_p) 0) { + if (curproc == (proc_p) 0) { + /* Just a data-unit; no real instructions */ + putlines(l->l_next,lfile2); + oldline(l); + continue; + } + if (IS_DISPENSABLE(curproc)) { + liquidate(curproc,l->l_next); + } else { + startscan = l->l_next; + lastcid = 0; + for (c = curproc->P_CALS; c != (call_p) 0; c = next) { + next = c->cl_cdr; + cal = scan_to_cal(startscan,c->cl_id - lastcid); + assert (cal != (line_p) 0); + startscan = scan_to_cal(cal->l_next,1); + /* next CAL */ + lastcid = c->cl_id; + /* next CAL after current one */ + substitute(lfilerand,c,cal,l->l_next); + if (verbose) { + putcall(c,sfile,0); + } else { + rem_call(c); + } + } + } + putlines(l->l_next,lfile2); + Ldeleteset(mesregs); + mesregs = Lempty_set(); + oldline(l); + } + fclose(lfile); + fclose(lfile2); + if (verbose) { + fclose(sfile); + unlink(sname); + } +} + + +STATIC il_extptab(ptab) + proc_p ptab; +{ + /* Allocate space for extension of proctable entries. + * Also, initialise some of the fields just allocated. + */ + + register proc_p p; + + for (p = ptab; p != (proc_p) 0; p = p->p_next) { + p->p_extend = newilpx(); + p->P_ORGLABELS = p->p_nrlabels; + p->P_ORGLOCALS = p->p_localbytes; + } +} + +STATIC il_cleanptab(ptab) + proc_p ptab; +{ + /* De-allocate space for extensions */ + + register proc_p p; + + for (p = ptab; p != (proc_p) 0; p = p->p_next) { + oldilpx(p->p_extend); + } +} + +#ifdef VERBOSE +Sdiagnostics() +{ + /* print statictical information */ + + fprintf(stderr,"STATISTICS:\n"); + fprintf(stderr,"Info about procedures:\n"); + fprintf(stderr,"environment accessed: %d\n",Senv); + fprintf(stderr,"recursive: %d\n",Srecursive); + fprintf(stderr,"too many locals: %d\n",Slocals); + fprintf(stderr,"instr. lab in data block: %d\n",Sinstrlab); + fprintf(stderr,"procedures removed: %d\n",Spremoved); + fprintf(stderr,"\nInfo about calls:\n"); + fprintf(stderr,"total number of calls: %d\n",Scals); + fprintf(stderr,"total number of calls substituted: %d\n",Ssubst); + fprintf(stderr,"parser failed: %d\n",Sparsefails); + fprintf(stderr,"caller too big: %d\n",Sbig_caller); + fprintf(stderr,"caller dispensable: %d\n",Sdispensable); + fprintf(stderr,"callee is changed: %d\n",Schangedcallee); + fprintf(stderr,"callee too big: %d\n",Sbigcallee); + fprintf(stderr,"no space available: %d\n",Sspace); + fprintf(stderr,"zero ratio: %d\n",Szeroratio); +} +#endif + +il_flags(p) + char *p; +{ + if (*p++ == 's') { + while (*p != '\0') { + space = 10*space +*p++ -'0'; + } + } +} + +main(argc,argv) + int argc; + char *argv[]; +{ + FILE *f; + + go(argc,argv,no_action,no_action,no_action,il_flags); + il_extptab(fproc); /* add extended data structures */ + mktemp(cname); + mktemp(ccname); + mktemp(sname); + mktemp(cname2); + pass1(lname,bname,cname); /* grep calls, analyse procedures */ + pass2(cname,space); /* select calls to be expanded */ + pass3(lname,lname2); /* do substitutions */ + f = openfile(dname2,"w"); + il_cleanptab(fproc); /* remove extended data structures */ + putdtable(fdblock,f); + f = openfile(pname2,"w"); + putptable(fproc,f,FALSE); + report("inline substitutions",Ssubst); +#ifdef VERBOSE + if (verbose_flag) { + Sdiagnostics(); + } +#endif +#ifdef DEBUG + core_usage(); +#endif + exit(0); +} diff --git a/util/ego/il/il.h b/util/ego/il/il.h new file mode 100644 index 000000000..fb5e4b4dd --- /dev/null +++ b/util/ego/il/il.h @@ -0,0 +1,69 @@ +/* I N T E R N A L D A T A S T R U C T U R E S O F + * + * I N L I N E S U B S T I T U T I O N + * + */ + + +extern int calnr; +extern calcnt_p cchead; /* calcnt info of current proc */ + +/* Macro's for extended data structures */ + +#define P_CALS p_extend->px_il.p_cals +#define P_SIZE p_extend->px_il.p_size +#define P_FORMALS p_extend->px_il.p_formals +#define P_NRCALLED p_extend->px_il.p_nrcalled +#define P_CCADDR p_extend->px_il.p_ccaddr +#define P_LADDR p_extend->px_il.p_laddr +#define P_ORGLABELS p_extend->px_il.p_orglabels +#define P_ORGLOCALS p_extend->px_il.p_orglocals + +/* flags2: */ + +#define PF_UNSUITABLE 01 +#define PF_NO_INLPARS 02 +#define PF_FALLTHROUGH 04 +#define PF_DISPENSABLE 010 +#define PF_CHANGED 020 + + +/* kinds of usages: */ + +#define USE 0 +#define CHANGE 1 +#define ADDRESS 2 + + + + +/* We do not expand calls if: + * - the called procedure has to many local variables + * - the calling procedure is already very large + * - the called procedure is to large. + */ + +#define MANY_LOCALS(p) (p->p_localbytes > LOCAL_THRESHOLD) +#define LOCAL_THRESHOLD 200 +#define BIG_CALLER(p) (p->P_SIZE > CALLER_THRESHOLD) +#define CALLER_THRESHOLD 500 +#define BIG_PROC(p) (p->P_SIZE > CALLEE_THRESHOLD) +#define CALLEE_THRESHOLD 100 + +#define FALLTHROUGH(p) (p->p_flags2 & PF_FALLTHROUGH) +#define DISPENSABLE(p) p->p_flags2 |= PF_DISPENSABLE +#define IS_DISPENSABLE(p) (p->p_flags2 & PF_DISPENSABLE) +#define SELECTED(c) c->cl_flags |= CLF_SELECTED +#define IS_SELECTED(c) (c->cl_flags & CLF_SELECTED) +#define EVER_EXPANDED(c) c->cl_flags |= CLF_EVER_EXPANDED +#define IS_EVER_EXPANDED(c) (c->cl_flags & CLF_EVER_EXPANDED) +#define UNSUITABLE(p) p->p_flags2 |= PF_UNSUITABLE +#define SUITABLE(p) (!(p->p_flags2&PF_UNSUITABLE)) +#define INLINE_PARS(p) (!(p->p_flags2&PF_NO_INLPARS)) +#define PARAMS_UNKNOWN(p) (p->p_nrformals == UNKNOWN_SIZE) + +extern int Ssubst; +#ifdef VERBOSE +extern int Senv,Srecursive,Slocals,Sinstrlab,Sparsefails,Spremoved,Scals; +extern int Sbig_caller,Sdispensable,Schangedcallee,Sbigcallee,Sspace,Szeroratio; +#endif diff --git a/util/ego/il/il1_anal.c b/util/ego/il/il1_anal.c new file mode 100644 index 000000000..2e8acd28c --- /dev/null +++ b/util/ego/il/il1_anal.c @@ -0,0 +1,177 @@ +/* I N L I N E S U B S T I T U T I O N + * + * I L 1 _ A N A L . C + */ + +#include +#include "../share/types.h" +#include "il.h" +#include "../share/debug.h" +#include "../share/alloc.h" +#include "../share/global.h" +#include "../share/lset.h" +#include "../share/aux.h" +#include "../../../h/em_mnem.h" +#include "../../../h/em_pseu.h" +#include "il1_aux.h" +#include "il1_formal.h" +#include "il1_cal.h" +#include "il1_anal.h" +#include "il_aux.h" +#include "../share/put.h" + +#define BODY_KNOWN(p) (p->p_flags1 & (byte) PF_BODYSEEN) +#define ENVIRON(p) (p->p_flags1 & (byte) PF_ENVIRON) +#define RETURN_BLOCK(b) (Lnrelems(b->b_succ) == 0) +#define LAST_BLOCK(b) (b->b_next == (bblock_p) 0) + +/* Daisy chain recursion not yet accounted for: */ +#define RECURSIVE(p) (Cis_elem(p->p_id,p->p_calling)) +/* +#define CALLS_UNKNOWN(p) (p->p_flags1 & (byte) PF_CALUNKNOWN) +*/ +#define CALLS_UNKNOWN(p) (FALSE) + + + +apriori(proctab) + proc_p proctab; +{ + /* For every procedure, see if we can determine + * from the information provided by the previous + * phases of the optimizer that it cannot or should not + * be expanded in line. This will reduce the length + * of the call list. + */ + + register proc_p p; + + for (p = proctab; p != (proc_p) 0; p = p->p_next) { + if (!BODY_KNOWN(p) || + ENVIRON(p) || RECURSIVE(p) || + PARAMS_UNKNOWN(p) || MANY_LOCALS(p)) { + UNSUITABLE(p); +#ifdef VERBOSE + if (BODY_KNOWN(p)) { + if (ENVIRON(p)) Senv++; + if (RECURSIVE(p)) Srecursive++; + if (MANY_LOCALS(p)) Slocals++; + } +#endif + } + } +} + + +STATIC check_labels(p,arglist) + proc_p p; + arg_p arglist; +{ + /* Check if any of the arguments contains an instruction + * label; if so, make p unsuitable. + */ + + arg_p arg; + + for (arg = arglist; arg != (arg_p) 0; arg = arg->a_next) { + if (arg->a_type == ARGINSTRLAB) { + UNSUITABLE(p); +#ifdef VERBOSE + Sinstrlab++; +#endif + break; + } + } +} + + + +STATIC anal_instr(p,b,cf) + proc_p p; + bblock_p b; + FILE *cf; +{ + /* Analyze the instructions of block b + * within procedure p. + * See which parameters are used, changed + * or have their address taken. Recognize + * the actual parameter expressions of + * the CAL instructions. + */ + + register line_p l; + + for (l = b->b_start; l != (line_p) 0; l = l->l_next) { + switch(INSTR(l)) { + case op_cal: + anal_cal(p,l,b,cf); + break; + case op_stl: + case op_inl: + case op_del: + case op_zrl: + formal(p,b,off_set(l),SINGLE,CHANGE); + /* see if the local is a parameter. + * If so, it is a one-word parameter + * that is stored into. + */ + break; + case op_sdl: + formal(p,b,off_set(l),DOUBLE,CHANGE); + break; + case op_lol: + formal(p,b,off_set(l),SINGLE,USE); + break; + case op_ldl: + formal(p,b,off_set(l),DOUBLE,USE); + break; + case op_sil: + case op_lil: + formal(p,b,off_set(l),POINTER,USE); + break; + case op_lal: + formal(p,b,off_set(l),UNKNOWN,ADDRESS); + break; + case ps_rom: + case ps_con: + case ps_bss: + case ps_hol: + check_labels(p,ARG(l)); + break; + } + } +} + + + +anal_proc(p,cf,ccf) + proc_p p; + FILE *cf,*ccf; +{ + /* Analyze a procedure; use information + * stored in its basic blocks or in + * its instructions. + */ + + register bblock_p b; + bool fallthrough = TRUE; + + cchead = (calcnt_p) 0; + for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) { + if (RETURN_BLOCK(b) && !LAST_BLOCK(b)) { + fallthrough = FALSE; + /* p contains a RET instruction somewhere + * in the middle of its code. + */ + } + anal_instr(p,b,cf); /* analyze instructions */ + } + if (fallthrough) { + p->p_flags2 |= PF_FALLTHROUGH; + } + rem_indir_acc(p); + /* don't expand formal that may be accessed indirectly */ + p->P_CCADDR = putcc(cchead,ccf); + /* write calcnt info and remember disk address */ + remcc(cchead); +} diff --git a/util/ego/il/il1_anal.h b/util/ego/il/il1_anal.h new file mode 100644 index 000000000..ed01629f5 --- /dev/null +++ b/util/ego/il/il1_anal.h @@ -0,0 +1,17 @@ +/* I N L I N E S U B S T I T U T I O N + * + * I L 1 _ A N A L . H + */ + +extern apriori(); /* (proc_p proctab) + * For every procedure, see if we can determine + * from the information provided by the previous + * phases of the optimizer that it cannot or should not + * be expanded in line. This will reduce the length + * of the call list. + */ +extern anal_proc(); /* (proc_p p, FILE *cf, *cff) + * Analyse a procedure. See which formal parameters + * it uses and which procedures it calls. + * cf and ccf are the call-file and the call-count file. + */ diff --git a/util/ego/il/il1_aux.c b/util/ego/il/il1_aux.c new file mode 100644 index 000000000..b8602c024 --- /dev/null +++ b/util/ego/il/il1_aux.c @@ -0,0 +1,208 @@ +/* I N L I N E S U B S T I T U T I O N + * + * I L 1 _ A U X . C + */ + +#include "../share/types.h" +#include "il.h" +#include "../share/debug.h" +#include "../share/alloc.h" +#include "../share/global.h" +#include "../share/lset.h" +#include "../../../h/em_spec.h" +#include "il_aux.h" +#include "il1_aux.h" + +#define CHANGE_INDIR(p) (p->p_change->c_flags & CF_INDIR) +#define USE_INDIR(p) (p->p_use->u_flags & UF_INDIR) + +#define IS_INSTR(c) (c >= sp_fmnem && c <= sp_lmnem) + + +bool same_size(t1,t2) + int t1, t2; +{ + /* See if the two types have the same size */ + + return tsize(t1) == tsize(t2); +} + + + +STATIC bool is_reg(off,s) + offset off; + int s; +{ + /* See if there is a register message + * for the local or parameter at offset off + * and size s. + */ + + Lindex i; + arg_p arg; + + for (i = Lfirst(mesregs); i != (Lindex) 0; i = Lnext(i,mesregs)) { + arg = ((line_p) Lelem(i))->l_a.la_arg->a_next; + if (arg->a_a.a_offset == off && + arg->a_next->a_a.a_offset == s) { + return TRUE; + } + } + return FALSE; +} + + +rem_actuals(acts) + actual_p acts; +{ + /* remove the actual-list */ + + actual_p a,next; + + for (a = acts; a != (actual_p) 0; a = next) { + next = a->ac_next; + /* REMOVE CODE OF a->ac_exp HERE */ + oldactual(a); + } +} + + + +remov_formals(p) + proc_p p; +{ + /* Remove the list of formals of p */ + + formal_p f, next; + + for (f = p->P_FORMALS; f != (formal_p) 0; f = next) { + next = f->f_next; + oldformal(f); + } + p->P_FORMALS = (formal_p) 0; +} + + + +rem_indir_acc(p) + proc_p p; +{ + /* Formals that may be accessed indirectly + * cannot be expanded in line, so they are + * removed from the formals list. + */ + + formal_p prev, f, next; + + if (!USE_INDIR(p) && !CHANGE_INDIR(p)) return; + /* Any formal for which we don't have + * a register message is now doomed. + */ + prev = (formal_p) 0; + for (f = p->P_FORMALS; f != (formal_p) 0; f = next) { + next = f->f_next; + if (!is_reg(f->f_offset,tsize(f->f_type))) { + if (prev == (formal_p) 0) { + p->P_FORMALS = next; + } else { + prev->f_next = next; + } + oldformal(f); + } + } +} + + + +bool par_overlap(off1,t1,off2,t2) + offset off1,off2; + int t1,t2; +{ + /* See if the parameter at offset off1 and type t1 + * overlaps the paramete at offset off2 and type t2. + */ + + if (off1 > off2) { + return off2 + tsize(t2) > off1; + } else { + if (off2 > off1) { + return off1 + tsize(t1) > off2; + } else { + return TRUE; + } + } +} + + + +short looplevel(b) + bblock_p b; +{ + /* determine the loop nesting level of basic block b; + * this is the highest nesting level of all blocks + * that b is part of. + * Note that the level of a loop is 0 for outer loops, + * so a block inside a loop with nesting level N has + * looplevel N+1. + */ + + Lindex i; + short max = 0; + + for (i = Lfirst(b->b_loops); i != (Lindex)0; i = Lnext(i,b->b_loops)) { + if (((loop_p) Lelem(i))->lp_level >= max) { + max = ((loop_p) Lelem(i))->lp_level + 1; + } + } + return max; +} + + + +short proclength(p) + proc_p p; +{ + /* count the number of EM instructions of p */ + + register short cnt; + register bblock_p b; + register line_p l; + + cnt = 0; + for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) { + for (l = b->b_start; l != (line_p) 0; l = l->l_next) { + if (IS_INSTR(INSTR(l))) { + /* skip pseudo instructions */ + cnt++; + } + } + } + return cnt; +} + + + + + +line_p copy_code(l1,l2) + line_p l1,l2; +{ + /* copy the code between l1 and l2 */ + + line_p head, tail, l, lnp; + + head = (line_p) 0; + for (lnp = l1; ; lnp = lnp->l_next) { + l = duplicate(lnp); + if (head == (line_p) 0) { + head = tail = l; + PREV(l) = (line_p) 0; + } else { + tail->l_next = l; + PREV(l) = tail; + tail = l; + } + if (lnp == l2) break; + } + return head; +} diff --git a/util/ego/il/il1_aux.h b/util/ego/il/il1_aux.h new file mode 100644 index 000000000..9f7ee795f --- /dev/null +++ b/util/ego/il/il1_aux.h @@ -0,0 +1,38 @@ +/* I N L I N E S U B S T I T U T I O N + * + * I L 1 _ A U X . H + */ + +extern bool same_size(); /* (int t1,t2) + * See if the two types t1 and t2 have + * the same size. + */ +extern rem_actuals(); /* (actual_p atcs) + * remove an actual-list from core. + */ +extern remov_formals(); /* (proc_p p) + * Remove the formals-list of p from core. + */ +extern rem_indir_acc(); /* (proc_p p) + * Remove formal that may be accessed + * indirectly from formal lists of p + */ +extern bool par_overlap(); /* (offset off1, int t1, offset off2, int t2) + * See if the formal at offset off1 and type t1 + * overlaps the formal at offset off2 + * and type t2. + */ +extern short looplevel(); /* (bblock_p b) + * Determine the loop nesting level of b. + */ +extern short proclength(); /* (proc_p p) + * Determine the number of EM instructions + * in p. Do not count pseudos. + */ + +extern line_p copy_code(); /* (line_p l1,l2) + * copy the code between l1 and l2. + * Pseudos may not be contained in + * the list of instructions. If l1==l2 + * the result is only one instruction. + */ diff --git a/util/ego/il/il1_cal.c b/util/ego/il/il1_cal.c new file mode 100644 index 000000000..7a694699b --- /dev/null +++ b/util/ego/il/il1_cal.c @@ -0,0 +1,138 @@ +/* I N L I N E S U B S T I T U T I O N + * + * I L 1 _ C A L . C + */ + +#include +#include "../share/types.h" +#include "il.h" +#include "il1_cal.h" +#include "../share/debug.h" +#include "../share/alloc.h" +#include "../share/global.h" +#include "../share/lset.h" +#include "../../../h/em_spec.h" +#include "../../../h/em_mnem.h" +#include "il1_aux.h" +#include "../share/parser.h" + +STATIC actual_p acts, *app; + +#define INIT_ACTS() {acts = (actual_p) 0; app = &acts;} +#define APPEND_ACTUAL(a) {*app = a; app = &a->ac_next;} + +STATIC make_actual(l1,l2,size) + line_p l1,l2; + offset size; +{ + /* Allocate a struct for a new actual parameter + * expression, the code of which extends from + * l1 to l2. + */ + + actual_p a; + + a = newactual(); + a->ac_exp = copy_code(l1,l2); + a->ac_size = size; + APPEND_ACTUAL(a); /* append it to actual-list */ +} + + + +STATIC bool chck_asp(p,l) + proc_p p; + line_p l; +{ + /* We require a call to a procedure p that has n formal + * parameters to be followed by an 'asp n' instruction + * (i.e. the caller should remove the actual parameters). + */ + + return (p->p_nrformals == 0 || (l != (line_p) 0 &&INSTR(l) == op_asp && + TYPE(l) == OPSHORT && SHORT(l) == p->p_nrformals)); +} + + + +STATIC inc_count(caller,callee) + proc_p caller, callee; +{ + /* Update the call-count information. + * Record the fact that there is one more call + * to 'callee', appearing in 'caller'. + */ + + calcnt_p cc; + + if (!SUITABLE(caller)) return; + /* if the calling routine is never expanded in line + * we do not need call-count information. + */ + for (cc = cchead; cc != (calcnt_p) 0; cc = cc->cc_next) { + if (cc->cc_proc == callee) { + cc->cc_count++; + /* #calls to callee from caller */ + return; + } + } + /* This is the first call from caller to callee. + * Allocate a new calcnt struct. + */ + cc = newcalcnt(); + cc->cc_proc = callee; + cc->cc_count = 1; + cc->cc_next = cchead; /* insert it at front of list */ + cchead = cc; +} + + + +anal_cal(p,call,b,cf) + proc_p p; + line_p call; + bblock_p b; + FILE *cf; +{ + /* Analyze a call instruction. If the called + * routine may be expanded in line, try to + * recognize the actual parameter expressions of + * the call and extend the call list. + */ + + call_p c; + line_p lnp; + proc_p callee; + +#ifdef VERBOSE + Scals++; +#endif + calnr++; + callee = PROC(call); + if (SUITABLE(callee)) { + /* The called procedure may be expanded */ + callee->P_NRCALLED++; /* #calls to callee from anywhere */ + INIT_ACTS(); + if (parse(PREV(call),callee->p_nrformals,&lnp,0,make_actual) && + chck_asp(callee,call->l_next)) { + /* succeeded in recognizing the actuals */ + c = newcall(); + c->cl_caller = p; + c->cl_id = calnr; + c->cl_proc = callee; + c->cl_looplevel = (byte) looplevel(b); + if (c->cl_looplevel > 0 && IS_FIRM(b)) { + c->cl_flags |= CLF_FIRM; + } + c->cl_actuals = acts; + inc_count(p,callee); + /* update call-count info */ + putcall(c,cf,(short) 0); /* write the call to the calfile */ + } else { +#ifdef VERBOSE + Sparsefails++; +#endif + rem_actuals(acts); + } + } +} diff --git a/util/ego/il/il1_cal.h b/util/ego/il/il1_cal.h new file mode 100644 index 000000000..191e7ae58 --- /dev/null +++ b/util/ego/il/il1_cal.h @@ -0,0 +1,31 @@ +/* I N L I N E S U B S T I T U T I O N + * + * I L 1 _ C A L . C + */ + +struct class { + byte src_class; + byte res_class; +}; + +typedef struct class *class_p; + +extern struct class classtab[]; + +#define NOCLASS 0 +#define CLASS1 1 +#define CLASS2 2 +#define CLASS3 3 +#define CLASS4 4 +#define CLASS5 5 +#define CLASS6 6 +#define CLASS7 7 +#define CLASS8 8 +#define CLASS9 9 + + +extern anal_cal(); /* (line_p call, bblock_p b) + * analyze a call instruction; + * try to recognize the actual parameter + * expressions. + */ diff --git a/util/ego/il/il1_formal.c b/util/ego/il/il1_formal.c new file mode 100644 index 000000000..1a616efcc --- /dev/null +++ b/util/ego/il/il1_formal.c @@ -0,0 +1,141 @@ +/* I N L I N E S U B S T I T U T I O N + * + * I L 1 _ F O R M A L . C + */ + +#include "../share/types.h" +#include "il.h" +#include "../share/debug.h" +#include "../share/alloc.h" +#include "../share/global.h" +#include "../share/lset.h" +#include "il1_aux.h" +#include "il1_formal.h" + +#define NOT_USED(f) (!(f->f_flags & USEMASK)) +#define USED_ONCE(f) f->f_flags |= FF_ONCEUSED +#define USED_OFTEN(f) f->f_flags |= FF_OFTENUSED +#define BADFORMAL(f) f->f_flags |= FF_BAD + +#define OUTSIDE_LOOP(b) (Lnrelems(b->b_loops) == 0) +#define IS_FORMAL(x) (x >= 0) + + + +formal_p find_formal(p,type,off) + proc_p p; + int type; + offset off; +{ + /* Find a formal parameter of p + * If the formal overlaps with an existing formal + * or has an unknown type (i.e. its address is used) + * 0 is returned. + */ + + formal_p f,prev,nf; + + if (type == UNKNOWN) return (formal_p) 0; + prev = (formal_p) 0; + for (f = p->P_FORMALS; f != (formal_p) 0; f = f->f_next) { + if (f->f_offset >= off) break; + prev = f; + } + if (f != (formal_p) 0 && f->f_offset == off) { + return (same_size(f->f_type,type) ? f : (formal_p) 0); + } + if (f != (formal_p) 0 && par_overlap(off,type,f->f_offset,f->f_type)) { + return (formal_p) 0; + } + if (prev != (formal_p) 0 && par_overlap(prev->f_offset,prev->f_type, + off,type)) { + return (formal_p) 0; + } + nf = newformal(); + nf->f_type = type; + nf->f_offset = off; + if (prev == (formal_p) 0) { + p->P_FORMALS = nf; + } else { + prev->f_next = nf; + } + nf->f_next = f; + return nf; +} + + + +STATIC no_inl_pars(p) + proc_p p; +{ + /* p may not have any in line parameters */ + + p->p_flags2 |= PF_NO_INLPARS; + remov_formals(p); +} + + + +STATIC inc_use(f,b) + formal_p f; + bblock_p b; +{ + /* Increment the use count of formal f. + * The counter has only three states: not used, + * used once, used more than once. + * We count the number of times the formal + * is used dynamically (rather than statically), + * so if it is used in a loop, the counter + * is always set to more than once. + */ + + if (NOT_USED(f) && OUTSIDE_LOOP(b)) { + USED_ONCE(f); + } else { + USED_OFTEN(f); + } +} + + + +formal(p,b,off,type,usage) + proc_p p; + bblock_p b; + offset off; + int type, + usage; +{ + /* Analyze a reference to a parameter of p + * (occurring within basic block b). + * The parameter has offset off. If this + * offset is less than 0, it is not a + * parameter, but a local. + * The type can be SINGLE (1 word), DOUBLE + * (2 words), POINTER or UNKNOWN. + */ + + formal_p f; + + if (!IS_FORMAL(off) || !SUITABLE(p) || !INLINE_PARS(p)) return; + /* We are not interested in formal parameters of + * proccedures that will never be expanded in line, + * or whose parameters will not be expanded in line. + */ + f = find_formal(p,type,off); + /* Find the formal; if not found, create one; + * if inconsistent with previous formals (e.g. + * overlapping formals) then return 0; + * also fills in its type. + */ + if (f == (formal_p) 0) { + no_inl_pars(p); + /* parameters of p may not be expanded in line */ + } else { + if (usage == CHANGE) { + /* don't expand f in line */ + BADFORMAL(f); + } else { + inc_use(f,b); /* increment use count */ + } + } +} diff --git a/util/ego/il/il1_formal.h b/util/ego/il/il1_formal.h new file mode 100644 index 000000000..062043c7b --- /dev/null +++ b/util/ego/il/il1_formal.h @@ -0,0 +1,11 @@ +/* I N L I N E S U B S T I T U T I O N + * + * I L 1 _ F O R M A L . C + */ + +extern formal(); /* (proc_p p; bblock_p b; offset off; + * int type, usage) + * Analyze a reference to a parameter of p. + * The type denotes its size (single,double, + * pointer). + */ diff --git a/util/ego/il/il2_aux.c b/util/ego/il/il2_aux.c new file mode 100644 index 000000000..0d393c747 --- /dev/null +++ b/util/ego/il/il2_aux.c @@ -0,0 +1,718 @@ +/* I N L I N E S U B S T I T U T I O N + * + * I L 2 _ A U X . C + */ + +#include +#include "../share/types.h" +#include "il.h" +#include "../share/debug.h" +#include "../share/alloc.h" +#include "../share/global.h" +#include "../share/lset.h" +#include "../../../h/em_spec.h" +#include "../../../h/em_mnem.h" +#include "il_aux.h" +#include "il2_aux.h" +#include "../share/get.h" +#include "../share/aux.h" + +#define CHANGE_INDIR(p) (p->p_change->c_flags & CF_INDIR) +#define USE_INDIR(p) (p->p_use->u_flags & UF_INDIR) + +#define OFTEN_USED(f) ((f->f_flags&FF_OFTENUSED) == FF_OFTENUSED) +#define CHANGE_EXT(p) (Cnrelems(p->p_change->c_ext) > 0) +#define NOT_INLINE(a) (a->ac_inl = FALSE) +#define INLINE(a) (a->ac_inl = TRUE) + + +#define CHANGED(p) p->p_flags2 |= PF_CHANGED +#define IS_CHANGED(p) (p->p_flags2 & PF_CHANGED) + + + +STATIC bool match_pars(fm,act) + formal_p fm; + actual_p act; +{ + /* Check if every actual parameter has the same + * size as its corresponding formal. If not, the + * actual parameters should not be expanded in line. + */ + + while (act != (actual_p) 0) { + if (fm == (formal_p) 0 || tsize(fm->f_type) != act->ac_size) { + return FALSE; + } + act = act->ac_next; + fm = fm->f_next; + } + return (fm == (formal_p) 0 ? TRUE : FALSE); +} + + +STATIC bool change_act(p,act) + proc_p p; + actual_p act; +{ + /* See if a call to p migth change any of the + * operands of the actual parameter expression. + * If the parameter is to be expanded in line, + * we must be sure its value does not depend + * on the point in the program where it is + * evaluated. + */ + + line_p l; + + for (l = act->ac_exp; l != (line_p) 0; l = l->l_next) { + switch(INSTR(l)) { + case op_lil: + case op_lof: + case op_loi: + case op_los: + case op_ldf: + return TRUE; + /* assume worst case */ + case op_lol: + case op_ldl: + if (CHANGE_INDIR(p)) { + return TRUE; + } + break; + case op_loe: + case op_lde: + if (CHANGE_INDIR(p) || CHANGE_EXT(p)) { + return TRUE; + } + break; + } + } + return FALSE; +} + + + +STATIC bool is_simple(expr) + line_p expr; +{ + /* See if expr is something simple, i.e. a constant or + * a variable. So the expression must consist of + * only one instruction. + */ + + + if (expr->l_next == (line_p) 0) { + switch(INSTR(expr)) { + case op_loc: + case op_ldc: + case op_lol: + case op_ldl: + case op_loe: + case op_lde: + return TRUE; + } + } + return FALSE; +} + + + +STATIC bool too_expensive(fm,act) + formal_p fm; + actual_p act; +{ + /* If the formal parameter is used often and the + * actual parameter is not something simple + * (i.e. an expression, not a constant or variable) + * it may be too expensive too expand the parameter + * in line. + */ + + return (OFTEN_USED(fm) && !is_simple(act->ac_exp)); +} +anal_params(c) + call_p c; +{ + /* Determine which of the actual parameters of a + * call may be expanded in line. + */ + + proc_p p; + actual_p act; + formal_p form; + int inlpars = 0; + + p = c->cl_proc; /* the called procedure */ + if (!INLINE_PARS(p) || !match_pars(p->P_FORMALS, c->cl_actuals)) { + for (act = c->cl_actuals; act != (actual_p) 0; + act = act->ac_next) { + NOT_INLINE(act); + } + return; /* "# of inline pars." field in cl_flags remains 0 */ + } + for (act = c->cl_actuals, form = p->P_FORMALS; act != (actual_p) 0; + act = act->ac_next, form = form->f_next) { + if (form->f_flags & FF_BAD || + change_act(p,act) || too_expensive(form,act)) { + NOT_INLINE(act); + } else { + INLINE(act); + inlpars++; + } + } + if (inlpars > 15) inlpars = 15; /* We've only got 4 bits! */ + c->cl_flags |= inlpars; /* number of inline parameters */ +} + + +STATIC short space_saved(c) + call_p c; +{ + /* When a call gets expanded in line, the total size of the + * code usually gets incremented, because we have to + * duplicate the text of the called routine. However, we save + * ourselves a CAL instruction and possibly anASP instruction + * (if the called procedure has parameters). Moreover, if we + * can put some parameters in line, we don't have to push + * their results on the stack before doing the call, so we + * save some code here too. The routine estimates the amount of + * code saved, expressed in number of EM instructions. + */ + + return (1 + (c->cl_flags & CLF_INLPARS) + (c->cl_proc->p_nrformals>0)); +} + +STATIC short param_score(c) + call_p c; +{ + /* If a call has an inline parameter that is a constant, + * chances are high that other optimization techniques + * can do further optimizations, especially if the constant + * happens to be "0". So the call gets extra points for this. + */ + + register actual_p act; + line_p l; + short score = 0; + + for (act = c->cl_actuals; act != (actual_p) 0; act = act->ac_next) { + if (act->ac_inl) { + l = act->ac_exp; + if (l->l_next == (line_p) 0 && + (INSTR(l) == op_loc || INSTR(l) == op_ldc)) { + score += (off_set(l) == (offset) 0 ? 2 : 1); + /* 0's count for two! */ + } + } + } + return score; +} + + + + + +assign_ratio(c) + call_p c; +{ + /* This routine is one of the most important ones + * of the inline substitution phase. It assigns a number + * (a 'ratio') to a call, indicating how desirable + * it is to expand the call in line. + * Currently, a very simplified straightforward heuristic + * is used. + */ + + short ll, loopfact, ratio; + + ll = c->cl_proc->P_SIZE - space_saved(c); + if (ll <= 0) ll = 1; + ratio = 1000 / ll; + if (ratio == 0) ratio = 1; + /* Add points if the called procedure falls through + * it's end (no BRA needed) or has formal parameters + * (ASP can be deleted). + */ + if (c->cl_proc->p_flags2 & PF_FALLTHROUGH) { + ratio += 10; + } + if (c->cl_proc->p_nrformals > 0) { + ratio += 10; + } + if (c->cl_caller->p_localbytes == 0) { + ratio -= 10; + } + ratio += (10 *param_score(c)); + /* Extra points for constants as parameters */ + if (ratio <= 0) ratio = 1; + ll = c->cl_looplevel+1; + if (ll == 1 && !IS_CALLED_IN_LOOP(c->cl_caller)) ll = 0; + /* If the call is not in a loop and the called proc. is never called + * in a loop, ll is set to 0. + */ + loopfact = (ll > 3 ? 10 : ll*ll); + ratio *= loopfact; + if (c->cl_flags & CLF_FIRM) { + ratio = 2*ratio; + } + c->cl_ratio = ratio; +} + + +call_p abstract(c) + call_p c; +{ + /* Abstract information from the call that is essential + * for choosing the calls that will be expanded. + * Put the information is an 'abstracted call'. + */ + + call_p a; + + a = newcall(); + a->cl_caller = c->cl_caller; + a->cl_id = c->cl_id; + a->cl_proc = c->cl_proc; + a->cl_looplevel = c->cl_looplevel; + a->cl_ratio = c->cl_ratio; + a->cl_flags = c->cl_flags; + return a; +} + + + +STATIC adjust_counts(callee,ccf) + proc_p callee; + FILE *ccf; +{ + /* A call to callee is expanded in line; + * the text of callee is not removed, so + * every proc called by callee gets its + * P_NRCALLED field incremented. + */ + + calcnt_p cc, head; + + head = getcc(ccf,callee); /* get calcnt info of called proc */ + for (cc = head; cc != (calcnt_p) 0; cc = cc->cc_next) { + cc->cc_proc->P_NRCALLED += cc->cc_count; + } + remcc(head); /* remove calcnt info */ +} + + + +STATIC bool is_dispensable(callee,ccf) + proc_p callee; + FILE *ccf; +{ + /* A call to callee is expanded in line. + * Decrement its P_NRCALLED field and see if + * it can now be removed because it is no + * longer called. Procedures that ever have + * their address taken (via LPI) will never + * be removed, as they might be called indirectly. + */ + + if ((--callee->P_NRCALLED) == 0 && + (callee->p_flags1 & PF_LPI) == 0) { + DISPENSABLE(callee); + OUTTRACE("procedure %d can be removed",callee->p_id); +#ifdef VERBOSE + Spremoved++; +#endif + return TRUE; + } else { + adjust_counts(callee,ccf); + return FALSE; + } +} + + + + +STATIC call_p nested_calls(a) + call_p a; +{ + /* Get a list of all calls that will appear in the + * EM text if the call 'a' is expanded in line. + * These are the calls in the P_CALS list of the + * called procedure. + */ + + call_p c, cp, head, *cpp; + + head = (call_p) 0; + cpp = &head; + for (c = a->cl_proc->P_CALS; c != (call_p) 0; c = c->cl_cdr) { + cp = abstract(c); + cp->cl_looplevel += a->cl_looplevel; + cp->cl_flags = (byte) 0; + if (a->cl_flags & CLF_FIRM) { + cp->cl_flags |= CLF_FIRM; + } + assign_ratio(cp); + *cpp = cp; + cpp = &cp->cl_cdr; + } + return head; +} + + + + +STATIC call_p find_origin(c) + call_p c; +{ + /* c is a nested call. Find the original call. + * This origional must be in the P_CALS list + * of the calling procedure. + */ + + register call_p x; + + for (x = c->cl_caller->P_CALS; x != (call_p) 0; x = x->cl_cdr) { + if (x->cl_id == c->cl_id) return x; + } + assert(FALSE); + /* NOTREACHED */ +} + + + +STATIC selected(a) + call_p a; +{ + /* The call a is selected for in line expansion. + * Mark the call as being selected and get the + * calls nested in it; these will be candidates + * too now. + */ + + SELECTED(a); + EVER_EXPANDED(find_origin(a)); + a->cl_car = nested_calls(a); +} + + + + +STATIC compare(x,best,space) + call_p x, *best; + short space; +{ + /* See if x is better than the current best choice */ + + if (x != (call_p) 0 && !IS_CHANGED(x->cl_proc) && + x->cl_proc->P_SIZE - space_saved(x) <= space) { + if ((*best == (call_p) 0 && x->cl_ratio != 0) || + (*best != (call_p) 0 && x->cl_ratio > (*best)->cl_ratio )) { + *best = x; + } + } +} + + + + +STATIC call_p best_one(list,space) + call_p list; + short space; +{ + /* Find the best candidate of the list + * that has not already been selected. The + * candidate must fit in the given space. + * We look in the cdr as well as in the car + * direction. + */ + + call_p best = (call_p) 0; + call_p x,c; + + for (c = list; c != (call_p) 0; c = c->cl_cdr) { + if (IS_SELECTED(c)) { + compare(best_one(c->cl_car,space),&best,space); + } else { + compare(c,&best,space); + } + } + return best; +} + + + +STATIC singles(cals) + call_p cals; +{ + /* If a procedure is only called once, this call + * will be expanded in line, because it costs + * no extra space. + */ + + call_p c; + + for (c = cals; c != (call_p) 0; c = c->cl_cdr) { + if (IS_SELECTED(c)) { + singles(c->cl_car); + } else { + if (c->cl_proc->P_NRCALLED == 1 && + !IS_CHANGED(c->cl_proc) && + (c->cl_proc->p_flags1 & PF_LPI) == 0) { + c->cl_proc->P_NRCALLED = 0; + SELECTED(c); + EVER_EXPANDED(find_origin(c)); + DISPENSABLE(c->cl_proc); + CHANGED(c->cl_caller); + OUTTRACE("procedure %d can be removed", + c->cl_proc->p_id); +#ifdef VERBOSE + Spremoved++; +#endif + } + } + } +} + + + +STATIC single_calls(proclist) + proc_p proclist; +{ + proc_p p; + + for (p = proclist; p != (proc_p) 0; p = p->p_next) { + if (!BIG_CALLER(p) && !IS_DISPENSABLE(p)) { + /* Calls appearing in a large procedure or in + * a procedure that was already eliminated + * are not considered. + */ + singles(p->P_CALS); + } + } +} + + + + +select_calls(proclist,ccf,space) + proc_p proclist; + FILE *ccf; + short space ; +{ + /* Select all calls that are to be expanded in line. */ + + proc_p p,chp; + call_p best, x; + + for (;;) { + best = (call_p) 0; + chp = (proc_p) 0; /* the changed procedure */ + for (p = proclist; p != (proc_p) 0; p = p->p_next) { + if (!BIG_CALLER(p) && !IS_DISPENSABLE(p)) { + /* Calls appearing in a large procedure or in + * a procedure that was already eliminated + * are not considered. + */ + x = best_one(p->P_CALS,space); + compare(x,&best,space); + if (x == best) chp = p; + } + } + if (best == (call_p) 0) break; + if (!is_dispensable(best->cl_proc,ccf)) { + space -= (best->cl_proc->P_SIZE - space_saved(best)); + } + selected(best); + CHANGED(chp); + } + single_calls(proclist); +#ifdef VERBOSE + Sstat(proclist,space); +#endif +} + + + + +STATIC nonnested_calls(cfile) + FILE *cfile; +{ + register call_p c,a; + + while((c = getcall(cfile)) != (call_p) 0) { + /* find the call in the call list of the caller */ + for (a = c->cl_caller->P_CALS; + a != (call_p) 0 && c->cl_id != a->cl_id; a = a->cl_cdr); + assert(a != (call_p) 0 && a->cl_proc == c->cl_proc); + if (IS_EVER_EXPANDED(a)) { + a->cl_actuals = c->cl_actuals; + c->cl_actuals = (actual_p) 0; + } + rem_call(c); + } +} + + + +STATIC copy_pars(src,dest) + call_p src, dest; +{ + /* Copy the actual parameters of src to dest. */ + + actual_p as,ad, *app; + + app = &dest->cl_actuals; + for (as = src->cl_actuals; as != (actual_p) 0; as = as->ac_next) { + ad = newactual(); + ad->ac_exp = copy_expr(as->ac_exp); + ad->ac_size = as->ac_size; + ad->ac_inl = as->ac_inl; + *app = ad; + app = &ad->ac_next; + } +} + + + +STATIC nest_pars(cals) + call_p cals; +{ + /* Recursive auxiliary procedure of add_actuals. */ + + call_p c,org; + + for (c = cals; c != (call_p) 0; c = c->cl_cdr) { + if (IS_SELECTED(c)) { + org = find_origin(c); + copy_pars(org,c); + nest_pars(c->cl_car); + } + } +} + + + +add_actuals(proclist,cfile) + proc_p proclist; + FILE *cfile; +{ + /* Fetch the actual parameters of all selected calls. + * For all non-nested calls (i.e. those calls that + * appeared originally in the EM text), we get the + * parameters from the cal-file. + * For nested calls (i.e. calls + * that are a result of in line substitution) we + * get the parameters from the original call. + */ + + proc_p p; + call_p a; + + nonnested_calls(cfile); + for (p = proclist; p != (proc_p) 0; p = p->p_next) { + for (a = p->P_CALS; a != (call_p) 0; a = a->cl_cdr) { + nest_pars(a->cl_car); + } + } +} + + + +STATIC clean(cals) + call_p *cals; +{ + call_p c,next,*cpp; + + /* Recursive auxiliary routine of cleancals */ + + cpp = cals; + for (c = *cpp; c != (call_p) 0; c = next) { + next = c->cl_cdr; + if (IS_SELECTED(c)) { + clean(&c->cl_car); + cpp = &c->cl_cdr; + } else { + assert(c->cl_car == (call_p) 0); + oldcall(c); + *cpp = next; + } + } +} + + +cleancals(proclist) + proc_p proclist; +{ + /* Remove all calls in the P_CALS list of p + * that were not selected for in line expansion. + */ + + register proc_p p; + + for (p = proclist; p != (proc_p) 0; p = p->p_next) { + clean(&p->P_CALS); + } +} + + + + +append_abstract(a,p) + call_p a; + proc_p p; +{ + /* Append an abstract of a call-descriptor to + * the call-list of procedure p. + */ + + call_p c; + + if (p->P_CALS == (call_p) 0) { + p->P_CALS = a; + } else { + for (c = p->P_CALS; c->cl_cdr != (call_p) 0; c = c->cl_cdr); + c->cl_cdr = a; + } +} + + +#ifdef VERBOSE + +/* At the end, we traverse the entire call-list, to see why the + * remaining calls were not expanded inline. + */ + + +Sstatist(list,space) + call_p list; + short space; +{ + call_p c; + + for (c = list; c != (call_p) 0; c = c->cl_cdr) { + if (IS_SELECTED(c)) { + Sstatist(c->cl_car,space); + } else { + if (IS_CHANGED(c->cl_proc)) Schangedcallee++; + else if (BIG_PROC(c->cl_proc)) Sbigcallee++; + else if (c->cl_proc->P_SIZE > space) Sspace++; + else if (c->cl_ratio == 0) Szeroratio++; + else assert(FALSE); + } + } +} + +Sstat(proclist,space) + proc_p proclist; + short space; +{ + proc_p p; + + for (p = proclist; p != (proc_p) 0; p = p->p_next) { + if (BIG_CALLER(p)) Sbig_caller++; + else if (IS_DISPENSABLE(p)) Sdispensable++; + else Sstatist(p->P_CALS,space); + } +} +#endif diff --git a/util/ego/il/il2_aux.h b/util/ego/il/il2_aux.h new file mode 100644 index 000000000..8ef35527c --- /dev/null +++ b/util/ego/il/il2_aux.h @@ -0,0 +1,36 @@ +extern anal_params(); /* (call_p c) + * See which parameters of the call + * may be expanded in line. + */ +extern assign_ratio(); /* (call_p c) + * Assigna ratio number to the call, + * indicating how desirable it is to + * expand the call in line. + */ +extern call_p abstract(); /* (call_p c) + * Abstract essential information from + * the call. + */ +extern select_calls(); /* (call_p alist; FILE *ccf;short space) + * Select the best calls to be expanded. + * Every procedure gets a list of + * selected calls appearing in it. + * space is the amount of space that the + * program is allowed to grow + * (expressed in number of EM instructions). + */ +extern cleancals(); /* (proc_p plist) + * Remove all calls that were not selected. + */ +extern add_actuals(); /* (proc_p plist; FILE *cfile) + * Add the actual parameters to the descriptor abstracts + * of the selected calls. + * the calfile contains the full descriptors of all + * calls. + * These two are combined to yield a file of full + * descriptors of the selected calls. + */ +extern append_abstract(); /* (call_p a; proc_p p) + * Put the call-descriptor abstract in the p_cals + * list of p. + */ diff --git a/util/ego/il/il3_aux.c b/util/ego/il/il3_aux.c new file mode 100644 index 000000000..dfeefa36c --- /dev/null +++ b/util/ego/il/il3_aux.c @@ -0,0 +1,63 @@ +/* I N L I N E S U B S T I T U T I O N + * + * I L 3 _ A U X . C + */ + + +#include "../share/types.h" +#include "il.h" +#include "../share/debug.h" +#include "../share/alloc.h" +#include "../share/global.h" +#include "il_aux.h" +#include "il3_aux.h" + + + +line_p last_line(lines) + line_p lines; +{ + /* Determine the last line of a list */ + + register line_p l; + + assert (l != (line_p) 0); + for (l = lines; l->l_next != (line_p) 0; l = l->l_next); + return l; +} + + + +app_list(list,l) + line_p list,l; +{ + /* Append the list after line l */ + + line_p llast; + + assert(l != (line_p) 0); + assert (list != (line_p) 0); + llast = last_line(list); + llast->l_next = l->l_next; + if (l->l_next != (line_p) 0) { + PREV(l->l_next) = llast; + } + l->l_next = list; + PREV(list) = l; +} + + + +rem_line(l) + line_p l; +{ + /* Remove a line from the list */ + + if (PREV(l) != (line_p) 0) { + PREV(l)->l_next = l->l_next; + } + if (l->l_next != (line_p) 0) { + PREV(l->l_next) = PREV(l); + } + oldline(l); +} diff --git a/util/ego/il/il3_aux.h b/util/ego/il/il3_aux.h new file mode 100644 index 000000000..afa8cdbd4 --- /dev/null +++ b/util/ego/il/il3_aux.h @@ -0,0 +1,15 @@ +/* I N L I N E S U B S T I T U T I O N + * + * I L 3 _ A U X . H + */ + +extern line_p last_line(); /* (line_p list) + * Find the last line of a list. + */ +extern app_list(); /* (line_p list,l) + * Put list after l + */ +extern rem_line(); /* (line_p l) + * Remove a line from a (doubly linked) + * list. + */ diff --git a/util/ego/il/il3_change.c b/util/ego/il/il3_change.c new file mode 100644 index 000000000..f9850035e --- /dev/null +++ b/util/ego/il/il3_change.c @@ -0,0 +1,583 @@ +/* I N L I N E S U B S T I T U T I O N + * + * I L 3 _ C H A N G E . C + */ + + +#include "../share/types.h" +#include "il.h" +#include "../share/debug.h" +#include "../share/alloc.h" +#include "../share/global.h" +#include "../share/def.h" +#include "../share/lset.h" +#include "../share/aux.h" +#include "../../../h/em_mnem.h" +#include "../../../h/em_pseu.h" +#include "../../../h/em_spec.h" +#include "../../../h/em_mes.h" +#include "../share/get.h" +#include "../share/put.h" +#include "il_aux.h" +#include "il3_change.h" +#include "il3_aux.h" + +/* chg_callseq */ + + + + +STATIC line_p par_expr(l,expr) + line_p l, expr; +{ + /* Find the first line of the expression of which + * l is the last line; expr contains a pointer + * to a copy of that expression; effectively we + * just have to tally lines. + */ + + line_p lnp; + + for (lnp = expr->l_next; lnp != (line_p) 0; lnp = lnp->l_next) { + assert(l != (line_p) 0); + l = PREV(l); + } + return l; +} + + + +STATIC rem_text(l1,l2) + line_p l1,l2; +{ + /* Remove the lines from l1 to l2 (inclusive) */ + + line_p l, lstop; + l = PREV(l1); + lstop = l2->l_next; + while (l->l_next != lstop) { + rem_line(l->l_next); + } +} + + + +STATIC store_tmp(p,l,size) + proc_p p; + line_p l; + offset size; +{ + /* Emit code to store a 'size'-byte value in a new + * temporary local variable in the stack frame of p. + * Put this code after line l. + */ + + line_p lnp; + + lnp = int_line(tmplocal(p,size)); /* line with operand temp. */ + if (size == ws) { + lnp->l_instr = op_stl; /* STL temp. */ + } else { + if (size == 2*ws) { + lnp->l_instr = op_sdl; /* SDL temp. */ + } else { + /* emit 'LAL temp; STI size' */ + lnp->l_instr = op_lal; + appnd_line(lnp,l); + l = lnp; + assert ((short) size == size); + lnp = newline(OPSHORT); + SHORT(lnp) = size; + lnp->l_instr = op_sti; + } + } + appnd_line(lnp,l); +} + + + +STATIC chg_actuals(c,cal) + call_p c; + line_p cal; +{ + /* Change the actual parameter expressions of the call. */ + + actual_p act; + line_p llast,lfirst,l; + + llast = PREV(cal); + for (act = c->cl_actuals; act != (actual_p) 0; act = act->ac_next) { + lfirst = par_expr(llast,act->ac_exp); + /* the code from lfirst to llast is a parameter expression */ + if (act->ac_inl) { + /* in line parameter; remove it */ + l = llast; + llast = PREV(lfirst); + rem_text(lfirst,l); + } else { + store_tmp(curproc,llast,act->ac_size); + /* put a "STL tmp" -like instruction after the code */ + llast = PREV(lfirst); + } + } +} + + + +STATIC rm_callpart(c,cal) + call_p c; + line_p cal; +{ + /* Remove the call part, consisting of a CAL, + * an optional ASP and an optional LFR. + */ + + line_p l; + + l= PREV(cal); + rem_line(cal); + if (c->cl_proc->p_nrformals > 0) { + /* called procedure has parameters */ + assert (INSTR(l->l_next) == op_asp); + rem_line(l->l_next); + } + if (INSTR(l->l_next) == op_lfr) { + rem_line(l->l_next); + } +} + + + +chg_callseq(c,cal,l_out) + call_p c; + line_p cal,*l_out; +{ + /* Change the calling sequence. The actual parameter + * expressions are changed (in line parameters are + * removed, all other ones now store their result + * in a temporary local of the caller); + * the sequence "CAL ; ASP ; LFR" is removed. + */ + + + chg_actuals(c,cal); + *l_out = PREV(cal); /* last instr. of new parameter part */ + rm_callpart(c,cal); +} + + +/* make_label */ + +line_p make_label(l,p) + line_p l; + proc_p p; +{ + /* Make sure that the instruction after l + * contains an instruction label. If this is + * not already the case, create a new label. + */ + + line_p lab; + + if (l->l_next != (line_p) 0 && INSTR(l->l_next) == op_lab) { + return l->l_next; + } + lab = newline(OPINSTRLAB); + lab->l_instr = op_lab; + p->p_nrlabels++; + INSTRLAB(lab) = p->p_nrlabels; + appnd_line(lab,l); + return lab; +} + + + +/* modify */ + +STATIC act_info(off,acts,ab_off,act_out,off_out) + offset off, ab_off, *off_out; + actual_p acts, *act_out; +{ + /* Find the actual parameter that corresponds to + * the formal parameter with the given offset. + * Return it via act_out. If the actual is not + * an in-line actual, determine which temporary + * local is used for it; return the offset of that + * local via off_out. + */ + + offset sum = 0, tmp = 0; + actual_p act; + + for (act = acts; act != (actual_p) 0; act = act->ac_next) { + if (!act->ac_inl) { + tmp -= act->ac_size; + } + if (sum >= off) { + /* found */ + *act_out = act; + if (!act->ac_inl) { + *off_out = tmp + sum - off + ab_off; + } else { + assert (sum == off); + } + return; + } + sum += act->ac_size; + } + assert(FALSE); +} + + + +STATIC store_off(off,l) + offset off; + line_p l; +{ + if (TYPE(l) == OPSHORT) { + assert ((short) off == off); + SHORT(l) = (short) off; + } else { + OFFSET(l) = off; + } +} + + + +STATIC inl_actual(l,expr) + line_p l, expr; +{ + /* Expand an actual parameter in line. + * A LOL or LDL instruction is replaced + * by an expression. + * A SIL or LIL is replaced by the expression + * followed by a STI or LOI. + */ + + line_p e, lnp, s; + short instr; + + instr = INSTR(l); + assert(expr != (line_p) 0); + e = copy_expr(expr); /* make a copy of expr. */ + if (instr == op_sil || instr == op_lil) { + s = int_line((offset) ws); + s->l_instr = (instr == op_sil ? op_sti : op_loi); + appnd_line(s,last_line(e)); + } else { + assert(instr == op_lol || instr == op_ldl); + } + lnp = PREV(l); + rem_line(l); + app_list(e,lnp); +} + + + +STATIC localref(l,c,ab_off,lb_off) + line_p l; + call_p c; + offset ab_off, lb_off; +{ + /* Change a reference to a local variable or parameter + * of the called procedure. + */ + + offset off, tmpoff; + actual_p act; + + off = off_set(l); + if (off < 0) { + /* local variable, only the offset changes */ + store_off(lb_off + off,l); + } else { + act_info(off,c->cl_actuals,ab_off,&act,&tmpoff); /* find actual */ + if (act->ac_inl) { + /* inline actual parameter */ + inl_actual(l,act->ac_exp); + } else { + /* parameter stored in temporary local */ + store_off(tmpoff,l); + } + } +} + + + +STATIC chg_mes(l,c,ab_off,lb_off) + line_p l; + call_p c; + offset ab_off, lb_off; +{ + /* The register messages of the called procedure + * must be changed. If the message applies to a + * local variable or to a parameter that is not + * expanded in line, the offset of the variable + * is changed; else the entire message is deleted. + */ + + offset off, tmpoff; + actual_p act; + arg_p arg; + + arg = ARG(l); + switch ((int) arg->a_a.a_offset) { + case ms_reg: + if ((arg = arg->a_next) != (arg_p) 0) { + /* "mes 3" without further argument is not changed */ + off = arg->a_a.a_offset; + if (off < 0) { + /* local variable */ + arg->a_a.a_offset += lb_off; + } else { + act_info(off,c->cl_actuals,ab_off,&act,&tmpoff); + if (act->ac_inl) { + /* in line actual */ + rem_line(l); + } else { + arg->a_a.a_offset = tmpoff; + } + } + } + break; + case ms_par: + rem_line(l); + break; + } +} + + + +STATIC chg_ret(l,c,lab) + line_p l,lab; + call_p c; +{ + /* Change the RET instruction appearing in the + * expanded text of a call. If the called procedure + * falls through, the RET is just deleted; else it + * is replaced by a branch. + */ + + line_p lnp, bra; + + lnp = PREV(l); + rem_line(l); + if (!FALLTHROUGH(c->cl_proc)) { + bra = newline(OPINSTRLAB); + bra->l_instr = op_bra; + INSTRLAB(bra) = INSTRLAB(lab); + appnd_line(bra,lnp); + } +} + + + +STATIC mod_instr(l,c,lab,ab_off,lb_off,lab_off) + line_p l,lab; + call_p c; + offset ab_off,lb_off; + int lab_off; +{ + if (TYPE(l) == OPINSTRLAB) { + INSTRLAB(l) += lab_off; + } else { + switch(INSTR(l)) { + case op_stl: + case op_inl: + case op_del: + case op_zrl: + case op_sdl: + case op_lol: + case op_ldl: + case op_sil: + case op_lil: + case op_lal: + localref(l,c,ab_off,lb_off); + break; + case op_ret: + chg_ret(l,c,lab); + break; + case ps_pro: + case ps_end: + case ps_sym: + case ps_hol: + case ps_bss: + case ps_con: + case ps_rom: + rem_line(l); + break; + case ps_mes: + chg_mes(l,c,ab_off,lb_off); + break; + } + } +} + + +modify(text,c,lab,ab_off,lb_off,lab_off) + line_p text,lab; + call_p c; + offset ab_off,lb_off; + int lab_off; +{ + /* Modify the EM text of the called procedure. + * References to locals and parameters are + * changed; RETs are either deleted or replaced + * by a BRA to the given label; PRO and END pseudos + * are removed; instruction labels are changed, in + * order to make them different from any label used + * by the caller; some messages need to be changed too. + * Note that the first line of the text is a dummy instruction. + */ + + register line_p l; + line_p next; + + for (l = text->l_next; l != (line_p) 0; l = next) { + next = l->l_next; + /* This is rather tricky. An instruction like + * LOL 2 may be replaced by a number of instructions + * (if the parameter is expanded in line). This inserted + * code, however, should not be modified! + */ + mod_instr(l,c,lab,ab_off,lb_off,lab_off); + } +} + + + +mod_actuals(nc,c,lab,ab_off,lb_off,lab_off) + call_p nc,c; + line_p lab; + offset ab_off,lb_off; + int lab_off; +{ + actual_p act; + line_p l, next, dum; + + dum = newline(OPNO); + PREV(dum) = (line_p) 0; + for (act = nc->cl_actuals; act != (actual_p) 0; act = act->ac_next) { + l = act->ac_exp; + assert(l != (line_p) 0); + /* Insert a dummy instruction before l */ + dum->l_next = l; + PREV(l) = dum; + while(l != (line_p) 0) { + next = l->l_next; + mod_instr(l,c,lab,ab_off,lb_off,lab_off); + l = next; + } + act->ac_exp = dum->l_next; + PREV(dum->l_next) = (line_p) 0; + } + oldline(dum); +} + + + +/* insert */ + +STATIC line_p first_nonpseudo(l) + line_p l; +{ + /* Find the first non-pseudo instruction of + * a list of instructions. + */ + + while (l != (line_p) 0 && INSTR(l) >= sp_fpseu && + INSTR(l) <= ps_last) l = l->l_next; + return l; +} + + + +insert(text,l,firstline) + line_p text,l,firstline; +{ + /* Insert the modified EM text of the called + * routine in the calling routine. Pseudos are + * put after the pseudos of the caller; all + * normal instructions are put at the place + * where the CAL originally was. + */ + + line_p l1,l2,lastpseu; + + l1 = text->l_next; + oldline(text); /* remove dummy head instruction */ + if (l1 == (line_p) 0) return; /* no text at all! */ + l2 = first_nonpseudo(l1); + if (l2 == (line_p) 0) { + /* modified code consists only of pseudos */ + app_list(l1,PREV(first_nonpseudo(firstline))); + } else { + if (l1 == l2) { + /* no pseudos */ + app_list(l2,l); + } else { + lastpseu = PREV(first_nonpseudo(firstline)); + PREV(l2)->l_next = (line_p) 0; /* cut link */ + app_list(l2,l); /* insert normal instructions */ + app_list(l1,lastpseu); + } + } +} + + + +liquidate(p,text) + proc_p p; + line_p text; +{ + /* All calls to procedure p were expanded in line, so + * p is no longer needed. However, we must not throw away + * any data declarations appearing in p. + * The proctable entry of p is not removed, as we do not + * want to create holes in this table; however the PF_BODYSEEN + * flag is cleared, so p gets the same status as a procedure + * whose body is unmkown. + */ + + line_p l, nextl, lastkept = (line_p) 0; + call_p c, nextc; + + for (l = text; l != (line_p) 0; l = nextl) { + nextl = l->l_next; + switch(INSTR(l)) { + case ps_sym: + case ps_hol: + case ps_bss: + case ps_con: + case ps_rom: + lastkept = l; + break; + default: + rem_line(l); + } + } + if (lastkept != (line_p) 0) { + /* There were some data declarations in p, + * so we'll turn p into a data-unit; we'll + * have to append an end-pseudo for this + * purpose. + */ + lastkept->l_next = newline(OPNO); + lastkept->l_next->l_instr = (byte) ps_end; + } + /* There may be some calls in the body of p that + * ought to be expanded in line. As p is removed + * anyway, there is no use in really performing + * these substitutions, so the call-descriptors + * are just thrown away. + */ + + for (c = p->P_CALS; c != (call_p) 0; c = nextc) { + nextc = c->cl_cdr; + rem_call(c); + } + /* change the proctable entry */ + p->p_flags1 &= (byte) ~PF_BODYSEEN; + oldchange(p->p_change); + olduse(p->p_use); +} diff --git a/util/ego/il/il3_change.h b/util/ego/il/il3_change.h new file mode 100644 index 000000000..835249412 --- /dev/null +++ b/util/ego/il/il3_change.h @@ -0,0 +1,41 @@ +/* I N L I N E S U B S T I T U T I O N + * + * I L 3 _ C H A N G E . C + */ + + +extern chg_callseq(); /* (call_p c; line_p cal, *l_out) + * Change the calling sequence of + * the call c. The parameters are + * changed and the sequence + * CAL - ASP - LFR is removed. + * cal points to the CAL instruction + * l_out indicates where the expanded + * text of the called routine must + * be put. + */ +extern line_p make_label(); /* (line_p l; proc_p p) + * Make sure that the instruction after + * l contains a label. If this is not + * already the case, create a new label. + */ +extern modify(); /* (line_p text; call_p c; line_p lab; + * offset ab_off, lb_off; int lab_off) + * Modify the EM text of the called + * procedure. + */ +extern mod_actuals(); /* (call_p nc,c; line_p lab; + * offset ab_off, lb_off; int lab_off) + * Modify the actual parameters of the + * call nc the same way as the text of + * call c would be modified. + */ +extern insert(); /* (line_p text,l,firstline) + * Insert the modified EM text. + * Pseudos are put after the pseudos + * of the caller. + */ +extern liquidate(); /* (proc_p p; line_p text) + * All calls to p were expanded in line, + * so p is no longer needed. + */ diff --git a/util/ego/il/il3_subst.c b/util/ego/il/il3_subst.c new file mode 100644 index 000000000..29efd2008 --- /dev/null +++ b/util/ego/il/il3_subst.c @@ -0,0 +1,121 @@ +/* I N L I N E S U B S T I T U T I O N + * + * I L 3 _ S U B S T . C + */ + +#include +#include "../share/types.h" +#include "il.h" +#include "../share/debug.h" +#include "../share/alloc.h" +#include "../share/global.h" +#include "../share/lset.h" +#include "../share/get.h" +#include "../../../h/em_mnem.h" +#include "il3_aux.h" +#include "il3_change.h" +#include "il3_subst.h" + +STATIC line_p fetch_text(lf,c) + FILE *lf; + call_p c; +{ + /* Read the EM text of the called procedure. + * We use random access I/O here. + */ + + line_p l; + proc_p p; + lset savmes; + + savmes = mesregs; + mesregs = Lempty_set(); + fseek(lf,c->cl_proc->P_LADDR,0); + l = get_text(lf,&p); + assert (p == c->cl_proc); + Ldeleteset(mesregs); + mesregs = savmes; + return l; +} + + + + +line_p scan_to_cal(lines,n) + line_p lines; + short n; +{ + /* Find the n-th CAL instruction */ + + register line_p l; + + for (l = lines; l != (line_p) 0; l = l->l_next) { + if (INSTR(l) == op_cal) { + if (--n == 0) return l; + } + } + return (line_p) 0; /* CAL not found */ +} + + + +substitute(lf,c,cal,firstline) + FILE *lf; + call_p c; + line_p cal,firstline; +{ + /* Perform in line substitution of the call described + * by c. The EM text of the called routine is fetched + * and modified, the calling sequence is changed, + * the modified routine is put at the place of the call + * and all global information (proctable etc.) is kept + * up to date. + */ + + line_p l, text, lab; + offset ab_off, lb_off; + line_p startscan, ncal; + short lastcid; + call_p nc; + + Ssubst++; + ab_off = - curproc->p_localbytes; + /* offset of temporaries for parameters + * that are not expanded in line. + */ + chg_callseq(c,cal,&l); + /* Change the calling sequence; l points to the place + * where the expanded text must be put + */ + text = fetch_text(lf,c); /* fetch EM text of called routine */ + lb_off = - curproc->p_localbytes; + /* offset of temps. for locals of called proc. */ + curproc->p_localbytes += c->cl_proc->P_ORGLOCALS; + /* locals of called routine are put in stack frame of caller */ + if (!FALLTHROUGH(c->cl_proc)) { + /* The called proc contains one or more RETurns + * somewhere in the middle of its text; these + * should be changed into a jump to the end + * of the text. We create a label for this + * purpose (if there was no one already). + */ + lab = make_label(l,curproc); + } + modify(text,c,lab,ab_off,lb_off,curproc->p_nrlabels); + curproc->p_nrlabels += c->cl_proc->P_ORGLABELS; + insert(text,l,firstline); + /* insert text; instructions are put after l, pseudos + * are put at beginning of caller. + */ + /* Now take care of the nested calls */ + startscan = l->l_next; + lastcid = 0; + for (nc = c->cl_car; nc != (call_p) 0; nc = nc->cl_cdr) { + mod_actuals(nc,c,lab,ab_off,lb_off,curproc->p_nrlabels); + ncal = scan_to_cal(startscan,nc->cl_id - lastcid); + assert(ncal != (line_p) 0); + startscan = scan_to_cal(ncal->l_next,1); + lastcid = nc->cl_id; + substitute(lf,nc,ncal,firstline); + } +} diff --git a/util/ego/il/il3_subst.h b/util/ego/il/il3_subst.h new file mode 100644 index 000000000..d3e582f66 --- /dev/null +++ b/util/ego/il/il3_subst.h @@ -0,0 +1,17 @@ + +/* I N L I N E S U B S T I T U T I O N + * + * I L 3 _ S U B S T . H + */ + +extern line_p scan_to_cal(); /* (line_p lines; short n) + * Find the n-th cal instruction. + */ +extern substitute(); /* (FILE *lf;call_p c; line_ pcal,firstline) + * Perform in line substitution of the call described + * by c. The EM text of the called routine is fetched + * and modified, the calling sequence is changed, + * the modified routine is put at the place of the call + * and all global information (proctable etc.) is kept + * up to date. + */ diff --git a/util/ego/il/il_aux.c b/util/ego/il/il_aux.c new file mode 100644 index 000000000..04fd488c6 --- /dev/null +++ b/util/ego/il/il_aux.c @@ -0,0 +1,182 @@ + +/* I N L I N E S U B S T I T U T I O N + * + * I L _ A U X . C + */ + +#include "../share/types.h" +#include "il.h" +#include "../share/debug.h" +#include "../share/alloc.h" +#include "../share/global.h" +#include "../share/lset.h" +#include "../share/map.h" +#include "../../../h/em_spec.h" +#include "il_aux.h" + + +int tsize(type) + int type; +{ + /* Determine the size of a variable of the + * given type. + */ + + switch(type) { + case SINGLE: return ws; + case DOUBLE: return 2*ws; + case POINTER: return ps; + default: assert(FALSE); + } + /* NOTREACHED */ +} + + + +line_p duplicate(lnp) + line_p lnp; +{ + /* Make a duplicate of an EM instruction. + * Pseudos may not be passed as argument. + */ + + line_p l; + + l = newline(TYPE(lnp)); + l->l_instr = INSTR(lnp); + switch(TYPE(l)) { + case OPNO: + break; + case OPSHORT: + SHORT(l) = SHORT(lnp); + break; + case OPOFFSET: + OFFSET(l) = OFFSET(lnp); + break; + case OPINSTRLAB: + INSTRLAB(l) = INSTRLAB(lnp); + break; + case OPOBJECT: + OBJ(l) = OBJ(lnp); + break; + case OPPROC: + PROC(l) = PROC(lnp); + break; + default: + assert(FALSE); /* cannot copy pseudo */ + } + return l; +} + + + + +line_p copy_expr(l1) + line_p l1; +{ + /* copy the expression */ + + line_p head, tail, l, lnp; + + head = (line_p) 0; + for (lnp = l1; lnp != (line_p) 0; lnp = lnp->l_next) { + l = duplicate(lnp); + if (head == (line_p) 0) { + head = tail = l; + PREV(l) = (line_p) 0; + } else { + tail->l_next = l; + PREV(l) = tail; + tail = l; + } + } + return head; +} + + + +rem_call(c) + call_p c; +{ + actual_p act, nexta; + call_p nc,nextc; + line_p l, nextl; + + for (act = c->cl_actuals; act != (actual_p) 0; act = nexta) { + nexta = act->ac_next; + for (l = act->ac_exp; l != (line_p) 0; l = nextl) { + nextl = l->l_next; + oldline(l); + } + oldactual(act); + } + nc = c->cl_car; + oldcall(c); + for (; nc != (call_p) 0; nc = nextc) { + /* Take care of nested calls */ + nextc = nc->cl_cdr; + rem_call(nc); + } +} + + + +/* rem_graph */ + +STATIC short remlines(l) + line_p l; +{ + + register line_p lnp; + line_p next; + + for (lnp = l; lnp != (line_p) 0; lnp = next) { + next = lnp->l_next; + oldline(lnp); + } +} + + + +remunit(kind,p,l) + short kind; + proc_p p; + line_p l; +{ + register bblock_p b; + bblock_p next; + Lindex pi; + loop_p lp; + + if (kind == LDATA) { + remlines(l); + return; + } + for (b = p->p_start; b != (bblock_p) 0; b = next) { + next = b->b_next; + remlines(b->b_start); + Ldeleteset(b->b_loops); + Ldeleteset(b->b_succ); + Ldeleteset(b->b_pred); + oldbblock(b); + } + for (pi = Lfirst(p->p_loops); pi != (Lindex) 0; + pi = Lnext(pi,p->p_loops)) { + oldloop(Lelem(pi)); + } + Ldeleteset(p->p_loops); + oldmap(lmap,llength); + oldmap(lbmap,llength); + oldmap(bmap,blength); + oldmap(lpmap,lplength); +} +remcc(head) + calcnt_p head; +{ + calcnt_p cc, next; + + for (cc = head; cc != (calcnt_p) 0; cc = next) { + next = cc->cc_next; + oldcalcnt(cc); + } +} diff --git a/util/ego/il/il_aux.h b/util/ego/il/il_aux.h new file mode 100644 index 000000000..2b673b226 --- /dev/null +++ b/util/ego/il/il_aux.h @@ -0,0 +1,30 @@ + +/* I N L I N E S U B S T I T U T I O N + * + * I L _ A U X . H + */ + +extern int tsize(); /* (int type) + * Determine the size of a variable of + * the given type. + */ +extern line_p duplicate(); /* (line_p lnp) + * Make a duplicate of the given EM + * instruction. Pseudos may not be + * passed as argumnets. + */ +extern line_p copy_expr(); /* (line_p l1) + * copy the expression l1. + * Pseudos may not be contained in + * the list of instructions. + */ +extern rem_call(); /* (call_p c) + * Remove a call from main memory. + */ +extern rem_graph(); /* (proc_p p) + * Remove the CFG and EM text of + * a procedure from core. + */ +extern remcc(); /* (calcnt_p head) + * Remove call-count info from core. + */ -- 2.34.1