Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20050628132900

Diff

Diff from 1.26 to:

Annotations

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

Annotated File View

ragge
1.26
1 /*      $Id: optim2.c,v 1.26 2005/06/28 13:29:00 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;
417         struct interpass *ip, *n, *ip2;
418         int gotone,lowhigh;
419         int *lblaryiszo;
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
440         /* Delete all goto/branch to the following label */
441         DLIST_FOREACH(ip, &ipoleqelem) {
442                 if (ip->type == IP_DEFLAB) {
443                         lblary[ip->ip_lbl-low] |= FOUND;
444 printf("IP_DEFLAB: %d\n"ip->ip_lbl);
445                         ip2 = DLIST_NEXT(ipqelem);
446 printf("ip2 %d\n"ip2->type);
447                         while (ip2->type == IP_DEFLAB ||
448                             ip2->type == IP_STKOFF) {
449                                 if (ip2->type == IP_DEFLAB) {
450                                         lblary[ip2->ip_lbl-low] = -ip->ip_lbl;
451 printf("coal %d\n"ip2->ip_lbl);
452                                         DLIST_REMOVE(ip2qelem);
453                                         gotone = 1;
454                                 } else
455                                         ip = ip2;
456                                 ip2 = DLIST_NEXT(ipqelem);
457                         }
458                         ip = DLIST_PREV(ipqelem);
459                         continue;
460                 }
461                 n = DLIST_NEXT(ipqelem);
462                 if (n->type != IP_NODE)
463                         continue;
464                 o = n->ip_node->n_op;
465                 if (o == GOTO)
466                         i = n->ip_node->n_left->n_lval;
467                 else if (o == CBRANCH)
468                         i = n->ip_node->n_right->n_lval;
469                 else
470                         continue;
471                 if (lblary[i-low] < 0) {
472                         if (o == GOTO)
473                                 n->ip_node->n_left->n_lval = -lblary[i-low];
474                         else
475                                 n->ip_node->n_right->n_lval = -lblary[i-low];
476                         gotone = 1;
477                 }
478                 ip2 = DLIST_NEXT(nqelem);
479                 if (ip2->type == IP_DEFLAB && ip2->ip_lbl == i) {
480                         tfree(n->ip_node);
481                         DLIST_REMOVE(nqelem);
482                         gotone = 1;
483                 }
484         }
485         if (gotone)
486                 goto again;
487
488 #ifdef notyet
489         tmpfree(mark);
490 #endif
491
492 #if 0
493         DLIST_FOREACH(ip, &ipoleqelem) {
494                 if (ip->type == IP_DEFLAB) {
495                         lblary[ip->ip_lbl-low] |= FOUND;
496                         ip2 = DLIST_NEXT(ipqelem);
497                         while (ip2->type == IP_DEFLAB) {
498                                 lblary[ip2->ip_lbl-low] = -ip->ip_lbl;
499                                 DLIST_REMOVE(ip2qelem);
500                                 ip2 = DLIST_NEXT(ipqelem);
501                         }
502                 }
503                 if (ip->type != IP_NODE)
504                         continue;
505                 if (o == GOTO)
506                         i = ip->ip_node->n_left->n_lval;
507                 else if (o == CBRANCH)
508                         i = ip->ip_node->n_right->n_lval;
509                 else
510                         continue;
511                 if (lblary[i-low] < 0) {
512                         /* coalesced */
513                         
514                 lblary[i-low] |= REFD;
515         }
516
517
518
ragge
1.1
519
520 again:  gotone = 0;
521
ragge
1.26
522
523
524
525
526
527
ragge
1.11
528         DLIST_FOREACH(ip, &ipoleqelem) {
ragge
1.1
529                 if (ip->type == IP_EPILOG)
530                         return;
531                 if (ip->type != IP_NODE)
532                         continue;
ragge
1.11
533                 n = DLIST_NEXT(ipqelem);
ragge
1.1
534                 /* Check for nodes without side effects */
535                 if (ip->ip_node->n_op != GOTO)
536                         continue;
537                 switch (n->type) {
538                 case IP_NODE:
539                         tfree(n->ip_node);
ragge
1.11
540                         DLIST_REMOVE(nqelem);
ragge
1.1
541                         break;
542                 case IP_DEFLAB:
543                         if (ip->ip_node->n_left->n_lval != n->ip_lbl)
544                                 continue;
545                         tfree(ip->ip_node);
546                         *ip = *n;
547                         break;
548                 default:
549                         continue;
550                 }
551                 gotone = 1;
552         }
553         if (gotone)
554                 goto again;
ragge
1.26
555 #endif
ragge
1.1
556 }
557
558 void
559 optdump(struct interpass *ip)
560 {
561         static char *nm[] = { "node""prolog""newblk""epilog""locctr",
562                 "deflab""defnam""asm" };
563         printf("type %s\n"nm[ip->type-1]);
564         switch (ip->type) {
565         case IP_NODE:
566                 fwalk(ip->ip_nodee2print0);
567                 break;
568         case IP_DEFLAB:
569                 printf("label " LABFMT "\n"ip->ip_lbl);
570                 break;
571         case IP_ASM:
572                 printf(": %s\n"ip->ip_asm);
573                 break;
574         }
575 }
pj
1.4
576
577 /*
578  * Build the basic blocks, algorithm 9.1, pp 529 in Compilers.
579  *
580  * Also fills the labelinfo struct with information about which bblocks
581  * that contain which label.
582  */
583
584 int
pj
1.8
585 bblocks_build(struct labelinfo *labinfostruct bblockinfo *bbinfo)
pj
1.4
586 {
587         struct interpass *ip;
588         struct basicblock *bb = NULL;
589         int leader = 1;
pj
1.12
590         unsigned int lowhigh = 0;
pj
1.8
591         int count = 0;
pj
1.4
592         int i;
593
pj
1.12
594         low = sizeof(int) == 2 ? 65000 : 1000000000;
pj
1.4
595         /* 
596          * First statement is a leader.
597          * Any statement that is target of a jump is a leader.
598          * Any statement that immediately follows a jump is a leader.
599          */
600
ragge
1.11
601         DLIST_FOREACH(ip, &ipoleqelem) {
pj
1.4
602                 /* Garbage, skip it */
603                 if (leader) {
604                         bb = tmpalloc(sizeof(struct basicblock));
605                         bb->first = bb->last = ip;
ragge
1.11
606                         SLIST_INIT(&bb->children);
607                         SLIST_INIT(&bb->parents);
pj
1.8
608                         bb->dfnum = 0;
609                         bb->dfparent = 0;
610                         bb->semi = 0;
611                         bb->ancestor = 0;
612                         bb->idom = 0;
613                         bb->samedom = 0;
614                         bb->bucket = NULL;
615                         bb->df = NULL;
pj
1.10
616                         bb->dfchildren = NULL;
pj
1.22
617                         bb->Aorig = NULL;
618                         bb->Aphi = NULL;
ragge
1.11
619                         DLIST_INSERT_BEFORE(&bblocksbbbbelem);
pj
1.4
620                         leader = 0;
pj
1.8
621                         count++;
pj
1.4
622                 } 
623                 
624                 /* Prologue and epilogue in their own bblock */
625                 if ((ip->type == IP_PROLOG) || (ip->type == IP_EPILOG)) {
626                         bb->last = ip;
627                         if (ip->type == IP_EPILOG)
ragge
1.5
628                                 high = MAX(ip->ip_lblhigh);
pj
1.4
629                         leader = 1;
630                         continue;
631                 }
632                 
633                 /* Keep track of highest and lowest label number */
634                 if (ip->type == IP_DEFLAB) {
635                         low = MIN(ip->ip_lbllow);
636                         high = MAX(ip->ip_lblhigh);
637                 }
638
639                 /* Make sure each label is in a unique bblock */
640                 if (((ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) && 
641                     bb->first != ip) {
642                         bb = tmpalloc(sizeof(struct basicblock));
643                         bb->first = bb->last = ip;
ragge
1.11
644                         SLIST_INIT(&bb->children);
645                         SLIST_INIT(&bb->parents);
pj
1.8
646                         bb->dfnum = 0;
647                         bb->dfparent = 0;
648                         bb->semi = 0;
649                         bb->ancestor = 0;
650                         bb->idom = 0;
651                         bb->samedom = 0;
652                         bb->bucket = NULL;
653                         bb->df = NULL;
pj
1.10
654                         bb->dfchildren = NULL;
pj
1.22
655                         bb->Aorig = NULL;
656                         bb->Aphi = NULL;
ragge
1.11
657                         DLIST_INSERT_BEFORE(&bblocksbbbbelem);
pj
1.8
658                         count++;
pj
1.4
659                         continue;
660                 }
661
662                 if (ip->type == IP_ASM)
663                         return 0;
664
665                 if (ip->type == IP_NODE) {
666                         switch(ip->ip_node->n_op) {
667                         case CBRANCH:
668                         case GOTO:
669                         case RETURN:
670                                 /* Jumps, last in bblock. */
671                                 leader = 1;
672                                 break;
673
674                         case NAME:
675                         case ICON:
676                         case FCON:
677                         case REG:
678                         case OREG:
679                         case MOVE:
680                         case PLUS:
681                         case MINUS:
682                         case DIV:
683                         case MOD:
684                         case MUL:
685                         case AND:
686                         case OR:
687                         case ER:
688                         case LS:
689                         case COMPL:
690                         case INCR:
691                         case DECR:
692                         case UMUL:
693                         case UMINUS:
694                         case EQ:
695                         case NE:
696                         case LE:
697                         case GE:
698                         case GT:
699                         case ULE:
700                         case ULT:
701                         case UGE:
702                         case UGT:
703                         case ASSIGN:
704                         case FORCE:
705                         case FUNARG:
pj
1.7
706                         case CALL:
707                         case UCALL:
708                         case FORTCALL:
709                         case UFORTCALL:
710                         case STCALL:
711                         case USTCALL:
pj
1.4
712                                 /* Not jumps, continue with bblock. */
713                                 break;
714
715                         default:
716                                 comperr("optim2:bblocks_build() %d",ip->ip_node->n_op ); 
717                                 break;
718                         }
719                 }
720
721                 bb->last = ip;
722         }
pj
1.20
723 #if 0
pj
1.8
724         printf("Basic blocks in func: %d\n"count);
pj
1.10
725         printf("Label range in func: %d\n"high - low + 1);
pj
1.4
726 #endif
727
728         labinfo->low = low;
729         labinfo->size = high - low + 1;
730         labinfo->arr = tmpalloc(labinfo->size * sizeof(struct basicblock *));
pj
1.8
731         for (i = 0i <= labinfo->sizei++) {
pj
1.4
732                 labinfo->arr[i] = NULL;
733         }
pj
1.8
734         
735         bbinfo->size = count + 1;
736         bbinfo->arr = tmpalloc(bbinfo->size * sizeof(struct basicblock *));
737         for (i = 0i <= bbinfo->sizei++) {
738                 bbinfo->arr[i] = NULL;
739         }
pj
1.4
740
ragge
1.11
741         DLIST_FOREACH(bb, &bblocksbbelem) {
pj
1.20
742                 /* Build the label table */
pj
1.4
743                 if (bb->first->type == IP_DEFLAB) {
744                         labinfo->arr[bb->first->ip_lbl - low] = bb;
745                 }
746                 if (bb->first->type == IP_EPILOG) {
ragge
1.5
747                         labinfo->arr[bb->first->ip_lbl - low] = bb;
pj
1.4
748                 }
749         }
750
751         return 1;
752 }
753
754 /*
755  * Build the control flow graph.
756  */
757
758 void
759 cfg_build(struct labelinfo *labinfo)
760 {
761         /* Child and parent nodes */
762         struct cfgnode *cnode
763         struct cfgnode *pnode;
764         struct basicblock *bb;
765         
ragge
1.11
766         DLIST_FOREACH(bb, &bblocksbbelem) {
pj
1.4
767
768                 if (bb->first->type == IP_EPILOG) {
769                         break;
770                 }
771
772                 cnode = tmpalloc(sizeof(struct cfgnode));
773                 pnode = tmpalloc(sizeof(struct cfgnode));
774                 pnode->bblock = bb;
775
776                 if ((bb->last->type == IP_NODE) && 
777                     (bb->last->ip_node->n_op == GOTO)) {
778                         if (bb->last->ip_node->n_left->n_lval - labinfo->low > 
779                             labinfo->size) {
780                                 comperr("Label out of range: %d, base %d"
781                                         bb->last->ip_node->n_left->n_lval
782                                         labinfo->low);
783                         }
784                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_left->n_lval - labinfo->low];
ragge
1.11
785                         SLIST_INSERT_LAST(&cnode->bblock->parentspnodecfgelem);
786                         SLIST_INSERT_LAST(&bb->childrencnodecfgelem);
pj
1.4
787                         continue;
788                 }
789                 if ((bb->last->type == IP_NODE) && 
790                     (bb->last->ip_node->n_op == CBRANCH)) {
791                         if (bb->last->ip_node->n_right->n_lval - labinfo->low > 
792                             labinfo->size
793                                 comperr("Label out of range: %d"
794                                         bb->last->ip_node->n_left->n_lval);
795                         
796                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_right->n_lval - labinfo->low];
ragge
1.11
797                         SLIST_INSERT_LAST(&cnode->bblock->parentspnodecfgelem);
798                         SLIST_INSERT_LAST(&bb->childrencnodecfgelem);
pj
1.4
799                         cnode = tmpalloc(sizeof(struct cfgnode));
800                         pnode = tmpalloc(sizeof(struct cfgnode));
801                         pnode->bblock = bb;
802                 }
803
ragge
1.11
804                 cnode->bblock = DLIST_NEXT(bbbbelem);
805                 SLIST_INSERT_LAST(&cnode->bblock->parentspnodecfgelem);
806                 SLIST_INSERT_LAST(&bb->childrencnodecfgelem);
pj
1.4
807         }
808 }
pj
1.6
809
pj
1.8
810 void
811 cfg_dfs(struct basicblock *bbunsigned int parentstruct bblockinfo *bbinfo)
812 {
813         struct cfgnode *cnode;
814         
815         if (bb->dfnum != 0)
816                 return;
817
818         bb->dfnum = ++dfsnum;
819         bb->dfparent = parent;
820         bbinfo->arr[bb->dfnum] = bb;
ragge
1.11
821         SLIST_FOREACH(cnode, &bb->childrencfgelem) {
pj
1.8
822                 cfg_dfs(cnode->bblockbb->dfnumbbinfo);
823         }
pj
1.13
824         /* Don't bring in unreachable nodes in the future */
pj
1.20
825         bbinfo->size = dfsnum + 1;
pj
1.8
826 }
827
ragge
1.11
828 static bittype *
829 setalloc(int nelem)
830 {
831         bittype *b;
832         int sz = (nelem+NUMBITS-1)/NUMBITS;
833
834         b = tmpalloc(sz * sizeof(bittype));
835         memset(b0sz * sizeof(bittype));
836         return b;
837 }
838
pj
1.8
839 /*
840  * Algorithm 19.9, pp 414 from Appel.
841  */
842
843 void
844 dominators(struct bblockinfo *bbinfo)
845 {
846         struct cfgnode *cnode;
847         struct basicblock *bb, *y, *v;
848         struct basicblock *s, *sprime, *p;
pj
1.10
849         int hi;
pj
1.8
850
ragge
1.11
851         DLIST_FOREACH(bb, &bblocksbbelem) {
852                 bb->bucket = setalloc(bbinfo->size);
853                 bb->df = setalloc(bbinfo->size);
854                 bb->dfchildren = setalloc(bbinfo->size);
pj
1.8
855         }
856
857         dfsnum = 0;
ragge
1.11
858         cfg_dfs(DLIST_NEXT(&bblocksbbelem), 0bbinfo);
pj
1.8
859
pj
1.20
860 #if 0
861         { struct basicblock *bbbstruct cfgnode *ccnode;
862         DLIST_FOREACH(bbb, &bblocksbbelem) {
863                 printf("Basic block %d, parents: "bbb->dfnum);
864                 SLIST_FOREACH(ccnode, &bbb->parentscfgelem) {
865                         printf("%d, "ccnode->bblock->dfnum);
866                 }
867                 printf("\nChildren: ");
868                 SLIST_FOREACH(ccnode, &bbb->childrencfgelem) {
869                         printf("%d, "ccnode->bblock->dfnum);
870                 }
871                 printf("\n");
872         }
873         }
874 #endif
875
pj
1.10
876         for(h = bbinfo->size - 1h > 1h--) {
877                 bb = bbinfo->arr[h];
pj
1.8
878                 p = s = bbinfo->arr[bb->dfparent];
ragge
1.11
879                 SLIST_FOREACH(cnode, &bb->parentscfgelem) {
pj
1.8
880                         if (cnode->bblock->dfnum <= bb->dfnum
881                                 sprime = cnode->bblock;
pj
1.10
882                         else 
883                                 sprime = bbinfo->arr[ancestorwithlowestsemi
884                                               (cnode->bblockbbinfo)->semi];
pj
1.8
885                         if (sprime->dfnum < s->dfnum)
886                                 s = sprime;
887                 }
888                 bb->semi = s->dfnum;
pj
1.10
889                 BITSET(s->bucketbb->dfnum);
pj
1.8
890                 link(pbb);
891                 for (i = 1i < bbinfo->sizei++) {
pj
1.10
892                         if(TESTBIT(p->bucketi)) {
pj
1.8
893                                 v = bbinfo->arr[i];
pj
1.10
894                                 y = ancestorwithlowestsemi(vbbinfo);
895                                 if (y->semi == v->semi
pj
1.8
896                                         v->idom = p->dfnum;
897                                 else
898                                         v->samedom = y->dfnum;
899                         }
900                 }
901                 memset(p->bucket0, (bbinfo->size + 7)/8);
902         }
pj
1.10
903 #if 0
904         printf("Num\tSemi\tAncest\tidom\n");
pj
1.8
905         CIRCLEQ_FOREACH(bb, &bblocksbbelem) {
pj
1.10
906                 printf("%d\t%d\t%d\t%d\n"bb->dfnumbb->semibb->ancestorbb->idom);
907         }
908 #endif
909         for(h = 2h < bbinfo->sizeh++) {
910                 bb = bbinfo->arr[h];
911                 if (bb->samedom != 0) {
pj
1.8
912                         bb->idom = bbinfo->arr[bb->samedom]->idom;
pj
1.10
913                 }
914         }
ragge
1.11
915         DLIST_FOREACH(bb, &bblocksbbelem) {
pj
1.10
916                 if (bb->idom != 0 && bb->idom != bb->dfnum) {
917 #if 0
918
919                         printf("Setting child %d of %d\n"bb->dfnumbbinfo->arr[bb->idom]->dfnum);
920 #endif
921
922                         BITSET(bbinfo->arr[bb->idom]->dfchildrenbb->dfnum);
923                 }
pj
1.8
924         }
925 }
926
927
928 struct basicblock *
929 ancestorwithlowestsemi(struct basicblock *bblockstruct bblockinfo *bbinfo)
930 {
931         struct basicblock *u = bblock;
932         struct basicblock *v = bblock;
933
934         while (v->ancestor != 0) {
935                 if (bbinfo->arr[v->semi]->dfnum < 
pj
1.10
936                     bbinfo->arr[u->semi]->dfnum
pj
1.8
937                         u = v;
938                 v = bbinfo->arr[v->ancestor];
939         }
940         return u;
941 }
942
943 void
944 link(struct basicblock *parentstruct basicblock *child)
945 {
946         child->ancestor = parent->dfnum;
947 }
948
949 void
950 computeDF(struct basicblock *bblockstruct bblockinfo *bbinfo)
951 {
952         struct cfgnode *cnode;
pj
1.10
953         int hi;
pj
1.8
954         
ragge
1.11
955         SLIST_FOREACH(cnode, &bblock->childrencfgelem) {
pj
1.8
956                 if (cnode->bblock->idom != bblock->dfnum)
957                         BITSET(bblock->dfcnode->bblock->dfnum);
958         }
pj
1.10
959         for (h = 1h < bbinfo->sizeh++) {
960                 if (!TESTBIT(bblock->dfchildrenh))
961                         continue;
962                 computeDF(bbinfo->arr[h], bbinfo);
pj
1.8
963                 for (i = 1i < bbinfo->sizei++) {
pj
1.10
964                         if (TESTBIT(bbinfo->arr[h]->dfi) && 
965                             (bbinfo->arr[h] == bblock ||
966                              (bblock->idom != bbinfo->arr[h]->dfnum))) 
pj
1.8
967                             BITSET(bblock->dfi);
968                 }
969         }
970 }
pj
1.15
971
pj
1.21
972 static struct basicblock *currbb;
973 static struct interpass *currip;
974
975 /* Helper function for findTemps, Find assignment nodes. */
976 static void
977 findasg(NODE *p)
978 {
979         struct pvarinfo *pv;
980
981         if (p->n_op != ASSIGN)
982                 return;
983
984         if (p->n_left->n_op != TEMP)
985                 return;
986
987         pv = tmpcalloc(sizeof(struct pvarinfo));
988         pv->next = defsites.arr[p->n_left->n_lval];
989         pv->bb = currbb;
990         pv->top = currip->ip_node;
991         pv->n = p->n_left;
pj
1.22
992         BITSET(currbb->Aorigp->n_left->n_lval);
pj
1.21
993
994         defsites.arr[p->n_left->n_lval] = pv;
995 }
996
997 /* Walk the interpass looking for assignment nodes. */
998 void findTemps(struct interpass *ip)
pj
1.20
999 {
1000         if (ip->type != IP_NODE)
1001                 return;
1002
pj
1.21
1003         currip = ip;
1004
1005         walkf(ip->ip_nodefindasg);
pj
1.20
1006 }
1007
1008 /*
1009  * Algorithm 19.6 from Appel.
1010  */
1011
1012 void
1013 placePhiFunctions(struct bblockinfo *bbinfo)
1014 {
1015         struct basicblock *bb;
1016         struct interpass *ip;
1017         int maxtmpijkl;
1018         struct pvarinfo *n;
1019         struct cfgnode *cnode;
1020         TWORD ntype;
1021         NODE *p;
pj
1.22
1022         struct pvarinfo *pv;
pj
1.20
1023
1024         bb = DLIST_NEXT(&bblocksbbelem);
1025         defsites.low = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
1026         bb = DLIST_PREV(&bblocksbbelem);
1027         maxtmp = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
1028         defsites.size = maxtmp - defsites.low + 1;
1029         defsites.arr = tmpcalloc(defsites.size*sizeof(struct pvarinfo *));
1030
pj
1.21
1031         /* Find all defsites */
pj
1.20
1032         DLIST_FOREACH(bb, &bblocksbbelem) {
pj
1.21
1033                 currbb = bb;
pj
1.20
1034                 ip = bb->first;
pj
1.22
1035                 bb->Aorig = setalloc(defsites.size);
1036                 bb->Aphi = setalloc(defsites.size);
1037                 
pj
1.20
1038
1039                 while (ip != bb->last) {
pj
1.21
1040                         findTemps(ip);
pj
1.20
1041                         ip = DLIST_NEXT(ipqelem);
1042                 }
1043                 /* Make sure we get the last statement in the bblock */
pj
1.21
1044                 findTemps(ip);
pj
1.20
1045         }
pj
1.21
1046         /* For each variable */
pj
1.20
1047         for (i = defsites.lowi < defsites.sizei++) {