Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20050721150758

Diff

Diff from 1.33 to:

Annotations

Annotate by Age | Author | Mixed | None
ragge (445) pj (400)
/fisheye/browse/pcc/pcc/mip/optim2.c

Annotated File View

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