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