Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20050403145852

Diff

Diff from 1.19 to:

Annotations

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

Annotated File View

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