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 ABSOLUTE_MAX:
 287                 if (sval_binop_overflows(left, expr->op, right))
 288                         return sval_type_max(get_type(expr));
 289                 break;
 290         case HARD_MAX:
 291         case FUZZY_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         int left_known = 0;
 382         int right_known = 0;
 383
 384         if (implied == NOTIMPLIED) {
 385                 if (get_value(expr->left, &left))
 386                         left_known = 1;
 387                 if (get_value(expr->right, &right))
 388                         right_known = 1;
 389         } else {
 390                 if (get_implied_value(expr->left, &left))
 391                         left_known = 1;
 392                 if (get_implied_value(expr->right, &right))
 393                         right_known = 1;
 394         }
 395
 396         switch (expr->op) {
 397         case SPECIAL_LOGICAL_OR:
 398                 if (left_known && left.value)
 399                         return one;
 400                 if (right_known && right.value)
 401                         return one;
 402                 if (left_known && right_known)
 403                         return zero;
 404                 break;
 405         case SPECIAL_LOGICAL_AND:
 406                 if (left_known && right_known) {
 407                         if (left.value && right.value)
 408                                 return one;
 409                         return zero;
 410                 }
 411                 break;
 412         default:
 413                 *undefined = 1;
 414                 return bogus;
 415         }
 416
 417         if (implied == IMPLIED_MIN || implied == FUZZY_MIN || implied == ABSOLUTE_MIN)
 418                 return zero;
 419         if (implied == IMPLIED_MAX || implied == FUZZY_MAX || implied == ABSOLUTE_MAX)
 420                 return one;
 421
 422         *undefined = 1;
 423         return bogus;
 424 }
 425
 426 static sval_t handle_conditional(struct expression *expr, int *undefined, int implied)
 427 {
 428         if (known_condition_true(expr->conditional))
 429                 return _get_value(expr->cond_true, undefined, implied);
 430         if (known_condition_false(expr->conditional))
 431                 return _get_value(expr->cond_false, undefined, implied);
 432
 433         if (implied == NOTIMPLIED) {
 434                 *undefined = 1;
 435                 return bogus;
 436         }
 437
 438         if (implied_condition_true(expr->conditional))
 439                 return _get_value(expr->cond_true, undefined, implied);
 440         if (implied_condition_false(expr->conditional))
 441                 return _get_value(expr->cond_false, undefined, implied);
 442
 443         *undefined = 1;
 444         return bogus;
 445 }
 446
 447 static int get_implied_value_helper(struct expression *expr, sval_t *sval, int implied)
 448 {
 449         struct smatch_state *state;
 450         struct symbol *sym;
 451         char *name;
 452
 453         /* fixme: this should return the casted value */
 454
 455         expr = strip_expr(expr);
 456
 457         if (get_value(expr, sval))
 458                 return 1;
 459
 460         name = get_variable_from_expr(expr, &sym);
 461         if (!name)
 462                 return 0;
 463         *sval = sval_blank(expr);
 464         state = get_state(SMATCH_EXTRA, name, sym);
 465         free_string(name);
 466         if (!state || !state->data)
 467                 return 0;
 468         if (implied == IMPLIED) {
 469                 if (estate_get_single_value(state, sval))
 470                         return 1;
 471                 return 0;
 472         }
 473         if (implied == HARD_MAX) {
 474                 if (estate_get_hard_max(state, sval))
 475                         return 1;
 476                 return 0;
 477         }
 478         if (implied == IMPLIED_MAX) {
 479                 *sval = estate_max(state);
 480                 if (sval_is_max(*sval)) /* this means just guessing.  fixme. not really */
 481                         return 0;
 482                 return 1;
 483         }
 484         *sval = estate_min(state);
 485         if (sval_is_min(*sval))       /* fixme */
 486                 return 0;
 487         return 1;
 488 }
 489
 490 static int get_fuzzy_max_helper(struct expression *expr, sval_t *max)
 491 {
 492         struct sm_state *sm;
 493         struct sm_state *tmp;
 494         sval_t sval;
 495
 496         if (get_hard_max(expr, &sval)) {
 497                 *max = sval;
 498                 return 1;
 499         }
 500
 501         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 502         if (!sm)
 503                 return 0;
 504
 505         sval = sval_type_min(estate_type(sm->state));
 506         FOR_EACH_PTR(sm->possible, tmp) {
 507                 sval_t new_min;
 508
 509                 new_min = estate_min(tmp->state);
 510                 if (sval_cmp(new_min, sval) > 0)
 511                         sval = new_min;
 512         } END_FOR_EACH_PTR(tmp);
 513
 514         if (sval_is_min(sval))
 515                 return 0;
 516         if (sval.value == sval_type_min(sval.type).value + 1)  /* it's common to be on off */
 517                 return 0;
 518
 519         *max = sval_cast(get_type(expr), sval);
 520         return 1;
 521 }
 522
 523 static int get_fuzzy_min_helper(struct expression *expr, sval_t *min)
 524 {
 525         struct sm_state *sm;
 526         struct sm_state *tmp;
 527         sval_t sval;
 528
 529         if (get_implied_min(expr, min))
 530                 return 1;
 531
 532         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 533         if (!sm)
 534                 return 0;
 535
 536         sval = sval_type_max(estate_type(sm->state));
 537         FOR_EACH_PTR(sm->possible, tmp) {
 538                 sval_t new_max;
 539
 540                 new_max = estate_max(tmp->state);
 541                 if (sval_cmp(new_max, sval) < 0)
 542                         sval = new_max;
 543         } END_FOR_EACH_PTR(tmp);
 544
 545         if (sval_is_max(sval))
 546                 return 0;
 547         *min = sval_cast(get_type(expr), sval);
 548         return 1;
 549 }
 550
 551 static sval_t _get_implied_value(struct expression *expr, int *undefined, int implied)
 552 {
 553         sval_t ret;
 554
 555         ret = sval_blank(expr);
 556
 557         switch (implied) {
 558         case IMPLIED:
 559         case IMPLIED_MAX:
 560         case IMPLIED_MIN:
 561         case HARD_MAX:
 562                 if (!get_implied_value_helper(expr, &ret, implied))
 563                         *undefined = 1;
 564                 break;
 565         case ABSOLUTE_MIN:
 566                 if (!get_absolute_min_helper(expr, &ret))
 567                         *undefined = 1;
 568                 break;
 569         case ABSOLUTE_MAX:
 570                 if (!get_absolute_max_helper(expr, &ret))
 571                         *undefined = 1;
 572                 break;
 573         case FUZZY_MAX:
 574                 if (!get_fuzzy_max_helper(expr, &ret))
 575                         *undefined = 1;
 576                 break;
 577         case FUZZY_MIN:
 578                 if (!get_fuzzy_min_helper(expr, &ret))
 579                         *undefined = 1;
 580                 break;
 581         default:
 582                 *undefined = 1;
 583         }
 584         return ret;
 585 }
 586
 587 static int get_const_value(struct expression *expr, sval_t *sval)
 588 {
 589         struct symbol *sym;
 590         sval_t right;
 591
 592         if (expr->type != EXPR_SYMBOL || !expr->symbol)
 593                 return 0;
 594         sym = expr->symbol;
 595         if (!(sym->ctype.modifiers & MOD_CONST))
 596                 return 0;
 597         if (get_value(sym->initializer, &right)) {
 598                 *sval = sval_cast(get_type(expr), right);
 599                 return 1;
 600         }
 601         return 0;
 602 }
 603
 604 static sval_t _get_value(struct expression *expr, int *undefined, int implied)
 605 {
 606         sval_t ret;
 607
 608         if (!expr) {
 609                 *undefined = 1;
 610                 return bogus;
 611         }
 612         if (*undefined)
 613                 return bogus;
 614
 615         expr = strip_parens(expr);
 616
 617         switch (expr->type) {
 618         case EXPR_VALUE:
 619                 ret = sval_from_val(expr, expr->value);
 620                 break;
 621         case EXPR_PREOP:
 622                 ret = handle_preop(expr, undefined, implied);
 623                 break;
 624         case EXPR_POSTOP:
 625                 ret = _get_value(expr->unop, undefined, implied);
 626                 break;
 627         case EXPR_CAST:
 628         case EXPR_FORCE_CAST:
 629         case EXPR_IMPLIED_CAST:
 630                 ret = _get_value(expr->cast_expression, undefined, implied);
 631                 ret = sval_cast(get_type(expr), ret);
 632                 break;
 633         case EXPR_BINOP:
 634                 ret = handle_binop(expr, undefined, implied);
 635                 break;
 636         case EXPR_COMPARE:
 637                 ret = handle_comparison(expr, undefined, implied);
 638                 break;
 639         case EXPR_LOGICAL:
 640                 ret = handle_logical(expr, undefined, implied);
 641                 break;
 642         case EXPR_PTRSIZEOF:
 643         case EXPR_SIZEOF:
 644                 ret = sval_blank(expr);
 645                 ret.value = get_expression_value_nomod(expr);
 646                 break;
 647         case EXPR_SYMBOL:
 648                 if (get_const_value(expr, &ret)) {
 649                         break;
 650                 }
 651                 ret = _get_implied_value(expr, undefined, implied);
 652                 break;
 653         case EXPR_SELECT:
 654         case EXPR_CONDITIONAL:
 655                 ret = handle_conditional(expr, undefined, implied);
 656                 break;
 657         default:
 658                 ret = _get_implied_value(expr, undefined, implied);
 659         }
 660         if (*undefined)
 661                 return bogus;
 662         return ret;
 663 }
 664
 665 /* returns 1 if it can get a value literal or else returns 0 */
 666 int get_value(struct expression *expr, sval_t *sval)
 667 {
 668         int undefined = 0;
 669         sval_t ret;
 670
 671         ret = _get_value(expr, &undefined, NOTIMPLIED);
 672         if (undefined)
 673                 return 0;
 674         *sval = ret;
 675         return 1;
 676 }
 677
 678 int get_implied_value(struct expression *expr, sval_t *sval)
 679 {
 680         int undefined = 0;
 681         sval_t ret;
 682
 683         ret =  _get_value(expr, &undefined, IMPLIED);
 684         if (undefined)
 685                 return 0;
 686         *sval = ret;
 687         return 1;
 688 }
 689
 690 int get_implied_min(struct expression *expr, sval_t *sval)
 691 {
 692         int undefined = 0;
 693         sval_t ret;
 694
 695         ret =  _get_value(expr, &undefined, IMPLIED_MIN);
 696         if (undefined)
 697                 return 0;
 698         *sval = ret;
 699         return 1;
 700 }
 701
 702 int get_implied_max(struct expression *expr, sval_t *sval)
 703 {
 704         int undefined = 0;
 705         sval_t ret;
 706
 707         ret =  _get_value(expr, &undefined, IMPLIED_MAX);
 708         if (undefined)
 709                 return 0;
 710         *sval = ret;
 711         return 1;
 712 }
 713
 714 int get_implied_range_list(struct expression *expr, struct range_list **rl)
 715 {
 716         sval_t sval;
 717         struct smatch_state *state;
 718         sval_t min, max;
 719
 720         *rl = NULL;
 721
 722         expr = strip_parens(expr);
 723         if (!expr)
 724                 return 0;
 725
 726         state = get_state_expr(SMATCH_EXTRA, expr);
 727         if (state) {
 728                 *rl = clone_range_list(estate_ranges(state));
 729                 return 1;
 730         }
 731
 732         if (expr->type == EXPR_CALL) {
 733                 if (get_implied_return(expr, rl))
 734                         return 1;
 735                 *rl = db_return_vals(expr);
 736                 if (*rl)
 737                         return 1;
 738                 return 0;
 739         }
 740
 741         if (get_implied_value(expr, &sval)) {
 742                 add_range(rl, sval, sval);
 743                 return 1;
 744         }
 745
 746         if (!get_implied_min(expr, &min))
 747                 return 0;
 748         if (!get_implied_max(expr, &max))
 749                 return 0;
 750
 751         *rl = alloc_range_list(min, max);
 752         return 1;
 753 }
 754
 755 int get_hard_max(struct expression *expr, sval_t *sval)
 756 {
 757         int undefined = 0;
 758         sval_t ret;
 759
 760         ret =  _get_value(expr, &undefined, HARD_MAX);
 761         if (undefined)
 762                 return 0;
 763         *sval = ret;
 764         return 1;
 765 }
 766
 767 int get_fuzzy_min(struct expression *expr, sval_t *sval)
 768 {
 769         int undefined = 0;
 770         sval_t ret;
 771
 772         ret =  _get_value(expr, &undefined, FUZZY_MIN);
 773         if (undefined)
 774                 return 0;
 775         *sval = ret;
 776         return 1;
 777 }
 778
 779 int get_fuzzy_max(struct expression *expr, sval_t *sval)
 780 {
 781         int undefined = 0;
 782         sval_t ret;
 783
 784         ret =  _get_value(expr, &undefined, FUZZY_MAX);
 785         if (undefined)
 786                 return 0;
 787         *sval = ret;
 788         return 1;
 789 }
 790
 791 int get_absolute_min(struct expression *expr, sval_t *sval)
 792 {
 793         int undefined = 0;
 794         struct symbol *type;
 795
 796         type = get_type(expr);
 797         if (!type)
 798                 type = &llong_ctype;  // FIXME: this is wrong but places assume get type can't fail.
 799         *sval =  _get_value(expr, &undefined, ABSOLUTE_MIN);
 800         if (undefined) {
 801                 *sval = sval_type_min(type);
 802                 return 1;
 803         }
 804
 805         if (sval_cmp(*sval, sval_type_min(type)) < 0)
 806                 *sval = sval_type_min(type);
 807         return 1;
 808 }
 809
 810 int get_absolute_max(struct expression *expr, sval_t *sval)
 811 {
 812         int undefined = 0;
 813         struct symbol *type;
 814
 815         type = get_type(expr);
 816         if (!type)
 817                 type = &llong_ctype;
 818         *sval = _get_value(expr, &undefined, ABSOLUTE_MAX);
 819         if (undefined) {
 820                 *sval = sval_type_max(type);
 821                 return 1;
 822         }
 823
 824         if (sval_cmp(sval_type_max(type), *sval) < 0)
 825                 *sval = sval_type_max(type);
 826         return 1;
 827 }
 828
 829 int known_condition_true(struct expression *expr)
 830 {
 831         sval_t tmp;
 832
 833         if (!expr)
 834                 return 0;
 835
 836         if (get_value(expr, &tmp) && tmp.value)
 837                 return 1;
 838
 839         return 0;
 840 }
 841
 842 int known_condition_false(struct expression *expr)
 843 {
 844         if (!expr)
 845                 return 0;
 846
 847         if (is_zero(expr))
 848                 return 1;
 849
 850         if (expr->type == EXPR_CALL) {
 851                 if (sym_name_is("__builtin_constant_p", expr->fn))
 852                         return 1;
 853         }
 854         return 0;
 855 }
 856
 857 int implied_condition_true(struct expression *expr)
 858 {
 859         sval_t tmp;
 860
 861         if (!expr)
 862                 return 0;
 863
 864         if (known_condition_true(expr))
 865                 return 1;
 866         if (get_implied_value(expr, &tmp) && tmp.value)
 867                 return 1;
 868
 869         if (expr->type == EXPR_POSTOP)
 870                 return implied_condition_true(expr->unop);
 871
 872         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
 873                 return implied_not_equal(expr->unop, 1);
 874         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
 875                 return implied_not_equal(expr->unop, -1);
 876
 877         expr = strip_expr(expr);
 878         switch (expr->type) {
 879         case EXPR_COMPARE:
 880                 if (do_comparison(expr) == 1)
 881                         return 1;
 882                 break;
 883         case EXPR_PREOP:
 884                 if (expr->op == '!') {
 885                         if (implied_condition_false(expr->unop))
 886                                 return 1;
 887                         break;
 888                 }
 889                 break;
 890         default:
 891                 if (implied_not_equal(expr, 0) == 1)
 892                         return 1;
 893                 break;
 894         }
 895         return 0;
 896 }
 897
 898 int implied_condition_false(struct expression *expr)
 899 {
 900         struct expression *tmp;
 901         sval_t sval;
 902
 903         if (!expr)
 904                 return 0;
 905
 906         if (known_condition_false(expr))
 907                 return 1;
 908
 909         switch (expr->type) {
 910         case EXPR_COMPARE:
 911                 if (do_comparison(expr) == 2)
 912                         return 1;
 913         case EXPR_PREOP:
 914                 if (expr->op == '!') {
 915                         if (implied_condition_true(expr->unop))
 916                                 return 1;
 917                         break;
 918                 }
 919                 tmp = strip_expr(expr);
 920                 if (tmp != expr)
 921                         return implied_condition_false(tmp);
 922                 break;
 923         default:
 924                 if (get_implied_value(expr, &sval) && sval.value == 0)
 925                         return 1;
 926                 break;
 927         }
 928         return 0;
 929 }