source: mainline/uspace/app/pcc/mip/match.c@ 7ab6fc2

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 7ab6fc2 was a7de7182, checked in by Jiří Zárevúcky <zarevucky.jiri@…>, 14 years ago

Added pcc source tree (contents of pcc-1.0.0.tgz)
  • Property mode set to 100644
File size: 27.4 KB
RevLine 
[a7de7182]1/* $Id: match.c,v 1.93 2010/06/04 05:58:31 ragge Exp $ */
2/*
3 * Copyright (c) 2003 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/*
30 * Copyright(C) Caldera International Inc. 2001-2002. All rights reserved.
31 *
32 * Redistribution and use in source and binary forms, with or without
33 * modification, are permitted provided that the following conditions
34 * are met:
35 *
36 * Redistributions of source code and documentation must retain the above
37 * copyright notice, this list of conditions and the following disclaimer.
38 * Redistributions in binary form must reproduce the above copyright
39 * notice, this list of conditionsand the following disclaimer in the
40 * documentation and/or other materials provided with the distribution.
41 * All advertising materials mentioning features or use of this software
42 * must display the following acknowledgement:
43 * This product includes software developed or owned by Caldera
44 * International, Inc.
45 * Neither the name of Caldera International, Inc. nor the names of other
46 * contributors may be used to endorse or promote products derived from
47 * this software without specific prior written permission.
48 *
49 * USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA
50 * INTERNATIONAL, INC. AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR
51 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
52 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
53 * DISCLAIMED. IN NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE LIABLE
54 * FOR ANY DIRECT, INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
55 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
56 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
57 * HOWEVER CAUSED AND ON ANY THEORY OFLIABILITY, WHETHER IN CONTRACT,
58 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
59 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
60 * POSSIBILITY OF SUCH DAMAGE.
61 */
62
63#include "pass2.h"
64
65#ifdef HAVE_STRINGS_H
66#include <strings.h>
67#endif
68
69void setclass(int tmp, int class);
70int getclass(int tmp);
71
72int s2debug;
73
74extern char *ltyp[], *rtyp[];
75
76static char *srtyp[] = { "SRNOPE", "SRDIR", "SROREG", "SRREG" };
77
78/*
79 * return true if shape is appropriate for the node p
80 * side effect for SFLD is to set up fldsz, etc
81 *
82 * Return values:
83 * SRNOPE Cannot match this shape.
84 * SRDIR Direct match, may or may not traverse down.
85 * SRREG Will match if put in a regster XXX - kill this?
86 */
87int
88tshape(NODE *p, int shape)
89{
90 int o, mask;
91
92 o = p->n_op;
93
94#ifdef PCC_DEBUG
95 if (s2debug)
96 printf("tshape(%p, %s) op = %s\n", p, prcook(shape), opst[o]);
97#endif
98
99 if (shape & SPECIAL) {
100
101 switch (shape) {
102 case SZERO:
103 case SONE:
104 case SMONE:
105 case SSCON:
106 case SCCON:
107 if (o != ICON || p->n_name[0])
108 return SRNOPE;
109 if (p->n_lval == 0 && shape == SZERO)
110 return SRDIR;
111 if (p->n_lval == 1 && shape == SONE)
112 return SRDIR;
113 if (p->n_lval == -1 && shape == SMONE)
114 return SRDIR;
115 if (p->n_lval > -257 && p->n_lval < 256 &&
116 shape == SCCON)
117 return SRDIR;
118 if (p->n_lval > -32769 && p->n_lval < 32768 &&
119 shape == SSCON)
120 return SRDIR;
121 return SRNOPE;
122
123 case SSOREG: /* non-indexed OREG */
124 if (o == OREG && !R2TEST(p->n_rval))
125 return SRDIR;
126 return SRNOPE;
127
128 default:
129 return (special(p, shape));
130 }
131 }
132
133 if (shape & SANY)
134 return SRDIR;
135
136 if ((shape&INTEMP) && shtemp(p)) /* XXX remove? */
137 return SRDIR;
138
139 if ((shape&SWADD) && (o==NAME||o==OREG))
140 if (BYTEOFF(p->n_lval))
141 return SRNOPE;
142
143 switch (o) {
144
145 case NAME:
146 if (shape & SNAME)
147 return SRDIR;
148 break;
149
150 case ICON:
151 case FCON:
152 if (shape & SCON)
153 return SRDIR;
154 break;
155
156 case FLD:
157 if (shape & SFLD)
158 return flshape(p->n_left);
159 break;
160
161 case CCODES:
162 if (shape & SCC)
163 return SRDIR;
164 break;
165
166 case REG:
167 case TEMP:
168 mask = PCLASS(p);
169 if (shape & mask)
170 return SRDIR;
171 break;
172
173 case OREG:
174 if (shape & SOREG)
175 return SRDIR;
176 break;
177
178 case UMUL:
179#if 0
180 if (shumul(p->n_left) & shape)
181 return SROREG; /* Calls offstar to traverse down */
182 break;
183#else
184 return shumul(p->n_left, shape);
185#endif
186
187 }
188 return SRNOPE;
189}
190
191/*
192 * does the type t match tword
193 */
194int
195ttype(TWORD t, int tword)
196{
197 if (tword & TANY)
198 return(1);
199
200#ifdef PCC_DEBUG
201 if (t2debug)
202 printf("ttype(%o, %o)\n", t, tword);
203#endif
204 if (ISPTR(t) && ISFTN(DECREF(t)) && (tword & TFTN)) {
205 /* For funny function pointers */
206 return 1;
207 }
208 if (ISPTR(t) && (tword&TPTRTO)) {
209 do {
210 t = DECREF(t);
211 } while (ISARY(t));
212 /* arrays that are left are usually only
213 * in structure references...
214 */
215 return (ttype(t, tword&(~TPTRTO)));
216 }
217 if (t != BTYPE(t))
218 return (tword & TPOINT); /* TPOINT means not simple! */
219 if (tword & TPTRTO)
220 return(0);
221
222 switch (t) {
223 case CHAR:
224 return( tword & TCHAR );
225 case SHORT:
226 return( tword & TSHORT );
227 case STRTY:
228 case UNIONTY:
229 return( tword & TSTRUCT );
230 case INT:
231 return( tword & TINT );
232 case UNSIGNED:
233 return( tword & TUNSIGNED );
234 case USHORT:
235 return( tword & TUSHORT );
236 case UCHAR:
237 return( tword & TUCHAR );
238 case ULONG:
239 return( tword & TULONG );
240 case LONG:
241 return( tword & TLONG );
242 case LONGLONG:
243 return( tword & TLONGLONG );
244 case ULONGLONG:
245 return( tword & TULONGLONG );
246 case FLOAT:
247 return( tword & TFLOAT );
248 case DOUBLE:
249 return( tword & TDOUBLE );
250 case LDOUBLE:
251 return( tword & TLDOUBLE );
252 }
253
254 return(0);
255}
256
257#define FLDSZ(x) UPKFSZ(x)
258#ifdef RTOLBYTES
259#define FLDSHF(x) UPKFOFF(x)
260#else
261#define FLDSHF(x) (SZINT - FLDSZ(x) - UPKFOFF(x))
262#endif
263
264/*
265 * generate code by interpreting table entry
266 */
267void
268expand(NODE *p, int cookie, char *cp)
269{
270 CONSZ val;
271
272#if 0
273 printf("expand\n");
274 fwalk(p, e2print, 0);
275#endif
276
277 for( ; *cp; ++cp ){
278 switch( *cp ){
279
280 default:
281 PUTCHAR( *cp );
282 continue; /* this is the usual case... */
283
284 case 'Z': /* special machine dependent operations */
285 zzzcode( p, *++cp );
286 continue;
287
288 case 'F': /* this line deleted if FOREFF is active */
289 if (cookie & FOREFF) {
290 while (*cp && *cp != '\n')
291 cp++;
292 if (*cp == 0)
293 return;
294 }
295 continue;
296
297 case 'S': /* field size */
298 if (fldexpand(p, cookie, &cp))
299 continue;
300 printf("%d", FLDSZ(p->n_rval));
301 continue;
302
303 case 'H': /* field shift */
304 if (fldexpand(p, cookie, &cp))
305 continue;
306 printf("%d", FLDSHF(p->n_rval));
307 continue;
308
309 case 'M': /* field mask */
310 case 'N': /* complement of field mask */
311 if (fldexpand(p, cookie, &cp))
312 continue;
313 val = 1;
314 val <<= FLDSZ(p->n_rval);
315 --val;
316 val <<= FLDSHF(p->n_rval);
317 adrcon( *cp=='M' ? val : ~val );
318 continue;
319
320 case 'L': /* output special label field */
321 if (*++cp == 'C')
322 printf(LABFMT, p->n_label);
323 else
324 printf(LABFMT, (int)getlr(p,*cp)->n_lval);
325 continue;
326
327 case 'O': /* opcode string */
328#ifdef FINDMOPS
329 if (p->n_op == ASSIGN)
330 hopcode(*++cp, p->n_right->n_op);
331 else
332#endif
333 hopcode( *++cp, p->n_op );
334 continue;
335
336 case 'B': /* byte offset in word */
337 val = getlr(p,*++cp)->n_lval;
338 val = BYTEOFF(val);
339 printf( CONFMT, val );
340 continue;
341
342 case 'C': /* for constant value only */
343 conput(stdout, getlr( p, *++cp ) );
344 continue;
345
346 case 'I': /* in instruction */
347 insput( getlr( p, *++cp ) );
348 continue;
349
350 case 'A': /* address of */
351 adrput(stdout, getlr( p, *++cp ) );
352 continue;
353
354 case 'U': /* for upper half of address, only */
355 upput(getlr(p, *++cp), SZLONG);
356 continue;
357
358 }
359
360 }
361
362 }
363
364NODE resc[4];
365
366NODE *
367getlr(NODE *p, int c)
368{
369 NODE *q;
370
371 /* return the pointer to the left or right side of p, or p itself,
372 depending on the optype of p */
373
374 switch (c) {
375
376 case '1':
377 case '2':
378 case '3':
379 case 'D':
380 if (c == 'D')
381 c = 0;
382 else
383 c -= '0';
384 q = &resc[c];
385 q->n_op = REG;
386 q->n_type = p->n_type; /* XXX should be correct type */
387 q->n_rval = DECRA(p->n_reg, c);
388 q->n_su = p->n_su;
389 return q;
390
391 case 'L':
392 return( optype( p->n_op ) == LTYPE ? p : p->n_left );
393
394 case 'R':
395 return( optype( p->n_op ) != BITYPE ? p : p->n_right );
396
397 }
398 cerror( "bad getlr: %c", c );
399 /* NOTREACHED */
400 return NULL;
401}
402
403#ifdef PCC_DEBUG
404#define F2DEBUG(x) if (f2debug) printf x
405#define F2WALK(x) if (f2debug) fwalk(x, e2print, 0)
406#else
407#define F2DEBUG(x)
408#define F2WALK(x)
409#endif
410
411/*
412 * Convert a node to REG or OREG.
413 * Shape is register class where we want the result.
414 * Returns register class if register nodes.
415 * If w is: (should be shapes)
416 * - SRREG - result in register, call geninsn().
417 * - SROREG - create OREG; call offstar().
418 * - 0 - clear su, walk down.
419 */
420static int
421swmatch(NODE *p, int shape, int w)
422{
423 int rv = 0;
424
425 F2DEBUG(("swmatch: p=%p, shape=%s, w=%s\n", p, prcook(shape), srtyp[w]));
426
427 switch (w) {
428 case SRREG:
429 rv = geninsn(p, shape);
430 break;
431
432 case SROREG:
433 /* should be here only if op == UMUL */
434 if (p->n_op != UMUL && p->n_op != FLD)
435 comperr("swmatch %p", p);
436 if (p->n_op == FLD) {
437 offstar(p->n_left->n_left, shape);
438 p->n_left->n_su = 0;
439 } else
440 offstar(p->n_left, shape);
441 p->n_su = 0;
442 rv = ffs(shape)-1;
443 break;
444
445 case 0:
446 if (optype(p->n_op) == BITYPE)
447 swmatch(p->n_right, 0, 0);
448 if (optype(p->n_op) != LTYPE)
449 swmatch(p->n_left, 0, 0);
450 p->n_su = 0;
451 }
452 return rv;
453
454}
455
456/*
457 * Help routines for find*() functions.
458 * If the node will be a REG node and it will be rewritten in the
459 * instruction, ask for it to be put in a register.
460 */
461static int
462chcheck(NODE *p, int shape, int rew)
463{
464 int sh, sha;
465
466 sha = shape;
467 if (shape & SPECIAL)
468 shape = 0;
469
470 switch ((sh = tshape(p, sha))) {
471 case SRNOPE:
472 if (shape & INREGS)
473 sh = SRREG;
474 break;
475
476 case SROREG:
477 case SRDIR:
478 if (rew == 0)
479 break;
480 if (shape & INREGS)
481 sh = SRREG;
482 else
483 sh = SRNOPE;
484 break;
485 }
486 return sh;
487}
488
489/*
490 * Check how to walk further down.
491 * Merge with swmatch()?
492 * sh - shape for return value (register class).
493 * p - node (for this leg)
494 * shape - given shape for this leg
495 * cookie - cookie given for parent node
496 * rew -
497 * go - switch key for traversing down
498 * returns register class.
499 */
500static int
501shswitch(int sh, NODE *p, int shape, int cookie, int rew, int go)
502{
503 int lsh;
504
505 F2DEBUG(("shswitch: p=%p, shape=%s, ", p, prcook(shape)));
506 F2DEBUG(("cookie=%s, rew=0x%x, go=%s\n", prcook(cookie), rew, srtyp[go]));
507
508 switch (go) {
509 case SRDIR: /* direct match, just clear su */
510 (void)swmatch(p, 0, 0);
511 break;
512
513 case SROREG: /* call offstar to prepare for OREG conversion */
514 (void)swmatch(p, shape, SROREG);
515 break;
516
517 case SRREG: /* call geninsn() to get value into register */
518 lsh = shape & (FORCC | INREGS);
519 if (rew && cookie != FOREFF)
520 lsh &= (cookie & (FORCC | INREGS));
521 lsh = swmatch(p, lsh, SRREG);
522 if (rew)
523 sh = lsh;
524 break;
525 }
526 return sh;
527}
528
529/*
530 * Find the best instruction to evaluate the given tree.
531 * Best is to match both subnodes directly, second-best is if
532 * subnodes must be evaluated into OREGs, thereafter if nodes
533 * must be put into registers.
534 * Whether 2-op instructions or 3-op is preferred is depending on in
535 * which order they are found in the table.
536 * mtchno is set to the count of regs needed for its legs.
537 */
538int
539findops(NODE *p, int cookie)
540{
541 extern int *qtable[];
542 struct optab *q, *qq = NULL;
543 int i, shl, shr, *ixp, sh;
544 int lvl = 10, idx = 0, gol = 0, gor = 0;
545 NODE *l, *r;
546
547 F2DEBUG(("findops node %p (%s)\n", p, prcook(cookie)));
548 F2WALK(p);
549
550 ixp = qtable[p->n_op];
551 l = getlr(p, 'L');
552 r = getlr(p, 'R');
553 for (i = 0; ixp[i] >= 0; i++) {
554 q = &table[ixp[i]];
555
556 F2DEBUG(("findop: ixp %d str %s\n", ixp[i], q->cstring));
557 if (!acceptable(q)) /* target-dependent filter */
558 continue;
559
560 if (ttype(l->n_type, q->ltype) == 0 ||
561 ttype(r->n_type, q->rtype) == 0)
562 continue; /* Types must be correct */
563
564 if ((cookie & q->visit) == 0)
565 continue; /* must get a result */
566
567 F2DEBUG(("findop got types\n"));
568
569 if ((shl = chcheck(l, q->lshape, q->rewrite & RLEFT)) == SRNOPE)
570 continue;
571
572 F2DEBUG(("findop lshape %s\n", srtyp[shl]));
573 F2WALK(l);
574
575 if ((shr = chcheck(r, q->rshape, q->rewrite & RRIGHT)) == SRNOPE)
576 continue;
577
578 F2DEBUG(("findop rshape %s\n", srtyp[shr]));
579 F2WALK(r);
580
581 /* Help register assignment after SSA by preferring */
582 /* 2-op insns instead of 3-ops */
583 if (xssaflag && (q->rewrite & RLEFT) == 0 && shl == SRDIR)
584 shl = SRREG;
585
586 if (q->needs & REWRITE)
587 break; /* Done here */
588
589 if (lvl <= (shl + shr))
590 continue;
591 lvl = shl + shr;
592 qq = q;
593 idx = ixp[i];
594 gol = shl;
595 gor = shr;
596 }
597 if (lvl == 10) {
598 F2DEBUG(("findops failed\n"));
599 if (setbin(p))
600 return FRETRY;
601 return FFAIL;
602 }
603
604 F2DEBUG(("findops entry %d(%s,%s)\n", idx, srtyp[gol], srtyp[gor]));
605
606 sh = -1;
607
608#ifdef mach_pdp11
609 if (cookie == FORCC && p->n_op != AND) /* XXX - fix */
610 cookie = INREGS;
611#else
612 if (cookie == FORCC)
613 cookie = INREGS;
614#endif
615
616 sh = shswitch(sh, p->n_left, qq->lshape, cookie,
617 qq->rewrite & RLEFT, gol);
618 sh = shswitch(sh, p->n_right, qq->rshape, cookie,
619 qq->rewrite & RRIGHT, gor);
620
621 if (sh == -1) {
622 if (cookie == FOREFF || cookie == FORCC)
623 sh = 0;
624 else
625 sh = ffs(cookie & qq->visit & INREGS)-1;
626 }
627 F2DEBUG(("findops: node %p sh %d (%s)\n", p, sh, prcook(1 << sh)));
628 p->n_su = MKIDX(idx, 0);
629 SCLASS(p->n_su, sh);
630 return sh;
631}
632
633/*
634 * Find the best relation op for matching the two trees it has.
635 * This is a sub-version of the function findops() above.
636 * The instruction with the lowest grading is emitted.
637 *
638 * Level assignment for priority:
639 * left right prio
640 * - - -
641 * direct direct 1
642 * direct OREG 2 # make oreg
643 * OREG direct 2 # make oreg
644 * OREG OREG 2 # make both oreg
645 * direct REG 3 # put in reg
646 * OREG REG 3 # put in reg, make oreg
647 * REG direct 3 # put in reg
648 * REG OREG 3 # put in reg, make oreg
649 * REG REG 4 # put both in reg
650 */
651int
652relops(NODE *p)
653{
654 extern int *qtable[];
655 struct optab *q;
656 int i, shl = 0, shr = 0;
657 NODE *l, *r;
658 int *ixp, idx = 0;
659 int lvl = 10, gol = 0, gor = 0;
660
661 F2DEBUG(("relops tree:\n"));
662 F2WALK(p);
663
664 l = getlr(p, 'L');
665 r = getlr(p, 'R');
666 ixp = qtable[p->n_op];
667 for (i = 0; ixp[i] >= 0; i++) {
668 q = &table[ixp[i]];
669
670 F2DEBUG(("relops: ixp %d\n", ixp[i]));
671 if (!acceptable(q)) /* target-dependent filter */
672 continue;
673
674 if (ttype(l->n_type, q->ltype) == 0 ||
675 ttype(r->n_type, q->rtype) == 0)
676 continue; /* Types must be correct */
677
678 F2DEBUG(("relops got types\n"));
679 if ((shl = chcheck(l, q->lshape, 0)) == SRNOPE)
680 continue;
681 F2DEBUG(("relops lshape %d\n", shl));
682 F2WALK(p);
683 if ((shr = chcheck(r, q->rshape, 0)) == SRNOPE)
684 continue;
685 F2DEBUG(("relops rshape %d\n", shr));
686 F2WALK(p);
687 if (q->needs & REWRITE)
688 break; /* Done here */
689
690 if (lvl <= (shl + shr))
691 continue;
692 lvl = shl + shr;
693 idx = ixp[i];
694 gol = shl;
695 gor = shr;
696 }
697 if (lvl == 10) {
698 F2DEBUG(("relops failed\n"));
699 if (setbin(p))
700 return FRETRY;
701 return FFAIL;
702 }
703 F2DEBUG(("relops entry %d(%s %s)\n", idx, srtyp[gol], srtyp[gor]));
704
705 q = &table[idx];
706
707 (void)shswitch(-1, p->n_left, q->lshape, FORCC,
708 q->rewrite & RLEFT, gol);
709
710 (void)shswitch(-1, p->n_right, q->rshape, FORCC,
711 q->rewrite & RRIGHT, gor);
712
713 F2DEBUG(("relops: node %p\n", p));
714 p->n_su = MKIDX(idx, 0);
715 SCLASS(p->n_su, CLASSA); /* XXX */
716 return 0;
717}
718
719/*
720 * Find a matching assign op.
721 *
722 * Level assignment for priority:
723 * left right prio
724 * - - -
725 * direct direct 1
726 * direct REG 2
727 * direct OREG 3
728 * OREG direct 4
729 * OREG REG 5
730 * OREG OREG 6
731 */
732int
733findasg(NODE *p, int cookie)
734{
735 extern int *qtable[];
736 struct optab *q;
737 int i, sh, shl, shr, lvl = 10;
738 NODE *l, *r;
739 int *ixp;
740 struct optab *qq = NULL; /* XXX gcc */
741 int idx = 0, gol = 0, gor = 0;
742
743 shl = shr = 0;
744
745 F2DEBUG(("findasg tree: %s\n", prcook(cookie)));
746 F2WALK(p);
747
748 ixp = qtable[p->n_op];
749 l = getlr(p, 'L');
750 r = getlr(p, 'R');
751 for (i = 0; ixp[i] >= 0; i++) {
752 q = &table[ixp[i]];
753
754 F2DEBUG(("findasg: ixp %d\n", ixp[i]));
755 if (!acceptable(q)) /* target-dependent filter */
756 continue;
757
758 if (ttype(l->n_type, q->ltype) == 0 ||
759 ttype(r->n_type, q->rtype) == 0)
760 continue; /* Types must be correct */
761
762 if ((cookie & q->visit) == 0)
763 continue; /* must get a result */
764
765 F2DEBUG(("findasg got types\n"));
766#ifdef mach_pdp11 /* XXX - check for other targets too */
767 if (p->n_op == STASG && ISPTR(l->n_type)) {
768 /* Accept lvalue to be in register */
769 /* if struct assignment is given a pointer */
770 if ((shl = chcheck(l, q->lshape,
771 q->rewrite & RLEFT)) == SRNOPE)
772 continue;
773 } else
774#endif
775 {
776 if ((shl = tshape(l, q->lshape)) == SRNOPE)
777 continue;
778 if (shl == SRREG)
779 continue;
780 }
781
782 F2DEBUG(("findasg lshape %d\n", shl));
783 F2WALK(l);
784
785 if ((shr = chcheck(r, q->rshape, q->rewrite & RRIGHT)) == SRNOPE)
786 continue;
787
788 F2DEBUG(("findasg rshape %d\n", shr));
789 F2WALK(r);
790 if (q->needs & REWRITE)
791 break; /* Done here */
792
793 if (lvl <= (shl + shr))
794 continue;
795
796 lvl = shl + shr;
797 qq = q;
798 idx = ixp[i];
799 gol = shl;
800 gor = shr;
801 }
802
803 if (lvl == 10) {
804 F2DEBUG(("findasg failed\n"));
805 if (setasg(p, cookie))
806 return FRETRY;
807 return FFAIL;
808 }
809 F2DEBUG(("findasg entry %d(%s,%s)\n", idx, srtyp[gol], srtyp[gor]));
810
811 sh = -1;
812 sh = shswitch(sh, p->n_left, qq->lshape, cookie,
813 qq->rewrite & RLEFT, gol);
814
815 sh = shswitch(sh, p->n_right, qq->rshape, cookie,
816 qq->rewrite & RRIGHT, gor);
817
818#ifdef mach_pdp11 /* XXX all targets? */
819 lvl = 0;
820 if (cookie == FOREFF)
821 lvl = RVEFF, sh = 0;
822 else if (cookie == FORCC)
823 lvl = RVCC, sh = 0;
824 else if (sh == -1) {
825 sh = ffs(cookie & qq->visit & INREGS)-1;
826#ifdef PCC_DEBUG
827 if (sh == -1)
828 comperr("findasg bad shape");
829#endif
830 SCLASS(lvl,sh);
831 } else
832 SCLASS(lvl,sh);
833 p->n_su = MKIDX(idx, lvl);
834#else
835 if (sh == -1) {
836 if (cookie == FOREFF)
837 sh = 0;
838 else
839 sh = ffs(cookie & qq->visit & INREGS)-1;
840 }
841 F2DEBUG(("findasg: node %p class %d\n", p, sh));
842
843 p->n_su = MKIDX(idx, 0);
844 SCLASS(p->n_su, sh);
845#endif /* mach_pdp11 */
846#ifdef FINDMOPS
847 p->n_flags &= ~1;
848#endif
849 return sh;
850}
851
852/*
853 * Search for an UMUL table entry that can turn an indirect node into
854 * a move from an OREG.
855 */
856int
857findumul(NODE *p, int cookie)
858{
859 extern int *qtable[];
860 struct optab *q = NULL; /* XXX gcc */
861 int i, shl = 0, shr = 0, sh;
862 int *ixp;
863
864 F2DEBUG(("findumul p %p (%s)\n", p, prcook(cookie)));
865 F2WALK(p);
866
867 ixp = qtable[p->n_op];
868 for (i = 0; ixp[i] >= 0; i++) {
869 q = &table[ixp[i]];
870
871 F2DEBUG(("findumul: ixp %d\n", ixp[i]));
872 if (!acceptable(q)) /* target-dependent filter */
873 continue;
874
875 if ((q->visit & cookie) == 0)
876 continue; /* wrong registers */
877
878 if (ttype(p->n_type, q->rtype) == 0)
879 continue; /* Types must be correct */
880
881
882 F2DEBUG(("findumul got types, rshape %s\n", prcook(q->rshape)));
883 /*
884 * Try to create an OREG of the node.
885 * Fake left even though it's right node,
886 * to be sure of conversion if going down left.
887 */
888 if ((shl = chcheck(p, q->rshape, 0)) == SRNOPE)
889 continue;
890
891 shr = 0;
892
893 if (q->needs & REWRITE)
894 break; /* Done here */
895
896 F2DEBUG(("findumul got shape %s\n", srtyp[shl]));
897
898 break; /* XXX search better matches */
899 }
900 if (ixp[i] < 0) {
901 F2DEBUG(("findumul failed\n"));
902 if (setuni(p, cookie))
903 return FRETRY;
904 return FFAIL;
905 }
906 F2DEBUG(("findumul entry %d(%s %s)\n", ixp[i], srtyp[shl], srtyp[shr]));
907
908 sh = shswitch(-1, p, q->rshape, cookie, q->rewrite & RLEFT, shl);
909 if (sh == -1)
910 sh = ffs(cookie & q->visit & INREGS)-1;
911
912 F2DEBUG(("findumul: node %p (%s)\n", p, prcook(1 << sh)));
913 p->n_su = MKIDX(ixp[i], 0);
914 SCLASS(p->n_su, sh);
915 return sh;
916}
917
918/*
919 * Find a leaf type node that puts the value into a register.
920 */
921int
922findleaf(NODE *p, int cookie)
923{
924 extern int *qtable[];
925 struct optab *q = NULL; /* XXX gcc */
926 int i, sh;
927 int *ixp;
928
929 F2DEBUG(("findleaf p %p (%s)\n", p, prcook(cookie)));
930 F2WALK(p);
931
932 ixp = qtable[p->n_op];
933 for (i = 0; ixp[i] >= 0; i++) {
934 q = &table[ixp[i]];
935
936 F2DEBUG(("findleaf: ixp %d\n", ixp[i]));
937 if (!acceptable(q)) /* target-dependent filter */
938 continue;
939 if ((q->visit & cookie) == 0)
940 continue; /* wrong registers */
941
942 if (ttype(p->n_type, q->rtype) == 0 ||
943 ttype(p->n_type, q->ltype) == 0)
944 continue; /* Types must be correct */
945
946 F2DEBUG(("findleaf got types, rshape %s\n", prcook(q->rshape)));
947
948 if (chcheck(p, q->rshape, 0) != SRDIR)
949 continue;
950
951 if (q->needs & REWRITE)
952 break; /* Done here */
953
954 break;
955 }
956 if (ixp[i] < 0) {
957 F2DEBUG(("findleaf failed\n"));
958 if (setuni(p, cookie))
959 return FRETRY;
960 return FFAIL;
961 }
962 F2DEBUG(("findleaf entry %d\n", ixp[i]));
963
964 sh = ffs(cookie & q->visit & INREGS)-1;
965 F2DEBUG(("findleaf: node %p (%s)\n", p, prcook(1 << sh)));
966 p->n_su = MKIDX(ixp[i], 0);
967 SCLASS(p->n_su, sh);
968 return sh;
969}
970
971/*
972 * Find a UNARY op that satisfy the needs.
973 * For now, the destination is always a register.
974 * Both source and dest types must match, but only source (left)
975 * shape is of interest.
976 */
977int
978finduni(NODE *p, int cookie)
979{
980 extern int *qtable[];
981 struct optab *q;
982 NODE *l, *r;
983 int i, shl = 0, num = 4;
984 int *ixp, idx = 0;
985 int sh;
986
987 F2DEBUG(("finduni tree: %s\n", prcook(cookie)));
988 F2WALK(p);
989
990 l = getlr(p, 'L');
991 if (p->n_op == CALL || p->n_op == FORTCALL || p->n_op == STCALL)
992 r = p;
993 else
994 r = getlr(p, 'R');
995 ixp = qtable[p->n_op];
996 for (i = 0; ixp[i] >= 0; i++) {
997 q = &table[ixp[i]];
998
999 F2DEBUG(("finduni: ixp %d\n", ixp[i]));
1000 if (!acceptable(q)) /* target-dependent filter */
1001 continue;
1002
1003 if (ttype(l->n_type, q->ltype) == 0)
1004 continue; /* Type must be correct */
1005
1006 F2DEBUG(("finduni got left type\n"));
1007 if (ttype(r->n_type, q->rtype) == 0)
1008 continue; /* Type must be correct */
1009
1010 F2DEBUG(("finduni got types\n"));
1011 if ((shl = chcheck(l, q->lshape, q->rewrite & RLEFT)) == SRNOPE)
1012 continue;
1013
1014 F2DEBUG(("finduni got shapes %d\n", shl));
1015
1016 if ((cookie & q->visit) == 0) /* check correct return value */
1017 continue; /* XXX - should check needs */
1018
1019 /* avoid clobbering of longlived regs */
1020 /* let register allocator coalesce */
1021 if ((q->rewrite & RLEFT) && (shl == SRDIR) /* && isreg(l) */)
1022 shl = SRREG;
1023
1024 F2DEBUG(("finduni got cookie\n"));
1025 if (q->needs & REWRITE)
1026 break; /* Done here */
1027
1028 if (shl >= num)
1029 continue;
1030 num = shl;
1031 idx = ixp[i];
1032
1033 if (shl == SRDIR)
1034 break;
1035 }
1036
1037 if (num == 4) {
1038 F2DEBUG(("finduni failed\n"));
1039 } else
1040 F2DEBUG(("finduni entry %d(%s)\n", idx, srtyp[num]));
1041
1042 if (num == 4) {
1043 if (setuni(p, cookie))
1044 return FRETRY;
1045 return FFAIL;
1046 }
1047 q = &table[idx];
1048
1049 sh = shswitch(-1, p->n_left, q->lshape, cookie,
1050 q->rewrite & RLEFT, num);
1051 if (sh == -1)
1052 sh = ffs(cookie & q->visit & INREGS)-1;
1053 if (sh == -1)
1054 sh = 0;
1055
1056 F2DEBUG(("finduni: node %p (%s)\n", p, prcook(1 << sh)));
1057 p->n_su = MKIDX(idx, 0);
1058 SCLASS(p->n_su, sh);
1059 return sh;
1060}
1061
1062#ifdef FINDMOPS
1063/*
1064 * Try to find constructs like "a = a + 1;" and match them together
1065 * with instructions like "incl a" or "addl $1,a".
1066 *
1067 * Level assignment for priority:
1068 * left right prio
1069 * - - -
1070 * direct direct 1
1071 * direct REG 2
1072 * direct OREG 3
1073 * OREG direct 4
1074 * OREG REG 5
1075 * OREG OREG 6
1076 */
1077int
1078findmops(NODE *p, int cookie)
1079{
1080 extern int *qtable[];
1081 struct optab *q;
1082 int i, sh, shl, shr, lvl = 10;
1083 NODE *l, *r;
1084 int *ixp;
1085 struct optab *qq = NULL; /* XXX gcc */
1086 int idx = 0, gol = 0, gor = 0;
1087
1088 shl = shr = 0;
1089
1090 F2DEBUG(("findmops tree: %s\n", prcook(cookie)));
1091 F2WALK(p);
1092
1093 l = getlr(p, 'L');
1094 r = getlr(p, 'R');
1095 /* See if this is a usable tree to work with */
1096 /* Currently only check for leaves */
1097 if (optype(r->n_op) != BITYPE || treecmp(l, r->n_left) == 0)
1098 return FFAIL;
1099
1100 F2DEBUG(("findmops is useable\n"));
1101
1102 /* We can try to find a match. Use right op */
1103 ixp = qtable[r->n_op];
1104 l = getlr(r, 'L');
1105 r = getlr(r, 'R');
1106
1107 for (i = 0; ixp[i] >= 0; i++) {
1108 q = &table[ixp[i]];
1109
1110 F2DEBUG(("findmops: ixp %d\n", ixp[i]));
1111 if (!acceptable(q)) /* target-dependent filter */
1112 continue;
1113
1114 if (ttype(l->n_type, q->ltype) == 0 ||
1115 ttype(r->n_type, q->rtype) == 0)
1116 continue; /* Types must be correct */
1117
1118 F2DEBUG(("findmops got types\n"));
1119
1120 switch (cookie) {
1121 case FOREFF:
1122 if ((q->visit & FOREFF) == 0)
1123 continue; /* Not only for side effects */
1124 break;
1125 case FORCC:
1126 if ((q->visit & FORCC) == 0)
1127 continue; /* Not only for side effects */
1128 break;
1129 default:
1130 if ((cookie & q->visit) == 0)
1131 continue; /* Won't match requested shape */
1132 if (((cookie & INREGS & q->lshape) == 0) || !isreg(l))
1133 continue; /* Bad return register */
1134 break;
1135 }
1136 F2DEBUG(("findmops cookie\n"));
1137
1138 /*
1139 * left shape must match left node.
1140 */
1141 if ((shl = tshape(l, q->lshape)) != SRDIR && (shl != SROREG))
1142 continue;
1143
1144 F2DEBUG(("findmops lshape %s\n", srtyp[shl]));
1145 F2WALK(l);
1146
1147 if ((shr = chcheck(r, q->rshape, 0)) == SRNOPE)
1148 continue;
1149
1150 F2DEBUG(("findmops rshape %s\n", srtyp[shr]));
1151
1152 /*
1153 * Only allow RLEFT. XXX
1154 */
1155 if ((q->rewrite & (RLEFT|RRIGHT)) != RLEFT)
1156 continue;
1157
1158 F2DEBUG(("rewrite OK\n"));
1159
1160 F2WALK(r);
1161 if (q->needs & REWRITE)
1162 break; /* Done here */
1163
1164 if (lvl <= (shl + shr))
1165 continue;
1166
1167 lvl = shl + shr;
1168 qq = q;
1169 idx = ixp[i];
1170 gol = shl;
1171 gor = shr;
1172 }
1173
1174 if (lvl == 10)
1175 return FFAIL;
1176 F2DEBUG(("findmops entry %d(%s,%s)\n", idx, srtyp[gol], srtyp[gor]));
1177
1178 /*
1179 * Now we're here and have a match. left is semi-direct and
1180 * right may be anything.
1181 */
1182
1183 sh = -1;
1184 sh = shswitch(sh, p->n_left, qq->lshape, cookie,
1185 qq->rewrite & RLEFT, gol);
1186 sh = shswitch(sh, r, qq->rshape, cookie, 0, gor);
1187
1188 if (sh == -1) {
1189 if (cookie & (FOREFF|FORCC))
1190 sh = 0;
1191 else
1192 sh = ffs(cookie & qq->visit & INREGS)-1;
1193 }
1194 F2DEBUG(("findmops done: node %p class %d\n", p, sh));
1195
1196 /* Trickery: Set table index on assign to op instead */
1197 /* gencode() will remove useless nodes */
1198 p->n_su = MKIDX(idx, 0);
1199 p->n_flags |= 1; /* XXX tell gencode to reduce the right tree */
1200 SCLASS(p->n_su, sh);
1201
1202 return sh;
1203}
1204
1205/*
1206 * Compare two trees; return 1 if equal and 0 if not.
1207 */
1208int
1209treecmp(NODE *p1, NODE *p2)
1210{
1211 if (p1->n_op != p2->n_op)
1212 return 0;
1213
1214 switch (p1->n_op) {
1215 case SCONV:
1216 case UMUL:
1217 return treecmp(p1->n_left, p2->n_left);
1218
1219 case OREG:
1220 if (p1->n_lval != p2->n_lval || p1->n_rval != p2->n_rval)
1221 return 0;
1222 break;
1223
1224 case NAME:
1225 case ICON:
1226 if (strcmp(p1->n_name, p2->n_name))
1227 return 0;
1228 /* FALLTHROUGH */
1229 if (p1->n_lval != p2->n_lval)
1230 return 0;
1231 break;
1232
1233 case TEMP:
1234#ifdef notyet
1235 /* SSA will put assignment in separate register */
1236 /* Help out by accepting different regs here */
1237 if (xssaflag)
1238 break;
1239#endif
1240 case REG:
1241 if (p1->n_rval != p2->n_rval)
1242 return 0;
1243 break;
1244 case LS:
1245 case RS:
1246 case PLUS:
1247 case MINUS:
1248 case MUL:
1249 case DIV:
1250 if (treecmp(p1->n_left, p2->n_left) == 0 ||
1251 treecmp(p1->n_right, p2->n_right) == 0)
1252 return 0;
1253 break;
1254
1255 default:
1256 return 0;
1257 }
1258 return 1;
1259}
1260#endif
Note: See TracBrowser for help on using the repository browser.