Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:pj:20050115153553

Diff

Diff from 1.4 to:

Annotations

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

Annotated File View

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