Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:pj:20050206163156

Diff

Diff from 1.10 to:

Annotations

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

Annotated File View

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