smatch_math.c

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