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 static void computeDFOrdering (eBBlock *, int *);
30 /*-----------------------------------------------------------------*/
31 /* domSetFromVect - creates a domset from the vector */
32 /*-----------------------------------------------------------------*/
34 domSetFromVect (ebbIndex *ebbi, bitVect * domVect)
42 for (i = 0; i < domVect->size; i++)
43 if (bitVectBitValue (domVect, i))
44 addSet (&domSet, ebbi->bbOrder[i]);
49 /*-----------------------------------------------------------------*/
50 /* addSuccessor - will add bb to succ also add it to the pred of */
52 /*-----------------------------------------------------------------*/
54 addSuccessor (eBBlock * thisBlock, eBBlock * succ)
56 /* check for boundary conditions */
57 if (!thisBlock || !succ)
60 /* add it to the succ of thisBlock */
61 addSetIfnotP (&thisBlock->succList, succ);
64 bitVectSetBit (thisBlock->succVect, succ->bbnum);
65 /* add this edge to the list of edges */
66 addSet (&graphEdges, newEdge (thisBlock, succ));
70 /*-----------------------------------------------------------------*/
71 /* eBBPredecessors - find the predecessors for each block */
72 /*-----------------------------------------------------------------*/
74 eBBPredecessors (ebbIndex * ebbi)
76 eBBlock ** ebbs = ebbi->bbOrder;
77 int count = ebbi->count;
80 /* for each block do */
81 for (i = 0; i < count; i++)
84 /* if there is no path to this then continue */
88 /* for each successor of this block if */
89 /* it has depth first number > this block */
90 /* then this block precedes the successor */
91 for (j = 0; j < ebbs[i]->succVect->size; j++)
93 if (bitVectBitValue (ebbs[i]->succVect, j) &&
94 ebbs[j]->dfnum > ebbs[i]->dfnum)
96 addSet (&ebbs[j]->predList, ebbs[i]);
100 /*-----------------------------------------------------------------*/
101 /* eBBSuccessors- find out the successors of all the nodes */
102 /*-----------------------------------------------------------------*/
104 eBBSuccessors (ebbIndex * ebbi)
106 eBBlock ** ebbs = ebbi->bbOrder;
107 int count = ebbi->count;
110 /* for all the blocks do */
111 for (; i < count; i++)
118 ebbs[i]->succVect = newBitVect (count);
120 /* if the next on exists & this one does not */
121 /* end in a GOTO or RETURN then the next is */
122 /* a natural successor of this. Note we have */
123 /* consider eBBlocks with no instructions */
129 if (ebbs[i]->ech->op != GOTO &&
130 ebbs[i]->ech->op != RETURN &&
131 ebbs[i]->ech->op != JUMPTABLE)
135 while (ebbs[j] && ebbs[j]->noPath)
138 addSuccessor (ebbs[i], ebbs[j]); /* add it */
142 if (i && ebbs[i-1]->ech && ebbs[i-1]->ech->op==IFX) {
143 ebbs[i]->isConditionalExitFrom=ebbs[i-1];
146 } /* no instructions in the block */
147 /* could happen for dummy blocks */
149 addSuccessor (ebbs[i], ebbs[i + 1]);
152 /* go thru all the instructions: if we find a */
153 /* goto or ifx or a return then we have a succ */
154 if ((ic = ebbs[i]->ech))
158 /* special case for jumptable */
159 if (ic->op == JUMPTABLE)
162 for (lbl = setFirstItem (IC_JTLABELS (ic)); lbl;
163 lbl = setNextItem (IC_JTLABELS (ic)))
164 addSuccessor (ebbs[i],
165 eBBWithEntryLabel (ebbi, lbl));
171 /* depending on the instruction operator */
174 case GOTO: /* goto has edge to label */
175 succ = eBBWithEntryLabel (ebbi, ic->label);
178 case IFX: /* conditional jump */
179 /* if true label is present */
181 succ = eBBWithEntryLabel (ebbi, IC_TRUE (ic));
183 succ = eBBWithEntryLabel (ebbi, IC_FALSE (ic));
186 case RETURN: /* block with return */
187 succ = eBBWithEntryLabel (ebbi, returnLabel);
191 /* if there is a successor add to the list */
192 /* if it is not already present in the list */
194 addSuccessor (ebbs[i], succ);
200 /*-----------------------------------------------------------------*/
201 /* computeDominance - computes the dominance graph */
202 /* for algorithm look at Dragon book section 10.10, algo 10.16 */
203 /*-----------------------------------------------------------------*/
205 computeDominance (ebbIndex * ebbi)
207 eBBlock ** ebbs = ebbi->bbOrder;
208 int count = ebbi->count;
211 /* now do the initialisation */
212 /* D(n0) := { n0 } */
214 bitVectSetBit (ebbs[0]->domVect = newBitVect (count), ebbs[0]->bbnum);
217 /* for n in N - { n0 } do D(n) = N */
218 for (i = 1; i < count; i++)
220 ebbs[i]->domVect = newBitVect (count);
221 for (j = 0; j < count; j++)
224 bitVectSetBit (ebbs[i]->domVect, ebbs[j]->bbnum);
228 /* end of initialisation */
230 /* while changes to any D(n) occur do */
231 /* for n in N - { n0 } do */
232 /* D(n) := { n } U (intersection of D( all predecessors of n)) */
238 for (i = 1; i < count; i++)
245 /* get the intersection of the dominance of all predecessors */
246 for (pred = setFirstItem (ebbs[i]->predList),
247 cDomVect = (pred ? bitVectCopy (pred->domVect) : NULL);
249 pred = setNextItem (ebbs[i]->predList))
251 cDomVect = bitVectIntersect (cDomVect, pred->domVect);
254 cDomVect = newBitVect (count);
255 /* this node to the list */
256 cDomVect = bitVectSetBit (cDomVect, ebbs[i]->bbnum);
259 if (!bitVectEqual (cDomVect, ebbs[i]->domVect))
261 ebbs[i]->domVect = cDomVect;
266 /* if no change then exit */
273 /*-----------------------------------------------------------------*/
274 /* immedDom - returns the immediate dominator of a block */
275 /*-----------------------------------------------------------------*/
277 immedDom (ebbIndex * ebbi, eBBlock * ebp)
279 /* first delete self from the list */
280 set *iset = domSetFromVect (ebbi, ebp->domVect);
282 eBBlock *idom = NULL;
284 deleteSetItem (&iset, ebp);
285 /* then just return the one with the greatest */
286 /* depthfirst number, this will be the immed dominator */
287 if ((loop = setFirstItem (iset)))
289 for (; loop; loop = setNextItem (iset))
290 if (loop->dfnum > idom->dfnum)
293 setToNull ((void *) &iset);
298 /*-----------------------------------------------------------------*/
299 /* DFOrdering - is visited then nothing else call DFOrdering this */
300 /*-----------------------------------------------------------------*/
301 DEFSETFUNC (DFOrdering)
303 eBBlock *ebbp = item;
304 V_ARG (int *, count);
309 computeDFOrdering (ebbp, count); /* depthfirst */
314 /*-----------------------------------------------------------------*/
315 /* computeDFOrdering - computes the depth first ordering of the */
317 /*-----------------------------------------------------------------*/
319 computeDFOrdering (eBBlock * ebbp, int *count)
323 /* for each successor that is not visited */
324 applyToSet (ebbp->succList, DFOrdering, count);
326 /* set the depth first number */
327 ebbp->dfnum = *count;
331 /*-----------------------------------------------------------------*/
332 /* disconBBlock - removes all control flow links for a block */
333 /*-----------------------------------------------------------------*/
335 disconBBlock (eBBlock * ebp, ebbIndex * ebbi)
337 /* mark this block as noPath & recompute control flow */
339 computeControlFlow (ebbi);
342 /*-----------------------------------------------------------------*/
343 /* markNoPath - marks those blocks which cannot be reached from top */
344 /*-----------------------------------------------------------------*/
346 markNoPath (ebbIndex * ebbi)
348 eBBlock ** ebbs = ebbi->bbOrder;
349 int count = ebbi->count;
352 /* for all blocks if the visited flag is not set : then there */
353 /* is no path from _entry to this block push them down in the */
354 /* depth first order */
355 for (i = 0; i < count; i++)
356 if (!ebbs[i]->visited)
360 /*-----------------------------------------------------------------*/
361 /* dfNumCompare - used by qsort to sort by dfNumber */
362 /*-----------------------------------------------------------------*/
364 dfNumCompare (const void *a, const void *b)
366 const eBBlock *const *i = a;
367 const eBBlock *const *j = b;
369 if ((*i)->dfnum > (*j)->dfnum)
372 if ((*i)->dfnum < (*j)->dfnum)
378 /*-----------------------------------------------------------------*/
379 /* computeControlFlow - does the control flow computation */
380 /*-----------------------------------------------------------------*/
382 computeControlFlow (ebbIndex * ebbi)
384 eBBlock ** ebbs = ebbi->bbOrder;
385 int dfCount = ebbi->count;
388 /* initialise some things */
390 for (i = 0; i < ebbi->count; i++)
392 setToNull ((void *) &ebbs[i]->predList);
393 setToNull ((void *) &ebbs[i]->domVect);
394 setToNull ((void *) &ebbs[i]->succList);
395 setToNull ((void *) &ebbs[i]->succVect);
396 ebbs[i]->visited = 0;
400 setToNull ((void *) &graphEdges);
401 /* this will put in the */
402 /* successor information for each blk */
403 eBBSuccessors (ebbi);
405 /* compute the depth first ordering */
406 computeDFOrdering (ebbi->bbOrder[0], &dfCount);
408 /* mark blocks with no paths to them */
411 /* with the depth first info in place */
412 /* add the predecessors for the blocks */
413 eBBPredecessors (ebbi);
415 /* compute the dominance graph */
416 computeDominance (ebbi);
418 /* sort it by dfnumber */
420 ebbi->dfOrder = Safe_alloc ((ebbi->count+1) * sizeof (eBBlock *));
421 for (i = 0; i < (ebbi->count+1); i++)
423 ebbi->dfOrder[i] = ebbi->bbOrder[i];
426 qsort (ebbi->dfOrder, ebbi->count, 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;