1 //#define LIVERANGEHUNT
7 /*-------------------------------------------------------------------------
9 SDCCcflow.c - source file for control flow analysis
11 Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
13 This program is free software; you can redistribute it and/or modify it
14 under the terms of the GNU General Public License as published by the
15 Free Software Foundation; either version 2, or (at your option) any
18 This program is distributed in the hope that it will be useful,
19 but WITHOUT ANY WARRANTY; without even the implied warranty of
20 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 GNU General Public License for more details.
23 You should have received a copy of the GNU General Public License
24 along with this program; if not, write to the Free Software
25 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
27 In other words, you are welcome to use, share and improve this program.
28 You are forbidden to forbid anyone else to use, share and improve
29 what you give them. Help stamp out software-hoarding!
30 -------------------------------------------------------------------------*/
34 /*-----------------------------------------------------------------*/
35 /* domSetFromVect - creates a domset from the vector */
36 /*-----------------------------------------------------------------*/
38 domSetFromVect (eBBlock ** ebbs, bitVect * domVect)
46 for (i = 0; i < domVect->size; i++)
47 if (bitVectBitValue (domVect, i))
48 addSet (&domSet, ebbs[i]);
53 /*-----------------------------------------------------------------*/
54 /* addSuccessor - will add bb to succ also add it to the pred of */
56 /*-----------------------------------------------------------------*/
58 addSuccessor (eBBlock * thisBlock, eBBlock * succ)
60 /* check for boundary conditions */
61 if (!thisBlock || !succ)
64 /* add it to the succ of thisBlock */
65 addSetIfnotP (&thisBlock->succList, succ);
68 bitVectSetBit (thisBlock->succVect, succ->bbnum);
69 /* add this edge to the list of edges */
70 addSet (&graphEdges, newEdge (thisBlock, succ));
74 /*-----------------------------------------------------------------*/
75 /* eBBPredecessors - find the predecessors for each block */
76 /*-----------------------------------------------------------------*/
78 eBBPredecessors (eBBlock ** ebbs, int count)
82 /* for each block do */
83 for (i = 0; i < count; i++)
86 /* if there is no path to this then continue */
90 /* for each successor of this block if */
91 /* it has depth first number > this block */
92 /* then this block precedes the successor */
93 for (j = 0; j < ebbs[i]->succVect->size; j++)
95 if (bitVectBitValue (ebbs[i]->succVect, j) &&
96 ebbs[j]->dfnum > ebbs[i]->dfnum)
98 addSet (&ebbs[j]->predList, ebbs[i]);
102 /*-----------------------------------------------------------------*/
103 /* eBBSuccessors- find out the successors of all the nodes */
104 /*-----------------------------------------------------------------*/
106 eBBSuccessors (eBBlock ** ebbs, int 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 */
144 if (ebbs[j]->ech && ebbs[j]->ech->op==IFX &&
145 (isSymbolEqual(IC_TRUE(ebbs[j]->ech), ebbs[i]->entryLabel) ||
146 isSymbolEqual(IC_FALSE(ebbs[j]->ech), ebbs[i]->entryLabel))) {
147 LRH(printf ("%s has a conditional exit from %s\n", ebbs[i]->entryLabel->name, ebbs[j]->entryLabel->name));
148 ebbs[i]->hasConditionalExit=1;
152 } /* no instructions in the block */
153 /* could happen for dummy blocks */
155 addSuccessor (ebbs[i], ebbs[i + 1]);
158 /* go thru all the instructions: if we find a */
159 /* goto or ifx or a return then we have a succ */
160 if ((ic = ebbs[i]->ech))
164 /* special case for jumptable */
165 if (ic->op == JUMPTABLE)
168 for (lbl = setFirstItem (IC_JTLABELS (ic)); lbl;
169 lbl = setNextItem (IC_JTLABELS (ic)))
170 addSuccessor (ebbs[i],
171 eBBWithEntryLabel (ebbs, lbl, count));
177 /* depending on the instruction operator */
180 case GOTO: /* goto has edge to label */
181 succ = eBBWithEntryLabel (ebbs, ic->label, count);
184 case IFX: /* conditional jump */
185 /* if true label is present */
187 succ = eBBWithEntryLabel (ebbs, IC_TRUE (ic), count);
189 succ = eBBWithEntryLabel (ebbs, IC_FALSE (ic), count);
192 case RETURN: /* block with return */
193 succ = eBBWithEntryLabel (ebbs, returnLabel, count);
197 /* if there is a successor add to the list */
198 /* if it is not already present in the list */
200 addSuccessor (ebbs[i], succ);
206 /*-----------------------------------------------------------------*/
207 /* computeDominance - computes the dominance graph */
208 /* for algorithm look at Dragon book section 10.10, algo 10.16 */
209 /*-----------------------------------------------------------------*/
211 computeDominance (eBBlock ** ebbs, int count)
215 /* now do the initialisation */
216 /* D(n0) := { n0 } */
218 bitVectSetBit (ebbs[0]->domVect = newBitVect (count), ebbs[0]->bbnum);
221 /* for n in N - { n0 } do D(n) = N */
222 for (i = 1; i < count; i++)
224 ebbs[i]->domVect = newBitVect (count);
225 for (j = 0; j < count; j++)
228 bitVectSetBit (ebbs[i]->domVect, ebbs[j]->bbnum);
232 /* end of initialisation */
234 /* while changes to any D(n) occur do */
235 /* for n in N - { n0 } do */
236 /* D(n) := { n } U (intersection of D( all predecessors of n)) */
242 for (i = 1; i < count; i++)
249 /* get the intersection of the dominance of all predecessors */
250 for (pred = setFirstItem (ebbs[i]->predList),
251 cDomVect = (pred ? bitVectCopy (pred->domVect) : NULL);
253 pred = setNextItem (ebbs[i]->predList))
255 cDomVect = bitVectIntersect (cDomVect, pred->domVect);
258 cDomVect = newBitVect (count);
259 /* this node to the list */
260 cDomVect = bitVectSetBit (cDomVect, ebbs[i]->bbnum);
263 if (!bitVectEqual (cDomVect, ebbs[i]->domVect))
265 ebbs[i]->domVect = cDomVect;
270 /* if no change then exit */
276 /*-----------------------------------------------------------------*/
277 /* immedDom - returns the immediate dominator of a block */
278 /*-----------------------------------------------------------------*/
280 immedDom (eBBlock ** ebbs, eBBlock * ebp)
282 /* first delete self from the list */
283 set *iset = domSetFromVect (ebbs, ebp->domVect);
285 eBBlock *idom = NULL;
287 deleteSetItem (&iset, ebp);
288 /* then just return the one with the greatest */
289 /* depthfirst number, this will be the immed dominator */
290 if ((loop = setFirstItem (iset)))
292 for (; loop; loop = setNextItem (iset))
293 if (loop->dfnum > idom->dfnum)
296 setToNull ((void **) &iset);
301 /*-----------------------------------------------------------------*/
302 /* DFOrdering - is visited then nothing else call DFOrdering this */
303 /*-----------------------------------------------------------------*/
304 DEFSETFUNC (DFOrdering)
306 eBBlock *ebbp = item;
307 V_ARG (int *, count);
312 computeDFOrdering (ebbp, count); /* depthfirst */
317 /*-----------------------------------------------------------------*/
318 /* computeDFOrdering - computes the depth first ordering of the */
320 /*-----------------------------------------------------------------*/
322 computeDFOrdering (eBBlock * ebbp, int *count)
326 /* for each successor that is not visited */
327 applyToSet (ebbp->succList, DFOrdering, count);
329 /* set the depth first number */
330 ebbp->dfnum = *count;
334 /*-----------------------------------------------------------------*/
335 /* disconBBlock - removes all control flow links for a block */
336 /*-----------------------------------------------------------------*/
338 disconBBlock (eBBlock * ebp, eBBlock ** ebbs, int count)
340 /* mark this block as noPath & recompute control flow */
342 computeControlFlow (ebbs, count, TRUE);
345 /*-----------------------------------------------------------------*/
346 /* markNoPath - marks those blocks which cannot be reached from top */
347 /*-----------------------------------------------------------------*/
349 markNoPath (eBBlock ** ebbs, int count)
354 /* for all blocks if the visited flag is not set : then there */
355 /* is no path from _entry to this block push them down in the */
356 /* depth first order */
357 for (i = 0; i < count; i++)
358 if (!ebbs[i]->visited)
361 /*-----------------------------------------------------------------*/
362 /* dfNumCompare - used by qsort to sort by dfNumber */
363 /*-----------------------------------------------------------------*/
365 dfNumCompare (const void *a, const void *b)
367 const eBBlock *const *i = a;
368 const eBBlock *const *j = b;
370 if ((*i)->dfnum > (*j)->dfnum)
373 if ((*i)->dfnum < (*j)->dfnum)
379 /*-----------------------------------------------------------------*/
380 /* bbNumCompare - used by qsort to sort by bbNumber */
381 /*-----------------------------------------------------------------*/
383 bbNumCompare (const void *a, const void *b)
385 const eBBlock *const *i = a;
386 const eBBlock *const *j = b;
388 if ((*i)->bbnum > (*j)->bbnum)
391 if ((*i)->bbnum < (*j)->bbnum)
398 /*-----------------------------------------------------------------*/
399 /* computeControlFlow - does the control flow computation */
400 /*-----------------------------------------------------------------*/
402 computeControlFlow (eBBlock ** ebbs, int count, int reSort)
404 int saveCount = count;
407 /* initialise some things */
409 for (i = 0; i < count; i++)
411 setToNull ((void **) &ebbs[i]->predList);
412 setToNull ((void **) &ebbs[i]->domVect);
413 setToNull ((void **) &ebbs[i]->succList);
414 setToNull ((void **) &ebbs[i]->succVect);
415 ebbs[i]->visited = 0;
420 /* sort it back by block number */
421 qsort (ebbs, saveCount, sizeof (eBBlock *), bbNumCompare);
423 setToNull ((void **) &graphEdges);
424 /* this will put in the */
425 /* successor information for each blk */
426 eBBSuccessors (ebbs, count);
428 /* compute the depth first ordering */
429 computeDFOrdering (ebbs[0], &count);
431 /* mark blocks with no paths to them */
432 markNoPath (ebbs, saveCount);
434 /* with the depth first info in place */
435 /* add the predecessors for the blocks */
436 eBBPredecessors (ebbs, saveCount);
438 /* compute the dominance graph */
439 computeDominance (ebbs, saveCount);
441 /* sort it by dfnumber */
442 qsort (ebbs, saveCount, sizeof (eBBlock *), dfNumCompare);
446 /*-----------------------------------------------------------------*/
447 /* returnAtEnd - returns 1 if Basic Block has a return at the end */
449 /*-----------------------------------------------------------------*/
450 int returnAtEnd (eBBlock *ebp)
453 This basic block ends in a return statment
455 if (ebp->ech && ebp->ech->op == RETURN) return 1;
458 This basic block has only one successor and that
459 successor has only one return statement
461 if (elementsInSet(ebp->succList) == 1) {
462 eBBlock *succ = setFirstItem(ebp->succList);
463 /* could happen for dummy blocks */
464 if (!succ->sch || !succ->ech) return 0;
466 /* first iCode is a return */
467 if (succ->sch->op == RETURN) return 2;
469 /* or first iCode is a label & the next &
470 last icode is a return */
471 if (succ->sch->op == LABEL && succ->sch->next == succ->ech &&
472 succ->ech->op == RETURN ) return 2;