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 *
  47 neweBBlock ()
  48 {
  49   eBBlock *ebb;
  50
  51   ebb = Safe_calloc (1, sizeof (eBBlock));
  52   return ebb;
  53 }
  54
  55 /*-----------------------------------------------------------------*/
  56 /* newEdge - allocates & initialises an edge to given values       */
  57 /*-----------------------------------------------------------------*/
  58 edge *
  59 newEdge (eBBlock * from, eBBlock * to)
  60 {
  61   edge *ep;
  62
  63   ep = Safe_calloc (1, sizeof (edge));
  64
  65   ep->from = from;
  66   ep->to = to;
  67   return ep;
  68 }
  69
  70 /*-----------------------------------------------------------------*/
  71 /* dumpLiveRanges - dump liverange information into a file         */
  72 /*-----------------------------------------------------------------*/
  73 void
  74 dumpLiveRanges (char *ext, hTab * liveRanges)
  75 {
  76   FILE *file;
  77   symbol *sym;
  78   int k;
  79
  80   if (ext)
  81     {
  82       /* create the file name */
  83       strcpy (buffer, srcFileName);
  84       strcat (buffer, ext);
  85
  86       if (!(file = fopen (buffer, "a+")))
  87         {
  88           werror (E_FILE_OPEN_ERR, buffer);
  89           exit (1);
  90         }
  91     }
  92   else
  93     file = stdout;
  94
  95   for (sym = hTabFirstItem (liveRanges, &k); sym;
  96        sym = hTabNextItem (liveRanges, &k))
  97     {
  98
  99       fprintf (file, "%s [k%d lr%d:%d so:%d]{ re%d rm%d}",
 100                (sym->rname[0] ? sym->rname : sym->name),
 101                sym->key,
 102                sym->liveFrom, sym->liveTo,
 103                sym->stack,
 104                sym->isreqv, sym->remat
 105         );
 106
 107       fprintf (file, "{");
 108       printTypeChain (sym->type, file);
 109       if (sym->usl.spillLoc)
 110         {
 111           fprintf (file, "}{ sir@ %s", sym->usl.spillLoc->rname);
 112         }
 113       fprintf (file, "}");
 114
 115       /* if assigned to registers */
 116       if (sym->nRegs)
 117         {
 118           if (sym->isspilt)
 119             {
 120               if (!sym->remat)
 121                 if (sym->usl.spillLoc)
 122                   fprintf (file, "[%s]", (sym->usl.spillLoc->rname[0] ?
 123                                           sym->usl.spillLoc->rname :
 124                                           sym->usl.spillLoc->name));
 125                 else
 126                   fprintf (file, "[err]");
 127               else
 128                 fprintf (file, "[remat]");
 129             }
 130           else
 131             {
 132               int i;
 133               fprintf (file, "[");
 134               for (i = 0; i < sym->nRegs; i++)
 135                 fprintf (file, "%s ", port->getRegName (sym->regs[i]));
 136               fprintf (file, "]");
 137             }
 138         }
 139       fprintf (file, "\n");
 140     }
 141
 142   fclose (file);
 143 }
 144 /*-----------------------------------------------------------------*/
 145 /* dumpEbbsToFileExt - writeall the basic blocks to a file         */
 146 /*-----------------------------------------------------------------*/
 147 void
 148 dumpEbbsToFileExt (char *ext, eBBlock ** ebbs, int count)
 149 {
 150   FILE *of;
 151   int i;
 152
 153   if (ext)
 154     {
 155       /* create the file name */
 156       strcpy (buffer, srcFileName);
 157       strcat (buffer, ext);
 158
 159       if (!(of = fopen (buffer, "w")))
 160         {
 161           werror (E_FILE_OPEN_ERR, buffer);
 162           exit (1);
 163         }
 164     }
 165   else
 166     of = stdout;
 167
 168   for (i = 0; i < count; i++)
 169     {
 170       fprintf (of, "\n----------------------------------------------------------------\n");
 171       fprintf (of, "Basic Block %s : loop Depth = %d noPath = %d , lastinLoop = %d\n",
 172                ebbs[i]->entryLabel->name,
 173                ebbs[i]->depth,
 174                ebbs[i]->noPath,
 175                ebbs[i]->isLastInLoop);
 176       fprintf (of, "\ndefines bitVector :");
 177       bitVectDebugOn (ebbs[i]->defSet, of);
 178       fprintf (of, "\nlocal defines bitVector :");
 179       bitVectDebugOn (ebbs[i]->ldefs, of);
 180       fprintf (of, "\npointers Set bitvector :");
 181       bitVectDebugOn (ebbs[i]->ptrsSet, of);
 182       fprintf (of, "\n----------------------------------------------------------------\n");
 183       printiCChain (ebbs[i]->sch, of);
 184     }
 185   fclose (of);
 186 }
 187
 188 /*-----------------------------------------------------------------*/
 189 /* iCode2eBBlock - converts a sequnce till label to a ebb          */
 190 /*-----------------------------------------------------------------*/
 191 eBBlock *
 192 iCode2eBBlock (iCode * ic)
 193 {
 194   iCode *loop;
 195   eBBlock *ebb = neweBBlock (); /* a llocate an entry */
 196
 197   /* put the first one unconditionally */
 198   ebb->sch = ic;
 199
 200   /* if this is a label then */
 201   if (ic->op == LABEL)
 202     ebb->entryLabel = ic->argLabel.label;
 203   else
 204     {
 205       sprintf (buffer, "_eBBlock%d", eBBNum++);
 206       ebb->entryLabel = newSymbol (buffer, 1);
 207       ebb->entryLabel->key = labelKey++;
 208     }
 209
 210   if (ic &&
 211       (ic->op == GOTO ||
 212        ic->op == JUMPTABLE ||
 213        ic->op == IFX))
 214     {
 215       ebb->ech = ebb->sch;
 216       return ebb;
 217     }
 218
 219   if ((ic->next && ic->next->op == LABEL) ||
 220       !ic->next)
 221     {
 222       ebb->ech = ebb->sch;
 223       return ebb;
 224     }
 225
 226   /* loop thru till we find one with a label */
 227   for (loop = ic->next; loop; loop = loop->next)
 228     {
 229
 230       /* if this is the last one */
 231       if (!loop->next)
 232         break;
 233       /* if this is a function call */
 234       if (loop->op == CALL || loop->op == PCALL)
 235         {
 236           ebb->hasFcall = 1;
 237           if (currFunc)
 238             currFunc->hasFcall = 1;
 239         }
 240
 241       /* if the next one is a label */
 242       /* if this is a goto or ifx */
 243       if (loop->next->op == LABEL ||
 244           loop->op == GOTO ||
 245           loop->op == JUMPTABLE ||
 246           loop->op == IFX)
 247         break;
 248     }
 249
 250   /* mark the end of the chain */
 251   ebb->ech = loop;
 252
 253   return ebb;
 254 }
 255
 256 /*-----------------------------------------------------------------*/
 257 /* eBBWithEntryLabel - finds the basic block with the entry label  */
 258 /*-----------------------------------------------------------------*/
 259 eBBlock *
 260 eBBWithEntryLabel (eBBlock ** ebbs, symbol * eLabel, int count)
 261 {
 262   int i;
 263
 264   for (i = 0; i < count; i++)
 265     {
 266       if (isSymbolEqual (ebbs[i]->entryLabel, eLabel))
 267         return ebbs[i];
 268     }
 269
 270   return NULL;
 271 }
 272
 273
 274 /*-----------------------------------------------------------------*/
 275 /* ifFromIs - will return 1 if the from block matches this         */
 276 /*-----------------------------------------------------------------*/
 277 DEFSETFUNC (ifFromIs)
 278 {
 279   edge *ep = item;
 280   V_ARG (eBBlock *, this);
 281
 282   if (ep->from == this)
 283     return 1;
 284
 285   return 0;
 286 }
 287
 288
 289 /*-----------------------------------------------------------------*/
 290 /* edgesTo  - returns a set of edges with to == supplied value     */
 291 /*-----------------------------------------------------------------*/
 292 set *
 293 edgesTo (eBBlock * to)
 294 {
 295   set *result = NULL;
 296   edge *loop;
 297
 298   for (loop = setFirstItem (graphEdges); loop; loop = setNextItem (graphEdges))
 299     if (loop->to == to && !loop->from->noPath)
 300       addSet (&result, loop->from);
 301
 302   return result;
 303 }
 304
 305
 306 /*-----------------------------------------------------------------*/
 307 /* addiCodeToeBBlock - will add an iCode to the end of a block     */
 308 /*-----------------------------------------------------------------*/
 309 void
 310 addiCodeToeBBlock (eBBlock * ebp, iCode * ic, iCode * ip)
 311 {
 312   ic->prev = ic->next = NULL;
 313   /* if the insert point is given */
 314   if (ip)
 315     {
 316       ic->lineno = ip->lineno;
 317       ic->prev = ip->prev;
 318       ip->prev = ic;
 319       ic->next = ip;
 320       if (!ic->prev)
 321         ebp->sch = ic;
 322       else
 323         ic->prev->next = ic;
 324       return;
 325     }
 326
 327   /* if the block has no  instructions */
 328   if (ebp->ech == NULL)
 329     {
 330       ebp->sch = ebp->ech = ic;
 331       ic->next = NULL;
 332       return;
 333     }
 334
 335   /* if the last instruction is a goto */
 336   /* we add it just before the goto    */
 337   if (ebp->ech->op == GOTO || ebp->ech->op == JUMPTABLE
 338       || ebp->ech->op == RETURN)
 339     {
 340       ic->lineno = ebp->ech->lineno;
 341       ic->prev = ebp->ech->prev;
 342       ebp->ech->prev = ic;
 343       ic->next = ebp->ech;
 344       if (!ic->prev)            /* was the last only on in the block */
 345         ebp->sch = ic;
 346       else
 347         ic->prev->next = ic;
 348       return;
 349     }
 350
 351   /* if the last one was a ifx statement we check to see */
 352   /* if the condition was defined in the previous instruction */
 353   /* if this is true then we put it before the condition else */
 354   /* we put it before if, this is to reduce register pressure, */
 355   /* we don't have to hold  condition too long in a register  */
 356   if (ebp->ech->op == IFX)
 357     {
 358       iCode *ipoint;
 359
 360 /*  if ( !ebp->ech->prev )  */
 361 /*      ipoint = ebp->ech ; */
 362 /*  else  */
 363 /*      if (!IC_RESULT(ebp->ech->prev)) */
 364 /*    ipoint = ebp->ech ; */
 365 /*      else */
 366 /*    if (IC_COND(ebp->ech)->key == IC_RESULT(ebp->ech->prev)->key) */
 367 /*        ipoint = ebp->ech->prev; */
 368 /*    else */
 369 /*        ipoint = ebp->ech ; */
 370       ipoint = ebp->ech;
 371       ic->lineno = ipoint->lineno;
 372       ic->prev = ipoint->prev;
 373       ipoint->prev = ic;
 374       ic->next = ipoint;
 375       if (!ic->prev)
 376         ebp->sch = ic;
 377       else
 378         ic->prev->next = ic;
 379       return;
 380     }
 381
 382   /* will add it to the very end */
 383   ip = ebp->ech;
 384   ip->next = ic;
 385   ic->prev = ip;
 386   ic->next = NULL;
 387   ebp->ech = ic;
 388
 389   return;
 390 }
 391
 392 /*-----------------------------------------------------------------*/
 393 /* remiCodeFromeBBlock - remove an iCode from BBlock               */
 394 /*-----------------------------------------------------------------*/
 395 void
 396 remiCodeFromeBBlock (eBBlock * ebb, iCode * ic)
 397 {
 398   if (ic->prev)
 399     ic->prev->next = ic->next;
 400   else
 401     ebb->sch = ic->next;
 402
 403   if (ic->next)
 404     ic->next->prev = ic->prev;
 405   else
 406     ebb->ech = ic->prev;
 407 }
 408
 409 /*-----------------------------------------------------------------*/
 410 /* iCodeBreakDown : breakDown iCode chain to blocks                */
 411 /*-----------------------------------------------------------------*/
 412 eBBlock **
 413 iCodeBreakDown (iCode * ic, int *count)
 414 {
 415   eBBlock **ebbs = NULL;
 416   iCode *loop = ic;
 417
 418   *count = 0;
 419
 420   /* allocate for the first entry */
 421
 422   ebbs = Safe_calloc (1, sizeof (eBBlock **));
 423
 424   while (loop)
 425     {
 426
 427       /* convert 2 block */
 428       eBBlock *ebb = iCode2eBBlock (loop);
 429       loop = ebb->ech->next;
 430
 431       ebb->ech->next = NULL;    /* mark the end of this chain */
 432       if (loop)
 433         loop->prev = NULL;
 434       ebb->bbnum = *count;      /* save this block number     */
 435       /* put it in the array */
 436       ebbs[(*count)++] = ebb;
 437
 438       /* allocate for the next one. Remember to clear the new */
 439       /*  pointer at the end, that was created by realloc. */
 440
 441       ebbs = Safe_realloc (ebbs, (*count + 1) * sizeof (eBBlock **));
 442
 443       ebbs[*count] = 0;
 444
 445       /* if this one ends in a goto or a conditional */
 446       /* branch then check if the block it is going  */
 447       /* to already exists, if yes then this could   */
 448       /* be a loop, add a preheader to the block it  */
 449       /* goes to  if it does not already have one    */
 450       if (ebbs[(*count) - 1]->ech &&
 451           (ebbs[(*count) - 1]->ech->op == GOTO ||
 452            ebbs[(*count) - 1]->ech->op == IFX))
 453         {
 454
 455           symbol *label;
 456           eBBlock *destBlock;
 457
 458           if (ebbs[(*count) - 1]->ech->op == GOTO)
 459             label = IC_LABEL (ebbs[(*count) - 1]->ech);
 460           else if (!(label = IC_TRUE (ebbs[(*count) - 1]->ech)))
 461             label = IC_FALSE (ebbs[(*count) - 1]->ech);
 462
 463           if ((destBlock = eBBWithEntryLabel (ebbs, label, (*count))) &&
 464               destBlock->preHeader == NULL &&
 465               otherPathsPresent (ebbs, destBlock))
 466             {
 467
 468               symbol *preHeaderLabel = newiTempPreheaderLabel ();
 469               int i, j;
 470               eBBlock *pBlock;
 471
 472               /* go thru all block replacing the entryLabel with new label */
 473               /* till we reach the block , then we insert a new ebblock    */
 474               for (i = 0; i < (*count); i++)
 475                 {
 476                   if (ebbs[i] == destBlock)
 477                     break;
 478                   replaceLabel (ebbs[i], label, preHeaderLabel);
 479                 }
 480
 481               (*count)++;
 482
 483               /* if we have stopped at the block , allocate for an extra one */
 484
 485               ebbs = Safe_realloc (ebbs, (*count + 1) * sizeof (eBBlock **));
 486
 487               ebbs[*count] = 0;
 488
 489               /* then move the block down one count */
 490               pBlock = ebbs[j = i];
 491               for (i += 1; i < (*count); i++)
 492                 {
 493                   eBBlock *xBlock;
 494
 495                   xBlock = ebbs[i];
 496                   ebbs[i] = pBlock;
 497                   ebbs[i]->bbnum = i;
 498                   pBlock = xBlock;
 499                 }
 500
 501               destBlock->preHeader = ebbs[j] = neweBBlock ();
 502               ebbs[j]->bbnum = j;
 503               ebbs[j]->entryLabel = preHeaderLabel;
 504               ebbs[j]->sch = ebbs[j]->ech = newiCodeLabelGoto (LABEL, preHeaderLabel);
 505               ebbs[j]->sch->lineno = destBlock->sch->lineno;
 506             }
 507         }
 508     }
 509
 510   /* mark the end */
 511   ebbs[*count] = NULL;
 512
 513   return ebbs;
 514 }
 515
 516 /*-----------------------------------------------------------------*/
 517 /* replaceSymBySym : - replace operand by operand in blocks        */
 518 /*                     replaces only left & right in blocks        */
 519 /*-----------------------------------------------------------------*/
 520 void
 521 replaceSymBySym (set * sset, operand * src, operand * dest)
 522 {
 523   set *loop;
 524   eBBlock *rBlock;
 525
 526   /* for all blocks in the set do */
 527   for (loop = sset; loop; loop = loop->next)
 528     {
 529       iCode *ic;
 530
 531       rBlock = loop->item;
 532       /* for all instructions in this block do */
 533       for (ic = rBlock->sch; ic; ic = ic->next)
 534         {
 535
 536           /* if we find usage */
 537           if (ic->op == IFX && isOperandEqual (src, IC_COND (ic)))
 538             {
 539               bitVectUnSetBit (OP_USES (IC_COND (ic)), ic->key);
 540               IC_COND (ic) = operandFromOperand (dest);
 541               OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
 542               continue;
 543             }
 544
 545           if (isOperandEqual (IC_RIGHT (ic), src))
 546             {
 547               bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
 548               IC_RIGHT (ic) = operandFromOperand (dest);
 549               IC_RIGHT (ic)->isaddr = 0;
 550               OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
 551             }
 552
 553           if (isOperandEqual (IC_LEFT (ic), src))
 554             {
 555               bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
 556               if (POINTER_GET (ic) && IS_ITEMP (dest))
 557                 {
 558                   IC_LEFT (ic) = operandFromOperand (dest);
 559                   IC_LEFT (ic)->isaddr = 1;
 560                 }
 561               else
 562                 {
 563                   IC_LEFT (ic) = operandFromOperand (dest);
 564                   IC_LEFT (ic)->isaddr = 0;
 565                 }
 566               OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
 567             }
 568
 569           /* special case for pointer sets */
 570           if (POINTER_SET (ic) &&
 571               isOperandEqual (IC_RESULT (ic), src))
 572             {
 573               bitVectUnSetBit (OP_USES (IC_RESULT (ic)), ic->key);
 574               IC_RESULT (ic) = operandFromOperand (dest);
 575               IC_RESULT (ic)->isaddr = 1;
 576               OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
 577             }
 578         }
 579     }
 580 }
 581
 582 /*-----------------------------------------------------------------*/
 583 /* replaceLabel - replace reference to one label by another        */
 584 /*-----------------------------------------------------------------*/
 585 void
 586 replaceLabel (eBBlock * ebp, symbol * fromLbl, symbol * toLbl)
 587 {
 588   iCode *ic;
 589
 590   if (!ebp)
 591     return;
 592
 593   for (ic = ebp->sch; ic; ic = ic->next)
 594     {
 595       switch (ic->op)
 596         {
 597
 598         case GOTO:
 599           if (isSymbolEqual (IC_LABEL (ic), fromLbl))
 600             IC_LABEL (ic) = toLbl;
 601           break;
 602
 603         case IFX:
 604           if (IC_TRUE (ic) && isSymbolEqual (IC_TRUE (ic), fromLbl))
 605             IC_TRUE (ic) = toLbl;
 606           else if (isSymbolEqual (IC_FALSE (ic), fromLbl))
 607             IC_FALSE (ic) = toLbl;
 608           break;
 609         }
 610     }
 611
 612   return;
 613
 614 }
 615
 616
 617 /*-----------------------------------------------------------------*/
 618 /* iCodeFromeBBlock - convert basic block to iCode chain           */
 619 /*-----------------------------------------------------------------*/
 620 iCode *
 621 iCodeFromeBBlock (eBBlock ** ebbs, int count)
 622 {
 623   int i = 1;
 624   iCode *ric = ebbs[0]->sch;
 625   iCode *lic = ebbs[0]->ech;
 626
 627   for (; i < count; i++)
 628     {
 629       if (ebbs[i]->sch == NULL)
 630         continue;
 631
 632       if (ebbs[i]->noPath &&
 633           (ebbs[i]->entryLabel != entryLabel &&
 634            ebbs[i]->entryLabel != returnLabel))
 635         {
 636           werror (W_CODE_UNREACH, ebbs[i]->sch->filename, ebbs[i]->sch->lineno);
 637           continue;
 638         }
 639
 640       lic->next = ebbs[i]->sch;
 641       lic->next->prev = lic;
 642       lic = ebbs[i]->ech;
 643     }
 644
 645   return ric;
 646 }
 647
 648 /*-----------------------------------------------------------------*/
 649 /* otherPathsPresent - determines if there is a path from _entry   */
 650 /*      to this block in a half constructed set of blocks          */
 651 /*-----------------------------------------------------------------*/
 652 int
 653 otherPathsPresent (eBBlock ** ebbs, eBBlock * this)
 654 {
 655   int i;
 656
 657   /* for all blocks preceding this block */
 658   for (i = 0; i < this->bbnum; i++)
 659     {
 660       iCode *ic;
 661
 662       /* if there is a reference to the entry label of this block */
 663       for (ic = ebbs[i]->sch; ic; ic = ic->next)
 664         {
 665           switch (ic->op)
 666             {
 667             case GOTO:
 668               if (IC_LABEL (ic)->key == this->entryLabel->key)
 669                 return 1;
 670               break;
 671
 672             case IFX:
 673               if (IC_TRUE (ic))
 674                 {
 675                   if (IC_TRUE (ic)->key == this->entryLabel->key)
 676                     return 1;
 677                 }
 678               else if (IC_FALSE (ic)->key == this->entryLabel->key)
 679                 return 1;
 680               break;
 681             }
 682         }
 683     }
 684
 685   /* comes here means we have not found it yet */
 686   /* in this case check if the previous block  */
 687   /* ends in a goto if it does then we have no */
 688   /* path else we have a path                  */
 689   if (this->bbnum && ebbs[this->bbnum - 1]->ech &&
 690       ebbs[this->bbnum - 1]->ech->op == GOTO)
 691     return 0;
 692   else
 693     return 1;
 694 }