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