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 struct range_list *_get_rl(struct expression *expr, int implied, int *recurse_cnt);
  24 static struct range_list *handle_variable(struct expression *expr, int implied, int *recurse_cnt);
  25 static struct range_list *(*custom_handle_variable)(struct expression *expr);
  26
  27 static int get_implied_value_internal(struct expression *expr, sval_t *sval, int *recurse_cnt);
  28 static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt);
  29
  30 static sval_t zero  = {.type = &int_ctype, {.value = 0} };
  31 static sval_t one   = {.type = &int_ctype, {.value = 1} };
  32
  33 struct range_list *rl_zero(void)
  34 {
  35         return alloc_rl(zero, zero);
  36 }
  37
  38 struct range_list *rl_one(void)
  39 {
  40         return alloc_rl(one, one);
  41 }
  42
  43 enum {
  44         RL_EXACT,
  45         RL_HARD,
  46         RL_FUZZY,
  47         RL_IMPLIED,
  48         RL_ABSOLUTE,
  49         RL_REAL_ABSOLUTE,
  50 };
  51
  52 static struct range_list *last_stmt_rl(struct statement *stmt, int implied, int *recurse_cnt)
  53 {
  54         if (!stmt)
  55                 return NULL;
  56
  57         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
  58         if (stmt->type != STMT_EXPRESSION)
  59                 return NULL;
  60         return _get_rl(stmt->expression, implied, recurse_cnt);
  61 }
  62
  63 static struct range_list *handle_expression_statement_rl(struct expression *expr, int implied, int *recurse_cnt)
  64 {
  65         return last_stmt_rl(get_expression_statement(expr), implied, recurse_cnt);
  66 }
  67
  68 static struct range_list *handle_ampersand_rl(struct expression *expr, int implied, int *recurse_cnt)
  69 {
  70         struct range_list *rl;
  71
  72         if (implied == RL_EXACT || implied == RL_HARD)
  73                 return NULL;
  74         if (get_address_rl(expr, &rl))
  75                 return rl;
  76         return alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
  77 }
  78
  79 static struct range_list *handle_negate_rl(struct expression *expr, int implied, int *recurse_cnt)
  80 {
  81         if (known_condition_true(expr->unop))
  82                 return rl_zero();
  83         if (known_condition_false(expr->unop))
  84                 return rl_one();
  85
  86         if (implied == RL_EXACT)
  87                 return NULL;
  88
  89         if (implied_condition_true(expr->unop))
  90                 return rl_zero();
  91         if (implied_condition_false(expr->unop))
  92                 return rl_one();
  93         return alloc_rl(zero, one);
  94 }
  95
  96 static struct range_list *handle_bitwise_negate(struct expression *expr, int implied, int *recurse_cnt)
  97 {
  98         struct range_list *rl;
  99         sval_t sval;
 100
 101         rl = _get_rl(expr->unop, implied, recurse_cnt);
 102         if (!rl_to_sval(rl, &sval))
 103                 return NULL;
 104         sval = sval_preop(sval, '~');
 105         sval_cast(get_type(expr->unop), sval);
 106         return alloc_rl(sval, sval);
 107 }
 108
 109 static struct range_list *handle_minus_preop(struct expression *expr, int implied, int *recurse_cnt)
 110 {
 111         struct range_list *rl;
 112         sval_t sval;
 113
 114         rl = _get_rl(expr->unop, implied, recurse_cnt);
 115         if (!rl_to_sval(rl, &sval))
 116                 return NULL;
 117         sval = sval_preop(sval, '-');
 118         return alloc_rl(sval, sval);
 119 }
 120
 121 static struct range_list *handle_preop_rl(struct expression *expr, int implied, int *recurse_cnt)
 122 {
 123         switch (expr->op) {
 124         case '&':
 125                 return handle_ampersand_rl(expr, implied, recurse_cnt);
 126         case '!':
 127                 return handle_negate_rl(expr, implied, recurse_cnt);
 128         case '~':
 129                 return handle_bitwise_negate(expr, implied, recurse_cnt);
 130         case '-':
 131                 return handle_minus_preop(expr, implied, recurse_cnt);
 132         case '*':
 133                 return handle_variable(expr, implied, recurse_cnt);
 134         case '(':
 135                 return handle_expression_statement_rl(expr, implied, recurse_cnt);
 136         default:
 137                 return NULL;
 138         }
 139 }
 140
 141 static struct range_list *handle_divide_rl(struct expression *expr, int implied, int *recurse_cnt)
 142 {
 143         struct range_list *left_rl, *right_rl;
 144         struct symbol *type;
 145
 146         type = get_type(expr);
 147
 148         left_rl = _get_rl(expr->left, implied, recurse_cnt);
 149         left_rl = cast_rl(type, left_rl);
 150         right_rl = _get_rl(expr->right, implied, recurse_cnt);
 151         right_rl = cast_rl(type, right_rl);
 152
 153         if (!left_rl || !right_rl)
 154                 return NULL;
 155
 156         if (implied != RL_REAL_ABSOLUTE) {
 157                 if (is_whole_rl(left_rl) || is_whole_rl(right_rl))
 158                         return NULL;
 159         }
 160
 161         return rl_binop(left_rl, '/', right_rl);
 162 }
 163
 164 static struct range_list *handle_subtract_rl(struct expression *expr, int implied, int *recurse_cnt)
 165 {
 166         struct symbol *type;
 167         struct range_list *left_rl, *right_rl;
 168         sval_t max, min, tmp;
 169         int comparison;
 170
 171         type = get_type(expr);
 172         comparison = get_comparison(expr->left, expr->right);
 173
 174         left_rl = _get_rl(expr->left, implied, recurse_cnt);
 175         left_rl = cast_rl(type, left_rl);
 176         right_rl = _get_rl(expr->right, implied, recurse_cnt);
 177         right_rl = cast_rl(type, right_rl);
 178
 179         if ((!left_rl || !right_rl) &&
 180             (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY))
 181                 return NULL;
 182
 183         if (!left_rl)
 184                 left_rl = alloc_whole_rl(type);
 185         if (!right_rl)
 186                 right_rl = alloc_whole_rl(type);
 187
 188         /* negative values complicate everything fix this later */
 189         if (sval_is_negative(rl_min(right_rl)))
 190                 return NULL;
 191         max = rl_max(left_rl);
 192
 193         switch (comparison) {
 194         case '>':
 195         case SPECIAL_UNSIGNED_GT:
 196                 min = sval_type_val(type, 1);
 197                 max = rl_max(left_rl);
 198                 break;
 199         case SPECIAL_GTE:
 200         case SPECIAL_UNSIGNED_GTE:
 201                 min = sval_type_val(type, 0);
 202                 max = rl_max(left_rl);
 203                 break;
 204         default:
 205                 if (sval_binop_overflows(rl_min(left_rl), '-', rl_max(right_rl)))
 206                         return NULL;
 207                 min = sval_type_min(type);
 208         }
 209
 210         if (!sval_binop_overflows(rl_min(left_rl), '-', rl_max(right_rl))) {
 211                 tmp = sval_binop(rl_min(left_rl), '-', rl_max(right_rl));
 212                 if (sval_cmp(tmp, min) > 0)
 213                         min = tmp;
 214         }
 215
 216         if (!sval_is_max(rl_max(left_rl))) {
 217                 tmp = sval_binop(rl_max(left_rl), '-', rl_min(right_rl));
 218                 if (sval_cmp(tmp, max) < 0)
 219                         max = tmp;
 220         }
 221
 222         if (sval_is_min(min) && sval_is_max(max))
 223                 return NULL;
 224
 225         return cast_rl(type, alloc_rl(min, max));
 226 }
 227
 228 static struct range_list *handle_mod_rl(struct expression *expr, int implied, int *recurse_cnt)
 229 {
 230         struct range_list *rl;
 231         sval_t left, right, sval;
 232
 233         if (implied == RL_EXACT) {
 234                 if (!get_value(expr->right, &right))
 235                         return NULL;
 236                 if (!get_value(expr->left, &left))
 237                         return NULL;
 238                 sval = sval_binop(left, '%', right);
 239                 return alloc_rl(sval, sval);
 240         }
 241         /* if we can't figure out the right side it's probably hopeless */
 242         if (!get_implied_value_internal(expr->right, &right, recurse_cnt))
 243                 return NULL;
 244
 245         right = sval_cast(get_type(expr), right);
 246         right.value--;
 247
 248         rl = _get_rl(expr->left, implied, recurse_cnt);
 249         if (rl && rl_max(rl).uvalue < right.uvalue)
 250                 right.uvalue = rl_max(rl).uvalue;
 251
 252         return alloc_rl(zero, right);
 253 }
 254
 255 static sval_t sval_lowest_set_bit(sval_t sval)
 256 {
 257         int i;
 258         int found = 0;
 259
 260         for (i = 0; i < 64; i++) {
 261                 if (sval.uvalue & 1ULL << i) {
 262                         if (!found++)
 263                                 continue;
 264                         sval.uvalue &= ~(1ULL << i);
 265                 }
 266         }
 267         return sval;
 268 }
 269
 270 static struct range_list *handle_bitwise_AND(struct expression *expr, int implied, int *recurse_cnt)
 271 {
 272         struct symbol *type;
 273         struct range_list *left_rl, *right_rl;
 274         sval_t known;
 275
 276         if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE)
 277                 return NULL;
 278
 279         type = get_type(expr);
 280
 281         if (get_implied_value_internal(expr->left, &known, recurse_cnt)) {
 282                 sval_t min;
 283
 284                 min = sval_lowest_set_bit(known);
 285                 left_rl = alloc_rl(min, known);
 286                 left_rl = cast_rl(type, left_rl);
 287                 add_range(&left_rl, sval_type_val(type, 0), sval_type_val(type, 0));
 288         } else {
 289                 left_rl = _get_rl(expr->left, implied, recurse_cnt);
 290                 if (left_rl) {
 291                         left_rl = cast_rl(type, left_rl);
 292                         left_rl = alloc_rl(sval_type_val(type, 0), rl_max(left_rl));
 293                 } else {
 294                         if (implied == RL_HARD)
 295                                 return NULL;
 296                         left_rl = alloc_whole_rl(type);
 297                 }
 298         }
 299
 300         if (get_implied_value_internal(expr->right, &known, recurse_cnt)) {
 301                 sval_t min, left_max, mod;
 302
 303                 min = sval_lowest_set_bit(known);
 304                 right_rl = alloc_rl(min, known);
 305                 right_rl = cast_rl(type, right_rl);
 306                 add_range(&right_rl, sval_type_val(type, 0), sval_type_val(type, 0));
 307
 308                 if (min.value != 0) {
 309                         left_max = rl_max(left_rl);
 310                         mod = sval_binop(left_max, '%', min);
 311                         if (mod.value) {
 312                                 left_max = sval_binop(left_max, '-', mod);
 313                                 left_max.value++;
 314                                 if (left_max.value > 0 && sval_cmp(left_max, rl_max(left_rl)) < 0)
 315                                         left_rl = remove_range(left_rl, left_max, rl_max(left_rl));
 316                         }
 317                 }
 318         } else {
 319                 right_rl = _get_rl(expr->right, implied, recurse_cnt);
 320                 if (right_rl) {
 321                         right_rl = cast_rl(type, right_rl);
 322                         right_rl = alloc_rl(sval_type_val(type, 0), rl_max(right_rl));
 323                 } else {
 324                         if (implied == RL_HARD)
 325                                 return NULL;
 326                         right_rl = alloc_whole_rl(type);
 327                 }
 328         }
 329
 330         return rl_intersection(left_rl, right_rl);
 331 }
 332
 333 static struct range_list *use_rl_binop(struct expression *expr, int implied, int *recurse_cnt)
 334 {
 335         struct symbol *type;
 336         struct range_list *left_rl, *right_rl;
 337
 338         if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE)
 339                 return NULL;
 340
 341         type = get_type(expr);
 342
 343         get_absolute_rl_internal(expr->left, &left_rl, recurse_cnt);
 344         get_absolute_rl_internal(expr->right, &right_rl, recurse_cnt);
 345         left_rl = cast_rl(type, left_rl);
 346         right_rl = cast_rl(type, right_rl);
 347         if (!left_rl || !right_rl)
 348                 return NULL;
 349
 350         return rl_binop(left_rl, expr->op, right_rl);
 351 }
 352
 353 static struct range_list *handle_right_shift(struct expression *expr, int implied, int *recurse_cnt)
 354 {
 355         struct range_list *left_rl;
 356         sval_t right;
 357         sval_t min, max;
 358
 359         if (implied == RL_EXACT || implied == RL_HARD)
 360                 return NULL;
 361
 362         left_rl = _get_rl(expr->left, implied, recurse_cnt);
 363         if (left_rl) {
 364                 max = rl_max(left_rl);
 365                 min = rl_min(left_rl);
 366         } else {
 367                 if (implied == RL_FUZZY)
 368                         return NULL;
 369                 max = sval_type_max(get_type(expr->left));
 370                 min = sval_type_val(get_type(expr->left), 0);
 371         }
 372
 373         if (get_implied_value_internal(expr->right, &right, recurse_cnt)) {
 374                 min = sval_binop(min, SPECIAL_RIGHTSHIFT, right);
 375                 max = sval_binop(max, SPECIAL_RIGHTSHIFT, right);
 376         } else if (!sval_is_negative(min)) {
 377                 min.value = 0;
 378                 max = sval_type_max(max.type);
 379         } else {
 380                 return NULL;
 381         }
 382
 383         return alloc_rl(min, max);
 384 }
 385
 386 static struct range_list *handle_left_shift(struct expression *expr, int implied, int *recurse_cnt)
 387 {
 388         struct range_list *left_rl, *res;
 389         sval_t right;
 390         sval_t min, max;
 391         int add_zero = 0;
 392
 393         if (implied == RL_EXACT || implied == RL_HARD)
 394                 return NULL;
 395         /* this is hopeless without the right side */
 396         if (!get_implied_value_internal(expr->right, &right, recurse_cnt))
 397                 return NULL;
 398         left_rl = _get_rl(expr->left, implied, recurse_cnt);
 399         if (left_rl) {
 400                 max = rl_max(left_rl);
 401                 min = rl_min(left_rl);
 402                 if (min.value == 0) {
 403                         min.value = 1;
 404                         add_zero = 1;
 405                 }
 406         } else {
 407                 if (implied == RL_FUZZY)
 408                         return NULL;
 409                 max = sval_type_max(get_type(expr->left));
 410                 min = sval_type_val(get_type(expr->left), 1);
 411                 add_zero = 1;
 412         }
 413
 414         max = sval_binop(max, SPECIAL_LEFTSHIFT, right);
 415         min = sval_binop(min, SPECIAL_LEFTSHIFT, right);
 416         res = alloc_rl(min, max);
 417         if (add_zero)
 418                 res = rl_union(res, rl_zero());
 419         return res;
 420 }
 421
 422 static struct range_list *handle_known_binop(struct expression *expr)
 423 {
 424         sval_t left, right;
 425
 426         if (!get_value(expr->left, &left))
 427                 return NULL;
 428         if (!get_value(expr->right, &right))
 429                 return NULL;
 430         left = sval_binop(left, expr->op, right);
 431         return alloc_rl(left, left);
 432 }
 433
 434 static int has_actual_ranges(struct range_list *rl)
 435 {
 436         struct data_range *tmp;
 437
 438         FOR_EACH_PTR(rl, tmp) {
 439                 if (sval_cmp(tmp->min, tmp->max) != 0)
 440                         return 1;
 441         } END_FOR_EACH_PTR(tmp);
 442         return 0;
 443 }
 444
 445 static struct range_list *handle_implied_binop(struct range_list *left_rl, int op, struct range_list *right_rl)
 446 {
 447         struct range_list *res_rl;
 448         struct data_range *left_drange, *right_drange;
 449         sval_t res;
 450
 451         if (!left_rl || !right_rl)
 452                 return NULL;
 453         if (has_actual_ranges(left_rl))
 454                 return NULL;
 455         if (has_actual_ranges(right_rl))
 456                 return NULL;
 457
 458         if (ptr_list_size((struct ptr_list *)left_rl) * ptr_list_size((struct ptr_list *)right_rl) > 20)
 459                 return NULL;
 460
 461         res_rl = NULL;
 462
 463         FOR_EACH_PTR(left_rl, left_drange) {
 464                 FOR_EACH_PTR(right_rl, right_drange) {
 465                         if ((op == '%' || op == '/') &&
 466                             right_drange->min.value == 0)
 467                                 return NULL;
 468                         res = sval_binop(left_drange->min, op, right_drange->min);
 469                         add_range(&res_rl, res, res);
 470                 } END_FOR_EACH_PTR(right_drange);
 471         } END_FOR_EACH_PTR(left_drange);
 472
 473         return res_rl;
 474 }
 475
 476 static struct range_list *handle_binop_rl(struct expression *expr, int implied, int *recurse_cnt)
 477 {
 478         struct smatch_state *state;
 479         struct symbol *type;
 480         struct range_list *left_rl, *right_rl, *rl;
 481         sval_t min, max;
 482
 483         rl = handle_known_binop(expr);
 484         if (rl)
 485                 return rl;
 486         if (implied == RL_EXACT)
 487                 return NULL;
 488
 489         state = get_extra_state(expr);
 490         if (state && !is_whole_rl(estate_rl(state)))
 491                 return clone_rl(estate_rl(state));
 492
 493         type = get_type(expr);
 494         left_rl = _get_rl(expr->left, implied, recurse_cnt);
 495         left_rl = cast_rl(type, left_rl);
 496         right_rl = _get_rl(expr->right, implied, recurse_cnt);
 497         right_rl = cast_rl(type, right_rl);
 498
 499         if (!left_rl && !right_rl)
 500                 return NULL;
 501
 502         rl = handle_implied_binop(left_rl, expr->op, right_rl);
 503         if (rl)
 504                 return rl;
 505
 506         switch (expr->op) {
 507         case '%':
 508                 return handle_mod_rl(expr, implied, recurse_cnt);
 509         case '&':
 510                 return handle_bitwise_AND(expr, implied, recurse_cnt);
 511         case '|':
 512         case '^':
 513                 return use_rl_binop(expr, implied, recurse_cnt);
 514         case SPECIAL_RIGHTSHIFT:
 515                 return handle_right_shift(expr, implied, recurse_cnt);
 516         case SPECIAL_LEFTSHIFT:
 517                 return handle_left_shift(expr, implied, recurse_cnt);
 518         case '-':
 519                 return handle_subtract_rl(expr, implied, recurse_cnt);
 520         case '/':
 521                 return handle_divide_rl(expr, implied, recurse_cnt);
 522         }
 523
 524         if (!left_rl || !right_rl)
 525                 return NULL;
 526
 527         if (sval_binop_overflows(rl_min(left_rl), expr->op, rl_min(right_rl)))
 528                 return NULL;
 529         if (sval_binop_overflows(rl_max(left_rl), expr->op, rl_max(right_rl)))
 530                 return NULL;
 531
 532         min = sval_binop(rl_min(left_rl), expr->op, rl_min(right_rl));
 533         max = sval_binop(rl_max(left_rl), expr->op, rl_max(right_rl));
 534
 535         return alloc_rl(min, max);
 536 }
 537
 538 static int do_comparison(struct expression *expr)
 539 {
 540         struct range_list *left_ranges = NULL;
 541         struct range_list *right_ranges = NULL;
 542         int poss_true, poss_false;
 543         struct symbol *type;
 544
 545         type = get_type(expr);
 546         get_absolute_rl(expr->left, &left_ranges);
 547         get_absolute_rl(expr->right, &right_ranges);
 548
 549         left_ranges = cast_rl(type, left_ranges);
 550         right_ranges = cast_rl(type, right_ranges);
 551
 552         poss_true = possibly_true_rl(left_ranges, expr->op, right_ranges);
 553         poss_false = possibly_false_rl(left_ranges, expr->op, right_ranges);
 554
 555         free_rl(&left_ranges);
 556         free_rl(&right_ranges);
 557
 558         if (!poss_true && !poss_false)
 559                 return 0x0;
 560         if (poss_true && !poss_false)
 561                 return 0x1;
 562         if (!poss_true && poss_false)
 563                 return 0x2;
 564         return 0x3;
 565 }
 566
 567 static struct range_list *handle_comparison_rl(struct expression *expr, int implied, int *recurse_cnt)
 568 {
 569         sval_t left, right;
 570         int res;
 571
 572         if (get_value(expr->left, &left) && get_value(expr->right, &right)) {
 573                 struct data_range tmp_left, tmp_right;
 574
 575                 tmp_left.min = left;
 576                 tmp_left.max = left;
 577                 tmp_right.min = right;
 578                 tmp_right.max = right;
 579                 if (true_comparison_range(&tmp_left, expr->op, &tmp_right))
 580                         return rl_one();
 581                 return rl_zero();
 582         }
 583
 584         if (implied == RL_EXACT)
 585                 return NULL;
 586
 587         res = do_comparison(expr);
 588         if (res == 1)
 589                 return rl_one();
 590         if (res == 2)
 591                 return rl_zero();
 592
 593         return alloc_rl(zero, one);
 594 }
 595
 596 static struct range_list *handle_logical_rl(struct expression *expr, int implied, int *recurse_cnt)
 597 {
 598         sval_t left, right;
 599         int left_known = 0;
 600         int right_known = 0;
 601
 602         if (implied == RL_EXACT) {
 603                 if (get_value(expr->left, &left))
 604                         left_known = 1;
 605                 if (get_value(expr->right, &right))
 606                         right_known = 1;
 607         } else {
 608                 if (get_implied_value_internal(expr->left, &left, recurse_cnt))
 609                         left_known = 1;
 610                 if (get_implied_value_internal(expr->right, &right, recurse_cnt))
 611                         right_known = 1;
 612         }
 613
 614         switch (expr->op) {
 615         case SPECIAL_LOGICAL_OR:
 616                 if (left_known && left.value)
 617                         return rl_one();
 618                 if (right_known && right.value)
 619                         return rl_one();
 620                 if (left_known && right_known)
 621                         return rl_zero();
 622                 break;
 623         case SPECIAL_LOGICAL_AND:
 624                 if (left_known && right_known) {
 625                         if (left.value && right.value)
 626                                 return rl_one();
 627                         return rl_zero();
 628                 }
 629                 break;
 630         default:
 631                 return NULL;
 632         }
 633
 634         if (implied == RL_EXACT)
 635                 return NULL;
 636
 637         return alloc_rl(zero, one);
 638 }
 639
 640 static struct range_list *handle_conditional_rl(struct expression *expr, int implied, int *recurse_cnt)
 641 {
 642         struct range_list *true_rl, *false_rl;
 643         struct symbol *type;
 644         int final_pass_orig = final_pass;
 645
 646         if (known_condition_true(expr->conditional))
 647                 return _get_rl(expr->cond_true, implied, recurse_cnt);
 648         if (known_condition_false(expr->conditional))
 649                 return _get_rl(expr->cond_false, implied, recurse_cnt);
 650
 651         if (implied == RL_EXACT)
 652                 return NULL;
 653
 654         if (implied_condition_true(expr->conditional))
 655                 return _get_rl(expr->cond_true, implied, recurse_cnt);
 656         if (implied_condition_false(expr->conditional))
 657                 return _get_rl(expr->cond_false, implied, recurse_cnt);
 658
 659
 660         /* this becomes a problem with deeply nested conditional statements */
 661         if (low_on_memory())
 662                 return NULL;
 663
 664         type = get_type(expr);
 665
 666         __push_fake_cur_stree();
 667         final_pass = 0;
 668         __split_whole_condition(expr->conditional);
 669         true_rl = _get_rl(expr->cond_true, implied, recurse_cnt);
 670         __push_true_states();
 671         __use_false_states();
 672         false_rl = _get_rl(expr->cond_false, implied, recurse_cnt);
 673         __merge_true_states();
 674         __free_fake_cur_stree();
 675         final_pass = final_pass_orig;
 676
 677         if (!true_rl || !false_rl)
 678                 return NULL;
 679         true_rl = cast_rl(type, true_rl);
 680         false_rl = cast_rl(type, false_rl);
 681
 682         return rl_union(true_rl, false_rl);
 683 }
 684
 685 static int get_fuzzy_max_helper(struct expression *expr, sval_t *max)
 686 {
 687         struct smatch_state *state;
 688         sval_t sval;
 689
 690         if (get_hard_max(expr, &sval)) {
 691                 *max = sval;
 692                 return 1;
 693         }
 694
 695         state = get_extra_state(expr);
 696         if (!state || !estate_has_fuzzy_max(state))
 697                 return 0;
 698         *max = sval_cast(get_type(expr), estate_get_fuzzy_max(state));
 699         return 1;
 700 }
 701
 702 static int get_fuzzy_min_helper(struct expression *expr, sval_t *min)
 703 {
 704         struct smatch_state *state;
 705         sval_t sval;
 706
 707         state = get_extra_state(expr);
 708         if (!state || !estate_rl(state))
 709                 return 0;
 710
 711         sval = estate_min(state);
 712         if (sval_is_negative(sval) && sval_is_min(sval))
 713                 return 0;
 714
 715         if (sval_is_max(sval))
 716                 return 0;
 717
 718         *min = sval_cast(get_type(expr), sval);
 719         return 1;
 720 }
 721
 722 int get_const_value(struct expression *expr, sval_t *sval)
 723 {
 724         struct symbol *sym;
 725         sval_t right;
 726
 727         if (expr->type != EXPR_SYMBOL || !expr->symbol)
 728                 return 0;
 729         sym = expr->symbol;
 730         if (!(sym->ctype.modifiers & MOD_CONST))
 731                 return 0;
 732         if (get_value(sym->initializer, &right)) {
 733                 *sval = sval_cast(get_type(expr), right);
 734                 return 1;
 735         }
 736         return 0;
 737 }
 738
 739 struct range_list *var_to_absolute_rl(struct expression *expr)
 740 {
 741         struct smatch_state *state;
 742         struct range_list *rl;
 743
 744         state = get_extra_state(expr);
 745         if (!state || is_whole_rl(estate_rl(state))) {
 746                 state = get_real_absolute_state(expr);
 747                 if (state && state->data && !estate_is_whole(state))
 748                         return clone_rl(estate_rl(state));
 749                 if (get_local_rl(expr, &rl) && !is_whole_rl(rl))
 750                         return rl;
 751                 if (get_db_type_rl(expr, &rl) && !is_whole_rl(rl))
 752                         return rl;
 753                 return alloc_whole_rl(get_type(expr));
 754         }
 755         /* err on the side of saying things are possible */
 756         if (!estate_rl(state))
 757                 return alloc_whole_rl(get_type(expr));
 758         return clone_rl(estate_rl(state));
 759 }
 760
 761 static struct range_list *handle_variable(struct expression *expr, int implied, int *recurse_cnt)
 762 {
 763         struct smatch_state *state;
 764         struct range_list *rl;
 765         sval_t sval, min, max;
 766
 767         if (get_const_value(expr, &sval))
 768                 return alloc_rl(sval, sval);
 769
 770         if (custom_handle_variable) {
 771                 rl = custom_handle_variable(expr);
 772                 if (!rl)
 773                         return var_to_absolute_rl(expr);
 774                 return rl;
 775         }
 776
 777         switch (implied) {
 778         case RL_EXACT:
 779                 return NULL;
 780         case RL_HARD:
 781         case RL_IMPLIED:
 782         case RL_ABSOLUTE:
 783                 state = get_extra_state(expr);
 784                 if (!state || !state->data) {
 785                         if (implied == RL_HARD)
 786                                 return NULL;
 787                         if (get_local_rl(expr, &rl))
 788                                 return rl;
 789                         if (get_db_type_rl(expr, &rl))
 790                                 return rl;
 791                         return NULL;
 792                 }
 793                 if (implied == RL_HARD && !estate_has_hard_max(state))
 794                         return NULL;
 795                 return clone_rl(estate_rl(state));
 796         case RL_REAL_ABSOLUTE:
 797                 state = get_extra_state(expr);
 798                 if (!state || !state->data || is_whole_rl(estate_rl(state))) {
 799                         if (get_local_rl(expr, &rl))
 800                                 return rl;
 801                         if (get_db_type_rl(expr, &rl))
 802                                 return rl;
 803                         state = get_real_absolute_state(expr);
 804                         if (state && state->data)
 805                                 return clone_rl(estate_rl(state));
 806                         return NULL;
 807                 }
 808                 return clone_rl(estate_rl(state));
 809         case RL_FUZZY:
 810                 if (!get_fuzzy_min_helper(expr, &min))
 811                         min = sval_type_min(get_type(expr));
 812                 if (!get_fuzzy_max_helper(expr, &max))
 813                         return NULL;
 814                 /* fuzzy ranges are often inverted */
 815                 if (sval_cmp(min, max) > 0) {
 816                         sval = min;
 817                         min = max;
 818                         max = sval;
 819                 }
 820                 return alloc_rl(min, max);
 821         }
 822         return NULL;
 823 }
 824
 825 static sval_t handle_sizeof(struct expression *expr)
 826 {
 827         struct symbol *sym;
 828         sval_t ret;
 829
 830         ret = sval_blank(expr);
 831         sym = expr->cast_type;
 832         if (!sym) {
 833                 sym = evaluate_expression(expr->cast_expression);
 834                 /*
 835                  * Expressions of restricted types will possibly get
 836                  * promoted - check that here
 837                  */
 838                 if (is_restricted_type(sym)) {
 839                         if (type_bits(sym) < bits_in_int)
 840                                 sym = &int_ctype;
 841                 } else if (is_fouled_type(sym)) {
 842                         sym = &int_ctype;
 843                 }
 844         }
 845         examine_symbol_type(sym);
 846
 847         ret.type = size_t_ctype;
 848         if (type_bits(sym) <= 0) /* sizeof(void) */ {
 849                 if (get_real_base_type(sym) == &void_ctype)
 850                         ret.value = 1;
 851                 else
 852                         ret.value = 0;
 853         } else
 854                 ret.value = type_bytes(sym);
 855
 856         return ret;
 857 }
 858
 859 static struct range_list *handle_strlen(struct expression *expr, int implied, int *recurse_cnt)
 860 {
 861         struct range_list *rl;
 862         struct expression *arg;
 863         sval_t sval = { .type = &ulong_ctype };
 864
 865         if (implied == RL_EXACT)
 866                 return NULL;
 867
 868         arg = get_argument_from_call_expr(expr->args, 0);
 869         if (!arg)
 870                 return NULL;
 871         if (arg->type == EXPR_STRING) {
 872                 sval.value = arg->string->length - 1;
 873                 return alloc_rl(sval, sval);
 874         }
 875
 876         if (implied == RL_HARD || implied == RL_FUZZY)
 877                 return NULL;
 878
 879         if (get_implied_return(expr, &rl))
 880                 return rl;
 881
 882         return NULL;
 883 }
 884
 885 static struct range_list *handle_call_rl(struct expression *expr, int implied, int *recurse_cnt)
 886 {
 887         struct range_list *rl;
 888
 889         if (sym_name_is("__builtin_expect", expr->fn)) {
 890                 struct expression *arg;
 891
 892                 arg = get_argument_from_call_expr(expr->args, 0);
 893                 return _get_rl(arg, implied, recurse_cnt);
 894         }
 895
 896         if (sym_name_is("strlen", expr->fn))
 897                 return handle_strlen(expr, implied, recurse_cnt);
 898
 899         if (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY)
 900                 return NULL;
 901
 902         if (get_implied_return(expr, &rl))
 903                 return rl;
 904         return db_return_vals(expr);
 905 }
 906
 907 static struct range_list *handle_cast(struct expression *expr, int implied, int *recurse_cnt)
 908 {
 909         struct range_list *rl;
 910         struct symbol *type;
 911
 912         type = get_type(expr);
 913         rl = _get_rl(expr->cast_expression, implied, recurse_cnt);
 914         if (rl)
 915                 return cast_rl(type, rl);
 916         if (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE)
 917                 return alloc_whole_rl(type);
 918         if (implied == RL_IMPLIED && type &&
 919             type_bits(type) > 0 && type_bits(type) < 32)
 920                 return alloc_whole_rl(type);
 921         return NULL;
 922 }
 923
 924 static struct range_list *_get_rl(struct expression *expr, int implied, int *recurse_cnt)
 925 {
 926         struct range_list *rl;
 927         struct symbol *type;
 928         sval_t sval;
 929
 930         type = get_type(expr);
 931         expr = strip_parens(expr);
 932         if (!expr)
 933                 return NULL;
 934
 935         if (++(*recurse_cnt) >= 200)
 936                 return NULL;
 937
 938         switch(expr->type) {
 939         case EXPR_CAST:
 940         case EXPR_FORCE_CAST:
 941         case EXPR_IMPLIED_CAST:
 942                 rl = handle_cast(expr, implied, recurse_cnt);
 943                 goto out_cast;
 944         }
 945
 946         expr = strip_expr(expr);
 947         if (!expr)
 948                 return NULL;
 949
 950         switch (expr->type) {
 951         case EXPR_VALUE:
 952                 sval = sval_from_val(expr, expr->value);
 953                 rl = alloc_rl(sval, sval);
 954                 break;
 955         case EXPR_PREOP:
 956                 rl = handle_preop_rl(expr, implied, recurse_cnt);
 957                 break;
 958         case EXPR_POSTOP:
 959                 rl = _get_rl(expr->unop, implied, recurse_cnt);
 960                 break;
 961         case EXPR_BINOP:
 962                 rl = handle_binop_rl(expr, implied, recurse_cnt);
 963                 break;
 964         case EXPR_COMPARE:
 965                 rl = handle_comparison_rl(expr, implied, recurse_cnt);
 966                 break;
 967         case EXPR_LOGICAL:
 968                 rl = handle_logical_rl(expr, implied, recurse_cnt);
 969                 break;
 970         case EXPR_PTRSIZEOF:
 971         case EXPR_SIZEOF:
 972                 sval = handle_sizeof(expr);
 973                 rl = alloc_rl(sval, sval);
 974                 break;
 975         case EXPR_SELECT:
 976         case EXPR_CONDITIONAL:
 977                 rl = handle_conditional_rl(expr, implied, recurse_cnt);
 978                 break;
 979         case EXPR_CALL:
 980                 rl = handle_call_rl(expr, implied, recurse_cnt);
 981                 break;
 982         default:
 983                 rl = handle_variable(expr, implied, recurse_cnt);
 984         }
 985
 986 out_cast:
 987         if (rl)
 988                 return rl;
 989         if (type && (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE))
 990                 return alloc_whole_rl(type);
 991         return NULL;
 992 }
 993
 994 /* returns 1 if it can get a value literal or else returns 0 */
 995 int get_value(struct expression *expr, sval_t *sval)
 996 {
 997         struct range_list *rl;
 998         int recurse_cnt = 0;
 999
1000         rl = _get_rl(expr, RL_EXACT, &recurse_cnt);
1001         if (!rl_to_sval(rl, sval))
1002                 return 0;
1003         return 1;
1004 }
1005
1006 static int get_implied_value_internal(struct expression *expr, sval_t *sval, int *recurse_cnt)
1007 {
1008         struct range_list *rl;
1009
1010         rl =  _get_rl(expr, RL_IMPLIED, recurse_cnt);
1011         if (!rl_to_sval(rl, sval))
1012                 return 0;
1013         return 1;
1014 }
1015
1016 int get_implied_value(struct expression *expr, sval_t *sval)
1017 {
1018         struct range_list *rl;
1019         int recurse_cnt = 0;
1020
1021         rl =  _get_rl(expr, RL_IMPLIED, &recurse_cnt);
1022         if (!rl_to_sval(rl, sval))
1023                 return 0;
1024         return 1;
1025 }
1026
1027 int get_implied_min(struct expression *expr, sval_t *sval)
1028 {
1029         struct range_list *rl;
1030         int recurse_cnt = 0;
1031
1032         rl =  _get_rl(expr, RL_IMPLIED, &recurse_cnt);
1033         if (!rl)
1034                 return 0;
1035         *sval = rl_min(rl);
1036         return 1;
1037 }
1038
1039 int get_implied_max(struct expression *expr, sval_t *sval)
1040 {
1041         struct range_list *rl;
1042         int recurse_cnt = 0;
1043
1044         rl =  _get_rl(expr, RL_IMPLIED, &recurse_cnt);
1045         if (!rl)
1046                 return 0;
1047         *sval = rl_max(rl);
1048         return 1;
1049 }
1050
1051 int get_implied_rl(struct expression *expr, struct range_list **rl)
1052 {
1053         int recurse_cnt = 0;
1054
1055         *rl = _get_rl(expr, RL_IMPLIED, &recurse_cnt);
1056         if (*rl)
1057                 return 1;
1058         return 0;
1059 }
1060
1061 static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt)
1062 {
1063         *rl = _get_rl(expr, RL_ABSOLUTE, recurse_cnt);
1064         if (!*rl)
1065                 *rl = alloc_whole_rl(get_type(expr));
1066         return 1;
1067 }
1068
1069 int get_absolute_rl(struct expression *expr, struct range_list **rl)
1070 {
1071         int recurse_cnt = 0;
1072
1073         *rl = _get_rl(expr, RL_ABSOLUTE, &recurse_cnt);
1074         if (!*rl)
1075                 *rl = alloc_whole_rl(get_type(expr));
1076         return 1;
1077 }
1078
1079 int get_real_absolute_rl(struct expression *expr, struct range_list **rl)
1080 {
1081         int recurse_cnt = 0;
1082
1083         *rl = _get_rl(expr, RL_REAL_ABSOLUTE, &recurse_cnt);
1084         if (!*rl)
1085                 *rl = alloc_whole_rl(get_type(expr));
1086         return 1;
1087 }
1088
1089 int custom_get_absolute_rl(struct expression *expr,
1090                            struct range_list *(*fn)(struct expression *expr),
1091                            struct range_list **rl)
1092 {
1093         int recurse_cnt = 0;
1094
1095         *rl = NULL;
1096         custom_handle_variable = fn;
1097         *rl = _get_rl(expr, RL_REAL_ABSOLUTE, &recurse_cnt);
1098         custom_handle_variable = NULL;
1099         return 1;
1100 }
1101
1102 int get_implied_rl_var_sym(const char *var, struct symbol *sym, struct range_list **rl)
1103 {
1104         struct smatch_state *state;
1105
1106         state = get_state(SMATCH_EXTRA, var, sym);
1107         *rl = estate_rl(state);
1108         if (*rl)
1109                 return 1;
1110         return 0;
1111 }
1112
1113 int get_hard_max(struct expression *expr, sval_t *sval)
1114 {
1115         struct range_list *rl;
1116         int recurse_cnt = 0;
1117
1118         rl =  _get_rl(expr, RL_HARD, &recurse_cnt);
1119         if (!rl)
1120                 return 0;
1121         *sval = rl_max(rl);
1122         return 1;
1123 }
1124
1125 int get_fuzzy_min(struct expression *expr, sval_t *sval)
1126 {
1127         struct range_list *rl;
1128         sval_t tmp;
1129         int recurse_cnt = 0;
1130
1131         rl =  _get_rl(expr, RL_FUZZY, &recurse_cnt);
1132         if (!rl)
1133                 return 0;
1134         tmp = rl_min(rl);
1135         if (sval_is_negative(tmp) && sval_is_min(tmp))
1136                 return 0;
1137         *sval = tmp;
1138         return 1;
1139 }
1140
1141 int get_fuzzy_max(struct expression *expr, sval_t *sval)
1142 {
1143         struct range_list *rl;
1144         sval_t max;
1145         int recurse_cnt = 0;
1146
1147         rl =  _get_rl(expr, RL_FUZZY, &recurse_cnt);
1148         if (!rl)
1149                 return 0;
1150         max = rl_max(rl);
1151         if (max.uvalue > INT_MAX - 10000)
1152                 return 0;
1153         *sval = max;
1154         return 1;
1155 }
1156
1157 int get_absolute_min(struct expression *expr, sval_t *sval)
1158 {
1159         struct range_list *rl;
1160         struct symbol *type;
1161         int recurse_cnt = 0;
1162
1163         type = get_type(expr);
1164         if (!type)
1165                 type = &llong_ctype;  // FIXME: this is wrong but places assume get type can't fail.
1166         rl = _get_rl(expr, RL_ABSOLUTE, &recurse_cnt);
1167         if (rl)
1168                 *sval = rl_min(rl);
1169         else
1170                 *sval = sval_type_min(type);
1171
1172         if (sval_cmp(*sval, sval_type_min(type)) < 0)
1173                 *sval = sval_type_min(type);
1174         return 1;
1175 }
1176
1177 int get_absolute_max(struct expression *expr, sval_t *sval)
1178 {
1179         struct range_list *rl;
1180         struct symbol *type;
1181         int recurse_cnt = 0;
1182
1183         type = get_type(expr);
1184         if (!type)
1185                 type = &llong_ctype;
1186         rl = _get_rl(expr, RL_ABSOLUTE, &recurse_cnt);
1187         if (rl)
1188                 *sval = rl_max(rl);
1189         else
1190                 *sval = sval_type_max(type);
1191
1192         if (sval_cmp(sval_type_max(type), *sval) < 0)
1193                 *sval = sval_type_max(type);
1194         return 1;
1195 }
1196
1197 int known_condition_true(struct expression *expr)
1198 {
1199         sval_t tmp;
1200
1201         if (!expr)
1202                 return 0;
1203
1204         if (get_value(expr, &tmp) && tmp.value)
1205                 return 1;
1206
1207         return 0;
1208 }
1209
1210 int known_condition_false(struct expression *expr)
1211 {
1212         if (!expr)
1213                 return 0;
1214
1215         if (is_zero(expr))
1216                 return 1;
1217
1218         if (expr->type == EXPR_CALL) {
1219                 if (sym_name_is("__builtin_constant_p", expr->fn))
1220                         return 1;
1221         }
1222         return 0;
1223 }
1224
1225 int implied_condition_true(struct expression *expr)
1226 {
1227         sval_t tmp;
1228
1229         if (!expr)
1230                 return 0;
1231
1232         if (known_condition_true(expr))
1233                 return 1;
1234         if (get_implied_value(expr, &tmp) && tmp.value)
1235                 return 1;
1236
1237         if (expr->type == EXPR_POSTOP)
1238                 return implied_condition_true(expr->unop);
1239
1240         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
1241                 return implied_not_equal(expr->unop, 1);
1242         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
1243                 return implied_not_equal(expr->unop, -1);
1244
1245         expr = strip_expr(expr);
1246         switch (expr->type) {
1247         case EXPR_COMPARE:
1248                 if (do_comparison(expr) == 1)
1249                         return 1;
1250                 break;
1251         case EXPR_PREOP:
1252                 if (expr->op == '!') {
1253                         if (implied_condition_false(expr->unop))
1254                                 return 1;
1255                         break;
1256                 }
1257                 break;
1258         default:
1259                 if (implied_not_equal(expr, 0) == 1)
1260                         return 1;
1261                 break;
1262         }
1263         return 0;
1264 }
1265
1266 int implied_condition_false(struct expression *expr)
1267 {
1268         struct expression *tmp;
1269         sval_t sval;
1270
1271         if (!expr)
1272                 return 0;
1273
1274         if (known_condition_false(expr))
1275                 return 1;
1276
1277         switch (expr->type) {
1278         case EXPR_COMPARE:
1279                 if (do_comparison(expr) == 2)
1280                         return 1;
1281         case EXPR_PREOP:
1282                 if (expr->op == '!') {
1283                         if (implied_condition_true(expr->unop))
1284                                 return 1;
1285                         break;
1286                 }
1287                 tmp = strip_expr(expr);
1288                 if (tmp != expr)
1289                         return implied_condition_false(tmp);
1290                 break;
1291         default:
1292                 if (get_implied_value(expr, &sval) && sval.value == 0)
1293                         return 1;
1294                 break;
1295         }
1296         return 0;
1297 }
1298
1299 int can_integer_overflow(struct symbol *type, struct expression *expr)
1300 {
1301         int op;
1302         sval_t lmax, rmax, res;
1303
1304         if (!type)
1305                 type = &int_ctype;
1306
1307         expr = strip_expr(expr);
1308
1309         if (expr->type == EXPR_ASSIGNMENT) {
1310                 switch(expr->op) {
1311                 case SPECIAL_MUL_ASSIGN:
1312                         op = '*';
1313                         break;
1314                 case SPECIAL_ADD_ASSIGN:
1315                         op = '+';
1316                         break;
1317                 case SPECIAL_SHL_ASSIGN:
1318                         op = SPECIAL_LEFTSHIFT;
1319                         break;
1320                 default:
1321                         return 0;
1322                 }
1323         } else if (expr->type == EXPR_BINOP) {
1324                 if (expr->op != '*' && expr->op != '+' && expr->op != SPECIAL_LEFTSHIFT)
1325                         return 0;
1326                 op = expr->op;
1327         } else {
1328                 return 0;
1329         }
1330
1331         get_absolute_max(expr->left, &lmax);
1332         get_absolute_max(expr->right, &rmax);
1333
1334         if (sval_binop_overflows(lmax, op, rmax))
1335                 return 1;
1336
1337         res = sval_binop(lmax, op, rmax);
1338         if (sval_cmp(res, sval_type_max(type)) > 0)
1339                 return 1;
1340         return 0;
1341 }