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         EXACT,
  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 EXACT;
  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 == EXACT) {
 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 EXACT:
 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                 if (implied == HARD_MAX) {
 296                         *undefined = 1;
 297                         return bogus;
 298                 }
 299                 left = _get_value(expr->left, &local_undef, implied);
 300                 if (local_undef) {
 301                         if (implied == IMPLIED_MIN || implied == ABSOLUTE_MIN) {
 302                                 ret = sval_blank(expr->left);
 303                                 ret.value = 0;
 304                                 return ret;
 305                         }
 306                         if (implied != IMPLIED_MAX && implied != ABSOLUTE_MAX)
 307                                 *undefined = 1;
 308                         if (!get_absolute_max(expr->left, &left))
 309                                 *undefined = 1;
 310                 }
 311                 right = _get_value(expr->right, undefined, implied);
 312                 if (*undefined)
 313                         return bogus;
 314                 return sval_binop(left, '&', right);
 315
 316         case SPECIAL_RIGHTSHIFT:
 317                 if (implied == HARD_MAX) {
 318                         *undefined = 1;
 319                         return bogus;
 320                 }
 321                 left = _get_value(expr->left, &local_undef, implied);
 322                 if (local_undef) {
 323                         if (implied == IMPLIED_MIN || implied == ABSOLUTE_MIN) {
 324                                 ret = sval_blank(expr->left);
 325                                 ret.value = 0;
 326                                 return ret;
 327                         }
 328                         if (implied != IMPLIED_MAX && implied != ABSOLUTE_MAX)
 329                                 *undefined = 1;
 330                         if (!get_absolute_max(expr->left, &left))
 331                                 *undefined = 1;
 332                 }
 333                 right = _get_value(expr->right, undefined, implied);
 334                 if (*undefined)
 335                         return bogus;
 336                 return sval_binop(left, SPECIAL_RIGHTSHIFT, right);
 337         case '-':
 338                 return handle_subtract(expr, undefined, implied);
 339         }
 340
 341         left = _get_value(expr->left, undefined, implied);
 342         right = _get_value(expr->right, undefined, implied);
 343
 344         if (*undefined)
 345                 return bogus;
 346
 347         type = get_type(expr);
 348         left = sval_cast(type, left);
 349         right = sval_cast(type, right);
 350
 351         switch (implied) {
 352         case IMPLIED_MAX:
 353         case ABSOLUTE_MAX:
 354                 if (sval_binop_overflows(left, expr->op, right))
 355                         return sval_type_max(get_type(expr));
 356                 break;
 357         case HARD_MAX:
 358         case FUZZY_MAX:
 359                 if (sval_binop_overflows(left, expr->op, right)) {
 360                         *undefined = 1;
 361                         return bogus;
 362                 }
 363         }
 364
 365         switch (expr->op) {
 366         case '/':
 367                 return handle_divide(expr, undefined, implied);
 368         case '%':
 369                 if (right.value == 0) {
 370                         *undefined = 1;
 371                         return bogus;
 372                 } else {
 373                         return sval_binop(left, '%', right);
 374                 }
 375         default:
 376                 ret = sval_binop(left, expr->op, right);
 377         }
 378         return ret;
 379 }
 380
 381 static int do_comparison(struct expression *expr)
 382 {
 383         struct range_list *left_ranges = NULL;
 384         struct range_list *right_ranges = NULL;
 385         int poss_true, poss_false;
 386         struct symbol *type;
 387
 388         type = get_type(expr);
 389
 390         get_implied_rl(expr->left, &left_ranges);
 391         get_implied_rl(expr->right, &right_ranges);
 392         left_ranges = cast_rl(type, left_ranges);
 393         right_ranges = cast_rl(type, right_ranges);
 394
 395         poss_true = possibly_true_rl(left_ranges, expr->op, right_ranges);
 396         poss_false = possibly_false_rl(left_ranges, expr->op, right_ranges);
 397
 398         free_rl(&left_ranges);
 399         free_rl(&right_ranges);
 400
 401         if (!poss_true && !poss_false)
 402                 return 0;
 403         if (poss_true && !poss_false)
 404                 return 1;
 405         if (!poss_true && poss_false)
 406                 return 2;
 407         return 3;
 408 }
 409
 410 static sval_t handle_comparison(struct expression *expr, int *undefined, int implied)
 411 {
 412         sval_t left, right;
 413         int res;
 414
 415         if (get_value(expr->left, &left) && get_value(expr->right, &right)) {
 416                 struct data_range tmp_left, tmp_right;
 417
 418                 tmp_left.min = left;
 419                 tmp_left.max = left;
 420                 tmp_right.min = right;
 421                 tmp_right.max = right;
 422                 if (true_comparison_range(&tmp_left, expr->op, &tmp_right))
 423                         return one;
 424                 return zero;
 425         }
 426
 427         if (implied == EXACT) {
 428                 *undefined = 1;
 429                 return bogus;
 430         }
 431
 432         res = do_comparison(expr);
 433         if (res == 1)
 434                 return one;
 435         if (res == 2)
 436                 return zero;
 437
 438         if (implied == IMPLIED_MIN || implied == FUZZY_MIN || implied == ABSOLUTE_MIN)
 439                 return zero;
 440         if (implied == IMPLIED_MAX || implied == FUZZY_MAX || implied == ABSOLUTE_MAX)
 441                 return one;
 442
 443         *undefined = 1;
 444         return bogus;
 445 }
 446
 447 static sval_t handle_logical(struct expression *expr, int *undefined, int implied)
 448 {
 449         sval_t left, right;
 450         int left_known = 0;
 451         int right_known = 0;
 452
 453         if (implied == EXACT) {
 454                 if (get_value(expr->left, &left))
 455                         left_known = 1;
 456                 if (get_value(expr->right, &right))
 457                         right_known = 1;
 458         } else {
 459                 if (get_implied_value(expr->left, &left))
 460                         left_known = 1;
 461                 if (get_implied_value(expr->right, &right))
 462                         right_known = 1;
 463         }
 464
 465         switch (expr->op) {
 466         case SPECIAL_LOGICAL_OR:
 467                 if (left_known && left.value)
 468                         return one;
 469                 if (right_known && right.value)
 470                         return one;
 471                 if (left_known && right_known)
 472                         return zero;
 473                 break;
 474         case SPECIAL_LOGICAL_AND:
 475                 if (left_known && right_known) {
 476                         if (left.value && right.value)
 477                                 return one;
 478                         return zero;
 479                 }
 480                 break;
 481         default:
 482                 *undefined = 1;
 483                 return bogus;
 484         }
 485
 486         if (implied == IMPLIED_MIN || implied == FUZZY_MIN || implied == ABSOLUTE_MIN)
 487                 return zero;
 488         if (implied == IMPLIED_MAX || implied == FUZZY_MAX || implied == ABSOLUTE_MAX)
 489                 return one;
 490
 491         *undefined = 1;
 492         return bogus;
 493 }
 494
 495 static sval_t handle_conditional(struct expression *expr, int *undefined, int implied)
 496 {
 497         if (known_condition_true(expr->conditional))
 498                 return _get_value(expr->cond_true, undefined, implied);
 499         if (known_condition_false(expr->conditional))
 500                 return _get_value(expr->cond_false, undefined, implied);
 501
 502         if (implied == EXACT) {
 503                 *undefined = 1;
 504                 return bogus;
 505         }
 506
 507         if (implied_condition_true(expr->conditional))
 508                 return _get_value(expr->cond_true, undefined, implied);
 509         if (implied_condition_false(expr->conditional))
 510                 return _get_value(expr->cond_false, undefined, implied);
 511
 512         *undefined = 1;
 513         return bogus;
 514 }
 515
 516 static int get_local_value(struct expression *expr, sval_t *sval, int implied)
 517 {
 518         switch (implied) {
 519         case EXACT:
 520         case IMPLIED:
 521                 return 0;
 522         case IMPLIED_MIN:
 523         case FUZZY_MIN:
 524         case ABSOLUTE_MIN:
 525                 return get_local_min_helper(expr, sval);
 526         case ABSOLUTE_MAX:
 527         case HARD_MAX:
 528         case IMPLIED_MAX:
 529         case FUZZY_MAX:
 530                 return get_local_max_helper(expr, sval);
 531         }
 532         return 0;
 533 }
 534
 535 static int get_implied_value_helper(struct expression *expr, sval_t *sval, int implied)
 536 {
 537         struct smatch_state *state;
 538         struct symbol *sym;
 539         char *name;
 540
 541         /* fixme: this should return the casted value */
 542
 543         expr = strip_expr(expr);
 544
 545         if (get_value(expr, sval))
 546                 return 1;
 547
 548         name = expr_to_var_sym(expr, &sym);
 549         if (!name)
 550                 return 0;
 551         *sval = sval_blank(expr);
 552         state = get_state(SMATCH_EXTRA, name, sym);
 553         free_string(name);
 554         if (!state || !state->data)
 555                 return get_local_value(expr, sval, implied);
 556         if (implied == IMPLIED) {
 557                 if (estate_get_single_value(state, sval))
 558                         return 1;
 559                 return 0;
 560         }
 561         if (implied == HARD_MAX) {
 562                 if (estate_get_hard_max(state, sval))
 563                         return 1;
 564                 return 0;
 565         }
 566         if (implied == IMPLIED_MAX || implied == ABSOLUTE_MAX) {
 567                 *sval = estate_max(state);
 568                 return 1;
 569         }
 570         *sval = estate_min(state);
 571         return 1;
 572 }
 573
 574 static int get_fuzzy_max_helper(struct expression *expr, sval_t *max)
 575 {
 576         struct sm_state *sm;
 577         struct sm_state *tmp;
 578         sval_t sval;
 579
 580         if (get_hard_max(expr, &sval)) {
 581                 *max = sval;
 582                 return 1;
 583         }
 584
 585         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 586         if (!sm)
 587                 return 0;
 588
 589         sval = sval_type_min(estate_type(sm->state));
 590         FOR_EACH_PTR(sm->possible, tmp) {
 591                 sval_t new_min;
 592
 593                 new_min = estate_min(tmp->state);
 594                 if (sval_cmp(new_min, sval) > 0)
 595                         sval = new_min;
 596         } END_FOR_EACH_PTR(tmp);
 597
 598         if (sval_is_min(sval))
 599                 return 0;
 600         if (sval.value == sval_type_min(sval.type).value + 1)  /* it's common to be on off */
 601                 return 0;
 602
 603         *max = sval_cast(get_type(expr), sval);
 604         return 1;
 605 }
 606
 607 static int get_fuzzy_min_helper(struct expression *expr, sval_t *min)
 608 {
 609         struct sm_state *sm;
 610         struct sm_state *tmp;
 611         sval_t sval;
 612
 613         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 614         if (!sm)
 615                 return 0;
 616
 617         if (!sval_is_min(estate_min(sm->state))) {
 618                 *min = estate_min(sm->state);
 619                 return 1;
 620         }
 621
 622         sval = sval_type_max(estate_type(sm->state));
 623         FOR_EACH_PTR(sm->possible, tmp) {
 624                 sval_t new_max;
 625
 626                 new_max = estate_max(tmp->state);
 627                 if (sval_cmp(new_max, sval) < 0)
 628                         sval = new_max;
 629         } END_FOR_EACH_PTR(tmp);
 630
 631         if (sval_is_max(sval))
 632                 return 0;
 633         *min = sval_cast(get_type(expr), sval);
 634         return 1;
 635 }
 636
 637 static sval_t _get_implied_value(struct expression *expr, int *undefined, int implied)
 638 {
 639         sval_t ret;
 640
 641         ret = sval_blank(expr);
 642
 643         switch (implied) {
 644         case IMPLIED:
 645         case IMPLIED_MAX:
 646         case IMPLIED_MIN:
 647         case HARD_MAX:
 648         case ABSOLUTE_MIN:
 649         case ABSOLUTE_MAX:
 650                 if (!get_implied_value_helper(expr, &ret, implied))
 651                         *undefined = 1;
 652                 break;
 653         case FUZZY_MAX:
 654                 if (!get_fuzzy_max_helper(expr, &ret))
 655                         *undefined = 1;
 656                 break;
 657         case FUZZY_MIN:
 658                 if (!get_fuzzy_min_helper(expr, &ret))
 659                         *undefined = 1;
 660                 break;
 661         default:
 662                 *undefined = 1;
 663         }
 664         return ret;
 665 }
 666
 667 static int get_const_value(struct expression *expr, sval_t *sval)
 668 {
 669         struct symbol *sym;
 670         sval_t right;
 671
 672         if (expr->type != EXPR_SYMBOL || !expr->symbol)
 673                 return 0;
 674         sym = expr->symbol;
 675         if (!(sym->ctype.modifiers & MOD_CONST))
 676                 return 0;
 677         if (get_value(sym->initializer, &right)) {
 678                 *sval = sval_cast(get_type(expr), right);
 679                 return 1;
 680         }
 681         return 0;
 682 }
 683
 684 static sval_t handle_sizeof(struct expression *expr)
 685 {
 686         struct symbol *sym;
 687         sval_t ret;
 688
 689         ret = sval_blank(expr);
 690         sym = expr->cast_type;
 691         if (!sym) {
 692                 sym = evaluate_expression(expr->cast_expression);
 693                 /*
 694                  * Expressions of restricted types will possibly get
 695                  * promoted - check that here
 696                  */
 697                 if (is_restricted_type(sym)) {
 698                         if (sym->bit_size < bits_in_int)
 699                                 sym = &int_ctype;
 700                 } else if (is_fouled_type(sym)) {
 701                         sym = &int_ctype;
 702                 }
 703         }
 704         examine_symbol_type(sym);
 705
 706         ret.type = size_t_ctype;
 707         if (sym->bit_size <= 0) /* sizeof(void) */ {
 708                 if (get_real_base_type(sym) == &void_ctype)
 709                         ret.value = 1;
 710                 else
 711                         ret.value = 0;
 712         } else
 713                 ret.value = bits_to_bytes(sym->bit_size);
 714
 715         return ret;
 716 }
 717
 718 static sval_t handle_call(struct expression *expr, int *undefined, int implied)
 719 {
 720         struct range_list *rl;
 721
 722         if (!get_implied_rl(expr, &rl)) {
 723                 *undefined = 1;
 724                 return bogus;
 725         }
 726
 727         switch (implied) {
 728         case IMPLIED:
 729                 if (sval_cmp(rl_min(rl), rl_max(rl)) == 0)
 730                         return rl_min(rl);
 731                 *undefined = 1;
 732                 return bogus;
 733         case IMPLIED_MIN:
 734         case ABSOLUTE_MIN:
 735                 return rl_min(rl);
 736
 737         case IMPLIED_MAX:
 738         case HARD_MAX:
 739         case ABSOLUTE_MAX:
 740                 return rl_max(rl);
 741         default:
 742                 *undefined = 1;
 743                 return bogus;
 744         }
 745
 746 }
 747
 748 static sval_t _get_value(struct expression *expr, int *undefined, int implied)
 749 {
 750         struct symbol *type;
 751         sval_t ret;
 752
 753         if (!expr) {
 754                 *undefined = 1;
 755                 return bogus;
 756         }
 757         if (*undefined)
 758                 return bogus;
 759
 760         expr = strip_parens(expr);
 761         type = get_type(expr);
 762
 763         switch (expr->type) {
 764         case EXPR_VALUE:
 765                 ret = sval_from_val(expr, expr->value);
 766                 break;
 767         case EXPR_PREOP:
 768                 ret = handle_preop(expr, undefined, implied);
 769                 break;
 770         case EXPR_POSTOP:
 771                 ret = _get_value(expr->unop, undefined, implied);
 772                 break;
 773         case EXPR_CAST:
 774         case EXPR_FORCE_CAST:
 775         case EXPR_IMPLIED_CAST:
 776                 ret = _get_value(expr->cast_expression, undefined, implied);
 777                 ret = sval_cast(type, ret);
 778                 break;
 779         case EXPR_BINOP:
 780                 ret = handle_binop(expr, undefined, implied);
 781                 break;
 782         case EXPR_COMPARE:
 783                 ret = handle_comparison(expr, undefined, implied);
 784                 break;
 785         case EXPR_LOGICAL:
 786                 ret = handle_logical(expr, undefined, implied);
 787                 break;
 788         case EXPR_PTRSIZEOF:
 789         case EXPR_SIZEOF:
 790                 ret = handle_sizeof(expr);
 791                 break;
 792         case EXPR_SYMBOL:
 793                 if (get_const_value(expr, &ret)) {
 794                         break;
 795                 }
 796                 ret = _get_implied_value(expr, undefined, implied);
 797                 break;
 798         case EXPR_SELECT:
 799         case EXPR_CONDITIONAL:
 800                 ret = handle_conditional(expr, undefined, implied);
 801                 break;
 802         case EXPR_CALL:
 803                 ret = handle_call(expr, undefined, implied);
 804                 break;
 805         default:
 806                 ret = _get_implied_value(expr, undefined, implied);
 807         }
 808         if (*undefined && type && implied == ABSOLUTE_MAX) {
 809                 *undefined = 0;
 810                 ret = sval_type_max(type);
 811         }
 812         if (*undefined && type && implied == ABSOLUTE_MIN) {
 813                 *undefined = 0;
 814                 ret = sval_type_min(type);
 815         }
 816
 817         if (*undefined)
 818                 return bogus;
 819         return ret;
 820 }
 821
 822 /* returns 1 if it can get a value literal or else returns 0 */
 823 int get_value(struct expression *expr, sval_t *sval)
 824 {
 825         int undefined = 0;
 826         sval_t ret;
 827
 828         ret = _get_value(expr, &undefined, EXACT);
 829         if (undefined)
 830                 return 0;
 831         *sval = ret;
 832         return 1;
 833 }
 834
 835 int get_implied_value(struct expression *expr, sval_t *sval)
 836 {
 837         int undefined = 0;
 838         sval_t ret;
 839
 840         ret =  _get_value(expr, &undefined, IMPLIED);
 841         if (undefined)
 842                 return 0;
 843         *sval = ret;
 844         return 1;
 845 }
 846
 847 int get_implied_min(struct expression *expr, sval_t *sval)
 848 {
 849         int undefined = 0;
 850         sval_t ret;
 851
 852         ret =  _get_value(expr, &undefined, IMPLIED_MIN);
 853         if (undefined)
 854                 return 0;
 855         *sval = ret;
 856         return 1;
 857 }
 858
 859 int get_implied_max(struct expression *expr, sval_t *sval)
 860 {
 861         int undefined = 0;
 862         sval_t ret;
 863
 864         ret =  _get_value(expr, &undefined, IMPLIED_MAX);
 865         if (undefined)
 866                 return 0;
 867         *sval = ret;
 868         return 1;
 869 }
 870
 871 int get_implied_rl(struct expression *expr, struct range_list **rl)
 872 {
 873         sval_t sval;
 874         struct smatch_state *state;
 875         sval_t min, max;
 876         int min_known = 0;
 877         int max_known = 0;
 878
 879         *rl = NULL;
 880
 881         expr = strip_parens(expr);
 882         if (!expr)
 883                 return 0;
 884
 885         state = get_state_expr(SMATCH_EXTRA, expr);
 886         if (state) {
 887                 *rl = clone_rl(estate_rl(state));
 888                 return 1;
 889         }
 890
 891         if (expr->type == EXPR_CALL) {
 892                 if (get_implied_return(expr, rl))
 893                         return 1;
 894                 *rl = db_return_vals(expr);
 895                 if (*rl)
 896                         return 1;
 897                 return 0;
 898         }
 899
 900         if (get_implied_value(expr, &sval)) {
 901                 add_range(rl, sval, sval);
 902                 return 1;
 903         }
 904
 905         if (get_local_rl(expr, rl))
 906                 return 1;
 907
 908         min_known = get_implied_min(expr, &min);
 909         max_known = get_implied_max(expr, &max);
 910         if (!min_known && !max_known)
 911                 return 0;
 912         if (!min_known)
 913                 get_absolute_min(expr, &min);
 914         if (!max_known)
 915                 get_absolute_max(expr, &max);
 916
 917         *rl = alloc_rl(min, max);
 918         return 1;
 919 }
 920
 921 int get_hard_max(struct expression *expr, sval_t *sval)
 922 {
 923         int undefined = 0;
 924         sval_t ret;
 925
 926         ret =  _get_value(expr, &undefined, HARD_MAX);
 927         if (undefined)
 928                 return 0;
 929         *sval = ret;
 930         return 1;
 931 }
 932
 933 int get_fuzzy_min(struct expression *expr, sval_t *sval)
 934 {
 935         int undefined = 0;
 936         sval_t ret;
 937
 938         ret =  _get_value(expr, &undefined, FUZZY_MIN);
 939         if (undefined)
 940                 return 0;
 941         *sval = ret;
 942         return 1;
 943 }
 944
 945 int get_fuzzy_max(struct expression *expr, sval_t *sval)
 946 {
 947         int undefined = 0;
 948         sval_t ret;
 949
 950         ret =  _get_value(expr, &undefined, FUZZY_MAX);
 951         if (undefined)
 952                 return 0;
 953         if (ret.uvalue > INT_MAX - 10000)
 954                 return 0;
 955         *sval = ret;
 956         return 1;
 957 }
 958
 959 int get_absolute_min(struct expression *expr, sval_t *sval)
 960 {
 961         int undefined = 0;
 962         struct symbol *type;
 963
 964         type = get_type(expr);
 965         if (!type)
 966                 type = &llong_ctype;  // FIXME: this is wrong but places assume get type can't fail.
 967         *sval =  _get_value(expr, &undefined, ABSOLUTE_MIN);
 968         if (undefined) {
 969                 *sval = sval_type_min(type);
 970                 return 1;
 971         }
 972
 973         if (sval_cmp(*sval, sval_type_min(type)) < 0)
 974                 *sval = sval_type_min(type);
 975         return 1;
 976 }
 977
 978 int get_absolute_max(struct expression *expr, sval_t *sval)
 979 {
 980         int undefined = 0;
 981         struct symbol *type;
 982
 983         type = get_type(expr);
 984         if (!type)
 985                 type = &llong_ctype;
 986         *sval = _get_value(expr, &undefined, ABSOLUTE_MAX);
 987         if (undefined) {
 988                 *sval = sval_type_max(type);
 989                 return 1;
 990         }
 991
 992         if (sval_cmp(sval_type_max(type), *sval) < 0)
 993                 *sval = sval_type_max(type);
 994         return 1;
 995 }
 996
 997 int known_condition_true(struct expression *expr)
 998 {
 999         sval_t tmp;
1000
1001         if (!expr)
1002                 return 0;
1003
1004         if (get_value(expr, &tmp) && tmp.value)
1005                 return 1;
1006
1007         return 0;
1008 }
1009
1010 int known_condition_false(struct expression *expr)
1011 {
1012         if (!expr)
1013                 return 0;
1014
1015         if (is_zero(expr))
1016                 return 1;
1017
1018         if (expr->type == EXPR_CALL) {
1019                 if (sym_name_is("__builtin_constant_p", expr->fn))
1020                         return 1;
1021         }
1022         return 0;
1023 }
1024
1025 int implied_condition_true(struct expression *expr)
1026 {
1027         sval_t tmp;
1028
1029         if (!expr)
1030                 return 0;
1031
1032         if (known_condition_true(expr))
1033                 return 1;
1034         if (get_implied_value(expr, &tmp) && tmp.value)
1035                 return 1;
1036
1037         if (expr->type == EXPR_POSTOP)
1038                 return implied_condition_true(expr->unop);
1039
1040         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
1041                 return implied_not_equal(expr->unop, 1);
1042         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
1043                 return implied_not_equal(expr->unop, -1);
1044
1045         expr = strip_expr(expr);
1046         switch (expr->type) {
1047         case EXPR_COMPARE:
1048                 if (do_comparison(expr) == 1)
1049                         return 1;
1050                 break;
1051         case EXPR_PREOP:
1052                 if (expr->op == '!') {
1053                         if (implied_condition_false(expr->unop))
1054                                 return 1;
1055                         break;
1056                 }
1057                 break;
1058         default:
1059                 if (implied_not_equal(expr, 0) == 1)
1060                         return 1;
1061                 break;
1062         }
1063         return 0;
1064 }
1065
1066 int implied_condition_false(struct expression *expr)
1067 {
1068         struct expression *tmp;
1069         sval_t sval;
1070
1071         if (!expr)
1072                 return 0;
1073
1074         if (known_condition_false(expr))
1075                 return 1;
1076
1077         switch (expr->type) {
1078         case EXPR_COMPARE:
1079                 if (do_comparison(expr) == 2)
1080                         return 1;
1081         case EXPR_PREOP:
1082                 if (expr->op == '!') {
1083                         if (implied_condition_true(expr->unop))
1084                                 return 1;
1085                         break;
1086                 }
1087                 tmp = strip_expr(expr);
1088                 if (tmp != expr)
1089                         return implied_condition_false(tmp);
1090                 break;
1091         default:
1092                 if (get_implied_value(expr, &sval) && sval.value == 0)
1093                         return 1;
1094                 break;
1095         }
1096         return 0;
1097 }