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