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             /* copy the pointer set from the dominator */
 103             dest->inPtrsSet = bitVectCopy(ebp->ptrsSet);
 104             dest->ndompset  = bitVectCopy(ebp->ndompset);
 105         }
 106         else {
 107             dest->inExprs = intersectSets (dest->inExprs,
 108                                            ebp->outExprs,
 109                                            THROW_DEST);
 110             dest->inPtrsSet = bitVectUnion(dest->inPtrsSet,ebp->ptrsSet);
 111             dest->ndompset  = bitVectUnion(dest->ndompset,ebp->ndompset);
 112         }
 113     }
 114     else {
 115         /* delete only if killed in this block */
 116         deleteItemIf (&dest->inExprs,ifKilledInBlock, ebp);
 117         /* union the ndompset with pointers set in this block*/
 118         dest->ndompset = bitVectUnion(dest->ndompset,ebp->ptrsSet);
 119     }
 120
 121     *firstTime = 0;
 122
 123     return 0;
 124 }
 125
 126 /*-----------------------------------------------------------------*/
 127 /* mergeInDefs - merge in incoming definitions                     */
 128 /*-----------------------------------------------------------------*/
 129 DEFSETFUNC(mergeInDefs)
 130 {
 131     eBBlock *ebp = item ;
 132     V_ARG(eBBlock *,dest);
 133     V_ARG(int *,firstTime);
 134
 135     /* the in definition is the union of the out */
 136     /* of all blocks that come to this block     */
 137     if (!dest->inDefs && *firstTime)
 138         dest->inDefs = bitVectCopy (ebp->outDefs);
 139     else
 140         dest->inDefs = bitVectUnion (dest->inDefs,
 141                                      ebp->outDefs) ;
 142
 143     *firstTime = 0;
 144
 145     return 0;
 146
 147 }
 148
 149 /*-----------------------------------------------------------------*/
 150 /* computeDataFlow - does computations for data flow accross blocks*/
 151 /*-----------------------------------------------------------------*/
 152 void computeDataFlow (eBBlock **ebbs, int count)
 153 {
 154     int i;
 155     int change = 1;
 156
 157     while (change) {
 158
 159         change = 0;
 160
 161         /* for all blocks */
 162         for ( i = 0 ; i < count ; i++ ) {
 163
 164             set *pred ;
 165             set *oldOut;
 166             int firstTime ;
 167             eBBlock *pBlock ;
 168
 169             /* if this is the entry block then continue     */
 170             /* since entry block can never have any inExprs */
 171             if (ebbs[i]->noPath)
 172                 continue ;
 173
 174             /* get blocks that can come to this block */
 175             pred = edgesTo(ebbs[i]);
 176
 177             /* make a copy of the outExpressions : to be */
 178             /* used for iteration   */
 179             oldOut = setFromSet(ebbs[i]->outExprs);
 180             setToNull ((void **)&ebbs[i]->inDefs);
 181
 182             /* indefitions are easy just merge them by union */
 183             /* these are the definitions that can possibly   */
 184             /* reach this block                              */
 185             firstTime = 1;
 186             applyToSet(pred,mergeInDefs,ebbs[i],&firstTime);
 187
 188
 189             /* if none of the edges coming to this block */
 190             /* dominate this block then add the immediate dominator */
 191             /* of this block to the list of predecessors */
 192             for ( pBlock = setFirstItem(pred); pBlock ;
 193                   pBlock = setNextItem(pred)) {
 194                 if (bitVectBitValue(ebbs[i]->domVect,pBlock->bbnum))
 195                     break ;
 196             }
 197
 198             /* get the immediate dominator and put it there */
 199             if (!pBlock) {
 200                 eBBlock *idom = immedDom(ebbs,ebbs[i]);
 201                 if (idom)
 202                     addSetHead (&pred,idom);
 203             }
 204
 205             /* figure out the incoming expressions */
 206             /* this is a little more complex       */
 207             setToNull ((void **)&ebbs[i]->inExprs);
 208             firstTime = 1;
 209             applyToSet(pred,mergeInExprs,ebbs[i],&firstTime);
 210
 211             setToNull ((void **)&pred);
 212
 213             /* do cse with computeOnly flag set to TRUE */
 214             /* this by far the quickest way of computing*/
 215             cseBBlock(ebbs[i],TRUE,ebbs,count);
 216
 217             /* if it change we will need to iterate */
 218             change += ! isSetsEqualWith(ebbs[i]->outExprs,oldOut,isCseDefEqual);
 219         }
 220
 221         if (!change) /* iterate till no change */
 222             break ;
 223     }
 224
 225     return ;
 226 }
 227
 228 /*-----------------------------------------------------------------*/
 229 /* usedBetweenPoints - used between start & end                    */
 230 /*-----------------------------------------------------------------*/
 231 int usedBetweenPoints ( operand *op, iCode *start, iCode *end )
 232 {
 233     iCode *lic = start;
 234
 235       for (;lic != end; lic = lic->next) {
 236
 237         /* if the operand is a parameter */
 238         /* then check for calls and return */
 239         /* true if there is a call       */
 240         if (IS_PARM(op) &&
 241             ( lic->op == CALL ||
 242               lic->op == PCALL ))
 243             if ( isParameterToCall(IC_ARGS(lic),op))
 244                 return 1;
 245
 246         if (SKIP_IC2(lic))
 247             continue ;
 248
 249         /* if ifx then check the condition */
 250         if (lic->op == IFX &&
 251             IC_COND(lic)->key == op->key )
 252             return 1;
 253
 254         if (lic->op == JUMPTABLE &&
 255             IC_JTCOND(lic)->key == op->key )
 256             return 1;
 257
 258         if (IC_RIGHT(lic) &&
 259             IC_RIGHT(lic)->key == op->key )
 260             return 1;
 261
 262         if (IC_LEFT(lic) &&
 263             IC_LEFT(lic)->key == op->key  )
 264             return 1;
 265
 266         /* for a pointer assignment usage */
 267         if (POINTER_SET(lic) &&
 268             op->key == IC_RESULT(lic)->key )
 269             return 1;
 270         else
 271             if (IC_RESULT(lic) && op->key == IC_RESULT(lic)->key)
 272                 return 0;
 273     }
 274
 275     return 0;
 276
 277 }
 278
 279
 280 /*-----------------------------------------------------------------*/
 281 /* usedInRemaining - returns point of usage for an operand if found*/
 282 /*-----------------------------------------------------------------*/
 283 iCode *usedInRemaining (operand *op, iCode *ic)
 284 {
 285     iCode *lic = ic;
 286
 287     if (!IS_SYMOP(op))
 288         return 0;
 289
 290     for (;lic; lic = lic->next) {
 291
 292         /* if the operand is a parameter */
 293         /* then check for calls and return */
 294         /* true if there is a call       */
 295         /* if this is a global variable then
 296            return true */
 297         if ( lic->op == CALL || lic->op == PCALL ) {
 298
 299             if ((IS_PARM(op) &&
 300                 isParameterToCall(IC_ARGS(lic),op)) ||
 301                 isOperandGlobal (op))
 302                 return lic;
 303         }
 304
 305         if (ic->op == SEND &&
 306             isOperandEqual (IC_LEFT(lic),op))
 307             return lic;
 308
 309         if (SKIP_IC1(lic))
 310             continue ;
 311
 312         /* if ifx then check the condition */
 313         if (lic->op == IFX &&
 314             isOperandEqual (IC_COND(lic),op))
 315             return lic;
 316
 317         if (lic->op == JUMPTABLE &&
 318             isOperandEqual (IC_JTCOND(lic),op) )
 319             return lic;
 320
 321         if (IC_RIGHT(lic) &&
 322             isOperandEqual(IC_RIGHT(lic),op))
 323             return lic;
 324
 325         if (IC_LEFT(lic) &&
 326             isOperandEqual(IC_LEFT(lic),op) )
 327             return lic;
 328
 329         /* for a pointer assignment usage */
 330         if (POINTER_SET(lic) &&
 331             isOperandEqual (op,IC_RESULT(lic)))
 332             return lic;
 333         else
 334             if (IC_RESULT(lic) && isOperandEqual(IC_RESULT(lic),op))
 335                 return NULL;
 336     }
 337
 338     return NULL;
 339 }
 340
 341
 342
 343 /*-----------------------------------------------------------------*/
 344 /* isDefAlive - will return true if definiton reaches a block & used */
 345 /*-----------------------------------------------------------------*/
 346 DEFSETFUNC(isDefAlive)
 347 {
 348     eBBlock *ebp = item;
 349     V_ARG(iCode *,diCode);
 350
 351     if (ebp->visited)
 352         return 0;
 353
 354     ebp->visited = 1;
 355
 356     /* if this definition is used in the block */
 357     if (bitVectBitValue(ebp->usesDefs,diCode->key))
 358         return 1;
 359
 360     return applyToSet(ebp->succList,isDefAlive,diCode);
 361 }
 362