smatch_math.c

   1 /*
   2  * smatch/smatch_math.c
   3  *
   4  * Copyright (C) 2010 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 #include "symbol.h"
  11 #include "smatch.h"
  12 #include "smatch_slist.h"
  13 #include "smatch_extra.h"
  14
  15 static sval_t _get_value(struct expression *expr, int *undefined, int implied);
  16 static sval_t _get_implied_value(struct expression *expr, int *undefined, int implied);
  17
  18 #define BOGUS 12345
  19
  20 static sval_t zero  = {.type = &int_ctype, {.value = 0} };
  21 static sval_t one   = {.type = &int_ctype, {.value = 1} };
  22 static sval_t bogus = {.type = &int_ctype, {.value = BOGUS} };
  23
  24 enum {
  25         NOTIMPLIED,
  26         IMPLIED,
  27         IMPLIED_MIN,
  28         IMPLIED_MAX,
  29         FUZZY_MAX,
  30         FUZZY_MIN,
  31         ABSOLUTE_MIN,
  32         ABSOLUTE_MAX,
  33         HARD_MAX,
  34 };
  35
  36 static int opposite_implied(int implied)
  37 {
  38         if (implied == IMPLIED_MIN)
  39                 return IMPLIED_MAX;
  40         if (implied == IMPLIED_MAX)
  41                 return IMPLIED_MIN;
  42         if (implied == FUZZY_MIN)
  43                 return FUZZY_MAX;
  44         if (implied == FUZZY_MAX)
  45                 return FUZZY_MIN;
  46         if (implied == ABSOLUTE_MIN)
  47                 return ABSOLUTE_MAX;
  48         if (implied == ABSOLUTE_MAX)
  49                 return ABSOLUTE_MIN;
  50         if (implied == HARD_MAX)  /* we don't have a hard min.  */
  51                 return NOTIMPLIED;
  52
  53         return implied;
  54 }
  55
  56 static int last_stmt_sval(struct statement *stmt, sval_t *sval)
  57 {
  58         struct expression *expr;
  59
  60         if (!stmt)
  61                 return 0;
  62
  63         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
  64         if (stmt->type != STMT_EXPRESSION)
  65                 return 0;
  66         expr = stmt->expression;
  67         if (!get_value(expr, sval))
  68                 return 0;
  69         return 1;
  70 }
  71
  72 static sval_t handle_expression_statement(struct expression *expr, int *undefined, int implied)
  73 {
  74         struct statement *stmt;
  75         sval_t ret;
  76
  77         stmt = get_expression_statement(expr);
  78         if (!last_stmt_sval(stmt, &ret)) {
  79                 *undefined = 1;
  80                 ret = bogus;
  81         }
  82
  83         return ret;
  84 }
  85
  86 static sval_t handle_ampersand(int *undefined, int implied)
  87 {
  88         sval_t ret;
  89
  90         ret.type = &ptr_ctype;
  91         ret.value = BOGUS;
  92
  93         if (implied == IMPLIED_MIN || implied == FUZZY_MIN || implied == ABSOLUTE_MIN)
  94                 return valid_ptr_min_sval;
  95         if (implied == IMPLIED_MAX || implied == FUZZY_MAX || implied == ABSOLUTE_MAX)
  96                 return valid_ptr_max_sval;
  97
  98         *undefined = 1;
  99         return ret;
 100 }
 101
 102 static sval_t handle_negate(struct expression *expr, int *undefined, int implied)
 103 {
 104         sval_t ret;
 105
 106         ret = sval_blank(expr->unop);
 107
 108         if (known_condition_true(expr->unop)) {
 109                 ret.value = 0;
 110                 return ret;
 111         }
 112
 113         if (implied == NOTIMPLIED) {
 114                 *undefined = 1;
 115                 return bogus;
 116         }
 117
 118         if (implied_condition_true(expr->unop)) {
 119                 ret.value = 0;
 120                 return ret;
 121         }
 122         if (implied_condition_false(expr->unop)) {
 123                 ret.value = 1;
 124                 return ret;
 125         }
 126         if (implied == IMPLIED_MIN || implied == FUZZY_MIN || implied == ABSOLUTE_MIN) {
 127                 ret.value = 0;
 128                 return ret;
 129         }
 130         if (implied == IMPLIED_MAX || implied == FUZZY_MAX || implied == ABSOLUTE_MAX) {
 131                 ret.value = 1;
 132                 return ret;
 133         }
 134         *undefined = 1;
 135         return bogus;
 136 }
 137
 138 static sval_t handle_preop(struct expression *expr, int *undefined, int implied)
 139 {
 140         sval_t ret;
 141
 142         switch (expr->op) {
 143         case '&':
 144                 ret = handle_ampersand(undefined, implied);
 145                 break;
 146         case '!':
 147                 ret = handle_negate(expr, undefined, implied);
 148                 break;
 149         case '~':
 150                 ret = _get_value(expr->unop, undefined, implied);
 151                 ret = sval_preop(ret, '~');
 152                 ret = sval_cast(get_type(expr->unop), ret);
 153                 break;
 154         case '-':
 155                 ret = _get_value(expr->unop, undefined, implied);
 156                 ret = sval_preop(ret, '-');
 157                 break;
 158         case '*':
 159                 ret = _get_implied_value(expr, undefined, implied);
 160                 break;
 161         case '(':
 162                 ret = handle_expression_statement(expr, undefined, implied);
 163                 break;
 164         default:
 165                 *undefined = 1;
 166                 ret = sval_blank(expr);
 167         }
 168         ret = sval_cast(get_type(expr), ret);
 169         return ret;
 170 }
 171
 172 static sval_t handle_divide(struct expression *expr, int *undefined, int implied)
 173 {
 174         sval_t left, right;
 175
 176         left = _get_value(expr->left, undefined, implied);
 177         right = _get_value(expr->right, undefined, opposite_implied(implied));
 178
 179         if (right.value == 0) {
 180                 *undefined = 1;
 181                 return bogus;
 182         }
 183
 184         return sval_binop(left, '/', right);
 185 }
 186
 187 static sval_t handle_subtract(struct expression *expr, int *undefined, int implied)
 188 {
 189         struct symbol *type;
 190         sval_t left, right, ret;
 191         int left_undefined = 0;
 192         int right_undefined = 0;
 193         int known_but_negative = 0;
 194         int comparison;
 195
 196         left = _get_value(expr->left, &left_undefined, implied);
 197         right = _get_value(expr->right, &right_undefined, opposite_implied(implied));
 198
 199         if (!left_undefined && !right_undefined) {
 200                 ret = sval_binop(left, '-', right);
 201                 if (sval_is_negative(ret))
 202                         known_but_negative = 1;
 203                 else
 204                         return ret;  /* best case scenario */
 205         }
 206
 207         comparison = get_comparison(expr->left, expr->right);
 208         if (!comparison)
 209                 goto bogus;
 210
 211         type = get_type(expr);
 212
 213         switch (comparison) {
 214         case '>':
 215         case SPECIAL_UNSIGNED_GT:
 216                 switch (implied) {
 217                 case IMPLIED_MIN:
 218                 case FUZZY_MIN:
 219                 case ABSOLUTE_MIN:
 220                         return sval_type_val(type, 1);
 221                 case IMPLIED_MAX:
 222                 case FUZZY_MAX:
 223                 case ABSOLUTE_MAX:
 224                         return _get_value(expr->left, undefined, implied);
 225                 }
 226                 break;
 227         case SPECIAL_GTE:
 228         case SPECIAL_UNSIGNED_GTE:
 229                 switch (implied) {
 230                 case IMPLIED_MIN:
 231                 case FUZZY_MIN:
 232                 case ABSOLUTE_MIN:
 233                         return sval_type_val(type, 0);
 234                 case IMPLIED_MAX:
 235                 case FUZZY_MAX:
 236                 case ABSOLUTE_MAX:
 237                         return _get_value(expr->left, undefined, implied);
 238                 }
 239                 break;
 240         }
 241
 242         if (known_but_negative)
 243                 return ret;
 244
 245 bogus:
 246         *undefined = 1;
 247         return bogus;
 248 }
 249
 250 static sval_t handle_mod(struct expression *expr, int *undefined, int implied)
 251 {
 252         sval_t left, right;
 253
 254         /* if we can't figure out the right side it's probably hopeless */
 255         right = _get_value(expr->right, undefined, implied);
 256         if (*undefined || right.value == 0) {
 257                 *undefined = 1;
 258                 return bogus;
 259         }
 260
 261         switch (implied) {
 262         case NOTIMPLIED:
 263         case IMPLIED:
 264                 left = _get_value(expr->left, undefined, implied);
 265                 if (!*undefined)
 266                         return sval_binop(left, '%', right);
 267                 return bogus;
 268         case IMPLIED_MIN:
 269         case FUZZY_MIN:
 270         case ABSOLUTE_MIN:
 271                 *undefined = 0;
 272                 return sval_type_val(get_type(expr), 0);
 273         case IMPLIED_MAX:
 274         case FUZZY_MAX:
 275         case ABSOLUTE_MAX:
 276                 *undefined = 0;
 277                 right = sval_cast(get_type(expr), right);
 278                 right.value--;
 279                 return right;
 280         }
 281         return bogus;
 282 }
 283
 284 static sval_t handle_binop(struct expression *expr, int *undefined, int implied)
 285 {
 286         struct symbol *type;
 287         sval_t left, right;
 288         sval_t ret = {.type = &int_ctype, {.value = 123456} };
 289         int local_undef = 0;
 290
 291         switch (expr->op) {
 292         case '%':
 293                 return handle_mod(expr, undefined, implied);
 294         case '&':
 295                 left = _get_value(expr->left, &local_undef, implied);
 296                 if (local_undef) {
 297                         if (implied == IMPLIED_MIN || implied == ABSOLUTE_MIN) {
 298                                 ret = sval_blank(expr->left);
 299                                 ret.value = 0;
 300                                 return ret;
 301                         }
 302                         if (implied != IMPLIED_MAX && implied != ABSOLUTE_MAX)
 303                                 *undefined = 1;
 304                         if (!get_absolute_max(expr->left, &left))
 305                                 *undefined = 1;
 306                 }
 307                 right = _get_value(expr->right, undefined, implied);
 308                 if (*undefined)
 309                         return bogus;
 310                 return sval_binop(left, '&', right);
 311
 312         case SPECIAL_RIGHTSHIFT:
 313                 left = _get_value(expr->left, &local_undef, implied);
 314                 if (local_undef) {
 315                         if (implied == IMPLIED_MIN || implied == ABSOLUTE_MIN) {
 316                                 ret = sval_blank(expr->left);
 317                                 ret.value = 0;
 318                                 return ret;
 319                         }
 320                         if (implied != IMPLIED_MAX && implied != ABSOLUTE_MAX)
 321                                 *undefined = 1;
 322                         if (!get_absolute_max(expr->left, &left))
 323                                 *undefined = 1;
 324                 }
 325                 right = _get_value(expr->right, undefined, implied);
 326                 if (*undefined)
 327                         return bogus;
 328                 return sval_binop(left, SPECIAL_RIGHTSHIFT, right);
 329         case '-':
 330                 return handle_subtract(expr, undefined, implied);
 331         }
 332
 333         left = _get_value(expr->left, undefined, implied);
 334         right = _get_value(expr->right, undefined, implied);
 335
 336         if (*undefined)
 337                 return bogus;
 338
 339         type = get_type(expr);
 340         left = sval_cast(type, left);
 341         right = sval_cast(type, right);
 342
 343         switch (implied) {
 344         case IMPLIED_MAX:
 345         case ABSOLUTE_MAX:
 346                 if (sval_binop_overflows(left, expr->op, right))
 347                         return sval_type_max(get_type(expr));
 348                 break;
 349         case HARD_MAX:
 350         case FUZZY_MAX:
 351                 if (sval_binop_overflows(left, expr->op, right)) {
 352                         *undefined = 1;
 353                         return bogus;
 354                 }
 355         }
 356
 357         switch (expr->op) {
 358         case '/':
 359                 return handle_divide(expr, undefined, implied);
 360         case '%':
 361                 if (right.value == 0) {
 362                         *undefined = 1;
 363                         return bogus;
 364                 } else {
 365                         return sval_binop(left, '%', right);
 366                 }
 367         default:
 368                 ret = sval_binop(left, expr->op, right);
 369         }
 370         return ret;
 371 }
 372
 373 static int do_comparison(struct expression *expr)
 374 {
 375         struct range_list *left_ranges = NULL;
 376         struct range_list *right_ranges = NULL;
 377         int poss_true, poss_false;
 378         struct symbol *type;
 379
 380         type = get_type(expr);
 381
 382         get_implied_rl(expr->left, &left_ranges);
 383         get_implied_rl(expr->right, &right_ranges);
 384         left_ranges = cast_rl(type, left_ranges);
 385         right_ranges = cast_rl(type, right_ranges);
 386
 387         poss_true = possibly_true_rl(left_ranges, expr->op, right_ranges);
 388         poss_false = possibly_false_rl(left_ranges, expr->op, right_ranges);
 389
 390         free_rl(&left_ranges);
 391         free_rl(&right_ranges);
 392
 393         if (!poss_true && !poss_false)
 394                 return 0;
 395         if (poss_true && !poss_false)
 396                 return 1;
 397         if (!poss_true && poss_false)
 398                 return 2;
 399         return 3;
 400 }
 401
 402 static sval_t handle_comparison(struct expression *expr, int *undefined, int implied)
 403 {
 404         sval_t left, right;
 405         int res;
 406
 407         if (get_value(expr->left, &left) && get_value(expr->right, &right)) {
 408                 struct data_range tmp_left, tmp_right;
 409
 410                 tmp_left.min = left;
 411                 tmp_left.max = left;
 412                 tmp_right.min = right;
 413                 tmp_right.max = right;
 414                 if (true_comparison_range(&tmp_left, expr->op, &tmp_right))
 415                         return one;
 416                 return zero;
 417         }
 418
 419         if (implied == NOTIMPLIED) {
 420                 *undefined = 1;
 421                 return bogus;
 422         }
 423
 424         res = do_comparison(expr);
 425         if (res == 1)
 426                 return one;
 427         if (res == 2)
 428                 return zero;
 429
 430         if (implied == IMPLIED_MIN || implied == FUZZY_MIN || implied == ABSOLUTE_MIN)
 431                 return zero;
 432         if (implied == IMPLIED_MAX || implied == FUZZY_MAX || implied == ABSOLUTE_MAX)
 433                 return one;
 434
 435         *undefined = 1;
 436         return bogus;
 437 }
 438
 439 static sval_t handle_logical(struct expression *expr, int *undefined, int implied)
 440 {
 441         sval_t left, right;
 442         int left_known = 0;
 443         int right_known = 0;
 444
 445         if (implied == NOTIMPLIED) {
 446                 if (get_value(expr->left, &left))
 447                         left_known = 1;
 448                 if (get_value(expr->right, &right))
 449                         right_known = 1;
 450         } else {
 451                 if (get_implied_value(expr->left, &left))
 452                         left_known = 1;
 453                 if (get_implied_value(expr->right, &right))
 454                         right_known = 1;
 455         }
 456
 457         switch (expr->op) {
 458         case SPECIAL_LOGICAL_OR:
 459                 if (left_known && left.value)
 460                         return one;
 461                 if (right_known && right.value)
 462                         return one;
 463                 if (left_known && right_known)
 464                         return zero;
 465                 break;
 466         case SPECIAL_LOGICAL_AND:
 467                 if (left_known && right_known) {
 468                         if (left.value && right.value)
 469                                 return one;
 470                         return zero;
 471                 }
 472                 break;
 473         default:
 474                 *undefined = 1;
 475                 return bogus;
 476         }
 477
 478         if (implied == IMPLIED_MIN || implied == FUZZY_MIN || implied == ABSOLUTE_MIN)
 479                 return zero;
 480         if (implied == IMPLIED_MAX || implied == FUZZY_MAX || implied == ABSOLUTE_MAX)
 481                 return one;
 482
 483         *undefined = 1;
 484         return bogus;
 485 }
 486
 487 static sval_t handle_conditional(struct expression *expr, int *undefined, int implied)
 488 {
 489         if (known_condition_true(expr->conditional))
 490                 return _get_value(expr->cond_true, undefined, implied);
 491         if (known_condition_false(expr->conditional))
 492                 return _get_value(expr->cond_false, undefined, implied);
 493
 494         if (implied == NOTIMPLIED) {
 495                 *undefined = 1;
 496                 return bogus;
 497         }
 498
 499         if (implied_condition_true(expr->conditional))
 500                 return _get_value(expr->cond_true, undefined, implied);
 501         if (implied_condition_false(expr->conditional))
 502                 return _get_value(expr->cond_false, undefined, implied);
 503
 504         *undefined = 1;
 505         return bogus;
 506 }
 507
 508 static int get_local_value(struct expression *expr, sval_t *sval, int implied)
 509 {
 510         switch (implied) {
 511         case NOTIMPLIED:
 512         case IMPLIED:
 513                 return 0;
 514         case IMPLIED_MIN:
 515         case FUZZY_MIN:
 516         case ABSOLUTE_MIN:
 517                 return get_local_min_helper(expr, sval);
 518         case ABSOLUTE_MAX:
 519         case HARD_MAX:
 520         case IMPLIED_MAX:
 521         case FUZZY_MAX:
 522                 return get_local_max_helper(expr, sval);
 523         }
 524         return 0;
 525 }
 526
 527 static int get_implied_value_helper(struct expression *expr, sval_t *sval, int implied)
 528 {
 529         struct smatch_state *state;
 530         struct symbol *sym;
 531         char *name;
 532
 533         /* fixme: this should return the casted value */
 534
 535         expr = strip_expr(expr);
 536
 537         if (get_value(expr, sval))
 538                 return 1;
 539
 540         name = expr_to_var_sym(expr, &sym);
 541         if (!name)
 542                 return 0;
 543         *sval = sval_blank(expr);
 544         state = get_state(SMATCH_EXTRA, name, sym);
 545         free_string(name);
 546         if (!state || !state->data)
 547                 return get_local_value(expr, sval, implied);
 548         if (implied == IMPLIED) {
 549                 if (estate_get_single_value(state, sval))
 550                         return 1;
 551                 return 0;
 552         }
 553         if (implied == HARD_MAX) {
 554                 if (estate_get_hard_max(state, sval))
 555                         return 1;
 556                 return 0;
 557         }
 558         if (implied == IMPLIED_MAX || implied == ABSOLUTE_MAX) {
 559                 *sval = estate_max(state);
 560                 return 1;
 561         }
 562         *sval = estate_min(state);
 563         return 1;
 564 }
 565
 566 static int get_fuzzy_max_helper(struct expression *expr, sval_t *max)
 567 {
 568         struct sm_state *sm;
 569         struct sm_state *tmp;
 570         sval_t sval;
 571
 572         if (get_hard_max(expr, &sval)) {
 573                 *max = sval;
 574                 return 1;
 575         }
 576
 577         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 578         if (!sm)
 579                 return 0;
 580
 581         sval = sval_type_min(estate_type(sm->state));
 582         FOR_EACH_PTR(sm->possible, tmp) {
 583                 sval_t new_min;
 584
 585                 new_min = estate_min(tmp->state);
 586                 if (sval_cmp(new_min, sval) > 0)
 587                         sval = new_min;
 588         } END_FOR_EACH_PTR(tmp);
 589
 590         if (sval_is_min(sval))
 591                 return 0;
 592         if (sval.value == sval_type_min(sval.type).value + 1)  /* it's common to be on off */
 593                 return 0;
 594
 595         *max = sval_cast(get_type(expr), sval);
 596         return 1;
 597 }
 598
 599 static int get_fuzzy_min_helper(struct expression *expr, sval_t *min)
 600 {
 601         struct sm_state *sm;
 602         struct sm_state *tmp;
 603         sval_t sval;
 604
 605         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 606         if (!sm)
 607                 return 0;
 608
 609         if (!sval_is_min(estate_min(sm->state))) {
 610                 *min = estate_min(sm->state);
 611                 return 1;
 612         }
 613
 614         sval = sval_type_max(estate_type(sm->state));
 615         FOR_EACH_PTR(sm->possible, tmp) {
 616                 sval_t new_max;
 617
 618                 new_max = estate_max(tmp->state);
 619                 if (sval_cmp(new_max, sval) < 0)
 620                         sval = new_max;
 621         } END_FOR_EACH_PTR(tmp);
 622
 623         if (sval_is_max(sval))
 624                 return 0;
 625         *min = sval_cast(get_type(expr), sval);
 626         return 1;
 627 }
 628
 629 static sval_t _get_implied_value(struct expression *expr, int *undefined, int implied)
 630 {
 631         sval_t ret;
 632
 633         ret = sval_blank(expr);
 634
 635         switch (implied) {
 636         case IMPLIED:
 637         case IMPLIED_MAX:
 638         case IMPLIED_MIN:
 639         case HARD_MAX:
 640         case ABSOLUTE_MIN:
 641         case ABSOLUTE_MAX:
 642                 if (!get_implied_value_helper(expr, &ret, implied))
 643                         *undefined = 1;
 644                 break;
 645         case FUZZY_MAX:
 646                 if (!get_fuzzy_max_helper(expr, &ret))
 647                         *undefined = 1;
 648                 break;
 649         case FUZZY_MIN:
 650                 if (!get_fuzzy_min_helper(expr, &ret))
 651                         *undefined = 1;
 652                 break;
 653         default:
 654                 *undefined = 1;
 655         }
 656         return ret;
 657 }
 658
 659 static int get_const_value(struct expression *expr, sval_t *sval)
 660 {
 661         struct symbol *sym;
 662         sval_t right;
 663
 664         if (expr->type != EXPR_SYMBOL || !expr->symbol)
 665                 return 0;
 666         sym = expr->symbol;
 667         if (!(sym->ctype.modifiers & MOD_CONST))
 668                 return 0;
 669         if (get_value(sym->initializer, &right)) {
 670                 *sval = sval_cast(get_type(expr), right);
 671                 return 1;
 672         }
 673         return 0;
 674 }
 675
 676 static sval_t handle_sizeof(struct expression *expr)
 677 {
 678         struct symbol *sym;
 679         sval_t ret;
 680
 681         ret = sval_blank(expr);
 682         sym = expr->cast_type;
 683         if (!sym) {
 684                 sym = evaluate_expression(expr->cast_expression);
 685                 /*
 686                  * Expressions of restricted types will possibly get
 687                  * promoted - check that here
 688                  */
 689                 if (is_restricted_type(sym)) {
 690                         if (sym->bit_size < bits_in_int)
 691                                 sym = &int_ctype;
 692                 } else if (is_fouled_type(sym)) {
 693                         sym = &int_ctype;
 694                 }
 695         }
 696         examine_symbol_type(sym);
 697
 698         ret.type = size_t_ctype;
 699         if (sym->bit_size <= 0) /* sizeof(void) */
 700                 ret.value = 1;
 701         else
 702                 ret.value = bits_to_bytes(sym->bit_size);
 703
 704         return ret;
 705 }
 706
 707 static sval_t handle_call(struct expression *expr, int *undefined, int implied)
 708 {
 709         struct range_list *rl;
 710
 711         if (!get_implied_rl(expr, &rl)) {
 712                 *undefined = 1;
 713                 return bogus;
 714         }
 715
 716         switch (implied) {
 717         case IMPLIED:
 718                 if (sval_cmp(rl_min(rl), rl_max(rl)) == 0)
 719                         return rl_min(rl);
 720                 *undefined = 1;
 721                 return bogus;
 722         case IMPLIED_MIN:
 723         case ABSOLUTE_MIN:
 724                 return rl_min(rl);
 725
 726         case IMPLIED_MAX:
 727         case HARD_MAX:
 728         case ABSOLUTE_MAX:
 729                 return rl_max(rl);
 730         default:
 731                 *undefined = 1;
 732                 return bogus;
 733         }
 734
 735 }
 736
 737 static sval_t _get_value(struct expression *expr, int *undefined, int implied)
 738 {
 739         sval_t ret;
 740
 741         if (!expr) {
 742                 *undefined = 1;
 743                 return bogus;
 744         }
 745         if (*undefined)
 746                 return bogus;
 747
 748         expr = strip_parens(expr);
 749
 750         switch (expr->type) {
 751         case EXPR_VALUE:
 752                 ret = sval_from_val(expr, expr->value);
 753                 break;
 754         case EXPR_PREOP:
 755                 ret = handle_preop(expr, undefined, implied);
 756                 break;
 757         case EXPR_POSTOP:
 758                 ret = _get_value(expr->unop, undefined, implied);
 759                 break;
 760         case EXPR_CAST:
 761         case EXPR_FORCE_CAST:
 762         case EXPR_IMPLIED_CAST:
 763                 ret = _get_value(expr->cast_expression, undefined, implied);
 764                 ret = sval_cast(get_type(expr), ret);
 765                 break;
 766         case EXPR_BINOP:
 767                 ret = handle_binop(expr, undefined, implied);
 768                 break;
 769         case EXPR_COMPARE:
 770                 ret = handle_comparison(expr, undefined, implied);
 771                 break;
 772         case EXPR_LOGICAL:
 773                 ret = handle_logical(expr, undefined, implied);
 774                 break;
 775         case EXPR_PTRSIZEOF:
 776         case EXPR_SIZEOF:
 777                 ret = handle_sizeof(expr);
 778                 break;
 779         case EXPR_SYMBOL:
 780                 if (get_const_value(expr, &ret)) {
 781                         break;
 782                 }
 783                 ret = _get_implied_value(expr, undefined, implied);
 784                 break;
 785         case EXPR_SELECT:
 786         case EXPR_CONDITIONAL:
 787                 ret = handle_conditional(expr, undefined, implied);
 788                 break;
 789         case EXPR_CALL:
 790                 ret = handle_call(expr, undefined, implied);
 791                 break;
 792         default:
 793                 ret = _get_implied_value(expr, undefined, implied);
 794         }
 795         if (*undefined)
 796                 return bogus;
 797         return ret;
 798 }
 799
 800 /* returns 1 if it can get a value literal or else returns 0 */
 801 int get_value(struct expression *expr, sval_t *sval)
 802 {
 803         int undefined = 0;
 804         sval_t ret;
 805
 806         ret = _get_value(expr, &undefined, NOTIMPLIED);
 807         if (undefined)
 808                 return 0;
 809         *sval = ret;
 810         return 1;
 811 }
 812
 813 int get_implied_value(struct expression *expr, sval_t *sval)
 814 {
 815         int undefined = 0;
 816         sval_t ret;
 817
 818         ret =  _get_value(expr, &undefined, IMPLIED);
 819         if (undefined)
 820                 return 0;
 821         *sval = ret;
 822         return 1;
 823 }
 824
 825 int get_implied_min(struct expression *expr, sval_t *sval)
 826 {
 827         int undefined = 0;
 828         sval_t ret;
 829
 830         ret =  _get_value(expr, &undefined, IMPLIED_MIN);
 831         if (undefined)
 832                 return 0;
 833         *sval = ret;
 834         return 1;
 835 }
 836
 837 int get_implied_max(struct expression *expr, sval_t *sval)
 838 {
 839         int undefined = 0;
 840         sval_t ret;
 841
 842         ret =  _get_value(expr, &undefined, IMPLIED_MAX);
 843         if (undefined)
 844                 return 0;
 845         *sval = ret;
 846         return 1;
 847 }
 848
 849 int get_implied_rl(struct expression *expr, struct range_list **rl)
 850 {
 851         sval_t sval;
 852         struct smatch_state *state;
 853         sval_t min, max;
 854         int min_known = 0;
 855         int max_known = 0;
 856
 857         *rl = NULL;
 858
 859         expr = strip_parens(expr);
 860         if (!expr)
 861                 return 0;
 862
 863         state = get_state_expr(SMATCH_EXTRA, expr);
 864         if (state) {
 865                 *rl = clone_rl(estate_rl(state));
 866                 return 1;
 867         }
 868
 869         if (expr->type == EXPR_CALL) {
 870                 if (get_implied_return(expr, rl))
 871                         return 1;
 872                 *rl = db_return_vals(expr);
 873                 if (*rl)
 874                         return 1;
 875                 return 0;
 876         }
 877
 878         if (get_implied_value(expr, &sval)) {
 879                 add_range(rl, sval, sval);
 880                 return 1;
 881         }
 882
 883         if (get_local_rl(expr, rl))
 884                 return 1;
 885
 886         min_known = get_implied_min(expr, &min);
 887         max_known = get_implied_max(expr, &max);
 888         if (!min_known && !max_known)
 889                 return 0;
 890         if (!min_known)
 891                 get_absolute_min(expr, &min);
 892         if (!max_known)
 893                 get_absolute_max(expr, &max);
 894
 895         *rl = alloc_rl(min, max);
 896         return 1;
 897 }
 898
 899 int get_hard_max(struct expression *expr, sval_t *sval)
 900 {
 901         int undefined = 0;
 902         sval_t ret;
 903
 904         ret =  _get_value(expr, &undefined, HARD_MAX);
 905         if (undefined)
 906                 return 0;
 907         *sval = ret;
 908         return 1;
 909 }
 910
 911 int get_fuzzy_min(struct expression *expr, sval_t *sval)
 912 {
 913         int undefined = 0;
 914         sval_t ret;
 915
 916         ret =  _get_value(expr, &undefined, FUZZY_MIN);
 917         if (undefined)
 918                 return 0;
 919         *sval = ret;
 920         return 1;
 921 }
 922
 923 int get_fuzzy_max(struct expression *expr, sval_t *sval)
 924 {
 925         int undefined = 0;
 926         sval_t ret;
 927
 928         ret =  _get_value(expr, &undefined, FUZZY_MAX);
 929         if (undefined)
 930                 return 0;
 931         if (ret.uvalue > INT_MAX - 10000)
 932                 return 0;
 933         *sval = ret;
 934         return 1;
 935 }
 936
 937 int get_absolute_min(struct expression *expr, sval_t *sval)
 938 {
 939         int undefined = 0;
 940         struct symbol *type;
 941
 942         type = get_type(expr);
 943         if (!type)
 944                 type = &llong_ctype;  // FIXME: this is wrong but places assume get type can't fail.
 945         *sval =  _get_value(expr, &undefined, ABSOLUTE_MIN);
 946         if (undefined) {
 947                 *sval = sval_type_min(type);
 948                 return 1;
 949         }
 950
 951         if (sval_cmp(*sval, sval_type_min(type)) < 0)
 952                 *sval = sval_type_min(type);
 953         return 1;
 954 }
 955
 956 int get_absolute_max(struct expression *expr, sval_t *sval)
 957 {
 958         int undefined = 0;
 959         struct symbol *type;
 960
 961         type = get_type(expr);
 962         if (!type)
 963                 type = &llong_ctype;
 964         *sval = _get_value(expr, &undefined, ABSOLUTE_MAX);
 965         if (undefined) {
 966                 *sval = sval_type_max(type);
 967                 return 1;
 968         }
 969
 970         if (sval_cmp(sval_type_max(type), *sval) < 0)
 971                 *sval = sval_type_max(type);
 972         return 1;
 973 }
 974
 975 int known_condition_true(struct expression *expr)
 976 {
 977         sval_t tmp;
 978
 979         if (!expr)
 980                 return 0;
 981
 982         if (get_value(expr, &tmp) && tmp.value)
 983                 return 1;
 984
 985         return 0;
 986 }
 987
 988 int known_condition_false(struct expression *expr)
 989 {
 990         if (!expr)
 991                 return 0;
 992
 993         if (is_zero(expr))
 994                 return 1;
 995
 996         if (expr->type == EXPR_CALL) {
 997                 if (sym_name_is("__builtin_constant_p", expr->fn))
 998                         return 1;
 999         }
1000         return 0;
1001 }
1002
1003 int implied_condition_true(struct expression *expr)
1004 {
1005         sval_t tmp;
1006
1007         if (!expr)
1008                 return 0;
1009
1010         if (known_condition_true(expr))
1011                 return 1;
1012         if (get_implied_value(expr, &tmp) && tmp.value)
1013                 return 1;
1014
1015         if (expr->type == EXPR_POSTOP)
1016                 return implied_condition_true(expr->unop);
1017
1018         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
1019                 return implied_not_equal(expr->unop, 1);
1020         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
1021                 return implied_not_equal(expr->unop, -1);
1022
1023         expr = strip_expr(expr);
1024         switch (expr->type) {
1025         case EXPR_COMPARE:
1026                 if (do_comparison(expr) == 1)
1027                         return 1;
1028                 break;
1029         case EXPR_PREOP:
1030                 if (expr->op == '!') {
1031                         if (implied_condition_false(expr->unop))
1032                                 return 1;
1033                         break;
1034                 }
1035                 break;
1036         default:
1037                 if (implied_not_equal(expr, 0) == 1)
1038                         return 1;
1039                 break;
1040         }
1041         return 0;
1042 }
1043
1044 int implied_condition_false(struct expression *expr)
1045 {
1046         struct expression *tmp;
1047         sval_t sval;
1048
1049         if (!expr)
1050                 return 0;
1051
1052         if (known_condition_false(expr))
1053                 return 1;
1054
1055         switch (expr->type) {
1056         case EXPR_COMPARE:
1057                 if (do_comparison(expr) == 2)
1058                         return 1;
1059         case EXPR_PREOP:
1060                 if (expr->op == '!') {
1061                         if (implied_condition_true(expr->unop))
1062                                 return 1;
1063                         break;
1064                 }
1065                 tmp = strip_expr(expr);
1066                 if (tmp != expr)
1067                         return implied_condition_false(tmp);
1068                 break;
1069         default:
1070                 if (get_implied_value(expr, &sval) && sval.value == 0)
1071                         return 1;
1072                 break;
1073         }
1074         return 0;
1075 }