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