fold.c (17406B)
1 #include <assert.h> 2 #include <stdlib.h> 3 4 #include <scc/scc.h> 5 #include "cc1.h" 6 7 8 unsigned long long 9 ones(int nbytes) 10 { 11 return (nbytes == 8) ? -1 : ~(-1ull << nbytes * 8); 12 } 13 14 static int 15 addi(long long l, long long r, Type *tp) 16 { 17 struct limits *lim = getlimits(tp); 18 long long max = lim->max.i, min = lim->min.i; 19 20 if (l < 0 && r < 0 && l >= min - r || 21 l == 0 || 22 r == 0 || 23 l < 0 && r > 0 || 24 l > 0 && r < 0 || 25 l > 0 && r > 0 && l <= max - r) { 26 return 1; 27 } 28 warn("overflow in constant expression"); 29 return 0; 30 } 31 32 static int 33 addf(double l, double r, Type *tp) 34 { 35 struct limits *lim = getlimits(tp); 36 double max = lim->max.f, min = lim->min.f; 37 38 if (l < 0 && r < 0 && l >= min - r || 39 l == 0 || 40 r == 0 || 41 l < 0 && r > 0 || 42 l > 0 && r < 0 || 43 l > 0 && r > 0 && l <= max - r) { 44 return 1; 45 } 46 warn("overflow in constant expression"); 47 return 0; 48 } 49 50 static int 51 subi(long long l, long long r, Type *tp) 52 { 53 return addi(l, -r, tp); 54 } 55 56 static int 57 subf(double l, double r, Type *tp) 58 { 59 return addf(l, -r, tp); 60 } 61 62 static int 63 muli(long long l, long long r, Type *tp) 64 { 65 struct limits *lim = getlimits(tp); 66 long long max = lim->max.i, min = lim->min.i; 67 68 if (l > -1 && l <= 1 || 69 r > -1 && r <= 1 || 70 l < 0 && r < 0 && -l <= max/-r || 71 l < 0 && r > 0 && l >= min/r || 72 l > 0 && r < 0 && r >= min/l || 73 l > 0 && r > 0 && l <= max/r) { 74 return 1; 75 } 76 warn("overflow in constant expression"); 77 return 0; 78 } 79 80 static int 81 mulf(double l, double r, Type *tp) 82 { 83 struct limits *lim = getlimits(tp); 84 double max = lim->max.f, min = lim->min.f; 85 86 if (l > -1 && l <= 1 || 87 r > -1 && r <= 1 || 88 l < 0 && r < 0 && -l <= max/-r || 89 l < 0 && r > 0 && l >= min/r || 90 l > 0 && r < 0 && r >= min/l || 91 l > 0 && r > 0 && l <= max/r) { 92 return 1; 93 } 94 warn("overflow in constant expression"); 95 return 0; 96 } 97 98 static int 99 divi(long long l, long long r, Type *tp) 100 { 101 struct limits *lim = getlimits(tp); 102 103 if (r == 0 || l == -lim->min.i && r == -1) { 104 warn("overflow in constant expression"); 105 return 0; 106 } 107 return 1; 108 } 109 110 static int 111 divf(double l, double r, Type *tp) 112 { 113 struct limits *lim = getlimits(tp); 114 115 if (l < 0) l = -l; 116 if (r < 0) r = -r; 117 118 if (r == 0.0 || r < 1.0 && l > lim->max.f * r) { 119 warn("overflow in constant expression"); 120 return 0; 121 } 122 return 1; 123 } 124 125 static int 126 lshi(long long l, long long r, Type *tp) 127 { 128 if (r < 0 || r >= tp->size * 8) { 129 warn("shifting %d bits is undefined", r); 130 return 0; 131 } 132 return muli(l, 1 << r, tp); 133 } 134 135 static int 136 rshi(long long l, long long r, Type *tp) 137 { 138 if (r < 0 || r >= tp->size * 8) { 139 warn("shifting %d bits is undefined", r); 140 return 0; 141 } 142 return 1; 143 } 144 145 static int 146 foldint(int op, Symbol *res, long long l, long long r) 147 { 148 long long i; 149 Type *tp = res->type; 150 int (*validate)(long long, long long, Type *tp); 151 152 switch (op) { 153 case OADD: validate = addi; break; 154 case OSUB: validate = subi; break; 155 case OMUL: validate = muli; break; 156 case ODIV: validate = divi; break; 157 case OSHL: validate = lshi; break; 158 case OSHR: validate = rshi; break; 159 case OMOD: validate = divi; break; 160 default: validate = NULL; break; 161 } 162 163 if (validate && !(*validate)(l, r, tp)) 164 return 0; 165 166 switch (op) { 167 case OADD: i = l + r; break; 168 case OSUB: i = l - r; break; 169 case OMUL: i = l * r; break; 170 case ODIV: i = l / r; break; 171 case OMOD: i = l % r; break; 172 case OSHL: i = l << r; break; 173 case OSHR: i = l >> r; break; 174 case OBAND: i = l & r; break; 175 case OBXOR: i = l ^ r; break; 176 case OBOR: i = l | r; break; 177 case OAND: i = l && r; break; 178 case OOR: i = l || r; break; 179 case OLT: i = l < r; break; 180 case OGT: i = l > r; break; 181 case OGE: i = l >= r; break; 182 case OLE: i = l <= r; break; 183 case OEQ: i = l == r; break; 184 case ONE: i = l != r; break; 185 case ONEG: i = !l; break; 186 case OSNEG: i = -l; break; 187 case OCPL: i = ~l; break; 188 default: return 0; 189 } 190 res->u.i = i; 191 192 DBG("FOLD i l=%lld %d r=%lld = %lld", l, op, r, i); 193 return 1; 194 } 195 196 static int 197 folduint(int op, Symbol *res, unsigned long long l, unsigned long long r) 198 { 199 long long i; 200 unsigned long long u; 201 202 switch (op) { 203 case OADD: u = l + r; break; 204 case OSUB: u = l - r; break; 205 case OMUL: u = l * r; break; 206 case ODIV: u = l / r; break; 207 case OMOD: u = l % r; break; 208 case OSHL: u = l << r; break; 209 case OSHR: u = l >> r; break; 210 case OBAND: u = l & r; break; 211 case OBXOR: u = l ^ r; break; 212 case OBOR: u = l | r; break; 213 case ONEG: u = !l; break; 214 case OSNEG: u = -l; break; 215 case OCPL: u = ~l; break; 216 case OAND: i = l && r; goto sign; 217 case OOR: i = l || r; goto sign; 218 case OLT: i = l < r; goto sign; 219 case OGT: i = l > r; goto sign; 220 case OGE: i = l >= r; goto sign; 221 case OLE: i = l <= r; goto sign; 222 case OEQ: i = l == r; goto sign; 223 case ONE: i = l != r; goto sign; 224 default: return 0; 225 } 226 res->u.u = u & ones(res->type->size); 227 228 DBG("FOLD ui l=%llu %d r=%llu = %llu", l, op, r, u); 229 return 1; 230 231 sign: 232 res->u.i = i; 233 234 DBG("FOLD sui %llu %d %llu = %llu", l, op, r, i); 235 return 1; 236 } 237 238 static int 239 foldldouble(int op, Symbol *res, long double l, long double r) 240 { 241 long double f; 242 long long i; 243 int (*validate)(double, double, Type *tp); 244 245 switch (op) { 246 case OADD: validate = addf; break; 247 case OSUB: validate = subf; break; 248 case OMUL: validate = mulf; break; 249 case ODIV: validate = divf; break; 250 default: validate = NULL; break; 251 } 252 253 if (validate && !(*validate)(l, r, res->type)) 254 return 0; 255 256 switch (op) { 257 case OADD: f = l + r; break; 258 case OSUB: f = l - r; break; 259 case OMUL: f = l * r; break; 260 case ODIV: f = l / r; break; 261 case OSNEG: f = -l; break; 262 case OLT: i = l < r; goto comparison; 263 case OGT: i = l > r; goto comparison; 264 case OGE: i = l >= r; goto comparison; 265 case OLE: i = l <= r; goto comparison; 266 case OEQ: i = l == r; goto comparison; 267 case ONE: i = l != r; goto comparison; 268 default: return 0; 269 } 270 res->u.ld = f; 271 272 DBG("FOLD f l=%llf %d r=%llf = %llf", l, op, r, f); 273 return 1; 274 275 comparison: 276 res->u.i = i; 277 278 DBG("FOLD if l=%lf %d r=%lf = %lld", l, op, r, i); 279 return 1; 280 } 281 282 static int 283 folddouble(int op, Symbol *res, double l, double r) 284 { 285 double f; 286 long long i; 287 int (*validate)(double, double, Type *tp); 288 289 switch (op) { 290 case OADD: validate = addf; break; 291 case OSUB: validate = subf; break; 292 case OMUL: validate = mulf; break; 293 case ODIV: validate = divf; break; 294 default: validate = NULL; break; 295 } 296 297 if (validate && !(*validate)(l, r, res->type)) 298 return 0; 299 300 switch (op) { 301 case OADD: f = l + r; break; 302 case OSUB: f = l - r; break; 303 case OMUL: f = l * r; break; 304 case ODIV: f = l / r; break; 305 case OSNEG: f = -l; break; 306 case OLT: i = l < r; goto comparison; 307 case OGT: i = l > r; goto comparison; 308 case OGE: i = l >= r; goto comparison; 309 case OLE: i = l <= r; goto comparison; 310 case OEQ: i = l == r; goto comparison; 311 case ONE: i = l != r; goto comparison; 312 default: return 0; 313 } 314 res->u.d = f; 315 316 DBG("FOLD f l=%lf %d r=%lf = %lf", l, op, r, f); 317 return 1; 318 319 comparison: 320 res->u.i = i; 321 322 DBG("FOLD if l=%lf %d r=%lf = %lld", l, op, r, i); 323 return 1; 324 } 325 326 static int 327 foldfloat(int op, Symbol *res, float l, float r) 328 { 329 float f; 330 long long i; 331 int (*validate)(double, double, Type *tp); 332 333 switch (op) { 334 case OADD: validate = addf; break; 335 case OSUB: validate = subf; break; 336 case OMUL: validate = mulf; break; 337 case ODIV: validate = divf; break; 338 default: validate = NULL; break; 339 } 340 341 if (validate && !(*validate)(l, r, res->type)) 342 return 0; 343 344 switch (op) { 345 case OADD: f = l + r; break; 346 case OSUB: f = l - r; break; 347 case OMUL: f = l * r; break; 348 case ODIV: f = l / r; break; 349 case OSNEG: f = -l; break; 350 case OLT: i = l < r; goto comparison; 351 case OGT: i = l > r; goto comparison; 352 case OGE: i = l >= r; goto comparison; 353 case OLE: i = l <= r; goto comparison; 354 case OEQ: i = l == r; goto comparison; 355 case ONE: i = l != r; goto comparison; 356 default: return 0; 357 } 358 res->u.f = f; 359 360 DBG("FOLD f l=%f %d r=%f = %f", l, op, r, f); 361 return 1; 362 363 comparison: 364 res->u.i = i; 365 366 DBG("FOLD if l=%lf %d r=%lf = %lld", l, op, r, i); 367 return 1; 368 } 369 370 371 static Node * 372 foldconst(int type, int op, Type *tp, Symbol *ls, Symbol *rs) 373 { 374 Symbol *sym, aux; 375 long long i; 376 unsigned long long u; 377 float f; 378 double d; 379 long double ld; 380 381 aux.type = tp; 382 switch (type) { 383 case INT: 384 i = (rs) ? rs->u.i : 0; 385 if (!foldint(op, &aux, ls->u.i, i)) 386 return NULL; 387 break; 388 case PTR: 389 case UNSIGNED: 390 u = (rs) ? rs->u.u : 0u; 391 if (!folduint(op, &aux, ls->u.u, u)) 392 return NULL; 393 break; 394 case FLOAT: 395 if (tp == floattype) { 396 f = (rs) ? rs->u.f : 0.0; 397 if (!foldfloat(op, &aux, ls->u.f, f)) 398 return NULL; 399 } else if (tp == doubletype) { 400 d = (rs) ? rs->u.d : 0.0; 401 if (!folddouble(op, &aux, ls->u.d, d)) 402 return NULL; 403 } else { 404 ld = (rs) ? rs->u.ld : 0.0; 405 if (!foldldouble(op, &aux, ls->u.ld, ld)) 406 return NULL; 407 } 408 break; 409 default: 410 abort(); 411 } 412 sym = newsym(NS_IDEN, NULL); 413 sym->flags |= SCONSTANT; 414 sym->type = tp; 415 sym->u = aux.u; 416 return constnode(sym); 417 } 418 419 static Node * 420 foldcast(Node *np, Node *l) 421 { 422 long double ld; 423 unsigned long long negmask, mask, u; 424 Type *newtp = np->type, *oldtp = l->type; 425 Symbol aux, *sym, *osym = l->sym; 426 427 if ((l->flags & NCONST) == 0 || !osym) 428 return np; 429 430 switch (newtp->op) { 431 case PTR: 432 case INT: 433 case ENUM: 434 switch (oldtp->op) { 435 case PTR: 436 case INT: 437 case ENUM: 438 u = (oldtp->prop & TSIGNED) ? osym->u.i : osym->u.u; 439 break; 440 case FLOAT: 441 oldtp = newtp; 442 u = osym->u.f; 443 break; 444 default: 445 return np; 446 } 447 mask = ones(newtp->size); 448 if (newtp->prop & TSIGNED) { 449 negmask = ~mask; 450 if (u & (negmask >> 1) & mask) 451 u |= negmask; 452 aux.u.i = u; 453 } else { 454 aux.u.u = u & mask; 455 } 456 break; 457 case FLOAT: 458 if (oldtp->op != FLOAT) { 459 if (oldtp->prop & TSIGNED) 460 ld = osym->u.i; 461 else 462 ld = osym->u.u; 463 } else if (oldtp == floattype) { 464 ld = osym->u.f; 465 } else if (oldtp == doubletype) { 466 ld = osym->u.d; 467 } else if (oldtp == ldoubletype) { 468 ld = osym->u.ld; 469 } else { 470 return np; 471 } 472 473 if (newtp == floattype) 474 aux.u.f = ld; 475 else if (newtp == doubletype) 476 aux.u.d = ld; 477 else if (newtp == ldoubletype) 478 aux.u.ld = ld; 479 else 480 abort(); 481 break; 482 default: 483 return np; 484 } 485 486 DBG("FOLD cast %c->%c", oldtp->letter, newtp->letter); 487 freetree(np); 488 sym = newsym(NS_IDEN, NULL); 489 sym->flags |= SCONSTANT; 490 sym->type = newtp; 491 sym->u = aux.u; 492 return constnode(sym); 493 } 494 495 static Node * 496 foldunary(Node *np) 497 { 498 Node *l = np->left; 499 Node *aux; 500 Symbol *sym; 501 int op = l->op; 502 503 switch (np->op) { 504 case ONEG: 505 if (l->op == ONEG) 506 break; 507 return np; 508 case OADD: 509 DBG("FOLD unary delete %d", np->op); 510 np->left = NULL; 511 freetree(np); 512 return l; 513 case OCAST: 514 return foldcast(np, l); 515 case OSNEG: 516 case OCPL: 517 if (op != np->op) 518 return np; 519 break; 520 case OPTR: 521 if (op != OADDR || np->type != l->left->type) 522 return np; 523 break; 524 case OADDR: 525 /* &(*s).f -> s + offsetof(typeof(*s), f) */ 526 if (op == OFIELD && l->left->op == OPTR) { 527 DBG("FOLD collapse '&(*s).f' %d", np->op); 528 aux = node(OADD, 529 np->type, 530 l->left->left, 531 offsetnode(l->right->sym, np->type)); 532 533 if (aux->left->flags & NCONST) 534 aux->flags |= NCONST; 535 l->left->left = NULL; 536 freetree(np); 537 return aux; 538 } 539 540 /* &s.f -> &s + offsetof(typeof(s), f) */ 541 if (op == OFIELD) { 542 DBG("FOLD collapse '&s.f' %d", np->op); 543 aux = node(OADD, 544 np->type, 545 node(OADDR, np->type, l->left, NULL), 546 offsetnode(l->right->sym, np->type)); 547 548 if (np->flags & NCONST) 549 aux->flags |= NCONST; 550 l->left = NULL; 551 freetree(np); 552 return aux; 553 } 554 555 if (op != OPTR) 556 return np; 557 break; 558 default: 559 return np; 560 } 561 DBG("FOLD unary cancel %d", np->op); 562 aux = l->left; 563 l->left = NULL; 564 freetree(np); 565 return aux; 566 } 567 568 static Node * 569 fold(Node *np) 570 { 571 Symbol *rs, *ls; 572 Type *optype; 573 int type; 574 int op = np->op; 575 Node *p, *lp = np->left, *rp = np->right; 576 Type *tp = np->type; 577 578 if (!lp && !rp) 579 return np; 580 581 if ((op == ODIV || op == OMOD) && cmpnode(rp, 0)) { 582 warn("division by 0"); 583 return np; 584 } 585 /* 586 * Return if any of the children is no constant, 587 * or it is a constant generated when 588 * the address of a static variable is taken 589 * (when we don't know the physical address so 590 * we cannot fold it) 591 */ 592 if (!rp) { 593 rs = NULL; 594 } else { 595 if (!(rp->flags & NCONST) || !rp->sym) 596 return np; 597 rs = rp->sym; 598 } 599 600 if ((lp->flags & NCONST) == 0 || !lp->sym) 601 return np; 602 optype = lp->type; 603 ls = lp->sym; 604 605 type = optype->op; 606 switch (type) { 607 case ENUM: 608 case INT: 609 if (!(optype->prop & TSIGNED)) 610 type = UNSIGNED; 611 case PTR: 612 case FLOAT: 613 if ((p = foldconst(type, op, tp, ls, rs)) == NULL) { 614 np->flags &= ~NCONST; 615 return np; 616 } 617 freetree(np); 618 return p; 619 default: 620 return np; 621 } 622 } 623 624 static void 625 commutative(Node *np) 626 { 627 int op = np->op; 628 Node *l = np->left, *r = np->right; 629 630 if (r == NULL || r->flags&NCONST || !(l->flags&NCONST)) 631 return; 632 633 switch (op) { 634 case OLT: 635 case OGT: 636 case OGE: 637 case OLE: 638 DBG("FOLD neg commutative %d", np->op); 639 np->op = negop(op); 640 case OEQ: 641 case ONE: 642 case OADD: 643 case OMUL: 644 case OBAND: 645 case OBXOR: 646 case OBOR: 647 DBG("FOLD commutative %d", np->op); 648 np->left = r; 649 np->right = l; 650 break; 651 } 652 } 653 654 static Node * 655 identity(Node *np) 656 { 657 int iszeror, isoner; 658 int iszerol, isonel; 659 Node *lp = np->left, *rp = np->right; 660 661 if (!rp) 662 return np; 663 664 iszeror = cmpnode(rp, 0); 665 isoner = cmpnode(rp, 1), 666 iszerol = cmpnode(lp, 0); 667 isonel = cmpnode(lp, 1); 668 669 switch (np->op) { 670 case OOR: 671 /* 672 * 1 || i => 1 (free right) 673 * i || 0 => i (free right) 674 * 0 || i => i (free left) 675 * i || 1 => i,1 (comma) 676 */ 677 if (isonel | iszeror) 678 goto free_right; 679 if (iszerol) 680 goto free_left; 681 if (isoner) 682 goto change_to_comma; 683 return np; 684 case OAND: 685 /* 686 * 0 && i => 0 (free right) 687 * i && 1 => i (free right) 688 * 1 && i => i (free left) 689 * i && 0 => i,0 (comma) 690 */ 691 if (iszerol | isoner) 692 goto free_right; 693 if (isonel) 694 goto free_left; 695 if (iszeror) 696 goto change_to_comma; 697 return np; 698 case OSHL: 699 case OSHR: 700 /* 701 * i >> 0 => i (free right) 702 * i << 0 => i (free right) 703 * 0 >> i => 0 (free right) 704 * 0 << i => 0 (free right) 705 */ 706 if (iszeror | iszerol) 707 goto free_right; 708 return np; 709 case OBXOR: 710 case OADD: 711 case OBOR: 712 case OSUB: 713 /* 714 * i + 0 => i 715 * i - 0 => i 716 * i | 0 => i 717 * i ^ 0 => i 718 */ 719 if (iszeror) 720 goto free_right; 721 return np; 722 case OMUL: 723 /* 724 * i * 0 => i,0 (comma) 725 * i * 1 => i (free right) 726 */ 727 if (iszeror) 728 goto change_to_comma; 729 if (isoner) 730 goto free_right; 731 return np; 732 case ODIV: 733 /* i / 1 => i */ 734 if (isoner) 735 goto free_right; 736 return np; 737 case OBAND: 738 /* i & ~0 => i */ 739 if (cmpnode(rp, -1)) 740 goto free_right; 741 return np; 742 case OMOD: 743 /* i % 1 => i,1 */ 744 if (isoner) 745 goto change_to_comma; 746 default: 747 return np; 748 } 749 750 free_right: 751 DBG("FOLD identity %d", np->op); 752 np->left = NULL; 753 freetree(np); 754 return lp; 755 756 free_left: 757 DBG("FOLD identity %d", np->op); 758 np->right = NULL; 759 freetree(np); 760 return rp; 761 762 change_to_comma: 763 DBG("FOLD identity %d", np->op); 764 np->op = OCOMMA; 765 return np; 766 } 767 768 static Node * 769 foldternary(Node *np) 770 { 771 Node *cond = np->left, *body = np->right; 772 773 if ((cond->flags & NCONST) == 0) 774 return np; 775 if (cmpnode(cond, 0)) { 776 np = body->right; 777 freetree(body->left); 778 } else { 779 np = body->left; 780 freetree(body->right); 781 } 782 783 DBG("FOLD ternary"); 784 body->left = NULL; 785 body->right = NULL; 786 freetree(cond); 787 free(body); 788 return np; 789 } 790 791 static Node *xsimplify(Node *); 792 793 static void 794 reduce(Node *np) 795 { 796 Node *lp = np->left, *rp = np->right; 797 Node *aux, *aux2; 798 int op = np->op; 799 800 switch (op) { 801 case OMOD: 802 /* i % 2^n => i & n-1 */ 803 if (power2node(rp, NULL)) { 804 np->op = OBAND; 805 rp->sym->u.u--; 806 break; 807 } 808 return; 809 default: 810 return; 811 } 812 813 DBG("FOLD reduce %d->%d", op, np->op); 814 } 815 816 static void 817 associative(Node *np) 818 { 819 Node *l = np->left, *r = np->right; 820 821 switch (np->op) { 822 case OADD: 823 case OMUL: 824 case OBAND: 825 case OBXOR: 826 case OBOR: 827 if (np->op != l->op 828 || l->right->op != OSYM 829 || !(l->right->sym->flags&SCONSTANT)) { 830 return; 831 } 832 833 DBG("FOLD associative %d", np->op); 834 np->left = l->left; 835 l->left = r; 836 np->right = fold(l); 837 break; 838 } 839 } 840 841 /* TODO: fold OCOMMA */ 842 static Node * 843 xxsimplify(Node *np) 844 { 845 int op; 846 int isfloat = np->type->op == FLOAT; 847 848 np->left = xsimplify(np->left); 849 np->right = xsimplify(np->right); 850 851 repeat: 852 switch (op = np->op) { 853 case OASK: 854 np = foldternary(np); 855 break; 856 case OCALL: 857 case OPAR: 858 case OSYM: 859 case OASSIGN: 860 case OA_MUL: 861 case OA_DIV: 862 case OA_MOD: 863 case OA_ADD: 864 case OA_SUB: 865 case OA_SHL: 866 case OA_SHR: 867 case OA_AND: 868 case OA_XOR: 869 case OA_OR: 870 break; 871 case OSNEG: 872 case OCPL: 873 case OADDR: 874 case OPTR: 875 case INC: 876 case DEC: 877 case OCAST: 878 case ONEG: 879 assert(!np->right); 880 np = foldunary(np); 881 np = fold(np); 882 break; 883 default: 884 if (!isfloat) { 885 commutative(np); 886 associative(np); 887 } 888 np = fold(np); 889 if (!isfloat) 890 np = identity(np); 891 reduce(np); 892 break; 893 } 894 895 if (op != np->op) 896 goto repeat; 897 return np; 898 } 899 900 static Node * 901 xsimplify(Node *np) 902 { 903 if (!np) 904 return NULL; 905 906 if (enadebug) 907 prtree("simplify before", np); 908 np = xxsimplify(np); 909 if (enadebug) 910 prtree("simplify after", np); 911 912 return np; 913 } 914 915 Node * 916 simplify(Node *np) 917 { 918 DBG("SIMPLIFY"); 919 return xsimplify(np); 920 DBG("SIMPLIFY DONE"); 921 }