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