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