Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20050905170716

Diff

Diff from 1.38 to:

Annotations

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

Annotated File View

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