Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20090606191955

Diff

Diff from 1.67 to:

Annotations

Annotate by Age | Author | Mixed | None
/fisheye/browse/pcc/pcc/mip/optim2.c

Annotated File View

ragge
1.67
1 /*      $Id: optim2.c,v 1.67 2009/06/06 19:19:55 ragge Exp $    */
ragge
1.1
2 /*
3  * Copyright (c) 2004 Anders Magnusson (ragge@ludd.luth.se).
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  * 1. Redistributions of source code must retain the above copyright
10  *    notice, this list of conditions and the following disclaimer.
11  * 2. Redistributions in binary form must reproduce the above copyright
12  *    notice, this list of conditions and the following disclaimer in the
13  *    documentation and/or other materials provided with the distribution.
14  * 3. The name of the author may not be used to endorse or promote products
15  *    derived from this software without specific prior written permission
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28
29 #include "pass2.h"
30
ragge
1.3
31 #include <string.h>
pj
1.4
32 #include <stdlib.h>
33
34 #ifndef MIN
35 #define MIN(a,b) (((a)<(b))?(a):(b))
36 #endif
37
38 #ifndef MAX
39 #define MAX(a,b) (((a) > (b)) ? (a) : (b))
40 #endif
ragge
1.3
41
ragge
1.30
42 #define BDEBUG(x)       if (b2debug) printf x
43
ragge
1.50
44 #define mktemp(n, t)    mklnode(TEMP, 0, n, t)
45
ragge
1.66
46 /* main switch for new things not yet ready for all-day use */
47 /* #define ENABLE_NEW */
48
49
pj
1.8
50 static int dfsnum;
ragge
1.1
51
52 void saveip(struct interpass *ip);
ragge
1.56
53 void deljumps(struct p2env *);
ragge
1.1
54 void optdump(struct interpass *ip);
ragge
1.19
55 void printip(struct interpass *pole);
ragge
1.1
56
pj
1.21
57 static struct varinfo defsites;
ragge
1.19
58 struct interpass *storesave;
ragge
1.1
59
ragge
1.56
60 void bblocks_build(struct p2env *, struct labelinfo *, struct bblockinfo *);
61 void cfg_build(struct p2env *, struct labelinfo *labinfo);
pj
1.8
62 void cfg_dfs(struct basicblock *bbunsigned int parent
63              struct bblockinfo *bbinfo);
ragge
1.56
64 void dominators(struct p2env *, struct bblockinfo *bbinfo);
pj
1.9
65 struct basicblock *
66 ancestorwithlowestsemi(struct basicblock *bblockstruct bblockinfo *bbinfo);
67 void link(struct basicblock *parentstruct basicblock *child);
68 void computeDF(struct basicblock *bblockstruct bblockinfo *bbinfo);
pantzer
1.59
69 void printDF(struct p2env *p2estruct bblockinfo *bbinfo);
pj
1.21
70 void findTemps(struct interpass *ip);
ragge
1.56
71 void placePhiFunctions(struct p2env *, struct bblockinfo *bbinfo);
pantzer
1.59
72 void renamevar(struct p2env *p2e,struct basicblock *bblockstruct bblockinfo *bbinfo);
73 void removephi(struct p2env *p2estruct labelinfo *,struct bblockinfo *bbinfo);
ragge
1.56
74 void remunreach(struct p2env *);
pj
1.4
75
ragge
1.66
76 /* create "proper" basic blocks, add labels where needed (so bblocks have labels) */
77 /* run before bb generate */
78 static void add_labels(struct p2env*) ;
79
80 /* Perform trace scheduling, try to get rid of gotos as much as possible */
81 void TraceSchedule(struct p2env*) ;
82
83 #ifdef ENABLE_NEW
84 static void do_cse(struct p2envp2e) ;
85 #endif
86
87 /* Walk the complete set, performing a function on each node. 
88  * if type is given, apply function on only that type */
ragge
1.67
89 void WalkAll(struct p2envp2evoid (*f) (NODE*, void*), voidargint type) ;
ragge
1.66
90
91 void BBLiveDead(struct basicblockbblockint whatunsigned int variable) ;
92
93 /* Fill the live/dead code */
ragge
1.67
94 void LiveDead(struct p2envp2eint whatunsigned int variable) ;
ragge
1.66
95
pantzer
1.63
96 #ifdef PCC_DEBUG
97 void printflowdiagram(struct p2env *,struct labelinfo *labinfo,struct bblockinfo *bbinfo,char *);
98 #endif
99
ragge
1.38
100 void
ragge
1.56
101 optimize(struct p2env *p2e)
ragge
1.38
102 {
ragge
1.56
103         struct interpass *ipole = &p2e->ipole;
ragge
1.38
104         struct labelinfo labinfo;
105         struct bblockinfo bbinfo;
106
107         if (b2debug) {
108                 printf("initial links\n");
109                 printip(ipole);
110         }
111
112         if (xdeljumps)
ragge
1.56
113                 deljumps(p2e); /* Delete redundant jumps and dead code */
ragge
1.38
114
ragge
1.66
115         if (xssaflag)
116                 add_labels(p2e) ;
117 #ifdef ENABLE_NEW
118         do_cse(p2e);
119 #endif
120
ragge
1.38
121 #ifdef PCC_DEBUG
122         if (b2debug) {
123                 printf("links after deljumps\n");
124                 printip(ipole);
125         }
126 #endif
127         if (xssaflag || xtemps) {
ragge
1.56
128                 DLIST_INIT(&p2e->bblocksbbelem);
129                 bblocks_build(p2e, &labinfo, &bbinfo);
ragge
1.38
130                 BDEBUG(("Calling cfg_build\n"));
ragge
1.56
131                 cfg_build(p2e, &labinfo);
pantzer
1.63
132         
133 #ifdef PCC_DEBUG
134                 printflowdiagram(p2e, &labinfo, &bbinfo,"first");
135 #endif
ragge
1.38
136         }
137         if (xssaflag) {
138                 BDEBUG(("Calling dominators\n"));
ragge
1.56
139                 dominators(p2e, &bbinfo);
ragge
1.38
140                 BDEBUG(("Calling computeDF\n"));
ragge
1.56
141                 computeDF(DLIST_NEXT(&p2e->bblocksbbelem), &bbinfo);
pantzer
1.59
142
143                 if (b2debug) {
144                         printDF(p2e,&bbinfo);
145                 }
146
147                 BDEBUG(("Calling placePhiFunctions\n"));
148
149                 placePhiFunctions(p2e, &bbinfo);
150
151                 BDEBUG(("Calling renamevar\n"));
152
153                 renamevar(p2e,DLIST_NEXT(&p2e->bblocksbbelem), &bbinfo);
154
155                 BDEBUG(("Calling removephi\n"));
156
pantzer
1.63
157 #ifdef PCC_DEBUG
158                 printflowdiagram(p2e, &labinfo, &bbinfo,"ssa");
159 #endif
160
pantzer
1.59
161                 removephi(p2e,&labinfo,&bbinfo);
162
ragge
1.38
163                 BDEBUG(("Calling remunreach\n"));
ragge
1.66
164 /*              remunreach(p2e); */
pantzer
1.59
165                 
166                 /*
167                  Recalculate basic blocks and cfg that was destroyed
168                  by removephi
169                  */
ragge
1.66
170                 /* first, clean up all what deljumps should have done, and more */
171
172                 /*TODO: add the basic blocks done by the ssa code by hand. 
173                  * The trace scheduler should not change the order in which blocks
174                  * are executed or what data is calculated. Thus, the BBlock order
175                  * should remain correct.
176                  */
177
178 #ifdef ENABLE_NEW
179                 DLIST_INIT(&p2e->bblocksbbelem);
180                 bblocks_build(p2e, &labinfo, &bbinfo);
181                 BDEBUG(("Calling cfg_build\n"));
182                 cfg_build(p2e, &labinfo);
183
184                 TraceSchedule(p2e);
185 #ifdef PCC_DEBUG
186                 printflowdiagram(p2e, &labinfo, &bbinfo,"sched_trace");
187
188                 if (b2debug) {
189                         printf("after tracesched\n");
190                         printip(ipole);
191                         fflush(stdout) ;
192                 }
193 #endif
194 #endif
195
196                 /* Now, clean up the gotos we do not need any longer */
197                 if (xdeljumps)
198                         deljumps(p2e); /* Delete redundant jumps and dead code */
pantzer
1.59
199
200                 DLIST_INIT(&p2e->bblocksbbelem);
201                 bblocks_build(p2e, &labinfo, &bbinfo);
202                 BDEBUG(("Calling cfg_build\n"));
203                 cfg_build(p2e, &labinfo);
204
205 #ifdef PCC_DEBUG
pantzer
1.63
206                 printflowdiagram(p2e, &labinfo, &bbinfo,"no_phi");
207
pantzer
1.59
208                 if (b2debug) {
209                         printf("new tree\n");
210                         printip(ipole);
211                 }
ragge
1.38
212 #endif
213         }
214
215 #ifdef PCC_DEBUG
mickey
1.55
216         {
217                 int i;
218                 for (i = NIPPREGSi--; )
ragge
1.56
219                         if (p2e->epp->ipp_regs[i] != 0)
mickey
1.55
220                                 comperr("register error");
221         }
ragge
1.38
222 #endif
223
mickey
1.49
224         myoptim(ipole);
ragge
1.38
225 }
ragge
1.1
226
ragge
1.26
227 /*
228  * Delete unused labels, excess of labels, gotos to gotos.
229  * This routine can be made much more efficient.
230  */
ragge
1.1
231 void
ragge
1.56
232 deljumps(struct p2env *p2e)
ragge
1.1
233 {
ragge
1.56
234         struct interpass *ipole = &p2e->ipole;
ragge
1.45
235         struct interpass *ip, *n, *ip2, *start;
ragge
1.26
236         int gotone,lowhigh;
ragge
1.45
237         int *lblary, *jmparyszoijlab1lab2;
238         int del;
ragge
1.46
239         extern int negrel[];
240         extern size_t negrelsize;
ragge
1.26
241
ragge
1.56
242         low = p2e->ipp->ip_lblnum;
243         high = p2e->epp->ip_lblnum;
ragge
1.26
244
245 #ifdef notyet
246         mark = tmpmark(); /* temporary used memory */
247 #endif
ragge
1.28
248
ragge
1.26
249         sz = (high-low) * sizeof(int);
250         lblary = tmpalloc(sz);
ragge
1.45
251         jmpary = tmpalloc(sz);
252
253         /*
254          * XXX: Find the first two labels. They may not be deleted,
255          * because the register allocator expects them to be there.
256          * These will not be coalesced with any other label.
257          */
258         lab1 = lab2 = -1;
259         start = NULL;
260         DLIST_FOREACH(ipipoleqelem) {
261                 if (ip->type != IP_DEFLAB)
262                         continue;
263                 if (lab1 < 0)
264                         lab1 = ip->ip_lbl;
265                 else if (lab2 < 0) {
266                         lab2 = ip->ip_lbl;
267                         start = ip;
268                 } else  /* lab1 >= 0 && lab2 >= 0, we're done. */
269                         break;
270         }
271         if (lab1 < 0 || lab2 < 0)
272                 comperr("deljumps");
ragge
1.26
273
274 again:  gotone = 0;
ragge
1.28
275         memset(lblary0sz);
ragge
1.45
276         lblary[lab1 - low] = lblary[lab2 - low] = 1;
277         memset(jmpary0sz);
ragge
1.26
278
ragge
1.33
279         /* refcount and coalesce all labels */
ragge
1.38
280         DLIST_FOREACH(ipipoleqelem) {
ragge
1.45
281                 if (ip->type == IP_DEFLAB && ip->ip_lbl != lab1 &&
282                     ip->ip_lbl != lab2) {
ragge
1.27
283                         n = DLIST_NEXT(ipqelem);
ragge
1.45
284
285                         /*
286                          * Find unconditional jumps directly following a
stefan
1.51
287                          * label. Jumps jumping to themselves are not
288                          * taken into account.
ragge
1.45
289                          */
290                         if (n->type == IP_NODE && n->ip_node->n_op == GOTO) {
291                                 i = n->ip_node->n_left->n_lval;
stefan
1.51
292                                 if (i != ip->ip_lbl)
293                                         jmpary[ip->ip_lbl - low] = i;
ragge
1.45
294                         }
295
ragge
1.38
296                         while (n->type == IP_DEFLAB) {
ragge
1.45
297                                 if (n->ip_lbl != lab1 && n->ip_lbl != lab2 &&
298                                     lblary[n->ip_lbl-low] >= 0) {
299                                         /*
300                                          * If the label is used, mark the
301                                          * label to be coalesced with as
302                                          * used, too.
303                                          */
304                                         if (lblary[n->ip_lbl - low] > 0 &&
305                                             lblary[ip->ip_lbl - low] == 0)
306                                                 lblary[ip->ip_lbl - low] = 1;
307                                         lblary[n->ip_lbl - low] = -ip->ip_lbl;
308                                 }
ragge
1.27
309                                 n = DLIST_NEXT(nqelem);
310                         }
311                 }
ragge
1.28
312                 if (ip->type != IP_NODE)
313                         continue;
314                 o = ip->ip_node->n_op;
315                 if (o == GOTO)
316                         i = ip->ip_node->n_left->n_lval;
317                 else if (o == CBRANCH)
318                         i = ip->ip_node->n_right->n_lval;
319                 else
320                         continue;
ragge
1.45
321
322                 /*
323                  * Mark destination label i as used, if it is not already.
324                  * If i is to be merged with label j, mark j as used, too.
325                  */
326                 if (lblary[i - low] == 0)
327                         lblary[i-low] = 1;
328                 else if ((j = lblary[i - low]) < 0 && lblary[-j - low] == 0)
329                         lblary[-j - low] = 1;
ragge
1.27
330         }
331
ragge
1.28
332         /* delete coalesced/unused labels and rename gotos */
ragge
1.38
333         DLIST_FOREACH(ipipoleqelem) {
ragge
1.27
334                 n = DLIST_NEXT(ipqelem);
ragge
1.28
335                 if (n->type == IP_DEFLAB) {
336                         if (lblary[n->ip_lbl-low] <= 0) {
337                                 DLIST_REMOVE(nqelem);
338                                 gotone = 1;
ragge
1.26
339                         }
340                 }
ragge
1.45
341                 if (ip->type != IP_NODE)
ragge
1.26
342                         continue;
ragge
1.45
343                 o = ip->ip_node->n_op;
ragge
1.26
344                 if (o == GOTO)
ragge
1.45
345                         i = ip->ip_node->n_left->n_lval;
ragge
1.26
346                 else if (o == CBRANCH)
ragge
1.45
347                         i = ip->ip_node->n_right->n_lval;
ragge
1.26
348                 else
349                         continue;
ragge
1.45
350
351                 /* Simplify (un-)conditional jumps to unconditional jumps. */
352                 if (jmpary[i - low] > 0) {
353                         gotone = 1;
354                         i = jmpary[i - low];
355                         if (o == GOTO)
356                                 ip->ip_node->n_left->n_lval = i;
357                         else
358                                 ip->ip_node->n_right->n_lval = i;
359                 }
360
361                 /* Fixup for coalesced labels. */
ragge
1.26
362                 if (lblary[i-low] < 0) {
363                         if (o == GOTO)
ragge
1.45
364                                 ip->ip_node->n_left->n_lval = -lblary[i-low];
ragge
1.26
365                         else
ragge
1.45
366                                 ip->ip_node->n_right->n_lval = -lblary[i-low];
ragge
1.26
367                 }
368         }
ragge
1.27
369
ragge
1.28
370         /* Delete gotos to the next statement */
ragge
1.38
371         DLIST_FOREACH(ipipoleqelem) {
ragge
1.28
372                 n = DLIST_NEXT(ipqelem);
373                 if (n->type != IP_NODE)
ragge
1.26
374                         continue;
ragge
1.28
375                 o = n->ip_node->n_op;
ragge
1.26
376                 if (o == GOTO)
ragge
1.28
377                         i = n->ip_node->n_left->n_lval;
ragge
1.26
378                 else if (o == CBRANCH)
ragge
1.28
379                         i = n->ip_node->n_right->n_lval;
ragge
1.26
380                 else
381                         continue;
ragge
1.33
382
383                 ip2 = n;
ragge
1.38
384                 ip2 = DLIST_NEXT(ip2qelem);
ragge
1.33
385
ragge
1.28
386                 if (ip2->type != IP_DEFLAB)
ragge
1.1
387                         continue;
ragge
1.45
388                 if (ip2->ip_lbl == i && i != lab1 && i != lab2) {
ragge
1.1
389                         tfree(n->ip_node);
ragge
1.11
390                         DLIST_REMOVE(nqelem);
ragge
1.28
391                         gotone = 1;
ragge
1.1
392                 }
393         }
ragge
1.28
394
ragge
1.45
395         /*
396          * Transform cbranch cond, 1; goto 2; 1: ... into
397          * cbranch !cond, 2; 1: ...
398          */
399         DLIST_FOREACH(ipipoleqelem) {
400                 n = DLIST_NEXT(ipqelem);
401                 ip2 = DLIST_NEXT(nqelem);
402                 if (ip->type != IP_NODE || ip->ip_node->n_op != CBRANCH)
403                         continue;
404                 if (n->type != IP_NODE || n->ip_node->n_op != GOTO)
405                         continue;
406                 if (ip2->type != IP_DEFLAB)
407                         continue;
408                 i = ip->ip_node->n_right->n_lval;
409                 j = n->ip_node->n_left->n_lval;
410                 if (j == lab1 || j == lab2)
411                         continue;
412                 if (i != ip2->ip_lbl || i == lab1 || i == lab2)
413                         continue;
414                 ip->ip_node->n_right->n_lval = j;
ragge
1.46
415                 i = ip->ip_node->n_left->n_op;
gmcgarry
1.54
416                 if (i < EQ || i - EQ >= (int)negrelsize)
ragge
1.45
417                         comperr("deljumps: unexpected op");
ragge
1.46
418                 ip->ip_node->n_left->n_op = negrel[i - EQ];
ragge
1.45
419                 tfree(n->ip_node);
420                 DLIST_REMOVE(nqelem);
421                 gotone = 1;
422         }
423
424         /* Delete everything after a goto up to the next label. */
425         for (ip = startdel = 0ip != DLIST_ENDMARK(ipole);
426              ip = DLIST_NEXT(ipqelem)) {
427 loop:
428                 if ((n = DLIST_NEXT(ipqelem)) == DLIST_ENDMARK(ipole))
429                         break;
430                 if (n->type != IP_NODE) {
431                         del = 0;
432                         continue;
433                 }
434                 if (del) {
435                         tfree(n->ip_node);
436                         DLIST_REMOVE(nqelem);
437                         gotone = 1;
438                         goto loop;
439                 } else if (n->ip_node->n_op == GOTO)
440                         del = 1;
441         }
442
ragge
1.1
443         if (gotone)
444                 goto again;
ragge
1.28
445
446 #ifdef notyet
447         tmpfree(mark);
ragge
1.26
448 #endif
ragge
1.1
449 }
450
451 void
452 optdump(struct interpass *ip)
453 {
454         static char *nm[] = { "node""prolog""newblk""epilog""locctr",
455                 "deflab""defnam""asm" };
456         printf("type %s\n"nm[ip->type-1]);
457         switch (ip->type) {
458         case IP_NODE:
gmcgarry
1.52
459 #ifdef PCC_DEBUG
ragge
1.1
460                 fwalk(ip->ip_nodee2print0);
gmcgarry
1.52
461 #endif
ragge
1.1
462                 break;
463         case IP_DEFLAB:
464                 printf("label " LABFMT "\n"ip->ip_lbl);
465                 break;
466         case IP_ASM:
467                 printf(": %s\n"ip->ip_asm);
468                 break;
469         }
470 }
pj
1.4
471
472 /*
473  * Build the basic blocks, algorithm 9.1, pp 529 in Compilers.
474  *
475  * Also fills the labelinfo struct with information about which bblocks
476  * that contain which label.
477  */
478
ragge
1.30
479 void
ragge
1.56
480 bblocks_build(struct p2env *p2estruct labelinfo *labinfo,
ragge
1.38
481     struct bblockinfo *bbinfo)
pj
1.4
482 {
ragge
1.56
483         struct interpass *ipole = &p2e->ipole;
pj
1.4
484         struct interpass *ip;
485         struct basicblock *bb = NULL;
ragge
1.30
486         int lowhigh;
pj
1.8
487         int count = 0;
pj
1.4
488         int i;
489
ragge
1.30
490         BDEBUG(("bblocks_build (%p, %p)\n"labinfobbinfo));
ragge
1.56
491         low = p2e->ipp->ip_lblnum;
492         high = p2e->epp->ip_lblnum;
ragge
1.30
493
pj
1.4
494         /* 
495          * First statement is a leader.
496          * Any statement that is target of a jump is a leader.
497          * Any statement that immediately follows a jump is a leader.
498          */
ragge
1.38
499         DLIST_FOREACH(ipipoleqelem) {
ragge
1.31
500                 if (bb == NULL || (ip->type == IP_EPILOG) ||
501                     (ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) {
502                         bb = tmpalloc(sizeof(struct basicblock));
503                         bb->first = ip;
504                         SLIST_INIT(&bb->children);
505                         SLIST_INIT(&bb->parents);
506                         bb->dfnum = 0;
507                         bb->dfparent = 0;
508                         bb->semi = 0;
509                         bb->ancestor = 0;
510                         bb->idom = 0;
511                         bb->samedom = 0;
512                         bb->bucket = NULL;
513                         bb->df = NULL;
514                         bb->dfchildren = NULL;
515                         bb->Aorig = NULL;
516                         bb->Aphi = NULL;
pantzer
1.59
517                         SLIST_INIT(&bb->phi);
ragge
1.34
518                         bb->bbnum = count;
ragge
1.56
519                         DLIST_INSERT_BEFORE(&p2e->bblocksbbbbelem);
ragge
1.31
520                         count++;
521                 }
522                 bb->last = ip;
523                 if ((ip->type == IP_NODE) && (ip->ip_node->n_op == GOTO || 
524                     ip->ip_node->n_op == CBRANCH))
525                         bb = NULL;
526                 if (ip->type == IP_PROLOG)
527                         bb = NULL;
528         }
ragge
1.56
529         p2e->nbblocks = count;
ragge
1.30
530
ragge
1.31
531         if (b2debug) {
ragge
1.32
532                 printf("Basic blocks in func: %d, low %d, high %d\n",
533                     countlowhigh);
ragge
1.56
534                 DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
ragge
1.31
535                         printf("bb %p: first %p last %p\n"bb,
536                             bb->firstbb->last);
537                 }
538         }
pj
1.4
539
540         labinfo->low = low;
541         labinfo->size = high - low + 1;
542         labinfo->arr = tmpalloc(labinfo->size * sizeof(struct basicblock *));
ragge
1.42
543         for (i = 0i < labinfo->sizei++) {
pj
1.4
544                 labinfo->arr[i] = NULL;
545         }
pj
1.8
546         
547         bbinfo->size = count + 1;
548         bbinfo->arr = tmpalloc(bbinfo->size * sizeof(struct basicblock *));
ragge
1.42
549         for (i = 0i < bbinfo->sizei++) {
pj
1.8
550                 bbinfo->arr[i] = NULL;
551         }
pj
1.4
552
ragge
1.32
553         /* Build the label table */
ragge
1.56
554         DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
ragge
1.32
555                 if (bb->first->type == IP_DEFLAB)
pj
1.4
556                         labinfo->arr[bb->first->ip_lbl - low] = bb;
ragge
1.32
557         }
558
559         if (b2debug) {
560                 printf("Label table:\n");
561                 for (i = 0i < labinfo->sizei++)
562                         if (labinfo->arr[i])
563                                 printf("Label %d bblock %p\n"i+low,
564                                     labinfo->arr[i]);
pj
1.4
565         }
566 }
567
568 /*
569  * Build the control flow graph.
570  */
571
572 void
ragge
1.56
573 cfg_build(struct p2env *p2estruct labelinfo *labinfo)
pj
1.4
574 {
575         /* Child and parent nodes */
576         struct cfgnode *cnode
577         struct cfgnode *pnode;
578         struct basicblock *bb;
579         
ragge
1.56
580         DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
pj
1.4
581
582                 if (bb->first->type == IP_EPILOG) {
583                         break;
584                 }
585
586                 cnode = tmpalloc(sizeof(struct cfgnode));
587                 pnode = tmpalloc(sizeof(struct cfgnode));
588                 pnode->bblock = bb;
589
590                 if ((bb->last->type == IP_NODE) && 
gmcgarry
1.47
591                     (bb->last->ip_node->n_op == GOTO) &&
592                     (bb->last->ip_node->n_left->n_op == ICON))  {
pj
1.4
593                         if (bb->last->ip_node->n_left->n_lval - labinfo->low > 
594                             labinfo->size) {
595                                 comperr("Label out of range: %d, base %d"
596                                         bb->last->ip_node->n_left->n_lval
597                                         labinfo->low);
598                         }
599                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_left->n_lval - labinfo->low];
ragge
1.11
600                         SLIST_INSERT_LAST(&cnode->bblock->parentspnodecfgelem);
601                         SLIST_INSERT_LAST(&bb->childrencnodecfgelem);
pj
1.4
602                         continue;
603                 }
604                 if ((bb->last->type == IP_NODE) && 
605                     (bb->last->ip_node->n_op == CBRANCH)) {
606                         if (bb->last->ip_node->n_right->n_lval - labinfo->low > 
607                             labinfo->size
608                                 comperr("Label out of range: %d"
609                                         bb->last->ip_node->n_left->n_lval);
ragge
1.66
610
pj
1.4
611                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_right->n_lval - labinfo->low];
ragge
1.11
612                         SLIST_INSERT_LAST(&cnode->bblock->parentspnodecfgelem);
613                         SLIST_INSERT_LAST(&bb->childrencnodecfgelem);
pj
1.4
614                         cnode = tmpalloc(sizeof(struct cfgnode));
615                         pnode = tmpalloc(sizeof(struct cfgnode));
616                         pnode->bblock = bb;
617                 }
618
ragge
1.11
619                 cnode->bblock = DLIST_NEXT(bbbbelem);
620                 SLIST_INSERT_LAST(&cnode->bblock->parentspnodecfgelem);
621                 SLIST_INSERT_LAST(&bb->childrencnodecfgelem);
pj
1.4
622         }
623 }
pj
1.6
624
pj
1.8
625 void
626 cfg_dfs(struct basicblock *bbunsigned int parentstruct bblockinfo *bbinfo)
627 {
628         struct cfgnode *cnode;
629         
630         if (bb->dfnum != 0)
631                 return;
632
633         bb->dfnum = ++dfsnum;
634         bb->dfparent = parent;
635         bbinfo->arr[bb->dfnum] = bb;
ragge
1.11
636         SLIST_FOREACH(cnode, &bb->childrencfgelem) {
pj
1.8
637                 cfg_dfs(cnode->bblockbb->dfnumbbinfo);
638         }
pj
1.13
639         /* Don't bring in unreachable nodes in the future */
pj
1.20
640         bbinfo->size = dfsnum + 1;
pj
1.8
641 }
642
ragge
1.11
643 static bittype *
644 setalloc(int nelem)
645 {
646         bittype *b;
647         int sz = (nelem+NUMBITS-1)/NUMBITS;
648
649         b = tmpalloc(sz * sizeof(bittype));
650         memset(b0sz * sizeof(bittype));
651         return b;
652 }
653
pj
1.8
654 /*
655  * Algorithm 19.9, pp 414 from Appel.
656  */
657
658 void
ragge
1.56
659 dominators(struct p2env *p2estruct bblockinfo *bbinfo)
pj
1.8
660 {
661         struct cfgnode *cnode;
662         struct basicblock *bb, *y, *v;
663         struct basicblock *s, *sprime, *p;
pj
1.10
664         int hi;
pj
1.8
665
ragge
1.56
666         DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
ragge
1.11
667                 bb->bucket = setalloc(bbinfo->size);
668                 bb->df = setalloc(bbinfo->size);
669                 bb->dfchildren = setalloc(bbinfo->size);
pj
1.8
670         }
671
672         dfsnum = 0;
ragge
1.56
673         cfg_dfs(DLIST_NEXT(&p2e->bblocksbbelem), 0bbinfo);
pj
1.8
674
ragge
1.30
675         if (b2debug) {
676                 struct basicblock *bbb;
677                 struct cfgnode *ccnode;
678
ragge
1.56
679                 DLIST_FOREACH(bbb, &p2e->bblocksbbelem) {
ragge
1.30
680                         printf("Basic block %d, parents: "bbb->dfnum);
681                         SLIST_FOREACH(ccnode, &bbb->parentscfgelem) {
682                                 printf("%d, "ccnode->bblock->dfnum);
683                         }
684                         printf("\nChildren: ");
685                         SLIST_FOREACH(ccnode, &bbb->childrencfgelem) {
686                                 printf("%d, "ccnode->bblock->dfnum);
687                         }
688                         printf("\n");
pj
1.20
689                 }
690         }
691
pj
1.10
692         for(h = bbinfo->size - 1h > 1h--) {
693                 bb = bbinfo->arr[h];
pj
1.8
694                 p = s = bbinfo->arr[bb->dfparent];
ragge
1.11
695                 SLIST_FOREACH(cnode, &bb->parentscfgelem) {
pantzer
1.60
696                         if (cnode->bblock->dfnum ==0)
697                                 continue/* Ignore unreachable code */
698
pj
1.8
699                         if (cnode->bblock->dfnum <= bb->dfnum
700                                 sprime = cnode->bblock;
pj
1.10
701                         else 
702                                 sprime = bbinfo->arr[ancestorwithlowestsemi
703                                               (cnode->bblockbbinfo)->semi];
pj
1.8
704                         if (sprime->dfnum < s->dfnum)
705                                 s = sprime;
706                 }
707                 bb->semi = s->dfnum;
pj
1.10
708                 BITSET(s->bucketbb->dfnum);
pj
1.8
709                 link(pbb);
710                 for (i = 1i < bbinfo->sizei++) {
pj
1.10
711                         if(TESTBIT(p->bucketi)) {
pj
1.8
712                                 v = bbinfo->arr[i];
pj
1.10
713                                 y = ancestorwithlowestsemi(vbbinfo);
714                                 if (y->semi == v->semi
pj
1.8
715                                         v->idom = p->dfnum;
716                                 else
717                                         v->samedom = y->dfnum;
718                         }
719                 }
720                 memset(p->bucket0, (bbinfo->size + 7)/8);
721         }
ragge
1.30
722
723         if (b2debug) {
724                 printf("Num\tSemi\tAncest\tidom\n");
ragge
1.56
725                 DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
ragge
1.30
726                         printf("%d\t%d\t%d\t%d\n"bb->dfnumbb->semi,
727                             bb->ancestorbb->idom);
728                 }
pj
1.10
729         }
ragge
1.30
730
pj
1.10
731         for(h = 2h < bbinfo->sizeh++) {
732                 bb = bbinfo->arr[h];
733                 if (bb->samedom != 0) {
pj
1.8
734                         bb->idom = bbinfo->arr[bb->samedom]->idom;
pj
1.10
735                 }
736         }
ragge
1.56
737         DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
pj
1.10
738                 if (bb->idom != 0 && bb->idom != bb->dfnum) {
ragge
1.30
739                         BDEBUG(("Setting child %d of %d\n",
740                             bb->dfnumbbinfo->arr[bb->idom]->dfnum));
pj
1.10
741                         BITSET(bbinfo->arr[bb->idom]->dfchildrenbb->dfnum);
742                 }
pj
1.8
743         }
744 }
745
746
747 struct basicblock *
748 ancestorwithlowestsemi(struct basicblock *bblockstruct bblockinfo *bbinfo)
749 {
750         struct basicblock *u = bblock;
751         struct basicblock *v = bblock;
752
753         while (v->ancestor != 0) {
754                 if (bbinfo->arr[v->semi]->dfnum < 
pj
1.10
755                     bbinfo->arr[u->semi]->dfnum
pj
1.8
756                         u = v;
757                 v = bbinfo->arr[v->ancestor];
758         }
759         return u;
760 }
761
762 void
763 link(struct basicblock *parentstruct basicblock *child)
764 {
765         child->ancestor = parent->dfnum;
766 }
767
768 void
769 computeDF(struct basicblock *bblockstruct bblockinfo *bbinfo)
770 {
771         struct cfgnode *cnode;
pj
1.10
772         int hi;
pj
1.8
773         
ragge
1.11
774         SLIST_FOREACH(cnode, &bblock->childrencfgelem) {
pj
1.8
775                 if (cnode->bblock->idom != bblock->dfnum)
776                         BITSET(bblock->dfcnode->bblock->dfnum);
777         }
pj
1.10
778         for (h = 1h < bbinfo->sizeh++) {
779                 if (!TESTBIT(bblock->dfchildrenh))
780                         continue;
781                 computeDF(bbinfo->arr[h], bbinfo);
pj
1.8
782                 for (i = 1i < bbinfo->sizei++) {
pj
1.10
783                         if (TESTBIT(bbinfo->arr[h]->dfi) && 
pantzer
1.59
784                             (bbinfo->arr[i] == bblock ||
785                              (bblock->dfnum != bbinfo->arr[i]->idom))) 
pj
1.8
786                             BITSET(bblock->dfi);
787                 }
788         }
789 }
pj
1.15
790
pantzer
1.59
791 void printDF(struct p2env *p2estruct bblockinfo *bbinfo)
792 {
793         struct basicblock *bb;
794         int i;
795
796         printf("Dominance frontiers:\n");
797     
798         DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
799                 printf("bb %d : "bb->dfnum);
800         
801                 for (i=1i < bbinfo->size;i++) {
802                         if (TESTBIT(bb->df,i)) {
803                                 printf("%d ",i);
804                         }
805                 }
806             
807                 printf("\n");
808         }
809     
810 }
811
812
813
pj
1.21
814 static struct basicblock *currbb;
815 static struct interpass *currip;
816
817 /* Helper function for findTemps, Find assignment nodes. */
818 static void
ragge
1.57
819 searchasg(NODE *pvoid *arg)
pj
1.21
820 {
821         struct pvarinfo *pv;
pantzer
1.59
822         int tempnr;
823         struct varstack *stacke;
824     
pj
1.21
825         if (p->n_op != ASSIGN)
826                 return;
827
828         if (p->n_left->n_op != TEMP)
829                 return;
830
pantzer
1.59
831         tempnr=regno(p->n_left)-defsites.low;
832     
833         BITSET(currbb->Aorigtempnr);
834         
pj
1.21
835         pv = tmpcalloc(sizeof(struct pvarinfo));
pantzer
1.59
836         pv->next = defsites.arr[tempnr];
pj
1.21
837         pv->bb = currbb;
pantzer
1.59
838         pv->n_type = p->n_left->n_type;
839         
840         defsites.arr[tempnr] = pv;
841         
842         
843         if (SLIST_FIRST(&defsites.stack[tempnr])==NULL) {
844                 stacke=tmpcalloc(sizeof (struct varstack));
pantzer
1.62
845                 stacke->tmpregno=0;
pantzer
1.59
846                 SLIST_INSERT_FIRST(&defsites.stack[tempnr],stacke,varstackelem);
847         }
pj
1.21
848 }
849
850 /* Walk the interpass looking for assignment nodes. */
851 void findTemps(struct interpass *ip)
pj
1.20
852 {
853         if (ip->type != IP_NODE)
854                 return;
855
pj
1.21
856         currip = ip;
857
ragge
1.57
858         walkf(ip->ip_nodesearchasg0);
pj
1.20
859 }
860
861 /*
862  * Algorithm 19.6 from Appel.
863  */
864
865 void
ragge
1.56
866 placePhiFunctions(struct p2env *p2estruct bblockinfo *bbinfo)
pj
1.20
867 {
868         struct basicblock *bb;
pantzer
1.59
869         struct basicblock *y;
pj
1.20
870         struct interpass *ip;
pantzer
1.59
871         int maxtmpijk;
pj
1.20
872         struct pvarinfo *n;
873         struct cfgnode *cnode;
874         TWORD ntype;
pj
1.22
875         struct pvarinfo *pv;
pantzer
1.59
876         struct phiinfo *phi;
877         int phifound;
pj
1.20
878
ragge
1.56
879         bb = DLIST_NEXT(&p2e->bblocksbbelem);
pj
1.20
880         defsites.low = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
ragge
1.56
881         bb = DLIST_PREV(&p2e->bblocksbbelem);
pj
1.20
882         maxtmp = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
883         defsites.size = maxtmp - defsites.low + 1;
884         defsites.arr = tmpcalloc(defsites.size*sizeof(struct pvarinfo *));
pantzer
1.59
885         defsites.stack = tmpcalloc(defsites.size*sizeof(SLIST_HEAD(, varstack)));
886         
887         for (i=0;i<defsites.size;i++)
888                 SLIST_INIT(&defsites.stack[i]); 
889         
pj
1.21
890         /* Find all defsites */
ragge
1.56
891         DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
pj
1.21
892                 currbb = bb;
pj
1.20
893                 ip = bb->first;
pj
1.22
894                 bb->Aorig = setalloc(defsites.size);
895                 bb->Aphi = setalloc(defsites.size);
896                 
pj
1.20
897                 while (ip != bb->last) {
pj
1.21
898                         findTemps(ip);
pj
1.20
899                         ip = DLIST_NEXT(ipqelem);
900                 }
901                 /* Make sure we get the last statement in the bblock */
pj
1.21
902                 findTemps(ip);
pj
1.20
903         }
pantzer
1.59
904     
pj
1.21
905         /* For each variable */
pantzer
1.59
906         for (i = 0i < defsites.sizei++) {
pj
1.21
907                 /* While W not empty */
pj
1.20
908                 while (defsites.arr[i] != NULL) {
pj
1.21
909                         /* Remove some node n from W */
pj
1.20
910                         n = defsites.arr[i];
911                         defsites.arr[i] = n->next;
pj
1.21
912                         /* For each y in n->bb->df */
pj
1.20
913                         for (j = 0j < bbinfo->sizej++) {
pj
1.22
914                                 if (!TESTBIT(n->bb->dfj))
pj
1.20
915                                         continue;
pj
1.22
916                                 
917                                 if (TESTBIT(bbinfo->arr[j]->Aphii))
918                                         continue;
919
pantzer
1.59
920                                 y=bbinfo->arr[j];
921                                 ntype = n->n_type;
pj
1.20
922                                 k = 0;
pj
1.21
923                                 /* Amount of predecessors for y */
pantzer
1.59
924                                 SLIST_FOREACH(cnode, &y->parentscfgelem
pj
1.20
925                                         k++;
pantzer
1.59
926                                 /* Construct phi(...) 
927                                 */
928                             
929                                 phifound=0;
930                             
931                                 SLIST_FOREACH(phi, &y->phiphielem) {
932                                     if (phi->tmpregno==i+defsites.low)
933                                         phifound++;
934                                 }
935                             
936                                 if (phifound==0) {
937                                         if (b2debug)
pantzer
1.61
938                                             printf("Phi in %d (%p) for %d\n",y->dfnum,y,i+defsites.low);
pantzer
1.59
939
940                                         phi = tmpcalloc(sizeof(struct phiinfo));
941                             
942                                         phi->tmpregno=i+defsites.low;
943                                         phi->size=k;
944                                         phi->n_type=ntype;
pantzer
1.62
945                                         phi->intmpregno=tmpcalloc(k*sizeof(int));
pantzer
1.59
946                             
947                                         SLIST_INSERT_LAST(&y->phi,phi,phielem);
948                                 } else {
949               &