smatch_math.c

   1 /*
   2  * smatch/smatch_math.c
   3  *
   4  * Copyright (C) 2010 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 #include "smatch.h"
  11 #include "smatch_slist.h"
  12 #include "smatch_extra.h"
  13
  14 static long long _get_implied_value(struct expression *expr, int *undefined, int implied);
  15 static long long _get_value(struct expression *expr, int *undefined, int implied);
  16
  17 #define BOGUS 12345
  18
  19 #define NOTIMPLIED  0
  20 #define IMPLIED     1
  21 #define IMPLIED_MIN 2
  22 #define IMPLIED_MAX 3
  23 #define FUZZYMAX    4
  24 #define FUZZYMIN    5
  25 #define ABSOLUTE_MIN 6
  26 #define ABSOLUTE_MAX 7
  27
  28 static long long cast_to_type(struct expression *expr, long long val)
  29 {
  30         struct symbol *type = get_type(expr);
  31
  32         if (!type)
  33                 return val;
  34
  35         switch (type->bit_size) {
  36         case 8:
  37                 if (type->ctype.modifiers & MOD_UNSIGNED)
  38                         val = (long long)(unsigned char) val;
  39                 else
  40                         val = (long long)(char) val;
  41                 break;
  42         case 16:
  43                 if (type->ctype.modifiers & MOD_UNSIGNED)
  44                         val = (long long)(unsigned short) val;
  45                 else
  46                         val = (long long)(short) val;
  47                 break;
  48         case 32:
  49                 if (type->ctype.modifiers & MOD_UNSIGNED)
  50                         val = (long long)(unsigned int) val;
  51                 else
  52                         val = (long long)(int) val;
  53                 break;
  54         }
  55         return val;
  56 }
  57
  58 static int opposite_implied(int implied)
  59 {
  60         if (implied == IMPLIED_MIN)
  61                 return IMPLIED_MAX;
  62         if (implied == IMPLIED_MAX)
  63                 return IMPLIED_MIN;
  64         if (implied == ABSOLUTE_MIN)
  65                 return ABSOLUTE_MAX;
  66         if (implied == ABSOLUTE_MAX)
  67                 return ABSOLUTE_MIN;
  68         return implied;
  69 }
  70
  71 static int last_stmt_val(struct statement *stmt, long long *val)
  72 {
  73         struct expression *expr;
  74
  75         if (!stmt)
  76                 return 0;
  77
  78         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
  79         if (stmt->type != STMT_EXPRESSION)
  80                 return 0;
  81         expr = stmt->expression;
  82         return get_value(expr, val);
  83 }
  84
  85 static long long handle_expression_statement(struct expression *expr, int *undefined, int implied)
  86 {
  87         struct statement *stmt;
  88         long long tmp;
  89
  90         stmt = get_expression_statement(expr);
  91         if (last_stmt_val(stmt, &tmp))
  92                 return tmp;
  93
  94         *undefined = 1;
  95         return BOGUS;
  96 }
  97
  98 static long long handle_ampersand(int *undefined, int implied)
  99 {
 100         if (implied == IMPLIED_MIN || implied == FUZZYMIN || implied == ABSOLUTE_MIN)
 101                 return valid_ptr_min;
 102         if (implied == IMPLIED_MAX || implied == FUZZYMAX || implied == ABSOLUTE_MAX)
 103                 return valid_ptr_max;
 104
 105         *undefined = 1;
 106         return BOGUS;
 107 }
 108
 109 static long long handle_preop(struct expression *expr, int *undefined, int implied)
 110 {
 111         long long ret = BOGUS;
 112
 113         switch (expr->op) {
 114         case '&':
 115                 ret = handle_ampersand(undefined, implied);
 116                 break;
 117         case '!':
 118                 ret = !_get_value(expr->unop, undefined, implied);
 119                 break;
 120         case '~':
 121                 ret = ~_get_value(expr->unop, undefined, implied);
 122                 ret = cast_to_type(expr->unop, ret);
 123                 break;
 124         case '-':
 125                 ret = -_get_value(expr->unop, undefined, implied);
 126                 break;
 127         case '*':
 128                 ret = _get_implied_value(expr, undefined, implied);
 129                 break;
 130         case '(':
 131                 ret = handle_expression_statement(expr, undefined, implied);
 132                 break;
 133         default:
 134                 *undefined = 1;
 135         }
 136         return ret;
 137 }
 138
 139 static long long handle_divide(struct expression *expr, int *undefined, int implied)
 140 {
 141         long long left;
 142         long long right;
 143         long long ret = BOGUS;
 144
 145         left = _get_value(expr->left, undefined, implied);
 146         right = _get_value(expr->right, undefined, opposite_implied(implied));
 147
 148         if (right == 0)
 149                 *undefined = 1;
 150         else
 151                 ret = left / right;
 152
 153         return ret;
 154 }
 155
 156 static long long handle_subtract(struct expression *expr, int *undefined, int implied)
 157 {
 158         long long left;
 159         long long right;
 160
 161         left = _get_value(expr->left, undefined, implied);
 162         right = _get_value(expr->right, undefined, opposite_implied(implied));
 163
 164         return left - right;
 165 }
 166
 167 static long long handle_binop(struct expression *expr, int *undefined, int implied)
 168 {
 169         long long left;
 170         long long right;
 171         long long ret = BOGUS;
 172         int local_undef = 0;
 173
 174         if (option_debug)
 175                 sm_msg("handle_binop %s", show_special(expr->op));
 176
 177         switch (expr->op) {
 178         case '%':
 179                 left = _get_value(expr->left, &local_undef, implied);
 180                 if (local_undef) {
 181                         if (implied == ABSOLUTE_MIN)
 182                                 return 0;
 183                         if (implied != ABSOLUTE_MAX)
 184                                 *undefined = 1;
 185                         if (!get_absolute_max(expr->left, &left))
 186                                 *undefined = 1;
 187                 }
 188                 right = _get_value(expr->right, undefined, implied);
 189                 if (right == 0)
 190                         *undefined = 1;
 191                 else
 192                         ret = left % right;
 193                 return ret;
 194
 195         case '&':
 196                 left = _get_value(expr->left, &local_undef, implied);
 197                 if (local_undef) {
 198                         if (implied == ABSOLUTE_MIN)
 199                                 return 0;
 200                         if (implied != ABSOLUTE_MAX)
 201                                 *undefined = 1;
 202                         if (!get_absolute_max(expr->left, &left))
 203                                 *undefined = 1;
 204                 }
 205                 right = _get_value(expr->right, undefined, implied);
 206                 return left & right;
 207         case SPECIAL_RIGHTSHIFT:
 208                 left = _get_value(expr->left, &local_undef, implied);
 209                 if (local_undef) {
 210                         if (implied == ABSOLUTE_MIN)
 211                                 return 0;
 212                         if (implied != ABSOLUTE_MAX)
 213                                 *undefined = 1;
 214                         if (!get_absolute_max(expr->left, &left))
 215                                 *undefined = 1;
 216                 }
 217                 right = _get_value(expr->right, undefined, implied);
 218                 return left >> right;
 219         }
 220
 221         left = _get_value(expr->left, undefined, implied);
 222         right = _get_value(expr->right, undefined, implied);
 223
 224         switch (expr->op) {
 225         case '*':
 226                 ret =  left * right;
 227                 break;
 228         case '/':
 229                 ret = handle_divide(expr, undefined, implied);
 230                 break;
 231         case '+':
 232                 ret = left + right;
 233                 break;
 234         case '-':
 235                 ret = handle_subtract(expr, undefined, implied);
 236                 break;
 237         case '%':
 238                 if (right == 0)
 239                         *undefined = 1;
 240                 else
 241                         ret = left % right;
 242                 break;
 243         case '|':
 244                 ret = left | right;
 245                 break;
 246         case '&':
 247                 ret = left & right;
 248                 break;
 249         case SPECIAL_RIGHTSHIFT:
 250                 ret = left >> right;
 251                 break;
 252         case SPECIAL_LEFTSHIFT:
 253                 ret = left << right;
 254                 break;
 255         case '^':
 256                 ret = left ^ right;
 257                 break;
 258         default:
 259                 *undefined = 1;
 260         }
 261         return ret;
 262 }
 263
 264 static int do_comparison(struct expression *expr)
 265 {
 266         struct range_list *left_ranges = NULL;
 267         struct range_list *right_ranges = NULL;
 268         int poss_true, poss_false;
 269
 270         get_implied_range_list(expr->left, &left_ranges);
 271         get_implied_range_list(expr->right, &right_ranges);
 272
 273         poss_true = possibly_true_range_lists(left_ranges, expr->op, right_ranges);
 274         poss_false = possibly_false_range_lists(left_ranges, expr->op, right_ranges);
 275
 276         free_range_list(&left_ranges);
 277         free_range_list(&right_ranges);
 278
 279         if (!poss_true && !poss_false)
 280                 return 0;
 281         if (poss_true && !poss_false)
 282                 return 1;
 283         if (!poss_true && poss_false)
 284                 return 2;
 285         return 3;
 286 }
 287
 288 static long long handle_comparison(struct expression *expr, int *undefined, int implied)
 289 {
 290         long long left, right;
 291         int res;
 292
 293         if (get_value(expr->left, &left) && get_value(expr->right, &right)) {
 294                 struct data_range tmp_left, tmp_right;
 295
 296                 tmp_left.min = left;
 297                 tmp_left.max = left;
 298                 tmp_right.min = right;
 299                 tmp_right.max = right;
 300                 return true_comparison_range(&tmp_left, expr->op, &tmp_right);
 301         }
 302
 303         if (implied == NOTIMPLIED) {
 304                 *undefined = 1;
 305                 return BOGUS;
 306         }
 307
 308         res = do_comparison(expr);
 309         if (res == 1)
 310                 return 1;
 311         if (res == 2)
 312                 return 0;
 313
 314         if (implied == IMPLIED_MIN || implied == FUZZYMIN || implied == ABSOLUTE_MIN)
 315                 return 0;
 316         if (implied == IMPLIED_MAX || implied == FUZZYMAX || implied == ABSOLUTE_MAX)
 317                 return 1;
 318
 319         *undefined = 1;
 320         return BOGUS;
 321 }
 322
 323 static long long handle_logical(struct expression *expr, int *undefined, int implied)
 324 {
 325         long long left_val, right_val;
 326
 327         if ((implied == NOTIMPLIED && get_value(expr->left, &left_val) &&
 328                                       get_value(expr->right, &right_val)) ||
 329             (implied != NOTIMPLIED && get_implied_value(expr->left, &left_val) &&
 330                                       get_implied_value(expr->right, &right_val))) {
 331                 switch (expr->op) {
 332                 case SPECIAL_LOGICAL_OR:
 333                         return left_val || right_val;
 334                 case SPECIAL_LOGICAL_AND:
 335                         return left_val && right_val;
 336                 default:
 337                         *undefined = 1;
 338                         return BOGUS;
 339                 }
 340         }
 341
 342         if (implied == IMPLIED_MIN || implied == FUZZYMIN || implied == ABSOLUTE_MIN)
 343                 return 0;
 344         if (implied == IMPLIED_MAX || implied == FUZZYMAX || implied == ABSOLUTE_MAX)
 345                 return 1;
 346
 347         *undefined = 1;
 348         return BOGUS;
 349 }
 350
 351 static long long handle_conditional(struct expression *expr, int *undefined, int implied)
 352 {
 353         if (known_condition_true(expr->conditional))
 354                 return _get_value(expr->cond_true, undefined, implied);
 355         if (known_condition_false(expr->conditional))
 356                 return _get_value(expr->cond_false, undefined, implied);
 357
 358         if (implied == NOTIMPLIED) {
 359                 *undefined = 1;
 360                 return BOGUS;
 361         }
 362
 363         if (implied_condition_true(expr->conditional))
 364                 return _get_value(expr->cond_true, undefined, implied);
 365         if (implied_condition_false(expr->conditional))
 366                 return _get_value(expr->cond_false, undefined, implied);
 367
 368         *undefined = 1;
 369         return BOGUS;
 370 }
 371
 372 static int get_implied_value_helper(struct expression *expr, long long *val, int what)
 373 {
 374         struct smatch_state *state;
 375         struct symbol *sym;
 376         char *name;
 377
 378         expr = strip_expr(expr);
 379
 380         if (get_value(expr, val))
 381                 return 1;
 382
 383         name = get_variable_from_expr(expr, &sym);
 384         if (!name)
 385                 return 0;
 386         state = get_state(SMATCH_EXTRA, name, sym);
 387         free_string(name);
 388         if (!state || !state->data)
 389                 return 0;
 390         if (what == IMPLIED)
 391                 return estate_get_single_value(state, val);
 392         if (what == IMPLIED_MAX || what == ABSOLUTE_MAX) {
 393                 *val = estate_max(state);
 394                 if (*val == whole_range.max) /* this means just guessing */
 395                         return 0;
 396                 return 1;
 397         }
 398         *val = estate_min(state);
 399         if (*val == whole_range.min)
 400                 return 0;
 401         return 1;
 402 }
 403
 404 static int get_fuzzy_max_helper(struct expression *expr, long long *max)
 405 {
 406         struct sm_state *sm;
 407         struct sm_state *tmp;
 408
 409         if (get_implied_max(expr, max))
 410                 return 1;
 411
 412         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 413         if (!sm)
 414                 return 0;
 415
 416         *max = whole_range.min;
 417         FOR_EACH_PTR(sm->possible, tmp) {
 418                 long long new_min;
 419
 420                 new_min = estate_min(tmp->state);
 421                 if (new_min > *max)
 422                         *max = new_min;
 423         } END_FOR_EACH_PTR(tmp);
 424
 425         if (*max > whole_range.min)
 426                 return 1;
 427         return 0;
 428 }
 429
 430 static int get_fuzzy_min_helper(struct expression *expr, long long *min)
 431 {
 432         struct sm_state *sm;
 433         struct sm_state *tmp;
 434
 435         if (get_implied_min(expr, min))
 436                 return 1;
 437
 438         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 439         if (!sm)
 440                 return 0;
 441
 442         *min = whole_range.max;
 443         FOR_EACH_PTR(sm->possible, tmp) {
 444                 long long new_max;
 445
 446                 new_max = estate_max(tmp->state);
 447                 if (new_max < *min)
 448                         *min = new_max;
 449         } END_FOR_EACH_PTR(tmp);
 450
 451         if (*min < whole_range.max)
 452                 return 1;
 453         return 0;
 454 }
 455
 456 static long long _get_implied_value(struct expression *expr, int *undefined, int implied)
 457 {
 458         long long ret = BOGUS;
 459
 460         switch (implied) {
 461         case IMPLIED:
 462         case IMPLIED_MAX:
 463         case IMPLIED_MIN:
 464                 if (!get_implied_value_helper(expr, &ret, implied))
 465                         *undefined = 1;
 466                 break;
 467         case ABSOLUTE_MIN:
 468         case ABSOLUTE_MAX: {
 469                 struct smatch_state *state;
 470                 struct data_range *range;
 471
 472                 if (get_implied_value_helper(expr, &ret, implied))
 473                         break;
 474
 475                 state = get_state_expr(absolute_id, expr);
 476                 if (!state || !state->data) {
 477                         *undefined = 1;
 478                         break;
 479                 }
 480                 range = state->data;
 481                 if (implied == ABSOLUTE_MAX)
 482                         ret = range->max;
 483                 else
 484                         ret = range->min;
 485                 break;
 486         }
 487         case FUZZYMAX:
 488                 if (!get_fuzzy_max_helper(expr, &ret))
 489                         *undefined = 1;
 490                 break;
 491         case FUZZYMIN:
 492                 if (!get_fuzzy_min_helper(expr, &ret))
 493                         *undefined = 1;
 494                 break;
 495         default:
 496                 *undefined = 1;
 497         }
 498         return ret;
 499 }
 500
 501 static int get_const_value(struct expression *expr, long long *val)
 502 {
 503         struct symbol *sym;
 504
 505         sym = expr->symbol;
 506         if (!sym)
 507                 return 0;
 508         if (!(sym->ctype.modifiers & MOD_CONST))
 509                 return 0;
 510         if (get_value(sym->initializer, val))
 511                 return 1;
 512         return 0;
 513 }
 514
 515 static long long _get_value(struct expression *expr, int *undefined, int implied)
 516 {
 517         long long ret = BOGUS;
 518
 519         if (!expr) {
 520                 *undefined = 1;
 521                 return BOGUS;
 522         }
 523         if (*undefined)
 524                 return BOGUS;
 525
 526         expr = strip_parens(expr);
 527
 528         switch (expr->type) {
 529         case EXPR_VALUE:
 530                 ret = expr->value;
 531                 ret = cast_to_type(expr, ret);
 532                 break;
 533         case EXPR_PREOP:
 534                 ret = handle_preop(expr, undefined, implied);
 535                 break;
 536         case EXPR_POSTOP:
 537                 ret = _get_value(expr->unop, undefined, implied);
 538                 break;
 539         case EXPR_CAST:
 540         case EXPR_FORCE_CAST:
 541         case EXPR_IMPLIED_CAST:
 542                 ret = _get_value(expr->cast_expression, undefined, implied);
 543                 return cast_to_type(expr, ret);
 544         case EXPR_BINOP:
 545                 ret = handle_binop(expr, undefined, implied);
 546                 break;
 547         case EXPR_COMPARE:
 548                 ret = handle_comparison(expr, undefined, implied);
 549                 break;
 550         case EXPR_LOGICAL:
 551                 ret = handle_logical(expr, undefined, implied);
 552                 break;
 553         case EXPR_PTRSIZEOF:
 554         case EXPR_SIZEOF:
 555                 ret = get_expression_value_nomod(expr);
 556                 break;
 557         case EXPR_SYMBOL:
 558                 if (get_const_value(expr, &ret))
 559                         break;
 560                 ret = _get_implied_value(expr, undefined, implied);
 561                 break;
 562         case EXPR_SELECT:
 563         case EXPR_CONDITIONAL:
 564                 ret = handle_conditional(expr, undefined, implied);
 565                 break;
 566         default:
 567                 ret = _get_implied_value(expr, undefined, implied);
 568         }
 569         if (*undefined)
 570                 return BOGUS;
 571         return ret;
 572 }
 573
 574 /* returns 1 if it can get a value literal or else returns 0 */
 575 int get_value(struct expression *expr, long long *val)
 576 {
 577         int undefined = 0;
 578
 579         *val = _get_value(expr, &undefined, NOTIMPLIED);
 580         if (undefined)
 581                 return 0;
 582         return 1;
 583 }
 584
 585 int get_implied_value(struct expression *expr, long long *val)
 586 {
 587         int undefined = 0;
 588
 589         *val =  _get_value(expr, &undefined, IMPLIED);
 590         return !undefined;
 591 }
 592
 593 int get_implied_min(struct expression *expr, long long *val)
 594 {
 595         int undefined = 0;
 596
 597         *val =  _get_value(expr, &undefined, IMPLIED_MIN);
 598         return !undefined;
 599 }
 600
 601 int get_implied_max(struct expression *expr, long long *val)
 602 {
 603         int undefined = 0;
 604
 605         *val =  _get_value(expr, &undefined, IMPLIED_MAX);
 606         return !undefined;
 607 }
 608
 609 int get_fuzzy_min(struct expression *expr, long long *val)
 610 {
 611         int undefined = 0;
 612
 613         *val =  _get_value(expr, &undefined, FUZZYMIN);
 614         return !undefined;
 615 }
 616
 617 int get_fuzzy_max(struct expression *expr, long long *val)
 618 {
 619         int undefined = 0;
 620
 621         *val =  _get_value(expr, &undefined, FUZZYMAX);
 622         return !undefined;
 623 }
 624
 625 int get_absolute_min(struct expression *expr, long long *val)
 626 {
 627         int undefined = 0;
 628         struct symbol *type;
 629
 630         type = get_type(expr);
 631         *val =  _get_value(expr, &undefined, ABSOLUTE_MIN);
 632         if (undefined) {
 633                 *val = type_min(type);
 634                 return 1;
 635         }
 636
 637         if (type_min(type) > *val)
 638                 *val = type_min(type);
 639         return 1;
 640 }
 641
 642 int get_absolute_max(struct expression *expr, long long *val)
 643 {
 644         int undefined = 0;
 645         struct symbol *type;
 646
 647         type = get_type(expr);
 648         *val =  _get_value(expr, &undefined, ABSOLUTE_MAX);
 649         if (undefined) {
 650                 *val = type_max(type);
 651                 return 1;
 652         }
 653
 654         if (type_max(type) < *val)
 655                 *val = type_max(type);
 656         return 1;
 657 }
 658
 659 int known_condition_true(struct expression *expr)
 660 {
 661         long long tmp;
 662
 663         if (!expr)
 664                 return 0;
 665
 666         if (get_value(expr, &tmp) && tmp)
 667                 return 1;
 668
 669         return 0;
 670 }
 671
 672 int known_condition_false(struct expression *expr)
 673 {
 674         if (!expr)
 675                 return 0;
 676
 677         if (is_zero(expr))
 678                 return 1;
 679
 680         if (expr->type == EXPR_CALL) {
 681                 if (sym_name_is("__builtin_constant_p", expr->fn))
 682                         return 1;
 683         }
 684         return 0;
 685 }
 686
 687 int implied_condition_true(struct expression *expr)
 688 {
 689         long long tmp;
 690
 691         if (!expr)
 692                 return 0;
 693
 694         if (known_condition_true(expr))
 695                 return 1;
 696         if (get_implied_value(expr, &tmp) && tmp)
 697                 return 1;
 698
 699         if (expr->type == EXPR_POSTOP)
 700                 return implied_condition_true(expr->unop);
 701
 702         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
 703                 return implied_not_equal(expr->unop, 1);
 704         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
 705                 return implied_not_equal(expr->unop, -1);
 706
 707         expr = strip_expr(expr);
 708         switch (expr->type) {
 709         case EXPR_COMPARE:
 710                 if (do_comparison(expr) == 1)
 711                         return 1;
 712                 break;
 713         case EXPR_PREOP:
 714                 if (expr->op == '!') {
 715                         if (implied_condition_false(expr->unop))
 716                                 return 1;
 717                         break;
 718                 }
 719                 break;
 720         default:
 721                 if (implied_not_equal(expr, 0) == 1)
 722                         return 1;
 723                 break;
 724         }
 725         return 0;
 726 }
 727
 728 int implied_condition_false(struct expression *expr)
 729 {
 730         struct expression *tmp;
 731         long long val;
 732
 733         if (!expr)
 734                 return 0;
 735
 736         if (known_condition_false(expr))
 737                 return 1;
 738
 739         switch (expr->type) {
 740         case EXPR_COMPARE:
 741                 if (do_comparison(expr) == 2)
 742                         return 1;
 743         case EXPR_PREOP:
 744                 if (expr->op == '!') {
 745                         if (implied_condition_true(expr->unop))
 746                                 return 1;
 747                         break;
 748                 }
 749                 tmp = strip_expr(expr);
 750                 if (tmp != expr)
 751                         return implied_condition_false(tmp);
 752                 break;
 753         default:
 754                 if (get_implied_value(expr, &val) && val == 0)
 755                         return 1;
 756                 break;
 757         }
 758         return 0;
 759 }