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;
 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         } else {
 303                 right_rl = _get_rl(expr->right, implied);
 304                 if (right_rl) {
 305                         right_rl = cast_rl(type, right_rl);
 306                         right_rl = alloc_rl(sval_type_val(type, 0), rl_max(right_rl));
 307                 } else {
 308                         if (implied == RL_HARD)
 309                                 return NULL;
 310                         right_rl = alloc_whole_rl(type);
 311                 }
 312         }
 313
 314         return rl_intersection(left_rl, right_rl);
 315 }
 316
 317 static struct range_list *handle_bitwise_OR(struct expression *expr, int implied)
 318 {
 319         struct symbol *type;
 320         struct range_list *left_rl, *right_rl;
 321
 322         if (implied != RL_IMPLIED && implied != RL_ABSOLUTE)
 323                 return NULL;
 324
 325         type = get_type(expr);
 326
 327         get_absolute_rl(expr->left, &left_rl);
 328         get_absolute_rl(expr->right, &right_rl);
 329         left_rl = cast_rl(type, left_rl);
 330         right_rl = cast_rl(type, right_rl);
 331
 332         return rl_union(left_rl, right_rl);
 333 }
 334
 335 static struct range_list *handle_right_shift(struct expression *expr, int implied)
 336 {
 337         struct range_list *left_rl;
 338         sval_t right;
 339         sval_t min, max;
 340
 341         if (implied == RL_EXACT || implied == RL_HARD)
 342                 return NULL;
 343
 344         left_rl = _get_rl(expr->left, implied);
 345         if (left_rl) {
 346                 max = rl_max(left_rl);
 347                 min = rl_min(left_rl);
 348         } else {
 349                 if (implied == RL_FUZZY)
 350                         return NULL;
 351                 max = sval_type_max(get_type(expr->left));
 352                 min = sval_type_val(get_type(expr->left), 0);
 353         }
 354
 355         if (get_implied_value(expr->right, &right)) {
 356                 min = sval_binop(min, SPECIAL_RIGHTSHIFT, right);
 357                 max = sval_binop(max, SPECIAL_RIGHTSHIFT, right);
 358         } else if (!sval_is_negative(min)) {
 359                 min.value = 0;
 360                 max = sval_type_max(max.type);
 361         } else {
 362                 return NULL;
 363         }
 364
 365         return alloc_rl(min, max);
 366 }
 367
 368 static struct range_list *handle_left_shift(struct expression *expr, int implied)
 369 {
 370         struct range_list *left_rl, *res;
 371         sval_t right;
 372         sval_t min, max;
 373         int add_zero = 0;
 374
 375         if (implied == RL_EXACT || implied == RL_HARD)
 376                 return NULL;
 377         /* this is hopeless without the right side */
 378         if (!get_implied_value(expr->right, &right))
 379                 return NULL;
 380         left_rl = _get_rl(expr->left, implied);
 381         if (left_rl) {
 382                 max = rl_max(left_rl);
 383                 min = rl_min(left_rl);
 384                 if (min.value == 0) {
 385                         min.value = 1;
 386                         add_zero = 1;
 387                 }
 388         } else {
 389                 if (implied == RL_FUZZY)
 390                         return NULL;
 391                 max = sval_type_max(get_type(expr->left));
 392                 min = sval_type_val(get_type(expr->left), 1);
 393                 add_zero = 1;
 394         }
 395
 396         max = sval_binop(max, SPECIAL_LEFTSHIFT, right);
 397         min = sval_binop(min, SPECIAL_LEFTSHIFT, right);
 398         res = alloc_rl(min, max);
 399         if (add_zero)
 400                 res = rl_union(res, rl_zero());
 401         return res;
 402 }
 403
 404 static struct range_list *handle_known_binop(struct expression *expr)
 405 {
 406         sval_t left, right;
 407
 408         if (!get_value(expr->left, &left))
 409                 return NULL;
 410         if (!get_value(expr->right, &right))
 411                 return NULL;
 412         left = sval_binop(left, expr->op, right);
 413         return alloc_rl(left, left);
 414 }
 415
 416 static struct range_list *handle_binop_rl(struct expression *expr, int implied)
 417 {
 418         struct symbol *type;
 419         struct range_list *left_rl, *right_rl, *rl;
 420         sval_t min, max;
 421
 422         rl = handle_known_binop(expr);
 423         if (rl)
 424                 return rl;
 425         if (implied == RL_EXACT)
 426                 return NULL;
 427
 428         switch (expr->op) {
 429         case '%':
 430                 return handle_mod_rl(expr, implied);
 431         case '&':
 432                 return handle_bitwise_AND(expr, implied);
 433         case '|':
 434                 return handle_bitwise_OR(expr, implied);
 435         case SPECIAL_RIGHTSHIFT:
 436                 return handle_right_shift(expr, implied);
 437         case SPECIAL_LEFTSHIFT:
 438                 return handle_left_shift(expr, implied);
 439         case '-':
 440                 return handle_subtract_rl(expr, implied);
 441         case '/':
 442                 return handle_divide_rl(expr, implied);
 443         }
 444
 445         type = get_type(expr);
 446         left_rl = _get_rl(expr->left, implied);
 447         left_rl = cast_rl(type, left_rl);
 448         right_rl = _get_rl(expr->right, implied);
 449         right_rl = cast_rl(type, right_rl);
 450
 451         if (!left_rl || !right_rl)
 452                 return NULL;
 453
 454         if (sval_binop_overflows(rl_min(left_rl), expr->op, rl_min(right_rl)))
 455                 return NULL;
 456         min = sval_binop(rl_min(left_rl), expr->op, rl_min(right_rl));
 457
 458         if (sval_binop_overflows(rl_max(left_rl), expr->op, rl_max(right_rl))) {
 459                 switch (implied) {
 460                 case RL_FUZZY:
 461                 case RL_HARD:
 462                         return NULL;
 463                 default:
 464                         max = sval_type_max(get_type(expr));
 465                 }
 466         } else {
 467                 max = sval_binop(rl_max(left_rl), expr->op, rl_max(right_rl));
 468         }
 469
 470         return alloc_rl(min, max);
 471 }
 472
 473 static int do_comparison(struct expression *expr)
 474 {
 475         struct range_list *left_ranges = NULL;
 476         struct range_list *right_ranges = NULL;
 477         int poss_true, poss_false;
 478         struct symbol *type;
 479
 480         type = get_type(expr);
 481
 482         get_implied_rl(expr->left, &left_ranges);
 483         get_implied_rl(expr->right, &right_ranges);
 484         left_ranges = cast_rl(type, left_ranges);
 485         right_ranges = cast_rl(type, right_ranges);
 486
 487         poss_true = possibly_true_rl(left_ranges, expr->op, right_ranges);
 488         poss_false = possibly_false_rl(left_ranges, expr->op, right_ranges);
 489
 490         free_rl(&left_ranges);
 491         free_rl(&right_ranges);
 492
 493         if (!poss_true && !poss_false)
 494                 return 0;
 495         if (poss_true && !poss_false)
 496                 return 1;
 497         if (!poss_true && poss_false)
 498                 return 2;
 499         return 3;
 500 }
 501
 502 static struct range_list *handle_comparison_rl(struct expression *expr, int implied)
 503 {
 504         sval_t left, right;
 505         int res;
 506
 507         if (get_value(expr->left, &left) && get_value(expr->right, &right)) {
 508                 struct data_range tmp_left, tmp_right;
 509
 510                 tmp_left.min = left;
 511                 tmp_left.max = left;
 512                 tmp_right.min = right;
 513                 tmp_right.max = right;
 514                 if (true_comparison_range(&tmp_left, expr->op, &tmp_right))
 515                         return rl_one();
 516                 return rl_zero();
 517         }
 518
 519         if (implied == RL_EXACT)
 520                 return NULL;
 521
 522         res = do_comparison(expr);
 523         if (res == 1)
 524                 return rl_one();
 525         if (res == 2)
 526                 return rl_zero();
 527
 528         return alloc_rl(zero, one);
 529 }
 530
 531 static struct range_list *handle_logical_rl(struct expression *expr, int implied)
 532 {
 533         sval_t left, right;
 534         int left_known = 0;
 535         int right_known = 0;
 536
 537         if (implied == RL_EXACT) {
 538                 if (get_value(expr->left, &left))
 539                         left_known = 1;
 540                 if (get_value(expr->right, &right))
 541                         right_known = 1;
 542         } else {
 543                 if (get_implied_value(expr->left, &left))
 544                         left_known = 1;
 545                 if (get_implied_value(expr->right, &right))
 546                         right_known = 1;
 547         }
 548
 549         switch (expr->op) {
 550         case SPECIAL_LOGICAL_OR:
 551                 if (left_known && left.value)
 552                         return rl_one();
 553                 if (right_known && right.value)
 554                         return rl_one();
 555                 if (left_known && right_known)
 556                         return rl_zero();
 557                 break;
 558         case SPECIAL_LOGICAL_AND:
 559                 if (left_known && right_known) {
 560                         if (left.value && right.value)
 561                                 return rl_one();
 562                         return rl_zero();
 563                 }
 564                 break;
 565         default:
 566                 return NULL;
 567         }
 568
 569         if (implied == RL_EXACT)
 570                 return NULL;
 571
 572         return alloc_rl(zero, one);
 573 }
 574
 575 static struct range_list *handle_conditional_rl(struct expression *expr, int implied)
 576 {
 577         struct range_list *true_rl, *false_rl;
 578         struct symbol *type;
 579         int final_pass_orig = final_pass;
 580
 581         if (known_condition_true(expr->conditional))
 582                 return _get_rl(expr->cond_true, implied);
 583         if (known_condition_false(expr->conditional))
 584                 return _get_rl(expr->cond_false, implied);
 585
 586         if (implied == RL_EXACT)
 587                 return NULL;
 588
 589         if (implied_condition_true(expr->conditional))
 590                 return _get_rl(expr->cond_true, implied);
 591         if (implied_condition_false(expr->conditional))
 592                 return _get_rl(expr->cond_false, implied);
 593
 594
 595         /* this becomes a problem with deeply nested conditional statements */
 596         if (low_on_memory())
 597                 return NULL;
 598
 599         type = get_type(expr);
 600
 601         __push_fake_cur_stree();
 602         final_pass = 0;
 603         __split_whole_condition(expr->conditional);
 604         true_rl = _get_rl(expr->cond_true, implied);
 605         __push_true_states();
 606         __use_false_states();
 607         false_rl = _get_rl(expr->cond_false, implied);
 608         __merge_true_states();
 609         __free_fake_cur_stree();
 610         final_pass = final_pass_orig;
 611
 612         if (!true_rl || !false_rl)
 613                 return NULL;
 614         true_rl = cast_rl(type, true_rl);
 615         false_rl = cast_rl(type, false_rl);
 616
 617         return rl_union(true_rl, false_rl);
 618 }
 619
 620 static int get_fuzzy_max_helper(struct expression *expr, sval_t *max)
 621 {
 622         struct smatch_state *state;
 623         sval_t sval;
 624
 625         if (get_hard_max(expr, &sval)) {
 626                 *max = sval;
 627                 return 1;
 628         }
 629
 630         state = get_state_expr(SMATCH_EXTRA, expr);
 631         if (!state || !estate_has_fuzzy_max(state))
 632                 return 0;
 633         *max = sval_cast(get_type(expr), estate_get_fuzzy_max(state));
 634         return 1;
 635 }
 636
 637 static int get_fuzzy_min_helper(struct expression *expr, sval_t *min)
 638 {
 639         struct smatch_state *state;
 640         sval_t sval;
 641
 642         state = get_state_expr(SMATCH_EXTRA, expr);
 643         if (!state || !estate_rl(state))
 644                 return 0;
 645
 646         sval = estate_min(state);
 647         if (sval_is_negative(sval) && sval_is_min(sval))
 648                 return 0;
 649
 650         if (sval_is_max(sval))
 651                 return 0;
 652
 653         *min = sval_cast(get_type(expr), sval);
 654         return 1;
 655 }
 656
 657 int get_const_value(struct expression *expr, sval_t *sval)
 658 {
 659         struct symbol *sym;
 660         sval_t right;
 661
 662         if (expr->type != EXPR_SYMBOL || !expr->symbol)
 663                 return 0;
 664         sym = expr->symbol;
 665         if (!(sym->ctype.modifiers & MOD_CONST))
 666                 return 0;
 667         if (get_value(sym->initializer, &right)) {
 668                 *sval = sval_cast(get_type(expr), right);
 669                 return 1;
 670         }
 671         return 0;
 672 }
 673
 674 static struct range_list *handle_variable(struct expression *expr, int implied)
 675 {
 676         struct smatch_state *state;
 677         struct range_list *rl;
 678         sval_t sval, min, max;
 679
 680         if (get_const_value(expr, &sval))
 681                 return alloc_rl(sval, sval);
 682
 683         switch (implied) {
 684         case RL_EXACT:
 685                 return NULL;
 686         case RL_HARD:
 687         case RL_IMPLIED:
 688         case RL_ABSOLUTE:
 689                 state = get_state_expr(SMATCH_EXTRA, expr);
 690                 if (!state || !state->data) {
 691                         if (implied == RL_HARD)
 692                                 return NULL;
 693                         if (get_local_rl(expr, &rl))
 694                                 return rl;
 695                         if (get_db_type_rl(expr, &rl))
 696                                 return rl;
 697                         return NULL;
 698                 }
 699                 if (implied == RL_HARD && !estate_has_hard_max(state))
 700                         return NULL;
 701                 return clone_rl(estate_rl(state));
 702         case RL_FUZZY:
 703                 if (!get_fuzzy_min_helper(expr, &min))
 704                         min = sval_type_min(get_type(expr));
 705                 if (!get_fuzzy_max_helper(expr, &max))
 706                         return NULL;
 707                 /* fuzzy ranges are often inverted */
 708                 if (sval_cmp(min, max) > 0) {
 709                         sval = min;
 710                         min = max;
 711                         max = sval;
 712                 }
 713                 return alloc_rl(min, max);
 714         }
 715         return NULL;
 716 }
 717
 718 static sval_t handle_sizeof(struct expression *expr)
 719 {
 720         struct symbol *sym;
 721         sval_t ret;
 722
 723         ret = sval_blank(expr);
 724         sym = expr->cast_type;
 725         if (!sym) {
 726                 sym = evaluate_expression(expr->cast_expression);
 727                 /*
 728                  * Expressions of restricted types will possibly get
 729                  * promoted - check that here
 730                  */
 731                 if (is_restricted_type(sym)) {
 732                         if (type_bits(sym) < bits_in_int)
 733                                 sym = &int_ctype;
 734                 } else if (is_fouled_type(sym)) {
 735                         sym = &int_ctype;
 736                 }
 737         }
 738         examine_symbol_type(sym);
 739
 740         ret.type = size_t_ctype;
 741         if (type_bits(sym) <= 0) /* sizeof(void) */ {
 742                 if (get_real_base_type(sym) == &void_ctype)
 743                         ret.value = 1;
 744                 else
 745                         ret.value = 0;
 746         } else
 747                 ret.value = type_bytes(sym);
 748
 749         return ret;
 750 }
 751
 752 static struct range_list *handle_call_rl(struct expression *expr, int implied)
 753 {
 754         struct range_list *rl;
 755
 756         if (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY)
 757                 return NULL;
 758
 759         if (get_implied_return(expr, &rl))
 760                 return rl;
 761         return db_return_vals(expr);
 762 }
 763
 764 static struct range_list *handle_cast(struct expression *expr, int implied)
 765 {
 766         struct range_list *rl;
 767         struct symbol *type;
 768
 769         type = get_type(expr);
 770         rl = _get_rl(expr->cast_expression, implied);
 771         if (rl)
 772                 return cast_rl(type, rl);
 773         if (implied == RL_ABSOLUTE)
 774                 return alloc_whole_rl(type);
 775         if (implied == RL_IMPLIED && type &&
 776             type_bits(type) > 0 && type_bits(type) < 32)
 777                 return alloc_whole_rl(type);
 778         return NULL;
 779 }
 780
 781 static struct range_list *_get_rl(struct expression *expr, int implied)
 782 {
 783         struct range_list *rl;
 784         struct symbol *type;
 785         sval_t sval;
 786
 787         expr = strip_parens(expr);
 788         if (!expr)
 789                 return NULL;
 790
 791         switch(expr->type) {
 792         case EXPR_CAST:
 793         case EXPR_FORCE_CAST:
 794         case EXPR_IMPLIED_CAST:
 795                 rl = handle_cast(expr, implied);
 796                 goto out_cast;
 797         }
 798
 799         expr = strip_expr(expr);
 800         if (!expr)
 801                 return NULL;
 802         type = get_type(expr);
 803
 804         switch (expr->type) {
 805         case EXPR_VALUE:
 806                 sval = sval_from_val(expr, expr->value);
 807                 rl = alloc_rl(sval, sval);
 808                 break;
 809         case EXPR_PREOP:
 810                 rl = handle_preop_rl(expr, implied);
 811                 break;
 812         case EXPR_POSTOP:
 813                 rl = _get_rl(expr->unop, implied);
 814                 break;
 815         case EXPR_BINOP:
 816                 rl = handle_binop_rl(expr, implied);
 817                 break;
 818         case EXPR_COMPARE:
 819                 rl = handle_comparison_rl(expr, implied);
 820                 break;
 821         case EXPR_LOGICAL:
 822                 rl = handle_logical_rl(expr, implied);
 823                 break;
 824         case EXPR_PTRSIZEOF:
 825         case EXPR_SIZEOF:
 826                 sval = handle_sizeof(expr);
 827                 rl = alloc_rl(sval, sval);
 828                 break;
 829         case EXPR_SELECT:
 830         case EXPR_CONDITIONAL:
 831                 rl = handle_conditional_rl(expr, implied);
 832                 break;
 833         case EXPR_CALL:
 834                 rl = handle_call_rl(expr, implied);
 835                 break;
 836         default:
 837                 rl = handle_variable(expr, implied);
 838         }
 839
 840 out_cast:
 841         if (rl)
 842                 return rl;
 843         if (type && implied == RL_ABSOLUTE)
 844                 return alloc_whole_rl(type);
 845         return NULL;
 846 }
 847
 848 /* returns 1 if it can get a value literal or else returns 0 */
 849 int get_value(struct expression *expr, sval_t *sval)
 850 {
 851         struct range_list *rl;
 852
 853         rl = _get_rl(expr, RL_EXACT);
 854         if (!rl_to_sval(rl, sval))
 855                 return 0;
 856         return 1;
 857 }
 858
 859 int get_implied_value(struct expression *expr, sval_t *sval)
 860 {
 861         struct range_list *rl;
 862
 863         rl =  _get_rl(expr, RL_IMPLIED);
 864         if (!rl_to_sval(rl, sval))
 865                 return 0;
 866         return 1;
 867 }
 868
 869 int get_implied_min(struct expression *expr, sval_t *sval)
 870 {
 871         struct range_list *rl;
 872
 873         rl =  _get_rl(expr, RL_IMPLIED);
 874         if (!rl)
 875                 return 0;
 876         *sval = rl_min(rl);
 877         return 1;
 878 }
 879
 880 int get_implied_max(struct expression *expr, sval_t *sval)
 881 {
 882         struct range_list *rl;
 883
 884         rl =  _get_rl(expr, RL_IMPLIED);
 885         if (!rl)
 886                 return 0;
 887         *sval = rl_max(rl);
 888         return 1;
 889 }
 890
 891 int get_implied_rl(struct expression *expr, struct range_list **rl)
 892 {
 893         *rl = _get_rl(expr, RL_IMPLIED);
 894         if (*rl)
 895                 return 1;
 896         return 0;
 897 }
 898
 899 int get_absolute_rl(struct expression *expr, struct range_list **rl)
 900 {
 901         *rl = _get_rl(expr, RL_ABSOLUTE);
 902         if (!*rl)
 903                 *rl = alloc_whole_rl(get_type(expr));
 904         return 1;
 905 }
 906
 907 int get_implied_rl_var_sym(const char *var, struct symbol *sym, struct range_list **rl)
 908 {
 909         struct smatch_state *state;
 910
 911         state = get_state(SMATCH_EXTRA, var, sym);
 912         *rl = estate_rl(state);
 913         if (*rl)
 914                 return 1;
 915         return 0;
 916 }
 917
 918 int get_hard_max(struct expression *expr, sval_t *sval)
 919 {
 920         struct range_list *rl;
 921
 922         rl =  _get_rl(expr, RL_HARD);
 923         if (!rl)
 924                 return 0;
 925         *sval = rl_max(rl);
 926         return 1;
 927 }
 928
 929 int get_fuzzy_min(struct expression *expr, sval_t *sval)
 930 {
 931         struct range_list *rl;
 932         sval_t tmp;
 933
 934         rl =  _get_rl(expr, RL_FUZZY);
 935         if (!rl)
 936                 return 0;
 937         tmp = rl_min(rl);
 938         if (sval_is_negative(tmp) && sval_is_min(tmp))
 939                 return 0;
 940         *sval = tmp;
 941         return 1;
 942 }
 943
 944 int get_fuzzy_max(struct expression *expr, sval_t *sval)
 945 {
 946         struct range_list *rl;
 947         sval_t max;
 948
 949         rl =  _get_rl(expr, RL_FUZZY);
 950         if (!rl)
 951                 return 0;
 952         max = rl_max(rl);
 953         if (max.uvalue > INT_MAX - 10000)
 954                 return 0;
 955         *sval = max;
 956         return 1;
 957 }
 958
 959 int get_absolute_min(struct expression *expr, sval_t *sval)
 960 {
 961         struct range_list *rl;
 962         struct symbol *type;
 963
 964         type = get_type(expr);
 965         if (!type)
 966                 type = &llong_ctype;  // FIXME: this is wrong but places assume get type can't fail.
 967         rl = _get_rl(expr, RL_ABSOLUTE);
 968         if (rl)
 969                 *sval = rl_min(rl);
 970         else
 971                 *sval = sval_type_min(type);
 972
 973         if (sval_cmp(*sval, sval_type_min(type)) < 0)
 974                 *sval = sval_type_min(type);
 975         return 1;
 976 }
 977
 978 int get_absolute_max(struct expression *expr, sval_t *sval)
 979 {
 980         struct range_list *rl;
 981         struct symbol *type;
 982
 983         type = get_type(expr);
 984         if (!type)
 985                 type = &llong_ctype;
 986         rl = _get_rl(expr, RL_ABSOLUTE);
 987         if (rl)
 988                 *sval = rl_max(rl);
 989         else
 990                 *sval = sval_type_max(type);
 991
 992         if (sval_cmp(sval_type_max(type), *sval) < 0)
 993                 *sval = sval_type_max(type);
 994         return 1;
 995 }
 996
 997 int known_condition_true(struct expression *expr)
 998 {
 999         sval_t tmp;
1000
1001         if (!expr)
1002                 return 0;
1003
1004         if (get_value(expr, &tmp) && tmp.value)
1005                 return 1;
1006
1007         return 0;
1008 }
1009
1010 int known_condition_false(struct expression *expr)
1011 {
1012         if (!expr)
1013                 return 0;
1014
1015         if (is_zero(expr))
1016                 return 1;
1017
1018         if (expr->type == EXPR_CALL) {
1019                 if (sym_name_is("__builtin_constant_p", expr->fn))
1020                         return 1;
1021         }
1022         return 0;
1023 }
1024
1025 int implied_condition_true(struct expression *expr)
1026 {
1027         sval_t tmp;
1028
1029         if (!expr)
1030                 return 0;
1031
1032         if (known_condition_true(expr))
1033                 return 1;
1034         if (get_implied_value(expr, &tmp) && tmp.value)
1035                 return 1;
1036
1037         if (expr->type == EXPR_POSTOP)
1038                 return implied_condition_true(expr->unop);
1039
1040         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
1041                 return implied_not_equal(expr->unop, 1);
1042         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
1043                 return implied_not_equal(expr->unop, -1);
1044
1045         expr = strip_expr(expr);
1046         switch (expr->type) {
1047         case EXPR_COMPARE:
1048                 if (do_comparison(expr) == 1)
1049                         return 1;
1050                 break;
1051         case EXPR_PREOP:
1052                 if (expr->op == '!') {
1053                         if (implied_condition_false(expr->unop))
1054                                 return 1;
1055                         break;
1056                 }
1057                 break;
1058         default:
1059                 if (implied_not_equal(expr, 0) == 1)
1060                         return 1;
1061                 break;
1062         }
1063         return 0;
1064 }
1065
1066 int implied_condition_false(struct expression *expr)
1067 {
1068         struct expression *tmp;
1069         sval_t sval;
1070
1071         if (!expr)
1072                 return 0;
1073
1074         if (known_condition_false(expr))
1075                 return 1;
1076
1077         switch (expr->type) {
1078         case EXPR_COMPARE:
1079                 if (do_comparison(expr) == 2)
1080                         return 1;
1081         case EXPR_PREOP:
1082                 if (expr->op == '!') {
1083                         if (implied_condition_true(expr->unop))
1084                                 return 1;
1085                         break;
1086                 }
1087                 tmp = strip_expr(expr);
1088                 if (tmp != expr)
1089                         return implied_condition_false(tmp);
1090                 break;
1091         default:
1092                 if (get_implied_value(expr, &sval) && sval.value == 0)
1093                         return 1;
1094                 break;
1095         }
1096         return 0;
1097 }