Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20050806121819

Diff

Diff from 1.37 to:

Annotations

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

Annotated File View

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