PulkoMandy | 17fc759 | 2022-07-28 18:27:54 +0200 | [diff] [blame^] | 1 | /* $VER: vbcc (flow.c) $Revision: 1.13 $ */ |
| 2 | /* Generierung des FLussgraphs und Optimierungen des Kontrollflusses */ |
| 3 | |
| 4 | #include "opt.h" |
| 5 | |
| 6 | static char FILE_[]=__FILE__; |
| 7 | |
| 8 | int bvcmp(bvtype *dest,bvtype *src,size_t len) |
| 9 | /* vergleicht zwei Bitvektoren */ |
| 10 | { |
| 11 | len/=sizeof(bvtype); |
| 12 | for(;len>0;len--) |
| 13 | if(*dest++!=*src++) return(0); |
| 14 | return(1); |
| 15 | } |
| 16 | /* Schnittmenge nicht leer? */ |
| 17 | int bvdointersect(bvtype *p1,bvtype *p2,size_t len) |
| 18 | { |
| 19 | len/=sizeof(bvtype); |
| 20 | for(;len>0;len--) |
| 21 | if(*p1++&*p2++) |
| 22 | return 1; |
| 23 | return 0; |
| 24 | } |
| 25 | void bvunite(bvtype *dest,bvtype *src,size_t len) |
| 26 | /* berechnet Vereinigung zweier Bitvektoren */ |
| 27 | { |
| 28 | len/=sizeof(bvtype); |
| 29 | for(;len>0;len--) |
| 30 | *dest++|=*src++; |
| 31 | } |
| 32 | void bvintersect(bvtype *dest,bvtype *src,size_t len) |
| 33 | /* berechnet Durchschnitt zweier Bitvektoren */ |
| 34 | { |
| 35 | len/=sizeof(bvtype); |
| 36 | for(;len>0;len--) |
| 37 | *dest++&=*src++; |
| 38 | } |
| 39 | void bvdiff(bvtype *dest,bvtype *src,size_t len) |
| 40 | /* berechnet 'Differenz' zweier Bitvektoren */ |
| 41 | { |
| 42 | len/=sizeof(bvtype); |
| 43 | for(;len>0;len--) |
| 44 | *dest++&=~(*src++); |
| 45 | } |
| 46 | |
| 47 | unsigned int basic_blocks; |
| 48 | |
| 49 | flowgraph *new_flowgraph(void) |
| 50 | { |
| 51 | flowgraph *new; |
| 52 | new=mymalloc(sizeof(*new)); |
| 53 | new->av_in=new->av_out=new->av_gen=new->av_kill=0; |
| 54 | new->rd_in=new->rd_out=new->rd_gen=new->rd_kill=0; |
| 55 | new->ae_in=new->ae_out=new->ae_gen=new->ae_kill=0; |
| 56 | new->cp_in=new->cp_out=new->cp_gen=new->cp_kill=0; |
| 57 | new->pt=0; |
| 58 | new->start=new->end=0; |
| 59 | new->normalout=new->branchout=0; |
| 60 | new->in=0; |
| 61 | new->loopend=0; |
| 62 | #if ALEX_REG |
| 63 | new->loop_depth=0; |
| 64 | #endif |
| 65 | return new; |
| 66 | } |
| 67 | |
| 68 | flowgraph *construct_flowgraph(void) |
| 69 | /* entfernt ueberfluessige Labels und erzeugt Flussgraph */ |
| 70 | { |
| 71 | IC *p,*cl; |
| 72 | int firstl,lcnt,currentl,i,code,l; |
| 73 | int *iseq,*used; |
| 74 | flowgraph **lg,*g,*fg; |
| 75 | if(cross_module){ |
| 76 | int lastl; |
| 77 | firstl=0;lastl=0;lcnt=0; |
| 78 | for(p=first_ic;p;p=p->next){ |
| 79 | if(p->code==LABEL){ |
| 80 | if(p->typf<firstl) firstl=p->typf; |
| 81 | if(p->typf>lastl) lastl=p->typf; |
| 82 | } |
| 83 | } |
| 84 | lcnt=lastl-firstl+1; |
| 85 | }else{ |
| 86 | firstl=lastlabel; |
| 87 | lcnt=label-firstl; |
| 88 | } |
| 89 | return_label=0; |
| 90 | if(last_ic&&last_ic->code==LABEL) return_label=last_ic->typf; |
| 91 | if(last_ic&&last_ic->code==SETRETURN&&last_ic->prev&&last_ic->prev->code==LABEL) return_label=last_ic->prev->typf; |
| 92 | |
| 93 | iseq=mymalloc(lcnt*sizeof(int)); |
| 94 | used=mymalloc(lcnt*sizeof(int)); |
| 95 | lg=mymalloc(lcnt*sizeof(flowgraph *)); |
| 96 | g=new_flowgraph(); |
| 97 | fg=g; |
| 98 | g->start=first_ic;g->in=0;g->branchout=0;g->loopend=0; |
| 99 | |
| 100 | for(i=0;i<lcnt;i++) {iseq[i]=used[i]=0;lg[i]=0;} |
| 101 | currentl=0;firstl++; |
| 102 | /* Diese Schleife entfernt alle Labels, die mit anderen */ |
| 103 | /* uebereinstimmen, merkt sich das und kennzeichnet alle */ |
| 104 | /* Labels, die benutzt werden. */ |
| 105 | /* Ausserdem wird der Flussgraph teilweise aufgebaut. */ |
| 106 | if(DEBUG&1024) {puts("construct_flowgraph(): loop1");/*scanf("%d",&i);*/} |
| 107 | i=1;g->index=i; |
| 108 | for(p=first_ic;p;){ |
| 109 | code=p->code; |
| 110 | if(code>=BEQ&&code<=BRA){ |
| 111 | l=p->typf; |
| 112 | /* als used markieren; falls aequivalent, das erste markieren */ |
| 113 | if(iseq[l-firstl]) used[iseq[l-firstl]-firstl]=1; |
| 114 | else used[l-firstl]=1; |
| 115 | /* Flussgraph beenden und evtl. naechsten Knoten erzeugen */ |
| 116 | g->end=p; |
| 117 | if(p->next){ |
| 118 | g->normalout=new_flowgraph(); |
| 119 | g->normalout->in=mymalloc(sizeof(flowlist)); |
| 120 | g->normalout->in->next=0; |
| 121 | g->normalout->in->graph=g; |
| 122 | g=g->normalout; |
| 123 | g->start=p->next; |
| 124 | g->branchout=0; |
| 125 | g->loopend=0; |
| 126 | g->index=++i; |
| 127 | }else g->normalout=0; |
| 128 | |
| 129 | currentl=0;p=p->next;continue; |
| 130 | } |
| 131 | if(code==ALLOCREG||code==FREEREG){p=p->next; continue;} |
| 132 | if(code!=LABEL){currentl=0;p=p->next;continue;} |
| 133 | /* ist ein Label */ |
| 134 | l=p->typf; |
| 135 | if(currentl){ |
| 136 | IC *m; |
| 137 | iseq[l-firstl]=currentl; |
| 138 | if(l==return_label) return_label=currentl; |
| 139 | if(used[l-firstl]) used[currentl-firstl]=1; |
| 140 | cl->flags|=p->flags; |
| 141 | m=p;p=p->next; |
| 142 | remove_IC(m); |
| 143 | continue; |
| 144 | /* if(DEBUG&1024) printf("label %d==%d\n",l,iseq[l-firstl]);*/ |
| 145 | }else{ |
| 146 | currentl=l;cl=p; |
| 147 | if(g->start!=p){ |
| 148 | g->end=p->prev; |
| 149 | g->normalout=new_flowgraph(); |
| 150 | g->normalout->in=mymalloc(sizeof(flowlist)); |
| 151 | g->normalout->in->next=0; |
| 152 | g->normalout->in->graph=g; |
| 153 | g=g->normalout; |
| 154 | g->start=p; |
| 155 | g->branchout=0; |
| 156 | g->loopend=0; |
| 157 | g->index=++i; |
| 158 | }else g->branchout=0; |
| 159 | lg[l-firstl]=g; |
| 160 | } |
| 161 | p=p->next; |
| 162 | } |
| 163 | g->end=last_ic;g->normalout=g->branchout=0; |
| 164 | if(DEBUG&(16384|1024)) printf("%d basic blocks\n",i); |
| 165 | basic_blocks=i; |
| 166 | |
| 167 | /* if(DEBUG&1024) for(i=firstl;i<=lcnt;i++) printf("L%d used: %d\n",i,used[i-firstl]);*/ |
| 168 | /* Diese Schleife entfernt alle nicht benutzten Labels und biegt alle */ |
| 169 | /* Branches auf aequivalente Labels um. */ |
| 170 | if(DEBUG&1024) {puts("construct_flowgraph(): loop2");/*scanf("%d",&i);*/} |
| 171 | g=fg; |
| 172 | while(g){ |
| 173 | int flag=0;flowlist *lp; |
| 174 | /* printf("g=%p\n",(void *)g);*/ |
| 175 | g->av_in=g->av_out=g->av_gen=g->av_kill=0; |
| 176 | g->rd_in=g->rd_out=g->rd_gen=g->rd_kill=0; |
| 177 | g->ae_in=g->ae_out=g->ae_gen=g->ae_kill=0; |
| 178 | g->cp_in=g->cp_out=g->cp_gen=g->cp_kill=0; |
| 179 | g->pt=0; |
| 180 | p=g->start; |
| 181 | while(p&&!flag){ |
| 182 | /* pric2(stdout,p);*/ |
| 183 | code=p->code; |
| 184 | if(code>=BEQ&&code<=BRA){ |
| 185 | l=p->typf; |
| 186 | if(iseq[l-firstl]) p->typf=l=iseq[l-firstl]; |
| 187 | /* in Flussgraph eintragen */ |
| 188 | g->branchout=lg[l-firstl]; |
| 189 | if(!lg[l-firstl]) error(353); |
| 190 | lp=lg[l-firstl]->in; |
| 191 | /* das hier sollte man noch schoener machen */ |
| 192 | if(!lp){ |
| 193 | lg[l-firstl]->in=mymalloc(sizeof(flowlist)); |
| 194 | lg[l-firstl]->in->next=0; |
| 195 | lg[l-firstl]->in->graph=g; |
| 196 | }else{ |
| 197 | while(lp&&lp->next) lp=lp->next; |
| 198 | lp->next=mymalloc(sizeof(flowlist)); |
| 199 | lp->next->next=0; |
| 200 | lp->next->graph=g; |
| 201 | } |
| 202 | } |
| 203 | /* if(code==LABEL&&!used[p->typf-firstl]) remove_IC(p);*/ |
| 204 | if(p==g->end) flag=1; |
| 205 | p=p->next; |
| 206 | } |
| 207 | g=g->normalout; |
| 208 | } |
| 209 | /* Unbenutzte Labels entfernen und Bloecke verbinden */ |
| 210 | if(DEBUG&1024) {puts("construct_flowgraph(): loop3");/*scanf("%d",&i);*/} |
| 211 | for(g=fg;g;g=g->normalout){ |
| 212 | if(g->end&&(g->end->code<BEQ||g->end->code>BRA)){ |
| 213 | flowgraph *next=g->normalout;flowlist *lp; |
| 214 | if(next&&next->start&&next->start->code==LABEL&&!used[next->start->typf-firstl]){ |
| 215 | if(next->end!=next->start) g->end=next->end; |
| 216 | g->normalout=next->normalout; |
| 217 | g->branchout=next->branchout; |
| 218 | free(next->in); /* darf eigentlich nur einen Vorgaenger haben */ |
| 219 | /* in im Nachfolgeknoten auf den ersten der beiden setzen */ |
| 220 | if(next->normalout&&next->normalout->in) next->normalout->in->graph=g; |
| 221 | /* in im Ziel von next->branchout auf den ersten setzen */ |
| 222 | if(next->branchout){ |
| 223 | lp=next->branchout->in; |
| 224 | while(1){ |
| 225 | if(lp->graph==next){ lp->graph=g;break;} |
| 226 | lp=lp->next;if(!lp) ierror(0); |
| 227 | } |
| 228 | } |
| 229 | if(DEBUG&1024){ printf("unused label deleted:\n");pric2(stdout,next->start);} |
| 230 | remove_IC(next->start); |
| 231 | free(next); |
| 232 | } |
| 233 | } |
| 234 | /* unbenutzte Labels entfernen */ |
| 235 | if(g->start&&g->start->code==LABEL&&!used[g->start->typf-firstl]) |
| 236 | remove_IC_fg(g,g->start); |
| 237 | } |
| 238 | free(iseq); |
| 239 | free(used); |
| 240 | return(fg); |
| 241 | } |
| 242 | |
| 243 | void print_flowgraph(flowgraph *g) |
| 244 | /* Gibt Flussgraph auf Bildschirm aus */ |
| 245 | { |
| 246 | static int dontprint=0; |
| 247 | int flag,i;flowlist *lp;IC *ip; |
| 248 | if(dontprint>0) {dontprint--;return;} |
| 249 | if(dontprint!=-1){ |
| 250 | puts("print_flowgraph()");scanf("%d",&i); |
| 251 | if(i<-1){dontprint=-i;return;} |
| 252 | if(!i) return; |
| 253 | if(i==-1){dontprint=-1; i=1;} |
| 254 | }else{ |
| 255 | i=1; |
| 256 | } |
| 257 | while(g){ |
| 258 | printf("\nBasic Block nr. %d\n",g->index); |
| 259 | printf("\tin from "); |
| 260 | lp=g->in; |
| 261 | while(lp){if(lp->graph) printf("%d ",lp->graph->index);lp=lp->next;} |
| 262 | printf("\n\tout to %d %d\n",g->normalout?g->normalout->index:0,g->branchout?g->branchout->index:0); |
| 263 | if(g->loopend) printf("head of a loop ending at block %d\n",g->loopend->index); |
| 264 | if(!(optflags&32)&&g->pt) |
| 265 | ierror(0); |
| 266 | if(i&2){ |
| 267 | printf("av_gen:\n"); print_av(g->av_gen); |
| 268 | printf("av_kill:\n"); print_av(g->av_kill); |
| 269 | printf("av_in:\n"); print_av(g->av_in); |
| 270 | printf("av_out:\n"); print_av(g->av_out); |
| 271 | } |
| 272 | if(i&4){ |
| 273 | printf("rd_gen:\n"); print_rd(g->rd_gen); |
| 274 | printf("rd_kill:\n"); print_rd(g->rd_kill); |
| 275 | printf("rd_in:\n"); print_rd(g->rd_in); |
| 276 | printf("rd_out:\n"); print_rd(g->rd_out); |
| 277 | } |
| 278 | if(i&8){ |
| 279 | printf("ae_gen:\n"); print_ae(g->ae_gen); |
| 280 | printf("ae_kill:\n"); print_ae(g->ae_kill); |
| 281 | printf("ae_in:\n"); print_ae(g->ae_in); |
| 282 | printf("ae_out:\n"); print_ae(g->ae_out); |
| 283 | } |
| 284 | if(i&16){ |
| 285 | printf("cp_gen:\n"); print_cp(g->cp_gen); |
| 286 | printf("cp_kill:\n"); print_cp(g->cp_kill); |
| 287 | printf("cp_in:\n"); print_cp(g->cp_in); |
| 288 | printf("cp_out:\n"); print_cp(g->cp_out); |
| 289 | } |
| 290 | if(i&32){ |
| 291 | int r; |
| 292 | for(r=1;r<=MAXR;r++) |
| 293 | if(g->regv[r]) printf("(%s),%ld assigned to %s\n",g->regv[r]->identifier,(long)zm2l(g->regv[r]->offset),regnames[r]); |
| 294 | } |
| 295 | if(i&64){ |
| 296 | print_pt(g->pt); |
| 297 | } |
| 298 | flag=0;ip=g->start; |
| 299 | while(ip&&!flag){ |
| 300 | pric2(stdout,ip); |
| 301 | if(i&64){ |
| 302 | int r; |
| 303 | printf("changes: "); |
| 304 | for(r=0;r<ip->change_cnt;r++) |
| 305 | printf("(%s,%ld,%d,%d)",ip->change_list[r].v->identifier,(long)zm2l(ip->change_list[r].v->offset),ip->change_list[r].flags,ip->change_list[r].v->index); |
| 306 | printf("\nuses: "); |
| 307 | for(r=0;r<ip->use_cnt;r++) |
| 308 | printf("(%s,%ld,%d,%d)",ip->use_list[r].v->identifier,(long)zm2l(ip->use_list[r].v->offset),ip->use_list[r].flags,ip->use_list[r].v->index); |
| 309 | printf("\n"); |
| 310 | } |
| 311 | if(ip==g->end) flag=1; |
| 312 | ip=ip->next; |
| 313 | } |
| 314 | g=g->normalout; |
| 315 | } |
| 316 | printf("return_label=%d\n",return_label); |
| 317 | } |
| 318 | void free_flowgraph(flowgraph *g) |
| 319 | /* Gibt Flussgraph frei */ |
| 320 | { |
| 321 | flowgraph *pm;flowlist *lp,*lpm; |
| 322 | if(DEBUG&(16384|1024)) puts("free_flowgraph()"); |
| 323 | while(g){ |
| 324 | lp=g->in; |
| 325 | while(lp){ |
| 326 | lpm=lp->next; |
| 327 | free(lp); |
| 328 | lp=lpm; |
| 329 | } |
| 330 | free(g->av_in); |
| 331 | free(g->av_out); |
| 332 | free(g->av_gen); |
| 333 | free(g->av_kill); |
| 334 | free(g->rd_in); |
| 335 | free(g->rd_out); |
| 336 | free(g->rd_gen); |
| 337 | free(g->rd_kill); |
| 338 | free(g->ae_in); |
| 339 | free(g->ae_out); |
| 340 | free(g->ae_gen); |
| 341 | free(g->ae_kill); |
| 342 | free(g->cp_in); |
| 343 | free(g->cp_out); |
| 344 | free(g->cp_gen); |
| 345 | free(g->cp_kill); |
| 346 | free_pt(g->pt); |
| 347 | |
| 348 | pm=g->normalout; |
| 349 | free(g); |
| 350 | g=pm; |
| 351 | } |
| 352 | } |
| 353 | static void mark_reachable(flowgraph *fg) |
| 354 | /* negiert den index aller Bloecke, die reachable sind */ |
| 355 | { |
| 356 | fg->index=-fg->index; |
| 357 | if(fg->branchout&&fg->branchout->index>=0) |
| 358 | mark_reachable(fg->branchout); |
| 359 | if(fg->normalout&&(!fg->end||fg->end->code!=BRA)&&fg->normalout->index>=0) |
| 360 | mark_reachable(fg->normalout); |
| 361 | } |
| 362 | flowgraph *jump_optimization(void) |
| 363 | /* entfernt ueberfluessige Spruenge etc. */ |
| 364 | { |
| 365 | flowgraph *fg,*g;IC *p;int changed,i; |
| 366 | flowlist *lp; |
| 367 | do{ |
| 368 | changed=0; |
| 369 | fg=construct_flowgraph(); |
| 370 | mark_reachable(fg); |
| 371 | if(DEBUG&1024) {printf("jump_optimization() pass\n");print_flowgraph(fg);} |
| 372 | g=fg; |
| 373 | while(g){ |
| 374 | /* tote Bloecke entfernen */ |
| 375 | if(g->index<0){ |
| 376 | g->index=-g->index; |
| 377 | }else{ |
| 378 | IC *m; |
| 379 | if(DEBUG&1024) printf("deleting dead block %d\n",g->index); |
| 380 | #ifdef HAVE_MISRA |
| 381 | /* removed */ |
| 382 | #endif |
| 383 | p=g->start;i=0; |
| 384 | while(p&&!i){ |
| 385 | if(p==g->end) i=1; |
| 386 | if(DEBUG&1024) pric2(stdout,p); |
| 387 | m=p->next; |
| 388 | remove_IC_fg(g,p);changed=gchanged=1; |
| 389 | p=m; |
| 390 | } |
| 391 | if(g->branchout){ |
| 392 | /* Eintrag in Ziel loeschen (nur einmal, falls auch normalout) */ |
| 393 | lp=g->branchout->in; |
| 394 | while(lp){ |
| 395 | if(lp->graph==g){ lp->graph=0;break;} |
| 396 | lp=lp->next; |
| 397 | } |
| 398 | g->branchout=0; |
| 399 | } |
| 400 | g=g->normalout;continue; |
| 401 | } |
| 402 | /* Spruenge zum folgenden Code entfernen */ |
| 403 | if(g->normalout&&g->normalout==g->branchout){ |
| 404 | p=g->end; |
| 405 | if(!p||p->code<BEQ||p->code>BRA) ierror(0); |
| 406 | if(DEBUG&1024){printf("branch to following label deleted:\n");pric2(stdout,p);} |
| 407 | remove_IC_fg(g,p);g->branchout=0;changed=gchanged=1; |
| 408 | p=g->end; |
| 409 | /* vorangehenden Vergleich auch entfernen */ |
| 410 | if(p&&(p->code==COMPARE||p->code==TEST)){ |
| 411 | if(DEBUG&1024){printf("preceding comparison also deleted:\n");pric2(stdout,p);} |
| 412 | remove_IC_fg(g,p); |
| 413 | } |
| 414 | } |
| 415 | |
| 416 | /* bcc l1;bra l2;l1 aendern */ |
| 417 | p=g->end; |
| 418 | if(p&&p->code>=BEQ&&p->code<BRA&&g->normalout){ |
| 419 | if(g->normalout->start&&g->normalout->start->code==BRA){ |
| 420 | if(g->normalout->normalout==g->branchout){ |
| 421 | g->branchout=g->normalout->branchout; |
| 422 | i=p->typf; |
| 423 | p->typf=g->normalout->start->typf; |
| 424 | if(DEBUG&1024) printf("changing bcc l%d;bra l%d;l%d to b!cc l%d\n",i,p->typf,i,p->typf); |
| 425 | switch(p->code){ |
| 426 | case BEQ: p->code=BNE;break; |
| 427 | case BNE: p->code=BEQ;break; |
| 428 | case BLT: p->code=BGE;break; |
| 429 | case BGE: p->code=BLT;break; |
| 430 | case BGT: p->code=BLE;break; |
| 431 | case BLE: p->code=BGT;break; |
| 432 | } |
| 433 | g->normalout->branchout=g->normalout->normalout; |
| 434 | g->normalout->start->typf=i; |
| 435 | changed=gchanged=1; |
| 436 | } |
| 437 | } |
| 438 | } |
| 439 | /* Haben alle Vorgaenger eines Blocks die selbe Anweisung am */ |
| 440 | /* Blockende und keinen weiteren Nachfolger, dann kann die */ |
| 441 | /* Anweisung in den Nachfogerblock geschoben werden */ |
| 442 | i=0;p=0; |
| 443 | for(lp=g->in;lp;lp=lp->next){ |
| 444 | if(lp->graph){ |
| 445 | IC *np; |
| 446 | flowgraph *ng=lp->graph; |
| 447 | flowlist *l2; |
| 448 | /* doppelte Bloecke loeschen und ueberspringen */ |
| 449 | for(l2=g->in;l2;l2=l2->next) |
| 450 | if(l2!=lp&&l2->graph==ng) break; |
| 451 | if(l2){ lp->graph=0;continue;} |
| 452 | np=ng->end; |
| 453 | if(!np){ i=-1;break;} |
| 454 | if(ng->branchout&&(np->code!=BRA||ng->branchout!=g)){i=-1;break;} |
| 455 | if(np->code==BRA) np=np->prev; |
| 456 | if(!np){ i=-1;break;} |
| 457 | if(!p){ |
| 458 | i=1; |
| 459 | p=np; |
| 460 | }else{ |
| 461 | if(p->code==np->code&&p->typf==np->typf&& |
| 462 | p->code!=CALL&&p->code!=GETRETURN&&p->code!=PUSH&&(p->code<TEST||p->code>COMPARE)&& |
| 463 | !compare_objs(&p->q1,&np->q1,p->typf)&& |
| 464 | !compare_objs(&p->q2,&np->q2,p->typf)&& |
| 465 | !compare_objs(&p->z,&np->z,p->typf)){ |
| 466 | i++; |
| 467 | }else{ |
| 468 | i=-1; |
| 469 | break; |
| 470 | } |
| 471 | } |
| 472 | } |
| 473 | } |
| 474 | if(i>1&&g->start){ |
| 475 | IC *new=new_IC(); |
| 476 | if(DEBUG&1024){ printf("moving instruction from preceding blocks to successor:\n");pric2(stdout,p);} |
| 477 | changed=gchanged=1; |
| 478 | memcpy(new,p,ICS); |
| 479 | new->use_cnt=new->change_cnt=0; |
| 480 | new->use_list=new->change_list=0; |
| 481 | if(g->start->code==LABEL){ |
| 482 | insert_IC_fg(g,g->start,new); |
| 483 | }else{ |
| 484 | insert_IC_fg(g,g->start->prev,new); |
| 485 | } |
| 486 | for(lp=g->in;lp;lp=lp->next){ |
| 487 | flowgraph *ng=lp->graph; |
| 488 | if(ng){ |
| 489 | if(!ng->end) ierror(0); |
| 490 | if(ng->end->code==BRA){ |
| 491 | remove_IC_fg(ng,ng->end->prev); |
| 492 | }else{ |
| 493 | remove_IC_fg(ng,ng->end); |
| 494 | } |
| 495 | } |
| 496 | } |
| 497 | } |
| 498 | /* Haben alle Nachfolger eines Blocks die selbe Anweisung am */ |
| 499 | /* Blockbeginn und keinen weiteren Vorgaenger, dann kann die */ |
| 500 | /* Anweisung in den Vorgaengerblock geschoben werden */ |
| 501 | if(g->branchout&&g->normalout&&g->branchout!=g->normalout&&g->end&&g->end->code!=BRA){ |
| 502 | flowgraph *a=g->normalout,*b=g->branchout; |
| 503 | IC *as=a->start,*bs=b->start,*tp; |
| 504 | int destroys; |
| 505 | if(as&&as->code==LABEL&&as!=a->end) as=as->next; |
| 506 | if(bs&&bs->code==LABEL&&bs!=b->end) bs=bs->next; |
| 507 | |
| 508 | if(as&&bs&&as->code==bs->code&&as->code!=PUSH&&(as->code<TEST||as->code>COMPARE)&&as->typf==bs->typf&& |
| 509 | !compare_objs(&as->q1,&bs->q1,as->typf)&& |
| 510 | !compare_objs(&as->q2,&bs->q2,as->typf)&& |
| 511 | !compare_objs(&as->z,&bs->z,as->typf)){ |
| 512 | i=0; |
| 513 | for(lp=a->in;lp;lp=lp->next) |
| 514 | if(lp->graph&&lp->graph!=g&&(lp->graph->branchout==a||!lp->graph->end||lp->graph->end->code!=BRA)) i=1; |
| 515 | for(lp=b->in;lp;lp=lp->next) |
| 516 | if(lp->graph&&lp->graph!=g&&(lp->graph->branchout==b||!lp->graph->end||lp->graph->end->code!=BRA)) i=1; |
| 517 | if(as->code==CALL&&as->next&&(as->next->code==GETRETURN||as->code==NOP)) i=1; |
| 518 | if(bs->code==CALL&&bs->next&&(bs->next->code==GETRETURN||bs->code==NOP)) i=1; |
| 519 | if(!i){ |
| 520 | if(!(tp=g->end->prev)) ierror(0); |
| 521 | if(tp->code!=TEST&&tp->code!=COMPARE) |
| 522 | ierror(0); |
| 523 | /* schauen, ob die Anweisung eine evtl. TEST */ |
| 524 | /* oder COMPARE-Anweisung beeinflusst */ |
| 525 | destroys=0; |
| 526 | if(as->z.flags&DREFOBJ) destroys|=1; |
| 527 | if(as->code==CALL) destroys|=2; |
| 528 | if(tp->q1.flags&VAR){ |
| 529 | if(destroys&3){ |
| 530 | if((tp->q1.v->flags&USEDASADR)|| |
| 531 | (tp->q1.flags&DREFOBJ)|| |
| 532 | (tp->q1.v->storage_class==EXTERN)|| |
| 533 | (tp->q1.v->nesting==0)) |
| 534 | i=1; |
| 535 | if((destroys&2)&&tp->q1.v->storage_class==STATIC) |
| 536 | i=1; |
| 537 | } |
| 538 | if((as->z.flags&VAR)&&as->z.v==tp->q1.v) |
| 539 | i=1; |
| 540 | } |
| 541 | if(tp->q2.flags&VAR){ |
| 542 | if(destroys&3){ |
| 543 | if((tp->q2.v->flags&USEDASADR)|| |
| 544 | (tp->q2.flags&DREFOBJ)|| |
| 545 | (tp->q2.v->storage_class==EXTERN)|| |
| 546 | (tp->q2.v->nesting==0)) |
| 547 | i=1; |
| 548 | if((destroys&2)&&tp->q2.v->storage_class==STATIC) |
| 549 | i=1; |
| 550 | } |
| 551 | if((as->z.flags&VAR)&&as->z.v==tp->q2.v) |
| 552 | i=1; |
| 553 | } |
| 554 | if(!i&&!(disable&2)){ |
| 555 | if(DEBUG&1024){ printf("moving instruction from following blocks to predecessor:\n");pric2(stdout,as);} |
| 556 | p=new_IC(); |
| 557 | memcpy(p,as,ICS); |
| 558 | remove_IC_fg(a,as); |
| 559 | remove_IC_fg(b,bs); |
| 560 | p->use_cnt=p->change_cnt=0; |
| 561 | p->use_list=p->change_list=0; |
| 562 | insert_IC_fg(g,g->end->prev->prev,p); |
| 563 | changed=gchanged=1; |
| 564 | } |
| 565 | } |
| 566 | } |
| 567 | } |
| 568 | g=g->normalout; |
| 569 | } |
| 570 | g=fg; |
| 571 | while(g){ |
| 572 | /* Spruenge zu Spruengen umsetzen; einige Zeiger im Flussgraph */ |
| 573 | /* werden nicht korrekt aktualisiert, aber das sollte egal sein*/ |
| 574 | p=g->start; |
| 575 | for(i=0;i<2;i++){ |
| 576 | if(i){if(p&&p->code==LABEL) p=p->next; else break;} |
| 577 | if(p&&p->code>=BEQ&&p->code<=BRA){ |
| 578 | lp=g->in; |
| 579 | while(lp){ |
| 580 | if(lp->graph&&lp->graph->branchout==g&&(/*lp->graph->end->code==p->code||*/p->code==BRA)&&lp->graph->end->typf!=p->typf){ |
| 581 | if(DEBUG&1024){printf("branch bypassed to L%d:\n",p->typf);pric2(stdout,lp->graph->end);} |
| 582 | if(lp->graph->end->code<BEQ||lp->graph->end->code>BRA) ierror(0); |
| 583 | lp->graph->branchout=g->branchout; |
| 584 | lp->graph->end->typf=p->typf;changed=gchanged=1; |
| 585 | } |
| 586 | lp=lp->next; |
| 587 | } |
| 588 | } |
| 589 | } |
| 590 | |
| 591 | |
| 592 | g=g->normalout; |
| 593 | } |
| 594 | if(changed) free_flowgraph(fg); |
| 595 | }while(changed); |
| 596 | return fg; |
| 597 | } |
| 598 | |
| 599 | void insert_IC_fg(flowgraph *fg,IC *p,IC *new) |
| 600 | /* fuegt ein IC hinter p ein unter Beibehaltung des Flussgraphen */ |
| 601 | { |
| 602 | if(fg->start){ |
| 603 | if(!p||p==fg->start->prev) fg->start=new; |
| 604 | if(p==fg->end) fg->end=new; |
| 605 | }else{ |
| 606 | fg->start=fg->end=new; |
| 607 | } |
| 608 | insert_IC(p,new); |
| 609 | } |