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 struct range_list *handle_bitwise_AND(struct expression *expr, int implied)
 243 {
 244         struct symbol *type;
 245         struct range_list *left_rl, *right_rl;
 246
 247         if (implied != RL_IMPLIED && implied != RL_ABSOLUTE)
 248                 return NULL;
 249
 250         type = get_type(expr);
 251
 252         left_rl = _get_rl(expr->left, implied);
 253         if (left_rl) {
 254                 left_rl = cast_rl(type, left_rl);
 255                 left_rl = alloc_rl(sval_type_val(type, 0), rl_max(left_rl));
 256         } else {
 257                 if (implied == RL_HARD)
 258                         return NULL;
 259                 left_rl = alloc_whole_rl(type);
 260         }
 261
 262         right_rl = _get_rl(expr->right, implied);
 263         if (right_rl) {
 264                 right_rl = cast_rl(type, right_rl);
 265                 right_rl = alloc_rl(sval_type_val(type, 0), rl_max(right_rl));
 266         } else {
 267                 if (implied == RL_HARD)
 268                         return NULL;
 269                 right_rl = alloc_whole_rl(type);
 270         }
 271
 272         return rl_intersection(left_rl, right_rl);
 273 }
 274
 275 static struct range_list *handle_right_shift(struct expression *expr, int implied)
 276 {
 277         struct range_list *left_rl;
 278         sval_t right;
 279         sval_t min, max;
 280
 281         if (implied == RL_EXACT || implied == RL_HARD)
 282                 return NULL;
 283         /* this is hopeless without the right side */
 284         if (!get_implied_value(expr->right, &right))
 285                 return NULL;
 286         left_rl = _get_rl(expr->left, implied);
 287         if (left_rl) {
 288                 max = rl_max(left_rl);
 289                 min = rl_min(left_rl);
 290         } else {
 291                 if (implied == RL_FUZZY)
 292                         return NULL;
 293                 if (implied == RL_HARD)
 294                         return NULL;
 295                 max = sval_type_max(get_type(expr->left));
 296                 min = sval_type_val(get_type(expr->left), 0);
 297         }
 298
 299         max = sval_binop(max, SPECIAL_RIGHTSHIFT, right);
 300         min = sval_binop(min, SPECIAL_RIGHTSHIFT, right);
 301         return alloc_rl(min, max);
 302 }
 303
 304 static struct range_list *handle_known_binop(struct expression *expr)
 305 {
 306         sval_t left, right;
 307
 308         if (!get_value(expr->left, &left))
 309                 return NULL;
 310         if (!get_value(expr->right, &right))
 311                 return NULL;
 312         left = sval_binop(left, expr->op, right);
 313         return alloc_rl(left, left);
 314 }
 315
 316 static struct range_list *handle_binop_rl(struct expression *expr, int implied)
 317 {
 318         struct symbol *type;
 319         struct range_list *left_rl, *right_rl, *rl;
 320         sval_t min, max;
 321
 322         rl = handle_known_binop(expr);
 323         if (rl)
 324                 return rl;
 325         if (implied == RL_EXACT)
 326                 return NULL;
 327
 328         switch (expr->op) {
 329         case '%':
 330                 return handle_mod_rl(expr, implied);
 331         case '&':
 332                 return handle_bitwise_AND(expr, implied);
 333         case SPECIAL_RIGHTSHIFT:
 334                 return handle_right_shift(expr, implied);
 335         case '-':
 336                 return handle_subtract_rl(expr, implied);
 337         case '/':
 338                 return handle_divide_rl(expr, implied);
 339         }
 340
 341         type = get_type(expr);
 342         left_rl = _get_rl(expr->left, implied);
 343         left_rl = cast_rl(type, left_rl);
 344         right_rl = _get_rl(expr->right, implied);
 345         right_rl = cast_rl(type, right_rl);
 346
 347         if (!left_rl || !right_rl)
 348                 return NULL;
 349
 350         if (sval_binop_overflows(rl_min(left_rl), expr->op, rl_min(right_rl)))
 351                 return NULL;
 352         min = sval_binop(rl_min(left_rl), expr->op, rl_min(right_rl));
 353
 354         if (sval_binop_overflows(rl_max(left_rl), expr->op, rl_max(right_rl))) {
 355                 switch (implied) {
 356                 case RL_FUZZY:
 357                 case RL_HARD:
 358                         return NULL;
 359                 default:
 360                         max = sval_type_max(get_type(expr));
 361                 }
 362         } else {
 363                 max = sval_binop(rl_max(left_rl), expr->op, rl_max(right_rl));
 364         }
 365
 366         return alloc_rl(min, max);
 367 }
 368
 369 static int do_comparison(struct expression *expr)
 370 {
 371         struct range_list *left_ranges = NULL;
 372         struct range_list *right_ranges = NULL;
 373         int poss_true, poss_false;
 374         struct symbol *type;
 375
 376         type = get_type(expr);
 377
 378         get_implied_rl(expr->left, &left_ranges);
 379         get_implied_rl(expr->right, &right_ranges);
 380         left_ranges = cast_rl(type, left_ranges);
 381         right_ranges = cast_rl(type, right_ranges);
 382
 383         poss_true = possibly_true_rl(left_ranges, expr->op, right_ranges);
 384         poss_false = possibly_false_rl(left_ranges, expr->op, right_ranges);
 385
 386         free_rl(&left_ranges);
 387         free_rl(&right_ranges);
 388
 389         if (!poss_true && !poss_false)
 390                 return 0;
 391         if (poss_true && !poss_false)
 392                 return 1;
 393         if (!poss_true && poss_false)
 394                 return 2;
 395         return 3;
 396 }
 397
 398 static struct range_list *handle_comparison_rl(struct expression *expr, int implied)
 399 {
 400         sval_t left, right;
 401         int res;
 402
 403         if (get_value(expr->left, &left) && get_value(expr->right, &right)) {
 404                 struct data_range tmp_left, tmp_right;
 405
 406                 tmp_left.min = left;
 407                 tmp_left.max = left;
 408                 tmp_right.min = right;
 409                 tmp_right.max = right;
 410                 if (true_comparison_range(&tmp_left, expr->op, &tmp_right))
 411                         return rl_one();
 412                 return rl_zero();
 413         }
 414
 415         if (implied == RL_EXACT)
 416                 return NULL;
 417
 418         res = do_comparison(expr);
 419         if (res == 1)
 420                 return rl_one();
 421         if (res == 2)
 422                 return rl_zero();
 423
 424         return alloc_rl(zero, one);
 425 }
 426
 427 static struct range_list *handle_logical_rl(struct expression *expr, int implied)
 428 {
 429         sval_t left, right;
 430         int left_known = 0;
 431         int right_known = 0;
 432
 433         if (implied == RL_EXACT) {
 434                 if (get_value(expr->left, &left))
 435                         left_known = 1;
 436                 if (get_value(expr->right, &right))
 437                         right_known = 1;
 438         } else {
 439                 if (get_implied_value(expr->left, &left))
 440                         left_known = 1;
 441                 if (get_implied_value(expr->right, &right))
 442                         right_known = 1;
 443         }
 444
 445         switch (expr->op) {
 446         case SPECIAL_LOGICAL_OR:
 447                 if (left_known && left.value)
 448                         return rl_one();
 449                 if (right_known && right.value)
 450                         return rl_one();
 451                 if (left_known && right_known)
 452                         return rl_zero();
 453                 break;
 454         case SPECIAL_LOGICAL_AND:
 455                 if (left_known && right_known) {
 456                         if (left.value && right.value)
 457                                 return rl_one();
 458                         return rl_zero();
 459                 }
 460                 break;
 461         default:
 462                 return NULL;
 463         }
 464
 465         if (implied == RL_EXACT)
 466                 return NULL;
 467
 468         return alloc_rl(zero, one);
 469 }
 470
 471 static struct range_list *handle_conditional_rl(struct expression *expr, int implied)
 472 {
 473         struct range_list *true_rl, *false_rl;
 474         struct symbol *type;
 475         int final_pass_orig = final_pass;
 476
 477         if (known_condition_true(expr->conditional))
 478                 return _get_rl(expr->cond_true, implied);
 479         if (known_condition_false(expr->conditional))
 480                 return _get_rl(expr->cond_false, implied);
 481
 482         if (implied == RL_EXACT)
 483                 return NULL;
 484
 485         if (implied_condition_true(expr->conditional))
 486                 return _get_rl(expr->cond_true, implied);
 487         if (implied_condition_false(expr->conditional))
 488                 return _get_rl(expr->cond_false, implied);
 489
 490
 491         /* this becomes a problem with deeply nested conditional statements */
 492         if (low_on_memory())
 493                 return NULL;
 494
 495         type = get_type(expr);
 496
 497         __push_fake_cur_slist();
 498         final_pass = 0;
 499         __split_whole_condition(expr->conditional);
 500         true_rl = _get_rl(expr->cond_true, implied);
 501         __push_true_states();
 502         __use_false_states();
 503         false_rl = _get_rl(expr->cond_false, implied);
 504         __merge_true_states();
 505         __free_fake_cur_slist();
 506         final_pass = final_pass_orig;
 507
 508         if (!true_rl || !false_rl)
 509                 return NULL;
 510         true_rl = cast_rl(type, true_rl);
 511         false_rl = cast_rl(type, false_rl);
 512
 513         return rl_union(true_rl, false_rl);
 514 }
 515
 516 static int get_fuzzy_max_helper(struct expression *expr, sval_t *max)
 517 {
 518         struct sm_state *sm;
 519         struct sm_state *tmp;
 520         sval_t sval;
 521
 522         if (get_hard_max(expr, &sval)) {
 523                 *max = sval;
 524                 return 1;
 525         }
 526
 527         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 528         if (!sm)
 529                 return 0;
 530
 531         sval = sval_type_min(estate_type(sm->state));
 532         FOR_EACH_PTR(sm->possible, tmp) {
 533                 sval_t new_min;
 534
 535                 new_min = estate_min(tmp->state);
 536                 if (sval_cmp(new_min, sval) > 0)
 537                         sval = new_min;
 538         } END_FOR_EACH_PTR(tmp);
 539
 540         if (sval_is_min(sval))
 541                 return 0;
 542         if (sval.value == sval_type_min(sval.type).value + 1)  /* it's common to be on off */
 543                 return 0;
 544
 545         *max = sval_cast(get_type(expr), sval);
 546         return 1;
 547 }
 548
 549 static int get_fuzzy_min_helper(struct expression *expr, sval_t *min)
 550 {
 551         struct sm_state *sm;
 552         struct sm_state *tmp;
 553         sval_t sval;
 554
 555         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 556         if (!sm)
 557                 return 0;
 558
 559         if (!sval_is_min(estate_min(sm->state))) {
 560                 *min = estate_min(sm->state);
 561                 return 1;
 562         }
 563
 564         sval = sval_type_max(estate_type(sm->state));
 565         FOR_EACH_PTR(sm->possible, tmp) {
 566                 sval_t new_max;
 567
 568                 new_max = estate_max(tmp->state);
 569                 if (sval_cmp(new_max, sval) < 0)
 570                         sval = new_max;
 571         } END_FOR_EACH_PTR(tmp);
 572
 573         if (sval_is_max(sval))
 574                 return 0;
 575         *min = sval_cast(get_type(expr), sval);
 576         return 1;
 577 }
 578
 579 static int get_const_value(struct expression *expr, sval_t *sval)
 580 {
 581         struct symbol *sym;
 582         sval_t right;
 583
 584         if (expr->type != EXPR_SYMBOL || !expr->symbol)
 585                 return 0;
 586         sym = expr->symbol;
 587         if (!(sym->ctype.modifiers & MOD_CONST))
 588                 return 0;
 589         if (get_value(sym->initializer, &right)) {
 590                 *sval = sval_cast(get_type(expr), right);
 591                 return 1;
 592         }
 593         return 0;
 594 }
 595
 596 static struct range_list *handle_variable(struct expression *expr, int implied)
 597 {
 598         struct smatch_state *state;
 599         struct range_list *rl;
 600         sval_t sval, min, max;
 601
 602         if (get_const_value(expr, &sval))
 603                 return alloc_rl(sval, sval);
 604
 605         switch (implied) {
 606         case RL_EXACT:
 607                 return NULL;
 608         case RL_HARD:
 609         case RL_IMPLIED:
 610         case RL_ABSOLUTE:
 611                 state = get_state_expr(SMATCH_EXTRA, expr);
 612                 if (!state || !state->data) {
 613                         if (implied == RL_HARD)
 614                                 return NULL;
 615                         if (get_local_rl(expr, &rl))
 616                                 return rl;
 617                         return NULL;
 618                 }
 619                 if (implied == RL_HARD && !estate_has_hard_max(state))
 620                         return NULL;
 621                 return clone_rl(estate_rl(state));
 622         case RL_FUZZY:
 623                 if (!get_fuzzy_min_helper(expr, &min))
 624                         min = sval_type_min(get_type(expr));
 625                 if (!get_fuzzy_max_helper(expr, &max))
 626                         return NULL;
 627                 /* fuzzy ranges are often inverted */
 628                 if (sval_cmp(min, max) > 0) {
 629                         sval = min;
 630                         min = max;
 631                         max = sval;
 632                 }
 633                 return alloc_rl(min, max);
 634         }
 635         return NULL;
 636 }
 637
 638 static sval_t handle_sizeof(struct expression *expr)
 639 {
 640         struct symbol *sym;
 641         sval_t ret;
 642
 643         ret = sval_blank(expr);
 644         sym = expr->cast_type;
 645         if (!sym) {
 646                 sym = evaluate_expression(expr->cast_expression);
 647                 /*
 648                  * Expressions of restricted types will possibly get
 649                  * promoted - check that here
 650                  */
 651                 if (is_restricted_type(sym)) {
 652                         if (sym->bit_size < bits_in_int)
 653                                 sym = &int_ctype;
 654                 } else if (is_fouled_type(sym)) {
 655                         sym = &int_ctype;
 656                 }
 657         }
 658         examine_symbol_type(sym);
 659
 660         ret.type = size_t_ctype;
 661         if (sym->bit_size <= 0) /* sizeof(void) */ {
 662                 if (get_real_base_type(sym) == &void_ctype)
 663                         ret.value = 1;
 664                 else
 665                         ret.value = 0;
 666         } else
 667                 ret.value = bits_to_bytes(sym->bit_size);
 668
 669         return ret;
 670 }
 671
 672 static struct range_list *handle_call_rl(struct expression *expr, int implied)
 673 {
 674         struct range_list *rl;
 675
 676         if (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY)
 677                 return NULL;
 678
 679         if (get_implied_return(expr, &rl))
 680                 return rl;
 681         return db_return_vals(expr);
 682 }
 683
 684 static struct range_list *_get_rl(struct expression *expr, int implied)
 685 {
 686         struct range_list *rl;
 687         struct symbol *type;
 688         sval_t sval;
 689
 690         expr = strip_parens(expr);
 691         if (!expr)
 692                 return NULL;
 693         type = get_type(expr);
 694
 695         switch (expr->type) {
 696         case EXPR_VALUE:
 697                 sval = sval_from_val(expr, expr->value);
 698                 rl = alloc_rl(sval, sval);
 699                 break;
 700         case EXPR_PREOP:
 701                 rl = handle_preop_rl(expr, implied);
 702                 break;
 703         case EXPR_POSTOP:
 704                 rl = _get_rl(expr->unop, implied);
 705                 break;
 706         case EXPR_CAST:
 707         case EXPR_FORCE_CAST:
 708         case EXPR_IMPLIED_CAST:
 709                 rl = _get_rl(expr->cast_expression, implied);
 710                 rl = cast_rl(type, rl);
 711                 break;
 712         case EXPR_BINOP:
 713                 rl = handle_binop_rl(expr, implied);
 714                 break;
 715         case EXPR_COMPARE:
 716                 rl = handle_comparison_rl(expr, implied);
 717                 break;
 718         case EXPR_LOGICAL:
 719                 rl = handle_logical_rl(expr, implied);
 720                 break;
 721         case EXPR_PTRSIZEOF:
 722         case EXPR_SIZEOF:
 723                 sval = handle_sizeof(expr);
 724                 rl = alloc_rl(sval, sval);
 725                 break;
 726         case EXPR_SELECT:
 727         case EXPR_CONDITIONAL:
 728                 rl = handle_conditional_rl(expr, implied);
 729                 break;
 730         case EXPR_CALL:
 731                 rl = handle_call_rl(expr, implied);
 732                 break;
 733         default:
 734                 rl = handle_variable(expr, implied);
 735         }
 736
 737         if (rl)
 738                 return rl;
 739         if (type && implied == RL_ABSOLUTE)
 740                 return alloc_whole_rl(type);
 741         return NULL;
 742 }
 743
 744 /* returns 1 if it can get a value literal or else returns 0 */
 745 int get_value(struct expression *expr, sval_t *sval)
 746 {
 747         struct range_list *rl;
 748
 749         rl = _get_rl(expr, RL_EXACT);
 750         if (!rl_to_sval(rl, sval))
 751                 return 0;
 752         return 1;
 753 }
 754
 755 int get_implied_value(struct expression *expr, sval_t *sval)
 756 {
 757         struct range_list *rl;
 758
 759         rl =  _get_rl(expr, RL_IMPLIED);
 760         if (!rl_to_sval(rl, sval))
 761                 return 0;
 762         return 1;
 763 }
 764
 765 int get_implied_min(struct expression *expr, sval_t *sval)
 766 {
 767         struct range_list *rl;
 768
 769         rl =  _get_rl(expr, RL_IMPLIED);
 770         if (!rl)
 771                 return 0;
 772         *sval = rl_min(rl);
 773         return 1;
 774 }
 775
 776 int get_implied_max(struct expression *expr, sval_t *sval)
 777 {
 778         struct range_list *rl;
 779
 780         rl =  _get_rl(expr, RL_IMPLIED);
 781         if (!rl)
 782                 return 0;
 783         *sval = rl_max(rl);
 784         return 1;
 785 }
 786
 787 int get_implied_rl(struct expression *expr, struct range_list **rl)
 788 {
 789         *rl = _get_rl(expr, RL_IMPLIED);
 790         if (*rl)
 791                 return 1;
 792         return 0;
 793 }
 794
 795 int get_implied_rl_var_sym(const char *var, struct symbol *sym, struct range_list **rl)
 796 {
 797         struct smatch_state *state;
 798
 799         state = get_state(SMATCH_EXTRA, var, sym);
 800         *rl = estate_rl(state);
 801         if (*rl)
 802                 return 1;
 803         return 0;
 804 }
 805
 806 int get_hard_max(struct expression *expr, sval_t *sval)
 807 {
 808         struct range_list *rl;
 809
 810         rl =  _get_rl(expr, RL_HARD);
 811         if (!rl)
 812                 return 0;
 813         *sval = rl_max(rl);
 814         return 1;
 815 }
 816
 817 int get_fuzzy_min(struct expression *expr, sval_t *sval)
 818 {
 819         struct range_list *rl;
 820         sval_t tmp;
 821
 822         rl =  _get_rl(expr, RL_FUZZY);
 823         if (!rl)
 824                 return 0;
 825         tmp = rl_min(rl);
 826         if (sval_is_negative(tmp) && sval_is_min(tmp))
 827                 return 0;
 828         *sval = tmp;
 829         return 1;
 830 }
 831
 832 int get_fuzzy_max(struct expression *expr, sval_t *sval)
 833 {
 834         struct range_list *rl;
 835         sval_t max;
 836
 837         rl =  _get_rl(expr, RL_FUZZY);
 838         if (!rl)
 839                 return 0;
 840         max = rl_max(rl);
 841         if (max.uvalue > INT_MAX - 10000)
 842                 return 0;
 843         *sval = max;
 844         return 1;
 845 }
 846
 847 int get_absolute_min(struct expression *expr, sval_t *sval)
 848 {
 849         struct range_list *rl;
 850         struct symbol *type;
 851
 852         type = get_type(expr);
 853         if (!type)
 854                 type = &llong_ctype;  // FIXME: this is wrong but places assume get type can't fail.
 855         rl = _get_rl(expr, RL_ABSOLUTE);
 856         if (rl)
 857                 *sval = rl_min(rl);
 858         else
 859                 *sval = sval_type_min(type);
 860
 861         if (sval_cmp(*sval, sval_type_min(type)) < 0)
 862                 *sval = sval_type_min(type);
 863         return 1;
 864 }
 865
 866 int get_absolute_max(struct expression *expr, sval_t *sval)
 867 {
 868         struct range_list *rl;
 869         struct symbol *type;
 870
 871         type = get_type(expr);
 872         if (!type)
 873                 type = &llong_ctype;
 874         rl = _get_rl(expr, RL_ABSOLUTE);
 875         if (rl)
 876                 *sval = rl_max(rl);
 877         else
 878                 *sval = sval_type_max(type);
 879
 880         if (sval_cmp(sval_type_max(type), *sval) < 0)
 881                 *sval = sval_type_max(type);
 882         return 1;
 883 }
 884
 885 int known_condition_true(struct expression *expr)
 886 {
 887         sval_t tmp;
 888
 889         if (!expr)
 890                 return 0;
 891
 892         if (get_value(expr, &tmp) && tmp.value)
 893                 return 1;
 894
 895         return 0;
 896 }
 897
 898 int known_condition_false(struct expression *expr)
 899 {
 900         if (!expr)
 901                 return 0;
 902
 903         if (is_zero(expr))
 904                 return 1;
 905
 906         if (expr->type == EXPR_CALL) {
 907                 if (sym_name_is("__builtin_constant_p", expr->fn))
 908                         return 1;
 909         }
 910         return 0;
 911 }
 912
 913 int implied_condition_true(struct expression *expr)
 914 {
 915         sval_t tmp;
 916
 917         if (!expr)
 918                 return 0;
 919
 920         if (known_condition_true(expr))
 921                 return 1;
 922         if (get_implied_value(expr, &tmp) && tmp.value)
 923                 return 1;
 924
 925         if (expr->type == EXPR_POSTOP)
 926                 return implied_condition_true(expr->unop);
 927
 928         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
 929                 return implied_not_equal(expr->unop, 1);
 930         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
 931                 return implied_not_equal(expr->unop, -1);
 932
 933         expr = strip_expr(expr);
 934         switch (expr->type) {
 935         case EXPR_COMPARE:
 936                 if (do_comparison(expr) == 1)
 937                         return 1;
 938                 break;
 939         case EXPR_PREOP:
 940                 if (expr->op == '!') {
 941                         if (implied_condition_false(expr->unop))
 942                                 return 1;
 943                         break;
 944                 }
 945                 break;
 946         default:
 947                 if (implied_not_equal(expr, 0) == 1)
 948                         return 1;
 949                 break;
 950         }
 951         return 0;
 952 }
 953
 954 int implied_condition_false(struct expression *expr)
 955 {
 956         struct expression *tmp;
 957         sval_t sval;
 958
 959         if (!expr)
 960                 return 0;
 961
 962         if (known_condition_false(expr))
 963                 return 1;
 964
 965         switch (expr->type) {
 966         case EXPR_COMPARE:
 967                 if (do_comparison(expr) == 2)
 968                         return 1;
 969         case EXPR_PREOP:
 970                 if (expr->op == '!') {
 971                         if (implied_condition_true(expr->unop))
 972                                 return 1;
 973                         break;
 974                 }
 975                 tmp = strip_expr(expr);
 976                 if (tmp != expr)
 977                         return implied_condition_false(tmp);
 978                 break;
 979         default:
 980                 if (get_implied_value(expr, &sval) && sval.value == 0)
 981                         return 1;
 982                 break;
 983         }
 984         return 0;
 985 }