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