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         value *args;
 257         if (lic->op == CALL) {
 258           args=FUNC_ARGS(OP_SYMBOL(IC_LEFT(lic))->type);
 259         } else {
 260           args=FUNC_ARGS(OP_SYMBOL(IC_LEFT(lic))->type->next);
 261         }
 262         if (isParameterToCall (args, op))
 263           return 1;
 264       }
 265
 266       if (SKIP_IC2 (lic))
 267         continue;
 268
 269       /* if ifx then check the condition */
 270       if (lic->op == IFX &&
 271           IC_COND (lic)->key == op->key)
 272         return 1;
 273
 274       if (lic->op == JUMPTABLE &&
 275           IC_JTCOND (lic)->key == op->key)
 276         return 1;
 277
 278       if (IC_RIGHT (lic) &&
 279           IC_RIGHT (lic)->key == op->key)
 280         return 1;
 281
 282       if (IC_LEFT (lic) &&
 283           IC_LEFT (lic)->key == op->key)
 284         return 1;
 285
 286       /* for a pointer assignment usage */
 287       if (POINTER_SET (lic) &&
 288           op->key == IC_RESULT (lic)->key)
 289         return 1;
 290       else if (IC_RESULT (lic) && op->key == IC_RESULT (lic)->key)
 291         return 0;
 292     }
 293
 294   return 0;
 295
 296 }
 297
 298
 299 /*-----------------------------------------------------------------*/
 300 /* usedInRemaining - returns point of usage for an operand if found */
 301 /*-----------------------------------------------------------------*/
 302 iCode *
 303 usedInRemaining (operand * op, iCode * ic)
 304 {
 305   iCode *lic = ic;
 306
 307   if (!IS_SYMOP (op))
 308     return 0;
 309
 310   for (; lic; lic = lic->next)
 311     {
 312
 313       /* if the operand is a parameter */
 314       /* then check for calls and return */
 315       /* true if there is a call       */
 316       /* if this is a global variable then
 317          return true */
 318       if (lic->op == CALL || lic->op == PCALL)
 319         {
 320           value *args;
 321           if (lic->op == CALL) {
 322             args=FUNC_ARGS(OP_SYMBOL(IC_LEFT(lic))->type);
 323           } else {
 324             args=FUNC_ARGS(OP_SYMBOL(IC_LEFT(lic))->type->next);
 325           }
 326           if ((IS_PARM (op) &&
 327                isParameterToCall (args, op)) ||
 328               isOperandGlobal (op))
 329             return lic;
 330         }
 331
 332       if (ic->op == SEND &&
 333           isOperandEqual (IC_LEFT (lic), op))
 334         return lic;
 335
 336       if (SKIP_IC1 (lic))
 337         continue;
 338
 339       /* if ifx then check the condition */
 340       if (lic->op == IFX &&
 341           isOperandEqual (IC_COND (lic), op))
 342         return lic;
 343
 344       if (lic->op == JUMPTABLE &&
 345           isOperandEqual (IC_JTCOND (lic), op))
 346         return lic;
 347
 348       if (IC_RIGHT (lic) &&
 349           isOperandEqual (IC_RIGHT (lic), op))
 350         return lic;
 351
 352       if (IC_LEFT (lic) &&
 353           isOperandEqual (IC_LEFT (lic), op))
 354         return lic;
 355
 356       /* for a pointer assignment usage */
 357       if (POINTER_SET (lic) &&
 358           isOperandEqual (op, IC_RESULT (lic)))
 359         return lic;
 360       else if (IC_RESULT (lic) && isOperandEqual (IC_RESULT (lic), op))
 361         return NULL;
 362     }
 363
 364   return NULL;
 365 }
 366
 367
 368
 369 /*-----------------------------------------------------------------*/
 370 /* isDefAlive - will return true if definiton reaches a block & used */
 371 /*-----------------------------------------------------------------*/
 372 DEFSETFUNC (isDefAlive)
 373 {
 374   eBBlock *ebp = item;
 375   V_ARG (iCode *, diCode);
 376
 377   if (ebp->visited)
 378     return 0;
 379
 380   ebp->visited = 1;
 381
 382   /* if this definition is used in the block */
 383   if (bitVectBitValue (ebp->usesDefs, diCode->key))
 384     return 1;
 385
 386   return applyToSet (ebp->succList, isDefAlive, diCode);
 387 }