123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759 |
- #include "gc.h"
- static int
- needc(Prog *p)
- {
- while(p != P) {
- switch(p->as) {
- case AADCL:
- case ASBBL:
- case ARCRL:
- return 1;
- case AADDL:
- case ASUBL:
- case AJMP:
- case ARET:
- case ACALL:
- return 0;
- default:
- if(p->to.type == D_BRANCH)
- return 0;
- }
- p = p->link;
- }
- return 0;
- }
- void
- peep(void)
- {
- Reg *r, *r1, *r2;
- Prog *p, *p1;
- int t;
- /*
- * complete R structure
- */
- t = 0;
- for(r=firstr; r!=R; r=r1) {
- r1 = r->link;
- if(r1 == R)
- break;
- p = r->prog->link;
- while(p != r1->prog)
- switch(p->as) {
- default:
- r2 = rega();
- r->link = r2;
- r2->link = r1;
- r2->prog = p;
- r2->p1 = r;
- r->s1 = r2;
- r2->s1 = r1;
- r1->p1 = r2;
- r = r2;
- t++;
- case ADATA:
- case AGLOBL:
- case ANAME:
- case ASIGNAME:
- p = p->link;
- }
- }
- pc = 0; /* speculating it won't kill */
- loop1:
- if(debug['b'])
- comtarg();
- t = 0;
- for(r=firstr; r!=R; r=r->link) {
- p = r->prog;
- switch(p->as) {
- case AMOVL:
- if(regtyp(&p->to))
- if(regtyp(&p->from)) {
- if(copyprop(r)) {
- excise(r);
- t++;
- }
- if(subprop(r) && copyprop(r)) {
- excise(r);
- t++;
- }
- }
- break;
- case AMOVBLSX:
- case AMOVBLZX:
- case AMOVWLSX:
- case AMOVWLZX:
- if(regtyp(&p->to)) {
- r1 = uniqs(r);
- if(r1 != R) {
- p1 = r1->prog;
- if(p->as == p1->as && p->to.type == p1->from.type)
- p1->as = AMOVL;
- }
- }
- break;
- case AADDL:
- case AADDW:
- if(p->from.type != D_CONST || needc(p->link))
- break;
- if(p->from.offset == -1){
- if(p->as == AADDL)
- p->as = ADECL;
- else
- p->as = ADECW;
- p->from = zprog.from;
- }
- else if(p->from.offset == 1){
- if(p->as == AADDL)
- p->as = AINCL;
- else
- p->as = AINCW;
- p->from = zprog.from;
- }
- break;
- case ASUBL:
- case ASUBW:
- if(p->from.type != D_CONST || needc(p->link))
- break;
- if(p->from.offset == -1) {
- if(p->as == ASUBL)
- p->as = AINCL;
- else
- p->as = AINCW;
- p->from = zprog.from;
- }
- else if(p->from.offset == 1){
- if(p->as == ASUBL)
- p->as = ADECL;
- else
- p->as = ADECW;
- p->from = zprog.from;
- }
- break;
- }
- }
- if(t)
- goto loop1;
- }
- void
- excise(Reg *r)
- {
- Prog *p;
- p = r->prog;
- p->as = ANOP;
- p->from = zprog.from;
- p->to = zprog.to;
- }
- Reg*
- uniqp(Reg *r)
- {
- Reg *r1;
- r1 = r->p1;
- if(r1 == R) {
- r1 = r->p2;
- if(r1 == R || r1->p2link != R)
- return R;
- } else
- if(r->p2 != R)
- return R;
- return r1;
- }
- Reg*
- uniqs(Reg *r)
- {
- Reg *r1;
- r1 = r->s1;
- if(r1 == R) {
- r1 = r->s2;
- if(r1 == R)
- return R;
- } else
- if(r->s2 != R)
- return R;
- return r1;
- }
- int
- regtyp(Adr *a)
- {
- int t;
- t = a->type;
- if(t >= D_AX && t <= D_DI)
- return 1;
- return 0;
- }
- /*
- * the idea is to substitute
- * one register for another
- * from one MOV to another
- * MOV a, R0
- * ADD b, R0 / no use of R1
- * MOV R0, R1
- * would be converted to
- * MOV a, R1
- * ADD b, R1
- * MOV R1, R0
- * hopefully, then the former or latter MOV
- * will be eliminated by copy propagation.
- */
- int
- subprop(Reg *r0)
- {
- Prog *p;
- Adr *v1, *v2;
- Reg *r;
- int t;
- p = r0->prog;
- v1 = &p->from;
- if(!regtyp(v1))
- return 0;
- v2 = &p->to;
- if(!regtyp(v2))
- return 0;
- for(r=uniqp(r0); r!=R; r=uniqp(r)) {
- if(uniqs(r) == R)
- break;
- p = r->prog;
- switch(p->as) {
- case ACALL:
- return 0;
- case AIMULL:
- case AIMULW:
- if(p->to.type != D_NONE)
- break;
- case ADIVB:
- case ADIVL:
- case ADIVW:
- case AIDIVB:
- case AIDIVL:
- case AIDIVW:
- case AIMULB:
- case AMULB:
- case AMULL:
- case AMULW:
- case AROLB:
- case AROLL:
- case AROLW:
- case ARORB:
- case ARORL:
- case ARORW:
- case ASALB:
- case ASALL:
- case ASALW:
- case ASARB:
- case ASARL:
- case ASARW:
- case ASHLB:
- case ASHLL:
- case ASHLW:
- case ASHRB:
- case ASHRL:
- case ASHRW:
- case AREP:
- case AREPN:
- case ACWD:
- case ACDQ:
- case AMOVSL:
- case AFSTSW:
- return 0;
- case AMOVL:
- if(p->to.type == v1->type)
- goto gotit;
- break;
- }
- if(copyau(&p->from, v2) ||
- copyau(&p->to, v2))
- break;
- if(copysub(&p->from, v1, v2, 0) ||
- copysub(&p->to, v1, v2, 0))
- break;
- }
- return 0;
- gotit:
- copysub(&p->to, v1, v2, 1);
- if(debug['P']) {
- print("gotit: %D->%D\n%P", v1, v2, r->prog);
- if(p->from.type == v2->type)
- print(" excise");
- print("\n");
- }
- for(r=uniqs(r); r!=r0; r=uniqs(r)) {
- p = r->prog;
- copysub(&p->from, v1, v2, 1);
- copysub(&p->to, v1, v2, 1);
- if(debug['P'])
- print("%P\n", r->prog);
- }
- t = v1->type;
- v1->type = v2->type;
- v2->type = t;
- if(debug['P'])
- print("%P last\n", r->prog);
- return 1;
- }
- /*
- * The idea is to remove redundant copies.
- * v1->v2 F=0
- * (use v2 s/v2/v1/)*
- * set v1 F=1
- * use v2 return fail
- * -----------------
- * v1->v2 F=0
- * (use v2 s/v2/v1/)*
- * set v1 F=1
- * set v2 return success
- */
- int
- copyprop(Reg *r0)
- {
- Prog *p;
- Adr *v1, *v2;
- Reg *r;
- p = r0->prog;
- v1 = &p->from;
- v2 = &p->to;
- if(copyas(v1, v2))
- return 1;
- for(r=firstr; r!=R; r=r->link)
- r->active = 0;
- return copy1(v1, v2, r0->s1, 0);
- }
- int
- copy1(Adr *v1, Adr *v2, Reg *r, int f)
- {
- int t;
- Prog *p;
- if(r->active) {
- if(debug['P'])
- print("act set; return 1\n");
- return 1;
- }
- r->active = 1;
- if(debug['P'])
- print("copy %D->%D f=%d\n", v1, v2, f);
- for(; r != R; r = r->s1) {
- p = r->prog;
- if(debug['P'])
- print("%P", p);
- if(!f && uniqp(r) == R) {
- f = 1;
- if(debug['P'])
- print("; merge; f=%d", f);
- }
- t = copyu(p, v2, A);
- switch(t) {
- case 2: /* rar, cant split */
- if(debug['P'])
- print("; %D rar; return 0\n", v2);
- return 0;
- case 3: /* set */
- if(debug['P'])
- print("; %D set; return 1\n", v2);
- return 1;
- case 1: /* used, substitute */
- case 4: /* use and set */
- if(f) {
- if(!debug['P'])
- return 0;
- if(t == 4)
- print("; %D used+set and f=%d; return 0\n", v2, f);
- else
- print("; %D used and f=%d; return 0\n", v2, f);
- return 0;
- }
- if(copyu(p, v2, v1)) {
- if(debug['P'])
- print("; sub fail; return 0\n");
- return 0;
- }
- if(debug['P'])
- print("; sub %D/%D", v2, v1);
- if(t == 4) {
- if(debug['P'])
- print("; %D used+set; return 1\n", v2);
- return 1;
- }
- break;
- }
- if(!f) {
- t = copyu(p, v1, A);
- if(!f && (t == 2 || t == 3 || t == 4)) {
- f = 1;
- if(debug['P'])
- print("; %D set and !f; f=%d", v1, f);
- }
- }
- if(debug['P'])
- print("\n");
- if(r->s2)
- if(!copy1(v1, v2, r->s2, f))
- return 0;
- }
- return 1;
- }
- /*
- * return
- * 1 if v only used (and substitute),
- * 2 if read-alter-rewrite
- * 3 if set
- * 4 if set and used
- * 0 otherwise (not touched)
- */
- int
- copyu(Prog *p, Adr *v, Adr *s)
- {
- switch(p->as) {
- default:
- if(debug['P'])
- print("unknown op %A\n", p->as);
- return 2;
- case ANEGB:
- case ANEGW:
- case ANEGL:
- case ANOTB:
- case ANOTW:
- case ANOTL:
- if(copyas(&p->to, v))
- return 2;
- break;
- case ALEAL: /* lhs addr, rhs store */
- if(copyas(&p->from, v))
- return 2;
- case ANOP: /* rhs store */
- case AMOVL:
- case AMOVBLSX:
- case AMOVBLZX:
- case AMOVWLSX:
- case AMOVWLZX:
- if(copyas(&p->to, v)) {
- if(s != A)
- return copysub(&p->from, v, s, 1);
- if(copyau(&p->from, v))
- return 4;
- return 3;
- }
- goto caseread;
- case AROLB:
- case AROLL:
- case AROLW:
- case ARORB:
- case ARORL:
- case ARORW:
- case ASALB:
- case ASALL:
- case ASALW:
- case ASARB:
- case ASARL:
- case ASARW:
- case ASHLB:
- case ASHLL:
- case ASHLW:
- case ASHRB:
- case ASHRL:
- case ASHRW:
- if(copyas(&p->to, v))
- return 2;
- if(copyas(&p->from, v))
- if(p->from.type == D_CX)
- return 2;
- goto caseread;
- case AADDB: /* rhs rar */
- case AADDL:
- case AADDW:
- case AANDB:
- case AANDL:
- case AANDW:
- case ADECL:
- case ADECW:
- case AINCL:
- case AINCW:
- case ASUBB:
- case ASUBL:
- case ASUBW:
- case AORB:
- case AORL:
- case AORW:
- case AXORB:
- case AXORL:
- case AXORW:
- case AMOVB:
- case AMOVW:
- case AFMOVB:
- case AFMOVBP:
- case AFMOVD:
- case AFMOVDP:
- case AFMOVF:
- case AFMOVFP:
- case AFMOVL:
- case AFMOVLP:
- case AFMOVV:
- case AFMOVVP:
- case AFMOVW:
- case AFMOVWP:
- case AFMOVX:
- case AFMOVXP:
- case AFADDDP:
- case AFADDW:
- case AFADDL:
- case AFADDF:
- case AFADDD:
- case AFMULDP:
- case AFMULW:
- case AFMULL:
- case AFMULF:
- case AFMULD:
- case AFSUBDP:
- case AFSUBW:
- case AFSUBL:
- case AFSUBF:
- case AFSUBD:
- case AFSUBRDP:
- case AFSUBRW:
- case AFSUBRL:
- case AFSUBRF:
- case AFSUBRD:
- case AFDIVDP:
- case AFDIVW:
- case AFDIVL:
- case AFDIVF:
- case AFDIVD:
- case AFDIVRDP:
- case AFDIVRW:
- case AFDIVRL:
- case AFDIVRF:
- case AFDIVRD:
- if(copyas(&p->to, v))
- return 2;
- goto caseread;
- case ACMPL: /* read only */
- case ACMPW:
- case ACMPB:
- case AFCOMB:
- case AFCOMBP:
- case AFCOMD:
- case AFCOMDP:
- case AFCOMDPP:
- case AFCOMF:
- case AFCOMFP:
- case AFCOML:
- case AFCOMLP:
- case AFCOMW:
- case AFCOMWP:
- case AFUCOM:
- case AFUCOMP:
- case AFUCOMPP:
- caseread:
- if(s != A) {
- if(copysub(&p->from, v, s, 1))
- return 1;
- return copysub(&p->to, v, s, 1);
- }
- if(copyau(&p->from, v))
- return 1;
- if(copyau(&p->to, v))
- return 1;
- break;
- case AJGE: /* no reference */
- case AJNE:
- case AJLE:
- case AJEQ:
- case AJHI:
- case AJLS:
- case AJMI:
- case AJPL:
- case AJGT:
- case AJLT:
- case AJCC:
- case AJCS:
- case AADJSP:
- case AFLDZ:
- case AWAIT:
- break;
- case AIMULL:
- case AIMULW:
- if(p->to.type != D_NONE) {
- if(copyas(&p->to, v))
- return 2;
- goto caseread;
- }
- case ADIVB:
- case ADIVL:
- case ADIVW:
- case AIDIVB:
- case AIDIVL:
- case AIDIVW:
- case AIMULB:
- case AMULB:
- case AMULL:
- case AMULW:
- case ACWD:
- case ACDQ:
- if(v->type == D_AX || v->type == D_DX)
- return 2;
- goto caseread;
- case AMOVSL:
- case AREP:
- case AREPN:
- if(v->type == D_CX || v->type == D_DI || v->type == D_SI)
- return 2;
- goto caseread;
- case AFSTSW:
- if(v->type == D_AX)
- return 2;
- goto caseread;
- case AJMP: /* funny */
- if(s != A) {
- if(copysub(&p->to, v, s, 1))
- return 1;
- return 0;
- }
- if(copyau(&p->to, v))
- return 1;
- return 0;
- case ARET: /* funny */
- if(v->type == REGRET)
- return 2;
- if(s != A)
- return 1;
- return 3;
- case ACALL: /* funny */
- if(REGARG>=0 && v->type == REGARG)
- return 2;
- if(s != A) {
- if(copysub(&p->to, v, s, 1))
- return 1;
- return 0;
- }
- if(copyau(&p->to, v))
- return 4;
- return 3;
- }
- return 0;
- }
- /*
- * direct reference,
- * could be set/use depending on
- * semantics
- */
- int
- copyas(Adr *a, Adr *v)
- {
- if(a->type != v->type)
- return 0;
- if(regtyp(v))
- return 1;
- if(v->type == D_AUTO || v->type == D_PARAM)
- if(v->offset == a->offset)
- return 1;
- return 0;
- }
- /*
- * either direct or indirect
- */
- int
- copyau(Adr *a, Adr *v)
- {
- if(copyas(a, v))
- return 1;
- if(regtyp(v)) {
- if(a->type-D_INDIR == v->type)
- return 1;
- if(a->index == v->type)
- return 1;
- }
- return 0;
- }
- /*
- * substitute s for v in a
- * return failure to substitute
- */
- int
- copysub(Adr *a, Adr *v, Adr *s, int f)
- {
- int t;
- if(copyas(a, v)) {
- t = s->type;
- if(t >= D_AX && t <= D_DI) {
- if(f)
- a->type = t;
- }
- return 0;
- }
- if(regtyp(v)) {
- t = v->type;
- if(a->type == t+D_INDIR) {
- if(s->type == D_BP && a->index != D_NONE)
- return 1; /* can't use BP-base with index */
- if(f)
- a->type = s->type+D_INDIR;
- // return 0;
- }
- if(a->index == t) {
- if(f)
- a->index = s->type;
- return 0;
- }
- return 0;
- }
- return 0;
- }
|