Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20050628184815

Diff

Diff from 1.27 to:

Annotations

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

Annotated File View

ragge
1.27
1 /*      $Id: optim2.c,v 1.27 2005/06/28 18:48:15 ragge 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;
ragge
1.23
270         static int inftn;
ragge
1.5
271
pj
1.4
272 #if 0
ragge
1.2
273         int regs;
pj
1.4
274 #endif
275         struct labelinfo labinfo;
pj
1.8
276         struct bblockinfo bbinfo;
ragge
1.1
277
ragge
1.23
278         if (ip->type == IP_PROLOG) {
ragge
1.11
279                 DLIST_INIT(&ipoleqelem);
ragge
1.23
280                 inftn = 1;
281         } else if (inftn == 0)
282                 comperr("saveip");
ragge
1.11
283
284         DLIST_INSERT_BEFORE(&ipoleipqelem);
ragge
1.1
285
286         if (ip->type != IP_EPILOG)
287                 return;
ragge
1.23
288         inftn = 0;
ragge
1.5
289         epp = (struct interpass_prolog *)ip;
ragge
1.1
290         saving = -1;
291
ragge
1.26
292 ipp = (struct interpass_prolog *)DLIST_NEXT(&ipoleqelem);
293 printf("inlab %d utlab %d\n"ipp->ip_lblnumepp->ip_lblnum);
294         if (xdeljumps)
295                 deljumps();     /* Delete redundant jumps and dead code */
pj
1.4
296         if (xssaflag) {
ragge
1.11
297                 DLIST_INIT(&bblocksbbelem);
pj
1.8
298                 if (bblocks_build(&labinfo, &bbinfo)) {
pj
1.4
299                         cfg_build(&labinfo);
pj
1.8
300                         dominators(&bbinfo);
ragge
1.11
301                         computeDF(DLIST_NEXT(&bblocksbbelem), &bbinfo);
pj
1.15
302                         remunreach();
pj
1.4
303 #if 0
pj
1.6
304                         if (xssaflag) {
305                                 dfg = dfg_build(cfg);
306                                 ssa = ssa_build(cfgdfg);
307                         }
pj
1.4
308 #endif
309                 }
310  
311         }
312 #if 0
ragge
1.2
313         regs = asgregs();       /* Assign non-temporary registers */
pj
1.4
314 #endif
ragge
1.2
315
316 #ifdef PCC_DEBUG
ragge
1.5
317         if (epp->ipp_regs != MAXRVAR)
ragge
1.2
318                 comperr("register error");
319 #endif
ragge
1.1
320
ragge
1.11
321         ipp = (struct interpass_prolog *)DLIST_NEXT(&ipoleqelem);
ragge
1.5
322         ipp->ipp_autos = epp->ipp_autos;
323         ipp->ipp_regs = epp->ipp_regs// = regs;
ragge
1.1
324
325 #ifdef MYOPTIM
pj
1.6
326         myoptim((struct interpass *)ipp);
ragge
1.1
327 #endif
328
ragge
1.19
329 if (xnewreg == 0) {
330         int tmpautooff;
331         NODE *p;
332
333         p2autooff = p2maxautooff = AUTOINIT;
334         /* Must verify stack usage first */
335         DLIST_FOREACH(ip, &ipoleqelem) {
336                 if (ip->type == IP_STKOFF) {
337                         p2autooff = ip->ip_off;
338                         if (p2autooff > p2maxautooff)
339                                 p2maxautooff = p2autooff;
340                 }
341         }
342         p2autooff = p2maxautooff/* don't have live range analysis yet */
343
344         DLIST_FOREACH(ip, &ipoleqelem) {
ragge
1.23
345                 if (ip->type == IPSTK) {
ragge
1.19
346                         struct interpass *ip3;
347                         p2autooff = ip->ip_off;
348                         ip3 = ip;
349                         ip = DLIST_NEXT(ipqelem);
350                         DLIST_REMOVE(ip3qelem);
351                 }
352                         
353                 if (ip->type != IP_NODE)
354                         continue;
355
356                 p = ip->ip_node;
357                 walkf(pdeltemp);
358
359                 tmpautooff = p2autooff;
360
361                 geninsn(pFOREFF);
362                 if (sucomp(p) < 0) {
363                         /* Create STKOFF entry */
364                         struct interpass *ip3;
365                         DLIST_INSERT_BEFORE(ipstoresaveqelem);
366                         ip3 = ipnode(NULL);
ragge
1.23
367                         ip3->type = IPSTK;
ragge
1.19
368                         ip3->ip_off = tmpautooff;
369                         DLIST_INSERT_AFTER(ipip3qelem);
370                         ip = DLIST_PREV(storesaveqelem);
371                         continue;
372                 }
373
374                 p2autooff = tmpautooff;
375
376                 genregs(p);
377                 mygenregs(p);
378         }
379
380 else {
381         /*
382          * Loop over instruction assignment until the register assignment
383          * code is satisfied.
384          */
ragge
1.25
385 #if 0
386         extern int tempmintempmax;
387
388         tempmin = ip->ip_tmpnum;
389         tempmin = ie->ip_tmpnum;
390 #endif
ragge
1.19
391         do {
392                 /* do instruction assignment */
393                 DLIST_FOREACH(ip, &ipoleqelem) {
394                         if (ip->type != IP_NODE)
395                                 continue;
396                         geninsn(ip->ip_nodeFOREFF);
397                         nsucomp(ip->ip_node);
398                 }
399         } while (ngenregs(DLIST_NEXT(&ipoleqelem),
400             DLIST_PREV(&ipoleqelem)));
401 }
402
403         DLIST_FOREACH(ip, &ipoleqelem) {
404                 emit(ip);
405         }
ragge
1.11
406         DLIST_INIT(&ipoleqelem);
ragge
1.1
407 }
408
ragge
1.26
409 /*
410  * Delete unused labels, excess of labels, gotos to gotos.
411  * This routine can be made much more efficient.
412  */
ragge
1.1
413 void
414 deljumps()
415 {
ragge
1.26
416         struct interpass_prolog *ipp, *epp;
ragge
1.27
417         struct interpass *ip, *n;
ragge
1.26
418         int gotone,lowhigh;
ragge
1.27
419         int *lblarysz;
ragge
1.26
420
421         ipp = (struct interpass_prolog *)DLIST_NEXT(&ipoleqelem);
422         epp = (struct interpass_prolog *)DLIST_PREV(&ipoleqelem);
423
424         low = ipp->ip_lblnum;
425         high = epp->ip_lblnum;
426
427 #ifdef notyet
428         mark = tmpmark(); /* temporary used memory */
429 #endif
430 #define FOUND   1
431 #define REFD    2
432         sz = (high-low) * sizeof(int);
433         lblary = tmpalloc(sz);
434         memset(lblary0sz);
435
436 again:  gotone = 0;
437
438 printip(&ipole);
439
ragge
1.27
440         /* delete all labels with a following label */
441         DLIST_FOREACH(ip, &ipoleqelem) {
442                 if (ip->type == IP_DEFLAB) {
443                         n = DLIST_NEXT(ipqelem);
444                         while (n->type == IP_DEFLAB) {
445                                 lblary[n->ip_lbl-low] = -ip->ip_lbl;
446                                 DLIST_REMOVE(nqelem);
447                                 n = DLIST_NEXT(ipqelem);
448                         }
449                         if (n->type == IP_STKOFF) {
450                                 n = DLIST_NEXT(nqelem);
451                                 while (n->type == IP_DEFLAB) {
452                                         lblary[n->ip_lbl-low] = -ip->ip_lbl;
453                                         DLIST_REMOVE(nqelem);
454                                         n = DLIST_NEXT(nqelem);
455                                 }
456                         }
457                 }
458         }
459
460         if (gotone)
461                 goto again;
462
463 printf("2\n");
464 printip(&ipole);
465
466 #if 0
467  && ip->type != IP_STKOFF)
468                         continue;
469
470                 n = DLIST_NEXT(ipqelem);
471                 while (n->type == IP_DEFLAB || n->type == IP_STKOFF) {
472                         
473
474
475
476
477
478
ragge
1.26
479         DLIST_FOREACH(ip, &ipoleqelem) {
480                 if (ip->type == IP_DEFLAB) {
481                         lblary[ip->ip_lbl-low] |= FOUND;
482 printf("IP_DEFLAB: %d\n"ip->ip_lbl);
483                         ip2 = DLIST_NEXT(ipqelem);
484 printf("ip2 %d\n"ip2->type);
485                         while (ip2->type == IP_DEFLAB ||
486                             ip2->type == IP_STKOFF) {
487                                 if (ip2->type == IP_DEFLAB) {
488                                         lblary[ip2->ip_lbl-low] = -ip->ip_lbl;
489 printf("coal %d\n"ip2->ip_lbl);
490                                         DLIST_REMOVE(ip2qelem);
491                                         gotone = 1;
492                                 } else
493                                         ip = ip2;
494                                 ip2 = DLIST_NEXT(ipqelem);
495                         }
496                         ip = DLIST_PREV(ipqelem);
497                         continue;
498                 }
499                 n = DLIST_NEXT(ipqelem);
500                 if (n->type != IP_NODE)
501                         continue;
502                 o = n->ip_node->n_op;
503                 if (o == GOTO)
504                         i = n->ip_node->n_left->n_lval;
505                 else if (o == CBRANCH)
506                         i = n->ip_node->n_right->n_lval;
507                 else
508                         continue;
509                 if (lblary[i-low] < 0) {
510                         if (o == GOTO)
511                                 n->ip_node->n_left->n_lval = -lblary[i-low];
512                         else
513                                 n->ip_node->n_right->n_lval = -lblary[i-low];
514                         gotone = 1;
515                 }
516                 ip2 = DLIST_NEXT(nqelem);
517                 if (ip2->type == IP_DEFLAB && ip2->ip_lbl == i) {
518                         tfree(n->ip_node);
519                         DLIST_REMOVE(nqelem);
520                         gotone = 1;
521                 }
522         }
523         if (gotone)
524                 goto again;
525
ragge
1.27
526 #endif
527
ragge
1.26
528 #ifdef notyet
529         tmpfree(mark);
530 #endif
531
532 #if 0
533         DLIST_FOREACH(ip, &ipoleqelem) {
534                 if (ip->type == IP_DEFLAB) {
535                         lblary[ip->ip_lbl-low] |= FOUND;
536                         ip2 = DLIST_NEXT(ipqelem);
537                         while (ip2->type == IP_DEFLAB) {
538                                 lblary[ip2->ip_lbl-low] = -ip->ip_lbl;
539                                 DLIST_REMOVE(ip2qelem);
540                                 ip2 = DLIST_NEXT(ipqelem);
541                         }
542                 }
543                 if (ip->type != IP_NODE)
544                         continue;
545                 if (o == GOTO)
546                         i = ip->ip_node->n_left->n_lval;
547                 else if (o == CBRANCH)
548                         i = ip->ip_node->n_right->n_lval;
549                 else
550                         continue;
551                 if (lblary[i-low] < 0) {
552                         /* coalesced */
553                         
554                 lblary[i-low] |= REFD;
555         }
556
557
558
ragge
1.1
559
560 again:  gotone = 0;
561
ragge
1.26
562
563
564
565
566
567
ragge
1.11
568         DLIST_FOREACH(ip, &ipoleqelem) {
ragge
1.1
569                 if (ip->type == IP_EPILOG)
570                         return;
571                 if (ip->type != IP_NODE)
572                         continue;
ragge
1.11
573                 n = DLIST_NEXT(ipqelem);
ragge
1.1
574                 /* Check for nodes without side effects */
575                 if (ip->ip_node->n_op != GOTO)
576                         continue;
577                 switch (n->type) {
578                 case IP_NODE:
579                         tfree(n->ip_node);
ragge
1.11
580                         DLIST_REMOVE(nqelem);
ragge
1.1
581                         break;
582                 case IP_DEFLAB:
583                         if (ip->ip_node->n_left->n_lval != n->ip_lbl)
584                                 continue;
585                         tfree(ip->ip_node);
586                         *ip = *n;
587                         break;
588                 default:
589                         continue;
590                 }
591                 gotone = 1;
592         }
593         if (gotone)
594                 goto again;
ragge
1.26
595 #endif
ragge
1.1
596 }
597
598 void
599 optdump(struct interpass *ip)
600 {
601         static char *nm[] = { "node""prolog""newblk""epilog""locctr",
602                 "deflab""defnam""asm" };
603         printf("type %s\n"nm[ip->type-1]);
604         switch (ip->type) {
605         case IP_NODE:
606                 fwalk(ip->ip_nodee2print0);
607                 break;
608         case IP_DEFLAB:
609                 printf("label " LABFMT "\n"ip->ip_lbl);
610                 break;
611         case IP_ASM:
612                 printf(": %s\n"ip->ip_asm);
613                 break;
614         }
615 }
pj
1.4
616
617 /*
618  * Build the basic blocks, algorithm 9.1, pp 529 in Compilers.
619  *
620  * Also fills the labelinfo struct with information about which bblocks
621  * that contain which label.
622  */
623
624 int
pj
1.8
625 bblocks_build(struct labelinfo *labinfostruct bblockinfo *bbinfo)
pj
1.4
626 {
627         struct interpass *ip;
628         struct basicblock *bb = NULL;
629         int leader = 1;
pj
1.12
630         unsigned int lowhigh = 0;
pj
1.8
631         int count = 0;
pj
1.4
632         int i;
633
pj
1.12
634         low = sizeof(int) == 2 ? 65000 : 1000000000;
pj
1.4
635         /* 
636          * First statement is a leader.
637          * Any statement that is target of a jump is a leader.
638          * Any statement that immediately follows a jump is a leader.
639          */
640
ragge
1.11
641         DLIST_FOREACH(ip, &ipoleqelem) {
pj
1.4
642                 /* Garbage, skip it */
643                 if (leader) {
644                         bb = tmpalloc(sizeof(struct basicblock));
645                         bb->first = bb->last = ip;
ragge
1.11
646                         SLIST_INIT(&bb->children);
647                         SLIST_INIT(&bb->parents);
pj
1.8
648                         bb->dfnum = 0;
649                         bb->dfparent = 0;
650                         bb->semi = 0;
651                         bb->ancestor = 0;
652                         bb->idom = 0;
653                         bb->samedom = 0;
654                         bb->bucket = NULL;
655                         bb->df = NULL;
pj
1.10
656                         bb->dfchildren = NULL;
pj
1.22
657                         bb->Aorig = NULL;
658                         bb->Aphi = NULL;
ragge
1.11
659                         DLIST_INSERT_BEFORE(&bblocksbbbbelem);
pj
1.4
660                         leader = 0;
pj
1.8
661                         count++;
pj
1.4
662                 } 
663                 
664                 /* Prologue and epilogue in their own bblock */
665                 if ((ip->type == IP_PROLOG) || (ip->type == IP_EPILOG)) {
666                         bb->last = ip;
667                         if (ip->type == IP_EPILOG)
ragge
1.5
668                                 high = MAX(ip->ip_lblhigh);
pj
1.4
669                         leader = 1;
670                         continue;
671                 }
672                 
673                 /* Keep track of highest and lowest label number */
674                 if (ip->type == IP_DEFLAB) {
675                         low = MIN(ip->ip_lbllow);
676                         high = MAX(ip->ip_lblhigh);
677                 }
678
679                 /* Make sure each label is in a unique bblock */
680                 if (((ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) && 
681                     bb->first != ip) {
682                         bb = tmpalloc(sizeof(struct basicblock));
683                         bb->first = bb->last = ip;
ragge
1.11
684                         SLIST_INIT(&bb->children);
685                         SLIST_INIT(&bb->parents);
pj
1.8
686                         bb->dfnum = 0;
687                         bb->dfparent = 0;
688                         bb->semi = 0;
689                         bb->ancestor = 0;
690                         bb->idom = 0;
691                         bb->samedom = 0;
692                         bb->bucket = NULL;
693                         bb->df = NULL;
pj
1.10
694                         bb->dfchildren = NULL;
pj
1.22
695                         bb->Aorig = NULL;
696                         bb->Aphi = NULL;
ragge
1.11
697                         DLIST_INSERT_BEFORE(&bblocksbbbbelem);
pj
1.8
698                         count++;
pj
1.4
699                         continue;
700                 }
701
702                 if (ip->type == IP_ASM)
703                         return 0;
704
705                 if (ip->type == IP_NODE) {
706                         switch(ip->ip_node->n_op) {
707                         case CBRANCH:
708                         case GOTO:
709                         case RETURN:
710                                 /* Jumps, last in bblock. */
711                                 leader = 1;
712                                 break;
713
714                         case NAME:
715                         case ICON:
716                         case FCON:
717                         case REG:
718                         case OREG:
719                         case MOVE:
720                         case PLUS:
721                         case MINUS:
722                         case DIV:
723                         case MOD:
724                         case MUL:
725                         case AND:
726                         case OR:
727                         case ER:
728                         case LS:
729                         case COMPL:
730                         case INCR:
731                         case DECR:
732                         case UMUL:
733                         case UMINUS:
734                         case EQ:
735                         case NE:
736                         case LE:
737                         case GE:
738                         case GT:
739                         case ULE:
740                         case ULT:
741                         case UGE:
742                         case UGT:
743                         case ASSIGN:
744                         case FORCE:
745                         case FUNARG:
pj
1.7
746                         case CALL:
747                         case UCALL:
748                         case FORTCALL:
749                         case UFORTCALL:
750                         case STCALL:
751                         case USTCALL:
pj
1.4
752                                 /* Not jumps, continue with bblock. */
753                                 break;
754
755                         default:
756                                 comperr("optim2:bblocks_build() %d",ip->ip_node->n_op ); 
757                                 break;
758                         }
759                 }
760
761                 bb->last = ip;
762         }
pj
1.20
763 #if 0
pj
1.8
764         printf("Basic blocks in func: %d\n"count);
pj
1.10
765         printf("Label range in func: %d\n"high - low + 1);
pj
1.4
766 #endif
767
768         labinfo->low = low;
769         labinfo->size = high - low + 1;
770         labinfo->arr = tmpalloc(labinfo->size * sizeof(struct basicblock *));
pj
1.8
771         for (i = 0i <= labinfo->sizei++) {
pj
1.4
772                 labinfo->arr[i] = NULL;
773         }
pj
1.8
774         
775         bbinfo->size = count + 1;
776         bbinfo->arr = tmpalloc(bbinfo->size * sizeof(struct basicblock *));
777         for (i = 0i <= bbinfo->sizei++) {
778                 bbinfo->arr[i] = NULL;
779         }
pj
1.4
780
ragge
1.11
781         DLIST_FOREACH(bb, &bblocksbbelem) {
pj
1.20
782                 /* Build the label table */
pj
1.4
783                 if (bb->first->type == IP_DEFLAB) {
784                         labinfo->arr[bb->first->ip_lbl - low] = bb;
785                 }
786                 if (bb->first->type == IP_EPILOG) {
ragge
1.5
787                         labinfo->arr[bb->first->ip_lbl - low] = bb;
pj
1.4
788                 }
789         }
790
791         return 1;
792 }
793
794 /*
795  * Build the control flow graph.
796  */
797
798 void
799 cfg_build(struct labelinfo *labinfo)
800 {
801         /* Child and parent nodes */
802         struct cfgnode *cnode
803         struct cfgnode *pnode;
804         struct basicblock *bb;
805         
ragge
1.11
806         DLIST_FOREACH(bb, &bblocksbbelem) {
pj
1.4
807
808                 if (bb->first->type == IP_EPILOG) {
809                         break;
810                 }
811
812                 cnode = tmpalloc(sizeof(struct cfgnode));
813                 pnode = tmpalloc(sizeof(struct cfgnode));
814                 pnode->bblock = bb;
815
816                 if ((bb->last->type == IP_NODE) && 
817                     (bb->last->ip_node->n_op == GOTO)) {
818                         if (bb->last->ip_node->n_left->n_lval - labinfo->low > 
819                             labinfo->size) {
820                                 comperr("Label out of range: %d, base %d"
821                                         bb->last->ip_node->n_left->n_lval
822                                         labinfo->low);
823                         }
824                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_left->n_lval - labinfo->low];
ragge
1.11
825                         SLIST_INSERT_LAST(&cnode->bblock->parentspnodecfgelem);
826                         SLIST_INSERT_LAST(&bb->childrencnodecfgelem);
pj
1.4
827                         continue;
828                 }
829                 if ((bb->last->type == IP_NODE) && 
830                     (bb->last->ip_node->n_op == CBRANCH)) {
831                         if (bb->last->ip_node->n_right->n_lval - labinfo->low > 
832                             labinfo->size
833                                 comperr("Label out of range: %d"
834                                         bb->last->ip_node->n_left->n_lval);
835                         
836                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_right->n_lval - labinfo->low];
ragge
1.11
837                         SLIST_INSERT_LAST(&cnode->bblock->parentspnodecfgelem);
838                         SLIST_INSERT_LAST(&bb->childrencnodecfgelem);
pj
1.4
839                         cnode = tmpalloc(sizeof(struct cfgnode));
840                         pnode = tmpalloc(sizeof(struct cfgnode));
841                         pnode->bblock = bb;
842                 }
843
ragge
1.11
844                 cnode->bblock = DLIST_NEXT(bbbbelem);
845                 SLIST_INSERT_LAST(&cnode->bblock->parentspnodecfgelem);
846                 SLIST_INSERT_LAST(&bb->childrencnodecfgelem);
pj
1.4
847         }
848 }
pj
1.6
849
pj
1.8
850 void
851 cfg_dfs(struct basicblock *bbunsigned int parentstruct bblockinfo *bbinfo)
852 {
853         struct cfgnode *cnode;
854         
855         if (bb->dfnum != 0)
856                 return;
857
858         bb->dfnum = ++dfsnum;
859         bb->dfparent = parent;
860         bbinfo->arr[bb->dfnum] = bb;
ragge
1.11
861         SLIST_FOREACH(cnode, &bb->childrencfgelem) {
pj
1.8
862                 cfg_dfs(cnode->bblockbb->dfnumbbinfo);
863         }
pj
1.13
864         /* Don't bring in unreachable nodes in the future */
pj
1.20
865         bbinfo->size = dfsnum + 1;
pj
1.8
866 }
867
ragge
1.11
868 static bittype *
869 setalloc(int nelem)
870 {
871         bittype *b;
872         int sz = (nelem+NUMBITS-1)/NUMBITS;
873
874         b = tmpalloc(sz * sizeof(bittype));
875         memset(b0sz * sizeof(bittype));
876         return b;
877 }
878
pj
1.8
879 /*
880  * Algorithm 19.9, pp 414 from Appel.
881  */
882
883 void
884 dominators(struct bblockinfo *bbinfo)
885 {
886         struct cfgnode *cnode;
887         struct basicblock *bb, *y, *v;
888         struct basicblock *s, *sprime, *p;
pj
1.10
889         int hi;
pj
1.8
890
ragge
1.11
891         DLIST_FOREACH(bb, &bblocksbbelem) {
892                 bb->bucket = setalloc(bbinfo->size);
893                 bb->df = setalloc(bbinfo->size);
894                 bb->dfchildren = setalloc(bbinfo->size);
pj
1.8
895         }
896
897         dfsnum = 0;
ragge
1.11
898         cfg_dfs(DLIST_NEXT(&bblocksbbelem), 0bbinfo);
pj
1.8
899
pj
1.20
900 #if 0
901         { struct basicblock *bbbstruct cfgnode *ccnode;
902         DLIST_FOREACH(bbb, &bblocksbbelem) {
903                 printf("Basic block %d, parents: "bbb->dfnum);
904                 SLIST_FOREACH(ccnode, &bbb->parentscfgelem) {
905                         printf("%d, "ccnode->bblock->dfnum);
906                 }
907                 printf("\nChildren: ");
908                 SLIST_FOREACH(ccnode, &bbb->childrencfgelem) {
909                         printf("%d, "ccnode->bblock->dfnum);
910                 }
911                 printf("\n");
912         }
913         }
914 #endif
915
pj
1.10
916         for(h = bbinfo->size - 1h > 1h--) {
917                 bb = bbinfo->arr[h];
pj
1.8
918                 p = s = bbinfo->arr[bb->dfparent];
ragge
1.11
919                 SLIST_FOREACH(cnode, &bb->parentscfgelem) {
pj
1.8
920                         if (cnode->bblock->dfnum <= bb->dfnum
921                                 sprime = cnode->bblock;
pj
1.10
922                         else 
923                                 sprime = bbinfo->arr[ancestorwithlowestsemi
924                                               (cnode->bblockbbinfo)->semi];
pj
1.8
925                         if (sprime->dfnum < s->dfnum)
926                                 s = sprime;
927                 }
928                 bb->semi = s->dfnum;
pj
1.10
929                 BITSET(s->bucketbb->dfnum);
pj
1.8
930                 link(pbb);
931                 for (i = 1i < bbinfo->sizei++) {
pj
1.10
932                         if(TESTBIT(p->bucketi)) {
pj
1.8
933                                 v = bbinfo->arr[i];
pj
1.10
934                                 y = ancestorwithlowestsemi(vbbinfo);
935                                 if (y->semi == v->semi
pj
1.8
936                                         v->idom = p->dfnum;
937                                 else
938                                         v->samedom = y->dfnum;
939                         }
940                 }
941                 memset(p->bucket0, (bbinfo->size + 7)/8);
942         }
pj
1.10
943 #if 0
944         printf("Num\tSemi\tAncest\tidom\n");
pj
1.8
945         CIRCLEQ_FOREACH(bb, &bblocksbbelem) {
pj
1.10
946                 printf("%d\t%d\t%d\t%d\n"bb->dfnumbb->semibb->ancestorbb->idom);
947         }
948 #endif
949         for(h = 2h < bbinfo->sizeh++) {
950                 bb = bbinfo->arr[h];
951                 if (bb->samedom != 0) {
pj
1.8
952                         bb->idom = bbinfo->arr[bb->samedom]->idom;
pj
1.10
953                 }
954         }
ragge
1.11
955         DLIST_FOREACH(bb, &bblocksbbelem) {
pj
1.10
956                 if (bb->idom != 0 && bb->idom != bb->dfnum) {
957 #if 0
958
959                         printf("Setting child %d of %d\n"bb->dfnumbbinfo->arr[bb->idom]->dfnum);
960 #endif
961
962                         BITSET(bbinfo->arr[bb->idom]->dfchildrenbb->dfnum);
963                 }
pj
1.8
964         }
965 }
966
967
968 struct basicblock *
969 ancestorwithlowestsemi(struct basicblock *bblockstruct bblockinfo *bbinfo)
970 {
971         struct basicblock *u = bblock;
972         struct basicblock *v = bblock;
973
974         while (v->ancestor != 0) {
975                 if (bbinfo->arr[v->semi]->dfnum < 
pj
1.10
976                     bbinfo->arr[u->semi]->dfnum
pj
1.8
977                         u = v;
978                 v = bbinfo->arr[v->ancestor];
979         }
980         return u;
981 }
982
983 void
984 link(struct basicblock *parentstruct basicblock *child)
985 {
986         child->ancestor = parent->dfnum;
987 }
988
989 void
990 computeDF(struct basicblock *bblockstruct bblockinfo *bbinfo)
991 {
992         struct cfgnode *cnode;
pj
1.10
993         int hi;
pj
1.8
994         
ragge
1.11
995         SLIST_FOREACH(cnode, &bblock->childrencfgelem) {
pj
1.8
996                 if (cnode->bblock->idom != bblock->dfnum)
997                         BITSET(bblock->dfcnode->bblock->dfnum);
998         }
pj
1.10
999         for (h = 1h < bbinfo->sizeh++) {
1000                 if (!TESTBIT(bblock->dfchildrenh))
1001                         continue;
1002                 computeDF(bbinfo->arr[h], bbinfo);
pj
1.8
1003                 for (i = 1i < bbinfo->sizei++) {
pj
1.10
1004                         if (TESTBIT(bbinfo->arr[h]->dfi) && 
1005                             (bbinfo->arr[h] == bblock ||
1006                              (bblock->idom != bbinfo->arr[h]->dfnum))) 
pj
1.8
1007                             BITSET(bblock->dfi);
1008                 }
1009         }
1010 }
pj
1.15
1011
pj
1.21
1012 static struct basicblock *currbb;
1013 static struct interpass *currip;
1014
1015 /* Helper function for findTemps, Find assignment nodes. */
1016 static void
1017 findasg(NODE *p)
1018 {
1019         struct pvarinfo *pv;
1020
1021         if (p->n_op != ASSIGN)
1022                 return;
1023
1024         if (p->n_left->n_op != TEMP)
1025                 return;
1026
1027         pv = tmpcalloc(sizeof(struct pvarinfo));
1028         pv->next = defsites.arr[p->n_left->n_lval];
1029         pv->bb = currbb;
1030         pv->top = currip->ip_node;
1031         pv->n = p->n_left;
pj
1.22
1032         BITSET(currbb->Aorigp->n_left->n_lval);
pj
1.21
1033
1034         defsites.arr[p->n_left->n_lval] = pv;
1035 }
1036
1037 /* Walk the interpass looking for assignment nodes. */
1038 void findTemps(struct interpass *ip)
pj
1.20
1039 {
1040         if (ip->type != IP_NODE)
1041                 return;
1042
pj
1.21
1043         currip = ip;
1044
1045         walkf(ip->ip_nodefindasg);
pj
1.20
1046 }
1047
1048 /*
1049  * Algorithm 19.6 from Appel.
1050  */
1051
1052 void
1053