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