Context Navigation

source: mainline/uspace/app/pcc/mip/match.c@ 12831ed7

Visit:

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export

Last change on this file since 12831ed7 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

Line
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
69	void setclass(int tmp, int class);
70	int getclass(int tmp);
71
72	int s2debug;
73
74	extern char ltyp[], rtyp[];
75
76	static 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	*/
87	int
88	tshape(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	*/
194	int
195	ttype(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	*/
267	void
268	expand(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
364	NODE resc[4];
365
366	NODE *
367	getlr(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	*/
420	static int
421	swmatch(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	*/
461	static int
462	chcheck(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	*/
500	static int
501	shswitch(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	*/
538	int
539	findops(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	*/
651	int
652	relops(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	*/
732	int
733	findasg(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	*/
856	int
857	findumul(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	*/
921	int
922	findleaf(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	*/
977	int
978	finduni(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	*/
1077	int
1078	findmops(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	*/
1208	int
1209	treecmp(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.

Download in other formats: