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