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

   1 //#define LIVERANGEHUNT
   2 #ifdef LIVERANGEHUNT
   3   #define LRH(x) x
   4 #else
   5   #define LRH(x)
   6 #endif
   7 /*-------------------------------------------------------------------------
   8
   9   SDCCcflow.c - source file for control flow analysis
  10
  11              Written By -  Sandeep Dutta . sandeep.dutta@usa.net (1998)
  12
  13    This program is free software; you can redistribute it and/or modify it
  14    under the terms of the GNU General Public License as published by the
  15    Free Software Foundation; either version 2, or (at your option) any
  16    later version.
  17
  18    This program is distributed in the hope that it will be useful,
  19    but WITHOUT ANY WARRANTY; without even the implied warranty of
  20    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21    GNU General Public License for more details.
  22
  23    You should have received a copy of the GNU General Public License
  24    along with this program; if not, write to the Free Software
  25    Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  26
  27    In other words, you are welcome to use, share and improve this program.
  28    You are forbidden to forbid anyone else to use, share and improve
  29    what you give them.   Help stamp out software-hoarding!
  30 -------------------------------------------------------------------------*/
  31
  32 #include "common.h"
  33
  34 /*-----------------------------------------------------------------*/
  35 /* domSetFromVect - creates a domset from the vector               */
  36 /*-----------------------------------------------------------------*/
  37 set *
  38 domSetFromVect (eBBlock ** ebbs, bitVect * domVect)
  39 {
  40   int i = 0;
  41   set *domSet = NULL;
  42
  43   if (!domVect)
  44     return NULL;
  45
  46   for (i = 0; i < domVect->size; i++)
  47     if (bitVectBitValue (domVect, i))
  48       addSet (&domSet, ebbs[i]);
  49   return domSet;
  50 }
  51
  52
  53 /*-----------------------------------------------------------------*/
  54 /* addSuccessor - will add bb to succ also add it to the pred of   */
  55 /*                the next one :                                   */
  56 /*-----------------------------------------------------------------*/
  57 void
  58 addSuccessor (eBBlock * thisBlock, eBBlock * succ)
  59 {
  60   /* check for boundary conditions */
  61   if (!thisBlock || !succ)
  62     return;
  63
  64   /* add it to the succ of thisBlock */
  65   addSetIfnotP (&thisBlock->succList, succ);
  66
  67   thisBlock->succVect =
  68     bitVectSetBit (thisBlock->succVect, succ->bbnum);
  69   /* add this edge to the list of edges */
  70   addSet (&graphEdges, newEdge (thisBlock, succ));
  71
  72 }
  73
  74 /*-----------------------------------------------------------------*/
  75 /* eBBPredecessors - find the predecessors for each block          */
  76 /*-----------------------------------------------------------------*/
  77 void
  78 eBBPredecessors (eBBlock ** ebbs, int count)
  79 {
  80   int i = 0, j;
  81
  82   /* for each block do */
  83   for (i = 0; i < count; i++)
  84     {
  85
  86       /* if there is no path to this then continue */
  87       if (ebbs[i]->noPath)
  88         continue;
  89
  90       /* for each successor of this block if */
  91       /* it has depth first number > this block */
  92       /* then this block precedes the successor  */
  93       for (j = 0; j < ebbs[i]->succVect->size; j++)
  94
  95         if (bitVectBitValue (ebbs[i]->succVect, j) &&
  96             ebbs[j]->dfnum > ebbs[i]->dfnum)
  97
  98           addSet (&ebbs[j]->predList, ebbs[i]);
  99     }
 100 }
 101
 102 /*-----------------------------------------------------------------*/
 103 /* eBBSuccessors- find out the successors of all the nodes         */
 104 /*-----------------------------------------------------------------*/
 105 void
 106 eBBSuccessors (eBBlock ** ebbs, int count)
 107 {
 108   int i = 0;
 109
 110   /* for all the blocks do */
 111   for (; i < count; i++)
 112     {
 113       iCode *ic;
 114
 115       if (ebbs[i]->noPath)
 116         continue;
 117
 118       ebbs[i]->succVect = newBitVect (count);
 119
 120       /* if the next on exists & this one does not */
 121       /* end in a GOTO or RETURN then the next is  */
 122       /* a natural successor of this. Note we have */
 123       /* consider eBBlocks with no instructions    */
 124       if (ebbs[i + 1])
 125         {
 126
 127           if (ebbs[i]->ech)
 128             {
 129               if (ebbs[i]->ech->op != GOTO &&
 130                   ebbs[i]->ech->op != RETURN &&
 131                   ebbs[i]->ech->op != JUMPTABLE)
 132                 {
 133                   int j = i + 1;
 134
 135                   while (ebbs[j] && ebbs[j]->noPath)
 136                     j++;
 137
 138                   addSuccessor (ebbs[i], ebbs[j]);      /* add it */
 139                 }
 140               else
 141                 {
 142                   int j=i;
 143                   while (j--) {
 144                     if (ebbs[j]->ech && ebbs[j]->ech->op==IFX &&
 145                         (isSymbolEqual(IC_TRUE(ebbs[j]->ech), ebbs[i]->entryLabel) ||
 146                          isSymbolEqual(IC_FALSE(ebbs[j]->ech), ebbs[i]->entryLabel))) {
 147                       LRH(printf ("%s has a conditional exit from %s\n", ebbs[i]->entryLabel->name, ebbs[j]->entryLabel->name));
 148                       ebbs[i]->hasConditionalExit=1;
 149                     }
 150                   }
 151                 }
 152             }                   /* no instructions in the block */
 153           /* could happen for dummy blocks */
 154           else
 155             addSuccessor (ebbs[i], ebbs[i + 1]);
 156         }
 157
 158       /* go thru all the instructions: if we find a */
 159       /* goto or ifx or a return then we have a succ */
 160       if ((ic = ebbs[i]->ech))
 161         {
 162           eBBlock *succ;
 163
 164           /* special case for jumptable */
 165           if (ic->op == JUMPTABLE)
 166             {
 167               symbol *lbl;
 168               for (lbl = setFirstItem (IC_JTLABELS (ic)); lbl;
 169                    lbl = setNextItem (IC_JTLABELS (ic)))
 170                 addSuccessor (ebbs[i],
 171                               eBBWithEntryLabel (ebbs, lbl, count));
 172             }
 173           else
 174             {
 175
 176               succ = NULL;
 177               /* depending on the instruction operator */
 178               switch (ic->op)
 179                 {
 180                 case GOTO:      /* goto has edge to label */
 181                   succ = eBBWithEntryLabel (ebbs, ic->label, count);
 182                   break;
 183
 184                 case IFX:       /* conditional jump */
 185                   /* if true label is present */
 186                   if (IC_TRUE (ic))
 187                     succ = eBBWithEntryLabel (ebbs, IC_TRUE (ic), count);
 188                   else
 189                     succ = eBBWithEntryLabel (ebbs, IC_FALSE (ic), count);
 190                   break;
 191
 192                 case RETURN:    /* block with return */
 193                   succ = eBBWithEntryLabel (ebbs, returnLabel, count);
 194                   break;
 195                 }
 196
 197               /* if there is a successor add to the list */
 198               /* if it is not already present in the list */
 199               if (succ)
 200                 addSuccessor (ebbs[i], succ);
 201             }
 202         }
 203     }
 204 }
 205
 206 /*-----------------------------------------------------------------*/
 207 /* computeDominance - computes the dominance graph                 */
 208 /* for algorithm look at Dragon book section 10.10, algo 10.16     */
 209 /*-----------------------------------------------------------------*/
 210 void
 211 computeDominance (eBBlock ** ebbs, int count)
 212 {
 213   int i, j;
 214
 215   /* now do the initialisation */
 216   /* D(n0) := { n0 } */
 217   ebbs[0]->domVect =
 218     bitVectSetBit (ebbs[0]->domVect = newBitVect (count), ebbs[0]->bbnum);
 219
 220
 221   /* for n in N - { n0 } do D(n) = N */
 222   for (i = 1; i < count; i++)
 223     {
 224       ebbs[i]->domVect = newBitVect (count);
 225       for (j = 0; j < count; j++)
 226         {
 227           ebbs[i]->domVect =
 228             bitVectSetBit (ebbs[i]->domVect, ebbs[j]->bbnum);
 229         }
 230     }
 231
 232   /* end of initialisation */
 233
 234   /* while changes to any D(n) occur do */
 235   /*   for n in N - { n0 } do           */
 236   /*       D(n) := { n } U  (intersection of D( all predecessors of n)) */
 237   while (1)
 238     {
 239       int change;
 240
 241       change = 0;
 242       for (i = 1; i < count; i++)
 243         {
 244           bitVect *cDomVect;
 245           eBBlock *pred;
 246
 247           cDomVect = NULL;
 248
 249           /* get the intersection of the dominance of all predecessors */
 250           for (pred = setFirstItem (ebbs[i]->predList),
 251                cDomVect = (pred ? bitVectCopy (pred->domVect) : NULL);
 252                pred;
 253                pred = setNextItem (ebbs[i]->predList))
 254             {
 255               cDomVect = bitVectIntersect (cDomVect, pred->domVect);
 256             }
 257           if (!cDomVect)
 258             cDomVect = newBitVect (count);
 259           /* this node to the list */
 260           cDomVect = bitVectSetBit (cDomVect, ebbs[i]->bbnum);
 261
 262
 263           if (!bitVectEqual (cDomVect, ebbs[i]->domVect))
 264             {
 265               ebbs[i]->domVect = cDomVect;
 266               change = 1;
 267             }
 268         }
 269
 270       /* if no change then exit */
 271       if (!change)
 272         break;
 273     }
 274 }
 275
 276 /*-----------------------------------------------------------------*/
 277 /* immedDom - returns the immediate dominator of a block           */
 278 /*-----------------------------------------------------------------*/
 279 eBBlock *
 280 immedDom (eBBlock ** ebbs, eBBlock * ebp)
 281 {
 282   /* first delete self from the list */
 283   set *iset = domSetFromVect (ebbs, ebp->domVect);
 284   eBBlock *loop;
 285   eBBlock *idom = NULL;
 286
 287   deleteSetItem (&iset, ebp);
 288   /* then just return the one with the greatest */
 289   /* depthfirst number, this will be the immed dominator */
 290   if ((loop = setFirstItem (iset)))
 291     idom = loop;
 292   for (; loop; loop = setNextItem (iset))
 293     if (loop->dfnum > idom->dfnum)
 294       idom = loop;
 295
 296   setToNull ((void **) &iset);
 297   return idom;
 298
 299 }
 300
 301 /*-----------------------------------------------------------------*/
 302 /* DFOrdering - is visited then nothing else call DFOrdering this  */
 303 /*-----------------------------------------------------------------*/
 304 DEFSETFUNC (DFOrdering)
 305 {
 306   eBBlock *ebbp = item;
 307   V_ARG (int *, count);
 308
 309   if (ebbp->visited)
 310     return 0;
 311
 312   computeDFOrdering (ebbp, count);      /* depthfirst */
 313
 314   return 0;
 315 }
 316
 317 /*-----------------------------------------------------------------*/
 318 /* computeDFOrdering - computes the depth first ordering of the    */
 319 /*                     flowgraph                                   */
 320 /*-----------------------------------------------------------------*/
 321 void
 322 computeDFOrdering (eBBlock * ebbp, int *count)
 323 {
 324
 325   ebbp->visited = 1;
 326   /* for each successor that is not visited */
 327   applyToSet (ebbp->succList, DFOrdering, count);
 328
 329   /* set the depth first number */
 330   ebbp->dfnum = *count;
 331   *count -= 1;
 332 }
 333
 334 /*-----------------------------------------------------------------*/
 335 /* disconBBlock - removes all control flow links for a block       */
 336 /*-----------------------------------------------------------------*/
 337 void
 338 disconBBlock (eBBlock * ebp, eBBlock ** ebbs, int count)
 339 {
 340   /* mark this block as noPath & recompute control flow */
 341   ebp->noPath = 1;
 342   computeControlFlow (ebbs, count, TRUE);
 343 }
 344
 345 /*-----------------------------------------------------------------*/
 346 /* markNoPath - marks those blocks which cannot be reached from top */
 347 /*-----------------------------------------------------------------*/
 348 void
 349 markNoPath (eBBlock ** ebbs, int count)
 350 {
 351   int i;
 352
 353
 354   /* for all blocks if the visited flag is not set : then there */
 355   /* is no path from _entry to this block push them down in the */
 356   /* depth first order */
 357   for (i = 0; i < count; i++)
 358     if (!ebbs[i]->visited)
 359       ebbs[i]->noPath = 1;
 360 }
 361 /*-----------------------------------------------------------------*/
 362 /* dfNumCompare - used by qsort to sort by dfNumber                */
 363 /*-----------------------------------------------------------------*/
 364 int
 365 dfNumCompare (const void *a, const void *b)
 366 {
 367   const eBBlock *const *i = a;
 368   const eBBlock *const *j = b;
 369
 370   if ((*i)->dfnum > (*j)->dfnum)
 371     return 1;
 372
 373   if ((*i)->dfnum < (*j)->dfnum)
 374     return -1;
 375
 376   return 0;
 377 }
 378
 379 /*-----------------------------------------------------------------*/
 380 /* bbNumCompare - used by qsort to sort by bbNumber                */
 381 /*-----------------------------------------------------------------*/
 382 int
 383 bbNumCompare (const void *a, const void *b)
 384 {
 385   const eBBlock *const *i = a;
 386   const eBBlock *const *j = b;
 387
 388   if ((*i)->bbnum > (*j)->bbnum)
 389     return 1;
 390
 391   if ((*i)->bbnum < (*j)->bbnum)
 392     return -1;
 393
 394   return 0;
 395 }
 396
 397
 398 /*-----------------------------------------------------------------*/
 399 /* computeControlFlow - does the control flow computation          */
 400 /*-----------------------------------------------------------------*/
 401 void
 402 computeControlFlow (eBBlock ** ebbs, int count, int reSort)
 403 {
 404   int saveCount = count;
 405   int i;
 406
 407   /* initialise some things */
 408
 409   for (i = 0; i < count; i++)
 410     {
 411       setToNull ((void **) &ebbs[i]->predList);
 412       setToNull ((void **) &ebbs[i]->domVect);
 413       setToNull ((void **) &ebbs[i]->succList);
 414       setToNull ((void **) &ebbs[i]->succVect);
 415       ebbs[i]->visited = 0;
 416       ebbs[i]->dfnum = 0;
 417     }
 418
 419   if (reSort)
 420     /* sort it back by block number */
 421     qsort (ebbs, saveCount, sizeof (eBBlock *), bbNumCompare);
 422
 423   setToNull ((void **) &graphEdges);
 424   /* this will put in the  */
 425   /* successor information for each blk */
 426   eBBSuccessors (ebbs, count);
 427
 428   /* compute the depth first ordering */
 429   computeDFOrdering (ebbs[0], &count);
 430
 431   /* mark blocks with no paths to them */
 432   markNoPath (ebbs, saveCount);
 433
 434   /* with the depth first info in place */
 435   /* add the predecessors for the blocks */
 436   eBBPredecessors (ebbs, saveCount);
 437
 438   /* compute the dominance graph */
 439   computeDominance (ebbs, saveCount);
 440
 441   /* sort it by dfnumber */
 442   qsort (ebbs, saveCount, sizeof (eBBlock *), dfNumCompare);
 443
 444 }
 445
 446 /*-----------------------------------------------------------------*/
 447 /* returnAtEnd - returns 1 if Basic Block has a return at the end  */
 448 /*               of it                                             */
 449 /*-----------------------------------------------------------------*/
 450 int returnAtEnd (eBBlock *ebp)
 451 {
 452     /* case 1.
 453        This basic block ends in a return statment
 454     */
 455     if (ebp->ech && ebp->ech->op == RETURN) return 1;
 456
 457     /* case 2.
 458        This basic block has only one successor and that
 459        successor has only one return statement
 460     */
 461     if (elementsInSet(ebp->succList) == 1) {
 462         eBBlock *succ = setFirstItem(ebp->succList);
 463         /* could happen for dummy blocks */
 464         if (!succ->sch || !succ->ech) return 0;
 465
 466         /* first iCode is a return */
 467         if (succ->sch->op == RETURN) return 2;
 468
 469         /* or first iCode is a label & the next &
 470            last icode is a return */
 471         if (succ->sch->op == LABEL && succ->sch->next == succ->ech &&
 472             succ->ech->op == RETURN ) return 2;
 473     }
 474
 475     return 0;
 476 }