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