/*  $VER: vbcc (loop.c) V0.3     */
/*  schleifenorientierte Optimierungen  */

#include "opt.h"

int report_weird_code;

void loops(struct flowgraph *fg,int footers)
/*  kennzeichnet Schleifen im Flussgraph; wenn footers!=0 werden darf eine  */
/*  Schleife nur einen gemeinsamen Austrittspunkt haben                     */
{
    int i,start,end;struct flowlist *lp;struct flowgraph *g,*loopend;
    if(DEBUG&1024) printf("searching loops\n");
    g=fg;
    while(g){
        start=g->index;
        end=-1;
        lp=g->in;
        while(lp){
            if(lp->graph->branchout==g||!lp->graph->end||lp->graph->end->code!=BRA){
                i=lp->graph->index;
                if(i>=start&&i>end){ end=i;loopend=lp->graph; }
            }
            lp=lp->next;
        }
        if(end>=0){
        /*  Schleife oder etwas aehnliches  */
            struct flowgraph *p=g;
            if(DEBUG&1024) printf("found possible loop from blocks %d to %d\n",start,end);
            if(goto_used){
                if(DEBUG&1024) printf("have to check...\n");
                do{
                    if(!p||p->index>end) break;
                    /*  testen, ob aus der Schleife gesprungen wird */
                    if(p->branchout){
                        i=p->branchout->index;
                        if(i<start){
                            if(report_weird_code){error(175);report_weird_code=0;}
                            end=-1;
                            break;
                        }
                        if(i>end&&(DEBUG&1024)){
                            puts("jump out of loop");
                            if(p->branchout!=loopend->normalout){
                                puts("no break");
                                if(p->branchout->start->typf!=return_label) puts("no return");
                            }
                        }
                        if(i>end&&p->branchout!=loopend->normalout&&p->branchout->start->typf!=return_label){
                        /*  Sprung zu anderem als dem normalen Austritt oder return */
                            end=-1;
                            break;
                        }
                    }
                    /*  testen, ob in die Schleife gesprungen wird  */
                    lp=p->in;
                    while(lp){
                        if(lp->graph->branchout==p){
                            i=lp->graph->index;
                            if(i<start||i>end){
                                if(report_weird_code){error(175);report_weird_code=0;}
                                end=-1;
                                break;
                            }
                        }
                        lp=lp->next;
                    }
                    if(p->index==end) break;
                    p=p->normalout;
                }while(1);
            }else{
                if(DEBUG&1024) printf("must be a loop, because there was no goto\n");
            }
        }
        if(end>=0){
            if(DEBUG&1024) printf("confirmed that it is a loop\n");
            g->loopend=loopend;
        }
        g=g->normalout;
    }
}

struct flowgraph *create_loop_headers(struct flowgraph *fg)
/*  fuegt vor jede Schleife einen Kopf-Block ein, wenn noetig   */
/*  braucht aktive Variablen und kann einen Block mehrmals in   */
/*  der ->in Liste eintragen                                    */
{
    struct flowgraph *g,*last,*new,*rg=fg;
    struct IC *lic;
    if(DEBUG&1024) printf("creating loop-headers\n");
    g=fg;last=0;
    while(g){
        new=0;
        if(g->loopend){
            if(!last){
                struct flowlist *lp;
                new=mymalloc(sizeof(struct flowgraph));
                rg=new;
                new->in=0;
                new->start=new->end=0;
                lp=mymalloc(sizeof(struct flowlist));
                lp->graph=new;
                lp->next=g->in;
                g->in=lp;
            }else{
                struct flowlist *lp,*nl,**ls;
                new=mymalloc(sizeof(struct flowgraph));
                last->normalout=new;
                lic=mymalloc(ICS);
                new->start=new->end=lic;
                lic->code=LABEL;
                lic->typf=++label;
                lic->q1.flags=lic->q2.flags=lic->z.flags=0;
                lic->q1.am=lic->q2.am=lic->z.am=0;
                last->end->next=lic;    /*  kann nicht leer sein, da sonst branchout nicht 0 waere  */
                lic->prev=last->end;
                g->start->prev=lic;
                lic->next=g->start;
                lp=g->in;ls=&new->in;
                while(lp){
                    if(lp->graph&&lp->graph->index<g->index){
                    /*  Eintritt von oben soll in den Kopf  */
                        nl=mymalloc(sizeof(struct flowlist));
                        nl->graph=lp->graph;
                        nl->next=0;
                        (*ls)=nl;
                        ls=&nl->next;
                        if(lp->graph->branchout==g){
                            if(DEBUG&1024) printf("changing branch\n");
                            if(lp->graph->end->code<BEQ||lp->graph->end->code>BRA) ierror(0);
                            lp->graph->end->typf=lic->typf;
                            lp->graph->branchout=new;
                        }
                        lp->graph=new;
                    }
                    lp=lp->next;
                }
                if(!new->in) ierror(0);
            }
            if(new){
                if(DEBUG&1024) printf("must insert loop-header before block %d\n",g->index);
                basic_blocks++;
                new->branchout=0;
                new->loopend=0;
                new->index=-1;
                new->normalout=g;
                new->calls=0;
                new->loop_calls=0;
                new->rd_in=new->rd_out=new->rd_kill=new->rd_gen=0;
                new->ae_in=new->ae_out=new->ae_kill=new->ae_gen=0;
                new->cp_in=new->cp_out=new->cp_kill=new->cp_gen=0;
                new->av_in=mymalloc(vsize);
                new->av_out=mymalloc(vsize);
                new->av_gen=mymalloc(vsize);
                new->av_kill=mymalloc(vsize);
                memset(new->av_gen,0,vsize);
                memset(new->av_kill,0,vsize);
                memcpy(new->av_out,g->av_in,vsize);
                memcpy(new->av_in,g->av_in,vsize);
                memcpy(&new->regv,&g->regv,sizeof(new->regv));
                memcpy(&new->regused,&g->regused,sizeof(new->regused));
            }
        }
        last=g;
        g=g->normalout;
    }
    return(rg);
}
struct flowgraph *create_loop_footers(struct flowgraph *fg)
/*  fuegt hinter jede Schleife einen Austritts-Block ein, wenn noetig   */
/*  braucht aktive Variablen und kann einen Block mehrmals in der ->in  */
/*  Liste eintragen                                                     */
{
    struct flowgraph *g,*loopend,*out,*new;
    struct IC *lic;
    if(DEBUG&1024) printf("creating loop-footers\n");
    g=fg;
    while(g){
        new=0;
        loopend=g->loopend;
        if(loopend){
            struct flowlist *lp,*nl,**ls;
            out=loopend->normalout;
            new=mymalloc(sizeof(struct flowgraph));
            new->normalout=out;
            loopend->normalout=new;
            lic=mymalloc(ICS);
            new->start=new->end=lic;
            lic->code=LABEL;
            lic->typf=++label;
            lic->q1.flags=lic->q2.flags=lic->z.flags=0;
            lic->q1.am=lic->q2.am=lic->z.am=0;
            if(out) lp=out->in; else {lp=0;new->in=0;}
            ls=&new->in;
            while(lp){
                if(lp->graph&&lp->graph->index<=loopend->index&&lp->graph->index>=g->index){
                /*  Austritt aus Schleife soll in den Fuss  */
                    nl=mymalloc(sizeof(struct flowlist));
                    nl->graph=lp->graph;
                    nl->next=0;
                    (*ls)=nl;
                    ls=&nl->next;
                    if(lp->graph->branchout==out){
                        if(DEBUG&1024) printf("changing branch\n");
                        if(lp->graph->end->code<BEQ||lp->graph->end->code>BRA) ierror(0);
                        lp->graph->end->typf=lic->typf;
                        lp->graph->branchout=new;
                    }
                    lp->graph=new;
                }
                lp=lp->next;
            }
            if(out&&!new->in) ierror(0);
            if(DEBUG&1024) printf("must insert loop-footer after block %d\n",loopend->index);
            basic_blocks++;
            new->branchout=0;
            new->loopend=0;
            new->index=-2;
            new->normalout=out;
            new->calls=0;
            new->loop_calls=0;
            new->rd_in=new->rd_out=new->rd_kill=new->rd_gen=0;
            new->ae_in=new->ae_out=new->ae_kill=new->ae_gen=0;
            new->cp_in=new->cp_out=new->cp_kill=new->cp_gen=0;
            new->av_in=mymalloc(vsize);
            new->av_out=mymalloc(vsize);
            new->av_kill=mymalloc(vsize);
            new->av_gen=mymalloc(vsize);
            memset(new->av_gen,0,vsize);
            memset(new->av_kill,0,vsize);
            if(out){
                memcpy(new->av_out,out->av_in,vsize);
                memcpy(new->av_in,out->av_in,vsize);
            }else{
                memset(new->av_in,0,vsize);
                memset(new->av_out,0,vsize);
            }
            memcpy(&new->regv,&g->regv,sizeof(new->regv));
            memcpy(&new->regused,&g->regused,sizeof(new->regused));
            insert_IC_fg(new,loopend->end,lic);
        }
        g=g->normalout;
    }
    return(fg);
}