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 #include <stdio.h>
  27 #include <stdlib.h>
  28 #include "SDCCglobl.h"
  29 #include "SDCCast.h"
  30 #include "SDCCmem.h"
  31 #include "SDCCy.h"
  32 #include "SDCChasht.h"
  33 #include "SDCCbitv.h"
  34 #include "SDCCset.h"
  35 #include "SDCCicode.h"
  36 #include "SDCClabel.h"
  37 #include "SDCCBBlock.h"
  38 #include "SDCCloop.h"
  39 #include "SDCCcse.h"
  40 #include "SDCCcflow.h"
  41 #include "SDCCdflow.h"
  42
  43 /*-----------------------------------------------------------------*/
  44 /* ifKilledInBlock - will return 1 if the symbol is redefined in B */
  45 /*-----------------------------------------------------------------*/
  46 DEFSETFUNC(ifKilledInBlock)
  47 {
  48     cseDef *cdp = item;
  49     V_ARG(eBBlock *,src);
  50     bitVect *outs ;
  51
  52     /* if this is a global variable and this block
  53        has a function call then delete it */
  54     if (isOperandGlobal(cdp->sym) && src->hasFcall)
  55         return 1;
  56
  57     /* if this is pointer get then it will be killed
  58        if there is a pointer set for the same pointer
  59        in this block */
  60     if (POINTER_GET(cdp->diCode) &&
  61         bitVectBitValue(src->ptrsSet,
  62                         IC_LEFT(cdp->diCode)->key))
  63         return 1;
  64
  65     /* if assignment to iTmep then if right is defined
  66        elsewhere kill this one */
  67     if (ASSIGNMENT(cdp->diCode)   &&
  68         !POINTER_SET(cdp->diCode) &&
  69         IS_ITEMP(IC_RESULT(cdp->diCode)) &&
  70         IS_SYMOP(IC_RIGHT(cdp->diCode))  &&
  71         bitVectBitsInCommon(src->outDefs,OP_DEFS(IC_RIGHT(cdp->diCode))))
  72         return 1;
  73
  74     /* if we find it in the defSet of this block */
  75     if (bitVectBitsInCommon(src->defSet,OP_DEFS(cdp->sym)))
  76         return 1;
  77
  78     /* if in the outdef we find a definition other than this one */
  79     /* to do this we make a copy of the out definitions and turn */
  80     /* this one off then check if there are other definitions    */
  81     bitVectUnSetBit (outs = bitVectCopy (src->outDefs),
  82                      cdp->diCode->key);
  83     if (bitVectBitsInCommon (outs,OP_DEFS(cdp->sym))) {
  84         setToNull((void **) &outs);
  85         return 1;
  86     }
  87
  88     setToNull((void **) &outs);
  89
  90     /* if the operands of this one was changed in the block */
  91     /* then delete it */
  92     if (cdp->diCode &&
  93         ( (IS_SYMOP(IC_LEFT(cdp->diCode)) &&
  94            bitVectBitsInCommon (src->defSet,OP_DEFS(IC_LEFT(cdp->diCode)))) ||
  95           (IS_SYMOP(IC_RIGHT(cdp->diCode)) &&
  96            bitVectBitsInCommon (src->defSet,OP_DEFS(IC_RIGHT(cdp->diCode)))) ))
  97         return 1;
  98
  99     return 0;
 100 }
 101
 102 /*-----------------------------------------------------------------*/
 103 /* mergeInExprs - copy the in expression if it dominates           */
 104 /*-----------------------------------------------------------------*/
 105 DEFSETFUNC(mergeInExprs)
 106 {
 107     eBBlock *ebp = item;
 108     V_ARG(eBBlock *,dest);
 109     V_ARG(int *,firstTime);
 110
 111     /* if in the dominator list then */
 112     if (bitVectBitValue(dest->domVect,ebp->bbnum) && dest != ebp) {
 113         /* if already present then intersect */
 114         if (!dest->inExprs && *firstTime)
 115             dest->inExprs = setFromSet(ebp->outExprs);
 116         else
 117             dest->inExprs = intersectSets (dest->inExprs,
 118                                            ebp->outExprs,
 119                                            THROW_DEST);
 120         /* copy the pointer set from the dominator */
 121         dest->inPtrsSet = bitVectCopy(ebp->ptrsSet);
 122     }
 123     else
 124         /* delete only if killed in this block */
 125         deleteItemIf (&dest->inExprs,ifKilledInBlock, ebp);
 126
 127     *firstTime = 0;
 128
 129     return 0;
 130 }
 131
 132 /*-----------------------------------------------------------------*/
 133 /* mergeInDefs - merge in incoming definitions                     */
 134 /*-----------------------------------------------------------------*/
 135 DEFSETFUNC(mergeInDefs)
 136 {
 137     eBBlock *ebp = item ;
 138     V_ARG(eBBlock *,dest);
 139     V_ARG(int *,firstTime);
 140
 141     /* the in definition is the union of the out */
 142     /* of all blocks that come to this block     */
 143     if (!dest->inDefs && *firstTime)
 144         dest->inDefs = bitVectCopy (ebp->outDefs);
 145     else
 146         dest->inDefs = bitVectUnion (dest->inDefs,
 147                                      ebp->outDefs) ;
 148
 149     *firstTime = 0;
 150
 151     return 0;
 152
 153 }
 154
 155 /*-----------------------------------------------------------------*/
 156 /* computeDataFlow - does computations for data flow accross blocks*/
 157 /*-----------------------------------------------------------------*/
 158 void computeDataFlow (eBBlock **ebbs, int count)
 159 {
 160     int i;
 161     int change = 1;
 162
 163     while (change) {
 164
 165         change = 0;
 166
 167         /* for all blocks */
 168         for ( i = 0 ; i < count ; i++ ) {
 169
 170             set *pred ;
 171             set *oldOut;
 172             int firstTime ;
 173             eBBlock *pBlock ;
 174
 175             /* if this is the entry block then continue     */
 176             /* since entry block can never have any inExprs */
 177             if (ebbs[i]->noPath)
 178                 continue ;
 179
 180             /* get blocks that can come to this block */
 181             pred = edgesTo(ebbs[i]);
 182
 183             /* make a copy of the outExpressions : to be */
 184             /* used for iteration   */
 185             oldOut = setFromSet(ebbs[i]->outExprs);
 186             setToNull ((void **)&ebbs[i]->inDefs);
 187
 188             /* indefitions are easy just merge them by union */
 189             /* these are the definitions that can possibly   */
 190             /* reach this block                              */
 191             firstTime = 1;
 192             applyToSet(pred,mergeInDefs,ebbs[i],&firstTime);
 193
 194
 195             /* if none of the edges coming to this block */
 196             /* dominate this block then add the immediate dominator */
 197             /* of this block to the list of predecessors */
 198             for ( pBlock = setFirstItem(pred); pBlock ;
 199                   pBlock = setNextItem(pred)) {
 200                 if (bitVectBitValue(ebbs[i]->domVect,pBlock->bbnum))
 201                     break ;
 202             }
 203
 204             /* get the immediate dominator and put it there */
 205             if (!pBlock) {
 206                 eBBlock *idom = immedDom(ebbs,ebbs[i]);
 207                 if (idom)
 208                     addSetHead (&pred,idom);
 209             }
 210
 211             /* figure out the incoming expressions */
 212             /* this is a little more complex       */
 213             setToNull ((void **)&ebbs[i]->inExprs);
 214             firstTime = 1;
 215             applyToSet(pred,mergeInExprs,ebbs[i],&firstTime);
 216
 217             setToNull ((void **)&pred);
 218
 219             /* do cse with computeOnly flag set to TRUE */
 220             /* this by far the quickest way of computing*/
 221             cseBBlock(ebbs[i],TRUE,ebbs,count);
 222
 223             /* if it change we will need to iterate */
 224             change += ! isSetsEqualWith(ebbs[i]->outExprs,oldOut,isCseDefEqual);
 225         }
 226
 227         if (!change) /* iterate till no change */
 228             break ;
 229     }
 230
 231     return ;
 232 }
 233
 234 /*-----------------------------------------------------------------*/
 235 /* usedBetweenPoints - used between start & end                    */
 236 /*-----------------------------------------------------------------*/
 237 int usedBetweenPoints ( operand *op, iCode *start, iCode *end )
 238 {
 239     iCode *lic = start;
 240
 241       for (;lic != end; lic = lic->next) {
 242
 243         /* if the operand is a parameter */
 244         /* then check for calls and return */
 245         /* true if there is a call       */
 246         if (IS_PARM(op) &&
 247             ( lic->op == CALL ||
 248               lic->op == PCALL ))
 249             if ( isParameterToCall(IC_ARGS(lic),op))
 250                 return 1;
 251
 252         if (SKIP_IC2(lic))
 253             continue ;
 254
 255         /* if ifx then check the condition */
 256         if (lic->op == IFX &&
 257             IC_COND(lic)->key == op->key )
 258             return 1;
 259
 260         if (lic->op == JUMPTABLE &&
 261             IC_JTCOND(lic)->key == op->key )
 262             return 1;
 263
 264         if (IC_RIGHT(lic) &&
 265             IC_RIGHT(lic)->key == op->key )
 266             return 1;
 267
 268         if (IC_LEFT(lic) &&
 269             IC_LEFT(lic)->key == op->key  )
 270             return 1;
 271
 272         /* for a pointer assignment usage */
 273         if (POINTER_SET(lic) &&
 274             op->key == IC_RESULT(lic)->key )
 275             return 1;
 276         else
 277             if (IC_RESULT(lic) && op->key == IC_RESULT(lic)->key)
 278                 return 0;
 279     }
 280
 281     return 0;
 282
 283 }
 284
 285
 286 /*-----------------------------------------------------------------*/
 287 /* usedInRemaining - returns point of usage for an operand if found*/
 288 /*-----------------------------------------------------------------*/
 289 iCode *usedInRemaining (operand *op, iCode *ic)
 290 {
 291     iCode *lic = ic;
 292
 293     if (!IS_SYMOP(op))
 294         return 0;
 295
 296     for (;lic; lic = lic->next) {
 297
 298         /* if the operand is a parameter */
 299         /* then check for calls and return */
 300         /* true if there is a call       */
 301         /* if this is a global variable then
 302            return true */
 303         if ( lic->op == CALL || lic->op == PCALL ) {
 304
 305             if ((IS_PARM(op) &&
 306                 isParameterToCall(IC_ARGS(lic),op)) ||
 307                 isOperandGlobal (op))
 308                 return lic;
 309         }
 310
 311         if (ic->op == SEND &&
 312             isOperandEqual (IC_LEFT(lic),op))
 313             return lic;
 314
 315         if (SKIP_IC1(lic))
 316             continue ;
 317
 318         /* if ifx then check the condition */
 319         if (lic->op == IFX &&
 320             isOperandEqual (IC_COND(lic),op))
 321             return lic;
 322
 323         if (lic->op == JUMPTABLE &&
 324             isOperandEqual (IC_JTCOND(lic),op) )
 325             return lic;
 326
 327         if (IC_RIGHT(lic) &&
 328             isOperandEqual(IC_RIGHT(lic),op))
 329             return lic;
 330
 331         if (IC_LEFT(lic) &&
 332             isOperandEqual(IC_LEFT(lic),op) )
 333             return lic;
 334
 335         /* for a pointer assignment usage */
 336         if (POINTER_SET(lic) &&
 337             isOperandEqual (op,IC_RESULT(lic)))
 338             return lic;
 339         else
 340             if (IC_RESULT(lic) && isOperandEqual(IC_RESULT(lic),op))
 341                 return NULL;
 342     }
 343
 344     return NULL;
 345 }
 346
 347
 348
 349 /*-----------------------------------------------------------------*/
 350 /* isDefAlive - will return true if definiton reaches a block & used */
 351 /*-----------------------------------------------------------------*/
 352 DEFSETFUNC(isDefAlive)
 353 {
 354     eBBlock *ebp = item;
 355     V_ARG(iCode *,diCode);
 356
 357     if (ebp->visited)
 358         return 0;
 359
 360     ebp->visited = 1;
 361
 362     /* if this definition is used in the block */
 363     if (bitVectBitValue(ebp->usesDefs,diCode->key))
 364         return 1;
 365
 366     return applyToSet(ebp->succList,isDefAlive,diCode);
 367 }
 368