Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20050701181741

Diff

Diff from 1.31 to:

Annotations

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

Annotated File View

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