sdcc/src/SDCCcflow.c

   1 /*-------------------------------------------------------------------------
   2
   3   SDCCcflow.c - source file for control flow analysis
   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
  28 static void computeDFOrdering (eBBlock *, int *);
  29
  30 /*-----------------------------------------------------------------*/
  31 /* domSetFromVect - creates a domset from the vector               */
  32 /*-----------------------------------------------------------------*/
  33 static set *
  34 domSetFromVect (ebbIndex *ebbi, bitVect * domVect)
  35 {
  36   int i = 0;
  37   set *domSet = NULL;
  38
  39   if (!domVect)
  40     return NULL;
  41
  42   for (i = 0; i < domVect->size; i++)
  43     if (bitVectBitValue (domVect, i))
  44       addSet (&domSet, ebbi->bbOrder[i]);
  45   return domSet;
  46 }
  47
  48
  49 /*-----------------------------------------------------------------*/
  50 /* addSuccessor - will add bb to succ also add it to the pred of   */
  51 /*                the next one :                                   */
  52 /*-----------------------------------------------------------------*/
  53 static void
  54 addSuccessor (eBBlock * thisBlock, eBBlock * succ)
  55 {
  56   /* check for boundary conditions */
  57   if (!thisBlock || !succ)
  58     return;
  59
  60   /* add it to the succ of thisBlock */
  61   addSetIfnotP (&thisBlock->succList, succ);
  62
  63   thisBlock->succVect =
  64     bitVectSetBit (thisBlock->succVect, succ->bbnum);
  65   /* add this edge to the list of edges */
  66   addSet (&graphEdges, newEdge (thisBlock, succ));
  67
  68 }
  69
  70 /*-----------------------------------------------------------------*/
  71 /* eBBPredecessors - find the predecessors for each block          */
  72 /*-----------------------------------------------------------------*/
  73 static void
  74 eBBPredecessors (ebbIndex * ebbi)
  75 {
  76   eBBlock ** ebbs = ebbi->bbOrder;
  77   int count = ebbi->count;
  78   int i = 0, j;
  79
  80   /* for each block do */
  81   for (i = 0; i < count; i++)
  82     {
  83
  84       /* if there is no path to this then continue */
  85       if (ebbs[i]->noPath)
  86         continue;
  87
  88       /* for each successor of this block if */
  89       /* it has depth first number > this block */
  90       /* then this block precedes the successor  */
  91       for (j = 0; j < ebbs[i]->succVect->size; j++)
  92
  93         if (bitVectBitValue (ebbs[i]->succVect, j) &&
  94             ebbs[j]->dfnum > ebbs[i]->dfnum)
  95
  96           addSet (&ebbs[j]->predList, ebbs[i]);
  97     }
  98 }
  99
 100 /*-----------------------------------------------------------------*/
 101 /* eBBSuccessors- find out the successors of all the nodes         */
 102 /*-----------------------------------------------------------------*/
 103 static void
 104 eBBSuccessors (ebbIndex * ebbi)
 105 {
 106   eBBlock ** ebbs = ebbi->bbOrder;
 107   int count = ebbi->count;
 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               bool foundNoReturn = FALSE;
 130               if (ebbs[i]->ech->op == CALL || ebbs[i]->ech->op == PCALL)
 131                 {
 132                   sym_link *type = operandType (IC_LEFT (ebbs[i]->ech));
 133                   if (IS_FUNCPTR (type))
 134                     type = type->next;
 135                   if (type && FUNC_ISNORETURN (type))
 136                     foundNoReturn = TRUE;
 137                 }
 138               if (!foundNoReturn &&
 139                  ebbs[i]->ech->op != GOTO &&
 140                   ebbs[i]->ech->op != RETURN &&
 141                   ebbs[i]->ech->op != JUMPTABLE)
 142                 {
 143                   int j = i + 1;
 144
 145                   while (ebbs[j] && ebbs[j]->noPath)
 146                     j++;
 147
 148                   addSuccessor (ebbs[i], ebbs[j]);      /* add it */
 149                 }
 150               else
 151                 {
 152                   if (i && ebbs[i-1]->ech && ebbs[i-1]->ech->op==IFX) {
 153                     ebbs[i]->isConditionalExitFrom=ebbs[i-1];
 154                   }
 155                 }
 156             }                   /* no instructions in the block */
 157           /* could happen for dummy blocks */
 158           else
 159             addSuccessor (ebbs[i], ebbs[i + 1]);
 160         }
 161
 162       /* go thru all the instructions: if we find a */
 163       /* goto or ifx or a return then we have a succ */
 164       if ((ic = ebbs[i]->ech))
 165         {
 166           eBBlock *succ;
 167
 168           /* special case for jumptable */
 169           if (ic->op == JUMPTABLE)
 170             {
 171               symbol *lbl;
 172               for (lbl = setFirstItem (IC_JTLABELS (ic)); lbl;
 173                    lbl = setNextItem (IC_JTLABELS (ic)))
 174                 addSuccessor (ebbs[i],
 175                               eBBWithEntryLabel (ebbi, lbl));
 176             }
 177           else
 178             {
 179
 180               succ = NULL;
 181               /* depending on the instruction operator */
 182               switch (ic->op)
 183                 {
 184                 case GOTO:      /* goto has edge to label */
 185                   succ = eBBWithEntryLabel (ebbi, ic->label);
 186
 187                   /* Sometimes a block has a GOTO added after the original */
 188                   /* final IFX (due to loop optimizations). If IFX found,  */
 189                   /* fall through to handle the IFX too. */
 190                   if (ic->prev && ic->prev->op == IFX)
 191                     {
 192                       if (succ)
 193                         addSuccessor (ebbs[i], succ); /* add the GOTO target */
 194                       ic = ic->prev;       /* get ready to handle IFX too. */
 195                     }
 196                   else
 197                     break;
 198
 199                 case IFX:       /* conditional jump */
 200                   /* if true label is present */
 201                   if (IC_TRUE (ic))
 202                     succ = eBBWithEntryLabel (ebbi, IC_TRUE (ic));
 203                   else
 204                     succ = eBBWithEntryLabel (ebbi, IC_FALSE (ic));
 205                   break;
 206
 207                 case RETURN:    /* block with return */
 208                   succ = eBBWithEntryLabel (ebbi, returnLabel);
 209                   break;
 210                 }
 211
 212               /* if there is a successor add to the list */
 213               /* if it is not already present in the list */
 214               if (succ)
 215                 addSuccessor (ebbs[i], succ);
 216             }
 217         }
 218     }
 219 }
 220
 221 /*-----------------------------------------------------------------*/
 222 /* computeDominance - computes the dominance graph                 */
 223 /* for algorithm look at Dragon book section 10.10, algo 10.16     */
 224 /*-----------------------------------------------------------------*/
 225 static void
 226 computeDominance (ebbIndex * ebbi)
 227 {
 228   eBBlock ** ebbs = ebbi->bbOrder;
 229   int count = ebbi->count;
 230   int i, j;
 231
 232   /* now do the initialisation */
 233   /* D(n0) := { n0 } */
 234   ebbs[0]->domVect =
 235     bitVectSetBit (ebbs[0]->domVect = newBitVect (count), ebbs[0]->bbnum);
 236
 237
 238   /* for n in N - { n0 } do D(n) = N */
 239   for (i = 1; i < count; i++)
 240     {
 241       ebbs[i]->domVect = newBitVect (count);
 242       for (j = 0; j < count; j++)
 243         {
 244           ebbs[i]->domVect =
 245             bitVectSetBit (ebbs[i]->domVect, ebbs[j]->bbnum);
 246         }
 247     }
 248
 249   /* end of initialisation */
 250
 251   /* while changes to any D(n) occur do */
 252   /*   for n in N - { n0 } do           */
 253   /*       D(n) := { n } U  (intersection of D( all predecessors of n)) */
 254   while (1)
 255     {
 256       int change;
 257
 258       change = 0;
 259       for (i = 1; i < count; i++)
 260         {
 261           bitVect *cDomVect;
 262           eBBlock *pred;
 263
 264           cDomVect = NULL;
 265
 266           /* get the intersection of the dominance of all predecessors */
 267           for (pred = setFirstItem (ebbs[i]->predList),
 268                cDomVect = (pred ? bitVectCopy (pred->domVect) : NULL);
 269                pred;
 270                pred = setNextItem (ebbs[i]->predList))
 271             {
 272               cDomVect = bitVectInplaceIntersect (cDomVect, pred->domVect);
 273             }
 274           if (!cDomVect)
 275             cDomVect = newBitVect (count);
 276           /* this node to the list */
 277           cDomVect = bitVectSetBit (cDomVect, ebbs[i]->bbnum);
 278
 279
 280           if (!bitVectEqual (cDomVect, ebbs[i]->domVect))
 281             {
 282         freeBitVect (ebbs[i]->domVect);
 283               ebbs[i]->domVect = cDomVect;
 284               change = 1;
 285             }
 286         }
 287
 288       /* if no change then exit */
 289       if (!change)
 290         break;
 291     }
 292
 293 }
 294
 295 /*-----------------------------------------------------------------*/
 296 /* immedDom - returns the immediate dominator of a block           */
 297 /*-----------------------------------------------------------------*/
 298 eBBlock *
 299 immedDom (ebbIndex * ebbi, eBBlock * ebp)
 300 {
 301   /* first delete self from the list */
 302   set *iset = domSetFromVect (ebbi, ebp->domVect);
 303   eBBlock *loop;
 304   eBBlock *idom = NULL;
 305
 306   deleteSetItem (&iset, ebp);
 307   /* then just return the one with the greatest */
 308   /* depthfirst number, this will be the immed dominator */
 309   if ((loop = setFirstItem (iset)))
 310     idom = loop;
 311   for (; loop; loop = setNextItem (iset))
 312     if (loop->dfnum > idom->dfnum)
 313       idom = loop;
 314
 315   setToNull ((void *) &iset);
 316   return idom;
 317
 318 }
 319
 320 /*-----------------------------------------------------------------*/
 321 /* DFOrdering - is visited then nothing else call DFOrdering this  */
 322 /*-----------------------------------------------------------------*/
 323 DEFSETFUNC (DFOrdering)
 324 {
 325   eBBlock *ebbp = item;
 326   V_ARG (int *, count);
 327
 328   if (ebbp->visited)
 329     return 0;
 330
 331   computeDFOrdering (ebbp, count);      /* depthfirst */
 332
 333   return 0;
 334 }
 335
 336 /*-----------------------------------------------------------------*/
 337 /* computeDFOrdering - computes the depth first ordering of the    */
 338 /*                     flowgraph                                   */
 339 /*-----------------------------------------------------------------*/
 340 static void
 341 computeDFOrdering (eBBlock * ebbp, int *count)
 342 {
 343
 344   ebbp->visited = 1;
 345   /* for each successor that is not visited */
 346   applyToSet (ebbp->succList, DFOrdering, count);
 347
 348   /* set the depth first number */
 349   ebbp->dfnum = *count;
 350   *count -= 1;
 351 }
 352
 353 /*-----------------------------------------------------------------*/
 354 /* disconBBlock - removes all control flow links for a block       */
 355 /*-----------------------------------------------------------------*/
 356 void
 357 disconBBlock (eBBlock * ebp, ebbIndex * ebbi)
 358 {
 359   /* mark this block as noPath & recompute control flow */
 360   ebp->noPath = 1;
 361   computeControlFlow (ebbi);
 362 }
 363
 364 /*-----------------------------------------------------------------*/
 365 /* markNoPath - marks those blocks which cannot be reached from top */
 366 /*-----------------------------------------------------------------*/
 367 static void
 368 markNoPath (ebbIndex * ebbi)
 369 {
 370   eBBlock ** ebbs = ebbi->bbOrder;
 371   int count = ebbi->count;
 372   int i;
 373
 374   /* for all blocks if the visited flag is not set : then there */
 375   /* is no path from _entry to this block push them down in the */
 376   /* depth first order */
 377   for (i = 0; i < count; i++)
 378     if (!ebbs[i]->visited)
 379       ebbs[i]->noPath = 1;
 380 }
 381
 382 /*-----------------------------------------------------------------*/
 383 /* dfNumCompare - used by qsort to sort by dfNumber                */
 384 /*-----------------------------------------------------------------*/
 385 int
 386 dfNumCompare (const void *a, const void *b)
 387 {
 388   const eBBlock *const *i = a;
 389   const eBBlock *const *j = b;
 390
 391   if ((*i)->dfnum > (*j)->dfnum)
 392     return 1;
 393
 394   if ((*i)->dfnum < (*j)->dfnum)
 395     return -1;
 396
 397   return 0;
 398 }
 399
 400 /*-----------------------------------------------------------------*/
 401 /* computeControlFlow - does the control flow computation          */
 402 /*-----------------------------------------------------------------*/
 403 void
 404 computeControlFlow (ebbIndex * ebbi)
 405 {
 406   eBBlock ** ebbs = ebbi->bbOrder;
 407   int dfCount = ebbi->count;
 408   int i;
 409
 410   /* initialise some things */
 411
 412   for (i = 0; i < ebbi->count; i++)
 413     {
 414       deleteSet (&ebbs[i]->predList);
 415       freeBitVect (ebbs[i]->domVect); ebbs[i]->domVect = NULL;
 416       deleteSet (&ebbs[i]->succList);
 417       freeBitVect (ebbs[i]->succVect); ebbs[i]->succVect = NULL;
 418       ebbs[i]->visited = 0;
 419       ebbs[i]->dfnum = 0;
 420     }
 421
 422   setToNull ((void *) &graphEdges);
 423   /* this will put in the  */
 424   /* successor information for each blk */
 425   eBBSuccessors (ebbi);
 426
 427   /* compute the depth first ordering */
 428   computeDFOrdering (ebbi->bbOrder[0], &dfCount);
 429
 430   /* mark blocks with no paths to them */
 431   markNoPath (ebbi);
 432
 433   /* with the depth first info in place */
 434   /* add the predecessors for the blocks */
 435   eBBPredecessors (ebbi);
 436
 437   /* compute the dominance graph */
 438   computeDominance (ebbi);
 439
 440   /* sort it by dfnumber */
 441   if (!ebbi->dfOrder)
 442     ebbi->dfOrder = Safe_alloc ((ebbi->count+1) * sizeof (eBBlock *));
 443   for (i = 0; i < (ebbi->count+1); i++)
 444     {
 445       ebbi->dfOrder[i] = ebbi->bbOrder[i];
 446     }
 447
 448   qsort (ebbi->dfOrder, ebbi->count, sizeof (eBBlock *), dfNumCompare);
 449
 450 }
 451
 452 /*-----------------------------------------------------------------*/
 453 /* returnAtEnd - returns 1 if Basic Block has a return at the end  */
 454 /*               of it                                             */
 455 /*-----------------------------------------------------------------*/
 456 int returnAtEnd (eBBlock *ebp)
 457 {
 458     /* case 1.
 459        This basic block ends in a return statement
 460     */
 461     if (ebp->ech && ebp->ech->op == RETURN) return 1;
 462
 463     /* case 2.
 464        This basic block has only one successor and that
 465        successor has only one return statement
 466     */
 467     if (elementsInSet(ebp->succList) == 1) {
 468         eBBlock *succ = setFirstItem(ebp->succList);
 469         /* could happen for dummy blocks */
 470         if (!succ->sch || !succ->ech) return 0;
 471
 472         /* first iCode is a return */
 473         if (succ->sch->op == RETURN) return 2;
 474
 475         /* or first iCode is a label & the next &
 476            last icode is a return */
 477         if (succ->sch->op == LABEL && succ->sch->next == succ->ech &&
 478             succ->ech->op == RETURN ) return 2;
 479     }
 480
 481     return 0;
 482 }
 483