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
  18 static sval_t zero  = {.type = &int_ctype, {.value = 0} };
  19 static sval_t one   = {.type = &int_ctype, {.value = 1} };
  20
  21 static struct range_list *rl_zero(void)
  22 {
  23         return alloc_rl(zero, zero);
  24 }
  25
  26 static struct range_list *rl_one(void)
  27 {
  28         return alloc_rl(one, one);
  29 }
  30
  31 enum {
  32         RL_EXACT,
  33         RL_HARD,
  34         RL_FUZZY,
  35         RL_IMPLIED,
  36         RL_ABSOLUTE
  37 };
  38
  39 static struct range_list *last_stmt_rl(struct statement *stmt, int implied)
  40 {
  41         if (!stmt)
  42                 return NULL;
  43
  44         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
  45         if (stmt->type != STMT_EXPRESSION)
  46                 return NULL;
  47         return _get_rl(stmt->expression, implied);
  48 }
  49
  50 static struct range_list *handle_expression_statement_rl(struct expression *expr, int implied)
  51 {
  52         return last_stmt_rl(get_expression_statement(expr), implied);
  53 }
  54
  55 static struct range_list *handle_ampersand_rl(int implied)
  56 {
  57         if (implied == RL_EXACT || implied == RL_HARD)
  58                 return NULL;
  59         return alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
  60 }
  61
  62 static struct range_list *handle_negate_rl(struct expression *expr, int implied)
  63 {
  64         if (known_condition_true(expr->unop))
  65                 return rl_zero();
  66         if (known_condition_false(expr->unop))
  67                 return rl_one();
  68
  69         if (implied == RL_EXACT)
  70                 return NULL;
  71
  72         if (implied_condition_true(expr->unop))
  73                 return rl_zero();
  74         if (implied_condition_false(expr->unop))
  75                 return rl_one();
  76         return alloc_rl(zero, one);
  77 }
  78
  79 static struct range_list *handle_bitwise_negate(struct expression *expr, int implied)
  80 {
  81         struct range_list *rl;
  82         sval_t sval;
  83
  84         rl = _get_rl(expr->unop, implied);
  85         if (!rl_to_sval(rl, &sval))
  86                 return NULL;
  87         sval = sval_preop(sval, '~');
  88         sval_cast(get_type(expr->unop), sval);
  89         return alloc_rl(sval, sval);
  90 }
  91
  92 static struct range_list *handle_minus_preop(struct expression *expr, int implied)
  93 {
  94         struct range_list *rl;
  95         sval_t sval;
  96
  97         rl = _get_rl(expr->unop, implied);
  98         if (!rl_to_sval(rl, &sval))
  99                 return NULL;
 100         sval = sval_preop(sval, '-');
 101         return alloc_rl(sval, sval);
 102 }
 103
 104 static struct range_list *handle_preop_rl(struct expression *expr, int implied)
 105 {
 106         switch (expr->op) {
 107         case '&':
 108                 return handle_ampersand_rl(implied);
 109         case '!':
 110                 return handle_negate_rl(expr, implied);
 111         case '~':
 112                 return handle_bitwise_negate(expr, implied);
 113         case '-':
 114                 return handle_minus_preop(expr, implied);
 115         case '*':
 116                 return handle_variable(expr, implied);
 117         case '(':
 118                 return handle_expression_statement_rl(expr, implied);
 119         default:
 120                 return NULL;
 121         }
 122 }
 123
 124 static struct range_list *handle_divide_rl(struct expression *expr, int implied)
 125 {
 126         struct range_list *left_rl, *right_rl;
 127         struct symbol *type;
 128         sval_t min, max;
 129
 130         type = get_type(expr);
 131
 132         left_rl = _get_rl(expr->left, implied);
 133         left_rl = cast_rl(type, left_rl);
 134         right_rl = _get_rl(expr->right, implied);
 135         right_rl = cast_rl(type, right_rl);
 136
 137         if (!left_rl || !right_rl)
 138                 return NULL;
 139         if (is_whole_rl(left_rl) || is_whole_rl(right_rl))
 140                 return NULL;
 141         if (sval_is_negative(rl_min(left_rl)) || sval_cmp_val(rl_min(right_rl), 0) <= 0)
 142                 return NULL;
 143
 144         max = rl_max(left_rl);
 145         if (!sval_is_max(max))
 146                 max = sval_binop(max, '/', rl_min(right_rl));
 147         min = sval_binop(rl_min(left_rl), '/', rl_max(right_rl));
 148         return alloc_rl(min, max);
 149 }
 150
 151 static struct range_list *handle_subtract_rl(struct expression *expr, int implied)
 152 {
 153         struct symbol *type;
 154         struct range_list *left_rl, *right_rl;
 155         sval_t max, min, tmp;
 156         int comparison;
 157
 158         type = get_type(expr);
 159         comparison = get_comparison(expr->left, expr->right);
 160
 161         left_rl = _get_rl(expr->left, implied);
 162         left_rl = cast_rl(type, left_rl);
 163         right_rl = _get_rl(expr->right, implied);
 164         right_rl = cast_rl(type, right_rl);
 165
 166         if ((!left_rl || !right_rl) &&
 167             (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY))
 168                 return NULL;
 169
 170         if (!left_rl)
 171                 left_rl = alloc_whole_rl(type);
 172         if (!right_rl)
 173                 right_rl = alloc_whole_rl(type);
 174
 175         /* negative values complicate everything fix this later */
 176         if (sval_is_negative(rl_min(right_rl)))
 177                 return NULL;
 178         max = rl_max(left_rl);
 179
 180         switch (comparison) {
 181         case '>':
 182         case SPECIAL_UNSIGNED_GT:
 183                 min = sval_type_val(type, 1);
 184                 max = rl_max(left_rl);
 185                 break;
 186         case SPECIAL_GTE:
 187         case SPECIAL_UNSIGNED_GTE:
 188                 min = sval_type_val(type, 0);
 189                 max = rl_max(left_rl);
 190                 break;
 191         default:
 192                 if (sval_binop_overflows(rl_min(left_rl), '-', rl_max(right_rl)))
 193                         return NULL;
 194                 min = sval_type_min(type);
 195         }
 196
 197         if (!sval_binop_overflows(rl_min(left_rl), '-', rl_max(right_rl))) {
 198                 tmp = sval_binop(rl_min(left_rl), '-', rl_max(right_rl));
 199                 if (sval_cmp(tmp, min) > 0)
 200                         min = tmp;
 201         }
 202
 203         if (!sval_is_max(rl_max(left_rl))) {
 204                 tmp = sval_binop(rl_max(left_rl), '-', rl_min(right_rl));
 205                 if (sval_cmp(tmp, max) < 0)
 206                         max = tmp;
 207         }
 208
 209         if (sval_is_min(min) && sval_is_max(max))
 210                 return NULL;
 211
 212         return cast_rl(type, alloc_rl(min, max));
 213 }
 214
 215 static struct range_list *handle_mod_rl(struct expression *expr, int implied)
 216 {
 217         struct range_list *rl;
 218         sval_t left, right, sval;
 219
 220         if (implied == RL_EXACT) {
 221                 if (!get_value(expr->right, &right))
 222                         return NULL;
 223                 if (!get_value(expr->left, &left))
 224                         return NULL;
 225                 sval = sval_binop(left, '%', right);
 226                 return alloc_rl(sval, sval);
 227         }
 228         /* if we can't figure out the right side it's probably hopeless */
 229         if (!get_implied_value(expr->right, &right))
 230                 return NULL;
 231
 232         right = sval_cast(get_type(expr), right);
 233         right.value--;
 234
 235         rl = _get_rl(expr->left, implied);
 236         if (rl && rl_max(rl).uvalue < right.uvalue)
 237                 right.uvalue = rl_max(rl).uvalue;
 238
 239         return alloc_rl(zero, right);
 240 }
 241
 242 static sval_t sval_lowest_set_bit(sval_t sval)
 243 {
 244         int i;
 245         int found = 0;
 246
 247         for (i = 0; i < 64; i++) {
 248                 if (sval.uvalue & 1ULL << i) {
 249                         if (!found++)
 250                                 continue;
 251                         sval.uvalue &= ~(1ULL << i);
 252                 }
 253         }
 254         return sval;
 255 }
 256
 257 static struct range_list *handle_bitwise_AND(struct expression *expr, int implied)
 258 {
 259         struct symbol *type;
 260         struct range_list *left_rl, *right_rl;
 261         sval_t known;
 262
 263         if (implied != RL_IMPLIED && implied != RL_ABSOLUTE)
 264                 return NULL;
 265
 266         type = get_type(expr);
 267
 268         if (get_implied_value(expr->left, &known)) {
 269                 sval_t min;
 270
 271                 min = sval_lowest_set_bit(known);
 272                 left_rl = alloc_rl(min, known);
 273                 left_rl = cast_rl(type, left_rl);
 274                 add_range(&left_rl, sval_type_val(type, 0), sval_type_val(type, 0));
 275         } else {
 276                 left_rl = _get_rl(expr->left, implied);
 277                 if (left_rl) {
 278                         left_rl = cast_rl(type, left_rl);
 279                         left_rl = alloc_rl(sval_type_val(type, 0), rl_max(left_rl));
 280                 } else {
 281                         if (implied == RL_HARD)
 282                                 return NULL;
 283                         left_rl = alloc_whole_rl(type);
 284                 }
 285         }
 286
 287         if (get_implied_value(expr->right, &known)) {
 288                 sval_t min;
 289
 290                 min = sval_lowest_set_bit(known);
 291                 right_rl = alloc_rl(min, known);
 292                 right_rl = cast_rl(type, right_rl);
 293                 add_range(&right_rl, sval_type_val(type, 0), sval_type_val(type, 0));
 294         } else {
 295                 right_rl = _get_rl(expr->right, implied);
 296                 if (right_rl) {
 297                         right_rl = cast_rl(type, right_rl);
 298                         right_rl = alloc_rl(sval_type_val(type, 0), rl_max(right_rl));
 299                 } else {
 300                         if (implied == RL_HARD)
 301                                 return NULL;
 302                         right_rl = alloc_whole_rl(type);
 303                 }
 304         }
 305
 306         return rl_intersection(left_rl, right_rl);
 307 }
 308
 309 static struct range_list *handle_right_shift(struct expression *expr, int implied)
 310 {
 311         struct range_list *left_rl;
 312         sval_t right;
 313         sval_t min, max;
 314
 315         if (implied == RL_EXACT || implied == RL_HARD)
 316                 return NULL;
 317         /* this is hopeless without the right side */
 318         if (!get_implied_value(expr->right, &right))
 319                 return NULL;
 320         left_rl = _get_rl(expr->left, implied);
 321         if (left_rl) {
 322                 max = rl_max(left_rl);
 323                 min = rl_min(left_rl);
 324         } else {
 325                 if (implied == RL_FUZZY)
 326                         return NULL;
 327                 if (implied == RL_HARD)
 328                         return NULL;
 329                 max = sval_type_max(get_type(expr->left));
 330                 min = sval_type_val(get_type(expr->left), 0);
 331         }
 332
 333         max = sval_binop(max, SPECIAL_RIGHTSHIFT, right);
 334         min = sval_binop(min, SPECIAL_RIGHTSHIFT, right);
 335         return alloc_rl(min, max);
 336 }
 337
 338 static struct range_list *handle_known_binop(struct expression *expr)
 339 {
 340         sval_t left, right;
 341
 342         if (!get_value(expr->left, &left))
 343                 return NULL;
 344         if (!get_value(expr->right, &right))
 345                 return NULL;
 346         left = sval_binop(left, expr->op, right);
 347         return alloc_rl(left, left);
 348 }
 349
 350 static struct range_list *handle_binop_rl(struct expression *expr, int implied)
 351 {
 352         struct symbol *type;
 353         struct range_list *left_rl, *right_rl, *rl;
 354         sval_t min, max;
 355
 356         rl = handle_known_binop(expr);
 357         if (rl)
 358                 return rl;
 359         if (implied == RL_EXACT)
 360                 return NULL;
 361
 362         switch (expr->op) {
 363         case '%':
 364                 return handle_mod_rl(expr, implied);
 365         case '&':
 366                 return handle_bitwise_AND(expr, implied);
 367         case SPECIAL_RIGHTSHIFT:
 368                 return handle_right_shift(expr, implied);
 369         case '-':
 370                 return handle_subtract_rl(expr, implied);
 371         case '/':
 372                 return handle_divide_rl(expr, implied);
 373         }
 374
 375         type = get_type(expr);
 376         left_rl = _get_rl(expr->left, implied);
 377         left_rl = cast_rl(type, left_rl);
 378         right_rl = _get_rl(expr->right, implied);
 379         right_rl = cast_rl(type, right_rl);
 380
 381         if (!left_rl || !right_rl)
 382                 return NULL;
 383
 384         if (sval_binop_overflows(rl_min(left_rl), expr->op, rl_min(right_rl)))
 385                 return NULL;
 386         min = sval_binop(rl_min(left_rl), expr->op, rl_min(right_rl));
 387
 388         if (sval_binop_overflows(rl_max(left_rl), expr->op, rl_max(right_rl))) {
 389                 switch (implied) {
 390                 case RL_FUZZY:
 391                 case RL_HARD:
 392                         return NULL;
 393                 default:
 394                         max = sval_type_max(get_type(expr));
 395                 }
 396         } else {
 397                 max = sval_binop(rl_max(left_rl), expr->op, rl_max(right_rl));
 398         }
 399
 400         return alloc_rl(min, max);
 401 }
 402
 403 static int do_comparison(struct expression *expr)
 404 {
 405         struct range_list *left_ranges = NULL;
 406         struct range_list *right_ranges = NULL;
 407         int poss_true, poss_false;
 408         struct symbol *type;
 409
 410         type = get_type(expr);
 411
 412         get_implied_rl(expr->left, &left_ranges);
 413         get_implied_rl(expr->right, &right_ranges);
 414         left_ranges = cast_rl(type, left_ranges);
 415         right_ranges = cast_rl(type, right_ranges);
 416
 417         poss_true = possibly_true_rl(left_ranges, expr->op, right_ranges);
 418         poss_false = possibly_false_rl(left_ranges, expr->op, right_ranges);
 419
 420         free_rl(&left_ranges);
 421         free_rl(&right_ranges);
 422
 423         if (!poss_true && !poss_false)
 424                 return 0;
 425         if (poss_true && !poss_false)
 426                 return 1;
 427         if (!poss_true && poss_false)
 428                 return 2;
 429         return 3;
 430 }
 431
 432 static struct range_list *handle_comparison_rl(struct expression *expr, int implied)
 433 {
 434         sval_t left, right;
 435         int res;
 436
 437         if (get_value(expr->left, &left) && get_value(expr->right, &right)) {
 438                 struct data_range tmp_left, tmp_right;
 439
 440                 tmp_left.min = left;
 441                 tmp_left.max = left;
 442                 tmp_right.min = right;
 443                 tmp_right.max = right;
 444                 if (true_comparison_range(&tmp_left, expr->op, &tmp_right))
 445                         return rl_one();
 446                 return rl_zero();
 447         }
 448
 449         if (implied == RL_EXACT)
 450                 return NULL;
 451
 452         res = do_comparison(expr);
 453         if (res == 1)
 454                 return rl_one();
 455         if (res == 2)
 456                 return rl_zero();
 457
 458         return alloc_rl(zero, one);
 459 }
 460
 461 static struct range_list *handle_logical_rl(struct expression *expr, int implied)
 462 {
 463         sval_t left, right;
 464         int left_known = 0;
 465         int right_known = 0;
 466
 467         if (implied == RL_EXACT) {
 468                 if (get_value(expr->left, &left))
 469                         left_known = 1;
 470                 if (get_value(expr->right, &right))
 471                         right_known = 1;
 472         } else {
 473                 if (get_implied_value(expr->left, &left))
 474                         left_known = 1;
 475                 if (get_implied_value(expr->right, &right))
 476                         right_known = 1;
 477         }
 478
 479         switch (expr->op) {
 480         case SPECIAL_LOGICAL_OR:
 481                 if (left_known && left.value)
 482                         return rl_one();
 483                 if (right_known && right.value)
 484                         return rl_one();
 485                 if (left_known && right_known)
 486                         return rl_zero();
 487                 break;
 488         case SPECIAL_LOGICAL_AND:
 489                 if (left_known && right_known) {
 490                         if (left.value && right.value)
 491                                 return rl_one();
 492                         return rl_zero();
 493                 }
 494                 break;
 495         default:
 496                 return NULL;
 497         }
 498
 499         if (implied == RL_EXACT)
 500                 return NULL;
 501
 502         return alloc_rl(zero, one);
 503 }
 504
 505 static struct range_list *handle_conditional_rl(struct expression *expr, int implied)
 506 {
 507         struct range_list *true_rl, *false_rl;
 508         struct symbol *type;
 509         int final_pass_orig = final_pass;
 510
 511         if (known_condition_true(expr->conditional))
 512                 return _get_rl(expr->cond_true, implied);
 513         if (known_condition_false(expr->conditional))
 514                 return _get_rl(expr->cond_false, implied);
 515
 516         if (implied == RL_EXACT)
 517                 return NULL;
 518
 519         if (implied_condition_true(expr->conditional))
 520                 return _get_rl(expr->cond_true, implied);
 521         if (implied_condition_false(expr->conditional))
 522                 return _get_rl(expr->cond_false, implied);
 523
 524
 525         /* this becomes a problem with deeply nested conditional statements */
 526         if (low_on_memory())
 527                 return NULL;
 528
 529         type = get_type(expr);
 530
 531         __push_fake_cur_slist();
 532         final_pass = 0;
 533         __split_whole_condition(expr->conditional);
 534         true_rl = _get_rl(expr->cond_true, implied);
 535         __push_true_states();
 536         __use_false_states();
 537         false_rl = _get_rl(expr->cond_false, implied);
 538         __merge_true_states();
 539         __free_fake_cur_slist();
 540         final_pass = final_pass_orig;
 541
 542         if (!true_rl || !false_rl)
 543                 return NULL;
 544         true_rl = cast_rl(type, true_rl);
 545         false_rl = cast_rl(type, false_rl);
 546
 547         return rl_union(true_rl, false_rl);
 548 }
 549
 550 static int get_fuzzy_max_helper(struct expression *expr, sval_t *max)
 551 {
 552         struct sm_state *sm;
 553         struct sm_state *tmp;
 554         sval_t sval;
 555
 556         if (get_hard_max(expr, &sval)) {
 557                 *max = sval;
 558                 return 1;
 559         }
 560
 561         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 562         if (!sm)
 563                 return 0;
 564
 565         sval = sval_type_min(estate_type(sm->state));
 566         FOR_EACH_PTR(sm->possible, tmp) {
 567                 sval_t new_min;
 568
 569                 new_min = estate_min(tmp->state);
 570                 if (sval_cmp(new_min, sval) > 0)
 571                         sval = new_min;
 572         } END_FOR_EACH_PTR(tmp);
 573
 574         if (sval_is_min(sval))
 575                 return 0;
 576         if (sval.value == sval_type_min(sval.type).value + 1)  /* it's common to be on off */
 577                 return 0;
 578
 579         *max = sval_cast(get_type(expr), sval);
 580         return 1;
 581 }
 582
 583 static int get_fuzzy_min_helper(struct expression *expr, sval_t *min)
 584 {
 585         struct sm_state *sm;
 586         struct sm_state *tmp;
 587         sval_t sval;
 588
 589         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 590         if (!sm)
 591                 return 0;
 592
 593         if (!sval_is_min(estate_min(sm->state))) {
 594                 *min = estate_min(sm->state);
 595                 return 1;
 596         }
 597
 598         sval = sval_type_max(estate_type(sm->state));
 599         FOR_EACH_PTR(sm->possible, tmp) {
 600                 sval_t new_max;
 601
 602                 new_max = estate_max(tmp->state);
 603                 if (sval_cmp(new_max, sval) < 0)
 604                         sval = new_max;
 605         } END_FOR_EACH_PTR(tmp);
 606
 607         if (sval_is_max(sval))
 608                 return 0;
 609         *min = sval_cast(get_type(expr), sval);
 610         return 1;
 611 }
 612
 613 static int get_const_value(struct expression *expr, sval_t *sval)
 614 {
 615         struct symbol *sym;
 616         sval_t right;
 617
 618         if (expr->type != EXPR_SYMBOL || !expr->symbol)
 619                 return 0;
 620         sym = expr->symbol;
 621         if (!(sym->ctype.modifiers & MOD_CONST))
 622                 return 0;
 623         if (get_value(sym->initializer, &right)) {
 624                 *sval = sval_cast(get_type(expr), right);
 625                 return 1;
 626         }
 627         return 0;
 628 }
 629
 630 static struct range_list *handle_variable(struct expression *expr, int implied)
 631 {
 632         struct smatch_state *state;
 633         struct range_list *rl;
 634         sval_t sval, min, max;
 635
 636         if (get_const_value(expr, &sval))
 637                 return alloc_rl(sval, sval);
 638
 639         switch (implied) {
 640         case RL_EXACT:
 641                 return NULL;
 642         case RL_HARD:
 643         case RL_IMPLIED:
 644         case RL_ABSOLUTE:
 645                 state = get_state_expr(SMATCH_EXTRA, expr);
 646                 if (!state || !state->data) {
 647                         if (implied == RL_HARD)
 648                                 return NULL;
 649                         if (get_local_rl(expr, &rl))
 650                                 return rl;
 651                         return NULL;
 652                 }
 653                 if (implied == RL_HARD && !estate_has_hard_max(state))
 654                         return NULL;
 655                 return clone_rl(estate_rl(state));
 656         case RL_FUZZY:
 657                 if (!get_fuzzy_min_helper(expr, &min))
 658                         min = sval_type_min(get_type(expr));
 659                 if (!get_fuzzy_max_helper(expr, &max))
 660                         return NULL;
 661                 /* fuzzy ranges are often inverted */
 662                 if (sval_cmp(min, max) > 0) {
 663                         sval = min;
 664                         min = max;
 665                         max = sval;
 666                 }
 667                 return alloc_rl(min, max);
 668         }
 669         return NULL;
 670 }
 671
 672 static sval_t handle_sizeof(struct expression *expr)
 673 {
 674         struct symbol *sym;
 675         sval_t ret;
 676
 677         ret = sval_blank(expr);
 678         sym = expr->cast_type;
 679         if (!sym) {
 680                 sym = evaluate_expression(expr->cast_expression);
 681                 /*
 682                  * Expressions of restricted types will possibly get
 683                  * promoted - check that here
 684                  */
 685                 if (is_restricted_type(sym)) {
 686                         if (sym->bit_size < bits_in_int)
 687                                 sym = &int_ctype;
 688                 } else if (is_fouled_type(sym)) {
 689                         sym = &int_ctype;
 690                 }
 691         }
 692         examine_symbol_type(sym);
 693
 694         ret.type = size_t_ctype;
 695         if (sym->bit_size <= 0) /* sizeof(void) */ {
 696                 if (get_real_base_type(sym) == &void_ctype)
 697                         ret.value = 1;
 698                 else
 699                         ret.value = 0;
 700         } else
 701                 ret.value = bits_to_bytes(sym->bit_size);
 702
 703         return ret;
 704 }
 705
 706 static struct range_list *handle_call_rl(struct expression *expr, int implied)
 707 {
 708         struct range_list *rl;
 709
 710         if (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY)
 711                 return NULL;
 712
 713         if (get_implied_return(expr, &rl))
 714                 return rl;
 715         return db_return_vals(expr);
 716 }
 717
 718 static struct range_list *_get_rl(struct expression *expr, int implied)
 719 {
 720         struct range_list *rl;
 721         struct symbol *type;
 722         sval_t sval;
 723
 724         expr = strip_parens(expr);
 725         if (!expr)
 726                 return NULL;
 727         type = get_type(expr);
 728
 729         switch (expr->type) {
 730         case EXPR_VALUE:
 731                 sval = sval_from_val(expr, expr->value);
 732                 rl = alloc_rl(sval, sval);
 733                 break;
 734         case EXPR_PREOP:
 735                 rl = handle_preop_rl(expr, implied);
 736                 break;
 737         case EXPR_POSTOP:
 738                 rl = _get_rl(expr->unop, implied);
 739                 break;
 740         case EXPR_CAST:
 741         case EXPR_FORCE_CAST:
 742         case EXPR_IMPLIED_CAST:
 743                 rl = _get_rl(expr->cast_expression, implied);
 744                 rl = cast_rl(type, rl);
 745                 break;
 746         case EXPR_BINOP:
 747                 rl = handle_binop_rl(expr, implied);
 748                 break;
 749         case EXPR_COMPARE:
 750                 rl = handle_comparison_rl(expr, implied);
 751                 break;
 752         case EXPR_LOGICAL:
 753                 rl = handle_logical_rl(expr, implied);
 754                 break;
 755         case EXPR_PTRSIZEOF:
 756         case EXPR_SIZEOF:
 757                 sval = handle_sizeof(expr);
 758                 rl = alloc_rl(sval, sval);
 759                 break;
 760         case EXPR_SELECT:
 761         case EXPR_CONDITIONAL:
 762                 rl = handle_conditional_rl(expr, implied);
 763                 break;
 764         case EXPR_CALL:
 765                 rl = handle_call_rl(expr, implied);
 766                 break;
 767         default:
 768                 rl = handle_variable(expr, implied);
 769         }
 770
 771         if (rl)
 772                 return rl;
 773         if (type && implied == RL_ABSOLUTE)
 774                 return alloc_whole_rl(type);
 775         return NULL;
 776 }
 777
 778 /* returns 1 if it can get a value literal or else returns 0 */
 779 int get_value(struct expression *expr, sval_t *sval)
 780 {
 781         struct range_list *rl;
 782
 783         rl = _get_rl(expr, RL_EXACT);
 784         if (!rl_to_sval(rl, sval))
 785                 return 0;
 786         return 1;
 787 }
 788
 789 int get_implied_value(struct expression *expr, sval_t *sval)
 790 {
 791         struct range_list *rl;
 792
 793         rl =  _get_rl(expr, RL_IMPLIED);
 794         if (!rl_to_sval(rl, sval))
 795                 return 0;
 796         return 1;
 797 }
 798
 799 int get_implied_min(struct expression *expr, sval_t *sval)
 800 {
 801         struct range_list *rl;
 802
 803         rl =  _get_rl(expr, RL_IMPLIED);
 804         if (!rl)
 805                 return 0;
 806         *sval = rl_min(rl);
 807         return 1;
 808 }
 809
 810 int get_implied_max(struct expression *expr, sval_t *sval)
 811 {
 812         struct range_list *rl;
 813
 814         rl =  _get_rl(expr, RL_IMPLIED);
 815         if (!rl)
 816                 return 0;
 817         *sval = rl_max(rl);
 818         return 1;
 819 }
 820
 821 int get_implied_rl(struct expression *expr, struct range_list **rl)
 822 {
 823         *rl = _get_rl(expr, RL_IMPLIED);
 824         if (*rl)
 825                 return 1;
 826         return 0;
 827 }
 828
 829 int get_absolute_rl(struct expression *expr, struct range_list **rl)
 830 {
 831         *rl = _get_rl(expr, RL_ABSOLUTE);
 832         if (!*rl)
 833                 *rl = alloc_whole_rl(get_type(expr));
 834         return 1;
 835 }
 836
 837 int get_implied_rl_var_sym(const char *var, struct symbol *sym, struct range_list **rl)
 838 {
 839         struct smatch_state *state;
 840
 841         state = get_state(SMATCH_EXTRA, var, sym);
 842         *rl = estate_rl(state);
 843         if (*rl)
 844                 return 1;
 845         return 0;
 846 }
 847
 848 int get_hard_max(struct expression *expr, sval_t *sval)
 849 {
 850         struct range_list *rl;
 851
 852         rl =  _get_rl(expr, RL_HARD);
 853         if (!rl)
 854                 return 0;
 855         *sval = rl_max(rl);
 856         return 1;
 857 }
 858
 859 int get_fuzzy_min(struct expression *expr, sval_t *sval)
 860 {
 861         struct range_list *rl;
 862         sval_t tmp;
 863
 864         rl =  _get_rl(expr, RL_FUZZY);
 865         if (!rl)
 866                 return 0;
 867         tmp = rl_min(rl);
 868         if (sval_is_negative(tmp) && sval_is_min(tmp))
 869                 return 0;
 870         *sval = tmp;
 871         return 1;
 872 }
 873
 874 int get_fuzzy_max(struct expression *expr, sval_t *sval)
 875 {
 876         struct range_list *rl;
 877         sval_t max;
 878
 879         rl =  _get_rl(expr, RL_FUZZY);
 880         if (!rl)
 881                 return 0;
 882         max = rl_max(rl);
 883         if (max.uvalue > INT_MAX - 10000)
 884                 return 0;
 885         *sval = max;
 886         return 1;
 887 }
 888
 889 int get_absolute_min(struct expression *expr, sval_t *sval)
 890 {
 891         struct range_list *rl;
 892         struct symbol *type;
 893
 894         type = get_type(expr);
 895         if (!type)
 896                 type = &llong_ctype;  // FIXME: this is wrong but places assume get type can't fail.
 897         rl = _get_rl(expr, RL_ABSOLUTE);
 898         if (rl)
 899                 *sval = rl_min(rl);
 900         else
 901                 *sval = sval_type_min(type);
 902
 903         if (sval_cmp(*sval, sval_type_min(type)) < 0)
 904                 *sval = sval_type_min(type);
 905         return 1;
 906 }
 907
 908 int get_absolute_max(struct expression *expr, sval_t *sval)
 909 {
 910         struct range_list *rl;
 911         struct symbol *type;
 912
 913         type = get_type(expr);
 914         if (!type)
 915                 type = &llong_ctype;
 916         rl = _get_rl(expr, RL_ABSOLUTE);
 917         if (rl)
 918                 *sval = rl_max(rl);
 919         else
 920                 *sval = sval_type_max(type);
 921
 922         if (sval_cmp(sval_type_max(type), *sval) < 0)
 923                 *sval = sval_type_max(type);
 924         return 1;
 925 }
 926
 927 int known_condition_true(struct expression *expr)
 928 {
 929         sval_t tmp;
 930
 931         if (!expr)
 932                 return 0;
 933
 934         if (get_value(expr, &tmp) && tmp.value)
 935                 return 1;
 936
 937         return 0;
 938 }
 939
 940 int known_condition_false(struct expression *expr)
 941 {
 942         if (!expr)
 943                 return 0;
 944
 945         if (is_zero(expr))
 946                 return 1;
 947
 948         if (expr->type == EXPR_CALL) {
 949                 if (sym_name_is("__builtin_constant_p", expr->fn))
 950                         return 1;
 951         }
 952         return 0;
 953 }
 954
 955 int implied_condition_true(struct expression *expr)
 956 {
 957         sval_t tmp;
 958
 959         if (!expr)
 960                 return 0;
 961
 962         if (known_condition_true(expr))
 963                 return 1;
 964         if (get_implied_value(expr, &tmp) && tmp.value)
 965                 return 1;
 966
 967         if (expr->type == EXPR_POSTOP)
 968                 return implied_condition_true(expr->unop);
 969
 970         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
 971                 return implied_not_equal(expr->unop, 1);
 972         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
 973                 return implied_not_equal(expr->unop, -1);
 974
 975         expr = strip_expr(expr);
 976         switch (expr->type) {
 977         case EXPR_COMPARE:
 978                 if (do_comparison(expr) == 1)
 979                         return 1;
 980                 break;
 981         case EXPR_PREOP:
 982                 if (expr->op == '!') {
 983                         if (implied_condition_false(expr->unop))
 984                                 return 1;
 985                         break;
 986                 }
 987                 break;
 988         default:
 989                 if (implied_not_equal(expr, 0) == 1)
 990                         return 1;
 991                 break;
 992         }
 993         return 0;
 994 }
 995
 996 int implied_condition_false(struct expression *expr)
 997 {
 998         struct expression *tmp;
 999         sval_t sval;
1000
1001         if (!expr)
1002                 return 0;
1003
1004         if (known_condition_false(expr))
1005                 return 1;
1006
1007         switch (expr->type) {
1008         case EXPR_COMPARE:
1009                 if (do_comparison(expr) == 2)
1010                         return 1;
1011         case EXPR_PREOP:
1012                 if (expr->op == '!') {
1013                         if (implied_condition_true(expr->unop))
1014                                 return 1;
1015                         break;
1016                 }
1017                 tmp = strip_expr(expr);
1018                 if (tmp != expr)
1019                         return implied_condition_false(tmp);
1020                 break;
1021         default:
1022                 if (get_implied_value(expr, &sval) && sval.value == 0)
1023                         return 1;
1024                 break;
1025         }
1026         return 0;
1027 }