1 /*-------------------------------------------------------------------------
2
3 SDCCcflow.c - source file for control flow analysis
4
5 Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
6
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
10 later version.
11
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.
16
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.
20
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 -------------------------------------------------------------------------*/
25
26 #include "common.h"
27
28 static void computeDFOrdering (eBBlock *, int *);
29
30 /*-----------------------------------------------------------------*/
31 /* domSetFromVect - creates a domset from the vector */
32 /*-----------------------------------------------------------------*/
33 static set *
domSetFromVect(ebbIndex * ebbi,bitVect * domVect)34 domSetFromVect (ebbIndex *ebbi, bitVect * domVect)
35 {
36 int i = 0;
37 set *domSet = NULL;
38
39 if (!domVect)
40 return NULL;
41
42 for (i = 0; i < domVect->size; i++)
43 if (bitVectBitValue (domVect, i))
44 addSet (&domSet, ebbi->bbOrder[i]);
45 return domSet;
46 }
47
48
49 /*-----------------------------------------------------------------*/
50 /* addSuccessor - will add bb to succ also add it to the pred of */
51 /* the next one : */
52 /*-----------------------------------------------------------------*/
53 static void
addSuccessor(eBBlock * thisBlock,eBBlock * succ)54 addSuccessor (eBBlock * thisBlock, eBBlock * succ)
55 {
56 /* check for boundary conditions */
57 if (!thisBlock || !succ)
58 return;
59
60 /* add it to the succ of thisBlock */
61 addSetIfnotP (&thisBlock->succList, succ);
62
63 thisBlock->succVect =
64 bitVectSetBit (thisBlock->succVect, succ->bbnum);
65 /* add this edge to the list of edges */
66 addSet (&graphEdges, newEdge (thisBlock, succ));
67
68 }
69
70 /*-----------------------------------------------------------------*/
71 /* eBBPredecessors - find the predecessors for each block */
72 /*-----------------------------------------------------------------*/
73 static void
eBBPredecessors(ebbIndex * ebbi)74 eBBPredecessors (ebbIndex * ebbi)
75 {
76 eBBlock ** ebbs = ebbi->bbOrder;
77 int count = ebbi->count;
78 int i = 0, j;
79
80 /* for each block do */
81 for (i = 0; i < count; i++)
82 {
83
84 /* if there is no path to this then continue */
85 if (ebbs[i]->noPath)
86 continue;
87
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++)
92
93 if (bitVectBitValue (ebbs[i]->succVect, j) &&
94 ebbs[j]->dfnum > ebbs[i]->dfnum)
95
96 addSet (&ebbs[j]->predList, ebbs[i]);
97 }
98 }
99
100 /*-----------------------------------------------------------------*/
101 /* eBBSuccessors- find out the successors of all the nodes */
102 /*-----------------------------------------------------------------*/
103 static void
eBBSuccessors(ebbIndex * ebbi)104 eBBSuccessors (ebbIndex * ebbi)
105 {
106 eBBlock ** ebbs = ebbi->bbOrder;
107 int count = ebbi->count;
108 int i = 0;
109
110 /* for all the blocks do */
111 for (; i < count; i++)
112 {
113 iCode *ic;
114
115 if (ebbs[i]->noPath)
116 continue;
117
118 ebbs[i]->succVect = newBitVect (count);
119
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 */
124 if (ebbs[i + 1])
125 {
126
127 if (ebbs[i]->ech)
128 {
129 bool foundNoReturn = FALSE;
130 if (ebbs[i]->ech->op == CALL || ebbs[i]->ech->op == PCALL)
131 {
132 sym_link *type = operandType (IC_LEFT (ebbs[i]->ech));
133 if (IS_FUNCPTR (type))
134 type = type->next;
135 if (type && FUNC_ISNORETURN (type))
136 foundNoReturn = TRUE;
137 }
138 if (!foundNoReturn &&
139 ebbs[i]->ech->op != GOTO &&
140 ebbs[i]->ech->op != RETURN &&
141 ebbs[i]->ech->op != JUMPTABLE)
142 {
143 int j = i + 1;
144
145 while (ebbs[j] && ebbs[j]->noPath)
146 j++;
147
148 addSuccessor (ebbs[i], ebbs[j]); /* add it */
149 }
150 else
151 {
152 if (i && ebbs[i-1]->ech && ebbs[i-1]->ech->op==IFX) {
153 ebbs[i]->isConditionalExitFrom=ebbs[i-1];
154 }
155 }
156 } /* no instructions in the block */
157 /* could happen for dummy blocks */
158 else
159 addSuccessor (ebbs[i], ebbs[i + 1]);
160 }
161
162 /* go thru all the instructions: if we find a */
163 /* goto or ifx or a return then we have a succ */
164 if ((ic = ebbs[i]->ech))
165 {
166 eBBlock *succ;
167
168 /* special case for jumptable */
169 if (ic->op == JUMPTABLE)
170 {
171 symbol *lbl;
172 for (lbl = setFirstItem (IC_JTLABELS (ic)); lbl;
173 lbl = setNextItem (IC_JTLABELS (ic)))
174 addSuccessor (ebbs[i],
175 eBBWithEntryLabel (ebbi, lbl));
176 }
177 else
178 {
179
180 succ = NULL;
181 /* depending on the instruction operator */
182 switch (ic->op)
183 {
184 case GOTO: /* goto has edge to label */
185 succ = eBBWithEntryLabel (ebbi, ic->label);
186
187 /* Sometimes a block has a GOTO added after the original */
188 /* final IFX (due to loop optimizations). If IFX found, */
189 /* fall through to handle the IFX too. */
190 if (ic->prev && ic->prev->op == IFX)
191 {
192 if (succ)
193 addSuccessor (ebbs[i], succ); /* add the GOTO target */
194 ic = ic->prev; /* get ready to handle IFX too. */
195 }
196 else
197 break;
198
199 case IFX: /* conditional jump */
200 /* if true label is present */
201 if (IC_TRUE (ic))
202 succ = eBBWithEntryLabel (ebbi, IC_TRUE (ic));
203 else
204 succ = eBBWithEntryLabel (ebbi, IC_FALSE (ic));
205 break;
206
207 case RETURN: /* block with return */
208 succ = eBBWithEntryLabel (ebbi, returnLabel);
209 break;
210 }
211
212 /* if there is a successor add to the list */
213 /* if it is not already present in the list */
214 if (succ)
215 addSuccessor (ebbs[i], succ);
216 }
217 }
218 }
219 }
220
221 /*-----------------------------------------------------------------*/
222 /* computeDominance - computes the dominance graph */
223 /* for algorithm look at Dragon book section 10.10, algo 10.16 */
224 /*-----------------------------------------------------------------*/
225 static void
computeDominance(ebbIndex * ebbi)226 computeDominance (ebbIndex * ebbi)
227 {
228 eBBlock ** ebbs = ebbi->bbOrder;
229 int count = ebbi->count;
230 int i, j;
231
232 /* now do the initialisation */
233 /* D(n0) := { n0 } */
234 ebbs[0]->domVect =
235 bitVectSetBit (ebbs[0]->domVect = newBitVect (count), ebbs[0]->bbnum);
236
237
238 /* for n in N - { n0 } do D(n) = N */
239 for (i = 1; i < count; i++)
240 {
241 ebbs[i]->domVect = newBitVect (count);
242 for (j = 0; j < count; j++)
243 {
244 ebbs[i]->domVect =
245 bitVectSetBit (ebbs[i]->domVect, ebbs[j]->bbnum);
246 }
247 }
248
249 /* end of initialisation */
250
251 /* while changes to any D(n) occur do */
252 /* for n in N - { n0 } do */
253 /* D(n) := { n } U (intersection of D( all predecessors of n)) */
254 while (1)
255 {
256 int change;
257
258 change = 0;
259 for (i = 1; i < count; i++)
260 {
261 bitVect *cDomVect;
262 eBBlock *pred;
263
264 cDomVect = NULL;
265
266 /* get the intersection of the dominance of all predecessors */
267 for (pred = setFirstItem (ebbs[i]->predList),
268 cDomVect = (pred ? bitVectCopy (pred->domVect) : NULL);
269 pred;
270 pred = setNextItem (ebbs[i]->predList))
271 {
272 cDomVect = bitVectInplaceIntersect (cDomVect, pred->domVect);
273 }
274 if (!cDomVect)
275 cDomVect = newBitVect (count);
276 /* this node to the list */
277 cDomVect = bitVectSetBit (cDomVect, ebbs[i]->bbnum);
278
279
280 if (!bitVectEqual (cDomVect, ebbs[i]->domVect))
281 {
282 freeBitVect (ebbs[i]->domVect);
283 ebbs[i]->domVect = cDomVect;
284 change = 1;
285 }
286 }
287
288 /* if no change then exit */
289 if (!change)
290 break;
291 }
292
293 }
294
295 /*-----------------------------------------------------------------*/
296 /* immedDom - returns the immediate dominator of a block */
297 /*-----------------------------------------------------------------*/
298 eBBlock *
immedDom(ebbIndex * ebbi,eBBlock * ebp)299 immedDom (ebbIndex * ebbi, eBBlock * ebp)
300 {
301 /* first delete self from the list */
302 set *iset = domSetFromVect (ebbi, ebp->domVect);
303 eBBlock *loop;
304 eBBlock *idom = NULL;
305
306 deleteSetItem (&iset, ebp);
307 /* then just return the one with the greatest */
308 /* depthfirst number, this will be the immed dominator */
309 if ((loop = setFirstItem (iset)))
310 idom = loop;
311 for (; loop; loop = setNextItem (iset))
312 if (loop->dfnum > idom->dfnum)
313 idom = loop;
314
315 setToNull ((void *) &iset);
316 return idom;
317
318 }
319
320 /*-----------------------------------------------------------------*/
321 /* DFOrdering - is visited then nothing else call DFOrdering this */
322 /*-----------------------------------------------------------------*/
DEFSETFUNC(DFOrdering)323 DEFSETFUNC (DFOrdering)
324 {
325 eBBlock *ebbp = item;
326 V_ARG (int *, count);
327
328 if (ebbp->visited)
329 return 0;
330
331 computeDFOrdering (ebbp, count); /* depthfirst */
332
333 return 0;
334 }
335
336 /*-----------------------------------------------------------------*/
337 /* computeDFOrdering - computes the depth first ordering of the */
338 /* flowgraph */
339 /*-----------------------------------------------------------------*/
340 static void
computeDFOrdering(eBBlock * ebbp,int * count)341 computeDFOrdering (eBBlock * ebbp, int *count)
342 {
343
344 ebbp->visited = 1;
345 /* for each successor that is not visited */
346 applyToSet (ebbp->succList, DFOrdering, count);
347
348 /* set the depth first number */
349 ebbp->dfnum = *count;
350 *count -= 1;
351 }
352
353 /*-----------------------------------------------------------------*/
354 /* disconBBlock - removes all control flow links for a block */
355 /*-----------------------------------------------------------------*/
356 void
disconBBlock(eBBlock * ebp,ebbIndex * ebbi)357 disconBBlock (eBBlock * ebp, ebbIndex * ebbi)
358 {
359 /* mark this block as noPath & recompute control flow */
360 ebp->noPath = 1;
361 computeControlFlow (ebbi);
362 }
363
364 /*-----------------------------------------------------------------*/
365 /* markNoPath - marks those blocks which cannot be reached from top */
366 /*-----------------------------------------------------------------*/
367 static void
markNoPath(ebbIndex * ebbi)368 markNoPath (ebbIndex * ebbi)
369 {
370 eBBlock ** ebbs = ebbi->bbOrder;
371 int count = ebbi->count;
372 int i;
373
374 /* for all blocks if the visited flag is not set : then there */
375 /* is no path from _entry to this block push them down in the */
376 /* depth first order */
377 for (i = 0; i < count; i++)
378 if (!ebbs[i]->visited)
379 ebbs[i]->noPath = 1;
380 }
381
382 /*-----------------------------------------------------------------*/
383 /* dfNumCompare - used by qsort to sort by dfNumber */
384 /*-----------------------------------------------------------------*/
385 int
dfNumCompare(const void * a,const void * b)386 dfNumCompare (const void *a, const void *b)
387 {
388 const eBBlock *const *i = a;
389 const eBBlock *const *j = b;
390
391 if ((*i)->dfnum > (*j)->dfnum)
392 return 1;
393
394 if ((*i)->dfnum < (*j)->dfnum)
395 return -1;
396
397 return 0;
398 }
399
400 /*-----------------------------------------------------------------*/
401 /* computeControlFlow - does the control flow computation */
402 /*-----------------------------------------------------------------*/
403 void
computeControlFlow(ebbIndex * ebbi)404 computeControlFlow (ebbIndex * ebbi)
405 {
406 eBBlock ** ebbs = ebbi->bbOrder;
407 int dfCount = ebbi->count;
408 int i;
409
410 /* initialise some things */
411
412 for (i = 0; i < ebbi->count; i++)
413 {
414 deleteSet (&ebbs[i]->predList);
415 freeBitVect (ebbs[i]->domVect); ebbs[i]->domVect = NULL;
416 deleteSet (&ebbs[i]->succList);
417 freeBitVect (ebbs[i]->succVect); ebbs[i]->succVect = NULL;
418 ebbs[i]->visited = 0;
419 ebbs[i]->dfnum = 0;
420 }
421
422 setToNull ((void *) &graphEdges);
423 /* this will put in the */
424 /* successor information for each blk */
425 eBBSuccessors (ebbi);
426
427 /* compute the depth first ordering */
428 computeDFOrdering (ebbi->bbOrder[0], &dfCount);
429
430 /* mark blocks with no paths to them */
431 markNoPath (ebbi);
432
433 /* with the depth first info in place */
434 /* add the predecessors for the blocks */
435 eBBPredecessors (ebbi);
436
437 /* compute the dominance graph */
438 computeDominance (ebbi);
439
440 /* sort it by dfnumber */
441 if (!ebbi->dfOrder)
442 ebbi->dfOrder = Safe_alloc ((ebbi->count+1) * sizeof (eBBlock *));
443 for (i = 0; i < (ebbi->count+1); i++)
444 {
445 ebbi->dfOrder[i] = ebbi->bbOrder[i];
446 }
447
448 qsort (ebbi->dfOrder, ebbi->count, sizeof (eBBlock *), dfNumCompare);
449
450 }
451
452 /*-----------------------------------------------------------------*/
453 /* returnAtEnd - returns 1 if Basic Block has a return at the end */
454 /* of it */
455 /*-----------------------------------------------------------------*/
returnAtEnd(eBBlock * ebp)456 int returnAtEnd (eBBlock *ebp)
457 {
458 /* case 1.
459 This basic block ends in a return statment
460 */
461 if (ebp->ech && ebp->ech->op == RETURN) return 1;
462
463 /* case 2.
464 This basic block has only one successor and that
465 successor has only one return statement
466 */
467 if (elementsInSet(ebp->succList) == 1) {
468 eBBlock *succ = setFirstItem(ebp->succList);
469 /* could happen for dummy blocks */
470 if (!succ->sch || !succ->ech) return 0;
471
472 /* first iCode is a return */
473 if (succ->sch->op == RETURN) return 2;
474
475 /* or first iCode is a label & the next &
476 last icode is a return */
477 if (succ->sch->op == LABEL && succ->sch->next == succ->ech &&
478 succ->ech->op == RETURN ) return 2;
479 }
480
481 return 0;
482 }
483
484