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