Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20050727202432

Diff

Diff from 1.34 to:

Annotations

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

Annotated File View

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