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