Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:pj:20050501110510

Diff

Diff from 1.22 to:

Annotations

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

Annotated File View

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