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