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       || 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     ALLOC(ebbs,sizeof(eBBlock **));
 390
 391     while (loop) {
 392
 393         /* convert 2 block */
 394         eBBlock *ebb = iCode2eBBlock(loop);
 395         loop = ebb->ech->next ;
 396
 397         ebb->ech->next = NULL ; /* mark the end of this chain */
 398         if (loop)
 399             loop->prev = NULL ;
 400         ebb->bbnum = *count ;    /* save this block number     */
 401         /* put it in the array */
 402         ebbs[(*count)++] = ebb ;
 403
 404         /* allocate for the next one */
 405         if (!(ebbs = GC_realloc(ebbs,(*count + 1)*sizeof(eBBlock **)))) {
 406             werror(E_OUT_OF_MEM,__FILE__,(*count + 1)*sizeof(eBBlock **));
 407             exit (1);
 408         }
 409
 410         /* if this one ends in a goto or a conditional */
 411         /* branch then check if the block it is going  */
 412         /* to already exists, if yes then this could   */
 413         /* be a loop, add a preheader to the block it  */
 414         /* goes to  if it does not already have one    */
 415         if (ebbs[(*count) - 1]->ech   &&
 416             (ebbs[(*count) - 1]->ech->op == GOTO ||
 417              ebbs[(*count) - 1]->ech->op == IFX )) {
 418
 419             symbol *label ;
 420             eBBlock *destBlock;
 421
 422             if (ebbs[(*count) - 1]->ech->op == GOTO)
 423                 label = IC_LABEL(ebbs[(*count)-1]->ech);
 424             else
 425                 if (!(label = IC_TRUE(ebbs[(*count)-1]->ech)))
 426                     label = IC_FALSE(ebbs[(*count)-1]->ech);
 427
 428             if ((destBlock = eBBWithEntryLabel(ebbs,label,(*count))) &&
 429                 destBlock->preHeader == NULL                         &&
 430                 otherPathsPresent(ebbs,destBlock) ) {
 431
 432                 symbol *preHeaderLabel = newiTempPreheaderLabel();
 433                 int i,j ;
 434                 eBBlock *pBlock ;
 435
 436                 /* go thru all block replacing the entryLabel with new label */
 437                 /* till we reach the block , then we insert a new ebblock    */
 438                 for ( i = 0 ; i < (*count) ; i++ ) {
 439                     if ( ebbs[i] == destBlock )
 440                         break ;
 441                     replaceLabel(ebbs[i],label,preHeaderLabel);
 442                 }
 443
 444                 (*count)++ ;
 445                 /* if we have stopped at the block , allocate for an extra one */
 446                 if (!(ebbs = GC_realloc(ebbs,(*count + 1)*sizeof(eBBlock **)))) {
 447                     werror(E_OUT_OF_MEM,__FILE__,(*count + 1)*sizeof(eBBlock **));
 448                     exit (1);
 449                 }
 450
 451                 /* then move the block down one count */
 452                 pBlock = ebbs[j = i];
 453                 for ( i += 1; i < (*count) ; i++ ) {
 454                     eBBlock *xBlock;
 455
 456                     xBlock = ebbs[i];
 457                     ebbs[i] = pBlock;
 458                     ebbs[i]->bbnum = i;
 459                     pBlock = xBlock ;
 460                 }
 461
 462                 destBlock->preHeader = ebbs[j] = neweBBlock();
 463                 ebbs[j]->bbnum = j;
 464                 ebbs[j]->entryLabel = preHeaderLabel ;
 465                 ebbs[j]->sch = ebbs[j]->ech = newiCodeLabelGoto(LABEL,preHeaderLabel);
 466                 ebbs[j]->sch->lineno = destBlock->sch->lineno;
 467             }
 468         }
 469     }
 470
 471     /* mark the end */
 472     ebbs[*count] = NULL ;
 473
 474     return ebbs ;
 475 }
 476
 477 /*-----------------------------------------------------------------*/
 478 /* replaceSymBySym : - replace operand by operand in blocks        */
 479 /*                     replaces only left & right in blocks        */
 480 /*-----------------------------------------------------------------*/
 481  void replaceSymBySym (set *sset, operand *src, operand *dest)
 482 {
 483     set *loop ;
 484     eBBlock *rBlock ;
 485
 486     /* for all blocks in the set do */
 487     for ( loop = sset ; loop ; loop = loop->next) {
 488         iCode *ic ;
 489
 490         rBlock = loop->item ;
 491         /* for all instructions in this block do */
 492         for ( ic = rBlock->sch ; ic ; ic = ic->next ) {
 493
 494             /* if we find usage */
 495             if (ic->op == IFX && isOperandEqual(src,IC_COND(ic))) {
 496                 bitVectUnSetBit (OP_USES(IC_COND(ic)),ic->key);
 497                 IC_COND(ic) = operandFromOperand(dest);
 498                 OP_USES(dest) = bitVectSetBit (OP_USES(dest),ic->key);
 499                 continue ;
 500             }
 501
 502             if (isOperandEqual(IC_RIGHT(ic),src)) {
 503                 bitVectUnSetBit (OP_USES(IC_RIGHT(ic)),ic->key);
 504                 IC_RIGHT(ic) = operandFromOperand(dest);
 505                 IC_RIGHT(ic)->isaddr = 0;
 506                 OP_USES(dest) = bitVectSetBit (OP_USES(dest),ic->key);
 507             }
 508
 509             if (isOperandEqual(IC_LEFT(ic),src)) {
 510                 bitVectUnSetBit (OP_USES(IC_LEFT(ic)),ic->key);
 511                 if (POINTER_GET(ic) && IS_ITEMP(dest)) {
 512                     IC_LEFT(ic) = operandFromOperand(dest);
 513                     IC_LEFT(ic)->isaddr = 1;
 514                 } else {
 515                     IC_LEFT(ic) = operandFromOperand(dest);
 516                     IC_LEFT(ic)->isaddr = 0;
 517                 }
 518                 OP_USES(dest) = bitVectSetBit (OP_USES(dest),ic->key);
 519             }
 520
 521             /* special case for pointer sets */
 522             if (POINTER_SET(ic) &&
 523                 isOperandEqual(IC_RESULT(ic),src)) {
 524                 bitVectUnSetBit (OP_USES(IC_RESULT(ic)),ic->key);
 525                 IC_RESULT(ic) = operandFromOperand(dest);
 526                 IC_RESULT(ic)->isaddr = 1;
 527                 OP_USES(dest) = bitVectSetBit(OP_USES(dest),ic->key);
 528             }
 529         }
 530     }
 531 }
 532
 533 /*-----------------------------------------------------------------*/
 534 /* replaceLabel - replace reference to one label by another        */
 535 /*-----------------------------------------------------------------*/
 536  void replaceLabel(eBBlock *ebp, symbol *fromLbl, symbol *toLbl)
 537 {
 538     iCode *ic;
 539
 540     if (!ebp)
 541         return ;
 542
 543     for (ic = ebp->sch ; ic ; ic = ic->next ) {
 544         switch (ic->op) {
 545
 546         case GOTO :
 547             if (isSymbolEqual(IC_LABEL(ic),fromLbl))
 548                 IC_LABEL(ic) = toLbl;
 549             break;
 550
 551         case IFX:
 552             if (IC_TRUE(ic) && isSymbolEqual(IC_TRUE(ic),fromLbl))
 553                 IC_TRUE(ic) = toLbl ;
 554             else
 555                 if (isSymbolEqual(IC_FALSE(ic),fromLbl))
 556                     IC_FALSE(ic) = toLbl;
 557             break;
 558         }
 559     }
 560
 561     return;
 562
 563 }
 564
 565
 566 /*-----------------------------------------------------------------*/
 567 /* iCodeFromeBBlock - convert basic block to iCode chain           */
 568 /*-----------------------------------------------------------------*/
 569 iCode *iCodeFromeBBlock ( eBBlock **ebbs, int count)
 570 {
 571     int i = 1 ;
 572     iCode *ric = ebbs[0]->sch ;
 573     iCode *lic = ebbs[0]->ech ;
 574
 575     for ( ; i < count; i++ ) {
 576         if ( ebbs[i]->sch == NULL)
 577             continue ;
 578
 579         if ( ebbs[i]->noPath &&
 580              (ebbs[i]->entryLabel != entryLabel &&
 581               ebbs[i]->entryLabel != returnLabel )) {
 582             werror(W_CODE_UNREACH,ebbs[i]->sch->filename,ebbs[i]->sch->lineno);
 583             continue ;
 584         }
 585
 586         lic->next = ebbs[i]->sch ;
 587         lic->next->prev = lic;
 588         lic = ebbs[i]->ech ;
 589     }
 590
 591     return ric;
 592 }
 593
 594 /*-----------------------------------------------------------------*/
 595 /* otherPathsPresent - determines if there is a path from _entry   */
 596 /*      to this block in a half constructed set of blocks          */
 597 /*-----------------------------------------------------------------*/
 598 int otherPathsPresent (eBBlock **ebbs, eBBlock *this)
 599 {
 600     int i ;
 601
 602     /* for all blocks preceding this block */
 603     for ( i = 0 ; i < this->bbnum ; i++ ) {
 604         iCode *ic ;
 605
 606         /* if there is a reference to the entry label of this block */
 607         for ( ic = ebbs[i]->sch ; ic ; ic = ic->next ) {
 608             switch (ic->op) {
 609             case GOTO :
 610                 if (IC_LABEL(ic)->key == this->entryLabel->key)
 611                     return 1;
 612                 break;
 613
 614             case IFX :
 615                 if (IC_TRUE(ic)) {
 616                     if (IC_TRUE(ic)->key == this->entryLabel->key)
 617                         return 1;
 618                 } else
 619                     if (IC_FALSE(ic)->key == this->entryLabel->key)
 620                         return 1 ;
 621                 break;
 622             }
 623         }
 624     }
 625
 626     /* comes here means we have not found it yet */
 627     /* in this case check if the previous block  */
 628     /* ends in a goto if it does then we have no */
 629     /* path else we have a path                  */
 630     if (this->bbnum && ebbs[this->bbnum - 1]->ech &&
 631         ebbs[this->bbnum - 1]->ech->op == GOTO )
 632         return 0;
 633     else
 634         return 1;
 635 }
 636