ref: a00b6bdbfa72a1688a866edf5f825720c9874ada
dir: /sys/src/cmd/6c/peep.c/
#include "gc.h" static int needc(Prog *p) { while(p != P) { switch(p->as) { case AADCL: case AADCQ: case ASBBL: case ASBBQ: case ARCRL: case ARCRQ: return 1; case AADDL: case AADDQ: case ASUBL: case ASUBQ: case AJMP: case ARET: case ACALL: return 0; default: if(p->to.type == D_BRANCH) return 0; } p = p->link; } return 0; } static Reg* rnops(Reg *r) { Prog *p; Reg *r1; if(r != R) for(;;){ p = r->prog; if(p->as != ANOP || p->from.type != D_NONE || p->to.type != D_NONE) break; r1 = uniqs(r); if(r1 == R) break; r = r1; } return r; } 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: t = 0; for(r=firstr; r!=R; r=r->link) { p = r->prog; switch(p->as) { case AMOVL: case AMOVQ: case AMOVSS: case AMOVSD: if(!regtyp(&p->to)) break; if(regtyp(&p->from)) { if(copyprop(r)) { excise(r); t++; break; } if(subprop(r) && copyprop(r)) { excise(r); t++; break; } } if(p->as != AMOVL) break; r1 = rnops(uniqs(r)); if(r1 != R){ p1 = r1->prog; if(p1->as == AMOVLQZX && p1->from.type == p->to.type && p1->to.type == p->to.type){ excise(r1); t++; } } break; case AMOVBLZX: case AMOVWLZX: case AMOVBLSX: case AMOVWLSX: if(regtyp(&p->to)) { r1 = rnops(uniqs(r)); if(r1 != R) { p1 = r1->prog; if(p->to.type != p1->from.type) break; if((p->as == AMOVBLZX && p1->as == AMOVBQZX) || (p->as == AMOVWLZX && p1->as == AMOVWQZX) || (p->as == AMOVBLSX && p1->as == AMOVBQSX && p1->to.type == p->to.type) || (p->as == AMOVWLSX && p1->as == AMOVWQSX && p1->to.type == p->to.type)) { p->as = p1->as; p1->as = AMOVQ; t++; } else if(p->as == p1->as) { p1->as = AMOVL; t++; } } } break; case AMOVBQSX: case AMOVBQZX: case AMOVWQSX: case AMOVWQZX: case AMOVLQSX: case AMOVLQZX: if(regtyp(&p->to)) { r1 = rnops(uniqs(r)); if(r1 != R) { p1 = r1->prog; if(p->as == p1->as && p->to.type == p1->from.type){ p1->as = AMOVQ; t++; } } } break; case AADDL: case AADDQ: case AADDW: if(p->from.type != D_CONST || needc(p->link)) break; if(p->from.offset == -1){ if(p->as == AADDQ) p->as = ADECQ; else if(p->as == AADDL) p->as = ADECL; else p->as = ADECW; p->from = zprog.from; } else if(p->from.offset == 1){ if(p->as == AADDQ) p->as = AINCQ; else if(p->as == AADDL) p->as = AINCL; else p->as = AINCW; p->from = zprog.from; } break; case ASUBL: case ASUBQ: case ASUBW: if(p->from.type != D_CONST || needc(p->link)) break; if(p->from.offset == -1) { if(p->as == ASUBQ) p->as = AINCQ; else if(p->as == ASUBL) p->as = AINCL; else p->as = AINCW; p->from = zprog.from; } else if(p->from.offset == 1){ if(p->as == ASUBQ) p->as = ADECQ; else if(p->as == ASUBL) p->as = ADECL; else p->as = ADECW; p->from = zprog.from; } break; case ACMPL: case ACMPQ: if(p->to.type != D_CONST || p->to.offset != 0 || regtyp(&p->from) == 0) break; if(p->link == P || (p->link->as != AJEQ && p->link->as != AJNE)) break; r1 = uniqp(r); while(r1 != R && r1->prog->as == ANOP) r1 = uniqp(r1); if(r1 == R || r1->prog->to.type != p->from.type) break; p1 = r1->prog; switch(p1->as){ case ASHLQ: case ASHRQ: case ASALQ: case ASARQ: /* shift doesnt affect ZF when shift count is zero */ if(p1->from.type != D_CONST || p1->from.offset == 0) break; case AANDQ: case AORQ: case AXORQ: case ANEGQ: case AADDQ: case AADCQ: case ASUBQ: case ASBBQ: case AINCQ: case ADECQ: if(p->as != ACMPQ) break; case AANDL: case AORL: case AXORL: case ANEGL: case AADDL: case AADCL: case ASUBL: case ASBBL: case AINCL: case ADECL: excise(r); break; case ASHLL: case ASHRL: case ASALL: case ASARL: /* shift doesnt affect ZF when shift count is zero */ if(p1->from.type != D_CONST || p1->from.offset == 0) break; excise(r); } 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_R15) return 1; if(t >= D_X0 && t <= D_X0+15) 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 AIMULL: case AIMULQ: case AIMULW: if(p->to.type != D_NONE) break; case ADIVB: case ADIVL: case ADIVQ: case ADIVW: case AIDIVB: case AIDIVL: case AIDIVQ: case AIDIVW: case AIMULB: case AMULB: case AMULL: case AMULQ: case AMULW: case ACWD: case ACDQ: case ACQO: case AREP: case AREPN: case ALOOP: case ALOOPEQ: case ALOOPNE: case ACALL: return 0; case AROLB: case AROLL: case AROLQ: case AROLW: case ARORB: case ARORL: case ARORQ: case ARORW: case ASALB: case ASALL: case ASALQ: case ASALW: case ASARB: case ASARL: case ASARQ: case ASARW: case ASHLB: case ASHLL: case ASHLQ: case ASHLW: case ASHRB: case ASHRL: case ASHRQ: case ASHRW: if(p->from.type == D_CX && v1->type == D_CX) return 0; break; case AORL: case AORQ: case AANDL: case AANDQ: case AXORL: case AXORQ: case AADDL: case AADDQ: case AADCL: case AADCQ: /* * can swap when: * ADD R2, R1 * MOV R1, R2 * convert to: * ADD R1, R2 * MOV R2, R1 / no use for R1 */ if(p->to.type == v1->type && p->from.type == v2->type){ copysub(&p->from, v2, v1, 1); goto gotit; } break; case AMOVL: case ALEAL: case AMOVSL: case AMOVBLZX: case AMOVBLSX: case AMOVWLZX: case AMOVWLSX: case AMOVQL: case AMOVQ: case ALEAQ: case AMOVSQ: case AMOVBQZX: case AMOVBQSX: case AMOVWQZX: case AMOVWQSX: case AMOVLQZX: case AMOVLQSX: 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); /* SBBL; ADCL; FLD1; SAHF */ return 2; case ANEGB: case ANEGW: case ANEGL: case ANEGQ: case ANOTB: case ANOTW: case ANOTL: case ANOTQ: if(copyas(&p->to, v)) return 2; break; case ALEAL: /* lhs addr, rhs store */ case ALEAQ: if(copyas(&p->from, v)) return 2; case ANOP: /* rhs store */ case AMOVL: case AMOVQ: case AMOVBLSX: case AMOVBLZX: case AMOVBQSX: case AMOVBQZX: case AMOVLQSX: case AMOVLQZX: case AMOVWLSX: case AMOVWLZX: case AMOVWQSX: case AMOVWQZX: case AMOVQL: case AMOVSS: case AMOVSD: case ACVTSD2SL: case ACVTSD2SQ: case ACVTSD2SS: case ACVTSL2SD: case ACVTSL2SS: case ACVTSQ2SD: case ACVTSQ2SS: case ACVTSS2SD: case ACVTSS2SL: case ACVTSS2SQ: case ACVTTSD2SL: case ACVTTSD2SQ: case ACVTTSS2SL: case ACVTTSS2SQ: 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 AROLQ: case AROLW: case ARORB: case ARORL: case ARORQ: case ARORW: case ASALB: case ASALL: case ASALQ: case ASALW: case ASARB: case ASARL: case ASARQ: case ASARW: case ASHLB: case ASHLL: case ASHLQ: case ASHLW: case ASHRB: case ASHRL: case ASHRQ: 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 AADDQ: case AADDW: case AANDB: case AANDL: case AANDQ: case AANDW: case ADECL: case ADECQ: case ADECW: case AINCL: case AINCQ: case AINCW: case ASUBB: case ASUBL: case ASUBQ: case ASUBW: case AORB: case AORL: case AORQ: case AORW: case AXORB: case AXORL: case AXORQ: case AXORW: case AMOVB: case AMOVW: case AADDSD: case AADDSS: case ACMPSD: case ACMPSS: case ADIVSD: case ADIVSS: case AMAXSD: case AMAXSS: case AMINSD: case AMINSS: case AMULSD: case AMULSS: case ARCPSS: case ARSQRTSS: case ASQRTSD: case ASQRTSS: case ASUBSD: case ASUBSS: case AXORPD: if(copyas(&p->to, v)) return 2; goto caseread; case ACMPL: /* read only */ case ACMPW: case ACMPB: case ACMPQ: case ACOMISD: case ACOMISS: case AUCOMISD: case AUCOMISS: 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 AWAIT: case ACLD: break; case AIMULL: case AIMULQ: case AIMULW: if(p->to.type != D_NONE) { if(copyas(&p->to, v)) return 2; goto caseread; } case ADIVB: case ADIVL: case ADIVQ: case ADIVW: case AIDIVB: case AIDIVL: case AIDIVQ: case AIDIVW: case AIMULB: case AMULB: case AMULL: case AMULQ: case AMULW: case ACWD: case ACDQ: case ACQO: if(v->type == D_AX || v->type == D_DX) return 2; goto caseread; case AMOVSL: case AMOVSQ: case AREP: case AREPN: if(v->type == D_CX || v->type == D_DI || v->type == D_SI) 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 || v->type == FREGRET) return 2; if(s != A) return 1; return 3; case ACALL: /* funny */ if(REGEXT && v->type <= REGEXT && v->type > exregoffset) return 2; if(REGARG && 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; case ATEXT: /* funny */ if(REGARG && v->type == REGARG) return 3; return 0; } 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_R15 || t >= D_X0 && t <= D_X0+15) { if(f) a->type = t; } return 0; } if(regtyp(v)) { t = v->type; if(a->type == t+D_INDIR) { if((s->type == D_BP || s->type == D_R13) && 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; }