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