Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:gmcgarry:20071116223741

Diff

Diff from 1.48 to:

Annotations

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

Annotated File View

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