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