smatch_math.c

   1 /*
   2  * Copyright (C) 2010 Dan Carpenter.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
  16  */
  17
  18 #include "symbol.h"
  19 #include "smatch.h"
  20 #include "smatch_slist.h"
  21 #include "smatch_extra.h"
  22
  23 static struct range_list *_get_rl(struct expression *expr, int implied, int *recurse_cnt);
  24 static struct range_list *handle_variable(struct expression *expr, int implied, int *recurse_cnt);
  25 static struct range_list *(*custom_handle_variable)(struct expression *expr);
  26
  27 static int get_implied_value_internal(struct expression *expr, sval_t *sval, int *recurse_cnt);
  28 static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt);
  29
  30 static sval_t zero  = {.type = &int_ctype, {.value = 0} };
  31 static sval_t one   = {.type = &int_ctype, {.value = 1} };
  32
  33 struct range_list *rl_zero(void)
  34 {
  35         static struct range_list *zero_perm;
  36
  37         if (!zero_perm)
  38                 zero_perm = clone_rl_permanent(alloc_rl(zero, zero));
  39         return zero_perm;
  40 }
  41
  42 struct range_list *rl_one(void)
  43 {
  44         static struct range_list *one_perm;
  45
  46         if (!one_perm)
  47                 one_perm = clone_rl_permanent(alloc_rl(one, one));
  48
  49         return one_perm;
  50 }
  51
  52 enum {
  53         RL_EXACT,
  54         RL_HARD,
  55         RL_FUZZY,
  56         RL_IMPLIED,
  57         RL_ABSOLUTE,
  58         RL_REAL_ABSOLUTE,
  59 };
  60
  61 static struct range_list *last_stmt_rl(struct statement *stmt, int implied, int *recurse_cnt)
  62 {
  63         struct expression *expr;
  64
  65         if (!stmt)
  66                 return NULL;
  67
  68         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
  69         if (stmt->type == STMT_LABEL) {
  70                 if (stmt->label_statement &&
  71                     stmt->label_statement->type == STMT_EXPRESSION)
  72                         expr = stmt->label_statement->expression;
  73                 else
  74                         return NULL;
  75         } else if (stmt->type == STMT_EXPRESSION) {
  76                 expr = stmt->expression;
  77         } else {
  78                 return NULL;
  79         }
  80         return _get_rl(expr, implied, recurse_cnt);
  81 }
  82
  83 static struct range_list *handle_expression_statement_rl(struct expression *expr, int implied, int *recurse_cnt)
  84 {
  85         return last_stmt_rl(get_expression_statement(expr), implied, recurse_cnt);
  86 }
  87
  88 static struct range_list *handle_ampersand_rl(struct expression *expr, int implied, int *recurse_cnt)
  89 {
  90         struct range_list *rl;
  91
  92         if (implied == RL_EXACT || implied == RL_HARD)
  93                 return NULL;
  94         if (get_address_rl(expr, &rl))
  95                 return rl;
  96         return alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
  97 }
  98
  99 static struct range_list *handle_negate_rl(struct expression *expr, int implied, int *recurse_cnt)
 100 {
 101         if (known_condition_true(expr->unop))
 102                 return rl_zero();
 103         if (known_condition_false(expr->unop))
 104                 return rl_one();
 105
 106         if (implied == RL_EXACT)
 107                 return NULL;
 108
 109         if (implied_condition_true(expr->unop))
 110                 return rl_zero();
 111         if (implied_condition_false(expr->unop))
 112                 return rl_one();
 113         return alloc_rl(zero, one);
 114 }
 115
 116 static struct range_list *handle_bitwise_negate(struct expression *expr, int implied, int *recurse_cnt)
 117 {
 118         struct range_list *rl;
 119         sval_t sval;
 120
 121         rl = _get_rl(expr->unop, implied, recurse_cnt);
 122         if (!rl_to_sval(rl, &sval))
 123                 return NULL;
 124         sval = sval_preop(sval, '~');
 125         sval_cast(get_type(expr->unop), sval);
 126         return alloc_rl(sval, sval);
 127 }
 128
 129 static struct range_list *handle_minus_preop(struct expression *expr, int implied, int *recurse_cnt)
 130 {
 131         struct range_list *rl;
 132         sval_t min, max;
 133
 134         rl = _get_rl(expr->unop, implied, recurse_cnt);
 135         min = sval_preop(rl_max(rl), '-');
 136         max = sval_preop(rl_min(rl), '-');
 137         return alloc_rl(min, max);
 138 }
 139
 140 static struct range_list *handle_preop_rl(struct expression *expr, int implied, int *recurse_cnt)
 141 {
 142         switch (expr->op) {
 143         case '&':
 144                 return handle_ampersand_rl(expr, implied, recurse_cnt);
 145         case '!':
 146                 return handle_negate_rl(expr, implied, recurse_cnt);
 147         case '~':
 148                 return handle_bitwise_negate(expr, implied, recurse_cnt);
 149         case '-':
 150                 return handle_minus_preop(expr, implied, recurse_cnt);
 151         case '*':
 152                 return handle_variable(expr, implied, recurse_cnt);
 153         case '(':
 154                 return handle_expression_statement_rl(expr, implied, recurse_cnt);
 155         default:
 156                 return NULL;
 157         }
 158 }
 159
 160 static struct range_list *handle_divide_rl(struct expression *expr, int implied, int *recurse_cnt)
 161 {
 162         struct range_list *left_rl, *right_rl;
 163         struct symbol *type;
 164
 165         type = get_type(expr);
 166
 167         left_rl = _get_rl(expr->left, implied, recurse_cnt);
 168         left_rl = cast_rl(type, left_rl);
 169         right_rl = _get_rl(expr->right, implied, recurse_cnt);
 170         right_rl = cast_rl(type, right_rl);
 171
 172         if (!left_rl || !right_rl)
 173                 return NULL;
 174
 175         if (implied != RL_REAL_ABSOLUTE) {
 176                 if (is_whole_rl(left_rl) || is_whole_rl(right_rl))
 177                         return NULL;
 178         }
 179
 180         return rl_binop(left_rl, '/', right_rl);
 181 }
 182
 183 static int handle_offset_subtraction(struct expression *expr)
 184 {
 185         struct expression *left, *right;
 186         struct symbol *left_sym, *right_sym;
 187         struct symbol *type;
 188         int left_offset, right_offset;
 189
 190         type = get_type(expr);
 191         if (!type || type->type != SYM_PTR)
 192                 return -1;
 193         type = get_real_base_type(type);
 194         if (!type || (type_bits(type) != 8 && (type != &void_ctype)))
 195                 return -1;
 196
 197         left = strip_expr(expr->left);
 198         right = strip_expr(expr->right);
 199
 200         if (left->type != EXPR_PREOP || left->op != '&')
 201                 return -1;
 202         left = strip_expr(left->unop);
 203
 204         left_sym = expr_to_sym(left);
 205         right_sym = expr_to_sym(right);
 206         if (!left_sym || left_sym != right_sym)
 207                 return -1;
 208
 209         left_offset = get_member_offset_from_deref(left);
 210         if (right->type == EXPR_SYMBOL)
 211                 right_offset = 0;
 212         else {
 213                 if (right->type != EXPR_PREOP || right->op != '&')
 214                         return -1;
 215                 right = strip_expr(right->unop);
 216                 right_offset = get_member_offset_from_deref(right);
 217         }
 218         if (left_offset < 0 || right_offset < 0)
 219                 return -1;
 220
 221         return left_offset - right_offset;
 222 }
 223
 224 static struct range_list *handle_subtract_rl(struct expression *expr, int implied, int *recurse_cnt)
 225 {
 226         struct symbol *type;
 227         struct range_list *left_orig, *right_orig;
 228         struct range_list *left_rl, *right_rl;
 229         sval_t max, min, tmp;
 230         int comparison;
 231         int offset;
 232
 233         type = get_type(expr);
 234
 235         offset = handle_offset_subtraction(expr);
 236         if (offset >= 0) {
 237                 tmp.type = type;
 238                 tmp.value = offset;
 239
 240                 return alloc_rl(tmp, tmp);
 241         }
 242
 243         comparison = get_comparison(expr->left, expr->right);
 244
 245         left_orig = _get_rl(expr->left, implied, recurse_cnt);
 246         left_rl = cast_rl(type, left_orig);
 247         right_orig = _get_rl(expr->right, implied, recurse_cnt);
 248         right_rl = cast_rl(type, right_orig);
 249
 250         if ((!left_rl || !right_rl) &&
 251             (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY))
 252                 return NULL;
 253
 254         if (!left_rl)
 255                 left_rl = alloc_whole_rl(type);
 256         if (!right_rl)
 257                 right_rl = alloc_whole_rl(type);
 258
 259         /* negative values complicate everything fix this later */
 260         if (sval_is_negative(rl_min(right_rl)))
 261                 return NULL;
 262         max = rl_max(left_rl);
 263         min = sval_type_min(type);
 264
 265         switch (comparison) {
 266         case '>':
 267         case SPECIAL_UNSIGNED_GT:
 268                 min = sval_type_val(type, 1);
 269                 max = rl_max(left_rl);
 270                 break;
 271         case SPECIAL_GTE:
 272         case SPECIAL_UNSIGNED_GTE:
 273                 min = sval_type_val(type, 0);
 274                 max = rl_max(left_rl);
 275                 break;
 276         case SPECIAL_EQUAL:
 277                 min = sval_type_val(type, 0);
 278                 max = sval_type_val(type, 0);
 279                 break;
 280         case '<':
 281         case SPECIAL_UNSIGNED_LT:
 282                 max = sval_type_val(type, -1);
 283                 break;
 284         case SPECIAL_LTE:
 285         case SPECIAL_UNSIGNED_LTE:
 286                 max = sval_type_val(type, 0);
 287                 break;
 288         default:
 289                 if (!left_orig || !right_orig)
 290                         return NULL;
 291                 return rl_binop(left_rl, '-', right_rl);
 292         }
 293
 294         if (!sval_binop_overflows(rl_min(left_rl), '-', rl_max(right_rl))) {
 295                 tmp = sval_binop(rl_min(left_rl), '-', rl_max(right_rl));
 296                 if (sval_cmp(tmp, min) > 0)
 297                         min = tmp;
 298         }
 299
 300         if (!sval_is_max(rl_max(left_rl))) {
 301                 tmp = sval_binop(rl_max(left_rl), '-', rl_min(right_rl));
 302                 if (sval_cmp(tmp, max) < 0)
 303                         max = tmp;
 304         }
 305
 306         if (sval_is_min(min) && sval_is_max(max))
 307                 return NULL;
 308
 309         return cast_rl(type, alloc_rl(min, max));
 310 }
 311
 312 static struct range_list *handle_mod_rl(struct expression *expr, int implied, int *recurse_cnt)
 313 {
 314         struct range_list *rl;
 315         sval_t left, right, sval;
 316
 317         if (implied == RL_EXACT) {
 318                 if (!get_implied_value(expr->right, &right))
 319                         return NULL;
 320                 if (!get_implied_value(expr->left, &left))
 321                         return NULL;
 322                 sval = sval_binop(left, '%', right);
 323                 return alloc_rl(sval, sval);
 324         }
 325         /* if we can't figure out the right side it's probably hopeless */
 326         if (!get_implied_value_internal(expr->right, &right, recurse_cnt))
 327                 return NULL;
 328
 329         right = sval_cast(get_type(expr), right);
 330         right.value--;
 331
 332         rl = _get_rl(expr->left, implied, recurse_cnt);
 333         if (rl && rl_max(rl).uvalue < right.uvalue)
 334                 right.uvalue = rl_max(rl).uvalue;
 335
 336         return alloc_rl(sval_cast(right.type, zero), right);
 337 }
 338
 339 static sval_t sval_lowest_set_bit(sval_t sval)
 340 {
 341         int i;
 342         int found = 0;
 343
 344         for (i = 0; i < 64; i++) {
 345                 if (sval.uvalue & 1ULL << i) {
 346                         if (!found++)
 347                                 continue;
 348                         sval.uvalue &= ~(1ULL << i);
 349                 }
 350         }
 351         return sval;
 352 }
 353
 354 static struct range_list *handle_bitwise_AND(struct expression *expr, int implied, int *recurse_cnt)
 355 {
 356         struct symbol *type;
 357         struct range_list *left_rl, *right_rl;
 358         sval_t known;
 359         int new_recurse;
 360
 361         if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE)
 362                 return NULL;
 363
 364         type = get_type(expr);
 365
 366         if (get_implied_value_internal(expr->left, &known, recurse_cnt)) {
 367                 sval_t min;
 368
 369                 min = sval_lowest_set_bit(known);
 370                 left_rl = alloc_rl(min, known);
 371                 left_rl = cast_rl(type, left_rl);
 372                 add_range(&left_rl, sval_type_val(type, 0), sval_type_val(type, 0));
 373         } else {
 374                 left_rl = _get_rl(expr->left, implied, recurse_cnt);
 375                 if (left_rl) {
 376                         left_rl = cast_rl(type, left_rl);
 377                         left_rl = alloc_rl(sval_type_val(type, 0), rl_max(left_rl));
 378                 } else {
 379                         if (implied == RL_HARD)
 380                                 return NULL;
 381                         left_rl = alloc_whole_rl(type);
 382                 }
 383         }
 384
 385         new_recurse = *recurse_cnt;
 386         if (*recurse_cnt >= 200)
 387                 new_recurse = 100;  /* Let's try super hard to get the mask */
 388         if (get_implied_value_internal(expr->right, &known, &new_recurse)) {
 389                 sval_t min, left_max, mod;
 390
 391                 *recurse_cnt = new_recurse;
 392
 393                 min = sval_lowest_set_bit(known);
 394                 right_rl = alloc_rl(min, known);
 395                 right_rl = cast_rl(type, right_rl);
 396                 add_range(&right_rl, sval_type_val(type, 0), sval_type_val(type, 0));
 397
 398                 if (min.value != 0) {
 399                         left_max = rl_max(left_rl);
 400                         mod = sval_binop(left_max, '%', min);
 401                         if (mod.value) {
 402                                 left_max = sval_binop(left_max, '-', mod);
 403                                 left_max.value++;
 404                                 if (left_max.value > 0 && sval_cmp(left_max, rl_max(left_rl)) < 0)
 405                                         left_rl = remove_range(left_rl, left_max, rl_max(left_rl));
 406                         }
 407                 }
 408         } else {
 409                 right_rl = _get_rl(expr->right, implied, recurse_cnt);
 410                 if (right_rl) {
 411                         right_rl = cast_rl(type, right_rl);
 412                         right_rl = alloc_rl(sval_type_val(type, 0), rl_max(right_rl));
 413                 } else {
 414                         if (implied == RL_HARD)
 415                                 return NULL;
 416                         right_rl = alloc_whole_rl(type);
 417                 }
 418         }
 419
 420         return rl_intersection(left_rl, right_rl);
 421 }
 422
 423 static struct range_list *use_rl_binop(struct expression *expr, int implied, int *recurse_cnt)
 424 {
 425         struct symbol *type;
 426         struct range_list *left_rl, *right_rl;
 427
 428         if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE)
 429                 return NULL;
 430
 431         type = get_type(expr);
 432
 433         get_absolute_rl_internal(expr->left, &left_rl, recurse_cnt);
 434         get_absolute_rl_internal(expr->right, &right_rl, recurse_cnt);
 435         left_rl = cast_rl(type, left_rl);
 436         right_rl = cast_rl(type, right_rl);
 437         if (!left_rl || !right_rl)
 438                 return NULL;
 439
 440         return rl_binop(left_rl, expr->op, right_rl);
 441 }
 442
 443 static struct range_list *handle_right_shift(struct expression *expr, int implied, int *recurse_cnt)
 444 {
 445         struct range_list *left_rl;
 446         sval_t right;
 447         sval_t min, max;
 448
 449         if (implied == RL_EXACT || implied == RL_HARD)
 450                 return NULL;
 451
 452         left_rl = _get_rl(expr->left, implied, recurse_cnt);
 453         if (left_rl) {
 454                 max = rl_max(left_rl);
 455                 min = rl_min(left_rl);
 456         } else {
 457                 if (implied == RL_FUZZY)
 458                         return NULL;
 459                 max = sval_type_max(get_type(expr->left));
 460                 min = sval_type_val(get_type(expr->left), 0);
 461         }
 462
 463         if (get_implied_value_internal(expr->right, &right, recurse_cnt)) {
 464                 min = sval_binop(min, SPECIAL_RIGHTSHIFT, right);
 465                 max = sval_binop(max, SPECIAL_RIGHTSHIFT, right);
 466         } else if (!sval_is_negative(min)) {
 467                 min.value = 0;
 468                 max = sval_type_max(max.type);
 469         } else {
 470                 return NULL;
 471         }
 472
 473         return alloc_rl(min, max);
 474 }
 475
 476 static struct range_list *handle_left_shift(struct expression *expr, int implied, int *recurse_cnt)
 477 {
 478         struct range_list *left_rl, *res;
 479         sval_t right;
 480         sval_t min, max;
 481         int add_zero = 0;
 482
 483         if (implied == RL_EXACT || implied == RL_HARD)
 484                 return NULL;
 485         /* this is hopeless without the right side */
 486         if (!get_implied_value_internal(expr->right, &right, recurse_cnt))
 487                 return NULL;
 488         left_rl = _get_rl(expr->left, implied, recurse_cnt);
 489         if (left_rl) {
 490                 max = rl_max(left_rl);
 491                 min = rl_min(left_rl);
 492                 if (min.value == 0) {
 493                         min.value = 1;
 494                         add_zero = 1;
 495                 }
 496         } else {
 497                 if (implied == RL_FUZZY)
 498                         return NULL;
 499                 max = sval_type_max(get_type(expr->left));
 500                 min = sval_type_val(get_type(expr->left), 1);
 501                 add_zero = 1;
 502         }
 503
 504         max = sval_binop(max, SPECIAL_LEFTSHIFT, right);
 505         min = sval_binop(min, SPECIAL_LEFTSHIFT, right);
 506         res = alloc_rl(min, max);
 507         if (add_zero)
 508                 res = rl_union(res, rl_zero());
 509         return res;
 510 }
 511
 512 static struct range_list *handle_known_binop(struct expression *expr)
 513 {
 514         sval_t left, right;
 515
 516         if (!get_value(expr->left, &left))
 517                 return NULL;
 518         if (!get_value(expr->right, &right))
 519                 return NULL;
 520         left = sval_binop(left, expr->op, right);
 521         return alloc_rl(left, left);
 522 }
 523
 524 static int has_actual_ranges(struct range_list *rl)
 525 {
 526         struct data_range *tmp;
 527
 528         FOR_EACH_PTR(rl, tmp) {
 529                 if (sval_cmp(tmp->min, tmp->max) != 0)
 530                         return 1;
 531         } END_FOR_EACH_PTR(tmp);
 532         return 0;
 533 }
 534
 535 static struct range_list *handle_implied_binop(struct range_list *left_rl, int op, struct range_list *right_rl)
 536 {
 537         struct range_list *res_rl;
 538         struct data_range *left_drange, *right_drange;
 539         sval_t res;
 540
 541         if (!left_rl || !right_rl)
 542                 return NULL;
 543         if (has_actual_ranges(left_rl))
 544                 return NULL;
 545         if (has_actual_ranges(right_rl))
 546                 return NULL;
 547
 548         if (ptr_list_size((struct ptr_list *)left_rl) * ptr_list_size((struct ptr_list *)right_rl) > 20)
 549                 return NULL;
 550
 551         res_rl = NULL;
 552
 553         FOR_EACH_PTR(left_rl, left_drange) {
 554                 FOR_EACH_PTR(right_rl, right_drange) {
 555                         if ((op == '%' || op == '/') &&
 556                             right_drange->min.value == 0)
 557                                 return NULL;
 558                         res = sval_binop(left_drange->min, op, right_drange->min);
 559                         add_range(&res_rl, res, res);
 560                 } END_FOR_EACH_PTR(right_drange);
 561         } END_FOR_EACH_PTR(left_drange);
 562
 563         return res_rl;
 564 }
 565
 566 static struct range_list *handle_binop_rl(struct expression *expr, int implied, int *recurse_cnt)
 567 {
 568         struct smatch_state *state;
 569         struct symbol *type;
 570         struct range_list *left_rl, *right_rl, *rl;
 571         sval_t min, max;
 572
 573         rl = handle_known_binop(expr);
 574         if (rl)
 575                 return rl;
 576         if (implied == RL_EXACT)
 577                 return NULL;
 578
 579         if (custom_handle_variable) {
 580                 rl = custom_handle_variable(expr);
 581                 if (rl)
 582                         return rl;
 583         }
 584
 585         state = get_extra_state(expr);
 586         if (state && !is_whole_rl(estate_rl(state))) {
 587                 if (implied != RL_HARD || estate_has_hard_max(state))
 588                         return clone_rl(estate_rl(state));
 589         }
 590
 591         type = get_type(expr);
 592         left_rl = _get_rl(expr->left, implied, recurse_cnt);
 593         left_rl = cast_rl(type, left_rl);
 594         right_rl = _get_rl(expr->right, implied, recurse_cnt);
 595         right_rl = cast_rl(type, right_rl);
 596
 597         if (!left_rl && !right_rl)
 598                 return NULL;
 599
 600         rl = handle_implied_binop(left_rl, expr->op, right_rl);
 601         if (rl)
 602                 return rl;
 603
 604         switch (expr->op) {
 605         case '%':
 606                 return handle_mod_rl(expr, implied, recurse_cnt);
 607         case '&':
 608                 return handle_bitwise_AND(expr, implied, recurse_cnt);
 609         case '|':
 610         case '^':
 611                 return use_rl_binop(expr, implied, recurse_cnt);
 612         case SPECIAL_RIGHTSHIFT:
 613                 return handle_right_shift(expr, implied, recurse_cnt);
 614         case SPECIAL_LEFTSHIFT:
 615                 return handle_left_shift(expr, implied, recurse_cnt);
 616         case '-':
 617                 return handle_subtract_rl(expr, implied, recurse_cnt);
 618         case '/':
 619                 return handle_divide_rl(expr, implied, recurse_cnt);
 620         }
 621
 622         if (!left_rl || !right_rl)
 623                 return NULL;
 624
 625         if (sval_binop_overflows(rl_min(left_rl), expr->op, rl_min(right_rl)))
 626                 return NULL;
 627         if (sval_binop_overflows(rl_max(left_rl), expr->op, rl_max(right_rl)))
 628                 return NULL;
 629
 630         min = sval_binop(rl_min(left_rl), expr->op, rl_min(right_rl));
 631         max = sval_binop(rl_max(left_rl), expr->op, rl_max(right_rl));
 632
 633         return alloc_rl(min, max);
 634 }
 635
 636 static int do_comparison(struct expression *expr)
 637 {
 638         struct range_list *left_ranges = NULL;
 639         struct range_list *right_ranges = NULL;
 640         int poss_true, poss_false;
 641         struct symbol *type;
 642
 643         type = get_type(expr);
 644         get_absolute_rl(expr->left, &left_ranges);
 645         get_absolute_rl(expr->right, &right_ranges);
 646
 647         left_ranges = cast_rl(type, left_ranges);
 648         right_ranges = cast_rl(type, right_ranges);
 649
 650         poss_true = possibly_true_rl(left_ranges, expr->op, right_ranges);
 651         poss_false = possibly_false_rl(left_ranges, expr->op, right_ranges);
 652
 653         if (!poss_true && !poss_false)
 654                 return 0x0;
 655         if (poss_true && !poss_false)
 656                 return 0x1;
 657         if (!poss_true && poss_false)
 658                 return 0x2;
 659         return 0x3;
 660 }
 661
 662 static struct range_list *handle_comparison_rl(struct expression *expr, int implied, int *recurse_cnt)
 663 {
 664         sval_t left, right;
 665         int res;
 666
 667         if (expr->op == SPECIAL_EQUAL && expr->left->type == EXPR_TYPE) {
 668                 struct symbol *left, *right;
 669
 670                 left = get_real_base_type(expr->left->symbol);
 671                 right = get_real_base_type(expr->left->symbol);
 672                 if (left == right)
 673                         return rl_one();
 674                 return rl_zero();
 675         }
 676
 677         if (get_value(expr->left, &left) && get_value(expr->right, &right)) {
 678                 struct data_range tmp_left, tmp_right;
 679
 680                 tmp_left.min = left;
 681                 tmp_left.max = left;
 682                 tmp_right.min = right;
 683                 tmp_right.max = right;
 684                 if (true_comparison_range(&tmp_left, expr->op, &tmp_right))
 685                         return rl_one();
 686                 return rl_zero();
 687         }
 688
 689         if (implied == RL_EXACT)
 690                 return NULL;
 691
 692         res = do_comparison(expr);
 693         if (res == 1)
 694                 return rl_one();
 695         if (res == 2)
 696                 return rl_zero();
 697
 698         return alloc_rl(zero, one);
 699 }
 700
 701 static struct range_list *handle_logical_rl(struct expression *expr, int implied, int *recurse_cnt)
 702 {
 703         sval_t left, right;
 704         int left_known = 0;
 705         int right_known = 0;
 706
 707         if (implied == RL_EXACT) {
 708                 if (get_value(expr->left, &left))
 709                         left_known = 1;
 710                 if (get_value(expr->right, &right))
 711                         right_known = 1;
 712         } else {
 713                 if (get_implied_value_internal(expr->left, &left, recurse_cnt))
 714                         left_known = 1;
 715                 if (get_implied_value_internal(expr->right, &right, recurse_cnt))
 716                         right_known = 1;
 717         }
 718
 719         switch (expr->op) {
 720         case SPECIAL_LOGICAL_OR:
 721                 if (left_known && left.value)
 722                         return rl_one();
 723                 if (right_known && right.value)
 724                         return rl_one();
 725                 if (left_known && right_known)
 726                         return rl_zero();
 727                 break;
 728         case SPECIAL_LOGICAL_AND:
 729                 if (left_known && right_known) {
 730                         if (left.value && right.value)
 731                                 return rl_one();
 732                         return rl_zero();
 733                 }
 734                 break;
 735         default:
 736                 return NULL;
 737         }
 738
 739         if (implied == RL_EXACT)
 740                 return NULL;
 741
 742         return alloc_rl(zero, one);
 743 }
 744
 745 static struct range_list *handle_conditional_rl(struct expression *expr, int implied, int *recurse_cnt)
 746 {
 747         struct range_list *true_rl, *false_rl;
 748         struct symbol *type;
 749         int final_pass_orig = final_pass;
 750
 751         if (known_condition_true(expr->conditional))
 752                 return _get_rl(expr->cond_true, implied, recurse_cnt);
 753         if (known_condition_false(expr->conditional))
 754                 return _get_rl(expr->cond_false, implied, recurse_cnt);
 755
 756         if (implied == RL_EXACT)
 757                 return NULL;
 758
 759         if (implied_condition_true(expr->conditional))
 760                 return _get_rl(expr->cond_true, implied, recurse_cnt);
 761         if (implied_condition_false(expr->conditional))
 762                 return _get_rl(expr->cond_false, implied, recurse_cnt);
 763
 764
 765         /* this becomes a problem with deeply nested conditional statements */
 766         if (low_on_memory())
 767                 return NULL;
 768
 769         type = get_type(expr);
 770
 771         __push_fake_cur_stree();
 772         final_pass = 0;
 773         __split_whole_condition(expr->conditional);
 774         true_rl = _get_rl(expr->cond_true, implied, recurse_cnt);
 775         __push_true_states();
 776         __use_false_states();
 777         false_rl = _get_rl(expr->cond_false, implied, recurse_cnt);
 778         __merge_true_states();
 779         __free_fake_cur_stree();
 780         final_pass = final_pass_orig;
 781
 782         if (!true_rl || !false_rl)
 783                 return NULL;
 784         true_rl = cast_rl(type, true_rl);
 785         false_rl = cast_rl(type, false_rl);
 786
 787         return rl_union(true_rl, false_rl);
 788 }
 789
 790 static int get_fuzzy_max_helper(struct expression *expr, sval_t *max)
 791 {
 792         struct smatch_state *state;
 793         sval_t sval;
 794
 795         if (get_hard_max(expr, &sval)) {
 796                 *max = sval;
 797                 return 1;
 798         }
 799
 800         state = get_extra_state(expr);
 801         if (!state || !estate_has_fuzzy_max(state))
 802                 return 0;
 803         *max = sval_cast(get_type(expr), estate_get_fuzzy_max(state));
 804         return 1;
 805 }
 806
 807 static int get_fuzzy_min_helper(struct expression *expr, sval_t *min)
 808 {
 809         struct smatch_state *state;
 810         sval_t sval;
 811
 812         state = get_extra_state(expr);
 813         if (!state || !estate_rl(state))
 814                 return 0;
 815
 816         sval = estate_min(state);
 817         if (sval_is_negative(sval) && sval_is_min(sval))
 818                 return 0;
 819
 820         if (sval_is_max(sval))
 821                 return 0;
 822
 823         *min = sval_cast(get_type(expr), sval);
 824         return 1;
 825 }
 826
 827 int get_const_value(struct expression *expr, sval_t *sval)
 828 {
 829         struct symbol *sym;
 830         sval_t right;
 831
 832         if (expr->type != EXPR_SYMBOL || !expr->symbol)
 833                 return 0;
 834         sym = expr->symbol;
 835         if (!(sym->ctype.modifiers & MOD_CONST))
 836                 return 0;
 837         if (get_value(sym->initializer, &right)) {
 838                 *sval = sval_cast(get_type(expr), right);
 839                 return 1;
 840         }
 841         return 0;
 842 }
 843
 844 struct range_list *var_to_absolute_rl(struct expression *expr)
 845 {
 846         struct smatch_state *state;
 847         struct range_list *rl;
 848
 849         state = get_extra_state(expr);
 850         if (!state || is_whole_rl(estate_rl(state))) {
 851                 state = get_real_absolute_state(expr);
 852                 if (state && state->data && !estate_is_whole(state))
 853                         return clone_rl(estate_rl(state));
 854                 if (get_local_rl(expr, &rl) && !is_whole_rl(rl))
 855                         return rl;
 856                 if (get_db_type_rl(expr, &rl) && !is_whole_rl(rl))
 857                         return rl;
 858                 return alloc_whole_rl(get_type(expr));
 859         }
 860         /* err on the side of saying things are possible */
 861         if (!estate_rl(state))
 862                 return alloc_whole_rl(get_type(expr));
 863         return clone_rl(estate_rl(state));
 864 }
 865
 866 static struct range_list *handle_variable(struct expression *expr, int implied, int *recurse_cnt)
 867 {
 868         struct smatch_state *state;
 869         struct range_list *rl;
 870         sval_t sval, min, max;
 871         struct symbol *type;
 872
 873         if (get_const_value(expr, &sval))
 874                 return alloc_rl(sval, sval);
 875
 876         if (custom_handle_variable) {
 877                 rl = custom_handle_variable(expr);
 878                 if (!rl)
 879                         return var_to_absolute_rl(expr);
 880                 return rl;
 881         }
 882
 883         if (implied == RL_EXACT)
 884                 return NULL;
 885
 886         type = get_type(expr);
 887         if (type && type->type == SYM_FN)
 888                 return alloc_rl(fn_ptr_min, fn_ptr_max);
 889
 890         switch (implied) {
 891         case RL_HARD:
 892         case RL_IMPLIED:
 893         case RL_ABSOLUTE:
 894                 state = get_extra_state(expr);
 895                 if (!state || !state->data) {
 896                         if (implied == RL_HARD)
 897                                 return NULL;
 898                         if (get_local_rl(expr, &rl))
 899                                 return rl;
 900                         if (get_db_type_rl(expr, &rl))
 901                                 return rl;
 902                         return NULL;
 903                 }
 904                 if (implied == RL_HARD && !estate_has_hard_max(state))
 905                         return NULL;
 906                 return clone_rl(estate_rl(state));
 907         case RL_REAL_ABSOLUTE: {
 908                 struct smatch_state *abs_state;
 909
 910                 state = get_extra_state(expr);
 911                 abs_state = get_real_absolute_state(expr);
 912
 913                 if (estate_rl(state) && estate_rl(abs_state)) {
 914                         return clone_rl(rl_intersection(estate_rl(state),
 915                                                         estate_rl(abs_state)));
 916                 } else if (estate_rl(state)) {
 917                         return clone_rl(estate_rl(state));
 918                 } else if (estate_is_empty(state)) {
 919                         /*
 920                          * FIXME: we don't handle empty extra states correctly.
 921                          *
 922                          * The real abs rl is supposed to be filtered by the
 923                          * extra state if there is one.  We don't bother keeping
 924                          * the abs state in sync all the time because we know it
 925                          * will be filtered later.
 926                          *
 927                          * It's not totally obvious to me how they should be
 928                          * handled.  Perhaps we should take the whole rl and
 929                          * filter by the imaginary states.  Perhaps we should
 930                          * just go with the empty state.
 931                          *
 932                          * Anyway what we currently do is return NULL here and
 933                          * that gets translated into the whole range in
 934                          * get_real_absolute_rl().
 935                          *
 936                          */
 937                         return NULL;
 938                 } else if (estate_rl(abs_state)) {
 939                         return clone_rl(estate_rl(abs_state));
 940                 }
 941
 942                 if (get_local_rl(expr, &rl))
 943                         return rl;
 944                 if (get_db_type_rl(expr, &rl))
 945                         return rl;
 946                 return NULL;
 947         }
 948         case RL_FUZZY:
 949                 if (!get_fuzzy_min_helper(expr, &min))
 950                         min = sval_type_min(get_type(expr));
 951                 if (!get_fuzzy_max_helper(expr, &max))
 952                         return NULL;
 953                 /* fuzzy ranges are often inverted */
 954                 if (sval_cmp(min, max) > 0) {
 955                         sval = min;
 956                         min = max;
 957                         max = sval;
 958                 }
 959                 return alloc_rl(min, max);
 960         }
 961         return NULL;
 962 }
 963
 964 static sval_t handle_sizeof(struct expression *expr)
 965 {
 966         struct symbol *sym;
 967         sval_t ret;
 968
 969         ret = sval_blank(expr);
 970         sym = expr->cast_type;
 971         if (!sym) {
 972                 sym = evaluate_expression(expr->cast_expression);
 973                 if (!sym) {
 974                         __silence_warnings_for_stmt = true;
 975                         sym = &int_ctype;
 976                 }
 977 #if 0
 978                 /*
 979                  * Expressions of restricted types will possibly get
 980                  * promoted - check that here.  I'm not sure how this works,
 981                  * the problem is that sizeof(le16) shouldn't be promoted and
 982                  * the original code did that...  Let's if zero this out and
 983                  * see what breaks.
 984                  */
 985
 986                 if (is_restricted_type(sym)) {
 987                         if (type_bits(sym) < bits_in_int)
 988                                 sym = &int_ctype;
 989                 }
 990 #endif
 991                 if (is_fouled_type(sym))
 992                         sym = &int_ctype;
 993         }
 994         examine_symbol_type(sym);
 995
 996         ret.type = size_t_ctype;
 997         if (type_bits(sym) <= 0) /* sizeof(void) */ {
 998                 if (get_real_base_type(sym) == &void_ctype)
 999                         ret.value = 1;
1000                 else
1001                         ret.value = 0;
1002         } else
1003                 ret.value = type_bytes(sym);
1004
1005         return ret;
1006 }
1007
1008 static struct range_list *handle_strlen(struct expression *expr, int implied, int *recurse_cnt)
1009 {
1010         struct range_list *rl;
1011         struct expression *arg;
1012         sval_t sval = { .type = &ulong_ctype };
1013
1014         if (implied == RL_EXACT)
1015                 return NULL;
1016
1017         arg = get_argument_from_call_expr(expr->args, 0);
1018         if (!arg)
1019                 return NULL;
1020         if (arg->type == EXPR_STRING) {
1021                 sval.value = arg->string->length - 1;
1022                 return alloc_rl(sval, sval);
1023         }
1024
1025         if (implied == RL_HARD || implied == RL_FUZZY)
1026                 return NULL;
1027
1028         if (get_implied_return(expr, &rl))
1029                 return rl;
1030
1031         return NULL;
1032 }
1033
1034 static struct range_list *handle_builtin_constant_p(struct expression *expr, int implied, int *recurse_cnt)
1035 {
1036         struct expression *arg;
1037         struct range_list *rl;
1038         sval_t sval;
1039
1040         arg = get_argument_from_call_expr(expr->args, 0);
1041         rl = _get_rl(arg, RL_EXACT, recurse_cnt);
1042         if (rl_to_sval(rl, &sval))
1043                 return rl_one();
1044         return rl_zero();
1045 }
1046
1047 static struct range_list *handle__builtin_choose_expr(struct expression *expr, int implied, int *recurse_cnt)
1048 {
1049         struct expression *const_expr, *expr1, *expr2;
1050         sval_t sval;
1051
1052         const_expr = get_argument_from_call_expr(expr->args, 0);
1053         expr1 = get_argument_from_call_expr(expr->args, 1);
1054         expr2 = get_argument_from_call_expr(expr->args, 2);
1055
1056         if (!get_value(const_expr, &sval) || !expr1 || !expr2)
1057                 return NULL;
1058         if (sval.value)
1059                 return _get_rl(expr1, implied, recurse_cnt);
1060         return _get_rl(expr2, implied, recurse_cnt);
1061 }
1062
1063 static struct range_list *handle_call_rl(struct expression *expr, int implied, int *recurse_cnt)
1064 {
1065         struct range_list *rl;
1066
1067         if (sym_name_is("__builtin_constant_p", expr->fn))
1068                 return handle_builtin_constant_p(expr, implied, recurse_cnt);
1069
1070         if (sym_name_is("__builtin_choose_expr", expr->fn))
1071                 return handle__builtin_choose_expr(expr, implied, recurse_cnt);
1072
1073         if (sym_name_is("__builtin_expect", expr->fn) ||
1074             sym_name_is("__builtin_bswap16", expr->fn) ||
1075             sym_name_is("__builtin_bswap32", expr->fn) ||
1076             sym_name_is("__builtin_bswap64", expr->fn)) {
1077                 struct expression *arg;
1078
1079                 arg = get_argument_from_call_expr(expr->args, 0);
1080                 return _get_rl(arg, implied, recurse_cnt);
1081         }
1082
1083         if (sym_name_is("strlen", expr->fn))
1084                 return handle_strlen(expr, implied, recurse_cnt);
1085
1086         if (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY)
1087                 return NULL;
1088
1089         if (custom_handle_variable) {
1090                 rl = custom_handle_variable(expr);
1091                 if (rl)
1092                         return rl;
1093         }
1094
1095         if (get_implied_return(expr, &rl))
1096                 return rl;
1097         return db_return_vals(expr);
1098 }
1099
1100 static struct range_list *handle_cast(struct expression *expr, int implied, int *recurse_cnt)
1101 {
1102         struct range_list *rl;
1103         struct symbol *type;
1104
1105         type = get_type(expr);
1106         rl = _get_rl(expr->cast_expression, implied, recurse_cnt);
1107         if (rl)
1108                 return cast_rl(type, rl);
1109         if (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE)
1110                 return alloc_whole_rl(type);
1111         if (implied == RL_IMPLIED && type &&
1112             type_bits(type) > 0 && type_bits(type) < 32)
1113                 return alloc_whole_rl(type);
1114         return NULL;
1115 }
1116
1117 static struct range_list *_get_rl(struct expression *expr, int implied, int *recurse_cnt)
1118 {
1119         struct range_list *rl;
1120         struct symbol *type;
1121         sval_t sval;
1122
1123         type = get_type(expr);
1124         expr = strip_parens(expr);
1125         if (!expr)
1126                 return NULL;
1127
1128         if (++(*recurse_cnt) >= 200)
1129                 return NULL;
1130
1131         switch(expr->type) {
1132         case EXPR_CAST:
1133         case EXPR_FORCE_CAST:
1134         case EXPR_IMPLIED_CAST:
1135                 rl = handle_cast(expr, implied, recurse_cnt);
1136                 goto out_cast;
1137         }
1138
1139         expr = strip_expr(expr);
1140         if (!expr)
1141                 return NULL;
1142
1143         switch (expr->type) {
1144         case EXPR_VALUE:
1145                 sval = sval_from_val(expr, expr->value);
1146                 rl = alloc_rl(sval, sval);
1147                 break;
1148         case EXPR_PREOP:
1149                 rl = handle_preop_rl(expr, implied, recurse_cnt);
1150                 break;
1151         case EXPR_POSTOP:
1152                 rl = _get_rl(expr->unop, implied, recurse_cnt);
1153                 break;
1154         case EXPR_BINOP:
1155                 rl = handle_binop_rl(expr, implied, recurse_cnt);
1156                 break;
1157         case EXPR_COMPARE:
1158                 rl = handle_comparison_rl(expr, implied, recurse_cnt);
1159                 break;
1160         case EXPR_LOGICAL:
1161                 rl = handle_logical_rl(expr, implied, recurse_cnt);
1162                 break;
1163         case EXPR_PTRSIZEOF:
1164         case EXPR_SIZEOF:
1165                 sval = handle_sizeof(expr);
1166                 rl = alloc_rl(sval, sval);
1167                 break;
1168         case EXPR_SELECT:
1169         case EXPR_CONDITIONAL:
1170                 rl = handle_conditional_rl(expr, implied, recurse_cnt);
1171                 break;
1172         case EXPR_CALL:
1173                 rl = handle_call_rl(expr, implied, recurse_cnt);
1174                 break;
1175         default:
1176                 rl = handle_variable(expr, implied, recurse_cnt);
1177         }
1178
1179 out_cast:
1180         if (rl)
1181                 return rl;
1182         if (type && (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE))
1183                 return alloc_whole_rl(type);
1184         return NULL;
1185 }
1186
1187 struct {
1188         struct expression *expr;
1189         struct range_list *rl;
1190 } cached_results[24];
1191 static int cache_idx;
1192
1193 void clear_math_cache(void)
1194 {
1195         memset(cached_results, 0, sizeof(cached_results));
1196 }
1197
1198 /* returns 1 if it can get a value literal or else returns 0 */
1199 int get_value(struct expression *expr, sval_t *sval)
1200 {
1201         struct range_list *rl;
1202         int recurse_cnt = 0;
1203         sval_t tmp;
1204         int i;
1205
1206         /*
1207          * This only handles RL_EXACT because other expr statements can be
1208          * different at different points.  Like the list iterator, for example.
1209          */
1210         for (i = 0; i < ARRAY_SIZE(cached_results); i++) {
1211                 if (expr == cached_results[i].expr)
1212                         return rl_to_sval(cached_results[i].rl, sval);
1213         }
1214
1215         rl = _get_rl(expr, RL_EXACT, &recurse_cnt);
1216         if (!rl_to_sval(rl, &tmp))
1217                 rl = NULL;
1218
1219         cached_results[cache_idx].expr = expr;
1220         cached_results[cache_idx].rl = rl;
1221         cache_idx = (cache_idx + 1) % ARRAY_SIZE(cached_results);
1222
1223         if (!rl)
1224                 return 0;
1225
1226         *sval = tmp;
1227         return 1;
1228 }
1229
1230 static int get_implied_value_internal(struct expression *expr, sval_t *sval, int *recurse_cnt)
1231 {
1232         struct range_list *rl;
1233
1234         rl =  _get_rl(expr, RL_IMPLIED, recurse_cnt);
1235         if (!rl_to_sval(rl, sval))
1236                 return 0;
1237         return 1;
1238 }
1239
1240 int get_implied_value(struct expression *expr, sval_t *sval)
1241 {
1242         struct range_list *rl;
1243         int recurse_cnt = 0;
1244
1245         rl =  _get_rl(expr, RL_IMPLIED, &recurse_cnt);
1246         if (!rl_to_sval(rl, sval))
1247                 return 0;
1248         return 1;
1249 }
1250
1251 int get_implied_min(struct expression *expr, sval_t *sval)
1252 {
1253         struct range_list *rl;
1254         int recurse_cnt = 0;
1255
1256         rl =  _get_rl(expr, RL_IMPLIED, &recurse_cnt);
1257         if (!rl)
1258                 return 0;
1259         *sval = rl_min(rl);
1260         return 1;
1261 }
1262
1263 int get_implied_max(struct expression *expr, sval_t *sval)
1264 {
1265         struct range_list *rl;
1266         int recurse_cnt = 0;
1267
1268         rl =  _get_rl(expr, RL_IMPLIED, &recurse_cnt);
1269         if (!rl)
1270                 return 0;
1271         *sval = rl_max(rl);
1272         return 1;
1273 }
1274
1275 int get_implied_rl(struct expression *expr, struct range_list **rl)
1276 {
1277         int recurse_cnt = 0;
1278
1279         *rl = _get_rl(expr, RL_IMPLIED, &recurse_cnt);
1280         if (*rl)
1281                 return 1;
1282         return 0;
1283 }
1284
1285 static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt)
1286 {
1287         *rl = _get_rl(expr, RL_ABSOLUTE, recurse_cnt);
1288         if (!*rl)
1289                 *rl = alloc_whole_rl(get_type(expr));
1290         return 1;
1291 }
1292
1293 int get_absolute_rl(struct expression *expr, struct range_list **rl)
1294 {
1295         int recurse_cnt = 0;
1296
1297         *rl = _get_rl(expr, RL_ABSOLUTE, &recurse_cnt);
1298         if (!*rl)
1299                 *rl = alloc_whole_rl(get_type(expr));
1300         return 1;
1301 }
1302
1303 int get_real_absolute_rl(struct expression *expr, struct range_list **rl)
1304 {
1305         int recurse_cnt = 0;
1306
1307         *rl = _get_rl(expr, RL_REAL_ABSOLUTE, &recurse_cnt);
1308         if (!*rl)
1309                 *rl = alloc_whole_rl(get_type(expr));
1310         return 1;
1311 }
1312
1313 int custom_get_absolute_rl(struct expression *expr,
1314                            struct range_list *(*fn)(struct expression *expr),
1315                            struct range_list **rl)
1316 {
1317         int recurse_cnt = 0;
1318
1319         *rl = NULL;
1320         custom_handle_variable = fn;
1321         *rl = _get_rl(expr, RL_REAL_ABSOLUTE, &recurse_cnt);
1322         custom_handle_variable = NULL;
1323         return 1;
1324 }
1325
1326 int get_implied_rl_var_sym(const char *var, struct symbol *sym, struct range_list **rl)
1327 {
1328         struct smatch_state *state;
1329
1330         state = get_state(SMATCH_EXTRA, var, sym);
1331         *rl = estate_rl(state);
1332         if (*rl)
1333                 return 1;
1334         return 0;
1335 }
1336
1337 int get_hard_max(struct expression *expr, sval_t *sval)
1338 {
1339         struct range_list *rl;
1340         int recurse_cnt = 0;
1341
1342         rl =  _get_rl(expr, RL_HARD, &recurse_cnt);
1343         if (!rl)
1344                 return 0;
1345         *sval = rl_max(rl);
1346         return 1;
1347 }
1348
1349 int get_fuzzy_min(struct expression *expr, sval_t *sval)
1350 {
1351         struct range_list *rl;
1352         sval_t tmp;
1353         int recurse_cnt = 0;
1354
1355         rl =  _get_rl(expr, RL_FUZZY, &recurse_cnt);
1356         if (!rl)
1357                 return 0;
1358         tmp = rl_min(rl);
1359         if (sval_is_negative(tmp) && sval_is_min(tmp))
1360                 return 0;
1361         *sval = tmp;
1362         return 1;
1363 }
1364
1365 int get_fuzzy_max(struct expression *expr, sval_t *sval)
1366 {
1367         struct range_list *rl;
1368         sval_t max;
1369         int recurse_cnt = 0;
1370
1371         rl =  _get_rl(expr, RL_FUZZY, &recurse_cnt);
1372         if (!rl)
1373                 return 0;
1374         max = rl_max(rl);
1375         if (max.uvalue > INT_MAX - 10000)
1376                 return 0;
1377         *sval = max;
1378         return 1;
1379 }
1380
1381 int get_absolute_min(struct expression *expr, sval_t *sval)
1382 {
1383         struct range_list *rl;
1384         struct symbol *type;
1385         int recurse_cnt = 0;
1386
1387         type = get_type(expr);
1388         if (!type)
1389                 type = &llong_ctype;  // FIXME: this is wrong but places assume get type can't fail.
1390         rl = _get_rl(expr, RL_REAL_ABSOLUTE, &recurse_cnt);
1391         if (rl)
1392                 *sval = rl_min(rl);
1393         else
1394                 *sval = sval_type_min(type);
1395
1396         if (sval_cmp(*sval, sval_type_min(type)) < 0)
1397                 *sval = sval_type_min(type);
1398         return 1;
1399 }
1400
1401 int get_absolute_max(struct expression *expr, sval_t *sval)
1402 {
1403         struct range_list *rl;
1404         struct symbol *type;
1405         int recurse_cnt = 0;
1406
1407         type = get_type(expr);
1408         if (!type)
1409                 type = &llong_ctype;
1410         rl = _get_rl(expr, RL_REAL_ABSOLUTE, &recurse_cnt);
1411         if (rl)
1412                 *sval = rl_max(rl);
1413         else
1414                 *sval = sval_type_max(type);
1415
1416         if (sval_cmp(sval_type_max(type), *sval) < 0)
1417                 *sval = sval_type_max(type);
1418         return 1;
1419 }
1420
1421 int known_condition_true(struct expression *expr)
1422 {
1423         sval_t tmp;
1424
1425         if (!expr)
1426                 return 0;
1427
1428         if (get_value(expr, &tmp) && tmp.value)
1429                 return 1;
1430
1431         return 0;
1432 }
1433
1434 int known_condition_false(struct expression *expr)
1435 {
1436         if (!expr)
1437                 return 0;
1438
1439         if (is_zero(expr))
1440                 return 1;
1441
1442         return 0;
1443 }
1444
1445 int implied_condition_true(struct expression *expr)
1446 {
1447         sval_t tmp;
1448
1449         if (!expr)
1450                 return 0;
1451
1452         if (known_condition_true(expr))
1453                 return 1;
1454         if (get_implied_value(expr, &tmp) && tmp.value)
1455                 return 1;
1456
1457         if (expr->type == EXPR_POSTOP)
1458                 return implied_condition_true(expr->unop);
1459
1460         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
1461                 return implied_not_equal(expr->unop, 1);
1462         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
1463                 return implied_not_equal(expr->unop, -1);
1464
1465         expr = strip_expr(expr);
1466         switch (expr->type) {
1467         case EXPR_COMPARE:
1468                 if (do_comparison(expr) == 1)
1469                         return 1;
1470                 break;
1471         case EXPR_PREOP:
1472                 if (expr->op == '!') {
1473                         if (implied_condition_false(expr->unop))
1474                                 return 1;
1475                         break;
1476                 }
1477                 break;
1478         default:
1479                 if (implied_not_equal(expr, 0) == 1)
1480                         return 1;
1481                 break;
1482         }
1483         return 0;
1484 }
1485
1486 int implied_condition_false(struct expression *expr)
1487 {
1488         struct expression *tmp;
1489         sval_t sval;
1490
1491         if (!expr)
1492                 return 0;
1493
1494         if (known_condition_false(expr))
1495                 return 1;
1496
1497         switch (expr->type) {
1498         case EXPR_COMPARE:
1499                 if (do_comparison(expr) == 2)
1500                         return 1;
1501         case EXPR_PREOP:
1502                 if (expr->op == '!') {
1503                         if (implied_condition_true(expr->unop))
1504                                 return 1;
1505                         break;
1506                 }
1507                 tmp = strip_expr(expr);
1508                 if (tmp != expr)
1509                         return implied_condition_false(tmp);
1510                 break;
1511         default:
1512                 if (get_implied_value(expr, &sval) && sval.value == 0)
1513                         return 1;
1514                 break;
1515         }
1516         return 0;
1517 }
1518
1519 int can_integer_overflow(struct symbol *type, struct expression *expr)
1520 {
1521         int op;
1522         sval_t lmax, rmax, res;
1523
1524         if (!type)
1525                 type = &int_ctype;
1526
1527         expr = strip_expr(expr);
1528
1529         if (expr->type == EXPR_ASSIGNMENT) {
1530                 switch(expr->op) {
1531                 case SPECIAL_MUL_ASSIGN:
1532                         op = '*';
1533                         break;
1534                 case SPECIAL_ADD_ASSIGN:
1535                         op = '+';
1536                         break;
1537                 case SPECIAL_SHL_ASSIGN:
1538                         op = SPECIAL_LEFTSHIFT;
1539                         break;
1540                 default:
1541                         return 0;
1542                 }
1543         } else if (expr->type == EXPR_BINOP) {
1544                 if (expr->op != '*' && expr->op != '+' && expr->op != SPECIAL_LEFTSHIFT)
1545                         return 0;
1546                 op = expr->op;
1547         } else {
1548                 return 0;
1549         }
1550
1551         get_absolute_max(expr->left, &lmax);
1552         get_absolute_max(expr->right, &rmax);
1553
1554         if (sval_binop_overflows(lmax, op, rmax))
1555                 return 1;
1556
1557         res = sval_binop(lmax, op, rmax);
1558         if (sval_cmp(res, sval_type_max(type)) > 0)
1559                 return 1;
1560         return 0;
1561 }