fold.c (12812B)
1 static char sccsid[] = "@(#) ./cc1/fold.c"; 2 #include <assert.h> 3 #include <stdlib.h> 4 5 #include "../inc/scc.h" 6 #include "cc1.h" 7 8 9 TUINT 10 ones(int nbytes) 11 { 12 TUINT v; 13 14 for (v = 0; nbytes--; v |= 255) 15 v <<= 8; 16 return v; 17 } 18 19 static int 20 addi(TINT l, TINT r, Type *tp) 21 { 22 struct limits *lim = getlimits(tp); 23 TINT max = lim->max.i, min = -lim->min.i; 24 25 if (l < 0 && r < 0 && l >= min - r || 26 l == 0 || 27 r == 0 || 28 l < 0 && r > 0 || 29 l > 0 && r < 0 || 30 l > 0 && r > 0 && l <= max - r) { 31 return 1; 32 } 33 warn("overflow in constant expression"); 34 return 0; 35 } 36 37 static int 38 addf(TFLOAT l, TFLOAT r, Type *tp) 39 { 40 struct limits *lim = getlimits(tp); 41 TFLOAT max = lim->max.f, min = lim->min.f; 42 43 if (l < 0 && r < 0 && l >= min - r || 44 l == 0 || 45 r == 0 || 46 l < 0 && r > 0 || 47 l > 0 && r < 0 || 48 l > 0 && r > 0 && l <= max - r) { 49 return 1; 50 } 51 warn("overflow in constant expression"); 52 return 0; 53 } 54 55 static int 56 subi(TINT l, TINT r, Type *tp) 57 { 58 return addi(l, -r, tp); 59 } 60 61 static int 62 subf(TFLOAT l, TFLOAT r, Type *tp) 63 { 64 return addf(l, -r, tp); 65 } 66 67 static int 68 muli(TINT l, TINT r, Type *tp) 69 { 70 struct limits *lim = getlimits(tp); 71 TINT max = lim->max.i, min = -lim->min.i; 72 73 if (l > -1 && l <= 1 || 74 r > -1 && r <= 1 || 75 l < 0 && r < 0 && -l <= max/-r || 76 l < 0 && r > 0 && l >= min/r || 77 l > 0 && r < 0 && r >= min/l || 78 l > 0 && r > 0 && l <= max/r) { 79 return 1; 80 } 81 warn("overflow in constant expression"); 82 return 0; 83 } 84 85 static int 86 mulf(TFLOAT l, TFLOAT r, Type *tp) 87 { 88 struct limits *lim = getlimits(tp); 89 TFLOAT max = lim->max.f, min = lim->min.f; 90 91 if (l > -1 && l <= 1 || 92 r > -1 && r <= 1 || 93 l < 0 && r < 0 && -l <= max/-r || 94 l < 0 && r > 0 && l >= min/r || 95 l > 0 && r < 0 && r >= min/l || 96 l > 0 && r > 0 && l <= max/r) { 97 return 1; 98 } 99 warn("overflow in constant expression"); 100 return 0; 101 } 102 103 static int 104 divi(TINT l, TINT r, Type *tp) 105 { 106 struct limits *lim = getlimits(tp); 107 108 if (r == 0 || l == -lim->min.i && r == -1) { 109 warn("overflow in constant expression"); 110 return 0; 111 } 112 return 1; 113 } 114 115 static int 116 divf(TFLOAT l, TFLOAT r, Type *tp) 117 { 118 struct limits *lim = getlimits(tp); 119 120 if (l < 0) l = -l; 121 if (r < 0) r = -r; 122 123 if (r == 0.0 || r < 1.0 && l > lim->max.f * r) { 124 warn("overflow in constant expression"); 125 return 0; 126 } 127 return 1; 128 } 129 130 static int 131 lshi(TINT l, TINT r, Type *tp) 132 { 133 if (r < 0 || r >= tp->size * 8) { 134 warn("shifting %d bits is undefined", r); 135 return 0; 136 } 137 return muli(l, 1 << r, tp); 138 } 139 140 static int 141 rshi(TINT l, TINT r, Type *tp) 142 { 143 if (r < 0 || r >= tp->size * 8) { 144 warn("shifting %d bits is undefined", r); 145 return 0; 146 } 147 return 1; 148 } 149 150 static int 151 foldint(int op, Symbol *res, TINT l, TINT r) 152 { 153 TINT i; 154 Type *tp = res->type; 155 int (*validate)(TINT, TINT, Type *tp); 156 157 switch (op) { 158 case OADD: validate = addi; break; 159 case OSUB: validate = subi; break; 160 case OMUL: validate = muli; break; 161 case ODIV: validate = divi; break; 162 case OSHL: validate = lshi; break; 163 case OSHR: validate = rshi; break; 164 case OMOD: validate = divi; break; 165 default: validate = NULL; break; 166 } 167 168 if (validate && !(*validate)(l, r, tp)) 169 return 0; 170 171 switch (op) { 172 case OADD: i = l + r; break; 173 case OSUB: i = l - r; break; 174 case OMUL: i = l * r; break; 175 case ODIV: i = l / r; break; 176 case OMOD: i = l % r; break; 177 case OSHL: i = l << r; break; 178 case OSHR: i = l >> r; break; 179 case OBAND: i = l & r; break; 180 case OBXOR: i = l ^ r; break; 181 case OBOR: i = l | r; break; 182 case OAND: i = l && r; break; 183 case OOR: i = l || r; break; 184 case OLT: i = l < r; break; 185 case OGT: i = l > r; break; 186 case OGE: i = l >= r; break; 187 case OLE: i = l <= r; break; 188 case OEQ: i = l == r; break; 189 case ONE: i = l != r; break; 190 case ONEG: i = !l; break; 191 case OSNEG: i = -l; break; 192 case OCPL: i = ~l; break; 193 default: return 0; 194 } 195 res->u.i = i; 196 197 DBG("FOLD i l=%lld %d r=%lld = %lld", l, op, r, i); 198 return 1; 199 } 200 201 static int 202 folduint(int op, Symbol *res, TUINT l, TUINT r) 203 { 204 TINT i; 205 TUINT u; 206 207 switch (op) { 208 case OADD: u = l + r; break; 209 case OSUB: u = l - r; break; 210 case OMUL: u = l * r; break; 211 case ODIV: u = l / r; break; 212 case OMOD: u = l % r; break; 213 case OSHL: u = l << r; break; 214 case OSHR: u = l >> r; break; 215 case OBAND: u = l & r; break; 216 case OBXOR: u = l ^ r; break; 217 case OBOR: u = l | r; break; 218 case ONEG: u = !l; break; 219 case OSNEG: u = -l; break; 220 case OCPL: u = ~l; break; 221 case OAND: i = l && r; goto sign; 222 case OOR: i = l || r; goto sign; 223 case OLT: i = l < r; goto sign; 224 case OGT: i = l > r; goto sign; 225 case OGE: i = l >= r; goto sign; 226 case OLE: i = l <= r; goto sign; 227 case OEQ: i = l == r; goto sign; 228 case ONE: i = l != r; goto sign; 229 default: return 0; 230 } 231 res->u.u = u & ones(res->type->size); 232 233 DBG("FOLD ui l=%llu %d r=%llu = %llu", l, op, r, u); 234 return 1; 235 236 sign: 237 res->u.i = i; 238 239 DBG("FOLD sui %llu %d %llu = %llu", l, op, r, i); 240 return 1; 241 } 242 243 static int 244 foldfloat(int op, Symbol *res, TFLOAT l, TFLOAT r) 245 { 246 TFLOAT f; 247 TINT i; 248 int (*validate)(TFLOAT, TFLOAT, Type *tp); 249 250 switch (op) { 251 case OADD: validate = addf; break; 252 case OSUB: validate = subf; break; 253 case OMUL: validate = mulf; break; 254 case ODIV: validate = divf; break; 255 default: validate = NULL; break; 256 } 257 258 if (validate && !(*validate)(l, r, res->type)) 259 return 0; 260 261 switch (op) { 262 case OADD: f = l + r; break; 263 case OSUB: f = l - r; break; 264 case OMUL: f = l * r; break; 265 case ODIV: f = l / r; break; 266 case OLT: i = l < r; goto comparison; 267 case OGT: i = l > r; goto comparison; 268 case OGE: i = l >= r; goto comparison; 269 case OLE: i = l <= r; goto comparison; 270 case OEQ: i = l == r; goto comparison; 271 case ONE: i = l != r; goto comparison; 272 default: return 0; 273 } 274 res->u.f = f; 275 276 DBG("FOLD f l=%lf %d r=%lf = %lf", l, op, r, f); 277 return 1; 278 279 comparison: 280 res->u.i = i; 281 282 DBG("FOLD if l=%lf %d r=%lf = %lld", l, op, r, i); 283 return 1; 284 } 285 286 static Node * 287 foldconst(int type, int op, Type *tp, Symbol *ls, Symbol *rs) 288 { 289 Symbol *sym, aux; 290 TINT i; 291 TUINT u; 292 TFLOAT f; 293 294 aux.type = tp; 295 switch (type) { 296 case INT: 297 i = (rs) ? rs->u.i : 0; 298 if (!foldint(op, &aux, ls->u.i, i)) 299 return NULL; 300 break; 301 case UNSIGNED: 302 u = (rs) ? rs->u.u : 0u; 303 if (!folduint(op, &aux, ls->u.u, u)) 304 return NULL; 305 break; 306 case FLOAT: 307 f = (rs) ? rs->u.f : 0.0; 308 if (!foldfloat(op, &aux, ls->u.f, f)) 309 return NULL; 310 break; 311 } 312 sym = newsym(NS_IDEN, NULL); 313 sym->flags |= SCONSTANT; 314 sym->type = tp; 315 sym->u = aux.u; 316 return constnode(sym); 317 } 318 319 static Node * 320 foldcast(Node *np, Node *l) 321 { 322 TUINT negmask, mask, u; 323 Type *newtp = np->type, *oldtp = l->type; 324 Symbol aux, *sym, *osym = l->sym; 325 326 if (!(l->flags & NCONST)) 327 return np; 328 329 switch (newtp->op) { 330 case PTR: 331 case INT: 332 case ENUM: 333 switch (oldtp->op) { 334 case PTR: 335 case INT: 336 case ENUM: 337 u = (oldtp->prop & TSIGNED) ? osym->u.i : osym->u.u; 338 break; 339 case FLOAT: 340 oldtp = newtp; 341 u = osym->u.f; 342 break; 343 default: 344 return np; 345 } 346 mask = ones(newtp->size); 347 if (newtp->prop & TSIGNED) { 348 negmask = ~mask; 349 if (u & (negmask >> 1) & mask) 350 u |= negmask; 351 aux.u.i = u; 352 } else { 353 aux.u.u = u & mask; 354 } 355 break; 356 case FLOAT: 357 /* FIXME: The cast can be from another float type */ 358 aux.u.f = (oldtp->prop & TSIGNED) ? osym->u.i : osym->u.u; 359 break; 360 default: 361 return np; 362 } 363 DBG("FOLD cast %c->%c", oldtp->letter, newtp->letter); 364 freetree(np); 365 sym = newsym(NS_IDEN, NULL); 366 sym->flags |= SCONSTANT; 367 sym->type = newtp; 368 sym->u = aux.u; 369 return constnode(sym); 370 } 371 372 static Node * 373 foldunary(Node *np, Node *l) 374 { 375 int op = l->op; 376 Node *aux; 377 378 switch (np->op) { 379 case ONEG: 380 if (l->op == ONEG) 381 break; 382 return NULL; 383 case OADD: 384 DBG("FOLD unary delete %d", np->op); 385 np->left = NULL; 386 freetree(np); 387 return l; 388 case OCAST: 389 if (op != OCAST) 390 return foldcast(np, l); 391 /* TODO: This is wrong: (float)(int) 7.2 */ 392 DBG("FOLD unary collapse %d", np->op); 393 np->left = l->left; 394 l->left = NULL; 395 freetree(l); 396 return np; 397 case OSNEG: 398 case OCPL: 399 if (op != np->op) 400 return NULL; 401 break; 402 case OPTR: 403 if (op != OADDR || np->type != l->left->type) 404 return NULL; 405 break; 406 case OADDR: 407 if (op != OPTR) 408 return NULL; 409 break; 410 default: 411 return NULL; 412 } 413 DBG("FOLD unary cancel %d", np->op); 414 aux = l->left; 415 l->left = NULL; 416 freetree(np); 417 return aux; 418 } 419 420 static Node * 421 fold(Node *np) 422 { 423 Symbol *rs, *ls; 424 Type *optype; 425 int type; 426 int op = np->op; 427 Node *p, *lp = np->left, *rp = np->right; 428 Type *tp = np->type; 429 430 assert(lp && rp); 431 if ((op == ODIV || op == OMOD) && cmpnode(rp, 0)) { 432 warn("division by 0"); 433 return NULL; 434 } 435 /* 436 * Return if any of the children is no constant, 437 * or it is a constant generated when 438 * the address of a static variable is taken 439 * (when we don't know the physical address so 440 * we cannot fold it) 441 */ 442 if (!rp) { 443 rs = NULL; 444 } else { 445 if (!(rp->flags & NCONST) || !rp->sym) 446 return NULL; 447 rs = rp->sym; 448 } 449 450 if (!(lp->flags & NCONST) || !lp->sym) 451 return NULL; 452 optype = lp->type; 453 ls = lp->sym; 454 455 switch (type = optype->op) { 456 case ENUM: 457 case INT: 458 if (!(optype->prop & TSIGNED)) 459 type = UNSIGNED; 460 case PTR: 461 case FLOAT: 462 if ((p = foldconst(type, op, tp, ls, rs)) == NULL) 463 return NULL; 464 freetree(np); 465 return p; 466 default: 467 return NULL; 468 } 469 } 470 471 static void 472 commutative(Node *np, Node *l, Node *r) 473 { 474 int op = np->op; 475 476 if (r == NULL || r->flags&NCONST || !(l->flags&NCONST)) 477 return; 478 479 switch (op) { 480 case OLT: 481 case OGT: 482 case OGE: 483 case OLE: 484 DBG("FOLD neg commutative %d", np->op); 485 np->op = negop(op); 486 case OEQ: 487 case ONE: 488 case OADD: 489 case OMUL: 490 case OBAND: 491 case OBXOR: 492 case OBOR: 493 DBG("FOLD commutative %d", np->op); 494 np->left = r; 495 np->right = l; 496 break; 497 } 498 } 499 500 static Node * 501 identity(Node *np) 502 { 503 int iszeror, isoner; 504 int iszerol, isonel; 505 Node *lp = np->left, *rp = np->right; 506 507 if (!rp) 508 return NULL; 509 510 iszeror = cmpnode(rp, 0); 511 isoner = cmpnode(rp, 1), 512 iszerol = cmpnode(lp, 0); 513 isonel = cmpnode(lp, 1); 514 515 switch (np->op) { 516 case OOR: 517 /* 518 * 1 || i => 1 (free right) 519 * i || 0 => i (free right) 520 * 0 || i => i (free left) 521 * i || 1 => i,1 (comma) 522 */ 523 if (isonel | iszeror) 524 goto free_right; 525 if (iszerol) 526 goto free_left; 527 if (isoner) 528 goto change_to_comma; 529 return NULL; 530 case OAND: 531 /* 532 * 0 && i => 0 (free right) 533 * i && 1 => i (free right) 534 * 1 && i => i (free left) 535 * i && 0 => i,0 (comma) 536 */ 537 if (iszerol | isoner) 538 goto free_right; 539 if (isonel) 540 goto free_left; 541 if (iszeror) 542 goto change_to_comma; 543 return NULL; 544 case OSHL: 545 case OSHR: 546 /* 547 * i >> 0 => i (free right) 548 * i << 0 => i (free right) 549 * 0 >> i => 0 (free right) 550 * 0 << i => 0 (free right) 551 */ 552 if (iszeror | iszerol) 553 goto free_right; 554 return NULL; 555 case OBXOR: 556 case OADD: 557 case OBOR: 558 case OSUB: 559 /* 560 * i + 0 => i 561 * i - 0 => i 562 * i | 0 => i 563 * i ^ 0 => i 564 */ 565 if (iszeror) 566 goto free_right; 567 return NULL; 568 case OMUL: 569 /* 570 * i * 0 => i,0 571 * i * 1 => i 572 */ 573 if (iszeror) 574 goto change_to_comma; 575 if (isoner) 576 goto free_right; 577 return NULL; 578 case ODIV: 579 /* i / 1 => i */ 580 if (isoner) 581 goto free_right; 582 return NULL; 583 case OBAND: 584 /* i & ~0 => i */ 585 if (cmpnode(rp, -1)) 586 goto free_right; 587 return NULL; 588 case OMOD: 589 /* i % 1 => i,1 */ 590 /* TODO: i % 2^n => i & n-1 */ 591 if (isoner) 592 goto change_to_comma; 593 default: 594 return NULL; 595 } 596 597 free_right: 598 DBG("FOLD identity %d", np->op); 599 np->left = NULL; 600 freetree(np); 601 return lp; 602 603 free_left: 604 DBG("FOLD identity %d", np->op); 605 np->right = NULL; 606 freetree(np); 607 return rp; 608 609 change_to_comma: 610 DBG("FOLD identity %d", np->op); 611 np->op = OCOMMA; 612 return np; 613 } 614 615 static Node * 616 foldternary(Node *np, Node *cond, Node *body) 617 { 618 if (!(cond->flags & NCONST)) 619 return np; 620 if (cmpnode(cond, 0)) { 621 np = body->right; 622 freetree(body->left); 623 } else { 624 np = body->left; 625 freetree(body->right); 626 } 627 628 DBG("FOLD ternary"); 629 body->left = NULL; 630 body->right = NULL; 631 freetree(cond); 632 free(body); 633 return np; 634 } 635 636 /* TODO: fold OCOMMA */ 637 638 Node * 639 simplify(Node *np) 640 { 641 Node *p, *l, *r; 642 643 if (!np) 644 return NULL; 645 if (debug) 646 prtree(np); 647 648 l = np->left = simplify(np->left); 649 r = np->right = simplify(np->right); 650 651 switch (np->op) { 652 case OASK: 653 return foldternary(np, l, r); 654 case OCALL: 655 case OPAR: 656 case OSYM: 657 case OASSIGN: 658 case OA_MUL: 659 case OA_DIV: 660 case OA_MOD: 661 case OA_ADD: 662 case OA_SUB: 663 case OA_SHL: 664 case OA_SHR: 665 case OA_AND: 666 case OA_XOR: 667 case OA_OR: 668 return np; 669 case OSNEG: 670 case OCPL: 671 case OADDR: 672 case OPTR: 673 case INC: 674 case DEC: 675 case OCAST: 676 case ONEG: 677 assert(!r); 678 if ((p = foldunary(np, l)) != NULL) 679 return p; 680 return np; 681 default: 682 commutative(np, l, r); 683 if ((p = fold(np)) != NULL) 684 return p; 685 if ((p = identity(np)) != NULL) 686 return p; 687 return np; 688 } 689 }