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