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