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