simp.c (16387B)
1 #include "c.h" 2 #include <float.h> 3 4 5 #define foldcnst(TYPE,VAR,OP) \ 6 if (l->op == CNST+TYPE && r->op == CNST+TYPE) \ 7 return cnsttree(ty, l->u.v.VAR OP r->u.v.VAR) 8 #define commute(L,R) \ 9 if (generic(R->op) == CNST && generic(L->op) != CNST) \ 10 do { Tree t = L; L = R; R = t; } while(0) 11 #define xfoldcnst(TYPE,VAR,OP,FUNC)\ 12 if (l->op == CNST+TYPE && r->op == CNST+TYPE\ 13 && FUNC(l->u.v.VAR,r->u.v.VAR,\ 14 ty->u.sym->u.limits.min.VAR,\ 15 ty->u.sym->u.limits.max.VAR, needconst)) \ 16 return cnsttree(ty, l->u.v.VAR OP r->u.v.VAR) 17 #define xcvtcnst(FTYPE,SRC,DST,VAR,EXPR) \ 18 if (l->op == CNST+FTYPE) do {\ 19 if (!explicitCast\ 20 && ((SRC) < DST->u.sym->u.limits.min.VAR || (SRC) > DST->u.sym->u.limits.max.VAR))\ 21 warning("overflow in converting constant expression from `%t' to `%t'\n", l->type, DST);\ 22 if (needconst\ 23 || !((SRC) < DST->u.sym->u.limits.min.VAR || (SRC) > DST->u.sym->u.limits.max.VAR))\ 24 return cnsttree(ty, (EXPR)); } while(0) 25 #define identity(X,Y,TYPE,VAR,VAL) \ 26 if (X->op == CNST+TYPE && X->u.v.VAR == VAL) return Y 27 #define zerofield(OP,TYPE,VAR) \ 28 if (l->op == FIELD \ 29 && r->op == CNST+TYPE && r->u.v.VAR == 0)\ 30 return eqtree(OP, bittree(BAND, l->kids[0],\ 31 cnsttree(unsignedtype, \ 32 (unsigned long)fieldmask(l->u.field)<<fieldright(l->u.field))), r) 33 #define cfoldcnst(TYPE,VAR,OP) \ 34 if (l->op == CNST+TYPE && r->op == CNST+TYPE) \ 35 return cnsttree(inttype, (long)(l->u.v.VAR OP r->u.v.VAR)) 36 #define foldaddp(L,R,RTYPE,VAR) \ 37 if (L->op == CNST+P && R->op == CNST+RTYPE) { \ 38 Tree e = tree(CNST+P, ty, NULL, NULL);\ 39 e->u.v.p = (char *)L->u.v.p + R->u.v.VAR;\ 40 return e; } 41 #define ufoldcnst(TYPE,EXP) if (l->op == CNST+TYPE) return EXP 42 #define sfoldcnst(OP) \ 43 if (l->op == CNST+U && r->op == CNST+I \ 44 && r->u.v.i >= 0 && r->u.v.i < 8*l->type->size) \ 45 return cnsttree(ty, (unsigned long)(l->u.v.u OP r->u.v.i)) 46 #define geu(L,R,V) \ 47 if (R->op == CNST+U && R->u.v.u == 0) do { \ 48 warning("result of unsigned comparison is constant\n"); \ 49 return tree(RIGHT, inttype, root(L), cnsttree(inttype, (long)(V))); } while(0) 50 #define idempotent(OP) if (l->op == OP) return l->kids[0] 51 52 int needconst; 53 int explicitCast; 54 static int addi(long x, long y, long min, long max, int needconst) { 55 int cond = x == 0 || y == 0 56 || x < 0 && y < 0 && x >= min - y 57 || x < 0 && y > 0 58 || x > 0 && y < 0 59 || x > 0 && y > 0 && x <= max - y; 60 if (!cond && needconst) { 61 warning("overflow in constant expression\n"); 62 cond = 1; 63 } 64 return cond; 65 66 67 } 68 69 static int addd(double x, double y, double min, double max, int needconst) { 70 int cond = x == 0 || y == 0 71 || x < 0 && y < 0 && x >= min - y 72 || x < 0 && y > 0 73 || x > 0 && y < 0 74 || x > 0 && y > 0 && x <= max - y; 75 if (!cond && needconst) { 76 warning("overflow in constant expression\n"); 77 cond = 1; 78 } 79 return cond; 80 81 82 } 83 84 static Tree addrtree(Tree e, long n, Type ty) { 85 Symbol p = e->u.sym, q; 86 87 if (p->scope == GLOBAL 88 || p->sclass == STATIC || p->sclass == EXTERN) 89 NEW0(q, PERM); 90 else 91 NEW0(q, FUNC); 92 q->name = stringd(genlabel(1)); 93 q->sclass = p->sclass; 94 q->scope = p->scope; 95 assert(isptr(ty) || isarray(ty)); 96 q->type = isptr(ty) ? ty->type : ty; 97 q->temporary = p->temporary; 98 q->generated = p->generated; 99 q->addressed = p->addressed; 100 q->computed = 1; 101 q->defined = 1; 102 q->ref = 1; 103 if (p->scope == GLOBAL 104 || p->sclass == STATIC || p->sclass == EXTERN) { 105 if (p->sclass == AUTO) 106 q->sclass = STATIC; 107 (*IR->address)(q, p, n); 108 } else { 109 Code cp; 110 addlocal(p); 111 cp = code(Address); 112 cp->u.addr.sym = q; 113 cp->u.addr.base = p; 114 cp->u.addr.offset = n; 115 } 116 e = tree(e->op, ty, NULL, NULL); 117 e->u.sym = q; 118 return e; 119 } 120 121 /* div[id] - return 1 if min <= x/y <= max, 0 otherwise */ 122 static int divi(long x, long y, long min, long max, int needconst) { 123 int cond = y != 0 && !(x == min && y == -1); 124 if (!cond && needconst) { 125 warning("overflow in constant expression\n"); 126 cond = 1; 127 } 128 return cond; 129 130 131 } 132 133 static int divd(double x, double y, double min, double max, int needconst) { 134 int cond; 135 136 if (x < 0) x = -x; 137 if (y < 0) y = -y; 138 cond = y != 0 && !(y < 1 && x > max*y); 139 if (!cond && needconst) { 140 warning("overflow in constant expression\n"); 141 cond = 1; 142 } 143 return cond; 144 145 } 146 147 /* mul[id] - return 1 if min <= x*y <= max, 0 otherwise */ 148 static int muli(long x, long y, long min, long max, int needconst) { 149 int cond = x > -1 && x <= 1 || y > -1 && y <= 1 150 || x < 0 && y < 0 && -x <= max/-y 151 || x < 0 && y > 0 && x >= min/y 152 || x > 0 && y < 0 && y >= min/x 153 || x > 0 && y > 0 && x <= max/y; 154 if (!cond && needconst) { 155 warning("overflow in constant expression\n"); 156 cond = 1; 157 } 158 return cond; 159 160 161 } 162 163 static int muld(double x, double y, double min, double max, int needconst) { 164 int cond = x >= -1 && x <= 1 || y >= -1 && y <= 1 165 || x < 0 && y < 0 && -x <= max/-y 166 || x < 0 && y > 0 && x >= min/y 167 || x > 0 && y < 0 && y >= min/x 168 || x > 0 && y > 0 && x <= max/y; 169 if (!cond && needconst) { 170 warning("overflow in constant expression\n"); 171 cond = 1; 172 } 173 return cond; 174 175 176 } 177 /* sub[id] - return 1 if min <= x-y <= max, 0 otherwise */ 178 static int subi(long x, long y, long min, long max, int needconst) { 179 return addi(x, -y, min, max, needconst); 180 } 181 182 static int subd(double x, double y, double min, double max, int needconst) { 183 return addd(x, -y, min, max, needconst); 184 } 185 Tree constexpr(int tok) { 186 Tree p; 187 188 needconst++; 189 p = expr1(tok); 190 needconst--; 191 return p; 192 } 193 194 int intexpr(int tok, int n) { 195 Tree p = constexpr(tok); 196 197 needconst++; 198 if (p->op == CNST+I || p->op == CNST+U) 199 n = cast(p, inttype)->u.v.i; 200 else 201 error("integer expression must be constant\n"); 202 needconst--; 203 return n; 204 } 205 Tree simplify(int op, Type ty, Tree l, Tree r) { 206 int n; 207 Tree p; 208 209 if (optype(op) == 0) 210 op = mkop(op, ty); 211 switch (op) { 212 case ADD+U: 213 foldcnst(U,u,+); 214 commute(r,l); 215 identity(r,l,U,u,0); 216 break; 217 case ADD+I: 218 xfoldcnst(I,i,+,addi); 219 commute(r,l); 220 identity(r,l,I,i,0); 221 break; 222 case CVI+I: 223 xcvtcnst(I,l->u.v.i,ty,i,(long)extend(l->u.v.i,ty)); 224 break; 225 case CVU+I: 226 if (l->op == CNST+U) { 227 if (!explicitCast && l->u.v.u > ty->u.sym->u.limits.max.i) 228 warning("overflow in converting constant expression from `%t' to `%t'\n", l->type, ty); 229 if (needconst || !(l->u.v.u > ty->u.sym->u.limits.max.i)) 230 return cnsttree(ty, (long)extend(l->u.v.u,ty)); 231 } 232 break; 233 case CVP+U: 234 xcvtcnst(P,(unsigned long)l->u.v.p,ty,u,(unsigned long)l->u.v.p); 235 break; 236 case CVU+P: 237 xcvtcnst(U,(void*)l->u.v.u,ty,p,(void*)l->u.v.u); 238 break; 239 case CVP+P: 240 xcvtcnst(P,l->u.v.p,ty,p,l->u.v.p); 241 break; 242 case CVI+U: 243 xcvtcnst(I,l->u.v.i,ty,u,((unsigned long)l->u.v.i)&ones(8*ty->size)); 244 break; 245 case CVU+U: 246 xcvtcnst(U,l->u.v.u,ty,u,l->u.v.u&ones(8*ty->size)); 247 break; 248 249 case CVI+F: 250 xcvtcnst(I,l->u.v.i,ty,d,(long double)l->u.v.i); 251 case CVU+F: 252 xcvtcnst(U,l->u.v.u,ty,d,(long double)l->u.v.u); 253 break; 254 case CVF+I: 255 xcvtcnst(F,l->u.v.d,ty,i,(long)l->u.v.d); 256 break; 257 case CVF+F: { 258 float d; 259 if (l->op == CNST+F) 260 if (l->u.v.d < ty->u.sym->u.limits.min.d) 261 d = ty->u.sym->u.limits.min.d; 262 else if (l->u.v.d > ty->u.sym->u.limits.max.d) 263 d = ty->u.sym->u.limits.max.d; 264 else 265 d = l->u.v.d; 266 xcvtcnst(F,l->u.v.d,ty,d,(long double)d); 267 break; 268 } 269 case BAND+U: 270 foldcnst(U,u,&); 271 commute(r,l); 272 identity(r,l,U,u,ones(8*ty->size)); 273 if (r->op == CNST+U && r->u.v.u == 0) 274 return tree(RIGHT, ty, root(l), cnsttree(ty, 0UL)); 275 break; 276 case BAND+I: 277 foldcnst(I,i,&); 278 commute(r,l); 279 identity(r,l,I,i,ones(8*ty->size)); 280 if (r->op == CNST+I && r->u.v.u == 0) 281 return tree(RIGHT, ty, root(l), cnsttree(ty, 0L)); 282 break; 283 284 case MUL+U: 285 commute(l,r); 286 if (l->op == CNST+U && (n = ispow2(l->u.v.u)) != 0) 287 return simplify(LSH, ty, r, cnsttree(inttype, (long)n)); 288 foldcnst(U,u,*); 289 identity(r,l,U,u,1); 290 break; 291 case NE+I: 292 cfoldcnst(I,i,!=); 293 commute(r,l); 294 zerofield(NE,I,i); 295 break; 296 297 case EQ+I: 298 cfoldcnst(I,i,==); 299 commute(r,l); 300 zerofield(EQ,I,i); 301 break; 302 case ADD+P: 303 foldaddp(l,r,I,i); 304 foldaddp(l,r,U,u); 305 foldaddp(r,l,I,i); 306 foldaddp(r,l,U,u); 307 commute(r,l); 308 identity(r,retype(l,ty),I,i,0); 309 identity(r,retype(l,ty),U,u,0); 310 if (isaddrop(l->op) 311 && (r->op == CNST+I && r->u.v.i <= longtype->u.sym->u.limits.max.i 312 && r->u.v.i >= longtype->u.sym->u.limits.min.i 313 || r->op == CNST+U && r->u.v.u <= longtype->u.sym->u.limits.max.i)) 314 return addrtree(l, cast(r, longtype)->u.v.i, ty); 315 if (l->op == ADD+P && isaddrop(l->kids[1]->op) 316 && (r->op == CNST+I && r->u.v.i <= longtype->u.sym->u.limits.max.i 317 && r->u.v.i >= longtype->u.sym->u.limits.min.i 318 || r->op == CNST+U && r->u.v.u <= longtype->u.sym->u.limits.max.i)) 319 return simplify(ADD+P, ty, l->kids[0], 320 addrtree(l->kids[1], cast(r, longtype)->u.v.i, ty)); 321 if ((l->op == ADD+I || l->op == SUB+I) 322 && l->kids[1]->op == CNST+I && isaddrop(r->op)) 323 return simplify(ADD+P, ty, l->kids[0], 324 simplify(generic(l->op)+P, ty, r, l->kids[1])); 325 if (l->op == ADD+P && generic(l->kids[1]->op) == CNST 326 && generic(r->op) == CNST) 327 return simplify(ADD+P, ty, l->kids[0], 328 simplify(ADD, l->kids[1]->type, l->kids[1], r)); 329 if (l->op == ADD+I && generic(l->kids[1]->op) == CNST 330 && r->op == ADD+P && generic(r->kids[1]->op) == CNST) 331 return simplify(ADD+P, ty, l->kids[0], 332 simplify(ADD+P, ty, r->kids[0], 333 simplify(ADD, r->kids[1]->type, l->kids[1], r->kids[1]))); 334 if (l->op == RIGHT && l->kids[1]) 335 return tree(RIGHT, ty, l->kids[0], 336 simplify(ADD+P, ty, l->kids[1], r)); 337 else if (l->op == RIGHT && l->kids[0]) 338 return tree(RIGHT, ty, 339 simplify(ADD+P, ty, l->kids[0], r), NULL); 340 break; 341 342 case ADD+F: 343 xfoldcnst(F,d,+,addd); 344 commute(r,l); 345 break; 346 case AND+I: 347 op = AND; 348 ufoldcnst(I,l->u.v.i ? cond(r) : l); /* 0&&r => 0, 1&&r => r */ 349 break; 350 case OR+I: 351 op = OR; 352 /* 0||r => r, 1||r => 1 */ 353 ufoldcnst(I,l->u.v.i ? cnsttree(ty, 1L) : cond(r)); 354 break; 355 case BCOM+I: 356 ufoldcnst(I,cnsttree(ty, (long)extend((~l->u.v.i)&ones(8*ty->size), ty))); 357 idempotent(BCOM+U); 358 break; 359 case BCOM+U: 360 ufoldcnst(U,cnsttree(ty, (unsigned long)((~l->u.v.u)&ones(8*ty->size)))); 361 idempotent(BCOM+U); 362 break; 363 case BOR+U: 364 foldcnst(U,u,|); 365 commute(r,l); 366 identity(r,l,U,u,0); 367 break; 368 case BOR+I: 369 foldcnst(I,i,|); 370 commute(r,l); 371 identity(r,l,I,i,0); 372 break; 373 case BXOR+U: 374 foldcnst(U,u,^); 375 commute(r,l); 376 identity(r,l,U,u,0); 377 break; 378 case BXOR+I: 379 foldcnst(I,i,^); 380 commute(r,l); 381 identity(r,l,I,i,0); 382 break; 383 case DIV+F: 384 xfoldcnst(F,d,/,divd); 385 break; 386 case DIV+I: 387 identity(r,l,I,i,1); 388 if (r->op == CNST+I && r->u.v.i == 0 389 || l->op == CNST+I && l->u.v.i == ty->u.sym->u.limits.min.i 390 && r->op == CNST+I && r->u.v.i == -1) 391 break; 392 xfoldcnst(I,i,/,divi); 393 break; 394 case DIV+U: 395 identity(r,l,U,u,1); 396 if (r->op == CNST+U && r->u.v.u == 0) 397 break; 398 if (r->op == CNST+U && (n = ispow2(r->u.v.u)) != 0) 399 return simplify(RSH, ty, l, cnsttree(inttype, (long)n)); 400 foldcnst(U,u,/); 401 break; 402 case EQ+F: 403 cfoldcnst(F,d,==); 404 commute(r,l); 405 break; 406 case EQ+U: 407 cfoldcnst(U,u,==); 408 commute(r,l); 409 zerofield(EQ,U,u); 410 break; 411 case GE+F: cfoldcnst(F,d,>=); break; 412 case GE+I: cfoldcnst(I,i,>=); break; 413 case GE+U: 414 geu(l,r,1); /* l >= 0 => (l,1) */ 415 cfoldcnst(U,u,>=); 416 if (l->op == CNST+U && l->u.v.u == 0) /* 0 >= r => r == 0 */ 417 return eqtree(EQ, r, l); 418 break; 419 case GT+F: cfoldcnst(F,d, >); break; 420 case GT+I: cfoldcnst(I,i, >); break; 421 case GT+U: 422 geu(r,l,0); /* 0 > r => (r,0) */ 423 cfoldcnst(U,u, >); 424 if (r->op == CNST+U && r->u.v.u == 0) /* l > 0 => l != 0 */ 425 return eqtree(NE, l, r); 426 break; 427 case LE+F: cfoldcnst(F,d,<=); break; 428 case LE+I: cfoldcnst(I,i,<=); break; 429 case LE+U: 430 geu(r,l,1); /* 0 <= r => (r,1) */ 431 cfoldcnst(U,u,<=); 432 if (r->op == CNST+U && r->u.v.u == 0) /* l <= 0 => l == 0 */ 433 return eqtree(EQ, l, r); 434 break; 435 case LSH+I: 436 identity(r,l,I,i,0); 437 if (l->op == CNST+I && r->op == CNST+I 438 && r->u.v.i >= 0 && r->u.v.i < 8*l->type->size 439 && muli(l->u.v.i, 1<<r->u.v.i, ty->u.sym->u.limits.min.i, ty->u.sym->u.limits.max.i, needconst)) 440 return cnsttree(ty, (long)(l->u.v.i<<r->u.v.i)); 441 if (r->op == CNST+I && (r->u.v.i >= 8*ty->size || r->u.v.i < 0)) { 442 warning("shifting an `%t' by %d bits is undefined\n", ty, r->u.v.i); 443 break; 444 } 445 446 break; 447 case LSH+U: 448 identity(r,l,I,i,0); 449 sfoldcnst(<<); 450 if (r->op == CNST+I && (r->u.v.i >= 8*ty->size || r->u.v.i < 0)) { 451 warning("shifting an `%t' by %d bits is undefined\n", ty, r->u.v.i); 452 break; 453 } 454 455 break; 456 457 case LT+F: cfoldcnst(F,d, <); break; 458 case LT+I: cfoldcnst(I,i, <); break; 459 case LT+U: 460 geu(l,r,0); /* l < 0 => (l,0) */ 461 cfoldcnst(U,u, <); 462 if (l->op == CNST+U && l->u.v.u == 0) /* 0 < r => r != 0 */ 463 return eqtree(NE, r, l); 464 break; 465 case MOD+I: 466 if (r->op == CNST+I && r->u.v.i == 1) /* l%1 => (l,0) */ 467 return tree(RIGHT, ty, root(l), cnsttree(ty, 0L)); 468 if (r->op == CNST+I && r->u.v.i == 0 469 || l->op == CNST+I && l->u.v.i == ty->u.sym->u.limits.min.i 470 && r->op == CNST+I && r->u.v.i == -1) 471 break; 472 xfoldcnst(I,i,%,divi); 473 break; 474 case MOD+U: 475 if (r->op == CNST+U && ispow2(r->u.v.u)) /* l%2^n => l&(2^n-1) */ 476 return bittree(BAND, l, cnsttree(ty, r->u.v.u - 1)); 477 if (r->op == CNST+U && r->u.v.u == 0) 478 break; 479 foldcnst(U,u,%); 480 break; 481 case MUL+F: 482 xfoldcnst(F,d,*,muld); 483 commute(l,r); 484 break; 485 case MUL+I: 486 commute(l,r); 487 xfoldcnst(I,i,*,muli); 488 if (l->op == CNST+I && r->op == ADD+I && r->kids[1]->op == CNST+I) 489 /* c1*(x + c2) => c1*x + c1*c2 */ 490 return simplify(ADD, ty, simplify(MUL, ty, l, r->kids[0]), 491 simplify(MUL, ty, l, r->kids[1])); 492 if (l->op == CNST+I && r->op == SUB+I && r->kids[1]->op == CNST+I) 493 /* c1*(x - c2) => c1*x - c1*c2 */ 494 return simplify(SUB, ty, simplify(MUL, ty, l, r->kids[0]), 495 simplify(MUL, ty, l, r->kids[1])); 496 if (l->op == CNST+I && l->u.v.i > 0 && (n = ispow2(l->u.v.i)) != 0) 497 /* 2^n * r => r<<n */ 498 return simplify(LSH, ty, r, cnsttree(inttype, (long)n)); 499 identity(r,l,I,i,1); 500 break; 501 case NE+F: 502 cfoldcnst(F,d,!=); 503 commute(r,l); 504 break; 505 case NE+U: 506 cfoldcnst(U,u,!=); 507 commute(r,l); 508 zerofield(NE,U,u); 509 break; 510 case NEG+F: 511 ufoldcnst(F,cnsttree(ty, -l->u.v.d)); 512 idempotent(NEG+F); 513 break; 514 case NEG+I: 515 if (l->op == CNST+I) { 516 if (needconst && l->u.v.i == ty->u.sym->u.limits.min.i) 517 warning("overflow in constant expression\n"); 518 if (needconst || l->u.v.i != ty->u.sym->u.limits.min.i) 519 return cnsttree(ty, -l->u.v.i); 520 } 521 idempotent(NEG+I); 522 break; 523 case NOT+I: 524 op = NOT; 525 ufoldcnst(I,cnsttree(ty, !l->u.v.i)); 526 break; 527 case RSH+I: 528 identity(r,l,I,i,0); 529 if (l->op == CNST+I && r->op == CNST+I 530 && r->u.v.i >= 0 && r->u.v.i < 8*l->type->size) { 531 long n = l->u.v.i>>r->u.v.i; 532 if (l->u.v.i < 0) 533 n |= ~0UL<<(8*l->type->size - r->u.v.i); 534 return cnsttree(ty, n); 535 } 536 if (r->op == CNST+I && (r->u.v.i >= 8*ty->size || r->u.v.i < 0)) { 537 warning("shifting an `%t' by %d bits is undefined\n", ty, r->u.v.i); 538 break; 539 } 540 541 break; 542 case RSH+U: 543 identity(r,l,I,i,0); 544 sfoldcnst(>>); 545 if (r->op == CNST+I && (r->u.v.i >= 8*ty->size || r->u.v.i < 0)) { 546 warning("shifting an `%t' by %d bits is undefined\n", ty, r->u.v.i); 547 break; 548 } 549 550 break; 551 case SUB+F: 552 xfoldcnst(F,d,-,subd); 553 break; 554 case SUB+I: 555 xfoldcnst(I,i,-,subi); 556 identity(r,l,I,i,0); 557 break; 558 case SUB+U: 559 foldcnst(U,u,-); 560 identity(r,l,U,u,0); 561 break; 562 case SUB+P: 563 if (l->op == CNST+P && r->op == CNST+P) 564 return cnsttree(ty, (long)((char *)l->u.v.p - (char *)r->u.v.p)); 565 if (r->op == CNST+I || r->op == CNST+U) 566 return simplify(ADD, ty, l, 567 cnsttree(inttype, r->op == CNST+I ? -r->u.v.i : -(long)r->u.v.u)); 568 if (isaddrop(l->op) && r->op == ADD+I && r->kids[1]->op == CNST+I) 569 /* l - (x + c) => l-c - x */ 570 return simplify(SUB, ty, 571 simplify(SUB, ty, l, r->kids[1]), r->kids[0]); 572 break; 573 default:assert(0); 574 } 575 return tree(op, ty, l, r); 576 } 577 /* ispow2 - if u > 1 && u == 2^n, return n, otherwise return 0 */ 578 int ispow2(unsigned long u) { 579 int n; 580 581 if (u > 1 && (u&(u-1)) == 0) 582 for (n = 0; u; u >>= 1, n++) 583 if (u&1) 584 return n; 585 return 0; 586 } 587