Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:pj:20050223153725

Diff

Diff from 1.15 to:

Annotations

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

Annotated File View

pj
1.15
1 /*      $Id: optim2.c,v 1.15 2005/02/23 15:37:25 pj 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.1
42 extern int saving;
pj
1.8
43 static int dfsnum;
ragge
1.1
44
45 void saveip(struct interpass *ip);
46 void deljumps(void);
47 void deltemp(NODE *p);
48 void optdump(struct interpass *ip);
49
ragge
1.11
50 static struct interpass ipole;
ragge
1.1
51
52 static struct rsv {
53         struct rsv *next;
54         int fpoff;
55         TWORD type;
56         int use;
57 } *rsv;
58
pj
1.8
59 int bblocks_build(struct labelinfo *labinfostruct bblockinfo *bbinfo);
pj
1.4
60 void cfg_build(struct labelinfo *labinfo);
pj
1.8
61 void cfg_dfs(struct basicblock *bbunsigned int parent
62              struct bblockinfo *bbinfo);
63 void dominators(struct bblockinfo *bbinfo);
pj
1.9
64 struct basicblock *
65 ancestorwithlowestsemi(struct basicblock *bblockstruct bblockinfo *bbinfo);
66 void link(struct basicblock *parentstruct basicblock *child);
67 void computeDF(struct basicblock *bblockstruct bblockinfo *bbinfo);
pj
1.15
68 void remunreach(void);
pj
1.4
69
70
ragge
1.11
71 static struct basicblock bblocks;
pj
1.4
72
ragge
1.1
73 static void
74 addcand(TWORD typeint offint avoid)
75 {
76         struct rsv *w = rsv;
77
78         while (w != NULL) {
79                 if (w->type == type && w->fpoff == off) {
80                         if (avoid)
81                                 w->use = -1;
82                         else if (w->use > 0)
83                                 w->use++;
84                         return;
85                 }
86                 w = w->next;
87         }
88         w = tmpalloc(sizeof(*w));
89         w->type = type;
90         w->fpoff = off;
91         w->use = avoid ? -1 : 1;
92         w->next = rsv;
93         rsv = w;
94 }
95
96 /*
97  * walk through the tree and count the number of (possible)
98  * temporary nodes.
99  */
100 static void
101 cntuse(NODE *p)
102 {
103         NODE *l = p->n_left;
104         NODE *r = p->n_right;
105
106         if (p->n_op == UMUL && l->n_op == REG && l->n_rval == FPREG) {
107                 /* found a candidate for register */
108                 addcand(p->n_type0ISVOL(p->n_qual << TSHIFT));
109         } else if (p->n_op == UMUL && l->n_op == PLUS &&
110             l->n_right->n_op == ICON && 
111              (l->n_left->n_op == REG && l->n_left->n_rval == FPREG)) {
112                 /* The same as above */
113                 addcand(p->n_typel->n_right->n_lval,
114                     ISVOL(p->n_qual << TSHIFT));
115         } else if (p->n_op == PLUS && l->n_op == REG && l->n_rval == FPREG &&
116             p->n_right->n_op == ICON) {
117                 /* Address taken of temporary, avoid register */
118                 addcand(DECREF(p->n_type), r->n_lval1);
119         } else {
120                 if (optype(p->n_op) == BITYPE)
121                         cntuse(r);
122                 if (optype(p->n_op) != LTYPE)
123                         cntuse(l);
124         }
125 }
126
127 /*
ragge
1.2
128  * Insert a node into the register stack.
129  */
130 static void
131 insert(struct rsv *wstruct rsv **savedint maxregs)
132 {
133         int ijsize;
134
135         size = szty(w->type);
136
137         /* Find reg move position */
138         for (i = 0i < maxregsi++) {
139                 if (saved[i] == NULL)
140                         continue;
141                 if (saved[i]->use > w->use)
142                         break;
143         }
144         /* Move down other regs */
145         for (j = sizej < ij++)
146                 saved[j-size] = saved[j];
147
148         /* Insert new reg pointer */
149         if (i-size >= 0) {
150                 saved[i-size] = w;
151                 for (j = i-size+1j < ij++)
152                         saved[j] = NULL;
153         }
154 }
155
156 /* Help routine to rconvert() */
157 static int
158 matches(TWORD typeint offstruct rsv **rsvint maxregs)
159 {
160         int i;
161
162         for (i = 0i < maxregsi++)
163                 if (rsv[i] && rsv[i]->type == type && rsv[i]->fpoff == off)
164                         return i;
165         return -1;
166 }
167
168 /* Help routine to rconvert() */
169 static void
170 modify(NODE *pint reg)
171 {
172         tfree(p->n_left);
173         p->n_op = REG;
174         p->n_rval = p->n_rall = reg + MINRVAR;
175         p->n_lval = 0;
176 }
177
178 /*
179  * walk through the tree and convert nodes to registers
180  */
181 static void
182 rconvert(NODE *pstruct rsv **rsvint maxregs)
183 {
184         NODE *l = p->n_left;
185         NODE *r = p->n_right;
186         int i;
187
188         if (p->n_op == UMUL && l->n_op == REG && l->n_rval == FPREG) {
189                 /* found a candidate for register */
190                 if ((i = matches(p->n_type0rsvmaxregs)) >= 0)
191                         modify(pi);
192         } else if (p->n_op == UMUL && l->n_op == PLUS &&
193             l->n_right->n_op == ICON && 
194              (l->n_left->n_op == REG && l->n_left->n_rval == FPREG)) {
195                 /* The same as above */
196                 if ((i = matches(p->n_type,
197                     l->n_right->n_lvalrsvmaxregs)) >= 0)
198                         modify(pi);
199 #if 0
200         } else if (p->n_op == PLUS && l->n_op == REG && l->n_rval == FPREG &&
201             p->n_right->n_op == ICON) {
202                 /* Address taken of temporary, avoid register */
203                 addcand(DECREF(p->n_type), r->n_lval1);
204 #endif
205         } else {
206                 if (optype(p->n_op) == BITYPE)
207                         rconvert(rrsvmaxregs);
208                 if (optype(p->n_op) != LTYPE)
209                         rconvert(lrsvmaxregs);
210         }
211 }
212
213 /*
ragge
1.1
214  * Assign non-temporary registers to variables.
215  * Cannot do it if:
216  * - address is taken of the temporary
217  * - variable is declared "volatile".
218  */
pj
1.4
219 int asgregs(void);
220 int
ragge
1.1
221 asgregs(void)
222 {
223         struct interpass *ip;
ragge
1.2
224         struct rsv *w, **saved;
225         int imaxregs = MAXRVAR - MINRVAR + 1;
ragge
1.1
226
ragge
1.2
227         if (maxregs == 0)
228                 return MAXRVAR/* No register usage */
ragge
1.1
229         rsv = NULL;
230
231         /* Loop over the function to do a usage count */
ragge
1.11
232         DLIST_FOREACH(ip, &ipoleqelem) {
ragge
1.1
233                 if (ip->type != IP_NODE)
234                         continue;
235                 cntuse(ip->ip_node);
236         }
237         /* Check which nodes that shall be converted to registers */
ragge
1.2
238         saved = tmpalloc(sizeof(struct rsv *) * maxregs);
239         memset(saved0sizeof(struct rsv *) * maxregs);
ragge
1.1
240         w = rsv;
241         for (w = rsvww = w->next) {
242                 if (w->use < 0)
ragge
1.2
243                         continue/* Not allowed to be in register */
244
245                 /* XXX check here if type is allowed to be in register */
246
247                 insert(wsavedmaxregs);
ragge
1.1
248         }
249
250         /* Convert found nodes to registers */
ragge
1.11
251         DLIST_FOREACH(ip, &ipoleqelem) {
ragge
1.2
252                 if (ip->type != IP_NODE)
253                         continue;
254                 rconvert(ip->ip_nodesavedmaxregs);
255         }
256         for (i = 0i < maxregsi++)
257                 if (saved[i] != NULL)
258                         break;
259         return MINRVAR+i-1;
ragge
1.1
260 }
261
262 void
263 saveip(struct interpass *ip)
264 {
ragge
1.5
265         struct interpass_prolog *ipp, *epp;
266
pj
1.4
267 #if 0
ragge
1.2
268         int regs;
pj
1.4
269 #endif
270         struct labelinfo labinfo;
pj
1.8
271         struct bblockinfo bbinfo;
ragge
1.1
272
ragge
1.11
273         if (ip->type == IP_PROLOG)
274                 DLIST_INIT(&ipoleqelem);
275
276         DLIST_INSERT_BEFORE(&ipoleipqelem);
ragge
1.1
277
278         if (ip->type != IP_EPILOG)
279                 return;
ragge
1.5
280         epp = (struct interpass_prolog *)ip;
ragge
1.1
281         saving = -1;
282
pj
1.4
283         //              deljumps();     /* Delete redundant jumps and dead code */
284         if (xssaflag) {
ragge
1.11
285                 DLIST_INIT(&bblocksbbelem);
pj
1.8
286                 if (bblocks_build(&labinfo, &bbinfo)) {
pj
1.4
287                         cfg_build(&labinfo);
pj
1.8
288                         dominators(&bbinfo);
ragge
1.11
289                         computeDF(DLIST_NEXT(&bblocksbbelem), &bbinfo);
pj
1.15
290                         remunreach();
pj
1.4
291 #if 0
pj
1.6
292                         if (xssaflag) {
293                                 dfg = dfg_build(cfg);
294                                 ssa = ssa_build(cfgdfg);
295                         }
pj
1.4
296 #endif
297                 }
298  
299         }
300 #if 0
ragge
1.2
301         regs = asgregs();       /* Assign non-temporary registers */
pj
1.4
302 #endif
ragge
1.2
303
304 #ifdef PCC_DEBUG
ragge
1.5
305         if (epp->ipp_regs != MAXRVAR)
ragge
1.2
306                 comperr("register error");
307 #endif
ragge
1.1
308
ragge
1.11
309         ipp = (struct interpass_prolog *)DLIST_NEXT(&ipoleqelem);
ragge
1.5
310         ipp->ipp_autos = epp->ipp_autos;
311         ipp->ipp_regs = epp->ipp_regs// = regs;
ragge
1.1
312
313 #ifdef MYOPTIM
pj
1.6
314         myoptim((struct interpass *)ipp);
ragge
1.1
315 #endif
316
ragge
1.11
317         DLIST_FOREACH(ip, &ipoleqelem) {
ragge
1.1
318                 pass2_compile(ip);
319         }
ragge
1.11
320         DLIST_INIT(&ipoleqelem);
ragge
1.1
321 }
322
323 void
324 deljumps()
325 {
326         struct interpass *ip, *n;
327         int gotone;
328
329 again:  gotone = 0;
330
ragge
1.11
331         DLIST_FOREACH(ip, &ipoleqelem) {
ragge
1.1
332                 if (ip->type == IP_EPILOG)
333                         return;
334                 if (ip->type != IP_NODE)
335                         continue;
ragge
1.11
336                 n = DLIST_NEXT(ipqelem);
ragge
1.1
337                 /* Check for nodes without side effects */
338                 if (ip->ip_node->n_op != GOTO)
339                         continue;
340                 switch (n->type) {
341                 case IP_NODE:
342                         tfree(n->ip_node);
ragge
1.11
343                         DLIST_REMOVE(nqelem);
ragge
1.1
344                         break;
345                 case IP_DEFLAB:
346                         if (ip->ip_node->n_left->n_lval != n->ip_lbl)
347                                 continue;
348                         tfree(ip->ip_node);
349                         *ip = *n;
350                         break;
351                 default:
352                         continue;
353                 }
354                 gotone = 1;
355         }
356         if (gotone)
357                 goto again;
358 }
359
360 void
361 optdump(struct interpass *ip)
362 {
363         static char *nm[] = { "node""prolog""newblk""epilog""locctr",
364                 "deflab""defnam""asm" };
365         printf("type %s\n"nm[ip->type-1]);
366         switch (ip->type) {
367         case IP_NODE:
368                 fwalk(ip->ip_nodee2print0);
369                 break;
370         case IP_DEFLAB:
371                 printf("label " LABFMT "\n"ip->ip_lbl);
372                 break;
373         case IP_ASM:
374                 printf(": %s\n"ip->ip_asm);
375                 break;
376         }
377 }
pj
1.4
378
379 /*
380  * Build the basic blocks, algorithm 9.1, pp 529 in Compilers.
381  *
382  * Also fills the labelinfo struct with information about which bblocks
383  * that contain which label.
384  */
385
386 int
pj
1.8
387 bblocks_build(struct labelinfo *labinfostruct bblockinfo *bbinfo)
pj
1.4
388 {
389         struct interpass *ip;
390         struct basicblock *bb = NULL;
391         int leader = 1;
pj
1.12
392         unsigned int lowhigh = 0;
pj
1.8
393         int count = 0;
pj
1.4
394         int i;
395
pj
1.12
396         low = sizeof(int) == 2 ? 65000 : 1000000000;
pj
1.4
397         /* 
398          * First statement is a leader.
399          * Any statement that is target of a jump is a leader.
400          * Any statement that immediately follows a jump is a leader.
401          */
402
ragge
1.11
403         DLIST_FOREACH(ip, &ipoleqelem) {
pj
1.4
404                 /* Garbage, skip it */
ragge
1.11
405                 if (ip->type == IP_NEWBLK)
pj
1.4
406                         continue;
407
408                 if (leader) {
409                         bb = tmpalloc(sizeof(struct basicblock));
410                         bb->first = bb->last = ip;
ragge
1.11
411                         SLIST_INIT(&bb->children);
412                         SLIST_INIT(&bb->parents);
pj
1.8
413                         bb->dfnum = 0;
414                         bb->dfparent = 0;
415                         bb->semi = 0;
416                         bb->ancestor = 0;
417                         bb->idom = 0;
418                         bb->samedom = 0;
419                         bb->bucket = NULL;
420                         bb->df = NULL;
pj
1.10
421                         bb->dfchildren = NULL;
ragge
1.11
422                         DLIST_INSERT_BEFORE(&bblocksbbbbelem);
pj
1.4
423                         leader = 0;
pj
1.8
424                         count++;
pj
1.4
425                 } 
426                 
427                 /* Prologue and epilogue in their own bblock */
428                 if ((ip->type == IP_PROLOG) || (ip->type == IP_EPILOG)) {
429                         bb->last = ip;
430                         if (ip->type == IP_EPILOG)
ragge
1.5
431                                 high = MAX(ip->ip_lblhigh);
pj
1.4
432                         leader = 1;
433                         continue;
434                 }
435                 
436                 /* Keep track of highest and lowest label number */
437                 if (ip->type == IP_DEFLAB) {
438                         low = MIN(ip->ip_lbllow);
439                         high = MAX(ip->ip_lblhigh);
440                 }
441
442                 /* Make sure each label is in a unique bblock */
443                 if (((ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) && 
444                     bb->first != ip) {
445                         bb = tmpalloc(sizeof(struct basicblock));
446                         bb->first = bb->last = ip;
ragge
1.11
447                         SLIST_INIT(&bb->children);
448                         SLIST_INIT(&bb->parents);
pj
1.8
449                         bb->dfnum = 0;
450                         bb->dfparent = 0;
451                         bb->semi = 0;
452                         bb->ancestor = 0;
453                         bb->idom = 0;
454                         bb->samedom = 0;
455                         bb->bucket = NULL;
456                         bb->df = NULL;
pj
1.10
457                         bb->dfchildren = NULL;
ragge
1.11
458                         DLIST_INSERT_BEFORE(&bblocksbbbbelem);
pj
1.8
459                         count++;
pj
1.4
460                         continue;
461                 }
462
463                 if (ip->type == IP_ASM)
464                         return 0;
465
466                 if (ip->type == IP_NODE) {
467                         switch(ip->ip_node->n_op) {
468                         case CBRANCH:
469                         case GOTO:
470                         case RETURN:
471                                 /* Jumps, last in bblock. */
472                                 leader = 1;
473                                 break;
474
475                         case NAME:
476                         case ICON:
477                         case FCON:
478                         case REG:
479                         case OREG:
480                         case MOVE:
481                         case PLUS:
482                         case MINUS:
483                         case DIV:
484                         case MOD:
485                         case MUL:
486                         case AND:
487                         case OR:
488                         case ER:
489                         case LS:
490                         case COMPL:
491                         case INCR:
492                         case DECR:
493                         case UMUL:
494                         case UMINUS:
495                         case EQ:
496                         case NE:
497                         case LE:
498                         case GE:
499                         case GT:
500                         case ULE:
501                         case ULT:
502                         case UGE:
503                         case UGT:
504                         case ASSIGN:
505                         case FORCE:
506                         case FUNARG:
pj
1.7
507                         case CALL:
508                         case UCALL:
509                         case FORTCALL:
510                         case UFORTCALL:
511                         case STCALL:
512                         case USTCALL:
pj
1.4
513                                 /* Not jumps, continue with bblock. */
514                                 break;
515
516                         default:
517                                 comperr("optim2:bblocks_build() %d",ip->ip_node->n_op ); 
518                                 break;
519                         }
520                 }
521
522                 bb->last = ip;
523         }
524 #ifdef PCC_DEBUG
pj
1.8
525         printf("Basic blocks in func: %d\n"count);
pj
1.10
526         printf("Label range in func: %d\n"high - low + 1);
pj
1.4
527 #endif
528
529         labinfo->low = low;
530         labinfo->size = high - low + 1;
531         labinfo->arr = tmpalloc(labinfo->size * sizeof(struct basicblock *));
pj
1.8
532         for (i = 0i <= labinfo->sizei++) {
pj
1.4
533                 labinfo->arr[i] = NULL;
534         }
pj
1.8
535         
536         bbinfo->size = count + 1;
537         bbinfo->arr = tmpalloc(bbinfo->size * sizeof(struct basicblock *));
538         for (i = 0i <= bbinfo->sizei++) {
539                 bbinfo->arr[i] = NULL;
540         }
pj
1.4
541
542         /* Build the label table */
ragge
1.11
543         DLIST_FOREACH(bb, &bblocksbbelem) {
pj
1.4
544                 if (bb->first->type == IP_DEFLAB) {
545                         labinfo->arr[bb->first->ip_lbl - low] = bb;
546                 }
547                 if (bb->first->type == IP_EPILOG) {
ragge
1.5
548                         labinfo->arr[bb->first->ip_lbl - low] = bb;
pj
1.4
549                 }
550         }
551
552         return 1;
553 }
554
555 /*
556  * Build the control flow graph.
557  */
558
559 void
560 cfg_build(struct labelinfo *labinfo)
561 {
562         /* Child and parent nodes */
563         struct cfgnode *cnode
564         struct cfgnode *pnode;
565         struct basicblock *bb;
566         
ragge
1.11
567         DLIST_FOREACH(bb, &bblocksbbelem) {
pj
1.4
568
569                 if (bb->first->type == IP_EPILOG) {
570                         break;
571                 }
572
573                 cnode = tmpalloc(sizeof(struct cfgnode));
574                 pnode = tmpalloc(sizeof(struct cfgnode));
575                 pnode->bblock = bb;
576
577                 if ((bb->last->type == IP_NODE) && 
578                     (bb->last->ip_node->n_op == GOTO)) {
579                         if (bb->last->ip_node->n_left->n_lval - labinfo->low > 
580                             labinfo->size) {
581                                 comperr("Label out of range: %d, base %d"
582                                         bb->last->ip_node->n_left->n_lval
583                                         labinfo->low);
584                         }
585                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_left->n_lval - labinfo->low];
ragge
1.11
586                         SLIST_INSERT_LAST(&cnode->bblock->parentspnodecfgelem);
587                         SLIST_INSERT_LAST(&bb->childrencnodecfgelem);
pj
1.4
588                         continue;
589                 }
590                 if ((bb->last->type == IP_NODE) && 
591                     (bb->last->ip_node->n_op == CBRANCH)) {
592                         if (bb->last->ip_node->n_right->n_lval - labinfo->low > 
593                             labinfo->size
594                                 comperr("Label out of range: %d"
595                                         bb->last->ip_node->n_left->n_lval);
596                         
597                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_right->n_lval - labinfo->low];
ragge
1.11
598                         SLIST_INSERT_LAST(&cnode->bblock->parentspnodecfgelem);
599                         SLIST_INSERT_LAST(&bb->childrencnodecfgelem);
pj
1.4
600                         cnode = tmpalloc(sizeof(struct cfgnode));
601                         pnode = tmpalloc(sizeof(struct cfgnode));
602                         pnode->bblock = bb;
603                 }
604
ragge
1.11
605                 cnode->bblock = DLIST_NEXT(bbbbelem);
606                 SLIST_INSERT_LAST(&cnode->bblock->parentspnodecfgelem);
607                 SLIST_INSERT_LAST(&bb->childrencnodecfgelem);
pj
1.4
608         }
609 }
pj
1.6
610
pj
1.8
611 void
612 cfg_dfs(struct basicblock *bbunsigned int parentstruct bblockinfo *bbinfo)
613 {
614         struct cfgnode *cnode;
615         
616         if (bb->dfnum != 0)
617                 return;
618
619         bb->dfnum = ++dfsnum;
620         bb->dfparent = parent;
621         bbinfo->arr[bb->dfnum] = bb;
ragge
1.11
622         SLIST_FOREACH(cnode, &bb->childrencfgelem) {
pj
1.8
623                 cfg_dfs(cnode->bblockbb->dfnumbbinfo);
624         }
pj
1.13
625         /* Don't bring in unreachable nodes in the future */
pj
1.14
626         bbinfo->size = dfsnum + 1
pj
1.8
627 }
628
ragge
1.11
629 static bittype *
630 setalloc(int nelem)
631 {
632         bittype *b;
633         int sz = (nelem+NUMBITS-1)/NUMBITS;
634
635         b = tmpalloc(sz * sizeof(bittype));
636         memset(b0sz * sizeof(bittype));
637         return b;
638 }
639
pj
1.8
640 /*
641  * Algorithm 19.9, pp 414 from Appel.
642  */
643
644 void
645 dominators(struct bblockinfo *bbinfo)
646 {
647         struct cfgnode *cnode;
648         struct basicblock *bb, *y, *v;
649         struct basicblock *s, *sprime, *p;
pj
1.10
650         int hi;
pj
1.8
651
ragge
1.11
652         DLIST_FOREACH(bb, &bblocksbbelem) {
653                 bb->bucket = setalloc(bbinfo->size);
654                 bb->df = setalloc(bbinfo->size);
655                 bb->dfchildren = setalloc(bbinfo->size);
pj
1.8
656         }
657
658         dfsnum = 0;
ragge
1.11
659         cfg_dfs(DLIST_NEXT(&bblocksbbelem), 0bbinfo);
pj
1.8
660
pj
1.10
661         for(h = bbinfo->size - 1h > 1h--) {
662                 bb = bbinfo->arr[h];
pj
1.8
663                 p = s = bbinfo->arr[bb->dfparent];
ragge
1.11
664                 SLIST_FOREACH(cnode, &bb->parentscfgelem) {
pj
1.8
665                         if (cnode->bblock->dfnum <= bb->dfnum
666                                 sprime = cnode->bblock;
pj
1.10
667                         else 
668                                 sprime = bbinfo->arr[ancestorwithlowestsemi
669                                               (cnode->bblockbbinfo)->semi];
pj
1.8
670                         if (sprime->dfnum < s->dfnum)
671                                 s = sprime;
672                 }
673                 bb->semi = s->dfnum;
pj
1.10
674                 BITSET(s->bucketbb->dfnum);
pj
1.8
675                 link(pbb);
676                 for (i = 1i < bbinfo->sizei++) {
pj
1.10
677                         if(TESTBIT(p->bucketi)) {
pj
1.8
678                                 v = bbinfo->arr[i];
pj
1.10
679                                 y = ancestorwithlowestsemi(vbbinfo);
680                                 if (y->semi == v->semi
pj
1.8
681                                         v->idom = p->dfnum;
682                                 else
683                                         v->samedom = y->dfnum;
684                         }
685                 }
686                 memset(p->bucket0, (bbinfo->size + 7)/8);
687         }
pj
1.10
688 #if 0
689         printf("Num\tSemi\tAncest\tidom\n");
pj
1.8
690         CIRCLEQ_FOREACH(bb, &bblocksbbelem) {
pj
1.10
691                 printf("%d\t%d\t%d\t%d\n"bb->dfnumbb->semibb->ancestorbb->idom);
692         }
693 #endif
694         for(h = 2h < bbinfo->sizeh++) {
695                 bb = bbinfo->arr[h];
696                 if (bb->samedom != 0) {
pj
1.8
697                         bb->idom = bbinfo->arr[bb->samedom]->idom;
pj
1.10
698                 }
699         }
ragge
1.11
700         DLIST_FOREACH(bb, &bblocksbbelem) {
pj
1.10
701                 if (bb->idom != 0 && bb->idom != bb->dfnum) {
702 #if 0
703
704                         printf("Setting child %d of %d\n"bb->dfnumbbinfo->arr[bb->idom]->dfnum);
705 #endif
706
707                         BITSET(bbinfo->arr[bb->idom]->dfchildrenbb->dfnum);
708                 }
pj
1.8
709         }
710 }
711
712
713 struct basicblock *
714 ancestorwithlowestsemi(struct basicblock *bblockstruct bblockinfo *bbinfo)
715 {
716         struct basicblock *u = bblock;
717         struct basicblock *v = bblock;
718
719         while (v->ancestor != 0) {
720                 if (bbinfo->arr[v->semi]->dfnum < 
pj
1.10
721                     bbinfo->arr[u->semi]->dfnum
pj
1.8
722                         u = v;
723                 v = bbinfo->arr[v->ancestor];
724         }
725         return u;
726 }
727
728 void
729 link(struct basicblock *parentstruct basicblock *child)
730 {
731         child->ancestor = parent->dfnum;
732 }
733
734 void
735 computeDF(struct basicblock *bblockstruct bblockinfo *bbinfo)
736 {
737         struct cfgnode *cnode;
pj
1.10
738         int hi;
pj
1.8
739         
ragge
1.11
740         SLIST_FOREACH(cnode, &bblock->childrencfgelem) {
pj
1.8
741                 if (cnode->bblock->idom != bblock->dfnum)
742                         BITSET(bblock->dfcnode->bblock->dfnum);
743         }
pj
1.10
744         for (h = 1h < bbinfo->sizeh++) {
745                 if (!TESTBIT(bblock->dfchildrenh))
746                         continue;
747                 computeDF(bbinfo->arr[h], bbinfo);
pj
1.8
748                 for (i = 1i < bbinfo->sizei++) {
pj
1.10
749                         if (TESTBIT(bbinfo->arr[h]->dfi) && 
750                             (bbinfo->arr[h] == bblock ||
751                              (bblock->idom != bbinfo->arr[h]->dfnum))) 
pj
1.8
752                             BITSET(bblock->dfi);
753                 }
754         }
755 }
pj
1.15
756
757 /*
758  * Remove unreachable nodes in the CFG.
759  */ 
760
761 void
762 remunreach(void)
763 {
764         struct basicblock *bb, *nbb;
765         struct interpass *next, *ctree;
766
767         bb = DLIST_NEXT(&bblocksbbelem);
768         while (bb != &bblocks) {
769                 nbb = DLIST_NEXT(bbbbelem);
770
771                 /* Code with dfnum 0 is unreachable */
772                 if (bb->dfnum != 0) {
773                         bb = nbb;
774                         continue;
775                 }
776
777                 /* Need the epilogue node for other parts of the
778                    compiler, set its label to 0 and backend will
779                    handle it. */ 
780                 if (bb->first->type == IP_EPILOG) {
781                         bb->first->ip_lbl = 0;
782                         bb = nbb;
783                         continue;
784                 }
785
786                 next = bb->first;
787                 do {
788                         ctree = next;
789                         next = DLIST_NEXT(ctreeqelem);
790                         
791                         if (ctree->type == IP_NODE)
792                                 tfree(ctree->_un._p);
793                         DLIST_REMOVE(ctreeqelem);
794                 } while (ctree != bb->last);
795                         
796                 DLIST_REMOVE(bbbbelem);
797                 bb = nbb;
798         }
799 }
FishEye: Open Source License registered to PCC.
Your maintenance has expired. You can renew your license at http://www.atlassian.com/fisheye/renew
Atlassian FishEye, CVS analysis. (Version:1.6.3 Build:build-336 2008-11-04) - Administration - Page generated 2014-09-16 02:55 +0200