1 /*-------------------------------------------------------------------------
3 SDCCdflow.c - source file for data flow analysis and other utility
4 routines related to data flow.
6 Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
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
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.
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.
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 -------------------------------------------------------------------------*/
29 /*-----------------------------------------------------------------*/
30 /* ifKilledInBlock - will return 1 if the symbol is redefined in B */
31 /*-----------------------------------------------------------------*/
32 DEFSETFUNC (ifKilledInBlock)
35 V_ARG (eBBlock *, src);
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)
43 /* if this is pointer get then it will be killed
44 if there is a pointer set for the same pointer
46 if (POINTER_GET (cdp->diCode) &&
47 bitVectBitValue (src->ptrsSet,
48 IC_LEFT (cdp->diCode)->key))
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))))
60 /* if we find it in the defSet of this block */
61 if (bitVectBitsInCommon (src->defSet, OP_DEFS (cdp->sym)))
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),
69 if (bitVectBitsInCommon (outs, OP_DEFS (cdp->sym)))
71 setToNull ((void *) &outs);
75 setToNull ((void *) &outs);
77 /* if the operands of this one was changed in the block */
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))))))
86 /* kill if cseBBlock() found a case we missed here */
87 if (isinSetWith(src->killedExprs, cdp, isCseDefEqual))
93 /*-----------------------------------------------------------------*/
94 /* mergeInExprs - copy the in expression if it dominates */
95 /*-----------------------------------------------------------------*/
96 DEFSETFUNC (mergeInExprs)
99 V_ARG (eBBlock *, dest);
100 V_ARG (int *, firstTime);
102 dest->killedExprs = unionSets (dest->killedExprs, ebp->killedExprs, THROW_DEST);
104 /* if in the dominator list then */
105 if (bitVectBitValue (dest->domVect, ebp->bbnum) && dest != ebp)
107 /* if already present then intersect */
108 if (!dest->inExprs && *firstTime)
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);
117 dest->inExprs = intersectSets (dest->inExprs,
120 dest->inPtrsSet = bitVectUnion (dest->inPtrsSet, ebp->ptrsSet);
121 dest->ndompset = bitVectUnion (dest->ndompset, ebp->ndompset);
127 // dest->inExprs = intersectSets (dest->inExprs, ebp->outExprs, THROW_DEST);
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);
140 /*-----------------------------------------------------------------*/
141 /* mergeInDefs - merge in incoming definitions */
142 /*-----------------------------------------------------------------*/
143 DEFSETFUNC (mergeInDefs)
146 V_ARG (eBBlock *, dest);
147 V_ARG (int *, firstTime);
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);
154 dest->inDefs = bitVectUnion (dest->inDefs,
164 /*-----------------------------------------------------------------*/
165 /* computeDataFlow - does computations for data flow accross blocks */
166 /*-----------------------------------------------------------------*/
168 computeDataFlow (ebbIndex * ebbi)
170 eBBlock ** ebbs = ebbi->dfOrder;
171 int count = ebbi->count;
175 for (i = 0; i < count; i++)
176 ebbs[i]->killedExprs = NULL;
183 for (i = 0; i < count; i++)
187 set *oldOutExprs = NULL;
188 set *oldKilledExprs = NULL;
189 bitVect *oldOutDefs = NULL;
193 /* if this is the entry block then continue */
194 /* since entry block can never have any inExprs */
198 /* get blocks that can come to this block */
199 pred = edgesTo (ebbs[i]);
201 /* make a copy of the outExpressions and outDefs : to be */
202 /* used for iteration */
203 if (optimize.global_cse)
205 oldOutExprs = setFromSet (ebbs[i]->outExprs);
206 oldKilledExprs = setFromSet (ebbs[i]->killedExprs);
208 oldOutDefs = bitVectCopy (ebbs[i]->outDefs);
209 setToNull ((void *) &ebbs[i]->inDefs);
211 /* indefitions are easy just merge them by union */
212 /* these are the definitions that can possibly */
213 /* reach this block */
215 applyToSet (pred, mergeInDefs, ebbs[i], &firstTime);
217 /* if none of the edges coming to this block */
218 /* dominate this block then add the immediate dominator */
219 /* of this block to the list of predecessors */
220 for (pBlock = setFirstItem (pred); pBlock;
221 pBlock = setNextItem (pred))
223 if (bitVectBitValue (ebbs[i]->domVect, pBlock->bbnum))
227 /* get the immediate dominator and put it there */
230 eBBlock *idom = immedDom (ebbi, ebbs[i]);
232 addSetHead (&pred, idom);
235 /* figure out the incoming expressions */
236 /* this is a little more complex */
237 setToNull ((void *) &ebbs[i]->inExprs);
238 if (optimize.global_cse)
241 applyToSet (pred, mergeInExprs, ebbs[i], &firstTime);
243 setToNull ((void *) &pred);
245 /* do cse with computeOnly flag set to TRUE */
246 /* this by far the quickest way of computing */
247 cseBBlock (ebbs[i], TRUE, ebbi);
249 /* if it change we will need to iterate */
250 if (optimize.global_cse)
252 change += !isSetsEqualWith (ebbs[i]->outExprs, oldOutExprs, isCseDefEqual);
253 change += !isSetsEqualWith (ebbs[i]->killedExprs, oldKilledExprs, isCseDefEqual);
255 change += !bitVectEqual (ebbs[i]->outDefs, oldOutDefs);
258 if (!change) /* iterate till no change */
265 /*-----------------------------------------------------------------*/
266 /* usedBetweenPoints - used between start & end */
267 /*-----------------------------------------------------------------*/
269 usedBetweenPoints (operand * op, iCode * start, iCode * end)
273 for (; lic != end; lic = lic->next)
276 /* if the operand is a parameter */
277 /* then check for calls and return */
278 /* true if there is a call */
283 if (lic->op == CALL) {
284 args=FUNC_ARGS(OP_SYMBOL(IC_LEFT(lic))->type);
286 args=FUNC_ARGS(OP_SYMBOL(IC_LEFT(lic))->type->next);
288 if (isParameterToCall (args, op))
295 /* if ifx then check the condition */
296 if (lic->op == IFX &&
297 IC_COND (lic)->key == op->key)
300 if (lic->op == JUMPTABLE &&
301 IC_JTCOND (lic)->key == op->key)
304 if (IC_RIGHT (lic) &&
305 IC_RIGHT (lic)->key == op->key)
309 IC_LEFT (lic)->key == op->key)
312 /* for a pointer assignment usage */
313 if (POINTER_SET (lic) &&
314 op->key == IC_RESULT (lic)->key)
316 else if (IC_RESULT (lic) && op->key == IC_RESULT (lic)->key)
325 /*-----------------------------------------------------------------*/
326 /* usedInRemaining - returns point of usage for an operand if found */
327 /*-----------------------------------------------------------------*/
329 usedInRemaining (operand * op, iCode * ic)
336 for (; lic; lic = lic->next)
339 /* if the operand is a parameter */
340 /* then check for calls and return */
341 /* true if there is a call */
342 /* if this is a global variable then
344 if (lic->op == CALL || lic->op == PCALL)
347 if (lic->op == CALL) {
348 args=FUNC_ARGS(OP_SYMBOL(IC_LEFT(lic))->type);
350 args=FUNC_ARGS(operandType(IC_LEFT(lic))->next);
353 isParameterToCall (args, op)) ||
354 isOperandGlobal (op))
358 if (ic->op == SEND &&
359 isOperandEqual (IC_LEFT (lic), op))
365 /* if ifx then check the condition */
366 if (lic->op == IFX &&
367 isOperandEqual (IC_COND (lic), op))
370 if (lic->op == JUMPTABLE &&
371 isOperandEqual (IC_JTCOND (lic), op))
374 if (IC_RIGHT (lic) &&
375 isOperandEqual (IC_RIGHT (lic), op))
379 isOperandEqual (IC_LEFT (lic), op))
382 /* for a pointer assignment usage */
383 if (POINTER_SET (lic) &&
384 isOperandEqual (op, IC_RESULT (lic)))
386 else if (IC_RESULT (lic) && isOperandEqual (IC_RESULT (lic), op))
395 /*-----------------------------------------------------------------*/
396 /* isDefAlive - will return true if definiton reaches a block & used */
397 /*-----------------------------------------------------------------*/
398 DEFSETFUNC (isDefAlive)
401 V_ARG (iCode *, diCode);
408 /* if this definition is used in the block */
409 if (bitVectBitValue (ebp->usesDefs, diCode->key))
412 return applyToSet (ebp->succList, isDefAlive, diCode);