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