Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:pj:20050430083010

Diff

Diff from 1.20 to:

Annotations

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

Annotated File View

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