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