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