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 "symbol.h"
  11 #include "smatch.h"
  12 #include "smatch_slist.h"
  13 #include "smatch_extra.h"
  14
  15 static struct range_list *_get_rl(struct expression *expr, int implied);
  16 static struct range_list *handle_variable(struct expression *expr, int implied);
  17 static sval_t _get_value(struct expression *expr, int *undefined, int implied);
  18 static sval_t _get_implied_value(struct expression *expr, int *undefined, int implied);
  19
  20 #define BOGUS 12345
  21
  22 static sval_t zero  = {.type = &int_ctype, {.value = 0} };
  23 static sval_t one   = {.type = &int_ctype, {.value = 1} };
  24 static sval_t bogus = {.type = &int_ctype, {.value = BOGUS} };
  25
  26 static struct range_list *rl_zero(void)
  27 {
  28         return alloc_rl(zero, zero);
  29 }
  30
  31 static struct range_list *rl_one(void)
  32 {
  33         return alloc_rl(one, one);
  34 }
  35
  36 enum {
  37         EXACT,
  38         IMPLIED,
  39         IMPLIED_MIN,
  40         IMPLIED_MAX,
  41         FUZZY_MAX,
  42         FUZZY_MIN,
  43         ABSOLUTE_MIN,
  44         ABSOLUTE_MAX,
  45         HARD_MAX,
  46 };
  47
  48 enum {
  49         RL_EXACT,
  50         RL_HARD,
  51         RL_FUZZY,
  52         RL_IMPLIED,
  53         RL_ABSOLUTE
  54 };
  55
  56 static int implied_to_rl_enum(int implied)
  57 {
  58         switch (implied) {
  59         case EXACT:
  60                 return RL_EXACT;
  61         case HARD_MAX:
  62                 return RL_HARD;
  63         case FUZZY_MAX:
  64         case FUZZY_MIN:
  65                 return RL_FUZZY;
  66         case IMPLIED:
  67         case IMPLIED_MIN:
  68         case IMPLIED_MAX:
  69                 return RL_IMPLIED;
  70         case ABSOLUTE_MIN:
  71         case ABSOLUTE_MAX:
  72                 return RL_ABSOLUTE;
  73         }
  74         return 0;
  75 }
  76
  77 static int opposite_implied(int implied)
  78 {
  79         if (implied == IMPLIED_MIN)
  80                 return IMPLIED_MAX;
  81         if (implied == IMPLIED_MAX)
  82                 return IMPLIED_MIN;
  83         if (implied == FUZZY_MIN)
  84                 return FUZZY_MAX;
  85         if (implied == FUZZY_MAX)
  86                 return FUZZY_MIN;
  87         if (implied == ABSOLUTE_MIN)
  88                 return ABSOLUTE_MAX;
  89         if (implied == ABSOLUTE_MAX)
  90                 return ABSOLUTE_MIN;
  91         if (implied == HARD_MAX)  /* we don't have a hard min.  */
  92                 return EXACT;
  93
  94         return implied;
  95 }
  96
  97 static struct range_list *last_stmt_rl(struct statement *stmt, int implied)
  98 {
  99         if (!stmt)
 100                 return NULL;
 101
 102         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
 103         if (stmt->type != STMT_EXPRESSION)
 104                 return NULL;
 105         return _get_rl(stmt->expression, implied);
 106 }
 107
 108 static struct range_list *handle_expression_statement_rl(struct expression *expr, int implied)
 109 {
 110         return last_stmt_rl(get_expression_statement(expr), implied);
 111 }
 112
 113 static int last_stmt_sval(struct statement *stmt, sval_t *sval)
 114 {
 115         struct expression *expr;
 116
 117         if (!stmt)
 118                 return 0;
 119
 120         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
 121         if (stmt->type != STMT_EXPRESSION)
 122                 return 0;
 123         expr = stmt->expression;
 124         if (!get_value(expr, sval))
 125                 return 0;
 126         return 1;
 127 }
 128
 129 static sval_t handle_expression_statement(struct expression *expr, int *undefined, int implied)
 130 {
 131         struct statement *stmt;
 132         sval_t ret;
 133
 134         stmt = get_expression_statement(expr);
 135         if (!last_stmt_sval(stmt, &ret)) {
 136                 *undefined = 1;
 137                 ret = bogus;
 138         }
 139
 140         return ret;
 141 }
 142
 143 static struct range_list *handle_ampersand_rl(int implied)
 144 {
 145         if (implied == EXACT || implied == HARD_MAX)
 146                 return NULL;
 147         return alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
 148 }
 149
 150 static sval_t handle_ampersand(int *undefined, int implied)
 151 {
 152         sval_t ret;
 153
 154         ret.type = &ptr_ctype;
 155         ret.value = BOGUS;
 156
 157         if (implied == IMPLIED_MIN || implied == FUZZY_MIN || implied == ABSOLUTE_MIN)
 158                 return valid_ptr_min_sval;
 159         if (implied == IMPLIED_MAX || implied == FUZZY_MAX || implied == ABSOLUTE_MAX)
 160                 return valid_ptr_max_sval;
 161
 162         *undefined = 1;
 163         return ret;
 164 }
 165
 166 static struct range_list *handle_negate_rl(struct expression *expr, int implied)
 167 {
 168         if (known_condition_true(expr->unop))
 169                 return rl_zero();
 170         if (known_condition_false(expr->unop))
 171                 return rl_one();
 172
 173         if (implied == EXACT)
 174                 return NULL;
 175
 176         if (implied_condition_true(expr->unop))
 177                 return rl_zero();
 178         if (implied_condition_false(expr->unop))
 179                 return rl_one();
 180         return alloc_rl(zero, one);
 181 }
 182
 183 static sval_t handle_negate(struct expression *expr, int *undefined, int implied)
 184 {
 185         sval_t ret;
 186
 187         ret = sval_blank(expr->unop);
 188
 189         if (known_condition_true(expr->unop)) {
 190                 ret.value = 0;
 191                 return ret;
 192         }
 193
 194         if (implied == EXACT) {
 195                 *undefined = 1;
 196                 return bogus;
 197         }
 198
 199         if (implied_condition_true(expr->unop)) {
 200                 ret.value = 0;
 201                 return ret;
 202         }
 203         if (implied_condition_false(expr->unop)) {
 204                 ret.value = 1;
 205                 return ret;
 206         }
 207         if (implied == IMPLIED_MIN || implied == FUZZY_MIN || implied == ABSOLUTE_MIN) {
 208                 ret.value = 0;
 209                 return ret;
 210         }
 211         if (implied == IMPLIED_MAX || implied == FUZZY_MAX || implied == ABSOLUTE_MAX) {
 212                 ret.value = 1;
 213                 return ret;
 214         }
 215         *undefined = 1;
 216         return bogus;
 217 }
 218
 219 static struct range_list *handle_bitwise_negate(struct expression *expr, int implied)
 220 {
 221         struct range_list *rl;
 222         sval_t sval;
 223
 224         rl = _get_rl(expr->unop, implied);
 225         if (!rl_to_sval(rl, &sval))
 226                 return NULL;
 227         sval = sval_preop(sval, '~');
 228         sval_cast(get_type(expr->unop), sval);
 229         return alloc_rl(sval, sval);
 230 }
 231
 232 static struct range_list *handle_minus_preop(struct expression *expr, int implied)
 233 {
 234         struct range_list *rl;
 235         sval_t sval;
 236
 237         rl = _get_rl(expr->unop, implied);
 238         if (!rl_to_sval(rl, &sval))
 239                 return NULL;
 240         sval = sval_preop(sval, '-');
 241         return alloc_rl(sval, sval);
 242 }
 243
 244 static struct range_list *handle_preop_rl(struct expression *expr, int implied)
 245 {
 246         switch (expr->op) {
 247         case '&':
 248                 return handle_ampersand_rl(implied);
 249         case '!':
 250                 return handle_negate_rl(expr, implied);
 251         case '~':
 252                 return handle_bitwise_negate(expr, implied);
 253         case '-':
 254                 return handle_minus_preop(expr, implied);
 255         case '*':
 256                 return handle_variable(expr, implied);
 257         case '(':
 258                 return handle_expression_statement_rl(expr, implied);
 259         default:
 260                 return NULL;
 261         }
 262 }
 263
 264 static sval_t handle_preop(struct expression *expr, int *undefined, int implied)
 265 {
 266         sval_t ret;
 267
 268         switch (expr->op) {
 269         case '&':
 270                 ret = handle_ampersand(undefined, implied);
 271                 break;
 272         case '!':
 273                 ret = handle_negate(expr, undefined, implied);
 274                 break;
 275         case '~':
 276                 ret = _get_value(expr->unop, undefined, implied);
 277                 ret = sval_preop(ret, '~');
 278                 ret = sval_cast(get_type(expr->unop), ret);
 279                 break;
 280         case '-':
 281                 ret = _get_value(expr->unop, undefined, implied);
 282                 ret = sval_preop(ret, '-');
 283                 break;
 284         case '*':
 285                 ret = _get_implied_value(expr, undefined, implied);
 286                 break;
 287         case '(':
 288                 ret = handle_expression_statement(expr, undefined, implied);
 289                 break;
 290         default:
 291                 *undefined = 1;
 292                 ret = sval_blank(expr);
 293         }
 294         ret = sval_cast(get_type(expr), ret);
 295         return ret;
 296 }
 297
 298 static sval_t handle_divide(struct expression *expr, int *undefined, int implied)
 299 {
 300         sval_t left, right;
 301
 302         left = _get_value(expr->left, undefined, implied);
 303         right = _get_value(expr->right, undefined, opposite_implied(implied));
 304
 305         if (right.value == 0) {
 306                 *undefined = 1;
 307                 return bogus;
 308         }
 309
 310         return sval_binop(left, '/', right);
 311 }
 312
 313 static sval_t handle_subtract(struct expression *expr, int *undefined, int implied)
 314 {
 315         struct symbol *type;
 316         sval_t left, right, ret;
 317         int left_undefined = 0;
 318         int right_undefined = 0;
 319         int known_but_negative = 0;
 320         int comparison;
 321
 322         left = _get_value(expr->left, &left_undefined, implied);
 323         right = _get_value(expr->right, &right_undefined, opposite_implied(implied));
 324
 325         if (!left_undefined && !right_undefined) {
 326                 ret = sval_binop(left, '-', right);
 327                 if (sval_is_negative(ret))
 328                         known_but_negative = 1;
 329                 else
 330                         return ret;  /* best case scenario */
 331         }
 332
 333         comparison = get_comparison(expr->left, expr->right);
 334         if (!comparison)
 335                 goto bogus;
 336
 337         type = get_type(expr);
 338
 339         switch (comparison) {
 340         case '>':
 341         case SPECIAL_UNSIGNED_GT:
 342                 switch (implied) {
 343                 case IMPLIED_MIN:
 344                 case FUZZY_MIN:
 345                 case ABSOLUTE_MIN:
 346                         return sval_type_val(type, 1);
 347                 case IMPLIED_MAX:
 348                 case FUZZY_MAX:
 349                 case ABSOLUTE_MAX:
 350                         return _get_value(expr->left, undefined, implied);
 351                 }
 352                 break;
 353         case SPECIAL_GTE:
 354         case SPECIAL_UNSIGNED_GTE:
 355                 switch (implied) {
 356                 case IMPLIED_MIN:
 357                 case FUZZY_MIN:
 358                 case ABSOLUTE_MIN:
 359                         return sval_type_val(type, 0);
 360                 case IMPLIED_MAX:
 361                 case FUZZY_MAX:
 362                 case ABSOLUTE_MAX:
 363                         return _get_value(expr->left, undefined, implied);
 364                 }
 365                 break;
 366         }
 367
 368         if (known_but_negative)
 369                 return ret;
 370
 371 bogus:
 372         *undefined = 1;
 373         return bogus;
 374 }
 375
 376 static struct range_list *handle_mod_rl(struct expression *expr, int implied)
 377 {
 378         struct range_list *rl;
 379         sval_t left, right, sval;
 380
 381         if (implied == EXACT) {
 382                 if (!get_value(expr->right, &right))
 383                         return NULL;
 384                 if (!get_value(expr->left, &left))
 385                         return NULL;
 386                 sval = sval_binop(left, '%', right);
 387                 return alloc_rl(sval, sval);
 388         }
 389         /* if we can't figure out the right side it's probably hopeless */
 390         if (!get_implied_value(expr->right, &right))
 391                 return NULL;
 392
 393         right = sval_cast(get_type(expr), right);
 394         right.value--;
 395
 396         rl = _get_rl(expr->left, implied);
 397         if (rl && rl_max(rl).uvalue < right.uvalue)
 398                 right.uvalue = rl_max(rl).uvalue;
 399
 400         return alloc_rl(zero, right);
 401 }
 402
 403 static sval_t handle_mod(struct expression *expr, int *undefined, int implied)
 404 {
 405         sval_t left, right;
 406
 407         /* if we can't figure out the right side it's probably hopeless */
 408         right = _get_value(expr->right, undefined, implied);
 409         if (*undefined || right.value == 0) {
 410                 *undefined = 1;
 411                 return bogus;
 412         }
 413
 414         switch (implied) {
 415         case EXACT:
 416         case IMPLIED:
 417                 left = _get_value(expr->left, undefined, implied);
 418                 if (!*undefined)
 419                         return sval_binop(left, '%', right);
 420                 return bogus;
 421         case IMPLIED_MIN:
 422         case FUZZY_MIN:
 423         case ABSOLUTE_MIN:
 424                 *undefined = 0;
 425                 return sval_type_val(get_type(expr), 0);
 426         case IMPLIED_MAX:
 427         case FUZZY_MAX:
 428         case ABSOLUTE_MAX:
 429                 *undefined = 0;
 430                 right = sval_cast(get_type(expr), right);
 431                 right.value--;
 432                 return right;
 433         }
 434         return bogus;
 435 }
 436
 437 static struct range_list *handle_bitwise_AND(struct expression *expr, int implied)
 438 {
 439         struct symbol *type;
 440         struct range_list *left_rl, *right_rl;
 441
 442         if (implied == EXACT || implied == HARD_MAX)
 443                 return NULL;
 444         type = get_type(expr);
 445
 446         left_rl = _get_rl(expr->left, implied);
 447         if (left_rl) {
 448                 left_rl = cast_rl(type, left_rl);
 449                 left_rl = alloc_rl(sval_type_val(type, 0), rl_max(left_rl));
 450         } else {
 451                 left_rl = alloc_whole_rl(type);
 452         }
 453
 454         right_rl = _get_rl(expr->right, implied);
 455         if (right_rl) {
 456                 right_rl = cast_rl(type, right_rl);
 457                 right_rl = alloc_rl(sval_type_val(type, 0), rl_max(right_rl));
 458         } else {
 459                 right_rl = alloc_whole_rl(type);
 460         }
 461
 462         return rl_intersection(left_rl, right_rl);
 463 }
 464
 465 static struct range_list *handle_known_binop(struct expression *expr)
 466 {
 467         sval_t left, right;
 468
 469         if (!get_value(expr->left, &left))
 470                 return NULL;
 471         if (!get_value(expr->right, &right))
 472                 return NULL;
 473         left = sval_binop(left, expr->op, right);
 474         return alloc_rl(left, left);
 475 }
 476
 477 static struct range_list *handle_binop_rl(struct expression *expr, int implied)
 478 {
 479         struct symbol *type;
 480         sval_t left, right;
 481         sval_t ret = {.type = &int_ctype, {.value = 123456} };
 482         int local_undef = 0;
 483         int undefined = 0;
 484         struct range_list *rl;
 485
 486         rl = handle_known_binop(expr);
 487         if (rl)
 488                 return rl;
 489         if (implied == EXACT)
 490                 return NULL;
 491
 492         switch (expr->op) {
 493         case '%':
 494                 return handle_mod_rl(expr, implied);
 495         case '&':
 496                 return handle_bitwise_AND(expr, implied);
 497         case SPECIAL_RIGHTSHIFT:
 498                 if (implied == HARD_MAX)
 499                         return NULL;
 500                 left = _get_value(expr->left, &local_undef, implied);
 501                 if (local_undef) {
 502                         if (implied == IMPLIED_MIN || implied == ABSOLUTE_MIN) {
 503                                 ret = sval_blank(expr->left);
 504                                 ret.value = 0;
 505                                 return alloc_rl(ret, ret);
 506                         }
 507                         if (implied != IMPLIED_MAX && implied != ABSOLUTE_MAX)
 508                                 undefined = 1;
 509                         if (!get_absolute_max(expr->left, &left))
 510                                 undefined = 1;
 511                 }
 512                 right = _get_value(expr->right, &undefined, implied);
 513                 if (undefined)
 514                         return NULL;
 515                 ret = sval_binop(left, SPECIAL_RIGHTSHIFT, right);
 516                 return alloc_rl(ret, ret);
 517         case '-':
 518                 ret = handle_subtract(expr, &undefined, implied);
 519                 if (undefined)
 520                         return NULL;
 521                 return alloc_rl(ret, ret);
 522         }
 523
 524         left = _get_value(expr->left, &undefined, implied);
 525         right = _get_value(expr->right, &undefined, implied);
 526
 527         if (undefined)
 528                 return NULL;
 529
 530         type = get_type(expr);
 531         left = sval_cast(type, left);
 532         right = sval_cast(type, right);
 533
 534         switch (implied) {
 535         case IMPLIED_MAX:
 536         case ABSOLUTE_MAX:
 537                 if (sval_binop_overflows(left, expr->op, right)) {
 538                         ret = sval_type_max(get_type(expr));
 539                         return alloc_rl(ret, ret);
 540                 }
 541                 break;
 542         case HARD_MAX:
 543         case FUZZY_MAX:
 544                 if (sval_binop_overflows(left, expr->op, right))
 545                         return NULL;
 546         }
 547
 548         switch (expr->op) {
 549         case '/':
 550                 ret = handle_divide(expr, &undefined, implied);
 551                 if (undefined)
 552                         return NULL;
 553                 return alloc_rl(ret, ret);
 554         case '%':
 555                 if (right.value == 0) {
 556                         return NULL;
 557                 } else {
 558                         ret = sval_binop(left, '%', right);
 559                         return alloc_rl(ret, ret);
 560                 }
 561         default:
 562                 ret = sval_binop(left, expr->op, right);
 563         }
 564         return alloc_rl(ret, ret);
 565 }
 566
 567 static sval_t handle_binop(struct expression *expr, int *undefined, int implied)
 568 {
 569         struct symbol *type;
 570         sval_t left, right;
 571         sval_t ret = {.type = &int_ctype, {.value = 123456} };
 572         int local_undef = 0;
 573
 574         switch (expr->op) {
 575         case '%':
 576                 return handle_mod(expr, undefined, implied);
 577         case '&':
 578                 if (implied == HARD_MAX) {
 579                         *undefined = 1;
 580                         return bogus;
 581                 }
 582                 left = _get_value(expr->left, &local_undef, implied);
 583                 if (local_undef) {
 584                         if (implied == IMPLIED_MIN || implied == ABSOLUTE_MIN) {
 585                                 ret = sval_blank(expr->left);
 586                                 ret.value = 0;
 587                                 return ret;
 588                         }
 589                         if (implied != IMPLIED_MAX && implied != ABSOLUTE_MAX)
 590                                 *undefined = 1;
 591                         if (!get_absolute_max(expr->left, &left))
 592                                 *undefined = 1;
 593                 }
 594                 right = _get_value(expr->right, undefined, implied);
 595                 if (*undefined)
 596                         return bogus;
 597                 return sval_binop(left, '&', right);
 598
 599         case SPECIAL_RIGHTSHIFT:
 600                 if (implied == HARD_MAX) {
 601                         *undefined = 1;
 602                         return bogus;
 603                 }
 604                 left = _get_value(expr->left, &local_undef, implied);
 605                 if (local_undef) {
 606                         if (implied == IMPLIED_MIN || implied == ABSOLUTE_MIN) {
 607                                 ret = sval_blank(expr->left);
 608                                 ret.value = 0;
 609                                 return ret;
 610                         }
 611                         if (implied != IMPLIED_MAX && implied != ABSOLUTE_MAX)
 612                                 *undefined = 1;
 613                         if (!get_absolute_max(expr->left, &left))
 614                                 *undefined = 1;
 615                 }
 616                 right = _get_value(expr->right, undefined, implied);
 617                 if (*undefined)
 618                         return bogus;
 619                 return sval_binop(left, SPECIAL_RIGHTSHIFT, right);
 620         case '-':
 621                 return handle_subtract(expr, undefined, implied);
 622         }
 623
 624         left = _get_value(expr->left, undefined, implied);
 625         right = _get_value(expr->right, undefined, implied);
 626
 627         if (*undefined)
 628                 return bogus;
 629
 630         type = get_type(expr);
 631         left = sval_cast(type, left);
 632         right = sval_cast(type, right);
 633
 634         switch (implied) {
 635         case IMPLIED_MAX:
 636         case ABSOLUTE_MAX:
 637                 if (sval_binop_overflows(left, expr->op, right))
 638                         return sval_type_max(get_type(expr));
 639                 break;
 640         case HARD_MAX:
 641         case FUZZY_MAX:
 642                 if (sval_binop_overflows(left, expr->op, right)) {
 643                         *undefined = 1;
 644                         return bogus;
 645                 }
 646         }
 647
 648         switch (expr->op) {
 649         case '/':
 650                 return handle_divide(expr, undefined, implied);
 651         case '%':
 652                 if (right.value == 0) {
 653                         *undefined = 1;
 654                         return bogus;
 655                 } else {
 656                         return sval_binop(left, '%', right);
 657                 }
 658         default:
 659                 ret = sval_binop(left, expr->op, right);
 660         }
 661         return ret;
 662 }
 663
 664 static int do_comparison(struct expression *expr)
 665 {
 666         struct range_list *left_ranges = NULL;
 667         struct range_list *right_ranges = NULL;
 668         int poss_true, poss_false;
 669         struct symbol *type;
 670
 671         type = get_type(expr);
 672
 673         get_implied_rl(expr->left, &left_ranges);
 674         get_implied_rl(expr->right, &right_ranges);
 675         left_ranges = cast_rl(type, left_ranges);
 676         right_ranges = cast_rl(type, right_ranges);
 677
 678         poss_true = possibly_true_rl(left_ranges, expr->op, right_ranges);
 679         poss_false = possibly_false_rl(left_ranges, expr->op, right_ranges);
 680
 681         free_rl(&left_ranges);
 682         free_rl(&right_ranges);
 683
 684         if (!poss_true && !poss_false)
 685                 return 0;
 686         if (poss_true && !poss_false)
 687                 return 1;
 688         if (!poss_true && poss_false)
 689                 return 2;
 690         return 3;
 691 }
 692
 693 static struct range_list *handle_comparison_rl(struct expression *expr, int implied)
 694 {
 695         sval_t left, right;
 696         int res;
 697
 698         if (get_value(expr->left, &left) && get_value(expr->right, &right)) {
 699                 struct data_range tmp_left, tmp_right;
 700
 701                 tmp_left.min = left;
 702                 tmp_left.max = left;
 703                 tmp_right.min = right;
 704                 tmp_right.max = right;
 705                 if (true_comparison_range(&tmp_left, expr->op, &tmp_right))
 706                         return rl_one();
 707                 return rl_zero();
 708         }
 709
 710         if (implied == EXACT)
 711                 return NULL;
 712
 713         res = do_comparison(expr);
 714         if (res == 1)
 715                 return rl_one();
 716         if (res == 2)
 717                 return rl_zero();
 718
 719         return alloc_rl(zero, one);
 720 }
 721
 722 static sval_t handle_comparison(struct expression *expr, int *undefined, int implied)
 723 {
 724         sval_t left, right;
 725         int res;
 726
 727         if (get_value(expr->left, &left) && get_value(expr->right, &right)) {
 728                 struct data_range tmp_left, tmp_right;
 729
 730                 tmp_left.min = left;
 731                 tmp_left.max = left;
 732                 tmp_right.min = right;
 733                 tmp_right.max = right;
 734                 if (true_comparison_range(&tmp_left, expr->op, &tmp_right))
 735                         return one;
 736                 return zero;
 737         }
 738
 739         if (implied == EXACT) {
 740                 *undefined = 1;
 741                 return bogus;
 742         }
 743
 744         res = do_comparison(expr);
 745         if (res == 1)
 746                 return one;
 747         if (res == 2)
 748                 return zero;
 749
 750         if (implied == IMPLIED_MIN || implied == FUZZY_MIN || implied == ABSOLUTE_MIN)
 751                 return zero;
 752         if (implied == IMPLIED_MAX || implied == FUZZY_MAX || implied == ABSOLUTE_MAX)
 753                 return one;
 754
 755         *undefined = 1;
 756         return bogus;
 757 }
 758
 759 static struct range_list *handle_logical_rl(struct expression *expr, int implied)
 760 {
 761         sval_t left, right;
 762         int left_known = 0;
 763         int right_known = 0;
 764
 765         if (implied == EXACT) {
 766                 if (get_value(expr->left, &left))
 767                         left_known = 1;
 768                 if (get_value(expr->right, &right))
 769                         right_known = 1;
 770         } else {
 771                 if (get_implied_value(expr->left, &left))
 772                         left_known = 1;
 773                 if (get_implied_value(expr->right, &right))
 774                         right_known = 1;
 775         }
 776
 777         switch (expr->op) {
 778         case SPECIAL_LOGICAL_OR:
 779                 if (left_known && left.value)
 780                         return rl_one();
 781                 if (right_known && right.value)
 782                         return rl_one();
 783                 if (left_known && right_known)
 784                         return rl_zero();
 785                 break;
 786         case SPECIAL_LOGICAL_AND:
 787                 if (left_known && right_known) {
 788                         if (left.value && right.value)
 789                                 return rl_one();
 790                         return rl_zero();
 791                 }
 792                 break;
 793         default:
 794                 return NULL;
 795         }
 796
 797         if (implied == EXACT)
 798                 return NULL;
 799
 800         return alloc_rl(zero, one);
 801 }
 802
 803 static sval_t handle_logical(struct expression *expr, int *undefined, int implied)
 804 {
 805         sval_t left, right;
 806         int left_known = 0;
 807         int right_known = 0;
 808
 809         if (implied == EXACT) {
 810                 if (get_value(expr->left, &left))
 811                         left_known = 1;
 812                 if (get_value(expr->right, &right))
 813                         right_known = 1;
 814         } else {
 815                 if (get_implied_value(expr->left, &left))
 816                         left_known = 1;
 817                 if (get_implied_value(expr->right, &right))
 818                         right_known = 1;
 819         }
 820
 821         switch (expr->op) {
 822         case SPECIAL_LOGICAL_OR:
 823                 if (left_known && left.value)
 824                         return one;
 825                 if (right_known && right.value)
 826                         return one;
 827                 if (left_known && right_known)
 828                         return zero;
 829                 break;
 830         case SPECIAL_LOGICAL_AND:
 831                 if (left_known && right_known) {
 832                         if (left.value && right.value)
 833                                 return one;
 834                         return zero;
 835                 }
 836                 break;
 837         default:
 838                 *undefined = 1;
 839                 return bogus;
 840         }
 841
 842         if (implied == IMPLIED_MIN || implied == FUZZY_MIN || implied == ABSOLUTE_MIN)
 843                 return zero;
 844         if (implied == IMPLIED_MAX || implied == FUZZY_MAX || implied == ABSOLUTE_MAX)
 845                 return one;
 846
 847         *undefined = 1;
 848         return bogus;
 849 }
 850
 851 static struct range_list *handle_conditional_rl(struct expression *expr, int implied)
 852 {
 853         struct range_list *true_rl, *false_rl;
 854
 855         if (known_condition_true(expr->conditional))
 856                 return _get_rl(expr->cond_true, implied);
 857         if (known_condition_false(expr->conditional))
 858                 return _get_rl(expr->cond_false, implied);
 859
 860         if (implied == EXACT)
 861                 return NULL;
 862
 863         if (implied_condition_true(expr->conditional))
 864                 return _get_rl(expr->cond_true, implied);
 865         if (implied_condition_false(expr->conditional))
 866                 return _get_rl(expr->cond_false, implied);
 867
 868         true_rl = _get_rl(expr->cond_true, implied);
 869         if (!true_rl)
 870                 return NULL;
 871         false_rl = _get_rl(expr->cond_false, implied);
 872         if (!false_rl)
 873                 return NULL;
 874
 875         return rl_union(true_rl, false_rl);
 876 }
 877
 878 static sval_t handle_conditional(struct expression *expr, int *undefined, int implied)
 879 {
 880         if (known_condition_true(expr->conditional))
 881                 return _get_value(expr->cond_true, undefined, implied);
 882         if (known_condition_false(expr->conditional))
 883                 return _get_value(expr->cond_false, undefined, implied);
 884
 885         if (implied == EXACT) {
 886                 *undefined = 1;
 887                 return bogus;
 888         }
 889
 890         if (implied_condition_true(expr->conditional))
 891                 return _get_value(expr->cond_true, undefined, implied);
 892         if (implied_condition_false(expr->conditional))
 893                 return _get_value(expr->cond_false, undefined, implied);
 894
 895         *undefined = 1;
 896         return bogus;
 897 }
 898
 899 static int get_local_value(struct expression *expr, sval_t *sval, int implied)
 900 {
 901         switch (implied) {
 902         case EXACT:
 903         case IMPLIED:
 904                 return 0;
 905         case IMPLIED_MIN:
 906         case FUZZY_MIN:
 907         case ABSOLUTE_MIN:
 908                 return get_local_min_helper(expr, sval);
 909         case ABSOLUTE_MAX:
 910         case HARD_MAX:
 911         case IMPLIED_MAX:
 912         case FUZZY_MAX:
 913                 return get_local_max_helper(expr, sval);
 914         }
 915         return 0;
 916 }
 917
 918 static int get_implied_value_helper(struct expression *expr, sval_t *sval, int implied)
 919 {
 920         struct smatch_state *state;
 921         struct symbol *sym;
 922         char *name;
 923
 924         /* fixme: this should return the casted value */
 925
 926         expr = strip_expr(expr);
 927
 928         if (get_value(expr, sval))
 929                 return 1;
 930
 931         name = expr_to_var_sym(expr, &sym);
 932         if (!name)
 933                 return 0;
 934         *sval = sval_blank(expr);
 935         state = get_state(SMATCH_EXTRA, name, sym);
 936         free_string(name);
 937         if (!state || !state->data)
 938                 return get_local_value(expr, sval, implied);
 939         if (implied == IMPLIED) {
 940                 if (estate_get_single_value(state, sval))
 941                         return 1;
 942                 return 0;
 943         }
 944         if (implied == HARD_MAX) {
 945                 if (estate_get_hard_max(state, sval))
 946                         return 1;
 947                 return 0;
 948         }
 949         if (implied == IMPLIED_MAX || implied == ABSOLUTE_MAX) {
 950                 *sval = estate_max(state);
 951                 return 1;
 952         }
 953         *sval = estate_min(state);
 954         return 1;
 955 }
 956
 957 static int get_fuzzy_max_helper(struct expression *expr, sval_t *max)
 958 {
 959         struct sm_state *sm;
 960         struct sm_state *tmp;
 961         sval_t sval;
 962
 963         if (get_hard_max(expr, &sval)) {
 964                 *max = sval;
 965                 return 1;
 966         }
 967
 968         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 969         if (!sm)
 970                 return 0;
 971
 972         sval = sval_type_min(estate_type(sm->state));
 973         FOR_EACH_PTR(sm->possible, tmp) {
 974                 sval_t new_min;
 975
 976                 new_min = estate_min(tmp->state);
 977                 if (sval_cmp(new_min, sval) > 0)
 978                         sval = new_min;
 979         } END_FOR_EACH_PTR(tmp);
 980
 981         if (sval_is_min(sval))
 982                 return 0;
 983         if (sval.value == sval_type_min(sval.type).value + 1)  /* it's common to be on off */
 984                 return 0;
 985
 986         *max = sval_cast(get_type(expr), sval);
 987         return 1;
 988 }
 989
 990 static int get_fuzzy_min_helper(struct expression *expr, sval_t *min)
 991 {
 992         struct sm_state *sm;
 993         struct sm_state *tmp;
 994         sval_t sval;
 995
 996         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 997         if (!sm)
 998                 return 0;
 999
1000         if (!sval_is_min(estate_min(sm->state))) {
1001                 *min = estate_min(sm->state);
1002                 return 1;
1003         }
1004
1005         sval = sval_type_max(estate_type(sm->state));
1006         FOR_EACH_PTR(sm->possible, tmp) {
1007                 sval_t new_max;
1008
1009                 new_max = estate_max(tmp->state);
1010                 if (sval_cmp(new_max, sval) < 0)
1011                         sval = new_max;
1012         } END_FOR_EACH_PTR(tmp);
1013
1014         if (sval_is_max(sval))
1015                 return 0;
1016         *min = sval_cast(get_type(expr), sval);
1017         return 1;
1018 }
1019
1020 static int get_const_value(struct expression *expr, sval_t *sval)
1021 {
1022         struct symbol *sym;
1023         sval_t right;
1024
1025         if (expr->type != EXPR_SYMBOL || !expr->symbol)
1026                 return 0;
1027         sym = expr->symbol;
1028         if (!(sym->ctype.modifiers & MOD_CONST))
1029                 return 0;
1030         if (get_value(sym->initializer, &right)) {
1031                 *sval = sval_cast(get_type(expr), right);
1032                 return 1;
1033         }
1034         return 0;
1035 }
1036
1037 static struct range_list *handle_variable(struct expression *expr, int implied)
1038 {
1039         struct smatch_state *state;
1040         struct range_list *rl;
1041         sval_t sval, min, max;
1042
1043         if (get_const_value(expr, &sval))
1044                 return alloc_rl(sval, sval);
1045
1046         switch (implied_to_rl_enum(implied)) {
1047         case RL_EXACT:
1048                 return NULL;
1049         case RL_HARD:
1050         case RL_IMPLIED:
1051         case RL_ABSOLUTE:
1052                 state = get_state_expr(SMATCH_EXTRA, expr);
1053                 if (!state || !state->data) {
1054                         if (get_local_rl(expr, &rl))
1055                                 return rl;
1056                         return NULL;
1057                 }
1058                 if (implied == HARD_MAX && !estate_has_hard_max(state))
1059                         return NULL;
1060                 return estate_rl(state);
1061         case RL_FUZZY:
1062                 if (!get_fuzzy_min_helper(expr, &min))
1063                         min = sval_type_min(get_type(expr));
1064                 if (!get_fuzzy_max_helper(expr, &max))
1065                         return NULL;
1066                 return alloc_rl(min, max);
1067         }
1068         return NULL;
1069 }
1070
1071 static sval_t _get_implied_value(struct expression *expr, int *undefined, int implied)
1072 {
1073         sval_t ret;
1074
1075         ret = sval_blank(expr);
1076
1077         switch (implied) {
1078         case IMPLIED:
1079         case IMPLIED_MAX:
1080         case IMPLIED_MIN:
1081         case HARD_MAX:
1082         case ABSOLUTE_MIN:
1083         case ABSOLUTE_MAX:
1084                 if (!get_implied_value_helper(expr, &ret, implied))
1085                         *undefined = 1;
1086                 break;
1087         case FUZZY_MAX:
1088                 if (!get_fuzzy_max_helper(expr, &ret))
1089                         *undefined = 1;
1090                 break;
1091         case FUZZY_MIN:
1092                 if (!get_fuzzy_min_helper(expr, &ret))
1093                         *undefined = 1;
1094                 break;
1095         default:
1096                 *undefined = 1;
1097         }
1098         return ret;
1099 }
1100
1101 static sval_t handle_sizeof(struct expression *expr)
1102 {
1103         struct symbol *sym;
1104         sval_t ret;
1105
1106         ret = sval_blank(expr);
1107         sym = expr->cast_type;
1108         if (!sym) {
1109                 sym = evaluate_expression(expr->cast_expression);
1110                 /*
1111                  * Expressions of restricted types will possibly get
1112                  * promoted - check that here
1113                  */
1114                 if (is_restricted_type(sym)) {
1115                         if (sym->bit_size < bits_in_int)
1116                                 sym = &int_ctype;
1117                 } else if (is_fouled_type(sym)) {
1118                         sym = &int_ctype;
1119                 }
1120         }
1121         examine_symbol_type(sym);
1122
1123         ret.type = size_t_ctype;
1124         if (sym->bit_size <= 0) /* sizeof(void) */ {
1125                 if (get_real_base_type(sym) == &void_ctype)
1126                         ret.value = 1;
1127                 else
1128                         ret.value = 0;
1129         } else
1130                 ret.value = bits_to_bytes(sym->bit_size);
1131
1132         return ret;
1133 }
1134
1135 static struct range_list *handle_call_rl(struct expression *expr, int implied)
1136 {
1137         struct range_list *rl;
1138
1139         if (implied == EXACT)
1140                 return NULL;
1141
1142         if (get_implied_return(expr, &rl))
1143                 return rl;
1144         return db_return_vals(expr);
1145 }
1146
1147 static sval_t handle_call(struct expression *expr, int *undefined, int implied)
1148 {
1149         struct range_list *rl;
1150
1151         if (!get_implied_rl(expr, &rl)) {
1152                 *undefined = 1;
1153                 return bogus;
1154         }
1155
1156         switch (implied) {
1157         case IMPLIED:
1158                 if (sval_cmp(rl_min(rl), rl_max(rl)) == 0)
1159                         return rl_min(rl);
1160                 *undefined = 1;
1161                 return bogus;
1162         case IMPLIED_MIN:
1163         case ABSOLUTE_MIN:
1164                 return rl_min(rl);
1165
1166         case IMPLIED_MAX:
1167         case HARD_MAX:
1168         case ABSOLUTE_MAX:
1169                 return rl_max(rl);
1170         default:
1171                 *undefined = 1;
1172                 return bogus;
1173         }
1174
1175 }
1176
1177 static struct range_list *_get_rl(struct expression *expr, int implied)
1178 {
1179         struct range_list *rl;
1180         struct symbol *type;
1181         int undefined;
1182         sval_t sval;
1183
1184         expr = strip_parens(expr);
1185         if (!expr)
1186                 return NULL;
1187         type = get_type(expr);
1188
1189         undefined = 0;
1190         switch (expr->type) {
1191         case EXPR_VALUE:
1192                 sval = sval_from_val(expr, expr->value);
1193                 break;
1194         case EXPR_PREOP:
1195                 rl = handle_preop_rl(expr, implied);
1196                 if (rl)
1197                         return rl;
1198                 undefined = 1;
1199                 break;
1200         case EXPR_POSTOP:
1201                 return _get_rl(expr->unop, implied);
1202         case EXPR_CAST:
1203         case EXPR_FORCE_CAST:
1204         case EXPR_IMPLIED_CAST:
1205                 rl = _get_rl(expr->cast_expression, implied);
1206                 if (!rl)
1207                         undefined = 1;
1208                 else
1209                         return cast_rl(type, rl);
1210                 break;
1211         case EXPR_BINOP:
1212                 rl = handle_binop_rl(expr, implied);
1213                 if (rl)
1214                         return rl;
1215                 undefined = 1;
1216                 break;
1217         case EXPR_COMPARE:
1218                 rl = handle_comparison_rl(expr, implied);
1219                 if (rl)
1220                         return rl;
1221                 undefined = 1;
1222                 break;
1223         case EXPR_LOGICAL:
1224                 rl = handle_logical_rl(expr, implied);
1225                 if (rl)
1226                         return rl;
1227                 undefined = 1;
1228                 break;
1229         case EXPR_PTRSIZEOF:
1230         case EXPR_SIZEOF:
1231                 sval = handle_sizeof(expr);
1232                 break;
1233         case EXPR_SELECT:
1234         case EXPR_CONDITIONAL:
1235                 rl = handle_conditional_rl(expr, implied);
1236                 if (rl)
1237                         return rl;
1238                 undefined = 1;
1239                 break;
1240         case EXPR_CALL:
1241                 rl = handle_call_rl(expr, implied);
1242                 if (rl)
1243                         return rl;
1244                 else
1245                         undefined = 1;
1246                 break;
1247         default:
1248                 rl = handle_variable(expr, implied);
1249                 if (rl)
1250                         return rl;
1251                 else
1252                         undefined = 1;
1253         }
1254
1255         if (undefined && type &&
1256             (implied == ABSOLUTE_MAX || implied == ABSOLUTE_MIN))
1257                 return alloc_whole_rl(type);
1258         if (undefined)
1259                 return NULL;
1260         rl = alloc_rl(sval, sval);
1261         return rl;
1262 }
1263
1264 static sval_t _get_value(struct expression *expr, int *undefined, int implied)
1265 {
1266         struct symbol *type;
1267         sval_t ret;
1268
1269         if (!expr) {
1270                 *undefined = 1;
1271                 return bogus;
1272         }
1273         if (*undefined)
1274                 return bogus;
1275
1276         expr = strip_parens(expr);
1277         type = get_type(expr);
1278
1279         switch (expr->type) {
1280         case EXPR_VALUE:
1281                 ret = sval_from_val(expr, expr->value);
1282                 break;
1283         case EXPR_PREOP:
1284                 ret = handle_preop(expr, undefined, implied);
1285                 break;
1286         case EXPR_POSTOP:
1287                 ret = _get_value(expr->unop, undefined, implied);
1288                 break;
1289         case EXPR_CAST:
1290         case EXPR_FORCE_CAST:
1291         case EXPR_IMPLIED_CAST:
1292                 ret = _get_value(expr->cast_expression, undefined, implied);
1293                 ret = sval_cast(type, ret);
1294                 break;
1295         case EXPR_BINOP:
1296                 ret = handle_binop(expr, undefined, implied);
1297                 break;
1298         case EXPR_COMPARE:
1299                 ret = handle_comparison(expr, undefined, implied);
1300                 break;
1301         case EXPR_LOGICAL:
1302                 ret = handle_logical(expr, undefined, implied);
1303                 break;
1304         case EXPR_PTRSIZEOF:
1305         case EXPR_SIZEOF:
1306                 ret = handle_sizeof(expr);
1307                 break;
1308         case EXPR_SYMBOL:
1309                 if (get_const_value(expr, &ret)) {
1310                         break;
1311                 }
1312                 ret = _get_implied_value(expr, undefined, implied);
1313                 break;
1314         case EXPR_SELECT:
1315         case EXPR_CONDITIONAL:
1316                 ret = handle_conditional(expr, undefined, implied);
1317                 break;
1318         case EXPR_CALL:
1319                 ret = handle_call(expr, undefined, implied);
1320                 break;
1321         default:
1322                 ret = _get_implied_value(expr, undefined, implied);
1323         }
1324
1325         if (*undefined)
1326                 return bogus;
1327         return ret;
1328 }
1329
1330 /* returns 1 if it can get a value literal or else returns 0 */
1331 int get_value(struct expression *expr, sval_t *sval)
1332 {
1333         struct range_list *rl;
1334
1335         rl = _get_rl(expr, EXACT);
1336         if (!rl_to_sval(rl, sval))
1337                 return 0;
1338         return 1;
1339 }
1340
1341 int get_implied_value(struct expression *expr, sval_t *sval)
1342 {
1343         struct range_list *rl;
1344
1345         rl =  _get_rl(expr, IMPLIED);
1346         if (!rl_to_sval(rl, sval))
1347                 return 0;
1348         return 1;
1349 }
1350
1351 int get_implied_min(struct expression *expr, sval_t *sval)
1352 {
1353         struct range_list *rl;
1354
1355         rl =  _get_rl(expr, IMPLIED_MIN);
1356         if (!rl)
1357                 return 0;
1358         *sval = rl_min(rl);
1359         return 1;
1360 }
1361
1362 int get_implied_max(struct expression *expr, sval_t *sval)
1363 {
1364         struct range_list *rl;
1365
1366         rl =  _get_rl(expr, IMPLIED_MAX);
1367         if (!rl)
1368                 return 0;
1369         *sval = rl_max(rl);
1370         return 1;
1371 }
1372
1373 int get_implied_rl(struct expression *expr, struct range_list **rl)
1374 {
1375         sval_t sval;
1376         struct smatch_state *state;
1377         sval_t min, max;
1378         int min_known = 0;
1379         int max_known = 0;
1380
1381         *rl = NULL;
1382
1383         expr = strip_parens(expr);
1384         if (!expr)
1385                 return 0;
1386
1387         state = get_state_expr(SMATCH_EXTRA, expr);
1388         if (state) {
1389                 *rl = clone_rl(estate_rl(state));
1390                 return 1;
1391         }
1392
1393         if (expr->type == EXPR_CALL) {
1394                 if (get_implied_return(expr, rl))
1395                         return 1;
1396                 *rl = db_return_vals(expr);
1397                 if (*rl)
1398                         return 1;
1399                 return 0;
1400         }
1401
1402         if (get_implied_value(expr, &sval)) {
1403                 add_range(rl, sval, sval);
1404                 return 1;
1405         }
1406
1407         if (get_local_rl(expr, rl))
1408                 return 1;
1409
1410         min_known = get_implied_min(expr, &min);
1411         max_known = get_implied_max(expr, &max);
1412         if (!min_known && !max_known)
1413                 return 0;
1414         if (!min_known)
1415                 get_absolute_min(expr, &min);
1416         if (!max_known)
1417                 get_absolute_max(expr, &max);
1418
1419         *rl = alloc_rl(min, max);
1420         return 1;
1421 }
1422
1423 int get_hard_max(struct expression *expr, sval_t *sval)
1424 {
1425         struct range_list *rl;
1426
1427         rl =  _get_rl(expr, HARD_MAX);
1428         if (!rl)
1429                 return 0;
1430         *sval = rl_max(rl);
1431         return 1;
1432 }
1433
1434 int get_fuzzy_min(struct expression *expr, sval_t *sval)
1435 {
1436         struct range_list *rl;
1437
1438         rl =  _get_rl(expr, FUZZY_MIN);
1439         if (!rl)
1440                 return 0;
1441         *sval = rl_min(rl);
1442         return 1;
1443 }
1444
1445 int get_fuzzy_max(struct expression *expr, sval_t *sval)
1446 {
1447         struct range_list *rl;
1448         sval_t max;
1449
1450         rl =  _get_rl(expr, FUZZY_MAX);
1451         if (!rl)
1452                 return 0;
1453         max = rl_max(rl);
1454         if (max.uvalue > INT_MAX - 10000)
1455                 return 0;
1456         *sval = max;
1457         return 1;
1458 }
1459
1460 int get_absolute_min(struct expression *expr, sval_t *sval)
1461 {
1462         struct range_list *rl;
1463         struct symbol *type;
1464
1465         type = get_type(expr);
1466         if (!type)
1467                 type = &llong_ctype;  // FIXME: this is wrong but places assume get type can't fail.
1468         rl = _get_rl(expr, ABSOLUTE_MIN);
1469         if (rl)
1470                 *sval = rl_min(rl);
1471         else
1472                 *sval = sval_type_min(type);
1473
1474         if (sval_cmp(*sval, sval_type_min(type)) < 0)
1475                 *sval = sval_type_min(type);
1476         return 1;
1477 }
1478
1479 int get_absolute_max(struct expression *expr, sval_t *sval)
1480 {
1481         struct range_list *rl;
1482         struct symbol *type;
1483
1484         type = get_type(expr);
1485         if (!type)
1486                 type = &llong_ctype;
1487         rl = _get_rl(expr, ABSOLUTE_MAX);
1488         if (rl)
1489                 *sval = rl_max(rl);
1490         else
1491                 *sval = sval_type_max(type);
1492
1493         if (sval_cmp(sval_type_max(type), *sval) < 0)
1494                 *sval = sval_type_max(type);
1495         return 1;
1496 }
1497
1498 int known_condition_true(struct expression *expr)
1499 {
1500         sval_t tmp;
1501
1502         if (!expr)
1503                 return 0;
1504
1505         if (get_value(expr, &tmp) && tmp.value)
1506                 return 1;
1507
1508         return 0;
1509 }
1510
1511 int known_condition_false(struct expression *expr)
1512 {
1513         if (!expr)
1514                 return 0;
1515
1516         if (is_zero(expr))
1517                 return 1;
1518
1519         if (expr->type == EXPR_CALL) {
1520                 if (sym_name_is("__builtin_constant_p", expr->fn))
1521                         return 1;
1522         }
1523         return 0;
1524 }
1525
1526 int implied_condition_true(struct expression *expr)
1527 {
1528         sval_t tmp;
1529
1530         if (!expr)
1531                 return 0;
1532
1533         if (known_condition_true(expr))
1534                 return 1;
1535         if (get_implied_value(expr, &tmp) && tmp.value)
1536                 return 1;
1537
1538         if (expr->type == EXPR_POSTOP)
1539                 return implied_condition_true(expr->unop);
1540
1541         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
1542                 return implied_not_equal(expr->unop, 1);
1543         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
1544                 return implied_not_equal(expr->unop, -1);
1545
1546         expr = strip_expr(expr);
1547         switch (expr->type) {
1548         case EXPR_COMPARE:
1549                 if (do_comparison(expr) == 1)
1550                         return 1;
1551                 break;
1552         case EXPR_PREOP:
1553                 if (expr->op == '!') {
1554                         if (implied_condition_false(expr->unop))
1555                                 return 1;
1556                         break;
1557                 }
1558                 break;
1559         default:
1560                 if (implied_not_equal(expr, 0) == 1)
1561                         return 1;
1562                 break;
1563         }
1564         return 0;
1565 }
1566
1567 int implied_condition_false(struct expression *expr)
1568 {
1569         struct expression *tmp;
1570         sval_t sval;
1571
1572         if (!expr)
1573                 return 0;
1574
1575         if (known_condition_false(expr))
1576                 return 1;
1577
1578         switch (expr->type) {
1579         case EXPR_COMPARE:
1580                 if (do_comparison(expr) == 2)
1581                         return 1;
1582         case EXPR_PREOP:
1583                 if (expr->op == '!') {
1584                         if (implied_condition_true(expr->unop))
1585                                 return 1;
1586                         break;
1587                 }
1588                 tmp = strip_expr(expr);
1589                 if (tmp != expr)
1590                         return implied_condition_false(tmp);
1591                 break;
1592         default:
1593                 if (get_implied_value(expr, &sval) && sval.value == 0)
1594                         return 1;
1595                 break;
1596         }
1597         return 0;
1598 }