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 #include "newalloc.h"
  28
  29 int eBBNum = 0;
  30 set *graphEdges = NULL ;  /* list of edges in this flow graph */
  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     ebb = Safe_calloc(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     ep = Safe_calloc(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       || ebp->ech->op == RETURN)
 310     {
 311         ic->lineno = ebp->ech->lineno;
 312         ic->prev = ebp->ech->prev;
 313         ebp->ech->prev = ic;
 314         ic->next = ebp->ech;
 315         if (!ic->prev) /* was the last only on in the block */
 316             ebp->sch = ic;
 317         else
 318             ic->prev->next = ic;
 319         return;
 320     }
 321
 322     /* if the last one was a ifx statement we check to see */
 323     /* if the condition was defined in the previous instruction */
 324     /* if this is true then we put it before the condition else */
 325     /* we put it before if, this is to reduce register pressure,*/
 326     /* we don't have to hold  condition too long in a register  */
 327     if ( ebp->ech->op == IFX ) {
 328         iCode *ipoint ;
 329
 330 /*      if ( !ebp->ech->prev )  */
 331 /*          ipoint = ebp->ech ; */
 332 /*      else  */
 333 /*          if (!IC_RESULT(ebp->ech->prev)) */
 334 /*              ipoint = ebp->ech ; */
 335 /*          else */
 336 /*              if (IC_COND(ebp->ech)->key == IC_RESULT(ebp->ech->prev)->key) */
 337 /*                  ipoint = ebp->ech->prev; */
 338 /*              else */
 339 /*                  ipoint = ebp->ech ; */
 340         ipoint = ebp->ech ;
 341         ic->lineno = ipoint->lineno;
 342         ic->prev = ipoint->prev;
 343         ipoint->prev = ic;
 344         ic->next = ipoint;
 345         if (!ic->prev)
 346             ebp->sch = ic;
 347         else
 348             ic->prev->next = ic;
 349         return;
 350     }
 351
 352     /* will add it to the very end */
 353     ip = ebp->ech;
 354     ip->next = ic;
 355     ic->prev = ip;
 356     ic->next = NULL;
 357     ebp->ech = ic;
 358
 359     return ;
 360 }
 361
 362 /*-----------------------------------------------------------------*/
 363 /* remiCodeFromeBBlock - remove an iCode from BBlock               */
 364 /*-----------------------------------------------------------------*/
 365 void remiCodeFromeBBlock (eBBlock *ebb, iCode *ic)
 366 {
 367     if (ic->prev)
 368         ic->prev->next = ic->next ;
 369     else
 370         ebb->sch = ic->next ;
 371
 372     if (ic->next)
 373         ic->next->prev = ic->prev;
 374     else
 375         ebb->ech = ic->prev;
 376 }
 377
 378 /*-----------------------------------------------------------------*/
 379 /* iCodeBreakDown : breakDown iCode chain to blocks                */
 380 /*-----------------------------------------------------------------*/
 381 eBBlock **iCodeBreakDown (iCode *ic, int *count)
 382 {
 383     eBBlock **ebbs = NULL ;
 384     iCode *loop = ic;
 385
 386     *count = 0 ;
 387
 388     /* allocate for the first entry */
 389
 390     ebbs = Safe_calloc(sizeof(eBBlock **));
 391
 392     while (loop) {
 393
 394         /* convert 2 block */
 395         eBBlock *ebb = iCode2eBBlock(loop);
 396         loop = ebb->ech->next ;
 397
 398         ebb->ech->next = NULL ; /* mark the end of this chain */
 399         if (loop)
 400             loop->prev = NULL ;
 401         ebb->bbnum = *count ;    /* save this block number     */
 402         /* put it in the array */
 403         ebbs[(*count)++] = ebb ;
 404
 405         /* allocate for the next one. Remember to clear the new */
 406         /*  pointer at the end, that was created by realloc. */
 407
 408         ebbs = Safe_realloc(ebbs,(*count + 1)*sizeof(eBBlock **)) ;
 409
 410         ebbs[*count] = 0;
 411
 412         /* if this one ends in a goto or a conditional */
 413         /* branch then check if the block it is going  */
 414         /* to already exists, if yes then this could   */
 415         /* be a loop, add a preheader to the block it  */
 416         /* goes to  if it does not already have one    */
 417         if (ebbs[(*count) - 1]->ech   &&
 418             (ebbs[(*count) - 1]->ech->op == GOTO ||
 419              ebbs[(*count) - 1]->ech->op == IFX )) {
 420
 421             symbol *label ;
 422             eBBlock *destBlock;
 423
 424             if (ebbs[(*count) - 1]->ech->op == GOTO)
 425                 label = IC_LABEL(ebbs[(*count)-1]->ech);
 426             else
 427                 if (!(label = IC_TRUE(ebbs[(*count)-1]->ech)))
 428                     label = IC_FALSE(ebbs[(*count)-1]->ech);
 429
 430             if ((destBlock = eBBWithEntryLabel(ebbs,label,(*count))) &&
 431                 destBlock->preHeader == NULL                         &&
 432                 otherPathsPresent(ebbs,destBlock) ) {
 433
 434                 symbol *preHeaderLabel = newiTempPreheaderLabel();
 435                 int i,j ;
 436                 eBBlock *pBlock ;
 437
 438                 /* go thru all block replacing the entryLabel with new label */
 439                 /* till we reach the block , then we insert a new ebblock    */
 440                 for ( i = 0 ; i < (*count) ; i++ ) {
 441                     if ( ebbs[i] == destBlock )
 442                         break ;
 443                     replaceLabel(ebbs[i],label,preHeaderLabel);
 444                 }
 445
 446                 (*count)++ ;
 447
 448                 /* if we have stopped at the block , allocate for an extra one */
 449
 450                 ebbs = Safe_realloc(ebbs,(*count + 1)*sizeof(eBBlock **)) ;
 451
 452                 ebbs[*count] = 0;
 453
 454                 /* then move the block down one count */
 455                 pBlock = ebbs[j = i];
 456                 for ( i += 1; i < (*count) ; i++ ) {
 457                     eBBlock *xBlock;
 458
 459                     xBlock = ebbs[i];
 460                     ebbs[i] = pBlock;
 461                     ebbs[i]->bbnum = i;
 462                     pBlock = xBlock ;
 463                 }
 464
 465                 destBlock->preHeader = ebbs[j] = neweBBlock();
 466                 ebbs[j]->bbnum = j;
 467                 ebbs[j]->entryLabel = preHeaderLabel ;
 468                 ebbs[j]->sch = ebbs[j]->ech = newiCodeLabelGoto(LABEL,preHeaderLabel);
 469                 ebbs[j]->sch->lineno = destBlock->sch->lineno;
 470             }
 471         }
 472     }
 473
 474     /* mark the end */
 475     ebbs[*count] = NULL ;
 476
 477     return ebbs ;
 478 }
 479
 480 /*-----------------------------------------------------------------*/
 481 /* replaceSymBySym : - replace operand by operand in blocks        */
 482 /*                     replaces only left & right in blocks        */
 483 /*-----------------------------------------------------------------*/
 484  void replaceSymBySym (set *sset, operand *src, operand *dest)
 485 {
 486     set *loop ;
 487     eBBlock *rBlock ;
 488
 489     /* for all blocks in the set do */
 490     for ( loop = sset ; loop ; loop = loop->next) {
 491         iCode *ic ;
 492
 493         rBlock = loop->item ;
 494         /* for all instructions in this block do */
 495         for ( ic = rBlock->sch ; ic ; ic = ic->next ) {
 496
 497             /* if we find usage */
 498             if (ic->op == IFX && isOperandEqual(src,IC_COND(ic))) {
 499                 bitVectUnSetBit (OP_USES(IC_COND(ic)),ic->key);
 500                 IC_COND(ic) = operandFromOperand(dest);
 501                 OP_USES(dest) = bitVectSetBit (OP_USES(dest),ic->key);
 502                 continue ;
 503             }
 504
 505             if (isOperandEqual(IC_RIGHT(ic),src)) {
 506                 bitVectUnSetBit (OP_USES(IC_RIGHT(ic)),ic->key);
 507                 IC_RIGHT(ic) = operandFromOperand(dest);
 508                 IC_RIGHT(ic)->isaddr = 0;
 509                 OP_USES(dest) = bitVectSetBit (OP_USES(dest),ic->key);
 510             }
 511
 512             if (isOperandEqual(IC_LEFT(ic),src)) {
 513                 bitVectUnSetBit (OP_USES(IC_LEFT(ic)),ic->key);
 514                 if (POINTER_GET(ic) && IS_ITEMP(dest)) {
 515                     IC_LEFT(ic) = operandFromOperand(dest);
 516                     IC_LEFT(ic)->isaddr = 1;
 517                 } else {
 518                     IC_LEFT(ic) = operandFromOperand(dest);
 519                     IC_LEFT(ic)->isaddr = 0;
 520                 }
 521                 OP_USES(dest) = bitVectSetBit (OP_USES(dest),ic->key);
 522             }
 523
 524             /* special case for pointer sets */
 525             if (POINTER_SET(ic) &&
 526                 isOperandEqual(IC_RESULT(ic),src)) {
 527                 bitVectUnSetBit (OP_USES(IC_RESULT(ic)),ic->key);
 528                 IC_RESULT(ic) = operandFromOperand(dest);
 529                 IC_RESULT(ic)->isaddr = 1;
 530                 OP_USES(dest) = bitVectSetBit(OP_USES(dest),ic->key);
 531             }
 532         }
 533     }
 534 }
 535
 536 /*-----------------------------------------------------------------*/
 537 /* replaceLabel - replace reference to one label by another        */
 538 /*-----------------------------------------------------------------*/
 539  void replaceLabel(eBBlock *ebp, symbol *fromLbl, symbol *toLbl)
 540 {
 541     iCode *ic;
 542
 543     if (!ebp)
 544         return ;
 545
 546     for (ic = ebp->sch ; ic ; ic = ic->next ) {
 547         switch (ic->op) {
 548
 549         case GOTO :
 550             if (isSymbolEqual(IC_LABEL(ic),fromLbl))
 551                 IC_LABEL(ic) = toLbl;
 552             break;
 553
 554         case IFX:
 555             if (IC_TRUE(ic) && isSymbolEqual(IC_TRUE(ic),fromLbl))
 556                 IC_TRUE(ic) = toLbl ;
 557             else
 558                 if (isSymbolEqual(IC_FALSE(ic),fromLbl))
 559                     IC_FALSE(ic) = toLbl;
 560             break;
 561         }
 562     }
 563
 564     return;
 565
 566 }
 567
 568
 569 /*-----------------------------------------------------------------*/
 570 /* iCodeFromeBBlock - convert basic block to iCode chain           */
 571 /*-----------------------------------------------------------------*/
 572 iCode *iCodeFromeBBlock ( eBBlock **ebbs, int count)
 573 {
 574     int i = 1 ;
 575     iCode *ric = ebbs[0]->sch ;
 576     iCode *lic = ebbs[0]->ech ;
 577
 578     for ( ; i < count; i++ ) {
 579         if ( ebbs[i]->sch == NULL)
 580             continue ;
 581
 582         if ( ebbs[i]->noPath &&
 583              (ebbs[i]->entryLabel != entryLabel &&
 584               ebbs[i]->entryLabel != returnLabel )) {
 585             werror(W_CODE_UNREACH,ebbs[i]->sch->filename,ebbs[i]->sch->lineno);
 586             continue ;
 587         }
 588
 589         lic->next = ebbs[i]->sch ;
 590         lic->next->prev = lic;
 591         lic = ebbs[i]->ech ;
 592     }
 593
 594     return ric;
 595 }
 596
 597 /*-----------------------------------------------------------------*/
 598 /* otherPathsPresent - determines if there is a path from _entry   */
 599 /*      to this block in a half constructed set of blocks          */
 600 /*-----------------------------------------------------------------*/
 601 int otherPathsPresent (eBBlock **ebbs, eBBlock *this)
 602 {
 603     int i ;
 604
 605     /* for all blocks preceding this block */
 606     for ( i = 0 ; i < this->bbnum ; i++ ) {
 607         iCode *ic ;
 608
 609         /* if there is a reference to the entry label of this block */
 610         for ( ic = ebbs[i]->sch ; ic ; ic = ic->next ) {
 611             switch (ic->op) {
 612             case GOTO :
 613                 if (IC_LABEL(ic)->key == this->entryLabel->key)
 614                     return 1;
 615                 break;
 616
 617             case IFX :
 618                 if (IC_TRUE(ic)) {
 619                     if (IC_TRUE(ic)->key == this->entryLabel->key)
 620                         return 1;
 621                 } else
 622                     if (IC_FALSE(ic)->key == this->entryLabel->key)
 623                         return 1 ;
 624                 break;
 625             }
 626         }
 627     }
 628
 629     /* comes here means we have not found it yet */
 630     /* in this case check if the previous block  */
 631     /* ends in a goto if it does then we have no */
 632     /* path else we have a path                  */
 633     if (this->bbnum && ebbs[this->bbnum - 1]->ech &&
 634         ebbs[this->bbnum - 1]->ech->op == GOTO )
 635         return 0;
 636     else
 637         return 1;
 638 }
 639