Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20081116211741

Diff

Diff from 1.58 to:

Annotations

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

Annotated File View

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