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