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_right_shift(struct expression *expr, int implied)
 466 {
 467         struct range_list *left_rl;
 468         sval_t right;
 469         sval_t min, max;
 470
 471         if (implied == HARD_MAX)
 472                 return NULL;
 473         /* this is hopeless without the right side */
 474         if (!get_implied_value(expr->right, &right))
 475                 return NULL;
 476         left_rl = _get_rl(expr->left, implied);
 477         if (left_rl) {
 478                 max = rl_max(left_rl);
 479                 min = rl_min(left_rl);
 480         } else {
 481                 if (implied_to_rl_enum(implied) == RL_FUZZY)
 482                         return NULL;
 483                 if (implied_to_rl_enum(implied) == RL_HARD)
 484                         return NULL;
 485                 max = sval_type_max(get_type(expr->left));
 486                 min = sval_type_val(get_type(expr->left), 0);
 487         }
 488
 489         max = sval_binop(max, SPECIAL_RIGHTSHIFT, right);
 490         min = sval_binop(min, SPECIAL_RIGHTSHIFT, right);
 491         return alloc_rl(min, max);
 492 }
 493
 494 static struct range_list *handle_known_binop(struct expression *expr)
 495 {
 496         sval_t left, right;
 497
 498         if (!get_value(expr->left, &left))
 499                 return NULL;
 500         if (!get_value(expr->right, &right))
 501                 return NULL;
 502         left = sval_binop(left, expr->op, right);
 503         return alloc_rl(left, left);
 504 }
 505
 506 static struct range_list *handle_binop_rl(struct expression *expr, int implied)
 507 {
 508         struct symbol *type;
 509         sval_t left, right;
 510         sval_t ret = {.type = &int_ctype, {.value = 123456} };
 511         int undefined = 0;
 512         struct range_list *rl;
 513
 514         rl = handle_known_binop(expr);
 515         if (rl)
 516                 return rl;
 517         if (implied == EXACT)
 518                 return NULL;
 519
 520         switch (expr->op) {
 521         case '%':
 522                 return handle_mod_rl(expr, implied);
 523         case '&':
 524                 return handle_bitwise_AND(expr, implied);
 525         case SPECIAL_RIGHTSHIFT:
 526                 return handle_right_shift(expr, implied);
 527         case '-':
 528                 ret = handle_subtract(expr, &undefined, implied);
 529                 if (undefined)
 530                         return NULL;
 531                 return alloc_rl(ret, ret);
 532         }
 533
 534         left = _get_value(expr->left, &undefined, implied);
 535         right = _get_value(expr->right, &undefined, implied);
 536
 537         if (undefined)
 538                 return NULL;
 539
 540         type = get_type(expr);
 541         left = sval_cast(type, left);
 542         right = sval_cast(type, right);
 543
 544         switch (implied) {
 545         case IMPLIED_MAX:
 546         case ABSOLUTE_MAX:
 547                 if (sval_binop_overflows(left, expr->op, right)) {
 548                         ret = sval_type_max(get_type(expr));
 549                         return alloc_rl(ret, ret);
 550                 }
 551                 break;
 552         case HARD_MAX:
 553         case FUZZY_MAX:
 554                 if (sval_binop_overflows(left, expr->op, right))
 555                         return NULL;
 556         }
 557
 558         switch (expr->op) {
 559         case '/':
 560                 ret = handle_divide(expr, &undefined, implied);
 561                 if (undefined)
 562                         return NULL;
 563                 return alloc_rl(ret, ret);
 564         case '%':
 565                 if (right.value == 0) {
 566                         return NULL;
 567                 } else {
 568                         ret = sval_binop(left, '%', right);
 569                         return alloc_rl(ret, ret);
 570                 }
 571         default:
 572                 ret = sval_binop(left, expr->op, right);
 573         }
 574         return alloc_rl(ret, ret);
 575 }
 576
 577 static sval_t handle_binop(struct expression *expr, int *undefined, int implied)
 578 {
 579         struct symbol *type;
 580         sval_t left, right;
 581         sval_t ret = {.type = &int_ctype, {.value = 123456} };
 582         int local_undef = 0;
 583
 584         switch (expr->op) {
 585         case '%':
 586                 return handle_mod(expr, undefined, implied);
 587         case '&':
 588                 if (implied == HARD_MAX) {
 589                         *undefined = 1;
 590                         return bogus;
 591                 }
 592                 left = _get_value(expr->left, &local_undef, implied);
 593                 if (local_undef) {
 594                         if (implied == IMPLIED_MIN || implied == ABSOLUTE_MIN) {
 595                                 ret = sval_blank(expr->left);
 596                                 ret.value = 0;
 597                                 return ret;
 598                         }
 599                         if (implied != IMPLIED_MAX && implied != ABSOLUTE_MAX)
 600                                 *undefined = 1;
 601                         if (!get_absolute_max(expr->left, &left))
 602                                 *undefined = 1;
 603                 }
 604                 right = _get_value(expr->right, undefined, implied);
 605                 if (*undefined)
 606                         return bogus;
 607                 return sval_binop(left, '&', right);
 608
 609         case SPECIAL_RIGHTSHIFT:
 610                 if (implied == HARD_MAX) {
 611                         *undefined = 1;
 612                         return bogus;
 613                 }
 614                 left = _get_value(expr->left, &local_undef, implied);
 615                 if (local_undef) {
 616                         if (implied == IMPLIED_MIN || implied == ABSOLUTE_MIN) {
 617                                 ret = sval_blank(expr->left);
 618                                 ret.value = 0;
 619                                 return ret;
 620                         }
 621                         if (implied != IMPLIED_MAX && implied != ABSOLUTE_MAX)
 622                                 *undefined = 1;
 623                         if (!get_absolute_max(expr->left, &left))
 624                                 *undefined = 1;
 625                 }
 626                 right = _get_value(expr->right, undefined, implied);
 627                 if (*undefined)
 628                         return bogus;
 629                 return sval_binop(left, SPECIAL_RIGHTSHIFT, right);
 630         case '-':
 631                 return handle_subtract(expr, undefined, implied);
 632         }
 633
 634         left = _get_value(expr->left, undefined, implied);
 635         right = _get_value(expr->right, undefined, implied);
 636
 637         if (*undefined)
 638                 return bogus;
 639
 640         type = get_type(expr);
 641         left = sval_cast(type, left);
 642         right = sval_cast(type, right);
 643
 644         switch (implied) {
 645         case IMPLIED_MAX:
 646         case ABSOLUTE_MAX:
 647                 if (sval_binop_overflows(left, expr->op, right))
 648                         return sval_type_max(get_type(expr));
 649                 break;
 650         case HARD_MAX:
 651         case FUZZY_MAX:
 652                 if (sval_binop_overflows(left, expr->op, right)) {
 653                         *undefined = 1;
 654                         return bogus;
 655                 }
 656         }
 657
 658         switch (expr->op) {
 659         case '/':
 660                 return handle_divide(expr, undefined, implied);
 661         case '%':
 662                 if (right.value == 0) {
 663                         *undefined = 1;
 664                         return bogus;
 665                 } else {
 666                         return sval_binop(left, '%', right);
 667                 }
 668         default:
 669                 ret = sval_binop(left, expr->op, right);
 670         }
 671         return ret;
 672 }
 673
 674 static int do_comparison(struct expression *expr)
 675 {
 676         struct range_list *left_ranges = NULL;
 677         struct range_list *right_ranges = NULL;
 678         int poss_true, poss_false;
 679         struct symbol *type;
 680
 681         type = get_type(expr);
 682
 683         get_implied_rl(expr->left, &left_ranges);
 684         get_implied_rl(expr->right, &right_ranges);
 685         left_ranges = cast_rl(type, left_ranges);
 686         right_ranges = cast_rl(type, right_ranges);
 687
 688         poss_true = possibly_true_rl(left_ranges, expr->op, right_ranges);
 689         poss_false = possibly_false_rl(left_ranges, expr->op, right_ranges);
 690
 691         free_rl(&left_ranges);
 692         free_rl(&right_ranges);
 693
 694         if (!poss_true && !poss_false)
 695                 return 0;
 696         if (poss_true && !poss_false)
 697                 return 1;
 698         if (!poss_true && poss_false)
 699                 return 2;
 700         return 3;
 701 }
 702
 703 static struct range_list *handle_comparison_rl(struct expression *expr, int implied)
 704 {
 705         sval_t left, right;
 706         int res;
 707
 708         if (get_value(expr->left, &left) && get_value(expr->right, &right)) {
 709                 struct data_range tmp_left, tmp_right;
 710
 711                 tmp_left.min = left;
 712                 tmp_left.max = left;
 713                 tmp_right.min = right;
 714                 tmp_right.max = right;
 715                 if (true_comparison_range(&tmp_left, expr->op, &tmp_right))
 716                         return rl_one();
 717                 return rl_zero();
 718         }
 719
 720         if (implied == EXACT)
 721                 return NULL;
 722
 723         res = do_comparison(expr);
 724         if (res == 1)
 725                 return rl_one();
 726         if (res == 2)
 727                 return rl_zero();
 728
 729         return alloc_rl(zero, one);
 730 }
 731
 732 static sval_t handle_comparison(struct expression *expr, int *undefined, int implied)
 733 {
 734         sval_t left, right;
 735         int res;
 736
 737         if (get_value(expr->left, &left) && get_value(expr->right, &right)) {
 738                 struct data_range tmp_left, tmp_right;
 739
 740                 tmp_left.min = left;
 741                 tmp_left.max = left;
 742                 tmp_right.min = right;
 743                 tmp_right.max = right;
 744                 if (true_comparison_range(&tmp_left, expr->op, &tmp_right))
 745                         return one;
 746                 return zero;
 747         }
 748
 749         if (implied == EXACT) {
 750                 *undefined = 1;
 751                 return bogus;
 752         }
 753
 754         res = do_comparison(expr);
 755         if (res == 1)
 756                 return one;
 757         if (res == 2)
 758                 return zero;
 759
 760         if (implied == IMPLIED_MIN || implied == FUZZY_MIN || implied == ABSOLUTE_MIN)
 761                 return zero;
 762         if (implied == IMPLIED_MAX || implied == FUZZY_MAX || implied == ABSOLUTE_MAX)
 763                 return one;
 764
 765         *undefined = 1;
 766         return bogus;
 767 }
 768
 769 static struct range_list *handle_logical_rl(struct expression *expr, int implied)
 770 {
 771         sval_t left, right;
 772         int left_known = 0;
 773         int right_known = 0;
 774
 775         if (implied == EXACT) {
 776                 if (get_value(expr->left, &left))
 777                         left_known = 1;
 778                 if (get_value(expr->right, &right))
 779                         right_known = 1;
 780         } else {
 781                 if (get_implied_value(expr->left, &left))
 782                         left_known = 1;
 783                 if (get_implied_value(expr->right, &right))
 784                         right_known = 1;
 785         }
 786
 787         switch (expr->op) {
 788         case SPECIAL_LOGICAL_OR:
 789                 if (left_known && left.value)
 790                         return rl_one();
 791                 if (right_known && right.value)
 792                         return rl_one();
 793                 if (left_known && right_known)
 794                         return rl_zero();
 795                 break;
 796         case SPECIAL_LOGICAL_AND:
 797                 if (left_known && right_known) {
 798                         if (left.value && right.value)
 799                                 return rl_one();
 800                         return rl_zero();
 801                 }
 802                 break;
 803         default:
 804                 return NULL;
 805         }
 806
 807         if (implied == EXACT)
 808                 return NULL;
 809
 810         return alloc_rl(zero, one);
 811 }
 812
 813 static sval_t handle_logical(struct expression *expr, int *undefined, int implied)
 814 {
 815         sval_t left, right;
 816         int left_known = 0;
 817         int right_known = 0;
 818
 819         if (implied == EXACT) {
 820                 if (get_value(expr->left, &left))
 821                         left_known = 1;
 822                 if (get_value(expr->right, &right))
 823                         right_known = 1;
 824         } else {
 825                 if (get_implied_value(expr->left, &left))
 826                         left_known = 1;
 827                 if (get_implied_value(expr->right, &right))
 828                         right_known = 1;
 829         }
 830
 831         switch (expr->op) {
 832         case SPECIAL_LOGICAL_OR:
 833                 if (left_known && left.value)
 834                         return one;
 835                 if (right_known && right.value)
 836                         return one;
 837                 if (left_known && right_known)
 838                         return zero;
 839                 break;
 840         case SPECIAL_LOGICAL_AND:
 841                 if (left_known && right_known) {
 842                         if (left.value && right.value)
 843                                 return one;
 844                         return zero;
 845                 }
 846                 break;
 847         default:
 848                 *undefined = 1;
 849                 return bogus;
 850         }
 851
 852         if (implied == IMPLIED_MIN || implied == FUZZY_MIN || implied == ABSOLUTE_MIN)
 853                 return zero;
 854         if (implied == IMPLIED_MAX || implied == FUZZY_MAX || implied == ABSOLUTE_MAX)
 855                 return one;
 856
 857         *undefined = 1;
 858         return bogus;
 859 }
 860
 861 static struct range_list *handle_conditional_rl(struct expression *expr, int implied)
 862 {
 863         struct range_list *true_rl, *false_rl;
 864
 865         if (known_condition_true(expr->conditional))
 866                 return _get_rl(expr->cond_true, implied);
 867         if (known_condition_false(expr->conditional))
 868                 return _get_rl(expr->cond_false, implied);
 869
 870         if (implied == EXACT)
 871                 return NULL;
 872
 873         if (implied_condition_true(expr->conditional))
 874                 return _get_rl(expr->cond_true, implied);
 875         if (implied_condition_false(expr->conditional))
 876                 return _get_rl(expr->cond_false, implied);
 877
 878         true_rl = _get_rl(expr->cond_true, implied);
 879         if (!true_rl)
 880                 return NULL;
 881         false_rl = _get_rl(expr->cond_false, implied);
 882         if (!false_rl)
 883                 return NULL;
 884
 885         return rl_union(true_rl, false_rl);
 886 }
 887
 888 static sval_t handle_conditional(struct expression *expr, int *undefined, int implied)
 889 {
 890         if (known_condition_true(expr->conditional))
 891                 return _get_value(expr->cond_true, undefined, implied);
 892         if (known_condition_false(expr->conditional))
 893                 return _get_value(expr->cond_false, undefined, implied);
 894
 895         if (implied == EXACT) {
 896                 *undefined = 1;
 897                 return bogus;
 898         }
 899
 900         if (implied_condition_true(expr->conditional))
 901                 return _get_value(expr->cond_true, undefined, implied);
 902         if (implied_condition_false(expr->conditional))
 903                 return _get_value(expr->cond_false, undefined, implied);
 904
 905         *undefined = 1;
 906         return bogus;
 907 }
 908
 909 static int get_local_value(struct expression *expr, sval_t *sval, int implied)
 910 {
 911         switch (implied) {
 912         case EXACT:
 913         case IMPLIED:
 914                 return 0;
 915         case IMPLIED_MIN:
 916         case FUZZY_MIN:
 917         case ABSOLUTE_MIN:
 918                 return get_local_min_helper(expr, sval);
 919         case ABSOLUTE_MAX:
 920         case HARD_MAX:
 921         case IMPLIED_MAX:
 922         case FUZZY_MAX:
 923                 return get_local_max_helper(expr, sval);
 924         }
 925         return 0;
 926 }
 927
 928 static int get_implied_value_helper(struct expression *expr, sval_t *sval, int implied)
 929 {
 930         struct smatch_state *state;
 931         struct symbol *sym;
 932         char *name;
 933
 934         /* fixme: this should return the casted value */
 935
 936         expr = strip_expr(expr);
 937
 938         if (get_value(expr, sval))
 939                 return 1;
 940
 941         name = expr_to_var_sym(expr, &sym);
 942         if (!name)
 943                 return 0;
 944         *sval = sval_blank(expr);
 945         state = get_state(SMATCH_EXTRA, name, sym);
 946         free_string(name);
 947         if (!state || !state->data)
 948                 return get_local_value(expr, sval, implied);
 949         if (implied == IMPLIED) {
 950                 if (estate_get_single_value(state, sval))
 951                         return 1;
 952                 return 0;
 953         }
 954         if (implied == HARD_MAX) {
 955                 if (estate_get_hard_max(state, sval))
 956                         return 1;
 957                 return 0;
 958         }
 959         if (implied == IMPLIED_MAX || implied == ABSOLUTE_MAX) {
 960                 *sval = estate_max(state);
 961                 return 1;
 962         }
 963         *sval = estate_min(state);
 964         return 1;
 965 }
 966
 967 static int get_fuzzy_max_helper(struct expression *expr, sval_t *max)
 968 {
 969         struct sm_state *sm;
 970         struct sm_state *tmp;
 971         sval_t sval;
 972
 973         if (get_hard_max(expr, &sval)) {
 974                 *max = sval;
 975                 return 1;
 976         }
 977
 978         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 979         if (!sm)
 980                 return 0;
 981
 982         sval = sval_type_min(estate_type(sm->state));
 983         FOR_EACH_PTR(sm->possible, tmp) {
 984                 sval_t new_min;
 985
 986                 new_min = estate_min(tmp->state);
 987                 if (sval_cmp(new_min, sval) > 0)
 988                         sval = new_min;
 989         } END_FOR_EACH_PTR(tmp);
 990
 991         if (sval_is_min(sval))
 992                 return 0;
 993         if (sval.value == sval_type_min(sval.type).value + 1)  /* it's common to be on off */
 994                 return 0;
 995
 996         *max = sval_cast(get_type(expr), sval);
 997         return 1;
 998 }
 999
1000 static int get_fuzzy_min_helper(struct expression *expr, sval_t *min)
1001 {
1002         struct sm_state *sm;
1003         struct sm_state *tmp;
1004         sval_t sval;
1005
1006         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
1007         if (!sm)
1008                 return 0;
1009
1010         if (!sval_is_min(estate_min(sm->state))) {
1011                 *min = estate_min(sm->state);
1012                 return 1;
1013         }
1014
1015         sval = sval_type_max(estate_type(sm->state));
1016         FOR_EACH_PTR(sm->possible, tmp) {
1017                 sval_t new_max;
1018
1019                 new_max = estate_max(tmp->state);
1020                 if (sval_cmp(new_max, sval) < 0)
1021                         sval = new_max;
1022         } END_FOR_EACH_PTR(tmp);
1023
1024         if (sval_is_max(sval))
1025                 return 0;
1026         *min = sval_cast(get_type(expr), sval);
1027         return 1;
1028 }
1029
1030 static int get_const_value(struct expression *expr, sval_t *sval)
1031 {
1032         struct symbol *sym;
1033         sval_t right;
1034
1035         if (expr->type != EXPR_SYMBOL || !expr->symbol)
1036                 return 0;
1037         sym = expr->symbol;
1038         if (!(sym->ctype.modifiers & MOD_CONST))
1039                 return 0;
1040         if (get_value(sym->initializer, &right)) {
1041                 *sval = sval_cast(get_type(expr), right);
1042                 return 1;
1043         }
1044         return 0;
1045 }
1046
1047 static struct range_list *handle_variable(struct expression *expr, int implied)
1048 {
1049         struct smatch_state *state;
1050         struct range_list *rl;
1051         sval_t sval, min, max;
1052
1053         if (get_const_value(expr, &sval))
1054                 return alloc_rl(sval, sval);
1055
1056         switch (implied_to_rl_enum(implied)) {
1057         case RL_EXACT:
1058                 return NULL;
1059         case RL_HARD:
1060         case RL_IMPLIED:
1061         case RL_ABSOLUTE:
1062                 state = get_state_expr(SMATCH_EXTRA, expr);
1063                 if (!state || !state->data) {
1064                         if (get_local_rl(expr, &rl))
1065                                 return rl;
1066                         return NULL;
1067                 }
1068                 if (implied == HARD_MAX && !estate_has_hard_max(state))
1069                         return NULL;
1070                 return estate_rl(state);
1071         case RL_FUZZY:
1072                 if (!get_fuzzy_min_helper(expr, &min))
1073                         min = sval_type_min(get_type(expr));
1074                 if (!get_fuzzy_max_helper(expr, &max))
1075                         return NULL;
1076                 return alloc_rl(min, max);
1077         }
1078         return NULL;
1079 }
1080
1081 static sval_t _get_implied_value(struct expression *expr, int *undefined, int implied)
1082 {
1083         sval_t ret;
1084
1085         ret = sval_blank(expr);
1086
1087         switch (implied) {
1088         case IMPLIED:
1089         case IMPLIED_MAX:
1090         case IMPLIED_MIN:
1091         case HARD_MAX:
1092         case ABSOLUTE_MIN:
1093         case ABSOLUTE_MAX:
1094                 if (!get_implied_value_helper(expr, &ret, implied))
1095                         *undefined = 1;
1096                 break;
1097         case FUZZY_MAX:
1098                 if (!get_fuzzy_max_helper(expr, &ret))
1099                         *undefined = 1;
1100                 break;
1101         case FUZZY_MIN:
1102                 if (!get_fuzzy_min_helper(expr, &ret))
1103                         *undefined = 1;
1104                 break;
1105         default:
1106                 *undefined = 1;
1107         }
1108         return ret;
1109 }
1110
1111 static sval_t handle_sizeof(struct expression *expr)
1112 {
1113         struct symbol *sym;
1114         sval_t ret;
1115
1116         ret = sval_blank(expr);
1117         sym = expr->cast_type;
1118         if (!sym) {
1119                 sym = evaluate_expression(expr->cast_expression);
1120                 /*
1121                  * Expressions of restricted types will possibly get
1122                  * promoted - check that here
1123                  */
1124                 if (is_restricted_type(sym)) {
1125                         if (sym->bit_size < bits_in_int)
1126                                 sym = &int_ctype;
1127                 } else if (is_fouled_type(sym)) {
1128                         sym = &int_ctype;
1129                 }
1130         }
1131         examine_symbol_type(sym);
1132
1133         ret.type = size_t_ctype;
1134         if (sym->bit_size <= 0) /* sizeof(void) */ {
1135                 if (get_real_base_type(sym) == &void_ctype)
1136                         ret.value = 1;
1137                 else
1138                         ret.value = 0;
1139         } else
1140                 ret.value = bits_to_bytes(sym->bit_size);
1141
1142         return ret;
1143 }
1144
1145 static struct range_list *handle_call_rl(struct expression *expr, int implied)
1146 {
1147         struct range_list *rl;
1148
1149         if (implied == EXACT)
1150                 return NULL;
1151
1152         if (get_implied_return(expr, &rl))
1153                 return rl;
1154         return db_return_vals(expr);
1155 }
1156
1157 static sval_t handle_call(struct expression *expr, int *undefined, int implied)
1158 {
1159         struct range_list *rl;
1160
1161         if (!get_implied_rl(expr, &rl)) {
1162                 *undefined = 1;
1163                 return bogus;
1164         }
1165
1166         switch (implied) {
1167         case IMPLIED:
1168                 if (sval_cmp(rl_min(rl), rl_max(rl)) == 0)
1169                         return rl_min(rl);
1170                 *undefined = 1;
1171                 return bogus;
1172         case IMPLIED_MIN:
1173         case ABSOLUTE_MIN:
1174                 return rl_min(rl);
1175
1176         case IMPLIED_MAX:
1177         case HARD_MAX:
1178         case ABSOLUTE_MAX:
1179                 return rl_max(rl);
1180         default:
1181                 *undefined = 1;
1182                 return bogus;
1183         }
1184
1185 }
1186
1187 static struct range_list *_get_rl(struct expression *expr, int implied)
1188 {
1189         struct range_list *rl;
1190         struct symbol *type;
1191         int undefined;
1192         sval_t sval;
1193
1194         expr = strip_parens(expr);
1195         if (!expr)
1196                 return NULL;
1197         type = get_type(expr);
1198
1199         undefined = 0;
1200         switch (expr->type) {
1201         case EXPR_VALUE:
1202                 sval = sval_from_val(expr, expr->value);
1203                 break;
1204         case EXPR_PREOP:
1205                 rl = handle_preop_rl(expr, implied);
1206                 if (rl)
1207                         return rl;
1208                 undefined = 1;
1209                 break;
1210         case EXPR_POSTOP:
1211                 return _get_rl(expr->unop, implied);
1212         case EXPR_CAST:
1213         case EXPR_FORCE_CAST:
1214         case EXPR_IMPLIED_CAST:
1215                 rl = _get_rl(expr->cast_expression, implied);
1216                 if (!rl)
1217                         undefined = 1;
1218                 else
1219                         return cast_rl(type, rl);
1220                 break;
1221         case EXPR_BINOP:
1222                 rl = handle_binop_rl(expr, implied);
1223                 if (rl)
1224                         return rl;
1225                 undefined = 1;
1226                 break;
1227         case EXPR_COMPARE:
1228                 rl = handle_comparison_rl(expr, implied);
1229                 if (rl)
1230                         return rl;
1231                 undefined = 1;
1232                 break;
1233         case EXPR_LOGICAL:
1234                 rl = handle_logical_rl(expr, implied);
1235                 if (rl)
1236                         return rl;
1237                 undefined = 1;
1238                 break;
1239         case EXPR_PTRSIZEOF:
1240         case EXPR_SIZEOF:
1241                 sval = handle_sizeof(expr);
1242                 break;
1243         case EXPR_SELECT:
1244         case EXPR_CONDITIONAL:
1245                 rl = handle_conditional_rl(expr, implied);
1246                 if (rl)
1247                         return rl;
1248                 undefined = 1;
1249                 break;
1250         case EXPR_CALL:
1251                 rl = handle_call_rl(expr, implied);
1252                 if (rl)
1253                         return rl;
1254                 else
1255                         undefined = 1;
1256                 break;
1257         default:
1258                 rl = handle_variable(expr, implied);
1259                 if (rl)
1260                         return rl;
1261                 else
1262                         undefined = 1;
1263         }
1264
1265         if (undefined && type &&
1266             (implied == ABSOLUTE_MAX || implied == ABSOLUTE_MIN))
1267                 return alloc_whole_rl(type);
1268         if (undefined)
1269                 return NULL;
1270         rl = alloc_rl(sval, sval);
1271         return rl;
1272 }
1273
1274 static sval_t _get_value(struct expression *expr, int *undefined, int implied)
1275 {
1276         struct symbol *type;
1277         sval_t ret;
1278
1279         if (!expr) {
1280                 *undefined = 1;
1281                 return bogus;
1282         }
1283         if (*undefined)
1284                 return bogus;
1285
1286         expr = strip_parens(expr);
1287         type = get_type(expr);
1288
1289         switch (expr->type) {
1290         case EXPR_VALUE:
1291                 ret = sval_from_val(expr, expr->value);
1292                 break;
1293         case EXPR_PREOP:
1294                 ret = handle_preop(expr, undefined, implied);
1295                 break;
1296         case EXPR_POSTOP:
1297                 ret = _get_value(expr->unop, undefined, implied);
1298                 break;
1299         case EXPR_CAST:
1300         case EXPR_FORCE_CAST:
1301         case EXPR_IMPLIED_CAST:
1302                 ret = _get_value(expr->cast_expression, undefined, implied);
1303                 ret = sval_cast(type, ret);
1304                 break;
1305         case EXPR_BINOP:
1306                 ret = handle_binop(expr, undefined, implied);
1307                 break;
1308         case EXPR_COMPARE:
1309                 ret = handle_comparison(expr, undefined, implied);
1310                 break;
1311         case EXPR_LOGICAL:
1312                 ret = handle_logical(expr, undefined, implied);
1313                 break;
1314         case EXPR_PTRSIZEOF:
1315         case EXPR_SIZEOF:
1316                 ret = handle_sizeof(expr);
1317                 break;
1318         case EXPR_SYMBOL:
1319                 if (get_const_value(expr, &ret)) {
1320                         break;
1321                 }
1322                 ret = _get_implied_value(expr, undefined, implied);
1323                 break;
1324         case EXPR_SELECT:
1325         case EXPR_CONDITIONAL:
1326                 ret = handle_conditional(expr, undefined, implied);
1327                 break;
1328         case EXPR_CALL:
1329                 ret = handle_call(expr, undefined, implied);
1330                 break;
1331         default:
1332                 ret = _get_implied_value(expr, undefined, implied);
1333         }
1334
1335         if (*undefined)
1336                 return bogus;
1337         return ret;
1338 }
1339
1340 /* returns 1 if it can get a value literal or else returns 0 */
1341 int get_value(struct expression *expr, sval_t *sval)
1342 {
1343         struct range_list *rl;
1344
1345         rl = _get_rl(expr, EXACT);
1346         if (!rl_to_sval(rl, sval))
1347                 return 0;
1348         return 1;
1349 }
1350
1351 int get_implied_value(struct expression *expr, sval_t *sval)
1352 {
1353         struct range_list *rl;
1354
1355         rl =  _get_rl(expr, IMPLIED);
1356         if (!rl_to_sval(rl, sval))
1357                 return 0;
1358         return 1;
1359 }
1360
1361 int get_implied_min(struct expression *expr, sval_t *sval)
1362 {
1363         struct range_list *rl;
1364
1365         rl =  _get_rl(expr, IMPLIED_MIN);
1366         if (!rl)
1367                 return 0;
1368         *sval = rl_min(rl);
1369         return 1;
1370 }
1371
1372 int get_implied_max(struct expression *expr, sval_t *sval)
1373 {
1374         struct range_list *rl;
1375
1376         rl =  _get_rl(expr, IMPLIED_MAX);
1377         if (!rl)
1378                 return 0;
1379         *sval = rl_max(rl);
1380         return 1;
1381 }
1382
1383 int get_implied_rl(struct expression *expr, struct range_list **rl)
1384 {
1385         sval_t sval;
1386         struct smatch_state *state;
1387         sval_t min, max;
1388         int min_known = 0;
1389         int max_known = 0;
1390
1391         *rl = NULL;
1392
1393         expr = strip_parens(expr);
1394         if (!expr)
1395                 return 0;
1396
1397         state = get_state_expr(SMATCH_EXTRA, expr);
1398         if (state) {
1399                 *rl = clone_rl(estate_rl(state));
1400                 return 1;
1401         }
1402
1403         if (expr->type == EXPR_CALL) {
1404                 if (get_implied_return(expr, rl))
1405                         return 1;
1406                 *rl = db_return_vals(expr);
1407                 if (*rl)
1408                         return 1;
1409                 return 0;
1410         }
1411
1412         if (get_implied_value(expr, &sval)) {
1413                 add_range(rl, sval, sval);
1414                 return 1;
1415         }
1416
1417         if (get_local_rl(expr, rl))
1418                 return 1;
1419
1420         min_known = get_implied_min(expr, &min);
1421         max_known = get_implied_max(expr, &max);
1422         if (!min_known && !max_known)
1423                 return 0;
1424         if (!min_known)
1425                 get_absolute_min(expr, &min);
1426         if (!max_known)
1427                 get_absolute_max(expr, &max);
1428
1429         *rl = alloc_rl(min, max);
1430         return 1;
1431 }
1432
1433 int get_hard_max(struct expression *expr, sval_t *sval)
1434 {
1435         struct range_list *rl;
1436
1437         rl =  _get_rl(expr, HARD_MAX);
1438         if (!rl)
1439                 return 0;
1440         *sval = rl_max(rl);
1441         return 1;
1442 }
1443
1444 int get_fuzzy_min(struct expression *expr, sval_t *sval)
1445 {
1446         struct range_list *rl;
1447
1448         rl =  _get_rl(expr, FUZZY_MIN);
1449         if (!rl)
1450                 return 0;
1451         *sval = rl_min(rl);
1452         return 1;
1453 }
1454
1455 int get_fuzzy_max(struct expression *expr, sval_t *sval)
1456 {
1457         struct range_list *rl;
1458         sval_t max;
1459
1460         rl =  _get_rl(expr, FUZZY_MAX);
1461         if (!rl)
1462                 return 0;
1463         max = rl_max(rl);
1464         if (max.uvalue > INT_MAX - 10000)
1465                 return 0;
1466         *sval = max;
1467         return 1;
1468 }
1469
1470 int get_absolute_min(struct expression *expr, sval_t *sval)
1471 {
1472         struct range_list *rl;
1473         struct symbol *type;
1474
1475         type = get_type(expr);
1476         if (!type)
1477                 type = &llong_ctype;  // FIXME: this is wrong but places assume get type can't fail.
1478         rl = _get_rl(expr, ABSOLUTE_MIN);
1479         if (rl)
1480                 *sval = rl_min(rl);
1481         else
1482                 *sval = sval_type_min(type);
1483
1484         if (sval_cmp(*sval, sval_type_min(type)) < 0)
1485                 *sval = sval_type_min(type);
1486         return 1;
1487 }
1488
1489 int get_absolute_max(struct expression *expr, sval_t *sval)
1490 {
1491         struct range_list *rl;
1492         struct symbol *type;
1493
1494         type = get_type(expr);
1495         if (!type)
1496                 type = &llong_ctype;
1497         rl = _get_rl(expr, ABSOLUTE_MAX);
1498         if (rl)
1499                 *sval = rl_max(rl);
1500         else
1501                 *sval = sval_type_max(type);
1502
1503         if (sval_cmp(sval_type_max(type), *sval) < 0)
1504                 *sval = sval_type_max(type);
1505         return 1;
1506 }
1507
1508 int known_condition_true(struct expression *expr)
1509 {
1510         sval_t tmp;
1511
1512         if (!expr)
1513                 return 0;
1514
1515         if (get_value(expr, &tmp) && tmp.value)
1516                 return 1;
1517
1518         return 0;
1519 }
1520
1521 int known_condition_false(struct expression *expr)
1522 {
1523         if (!expr)
1524                 return 0;
1525
1526         if (is_zero(expr))
1527                 return 1;
1528
1529         if (expr->type == EXPR_CALL) {
1530                 if (sym_name_is("__builtin_constant_p", expr->fn))
1531                         return 1;
1532         }
1533         return 0;
1534 }
1535
1536 int implied_condition_true(struct expression *expr)
1537 {
1538         sval_t tmp;
1539
1540         if (!expr)
1541                 return 0;
1542
1543         if (known_condition_true(expr))
1544                 return 1;
1545         if (get_implied_value(expr, &tmp) && tmp.value)
1546                 return 1;
1547
1548         if (expr->type == EXPR_POSTOP)
1549                 return implied_condition_true(expr->unop);
1550
1551         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
1552                 return implied_not_equal(expr->unop, 1);
1553         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
1554                 return implied_not_equal(expr->unop, -1);
1555
1556         expr = strip_expr(expr);
1557         switch (expr->type) {
1558         case EXPR_COMPARE:
1559                 if (do_comparison(expr) == 1)
1560                         return 1;
1561                 break;
1562         case EXPR_PREOP:
1563                 if (expr->op == '!') {
1564                         if (implied_condition_false(expr->unop))
1565                                 return 1;
1566                         break;
1567                 }
1568                 break;
1569         default:
1570                 if (implied_not_equal(expr, 0) == 1)
1571                         return 1;
1572                 break;
1573         }
1574         return 0;
1575 }
1576
1577 int implied_condition_false(struct expression *expr)
1578 {
1579         struct expression *tmp;
1580         sval_t sval;
1581
1582         if (!expr)
1583                 return 0;
1584
1585         if (known_condition_false(expr))
1586                 return 1;
1587
1588         switch (expr->type) {
1589         case EXPR_COMPARE:
1590                 if (do_comparison(expr) == 2)
1591                         return 1;
1592         case EXPR_PREOP:
1593                 if (expr->op == '!') {
1594                         if (implied_condition_true(expr->unop))
1595                                 return 1;
1596                         break;
1597                 }
1598                 tmp = strip_expr(expr);
1599                 if (tmp != expr)
1600                         return implied_condition_false(tmp);
1601                 break;
1602         default:
1603                 if (get_implied_value(expr, &sval) && sval.value == 0)
1604                         return 1;
1605                 break;
1606         }
1607         return 0;
1608 }