git.gag.com Git - fw/sdcc/blob - src/SDCCBBlock.c

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