smatch_math.c

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