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