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