123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891 |
- #include "gc.h"
- 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;
- }
- }
- loop1:
- t = 0;
- for(r=firstr; r!=R; r=r->link) {
- p = r->prog;
- if(p->as == AMOVW || p->as == AFMOVS || p->as == AFMOVD)
- if(regtyp(&p->to)) {
- if(regtyp(&p->from))
- if(p->from.type == p->to.type) {
- if(copyprop(r)) {
- excise(r);
- t++;
- } else
- if(subprop(r) && copyprop(r)) {
- excise(r);
- t++;
- }
- }
- if(regzer(&p->from))
- if(p->to.type == D_REG) {
- p->from.type = D_REG;
- p->from.reg = REGZERO;
- if(copyprop(r)) {
- excise(r);
- t++;
- } else
- if(subprop(r) && copyprop(r)) {
- excise(r);
- t++;
- }
- }
- }
- }
- if(t)
- goto loop1;
- /*
- * look for MOVB x,R; MOVB R,R
- */
- for(r=firstr; r!=R; r=r->link) {
- p = r->prog;
- switch(p->as) {
- default:
- continue;
- case AMOVH:
- case AMOVHZ:
- case AMOVB:
- case AMOVBZ:
- if(p->to.type != D_REG)
- continue;
- break;
- }
- r1 = r->link;
- if(r1 == R)
- continue;
- p1 = r1->prog;
- if(p1->as != p->as)
- continue;
- if(p1->from.type != D_REG || p1->from.reg != p->to.reg)
- continue;
- if(p1->to.type != D_REG || p1->to.reg != p->to.reg)
- continue;
- excise(r1);
- }
- if(debug['Q'] > 1)
- return; /* allow following code improvement to be suppressed */
- /*
- * look for OP x,y,R; CMP R, $0 -> OPCC x,y,R
- * when OP can set condition codes correctly
- */
- for(r=firstr; r!=R; r=r->link) {
- p = r->prog;
- switch(p->as) {
- case ACMP:
- if(!regzer(&p->to))
- continue;
- r1 = r->s1;
- if(r1 == R)
- continue;
- switch(r1->prog->as) {
- default:
- continue;
- case ABCL:
- case ABC:
- /* the conditions can be complex and these are currently little used */
- continue;
- case ABEQ:
- case ABGE:
- case ABGT:
- case ABLE:
- case ABLT:
- case ABNE:
- case ABVC:
- case ABVS:
- break;
- }
- r1 = r;
- do
- r1 = uniqp(r1);
- while (r1 != R && r1->prog->as == ANOP);
- if(r1 == R)
- continue;
- p1 = r1->prog;
- if(p1->to.type != D_REG || p1->to.reg != p->from.reg)
- continue;
- switch(p1->as) {
- case ASUB:
- case AADD:
- case AXOR:
- case AOR:
- /* irregular instructions */
- if(p1->from.type == D_CONST)
- continue;
- break;
- }
- switch(p1->as) {
- default:
- continue;
- case AMOVW:
- if(p1->from.type != D_REG)
- continue;
- continue;
- case AANDCC:
- case AANDNCC:
- case AORCC:
- case AORNCC:
- case AXORCC:
- case ASUBCC:
- case AADDCC:
- t = p1->as;
- break;
- /* don't deal with floating point instructions for now */
- /*
- case AFABS: t = AFABSCC; break;
- case AFADD: t = AFADDCC; break;
- case AFADDS: t = AFADDSCC; break;
- case AFCTIW: t = AFCTIWCC; break;
- case AFCTIWZ: t = AFCTIWZCC; break;
- case AFDIV: t = AFDIVCC; break;
- case AFDIVS: t = AFDIVSCC; break;
- case AFMADD: t = AFMADDCC; break;
- case AFMADDS: t = AFMADDSCC; break;
- case AFMOVD: t = AFMOVDCC; break;
- case AFMSUB: t = AFMSUBCC; break;
- case AFMSUBS: t = AFMSUBSCC; break;
- case AFMUL: t = AFMULCC; break;
- case AFMULS: t = AFMULSCC; break;
- case AFNABS: t = AFNABSCC; break;
- case AFNEG: t = AFNEGCC; break;
- case AFNMADD: t = AFNMADDCC; break;
- case AFNMADDS: t = AFNMADDSCC; break;
- case AFNMSUB: t = AFNMSUBCC; break;
- case AFNMSUBS: t = AFNMSUBSCC; break;
- case AFRSP: t = AFRSPCC; break;
- case AFSUB: t = AFSUBCC; break;
- case AFSUBS: t = AFSUBSCC; break;
- case ACNTLZW: t = ACNTLZWCC; break;
- case AMTFSB0: t = AMTFSB0CC; break;
- case AMTFSB1: t = AMTFSB1CC; break;
- */
- case AADD: t = AADDCC; break;
- case AADDV: t = AADDVCC; break;
- case AADDC: t = AADDCCC; break;
- case AADDCV: t = AADDCVCC; break;
- case AADDME: t = AADDMECC; break;
- case AADDMEV: t = AADDMEVCC; break;
- case AADDE: t = AADDECC; break;
- case AADDEV: t = AADDEVCC; break;
- case AADDZE: t = AADDZECC; break;
- case AADDZEV: t = AADDZEVCC; break;
- case AAND: t = AANDCC; break;
- case AANDN: t = AANDNCC; break;
- case ADIVW: t = ADIVWCC; break;
- case ADIVWV: t = ADIVWVCC; break;
- case ADIVWU: t = ADIVWUCC; break;
- case ADIVWUV: t = ADIVWUVCC; break;
- case AEQV: t = AEQVCC; break;
- case AEXTSB: t = AEXTSBCC; break;
- case AEXTSH: t = AEXTSHCC; break;
- case AMULHW: t = AMULHWCC; break;
- case AMULHWU: t = AMULHWUCC; break;
- case AMULLW: t = AMULLWCC; break;
- case AMULLWV: t = AMULLWVCC; break;
- case ANAND: t = ANANDCC; break;
- case ANEG: t = ANEGCC; break;
- case ANEGV: t = ANEGVCC; break;
- case ANOR: t = ANORCC; break;
- case AOR: t = AORCC; break;
- case AORN: t = AORNCC; break;
- case AREM: t = AREMCC; break;
- case AREMV: t = AREMVCC; break;
- case AREMU: t = AREMUCC; break;
- case AREMUV: t = AREMUVCC; break;
- case ARLWMI: t = ARLWMICC; break;
- case ARLWNM: t = ARLWNMCC; break;
- case ASLW: t = ASLWCC; break;
- case ASRAW: t = ASRAWCC; break;
- case ASRW: t = ASRWCC; break;
- case ASUB: t = ASUBCC; break;
- case ASUBV: t = ASUBVCC; break;
- case ASUBC: t = ASUBCCC; break;
- case ASUBCV: t = ASUBCVCC; break;
- case ASUBME: t = ASUBMECC; break;
- case ASUBMEV: t = ASUBMEVCC; break;
- case ASUBE: t = ASUBECC; break;
- case ASUBEV: t = ASUBEVCC; break;
- case ASUBZE: t = ASUBZECC; break;
- case ASUBZEV: t = ASUBZEVCC; break;
- case AXOR: t = AXORCC; break;
- break;
- }
- if(debug['Q'])
- print("cmp %P; %P -> ", p1, p);
- p1->as = t;
- if(debug['Q'])
- print("%P\n", p1);
- excise(r);
- continue;
- }
- }
- }
- void
- excise(Reg *r)
- {
- Prog *p;
- p = r->prog;
- p->as = ANOP;
- p->from = zprog.from;
- p->to = zprog.to;
- p->reg = zprog.reg; /**/
- }
- 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;
- }
- /*
- * if the system forces R0 to be zero,
- * convert references to $0 to references to R0.
- */
- regzer(Adr *a)
- {
- if(R0ISZERO) {
- if(a->type == D_CONST)
- if(a->sym == S)
- if(a->offset == 0)
- return 1;
- if(a->type == D_REG)
- if(a->reg == REGZERO)
- return 1;
- }
- return 0;
- }
- regtyp(Adr *a)
- {
- if(a->type == D_REG) {
- if(!R0ISZERO || a->reg != REGZERO)
- return 1;
- return 0;
- }
- if(a->type == D_FREG)
- 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 ABL:
- return 0;
- case AADD:
- case ASUB:
- case ASLW:
- case ASRW:
- case ASRAW:
- case AOR:
- case AORCC:
- case AORN:
- case AORNCC:
- case AAND:
- case AANDCC:
- case AANDN:
- case AANDNCC:
- case ANAND:
- case ANANDCC:
- case ANOR:
- case ANORCC:
- case AXOR:
- case AXORCC:
- case AMULLW:
- case ADIVW:
- case ADIVWU:
- case AREM:
- case AREMU:
- case ANEG:
- case ANEGCC:
- case AFADD:
- case AFADDS:
- case AFSUB:
- case AFSUBS:
- case AFMUL:
- case AFMULS:
- case AFDIV:
- case AFDIVS:
- case AFNEG:
- case AFNEGCC:
- if(p->to.type == v1->type)
- if(p->to.reg == v1->reg) {
- if(p->reg == NREG)
- p->reg = p->to.reg;
- goto gotit;
- }
- break;
- case AFMOVS:
- case AFMOVD:
- case AMOVW:
- if(p->to.type == v1->type)
- if(p->to.reg == v1->reg)
- goto gotit;
- break;
- }
- if(copyau(&p->from, v2) ||
- copyau1(p, v2) ||
- copyau(&p->to, v2))
- break;
- if(copysub(&p->from, v1, v2, 0) ||
- copysub1(p, 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);
- copysub1(p, v1, v2, 1);
- copysub(&p->to, v1, v2, 1);
- if(debug['P'])
- print("%P\n", r->prog);
- }
- t = v1->reg;
- v1->reg = v2->reg;
- v2->reg = 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);
- }
- 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("; %Drar; return 0\n", v2);
- return 0;
- case 3: /* set */
- if(debug['P'])
- print("; %Dset; 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("; %Dused+set and f=%d; return 0\n", v2, f);
- else
- print("; %Dused 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("; %Dused+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("; %Dset 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(" (???)");
- return 2;
- case ANOP: /* read, write */
- case AMOVW:
- case AMOVH:
- case AMOVHZ:
- case AMOVB:
- case AMOVBZ:
- case ANEG:
- case ANEGCC:
- case AFCTIW:
- case AFCTIWZ:
- case AFMOVS:
- case AFMOVD:
- case AFRSP:
- case AFNEG:
- case AFNEGCC:
- if(s != A) {
- if(copysub(&p->from, v, s, 1))
- return 1;
- if(!copyas(&p->to, v))
- if(copysub(&p->to, v, s, 1))
- return 1;
- return 0;
- }
- if(copyas(&p->to, v)) {
- if(copyau(&p->from, v))
- return 4;
- return 3;
- }
- if(copyau(&p->from, v))
- return 1;
- if(copyau(&p->to, v))
- return 1;
- return 0;
- case AADD: /* read read write */
- case ASUB:
- case ASLW:
- case ASRW:
- case ASRAW:
- case AOR:
- case AORCC:
- case AORN:
- case AORNCC:
- case AAND:
- case AANDCC:
- case AANDN:
- case AANDNCC:
- case ANAND:
- case ANANDCC:
- case ANOR:
- case ANORCC:
- case AXOR:
- case AMULLW:
- case ADIVW:
- case ADIVWU:
- case AREM:
- case AREMU:
- case AFADDS:
- case AFADD:
- case AFSUBS:
- case AFSUB:
- case AFMULS:
- case AFMUL:
- case AFDIVS:
- case AFDIV:
- if(s != A) {
- if(copysub(&p->from, v, s, 1))
- return 1;
- if(copysub1(p, v, s, 1))
- return 1;
- if(!copyas(&p->to, v))
- if(copysub(&p->to, v, s, 1))
- return 1;
- return 0;
- }
- if(copyas(&p->to, v)) {
- if(p->reg == NREG)
- p->reg = p->to.reg;
- if(copyau(&p->from, v))
- return 4;
- if(copyau1(p, v))
- return 4;
- return 3;
- }
- if(copyau(&p->from, v))
- return 1;
- if(copyau1(p, v))
- return 1;
- if(copyau(&p->to, v))
- return 1;
- return 0;
- case ABEQ:
- case ABGT:
- case ABGE:
- case ABLT:
- case ABLE:
- case ABNE:
- case ABVC:
- case ABVS:
- break;
- case ACMP: /* read read */
- case ACMPU:
- case AFCMPO:
- case AFCMPU:
- 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 ABR: /* 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 ARETURN: /* funny */
- if(v->type == D_REG)
- if(v->reg == REGRET)
- return 2;
- if(v->type == D_FREG)
- if(v->reg == FREGRET)
- return 2;
- case ABL: /* funny */
- if(v->type == D_REG) {
- if(v->reg <= REGEXT && v->reg > exregoffset)
- return 2;
- if(v->reg == REGARG)
- return 2;
- }
- if(v->type == D_FREG) {
- if(v->reg <= FREGEXT && v->reg > exfregoffset)
- 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;
- case ATEXT: /* funny */
- if(v->type == D_REG)
- if(v->reg == REGARG)
- return 3;
- return 0;
- }
- return 0;
- }
- int
- a2type(Prog *p)
- {
- switch(p->as) {
- case AADD:
- case AADDCC:
- case ASUB:
- case ASUBCC:
- case ASLW:
- case ASLWCC:
- case ASRW:
- case ASRWCC:
- case ASRAW:
- case ASRAWCC:
- case AOR:
- case AORCC:
- case AORN:
- case AORNCC:
- case AAND:
- case AANDCC:
- case AANDN:
- case AANDNCC:
- case AXOR:
- case AXORCC:
- case ANEG:
- case ANEGCC:
- case AMULLW:
- case AMULLWCC:
- case ADIVW:
- case ADIVWCC:
- case ADIVWU:
- case ADIVWUCC:
- case AREM:
- case AREMCC:
- case AREMU:
- case AREMUCC:
- case ANAND:
- case ANANDCC:
- case ANOR:
- case ANORCC:
- return D_REG;
- case AFADDS:
- case AFADDSCC:
- case AFADD:
- case AFADDCC:
- case AFSUBS:
- case AFSUBSCC:
- case AFSUB:
- case AFSUBCC:
- case AFMULS:
- case AFMULSCC:
- case AFMUL:
- case AFMULCC:
- case AFDIVS:
- case AFDIVSCC:
- case AFDIV:
- case AFDIVCC:
- case AFNEG:
- case AFNEGCC:
- return D_FREG;
- }
- return D_NONE;
- }
- /*
- * direct reference,
- * could be set/use depending on
- * semantics
- */
- int
- copyas(Adr *a, Adr *v)
- {
- if(regtyp(v))
- if(a->type == v->type)
- if(a->reg == v->reg)
- return 1;
- return 0;
- }
- /*
- * either direct or indirect
- */
- int
- copyau(Adr *a, Adr *v)
- {
- if(copyas(a, v))
- return 1;
- if(v->type == D_REG)
- if(a->type == D_OREG)
- if(v->reg == a->reg)
- return 1;
- return 0;
- }
- int
- copyau1(Prog *p, Adr *v)
- {
- if(regtyp(v))
- if(p->from.type == v->type || p->to.type == v->type)
- if(p->reg == v->reg) {
- if(a2type(p) != v->type)
- print("botch a2type %P\n", p);
- return 1;
- }
- return 0;
- }
- /*
- * substitute s for v in a
- * return failure to substitute
- */
- int
- copysub(Adr *a, Adr *v, Adr *s, int f)
- {
- if(f)
- if(copyau(a, v))
- a->reg = s->reg;
- return 0;
- }
- int
- copysub1(Prog *p1, Adr *v, Adr *s, int f)
- {
- if(f)
- if(copyau1(p1, v))
- p1->reg = s->reg;
- return 0;
- }
|