Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:stefan:20080111211442

Diff

Diff from 1.51 to:

Annotations

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

Annotated File View

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