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