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 /* computeControlFlow - does the control flow computation          */
 362 /*-----------------------------------------------------------------*/
 363 void
 364 computeControlFlow (ebbIndex * ebbi)
 365 {
 366   eBBlock ** ebbs = ebbi->bbOrder;
 367   int dfCount = ebbi->count;
 368   int i;
 369
 370   /* initialise some things */
 371
 372   for (i = 0; i < ebbi->count; i++)
 373     {
 374       setToNull ((void *) &ebbs[i]->predList);
 375       setToNull ((void *) &ebbs[i]->domVect);
 376       setToNull ((void *) &ebbs[i]->succList);
 377       setToNull ((void *) &ebbs[i]->succVect);
 378       ebbs[i]->visited = 0;
 379       ebbs[i]->dfnum = 0;
 380     }
 381
 382   setToNull ((void *) &graphEdges);
 383   /* this will put in the  */
 384   /* successor information for each blk */
 385   eBBSuccessors (ebbi);
 386
 387   /* compute the depth first ordering */
 388   computeDFOrdering (ebbi->bbOrder[0], &dfCount);
 389
 390   /* mark blocks with no paths to them */
 391   markNoPath (ebbi);
 392
 393   /* with the depth first info in place */
 394   /* add the predecessors for the blocks */
 395   eBBPredecessors (ebbi);
 396
 397   /* compute the dominance graph */
 398   computeDominance (ebbi);
 399
 400   /* sort it by dfnumber */
 401   if (!ebbi->dfOrder)
 402     ebbi->dfOrder = Safe_alloc ((ebbi->count+1) * sizeof (eBBlock *));
 403   for (i = 0; i < (ebbi->count+1); i++)
 404     {
 405       ebbi->dfOrder[i] = ebbi->bbOrder[i];
 406     }
 407
 408   qsort (ebbi->dfOrder, ebbi->count, sizeof (eBBlock *), dfNumCompare);
 409
 410 }
 411
 412 /*-----------------------------------------------------------------*/
 413 /* returnAtEnd - returns 1 if Basic Block has a return at the end  */
 414 /*               of it                                             */
 415 /*-----------------------------------------------------------------*/
 416 int returnAtEnd (eBBlock *ebp)
 417 {
 418     /* case 1.
 419        This basic block ends in a return statment
 420     */
 421     if (ebp->ech && ebp->ech->op == RETURN) return 1;
 422
 423     /* case 2.
 424        This basic block has only one successor and that
 425        successor has only one return statement
 426     */
 427     if (elementsInSet(ebp->succList) == 1) {
 428         eBBlock *succ = setFirstItem(ebp->succList);
 429         /* could happen for dummy blocks */
 430         if (!succ->sch || !succ->ech) return 0;
 431
 432         /* first iCode is a return */
 433         if (succ->sch->op == RETURN) return 2;
 434
 435         /* or first iCode is a label & the next &
 436            last icode is a return */
 437         if (succ->sch->op == LABEL && succ->sch->next == succ->ech &&
 438             succ->ech->op == RETURN ) return 2;
 439     }
 440
 441     return 0;
 442 }