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