Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:pj:20050121154134

Diff

Diff from 1.6 to:

Annotations

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

Annotated File View

pj
1.6
1 /*      $Id: optim2.c,v 1.6 2005/01/21 15:41:34 pj 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 #include "external.h"
31
ragge
1.3
32 #include <string.h>
pj
1.4
33 #include <stdlib.h>
34 #include <machine/limits.h>
35
36 #ifndef MIN
37 #define MIN(a,b) (((a)<(b))?(a):(b))
38 #endif
39
40 #ifndef MAX
41 #define MAX(a,b) (((a) > (b)) ? (a) : (b))
42 #endif
ragge
1.3
43
ragge
1.1
44 extern int saving;
45
46 void saveip(struct interpass *ip);
47 void deljumps(void);
48 void deltemp(NODE *p);
49 void optdump(struct interpass *ip);
50
51 static SIMPLEQ_HEAD(, interpassipole = SIMPLEQ_HEAD_INITIALIZER(ipole);
52
53 static struct rsv {
54         struct rsv *next;
55         int fpoff;
56         TWORD type;
57         int use;
58 } *rsv;
59
pj
1.4
60 int bblocks_build(struct labelinfo *labinfo);
61 void cfg_build(struct labelinfo *labinfo);
62
63
64 static CIRCLEQ_HEAD(, basicblockbblocks = CIRCLEQ_HEAD_INITIALIZER(bblocks);
65
ragge
1.1
66 static void
67 addcand(TWORD typeint offint avoid)
68 {
69         struct rsv *w = rsv;
70
71         while (w != NULL) {
72                 if (w->type == type && w->fpoff == off) {
73                         if (avoid)
74                                 w->use = -1;
75                         else if (w->use > 0)
76                                 w->use++;
77                         return;
78                 }
79                 w = w->next;
80         }
81         w = tmpalloc(sizeof(*w));
82         w->type = type;
83         w->fpoff = off;
84         w->use = avoid ? -1 : 1;
85         w->next = rsv;
86         rsv = w;
87 }
88
89 /*
90  * walk through the tree and count the number of (possible)
91  * temporary nodes.
92  */
93 static void
94 cntuse(NODE *p)
95 {
96         NODE *l = p->n_left;
97         NODE *r = p->n_right;
98
99         if (p->n_op == UMUL && l->n_op == REG && l->n_rval == FPREG) {
100                 /* found a candidate for register */
101                 addcand(p->n_type0ISVOL(p->n_qual << TSHIFT));
102         } else if (p->n_op == UMUL && l->n_op == PLUS &&
103             l->n_right->n_op == ICON && 
104              (l->n_left->n_op == REG && l->n_left->n_rval == FPREG)) {
105                 /* The same as above */
106                 addcand(p->n_typel->n_right->n_lval,
107                     ISVOL(p->n_qual << TSHIFT));
108         } else if (p->n_op == PLUS && l->n_op == REG && l->n_rval == FPREG &&
109             p->n_right->n_op == ICON) {
110                 /* Address taken of temporary, avoid register */
111                 addcand(DECREF(p->n_type), r->n_lval1);
112         } else {
113                 if (optype(p->n_op) == BITYPE)
114                         cntuse(r);
115                 if (optype(p->n_op) != LTYPE)
116                         cntuse(l);
117         }
118 }
119
120 /*
ragge
1.2
121  * Insert a node into the register stack.
122  */
123 static void
124 insert(struct rsv *wstruct rsv **savedint maxregs)
125 {
126         int ijsize;
127
128         size = szty(w->type);
129
130         /* Find reg move position */
131         for (i = 0i < maxregsi++) {
132                 if (saved[i] == NULL)
133                         continue;
134                 if (saved[i]->use > w->use)
135                         break;
136         }
137         /* Move down other regs */
138         for (j = sizej < ij++)
139                 saved[j-size] = saved[j];
140
141         /* Insert new reg pointer */
142         if (i-size >= 0) {
143                 saved[i-size] = w;
144                 for (j = i-size+1j < ij++)
145                         saved[j] = NULL;
146         }
147 }
148
149 /* Help routine to rconvert() */
150 static int
151 matches(TWORD typeint offstruct rsv **rsvint maxregs)
152 {
153         int i;
154
155         for (i = 0i < maxregsi++)
156                 if (rsv[i] && rsv[i]->type == type && rsv[i]->fpoff == off)
157                         return i;
158         return -1;
159 }
160
161 /* Help routine to rconvert() */
162 static void
163 modify(NODE *pint reg)
164 {
165         tfree(p->n_left);
166         p->n_op = REG;
167         p->n_rval = p->n_rall = reg + MINRVAR;
168         p->n_lval = 0;
169 }
170
171 /*
172  * walk through the tree and convert nodes to registers
173  */
174 static void
175 rconvert(NODE *pstruct rsv **rsvint maxregs)
176 {
177         NODE *l = p->n_left;
178         NODE *r = p->n_right;
179         int i;
180
181         if (p->n_op == UMUL && l->n_op == REG && l->n_rval == FPREG) {
182                 /* found a candidate for register */
183                 if ((i = matches(p->n_type0rsvmaxregs)) >= 0)
184                         modify(pi);
185         } else if (p->n_op == UMUL && l->n_op == PLUS &&
186             l->n_right->n_op == ICON && 
187              (l->n_left->n_op == REG && l->n_left->n_rval == FPREG)) {
188                 /* The same as above */
189                 if ((i = matches(p->n_type,
190                     l->n_right->n_lvalrsvmaxregs)) >= 0)
191                         modify(pi);
192 #if 0
193         } else if (p->n_op == PLUS && l->n_op == REG && l->n_rval == FPREG &&
194             p->n_right->n_op == ICON) {
195                 /* Address taken of temporary, avoid register */
196                 addcand(DECREF(p->n_type), r->n_lval1);
197 #endif
198         } else {
199                 if (optype(p->n_op) == BITYPE)
200                         rconvert(rrsvmaxregs);
201                 if (optype(p->n_op) != LTYPE)
202                         rconvert(lrsvmaxregs);
203         }
204 }
205
206 /*
ragge
1.1
207  * Assign non-temporary registers to variables.
208  * Cannot do it if:
209  * - address is taken of the temporary
210  * - variable is declared "volatile".
211  */
pj
1.4
212 int asgregs(void);
213 int
ragge
1.1
214 asgregs(void)
215 {
216         struct interpass *ip;
ragge
1.2
217         struct rsv *w, **saved;
218         int imaxregs = MAXRVAR - MINRVAR + 1;
ragge
1.1
219
ragge
1.2
220         if (maxregs == 0)
221                 return MAXRVAR/* No register usage */
ragge
1.1
222         rsv = NULL;
223
224         /* Loop over the function to do a usage count */
225         SIMPLEQ_FOREACH(ip, &ipolesqelem) {
226                 if (ip->type != IP_NODE)
227                         continue;
228                 cntuse(ip->ip_node);
229         }
230         /* Check which nodes that shall be converted to registers */
ragge
1.2
231         saved = tmpalloc(sizeof(struct rsv *) * maxregs);
232         memset(saved0sizeof(struct rsv *) * maxregs);
ragge
1.1
233         w = rsv;
234         for (w = rsvww = w->next) {
235                 if (w->use < 0)
ragge
1.2
236                         continue/* Not allowed to be in register */
237
238                 /* XXX check here if type is allowed to be in register */
239
240                 insert(wsavedmaxregs);
ragge
1.1
241         }
242
243         /* Convert found nodes to registers */
ragge
1.2
244         SIMPLEQ_FOREACH(ip, &ipolesqelem) {
245                 if (ip->type != IP_NODE)
246                         continue;
247                 rconvert(ip->ip_nodesavedmaxregs);
248         }
249         for (i = 0i < maxregsi++)
250                 if (saved[i] != NULL)
251                         break;
252         return MINRVAR+i-1;
ragge
1.1
253 }
254
255 void
256 saveip(struct interpass *ip)
257 {
ragge
1.5
258         struct interpass_prolog *ipp, *epp;
259
pj
1.4
260 #if 0
ragge
1.2
261         int regs;
pj
1.4
262 #endif
263         struct labelinfo labinfo;
ragge
1.1
264
265         SIMPLEQ_INSERT_TAIL(&ipoleipsqelem);
266
267         if (ip->type != IP_EPILOG)
268                 return;
ragge
1.5
269         epp = (struct interpass_prolog *)ip;
ragge
1.1
270         saving = -1;
271
pj
1.4
272         //              deljumps();     /* Delete redundant jumps and dead code */
273         if (xssaflag) {
274                 CIRCLEQ_INIT(&bblocks);
275                 if (bblocks_build(&labinfo)) {
276                         cfg_build(&labinfo);
277 #if 0
pj
1.6
278                         if (xssaflag) {
279                                 dfg = dfg_build(cfg);
280                                 ssa = ssa_build(cfgdfg);
281                         }
pj
1.4
282 #endif
283                 }
284  
285         }
286 #if 0
ragge
1.2
287         regs = asgregs();       /* Assign non-temporary registers */
pj
1.4
288 #endif
ragge
1.2
289
290 #ifdef PCC_DEBUG
ragge
1.5
291         if (epp->ipp_regs != MAXRVAR)
ragge
1.2
292                 comperr("register error");
293 #endif
ragge
1.1
294
ragge
1.5
295         ipp = (struct interpass_prolog *)SIMPLEQ_FIRST(&ipole);
296         ipp->ipp_autos = epp->ipp_autos;
297         ipp->ipp_regs = epp->ipp_regs// = regs;
ragge
1.1
298
299 #ifdef MYOPTIM
pj
1.6
300         myoptim((struct interpass *)ipp);
ragge
1.1
301 #endif
302
303         while ((ip = SIMPLEQ_FIRST(&ipole))) {
304                 SIMPLEQ_REMOVE_HEAD(&ipolesqelem);
305                 pass2_compile(ip);
306         }
307 }
308
309 void
310 deljumps()
311 {
312         struct interpass *ip, *n;
313         int gotone;
314
315 again:  gotone = 0;
316
317         SIMPLEQ_FOREACH(ip, &ipolesqelem) {
318                 if (ip->type == IP_EPILOG)
319                         return;
320                 if (ip->type != IP_NODE)
321                         continue;
322                 n = ip->sqelem.sqe_next;
323                 /* Check for nodes without side effects */
324                 if (ip->ip_node->n_op != GOTO)
325                         continue;
326                 switch (n->type) {
327                 case IP_NODE:
328                         tfree(n->ip_node);
329                         ip->sqelem.sqe_next = n->sqelem.sqe_next;
330                         break;
331                 case IP_DEFLAB:
332                         if (ip->ip_node->n_left->n_lval != n->ip_lbl)
333                                 continue;
334                         tfree(ip->ip_node);
335                         *ip = *n;
336                         break;
337                 default:
338                         continue;
339                 }
340                 gotone = 1;
341         }
342         if (gotone)
343                 goto again;
344 }
345
346 void
347 optdump(struct interpass *ip)
348 {
349         static char *nm[] = { "node""prolog""newblk""epilog""locctr",
350                 "deflab""defnam""asm" };
351         printf("type %s\n"nm[ip->type-1]);
352         switch (ip->type) {
353         case IP_NODE:
354                 fwalk(ip->ip_nodee2print0);
355                 break;
356         case IP_DEFLAB:
357                 printf("label " LABFMT "\n"ip->ip_lbl);
358                 break;
359         case IP_ASM:
360                 printf(": %s\n"ip->ip_asm);
361                 break;
362         }
363 }
pj
1.4
364
365 /*
366  * Build the basic blocks, algorithm 9.1, pp 529 in Compilers.
367  *
368  * Also fills the labelinfo struct with information about which bblocks
369  * that contain which label.
370  */
371
372 int
373 bblocks_build(struct labelinfo *labinfo)
374 {
375         struct interpass *ip;
376         struct basicblock *bb = NULL;
377         int leader = 1;
378         unsigned int low = UINT_MAXhigh = 0;
379         int XXXcount = 0;
380         int i;
381
382         /* 
383          * First statement is a leader.
384          * Any statement that is target of a jump is a leader.
385          * Any statement that immediately follows a jump is a leader.
386          */
387
388         SIMPLEQ_FOREACH(ip, &ipolesqelem) {
389                 /* Garbage, skip it */
390                 if ((ip->type == IP_LOCCTR) || (ip->type == IP_NEWBLK))
391                         continue;
392
393                 if (leader) {
394                         bb = tmpalloc(sizeof(struct basicblock));
395                         bb->first = bb->last = ip;
396                         SIMPLEQ_INIT(&bb->children);
397                         SIMPLEQ_INIT(&bb->parents);
398                         CIRCLEQ_INSERT_TAIL(&bblocksbbbbelem);
399                         leader = 0;
400                         XXXcount++;
401                 } 
402                 
403                 /* Prologue and epilogue in their own bblock */
404                 if ((ip->type == IP_PROLOG) || (ip->type == IP_EPILOG)) {
405                         bb->last = ip;
406                         if (ip->type == IP_EPILOG)
ragge
1.5
407                                 high = MAX(ip->ip_lblhigh);
pj
1.4
408                         leader = 1;
409                         continue;
410                 }
411                 
412                 /* Keep track of highest and lowest label number */
413                 if (ip->type == IP_DEFLAB) {
414                         low = MIN(ip->ip_lbllow);
415                         high = MAX(ip->ip_lblhigh);
416                 }
417
418                 /* Make sure each label is in a unique bblock */
419                 if (((ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) && 
420                     bb->first != ip) {
421                         bb = tmpalloc(sizeof(struct basicblock));
422                         bb->first = bb->last = ip;
423                         SIMPLEQ_INIT(&bb->children);
424                         SIMPLEQ_INIT(&bb->parents);
425                         CIRCLEQ_INSERT_TAIL(&bblocksbbbbelem);
426                         XXXcount++;
427                         continue;
428                 }
429
430                 if (ip->type == IP_ASM)
431                         return 0;
432
433                 if (ip->type == IP_NODE) {
434                         switch(ip->ip_node->n_op) {
435                         case CBRANCH:
436                         case CALL:
437                         case UCALL:
438                         case FORTCALL:
439                         case UFORTCALL:
440                         case STCALL:
441                         case USTCALL:
442                         case GOTO:
443                         case RETURN:
444                                 /* Jumps, last in bblock. */
445                                 leader = 1;
446                                 break;
447
448                         case NAME:
449                         case ICON:
450                         case FCON:
451                         case REG:
452                         case OREG:
453                         case MOVE:
454                         case PLUS:
455                         case MINUS:
456                         case DIV:
457                         case MOD:
458                         case MUL:
459                         case AND:
460                         case OR:
461                         case ER:
462                         case LS:
463                         case COMPL:
464                         case INCR:
465                         case DECR:
466                         case UMUL:
467                         case UMINUS:
468                         case EQ:
469                         case NE:
470                         case LE:
471                         case GE:
472                         case GT:
473                         case ULE:
474                         case ULT:
475                         case UGE:
476                         case UGT:
477                         case ASSIGN:
478                         case FORCE:
479                         case FUNARG:
480                                 /* Not jumps, continue with bblock. */
481                                 break;
482
483                         default:
484                                 comperr("optim2:bblocks_build() %d",ip->ip_node->n_op ); 
485                                 break;
486                         }
487                 }
488
489                 bb->last = ip;
490         }
491 #ifdef PCC_DEBUG
492         printf("Basic blocks in func: %d\n"XXXcount);
493         printf("Label range in func: %d\n %d"high - low + 1low);
494 #endif
495
496         labinfo->low = low;
497         labinfo->size = high - low + 1;
498         labinfo->arr = tmpalloc(labinfo->size * sizeof(struct basicblock *));
499         for(i = 0i <= labinfo->sizei++) {
500                 labinfo->arr[i] = NULL;
501         }
502
503         /* Build the label table */
504         CIRCLEQ_FOREACH(bb, &bblocksbbelem) {
505                 if (bb->first->type == IP_DEFLAB) {
506                         labinfo->arr[bb->first->ip_lbl - low] = bb;
507                 }
508                 if (bb->first->type == IP_EPILOG) {
ragge
1.5
509                         labinfo->arr[bb->first->ip_lbl - low] = bb;
pj
1.4
510                 }
511         }
512
513         return 1;
514 }
515
516 /*
517  * Build the control flow graph.
518  */
519
520 void
521 cfg_build(struct labelinfo *labinfo)
522 {
523         /* Child and parent nodes */
524         struct cfgnode *cnode
525         struct cfgnode *pnode;
526         struct basicblock *bb;
527         
528         CIRCLEQ_FOREACH(bb, &bblocksbbelem) {
529
530                 if (bb->first->type == IP_EPILOG) {
531                         break;
532                 }
533
534                 cnode = tmpalloc(sizeof(struct cfgnode));
535                 pnode = tmpalloc(sizeof(struct cfgnode));
536                 pnode->bblock = bb;
537
538                 if ((bb->last->type == IP_NODE) && 
539                     (bb->last->ip_node->n_op == GOTO)) {
540                         if (bb->last->ip_node->n_left->n_lval - labinfo->low > 
541                             labinfo->size) {
542                                 comperr("Label out of range: %d, base %d"
543                                         bb->last->ip_node->n_left->n_lval
544                                         labinfo->low);
545                         }
546                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_left->n_lval - labinfo->low];
547                         SIMPLEQ_INSERT_TAIL(&cnode->bblock->parentspnodecfgelem);
548                         SIMPLEQ_INSERT_TAIL(&bb->childrencnodecfgelem);
549                         continue;
550                 }
551                 if ((bb->last->type == IP_NODE) && 
552                     (bb->last->ip_node->n_op == CBRANCH)) {
553                         if (bb->last->ip_node->n_right->n_lval - labinfo->low > 
554                             labinfo->size
555                                 comperr("Label out of range: %d"
556                                         bb->last->ip_node->n_left->n_lval);
557                         
558                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_right->n_lval - labinfo->low];
559                         SIMPLEQ_INSERT_TAIL(&cnode->bblock->parentspnodecfgelem);
560                         SIMPLEQ_INSERT_TAIL(&bb->childrencnodecfgelem);
561                         cnode = tmpalloc(sizeof(struct cfgnode));
562                         pnode = tmpalloc(sizeof(struct cfgnode));
563                         pnode->bblock = bb;
564                 }
565
566                 cnode->bblock = CIRCLEQ_NEXT(bbbbelem);
567                 SIMPLEQ_INSERT_TAIL(&cnode->bblock->parentspnodecfgelem);
568                 SIMPLEQ_INSERT_TAIL(&bb->childrencnodecfgelem);
569         }
570 }
pj
1.6
571
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-16 19:29 +0200