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         sval_t left, right;
 187
 188         left = _get_value(expr->left, undefined, implied);
 189         right = _get_value(expr->right, undefined, opposite_implied(implied));
 190
 191         return sval_binop(left, '-', right);
 192 }
 193
 194 static sval_t handle_mod(struct expression *expr, int *undefined, int implied)
 195 {
 196         sval_t left, right;
 197
 198         /* if we can't figure out the right side it's probably hopeless */
 199         right = _get_value(expr->right, undefined, implied);
 200         if (*undefined || right.value == 0)
 201                 return bogus;
 202
 203         left = _get_value(expr->left, undefined, implied);
 204         if (!*undefined)
 205                 return sval_binop(left, '%', right);
 206
 207         switch (implied) {
 208         case NOTIMPLIED:
 209         case IMPLIED:
 210                 return bogus;
 211         case IMPLIED_MIN:
 212         case FUZZY_MIN:
 213         case ABSOLUTE_MIN:
 214                 *undefined = 0;
 215                 return sval_type_val(get_type(expr->left), 0);
 216         case IMPLIED_MAX:
 217         case FUZZY_MAX:
 218         case ABSOLUTE_MAX:
 219                 *undefined = 0;
 220                 right = sval_cast(get_type(expr), right);
 221                 right.value--;
 222                 return right;
 223         }
 224         return bogus;
 225 }
 226
 227 static sval_t handle_binop(struct expression *expr, int *undefined, int implied)
 228 {
 229         struct symbol *type;
 230         sval_t left, right;
 231         sval_t ret = {.type = &int_ctype, .value = 123456};
 232         int local_undef = 0;
 233
 234         switch (expr->op) {
 235         case '%':
 236                 return handle_mod(expr, undefined, implied);
 237         case '&':
 238                 left = _get_value(expr->left, &local_undef, implied);
 239                 if (local_undef) {
 240                         if (implied == IMPLIED_MIN || implied == ABSOLUTE_MIN) {
 241                                 ret = sval_blank(expr->left);
 242                                 ret.value = 0;
 243                                 return ret;
 244                         }
 245                         if (implied != IMPLIED_MAX && implied != ABSOLUTE_MAX)
 246                                 *undefined = 1;
 247                         if (!get_absolute_max(expr->left, &left))
 248                                 *undefined = 1;
 249                 }
 250                 right = _get_value(expr->right, undefined, implied);
 251                 if (*undefined)
 252                         return bogus;
 253                 return sval_binop(left, '&', right);
 254
 255         case SPECIAL_RIGHTSHIFT:
 256                 left = _get_value(expr->left, &local_undef, implied);
 257                 if (local_undef) {
 258                         if (implied == IMPLIED_MIN || implied == ABSOLUTE_MIN) {
 259                                 ret = sval_blank(expr->left);
 260                                 ret.value = 0;
 261                                 return ret;
 262                         }
 263                         if (implied != IMPLIED_MAX && implied != ABSOLUTE_MAX)
 264                                 *undefined = 1;
 265                         if (!get_absolute_max(expr->left, &left))
 266                                 *undefined = 1;
 267                 }
 268                 right = _get_value(expr->right, undefined, implied);
 269                 if (*undefined)
 270                         return bogus;
 271                 return sval_binop(left, SPECIAL_RIGHTSHIFT, right);
 272         }
 273
 274         left = _get_value(expr->left, undefined, implied);
 275         right = _get_value(expr->right, undefined, implied);
 276
 277         if (*undefined)
 278                 return bogus;
 279
 280         type = get_type(expr);
 281         left = sval_cast(type, left);
 282         right = sval_cast(type, right);
 283
 284         switch (implied) {
 285         case IMPLIED_MAX:
 286         case FUZZY_MAX:
 287         case ABSOLUTE_MAX:
 288                 if (sval_binop_overflows(left, expr->op, right))
 289                         return sval_type_max(get_type(expr));
 290                 break;
 291         case HARD_MAX:
 292                 if (sval_binop_overflows(left, expr->op, right)) {
 293                         *undefined = 1;
 294                         return bogus;
 295                 }
 296         }
 297
 298         switch (expr->op) {
 299         case '/':
 300                 return handle_divide(expr, undefined, implied);
 301         case '%':
 302                 if (right.value == 0) {
 303                         *undefined = 1;
 304                         return bogus;
 305                 } else {
 306                         return sval_binop(left, '%', right);
 307                 }
 308         case '-':
 309                 ret = handle_subtract(expr, undefined, implied);
 310                 break;
 311         default:
 312                 ret = sval_binop(left, expr->op, right);
 313         }
 314         return ret;
 315 }
 316
 317 static int do_comparison(struct expression *expr)
 318 {
 319         struct range_list *left_ranges = NULL;
 320         struct range_list *right_ranges = NULL;
 321         int poss_true, poss_false;
 322
 323         get_implied_range_list(expr->left, &left_ranges);
 324         get_implied_range_list(expr->right, &right_ranges);
 325
 326         poss_true = possibly_true_range_lists(left_ranges, expr->op, right_ranges);
 327         poss_false = possibly_false_range_lists(left_ranges, expr->op, right_ranges);
 328
 329         free_range_list(&left_ranges);
 330         free_range_list(&right_ranges);
 331
 332         if (!poss_true && !poss_false)
 333                 return 0;
 334         if (poss_true && !poss_false)
 335                 return 1;
 336         if (!poss_true && poss_false)
 337                 return 2;
 338         return 3;
 339 }
 340
 341 static sval_t handle_comparison(struct expression *expr, int *undefined, int implied)
 342 {
 343         sval_t left, right;
 344         int res;
 345
 346         if (get_value(expr->left, &left) && get_value(expr->right, &right)) {
 347                 struct data_range tmp_left, tmp_right;
 348
 349                 tmp_left.min = left;
 350                 tmp_left.max = left;
 351                 tmp_right.min = right;
 352                 tmp_right.max = right;
 353                 if (true_comparison_range(&tmp_left, expr->op, &tmp_right))
 354                         return one;
 355                 return zero;
 356         }
 357
 358         if (implied == NOTIMPLIED) {
 359                 *undefined = 1;
 360                 return bogus;
 361         }
 362
 363         res = do_comparison(expr);
 364         if (res == 1)
 365                 return one;
 366         if (res == 2)
 367                 return zero;
 368
 369         if (implied == IMPLIED_MIN || implied == FUZZY_MIN || implied == ABSOLUTE_MIN)
 370                 return zero;
 371         if (implied == IMPLIED_MAX || implied == FUZZY_MAX || implied == ABSOLUTE_MAX)
 372                 return one;
 373
 374         *undefined = 1;
 375         return bogus;
 376 }
 377
 378 static sval_t handle_logical(struct expression *expr, int *undefined, int implied)
 379 {
 380         sval_t left, right;
 381
 382         if ((implied == NOTIMPLIED && get_value(expr->left, &left) &&
 383                                       get_value(expr->right, &right)) ||
 384             (implied != NOTIMPLIED && get_implied_value(expr->left, &left) &&
 385                                       get_implied_value(expr->right, &right))) {
 386                 switch (expr->op) {
 387                 case SPECIAL_LOGICAL_OR:
 388                         if (left.value || right.value)
 389                                 return one;
 390                         return zero;
 391                 case SPECIAL_LOGICAL_AND:
 392                         if (left.value && right.value)
 393                                 return one;
 394                         return zero;
 395                 default:
 396                         *undefined = 1;
 397                         return bogus;
 398                 }
 399         }
 400
 401         if (implied == IMPLIED_MIN || implied == FUZZY_MIN || implied == ABSOLUTE_MIN)
 402                 return zero;
 403         if (implied == IMPLIED_MAX || implied == FUZZY_MAX || implied == ABSOLUTE_MAX)
 404                 return one;
 405
 406         *undefined = 1;
 407         return bogus;
 408 }
 409
 410 static sval_t handle_conditional(struct expression *expr, int *undefined, int implied)
 411 {
 412         if (known_condition_true(expr->conditional))
 413                 return _get_value(expr->cond_true, undefined, implied);
 414         if (known_condition_false(expr->conditional))
 415                 return _get_value(expr->cond_false, undefined, implied);
 416
 417         if (implied == NOTIMPLIED) {
 418                 *undefined = 1;
 419                 return bogus;
 420         }
 421
 422         if (implied_condition_true(expr->conditional))
 423                 return _get_value(expr->cond_true, undefined, implied);
 424         if (implied_condition_false(expr->conditional))
 425                 return _get_value(expr->cond_false, undefined, implied);
 426
 427         *undefined = 1;
 428         return bogus;
 429 }
 430
 431 static int get_implied_value_helper(struct expression *expr, sval_t *sval, int implied)
 432 {
 433         struct smatch_state *state;
 434         struct symbol *sym;
 435         char *name;
 436
 437         /* fixme: this should return the casted value */
 438
 439         expr = strip_expr(expr);
 440
 441         if (get_value(expr, sval))
 442                 return 1;
 443
 444         name = get_variable_from_expr(expr, &sym);
 445         if (!name)
 446                 return 0;
 447         *sval = sval_blank(expr);
 448         state = get_state(SMATCH_EXTRA, name, sym);
 449         free_string(name);
 450         if (!state || !state->data)
 451                 return 0;
 452         if (implied == IMPLIED) {
 453                 if (estate_get_single_value(state, sval))
 454                         return 1;
 455                 return 0;
 456         }
 457         if (implied == HARD_MAX) {
 458                 if (estate_get_hard_max(state, sval))
 459                         return 1;
 460                 return 0;
 461         }
 462         if (implied == IMPLIED_MAX) {
 463                 *sval = estate_max(state);
 464                 if (sval_is_max(*sval)) /* this means just guessing.  fixme. not really */
 465                         return 0;
 466                 return 1;
 467         }
 468         *sval = estate_min(state);
 469         if (sval_is_min(*sval))       /* fixme */
 470                 return 0;
 471         return 1;
 472 }
 473
 474 static int get_fuzzy_max_helper(struct expression *expr, sval_t *max)
 475 {
 476         struct sm_state *sm;
 477         struct sm_state *tmp;
 478         sval_t sval;
 479
 480         if (get_hard_max(expr, &sval)) {
 481                 *max = sval;
 482                 return 1;
 483         }
 484
 485         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 486         if (!sm)
 487                 return 0;
 488
 489         sval = sval_type_min(estate_type(sm->state));
 490         FOR_EACH_PTR(sm->possible, tmp) {
 491                 sval_t new_min;
 492
 493                 new_min = estate_min(tmp->state);
 494                 if (sval_cmp(new_min, sval) > 0)
 495                         sval = new_min;
 496         } END_FOR_EACH_PTR(tmp);
 497
 498         if (sval_is_min(sval))
 499                 return 0;
 500
 501         *max = sval_cast(get_type(expr), sval);
 502         return 1;
 503 }
 504
 505 static int get_fuzzy_min_helper(struct expression *expr, sval_t *min)
 506 {
 507         struct sm_state *sm;
 508         struct sm_state *tmp;
 509         sval_t sval;
 510
 511         if (get_implied_min(expr, min))
 512                 return 1;
 513
 514         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 515         if (!sm)
 516                 return 0;
 517
 518         sval = sval_type_max(estate_type(sm->state));
 519         FOR_EACH_PTR(sm->possible, tmp) {
 520                 sval_t new_max;
 521
 522                 new_max = estate_max(tmp->state);
 523                 if (sval_cmp(new_max, sval) < 0)
 524                         sval = new_max;
 525         } END_FOR_EACH_PTR(tmp);
 526
 527         if (sval_is_max(sval))
 528                 return 0;
 529         *min = sval_cast(get_type(expr), sval);
 530         return 1;
 531 }
 532
 533 static sval_t _get_implied_value(struct expression *expr, int *undefined, int implied)
 534 {
 535         sval_t ret;
 536
 537         ret = sval_blank(expr);
 538
 539         switch (implied) {
 540         case IMPLIED:
 541         case IMPLIED_MAX:
 542         case IMPLIED_MIN:
 543         case HARD_MAX:
 544                 if (!get_implied_value_helper(expr, &ret, implied))
 545                         *undefined = 1;
 546                 break;
 547         case ABSOLUTE_MIN:
 548                 if (!get_absolute_min_helper(expr, &ret))
 549                         *undefined = 1;
 550                 break;
 551         case ABSOLUTE_MAX:
 552                 if (!get_absolute_max_helper(expr, &ret))
 553                         *undefined = 1;
 554                 break;
 555         case FUZZY_MAX:
 556                 if (!get_fuzzy_max_helper(expr, &ret))
 557                         *undefined = 1;
 558                 break;
 559         case FUZZY_MIN:
 560                 if (!get_fuzzy_min_helper(expr, &ret))
 561                         *undefined = 1;
 562                 break;
 563         default:
 564                 *undefined = 1;
 565         }
 566         return ret;
 567 }
 568
 569 static int get_const_value(struct expression *expr, sval_t *sval)
 570 {
 571         struct symbol *sym;
 572         sval_t right;
 573
 574         if (expr->type != EXPR_SYMBOL || !expr->symbol)
 575                 return 0;
 576         sym = expr->symbol;
 577         if (!(sym->ctype.modifiers & MOD_CONST))
 578                 return 0;
 579         if (get_value(sym->initializer, &right)) {
 580                 *sval = sval_cast(get_type(expr), right);
 581                 return 1;
 582         }
 583         return 0;
 584 }
 585
 586 static sval_t _get_value(struct expression *expr, int *undefined, int implied)
 587 {
 588         sval_t ret;
 589
 590         if (!expr) {
 591                 *undefined = 1;
 592                 return bogus;
 593         }
 594         if (*undefined)
 595                 return bogus;
 596
 597         expr = strip_parens(expr);
 598
 599         switch (expr->type) {
 600         case EXPR_VALUE:
 601                 ret = sval_from_val(expr, expr->value);
 602                 break;
 603         case EXPR_PREOP:
 604                 ret = handle_preop(expr, undefined, implied);
 605                 break;
 606         case EXPR_POSTOP:
 607                 ret = _get_value(expr->unop, undefined, implied);
 608                 break;
 609         case EXPR_CAST:
 610         case EXPR_FORCE_CAST:
 611         case EXPR_IMPLIED_CAST:
 612                 ret = _get_value(expr->cast_expression, undefined, implied);
 613                 ret = sval_cast(get_type(expr), ret);
 614                 break;
 615         case EXPR_BINOP:
 616                 ret = handle_binop(expr, undefined, implied);
 617                 break;
 618         case EXPR_COMPARE:
 619                 ret = handle_comparison(expr, undefined, implied);
 620                 break;
 621         case EXPR_LOGICAL:
 622                 ret = handle_logical(expr, undefined, implied);
 623                 break;
 624         case EXPR_PTRSIZEOF:
 625         case EXPR_SIZEOF:
 626                 ret = sval_blank(expr);
 627                 ret.value = get_expression_value_nomod(expr);
 628                 break;
 629         case EXPR_SYMBOL:
 630                 if (get_const_value(expr, &ret)) {
 631                         break;
 632                 }
 633                 ret = _get_implied_value(expr, undefined, implied);
 634                 break;
 635         case EXPR_SELECT:
 636         case EXPR_CONDITIONAL:
 637                 ret = handle_conditional(expr, undefined, implied);
 638                 break;
 639         default:
 640                 ret = _get_implied_value(expr, undefined, implied);
 641         }
 642         if (*undefined)
 643                 return bogus;
 644         return ret;
 645 }
 646
 647 /* returns 1 if it can get a value literal or else returns 0 */
 648 int get_value(struct expression *expr, sval_t *sval)
 649 {
 650         int undefined = 0;
 651         sval_t ret;
 652
 653         ret = _get_value(expr, &undefined, NOTIMPLIED);
 654         if (undefined)
 655                 return 0;
 656         *sval = ret;
 657         return 1;
 658 }
 659
 660 int get_implied_value(struct expression *expr, sval_t *sval)
 661 {
 662         int undefined = 0;
 663         sval_t ret;
 664
 665         ret =  _get_value(expr, &undefined, IMPLIED);
 666         if (undefined)
 667                 return 0;
 668         *sval = ret;
 669         return 1;
 670 }
 671
 672 int get_implied_min(struct expression *expr, sval_t *sval)
 673 {
 674         int undefined = 0;
 675         sval_t ret;
 676
 677         ret =  _get_value(expr, &undefined, IMPLIED_MIN);
 678         if (undefined)
 679                 return 0;
 680         *sval = ret;
 681         return 1;
 682 }
 683
 684 int get_implied_max(struct expression *expr, sval_t *sval)
 685 {
 686         int undefined = 0;
 687         sval_t ret;
 688
 689         ret =  _get_value(expr, &undefined, IMPLIED_MAX);
 690         if (undefined)
 691                 return 0;
 692         *sval = ret;
 693         return 1;
 694 }
 695
 696 int get_implied_range_list(struct expression *expr, struct range_list **rl)
 697 {
 698         sval_t sval;
 699         struct smatch_state *state;
 700         sval_t min, max;
 701
 702         *rl = NULL;
 703
 704         expr = strip_parens(expr);
 705         if (!expr)
 706                 return 0;
 707
 708         state = get_state_expr(SMATCH_EXTRA, expr);
 709         if (state) {
 710                 *rl = clone_range_list(estate_ranges(state));
 711                 return 1;
 712         }
 713
 714         if (expr->type == EXPR_CALL) {
 715                 if (get_implied_return(expr, rl))
 716                         return 1;
 717                 *rl = db_return_vals(expr);
 718                 if (*rl)
 719                         return 1;
 720                 return 0;
 721         }
 722
 723         if (get_implied_value(expr, &sval)) {
 724                 add_range(rl, sval, sval);
 725                 return 1;
 726         }
 727
 728         if (!get_implied_min(expr, &min))
 729                 return 0;
 730         if (!get_implied_max(expr, &max))
 731                 return 0;
 732
 733         *rl = alloc_range_list(min, max);
 734         return 1;
 735 }
 736
 737 int get_hard_max(struct expression *expr, sval_t *sval)
 738 {
 739         int undefined = 0;
 740         sval_t ret;
 741
 742         ret =  _get_value(expr, &undefined, HARD_MAX);
 743         if (undefined)
 744                 return 0;
 745         *sval = ret;
 746         return 1;
 747 }
 748
 749 int get_fuzzy_min(struct expression *expr, sval_t *sval)
 750 {
 751         int undefined = 0;
 752         sval_t ret;
 753
 754         ret =  _get_value(expr, &undefined, FUZZY_MIN);
 755         if (undefined)
 756                 return 0;
 757         *sval = ret;
 758         return 1;
 759 }
 760
 761 int get_fuzzy_max(struct expression *expr, sval_t *sval)
 762 {
 763         int undefined = 0;
 764         sval_t ret;
 765
 766         ret =  _get_value(expr, &undefined, FUZZY_MAX);
 767         if (undefined)
 768                 return 0;
 769         *sval = ret;
 770         return 1;
 771 }
 772
 773 int get_absolute_min(struct expression *expr, sval_t *sval)
 774 {
 775         int undefined = 0;
 776         struct symbol *type;
 777
 778         type = get_type(expr);
 779         if (!type)
 780                 type = &llong_ctype;  // FIXME: this is wrong but places assume get type can't fail.
 781         *sval =  _get_value(expr, &undefined, ABSOLUTE_MIN);
 782         if (undefined) {
 783                 *sval = sval_type_min(type);
 784                 return 1;
 785         }
 786
 787         if (sval_cmp(*sval, sval_type_min(type)) < 0)
 788                 *sval = sval_type_min(type);
 789         return 1;
 790 }
 791
 792 int get_absolute_max(struct expression *expr, sval_t *sval)
 793 {
 794         int undefined = 0;
 795         struct symbol *type;
 796
 797         type = get_type(expr);
 798         if (!type)
 799                 type = &llong_ctype;
 800         *sval = _get_value(expr, &undefined, ABSOLUTE_MAX);
 801         if (undefined) {
 802                 *sval = sval_type_max(type);
 803                 return 1;
 804         }
 805
 806         if (sval_cmp(sval_type_max(type), *sval) < 0)
 807                 *sval = sval_type_max(type);
 808         return 1;
 809 }
 810
 811 int known_condition_true(struct expression *expr)
 812 {
 813         sval_t tmp;
 814
 815         if (!expr)
 816                 return 0;
 817
 818         if (get_value(expr, &tmp) && tmp.value)
 819                 return 1;
 820
 821         return 0;
 822 }
 823
 824 int known_condition_false(struct expression *expr)
 825 {
 826         if (!expr)
 827                 return 0;
 828
 829         if (is_zero(expr))
 830                 return 1;
 831
 832         if (expr->type == EXPR_CALL) {
 833                 if (sym_name_is("__builtin_constant_p", expr->fn))
 834                         return 1;
 835         }
 836         return 0;
 837 }
 838
 839 int implied_condition_true(struct expression *expr)
 840 {
 841         sval_t tmp;
 842
 843         if (!expr)
 844                 return 0;
 845
 846         if (known_condition_true(expr))
 847                 return 1;
 848         if (get_implied_value(expr, &tmp) && tmp.value)
 849                 return 1;
 850
 851         if (expr->type == EXPR_POSTOP)
 852                 return implied_condition_true(expr->unop);
 853
 854         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
 855                 return implied_not_equal(expr->unop, 1);
 856         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
 857                 return implied_not_equal(expr->unop, -1);
 858
 859         expr = strip_expr(expr);
 860         switch (expr->type) {
 861         case EXPR_COMPARE:
 862                 if (do_comparison(expr) == 1)
 863                         return 1;
 864                 break;
 865         case EXPR_PREOP:
 866                 if (expr->op == '!') {
 867                         if (implied_condition_false(expr->unop))
 868                                 return 1;
 869                         break;
 870                 }
 871                 break;
 872         default:
 873                 if (implied_not_equal(expr, 0) == 1)
 874                         return 1;
 875                 break;
 876         }
 877         return 0;
 878 }
 879
 880 int implied_condition_false(struct expression *expr)
 881 {
 882         struct expression *tmp;
 883         sval_t sval;
 884
 885         if (!expr)
 886                 return 0;
 887
 888         if (known_condition_false(expr))
 889                 return 1;
 890
 891         switch (expr->type) {
 892         case EXPR_COMPARE:
 893                 if (do_comparison(expr) == 2)
 894                         return 1;
 895         case EXPR_PREOP:
 896                 if (expr->op == '!') {
 897                         if (implied_condition_true(expr->unop))
 898                                 return 1;
 899                         break;
 900                 }
 901                 tmp = strip_expr(expr);
 902                 if (tmp != expr)
 903                         return implied_condition_false(tmp);
 904                 break;
 905         default:
 906                 if (get_implied_value(expr, &sval) && sval.value == 0)
 907                         return 1;
 908                 break;
 909         }
 910         return 0;
 911 }