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