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 #include "newalloc.h"
  28
  29 int eBBNum = 0;
  30 set *graphEdges = NULL ;  /* list of edges in this flow graph */
  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     ebb = Safe_calloc(1,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     ep = Safe_calloc(1,sizeof(edge));
  62
  63     ep->from = from;
  64     ep->to = to;
  65     return ep;
  66 }
  67
  68 /*-----------------------------------------------------------------*/
  69 /* dumpLiveRanges - dump liverange information into a file         */
  70 /*-----------------------------------------------------------------*/
  71 void dumpLiveRanges (char *ext,hTab *liveRanges)
  72 {
  73     FILE *file;
  74     symbol *sym;
  75     int k;
  76
  77     if (ext) {
  78   /* create the file name */
  79   strcpy(buffer,srcFileName);
  80   strcat(buffer,ext);
  81
  82   if (!(file = fopen(buffer,"a+"))) {
  83       werror(E_FILE_OPEN_ERR,buffer);
  84       exit(1);
  85   }
  86     } else
  87   file = stdout;
  88
  89     for (sym = hTabFirstItem(liveRanges,&k); sym ;
  90    sym = hTabNextItem(liveRanges,&k)) {
  91
  92   fprintf (file,"%s [k%d lr%d:%d so:%d]{ re%d rm%d}",
  93      (sym->rname[0] ? sym->rname : sym->name),
  94      sym->key,
  95      sym->liveFrom,sym->liveTo,
  96      sym->stack,
  97      sym->isreqv,sym->remat
  98      );
  99
 100   fprintf(file,"{"); printTypeChain(sym->type,file);
 101   if (sym->usl.spillLoc) {
 102       fprintf(file,"}{ sir@ %s",sym->usl.spillLoc->rname);
 103   }
 104   fprintf(file,"}");
 105
 106   /* if assigned to registers */
 107   if (sym->nRegs) {
 108       if (sym->isspilt) {
 109     if (!sym->remat)
 110         if (sym->usl.spillLoc)
 111       fprintf(file,"[%s]",(sym->usl.spillLoc->rname[0] ?
 112                sym->usl.spillLoc->rname :
 113                sym->usl.spillLoc->name));
 114         else
 115       fprintf(file,"[err]");
 116     else
 117         fprintf(file,"[remat]");
 118       }
 119       else {
 120     int i;
 121     fprintf(file,"[");
 122     for(i=0;i<sym->nRegs;i++)
 123         fprintf(file,"%s ", port->getRegName(sym->regs[i]));
 124     fprintf(file,"]");
 125       }
 126   }
 127   fprintf(file,"\n");
 128     }
 129
 130     fclose(file);
 131 }
 132 /*-----------------------------------------------------------------*/
 133 /* dumpEbbsToFileExt - writeall the basic blocks to a file         */
 134 /*-----------------------------------------------------------------*/
 135 void dumpEbbsToFileExt (char *ext,eBBlock **ebbs, int count)
 136 {
 137     FILE *of;
 138     int i;
 139
 140     if (ext) {
 141   /* create the file name */
 142   strcpy(buffer,srcFileName);
 143   strcat(buffer,ext);
 144
 145   if (!(of = fopen(buffer,"a+"))) {
 146       werror(E_FILE_OPEN_ERR,buffer);
 147       exit(1);
 148   }
 149     } else
 150   of = stdout;
 151
 152     for (i=0; i < count ; i++ ) {
 153   fprintf(of,"\n----------------------------------------------------------------\n");
 154   fprintf(of,"Basic Block %s : loop Depth = %d noPath = %d , lastinLoop = %d\n",
 155     ebbs[i]->entryLabel->name,
 156     ebbs[i]->depth,
 157     ebbs[i]->noPath,
 158     ebbs[i]->isLastInLoop);
 159   fprintf(of,"\ndefines bitVector :");
 160   bitVectDebugOn(ebbs[i]->defSet,of);
 161   fprintf(of,"\nlocal defines bitVector :");
 162   bitVectDebugOn(ebbs[i]->ldefs,of);
 163   fprintf(of,"\npointers Set bitvector :");
 164   bitVectDebugOn(ebbs[i]->ptrsSet,of);
 165   fprintf(of,"\n----------------------------------------------------------------\n");
 166   printiCChain(ebbs[i]->sch,of);
 167     }
 168     fclose(of);
 169 }
 170
 171 /*-----------------------------------------------------------------*/
 172 /* iCode2eBBlock - converts a sequnce till label to a ebb          */
 173 /*-----------------------------------------------------------------*/
 174 eBBlock *iCode2eBBlock (iCode *ic)
 175 {
 176     iCode *loop ;
 177     eBBlock *ebb = neweBBlock(); /* a llocate an entry */
 178
 179     /* put the first one unconditionally */
 180     ebb->sch = ic ;
 181
 182     /* if this is a label then */
 183     if (ic->op == LABEL)
 184   ebb->entryLabel = ic->argLabel.label ;
 185     else {
 186   sprintf(buffer,"_eBBlock%d",eBBNum++);
 187   ebb->entryLabel = newSymbol(buffer,1);
 188   ebb->entryLabel->key = labelKey++;
 189     }
 190
 191     if (ic &&
 192   ( ic->op == GOTO       ||
 193     ic->op == JUMPTABLE  ||
 194     ic->op == IFX        )) {
 195   ebb->ech = ebb->sch;
 196   return ebb;
 197     }
 198
 199     if ((ic->next && ic->next->op == LABEL) ||
 200   !ic->next ) {
 201   ebb->ech = ebb->sch ;
 202   return ebb ;
 203     }
 204
 205     /* loop thru till we find one with a label */
 206     for ( loop = ic->next ; loop ; loop = loop->next ) {
 207
 208   /* if this is the last one */
 209   if (!loop->next)
 210       break;
 211   /* if this is a function call */
 212   if (loop->op == CALL || loop->op == PCALL) {
 213       ebb->hasFcall = 1;
 214       if (currFunc)
 215     currFunc->hasFcall = 1;
 216   }
 217
 218   /* if the next one is a label */
 219   /* if this is a goto or ifx */
 220   if (loop->next->op == LABEL ||
 221       loop->op == GOTO        ||
 222       loop->op == JUMPTABLE   ||
 223       loop->op == IFX )
 224       break ;
 225     }
 226
 227     /* mark the end of the chain */
 228     ebb->ech = loop ;
 229
 230     return ebb;
 231 }
 232
 233 /*-----------------------------------------------------------------*/
 234 /* eBBWithEntryLabel - finds the basic block with the entry label  */
 235 /*-----------------------------------------------------------------*/
 236 eBBlock *eBBWithEntryLabel ( eBBlock **ebbs , symbol *eLabel, int count)
 237 {
 238     int i;
 239
 240     for ( i = 0 ; i < count ; i++ ) {
 241   if (isSymbolEqual(ebbs[i]->entryLabel,eLabel))
 242       return ebbs[i] ;
 243     }
 244
 245     return NULL ;
 246 }
 247
 248
 249 /*-----------------------------------------------------------------*/
 250 /* ifFromIs - will return 1 if the from block matches this         */
 251 /*-----------------------------------------------------------------*/
 252 DEFSETFUNC(ifFromIs)
 253 {
 254     edge *ep = item;
 255     V_ARG(eBBlock *,this);
 256
 257     if (ep->from == this)
 258   return 1;
 259
 260     return 0;
 261 }
 262
 263
 264 /*-----------------------------------------------------------------*/
 265 /* edgesTo  - returns a set of edges with to == supplied value     */
 266 /*-----------------------------------------------------------------*/
 267 set *edgesTo ( eBBlock *to )
 268 {
 269     set *result = NULL ;
 270     edge *loop ;
 271
 272     for (loop = setFirstItem(graphEdges) ; loop ; loop = setNextItem(graphEdges))
 273   if (loop->to == to && !loop->from->noPath)
 274       addSet(&result,loop->from);
 275
 276     return result ;
 277 }
 278
 279
 280 /*-----------------------------------------------------------------*/
 281 /* addiCodeToeBBlock - will add an iCode to the end of a block     */
 282 /*-----------------------------------------------------------------*/
 283 void addiCodeToeBBlock ( eBBlock *ebp, iCode *ic , iCode *ip)
 284 {
 285     ic->prev = ic->next = NULL;
 286     /* if the insert point is given */
 287     if (ip) {
 288   ic->lineno = ip->lineno;
 289   ic->prev = ip->prev;
 290   ip->prev = ic;
 291   ic->next = ip;
 292   if (!ic->prev)
 293       ebp->sch = ic;
 294   else
 295       ic->prev->next = ic;
 296   return;
 297     }
 298
 299     /* if the block has no  instructions */
 300     if (ebp->ech == NULL ) {
 301   ebp->sch = ebp->ech = ic;
 302   ic->next = NULL;
 303   return ;
 304     }
 305
 306     /* if the last instruction is a goto */
 307     /* we add it just before the goto    */
 308     if ( ebp->ech->op == GOTO || ebp->ech->op == JUMPTABLE
 309       || ebp->ech->op == RETURN)
 310     {
 311   ic->lineno = ebp->ech->lineno;
 312   ic->prev = ebp->ech->prev;
 313   ebp->ech->prev = ic;
 314   ic->next = ebp->ech;
 315   if (!ic->prev) /* was the last only on in the block */
 316       ebp->sch = ic;
 317   else
 318       ic->prev->next = ic;
 319   return;
 320     }
 321
 322     /* if the last one was a ifx statement we check to see */
 323     /* if the condition was defined in the previous instruction */
 324     /* if this is true then we put it before the condition else */
 325     /* we put it before if, this is to reduce register pressure,*/
 326     /* we don't have to hold  condition too long in a register  */
 327     if ( ebp->ech->op == IFX ) {
 328   iCode *ipoint ;
 329
 330 /*  if ( !ebp->ech->prev )  */
 331 /*      ipoint = ebp->ech ; */
 332 /*  else  */
 333 /*      if (!IC_RESULT(ebp->ech->prev)) */
 334 /*    ipoint = ebp->ech ; */
 335 /*      else */
 336 /*    if (IC_COND(ebp->ech)->key == IC_RESULT(ebp->ech->prev)->key) */
 337 /*        ipoint = ebp->ech->prev; */
 338 /*    else */
 339 /*        ipoint = ebp->ech ; */
 340   ipoint = ebp->ech ;
 341   ic->lineno = ipoint->lineno;
 342   ic->prev = ipoint->prev;
 343   ipoint->prev = ic;
 344   ic->next = ipoint;
 345   if (!ic->prev)
 346       ebp->sch = ic;
 347   else
 348       ic->prev->next = ic;
 349   return;
 350     }
 351
 352     /* will add it to the very end */
 353     ip = ebp->ech;
 354     ip->next = ic;
 355     ic->prev = ip;
 356     ic->next = NULL;
 357     ebp->ech = ic;
 358
 359     return ;
 360 }
 361
 362 /*-----------------------------------------------------------------*/
 363 /* remiCodeFromeBBlock - remove an iCode from BBlock               */
 364 /*-----------------------------------------------------------------*/
 365 void remiCodeFromeBBlock (eBBlock *ebb, iCode *ic)
 366 {
 367     if (ic->prev)
 368   ic->prev->next = ic->next ;
 369     else
 370   ebb->sch = ic->next ;
 371
 372     if (ic->next)
 373   ic->next->prev = ic->prev;
 374     else
 375   ebb->ech = ic->prev;
 376 }
 377
 378 /*-----------------------------------------------------------------*/
 379 /* iCodeBreakDown : breakDown iCode chain to blocks                */
 380 /*-----------------------------------------------------------------*/
 381 eBBlock **iCodeBreakDown (iCode *ic, int *count)
 382 {
 383     eBBlock **ebbs = NULL ;
 384     iCode *loop = ic;
 385
 386     *count = 0 ;
 387
 388     /* allocate for the first entry */
 389
 390     ebbs = Safe_calloc(1,sizeof(eBBlock **));
 391
 392     while (loop) {
 393
 394   /* convert 2 block */
 395   eBBlock *ebb = iCode2eBBlock(loop);
 396   loop = ebb->ech->next ;
 397
 398   ebb->ech->next = NULL ; /* mark the end of this chain */
 399   if (loop)
 400       loop->prev = NULL ;
 401   ebb->bbnum = *count ;    /* save this block number     */
 402   /* put it in the array */
 403   ebbs[(*count)++] = ebb ;
 404
 405   /* allocate for the next one. Remember to clear the new */
 406   /*  pointer at the end, that was created by realloc. */
 407
 408   ebbs = Safe_realloc(ebbs,(*count + 1)*sizeof(eBBlock **)) ;
 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
 448     /* if we have stopped at the block , allocate for an extra one */
 449
 450     ebbs = Safe_realloc(ebbs,(*count + 1)*sizeof(eBBlock **)) ;
 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