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. Remember to clear the new */
 404           /*  pointer at the end, that was created by realloc. */
 405         if (!(ebbs = realloc(ebbs,(*count + 1)*sizeof(eBBlock **)))) {
 406             werror(E_OUT_OF_MEM,__FILE__,(*count + 1)*sizeof(eBBlock **));
 407             exit (1);
 408         }
 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                 /* if we have stopped at the block , allocate for an extra one */
 448                 if (!(ebbs = realloc(ebbs,(*count + 1)*sizeof(eBBlock **)))) {
 449                     werror(E_OUT_OF_MEM,__FILE__,(*count + 1)*sizeof(eBBlock **));
 450                     exit (1);
 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