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