git.gag.com Git - fw/sdcc/blob - src/SDCCdflow.c

   1 /*-------------------------------------------------------------------------
   2
   3   SDCCdflow.c - source file for data flow analysis and other utility
   4                 routines related to data flow.
   5
   6              Written By -  Sandeep Dutta . sandeep.dutta@usa.net (1998)
   7
   8    This program is free software; you can redistribute it and/or modify it
   9    under the terms of the GNU General Public License as published by the
  10    Free Software Foundation; either version 2, or (at your option) any
  11    later version.
  12
  13    This program is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; if not, write to the Free Software
  20    Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  21
  22    In other words, you are welcome to use, share and improve this program.
  23    You are forbidden to forbid anyone else to use, share and improve
  24    what you give them.   Help stamp out software-hoarding!
  25 -------------------------------------------------------------------------*/
  26
  27 #include "common.h"
  28
  29 /*-----------------------------------------------------------------*/
  30 /* ifKilledInBlock - will return 1 if the symbol is redefined in B */
  31 /*-----------------------------------------------------------------*/
  32 DEFSETFUNC(ifKilledInBlock)
  33 {
  34     cseDef *cdp = item;
  35     V_ARG(eBBlock *,src);
  36     bitVect *outs ;
  37
  38     /* if this is a global variable and this block
  39        has a function call then delete it */
  40     if (isOperandGlobal(cdp->sym) && src->hasFcall)
  41         return 1;
  42
  43     /* if this is pointer get then it will be killed
  44        if there is a pointer set for the same pointer
  45        in this block */
  46     if (POINTER_GET(cdp->diCode) &&
  47         bitVectBitValue(src->ptrsSet,
  48                         IC_LEFT(cdp->diCode)->key))
  49         return 1;
  50
  51     /* if assignment to iTmep then if right is defined
  52        elsewhere kill this one */
  53     if (ASSIGNMENT(cdp->diCode)   &&
  54         !POINTER_SET(cdp->diCode) &&
  55         IS_ITEMP(IC_RESULT(cdp->diCode)) &&
  56         IS_SYMOP(IC_RIGHT(cdp->diCode))  &&
  57         bitVectBitsInCommon(src->outDefs,OP_DEFS(IC_RIGHT(cdp->diCode))))
  58         return 1;
  59
  60     /* if we find it in the defSet of this block */
  61     if (bitVectBitsInCommon(src->defSet,OP_DEFS(cdp->sym)))
  62         return 1;
  63
  64     /* if in the outdef we find a definition other than this one */
  65     /* to do this we make a copy of the out definitions and turn */
  66     /* this one off then check if there are other definitions    */
  67     bitVectUnSetBit (outs = bitVectCopy (src->outDefs),
  68                      cdp->diCode->key);
  69     if (bitVectBitsInCommon (outs,OP_DEFS(cdp->sym))) {
  70         setToNull((void **) &outs);
  71         return 1;
  72     }
  73
  74     setToNull((void **) &outs);
  75
  76     /* if the operands of this one was changed in the block */
  77     /* then delete it */
  78     if (cdp->diCode &&
  79         ( (IS_SYMOP(IC_LEFT(cdp->diCode)) &&
  80            bitVectBitsInCommon (src->defSet,OP_DEFS(IC_LEFT(cdp->diCode)))) ||
  81           (IS_SYMOP(IC_RIGHT(cdp->diCode)) &&
  82            bitVectBitsInCommon (src->defSet,OP_DEFS(IC_RIGHT(cdp->diCode)))) ))
  83         return 1;
  84
  85     return 0;
  86 }
  87
  88 /*-----------------------------------------------------------------*/
  89 /* mergeInExprs - copy the in expression if it dominates           */
  90 /*-----------------------------------------------------------------*/
  91 DEFSETFUNC(mergeInExprs)
  92 {
  93     eBBlock *ebp = item;
  94     V_ARG(eBBlock *,dest);
  95     V_ARG(int *,firstTime);
  96
  97     /* if in the dominator list then */
  98     if (bitVectBitValue(dest->domVect,ebp->bbnum) && dest != ebp) {
  99         /* if already present then intersect */
 100         if (!dest->inExprs && *firstTime)
 101             dest->inExprs = setFromSet(ebp->outExprs);
 102         else
 103             dest->inExprs = intersectSets (dest->inExprs,
 104                                            ebp->outExprs,
 105                                            THROW_DEST);
 106         /* copy the pointer set from the dominator */
 107         dest->inPtrsSet = bitVectCopy(ebp->ptrsSet);
 108     }
 109     else
 110         /* delete only if killed in this block */
 111         deleteItemIf (&dest->inExprs,ifKilledInBlock, ebp);
 112
 113     *firstTime = 0;
 114
 115     return 0;
 116 }
 117
 118 /*-----------------------------------------------------------------*/
 119 /* mergeInDefs - merge in incoming definitions                     */
 120 /*-----------------------------------------------------------------*/
 121 DEFSETFUNC(mergeInDefs)
 122 {
 123     eBBlock *ebp = item ;
 124     V_ARG(eBBlock *,dest);
 125     V_ARG(int *,firstTime);
 126
 127     /* the in definition is the union of the out */
 128     /* of all blocks that come to this block     */
 129     if (!dest->inDefs && *firstTime)
 130         dest->inDefs = bitVectCopy (ebp->outDefs);
 131     else
 132         dest->inDefs = bitVectUnion (dest->inDefs,
 133                                      ebp->outDefs) ;
 134
 135     *firstTime = 0;
 136
 137     return 0;
 138
 139 }
 140
 141 /*-----------------------------------------------------------------*/
 142 /* computeDataFlow - does computations for data flow accross blocks*/
 143 /*-----------------------------------------------------------------*/
 144 void computeDataFlow (eBBlock **ebbs, int count)
 145 {
 146     int i;
 147     int change = 1;
 148
 149     while (change) {
 150
 151         change = 0;
 152
 153         /* for all blocks */
 154         for ( i = 0 ; i < count ; i++ ) {
 155
 156             set *pred ;
 157             set *oldOut;
 158             int firstTime ;
 159             eBBlock *pBlock ;
 160
 161             /* if this is the entry block then continue     */
 162             /* since entry block can never have any inExprs */
 163             if (ebbs[i]->noPath)
 164                 continue ;
 165
 166             /* get blocks that can come to this block */
 167             pred = edgesTo(ebbs[i]);
 168
 169             /* make a copy of the outExpressions : to be */
 170             /* used for iteration   */
 171             oldOut = setFromSet(ebbs[i]->outExprs);
 172             setToNull ((void **)&ebbs[i]->inDefs);
 173
 174             /* indefitions are easy just merge them by union */
 175             /* these are the definitions that can possibly   */
 176             /* reach this block                              */
 177             firstTime = 1;
 178             applyToSet(pred,mergeInDefs,ebbs[i],&firstTime);
 179
 180
 181             /* if none of the edges coming to this block */
 182             /* dominate this block then add the immediate dominator */
 183             /* of this block to the list of predecessors */
 184             for ( pBlock = setFirstItem(pred); pBlock ;
 185                   pBlock = setNextItem(pred)) {
 186                 if (bitVectBitValue(ebbs[i]->domVect,pBlock->bbnum))
 187                     break ;
 188             }
 189
 190             /* get the immediate dominator and put it there */
 191             if (!pBlock) {
 192                 eBBlock *idom = immedDom(ebbs,ebbs[i]);
 193                 if (idom)
 194                     addSetHead (&pred,idom);
 195             }
 196
 197             /* figure out the incoming expressions */
 198             /* this is a little more complex       */
 199             setToNull ((void **)&ebbs[i]->inExprs);
 200             firstTime = 1;
 201             applyToSet(pred,mergeInExprs,ebbs[i],&firstTime);
 202
 203             setToNull ((void **)&pred);
 204
 205             /* do cse with computeOnly flag set to TRUE */
 206             /* this by far the quickest way of computing*/
 207             cseBBlock(ebbs[i],TRUE,ebbs,count);
 208
 209             /* if it change we will need to iterate */
 210             change += ! isSetsEqualWith(ebbs[i]->outExprs,oldOut,isCseDefEqual);
 211         }
 212
 213         if (!change) /* iterate till no change */
 214             break ;
 215     }
 216
 217     return ;
 218 }
 219
 220 /*-----------------------------------------------------------------*/
 221 /* usedBetweenPoints - used between start & end                    */
 222 /*-----------------------------------------------------------------*/
 223 int usedBetweenPoints ( operand *op, iCode *start, iCode *end )
 224 {
 225     iCode *lic = start;
 226
 227       for (;lic != end; lic = lic->next) {
 228
 229         /* if the operand is a parameter */
 230         /* then check for calls and return */
 231         /* true if there is a call       */
 232         if (IS_PARM(op) &&
 233             ( lic->op == CALL ||
 234               lic->op == PCALL ))
 235             if ( isParameterToCall(IC_ARGS(lic),op))
 236                 return 1;
 237
 238         if (SKIP_IC2(lic))
 239             continue ;
 240
 241         /* if ifx then check the condition */
 242         if (lic->op == IFX &&
 243             IC_COND(lic)->key == op->key )
 244             return 1;
 245
 246         if (lic->op == JUMPTABLE &&
 247             IC_JTCOND(lic)->key == op->key )
 248             return 1;
 249
 250         if (IC_RIGHT(lic) &&
 251             IC_RIGHT(lic)->key == op->key )
 252             return 1;
 253
 254         if (IC_LEFT(lic) &&
 255             IC_LEFT(lic)->key == op->key  )
 256             return 1;
 257
 258         /* for a pointer assignment usage */
 259         if (POINTER_SET(lic) &&
 260             op->key == IC_RESULT(lic)->key )
 261             return 1;
 262         else
 263             if (IC_RESULT(lic) && op->key == IC_RESULT(lic)->key)
 264                 return 0;
 265     }
 266
 267     return 0;
 268
 269 }
 270
 271
 272 /*-----------------------------------------------------------------*/
 273 /* usedInRemaining - returns point of usage for an operand if found*/
 274 /*-----------------------------------------------------------------*/
 275 iCode *usedInRemaining (operand *op, iCode *ic)
 276 {
 277     iCode *lic = ic;
 278
 279     if (!IS_SYMOP(op))
 280         return 0;
 281
 282     for (;lic; lic = lic->next) {
 283
 284         /* if the operand is a parameter */
 285         /* then check for calls and return */
 286         /* true if there is a call       */
 287         /* if this is a global variable then
 288            return true */
 289         if ( lic->op == CALL || lic->op == PCALL ) {
 290
 291             if ((IS_PARM(op) &&
 292                 isParameterToCall(IC_ARGS(lic),op)) ||
 293                 isOperandGlobal (op))
 294                 return lic;
 295         }
 296
 297         if (ic->op == SEND &&
 298             isOperandEqual (IC_LEFT(lic),op))
 299             return lic;
 300
 301         if (SKIP_IC1(lic))
 302             continue ;
 303
 304         /* if ifx then check the condition */
 305         if (lic->op == IFX &&
 306             isOperandEqual (IC_COND(lic),op))
 307             return lic;
 308
 309         if (lic->op == JUMPTABLE &&
 310             isOperandEqual (IC_JTCOND(lic),op) )
 311             return lic;
 312
 313         if (IC_RIGHT(lic) &&
 314             isOperandEqual(IC_RIGHT(lic),op))
 315             return lic;
 316
 317         if (IC_LEFT(lic) &&
 318             isOperandEqual(IC_LEFT(lic),op) )
 319             return lic;
 320
 321         /* for a pointer assignment usage */
 322         if (POINTER_SET(lic) &&
 323             isOperandEqual (op,IC_RESULT(lic)))
 324             return lic;
 325         else
 326             if (IC_RESULT(lic) && isOperandEqual(IC_RESULT(lic),op))
 327                 return NULL;
 328     }
 329
 330     return NULL;
 331 }
 332
 333
 334
 335 /*-----------------------------------------------------------------*/
 336 /* isDefAlive - will return true if definiton reaches a block & used */
 337 /*-----------------------------------------------------------------*/
 338 DEFSETFUNC(isDefAlive)
 339 {
 340     eBBlock *ebp = item;
 341     V_ARG(iCode *,diCode);
 342
 343     if (ebp->visited)
 344         return 0;
 345
 346     ebp->visited = 1;
 347
 348     /* if this definition is used in the block */
 349     if (bitVectBitValue(ebp->usesDefs,diCode->key))
 350         return 1;
 351
 352     return applyToSet(ebp->succList,isDefAlive,diCode);
 353 }
 354