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