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