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