1 /* 2 * sparse/expand.c 3 * 4 * Copyright (C) 2003 Transmeta Corp. 5 * 2003-2004 Linus Torvalds 6 * 7 * Permission is hereby granted, free of charge, to any person obtaining a copy 8 * of this software and associated documentation files (the "Software"), to deal 9 * in the Software without restriction, including without limitation the rights 10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 11 * copies of the Software, and to permit persons to whom the Software is 12 * furnished to do so, subject to the following conditions: 13 * 14 * The above copyright notice and this permission notice shall be included in 15 * all copies or substantial portions of the Software. 16 * 17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 23 * THE SOFTWARE. 24 * 25 * expand constant expressions. 26 */ 27 #include <stdlib.h> 28 #include <stdarg.h> 29 #include <stddef.h> 30 #include <stdio.h> 31 #include <string.h> 32 #include <ctype.h> 33 #include <unistd.h> 34 #include <fcntl.h> 35 #include <limits.h> 36 37 #include "lib.h" 38 #include "allocate.h" 39 #include "parse.h" 40 #include "token.h" 41 #include "symbol.h" 42 #include "target.h" 43 #include "expression.h" 44 #include "expand.h" 45 46 47 static int expand_expression(struct expression *); 48 static int expand_statement(struct statement *); 49 static int conservative; 50 51 static int expand_symbol_expression(struct expression *expr) 52 { 53 struct symbol *sym = expr->symbol; 54 55 if (sym == &zero_int) { 56 if (Wundef) 57 warning(expr->pos, "undefined preprocessor identifier '%s'", show_ident(expr->symbol_name)); 58 expr->type = EXPR_VALUE; 59 expr->value = 0; 60 expr->taint = 0; 61 return 0; 62 } 63 /* The cost of a symbol expression is lower for on-stack symbols */ 64 return (sym->ctype.modifiers & (MOD_STATIC | MOD_EXTERN)) ? 2 : 1; 65 } 66 67 static long long get_longlong(struct expression *expr) 68 { 69 int no_expand = expr->ctype->ctype.modifiers & MOD_UNSIGNED; 70 long long mask = 1ULL << (expr->ctype->bit_size - 1); 71 long long value = expr->value; 72 long long ormask, andmask; 73 74 if (!(value & mask)) 75 no_expand = 1; 76 andmask = mask | (mask-1); 77 ormask = ~andmask; 78 if (no_expand) 79 ormask = 0; 80 return (value & andmask) | ormask; 81 } 82 83 void cast_value(struct expression *expr, struct symbol *newtype, 84 struct expression *old, struct symbol *oldtype) 85 { 86 int old_size = oldtype->bit_size; 87 int new_size = newtype->bit_size; 88 long long value, mask, signmask; 89 long long oldmask, oldsignmask, dropped; 90 91 if (is_float_type(newtype) || is_float_type(oldtype)) 92 goto Float; 93 94 // For pointers and integers, we can just move the value around 95 expr->type = EXPR_VALUE; 96 expr->taint = old->taint; 97 if (old_size == new_size) { 98 expr->value = old->value; 99 return; 100 } 101 102 // expand it to the full "long long" value 103 value = get_longlong(old); 104 105 Int: 106 // _Bool requires a zero test rather than truncation. 107 if (is_bool_type(newtype)) { 108 expr->value = !!value; 109 if (!conservative && value != 0 && value != 1) 110 warning(old->pos, "odd constant _Bool cast (%llx becomes 1)", value); 111 return; 112 } 113 114 // Truncate it to the new size 115 signmask = 1ULL << (new_size-1); 116 mask = signmask | (signmask-1); 117 expr->value = value & mask; 118 119 // Stop here unless checking for truncation 120 if (!Wcast_truncate || conservative) 121 return; 122 123 // Check if we dropped any bits.. 124 oldsignmask = 1ULL << (old_size-1); 125 oldmask = oldsignmask | (oldsignmask-1); 126 dropped = oldmask & ~mask; 127 128 // OK if the bits were (and still are) purely sign bits 129 if (value & dropped) { 130 if (!(value & oldsignmask) || !(value & signmask) || (value & dropped) != dropped) 131 warning(old->pos, "cast truncates bits from constant value (%llx becomes %llx)", 132 value & oldmask, 133 value & mask); 134 } 135 return; 136 137 Float: 138 if (!is_float_type(newtype)) { 139 value = (long long)old->fvalue; 140 expr->type = EXPR_VALUE; 141 expr->taint = 0; 142 goto Int; 143 } 144 145 if (!is_float_type(oldtype)) 146 expr->fvalue = (long double)get_longlong(old); 147 else 148 expr->fvalue = old->fvalue; 149 150 if (!(newtype->ctype.modifiers & MOD_LONGLONG) && \ 151 !(newtype->ctype.modifiers & MOD_LONGLONGLONG)) { 152 if ((newtype->ctype.modifiers & MOD_LONG)) 153 expr->fvalue = (double)expr->fvalue; 154 else 155 expr->fvalue = (float)expr->fvalue; 156 } 157 expr->type = EXPR_FVALUE; 158 } 159 160 static int check_shift_count(struct expression *expr, struct symbol *ctype, unsigned int count) 161 { 162 warning(expr->pos, "shift too big (%u) for type %s", count, show_typename(ctype)); 163 count &= ctype->bit_size-1; 164 return count; 165 } 166 167 /* 168 * CAREFUL! We need to get the size and sign of the 169 * result right! 170 */ 171 #define CONVERT(op,s) (((op)<<1)+(s)) 172 #define SIGNED(op) CONVERT(op, 1) 173 #define UNSIGNED(op) CONVERT(op, 0) 174 static int simplify_int_binop(struct expression *expr, struct symbol *ctype) 175 { 176 struct expression *left = expr->left, *right = expr->right; 177 unsigned long long v, l, r, mask; 178 signed long long sl, sr; 179 int is_signed; 180 181 if (right->type != EXPR_VALUE) 182 return 0; 183 r = right->value; 184 if (expr->op == SPECIAL_LEFTSHIFT || expr->op == SPECIAL_RIGHTSHIFT) { 185 if (r >= ctype->bit_size) { 186 if (conservative) 187 return 0; 188 r = check_shift_count(expr, ctype, r); 189 right->value = r; 190 } 191 } 192 if (left->type != EXPR_VALUE) 193 return 0; 194 l = left->value; r = right->value; 195 is_signed = !(ctype->ctype.modifiers & MOD_UNSIGNED); 196 mask = 1ULL << (ctype->bit_size-1); 197 sl = l; sr = r; 198 if (is_signed && (sl & mask)) 199 sl |= ~(mask-1); 200 if (is_signed && (sr & mask)) 201 sr |= ~(mask-1); 202 203 switch (CONVERT(expr->op,is_signed)) { 204 case SIGNED('+'): 205 case UNSIGNED('+'): 206 v = l + r; 207 break; 208 209 case SIGNED('-'): 210 case UNSIGNED('-'): 211 v = l - r; 212 break; 213 214 case SIGNED('&'): 215 case UNSIGNED('&'): 216 v = l & r; 217 break; 218 219 case SIGNED('|'): 220 case UNSIGNED('|'): 221 v = l | r; 222 break; 223 224 case SIGNED('^'): 225 case UNSIGNED('^'): 226 v = l ^ r; 227 break; 228 229 case SIGNED('*'): 230 v = sl * sr; 231 break; 232 233 case UNSIGNED('*'): 234 v = l * r; 235 break; 236 237 case SIGNED('/'): 238 if (!r) 239 goto Div; 240 if (l == mask && sr == -1) 241 goto Overflow; 242 v = sl / sr; 243 break; 244 245 case UNSIGNED('/'): 246 if (!r) goto Div; 247 v = l / r; 248 break; 249 250 case SIGNED('%'): 251 if (!r) 252 goto Div; 253 if (l == mask && sr == -1) 254 goto Overflow; 255 v = sl % sr; 256 break; 257 258 case UNSIGNED('%'): 259 if (!r) goto Div; 260 v = l % r; 261 break; 262 263 case SIGNED(SPECIAL_LEFTSHIFT): 264 case UNSIGNED(SPECIAL_LEFTSHIFT): 265 v = l << r; 266 break; 267 268 case SIGNED(SPECIAL_RIGHTSHIFT): 269 v = sl >> r; 270 break; 271 272 case UNSIGNED(SPECIAL_RIGHTSHIFT): 273 v = l >> r; 274 break; 275 276 default: 277 return 0; 278 } 279 mask = mask | (mask-1); 280 expr->value = v & mask; 281 expr->type = EXPR_VALUE; 282 expr->taint = left->taint | right->taint; 283 return 1; 284 Div: 285 if (!conservative) 286 warning(expr->pos, "division by zero"); 287 return 0; 288 Overflow: 289 if (!conservative) 290 warning(expr->pos, "constant integer operation overflow"); 291 return 0; 292 } 293 294 static int simplify_cmp_binop(struct expression *expr, struct symbol *ctype) 295 { 296 struct expression *left = expr->left, *right = expr->right; 297 unsigned long long l, r, mask; 298 signed long long sl, sr; 299 300 if (left->type != EXPR_VALUE || right->type != EXPR_VALUE) 301 return 0; 302 l = left->value; r = right->value; 303 mask = 1ULL << (ctype->bit_size-1); 304 sl = l; sr = r; 305 if (sl & mask) 306 sl |= ~(mask-1); 307 if (sr & mask) 308 sr |= ~(mask-1); 309 switch (expr->op) { 310 case '<': expr->value = sl < sr; break; 311 case '>': expr->value = sl > sr; break; 312 case SPECIAL_LTE: expr->value = sl <= sr; break; 313 case SPECIAL_GTE: expr->value = sl >= sr; break; 314 case SPECIAL_EQUAL: expr->value = l == r; break; 315 case SPECIAL_NOTEQUAL: expr->value = l != r; break; 316 case SPECIAL_UNSIGNED_LT:expr->value = l < r; break; 317 case SPECIAL_UNSIGNED_GT:expr->value = l > r; break; 318 case SPECIAL_UNSIGNED_LTE:expr->value = l <= r; break; 319 case SPECIAL_UNSIGNED_GTE:expr->value = l >= r; break; 320 } 321 expr->type = EXPR_VALUE; 322 expr->taint = left->taint | right->taint; 323 return 1; 324 } 325 326 static int simplify_float_binop(struct expression *expr) 327 { 328 struct expression *left = expr->left, *right = expr->right; 329 unsigned long mod = expr->ctype->ctype.modifiers; 330 long double l, r, res; 331 332 if (left->type != EXPR_FVALUE || right->type != EXPR_FVALUE) 333 return 0; 334 335 l = left->fvalue; 336 r = right->fvalue; 337 338 if (mod & MOD_LONGLONG) { 339 switch (expr->op) { 340 case '+': res = l + r; break; 341 case '-': res = l - r; break; 342 case '*': res = l * r; break; 343 case '/': if (!r) goto Div; 344 res = l / r; break; 345 default: return 0; 346 } 347 } else if (mod & MOD_LONG) { 348 switch (expr->op) { 349 case '+': res = (double) l + (double) r; break; 350 case '-': res = (double) l - (double) r; break; 351 case '*': res = (double) l * (double) r; break; 352 case '/': if (!r) goto Div; 353 res = (double) l / (double) r; break; 354 default: return 0; 355 } 356 } else { 357 switch (expr->op) { 358 case '+': res = (float)l + (float)r; break; 359 case '-': res = (float)l - (float)r; break; 360 case '*': res = (float)l * (float)r; break; 361 case '/': if (!r) goto Div; 362 res = (float)l / (float)r; break; 363 default: return 0; 364 } 365 } 366 expr->type = EXPR_FVALUE; 367 expr->fvalue = res; 368 return 1; 369 Div: 370 if (!conservative) 371 warning(expr->pos, "division by zero"); 372 return 0; 373 } 374 375 static int simplify_float_cmp(struct expression *expr, struct symbol *ctype) 376 { 377 struct expression *left = expr->left, *right = expr->right; 378 long double l, r; 379 380 if (left->type != EXPR_FVALUE || right->type != EXPR_FVALUE) 381 return 0; 382 383 l = left->fvalue; 384 r = right->fvalue; 385 switch (expr->op) { 386 case '<': expr->value = l < r; break; 387 case '>': expr->value = l > r; break; 388 case SPECIAL_LTE: expr->value = l <= r; break; 389 case SPECIAL_GTE: expr->value = l >= r; break; 390 case SPECIAL_EQUAL: expr->value = l == r; break; 391 case SPECIAL_NOTEQUAL: expr->value = l != r; break; 392 } 393 expr->type = EXPR_VALUE; 394 expr->taint = 0; 395 return 1; 396 } 397 398 static int expand_binop(struct expression *expr) 399 { 400 int cost; 401 402 cost = expand_expression(expr->left); 403 cost += expand_expression(expr->right); 404 if (simplify_int_binop(expr, expr->ctype)) 405 return 0; 406 if (simplify_float_binop(expr)) 407 return 0; 408 return cost + 1; 409 } 410 411 static int expand_logical(struct expression *expr) 412 { 413 struct expression *left = expr->left; 414 struct expression *right; 415 int cost, rcost; 416 417 /* Do immediate short-circuiting ... */ 418 cost = expand_expression(left); 419 if (left->type == EXPR_VALUE) { 420 if (expr->op == SPECIAL_LOGICAL_AND) { 421 if (!left->value) { 422 expr->type = EXPR_VALUE; 423 expr->value = 0; 424 expr->taint = left->taint; 425 return 0; 426 } 427 } else { 428 if (left->value) { 429 expr->type = EXPR_VALUE; 430 expr->value = 1; 431 expr->taint = left->taint; 432 return 0; 433 } 434 } 435 } 436 437 right = expr->right; 438 rcost = expand_expression(right); 439 if (left->type == EXPR_VALUE && right->type == EXPR_VALUE) { 440 /* 441 * We know the left value doesn't matter, since 442 * otherwise we would have short-circuited it.. 443 */ 444 expr->type = EXPR_VALUE; 445 expr->value = right->value != 0; 446 expr->taint = left->taint | right->taint; 447 return 0; 448 } 449 450 /* 451 * If the right side is safe and cheaper than a branch, 452 * just avoid the branch and turn it into a regular binop 453 * style SAFELOGICAL. 454 */ 455 if (rcost < BRANCH_COST) { 456 expr->type = EXPR_BINOP; 457 rcost -= BRANCH_COST - 1; 458 } 459 460 return cost + BRANCH_COST + rcost; 461 } 462 463 static int expand_comma(struct expression *expr) 464 { 465 int cost; 466 467 cost = expand_expression(expr->left); 468 cost += expand_expression(expr->right); 469 if (expr->left->type == EXPR_VALUE || expr->left->type == EXPR_FVALUE) { 470 unsigned flags = expr->flags; 471 unsigned taint; 472 taint = expr->left->type == EXPR_VALUE ? expr->left->taint : 0; 473 *expr = *expr->right; 474 expr->flags = flags; 475 if (expr->type == EXPR_VALUE) 476 expr->taint |= Taint_comma | taint; 477 } 478 return cost; 479 } 480 481 #define MOD_IGN (MOD_VOLATILE | MOD_CONST) 482 483 static int compare_types(int op, struct symbol *left, struct symbol *right) 484 { 485 struct ctype c1 = {.base_type = left}; 486 struct ctype c2 = {.base_type = right}; 487 switch (op) { 488 case SPECIAL_EQUAL: 489 return !type_difference(&c1, &c2, MOD_IGN, MOD_IGN); 490 case SPECIAL_NOTEQUAL: 491 return type_difference(&c1, &c2, MOD_IGN, MOD_IGN) != NULL; 492 case '<': 493 return left->bit_size < right->bit_size; 494 case '>': 495 return left->bit_size > right->bit_size; 496 case SPECIAL_LTE: 497 return left->bit_size <= right->bit_size; 498 case SPECIAL_GTE: 499 return left->bit_size >= right->bit_size; 500 } 501 return 0; 502 } 503 504 static int expand_compare(struct expression *expr) 505 { 506 struct expression *left = expr->left, *right = expr->right; 507 int cost; 508 509 cost = expand_expression(left); 510 cost += expand_expression(right); 511 512 if (left && right) { 513 /* Type comparison? */ 514 if (left->type == EXPR_TYPE && right->type == EXPR_TYPE) { 515 int op = expr->op; 516 expr->type = EXPR_VALUE; 517 expr->value = compare_types(op, left->symbol, right->symbol); 518 expr->taint = 0; 519 return 0; 520 } 521 if (simplify_cmp_binop(expr, left->ctype)) 522 return 0; 523 if (simplify_float_cmp(expr, left->ctype)) 524 return 0; 525 } 526 return cost + 1; 527 } 528 529 static int expand_conditional(struct expression *expr) 530 { 531 struct expression *cond = expr->conditional; 532 struct expression *true = expr->cond_true; 533 struct expression *false = expr->cond_false; 534 int cost, cond_cost; 535 536 cond_cost = expand_expression(cond); 537 if (cond->type == EXPR_VALUE) { 538 unsigned flags = expr->flags; 539 if (!cond->value) 540 true = false; 541 if (!true) 542 true = cond; 543 cost = expand_expression(true); 544 *expr = *true; 545 expr->flags = flags; 546 if (expr->type == EXPR_VALUE) 547 expr->taint |= cond->taint; 548 return cost; 549 } 550 551 cost = expand_expression(true); 552 cost += expand_expression(false); 553 554 if (cost < SELECT_COST) { 555 expr->type = EXPR_SELECT; 556 cost -= BRANCH_COST - 1; 557 } 558 559 return cost + cond_cost + BRANCH_COST; 560 } 561 562 static int expand_assignment(struct expression *expr) 563 { 564 expand_expression(expr->left); 565 expand_expression(expr->right); 566 return SIDE_EFFECTS; 567 } 568 569 static int expand_addressof(struct expression *expr) 570 { 571 return expand_expression(expr->unop); 572 } 573 574 /* 575 * Look up a trustable initializer value at the requested offset. 576 * 577 * Return NULL if no such value can be found or statically trusted. 578 * 579 * FIXME!! We should check that the size is right! 580 */ 581 static struct expression *constant_symbol_value(struct symbol *sym, int offset) 582 { 583 struct expression *value; 584 585 if (sym->ctype.modifiers & (MOD_ASSIGNED | MOD_ADDRESSABLE)) 586 return NULL; 587 value = sym->initializer; 588 if (!value) 589 return NULL; 590 if (value->type == EXPR_INITIALIZER) { 591 struct expression *entry; 592 FOR_EACH_PTR(value->expr_list, entry) { 593 if (entry->type != EXPR_POS) { 594 if (offset) 595 continue; 596 return entry; 597 } 598 if (entry->init_offset < offset) 599 continue; 600 if (entry->init_offset > offset) 601 return NULL; 602 return entry->init_expr; 603 } END_FOR_EACH_PTR(entry); 604 return NULL; 605 } 606 return value; 607 } 608 609 static int expand_dereference(struct expression *expr) 610 { 611 struct expression *unop = expr->unop; 612 unsigned int offset; 613 614 expand_expression(unop); 615 616 /* 617 * NOTE! We get a bogus warning right now for some special 618 * cases: apparently I've screwed up the optimization of 619 * a zero-offset dereference, and the ctype is wrong. 620 * 621 * Leave the warning in anyway, since this is also a good 622 * test for me to get the type evaluation right.. 623 */ 624 if (expr->ctype->ctype.modifiers & MOD_NODEREF) 625 warning(unop->pos, "dereference of noderef expression"); 626 627 /* 628 * Is it "symbol" or "symbol + offset"? 629 */ 630 offset = 0; 631 if (unop->type == EXPR_BINOP && unop->op == '+') { 632 struct expression *right = unop->right; 633 if (right->type == EXPR_VALUE) { 634 offset = right->value; 635 unop = unop->left; 636 } 637 } 638 639 if (unop->type == EXPR_SYMBOL) { 640 struct symbol *sym = unop->symbol; 641 struct expression *value = constant_symbol_value(sym, offset); 642 643 /* Const symbol with a constant initializer? */ 644 if (value) { 645 /* FIXME! We should check that the size is right! */ 646 if (value->type == EXPR_VALUE) { 647 expr->type = EXPR_VALUE; 648 expr->value = value->value; 649 expr->taint = 0; 650 return 0; 651 } else if (value->type == EXPR_FVALUE) { 652 expr->type = EXPR_FVALUE; 653 expr->fvalue = value->fvalue; 654 return 0; 655 } 656 } 657 658 /* Direct symbol dereference? Cheap and safe */ 659 return (sym->ctype.modifiers & (MOD_STATIC | MOD_EXTERN)) ? 2 : 1; 660 } 661 662 return UNSAFE; 663 } 664 665 static int simplify_preop(struct expression *expr) 666 { 667 struct expression *op = expr->unop; 668 unsigned long long v, mask; 669 670 if (op->type != EXPR_VALUE) 671 return 0; 672 673 mask = 1ULL << (expr->ctype->bit_size-1); 674 v = op->value; 675 switch (expr->op) { 676 case '+': break; 677 case '-': 678 if (v == mask && !(expr->ctype->ctype.modifiers & MOD_UNSIGNED)) 679 goto Overflow; 680 v = -v; 681 break; 682 case '!': v = !v; break; 683 case '~': v = ~v; break; 684 default: return 0; 685 } 686 mask = mask | (mask-1); 687 expr->value = v & mask; 688 expr->type = EXPR_VALUE; 689 expr->taint = op->taint; 690 return 1; 691 692 Overflow: 693 if (!conservative) 694 warning(expr->pos, "constant integer operation overflow"); 695 return 0; 696 } 697 698 static int simplify_float_preop(struct expression *expr) 699 { 700 struct expression *op = expr->unop; 701 long double v; 702 703 if (op->type != EXPR_FVALUE) 704 return 0; 705 v = op->fvalue; 706 switch (expr->op) { 707 case '+': break; 708 case '-': v = -v; break; 709 default: return 0; 710 } 711 expr->fvalue = v; 712 expr->type = EXPR_FVALUE; 713 return 1; 714 } 715 716 /* 717 * Unary post-ops: x++ and x-- 718 */ 719 static int expand_postop(struct expression *expr) 720 { 721 expand_expression(expr->unop); 722 return SIDE_EFFECTS; 723 } 724 725 static int expand_preop(struct expression *expr) 726 { 727 int cost; 728 729 switch (expr->op) { 730 case '*': 731 return expand_dereference(expr); 732 733 case '&': 734 return expand_addressof(expr); 735 736 case SPECIAL_INCREMENT: 737 case SPECIAL_DECREMENT: 738 /* 739 * From a type evaluation standpoint the preops are 740 * the same as the postops 741 */ 742 return expand_postop(expr); 743 744 default: 745 break; 746 } 747 cost = expand_expression(expr->unop); 748 749 if (simplify_preop(expr)) 750 return 0; 751 if (simplify_float_preop(expr)) 752 return 0; 753 return cost + 1; 754 } 755 756 static int expand_arguments(struct expression_list *head) 757 { 758 int cost = 0; 759 struct expression *expr; 760 761 FOR_EACH_PTR (head, expr) { 762 cost += expand_expression(expr); 763 } END_FOR_EACH_PTR(expr); 764 return cost; 765 } 766 767 static int expand_cast(struct expression *expr) 768 { 769 int cost; 770 struct expression *target = expr->cast_expression; 771 772 cost = expand_expression(target); 773 774 /* Simplify normal integer casts.. */ 775 if (target->type == EXPR_VALUE || target->type == EXPR_FVALUE) { 776 cast_value(expr, expr->ctype, target, target->ctype); 777 return 0; 778 } 779 return cost + 1; 780 } 781 782 /* 783 * expand a call expression with a symbol. This 784 * should expand builtins. 785 */ 786 static int expand_symbol_call(struct expression *expr, int cost) 787 { 788 struct expression *fn = expr->fn; 789 struct symbol *ctype = fn->ctype; 790 791 if (fn->type != EXPR_PREOP) 792 return SIDE_EFFECTS; 793 794 if (ctype->op && ctype->op->expand) 795 return ctype->op->expand(expr, cost); 796 797 if (ctype->ctype.modifiers & MOD_PURE) 798 return cost + 1; 799 800 return SIDE_EFFECTS; 801 } 802 803 static int expand_call(struct expression *expr) 804 { 805 int cost; 806 struct symbol *sym; 807 struct expression *fn = expr->fn; 808 809 cost = expand_arguments(expr->args); 810 sym = fn->ctype; 811 if (!sym) { 812 expression_error(expr, "function has no type"); 813 return SIDE_EFFECTS; 814 } 815 if (sym->type == SYM_NODE) 816 return expand_symbol_call(expr, cost); 817 818 return SIDE_EFFECTS; 819 } 820 821 static int expand_expression_list(struct expression_list *list) 822 { 823 int cost = 0; 824 struct expression *expr; 825 826 FOR_EACH_PTR(list, expr) { 827 cost += expand_expression(expr); 828 } END_FOR_EACH_PTR(expr); 829 return cost; 830 } 831 832 /* 833 * We can simplify nested position expressions if 834 * this is a simple (single) positional expression. 835 */ 836 static int expand_pos_expression(struct expression *expr) 837 { 838 struct expression *nested = expr->init_expr; 839 unsigned long offset = expr->init_offset; 840 int nr = expr->init_nr; 841 842 if (nr == 1) { 843 switch (nested->type) { 844 case EXPR_POS: 845 offset += nested->init_offset; 846 *expr = *nested; 847 expr->init_offset = offset; 848 nested = expr; 849 break; 850 851 case EXPR_INITIALIZER: { 852 struct expression *reuse = nested, *entry; 853 *expr = *nested; 854 FOR_EACH_PTR(expr->expr_list, entry) { 855 if (entry->type == EXPR_POS) { 856 entry->init_offset += offset; 857 } else { 858 if (!reuse) { 859 /* 860 * This happens rarely, but it can happen 861 * with bitfields that are all at offset 862 * zero.. 863 */ 864 reuse = alloc_expression(entry->pos, EXPR_POS); 865 } 866 reuse->type = EXPR_POS; 867 reuse->ctype = entry->ctype; 868 reuse->init_offset = offset; 869 reuse->init_nr = 1; 870 reuse->init_expr = entry; 871 REPLACE_CURRENT_PTR(entry, reuse); 872 reuse = NULL; 873 } 874 } END_FOR_EACH_PTR(entry); 875 nested = expr; 876 break; 877 } 878 879 default: 880 break; 881 } 882 } 883 return expand_expression(nested); 884 } 885 886 static unsigned long bit_offset(const struct expression *expr) 887 { 888 unsigned long offset = 0; 889 while (expr->type == EXPR_POS) { 890 offset += bytes_to_bits(expr->init_offset); 891 expr = expr->init_expr; 892 } 893 if (expr && expr->ctype) 894 offset += expr->ctype->bit_offset; 895 return offset; 896 } 897 898 static unsigned long bit_range(const struct expression *expr) 899 { 900 unsigned long range = 0; 901 unsigned long size = 0; 902 while (expr->type == EXPR_POS) { 903 unsigned long nr = expr->init_nr; 904 size = expr->ctype->bit_size; 905 range += (nr - 1) * size; 906 expr = expr->init_expr; 907 } 908 range += size; 909 return range; 910 } 911 912 static int compare_expressions(const void *_a, const void *_b) 913 { 914 const struct expression *a = _a; 915 const struct expression *b = _b; 916 unsigned long a_pos = bit_offset(a); 917 unsigned long b_pos = bit_offset(b); 918 919 return (a_pos < b_pos) ? -1 : (a_pos == b_pos) ? 0 : 1; 920 } 921 922 static void sort_expression_list(struct expression_list **list) 923 { 924 sort_list((struct ptr_list **)list, compare_expressions); 925 } 926 927 static void verify_nonoverlapping(struct expression_list **list, struct expression *expr) 928 { 929 struct expression *a = NULL; 930 unsigned long max = 0; 931 unsigned long whole = expr->ctype->bit_size; 932 struct expression *b; 933 934 if (!Woverride_init) 935 return; 936 937 FOR_EACH_PTR(*list, b) { 938 unsigned long off, end; 939 if (!b->ctype || !b->ctype->bit_size) 940 continue; 941 off = bit_offset(b); 942 if (a && off < max) { 943 warning(a->pos, "Initializer entry defined twice"); 944 info(b->pos, " also defined here"); 945 if (!Woverride_init_all) 946 return; 947 } 948 end = off + bit_range(b); 949 if (!a && !Woverride_init_whole_range) { 950 // If first entry is the whole range, do not let 951 // any warning about it (this allow to initialize 952 // an array with some default value and then override 953 // some specific entries). 954 if (off == 0 && end == whole) 955 continue; 956 } 957 if (end > max) { 958 max = end; 959 a = b; 960 } 961 } END_FOR_EACH_PTR(b); 962 } 963 964 static int expand_expression(struct expression *expr) 965 { 966 if (!expr) 967 return 0; 968 if (!expr->ctype || expr->ctype == &bad_ctype) 969 return UNSAFE; 970 971 switch (expr->type) { 972 case EXPR_VALUE: 973 case EXPR_FVALUE: 974 case EXPR_STRING: 975 return 0; 976 case EXPR_TYPE: 977 case EXPR_SYMBOL: 978 return expand_symbol_expression(expr); 979 case EXPR_BINOP: 980 return expand_binop(expr); 981 982 case EXPR_LOGICAL: 983 return expand_logical(expr); 984 985 case EXPR_COMMA: 986 return expand_comma(expr); 987 988 case EXPR_COMPARE: 989 return expand_compare(expr); 990 991 case EXPR_ASSIGNMENT: 992 return expand_assignment(expr); 993 994 case EXPR_PREOP: 995 return expand_preop(expr); 996 997 case EXPR_POSTOP: 998 return expand_postop(expr); 999 1000 case EXPR_CAST: 1001 case EXPR_FORCE_CAST: 1002 case EXPR_IMPLIED_CAST: 1003 return expand_cast(expr); 1004 1005 case EXPR_CALL: 1006 return expand_call(expr); 1007 1008 case EXPR_DEREF: 1009 warning(expr->pos, "we should not have an EXPR_DEREF left at expansion time"); 1010 return UNSAFE; 1011 1012 case EXPR_SELECT: 1013 case EXPR_CONDITIONAL: 1014 return expand_conditional(expr); 1015 1016 case EXPR_STATEMENT: { 1017 struct statement *stmt = expr->statement; 1018 int cost = expand_statement(stmt); 1019 1020 if (stmt->type == STMT_EXPRESSION && stmt->expression) 1021 *expr = *stmt->expression; 1022 return cost; 1023 } 1024 1025 case EXPR_LABEL: 1026 return 0; 1027 1028 case EXPR_INITIALIZER: 1029 sort_expression_list(&expr->expr_list); 1030 verify_nonoverlapping(&expr->expr_list, expr); 1031 return expand_expression_list(expr->expr_list); 1032 1033 case EXPR_IDENTIFIER: 1034 return UNSAFE; 1035 1036 case EXPR_INDEX: 1037 return UNSAFE; 1038 1039 case EXPR_SLICE: 1040 return expand_expression(expr->base) + 1; 1041 1042 case EXPR_POS: 1043 return expand_pos_expression(expr); 1044 1045 case EXPR_SIZEOF: 1046 case EXPR_PTRSIZEOF: 1047 case EXPR_ALIGNOF: 1048 case EXPR_OFFSETOF: 1049 expression_error(expr, "internal front-end error: sizeof in expansion?"); 1050 return UNSAFE; 1051 } 1052 return SIDE_EFFECTS; 1053 } 1054 1055 static void expand_const_expression(struct expression *expr, const char *where) 1056 { 1057 if (expr) { 1058 expand_expression(expr); 1059 if (expr->type != EXPR_VALUE) 1060 expression_error(expr, "Expected constant expression in %s", where); 1061 } 1062 } 1063 1064 int expand_symbol(struct symbol *sym) 1065 { 1066 int retval; 1067 struct symbol *base_type; 1068 1069 if (!sym) 1070 return 0; 1071 base_type = sym->ctype.base_type; 1072 if (!base_type) 1073 return 0; 1074 1075 retval = expand_expression(sym->initializer); 1076 /* expand the body of the symbol */ 1077 if (base_type->type == SYM_FN) { 1078 if (base_type->stmt) 1079 expand_statement(base_type->stmt); 1080 } 1081 return retval; 1082 } 1083 1084 static void expand_return_expression(struct statement *stmt) 1085 { 1086 expand_expression(stmt->expression); 1087 } 1088 1089 static int expand_if_statement(struct statement *stmt) 1090 { 1091 struct expression *expr = stmt->if_conditional; 1092 1093 if (!expr || !expr->ctype || expr->ctype == &bad_ctype) 1094 return UNSAFE; 1095 1096 expand_expression(expr); 1097 1098 /* This is only valid if nobody jumps into the "dead" side */ 1099 #if 0 1100 /* Simplify constant conditionals without even evaluating the false side */ 1101 if (expr->type == EXPR_VALUE) { 1102 struct statement *simple; 1103 simple = expr->value ? stmt->if_true : stmt->if_false; 1104 1105 /* Nothing? */ 1106 if (!simple) { 1107 stmt->type = STMT_NONE; 1108 return 0; 1109 } 1110 expand_statement(simple); 1111 *stmt = *simple; 1112 return SIDE_EFFECTS; 1113 } 1114 #endif 1115 expand_statement(stmt->if_true); 1116 expand_statement(stmt->if_false); 1117 return SIDE_EFFECTS; 1118 } 1119 1120 /* 1121 * Expanding a compound statement is really just 1122 * about adding up the costs of each individual 1123 * statement. 1124 * 1125 * We also collapse a simple compound statement: 1126 * this would trigger for simple inline functions, 1127 * except we would have to check the "return" 1128 * symbol usage. Next time. 1129 */ 1130 static int expand_compound(struct statement *stmt) 1131 { 1132 struct statement *s, *last; 1133 int cost, statements; 1134 1135 if (stmt->ret) 1136 expand_symbol(stmt->ret); 1137 1138 last = stmt->args; 1139 cost = expand_statement(last); 1140 statements = last != NULL; 1141 FOR_EACH_PTR(stmt->stmts, s) { 1142 statements++; 1143 last = s; 1144 cost += expand_statement(s); 1145 } END_FOR_EACH_PTR(s); 1146 1147 if (statements == 1 && !stmt->ret) 1148 *stmt = *last; 1149 1150 return cost; 1151 } 1152 1153 static int expand_statement(struct statement *stmt) 1154 { 1155 if (!stmt) 1156 return 0; 1157 1158 switch (stmt->type) { 1159 case STMT_DECLARATION: { 1160 struct symbol *sym; 1161 FOR_EACH_PTR(stmt->declaration, sym) { 1162 expand_symbol(sym); 1163 } END_FOR_EACH_PTR(sym); 1164 return SIDE_EFFECTS; 1165 } 1166 1167 case STMT_RETURN: 1168 expand_return_expression(stmt); 1169 return SIDE_EFFECTS; 1170 1171 case STMT_EXPRESSION: 1172 return expand_expression(stmt->expression); 1173 1174 case STMT_COMPOUND: 1175 return expand_compound(stmt); 1176 1177 case STMT_IF: 1178 return expand_if_statement(stmt); 1179 1180 case STMT_ITERATOR: 1181 expand_expression(stmt->iterator_pre_condition); 1182 expand_expression(stmt->iterator_post_condition); 1183 expand_statement(stmt->iterator_pre_statement); 1184 expand_statement(stmt->iterator_statement); 1185 expand_statement(stmt->iterator_post_statement); 1186 return SIDE_EFFECTS; 1187 1188 case STMT_SWITCH: 1189 expand_expression(stmt->switch_expression); 1190 expand_statement(stmt->switch_statement); 1191 return SIDE_EFFECTS; 1192 1193 case STMT_CASE: 1194 expand_const_expression(stmt->case_expression, "case statement"); 1195 expand_const_expression(stmt->case_to, "case statement"); 1196 expand_statement(stmt->case_statement); 1197 return SIDE_EFFECTS; 1198 1199 case STMT_LABEL: 1200 expand_statement(stmt->label_statement); 1201 return SIDE_EFFECTS; 1202 1203 case STMT_GOTO: 1204 expand_expression(stmt->goto_expression); 1205 return SIDE_EFFECTS; 1206 1207 case STMT_NONE: 1208 break; 1209 case STMT_ASM: 1210 /* FIXME! Do the asm parameter evaluation! */ 1211 break; 1212 case STMT_CONTEXT: 1213 expand_expression(stmt->expression); 1214 break; 1215 case STMT_RANGE: 1216 expand_expression(stmt->range_expression); 1217 expand_expression(stmt->range_low); 1218 expand_expression(stmt->range_high); 1219 break; 1220 } 1221 return SIDE_EFFECTS; 1222 } 1223 1224 static inline int bad_integer_constant_expression(struct expression *expr) 1225 { 1226 if (!(expr->flags & CEF_ICE)) 1227 return 1; 1228 if (expr->taint & Taint_comma) 1229 return 1; 1230 return 0; 1231 } 1232 1233 static long long __get_expression_value(struct expression *expr, int strict) 1234 { 1235 long long value, mask; 1236 struct symbol *ctype; 1237 1238 if (!expr) 1239 return 0; 1240 ctype = evaluate_expression(expr); 1241 if (!ctype) { 1242 expression_error(expr, "bad constant expression type"); 1243 return 0; 1244 } 1245 expand_expression(expr); 1246 if (expr->type != EXPR_VALUE) { 1247 if (strict != 2) 1248 expression_error(expr, "bad constant expression"); 1249 return 0; 1250 } 1251 if ((strict == 1) && bad_integer_constant_expression(expr)) { 1252 expression_error(expr, "bad integer constant expression"); 1253 return 0; 1254 } 1255 1256 value = expr->value; 1257 mask = 1ULL << (ctype->bit_size-1); 1258 1259 if (value & mask) { 1260 while (ctype->type != SYM_BASETYPE) 1261 ctype = ctype->ctype.base_type; 1262 if (!(ctype->ctype.modifiers & MOD_UNSIGNED)) 1263 value = value | mask | ~(mask-1); 1264 } 1265 return value; 1266 } 1267 1268 long long get_expression_value(struct expression *expr) 1269 { 1270 return __get_expression_value(expr, 0); 1271 } 1272 1273 long long const_expression_value(struct expression *expr) 1274 { 1275 return __get_expression_value(expr, 1); 1276 } 1277 1278 long long get_expression_value_silent(struct expression *expr) 1279 { 1280 1281 return __get_expression_value(expr, 2); 1282 } 1283 1284 int expr_truth_value(struct expression *expr) 1285 { 1286 const int saved = conservative; 1287 struct symbol *ctype; 1288 1289 if (!expr) 1290 return 0; 1291 1292 ctype = evaluate_expression(expr); 1293 if (!ctype) 1294 return -1; 1295 1296 conservative = 1; 1297 expand_expression(expr); 1298 conservative = saved; 1299 1300 redo: 1301 switch (expr->type) { 1302 case EXPR_COMMA: 1303 expr = expr->right; 1304 goto redo; 1305 case EXPR_VALUE: 1306 return expr->value != 0; 1307 case EXPR_FVALUE: 1308 return expr->fvalue != 0; 1309 default: 1310 return -1; 1311 } 1312 } 1313 1314 int is_zero_constant(struct expression *expr) 1315 { 1316 const int saved = conservative; 1317 conservative = 1; 1318 expand_expression(expr); 1319 conservative = saved; 1320 return expr->type == EXPR_VALUE && !expr->value; 1321 } 1322