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       cseDef *expr;
 121
 122       /* cseBBlock does a much more thorough analysis than   */
 123       /* ifKilledInBlock. Anything that is listed in inExprs */
 124       /* but not in outExprs must have been killed somehow.  */
 125       for (expr=setFirstItem(ebp->inExprs); expr; expr=setNextItem(ebp->inExprs))
 126         if (!isinSet(ebp->outExprs, expr))
 127           deleteSetItem (&dest->inExprs, expr);
 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
 135   *firstTime = 0;
 136
 137   return 0;
 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 (eBBlock ** ebbs, int count)
 169 {
 170   int i;
 171   int change = 1;
 172
 173   while (change)
 174     {
 175
 176       change = 0;
 177
 178       /* for all blocks */
 179       for (i = 0; i < count; i++)
 180         {
 181
 182           set *pred;
 183           set *oldOutExprs = 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             oldOutExprs = setFromSet (ebbs[i]->outExprs);
 200           else
 201             oldOutDefs = bitVectCopy (ebbs[i]->outDefs);
 202           setToNull ((void *) &ebbs[i]->inDefs);
 203
 204           /* indefitions are easy just merge them by union */
 205           /* these are the definitions that can possibly   */
 206           /* reach this block                              */
 207           firstTime = 1;
 208           applyToSet (pred, mergeInDefs, ebbs[i], &firstTime);
 209
 210           /* if none of the edges coming to this block */
 211           /* dominate this block then add the immediate dominator */
 212           /* of this block to the list of predecessors */
 213           for (pBlock = setFirstItem (pred); pBlock;
 214                pBlock = setNextItem (pred))
 215             {
 216               if (bitVectBitValue (ebbs[i]->domVect, pBlock->bbnum))
 217                 break;
 218             }
 219
 220           /* get the immediate dominator and put it there */
 221           if (!pBlock)
 222             {
 223               eBBlock *idom = immedDom (ebbs, ebbs[i]);
 224               if (idom)
 225                 addSetHead (&pred, idom);
 226             }
 227
 228           /* figure out the incoming expressions */
 229           /* this is a little more complex       */
 230           setToNull ((void *) &ebbs[i]->inExprs);
 231           if (optimize.global_cse)
 232             {
 233               firstTime = 1;
 234               applyToSet (pred, mergeInExprs, ebbs[i], &firstTime);
 235             }
 236           setToNull ((void *) &pred);
 237
 238           /* do cse with computeOnly flag set to TRUE */
 239           /* this by far the quickest way of computing */
 240           cseBBlock (ebbs[i], TRUE, ebbs, count);
 241
 242           /* if it change we will need to iterate */
 243           if (optimize.global_cse)
 244             change += !isSetsEqualWith (ebbs[i]->outExprs, oldOutExprs, isCseDefEqual);
 245           else
 246             change += !bitVectEqual (ebbs[i]->outDefs, oldOutDefs);
 247         }
 248
 249       if (!change)              /* iterate till no change */
 250         break;
 251     }
 252
 253   return;
 254 }
 255
 256 /*-----------------------------------------------------------------*/
 257 /* usedBetweenPoints - used between start & end                    */
 258 /*-----------------------------------------------------------------*/
 259 int
 260 usedBetweenPoints (operand * op, iCode * start, iCode * end)
 261 {
 262   iCode *lic = start;
 263
 264   for (; lic != end; lic = lic->next)
 265     {
 266
 267       /* if the operand is a parameter */
 268       /* then check for calls and return */
 269       /* true if there is a call       */
 270       if (IS_PARM (op) &&
 271           (lic->op == CALL ||
 272            lic->op == PCALL)) {
 273         value *args;
 274         if (lic->op == CALL) {
 275           args=FUNC_ARGS(OP_SYMBOL(IC_LEFT(lic))->type);
 276         } else {
 277           args=FUNC_ARGS(OP_SYMBOL(IC_LEFT(lic))->type->next);
 278         }
 279         if (isParameterToCall (args, op))
 280           return 1;
 281       }
 282
 283       if (SKIP_IC2 (lic))
 284         continue;
 285
 286       /* if ifx then check the condition */
 287       if (lic->op == IFX &&
 288           IC_COND (lic)->key == op->key)
 289         return 1;
 290
 291       if (lic->op == JUMPTABLE &&
 292           IC_JTCOND (lic)->key == op->key)
 293         return 1;
 294
 295       if (IC_RIGHT (lic) &&
 296           IC_RIGHT (lic)->key == op->key)
 297         return 1;
 298
 299       if (IC_LEFT (lic) &&
 300           IC_LEFT (lic)->key == op->key)
 301         return 1;
 302
 303       /* for a pointer assignment usage */
 304       if (POINTER_SET (lic) &&
 305           op->key == IC_RESULT (lic)->key)
 306         return 1;
 307       else if (IC_RESULT (lic) && op->key == IC_RESULT (lic)->key)
 308         return 0;
 309     }
 310
 311   return 0;
 312
 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
 330       /* if the operand is a parameter */
 331       /* then check for calls and return */
 332       /* true if there is a call       */
 333       /* if this is a global variable then
 334          return true */
 335       if (lic->op == CALL || lic->op == PCALL)
 336         {
 337           value *args;
 338           if (lic->op == CALL) {
 339             args=FUNC_ARGS(OP_SYMBOL(IC_LEFT(lic))->type);
 340           } else {
 341             args=FUNC_ARGS(operandType(IC_LEFT(lic))->next);
 342           }
 343           if ((IS_PARM (op) &&
 344                isParameterToCall (args, op)) ||
 345               isOperandGlobal (op))
 346             return lic;
 347         }
 348
 349       if (ic->op == SEND &&
 350           isOperandEqual (IC_LEFT (lic), op))
 351         return lic;
 352
 353       if (SKIP_IC1 (lic))
 354         continue;
 355
 356       /* if ifx then check the condition */
 357       if (lic->op == IFX &&
 358           isOperandEqual (IC_COND (lic), op))
 359         return lic;
 360
 361       if (lic->op == JUMPTABLE &&
 362           isOperandEqual (IC_JTCOND (lic), op))
 363         return lic;
 364
 365       if (IC_RIGHT (lic) &&
 366           isOperandEqual (IC_RIGHT (lic), op))
 367         return lic;
 368
 369       if (IC_LEFT (lic) &&
 370           isOperandEqual (IC_LEFT (lic), op))
 371         return lic;
 372
 373       /* for a pointer assignment usage */
 374       if (POINTER_SET (lic) &&
 375           isOperandEqual (op, IC_RESULT (lic)))
 376         return lic;
 377       else if (IC_RESULT (lic) && isOperandEqual (IC_RESULT (lic), op))
 378         return NULL;
 379     }
 380
 381   return NULL;
 382 }
 383
 384
 385
 386 /*-----------------------------------------------------------------*/
 387 /* isDefAlive - will return true if definiton reaches a block & used */
 388 /*-----------------------------------------------------------------*/
 389 DEFSETFUNC (isDefAlive)
 390 {
 391   eBBlock *ebp = item;
 392   V_ARG (iCode *, diCode);
 393
 394   if (ebp->visited)
 395     return 0;
 396
 397   ebp->visited = 1;
 398
 399   /* if this definition is used in the block */
 400   if (bitVectBitValue (ebp->usesDefs, diCode->key))
 401     return 1;
 402
 403   return applyToSet (ebp->succList, isDefAlive, diCode);
 404 }