Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20090522084102

Diff

Diff from 1.65 to:

Annotations

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

Annotated File View

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