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