Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:pantzer:20081122201350

Diff

Diff from 1.59 to:

Annotations

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

Annotated File View

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