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
 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         if (sval.value == sval_type_min(sval.type).value + 1)  /* it's common to be on off */
 501                 return 0;
 502
 503         *max = sval_cast(get_type(expr), sval);
 504         return 1;
 505 }
 506
 507 static int get_fuzzy_min_helper(struct expression *expr, sval_t *min)
 508 {
 509         struct sm_state *sm;
 510         struct sm_state *tmp;
 511         sval_t sval;
 512
 513         if (get_implied_min(expr, min))
 514                 return 1;
 515
 516         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 517         if (!sm)
 518                 return 0;
 519
 520         sval = sval_type_max(estate_type(sm->state));
 521         FOR_EACH_PTR(sm->possible, tmp) {
 522                 sval_t new_max;
 523
 524                 new_max = estate_max(tmp->state);
 525                 if (sval_cmp(new_max, sval) < 0)
 526                         sval = new_max;
 527         } END_FOR_EACH_PTR(tmp);
 528
 529         if (sval_is_max(sval))
 530                 return 0;
 531         *min = sval_cast(get_type(expr), sval);
 532         return 1;
 533 }
 534
 535 static sval_t _get_implied_value(struct expression *expr, int *undefined, int implied)
 536 {
 537         sval_t ret;
 538
 539         ret = sval_blank(expr);
 540
 541         switch (implied) {
 542         case IMPLIED:
 543         case IMPLIED_MAX:
 544         case IMPLIED_MIN:
 545         case HARD_MAX:
 546                 if (!get_implied_value_helper(expr, &ret, implied))
 547                         *undefined = 1;
 548                 break;
 549         case ABSOLUTE_MIN:
 550                 if (!get_absolute_min_helper(expr, &ret))
 551                         *undefined = 1;
 552                 break;
 553         case ABSOLUTE_MAX:
 554                 if (!get_absolute_max_helper(expr, &ret))
 555                         *undefined = 1;
 556                 break;
 557         case FUZZY_MAX:
 558                 if (!get_fuzzy_max_helper(expr, &ret))
 559                         *undefined = 1;
 560                 break;
 561         case FUZZY_MIN:
 562                 if (!get_fuzzy_min_helper(expr, &ret))
 563                         *undefined = 1;
 564                 break;
 565         default:
 566                 *undefined = 1;
 567         }
 568         return ret;
 569 }
 570
 571 static int get_const_value(struct expression *expr, sval_t *sval)
 572 {
 573         struct symbol *sym;
 574         sval_t right;
 575
 576         if (expr->type != EXPR_SYMBOL || !expr->symbol)
 577                 return 0;
 578         sym = expr->symbol;
 579         if (!(sym->ctype.modifiers & MOD_CONST))
 580                 return 0;
 581         if (get_value(sym->initializer, &right)) {
 582                 *sval = sval_cast(get_type(expr), right);
 583                 return 1;
 584         }
 585         return 0;
 586 }
 587
 588 static sval_t _get_value(struct expression *expr, int *undefined, int implied)
 589 {
 590         sval_t ret;
 591
 592         if (!expr) {
 593                 *undefined = 1;
 594                 return bogus;
 595         }
 596         if (*undefined)
 597                 return bogus;
 598
 599         expr = strip_parens(expr);
 600
 601         switch (expr->type) {
 602         case EXPR_VALUE:
 603                 ret = sval_from_val(expr, expr->value);
 604                 break;
 605         case EXPR_PREOP:
 606                 ret = handle_preop(expr, undefined, implied);
 607                 break;
 608         case EXPR_POSTOP:
 609                 ret = _get_value(expr->unop, undefined, implied);
 610                 break;
 611         case EXPR_CAST:
 612         case EXPR_FORCE_CAST:
 613         case EXPR_IMPLIED_CAST:
 614                 ret = _get_value(expr->cast_expression, undefined, implied);
 615                 ret = sval_cast(get_type(expr), ret);
 616                 break;
 617         case EXPR_BINOP:
 618                 ret = handle_binop(expr, undefined, implied);
 619                 break;
 620         case EXPR_COMPARE:
 621                 ret = handle_comparison(expr, undefined, implied);
 622                 break;
 623         case EXPR_LOGICAL:
 624                 ret = handle_logical(expr, undefined, implied);
 625                 break;
 626         case EXPR_PTRSIZEOF:
 627         case EXPR_SIZEOF:
 628                 ret = sval_blank(expr);
 629                 ret.value = get_expression_value_nomod(expr);
 630                 break;
 631         case EXPR_SYMBOL:
 632                 if (get_const_value(expr, &ret)) {
 633                         break;
 634                 }
 635                 ret = _get_implied_value(expr, undefined, implied);
 636                 break;
 637         case EXPR_SELECT:
 638         case EXPR_CONDITIONAL:
 639                 ret = handle_conditional(expr, undefined, implied);
 640                 break;
 641         default:
 642                 ret = _get_implied_value(expr, undefined, implied);
 643         }
 644         if (*undefined)
 645                 return bogus;
 646         return ret;
 647 }
 648
 649 /* returns 1 if it can get a value literal or else returns 0 */
 650 int get_value(struct expression *expr, sval_t *sval)
 651 {
 652         int undefined = 0;
 653         sval_t ret;
 654
 655         ret = _get_value(expr, &undefined, NOTIMPLIED);
 656         if (undefined)
 657                 return 0;
 658         *sval = ret;
 659         return 1;
 660 }
 661
 662 int get_implied_value(struct expression *expr, sval_t *sval)
 663 {
 664         int undefined = 0;
 665         sval_t ret;
 666
 667         ret =  _get_value(expr, &undefined, IMPLIED);
 668         if (undefined)
 669                 return 0;
 670         *sval = ret;
 671         return 1;
 672 }
 673
 674 int get_implied_min(struct expression *expr, sval_t *sval)
 675 {
 676         int undefined = 0;
 677         sval_t ret;
 678
 679         ret =  _get_value(expr, &undefined, IMPLIED_MIN);
 680         if (undefined)
 681                 return 0;
 682         *sval = ret;
 683         return 1;
 684 }
 685
 686 int get_implied_max(struct expression *expr, sval_t *sval)
 687 {
 688         int undefined = 0;
 689         sval_t ret;
 690
 691         ret =  _get_value(expr, &undefined, IMPLIED_MAX);
 692         if (undefined)
 693                 return 0;
 694         *sval = ret;
 695         return 1;
 696 }
 697
 698 int get_implied_range_list(struct expression *expr, struct range_list **rl)
 699 {
 700         sval_t sval;
 701         struct smatch_state *state;
 702         sval_t min, max;
 703
 704         *rl = NULL;
 705
 706         expr = strip_parens(expr);
 707         if (!expr)
 708                 return 0;
 709
 710         state = get_state_expr(SMATCH_EXTRA, expr);
 711         if (state) {
 712                 *rl = clone_range_list(estate_ranges(state));
 713                 return 1;
 714         }
 715
 716         if (expr->type == EXPR_CALL) {
 717                 if (get_implied_return(expr, rl))
 718                         return 1;
 719                 *rl = db_return_vals(expr);
 720                 if (*rl)
 721                         return 1;
 722                 return 0;
 723         }
 724
 725         if (get_implied_value(expr, &sval)) {
 726                 add_range(rl, sval, sval);
 727                 return 1;
 728         }
 729
 730         if (!get_implied_min(expr, &min))
 731                 return 0;
 732         if (!get_implied_max(expr, &max))
 733                 return 0;
 734
 735         *rl = alloc_range_list(min, max);
 736         return 1;
 737 }
 738
 739 int get_hard_max(struct expression *expr, sval_t *sval)
 740 {
 741         int undefined = 0;
 742         sval_t ret;
 743
 744         ret =  _get_value(expr, &undefined, HARD_MAX);
 745         if (undefined)
 746                 return 0;
 747         *sval = ret;
 748         return 1;
 749 }
 750
 751 int get_fuzzy_min(struct expression *expr, sval_t *sval)
 752 {
 753         int undefined = 0;
 754         sval_t ret;
 755
 756         ret =  _get_value(expr, &undefined, FUZZY_MIN);
 757         if (undefined)
 758                 return 0;
 759         *sval = ret;
 760         return 1;
 761 }
 762
 763 int get_fuzzy_max(struct expression *expr, sval_t *sval)
 764 {
 765         int undefined = 0;
 766         sval_t ret;
 767
 768         ret =  _get_value(expr, &undefined, FUZZY_MAX);
 769         if (undefined)
 770                 return 0;
 771         *sval = ret;
 772         return 1;
 773 }
 774
 775 int get_absolute_min(struct expression *expr, sval_t *sval)
 776 {
 777         int undefined = 0;
 778         struct symbol *type;
 779
 780         type = get_type(expr);
 781         if (!type)
 782                 type = &llong_ctype;  // FIXME: this is wrong but places assume get type can't fail.
 783         *sval =  _get_value(expr, &undefined, ABSOLUTE_MIN);
 784         if (undefined) {
 785                 *sval = sval_type_min(type);
 786                 return 1;
 787         }
 788
 789         if (sval_cmp(*sval, sval_type_min(type)) < 0)
 790                 *sval = sval_type_min(type);
 791         return 1;
 792 }
 793
 794 int get_absolute_max(struct expression *expr, sval_t *sval)
 795 {
 796         int undefined = 0;
 797         struct symbol *type;
 798
 799         type = get_type(expr);
 800         if (!type)
 801                 type = &llong_ctype;
 802         *sval = _get_value(expr, &undefined, ABSOLUTE_MAX);
 803         if (undefined) {
 804                 *sval = sval_type_max(type);
 805                 return 1;
 806         }
 807
 808         if (sval_cmp(sval_type_max(type), *sval) < 0)
 809                 *sval = sval_type_max(type);
 810         return 1;
 811 }
 812
 813 int known_condition_true(struct expression *expr)
 814 {
 815         sval_t tmp;
 816
 817         if (!expr)
 818                 return 0;
 819
 820         if (get_value(expr, &tmp) && tmp.value)
 821                 return 1;
 822
 823         return 0;
 824 }
 825
 826 int known_condition_false(struct expression *expr)
 827 {
 828         if (!expr)
 829                 return 0;
 830
 831         if (is_zero(expr))
 832                 return 1;
 833
 834         if (expr->type == EXPR_CALL) {
 835                 if (sym_name_is("__builtin_constant_p", expr->fn))
 836                         return 1;
 837         }
 838         return 0;
 839 }
 840
 841 int implied_condition_true(struct expression *expr)
 842 {
 843         sval_t tmp;
 844
 845         if (!expr)
 846                 return 0;
 847
 848         if (known_condition_true(expr))
 849                 return 1;
 850         if (get_implied_value(expr, &tmp) && tmp.value)
 851                 return 1;
 852
 853         if (expr->type == EXPR_POSTOP)
 854                 return implied_condition_true(expr->unop);
 855
 856         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
 857                 return implied_not_equal(expr->unop, 1);
 858         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
 859                 return implied_not_equal(expr->unop, -1);
 860
 861         expr = strip_expr(expr);
 862         switch (expr->type) {
 863         case EXPR_COMPARE:
 864                 if (do_comparison(expr) == 1)
 865                         return 1;
 866                 break;
 867         case EXPR_PREOP:
 868                 if (expr->op == '!') {
 869                         if (implied_condition_false(expr->unop))
 870                                 return 1;
 871                         break;
 872                 }
 873                 break;
 874         default:
 875                 if (implied_not_equal(expr, 0) == 1)
 876                         return 1;
 877                 break;
 878         }
 879         return 0;
 880 }
 881
 882 int implied_condition_false(struct expression *expr)
 883 {
 884         struct expression *tmp;
 885         sval_t sval;
 886
 887         if (!expr)
 888                 return 0;
 889
 890         if (known_condition_false(expr))
 891                 return 1;
 892
 893         switch (expr->type) {
 894         case EXPR_COMPARE:
 895                 if (do_comparison(expr) == 2)
 896                         return 1;
 897         case EXPR_PREOP:
 898                 if (expr->op == '!') {
 899                         if (implied_condition_true(expr->unop))
 900                                 return 1;
 901                         break;
 902                 }
 903                 tmp = strip_expr(expr);
 904                 if (tmp != expr)
 905                         return implied_condition_false(tmp);
 906                 break;
 907         default:
 908                 if (get_implied_value(expr, &sval) && sval.value == 0)
 909                         return 1;
 910                 break;
 911         }
 912         return 0;
 913 }