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