Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20081116115241

Diff

Diff from 1.56 to:

Annotations

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

Annotated File View

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