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