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         case ABSOLUTE_MIN:
 465         case ABSOLUTE_MAX:
 466                 if (!get_implied_value_helper(expr, &ret, implied))
 467                         *undefined = 1;
 468                 break;
 469         case FUZZYMAX:
 470                 if (!get_fuzzy_max_helper(expr, &ret))
 471                         *undefined = 1;
 472                 break;
 473         case FUZZYMIN:
 474                 if (!get_fuzzy_min_helper(expr, &ret))
 475                         *undefined = 1;
 476                 break;
 477         default:
 478                 *undefined = 1;
 479         }
 480         return ret;
 481 }
 482
 483 static int get_const_value(struct expression *expr, long long *val)
 484 {
 485         struct symbol *sym;
 486
 487         sym = expr->symbol;
 488         if (!sym)
 489                 return 0;
 490         if (!(sym->ctype.modifiers & MOD_CONST))
 491                 return 0;
 492         if (get_value(sym->initializer, val))
 493                 return 1;
 494         return 0;
 495 }
 496
 497 static long long _get_value(struct expression *expr, int *undefined, int implied)
 498 {
 499         long long ret = BOGUS;
 500
 501         if (!expr) {
 502                 *undefined = 1;
 503                 return BOGUS;
 504         }
 505         if (*undefined)
 506                 return BOGUS;
 507
 508         expr = strip_parens(expr);
 509
 510         switch (expr->type) {
 511         case EXPR_VALUE:
 512                 ret = expr->value;
 513                 ret = cast_to_type(expr, ret);
 514                 break;
 515         case EXPR_PREOP:
 516                 ret = handle_preop(expr, undefined, implied);
 517                 break;
 518         case EXPR_POSTOP:
 519                 ret = _get_value(expr->unop, undefined, implied);
 520                 break;
 521         case EXPR_CAST:
 522         case EXPR_FORCE_CAST:
 523         case EXPR_IMPLIED_CAST:
 524                 ret = _get_value(expr->cast_expression, undefined, implied);
 525                 return cast_to_type(expr, ret);
 526         case EXPR_BINOP:
 527                 ret = handle_binop(expr, undefined, implied);
 528                 break;
 529         case EXPR_COMPARE:
 530                 ret = handle_comparison(expr, undefined, implied);
 531                 break;
 532         case EXPR_LOGICAL:
 533                 ret = handle_logical(expr, undefined, implied);
 534                 break;
 535         case EXPR_PTRSIZEOF:
 536         case EXPR_SIZEOF:
 537                 ret = get_expression_value_nomod(expr);
 538                 break;
 539         case EXPR_SYMBOL:
 540                 if (get_const_value(expr, &ret))
 541                         break;
 542                 ret = _get_implied_value(expr, undefined, implied);
 543                 break;
 544         case EXPR_SELECT:
 545         case EXPR_CONDITIONAL:
 546                 ret = handle_conditional(expr, undefined, implied);
 547                 break;
 548         default:
 549                 ret = _get_implied_value(expr, undefined, implied);
 550         }
 551         if (*undefined)
 552                 return BOGUS;
 553         return ret;
 554 }
 555
 556 /* returns 1 if it can get a value literal or else returns 0 */
 557 int get_value(struct expression *expr, long long *val)
 558 {
 559         int undefined = 0;
 560
 561         *val = _get_value(expr, &undefined, NOTIMPLIED);
 562         if (undefined)
 563                 return 0;
 564         return 1;
 565 }
 566
 567 int get_implied_value(struct expression *expr, long long *val)
 568 {
 569         int undefined = 0;
 570
 571         *val =  _get_value(expr, &undefined, IMPLIED);
 572         return !undefined;
 573 }
 574
 575 int get_implied_min(struct expression *expr, long long *val)
 576 {
 577         int undefined = 0;
 578
 579         *val =  _get_value(expr, &undefined, IMPLIED_MIN);
 580         return !undefined;
 581 }
 582
 583 int get_implied_max(struct expression *expr, long long *val)
 584 {
 585         int undefined = 0;
 586
 587         *val =  _get_value(expr, &undefined, IMPLIED_MAX);
 588         return !undefined;
 589 }
 590
 591 int get_fuzzy_min(struct expression *expr, long long *val)
 592 {
 593         int undefined = 0;
 594
 595         *val =  _get_value(expr, &undefined, FUZZYMIN);
 596         return !undefined;
 597 }
 598
 599 int get_fuzzy_max(struct expression *expr, long long *val)
 600 {
 601         int undefined = 0;
 602
 603         *val =  _get_value(expr, &undefined, FUZZYMAX);
 604         return !undefined;
 605 }
 606
 607 int get_absolute_min(struct expression *expr, long long *val)
 608 {
 609         int undefined = 0;
 610         struct symbol *type;
 611
 612         *val =  _get_value(expr, &undefined, ABSOLUTE_MIN);
 613         if (!undefined)
 614                 return 1;
 615
 616         type = get_type(expr);
 617         *val = type_min(type);
 618         return 1;
 619 }
 620
 621 int get_absolute_max(struct expression *expr, long long *val)
 622 {
 623         int undefined = 0;
 624         struct symbol *type;
 625
 626         *val =  _get_value(expr, &undefined, ABSOLUTE_MAX);
 627         if (!undefined)
 628                 return 1;
 629
 630         type = get_type(expr);
 631         *val = type_max(type);
 632         return 1;
 633 }
 634
 635 int known_condition_true(struct expression *expr)
 636 {
 637         long long tmp;
 638
 639         if (!expr)
 640                 return 0;
 641
 642         if (get_value(expr, &tmp) && tmp)
 643                 return 1;
 644
 645         return 0;
 646 }
 647
 648 int known_condition_false(struct expression *expr)
 649 {
 650         if (!expr)
 651                 return 0;
 652
 653         if (is_zero(expr))
 654                 return 1;
 655
 656         if (expr->type == EXPR_CALL) {
 657                 if (sym_name_is("__builtin_constant_p", expr->fn))
 658                         return 1;
 659         }
 660         return 0;
 661 }
 662
 663 int implied_condition_true(struct expression *expr)
 664 {
 665         long long tmp;
 666
 667         if (!expr)
 668                 return 0;
 669
 670         if (known_condition_true(expr))
 671                 return 1;
 672         if (get_implied_value(expr, &tmp) && tmp)
 673                 return 1;
 674
 675         if (expr->type == EXPR_POSTOP)
 676                 return implied_condition_true(expr->unop);
 677
 678         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
 679                 return implied_not_equal(expr->unop, 1);
 680         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
 681                 return implied_not_equal(expr->unop, -1);
 682
 683         expr = strip_expr(expr);
 684         switch (expr->type) {
 685         case EXPR_COMPARE:
 686                 if (do_comparison(expr) == 1)
 687                         return 1;
 688                 break;
 689         case EXPR_PREOP:
 690                 if (expr->op == '!') {
 691                         if (implied_condition_false(expr->unop))
 692                                 return 1;
 693                         break;
 694                 }
 695                 break;
 696         default:
 697                 if (implied_not_equal(expr, 0) == 1)
 698                         return 1;
 699                 break;
 700         }
 701         return 0;
 702 }
 703
 704 int implied_condition_false(struct expression *expr)
 705 {
 706         struct expression *tmp;
 707         long long val;
 708
 709         if (!expr)
 710                 return 0;
 711
 712         if (known_condition_false(expr))
 713                 return 1;
 714
 715         switch (expr->type) {
 716         case EXPR_COMPARE:
 717                 if (do_comparison(expr) == 2)
 718                         return 1;
 719         case EXPR_PREOP:
 720                 if (expr->op == '!') {
 721                         if (implied_condition_true(expr->unop))
 722                                 return 1;
 723                         break;
 724                 }
 725                 tmp = strip_expr(expr);
 726                 if (tmp != expr)
 727                         return implied_condition_false(tmp);
 728                 break;
 729         default:
 730                 if (get_implied_value(expr, &val) && val == 0)
 731                         return 1;
 732                 break;
 733         }
 734         return 0;
 735 }