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