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