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 /*-----------------------------------------------------------------*/
31 set *domSetFromVect (eBBlock **ebbs, bitVect *domVect)
39 for (i = 0 ; i < domVect->size ;i++ )
40 if (bitVectBitValue(domVect,i))
41 addSet(&domSet,ebbs[i]);
46 /*-----------------------------------------------------------------*/
47 /* addSuccessor - will add bb to succ also add it to the pred of */
49 /*-----------------------------------------------------------------*/
50 void addSuccessor (eBBlock *thisBlock, eBBlock *succ )
52 /* check for boundary conditions */
53 if ( ! thisBlock || ! succ )
56 /* add it to the succ of thisBlock */
57 addSetIfnotP (&thisBlock->succList,succ);
60 bitVectSetBit(thisBlock->succVect,succ->bbnum);
61 /* add this edge to the list of edges */
62 addSet(&graphEdges,newEdge(thisBlock,succ));
66 /*-----------------------------------------------------------------*/
67 /* eBBPredecessors - find the predecessors for each block */
68 /*-----------------------------------------------------------------*/
69 void eBBPredecessors ( eBBlock **ebbs, int count)
73 /* for each block do */
74 for ( i = 0 ; i < count ; i++ ) {
76 /* if there is no path to this then continue */
80 /* for each successor of this block if */
81 /* it has depth first number > this block */
82 /* then this block precedes the successor */
83 for (j = 0; j < ebbs[i]->succVect->size ; j++)
85 if ( bitVectBitValue(ebbs[i]->succVect,j) &&
86 ebbs[j]->dfnum > ebbs[i]->dfnum )
88 addSet(&ebbs[j]->predList,ebbs[i]);
92 /*-----------------------------------------------------------------*/
93 /* eBBSuccessors- find out the successors of all the nodes */
94 /*-----------------------------------------------------------------*/
95 void eBBSuccessors ( eBBlock **ebbs , int count )
99 /* for all the blocks do */
100 for (; i < count; i++ ) {
106 ebbs[i]->succVect = newBitVect(count);
108 /* if the next on exists & this one does not */
109 /* end in a GOTO or RETURN then the next is */
110 /* a natural successor of this. Note we have */
111 /* consider eBBlocks with no instructions */
116 if (ebbs[i]->ech->op != GOTO &&
117 ebbs[i]->ech->op != RETURN &&
118 ebbs[i]->ech->op != JUMPTABLE) {
121 while (ebbs[j] && ebbs[j]->noPath) j++;
123 addSuccessor (ebbs[i],ebbs[j]); /* add it */
125 } /* no instructions in the block */
126 /* could happen for dummy blocks*/
128 addSuccessor (ebbs[i],ebbs[i+1]);
131 /* go thru all the instructions: if we find a */
132 /* goto or ifx or a return then we have a succ*/
133 if ((ic = ebbs[i]->ech)) {
136 /* special case for jumptable */
137 if (ic->op == JUMPTABLE ) {
139 for (lbl = setFirstItem(IC_JTLABELS(ic)); lbl;
140 lbl = setNextItem(IC_JTLABELS(ic)))
141 addSuccessor(ebbs[i],
142 eBBWithEntryLabel(ebbs,lbl,count));
146 /* depending on the instruction operator */
148 case GOTO : /* goto has edge to label */
149 succ = eBBWithEntryLabel (ebbs,ic->argLabel.label,count);
152 case IFX : /* conditional jump */
153 /* if true label is present */
155 succ = eBBWithEntryLabel (ebbs,IC_TRUE(ic),count);
157 succ = eBBWithEntryLabel (ebbs,IC_FALSE(ic),count);
160 case RETURN : /* block with return */
161 succ = eBBWithEntryLabel (ebbs,returnLabel,count);
165 /* if there is a successor add to the list */
166 /* if it is not already present in the list*/
168 addSuccessor(ebbs[i],succ);
174 /*-----------------------------------------------------------------*/
175 /* computeDominance - computes the dominance graph */
176 /* for algorithm look at Dragon book section 10.10, algo 10.16 */
177 /*-----------------------------------------------------------------*/
178 void computeDominance ( eBBlock **ebbs, int count )
182 /* now do the initialisation */
183 /* D(n0) := { n0 } */
185 bitVectSetBit(ebbs[0]->domVect = newBitVect(count),ebbs[0]->bbnum);
188 /* for n in N - { n0 } do D(n) = N */
189 for (i = 1 ; i < count ; i++ ) {
190 ebbs[i]->domVect = newBitVect(count);
191 for (j = 0 ; j < count ; j++ ) {
193 bitVectSetBit(ebbs[i]->domVect,ebbs[j]->bbnum);
197 /* end of initialisation */
199 /* while changes to any D(n) occur do */
200 /* for n in N - { n0 } do */
201 /* D(n) := { n } U (intersection of D( all predecessors of n)) */
206 for ( i = 1 ; i < count ; i++ ) {
212 /* get the intersection of the dominance of all predecessors */
213 for (pred = setFirstItem(ebbs[i]->predList) ,
214 cDomVect = (pred ? bitVectCopy(pred->domVect) : NULL) ;
216 pred = setNextItem(ebbs[i]->predList)) {
217 cDomVect = bitVectIntersect(cDomVect,pred->domVect);
220 cDomVect = newBitVect(count);
221 /* this node to the list */
222 cDomVect = bitVectSetBit(cDomVect,ebbs[i]->bbnum);
225 if (!bitVectEqual(cDomVect,ebbs[i]->domVect)) {
226 ebbs[i]->domVect = cDomVect;
231 /* if no change then exit */
237 /*-----------------------------------------------------------------*/
238 /* immedDom - returns the immediate dominator of a block */
239 /*-----------------------------------------------------------------*/
240 eBBlock *immedDom (eBBlock **ebbs,eBBlock *ebp)
242 /* first delete self from the list */
243 set *iset = domSetFromVect(ebbs,ebp->domVect);
245 eBBlock *idom = NULL;
247 deleteSetItem(&iset,ebp);
248 /* then just return the one with the greatest */
249 /* depthfirst number, this will be the immed dominator */
250 if ((loop = setFirstItem(iset)))
252 for (; loop; loop = setNextItem(iset))
253 if (loop->dfnum > idom->dfnum)
256 setToNull ((void **)&iset);
261 /*-----------------------------------------------------------------*/
262 /* DFOrdering - is visited then nothing else call DFOrdering this */
263 /*-----------------------------------------------------------------*/
264 DEFSETFUNC(DFOrdering)
266 eBBlock *ebbp = item ;
272 computeDFOrdering (ebbp,count); /* depthfirst */
277 /*-----------------------------------------------------------------*/
278 /* computeDFOrdering - computes the depth first ordering of the */
280 /*-----------------------------------------------------------------*/
281 void computeDFOrdering ( eBBlock *ebbp , int *count)
285 /* for each successor that is not visited */
286 applyToSet(ebbp->succList,DFOrdering,count);
288 /* set the depth first number */
289 ebbp->dfnum = *count ;
293 /*-----------------------------------------------------------------*/
294 /* disconBBlock - removes all control flow links for a block */
295 /*-----------------------------------------------------------------*/
296 void disconBBlock (eBBlock *ebp, eBBlock **ebbs, int count)
298 /* mark this block as noPath & recompute control flow */
300 computeControlFlow (ebbs,count,TRUE);
303 /*-----------------------------------------------------------------*/
304 /* markNoPath - marks those blocks which cannot be reached from top*/
305 /*-----------------------------------------------------------------*/
306 void markNoPath ( eBBlock **ebbs, int count )
311 /* for all blocks if the visited flag is not set : then there */
312 /* is no path from _entry to this block push them down in the */
313 /* depth first order */
314 for ( i = 0 ; i < count ; i++ )
315 if (!ebbs[i]->visited)
318 /*-----------------------------------------------------------------*/
319 /* dfNumCompare - used by qsort to sort by dfNumber */
320 /*-----------------------------------------------------------------*/
321 int dfNumCompare (const void *a, const void *b)
323 const eBBlock * const *i = a;
324 const eBBlock * const *j = b;
326 if ( (*i)->dfnum > (*j)->dfnum )
329 if ( (*i)->dfnum < (*j)->dfnum )
335 /*-----------------------------------------------------------------*/
336 /* bbNumCompare - used by qsort to sort by bbNumber */
337 /*-----------------------------------------------------------------*/
338 int bbNumCompare (const void *a, const void *b)
340 const eBBlock * const *i = a;
341 const eBBlock * const *j = b;
343 if ( (*i)->bbnum > (*j)->bbnum )
346 if ( (*i)->bbnum < (*j)->bbnum )
353 /*-----------------------------------------------------------------*/
354 /* computeControlFlow - does the control flow computation */
355 /*-----------------------------------------------------------------*/
356 void computeControlFlow (eBBlock **ebbs,int count, int reSort)
358 int saveCount = count;
361 /* initialise some things */
363 for ( i = 0 ; i < count ; i++ ) {
364 setToNull((void **)&ebbs[i]->predList);
365 setToNull((void **)&ebbs[i]->domVect);
366 setToNull((void **)&ebbs[i]->succList);
367 setToNull((void **)&ebbs[i]->succVect);
368 ebbs[i]->visited = 0;
373 /* sort it back by block number */
374 qsort (ebbs,saveCount,sizeof(eBBlock *),bbNumCompare);
376 setToNull ((void **)&graphEdges);
377 /* this will put in the */
378 /* successor information for each blk */
379 eBBSuccessors (ebbs,count);
381 /* compute the depth first ordering */
382 computeDFOrdering (ebbs[0],&count);
384 /* mark blocks with no paths to them */
385 markNoPath (ebbs,saveCount);
387 /* with the depth first info in place */
388 /* add the predecessors for the blocks*/
389 eBBPredecessors (ebbs,saveCount);
391 /* compute the dominance graph */
392 computeDominance (ebbs,saveCount);
394 /* sort it by dfnumber */
395 qsort (ebbs,saveCount,sizeof(eBBlock *),dfNumCompare);