#include "gc.h"

void
peep(void)
{
       Reg *r, *r1, *r2;
       Prog *p, *p1;
       int t, s;
/*
* 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:
       /*
        * propigate move's by renaming
        */
       t = 0;
       for(r=firstr; r!=R; r=r->link) {
               p = r->prog;
               if(p->as == AMOVL || p->as == AFMOVEF || p->as == AFMOVED)
               if(regtyp(p->from.type))
               if(anyvar(&p->to)) {
                       if(copyprop(r)) {
                               excise(r);
                               t++;
                       } else
                       if(subprop(r) && copyprop(r)) {
                               excise(r);
                               t++;
                       }
               }
       }
       if(t)
               goto loop1;
       for(r=firstr; r!=R; r=r->link) {
               p = r->prog;
               /*
                * convert (A) ... A++ into (A)++
                * and     A-- ... (A) into --(A)
                */
               t = aregind(&p->from);
               if(t == D_NONE)
                       goto out1;
               s = asize(p->as);
               if(s == 0)
                       goto out1;
               r1 = findop(r, t, AADDL, s);
               if(r1 != R) {
                       if(usedin(t, &p->to))
                               goto out1;
                       p->from.type += I_INDINC - I_INDIR;
                       excise(r1);
                       goto out1;
               }
               r1 = findop(r, t, ASUBL, s);
               if(r1 != R) {
                       p->from.type += I_INDDEC - I_INDIR;
                       excise(r1);
               }
       out1:
               t = aregind(&p->to);
               if(t == D_NONE)
                       goto out2;
               s = asize(p->as);
               if(s == 0)
                       goto out2;
               r1 = findop(r, t, AADDL, s);
               if(r1 != R) {
                       p->to.type += I_INDINC - I_INDIR;
                       excise(r1);
                       goto out2;
               }
               r1 = findop(r, t, ASUBL, s);
               if(r1 != R) {
                       if(usedin(t, &p->from))
                               goto out2;
                       p->to.type += I_INDDEC - I_INDIR;
                       excise(r1);
               }
       out2:
               /*
                * get rid of unneeded save/restore CCR
                */
               if(p->from.type == D_CCR) {
                       r1 = findccr(r);
                       if(r1 != R) {
                               excise(r);
                               excise(r1);
                       }
               }
               switch(p->as) {
               case ATSTB:
               case ATSTW:
               case ATSTL:
                       if(findtst(r, r->prog, 0))
                               excise(r);
               }
               /*
                * turn TSTB (A); BLT; ORB $128,(A) into TAS (A); BLT; NOP
                */
               if(p->as == ATSTB && (r1 = r->s1)) {
                       if((r1->prog->as == ABLT && (r2 = r1->s1)) ||
                          (r1->prog->as == ABGE && (r2 = r1->s2))) {
                               p1 = r2->prog;
                               if(p1->as == AORB)
                               if(p1->from.type == D_CONST)
                               if(p1->from.offset == 128)
                               if(r1 == uniqp(r2))
                               if(tasas(&p->to, &p1->to)) {
                                       p->as = ATAS;
                                       excise(r2);
                               }
                       }
               }
       }
}

void
excise(Reg *r)
{

       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;
}

/*
* chase backward all cc setting.
* returns 1 if all set same.
*/
int
findtst(Reg *r0, Prog *rp, int n)
{
       Reg *r;
       int c;

loop:
       n++;
       if(n >= 10)
               return 0;
       for(r=r0->p2; r!=R; r=r->p2link) {
               c = setcc(r->prog, rp);
               if(c > 0)
                       continue;
               if(c == 0)
                       return 0;
               if(findtst(r, rp, n) == 0)
                       return 0;
       }
       r = r0->p1;
       if(r == R)
               return 1;
       c = setcc(r->prog, rp);
       if(c > 0)
               return 1;
       if(c == 0)
               return 0;
       r0 = r;
       goto loop;
}

/*
* tests cc
* returns -1 if no change
* returns 1 if set the same
* returns 0 if set different
*/
int
setcc(Prog *p, Prog *rp)
{
       int s;

       s = asize(rp->as);
       switch(p->as) {
       default:
               if(debug['P'])
                       print("unknown setcc %A\n", p->as);
               break;

       case ACMPB:
       case ACMPW:
       case ACMPL:
       case ABSR:
               return 0;

       case ABRA:
       case ABGE:
       case ABNE:
       case ABLE:
       case ABEQ:
       case ABHI:
       case ABLS:
       case ABMI:
       case ABPL:
       case ABGT:
       case ABLT:
       case ABCC:
       case ABCS:
       case APEA:
       case ALEA:
       case ANOP:

       case AFADDD:
       case AFMULD:
       case AFDIVD:
       case AFSUBD:
       case AFADDF:
       case AFMULF:
       case AFDIVF:
       case AFSUBF:
       case AADJSP:
               return -1;

       case AADDW:
       case AADDL:
       case ASUBW:
       case ASUBL:
       case ACLRL:
       case ACLRW:
               if(p->to.type >= D_A0 && p->to.type < D_A0+8)
                       goto areg;

       case AADDB:
       case ASUBB:
       case AANDB:
       case AANDW:
       case AANDL:
       case AORB:
       case AORW:
       case AORL:
       case AEORB:
       case AEORW:
       case AEORL:
       case ALSLB:
       case ALSLW:
       case ALSLL:
       case ALSRB:
       case ALSRW:
       case ALSRL:
       case AASLB:
       case AASLW:
       case AASLL:
       case AASRB:
       case AASRW:
       case AASRL:
       case ATSTB:
       case ATSTW:
       case ATSTL:
       case ANEGB:
       case ANEGW:
       case ANEGL:
       case ACLRB:
               if(asize(p->as) != s)
                       break;
               if(compat(&rp->to, &p->to))
                       return 1;
               break;

       case AMOVW:
       case AMOVL:
               if(p->to.type >= D_A0 && p->to.type < D_A0+8)
                       goto areg;
       case AMOVB:
               if(asize(p->as) != s)
                       break;
               if(compat(&rp->to, &p->to))
                       return 1;
               if(compat(&rp->to, &p->from))
                       return 1;
       }
       return 0;

areg:
       if((rp->to.type&D_MASK) == p->to.type)
               return 0;
       return -1;
}

int
compat(Adr *a, Adr *b)
{
       int o;

       if(a->index != D_NONE)
               return 0;
       if(b->index != D_NONE)
               return 0;
       o = a->type;
       if((o >= D_R0 && o < D_R0+NREG) ||
          (o >= D_A0 && o < D_A0+NREG))
               return o == b->type;
       o &= D_MASK;
       if(o >= D_A0 && o < D_A0+NREG) {
               if(o != (b->type&D_MASK))
                       return 0;
               if(a->offset != b->offset)
                       return 0;
               o = a->type & I_MASK;
               if(o == I_INDIR) {
                       o = b->type & I_MASK;
                       if(o == I_INDIR || o == I_INDDEC)
                               return 1;
                       return 0;
               }
               if(o == I_INDINC) {
                       o = b->type & I_MASK;
                       if(o == I_INDIR) {
                               b->type += I_INDINC-I_INDIR;
                               return 1;
                       }
                       if(o == I_INDDEC) {
                               b->type += I_INDIR-I_INDDEC;
                               return 1;
                       }
                       return 0;
               }
       }
       return 0;
}

int
aregind(Adr *a)
{
       int t;

       t = a->type;
       if(t >= (D_A0|I_INDIR) && t < ((D_A0+NREG)|I_INDIR))
       while(a->offset == 0 && a->index == D_NONE)
               return t & D_MASK;
       return D_NONE;
}

int
asize(int a)
{

       switch(a) {
       case AFTSTD:
       case AFMOVED:
       case AFADDD:
       case AFSUBD:
       case AFMULD:
       case AFDIVD:
       case AFCMPD:
       case AFNEGD:
               return 8;

       case AFTSTF:
       case AFMOVEF:
       case AFADDF:
       case AFSUBF:
       case AFMULF:
       case AFDIVF:
       case AFCMPF:
       case AFNEGF:

       case ACLRL:
       case ATSTL:
       case AMOVL:
       case AADDL:
       case ASUBL:
       case ACMPL:
       case AANDL:
       case AORL:
       case AEORL:
       case ALSLL:
       case ALSRL:
       case AASLL:
       case AASRL:
       case ANEGL:
               return 4;

       case ACLRW:
       case ATSTW:
       case AMOVW:
       case AADDW:
       case ASUBW:
       case ACMPW:
       case AANDW:
       case AORW:
       case AEORW:
       case ALSLW:
       case ALSRW:
       case AASLW:
       case AASRW:
       case ANEGW:
               return 2;

       case ACLRB:
       case ATSTB:
       case AMOVB:
       case AADDB:
       case ASUBB:
       case ACMPB:
       case AANDB:
       case AORB:
       case AEORB:
       case ALSLB:
       case ALSRB:
       case AASLB:
       case AASRB:
       case ANEGB:
               return 1;
       }
       if(debug['P'])
               print("unknown asize %A\n", p->as);
       return 0;
}

int
usedin(int t, Adr *a)
{

       if((a->type&D_MASK) == t)
               return 1;
       if((a->index&D_MASK) == t)
               return 1;
       return 0;
}

Reg*
findccr(Reg *r)
{
       Prog *p;

       for(;;) {
               r = uniqs(r);
               if(r == R)
                       break;
               p = r->prog;
               if(p->to.type == D_CCR)
                       return r;
               if(setccr(p))
                       break;
       }
       return R;
}

int
setccr(Prog *p)
{

       switch(p->as) {
       case ANOP:
               return 0;

       case AADDL:
       case AMOVL:
       case ACLRL:
               if(p->to.type >= D_A0 && p->to.type < D_A0+8)
                       return 0;
       }
       return 1;
}

Reg*
findop(Reg *r, int t, int o, int s)
{
       Prog *p;
       Reg *r1;

       for(;;) {
               if(o == AADDL) {
                       r1 = uniqs(r);
                       if(r1 == R)
                               break;
                       if(uniqp(r1) != r)
                               break;
               } else {
                       r1 = uniqp(r);
                       if(r1 == R)
                               break;
                       if(uniqs(r1) != r)
                               break;
               }
               r = r1;
               p = r->prog;
               if(usedin(t, &p->from))
                       break;
               if(usedin(t, &p->to)) {
                       if(p->as == o)
                       if(p->to.type == t)
                       if(p->to.index == D_NONE)
                       if(p->from.type == D_CONST)
                       if(p->from.offset == s)
                               return r;
                       break;
               }
       }
       return R;
}

int
regtyp(int t)
{

       if(t >= D_R0 && t < D_R0+8)
               return 1;
       if(t >= D_A0 && t < D_A0+8)
               return 1;
       if(t >= D_F0 && t < D_F0+8)
               return 1;
       return 0;
}

int
anyvar(Adr *a)
{

       if(regtyp(a->type))
               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 MOVL
* 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->type))
               return 0;
       v2 = &p->to;
       if(!regtyp(v2->type))
               return 0;
       for(r=uniqp(r0); r!=R; r=uniqp(r)) {
               if(uniqs(r) == R)
                       break;
               p = r->prog;
               switch(p->as) {
               case ADIVUW:    /* these set Rn and Rn+1 */
               case ADIVUL:
               case ADIVSW:
               case ADIVSL:
               case ABSR:
                       return 0;

               case AFMOVED:
               case AFMOVEF:
               case AMOVL:
                       if(p->to.type == v1->type)
                               goto gotit;
               }
               if(copyau(&p->from, v2) || copyau(&p->to, v2))
                       break;
               if(copysub(&p->from, v1, v2, p, 0) || copysub(&p->to, v1, v2, p, 0))
                       break;
       }
       return 0;

gotit:
       copysub(&p->to, v1, v2, p, 1);
       if(debug['P']) {
               print("gotit: %D->%D\n%P", v1, v2, r->prog);
               if(p->from.type == v2->type)
                       print(" excise");
               print("\n");
       }
       if(p->from.type == v2->type)
               excise(r);
       for(r=uniqs(r); r!=r0; r=uniqs(r)) {
               p = r->prog;
               copysub(&p->from, v1, v2, p, 1);
               copysub(&p->to, v1, v2, p, 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;

       if(r->active) {
               if(debug['P'])
                       print("copyret 1\n");
               return 1;
       }
       r->active = 1;
       if(debug['P'])
               print("copy %D->%D\n", v1, v2);
       for(; r != R; r = r->s1) {
               if(debug['P'])
                       print("%P", r->prog);
               if(!f && uniqp(r) == R) {
                       f = 1;
                       if(debug['P'])
                               print("; merge; f=%d", f);
               }
               t = copyu(r->prog, v2, A);
               switch(t) {
               case 2: /* rar, cant split */
                       if(debug['P'])
                               print("; rar return 0\n");
                       return 0;
               case 3: /* set */
                       if(debug['P'])
                               print("; set; return 1\n");
                       return 1;
               case 1: /* used, substitute */
               case 4: /* use and set */
                       if(f) {
                               if(debug['P'])
                                       print("; used and f; return 0\n");
                               return 0;
                       }
                       if(copyu(r->prog, v2, v1)) {
                               if(debug['P'])
                                       print("; sub fail; return 0\n");
                               return 0;
                       }
                       if(debug['P'])
                               print("; substitute");
                       if(t == 4) {
                               if(debug['P'])
                                       print("; used and set; return 1\n");
                               return 1;
                       }
                       break;
               }
               if(!f) {
                       t = copyu(r->prog, v1, A);
                       if(!f && (t == 2 || t == 3 || t == 4)) {
                               if(debug['P'])
                                       print("; f set used");
                               f = 1;
                       }
               }
               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)
{
       int t;

       switch(p->as) {

       default:
               if(debug['P'])
                       print("unknown op %A\n", p->as);
               return 2;

       case APEA:      /* rhs addr */
               if(copyas(&p->to, v))
                       return 2;
               goto caseread;

       case ALEA:      /* lhs addr, rhs store */
               if(copyas(&p->from, v))
                       return 2;

       case AMOVL:     /* rhs store */
       case ACLRL:
       case AFMOVEF:
       case AFMOVED:
       case AFMOVEB:
       case AFMOVEW:
       case AFMOVEL:
       case ANOP:
               if(copyas(&p->to, v)) {
                       if(s != A)
                               return copysub(&p->from, v, s, p, 1);
                       if(copyau(&p->from, v))
                               return 4;
                       return 3;
               }
               goto caseread;

       case AADDL:     /* rhs rar */
       case AADDW:
       case AADDB:
       case ASUBL:
       case ASUBW:
       case ASUBB:
       case AANDL:
       case AANDW:
       case AANDB:
       case AORL:
       case AORW:
       case AORB:
       case AEORL:
       case AEORW:
       case AEORB:
       case AASRL:
       case AASRW:
       case AASRB:
       case AASLL:
       case AASLW:
       case AASLB:
       case ALSRL:
       case ALSRW:
       case ALSRB:
       case ANOTL:
       case ANOTW:
       case ANOTB:
       case ANEGL:
       case ANEGW:
       case ANEGB:
       case AEXTBL:
       case AEXTWL:
       case AEXTBW:

       case AMULSL:
       case AMULUL:

       case AMOVW:     /* only sets part of register */
       case AMOVB:
       case ACLRW:
       case ACLRB:

       case AFADDD:
       case AFMULD:
       case AFDIVD:
       case AFSUBD:
       case AFNEGD:
       case AFADDF:
       case AFMULF:
       case AFDIVF:
       case AFSUBF:
       case AFNEGF:
               if(copyas(&p->to, v))
                       return 2;
               goto caseread;

       case ADBF:      /* lhs rar */
               if(copyas(&p->from, v))
                       return 2;
               goto caseread;

       case ACMPL:     /* read only */
       case ACMPW:
       case ACMPB:
       case AFCMPF:
       case AFCMPD:
       case ATSTL:
       case ATSTW:
       case ATSTB:
       case AFTSTF:
       case AFTSTD:
       caseread:
               if(s != A) {
                       if(copysub(&p->from, v, s, p, 1))
                               return 1;
                       return copysub(&p->to, v, s, p, 1);
               }
               if(copyau(&p->from, v))
                       return 1;
               if(copyau(&p->to, v))
                       return 1;
               break;

       case ABRA:      /* no reference */
       case ABGE:
       case ABNE:
       case ABLE:
       case ABEQ:
       case ABHI:
       case ABLS:
       case ABMI:
       case ABPL:
       case ABGT:
       case ABLT:
       case ABCC:
       case ABCS:

       case AFBEQ:
       case AFBNE:
       case AFBGT:
       case AFBGE:
       case AFBLE:
       case AFBLT:

       case AADJSP:
       case ACASEW:
               break;

       case ADIVUW:    /* these set Rn and Rn+1 */
       case ADIVUL:
       case ADIVSW:
       case ADIVSL:
               t = v->type;
               if(t == p->to.type || t == p->to.type+1)
                       return 2;
               goto caseread;

       case ARTS:      /* funny */
               t = v->type;
               if(t == D_R0 || t == D_F0)
                       return 2;
               if(t >= D_R0 && t < D_R0+NREG)
               if(t-D_R0 > exregoffset)
                       return 2;
               if(t >= D_A0 && t < D_A0+NREG)
               if(t-D_A0 > exaregoffset)
                       return 2;
               if(t >= D_F0 && t < D_F0+NREG)
               if(t-D_F0 > exfregoffset)
                       return 2;
               return 3;

       case ABSR:      /* funny */
               t = v->type;
               if(t >= D_R0 && t < D_R0+NREG)
               if(t-D_R0 > exregoffset)
                       return 2;
               if(t >= D_A0 && t < D_A0+NREG)
               if(t-D_A0 > exaregoffset)
                       return 2;
               if(t >= D_F0 && t < D_F0+NREG)
               if(t-D_F0 > exfregoffset)
                       return 2;
               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->type))
               return 1;
       if(v->type == D_AUTO || v->type == D_PARAM) {
               if(v->offset == a->offset)
                       return 1;
               return 0;
       }
       return 0;
}

/*
* indirect
*/
int
tasas(Adr *a, Adr *v)
{
       int t;

       if(a->index != D_NONE)
               return 0;
       if(v->index != D_NONE)
               return 0;
       t = a->type;
       if(t < I_INDIR+D_A0 && t >= I_INDIR+D_A0+8)
               return 0;
       if(v->type != t)
               return 0;
       if(a->displace != v->displace)
               return 0;
       return 1;
}

/*
* either direct or indirect
*/
int
copyau(Adr *a, Adr *v)
{
       int t;

       if(copyas(a, v))
               return 1;
       t = v->type;
       if(regtyp(t)) {
               if((a->type & D_MASK) == t)
                       return 1;
               if((a->index & D_MASK) == t)
                       return 1;
       }
       return 0;
}

/*
* substitute s for v in a
* return failure to substitute
*/
int
copysub(Adr *a, Adr *v, Adr *s, Prog *p, int f)
{
       int t;

       if(copyas(a, v)) {
               t = s->type;
               if(t >= D_F0 && t < D_F0+8) {
                       if(f)
                               a->type = t;
                       return 0;
               }
               if(t >= D_R0 && t < D_R0+8) {
                       if(f)
                               a->type = t;
                       return 0;
               }
               if(!(t >= D_A0 && t < D_A0+8))
                       return 1;
               switch(p->as) {
               default:
                       return 1;

               case AMOVL:
               case AMOVW:
               case ACMPL:
               case ACMPW:
                       break;

               case AADDL:
               case AADDW:
               case ASUBL:
               case ASUBW:
                       if(a == &p->from && !regtyp(p->to.type))
                               return 1;
                       break;
               }
               if(f)
                       a->type = t;
               return 0;
       }
       t = v->type;
       if(regtyp(t)) {
               if((a->type & D_MASK) == t) {
                       if((s->type ^ t) & ~(NREG-1))
                               return 1;
                       if(f)
                               a->type = (a->type & ~D_MASK) | s->type;
                       return 0;
               }
               if((a->index & D_MASK) == t) {
                       if(f)
                               a->index = (a->index & ~D_MASK) | s->type;
                       return 0;
               }
               return 0;
       }
       return 0;
}

You are viewing proxied material from sdf.org. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.