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