fold.c (14428B)
1 #include <assert.h> 2 #include <stdlib.h> 3 4 #include <scc/scc.h> 5 #include "cc1.h" 6 7 8 TUINT 9 ones(int nbytes) 10 { 11 return (nbytes == 8) ? -1 : ~(-1ull << nbytes * 8); 12 } 13 14 static int 15 addi(TINT l, TINT r, Type *tp) 16 { 17 struct limits *lim = getlimits(tp); 18 TINT 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(TFLOAT l, TFLOAT r, Type *tp) 34 { 35 struct limits *lim = getlimits(tp); 36 TFLOAT 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(TINT l, TINT r, Type *tp) 52 { 53 return addi(l, -r, tp); 54 } 55 56 static int 57 subf(TFLOAT l, TFLOAT r, Type *tp) 58 { 59 return addf(l, -r, tp); 60 } 61 62 static int 63 muli(TINT l, TINT r, Type *tp) 64 { 65 struct limits *lim = getlimits(tp); 66 TINT 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(TFLOAT l, TFLOAT r, Type *tp) 82 { 83 struct limits *lim = getlimits(tp); 84 TFLOAT 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(TINT l, TINT 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(TFLOAT l, TFLOAT 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(TINT l, TINT 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(TINT l, TINT 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, TINT l, TINT r) 147 { 148 TINT i; 149 Type *tp = res->type; 150 int (*validate)(TINT, TINT, 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, TUINT l, TUINT r) 198 { 199 TINT i; 200 TUINT 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 foldfloat(int op, Symbol *res, TFLOAT l, TFLOAT r) 240 { 241 TFLOAT f; 242 TINT i; 243 int (*validate)(TFLOAT, TFLOAT, 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 OLT: i = l < r; goto comparison; 262 case OGT: i = l > r; goto comparison; 263 case OGE: i = l >= r; goto comparison; 264 case OLE: i = l <= r; goto comparison; 265 case OEQ: i = l == r; goto comparison; 266 case ONE: i = l != r; goto comparison; 267 default: return 0; 268 } 269 res->u.f = f; 270 271 DBG("FOLD f l=%lf %d r=%lf = %lf", l, op, r, f); 272 return 1; 273 274 comparison: 275 res->u.i = i; 276 277 DBG("FOLD if l=%lf %d r=%lf = %lld", l, op, r, i); 278 return 1; 279 } 280 281 static Node * 282 foldconst(int type, int op, Type *tp, Symbol *ls, Symbol *rs) 283 { 284 Symbol *sym, aux; 285 TINT i; 286 TUINT u; 287 TFLOAT f; 288 289 aux.type = tp; 290 switch (type) { 291 case INT: 292 i = (rs) ? rs->u.i : 0; 293 if (!foldint(op, &aux, ls->u.i, i)) 294 return NULL; 295 break; 296 case PTR: 297 case UNSIGNED: 298 u = (rs) ? rs->u.u : 0u; 299 if (!folduint(op, &aux, ls->u.u, u)) 300 return NULL; 301 break; 302 case FLOAT: 303 f = (rs) ? rs->u.f : 0.0; 304 if (!foldfloat(op, &aux, ls->u.f, f)) 305 return NULL; 306 break; 307 default: 308 abort(); 309 } 310 sym = newsym(NS_IDEN, NULL); 311 sym->flags |= SCONSTANT; 312 sym->type = tp; 313 sym->u = aux.u; 314 return constnode(sym); 315 } 316 317 static Node * 318 foldcast(Node *np, Node *l) 319 { 320 TUINT negmask, mask, u; 321 Type *newtp = np->type, *oldtp = l->type; 322 Symbol aux, *sym, *osym = l->sym; 323 324 if ((l->flags & NCONST) == 0 || !osym) 325 return np; 326 327 switch (newtp->op) { 328 case PTR: 329 case INT: 330 case ENUM: 331 switch (oldtp->op) { 332 case PTR: 333 case INT: 334 case ENUM: 335 u = (oldtp->prop & TSIGNED) ? osym->u.i : osym->u.u; 336 break; 337 case FLOAT: 338 oldtp = newtp; 339 u = osym->u.f; 340 break; 341 default: 342 return np; 343 } 344 mask = ones(newtp->size); 345 if (newtp->prop & TSIGNED) { 346 negmask = ~mask; 347 if (u & (negmask >> 1) & mask) 348 u |= negmask; 349 aux.u.i = u; 350 } else { 351 aux.u.u = u & mask; 352 } 353 break; 354 case FLOAT: 355 /* FIXME: The cast can be from another float type */ 356 aux.u.f = (oldtp->prop & TSIGNED) ? osym->u.i : osym->u.u; 357 break; 358 default: 359 return np; 360 } 361 362 DBG("FOLD cast %c->%c", oldtp->letter, newtp->letter); 363 freetree(np); 364 sym = newsym(NS_IDEN, NULL); 365 sym->flags |= SCONSTANT; 366 sym->type = newtp; 367 sym->u = aux.u; 368 return constnode(sym); 369 } 370 371 static Node * 372 foldunary(Node *np) 373 { 374 Node *l = np->left; 375 Node *aux; 376 Symbol *sym; 377 int op = l->op; 378 379 switch (np->op) { 380 case ONEG: 381 if (l->op == ONEG) 382 break; 383 return np; 384 case OADD: 385 DBG("FOLD unary delete %d", np->op); 386 np->left = NULL; 387 freetree(np); 388 return l; 389 case OCAST: 390 return foldcast(np, l); 391 case OSNEG: 392 case OCPL: 393 if (op != np->op) 394 return np; 395 break; 396 case OPTR: 397 if (op != OADDR || np->type != l->left->type) 398 return np; 399 break; 400 case OADDR: 401 /* &(*s).f -> s + offsetof(typeof(*s), f) */ 402 if (op == OFIELD && l->left->op == OPTR) { 403 DBG("FOLD collapse '&(*s).f' %d", np->op); 404 aux = node(OADD, 405 np->type, 406 l->left->left, 407 offsetnode(l->right->sym, np->type)); 408 409 if (aux->left->flags & NCONST) 410 aux->flags |= NCONST; 411 l->left->left = NULL; 412 freetree(np); 413 return aux; 414 } 415 416 /* &s.f -> &s + offsetof(typeof(s), f) */ 417 if (op == OFIELD) { 418 DBG("FOLD collapse '&s.f' %d", np->op); 419 aux = node(OADD, 420 np->type, 421 node(OADDR, np->type, l->left, NULL), 422 offsetnode(l->right->sym, np->type)); 423 424 if (np->flags & NCONST) 425 aux->flags |= NCONST; 426 l->left = NULL; 427 freetree(np); 428 return aux; 429 } 430 431 if (op != OPTR) 432 return np; 433 break; 434 default: 435 return np; 436 } 437 DBG("FOLD unary cancel %d", np->op); 438 aux = l->left; 439 l->left = NULL; 440 freetree(np); 441 return aux; 442 } 443 444 static Node * 445 fold(Node *np) 446 { 447 Symbol *rs, *ls; 448 Type *optype; 449 int type; 450 int op = np->op; 451 Node *p, *lp = np->left, *rp = np->right; 452 Type *tp = np->type; 453 454 if (!lp && !rp) 455 return np; 456 457 if ((op == ODIV || op == OMOD) && cmpnode(rp, 0)) { 458 warn("division by 0"); 459 return np; 460 } 461 /* 462 * Return if any of the children is no constant, 463 * or it is a constant generated when 464 * the address of a static variable is taken 465 * (when we don't know the physical address so 466 * we cannot fold it) 467 */ 468 if (!rp) { 469 rs = NULL; 470 } else { 471 if (!(rp->flags & NCONST) || !rp->sym) 472 return np; 473 rs = rp->sym; 474 } 475 476 if ((lp->flags & NCONST) == 0 || !lp->sym) 477 return np; 478 optype = lp->type; 479 ls = lp->sym; 480 481 type = optype->op; 482 switch (type) { 483 case ENUM: 484 case INT: 485 if (!(optype->prop & TSIGNED)) 486 type = UNSIGNED; 487 case PTR: 488 case FLOAT: 489 if ((p = foldconst(type, op, tp, ls, rs)) == NULL) { 490 np->flags &= ~NCONST; 491 return np; 492 } 493 freetree(np); 494 return p; 495 default: 496 return np; 497 } 498 } 499 500 static void 501 commutative(Node *np) 502 { 503 int op = np->op; 504 Node *l = np->left, *r = np->right; 505 506 if (r == NULL || r->flags&NCONST || !(l->flags&NCONST)) 507 return; 508 509 switch (op) { 510 case OLT: 511 case OGT: 512 case OGE: 513 case OLE: 514 DBG("FOLD neg commutative %d", np->op); 515 np->op = negop(op); 516 case OEQ: 517 case ONE: 518 case OADD: 519 case OMUL: 520 case OBAND: 521 case OBXOR: 522 case OBOR: 523 DBG("FOLD commutative %d", np->op); 524 np->left = r; 525 np->right = l; 526 break; 527 } 528 } 529 530 static Node * 531 identity(Node *np) 532 { 533 int iszeror, isoner; 534 int iszerol, isonel; 535 Node *lp = np->left, *rp = np->right; 536 537 if (!rp) 538 return np; 539 540 iszeror = cmpnode(rp, 0); 541 isoner = cmpnode(rp, 1), 542 iszerol = cmpnode(lp, 0); 543 isonel = cmpnode(lp, 1); 544 545 switch (np->op) { 546 case OOR: 547 /* 548 * 1 || i => 1 (free right) 549 * i || 0 => i (free right) 550 * 0 || i => i (free left) 551 * i || 1 => i,1 (comma) 552 */ 553 if (isonel | iszeror) 554 goto free_right; 555 if (iszerol) 556 goto free_left; 557 if (isoner) 558 goto change_to_comma; 559 return np; 560 case OAND: 561 /* 562 * 0 && i => 0 (free right) 563 * i && 1 => i (free right) 564 * 1 && i => i (free left) 565 * i && 0 => i,0 (comma) 566 */ 567 if (iszerol | isoner) 568 goto free_right; 569 if (isonel) 570 goto free_left; 571 if (iszeror) 572 goto change_to_comma; 573 return np; 574 case OSHL: 575 case OSHR: 576 /* 577 * i >> 0 => i (free right) 578 * i << 0 => i (free right) 579 * 0 >> i => 0 (free right) 580 * 0 << i => 0 (free right) 581 */ 582 if (iszeror | iszerol) 583 goto free_right; 584 return np; 585 case OBXOR: 586 case OADD: 587 case OBOR: 588 case OSUB: 589 /* 590 * i + 0 => i 591 * i - 0 => i 592 * i | 0 => i 593 * i ^ 0 => i 594 */ 595 if (iszeror) 596 goto free_right; 597 return np; 598 case OMUL: 599 /* 600 * i * 0 => i,0 (comma) 601 * i * 1 => i (free right) 602 */ 603 if (iszeror) 604 goto change_to_comma; 605 if (isoner) 606 goto free_right; 607 return np; 608 case ODIV: 609 /* i / 1 => i */ 610 if (isoner) 611 goto free_right; 612 return np; 613 case OBAND: 614 /* i & ~0 => i */ 615 if (cmpnode(rp, -1)) 616 goto free_right; 617 return np; 618 case OMOD: 619 /* i % 1 => i,1 */ 620 if (isoner) 621 goto change_to_comma; 622 default: 623 return np; 624 } 625 626 free_right: 627 DBG("FOLD identity %d", np->op); 628 np->left = NULL; 629 freetree(np); 630 return lp; 631 632 free_left: 633 DBG("FOLD identity %d", np->op); 634 np->right = NULL; 635 freetree(np); 636 return rp; 637 638 change_to_comma: 639 DBG("FOLD identity %d", np->op); 640 np->op = OCOMMA; 641 return np; 642 } 643 644 static Node * 645 foldternary(Node *np) 646 { 647 Node *cond = np->left, *body = np->right; 648 649 if ((cond->flags & NCONST) == 0) 650 return np; 651 if (cmpnode(cond, 0)) { 652 np = body->right; 653 freetree(body->left); 654 } else { 655 np = body->left; 656 freetree(body->right); 657 } 658 659 DBG("FOLD ternary"); 660 body->left = NULL; 661 body->right = NULL; 662 freetree(cond); 663 free(body); 664 return np; 665 } 666 667 static Node *xsimplify(Node *); 668 669 static void 670 reduce(Node *np) 671 { 672 Node *lp = np->left, *rp = np->right; 673 Node *aux, *aux2; 674 int op = np->op; 675 676 switch (op) { 677 case OMOD: 678 /* i % 2^n => i & n-1 */ 679 if (power2node(rp, NULL)) { 680 np->op = OBAND; 681 rp->sym->u.u--; 682 break; 683 } 684 return; 685 default: 686 return; 687 } 688 689 DBG("FOLD reduce %d->%d", op, np->op); 690 } 691 692 static void 693 associative(Node *np) 694 { 695 Node *l = np->left, *r = np->right; 696 697 switch (np->op) { 698 case OADD: 699 case OMUL: 700 case OBAND: 701 case OBXOR: 702 case OBOR: 703 if (np->op != l->op 704 || l->right->op != OSYM 705 || !(l->right->sym->flags&SCONSTANT)) { 706 return; 707 } 708 709 DBG("FOLD associative %d", np->op); 710 np->left = l->left; 711 l->left = r; 712 np->right = fold(l); 713 break; 714 } 715 } 716 717 /* TODO: fold OCOMMA */ 718 static Node * 719 xxsimplify(Node *np) 720 { 721 int op; 722 723 np->left = xsimplify(np->left); 724 np->right = xsimplify(np->right); 725 726 repeat: 727 switch (op = np->op) { 728 case OASK: 729 np = foldternary(np); 730 break; 731 case OCALL: 732 case OPAR: 733 case OSYM: 734 case OASSIGN: 735 case OA_MUL: 736 case OA_DIV: 737 case OA_MOD: 738 case OA_ADD: 739 case OA_SUB: 740 case OA_SHL: 741 case OA_SHR: 742 case OA_AND: 743 case OA_XOR: 744 case OA_OR: 745 break; 746 case OSNEG: 747 case OCPL: 748 case OADDR: 749 case OPTR: 750 case INC: 751 case DEC: 752 case OCAST: 753 case ONEG: 754 assert(!np->right); 755 np = foldunary(np); 756 np = fold(np); 757 break; 758 default: 759 commutative(np); 760 associative(np); 761 np = fold(np); 762 np = identity(np); 763 reduce(np); 764 break; 765 } 766 767 if (op != np->op) 768 goto repeat; 769 return np; 770 } 771 772 static Node * 773 xsimplify(Node *np) 774 { 775 if (!np) 776 return NULL; 777 778 if (enadebug) 779 prtree("simplify before", np); 780 np = xxsimplify(np); 781 if (enadebug) 782 prtree("simplify after", np); 783 784 return np; 785 } 786 787 Node * 788 simplify(Node *np) 789 { 790 DBG("SIMPLIFY"); 791 return xsimplify(np); 792 DBG("SIMPLIFY DONE"); 793 }