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