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