Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:pj:20050205144217

Diff

Diff from 1.8 to:

Annotations

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

Annotated File View

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