smatch_math.c

   1 /*
   2  * Copyright (C) 2010 Dan Carpenter.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
  16  */
  17
  18 #include "symbol.h"
  19 #include "smatch.h"
  20 #include "smatch_slist.h"
  21 #include "smatch_extra.h"
  22
  23 static struct range_list *_get_rl(struct expression *expr, int implied, int *recurse_cnt);
  24 static struct range_list *handle_variable(struct expression *expr, int implied, int *recurse_cnt);
  25 static struct range_list *(*custom_handle_variable)(struct expression *expr);
  26
  27 static int get_implied_value_internal(struct expression *expr, sval_t *sval, int *recurse_cnt);
  28 static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt);
  29
  30 static sval_t zero  = {.type = &int_ctype, {.value = 0} };
  31 static sval_t one   = {.type = &int_ctype, {.value = 1} };
  32
  33 struct range_list *rl_zero(void)
  34 {
  35         static struct range_list *zero_perm;
  36
  37         if (!zero_perm)
  38                 zero_perm = clone_rl_permanent(alloc_rl(zero, zero));
  39         return zero_perm;
  40 }
  41
  42 struct range_list *rl_one(void)
  43 {
  44         static struct range_list *one_perm;
  45
  46         if (!one_perm)
  47                 one_perm = clone_rl_permanent(alloc_rl(one, one));
  48
  49         return one_perm;
  50 }
  51
  52 enum {
  53         RL_EXACT,
  54         RL_HARD,
  55         RL_FUZZY,
  56         RL_IMPLIED,
  57         RL_ABSOLUTE,
  58         RL_REAL_ABSOLUTE,
  59 };
  60
  61 static struct range_list *last_stmt_rl(struct statement *stmt, int implied, int *recurse_cnt)
  62 {
  63         struct expression *expr;
  64
  65         if (!stmt)
  66                 return NULL;
  67
  68         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
  69         if (stmt->type == STMT_LABEL) {
  70                 if (stmt->label_statement &&
  71                     stmt->label_statement->type == STMT_EXPRESSION)
  72                         expr = stmt->label_statement->expression;
  73                 else
  74                         return NULL;
  75         } else if (stmt->type == STMT_EXPRESSION) {
  76                 expr = stmt->expression;
  77         } else {
  78                 return NULL;
  79         }
  80         return _get_rl(expr, implied, recurse_cnt);
  81 }
  82
  83 static struct range_list *handle_expression_statement_rl(struct expression *expr, int implied, int *recurse_cnt)
  84 {
  85         return last_stmt_rl(get_expression_statement(expr), implied, recurse_cnt);
  86 }
  87
  88 static struct range_list *handle_ampersand_rl(struct expression *expr, int implied, int *recurse_cnt)
  89 {
  90         struct range_list *rl;
  91         sval_t sval;
  92
  93         if (implied == RL_EXACT || implied == RL_HARD)
  94                 return NULL;
  95         if (get_mtag_sval(expr, &sval))
  96                 return alloc_rl(sval, sval);
  97         /* FIXME: are these lines still required ? */
  98         if (get_address_rl(expr, &rl))
  99                 return rl;
 100         return alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
 101 }
 102
 103 static struct range_list *handle_negate_rl(struct expression *expr, int implied, int *recurse_cnt)
 104 {
 105         if (known_condition_true(expr->unop))
 106                 return rl_zero();
 107         if (known_condition_false(expr->unop))
 108                 return rl_one();
 109
 110         if (implied == RL_EXACT)
 111                 return NULL;
 112
 113         if (implied_condition_true(expr->unop))
 114                 return rl_zero();
 115         if (implied_condition_false(expr->unop))
 116                 return rl_one();
 117         return alloc_rl(zero, one);
 118 }
 119
 120 static struct range_list *handle_bitwise_negate(struct expression *expr, int implied, int *recurse_cnt)
 121 {
 122         struct range_list *rl;
 123         sval_t sval;
 124
 125         rl = _get_rl(expr->unop, implied, recurse_cnt);
 126         if (!rl_to_sval(rl, &sval))
 127                 return NULL;
 128         sval = sval_preop(sval, '~');
 129         sval_cast(get_type(expr->unop), sval);
 130         return alloc_rl(sval, sval);
 131 }
 132
 133 static struct range_list *handle_minus_preop(struct expression *expr, int implied, int *recurse_cnt)
 134 {
 135         struct range_list *rl;
 136         sval_t min, max;
 137
 138         rl = _get_rl(expr->unop, implied, recurse_cnt);
 139         min = sval_preop(rl_max(rl), '-');
 140         max = sval_preop(rl_min(rl), '-');
 141         return alloc_rl(min, max);
 142 }
 143
 144 static struct range_list *handle_preop_rl(struct expression *expr, int implied, int *recurse_cnt)
 145 {
 146         switch (expr->op) {
 147         case '&':
 148                 return handle_ampersand_rl(expr, implied, recurse_cnt);
 149         case '!':
 150                 return handle_negate_rl(expr, implied, recurse_cnt);
 151         case '~':
 152                 return handle_bitwise_negate(expr, implied, recurse_cnt);
 153         case '-':
 154                 return handle_minus_preop(expr, implied, recurse_cnt);
 155         case '*':
 156                 return handle_variable(expr, implied, recurse_cnt);
 157         case '(':
 158                 return handle_expression_statement_rl(expr, implied, recurse_cnt);
 159         default:
 160                 return NULL;
 161         }
 162 }
 163
 164 static struct range_list *handle_divide_rl(struct expression *expr, int implied, int *recurse_cnt)
 165 {
 166         struct range_list *left_rl, *right_rl;
 167         struct symbol *type;
 168
 169         type = get_type(expr);
 170
 171         left_rl = _get_rl(expr->left, implied, recurse_cnt);
 172         left_rl = cast_rl(type, left_rl);
 173         right_rl = _get_rl(expr->right, implied, recurse_cnt);
 174         right_rl = cast_rl(type, right_rl);
 175
 176         if (!left_rl || !right_rl)
 177                 return NULL;
 178
 179         if (implied != RL_REAL_ABSOLUTE) {
 180                 if (is_whole_rl(left_rl) || is_whole_rl(right_rl))
 181                         return NULL;
 182         }
 183
 184         return rl_binop(left_rl, '/', right_rl);
 185 }
 186
 187 static int handle_offset_subtraction(struct expression *expr)
 188 {
 189         struct expression *left, *right;
 190         struct symbol *left_sym, *right_sym;
 191         struct symbol *type;
 192         int left_offset, right_offset;
 193
 194         type = get_type(expr);
 195         if (!type || type->type != SYM_PTR)
 196                 return -1;
 197         type = get_real_base_type(type);
 198         if (!type || (type_bits(type) != 8 && (type != &void_ctype)))
 199                 return -1;
 200
 201         left = strip_expr(expr->left);
 202         right = strip_expr(expr->right);
 203
 204         if (left->type != EXPR_PREOP || left->op != '&')
 205                 return -1;
 206         left = strip_expr(left->unop);
 207
 208         left_sym = expr_to_sym(left);
 209         right_sym = expr_to_sym(right);
 210         if (!left_sym || left_sym != right_sym)
 211                 return -1;
 212
 213         left_offset = get_member_offset_from_deref(left);
 214         if (right->type == EXPR_SYMBOL)
 215                 right_offset = 0;
 216         else {
 217                 if (right->type != EXPR_PREOP || right->op != '&')
 218                         return -1;
 219                 right = strip_expr(right->unop);
 220                 right_offset = get_member_offset_from_deref(right);
 221         }
 222         if (left_offset < 0 || right_offset < 0)
 223                 return -1;
 224
 225         return left_offset - right_offset;
 226 }
 227
 228 static struct range_list *handle_subtract_rl(struct expression *expr, int implied, int *recurse_cnt)
 229 {
 230         struct symbol *type;
 231         struct range_list *left_orig, *right_orig;
 232         struct range_list *left_rl, *right_rl;
 233         sval_t max, min, tmp;
 234         int comparison;
 235         int offset;
 236
 237         type = get_type(expr);
 238
 239         offset = handle_offset_subtraction(expr);
 240         if (offset >= 0) {
 241                 tmp.type = type;
 242                 tmp.value = offset;
 243
 244                 return alloc_rl(tmp, tmp);
 245         }
 246
 247         comparison = get_comparison(expr->left, expr->right);
 248
 249         left_orig = _get_rl(expr->left, implied, recurse_cnt);
 250         left_rl = cast_rl(type, left_orig);
 251         right_orig = _get_rl(expr->right, implied, recurse_cnt);
 252         right_rl = cast_rl(type, right_orig);
 253
 254         if ((!left_rl || !right_rl) &&
 255             (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY))
 256                 return NULL;
 257
 258         if (!left_rl)
 259                 left_rl = alloc_whole_rl(type);
 260         if (!right_rl)
 261                 right_rl = alloc_whole_rl(type);
 262
 263         /* negative values complicate everything fix this later */
 264         if (sval_is_negative(rl_min(right_rl)))
 265                 return NULL;
 266         max = rl_max(left_rl);
 267         min = sval_type_min(type);
 268
 269         switch (comparison) {
 270         case '>':
 271         case SPECIAL_UNSIGNED_GT:
 272                 min = sval_type_val(type, 1);
 273                 max = rl_max(left_rl);
 274                 break;
 275         case SPECIAL_GTE:
 276         case SPECIAL_UNSIGNED_GTE:
 277                 min = sval_type_val(type, 0);
 278                 max = rl_max(left_rl);
 279                 break;
 280         case SPECIAL_EQUAL:
 281                 min = sval_type_val(type, 0);
 282                 max = sval_type_val(type, 0);
 283                 break;
 284         case '<':
 285         case SPECIAL_UNSIGNED_LT:
 286                 max = sval_type_val(type, -1);
 287                 break;
 288         case SPECIAL_LTE:
 289         case SPECIAL_UNSIGNED_LTE:
 290                 max = sval_type_val(type, 0);
 291                 break;
 292         default:
 293                 if (!left_orig || !right_orig)
 294                         return NULL;
 295                 return rl_binop(left_rl, '-', right_rl);
 296         }
 297
 298         if (!sval_binop_overflows(rl_min(left_rl), '-', rl_max(right_rl))) {
 299                 tmp = sval_binop(rl_min(left_rl), '-', rl_max(right_rl));
 300                 if (sval_cmp(tmp, min) > 0)
 301                         min = tmp;
 302         }
 303
 304         if (!sval_is_max(rl_max(left_rl))) {
 305                 tmp = sval_binop(rl_max(left_rl), '-', rl_min(right_rl));
 306                 if (sval_cmp(tmp, max) < 0)
 307                         max = tmp;
 308         }
 309
 310         if (sval_is_min(min) && sval_is_max(max))
 311                 return NULL;
 312
 313         return cast_rl(type, alloc_rl(min, max));
 314 }
 315
 316 static struct range_list *handle_mod_rl(struct expression *expr, int implied, int *recurse_cnt)
 317 {
 318         struct range_list *rl;
 319         sval_t left, right, sval;
 320
 321         if (implied == RL_EXACT) {
 322                 if (!get_implied_value(expr->right, &right))
 323                         return NULL;
 324                 if (!get_implied_value(expr->left, &left))
 325                         return NULL;
 326                 sval = sval_binop(left, '%', right);
 327                 return alloc_rl(sval, sval);
 328         }
 329         /* if we can't figure out the right side it's probably hopeless */
 330         if (!get_implied_value_internal(expr->right, &right, recurse_cnt))
 331                 return NULL;
 332
 333         right = sval_cast(get_type(expr), right);
 334         right.value--;
 335
 336         rl = _get_rl(expr->left, implied, recurse_cnt);
 337         if (rl && rl_max(rl).uvalue < right.uvalue)
 338                 right.uvalue = rl_max(rl).uvalue;
 339
 340         return alloc_rl(sval_cast(right.type, zero), right);
 341 }
 342
 343 static sval_t sval_lowest_set_bit(sval_t sval)
 344 {
 345         int i;
 346         int found = 0;
 347
 348         for (i = 0; i < 64; i++) {
 349                 if (sval.uvalue & 1ULL << i) {
 350                         if (!found++)
 351                                 continue;
 352                         sval.uvalue &= ~(1ULL << i);
 353                 }
 354         }
 355         return sval;
 356 }
 357
 358 static struct range_list *handle_bitwise_AND(struct expression *expr, int implied, int *recurse_cnt)
 359 {
 360         struct symbol *type;
 361         struct range_list *left_rl, *right_rl;
 362         sval_t known;
 363         int new_recurse;
 364
 365         if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE)
 366                 return NULL;
 367
 368         type = get_type(expr);
 369
 370         if (get_implied_value_internal(expr->left, &known, recurse_cnt)) {
 371                 sval_t min;
 372
 373                 min = sval_lowest_set_bit(known);
 374                 left_rl = alloc_rl(min, known);
 375                 left_rl = cast_rl(type, left_rl);
 376                 add_range(&left_rl, sval_type_val(type, 0), sval_type_val(type, 0));
 377         } else {
 378                 left_rl = _get_rl(expr->left, implied, recurse_cnt);
 379                 if (left_rl) {
 380                         left_rl = cast_rl(type, left_rl);
 381                         left_rl = alloc_rl(sval_type_val(type, 0), rl_max(left_rl));
 382                 } else {
 383                         if (implied == RL_HARD)
 384                                 return NULL;
 385                         left_rl = alloc_whole_rl(type);
 386                 }
 387         }
 388
 389         new_recurse = *recurse_cnt;
 390         if (*recurse_cnt >= 200)
 391                 new_recurse = 100;  /* Let's try super hard to get the mask */
 392         if (get_implied_value_internal(expr->right, &known, &new_recurse)) {
 393                 sval_t min, left_max, mod;
 394
 395                 *recurse_cnt = new_recurse;
 396
 397                 min = sval_lowest_set_bit(known);
 398                 right_rl = alloc_rl(min, known);
 399                 right_rl = cast_rl(type, right_rl);
 400                 add_range(&right_rl, sval_type_val(type, 0), sval_type_val(type, 0));
 401
 402                 if (min.value != 0) {
 403                         left_max = rl_max(left_rl);
 404                         mod = sval_binop(left_max, '%', min);
 405                         if (mod.value) {
 406                                 left_max = sval_binop(left_max, '-', mod);
 407                                 left_max.value++;
 408                                 if (left_max.value > 0 && sval_cmp(left_max, rl_max(left_rl)) < 0)
 409                                         left_rl = remove_range(left_rl, left_max, rl_max(left_rl));
 410                         }
 411                 }
 412         } else {
 413                 right_rl = _get_rl(expr->right, implied, recurse_cnt);
 414                 if (right_rl) {
 415                         right_rl = cast_rl(type, right_rl);
 416                         right_rl = alloc_rl(sval_type_val(type, 0), rl_max(right_rl));
 417                 } else {
 418                         if (implied == RL_HARD)
 419                                 return NULL;
 420                         right_rl = alloc_whole_rl(type);
 421                 }
 422         }
 423
 424         return rl_intersection(left_rl, right_rl);
 425 }
 426
 427 static struct range_list *use_rl_binop(struct expression *expr, int implied, int *recurse_cnt)
 428 {
 429         struct symbol *type;
 430         struct range_list *left_rl, *right_rl;
 431
 432         if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE)
 433                 return NULL;
 434
 435         type = get_type(expr);
 436
 437         get_absolute_rl_internal(expr->left, &left_rl, recurse_cnt);
 438         get_absolute_rl_internal(expr->right, &right_rl, recurse_cnt);
 439         left_rl = cast_rl(type, left_rl);
 440         right_rl = cast_rl(type, right_rl);
 441         if (!left_rl || !right_rl)
 442                 return NULL;
 443
 444         return rl_binop(left_rl, expr->op, right_rl);
 445 }
 446
 447 static struct range_list *handle_right_shift(struct expression *expr, int implied, int *recurse_cnt)
 448 {
 449         struct range_list *left_rl;
 450         sval_t right;
 451         sval_t min, max;
 452
 453         if (implied == RL_EXACT || implied == RL_HARD)
 454                 return NULL;
 455
 456         left_rl = _get_rl(expr->left, implied, recurse_cnt);
 457         if (left_rl) {
 458                 max = rl_max(left_rl);
 459                 min = rl_min(left_rl);
 460         } else {
 461                 if (implied == RL_FUZZY)
 462                         return NULL;
 463                 max = sval_type_max(get_type(expr->left));
 464                 min = sval_type_val(get_type(expr->left), 0);
 465         }
 466
 467         if (get_implied_value_internal(expr->right, &right, recurse_cnt)) {
 468                 min = sval_binop(min, SPECIAL_RIGHTSHIFT, right);
 469                 max = sval_binop(max, SPECIAL_RIGHTSHIFT, right);
 470         } else if (!sval_is_negative(min)) {
 471                 min.value = 0;
 472                 max = sval_type_max(max.type);
 473         } else {
 474                 return NULL;
 475         }
 476
 477         return alloc_rl(min, max);
 478 }
 479
 480 static struct range_list *handle_left_shift(struct expression *expr, int implied, int *recurse_cnt)
 481 {
 482         struct range_list *left_rl, *res;
 483         sval_t right;
 484         sval_t min, max;
 485         int add_zero = 0;
 486
 487         if (implied == RL_EXACT || implied == RL_HARD)
 488                 return NULL;
 489         /* this is hopeless without the right side */
 490         if (!get_implied_value_internal(expr->right, &right, recurse_cnt))
 491                 return NULL;
 492         left_rl = _get_rl(expr->left, implied, recurse_cnt);
 493         if (left_rl) {
 494                 max = rl_max(left_rl);
 495                 min = rl_min(left_rl);
 496                 if (min.value == 0) {
 497                         min.value = 1;
 498                         add_zero = 1;
 499                 }
 500         } else {
 501                 if (implied == RL_FUZZY)
 502                         return NULL;
 503                 max = sval_type_max(get_type(expr->left));
 504                 min = sval_type_val(get_type(expr->left), 1);
 505                 add_zero = 1;
 506         }
 507
 508         max = sval_binop(max, SPECIAL_LEFTSHIFT, right);
 509         min = sval_binop(min, SPECIAL_LEFTSHIFT, right);
 510         res = alloc_rl(min, max);
 511         if (add_zero)
 512                 res = rl_union(res, rl_zero());
 513         return res;
 514 }
 515
 516 static struct range_list *handle_known_binop(struct expression *expr)
 517 {
 518         sval_t left, right;
 519
 520         if (!get_value(expr->left, &left))
 521                 return NULL;
 522         if (!get_value(expr->right, &right))
 523                 return NULL;
 524         left = sval_binop(left, expr->op, right);
 525         return alloc_rl(left, left);
 526 }
 527
 528 static int has_actual_ranges(struct range_list *rl)
 529 {
 530         struct data_range *tmp;
 531
 532         FOR_EACH_PTR(rl, tmp) {
 533                 if (sval_cmp(tmp->min, tmp->max) != 0)
 534                         return 1;
 535         } END_FOR_EACH_PTR(tmp);
 536         return 0;
 537 }
 538
 539 static struct range_list *handle_implied_binop(struct range_list *left_rl, int op, struct range_list *right_rl)
 540 {
 541         struct range_list *res_rl;
 542         struct data_range *left_drange, *right_drange;
 543         sval_t res;
 544
 545         if (!left_rl || !right_rl)
 546                 return NULL;
 547         if (has_actual_ranges(left_rl))
 548                 return NULL;
 549         if (has_actual_ranges(right_rl))
 550                 return NULL;
 551
 552         if (ptr_list_size((struct ptr_list *)left_rl) * ptr_list_size((struct ptr_list *)right_rl) > 20)
 553                 return NULL;
 554
 555         res_rl = NULL;
 556
 557         FOR_EACH_PTR(left_rl, left_drange) {
 558                 FOR_EACH_PTR(right_rl, right_drange) {
 559                         if ((op == '%' || op == '/') &&
 560                             right_drange->min.value == 0)
 561                                 return NULL;
 562                         res = sval_binop(left_drange->min, op, right_drange->min);
 563                         add_range(&res_rl, res, res);
 564                 } END_FOR_EACH_PTR(right_drange);
 565         } END_FOR_EACH_PTR(left_drange);
 566
 567         return res_rl;
 568 }
 569
 570 static struct range_list *handle_binop_rl(struct expression *expr, int implied, int *recurse_cnt)
 571 {
 572         struct smatch_state *state;
 573         struct symbol *type;
 574         struct range_list *left_rl, *right_rl, *rl;
 575         sval_t min, max;
 576
 577         rl = handle_known_binop(expr);
 578         if (rl)
 579                 return rl;
 580         if (implied == RL_EXACT)
 581                 return NULL;
 582
 583         if (custom_handle_variable) {
 584                 rl = custom_handle_variable(expr);
 585                 if (rl)
 586                         return rl;
 587         }
 588
 589         state = get_extra_state(expr);
 590         if (state && !is_whole_rl(estate_rl(state))) {
 591                 if (implied != RL_HARD || estate_has_hard_max(state))
 592                         return clone_rl(estate_rl(state));
 593         }
 594
 595         type = get_type(expr);
 596         left_rl = _get_rl(expr->left, implied, recurse_cnt);
 597         left_rl = cast_rl(type, left_rl);
 598         right_rl = _get_rl(expr->right, implied, recurse_cnt);
 599         right_rl = cast_rl(type, right_rl);
 600
 601         if (!left_rl && !right_rl)
 602                 return NULL;
 603
 604         rl = handle_implied_binop(left_rl, expr->op, right_rl);
 605         if (rl)
 606                 return rl;
 607
 608         switch (expr->op) {
 609         case '%':
 610                 return handle_mod_rl(expr, implied, recurse_cnt);
 611         case '&':
 612                 return handle_bitwise_AND(expr, implied, recurse_cnt);
 613         case '|':
 614         case '^':
 615                 return use_rl_binop(expr, implied, recurse_cnt);
 616         case SPECIAL_RIGHTSHIFT:
 617                 return handle_right_shift(expr, implied, recurse_cnt);
 618         case SPECIAL_LEFTSHIFT:
 619                 return handle_left_shift(expr, implied, recurse_cnt);
 620         case '-':
 621                 return handle_subtract_rl(expr, implied, recurse_cnt);
 622         case '/':
 623                 return handle_divide_rl(expr, implied, recurse_cnt);
 624         }
 625
 626         if (!left_rl || !right_rl)
 627                 return NULL;
 628
 629         if (sval_binop_overflows(rl_min(left_rl), expr->op, rl_min(right_rl)))
 630                 return NULL;
 631         if (sval_binop_overflows(rl_max(left_rl), expr->op, rl_max(right_rl)))
 632                 return NULL;
 633
 634         min = sval_binop(rl_min(left_rl), expr->op, rl_min(right_rl));
 635         max = sval_binop(rl_max(left_rl), expr->op, rl_max(right_rl));
 636
 637         return alloc_rl(min, max);
 638 }
 639
 640 static int do_comparison(struct expression *expr)
 641 {
 642         struct range_list *left_ranges = NULL;
 643         struct range_list *right_ranges = NULL;
 644         int poss_true, poss_false;
 645         struct symbol *type;
 646
 647         type = get_type(expr);
 648         get_absolute_rl(expr->left, &left_ranges);
 649         get_absolute_rl(expr->right, &right_ranges);
 650
 651         left_ranges = cast_rl(type, left_ranges);
 652         right_ranges = cast_rl(type, right_ranges);
 653
 654         poss_true = possibly_true_rl(left_ranges, expr->op, right_ranges);
 655         poss_false = possibly_false_rl(left_ranges, expr->op, right_ranges);
 656
 657         if (!poss_true && !poss_false)
 658                 return 0x0;
 659         if (poss_true && !poss_false)
 660                 return 0x1;
 661         if (!poss_true && poss_false)
 662                 return 0x2;
 663         return 0x3;
 664 }
 665
 666 static struct range_list *handle_comparison_rl(struct expression *expr, int implied, int *recurse_cnt)
 667 {
 668         sval_t left, right;
 669         int res;
 670
 671         if (expr->op == SPECIAL_EQUAL && expr->left->type == EXPR_TYPE) {
 672                 struct symbol *left, *right;
 673
 674                 left = get_real_base_type(expr->left->symbol);
 675                 right = get_real_base_type(expr->left->symbol);
 676                 if (left == right)
 677                         return rl_one();
 678                 return rl_zero();
 679         }
 680
 681         if (get_value(expr->left, &left) && get_value(expr->right, &right)) {
 682                 struct data_range tmp_left, tmp_right;
 683
 684                 tmp_left.min = left;
 685                 tmp_left.max = left;
 686                 tmp_right.min = right;
 687                 tmp_right.max = right;
 688                 if (true_comparison_range(&tmp_left, expr->op, &tmp_right))
 689                         return rl_one();
 690                 return rl_zero();
 691         }
 692
 693         if (implied == RL_EXACT)
 694                 return NULL;
 695
 696         res = do_comparison(expr);
 697         if (res == 1)
 698                 return rl_one();
 699         if (res == 2)
 700                 return rl_zero();
 701
 702         return alloc_rl(zero, one);
 703 }
 704
 705 static struct range_list *handle_logical_rl(struct expression *expr, int implied, int *recurse_cnt)
 706 {
 707         sval_t left, right;
 708         int left_known = 0;
 709         int right_known = 0;
 710
 711         if (implied == RL_EXACT) {
 712                 if (get_value(expr->left, &left))
 713                         left_known = 1;
 714                 if (get_value(expr->right, &right))
 715                         right_known = 1;
 716         } else {
 717                 if (get_implied_value_internal(expr->left, &left, recurse_cnt))
 718                         left_known = 1;
 719                 if (get_implied_value_internal(expr->right, &right, recurse_cnt))
 720                         right_known = 1;
 721         }
 722
 723         switch (expr->op) {
 724         case SPECIAL_LOGICAL_OR:
 725                 if (left_known && left.value)
 726                         return rl_one();
 727                 if (right_known && right.value)
 728                         return rl_one();
 729                 if (left_known && right_known)
 730                         return rl_zero();
 731                 break;
 732         case SPECIAL_LOGICAL_AND:
 733                 if (left_known && right_known) {
 734                         if (left.value && right.value)
 735                                 return rl_one();
 736                         return rl_zero();
 737                 }
 738                 break;
 739         default:
 740                 return NULL;
 741         }
 742
 743         if (implied == RL_EXACT)
 744                 return NULL;
 745
 746         return alloc_rl(zero, one);
 747 }
 748
 749 static struct range_list *handle_conditional_rl(struct expression *expr, int implied, int *recurse_cnt)
 750 {
 751         struct range_list *true_rl, *false_rl;
 752         struct symbol *type;
 753         int final_pass_orig = final_pass;
 754
 755         if (known_condition_true(expr->conditional))
 756                 return _get_rl(expr->cond_true, implied, recurse_cnt);
 757         if (known_condition_false(expr->conditional))
 758                 return _get_rl(expr->cond_false, implied, recurse_cnt);
 759
 760         if (implied == RL_EXACT)
 761                 return NULL;
 762
 763         if (implied_condition_true(expr->conditional))
 764                 return _get_rl(expr->cond_true, implied, recurse_cnt);
 765         if (implied_condition_false(expr->conditional))
 766                 return _get_rl(expr->cond_false, implied, recurse_cnt);
 767
 768
 769         /* this becomes a problem with deeply nested conditional statements */
 770         if (low_on_memory())
 771                 return NULL;
 772
 773         type = get_type(expr);
 774
 775         __push_fake_cur_stree();
 776         final_pass = 0;
 777         __split_whole_condition(expr->conditional);
 778         true_rl = _get_rl(expr->cond_true, implied, recurse_cnt);
 779         __push_true_states();
 780         __use_false_states();
 781         false_rl = _get_rl(expr->cond_false, implied, recurse_cnt);
 782         __merge_true_states();
 783         __free_fake_cur_stree();
 784         final_pass = final_pass_orig;
 785
 786         if (!true_rl || !false_rl)
 787                 return NULL;
 788         true_rl = cast_rl(type, true_rl);
 789         false_rl = cast_rl(type, false_rl);
 790
 791         return rl_union(true_rl, false_rl);
 792 }
 793
 794 static int get_fuzzy_max_helper(struct expression *expr, sval_t *max)
 795 {
 796         struct smatch_state *state;
 797         sval_t sval;
 798
 799         if (get_hard_max(expr, &sval)) {
 800                 *max = sval;
 801                 return 1;
 802         }
 803
 804         state = get_extra_state(expr);
 805         if (!state || !estate_has_fuzzy_max(state))
 806                 return 0;
 807         *max = sval_cast(get_type(expr), estate_get_fuzzy_max(state));
 808         return 1;
 809 }
 810
 811 static int get_fuzzy_min_helper(struct expression *expr, sval_t *min)
 812 {
 813         struct smatch_state *state;
 814         sval_t sval;
 815
 816         state = get_extra_state(expr);
 817         if (!state || !estate_rl(state))
 818                 return 0;
 819
 820         sval = estate_min(state);
 821         if (sval_is_negative(sval) && sval_is_min(sval))
 822                 return 0;
 823
 824         if (sval_is_max(sval))
 825                 return 0;
 826
 827         *min = sval_cast(get_type(expr), sval);
 828         return 1;
 829 }
 830
 831 int get_const_value(struct expression *expr, sval_t *sval)
 832 {
 833         struct symbol *sym;
 834         sval_t right;
 835
 836         if (expr->type != EXPR_SYMBOL || !expr->symbol)
 837                 return 0;
 838         sym = expr->symbol;
 839         if (!(sym->ctype.modifiers & MOD_CONST))
 840                 return 0;
 841         if (get_value(sym->initializer, &right)) {
 842                 *sval = sval_cast(get_type(expr), right);
 843                 return 1;
 844         }
 845         return 0;
 846 }
 847
 848 struct range_list *var_to_absolute_rl(struct expression *expr)
 849 {
 850         struct smatch_state *state;
 851         struct range_list *rl;
 852
 853         state = get_extra_state(expr);
 854         if (!state || is_whole_rl(estate_rl(state))) {
 855                 state = get_real_absolute_state(expr);
 856                 if (state && state->data && !estate_is_whole(state))
 857                         return clone_rl(estate_rl(state));
 858                 if (get_local_rl(expr, &rl) && !is_whole_rl(rl))
 859                         return rl;
 860                 if (get_db_data_rl(expr, &rl))
 861                         return rl;
 862                 if (get_db_type_rl(expr, &rl) && !is_whole_rl(rl))
 863                         return rl;
 864                 return alloc_whole_rl(get_type(expr));
 865         }
 866         /* err on the side of saying things are possible */
 867         if (!estate_rl(state))
 868                 return alloc_whole_rl(get_type(expr));
 869         return clone_rl(estate_rl(state));
 870 }
 871
 872 static struct range_list *handle_variable(struct expression *expr, int implied, int *recurse_cnt)
 873 {
 874         struct smatch_state *state;
 875         struct range_list *rl;
 876         sval_t sval, min, max;
 877         struct symbol *type;
 878
 879         if (get_const_value(expr, &sval))
 880                 return alloc_rl(sval, sval);
 881
 882         if (custom_handle_variable) {
 883                 rl = custom_handle_variable(expr);
 884                 if (!rl)
 885                         return var_to_absolute_rl(expr);
 886                 return rl;
 887         }
 888
 889         if (implied == RL_EXACT)
 890                 return NULL;
 891
 892         if (get_mtag_sval(expr, &sval))
 893                 return alloc_rl(sval, sval);
 894
 895         type = get_type(expr);
 896         if (type && type->type == SYM_FN)
 897                 return alloc_rl(fn_ptr_min, fn_ptr_max);
 898
 899         switch (implied) {
 900         case RL_HARD:
 901         case RL_IMPLIED:
 902         case RL_ABSOLUTE:
 903                 state = get_extra_state(expr);
 904                 if (!state || !state->data) {
 905                         if (implied == RL_HARD)
 906                                 return NULL;
 907                         if (get_local_rl(expr, &rl))
 908                                 return rl;
 909                         if (get_db_data_rl(expr, &rl))
 910                                 return rl;
 911                         if (get_db_type_rl(expr, &rl))
 912                                 return rl;
 913                         return NULL;
 914                 }
 915                 if (implied == RL_HARD && !estate_has_hard_max(state))
 916                         return NULL;
 917                 return clone_rl(estate_rl(state));
 918         case RL_REAL_ABSOLUTE: {
 919                 struct smatch_state *abs_state;
 920
 921                 state = get_extra_state(expr);
 922                 abs_state = get_real_absolute_state(expr);
 923
 924                 if (estate_rl(state) && estate_rl(abs_state)) {
 925                         return clone_rl(rl_intersection(estate_rl(state),
 926                                                         estate_rl(abs_state)));
 927                 } else if (estate_rl(state)) {
 928                         return clone_rl(estate_rl(state));
 929                 } else if (estate_is_empty(state)) {
 930                         /*
 931                          * FIXME: we don't handle empty extra states correctly.
 932                          *
 933                          * The real abs rl is supposed to be filtered by the
 934                          * extra state if there is one.  We don't bother keeping
 935                          * the abs state in sync all the time because we know it
 936                          * will be filtered later.
 937                          *
 938                          * It's not totally obvious to me how they should be
 939                          * handled.  Perhaps we should take the whole rl and
 940                          * filter by the imaginary states.  Perhaps we should
 941                          * just go with the empty state.
 942                          *
 943                          * Anyway what we currently do is return NULL here and
 944                          * that gets translated into the whole range in
 945                          * get_real_absolute_rl().
 946                          *
 947                          */
 948                         return NULL;
 949                 } else if (estate_rl(abs_state)) {
 950                         return clone_rl(estate_rl(abs_state));
 951                 }
 952
 953                 if (get_local_rl(expr, &rl))
 954                         return rl;
 955                 if (get_db_data_rl(expr, &rl))
 956                         return rl;
 957                 if (get_db_type_rl(expr, &rl))
 958                         return rl;
 959                 return NULL;
 960         }
 961         case RL_FUZZY:
 962                 if (!get_fuzzy_min_helper(expr, &min))
 963                         min = sval_type_min(get_type(expr));
 964                 if (!get_fuzzy_max_helper(expr, &max))
 965                         return NULL;
 966                 /* fuzzy ranges are often inverted */
 967                 if (sval_cmp(min, max) > 0) {
 968                         sval = min;
 969                         min = max;
 970                         max = sval;
 971                 }
 972                 return alloc_rl(min, max);
 973         }
 974         return NULL;
 975 }
 976
 977 static sval_t handle_sizeof(struct expression *expr)
 978 {
 979         struct symbol *sym;
 980         sval_t ret;
 981
 982         ret = sval_blank(expr);
 983         sym = expr->cast_type;
 984         if (!sym) {
 985                 sym = evaluate_expression(expr->cast_expression);
 986                 if (!sym) {
 987                         __silence_warnings_for_stmt = true;
 988                         sym = &int_ctype;
 989                 }
 990 #if 0
 991                 /*
 992                  * Expressions of restricted types will possibly get
 993                  * promoted - check that here.  I'm not sure how this works,
 994                  * the problem is that sizeof(le16) shouldn't be promoted and
 995                  * the original code did that...  Let's if zero this out and
 996                  * see what breaks.
 997                  */
 998
 999                 if (is_restricted_type(sym)) {
1000                         if (type_bits(sym) < bits_in_int)
1001                                 sym = &int_ctype;
1002                 }
1003 #endif
1004                 if (is_fouled_type(sym))
1005                         sym = &int_ctype;
1006         }
1007         examine_symbol_type(sym);
1008
1009         ret.type = size_t_ctype;
1010         if (type_bits(sym) <= 0) /* sizeof(void) */ {
1011                 if (get_real_base_type(sym) == &void_ctype)
1012                         ret.value = 1;
1013                 else
1014                         ret.value = 0;
1015         } else
1016                 ret.value = type_bytes(sym);
1017
1018         return ret;
1019 }
1020
1021 static struct range_list *handle_strlen(struct expression *expr, int implied, int *recurse_cnt)
1022 {
1023         struct range_list *rl;
1024         struct expression *arg;
1025         sval_t sval = { .type = &ulong_ctype };
1026
1027         if (implied == RL_EXACT)
1028                 return NULL;
1029
1030         arg = get_argument_from_call_expr(expr->args, 0);
1031         if (!arg)
1032                 return NULL;
1033         if (arg->type == EXPR_STRING) {
1034                 sval.value = arg->string->length - 1;
1035                 return alloc_rl(sval, sval);
1036         }
1037
1038         if (implied == RL_HARD || implied == RL_FUZZY)
1039                 return NULL;
1040
1041         if (get_implied_return(expr, &rl))
1042                 return rl;
1043
1044         return NULL;
1045 }
1046
1047 static struct range_list *handle_builtin_constant_p(struct expression *expr, int implied, int *recurse_cnt)
1048 {
1049         struct expression *arg;
1050         struct range_list *rl;
1051         sval_t sval;
1052
1053         arg = get_argument_from_call_expr(expr->args, 0);
1054         rl = _get_rl(arg, RL_EXACT, recurse_cnt);
1055         if (rl_to_sval(rl, &sval))
1056                 return rl_one();
1057         return rl_zero();
1058 }
1059
1060 static struct range_list *handle__builtin_choose_expr(struct expression *expr, int implied, int *recurse_cnt)
1061 {
1062         struct expression *const_expr, *expr1, *expr2;
1063         sval_t sval;
1064
1065         const_expr = get_argument_from_call_expr(expr->args, 0);
1066         expr1 = get_argument_from_call_expr(expr->args, 1);
1067         expr2 = get_argument_from_call_expr(expr->args, 2);
1068
1069         if (!get_value(const_expr, &sval) || !expr1 || !expr2)
1070                 return NULL;
1071         if (sval.value)
1072                 return _get_rl(expr1, implied, recurse_cnt);
1073         return _get_rl(expr2, implied, recurse_cnt);
1074 }
1075
1076 static struct range_list *handle_call_rl(struct expression *expr, int implied, int *recurse_cnt)
1077 {
1078         struct range_list *rl;
1079
1080         if (sym_name_is("__builtin_constant_p", expr->fn))
1081                 return handle_builtin_constant_p(expr, implied, recurse_cnt);
1082
1083         if (sym_name_is("__builtin_choose_expr", expr->fn))
1084                 return handle__builtin_choose_expr(expr, implied, recurse_cnt);
1085
1086         if (sym_name_is("__builtin_expect", expr->fn) ||
1087             sym_name_is("__builtin_bswap16", expr->fn) ||
1088             sym_name_is("__builtin_bswap32", expr->fn) ||
1089             sym_name_is("__builtin_bswap64", expr->fn)) {
1090                 struct expression *arg;
1091
1092                 arg = get_argument_from_call_expr(expr->args, 0);
1093                 return _get_rl(arg, implied, recurse_cnt);
1094         }
1095
1096         if (sym_name_is("strlen", expr->fn))
1097                 return handle_strlen(expr, implied, recurse_cnt);
1098
1099         if (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY)
1100                 return NULL;
1101
1102         if (custom_handle_variable) {
1103                 rl = custom_handle_variable(expr);
1104                 if (rl)
1105                         return rl;
1106         }
1107
1108         if (get_implied_return(expr, &rl))
1109                 return rl;
1110         return db_return_vals(expr);
1111 }
1112
1113 static struct range_list *handle_cast(struct expression *expr, int implied, int *recurse_cnt)
1114 {
1115         struct range_list *rl;
1116         struct symbol *type;
1117
1118         type = get_type(expr);
1119         rl = _get_rl(expr->cast_expression, implied, recurse_cnt);
1120         if (rl)
1121                 return cast_rl(type, rl);
1122         if (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE)
1123                 return alloc_whole_rl(type);
1124         if (implied == RL_IMPLIED && type &&
1125             type_bits(type) > 0 && type_bits(type) < 32)
1126                 return alloc_whole_rl(type);
1127         return NULL;
1128 }
1129
1130 static struct range_list *_get_rl(struct expression *expr, int implied, int *recurse_cnt)
1131 {
1132         struct range_list *rl;
1133         struct symbol *type;
1134         sval_t sval;
1135
1136         type = get_type(expr);
1137         expr = strip_parens(expr);
1138         if (!expr)
1139                 return NULL;
1140
1141         if (++(*recurse_cnt) >= 200)
1142                 return NULL;
1143
1144         switch(expr->type) {
1145         case EXPR_CAST:
1146         case EXPR_FORCE_CAST:
1147         case EXPR_IMPLIED_CAST:
1148                 rl = handle_cast(expr, implied, recurse_cnt);
1149                 goto out_cast;
1150         }
1151
1152         expr = strip_expr(expr);
1153         if (!expr)
1154                 return NULL;
1155
1156         switch (expr->type) {
1157         case EXPR_VALUE:
1158                 sval = sval_from_val(expr, expr->value);
1159                 rl = alloc_rl(sval, sval);
1160                 break;
1161         case EXPR_PREOP:
1162                 rl = handle_preop_rl(expr, implied, recurse_cnt);
1163                 break;
1164         case EXPR_POSTOP:
1165                 rl = _get_rl(expr->unop, implied, recurse_cnt);
1166                 break;
1167         case EXPR_BINOP:
1168                 rl = handle_binop_rl(expr, implied, recurse_cnt);
1169                 break;
1170         case EXPR_COMPARE:
1171                 rl = handle_comparison_rl(expr, implied, recurse_cnt);
1172                 break;
1173         case EXPR_LOGICAL:
1174                 rl = handle_logical_rl(expr, implied, recurse_cnt);
1175                 break;
1176         case EXPR_PTRSIZEOF:
1177         case EXPR_SIZEOF:
1178                 sval = handle_sizeof(expr);
1179                 rl = alloc_rl(sval, sval);
1180                 break;
1181         case EXPR_SELECT:
1182         case EXPR_CONDITIONAL:
1183                 rl = handle_conditional_rl(expr, implied, recurse_cnt);
1184                 break;
1185         case EXPR_CALL:
1186                 rl = handle_call_rl(expr, implied, recurse_cnt);
1187                 break;
1188         default:
1189                 rl = handle_variable(expr, implied, recurse_cnt);
1190         }
1191
1192 out_cast:
1193         if (rl)
1194                 return rl;
1195         if (type && (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE))
1196                 return alloc_whole_rl(type);
1197         return NULL;
1198 }
1199
1200 struct {
1201         struct expression *expr;
1202         struct range_list *rl;
1203 } cached_results[24];
1204 static int cache_idx;
1205
1206 void clear_math_cache(void)
1207 {
1208         memset(cached_results, 0, sizeof(cached_results));
1209 }
1210
1211 /* returns 1 if it can get a value literal or else returns 0 */
1212 int get_value(struct expression *expr, sval_t *sval)
1213 {
1214         struct range_list *(*orig_custom_fn)(struct expression *expr);
1215         struct range_list *rl;
1216         int recurse_cnt = 0;
1217         sval_t tmp;
1218         int i;
1219
1220         /*
1221          * This only handles RL_EXACT because other expr statements can be
1222          * different at different points.  Like the list iterator, for example.
1223          */
1224         for (i = 0; i < ARRAY_SIZE(cached_results); i++) {
1225                 if (expr == cached_results[i].expr)
1226                         return rl_to_sval(cached_results[i].rl, sval);
1227         }
1228
1229         orig_custom_fn = custom_handle_variable;
1230         custom_handle_variable = NULL;
1231         rl = _get_rl(expr, RL_EXACT, &recurse_cnt);
1232         if (!rl_to_sval(rl, &tmp))
1233                 rl = NULL;
1234         custom_handle_variable = orig_custom_fn;
1235
1236         cached_results[cache_idx].expr = expr;
1237         cached_results[cache_idx].rl = rl;
1238         cache_idx = (cache_idx + 1) % ARRAY_SIZE(cached_results);
1239
1240         if (!rl)
1241                 return 0;
1242
1243         *sval = tmp;
1244         return 1;
1245 }
1246
1247 static int get_implied_value_internal(struct expression *expr, sval_t *sval, int *recurse_cnt)
1248 {
1249         struct range_list *rl;
1250
1251         rl =  _get_rl(expr, RL_IMPLIED, recurse_cnt);
1252         if (!rl_to_sval(rl, sval))
1253                 return 0;
1254         return 1;
1255 }
1256
1257 int get_implied_value(struct expression *expr, sval_t *sval)
1258 {
1259         struct range_list *rl;
1260         int recurse_cnt = 0;
1261
1262         rl =  _get_rl(expr, RL_IMPLIED, &recurse_cnt);
1263         if (!rl_to_sval(rl, sval))
1264                 return 0;
1265         return 1;
1266 }
1267
1268 int get_implied_min(struct expression *expr, sval_t *sval)
1269 {
1270         struct range_list *rl;
1271         int recurse_cnt = 0;
1272
1273         rl =  _get_rl(expr, RL_IMPLIED, &recurse_cnt);
1274         if (!rl)
1275                 return 0;
1276         *sval = rl_min(rl);
1277         return 1;
1278 }
1279
1280 int get_implied_max(struct expression *expr, sval_t *sval)
1281 {
1282         struct range_list *rl;
1283         int recurse_cnt = 0;
1284
1285         rl =  _get_rl(expr, RL_IMPLIED, &recurse_cnt);
1286         if (!rl)
1287                 return 0;
1288         *sval = rl_max(rl);
1289         return 1;
1290 }
1291
1292 int get_implied_rl(struct expression *expr, struct range_list **rl)
1293 {
1294         int recurse_cnt = 0;
1295
1296         *rl = _get_rl(expr, RL_IMPLIED, &recurse_cnt);
1297         if (*rl)
1298                 return 1;
1299         return 0;
1300 }
1301
1302 static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt)
1303 {
1304         *rl = _get_rl(expr, RL_ABSOLUTE, recurse_cnt);
1305         if (!*rl)
1306                 *rl = alloc_whole_rl(get_type(expr));
1307         return 1;
1308 }
1309
1310 int get_absolute_rl(struct expression *expr, struct range_list **rl)
1311 {
1312         int recurse_cnt = 0;
1313
1314         *rl = _get_rl(expr, RL_ABSOLUTE, &recurse_cnt);
1315         if (!*rl)
1316                 *rl = alloc_whole_rl(get_type(expr));
1317         return 1;
1318 }
1319
1320 int get_real_absolute_rl(struct expression *expr, struct range_list **rl)
1321 {
1322         int recurse_cnt = 0;
1323
1324         *rl = _get_rl(expr, RL_REAL_ABSOLUTE, &recurse_cnt);
1325         if (!*rl)
1326                 *rl = alloc_whole_rl(get_type(expr));
1327         return 1;
1328 }
1329
1330 int custom_get_absolute_rl(struct expression *expr,
1331                            struct range_list *(*fn)(struct expression *expr),
1332                            struct range_list **rl)
1333 {
1334         int recurse_cnt = 0;
1335
1336         *rl = NULL;
1337         custom_handle_variable = fn;
1338         *rl = _get_rl(expr, RL_REAL_ABSOLUTE, &recurse_cnt);
1339         custom_handle_variable = NULL;
1340         return 1;
1341 }
1342
1343 int get_implied_rl_var_sym(const char *var, struct symbol *sym, struct range_list **rl)
1344 {
1345         struct smatch_state *state;
1346
1347         state = get_state(SMATCH_EXTRA, var, sym);
1348         *rl = estate_rl(state);
1349         if (*rl)
1350                 return 1;
1351         return 0;
1352 }
1353
1354 int get_hard_max(struct expression *expr, sval_t *sval)
1355 {
1356         struct range_list *rl;
1357         int recurse_cnt = 0;
1358
1359         rl =  _get_rl(expr, RL_HARD, &recurse_cnt);
1360         if (!rl)
1361                 return 0;
1362         *sval = rl_max(rl);
1363         return 1;
1364 }
1365
1366 int get_fuzzy_min(struct expression *expr, sval_t *sval)
1367 {
1368         struct range_list *rl;
1369         sval_t tmp;
1370         int recurse_cnt = 0;
1371
1372         rl =  _get_rl(expr, RL_FUZZY, &recurse_cnt);
1373         if (!rl)
1374                 return 0;
1375         tmp = rl_min(rl);
1376         if (sval_is_negative(tmp) && sval_is_min(tmp))
1377                 return 0;
1378         *sval = tmp;
1379         return 1;
1380 }
1381
1382 int get_fuzzy_max(struct expression *expr, sval_t *sval)
1383 {
1384         struct range_list *rl;
1385         sval_t max;
1386         int recurse_cnt = 0;
1387
1388         rl =  _get_rl(expr, RL_FUZZY, &recurse_cnt);
1389         if (!rl)
1390                 return 0;
1391         max = rl_max(rl);
1392         if (max.uvalue > INT_MAX - 10000)
1393                 return 0;
1394         *sval = max;
1395         return 1;
1396 }
1397
1398 int get_absolute_min(struct expression *expr, sval_t *sval)
1399 {
1400         struct range_list *rl;
1401         struct symbol *type;
1402         int recurse_cnt = 0;
1403
1404         type = get_type(expr);
1405         if (!type)
1406                 type = &llong_ctype;  // FIXME: this is wrong but places assume get type can't fail.
1407         rl = _get_rl(expr, RL_REAL_ABSOLUTE, &recurse_cnt);
1408         if (rl)
1409                 *sval = rl_min(rl);
1410         else
1411                 *sval = sval_type_min(type);
1412
1413         if (sval_cmp(*sval, sval_type_min(type)) < 0)
1414                 *sval = sval_type_min(type);
1415         return 1;
1416 }
1417
1418 int get_absolute_max(struct expression *expr, sval_t *sval)
1419 {
1420         struct range_list *rl;
1421         struct symbol *type;
1422         int recurse_cnt = 0;
1423
1424         type = get_type(expr);
1425         if (!type)
1426                 type = &llong_ctype;
1427         rl = _get_rl(expr, RL_REAL_ABSOLUTE, &recurse_cnt);
1428         if (rl)
1429                 *sval = rl_max(rl);
1430         else
1431                 *sval = sval_type_max(type);
1432
1433         if (sval_cmp(sval_type_max(type), *sval) < 0)
1434                 *sval = sval_type_max(type);
1435         return 1;
1436 }
1437
1438 int known_condition_true(struct expression *expr)
1439 {
1440         sval_t tmp;
1441
1442         if (!expr)
1443                 return 0;
1444
1445         if (get_value(expr, &tmp) && tmp.value)
1446                 return 1;
1447
1448         return 0;
1449 }
1450
1451 int known_condition_false(struct expression *expr)
1452 {
1453         if (!expr)
1454                 return 0;
1455
1456         if (is_zero(expr))
1457                 return 1;
1458
1459         return 0;
1460 }
1461
1462 int implied_condition_true(struct expression *expr)
1463 {
1464         sval_t tmp;
1465
1466         if (!expr)
1467                 return 0;
1468
1469         if (known_condition_true(expr))
1470                 return 1;
1471         if (get_implied_value(expr, &tmp) && tmp.value)
1472                 return 1;
1473
1474         if (expr->type == EXPR_POSTOP)
1475                 return implied_condition_true(expr->unop);
1476
1477         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
1478                 return implied_not_equal(expr->unop, 1);
1479         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
1480                 return implied_not_equal(expr->unop, -1);
1481
1482         expr = strip_expr(expr);
1483         switch (expr->type) {
1484         case EXPR_COMPARE:
1485                 if (do_comparison(expr) == 1)
1486                         return 1;
1487                 break;
1488         case EXPR_PREOP:
1489                 if (expr->op == '!') {
1490                         if (implied_condition_false(expr->unop))
1491                                 return 1;
1492                         break;
1493                 }
1494                 break;
1495         default:
1496                 if (implied_not_equal(expr, 0) == 1)
1497                         return 1;
1498                 break;
1499         }
1500         return 0;
1501 }
1502
1503 int implied_condition_false(struct expression *expr)
1504 {
1505         struct expression *tmp;
1506         sval_t sval;
1507
1508         if (!expr)
1509                 return 0;
1510
1511         if (known_condition_false(expr))
1512                 return 1;
1513
1514         switch (expr->type) {
1515         case EXPR_COMPARE:
1516                 if (do_comparison(expr) == 2)
1517                         return 1;
1518         case EXPR_PREOP:
1519                 if (expr->op == '!') {
1520                         if (implied_condition_true(expr->unop))
1521                                 return 1;
1522                         break;
1523                 }
1524                 tmp = strip_expr(expr);
1525                 if (tmp != expr)
1526                         return implied_condition_false(tmp);
1527                 break;
1528         default:
1529                 if (get_implied_value(expr, &sval) && sval.value == 0)
1530                         return 1;
1531                 break;
1532         }
1533         return 0;
1534 }
1535
1536 int can_integer_overflow(struct symbol *type, struct expression *expr)
1537 {
1538         int op;
1539         sval_t lmax, rmax, res;
1540
1541         if (!type)
1542                 type = &int_ctype;
1543
1544         expr = strip_expr(expr);
1545
1546         if (expr->type == EXPR_ASSIGNMENT) {
1547                 switch(expr->op) {
1548                 case SPECIAL_MUL_ASSIGN:
1549                         op = '*';
1550                         break;
1551                 case SPECIAL_ADD_ASSIGN:
1552                         op = '+';
1553                         break;
1554                 case SPECIAL_SHL_ASSIGN:
1555                         op = SPECIAL_LEFTSHIFT;
1556                         break;
1557                 default:
1558                         return 0;
1559                 }
1560         } else if (expr->type == EXPR_BINOP) {
1561                 if (expr->op != '*' && expr->op != '+' && expr->op != SPECIAL_LEFTSHIFT)
1562                         return 0;
1563                 op = expr->op;
1564         } else {
1565                 return 0;
1566         }
1567
1568         get_absolute_max(expr->left, &lmax);
1569         get_absolute_max(expr->right, &rmax);
1570
1571         if (sval_binop_overflows(lmax, op, rmax))
1572                 return 1;
1573
1574         res = sval_binop(lmax, op, rmax);
1575         if (sval_cmp(res, sval_type_max(type)) > 0)
1576                 return 1;
1577         return 0;
1578 }