Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20050120212414

Diff

Diff from 1.5 to:

Annotations

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

Annotated File View

ragge
1.5
1 /*      $Id: optim2.c,v 1.5 2005/01/20 21:24:14 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 #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 {
ragge
1.5
277         struct interpass_prolog *ipp, *epp;
278
pj
1.4
279 #if 0
ragge
1.2
280         int regs;
pj
1.4
281 #endif
282         struct labelinfo labinfo;
ragge
1.1
283
284         SIMPLEQ_INSERT_TAIL(&ipoleipsqelem);
285
286         if (ip->type != IP_EPILOG)
287                 return;
ragge
1.5
288         epp = (struct interpass_prolog *)ip;
ragge
1.1
289         saving = -1;
290
pj
1.4
291         //              deljumps();     /* Delete redundant jumps and dead code */
292         if (xssaflag) {
293                 CIRCLEQ_INIT(&bblocks);
294                 if (bblocks_build(&labinfo)) {
295                         cfg_build(&labinfo);
296 #if 0
297                         dfg = dfg_build(cfg);
298                         ssa = ssa_build(cfgdfg);
299 #endif
300                 }
301  
302         }
303 #if 0
ragge
1.2
304         regs = asgregs();       /* Assign non-temporary registers */
pj
1.4
305 #endif
ragge
1.2
306
307 #ifdef PCC_DEBUG
ragge
1.5
308         if (epp->ipp_regs != MAXRVAR)
ragge
1.2
309                 comperr("register error");
310 #endif
ragge
1.1
311
ragge
1.5
312         ipp = (struct interpass_prolog *)SIMPLEQ_FIRST(&ipole);
313         ipp->ipp_autos = epp->ipp_autos;
314         ipp->ipp_regs = epp->ipp_regs// = regs;
ragge
1.1
315
316 #ifdef MYOPTIM
317         myoptim(prol);
318 #endif
319
320         while ((ip = SIMPLEQ_FIRST(&ipole))) {
321                 SIMPLEQ_REMOVE_HEAD(&ipolesqelem);
322                 pass2_compile(ip);
323         }
324 }
325
326 void
327 deljumps()
328 {
329         struct interpass *ip, *n;
330         int gotone;
331
332 again:  gotone = 0;
333
334         SIMPLEQ_FOREACH(ip, &ipolesqelem) {
335                 if (ip->type == IP_EPILOG)
336                         return;
337                 if (ip->type != IP_NODE)
338                         continue;
339                 n = ip->sqelem.sqe_next;
340                 /* Check for nodes without side effects */
341                 if (ip->ip_node->n_op != GOTO)
342                         continue;
343                 switch (n->type) {
344                 case IP_NODE:
345                         tfree(n->ip_node);
346                         ip->sqelem.sqe_next = n->sqelem.sqe_next;
347                         break;
348                 case IP_DEFLAB:
349                         if (ip->ip_node->n_left->n_lval != n->ip_lbl)
350                                 continue;
351                         tfree(ip->ip_node);
352                         *ip = *n;
353                         break;
354                 default:
355                         continue;
356                 }
357                 gotone = 1;
358         }
359         if (gotone)
360                 goto again;
361 }
362
363 void
364 optdump(struct interpass *ip)
365 {
366         static char *nm[] = { "node""prolog""newblk""epilog""locctr",
367                 "deflab""defnam""asm" };
368         printf("type %s\n"nm[ip->type-1]);
369         switch (ip->type) {
370         case IP_NODE:
371                 fwalk(ip->ip_nodee2print0);
372                 break;
373         case IP_DEFLAB:
374                 printf("label " LABFMT "\n"ip->ip_lbl);
375                 break;
376         case IP_ASM:
377                 printf(": %s\n"ip->ip_asm);
378                 break;
379         }
380 }
pj
1.4
381
382 /*
383  * Build the basic blocks, algorithm 9.1, pp 529 in Compilers.
384  *
385  * Also fills the labelinfo struct with information about which bblocks
386  * that contain which label.
387  */
388
389 int
390 bblocks_build(struct labelinfo *labinfo)
391 {
392         struct interpass *ip;
393         struct basicblock *bb = NULL;
394         int leader = 1;
395         unsigned int low = UINT_MAXhigh = 0;
396         int XXXcount = 0;
397         int i;
398
399         /* 
400          * First statement is a leader.
401          * Any statement that is target of a jump is a leader.
402          * Any statement that immediately follows a jump is a leader.
403          */
404
405         SIMPLEQ_FOREACH(ip, &ipolesqelem) {
406                 /* Garbage, skip it */
407                 if ((ip->type == IP_LOCCTR) || (ip->type == IP_NEWBLK))
408                         continue;
409
410                 if (leader) {
411                         bb = tmpalloc(sizeof(struct basicblock));
412                         bb->first = bb->last = ip;
413                         SIMPLEQ_INIT(&bb->children);
414                         SIMPLEQ_INIT(&bb->parents);
415                         CIRCLEQ_INSERT_TAIL(&bblocksbbbbelem);
416                         leader = 0;
417                         XXXcount++;
418                 } 
419                 
420                 /* Prologue and epilogue in their own bblock */
421                 if ((ip->type == IP_PROLOG) || (ip->type == IP_EPILOG)) {
422                         bb->last = ip;
423                         if (ip->type == IP_EPILOG)
ragge
1.5
424                                 high = MAX(ip->ip_lblhigh);
pj
1.4
425                         leader = 1;
426                         continue;
427                 }
428                 
429                 /* Keep track of highest and lowest label number */
430                 if (ip->type == IP_DEFLAB) {
431                         low = MIN(ip->ip_lbllow);
432                         high = MAX(ip->ip_lblhigh);
433                 }
434
435                 /* Make sure each label is in a unique bblock */
436                 if (((ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) && 
437                     bb->first != ip) {
438                         bb = tmpalloc(sizeof(struct basicblock));
439                         bb->first = bb->last = ip;
440                         SIMPLEQ_INIT(&bb->children);
441                         SIMPLEQ_INIT(&bb->parents);
442                         CIRCLEQ_INSERT_TAIL(&bblocksbbbbelem);
443                         XXXcount++;
444                         continue;
445                 }
446
447                 if (ip->type == IP_ASM)
448                         return 0;
449
450                 if (ip->type == IP_NODE) {
451                         switch(ip->ip_node->n_op) {
452                         case CBRANCH:
453                         case CALL:
454                         case UCALL:
455                         case FORTCALL:
456                         case UFORTCALL:
457                         case STCALL:
458                         case USTCALL:
459                         case GOTO:
460                         case RETURN:
461                                 /* Jumps, last in bblock. */
462                                 leader = 1;
463                                 break;
464
465                         case NAME:
466                         case ICON:
467                         case FCON:
468                         case REG:
469                         case OREG:
470                         case MOVE:
471                         case PLUS:
472                         case MINUS:
473                         case DIV:
474                         case MOD:
475                         case MUL:
476                         case AND:
477                         case OR:
478                         case ER:
479                         case LS:
480                         case COMPL:
481                         case INCR:
482                         case DECR:
483                         case UMUL:
484                         case UMINUS:
485                         case EQ:
486                         case NE:
487                         case LE:
488                         case GE:
489                         case GT:
490                         case ULE:
491                         case ULT:
492                         case UGE:
493                         case UGT:
494                         case ASSIGN:
495                         case FORCE:
496                         case FUNARG:
497                                 /* Not jumps, continue with bblock. */
498                                 break;
499
500                         default:
501                                 comperr("optim2:bblocks_build() %d",ip->ip_node->n_op ); 
502                                 break;
503                         }
504                 }
505
506                 bb->last = ip;
507         }
508 #ifdef PCC_DEBUG
509         printf("Basic blocks in func: %d\n"XXXcount);
510         printf("Label range in func: %d\n %d"high - low + 1low);
511 #endif
512
513         labinfo->low = low;
514         labinfo->size = high - low + 1;
515         labinfo->arr = tmpalloc(labinfo->size * sizeof(struct basicblock *));
516         for(i = 0i <= labinfo->sizei++) {
517                 labinfo->arr[i] = NULL;
518         }
519
520         /* Build the label table */
521         CIRCLEQ_FOREACH(bb, &bblocksbbelem) {
522                 if (bb->first->type == IP_DEFLAB) {
523                         labinfo->arr[bb->first->ip_lbl - low] = bb;
524                 }
525                 if (bb->first->type == IP_EPILOG) {
ragge
1.5
526                         labinfo->arr[bb->first->ip_lbl - low] = bb;
pj
1.4
527                 }
528         }
529
530         return 1;
531 }
532
533 /*
534  * Build the control flow graph.
535  */
536
537 void
538 cfg_build(struct labelinfo *labinfo)
539 {
540         /* Child and parent nodes */
541         struct cfgnode *cnode
542         struct cfgnode *pnode;
543         struct basicblock *bb;
544         
545         CIRCLEQ_FOREACH(bb, &bblocksbbelem) {
546
547                 if (bb->first->type == IP_EPILOG) {
548                         break;
549                 }
550
551                 cnode = tmpalloc(sizeof(struct cfgnode));
552                 pnode = tmpalloc(sizeof(struct cfgnode));
553                 pnode->bblock = bb;
554
555                 if ((bb->last->type == IP_NODE) && 
556                     (bb->last->ip_node->n_op == GOTO)) {
557                         if (bb->last->ip_node->n_left->n_lval - labinfo->low > 
558                             labinfo->size) {
559                                 comperr("Label out of range: %d, base %d"
560                                         bb->last->ip_node->n_left->n_lval
561                                         labinfo->low);
562                         }
563                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_left->n_lval - labinfo->low];
564                         SIMPLEQ_INSERT_TAIL(&cnode->bblock->parentspnodecfgelem);
565                         SIMPLEQ_INSERT_TAIL(&bb->childrencnodecfgelem);
566                         continue;
567                 }
568                 if ((bb->last->type == IP_NODE) && 
569                     (bb->last->ip_node->n_op == CBRANCH)) {
570                         if (bb->last->ip_node->n_right->n_lval - labinfo->low > 
571                             labinfo->size
572                                 comperr("Label out of range: %d"
573                                         bb->last->ip_node->n_left->n_lval);
574                         
575                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_right->n_lval - labinfo->low];
576                         SIMPLEQ_INSERT_TAIL(&cnode->bblock->parentspnodecfgelem);
577                         SIMPLEQ_INSERT_TAIL(&bb->childrencnodecfgelem);
578                         cnode = tmpalloc(sizeof(struct cfgnode));
579                         pnode = tmpalloc(sizeof(struct cfgnode));
580                         pnode->bblock = bb;
581                 }
582
583                 cnode->bblock = CIRCLEQ_NEXT(bbbbelem);
584                 SIMPLEQ_INSERT_TAIL(&cnode->bblock->parentspnodecfgelem);
585                 SIMPLEQ_INSERT_TAIL(&bb->childrencnodecfgelem);
586         }
587 }
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-30 17:59 +0200