| // Derived from Inferno utils/6c/peep.c |
| // http://code.google.com/p/inferno-os/source/browse/utils/6c/peep.c |
| // |
| // Copyright © 1994-1999 Lucent Technologies Inc. All rights reserved. |
| // Portions Copyright © 1995-1997 C H Forsyth (forsyth@terzarima.net) |
| // Portions Copyright © 1997-1999 Vita Nuova Limited |
| // Portions Copyright © 2000-2007 Vita Nuova Holdings Limited (www.vitanuova.com) |
| // Portions Copyright © 2004,2006 Bruce Ellis |
| // Portions Copyright © 2005-2007 C H Forsyth (forsyth@terzarima.net) |
| // Revisions Copyright © 2000-2007 Lucent Technologies Inc. and others |
| // Portions Copyright © 2009 The Go Authors. All rights reserved. |
| // |
| // Permission is hereby granted, free of charge, to any person obtaining a copy |
| // of this software and associated documentation files (the "Software"), to deal |
| // in the Software without restriction, including without limitation the rights |
| // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
| // copies of the Software, and to permit persons to whom the Software is |
| // furnished to do so, subject to the following conditions: |
| // |
| // The above copyright notice and this permission notice shall be included in |
| // all copies or substantial portions of the Software. |
| // |
| // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
| // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
| // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, |
| // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN |
| // THE SOFTWARE. |
| |
| #include <u.h> |
| #include <libc.h> |
| #include "gg.h" |
| #include "opt.h" |
| |
| enum { |
| REGEXT = 0, |
| }; |
| |
| static void conprop(Flow *r); |
| static void elimshortmov(Graph*); |
| static int subprop(Flow*); |
| static int copyprop(Graph*, Flow*); |
| static int copy1(Adr*, Adr*, Flow*, int); |
| static int copyas(Adr*, Adr*); |
| static int copyau(Adr*, Adr*); |
| static int copysub(Adr*, Adr*, Adr*, int); |
| |
| static uint32 gactive; |
| |
| // do we need the carry bit |
| static int |
| needc(Prog *p) |
| { |
| ProgInfo info; |
| |
| while(p != P) { |
| proginfo(&info, p); |
| if(info.flags & UseCarry) |
| return 1; |
| if(info.flags & (SetCarry|KillCarry)) |
| return 0; |
| p = p->link; |
| } |
| return 0; |
| } |
| |
| static Flow* |
| rnops(Flow *r) |
| { |
| Prog *p; |
| Flow *r1; |
| |
| if(r != nil) |
| for(;;) { |
| p = r->prog; |
| if(p->as != ANOP || p->from.type != D_NONE || p->to.type != D_NONE) |
| break; |
| r1 = uniqs(r); |
| if(r1 == nil) |
| break; |
| r = r1; |
| } |
| return r; |
| } |
| |
| void |
| peep(Prog *firstp) |
| { |
| Flow *r, *r1; |
| Graph *g; |
| Prog *p, *p1; |
| int t; |
| |
| g = flowstart(firstp, sizeof(Flow)); |
| if(g == nil) |
| return; |
| gactive = 0; |
| |
| // byte, word arithmetic elimination. |
| elimshortmov(g); |
| |
| // constant propagation |
| // find MOV $con,R followed by |
| // another MOV $con,R without |
| // setting R in the interim |
| for(r=g->start; r!=nil; r=r->link) { |
| p = r->prog; |
| switch(p->as) { |
| case ALEAL: |
| if(regtyp(&p->to)) |
| if(p->from.sym != nil) |
| if(p->from.index == D_NONE || p->from.index == D_CONST) |
| conprop(r); |
| break; |
| |
| case AMOVB: |
| case AMOVW: |
| case AMOVL: |
| case AMOVSS: |
| case AMOVSD: |
| if(regtyp(&p->to)) |
| if(p->from.type == D_CONST) |
| conprop(r); |
| break; |
| } |
| } |
| |
| loop1: |
| if(debug['P'] && debug['v']) |
| dumpit("loop1", g->start, 0); |
| |
| t = 0; |
| for(r=g->start; r!=nil; r=r->link) { |
| p = r->prog; |
| switch(p->as) { |
| case AMOVL: |
| case AMOVSS: |
| case AMOVSD: |
| if(regtyp(&p->to)) |
| if(regtyp(&p->from)) { |
| if(copyprop(g, r)) { |
| excise(r); |
| t++; |
| } else |
| if(subprop(r) && copyprop(g, r)) { |
| excise(r); |
| t++; |
| } |
| } |
| break; |
| |
| case AMOVBLZX: |
| case AMOVWLZX: |
| case AMOVBLSX: |
| case AMOVWLSX: |
| if(regtyp(&p->to)) { |
| r1 = rnops(uniqs(r)); |
| if(r1 != nil) { |
| p1 = r1->prog; |
| if(p->as == p1->as && p->to.type == p1->from.type){ |
| p1->as = AMOVL; |
| t++; |
| } |
| } |
| } |
| 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; |
| break; |
| } |
| if(p->from.offset == 1){ |
| if(p->as == AADDL) |
| p->as = AINCL; |
| else |
| p->as = AINCW; |
| p->from = zprog.from; |
| break; |
| } |
| 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; |
| break; |
| } |
| if(p->from.offset == 1){ |
| if(p->as == ASUBL) |
| p->as = ADECL; |
| else |
| p->as = ADECW; |
| p->from = zprog.from; |
| break; |
| } |
| break; |
| } |
| } |
| if(t) |
| goto loop1; |
| |
| // MOVSD removal. |
| // We never use packed registers, so a MOVSD between registers |
| // can be replaced by MOVAPD, which moves the pair of float64s |
| // instead of just the lower one. We only use the lower one, but |
| // the processor can do better if we do moves using both. |
| for(r=g->start; r!=nil; r=r->link) { |
| p = r->prog; |
| if(p->as == AMOVSD) |
| if(regtyp(&p->from)) |
| if(regtyp(&p->to)) |
| p->as = AMOVAPD; |
| } |
| |
| flowend(g); |
| } |
| |
| void |
| excise(Flow *r) |
| { |
| Prog *p; |
| |
| p = r->prog; |
| if(debug['P'] && debug['v']) |
| print("%P ===delete===\n", p); |
| |
| p->as = ANOP; |
| p->from = zprog.from; |
| p->to = zprog.to; |
| |
| ostats.ndelmov++; |
| } |
| |
| int |
| regtyp(Adr *a) |
| { |
| int t; |
| |
| t = a->type; |
| if(t >= D_AX && t <= D_DI) |
| return 1; |
| if(t >= D_X0 && t <= D_X7) |
| return 1; |
| return 0; |
| } |
| |
| // movb elimination. |
| // movb is simulated by the linker |
| // when a register other than ax, bx, cx, dx |
| // is used, so rewrite to other instructions |
| // when possible. a movb into a register |
| // can smash the entire 64-bit register without |
| // causing any trouble. |
| static void |
| elimshortmov(Graph *g) |
| { |
| Prog *p; |
| Flow *r; |
| |
| for(r=g->start; r!=nil; r=r->link) { |
| p = r->prog; |
| if(regtyp(&p->to)) { |
| switch(p->as) { |
| case AINCB: |
| case AINCW: |
| p->as = AINCL; |
| break; |
| case ADECB: |
| case ADECW: |
| p->as = ADECL; |
| break; |
| case ANEGB: |
| case ANEGW: |
| p->as = ANEGL; |
| break; |
| case ANOTB: |
| case ANOTW: |
| p->as = ANOTL; |
| break; |
| } |
| if(regtyp(&p->from) || p->from.type == D_CONST) { |
| // move or artihmetic into partial register. |
| // from another register or constant can be movl. |
| // we don't switch to 32-bit arithmetic if it can |
| // change how the carry bit is set (and the carry bit is needed). |
| switch(p->as) { |
| case AMOVB: |
| case AMOVW: |
| p->as = AMOVL; |
| break; |
| case AADDB: |
| case AADDW: |
| if(!needc(p->link)) |
| p->as = AADDL; |
| break; |
| case ASUBB: |
| case ASUBW: |
| if(!needc(p->link)) |
| p->as = ASUBL; |
| break; |
| case AMULB: |
| case AMULW: |
| p->as = AMULL; |
| break; |
| case AIMULB: |
| case AIMULW: |
| p->as = AIMULL; |
| break; |
| case AANDB: |
| case AANDW: |
| p->as = AANDL; |
| break; |
| case AORB: |
| case AORW: |
| p->as = AORL; |
| break; |
| case AXORB: |
| case AXORW: |
| p->as = AXORL; |
| break; |
| case ASHLB: |
| case ASHLW: |
| p->as = ASHLL; |
| break; |
| } |
| } else { |
| // explicit zero extension |
| switch(p->as) { |
| case AMOVB: |
| p->as = AMOVBLZX; |
| break; |
| case AMOVW: |
| p->as = AMOVWLZX; |
| break; |
| } |
| } |
| } |
| } |
| } |
| |
| /* |
| * 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. |
| */ |
| static int |
| subprop(Flow *r0) |
| { |
| Prog *p; |
| Adr *v1, *v2; |
| Flow *r; |
| int t; |
| ProgInfo info; |
| |
| p = r0->prog; |
| v1 = &p->from; |
| if(!regtyp(v1)) |
| return 0; |
| v2 = &p->to; |
| if(!regtyp(v2)) |
| return 0; |
| for(r=uniqp(r0); r!=nil; r=uniqp(r)) { |
| if(debug['P'] && debug['v']) |
| print("\t? %P\n", r->prog); |
| if(uniqs(r) == nil) |
| break; |
| p = r->prog; |
| if(p->as == AVARDEF || p->as == AVARKILL) |
| continue; |
| proginfo(&info, p); |
| if(info.flags & Call) |
| return 0; |
| |
| if(info.reguse | info.regset) |
| return 0; |
| |
| if((info.flags & Move) && (info.flags & (SizeL|SizeQ|SizeF|SizeD)) && p->to.type == v1->type) |
| goto gotit; |
| |
| 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 |
| */ |
| static int |
| copyprop(Graph *g, Flow *r0) |
| { |
| Prog *p; |
| Adr *v1, *v2; |
| |
| USED(g); |
| p = r0->prog; |
| v1 = &p->from; |
| v2 = &p->to; |
| if(copyas(v1, v2)) |
| return 1; |
| gactive++; |
| return copy1(v1, v2, r0->s1, 0); |
| } |
| |
| static int |
| copy1(Adr *v1, Adr *v2, Flow *r, int f) |
| { |
| int t; |
| Prog *p; |
| |
| if(r->active == gactive) { |
| if(debug['P']) |
| print("act set; return 1\n"); |
| return 1; |
| } |
| r->active = gactive; |
| if(debug['P']) |
| print("copy %D->%D f=%d\n", v1, v2, f); |
| for(; r != nil; r = r->s1) { |
| p = r->prog; |
| if(debug['P']) |
| print("%P", p); |
| if(!f && uniqp(r) == nil) { |
| f = 1; |
| if(debug['P']) |
| print("; merge; f=%d", f); |
| } |
| t = copyu(p, v2, nil); |
| switch(t) { |
| case 2: /* rar, can't 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, nil); |
| 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) |
| { |
| ProgInfo info; |
| |
| switch(p->as) { |
| case AJMP: |
| if(s != nil) { |
| if(copysub(&p->to, v, s, 1)) |
| return 1; |
| return 0; |
| } |
| if(copyau(&p->to, v)) |
| return 1; |
| return 0; |
| |
| case ARET: |
| if(s != nil) |
| return 1; |
| return 3; |
| |
| case ACALL: |
| if(REGEXT && v->type <= REGEXT && v->type > exregoffset) |
| return 2; |
| if(REGARG >= 0 && v->type == (uchar)REGARG) |
| return 2; |
| if(v->type == p->from.type) |
| return 2; |
| |
| if(s != nil) { |
| if(copysub(&p->to, v, s, 1)) |
| return 1; |
| return 0; |
| } |
| if(copyau(&p->to, v)) |
| return 4; |
| return 3; |
| |
| case ATEXT: |
| if(REGARG >= 0 && v->type == (uchar)REGARG) |
| return 3; |
| return 0; |
| } |
| |
| if(p->as == AVARDEF || p->as == AVARKILL) |
| return 0; |
| proginfo(&info, p); |
| |
| if((info.reguse|info.regset) & RtoB(v->type)) |
| return 2; |
| |
| if(info.flags & LeftAddr) |
| if(copyas(&p->from, v)) |
| return 2; |
| |
| if((info.flags & (RightRead|RightWrite)) == (RightRead|RightWrite)) |
| if(copyas(&p->to, v)) |
| return 2; |
| |
| if(info.flags & RightWrite) { |
| if(copyas(&p->to, v)) { |
| if(s != nil) |
| return copysub(&p->from, v, s, 1); |
| if(copyau(&p->from, v)) |
| return 4; |
| return 3; |
| } |
| } |
| |
| if(info.flags & (LeftAddr|LeftRead|LeftWrite|RightAddr|RightRead|RightWrite)) { |
| if(s != nil) { |
| 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; |
| } |
| |
| return 0; |
| } |
| |
| /* |
| * direct reference, |
| * could be set/use depending on |
| * semantics |
| */ |
| static int |
| copyas(Adr *a, Adr *v) |
| { |
| if(D_AL <= a->type && a->type <= D_BL) |
| fatal("use of byte register"); |
| if(D_AL <= v->type && v->type <= D_BL) |
| fatal("use of byte register"); |
| |
| 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; |
| } |
| |
| int |
| sameaddr(Addr *a, Addr *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 |
| */ |
| static 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 |
| */ |
| static 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 || t >= D_X0 && t <= D_X7) { |
| 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; |
| } |
| |
| static void |
| conprop(Flow *r0) |
| { |
| Flow *r; |
| Prog *p, *p0; |
| int t; |
| Adr *v0; |
| |
| p0 = r0->prog; |
| v0 = &p0->to; |
| r = r0; |
| |
| loop: |
| r = uniqs(r); |
| if(r == nil || r == r0) |
| return; |
| if(uniqp(r) == nil) |
| return; |
| |
| p = r->prog; |
| t = copyu(p, v0, nil); |
| switch(t) { |
| case 0: // miss |
| case 1: // use |
| goto loop; |
| |
| case 2: // rar |
| case 4: // use and set |
| break; |
| |
| case 3: // set |
| if(p->as == p0->as) |
| if(p->from.type == p0->from.type) |
| if(p->from.node == p0->from.node) |
| if(p->from.offset == p0->from.offset) |
| if(p->from.scale == p0->from.scale) |
| if(p->from.type == D_FCONST && p->from.u.dval == p0->from.u.dval) |
| if(p->from.index == p0->from.index) { |
| excise(r); |
| goto loop; |
| } |
| break; |
| } |
| } |
| |
| int |
| smallindir(Addr *a, Addr *reg) |
| { |
| return regtyp(reg) && |
| a->type == D_INDIR + reg->type && |
| a->index == D_NONE && |
| 0 <= a->offset && a->offset < 4096; |
| } |
| |
| int |
| stackaddr(Addr *a) |
| { |
| return regtyp(a) && a->type == D_SP; |
| } |