1/*	Id: optim.c,v 1.49 2012/03/22 18:51:40 plunky Exp 	*/
2/*	$NetBSD: optim.c,v 1.1.1.4.4.1 2012/04/03 16:36:21 riz Exp $	*/
3/*
4 * Copyright(C) Caldera International Inc. 2001-2002. 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 *
10 * Redistributions of source code and documentation must retain the above
11 * copyright notice, this list of conditions and the following disclaimer.
12 * Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditionsand the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * All advertising materials mentioning features or use of this software
16 * must display the following acknowledgement:
17 * 	This product includes software developed or owned by Caldera
18 *	International, Inc.
19 * Neither the name of Caldera International, Inc. nor the names of other
20 * contributors may be used to endorse or promote products derived from
21 * this software without specific prior written permission.
22 *
23 * USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA
24 * INTERNATIONAL, INC. AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR
25 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
26 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
27 * DISCLAIMED.  IN NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE LIABLE
28 * FOR ANY DIRECT, INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OFLIABILITY, WHETHER IN CONTRACT,
32 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
33 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
34 * POSSIBILITY OF SUCH DAMAGE.
35 */
36
37# include "pass1.h"
38
39# define SWAP(p,q) {sp=p; p=q; q=sp;}
40# define RCON(p) (p->n_right->n_op==ICON)
41# define RO(p) p->n_right->n_op
42# define RV(p) p->n_right->n_lval
43# define LCON(p) (p->n_left->n_op==ICON)
44# define LO(p) p->n_left->n_op
45# define LV(p) p->n_left->n_lval
46
47/* remove left node */
48static NODE *
49zapleft(NODE *p)
50{
51	NODE *q;
52
53	q = p->n_left;
54	nfree(p->n_right);
55	nfree(p);
56	return q;
57}
58
59/*
60 * fortran function arguments
61 */
62static NODE *
63fortarg(NODE *p)
64{
65	if( p->n_op == CM ){
66		p->n_left = fortarg( p->n_left );
67		p->n_right = fortarg( p->n_right );
68		return(p);
69	}
70
71	while( ISPTR(p->n_type) ){
72		p = buildtree( UMUL, p, NIL );
73	}
74	return( optim(p) );
75}
76
77	/* mapping relationals when the sides are reversed */
78short revrel[] ={ EQ, NE, GE, GT, LE, LT, UGE, UGT, ULE, ULT };
79
80/*
81 * local optimizations, most of which are probably
82 * machine independent
83 */
84NODE *
85optim(NODE *p)
86{
87	int o, ty;
88	NODE *sp, *q;
89	OFFSZ sz;
90	int i;
91
92	if (odebug) return(p);
93
94	ty = coptype(p->n_op);
95	if( ty == LTYPE ) return(p);
96
97	if( ty == BITYPE ) p->n_right = optim(p->n_right);
98	p->n_left = optim(p->n_left);
99
100	/* collect constants */
101again:	o = p->n_op;
102	switch(o){
103
104	case SCONV:
105		if (concast(p->n_left, p->n_type)) {
106			q = p->n_left;
107			nfree(p);
108			p = q;
109			break;
110		}
111		/* FALLTHROUGH */
112	case PCONV:
113		if (p->n_type != VOID)
114			p = clocal(p);
115		break;
116
117	case FORTCALL:
118		p->n_right = fortarg( p->n_right );
119		break;
120
121	case ADDROF:
122		if (LO(p) == TEMP)
123			break;
124		if( LO(p) != NAME ) cerror( "& error" );
125
126		if( !andable(p->n_left) && !statinit)
127			break;
128
129		LO(p) = ICON;
130
131		setuleft:
132		/* paint over the type of the left hand side with the type of the top */
133		p->n_left->n_type = p->n_type;
134		p->n_left->n_df = p->n_df;
135		p->n_left->n_ap = p->n_ap;
136		q = p->n_left;
137		nfree(p);
138		p = q;
139		break;
140
141	case NOT:
142	case UMINUS:
143	case COMPL:
144		if (LCON(p) && conval(p->n_left, o, p->n_left))
145			p = nfree(p);
146		break;
147
148	case UMUL:
149		/* Do not discard ADDROF TEMP's */
150		if (LO(p) == ADDROF && LO(p->n_left) != TEMP) {
151			q = p->n_left->n_left;
152			nfree(p->n_left);
153			nfree(p);
154			p = q;
155			break;
156		}
157		if( LO(p) != ICON ) break;
158		LO(p) = NAME;
159		goto setuleft;
160
161	case RS:
162		if (LCON(p) && RCON(p) && conval(p->n_left, o, p->n_right))
163			goto zapright;
164
165		sz = tsize(p->n_type, p->n_df, p->n_ap);
166
167		if (LO(p) == RS && RCON(p->n_left) && RCON(p) &&
168		    (RV(p) + RV(p->n_left)) < sz) {
169			/* two right-shift  by constants */
170			RV(p) += RV(p->n_left);
171			p->n_left = zapleft(p->n_left);
172		}
173#if 0
174		  else if (LO(p) == LS && RCON(p->n_left) && RCON(p)) {
175			RV(p) -= RV(p->n_left);
176			if (RV(p) < 0)
177				o = p->n_op = LS, RV(p) = -RV(p);
178			p->n_left = zapleft(p->n_left);
179		}
180#endif
181		if (RO(p) == ICON) {
182			if (RV(p) < 0) {
183				RV(p) = -RV(p);
184				p->n_op = LS;
185				goto again;
186			}
187#ifdef notyet /* must check for side effects, --a >> 32; */
188			if (RV(p) >= tsize(p->n_type, p->n_df, p->n_sue) &&
189			    ISUNSIGNED(p->n_type)) { /* ignore signed shifts */
190				/* too many shifts */
191				tfree(p->n_left);
192				nfree(p->n_right);
193				p->n_op = ICON; p->n_lval = 0; p->n_sp = NULL;
194			} else
195#endif
196			/* avoid larger shifts than type size */
197			if (RV(p) >= sz) {
198				RV(p) = RV(p) % sz;
199				werror("shift larger than type");
200			}
201			if (RV(p) == 0)
202				p = zapleft(p);
203		}
204		break;
205
206	case LS:
207		if (LCON(p) && RCON(p) && conval(p->n_left, o, p->n_right))
208			goto zapright;
209
210		sz = tsize(p->n_type, p->n_df, p->n_ap);
211
212		if (LO(p) == LS && RCON(p->n_left) && RCON(p)) {
213			/* two left-shift  by constants */
214			RV(p) += RV(p->n_left);
215			p->n_left = zapleft(p->n_left);
216		}
217#if 0
218		  else if (LO(p) == RS && RCON(p->n_left) && RCON(p)) {
219			RV(p) -= RV(p->n_left);
220			p->n_left = zapleft(p->n_left);
221		}
222#endif
223		if (RO(p) == ICON) {
224			if (RV(p) < 0) {
225				RV(p) = -RV(p);
226				p->n_op = RS;
227				goto again;
228			}
229#ifdef notyet /* must check for side effects */
230			if (RV(p) >= tsize(p->n_type, p->n_df, p->n_sue)) {
231				/* too many shifts */
232				tfree(p->n_left);
233				nfree(p->n_right);
234				p->n_op = ICON; p->n_lval = 0; p->n_sp = NULL;
235			} else
236#endif
237			/* avoid larger shifts than type size */
238			if (RV(p) >= sz) {
239				RV(p) = RV(p) % sz;
240				werror("shift larger than type");
241			}
242			if (RV(p) == 0)
243				p = zapleft(p);
244		}
245		break;
246
247	case MINUS:
248		if (LCON(p) && RCON(p) && p->n_left->n_sp == p->n_right->n_sp) {
249			/* link-time constants, but both are the same */
250			/* solve it now by forgetting the symbols */
251			p->n_left->n_sp = p->n_right->n_sp = NULL;
252		}
253		if( !nncon(p->n_right) ) break;
254		RV(p) = -RV(p);
255		o = p->n_op = PLUS;
256
257	case MUL:
258		/*
259		 * Check for u=(x-y)+z; where all vars are pointers to
260		 * the same struct. This has two advantages:
261		 * 1: avoid a mul+div
262		 * 2: even if not allowed, people may get surprised if this
263		 *    calculation do not give correct result if using
264		 *    unaligned structs.
265		 */
266		if (p->n_type == INTPTR && RCON(p) &&
267		    LO(p) == DIV && RCON(p->n_left) &&
268		    RV(p) == RV(p->n_left) &&
269		    LO(p->n_left) == MINUS) {
270			q = p->n_left->n_left;
271			if (q->n_left->n_type == PTR+STRTY &&
272			    q->n_right->n_type == PTR+STRTY &&
273			    strmemb(q->n_left->n_ap) ==
274			    strmemb(q->n_right->n_ap)) {
275				p = zapleft(p);
276				p = zapleft(p);
277			}
278		}
279		/* FALLTHROUGH */
280	case PLUS:
281	case AND:
282	case OR:
283	case ER:
284		/* commutative ops; for now, just collect constants */
285		/* someday, do it right */
286		if( nncon(p->n_left) || ( LCON(p) && !RCON(p) ) )
287			SWAP( p->n_left, p->n_right );
288		/* make ops tower to the left, not the right */
289		if( RO(p) == o ){
290			NODE *t1, *t2, *t3;
291			t1 = p->n_left;
292			sp = p->n_right;
293			t2 = sp->n_left;
294			t3 = sp->n_right;
295			/* now, put together again */
296			p->n_left = sp;
297			sp->n_left = t1;
298			sp->n_right = t2;
299			sp->n_type = p->n_type;
300			p->n_right = t3;
301			}
302		if(o == PLUS && LO(p) == MINUS && RCON(p) && RCON(p->n_left) &&
303		   conval(p->n_right, MINUS, p->n_left->n_right)){
304			zapleft:
305
306			q = p->n_left->n_left;
307			nfree(p->n_left->n_right);
308			nfree(p->n_left);
309			p->n_left = q;
310		}
311		if( RCON(p) && LO(p)==o && RCON(p->n_left) &&
312		    conval( p->n_right, o, p->n_left->n_right ) ){
313			goto zapleft;
314			}
315		else if( LCON(p) && RCON(p) && conval( p->n_left, o, p->n_right ) ){
316			zapright:
317			nfree(p->n_right);
318			q = makety(p->n_left, p->n_type, p->n_qual,
319			    p->n_df, p->n_ap);
320			nfree(p);
321			p = clocal(q);
322			break;
323			}
324
325		/* change muls to shifts */
326
327		if( o == MUL && nncon(p->n_right) && (i=ispow2(RV(p)))>=0){
328			if( i == 0 ) { /* multiplication by 1 */
329				goto zapright;
330				}
331			o = p->n_op = LS;
332			p->n_right->n_type = INT;
333			p->n_right->n_df = NULL;
334			RV(p) = i;
335			}
336
337		/* change +'s of negative consts back to - */
338		if( o==PLUS && nncon(p->n_right) && RV(p)<0 ){
339			RV(p) = -RV(p);
340			o = p->n_op = MINUS;
341			}
342
343		/* remove ops with RHS 0 */
344		if ((o == PLUS || o == MINUS || o == OR || o == ER) &&
345		    nncon(p->n_right) && RV(p) == 0) {
346			goto zapright;
347		}
348		break;
349
350	case DIV:
351		if( nncon( p->n_right ) && p->n_right->n_lval == 1 )
352			goto zapright;
353		if (LCON(p) && RCON(p) && conval(p->n_left, DIV, p->n_right))
354			goto zapright;
355		if (RCON(p) && ISUNSIGNED(p->n_type) && (i=ispow2(RV(p))) > 0) {
356			p->n_op = RS;
357			RV(p) = i;
358			q = p->n_right;
359			if(tsize(q->n_type, q->n_df, q->n_ap) > SZINT)
360				p->n_right = makety(q, INT, 0, 0, 0);
361
362			break;
363		}
364		break;
365
366	case MOD:
367		if (RCON(p) && ISUNSIGNED(p->n_type) && ispow2(RV(p)) > 0) {
368			p->n_op = AND;
369			RV(p) = RV(p) -1;
370			break;
371		}
372		break;
373
374	case EQ:
375	case NE:
376	case LT:
377	case LE:
378	case GT:
379	case GE:
380	case ULT:
381	case ULE:
382	case UGT:
383	case UGE:
384		if( !LCON(p) ) break;
385
386		/* exchange operands */
387
388		sp = p->n_left;
389		p->n_left = p->n_right;
390		p->n_right = sp;
391		p->n_op = revrel[p->n_op - EQ ];
392		break;
393
394#ifdef notyet
395	case ASSIGN:
396		/* Simple test to avoid two branches */
397		if (RO(p) != NE)
398			break;
399		q = p->n_right;
400		if (RCON(q) && RV(q) == 0 && LO(q) == AND &&
401		    RCON(q->n_left) && (i = ispow2(RV(q->n_left))) &&
402		    q->n_left->n_type == INT) {
403			q->n_op = RS;
404			RV(q) = i;
405		}
406		break;
407#endif
408	}
409
410	return(p);
411	}
412
413int
414ispow2(CONSZ c)
415{
416	int i;
417	if( c <= 0 || (c&(c-1)) ) return(-1);
418	for( i=0; c>1; ++i) c >>= 1;
419	return(i);
420}
421
422int
423nncon( p ) NODE *p; {
424	/* is p a constant without a name */
425	return( p->n_op == ICON && p->n_sp == NULL );
426	}
427