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