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