Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20050917075840

Diff

Diff from 1.39 to:

Annotations

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

Annotated File View

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