/*  $VER: vbcc (rd.c) V0.4     */
/*  verfuegbare Definitionen und constant propagation   */

#include "opt.h"

static char FILE_[]=__FILE__;

/*  fuer verfuegbare Definitionen   */
unsigned int dcount;
size_t dsize;
struct IC **dlist;
unsigned char **defs;       /*  gibt an, welche Definitionen, welche    */
                            /*  Variablen definieren                    */
/*  alle Definitionen, globaler oder Adr. fuer propagation etc.         */
unsigned char *rd_globals,*rd_address,*rd_statics,*rd_drefs;
/*  dasseble, aber hier nur die undefs  */
unsigned char *rd_defs,*rd_tmp,*rd_parms;

/*  Bitvektor fuer geaenderte Variablen fuer ic_changes */
unsigned char *rd_vars;

/*  rd_mode==0 => reaching definitions fuer constant-propagatione,      */
/*  sonst fuer loop-invariant.                                          */
int rd_mode;

int compare_const(union atyps *q1,union atyps *q2,int t)
/*  vergleiht zwei Konstanten; -1, wenn q1<q2; 0, wenn q1==q1; 1 sonst  */
{
    zdouble d1,d2;zlong l1,l2;zulong u1,u2;zpointer p1,p2;
    t&=31;
    eval_const(q1,t);p1=vpointer;d1=vdouble;l1=vlong;u1=vulong;
    eval_const(q2,t);p2=vpointer;d2=vdouble;l2=vlong;u2=vulong;
    if(t==POINTER) return(zpleq(p2,p1)?!zpeqto(p1,p2):-1);
    if(t==DOUBLE||t==FLOAT) return(zdleq(d2,d1)?!zdeqto(d1,d2):-1);
    if(t&UNSIGNED) return(zulleq(u2,u1)?!zuleqto(u1,u2):-1);
    return(zlleq(l2,l1)?!zleqto(l1,l2):-1);
    ierror(0);
}

void print_rd(unsigned char *bitvector)
/*  druckt Definitionen in einem Bitvektor */
{
    unsigned int i;
    if(!bitvector) {printf("reaching definitions not available\n");return;}
    for(i=1;i<=dcount;i++)
        if(BTST(bitvector,i)) {printf("%3u:",i);pric2(stdout,dlist[i]);}
    for(i=0;i<vcount-rcount;i++)
        if(BTST(bitvector,i+dcount+1)) printf("%3u:\t\tundefined\t->%s\n",i+dcount+1,vilist[i]->identifier);
    for(i=vcount-rcount;i<vcount;i++)
        if(BTST(bitvector,i+dcount+1)) printf("%3u:\t\tundefined\t->(%s)\n",i+dcount+1,vilist[i]->identifier);
}

void num_defs(void)
/*  Numeriert alle Variablendefinitionen (nur elementare Typen noetig)  */
/*  und erzeugt diverse Bitvektoren.                                    */
{
    int i=0;struct IC *p;
    if(DEBUG&1024) printf("numerating definitions\n");
    for(p=first_ic;p;p=p->next){
        if(!(p->z.flags&VAR)&&p->code!=CALL){p->defindex=0;continue;}
/*        if((p->z.v->vtyp->flags&15)>POINTER){p->defindex=0;continue;}*/
        p->defindex=++i;
    }
    dcount=i;dsize=(dcount+CHAR_BIT+vcount)/CHAR_BIT;    /* +1, da bei 1 anfaengt */
    if(DEBUG&1024) printf("%lu definitions, dsize=%lu\n",(unsigned long)dcount,(unsigned long)dsize);
    /*  fuer jede Variable wird eine kuenstliche unbestimmte Def. erzeugt   */
    /*  Feld erzeugen, dass zu jeder Variable alle Definitionen erhaelt    */
    defs=mymalloc(sizeof(unsigned char *)*vcount);
    for(i=0;i<vcount;i++){
        defs[i]=mymalloc(dsize);
        memset(defs[i],0,dsize);
        BSET(defs[i],i+dcount+1);
    }
    dlist=mymalloc((dcount+1)*sizeof(struct IC *));
    rd_globals=mymalloc(dsize);
    memset(rd_globals,0,dsize);
    rd_statics=mymalloc(dsize);
    memset(rd_statics,0,dsize);
    rd_address=mymalloc(dsize);
    memset(rd_address,0,dsize);
    rd_drefs=mymalloc(dsize);
    memset(rd_drefs,0,dsize);

    rd_vars=mymalloc(vsize);

    for(p=first_ic;p;p=p->next){
        if(p->defindex){
            if(p->z.flags&VAR){
                i=p->z.v->index;
                if(p->z.flags&DREFOBJ) i+=vcount-rcount;
                BSET(defs[i],p->defindex);
            }
            dlist[p->defindex]=p;
        }
    }
    if(DEBUG&2048){
        for(i=1;i<=dcount;i++){ printf("Def%3d: ",i);pric2(stdout,dlist[i]);}
        for(i=0;i<vcount;i++){
            printf("Definitionen fuer <%s>:\n",vilist[i]->identifier);
            print_rd(defs[i]);
        }
    }
    for(i=0;i<vcount-rcount;i++){   /*  rd_globals berechnen    */
        if(vilist[i]->vtyp->flags&CONST) continue;
        if(vilist[i]->nesting==0||vilist[i]->storage_class==EXTERN) bvunite(rd_globals,defs[i],dsize);
        if(vilist[i]->flags&USEDASADR) bvunite(rd_address,defs[i],dsize);
        if(vilist[i]->storage_class==STATIC) bvunite(rd_statics,defs[i],dsize);
        if(i<rcount){
            bvunite(rd_address,defs[i+vcount-rcount],dsize);
            bvunite(rd_globals,defs[i+vcount-rcount],dsize);
            bvunite(rd_drefs,defs[i+vcount-rcount],dsize);
        }
    }
    rd_parms=mymalloc(dsize);
    memset(rd_parms,0,dsize);
    for(i=0;i<vcount;i++){
        struct Var *v=vilist[i];
        if(i>=vcount-rcount||v->offset<0||v->nesting==0||v->storage_class==EXTERN||v->storage_class==STATIC){
            BSET(rd_parms,i+dcount+1);
        }
    }
/*    if(DEBUG&1024){printf("rd_globals:\n");print_rd(rd_globals);}*/
}
int complete_def(struct IC *p)
/*  Testet, ob eine Definition die Zielvariable komplett setzt oder nur */
/*  teilweise.                                                          */
{
    struct Typ *t=p->z.v->vtyp;
    int s1,s2;
    if(p->z.flags&DREFOBJ) t=t->next;
    if(!t) return(0);
    s1=szof(t);
    if(p->code==ASSIGN||p->code==GETRETURN) s2=p->q2.reg;
        else s2=sizetab[p->typf&15];
/*    if(s1<s2) ierror(0);*/
    if(s1==s2) return(1); else return(0);
}
void reaching_definitions(struct flowgraph *fg)
/*  Berechnet die verfuegbaren Definitionen fuer jeden Block.   */
{
    struct flowgraph *g;struct IC *p;unsigned char *tmp;
    int changed,pass,i,j;
    /*  rd_gen und rd_kill fuer jeden Block berechnen   */
    if(DEBUG&1024) printf("analysing reaching definitions\n");
    tmp=mymalloc(dsize);
    g=fg;
    while(g){
        g->rd_in=mymalloc(dsize);
        memset(g->rd_in,0,dsize);
        g->rd_out=mymalloc(dsize);
        memset(g->rd_out,0,dsize);
        g->rd_gen=mymalloc(dsize);
        memset(g->rd_gen,0,dsize);
        g->rd_kill=mymalloc(dsize);
        memset(g->rd_kill,0,dsize);
        p=g->end;
        while(p){
            if(p->defindex){
                int zi=-1;
                if(!BTST(g->rd_kill,p->defindex)) BSET(g->rd_gen,p->defindex);
                if(p->z.flags&VAR){
                    if(!BTST(g->rd_kill,p->defindex)&&complete_def(p)){
                        zi=p->z.v->index;
                        if(p->z.flags&DREFOBJ) zi+=vcount-rcount;
                        memcpy(tmp,defs[zi],dsize);
                        bvdiff(tmp,g->rd_gen,dsize);
                        bvunite(g->rd_kill,tmp,dsize);
                    }
                }
                for(j=0;j<p->change_cnt;j++){
                    i=p->change_list[j].v->index;
                    if(p->change_list[j].flags&DREFOBJ) i+=vcount-rcount;
                    if(i>=vcount) continue;
                    if((i!=zi||(p->typf&15)>POINTER)&&!BTST(g->rd_kill,i+dcount+1)){
                        BSET(g->rd_gen,i+dcount+1);
                        if(i<rcount&&!BTST(g->rd_kill,dcount+1+i+vcount-rcount))
                            BSET(g->rd_gen,i+vcount-rcount+dcount+1);
                    }
                }
            }

            if(p==g->start) break;
            p=p->prev;
        }
        memcpy(g->rd_out,g->rd_gen,dsize);
        g=g->normalout;
    }

    /*  rd_in und rd_out fuer jeden Block berechnen */
    /*  out(b)=gen(B) vorinitialisiert              */
    if(DEBUG&1024) {printf("pass:");pass=0;}
    do{
        if(DEBUG&1024) {printf(" %d",++pass);fflush(stdout);}
        changed=0;
        g=fg;
        while(g){
            struct flowlist *lp;
            /*  in(B)=U out(C) : C Vorgaenger von B */
            if(g==fg) memcpy(g->rd_in,rd_parms,dsize);
                else  memset(g->rd_in,0,dsize);
            lp=g->in;
            while(lp){
                if(!lp->graph) ierror(0);
                if(lp->graph->branchout==g||!lp->graph->end||lp->graph->end->code!=BRA)
                    bvunite(g->rd_in,lp->graph->rd_out,dsize);
                lp=lp->next;
            }
            /*  out(b)=gen(B) U (in(B)-kill(B)  */
            memcpy(tmp,g->rd_in,dsize);
            bvdiff(tmp,g->rd_kill,dsize);
            bvunite(tmp,g->rd_gen,dsize);
            if(!bvcmp(tmp,g->rd_out,dsize)){changed=1;memcpy(g->rd_out,tmp,dsize);}
            g=g->normalout;
        }
    }while(changed);
    if(DEBUG&1024) printf("\n");
    free(tmp);
}
void calc(int c,int t,union atyps *q1,union atyps *q2,union atyps *z,struct IC *p)
/*  berechnet z:=q1 op q2; mit Konstanten                           */
{
    zdouble d1,d2;zlong l1,l2;zulong u1,u2;
    eval_const(q1,t);
    d1=vdouble;l1=vlong;u1=vulong;
    if(q2){
        eval_const(q2,t);
        d2=vdouble;l2=vlong;u2=vulong;
    }
    if(c==ADD){ vdouble=zdadd(d1,d2);vlong=zladd(l1,l2);vulong=zuladd(u1,u2);}
    if(c==SUB){ vdouble=zdsub(d1,d2);vlong=zlsub(l1,l2);vulong=zulsub(u1,u2);}
    if(c==MULT){ vdouble=zdmult(d1,d2);vlong=zlmult(l1,l2);vulong=zulmult(u1,u2);}
    if(c==DIV||c==MOD){
        if(zdeq(d2)&&zleq(l2)&&zuleq(u2)){
            err_ic=p;error(210);err_ic=0;
            vlong=l2zl(0L);vulong=ul2zul(0L);vdouble=zl2zd(l1);
        }else{
            if(c==DIV){vdouble=zddiv(d1,d2);if(!zleq(l2)) vlong=zldiv(l1,l2);if(!zuleq(u2)) vulong=zuldiv(u1,u2);}
             else     {if(!zleq(l1)) vlong=zlmod(l1,l2);if(!zuleq(u2)) vulong=zulmod(u1,u2);}
        }
    }
    if(c==AND){ vlong=zland(l1,l2);vulong=zuland(u1,u2);}
    if(c==OR){ vlong=zlor(l1,l2);vulong=zulor(u1,u2);}
    if(c==XOR){ vlong=zlxor(l1,l2);vulong=zulxor(u1,u2);}
    if(c==LSHIFT){ vlong=zllshift(l1,l2);vulong=zullshift(u1,u2);}
    if(c==RSHIFT){ vlong=zlrshift(l1,l2);vulong=zulrshift(u1,u2);}
    if(c==MINUS){ vdouble=zdneg(d1);vlong=zlneg(l1);vulong=zulneg(u1);}
    if(c==KOMPLEMENT){ vlong=zlkompl(l1);vulong=zulkompl(u1);}

    vint=zl2zi(vlong);vshort=zl2zs(vlong);vchar=zl2zc(vlong);
    vuint=zul2zui(vulong);vushort=zul2zus(vulong);vuchar=zul2zuc(vulong);
    vfloat=zd2zf(vdouble);
    insert_const2(z,t);
}

int fold(struct IC *p)
/*  wertet konstante ICs aus    */
{
    int c;
    if(!p) ierror(0);
    c=p->code;
    if(c==ADDI2P||c==SUBIFP||c==SUBPFP||c==ASSIGN||c==PUSH||c==SETRETURN) return(0);
    if(DEBUG&1024) {printf("folding IC:\n");pric2(stdout,p);}
    if(c==TEST||c==COMPARE){
        union atyps val;int cc; /*  condition codes */
        struct IC *bp;
        if(c==TEST){
            eval_const(&p->q1.val,p->typf);
            if(zleq(vlong)&&zuleq(vulong)&&zdeq(vdouble)&&zpeq(vpointer)) cc=0; else cc=1;
        } else cc=compare_const(&p->q1.val,&p->q2.val,p->typf);
        if(DEBUG&1024) printf("(cc=%d; comparison eliminated)\n",cc);
        bp=p->next;
        if(have_alias){ free(p->use_list);free(p->change_list);}
        remove_IC(p);
        while(1){   /*  zugehoerigen Branch suchen  */
            if(!bp||bp->code==LABEL||bp->code==BRA) ierror(0);
            c=bp->code;
            if(c>=BEQ&&c<=BGT) break;
            bp=bp->next;
        }
        if((c==BEQ&&cc==0)||(c==BNE&&cc!=0)||(c==BLT&&cc<0)||(c==BGT&&cc>0)||(c==BLE&&cc<=0)||(c==BGE&&cc>=0)){
            if(DEBUG&1024){ printf("changed following branch to BRA:\n");pric2(stdout,bp);}
            bp->code=BRA;
        }else{
            if(DEBUG&1024){ printf("removed following branch:\n");pric2(stdout,bp);}
            if(have_alias){ free(bp->use_list);free(bp->change_list);}
            remove_IC(bp);
        }
        return(1);
    }
    if(c>=CONVCHAR&&c<=CONVULONG){
        int t;
        if(c==CONVCHAR) t=CHAR;
        if(c==CONVUCHAR) t=UNSIGNED|CHAR;
        if(c==CONVSHORT) t=SHORT;
        if(c==CONVUSHORT) t=UNSIGNED|SHORT;
        if(c==CONVINT) t=INT;
        if(c==CONVUINT) t=UNSIGNED|INT;
        if(c==CONVLONG) t=LONG;
        if(c==CONVULONG) t=UNSIGNED|LONG;
        if(c==CONVFLOAT) t=FLOAT;
        if(c==CONVDOUBLE) t=DOUBLE;
        if(c==CONVPOINTER) t=POINTER;
        eval_const(&p->q1.val,t);
        insert_const2(&p->q1.val,p->typf);
    }else calc(c,p->typf,&p->q1.val,&p->q2.val,&p->q1.val,p);
    p->q2.flags=0;
    p->q2.reg=sizetab[p->typf&15];
    p->code=ASSIGN;
    if(DEBUG&1024){printf("becomes\n");pric2(stdout,p);}
    return(1);
}
int propagate(struct obj *o,int replace)
/*  versucht, Objekte durch Konstanten zu ersetzen und erkennt manche   */
/*  nicht initialisierten Variablen; ist replace==0, wird nicht ersetzt */
{
    unsigned int i,j,t;union atyps *val=0;
    struct Var *v;struct IC *p;
    if(!o||!o->v) ierror(0);
    v=o->v;
    i=v->index;
    if(o->flags&DREFOBJ) i+=vcount-rcount;
    if(DEBUG&2048){
        printf("propagate <%s>\n",o->v->identifier);
        if(o->flags&DREFOBJ) printf("(DREFOBJ)");
        printf("\nall reaching definitions:\n");print_rd(rd_defs);
        printf("definitions of object:\n");print_rd(defs[i]);
    }
    if(v->nesting==0||v->storage_class==STATIC||v->storage_class==EXTERN){
    /*  Wenn moeglich bei statischen Variablen den Wert bei der         */
    /*  Initialisierung ermitteln.                                      */
        if(replace&&(v->vtyp->flags&15)<=DOUBLE&&((v->vtyp->flags&CONST)||(v->nesting>0&&!(v->flags&(USEDASADR|USEDASDEST))))){
            /*  Variable hat noch den Wert der Initialisierung.         */
            if(v->clist){
                /*  Der Wert der Initialisierung ist noch gespeichert.  */
                if(DEBUG&1024) printf("using static initializer\n");
                o->val=v->clist->val;
                o->flags=KONST;
                return(1);
            }else{
                /*  Hier evtl. eine implizite 0 erkennen.               */
            }
        }
    }
    if(BTST(rd_defs,i+dcount+1)) return(0);
    memcpy(rd_tmp,rd_defs,dsize);
    bvintersect(rd_tmp,defs[i],dsize);
    i=0;
    for(j=1;j<=dcount;j++){
        if(BTST(rd_tmp,j)){
            p=dlist[j];
            /*  Die Def. muss mit dem Objekt uebereinstimmen (koennte   */
            /*  auch ein anderes Struktur- oder Arrayy-Element sein).   */
            /*  Dann uebergehen, aber merken, dass eine Def. existiert, */
            /*  um keine falsche "used before defined"-Meldung zu       */
            /*  erzeugen.                                               */
            if(compare_objs(&p->z,o,p->typf)){ i=1; continue;}
            /*  Wenn die Def. kein einfacher Typ ist, muss sie von      */
            /*  einer evtl. spaeteren Def. ueberschrieben worden sein,  */
            /*  da oben schon auf undefined geprueft wurde.             */
            if((p->typf&15)>POINTER){ i=1; continue; }
            /*  Wenn es keine Zuweisung einer Konstanten ist, ist keine */
            /*  Weitergabe von Konstanten moeglich.                     */
            if(p->code!=ASSIGN) return(0);
            if(!(p->q1.flags&KONST)) return(0);
            if(val){
                /*  Wenn mehr als eine Konstante, muessen alle gleich sein  */
                /*  und den gleichen Typ haben.                             */
                if((p->typf&31)!=t) return(0);
                if(compare_const(&p->q1.val,val,t)) return(0);
            }else{
                val=&p->q1.val;t=p->typf&31;
            }
        }
    }
    /*  kann Konstante einsetzen    */
    if(val){
        if(!replace) return(0);
        if(DEBUG&1024){ printf("can <%s> replace by constant\n",o->v->identifier);}
        o->val=*val;
        o->flags=KONST;
        return(1);
    }
    /*  gar keine Definition gefunden   */
    if(!i&&!(v->flags&USEDBEFORE)){
        error(171,v->identifier);v->flags|=USEDBEFORE;
        if(!*v->identifier) {probj(stdout,o,0);prd(stdout,v->vtyp);printf("; offset=%d\n",v->offset);}
    }
    return(0);

}
int constant_propagation(struct flowgraph *fg,int global)
/*  sucht nach konstanten Ausdruecken und nicht definierten Variablen   */
/*  wenn global!=0, dann werden reaching definitions benutzt und global */
/*  optimiert, ansonsten nur innerhalb von basic blocks                 */
{
    struct IC *p;int changed=0,i;struct flowgraph *g;
    if(DEBUG&1024){printf("trying constant propagation\n");}
    rd_defs=mymalloc(dsize);
    rd_tmp=mymalloc(dsize);
    g=fg;
    while(g){
        if(global) memcpy(rd_defs,g->rd_in,dsize);
            else   memset(rd_defs,~0,dsize);
        p=g->start;
        while(p){
/*            if(DEBUG&1024){print_rd(rd_defs);pric2(stdout,p);}*/
            if(p->code!=ADDRESS&&(p->typf&15)<=POINTER&&(p->code<LABEL||p->code>BRA)){
                int i;
                if((p->q1.flags&(VAR|VARADR))==VAR){
                    i=p->q1.v->index;
                    if(p->q1.flags&DREFOBJ) i+=vcount-rcount;
                    changed|=propagate(&p->q1,1);
                }
                if((p->q2.flags&(VAR|VARADR))==VAR){
                    i=p->q2.v->index;
                    if(p->q2.flags&DREFOBJ) i+=vcount-rcount;
                    changed|=propagate(&p->q2,1);
                }
            }
            /*  sollte eigentlich nichts bringen, ausser evtl. Meldung  */
            /*  bei unitiialisierter Variablen                          */
            if(((p->z.flags&(VAR|DREFOBJ))==(VAR|DREFOBJ))){
                i=p->z.v->index+vcount-rcount;
                if(!BTST(rd_defs,i+dcount+1))
                    changed|=propagate(&p->z,0);
            }
            rd_change(p);

            if(p==g->end) break;
            p=p->next;
        }
        g=g->normalout;
    }

    gchanged|=changed;
    for(i=0;i<vcount;i++) free(defs[i]);
    free(defs);
    free(dlist);
    free(rd_globals);
    free(rd_statics);
    free(rd_address);
    free(rd_drefs);
    free(rd_tmp);
    free(rd_defs);
    free(rd_parms);
    free(rd_vars);
    return(changed);
}
void rd_change(struct IC *p)
/*  Fuehrt die Aenderungen in rd_defs durch, die bei IC p auftreten.    */
/*  Benutzt eine ganze Reihe globaler Bitvektoren.                      */
{
    int i,j,zi=-1;
/*    print_rd(rd_defs);*/
    if(p->defindex){
        if(p->z.flags&VAR){
            zi=p->z.v->index;
            if(p->z.flags&DREFOBJ) zi+=vcount-rcount;
        }
        for(j=0;j<p->change_cnt;j++){
            i=p->change_list[j].v->index;
            if(p->change_list[j].flags&DREFOBJ) i+=vcount-rcount;
            if(i>=vcount) continue;
            if(i!=zi||(p->typf&15)>POINTER){
                BSET(rd_defs,i+dcount+1);
                if(i<rcount) BSET(rd_defs,i+vcount-rcount+dcount+1);
            }
        }
        if(zi>=0&&complete_def(p)){
            bvdiff(rd_defs,defs[zi],dsize);
        }
        BSET(rd_defs,p->defindex);
    }
/*    pric2(stdout,p);*/
}