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