Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20050630130538

Diff

Diff from 1.29 to:

Annotations

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

Annotated File View

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