#include "gc.h"

int xtramodes(Reg*, Adr*);

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 == ASLL || p->as == ASRL || p->as == ASRA || p->as == AROR) {
                       /*
                        * elide shift into D_SHIFT operand of subsequent instruction
                        */
                       if(shiftprop(r)) {
                               excise(r);
                               t++;
                       }
               }
               if(p->as == AMOVW || p->as == AMOVF || p->as == AMOVD)
               if(regtyp(&p->to)) {
                       if(p->from.type == D_CONST)
                               constprop(&p->from, &p->to, r->s1);
                       else 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(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 AEOR:
                       /*
                        * EOR -1,x,y => MVN x,y
                        */
                       if(p->from.type == D_CONST && p->from.offset == -1) {
                               p->as = AMVN;
                               p->from.type = D_REG;
                               if(p->reg != NREG)
                                       p->from.reg = p->reg;
                               else
                                       p->from.reg = p->to.reg;
                               p->reg = NREG;
                       }
                       continue;
               case AMOVH:
               case AMOVHU:
               case AMOVB:
               case AMOVBU:
                       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);
       }

       for(r=firstr; r!=R; r=r->link) {
               p = r->prog;
               switch(p->as) {
               case AMOVW:
               case AMOVB:
               case AMOVBU:
                       if(p->from.type == D_OREG && p->from.offset == 0)
                               xtramodes(r, &p->from);
                       else if(p->to.type == D_OREG && p->to.offset == 0)
                               xtramodes(r, &p->to);
                       else
                               continue;
                       break;
               case ACMP:
                       /*
                        * elide CMP $0,x if calculation of x can set condition codes
                        */
                       if(p->from.type != D_CONST || p->from.offset != 0)
                               continue;
                       r2 = r->s1;
                       if(r2 == R)
                               continue;
                       t = r2->prog->as;
                       switch(t) {
                       default:
                               continue;
                       case ABEQ:
                       case ABNE:
                       case ABMI:
                       case ABPL:
                               break;
                       case ABGE:
                               t = ABPL;
                               break;
                       case ABLT:
                               t = ABMI;
                               break;
                       case ABHI:
                               t = ABNE;
                               break;
                       case ABLS:
                               t = ABEQ;
                               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)
                               continue;
                       if(p1->to.reg != p->reg)
                       if(!(p1->as == AMOVW && p1->from.type == D_REG && p1->from.reg == p->reg))
                               continue;
                       switch(p1->as) {
                       default:
                               continue;
                       case AMOVW:
                               if(p1->from.type != D_REG)
                                       continue;
                       case AAND:
                       case AEOR:
                       case AORR:
                       case ABIC:
                       case AMVN:
                       case ASUB:
                       case ARSB:
                       case AADD:
                       case AADC:
                       case ASBC:
                       case ARSC:
                               break;
                       }
                       p1->scond |= C_SBIT;
                       r2->prog->as = t;
                       excise(r);
                       continue;
               }
       }

       predicate();
}

void
excise(Reg *r)
{
       Prog *p;

       p = r->prog;
       p->as = ANOP;
       p->scond = zprog.scond;
       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;
}

int
regtyp(Adr *a)
{
       if(a->type == D_REG)
               return 1;
       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 ACMP:
               case ACMN:
               case AADD:
               case ASUB:
               case ARSB:
               case ASLL:
               case ASRL:
               case ASRA:
               case AROR:
               case AORR:
               case AAND:
               case AEOR:
               case AMUL:
               case AMULU:
               case ADIV:
               case ADIVU:

               case ACMPF:
               case ACMPD:
               case AADDD:
               case AADDF:
               case ASUBD:
               case ASUBF:
               case AMULD:
               case AMULF:
               case ADIVD:
               case ADIVF:
                       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 AMOVF:
               case AMOVD:
               case AMOVW:
                       if(p->to.type == v1->type)
                       if(p->to.reg == v1->reg)
                               goto gotit;
                       break;

               case AMOVM:
                       t = (1<<v1->reg) | (1<<v2->reg);
                       if((p->from.type == D_CONST && (p->from.offset&t)) ||
                          (p->to.type == D_CONST && (p->to.offset&t)))
                               return 0;
                       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);
}

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("; %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;
}

/*
* The idea is to remove redundant constants.
*      $c1->v1
*      ($c1->v2 s/$c1/v1)*
*      set v1  return
* The v1->v2 should be eliminated by copy propagation.
*/
void
constprop(Adr *c1, Adr *v1, Reg *r)
{
       Prog *p;

       if(debug['C'])
               print("constprop %D->%D\n", c1, v1);
       for(; r != R; r = r->s1) {
               p = r->prog;
               if(debug['C'])
                       print("%P", p);
               if(uniqp(r) == R) {
                       if(debug['C'])
                               print("; merge; return\n");
                       return;
               }
               if(p->as == AMOVW && copyas(&p->from, c1)) {
                               if(debug['C'])
                                       print("; sub%D/%D", &p->from, v1);
                               p->from = *v1;
               } else if(copyu(p, v1, A) > 1) {
                       if(debug['C'])
                               print("; %Dset; return\n", v1);
                       return;
               }
               if(debug['C'])
                       print("\n");
               if(r->s2)
                       constprop(c1, v1, r->s2);
       }
}

/*
* ASLL x,y,w
* .. (not use w, not set x y w)
* AXXX w,a,b (a != w)
* .. (not use w)
* (set w)
* ----------- changed to
* ..
* AXXX (x<<y),a,b
* ..
*/
#define FAIL(msg) { if(debug['H']) print("\t%s; FAILURE\n", msg); return 0; }
int
shiftprop(Reg *r)
{
       Reg *r1;
       Prog *p, *p1, *p2;
       int n, o;
       Adr a;

       p = r->prog;
       if(p->to.type != D_REG)
               FAIL("BOTCH: result not reg");
       n = p->to.reg;
       a = zprog.from;
       if(p->reg != NREG && p->reg != p->to.reg) {
               a.type = D_REG;
               a.reg = p->reg;
       }
       if(debug['H'])
               print("shiftprop\n%P", p);
       r1 = r;
       for(;;) {
               /* find first use of shift result; abort if shift operands or result are changed */
               r1 = uniqs(r1);
               if(r1 == R)
                       FAIL("branch");
               if(uniqp(r1) == R)
                       FAIL("merge");
               p1 = r1->prog;
               if(debug['H'])
                       print("\n%P", p1);
               switch(copyu(p1, &p->to, A)) {
               case 0: /* not used or set */
                       if((p->from.type == D_REG && copyu(p1, &p->from, A) > 1) ||
                          (a.type == D_REG && copyu(p1, &a, A) > 1))
                               FAIL("args modified");
                       continue;
               case 3: /* set, not used */
                       FAIL("BOTCH: noref");
               }
               break;
       }
       /* check whether substitution can be done */
       switch(p1->as) {
       default:
               FAIL("non-dpi");
       case AAND:
       case AEOR:
       case AADD:
       case AADC:
       case AORR:
       case ASUB:
       case ARSB:
       case ASBC:
       case ARSC:
               if(p1->reg == n || (p1->reg == NREG && p1->to.type == D_REG && p1->to.reg == n)) {
                       if(p1->from.type != D_REG)
                               FAIL("can't swap");
                       p1->reg = p1->from.reg;
                       p1->from.reg = n;
                       switch(p1->as) {
                       case ASUB:
                               p1->as = ARSB;
                               break;
                       case ARSB:
                               p1->as = ASUB;
                               break;
                       case ASBC:
                               p1->as = ARSC;
                               break;
                       case ARSC:
                               p1->as = ASBC;
                               break;
                       }
                       if(debug['H'])
                               print("\t=>%P", p1);
               }
       case ABIC:
       case ACMP:
       case ACMN:
               if(p1->reg == n)
                       FAIL("can't swap");
               if(p1->reg == NREG && p1->to.reg == n)
                       FAIL("shift result used twice");
       case AMVN:
               if(p1->from.type == D_SHIFT)
                       FAIL("shift result used in shift");
               if(p1->from.type != D_REG || p1->from.reg != n)
                       FAIL("BOTCH: where is it used?");
               break;
       }
       /* check whether shift result is used subsequently */
       p2 = p1;
       if(p1->to.reg != n)
       for (;;) {
               r1 = uniqs(r1);
               if(r1 == R)
                       FAIL("inconclusive");
               p1 = r1->prog;
               if(debug['H'])
                       print("\n%P", p1);
               switch(copyu(p1, &p->to, A)) {
               case 0: /* not used or set */
                       continue;
               case 3: /* set, not used */
                       break;
               default:/* used */
                       FAIL("reused");
               }
               break;
       }
       /* make the substitution */
       p2->from.type = D_SHIFT;
       p2->from.reg = NREG;
       o = p->reg;
       if(o == NREG)
               o = p->to.reg;
       switch(p->from.type){
       case D_CONST:
               o |= (p->from.offset&0x1f)<<7;
               break;
       case D_REG:
               o |= (1<<4) | (p->from.reg<<8);
               break;
       }
       switch(p->as){
       case ASLL:
               o |= 0<<5;
               break;
       case ASRL:
               o |= 1<<5;
               break;
       case ASRA:
               o |= 2<<5;
               break;
       case AROR:
               o |= 3<<5;
               break;
       }
       p2->from.offset = o;
       if(debug['H'])
               print("\t=>%P\tSUCCEED\n", p2);
       return 1;
}

Reg*
findpre(Reg *r, Adr *v)
{
       Reg *r1;

       for(r1=uniqp(r); r1!=R; r=r1,r1=uniqp(r)) {
               if(uniqs(r1) != r)
                       return R;
               switch(copyu(r1->prog, v, A)) {
               case 1: /* used */
               case 2: /* read-alter-rewrite */
                       return R;
               case 3: /* set */
               case 4: /* set and used */
                       return r1;
               }
       }
       return R;
}

Reg*
findinc(Reg *r, Reg *r2, Adr *v)
{
       Reg *r1;
       Prog *p;


       for(r1=uniqs(r); r1!=R && r1!=r2; r=r1,r1=uniqs(r)) {
               if(uniqp(r1) != r)
                       return R;
               switch(copyu(r1->prog, v, A)) {
               case 0: /* not touched */
                       continue;
               case 4: /* set and used */
                       p = r1->prog;
                       if(p->as == AADD)
                       if(p->from.type == D_CONST)
                       if(p->from.offset > -4096 && p->from.offset < 4096)
                               return r1;
               default:
                       return R;
               }
       }
       return R;
}

int
nochange(Reg *r, Reg *r2, Prog *p)
{
       Adr a[3];
       int i, n;

       if(r == r2)
               return 1;
       n = 0;
       if(p->reg != NREG && p->reg != p->to.reg) {
               a[n].type = D_REG;
               a[n++].reg = p->reg;
       }
       switch(p->from.type) {
       case D_SHIFT:
               a[n].type = D_REG;
               a[n++].reg = p->from.offset&0xf;
       case D_REG:
               a[n].type = D_REG;
               a[n++].reg = p->from.reg;
       }
       if(n == 0)
               return 1;
       for(; r!=R && r!=r2; r=uniqs(r)) {
               p = r->prog;
               for(i=0; i<n; i++)
                       if(copyu(p, &a[i], A) > 1)
                               return 0;
       }
       return 1;
}

int
findu1(Reg *r, Adr *v)
{
       for(; r != R; r = r->s1) {
               if(r->active)
                       return 0;
               r->active = 1;
               switch(copyu(r->prog, v, A)) {
               case 1: /* used */
               case 2: /* read-alter-rewrite */
               case 4: /* set and used */
                       return 1;
               case 3: /* set */
                       return 0;
               }
               if(r->s2)
                       if (findu1(r->s2, v))
                               return 1;
       }
       return 0;
}

int
finduse(Reg *r, Adr *v)
{
       Reg *r1;

       for(r1=firstr; r1!=R; r1=r1->link)
               r1->active = 0;
       return findu1(r, v);
}

int
xtramodes(Reg *r, Adr *a)
{
       Reg *r1, *r2, *r3;
       Prog *p, *p1;
       Adr v;

       p = r->prog;
       if(debug['h'] && p->as == AMOVB && p->from.type == D_OREG)      /* byte load */
               return 0;
       v = *a;
       v.type = D_REG;
       r1 = findpre(r, &v);
       if(r1 != R) {
               p1 = r1->prog;
               if(p1->to.type == D_REG && p1->to.reg == v.reg)
               switch(p1->as) {
               case AADD:
                       if(p1->from.type == D_REG ||
                          (p1->from.type == D_SHIFT && (p1->from.offset&(1<<4)) == 0 &&
                           (p->as != AMOVB || (a == &p->from && (p1->from.offset&~0xf) == 0))) ||
                          (p1->from.type == D_CONST &&
                           p1->from.offset > -4096 && p1->from.offset < 4096))
                       if(nochange(uniqs(r1), r, p1)) {
                               if(a != &p->from || v.reg != p->to.reg)
                               if (finduse(r->s1, &v)) {
                                       if(p1->reg == NREG || p1->reg == v.reg)
                                               /* pre-indexing */
                                               p->scond |= C_WBIT;
                                       else return 0;
                               }
                               switch (p1->from.type) {
                               case D_REG:
                                       /* register offset */
                                       a->type = D_SHIFT;
                                       a->offset = p1->from.reg;
                                       break;
                               case D_SHIFT:
                                       /* scaled register offset */
                                       a->type = D_SHIFT;
                               case D_CONST:
                                       /* immediate offset */
                                       a->offset = p1->from.offset;
                                       break;
                               }
                               if(p1->reg != NREG)
                                       a->reg = p1->reg;
                               excise(r1);
                               return 1;
                       }
                       break;
               case AMOVW:
                       if(p1->from.type == D_REG)
                       if((r2 = findinc(r1, r, &p1->from)) != R) {
                       for(r3=uniqs(r2); r3->prog->as==ANOP; r3=uniqs(r3))
                               ;
                       if(r3 == r) {
                               /* post-indexing */
                               p1 = r2->prog;
                               a->reg = p1->to.reg;
                               a->offset = p1->from.offset;
                               p->scond |= C_PBIT;
                               if(!finduse(r, &r1->prog->to))
                                       excise(r1);
                               excise(r2);
                               return 1;
                       }
                       }
                       break;
               }
       }
       if(a != &p->from || a->reg != p->to.reg)
       if((r1 = findinc(r, R, &v)) != R) {
               /* post-indexing */
               p1 = r1->prog;
               a->offset = p1->from.offset;
               p->scond |= C_PBIT;
               excise(r1);
               return 1;
       }
       return 0;
}

/*
* 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 AMULL:
       case AMULAL:
       case AMULLU:
       case AMULALU:
               if(v->type != D_REG)
                       return 0;
               if(copyau(&p->to, v))
                       return (p->as == AMULAL || p->as == AMULALU) ? 2 : 3;
               if(p->from.reg == v->reg || p->reg == v->reg){
                       if(s != A && !copyau(&p->to, s) && p->from.reg != s->reg && p->reg != s->reg){
                               if(p->from.reg == v->reg)
                                       p->from.reg = s->reg;
                               if(p->reg == v->reg)
                                       p->reg = s->reg;
                       }
                       return 1;
               }
               return 0;

       case AMOVM:
               if(v->type != D_REG)
                       return 0;
               if(p->from.type == D_CONST) {   /* read reglist, read/rar */
                       if(s != A) {
                               if(p->from.offset&(1<<v->reg))
                                       return 1;
                               if(copysub(&p->to, v, s, 1))
                                       return 1;
                               return 0;
                       }
                       if(copyau(&p->to, v)) {
                               if(p->scond&C_WBIT)
                                       return 2;
                               return 1;
                       }
                       if(p->from.offset&(1<<v->reg))
                               return 1;
               } else {                        /* read/rar, write reglist */
                       if(s != A) {
                               if(p->to.offset&(1<<v->reg))
                                       return 1;
                               if(copysub(&p->from, v, s, 1))
                                       return 1;
                               return 0;
                       }
                       if(copyau(&p->from, v)) {
                               if(p->scond&C_WBIT)
                                       return 2;
                               if(p->to.offset&(1<<v->reg))
                                       return 4;
                               return 1;
                       }
                       if(p->to.offset&(1<<v->reg))
                               return 3;
               }
               return 0;

       case ANOP:      /* read, write */
       case AMOVW:
       case AMOVF:
       case AMOVD:
       case AMOVH:
       case AMOVHU:
       case AMOVB:
       case AMOVBU:
       case AMOVDW:
       case AMOVWD:
       case AMOVFD:
       case AMOVDF:
               if(p->scond&(C_WBIT|C_PBIT))
               if(v->type == D_REG) {
                       if(p->from.type == D_OREG || p->from.type == D_SHIFT) {
                               if(p->from.reg == v->reg)
                                       return 2;
                       } else {
                               if(p->to.reg == v->reg)
                               return 2;
                       }
               }
               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 ARSB:
       case ASLL:
       case ASRL:
       case ASRA:
       case AROR:
       case AORR:
       case AAND:
       case AEOR:
       case AMUL:
       case AMULU:
       case ADIV:
       case ADIVU:
       case AADDF:
       case AADDD:
       case ASUBF:
       case ASUBD:
       case AMULF:
       case AMULD:
       case ADIVF:
       case ADIVD:

       case ACMPF:
       case ACMPD:
       case ACMP:
       case ACMN:
       case ACASE:
               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:      /* read, read */
       case ABNE:
       case ABCS:
       case ABHS:
       case ABCC:
       case ABLO:
       case ABMI:
       case ABPL:
       case ABVS:
       case ABVC:
       case ABHI:
       case ABLS:
       case ABGE:
       case ABLT:
       case ABGT:
       case ABLE:
               if(s != A) {
                       if(copysub(&p->from, v, s, 1))
                               return 1;
                       return copysub1(p, v, s, 1);
               }
               if(copyau(&p->from, v))
                       return 1;
               if(copyau1(p, v))
                       return 1;
               return 0;

       case AB:        /* 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 == 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 == (uchar)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 == (uchar)REGARG)
                               return 3;
               return 0;
       }
}

int
a2type(Prog *p)
{

       switch(p->as) {

       case ACMP:
       case ACMN:

       case AADD:
       case ASUB:
       case ARSB:
       case ASLL:
       case ASRL:
       case ASRA:
       case AROR:
       case AORR:
       case AAND:
       case AEOR:
       case AMUL:
       case AMULU:
       case ADIV:
       case ADIVU:
               return D_REG;

       case ACMPF:
       case ACMPD:

       case AADDF:
       case AADDD:
       case ASUBF:
       case ASUBD:
       case AMULF:
       case AMULD:
       case ADIVF:
       case ADIVD:
               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;
       } else if(v->type == D_CONST) {         /* for constprop */
               if(a->type == v->type)
               if(a->name == v->name)
               if(a->sym == v->sym)
               if(a->reg == v->reg)
               if(a->offset == v->offset)
                       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(a->reg == v->reg)
                               return 1;
               } else if(a->type == D_SHIFT) {
                       if((a->offset&0xf) == v->reg)
                               return 1;
                       if((a->offset&(1<<4)) && (a->offset>>8) == v->reg)
                               return 1;
               } else if(a->type == D_REGREG) {
                       if(a->reg == v->reg || a->offset == v->reg)
                               return 1;
               }
       }
       return 0;
}

int
copyau1(Prog *p, Adr *v)
{

       if(regtyp(v)) {
               if(a2type(p) == 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)) {
               if(a->type == D_SHIFT) {
                       if((a->offset&0xf) == v->reg)
                               a->offset = (a->offset&~0xf)|s->reg;
                       if((a->offset&(1<<4)) && (a->offset>>8) == v->reg)
                               a->offset = (a->offset&~(0xf<<8))|(s->reg<<8);
               } else if(a->type == D_REGREG) {
                       if(a->offset == v->reg)
                               a->offset = s->reg;
                       if(a->reg == v->reg)
                               a->reg = s->reg;
               } else
                       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;
}

struct {
       int opcode;
       int notopcode;
       int scond;
       int notscond;
} predinfo[]  = {
       { ABEQ, ABNE,   0x0,    0x1, },
       { ABNE, ABEQ,   0x1,    0x0, },
       { ABCS, ABCC,   0x2,    0x3, },
       { ABHS, ABLO,   0x2,    0x3, },
       { ABCC, ABCS,   0x3,    0x2, },
       { ABLO, ABHS,   0x3,    0x2, },
       { ABMI, ABPL,   0x4,    0x5, },
       { ABPL, ABMI,   0x5,    0x4, },
       { ABVS, ABVC,   0x6,    0x7, },
       { ABVC, ABVS,   0x7,    0x6, },
       { ABHI, ABLS,   0x8,    0x9, },
       { ABLS, ABHI,   0x9,    0x8, },
       { ABGE, ABLT,   0xA,    0xB, },
       { ABLT, ABGE,   0xB,    0xA, },
       { ABGT, ABLE,   0xC,    0xD, },
       { ABLE, ABGT,   0xD,    0xC, },
};

typedef struct {
       Reg *start;
       Reg *last;
       Reg *end;
       int len;
} Joininfo;

enum {
       Join,
       Split,
       End,
       Branch,
       Setcond,
       Toolong
};

enum {
       Falsecond,
       Truecond,
       Delbranch,
       Keepbranch
};

int
isbranch(Prog *p)
{
       return (ABEQ <= p->as) && (p->as <= ABLE);
}

int
predicable(Prog *p)
{
       if (isbranch(p)
               || p->as == ANOP
               || p->as == AXXX
               || p->as == ADATA
               || p->as == AGLOBL
               || p->as == AGOK
               || p->as == AHISTORY
               || p->as == ANAME
               || p->as == ASIGNAME
               || p->as == ATEXT
               || p->as == AWORD
               || p->as == ADYNT
               || p->as == AINIT
               || p->as == ABCASE
               || p->as == ACASE)
               return 0;
       return 1;
}

/*
* Depends on an analysis of the encodings performed by 5l.
* These seem to be all of the opcodes that lead to the "S" bit
* being set in the instruction encodings.
*
* C_SBIT may also have been set explicitly in p->scond.
*/
int
modifiescpsr(Prog *p)
{
       return (p->scond&C_SBIT)
               || p->as == ATST
               || p->as == ATEQ
               || p->as == ACMN
               || p->as == ACMP
               || p->as == AMULU
               || p->as == ADIVU
               || p->as == AMUL
               || p->as == ADIV
               || p->as == AMOD
               || p->as == AMODU
               || p->as == ABL;
}

/*
* Find the maximal chain of instructions starting with r which could
* be executed conditionally
*/
int
joinsplit(Reg *r, Joininfo *j)
{
       j->start = r;
       j->last = r;
       j->len = 0;
       do {
               if (r->p2 && (r->p1 || r->p2->p2link)) {
                       j->end = r;
                       return Join;
               }
               if (r->s1 && r->s2) {
                       j->end = r;
                       return Split;
               }
               j->last = r;
               if (r->prog->as != ANOP)
                       j->len++;
               if (!r->s1 && !r->s2) {
                       j->end = r->link;
                       return End;
               }
               if (r->s2) {
                       j->end = r->s2;
                       return Branch;
               }
               switch(r->prog->as){
               case ADIV:
               case ADIVU:
               case AMOD:
               case AMODU:
                       /* emulated by 5l, doesnt handle conditionals */
                       j->end = r->s1;
                       return Toolong;
               }
               if (modifiescpsr(r->prog)) {
                       j->end = r->s1;
                       return Setcond;
               }
               r = r->s1;
       } while (j->len < 4);
       j->end = r;
       return Toolong;
}

Reg *
successor(Reg *r)
{
       if (r->s1)
               return r->s1;
       else
               return r->s2;
}

void
applypred(Reg *rstart, Joininfo *j, int cond, int branch)
{
       int pred;
       Reg *r;

       if(j->len == 0)
               return;
       if (cond == Truecond)
               pred = predinfo[rstart->prog->as - ABEQ].scond;
       else
               pred = predinfo[rstart->prog->as - ABEQ].notscond;

       for (r = j->start; ; r = successor(r)) {
               if (r->prog->as == AB) {
                       if (r != j->last || branch == Delbranch)
                               excise(r);
                       else {
                         if (cond == Truecond)
                               r->prog->as = predinfo[rstart->prog->as - ABEQ].opcode;
                         else
                               r->prog->as = predinfo[rstart->prog->as - ABEQ].notopcode;
                       }
               }
               else if (predicable(r->prog))
                       r->prog->scond = (r->prog->scond&~C_SCOND)|pred;
               if (r->s1 != r->link) {
                       r->s1 = r->link;
                       r->link->p1 = r;
               }
               if (r == j->last)
                       break;
       }
}

void
predicate(void)
{
       Reg *r;
       int t1, t2;
       Joininfo j1, j2;

       for(r=firstr; r!=R; r=r->link) {
               if (isbranch(r->prog)) {
                       t1 = joinsplit(r->s1, &j1);
                       t2 = joinsplit(r->s2, &j2);
                       if(j1.last->link != j2.start)
                               continue;
                       if(j1.end == j2.end)
                       if((t1 == Branch && (t2 == Join || t2 == Setcond)) ||
                          (t2 == Join && (t1 == Join || t1 == Setcond))) {
                               applypred(r, &j1, Falsecond, Delbranch);
                               applypred(r, &j2, Truecond, Delbranch);
                               excise(r);
                               continue;
                       }
                       if(t1 == End || t1 == Branch) {
                               applypred(r, &j1, Falsecond, Keepbranch);
                               excise(r);
                               continue;
                       }
               }
       }
}

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.