Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20050629071241

Diff

Diff from 1.28 to:

Annotations

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

Annotated File View

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