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