Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:pj:20050219154022

Diff

Diff from 1.13 to:

Annotations

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

Annotated File View

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