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