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