Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:gmcgarry:20090818084225

Diff

Diff from 1.71 to:

Annotations

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

Annotated File View

gmcgarry
1.71
1 /*      $Id: optim2.c,v 1.71 2009/08/18 08:42:25 gmcgarry 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) {
gmcgarry
1.70
291                                 i = (int)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)
gmcgarry
1.70
316                         i = (int)ip->ip_node->n_left->n_lval;
ragge
1.28
317                 else if (o == CBRANCH)
gmcgarry
1.70
318                         i = (int)ip->ip_node->n_right->n_lval;
ragge
1.28
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)
gmcgarry
1.70
345                         i = (int)ip->ip_node->n_left->n_lval;
ragge
1.26
346                 else if (o == CBRANCH)
gmcgarry
1.70
347                         i = (int)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)
gmcgarry
1.70
377                         i = (int)n->ip_node->n_left->n_lval;
ragge
1.69
378 #if 0 /* XXX must check for side effects in expression */
ragge
1.26
379                 else if (o == CBRANCH)
gmcgarry
1.70
380                         i = (int)n->ip_node->n_right->n_lval;
ragge
1.69
381 #endif
ragge
1.26
382                 else
383                         continue;
ragge
1.33
384
385                 ip2 = n;
ragge
1.38
386                 ip2 = DLIST_NEXT(ip2qelem);
ragge
1.33
387
ragge
1.28
388                 if (ip2->type != IP_DEFLAB)
ragge
1.1
389                         continue;
ragge
1.45
390                 if (ip2->ip_lbl == i && i != lab1 && i != lab2) {
ragge
1.1
391                         tfree(n->ip_node);
ragge
1.11
392                         DLIST_REMOVE(nqelem);
ragge
1.28
393                         gotone = 1;
ragge
1.1
394                 }
395         }
ragge
1.28
396
ragge
1.45
397         /*
398          * Transform cbranch cond, 1; goto 2; 1: ... into
399          * cbranch !cond, 2; 1: ...
400          */
401         DLIST_FOREACH(ipipoleqelem) {
402                 n = DLIST_NEXT(ipqelem);
403                 ip2 = DLIST_NEXT(nqelem);
404                 if (ip->type != IP_NODE || ip->ip_node->n_op != CBRANCH)
405                         continue;
406                 if (n->type != IP_NODE || n->ip_node->n_op != GOTO)
407                         continue;
408                 if (ip2->type != IP_DEFLAB)
409                         continue;
gmcgarry
1.70
410                 i = (int)ip->ip_node->n_right->n_lval;
411                 j = (int)n->ip_node->n_left->n_lval;
ragge
1.45
412                 if (j == lab1 || j == lab2)
413                         continue;
414                 if (i != ip2->ip_lbl || i == lab1 || i == lab2)
415                         continue;
416                 ip->ip_node->n_right->n_lval = j;
ragge
1.46
417                 i = ip->ip_node->n_left->n_op;
gmcgarry
1.54
418                 if (i < EQ || i - EQ >= (int)negrelsize)
ragge
1.45
419                         comperr("deljumps: unexpected op");
ragge
1.46
420                 ip->ip_node->n_left->n_op = negrel[i - EQ];
ragge
1.45
421                 tfree(n->ip_node);
422                 DLIST_REMOVE(nqelem);
423                 gotone = 1;
424         }
425
426         /* Delete everything after a goto up to the next label. */
427         for (ip = startdel = 0ip != DLIST_ENDMARK(ipole);
428              ip = DLIST_NEXT(ipqelem)) {
429 loop:
430                 if ((n = DLIST_NEXT(ipqelem)) == DLIST_ENDMARK(ipole))
431                         break;
432                 if (n->type != IP_NODE) {
433                         del = 0;
434                         continue;
435                 }
436                 if (del) {
437                         tfree(n->ip_node);
438                         DLIST_REMOVE(nqelem);
439                         gotone = 1;
440                         goto loop;
441                 } else if (n->ip_node->n_op == GOTO)
442                         del = 1;
443         }
444
ragge
1.1
445         if (gotone)
446                 goto again;
ragge
1.28
447
448 #ifdef notyet
449         tmpfree(mark);
ragge
1.26
450 #endif
ragge
1.1
451 }
452
453 void
454 optdump(struct interpass *ip)
455 {
456         static char *nm[] = { "node""prolog""newblk""epilog""locctr",
457                 "deflab""defnam""asm" };
458         printf("type %s\n"nm[ip->type-1]);
459         switch (ip->type) {
460         case IP_NODE:
gmcgarry
1.52
461 #ifdef PCC_DEBUG
ragge
1.1
462                 fwalk(ip->ip_nodee2print0);
gmcgarry
1.52
463 #endif
ragge
1.1
464                 break;
465         case IP_DEFLAB:
466                 printf("label " LABFMT "\n"ip->ip_lbl);
467                 break;
468         case IP_ASM:
469                 printf(": %s\n"ip->ip_asm);
470                 break;
471         }
472 }
pj
1.4
473
474 /*
475  * Build the basic blocks, algorithm 9.1, pp 529 in Compilers.
476  *
477  * Also fills the labelinfo struct with information about which bblocks
478  * that contain which label.
479  */
480
ragge
1.30
481 void
ragge
1.56
482 bblocks_build(struct p2env *p2estruct labelinfo *labinfo,
ragge
1.38
483     struct bblockinfo *bbinfo)
pj
1.4
484 {
ragge
1.56
485         struct interpass *ipole = &p2e->ipole;
pj
1.4
486         struct interpass *ip;
487         struct basicblock *bb = NULL;
ragge
1.30
488         int lowhigh;
pj
1.8
489         int count = 0;
pj
1.4
490         int i;
491
ragge
1.30
492         BDEBUG(("bblocks_build (%p, %p)\n"labinfobbinfo));
ragge
1.56
493         low = p2e->ipp->ip_lblnum;
494         high = p2e->epp->ip_lblnum;
ragge
1.30
495
pj
1.4
496         /* 
497          * First statement is a leader.
498          * Any statement that is target of a jump is a leader.
499          * Any statement that immediately follows a jump is a leader.
500          */
ragge
1.38
501         DLIST_FOREACH(ipipoleqelem) {
ragge
1.31
502                 if (bb == NULL || (ip->type == IP_EPILOG) ||
503                     (ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) {
504                         bb = tmpalloc(sizeof(struct basicblock));
505                         bb->first = ip;
506                         SLIST_INIT(&bb->children);
507                         SLIST_INIT(&bb->parents);
508                         bb->dfnum = 0;
509                         bb->dfparent = 0;
510                         bb->semi = 0;
511                         bb->ancestor = 0;
512                         bb->idom = 0;
513                         bb->samedom = 0;
514                         bb->bucket = NULL;
515                         bb->df = NULL;
516                         bb->dfchildren = NULL;
517                         bb->Aorig = NULL;
518                         bb->Aphi = NULL;
pantzer
1.59
519                         SLIST_INIT(&bb->phi);
ragge
1.34
520                         bb->bbnum = count;
ragge
1.56
521                         DLIST_INSERT_BEFORE(&p2e->bblocksbbbbelem);
ragge
1.31
522                         count++;
523                 }
524                 bb->last = ip;
525                 if ((ip->type == IP_NODE) && (ip->ip_node->n_op == GOTO || 
526                     ip->ip_node->n_op == CBRANCH))
527                         bb = NULL;
528                 if (ip->type == IP_PROLOG)
529                         bb = NULL;
530         }
ragge
1.56
531         p2e->nbblocks = count;
ragge
1.30
532
ragge
1.31
533         if (b2debug) {
ragge
1.32
534                 printf("Basic blocks in func: %d, low %d, high %d\n",
535                     countlowhigh);
ragge
1.56
536                 DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
ragge
1.31
537                         printf("bb %p: first %p last %p\n"bb,
538                             bb->firstbb->last);
539                 }
540         }
pj
1.4
541
542         labinfo->low = low;
543         labinfo->size = high - low + 1;
544         labinfo->arr = tmpalloc(labinfo->size * sizeof(struct basicblock *));
ragge
1.42
545         for (i = 0i < labinfo->sizei++) {
pj
1.4
546                 labinfo->arr[i] = NULL;
547         }
pj
1.8
548         
549         bbinfo->size = count + 1;
550         bbinfo->arr = tmpalloc(bbinfo->size * sizeof(struct basicblock *));
ragge
1.42
551         for (i = 0i < bbinfo->sizei++) {
pj
1.8
552                 bbinfo->arr[i] = NULL;
553         }
pj
1.4
554
ragge
1.32
555         /* Build the label table */
ragge
1.56
556         DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
ragge
1.32
557                 if (bb->first->type == IP_DEFLAB)
pj
1.4
558                         labinfo->arr[bb->first->ip_lbl - low] = bb;
ragge
1.32
559         }
560
561         if (b2debug) {
562                 printf("Label table:\n");
563                 for (i = 0i < labinfo->sizei++)
564                         if (labinfo->arr[i])
565                                 printf("Label %d bblock %p\n"i+low,
566                                     labinfo->arr[i]);
pj
1.4
567         }
568 }
569
570 /*
571  * Build the control flow graph.
572  */
573
574 void
ragge
1.56
575 cfg_build(struct p2env *p2estruct labelinfo *labinfo)
pj
1.4
576 {
577         /* Child and parent nodes */
578         struct cfgnode *cnode
579         struct cfgnode *pnode;
580         struct basicblock *bb;
581         
ragge
1.56
582         DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
pj
1.4
583
584                 if (bb->first->type == IP_EPILOG) {
585                         break;
586                 }
587
588                 cnode = tmpalloc(sizeof(struct cfgnode));
589                 pnode = tmpalloc(sizeof(struct cfgnode));
590                 pnode->bblock = bb;
591
592                 if ((bb->last->type == IP_NODE) && 
gmcgarry
1.47
593                     (bb->last->ip_node->n_op == GOTO) &&
594                     (bb->last->ip_node->n_left->n_op == ICON))  {
pj
1.4
595                         if (bb->last->ip_node->n_left->n_lval - labinfo->low > 
596                             labinfo->size) {
597                                 comperr("Label out of range: %d, base %d"
598                                         bb->last->ip_node->n_left->n_lval
599                                         labinfo->low);
600                         }
601                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_left->n_lval - labinfo->low];
ragge
1.11
602                         SLIST_INSERT_LAST(&cnode->bblock->parentspnodecfgelem);
603                         SLIST_INSERT_LAST(&bb->childrencnodecfgelem);
pj
1.4
604                         continue;
605                 }
606                 if ((bb->last->type == IP_NODE) && 
607                     (bb->last->ip_node->n_op == CBRANCH)) {
608                         if (bb->last->ip_node->n_right->n_lval - labinfo->low > 
609                             labinfo->size
610                                 comperr("Label out of range: %d"
611                                         bb->last->ip_node->n_left->n_lval);
ragge
1.66
612
pj
1.4
613                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_right->n_lval - labinfo->low];
ragge
1.11
614                         SLIST_INSERT_LAST(&cnode->bblock->parentspnodecfgelem);
615                         SLIST_INSERT_LAST(&bb->childrencnodecfgelem);
pj
1.4
616                         cnode = tmpalloc(sizeof(struct cfgnode));
617                         pnode = tmpalloc(sizeof(struct cfgnode));
618                         pnode->bblock = bb;
619                 }
620
ragge
1.11
621                 cnode->bblock = DLIST_NEXT(bbbbelem);
622                 SLIST_INSERT_LAST(&cnode->bblock->parentspnodecfgelem);
623                 SLIST_INSERT_LAST(&bb->childrencnodecfgelem);
pj
1.4
624         }
625 }
pj
1.6
626
pj
1.8
627 void
628 cfg_dfs(struct basicblock *bbunsigned int parentstruct bblockinfo *bbinfo)
629 {
630         struct cfgnode *cnode;
631         
632         if (bb->dfnum != 0)
633                 return;
634
635         bb->dfnum = ++dfsnum;
636         bb->dfparent = parent;
637         bbinfo->arr[bb->dfnum] = bb;
ragge
1.11
638         SLIST_FOREACH(cnode, &bb->childrencfgelem) {
pj
1.8
639                 cfg_dfs(cnode->bblockbb->dfnumbbinfo);
640         }
pj
1.13
641         /* Don't bring in unreachable nodes in the future */
pj
1.20
642         bbinfo->size = dfsnum + 1;
pj
1.8
643 }
644
ragge
1.11
645 static bittype *
646 setalloc(int nelem)
647 {
648         bittype *b;
649         int sz = (nelem+NUMBITS-1)/NUMBITS;
650
651         b = tmpalloc(sz * sizeof(bittype));
652         memset(b0sz * sizeof(bittype));
653         return b;
654 }
655
pj
1.8
656 /*
657  * Algorithm 19.9, pp 414 from Appel.
658  */
659
660 void
ragge
1.56
661 dominators(struct p2env *p2estruct bblockinfo *bbinfo)
pj
1.8
662 {
663         struct cfgnode *cnode;
664         struct basicblock *bb, *y, *v;
665         struct basicblock *s, *sprime, *p;
pj
1.10
666         int hi;
pj
1.8
667
ragge
1.56
668         DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
ragge
1.11
669                 bb->bucket = setalloc(bbinfo->size);
670                 bb->df = setalloc(bbinfo->size);
671                 bb->dfchildren = setalloc(bbinfo->size);
pj
1.8
672         }
673
674         dfsnum = 0;
ragge
1.56
675         cfg_dfs(DLIST_NEXT(&p2e->bblocksbbelem), 0bbinfo);
pj
1.8
676
ragge
1.30
677         if (b2debug) {
678                 struct basicblock *bbb;
679                 struct cfgnode *ccnode;
680
ragge
1.56
681                 DLIST_FOREACH(bbb, &p2e->bblocksbbelem) {
ragge
1.30
682                         printf("Basic block %d, parents: "bbb->dfnum);
683                         SLIST_FOREACH(ccnode, &bbb->parentscfgelem) {
684                                 printf("%d, "ccnode->bblock->dfnum);
685                         }
686                         printf("\nChildren: ");
687                         SLIST_FOREACH(ccnode, &bbb->childrencfgelem) {
688                                 printf("%d, "ccnode->bblock->dfnum);
689                         }
690                         printf("\n");
pj
1.20
691                 }
692         }
693
pj
1.10
694         for(h = bbinfo->size - 1h > 1h--) {
695                 bb = bbinfo->arr[h];
pj
1.8
696                 p = s = bbinfo->arr[bb->dfparent];
ragge
1.11
697                 SLIST_FOREACH(cnode, &bb->parentscfgelem) {
pantzer
1.60
698                         if (cnode->bblock->dfnum ==0)
699                                 continue/* Ignore unreachable code */
700
pj
1.8
701                         if (cnode->bblock->dfnum <= bb->dfnum
702                                 sprime = cnode->bblock;
pj
1.10
703                         else 
704                                 sprime = bbinfo->arr[ancestorwithlowestsemi
705                                               (cnode->bblockbbinfo)->semi];
pj
1.8
706                         if (sprime->dfnum < s->dfnum)
707                                 s = sprime;
708                 }
709                 bb->semi = s->dfnum;
pj
1.10
710                 BITSET(s->bucketbb->dfnum);
pj
1.8
711                 link(pbb);
712                 for (i = 1i < bbinfo->sizei++) {
pj
1.10
713                         if(TESTBIT(p->bucketi)) {
pj
1.8
714                                 v = bbinfo->arr[i];
pj
1.10
715                                 y = ancestorwithlowestsemi(vbbinfo);
716                                 if (y->semi == v->semi
pj
1.8
717                                         v->idom = p->dfnum;
718                                 else
719                                         v->samedom = y->dfnum;
720                         }
721                 }
722                 memset(p->bucket0, (bbinfo->size + 7)/8);
723         }
ragge
1.30
724
725         if (b2debug) {
726                 printf("Num\tSemi\tAncest\tidom\n");
ragge
1.56
727                 DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
ragge
1.30
728                         printf("%d\t%d\t%d\t%d\n"bb->dfnumbb->semi,
729                             bb->ancestorbb->idom);
730                 }
pj
1.10
731         }
ragge
1.30
732
pj
1.10
733         for(h = 2h < bbinfo->sizeh++) {
734                 bb = bbinfo->arr[h];
735                 if (bb->samedom != 0) {
pj
1.8
736                         bb->idom = bbinfo->arr[bb->samedom]->idom;
pj
1.10
737                 }
738         }
ragge
1.56
739         DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
pj
1.10
740                 if (bb->idom != 0 && bb->idom != bb->dfnum) {
ragge
1.30
741                         BDEBUG(("Setting child %d of %d\n",
742                             bb->dfnumbbinfo->arr[bb->idom]->dfnum));
pj
1.10
743                         BITSET(bbinfo->arr[bb->idom]->dfchildrenbb->dfnum);
744                 }
pj
1.8
745         }
746 }
747
748
749 struct basicblock *
750 ancestorwithlowestsemi(struct basicblock *bblockstruct bblockinfo *bbinfo)
751 {
752         struct basicblock *u = bblock;
753         struct basicblock *v = bblock;
754
755         while (v->ancestor != 0) {
756                 if (bbinfo->arr[v->semi]->dfnum < 
pj
1.10
757                     bbinfo->arr[u->semi]->dfnum
pj
1.8
758                         u = v;
759                 v = bbinfo->arr[v->ancestor];
760         }
761         return u;
762 }
763
764 void
765 link(struct basicblock *parentstruct basicblock *child)
766 {
767         child->ancestor = parent->dfnum;
768 }
769
770 void
771 computeDF(struct basicblock *bblockstruct bblockinfo *bbinfo)
772 {
773         struct cfgnode *cnode;
pj
1.10
774         int hi;
pj
1.8
775         
ragge
1.11
776         SLIST_FOREACH(cnode, &bblock->childrencfgelem) {
pj
1.8
777                 if (cnode->bblock->idom != bblock->dfnum)
778                         BITSET(bblock->dfcnode->bblock->dfnum);
779         }
pj
1.10
780         for (h = 1h < bbinfo->sizeh++) {
781                 if (!TESTBIT(bblock->dfchildrenh))
782                         continue;
783                 computeDF(bbinfo->arr[h], bbinfo);
pj
1.8
784                 for (i = 1i < bbinfo->sizei++) {
pj
1.10
785                         if (TESTBIT(bbinfo->arr[h]->dfi) && 
pantzer
1.59
786                             (bbinfo->arr[i] == bblock ||
787                              (bblock->dfnum != bbinfo->arr[i]->idom))) 
pj
1.8
788                             BITSET(bblock->dfi);
789                 }
790         }
791 }
pj
1.15
792
pantzer
1.59
793 void printDF(struct p2env *p2estruct bblockinfo *bbinfo)
794 {
795         struct basicblock *bb;
796         int i;
797
798         printf("Dominance frontiers:\n");
799     
800         DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
801                 printf("bb %d : "bb->dfnum);
802         
803                 for (i=1i < bbinfo->size;i++) {
804                         if (TESTBIT(bb->df,i)) {
805                                 printf("%d ",i);
806                         }
807                 }
808             
809                 printf("\n");
810         }
811     
812 }
813
814
815
pj
1.21
816 static struct basicblock *currbb;
817 static struct interpass *currip;
818
819 /* Helper function for findTemps, Find assignment nodes. */
820 static void
ragge
1.57
821 searchasg(NODE *pvoid *arg)
pj
1.21
822 {
823         struct pvarinfo *pv;
pantzer
1.59
824         int tempnr;
825         struct varstack *stacke;
826     
pj
1.21
827         if (p->n_op != ASSIGN)
828                 return;
829
830         if (p->n_left->n_op != TEMP)
831                 return;
832
pantzer
1.59
833         tempnr=regno(p->n_left)-defsites.low;
834     
835         BITSET(currbb->Aorigtempnr);
836         
pj
1.21
837         pv = tmpcalloc(sizeof(struct pvarinfo));
pantzer
1.59
838         pv->next = defsites.arr[tempnr];
pj
1.21
839         pv->bb = currbb;
pantzer
1.59
840         pv->n_type = p->n_left->n_type;
841         
842         defsites.arr[tempnr] = pv;
843         
844         
845         if (SLIST_FIRST(&defsites.stack[tempnr])==NULL) {
846                 stacke=tmpcalloc(sizeof (struct varstack));
pantzer
1.62
847                 stacke->tmpregno=0;
pantzer
1.59
848                 SLIST_INSERT_FIRST(&defsites.stack[tempnr],stacke,varstackelem);
849         }
pj
1.21
850 }
851
852 /* Walk the interpass looking for assignment nodes. */
853 void findTemps(struct interpass *ip)
pj
1.20
854 {
855         if (ip->type != IP_NODE)
856                 return;
857
pj
1.21
858         currip = ip;
859
ragge
1.57
860         walkf(ip->ip_nodesearchasg0);
pj
1.20
861 }
862
863 /*
864  * Algorithm 19.6 from Appel.
865  */
866
867 void
ragge
1.56
868 placePhiFunctions(struct p2env *p2estruct bblockinfo *bbinfo)
pj
1.20
869 {
870         struct basicblock *bb;
pantzer
1.59
871         struct basicblock *y;
pj
1.20
872         struct interpass *ip;
pantzer
1.59
873         int maxtmpijk;
pj
1.20
874         struct pvarinfo *n;
875         struct cfgnode *cnode;
876         TWORD ntype;
pj
1.22
877         struct pvarinfo *pv;
pantzer
1.59
878         struct phiinfo *phi;
879         int phifound;
pj
1.20
880
ragge
1.56
881         bb = DLIST_NEXT(&p2e->bblocksbbelem);
pj
1.20
882         defsites.low = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
ragge
1.56
883         bb = DLIST_PREV(&p2e->bblocksbbelem);
pj
1.20
884         maxtmp = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
885         defsites.size = maxtmp - defsites.low + 1;
886         defsites.arr = tmpcalloc(defsites.size*sizeof(struct pvarinfo *));
pantzer
1.59
887         defsites.stack = tmpcalloc(defsites.size*sizeof(SLIST_HEAD(, varstack)));
888         
889         for (i=0;i<defsites.size;i++)
890                 SLIST_INIT(&defsites.stack[i]); 
891         
pj
1.21
892         /* Find all defsites */
ragge
1.56
893         DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
pj
1.21
894                 currbb = bb;
pj
1.20
895                 ip = bb->first;
pj
1.22
896                 bb->Aorig = setalloc(defsites.size);
897                 bb->Aphi = setalloc(defsites.size);
898                 
pj
1.20
899                 while (ip != bb->last) {
pj
1.21
900                         findTemps(ip);
pj
1.20
901                         ip = DLIST_NEXT(ipqelem);
902                 }
903                 /* Make sure we get the last statement in the bblock */
pj
1.21
904                 findTemps(ip);
pj
1.20
905         }
pantzer
1.59
906     
pj
1.21
907         /* For each variable */
pantzer
1.59
908         for (i = 0i < defsites.sizei++) {
pj
1.21
909                 /* While W not empty */
pj
1.20
910                 while (defsites.arr[i] != NULL) {
pj
1.21
911                         /* Remove some node n from W */
pj
1.20
912                         n = defsites.arr[i];
913                         defsites.arr[i] = n->next;
pj
1.21
914                         /* For each y in n->bb->df */
pj
1.20
915                         for (j = 0j < bbinfo->sizej++) {
pj
1.22
916                                 if (!TESTBIT(n->bb->dfj))
pj
1.20
917                                         continue;
pj
1.22
918                                 
919                                 if (TESTBIT(bbinfo->arr[j]->Aphii))
920                                         continue;
921
pantzer
1.59
922                                 y=bbinfo->arr[j];
923                                 ntype = n->n_type;
pj
1.20
924                                 k = 0;
pj
1.21
925                                 /* Amount of predecessors for y */
pantzer
1.59
926                                 SLIST_FOREACH(cnode, &y->parentscfgelem
pj
1.20
927                                         k++;
pantzer
1.59
928                                 /* Construct phi(...) 
929                                 */
930                             
931                                 phifound=0;
932                             
933                                 SLIST_FOREACH(phi, &y->phiphielem) {
934                                     if (phi->tmpregno==i+defsites.low)
935                                         phifound++;
936                                 }
937                             
938                                 if (phifound==0) {
939                                         if (b2debug)
pantzer
1.61
940                                             printf("Phi in %d (%p) for %d\n",y->dfnum,y,i+defsites.low);
pantzer
1.59
941
942                                         phi = tmpcalloc(sizeof(struct phiinfo));
943                             
944                                         phi->tmpregno=i+defsites.low;
945                                         phi->size=k;
946                                         phi->n_type=