/* $VER: vbcc (loop.c) V0.8 *//* schleifenorientierte Optimierungen */ #include "opt.h" static char FILE_[]=__FILE__; #define MOVE_IC 1#define MOVE_COMP 2 /* Liste, in die ICs eingetragen werden, die aus Schleifen *//* gezogen werden sollen. */struct movlist{ struct movlist *next; struct IC *IC; struct flowgraph *target_fg; int flags;}; struct movlist *first_mov,*last_mov; int report_weird_code,report_suspicious_loops; /* Bitvektoren fuer schleifeninvariante ICs */bvtype *invariant,*inloop,*moved,*moved_completely;bvtype *fg_tmp;bvtype *not_movable;size_t bsize; /* Liste, in die ICs fuer strength-reduction eingetragen *//* werden. */struct srlist{ struct srlist *next; struct IC *ind_var; struct IC *IC; struct flowgraph *target_fg; /* Hilfsvariable, falls eine aequivalente Operation schon reduziert */ /* wurde. */ struct Var *hv;}; struct srlist *first_sr,*last_sr; /* Liste, in die Daten fuer loop-unrolling eingetragen werden. */struct urlist{ int flags; long total,unroll; struct IC *cmp,*branch,*ind; struct flowgraph *start,*head; struct urlist *next;} *first_ur; #define UNROLL_COMPLETELY 1#define UNROLL_MODULO 2#define UNROLL_INVARIANT 4#define UNROLL_REVERSE 8#define IND_ONLY_COUNTS 16#define MULTIPLE_EXITS 32 /* Hier werden Induktionsvariablen vermerkt */struct IC **ind_vars; static struct flowgraph *first_fg; #ifdef ALEX_REGvoid IncrementLoopDepth(struct flowgraph* fg,int start,int end) /* erhoeht loop_depth in den Bloecken [start,end] */{ if ( (fg->index >= start) && (fg->index <= end) ) { fg->loop_depth++; } if (fg->normalout) IncrementLoopDepth(fg->normalout,start,end);}#endif int 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,c=0;struct flowlist *lp;struct flowgraph *g,*loopend; if(DEBUG&1024) printf("searching loops\n"); g=fg; while(g){ start=g->index; end=-1; for(lp=g->in;lp;lp=lp->next){ if(!lp->graph) continue; 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; } } } 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(1/*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&&footers){ i=p->branchout->index; if(i<start){ 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 */ if(p!=g){ for(lp=p->in;lp;lp=lp->next){ if(!lp->graph) continue; if(lp->graph->branchout==p){ i=lp->graph->index; if(i<start){ if(report_weird_code){error(175);report_weird_code=0;} end=-1; break; } if(i>end){ end=-1; break; } } } } if(p->index==end) break; p=p->normalout; }while(end>=0); }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; c++;#ifdef ALEX_REG IncrementLoopDepth(fg,start,end);#endif } g=g->normalout; } return c;} struct flowgraph *create_loop_headers(struct flowgraph *fg,int av)/* Fuegt vor jede Schleife einen Kopf-Block ein, wenn noetig. *//* Wenn av!=0 werden aktive Variablen korrekt uebertragen und *//* diverse Registerlisten uebernommen und index=-1 gesetzt. *//* Kann einen Block mehrmals in der ->in Liste eintragen */{ struct flowgraph *g,*last,*new,*rg=fg; struct IC *lic,*lastic; if(DEBUG&1024) printf("creating loop-headers\n"); g=fg;last=0;lastic=0; while(g){ new=0; if(g->loopend){ if(!last){ struct flowlist *lp; new=new_flowgraph(); rg=new; new->in=0; lic=new_IC(); 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; new->start=new->end=lic; lic->next=first_ic; lic->prev=0; first_ic->prev=lic; first_ic=lic; lp=mymalloc(sizeof(struct flowlist)); lp->graph=new; lp->next=g->in; g->in=lp; }else{ struct flowlist *lp,*nl,**ls; new=new_flowgraph(); last->normalout=new; lic=new_IC(); 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(lastic) lastic->next=lic; else first_ic=lic; lic->prev=lastic; 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){ struct IC *p=lp->graph->end; if(DEBUG&1024) printf("changing branch\n"); while(p&&p->code==FREEREG) p=p->prev; if(!p||p->code<BEQ||p->code>BRA) ierror(0); p->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; if(av) new->index=-1; else new->index=basic_blocks; 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; if(!av){ new->av_in=new->av_out=new->av_kill=new->av_gen=0; }else{ 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;if(last->end) lastic=last->end; g=g->normalout; } return rg;}struct flowgraph *create_loop_footers(struct flowgraph *fg,int av)/* Fuegt hinter jede Schleife einen Fuss-Block ein, wenn noetig. *//* Wenn av!=0 werden aktive Variablen korrekt uebertragen und *//* diverse Registerlisten uebernommen und index auf -2 gesetzt. */{ 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=new_flowgraph(); new->normalout=out; loopend->normalout=new; lic=new_IC(); lic->line=0; lic->file=0; 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; lic->use_cnt=lic->change_cnt=0; lic->use_list=lic->change_list=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){ struct IC *p=lp->graph->end; if(DEBUG&1024) printf("changing branch\n"); while(p&&p->code==FREEREG) p=p->prev; if(!p||p->code<BEQ||p->code>BRA) ierror(0); p->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; if(av) new->index=-2; else new->index=basic_blocks; 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; if(!av){ new->av_in=new->av_out=new->av_kill=new->av_gen=0; }else{ 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{ memcpy(new->av_out,av_globals,vsize); bvunite(new->av_out,av_statics,vsize); memcpy(new->av_in,new->av_out,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;}void add_movable(struct IC *p,struct flowgraph *fg,int flags)/* Fuegt IC p, das aus der Schleife in Block fg mit Flags flags *//* verschoben werden darf in eine Liste. */{ struct movlist *new=mymalloc(sizeof(*new)); new->IC=p; new->target_fg=fg; new->flags=flags; new->next=0; if(last_mov){ last_mov->next=new; last_mov=new; }else{ first_mov=last_mov=new; } BSET(moved,p->defindex); if(flags==MOVE_IC) BSET(moved_completely,p->defindex);}int move_to_head(void)/* Geht die Liste mit verschiebbaren ICs durch und schiebt die ICs *//* in den Vorkopf der Schleife. Ausserdem wird die Liste *//* freigegeben. *//* Der Rueckgabewert hat Bit 1 gesetzt, wenn ICs ganz verschoben *//* wurden und Bit 2, falls eine Berechnung mit Hilfsvariable vor *//* die Schleife gezogen wurde. */{ struct IC **fglist; /* Letztes IC vor jedem Block */ struct flowgraph *g;struct IC *p;struct movlist *m; int changed=0; if(!first_mov) return 0; if(DEBUG&1024) printf("moving the ICs out of the loop\n"); fglist=mymalloc((basic_blocks+1)*sizeof(*fglist)); p=0; for(g=first_fg;g;g=g->normalout){ if(g->index>basic_blocks) ierror(0); if(g->end) p=g->end; fglist[g->index]=p; } while(first_mov){ p=first_mov->IC; g=first_mov->target_fg; if(first_mov->flags==MOVE_IC){ if(DEBUG&1024) {printf("moving IC out of loop:\n");pric2(stdout,p);} if(!p->prev||!p->next) ierror(0); p->next->prev=p->prev; p->prev->next=p->next; insert_IC_fg(g,fglist[g->index],p); fglist[g->index]=p; changed|=1; }else if(1){ struct Typ *t=new_typ(); struct IC *new=new_IC(); struct Var *v; if(DEBUG&1024) {printf("moving computation out of loop:\n");pric2(stdout,p);} t->flags=ztyp(p); if(p->code==COMPARE||p->code==TEST) t->flags=0; if(ISPOINTER(t->flags)){ t->next=new_typ(); t->next->flags=VOID; } v=add_tmp_var(t); *new=*p; new->z.flags=VAR; new->z.v=v; new->z.val.vmax=l2zm(0L); /* Die neue Operation benutzt maximal, was die andere benutzte */ /* und aendert nur die Hilfsvariable. */ if(have_alias){ new->use_cnt=p->use_cnt; new->use_list=mymalloc(new->use_cnt*VLS); memcpy(new->use_list,p->use_list,new->use_cnt*VLS); new->change_cnt=1; new->change_list=mymalloc(VLS); new->change_list[0].v=v; new->change_list[0].flags=0; } insert_IC_fg(g,fglist[g->index],new); fglist[g->index]=new; p->code=ASSIGN; p->typf=t->flags; p->q1.flags=VAR; p->q1.v=v; p->q1.val.vmax=l2zm(0L); p->q2.flags=0; p->q2.val.vmax=szof(t); /* Die Operation in der Schleife benutzt nun zusaetzlich */ /* noch die Hilfsvariable. */ if(have_alias){ void *m=p->use_list; p->use_cnt++; p->use_list=mymalloc(p->use_cnt*VLS); memcpy(&p->use_list[1],m,(p->use_cnt-1)*VLS); free(m); p->use_list[0].v=v; p->use_list[0].flags=0; } changed|=2; } m=first_mov->next; free(first_mov); first_mov=m; } if(DEBUG&1024) print_flowgraph(first_fg); free(fglist); return changed;}void calc_movable(struct flowgraph *start,struct flowgraph *end)/* Berechnet, welche Definitionen nicht aus der Schleife start-end *//* verschoben werden duerfen. Eine Def. p von z darf nur verschoben *//* werden, wenn keine andere Def. von p existiert und alle *//* Verwendungen von z nur von p erreicht werden. *//* Benutzt rd_defs. */{ struct flowgraph *g;struct IC *p; int i,j,k,d; bvtype *changed_vars; if(DEBUG&1024) printf("calculating not_movable for blocks %d to %d\n",start->index,end->index); if(0/*!(optflags&1024)*/){ memset(not_movable,UCHAR_MAX,dsize); return; } memset(not_movable,0,dsize); changed_vars=mymalloc(vsize); memset(changed_vars,0,vsize); for(i=0;i<vcount-rcount;i++){ if(vilist[i]->vtyp->flags&VOLATILE) BSET(changed_vars,i); if(i<rcount){ if(!vilist[i]->vtyp->next||(vilist[i]->vtyp->next->flags&VOLATILE)) BSET(changed_vars,i+vcount-rcount); } } for(g=start;g;g=g->normalout){ if(!g->rd_in) ierror(0); memcpy(rd_defs,g->rd_in,dsize); for(p=g->start;p;p=p->next){ 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;Lines 1–500 of 1922. Load more
/* $VER: vbcc (loop.c) V0.8 */ /* schleifenorientierte Optimierungen */ #include "opt.h" static char FILE_[]=__FILE__; #define MOVE_IC 1 #define MOVE_COMP 2 /* Liste, in die ICs eingetragen werden, die aus Schleifen */ /* gezogen werden sollen. */ struct movlist{ struct movlist *next; struct IC *IC; struct flowgraph *target_fg; int flags; }; struct movlist *first_mov,*last_mov; int report_weird_code,report_suspicious_loops; /* Bitvektoren fuer schleifeninvariante ICs */ bvtype *invariant,*inloop,*moved,*moved_completely; bvtype *fg_tmp; bvtype *not_movable; size_t bsize; /* Liste, in die ICs fuer strength-reduction eingetragen */ /* werden. */ struct srlist{ struct srlist *next; struct IC *ind_var; struct IC *IC; struct flowgraph *target_fg; /* Hilfsvariable, falls eine aequivalente Operation schon reduziert */ /* wurde. */ struct Var *hv; }; struct srlist *first_sr,*last_sr; /* Liste, in die Daten fuer loop-unrolling eingetragen werden. */ struct urlist{ int flags; long total,unroll; struct IC *cmp,*branch,*ind; struct flowgraph *start,*head; struct urlist *next; } *first_ur; #define UNROLL_COMPLETELY 1 #define UNROLL_MODULO 2 #define UNROLL_INVARIANT 4 #define UNROLL_REVERSE 8 #define IND_ONLY_COUNTS 16 #define MULTIPLE_EXITS 32 /* Hier werden Induktionsvariablen vermerkt */ struct IC **ind_vars; static struct flowgraph *first_fg; #ifdef ALEX_REG void IncrementLoopDepth(struct flowgraph* fg,int start,int end) /* erhoeht loop_depth in den Bloecken [start,end] */ { if ( (fg->index >= start) && (fg->index <= end) ) { fg->loop_depth++; } if (fg->normalout) IncrementLoopDepth(fg->normalout,start,end); } #endif int 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,c=0;struct flowlist *lp;struct flowgraph *g,*loopend; if(DEBUG&1024) printf("searching loops\n"); g=fg; while(g){ start=g->index; end=-1; for(lp=g->in;lp;lp=lp->next){ if(!lp->graph) continue; 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; } } } 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(1/*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&&footers){ i=p->branchout->index; if(i<start){ 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 */ if(p!=g){ for(lp=p->in;lp;lp=lp->next){ if(!lp->graph) continue; if(lp->graph->branchout==p){ i=lp->graph->index; if(i<start){ if(report_weird_code){error(175);report_weird_code=0;} end=-1; break; } if(i>end){ end=-1; break; } } } } if(p->index==end) break; p=p->normalout; }while(end>=0); }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; c++; #ifdef ALEX_REG IncrementLoopDepth(fg,start,end); #endif } g=g->normalout; } return c; } struct flowgraph *create_loop_headers(struct flowgraph *fg,int av) /* Fuegt vor jede Schleife einen Kopf-Block ein, wenn noetig. */ /* Wenn av!=0 werden aktive Variablen korrekt uebertragen und */ /* diverse Registerlisten uebernommen und index=-1 gesetzt. */ /* Kann einen Block mehrmals in der ->in Liste eintragen */ { struct flowgraph *g,*last,*new,*rg=fg; struct IC *lic,*lastic; if(DEBUG&1024) printf("creating loop-headers\n"); g=fg;last=0;lastic=0; while(g){ new=0; if(g->loopend){ if(!last){ struct flowlist *lp; new=new_flowgraph(); rg=new; new->in=0; lic=new_IC(); 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; new->start=new->end=lic; lic->next=first_ic; lic->prev=0; first_ic->prev=lic; first_ic=lic; lp=mymalloc(sizeof(struct flowlist)); lp->graph=new; lp->next=g->in; g->in=lp; }else{ struct flowlist *lp,*nl,**ls; new=new_flowgraph(); last->normalout=new; lic=new_IC(); 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(lastic) lastic->next=lic; else first_ic=lic; lic->prev=lastic; 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){ struct IC *p=lp->graph->end; if(DEBUG&1024) printf("changing branch\n"); while(p&&p->code==FREEREG) p=p->prev; if(!p||p->code<BEQ||p->code>BRA) ierror(0); p->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; if(av) new->index=-1; else new->index=basic_blocks; 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; if(!av){ new->av_in=new->av_out=new->av_kill=new->av_gen=0; }else{ 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;if(last->end) lastic=last->end; g=g->normalout; } return rg; } struct flowgraph *create_loop_footers(struct flowgraph *fg,int av) /* Fuegt hinter jede Schleife einen Fuss-Block ein, wenn noetig. */ /* Wenn av!=0 werden aktive Variablen korrekt uebertragen und */ /* diverse Registerlisten uebernommen und index auf -2 gesetzt. */ { 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=new_flowgraph(); new->normalout=out; loopend->normalout=new; lic=new_IC(); lic->line=0; lic->file=0; 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; lic->use_cnt=lic->change_cnt=0; lic->use_list=lic->change_list=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){ struct IC *p=lp->graph->end; if(DEBUG&1024) printf("changing branch\n"); while(p&&p->code==FREEREG) p=p->prev; if(!p||p->code<BEQ||p->code>BRA) ierror(0); p->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; if(av) new->index=-2; else new->index=basic_blocks; 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; if(!av){ new->av_in=new->av_out=new->av_kill=new->av_gen=0; }else{ 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{ memcpy(new->av_out,av_globals,vsize); bvunite(new->av_out,av_statics,vsize); memcpy(new->av_in,new->av_out,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; } void add_movable(struct IC *p,struct flowgraph *fg,int flags) /* Fuegt IC p, das aus der Schleife in Block fg mit Flags flags */ /* verschoben werden darf in eine Liste. */ { struct movlist *new=mymalloc(sizeof(*new)); new->IC=p; new->target_fg=fg; new->flags=flags; new->next=0; if(last_mov){ last_mov->next=new; last_mov=new; }else{ first_mov=last_mov=new; } BSET(moved,p->defindex); if(flags==MOVE_IC) BSET(moved_completely,p->defindex); } int move_to_head(void) /* Geht die Liste mit verschiebbaren ICs durch und schiebt die ICs */ /* in den Vorkopf der Schleife. Ausserdem wird die Liste */ /* freigegeben. */ /* Der Rueckgabewert hat Bit 1 gesetzt, wenn ICs ganz verschoben */ /* wurden und Bit 2, falls eine Berechnung mit Hilfsvariable vor */ /* die Schleife gezogen wurde. */ { struct IC **fglist; /* Letztes IC vor jedem Block */ struct flowgraph *g;struct IC *p;struct movlist *m; int changed=0; if(!first_mov) return 0; if(DEBUG&1024) printf("moving the ICs out of the loop\n"); fglist=mymalloc((basic_blocks+1)*sizeof(*fglist)); p=0; for(g=first_fg;g;g=g->normalout){ if(g->index>basic_blocks) ierror(0); if(g->end) p=g->end; fglist[g->index]=p; } while(first_mov){ p=first_mov->IC; g=first_mov->target_fg; if(first_mov->flags==MOVE_IC){ if(DEBUG&1024) {printf("moving IC out of loop:\n");pric2(stdout,p);} if(!p->prev||!p->next) ierror(0); p->next->prev=p->prev; p->prev->next=p->next; insert_IC_fg(g,fglist[g->index],p); fglist[g->index]=p; changed|=1; }else if(1){ struct Typ *t=new_typ(); struct IC *new=new_IC(); struct Var *v; if(DEBUG&1024) {printf("moving computation out of loop:\n");pric2(stdout,p);} t->flags=ztyp(p); if(p->code==COMPARE||p->code==TEST) t->flags=0; if(ISPOINTER(t->flags)){ t->next=new_typ(); t->next->flags=VOID; } v=add_tmp_var(t); *new=*p; new->z.flags=VAR; new->z.v=v; new->z.val.vmax=l2zm(0L); /* Die neue Operation benutzt maximal, was die andere benutzte */ /* und aendert nur die Hilfsvariable. */ if(have_alias){ new->use_cnt=p->use_cnt; new->use_list=mymalloc(new->use_cnt*VLS); memcpy(new->use_list,p->use_list,new->use_cnt*VLS); new->change_cnt=1; new->change_list=mymalloc(VLS); new->change_list[0].v=v; new->change_list[0].flags=0; } insert_IC_fg(g,fglist[g->index],new); fglist[g->index]=new; p->code=ASSIGN; p->typf=t->flags; p->q1.flags=VAR; p->q1.v=v; p->q1.val.vmax=l2zm(0L); p->q2.flags=0; p->q2.val.vmax=szof(t); /* Die Operation in der Schleife benutzt nun zusaetzlich */ /* noch die Hilfsvariable. */ if(have_alias){ void *m=p->use_list; p->use_cnt++; p->use_list=mymalloc(p->use_cnt*VLS); memcpy(&p->use_list[1],m,(p->use_cnt-1)*VLS); free(m); p->use_list[0].v=v; p->use_list[0].flags=0; } changed|=2; } m=first_mov->next; free(first_mov); first_mov=m; } if(DEBUG&1024) print_flowgraph(first_fg); free(fglist); return changed; } void calc_movable(struct flowgraph *start,struct flowgraph *end) /* Berechnet, welche Definitionen nicht aus der Schleife start-end */ /* verschoben werden duerfen. Eine Def. p von z darf nur verschoben */ /* werden, wenn keine andere Def. von p existiert und alle */ /* Verwendungen von z nur von p erreicht werden. */ /* Benutzt rd_defs. */ { struct flowgraph *g;struct IC *p; int i,j,k,d; bvtype *changed_vars; if(DEBUG&1024) printf("calculating not_movable for blocks %d to %d\n",start->index,end->index); if(0/*!(optflags&1024)*/){ memset(not_movable,UCHAR_MAX,dsize); return; } memset(not_movable,0,dsize); changed_vars=mymalloc(vsize); memset(changed_vars,0,vsize); for(i=0;i<vcount-rcount;i++){ if(vilist[i]->vtyp->flags&VOLATILE) BSET(changed_vars,i); if(i<rcount){ if(!vilist[i]->vtyp->next||(vilist[i]->vtyp->next->flags&VOLATILE)) BSET(changed_vars,i+vcount-rcount); } } for(g=start;g;g=g->normalout){ if(!g->rd_in) ierror(0); memcpy(rd_defs,g->rd_in,dsize); for(p=g->start;p;p=p->next){ 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;