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