1 /* Id: optim.c,v 1.61 2016/02/09 17:57:35 ragge Exp */
2 /* $NetBSD: optim.c,v 1.1.1.7 2016/02/09 20:28:50 plunky 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 NODE P1ND
40 #define nfree p1nfree
41 #define tfree p1tfree
42
43 # define SWAP(p,q) {sp=p; p=q; q=sp;}
44 # define RCON(p) (p->n_right->n_op==ICON)
45 # define RO(p) p->n_right->n_op
46 # define RV(p) getlval(p->n_right)
47 # define LCON(p) (p->n_left->n_op==ICON)
48 # define LO(p) p->n_left->n_op
49 # define LV(p) getlval(p->n_left)
50
51 /* remove left node */
52 static NODE *
zapleft(NODE * p)53 zapleft(NODE *p)
54 {
55 NODE *q;
56
57 q = p->n_left;
58 nfree(p->n_right);
59 nfree(p);
60 return q;
61 }
62
63 /*
64 * fortran function arguments
65 */
66 static NODE *
fortarg(NODE * p)67 fortarg(NODE *p)
68 {
69 if( p->n_op == CM ){
70 p->n_left = fortarg( p->n_left );
71 p->n_right = fortarg( p->n_right );
72 return(p);
73 }
74
75 while( ISPTR(p->n_type) ){
76 p = buildtree( UMUL, p, NIL );
77 }
78 return( optim(p) );
79 }
80
81 /* mapping relationals when the sides are reversed */
82 short revrel[] ={ EQ, NE, GE, GT, LE, LT, UGE, UGT, ULE, ULT };
83
84 /*
85 * local optimizations, most of which are probably
86 * machine independent
87 */
88 NODE *
optim(NODE * p)89 optim(NODE *p)
90 {
91 int o, ty;
92 NODE *sp, *q;
93 OFFSZ sz;
94 int i;
95
96 if (odebug) return(p);
97
98 ty = coptype(p->n_op);
99 if( ty == LTYPE ) return(p);
100
101 if( ty == BITYPE ) p->n_right = optim(p->n_right);
102 p->n_left = optim(p->n_left);
103
104 /* collect constants */
105 again: o = p->n_op;
106 switch(o){
107
108 case SCONV:
109 if (concast(p->n_left, p->n_type)) {
110 q = p->n_left;
111 nfree(p);
112 p = q;
113 break;
114 }
115 /* FALLTHROUGH */
116 case PCONV:
117 if (p->n_type != VOID)
118 p = clocal(p);
119 break;
120
121 case FORTCALL:
122 p->n_right = fortarg( p->n_right );
123 break;
124
125 case ADDROF:
126 if (LO(p) == TEMP)
127 break;
128 if( LO(p) != NAME ) cerror( "& error" );
129
130 if( !andable(p->n_left) && !statinit)
131 break;
132
133 LO(p) = ICON;
134
135 setuleft:
136 /* paint over the type of the left hand side with the type of the top */
137 p->n_left->n_type = p->n_type;
138 p->n_left->n_df = p->n_df;
139 p->n_left->n_ap = p->n_ap;
140 q = p->n_left;
141 nfree(p);
142 p = q;
143 break;
144
145 case NOT:
146 case UMINUS:
147 case COMPL:
148 if (LCON(p) && conval(p->n_left, o, p->n_left))
149 p = nfree(p);
150 break;
151
152 case UMUL:
153 /* Do not discard ADDROF TEMP's */
154 if (LO(p) == ADDROF && LO(p->n_left) != TEMP) {
155 q = p->n_left->n_left;
156 nfree(p->n_left);
157 nfree(p);
158 p = q;
159 break;
160 }
161 if( LO(p) != ICON ) break;
162 LO(p) = NAME;
163 goto setuleft;
164
165 case RS:
166 if (LCON(p) && RCON(p) && conval(p->n_left, o, p->n_right))
167 goto zapright;
168
169 sz = tsize(p->n_type, p->n_df, p->n_ap);
170
171 if (LO(p) == RS && RCON(p->n_left) && RCON(p) &&
172 (RV(p) + RV(p->n_left)) < sz) {
173 /* two right-shift by constants */
174 RV(p) += RV(p->n_left);
175 p->n_left = zapleft(p->n_left);
176 }
177 #if 0
178 else if (LO(p) == LS && RCON(p->n_left) && RCON(p)) {
179 RV(p) -= RV(p->n_left);
180 if (RV(p) < 0)
181 o = p->n_op = LS, RV(p) = -RV(p);
182 p->n_left = zapleft(p->n_left);
183 }
184 #endif
185 if (RO(p) == ICON) {
186 if (RV(p) < 0) {
187 RV(p) = -RV(p);
188 p->n_op = LS;
189 goto again;
190 }
191 #ifdef notyet /* must check for side effects, --a >> 32; */
192 if (RV(p) >= tsize(p->n_type, p->n_df, p->n_sue) &&
193 ISUNSIGNED(p->n_type)) { /* ignore signed shifts */
194 /* too many shifts */
195 tfree(p->n_left);
196 nfree(p->n_right);
197 p->n_op = ICON; p->n_lval = 0; p->n_sp = NULL;
198 } else
199 #endif
200 /* avoid larger shifts than type size */
201 if (RV(p) >= sz)
202 werror("shift larger than type");
203 if (RV(p) == 0)
204 p = zapleft(p);
205 }
206 break;
207
208 case LS:
209 if (LCON(p) && RCON(p) && conval(p->n_left, o, p->n_right))
210 goto zapright;
211
212 sz = tsize(p->n_type, p->n_df, p->n_ap);
213
214 if (LO(p) == LS && RCON(p->n_left) && RCON(p)) {
215 /* two left-shift by constants */
216 RV(p) += RV(p->n_left);
217 p->n_left = zapleft(p->n_left);
218 }
219 #if 0
220 else if (LO(p) == RS && RCON(p->n_left) && RCON(p)) {
221 RV(p) -= RV(p->n_left);
222 p->n_left = zapleft(p->n_left);
223 }
224 #endif
225 if (RO(p) == ICON) {
226 if (RV(p) < 0) {
227 RV(p) = -RV(p);
228 p->n_op = RS;
229 goto again;
230 }
231 #ifdef notyet /* must check for side effects */
232 if (RV(p) >= tsize(p->n_type, p->n_df, p->n_sue)) {
233 /* too many shifts */
234 tfree(p->n_left);
235 nfree(p->n_right);
236 p->n_op = ICON; p->n_lval = 0; p->n_sp = NULL;
237 } else
238 #endif
239 /* avoid larger shifts than type size */
240 if (RV(p) >= sz)
241 werror("shift larger than type");
242 if (RV(p) == 0)
243 p = zapleft(p);
244 }
245 break;
246
247 case QUEST:
248 if (!LCON(p))
249 break;
250 if (LV(p) == 0) {
251 q = p->n_right->n_right;
252 } else {
253 q = p->n_right->n_left;
254 p->n_right->n_left = p->n_right->n_right;
255 }
256 p->n_right->n_op = UMUL; /* for tfree() */
257 tfree(p);
258 p = q;
259 break;
260
261 case MINUS:
262 if (LCON(p) && RCON(p) && p->n_left->n_sp == p->n_right->n_sp) {
263 /* link-time constants, but both are the same */
264 /* solve it now by forgetting the symbols */
265 p->n_left->n_sp = p->n_right->n_sp = NULL;
266 }
267 if( !nncon(p->n_right) ) break;
268 RV(p) = -RV(p);
269 o = p->n_op = PLUS;
270 /* FALLTHROUGH */
271 case MUL:
272 /*
273 * Check for u=(x-y)+z; where all vars are pointers to
274 * the same struct. This has two advantages:
275 * 1: avoid a mul+div
276 * 2: even if not allowed, people may get surprised if this
277 * calculation do not give correct result if using
278 * unaligned structs.
279 */
280 if (o == MUL && p->n_type == INTPTR && RCON(p) &&
281 LO(p) == DIV && RCON(p->n_left) &&
282 RV(p) == RV(p->n_left) &&
283 LO(p->n_left) == MINUS) {
284 q = p->n_left->n_left;
285 if (q->n_left->n_type == PTR+STRTY &&
286 q->n_right->n_type == PTR+STRTY &&
287 strmemb(q->n_left->n_ap) ==
288 strmemb(q->n_right->n_ap)) {
289 p = zapleft(p);
290 p = zapleft(p);
291 }
292 }
293 /* FALLTHROUGH */
294 case PLUS:
295 case AND:
296 case OR:
297 case ER:
298 /* commutative ops; for now, just collect constants */
299 /* someday, do it right */
300 if( nncon(p->n_left) || ( LCON(p) && !RCON(p) ) )
301 SWAP( p->n_left, p->n_right );
302 /* make ops tower to the left, not the right */
303 if( RO(p) == o ){
304 SWAP(p->n_left, p->n_right);
305 #ifdef notdef
306 /* Yetch, this breaks type correctness in trees */
307 /* Code was probably written before types */
308 /* All we can do here is swap and pray */
309 NODE *t1, *t2, *t3;
310 t1 = p->n_left;
311 sp = p->n_right;
312 t2 = sp->n_left;
313 t3 = sp->n_right;
314 /* now, put together again */
315 p->n_left = sp;
316 sp->n_left = t1;
317 sp->n_right = t2;
318 sp->n_type = p->n_type;
319 p->n_right = t3;
320 #endif
321 }
322 if(o == PLUS && LO(p) == MINUS && RCON(p) && RCON(p->n_left) &&
323 conval(p->n_right, MINUS, p->n_left->n_right)){
324 zapleft:
325
326 q = p->n_left->n_left;
327 nfree(p->n_left->n_right);
328 nfree(p->n_left);
329 p->n_left = q;
330 }
331 if( RCON(p) && LO(p)==o && RCON(p->n_left) &&
332 conval( p->n_right, o, p->n_left->n_right ) ){
333 goto zapleft;
334 }
335 else if( LCON(p) && RCON(p) && conval( p->n_left, o, p->n_right ) ){
336 zapright:
337 nfree(p->n_right);
338 q = makety(p->n_left, p->n_type, p->n_qual,
339 p->n_df, p->n_ap);
340 nfree(p);
341 p = clocal(q);
342 break;
343 }
344
345 /* change muls to shifts */
346
347 if( o == MUL && nncon(p->n_right) && (i=ispow2(RV(p)))>=0){
348 if( i == 0 ) { /* multiplication by 1 */
349 goto zapright;
350 }
351 o = p->n_op = LS;
352 p->n_right->n_type = INT;
353 p->n_right->n_df = NULL;
354 RV(p) = i;
355 }
356
357 /* change +'s of negative consts back to - */
358 if( o==PLUS && nncon(p->n_right) && RV(p)<0 ){
359 RV(p) = -RV(p);
360 o = p->n_op = MINUS;
361 }
362
363 /* remove ops with RHS 0 */
364 if ((o == PLUS || o == MINUS || o == OR || o == ER) &&
365 nncon(p->n_right) && RV(p) == 0) {
366 goto zapright;
367 }
368 break;
369
370 case DIV:
371 if( nncon( p->n_right ) && getlval(p->n_right) == 1 )
372 goto zapright;
373 if (LCON(p) && RCON(p) && conval(p->n_left, DIV, p->n_right))
374 goto zapright;
375 if (RCON(p) && ISUNSIGNED(p->n_type) && (i=ispow2(RV(p))) > 0) {
376 p->n_op = RS;
377 RV(p) = i;
378 q = p->n_right;
379 if(tsize(q->n_type, q->n_df, q->n_ap) > SZINT)
380 p->n_right = makety(q, INT, 0, 0, 0);
381
382 break;
383 }
384 break;
385
386 case MOD:
387 if (RCON(p) && ISUNSIGNED(p->n_type) && ispow2(RV(p)) > 0) {
388 p->n_op = AND;
389 RV(p) = RV(p) -1;
390 break;
391 }
392 break;
393
394 case EQ:
395 case NE:
396 case LT:
397 case LE:
398 case GT:
399 case GE:
400 case ULT:
401 case ULE:
402 case UGT:
403 case UGE:
404 if (LCON(p) && RCON(p) &&
405 !ISPTR(p->n_left->n_type) && !ISPTR(p->n_right->n_type)) {
406 /* Do constant evaluation */
407 q = p->n_left;
408 if (conval(q, o, p->n_right)) {
409 nfree(p->n_right);
410 nfree(p);
411 p = q;
412 break;
413 }
414 }
415
416 if( !LCON(p) ) break;
417
418 /* exchange operands */
419
420 sp = p->n_left;
421 p->n_left = p->n_right;
422 p->n_right = sp;
423 p->n_op = revrel[p->n_op - EQ ];
424 break;
425
426 case CBRANCH:
427 if (LCON(p)) {
428 if (LV(p) == 0) {
429 tfree(p);
430 p = bcon(0);
431 } else {
432 tfree(p->n_left);
433 p->n_left = p->n_right;
434 p->n_op = GOTO;
435 }
436 }
437 break;
438
439
440 #ifdef notyet
441 case ASSIGN:
442 /* Simple test to avoid two branches */
443 if (RO(p) != NE)
444 break;
445 q = p->n_right;
446 if (RCON(q) && RV(q) == 0 && LO(q) == AND &&
447 RCON(q->n_left) && (i = ispow2(RV(q->n_left))) &&
448 q->n_left->n_type == INT) {
449 q->n_op = RS;
450 RV(q) = i;
451 }
452 break;
453 #endif
454
455 case ANDAND:
456 if (!nncon(p->n_left))
457 break;
458 if (LV(p) == 0) { /* right not evaluated */
459 p1walkf(p, putjops, 0);
460 p1tfree(p);
461 p = bcon(0);
462 } else {
463 q = p->n_right;
464 nfree(nfree(p));
465 p = cast(q, INT, 0);
466 }
467 break;
468 case OROR:
469 if (!nncon(p->n_left))
470 break;
471 if (LV(p) != 0) { /* right not evaluated */
472 p1walkf(p, putjops, 0);
473 p1tfree(p);
474 p = bcon(1);
475 } else {
476 q = p->n_right;
477 nfree(nfree(p));
478 p = cast(q, INT, 0);
479 }
480 break;
481 }
482
483 return(p);
484 }
485
486 int
ispow2(CONSZ c)487 ispow2(CONSZ c)
488 {
489 int i;
490 if( c <= 0 || (c&(c-1)) ) return(-1);
491 for( i=0; c>1; ++i) c >>= 1;
492 return(i);
493 }
494
495 int
nncon(NODE * p)496 nncon(NODE *p)
497 {
498 /* is p a constant without a name */
499 return( p->n_op == ICON && p->n_sp == NULL );
500 }
501