1 /*-------------------------------------------------------------------------
3 SDCCcflow.c - source file for control flow analysis
5 Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
7 This program is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 2, or (at your option) any
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
21 In other words, you are welcome to use, share and improve this program.
22 You are forbidden to forbid anyone else to use, share and improve
23 what you give them. Help stamp out software-hoarding!
24 -------------------------------------------------------------------------*/
28 /*-----------------------------------------------------------------*/
29 /* domSetFromVect - creates a domset from the vector */
30 /*-----------------------------------------------------------------*/
32 domSetFromVect (eBBlock ** ebbs, bitVect * domVect)
40 for (i = 0; i < domVect->size; i++)
41 if (bitVectBitValue (domVect, i))
42 addSet (&domSet, ebbs[i]);
47 /*-----------------------------------------------------------------*/
48 /* addSuccessor - will add bb to succ also add it to the pred of */
50 /*-----------------------------------------------------------------*/
52 addSuccessor (eBBlock * thisBlock, eBBlock * succ)
54 /* check for boundary conditions */
55 if (!thisBlock || !succ)
58 /* add it to the succ of thisBlock */
59 addSetIfnotP (&thisBlock->succList, succ);
62 bitVectSetBit (thisBlock->succVect, succ->bbnum);
63 /* add this edge to the list of edges */
64 addSet (&graphEdges, newEdge (thisBlock, succ));
68 /*-----------------------------------------------------------------*/
69 /* eBBPredecessors - find the predecessors for each block */
70 /*-----------------------------------------------------------------*/
72 eBBPredecessors (eBBlock ** ebbs, int count)
76 /* for each block do */
77 for (i = 0; i < count; i++)
80 /* if there is no path to this then continue */
84 /* for each successor of this block if */
85 /* it has depth first number > this block */
86 /* then this block precedes the successor */
87 for (j = 0; j < ebbs[i]->succVect->size; j++)
89 if (bitVectBitValue (ebbs[i]->succVect, j) &&
90 ebbs[j]->dfnum > ebbs[i]->dfnum)
92 addSet (&ebbs[j]->predList, ebbs[i]);
96 /*-----------------------------------------------------------------*/
97 /* eBBSuccessors- find out the successors of all the nodes */
98 /*-----------------------------------------------------------------*/
100 eBBSuccessors (eBBlock ** ebbs, int count)
104 /* for all the blocks do */
105 for (; i < count; i++)
112 ebbs[i]->succVect = newBitVect (count);
114 /* if the next on exists & this one does not */
115 /* end in a GOTO or RETURN then the next is */
116 /* a natural successor of this. Note we have */
117 /* consider eBBlocks with no instructions */
124 if (ebbs[i]->ech->op != GOTO &&
125 ebbs[i]->ech->op != RETURN &&
126 ebbs[i]->ech->op != JUMPTABLE)
131 while (ebbs[j] && ebbs[j]->noPath)
134 addSuccessor (ebbs[i], ebbs[j]); /* add it */
136 } /* no instructions in the block */
137 /* could happen for dummy blocks */
139 addSuccessor (ebbs[i], ebbs[i + 1]);
142 /* go thru all the instructions: if we find a */
143 /* goto or ifx or a return then we have a succ */
144 if ((ic = ebbs[i]->ech))
148 /* special case for jumptable */
149 if (ic->op == JUMPTABLE)
152 for (lbl = setFirstItem (IC_JTLABELS (ic)); lbl;
153 lbl = setNextItem (IC_JTLABELS (ic)))
154 addSuccessor (ebbs[i],
155 eBBWithEntryLabel (ebbs, lbl, count));
161 /* depending on the instruction operator */
164 case GOTO: /* goto has edge to label */
165 succ = eBBWithEntryLabel (ebbs, ic->argLabel.label, count);
168 case IFX: /* conditional jump */
169 /* if true label is present */
171 succ = eBBWithEntryLabel (ebbs, IC_TRUE (ic), count);
173 succ = eBBWithEntryLabel (ebbs, IC_FALSE (ic), count);
176 case RETURN: /* block with return */
177 succ = eBBWithEntryLabel (ebbs, returnLabel, count);
181 /* if there is a successor add to the list */
182 /* if it is not already present in the list */
184 addSuccessor (ebbs[i], succ);
190 /*-----------------------------------------------------------------*/
191 /* computeDominance - computes the dominance graph */
192 /* for algorithm look at Dragon book section 10.10, algo 10.16 */
193 /*-----------------------------------------------------------------*/
195 computeDominance (eBBlock ** ebbs, int count)
199 /* now do the initialisation */
200 /* D(n0) := { n0 } */
202 bitVectSetBit (ebbs[0]->domVect = newBitVect (count), ebbs[0]->bbnum);
205 /* for n in N - { n0 } do D(n) = N */
206 for (i = 1; i < count; i++)
208 ebbs[i]->domVect = newBitVect (count);
209 for (j = 0; j < count; j++)
212 bitVectSetBit (ebbs[i]->domVect, ebbs[j]->bbnum);
216 /* end of initialisation */
218 /* while changes to any D(n) occur do */
219 /* for n in N - { n0 } do */
220 /* D(n) := { n } U (intersection of D( all predecessors of n)) */
226 for (i = 1; i < count; i++)
233 /* get the intersection of the dominance of all predecessors */
234 for (pred = setFirstItem (ebbs[i]->predList),
235 cDomVect = (pred ? bitVectCopy (pred->domVect) : NULL);
237 pred = setNextItem (ebbs[i]->predList))
239 cDomVect = bitVectIntersect (cDomVect, pred->domVect);
242 cDomVect = newBitVect (count);
243 /* this node to the list */
244 cDomVect = bitVectSetBit (cDomVect, ebbs[i]->bbnum);
247 if (!bitVectEqual (cDomVect, ebbs[i]->domVect))
249 ebbs[i]->domVect = cDomVect;
254 /* if no change then exit */
260 /*-----------------------------------------------------------------*/
261 /* immedDom - returns the immediate dominator of a block */
262 /*-----------------------------------------------------------------*/
264 immedDom (eBBlock ** ebbs, eBBlock * ebp)
266 /* first delete self from the list */
267 set *iset = domSetFromVect (ebbs, ebp->domVect);
269 eBBlock *idom = NULL;
271 deleteSetItem (&iset, ebp);
272 /* then just return the one with the greatest */
273 /* depthfirst number, this will be the immed dominator */
274 if ((loop = setFirstItem (iset)))
276 for (; loop; loop = setNextItem (iset))
277 if (loop->dfnum > idom->dfnum)
280 setToNull ((void **) &iset);
285 /*-----------------------------------------------------------------*/
286 /* DFOrdering - is visited then nothing else call DFOrdering this */
287 /*-----------------------------------------------------------------*/
288 DEFSETFUNC (DFOrdering)
290 eBBlock *ebbp = item;
291 V_ARG (int *, count);
296 computeDFOrdering (ebbp, count); /* depthfirst */
301 /*-----------------------------------------------------------------*/
302 /* computeDFOrdering - computes the depth first ordering of the */
304 /*-----------------------------------------------------------------*/
306 computeDFOrdering (eBBlock * ebbp, int *count)
310 /* for each successor that is not visited */
311 applyToSet (ebbp->succList, DFOrdering, count);
313 /* set the depth first number */
314 ebbp->dfnum = *count;
318 /*-----------------------------------------------------------------*/
319 /* disconBBlock - removes all control flow links for a block */
320 /*-----------------------------------------------------------------*/
322 disconBBlock (eBBlock * ebp, eBBlock ** ebbs, int count)
324 /* mark this block as noPath & recompute control flow */
326 computeControlFlow (ebbs, count, TRUE);
329 /*-----------------------------------------------------------------*/
330 /* markNoPath - marks those blocks which cannot be reached from top */
331 /*-----------------------------------------------------------------*/
333 markNoPath (eBBlock ** ebbs, int count)
338 /* for all blocks if the visited flag is not set : then there */
339 /* is no path from _entry to this block push them down in the */
340 /* depth first order */
341 for (i = 0; i < count; i++)
342 if (!ebbs[i]->visited)
345 /*-----------------------------------------------------------------*/
346 /* dfNumCompare - used by qsort to sort by dfNumber */
347 /*-----------------------------------------------------------------*/
349 dfNumCompare (const void *a, const void *b)
351 const eBBlock *const *i = a;
352 const eBBlock *const *j = b;
354 if ((*i)->dfnum > (*j)->dfnum)
357 if ((*i)->dfnum < (*j)->dfnum)
363 /*-----------------------------------------------------------------*/
364 /* bbNumCompare - used by qsort to sort by bbNumber */
365 /*-----------------------------------------------------------------*/
367 bbNumCompare (const void *a, const void *b)
369 const eBBlock *const *i = a;
370 const eBBlock *const *j = b;
372 if ((*i)->bbnum > (*j)->bbnum)
375 if ((*i)->bbnum < (*j)->bbnum)
382 /*-----------------------------------------------------------------*/
383 /* computeControlFlow - does the control flow computation */
384 /*-----------------------------------------------------------------*/
386 computeControlFlow (eBBlock ** ebbs, int count, int reSort)
388 int saveCount = count;
391 /* initialise some things */
393 for (i = 0; i < count; i++)
395 setToNull ((void **) &ebbs[i]->predList);
396 setToNull ((void **) &ebbs[i]->domVect);
397 setToNull ((void **) &ebbs[i]->succList);
398 setToNull ((void **) &ebbs[i]->succVect);
399 ebbs[i]->visited = 0;
404 /* sort it back by block number */
405 qsort (ebbs, saveCount, sizeof (eBBlock *), bbNumCompare);
407 setToNull ((void **) &graphEdges);
408 /* this will put in the */
409 /* successor information for each blk */
410 eBBSuccessors (ebbs, count);
412 /* compute the depth first ordering */
413 computeDFOrdering (ebbs[0], &count);
415 /* mark blocks with no paths to them */
416 markNoPath (ebbs, saveCount);
418 /* with the depth first info in place */
419 /* add the predecessors for the blocks */
420 eBBPredecessors (ebbs, saveCount);
422 /* compute the dominance graph */
423 computeDominance (ebbs, saveCount);
425 /* sort it by dfnumber */
426 qsort (ebbs, saveCount, sizeof (eBBlock *), dfNumCompare);
430 /*-----------------------------------------------------------------*/
431 /* returnAtEnd - returns 1 if Basic Block has a return at the end */
433 /*-----------------------------------------------------------------*/
434 int returnAtEnd (eBBlock *ebp)
437 This basic block ends in a return statment
439 if (ebp->ech && ebp->ech->op == RETURN) return 1;
442 This basic block has only one successor and that
443 successor has only one return statement
445 if (elementsInSet(ebp->succList) == 1) {
446 eBBlock *succ = setFirstItem(ebp->succList);
447 /* could happen for dummy blocks */
448 if (!succ->sch || !succ->ech) return 0;
450 /* first iCode is a return */
451 if (succ->sch->op == RETURN) return 2;
453 /* or first iCode is a label & the next &
454 last icode is a return */
455 if (succ->sch->op == LABEL && succ->sch->next == succ->ech &&
456 succ->ech->op == RETURN ) return 2;