1 /* 2 * Copyright (C) 2010 Dan Carpenter. 3 * 4 * This program is free software; you can redistribute it and/or 5 * modify it under the terms of the GNU General Public License 6 * as published by the Free Software Foundation; either version 2 7 * of the License, or (at your option) any later version. 8 * 9 * This program is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * GNU General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt 16 */ 17 18 #include "symbol.h" 19 #include "smatch.h" 20 #include "smatch_slist.h" 21 #include "smatch_extra.h" 22 23 static struct range_list *_get_rl(struct expression *expr, int implied, int *recurse_cnt); 24 static struct range_list *handle_variable(struct expression *expr, int implied, int *recurse_cnt); 25 static struct range_list *(*custom_handle_variable)(struct expression *expr); 26 27 static int get_implied_value_internal(struct expression *expr, sval_t *sval, int *recurse_cnt); 28 static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt); 29 30 static sval_t zero = {.type = &int_ctype, {.value = 0} }; 31 static sval_t one = {.type = &int_ctype, {.value = 1} }; 32 33 struct range_list *rl_zero(void) 34 { 35 static struct range_list *zero_perm; 36 37 if (!zero_perm) 38 zero_perm = clone_rl_permanent(alloc_rl(zero, zero)); 39 return zero_perm; 40 } 41 42 struct range_list *rl_one(void) 43 { 44 static struct range_list *one_perm; 45 46 if (!one_perm) 47 one_perm = clone_rl_permanent(alloc_rl(one, one)); 48 49 return one_perm; 50 } 51 52 enum { 53 RL_EXACT, 54 RL_HARD, 55 RL_FUZZY, 56 RL_IMPLIED, 57 RL_ABSOLUTE, 58 RL_REAL_ABSOLUTE, 59 }; 60 61 static struct range_list *last_stmt_rl(struct statement *stmt, int implied, int *recurse_cnt) 62 { 63 struct expression *expr; 64 65 if (!stmt) 66 return NULL; 67 68 stmt = last_ptr_list((struct ptr_list *)stmt->stmts); 69 if (stmt->type == STMT_LABEL) { 70 if (stmt->label_statement && 71 stmt->label_statement->type == STMT_EXPRESSION) 72 expr = stmt->label_statement->expression; 73 else 74 return NULL; 75 } else if (stmt->type == STMT_EXPRESSION) { 76 expr = stmt->expression; 77 } else { 78 return NULL; 79 } 80 return _get_rl(expr, implied, recurse_cnt); 81 } 82 83 static struct range_list *handle_expression_statement_rl(struct expression *expr, int implied, int *recurse_cnt) 84 { 85 return last_stmt_rl(get_expression_statement(expr), implied, recurse_cnt); 86 } 87 88 static struct range_list *handle_ampersand_rl(struct expression *expr, int implied, int *recurse_cnt) 89 { 90 struct range_list *rl; 91 sval_t sval; 92 93 if (implied == RL_EXACT || implied == RL_HARD) 94 return NULL; 95 if (get_mtag_sval(expr, &sval)) 96 return alloc_rl(sval, sval); 97 if (get_address_rl(expr, &rl)) 98 return rl; 99 return alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval); 100 } 101 102 static struct range_list *handle_negate_rl(struct expression *expr, int implied, int *recurse_cnt) 103 { 104 if (known_condition_true(expr->unop)) 105 return rl_zero(); 106 if (known_condition_false(expr->unop)) 107 return rl_one(); 108 109 if (implied == RL_EXACT) 110 return NULL; 111 112 if (implied_condition_true(expr->unop)) 113 return rl_zero(); 114 if (implied_condition_false(expr->unop)) 115 return rl_one(); 116 return alloc_rl(zero, one); 117 } 118 119 static struct range_list *handle_bitwise_negate(struct expression *expr, int implied, int *recurse_cnt) 120 { 121 struct range_list *rl; 122 sval_t sval; 123 124 rl = _get_rl(expr->unop, implied, recurse_cnt); 125 if (!rl_to_sval(rl, &sval)) 126 return NULL; 127 sval = sval_preop(sval, '~'); 128 sval_cast(get_type(expr->unop), sval); 129 return alloc_rl(sval, sval); 130 } 131 132 static struct range_list *handle_minus_preop(struct expression *expr, int implied, int *recurse_cnt) 133 { 134 struct range_list *rl; 135 sval_t min, max; 136 137 rl = _get_rl(expr->unop, implied, recurse_cnt); 138 min = sval_preop(rl_max(rl), '-'); 139 max = sval_preop(rl_min(rl), '-'); 140 return alloc_rl(min, max); 141 } 142 143 static struct range_list *handle_preop_rl(struct expression *expr, int implied, int *recurse_cnt) 144 { 145 switch (expr->op) { 146 case '&': 147 return handle_ampersand_rl(expr, implied, recurse_cnt); 148 case '!': 149 return handle_negate_rl(expr, implied, recurse_cnt); 150 case '~': 151 return handle_bitwise_negate(expr, implied, recurse_cnt); 152 case '-': 153 return handle_minus_preop(expr, implied, recurse_cnt); 154 case '*': 155 return handle_variable(expr, implied, recurse_cnt); 156 case '(': 157 return handle_expression_statement_rl(expr, implied, recurse_cnt); 158 default: 159 return NULL; 160 } 161 } 162 163 static struct range_list *handle_divide_rl(struct expression *expr, int implied, int *recurse_cnt) 164 { 165 struct range_list *left_rl, *right_rl; 166 struct symbol *type; 167 168 type = get_type(expr); 169 170 left_rl = _get_rl(expr->left, implied, recurse_cnt); 171 left_rl = cast_rl(type, left_rl); 172 right_rl = _get_rl(expr->right, implied, recurse_cnt); 173 right_rl = cast_rl(type, right_rl); 174 175 if (!left_rl || !right_rl) 176 return NULL; 177 178 if (implied != RL_REAL_ABSOLUTE) { 179 if (is_whole_rl(left_rl) || is_whole_rl(right_rl)) 180 return NULL; 181 } 182 183 return rl_binop(left_rl, '/', right_rl); 184 } 185 186 static int handle_offset_subtraction(struct expression *expr) 187 { 188 struct expression *left, *right; 189 struct symbol *left_sym, *right_sym; 190 struct symbol *type; 191 int left_offset, right_offset; 192 193 type = get_type(expr); 194 if (!type || type->type != SYM_PTR) 195 return -1; 196 type = get_real_base_type(type); 197 if (!type || (type_bits(type) != 8 && (type != &void_ctype))) 198 return -1; 199 200 left = strip_expr(expr->left); 201 right = strip_expr(expr->right); 202 203 if (left->type != EXPR_PREOP || left->op != '&') 204 return -1; 205 left = strip_expr(left->unop); 206 207 left_sym = expr_to_sym(left); 208 right_sym = expr_to_sym(right); 209 if (!left_sym || left_sym != right_sym) 210 return -1; 211 212 left_offset = get_member_offset_from_deref(left); 213 if (right->type == EXPR_SYMBOL) 214 right_offset = 0; 215 else { 216 if (right->type != EXPR_PREOP || right->op != '&') 217 return -1; 218 right = strip_expr(right->unop); 219 right_offset = get_member_offset_from_deref(right); 220 } 221 if (left_offset < 0 || right_offset < 0) 222 return -1; 223 224 return left_offset - right_offset; 225 } 226 227 static struct range_list *handle_subtract_rl(struct expression *expr, int implied, int *recurse_cnt) 228 { 229 struct symbol *type; 230 struct range_list *left_orig, *right_orig; 231 struct range_list *left_rl, *right_rl; 232 sval_t max, min, tmp; 233 int comparison; 234 int offset; 235 236 type = get_type(expr); 237 238 offset = handle_offset_subtraction(expr); 239 if (offset >= 0) { 240 tmp.type = type; 241 tmp.value = offset; 242 243 return alloc_rl(tmp, tmp); 244 } 245 246 comparison = get_comparison(expr->left, expr->right); 247 248 left_orig = _get_rl(expr->left, implied, recurse_cnt); 249 left_rl = cast_rl(type, left_orig); 250 right_orig = _get_rl(expr->right, implied, recurse_cnt); 251 right_rl = cast_rl(type, right_orig); 252 253 if ((!left_rl || !right_rl) && 254 (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY)) 255 return NULL; 256 257 if (!left_rl) 258 left_rl = alloc_whole_rl(type); 259 if (!right_rl) 260 right_rl = alloc_whole_rl(type); 261 262 /* negative values complicate everything fix this later */ 263 if (sval_is_negative(rl_min(right_rl))) 264 return NULL; 265 max = rl_max(left_rl); 266 min = sval_type_min(type); 267 268 switch (comparison) { 269 case '>': 270 case SPECIAL_UNSIGNED_GT: 271 min = sval_type_val(type, 1); 272 max = rl_max(left_rl); 273 break; 274 case SPECIAL_GTE: 275 case SPECIAL_UNSIGNED_GTE: 276 min = sval_type_val(type, 0); 277 max = rl_max(left_rl); 278 break; 279 case SPECIAL_EQUAL: 280 min = sval_type_val(type, 0); 281 max = sval_type_val(type, 0); 282 break; 283 case '<': 284 case SPECIAL_UNSIGNED_LT: 285 max = sval_type_val(type, -1); 286 break; 287 case SPECIAL_LTE: 288 case SPECIAL_UNSIGNED_LTE: 289 max = sval_type_val(type, 0); 290 break; 291 default: 292 if (!left_orig || !right_orig) 293 return NULL; 294 return rl_binop(left_rl, '-', right_rl); 295 } 296 297 if (!sval_binop_overflows(rl_min(left_rl), '-', rl_max(right_rl))) { 298 tmp = sval_binop(rl_min(left_rl), '-', rl_max(right_rl)); 299 if (sval_cmp(tmp, min) > 0) 300 min = tmp; 301 } 302 303 if (!sval_is_max(rl_max(left_rl))) { 304 tmp = sval_binop(rl_max(left_rl), '-', rl_min(right_rl)); 305 if (sval_cmp(tmp, max) < 0) 306 max = tmp; 307 } 308 309 if (sval_is_min(min) && sval_is_max(max)) 310 return NULL; 311 312 return cast_rl(type, alloc_rl(min, max)); 313 } 314 315 static struct range_list *handle_mod_rl(struct expression *expr, int implied, int *recurse_cnt) 316 { 317 struct range_list *rl; 318 sval_t left, right, sval; 319 320 if (implied == RL_EXACT) { 321 if (!get_implied_value(expr->right, &right)) 322 return NULL; 323 if (!get_implied_value(expr->left, &left)) 324 return NULL; 325 sval = sval_binop(left, '%', right); 326 return alloc_rl(sval, sval); 327 } 328 /* if we can't figure out the right side it's probably hopeless */ 329 if (!get_implied_value_internal(expr->right, &right, recurse_cnt)) 330 return NULL; 331 332 right = sval_cast(get_type(expr), right); 333 right.value--; 334 335 rl = _get_rl(expr->left, implied, recurse_cnt); 336 if (rl && rl_max(rl).uvalue < right.uvalue) 337 right.uvalue = rl_max(rl).uvalue; 338 339 return alloc_rl(sval_cast(right.type, zero), right); 340 } 341 342 static sval_t sval_lowest_set_bit(sval_t sval) 343 { 344 int i; 345 int found = 0; 346 347 for (i = 0; i < 64; i++) { 348 if (sval.uvalue & 1ULL << i) { 349 if (!found++) 350 continue; 351 sval.uvalue &= ~(1ULL << i); 352 } 353 } 354 return sval; 355 } 356 357 static struct range_list *handle_bitwise_AND(struct expression *expr, int implied, int *recurse_cnt) 358 { 359 struct symbol *type; 360 struct range_list *left_rl, *right_rl; 361 sval_t known; 362 int new_recurse; 363 364 if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE) 365 return NULL; 366 367 type = get_type(expr); 368 369 if (get_implied_value_internal(expr->left, &known, recurse_cnt)) { 370 sval_t min; 371 372 min = sval_lowest_set_bit(known); 373 left_rl = alloc_rl(min, known); 374 left_rl = cast_rl(type, left_rl); 375 add_range(&left_rl, sval_type_val(type, 0), sval_type_val(type, 0)); 376 } else { 377 left_rl = _get_rl(expr->left, implied, recurse_cnt); 378 if (left_rl) { 379 left_rl = cast_rl(type, left_rl); 380 left_rl = alloc_rl(sval_type_val(type, 0), rl_max(left_rl)); 381 } else { 382 if (implied == RL_HARD) 383 return NULL; 384 left_rl = alloc_whole_rl(type); 385 } 386 } 387 388 new_recurse = *recurse_cnt; 389 if (*recurse_cnt >= 200) 390 new_recurse = 100; /* Let's try super hard to get the mask */ 391 if (get_implied_value_internal(expr->right, &known, &new_recurse)) { 392 sval_t min, left_max, mod; 393 394 *recurse_cnt = new_recurse; 395 396 min = sval_lowest_set_bit(known); 397 right_rl = alloc_rl(min, known); 398 right_rl = cast_rl(type, right_rl); 399 add_range(&right_rl, sval_type_val(type, 0), sval_type_val(type, 0)); 400 401 if (min.value != 0) { 402 left_max = rl_max(left_rl); 403 mod = sval_binop(left_max, '%', min); 404 if (mod.value) { 405 left_max = sval_binop(left_max, '-', mod); 406 left_max.value++; 407 if (left_max.value > 0 && sval_cmp(left_max, rl_max(left_rl)) < 0) 408 left_rl = remove_range(left_rl, left_max, rl_max(left_rl)); 409 } 410 } 411 } else { 412 right_rl = _get_rl(expr->right, implied, recurse_cnt); 413 if (right_rl) { 414 right_rl = cast_rl(type, right_rl); 415 right_rl = alloc_rl(sval_type_val(type, 0), rl_max(right_rl)); 416 } else { 417 if (implied == RL_HARD) 418 return NULL; 419 right_rl = alloc_whole_rl(type); 420 } 421 } 422 423 return rl_intersection(left_rl, right_rl); 424 } 425 426 static struct range_list *use_rl_binop(struct expression *expr, int implied, int *recurse_cnt) 427 { 428 struct symbol *type; 429 struct range_list *left_rl, *right_rl; 430 431 if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE) 432 return NULL; 433 434 type = get_type(expr); 435 436 get_absolute_rl_internal(expr->left, &left_rl, recurse_cnt); 437 get_absolute_rl_internal(expr->right, &right_rl, recurse_cnt); 438 left_rl = cast_rl(type, left_rl); 439 right_rl = cast_rl(type, right_rl); 440 if (!left_rl || !right_rl) 441 return NULL; 442 443 return rl_binop(left_rl, expr->op, right_rl); 444 } 445 446 static struct range_list *handle_right_shift(struct expression *expr, int implied, int *recurse_cnt) 447 { 448 struct range_list *left_rl; 449 sval_t right; 450 sval_t min, max; 451 452 if (implied == RL_EXACT || implied == RL_HARD) 453 return NULL; 454 455 left_rl = _get_rl(expr->left, implied, recurse_cnt); 456 if (left_rl) { 457 max = rl_max(left_rl); 458 min = rl_min(left_rl); 459 } else { 460 if (implied == RL_FUZZY) 461 return NULL; 462 max = sval_type_max(get_type(expr->left)); 463 min = sval_type_val(get_type(expr->left), 0); 464 } 465 466 if (get_implied_value_internal(expr->right, &right, recurse_cnt)) { 467 min = sval_binop(min, SPECIAL_RIGHTSHIFT, right); 468 max = sval_binop(max, SPECIAL_RIGHTSHIFT, right); 469 } else if (!sval_is_negative(min)) { 470 min.value = 0; 471 max = sval_type_max(max.type); 472 } else { 473 return NULL; 474 } 475 476 return alloc_rl(min, max); 477 } 478 479 static struct range_list *handle_left_shift(struct expression *expr, int implied, int *recurse_cnt) 480 { 481 struct range_list *left_rl, *res; 482 sval_t right; 483 sval_t min, max; 484 int add_zero = 0; 485 486 if (implied == RL_EXACT || implied == RL_HARD) 487 return NULL; 488 /* this is hopeless without the right side */ 489 if (!get_implied_value_internal(expr->right, &right, recurse_cnt)) 490 return NULL; 491 left_rl = _get_rl(expr->left, implied, recurse_cnt); 492 if (left_rl) { 493 max = rl_max(left_rl); 494 min = rl_min(left_rl); 495 if (min.value == 0) { 496 min.value = 1; 497 add_zero = 1; 498 } 499 } else { 500 if (implied == RL_FUZZY) 501 return NULL; 502 max = sval_type_max(get_type(expr->left)); 503 min = sval_type_val(get_type(expr->left), 1); 504 add_zero = 1; 505 } 506 507 max = sval_binop(max, SPECIAL_LEFTSHIFT, right); 508 min = sval_binop(min, SPECIAL_LEFTSHIFT, right); 509 res = alloc_rl(min, max); 510 if (add_zero) 511 res = rl_union(res, rl_zero()); 512 return res; 513 } 514 515 static struct range_list *handle_known_binop(struct expression *expr) 516 { 517 sval_t left, right; 518 519 if (!get_value(expr->left, &left)) 520 return NULL; 521 if (!get_value(expr->right, &right)) 522 return NULL; 523 left = sval_binop(left, expr->op, right); 524 return alloc_rl(left, left); 525 } 526 527 static int has_actual_ranges(struct range_list *rl) 528 { 529 struct data_range *tmp; 530 531 FOR_EACH_PTR(rl, tmp) { 532 if (sval_cmp(tmp->min, tmp->max) != 0) 533 return 1; 534 } END_FOR_EACH_PTR(tmp); 535 return 0; 536 } 537 538 static struct range_list *handle_implied_binop(struct range_list *left_rl, int op, struct range_list *right_rl) 539 { 540 struct range_list *res_rl; 541 struct data_range *left_drange, *right_drange; 542 sval_t res; 543 544 if (!left_rl || !right_rl) 545 return NULL; 546 if (has_actual_ranges(left_rl)) 547 return NULL; 548 if (has_actual_ranges(right_rl)) 549 return NULL; 550 551 if (ptr_list_size((struct ptr_list *)left_rl) * ptr_list_size((struct ptr_list *)right_rl) > 20) 552 return NULL; 553 554 res_rl = NULL; 555 556 FOR_EACH_PTR(left_rl, left_drange) { 557 FOR_EACH_PTR(right_rl, right_drange) { 558 if ((op == '%' || op == '/') && 559 right_drange->min.value == 0) 560 return NULL; 561 res = sval_binop(left_drange->min, op, right_drange->min); 562 add_range(&res_rl, res, res); 563 } END_FOR_EACH_PTR(right_drange); 564 } END_FOR_EACH_PTR(left_drange); 565 566 return res_rl; 567 } 568 569 static struct range_list *handle_binop_rl(struct expression *expr, int implied, int *recurse_cnt) 570 { 571 struct smatch_state *state; 572 struct symbol *type; 573 struct range_list *left_rl, *right_rl, *rl; 574 sval_t min, max; 575 576 rl = handle_known_binop(expr); 577 if (rl) 578 return rl; 579 if (implied == RL_EXACT) 580 return NULL; 581 582 if (custom_handle_variable) { 583 rl = custom_handle_variable(expr); 584 if (rl) 585 return rl; 586 } 587 588 state = get_extra_state(expr); 589 if (state && !is_whole_rl(estate_rl(state))) { 590 if (implied != RL_HARD || estate_has_hard_max(state)) 591 return clone_rl(estate_rl(state)); 592 } 593 594 type = get_type(expr); 595 left_rl = _get_rl(expr->left, implied, recurse_cnt); 596 left_rl = cast_rl(type, left_rl); 597 right_rl = _get_rl(expr->right, implied, recurse_cnt); 598 right_rl = cast_rl(type, right_rl); 599 600 if (!left_rl && !right_rl) 601 return NULL; 602 603 rl = handle_implied_binop(left_rl, expr->op, right_rl); 604 if (rl) 605 return rl; 606 607 switch (expr->op) { 608 case '%': 609 return handle_mod_rl(expr, implied, recurse_cnt); 610 case '&': 611 return handle_bitwise_AND(expr, implied, recurse_cnt); 612 case '|': 613 case '^': 614 return use_rl_binop(expr, implied, recurse_cnt); 615 case SPECIAL_RIGHTSHIFT: 616 return handle_right_shift(expr, implied, recurse_cnt); 617 case SPECIAL_LEFTSHIFT: 618 return handle_left_shift(expr, implied, recurse_cnt); 619 case '-': 620 return handle_subtract_rl(expr, implied, recurse_cnt); 621 case '/': 622 return handle_divide_rl(expr, implied, recurse_cnt); 623 } 624 625 if (!left_rl || !right_rl) 626 return NULL; 627 628 if (sval_binop_overflows(rl_min(left_rl), expr->op, rl_min(right_rl))) 629 return NULL; 630 if (sval_binop_overflows(rl_max(left_rl), expr->op, rl_max(right_rl))) 631 return NULL; 632 633 min = sval_binop(rl_min(left_rl), expr->op, rl_min(right_rl)); 634 max = sval_binop(rl_max(left_rl), expr->op, rl_max(right_rl)); 635 636 return alloc_rl(min, max); 637 } 638 639 static int do_comparison(struct expression *expr) 640 { 641 struct range_list *left_ranges = NULL; 642 struct range_list *right_ranges = NULL; 643 int poss_true, poss_false; 644 struct symbol *type; 645 646 type = get_type(expr); 647 get_absolute_rl(expr->left, &left_ranges); 648 get_absolute_rl(expr->right, &right_ranges); 649 650 left_ranges = cast_rl(type, left_ranges); 651 right_ranges = cast_rl(type, right_ranges); 652 653 poss_true = possibly_true_rl(left_ranges, expr->op, right_ranges); 654 poss_false = possibly_false_rl(left_ranges, expr->op, right_ranges); 655 656 if (!poss_true && !poss_false) 657 return 0x0; 658 if (poss_true && !poss_false) 659 return 0x1; 660 if (!poss_true && poss_false) 661 return 0x2; 662 return 0x3; 663 } 664 665 static struct range_list *handle_comparison_rl(struct expression *expr, int implied, int *recurse_cnt) 666 { 667 sval_t left, right; 668 int res; 669 670 if (expr->op == SPECIAL_EQUAL && expr->left->type == EXPR_TYPE) { 671 struct symbol *left, *right; 672 673 left = get_real_base_type(expr->left->symbol); 674 right = get_real_base_type(expr->left->symbol); 675 if (left == right) 676 return rl_one(); 677 return rl_zero(); 678 } 679 680 if (get_value(expr->left, &left) && get_value(expr->right, &right)) { 681 struct data_range tmp_left, tmp_right; 682 683 tmp_left.min = left; 684 tmp_left.max = left; 685 tmp_right.min = right; 686 tmp_right.max = right; 687 if (true_comparison_range(&tmp_left, expr->op, &tmp_right)) 688 return rl_one(); 689 return rl_zero(); 690 } 691 692 if (implied == RL_EXACT) 693 return NULL; 694 695 res = do_comparison(expr); 696 if (res == 1) 697 return rl_one(); 698 if (res == 2) 699 return rl_zero(); 700 701 return alloc_rl(zero, one); 702 } 703 704 static struct range_list *handle_logical_rl(struct expression *expr, int implied, int *recurse_cnt) 705 { 706 sval_t left, right; 707 int left_known = 0; 708 int right_known = 0; 709 710 if (implied == RL_EXACT) { 711 if (get_value(expr->left, &left)) 712 left_known = 1; 713 if (get_value(expr->right, &right)) 714 right_known = 1; 715 } else { 716 if (get_implied_value_internal(expr->left, &left, recurse_cnt)) 717 left_known = 1; 718 if (get_implied_value_internal(expr->right, &right, recurse_cnt)) 719 right_known = 1; 720 } 721 722 switch (expr->op) { 723 case SPECIAL_LOGICAL_OR: 724 if (left_known && left.value) 725 return rl_one(); 726 if (right_known && right.value) 727 return rl_one(); 728 if (left_known && right_known) 729 return rl_zero(); 730 break; 731 case SPECIAL_LOGICAL_AND: 732 if (left_known && right_known) { 733 if (left.value && right.value) 734 return rl_one(); 735 return rl_zero(); 736 } 737 break; 738 default: 739 return NULL; 740 } 741 742 if (implied == RL_EXACT) 743 return NULL; 744 745 return alloc_rl(zero, one); 746 } 747 748 static struct range_list *handle_conditional_rl(struct expression *expr, int implied, int *recurse_cnt) 749 { 750 struct expression *cond_true; 751 struct range_list *true_rl, *false_rl; 752 struct symbol *type; 753 int final_pass_orig = final_pass; 754 755 cond_true = expr->cond_true; 756 if (!cond_true) 757 cond_true = expr->conditional; 758 759 if (known_condition_true(expr->conditional)) 760 return _get_rl(cond_true, implied, recurse_cnt); 761 if (known_condition_false(expr->conditional)) 762 return _get_rl(expr->cond_false, implied, recurse_cnt); 763 764 if (implied == RL_EXACT) 765 return NULL; 766 767 if (implied_condition_true(expr->conditional)) 768 return _get_rl(cond_true, implied, recurse_cnt); 769 if (implied_condition_false(expr->conditional)) 770 return _get_rl(expr->cond_false, implied, recurse_cnt); 771 772 773 /* this becomes a problem with deeply nested conditional statements */ 774 if (low_on_memory()) 775 return NULL; 776 777 type = get_type(expr); 778 779 __push_fake_cur_stree(); 780 final_pass = 0; 781 __split_whole_condition(expr->conditional); 782 true_rl = _get_rl(cond_true, implied, recurse_cnt); 783 __push_true_states(); 784 __use_false_states(); 785 false_rl = _get_rl(expr->cond_false, implied, recurse_cnt); 786 __merge_true_states(); 787 __free_fake_cur_stree(); 788 final_pass = final_pass_orig; 789 790 if (!true_rl || !false_rl) 791 return NULL; 792 true_rl = cast_rl(type, true_rl); 793 false_rl = cast_rl(type, false_rl); 794 795 return rl_union(true_rl, false_rl); 796 } 797 798 static int get_fuzzy_max_helper(struct expression *expr, sval_t *max) 799 { 800 struct smatch_state *state; 801 sval_t sval; 802 803 if (get_hard_max(expr, &sval)) { 804 *max = sval; 805 return 1; 806 } 807 808 state = get_extra_state(expr); 809 if (!state || !estate_has_fuzzy_max(state)) 810 return 0; 811 *max = sval_cast(get_type(expr), estate_get_fuzzy_max(state)); 812 return 1; 813 } 814 815 static int get_fuzzy_min_helper(struct expression *expr, sval_t *min) 816 { 817 struct smatch_state *state; 818 sval_t sval; 819 820 state = get_extra_state(expr); 821 if (!state || !estate_rl(state)) 822 return 0; 823 824 sval = estate_min(state); 825 if (sval_is_negative(sval) && sval_is_min(sval)) 826 return 0; 827 828 if (sval_is_max(sval)) 829 return 0; 830 831 *min = sval_cast(get_type(expr), sval); 832 return 1; 833 } 834 835 int get_const_value(struct expression *expr, sval_t *sval) 836 { 837 struct symbol *sym; 838 sval_t right; 839 840 if (expr->type != EXPR_SYMBOL || !expr->symbol) 841 return 0; 842 sym = expr->symbol; 843 if (!(sym->ctype.modifiers & MOD_CONST)) 844 return 0; 845 if (get_value(sym->initializer, &right)) { 846 *sval = sval_cast(get_type(expr), right); 847 return 1; 848 } 849 return 0; 850 } 851 852 struct range_list *var_to_absolute_rl(struct expression *expr) 853 { 854 struct smatch_state *state; 855 struct range_list *rl; 856 857 state = get_extra_state(expr); 858 if (!state || is_whole_rl(estate_rl(state))) { 859 state = get_real_absolute_state(expr); 860 if (state && state->data && !estate_is_whole(state)) 861 return clone_rl(estate_rl(state)); 862 if (get_local_rl(expr, &rl) && !is_whole_rl(rl)) 863 return rl; 864 if (get_mtag_rl(expr, &rl)) 865 return rl; 866 if (get_db_type_rl(expr, &rl) && !is_whole_rl(rl)) 867 return rl; 868 return alloc_whole_rl(get_type(expr)); 869 } 870 /* err on the side of saying things are possible */ 871 if (!estate_rl(state)) 872 return alloc_whole_rl(get_type(expr)); 873 return clone_rl(estate_rl(state)); 874 } 875 876 static struct range_list *handle_variable(struct expression *expr, int implied, int *recurse_cnt) 877 { 878 struct smatch_state *state; 879 struct range_list *rl; 880 sval_t sval, min, max; 881 struct symbol *type; 882 883 if (get_const_value(expr, &sval)) 884 return alloc_rl(sval, sval); 885 886 if (custom_handle_variable) { 887 rl = custom_handle_variable(expr); 888 if (!rl) 889 return var_to_absolute_rl(expr); 890 return rl; 891 } 892 893 if (implied == RL_EXACT) 894 return NULL; 895 896 if (get_mtag_sval(expr, &sval)) 897 return alloc_rl(sval, sval); 898 899 type = get_type(expr); 900 if (type && type->type == SYM_FN) 901 return alloc_rl(fn_ptr_min, fn_ptr_max); 902 903 switch (implied) { 904 case RL_HARD: 905 case RL_IMPLIED: 906 case RL_ABSOLUTE: 907 state = get_extra_state(expr); 908 if (!state || !state->data) { 909 if (implied == RL_HARD) 910 return NULL; 911 if (get_local_rl(expr, &rl)) 912 return rl; 913 if (get_mtag_rl(expr, &rl)) 914 return rl; 915 if (get_db_type_rl(expr, &rl)) 916 return rl; 917 if (is_array(expr) && get_array_rl(expr, &rl)) 918 return rl; 919 return NULL; 920 } 921 if (implied == RL_HARD && !estate_has_hard_max(state)) 922 return NULL; 923 return clone_rl(estate_rl(state)); 924 case RL_REAL_ABSOLUTE: { 925 struct smatch_state *abs_state; 926 927 state = get_extra_state(expr); 928 abs_state = get_real_absolute_state(expr); 929 930 if (estate_rl(state) && estate_rl(abs_state)) { 931 return clone_rl(rl_intersection(estate_rl(state), 932 estate_rl(abs_state))); 933 } else if (estate_rl(state)) { 934 return clone_rl(estate_rl(state)); 935 } else if (estate_is_empty(state)) { 936 /* 937 * FIXME: we don't handle empty extra states correctly. 938 * 939 * The real abs rl is supposed to be filtered by the 940 * extra state if there is one. We don't bother keeping 941 * the abs state in sync all the time because we know it 942 * will be filtered later. 943 * 944 * It's not totally obvious to me how they should be 945 * handled. Perhaps we should take the whole rl and 946 * filter by the imaginary states. Perhaps we should 947 * just go with the empty state. 948 * 949 * Anyway what we currently do is return NULL here and 950 * that gets translated into the whole range in 951 * get_real_absolute_rl(). 952 * 953 */ 954 return NULL; 955 } else if (estate_rl(abs_state)) { 956 return clone_rl(estate_rl(abs_state)); 957 } 958 959 if (get_local_rl(expr, &rl)) 960 return rl; 961 if (get_mtag_rl(expr, &rl)) 962 return rl; 963 if (get_db_type_rl(expr, &rl)) 964 return rl; 965 if (is_array(expr) && get_array_rl(expr, &rl)) 966 return rl; 967 return NULL; 968 } 969 case RL_FUZZY: 970 if (!get_fuzzy_min_helper(expr, &min)) 971 min = sval_type_min(get_type(expr)); 972 if (!get_fuzzy_max_helper(expr, &max)) 973 return NULL; 974 /* fuzzy ranges are often inverted */ 975 if (sval_cmp(min, max) > 0) { 976 sval = min; 977 min = max; 978 max = sval; 979 } 980 return alloc_rl(min, max); 981 } 982 return NULL; 983 } 984 985 static sval_t handle_sizeof(struct expression *expr) 986 { 987 struct symbol *sym; 988 sval_t ret; 989 990 ret = sval_blank(expr); 991 sym = expr->cast_type; 992 if (!sym) { 993 sym = evaluate_expression(expr->cast_expression); 994 if (!sym) { 995 __silence_warnings_for_stmt = true; 996 sym = &int_ctype; 997 } 998 #if 0 999 /* 1000 * Expressions of restricted types will possibly get 1001 * promoted - check that here. I'm not sure how this works, 1002 * the problem is that sizeof(le16) shouldn't be promoted and 1003 * the original code did that... Let's if zero this out and 1004 * see what breaks. 1005 */ 1006 1007 if (is_restricted_type(sym)) { 1008 if (type_bits(sym) < bits_in_int) 1009 sym = &int_ctype; 1010 } 1011 #endif 1012 if (is_fouled_type(sym)) 1013 sym = &int_ctype; 1014 } 1015 examine_symbol_type(sym); 1016 1017 ret.type = size_t_ctype; 1018 if (type_bits(sym) <= 0) /* sizeof(void) */ { 1019 if (get_real_base_type(sym) == &void_ctype) 1020 ret.value = 1; 1021 else 1022 ret.value = 0; 1023 } else 1024 ret.value = type_bytes(sym); 1025 1026 return ret; 1027 } 1028 1029 static struct range_list *handle_strlen(struct expression *expr, int implied, int *recurse_cnt) 1030 { 1031 struct range_list *rl; 1032 struct expression *arg, *tmp; 1033 sval_t tag; 1034 sval_t ret = { .type = &ulong_ctype }; 1035 1036 if (implied == RL_EXACT) 1037 return NULL; 1038 1039 arg = get_argument_from_call_expr(expr->args, 0); 1040 if (!arg) 1041 return NULL; 1042 if (arg->type == EXPR_STRING) { 1043 ret.value = arg->string->length - 1; 1044 return alloc_rl(ret, ret); 1045 } 1046 if (get_implied_value(arg, &tag) && 1047 (tmp = fake_string_from_mtag(tag.uvalue))) { 1048 ret.value = tmp->string->length - 1; 1049 return alloc_rl(ret, ret); 1050 } 1051 1052 if (implied == RL_HARD || implied == RL_FUZZY) 1053 return NULL; 1054 1055 if (get_implied_return(expr, &rl)) 1056 return rl; 1057 1058 return NULL; 1059 } 1060 1061 static struct range_list *handle_builtin_constant_p(struct expression *expr, int implied, int *recurse_cnt) 1062 { 1063 struct expression *arg; 1064 struct range_list *rl; 1065 sval_t sval; 1066 1067 arg = get_argument_from_call_expr(expr->args, 0); 1068 rl = _get_rl(arg, RL_EXACT, recurse_cnt); 1069 if (rl_to_sval(rl, &sval)) 1070 return rl_one(); 1071 return rl_zero(); 1072 } 1073 1074 static struct range_list *handle__builtin_choose_expr(struct expression *expr, int implied, int *recurse_cnt) 1075 { 1076 struct expression *const_expr, *expr1, *expr2; 1077 sval_t sval; 1078 1079 const_expr = get_argument_from_call_expr(expr->args, 0); 1080 expr1 = get_argument_from_call_expr(expr->args, 1); 1081 expr2 = get_argument_from_call_expr(expr->args, 2); 1082 1083 if (!get_value(const_expr, &sval) || !expr1 || !expr2) 1084 return NULL; 1085 if (sval.value) 1086 return _get_rl(expr1, implied, recurse_cnt); 1087 return _get_rl(expr2, implied, recurse_cnt); 1088 } 1089 1090 static struct range_list *handle_call_rl(struct expression *expr, int implied, int *recurse_cnt) 1091 { 1092 struct range_list *rl; 1093 1094 if (sym_name_is("__builtin_constant_p", expr->fn)) 1095 return handle_builtin_constant_p(expr, implied, recurse_cnt); 1096 1097 if (sym_name_is("__builtin_choose_expr", expr->fn)) 1098 return handle__builtin_choose_expr(expr, implied, recurse_cnt); 1099 1100 if (sym_name_is("__builtin_expect", expr->fn) || 1101 sym_name_is("__builtin_bswap16", expr->fn) || 1102 sym_name_is("__builtin_bswap32", expr->fn) || 1103 sym_name_is("__builtin_bswap64", expr->fn)) { 1104 struct expression *arg; 1105 1106 arg = get_argument_from_call_expr(expr->args, 0); 1107 return _get_rl(arg, implied, recurse_cnt); 1108 } 1109 1110 if (sym_name_is("strlen", expr->fn)) 1111 return handle_strlen(expr, implied, recurse_cnt); 1112 1113 if (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY) 1114 return NULL; 1115 1116 if (custom_handle_variable) { 1117 rl = custom_handle_variable(expr); 1118 if (rl) 1119 return rl; 1120 } 1121 1122 if (get_implied_return(expr, &rl)) 1123 return rl; 1124 return db_return_vals(expr); 1125 } 1126 1127 static struct range_list *handle_cast(struct expression *expr, int implied, int *recurse_cnt) 1128 { 1129 struct range_list *rl; 1130 struct symbol *type; 1131 1132 type = get_type(expr); 1133 rl = _get_rl(expr->cast_expression, implied, recurse_cnt); 1134 if (rl) 1135 return cast_rl(type, rl); 1136 if (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE) 1137 return alloc_whole_rl(type); 1138 if (implied == RL_IMPLIED && type && 1139 type_bits(type) > 0 && type_bits(type) < 32) 1140 return alloc_whole_rl(type); 1141 return NULL; 1142 } 1143 1144 static struct range_list *_get_rl(struct expression *expr, int implied, int *recurse_cnt) 1145 { 1146 struct range_list *rl; 1147 struct symbol *type; 1148 sval_t sval; 1149 1150 type = get_type(expr); 1151 expr = strip_parens(expr); 1152 if (!expr) 1153 return NULL; 1154 1155 if (++(*recurse_cnt) >= 200) 1156 return NULL; 1157 1158 switch(expr->type) { 1159 case EXPR_CAST: 1160 case EXPR_FORCE_CAST: 1161 case EXPR_IMPLIED_CAST: 1162 rl = handle_cast(expr, implied, recurse_cnt); 1163 goto out_cast; 1164 } 1165 1166 expr = strip_expr(expr); 1167 if (!expr) 1168 return NULL; 1169 1170 switch (expr->type) { 1171 case EXPR_VALUE: 1172 sval = sval_from_val(expr, expr->value); 1173 rl = alloc_rl(sval, sval); 1174 break; 1175 case EXPR_PREOP: 1176 rl = handle_preop_rl(expr, implied, recurse_cnt); 1177 break; 1178 case EXPR_POSTOP: 1179 rl = _get_rl(expr->unop, implied, recurse_cnt); 1180 break; 1181 case EXPR_BINOP: 1182 rl = handle_binop_rl(expr, implied, recurse_cnt); 1183 break; 1184 case EXPR_COMPARE: 1185 rl = handle_comparison_rl(expr, implied, recurse_cnt); 1186 break; 1187 case EXPR_LOGICAL: 1188 rl = handle_logical_rl(expr, implied, recurse_cnt); 1189 break; 1190 case EXPR_PTRSIZEOF: 1191 case EXPR_SIZEOF: 1192 sval = handle_sizeof(expr); 1193 rl = alloc_rl(sval, sval); 1194 break; 1195 case EXPR_SELECT: 1196 case EXPR_CONDITIONAL: 1197 rl = handle_conditional_rl(expr, implied, recurse_cnt); 1198 break; 1199 case EXPR_CALL: 1200 rl = handle_call_rl(expr, implied, recurse_cnt); 1201 break; 1202 case EXPR_STRING: 1203 rl = NULL; 1204 if (get_mtag_sval(expr, &sval)) 1205 rl = alloc_rl(sval, sval); 1206 break; 1207 default: 1208 rl = handle_variable(expr, implied, recurse_cnt); 1209 } 1210 1211 out_cast: 1212 if (rl) 1213 return rl; 1214 if (type && (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE)) 1215 return alloc_whole_rl(type); 1216 return NULL; 1217 } 1218 1219 struct { 1220 struct expression *expr; 1221 struct range_list *rl; 1222 } cached_results[24]; 1223 static int cache_idx; 1224 1225 void clear_math_cache(void) 1226 { 1227 memset(cached_results, 0, sizeof(cached_results)); 1228 } 1229 1230 /* returns 1 if it can get a value literal or else returns 0 */ 1231 int get_value(struct expression *expr, sval_t *sval) 1232 { 1233 struct range_list *(*orig_custom_fn)(struct expression *expr); 1234 struct range_list *rl; 1235 int recurse_cnt = 0; 1236 sval_t tmp; 1237 int i; 1238 1239 /* 1240 * This only handles RL_EXACT because other expr statements can be 1241 * different at different points. Like the list iterator, for example. 1242 */ 1243 for (i = 0; i < ARRAY_SIZE(cached_results); i++) { 1244 if (expr == cached_results[i].expr) 1245 return rl_to_sval(cached_results[i].rl, sval); 1246 } 1247 1248 orig_custom_fn = custom_handle_variable; 1249 custom_handle_variable = NULL; 1250 rl = _get_rl(expr, RL_EXACT, &recurse_cnt); 1251 if (!rl_to_sval(rl, &tmp)) 1252 rl = NULL; 1253 custom_handle_variable = orig_custom_fn; 1254 1255 cached_results[cache_idx].expr = expr; 1256 cached_results[cache_idx].rl = rl; 1257 cache_idx = (cache_idx + 1) % ARRAY_SIZE(cached_results); 1258 1259 if (!rl) 1260 return 0; 1261 1262 *sval = tmp; 1263 return 1; 1264 } 1265 1266 static int get_implied_value_internal(struct expression *expr, sval_t *sval, int *recurse_cnt) 1267 { 1268 struct range_list *rl; 1269 1270 rl = _get_rl(expr, RL_IMPLIED, recurse_cnt); 1271 if (!rl_to_sval(rl, sval)) 1272 return 0; 1273 return 1; 1274 } 1275 1276 int get_implied_value(struct expression *expr, sval_t *sval) 1277 { 1278 struct range_list *rl; 1279 int recurse_cnt = 0; 1280 1281 rl = _get_rl(expr, RL_IMPLIED, &recurse_cnt); 1282 if (!rl_to_sval(rl, sval)) 1283 return 0; 1284 return 1; 1285 } 1286 1287 int get_implied_min(struct expression *expr, sval_t *sval) 1288 { 1289 struct range_list *rl; 1290 int recurse_cnt = 0; 1291 1292 rl = _get_rl(expr, RL_IMPLIED, &recurse_cnt); 1293 if (!rl) 1294 return 0; 1295 *sval = rl_min(rl); 1296 return 1; 1297 } 1298 1299 int get_implied_max(struct expression *expr, sval_t *sval) 1300 { 1301 struct range_list *rl; 1302 int recurse_cnt = 0; 1303 1304 rl = _get_rl(expr, RL_IMPLIED, &recurse_cnt); 1305 if (!rl) 1306 return 0; 1307 *sval = rl_max(rl); 1308 return 1; 1309 } 1310 1311 int get_implied_rl(struct expression *expr, struct range_list **rl) 1312 { 1313 int recurse_cnt = 0; 1314 1315 *rl = _get_rl(expr, RL_IMPLIED, &recurse_cnt); 1316 if (*rl) 1317 return 1; 1318 return 0; 1319 } 1320 1321 static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt) 1322 { 1323 *rl = _get_rl(expr, RL_ABSOLUTE, recurse_cnt); 1324 if (!*rl) 1325 *rl = alloc_whole_rl(get_type(expr)); 1326 return 1; 1327 } 1328 1329 int get_absolute_rl(struct expression *expr, struct range_list **rl) 1330 { 1331 int recurse_cnt = 0; 1332 1333 *rl = _get_rl(expr, RL_ABSOLUTE, &recurse_cnt); 1334 if (!*rl) 1335 *rl = alloc_whole_rl(get_type(expr)); 1336 return 1; 1337 } 1338 1339 int get_real_absolute_rl(struct expression *expr, struct range_list **rl) 1340 { 1341 int recurse_cnt = 0; 1342 1343 *rl = _get_rl(expr, RL_REAL_ABSOLUTE, &recurse_cnt); 1344 if (!*rl) 1345 *rl = alloc_whole_rl(get_type(expr)); 1346 return 1; 1347 } 1348 1349 int custom_get_absolute_rl(struct expression *expr, 1350 struct range_list *(*fn)(struct expression *expr), 1351 struct range_list **rl) 1352 { 1353 int recurse_cnt = 0; 1354 1355 *rl = NULL; 1356 custom_handle_variable = fn; 1357 *rl = _get_rl(expr, RL_REAL_ABSOLUTE, &recurse_cnt); 1358 custom_handle_variable = NULL; 1359 return 1; 1360 } 1361 1362 int get_implied_rl_var_sym(const char *var, struct symbol *sym, struct range_list **rl) 1363 { 1364 struct smatch_state *state; 1365 1366 state = get_state(SMATCH_EXTRA, var, sym); 1367 *rl = estate_rl(state); 1368 if (*rl) 1369 return 1; 1370 return 0; 1371 } 1372 1373 int get_hard_max(struct expression *expr, sval_t *sval) 1374 { 1375 struct range_list *rl; 1376 int recurse_cnt = 0; 1377 1378 rl = _get_rl(expr, RL_HARD, &recurse_cnt); 1379 if (!rl) 1380 return 0; 1381 *sval = rl_max(rl); 1382 return 1; 1383 } 1384 1385 int get_fuzzy_min(struct expression *expr, sval_t *sval) 1386 { 1387 struct range_list *rl; 1388 sval_t tmp; 1389 int recurse_cnt = 0; 1390 1391 rl = _get_rl(expr, RL_FUZZY, &recurse_cnt); 1392 if (!rl) 1393 return 0; 1394 tmp = rl_min(rl); 1395 if (sval_is_negative(tmp) && sval_is_min(tmp)) 1396 return 0; 1397 *sval = tmp; 1398 return 1; 1399 } 1400 1401 int get_fuzzy_max(struct expression *expr, sval_t *sval) 1402 { 1403 struct range_list *rl; 1404 sval_t max; 1405 int recurse_cnt = 0; 1406 1407 rl = _get_rl(expr, RL_FUZZY, &recurse_cnt); 1408 if (!rl) 1409 return 0; 1410 max = rl_max(rl); 1411 if (max.uvalue > INT_MAX - 10000) 1412 return 0; 1413 *sval = max; 1414 return 1; 1415 } 1416 1417 int get_absolute_min(struct expression *expr, sval_t *sval) 1418 { 1419 struct range_list *rl; 1420 struct symbol *type; 1421 int recurse_cnt = 0; 1422 1423 type = get_type(expr); 1424 if (!type) 1425 type = &llong_ctype; // FIXME: this is wrong but places assume get type can't fail. 1426 rl = _get_rl(expr, RL_REAL_ABSOLUTE, &recurse_cnt); 1427 if (rl) 1428 *sval = rl_min(rl); 1429 else 1430 *sval = sval_type_min(type); 1431 1432 if (sval_cmp(*sval, sval_type_min(type)) < 0) 1433 *sval = sval_type_min(type); 1434 return 1; 1435 } 1436 1437 int get_absolute_max(struct expression *expr, sval_t *sval) 1438 { 1439 struct range_list *rl; 1440 struct symbol *type; 1441 int recurse_cnt = 0; 1442 1443 type = get_type(expr); 1444 if (!type) 1445 type = &llong_ctype; 1446 rl = _get_rl(expr, RL_REAL_ABSOLUTE, &recurse_cnt); 1447 if (rl) 1448 *sval = rl_max(rl); 1449 else 1450 *sval = sval_type_max(type); 1451 1452 if (sval_cmp(sval_type_max(type), *sval) < 0) 1453 *sval = sval_type_max(type); 1454 return 1; 1455 } 1456 1457 int known_condition_true(struct expression *expr) 1458 { 1459 sval_t tmp; 1460 1461 if (!expr) 1462 return 0; 1463 1464 if (get_value(expr, &tmp) && tmp.value) 1465 return 1; 1466 1467 return 0; 1468 } 1469 1470 int known_condition_false(struct expression *expr) 1471 { 1472 if (!expr) 1473 return 0; 1474 1475 if (is_zero(expr)) 1476 return 1; 1477 1478 return 0; 1479 } 1480 1481 int implied_condition_true(struct expression *expr) 1482 { 1483 sval_t tmp; 1484 1485 if (!expr) 1486 return 0; 1487 1488 if (known_condition_true(expr)) 1489 return 1; 1490 if (get_implied_value(expr, &tmp) && tmp.value) 1491 return 1; 1492 1493 if (expr->type == EXPR_POSTOP) 1494 return implied_condition_true(expr->unop); 1495 1496 if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT) 1497 return implied_not_equal(expr->unop, 1); 1498 if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT) 1499 return implied_not_equal(expr->unop, -1); 1500 1501 expr = strip_expr(expr); 1502 switch (expr->type) { 1503 case EXPR_COMPARE: 1504 if (do_comparison(expr) == 1) 1505 return 1; 1506 break; 1507 case EXPR_PREOP: 1508 if (expr->op == '!') { 1509 if (implied_condition_false(expr->unop)) 1510 return 1; 1511 break; 1512 } 1513 break; 1514 default: 1515 if (implied_not_equal(expr, 0) == 1) 1516 return 1; 1517 break; 1518 } 1519 return 0; 1520 } 1521 1522 int implied_condition_false(struct expression *expr) 1523 { 1524 struct expression *tmp; 1525 sval_t sval; 1526 1527 if (!expr) 1528 return 0; 1529 1530 if (known_condition_false(expr)) 1531 return 1; 1532 1533 switch (expr->type) { 1534 case EXPR_COMPARE: 1535 if (do_comparison(expr) == 2) 1536 return 1; 1537 case EXPR_PREOP: 1538 if (expr->op == '!') { 1539 if (implied_condition_true(expr->unop)) 1540 return 1; 1541 break; 1542 } 1543 tmp = strip_expr(expr); 1544 if (tmp != expr) 1545 return implied_condition_false(tmp); 1546 break; 1547 default: 1548 if (get_implied_value(expr, &sval) && sval.value == 0) 1549 return 1; 1550 break; 1551 } 1552 return 0; 1553 } 1554 1555 int can_integer_overflow(struct symbol *type, struct expression *expr) 1556 { 1557 int op; 1558 sval_t lmax, rmax, res; 1559 1560 if (!type) 1561 type = &int_ctype; 1562 1563 expr = strip_expr(expr); 1564 1565 if (expr->type == EXPR_ASSIGNMENT) { 1566 switch(expr->op) { 1567 case SPECIAL_MUL_ASSIGN: 1568 op = '*'; 1569 break; 1570 case SPECIAL_ADD_ASSIGN: 1571 op = '+'; 1572 break; 1573 case SPECIAL_SHL_ASSIGN: 1574 op = SPECIAL_LEFTSHIFT; 1575 break; 1576 default: 1577 return 0; 1578 } 1579 } else if (expr->type == EXPR_BINOP) { 1580 if (expr->op != '*' && expr->op != '+' && expr->op != SPECIAL_LEFTSHIFT) 1581 return 0; 1582 op = expr->op; 1583 } else { 1584 return 0; 1585 } 1586 1587 get_absolute_max(expr->left, &lmax); 1588 get_absolute_max(expr->right, &rmax); 1589 1590 if (sval_binop_overflows(lmax, op, rmax)) 1591 return 1; 1592 1593 res = sval_binop(lmax, op, rmax); 1594 if (sval_cmp(res, sval_type_max(type)) > 0) 1595 return 1; 1596 return 0; 1597 } 1598