git.gag.com Git - fw/sdcc/blob - src/SDCCBBlock.c

   1 /*-------------------------------------------------------------------------
   2
   3   SDCCBBlock.c - routines to manipulate basic Blocks
   4
   5              Written By -  Sandeep Dutta . sandeep.dutta@usa.net (1998)
   6
   7    This program is free software; you can redistribute it and/or modify it
   8    under the terms of the GNU General Public License as published by the
   9    Free Software Foundation; either version 2, or (at your option) any
  10    later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program; if not, write to the Free Software
  19    Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  20
  21    In other words, you are welcome to use, share and improve this program.
  22    You are forbidden to forbid anyone else to use, share and improve
  23    what you give them.   Help stamp out software-hoarding!
  24 -------------------------------------------------------------------------*/
  25
  26 #include "common.h"
  27
  28 int eBBNum = 0;
  29 set *graphEdges = NULL ;  /* list of edges in this flow graph */
  30 extern int labelKey ;
  31
  32 /*-----------------------------------------------------------------*/
  33 /* printEntryLabel - prints entry label of a ebblock               */
  34 /*-----------------------------------------------------------------*/
  35 DEFSETFUNC(printEntryLabel)
  36 {
  37     eBBlock *bp = item;
  38
  39     fprintf (stdout," %-20s ",bp->entryLabel->name);
  40     return 0;
  41 }
  42
  43 /*-----------------------------------------------------------------*/
  44 /* neweBBlock - allocate & return a new extended basic block       */
  45 /*-----------------------------------------------------------------*/
  46 eBBlock *neweBBlock ()
  47 {
  48     eBBlock *ebb;
  49
  50     ALLOC(ebb,sizeof(eBBlock));
  51     return ebb ;
  52 }
  53
  54 /*-----------------------------------------------------------------*/
  55 /* newEdge - allocates & initialises an edge to given values       */
  56 /*-----------------------------------------------------------------*/
  57 edge *newEdge (eBBlock *from, eBBlock *to)
  58 {
  59     edge *ep ;
  60
  61     ALLOC(ep,sizeof(edge));
  62
  63     ep->from = from;
  64     ep->to = to;
  65     return ep;
  66 }
  67
  68 /*-----------------------------------------------------------------*/
  69 /* dumpLiveRanges - dump liverange information into a file         */
  70 /*-----------------------------------------------------------------*/
  71 void dumpLiveRanges (char *ext,hTab *liveRanges)
  72 {
  73     FILE *file;
  74     symbol *sym;
  75     int k;
  76
  77     if (ext) {
  78         /* create the file name */
  79         strcpy(buffer,srcFileName);
  80         strcat(buffer,ext);
  81
  82         if (!(file = fopen(buffer,"a+"))) {
  83             werror(E_FILE_OPEN_ERR,buffer);
  84             exit(1);
  85         }
  86     } else
  87         file = stdout;
  88
  89     for (sym = hTabFirstItem(liveRanges,&k); sym ;
  90          sym = hTabNextItem(liveRanges,&k)) {
  91
  92         fprintf (file,"%s [k%d lr%d:%d so:%d]{ re%d rm%d}",
  93                  (sym->rname[0] ? sym->rname : sym->name),
  94                  sym->key,
  95                  sym->liveFrom,sym->liveTo,
  96                  sym->stack,
  97                  sym->isreqv,sym->remat
  98                  );
  99
 100         fprintf(file,"{"); printTypeChain(sym->type,file);
 101         if (sym->usl.spillLoc) {
 102             fprintf(file,"}{ sir@ %s",sym->usl.spillLoc->rname);
 103         }
 104         fprintf(file,"}");
 105
 106         /* if assigned to registers */
 107         if (sym->nRegs) {
 108             if (sym->isspilt) {
 109                 if (!sym->remat)
 110                     if (sym->usl.spillLoc)
 111                         fprintf(file,"[%s]",(sym->usl.spillLoc->rname[0] ?
 112                                              sym->usl.spillLoc->rname :
 113                                              sym->usl.spillLoc->name));
 114                     else
 115                         fprintf(file,"[err]");
 116                 else
 117                     fprintf(file,"[remat]");
 118             }
 119             else {
 120                 int i;
 121                 fprintf(file,"[");
 122                 for(i=0;i<sym->nRegs;i++)
 123                     fprintf(file,"%s ", port->getRegName(sym->regs[i]));
 124                 fprintf(file,"]");
 125             }
 126         }
 127         fprintf(file,"\n");
 128     }
 129
 130     fclose(file);
 131 }
 132 /*-----------------------------------------------------------------*/
 133 /* dumpEbbsToFileExt - writeall the basic blocks to a file         */
 134 /*-----------------------------------------------------------------*/
 135 void dumpEbbsToFileExt (char *ext,eBBlock **ebbs, int count)
 136 {
 137     FILE *of;
 138     int i;
 139
 140     if (ext) {
 141         /* create the file name */
 142         strcpy(buffer,srcFileName);
 143         strcat(buffer,ext);
 144
 145         if (!(of = fopen(buffer,"a+"))) {
 146             werror(E_FILE_OPEN_ERR,buffer);
 147             exit(1);
 148         }
 149     } else
 150         of = stdout;
 151
 152     for (i=0; i < count ; i++ ) {
 153         fprintf(of,"\n----------------------------------------------------------------\n");
 154         fprintf(of,"Basic Block %s : loop Depth = %d noPath = %d , lastinLoop = %d\n",
 155                 ebbs[i]->entryLabel->name,
 156                 ebbs[i]->depth,
 157                 ebbs[i]->noPath,
 158                 ebbs[i]->isLastInLoop);
 159         fprintf(of,"\ndefines bitVector :");
 160         bitVectDebugOn(ebbs[i]->defSet,of);
 161         fprintf(of,"\nlocal defines bitVector :");
 162         bitVectDebugOn(ebbs[i]->ldefs,of);
 163         fprintf(of,"\npointers Set bitvector :");
 164         bitVectDebugOn(ebbs[i]->ptrsSet,of);
 165         fprintf(of,"\n----------------------------------------------------------------\n");
 166         printiCChain(ebbs[i]->sch,of);
 167     }
 168     fclose(of);
 169 }
 170
 171 /*-----------------------------------------------------------------*/
 172 /* iCode2eBBlock - converts a sequnce till label to a ebb          */
 173 /*-----------------------------------------------------------------*/
 174 eBBlock *iCode2eBBlock (iCode *ic)
 175 {
 176     iCode *loop ;
 177     eBBlock *ebb = neweBBlock(); /* a llocate an entry */
 178
 179     /* put the first one unconditionally */
 180     ebb->sch = ic ;
 181
 182     /* if this is a label then */
 183     if (ic->op == LABEL)
 184         ebb->entryLabel = ic->argLabel.label ;
 185     else {
 186         sprintf(buffer,"_eBBlock%d",eBBNum++);
 187         ebb->entryLabel = newSymbol(buffer,1);
 188         ebb->entryLabel->key = labelKey++;
 189     }
 190
 191     if (ic &&
 192         ( ic->op == GOTO       ||
 193           ic->op == JUMPTABLE  ||
 194           ic->op == IFX        )) {
 195         ebb->ech = ebb->sch;
 196         return ebb;
 197     }
 198
 199     if ((ic->next && ic->next->op == LABEL) ||
 200         !ic->next ) {
 201         ebb->ech = ebb->sch ;
 202         return ebb ;
 203     }
 204
 205     /* loop thru till we find one with a label */
 206     for ( loop = ic->next ; loop ; loop = loop->next ) {
 207
 208         /* if this is the last one */
 209         if (!loop->next)
 210             break;
 211         /* if this is a function call */
 212         if (loop->op == CALL || loop->op == PCALL) {
 213             ebb->hasFcall = 1;
 214             if (currFunc)
 215                 currFunc->hasFcall = 1;
 216         }
 217
 218         /* if the next one is a label */
 219         /* if this is a goto or ifx */
 220         if (loop->next->op == LABEL ||
 221             loop->op == GOTO        ||
 222             loop->op == JUMPTABLE   ||
 223             loop->op == IFX )
 224             break ;
 225     }
 226
 227     /* mark the end of the chain */
 228     ebb->ech = loop ;
 229
 230     return ebb;
 231 }
 232
 233 /*-----------------------------------------------------------------*/
 234 /* eBBWithEntryLabel - finds the basic block with the entry label  */
 235 /*-----------------------------------------------------------------*/
 236 eBBlock *eBBWithEntryLabel ( eBBlock **ebbs , symbol *eLabel, int count)
 237 {
 238     int i;
 239
 240     for ( i = 0 ; i < count ; i++ ) {
 241         if (isSymbolEqual(ebbs[i]->entryLabel,eLabel))
 242             return ebbs[i] ;
 243     }
 244
 245     return NULL ;
 246 }
 247
 248
 249 /*-----------------------------------------------------------------*/
 250 /* ifFromIs - will return 1 if the from block matches this         */
 251 /*-----------------------------------------------------------------*/
 252 DEFSETFUNC(ifFromIs)
 253 {
 254     edge *ep = item;
 255     V_ARG(eBBlock *,this);
 256
 257     if (ep->from == this)
 258         return 1;
 259
 260     return 0;
 261 }
 262
 263
 264 /*-----------------------------------------------------------------*/
 265 /* edgesTo  - returns a set of edges with to == supplied value     */
 266 /*-----------------------------------------------------------------*/
 267 set *edgesTo ( eBBlock *to )
 268 {
 269     set *result = NULL ;
 270     edge *loop ;
 271
 272     for (loop = setFirstItem(graphEdges) ; loop ; loop = setNextItem(graphEdges))
 273         if (loop->to == to && !loop->from->noPath)
 274             addSet(&result,loop->from);
 275
 276     return result ;
 277 }
 278
 279
 280 /*-----------------------------------------------------------------*/
 281 /* addiCodeToeBBlock - will add an iCode to the end of a block     */
 282 /*-----------------------------------------------------------------*/
 283 void addiCodeToeBBlock ( eBBlock *ebp, iCode *ic , iCode *ip)
 284 {
 285     ic->prev = ic->next = NULL;
 286     /* if the insert point is given */
 287     if (ip) {
 288         ic->lineno = ip->lineno;
 289         ic->prev = ip->prev;
 290         ip->prev = ic;
 291         ic->next = ip;
 292         if (!ic->prev)
 293             ebp->sch = ic;
 294         else
 295             ic->prev->next = ic;
 296         return;
 297     }
 298
 299     /* if the block has no  instructions */
 300     if (ebp->ech == NULL ) {
 301         ebp->sch = ebp->ech = ic;
 302         ic->next = NULL;
 303         return ;
 304     }
 305
 306     /* if the last instruction is a goto */
 307     /* we add it just before the goto    */
 308     if ( ebp->ech->op == GOTO || ebp->ech->op == JUMPTABLE) {
 309         ic->lineno = ebp->ech->lineno;
 310         ic->prev = ebp->ech->prev;
 311         ebp->ech->prev = ic;
 312         ic->next = ebp->ech;
 313         if (!ic->prev) /* was the last only on in the block */
 314             ebp->sch = ic;
 315         else
 316             ic->prev->next = ic;
 317         return;
 318     }
 319
 320     /* if the last one was a ifx statement we check to see */
 321     /* if the condition was defined in the previous instruction */
 322     /* if this is true then we put it before the condition else */
 323     /* we put it before if, this is to reduce register pressure,*/
 324     /* we don't have to hold  condition too long in a register  */
 325     if ( ebp->ech->op == IFX ) {
 326         iCode *ipoint ;
 327
 328 /*      if ( !ebp->ech->prev )  */
 329 /*          ipoint = ebp->ech ; */
 330 /*      else  */
 331 /*          if (!IC_RESULT(ebp->ech->prev)) */
 332 /*              ipoint = ebp->ech ; */
 333 /*          else */
 334 /*              if (IC_COND(ebp->ech)->key == IC_RESULT(ebp->ech->prev)->key) */
 335 /*                  ipoint = ebp->ech->prev; */
 336 /*              else */
 337 /*                  ipoint = ebp->ech ; */
 338         ipoint = ebp->ech ;
 339         ic->lineno = ipoint->lineno;
 340         ic->prev = ipoint->prev;
 341         ipoint->prev = ic;
 342         ic->next = ipoint;
 343         if (!ic->prev)
 344             ebp->sch = ic;
 345         else
 346             ic->prev->next = ic;
 347         return;
 348     }
 349
 350     /* will add it to the very end */
 351     ip = ebp->ech;
 352     ip->next = ic;
 353     ic->prev = ip;
 354     ic->next = NULL;
 355     ebp->ech = ic;
 356
 357     return ;
 358 }
 359
 360 /*-----------------------------------------------------------------*/
 361 /* remiCodeFromeBBlock - remove an iCode from BBlock               */
 362 /*-----------------------------------------------------------------*/
 363 void remiCodeFromeBBlock (eBBlock *ebb, iCode *ic)
 364 {
 365     if (ic->prev)
 366         ic->prev->next = ic->next ;
 367     else
 368         ebb->sch = ic->next ;
 369
 370     if (ic->next)
 371         ic->next->prev = ic->prev;
 372     else
 373         ebb->ech = ic->prev;
 374 }
 375
 376 /*-----------------------------------------------------------------*/
 377 /* iCodeBreakDown : breakDown iCode chain to blocks                */
 378 /*-----------------------------------------------------------------*/
 379 eBBlock **iCodeBreakDown (iCode *ic, int *count)
 380 {
 381     eBBlock **ebbs = NULL ;
 382     iCode *loop = ic;
 383
 384     *count = 0 ;
 385
 386     /* allocate for the first entry */
 387     ALLOC(ebbs,sizeof(eBBlock **));
 388
 389     while (loop) {
 390
 391         /* convert 2 block */
 392         eBBlock *ebb = iCode2eBBlock(loop);
 393         loop = ebb->ech->next ;
 394
 395         ebb->ech->next = NULL ; /* mark the end of this chain */
 396         if (loop)
 397             loop->prev = NULL ;
 398         ebb->bbnum = *count ;    /* save this block number     */
 399         /* put it in the array */
 400         ebbs[(*count)++] = ebb ;
 401
 402         /* allocate for the next one */
 403         if (!(ebbs = GC_realloc(ebbs,(*count + 1)*sizeof(eBBlock **)))) {
 404             werror(E_OUT_OF_MEM,__FILE__,(*count + 1)*sizeof(eBBlock **));
 405             exit (1);
 406         }
 407
 408         /* if this one ends in a goto or a conditional */
 409         /* branch then check if the block it is going  */
 410         /* to already exists, if yes then this could   */
 411         /* be a loop, add a preheader to the block it  */
 412         /* goes to  if it does not already have one    */
 413         if (ebbs[(*count) - 1]->ech   &&
 414             (ebbs[(*count) - 1]->ech->op == GOTO ||
 415              ebbs[(*count) - 1]->ech->op == IFX )) {
 416
 417             symbol *label ;
 418             eBBlock *destBlock;
 419
 420             if (ebbs[(*count) - 1]->ech->op == GOTO)
 421                 label = IC_LABEL(ebbs[(*count)-1]->ech);
 422             else
 423                 if (!(label = IC_TRUE(ebbs[(*count)-1]->ech)))
 424                     label = IC_FALSE(ebbs[(*count)-1]->ech);
 425
 426             if ((destBlock = eBBWithEntryLabel(ebbs,label,(*count))) &&
 427                 destBlock->preHeader == NULL                         &&
 428                 otherPathsPresent(ebbs,destBlock) ) {
 429
 430                 symbol *preHeaderLabel = newiTempPreheaderLabel();
 431                 int i,j ;
 432                 eBBlock *pBlock ;
 433
 434                 /* go thru all block replacing the entryLabel with new label */
 435                 /* till we reach the block , then we insert a new ebblock    */
 436                 for ( i = 0 ; i < (*count) ; i++ ) {
 437                     if ( ebbs[i] == destBlock )
 438                         break ;
 439                     replaceLabel(ebbs[i],label,preHeaderLabel);
 440                 }
 441
 442                 (*count)++ ;
 443                 /* if we have stopped at the block , allocate for an extra one */
 444                 if (!(ebbs = GC_realloc(ebbs,(*count + 1)*sizeof(eBBlock **)))) {
 445                     werror(E_OUT_OF_MEM,__FILE__,(*count + 1)*sizeof(eBBlock **));
 446                     exit (1);
 447                 }
 448
 449                 /* then move the block down one count */
 450                 pBlock = ebbs[j = i];
 451                 for ( i += 1; i < (*count) ; i++ ) {
 452                     eBBlock *xBlock;
 453
 454                     xBlock = ebbs[i];
 455                     ebbs[i] = pBlock;
 456                     ebbs[i]->bbnum = i;
 457                     pBlock = xBlock ;
 458                 }
 459
 460                 destBlock->preHeader = ebbs[j] = neweBBlock();
 461                 ebbs[j]->bbnum = j;
 462                 ebbs[j]->entryLabel = preHeaderLabel ;
 463                 ebbs[j]->sch = ebbs[j]->ech = newiCodeLabelGoto(LABEL,preHeaderLabel);
 464                 ebbs[j]->sch->lineno = destBlock->sch->lineno;
 465             }
 466         }
 467     }
 468
 469     /* mark the end */
 470     ebbs[*count] = NULL ;
 471
 472     return ebbs ;
 473 }
 474
 475 /*-----------------------------------------------------------------*/
 476 /* replaceSymBySym : - replace operand by operand in blocks        */
 477 /*                     replaces only left & right in blocks        */
 478 /*-----------------------------------------------------------------*/
 479  void replaceSymBySym (set *sset, operand *src, operand *dest)
 480 {
 481     set *loop ;
 482     eBBlock *rBlock ;
 483
 484     /* for all blocks in the set do */
 485     for ( loop = sset ; loop ; loop = loop->next) {
 486         iCode *ic ;
 487
 488         rBlock = loop->item ;
 489         /* for all instructions in this block do */
 490         for ( ic = rBlock->sch ; ic ; ic = ic->next ) {
 491
 492             /* if we find usage */
 493             if (ic->op == IFX && isOperandEqual(src,IC_COND(ic))) {
 494                 bitVectUnSetBit (OP_USES(IC_COND(ic)),ic->key);
 495                 IC_COND(ic) = operandFromOperand(dest);
 496                 OP_USES(dest) = bitVectSetBit (OP_USES(dest),ic->key);
 497                 continue ;
 498             }
 499
 500             if (isOperandEqual(IC_RIGHT(ic),src)) {
 501                 bitVectUnSetBit (OP_USES(IC_RIGHT(ic)),ic->key);
 502                 IC_RIGHT(ic) = operandFromOperand(dest);
 503                 IC_RIGHT(ic)->isaddr = 0;
 504                 OP_USES(dest) = bitVectSetBit (OP_USES(dest),ic->key);
 505             }
 506
 507             if (isOperandEqual(IC_LEFT(ic),src)) {
 508                 bitVectUnSetBit (OP_USES(IC_LEFT(ic)),ic->key);
 509                 if (POINTER_GET(ic) && IS_ITEMP(dest)) {
 510                     IC_LEFT(ic) = operandFromOperand(dest);
 511                     IC_LEFT(ic)->isaddr = 1;
 512                 } else {
 513                     IC_LEFT(ic) = operandFromOperand(dest);
 514                     IC_LEFT(ic)->isaddr = 0;
 515                 }
 516                 OP_USES(dest) = bitVectSetBit (OP_USES(dest),ic->key);
 517             }
 518
 519             /* special case for pointer sets */
 520             if (POINTER_SET(ic) &&
 521                 isOperandEqual(IC_RESULT(ic),src)) {
 522                 bitVectUnSetBit (OP_USES(IC_RESULT(ic)),ic->key);
 523                 IC_RESULT(ic) = operandFromOperand(dest);
 524                 IC_RESULT(ic)->isaddr = 1;
 525                 OP_USES(dest) = bitVectSetBit(OP_USES(dest),ic->key);
 526             }
 527         }
 528     }
 529 }
 530
 531 /*-----------------------------------------------------------------*/
 532 /* replaceLabel - replace reference to one label by another        */
 533 /*-----------------------------------------------------------------*/
 534  void replaceLabel(eBBlock *ebp, symbol *fromLbl, symbol *toLbl)
 535 {
 536     iCode *ic;
 537
 538     if (!ebp)
 539         return ;
 540
 541     for (ic = ebp->sch ; ic ; ic = ic->next ) {
 542         switch (ic->op) {
 543
 544         case GOTO :
 545             if (isSymbolEqual(IC_LABEL(ic),fromLbl))
 546                 IC_LABEL(ic) = toLbl;
 547             break;
 548
 549         case IFX:
 550             if (IC_TRUE(ic) && isSymbolEqual(IC_TRUE(ic),fromLbl))
 551                 IC_TRUE(ic) = toLbl ;
 552             else
 553                 if (isSymbolEqual(IC_FALSE(ic),fromLbl))
 554                     IC_FALSE(ic) = toLbl;
 555             break;
 556         }
 557     }
 558
 559     return;
 560
 561 }
 562
 563
 564 /*-----------------------------------------------------------------*/
 565 /* iCodeFromeBBlock - convert basic block to iCode chain           */
 566 /*-----------------------------------------------------------------*/
 567 iCode *iCodeFromeBBlock ( eBBlock **ebbs, int count)
 568 {
 569     int i = 1 ;
 570     iCode *ric = ebbs[0]->sch ;
 571     iCode *lic = ebbs[0]->ech ;
 572
 573     for ( ; i < count; i++ ) {
 574         if ( ebbs[i]->sch == NULL)
 575             continue ;
 576
 577         if ( ebbs[i]->noPath &&
 578              (ebbs[i]->entryLabel != entryLabel &&
 579               ebbs[i]->entryLabel != returnLabel )) {
 580             werror(W_CODE_UNREACH,ebbs[i]->sch->filename,ebbs[i]->sch->lineno);
 581             continue ;
 582         }
 583
 584         lic->next = ebbs[i]->sch ;
 585         lic->next->prev = lic;
 586         lic = ebbs[i]->ech ;
 587     }
 588
 589     return ric;
 590 }
 591
 592 /*-----------------------------------------------------------------*/
 593 /* otherPathsPresent - determines if there is a path from _entry   */
 594 /*      to this block in a half constructed set of blocks          */
 595 /*-----------------------------------------------------------------*/
 596 int otherPathsPresent (eBBlock **ebbs, eBBlock *this)
 597 {
 598     int i ;
 599
 600     /* for all blocks preceding this block */
 601     for ( i = 0 ; i < this->bbnum ; i++ ) {
 602         iCode *ic ;
 603
 604         /* if there is a reference to the entry label of this block */
 605         for ( ic = ebbs[i]->sch ; ic ; ic = ic->next ) {
 606             switch (ic->op) {
 607             case GOTO :
 608                 if (IC_LABEL(ic)->key == this->entryLabel->key)
 609                     return 1;
 610                 break;
 611
 612             case IFX :
 613                 if (IC_TRUE(ic)) {
 614                     if (IC_TRUE(ic)->key == this->entryLabel->key)
 615                         return 1;
 616                 } else
 617                     if (IC_FALSE(ic)->key == this->entryLabel->key)
 618                         return 1 ;
 619                 break;
 620             }
 621         }
 622     }
 623
 624     /* comes here means we have not found it yet */
 625     /* in this case check if the previous block  */
 626     /* ends in a goto if it does then we have no */
 627     /* path else we have a path                  */
 628     if (this->bbnum && ebbs[this->bbnum - 1]->ech &&
 629         ebbs[this->bbnum - 1]->ech->op == GOTO )
 630         return 0;
 631     else
 632         return 1;
 633 }
 634