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