Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20060318153043

Diff

Diff from 1.42 to:

Annotations

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

Annotated File View

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