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