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