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