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