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 */
123 if (ebbs[i]->ech->op != GOTO &&
124 ebbs[i]->ech->op != RETURN &&
125 ebbs[i]->ech->op != JUMPTABLE)
129 while (ebbs[j] && ebbs[j]->noPath)
132 addSuccessor (ebbs[i], ebbs[j]); /* add it */
138 if (ebbs[j]->ech && ebbs[j]->ech->op==IFX &&
139 (isSymbolEqual(IC_TRUE(ebbs[j]->ech), ebbs[i]->entryLabel) ||
140 isSymbolEqual(IC_FALSE(ebbs[j]->ech), ebbs[i]->entryLabel))) {
141 ebbs[i]->hasConditionalExit=1;
145 } /* no instructions in the block */
146 /* could happen for dummy blocks */
148 addSuccessor (ebbs[i], ebbs[i + 1]);
151 /* go thru all the instructions: if we find a */
152 /* goto or ifx or a return then we have a succ */
153 if ((ic = ebbs[i]->ech))
157 /* special case for jumptable */
158 if (ic->op == JUMPTABLE)
161 for (lbl = setFirstItem (IC_JTLABELS (ic)); lbl;
162 lbl = setNextItem (IC_JTLABELS (ic)))
163 addSuccessor (ebbs[i],
164 eBBWithEntryLabel (ebbs, lbl, count));
170 /* depending on the instruction operator */
173 case GOTO: /* goto has edge to label */
174 succ = eBBWithEntryLabel (ebbs, ic->label, count);
177 case IFX: /* conditional jump */
178 /* if true label is present */
180 succ = eBBWithEntryLabel (ebbs, IC_TRUE (ic), count);
182 succ = eBBWithEntryLabel (ebbs, IC_FALSE (ic), count);
185 case RETURN: /* block with return */
186 succ = eBBWithEntryLabel (ebbs, returnLabel, count);
190 /* if there is a successor add to the list */
191 /* if it is not already present in the list */
193 addSuccessor (ebbs[i], succ);
199 /*-----------------------------------------------------------------*/
200 /* computeDominance - computes the dominance graph */
201 /* for algorithm look at Dragon book section 10.10, algo 10.16 */
202 /*-----------------------------------------------------------------*/
204 computeDominance (eBBlock ** ebbs, int count)
208 /* now do the initialisation */
209 /* D(n0) := { n0 } */
211 bitVectSetBit (ebbs[0]->domVect = newBitVect (count), ebbs[0]->bbnum);
214 /* for n in N - { n0 } do D(n) = N */
215 for (i = 1; i < count; i++)
217 ebbs[i]->domVect = newBitVect (count);
218 for (j = 0; j < count; j++)
221 bitVectSetBit (ebbs[i]->domVect, ebbs[j]->bbnum);
225 /* end of initialisation */
227 /* while changes to any D(n) occur do */
228 /* for n in N - { n0 } do */
229 /* D(n) := { n } U (intersection of D( all predecessors of n)) */
235 for (i = 1; i < count; i++)
242 /* get the intersection of the dominance of all predecessors */
243 for (pred = setFirstItem (ebbs[i]->predList),
244 cDomVect = (pred ? bitVectCopy (pred->domVect) : NULL);
246 pred = setNextItem (ebbs[i]->predList))
248 cDomVect = bitVectIntersect (cDomVect, pred->domVect);
251 cDomVect = newBitVect (count);
252 /* this node to the list */
253 cDomVect = bitVectSetBit (cDomVect, ebbs[i]->bbnum);
256 if (!bitVectEqual (cDomVect, ebbs[i]->domVect))
258 ebbs[i]->domVect = cDomVect;
263 /* if no change then exit */
269 /*-----------------------------------------------------------------*/
270 /* immedDom - returns the immediate dominator of a block */
271 /*-----------------------------------------------------------------*/
273 immedDom (eBBlock ** ebbs, eBBlock * ebp)
275 /* first delete self from the list */
276 set *iset = domSetFromVect (ebbs, ebp->domVect);
278 eBBlock *idom = NULL;
280 deleteSetItem (&iset, ebp);
281 /* then just return the one with the greatest */
282 /* depthfirst number, this will be the immed dominator */
283 if ((loop = setFirstItem (iset)))
285 for (; loop; loop = setNextItem (iset))
286 if (loop->dfnum > idom->dfnum)
289 setToNull ((void **) &iset);
294 /*-----------------------------------------------------------------*/
295 /* DFOrdering - is visited then nothing else call DFOrdering this */
296 /*-----------------------------------------------------------------*/
297 DEFSETFUNC (DFOrdering)
299 eBBlock *ebbp = item;
300 V_ARG (int *, count);
305 computeDFOrdering (ebbp, count); /* depthfirst */
310 /*-----------------------------------------------------------------*/
311 /* computeDFOrdering - computes the depth first ordering of the */
313 /*-----------------------------------------------------------------*/
315 computeDFOrdering (eBBlock * ebbp, int *count)
319 /* for each successor that is not visited */
320 applyToSet (ebbp->succList, DFOrdering, count);
322 /* set the depth first number */
323 ebbp->dfnum = *count;
327 /*-----------------------------------------------------------------*/
328 /* disconBBlock - removes all control flow links for a block */
329 /*-----------------------------------------------------------------*/
331 disconBBlock (eBBlock * ebp, eBBlock ** ebbs, int count)
333 /* mark this block as noPath & recompute control flow */
335 computeControlFlow (ebbs, count, TRUE);
338 /*-----------------------------------------------------------------*/
339 /* markNoPath - marks those blocks which cannot be reached from top */
340 /*-----------------------------------------------------------------*/
342 markNoPath (eBBlock ** ebbs, int count)
347 /* for all blocks if the visited flag is not set : then there */
348 /* is no path from _entry to this block push them down in the */
349 /* depth first order */
350 for (i = 0; i < count; i++)
351 if (!ebbs[i]->visited)
354 /*-----------------------------------------------------------------*/
355 /* dfNumCompare - used by qsort to sort by dfNumber */
356 /*-----------------------------------------------------------------*/
358 dfNumCompare (const void *a, const void *b)
360 const eBBlock *const *i = a;
361 const eBBlock *const *j = b;
363 if ((*i)->dfnum > (*j)->dfnum)
366 if ((*i)->dfnum < (*j)->dfnum)
372 /*-----------------------------------------------------------------*/
373 /* bbNumCompare - used by qsort to sort by bbNumber */
374 /*-----------------------------------------------------------------*/
376 bbNumCompare (const void *a, const void *b)
378 const eBBlock *const *i = a;
379 const eBBlock *const *j = b;
381 if ((*i)->bbnum > (*j)->bbnum)
384 if ((*i)->bbnum < (*j)->bbnum)
391 /*-----------------------------------------------------------------*/
392 /* computeControlFlow - does the control flow computation */
393 /*-----------------------------------------------------------------*/
395 computeControlFlow (eBBlock ** ebbs, int count, int reSort)
397 int saveCount = count;
400 /* initialise some things */
402 for (i = 0; i < count; i++)
404 setToNull ((void **) &ebbs[i]->predList);
405 setToNull ((void **) &ebbs[i]->domVect);
406 setToNull ((void **) &ebbs[i]->succList);
407 setToNull ((void **) &ebbs[i]->succVect);
408 ebbs[i]->visited = 0;
413 /* sort it back by block number */
414 qsort (ebbs, saveCount, sizeof (eBBlock *), bbNumCompare);
416 setToNull ((void **) &graphEdges);
417 /* this will put in the */
418 /* successor information for each blk */
419 eBBSuccessors (ebbs, count);
421 /* compute the depth first ordering */
422 computeDFOrdering (ebbs[0], &count);
424 /* mark blocks with no paths to them */
425 markNoPath (ebbs, saveCount);
427 /* with the depth first info in place */
428 /* add the predecessors for the blocks */
429 eBBPredecessors (ebbs, saveCount);
431 /* compute the dominance graph */
432 computeDominance (ebbs, saveCount);
434 /* sort it by dfnumber */
435 qsort (ebbs, saveCount, sizeof (eBBlock *), dfNumCompare);
439 /*-----------------------------------------------------------------*/
440 /* returnAtEnd - returns 1 if Basic Block has a return at the end */
442 /*-----------------------------------------------------------------*/
443 int returnAtEnd (eBBlock *ebp)
446 This basic block ends in a return statment
448 if (ebp->ech && ebp->ech->op == RETURN) return 1;
451 This basic block has only one successor and that
452 successor has only one return statement
454 if (elementsInSet(ebp->succList) == 1) {
455 eBBlock *succ = setFirstItem(ebp->succList);
456 /* could happen for dummy blocks */
457 if (!succ->sch || !succ->ech) return 0;
459 /* first iCode is a return */
460 if (succ->sch->op == RETURN) return 2;
462 /* or first iCode is a label & the next &
463 last icode is a return */
464 if (succ->sch->op == LABEL && succ->sch->next == succ->ech &&
465 succ->ech->op == RETURN ) return 2;