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