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         int res;
 242
 243         /* TODO: we should be able to handle this...  */
 244         if (implied == NOTIMPLIED) {
 245                 *undefined = 1;
 246                 return BOGUS;
 247         }
 248
 249         res = do_comparison(expr);
 250         if (res == 1)
 251                 return 1;
 252         if (res == 2)
 253                 return 0;
 254
 255         if (implied == IMPLIED_MIN || implied == FUZZYMIN)
 256                 return 0;
 257         if (implied == IMPLIED_MAX || implied == FUZZYMAX)
 258                 return 1;
 259
 260         *undefined = 1;
 261         return BOGUS;
 262 }
 263
 264 static long long handle_logical(struct expression *expr, int *undefined, int implied)
 265 {
 266         long long left_val, right_val;
 267
 268         /* TODO: we should be able to handle this...  */
 269         if (implied == NOTIMPLIED) {
 270                 *undefined = 1;
 271                 return BOGUS;
 272         }
 273
 274         if (get_implied_value(expr->left, &left_val) &&
 275                         get_implied_value(expr->right, &right_val)) {
 276                 switch (expr->op) {
 277                 case SPECIAL_LOGICAL_OR:
 278                         return left_val || right_val;
 279                 case SPECIAL_LOGICAL_AND:
 280                         return left_val && right_val;
 281                 default:
 282                         *undefined = 1;
 283                         return BOGUS;
 284                 }
 285         }
 286
 287         if (implied == IMPLIED_MIN || implied == FUZZYMIN)
 288                 return 0;
 289         if (implied == IMPLIED_MAX || implied == FUZZYMAX)
 290                 return 1;
 291
 292         *undefined = 1;
 293         return BOGUS;
 294 }
 295
 296 static int get_implied_value_helper(struct expression *expr, long long *val, int what)
 297 {
 298         struct smatch_state *state;
 299         struct symbol *sym;
 300         char *name;
 301
 302         if (get_value(expr, val))
 303                 return 1;
 304
 305         name = get_variable_from_expr(expr, &sym);
 306         if (!name)
 307                 return 0;
 308         state = get_state(SMATCH_EXTRA, name, sym);
 309         free_string(name);
 310         if (!state || !state->data)
 311                 return 0;
 312         if (what == IMPLIED)
 313                 return estate_get_single_value(state, val);
 314         if (what == IMPLIED_MAX) {
 315                 *val = estate_max(state);
 316                 if (*val == whole_range.max) /* this means just guessing */
 317                         return 0;
 318                 return 1;
 319         }
 320         *val = estate_min(state);
 321         if (*val == whole_range.min)
 322                 return 0;
 323         return 1;
 324 }
 325
 326 static int get_fuzzy_max_helper(struct expression *expr, long long *max)
 327 {
 328         struct sm_state *sm;
 329         struct sm_state *tmp;
 330
 331         if (get_implied_max(expr, max))
 332                 return 1;
 333
 334         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 335         if (!sm)
 336                 return 0;
 337
 338         *max = whole_range.min;
 339         FOR_EACH_PTR(sm->possible, tmp) {
 340                 long long new_min;
 341
 342                 new_min = estate_min(tmp->state);
 343                 if (new_min > *max)
 344                         *max = new_min;
 345         } END_FOR_EACH_PTR(tmp);
 346
 347         if (*max > whole_range.min)
 348                 return 1;
 349         return 0;
 350 }
 351
 352 static int get_fuzzy_min_helper(struct expression *expr, long long *min)
 353 {
 354         struct sm_state *sm;
 355         struct sm_state *tmp;
 356
 357         if (get_implied_min(expr, min))
 358                 return 1;
 359
 360         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 361         if (!sm)
 362                 return 0;
 363
 364         *min = whole_range.max;
 365         FOR_EACH_PTR(sm->possible, tmp) {
 366                 long long new_max;
 367
 368                 new_max = estate_max(tmp->state);
 369                 if (new_max < *min)
 370                         *min = new_max;
 371         } END_FOR_EACH_PTR(tmp);
 372
 373         if (*min < whole_range.max)
 374                 return 1;
 375         return 0;
 376 }
 377
 378 static long long _get_implied_value(struct expression *expr, int *undefined, int implied)
 379 {
 380         long long ret = BOGUS;
 381
 382         switch (implied) {
 383         case IMPLIED:
 384         case IMPLIED_MAX:
 385         case IMPLIED_MIN:
 386                 if (!get_implied_value_helper(expr, &ret, implied))
 387                         *undefined = 1;
 388                 break;
 389         case FUZZYMAX:
 390                 if (!get_fuzzy_max_helper(expr, &ret))
 391                         *undefined = 1;
 392                 break;
 393         case FUZZYMIN:
 394                 if (!get_fuzzy_min_helper(expr, &ret))
 395                         *undefined = 1;
 396                 break;
 397         default:
 398                 *undefined = 1;
 399         }
 400         return ret;
 401 }
 402
 403 static int get_const_value(struct expression *expr, long long *val)
 404 {
 405         struct symbol *sym;
 406
 407         sym = expr->symbol;
 408         if (!sym)
 409                 return 0;
 410         if (!(sym->ctype.modifiers & MOD_CONST))
 411                 return 0;
 412         if (get_value(sym->initializer, val))
 413                 return 1;
 414         return 0;
 415 }
 416
 417 static long long _get_value(struct expression *expr, int *undefined, int implied)
 418 {
 419         long long ret = BOGUS;
 420
 421         if (!expr) {
 422                 *undefined = 1;
 423                 return BOGUS;
 424         }
 425         if (*undefined)
 426                 return BOGUS;
 427
 428         expr = strip_parens(expr);
 429
 430         switch (expr->type) {
 431         case EXPR_VALUE:
 432                 ret = expr->value;
 433                 ret = cast_to_type(expr, ret);
 434                 break;
 435         case EXPR_PREOP:
 436                 ret = handle_preop(expr, undefined, implied);
 437                 break;
 438         case EXPR_POSTOP:
 439                 ret = _get_value(expr->unop, undefined, implied);
 440                 break;
 441         case EXPR_CAST:
 442         case EXPR_FORCE_CAST:
 443         case EXPR_IMPLIED_CAST:
 444                 ret = _get_value(expr->cast_expression, undefined, implied);
 445                 return cast_to_type(expr, ret);
 446         case EXPR_BINOP:
 447                 ret = handle_binop(expr, undefined, implied);
 448                 break;
 449         case EXPR_COMPARE:
 450                 ret = handle_comparison(expr, undefined, implied);
 451                 break;
 452         case EXPR_LOGICAL:
 453                 ret = handle_logical(expr, undefined, implied);
 454                 break;
 455         case EXPR_PTRSIZEOF:
 456         case EXPR_SIZEOF:
 457                 ret = get_expression_value_nomod(expr);
 458                 break;
 459         case EXPR_SYMBOL:
 460                 if (get_const_value(expr, &ret))
 461                         break;
 462         default:
 463                 ret = _get_implied_value(expr, undefined, implied);
 464         }
 465         if (*undefined)
 466                 return BOGUS;
 467         return ret;
 468 }
 469
 470 /* returns 1 if it can get a value literal or else returns 0 */
 471 int get_value(struct expression *expr, long long *val)
 472 {
 473         int undefined = 0;
 474
 475         *val = _get_value(expr, &undefined, NOTIMPLIED);
 476         if (undefined)
 477                 return 0;
 478         return 1;
 479 }
 480
 481 int get_implied_value(struct expression *expr, long long *val)
 482 {
 483         int undefined = 0;
 484
 485         *val =  _get_value(expr, &undefined, IMPLIED);
 486         return !undefined;
 487 }
 488
 489 int get_implied_min(struct expression *expr, long long *val)
 490 {
 491         int undefined = 0;
 492
 493         *val =  _get_value(expr, &undefined, IMPLIED_MIN);
 494         return !undefined;
 495 }
 496
 497 int get_implied_max(struct expression *expr, long long *val)
 498 {
 499         int undefined = 0;
 500
 501         *val =  _get_value(expr, &undefined, IMPLIED_MAX);
 502         return !undefined;
 503 }
 504
 505 int get_fuzzy_min(struct expression *expr, long long *val)
 506 {
 507         int undefined = 0;
 508
 509         *val =  _get_value(expr, &undefined, FUZZYMIN);
 510         return !undefined;
 511 }
 512
 513 int get_fuzzy_max(struct expression *expr, long long *val)
 514 {
 515         int undefined = 0;
 516
 517         *val =  _get_value(expr, &undefined, FUZZYMAX);
 518         return !undefined;
 519 }
 520
 521 int get_absolute_min(struct expression *expr, long long *val)
 522 {
 523         struct symbol *type;
 524         long long min;
 525
 526         type = get_type(expr);
 527         if (!type) {
 528                 if (get_value(expr, val))
 529                         return 1;
 530                 return 0;
 531         }
 532         min = type_min(type);
 533         if (!get_implied_min(expr, val) || *val < min)
 534                 *val = min;
 535         return 1;
 536 }
 537
 538 int get_absolute_max(struct expression *expr, long long *val)
 539 {
 540         struct symbol *type;
 541         long long max;
 542
 543         type = get_type(expr);
 544         if (!type) {
 545                 if (get_value(expr, val))
 546                         return 1;
 547                 return 0;
 548         }
 549         max = type_max(type);
 550         if (!get_implied_max(expr, val) || *val > max)
 551                 *val = max;
 552         if (*val < type_min(type))
 553                 *val = max;
 554         return 1;
 555 }
 556
 557 int known_condition_true(struct expression *expr)
 558 {
 559         long long tmp;
 560
 561         if (!expr)
 562                 return 0;
 563
 564         if (get_value(expr, &tmp) && tmp)
 565                 return 1;
 566
 567         return 0;
 568 }
 569
 570 int known_condition_false(struct expression *expr)
 571 {
 572         if (!expr)
 573                 return 0;
 574
 575         if (is_zero(expr))
 576                 return 1;
 577
 578         if (expr->type == EXPR_CALL) {
 579                 if (sym_name_is("__builtin_constant_p", expr->fn))
 580                         return 1;
 581         }
 582         return 0;
 583 }
 584
 585 int implied_condition_true(struct expression *expr)
 586 {
 587         long long tmp;
 588
 589         if (!expr)
 590                 return 0;
 591
 592         if (known_condition_true(expr))
 593                 return 1;
 594         if (get_implied_value(expr, &tmp) && tmp)
 595                 return 1;
 596
 597         if (expr->type == EXPR_POSTOP)
 598                 return implied_condition_true(expr->unop);
 599
 600         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
 601                 return implied_not_equal(expr->unop, 1);
 602         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
 603                 return implied_not_equal(expr->unop, -1);
 604
 605         expr = strip_expr(expr);
 606         switch (expr->type) {
 607         case EXPR_COMPARE:
 608                 if (do_comparison(expr) == 1)
 609                         return 1;
 610                 break;
 611         case EXPR_PREOP:
 612                 if (expr->op == '!') {
 613                         if (implied_condition_false(expr->unop))
 614                                 return 1;
 615                         break;
 616                 }
 617                 break;
 618         default:
 619                 if (implied_not_equal(expr, 0) == 1)
 620                         return 1;
 621                 break;
 622         }
 623         return 0;
 624 }
 625
 626 int implied_condition_false(struct expression *expr)
 627 {
 628         struct expression *tmp;
 629         long long val;
 630
 631         if (!expr)
 632                 return 0;
 633
 634         if (known_condition_false(expr))
 635                 return 1;
 636
 637         switch (expr->type) {
 638         case EXPR_COMPARE:
 639                 if (do_comparison(expr) == 2)
 640                         return 1;
 641         case EXPR_PREOP:
 642                 if (expr->op == '!') {
 643                         if (implied_condition_true(expr->unop))
 644                                 return 1;
 645                         break;
 646                 }
 647                 tmp = strip_expr(expr);
 648                 if (tmp != expr)
 649                         return implied_condition_false(tmp);
 650                 break;
 651         default:
 652                 if (get_implied_value(expr, &val) && val == 0)
 653                         return 1;
 654                 break;
 655         }
 656         return 0;
 657 }