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