Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20060620060243

Diff

Diff from 1.44 to:

Annotations

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

Annotated File View

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