smatch_math.c

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